Copyright (c) 2000, 2015 IBM Corporation and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
    IBM Corporation - initial API and implementation
    Martin Oberhuber (Wind River) - [105554] handle cyclic symbolic links
    Martin Oberhuber (Wind River) - [232426] shared prefix histories for symlinks
    Serge Beauchamp (Freescale Semiconductor) - [252996] add resource filtering
    Martin Oberhuber (Wind River) - [292267] OutOfMemoryError due to leak in UnifiedTree
    James Blackburn (Broadcom Corp.) - ongoing development
    Lars Vogel  - Bug 473427
    Sergey Prigogin (Google) -  ongoing development
/*******************************************************************************
 * Copyright (c) 2000, 2015 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *     Martin Oberhuber (Wind River) - [105554] handle cyclic symbolic links
 *     Martin Oberhuber (Wind River) - [232426] shared prefix histories for symlinks
 *     Serge Beauchamp (Freescale Semiconductor) - [252996] add resource filtering
 *     Martin Oberhuber (Wind River) - [292267] OutOfMemoryError due to leak in UnifiedTree
 *     James Blackburn (Broadcom Corp.) - ongoing development
 *     Lars Vogel <Lars.Vogel@vogella.com> - Bug 473427
 *     Sergey Prigogin (Google) -  ongoing development
 *******************************************************************************/
package org.eclipse.core.internal.localstore;

import java.io.IOException;
import java.nio.file.Path;
import java.util.*;
import java.util.regex.Pattern;
import org.eclipse.core.filesystem.*;
import org.eclipse.core.internal.refresh.RefreshJob;
import org.eclipse.core.internal.resources.*;
import org.eclipse.core.resources.IContainer;
import org.eclipse.core.resources.IResource;
import org.eclipse.core.runtime.*;
import org.eclipse.core.runtime.jobs.Job;

Represents the workspace's tree merged with the file system's tree.
/**
 * Represents the workspace's tree merged with the file system's tree.
 */
public class UnifiedTree {

	
Skip advanced link checking, see bug 537449 /** Skip advanced link checking, see bug 537449 */
	private static boolean disable_advanced_recursive_link_checks = System.getProperty("org.eclipse.core.resources.disable_advanced_recursive_link_checks") != null; //$NON-NLS-1$

	
special node to mark the separation of a node's children /** special node to mark the separation of a node's children */
	protected static final UnifiedTreeNode childrenMarker = new UnifiedTreeNode(null, null, null, null, false);

	private static final Iterator<UnifiedTreeNode> EMPTY_ITERATOR = Collections.EMPTY_LIST.iterator();

	
special node to mark the beginning of a level in the tree /** special node to mark the beginning of a level in the tree */
	protected static final UnifiedTreeNode levelMarker = new UnifiedTreeNode(null, null, null, null, false);

	private static final IFileInfo[] NO_CHILDREN = {};

	
Singleton to indicate no local children /** Singleton to indicate no local children */
	private static final IResource[] NO_RESOURCES = {};

	
True if the level of the children of the current node are valid according
to the requested refresh depth, false otherwise
/**
	 * True if the level of the children of the current node are valid according
	 * to the requested refresh depth, false otherwise
	 */
	protected boolean childLevelValid;

	
an IFileTree which can be used to build a unified tree/** an IFileTree which can be used to build a unified tree*/
	protected IFileTree fileTree;

	
Spare node objects available for reuse /** Spare node objects available for reuse */
	protected ArrayList<UnifiedTreeNode> freeNodes = new ArrayList<>();
	
tree's actual level /** tree's actual level */
	protected int level;
	
our queue /** our queue */
	protected LinkedList<UnifiedTreeNode> queue;

	
path prefixes for checking symbolic link cycles /** path prefixes for checking symbolic link cycles */
	protected PrefixPool pathPrefixHistory, rootPathHistory;

	
tree's root /** tree's root */
	protected IResource root;

	
The root must only be a file or a folder.
/**
	 * The root must only be a file or a folder.
	 */
	public UnifiedTree(IResource root) {
		setRoot(root);
	}

	
Pass in a a root for the tree, a file tree containing all of the entries for this
tree and a flag indicating whether the UnifiedTree should consult the fileTree where
possible for entries
Params:
root – 
fileTree – /**
	 * Pass in a a root for the tree, a file tree containing all of the entries for this
	 * tree and a flag indicating whether the UnifiedTree should consult the fileTree where
	 * possible for entries
	 * @param root
	 * @param fileTree
	 */
	public UnifiedTree(IResource root, IFileTree fileTree) {
		this(root);
		this.fileTree = fileTree;
	}

