platform/lang-impl/src/com/intellij/util/indexing/FileBasedIndex.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.util.indexing;
  18
  19 import com.intellij.AppTopics;
  20 import com.intellij.concurrency.Job;
  21 import com.intellij.concurrency.JobScheduler;
  22 import com.intellij.ide.startup.BackgroundableCacheUpdater;
  23 import com.intellij.ide.startup.impl.FileSystemSynchronizerImpl;
  24 import com.intellij.lang.ASTNode;
  25 import com.intellij.openapi.application.*;
  26 import com.intellij.openapi.components.ApplicationComponent;
  27 import com.intellij.openapi.diagnostic.Logger;
  28 import com.intellij.openapi.editor.Document;
  29 import com.intellij.openapi.editor.highlighter.EditorHighlighter;
  30 import com.intellij.openapi.editor.impl.DocumentImpl;
  31 import com.intellij.openapi.extensions.Extensions;
  32 import com.intellij.openapi.fileEditor.FileDocumentManager;
  33 import com.intellij.openapi.fileTypes.*;
  34 import com.intellij.openapi.progress.*;
  35 import com.intellij.openapi.progress.impl.BackgroundableProcessIndicator;
  36 import com.intellij.openapi.project.*;
  37 import com.intellij.openapi.roots.CollectingContentIterator;
  38 import com.intellij.openapi.roots.ContentIterator;
  39 import com.intellij.openapi.roots.ProjectRootManager;
  40 import com.intellij.openapi.util.*;
  41 import com.intellij.openapi.util.io.FileUtil;
  42 import com.intellij.openapi.util.registry.Registry;
  43 import com.intellij.openapi.vfs.*;
  44 import com.intellij.openapi.vfs.ex.VirtualFileManagerEx;
  45 import com.intellij.openapi.vfs.newvfs.BulkFileListener;
  46 import com.intellij.openapi.vfs.newvfs.ManagingFS;
  47 import com.intellij.openapi.vfs.newvfs.NewVirtualFile;
  48 import com.intellij.openapi.vfs.newvfs.events.VFileEvent;
  49 import com.intellij.openapi.vfs.newvfs.impl.NullVirtualFile;
  50 import com.intellij.openapi.vfs.newvfs.persistent.PersistentFS;
  51 import com.intellij.psi.PsiDocumentManager;
  52 import com.intellij.psi.PsiFile;
  53 import com.intellij.psi.PsiLock;
  54 import com.intellij.psi.SingleRootFileViewProvider;
  55 import com.intellij.psi.impl.PsiDocumentTransactionListener;
  56 import com.intellij.psi.impl.source.PsiFileImpl;
  57 import com.intellij.psi.search.GlobalSearchScope;
  58 import com.intellij.util.ArrayUtil;
  59 import com.intellij.util.CommonProcessors;
  60 import com.intellij.util.Processor;
  61 import com.intellij.util.concurrency.JBLock;
  62 import com.intellij.util.concurrency.JBReentrantReadWriteLock;
  63 import com.intellij.util.concurrency.LockFactory;
  64 import com.intellij.util.concurrency.Semaphore;
  65 import com.intellij.util.containers.ConcurrentHashSet;
  66 import com.intellij.util.containers.ContainerUtil;
  67 import com.intellij.util.io.*;
  68 import com.intellij.util.messages.MessageBus;
  69 import com.intellij.util.messages.MessageBusConnection;
  70 import gnu.trove.TIntHashSet;
  71 import gnu.trove.TIntIterator;
  72 import gnu.trove.TObjectIntHashMap;
  73 import org.jetbrains.annotations.NonNls;
  74 import org.jetbrains.annotations.NotNull;
  75 import org.jetbrains.annotations.Nullable;
  76 import org.jetbrains.annotations.TestOnly;
  77
  78 import javax.swing.*;
  79 import java.io.*;
  80 import java.util.*;
  81 import java.util.concurrent.atomic.AtomicBoolean;
  82 import java.util.concurrent.atomic.AtomicInteger;
  83 import java.util.concurrent.locks.Lock;
  84
  85 /**
  86  * @author Eugene Zhuravlev
  87  *         Date: Dec 20, 2007
  88  */
  89
  90 public class FileBasedIndex implements ApplicationComponent {
  91   private static final Logger LOG = Logger.getInstance("#com.intellij.util.indexing.FileBasedIndex");
  92   @NonNls
  93   private static final String CORRUPTION_MARKER_NAME = "corruption.marker";
  94   private final Map<ID<?, ?>, Pair<UpdatableIndex<?, ?, FileContent>, InputFilter>> myIndices = new HashMap<ID<?, ?>, Pair<UpdatableIndex<?, ?, FileContent>, InputFilter>>();
  95   private final Map<ID<?, ?>, Semaphore> myUnsavedDataIndexingSemaphores = new HashMap<ID<?,?>, Semaphore>();
  96   private final TObjectIntHashMap<ID<?, ?>> myIndexIdToVersionMap = new TObjectIntHashMap<ID<?, ?>>();
  97   private final Set<ID<?, ?>> myNotRequiringContentIndices = new HashSet<ID<?, ?>>();
  98   private final Set<FileType> myNoLimitCheckTypes = new HashSet<FileType>();
  99
 100   private final PerIndexDocumentMap<Long> myLastIndexedDocStamps = new PerIndexDocumentMap<Long>() {
 101     @Override
 102     protected Long createDefault(Document document) {
 103       return 0L;
 104     }
 105   };
 106
 107   private final ChangedFilesUpdater myChangedFilesUpdater;
 108
 109   private final List<IndexableFileSet> myIndexableSets = ContainerUtil.createEmptyCOWList();
 110
 111   public static final int OK = 1;
 112   public static final int REQUIRES_REBUILD = 2;
 113   public static final int REBUILD_IN_PROGRESS = 3;
 114   private final Map<ID<?, ?>, AtomicInteger> myRebuildStatus = new HashMap<ID<?,?>, AtomicInteger>();
 115
 116   private final VirtualFileManagerEx myVfManager;
 117   private final FileDocumentManager myFileDocumentManager;
 118   private final ConcurrentHashSet<ID<?, ?>> myUpToDateIndices = new ConcurrentHashSet<ID<?, ?>>();
 119   private final Map<Document, PsiFile> myTransactionMap = new HashMap<Document, PsiFile>();
 120
 121   private static final int ALREADY_PROCESSED = 0x02;
 122   private static final String USE_MULTITHREADED_INDEXING = "fileIndex.multithreaded";
 123   private @Nullable String myConfigPath;
 124   private @Nullable String mySystemPath;
 125
 126   public void requestReindex(final VirtualFile file) {
 127     myChangedFilesUpdater.invalidateIndices(file, true);
 128   }
 129
 130   public interface InputFilter {
 131     boolean acceptInput(VirtualFile file);
 132   }
 133
 134   public FileBasedIndex(final VirtualFileManagerEx vfManager, FileDocumentManager fdm, MessageBus bus) throws IOException {
 135     myVfManager = vfManager;
 136     myFileDocumentManager = fdm;
 137
 138     myConfigPath = calcConfigPath(PathManager.getConfigPath());
 139     mySystemPath = calcConfigPath(PathManager.getSystemPath());
 140
 141     final MessageBusConnection connection = bus.connect();
 142     connection.subscribe(PsiDocumentTransactionListener.TOPIC, new PsiDocumentTransactionListener() {
 143       public void transactionStarted(final Document doc, final PsiFile file) {
 144         if (file != null) {
 145           myTransactionMap.put(doc, file);
 146           myUpToDateIndices.clear();
 147         }
 148       }
 149
 150       public void transactionCompleted(final Document doc, final PsiFile file) {
 151         myTransactionMap.remove(doc);
 152       }
 153     });
 154
 155     connection.subscribe(AppTopics.FILE_TYPES, new FileTypeListener() {
 156       private Map<FileType, Set<String>> myTypeToExtensionMap;
 157       public void beforeFileTypesChanged(final FileTypeEvent event) {
 158         cleanupProcessedFlag();
 159         myTypeToExtensionMap = new HashMap<FileType, Set<String>>();
 160         final FileTypeManager manager = event.getManager();
 161         for (FileType type : manager.getRegisteredFileTypes()) {
 162           myTypeToExtensionMap.put(type, getExtensions(manager, type));
 163         }
 164       }
 165
 166       public void fileTypesChanged(final FileTypeEvent event) {
 167         final Map<FileType, Set<String>> oldExtensions = myTypeToExtensionMap;
 168         myTypeToExtensionMap = null;
 169         if (oldExtensions != null) {
 170           final FileTypeManager manager = event.getManager();
 171           final Map<FileType, Set<String>> newExtensions = new HashMap<FileType, Set<String>>();
 172           for (FileType type : manager.getRegisteredFileTypes()) {
 173             newExtensions.put(type, getExtensions(manager, type));
 174           }
 175           // we are interested only in extension changes or removals.
 176           // addition of an extension is handled separately by RootsChanged event
 177           if (!newExtensions.keySet().containsAll(oldExtensions.keySet())) {
 178             rebuildAllndices();
 179             return;
 180           }
 181           for (FileType type : oldExtensions.keySet()) {
 182             if (!newExtensions.get(type).containsAll(oldExtensions.get(type))) {
 183               rebuildAllndices();
 184               return;
 185             }
 186           }
 187         }
 188       }
 189
 190       private Set<String> getExtensions(FileTypeManager manager, FileType type) {
 191         final Set<String> set = new HashSet<String>();
 192         for (FileNameMatcher matcher : manager.getAssociations(type)) {
 193           set.add(matcher.getPresentableString());
 194         }
 195         return set;
 196       }
 197
 198       private void rebuildAllndices() {
 199         for (ID<?, ?> indexId : myIndices.keySet()) {
 200           requestRebuild(indexId);
 201         }
 202       }
 203     });
 204
 205     connection.subscribe(VirtualFileManager.VFS_CHANGES, new BulkFileListener() {
 206       public void before(List<? extends VFileEvent> events) {
 207         for (VFileEvent event : events) {
 208           if (event.getRequestor() instanceof FileDocumentManager) {
 209             cleanupMemoryStorage();
 210             break;
 211           }
 212         }
 213       }
 214
 215       public void after(List<? extends VFileEvent> events) {
 216       }
 217     });
 218
 219     ApplicationManager.getApplication().addApplicationListener(new ApplicationAdapter() {
 220       public void writeActionStarted(Object action) {
 221         myUpToDateIndices.clear();
 222       }
 223     });
 224
 225     final File workInProgressFile = getMarkerFile();
 226     if (workInProgressFile.exists()) {
 227       // previous IDEA session was closed incorrectly, so drop all indices
 228       FileUtil.delete(PathManager.getIndexRoot());
 229     }
 230
 231     try {
 232       final FileBasedIndexExtension[] extensions = Extensions.getExtensions(FileBasedIndexExtension.EXTENSION_POINT_NAME);
 233       for (FileBasedIndexExtension<?, ?> extension : extensions) {
 234         myRebuildStatus.put(extension.getName(), new AtomicInteger(OK));
 235       }
 236
 237       final File corruptionMarker = new File(PathManager.getIndexRoot(), CORRUPTION_MARKER_NAME);
 238       final boolean currentVersionCorrupted = corruptionMarker.exists();
 239       for (FileBasedIndexExtension<?, ?> extension : extensions) {
 240         registerIndexer(extension, currentVersionCorrupted);
 241       }
 242       FileUtil.delete(corruptionMarker);
 243       dropUnregisteredIndices();
 244
 245       // check if rebuild was requested for any index during registration
 246       for (ID<?, ?> indexId : myIndices.keySet()) {
 247         if (myRebuildStatus.get(indexId).compareAndSet(REQUIRES_REBUILD, OK)) {
 248           try {
 249             clearIndex(indexId);
 250           }
 251           catch (StorageException e) {
 252             requestRebuild(indexId);
 253             LOG.error(e);
 254           }
 255         }
 256       }
 257
 258       myChangedFilesUpdater = new ChangedFilesUpdater();
 259       vfManager.addVirtualFileListener(myChangedFilesUpdater);
 260
 261       vfManager.registerRefreshUpdater(myChangedFilesUpdater);
 262
 263       registerIndexableSet(new AdditionalIndexableFileSet());
 264     }
 265     finally {
 266       ShutDownTracker.getInstance().registerShutdownTask(new Runnable() {
 267         public void run() {
 268           performShutdown();
 269         }
 270       });
 271       FileUtil.createIfDoesntExist(workInProgressFile);
 272       saveRegisteredIndices(myIndices.keySet());
 273     }
 274   }
 275
 276   private static String calcConfigPath(final String path) {
 277     try {
 278       final String _path = FileUtil.toSystemIndependentName(new File(path).getCanonicalPath());
 279       return _path.endsWith("/")? _path : _path + "/" ;
 280     }
 281     catch (IOException e) {
 282       LOG.info(e);
 283       return null;
 284     }
 285   }
 286
 287   private static FileBasedIndex ourInstance = CachedSingletonsRegistry.markCachedField(FileBasedIndex.class);
 288   public static FileBasedIndex getInstance() {
 289     if (ourInstance == null) {
 290       ourInstance = ApplicationManager.getApplication().getComponent(FileBasedIndex.class);
 291     }
 292
 293     return ourInstance;
 294   }
 295
 296   /**
 297    * @return true if registered index requires full rebuild for some reason, e.g. is just created or corrupted @param extension
 298    * @param isCurrentVersionCorrupted
 299    */
 300   private <K, V> void registerIndexer(final FileBasedIndexExtension<K, V> extension, final boolean isCurrentVersionCorrupted) throws IOException {
 301     final ID<K, V> name = extension.getName();
 302     final int version = extension.getVersion();
 303     if (!extension.dependsOnFileContent()) {
 304       myNotRequiringContentIndices.add(name);
 305     }
 306     myIndexIdToVersionMap.put(name, version);
 307     final File versionFile = IndexInfrastructure.getVersionFile(name);
 308     if (isCurrentVersionCorrupted || IndexInfrastructure.versionDiffers(versionFile, version)) {
 309       if (!isCurrentVersionCorrupted) {
 310         LOG.info("Version has changed for index " + extension.getName() + ". The index will be rebuilt.");
 311       }
 312       FileUtil.delete(IndexInfrastructure.getIndexRootDir(name));
 313       IndexInfrastructure.rewriteVersion(versionFile, version);
 314     }
 315
 316     for (int attempt = 0; attempt < 2; attempt++) {
 317       try {
 318         final MapIndexStorage<K, V> storage = new MapIndexStorage<K, V>(IndexInfrastructure.getStorageFile(name), extension.getKeyDescriptor(), extension.getValueExternalizer(), extension.getCacheSize());
 319         final IndexStorage<K, V> memStorage = new MemoryIndexStorage<K, V>(storage);
 320         final UpdatableIndex<K, V, FileContent> index = createIndex(name, extension, memStorage);
 321         myIndices.put(name, new Pair<UpdatableIndex<?,?, FileContent>, InputFilter>(index, new IndexableFilesFilter(extension.getInputFilter())));
 322         myUnsavedDataIndexingSemaphores.put(name, new Semaphore());
 323         myNoLimitCheckTypes.addAll(extension.getFileTypesWithSizeLimitNotApplicable());
 324         break;
 325       }
 326       catch (IOException e) {
 327         LOG.info(e);
 328         FileUtil.delete(IndexInfrastructure.getIndexRootDir(name));
 329         IndexInfrastructure.rewriteVersion(versionFile, version);
 330       }
 331     }
 332   }
 333
 334   private static void saveRegisteredIndices(Collection<ID<?, ?>> ids) {
 335     final File file = getRegisteredIndicesFile();
 336     try {
 337       FileUtil.createIfDoesntExist(file);
 338       final DataOutputStream os = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(file)));
 339       try {
 340         os.writeInt(ids.size());
 341         for (ID<?, ?> id : ids) {
 342           IOUtil.writeString(id.toString(), os);
 343         }
 344       }
 345       finally {
 346         os.close();
 347       }
 348     }
 349     catch (IOException ignored) {
 350     }
 351   }
 352
 353   private static Set<String> readRegistsredIndexNames() {
 354     final Set<String> result = new HashSet<String>();
 355     try {
 356       final DataInputStream in = new DataInputStream(new BufferedInputStream(new FileInputStream(getRegisteredIndicesFile())));
 357       try {
 358         final int size = in.readInt();
 359         for (int idx = 0; idx < size; idx++) {
 360           result.add(IOUtil.readString(in));
 361         }
 362       }
 363       finally {
 364         in.close();
 365       }
 366     }
 367     catch (IOException ignored) {
 368     }
 369     return result;
 370   }
 371
 372   private static File getRegisteredIndicesFile() {
 373     return new File(PathManager.getIndexRoot(), "registered");
 374   }
 375
 376   private static File getMarkerFile() {
 377     return new File(PathManager.getIndexRoot(), "work_in_progress");
 378   }
 379
 380   private <K, V> UpdatableIndex<K, V, FileContent> createIndex(final ID<K, V> indexId, final FileBasedIndexExtension<K, V> extension, final IndexStorage<K, V> storage) throws IOException {
 381     final MapReduceIndex<K, V, FileContent> index;
 382     if (extension instanceof CustomImplementationFileBasedIndexExtension) {
 383       final UpdatableIndex<K, V, FileContent> custom =
 384         ((CustomImplementationFileBasedIndexExtension<K, V, FileContent>)extension).createIndexImplementation(indexId, this, storage);
 385       if (!(custom instanceof MapReduceIndex)) {
 386         return custom;
 387       }
 388       index = (MapReduceIndex<K,V, FileContent>)custom;
 389     }
 390     else {
 391       index = new MapReduceIndex<K, V, FileContent>(indexId, extension.getIndexer(), storage);
 392     }
 393
 394     final KeyDescriptor<K> keyDescriptor = extension.getKeyDescriptor();
 395     index.setInputIdToDataKeysIndex(new Factory<PersistentHashMap<Integer, Collection<K>>>() {
 396       public PersistentHashMap<Integer, Collection<K>> create() {
 397         try {
 398           return createIdToDataKeysIndex(indexId, keyDescriptor);
 399         }
 400         catch (IOException e) {
 401           throw new RuntimeException(e);
 402         }
 403       }
 404     });
 405
 406     return index;
 407   }
 408
 409   private static <K> PersistentHashMap<Integer, Collection<K>> createIdToDataKeysIndex(ID<K, ?> indexId, final KeyDescriptor<K> keyDescriptor) throws IOException {
 410     final File indexStorageFile = IndexInfrastructure.getInputIndexStorageFile(indexId);
 411     return new PersistentHashMap<Integer, Collection<K>>(indexStorageFile, new EnumeratorIntegerDescriptor(), new DataExternalizer<Collection<K>>() {
 412       public void save(DataOutput out, Collection<K> value) throws IOException {
 413         DataInputOutputUtil.writeINT(out, value.size());
 414         for (K key : value) {
 415           keyDescriptor.save(out, key);
 416         }
 417       }
 418
 419       public Collection<K> read(DataInput in) throws IOException {
 420         final int size = DataInputOutputUtil.readINT(in);
 421         final List<K> list = new ArrayList<K>();
 422         for (int idx = 0; idx < size; idx++) {
 423           list.add(keyDescriptor.read(in));
 424         }
 425         return list;
 426       }
 427     });
 428   }
 429
 430   @NonNls
 431   @NotNull
 432   public String getComponentName() {
 433     return "FileBasedIndex";
 434   }
 435
 436   public void initComponent() {
 437   }
 438
 439   public void disposeComponent() {
 440     performShutdown();
 441   }
 442
 443   private AtomicBoolean myShutdownPerformed = new AtomicBoolean(false);
 444
 445   private void performShutdown() {
 446     if (!myShutdownPerformed.compareAndSet(false, true)) {
 447       return; // already shut down
 448     }
 449     myFileDocumentManager.saveAllDocuments();
 450
 451     LOG.info("START INDEX SHUTDOWN");
 452     try {
 453       myChangedFilesUpdater.forceUpdate(null);
 454
 455       for (ID<?, ?> indexId : myIndices.keySet()) {
 456         final UpdatableIndex<?, ?, FileContent> index = getIndex(indexId);
 457         assert index != null;
 458         checkRebuild(indexId, true); // if the index was scheduled for rebuild, only clean it
 459         //LOG.info("DISPOSING " + indexId);
 460         index.dispose();
 461       }
 462
 463       myVfManager.removeVirtualFileListener(myChangedFilesUpdater);
 464       myVfManager.unregisterRefreshUpdater(myChangedFilesUpdater);
 465
 466       FileUtil.delete(getMarkerFile());
 467     }
 468     catch (Throwable e) {
 469       LOG.info("Problems during index shutdown", e);
 470       throw new RuntimeException(e);
 471     }
 472     LOG.info("END INDEX SHUTDOWN");
 473   }
 474
 475   public void flushCaches() {
 476     IndexingStamp.flushCache();
 477     ApplicationManager.getApplication().executeOnPooledThread(new Runnable() {
 478       public void run() {
 479         for (ID<?, ?> indexId : myIndices.keySet()) {
 480           //noinspection ConstantConditions
 481           try {
 482             getIndex(indexId).flush();
 483           }
 484           catch (StorageException e) {
 485             LOG.info(e);
 486             requestRebuild(indexId);
 487           }
 488         }
 489       }
 490     });
 491   }
 492
 493   /**
 494    * @param project it is guaranteeed to return data which is up-to-date withing the project
 495    * Keys obtained from the files which do not belong to the project specified may not be up-to-date or even exist
 496    */
 497   @NotNull
 498   public <K> Collection<K> getAllKeys(final ID<K, ?> indexId, @NotNull Project project) {
 499     Set<K> allKeys = new HashSet<K>();
 500     processAllKeys(indexId, new CommonProcessors.CollectProcessor<K>(allKeys), project);
 501     return allKeys;
 502   }
 503
 504   /**
 505    * @param project it is guaranteeed to return data which is up-to-date withing the project
 506    * Keys obtained from the files which do not belong to the project specified may not be up-to-date or even exist
 507    */
 508   public <K> boolean processAllKeys(final ID<K, ?> indexId, Processor<K> processor, @NotNull Project project) {
 509     try {
 510       ensureUpToDate(indexId, project, GlobalSearchScope.allScope(project));
 511       final UpdatableIndex<K, ?, FileContent> index = getIndex(indexId);
 512       if (index == null) return true;
 513       return index.processAllKeys(processor);
 514     }
 515     catch (StorageException e) {
 516       scheduleRebuild(indexId, e);
 517     }
 518     catch (RuntimeException e) {
 519       final Throwable cause = e.getCause();
 520       if (cause instanceof StorageException || cause instanceof IOException) {
 521         scheduleRebuild(indexId, cause);
 522       }
 523       else {
 524         throw e;
 525       }
 526     }
 527
 528     return false;
 529   }
 530
 531   private static final ThreadLocal<Integer> myUpToDateCheckState = new ThreadLocal<Integer>();
 532
 533   public void disableUpToDateCheckForCurrentThread() {
 534     final Integer currentValue = myUpToDateCheckState.get();
 535     myUpToDateCheckState.set(currentValue == null? 1 : currentValue.intValue() + 1);
 536   }
 537
 538   public void enableUpToDateCheckForCurrentThread() {
 539     final Integer currentValue = myUpToDateCheckState.get();
 540     if (currentValue != null) {
 541       final int newValue = currentValue.intValue() - 1;
 542       if (newValue != 0) {
 543         myUpToDateCheckState.set(newValue);
 544       }
 545       else {
 546         myUpToDateCheckState.remove();
 547       }
 548     }
 549   }
 550
 551   private boolean isUpToDateCheckEnabled() {
 552     final Integer value = myUpToDateCheckState.get();
 553     return value == null || value.intValue() == 0;
 554   }
 555
 556
 557   private final ThreadLocal<Boolean> myReentrancyGuard = new ThreadLocal<Boolean>() {
 558     protected Boolean initialValue() {
 559       return Boolean.FALSE;
 560     }
 561   };
 562
 563   /**
 564    * DO NOT CALL DIRECTLY IN CLIENT CODE
 565    * The method is internal to indexing engine end is called internally. The method is public due to implementation details
 566    */
 567   public <K> void ensureUpToDate(final ID<K, ?> indexId, @NotNull Project project, @Nullable GlobalSearchScope filter) {
 568     if (isDumb(project)) {
 569       handleDumbMode(indexId, project);
 570     }
 571
 572     if (myReentrancyGuard.get().booleanValue()) {
 573       //assert false : "ensureUpToDate() is not reentrant!";
 574       return;
 575     }
 576     myReentrancyGuard.set(Boolean.TRUE);
 577
 578     try {
 579       myChangedFilesUpdater.ensureAllInvalidateTasksCompleted();
 580       if (isUpToDateCheckEnabled()) {
 581         try {
 582           checkRebuild(indexId, false);
 583           myChangedFilesUpdater.forceUpdate(filter);
 584           indexUnsavedDocuments(indexId, project, filter);
 585         }
 586         catch (StorageException e) {
 587           scheduleRebuild(indexId, e);
 588         }
 589         catch (RuntimeException e) {
 590           final Throwable cause = e.getCause();
 591           if (cause instanceof StorageException || cause instanceof IOException) {
 592             scheduleRebuild(indexId, e);
 593           }
 594           else {
 595             throw e;
 596           }
 597         }
 598       }
 599     }
 600     finally {
 601       myReentrancyGuard.set(Boolean.FALSE);
 602     }
 603   }
 604
 605   private void handleDumbMode(final ID<?, ?> indexId, Project project) {
 606     if (myNotRequiringContentIndices.contains(indexId)) {
 607       return; //indexed eagerly in foreground while building unindexed file list
 608     }
 609
 610     ProgressManager.checkCanceled(); // DumbModeAction.CANCEL
 611
 612     final ProgressIndicator progressIndicator = ProgressManager.getInstance().getProgressIndicator();
 613     if (progressIndicator instanceof BackgroundableProcessIndicator) {
 614       final BackgroundableProcessIndicator indicator = (BackgroundableProcessIndicator)progressIndicator;
 615       if (indicator.getDumbModeAction() == DumbModeAction.WAIT) {
 616         assert !ApplicationManager.getApplication().isDispatchThread();
 617         DumbService.getInstance(project).waitForSmartMode();
 618         return;
 619       }
 620     }
 621
 622     throw new IndexNotReadyException();
 623   }
 624
 625   private static boolean isDumb(Project project) {
 626     return DumbServiceImpl.getInstance(project).isDumb();
 627   }
 628
 629   @NotNull
 630   public <K, V> List<V> getValues(final ID<K, V> indexId, @NotNull K dataKey, @NotNull final GlobalSearchScope filter) {
 631     final List<V> values = new ArrayList<V>();
 632     processValuesImpl(indexId, dataKey, true, null, new ValueProcessor<V>() {
 633       public boolean process(final VirtualFile file, final V value) {
 634         values.add(value);
 635         return true;
 636       }
 637     }, filter);
 638     return values;
 639   }
 640
 641   @NotNull
 642   public <K, V> Collection<VirtualFile> getContainingFiles(final ID<K, V> indexId, @NotNull K dataKey, @NotNull final GlobalSearchScope filter) {
 643     final Set<VirtualFile> files = new HashSet<VirtualFile>();
 644     processValuesImpl(indexId, dataKey, false, null, new ValueProcessor<V>() {
 645       public boolean process(final VirtualFile file, final V value) {
 646         files.add(file);
 647         return true;
 648       }
 649     }, filter);
 650     return files;
 651   }
 652
 653
 654   public interface ValueProcessor<V> {
 655     /**
 656      * @param value a value to process
 657      * @param file the file the value came from
 658      * @return false if no further processing is needed, true otherwise
 659      */
 660     boolean process(VirtualFile file, V value);
 661   }
 662
 663   /**
 664    * @return false if ValueProcessor.process() returned false; true otherwise or if ValueProcessor was not called at all
 665    */
 666   public <K, V> boolean processValues(final ID<K, V> indexId, final @NotNull K dataKey, @Nullable final VirtualFile inFile,
 667                                    ValueProcessor<V> processor, @NotNull final GlobalSearchScope filter) {
 668     return processValuesImpl(indexId, dataKey, false, inFile, processor, filter);
 669   }
 670
 671
 672
 673   private <K, V> boolean processValuesImpl(final ID<K, V> indexId, final K dataKey, boolean ensureValueProcessedOnce,
 674                                         @Nullable final VirtualFile restrictToFile, ValueProcessor<V> processor,
 675                                         final GlobalSearchScope filter) {
 676     try {
 677       final Project project = filter.getProject();
 678       assert project != null : "GlobalSearchScope#getProject() should be not-null for all index queries";
 679       ensureUpToDate(indexId, project, filter);
 680       final UpdatableIndex<K, V, FileContent> index = getIndex(indexId);
 681       if (index == null) {
 682         return true;
 683       }
 684
 685       final Lock readLock = index.getReadLock();
 686       try {
 687         readLock.lock();
 688         final ValueContainer<V> container = index.getData(dataKey);
 689
 690         boolean shouldContinue = true;
 691
 692         if (restrictToFile != null) {
 693           if (restrictToFile instanceof VirtualFileWithId) {
 694             final int restrictedFileId = getFileId(restrictToFile);
 695             for (final Iterator<V> valueIt = container.getValueIterator(); valueIt.hasNext();) {
 696               final V value = valueIt.next();
 697               if (container.isAssociated(value, restrictedFileId)) {
 698                 shouldContinue = processor.process(restrictToFile, value);
 699                 if (!shouldContinue) {
 700                   break;
 701                 }
 702               }
 703             }
 704           }
 705         }
 706         else {
 707           final PersistentFS fs = (PersistentFS)ManagingFS.getInstance();
 708           VALUES_LOOP: for (final Iterator<V> valueIt = container.getValueIterator(); valueIt.hasNext();) {
 709             final V value = valueIt.next();
 710             for (final ValueContainer.IntIterator inputIdsIterator = container.getInputIdsIterator(value); inputIdsIterator.hasNext();) {
 711               final int id = inputIdsIterator.next();
 712               VirtualFile file = IndexInfrastructure.findFileById(fs, id);
 713               if (file != null && filter.accept(file)) {
 714                 shouldContinue = processor.process(file, value);
 715                 if (!shouldContinue) {
 716                   break VALUES_LOOP;
 717                 }
 718                 if (ensureValueProcessedOnce) {
 719                   break; // continue with the next value
 720                 }
 721               }
 722             }
 723           }
 724         }
 725         return shouldContinue;
 726       }
 727       finally {
 728         index.getReadLock().unlock();
 729       }
 730     }
 731     catch (StorageException e) {
 732       scheduleRebuild(indexId, e);
 733     }
 734     catch (RuntimeException e) {
 735       final Throwable cause = e.getCause();
 736       if (cause instanceof StorageException || cause instanceof IOException) {
 737         scheduleRebuild(indexId, cause);
 738       }
 739       else {
 740         throw e;
 741       }
 742     }
 743     return true;
 744   }
 745
 746   public <K, V> boolean getFilesWithKey(final ID<K, V> indexId, final Set<K> dataKeys,
 747                                          Processor<VirtualFile> processor,
 748                                          GlobalSearchScope filter) {
 749     try {
 750       final Project project = filter.getProject();
 751       assert project != null : "GlobalSearchScope#getProject() should be not-null for all index queries";
 752       ensureUpToDate(indexId, project, filter);
 753       final UpdatableIndex<K, V, FileContent> index = getIndex(indexId);
 754       if (index == null) {
 755         return true;
 756       }
 757
 758       final Lock readLock = index.getReadLock();
 759       try {
 760         readLock.lock();
 761         List<TIntHashSet> locals = new ArrayList<TIntHashSet>();
 762         for (K dataKey : dataKeys) {
 763           TIntHashSet local = new TIntHashSet();
 764           locals.add(local);
 765           final ValueContainer<V> container = index.getData(dataKey);
 766
 767           for (final Iterator<V> valueIt = container.getValueIterator(); valueIt.hasNext();) {
 768             final V value = valueIt.next();
 769             for (final ValueContainer.IntIterator inputIdsIterator = container.getInputIdsIterator(value); inputIdsIterator.hasNext();) {
 770               final int id = inputIdsIterator.next();
 771               local.add(id);
 772             }
 773           }
 774         }
 775
 776         if (locals.size() == 0) return true;
 777
 778         Collections.sort(locals, new Comparator<TIntHashSet>() {
 779           public int compare(TIntHashSet o1, TIntHashSet o2) {
 780             return o1.size() - o2.size();
 781           }
 782         });
 783
 784         final PersistentFS fs = (PersistentFS)ManagingFS.getInstance();
 785         TIntIterator ids = join(locals).iterator();
 786         while (ids.hasNext()) {
 787           int id = ids.next();
 788           VirtualFile file = IndexInfrastructure.findFileById(fs, id);
 789           if (file != null && filter.accept(file)) {
 790             if (!processor.process(file)) return false;
 791           }
 792         }
 793       }
 794       finally {
 795         index.getReadLock().unlock();
 796       }
 797     }
 798     catch (StorageException e) {
 799       scheduleRebuild(indexId, e);
 800     }
 801     catch (RuntimeException e) {
 802       final Throwable cause = e.getCause();
 803       if (cause instanceof StorageException || cause instanceof IOException) {
 804         scheduleRebuild(indexId, cause);
 805       }
 806       else {
 807         throw e;
 808       }
 809     }
 810     return true;
 811   }
 812
 813   private static TIntHashSet join(List<TIntHashSet> locals) {
 814     TIntHashSet result = locals.get(0);
 815     if (locals.size() > 1) {
 816       TIntIterator it = result.iterator();
 817
 818       while (it.hasNext()) {
 819         int id = it.next();
 820         for (int i = 1; i < locals.size(); i++) {
 821           if (!locals.get(i).contains(id)) {
 822             it.remove();
 823             break;
 824           }
 825         }
 826       }
 827     }
 828     return result;
 829   }
 830
 831   public interface AllValuesProcessor<V> {
 832     void process(final int inputId, V value);
 833   }
 834
 835   public <K, V> void processAllValues(final ID<K, V> indexId, AllValuesProcessor<V> processor, @NotNull Project project) {
 836     try {
 837       ensureUpToDate(indexId, project, null);
 838       final UpdatableIndex<K, V, FileContent> index = getIndex(indexId);
 839       if (index == null) {
 840         return;
 841       }
 842       try {
 843         index.getReadLock().lock();
 844         for (K dataKey : index.getAllKeys()) {
 845           final ValueContainer<V> container = index.getData(dataKey);
 846           for (final Iterator<V> it = container.getValueIterator(); it.hasNext();) {
 847             final V value = it.next();
 848             for (final ValueContainer.IntIterator inputsIt = container.getInputIdsIterator(value); inputsIt.hasNext();) {
 849               processor.process(inputsIt.next(), value);
 850             }
 851           }
 852         }
 853       }
 854       finally {
 855         index.getReadLock().unlock();
 856       }
 857     }
 858     catch (StorageException e) {
 859       scheduleRebuild(indexId, e);
 860     }
 861     catch (RuntimeException e) {
 862       final Throwable cause = e.getCause();
 863       if (cause instanceof StorageException || cause instanceof IOException) {
 864         scheduleRebuild(indexId, e);
 865       }
 866       else {
 867         throw e;
 868       }
 869     }
 870   }
 871
 872   private <K> void scheduleRebuild(final ID<K, ?> indexId, final Throwable e) {
 873     requestRebuild(indexId);
 874     LOG.info(e);
 875     checkRebuild(indexId, false);
 876   }
 877
 878   @TestOnly
 879   public boolean isIndexReady(final ID<?, ?> indexId) {
 880     return myRebuildStatus.get(indexId).get() == OK;
 881   }
 882
 883   private void checkRebuild(final ID<?, ?> indexId, final boolean cleanupOnly) {
 884     if (myRebuildStatus.get(indexId).compareAndSet(REQUIRES_REBUILD, REBUILD_IN_PROGRESS)) {
 885       cleanupProcessedFlag();
 886
 887       final Runnable rebuildRunnable = new Runnable() {
 888         public void run() {
 889           try {
 890             clearIndex(indexId);
 891             if (!cleanupOnly) {
 892               final FileSystemSynchronizerImpl synchronizer = new FileSystemSynchronizerImpl();
 893               synchronizer.setCancelable(false);
 894               for (Project project : ProjectManager.getInstance().getOpenProjects()) {
 895                 synchronizer.registerCacheUpdater(new UnindexedFilesUpdater(project, ProjectRootManager.getInstance(project), FileBasedIndex.this));
 896               }
 897               synchronizer.executeFileUpdate();
 898             }
 899           }
 900           catch (StorageException e) {
 901             requestRebuild(indexId);
 902             LOG.info(e);
 903           }
 904           finally {
 905             myRebuildStatus.get(indexId).compareAndSet(REBUILD_IN_PROGRESS, OK);
 906           }
 907         }
 908       };
 909
 910       final Application application = ApplicationManager.getApplication();
 911       if (cleanupOnly || application.isUnitTestMode()) {
 912         rebuildRunnable.run();
 913       }
 914       else {
 915         SwingUtilities.invokeLater(new Runnable() {
 916           public void run() {
 917             new Task.Modal(null, "Updating index", false) {
 918               public void run(@NotNull final ProgressIndicator indicator) {
 919                 indicator.setIndeterminate(true);
 920                 rebuildRunnable.run();
 921               }
 922             }.queue();
 923           }
 924         });
 925       }
 926     }
 927
 928     if (myRebuildStatus.get(indexId).get() == REBUILD_IN_PROGRESS) {
 929       throw new ProcessCanceledException();
 930     }
 931   }
 932
 933   private void clearIndex(final ID<?, ?> indexId) throws StorageException {
 934     final UpdatableIndex<?, ?, FileContent> index = getIndex(indexId);
 935     assert index != null;
 936     index.clear();
 937     try {
 938       IndexInfrastructure.rewriteVersion(IndexInfrastructure.getVersionFile(indexId), myIndexIdToVersionMap.get(indexId));
 939     }
 940     catch (IOException e) {
 941       LOG.error(e);
 942     }
 943   }
 944
 945   private Set<Document> getUnsavedOrTransactedDocuments() {
 946     Set<Document> docs = new HashSet<Document>(Arrays.asList(myFileDocumentManager.getUnsavedDocuments()));
 947     docs.addAll(myTransactionMap.keySet());
 948     return docs;
 949   }
 950
 951   private void indexUnsavedDocuments(ID<?, ?> indexId, Project project, GlobalSearchScope filter) throws StorageException {
 952
 953     if (myUpToDateIndices.contains(indexId)) {
 954       return; // no need to index unsaved docs
 955     }
 956
 957     final Set<Document> documents = getUnsavedOrTransactedDocuments();
 958     if (!documents.isEmpty()) {
 959       // now index unsaved data
 960       final StorageGuard.Holder guard = setDataBufferingEnabled(true);
 961       try {
 962         boolean allDocsProcessed = true;
 963         final Semaphore semaphore = myUnsavedDataIndexingSemaphores.get(indexId);
 964         semaphore.down();
 965         try {
 966           for (Document document : documents) {
 967             allDocsProcessed &= indexUnsavedDocument(document, indexId, project, filter);
 968           }
 969         }
 970         finally {
 971           semaphore.up();
 972
 973           while (!semaphore.waitFor(500)) { // may need to wait until another thread is done with indexing
 974             if (Thread.holdsLock(PsiLock.LOCK)) {
 975               break; // hack. Most probably that other indexing threads is waiting for PsiLock, which we're are holding.
 976             }
 977           }
 978           if (allDocsProcessed) {
 979             myUpToDateIndices.add(indexId); // safe to set the flag here, becase it will be cleared under the WriteAction
 980           }
 981         }
 982       }
 983       finally {
 984         guard.leave();
 985       }
 986     }
 987   }
 988
 989   private interface DocumentContent {
 990     String getText();
 991     long getModificationStamp();
 992   }
 993
 994   private static class AuthenticContent implements DocumentContent {
 995     private final Document myDocument;
 996
 997     private AuthenticContent(final Document document) {
 998       myDocument = document;
 999     }
1000
1001     public String getText() {
1002       return myDocument.getText();
1003     }
1004
1005     public long getModificationStamp() {
1006       return myDocument.getModificationStamp();
1007     }
1008   }
1009
1010   private static class PsiContent implements DocumentContent {
1011     private final Document myDocument;
1012     private final PsiFile myFile;
1013
1014     private PsiContent(final Document document, final PsiFile file) {
1015       myDocument = document;
1016       myFile = file;
1017     }
1018
1019     public String getText() {
1020       if (myFile.getModificationStamp() != myDocument.getModificationStamp()) {
1021         final ASTNode node = myFile.getNode();
1022         assert node != null;
1023         return node.getText();
1024       }
1025       return myDocument.getText();
1026     }
1027
1028     public long getModificationStamp() {
1029       return myFile.getModificationStamp();
1030     }
1031   }
1032
1033   // returns false if doc was not indexed because the file does not fit in scope
1034   private boolean indexUnsavedDocument(final Document document, final ID<?, ?> requestedIndexId, Project project, GlobalSearchScope filter) throws StorageException {
1035     final VirtualFile vFile = myFileDocumentManager.getFile(document);
1036     if (!(vFile instanceof VirtualFileWithId) || !vFile.isValid()) {
1037       return true;
1038     }
1039     if (filter != null && !filter.accept(vFile)) {
1040       return false;
1041     }
1042     final PsiFile dominantContentFile = findDominantPsiForDocument(document, project);
1043
1044     DocumentContent content;
1045     if (dominantContentFile != null && dominantContentFile.getModificationStamp() != document.getModificationStamp()) {
1046       content = new PsiContent(document, dominantContentFile);
1047     }
1048     else {
1049       content = new AuthenticContent(document);
1050     }
1051
1052     final long currentDocStamp = content.getModificationStamp();
1053     if (currentDocStamp != myLastIndexedDocStamps.getAndSet(document, requestedIndexId, currentDocStamp).longValue()) {
1054       final FileContent newFc = new FileContent(vFile, content.getText(), vFile.getCharset());
1055
1056       if (dominantContentFile != null) {
1057         dominantContentFile.putUserData(PsiFileImpl.BUILDING_STUB, true);
1058         newFc.putUserData(PSI_FILE, dominantContentFile);
1059       }
1060
1061       if (content instanceof AuthenticContent) {
1062         newFc.putUserData(EDITOR_HIGHLIGHTER, document instanceof DocumentImpl
1063                                               ? ((DocumentImpl)document).getEditorHighlighterForCachesBuilding() : null);
1064       }
1065
1066       if (getInputFilter(requestedIndexId).acceptInput(vFile)) {
1067         newFc.putUserData(PROJECT, project);
1068         final int inputId = Math.abs(getFileId(vFile));
1069         getIndex(requestedIndexId).update(inputId, newFc);
1070       }
1071
1072       if (dominantContentFile != null) {
1073         dominantContentFile.putUserData(PsiFileImpl.BUILDING_STUB, null);
1074       }
1075     }
1076     return true;
1077   }
1078
1079   public static final Key<PsiFile> PSI_FILE = new Key<PsiFile>("PSI for stubs");
1080   public static final Key<EditorHighlighter> EDITOR_HIGHLIGHTER = new Key<EditorHighlighter>("Editor");
1081   public static final Key<Project> PROJECT = new Key<Project>("Context project");
1082   public static final Key<VirtualFile> VIRTUAL_FILE = new Key<VirtualFile>("Context virtual file");
1083
1084   @Nullable
1085   private PsiFile findDominantPsiForDocument(final Document document, Project project) {
1086     if (myTransactionMap.containsKey(document)) {
1087       return myTransactionMap.get(document);
1088     }
1089
1090     return findLatestKnownPsiForUncomittedDocument(document, project);
1091   }
1092
1093   private final StorageGuard myStorageLock = new StorageGuard();
1094
1095   private StorageGuard.Holder setDataBufferingEnabled(final boolean enabled) {
1096     final StorageGuard.Holder holder = myStorageLock.enter(enabled);
1097     for (ID<?, ?> indexId : myIndices.keySet()) {
1098       final MapReduceIndex index = (MapReduceIndex)getIndex(indexId);
1099       assert index != null;
1100       final IndexStorage indexStorage = index.getStorage();
1101       ((MemoryIndexStorage)indexStorage).setBufferingEnabled(enabled);
1102     }
1103     return holder;
1104   }
1105
1106   private void cleanupMemoryStorage() {
1107     synchronized (myLastIndexedDocStamps) {
1108       myLastIndexedDocStamps.clear();
1109     }
1110     for (ID<?, ?> indexId : myIndices.keySet()) {
1111       final MapReduceIndex index = (MapReduceIndex)getIndex(indexId);
1112       assert index != null;
1113       final MemoryIndexStorage memStorage = (MemoryIndexStorage)index.getStorage();
1114       index.getWriteLock().lock();
1115       try {
1116         memStorage.clearMemoryMap();
1117       }
1118       finally {
1119         index.getWriteLock().unlock();
1120       }
1121       memStorage.fireMemoryStorageCleared();
1122     }
1123   }
1124
1125   private void dropUnregisteredIndices() {
1126     final Set<String> indicesToDrop = readRegistsredIndexNames();
1127     for (ID<?, ?> key : myIndices.keySet()) {
1128       indicesToDrop.remove(key.toString());
1129     }
1130     for (String s : indicesToDrop) {
1131       FileUtil.delete(IndexInfrastructure.getIndexRootDir(ID.create(s)));
1132     }
1133   }
1134
1135   public void requestRebuild(ID<?, ?> indexId) {
1136     requestRebuild(indexId, new Throwable());
1137   }
1138
1139   public void requestRebuild(ID<?, ?> indexId, Throwable throwable) {
1140     cleanupProcessedFlag();
1141     LOG.info("Rebuild requested for index " + indexId, throwable);
1142     myRebuildStatus.get(indexId).set(REQUIRES_REBUILD);
1143   }
1144
1145   private <K, V> UpdatableIndex<K, V, FileContent> getIndex(ID<K, V> indexId) {
1146     final Pair<UpdatableIndex<?, ?, FileContent>, InputFilter> pair = myIndices.get(indexId);
1147     //noinspection unchecked
1148     return pair != null? (UpdatableIndex<K,V, FileContent>)pair.getFirst() : null;
1149   }
1150
1151   private InputFilter getInputFilter(ID<?, ?> indexId) {
1152     final Pair<UpdatableIndex<?, ?, FileContent>, InputFilter> pair = myIndices.get(indexId);
1153     return pair != null? pair.getSecond() : null;
1154   }
1155
1156   public void indexFileContent(com.intellij.ide.startup.FileContent content) {
1157     myChangedFilesUpdater.ensureAllInvalidateTasksCompleted();
1158     final VirtualFile file = content.getVirtualFile();
1159     FileContent fc = null;
1160
1161     PsiFile psiFile = null;
1162
1163     final Ref<ProcessCanceledException> pce = Ref.create(null);
1164
1165     final List<Runnable> tasks = new ArrayList<Runnable>();
1166     for (final ID<?, ?> indexId : myIndices.keySet()) {
1167       if (shouldIndexFile(file, indexId)) {
1168         if (fc == null) {
1169           byte[] currentBytes;
1170           try {
1171             currentBytes = content.getBytes();
1172           }
1173           catch (IOException e) {
1174             currentBytes = ArrayUtil.EMPTY_BYTE_ARRAY;
1175           }
1176           fc = new FileContent(file, currentBytes);
1177
1178           psiFile = content.getUserData(PSI_FILE);
1179           if (psiFile != null) {
1180             psiFile.putUserData(PsiFileImpl.BUILDING_STUB, true);
1181             fc.putUserData(PSI_FILE, psiFile);
1182           }
1183           Project project = content.getUserData(PROJECT);
1184           if (project == null) {
1185             project = ProjectUtil.guessProjectForFile(file);
1186           }
1187           fc.putUserData(PROJECT, project);
1188         }
1189
1190         final FileContent _fc = fc;
1191         tasks.add(new Runnable() {
1192           public void run() {
1193             try {
1194               updateSingleIndex(indexId, file, _fc);
1195             }
1196             catch (ProcessCanceledException e) {
1197               pce.set(e);
1198             }
1199             catch (StorageException e) {
1200               requestRebuild(indexId);
1201               LOG.info(e);
1202             }
1203           }
1204         });
1205       }
1206     }
1207
1208     if (tasks.size() > 0) {
1209       if (Registry.get(USE_MULTITHREADED_INDEXING).asBoolean()) {
1210         final Job<Object> job = JobScheduler.getInstance().createJob("IndexJob", Job.DEFAULT_PRIORITY / 2);
1211         try {
1212           for (Runnable task : tasks) {
1213             job.addTask(task);
1214           }
1215           job.scheduleAndWaitForResults();
1216         }
1217         catch (Throwable throwable) {
1218           LOG.info(throwable);
1219         }
1220       }
1221       else {
1222         for (Runnable task : tasks) {
1223           task.run();
1224         }
1225       }
1226     }
1227
1228     if (!pce.isNull()) {
1229       myChangedFilesUpdater.scheduleForUpdate(file);
1230       throw pce.get();
1231     }
1232
1233     if (psiFile != null) {
1234       psiFile.putUserData(PsiFileImpl.BUILDING_STUB, null);
1235     }
1236   }
1237
1238   private void updateSingleIndex(final ID<?, ?> indexId, final VirtualFile file, final FileContent currentFC)
1239     throws StorageException {
1240     if (myRebuildStatus.get(indexId).get() == REQUIRES_REBUILD) {
1241       return; // the index is scheduled for rebuild, no need to update
1242     }
1243
1244     final StorageGuard.Holder lock = setDataBufferingEnabled(false);
1245
1246     try {
1247       final int inputId = Math.abs(getFileId(file));
1248
1249       final UpdatableIndex<?, ?, FileContent> index = getIndex(indexId);
1250       assert index != null;
1251
1252       index.update(inputId, currentFC);
1253       ApplicationManager.getApplication().runReadAction(new Runnable() {
1254         public void run() {
1255           if (file.isValid()) {
1256             if (currentFC != null) {
1257               IndexingStamp.update(file, indexId, IndexInfrastructure.getIndexCreationStamp(indexId));
1258             }
1259             else {
1260               // mark the file as unindexed
1261               IndexingStamp.update(file, indexId, -1L);
1262             }
1263           }
1264         }
1265       });
1266     }
1267     finally {
1268       lock.leave();
1269     }
1270   }
1271
1272   public static int getFileId(final VirtualFile file) {
1273     if (file instanceof VirtualFileWithId) {
1274       return ((VirtualFileWithId)file).getId();
1275     }
1276
1277     throw new IllegalArgumentException("Virtual file doesn't support id: " + file + ", implementation class: " + file.getClass().getName());
1278   }
1279
1280   private boolean needsFileContentLoading(ID<?, ?> indexId) {
1281     return !myNotRequiringContentIndices.contains(indexId);
1282   }
1283
1284   private abstract static class InvalidationTask implements Runnable {
1285     private final VirtualFile mySubj;
1286
1287     protected InvalidationTask(final VirtualFile subj) {
1288       mySubj = subj;
1289     }
1290
1291     public VirtualFile getSubj() {
1292       return mySubj;
1293     }
1294   }
1295
1296   private final class ChangedFilesUpdater extends VirtualFileAdapter implements BackgroundableCacheUpdater {
1297     private final Set<VirtualFile> myFilesToUpdate = new LinkedHashSet<VirtualFile>();
1298     private final Queue<InvalidationTask> myFutureInvalidations = new LinkedList<InvalidationTask>();
1299     private final JBReentrantReadWriteLock myLock = LockFactory.createReadWriteLock();
1300     private final JBLock r = myLock.readLock();
1301     private final JBLock w = myLock.writeLock();
1302
1303     private final ManagingFS myManagingFS = ManagingFS.getInstance();
1304     // No need to react on movement events since files stay valid, their ids don't change and all associated attributes remain intact.
1305
1306     public void fileCreated(final VirtualFileEvent event) {
1307       markDirty(event);
1308     }
1309
1310     public void fileDeleted(final VirtualFileEvent event) {
1311       w.lock();
1312       try {
1313         myFilesToUpdate.remove(event.getFile()); // no need to update it anymore
1314       }
1315       finally {
1316         w.unlock();
1317       }
1318     }
1319
1320     public void fileCopied(final VirtualFileCopyEvent event) {
1321       markDirty(event);
1322     }
1323
1324     public void beforeFileDeletion(final VirtualFileEvent event) {
1325       invalidateIndices(event.getFile(), false);
1326     }
1327
1328     public void beforeContentsChange(final VirtualFileEvent event) {
1329       invalidateIndices(event.getFile(), true);
1330     }
1331
1332     public void contentsChanged(final VirtualFileEvent event) {
1333       markDirty(event);
1334     }
1335
1336     public void beforePropertyChange(final VirtualFilePropertyEvent event) {
1337       if (event.getPropertyName().equals(VirtualFile.PROP_NAME)) {
1338         // indexes may depend on file name
1339         final VirtualFile file = event.getFile();
1340         if (!file.isDirectory()) {
1341           // name change may lead to filetype change so the file might become not indexable
1342           // in general case have to 'unindex' the file and index it again if needed after the name has been changed
1343           invalidateIndices(file, false);
1344         }
1345       }
1346     }
1347
1348     public void propertyChanged(final VirtualFilePropertyEvent event) {
1349       if (event.getPropertyName().equals(VirtualFile.PROP_NAME)) {
1350         // indexes may depend on file name
1351         if (!event.getFile().isDirectory()) {
1352           markDirty(event);
1353         }
1354       }
1355     }
1356
1357     private void markDirty(final VirtualFileEvent event) {
1358       cleanProcessedFlag(event.getFile());
1359       iterateIndexableFiles(event.getFile(), new Processor<VirtualFile>() {
1360         public boolean process(final VirtualFile file) {
1361           FileContent fileContent = null;
1362           // handle 'content-less' indices separately
1363           for (ID<?, ?> indexId : myNotRequiringContentIndices) {
1364             if (getInputFilter(indexId).acceptInput(file)) {
1365               try {
1366                 if (fileContent == null) {
1367                   fileContent = new FileContent(file);
1368                 }
1369                 updateSingleIndex(indexId, file, fileContent);
1370               }
1371               catch (StorageException e) {
1372                 LOG.info(e);
1373                 requestRebuild(indexId);
1374               }
1375             }
1376           }
1377           // For 'normal indices' schedule the file for update and stop iteration if at least one index accepts it
1378           if (!isTooLarge(file)) {
1379             for (ID<?, ?> indexId : myIndices.keySet()) {
1380               if (needsFileContentLoading(indexId) && getInputFilter(indexId).acceptInput(file)) {
1381                 scheduleForUpdate(file);
1382                 break; // no need to iterate further, as the file is already marked
1383               }
1384             }
1385           }
1386
1387           return true;
1388         }
1389       });
1390       IndexingStamp.flushCache();
1391     }
1392
1393     public void scheduleForUpdate(VirtualFile file) {
1394       w.lock();
1395       try {
1396         myFilesToUpdate.add(file);
1397       }
1398       finally {
1399         w.unlock();
1400       }
1401     }
1402
1403     void invalidateIndices(final VirtualFile file, final boolean markForReindex) {
1404       if (isUnderConfigOrSystem(file)) {
1405         return;
1406       }
1407       if (file.isDirectory()) {
1408         if (isMock(file) || myManagingFS.wereChildrenAccessed(file)) {
1409           final Collection<VirtualFile> children = (file instanceof NewVirtualFile)? ((NewVirtualFile)file).getInDbChildren() : Arrays.asList(file.getChildren());
1410           for (VirtualFile child : children) {
1411             if (NullVirtualFile.INSTANCE != child) {
1412               invalidateIndices(child, markForReindex);
1413             }
1414           }
1415         }
1416       }
1417       else {
1418         cleanProcessedFlag(file);
1419         IndexingStamp.flushCache();
1420         final List<ID<?, ?>> affectedIndices = new ArrayList<ID<?, ?>>(myIndices.size());
1421
1422         final boolean isTooLarge = isTooLarge(file);
1423         for (final ID<?, ?> indexId : myIndices.keySet()) {
1424           try {
1425             if (myNotRequiringContentIndices.contains(indexId)) {
1426               if (shouldUpdateIndex(file, indexId)) {
1427                 updateSingleIndex(indexId, file, null);
1428               }
1429             }
1430             else { // the index requires file content
1431               if (!isTooLarge && shouldUpdateIndex(file, indexId)) {
1432                 affectedIndices.add(indexId);
1433               }
1434             }
1435           }
1436           catch (StorageException e) {
1437             LOG.info(e);
1438             requestRebuild(indexId);
1439           }
1440         }
1441
1442         if (affectedIndices.size() > 0) {
1443           if (markForReindex) {
1444             // only mark the file as unindexed, reindex will be done lazily
1445             ApplicationManager.getApplication().runReadAction(new Runnable() {
1446               public void run() {
1447                 for (ID<?, ?> indexId : affectedIndices) {
1448                   IndexingStamp.update(file, indexId, -1L);
1449                 }
1450               }
1451             });
1452             iterateIndexableFiles(file, new Processor<VirtualFile>() {
1453               public boolean process(final VirtualFile file) {
1454                 scheduleForUpdate(file);
1455                 return true;
1456               }
1457             });
1458           }
1459           else {
1460             final InvalidationTask invalidator = new InvalidationTask(file) {
1461               public void run() {
1462                 Throwable unexpectedError = null;
1463                 for (ID<?, ?> indexId : affectedIndices) {
1464                   try {
1465                     updateSingleIndex(indexId, file, null);
1466                   }
1467                   catch (StorageException e) {
1468                     LOG.info(e);
1469                     requestRebuild(indexId);
1470                   }
1471                   catch (ProcessCanceledException ignored) {
1472                   }
1473                   catch (Throwable e) {
1474                     LOG.info(e);
1475                     if (unexpectedError == null) {
1476                       unexpectedError = e;
1477                     }
1478                   }
1479                 }
1480                 IndexingStamp.flushCache();
1481                 if (unexpectedError != null) {
1482                   LOG.error(unexpectedError);
1483                 }
1484               }
1485             };
1486
1487             w.lock();
1488             try {
1489               myFutureInvalidations.offer(invalidator);
1490             }
1491             finally {
1492               w.unlock();
1493             }
1494           }
1495         }
1496         IndexingStamp.flushCache();
1497       }
1498     }
1499
1500     public void ensureAllInvalidateTasksCompleted() {
1501       final int size;
1502       r.lock();
1503       try {
1504         size = myFutureInvalidations.size();
1505         if (size == 0) return;
1506       }
1507       finally {
1508         r.unlock();
1509       }
1510       final ProgressIndicator current = ProgressManager.getInstance().getProgressIndicator();
1511       final ProgressIndicator indicator = current != null ? current : new EmptyProgressIndicator();
1512       indicator.setText("");
1513       int count = 0;
1514       while (true) {
1515         InvalidationTask task;
1516         w.lock();
1517         try {
1518           task = myFutureInvalidations.poll();
1519         }
1520         finally {
1521           w.unlock();
1522         }
1523
1524         if (task == null) {
1525           break;
1526         }
1527         indicator.setFraction(((double)count++)/size);
1528         indicator.setText2(task.getSubj().getPresentableUrl());
1529         task.run();
1530       }
1531     }
1532
1533     private void iterateIndexableFiles(final VirtualFile file, final Processor<VirtualFile> processor) {
1534       if (file.isDirectory()) {
1535         final ContentIterator iterator = new ContentIterator() {
1536           public boolean processFile(final VirtualFile fileOrDir) {
1537             if (!fileOrDir.isDirectory()) {
1538               processor.process(fileOrDir);
1539             }
1540             return true;
1541           }
1542         };
1543
1544         for (IndexableFileSet set : myIndexableSets) {
1545           set.iterateIndexableFilesIn(file, iterator);
1546         }
1547       }
1548       else {
1549         for (IndexableFileSet set : myIndexableSets) {
1550           if (set.isInSet(file)) {
1551             processor.process(file);
1552             break;
1553           }
1554         }
1555       }
1556     }
1557
1558     public boolean initiallyBackgrounded() {
1559       if (ApplicationManager.getApplication().isCommandLine() || ApplicationManager.getApplication().isUnitTestMode()) {
1560         return false;
1561       }
1562       return Registry.get(DumbServiceImpl.FILE_INDEX_BACKGROUND).asBoolean();
1563     }
1564
1565     public boolean canBeSentToBackground(Collection<VirtualFile> remaining) {
1566       return true;
1567     }
1568
1569     public void backgrounded(Collection<VirtualFile> remaining) {
1570       new BackgroundCacheUpdaterRunner(remaining).processFiles(this);
1571     }
1572
1573     public VirtualFile[] queryNeededFiles() {
1574       r.lock();
1575       try {
1576         if (myFilesToUpdate.isEmpty()) {
1577           return VirtualFile.EMPTY_ARRAY;
1578         }
1579         return myFilesToUpdate.toArray(new VirtualFile[myFilesToUpdate.size()]);
1580       }
1581       finally {
1582         r.unlock();
1583       }
1584     }
1585
1586     public void processFile(final com.intellij.ide.startup.FileContent fileContent) {
1587       myChangedFilesUpdater.ensureAllInvalidateTasksCompleted();
1588       processFileImpl(fileContent);
1589     }
1590
1591     private final Semaphore myForceUpdateSemaphore = new Semaphore();
1592
1593     public void forceUpdate(@Nullable GlobalSearchScope filter) {
1594       myChangedFilesUpdater.ensureAllInvalidateTasksCompleted();
1595       final VirtualFile[] files = queryNeededFiles();
1596       if (files.length > 0) {
1597         for (VirtualFile file: files) {
1598           if (filter == null || filter.accept(file)) {
1599             try {
1600               myForceUpdateSemaphore.down();
1601               // process only files that can affect result
1602               processFileImpl(new com.intellij.ide.startup.FileContent(file));
1603             }
1604             finally {
1605               myForceUpdateSemaphore.up();
1606             }
1607           }
1608         }
1609       }
1610
1611       // If several threads entered the method at the same time and there were files to update,
1612       // all the threads should leave the method synchronously after all the files scheduled for update are reindexed,
1613       // no matter which thread will do reindexing job.
1614       // Thus we ensure that all the threads that entered the method will get the most recent data
1615
1616       while (!myForceUpdateSemaphore.waitFor(500)) { // may need to wait until another thread is done with indexing
1617         if (Thread.holdsLock(PsiLock.LOCK)) {
1618           break; // hack. Most probably that other indexing threads is waiting for PsiLock, which we're are holding.
1619         }
1620       }
1621     }
1622
1623     public void updatingDone() {
1624     }
1625
1626     public void canceled() {
1627     }
1628
1629     private void processFileImpl(final com.intellij.ide.startup.FileContent fileContent) {
1630       final VirtualFile file = fileContent.getVirtualFile();
1631       final boolean reallyRemoved;
1632       w.lock();
1633       try {
1634         reallyRemoved = myFilesToUpdate.remove(file);
1635       }
1636       finally {
1637         w.unlock();
1638       }
1639       if (reallyRemoved && file.isValid()) {
1640         indexFileContent(fileContent);
1641         IndexingStamp.flushCache();
1642       }
1643     }
1644   }
1645
1646   private class UnindexedFilesFinder implements CollectingContentIterator {
1647     private final List<VirtualFile> myFiles = new ArrayList<VirtualFile>();
1648     private final ProgressIndicator myProgressIndicator;
1649
1650     private UnindexedFilesFinder() {
1651       myProgressIndicator = ProgressManager.getInstance().getProgressIndicator();
1652     }
1653
1654     public List<VirtualFile> getFiles() {
1655       return myFiles;
1656     }
1657
1658     public boolean processFile(final VirtualFile file) {
1659       if (!file.isDirectory()) {
1660         if (file instanceof NewVirtualFile && ((NewVirtualFile)file).getFlag(ALREADY_PROCESSED)) {
1661           return true;
1662         }
1663
1664         if (file instanceof VirtualFileWithId) {
1665           boolean oldStuff = true;
1666           if (!isTooLarge(file)) {
1667             for (ID<?, ?> indexId : myIndices.keySet()) {
1668               try {
1669                 if (shouldIndexFile(file, indexId)) {
1670                   myFiles.add(file);
1671                   oldStuff = false;
1672                   break;
1673                 }
1674               }
1675               catch (RuntimeException e) {
1676                 final Throwable cause = e.getCause();
1677                 if (cause instanceof IOException || cause instanceof StorageException) {
1678                   LOG.info(e);
1679                   requestRebuild(indexId);
1680                 }
1681                 else {
1682                   throw e;
1683                 }
1684               }
1685             }
1686           }
1687           FileContent fileContent = null;
1688           for (ID<?, ?> indexId : myNotRequiringContentIndices) {
1689             if (shouldIndexFile(file, indexId)) {
1690               oldStuff = false;
1691               try {
1692                 if (fileContent == null) {
1693                   fileContent = new FileContent(file);
1694                 }
1695                 updateSingleIndex(indexId, file, fileContent);
1696               }
1697               catch (StorageException e) {
1698                 LOG.info(e);
1699                 requestRebuild(indexId);
1700               }
1701             }
1702           }
1703           IndexingStamp.flushCache();
1704
1705           if (oldStuff && file instanceof NewVirtualFile) {
1706             ((NewVirtualFile)file).setFlag(ALREADY_PROCESSED, true);
1707           }
1708         }
1709       }
1710       else {
1711         if (myProgressIndicator != null) {
1712           myProgressIndicator.setText("Scanning files to index");
1713           myProgressIndicator.setText2(file.getPresentableUrl());
1714         }
1715       }
1716       return true;
1717     }
1718   }
1719
1720   private boolean shouldUpdateIndex(final VirtualFile file, final ID<?, ?> indexId) {
1721     return getInputFilter(indexId).acceptInput(file) &&
1722            (isMock(file) || IndexingStamp.isFileIndexed(file, indexId, IndexInfrastructure.getIndexCreationStamp(indexId)));
1723   }
1724
1725   private boolean shouldIndexFile(final VirtualFile file, final ID<?, ?> indexId) {
1726     return getInputFilter(indexId).acceptInput(file) &&
1727            (isMock(file) || !IndexingStamp.isFileIndexed(file, indexId, IndexInfrastructure.getIndexCreationStamp(indexId)));
1728   }
1729
1730   private boolean isUnderConfigOrSystem(VirtualFile file) {
1731     final String filePath = file.getPath();
1732     if (myConfigPath != null && FileUtil.startsWith(filePath, myConfigPath)) {
1733       return true;
1734     }
1735     if (mySystemPath != null && FileUtil.startsWith(filePath, mySystemPath)) {
1736       return true;
1737     }
1738     return false;
1739   }
1740
1741   private static boolean isMock(final VirtualFile file) {
1742     return !(file instanceof NewVirtualFile);
1743   }
1744
1745   private boolean isTooLarge(VirtualFile file) {
1746     if (SingleRootFileViewProvider.isTooLarge(file)) {
1747       final FileType type = FileTypeManager.getInstance().getFileTypeByFile(file);
1748       return !myNoLimitCheckTypes.contains(type);
1749     }
1750     return false;
1751   }
1752
1753   public CollectingContentIterator createContentIterator() {
1754     return new UnindexedFilesFinder();
1755   }
1756
1757   public void registerIndexableSet(IndexableFileSet set) {
1758     myIndexableSets.add(set);
1759   }
1760
1761   public void removeIndexableSet(IndexableFileSet set) {
1762     myChangedFilesUpdater.forceUpdate(null);
1763     myIndexableSets.remove(set);
1764   }
1765
1766   @Nullable
1767   private static PsiFile findLatestKnownPsiForUncomittedDocument(Document doc, Project project) {
1768     return PsiDocumentManager.getInstance(project).getCachedPsiFile(doc);
1769   }
1770
1771   private static class IndexableFilesFilter implements InputFilter {
1772     private final InputFilter myDelegate;
1773
1774     private IndexableFilesFilter(InputFilter delegate) {
1775       myDelegate = delegate;
1776     }
1777
1778     public boolean acceptInput(final VirtualFile file) {
1779       return file instanceof VirtualFileWithId && myDelegate.acceptInput(file);
1780     }
1781   }
1782
1783   private static void cleanupProcessedFlag() {
1784     final VirtualFile[] roots = ManagingFS.getInstance().getRoots();
1785     for (VirtualFile root : roots) {
1786       cleanProcessedFlag(root);
1787     }
1788   }
1789
1790   private static void cleanProcessedFlag(final VirtualFile file) {
1791     if (!(file instanceof NewVirtualFile)) return;
1792
1793     final NewVirtualFile nvf = (NewVirtualFile)file;
1794     if (file.isDirectory()) {
1795       for (VirtualFile child : nvf.getCachedChildren()) {
1796         cleanProcessedFlag(child);
1797       }
1798     }
1799     else {
1800 /*      nvf.clearCachedFileType(); */
1801       nvf.setFlag(ALREADY_PROCESSED, false);
1802     }
1803   }
1804
1805   private static class StorageGuard {
1806     private int myHolds = 0;
1807
1808     public interface Holder {
1809       void leave();
1810     }
1811
1812     private final Holder myTrueHolder = new Holder() {
1813       public void leave() {
1814         StorageGuard.this.leave(true);
1815       }
1816     };
1817     private final Holder myFalseHolder = new Holder() {
1818       public void leave() {
1819         StorageGuard.this.leave(false);
1820       }
1821     };
1822
1823     public synchronized Holder enter(boolean mode) {
1824       if (mode) {
1825         while (myHolds < 0) {
1826           try {
1827             wait();
1828           }
1829           catch (InterruptedException ignored) {
1830           }
1831         }
1832         myHolds++;
1833         return myTrueHolder;
1834       }
1835       else {
1836         while (myHolds > 0) {
1837           try {
1838             wait();
1839           }
1840           catch (InterruptedException ignored) {
1841           }
1842         }
1843         myHolds--;
1844         return myFalseHolder;
1845       }
1846     }
1847
1848     private synchronized void leave(boolean mode) {
1849       myHolds += (mode? -1 : 1);
1850       if (myHolds == 0) {
1851         notifyAll();
1852       }
1853     }
1854
1855   }
1856 }