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