	public void accept(IUnifiedTreeVisitor visitor) throws CoreException {
		accept(visitor, IResource.DEPTH_INFINITE);
	}

	
Performs a breadth-first traversal of the unified tree, passing each
node to the provided visitor.
/**
	 * Performs a breadth-first traversal of the unified tree, passing each
	 * node to the provided visitor.
	 */
	public void accept(IUnifiedTreeVisitor visitor, int depth) throws CoreException {
		Assert.isNotNull(root);
		initializeQueue();
		setLevel(0, depth);
		while (!queue.isEmpty()) {
			UnifiedTreeNode node = queue.remove();
			if (isChildrenMarker(node))
				continue;
			if (isLevelMarker(node)) {
				if (!setLevel(getLevel() + 1, depth))
					break;
				continue;
			}
			if (visitor.visit(node))
				addNodeChildrenToQueue(node);
			else
				removeNodeChildrenFromQueue(node);
			//allow reuse of the node, but don't let the freeNodes list grow infinitely
			if (freeNodes.size() < 32767) {
				//free memory-consuming elements of the node for garbage collection
				node.releaseForGc();
				freeNodes.add(node);
			}
			//else, the whole node will be garbage collected since there is no
			//reference to it any more.
		}
	}

	protected void addChildren(UnifiedTreeNode node) {
		Resource parent = (Resource) node.getResource();

		// is there a possibility to have children?
		int parentType = parent.getType();
		if (parentType == IResource.FILE && !node.isFolder())
			return;

		//don't refresh resources in closed or non-existent projects
		if (!parent.getProject().isAccessible())
			return;

		// get the list of resources in the file system
		// don't ask for local children if we know it doesn't exist locally
		IFileInfo[] list = node.existsInFileSystem() ? getLocalList(node) : NO_CHILDREN;
		int localIndex = 0;

		// See if the children of this resource have been computed before
		ResourceInfo resourceInfo = parent.getResourceInfo(false, false);
		int flags = parent.getFlags(resourceInfo);
		boolean unknown = ResourceInfo.isSet(flags, ICoreConstants.M_CHILDREN_UNKNOWN);

		// get the list of resources in the workspace
		if (!unknown && (parentType == IResource.FOLDER || parentType == IResource.PROJECT) && parent.exists(flags, true)) {
			IResource target = null;
			UnifiedTreeNode child = null;
			IResource[] members;
			try {
				members = ((IContainer) parent).members(IContainer.INCLUDE_TEAM_PRIVATE_MEMBERS | IContainer.INCLUDE_HIDDEN);
			} catch (CoreException e) {
				members = NO_RESOURCES;
			}
			int workspaceIndex = 0;
			//iterate simultaneously over file system and workspace members
			while (workspaceIndex < members.length) {
				target = members[workspaceIndex];
				String name = target.getName();
				IFileInfo localInfo = localIndex < list.length ? list[localIndex] : null;
				int comp = localInfo != null ? name.compareTo(localInfo.getName()) : -1;
				//special handling for linked resources
				if (target.isLinked()) {
					//child will be null if location is undefined
					child = createChildForLinkedResource(target);
					workspaceIndex++;
					//if there is a matching local file, skip it - it will be blocked by the linked resource
					if (comp == 0)
						localIndex++;
				} else if (comp == 0) {
					// resource exists in workspace and file system --> localInfo is non-null
					//create workspace-only node for symbolic link that creates a cycle
					if (localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) && localInfo.isDirectory() && isRecursiveLink(node.getStore(), localInfo))
						child = createNode(target, null, null, true);
					else
						child = createNode(target, null, localInfo, true);
					localIndex++;
					workspaceIndex++;
				} else if (comp > 0) {
					// resource exists only in file system
					//don't create a node for symbolic links that create a cycle
					if (localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) && localInfo.isDirectory() && isRecursiveLink(node.getStore(), localInfo))
						child = null;
					else
						child = createChildNodeFromFileSystem(node, localInfo);
					localIndex++;
				} else {
					// resource exists only in the workspace
					child = createNode(target, null, null, true);
					workspaceIndex++;
				}
				if (child != null)
					addChildToTree(node, child);
			}
		}

		/* process any remaining resource from the file system */
		addChildrenFromFileSystem(node, list, localIndex);

		/* Mark the children as now known */
		if (unknown) {
			// Don't open the info - we might not be inside a workspace-modifying operation
			resourceInfo = parent.getResourceInfo(false, false);
			if (resourceInfo != null)
				resourceInfo.clear(ICoreConstants.M_CHILDREN_UNKNOWN);
		}

		/* if we added children, add the childMarker separator */
		if (node.getFirstChild() != null)
			addChildrenMarker();
	}

	protected void addChildrenFromFileSystem(UnifiedTreeNode node, IFileInfo[] childInfos, int index) {
		if (childInfos == null)
			return;
		for (int i = index; i < childInfos.length; i++) {
			IFileInfo info = childInfos[i];
			//don't create a node for symbolic links that create a cycle
			if (!info.getAttribute(EFS.ATTRIBUTE_SYMLINK) || !info.isDirectory() || !isRecursiveLink(node.getStore(), info))
				addChildToTree(node, createChildNodeFromFileSystem(node, info));
		}
	}

	protected void addChildrenMarker() {
		addElementToQueue(childrenMarker);
	}

	protected void addChildToTree(UnifiedTreeNode node, UnifiedTreeNode child) {
		if (node.getFirstChild() == null)
			node.setFirstChild(child);
		addElementToQueue(child);
	}

	protected void addElementToQueue(UnifiedTreeNode target) {
		queue.add(target);
	}

	protected void addNodeChildrenToQueue(UnifiedTreeNode node) {
		/* if the first child is not null we already added the children */
		/* If the children won't be at a valid level for the refresh depth, don't bother adding them */
		if (!childLevelValid || node.getFirstChild() != null)
			return;
		addChildren(node);
		if (queue.isEmpty())
			return;
		//if we're about to change levels, then the children just added
		//are the last nodes for their level, so add a level marker to the queue
		UnifiedTreeNode nextNode = queue.peek();
		if (isChildrenMarker(nextNode))
			queue.remove();
		nextNode = queue.peek();
		if (isLevelMarker(nextNode))
			addElementToQueue(levelMarker);
	}

	protected void addRootToQueue() {
		//don't refresh in closed projects
		if (!root.getProject().isAccessible())
			return;
		IFileStore store = ((Resource) root).getStore();
		IFileInfo fileInfo = fileTree != null ? fileTree.getFileInfo(store) : store.fetchInfo();
		UnifiedTreeNode node = createNode(root, store, fileInfo, root.exists());
		if (node.existsInFileSystem() || node.existsInWorkspace())
			addElementToQueue(node);
	}

	
