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