move a ton of code out of line, from RewriteRope.h -> RewriteRope.cpp

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@49664 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 796 insertions, 694 deletions

diff --git a/clang.xcodeproj/project.pbxproj b/clang.xcodeproj/project.pbxproj
index d083987178..9d2c312fc4 100644
--- a/clang.xcodeproj/project.pbxproj
+++ b/clang.xcodeproj/project.pbxproj
@@ -132,6 +132,7 @@
 		DEC8D9910A9433CD00353FCA /* Decl.h in CopyFiles */ = {isa = PBXBuildFile; fileRef = DEC8D9900A9433CD00353FCA /* Decl.h */; };
 		DEC8D9A40A94346E00353FCA /* AST.h in CopyFiles */ = {isa = PBXBuildFile; fileRef = DEC8D9A30A94346E00353FCA /* AST.h */; };
 		DECAB0950DA684C500E13CCB /* CGObjCEtoile.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DECAB0940DA684C500E13CCB /* CGObjCEtoile.cpp */; };
+		DECAB0D00DB3C84200E13CCB /* RewriteRope.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DECAB0CF0DB3C84200E13CCB /* RewriteRope.cpp */; };
 		DED626C90AE0C065001E80A4 /* TargetInfo.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DED626C80AE0C065001E80A4 /* TargetInfo.cpp */; };
 		DED62ABB0AE2EDF1001E80A4 /* Decl.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DED62ABA0AE2EDF1001E80A4 /* Decl.cpp */; };
 		DED676D10B6C786700AAD4A3 /* Builtins.def in CopyFiles */ = {isa = PBXBuildFile; fileRef = DED676D00B6C786700AAD4A3 /* Builtins.def */; };
@@ -419,6 +420,7 @@
 		DEC8D9900A9433CD00353FCA /* Decl.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; name = Decl.h; path = clang/AST/Decl.h; sourceTree = "<group>"; };
 		DEC8D9A30A94346E00353FCA /* AST.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; name = AST.h; path = clang/AST/AST.h; sourceTree = "<group>"; };
 		DECAB0940DA684C500E13CCB /* CGObjCEtoile.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = CGObjCEtoile.cpp; path = lib/CodeGen/CGObjCEtoile.cpp; sourceTree = "<group>"; };
+		DECAB0CF0DB3C84200E13CCB /* RewriteRope.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = RewriteRope.cpp; path = lib/Rewrite/RewriteRope.cpp; sourceTree = "<group>"; };
 		DED626C80AE0C065001E80A4 /* TargetInfo.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = TargetInfo.cpp; sourceTree = "<group>"; };
 		DED62ABA0AE2EDF1001E80A4 /* Decl.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 2; lastKnownFileType = sourcecode.cpp.cpp; name = Decl.cpp; path = lib/AST/Decl.cpp; sourceTree = "<group>"; tabWidth = 8; usesTabs = 0; };
 		DED676D00B6C786700AAD4A3 /* Builtins.def */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = text; name = Builtins.def; path = clang/AST/Builtins.def; sourceTree = "<group>"; };
@@ -907,6 +909,7 @@
 				DEFFECA60DB1546600B4E7C3 /* DeltaTree.cpp */,
 				72D16C1E0D9975C400E6DA4A /* HTMLRewrite.cpp */,
 				DEF7D9F80C9C8B1D0001F598 /* Rewriter.cpp */,
+				DECAB0CF0DB3C84200E13CCB /* RewriteRope.cpp */,
 			);
 			name = Rewrite;
 			sourceTree = "<group>";
@@ -1065,6 +1068,7 @@
 				35EF67700DAD1D2C00B19414 /* SemaDeclCXX.cpp in Sources */,
 				352712510DAFE54700C76352 /* IdentifierResolver.cpp in Sources */,
 				DEFFECA70DB1546600B4E7C3 /* DeltaTree.cpp in Sources */,