Creates a tree node for a resource that is linked in a different file system location.
/**
	 * Creates a tree node for a resource that is linked in a different file system location.
	 */
	protected UnifiedTreeNode createChildForLinkedResource(IResource target) {
		IFileStore store = ((Resource) target).getStore();
		return createNode(target, store, store.fetchInfo(), true);
	}

	
Creates a child node for a location in the file system. Does nothing and returns null if the location does not correspond to a valid file/folder.
/**
	 * Creates a child node for a location in the file system. Does nothing and returns null if the location does not correspond to a valid file/folder.
	 */
	protected UnifiedTreeNode createChildNodeFromFileSystem(UnifiedTreeNode parent, IFileInfo info) {
		IPath childPath = parent.getResource().getFullPath().append(info.getName());
		int type = info.isDirectory() ? IResource.FOLDER : IResource.FILE;
		IResource target = getWorkspace().newResource(childPath, type);
		return createNode(target, null, info, target.exists());
	}

	
Factory method for creating a node for this tree.  If the file exists on
disk, either the parent store or child store can be provided. Providing
only the parent store avoids creation of the child store in cases where
it is not needed. The store object is only needed for directories for
simple file system traversals, so this avoids creating store objects
for all files.
/**
	 * Factory method for creating a node for this tree.  If the file exists on
	 * disk, either the parent store or child store can be provided. Providing
	 * only the parent store avoids creation of the child store in cases where
	 * it is not needed. The store object is only needed for directories for
	 * simple file system traversals, so this avoids creating store objects
	 * for all files.
	 */
	protected UnifiedTreeNode createNode(IResource resource, IFileStore store, IFileInfo info, boolean existsWorkspace) {
		//first check for reusable objects
		UnifiedTreeNode node = null;
		int size = freeNodes.size();
		if (size > 0) {
			node = freeNodes.remove(size - 1);
			node.reuse(this, resource, store, info, existsWorkspace);
			return node;
		}
		//none available, so create a new one
		return new UnifiedTreeNode(this, resource, store, info, existsWorkspace);
	}

	protected Iterator<UnifiedTreeNode> getChildren(UnifiedTreeNode node) {
		/* if first child is null we need to add node's children to queue */
		if (node.getFirstChild() == null)
			addNodeChildrenToQueue(node);

		/* if the first child is still null, the node does not have any children */
		if (node.getFirstChild() == null)
			return EMPTY_ITERATOR;

		/* get the index of the first child */
		int index = queue.indexOf(node.getFirstChild());

		/* if we do not have children, just return an empty enumeration */
		if (index == -1)
			return EMPTY_ITERATOR;

		/* create an enumeration with node's children */
		List<UnifiedTreeNode> result = new ArrayList<>(10);
		while (true) {
			UnifiedTreeNode child = queue.get(index);
			if (isChildrenMarker(child))
				break;
			result.add(child);
			if (index == queue.size() - 1) {
				index = 0;
			} else {
				index++;
			}
		}
		return result.iterator();
	}

	protected int getLevel() {
		return level;
	}

	protected IFileInfo[] getLocalList(UnifiedTreeNode node) {
		try {
			final IFileStore store = node.getStore();
			IFileInfo[] list;
			if (fileTree != null && (fileTree.getTreeRoot().equals(store) || fileTree.getTreeRoot().isParentOf(store)))
				list = fileTree.getChildInfos(store);
			else
				list = store.childInfos(EFS.NONE, null);

			if (list == null || list.length == 0)
				return NO_CHILDREN;
			list = ((Resource) node.getResource()).filterChildren(list, false);
			int size = list.length;
			if (size > 1)
				quickSort(list, 0, size - 1);
			return list;
		} catch (CoreException e) {
			//treat failure to access the directory as a non-existent directory
			return NO_CHILDREN;
		}
	}

	protected Workspace getWorkspace() {
		return (Workspace) root.getWorkspace();
	}

	protected void initializeQueue() {
		//initialize the queue
		if (queue == null)
			queue = new LinkedList<>();
		else
			queue.clear();
		//initialize the free nodes list
		if (freeNodes == null)
			freeNodes = new ArrayList<>(100);
		else
			freeNodes.clear();
		addRootToQueue();
		addElementToQueue(levelMarker);
	}

	protected boolean isChildrenMarker(UnifiedTreeNode node) {
		return node == childrenMarker;
	}

	protected boolean isLevelMarker(UnifiedTreeNode node) {
		return node == levelMarker;
	}

	private static class PatternHolder {
		//Initialize-on-demand Holder class to avoid compiling Pattern if never needed
		//Pattern: A UNIX or Windows relative path that just points backward
		private static final String REGEX = Platform.getOS().equals(Platform.OS_WIN32) ? "\\.[.\\\\]*" : "\\.[./]*"; //$NON-NLS-1$ //$NON-NLS-2$
		public static final Pattern TRIVIAL_SYMLINK_PATTERN = Pattern.compile(REGEX);

		private static final String REGEX_BACK_REPEATING = Platform.getOS().equals(Platform.OS_WIN32) ? "(\\.\\.\\\\)+.*" : "(\\.\\./)+.*"; //$NON-NLS-1$ //$NON-NLS-2$
		public static final Pattern REPEATING_BACKWARDS_PATTERN = Pattern.compile(REGEX_BACK_REPEATING);
	}

	
