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         frozen = frozen.applyEvent(event, 0);
 116         corrected = new DocumentEventImpl(frozen, event.getOffset(), event.getOldFragment(), event.getNewFragment(), event.getOldTimeStamp(),
 117                                           event.isWholeTextReplaced(),
 118                                           ((DocumentEventImpl) event).getInitialStartOffset(), ((DocumentEventImpl) event).getInitialOldLength());
 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 }