bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/watson/ElementTree.java

/*******************************************************************************
 * Copyright (c) 2000, 2015 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *     James Blackburn (Broadcom Corp.) - ongoing development
 *     Lars Vogel <Lars.Vogel@vogella.com> - Bug 473427
 *******************************************************************************/
package org.eclipse.core.internal.watson;

import java.util.HashMap;
import org.eclipse.core.internal.dtree.*;
import org.eclipse.core.internal.utils.Messages;
import org.eclipse.core.internal.utils.StringPool;
import org.eclipse.core.runtime.*;
import org.eclipse.osgi.util.NLS;

/**
 * An ElementTree can be viewed as a generic rooted tree that stores
 * a hierarchy of elements.  An element in the tree consists of a
 * (name, data, children) 3-tuple.  The name can be any String, and
 * the data can be any Object.  The children are a collection of zero
 * or more elements that logically fall below their parent in the tree.
 * The implementation makes no guarantees about the ordering of children.
 *
 * Elements in the tree are referenced by a key that consists of the names
 * of all elements on the path from the root to that element in the tree.
 * For example, if root node "a" has child "b", which has child "c", element
 * "c" can be referenced in the tree using the key (/a/b/c).  Keys are represented
 * using IPath objects, where the Paths are relative to the root element of the
 * tree.
 * @see IPath
 *
 * Each ElementTree has a single root element that is created implicitly and
 * is always present in any tree.  This root corresponds to the key (/),
 * or the singleton <code>Path.ROOT</code>.  The root element cannot be created
 * or deleted, and its data and name cannot be set.  The root element's children
 * however can be modified (added, deleted, etc).  The root path can be obtained
 * using the <code>getRoot()</code> method.
 *
 * ElementTrees are modified in generations.  The method <code>newEmptyDelta()</code>
 * returns a new tree generation that can be modified arbitrarily by the user.
 * For the purpose of explanation, we call such a tree "active".
 * When the method <code>immutable()</code> is called, that tree generation is
 * frozen, and can never again be modified.  A tree must be immutable before
 * a new tree generation can start.  Since all ancestor trees are immutable,
 * different active trees can have ancestors in common without fear of
 * thread corruption problems.
 *
 * Internally, any single tree generation is simply stored as the
 * set of changes between itself and its most recent ancestor (its parent).
 * This compact delta representation allows chains of element trees to
 * be created at relatively low cost.  Clients of the ElementTree can
 * instantaneously "undo" sets of changes by navigating up to the parent
 * tree using the <code>getParent()</code> method.
 *
 * Although the delta representation is compact, extremely long delta
 * chains make for a large structure that is potentially slow to query.
 * For this reason, the client is encouraged to minimize delta chain
 * lengths using the <code>collapsing(int)</code> and <code>makeComplete()</code>
 * methods.  The <code>getDeltaDepth()</code> method can be used to
 * discover the length of the delta chain.  The entire delta chain can
 * also be re-oriented in terms of the current element tree using the
 * <code>reroot()</code> operation.
 *
 * Classes are also available for tree serialization and navigation.
 * @see ElementTreeReader
 * @see ElementTreeWriter
 * @see ElementTreeIterator
 *
 * Finally, why are ElementTrees in a package called "watson"?
 * 	- "It's ElementTree my dear Watson, ElementTree."
 */
public class ElementTree {
	protected DeltaDataTree tree;
	protected IElementTreeData userData;

	private class ChildIDsCache {
		ChildIDsCache(IPath path, IPath[] childPaths) {
			this.path = path;
			this.childPaths = childPaths;
		}

		IPath path;
		IPath[] childPaths;
	}

	private volatile ChildIDsCache childIDsCache = null;

	private volatile DataTreeLookup lookupCache = null;

	private volatile DataTreeLookup lookupCacheIgnoreCase = null;

	private static int treeCounter = 0;
	private int treeStamp;