Initialize history stores for symbolic links.
This may be done when starting a visitor, or later on demand.
/**
	 * Initialize history stores for symbolic links.
	 * This may be done when starting a visitor, or later on demand.
	 */
	protected void initLinkHistoriesIfNeeded() {
		if (pathPrefixHistory == null) {
			//Bug 232426: Check what life cycle we need for the histories
			Job job = Job.getJobManager().currentJob();
			if (job instanceof RefreshJob) {
				//we are running from the RefreshJob: use the path history of the job
				RefreshJob refreshJob = (RefreshJob) job;
				pathPrefixHistory = refreshJob.getPathPrefixHistory();
				rootPathHistory = refreshJob.getRootPathHistory();
			} else {
				//Local Histories
				pathPrefixHistory = new PrefixPool(20);
				rootPathHistory = new PrefixPool(20);
			}
		}
		if (rootPathHistory.size() == 0) {
			//add current root to history
			IFileStore rootStore = ((Resource) root).getStore();
			try {
				java.io.File rootFile = rootStore.toLocalFile(EFS.NONE, null);
				if (rootFile != null) {
					IPath rootProjPath = root.getProject().getLocation();
					if (rootProjPath != null) {
						try {
							java.io.File rootProjFile = new java.io.File(rootProjPath.toOSString());
							rootPathHistory.insertShorter(rootProjFile.getCanonicalPath() + '/');
						} catch (IOException ioe) {
							/*ignore here*/
						}
					}
					rootPathHistory.insertShorter(rootFile.getCanonicalPath() + '/');
				}
			} catch (CoreException | IOException e) {
				/*ignore*/
			}
		}
	}

	
