eb04fb6c103e981e4891004bd3c8510ac7abfc79
[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.Condition;
28 import com.intellij.openapi.util.LowMemoryWatcher;
29 import com.intellij.openapi.util.Pair;
30 import com.intellij.openapi.util.text.StringUtil;
31 import com.intellij.openapi.vfs.VfsUtilCore;
32 import com.intellij.openapi.vfs.VirtualFile;
33 import com.intellij.openapi.vfs.newvfs.events.VFileEvent;
34 import com.intellij.util.CollectionQuery;
35 import com.intellij.util.EmptyQuery;
36 import com.intellij.util.Query;
37 import com.intellij.util.containers.ConcurrentHashSet;
38 import com.intellij.util.containers.ContainerUtil;
39 import com.intellij.util.containers.MultiMap;
40 import gnu.trove.TObjectIntHashMap;
41 import org.jetbrains.annotations.NotNull;
42 import org.jetbrains.annotations.Nullable;
43 import org.jetbrains.jps.model.module.JpsModuleSourceRootType;
44
45 import java.util.*;
46
47 public class RootIndex {
48   public static final Comparator<OrderEntry> BY_OWNER_MODULE = new Comparator<OrderEntry>() {
49     @Override
50     public int compare(OrderEntry o1, OrderEntry o2) {
51       String name1 = o1.getOwnerModule().getName();
52       String name2 = o2.getOwnerModule().getName();
53       return name1.compareTo(name2);
54     }
55   };
56   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.roots.impl.RootIndex");
57
58   private final Set<VirtualFile> myProjectExcludedRoots = ContainerUtil.newHashSet();
59   private final MultiMap<String, VirtualFile> myPackagePrefixRoots = new MultiMap<String, VirtualFile>() {
60     @NotNull
61     @Override
62     protected Collection<VirtualFile> createCollection() {
63       return ContainerUtil.newLinkedHashSet();
64     }
65   };
66
67   private final Map<String, List<VirtualFile>> myDirectoriesByPackageNameCache = ContainerUtil.newConcurrentMap();
68   private final Set<String> myNonExistentPackages = new ConcurrentHashSet<String>();
69   private final InfoCache myInfoCache;
70   private final List<JpsModuleSourceRootType<?>> myRootTypes = ContainerUtil.newArrayList();
71   private final TObjectIntHashMap<JpsModuleSourceRootType<?>> myRootTypeId = new TObjectIntHashMap<JpsModuleSourceRootType<?>>();
72   @NotNull private final Project myProject;
73   private volatile Map<VirtualFile, OrderEntry[]> myOrderEntries;
74   @SuppressWarnings("UnusedDeclaration")
75   private final LowMemoryWatcher myLowMemoryWatcher = LowMemoryWatcher.register(new Runnable() {
76     @Override
77     public void run() {
78       myNonExistentPackages.clear();
79     }
80   });
81
82
83   // made public for Upsource
84   public RootIndex(@NotNull Project project, @NotNull InfoCache cache) {
85     myProject = project;
86     myInfoCache = cache;
87     final RootInfo info = buildRootInfo(project);
88
89     Set<VirtualFile> allRoots = info.getAllRoots();
90     for (VirtualFile root : allRoots) {
91       List<VirtualFile> hierarchy = getHierarchy(root, allRoots, info);
92       Pair<DirectoryInfo, String> pair = hierarchy != null
93                                          ? calcDirectoryInfo(root, hierarchy, info)
94                                          : new Pair<DirectoryInfo, String>(NonProjectDirectoryInfo.IGNORED, null);
95       cacheInfos(root, root, pair.first);
96       myPackagePrefixRoots.putValue(pair.second, root);
97       if (info.shouldMarkAsProjectExcluded(root, hierarchy)) {
98         myProjectExcludedRoots.add(root);
99       }
100     }
101   }
102
103   @NotNull
104   private RootInfo buildRootInfo(@NotNull Project project) {
105     final RootInfo info = new RootInfo();
106     for (final Module module : ModuleManager.getInstance(project).getModules()) {
107       final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
108
109       for (final VirtualFile contentRoot : moduleRootManager.getContentRoots()) {
110         if (!info.contentRootOf.containsKey(contentRoot)) {
111           info.contentRootOf.put(contentRoot, module);
112         }
113       }
114
115       for (ContentEntry contentEntry : moduleRootManager.getContentEntries()) {
116         if (!(contentEntry instanceof ContentEntryImpl) || !((ContentEntryImpl)contentEntry).isDisposed()) {
117           for (VirtualFile excludeRoot : contentEntry.getExcludeFolderFiles()) {
118             info.excludedFromModule.put(excludeRoot, module);
119           }
120         }
121
122         // Init module sources
123         for (final SourceFolder sourceFolder : contentEntry.getSourceFolders()) {
124           final VirtualFile sourceFolderRoot = sourceFolder.getFile();
125           if (sourceFolderRoot != null) {
126             info.rootTypeId.put(sourceFolderRoot, getRootTypeId(sourceFolder.getRootType()));
127             info.classAndSourceRoots.add(sourceFolderRoot);
128             info.sourceRootOf.putValue(sourceFolderRoot, module);
129             info.packagePrefix.put(sourceFolderRoot, sourceFolder.getPackagePrefix());
130           }
131         }
132       }
133
134       for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
135         if (orderEntry instanceof LibraryOrSdkOrderEntry) {
136           final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
137           final VirtualFile[] sourceRoots = entry.getRootFiles(OrderRootType.SOURCES);
138           final VirtualFile[] classRoots = entry.getRootFiles(OrderRootType.CLASSES);
139
140           // Init library sources
141           for (final VirtualFile sourceRoot : sourceRoots) {
142             info.classAndSourceRoots.add(sourceRoot);
143             info.libraryOrSdkSources.add(sourceRoot);
144             info.packagePrefix.put(sourceRoot, "");
145           }
146
147           // init library classes
148           for (final VirtualFile classRoot : classRoots) {
149             info.classAndSourceRoots.add(classRoot);
150             info.libraryOrSdkClasses.add(classRoot);
151             info.packagePrefix.put(classRoot, "");
152           }
153
154           if (orderEntry instanceof LibraryOrderEntry) {
155             Library library = ((LibraryOrderEntry)orderEntry).getLibrary();
156             if (library != null) {
157               for (VirtualFile root : ((LibraryEx)library).getExcludedRoots()) {
158                 info.excludedFromLibraries.putValue(root, library);
159               }
160               for (VirtualFile root : sourceRoots) {
161                 info.sourceOfLibraries.putValue(root, library);
162               }
163               for (VirtualFile root : classRoots) {
164                 info.classOfLibraries.putValue(root, library);
165               }
166             }
167           }
168         }
169       }
170     }
171
172     for (DirectoryIndexExcludePolicy policy : Extensions.getExtensions(DirectoryIndexExcludePolicy.EP_NAME, project)) {
173       Collections.addAll(info.excludedFromProject, policy.getExcludeRootsForProject());
174     }
175     return info;
176   }
177
178   @NotNull
179   private Map<VirtualFile, OrderEntry[]> getOrderEntries() {
180     Map<VirtualFile, OrderEntry[]> result = myOrderEntries;
181     if (result != null) return result;
182
183     MultiMap<VirtualFile, OrderEntry> libClassRootEntries = MultiMap.createSmartList();
184     MultiMap<VirtualFile, OrderEntry> libSourceRootEntries = MultiMap.createSmartList();
185     MultiMap<VirtualFile, OrderEntry> depEntries = MultiMap.createSmartList();
186
187     for (final Module module : ModuleManager.getInstance(myProject).getModules()) {
188       final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
189       for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
190         if (orderEntry instanceof ModuleOrderEntry) {
191           final Module depModule = ((ModuleOrderEntry)orderEntry).getModule();
192           if (depModule != null) {
193             VirtualFile[] importedClassRoots =
194               OrderEnumerator.orderEntries(depModule).exportedOnly().recursively().classes().usingCache().getRoots();
195             for (VirtualFile importedClassRoot : importedClassRoots) {
196               depEntries.putValue(importedClassRoot, orderEntry);
197             }
198           }
199           for (VirtualFile sourceRoot : orderEntry.getFiles(OrderRootType.SOURCES)) {
200             depEntries.putValue(sourceRoot, orderEntry);
201           }
202         }
203         else if (orderEntry instanceof LibraryOrSdkOrderEntry) {
204           final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
205           for (final VirtualFile sourceRoot : entry.getRootFiles(OrderRootType.SOURCES)) {
206             libSourceRootEntries.putValue(sourceRoot, orderEntry);
207           }
208           for (final VirtualFile classRoot : entry.getRootFiles(OrderRootType.CLASSES)) {
209             libClassRootEntries.putValue(classRoot, orderEntry);
210           }
211         }
212       }
213     }
214
215     RootInfo rootInfo = buildRootInfo(myProject);
216     result = ContainerUtil.newHashMap();
217     Set<VirtualFile> allRoots = rootInfo.getAllRoots();
218     for (VirtualFile file : allRoots) {
219       List<VirtualFile> hierarchy = getHierarchy(file, allRoots, rootInfo);
220       result.put(file, hierarchy == null
221                        ? OrderEntry.EMPTY_ARRAY
222                        : calcOrderEntries(rootInfo, depEntries, libClassRootEntries, libSourceRootEntries, hierarchy));
223     }
224     myOrderEntries = result;
225     return result;
226   }
227
228   private static OrderEntry[] calcOrderEntries(@NotNull RootInfo info,
229                                                @NotNull MultiMap<VirtualFile, OrderEntry> depEntries,
230                                                @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries,
231                                                @NotNull MultiMap<VirtualFile, OrderEntry> libSourceRootEntries,
232                                                @NotNull List<VirtualFile> hierarchy) {
233     @Nullable VirtualFile libraryClassRoot = info.findLibraryRootInfo(hierarchy, false);
234     @Nullable VirtualFile librarySourceRoot = info.findLibraryRootInfo(hierarchy, true);
235     Set<OrderEntry> orderEntries = ContainerUtil.newLinkedHashSet();
236     orderEntries
237       .addAll(info.getLibraryOrderEntries(hierarchy, libraryClassRoot, librarySourceRoot, libClassRootEntries, libSourceRootEntries));
238     for (VirtualFile root : hierarchy) {
239       orderEntries.addAll(depEntries.get(root));
240     }
241     VirtualFile moduleContentRoot = info.findModuleRootInfo(hierarchy);
242     if (moduleContentRoot != null) {
243       ContainerUtil.addIfNotNull(orderEntries, info.getModuleSourceEntry(hierarchy, moduleContentRoot, libClassRootEntries));
244     }
245     if (orderEntries.isEmpty()) {
246       return null;
247     }
248
249     OrderEntry[] array = orderEntries.toArray(new OrderEntry[orderEntries.size()]);
250     Arrays.sort(array, BY_OWNER_MODULE);
251     return array;
252   }
253
254
255   public void checkConsistency() {
256     for (VirtualFile file : myProjectExcludedRoots) {
257       assert file.exists() : file.getPath() + " does not exist";
258     }
259
260     for (VirtualFile file : myPackagePrefixRoots.values()) {
261       assert file.exists() : file.getPath() + " does not exist";
262     }
263   }
264
265   private int getRootTypeId(@NotNull JpsModuleSourceRootType<?> rootType) {
266     if (myRootTypeId.containsKey(rootType)) {
267       return myRootTypeId.get(rootType);
268     }
269
270     int id = myRootTypes.size();
271     if (id > DirectoryInfoImpl.MAX_ROOT_TYPE_ID) {
272       LOG.error("Too many different types of module source roots (" + id + ") registered: " + myRootTypes);
273     }
274     myRootTypes.add(rootType);
275     myRootTypeId.put(rootType, id);
276     return id;
277   }
278
279   @NotNull
280   public DirectoryInfo getInfoForFile(@NotNull VirtualFile file) {
281     if (!file.isValid()) {
282       return NonProjectDirectoryInfo.INVALID;
283     }
284     VirtualFile dir;
285     if (!file.isDirectory()) {
286       DirectoryInfo info = myInfoCache.getCachedInfo(file);
287       if (info != null) {
288         return info;
289       }
290       if (isIgnored(file)) {
291         return NonProjectDirectoryInfo.IGNORED;
292       }
293       dir = file.getParent();
294     }
295     else {
296       dir = file;
297     }
298
299     int count = 0;
300     for (VirtualFile root = dir; root != null; root = root.getParent()) {
301       if (++count > 1000) {
302         throw new IllegalStateException("Possible loop in tree, started at " + dir.getName());
303       }
304       DirectoryInfo info = myInfoCache.getCachedInfo(root);
305       if (info != null) {
306         if (!dir.equals(root)) {
307           cacheInfos(dir, root, info);
308         }
309         return info;
310       }
311
312       if (isIgnored(root)) {
313         return cacheInfos(dir, root, NonProjectDirectoryInfo.IGNORED);
314       }
315     }
316
317     return cacheInfos(dir, null, NonProjectDirectoryInfo.NOT_UNDER_PROJECT_ROOTS);
318   }
319
320   @NotNull
321   private DirectoryInfo cacheInfos(VirtualFile dir, @Nullable VirtualFile stopAt, @NotNull DirectoryInfo info) {
322     while (dir != null) {
323       myInfoCache.cacheInfo(dir, info);
324       if (dir.equals(stopAt)) {
325         break;
326       }
327       dir = dir.getParent();
328     }
329     return info;
330   }
331
332   @NotNull
333   public Query<VirtualFile> getDirectoriesByPackageName(@NotNull final String packageName, final boolean includeLibrarySources) {
334     List<VirtualFile> result = myDirectoriesByPackageNameCache.get(packageName);
335     if (result == null) {
336       if (myNonExistentPackages.contains(packageName)) return EmptyQuery.getEmptyQuery();
337
338       result = ContainerUtil.newSmartList();
339
340       if (StringUtil.isNotEmpty(packageName) && !StringUtil.startsWithChar(packageName, '.')) {
341         int i = packageName.lastIndexOf('.');
342         while (true) {
343           String shortName = packageName.substring(i + 1);
344           String parentPackage = i > 0 ? packageName.substring(0, i) : "";
345           for (VirtualFile parentDir : getDirectoriesByPackageName(parentPackage, true)) {
346             VirtualFile child = parentDir.findChild(shortName);
347             if (child != null && child.isDirectory() && getInfoForFile(child).isInProject()
348                 && packageName.equals(getPackageName(child))) {
349               result.add(child);
350             }
351           }
352           if (i < 0) break;
353           i = packageName.lastIndexOf('.', i - 1);
354         }
355       }
356
357       for (VirtualFile file : myPackagePrefixRoots.get(packageName)) {
358         if (file.isDirectory()) {
359           result.add(file);
360         }
361       }
362
363       if (!result.isEmpty()) {
364         myDirectoriesByPackageNameCache.put(packageName, result);
365       } else {
366         myNonExistentPackages.add(packageName);
367       }
368     }
369
370     if (!includeLibrarySources) {
371       result = ContainerUtil.filter(result, new Condition<VirtualFile>() {
372         @Override
373         public boolean value(VirtualFile file) {
374           DirectoryInfo info = getInfoForFile(file);
375           return info.isInProject() && (!info.isInLibrarySource() || info.isInModuleSource() || info.hasLibraryClassRoot());
376         }
377       });
378     }
379     return new CollectionQuery<VirtualFile>(result);
380   }
381
382   @Nullable
383   public String getPackageName(@NotNull final VirtualFile dir) {
384     if (dir.isDirectory()) {
385       if (isIgnored(dir)) {
386         return null;
387       }
388
389       for (final Map.Entry<String, Collection<VirtualFile>> entry : myPackagePrefixRoots.entrySet()) {
390         if (entry.getValue().contains(dir)) {
391           return entry.getKey();
392         }
393       }
394
395       final VirtualFile parent = dir.getParent();
396       if (parent != null) {
397         return getPackageNameForSubdir(getPackageName(parent), dir.getName());
398       }
399     }
400
401     return null;
402   }
403
404   @Nullable
405   protected static String getPackageNameForSubdir(String parentPackageName, @NotNull String subdirName) {
406     if (parentPackageName == null) return null;
407     return parentPackageName.isEmpty() ? subdirName : parentPackageName + "." + subdirName;
408   }
409
410   @Nullable
411   public JpsModuleSourceRootType<?> getSourceRootType(@NotNull DirectoryInfo directoryInfo) {
412     return myRootTypes.get(directoryInfo.getSourceRootTypeId());
413   }
414
415   boolean resetOnEvents(@NotNull List<? extends VFileEvent> events) {
416     for (VFileEvent event : events) {
417       VirtualFile file = event.getFile();
418       if (file == null || file.isDirectory()) {
419         return true;
420       }
421     }
422     return false;
423   }
424
425   @Nullable("returns null only if dir is under ignored folder")
426   private static List<VirtualFile> getHierarchy(VirtualFile dir, @NotNull Set<VirtualFile> allRoots, @NotNull RootInfo info) {
427     List<VirtualFile> hierarchy = ContainerUtil.newArrayList();
428     boolean hasContentRoots = false;
429     while (dir != null) {
430       hasContentRoots |= info.contentRootOf.get(dir) != null;
431       if (!hasContentRoots && isIgnored(dir)) {
432         return null;
433       }
434       if (allRoots.contains(dir)) {
435         hierarchy.add(dir);
436       }
437       dir = dir.getParent();
438     }
439     return hierarchy;
440   }
441
442   private static boolean isIgnored(@NotNull VirtualFile dir) {
443     return FileTypeRegistry.getInstance().isFileIgnored(dir);
444   }
445
446   private static class RootInfo {
447     // getDirectoriesByPackageName used to be in this order, some clients might rely on that
448     @NotNull final LinkedHashSet<VirtualFile> classAndSourceRoots = ContainerUtil.newLinkedHashSet();
449
450     @NotNull final Set<VirtualFile> libraryOrSdkSources = ContainerUtil.newHashSet();
451     @NotNull final Set<VirtualFile> libraryOrSdkClasses = ContainerUtil.newHashSet();
452     @NotNull final Map<VirtualFile, Module> contentRootOf = ContainerUtil.newHashMap();
453     @NotNull final MultiMap<VirtualFile, Module> sourceRootOf = MultiMap.createSet();
454     @NotNull final TObjectIntHashMap<VirtualFile> rootTypeId = new TObjectIntHashMap<VirtualFile>();
455     @NotNull final MultiMap<VirtualFile, Library> excludedFromLibraries = MultiMap.createSmartList();
456     @NotNull final MultiMap<VirtualFile, Library> classOfLibraries = MultiMap.createSmartList();
457     @NotNull final MultiMap<VirtualFile, Library> sourceOfLibraries = MultiMap.createSmartList();
458     @NotNull final Set<VirtualFile> excludedFromProject = ContainerUtil.newHashSet();
459     @NotNull final Map<VirtualFile, Module> excludedFromModule = ContainerUtil.newHashMap();
460     @NotNull final Map<VirtualFile, String> packagePrefix = ContainerUtil.newHashMap();
461
462     @NotNull
463     Set<VirtualFile> getAllRoots() {
464       LinkedHashSet<VirtualFile> result = ContainerUtil.newLinkedHashSet();
465       result.addAll(classAndSourceRoots);
466       result.addAll(contentRootOf.keySet());
467       result.addAll(excludedFromLibraries.keySet());
468       result.addAll(excludedFromModule.keySet());
469       result.addAll(excludedFromProject);
470       return result;
471     }
472
473     private boolean shouldMarkAsProjectExcluded(@NotNull VirtualFile root, @Nullable List<VirtualFile> hierarchy) {
474       if (hierarchy == null) return false;
475       if (!excludedFromProject.contains(root) && !excludedFromModule.containsKey(root)) return false;
476       return ContainerUtil.find(hierarchy, new Condition<VirtualFile>() {
477         @Override
478         public boolean value(VirtualFile ancestor) {
479           return contentRootOf.containsKey(ancestor);
480         }
481       }) == null;
482     }
483
484     @Nullable
485     private VirtualFile findModuleRootInfo(@NotNull List<VirtualFile> hierarchy) {
486       for (VirtualFile root : hierarchy) {
487         Module module = contentRootOf.get(root);
488         Module excludedFrom = excludedFromModule.get(root);
489         if (module != null && excludedFrom != module) {
490           return root;
491         }
492         if (excludedFrom != null || excludedFromProject.contains(root)) {
493           return null;
494         }
495       }
496       return null;
497     }
498
499     @Nullable
500     private Module findParentModuleForExcluded(@NotNull List<VirtualFile> hierarchy) {
501       for (VirtualFile root : hierarchy) {
502         Module module = contentRootOf.get(root);
503         if (module != null) return module;
504       }
505       return null;
506     }
507
508     @Nullable
509     private VirtualFile findLibraryRootInfo(@NotNull List<VirtualFile> hierarchy, boolean source) {
510       Set<Library> librariesToIgnore = ContainerUtil.newHashSet();
511       for (VirtualFile root : hierarchy) {
512         librariesToIgnore.addAll(excludedFromLibraries.get(root));
513         if (source && libraryOrSdkSources.contains(root) &&
514             (!sourceOfLibraries.containsKey(root) || !librariesToIgnore.containsAll(sourceOfLibraries.get(root)))) {
515           return root;
516         }
517         else if (!source && libraryOrSdkClasses.contains(root) &&
518                  (!classOfLibraries.containsKey(root) || !librariesToIgnore.containsAll(classOfLibraries.get(root)))) {
519           return root;
520         }
521       }
522       return null;
523     }
524
525     private String calcPackagePrefix(@NotNull VirtualFile root,
526                                      @NotNull List<VirtualFile> hierarchy,
527                                      VirtualFile moduleContentRoot,
528                                      VirtualFile libraryClassRoot,
529                                      VirtualFile librarySourceRoot) {
530       VirtualFile packageRoot = findPackageRootInfo(hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
531       String prefix = packagePrefix.get(packageRoot);
532       if (prefix != null && !root.equals(packageRoot)) {
533         assert packageRoot != null;
534         String relative = VfsUtilCore.getRelativePath(root, packageRoot, '.');
535         prefix = StringUtil.isEmpty(prefix) ? relative : prefix + '.' + relative;
536       }
537       return prefix;
538     }
539
540     @Nullable
541     private VirtualFile findPackageRootInfo(@NotNull List<VirtualFile> hierarchy,
542                                             VirtualFile moduleContentRoot,
543                                             VirtualFile libraryClassRoot,
544                                             VirtualFile librarySourceRoot) {
545       for (VirtualFile root : hierarchy) {
546         if (moduleContentRoot != null &&
547             sourceRootOf.get(root).contains(contentRootOf.get(moduleContentRoot)) &&
548             librarySourceRoot == null) {
549           return root;
550         }
551         if (root.equals(libraryClassRoot) || root.equals(librarySourceRoot)) {
552           return root;
553         }
554         if (root.equals(moduleContentRoot) && !sourceRootOf.containsKey(root) && librarySourceRoot == null && libraryClassRoot == null) {
555           return null;
556         }
557       }
558       return null;
559     }
560
561     @NotNull
562     private LinkedHashSet<OrderEntry> getLibraryOrderEntries(@NotNull List<VirtualFile> hierarchy,
563                                                              @Nullable VirtualFile libraryClassRoot,
564                                                              @Nullable VirtualFile librarySourceRoot,
565                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries,
566                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libSourceRootEntries) {
567       LinkedHashSet<OrderEntry> orderEntries = ContainerUtil.newLinkedHashSet();
568       for (VirtualFile root : hierarchy) {
569         if (root.equals(libraryClassRoot) && !sourceRootOf.containsKey(root)) {
570           orderEntries.addAll(libClassRootEntries.get(root));
571         }
572         if (root.equals(librarySourceRoot) && libraryClassRoot == null) {
573           orderEntries.addAll(libSourceRootEntries.get(root));
574         }
575         if (libClassRootEntries.containsKey(root) || sourceRootOf.containsKey(root) && librarySourceRoot == null) {
576           break;
577         }
578       }
579       return orderEntries;
580     }
581
582     @Nullable
583     private ModuleSourceOrderEntry getModuleSourceEntry(@NotNull List<VirtualFile> hierarchy,
584                                                         @NotNull VirtualFile moduleContentRoot,
585                                                         @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries) {
586       Module module = contentRootOf.get(moduleContentRoot);
587       for (VirtualFile root : hierarchy) {
588         if (sourceRootOf.get(root).contains(module)) {
589           return ContainerUtil.findInstance(ModuleRootManager.getInstance(module).getOrderEntries(), ModuleSourceOrderEntry.class);
590         }
591         if (libClassRootEntries.containsKey(root)) {
592           return null;
593         }
594       }
595       return null;
596     }
597   }
598
599
600   @NotNull
601   private static Pair<DirectoryInfo, String> calcDirectoryInfo(@NotNull final VirtualFile root,
602                                                                @NotNull final List<VirtualFile> hierarchy,
603                                                                @NotNull RootInfo info) {
604     VirtualFile moduleContentRoot = info.findModuleRootInfo(hierarchy);
605     VirtualFile libraryClassRoot = info.findLibraryRootInfo(hierarchy, false);
606     VirtualFile librarySourceRoot = info.findLibraryRootInfo(hierarchy, true);
607     Module parentModuleForExcluded = null;
608     if (moduleContentRoot == null && libraryClassRoot == null && librarySourceRoot == null) {
609       parentModuleForExcluded = info.findParentModuleForExcluded(hierarchy);
610       if (parentModuleForExcluded == null) {
611         return new Pair<DirectoryInfo, String>(NonProjectDirectoryInfo.EXCLUDED, null);
612       }
613     }
614
615     VirtualFile sourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, librarySourceRoot);
616
617     VirtualFile moduleSourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, null);
618     boolean inModuleSources = moduleSourceRoot != null;
619     boolean inLibrarySource = librarySourceRoot != null;
620     int typeId = moduleSourceRoot != null ? info.rootTypeId.get(moduleSourceRoot) : 0;
621
622     Module module = parentModuleForExcluded != null ? parentModuleForExcluded : info.contentRootOf.get(moduleContentRoot);
623     DirectoryInfo directoryInfo =
624       new DirectoryInfoImpl(root, module, moduleContentRoot, sourceRoot, libraryClassRoot, inModuleSources, inLibrarySource,
625                             parentModuleForExcluded != null, typeId);
626
627     String packagePrefix = info.calcPackagePrefix(root, hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
628
629     return Pair.create(directoryInfo, packagePrefix);
630   }
631
632   @NotNull
633   public OrderEntry[] getOrderEntries(@NotNull DirectoryInfo info) {
634     if (!(info instanceof DirectoryInfoImpl)) return OrderEntry.EMPTY_ARRAY;
635     OrderEntry[] entries = this.getOrderEntries().get(((DirectoryInfoImpl)info).getRoot());
636     return entries == null ? OrderEntry.EMPTY_ARRAY : entries;
637   }
638
639   public interface InfoCache {
640     @Nullable
641     DirectoryInfo getCachedInfo(@NotNull VirtualFile dir);
642
643     void cacheInfo(@NotNull VirtualFile dir, @NotNull DirectoryInfo info);
644   }
645 }