platform/indexing-impl/src/com/intellij/psi/impl/search/PsiSearchHelperImpl.java

   1 /*
   2  * Copyright 2000-2015 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.psi.impl.search;
  18
  19 import com.intellij.concurrency.AsyncFuture;
  20 import com.intellij.concurrency.AsyncUtil;
  21 import com.intellij.concurrency.JobLauncher;
  22 import com.intellij.openapi.application.ApplicationManager;
  23 import com.intellij.openapi.application.ex.ApplicationEx;
  24 import com.intellij.openapi.application.ex.ApplicationUtil;
  25 import com.intellij.openapi.diagnostic.Logger;
  26 import com.intellij.openapi.fileEditor.FileDocumentManager;
  27 import com.intellij.openapi.progress.EmptyProgressIndicator;
  28 import com.intellij.openapi.progress.ProcessCanceledException;
  29 import com.intellij.openapi.progress.ProgressIndicator;
  30 import com.intellij.openapi.progress.ProgressIndicatorProvider;
  31 import com.intellij.openapi.progress.util.TooManyUsagesStatus;
  32 import com.intellij.openapi.project.DumbService;
  33 import com.intellij.openapi.project.Project;
  34 import com.intellij.openapi.roots.FileIndexFacade;
  35 import com.intellij.openapi.util.*;
  36 import com.intellij.openapi.util.text.StringUtil;
  37 import com.intellij.openapi.vfs.VirtualFile;
  38 import com.intellij.psi.*;
  39 import com.intellij.psi.impl.PsiManagerEx;
  40 import com.intellij.psi.impl.cache.CacheManager;
  41 import com.intellij.psi.impl.cache.impl.id.IdIndex;
  42 import com.intellij.psi.impl.cache.impl.id.IdIndexEntry;
  43 import com.intellij.psi.search.*;
  44 import com.intellij.psi.util.PsiUtilCore;
  45 import com.intellij.usageView.UsageInfo;
  46 import com.intellij.usageView.UsageInfoFactory;
  47 import com.intellij.util.CommonProcessors;
  48 import com.intellij.util.Function;
  49 import com.intellij.util.Processor;
  50 import com.intellij.util.SmartList;
  51 import com.intellij.util.codeInsight.CommentUtilCore;
  52 import com.intellij.util.containers.ContainerUtil;
  53 import com.intellij.util.containers.MultiMap;
  54 import com.intellij.util.indexing.FileBasedIndex;
  55 import com.intellij.util.text.StringSearcher;
  56 import gnu.trove.THashMap;
  57 import gnu.trove.THashSet;
  58 import gnu.trove.TIntProcedure;
  59 import org.jetbrains.annotations.NotNull;
  60 import org.jetbrains.annotations.Nullable;
  61
  62 import java.io.IOException;
  63 import java.util.*;
  64 import java.util.concurrent.atomic.AtomicBoolean;
  65 import java.util.concurrent.atomic.AtomicInteger;
  66
  67 public class PsiSearchHelperImpl implements PsiSearchHelper {
  68   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.search.PsiSearchHelperImpl");
  69   private final PsiManagerEx myManager;
  70
  71   public enum Options {
  72     PROCESS_INJECTED_PSI, CASE_SENSITIVE_SEARCH, PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE
  73   }
  74
  75   @Override
  76   @NotNull
  77   public SearchScope getUseScope(@NotNull PsiElement element) {
  78     SearchScope scope = element.getUseScope();
  79     for (UseScopeEnlarger enlarger : UseScopeEnlarger.EP_NAME.getExtensions()) {
  80       final SearchScope additionalScope = enlarger.getAdditionalUseScope(element);
  81       if (additionalScope != null) {
  82         scope = scope.union(additionalScope);
  83       }
  84     }
  85     for (UseScopeOptimizer optimizer : UseScopeOptimizer.EP_NAME.getExtensions()) {
  86       final GlobalSearchScope scopeToExclude = optimizer.getScopeToExclude(element);
  87       if (scopeToExclude != null) {
  88         scope = scope.intersectWith(GlobalSearchScope.notScope(scopeToExclude));
  89       }
  90     }
  91     return scope;
  92   }
  93
  94   public PsiSearchHelperImpl(@NotNull PsiManagerEx manager) {
  95     myManager = manager;
  96   }
  97
  98   @Override
  99   @NotNull
 100   public PsiElement[] findCommentsContainingIdentifier(@NotNull String identifier, @NotNull SearchScope searchScope) {
 101     final List<PsiElement> results = Collections.synchronizedList(new ArrayList<PsiElement>());
 102     processCommentsContainingIdentifier(identifier, searchScope, new CommonProcessors.CollectProcessor<PsiElement>(results));
 103     return PsiUtilCore.toPsiElementArray(results);
 104   }
 105
 106   @Override
 107   public boolean processCommentsContainingIdentifier(@NotNull String identifier,
 108                                                      @NotNull SearchScope searchScope,
 109                                                      @NotNull final Processor<PsiElement> processor) {
 110     TextOccurenceProcessor occurrenceProcessor = new TextOccurenceProcessor() {
 111       @Override
 112       public boolean execute(@NotNull PsiElement element, int offsetInElement) {
 113         if (CommentUtilCore.isCommentTextElement(element)) {
 114           if (element.findReferenceAt(offsetInElement) == null) {
 115             return processor.process(element);
 116           }
 117         }
 118         return true;
 119       }
 120     };
 121     return processElementsWithWord(occurrenceProcessor, searchScope, identifier, UsageSearchContext.IN_COMMENTS, true);
 122   }
 123
 124   @Override
 125   public boolean processElementsWithWord(@NotNull TextOccurenceProcessor processor,
 126                                          @NotNull SearchScope searchScope,
 127                                          @NotNull String text,
 128                                          short searchContext,
 129                                          boolean caseSensitive) {
 130     return processElementsWithWord(processor, searchScope, text, searchContext, caseSensitive, shouldProcessInjectedPsi(searchScope));
 131   }
 132
 133   @Override
 134   public boolean processElementsWithWord(@NotNull TextOccurenceProcessor processor,
 135                                          @NotNull SearchScope searchScope,
 136                                          @NotNull String text,
 137                                          short searchContext,
 138                                          boolean caseSensitive,
 139                                          boolean processInjectedPsi) {
 140     final EnumSet<Options> options = EnumSet.of(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE);
 141     if (caseSensitive) options.add(Options.CASE_SENSITIVE_SEARCH);
 142     if (processInjectedPsi) options.add(Options.PROCESS_INJECTED_PSI);
 143
 144     return processElementsWithWord(processor, searchScope, text, searchContext, options, null);
 145   }
 146
 147   @NotNull
 148   @Override
 149   public AsyncFuture<Boolean> processElementsWithWordAsync(@NotNull final TextOccurenceProcessor processor,
 150                                                            @NotNull SearchScope searchScope,
 151                                                            @NotNull final String text,
 152                                                            final short searchContext,
 153                                                            final boolean caseSensitively) {
 154     boolean result = processElementsWithWord(processor, searchScope, text, searchContext, caseSensitively,
 155                                              shouldProcessInjectedPsi(searchScope));
 156     return AsyncUtil.wrapBoolean(result);
 157   }
 158
 159   public boolean processElementsWithWord(@NotNull final TextOccurenceProcessor processor,
 160                                          @NotNull SearchScope searchScope,
 161                                          @NotNull final String text,
 162                                          final short searchContext,
 163                                          @NotNull EnumSet<Options> options,
 164                                          @Nullable String containerName) {
 165     if (text.isEmpty()) {
 166       throw new IllegalArgumentException("Cannot search for elements with empty text");
 167     }
 168     ProgressIndicator progress = getOrCreateIndicator();
 169     if (searchScope instanceof GlobalSearchScope) {
 170       StringSearcher searcher = new StringSearcher(text, options.contains(Options.CASE_SENSITIVE_SEARCH), true,
 171                                                    searchContext == UsageSearchContext.IN_STRINGS,
 172                                                    options.contains(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE));
 173
 174       return processElementsWithTextInGlobalScope(processor,
 175                                                   (GlobalSearchScope)searchScope,
 176                                                   searcher,
 177                                                   searchContext, options.contains(Options.CASE_SENSITIVE_SEARCH), containerName, progress,
 178                                                   options.contains(Options.PROCESS_INJECTED_PSI));
 179     }
 180     LocalSearchScope scope = (LocalSearchScope)searchScope;
 181     PsiElement[] scopeElements = scope.getScope();
 182     final StringSearcher searcher = new StringSearcher(text, options.contains(Options.CASE_SENSITIVE_SEARCH), true,
 183                                                        searchContext == UsageSearchContext.IN_STRINGS,
 184                                                        options.contains(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE));
 185     Processor<PsiElement> localProcessor = localProcessor(processor, progress, options.contains(Options.PROCESS_INJECTED_PSI), searcher);
 186     return JobLauncher.getInstance().invokeConcurrentlyUnderProgress(Arrays.asList(scopeElements), progress, true, true, localProcessor);
 187   }
 188
 189   @NotNull
 190   private static ProgressIndicator getOrCreateIndicator() {
 191     ProgressIndicator progress = ProgressIndicatorProvider.getGlobalProgressIndicator();
 192     if (progress == null) progress = new EmptyProgressIndicator();
 193     return progress;
 194   }
 195
 196   public static boolean shouldProcessInjectedPsi(@NotNull SearchScope scope) {
 197     return !(scope instanceof LocalSearchScope) || !((LocalSearchScope)scope).isIgnoreInjectedPsi();
 198   }
 199
 200   @NotNull
 201   private static Processor<PsiElement> localProcessor(@NotNull final TextOccurenceProcessor processor,
 202                                                       @NotNull final ProgressIndicator progress,
 203                                                       final boolean processInjectedPsi,
 204                                                       @NotNull final StringSearcher searcher) {
 205     return new Processor<PsiElement>() {
 206         @Override
 207         public boolean process(final PsiElement scopeElement) {
 208           return ApplicationManager.getApplication().runReadAction(new Computable<Boolean>() {
 209             @Override
 210             public Boolean compute() {
 211               return LowLevelSearchUtil.processElementsContainingWordInElement(processor, scopeElement, searcher, processInjectedPsi, progress);
 212             }
 213           }).booleanValue();
 214         }
 215
 216       @Override
 217       public String toString() {
 218         return processor.toString();
 219       }
 220     };
 221   }
 222
 223   private boolean processElementsWithTextInGlobalScope(@NotNull final TextOccurenceProcessor processor,
 224                                                        @NotNull final GlobalSearchScope scope,
 225                                                        @NotNull final StringSearcher searcher,
 226                                                        final short searchContext,
 227                                                        final boolean caseSensitively,
 228                                                        @Nullable String containerName,
 229                                                        @NotNull ProgressIndicator progress,
 230                                                        final boolean processInjectedPsi) {
 231     if (Thread.holdsLock(PsiLock.LOCK)) {
 232       throw new AssertionError("You must not run search from within updating PSI activity. Please consider invokeLatering it instead.");
 233     }
 234     progress.pushState();
 235     progress.setText(PsiBundle.message("psi.scanning.files.progress"));
 236
 237     String text = searcher.getPattern();
 238     Set<VirtualFile> fileSet = new THashSet<VirtualFile>();
 239     getFilesWithText(scope, searchContext, caseSensitively, text, progress, fileSet);
 240
 241     progress.setText(PsiBundle.message("psi.search.for.word.progress", text));
 242
 243     final Processor<PsiElement> localProcessor = localProcessor(processor, progress, processInjectedPsi, searcher);
 244     if (containerName != null) {
 245       List<VirtualFile> intersectionWithContainerFiles = new ArrayList<VirtualFile>();
 246       // intersectionWithContainerFiles holds files containing words from both `text` and `containerName`
 247       getFilesWithText(scope, searchContext, caseSensitively, text+" "+containerName, progress, intersectionWithContainerFiles);
 248       if (!intersectionWithContainerFiles.isEmpty()) {
 249         int totalSize = fileSet.size();
 250         boolean result = processPsiFileRoots(intersectionWithContainerFiles, totalSize, 0, progress,
 251                                                          localProcessor);
 252
 253         if (result) {
 254           fileSet.removeAll(intersectionWithContainerFiles);
 255           if (!fileSet.isEmpty()) {
 256             result = processPsiFileRoots(new ArrayList<VirtualFile>(fileSet), totalSize, intersectionWithContainerFiles.size(), progress, localProcessor);
 257           }
 258         }
 259         progress.popState();
 260         return result;
 261       }
 262     }
 263
 264     boolean result = fileSet.isEmpty() || processPsiFileRoots(new ArrayList<VirtualFile>(fileSet), fileSet.size(), 0, progress, localProcessor);
 265     progress.popState();
 266     return result;
 267   }
 268
 269   /**
 270    * @param files to scan for references in this pass.
 271    * @param totalSize the number of files to scan in both passes. Can be different from <code>files.size()</code> in case of
 272    *                  two-pass scan, where we first scan files containing container name and then all the rest files.
 273    * @param alreadyProcessedFiles the number of files scanned in previous pass.
 274    * @return true if completed
 275    */
 276   private boolean processPsiFileRoots(@NotNull List<VirtualFile> files,
 277                                       final int totalSize,
 278                                       int alreadyProcessedFiles,
 279                                       @NotNull final ProgressIndicator progress,
 280                                       @NotNull final Processor<? super PsiFile> localProcessor) {
 281     myManager.startBatchFilesProcessingMode();
 282     try {
 283       final AtomicInteger counter = new AtomicInteger(alreadyProcessedFiles);
 284       final AtomicBoolean canceled = new AtomicBoolean(false);
 285
 286       boolean completed = true;
 287       while (true) {
 288         List<VirtualFile> failedList = new SmartList<VirtualFile>();
 289         final List<VirtualFile> failedFiles = Collections.synchronizedList(failedList);
 290         final Processor<VirtualFile> processor = new Processor<VirtualFile>() {
 291           @Override
 292           public boolean process(final VirtualFile vfile) {
 293             try {
 294               TooManyUsagesStatus.getFrom(progress).pauseProcessingIfTooManyUsages();
 295               processVirtualFile(vfile, progress, localProcessor, canceled, counter, totalSize);
 296             }
 297             catch (ApplicationUtil.CannotRunReadActionException action) {
 298               failedFiles.add(vfile);
 299             }
 300             return !canceled.get();
 301           }
 302         };
 303         if (ApplicationManager.getApplication().isWriteAccessAllowed() || ((ApplicationEx)ApplicationManager.getApplication()).isWriteActionPending()) {
 304           // no point in processing in separate threads - they are doomed to fail to obtain read action anyway
 305           completed &= ContainerUtil.process(files, processor);
 306         }
 307         else {
 308           completed &= JobLauncher.getInstance().invokeConcurrentlyUnderProgress(files, progress, false, false, processor);
 309         }
 310
 311         if (failedFiles.isEmpty()) {
 312           break;
 313         }
 314         // we failed to run read action in job launcher thread
 315         // run read action in our thread instead to wait for a write action to complete and resume parallel processing
 316         DumbService.getInstance(myManager.getProject()).runReadActionInSmartMode(EmptyRunnable.getInstance());
 317         files = failedList;
 318       }
 319       return completed;
 320     }
 321     finally {
 322       myManager.finishBatchFilesProcessingMode();
 323     }
 324   }
 325
 326   private void processVirtualFile(@NotNull final VirtualFile vfile,
 327                                   @NotNull final ProgressIndicator progress,
 328                                   @NotNull final Processor<? super PsiFile> localProcessor,
 329                                   @NotNull final AtomicBoolean canceled,
 330                                   @NotNull AtomicInteger counter,
 331                                   int totalSize) throws ApplicationUtil.CannotRunReadActionException {
 332     final PsiFile file = ApplicationUtil.tryRunReadAction(new Computable<PsiFile>() {
 333       @Override
 334       public PsiFile compute() {
 335         return vfile.isValid() ? myManager.findFile(vfile) : null;
 336       }
 337     });
 338     if (file != null && !(file instanceof PsiBinaryFile)) {
 339       // load contents outside read action
 340       if (FileDocumentManager.getInstance().getCachedDocument(vfile) == null) {
 341         // cache bytes in vfs
 342         try {
 343           vfile.contentsToByteArray();
 344         }
 345         catch (IOException ignored) {
 346         }
 347       }
 348       ApplicationUtil.tryRunReadAction(new Computable<Void>() {
 349         @Override
 350         public Void compute() {
 351           final Project project = myManager.getProject();
 352           if (project.isDisposed()) throw new ProcessCanceledException();
 353           if (DumbService.isDumb(project)) throw new ApplicationUtil.CannotRunReadActionException();
 354
 355           List<PsiFile> psiRoots = file.getViewProvider().getAllFiles();
 356           Set<PsiFile> processed = new THashSet<PsiFile>(psiRoots.size() * 2, (float)0.5);
 357           for (final PsiFile psiRoot : psiRoots) {
 358             progress.checkCanceled();
 359             assert psiRoot != null : "One of the roots of file " + file + " is null. All roots: " + psiRoots + "; ViewProvider: " +
 360                                      file.getViewProvider() + "; Virtual file: " + file.getViewProvider().getVirtualFile();
 361             if (!processed.add(psiRoot)) continue;
 362             if (!psiRoot.isValid()) {
 363               continue;
 364             }
 365
 366             if (!localProcessor.process(psiRoot)) {
 367               canceled.set(true);
 368               break;
 369             }
 370           }
 371           return null;
 372         }
 373       });
 374     }
 375     if (progress.isRunning()) {
 376       double fraction = (double)counter.incrementAndGet() / totalSize;
 377       progress.setFraction(fraction);
 378     }
 379   }
 380
 381   private void getFilesWithText(@NotNull GlobalSearchScope scope,
 382                                 final short searchContext,
 383                                 final boolean caseSensitively,
 384                                 @NotNull String text,
 385                                 @NotNull final ProgressIndicator progress,
 386                                 @NotNull Collection<VirtualFile> result) {
 387     myManager.startBatchFilesProcessingMode();
 388     try {
 389       Processor<VirtualFile> processor = new CommonProcessors.CollectProcessor<VirtualFile>(result){
 390         @Override
 391         public boolean process(VirtualFile file) {
 392           progress.checkCanceled();
 393           return super.process(file);
 394         }
 395       };
 396       boolean success = processFilesWithText(scope, searchContext, caseSensitively, text, processor);
 397       // success == false means exception in index
 398     }
 399     finally {
 400       myManager.finishBatchFilesProcessingMode();
 401     }
 402   }
 403
 404   public boolean processFilesWithText(@NotNull final GlobalSearchScope scope,
 405                                       final short searchContext,
 406                                       final boolean caseSensitively,
 407                                       @NotNull String text,
 408                                       @NotNull final Processor<VirtualFile> processor) {
 409     List<IdIndexEntry> entries = getWordEntries(text, caseSensitively);
 410     if (entries.isEmpty()) return true;
 411
 412     Condition<Integer> contextMatches = new Condition<Integer>() {
 413       @Override
 414       public boolean value(Integer integer) {
 415         return (integer.intValue() & searchContext) != 0;
 416       }
 417     };
 418     return processFilesContainingAllKeys(myManager.getProject(), scope, contextMatches, entries, processor);
 419   }
 420
 421   @Override
 422   @NotNull
 423   public PsiFile[] findFilesWithPlainTextWords(@NotNull String word) {
 424     return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(word, UsageSearchContext.IN_PLAIN_TEXT,
 425                                                                                      GlobalSearchScope.projectScope(myManager.getProject()),
 426                                                                                      true);
 427   }
 428
 429
 430   @Override
 431   public boolean processUsagesInNonJavaFiles(@NotNull String qName,
 432                                              @NotNull PsiNonJavaFileReferenceProcessor processor,
 433                                              @NotNull GlobalSearchScope searchScope) {
 434     return processUsagesInNonJavaFiles(null, qName, processor, searchScope);
 435   }
 436
 437   @Override
 438   public boolean processUsagesInNonJavaFiles(@Nullable final PsiElement originalElement,
 439                                              @NotNull String qName,
 440                                              @NotNull final PsiNonJavaFileReferenceProcessor processor,
 441                                              @NotNull final GlobalSearchScope initialScope) {
 442     if (qName.isEmpty()) {
 443       throw new IllegalArgumentException("Cannot search for elements with empty text. Element: "+originalElement+ "; "+(originalElement == null ? null : originalElement.getClass()));
 444     }
 445     final ProgressIndicator progress = getOrCreateIndicator();
 446
 447     int dotIndex = qName.lastIndexOf('.');
 448     int dollarIndex = qName.lastIndexOf('$');
 449     int maxIndex = Math.max(dotIndex, dollarIndex);
 450     final String wordToSearch = maxIndex >= 0 ? qName.substring(maxIndex + 1) : qName;
 451     final GlobalSearchScope theSearchScope = ApplicationManager.getApplication().runReadAction(new Computable<GlobalSearchScope>() {
 452       @Override
 453       public GlobalSearchScope compute() {
 454         if (originalElement != null && myManager.isInProject(originalElement) && initialScope.isSearchInLibraries()) {
 455           return initialScope.intersectWith(GlobalSearchScope.projectScope(myManager.getProject()));
 456         }
 457         return initialScope;
 458       }
 459     });
 460     PsiFile[] files = ApplicationManager.getApplication().runReadAction(new Computable<PsiFile[]>() {
 461       @Override
 462       public PsiFile[] compute() {
 463         return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(wordToSearch, UsageSearchContext.IN_PLAIN_TEXT, theSearchScope, true);
 464       }
 465     });
 466
 467     final StringSearcher searcher = new StringSearcher(qName, true, true, false);
 468     final int patternLength = searcher.getPattern().length();
 469
 470     progress.pushState();
 471     progress.setText(PsiBundle.message("psi.search.in.non.java.files.progress"));
 472
 473     final SearchScope useScope = originalElement == null ? null : ApplicationManager.getApplication().runReadAction(new Computable<SearchScope>() {
 474       @Override
 475       public SearchScope compute() {
 476         return getUseScope(originalElement);
 477       }
 478     });
 479
 480     final Ref<Boolean> cancelled = new Ref<Boolean>(Boolean.FALSE);
 481     for (int i = 0; i < files.length; i++) {
 482       progress.checkCanceled();
 483       final PsiFile psiFile = files[i];
 484       if (psiFile instanceof PsiBinaryFile) continue;
 485
 486       final CharSequence text = ApplicationManager.getApplication().runReadAction(new Computable<CharSequence>() {
 487         @Override
 488         public CharSequence compute() {
 489           return psiFile.getViewProvider().getContents();
 490         }
 491       });
 492
 493       LowLevelSearchUtil.processTextOccurrences(text, 0, text.length(), searcher, progress, new TIntProcedure() {
 494         @Override
 495         public boolean execute(final int index) {
 496           boolean isReferenceOK = ApplicationManager.getApplication().runReadAction(new Computable<Boolean>() {
 497             @Override
 498             public Boolean compute() {
 499               PsiReference referenceAt = psiFile.findReferenceAt(index);
 500               return referenceAt == null || useScope == null ||
 501                      !PsiSearchScopeUtil.isInScope(useScope.intersectWith(initialScope), psiFile);
 502             }
 503           });
 504           if (isReferenceOK && !processor.process(psiFile, index, index + patternLength)) {
 505             cancelled.set(Boolean.TRUE);
 506             return false;
 507           }
 508
 509           return true;
 510         }
 511       });
 512       if (cancelled.get()) break;
 513       progress.setFraction((double)(i + 1) / files.length);
 514     }
 515
 516     progress.popState();
 517     return !cancelled.get();
 518   }
 519
 520   @Override
 521   public boolean processAllFilesWithWord(@NotNull String word,
 522                                          @NotNull GlobalSearchScope scope,
 523                                          @NotNull Processor<PsiFile> processor,
 524                                          final boolean caseSensitively) {
 525     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_CODE, scope, caseSensitively);
 526   }
 527
 528   @Override
 529   public boolean processAllFilesWithWordInText(@NotNull final String word,
 530                                                @NotNull final GlobalSearchScope scope,
 531                                                @NotNull final Processor<PsiFile> processor,
 532                                                final boolean caseSensitively) {
 533     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_PLAIN_TEXT, scope, caseSensitively);
 534   }
 535
 536   @Override
 537   public boolean processAllFilesWithWordInComments(@NotNull String word,
 538                                                    @NotNull GlobalSearchScope scope,
 539                                                    @NotNull Processor<PsiFile> processor) {
 540     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_COMMENTS, scope, true);
 541   }
 542
 543   @Override
 544   public boolean processAllFilesWithWordInLiterals(@NotNull String word,
 545                                                    @NotNull GlobalSearchScope scope,
 546                                                    @NotNull Processor<PsiFile> processor) {
 547     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_STRINGS, scope, true);
 548   }
 549
 550   private static class RequestWithProcessor {
 551     @NotNull private final PsiSearchRequest request;
 552     @NotNull private Processor<PsiReference> refProcessor;
 553
 554     private RequestWithProcessor(@NotNull PsiSearchRequest first, @NotNull Processor<PsiReference> second) {
 555       request = first;
 556       refProcessor = second;
 557     }
 558
 559     private boolean uniteWith(@NotNull final RequestWithProcessor another) {
 560       if (request.equals(another.request)) {
 561         final Processor<PsiReference> myProcessor = refProcessor;
 562         if (myProcessor != another.refProcessor) {
 563           refProcessor = new Processor<PsiReference>() {
 564             @Override
 565             public boolean process(PsiReference psiReference) {
 566               return myProcessor.process(psiReference) && another.refProcessor.process(psiReference);
 567             }
 568           };
 569         }
 570         return true;
 571       }
 572       return false;
 573     }
 574
 575     @Override
 576     public String toString() {
 577       return request.toString();
 578     }
 579   }
 580
 581   @Override
 582   public boolean processRequests(@NotNull SearchRequestCollector collector, @NotNull Processor<PsiReference> processor) {
 583     final Map<SearchRequestCollector, Processor<PsiReference>> collectors = ContainerUtil.newHashMap();
 584     collectors.put(collector, processor);
 585
 586     ProgressIndicator progress = getOrCreateIndicator();
 587     appendCollectorsFromQueryRequests(collectors);
 588     boolean result;
 589     do {
 590       MultiMap<Set<IdIndexEntry>, RequestWithProcessor> globals = new MultiMap<Set<IdIndexEntry>, RequestWithProcessor>();
 591       final List<Computable<Boolean>> customs = ContainerUtil.newArrayList();
 592       final Set<RequestWithProcessor> locals = ContainerUtil.newLinkedHashSet();
 593       Map<RequestWithProcessor, Processor<PsiElement>> localProcessors = new THashMap<RequestWithProcessor, Processor<PsiElement>>();
 594       distributePrimitives(collectors, locals, globals, customs, localProcessors, progress);
 595       result = processGlobalRequestsOptimized(globals, progress, localProcessors);
 596       if (result) {
 597         for (RequestWithProcessor local : locals) {
 598           result = processSingleRequest(local.request, local.refProcessor);
 599           if (!result) break;
 600         }
 601         if (result) {
 602           for (Computable<Boolean> custom : customs) {
 603             result = custom.compute();
 604             if (!result) break;
 605           }
 606         }
 607         if (!result) break;
 608       }
 609     }
 610     while(appendCollectorsFromQueryRequests(collectors));
 611     return result;
 612   }
 613
 614   @NotNull
 615   @Override
 616   public AsyncFuture<Boolean> processRequestsAsync(@NotNull SearchRequestCollector collector, @NotNull Processor<PsiReference> processor) {
 617     return AsyncUtil.wrapBoolean(processRequests(collector, processor));
 618   }
 619
 620   private static boolean appendCollectorsFromQueryRequests(@NotNull Map<SearchRequestCollector, Processor<PsiReference>> collectors) {
 621     boolean changed = false;
 622     Deque<SearchRequestCollector> queue = new LinkedList<SearchRequestCollector>(collectors.keySet());
 623     while (!queue.isEmpty()) {
 624       final SearchRequestCollector each = queue.removeFirst();
 625       for (QuerySearchRequest request : each.takeQueryRequests()) {
 626         request.runQuery();
 627         assert !collectors.containsKey(request.collector) || collectors.get(request.collector) == request.processor;
 628         collectors.put(request.collector, request.processor);
 629         queue.addLast(request.collector);
 630         changed = true;
 631       }
 632     }
 633     return changed;
 634   }
 635
 636   private boolean processGlobalRequestsOptimized(@NotNull MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 637                                                  @NotNull ProgressIndicator progress,
 638                                                  @NotNull final Map<RequestWithProcessor, Processor<PsiElement>> localProcessors) {
 639     if (singles.isEmpty()) {
 640       return true;
 641     }
 642
 643     if (singles.size() == 1) {
 644       final Collection<? extends RequestWithProcessor> requests = singles.values();
 645       if (requests.size() == 1) {
 646         final RequestWithProcessor theOnly = requests.iterator().next();
 647         return processSingleRequest(theOnly.request, theOnly.refProcessor);
 648       }
 649     }
 650
 651     progress.pushState();
 652     progress.setText(PsiBundle.message("psi.scanning.files.progress"));
 653     boolean result;
 654
 655     try {
 656       // intersectionCandidateFiles holds files containing words from all requests in `singles` and words in corresponding container names
 657       final MultiMap<VirtualFile, RequestWithProcessor> intersectionCandidateFiles = createMultiMap();
 658       // restCandidateFiles holds files containing words from all requests in `singles` but EXCLUDING words in corresponding container names
 659       final MultiMap<VirtualFile, RequestWithProcessor> restCandidateFiles = createMultiMap();
 660       collectFiles(singles, progress, intersectionCandidateFiles, restCandidateFiles);
 661
 662       if (intersectionCandidateFiles.isEmpty() && restCandidateFiles.isEmpty()) {
 663         return true;
 664       }
 665
 666       final Set<String> allWords = new TreeSet<String>();
 667       for (RequestWithProcessor singleRequest : localProcessors.keySet()) {
 668         allWords.add(singleRequest.request.word);
 669       }
 670       progress.setText(PsiBundle.message("psi.search.for.word.progress", getPresentableWordsDescription(allWords)));
 671
 672       if (intersectionCandidateFiles.isEmpty()) {
 673         result = processCandidates(localProcessors, restCandidateFiles, progress, restCandidateFiles.size(), 0);
 674       }
 675       else {
 676         int totalSize = restCandidateFiles.size() + intersectionCandidateFiles.size();
 677         result = processCandidates(localProcessors, intersectionCandidateFiles, progress, totalSize, 0);
 678         if (result) {
 679           result = processCandidates(localProcessors, restCandidateFiles, progress, totalSize, intersectionCandidateFiles.size());
 680         }
 681       }
 682     }
 683     finally {
 684       progress.popState();
 685     }
 686
 687     return result;
 688   }
 689
 690   private boolean processCandidates(@NotNull final Map<RequestWithProcessor, Processor<PsiElement>> localProcessors,
 691                                     @NotNull final MultiMap<VirtualFile, RequestWithProcessor> candidateFiles,
 692                                     @NotNull ProgressIndicator progress,
 693                                     int totalSize,
 694                                     int alreadyProcessedFiles) {
 695     List<VirtualFile> files = new ArrayList<VirtualFile>(candidateFiles.keySet());
 696
 697     return processPsiFileRoots(files, totalSize, alreadyProcessedFiles, progress, new Processor<PsiFile>() {
 698       @Override
 699       public boolean process(final PsiFile psiRoot) {
 700         final VirtualFile vfile = psiRoot.getVirtualFile();
 701         for (final RequestWithProcessor singleRequest : candidateFiles.get(vfile)) {
 702           Processor<PsiElement> localProcessor = localProcessors.get(singleRequest);
 703           if (!localProcessor.process(psiRoot)) {
 704             return false;
 705           }
 706         }
 707         return true;
 708       }
 709     });
 710   }
 711
 712   @NotNull
 713   private static String getPresentableWordsDescription(@NotNull Set<String> allWords) {
 714     final StringBuilder result = new StringBuilder();
 715     for (String string : allWords) {
 716         if (string != null && !string.isEmpty()) {
 717         if (result.length() > 50) {
 718           result.append("...");
 719           break;
 720         }
 721         if (result.length() != 0) result.append(", ");
 722         result.append(string);
 723       }
 724     }
 725     return result.toString();
 726   }
 727
 728   @NotNull
 729   private static TextOccurenceProcessor adaptProcessor(@NotNull PsiSearchRequest singleRequest,
 730                                                        @NotNull final Processor<PsiReference> consumer) {
 731     final SearchScope searchScope = singleRequest.searchScope;
 732     final boolean ignoreInjectedPsi = searchScope instanceof LocalSearchScope && ((LocalSearchScope)searchScope).isIgnoreInjectedPsi();
 733     final RequestResultProcessor wrapped = singleRequest.processor;
 734     return new TextOccurenceProcessor() {
 735       @Override
 736       public boolean execute(@NotNull PsiElement element, int offsetInElement) {
 737         if (ignoreInjectedPsi && element instanceof PsiLanguageInjectionHost) return true;
 738
 739         return wrapped.processTextOccurrence(element, offsetInElement, consumer);
 740       }
 741
 742       @Override
 743       public String toString() {
 744         return consumer.toString();
 745       }
 746     };
 747   }
 748
 749   private void collectFiles(@NotNull MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 750                             @NotNull ProgressIndicator progress,
 751                             @NotNull final MultiMap<VirtualFile, RequestWithProcessor> intersectionResult,
 752                             @NotNull final MultiMap<VirtualFile, RequestWithProcessor> restResult) {
 753     for (final Set<IdIndexEntry> keys : singles.keySet()) {
 754       if (keys.isEmpty()) {
 755         continue;
 756       }
 757
 758       final Collection<RequestWithProcessor> data = singles.get(keys);
 759       final GlobalSearchScope commonScope = uniteScopes(data);
 760       final Set<VirtualFile> intersectionWithContainerNameFiles = intersectionWithContainerNameFiles(commonScope, data, keys);
 761
 762       List<VirtualFile> files = new ArrayList<VirtualFile>();
 763       Processor<VirtualFile> processor = new CommonProcessors.CollectProcessor<VirtualFile>(files);
 764       processFilesContainingAllKeys(myManager.getProject(), commonScope, null, keys, processor);
 765       for (final VirtualFile file : files) {
 766         progress.checkCanceled();
 767         for (final IdIndexEntry entry : keys) {
 768           DumbService.getInstance(myManager.getProject()).runReadActionInSmartMode(new Runnable() {
 769             @Override
 770             public void run() {
 771               FileBasedIndex.getInstance().processValues(IdIndex.NAME, entry, file, new FileBasedIndex.ValueProcessor<Integer>() {
 772                 @Override
 773                 public boolean process(VirtualFile file, Integer value) {
 774                   int mask = value.intValue();
 775                   for (RequestWithProcessor single : data) {
 776                     final PsiSearchRequest request = single.request;
 777                     if ((mask & request.searchContext) != 0 && ((GlobalSearchScope)request.searchScope).contains(file)) {
 778                       MultiMap<VirtualFile, RequestWithProcessor> result =
 779                         intersectionWithContainerNameFiles == null || !intersectionWithContainerNameFiles.contains(file) ? restResult : intersectionResult;
 780                       result.putValue(file, single);
 781                     }
 782                   }
 783                   return true;
 784                 }
 785               }, commonScope);
 786             }
 787           });
 788         }
 789       }
 790     }
 791   }
 792
 793   @Nullable("null means we did not find common container files")
 794   private Set<VirtualFile> intersectionWithContainerNameFiles(@NotNull GlobalSearchScope commonScope,
 795                                                               @NotNull Collection<RequestWithProcessor> data,
 796                                                               @NotNull Set<IdIndexEntry> keys) {
 797     String commonName = null;
 798     short searchContext = 0;
 799     boolean caseSensitive = true;
 800     for (RequestWithProcessor r : data) {
 801       String name = r.request.containerName;
 802       if (name != null) {
 803         if (commonName == null) {
 804           commonName = r.request.containerName;
 805           searchContext = r.request.searchContext;
 806           caseSensitive = r.request.caseSensitive;
 807         }
 808         else if (commonName.equals(name)) {
 809           searchContext |= r.request.searchContext;
 810           caseSensitive &= r.request.caseSensitive;
 811         }
 812         else {
 813           return null;
 814         }
 815       }
 816     }
 817     if (commonName == null) return null;
 818     Set<VirtualFile> containerFiles = new THashSet<VirtualFile>();
 819
 820     List<IdIndexEntry> entries = getWordEntries(commonName, caseSensitive);
 821     if (entries.isEmpty()) return null;
 822     entries.addAll(keys); // should find words from both text and container names
 823
 824     final short finalSearchContext = searchContext;
 825     Condition<Integer> contextMatches = new Condition<Integer>() {
 826       @Override
 827       public boolean value(Integer context) {
 828         return (context.intValue() & finalSearchContext) != 0;
 829       }
 830     };
 831     processFilesContainingAllKeys(myManager.getProject(), commonScope, contextMatches, entries, new CommonProcessors.CollectProcessor<VirtualFile>(containerFiles));
 832
 833     return containerFiles;
 834   }
 835
 836   @NotNull
 837   private static MultiMap<VirtualFile, RequestWithProcessor> createMultiMap() {
 838     // usually there is just one request
 839     return MultiMap.createSmart();
 840   }
 841
 842   @NotNull
 843   private static GlobalSearchScope uniteScopes(@NotNull Collection<RequestWithProcessor> requests) {
 844     Set<GlobalSearchScope> scopes = ContainerUtil.map2LinkedSet(requests, new Function<RequestWithProcessor, GlobalSearchScope>() {
 845       @Override
 846       public GlobalSearchScope fun(RequestWithProcessor r) {
 847         return (GlobalSearchScope)r.request.searchScope;
 848       }
 849     });
 850     return GlobalSearchScope.union(scopes.toArray(new GlobalSearchScope[scopes.size()]));
 851   }
 852
 853   private static void distributePrimitives(@NotNull Map<SearchRequestCollector, Processor<PsiReference>> collectors,
 854                                            @NotNull Set<RequestWithProcessor> locals,
 855                                            @NotNull MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 856                                            @NotNull List<Computable<Boolean>> customs,
 857                                            @NotNull Map<RequestWithProcessor, Processor<PsiElement>> localProcessors,
 858                                            @NotNull ProgressIndicator progress) {
 859     for (final Map.Entry<SearchRequestCollector, Processor<PsiReference>> entry : collectors.entrySet()) {
 860       final Processor<PsiReference> processor = entry.getValue();
 861       SearchRequestCollector collector = entry.getKey();
 862       for (final PsiSearchRequest primitive : collector.takeSearchRequests()) {
 863         final SearchScope scope = primitive.searchScope;
 864         if (scope instanceof LocalSearchScope) {
 865           registerRequest(locals, primitive, processor);
 866         }
 867         else {
 868           Set<IdIndexEntry> key = new HashSet<IdIndexEntry>(getWordEntries(primitive.word, primitive.caseSensitive));
 869           registerRequest(singles.getModifiable(key), primitive, processor);
 870         }
 871       }
 872       for (final Processor<Processor<PsiReference>> customAction : collector.takeCustomSearchActions()) {
 873         customs.add(new Computable<Boolean>() {
 874           @Override
 875           public Boolean compute() {
 876             return customAction.process(processor);
 877           }
 878         });
 879       }
 880     }
 881
 882     for (Map.Entry<Set<IdIndexEntry>, Collection<RequestWithProcessor>> entry : singles.entrySet()) {
 883       for (RequestWithProcessor singleRequest : entry.getValue()) {
 884         PsiSearchRequest primitive = singleRequest.request;
 885         StringSearcher searcher = new StringSearcher(primitive.word, primitive.caseSensitive, true, false);
 886         final TextOccurenceProcessor adapted = adaptProcessor(primitive, singleRequest.refProcessor);
 887
 888         Processor<PsiElement> localProcessor = localProcessor(adapted, progress, true, searcher);
 889
 890         assert !localProcessors.containsKey(singleRequest) || localProcessors.get(singleRequest) == localProcessor;
 891         localProcessors.put(singleRequest, localProcessor);
 892       }
 893     }
 894   }
 895
 896   private static void registerRequest(@NotNull Collection<RequestWithProcessor> collection,
 897                                       @NotNull PsiSearchRequest primitive,
 898                                       @NotNull Processor<PsiReference> processor) {
 899     RequestWithProcessor singleRequest = new RequestWithProcessor(primitive, processor);
 900
 901     for (RequestWithProcessor existing : collection) {
 902       if (existing.uniteWith(singleRequest)) {
 903         return;
 904       }
 905     }
 906     collection.add(singleRequest);
 907   }
 908
 909   private boolean processSingleRequest(@NotNull PsiSearchRequest single, @NotNull Processor<PsiReference> consumer) {
 910     final EnumSet<Options> options = EnumSet.of(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE);
 911     if (single.caseSensitive) options.add(Options.CASE_SENSITIVE_SEARCH);
 912     if (shouldProcessInjectedPsi(single.searchScope)) options.add(Options.PROCESS_INJECTED_PSI);
 913
 914     return processElementsWithWord(adaptProcessor(single, consumer), single.searchScope, single.word, single.searchContext, options,
 915                                    single.containerName);
 916   }
 917
 918   @NotNull
 919   @Override
 920   public SearchCostResult isCheapEnoughToSearch(@NotNull String name,
 921                                                 @NotNull final GlobalSearchScope scope,
 922                                                 @Nullable final PsiFile fileToIgnoreOccurrencesIn,
 923                                                 @Nullable final ProgressIndicator progress) {
 924     final AtomicInteger count = new AtomicInteger();
 925     final ProgressIndicator indicator = progress == null ? new EmptyProgressIndicator() : progress;
 926     final Processor<VirtualFile> processor = new Processor<VirtualFile>() {
 927       private final VirtualFile virtualFileToIgnoreOccurrencesIn =
 928         fileToIgnoreOccurrencesIn == null ? null : fileToIgnoreOccurrencesIn.getVirtualFile();
 929
 930       @Override
 931       public boolean process(VirtualFile file) {
 932         indicator.checkCanceled();
 933         if (Comparing.equal(file, virtualFileToIgnoreOccurrencesIn)) return true;
 934         final int value = count.incrementAndGet();
 935         return value < 10;
 936       }
 937     };
 938     List<IdIndexEntry> keys = getWordEntries(name, true);
 939     boolean cheap = keys.isEmpty() || processFilesContainingAllKeys(myManager.getProject(), scope, null, keys, processor);
 940
 941     if (!cheap) {
 942       return SearchCostResult.TOO_MANY_OCCURRENCES;
 943     }
 944
 945     return count.get() == 0 ? SearchCostResult.ZERO_OCCURRENCES : SearchCostResult.FEW_OCCURRENCES;
 946   }
 947
 948   private static boolean processFilesContainingAllKeys(@NotNull Project project,
 949                                                        @NotNull final GlobalSearchScope scope,
 950                                                        @Nullable final Condition<Integer> checker,
 951                                                        @NotNull final Collection<IdIndexEntry> keys,
 952                                                        @NotNull final Processor<VirtualFile> processor) {
 953     final FileIndexFacade index = FileIndexFacade.getInstance(project);
 954     return DumbService.getInstance(project).runReadActionInSmartMode(new Computable<Boolean>() {
 955       @Override
 956       public Boolean compute() {
 957         return FileBasedIndex.getInstance().processFilesContainingAllKeys(IdIndex.NAME, keys, scope, checker, new Processor<VirtualFile>() {
 958           @Override
 959           public boolean process(VirtualFile file) {
 960             return !index.shouldBeFound(scope, file) || processor.process(file);
 961           }
 962         });
 963       }
 964     });
 965   }
 966
 967   @NotNull
 968   private static List<IdIndexEntry> getWordEntries(@NotNull String name, final boolean caseSensitively) {
 969     List<String> words = StringUtil.getWordsInStringLongestFirst(name);
 970     if (words.isEmpty()) {
 971       String trimmed = name.trim();
 972       if (StringUtil.isNotEmpty(trimmed)) {
 973         words = Collections.singletonList(trimmed);
 974       }
 975     }
 976     if (words.isEmpty()) return Collections.emptyList();
 977     return ContainerUtil.map2List(words, new Function<String, IdIndexEntry>() {
 978       @Override
 979       public IdIndexEntry fun(String word) {
 980         return new IdIndexEntry(word, caseSensitively);
 981       }
 982     });
 983   }
 984
 985   public static boolean processTextOccurrences(@NotNull final PsiElement element,
 986                                                @NotNull String stringToSearch,
 987                                                @NotNull GlobalSearchScope searchScope,
 988                                                @NotNull final Processor<UsageInfo> processor,
 989                                                @NotNull final UsageInfoFactory factory) {
 990     PsiSearchHelper helper = ApplicationManager.getApplication().runReadAction(new Computable<PsiSearchHelper>() {
 991       @Override
 992       public PsiSearchHelper compute() {
 993         return SERVICE.getInstance(element.getProject());
 994       }
 995     });
 996
 997     return helper.processUsagesInNonJavaFiles(element, stringToSearch, new PsiNonJavaFileReferenceProcessor() {
 998       @Override
 999       public boolean process(final PsiFile psiFile, final int startOffset, final int endOffset) {
1000         try {
1001           UsageInfo usageInfo = ApplicationManager.getApplication().runReadAction(new Computable<UsageInfo>() {
1002             @Override
1003             public UsageInfo compute() {
1004               return factory.createUsageInfo(psiFile, startOffset, endOffset);
1005             }
1006           });
1007           return usageInfo == null || processor.process(usageInfo);
1008         }
1009         catch (ProcessCanceledException e) {
1010           throw e;
1011         }
1012         catch (Exception e) {
1013           LOG.error(e);
1014           return true;
1015         }
1016       }
1017     }, searchScope);
1018   }
1019 }