Check if the given child represents a recursive symbolic link.

On remote EFS stores, this check is not exhaustive and just
finds trivial recursive symbolic links pointing up in the tree.
 On local stores, where File.getCanonicalPath() is available, the test is exhaustive but may also find some false positives with transitive symbolic links. This may lead to suppressing duplicates of already known resources in the tree, but it will never lead to not finding a resource at all. See bug 105554 for details. 
Params:
parentStore – EFS IFileStore representing the parent folder
localInfo – child representing a symbolic link
Returns:
true if the given child represents a
    recursive symbolic link./**
	 * Check if the given child represents a recursive symbolic link.
	 * <p>
	 * On remote EFS stores, this check is not exhaustive and just
	 * finds trivial recursive symbolic links pointing up in the tree.
	 * </p><p>
	 * On local stores, where {@link java.io.File#getCanonicalPath()}
	 * is available, the test is exhaustive but may also find some
	 * false positives with transitive symbolic links. This may lead
	 * to suppressing duplicates of already known resources in the
	 * tree, but it will never lead to not finding a resource at
	 * all. See bug 105554 for details.
	 * </p>
	 * @param parentStore EFS IFileStore representing the parent folder
	 * @param localInfo child representing a symbolic link
	 * @return <code>true</code> if the given child represents a
	 *     recursive symbolic link.
	 */
	private boolean isRecursiveLink(IFileStore parentStore, IFileInfo localInfo) {
		//Try trivial pattern first - works also on remote EFS stores
		String linkTarget = localInfo.getStringAttribute(EFS.ATTRIBUTE_LINK_TARGET);
		if (linkTarget != null && PatternHolder.TRIVIAL_SYMLINK_PATTERN.matcher(linkTarget).matches()) {
			return true;
		}
		//Need canonical paths to check all other possibilities
		try {
			java.io.File parentFile = parentStore.toLocalFile(EFS.NONE, null);
			//If this store cannot be represented as a local file, there is nothing we can do
			//In the future, we could try to resolve the link target
			//against the remote file system to do more checks.
			if (parentFile == null) {
				return false;
			}

			Path parent = parentFile.toPath();
			Path realParentPath = parent.toRealPath();
			if (disable_advanced_recursive_link_checks) {
				// Multiple ../ backwards links can go outside the project tree
				if (linkTarget != null && PatternHolder.REPEATING_BACKWARDS_PATTERN.matcher(linkTarget).matches()) {
					Path targetPath = parent.resolve(linkTarget).normalize();

					// Recursive if literal target points to the literal parent of this tree
					if (parent.normalize().startsWith(targetPath)) {
						return true;
					}

					// Recursive if resolved target points to the resolved parent of this tree
					Path realTargetPath = targetPath.toRealPath();
					if (realParentPath.startsWith(realTargetPath)) {
						return true;
					}

					// If link is outside the project tree, consider as non recursive
					// The link still can create recursion in the tree, but we can't detect it here.
				}
				// Skip advanced link checking, it may hide valid directories, see bug 537449
				return false;
			}
			//get canonical path for both child and parent
			java.io.File childFile = new java.io.File(parentFile, localInfo.getName());
			String parentPath = realParentPath.toString() + java.io.File.separatorChar;
			String childPath = childFile.toPath().toRealPath().toString() + java.io.File.separatorChar;
			//get or instantiate the prefix and root path histories.
			//Might be done earlier - for now, do it on demand.
			initLinkHistoriesIfNeeded();
			//insert the parent for checking loops
			pathPrefixHistory.insertLonger(parentPath);
			if (pathPrefixHistory.containsAsPrefix(childPath)) {
				//found a potential loop: is it spanning up a new tree?
				if (!rootPathHistory.insertShorter(childPath)) {
					//not spanning up a new tree, so it is a real loop.
					return true;
				}
			} else if (rootPathHistory.hasPrefixOf(childPath)) {
				//child points into a different portion of the tree that we visited already before, or will certainly visit.
				//This does not introduce a loop yet, but introduces duplicate resources.
				//TODO Ideally, such duplicates should be modelled as linked resources. See bug 105534
				return false;
			} else {
				//child neither introduces a loop nor points to a known tree.
				//It probably spans up a new tree of potential prefixes.
				rootPathHistory.insertShorter(childPath);
			}
		} catch (IOException | CoreException e) {
			//ignore
		}
		return false;
	}

	protected boolean isValidLevel(int currentLevel, int depth) {
		switch (depth) {
			case IResource.DEPTH_INFINITE :
				return true;
			case IResource.DEPTH_ONE :
				return currentLevel <= 1;
			case IResource.DEPTH_ZERO :
				return currentLevel == 0;
			default :
				return currentLevel + 1000 <= depth;
		}
	}

	
