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