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