[peter]
[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.*;
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 }