	/**
	 * Creates a new empty element tree.
	 */
	public ElementTree() {
		initialize(new DeltaDataTree());
	}

	/**
	 * Creates an element tree given its internal node representation.
	 */
	protected ElementTree(DataTreeNode rootNode) {
		initialize(rootNode);
	}

	/**
	 * Creates a new element tree with the given data tree as its representation.
	 */
	protected ElementTree(DeltaDataTree tree) {
		initialize(tree);
	}

	/**
	 * Creates a new empty delta element tree having the
	 * given tree as its parent.
	 */
	protected ElementTree(ElementTree parent) {
		if (!parent.isImmutable()) {
			parent.immutable();
		}

		/* copy the user data forward */
		IElementTreeData data = parent.getTreeData();
		if (data != null) {
			userData = (IElementTreeData) data.clone();
		}

		initialize(parent.tree.newEmptyDeltaTree());
	}

	/**
	 * Collapses this tree so that the given ancestor becomes its
	 * immediate parent.  Afterwards, this tree will still have exactly the
	 * same contents, but its internal structure will be compressed.
	 *
	 * <p> This operation should be used to collapse chains of
	 * element trees created by newEmptyDelta()/immutable().
	 *
	 * <p>This element tree must be immutable at the start of this operation,
	 * and will be immutable afterwards.
	 * @return this tree.
	 */
	public synchronized ElementTree collapseTo(ElementTree parent) {
		Assert.isTrue(tree.isImmutable());
		if (this == parent) {
			//already collapsed
			return this;
		}
		//collapse my tree to be a forward delta of the parent's tree.
		tree.collapseTo(parent.tree, DefaultElementComparator.getComparator());
		return this;
	}

	/**
	 * Creates the indicated element and sets its element info.
	 * The parent element must be present, otherwise an IllegalArgumentException
	 * is thrown. If the indicated element is already present in the tree,
	 * its element info is replaced and any existing children are
	 * deleted.
	 *
	 * @param key element key
	 * @param data element data, or <code>null</code>
	 */
	public synchronized void createElement(IPath key, Object data) {
		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return;

		// Clear the child IDs cache in case it's referring to this parent. This is conservative.
		childIDsCache = null;

		IPath parent = key.removeLastSegments(1);
		try {
			tree.createChild(parent, key.lastSegment(), data);
		} catch (ObjectNotFoundException e) {
			elementNotFound(parent);
		}
		// Set the lookup to be this newly created object.
		lookupCache = DataTreeLookup.newLookup(key, true, data, true);
		lookupCacheIgnoreCase = null;
	}

	/**
	 * Creates or replaces the subtree below the given path with
	 * the given tree. The subtree can only have one child below
	 * the root, which will become the node specified by the given
	 * key in this tree.
	 *
	 * @param key The path of the new subtree in this tree.
	 * @see #getSubtree(IPath)
	 */
	public synchronized void createSubtree(IPath key, ElementTree subtree) {
		/* don't allow creating subtrees at the root */
		if (key.isRoot()) {
			throw new IllegalArgumentException(Messages.watson_noModify);
		}

		// Clear the child IDs cache in case it's referring to this parent.
		// This is conservative.
		childIDsCache = null;
		// Clear the lookup cache, in case the element being created is the same
		// as for the last lookup.
		lookupCache = lookupCacheIgnoreCase = null;
		try {
			/* don't copy the implicit root node of the subtree */
			IPath[] children = subtree.getChildren(subtree.getRoot());
			if (children.length != 1) {
				throw new IllegalArgumentException(Messages.watson_illegalSubtree);
			}

			/* get the subtree for the specified key */
			DataTreeNode node = (DataTreeNode) subtree.tree.copyCompleteSubtree(children[0]);

			/* insert the subtree in this tree */
			tree.createSubtree(key, node);

		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
		}
	}

