some more assertions
[idea/community.git] / platform / core-impl / src / com / intellij / psi / impl / smartPointers / MarkerCache.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.psi.impl.smartPointers;
17
18 import com.intellij.openapi.editor.event.DocumentEvent;
19 import com.intellij.openapi.editor.impl.FrozenDocument;
20 import com.intellij.openapi.editor.impl.ManualRangeMarker;
21 import com.intellij.openapi.editor.impl.event.DocumentEventImpl;
22 import com.intellij.openapi.editor.impl.event.RetargetRangeMarkers;
23 import com.intellij.openapi.util.TextRange;
24 import com.intellij.openapi.util.UnfairTextRange;
25 import org.jetbrains.annotations.NotNull;
26 import org.jetbrains.annotations.Nullable;
27
28 import java.util.Collections;
29 import java.util.Comparator;
30 import java.util.List;
31
32 /**
33  * @author peter
34  */
35 class MarkerCache {
36   static final Comparator<SelfElementInfo> INFO_COMPARATOR = new Comparator<SelfElementInfo>() {
37     @Override
38     public int compare(SelfElementInfo info1, SelfElementInfo info2) {
39       int o1 = info1.getPsiStartOffset();
40       int o2 = info2.getPsiStartOffset();
41       if (o1 < 0 || o2 < 0) return o1 >= 0 ? -1 : o2 >= 0 ? 1 : 0; // infos without range go after infos with range
42       if (o1 != o2) return o1 > o2 ? 1 : -1;
43
44       o1 = info1.getPsiEndOffset();
45       o2 = info2.getPsiEndOffset();
46       if (o1 != o2) return o1 > o2 ? 1 : -1;
47
48       return (info1.isForInjected() ? 1 : 0) - (info2.isForInjected() ? 1 : 0);
49     }
50   };
51   private final SmartPointerTracker myPointers;
52   private UpdatedRanges myUpdatedRanges;
53
54   MarkerCache(SmartPointerTracker pointers) {
55     myPointers = pointers;
56   }
57
58   private UpdatedRanges getUpdatedMarkers(@NotNull FrozenDocument frozen, @NotNull List<DocumentEvent> events) {
59     int eventCount = events.size();
60     assert eventCount > 0;
61
62     UpdatedRanges cache = myUpdatedRanges;
63     if (cache != null && cache.myEventCount == eventCount) return cache;
64
65     UpdatedRanges answer;
66     if (cache != null && cache.myEventCount < eventCount) {
67       // apply only the new events
68       answer = applyEvents(events.subList(cache.myEventCount, eventCount), cache);
69     }
70     else {
71       List<SelfElementInfo> infos = myPointers.getSortedInfos();
72       ManualRangeMarker[] markers = createMarkers(infos);
73       answer = applyEvents(events, new UpdatedRanges(0, frozen, infos, markers));
74     }
75
76     myUpdatedRanges = answer;
77     return answer;
78   }
79
80   @NotNull
81   private static ManualRangeMarker[] createMarkers(List<SelfElementInfo> infos) {
82     ManualRangeMarker[] markers = new ManualRangeMarker[infos.size()];
83     int i = 0;
84     while (i < markers.length) {
85       SelfElementInfo info = infos.get(i);
86       boolean forInjected = info.isForInjected();
87       int start = info.getPsiStartOffset();
88       int end = info.getPsiEndOffset();
89       markers[i] = new ManualRangeMarker(start, end, forInjected, forInjected, !forInjected, null);
90
91       i++;
92       while (i < markers.length && rangeEquals(infos.get(i), start, end, forInjected)) {
93         markers[i] = markers[i - 1];
94         i++;
95       }
96     }
97     return markers;
98   }
99
100   private static boolean rangeEquals(SelfElementInfo info, int start, int end, boolean injected) {
101     return start == info.getPsiStartOffset() && end == info.getPsiEndOffset() && injected == info.isForInjected();
102   }
103
104   private static UpdatedRanges applyEvents(@NotNull List<DocumentEvent> events, final UpdatedRanges struct) {
105     FrozenDocument frozen = struct.myResultDocument;
106     ManualRangeMarker[] resultMarkers = struct.myMarkers.clone();
107     for (DocumentEvent event : events) {
108       final FrozenDocument before = frozen;
109       final DocumentEvent corrected;
110       if (event instanceof RetargetRangeMarkers) {
111         RetargetRangeMarkers retarget = (RetargetRangeMarkers)event;
112         corrected = new RetargetRangeMarkers(frozen, retarget.getStartOffset(), retarget.getEndOffset(), retarget.getMoveDestinationOffset());
113       }
114       else {
115         corrected = new DocumentEventImpl(frozen, event.getOffset(), event.getOldFragment(), event.getNewFragment(), event.getOldTimeStamp(),
116                                           event.isWholeTextReplaced(),
117                                           ((DocumentEventImpl) event).getInitialStartOffset(), ((DocumentEventImpl) event).getInitialOldLength());
118         frozen = frozen.applyEvent(event, 0);
119       }
120
121       int i = 0;
122       while (i < resultMarkers.length) {
123         ManualRangeMarker currentRange = resultMarkers[i];
124
125         int sameMarkersEnd = i + 1;
126         while (sameMarkersEnd < resultMarkers.length && resultMarkers[sameMarkersEnd] == currentRange) {
127           sameMarkersEnd++;
128         }
129
130         ManualRangeMarker updatedRange = currentRange == null ? null : currentRange.getUpdatedRange(corrected, before);
131         while (i < sameMarkersEnd) {
132           resultMarkers[i] = updatedRange;
133           i++;
134         }
135       }
136     }
137     return new UpdatedRanges(struct.myEventCount + events.size(), frozen, struct.mySortedInfos, resultMarkers);
138   }
139
140   boolean updateMarkers(@NotNull FrozenDocument frozen, @NotNull List<DocumentEvent> events) {
141     UpdatedRanges updated = getUpdatedMarkers(frozen, events);
142
143     boolean sorted = true;
144     for (int i = 0; i < updated.myMarkers.length; i++) {
145       SelfElementInfo info = updated.mySortedInfos.get(i);
146       info.setRange(updated.myMarkers[i]);
147       if (sorted && i > 0 && INFO_COMPARATOR.compare(updated.mySortedInfos.get(i - 1), info) > 0) {
148         sorted = false;
149       }
150     }
151
152     myUpdatedRanges = null;
153     return sorted;
154   }
155
156   @Nullable
157   TextRange getUpdatedRange(@NotNull SelfElementInfo info, @NotNull FrozenDocument frozen, @NotNull List<DocumentEvent> events) {
158     UpdatedRanges struct = getUpdatedMarkers(frozen, events);
159     int i = Collections.binarySearch(struct.mySortedInfos, info, INFO_COMPARATOR);
160     ManualRangeMarker updated = i >= 0 ? struct.myMarkers[i] : null;
161     return updated == null ? null : new UnfairTextRange(updated.getStartOffset(), updated.getEndOffset());
162   }
163
164   void rangeChanged() {
165     myUpdatedRanges = null;
166   }
167
168   private static class UpdatedRanges {
169     private final int myEventCount;
170     private final FrozenDocument myResultDocument;
171     private final List<SelfElementInfo> mySortedInfos;
172     private final ManualRangeMarker[] myMarkers;
173
174     public UpdatedRanges(int eventCount,
175                          FrozenDocument resultDocument,
176                          List<SelfElementInfo> sortedInfos, ManualRangeMarker[] markers) {
177       myEventCount = eventCount;
178       myResultDocument = resultDocument;
179       mySortedInfos = sortedInfos;
180       myMarkers = markers;
181     }
182   }
183 }