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

/*
 * Copyright 2000-2014 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.openapi.editor.impl;

import com.intellij.openapi.application.ApplicationManager;
import com.intellij.openapi.application.impl.ApplicationInfoImpl;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.editor.Document;
import com.intellij.openapi.editor.event.DocumentEvent;
import com.intellij.openapi.editor.ex.PrioritizedDocumentListener;
import com.intellij.openapi.editor.ex.PrioritizedInternalDocumentListener;
import com.intellij.openapi.editor.ex.RangeMarkerEx;
import com.intellij.openapi.editor.ex.SweepProcessor;
import com.intellij.openapi.util.Getter;
import com.intellij.openapi.util.Segment;
import com.intellij.util.Processor;
import com.intellij.util.SmartList;
import org.jetbrains.annotations.NotNull;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * User: cdr
 */
public class RangeMarkerTree<T extends RangeMarkerEx> extends IntervalTreeImpl<T> {
  private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.editor.impl.RangeMarkerTree");
  private static final boolean DEBUG = LOG.isDebugEnabled() || ApplicationManager.getApplication() != null && (ApplicationManager.getApplication().isUnitTestMode() || ApplicationManager.getApplication().isInternal());

  private final PrioritizedDocumentListener myListener;
  private final Document myDocument;

  protected RangeMarkerTree(@NotNull Document document) {
    myDocument = document;
    myListener = new PrioritizedInternalDocumentListener() {
      @Override
      public int getPriority() {
        return EditorDocumentPriorities.RANGE_MARKER; // Need to make sure we invalidate all the stuff before someone (like LineStatusTracker) starts to modify highlights.
      }

      @Override
      public void beforeDocumentChange(DocumentEvent event) {}

      @Override
      public void documentChanged(DocumentEvent e) {
        updateMarkersOnChange(e);
      }

      @Override
      public void moveTextHappened(int start, int end, int newBase) {
        reTarget(start, end, newBase);
      }
    };

    document.addDocumentListener(myListener);
  }

  @Override
  protected int compareEqualStartIntervals(@NotNull IntervalTreeImpl.IntervalNode<T> i1, @NotNull IntervalTreeImpl.IntervalNode<T> i2) {
    RMNode o1 = (RMNode)i1;
    RMNode o2 = (RMNode)i2;
    boolean greedyL1 = o1.isGreedyToLeft();
    boolean greedyL2 = o2.isGreedyToLeft();
    if (greedyL1 != greedyL2) return greedyL1 ? -1 : 1;

    int o1Length = o1.intervalEnd() - o1.intervalStart();
    int o2Length = o2.intervalEnd() - o2.intervalStart();
    int d = o1Length - o2Length;
    if (d != 0) return d;

    boolean greedyR1 = o1.isGreedyToRight();
    boolean greedyR2 = o2.isGreedyToRight();
    if (greedyR1 != greedyR2) return greedyR1 ? -1 : 1;

    return 0;
  }

  public void dispose() {
    myDocument.removeDocumentListener(myListener);
  }

  private static final int DUPLICATE_LIMIT = 30; // assertion: no more than DUPLICATE_LIMIT range markers are allowed to be registered at given (start, end)
  @Override
  public RMNode<T> addInterval(@NotNull T interval, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
    RangeMarkerImpl marker = (RangeMarkerImpl)interval;
    marker.setValid(true);
    RMNode<T> node = (RMNode)super.addInterval(interval, start, end, greedyToLeft, greedyToRight, layer);

    if (DEBUG && !ApplicationInfoImpl.isInPerformanceTest() && node.intervals.size() > DUPLICATE_LIMIT) {
      l.readLock().lock();
      try {
        String msg = errMsg(node);
        if (msg != null) {
          LOG.warn(msg);
        }
      }
      finally {
        l.readLock().unlock();
      }
    }
    return node;
  }
  private String errMsg(@NotNull RMNode<T> node) {
    final AtomicInteger alive = new AtomicInteger();
    node.processAliveKeys(new Processor<Object>() {
      @Override
      public boolean process(Object t) {
        alive.incrementAndGet();
        return true;
      }
    });
    if (alive.get() > DUPLICATE_LIMIT) {
      return "Too many range markers (" + alive + ") registered in "+this+"\n";
    }

    return null;
  }

  @NotNull
  @Override
  protected RMNode<T> createNewNode(@NotNull T key, int start, int end, boolean greedyToLeft, boolean greedyToRight, int layer) {
    return new RMNode<T>(this, key, start, end, greedyToLeft, greedyToRight);
  }

