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