	/**
	 * Deletes the indicated element and its descendents.
	 * The element must be present.
	 */
	public synchronized void deleteElement(IPath key) {
		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return;

		// Clear the child IDs cache in case it's referring to this parent.
		// This is conservative.
		childIDsCache = null;
		// Clear the lookup cache, in case the element being deleted is the same
		// as for the last lookup.
		lookupCache = lookupCacheIgnoreCase = null;
		try {
			tree.deleteChild(key.removeLastSegments(1), key.lastSegment());
		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
		}
	}

	/**
	 * Complains that an element was not found
	 */
	protected void elementNotFound(IPath key) {
		throw new IllegalArgumentException(NLS.bind(Messages.watson_elementNotFound, key));
	}

	/**
	 * Given an array of element trees, returns the index of the
	 * oldest tree.  The oldest tree is the tree such that no
	 * other tree in the array is a descendent of that tree.
	 * Note that this counter-intuitive concept of oldest is based on the
	 * ElementTree orientation such that the complete tree is always the
	 * newest tree.
	 */
	public static int findOldest(ElementTree[] trees) {

		/* first put all the trees in a hashtable */
		HashMap<ElementTree, ElementTree> candidates = new HashMap<>((int) (trees.length * 1.5 + 1));
		for (int i = 0; i < trees.length; i++) {
			candidates.put(trees[i], trees[i]);
		}

		/* keep removing parents until only one tree remains */
		ElementTree oldestSoFar = null;
		while (candidates.size() > 0) {
			/* get a new candidate */
			ElementTree current = candidates.values().iterator().next();

			/* remove this candidate from the table */
			candidates.remove(current);

			/* remove all of this element's parents from the list of candidates*/
			ElementTree parent = current.getParent();

			/* walk up chain until we hit the root or a tree we have already tested */
			while (parent != null && parent != oldestSoFar) {
				candidates.remove(parent);
				parent = parent.getParent();
			}

			/* the current candidate is the oldest tree seen so far */
			oldestSoFar = current;

			/* if the table is now empty, we have a winner */
		}
		Assert.isNotNull(oldestSoFar);

		/* return the appropriate index */
		for (int i = 0; i < trees.length; i++) {
			if (trees[i] == oldestSoFar) {
				return i;
			}
		}
		Assert.isTrue(false, "Should not get here"); //$NON-NLS-1$
		return -1;
	}

	/**
	 * Returns the number of children of the element
	 * specified by the given path.
	 * The given element must be present in this tree.
	 */
	public synchronized int getChildCount(IPath key) {
		Assert.isNotNull(key);
		return getChildIDs(key).length;
	}

	/**
	 * Returns the IDs of the children of the specified element.
	 * If the specified element is null, returns the root element path.
	 */
	protected IPath[] getChildIDs(IPath key) {
		ChildIDsCache cache = childIDsCache; // Grab it in case it's replaced concurrently.
		if (cache != null && cache.path == key) {
			return cache.childPaths;
		}
		try {
			if (key == null)
				return new IPath[] {tree.rootKey()};
			IPath[] children = tree.getChildren(key);
			childIDsCache = new ChildIDsCache(key, children); // Cache the result
			return children;
		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
			return null; // can't get here
		}
	}

	/**
	 * Returns the paths of the children of the element
	 * specified by the given path.
	 * The given element must be present in this tree.
	 */
	public synchronized IPath[] getChildren(IPath key) {
		Assert.isNotNull(key);
		return getChildIDs(key);
	}

	/**
	 * Returns the internal data tree.
	 */
	public DeltaDataTree getDataTree() {
		return tree;
	}

	/**
	 * Returns the element data for the given element identifier.
	 * The given element must be present in this tree.
	 */
	public synchronized Object getElementData(IPath key) {
		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return null;
		DataTreeLookup lookup = lookupCache; // Grab it in case it's replaced concurrently.
		if (lookup == null || lookup.key != key)
			lookupCache = lookup = tree.lookup(key);
		if (lookup.isPresent)
			return lookup.data;
		elementNotFound(key);
		return null; // can't get here
	}

