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