platform/lang-impl/src/com/intellij/openapi/roots/impl/DirectoryIndexImpl.java

   1 /*
   2  * Copyright 2000-2009 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
  17 package com.intellij.openapi.roots.impl;
  18
  19 import com.intellij.AppTopics;
  20 import com.intellij.ProjectTopics;
  21 import com.intellij.ide.startup.StartupManagerEx;
  22 import com.intellij.openapi.components.ProjectComponent;
  23 import com.intellij.openapi.diagnostic.Logger;
  24 import com.intellij.openapi.extensions.Extensions;
  25 import com.intellij.openapi.fileTypes.FileTypeEvent;
  26 import com.intellij.openapi.fileTypes.FileTypeListener;
  27 import com.intellij.openapi.fileTypes.FileTypeManager;
  28 import com.intellij.openapi.module.Module;
  29 import com.intellij.openapi.module.ModuleManager;
  30 import com.intellij.openapi.progress.EmptyProgressIndicator;
  31 import com.intellij.openapi.progress.ProgressIndicator;
  32 import com.intellij.openapi.progress.ProgressManager;
  33 import com.intellij.openapi.project.Project;
  34 import com.intellij.openapi.project.ProjectBundle;
  35 import com.intellij.openapi.roots.*;
  36 import com.intellij.openapi.startup.StartupManager;
  37 import com.intellij.openapi.util.Condition;
  38 import com.intellij.openapi.util.Key;
  39 import com.intellij.openapi.vfs.*;
  40 import com.intellij.openapi.vfs.impl.BulkVirtualFileListenerAdapter;
  41 import com.intellij.openapi.vfs.newvfs.NewVirtualFile;
  42 import com.intellij.psi.impl.PsiManagerConfiguration;
  43 import com.intellij.util.*;
  44 import com.intellij.util.containers.*;
  45 import com.intellij.util.containers.HashMap;
  46 import com.intellij.util.messages.MessageBusConnection;
  47 import gnu.trove.THashMap;
  48 import org.jetbrains.annotations.NotNull;
  49 import org.jetbrains.annotations.Nullable;
  50 import org.jetbrains.annotations.TestOnly;
  51
  52 import java.util.*;
  53 import java.util.HashSet;
  54
  55 public class DirectoryIndexImpl extends DirectoryIndex implements ProjectComponent {
  56   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.roots.impl.DirectoryIndexImpl");
  57
  58   private final Project myProject;
  59
  60   private volatile boolean myInitialized = false;
  61   private volatile boolean myDisposed = false;
  62
  63   private final boolean myIsLasyMode;
  64
  65   private Map<VirtualFile, Set<String>> myExcludeRootsMap;
  66   private Set<VirtualFile> myProjectExcludeRoots;
  67   private Map<VirtualFile, DirectoryInfo> myDirToInfoMap = new ConcurrentHashMap<VirtualFile, DirectoryInfo>();
  68   private Map<String, VirtualFile[]> myPackageNameToDirsMap = new ConcurrentHashMap<String, VirtualFile[]>();
  69
  70   private final DirectoryIndexExcludePolicy[] myExcludePolicies;
  71   private final MessageBusConnection myConnection;
  72
  73   public DirectoryIndexImpl(Project project, PsiManagerConfiguration psiManagerConfiguration, StartupManager startupManager) {
  74     myProject = project;
  75     myConnection = project.getMessageBus().connect(project);
  76
  77     myIsLasyMode = !psiManagerConfiguration.REPOSITORY_ENABLED;
  78     ((StartupManagerEx)startupManager).registerPreStartupActivity(new Runnable() {
  79       public void run() {
  80         initialize();
  81       }
  82     });
  83     myExcludePolicies = Extensions.getExtensions(DirectoryIndexExcludePolicy.EP_NAME, myProject);
  84   }
  85
  86   @NotNull
  87   public String getComponentName() {
  88     return "DirectoryIndex";
  89   }
  90
  91   public void initComponent() {
  92   }
  93
  94   public void disposeComponent() {
  95     myDisposed = true;
  96   }
  97
  98   public void projectOpened() {
  99   }
 100
 101   public void projectClosed() {
 102   }
 103
 104   @TestOnly
 105   public void checkConsistency() {
 106     doCheckConsistency(false);
 107     doCheckConsistency(true);
 108   }
 109
 110   @TestOnly
 111   private void doCheckConsistency(boolean reverseAllSets) {
 112     assert myInitialized;
 113     assert !myDisposed;
 114
 115     Map<VirtualFile, DirectoryInfo> oldDirToInfoMap = myDirToInfoMap;
 116     myDirToInfoMap = new THashMap<VirtualFile, DirectoryInfo>();
 117
 118     Map<String, VirtualFile[]> oldPackageNameToDirsMap = myPackageNameToDirsMap;
 119     myPackageNameToDirsMap = new THashMap<String, VirtualFile[]>();
 120
 121     doInitialize(reverseAllSets, null);
 122
 123     if (myIsLasyMode) {
 124       Map<VirtualFile, DirectoryInfo> newDirToInfoMap = myDirToInfoMap;
 125       Map<String, VirtualFile[]> newPackageNameToDirsMap = myPackageNameToDirsMap;
 126       myDirToInfoMap = oldDirToInfoMap;
 127       myPackageNameToDirsMap = oldPackageNameToDirsMap;
 128
 129       Set<VirtualFile> allDirsSet = newDirToInfoMap.keySet();
 130       for (VirtualFile dir : allDirsSet) {
 131         getInfoForDirectory(dir);
 132       }
 133
 134       myDirToInfoMap = newDirToInfoMap;
 135       myPackageNameToDirsMap = newPackageNameToDirsMap;
 136     }
 137
 138     Set<VirtualFile> keySet = myDirToInfoMap.keySet();
 139     assert keySet.size() == oldDirToInfoMap.keySet().size();
 140     for (VirtualFile file : keySet) {
 141       DirectoryInfo info1 = myDirToInfoMap.get(file);
 142       DirectoryInfo info2 = oldDirToInfoMap.get(file);
 143       assert info1.equals(info2);
 144     }
 145
 146     assert myPackageNameToDirsMap.keySet().size() == oldPackageNameToDirsMap.keySet().size();
 147     for (Map.Entry<String, VirtualFile[]> entry : myPackageNameToDirsMap.entrySet()) {
 148       String packageName = entry.getKey();
 149       VirtualFile[] dirs = entry.getValue();
 150       VirtualFile[] dirs1 = oldPackageNameToDirsMap.get(packageName);
 151
 152       HashSet<VirtualFile> set1 = new HashSet<VirtualFile>();
 153       set1.addAll(Arrays.asList(dirs));
 154       HashSet<VirtualFile> set2 = new HashSet<VirtualFile>();
 155       set2.addAll(Arrays.asList(dirs1));
 156       assert set1.equals(set2);
 157     }
 158   }
 159
 160   public boolean isInitialized() {
 161     return myInitialized;
 162   }
 163
 164   public void initialize() {
 165     if (myInitialized) {
 166       LOG.error("Directory index is already initialized.");
 167       return;
 168     }
 169
 170     if (myDisposed) {
 171       LOG.error("Directory index is aleady disposed for this project");
 172       return;
 173     }
 174
 175     myInitialized = true;
 176
 177     subscribeToFileChanges();
 178     doInitialize();
 179   }
 180
 181   private void subscribeToFileChanges() {
 182     myConnection.subscribe(AppTopics.FILE_TYPES, new FileTypeListener() {
 183       public void beforeFileTypesChanged(FileTypeEvent event) {
 184       }
 185
 186       public void fileTypesChanged(FileTypeEvent event) {
 187         doInitialize();
 188       }
 189     });
 190
 191     myConnection.subscribe(ProjectTopics.PROJECT_ROOTS, new ModuleRootListener() {
 192       public void beforeRootsChange(ModuleRootEvent event) {
 193       }
 194
 195       public void rootsChanged(ModuleRootEvent event) {
 196         doInitialize();
 197       }
 198     });
 199
 200     myConnection.subscribe(VirtualFileManager.VFS_CHANGES, new BulkVirtualFileListenerAdapter(new MyVirtualFileListener()));
 201   }
 202
 203   private void doInitialize() {
 204     if (myIsLasyMode) {
 205       cleapAllMaps();
 206     }
 207     else {
 208       doInitialize(false, null);
 209     }
 210   }
 211
 212   private void doInitialize(boolean reverseAllSets/* for testing order independence*/, VirtualFile forDir/* in LAZY_MODE only*/) {
 213     ProgressIndicator progress = ProgressManager.getInstance().getProgressIndicator();
 214     if (progress == null) progress = new EmptyProgressIndicator();
 215
 216     progress.pushState();
 217
 218     progress.checkCanceled();
 219     progress.setText(ProjectBundle.message("project.index.scanning.files.progress"));
 220
 221     if (forDir == null) cleapAllMaps();
 222     else createMapsFor(forDir);
 223
 224     Module[] modules = ModuleManager.getInstance(myProject).getModules();
 225     if (reverseAllSets) modules = ArrayUtil.reverseArray(modules);
 226
 227     initExcludedDirMap(modules, progress);
 228
 229     for (Module module : modules) {
 230       initModuleContents(module, forDir, reverseAllSets, progress);
 231       initModuleSources(module, forDir, reverseAllSets, progress);
 232       initLibrarySources(module, forDir, progress);
 233       initLibraryClasses(module, forDir, progress);
 234     }
 235
 236     progress.checkCanceled();
 237     progress.setText2("");
 238
 239     for (Module module : modules) {
 240       initOrderEntries(module, forDir);
 241     }
 242
 243     progress.popState();
 244   }
 245
 246   private void cleapAllMaps() {
 247     myDirToInfoMap.clear();
 248     myPackageNameToDirsMap.clear();
 249   }
 250
 251   private void createMapsFor(VirtualFile forDir) {
 252     // clear map for all ancestors to not interfer with previous results
 253     VirtualFile dir = forDir;
 254     do {
 255       myDirToInfoMap.remove(dir);
 256       dir = dir.getParent();
 257     }
 258     while (dir != null);
 259   }
 260
 261   private void initExcludedDirMap(Module[] modules, ProgressIndicator progress) {
 262     progress.checkCanceled();
 263     progress.setText2(ProjectBundle.message("project.index.building.exclude.roots.progress"));
 264
 265     // exclude roots should be merged to prevent including excluded dirs of an inner module into the outer
 266     // exclude root should exclude from its content root and all outer content roots
 267     Map<VirtualFile, Set<String>> result = new THashMap<VirtualFile, Set<String>>();
 268     Set<VirtualFile> projectExcludeRoots = new HashSet<VirtualFile>();
 269
 270     for (Module module : modules) {
 271       for (ContentEntry contentEntry : getContentEntries(module)) {
 272         VirtualFile contentRoot = contentEntry.getFile();
 273         if (contentRoot == null) continue;
 274
 275         ExcludeFolder[] excludeRoots = contentEntry.getExcludeFolders();
 276         for (ExcludeFolder excludeRoot : excludeRoots) {
 277           // Output paths should be excluded (if marked as such) regardless if they're under corresponding module's content root
 278           if (excludeRoot.getFile() != null) {
 279             if (!contentRoot.getUrl().startsWith(excludeRoot.getUrl())) {
 280               if (isExcludeRootForModule(module, excludeRoot.getFile())) {
 281                 putForFileAndAllAncestors(result, excludeRoot.getFile(), excludeRoot.getUrl());
 282               }
 283             }
 284           }
 285
 286           putForFileAndAllAncestors(result, contentRoot, excludeRoot.getUrl());
 287         }
 288       }
 289     }
 290
 291     for(DirectoryIndexExcludePolicy policy: myExcludePolicies) {
 292       for(VirtualFile file: policy.getExcludeRootsForProject()) {
 293         putForFileAndAllAncestors(result, file, file.getUrl());
 294         projectExcludeRoots.add(file);
 295       }
 296     }
 297
 298     myExcludeRootsMap = result;
 299     myProjectExcludeRoots = projectExcludeRoots;
 300   }
 301
 302   private static void putForFileAndAllAncestors(Map<VirtualFile, Set<String>> map, VirtualFile file, String value) {
 303     while (true) {
 304       Set<String> set = map.get(file);
 305       if (set == null) {
 306         set = new HashSet<String>();
 307         map.put(file, set);
 308       }
 309       set.add(value);
 310
 311       file = file.getParent();
 312       if (file == null) break;
 313     }
 314   }
 315
 316   private boolean isExcludeRootForModule(Module module, VirtualFile excludeRoot) {
 317     for(DirectoryIndexExcludePolicy policy: myExcludePolicies) {
 318       if (policy.isExcludeRootForModule(module, excludeRoot)) return true;
 319     }
 320     return false;
 321   }
 322
 323   private static ContentEntry[] getContentEntries(Module module) {
 324     return ModuleRootManager.getInstance(module).getContentEntries();
 325   }
 326
 327   private static OrderEntry[] getOrderEntries(Module module) {
 328     return ModuleRootManager.getInstance(module).getOrderEntries();
 329   }
 330
 331   private void initModuleContents(Module module,
 332                                   VirtualFile forDir,
 333                                   boolean reverseAllSets,
 334                                   ProgressIndicator progress) {
 335     progress.checkCanceled();
 336     progress.setText2(ProjectBundle.message("project.index.processing.module.content.progress", module.getName()));
 337
 338     ModuleRootManager rootManager = ModuleRootManager.getInstance(module);
 339     VirtualFile[] contentRoots = rootManager.getContentRoots();
 340     if (reverseAllSets) {
 341       contentRoots = ArrayUtil.reverseArray(contentRoots);
 342     }
 343
 344     for (final VirtualFile contentRoot : contentRoots) {
 345       fillMapWithModuleContent(contentRoot, module, contentRoot, forDir);
 346     }
 347   }
 348
 349   private void fillMapWithModuleContent(VirtualFile dir,
 350                                         Module module,
 351                                         VirtualFile contentRoot,
 352                                         VirtualFile forDir) {
 353     if (isExcluded(contentRoot, dir)) return;
 354     if (isIgnored(dir)) return;
 355
 356     if (forDir != null) {
 357       if (!VfsUtil.isAncestor(dir, forDir, false)) return;
 358     }
 359
 360     DirectoryInfo info = getOrCreateDirInfo(dir);
 361
 362     if (info.module != null) { // module contents overlap
 363       DirectoryInfo parentInfo = myDirToInfoMap.get(dir.getParent());
 364       if (parentInfo == null || !info.module.equals(parentInfo.module)) return; // content of another module is below this module's content
 365     }
 366
 367     VirtualFile[] children = dir.getChildren();
 368     for (VirtualFile child : children) {
 369       if (child.isDirectory()) {
 370         fillMapWithModuleContent(child, module, contentRoot, forDir);
 371       }
 372     }
 373
 374     // important to change module AFTER processing children - to handle overlapping modules
 375     info.module = module;
 376     info.contentRoot = contentRoot;
 377   }
 378
 379   private boolean isExcluded(VirtualFile root, VirtualFile dir) {
 380     Set<String> excludes = myExcludeRootsMap.get(root);
 381     return excludes != null && excludes.contains(dir.getUrl());
 382   }
 383
 384   private void initModuleSources(Module module,
 385                                  VirtualFile forDir,
 386                                  boolean reverseAllSets,
 387                                  ProgressIndicator progress) {
 388     progress.checkCanceled();
 389     progress.setText2(ProjectBundle.message("project.index.processing.module.sources.progress", module.getName()));
 390
 391     ContentEntry[] contentEntries = getContentEntries(module);
 392
 393     if (reverseAllSets) {
 394       contentEntries = ArrayUtil.reverseArray(contentEntries);
 395     }
 396
 397     for (ContentEntry contentEntry : contentEntries) {
 398       SourceFolder[] sourceFolders = contentEntry.getSourceFolders();
 399       if (reverseAllSets) {
 400         sourceFolders = ArrayUtil.reverseArray(sourceFolders);
 401       }
 402       for (SourceFolder sourceFolder : sourceFolders) {
 403         VirtualFile dir = sourceFolder.getFile();
 404         if (dir != null) {
 405           fillMapWithModuleSource(dir, module, sourceFolder.getPackagePrefix(), dir, sourceFolder.isTestSource(), forDir);
 406         }
 407       }
 408     }
 409   }
 410
 411   private void fillMapWithModuleSource(VirtualFile dir,
 412                                        Module module,
 413                                        String packageName,
 414                                        VirtualFile sourceRoot,
 415                                        boolean isTestSource,
 416                                        VirtualFile forDir) {
 417     DirectoryInfo info = myDirToInfoMap.get(dir);
 418     if (info == null) return;
 419     if (!module.equals(info.module)) return;
 420
 421     if (forDir != null) {
 422       if (!VfsUtil.isAncestor(dir, forDir, false)) return;
 423     }
 424
 425     if (info.isInModuleSource) { // module sources overlap
 426       if (info.packageName != null && info.packageName.length() == 0) return; // another source root starts here
 427     }
 428
 429     info.isInModuleSource = true;
 430     info.isTestSource = isTestSource;
 431     info.sourceRoot = sourceRoot;
 432     setPackageName(dir, info, packageName);
 433
 434     VirtualFile[] children = dir.getChildren();
 435     for (VirtualFile child : children) {
 436       if (child.isDirectory()) {
 437         String childPackageName = getPackageNameForSubdir(packageName, child.getName());
 438         fillMapWithModuleSource(child, module, childPackageName, sourceRoot, isTestSource, forDir);
 439       }
 440     }
 441   }
 442
 443   private void initLibrarySources(Module module, VirtualFile forDir, ProgressIndicator progress) {
 444     progress.checkCanceled();
 445     progress.setText2(ProjectBundle.message("project.index.processing.library.sources.progress", module.getName()));
 446
 447     for (OrderEntry orderEntry : getOrderEntries(module)) {
 448       boolean isLibrary = orderEntry instanceof LibraryOrderEntry || orderEntry instanceof JdkOrderEntry;
 449       if (isLibrary) {
 450         VirtualFile[] sourceRoots = orderEntry.getFiles(OrderRootType.SOURCES);
 451         for (final VirtualFile sourceRoot : sourceRoots) {
 452           fillMapWithLibrarySources(sourceRoot, "", sourceRoot, forDir);
 453         }
 454       }
 455     }
 456   }
 457
 458   private void fillMapWithLibrarySources(VirtualFile dir,
 459                                          String packageName,
 460                                          VirtualFile sourceRoot,
 461                                          VirtualFile forDir) {
 462     if (isIgnored(dir)) return;
 463
 464     if (forDir != null) {
 465       if (!VfsUtil.isAncestor(dir, forDir, false)) return;
 466     }
 467
 468     DirectoryInfo info = getOrCreateDirInfo(dir);
 469
 470     if (info.isInLibrarySource) { // library sources overlap
 471       if (info.packageName != null && info.packageName.length() == 0) return; // another library source root starts here
 472     }
 473
 474     info.isInModuleSource = false;
 475     info.isInLibrarySource = true;
 476     info.sourceRoot = sourceRoot;
 477     setPackageName(dir, info, packageName);
 478
 479     VirtualFile[] children = dir.getChildren();
 480     for (VirtualFile child : children) {
 481       if (child.isDirectory()) {
 482         String childPackageName = getPackageNameForSubdir(packageName, child.getName());
 483         fillMapWithLibrarySources(child, childPackageName, sourceRoot, forDir);
 484       }
 485     }
 486   }
 487
 488   private void initLibraryClasses(Module module, VirtualFile forDir, ProgressIndicator progress) {
 489     progress.checkCanceled();
 490     progress.setText2(ProjectBundle.message("project.index.processing.library.classes.progress", module.getName()));
 491
 492     for (OrderEntry orderEntry : getOrderEntries(module)) {
 493       boolean isLibrary = orderEntry instanceof LibraryOrderEntry || orderEntry instanceof JdkOrderEntry;
 494       if (isLibrary) {
 495         VirtualFile[] classRoots = orderEntry.getFiles(OrderRootType.CLASSES);
 496         for (final VirtualFile classRoot : classRoots) {
 497           fillMapWithLibraryClasses(classRoot, "", classRoot, forDir);
 498         }
 499       }
 500     }
 501   }
 502
 503   private void fillMapWithLibraryClasses(VirtualFile dir, String packageName, VirtualFile classRoot, VirtualFile forDir) {
 504     if (isIgnored(dir)) return;
 505
 506     if (forDir != null) {
 507       if (!VfsUtil.isAncestor(dir, forDir, false)) return;
 508     }
 509
 510     DirectoryInfo info = getOrCreateDirInfo(dir);
 511
 512     if (info.libraryClassRoot != null) { // library classes overlap
 513       if (info.packageName != null && info.packageName.length() == 0) return; // another library root starts here
 514     }
 515
 516     info.libraryClassRoot = classRoot;
 517
 518     if (!info.isInModuleSource && !info.isInLibrarySource) {
 519       setPackageName(dir, info, packageName);
 520     }
 521
 522     VirtualFile[] children = dir.getChildren();
 523     for (VirtualFile child : children) {
 524       if (child.isDirectory()) {
 525         String childPackageName = getPackageNameForSubdir(packageName, child.getName());
 526         fillMapWithLibraryClasses(child, childPackageName, classRoot, forDir);
 527       }
 528     }
 529   }
 530
 531   private void initOrderEntries(Module module, VirtualFile forDir) {
 532     Map<VirtualFile, List<OrderEntry>> depEntries = new HashMap<VirtualFile, List<OrderEntry>>();
 533     Map<VirtualFile, List<OrderEntry>> libClassRootEntries = new HashMap<VirtualFile, List<OrderEntry>>();
 534     Map<VirtualFile, List<OrderEntry>> libSourceRootEntries = new HashMap<VirtualFile, List<OrderEntry>>();
 535
 536     for (OrderEntry orderEntry : getOrderEntries(module)) {
 537       if (orderEntry instanceof ModuleOrderEntry) {
 538         VirtualFile[] importedClassRoots = orderEntry.getFiles(OrderRootType.COMPILATION_CLASSES);
 539         for (VirtualFile importedClassRoot : importedClassRoots) {
 540           addEntryToMap(importedClassRoot, orderEntry, depEntries);
 541         }
 542         VirtualFile[] sourceRoots = orderEntry.getFiles(OrderRootType.SOURCES);
 543         for (VirtualFile sourceRoot : sourceRoots) {
 544           addEntryToMap(sourceRoot, orderEntry, depEntries);
 545         }
 546       }
 547       else if (orderEntry instanceof ModuleSourceOrderEntry) {
 548         List<OrderEntry> oneEntryList = Arrays.asList(orderEntry);
 549         Module entryModule = orderEntry.getOwnerModule();
 550
 551         VirtualFile[] sourceRoots = orderEntry.getFiles(OrderRootType.SOURCES);
 552         for (VirtualFile sourceRoot : sourceRoots) {
 553           fillMapWithOrderEntries(sourceRoot, oneEntryList, entryModule, null, null, forDir, null, null);
 554         }
 555       }
 556       else if (orderEntry instanceof LibraryOrderEntry || orderEntry instanceof JdkOrderEntry) {
 557         VirtualFile[] classRoots = orderEntry.getFiles(OrderRootType.CLASSES);
 558         for (VirtualFile classRoot : classRoots) {
 559           addEntryToMap(classRoot, orderEntry, libClassRootEntries);
 560         }
 561         VirtualFile[] sourceRoots = orderEntry.getFiles(OrderRootType.SOURCES);
 562         for (VirtualFile sourceRoot : sourceRoots) {
 563           addEntryToMap(sourceRoot, orderEntry, libSourceRootEntries);
 564         }
 565       }
 566     }
 567
 568     for (Map.Entry<VirtualFile, List<OrderEntry>> mapEntry : depEntries.entrySet()) {
 569       final VirtualFile vRoot = mapEntry.getKey();
 570       final List<OrderEntry> entries = mapEntry.getValue();
 571       fillMapWithOrderEntries(vRoot, entries, null, null, null, forDir, null, null);
 572     }
 573
 574     for (Map.Entry<VirtualFile, List<OrderEntry>> mapEntry : libClassRootEntries.entrySet()) {
 575       final VirtualFile vRoot = mapEntry.getKey();
 576       final List<OrderEntry> entries = mapEntry.getValue();
 577       fillMapWithOrderEntries(vRoot, entries, null, vRoot, null, forDir, null, null);
 578     }
 579
 580     for (Map.Entry<VirtualFile, List<OrderEntry>> mapEntry : libSourceRootEntries.entrySet()) {
 581       final VirtualFile vRoot = mapEntry.getKey();
 582       final List<OrderEntry> entries = mapEntry.getValue();
 583       fillMapWithOrderEntries(vRoot, entries, null, null, vRoot, forDir, null, null);
 584     }
 585   }
 586
 587   private static void addEntryToMap(final VirtualFile vRoot, final OrderEntry entry, final Map<VirtualFile, List<OrderEntry>> map) {
 588     List<OrderEntry> list = map.get(vRoot);
 589     if (list == null) {
 590       list = new ArrayList<OrderEntry>();
 591       map.put(vRoot, list);
 592     }
 593     list.add(entry);
 594   }
 595
 596   private void fillMapWithOrderEntries(VirtualFile dir,
 597                                        List<OrderEntry> orderEntries,
 598                                        Module module,
 599                                        VirtualFile libraryClassRoot,
 600                                        VirtualFile librarySourceRoot,
 601                                        VirtualFile forDir,
 602                                        DirectoryInfo parentInfo,
 603                                        final List<OrderEntry> oldParentEntries) {
 604     if (isIgnored(dir)) return;
 605
 606     if (forDir != null) {
 607       if (!VfsUtil.isAncestor(dir, forDir, false)) return;
 608     }
 609
 610     DirectoryInfo info = myDirToInfoMap.get(dir); // do not create it here!
 611     if (info == null) return;
 612
 613     if (module != null) {
 614       if (info.module != module) return;
 615       if (!info.isInModuleSource) return;
 616     }
 617     else if (libraryClassRoot != null) {
 618       if (info.libraryClassRoot != libraryClassRoot) return;
 619       if (info.isInModuleSource) return;
 620     }
 621     else if (librarySourceRoot != null) {
 622       if (!info.isInLibrarySource) return;
 623       if (info.sourceRoot != librarySourceRoot) return;
 624       if (info.libraryClassRoot != null) return;
 625     }
 626
 627     final List<OrderEntry> oldEntries = info.getOrderEntries();
 628     info.addOrderEntries(orderEntries, parentInfo, oldParentEntries);
 629
 630     final VirtualFile[] children = dir.getChildren();
 631     for (VirtualFile child : children) {
 632       if (child.isDirectory()) {
 633         fillMapWithOrderEntries(child, orderEntries, module, libraryClassRoot, librarySourceRoot, forDir, info, oldEntries);
 634       }
 635     }
 636   }
 637
 638   private static boolean isIgnored(VirtualFile f) {
 639     return FileTypeManager.getInstance().isFileIgnored(f.getName());
 640   }
 641
 642   public DirectoryInfo getInfoForDirectory(VirtualFile dir) {
 643     checkAvailability();
 644     dispatchPendingEvents();
 645
 646     if (myIsLasyMode) {
 647       DirectoryInfo info = myDirToInfoMap.get(dir);
 648       if (info != null) return info;
 649       doInitialize(false, dir);
 650     }
 651
 652     return myDirToInfoMap.get(dir);
 653   }
 654
 655   @Override
 656   public boolean isProjectExcludeRoot(VirtualFile dir) {
 657     checkAvailability();
 658     return myProjectExcludeRoots.contains(dir);
 659   }
 660
 661   private final PackageSink mySink = new PackageSink();
 662
 663   private static final Condition<VirtualFile> IS_VALID = new Condition<VirtualFile>() {
 664     public boolean value(final VirtualFile virtualFile) {
 665       return virtualFile.isValid();
 666     }
 667   };
 668
 669   private class PackageSink extends QueryFactory<VirtualFile, VirtualFile[]> {
 670     private PackageSink() {
 671       registerExecutor(new QueryExecutor<VirtualFile, VirtualFile[]>() {
 672         public boolean execute(final VirtualFile[] allDirs, final Processor<VirtualFile> consumer) {
 673           for (VirtualFile dir : allDirs) {
 674             DirectoryInfo info = getInfoForDirectory(dir);
 675             assert info != null;
 676
 677             if (!info.isInLibrarySource || info.libraryClassRoot != null) {
 678               if (!consumer.process(dir)) return false;
 679             }
 680           }
 681           return true;
 682         }
 683       });
 684     }
 685
 686     public Query<VirtualFile> search(@NotNull String packageName, boolean includeLibrarySources) {
 687       VirtualFile[] allDirs = doGetDirectoriesByPackageName(packageName);
 688       return new FilteredQuery<VirtualFile>(includeLibrarySources ? new ArrayQuery<VirtualFile>(allDirs) : createQuery(allDirs), IS_VALID);
 689     }
 690   }
 691
 692   @NotNull
 693   public Query<VirtualFile> getDirectoriesByPackageName(@NotNull String packageName, boolean includeLibrarySources) {
 694     checkAvailability();
 695     return mySink.search(packageName, includeLibrarySources);
 696   }
 697
 698   @NotNull
 699   private VirtualFile[] doGetDirectoriesByPackageName(@NotNull String packageName) {
 700     dispatchPendingEvents();
 701
 702     if (!myIsLasyMode) {
 703       VirtualFile[] dirs = myPackageNameToDirsMap.get(packageName);
 704       return dirs != null ? dirs : VirtualFile.EMPTY_ARRAY;
 705     }
 706     else {
 707       VirtualFile[] dirs = myPackageNameToDirsMap.get(packageName);
 708       if (dirs != null) return dirs;
 709       dirs = doGetDirectoriesByPackageNameInLazyMode(packageName);
 710       myPackageNameToDirsMap.put(packageName, dirs);
 711       return dirs;
 712     }
 713   }
 714
 715   @NotNull
 716   private VirtualFile[] doGetDirectoriesByPackageNameInLazyMode(@NotNull String packageName) {
 717     ArrayList<VirtualFile> list = new ArrayList<VirtualFile>();
 718
 719     Module[] modules = ModuleManager.getInstance(myProject).getModules();
 720     for (Module module : modules) {
 721       for (ContentEntry contentEntry : getContentEntries(module)) {
 722         SourceFolder[] sourceFolders = contentEntry.getSourceFolders();
 723         for (SourceFolder sourceFolder : sourceFolders) {
 724           VirtualFile sourceRoot = sourceFolder.getFile();
 725           if (sourceRoot != null) {
 726             findAndAddDirByPackageName(list, sourceRoot, packageName);
 727           }
 728         }
 729       }
 730
 731       for (OrderEntry orderEntry : getOrderEntries(module)) {
 732         if (orderEntry instanceof LibraryOrderEntry || orderEntry instanceof JdkOrderEntry) {
 733           VirtualFile[] libRoots = orderEntry.getFiles(OrderRootType.CLASSES);
 734           for (VirtualFile libRoot : libRoots) {
 735             findAndAddDirByPackageName(list, libRoot, packageName);
 736           }
 737
 738           VirtualFile[] libSourceRoots = orderEntry.getFiles(OrderRootType.SOURCES);
 739           for (VirtualFile libSourceRoot : libSourceRoots) {
 740             findAndAddDirByPackageName(list, libSourceRoot, packageName);
 741           }
 742         }
 743       }
 744     }
 745
 746     return list.toArray(new VirtualFile[list.size()]);
 747   }
 748
 749   private void findAndAddDirByPackageName(ArrayList<VirtualFile> list, VirtualFile root, @NotNull String packageName) {
 750     VirtualFile dir = findDirByPackageName(root, packageName);
 751     if (dir == null) return;
 752     DirectoryInfo info = getInfoForDirectory(dir);
 753     if (info == null) return;
 754     if (!packageName.equals(info.packageName)) return;
 755     if (!list.contains(dir)) {
 756       list.add(dir);
 757     }
 758   }
 759
 760   private static VirtualFile findDirByPackageName(VirtualFile root, @NotNull String packageName) {
 761     if (packageName.length() == 0) {
 762       return root;
 763     }
 764     else {
 765       int index = packageName.indexOf('.');
 766       if (index < 0) {
 767         VirtualFile child = root.findChild(packageName);
 768         if (child == null || !child.isDirectory()) return null;
 769         return child;
 770       }
 771       else {
 772         String name = packageName.substring(0, index);
 773         String restName = packageName.substring(index + 1);
 774         VirtualFile child = root.findChild(name);
 775         if (child == null || !child.isDirectory()) return null;
 776         return findDirByPackageName(child, restName);
 777       }
 778     }
 779   }
 780
 781   private void dispatchPendingEvents() {
 782     myConnection.deliverImmediately();
 783   }
 784
 785   private void checkAvailability() {
 786     if (!myInitialized) {
 787       LOG.error("Directory index is not initialized yet for "+myProject);
 788     }
 789
 790     if (myDisposed) {
 791       LOG.error("Directory index is aleady disposed for "+myProject);
 792     }
 793   }
 794
 795   private DirectoryInfo getOrCreateDirInfo(VirtualFile dir) {
 796     DirectoryInfo info = myDirToInfoMap.get(dir);
 797     if (info == null) {
 798       info = new DirectoryInfo(dir);
 799       myDirToInfoMap.put(dir, info);
 800     }
 801     return info;
 802   }
 803
 804   private void setPackageName(VirtualFile dir, DirectoryInfo info, String newPackageName) {
 805     assert dir != null;
 806
 807     if (!myIsLasyMode) {
 808       String oldPackageName = info.packageName;
 809       if (oldPackageName != null) {
 810         VirtualFile[] oldPackageDirs = myPackageNameToDirsMap.get(oldPackageName);
 811         assert oldPackageDirs != null;
 812         assert oldPackageDirs.length > 0;
 813         if (oldPackageDirs.length != 1) {
 814           VirtualFile[] dirs = new VirtualFile[oldPackageDirs.length - 1];
 815
 816           boolean found = false;
 817           for (int i = 0; i < oldPackageDirs.length; i++) {
 818             VirtualFile oldDir = oldPackageDirs[i];
 819             if (oldDir.equals(dir)) {
 820               found = true;
 821               continue;
 822             }
 823             dirs[found ? i - 1 : i] = oldDir;
 824           }
 825
 826           assert found;
 827
 828           myPackageNameToDirsMap.put(oldPackageName, dirs);
 829         }
 830         else {
 831           assert dir.equals(oldPackageDirs[0]);
 832           myPackageNameToDirsMap.remove(oldPackageName);
 833         }
 834
 835       }
 836
 837       if (newPackageName != null) {
 838         VirtualFile[] newPackageDirs = myPackageNameToDirsMap.get(newPackageName);
 839         VirtualFile[] dirs;
 840         if (newPackageDirs == null) {
 841           dirs = new VirtualFile[]{dir};
 842         }
 843         else {
 844           dirs = new VirtualFile[newPackageDirs.length + 1];
 845           System.arraycopy(newPackageDirs, 0, dirs, 0, newPackageDirs.length);
 846           dirs[newPackageDirs.length] = dir;
 847         }
 848         myPackageNameToDirsMap.put(newPackageName, dirs);
 849       }
 850     }
 851     else {
 852       if (info.packageName != null) {
 853         myPackageNameToDirsMap.remove(info.packageName);
 854       }
 855       if (newPackageName != null) {
 856         myPackageNameToDirsMap.remove(newPackageName);
 857       }
 858     }
 859
 860     info.packageName = newPackageName;
 861   }
 862
 863   @Nullable
 864   private static String getPackageNameForSubdir(String parentPackageName, String subdirName) {
 865     if (parentPackageName == null) return null;
 866     return parentPackageName.length() > 0 ? parentPackageName + "." + subdirName : subdirName;
 867   }
 868
 869   private class MyVirtualFileListener extends VirtualFileAdapter {
 870     private final Key<List<VirtualFile>> FILES_TO_RELEASE_KEY = Key.create("DirectoryIndexImpl.MyVirtualFileListener.FILES_TO_RELEASE_KEY");
 871
 872     public void fileCreated(VirtualFileEvent event) {
 873       if (myIsLasyMode) return;
 874
 875       VirtualFile file = event.getFile();
 876
 877       if (!file.isDirectory()) return;
 878
 879       VirtualFile parent = file.getParent();
 880       if (parent == null) return;
 881
 882       if (isIgnored(file)) return;
 883
 884       DirectoryInfo parentInfo = myDirToInfoMap.get(parent);
 885       if (parentInfo == null) return;
 886
 887       Module module = parentInfo.module;
 888
 889       for(DirectoryIndexExcludePolicy policy: myExcludePolicies) {
 890         if (policy.isExcludeRoot(file)) return;
 891       }
 892
 893       fillMapWithModuleContent(file, module, parentInfo.contentRoot, null);
 894
 895       if (module != null) {
 896         if (parentInfo.isInModuleSource) {
 897           String newDirPackageName = getPackageNameForSubdir(parentInfo.packageName, file.getName());
 898           fillMapWithModuleSource(file, module, newDirPackageName, parentInfo.sourceRoot, parentInfo.isTestSource, null);
 899         }
 900       }
 901
 902       if (parentInfo.libraryClassRoot != null) {
 903         String newDirPackageName = getPackageNameForSubdir(parentInfo.packageName, file.getName());
 904         fillMapWithLibraryClasses(file, newDirPackageName, parentInfo.libraryClassRoot, null);
 905       }
 906
 907       if (parentInfo.isInLibrarySource) {
 908         String newDirPackageName = getPackageNameForSubdir(parentInfo.packageName, file.getName());
 909         fillMapWithLibrarySources(file, newDirPackageName, parentInfo.sourceRoot, null);
 910       }
 911
 912       if (!parentInfo.getOrderEntries().isEmpty()) {
 913         fillMapWithOrderEntries(file, parentInfo.getOrderEntries(), null, null, null, null, parentInfo, null);
 914       }
 915     }
 916
 917     public void beforeFileDeletion(VirtualFileEvent event) {
 918       VirtualFile file = event.getFile();
 919       if (!file.isDirectory()) return;
 920       if (!myDirToInfoMap.containsKey(file)) return;
 921
 922       ArrayList<VirtualFile> list = new ArrayList<VirtualFile>();
 923       addDirsRecursively(list, file);
 924       file.putUserData(FILES_TO_RELEASE_KEY, list);
 925     }
 926
 927     private void addDirsRecursively(ArrayList<VirtualFile> list, VirtualFile dir) {
 928       if (!myDirToInfoMap.containsKey(dir) || !(dir instanceof NewVirtualFile)) return;
 929
 930       list.add(dir);
 931
 932       for (VirtualFile child : ((NewVirtualFile)dir).getCachedChildren()) {
 933         if (child.isDirectory()) {
 934           addDirsRecursively(list, child);
 935         }
 936       }
 937     }
 938
 939     public void fileDeleted(VirtualFileEvent event) {
 940       VirtualFile file = event.getFile();
 941       List<VirtualFile> list = file.getUserData(FILES_TO_RELEASE_KEY);
 942       if (list == null) return;
 943
 944       for (VirtualFile dir : list) {
 945         DirectoryInfo info = myDirToInfoMap.remove(dir);
 946         if (info != null) {
 947           setPackageName(dir, info, null);
 948         }
 949       }
 950     }
 951
 952     public void fileMoved(VirtualFileMoveEvent event) {
 953       VirtualFile file = event.getFile();
 954
 955       if (file.isDirectory()) {
 956         doInitialize();
 957       }
 958     }
 959
 960     public void propertyChanged(VirtualFilePropertyEvent event) {
 961       if (VirtualFile.PROP_NAME.equals(event.getPropertyName())) {
 962         VirtualFile file = event.getFile();
 963
 964         if (file.isDirectory()) {
 965           doInitialize();
 966         }
 967       }
 968     }
 969   }
 970 }