path: root/lib/Rewrite/RewriteRope.cpp

//===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file implements the RewriteRope class, which is a powerful string.
//
//===----------------------------------------------------------------------===//

#include "clang/Rewrite/RewriteRope.h"
#include "llvm/Support/Casting.h"
#include <algorithm>
using namespace clang;
using llvm::dyn_cast;
using llvm::cast;

/// RewriteRope is a "strong" string class, designed to make insertions and
/// deletions in the middle of the string nearly constant time (really, they are
/// O(log N), but with a very low constant factor).
///
/// The implementation of this datastructure is a conceptual linear sequence of
/// RopePiece elements.  Each RopePiece represents a view on a separately
/// allocated and reference counted string.  This means that splitting a very
/// long string can be done in constant time by splitting a RopePiece that
/// references the whole string into two rope pieces that reference each half.
/// Once split, another string can be inserted in between the two halves by
/// inserting a RopePiece in between the two others.  All of this is very
/// inexpensive: it takes time proportional to the number of RopePieces, not the
/// length of the strings they represent.
///
/// While a linear sequences of RopePieces is the conceptual model, the actual
/// implementation captures them in an adapted B+ Tree.  Using a B+ tree (which
/// is a tree that keeps the values in the leaves and has where each node
/// contains a reasonable number of pointers to children/values) allows us to
/// maintain efficient operation when the RewriteRope contains a *huge* number
/// of RopePieces.  The basic idea of the B+ Tree is that it allows us to find
/// the RopePiece corresponding to some offset very efficiently, and it
/// automatically balances itself on insertions of RopePieces (which can happen
/// for both insertions and erases of string ranges).
///
/// The one wrinkle on the theory is that we don't attempt to keep the tree
/// properly balanced when erases happen.  Erases of string data can both insert
/// new RopePieces (e.g. when the middle of some other rope piece is deleted,
/// which results in two rope pieces, which is just like an insert) or it can
/// reduce the number of RopePieces maintained by the B+Tree.  In the case when
/// the number of RopePieces is reduced, we don't attempt to maintain the
/// standard 'invariant' that each node in the tree contains at least
/// 'WidthFactor' children/values.  For our use cases, this doesn't seem to
/// matter.
///
/// The implementation below is primarily implemented in terms of three classes:
///   RopePieceBTreeNode - Common base class for:
///
///     RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
///          nodes.  This directly represents a chunk of the string with those
///          RopePieces contatenated.
///     RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
///          up to '2*WidthFactor' other nodes in the tree.


//===----------------------------------------------------------------------===//
// RopePieceBTreeNode Class
//===----------------------------------------------------------------------===//

namespace {
  /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
  /// RopePieceBTreeInterior.  This provides some 'virtual' dispatching methods
  /// and a flag that determines which subclass the instance is.  Also
  /// important, this node knows the full extend of the node, including any
  /// children that it has.  This allows efficient skipping over entire subtrees
  /// when looking for an offset in the BTree.
  class RopePieceBTreeNode {
  protected:
    /// WidthFactor - This controls the number of K/V slots held in the BTree:
    /// how wide it is.  Each level of the BTree is guaranteed to have at least
    /// 'WidthFactor' elements in it (either ropepieces or children), (except
    /// the root, which may have less) and may have at most 2*WidthFactor
    /// elements.
    enum { WidthFactor = 8 };

    /// Size - This is the number of bytes of file this node (including any
    /// potential children) covers.
    unsigned Size;

    /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
    /// is an instance of RopePieceBTreeInterior.
    bool IsLeaf;

    RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
    ~RopePieceBTreeNode() {}
  public:

    bool isLeaf() const { return IsLeaf; }
    unsigned size() const { return Size; }

    void Destroy();

    /// split - Split the range containing the specified offset so that we are
    /// guaranteed that there is a place to do an insertion at the specified
    /// offset.  The offset is relative, so "0" is the start of the node.
    ///
    /// If there is no space in this subtree for the extra piece, the extra tree
    /// node is returned and must be inserted into a parent.
    RopePieceBTreeNode *split(unsigned Offset);

