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