Add the clang library to the repo (with some of my changes, too).

1 files changed, 811 insertions, 0 deletions

diff --git a/clang/lib/Rewrite/RewriteRope.cpp b/clang/lib/Rewrite/RewriteRope.cpp
new file mode 100644
index 0000000..cc8de1b
--- /dev/null
+++ b/clang/lib/Rewrite/RewriteRope.cpp
@@ -0,0 +1,811 @@
+//===--- 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 "clang/Basic/LLVM.h"
+#include <algorithm>
+using namespace clang;
+
+/// 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 classof(const RopePieceBTreeLeaf *) { return true; }
+    static inline bool classof(const RopePieceBTreeNode *N) {
+      return N->isLeaf();
+    }
+  };
+} // end anonymous namespace
+
+/// 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 *RopePieceBTreeLeaf::split(unsigned Offset) {
+  // Find the insertion point.  We are guaranteed that there is a split at the
+  // specified offset so find it.
+  if (Offset == 0 || Offset == size()) {
+    // Fastpath for a common case.  There is already a splitpoint at the end.
+    return 0;
+  }
+
+  // Find the piece that this offset lands in.
+  unsigned PieceOffs = 0;
+  unsigned i = 0;
+  while (Offset >= PieceOffs+Pieces[i].size()) {
+    PieceOffs += Pieces[i].size();
+    ++i;
+  }
+
+  // If there is already a split point at the specified offset, just return
+  // success.
+  if (PieceOffs == Offset)
+    return 0;
+
+  // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
+  // to being Piece relative.
+  unsigned IntraPieceOffset = Offset-PieceOffs;
+
+  // We do this by shrinking the RopePiece and then doing an insert of the tail.
+  RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
+                 Pieces[i].EndOffs);
+  Size -= Pieces[i].size();
+  Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
+  Size += Pieces[i].size();
+
+  return insert(Offset, Tail);
+}
+
+
+/// 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 *RopePieceBTreeLeaf::insert(unsigned Offset,
+                                               const RopePiece &R) {
+  // If this node is not full, insert the piece.
+  if (!isFull()) {
+    // Find the insertion point.  We are guaranteed that there is a split at the
+    // specified offset so find it.
+    unsigned i = 0, e = getNumPieces();
+    if (Offset == size()) {
+      // Fastpath for a common case.
+      i = e;
+    } else {
+      unsigned SlotOffs = 0;
+      for (; Offset > SlotOffs; ++i)
+        SlotOffs += getPiece(i).size();
+      assert(SlotOffs == Offset && "Split didn't occur before insertion!");
+    }
+
+    // For an insertion into a non-full leaf node, just insert the value in
+    // its sorted position.  This requires moving later values over.
+    for (; i != e; --e)
+      Pieces[e] = Pieces[e-1];
+    Pieces[i] = R;
+    ++NumPieces;
+    Size += R.size();
+    return 0;
+  }
+
+  // Otherwise, if this is leaf is full, split it in two halves.  Since this
+  // node is full, it contains 2*WidthFactor values.  We move the first
+  // 'WidthFactor' values to the LHS child (which we leave in this node) and
+  // move the last 'WidthFactor' values into the RHS child.
+
+  // Create the new node.
+  RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
+
+  // Move over the last 'WidthFactor' values from here to NewNode.
+  std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
+            &NewNode->Pieces[0]);
+  // Replace old pieces with null RopePieces to drop refcounts.
+  std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumPieces = NumPieces = WidthFactor;
+
+  // Recompute the two nodes' size.
+  NewNode->FullRecomputeSizeLocally();
+  FullRecomputeSizeLocally();
+
+  // Update the list of leaves.
+  NewNode->insertAfterLeafInOrder(this);
+
+  // These insertions can't fail.
+  if (this->size() >= Offset)
+    this->insert(Offset, R);
+  else
+    NewNode->insert(Offset - this->size(), R);
+  return NewNode;
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
+  // Since we are guaranteed that there is a split at Offset, we start by
+  // finding the Piece that starts there.
+  unsigned PieceOffs = 0;
+  unsigned i = 0;
+  for (; Offset > PieceOffs; ++i)
+    PieceOffs += getPiece(i).size();
+  assert(PieceOffs == Offset && "Split didn't occur before erase!");
+
+  unsigned StartPiece = i;
+
+  // Figure out how many pieces completely cover 'NumBytes'.  We want to remove
+  // all of them.
+  for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
+    PieceOffs += getPiece(i).size();
+
+  // If we exactly include the last one, include it in the region to delete.
+  if (Offset+NumBytes == PieceOffs+getPiece(i).size())
+    PieceOffs += getPiece(i).size(), ++i;
+
+  // If we completely cover some RopePieces, erase them now.
+  if (i != StartPiece) {
+    unsigned NumDeleted = i-StartPiece;
+    for (; i != getNumPieces(); ++i)
+      Pieces[i-NumDeleted] = Pieces[i];
+
+    // Drop references to dead rope pieces.
+    std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
+              RopePiece());
+    NumPieces -= NumDeleted;
+
+    unsigned CoverBytes = PieceOffs-Offset;
+    NumBytes -= CoverBytes;
+    Size -= CoverBytes;
+  }
+
+  // If we completely removed some stuff, we could be done.
+  if (NumBytes == 0) return;
+
+  // Okay, now might be erasing part of some Piece.  If this is the case, then
+  // move the start point of the piece.
+  assert(getPiece(StartPiece).size() > NumBytes);
+  Pieces[StartPiece].StartOffs += NumBytes;
+
+  // The size of this node just shrunk by NumBytes.
+  Size -= NumBytes;
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeInterior Class
+//===----------------------------------------------------------------------===//
+
+namespace {
+  /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
+  /// which holds up to 2*WidthFactor pointers to child nodes.
+  class RopePieceBTreeInterior : public RopePieceBTreeNode {
+    /// NumChildren - This holds the number of children currently active in the
+    /// Children array.
+    unsigned char NumChildren;
+    RopePieceBTreeNode *Children[2*WidthFactor];
+  public:
+    RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
+
+    RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
+    : RopePieceBTreeNode(false) {
+      Children[0] = LHS;
+      Children[1] = RHS;
+      NumChildren = 2;
+      Size = LHS->size() + RHS->size();
+    }
+
+    ~RopePieceBTreeInterior() {
+      for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+        Children[i]->Destroy();
+    }
+
+    bool isFull() const { return NumChildren == 2*WidthFactor; }
+
+    unsigned getNumChildren() const { return NumChildren; }
+    const RopePieceBTreeNode *getChild(unsigned i) const {
+      assert(i < NumChildren && "invalid child #");
+      return Children[i];
+    }
+    RopePieceBTreeNode *getChild(unsigned i) {
+      assert(i < NumChildren && "invalid child #");
+      return Children[i];
+    }
+
+    /// FullRecomputeSizeLocally - Recompute the Size field of this node by
+    /// summing up the sizes of the child nodes.
+    void FullRecomputeSizeLocally() {
+      Size = 0;
+      for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
+        Size += getChild(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);
+
+    /// HandleChildPiece - A child propagated an insertion result up to us.
+    /// Insert the new child, and/or propagate the result further up the tree.
+    RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
+
+    /// 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 RopePieceBTreeInterior *) { return true; }
+    static inline bool classof(const RopePieceBTreeNode *N) {
+      return !N->isLeaf();
+    }
+  };
+} // end anonymous namespace
+
+/// 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 *RopePieceBTreeInterior::split(unsigned Offset) {
+  // Figure out which child to split.
+  if (Offset == 0 || Offset == size())
+    return 0;  // If we have an exact offset, we're already split.
+
+  unsigned ChildOffset = 0;
+  unsigned i = 0;
+  for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
+    ChildOffset += getChild(i)->size();
+
+  // If already split there, we're done.
+  if (ChildOffset == Offset)
+    return 0;
+
+  // Otherwise, recursively split the child.
+  if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
+    return HandleChildPiece(i, RHS);
+  return 0;  // Done!
+}
+
+/// 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 *RopePieceBTreeInterior::insert(unsigned Offset,
+                                                   const RopePiece &R) {
+  // Find the insertion point.  We are guaranteed that there is a split at the
+  // specified offset so find it.
+  unsigned i = 0, e = getNumChildren();
+
+  unsigned ChildOffs = 0;
+  if (Offset == size()) {
+    // Fastpath for a common case.  Insert at end of last child.
+    i = e-1;
+    ChildOffs = size()-getChild(i)->size();
+  } else {
+    for (; Offset > ChildOffs+getChild(i)->size(); ++i)
+      ChildOffs += getChild(i)->size();
+  }
+
+  Size += R.size();
+
+  // Insert at the end of this child.
+  if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
+    return HandleChildPiece(i, RHS);
+
+  return 0;
+}
+
+/// HandleChildPiece - A child propagated an insertion result up to us.
+/// Insert the new child, and/or propagate the result further up the tree.
+RopePieceBTreeNode *
+RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
+  // Otherwise the child propagated a subtree up to us as a new child.  See if
+  // we have space for it here.
+  if (!isFull()) {
+    // Insert RHS after child 'i'.
+    if (i + 1 != getNumChildren())
+      memmove(&Children[i+2], &Children[i+1],
+              (getNumChildren()-i-1)*sizeof(Children[0]));
+    Children[i+1] = RHS;
+    ++NumChildren;
+    return 0;
+  }
+
+  // Okay, this node is full.  Split it in half, moving WidthFactor children to
+  // a newly allocated interior node.
+
+  // Create the new node.
+  RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
+
+  // Move over the last 'WidthFactor' values from here to NewNode.
+  memcpy(&NewNode->Children[0], &Children[WidthFactor],
+         WidthFactor*sizeof(Children[0]));
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumChildren = NumChildren = WidthFactor;
+
+  // Finally, insert the two new children in the side the can (now) hold them.
+  // These insertions can't fail.
+  if (i < WidthFactor)
+    this->HandleChildPiece(i, RHS);
+  else
+    NewNode->HandleChildPiece(i-WidthFactor, RHS);
+
+  // Recompute the two nodes' size.
+  NewNode->FullRecomputeSizeLocally();
+  FullRecomputeSizeLocally();
+  return NewNode;
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
+  // This will shrink this node by NumBytes.
+  Size -= NumBytes;
+
+  // Find the first child that overlaps with Offset.
+  unsigned i = 0;
+  for (; Offset >= getChild(i)->size(); ++i)
+    Offset -= getChild(i)->size();
+
+  // Propagate the delete request into overlapping children, or completely
+  // delete the children as appropriate.
+  while (NumBytes) {
+    RopePieceBTreeNode *CurChild = getChild(i);
+
+    // If we are deleting something contained entirely in the child, pass on the
+    // request.
+    if (Offset+NumBytes < CurChild->size()) {
+      CurChild->erase(Offset, NumBytes);
+      return;
+    }
+
+    // If this deletion request starts somewhere in the middle of the child, it
+    // must be deleting to the end of the child.
+    if (Offset) {
+      unsigned BytesFromChild = CurChild->size()-Offset;
+      CurChild->erase(Offset, BytesFromChild);
+      NumBytes -= BytesFromChild;
+      // Start at the beginning of the next child.
+      Offset = 0;
+      ++i;
+      continue;
+    }
+
+    // If the deletion request completely covers the child, delete it and move
+    // the rest down.
+    NumBytes -= CurChild->size();
+    CurChild->Destroy();
+    --NumChildren;
+    if (i != getNumChildren())
+      memmove(&Children[i], &Children[i+1],
+              (getNumChildren()-i)*sizeof(Children[0]));
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeNode Implementation
+//===----------------------------------------------------------------------===//
+
+void RopePieceBTreeNode::Destroy() {
+  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    delete Leaf;
+  else
+    delete cast<RopePieceBTreeInterior>(this);
+}
+
+/// 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 *RopePieceBTreeNode::split(unsigned Offset) {
+  assert(Offset <= size() && "Invalid offset to split!");
+  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->split(Offset);
+  return cast<RopePieceBTreeInterior>(this)->split(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 *RopePieceBTreeNode::insert(unsigned Offset,
+                                               const RopePiece &R) {
+  assert(Offset <= size() && "Invalid offset to insert!");
+  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->insert(Offset, R);
+  return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
+}
+
+/// erase - Remove NumBytes from this node at the specified offset.  We are
+/// guaranteed that there is a split at Offset.
+void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
+  assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
+  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
+    return Leaf->erase(Offset, NumBytes);
+  return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
+}
+
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeIterator Implementation
+//===----------------------------------------------------------------------===//
+
+static const RopePieceBTreeLeaf *getCN(const void *P) {
+  return static_cast<const RopePieceBTreeLeaf*>(P);
+}
+
+// begin iterator.
+RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
+  const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
+
+  // Walk down the left side of the tree until we get to a leaf.
+  while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
+    N = IN->getChild(0);
+
+  // We must have at least one leaf.
+  CurNode = cast<RopePieceBTreeLeaf>(N);
+
+  // If we found a leaf that happens to be empty, skip over it until we get
+  // to something full.
+  while (CurNode && getCN(CurNode)->getNumPieces() == 0)
+    CurNode = getCN(CurNode)->getNextLeafInOrder();
+
+  if (CurNode != 0)
+    CurPiece = &getCN(CurNode)->getPiece(0);
+  else  // Empty tree, this is an end() iterator.
+    CurPiece = 0;
+  CurChar = 0;
+}
+
+void RopePieceBTreeIterator::MoveToNextPiece() {
+  if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
+    CurChar = 0;
+    ++CurPiece;
+    return;
+  }
+
+  // Find the next non-empty leaf node.
+  do
+    CurNode = getCN(CurNode)->getNextLeafInOrder();
+  while (CurNode && getCN(CurNode)->getNumPieces() == 0);
+
+  if (CurNode != 0)
+    CurPiece = &getCN(CurNode)->getPiece(0);
+  else // Hit end().
+    CurPiece = 0;
+  CurChar = 0;
+}
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTree Implementation
+//===----------------------------------------------------------------------===//
+
+static RopePieceBTreeNode *getRoot(void *P) {
+  return static_cast<RopePieceBTreeNode*>(P);
+}
+
+RopePieceBTree::RopePieceBTree() {
+  Root = new RopePieceBTreeLeaf();
+}
+RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
+  assert(RHS.empty() && "Can't copy non-empty tree yet");
+  Root = new RopePieceBTreeLeaf();
+}
+RopePieceBTree::~RopePieceBTree() {
+  getRoot(Root)->Destroy();
+}
+
+unsigned RopePieceBTree::size() const {
+  return getRoot(Root)->size();
+}
+
+void RopePieceBTree::clear() {
+  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
+    Leaf->clear();
+  else {
+    getRoot(Root)->Destroy();
+    Root = new RopePieceBTreeLeaf();
+  }
+}
+
+void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
+  // #1. Split at Offset.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+
+  // #2. Do the insertion.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+}
+
+void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
+  // #1. Split at Offset.
+  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
+    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
+
+  // #2. Do the erasing.
+  getRoot(Root)->erase(Offset, NumBytes);
+}
+
+//===----------------------------------------------------------------------===//
+// RewriteRope Implementation
+//===----------------------------------------------------------------------===//
+
+/// MakeRopeString - This copies the specified byte range into some instance of
+/// RopeRefCountString, and return a RopePiece that represents it.  This uses
+/// the AllocBuffer object to aggregate requests for small strings into one
+/// allocation instead of doing tons of tiny allocations.
+RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
+  unsigned Len = End-Start;
+  assert(Len && "Zero length RopePiece is invalid!");
+
+  // If we have space for this string in the current alloc buffer, use it.
+  if (AllocOffs+Len <= AllocChunkSize) {
+    memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
+    AllocOffs += Len;
+    return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
+  }
+
+  // If we don't have enough room because this specific allocation is huge,
+  // just allocate a new rope piece for it alone.
+  if (Len > AllocChunkSize) {
+    unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
+    RopeRefCountString *Res =
+      reinterpret_cast<RopeRefCountString *>(new char[Size]);
+    Res->RefCount = 0;
+    memcpy(Res->Data, Start, End-Start);
+    return RopePiece(Res, 0, End-Start);
+  }
+
+  // Otherwise, this was a small request but we just don't have space for it
+  // Make a new chunk and share it with later allocations.
+
+  // If we had an old allocation, drop our reference to it.
+  if (AllocBuffer && --AllocBuffer->RefCount == 0)
+    delete [] (char*)AllocBuffer;
+
+  unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
+  AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
+  AllocBuffer->RefCount = 0;
+  memcpy(AllocBuffer->Data, Start, Len);
+  AllocOffs = Len;
+
+  // Start out the new allocation with a refcount of 1, since we have an
+  // internal reference to it.
+  AllocBuffer->addRef();
+  return RopePiece(AllocBuffer, 0, Len);
+}
+
+