  @Override
  protected void checkBelongsToTheTree(T interval, boolean assertInvalid) {
    assert ((RangeMarkerImpl)interval).myDocument == myDocument;
    super.checkBelongsToTheTree(interval, assertInvalid);
  }

  @Override
  protected RMNode<T> lookupNode(@NotNull T key) {
    return (RMNode<T>)((RangeMarkerImpl)key).myNode;
  }

  @Override
  protected void setNode(@NotNull T key, IntervalNode<T> intervalNode) {
    ((RangeMarkerImpl)key).myNode = (RMNode)intervalNode;
  }

  static class RMNode<T extends RangeMarkerEx> extends IntervalTreeImpl.IntervalNode<T> {
    private static final int EXPAND_TO_LEFT_FLAG = VALID_FLAG+1;
    private static final int EXPAND_TO_RIGHT_FLAG = EXPAND_TO_LEFT_FLAG+1;

    public RMNode(@NotNull RangeMarkerTree<T> rangeMarkerTree,
                  @NotNull T key,
                  int start,
                  int end,
                  boolean greedyToLeft,
                  boolean greedyToRight) {
      super(rangeMarkerTree, key, start, end);
      setFlag(EXPAND_TO_LEFT_FLAG, greedyToLeft);
      setFlag(EXPAND_TO_RIGHT_FLAG, greedyToRight);
    }

    public boolean isGreedyToLeft() {
      return isFlagSet(EXPAND_TO_LEFT_FLAG);
    }

    public boolean isGreedyToRight() {
      return isFlagSet(EXPAND_TO_RIGHT_FLAG);
    }

    @Override
    public String toString() {
      return (isGreedyToLeft() ? "[" : "(") + intervalStart() + "," + intervalEnd() + (isGreedyToRight() ? "]" : ")");
    }
  }

  private void updateMarkersOnChange(@NotNull DocumentEvent e) {
    try {
      l.writeLock().lock();
      if (size() == 0) return;
      checkMax(true);

      modCount++;
      List<IntervalNode<T>> affected = new SmartList<IntervalNode<T>>();
      collectAffectedMarkersAndShiftSubtrees(getRoot(), e, affected);
      checkMax(false);

      if (!affected.isEmpty()) {
        for (IntervalNode<T> node : affected) {
          // assumption: interval.getEndOffset() will never be accessed during remove()
          int startOffset = node.intervalStart();
          int endOffset = node.intervalEnd();
          removeNode(node);
          checkMax(false);
          node.clearDelta();   // we can do it because all the deltas up from the root to this node were cleared in the collectAffectedMarkersAndShiftSubtrees
          node.setParent(null);
          node.setLeft(null);
          node.setRight(null);
          node.setValid(true);
          assert node.intervalStart() == startOffset;
          assert node.intervalEnd() == endOffset;
        }
        checkMax(true);
        for (IntervalNode<T> node : affected) {
          List<Getter<T>> keys = node.intervals;
          if (keys.isEmpty()) continue; // collected away

          RangeMarkerImpl marker = null;
          for (int i = keys.size() - 1; i >= 0; i--) {
            Getter<T> key = keys.get(i);
            marker = (RangeMarkerImpl)key.get();
            if (marker != null) {
              if (!marker.isValid()) {
                // marker can become invalid on its own, e.g. FoldRegion
                node.removeIntervalInternal(i);
                marker = null;
                continue;
              }
              break;
            }
          }
          if (marker == null) continue; // node remains removed from the tree
          marker.documentChanged(e);
          if (marker.isValid()) {
            RMNode<T> insertedNode = (RMNode)findOrInsert(node);
            // can change if two range become the one
            if (insertedNode != node) {
              // merge happened
              for (Getter<T> key : keys) {
                T interval = key.get();
                if (interval == null) continue;
                insertedNode.addInterval(interval);
              }
            }
            assert marker.isValid();
          }
          else {
            node.setValid(false);
          }
        }
      }
      checkMax(true);

      IntervalNode<T> root = getRoot();
      assert root == null || root.maxEnd + root.delta <= myDocument.getTextLength();
    }
    finally {
      l.writeLock().unlock();
    }
  }

