UnifiedTree


1   /*******************************************************************************
2    * Copyright (c) 2000, 2007 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    * 
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   * Martin Oberhuber (Wind River) - [105554] handle cyclic symbolic links
11   *******************************************************************************/
12  package org.eclipse.core.internal.localstore;
13  
14  import java.io.IOException  ;
15  import java.util.*;
16  import java.util.regex.Pattern  ;
17  import org.eclipse.core.filesystem.*;
18  import org.eclipse.core.internal.resources.*;
19  import org.eclipse.core.internal.utils.Queue;
20  import org.eclipse.core.resources.IContainer;
21  import org.eclipse.core.resources.IResource;
22  import org.eclipse.core.runtime.*;
23  
24  /**
25   * Represents the workspace's tree merged with the file system's tree.
26   */
27  public class UnifiedTree {
28      /** special node to mark the separation of a node's children */
29      protected static final UnifiedTreeNode childrenMarker = new UnifiedTreeNode(null, null, null, null, false);
30  
31      private static final Iterator EMPTY_ITERATOR = Collections.EMPTY_LIST.iterator();
32  
33      /** special node to mark the beginning of a level in the tree */
34      protected static final UnifiedTreeNode levelMarker = new UnifiedTreeNode(null, null, null, null, false);
35  
36      private static final IFileInfo[] NO_CHILDREN = new IFileInfo[0];
37  
38      /** Singleton to indicate no local children */
39      private static final IResource[] NO_RESOURCES = new IResource[0];
40  
41      /**
42       * True if the level of the children of the current node are valid according
43       * to the requested refresh depth, false otherwise
44       */
45      protected boolean childLevelValid = false;
46  
47      /** an IFileTree which can be used to build a unified tree*/
48      protected IFileTree fileTree = null;
49  
50      /** Spare node objects available for reuse */
51      protected ArrayList freeNodes = new ArrayList();
52      /** tree's actual level */
53      protected int level;
54      /** our queue */
55      protected Queue queue;
56      
57      /** path prefixes for checking symbolic link cycles */
58      protected PrefixPool pathPrefixHistory, rootPathHistory;
59  
60      /** tree's root */
61      protected IResource root;
62  
63      /**
64       * The root must only be a file or a folder.
65       */
66      public UnifiedTree(IResource root) {
67          setRoot(root);
68      }
69  
70      /**
71       * Pass in a a root for the tree, a file tree containing all of the entries for this 
72       * tree and a flag indicating whether the UnifiedTree should consult the fileTree where
73       * possible for entries
74       * @param root
75       * @param fileTree
76       */
77      public UnifiedTree(IResource root, IFileTree fileTree) {
78          this(root);
79          this.fileTree = fileTree;
80      }
81  
82      public void accept(IUnifiedTreeVisitor visitor) throws CoreException {
83          accept(visitor, IResource.DEPTH_INFINITE);
84      }
85  
86      public void accept(IUnifiedTreeVisitor visitor, int depth) throws CoreException {
87          Assert.isNotNull(root);
88          initializeQueue();
89          setLevel(0, depth);
90          while (!queue.isEmpty()) {
91              UnifiedTreeNode node = (UnifiedTreeNode) queue.remove();
92              if (isChildrenMarker(node))
93                  continue;
94              if (isLevelMarker(node)) {
95                  if (!setLevel(getLevel() + 1, depth))
96                      break;
97                  continue;
98              }
99              if (visitor.visit(node))
100                 addNodeChildrenToQueue(node);
101             else
102                 removeNodeChildrenFromQueue(node);
103             //allow reuse of the node
104             freeNodes.add(node);
105         }
106     }
107 
108     protected void addChildren(UnifiedTreeNode node) {
109         Resource parent = (Resource) node.getResource();
110 
111         // is there a possibility to have children? 
112         int parentType = parent.getType();
113         if (parentType == IResource.FILE && !node.isFolder())
114             return;
115 
116         //don't refresh resources in closed or non-existent projects
117         if (!parent.getProject().isAccessible())
118             return;
119 
120         // get the list of resources in the file system 
121         // don't ask for local children if we know it doesn't exist locally
122         IFileInfo[] list = node.existsInFileSystem() ? getLocalList(node) : NO_CHILDREN;
123         int localIndex = 0;
124 
125         // See if the children of this resource have been computed before 
126         ResourceInfo resourceInfo = parent.getResourceInfo(false, false);
127         int flags = parent.getFlags(resourceInfo);
128         boolean unknown = ResourceInfo.isSet(flags, ICoreConstants.M_CHILDREN_UNKNOWN);
129 
130         // get the list of resources in the workspace 
131         if (!unknown && (parentType == IResource.FOLDER || parentType == IResource.PROJECT) && parent.exists(flags, true)) {
132             IResource target = null;
133             UnifiedTreeNode child = null;
134             IResource[] members;
135             try {
136                 members = ((IContainer) parent).members(IContainer.INCLUDE_TEAM_PRIVATE_MEMBERS);
137             } catch (CoreException e) {
138                 members = NO_RESOURCES;
139             }
140             int workspaceIndex = 0;
141             //iterate simultaneously over file system and workspace members
142             while (workspaceIndex < members.length) {
143                 target = members[workspaceIndex];
144                 String   name = target.getName();
145                 IFileInfo localInfo = localIndex < list.length ? list[localIndex] : null;
146                 int comp = localInfo != null ? name.compareTo(localInfo.getName()) : -1;
147                 //special handling for linked resources
148                 if (target.isLinked()) {
149                     //child will be null if location is undefined
150                     child = createChildForLinkedResource(target);
151                     workspaceIndex++;
152                     //if there is a matching local file, skip it - it will be blocked by the linked resource
153                     if (comp == 0)
154                         localIndex++;
155                 } else if (comp == 0) {
156                     // resource exists in workspace and file system --> localInfo is non-null
157                     //create workspace-only node for symbolic link that creates a cycle
158                     if (localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) && localInfo.isDirectory() && isRecursiveLink(node.getStore(), localInfo))
159                         child = createNode(target, null, null, true);
160                     else
161                         child = createNode(target, null, localInfo, true);
162                     localIndex++;
163                     workspaceIndex++;
164                 } else if (comp > 0) {
165                     // resource exists only in file system
166                     //don't create a node for symbolic links that create a cycle
167                     if (!localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) || !localInfo.isDirectory() || !isRecursiveLink(node.getStore(), localInfo))
168                         child = createChildNodeFromFileSystem(node, localInfo);
169                     localIndex++;
170                 } else {
171                     // resource exists only in the workspace
172                     child = createNode(target, null, null, true);
173                     workspaceIndex++;
174                 }
175                 if (child != null)
176                     addChildToTree(node, child);
177             }
178         }
179 
180         /* process any remaining resource from the file system */
181         addChildrenFromFileSystem(node, list, localIndex);
182 
183         /* Mark the children as now known */
184         if (unknown) {
185             // Don't open the info - we might not be inside a workspace-modifying operation
186             resourceInfo = parent.getResourceInfo(false, false);
187             if (resourceInfo != null)
188                 resourceInfo.clear(ICoreConstants.M_CHILDREN_UNKNOWN);
189         }
190 
191         /* if we added children, add the childMarker separator */
192         if (node.getFirstChild() != null)
193             addChildrenMarker();
194     }
195 
196     protected void addChildrenFromFileSystem(UnifiedTreeNode node, IFileInfo[] childInfos, int index) {
197         if (childInfos == null)
198             return;
199         for (int i = index; i < childInfos.length; i++) {
200             IFileInfo info = childInfos[i];
201             //don't create a node for symbolic links that create a cycle
202             if (!info.getAttribute(EFS.ATTRIBUTE_SYMLINK) || !info.isDirectory() || !isRecursiveLink(node.getStore(), info))
203                 addChildToTree(node, createChildNodeFromFileSystem(node, info));
204         }
205     }
206 
207     protected void addChildrenMarker() {
208         addElementToQueue(childrenMarker);
209     }
210 
211     protected void addChildToTree(UnifiedTreeNode node, UnifiedTreeNode child) {
212         if (node.getFirstChild() == null)
213             node.setFirstChild(child);
214         addElementToQueue(child);
215     }
216 
217     protected void addElementToQueue(UnifiedTreeNode target) {
218         queue.add(target);
219     }
220 
221     protected void addNodeChildrenToQueue(UnifiedTreeNode node) {
222         /* if the first child is not null we already added the children */
223         /* If the children won't be at a valid level for the refresh depth, don't bother adding them */
224         if (!childLevelValid || node.getFirstChild() != null)
225             return;
226         addChildren(node);
227         if (queue.isEmpty())
228             return;
229         //if we're about to change levels, then the children just added
230         //are the last nodes for their level, so add a level marker to the queue
231         UnifiedTreeNode nextNode = (UnifiedTreeNode) queue.peek();
232         if (isChildrenMarker(nextNode))
233             queue.remove();
234         nextNode = (UnifiedTreeNode) queue.peek();
235         if (isLevelMarker(nextNode))
236             addElementToQueue(levelMarker);
237     }
238 
239     protected void addRootToQueue() {
240         //don't refresh in closed projects
241         if (!root.getProject().isAccessible())
242             return;
243         IFileStore store = ((Resource) root).getStore();
244         IFileInfo fileInfo = fileTree != null ? fileTree.getFileInfo(store) : store.fetchInfo();
245         UnifiedTreeNode node = createNode(root, store, fileInfo, root.exists());
246         if (node.existsInFileSystem() || node.existsInWorkspace())
247             addElementToQueue(node);
248     }
249 
250     /**
251      * Creates a tree node for a resource that is linked in a different file system location.
252      */
253     protected UnifiedTreeNode createChildForLinkedResource(IResource target) {
254         IFileStore store = ((Resource) target).getStore();
255         return createNode(target, store, store.fetchInfo(), true);
256     }
257 
258     /**
259      * 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. 
260      */
261     protected UnifiedTreeNode createChildNodeFromFileSystem(UnifiedTreeNode parent, IFileInfo info) {
262         IPath childPath = parent.getResource().getFullPath().append(info.getName());
263         int type = info.isDirectory() ? IResource.FOLDER : IResource.FILE;
264         IResource target = getWorkspace().newResource(childPath, type);
265         return createNode(target, null, info, false);
266     }
267 
268     /**
269      * Factory method for creating a node for this tree.  If the file exists on
270      * disk, either the parent store or child store can be provided. Providing
271      * only the parent store avoids creation of the child store in cases where
272      * it is not needed. The store object is only needed for directories for
273      * simple file system traversals, so this avoids creating store objects
274      * for all files.
275      */
276     protected UnifiedTreeNode createNode(IResource resource, IFileStore store, IFileInfo info, boolean existsWorkspace) {
277         //first check for reusable objects
278         UnifiedTreeNode node = null;
279         int size = freeNodes.size();
280         if (size > 0) {
281             node = (UnifiedTreeNode) freeNodes.remove(size - 1);
282             node.reuse(this, resource, store, info, existsWorkspace);
283             return node;
284         }
285         //none available, so create a new one
286         return new UnifiedTreeNode(this, resource, store, info, existsWorkspace);
287     }
288 
289     protected Iterator getChildren(UnifiedTreeNode node) {
290         /* if first child is null we need to add node's children to queue */
291         if (node.getFirstChild() == null)
292             addNodeChildrenToQueue(node);
293 
294         /* if the first child is still null, the node does not have any children */
295         if (node.getFirstChild() == null)
296             return EMPTY_ITERATOR;
297 
298         /* get the index of the first child */
299         int index = queue.indexOf(node.getFirstChild());
300 
301         /* if we do not have children, just return an empty enumeration */
302         if (index == -1)
303             return EMPTY_ITERATOR;
304 
305         /* create an enumeration with node's children */
306         List result = new ArrayList(10);
307         while (true) {
308             UnifiedTreeNode child = (UnifiedTreeNode) queue.elementAt(index);
309             if (isChildrenMarker(child))
310                 break;
311             result.add(child);
312             index = queue.increment(index);
313         }
314         return result.iterator();
315     }
316 
317     protected int getLevel() {
318         return level;
319     }
320 
321     protected IFileInfo[] getLocalList(UnifiedTreeNode node) {
322         try {
323             final IFileStore store = node.getStore();
324             IFileInfo[] list = fileTree != null ? fileTree.getChildInfos(store) : store.childInfos(EFS.NONE, null);
325             if (list == null)
326                 return NO_CHILDREN;
327             int size = list.length;
328             if (size > 1)
329                 quickSort(list, 0, size - 1);
330             return list;
331         } catch (CoreException e) {
332             //treat failure to access the directory as a non-existent directory
333             return NO_CHILDREN;
334         }
335     }
336 
337     protected Workspace getWorkspace() {
338         return (Workspace) root.getWorkspace();
339     }
340 
341     protected void initializeQueue() {
342         //initialize the queue
343         if (queue == null)
344             queue = new Queue(100, false);
345         else
346             queue.reset();
347         //initialize the free nodes list
348         if (freeNodes == null)
349             freeNodes = new ArrayList(100);
350         else
351             freeNodes.clear();
352         //clear any known path prefixes for recursive symbolic link checking
353         if (pathPrefixHistory != null) {
354             pathPrefixHistory.clear();
355             rootPathHistory.clear();
356         }
357         addRootToQueue();
358         addElementToQueue(levelMarker);
359     }
360 
361     protected boolean isChildrenMarker(UnifiedTreeNode node) {
362         return node == childrenMarker;
363     }
364 
365     protected boolean isLevelMarker(UnifiedTreeNode node) {
366         return node == levelMarker;
367     }
368 
369     private static class PatternHolder {
370         //Initialize-on-demand Holder class to avoid compiling Pattern if never needed
371         //Pattern: A UNIX relative path that just points backward 
372         public static Pattern   trivialSymlinkPattern = Pattern.compile("\\.[./]*"); //$NON-NLS-1$
373     }
374 
375     /**
376      * Initialize history stores for symbolic links.
377      * This may be done when starting a visitor, or later on demand.
378      */
379     protected void initLinkHistoriesIfNeeded() {
380         if (pathPrefixHistory==null) {
381             pathPrefixHistory = new PrefixPool(20);
382             rootPathHistory = new PrefixPool(20);
383         }
384         if (rootPathHistory.size()==0) {
385             //add current root to history
386             IFileStore rootStore = ((Resource) root).getStore();
387             try {
388                 java.io.File   rootFile = rootStore.toLocalFile(EFS.NONE, null);
389                 if (rootFile!=null) {
390                     IPath rootProjPath = root.getProject().getLocation();
391                     if (rootProjPath!=null) {
392                         try {
393                             java.io.File   rootProjFile = new java.io.File  (rootProjPath.toOSString());
394                             rootPathHistory.insertShorter(rootProjFile.getCanonicalPath()+'/');
395                         } catch(IOException   ioe) {
396                             /*ignore here*/
397                         }
398                     }
399                     rootPathHistory.insertShorter(rootFile.getCanonicalPath()+'/');
400                 }
401             } catch(CoreException e) {
402                 /*ignore*/
403             } catch(IOException   e) {
404                 /*ignore*/
405             }
406         }
407     }
408     
409     /**
410      * Check if the given child represents a recursive symbolic link.
411      * <p>
412      * On remote EFS stores, this check is not exhaustive and just
413      * finds trivial recursive symbolic links pointing up in the tree.
414      * </p><p>
415      * On local stores, where {@link java.io.File#getCanonicalPath()}
416      * is available, the test is exhaustive but may also find some
417      * false positives with transitive symbolic links. This may lead
418      * to suppressing duplicates of already known resources in the
419      * tree, but it will never lead to not finding a resource at
420      * all. See bug 105554 for details.
421      * </p>
422      * @param parentStore EFS IFileStore representing the parent folder
423      * @param localInfo child representing a symbolic link
424      * @return <code>true</code> if the given child represents a
425      *     recursive symbolic link.
426      */
427     private boolean isRecursiveLink(IFileStore parentStore, IFileInfo localInfo) {
428         //Try trivial pattern first - works also on remote EFS stores
429         String   linkTarget = localInfo.getStringAttribute(EFS.ATTRIBUTE_LINK_TARGET);
430         if (linkTarget!=null && PatternHolder.trivialSymlinkPattern.matcher(linkTarget).matches()) {
431             return true;
432         }
433         //Need canonical paths to check all other possibilities
434         try {
435             java.io.File   parentFile = parentStore.toLocalFile(EFS.NONE, null);
436             //If this store cannot be represented as a local file, there is nothing we can do
437             //In the future, we could try to resolve the link target
438             //against the remote file system to do more checks.
439             if (parentFile == null)
440                 return false;
441             //get canonical path for both child and parent
442             java.io.File   childFile = new java.io.File  (parentFile, localInfo.getName());
443             String   parentPath = parentFile.getCanonicalPath()+'/';
444             String   childPath = childFile.getCanonicalPath()+'/';
445             //get or instantiate the prefix and root path histories.
446             //Might be done earlier - for now, do it on demand.
447             initLinkHistoriesIfNeeded();
448             //insert the parent for checking loops
449             pathPrefixHistory.insertLonger(parentPath);
450             if (pathPrefixHistory.containsAsPrefix(childPath)) {
451                 //found a potential loop: is it spanning up a new tree?
452                 if (!rootPathHistory.insertShorter(childPath)) {
453                     //not spanning up a new tree, so it is a real loop.
454                     return true;
455                 }
456             } else if (rootPathHistory.hasPrefixOf(childPath)) {
457                 //child points into a different portion of the tree that we visited already before, or will certainly visit.
458                 //This does not introduce a loop yet, but introduces duplicate resources.
459                 //TODO Ideally, such duplicates should be modelled as linked resources. See bug 105534
460                 return false;
461             } else {
462                 //child neither introduces a loop nor points to a known tree.
463                 //It probably spans up a new tree of potential prefixes.
464                 rootPathHistory.insertShorter(childPath);
465             }
466         } catch (IOException   e) {
467             //ignore
468         } catch (CoreException e) {
469             //ignore
470         }
471         return false;
472     }
473 
474     protected boolean isValidLevel(int currentLevel, int depth) {
475         switch (depth) {
476             case IResource.DEPTH_INFINITE :
477                 return true;
478             case IResource.DEPTH_ONE :
479                 return currentLevel <= 1;
480             case IResource.DEPTH_ZERO :
481                 return currentLevel == 0;
482             default :
483                 return currentLevel + 1000 <= depth;
484         }
485     }
486 
487     /**
488      * Sorts the given array of strings in place.  This is
489      * not using the sorting framework to avoid casting overhead.
490      */
491     protected void quickSort(IFileInfo[] infos, int left, int right) {
492         int originalLeft = left;
493         int originalRight = right;
494         IFileInfo mid = infos[(left + right) / 2];
495         do {
496             while (mid.compareTo(infos[left]) > 0)
497                 left++;
498             while (infos[right].compareTo(mid) > 0)
499                 right--;
500             if (left <= right) {
501                 IFileInfo tmp = infos[left];
502                 infos[left] = infos[right];
503                 infos[right] = tmp;
504                 left++;
505                 right--;
506             }
507         } while (left <= right);
508         if (originalLeft < right)
509             quickSort(infos, originalLeft, right);
510         if (left < originalRight)
511             quickSort(infos, left, originalRight);
512         return;
513     }
514 
515     /**
516      * Remove from the last element of the queue to the first child of the
517      * given node.
518      */
519     protected void removeNodeChildrenFromQueue(UnifiedTreeNode node) {
520         UnifiedTreeNode first = node.getFirstChild();
521         if (first == null)
522             return;
523         while (true) {
524             if (first.equals(queue.removeTail()))
525                 break;
526         }
527         node.setFirstChild(null);
528     }
529 
530     /**
531      * Increases the current tree level by one. Returns true if the new
532      * level is still valid for the given depth
533      */
534     protected boolean setLevel(int newLevel, int depth) {
535         level = newLevel;
536         childLevelValid = isValidLevel(level + 1, depth);
537         return isValidLevel(level, depth);
538     }
539 
540     private void setRoot(IResource root) {
541         this.root = root;
542     }
543 }
544
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags