f65fd597af7e0657d3276d0a3eece02655d1fc8e
[idea/community.git] / platform / projectModel-impl / src / com / intellij / openapi / roots / impl / RootIndex.java
1 /*
2  * Copyright 2000-2017 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.fileTypes.impl.FileTypeAssocTable;
22 import com.intellij.openapi.module.Module;
23 import com.intellij.openapi.module.ModuleManager;
24 import com.intellij.openapi.module.UnloadedModuleDescription;
25 import com.intellij.openapi.project.Project;
26 import com.intellij.openapi.projectRoots.Sdk;
27 import com.intellij.openapi.roots.*;
28 import com.intellij.openapi.roots.impl.libraries.LibraryEx;
29 import com.intellij.openapi.roots.libraries.Library;
30 import com.intellij.openapi.util.Condition;
31 import com.intellij.openapi.util.Conditions;
32 import com.intellij.openapi.util.Pair;
33 import com.intellij.openapi.util.text.StringUtil;
34 import com.intellij.openapi.vfs.VfsUtilCore;
35 import com.intellij.openapi.vfs.VirtualFile;
36 import com.intellij.openapi.vfs.VirtualFileWithId;
37 import com.intellij.openapi.vfs.newvfs.events.VFileEvent;
38 import com.intellij.openapi.vfs.pointers.VirtualFilePointer;
39 import com.intellij.util.CollectionQuery;
40 import com.intellij.util.Function;
41 import com.intellij.util.Query;
42 import com.intellij.util.containers.ContainerUtil;
43 import com.intellij.util.containers.MultiMap;
44 import com.intellij.util.containers.SLRUMap;
45 import gnu.trove.TObjectIntHashMap;
46 import org.jetbrains.annotations.NotNull;
47 import org.jetbrains.annotations.Nullable;
48 import org.jetbrains.jps.model.fileTypes.FileNameMatcherFactory;
49 import org.jetbrains.jps.model.module.JpsModuleSourceRootType;
50
51 import java.util.*;
52
53 public class RootIndex {
54   public static final Comparator<OrderEntry> BY_OWNER_MODULE = (o1, o2) -> {
55     String name1 = o1.getOwnerModule().getName();
56     String name2 = o2.getOwnerModule().getName();
57     return name1.compareTo(name2);
58   };
59
60   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.roots.impl.RootIndex");
61   private static final FileTypeRegistry ourFileTypes = FileTypeRegistry.getInstance();
62
63   private final Map<VirtualFile, String> myPackagePrefixByRoot = ContainerUtil.newHashMap();
64
65   private final InfoCache myInfoCache;
66   private final List<JpsModuleSourceRootType<?>> myRootTypes = ContainerUtil.newArrayList();
67   private final TObjectIntHashMap<JpsModuleSourceRootType<?>> myRootTypeId = new TObjectIntHashMap<>();
68   @NotNull private final Project myProject;
69   private final PackageDirectoryCache myPackageDirectoryCache;
70   private OrderEntryGraph myOrderEntryGraph;
71
72   // made public for Upsource
73   public RootIndex(@NotNull Project project, @NotNull InfoCache cache) {
74     myProject = project;
75     myInfoCache = cache;
76     final RootInfo info = buildRootInfo(project);
77
78     MultiMap<String, VirtualFile> rootsByPackagePrefix = MultiMap.create();
79     Set<VirtualFile> allRoots = info.getAllRoots();
80     for (VirtualFile root : allRoots) {
81       List<VirtualFile> hierarchy = getHierarchy(root, allRoots, info);
82       Pair<DirectoryInfo, String> pair = hierarchy != null
83                                          ? calcDirectoryInfo(root, hierarchy, info)
84                                          : new Pair<>(NonProjectDirectoryInfo.IGNORED, null);
85       cacheInfos(root, root, pair.first);
86       rootsByPackagePrefix.putValue(pair.second, root);
87       myPackagePrefixByRoot.put(root, pair.second);
88     }
89     myPackageDirectoryCache = new PackageDirectoryCache(rootsByPackagePrefix) {
90       @Override
91       protected boolean isPackageDirectory(@NotNull VirtualFile dir, @NotNull String packageName) {
92         return getInfoForFile(dir).isInProject(dir) && packageName.equals(getPackageName(dir));
93       }
94     };
95   }
96
97   public void onLowMemory() {
98     myPackageDirectoryCache.onLowMemory();
99   }
100
101   @NotNull
102   private RootInfo buildRootInfo(@NotNull Project project) {
103     final RootInfo info = new RootInfo();
104     ModuleManager moduleManager = ModuleManager.getInstance(project);
105     for (final Module module : moduleManager.getModules()) {
106       final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
107
108       for (final VirtualFile contentRoot : moduleRootManager.getContentRoots()) {
109         if (!info.contentRootOf.containsKey(contentRoot) && ensureValid(contentRoot, module)) {
110           info.contentRootOf.put(contentRoot, module);
111         }
112       }
113
114       for (ContentEntry contentEntry : moduleRootManager.getContentEntries()) {
115         if (!(contentEntry instanceof ContentEntryImpl) || !((ContentEntryImpl)contentEntry).isDisposed()) {
116           for (VirtualFile excludeRoot : contentEntry.getExcludeFolderFiles()) {
117             if (!ensureValid(excludeRoot, contentEntry)) continue;
118
119             info.excludedFromModule.put(excludeRoot, module);
120           }
121           List<String> patterns = contentEntry.getExcludePatterns();
122           if (!patterns.isEmpty()) {
123             FileTypeAssocTable<Boolean> table = new FileTypeAssocTable<>();
124             for (String pattern : patterns) {
125               table.addAssociation(FileNameMatcherFactory.getInstance().createMatcher(pattern), Boolean.TRUE);
126             }
127             info.excludeFromContentRootTables.put(contentEntry.getFile(), table);
128           }
129         }
130
131         // Init module sources
132         for (final SourceFolder sourceFolder : contentEntry.getSourceFolders()) {
133           final VirtualFile sourceFolderRoot = sourceFolder.getFile();
134           if (sourceFolderRoot != null && ensureValid(sourceFolderRoot, sourceFolder)) {
135             info.rootTypeId.put(sourceFolderRoot, getRootTypeId(sourceFolder.getRootType()));
136             info.classAndSourceRoots.add(sourceFolderRoot);
137             info.sourceRootOf.putValue(sourceFolderRoot, module);
138             info.packagePrefix.put(sourceFolderRoot, sourceFolder.getPackagePrefix());
139           }
140         }
141       }
142
143       for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
144         if (orderEntry instanceof LibraryOrSdkOrderEntry) {
145           final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
146           final VirtualFile[] sourceRoots = entry.getRootFiles(OrderRootType.SOURCES);
147           final VirtualFile[] classRoots = entry.getRootFiles(OrderRootType.CLASSES);
148
149           // Init library sources
150           for (final VirtualFile sourceRoot : sourceRoots) {
151             if (!ensureValid(sourceRoot, entry)) continue;
152
153             info.classAndSourceRoots.add(sourceRoot);
154             info.libraryOrSdkSources.add(sourceRoot);
155             info.packagePrefix.put(sourceRoot, "");
156           }
157
158           // init library classes
159           for (final VirtualFile classRoot : classRoots) {
160             if (!ensureValid(classRoot, entry)) continue;
161
162             info.classAndSourceRoots.add(classRoot);
163             info.libraryOrSdkClasses.add(classRoot);
164             info.packagePrefix.put(classRoot, "");
165           }
166
167           if (orderEntry instanceof LibraryOrderEntry) {
168             Library library = ((LibraryOrderEntry)orderEntry).getLibrary();
169             if (library != null) {
170               for (VirtualFile root : ((LibraryEx)library).getExcludedRoots()) {
171                 if (!ensureValid(root, library)) continue;
172
173                 info.excludedFromLibraries.putValue(root, library);
174               }
175               for (VirtualFile root : sourceRoots) {
176                 if (!ensureValid(root, library)) continue;
177
178                 info.sourceOfLibraries.putValue(root, library);
179               }
180               for (VirtualFile root : classRoots) {
181                 if (!ensureValid(root, library)) continue;
182
183                 info.classOfLibraries.putValue(root, library);
184               }
185             }
186           }
187         }
188       }
189     }
190
191     for (AdditionalLibraryRootsProvider provider : Extensions.getExtensions(AdditionalLibraryRootsProvider.EP_NAME)) {
192       Collection<SyntheticLibrary> libraries = provider.getAdditionalProjectLibraries(project);
193       for (SyntheticLibrary descriptor : libraries) {
194         for (VirtualFile root : descriptor.getSourceRoots()) {
195           if (!ensureValid(root, project)) continue;
196
197           info.libraryOrSdkSources.add(root);
198           info.classAndSourceRoots.add(root);
199           info.sourceOfLibraries.putValue(root, descriptor);
200         }
201         for (VirtualFile file : descriptor.getExcludedRoots()) {
202           if (!ensureValid(file, project)) continue;
203           info.excludedFromLibraries.putValue(file, descriptor);
204         }
205       }
206     }
207     for (DirectoryIndexExcludePolicy policy : Extensions.getExtensions(DirectoryIndexExcludePolicy.EP_NAME, project)) {
208       info.excludedFromProject.addAll(ContainerUtil.filter(policy.getExcludeRootsForProject(), file -> ensureValid(file, policy)));
209
210       Function<Sdk, List<VirtualFile>> fun = policy.getExcludeSdkRootsStrategy();
211
212       if (fun != null) {
213         Set<Sdk> sdks = new HashSet<>();
214
215         for (Module m : ModuleManager.getInstance(myProject).getModules()) {
216           Sdk sdk = ModuleRootManager.getInstance(m).getSdk();
217           if (sdk != null) {
218             sdks.add(sdk);
219           }
220         }
221
222         Set<VirtualFile> roots = new HashSet<>();
223
224         for (Sdk sdk: sdks) {
225           roots.addAll(Arrays.asList(sdk.getRootProvider().getFiles(OrderRootType.CLASSES)));
226         }
227
228         for (Sdk sdk: sdks) {
229           info.excludedFromSdkRoots
230             .addAll(ContainerUtil.filter(fun.fun(sdk), file -> ensureValid(file, policy) && !roots.contains(file)));
231         }
232       }
233     }
234     for (UnloadedModuleDescription description : moduleManager.getUnloadedModuleDescriptions()) {
235       for (VirtualFilePointer pointer : description.getContentRoots()) {
236         VirtualFile contentRoot = pointer.getFile();
237         if (contentRoot != null) {
238           info.contentRootOfUnloaded.put(contentRoot, description.getName());
239         }
240       }
241     }
242     return info;
243   }
244
245   private static boolean ensureValid(@NotNull VirtualFile file, @NotNull Object container) {
246     if (!(file instanceof VirtualFileWithId)) {
247       //skip roots from unsupported file systems (e.g. http)
248       return false;
249     }
250     if (!file.isValid()) {
251       LOG.error("Invalid root " + file + " in " + container);
252       return false;
253     }
254     return true;
255   }
256
257   @NotNull
258   private synchronized OrderEntryGraph getOrderEntryGraph() {
259     if (myOrderEntryGraph == null) {
260       RootInfo rootInfo = buildRootInfo(myProject);
261       myOrderEntryGraph = new OrderEntryGraph(myProject, rootInfo);
262     }
263     return myOrderEntryGraph;
264   }
265
266   /**
267    * A reverse dependency graph of (library, jdk, module, module source) -> (module).
268    * <p>
269    * <p>Each edge carries with it the associated OrderEntry that caused the dependency.
270    */
271   private static class OrderEntryGraph {
272
273     private static class Edge {
274       Module myKey;
275       ModuleOrderEntry myOrderEntry; // Order entry from myKey -> the node containing the edge
276       boolean myRecursive; // Whether this edge should be descended into during graph walk
277
278       public Edge(Module key, ModuleOrderEntry orderEntry, boolean recursive) {
279         myKey = key;
280         myOrderEntry = orderEntry;
281         myRecursive = recursive;
282       }
283
284       @Override
285       public String toString() {
286         return myOrderEntry.toString();
287       }
288     }
289
290     private static class Node {
291       Module myKey;
292       List<Edge> myEdges = new ArrayList<>();
293       Set<String> myUnloadedDependentModules;
294
295       @Override
296       public String toString() {
297         return myKey.toString();
298       }
299     }
300
301     private static class Graph {
302       Map<Module, Node> myNodes = new HashMap<>();
303     }
304
305     final Project myProject;
306     final RootInfo myRootInfo;
307     final Set<VirtualFile> myAllRoots;
308     Graph myGraph;
309     MultiMap<VirtualFile, Node> myRoots; // Map of roots to their root nodes, eg. library jar -> library node
310     final SynchronizedSLRUCache<VirtualFile, List<OrderEntry>> myCache;
311     final SynchronizedSLRUCache<Module, Set<String>> myDependentUnloadedModulesCache;
312     private MultiMap<VirtualFile, OrderEntry> myLibClassRootEntries;
313     private MultiMap<VirtualFile, OrderEntry> myLibSourceRootEntries;
314
315     public OrderEntryGraph(Project project, RootInfo rootInfo) {
316       myProject = project;
317       myRootInfo = rootInfo;
318       myAllRoots = myRootInfo.getAllRoots();
319       int cacheSize = Math.max(25, (myAllRoots.size() / 100) * 2);
320       myCache = new SynchronizedSLRUCache<VirtualFile, List<OrderEntry>>(cacheSize, cacheSize) {
321         @NotNull
322         @Override
323         public List<OrderEntry> createValue(VirtualFile key) {
324           return collectOrderEntries(key);
325         }
326       };
327       int dependentUnloadedModulesCacheSize = ModuleManager.getInstance(project).getModules().length / 2;
328       myDependentUnloadedModulesCache =
329         new SynchronizedSLRUCache<Module, Set<String>>(dependentUnloadedModulesCacheSize, dependentUnloadedModulesCacheSize) {
330           @NotNull
331           @Override
332           public Set<String> createValue(Module key) {
333             return collectDependentUnloadedModules(key);
334           }
335         };
336       initGraph();
337       initLibraryRoots();
338     }
339
340     private void initGraph() {
341       Graph graph = new Graph();
342
343       MultiMap<VirtualFile, Node> roots = MultiMap.createSmart();
344
345       ModuleManager moduleManager = ModuleManager.getInstance(myProject);
346       for (final Module module : moduleManager.getModules()) {
347         final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
348         List<OrderEnumerationHandler> handlers = OrderEnumeratorBase.getCustomHandlers(module);
349         for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
350           if (orderEntry instanceof ModuleOrderEntry) {
351             ModuleOrderEntry moduleOrderEntry = (ModuleOrderEntry)orderEntry;
352             final Module depModule = moduleOrderEntry.getModule();
353             if (depModule != null) {
354               Node node = graph.myNodes.get(depModule);
355               OrderEnumerator en = OrderEnumerator.orderEntries(depModule).exportedOnly();
356               if (node == null) {
357                 node = new Node();
358                 node.myKey = depModule;
359                 graph.myNodes.put(depModule, node);
360
361                 VirtualFile[] importedClassRoots = en.classes().usingCache().getRoots();
362                 for (VirtualFile importedClassRoot : importedClassRoots) {
363                   roots.putValue(importedClassRoot, node);
364                 }
365
366                 VirtualFile[] importedSourceRoots = en.sources().usingCache().getRoots();
367                 for (VirtualFile sourceRoot : importedSourceRoots) {
368                   roots.putValue(sourceRoot, node);
369                 }
370               }
371               boolean shouldRecurse = en.recursively().shouldRecurse(moduleOrderEntry, handlers);
372               node.myEdges.add(new Edge(module, moduleOrderEntry, shouldRecurse));
373             }
374           }
375         }
376       }
377       for (UnloadedModuleDescription description : moduleManager.getUnloadedModuleDescriptions()) {
378         for (String depName : description.getDependencyModuleNames()) {
379           Module depModule = moduleManager.findModuleByName(depName);
380           if (depModule != null) {
381             Node node = graph.myNodes.get(depModule);
382             if (node == null) {
383               node = new Node();
384               node.myKey = depModule;
385               graph.myNodes.put(depModule, node);
386             }
387             if (node.myUnloadedDependentModules == null) {
388               node.myUnloadedDependentModules = new LinkedHashSet<>();
389             }
390             node.myUnloadedDependentModules.add(description.getName());
391           }
392         }
393       }
394
395       myGraph = graph;
396       myRoots = roots;
397     }
398
399     private void initLibraryRoots() {
400       MultiMap<VirtualFile, OrderEntry> libClassRootEntries = MultiMap.createSmart();
401       MultiMap<VirtualFile, OrderEntry> libSourceRootEntries = MultiMap.createSmart();
402
403       for (final Module module : ModuleManager.getInstance(myProject).getModules()) {
404         final ModuleRootManager moduleRootManager = ModuleRootManager.getInstance(module);
405         for (OrderEntry orderEntry : moduleRootManager.getOrderEntries()) {
406           if (orderEntry instanceof LibraryOrSdkOrderEntry) {
407             final LibraryOrSdkOrderEntry entry = (LibraryOrSdkOrderEntry)orderEntry;
408             for (final VirtualFile sourceRoot : entry.getRootFiles(OrderRootType.SOURCES)) {
409               libSourceRootEntries.putValue(sourceRoot, orderEntry);
410             }
411             for (final VirtualFile classRoot : entry.getRootFiles(OrderRootType.CLASSES)) {
412               libClassRootEntries.putValue(classRoot, orderEntry);
413             }
414           }
415         }
416       }
417
418       myLibClassRootEntries = libClassRootEntries;
419       myLibSourceRootEntries = libSourceRootEntries;
420     }
421
422     private List<OrderEntry> getOrderEntries(@NotNull VirtualFile file) {
423       return myCache.get(file);
424     }
425
426     /**
427      * Traverses the graph from the given file, collecting all encountered order entries.
428      */
429     private List<OrderEntry> collectOrderEntries(@NotNull VirtualFile file) {
430       List<VirtualFile> roots = getHierarchy(file, myAllRoots, myRootInfo);
431       if (roots == null) {
432         return Collections.emptyList();
433       }
434       List<OrderEntry> result = new ArrayList<>();
435       Stack<Node> stack = new Stack<>();
436       for (VirtualFile root : roots) {
437         Collection<Node> nodes = myRoots.get(root);
438         for (Node node : nodes) {
439           stack.push(node);
440         }
441       }
442
443       Set<Node> seen = new HashSet<>();
444       while (!stack.isEmpty()) {
445         Node node = stack.pop();
446         if (seen.contains(node)) {
447           continue;
448         }
449         seen.add(node);
450
451         for (Edge edge : node.myEdges) {
452           result.add(edge.myOrderEntry);
453
454           if (edge.myRecursive) {
455             Node targetNode = myGraph.myNodes.get(edge.myKey);
456             if (targetNode != null) {
457               stack.push(targetNode);
458             }
459           }
460         }
461       }
462
463       @Nullable Pair<VirtualFile, Collection<Object>> libraryClassRootInfo = myRootInfo.findLibraryRootInfo(roots, false);
464       @Nullable Pair<VirtualFile, Collection<Object>> librarySourceRootInfo = myRootInfo.findLibraryRootInfo(roots, true);
465       result.addAll(myRootInfo.getLibraryOrderEntries(roots,
466                                                       libraryClassRootInfo != null ? libraryClassRootInfo.first : null,
467                                                       librarySourceRootInfo != null ? librarySourceRootInfo.first : null,
468                                                       myLibClassRootEntries, myLibSourceRootEntries));
469
470       VirtualFile moduleContentRoot = myRootInfo.findNearestContentRoot(roots);
471       if (moduleContentRoot != null) {
472         ContainerUtil.addIfNotNull(result, myRootInfo.getModuleSourceEntry(roots, moduleContentRoot, myLibClassRootEntries));
473       }
474       Collections.sort(result, BY_OWNER_MODULE);
475       return result;
476     }
477
478     public Set<String> getDependentUnloadedModules(@NotNull Module module) {
479       return myDependentUnloadedModulesCache.get(module);
480     }
481
482     /**
483      * @return names of unloaded modules which directly or transitively via exported dependencies depend on the specified module
484      */
485     private Set<String> collectDependentUnloadedModules(@NotNull Module module) {
486       ArrayDeque<OrderEntryGraph.Node> stack = new ArrayDeque<>();
487       Node start = myGraph.myNodes.get(module);
488       if (start == null) return Collections.emptySet();
489       stack.push(start);
490       Set<Node> seen = new HashSet<>();
491       Set<String> result = null;
492       while (!stack.isEmpty()) {
493         Node node = stack.pop();
494         if (!seen.add(node)) {
495           continue;
496         }
497         if (node.myUnloadedDependentModules != null) {
498           if (result == null) {
499             result = new LinkedHashSet<>(node.myUnloadedDependentModules);
500           }
501           else {
502             result.addAll(node.myUnloadedDependentModules);
503           }
504         }
505         for (Edge edge : node.myEdges) {
506           if (edge.myRecursive) {
507             Node targetNode = myGraph.myNodes.get(edge.myKey);
508             if (targetNode != null) {
509               stack.push(targetNode);
510             }
511           }
512         }
513       }
514       return result != null ? result : Collections.emptySet();
515     }
516   }
517
518
519   private int getRootTypeId(@NotNull JpsModuleSourceRootType<?> rootType) {
520     if (myRootTypeId.containsKey(rootType)) {
521       return myRootTypeId.get(rootType);
522     }
523
524     int id = myRootTypes.size();
525     if (id > DirectoryInfoImpl.MAX_ROOT_TYPE_ID) {
526       LOG.error("Too many different types of module source roots (" + id + ") registered: " + myRootTypes);
527     }
528     myRootTypes.add(rootType);
529     myRootTypeId.put(rootType, id);
530     return id;
531   }
532
533   @NotNull
534   public DirectoryInfo getInfoForFile(@NotNull VirtualFile file) {
535     if (!file.isValid()) {
536       return NonProjectDirectoryInfo.INVALID;
537     }
538     VirtualFile dir;
539     if (!file.isDirectory()) {
540       DirectoryInfo info = myInfoCache.getCachedInfo(file);
541       if (info != null) {
542         return info;
543       }
544       if (ourFileTypes.isFileIgnored(file)) {
545         return NonProjectDirectoryInfo.IGNORED;
546       }
547       dir = file.getParent();
548     }
549     else {
550       dir = file;
551     }
552
553     int count = 0;
554     for (VirtualFile root = dir; root != null; root = root.getParent()) {
555       if (++count > 1000) {
556         throw new IllegalStateException("Possible loop in tree, started at " + dir.getName());
557       }
558       DirectoryInfo info = myInfoCache.getCachedInfo(root);
559       if (info != null) {
560         if (!dir.equals(root)) {
561           cacheInfos(dir, root, info);
562         }
563         return info;
564       }
565
566       if (ourFileTypes.isFileIgnored(root)) {
567         return cacheInfos(dir, root, NonProjectDirectoryInfo.IGNORED);
568       }
569     }
570
571     return cacheInfos(dir, null, NonProjectDirectoryInfo.NOT_UNDER_PROJECT_ROOTS);
572   }
573
574   @NotNull
575   private DirectoryInfo cacheInfos(VirtualFile dir, @Nullable VirtualFile stopAt, @NotNull DirectoryInfo info) {
576     while (dir != null) {
577       myInfoCache.cacheInfo(dir, info);
578       if (dir.equals(stopAt)) {
579         break;
580       }
581       dir = dir.getParent();
582     }
583     return info;
584   }
585
586   @NotNull
587   public Query<VirtualFile> getDirectoriesByPackageName(@NotNull final String packageName, final boolean includeLibrarySources) {
588     // Note that this method is used in upsource as well, hence, don't reduce this method's visibility.
589     List<VirtualFile> result = myPackageDirectoryCache.getDirectoriesByPackageName(packageName);
590     if (!includeLibrarySources) {
591       result = ContainerUtil.filter(result, file -> {
592         DirectoryInfo info = getInfoForFile(file);
593         return info.isInProject(file) && (!info.isInLibrarySource(file) || info.isInModuleSource(file) || info.hasLibraryClassRoot());
594       });
595     }
596     return new CollectionQuery<>(result);
597   }
598
599   @Nullable
600   public String getPackageName(@NotNull final VirtualFile dir) {
601     if (dir.isDirectory()) {
602       if (ourFileTypes.isFileIgnored(dir)) {
603         return null;
604       }
605
606       if (myPackagePrefixByRoot.containsKey(dir)) {
607         return myPackagePrefixByRoot.get(dir);
608       }
609
610       final VirtualFile parent = dir.getParent();
611       if (parent != null) {
612         return getPackageNameForSubdir(getPackageName(parent), dir.getName());
613       }
614     }
615
616     return null;
617   }
618
619   @Nullable
620   protected static String getPackageNameForSubdir(@Nullable String parentPackageName, @NotNull String subdirName) {
621     if (parentPackageName == null) return null;
622     return parentPackageName.isEmpty() ? subdirName : parentPackageName + "." + subdirName;
623   }
624
625   @Nullable
626   public JpsModuleSourceRootType<?> getSourceRootType(@NotNull DirectoryInfo directoryInfo) {
627     return myRootTypes.get(directoryInfo.getSourceRootTypeId());
628   }
629
630   boolean resetOnEvents(@NotNull List<? extends VFileEvent> events) {
631     for (VFileEvent event : events) {
632       VirtualFile file = event.getFile();
633       if (file == null || file.isDirectory()) {
634         return true;
635       }
636     }
637     return false;
638   }
639
640   @Nullable("returns null only if dir is under ignored folder")
641   private static List<VirtualFile> getHierarchy(VirtualFile dir, @NotNull Set<VirtualFile> allRoots, @NotNull RootInfo info) {
642     List<VirtualFile> hierarchy = ContainerUtil.newArrayList();
643     boolean hasContentRoots = false;
644     while (dir != null) {
645       hasContentRoots |= info.contentRootOf.get(dir) != null;
646       if (!hasContentRoots && ourFileTypes.isFileIgnored(dir)) {
647         return null;
648       }
649       if (allRoots.contains(dir)) {
650         hierarchy.add(dir);
651       }
652       dir = dir.getParent();
653     }
654     return hierarchy;
655   }
656
657   private static class RootInfo {
658     // getDirectoriesByPackageName used to be in this order, some clients might rely on that
659     @NotNull final LinkedHashSet<VirtualFile> classAndSourceRoots = ContainerUtil.newLinkedHashSet();
660
661     @NotNull final Set<VirtualFile> libraryOrSdkSources = ContainerUtil.newHashSet();
662     @NotNull final Set<VirtualFile> libraryOrSdkClasses = ContainerUtil.newHashSet();
663     @NotNull final Map<VirtualFile, Module> contentRootOf = ContainerUtil.newHashMap();
664     @NotNull final Map<VirtualFile, String> contentRootOfUnloaded = ContainerUtil.newHashMap();
665     @NotNull final MultiMap<VirtualFile, Module> sourceRootOf = MultiMap.createSet();
666     @NotNull final TObjectIntHashMap<VirtualFile> rootTypeId = new TObjectIntHashMap<>();
667     @NotNull final MultiMap<VirtualFile, /*Library|SyntheticLibrary*/ Object> excludedFromLibraries = MultiMap.createSmart();
668     @NotNull final MultiMap<VirtualFile, Library> classOfLibraries = MultiMap.createSmart();
669     @NotNull final MultiMap<VirtualFile, /*Library|SyntheticLibrary*/ Object> sourceOfLibraries = MultiMap.createSmart();
670     @NotNull final Set<VirtualFile> excludedFromProject = ContainerUtil.newHashSet();
671     @NotNull final Set<VirtualFile> excludedFromSdkRoots = ContainerUtil.newHashSet();
672     @NotNull final Map<VirtualFile, Module> excludedFromModule = ContainerUtil.newHashMap();
673     @NotNull final Map<VirtualFile, FileTypeAssocTable<Boolean>> excludeFromContentRootTables = ContainerUtil.newHashMap();
674     @NotNull final Map<VirtualFile, String> packagePrefix = ContainerUtil.newHashMap();
675
676     @NotNull
677     Set<VirtualFile> getAllRoots() {
678       LinkedHashSet<VirtualFile> result = ContainerUtil.newLinkedHashSet();
679       result.addAll(classAndSourceRoots);
680       result.addAll(contentRootOf.keySet());
681       result.addAll(contentRootOfUnloaded.keySet());
682       result.addAll(excludedFromLibraries.keySet());
683       result.addAll(excludedFromModule.keySet());
684       result.addAll(excludedFromProject);
685       result.addAll(excludedFromSdkRoots);
686       return result;
687     }
688
689     /**
690      * Returns nearest content root for a file by its parent directories hierarchy. If the file is excluded (i.e. located under an excluded
691      * root and there are no source roots on the path to the excluded root) returns {@code null}.
692      */
693     @Nullable
694     private VirtualFile findNearestContentRoot(@NotNull List<VirtualFile> hierarchy) {
695       Collection<Module> sourceRootOwners = null;
696       boolean underExcludedSourceRoot = false;
697       for (VirtualFile root : hierarchy) {
698         Module module = contentRootOf.get(root);
699         Module excludedFrom = excludedFromModule.get(root);
700         if (module != null) {
701           FileTypeAssocTable<Boolean> table = excludeFromContentRootTables.get(root);
702           if (table != null && isExcludedByPattern(root, hierarchy, table)) {
703             excludedFrom = module;
704           }
705         }
706         if (module != null && (excludedFrom != module || underExcludedSourceRoot && sourceRootOwners.contains(module))) {
707           return root;
708         }
709         if (excludedFrom != null || excludedFromProject.contains(root) || contentRootOfUnloaded.containsKey(root)) {
710           if (sourceRootOwners != null) {
711             underExcludedSourceRoot = true;
712           }
713           else {
714             return null;
715           }
716         }
717
718         if (!underExcludedSourceRoot && sourceRootOf.containsKey(root)) {
719           Collection<Module> modulesForSourceRoot = sourceRootOf.get(root);
720           if (!modulesForSourceRoot.isEmpty()) {
721             if (sourceRootOwners == null) {
722               sourceRootOwners = modulesForSourceRoot;
723             }
724             else {
725               sourceRootOwners = ContainerUtil.union(sourceRootOwners, modulesForSourceRoot);
726             }
727           }
728         }
729       }
730       return null;
731     }
732
733     private static boolean isExcludedByPattern(VirtualFile contentRoot, List<VirtualFile> hierarchy, FileTypeAssocTable<Boolean> table) {
734       for (VirtualFile file : hierarchy) {
735         if (table.findAssociatedFileType(file.getNameSequence()) != null) {
736           return true;
737         }
738         if (file.equals(contentRoot)) {
739           break;
740         }
741       }
742       return false;
743     }
744
745     @Nullable
746     private VirtualFile findNearestContentRootForExcluded(@NotNull List<VirtualFile> hierarchy) {
747       for (VirtualFile root : hierarchy) {
748         if (contentRootOf.containsKey(root) || contentRootOfUnloaded.containsKey(root)) {
749           return root;
750         }
751       }
752       return null;
753     }
754
755     /**
756      * @return root and set of libraries that provided it
757      */
758     @Nullable
759     private Pair<VirtualFile, Collection<Object>> findLibraryRootInfo(@NotNull List<VirtualFile> hierarchy, boolean source) {
760       Set<Object> librariesToIgnore = ContainerUtil.newHashSet();
761       for (VirtualFile root : hierarchy) {
762         librariesToIgnore.addAll(excludedFromLibraries.get(root));
763         if (source && libraryOrSdkSources.contains(root)) {
764           if (!sourceOfLibraries.containsKey(root)) {
765             return Pair.create(root, Collections.emptySet());
766           }
767           Collection<Object> rootProducers = findLibrarySourceRootProducers(librariesToIgnore, root);
768           if (!rootProducers.isEmpty()) {
769             return Pair.create(root, rootProducers);
770           }
771         }
772         else if (!source && libraryOrSdkClasses.contains(root)) {
773           if (!classOfLibraries.containsKey(root)) {
774             return Pair.create(root, Collections.emptySet());
775           }
776           Collection<Object> rootProducers = findLibraryClassRootProducers(librariesToIgnore, root);
777           if (!rootProducers.isEmpty()) {
778             return Pair.create(root, rootProducers);
779           }
780         }
781       }
782       return null;
783     }
784
785     @NotNull
786     private Collection<Object> findLibraryClassRootProducers(Set<Object> librariesToIgnore, VirtualFile root) {
787       Set<Object> libraries = ContainerUtil.newHashSet(classOfLibraries.get(root));
788       libraries.removeAll(librariesToIgnore);
789       return libraries;
790     }
791
792     @NotNull
793     private Collection<Object> findLibrarySourceRootProducers(Set<Object> librariesToIgnore, VirtualFile root) {
794       Set<Object> libraries = ContainerUtil.newHashSet();
795       for (Object library : sourceOfLibraries.get(root)) {
796         if (librariesToIgnore.contains(library)) continue;
797         if (library instanceof SyntheticLibrary) {
798           Condition<VirtualFile> exclusion = ((SyntheticLibrary)library).getExcludeFileCondition();
799           if (exclusion != null && exclusion.value(root)) {
800             continue;
801           }
802         }
803         libraries.add(library);
804       }
805       return libraries;
806     }
807
808     private String calcPackagePrefix(@NotNull VirtualFile root,
809                                      @NotNull List<VirtualFile> hierarchy,
810                                      VirtualFile moduleContentRoot,
811                                      VirtualFile libraryClassRoot,
812                                      VirtualFile librarySourceRoot) {
813       VirtualFile packageRoot = findPackageRootInfo(hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
814       String prefix = packagePrefix.get(packageRoot);
815       if (prefix != null && !root.equals(packageRoot)) {
816         assert packageRoot != null;
817         String relative = VfsUtilCore.getRelativePath(root, packageRoot, '.');
818         prefix = StringUtil.isEmpty(prefix) ? relative : prefix + '.' + relative;
819       }
820       return prefix;
821     }
822
823     @Nullable
824     private VirtualFile findPackageRootInfo(@NotNull List<VirtualFile> hierarchy,
825                                             VirtualFile moduleContentRoot,
826                                             VirtualFile libraryClassRoot,
827                                             VirtualFile librarySourceRoot) {
828       for (VirtualFile root : hierarchy) {
829         if (moduleContentRoot != null &&
830             sourceRootOf.get(root).contains(contentRootOf.get(moduleContentRoot)) &&
831             librarySourceRoot == null) {
832           return root;
833         }
834         if (root.equals(libraryClassRoot) || root.equals(librarySourceRoot)) {
835           return root;
836         }
837         if (root.equals(moduleContentRoot) && !sourceRootOf.containsKey(root) && librarySourceRoot == null && libraryClassRoot == null) {
838           return null;
839         }
840       }
841       return null;
842     }
843
844     @NotNull
845     private LinkedHashSet<OrderEntry> getLibraryOrderEntries(@NotNull List<VirtualFile> hierarchy,
846                                                              @Nullable VirtualFile libraryClassRoot,
847                                                              @Nullable VirtualFile librarySourceRoot,
848                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries,
849                                                              @NotNull MultiMap<VirtualFile, OrderEntry> libSourceRootEntries) {
850       LinkedHashSet<OrderEntry> orderEntries = ContainerUtil.newLinkedHashSet();
851       for (VirtualFile root : hierarchy) {
852         if (root.equals(libraryClassRoot) && !sourceRootOf.containsKey(root)) {
853           orderEntries.addAll(libClassRootEntries.get(root));
854         }
855         if (root.equals(librarySourceRoot) && libraryClassRoot == null) {
856           orderEntries.addAll(libSourceRootEntries.get(root));
857         }
858         if (libClassRootEntries.containsKey(root) || sourceRootOf.containsKey(root) && librarySourceRoot == null) {
859           break;
860         }
861       }
862       return orderEntries;
863     }
864
865
866     @Nullable
867     private ModuleSourceOrderEntry getModuleSourceEntry(@NotNull List<VirtualFile> hierarchy,
868                                                         @NotNull VirtualFile moduleContentRoot,
869                                                         @NotNull MultiMap<VirtualFile, OrderEntry> libClassRootEntries) {
870       Module module = contentRootOf.get(moduleContentRoot);
871       for (VirtualFile root : hierarchy) {
872         if (sourceRootOf.get(root).contains(module)) {
873           return ContainerUtil.findInstance(ModuleRootManager.getInstance(module).getOrderEntries(), ModuleSourceOrderEntry.class);
874         }
875         if (libClassRootEntries.containsKey(root)) {
876           return null;
877         }
878       }
879       return null;
880     }
881   }
882
883   @NotNull
884   private static Pair<DirectoryInfo, String> calcDirectoryInfo(@NotNull final VirtualFile root,
885                                                                @NotNull final List<VirtualFile> hierarchy,
886                                                                @NotNull RootInfo info) {
887     VirtualFile moduleContentRoot = info.findNearestContentRoot(hierarchy);
888     Pair<VirtualFile, Collection<Object>> librarySourceRootInfo = info.findLibraryRootInfo(hierarchy, true);
889     VirtualFile librarySourceRoot = librarySourceRootInfo != null ? librarySourceRootInfo.first : null;
890
891     Pair<VirtualFile, Collection<Object>> libraryClassRootInfo = info.findLibraryRootInfo(hierarchy, false);
892     VirtualFile libraryClassRoot = libraryClassRootInfo != null ? libraryClassRootInfo.first : null;
893
894     boolean inProject = moduleContentRoot != null ||
895                         ((libraryClassRoot != null || librarySourceRoot != null) && !info.excludedFromSdkRoots.contains(root));
896
897     VirtualFile nearestContentRoot;
898     if (inProject) {
899       nearestContentRoot = moduleContentRoot;
900     }
901     else {
902       nearestContentRoot = info.findNearestContentRootForExcluded(hierarchy);
903       if (nearestContentRoot == null) {
904         return new Pair<>(NonProjectDirectoryInfo.EXCLUDED, null);
905       }
906     }
907
908     VirtualFile sourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, librarySourceRoot);
909
910     VirtualFile moduleSourceRoot = info.findPackageRootInfo(hierarchy, moduleContentRoot, null, null);
911     boolean inModuleSources = moduleSourceRoot != null;
912     boolean inLibrarySource = librarySourceRoot != null;
913     int typeId = moduleSourceRoot != null ? info.rootTypeId.get(moduleSourceRoot) : 0;
914
915     Module module = info.contentRootOf.get(nearestContentRoot);
916     String unloadedModuleName = info.contentRootOfUnloaded.get(nearestContentRoot);
917     FileTypeAssocTable<Boolean> contentExcludePatterns =
918       moduleContentRoot != null ? info.excludeFromContentRootTables.get(moduleContentRoot) : null;
919     Condition<VirtualFile> libraryExclusionPredicate = getLibraryExclusionPredicate(librarySourceRootInfo);
920
921     DirectoryInfo directoryInfo = contentExcludePatterns != null || libraryExclusionPredicate != null
922                                   ? new DirectoryInfoWithExcludePatterns(root, module, nearestContentRoot, sourceRoot, libraryClassRoot,
923                                                                          inModuleSources, inLibrarySource, !inProject, typeId,
924                                                                          contentExcludePatterns, libraryExclusionPredicate, unloadedModuleName)
925                                   : new DirectoryInfoImpl(root, module, nearestContentRoot, sourceRoot, libraryClassRoot, inModuleSources,
926                                                           inLibrarySource, !inProject, typeId, unloadedModuleName);
927
928     String packagePrefix = info.calcPackagePrefix(root, hierarchy, moduleContentRoot, libraryClassRoot, librarySourceRoot);
929
930     return Pair.create(directoryInfo, packagePrefix);
931   }
932
933   @Nullable
934   private static Condition<VirtualFile> getLibraryExclusionPredicate(@Nullable Pair<VirtualFile, Collection<Object>> libraryRootInfo) {
935     Condition<VirtualFile> result = Conditions.alwaysFalse();
936     if (libraryRootInfo != null) {
937       for (Object library : libraryRootInfo.second) {
938         Condition<VirtualFile> exclusionPredicate =
939           library instanceof SyntheticLibrary ? ((SyntheticLibrary)library).getExcludeFileCondition() : null;
940         if (exclusionPredicate == null) continue;
941         result = Conditions.or(result, exclusionPredicate);
942       }
943     }
944     return result != Condition.FALSE ? result : null;
945   }
946
947   @NotNull
948   public List<OrderEntry> getOrderEntries(@NotNull DirectoryInfo info) {
949     if (!(info instanceof DirectoryInfoImpl)) return Collections.emptyList();
950     return getOrderEntryGraph().getOrderEntries(((DirectoryInfoImpl)info).getRoot());
951   }
952
953   @NotNull
954   public Set<String> getDependentUnloadedModules(@NotNull Module module) {
955     return getOrderEntryGraph().getDependentUnloadedModules(module);
956   }
957
958   public interface InfoCache {
959     @Nullable
960     DirectoryInfo getCachedInfo(@NotNull VirtualFile dir);
961
962     void cacheInfo(@NotNull VirtualFile dir, @NotNull DirectoryInfo info);
963   }
964
965   /**
966    * An LRU cache with synchronization around the primary cache operations (get() and insertion
967    * of a newly created value). Other map operations are not synchronized.
968    */
969   abstract static class SynchronizedSLRUCache<K, V> extends SLRUMap<K, V> {
970     protected final Object myLock = new Object();
971
972     protected SynchronizedSLRUCache(final int protectedQueueSize, final int probationalQueueSize) {
973       super(protectedQueueSize, probationalQueueSize);
974     }
975
976     @NotNull
977     public abstract V createValue(K key);
978
979     @Override
980     @NotNull
981     public V get(K key) {
982       V value;
983       synchronized (myLock) {
984         value = super.get(key);
985         if (value != null) {
986           return value;
987         }
988       }
989       value = createValue(key);
990       synchronized (myLock) {
991         put(key, value);
992       }
993       return value;
994     }
995   }
996 }