platform/lang-impl/src/com/intellij/psi/impl/search/PsiSearchHelperImpl.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.psi.impl.search;
  18
  19 import com.intellij.codeInsight.CommentUtil;
  20 import com.intellij.concurrency.JobUtil;
  21 import com.intellij.ide.todo.TodoIndexPatternProvider;
  22 import com.intellij.openapi.application.ApplicationManager;
  23 import com.intellij.openapi.application.ReadAction;
  24 import com.intellij.openapi.application.ReadActionProcessor;
  25 import com.intellij.openapi.application.Result;
  26 import com.intellij.openapi.diagnostic.Logger;
  27 import com.intellij.openapi.progress.ProcessCanceledException;
  28 import com.intellij.openapi.progress.ProgressIndicator;
  29 import com.intellij.openapi.progress.ProgressManager;
  30 import com.intellij.openapi.roots.FileIndexFacade;
  31 import com.intellij.openapi.util.*;
  32 import com.intellij.openapi.util.text.StringUtil;
  33 import com.intellij.openapi.vfs.VirtualFile;
  34 import com.intellij.psi.*;
  35 import com.intellij.psi.impl.PsiManagerEx;
  36 import com.intellij.psi.impl.cache.CacheManager;
  37 import com.intellij.psi.impl.cache.impl.IndexCacheManagerImpl;
  38 import com.intellij.psi.impl.cache.impl.id.IdIndex;
  39 import com.intellij.psi.impl.cache.impl.id.IdIndexEntry;
  40 import com.intellij.psi.search.*;
  41 import com.intellij.psi.search.searches.IndexPatternSearch;
  42 import com.intellij.psi.util.PsiUtilBase;
  43 import com.intellij.util.CommonProcessors;
  44 import com.intellij.util.Processor;
  45 import com.intellij.util.SmartList;
  46 import com.intellij.util.containers.CollectionFactory;
  47 import com.intellij.util.containers.ContainerUtil;
  48 import com.intellij.util.containers.MultiMap;
  49 import com.intellij.util.indexing.FileBasedIndex;
  50 import com.intellij.util.text.StringSearcher;
  51 import gnu.trove.TIntHashSet;
  52 import org.jetbrains.annotations.NotNull;
  53 import org.jetbrains.annotations.Nullable;
  54
  55 import java.util.*;
  56 import java.util.concurrent.atomic.AtomicBoolean;
  57 import java.util.concurrent.atomic.AtomicInteger;
  58
  59 public class PsiSearchHelperImpl implements PsiSearchHelper {
  60   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.search.PsiSearchHelperImpl");
  61
  62   private final PsiManagerEx myManager;
  63   private static final TodoItem[] EMPTY_TODO_ITEMS = new TodoItem[0];
  64
  65   @Override
  66   @NotNull
  67   public SearchScope getUseScope(@NotNull PsiElement element) {
  68     SearchScope scope = element.getUseScope();
  69     for (UseScopeEnlarger enlarger : UseScopeEnlarger.EP_NAME.getExtensions()) {
  70       final SearchScope additionalScope = enlarger.getAdditionalUseScope(element);
  71       if (additionalScope != null) {
  72         scope = scope.union(additionalScope);
  73       }
  74     }
  75     return scope;
  76   }
  77
  78
  79   public PsiSearchHelperImpl(PsiManagerEx manager) {
  80     myManager = manager;
  81   }
  82
  83   @Override
  84   @NotNull
  85   public PsiFile[] findFilesWithTodoItems() {
  86     return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithTodoItems();
  87   }
  88
  89   @Override
  90   @NotNull
  91   public TodoItem[] findTodoItems(@NotNull PsiFile file) {
  92     return findTodoItems(file, 0, file.getTextLength());
  93   }
  94
  95   @Override
  96   @NotNull
  97   public TodoItem[] findTodoItems(@NotNull PsiFile file, int startOffset, int endOffset) {
  98     final Collection<IndexPatternOccurrence> occurrences = IndexPatternSearch.search(file, TodoIndexPatternProvider.getInstance()).findAll();
  99     if (occurrences.isEmpty()) {
 100       return EMPTY_TODO_ITEMS;
 101     }
 102
 103     return processTodoOccurences(startOffset, endOffset, occurrences);
 104   }
 105
 106   private TodoItem[] processTodoOccurences(int startOffset, int endOffset, Collection<IndexPatternOccurrence> occurrences) {
 107     List<TodoItem> items = new ArrayList<TodoItem>(occurrences.size());
 108     TextRange textRange = new TextRange(startOffset, endOffset);
 109     final TodoItemsCreator todoItemsCreator = new TodoItemsCreator();
 110     for(IndexPatternOccurrence occurrence: occurrences) {
 111       TextRange occurrenceRange = occurrence.getTextRange();
 112       if (textRange.contains(occurrenceRange)) {
 113         items.add(todoItemsCreator.createTodo(occurrence));
 114       }
 115     }
 116
 117     return items.toArray(new TodoItem[items.size()]);
 118   }
 119
 120   @NotNull
 121   @Override
 122   public TodoItem[] findTodoItemsLight(@NotNull PsiFile file) {
 123     return findTodoItemsLight(file, 0, file.getTextLength());
 124   }
 125
 126   @NotNull
 127   @Override
 128   public TodoItem[] findTodoItemsLight(@NotNull PsiFile file, int startOffset, int endOffset) {
 129     final Collection<IndexPatternOccurrence> occurrences =
 130       LightIndexPatternSearch.SEARCH.createQuery(new IndexPatternSearch.SearchParameters(file, TodoIndexPatternProvider.getInstance())).findAll();
 131
 132     if (occurrences.isEmpty()) {
 133       return EMPTY_TODO_ITEMS;
 134     }
 135
 136     return processTodoOccurences(startOffset, endOffset, occurrences);
 137   }
 138
 139   @Override
 140   public int getTodoItemsCount(@NotNull PsiFile file) {
 141     int count = CacheManager.SERVICE.getInstance(myManager.getProject()).getTodoCount(file.getVirtualFile(), TodoIndexPatternProvider.getInstance());
 142     if (count != -1) return count;
 143     return findTodoItems(file).length;
 144   }
 145
 146   @Override
 147   public int getTodoItemsCount(@NotNull PsiFile file, @NotNull TodoPattern pattern) {
 148     int count = CacheManager.SERVICE.getInstance(myManager.getProject()).getTodoCount(file.getVirtualFile(), pattern.getIndexPattern());
 149     if (count != -1) return count;
 150     TodoItem[] items = findTodoItems(file);
 151     count = 0;
 152     for (TodoItem item : items) {
 153       if (item.getPattern().equals(pattern)) count++;
 154     }
 155     return count;
 156   }
 157
 158   @Override
 159   @NotNull
 160   public PsiElement[] findCommentsContainingIdentifier(@NotNull String identifier, @NotNull SearchScope searchScope) {
 161     final ArrayList<PsiElement> results = new ArrayList<PsiElement>();
 162     processCommentsContainingIdentifier(identifier, searchScope, new Processor<PsiElement>() {
 163       @Override
 164       public boolean process(PsiElement element) {
 165         synchronized (results) {
 166           results.add(element);
 167         }
 168         return true;
 169       }
 170     });
 171     synchronized (results) {
 172       return PsiUtilBase.toPsiElementArray(results);
 173     }
 174   }
 175
 176   @Override
 177   public boolean processCommentsContainingIdentifier(@NotNull String identifier,
 178                                                      @NotNull SearchScope searchScope,
 179                                                      @NotNull final Processor<PsiElement> processor) {
 180     TextOccurenceProcessor occurrenceProcessor = new TextOccurenceProcessor() {
 181       @Override
 182       public boolean execute(PsiElement element, int offsetInElement) {
 183         if (CommentUtil.isCommentTextElement(element)) {
 184           if (element.findReferenceAt(offsetInElement) == null) {
 185             return processor.process(element);
 186           }
 187         }
 188         return true;
 189       }
 190     };
 191     return processElementsWithWord(occurrenceProcessor, searchScope, identifier, UsageSearchContext.IN_COMMENTS, true);
 192   }
 193
 194   @Override
 195   public boolean processElementsWithWord(@NotNull final TextOccurenceProcessor processor,
 196                                          @NotNull SearchScope searchScope,
 197                                          @NotNull final String text,
 198                                          short searchContext,
 199                                          final boolean caseSensitively) {
 200     if (text.length() == 0) {
 201       throw new IllegalArgumentException("Cannot search for elements with empty text");
 202     }
 203     final ProgressIndicator progress = ProgressManager.getInstance().getProgressIndicator();
 204     if (searchScope instanceof GlobalSearchScope) {
 205       StringSearcher searcher = new StringSearcher(text, caseSensitively, true);
 206
 207       return processElementsWithTextInGlobalScope(processor,
 208                                                   (GlobalSearchScope)searchScope,
 209                                                   searcher,
 210                                                   searchContext, caseSensitively, progress);
 211     }
 212     else {
 213       LocalSearchScope scope = (LocalSearchScope)searchScope;
 214       PsiElement[] scopeElements = scope.getScope();
 215       final boolean ignoreInjectedPsi = scope.isIgnoreInjectedPsi();
 216
 217       return JobUtil.invokeConcurrentlyUnderProgress(Arrays.asList(scopeElements), progress, false, new Processor<PsiElement>() {
 218         @Override
 219         public boolean process(PsiElement scopeElement) {
 220           return processElementsWithWordInScopeElement(scopeElement, processor, text, caseSensitively, ignoreInjectedPsi, progress);
 221         }
 222       });
 223     }
 224   }
 225
 226   private static boolean processElementsWithWordInScopeElement(final PsiElement scopeElement,
 227                                                                final TextOccurenceProcessor processor,
 228                                                                final String word,
 229                                                                final boolean caseSensitive,
 230                                                                final boolean ignoreInjectedPsi,
 231                                                                final ProgressIndicator progress) {
 232     return ApplicationManager.getApplication().runReadAction(new Computable<Boolean>() {
 233       @Override
 234       public Boolean compute() {
 235         StringSearcher searcher = new StringSearcher(word, caseSensitive, true);
 236
 237         return LowLevelSearchUtil.processElementsContainingWordInElement(processor, scopeElement, searcher, !ignoreInjectedPsi, progress);
 238       }
 239     }).booleanValue();
 240   }
 241
 242   private boolean processElementsWithTextInGlobalScope(@NotNull final TextOccurenceProcessor processor,
 243                                                        @NotNull final GlobalSearchScope scope,
 244                                                        @NotNull final StringSearcher searcher,
 245                                                        final short searchContext,
 246                                                        final boolean caseSensitively,
 247                                                        final ProgressIndicator progress) {
 248     LOG.assertTrue(!Thread.holdsLock(PsiLock.LOCK), "You must not run search from within updating PSI activity. Please consider invokeLatering it instead.");
 249     if (progress != null) {
 250       progress.pushState();
 251       progress.setText(PsiBundle.message("psi.scanning.files.progress"));
 252     }
 253
 254     String text = searcher.getPattern();
 255     List<VirtualFile> fileSet = getFilesWithText(scope, searchContext, caseSensitively, text, progress);
 256
 257     if (progress != null) {
 258       progress.setText(PsiBundle.message("psi.search.for.word.progress", text));
 259     }
 260
 261     try {
 262       return processPsiFileRoots(fileSet, new Processor<PsiElement>() {
 263         @Override
 264         public boolean process(PsiElement psiRoot) {
 265           return LowLevelSearchUtil.processElementsContainingWordInElement(processor, psiRoot, searcher, true, progress);
 266         }
 267       }, progress);
 268     }
 269     finally {
 270       if (progress != null) {
 271         progress.popState();
 272       }
 273     }
 274   }
 275
 276   private boolean processPsiFileRoots(@NotNull List<VirtualFile> files,
 277                                       @NotNull final Processor<PsiElement> psiRootProcessor,
 278                                       final ProgressIndicator progress) {
 279     myManager.startBatchFilesProcessingMode();
 280     try {
 281       final AtomicInteger counter = new AtomicInteger(0);
 282       final AtomicBoolean canceled = new AtomicBoolean(false);
 283       final AtomicBoolean pceThrown = new AtomicBoolean(false);
 284
 285       final int size = files.size();
 286       boolean completed = JobUtil.invokeConcurrentlyUnderProgress(files, progress, false, new Processor<VirtualFile>() {
 287         @Override
 288         public boolean process(final VirtualFile vfile) {
 289           final PsiFile file = ApplicationManager.getApplication().runReadAction(new Computable<PsiFile>() {
 290             @Override
 291             public PsiFile compute() {
 292               return myManager.findFile(vfile);
 293             }
 294           });
 295           if (file != null && !(file instanceof PsiBinaryFile)) {
 296             file.getViewProvider().getContents(); // load contents outside readaction
 297             ApplicationManager.getApplication().runReadAction(new Runnable() {
 298               @Override
 299               public void run() {
 300                 try {
 301                   if (myManager.getProject().isDisposed()) throw new ProcessCanceledException();
 302                   PsiElement[] psiRoots = file.getPsiRoots();
 303                   Set<PsiElement> processed = new HashSet<PsiElement>(psiRoots.length * 2, (float)0.5);
 304                   for (PsiElement psiRoot : psiRoots) {
 305                     if (progress != null) progress.checkCanceled();
 306                     if (!processed.add(psiRoot)) continue;
 307                     if (!psiRootProcessor.process(psiRoot)) {
 308                       canceled.set(true);
 309                       return;
 310                     }
 311                   }
 312                   myManager.dropResolveCaches();
 313                 }
 314                 catch (ProcessCanceledException e) {
 315                   canceled.set(true);
 316                   pceThrown.set(true);
 317                 }
 318               }
 319             });
 320           }
 321           if (progress != null && progress.isRunning()) {
 322             double fraction = (double)counter.incrementAndGet() / size;
 323             progress.setFraction(fraction);
 324           }
 325           return !canceled.get();
 326         }
 327       });
 328
 329       if (pceThrown.get()) {
 330         throw new ProcessCanceledException();
 331       }
 332
 333       return completed;
 334     }
 335     finally {
 336       myManager.finishBatchFilesProcessingMode();
 337     }
 338   }
 339
 340   @NotNull
 341   private List<VirtualFile> getFilesWithText(@NotNull GlobalSearchScope scope,
 342                                          final short searchContext,
 343                                          final boolean caseSensitively,
 344                                          @NotNull String text,
 345                                          ProgressIndicator progress) {
 346     myManager.startBatchFilesProcessingMode();
 347     try {
 348       final List<VirtualFile> result = new ArrayList<VirtualFile>();
 349       boolean success = processFilesWithText(
 350         scope,
 351         searchContext,
 352         caseSensitively,
 353         text,
 354         new CommonProcessors.CollectProcessor<VirtualFile>(result)
 355       );
 356       LOG.assertTrue(success);
 357       return result;
 358     }
 359     finally {
 360       myManager.finishBatchFilesProcessingMode();
 361     }
 362   }
 363
 364   public boolean processFilesWithText(@NotNull final GlobalSearchScope scope,
 365                                       final short searchContext,
 366                                       final boolean caseSensitively,
 367                                       @NotNull String text,
 368                                       @NotNull final Processor<VirtualFile> processor) {
 369     final ArrayList<IdIndexEntry> entries = getWordEntries(text, caseSensitively);
 370     if (entries.isEmpty()) return true;
 371
 372     final Collection<VirtualFile> fileSet = ApplicationManager.getApplication().runReadAction(new Computable<Collection<VirtualFile>>() {
 373       @Override
 374       public Collection<VirtualFile> compute() {
 375         final CommonProcessors.CollectProcessor<VirtualFile> collectProcessor = new CommonProcessors.CollectProcessor<VirtualFile>();
 376         FileBasedIndex.getInstance().processFilesContainingAllKeys(IdIndex.NAME, entries, scope, new Condition<Integer>() {
 377           @Override
 378           public boolean value(Integer integer) {
 379             return (integer.intValue() & searchContext) != 0;
 380           }
 381         }, collectProcessor);
 382         return collectProcessor.getResults();
 383       }
 384     });
 385
 386     final FileIndexFacade index = FileIndexFacade.getInstance(myManager.getProject());
 387     return ContainerUtil.process(fileSet, new ReadActionProcessor<VirtualFile>() {
 388       @Override
 389       public boolean processInReadAction(VirtualFile virtualFile) {
 390         return !IndexCacheManagerImpl.shouldBeFound(scope, virtualFile, index) || processor.process(virtualFile);
 391       }
 392     });
 393   }
 394
 395   @Override
 396   @NotNull
 397   public PsiFile[] findFilesWithPlainTextWords(@NotNull String word) {
 398     return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(word,
 399                                                                                      UsageSearchContext.IN_PLAIN_TEXT,
 400                                                                                      GlobalSearchScope.projectScope(myManager.getProject()),
 401                                                                                      true);
 402   }
 403
 404
 405   @Override
 406   public void processUsagesInNonJavaFiles(@NotNull String qName,
 407                                           @NotNull PsiNonJavaFileReferenceProcessor processor,
 408                                           @NotNull GlobalSearchScope searchScope) {
 409     processUsagesInNonJavaFiles(null, qName, processor, searchScope);
 410   }
 411
 412   @Override
 413   public void processUsagesInNonJavaFiles(@Nullable final PsiElement originalElement,
 414                                           @NotNull String qName,
 415                                           @NotNull final PsiNonJavaFileReferenceProcessor processor,
 416                                           @NotNull GlobalSearchScope searchScope) {
 417     if (qName.length() == 0) {
 418       throw new IllegalArgumentException("Cannot search for elements with empty text");
 419     }
 420     final ProgressIndicator progress = ProgressManager.getInstance().getProgressIndicator();
 421
 422     int dotIndex = qName.lastIndexOf('.');
 423     int dollarIndex = qName.lastIndexOf('$');
 424     int maxIndex = Math.max(dotIndex, dollarIndex);
 425     final String wordToSearch = maxIndex >= 0 ? qName.substring(maxIndex + 1) : qName;
 426     if (originalElement != null && myManager.isInProject(originalElement) && searchScope.isSearchInLibraries()) {
 427       searchScope = searchScope.intersectWith(GlobalSearchScope.projectScope(myManager.getProject()));
 428     }
 429     final GlobalSearchScope theSearchScope = searchScope;
 430     PsiFile[] files = ApplicationManager.getApplication().runReadAction(new Computable<PsiFile[]>() {
 431       @Override
 432       public PsiFile[] compute() {
 433         return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(wordToSearch, UsageSearchContext.IN_PLAIN_TEXT, theSearchScope, true);
 434       }
 435     });
 436
 437     final StringSearcher searcher = new StringSearcher(qName, true, true);
 438
 439     if (progress != null) {
 440       progress.pushState();
 441       progress.setText(PsiBundle.message("psi.search.in.non.java.files.progress"));
 442     }
 443
 444     final SearchScope useScope = new ReadAction<SearchScope>() {
 445       @Override
 446       protected void run(final Result<SearchScope> result) {
 447         if (originalElement != null) {
 448           result.setResult(getUseScope(originalElement));
 449         }
 450       }
 451     }.execute().getResultObject();
 452
 453     final Ref<Boolean> cancelled = new Ref<Boolean>(Boolean.FALSE);
 454     final GlobalSearchScope finalScope = searchScope;
 455     for (int i = 0; i < files.length; i++) {
 456       if (progress != null) progress.checkCanceled();
 457
 458       final PsiFile psiFile = files[i];
 459
 460       ApplicationManager.getApplication().runReadAction(new Runnable() {
 461         @Override
 462         public void run() {
 463           CharSequence text = psiFile.getViewProvider().getContents();
 464           for (int index = LowLevelSearchUtil.searchWord(text, 0, text.length(), searcher, progress); index >= 0;) {
 465             PsiReference referenceAt = psiFile.findReferenceAt(index);
 466             if (referenceAt == null || useScope == null ||
 467                 !PsiSearchScopeUtil.isInScope(useScope.intersectWith(finalScope), psiFile)) {
 468               if (!processor.process(psiFile, index, index + searcher.getPattern().length())) {
 469                 cancelled.set(Boolean.TRUE);
 470                 return;
 471               }
 472             }
 473
 474             index = LowLevelSearchUtil.searchWord(text, index + searcher.getPattern().length(), text.length(), searcher, progress);
 475           }
 476         }
 477       });
 478       if (cancelled.get()) break;
 479       if (progress != null) {
 480         progress.setFraction((double)(i + 1) / files.length);
 481       }
 482     }
 483
 484     if (progress != null) {
 485       progress.popState();
 486     }
 487   }
 488
 489   @Override
 490   public void processAllFilesWithWord(@NotNull String word, @NotNull GlobalSearchScope scope, @NotNull Processor<PsiFile> processor, final boolean caseSensitively) {
 491     CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_CODE, scope, caseSensitively);
 492   }
 493
 494   @Override
 495   public void processAllFilesWithWordInText(@NotNull final String word, @NotNull final GlobalSearchScope scope, @NotNull final Processor<PsiFile> processor,
 496                                             final boolean caseSensitively) {
 497     CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_PLAIN_TEXT, scope, caseSensitively);
 498   }
 499
 500   @Override
 501   public void processAllFilesWithWordInComments(@NotNull String word, @NotNull GlobalSearchScope scope, @NotNull Processor<PsiFile> processor) {
 502     CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_COMMENTS, scope, true);
 503   }
 504
 505   @Override
 506   public void processAllFilesWithWordInLiterals(@NotNull String word, @NotNull GlobalSearchScope scope, @NotNull Processor<PsiFile> processor) {
 507     CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_STRINGS, scope, true);
 508   }
 509
 510   private static class RequestWithProcessor {
 511     final PsiSearchRequest request;
 512     Processor<PsiReference> refProcessor;
 513
 514     private RequestWithProcessor(PsiSearchRequest first, Processor<PsiReference> second) {
 515       request = first;
 516       refProcessor = second;
 517     }
 518
 519     boolean uniteWith(final RequestWithProcessor another) {
 520       if (request.equals(another.request)) {
 521         final Processor<PsiReference> myProcessor = refProcessor;
 522         if (myProcessor != another.refProcessor) {
 523           refProcessor = new Processor<PsiReference>() {
 524             @Override
 525             public boolean process(PsiReference psiReference) {
 526               return myProcessor.process(psiReference) && another.refProcessor.process(psiReference);
 527             }
 528           };
 529         }
 530         return true;
 531       }
 532       return false;
 533     }
 534
 535     @Override
 536     public String toString() {
 537       return request.toString();
 538     }
 539   }
 540
 541   @Override
 542   public boolean processRequests(@NotNull SearchRequestCollector collector, @NotNull Processor<PsiReference> processor) {
 543     Map<SearchRequestCollector, Processor<PsiReference>> collectors = CollectionFactory.hashMap();
 544     collectors.put(collector, processor);
 545
 546     appendCollectorsFromQueryRequests(collectors);
 547
 548     ProgressIndicator progress = ProgressManager.getInstance().getProgressIndicator();
 549     do {
 550       final MultiMap<Set<IdIndexEntry>, RequestWithProcessor> globals = new MultiMap<Set<IdIndexEntry>, RequestWithProcessor>();
 551       final List<Computable<Boolean>> customs = CollectionFactory.arrayList();
 552       final LinkedHashSet<RequestWithProcessor> locals = CollectionFactory.linkedHashSet();
 553       distributePrimitives(collectors, locals, globals, customs);
 554
 555       if (!processGlobalRequestsOptimized(globals, progress)) {
 556         return false;
 557       }
 558
 559       for (RequestWithProcessor local : locals) {
 560         if (!processSingleRequest(local.request, local.refProcessor)) {
 561           return false;
 562         }
 563       }
 564
 565       for (Computable<Boolean> custom : customs) {
 566         if (!custom.compute()) {
 567           return false;
 568         }
 569       }
 570     } while (appendCollectorsFromQueryRequests(collectors));
 571
 572     return true;
 573   }
 574
 575   private static boolean appendCollectorsFromQueryRequests(Map<SearchRequestCollector, Processor<PsiReference>> collectors) {
 576     boolean changed = false;
 577     LinkedList<SearchRequestCollector> queue = new LinkedList<SearchRequestCollector>(collectors.keySet());
 578     while (!queue.isEmpty()) {
 579       final SearchRequestCollector each = queue.removeFirst();
 580       for (QuerySearchRequest request : each.takeQueryRequests()) {
 581         request.runQuery();
 582         collectors.put(request.collector, request.processor);
 583         queue.addLast(request.collector);
 584         changed = true;
 585       }
 586     }
 587     return changed;
 588   }
 589
 590   private boolean processGlobalRequestsOptimized(MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 591                                                  final ProgressIndicator progress) {
 592     if (singles.isEmpty()) {
 593       return true;
 594     }
 595
 596     if (singles.size() == 1) {
 597       final Collection<RequestWithProcessor> requests = singles.get(singles.keySet().iterator().next());
 598       if (requests.size() == 1) {
 599         final RequestWithProcessor theOnly = requests.iterator().next();
 600         return processSingleRequest(theOnly.request, theOnly.refProcessor);
 601       }
 602     }
 603
 604     if (progress != null) {
 605       progress.pushState();
 606       progress.setText(PsiBundle.message("psi.scanning.files.progress"));
 607     }
 608
 609     final MultiMap<VirtualFile, RequestWithProcessor> candidateFiles = collectFiles(singles, progress);
 610
 611     try {
 612       if (candidateFiles.isEmpty()) {
 613         return true;
 614       }
 615
 616       final Map<RequestWithProcessor, StringSearcher> searchers = new HashMap<RequestWithProcessor, StringSearcher>();
 617       final Set<String> allWords = new TreeSet<String>();
 618       for (RequestWithProcessor singleRequest : candidateFiles.values()) {
 619         searchers.put(singleRequest, new StringSearcher(singleRequest.request.word, singleRequest.request.caseSensitive, true));
 620         allWords.add(singleRequest.request.word);
 621       }
 622
 623       if (progress != null) {
 624         final StringBuilder result = new StringBuilder();
 625         for (String string : allWords) {
 626           if (string != null && string.length() != 0) {
 627             if (result.length() > 50) {
 628               result.append("...");
 629               break;
 630             }
 631             if (result.length() != 0) result.append(", ");
 632             result.append(string);
 633           }
 634         }
 635         progress.setText(PsiBundle.message("psi.search.for.word.progress", result.toString()));
 636       }
 637
 638       return processPsiFileRoots(new ArrayList<VirtualFile>(candidateFiles.keySet()), new Processor<PsiElement>() {
 639                                    @Override
 640                                    public boolean process(PsiElement psiRoot) {
 641                                      final VirtualFile vfile = psiRoot.getContainingFile().getVirtualFile();
 642                                      for (final RequestWithProcessor singleRequest : candidateFiles.get(vfile)) {
 643                                        StringSearcher searcher = searchers.get(singleRequest);
 644                                        TextOccurenceProcessor adapted = adaptProcessor(singleRequest.request, singleRequest.refProcessor);
 645                                        if (!LowLevelSearchUtil.processElementsContainingWordInElement(adapted, psiRoot, searcher, true, progress)) {
 646                                          return false;
 647                                        }
 648                                      }
 649                                      return true;
 650                                    }
 651                                  }, progress);
 652     }
 653     finally {
 654       if (progress != null) {
 655         progress.popState();
 656       }
 657     }
 658   }
 659
 660   private static TextOccurenceProcessor adaptProcessor(final PsiSearchRequest singleRequest,
 661                                                        final Processor<PsiReference> consumer) {
 662     final SearchScope searchScope = singleRequest.searchScope;
 663     final boolean ignoreInjectedPsi = searchScope instanceof LocalSearchScope && ((LocalSearchScope)searchScope).isIgnoreInjectedPsi();
 664     final RequestResultProcessor wrapped = singleRequest.processor;
 665     return new TextOccurenceProcessor() {
 666       @Override
 667       public boolean execute(PsiElement element, int offsetInElement) {
 668         if (ignoreInjectedPsi && element instanceof PsiLanguageInjectionHost) return true;
 669
 670         return wrapped.processTextOccurrence(element, offsetInElement, consumer);
 671       }
 672     };
 673   }
 674
 675   private MultiMap<VirtualFile, RequestWithProcessor> collectFiles(MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 676                                                                    ProgressIndicator progress) {
 677     final FileIndexFacade index = FileIndexFacade.getInstance(myManager.getProject());
 678     final MultiMap<VirtualFile, RequestWithProcessor> result = createMultiMap();
 679     for (final Set<IdIndexEntry> key : singles.keySet()) {
 680       if (key.isEmpty()) {
 681         continue;
 682       }
 683
 684
 685       final Collection<RequestWithProcessor> data = singles.get(key);
 686       final GlobalSearchScope commonScope = uniteScopes(data);
 687
 688       if (key.size() == 1) {
 689         result.putAllValues(findFilesWithIndexEntry(key.iterator().next(), index, data, commonScope, progress));
 690         continue;
 691       }
 692
 693       final Collection<VirtualFile> fileSet = ApplicationManager.getApplication().runReadAction(new Computable<Collection<VirtualFile>>() {
 694         @Override
 695         public Collection<VirtualFile> compute() {
 696           final CommonProcessors.CollectProcessor<VirtualFile> processor = new CommonProcessors.CollectProcessor<VirtualFile>();
 697           FileBasedIndex.getInstance().processFilesContainingAllKeys(IdIndex.NAME, key, commonScope, null, processor);
 698           return processor.getResults();
 699         }
 700       });
 701
 702       for (final VirtualFile file : fileSet) {
 703         if (progress != null) {
 704           progress.checkCanceled();
 705         }
 706         for (final IdIndexEntry entry : key) {
 707           ApplicationManager.getApplication().runReadAction(new Runnable() {
 708             @Override
 709             public void run() {
 710               FileBasedIndex.getInstance().processValues(IdIndex.NAME, entry, file, new FileBasedIndex.ValueProcessor<Integer>() {
 711                 @Override
 712                 public boolean process(VirtualFile file, Integer value) {
 713                   if (IndexCacheManagerImpl.shouldBeFound(commonScope, file, index)) {
 714                     int mask = value.intValue();
 715                     for (RequestWithProcessor single : data) {
 716                       final PsiSearchRequest request = single.request;
 717                       if ((mask & request.searchContext) != 0 && ((GlobalSearchScope)request.searchScope).contains(file)) {
 718                         result.putValue(file, single);
 719                       }
 720                     }
 721                   }
 722                   return true;
 723                 }
 724               }, commonScope);
 725
 726             }
 727           });
 728         }
 729       }
 730     }
 731     return result;
 732   }
 733
 734   private static MultiMap<VirtualFile, RequestWithProcessor> createMultiMap() {
 735     return new MultiMap<VirtualFile, RequestWithProcessor>(){
 736       @Override
 737       protected Collection<RequestWithProcessor> createCollection() {
 738         return new SmartList<RequestWithProcessor>(); // usually there is just one request
 739       }
 740     };
 741   }
 742
 743   private static GlobalSearchScope uniteScopes(Collection<RequestWithProcessor> requests) {
 744     GlobalSearchScope commonScope = null;
 745     for (RequestWithProcessor r : requests) {
 746       final GlobalSearchScope scope = (GlobalSearchScope)r.request.searchScope;
 747       commonScope = commonScope == null ? scope : commonScope.uniteWith(scope);
 748     }
 749     assert commonScope != null;
 750     return commonScope;
 751   }
 752
 753   private static MultiMap<VirtualFile, RequestWithProcessor> findFilesWithIndexEntry(final IdIndexEntry entry,
 754                                                                                      final FileIndexFacade index,
 755                                                                                      final Collection<RequestWithProcessor> data,
 756                                                                                      final GlobalSearchScope commonScope,
 757                                                                                      final ProgressIndicator progress) {
 758     final MultiMap<VirtualFile, RequestWithProcessor> local = createMultiMap();
 759     ApplicationManager.getApplication().runReadAction(new Runnable() {
 760       @Override
 761       public void run() {
 762         if (progress != null) progress.checkCanceled();
 763         FileBasedIndex.getInstance().processValues(IdIndex.NAME, entry, null, new FileBasedIndex.ValueProcessor<Integer>() {
 764             @Override
 765             public boolean process(VirtualFile file, Integer value) {
 766               if (progress != null) progress.checkCanceled();
 767
 768               if (IndexCacheManagerImpl.shouldBeFound(commonScope, file, index)) {
 769                 int mask = value.intValue();
 770                 for (RequestWithProcessor single : data) {
 771                   final PsiSearchRequest request = single.request;
 772                   if ((mask & request.searchContext) != 0 && ((GlobalSearchScope)request.searchScope).contains(file)) {
 773                     local.putValue(file, single);
 774                   }
 775                 }
 776               }
 777               return true;
 778             }
 779           }, commonScope);
 780       }
 781     });
 782
 783     return local;
 784   }
 785
 786   private static void distributePrimitives(final Map<SearchRequestCollector, Processor<PsiReference>> collectors,
 787                                     LinkedHashSet<RequestWithProcessor> locals,
 788                                     MultiMap<Set<IdIndexEntry>, RequestWithProcessor> singles,
 789                                     List<Computable<Boolean>> customs) {
 790     for (final SearchRequestCollector collector : collectors.keySet()) {
 791       final Processor<PsiReference> processor = collectors.get(collector);
 792       for (final PsiSearchRequest primitive : collector.takeSearchRequests()) {
 793         final SearchScope scope = primitive.searchScope;
 794         if (scope instanceof LocalSearchScope) {
 795           registerRequest(locals, primitive, processor);
 796         } else {
 797           final List<String> words = StringUtil.getWordsIn(primitive.word);
 798           final Set<IdIndexEntry> key = new HashSet<IdIndexEntry>(words.size() * 2);
 799           for (String word : words) {
 800             key.add(new IdIndexEntry(word, primitive.caseSensitive));
 801           }
 802           registerRequest(singles.getModifiable(key), primitive, processor);
 803         }
 804       }
 805       for (final Processor<Processor<PsiReference>> customAction : collector.takeCustomSearchActions()) {
 806         customs.add(new Computable<Boolean>() {
 807           @Override
 808           public Boolean compute() {
 809             return customAction.process(processor);
 810           }
 811         });
 812       }
 813     }
 814   }
 815
 816   private static void registerRequest(Collection<RequestWithProcessor> collection,
 817                                       PsiSearchRequest primitive, Processor<PsiReference> processor) {
 818     final RequestWithProcessor newValue = new RequestWithProcessor(primitive, processor);
 819     for (RequestWithProcessor existing : collection) {
 820       if (existing.uniteWith(newValue)) {
 821         return;
 822       }
 823     }
 824     collection.add(newValue);
 825   }
 826
 827   private boolean processSingleRequest(PsiSearchRequest single, Processor<PsiReference> consumer) {
 828     return processElementsWithWord(adaptProcessor(single, consumer), single.searchScope, single.word, single.searchContext, single.caseSensitive);
 829   }
 830
 831   @Override
 832   public SearchCostResult isCheapEnoughToSearch(@NotNull String name,
 833                                                 @NotNull final GlobalSearchScope scope,
 834                                                 @Nullable final PsiFile fileToIgnoreOccurencesIn,
 835                                                 @Nullable ProgressIndicator progress) {
 836
 837     final ArrayList<IdIndexEntry> keys = getWordEntries(name, true);
 838     if (keys.isEmpty()) return SearchCostResult.ZERO_OCCURRENCES;
 839
 840     final TIntHashSet set = ApplicationManager.getApplication().runReadAction(new NullableComputable<TIntHashSet>() {
 841       @Override
 842       public TIntHashSet compute() {
 843         return FileBasedIndex.getInstance().collectFileIdsContainingAllKeys(IdIndex.NAME, keys, scope, null);
 844       }
 845     });
 846
 847     if (set == null || set.size() > 1000) {
 848       return SearchCostResult.TOO_MANY_OCCURRENCES;
 849     }
 850
 851     final AtomicInteger count = new AtomicInteger();
 852
 853     final FileIndexFacade index = FileIndexFacade.getInstance(myManager.getProject());
 854     final Processor<VirtualFile> processor = new Processor<VirtualFile>() {
 855       private final VirtualFile fileToIgnoreOccurencesInVirtualFile =
 856         fileToIgnoreOccurencesIn != null ? fileToIgnoreOccurencesIn.getVirtualFile() : null;
 857
 858       @Override
 859       public boolean process(VirtualFile file) {
 860         if (file == fileToIgnoreOccurencesInVirtualFile) return true;
 861         if (!IndexCacheManagerImpl.shouldBeFound(scope, file, index)) return true;
 862         final int value = count.incrementAndGet();
 863         return value < 10;
 864       }
 865     };
 866     final boolean cheap = ApplicationManager.getApplication().runReadAction(new NullableComputable<Boolean>() {
 867       @Override
 868       public Boolean compute() {
 869         return FileBasedIndex.processVirtualFiles(set, scope, processor);
 870       }
 871     });
 872
 873     if (!cheap) {
 874       return SearchCostResult.TOO_MANY_OCCURRENCES;
 875     }
 876
 877     return count.get() == 0 ? SearchCostResult.ZERO_OCCURRENCES : SearchCostResult.FEW_OCCURRENCES;
 878   }
 879
 880   private static ArrayList<IdIndexEntry> getWordEntries(String name, boolean caseSensitively) {
 881     List<String> words = StringUtil.getWordsIn(name);
 882     final ArrayList<IdIndexEntry> keys = new ArrayList<IdIndexEntry>();
 883     for (String word : words) {
 884       keys.add(new IdIndexEntry(word, caseSensitively));
 885     }
 886     return keys;
 887   }
 888 }