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"
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 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; }
    
  };
} // end anonymous namespace

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

namespace {
  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();
    }
  };
} // 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.  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 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.
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!");
    }