contribute library roots without creating Library/OrderEntry instances to avoid ...
[idea/community.git] / platform / projectModel-impl / src / com / intellij / openapi / roots / impl / RootIndex.java
1 /*
2  * Copyright 2000-2014 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.openapi.roots.impl;
17
18 import com.intellij.openapi.diagnostic.Logger;
19 import com.intellij.openapi.extensions.Extensions;
20 import com.intellij.openapi.fileTypes.FileTypeRegistry;
21 import com.intellij.openapi.module.Module;
22 import com.intellij.openapi.module.ModuleManager;
23 import com.intellij.openapi.project.Project;
24 import com.intellij.openapi.roots.*;
25 import com.intellij.openapi.roots.impl.libraries.LibraryEx;
26 import com.intellij.openapi.roots.libraries.Library;
27 import com.intellij.openapi.util.Pair;
28 import com.intellij.openapi.util.text.StringUtil;
29 import com.intellij.openapi.vfs.VfsUtilCore;
30 import com.intellij.openapi.vfs.VirtualFile;
31 import com.intellij.openapi.vfs.newvfs.events.VFileEvent;
32 import com.intellij.util.CollectionQuery;
33 import com.intellij.util.Query;
34 import com.intellij.util.containers.ContainerUtil;
35 import com.intellij.util.containers.MultiMap;
36 import com.intellij.util.containers.SLRUMap;
37 import gnu.trove.TObjectIntHashMap;
38 import org.jetbrains.annotations.NotNull;
39 import org.jetbrains.annotations.Nullable;
40 import org.jetbrains.jps.model.module.JpsModuleSourceRootType;
41
42 import java.util.*;
43
44 public class RootIndex {
45   public static final Comparator<OrderEntry> BY_OWNER_MODULE = (o1, o2) -> {
46     String name1 = o1.getOwnerModule().getName();
47     String name2 = o2.getOwnerModule().getName();
48     return name1.compareTo(name2);
49   };
50
51   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.roots.impl.RootIndex");
52   private static final FileTypeRegistry ourFileTypes = FileTypeRegistry.getInstance();
53
54   private final Map<VirtualFile, String> myPackagePrefixByRoot = ContainerUtil.newHashMap();
55
56   private final InfoCache myInfoCache;
57   private final List<JpsModuleSourceRootType<?>> myRootTypes = ContainerUtil.newArrayList();
58   private final TObjectIntHashMap<JpsModuleSourceRootType<?>> myRootTypeId = new TObjectIntHashMap<JpsModuleSourceRootType<?>>();
59   @NotNull private final Project myProject;
60   private final PackageDirectoryCache myPackageDirectoryCache;
61   private OrderEntryGraph myOrderEntryGraph;
62
63   // made public for Upsource
64   public RootIndex(@NotNull Project project, @NotNull InfoCache cache) {
65     myProject = project;
66     myInfoCache = cache;
67     final RootInfo info = buildRootInfo(project);
68
69     MultiMap<String, VirtualFile> rootsByPackagePrefix = MultiMap.create();
70     Set<VirtualFile> allRoots = info.getAllRoots();
71     for (VirtualFile root : allRoots) {
72       List<VirtualFile> hierarchy = getHierarchy(root, allRoots, info);
73       Pair<DirectoryInfo, String> pair = hierarchy != null
74                                          ? calcDirectoryInfo(root, hierarchy, info)
75                                          : new Pair<DirectoryInfo, String>(NonProjectDirectoryInfo.IGNORED, null);
76       cacheInfos(root, root, pair.first);
77       rootsByPackagePrefix.putValue(pair.second, root);
78       myPackagePrefixByRoot.put(root, pair.second);
79     }
80     myPackageDirectoryCache = new PackageDirectoryCache(rootsByPackagePrefix) {
81       @Override
82       protected boolean isPackageDirectory(@NotNull VirtualFile dir, @NotNull String packageName) {
83         return getInfoForFile(dir).isInProject() && packageName.equals(getPackageName(dir));
84       }
85     };
86   }
87
88   @NotNull
89   private RootInfo buildRootInfo(@NotNull Project project) {
90     final RootInfo info = new RootInfo();
91     for (final Module module : ModuleManager.getInstance(project).getModules()) {
92       final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
93
94       for (final VirtualFile contentRoot : moduleRootManager.getContentRoots()) {
95         if (!info.contentRootOf.containsKey(contentRoot)) {
96           info.contentRootOf.put(contentRoot, module);
97         }
98       }
99
100       for (ContentEntry contentEntry : moduleRootManager.getContentEntries()) {
101         if (!(contentEntry instanceof ContentEntryImpl) || !((ContentEntryImpl)contentEntry).isDisposed()) {
102           for (VirtualFile excludeRoot : contentEntry.getExcludeFolderFiles()) {
103             info.excludedFromModule.put(excludeRoot, module);
104           }
105         }
106
107         // Init module sources
108         for (final SourceFolder sourceFolder : contentEntry.getSourceFolders()) {
109           final VirtualFile sourceFolderRoot = sourceFolder.getFile();
110           if (sourceFolderRoot != null) {
111             info.rootTypeId.put(sourceFolderRoot, getRootTypeId(sourceFolder.getRootType()));
112             info.classAndSourceRoots.add(sourceFolderRoot);
113             info.sourceRootOf.putValue(sourceFolderRoot, module);
114             info.packagePrefix.put(sourceFolderRoot, sourceFolder.getPackagePrefix());
115           }
116         }
117       }
118
119       for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
120         if (orderEntry instanceof LibraryOrSdkOrderEntry) {
121           final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
122           final VirtualFile[] sourceRoots = entry.getRootFiles(OrderRootType.SOURCES);
123           final VirtualFile[] classRoots = entry.getRootFiles(OrderRootType.CLASSES);
124
125           // Init library sources
126           for (final VirtualFile sourceRoot : sourceRoots) {
127             info.classAndSourceRoots.add(sourceRoot);
128             info.libraryOrSdkSources.add(sourceRoot);
129             info.packagePrefix.put(sourceRoot, "");
130           }
131
132           // init library classes
133           for (final VirtualFile classRoot : classRoots) {
134             info.classAndSourceRoots.add(classRoot);
135             info.libraryOrSdkClasses.add(classRoot);
136             info.packagePrefix.put(classRoot, "");
137           }
138
139           if (orderEntry instanceof LibraryOrderEntry) {
140             Library library = ((LibraryOrderEntry)orderEntry).getLibrary();
141             if (library != null) {
142               for (VirtualFile root : ((LibraryEx)library).getExcludedRoots()) {
143                 info.excludedFromLibraries.putValue(root, library);
144               }
145               for (VirtualFile root : sourceRoots) {
146                 info.sourceOfLibraries.putValue(root, library);
147               }
148               for (VirtualFile root : classRoots) {
149                 info.classOfLibraries.putValue(root, library);
150               }
151             }
152           }
153         }
154       }
155     }
156
157     for (AdditionalLibraryRootsProvider provider : Extensions.getExtensions(AdditionalLibraryRootsProvider.EP_NAME)) {
158       Collection<VirtualFile> roots = provider.getAdditionalProjectLibrarySourceRoots(project);
159       info.libraryOrSdkSources.addAll(roots);
160     }
161     for (DirectoryIndexExcludePolicy policy : Extensions.getExtensions(DirectoryIndexExcludePolicy.EP_NAME, project)) {
162       Collections.addAll(info.excludedFromProject, policy.getExcludeRootsForProject());
163     }
164     return info;
165   }
166
167   @NotNull
168   private synchronized OrderEntryGraph getOrderEntryGraph() {
169     if (myOrderEntryGraph == null) {
170       RootInfo rootInfo = buildRootInfo(myProject);
171       myOrderEntryGraph = new OrderEntryGraph(myProject, rootInfo);
172     }
173     return myOrderEntryGraph;
174   }
175
176   /**
177    * A reverse dependency graph of (library, jdk, module, module source) -> (module).
178    *
179    * <p>Each edge carries with it the associated OrderEntry that caused the dependency.
180    */
181   private static class OrderEntryGraph {
182
183     private static class Edge {
184       Module myKey;
185       ModuleOrderEntry myOrderEntry; // Order entry from myKey -> the node containing the edge
186       boolean myRecursive; // Whether this edge should be descended into during graph walk
187
188       public Edge(Module key, ModuleOrderEntry orderEntry, boolean recursive) {
189         myKey = key;
190         myOrderEntry = orderEntry;
191         myRecursive = recursive;
192       }
193
194       @Override
195       public String toString() {
196         return myOrderEntry.toString();
197       }
198     }
199
200     private static class Node {
201       Module myKey;
202       List<Edge> myEdges = new ArrayList<Edge>();
203
204       @Override
205       public String toString() {
206         return myKey.toString();
207       }
208     }
209
210     private static class Graph {
211       Map<Module, Node> myNodes = new HashMap<Module, Node>();
212     }
213
214     final Project myProject;
215     final RootInfo myRootInfo;
216     final Set<VirtualFile> myAllRoots;
217     Graph myGraph;
218     MultiMap<VirtualFile, Node> myRoots; // Map of roots to their root nodes, eg. library jar -> library node
219     final SynchronizedSLRUCache<VirtualFile, List<OrderEntry>> myCache;
220     private MultiMap<VirtualFile, OrderEntry> myLibClassRootEntries;
221     private MultiMap<VirtualFile, OrderEntry> myLibSourceRootEntries;
222
223     public OrderEntryGraph(Project project, RootInfo rootInfo) {
224       myProject = project;
225       myRootInfo = rootInfo;
226       myAllRoots = myRootInfo.getAllRoots();
227       int cacheSize = Math.max(25, (myAllRoots.size() / 100) * 2);
228       myCache = new SynchronizedSLRUCache<VirtualFile, List<OrderEntry>>(cacheSize, cacheSize) {
229         @NotNull
230         @Override
231         public List<OrderEntry> createValue(VirtualFile key) {
232           return collectOrderEntries(key);
233         }
234       };
235       initGraph();
236       initLibraryRoots();
237     }
238
239     private void initGraph() {
240       Graph graph = new Graph();
241
242       MultiMap<VirtualFile, Node> roots = MultiMap.createSmart();
243
244       for (final Module module : ModuleManager.getInstance(myProject).getModules()) {
245         final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
246         List<OrderEnumerationHandler> handlers = OrderEnumeratorBase.getCustomHandlers(module);
247         for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
248           if (orderEntry instanceof ModuleOrderEntry) {
249             ModuleOrderEntry moduleOrderEntry = (ModuleOrderEntry)orderEntry;
250             final Module depModule = moduleOrderEntry.getModule();
251             if (depModule != null) {
252               Node node = graph.myNodes.get(depModule);
253               OrderEnumerator en = OrderEnumerator.orderEntries(depModule).exportedOnly();
254               if (node == null) {
255                 node = new Node();
256                 node.myKey = depModule;
257                 graph.myNodes.put(depModule, node);
258
259                 VirtualFile[] importedClassRoots = en.classes().usingCache().getRoots();
260                 for (VirtualFile importedClassRoot : importedClassRoots) {
261                   roots.putValue(importedClassRoot, node);
262                 }
263
264                 VirtualFile[] importedSourceRoots = en.sources().usingCache().getRoots();
265                 for (VirtualFile sourceRoot : importedSourceRoots) {
266                   roots.putValue(sourceRoot, node);
267                 }
268               }
269               boolean shouldRecurse = en.recursively().shouldRecurse(moduleOrderEntry, handlers);
270               node.myEdges.add(new Edge(module, moduleOrderEntry, shouldRecurse));
271             }
272           }
273         }
274       }
275
276       myGraph = graph;
277       myRoots = roots;
278     }
279
280     private void initLibraryRoots() {
281       MultiMap<VirtualFile, OrderEntry> libClassRootEntries = MultiMap.createSmart();
282       MultiMap<VirtualFile, OrderEntry> libSourceRootEntries = MultiMap.createSmart();
283
284       for (final Module module : ModuleManager.getInstance(myProject).getModules()) {
285         final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
286         for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
287           if (orderEntry instanceof LibraryOrSdkOrderEntry) {
288             final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
289             for (final VirtualFile sourceRoot : entry.getRootFiles(OrderRootType.SOURCES)) {
290               libSourceRootEntries.putValue(sourceRoot, orderEntry);
291             }
292             for (final VirtualFile classRoot : entry.getRootFiles(OrderRootType.CLASSES)) {
293               libClassRootEntries.putValue(classRoot, orderEntry);
294             }
295           }
296         }
297       }
298
299       myLibClassRootEntries = libClassRootEntries;
300       myLibSourceRootEntries = libSourceRootEntries;
301     }
302
303     private List<OrderEntry> getOrderEntries(@NotNull VirtualFile file) {
304       return myCache.get(file);
305     }
306
307     /**
308      * Traverses the graph from the given file, collecting all encountered order entries.
309      */
310     private List<OrderEntry> collectOrderEntries(@NotNull VirtualFile file) {
311       List<VirtualFile> roots = getHierarchy(file, myAllRoots, myRootInfo);
312       if (roots == null) {
313         return Collections.emptyList();
314       }
315       List<OrderEntry> result = new ArrayList<OrderEntry>();
316       Stack<Node> stack = new Stack<Node>();
317       for (VirtualFile root : roots) {
318         Collection<Node> nodes = myRoots.get(root);
319         for (Node node : nodes) {
320           stack.push(node);
321         }
322       }
323
324       Set<Node> seen = new HashSet<Node>();
325       while (!stack.isEmpty()) {
326         Node node = stack.pop();
327         if (seen.contains(node)) {
328           continue;
329         }
330         seen.add(node);
331
332         for (Edge edge : node.myEdges) {
333           result.add(edge.myOrderEntry);
334
335           if (edge.myRecursive) {
336             Node targetNode = myGraph.myNodes.get(edge.myKey);
337             if (targetNode != null) {
338               stack.push(targetNode);
339             }
340           }
341         }
342       }
343
344       @Nullable VirtualFile libraryClassRoot = myRootInfo.findLibraryRootInfo(roots, false);
345       @Nullable VirtualFile librarySourceRoot = myRootInfo.findLibraryRootInfo(roots, true);
346       result.addAll(myRootInfo.getLibraryOrderEntries(roots, libraryClassRoot, librarySourceRoot, myLibClassRootEntries, myLibSourceRootEntries));
347
348       VirtualFile moduleContentRoot = myRootInfo.findModuleRootInfo(roots);
349       if (moduleContentRoot != null) {
350         ContainerUtil.addIfNotNull(result, myRootInfo.getModuleSourceEntry(roots, moduleContentRoot, myLibClassRootEntries));
351       }
352       Collections.sort(result, BY_OWNER_MODULE);
353       return result;
354     }
355   }
356
357   private int getRootTypeId(@NotNull JpsModuleSourceRootType<?> rootType) {
358     if (myRootTypeId.containsKey(rootType)) {
359       return myRootTypeId.get(rootType);
360     }
361
362     int id = myRootTypes.size();
363     if (id > DirectoryInfoImpl.MAX_ROOT_TYPE_ID) {
364       LOG.error("Too many different types of module source roots (" + id + ") registered: " + myRootTypes);
365     }
366     myRootTypes.add(rootType);
367     myRootTypeId.put(rootType, id);
368     return id;
369   }
370
371   @NotNull
372   public DirectoryInfo getInfoForFile(@NotNull VirtualFile file) {
373     if (!file.isValid()) {
374       return NonProjectDirectoryInfo.INVALID;
375     }
376     VirtualFile dir;
377     if (!file.isDirectory()) {
378       DirectoryInfo info = myInfoCache.getCachedInfo(file);
379       if (info != null) {
380         return info;
381       }
382       if (ourFileTypes.isFileIgnored(file)) {
383         return NonProjectDirectoryInfo.IGNORED;
384       }
385       dir = file.getParent();
386     }
387     else {
388       dir = file;
389     }
390
391     int count = 0;
392     for (VirtualFile root = dir; root != null; root = root.getParent()) {
393       if (++count > 1000) {
394         throw new IllegalStateException("Possible loop in tree, started at " + dir.getName());
395       }
396       DirectoryInfo info = myInfoCache.getCachedInfo(root);
397       if (info != null) {
398         if (!dir.equals(root)) {
399           cacheInfos(dir, root, info);
400         }
401         return info;
402       }
403
404       if (ourFileTypes.isFileIgnored(root)) {
405         return cacheInfos(dir, root, NonProjectDirectoryInfo.IGNORED);
406       }
407     }
408
409     return cacheInfos(dir, null, NonProjectDirectoryInfo.NOT_UNDER_PROJECT_ROOTS);
410   }
411
412   @NotNull
413   private DirectoryInfo cacheInfos(VirtualFile dir, @Nullable VirtualFile stopAt, @NotNull DirectoryInfo info) {
414     while (dir != null) {
415       myInfoCache.cacheInfo(dir, info);
416       if (dir.equals(stopAt)) {
417         break;
418       }
419       dir = dir.getParent();
420     }
421     return info;
422   }
423
424   @NotNull
425   public Query<VirtualFile> getDirectoriesByPackageName(@NotNull final String packageName, final boolean includeLibrarySources) {
426     // Note that this method is used in upsource as well, hence, don't reduce this method's visibility.
427     List<VirtualFile> result = myPackageDirectoryCache.getDirectoriesByPackageName(packageName);
428     if (!includeLibrarySources) {
429       result = ContainerUtil.filter(result, file -> {
430         DirectoryInfo info = getInfoForFile(file);
431         return info.isInProject() && (!info.isInLibrarySource() || info.isInModuleSource() || info.hasLibraryClassRoot());
432       });
433     }
434     return new CollectionQuery<VirtualFile>(result);
435   }
436
437   @Nullable
438   public String getPackageName(@NotNull final VirtualFile dir) {
439     if (dir.isDirectory()) {
440       if (ourFileTypes.isFileIgnored(dir)) {
441         return null;
442       }
443
444       if (myPackagePrefixByRoot.containsKey(dir)) {
445         return myPackagePrefixByRoot.get(dir);
446       }
447
448       final VirtualFile parent = dir.getParent();
449       if (parent != null) {
450         return getPackageNameForSubdir(getPackageName(parent), dir.getName());
451       }
452     }
453
454     return null;
455   }
456
457   @Nullable
458   protected static String getPackageNameForSubdir(@Nullable String parentPackageName, @NotNull String subdirName) {
459     if (parentPackageName == null) return null;
460     return parentPackageName.isEmpty() ? subdirName : parentPackageName + "." + subdirName;
461   }
462
463   @Nullable
464   public JpsModuleSourceRootType<?> getSourceRootType(@NotNull DirectoryInfo directoryInfo) {
465     return myRootTypes.get(directoryInfo.getSourceRootTypeId());
466   }
467
468   boolean resetOnEvents(@NotNull List<? extends VFileEvent> events) {
469     for (VFileEvent event : events) {
470       VirtualFile file = event.getFile();
471       if (file == null || file.isDirectory()) {
472         return true;
473       }
474     }
475     return false;
476   }
477
478   @Nullable("returns null only if dir is under ignored folder")
479   private static List<VirtualFile> getHierarchy(VirtualFile dir, @NotNull Set<VirtualFile> allRoots, @NotNull RootInfo info) {
480     List<VirtualFile> hierarchy = ContainerUtil.newArrayList();
481     boolean hasContentRoots = false;
482     while (dir != null) {
483       hasContentRoots |= info.contentRootOf.get(dir) != null;
484       if (!hasContentRoots && ourFileTypes.isFileIgnored(dir)) {
485         return null;
486       }
487       if (allRoots.contains(dir)) {
488         hierarchy.add(dir);
489       }
490       dir = dir.getParent();
491     }
492     return hierarchy;
493   }
494
495   private static class RootInfo {
496     // getDirectoriesByPackageName used to be in this order, some clients might rely on that
497     @NotNull final LinkedHashSet<VirtualFile> classAndSourceRoots = ContainerUtil.newLinkedHashSet();
498
499     @NotNull final Set<VirtualFile> libraryOrSdkSources = ContainerUtil.newHashSet();
500     @NotNull final Set<VirtualFile> libraryOrSdkClasses = ContainerUtil.newHashSet();
501     @NotNull final Map<VirtualFile, Module> contentRootOf = ContainerUtil.newHashMap();
502     @NotNull final MultiMap<VirtualFile, Module> sourceRootOf = MultiMap.createSet();
503     @NotNull final TObjectIntHashMap<VirtualFile> rootTypeId = new TObjectIntHashMap<VirtualFile>();
504     @NotNull final MultiMap<VirtualFile, Library> excludedFromLibraries = MultiMap.createSmart();
505     @NotNull final MultiMap<VirtualFile, Library> classOfLibraries = MultiMap.createSmart();
506     @NotNull final MultiMap<VirtualFile, Library> sourceOfLibraries = MultiMap.createSmart();
507     @NotNull final Set<VirtualFile> excludedFromProject = ContainerUtil.newHashSet();
508     @NotNull final Map<VirtualFile, Module> excludedFromModule = ContainerUtil.newHashMap();
509     @NotNull final Map<VirtualFile, String> packagePrefix = ContainerUtil.newHashMap();
510
511     @NotNull
512     Set<VirtualFile> getAllRoots() {
513       LinkedHashSet<VirtualFile> result = ContainerUtil.newLinkedHashSet();
514       result.addAll(classAndSourceRoots);
515       result.addAll(contentRootOf.keySet());
516       result.addAll(excludedFromLibraries.keySet());
517       result.addAll(excludedFromModule.keySet());
518       result.addAll(excludedFromProject);
519       return result;
520     }
521
522     @Nullable
523     private VirtualFile findModuleRootInfo(@NotNull List<VirtualFile> hierarchy) {
524       for (VirtualFile root : hierarchy) {
525         Module module = contentRootOf.get(root);
526         Module excludedFrom = excludedFromModule.get(root);
527         if (module != null && excludedFrom != module) {
528           return root;
529         }
530         if (excludedFrom != null || excludedFromProject.contains(root)) {
531           return null;
532         }
533       }
534       return null;
535     }
536
537     @Nullable
538     private VirtualFile findNearestContentRootForExcluded(@NotNull List<VirtualFile> hierarchy) {
539       for (VirtualFile root : hierarchy) {
540         if (contentRootOf.containsKey(root)) {
541           return root;
542         }
543       }
544       return null;
545     }
546
547     @Nullable
548     private VirtualFile findLibraryRootInfo(@NotNull List<VirtualFile> hierarchy, boolean source) {
549       Set<Library> librariesToIgnore = ContainerUtil.newHashSet();
550       for (VirtualFile root : hierarchy) {
551         librariesToIgnore.addAll(excludedFromLibraries.get(root));
552         if (source && libraryOrSdkSources.contains(root) &&
553             (!sourceOfLibraries.containsKey(root) || !librariesToIgnore.containsAll(sourceOfLibraries.get(root)))) {
554           return root;
555         }
556         else if (!source && libraryOrSdkClasses.contains(root) &&
557                  (!classOfLibraries.containsKey(root) || !librariesToIgnore.containsAll(classOfLibraries.get(root)))) {
558           return root;
559         }
560       }
561       return null;
562     }
563
564     private String calcPackagePrefix(@NotNull VirtualFile root,
565                                      @NotNull List<VirtualFile> hierarchy,
566                                      VirtualFile moduleContentRoot,
567                                      VirtualFile libraryClassRoot,
568                                      VirtualFile librarySourceRoot) {
569       VirtualFile packageRoot = findPackageRootInfo(hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
570       String prefix = packagePrefix.get(packageRoot);
571       if (prefix != null && !root.equals(packageRoot)) {
572         assert packageRoot != null;
573         String relative = VfsUtilCore.getRelativePath(root, packageRoot, '.');
574         prefix = StringUtil.isEmpty(prefix) ? relative : prefix + '.' + relative;
575       }
576       return prefix;
577     }
578
579     @Nullable
580     private VirtualFile findPackageRootInfo(@NotNull List<VirtualFile> hierarchy,
581                                             VirtualFile moduleContentRoot,
582                                             VirtualFile libraryClassRoot,
583                                             VirtualFile librarySourceRoot) {
584       for (VirtualFile root : hierarchy) {
585         if (moduleContentRoot != null &&
586             sourceRootOf.get(root).contains(contentRootOf.get(moduleContentRoot)) &&
587             librarySourceRoot == null) {
588           return root;
589         }
590         if (root.equals(libraryClassRoot) || root.equals(librarySourceRoot)) {
591           return root;
592         }
593         if (root.equals(moduleContentRoot) && !sourceRootOf.containsKey(root) && librarySourceRoot == null && libraryClassRoot == null) {
594           return null;
595         }
596       }
597       return null;
598     }
599
600     @NotNull
601     private LinkedHashSet<OrderEntry> getLibraryOrderEntries(@NotNull List<VirtualFile> hierarchy,
602                                                              @Nullable VirtualFile libraryClassRoot,
603                                                              @Nullable VirtualFile librarySourceRoot,
604                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries,
605                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libSourceRootEntries) {
606       LinkedHashSet<OrderEntry> orderEntries = ContainerUtil.newLinkedHashSet();
607       for (VirtualFile root : hierarchy) {
608         if (root.equals(libraryClassRoot) && !sourceRootOf.containsKey(root)) {
609           orderEntries.addAll(libClassRootEntries.get(root));
610         }
611         if (root.equals(librarySourceRoot) && libraryClassRoot == null) {
612           orderEntries.addAll(libSourceRootEntries.get(root));
613         }
614         if (libClassRootEntries.containsKey(root) || sourceRootOf.containsKey(root) && librarySourceRoot == null) {
615           break;
616         }
617       }
618       return orderEntries;
619     }
620
621
622     @Nullable
623     private ModuleSourceOrderEntry getModuleSourceEntry(@NotNull List<VirtualFile> hierarchy,
624                                                         @NotNull VirtualFile moduleContentRoot,
625                                                         @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries) {
626       Module module = contentRootOf.get(moduleContentRoot);
627       for (VirtualFile root : hierarchy) {
628         if (sourceRootOf.get(root).contains(module)) {
629           return ContainerUtil.findInstance(ModuleRootManager.getInstance(module).getOrderEntries(), ModuleSourceOrderEntry.class);
630         }
631         if (libClassRootEntries.containsKey(root)) {
632           return null;
633         }
634       }
635       return null;
636     }
637   }
638
639   @NotNull
640   private static Pair<DirectoryInfo, String> calcDirectoryInfo(@NotNull final VirtualFile root,
641                                                                @NotNull final List<VirtualFile> hierarchy,
642                                                                @NotNull RootInfo info) {
643     VirtualFile moduleContentRoot = info.findModuleRootInfo(hierarchy);
644     VirtualFile libraryClassRoot = info.findLibraryRootInfo(hierarchy, false);
645     VirtualFile librarySourceRoot = info.findLibraryRootInfo(hierarchy, true);
646     boolean inProject = moduleContentRoot != null || libraryClassRoot != null || librarySourceRoot != null;
647     VirtualFile nearestContentRoot;
648     if (inProject) {
649       nearestContentRoot = moduleContentRoot;
650     }
651     else {
652       nearestContentRoot = info.findNearestContentRootForExcluded(hierarchy);
653       if (nearestContentRoot == null) {
654         return new Pair<DirectoryInfo, String>(NonProjectDirectoryInfo.EXCLUDED, null);
655       }
656     }
657
658     VirtualFile sourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, librarySourceRoot);
659
660     VirtualFile moduleSourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, null);
661     boolean inModuleSources = moduleSourceRoot != null;
662     boolean inLibrarySource = librarySourceRoot != null;
663     int typeId = moduleSourceRoot != null ? info.rootTypeId.get(moduleSourceRoot) : 0;
664
665     Module module = info.contentRootOf.get(nearestContentRoot);
666     DirectoryInfo directoryInfo =
667       new DirectoryInfoImpl(root, module, nearestContentRoot, sourceRoot, libraryClassRoot, inModuleSources, inLibrarySource, !inProject, typeId);
668
669     String packagePrefix = info.calcPackagePrefix(root, hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
670
671     return Pair.create(directoryInfo, packagePrefix);
672   }
673
674   @NotNull
675   public List<OrderEntry> getOrderEntries(@NotNull DirectoryInfo info) {
676     if (!(info instanceof DirectoryInfoImpl)) return Collections.emptyList();
677     return getOrderEntryGraph().getOrderEntries(((DirectoryInfoImpl)info).getRoot());
678   }
679
680   public interface InfoCache {
681     @Nullable
682     DirectoryInfo getCachedInfo(@NotNull VirtualFile dir);
683
684     void cacheInfo(@NotNull VirtualFile dir, @NotNull DirectoryInfo info);
685   }
686
687   /**
688    * An LRU cache with synchronization around the primary cache operations (get() and insertion
689    * of a newly created value). Other map operations are not synchronized.
690    */
691   abstract static class SynchronizedSLRUCache<K, V> extends SLRUMap<K,V> {
692     protected final Object myLock = new Object();
693
694     protected SynchronizedSLRUCache(final int protectedQueueSize, final int probationalQueueSize) {
695       super(protectedQueueSize, probationalQueueSize);
696     }
697
698     @NotNull
699     public abstract V createValue(K key);
700
701     @Override
702     @NotNull
703     public V get(K key) {
704       V value;
705       synchronized (myLock) {
706         value = super.get(key);
707         if (value != null) {
708           return value;
709         }
710       }
711       value = createValue(key);
712       synchronized (myLock) {
713         put(key, value);
714       }
715       return value;
716     }
717   }
718 }