    /// insert - Insert the specified ropepiece into this tree node at the
    /// specified offset.  The offset is relative, so "0" is the start of the
    /// node.
    ///
    /// If there is no space in this subtree for the extra piece, the extra tree
    /// node is returned and must be inserted into a parent.
    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);

    /// erase - Remove NumBytes from this node at the specified offset.  We are
    /// guaranteed that there is a split at Offset.
    void erase(unsigned Offset, unsigned NumBytes);

    static inline bool classof(const RopePieceBTreeNode *) { return true; }

  };
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// RopePieceBTreeLeaf Class
//===----------------------------------------------------------------------===//

namespace {
  /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
  /// nodes.  This directly represents a chunk of the string with those
  /// RopePieces contatenated.  Since this is a B+Tree, all values (in this case
  /// instances of RopePiece) are stored in leaves like this.  To make iteration
  /// over the leaves efficient, they maintain a singly linked list through the
  /// NextLeaf field.  This allows the B+Tree forward iterator to be constant
  /// time for all increments.
  class RopePieceBTreeLeaf : public RopePieceBTreeNode {
    /// NumPieces - This holds the number of rope pieces currently active in the
    /// Pieces array.
    unsigned char NumPieces;

    /// Pieces - This tracks the file chunks currently in this leaf.
    ///
    RopePiece Pieces[2*WidthFactor];

    /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
    /// efficient in-order forward iteration of the tree without traversal.
    RopePieceBTreeLeaf **PrevLeaf, *NextLeaf;
  public:
    RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0),
                           PrevLeaf(0), NextLeaf(0) {}
    ~RopePieceBTreeLeaf() {
      if (PrevLeaf || NextLeaf)
        removeFromLeafInOrder();
      clear();
    }

    bool isFull() const { return NumPieces == 2*WidthFactor; }

    /// clear - Remove all rope pieces from this leaf.
    void clear() {
      while (NumPieces)
        Pieces[--NumPieces] = RopePiece();
      Size = 0;
    }

    unsigned getNumPieces() const { return NumPieces; }

    const RopePiece &getPiece(unsigned i) const {
      assert(i < getNumPieces() && "Invalid piece ID");
      return Pieces[i];
    }

    const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
    void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
      assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");

      NextLeaf = Node->NextLeaf;
      if (NextLeaf)
        NextLeaf->PrevLeaf = &NextLeaf;
      PrevLeaf = &Node->NextLeaf;
      Node->NextLeaf = this;
    }

    void removeFromLeafInOrder() {
      if (PrevLeaf) {
        *PrevLeaf = NextLeaf;
        if (NextLeaf)
          NextLeaf->PrevLeaf = PrevLeaf;
      } else if (NextLeaf) {
        NextLeaf->PrevLeaf = 0;
      }
    }

    /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
    /// summing the size of all RopePieces.
    void FullRecomputeSizeLocally() {
      Size = 0;
      for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
        Size += getPiece(i).size();
    }

    /// split - Split the range containing the specified offset so that we are
    /// guaranteed that there is a place to do an insertion at the specified
    /// offset.  The offset is relative, so "0" is the start of the node.
    ///
    /// If there is no space in this subtree for the extra piece, the extra tree
    /// node is returned and must be inserted into a parent.
    RopePieceBTreeNode *split(unsigned Offset);

    /// insert - Insert the specified ropepiece into this tree node at the
    /// specified offset.  The offset is relative, so "0" is the start of the
    /// node.
    ///
    /// If there is no space in this subtree for the extra piece, the extra tree
    /// node is returned and must be inserted into a parent.
    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);


    /// erase - Remove NumBytes from this node at the specified offset.  We are
    /// guaranteed that there is a split at Offset.
    void erase(unsigned Offset, unsigned NumBytes);

    static inline bool