	/**
	 * Returns the element data for the given element identifier.
	 * The given element must be present in this tree.
	 */
	public synchronized Object getElementDataIgnoreCase(IPath key) {
		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return null;
		DataTreeLookup lookup = lookupCacheIgnoreCase; // Grab it in case it's replaced concurrently.
		if (lookup == null || lookup.key != key)
			lookupCacheIgnoreCase = lookup = tree.lookupIgnoreCase(key);
		if (lookup.isPresent)
			return lookup.data;
		elementNotFound(key);
		return null; // can't get here
	}

	/**
	 * Returns the names of the children of the specified element.
	 * The specified element must exist in the tree.
	 * If the specified element is null, returns the root element path.
	 */
	public synchronized String[] getNamesOfChildren(IPath key) {
		try {
			if (key == null)
				return new String[] {""}; //$NON-NLS-1$
			return tree.getNamesOfChildren(key);
		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
			return null; // can't get here
		}
	}

	/**
	 * Returns the parent tree, or <code>null</code> if there is no parent.
	 */
	public ElementTree getParent() {
		DeltaDataTree parentTree = tree.getParent();
		if (parentTree == null) {
			return null;
		}
		// The parent ElementTree is stored as the node data of the parent DeltaDataTree,
		// to simplify canonicalization in the presence of rerooting.
		return (ElementTree) parentTree.getData(tree.rootKey());
	}

	/**
	 * Returns the root node of this tree.
	 */
	public IPath getRoot() {
		return getChildIDs(null)[0];
	}

	/**
	 * Returns the subtree rooted at the given key. In the resulting tree,
	 * the implicit root node (designated by Path.ROOT), has a single child,
	 * which is the node specified by the given key in this tree.
	 *
	 * The subtree must be present in this tree.
	 *
	 * @see #createSubtree(IPath, ElementTree)
	 */
	public ElementTree getSubtree(IPath key) {
		/* the subtree of the root of this tree is just this tree */
		if (key.isRoot()) {
			return this;
		}
		try {
			DataTreeNode elementNode = (DataTreeNode) tree.copyCompleteSubtree(key);
			return new ElementTree(elementNode);
		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
			return null;
		}
	}

	/**
	 * Returns the user data associated with this tree.
	 */
	public IElementTreeData getTreeData() {
		return userData;
	}

	/**
	 * Returns true if there have been changes in the tree between the two
	 * given layers.  The two must be related and new must be newer than old.
	 * That is, new must be an ancestor of old.
	 */
	public static boolean hasChanges(ElementTree newLayer, ElementTree oldLayer, IElementComparator comparator, boolean inclusive) {
		// if any of the layers are null, assume that things have changed
		if (newLayer == null || oldLayer == null)
			return true;
		if (newLayer == oldLayer)
			return false;
		//if the tree data has changed, then the tree has changed
		if (comparator.compare(newLayer.getTreeData(), oldLayer.getTreeData()) != IElementComparator.K_NO_CHANGE)
			return true;

		// The tree structure has the top layer(s) (i.e., tree) parentage pointing down to a complete
		// layer whose parent is null.  The bottom layers (i.e., operationTree) point up to the
		// common complete layer whose parent is null.  The complete layer moves up as
		// changes happen.  To see if any changes have happened, we should consider only
		// layers whose parent is not null.  That is, skip the complete layer as it will clearly not be
		// empty.

		// look down from the current layer (always inclusive) if the top layer is mutable
		ElementTree stopLayer = null;
		if (newLayer.isImmutable())
			// if the newLayer is immutable, the tree structure all points up so ensure that
			// when searching up, we stop at newLayer (inclusive)
			stopLayer = newLayer.getParent();
		else {
			ElementTree layer = newLayer;
			while (layer != null && layer.getParent() != null) {
				if (!layer.getDataTree().isEmptyDelta())
					return true;
				layer = layer.getParent();
			}
		}

		// look up from the layer at which we started to null or newLayer's parent (variably inclusive)
		// depending on whether newLayer is mutable.
		ElementTree layer = inclusive ? oldLayer : oldLayer.getParent();
		while (layer != null && layer.getParent() != stopLayer) {
			if (!layer.getDataTree().isEmptyDelta())
				return true;
			layer = layer.getParent();
		}
		// didn't find anything that changed
		return false;
	}