+				DECAB0D00DB3C84200E13CCB /* RewriteRope.cpp in Sources */,
 			);
 			runOnlyForDeploymentPostprocessing = 0;
 		};
diff --git a/include/clang/Rewrite/RewriteRope.h b/include/clang/Rewrite/RewriteRope.h
index 951a06367d..899fc6d029 100644
--- a/include/clang/Rewrite/RewriteRope.h
+++ b/include/clang/Rewrite/RewriteRope.h
@@ -15,722 +15,148 @@
 #define LLVM_CLANG_REWRITEROPE_H
 
 #include "llvm/ADT/iterator"
-#include <list>
 #include <cstring>
 
-#include "llvm/Support/Casting.h"
-
 namespace clang {
-
-struct RopeRefCountString {
-  unsigned RefCount;
-  char Data[1];  //  Variable sized.
-  
-  void addRef() {
-    if (this) ++RefCount;
-  }
-  
-  void dropRef() {
-    if (this && --RefCount == 0)
-      delete [] (char*)this;
-  }
-};
-  
-struct RopePiece {
-  RopeRefCountString *StrData;
-  unsigned StartOffs;
-  unsigned EndOffs;
+  //===--------------------------------------------------------------------===//
+  // RopeRefCountString Class
+  //===--------------------------------------------------------------------===//
+  
+  /// RopeRefCountString
+  struct RopeRefCountString {
+    unsigned RefCount;
+    char Data[1];  //  Variable sized.
+    
+    void addRef() {
+      if (this) ++RefCount;
+    }
+    
+    void dropRef() {
+      if (this && --RefCount == 0)
+        delete [] (char*)this;
+    }
+  };
   
-  RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {}
+  //===--------------------------------------------------------------------===//
+  // RopePiece Class
+  //===--------------------------------------------------------------------===//
   
-  RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End)
+  struct RopePiece {
+    RopeRefCountString *StrData;
+    unsigned StartOffs;
+    unsigned EndOffs;
+    
+    RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {}
+    
+    RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End)
     : StrData(Str), StartOffs(Start), EndOffs(End) {
-    StrData->addRef();
-  }
-  RopePiece(const RopePiece &RP)
-    : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) {
-    StrData->addRef();
-  }
-
-  ~RopePiece() {
-    StrData->dropRef();
-  }
-  
-  void operator=(const RopePiece &RHS) {
-    if (StrData != RHS.StrData) {
-      StrData->dropRef();
-      StrData = RHS.StrData;
       StrData->addRef();
     }
-    StartOffs = RHS.StartOffs;
-    EndOffs = RHS.EndOffs;
-  }
-  
-  const char &operator[](unsigned Offset) const {
-    return StrData->Data[Offset+StartOffs];
-  }
-  char &operator[](unsigned Offset) {
-    return StrData->Data[Offset+StartOffs];
-  }
-  
-  unsigned size() const { return EndOffs-StartOffs; }
-};
-  
-  
-  
-  using llvm::dyn_cast;
-  using llvm::cast;
-
-/// This is an adapted B+ Tree, ... erases don't keep the tree balanced.
-  
-class RopePieceBTreeNode;
-struct InsertResult {
-  RopePieceBTreeNode *LHS, *RHS;
-};
-  
-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) : 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.  This
-  /// returns true if the insertion could not be done in place, and returns
-  /// information in 'Res' about the piece that is percolated up.
-  bool split(unsigned Offset, InsertResult *Res);
-  
-  /// 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.  This returns true if the insertion could not be done in place, and
-  /// returns information in 'Res' about the piece that is percolated up.
-  bool insert(unsigned Offset, const RopePiece &R, InsertResult *Res);
-
-  /// 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; }
-
-};
-  
-  
-
-  
-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.
-  const RopePieceBTreeLeaf *NextLeaf;
-public:
-  RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NextLeaf(0) {}
- 
-  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 setNextLeafInOrder(const RopePieceBTreeLeaf *NL) { NextLeaf = NL; }
-  
-  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.  This
-  /// returns true if the insertion could not be done in place, and returns
-  /// information in 'Res' about the piece that is percolated up.
-  bool split(unsigned Offset, InsertResult *Res);
-  
-  /// 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.  This returns true if the insertion could not be done in place, and
-  /// returns information in 'Res' about the piece that is percolated up.
-  bool insert(unsigned Offset, const RopePiece &R, InsertResult *Res);
-  
-  
-  /// 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();
-  }
-};
-
-/// 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.  This
-/// returns true if the insertion could not be done in place, and returns
-/// information in 'Res' about the piece that is percolated up.
-inline bool RopePieceBTreeLeaf::split(unsigned Offset, InsertResult *Res) {
-  // 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 false;
-  }
-  
-  // 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 false;
-  
-  // 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, Res);
-}
-  
-  
-/// 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.  This returns true if the insertion could not be done in place, and
-/// returns information in 'Res' about the piece that is percolated up.
-inline bool RopePieceBTreeLeaf::insert(unsigned Offset, const RopePiece &R,
-                                       InsertResult *Res) {
-  // 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!");
+    RopePiece(const RopePiece &RP)
+    : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) {
+      StrData->addRef();
     }
     
