platform/core-impl/src/com/intellij/openapi/editor/impl/RangeMarkerTree.java

   1 /*
   2  * Copyright 2000-2015 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.openapi.editor.impl;
  17
  18 import com.intellij.openapi.application.ApplicationManager;
  19 import com.intellij.openapi.application.impl.ApplicationInfoImpl;
  20 import com.intellij.openapi.diagnostic.Logger;
  21 import com.intellij.openapi.editor.Document;
  22 import com.intellij.openapi.editor.event.DocumentEvent;
  23 import com.intellij.openapi.editor.ex.PrioritizedDocumentListener;
  24 import com.intellij.openapi.editor.ex.PrioritizedInternalDocumentListener;
  25 import com.intellij.openapi.editor.ex.RangeMarkerEx;
  26 import com.intellij.openapi.editor.ex.SweepProcessor;
  27 import com.intellij.openapi.util.Getter;
  28 import com.intellij.openapi.util.Segment;
  29 import com.intellij.util.Processor;
  30 import com.intellij.util.SmartList;
  31 import org.jetbrains.annotations.NotNull;
  32 import org.jetbrains.annotations.Nullable;
  33
  34 import java.util.*;
  35 import java.util.concurrent.atomic.AtomicInteger;
  36
  37 /**
  38  * User: cdr
  39  */
  40 public class RangeMarkerTree<T extends RangeMarkerEx> extends IntervalTreeImpl<T> {
  41   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.editor.impl.RangeMarkerTree");
  42   private static final boolean DEBUG = LOG.isDebugEnabled() || ApplicationManager.getApplication() != null && (ApplicationManager.getApplication().isUnitTestMode() || ApplicationManager.getApplication().isInternal());
  43
  44   private final PrioritizedDocumentListener myListener;
  45   private final Document myDocument;
  46
  47   protected RangeMarkerTree(@NotNull Document document) {
  48     myDocument = document;
  49     myListener = new PrioritizedInternalDocumentListener() {
  50       @Override
  51       public int getPriority() {
  52         return EditorDocumentPriorities.RANGE_MARKER; // Need to make sure we invalidate all the stuff before someone (like LineStatusTracker) starts to modify highlights.
  53       }
  54
  55       @Override
  56       public void beforeDocumentChange(DocumentEvent event) {}
  57
  58       @Override
  59       public void documentChanged(DocumentEvent e) {
  60         updateMarkersOnChange(e);
  61       }
  62
  63       @Override
  64       public void moveTextHappened(int start, int end, int newBase) {
  65         reTarget(start, end, newBase);
  66       }
  67     };
  68
  69     document.addDocumentListener(myListener);
  70   }
  71
  72   @Override
  73   protected int compareEqualStartIntervals(@NotNull IntervalTreeImpl.IntervalNode<T> i1, @NotNull IntervalTreeImpl.IntervalNode<T> i2) {
  74     RMNode o1 = (RMNode)i1;
  75     RMNode o2 = (RMNode)i2;
  76     boolean greedyL1 = o1.isGreedyToLeft();
  77     boolean greedyL2 = o2.isGreedyToLeft();
  78     if (greedyL1 != greedyL2) return greedyL1 ? -1 : 1;
  79
  80     int o1Length = o1.intervalEnd() - o1.intervalStart();
  81     int o2Length = o2.intervalEnd() - o2.intervalStart();
  82     int d = o1Length - o2Length;
  83     if (d != 0) return d;
  84
  85     boolean greedyR1 = o1.isGreedyToRight();
  86     boolean greedyR2 = o2.isGreedyToRight();
  87     if (greedyR1 != greedyR2) return greedyR1 ? -1 : 1;
  88
  89     return 0;
  90   }
  91
  92   void dispose() {
  93     myDocument.removeDocumentListener(myListener);
  94   }
  95
  96   private static final int DUPLICATE_LIMIT = 30; // assertion: no more than DUPLICATE_LIMIT range markers are allowed to be registered at given (start, end)
  97   @NotNull
  98   @Override
  99   public RMNode<T> addInterval(@NotNull T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
 100     interval.setValid(true);
 101     RMNode<T> node = (RMNode<T>)super.addInterval(interval, start, end, greedyToLeft, greedyToRight, layer);
 102
 103     if (DEBUG && !ApplicationInfoImpl.isInPerformanceTest() && node.intervals.size() > DUPLICATE_LIMIT) {
 104       l.readLock().lock();
 105       try {
 106         String msg = errMsg(node);
 107         if (msg != null) {
 108           LOG.warn(msg);
 109         }
 110       }
 111       finally {
 112         l.readLock().unlock();
 113       }
 114     }
 115     return node;
 116   }
 117   private String errMsg(@NotNull RMNode<T> node) {
 118     final AtomicInteger alive = new AtomicInteger();
 119     node.processAliveKeys(new Processor<Object>() {
 120       @Override
 121       public boolean process(Object t) {
 122         alive.incrementAndGet();
 123         return true;
 124       }
 125     });
 126     if (alive.get() > DUPLICATE_LIMIT) {
 127       return "Too many range markers (" + alive + ") registered for interval "+node+"\n";
 128     }
 129
 130     return null;
 131   }
 132
 133   @NotNull
 134   @Override
 135   protected RMNode<T> createNewNode(@NotNull T key, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
 136     return new RMNode<T>(this, key, start, end, greedyToLeft, greedyToRight);
 137   }
 138
 139   @Override
 140   protected void checkBelongsToTheTree(@NotNull T interval, boolean assertInvalid) {
 141     assert interval.getDocument() == myDocument;
 142     super.checkBelongsToTheTree(interval, assertInvalid);
 143   }
 144
 145   @Override
 146   protected RMNode<T> lookupNode(@NotNull T key) {
 147     //noinspection unchecked
 148     return (RMNode<T>)((RangeMarkerImpl)key).myNode;
 149   }
 150
 151   @Override
 152   protected void setNode(@NotNull T key, IntervalNode<T> intervalNode) {
 153     //noinspection unchecked
 154     ((RangeMarkerImpl)key).myNode = (RMNode)intervalNode;
 155   }
 156
 157   static class RMNode<T extends RangeMarkerEx> extends IntervalTreeImpl.IntervalNode<T> {
 158     private static final byte EXPAND_TO_LEFT_FLAG = VALID_FLAG<<1;
 159     private static final byte EXPAND_TO_RIGHT_FLAG = EXPAND_TO_LEFT_FLAG<<1;
 160
 161     public RMNode(@NotNull RangeMarkerTree<T> rangeMarkerTree,
 162                   @NotNull T key,
 163                   int start,
 164                   int end,
 165                   boolean greedyToLeft,
 166                   boolean greedyToRight) {
 167       super(rangeMarkerTree, key, start, end);
 168       setFlag(EXPAND_TO_LEFT_FLAG, greedyToLeft);
 169       setFlag(EXPAND_TO_RIGHT_FLAG, greedyToRight);
 170     }
 171
 172     boolean isGreedyToLeft() {
 173       return isFlagSet(EXPAND_TO_LEFT_FLAG);
 174     }
 175
 176     boolean isGreedyToRight() {
 177       return isFlagSet(EXPAND_TO_RIGHT_FLAG);
 178     }
 179
 180     @Override
 181     public String toString() {
 182       return (isGreedyToLeft() ? "[" : "(") + intervalStart() + "," + intervalEnd() + (isGreedyToRight() ? "]" : ")");
 183     }
 184   }
 185
 186   private void updateMarkersOnChange(@NotNull DocumentEvent e) {
 187     try {
 188       l.writeLock().lock();
 189       if (size() == 0) return;
 190       checkMax(true);
 191
 192       modCount++;
 193       List<IntervalNode<T>> affected = new SmartList<IntervalNode<T>>();
 194       collectAffectedMarkersAndShiftSubtrees(getRoot(), e, affected);
 195       checkMax(false);
 196
 197       if (!affected.isEmpty()) {
 198         for (IntervalNode<T> node : affected) {
 199           // assumption: interval.getEndOffset() will never be accessed during remove()
 200           int startOffset = node.intervalStart();
 201           int endOffset = node.intervalEnd();
 202           removeNode(node);
 203           checkMax(false);
 204           node.clearDelta();   // we can do it because all the deltas up from the root to this node were cleared in the collectAffectedMarkersAndShiftSubtrees
 205           node.setParent(null);
 206           node.setLeft(null);
 207           node.setRight(null);
 208           node.setValid(true);
 209           assert node.intervalStart() == startOffset;
 210           assert node.intervalEnd() == endOffset;
 211         }
 212         checkMax(true);
 213         for (IntervalNode<T> node : affected) {
 214           List<Getter<T>> keys = node.intervals;
 215           if (keys.isEmpty()) continue; // collected away
 216
 217           RangeMarkerImpl marker = null;
 218           for (int i = keys.size() - 1; i >= 0; i--) {
 219             Getter<T> key = keys.get(i);
 220             marker = (RangeMarkerImpl)key.get();
 221             if (marker != null) {
 222               if (!marker.isValid()) {
 223                 // marker can become invalid on its own, e.g. FoldRegion
 224                 node.removeIntervalInternal(i);
 225                 marker = null;
 226                 continue;
 227               }
 228               break;
 229             }
 230           }
 231           if (marker == null) continue; // node remains removed from the tree
 232           marker.documentChanged(e);
 233           if (marker.isValid()) {
 234             RMNode<T> insertedNode = (RMNode)findOrInsert(node);
 235             // can change if two range become the one
 236             if (insertedNode != node) {
 237               // merge happened
 238               for (Getter<T> key : keys) {
 239                 T interval = key.get();
 240                 if (interval == null) continue;
 241                 insertedNode.addInterval(interval);
 242               }
 243             }
 244             assert marker.isValid();
 245           }
 246           else {
 247             node.setValid(false);
 248           }
 249         }
 250       }
 251       checkMax(true);
 252
 253       IntervalNode<T> root = getRoot();
 254       assert root == null || root.maxEnd + root.delta <= myDocument.getTextLength();
 255     }
 256     finally {
 257       l.writeLock().unlock();
 258     }
 259   }
 260
 261   // returns true if all deltas involved are still 0
 262   private boolean collectAffectedMarkersAndShiftSubtrees(@Nullable IntervalNode<T> root,
 263                                                          @NotNull DocumentEvent e,
 264                                                          @NotNull List<IntervalNode<T>> affected) {
 265     if (root == null) return true;
 266     boolean norm = pushDelta(root);
 267
 268     int maxEnd = root.maxEnd;
 269     assert root.isValid();
 270
 271     int offset = e.getOffset();
 272     int affectedEndOffset = offset + e.getOldLength();
 273     boolean hasAliveKeys = root.hasAliveKey(false);
 274     if (!hasAliveKeys) {
 275       // marker was garbage collected
 276       affected.add(root);
 277     }
 278     if (offset > maxEnd) {
 279       // no need to bother
 280     }
 281     else if (affectedEndOffset < root.intervalStart()) {
 282       // shift entire subtree
 283       int lengthDelta = e.getNewLength() - e.getOldLength();
 284       int newD = root.changeDelta(lengthDelta);
 285       norm &= newD == 0;
 286       IntervalNode<T> left = root.getLeft();
 287       if (left != null) {
 288         int newL = left.changeDelta(-lengthDelta);
 289         norm &= newL == 0;
 290       }
 291       norm &= pushDelta(root);
 292       norm &= collectAffectedMarkersAndShiftSubtrees(left, e, affected);
 293       correctMax(root, 0);
 294     }
 295     else {
 296       if (offset <= root.intervalEnd()) {
 297         // unlucky enough so that change affects the interval
 298         if (hasAliveKeys) affected.add(root); // otherwise we've already added it
 299         root.setValid(false);  //make invisible
 300       }
 301
 302       norm &= collectAffectedMarkersAndShiftSubtrees(root.getLeft(), e, affected);
 303       norm &= collectAffectedMarkersAndShiftSubtrees(root.getRight(), e, affected);
 304       correctMax(root,0);
 305     }
 306     return norm;
 307   }
 308
 309   public boolean sweep(final int start, final int end, @NotNull SweepProcessor<T> sweepProcessor) {
 310     return sweep(new Generator<T>() {
 311       @Override
 312       public boolean generateInStartOffsetOrder(@NotNull Processor<T> processor) {
 313         return processOverlappingWith(start, end, processor);
 314       }
 315     }, sweepProcessor);
 316   }
 317
 318   public interface Generator<T> {
 319     boolean generateInStartOffsetOrder(@NotNull Processor<T> processor);
 320   }
 321
 322   public static <T extends Segment> boolean sweep(@NotNull Generator<T> generator, @NotNull final SweepProcessor<T> sweepProcessor) {
 323     final Queue<T> ends = new PriorityQueue<T>(5, new Comparator<T>() {
 324       @Override
 325       public int compare(@NotNull T o1, @NotNull T o2) {
 326         return o1.getEndOffset() - o2.getEndOffset();
 327       }
 328     });
 329     final List<T> starts = new ArrayList<T>();
 330     if (!generator.generateInStartOffsetOrder(new Processor<T>() {
 331       @Override
 332       public boolean process(T marker) {
 333         // decide whether previous marker ends here or new marker begins
 334         int start = marker.getStartOffset();
 335         while (true) {
 336           assert ends.size() == starts.size();
 337           T previous = ends.peek();
 338           if (previous != null) {
 339             int prevEnd = previous.getEndOffset();
 340             if (prevEnd <= start) {
 341               if (!sweepProcessor.process(prevEnd, previous, false, ends)) return false;
 342               ends.remove();
 343               boolean removed = starts.remove(previous);
 344               assert removed;
 345               continue;
 346             }
 347           }
 348           break;
 349         }
 350         if (!sweepProcessor.process(start, marker, true, ends)) return false;
 351         starts.add(marker);
 352         ends.offer(marker);
 353
 354         return true;
 355       }
 356     })) return false;
 357
 358     while (!ends.isEmpty()) {
 359       assert ends.size() == starts.size();
 360       T previous = ends.remove();
 361       int prevEnd = previous.getEndOffset();
 362       if (!sweepProcessor.process(prevEnd, previous, false, ends)) return false;
 363       boolean removed = starts.remove(previous);
 364       assert removed;
 365     }
 366
 367     return true;
 368   }
 369
 370   private void reTarget(int start, int end, int newBase) {
 371     l.writeLock().lock();
 372     try {
 373       checkMax(true);
 374
 375       List<IntervalNode<T>> affected = new ArrayList<IntervalNode<T>>();
 376       collectNodesToRetarget(getRoot(), start, end, affected);
 377       if (affected.isEmpty()) return;
 378
 379       int shift = newBase - start;
 380       for (IntervalNode<T> node : affected) {
 381         removeNode(node);
 382         node.setLeft(null);
 383         node.setRight(null);
 384         node.setParent(null);
 385         node.changeDelta(shift);
 386         node.setValid(true);
 387         pushDelta(node);
 388         findOrInsert(node);
 389       }
 390     }
 391     finally {
 392       checkMax(true);
 393       l.writeLock().unlock();
 394     }
 395   }
 396
 397   private void collectNodesToRetarget(@Nullable IntervalNode<T> root,
 398                                       int start, int end,
 399                                       @NotNull List<IntervalNode<T>> affected) {
 400     if (root == null) return;
 401     pushDelta(root);
 402
 403     int maxEnd = root.maxEnd;
 404     assert root.isValid();
 405
 406     if (start > maxEnd) {
 407       // no need to bother
 408       return;
 409     }
 410     collectNodesToRetarget(root.getLeft(), start, end, affected);
 411     if (start <= root.intervalStart() && root.intervalEnd() <= end) {
 412       affected.add(root);
 413     }
 414     if (end < root.intervalStart()) {
 415       return;
 416     }
 417     collectNodesToRetarget(root.getRight(), start, end, affected);
 418   }
 419 }