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