  // returns true if all deltas involved are still 0
  private boolean collectAffectedMarkersAndShiftSubtrees(IntervalNode<T> root,
                                                         @NotNull DocumentEvent e,
                                                         @NotNull List<IntervalNode<T>> affected) {
    if (root == null) return true;
    boolean norm = pushDelta(root);

    int maxEnd = root.maxEnd;
    assert root.isValid();

    int offset = e.getOffset();
    int affectedEndOffset = offset + e.getOldLength();
    boolean hasAliveKeys = root.hasAliveKey(false);
    if (!hasAliveKeys) {
      // marker was garbage collected
      affected.add(root);
    }
    if (offset > maxEnd) {
      // no need to bother
    }
    else if (affectedEndOffset < root.intervalStart()) {
      // shift entire subtree
      int lengthDelta = e.getNewLength() - e.getOldLength();
      int newD = root.changeDelta(lengthDelta);
      norm &= newD == 0;
      IntervalNode<T> left = root.getLeft();
      if (left != null) {
        int newL = left.changeDelta(-lengthDelta);
        norm &= newL == 0;
      }
      norm &= pushDelta(root);
      norm &= collectAffectedMarkersAndShiftSubtrees(left, e, affected);
      correctMax(root, 0);
    }
    else {
      if (offset <= root.intervalEnd()) {
        // unlucky enough so that change affects the interval
        if (hasAliveKeys) affected.add(root); // otherwise we've already added it
        root.setValid(false);  //make invisible
      }

      norm &= collectAffectedMarkersAndShiftSubtrees(root.getLeft(), e, affected);
      norm &= collectAffectedMarkersAndShiftSubtrees(root.getRight(), e, affected);
      correctMax(root,0);
    }
    return norm;
  }

  public boolean sweep(final int start, final int end, @NotNull final SweepProcessor<T> sweepProcessor) {
    return sweep(new Generator<T>() {
      @Override
      public boolean generateInStartOffsetOrder(@NotNull Processor<T> processor) {
        return processOverlappingWith(start, end, processor);
      }
    }, sweepProcessor);
  }

  public interface Generator<T> {
    boolean generateInStartOffsetOrder(@NotNull Processor<T> processor);
  }

  public static <T extends Segment> boolean sweep(@NotNull Generator<T> generator, @NotNull final SweepProcessor<T> sweepProcessor) {
    final Queue<T> ends = new PriorityQueue<T>(5, new Comparator<T>() {
      @Override
      public int compare(T o1, T o2) {
        return o1.getEndOffset() - o2.getEndOffset();
      }
    });
    final List<T> starts = new ArrayList<T>();
    if (!generator.generateInStartOffsetOrder(new Processor<T>() {
      @Override
      public boolean process(T marker) {
        // decide whether previous marker ends here or new marker begins
        int start = marker.getStartOffset();
        while (true) {
          assert ends.size() == starts.size();
          T previous = ends.peek();
          if (previous != null) {
            int prevEnd = previous.getEndOffset();
            if (prevEnd <= start) {
              if (!sweepProcessor.process(prevEnd, previous, false, ends)) return false;
              ends.remove();
              boolean removed = starts.remove(previous);
              assert removed;
              continue;
            }
          }
          break;
        }
        if (!sweepProcessor.process(start, marker, true, ends)) return false;
        starts.add(marker);
        ends.offer(marker);

        return true;
      }
    })) return false;

    while (!ends.isEmpty()) {
      assert ends.size() == starts.size();
      T previous = ends.remove();
      int prevEnd = previous.getEndOffset();
      if (!sweepProcessor.process(prevEnd, previous, false, ends)) return false;
      boolean removed = starts.remove(previous);
      assert removed;
    }

    return true;
  }

  private void reTarget(int start, int end, int newBase) {
    l.writeLock().lock();
    try {
      checkMax(true);

      List<IntervalNode<T>> affected = new ArrayList<IntervalNode<T>>();
      collectNodesToRetarget(getRoot(), start, end, affected);
      if (affected.isEmpty()) return;

      int shift = newBase - start;
      for (IntervalNode<T> node : affected) {
        removeNode(node);
        node.setLeft(null);
        node.setRight(null);
        node.setParent(null);
        node.changeDelta(shift);
        node.setValid(true);
        pushDelta(node);
        findOrInsert(node);
      }
    }
    finally {
      checkMax(true);
      l.writeLock().unlock();
    }
  }

  private void collectNodesToRetarget(IntervalNode<T> root,
                                      int start, int end,
                                      @NotNull List<IntervalNode<T>> affected) {
    if (root == null) return;
    pushDelta(root);

    int maxEnd = root.maxEnd;
    assert root.isValid();

    if (start > maxEnd) {
      // no need to bother
      return;
    }
    collectNodesToRetarget(root.getLeft(), start, end, affected);
    if (start <= root.intervalStart() && root.intervalEnd() <= end) {
      affected.add(root);
    }
    if (end < root.intervalStart()) {
      return;
    }
    collectNodesToRetarget(root.getRight(), start, end, affected);
  }
}