-    // 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 false;
-  }
-  
-  // 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->setNextLeafInOrder(this->getNextLeafInOrder());
-  this->setNextLeafInOrder(NewNode);
-  
-  assert(Res && "No result location specified");
-  Res->LHS = this;
-  Res->RHS = NewNode;
-  
-  if (this->size() >= Offset)
-    this->insert(Offset, R, 0 /*can't fail*/);
-  else
-    NewNode->insert(Offset - this->size(), R, 0 /*can't fail*/);
-  return true;
-}
-  
-/// erase - Remove NumBytes from this node at the specified offset.  We are
-/// guaranteed that there is a split at Offset.
-inline 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;
+    ~RopePiece() {
+      StrData->dropRef();
+    }
     
-    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;
-}
-  
-// Holds up to 2*WidthFactor children.
-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) {}
-
-  RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
-    : RopePieceBTreeNode(false) {
-    Children[0] = LHS;
-    Children[1] = RHS;
-    NumChildren = 2;
-    Size = LHS->size() + RHS->size();
-  }
-
-  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];
-  }
-  
-  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.  This
-  /// returns true if the insertion could not be done in place, and returns
-  /// information in 'Res' about the piece that is percolated up.
-  bool split(unsigned Offset, InsertResult *Res);
-  
-  
-  /// 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.  This returns true if the insertion could not be done in place, and
-  /// returns information in 'Res' about the piece that is percolated up.
-  bool insert(unsigned Offset, const RopePiece &R, InsertResult *Res);
-  
-  /// HandleChildPiece - A child propagated an insertion result up to us.
-  /// Insert the new child, and/or propagate the result further up the tree.
-  bool HandleChildPiece(unsigned i, InsertResult &Res);
-  
-  /// 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(); 
-  }
-};
-  
-/// 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.  This
-/// returns true if the insertion could not be done in place, and returns
-/// information in 'Res' about the piece that is percolated up.
-inline bool RopePieceBTreeInterior::split(unsigned Offset, InsertResult *Res) {
-  // Figure out which child to split.
-  if (Offset == 0 || Offset == size())
-    return false;  // 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 false;
-  
-  // Otherwise, recursively split the child.
-  if (getChild(i)->split(Offset-ChildOffset, Res)) 
-    return HandleChildPiece(i, *Res);
-  return false;  // 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.  This returns true if the insertion could not be done in place, and
-/// returns information in 'Res' about the piece that is percolated up.
-inline bool RopePieceBTreeInterior::insert(unsigned Offset, const RopePiece &R,
-                                           InsertResult *Res) {
-  // 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 (getChild(i)->insert(Offset-ChildOffs, R, Res))
-    return HandleChildPiece(i, *Res);
-  
-  return false;
-}
-  
-/// HandleChildPiece - A child propagated an insertion result up to us.
-/// Insert the new child, and/or propagate the result further up the tree.
-inline bool RopePieceBTreeInterior::HandleChildPiece(unsigned i, 
-                                                     InsertResult &Res) {
-  // Otherwise the child propagated a subtree up to us as a new child.  See if
-  // we have space for it here.
-  if (!isFull()) {
-    // Replace child 'i' with the two children specified in Res.
-    if (i + 1 != getNumChildren())
-      memmove(&Children[i+2], &Children[i+1],
-              (getNumChildren()-i-1)*sizeof(Children[0]));
-    Children[i] = Res.LHS;
-    Children[i+1] = Res.RHS;
-    ++NumChildren;
-    return false;
-  }
-  
-  // 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.
-  if (i < WidthFactor)
-    this->HandleChildPiece(i, Res);
-  else
-    NewNode->HandleChildPiece(i-WidthFactor, Res);
-  
-  // Recompute the two nodes' size.
-  NewNode->FullRecomputeSizeLocally();
-  FullRecomputeSizeLocally();
-  
-  Res.LHS = this;
-  Res.RHS = NewNode;
-  return true;
-}
-
-/// erase - Remove NumBytes from this node at the specified offset.  We are
-/// guaranteed that there is a split at Offset.
-inline 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;
+    void operator=(const RopePiece &RHS) {
+      if (StrData != RHS.StrData) {
+        StrData->dropRef();
+        StrData = RHS.StrData;
+        StrData->addRef();
+      }
+      StartOffs = RHS.StartOffs;
+      EndOffs = RHS.EndOffs;
     }
     
-    // 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;
-      ++i;
-      continue;
+    const char &operator[](unsigned Offset) const {
+      return StrData->Data[Offset+StartOffs];
+    }
+    char &operator[](unsigned Offset) {
+      return StrData->Data[Offset+StartOffs];
     }
     
-    // If the deletion request completely covers the child, delete it and move
-    // the rest down.
-    NumBytes -= CurChild->size();
-    CurChild->Destroy();
-    --NumChildren;
-    if (i+1 != getNumChildren())
-      memmove(&Children[i], &Children[i+1],
-              (getNumChildren()-i)*sizeof(Children[0]));
-  }
-}
-  
-inline 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.  This
-/// returns true if the insertion could not be done in place, and returns
-/// information in 'Res' about the piece that is percolated up.
-inline bool RopePieceBTreeNode::split(unsigned Offset, InsertResult *Res) {
-  assert(Offset <= size() && "Invalid offset to split!");
-  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
-    return Leaf->split(Offset, Res);
-  return cast<RopePieceBTreeInterior>(this)->split(Offset, Res);
-}
-  
-/// 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.
-inline bool RopePieceBTreeNode::insert(unsigned Offset, const RopePiece &R,
-                                       InsertResult *Res) {
-  assert(Offset <= size() && "Invalid offset to insert!");
-  if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
-    return Leaf->insert(Offset, R, Res);
-  return cast<RopePieceBTreeInterior>(this)->insert(Offset, R, Res);
-}
-  
-/// erase - Remove NumBytes from this node at the specified offset.  We are
-/// guaranteed that there is a split at Offset.
-inline 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);
-}
-  
-  
-  
-/// RewritePieceBTreeIterator - Provide read-only forward iteration.
-class RewritePieceBTreeIterator :
-    public forward_iterator<const char, ptrdiff_t> {
-  /// CurNode - The current B+Tree node that we are inspecting.
-  const RopePieceBTreeLeaf *CurNode;
-  /// CurPiece - The current RopePiece in the B+Tree node that we're inspecting.
-  const RopePiece *CurPiece;
-  /// CurChar - The current byte in the RopePiece we are pointing to.
-  unsigned CurChar;
-  friend class RewriteRope;
-public:
-  RewritePieceBTreeIterator(const RopePieceBTreeNode *N) {  // begin iterator.
-    // 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);
+    unsigned size() const { return EndOffs-StartOffs; }
+  };
+  
+  //===--------------------------------------------------------------------===//
+  // RopePieceBTreeIterator Class
+  //===--------------------------------------------------------------------===//
+  
+  /// RopePieceBTreeIterator - Provide read-only forward iteration.
+  class RopePieceBTreeIterator :
+      public forward_iterator<const char, ptrdiff_t> {
+    /// CurNode - The current B+Tree node that we are inspecting.
+    const void /*RopePieceBTreeLeaf*/ *CurNode;
+    /// CurPiece - The current RopePiece in the B+Tree node that we're
+    /// inspecting.
+    const RopePiece *CurPiece;
+    /// CurChar - The current byte in the RopePiece we are pointing to.
+    unsigned CurChar;
+    friend class RewriteRope;
+  public:
+    // begin iterator.
+    RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
+    // end iterator
+    RopePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {}
     
-    // We must have at least one leaf.
-    CurNode = cast<RopePieceBTreeLeaf>(N);
+    const char operator*() const {
+      return (*CurPiece)[CurChar];
+    }
     
-    // If we found a leaf that happens to be empty, skip over it until we get to
-    // something full.
-    while (CurNode && CurNode->getNumPieces() == 0)
-      CurNode = CurNode->getNextLeafInOrder();
-      
-    if (CurNode != 0)
-      CurPiece = &CurNode->getPiece(0);
-    else  // Empty tree, this is an end() iterator.
-      CurPiece = 0;
-    CurChar = 0;
-  }
-  // end iterator
-  RewritePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {}
-  
-  const char operator*() const {
-    return (*CurPiece)[CurChar];
-  }
-  
-  bool operator==(const RewritePieceBTreeIterator &RHS) const {
-    return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
-  }
-  bool operator!=(const RewritePieceBTreeIterator &RHS) const {
-    return !operator==(RHS);
-  }
-  
-  inline RewritePieceBTreeIterator& operator++() {   // Preincrement
-    if (CurChar+1 < CurPiece->size())
-      ++CurChar;
-    else if (CurPiece != &CurNode->getPiece(CurNode->getNumPieces()-1)) {
-      CurChar = 0;
-      ++CurPiece;
-    } else {
-      // Find the next non-empty leaf node.
-      do
-        CurNode = CurNode->getNextLeafInOrder();
-      while (CurNode && CurNode->getNumPieces() == 0);
-
-      if (CurNode != 0)
-        CurPiece = &CurNode->getPiece(0);
-      else // Hit end().
-        CurPiece = 0;
-      CurChar = 0;
+    bool operator==(const RopePieceBTreeIterator &RHS) const {
+      return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
     }
-    return *this;
-  }
-  
-  inline RewritePieceBTreeIterator operator++(int) { // Postincrement
-    RewritePieceBTreeIterator tmp = *this; ++*this; return tmp;
-  }
-};
-  
-  
-class RopePieceBTree {
-  RopePieceBTreeNode *Root;
-  void operator=(const RopePieceBTree &); // DO NOT IMPLEMENT
-public:
-  RopePieceBTree() {
-    Root = new RopePieceBTreeLeaf();
-  }
-  RopePieceBTree(const RopePieceBTree &RHS) {
-    assert(RHS.empty() && "Can't copy non-empty tree yet");
-    Root = new RopePieceBTreeLeaf();
-  }
-  ~RopePieceBTree() {
-    Root->Destroy();
-  }
-  
-  typedef RewritePieceBTreeIterator iterator;
-  iterator begin() const { return iterator(Root); }
-  iterator end() const { return iterator(); }
-  unsigned size() const { return Root->size(); }
-  unsigned empty() const { return size() == 0; }
-  
-  void clear() {
-    if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(Root))
-      Leaf->clear();
-    else {
-      Root->Destroy();
-      Root = new RopePieceBTreeLeaf();
+    bool operator!=(const RopePieceBTreeIterator &RHS) const {
+      return !operator==(RHS);
     }
-  }
-  
-  void insert(unsigned Offset, const RopePiece &R) {
-    InsertResult Result;
-    // #1. Split at Offset.
-    if (Root->split(Offset, &Result))
-      Root = new RopePieceBTreeInterior(Result.LHS, Result.RHS);
     
-    // #2. Do the insertion.
-    if (Root->insert(Offset, R, &Result))
-      Root = new RopePieceBTreeInterior(Result.LHS, Result.RHS);
-  }
-
-  void erase(unsigned Offset, unsigned NumBytes) {
-    InsertResult Result;
-    // #1. Split at Offset.
-    if (Root->split(Offset, &Result))
-      Root = new RopePieceBTreeInterior(Result.LHS, Result.RHS);
+    RopePieceBTreeIterator& operator++() {   // Preincrement
+      if (CurChar+1 < CurPiece->size())
+        ++CurChar;
+      else
+        MoveToNextPiece();
+      return *this;
+    }
+        
+    inline RopePieceBTreeIterator operator++(int) { // Postincrement
+      RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
+    }
+        
+  private:
+    void MoveToNextPiece();
+  };
+  
+  //===--------------------------------------------------------------------===//
+  // RopePieceBTree Class
+  //===--------------------------------------------------------------------===//
+  
+  class RopePieceBTree {
+    void /*RopePieceBTreeNode*/ *Root;
+    void operator=(const RopePieceBTree &); // DO NOT IMPLEMENT
+  public:
+    RopePieceBTree();
+    RopePieceBTree(const RopePieceBTree &RHS);
+    ~RopePieceBTree();
     
-    // #2. Do the erasing.
-    Root->erase(Offset, NumBytes);
-  }
-};
+    typedef RopePieceBTreeIterator iterator;
+    iterator begin() const { return iterator(Root); }
+    iterator end() const { return iterator(); }
+    unsigned size() const;
+    unsigned empty() const { return size() == 0; }
+    
+    void clear();
+    
+    void insert(unsigned Offset, const RopePiece &R);
+
+    void erase(unsigned Offset, unsigned NumBytes);
+  };
 
