5bdbcc2a6fe1e23e4ca17f4d30e636042ec9f7ee
[idea/community.git] / platform / indexing-impl / src / com / intellij / psi / impl / search / PsiSearchHelperImpl.java
1 // Copyright 2000-2019 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.intellij.psi.impl.search;
3
4 import com.intellij.concurrency.AsyncFuture;
5 import com.intellij.concurrency.AsyncUtil;
6 import com.intellij.concurrency.JobLauncher;
7 import com.intellij.openapi.application.ApplicationManager;
8 import com.intellij.openapi.application.ReadAction;
9 import com.intellij.openapi.application.ReadActionProcessor;
10 import com.intellij.openapi.application.ex.ApplicationEx;
11 import com.intellij.openapi.application.ex.ApplicationUtil;
12 import com.intellij.openapi.diagnostic.Logger;
13 import com.intellij.openapi.extensions.ExtensionPointName;
14 import com.intellij.openapi.progress.*;
15 import com.intellij.openapi.progress.impl.CoreProgressManager;
16 import com.intellij.openapi.progress.util.TooManyUsagesStatus;
17 import com.intellij.openapi.project.DumbService;
18 import com.intellij.openapi.project.IndexNotReadyException;
19 import com.intellij.openapi.project.Project;
20 import com.intellij.openapi.roots.FileIndexFacade;
21 import com.intellij.openapi.util.*;
22 import com.intellij.openapi.util.registry.Registry;
23 import com.intellij.openapi.util.text.StringUtil;
24 import com.intellij.openapi.vfs.VirtualFile;
25 import com.intellij.psi.*;
26 import com.intellij.psi.impl.PsiManagerEx;
27 import com.intellij.psi.impl.cache.CacheManager;
28 import com.intellij.psi.impl.cache.impl.id.IdIndex;
29 import com.intellij.psi.impl.cache.impl.id.IdIndexEntry;
30 import com.intellij.psi.search.*;
31 import com.intellij.psi.util.PsiUtilCore;
32 import com.intellij.usageView.UsageInfo;
33 import com.intellij.usageView.UsageInfoFactory;
34 import com.intellij.util.Processor;
35 import com.intellij.util.Processors;
36 import com.intellij.util.SmartList;
37 import com.intellij.util.codeInsight.CommentUtilCore;
38 import com.intellij.util.containers.ContainerUtil;
39 import com.intellij.util.indexing.FileBasedIndex;
40 import com.intellij.util.text.StringSearcher;
41 import gnu.trove.THashMap;
42 import gnu.trove.THashSet;
43 import org.jetbrains.annotations.NotNull;
44 import org.jetbrains.annotations.Nullable;
45
46 import java.util.*;
47 import java.util.concurrent.atomic.AtomicBoolean;
48 import java.util.concurrent.atomic.AtomicInteger;
49 import java.util.concurrent.atomic.AtomicLong;
50
51 public class PsiSearchHelperImpl implements PsiSearchHelper {
52   private static final ExtensionPointName<ScopeOptimizer> USE_SCOPE_OPTIMIZER_EP_NAME = ExtensionPointName.create("com.intellij.useScopeOptimizer");
53
54   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.search.PsiSearchHelperImpl");
55   private final PsiManagerEx myManager;
56   private final DumbService myDumbService;
57
58   public enum Options {
59     PROCESS_INJECTED_PSI, CASE_SENSITIVE_SEARCH, PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE
60   }
61
62   @Override
63   @NotNull
64   public SearchScope getUseScope(@NotNull PsiElement element) {
65     SearchScope scope = element.getUseScope();
66     for (UseScopeEnlarger enlarger : UseScopeEnlarger.EP_NAME.getExtensions()) {
67       ProgressManager.checkCanceled();
68       final SearchScope additionalScope = enlarger.getAdditionalUseScope(element);
69       if (additionalScope != null) {
70         scope = scope.union(additionalScope);
71       }
72     }
73
74     SearchScope scopeToRestrict = ScopeOptimizer.calculateOverallRestrictedUseScope(USE_SCOPE_OPTIMIZER_EP_NAME.getExtensions(), element);
75     if (scopeToRestrict != null) {
76       scope = scope.intersectWith(scopeToRestrict);
77     }
78     return scope;
79   }
80
81   public PsiSearchHelperImpl(@NotNull PsiManagerEx manager) {
82     myManager = manager;
83     myDumbService = DumbService.getInstance(myManager.getProject());
84   }
85
86   @Override
87   @NotNull
88   public PsiElement[] findCommentsContainingIdentifier(@NotNull String identifier, @NotNull SearchScope searchScope) {
89     final List<PsiElement> result = Collections.synchronizedList(new ArrayList<>());
90     Processor<PsiElement> processor = Processors.cancelableCollectProcessor(result);
91     processCommentsContainingIdentifier(identifier, searchScope, processor);
92     return PsiUtilCore.toPsiElementArray(result);
93   }
94
95   @Override
96   public boolean processCommentsContainingIdentifier(@NotNull String identifier,
97                                                      @NotNull SearchScope searchScope,
98                                                      @NotNull final Processor<? super PsiElement> processor) {
99     TextOccurenceProcessor occurrenceProcessor = (element, offsetInElement) -> {
100       if (CommentUtilCore.isCommentTextElement(element) && element.findReferenceAt(offsetInElement) == null) {
101         return processor.process(element);
102       }
103       return true;
104     };
105     return processElementsWithWord(occurrenceProcessor, searchScope, identifier, UsageSearchContext.IN_COMMENTS, true);
106   }
107
108   @Override
109   public boolean processElementsWithWord(@NotNull TextOccurenceProcessor processor,
110                                          @NotNull SearchScope searchScope,
111                                          @NotNull String text,
112                                          short searchContext,
113                                          boolean caseSensitive) {
114     return processElementsWithWord(processor, searchScope, text, searchContext, caseSensitive, shouldProcessInjectedPsi(searchScope));
115   }
116
117   @Override
118   public boolean processElementsWithWord(@NotNull TextOccurenceProcessor processor,
119                                          @NotNull SearchScope searchScope,
120                                          @NotNull String text,
121                                          short searchContext,
122                                          boolean caseSensitive,
123                                          boolean processInjectedPsi) {
124     final EnumSet<Options> options = EnumSet.of(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE);
125     if (caseSensitive) options.add(Options.CASE_SENSITIVE_SEARCH);
126     if (processInjectedPsi) options.add(Options.PROCESS_INJECTED_PSI);
127
128     return processElementsWithWord(processor, searchScope, text, searchContext, options, null);
129   }
130
131   @NotNull
132   @Override
133   public AsyncFuture<Boolean> processElementsWithWordAsync(@NotNull final TextOccurenceProcessor processor,
134                                                            @NotNull SearchScope searchScope,
135                                                            @NotNull final String text,
136                                                            final short searchContext,
137                                                            final boolean caseSensitively) {
138     boolean result = processElementsWithWord(processor, searchScope, text, searchContext, caseSensitively,
139                                              shouldProcessInjectedPsi(searchScope));
140     return AsyncUtil.wrapBoolean(result);
141   }
142
143   public boolean processElementsWithWord(@NotNull final TextOccurenceProcessor processor,
144                                          @NotNull SearchScope searchScope,
145                                          @NotNull final String text,
146                                          final short searchContext,
147                                          @NotNull EnumSet<Options> options,
148                                          @Nullable String containerName) {
149     return bulkProcessElementsWithWord(searchScope, text, searchContext, options, containerName, (scope, offsetsInScope, searcher) ->
150       LowLevelSearchUtil.processElementsAtOffsets(scope, searcher, options.contains(Options.PROCESS_INJECTED_PSI), getOrCreateIndicator(),
151                                                   offsetsInScope, processor));
152   }
153
154   private boolean bulkProcessElementsWithWord(@NotNull SearchScope searchScope,
155                                               @NotNull final String text,
156                                               final short searchContext,
157                                               @NotNull EnumSet<Options> options,
158                                               @Nullable String containerName, @NotNull final BulkOccurrenceProcessor processor) {
159     if (text.isEmpty()) {
160       throw new IllegalArgumentException("Cannot search for elements with empty text");
161     }
162     final ProgressIndicator progress = getOrCreateIndicator();
163     if (searchScope instanceof GlobalSearchScope) {
164       StringSearcher searcher = new StringSearcher(text, options.contains(Options.CASE_SENSITIVE_SEARCH), true,
165                                                    searchContext == UsageSearchContext.IN_STRINGS,
166                                                    options.contains(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE));
167
168       return processElementsWithTextInGlobalScope((GlobalSearchScope)searchScope, searcher, searchContext,
169                                                   options.contains(Options.CASE_SENSITIVE_SEARCH), containerName, progress, processor);
170     }
171     LocalSearchScope scope = (LocalSearchScope)searchScope;
172     PsiElement[] scopeElements = scope.getScope();
173     final StringSearcher searcher = new StringSearcher(text, options.contains(Options.CASE_SENSITIVE_SEARCH), true,
174                                                        searchContext == UsageSearchContext.IN_STRINGS,
175                                                        options.contains(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE));
176     ReadActionProcessor<PsiElement> localProcessor = new ReadActionProcessor<PsiElement>() {
177       @Override
178       public boolean processInReadAction(PsiElement scopeElement) {
179         if (!scopeElement.isValid()) return true;
180         if (!scopeElement.isPhysical() || scopeElement instanceof PsiCompiledElement) {
181           scopeElement = scopeElement.getNavigationElement();
182         }
183         if (scopeElement instanceof PsiCompiledElement) {
184           // can't scan text of the element
185           return true;
186         }
187         if (scopeElement.getTextRange() == null) {
188           // clients can put whatever they want to the LocalSearchScope. Skip what we can't process.
189           LOG.debug("Element " + scopeElement + " of class " + scopeElement.getClass() + " has null range");
190           return true;
191         }
192         return processor.execute(scopeElement, LowLevelSearchUtil.getTextOccurrencesInScope(scopeElement, searcher, progress), searcher);
193       }
194
195       @Override
196       public String toString() {
197         return processor.toString();
198       }
199     };
200     return JobLauncher.getInstance().invokeConcurrentlyUnderProgress(Arrays.asList(scopeElements), progress, localProcessor);
201   }
202
203   @NotNull
204   private static ProgressIndicator getOrCreateIndicator() {
205     ProgressIndicator progress = ProgressIndicatorProvider.getGlobalProgressIndicator();
206     if (progress == null) progress = new EmptyProgressIndicator();
207     progress.setIndeterminate(false);
208     return progress;
209   }
210
211   public static boolean shouldProcessInjectedPsi(@NotNull SearchScope scope) {
212     return !(scope instanceof LocalSearchScope) || !((LocalSearchScope)scope).isIgnoreInjectedPsi();
213   }
214
215   @NotNull
216   private static Processor<PsiElement> localProcessor(@NotNull final ProgressIndicator progress,
217                                                       @NotNull final StringSearcher searcher,
218                                                       @NotNull final BulkOccurrenceProcessor processor) {
219     return new ReadActionProcessor<PsiElement>() {
220       @Override
221       public boolean processInReadAction(PsiElement scopeElement) {
222         if (scopeElement instanceof PsiCompiledElement) {
223           // can't scan text of the element
224           return true;
225         }
226
227         return scopeElement.isValid() &&
228                processor.execute(scopeElement, LowLevelSearchUtil.getTextOccurrencesInScope(scopeElement, searcher, progress), searcher);
229       }
230
231       @Override
232       public String toString() {
233         return processor.toString();
234       }
235     };
236   }
237
238   private boolean processElementsWithTextInGlobalScope(@NotNull final GlobalSearchScope scope,
239                                                        @NotNull final StringSearcher searcher,
240                                                        final short searchContext,
241                                                        final boolean caseSensitively,
242                                                        @Nullable String containerName,
243                                                        @NotNull ProgressIndicator progress,
244                                                        @NotNull final BulkOccurrenceProcessor processor) {
245     progress.pushState();
246     boolean result;
247     try {
248       progress.setText(PsiBundle.message("psi.scanning.files.progress"));
249
250       String text = searcher.getPattern();
251       Set<VirtualFile> fileSet = new THashSet<>();
252       getFilesWithText(scope, searchContext, caseSensitively, text, fileSet);
253
254       progress.setText(PsiBundle.message("psi.search.for.word.progress", text));
255
256       final Processor<PsiElement> localProcessor = localProcessor(progress, searcher, processor);
257       if (containerName != null) {
258         List<VirtualFile> intersectionWithContainerFiles = new ArrayList<>();
259         // intersectionWithContainerFiles holds files containing words from both `text` and `containerName`
260         getFilesWithText(scope, searchContext, caseSensitively, text+" "+containerName, intersectionWithContainerFiles);
261         if (!intersectionWithContainerFiles.isEmpty()) {
262           int totalSize = fileSet.size();
263           result = processPsiFileRoots(intersectionWithContainerFiles, totalSize, 0, progress, localProcessor);
264
265           if (result) {
266             fileSet.removeAll(intersectionWithContainerFiles);
267             if (!fileSet.isEmpty()) {
268               result = processPsiFileRoots(new ArrayList<>(fileSet), totalSize, intersectionWithContainerFiles.size(), progress, localProcessor);
269             }
270           }
271           return result;
272         }
273       }
274       result = fileSet.isEmpty() || processPsiFileRoots(new ArrayList<>(fileSet), fileSet.size(), 0, progress, localProcessor);
275     }
276     finally {
277       progress.popState();
278     }
279     return result;
280   }
281
282   /**
283    * @param files to scan for references in this pass.
284    * @param totalSize the number of files to scan in both passes. Can be different from {@code files.size()} in case of
285    *                  two-pass scan, where we first scan files containing container name and then all the rest files.
286    * @param alreadyProcessedFiles the number of files scanned in previous pass.
287    * @return true if completed
288    */
289   private boolean processPsiFileRoots(@NotNull List<? extends VirtualFile> files,
290                                       final int totalSize,
291                                       int alreadyProcessedFiles,
292                                       @NotNull final ProgressIndicator progress,
293                                       @NotNull final Processor<? super PsiFile> localProcessor) {
294     myManager.startBatchFilesProcessingMode();
295     try {
296       final AtomicInteger counter = new AtomicInteger(alreadyProcessedFiles);
297       final AtomicBoolean stopped = new AtomicBoolean(false);
298
299       return processFilesConcurrentlyDespiteWriteActions(myManager.getProject(), files, progress, stopped, vfile -> {
300         TooManyUsagesStatus.getFrom(progress).pauseProcessingIfTooManyUsages();
301         try {
302           processVirtualFile(vfile, stopped, localProcessor);
303         }
304         catch (ProcessCanceledException | IndexNotReadyException e) {
305           throw e;
306         }
307         catch (Throwable e) {
308           LOG.error("Error during processing of: " + vfile.getName(), e);
309           throw e;
310         }
311         if (progress.isRunning()) {
312           double fraction = (double)counter.incrementAndGet() / totalSize;
313           progress.setFraction(fraction);
314         }
315         return !stopped.get();
316       });
317     }
318     finally {
319       myManager.finishBatchFilesProcessingMode();
320     }
321   }
322
323   // Tries to run {@code localProcessor} for each file in {@code files} concurrently on ForkJoinPool.
324   // When encounters write action request, stops all threads, waits for write action to finish and re-starts all threads again.
325   // {@code localProcessor} must be as idempotent as possible.
326   public static boolean processFilesConcurrentlyDespiteWriteActions(@NotNull Project project,
327                                                                     @NotNull List<? extends VirtualFile> files,
328                                                                     @NotNull final ProgressIndicator progress,
329                                                                     @NotNull AtomicBoolean stopped,
330                                                                     @NotNull final Processor<? super VirtualFile> localProcessor) {
331     ApplicationEx app = (ApplicationEx)ApplicationManager.getApplication();
332     if (!app.isDispatchThread()) {
333       CoreProgressManager.assertUnderProgress(progress);
334     }
335
336     while (true) {
337       ProgressManager.checkCanceled();
338       List<VirtualFile> failedList = new SmartList<>();
339       List<VirtualFile> failedFiles = Collections.synchronizedList(failedList);
340       boolean completed;
341       if (app.isWriteAccessAllowed() || app.isReadAccessAllowed() && app.isWriteActionPending()) {
342         // no point in processing in separate threads - they are doomed to fail to obtain read action anyway
343         // do not wrap in impatient reader because every read action inside would trigger AU.CRRAE
344         completed = ContainerUtil.process(files, localProcessor);
345       }
346       else if (app.isWriteActionPending()) {
347         completed = true;
348         // we don't have read action now so wait for write action to complete
349         failedFiles.addAll(files);
350       }
351       else {
352         final Processor<VirtualFile> processor = vfile -> {
353           ProgressManager.checkCanceled();
354           if (failedFiles.isEmpty()) {
355             try {
356               // wrap in unconditional impatient reader to bail early at write action start,
357               // regardless of whether was called from highlighting (already impatient-wrapped) or Find Usages action
358               app.executeByImpatientReader(() -> {
359                 if (!localProcessor.process(vfile)) {
360                   stopped.set(true);
361                 }
362               });
363             }
364             catch (ApplicationUtil.CannotRunReadActionException action) {
365               failedFiles.add(vfile);
366             }
367           }
368           else {
369             // 1st: optimisation to avoid unnecessary processing if it's doomed to fail because some other task has failed already,
370             // and 2nd: bail out of fork/join task as soon as possible
371             failedFiles.add(vfile);
372           }
373           return !stopped.get();
374         };
375         // try to run parallel read actions but fail as soon as possible
376         completed = JobLauncher.getInstance().invokeConcurrentlyUnderProgress(files, progress, processor);
377       }
378       if (!completed) {
379         return false;
380       }
381       if (failedFiles.isEmpty()) {
382         break;
383       }
384       // we failed to run read action in job launcher thread
385       // run read action in our thread instead to wait for a write action to complete and resume parallel processing
386       DumbService.getInstance(project).runReadActionInSmartMode(EmptyRunnable.getInstance());
387       files = failedList;
388     }
389     return true;
390   }
391
392   private void processVirtualFile(@NotNull final VirtualFile vfile,
393                                   @NotNull final AtomicBoolean stopped, @NotNull final Processor<? super PsiFile> localProcessor) throws ApplicationUtil.CannotRunReadActionException {
394     final PsiFile file = ApplicationUtil.tryRunReadAction(() -> vfile.isValid() ? myManager.findFile(vfile) : null);
395     if (file != null && !(file instanceof PsiBinaryFile)) {
396       ApplicationUtil.tryRunReadAction(() -> {
397         final Project project = myManager.getProject();
398         if (project.isDisposed()) throw new ProcessCanceledException();
399         if (DumbService.isDumb(project)) throw ApplicationUtil.CannotRunReadActionException.create();
400
401         List<PsiFile> psiRoots = file.getViewProvider().getAllFiles();
402         Set<PsiFile> processed = new THashSet<>(psiRoots.size() * 2, (float)0.5);
403         for (final PsiFile psiRoot : psiRoots) {
404           ProgressManager.checkCanceled();
405           assert psiRoot != null : "One of the roots of file " + file + " is null. All roots: " + psiRoots + "; ViewProvider: " +
406                                    file.getViewProvider() + "; Virtual file: " + file.getViewProvider().getVirtualFile();
407           if (!processed.add(psiRoot)) continue;
408           if (!psiRoot.isValid()) {
409             continue;
410           }
411
412           if (!localProcessor.process(psiRoot)) {
413             stopped.set(true);
414             break;
415           }
416         }
417       });
418     }
419   }
420
421   private void getFilesWithText(@NotNull GlobalSearchScope scope,
422                                 final short searchContext,
423                                 final boolean caseSensitively,
424                                 @NotNull String text,
425                                 @NotNull Collection<? super VirtualFile> result) {
426     myManager.startBatchFilesProcessingMode();
427     try {
428       Processor<? super VirtualFile> processor = Processors.cancelableCollectProcessor(result);
429       boolean success = processFilesWithText(scope, searchContext, caseSensitively, text, processor);
430       // success == false means exception in index
431     }
432     finally {
433       myManager.finishBatchFilesProcessingMode();
434     }
435   }
436
437   public boolean processFilesWithText(@NotNull final GlobalSearchScope scope,
438                                       final short searchContext,
439                                       final boolean caseSensitively,
440                                       @NotNull String text,
441                                       @NotNull final Processor<? super VirtualFile> processor) {
442     List<IdIndexEntry> entries = getWordEntries(text, caseSensitively);
443     if (entries.isEmpty()) return true;
444
445     Condition<Integer> contextMatches = integer -> (integer.intValue() & searchContext) != 0;
446     return processFilesContainingAllKeys(myManager.getProject(), scope, contextMatches, entries, processor);
447   }
448
449   @Override
450   @NotNull
451   public PsiFile[] findFilesWithPlainTextWords(@NotNull String word) {
452     return CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(word, UsageSearchContext.IN_PLAIN_TEXT,
453                                                                                      GlobalSearchScope.projectScope(myManager.getProject()),
454                                                                                      true);
455   }
456
457
458   @Override
459   public boolean processUsagesInNonJavaFiles(@NotNull String qName,
460                                              @NotNull PsiNonJavaFileReferenceProcessor processor,
461                                              @NotNull GlobalSearchScope searchScope) {
462     return processUsagesInNonJavaFiles(null, qName, processor, searchScope);
463   }
464
465   @Override
466   public boolean processUsagesInNonJavaFiles(@Nullable final PsiElement originalElement,
467                                              @NotNull String qName,
468                                              @NotNull final PsiNonJavaFileReferenceProcessor processor,
469                                              @NotNull final GlobalSearchScope initialScope) {
470     if (qName.isEmpty()) {
471       throw new IllegalArgumentException("Cannot search for elements with empty text. Element: "+originalElement+ "; "+(originalElement == null ? null : originalElement.getClass()));
472     }
473     final ProgressIndicator progress = getOrCreateIndicator();
474
475     int dotIndex = qName.lastIndexOf('.');
476     int dollarIndex = qName.lastIndexOf('$');
477     int maxIndex = Math.max(dotIndex, dollarIndex);
478     final String wordToSearch = maxIndex >= 0 ? qName.substring(maxIndex + 1) : qName;
479     final GlobalSearchScope theSearchScope = ReadAction.compute(() -> {
480       if (originalElement != null && myManager.isInProject(originalElement) && initialScope.isSearchInLibraries()) {
481         return initialScope.intersectWith(GlobalSearchScope.projectScope(myManager.getProject()));
482       }
483       return initialScope;
484     });
485     PsiFile[] files = myDumbService.runReadActionInSmartMode(() -> CacheManager.SERVICE.getInstance(myManager.getProject()).getFilesWithWord(wordToSearch, UsageSearchContext.IN_PLAIN_TEXT, theSearchScope, true));
486
487     final StringSearcher searcher = new StringSearcher(qName, true, true, false);
488
489     progress.pushState();
490     final Ref<Boolean> stopped = Ref.create(Boolean.FALSE);
491     try {
492       progress.setText(PsiBundle.message("psi.search.in.non.java.files.progress"));
493
494       final SearchScope useScope = originalElement == null ? null : myDumbService.runReadActionInSmartMode(() -> getUseScope(originalElement));
495
496       final int patternLength = qName.length();
497       for (int i = 0; i < files.length; i++) {
498         ProgressManager.checkCanceled();
499         final PsiFile psiFile = files[i];
500         if (psiFile instanceof PsiBinaryFile) continue;
501
502         final CharSequence text = ReadAction.compute(() -> psiFile.getViewProvider().getContents());
503
504         LowLevelSearchUtil.processTextOccurrences(text, 0, text.length(), searcher, progress, index -> {
505           boolean isReferenceOK = myDumbService.runReadActionInSmartMode(() -> {
506             PsiReference referenceAt = psiFile.findReferenceAt(index);
507             return referenceAt == null || useScope == null || !PsiSearchScopeUtil.isInScope(useScope.intersectWith(initialScope), psiFile);
508           });
509           if (isReferenceOK && !processor.process(psiFile, index, index + patternLength)) {
510             stopped.set(Boolean.TRUE);
511             return false;
512           }
513
514           return true;
515         });
516         if (stopped.get()) break;
517         progress.setFraction((double)(i + 1) / files.length);
518       }
519     }
520     finally {
521       progress.popState();
522     }
523
524     return !stopped.get();
525   }
526
527   @Override
528   public boolean processAllFilesWithWord(@NotNull String word,
529                                          @NotNull GlobalSearchScope scope,
530                                          @NotNull Processor<PsiFile> processor,
531                                          final boolean caseSensitively) {
532     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_CODE, scope, caseSensitively);
533   }
534
535   @Override
536   public boolean processAllFilesWithWordInText(@NotNull final String word,
537                                                @NotNull final GlobalSearchScope scope,
538                                                @NotNull final Processor<PsiFile> processor,
539                                                final boolean caseSensitively) {
540     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_PLAIN_TEXT, scope, caseSensitively);
541   }
542
543   @Override
544   public boolean processAllFilesWithWordInComments(@NotNull String word,
545                                                    @NotNull GlobalSearchScope scope,
546                                                    @NotNull Processor<PsiFile> processor) {
547     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_COMMENTS, scope, true);
548   }
549
550   @Override
551   public boolean processAllFilesWithWordInLiterals(@NotNull String word,
552                                                    @NotNull GlobalSearchScope scope,
553                                                    @NotNull Processor<PsiFile> processor) {
554     return CacheManager.SERVICE.getInstance(myManager.getProject()).processFilesWithWord(processor, word, UsageSearchContext.IN_STRINGS, scope, true);
555   }
556
557   private static class RequestWithProcessor {
558     @NotNull private final PsiSearchRequest request;
559     @NotNull private Processor<? super PsiReference> refProcessor;
560
561     private RequestWithProcessor(@NotNull PsiSearchRequest request, @NotNull Processor<? super PsiReference> processor) {
562       this.request = request;
563       refProcessor = processor;
564     }
565
566     private boolean uniteWith(@NotNull final RequestWithProcessor another) {
567       if (request.equals(another.request)) {
568         final Processor<? super PsiReference> myProcessor = refProcessor;
569         if (myProcessor != another.refProcessor) {
570           refProcessor = psiReference -> myProcessor.process(psiReference) && another.refProcessor.process(psiReference);
571         }
572         return true;
573       }
574       return false;
575     }
576
577     @Override
578     public String toString() {
579       return request.toString();
580     }
581   }
582
583   @Override
584   public boolean processRequests(@NotNull SearchRequestCollector collector, @NotNull Processor<? super PsiReference> processor) {
585     final Map<SearchRequestCollector, Processor<? super PsiReference>> collectors = new HashMap<>();
586     collectors.put(collector, processor);
587
588     ProgressIndicator progress = getOrCreateIndicator();
589     if (appendCollectorsFromQueryRequests(progress, collectors) == QueryRequestsRunResult.STOPPED) {
590       return false;
591     }
592     do {
593       final Map<Set<IdIndexEntry>, Collection<RequestWithProcessor>> globals = new HashMap<>();
594       final List<Computable<Boolean>> customs = new ArrayList<>();
595       final Set<RequestWithProcessor> locals = new LinkedHashSet<>();
596       Map<RequestWithProcessor, Processor<? super PsiElement>> localProcessors = new THashMap<>();
597       distributePrimitives(collectors, locals, globals, customs, localProcessors, progress);
598       if (!processGlobalRequestsOptimized(globals, progress, localProcessors)) {
599         return false;
600       }
601       for (RequestWithProcessor local : locals) {
602         progress.checkCanceled();
603         if (!processSingleRequest(local.request, local.refProcessor)) {
604           return false;
605         }
606       }
607       for (Computable<Boolean> custom : customs) {
608         progress.checkCanceled();
609         if (!custom.compute()) {
610           return false;
611         }
612       }
613       final QueryRequestsRunResult result = appendCollectorsFromQueryRequests(progress, collectors);
614       if (result == QueryRequestsRunResult.STOPPED) {
615         return false;
616       }
617       else if (result == QueryRequestsRunResult.UNCHANGED) {
618         return true;
619       }
620     }
621     while (true);
622   }
623
624   @NotNull
625   @Override
626   public AsyncFuture<Boolean> processRequestsAsync(@NotNull SearchRequestCollector collector, @NotNull Processor<? super PsiReference> processor) {
627     return AsyncUtil.wrapBoolean(processRequests(collector, processor));
628   }
629
630   private enum QueryRequestsRunResult {
631     STOPPED,
632     UNCHANGED,
633     CHANGED,
634   }
635
636   @NotNull
637   private static QueryRequestsRunResult appendCollectorsFromQueryRequests(@NotNull ProgressIndicator progress,
638                                                                           @NotNull Map<SearchRequestCollector, Processor<? super PsiReference>> collectors) {
639     boolean changed = false;
640     Deque<SearchRequestCollector> queue = new LinkedList<>(collectors.keySet());
641     while (!queue.isEmpty()) {
642       progress.checkCanceled();
643       final SearchRequestCollector each = queue.removeFirst();
644       for (QuerySearchRequest request : each.takeQueryRequests()) {
645         progress.checkCanceled();
646         if (!request.runQuery()) {
647           return QueryRequestsRunResult.STOPPED;
648         }
649         assert !collectors.containsKey(request.collector) || collectors.get(request.collector) == request.processor;
650         collectors.put(request.collector, request.processor);
651         queue.addLast(request.collector);
652         changed = true;
653       }
654     }
655     return changed ? QueryRequestsRunResult.CHANGED : QueryRequestsRunResult.UNCHANGED;
656   }
657
658   private boolean processGlobalRequestsOptimized(@NotNull Map<Set<IdIndexEntry>, Collection<RequestWithProcessor>> singles,
659                                                  @NotNull ProgressIndicator progress,
660                                                  @NotNull final Map<RequestWithProcessor, Processor<? super PsiElement>> localProcessors) {
661     if (singles.isEmpty()) {
662       return true;
663     }
664
665     if (singles.size() == 1) {
666       final Collection<? extends RequestWithProcessor> requests = singles.values().iterator().next();
667       if (requests.size() == 1) {
668         final RequestWithProcessor theOnly = requests.iterator().next();
669         return processSingleRequest(theOnly.request, theOnly.refProcessor);
670       }
671     }
672
673     progress.pushState();
674     progress.setText(PsiBundle.message("psi.scanning.files.progress"));
675     boolean result;
676
677     try {
678       // intersectionCandidateFiles holds files containing words from all requests in `singles` and words in corresponding container names
679       final Map<VirtualFile, Collection<RequestWithProcessor>> intersectionCandidateFiles = new HashMap<>();
680       // restCandidateFiles holds files containing words from all requests in `singles` but EXCLUDING words in corresponding container names
681       final Map<VirtualFile, Collection<RequestWithProcessor>> restCandidateFiles = new HashMap<>();
682       collectFiles(singles, intersectionCandidateFiles, restCandidateFiles);
683
684       if (intersectionCandidateFiles.isEmpty() && restCandidateFiles.isEmpty()) {
685         return true;
686       }
687
688       final Set<String> allWords = new TreeSet<>();
689       for (RequestWithProcessor singleRequest : localProcessors.keySet()) {
690         ProgressManager.checkCanceled();
691         allWords.add(singleRequest.request.word);
692       }
693       progress.setText(PsiBundle.message("psi.search.for.word.progress", getPresentableWordsDescription(allWords)));
694
695       if (intersectionCandidateFiles.isEmpty()) {
696         result = processCandidates(localProcessors, restCandidateFiles, progress, restCandidateFiles.size(), 0);
697       }
698       else {
699         int totalSize = restCandidateFiles.size() + intersectionCandidateFiles.size();
700         result = processCandidates(localProcessors, intersectionCandidateFiles, progress, totalSize, 0);
701         if (result) {
702           result = processCandidates(localProcessors, restCandidateFiles, progress, totalSize, intersectionCandidateFiles.size());
703         }
704       }
705     }
706     finally {
707       progress.popState();
708     }
709
710     return result;
711   }
712
713   private <X> boolean processCandidates(@NotNull final Map<X, Processor<? super PsiElement>> localProcessors,
714                                         @NotNull final Map<VirtualFile, Collection<X>> candidateFiles,
715                                         @NotNull ProgressIndicator progress,
716                                         int totalSize,
717                                         int alreadyProcessedFiles) {
718     List<VirtualFile> files = new ArrayList<>(candidateFiles.keySet());
719
720     return processPsiFileRoots(files, totalSize, alreadyProcessedFiles, progress, psiRoot -> {
721       final VirtualFile vfile = psiRoot.getVirtualFile();
722       for (final X singleRequest : candidateFiles.get(vfile)) {
723         ProgressManager.checkCanceled();
724         Processor<? super PsiElement> localProcessor = localProcessors.get(singleRequest);
725         if (!localProcessor.process(psiRoot)) {
726           return false;
727         }
728       }
729       return true;
730     });
731   }
732
733   @NotNull
734   private static String getPresentableWordsDescription(@NotNull Set<String> allWords) {
735     final StringBuilder result = new StringBuilder();
736     for (String string : allWords) {
737       ProgressManager.checkCanceled();
738         if (string != null && !string.isEmpty()) {
739         if (result.length() > 50) {
740           result.append("...");
741           break;
742         }
743         if (result.length() != 0) result.append(", ");
744         result.append(string);
745       }
746     }
747     return result.toString();
748   }
749
750   @NotNull
751   private static BulkOccurrenceProcessor adaptProcessor(@NotNull PsiSearchRequest singleRequest,
752                                                        @NotNull Processor<? super PsiReference> consumer) {
753     final SearchScope searchScope = singleRequest.searchScope;
754     final boolean ignoreInjectedPsi = searchScope instanceof LocalSearchScope && ((LocalSearchScope)searchScope).isIgnoreInjectedPsi();
755     final RequestResultProcessor wrapped = singleRequest.processor;
756     return new BulkOccurrenceProcessor() {
757       @Override
758       public boolean execute(@NotNull PsiElement scope, @NotNull int[] offsetsInScope, @NotNull StringSearcher searcher) {
759         try {
760           ProgressManager.checkCanceled();
761           if (wrapped instanceof RequestResultProcessor.BulkResultProcessor) {
762             return ((RequestResultProcessor.BulkResultProcessor)wrapped).processTextOccurrences(scope, offsetsInScope, consumer);
763           }
764
765           return LowLevelSearchUtil.processElementsAtOffsets(scope, searcher, !ignoreInjectedPsi,
766                                                              getOrCreateIndicator(), offsetsInScope,
767                                                              (element, offsetInElement) -> {
768             if (ignoreInjectedPsi && element instanceof PsiLanguageInjectionHost) return true;
769             return wrapped.processTextOccurrence(element, offsetInElement, consumer);
770           });
771         }
772         catch (ProcessCanceledException e) {
773           throw e;
774         }
775         catch (Exception | Error e) {
776           PsiFile file = scope.getContainingFile();
777           LOG.error("Error during processing of: " + (file != null ? file.getName() : scope), e);
778           return true;
779         }
780       }
781
782       @Override
783       public String toString() {
784         return consumer.toString();
785       }
786     };
787   }
788
789   private void collectFiles(@NotNull final Map<Set<IdIndexEntry>, Collection<RequestWithProcessor>> singles,
790                             @NotNull final Map<VirtualFile, Collection<RequestWithProcessor>> intersectionResult,
791                             @NotNull final Map<VirtualFile, Collection<RequestWithProcessor>> restResult) {
792     for (Map.Entry<Set<IdIndexEntry>, Collection<RequestWithProcessor>> entry : singles.entrySet()) {
793       ProgressManager.checkCanceled();
794       final Set<IdIndexEntry> keys = entry.getKey();
795       if (keys.isEmpty()) {
796         continue;
797       }
798
799       final Collection<RequestWithProcessor> processors = entry.getValue();
800       final GlobalSearchScope commonScope = uniteScopes(processors);
801       final Set<VirtualFile> intersectionWithContainerNameFiles = intersectionWithContainerNameFiles(commonScope, processors, keys);
802
803       List<VirtualFile> result = new ArrayList<>();
804       Processor<VirtualFile> processor = Processors.cancelableCollectProcessor(result);
805       processFilesContainingAllKeys(myManager.getProject(), commonScope, null, keys, processor);
806       for (final VirtualFile file : result) {
807         ProgressManager.checkCanceled();
808         for (final IdIndexEntry indexEntry : keys) {
809           ProgressManager.checkCanceled();
810           myDumbService.runReadActionInSmartMode(
811             () -> FileBasedIndex.getInstance().processValues(IdIndex.NAME, indexEntry, file, (file1, value) -> {
812               int mask = value.intValue();
813               for (RequestWithProcessor single : processors) {
814                 ProgressManager.checkCanceled();
815                 final PsiSearchRequest request = single.request;
816                 if ((mask & request.searchContext) != 0 && request.searchScope.contains(file1)) {
817                   Map<VirtualFile, Collection<RequestWithProcessor>> result1 =
818                     intersectionWithContainerNameFiles == null || !intersectionWithContainerNameFiles.contains(file1) ? restResult : intersectionResult;
819                   result1.computeIfAbsent(file1, __ -> new SmartList<>()).add(single);
820                 }
821               }
822               return true;
823             }, commonScope));
824         }
825       }
826     }
827   }
828
829   @Nullable("null means we did not find common container files")
830   private Set<VirtualFile> intersectionWithContainerNameFiles(@NotNull GlobalSearchScope commonScope,
831                                                               @NotNull Collection<? extends RequestWithProcessor> data,
832                                                               @NotNull Set<IdIndexEntry> keys) {
833     String commonName = null;
834     short searchContext = 0;
835     boolean caseSensitive = true;
836     for (RequestWithProcessor r : data) {
837       ProgressManager.checkCanceled();
838       String containerName = r.request.containerName;
839       if (containerName != null) {
840         if (commonName == null) {
841           commonName = containerName;
842           searchContext = r.request.searchContext;
843           caseSensitive = r.request.caseSensitive;
844         }
845         else if (commonName.equals(containerName)) {
846           searchContext |= r.request.searchContext;
847           caseSensitive &= r.request.caseSensitive;
848         }
849         else {
850           return null;
851         }
852       }
853     }
854     if (commonName == null) return null;
855
856     List<IdIndexEntry> entries = getWordEntries(commonName, caseSensitive);
857     if (entries.isEmpty()) return null;
858     entries.addAll(keys); // should find words from both text and container names
859
860     final short finalSearchContext = searchContext;
861     Condition<Integer> contextMatches = context -> (context.intValue() & finalSearchContext) != 0;
862     Set<VirtualFile> containerFiles = new THashSet<>();
863     Processor<VirtualFile> processor = Processors.cancelableCollectProcessor(containerFiles);
864     processFilesContainingAllKeys(myManager.getProject(), commonScope, contextMatches, entries, processor);
865
866     return containerFiles;
867   }
868
869   @NotNull
870   private static GlobalSearchScope uniteScopes(@NotNull Collection<RequestWithProcessor> requests) {
871     Set<GlobalSearchScope> scopes = ContainerUtil.map2LinkedSet(requests, r -> (GlobalSearchScope)r.request.searchScope);
872     return GlobalSearchScope.union(scopes.toArray(GlobalSearchScope.EMPTY_ARRAY));
873   }
874
875   private static void distributePrimitives(@NotNull Map<SearchRequestCollector, Processor<? super PsiReference>> collectors,
876                                            @NotNull Set<RequestWithProcessor> locals,
877                                            @NotNull Map<Set<IdIndexEntry>, Collection<RequestWithProcessor>> globals,
878                                            @NotNull List<? super Computable<Boolean>> customs,
879                                            @NotNull Map<RequestWithProcessor, Processor<? super PsiElement>> localProcessors,
880                                            @NotNull ProgressIndicator progress) {
881     for (final Map.Entry<SearchRequestCollector, Processor<? super PsiReference>> entry : collectors.entrySet()) {
882       ProgressManager.checkCanceled();
883       final Processor<? super PsiReference> processor = entry.getValue();
884       SearchRequestCollector collector = entry.getKey();
885       for (final PsiSearchRequest primitive : collector.takeSearchRequests()) {
886         ProgressManager.checkCanceled();
887         final SearchScope scope = primitive.searchScope;
888         if (scope instanceof LocalSearchScope) {
889           registerRequest(locals, primitive, processor);
890         }
891         else {
892           Set<IdIndexEntry> key = new HashSet<>(getWordEntries(primitive.word, primitive.caseSensitive));
893           registerRequest(globals.computeIfAbsent(key, __ -> new SmartList<>()), primitive, processor);
894         }
895       }
896       for (final Processor<Processor<? super PsiReference>> customAction : collector.takeCustomSearchActions()) {
897         ProgressManager.checkCanceled();
898         customs.add((Computable<Boolean>)() -> customAction.process(processor));
899       }
900     }
901
902     for (Map.Entry<Set<IdIndexEntry>, Collection<RequestWithProcessor>> entry : globals.entrySet()) {
903       ProgressManager.checkCanceled();
904       for (RequestWithProcessor singleRequest : entry.getValue()) {
905         ProgressManager.checkCanceled();
906         PsiSearchRequest primitive = singleRequest.request;
907         StringSearcher searcher = new StringSearcher(primitive.word, primitive.caseSensitive, true, false);
908         BulkOccurrenceProcessor adapted = adaptProcessor(primitive, singleRequest.refProcessor);
909
910         Processor<PsiElement> localProcessor = localProcessor(progress, searcher, adapted);
911
912         assert !localProcessors.containsKey(singleRequest) || localProcessors.get(singleRequest) == localProcessor;
913         localProcessors.put(singleRequest, localProcessor);
914       }
915     }
916   }
917
918   private static void registerRequest(@NotNull Collection<RequestWithProcessor> collection,
919                                       @NotNull PsiSearchRequest primitive,
920                                       @NotNull Processor<? super PsiReference> processor) {
921     RequestWithProcessor singleRequest = new RequestWithProcessor(primitive, processor);
922
923     for (RequestWithProcessor existing : collection) {
924       ProgressManager.checkCanceled();
925       if (existing.uniteWith(singleRequest)) {
926         return;
927       }
928     }
929     collection.add(singleRequest);
930   }
931
932   private boolean processSingleRequest(@NotNull PsiSearchRequest single, @NotNull Processor<? super PsiReference> consumer) {
933     final EnumSet<Options> options = EnumSet.of(Options.PROCESS_ONLY_JAVA_IDENTIFIERS_IF_POSSIBLE);
934     if (single.caseSensitive) options.add(Options.CASE_SENSITIVE_SEARCH);
935     if (shouldProcessInjectedPsi(single.searchScope)) options.add(Options.PROCESS_INJECTED_PSI);
936
937     return bulkProcessElementsWithWord(single.searchScope, single.word, single.searchContext, options, single.containerName,
938                                        adaptProcessor(single, consumer)
939     );
940   }
941
942   @NotNull
943   @Override
944   public SearchCostResult isCheapEnoughToSearch(@NotNull String name,
945                                                 @NotNull final GlobalSearchScope scope,
946                                                 @Nullable final PsiFile fileToIgnoreOccurrencesIn,
947                                                 @Nullable final ProgressIndicator progress) {
948     if (!ReadAction.compute(() -> scope.getUnloadedModulesBelongingToScope().isEmpty())) {
949       return SearchCostResult.TOO_MANY_OCCURRENCES;
950     }
951
952     final AtomicInteger filesCount = new AtomicInteger();
953     final AtomicLong filesSizeToProcess = new AtomicLong();
954
955     final Processor<VirtualFile> processor = new Processor<VirtualFile>() {
956       private final VirtualFile virtualFileToIgnoreOccurrencesIn =
957         fileToIgnoreOccurrencesIn == null ? null : fileToIgnoreOccurrencesIn.getVirtualFile();
958       private final int maxFilesToProcess = Registry.intValue("ide.unused.symbol.calculation.maxFilesToSearchUsagesIn", 10);
959       private final int maxFilesSizeToProcess = Registry.intValue("ide.unused.symbol.calculation.maxFilesSizeToSearchUsagesIn", 524288);
960
961       @Override
962       public boolean process(VirtualFile file) {
963         ProgressManager.checkCanceled();
964         if (Comparing.equal(file, virtualFileToIgnoreOccurrencesIn)) return true;
965         int currentFilesCount = filesCount.incrementAndGet();
966         long accumulatedFileSizeToProcess = filesSizeToProcess.addAndGet(file.isDirectory() ? 0 : file.getLength());
967         return currentFilesCount < maxFilesToProcess && accumulatedFileSizeToProcess < maxFilesSizeToProcess;
968       }
969     };
970     List<IdIndexEntry> keys = getWordEntries(name, true);
971     boolean cheap = keys.isEmpty() || processFilesContainingAllKeys(myManager.getProject(), scope, null, keys, processor);
972
973     if (!cheap) {
974       return SearchCostResult.TOO_MANY_OCCURRENCES;
975     }
976
977     return filesCount.get() == 0 ? SearchCostResult.ZERO_OCCURRENCES : SearchCostResult.FEW_OCCURRENCES;
978   }
979
980   private static boolean processFilesContainingAllKeys(@NotNull Project project,
981                                                        @NotNull final GlobalSearchScope scope,
982                                                        @Nullable final Condition<? super Integer> checker,
983                                                        @NotNull final Collection<? extends IdIndexEntry> keys,
984                                                        @NotNull final Processor<? super VirtualFile> processor) {
985     final FileIndexFacade index = FileIndexFacade.getInstance(project);
986     return DumbService.getInstance(project).runReadActionInSmartMode(
987       () -> FileBasedIndex.getInstance().processFilesContainingAllKeys(IdIndex.NAME, keys, scope, checker,
988                                                                         file -> !index.shouldBeFound(scope, file) || processor.process(file)));
989   }
990
991   @NotNull
992   private static List<IdIndexEntry> getWordEntries(@NotNull String name, final boolean caseSensitively) {
993     List<String> words = StringUtil.getWordsInStringLongestFirst(name);
994     if (words.isEmpty()) {
995       String trimmed = name.trim();
996       if (StringUtil.isNotEmpty(trimmed)) {
997         words = Collections.singletonList(trimmed);
998       }
999     }
1000     if (words.isEmpty()) return Collections.emptyList();
1001     return ContainerUtil.map2List(words, word -> new IdIndexEntry(word, caseSensitively));
1002   }
1003
1004   public static boolean processTextOccurrences(@NotNull final PsiElement element,
1005                                                @NotNull String stringToSearch,
1006                                                @NotNull GlobalSearchScope searchScope,
1007                                                @NotNull final UsageInfoFactory factory,
1008                                                @NotNull final Processor<? super UsageInfo> processor) {
1009     PsiSearchHelper helper = ReadAction.compute(() -> PsiSearchHelper.getInstance(element.getProject()));
1010
1011     return helper.processUsagesInNonJavaFiles(element, stringToSearch, (psiFile, startOffset, endOffset) -> {
1012       try {
1013         UsageInfo usageInfo = ReadAction.compute(() -> factory.createUsageInfo(psiFile, startOffset, endOffset));
1014         return usageInfo == null || processor.process(usageInfo);
1015       }
1016       catch (ProcessCanceledException e) {
1017         throw e;
1018       }
1019       catch (Exception e) {
1020         LOG.error(e);
1021         return true;
1022       }
1023     }, searchScope);
1024   }
1025 }