d27218eefbcf9a868acf66c7856ec67966a167d4
[idea/community.git] / 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 }