	/**
	 * Makes this tree immutable (read-only); ignored if it is already
	 * immutable.
	 */
	public synchronized void immutable() {
		if (!tree.isImmutable()) {
			tree.immutable();
			/* need to clear the lookup cache since it reports whether results were found
			 in the topmost delta, and the order of deltas is changing */
			lookupCache = lookupCacheIgnoreCase = null;
			/* reroot the delta chain at this tree */
			tree.reroot();
		}
	}

	/**
	 * Returns true if this element tree includes an element with the given
	 * key, false otherwise.
	 */
	public synchronized boolean includes(IPath key) {
		DataTreeLookup lookup = lookupCache; // Grab it in case it's replaced concurrently.
		if (lookup == null || lookup.key != key) {
			lookupCache = lookup = tree.lookup(key);
		}
		return lookup.isPresent;
	}

	/**
	 * Returns true if this element tree includes an element with the given
	 * key, ignoring the case of the key, and false otherwise.
	 */
	public boolean includesIgnoreCase(IPath key) {
		DataTreeLookup lookup = lookupCacheIgnoreCase; // Grab it in case it's replaced concurrently.
		if (lookup == null || lookup.key != key) {
			lookupCacheIgnoreCase = lookup = tree.lookupIgnoreCase(key);
		}
		return lookup.isPresent;
	}

	protected void initialize(DataTreeNode rootNode) {
		/* create the implicit root node */
		initialize(new DeltaDataTree(new DataTreeNode(null, null, new AbstractDataTreeNode[] {rootNode})));
	}

	protected void initialize(DeltaDataTree newTree) {
		// Keep this element tree as the data of the root node.
		// Useful for canonical results for ElementTree.getParent().
		// see getParent().
		treeStamp = treeCounter++;
		newTree.setData(newTree.rootKey(), this);
		this.tree = newTree;
	}

	/**
	 * Returns whether this tree is immutable.
	 */
	public boolean isImmutable() {
		return tree.isImmutable();
	}

	/**
	 * Merges a chain of deltas for a certain subtree to this tree.
	 * If this tree has any data in the specified subtree, it will
	 * be overwritten.  The receiver tree must be open, and it will
	 * be made immutable during the merge operation.  The trees in the
	 * provided array will be replaced by new trees that have been
	 * merged into the receiver's delta chain.
	 *
	 * @param path The path of the subtree chain to merge
	 * @param trees The chain of trees to merge.  The trees can be
	 *  in any order, but they must all form a simple ancestral chain.
	 * @return A new open tree with the delta chain merged in.
	 */
	public ElementTree mergeDeltaChain(IPath path, ElementTree[] trees) {
		if (path == null || trees == null) {
			throw new IllegalArgumentException(NLS.bind(Messages.watson_nullArg, "ElementTree.mergeDeltaChain")); //$NON-NLS-1$
		}

		/* The tree has to be open */
		if (isImmutable()) {
			throw new IllegalArgumentException(Messages.watson_immutable);
		}
		ElementTree current = this;
		if (trees.length > 0) {
			/* find the oldest tree to be merged */
			ElementTree toMerge = trees[findOldest(trees)];

			/* merge the trees from oldest to newest */
			while (toMerge != null) {
				if (path.isRoot()) {
					//copy all the children
					IPath[] children = toMerge.getChildren(Path.ROOT);
					for (int i = 0; i < children.length; i++) {
						current.createSubtree(children[i], toMerge.getSubtree(children[i]));
					}
				} else {
					//just copy the specified node
					current.createSubtree(path, toMerge.getSubtree(path));
				}
				current.immutable();

				/* replace the tree in the array */
				/* we have to go through all trees because there may be duplicates */
				for (int i = 0; i < trees.length; i++) {
					if (trees[i] == toMerge) {
						trees[i] = current;
					}
				}
				current = current.newEmptyDelta();
				toMerge = toMerge.getParent();
			}
		}
		return current;
	}

