platform/util/src/com/intellij/openapi/util/ObjectTree.java

   1 // Copyright 2000-2020 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.openapi.util;
   3
   4 import com.intellij.openapi.Disposable;
   5 import com.intellij.openapi.diagnostic.Logger;
   6 import com.intellij.openapi.progress.ProcessCanceledException;
   7 import com.intellij.openapi.util.objectTree.ThrowableInterner;
   8 import com.intellij.util.IncorrectOperationException;
   9 import com.intellij.util.SmartList;
  10 import com.intellij.util.containers.ContainerUtil;
  11 import it.unimi.dsi.fastutil.objects.Reference2ObjectOpenHashMap;
  12 import it.unimi.dsi.fastutil.objects.ReferenceOpenHashSet;
  13 import org.jetbrains.annotations.NotNull;
  14 import org.jetbrains.annotations.Nullable;
  15 import org.jetbrains.annotations.TestOnly;
  16
  17 import java.util.*;
  18 import java.util.function.Supplier;
  19
  20 final class ObjectTree {
  21   private static final ThreadLocal<Throwable> ourTopmostDisposeTrace = new ThreadLocal<>();
  22
  23   // identity used here to prevent problems with hashCode/equals overridden by not very bright minds
  24   private final Set<Disposable> myRootObjects = new ReferenceOpenHashSet<>(); // guarded by treeLock
  25   // guarded by treeLock
  26   private final Map<Disposable, ObjectNode> myObject2NodeMap = new Reference2ObjectOpenHashMap<>();
  27   // Disposable -> trace or boolean marker (if trace unavailable)
  28   private final Map<Disposable, Object> myDisposedObjects = ContainerUtil.createWeakMap(100, 0.5f, ContainerUtil.identityStrategy()); // guarded by treeLock
  29
  30   final Object treeLock = new Object();
  31
  32   private ObjectNode getNode(@NotNull Disposable object) {
  33     return myObject2NodeMap.get(object);
  34   }
  35
  36   private void putNode(@NotNull Disposable object, @Nullable("null means remove") ObjectNode node) {
  37     if (node == null) {
  38       myObject2NodeMap.remove(object);
  39     }
  40     else {
  41       myObject2NodeMap.put(object, node);
  42     }
  43   }
  44
  45   @Nullable
  46   final RuntimeException register(@NotNull Disposable parent, @NotNull Disposable child) {
  47     if (parent == child) return new IllegalArgumentException("Cannot register to itself: "+parent);
  48     synchronized (treeLock) {
  49       Object wasDisposed = getDisposalInfo(parent);
  50       if (wasDisposed != null) {
  51         return new IncorrectOperationException("Sorry but parent: " + parent + " has already been disposed " +
  52                                               "(see the cause for stacktrace) so the child: "+child+" will never be disposed",
  53                                               wasDisposed instanceof Throwable ? (Throwable)wasDisposed : null);
  54       }
  55
  56       myDisposedObjects.remove(child); // if we dispose thing and then register it back it means it's not disposed anymore
  57       ObjectNode parentNode = getNode(parent);
  58       if (parentNode == null) parentNode = createNodeFor(parent, null);
  59
  60       ObjectNode childNode = getNode(child);
  61       if (childNode == null) {
  62         childNode = createNodeFor(child, parentNode);
  63       }
  64       else {
  65         ObjectNode oldParent = childNode.getParent();
  66         if (oldParent != null) {
  67           oldParent.removeChild(childNode);
  68         }
  69       }
  70       myRootObjects.remove(child);
  71
  72       RuntimeException e = checkWasNotAddedAlready(parentNode, childNode);
  73       if (e != null) return e;
  74
  75       parentNode.addChild(childNode);
  76     }
  77     return null;
  78   }
  79
  80   Object getDisposalInfo(@NotNull Disposable object) {
  81     synchronized (treeLock) {
  82       return myDisposedObjects.get(object);
  83     }
  84   }
  85
  86   private static RuntimeException checkWasNotAddedAlready(@NotNull ObjectNode childNode, @NotNull ObjectNode parentNode) {
  87     for (ObjectNode node = childNode; node != null; node = node.getParent()) {
  88       if (node == parentNode) {
  89         return new IncorrectOperationException("'"+childNode.getObject() + "' was already added as a child of '" + parentNode.getObject()+"'");
  90       }
  91     }
  92     return null;
  93   }
  94
  95   @NotNull
  96   private ObjectNode createNodeFor(@NotNull Disposable object, @Nullable ObjectNode parentNode) {
  97     final ObjectNode newNode = new ObjectNode(this, parentNode, object);
  98     if (parentNode == null) {
  99       myRootObjects.add(object);
 100     }
 101     putNode(object, newNode);
 102     return newNode;
 103   }
 104
 105   private void runWithTrace(@NotNull Supplier<? extends List<Disposable>> removeFromTreeAction) {
 106     boolean needTrace = Disposer.isDebugMode() && ourTopmostDisposeTrace.get() == null;
 107     if (needTrace) {
 108       ourTopmostDisposeTrace.set(ThrowableInterner.intern(new Throwable()));
 109     }
 110
 111     // first, atomically remove disposables from the tree to avoid "register during dispose" race conditions
 112     List<Disposable> disposables;
 113     synchronized (treeLock) {
 114       disposables = removeFromTreeAction.get();
 115     }
 116
 117     // second, call "beforeTreeDispose" in pre-order (some clients are hardcoded to see parents-then-children order in "beforeTreeDispose")
 118     List<Throwable> exceptions = null;
 119     for (int i = disposables.size() - 1; i >= 0; i--) {
 120       Disposable disposable = disposables.get(i);
 121       if (disposable instanceof Disposable.Parent) {
 122         try {
 123           ((Disposable.Parent)disposable).beforeTreeDispose();
 124         }
 125         catch (Throwable t) {
 126           if (exceptions == null) exceptions = new SmartList<>();
 127           exceptions.add(t);
 128         }
 129       }
 130     }
 131
 132     // third, dispose in post-order (bottom-up)
 133     for (Disposable disposable : disposables) {
 134       try {
 135         //noinspection SSBasedInspection
 136         disposable.dispose();
 137       }
 138       catch (Throwable e) {
 139         if (exceptions == null) exceptions = new SmartList<>();
 140         exceptions.add(e);
 141       }
 142     }
 143
 144     if (needTrace) {
 145       ourTopmostDisposeTrace.remove();
 146     }
 147     if (exceptions != null) {
 148       handleExceptions(exceptions);
 149     }
 150   }
 151
 152   void executeAllChildren(@NotNull Disposable object) {
 153     runWithTrace(() -> {
 154       ObjectNode node = getNode(object);
 155       if (node == null) {
 156         return Collections.emptyList();
 157       }
 158       List<Disposable> disposables = new ArrayList<>();
 159       node.getAndRemoveChildrenRecursively(disposables);
 160       return disposables;
 161     });
 162   }
 163
 164   void executeAll(@NotNull Disposable object, boolean processUnregistered) {
 165     runWithTrace(() -> {
 166       ObjectNode node = getNode(object);
 167       if (node == null && !processUnregistered) {
 168         return Collections.emptyList();
 169       }
 170       List<Disposable> disposables = new ArrayList<>();
 171       if (node == null) {
 172         if (rememberDisposedTrace(object) == null) {
 173           disposables.add(object);
 174         }
 175       }
 176       else {
 177         node.getAndRemoveRecursively(disposables);
 178       }
 179       return disposables;
 180     });
 181   }
 182
 183   private static void handleExceptions(@NotNull List<? extends Throwable> exceptions) {
 184     if (!exceptions.isEmpty()) {
 185       for (Throwable exception : exceptions) {
 186         if (!(exception instanceof ProcessCanceledException)) {
 187           getLogger().error(exception);
 188         }
 189       }
 190
 191       ProcessCanceledException pce = ContainerUtil.findInstance(exceptions, ProcessCanceledException.class);
 192       if (pce != null) {
 193         throw pce;
 194       }
 195     }
 196   }
 197
 198   @TestOnly
 199   void assertNoReferenceKeptInTree(@NotNull Disposable disposable) {
 200     synchronized (treeLock) {
 201       for (Map.Entry<Disposable, ObjectNode> entry : myObject2NodeMap.entrySet()) {
 202         Disposable key = entry.getKey();
 203         assert key != disposable;
 204         ObjectNode node = entry.getValue();
 205         node.assertNoReferencesKept(disposable);
 206       }
 207     }
 208   }
 209
 210   void assertIsEmpty(boolean throwError) {
 211     synchronized (treeLock) {
 212       for (Disposable object : myRootObjects) {
 213         if (object == null) continue;
 214         ObjectNode objectNode = getNode(object);
 215         if (objectNode == null) continue;
 216         while (objectNode.getParent() != null) {
 217           objectNode = objectNode.getParent();
 218         }
 219         final Throwable trace = objectNode.getTrace();
 220         RuntimeException exception = new RuntimeException("Memory leak detected: '" + object + "' of " + object.getClass()
 221                                                           + "\nSee the cause for the corresponding Disposer.register() stacktrace:\n",
 222                                                           trace);
 223         if (throwError) {
 224           throw exception;
 225         }
 226         getLogger().error(exception);
 227       }
 228     }
 229   }
 230
 231   @NotNull
 232   private static Logger getLogger() {
 233     return Logger.getInstance(ObjectTree.class);
 234   }
 235
 236   // return old value
 237   Object rememberDisposedTrace(@NotNull Disposable object) {
 238     synchronized (treeLock) {
 239       Throwable trace = ourTopmostDisposeTrace.get();
 240       return myDisposedObjects.put(object, trace != null ? trace : Boolean.TRUE);
 241     }
 242   }
 243
 244   void clearDisposedObjectTraces() {
 245     synchronized (treeLock) {
 246       myDisposedObjects.clear();
 247       for (ObjectNode value : myObject2NodeMap.values()) {
 248         value.clearTrace();
 249       }
 250     }
 251   }
 252
 253   @Nullable
 254   <D extends Disposable> D findRegisteredObject(@NotNull Disposable parentDisposable, @NotNull D object) {
 255     synchronized (treeLock) {
 256       ObjectNode parentNode = getNode(parentDisposable);
 257       if (parentNode == null) return null;
 258       return parentNode.findChildEqualTo(object);
 259     }
 260   }
 261
 262   void removeObjectFromTree(@NotNull ObjectNode node) {
 263     synchronized (treeLock) {
 264       Disposable myObject = node.getObject();
 265       putNode(myObject, null);
 266       ObjectNode parent = node.getParent();
 267       if (parent == null) {
 268         myRootObjects.remove(myObject);
 269       }
 270       else {
 271         parent.removeChild(node);
 272       }
 273       node.myParent = null;
 274     }
 275   }
 276 }