+  //===--------------------------------------------------------------------===//
+  // RewriteRope Class
+  //===--------------------------------------------------------------------===//
   
 /// RewriteRope - A powerful string class, todo generalize this.
 class RewriteRope {
diff --git a/lib/Rewrite/RewriteRope.cpp b/lib/Rewrite/RewriteRope.cpp
new file mode 100644
index 0000000000..9b092be0cc
--- /dev/null
+++ b/lib/Rewrite/RewriteRope.cpp
@@ -0,0 +1,672 @@
+//===--- 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"
+using namespace clang;
+using llvm::dyn_cast;
+using llvm::cast;
+
+
+//===----------------------------------------------------------------------===//
+// InsertResult Class
+//===----------------------------------------------------------------------===//
+
+/// This is an adapted B+ Tree, ... erases don't keep the tree balanced.
+
+namespace {
+  class RopePieceBTreeNode;
+  struct InsertResult {
+    RopePieceBTreeNode *LHS, *RHS;
+  };
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// RopePieceBTreeNode Class
+//===----------------------------------------------------------------------===//
+
+namespace {
+  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) : 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.  This
+    /// returns true if the insertion could not be done in place, and returns
+    /// information in 'Res' about the piece that is percolated up.
+    bool split(unsigned Offset, InsertResult *Res);
+    
+    /// insert - Insert the specified ropepiece into this tree node at the
+    /// specified offset.  The of