fix "IDEA-221944 Deadlock on opening second project" and support preloading for proje...
[idea/community.git] / java / java-impl / src / com / intellij / psi / refResolve / RefResolveServiceImpl.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.refResolve;
3
4 import com.intellij.ide.PowerSaveMode;
5 import com.intellij.openapi.Disposable;
6 import com.intellij.openapi.application.ApplicationListener;
7 import com.intellij.openapi.application.ApplicationManager;
8 import com.intellij.openapi.application.PathManager;
9 import com.intellij.openapi.application.ex.ApplicationManagerEx;
10 import com.intellij.openapi.application.ex.ApplicationUtil;
11 import com.intellij.openapi.diagnostic.Logger;
12 import com.intellij.openapi.fileTypes.FileTypeRegistry;
13 import com.intellij.openapi.fileTypes.StdFileTypes;
14 import com.intellij.openapi.module.Module;
15 import com.intellij.openapi.progress.ProcessCanceledException;
16 import com.intellij.openapi.progress.ProgressIndicator;
17 import com.intellij.openapi.progress.ProgressManager;
18 import com.intellij.openapi.progress.Task;
19 import com.intellij.openapi.progress.impl.BackgroundableProcessIndicator;
20 import com.intellij.openapi.progress.impl.ProgressManagerImpl;
21 import com.intellij.openapi.progress.util.ProgressIndicatorBase;
22 import com.intellij.openapi.progress.util.ProgressIndicatorUtils;
23 import com.intellij.openapi.project.*;
24 import com.intellij.openapi.roots.ProjectFileIndex;
25 import com.intellij.openapi.startup.StartupManager;
26 import com.intellij.openapi.util.Disposer;
27 import com.intellij.openapi.util.EmptyRunnable;
28 import com.intellij.openapi.util.io.FileUtil;
29 import com.intellij.openapi.util.text.StringUtil;
30 import com.intellij.openapi.vfs.*;
31 import com.intellij.openapi.vfs.newvfs.BulkFileListener;
32 import com.intellij.openapi.vfs.newvfs.NewVirtualFile;
33 import com.intellij.openapi.vfs.newvfs.events.VFileEvent;
34 import com.intellij.openapi.vfs.newvfs.persistent.FSRecords;
35 import com.intellij.openapi.vfs.newvfs.persistent.PersistentFS;
36 import com.intellij.psi.*;
37 import com.intellij.psi.search.GlobalSearchScope;
38 import com.intellij.psi.util.PsiUtilCore;
39 import com.intellij.util.ArrayUtil;
40 import com.intellij.util.ExceptionUtil;
41 import com.intellij.util.Function;
42 import com.intellij.util.Processor;
43 import com.intellij.util.containers.ConcurrentBitSet;
44 import com.intellij.util.containers.ContainerUtil;
45 import com.intellij.util.containers.IntObjectMap;
46 import com.intellij.util.io.storage.HeavyProcessLatch;
47 import com.intellij.util.messages.MessageBus;
48 import com.intellij.util.messages.MessageBusConnection;
49 import gnu.trove.*;
50 import org.jetbrains.annotations.NotNull;
51 import org.jetbrains.annotations.Nullable;
52 import org.jetbrains.jps.model.java.JavaSourceRootType;
53
54 import java.io.File;
55 import java.io.FileWriter;
56 import java.io.IOException;
57 import java.text.DateFormat;
58 import java.util.*;
59 import java.util.concurrent.Callable;
60 import java.util.concurrent.Future;
61 import java.util.concurrent.FutureTask;
62 import java.util.concurrent.atomic.AtomicInteger;
63 import java.util.concurrent.atomic.AtomicLong;
64
65 public final class RefResolveServiceImpl extends RefResolveService implements Runnable, Disposable {
66   private static final Logger LOG = Logger.getInstance(RefResolveServiceImpl.class);
67
68   private final AtomicInteger fileCount = new AtomicInteger();
69   private final AtomicLong bytesSize = new AtomicLong();
70   private final AtomicLong refCount = new AtomicLong();
71   private final PersistentIntList storage;
72   private final Deque<VirtualFile> filesToResolve = new ArrayDeque<>(); // guarded by filesToResolve
73   private final ConcurrentBitSet fileIsInQueue = new ConcurrentBitSet();
74   private final ConcurrentBitSet fileIsResolved;
75   private final Project myProject;
76   private volatile boolean myDisposed;
77   private volatile boolean upToDate;
78   private final AtomicInteger enableVetoes = new AtomicInteger();  // number of disable() calls. To enable the service, there should be at least corresponding number of enable() calls.
79   private final FileWriter log;
80   private final ProjectFileIndex myProjectFileIndex;
81
82   public RefResolveServiceImpl(@NotNull Project project) throws IOException {
83     myProject = project;
84     ((FutureTask)resolveProcess).run();
85     myProjectFileIndex = ProjectFileIndex.getInstance(project);
86     if (ENABLED) {
87       log = new FileWriter(new File(getStorageDirectory(), "log.txt"));
88
89       File dataFile = new File(getStorageDirectory(), "data");
90       fileIsResolved = ConcurrentBitSet.readFrom(new File(getStorageDirectory(), "bitSet"));
91       log("Read resolved file bitset: " + fileIsResolved);
92
93       int maxId = FSRecords.getMaxId();
94       PersistentIntList list = new PersistentIntList(dataFile, dataFile.exists() ? 0 : maxId);
95       if (list.getSize() == maxId) {
96         storage = list;
97       }
98       else {
99         // just to be safe, re-resolve all if VFS files count changes since last restart
100         Disposer.dispose(list);
101         storage = new PersistentIntList(dataFile, maxId);
102         log("VFS maxId changed: was "+list.getSize()+"; now: "+maxId+"; re-resolving everything");
103         fileIsResolved.clear();
104       }
105       Disposer.register(this, storage);
106       if (!ApplicationManager.getApplication().isUnitTestMode()) {
107         StartupManager.getInstance(project).runWhenProjectIsInitialized(() -> {
108           initListeners(project.getMessageBus(), PsiManager.getInstance(project));
109           startThread();
110         });
111       }
112
113       Disposer.register(this, new Disposable() {
114         @Override
115         public void dispose() {
116           try {
117             save();
118             log.close();
119           }
120           catch (IOException e) {
121             LOG.error(e);
122           }
123         }
124       });
125     }
126     else {
127       log = null;
128       fileIsResolved = null;
129       storage = null;
130     }
131   }
132
133   @NotNull
134   private static List<VirtualFile> toVf(@NotNull int[] ids) {
135     List<VirtualFile> res = new ArrayList<>();
136     for (int id : ids) {
137       VirtualFile file = PersistentFS.getInstance().findFileById(id);
138       if (file != null) {
139         res.add(file);
140       }
141     }
142     return res;
143   }
144
145   @NotNull
146   private static String toVfString(@NotNull int[] backIds) {
147     List<VirtualFile> list = toVf(backIds);
148     return toVfString(list);
149   }
150
151   @NotNull
152   private static String toVfString(@NotNull Collection<VirtualFile> list) {
153     List<VirtualFile> sub = ContainerUtil.getFirstItems(new ArrayList<>(list), 100);
154     return list.size() + " files: " + StringUtil.join(sub, file -> file.getName(), ", ") + (list.size() == sub.size() ? "" : "...");
155   }
156
157   private void initListeners(@NotNull MessageBus messageBus, @NotNull PsiManager psiManager) {
158     MessageBusConnection connection = messageBus.connect(this);
159     connection.subscribe(VirtualFileManager.VFS_CHANGES, new BulkFileListener() {
160       @Override
161       public void after(@NotNull List<? extends VFileEvent> events) {
162         fileCount.set(0);
163         List<VirtualFile> files = ContainerUtil.mapNotNull(events, (Function<VFileEvent, VirtualFile>)event -> event.getFile());
164         queue(files, "VFS events " + events.size());
165       }
166     });
167
168     psiManager.addPsiTreeChangeListener(new PsiTreeChangeAdapter() {
169       @Override
170       public void childrenChanged(@NotNull PsiTreeChangeEvent event) {
171         PsiFile file = event.getFile();
172         VirtualFile virtualFile = PsiUtilCore.getVirtualFile(file);
173         if (virtualFile != null) {
174           queue(Collections.singletonList(virtualFile), event);
175         }
176       }
177
178       @Override
179       public void propertyChanged(@NotNull PsiTreeChangeEvent event) {
180         childrenChanged(event);
181       }
182     });
183
184     connection.subscribe(DumbService.DUMB_MODE, new DumbService.DumbModeListener() {
185       @Override
186       public void enteredDumbMode() {
187         disable();
188       }
189
190       @Override
191       public void exitDumbMode() {
192         enable();
193       }
194     });
195
196     connection.subscribe(PowerSaveMode.TOPIC, new PowerSaveMode.Listener() {
197       @Override
198       public void powerSaveStateChanged() {
199         if (PowerSaveMode.isEnabled()) {
200           enable();
201         }
202         else {
203           disable();
204         }
205       }
206     });
207
208     ApplicationManagerEx.getApplicationEx().addApplicationListener(new ApplicationListener() {
209       @Override
210       public void beforeWriteActionStart(@NotNull Object action) {
211         disable();
212       }
213
214       @Override
215       public void writeActionFinished(@NotNull Object action) {
216         enable();
217       }
218
219       @Override
220       public void applicationExiting() {
221         disable();
222       }
223     }, this);
224
225     VirtualFileManager.getInstance().addVirtualFileManagerListener(new VirtualFileManagerListener() {
226       @Override
227       public void beforeRefreshStart(boolean asynchronous) {
228         disable();
229       }
230
231       @Override
232       public void afterRefreshFinish(boolean asynchronous) {
233         enable();
234       }
235     }, this);
236
237     HeavyProcessLatch.INSTANCE.addListener(new HeavyProcessLatch.HeavyProcessListener() {
238       @Override
239       public void processFinished() {
240         wakeUp();
241       }
242     }, this);
243   }
244
245   // return true if file was added to queue
246   private boolean queueIfNeeded(VirtualFile virtualFile, @NotNull Project project) {
247     return toResolve(virtualFile, project) && queueUpdate(virtualFile);
248   }
249
250   private boolean toResolve(VirtualFile virtualFile, @NotNull Project project) {
251     if (virtualFile != null &&
252         virtualFile.isValid() &&
253         project.isInitialized() &&
254         myProjectFileIndex.isInSourceContent(virtualFile) &&
255         isSupportedFileType(virtualFile)) {
256       return true;
257     }
258
259     // else mark it as resolved so we will not have to check it again
260     if (virtualFile instanceof VirtualFileWithId) {
261       int id = getAbsId(virtualFile);
262       fileIsResolved.set(id);
263     }
264
265     return false;
266   }
267
268   public static boolean isSupportedFileType(@NotNull VirtualFile virtualFile) {
269     if (virtualFile.isDirectory()) return true;
270     if (FileTypeRegistry.getInstance().isFileOfType(virtualFile, StdFileTypes.JAVA)) return true;
271     if (FileTypeRegistry.getInstance().isFileOfType(virtualFile, StdFileTypes.XML) && !ProjectUtil.isProjectOrWorkspaceFile(virtualFile)) return true;
272     final String extension = virtualFile.getExtension();
273     if ("groovy".equals(extension) || "kt".equals(extension)) return true;
274     return false;
275   }
276
277   @NotNull
278   private File getStorageDirectory() {
279     String dirName = myProject.getName() + "."+Integer.toHexString(myProject.getPresentableUrl().hashCode());
280     File dir = new File(PathManager.getSystemPath(), "refs/" + dirName);
281     FileUtil.createDirectory(dir);
282     return dir;
283   }
284
285
286   private void log(String m) {
287     //System.out.println(m);
288     logf(m);
289   }
290
291   private void logf(String m) {
292     if (LOG.isDebugEnabled()) {
293       try {
294         log.write(DateFormat.getDateTimeInstance().format(new Date()) + " "+m+/*"    ; gap="+storage.gap+*/"\n");
295       }
296       catch (IOException e) {
297         LOG.error(e);
298       }
299     }
300   }
301
302   private void flushLog() {
303     try {
304       log.flush();
305     }
306     catch (IOException e) {
307       LOG.error(e);
308     }
309   }
310
311   // return true if file was added to queue
312   private boolean queueUpdate(@NotNull VirtualFile file) {
313     synchronized (filesToResolve) {
314       if (!(file instanceof VirtualFileWithId)) return false;
315       int fileId = getAbsId(file);
316       countAndMarkUnresolved(file, new LinkedHashSet<>(), true);
317       boolean alreadyAdded = fileIsInQueue.set(fileId);
318       if (!alreadyAdded) {
319         filesToResolve.add(file);
320       }
321       upToDate = false;
322       wakeUpUnderLock();
323       return !alreadyAdded;
324     }
325   }
326
327   private void wakeUp() {
328     synchronized (filesToResolve) {
329       wakeUpUnderLock();
330     }
331   }
332
333   private void wakeUpUnderLock() {
334     filesToResolve.notifyAll();
335   }
336
337   private void waitForQueue() throws InterruptedException {
338     synchronized (filesToResolve) {
339       filesToResolve.wait(1000);
340     }
341   }
342
343   private void startThread() {
344     new Thread(this, "Ref resolve service").start();
345     upToDate = true;
346     queueUnresolvedFilesSinceLastRestart();
347   }
348
349   private void queueUnresolvedFilesSinceLastRestart() {
350     PersistentFS fs = PersistentFS.getInstance();
351     int maxId = FSRecords.getMaxId();
352     TIntArrayList list = new TIntArrayList();
353     for (int id= fileIsResolved.nextClearBit(1); id >= 0 && id < maxId; id = fileIsResolved.nextClearBit(id + 1)) {
354       int nextSetBit = fileIsResolved.nextSetBit(id);
355       int endOfRun = Math.min(maxId, nextSetBit == -1 ? maxId : nextSetBit);
356       do {
357         VirtualFile virtualFile = fs.findFileById(id);
358         if (queueIfNeeded(virtualFile, myProject)) {
359           list.add(id);
360         }
361         else {
362           fileIsResolved.set(id);
363         }
364       }
365       while (++id < endOfRun);
366     }
367     log("Initially added to resolve " + toVfString(list.toNativeArray()));
368   }
369
370   @Override
371   public void dispose() {
372     myDisposed = true;
373   }
374
375   private void save() throws IOException {
376     log("Saving resolved file bitset: "+fileIsResolved);
377     fileIsResolved.writeTo(new File(getStorageDirectory(), "bitSet"));
378     log("list.size = " + storage.getSize());
379   }
380
381   private volatile Future<?> resolveProcess = new FutureTask<>(EmptyRunnable.getInstance(), null); // write from EDT only
382
383   @Override
384   public void run() {
385     while (!myDisposed) {
386       boolean isEmpty;
387       synchronized (filesToResolve) {
388         isEmpty = filesToResolve.isEmpty();
389       }
390       if (enableVetoes.get() > 0 ||
391           isEmpty ||
392           !resolveProcess.isDone() ||
393           HeavyProcessLatch.INSTANCE.isRunning() ||
394           PsiDocumentManager.getInstance(myProject).hasUncommitedDocuments()) {
395         try {
396           waitForQueue();
397         }
398         catch (InterruptedException e) {
399           break;
400         }
401         continue;
402       }
403       final Set<VirtualFile> files = pollFilesToResolve();
404       if (files.isEmpty()) continue;
405
406       upToDate = false;
407
408       ApplicationManagerEx.getApplicationEx().invokeLater(() -> {
409         if (!resolveProcess.isDone()) return;
410         log("Started to resolve " + files.size() + " files");
411
412         Task.Backgroundable backgroundable = new Task.Backgroundable(myProject, "Resolving files...", false) {
413           @Override
414           public void run(@NotNull final ProgressIndicator indicator) {
415             if (!ApplicationManagerEx.getApplicationEx().isDisposed()) {
416               processBatch(indicator, files);
417             }
418           }
419         };
420         ProgressIndicator indicator;
421         if (files.size() > 1) {
422           //show progress
423           indicator = new BackgroundableProcessIndicator(backgroundable);
424         }
425         else {
426           indicator = new MyProgress();
427         }
428         resolveProcess = ((ProgressManagerImpl)ProgressManager.getInstance()).runProcessWithProgressAsynchronously(backgroundable, indicator, null);
429       }, myProject.getDisposed());
430
431       flushLog();
432     }
433   }
434
435   private volatile int resolvedInPreviousBatch;
436   private void processBatch(@NotNull final ProgressIndicator indicator, @NotNull Set<VirtualFile> files) {
437     assert !ApplicationManagerEx.getApplicationEx().isDispatchThread();
438     final int resolvedInPreviousBatch = this.resolvedInPreviousBatch;
439     final int totalSize = files.size() + resolvedInPreviousBatch;
440     final IntObjectMap<int[]> fileToForwardIds = ContainerUtil.createConcurrentIntObjectMap();
441     final Set<VirtualFile> toProcess = Collections.synchronizedSet(files);
442     indicator.setIndeterminate(false);
443     ProgressIndicatorUtils.forceWriteActionPriority(indicator, (Disposable)indicator);
444     long start = System.currentTimeMillis();
445     Processor<VirtualFile> processor = file -> {
446       double fraction = 1 - toProcess.size() * 1.0 / totalSize;
447       indicator.setFraction(fraction);
448       try {
449         if (!file.isDirectory() && toResolve(file, myProject)) {
450           int fileId = getAbsId(file);
451           int i = totalSize - toProcess.size();
452           indicator.setText(i + "/" + totalSize + ": Resolving " + file.getPresentableUrl());
453           int[] forwardIds = processFile(file, fileId, indicator);
454           if (forwardIds == null) {
455             //queueUpdate(file);
456             return false;
457           }
458           fileToForwardIds.put(fileId, forwardIds);
459         }
460         toProcess.remove(file);
461         return true;
462       }
463       catch (RuntimeException e) {
464         indicator.checkCanceled();
465       }
466       return true;
467     };
468     boolean success = true;
469     try {
470       success = processFilesConcurrently(files, indicator, processor);
471     }
472     finally {
473       this.resolvedInPreviousBatch = toProcess.isEmpty() ? 0 : totalSize - toProcess.size();
474       queue(toProcess, "re-added after fail. success=" + success);
475       storeIds(fileToForwardIds);
476
477       long end = System.currentTimeMillis();
478       log("Resolved batch of " + (totalSize - toProcess.size()) + " from " + totalSize + " files in " + ((end - start) / 1000) + "sec. (Gap: " + storage.gap+")");
479       synchronized (filesToResolve) {
480         upToDate = filesToResolve.isEmpty();
481         log("upToDate = " + upToDate);
482         if (upToDate) {
483           for (Listener listener : myListeners) {
484             listener.allFilesResolved();
485           }
486         }
487       }
488     }
489   }
490
491   private boolean processFilesConcurrently(@NotNull Set<VirtualFile> files,
492                                            @NotNull final ProgressIndicator indicator,
493                                            @NotNull final Processor<VirtualFile> processor) {
494     final List<VirtualFile> fileList = new ArrayList<>(files);
495     // fine but grabs all CPUs
496     //return JobLauncher.getInstance().invokeConcurrentlyUnderProgress(fileList, indicator, false, false, processor);
497
498     int parallelism = CacheUpdateRunner.indexingThreadCount();
499     final Callable<Boolean> processFileFromSet = () -> {
500       final boolean[] result = {true};
501       ProgressManager.getInstance().executeProcessUnderProgress(() -> {
502         while (true) {
503           ProgressManager.checkCanceled();
504           VirtualFile file;
505           synchronized (fileList) {
506             file = fileList.isEmpty() ? null : fileList.remove(fileList.size() - 1);
507           }
508           if (file == null) {
509             break;
510           }
511           if (!processor.process(file)) {
512             result[0] = false;
513             break;
514           }
515         }
516       }, indicator);
517       return result[0];
518     };
519     List<Future<Boolean>> futures = ContainerUtil.map(Collections.nCopies(parallelism, ""), s -> ApplicationManagerEx.getApplicationEx()
520       .executeOnPooledThread(processFileFromSet));
521
522     List<Boolean> results = ContainerUtil.map(futures, future -> {
523       try {
524         return future.get();
525       }
526       catch (Exception e) {
527         LOG.error(e);
528       }
529       return false;
530     });
531
532     return !ContainerUtil.exists(results, result -> {
533       return result != null && !result;  // null means PCE
534     });
535   }
536
537   @NotNull
538   private Set<VirtualFile> pollFilesToResolve() {
539     Set<VirtualFile> set;
540     synchronized (filesToResolve) {
541       int queuedSize = filesToResolve.size();
542       set = new LinkedHashSet<>(queuedSize);
543       // someone might have cleared this bit to mark file as processed
544       for (VirtualFile file : filesToResolve) {
545         if (fileIsInQueue.clear(getAbsId(file))) {
546           set.add(file);
547         }
548       }
549       filesToResolve.clear();
550     }
551     return countAndMarkUnresolved(set, false);
552   }
553
554   private static int getAbsId(@NotNull VirtualFile file) {
555     return ((VirtualFileWithId)file).getId();
556   }
557
558   @NotNull
559   private Set<VirtualFile> countAndMarkUnresolved(@NotNull Collection<VirtualFile> files, boolean inDbOnly) {
560     Set<VirtualFile> result = new LinkedHashSet<>();
561     for (VirtualFile file : files) {
562       countAndMarkUnresolved(file, result, inDbOnly);
563     }
564     return result;
565   }
566
567   private void countAndMarkUnresolved(@NotNull VirtualFile file, @NotNull final Set<VirtualFile> result, final boolean inDbOnly) {
568     if (file.isDirectory()) {
569       VfsUtilCore.visitChildrenRecursively(file, new VirtualFileVisitor<Void>() {
570         @Override
571         public boolean visitFile(@NotNull VirtualFile file) {
572           return doCountAndMarkUnresolved(file, result);
573         }
574
575         @Nullable
576         @Override
577         public Iterable<VirtualFile> getChildrenIterable(@NotNull VirtualFile file) {
578           return inDbOnly ? ((NewVirtualFile)file).iterInDbChildren() : null;
579         }
580       });
581     }
582     else {
583       doCountAndMarkUnresolved(file, result);
584     }
585   }
586
587   // return true if continue to process sub-directories of the {@code file}, false if the file is already processed
588   private boolean doCountAndMarkUnresolved(@NotNull VirtualFile file, @NotNull Set<VirtualFile> result) {
589     if (file.isDirectory()) {
590       fileIsResolved.set(getAbsId(file));
591       return result.add(file);
592     }
593     if (toResolve(file, myProject)) {
594       result.add(file);
595       fileIsResolved.clear(getAbsId(file));
596     }
597     return true;
598   }
599
600   private void enable() {
601     // decrement but only if it's positive
602     int vetoes;
603     do {
604       vetoes = enableVetoes.get();
605       if (vetoes == 0) break;
606     } while(!enableVetoes.compareAndSet(vetoes, vetoes-1));
607     wakeUp();
608   }
609
610   private void disable() {
611     enableVetoes.incrementAndGet();
612     wakeUp();
613   }
614
615   // returns list of resolved files if updated successfully, or null if write action or dumb mode started
616   private int[] processFile(@NotNull final VirtualFile file, int fileId, @NotNull final ProgressIndicator indicator) {
617     final TIntHashSet forward;
618     try {
619       forward = calcForwardRefs(file, indicator);
620     }
621     catch (IndexNotReadyException | ApplicationUtil.CannotRunReadActionException e) {
622       return null;
623     }
624     catch (ProcessCanceledException e) {
625       throw e;
626     }
627     catch (Exception e) {
628       log(ExceptionUtil.getThrowableText(e));
629       flushLog();
630       return null;
631     }
632
633     int[] forwardIds = forward.toArray();
634     fileIsResolved.set(fileId);
635     logf("  ---- " + file.getPresentableUrl() + " processed. forwardIds: " + toVfString(forwardIds));
636     for (Listener listener : myListeners) {
637       listener.fileResolved(file);
638     }
639     return forwardIds;
640   }
641
642   private void storeIds(@NotNull IntObjectMap<int[]> fileToForwardIds) {
643     int forwardSize = 0;
644     int backwardSize = 0;
645     final TIntObjectHashMap<TIntArrayList> fileToBackwardIds = new TIntObjectHashMap<>(fileToForwardIds.size());
646     for (IntObjectMap.Entry<int[]> entry : fileToForwardIds.entrySet()) {
647       int fileId = entry.getKey();
648       int[] forwardIds = entry.getValue();
649       forwardSize += forwardIds.length;
650       for (int forwardId : forwardIds) {
651         TIntArrayList backIds = fileToBackwardIds.get(forwardId);
652         if (backIds == null) {
653           backIds = new TIntArrayList();
654           fileToBackwardIds.put(forwardId, backIds);
655         }
656         backIds.add(fileId);
657         backwardSize++;
658       }
659     }
660     log("backwardSize = " + backwardSize);
661     log("forwardSize = " + forwardSize);
662     log("fileToForwardIds.size() = "+fileToForwardIds.size());
663     log("fileToBackwardIds.size() = "+fileToBackwardIds.size());
664     assert forwardSize == backwardSize;
665
666     // wrap in read action so that sudden quit (in write action) would not interrupt us
667     ApplicationManagerEx.getApplicationEx().runReadAction(() -> {
668       if (!ApplicationManagerEx.getApplicationEx().isDisposed()) {
669         fileToBackwardIds.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
670           @Override
671           public boolean execute(int fileId, TIntArrayList backIds) {
672             storage.addAll(fileId, backIds.toNativeArray());
673             return true;
674           }
675         });
676       }
677     });
678   }
679
680
681   @NotNull
682   private TIntHashSet calcForwardRefs(@NotNull final VirtualFile virtualFile, @NotNull final ProgressIndicator indicator)
683     throws IndexNotReadyException, ApplicationUtil.CannotRunReadActionException {
684
685     final TIntHashSet forward = new TIntHashSet();
686
687     final PsiFile psiFile = ApplicationUtil.tryRunReadAction(() -> {
688       if (myProject.isDisposed()) throw new ProcessCanceledException();
689       if (fileCount.incrementAndGet() % 100 == 0) {
690         PsiManager.getInstance(myProject).dropResolveCaches();
691         try {
692           storage.flush();
693           log.flush();
694         }
695         catch (IOException e) {
696           LOG.error(e);
697         }
698       }
699
700       return PsiManager.getInstance(myProject).findFile(virtualFile);
701     });
702     final int fileId = getAbsId(virtualFile);
703     if (psiFile != null) {
704       bytesSize.addAndGet(virtualFile.getLength());
705       final Set<PsiElement> resolved = new THashSet<>();
706       ApplicationUtil.tryRunReadAction(new Runnable() {
707         @Override
708         public void run() {
709           indicator.checkCanceled();
710
711           if (psiFile instanceof PsiJavaFile) {
712             psiFile.accept(new JavaRecursiveElementWalkingVisitor() {
713               @Override
714               public void visitReferenceElement(PsiJavaCodeReferenceElement reference) {
715                 indicator.checkCanceled();
716                 resolveReference(reference, resolved);
717
718                 super.visitReferenceElement(reference);
719               }
720             });
721           }
722           else {
723             psiFile.accept(new PsiRecursiveElementWalkingVisitor() {
724               @Override
725               public void visitElement(PsiElement element) {
726                 for (PsiReference reference : element.getReferences()) {
727                   indicator.checkCanceled();
728                   resolveReference(reference, resolved);
729                 }
730                 super.visitElement(element);
731               }
732             });
733           }
734
735           indicator.checkCanceled();
736           for (PsiElement element : resolved) {
737             PsiFile file = element.getContainingFile();
738             addIdAndSuperClasses(file, forward);
739           }
740         }
741       });
742     }
743
744     forward.remove(fileId);
745     return forward;
746   }
747
748   private void resolveReference(@NotNull PsiReference reference, @NotNull Set<PsiElement> resolved) {
749     PsiElement element = reference.resolve();
750     if (element != null) {
751       resolved.add(element);
752     }
753     refCount.incrementAndGet();
754   }
755
756   private static void addIdAndSuperClasses(PsiFile file, @NotNull TIntHashSet forward) {
757     if (file instanceof PsiJavaFile && file.getName().equals("Object.class") && ((PsiJavaFile)file).getPackageName().equals("java.lang")) {
758       return;
759     }
760     VirtualFile virtualFile = PsiUtilCore.getVirtualFile(file);
761     if (virtualFile instanceof VirtualFileWithId && forward.add(getAbsId(virtualFile)) && file instanceof PsiClassOwner) {
762       for (PsiClass aClass : ((PsiClassOwner)file).getClasses()) {
763         for (PsiClass superClass : aClass.getSupers()) {
764           addIdAndSuperClasses(superClass.getContainingFile(), forward);
765         }
766       }
767     }
768   }
769
770   @Override
771   @Nullable
772   public int[] getBackwardIds(@NotNull VirtualFileWithId file) {
773     if (!isUpToDate()) return null;
774     int fileId = getAbsId((VirtualFile)file);
775     return storage.get(fileId);
776   }
777
778   private String prevLog = "";
779   private static final Set<JavaSourceRootType> SOURCE_ROOTS = ContainerUtil.newTroveSet(JavaSourceRootType.SOURCE, JavaSourceRootType.TEST_SOURCE);
780
781   @NotNull
782   @Override
783   public GlobalSearchScope restrictByBackwardIds(@NotNull final VirtualFile virtualFile, @NotNull GlobalSearchScope scope) {
784     final int[] backIds = RefResolveService.getInstance(myProject).getBackwardIds((VirtualFileWithId)virtualFile);
785     if (backIds == null) {
786       return scope;
787     }
788     String files = toVfString(backIds);
789     String log = "Restricting scope of " + virtualFile.getName() + " to " + files;
790     if (!log.equals(prevLog)) {
791       log(log);
792       flushLog();
793       prevLog = log;
794     }
795     GlobalSearchScope restrictedByBackwardIds = new GlobalSearchScope() {
796       @Override
797       public boolean contains(@NotNull VirtualFile file) {
798         if (!(file instanceof VirtualFileWithId)
799             || file.equals(virtualFile)
800             || ArrayUtil.indexOf(backIds, getAbsId(file)) != -1) return true;
801         return false & !myProjectFileIndex.isUnderSourceRootOfType(file, SOURCE_ROOTS); // filter out source file which we know for sure does not reference the element
802       }
803
804       @Override
805       public boolean isSearchInModuleContent(@NotNull Module aModule) {
806         return true;
807       }
808
809       @Override
810       public boolean isSearchInLibraries() {
811         return false;
812       }
813     };
814     return scope.intersectWith(restrictedByBackwardIds);
815   }
816
817   @Override
818   public boolean queue(@NotNull Collection<VirtualFile> files, @NotNull Object reason) {
819     if (files.isEmpty()) {
820       return false;
821     }
822     boolean queued = false;
823     List<VirtualFile> added = new ArrayList<>(files.size());
824     for (VirtualFile file : files) {
825       boolean wasAdded = queueIfNeeded(file, myProject);
826       if (wasAdded) {
827         added.add(file);
828       }
829       queued |= wasAdded;
830     }
831     if (queued) {
832       log("Queued to resolve (from " + reason + "): " + toVfString(added));
833       flushLog();
834     }
835     return queued;
836   }
837
838   @Override
839   public boolean isUpToDate() {
840     return ENABLED && !myDisposed && upToDate;
841   }
842
843   @Override
844   public int getQueueSize() {
845     synchronized (filesToResolve) {
846       return filesToResolve.size();
847     }
848   }
849
850   private final List<Listener> myListeners = ContainerUtil.createLockFreeCopyOnWriteList();
851   @Override
852   public void addListener(@NotNull Disposable parent, @NotNull final Listener listener) {
853     myListeners.add(listener);
854     Disposer.register(parent, new Disposable() {
855       @Override
856       public void dispose() {
857         myListeners.remove(listener);
858       }
859     });
860   }
861
862   private static class MyProgress extends ProgressIndicatorBase implements Disposable{
863     @Override
864     public void dispose() {
865     }
866   }
867 }