	/**
	 * Creates a new element tree which is represented as a delta on this one.
	 * Initially they have the same content.  Subsequent changes to the new
	 * tree will not affect this one.
	 */
	public synchronized ElementTree newEmptyDelta() {
		// Don't want old trees hanging onto cached infos.
		lookupCache = lookupCacheIgnoreCase = null;
		return new ElementTree(this);
	}

	/**
	 * Returns a mutable copy of the element data for the given path.
	 * This copy will be held onto in the most recent delta.
	 * ElementTree data MUST implement the IElementTreeData interface
	 * for this method to work.  If the data does not define that interface
	 * this method will fail.
	 */
	public synchronized Object openElementData(IPath key) {
		Assert.isTrue(!isImmutable());

		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return null;
		DataTreeLookup lookup = lookupCache; // Grab it in case it's replaced concurrently.
		if (lookup == null || lookup.key != key) {
			lookupCache = lookup = tree.lookup(key);
		}
		if (lookup.isPresent) {
			if (lookup.foundInFirstDelta)
				return lookup.data;
			/**
			 * The node has no data in the most recent delta.
			 * Pull it up to the present delta by setting its data with a clone.
			 */
			IElementTreeData oldData = (IElementTreeData) lookup.data;
			if (oldData != null) {
				try {
					Object newData = oldData.clone();
					tree.setData(key, newData);
					lookupCache = lookupCacheIgnoreCase = null;
					return newData;
				} catch (ObjectNotFoundException e) {
					elementNotFound(key);
				}
			}
		} else {
			elementNotFound(key);
		}
		return null;
	}

	/**
	 * Sets the element for the given element identifier.
	 * The given element must be present in this tree.
	 * @param key element identifier
	 * @param data element info, or <code>null</code>
	 */
	public synchronized void setElementData(IPath key, Object data) {
		/* don't allow modification of the implicit root */
		if (key.isRoot())
			return;

		Assert.isNotNull(key);
		// Clear the lookup cache, in case the element being modified is the same
		// as for the last lookup.
		lookupCache = lookupCacheIgnoreCase = null;
		try {
			tree.setData(key, data);
		} catch (ObjectNotFoundException e) {
			elementNotFound(key);
		}
	}

	/**
	 * Sets the user data associated with this tree.
	 */
	public void setTreeData(IElementTreeData data) {
		userData = data;
	}

	/* (non-Javadoc)
	 * Method declared on IStringPoolParticipant
	 */
	public void shareStrings(StringPool set) {
		tree.storeStrings(set);
	}

	/**
	 * Returns a string representation of this element tree's
	 * structure suitable for debug purposes.
	 */
	public String toDebugString() {
		final StringBuilder buffer = new StringBuilder("\n"); //$NON-NLS-1$
		IElementContentVisitor visitor = new IElementContentVisitor() {
			@Override
			public boolean visitElement(ElementTree aTree, IPathRequestor elementID, Object elementContents) {
				buffer.append(elementID.requestPath() + " " + elementContents + "\n"); //$NON-NLS-1$ //$NON-NLS-2$
				return true;
			}
		};
		new ElementTreeIterator(this, Path.ROOT).iterate(visitor);
		return buffer.toString();
	}

	@Override
	public String toString() {
		return "ElementTree(" + treeStamp + ")"; //$NON-NLS-1$ //$NON-NLS-2$
	}
}