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