Sorts the given array of strings in place.  This is
not using the sorting framework to avoid casting overhead.
/**
	 * Sorts the given array of strings in place.  This is
	 * not using the sorting framework to avoid casting overhead.
	 */
	protected void quickSort(IFileInfo[] infos, int left, int right) {
		int originalLeft = left;
		int originalRight = right;
		IFileInfo mid = infos[(left + right) / 2];
		do {
			while (mid.compareTo(infos[left]) > 0)
				left++;
			while (infos[right].compareTo(mid) > 0)
				right--;
			if (left <= right) {
				IFileInfo tmp = infos[left];
				infos[left] = infos[right];
				infos[right] = tmp;
				left++;
				right--;
			}
		} while (left <= right);
		if (originalLeft < right)
			quickSort(infos, originalLeft, right);
		if (left < originalRight)
			quickSort(infos, left, originalRight);
		return;
	}

	
Remove from the last element of the queue to the first child of the
given node.
/**
	 * Remove from the last element of the queue to the first child of the
	 * given node.
	 */
	protected void removeNodeChildrenFromQueue(UnifiedTreeNode node) {
		UnifiedTreeNode first = node.getFirstChild();
		if (first == null)
			return;
		while (true) {
			if (first.equals(queue.pollLast()))
				break;
		}
		node.setFirstChild(null);
	}

	
Increases the current tree level by one. Returns true if the new
level is still valid for the given depth
/**
	 * Increases the current tree level by one. Returns true if the new
	 * level is still valid for the given depth
	 */
	protected boolean setLevel(int newLevel, int depth) {
		level = newLevel;
		childLevelValid = isValidLevel(level + 1, depth);
		return isValidLevel(level, depth);
	}

	private void setRoot(IResource root) {
		this.root = root;
	}
}