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

1 files changed, 467 insertions, 0 deletions

diff --git a/clang/lib/Rewrite/DeltaTree.cpp b/clang/lib/Rewrite/DeltaTree.cpp
new file mode 100644
index 0000000..4297dc8
--- /dev/null
+++ b/clang/lib/Rewrite/DeltaTree.cpp
@@ -0,0 +1,467 @@
+//===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===//
+//
+//                     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 DeltaTree and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Rewrite/DeltaTree.h"
+#include "clang/Basic/LLVM.h"
+#include <cstring>
+#include <cstdio>
+using namespace clang;
+
+/// The DeltaTree class is a multiway search tree (BTree) structure with some
+/// fancy features.  B-Trees are generally more memory and cache efficient
+/// than binary trees, because they store multiple keys/values in each node.
+///
+/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
+/// fast lookup by FileIndex.  However, an added (important) bonus is that it
+/// can also efficiently tell us the full accumulated delta for a specific
+/// file offset as well, without traversing the whole tree.
+///
+/// The nodes of the tree are made up of instances of two classes:
+/// DeltaTreeNode and DeltaTreeInteriorNode.  The later subclasses the
+/// former and adds children pointers.  Each node knows the full delta of all
+/// entries (recursively) contained inside of it, which allows us to get the
+/// full delta implied by a whole subtree in constant time.
+
+namespace {
+  /// SourceDelta - As code in the original input buffer is added and deleted,
+  /// SourceDelta records are used to keep track of how the input SourceLocation
+  /// object is mapped into the output buffer.
+  struct SourceDelta {
+    unsigned FileLoc;
+    int Delta;
+
+    static SourceDelta get(unsigned Loc, int D) {
+      SourceDelta Delta;
+      Delta.FileLoc = Loc;
+      Delta.Delta = D;
+      return Delta;
+    }
+  };
+  
+  /// DeltaTreeNode - The common part of all nodes.
+  ///
+  class DeltaTreeNode {
+  public:
+    struct InsertResult {
+      DeltaTreeNode *LHS, *RHS;
+      SourceDelta Split;
+    };
+    
+  private:
+    friend class DeltaTreeInteriorNode;
+
+    /// 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-1 K/V pairs (except the root) and may have at most
+    /// 2*WidthFactor-1 K/V pairs.
+    enum { WidthFactor = 8 };
+
+    /// Values - This tracks the SourceDelta's currently in this node.
+    ///
+    SourceDelta Values[2*WidthFactor-1];
+
+    /// NumValuesUsed - This tracks the number of values this node currently
+    /// holds.
+    unsigned char NumValuesUsed;
+
+    /// IsLeaf - This is true if this is a leaf of the btree.  If false, this is
+    /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
+    bool IsLeaf;
+
+    /// FullDelta - This is the full delta of all the values in this node and
+    /// all children nodes.
+    int FullDelta;
+  public:
+    DeltaTreeNode(bool isLeaf = true)
+      : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {}
+
+    bool isLeaf() const { return IsLeaf; }
+    int getFullDelta() const { return FullDelta; }
+    bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
+
+    unsigned getNumValuesUsed() const { return NumValuesUsed; }
+    const SourceDelta &getValue(unsigned i) const {
+      assert(i < NumValuesUsed && "Invalid value #");
+      return Values[i];
+    }
+    SourceDelta &getValue(unsigned i) {
+      assert(i < NumValuesUsed && "Invalid value #");
+      return Values[i];
+    }
+
+    /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
+    /// this node.  If insertion is easy, do it and return false.  Otherwise,
+    /// split the node, populate InsertRes with info about the split, and return
+    /// true.
+    bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
+
+    void DoSplit(InsertResult &InsertRes);
+
+
+    /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
+    /// local walk over our contained deltas.
+    void RecomputeFullDeltaLocally();
+
+    void Destroy();
+
+    //static inline bool classof(const DeltaTreeNode *) { return true; }
+  };
+} // end anonymous namespace
+
+namespace {
+  /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
+  /// This class tracks them.
+  class DeltaTreeInteriorNode : public DeltaTreeNode {
+    DeltaTreeNode *Children[2*WidthFactor];
+    ~DeltaTreeInteriorNode() {
+      for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
+        Children[i]->Destroy();
+    }
+    friend class DeltaTreeNode;
+  public:
+    DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
+
+    DeltaTreeInteriorNode(const InsertResult &IR)
+      : DeltaTreeNode(false /*nonleaf*/) {
+      Children[0] = IR.LHS;
+      Children[1] = IR.RHS;
+      Values[0] = IR.Split;
+      FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
+      NumValuesUsed = 1;
+    }
+
+    const DeltaTreeNode *getChild(unsigned i) const {
+      assert(i < getNumValuesUsed()+1 && "Invalid child");
+      return Children[i];
+    }
+    DeltaTreeNode *getChild(unsigned i) {
+      assert(i < getNumValuesUsed()+1 && "Invalid child");
+      return Children[i];
+    }
+
+  //static inline bool classof(const DeltaTreeInteriorNode *) { return true; }
+    static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
+  };
+}
+
+
+/// Destroy - A 'virtual' destructor.
+void DeltaTreeNode::Destroy() {
+  if (isLeaf())
+    delete this;
+  else
+    delete cast<DeltaTreeInteriorNode>(this);
+}
+
+/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
+/// local walk over our contained deltas.
+void DeltaTreeNode::RecomputeFullDeltaLocally() {
+  int NewFullDelta = 0;
+  for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
+    NewFullDelta += Values[i].Delta;
+  if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this))
+    for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
+      NewFullDelta += IN->getChild(i)->getFullDelta();
+  FullDelta = NewFullDelta;
+}
+
+/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
+/// this node.  If insertion is easy, do it and return false.  Otherwise,
+/// split the node, populate InsertRes with info about the split, and return
+/// true.
+bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
+                                InsertResult *InsertRes) {
+  // Maintain full delta for this node.
+  FullDelta += Delta;
+
+  // Find the insertion point, the first delta whose index is >= FileIndex.
+  unsigned i = 0, e = getNumValuesUsed();
+  while (i != e && FileIndex > getValue(i).FileLoc)
+    ++i;
+
+  // If we found an a record for exactly this file index, just merge this
+  // value into the pre-existing record and finish early.
+  if (i != e && getValue(i).FileLoc == FileIndex) {
+    // NOTE: Delta could drop to zero here.  This means that the delta entry is
+    // useless and could be removed.  Supporting erases is more complex than
+    // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
+    // the tree.
+    Values[i].Delta += Delta;
+    return false;
+  }
+
+  // Otherwise, we found an insertion point, and we know that the value at the
+  // specified index is > FileIndex.  Handle the leaf case first.
+  if (isLeaf()) {
+    if (!isFull()) {
+      // For an insertion into a non-full leaf node, just insert the value in
+      // its sorted position.  This requires moving later values over.
+      if (i != e)
+        memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
+      Values[i] = SourceDelta::get(FileIndex, Delta);
+      ++NumValuesUsed;
+      return false;
+    }
+
+    // Otherwise, if this is leaf is full, split the node at its median, insert
+    // the value into one of the children, and return the result.
+    assert(InsertRes && "No result location specified");
+    DoSplit(*InsertRes);
+
+    if (InsertRes->Split.FileLoc > FileIndex)
+      InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
+    else
+      InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
+    return true;
+  }
+
+  // Otherwise, this is an interior node.  Send the request down the tree.
+  DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
+  if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
+    return false; // If there was space in the child, just return.
+
+  // Okay, this split the subtree, producing a new value and two children to
+  // insert here.  If this node is non-full, we can just insert it directly.
+  if (!isFull()) {
+    // Now that we have two nodes and a new element, insert the perclated value
+    // into ourself by moving all the later values/children down, then inserting
+    // the new one.
+    if (i != e)
+      memmove(&IN->Children[i+2], &IN->Children[i+1],
+              (e-i)*sizeof(IN->Children[0]));
+    IN->Children[i] = InsertRes->LHS;
+    IN->Children[i+1] = InsertRes->RHS;
+
+    if (e != i)
+      memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
+    Values[i] = InsertRes->Split;
+    ++NumValuesUsed;
+    return false;
+  }
+
+  // Finally, if this interior node was full and a node is percolated up, split
+  // ourself and return that up the chain.  Start by saving all our info to
+  // avoid having the split clobber it.
+  IN->Children[i] = InsertRes->LHS;
+  DeltaTreeNode *SubRHS = InsertRes->RHS;
+  SourceDelta SubSplit = InsertRes->Split;
+
+  // Do the split.
+  DoSplit(*InsertRes);
+
+  // Figure out where to insert SubRHS/NewSplit.
+  DeltaTreeInteriorNode *InsertSide;
+  if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
+    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
+  else
+    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
+
+  // We now have a non-empty interior node 'InsertSide' to insert
+  // SubRHS/SubSplit into.  Find out where to insert SubSplit.
+
+  // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
+  i = 0; e = InsertSide->getNumValuesUsed();
+  while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
+    ++i;
+
+  // Now we know that i is the place to insert the split value into.  Insert it
+  // and the child right after it.
+  if (i != e)
+    memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
+            (e-i)*sizeof(IN->Children[0]));
+  InsertSide->Children[i+1] = SubRHS;
+
+  if (e != i)
+    memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
+            (e-i)*sizeof(Values[0]));
+  InsertSide->Values[i] = SubSplit;
+  ++InsertSide->NumValuesUsed;
+  InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
+  return true;
+}
+
+/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
+/// into two subtrees each with "WidthFactor-1" values and a pivot value.
+/// Return the pieces in InsertRes.
+void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
+  assert(isFull() && "Why split a non-full node?");
+
+  // Since this node is full, it contains 2*WidthFactor-1 values.  We move
+  // the first 'WidthFactor-1' values to the LHS child (which we leave in this
+  // node), propagate one value up, and move the last 'WidthFactor-1' values
+  // into the RHS child.
+
+  // Create the new child node.
+  DeltaTreeNode *NewNode;
+  if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
+    // If this is an interior node, also move over 'WidthFactor' children
+    // into the new node.
+    DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
+    memcpy(&New->Children[0], &IN->Children[WidthFactor],
+           WidthFactor*sizeof(IN->Children[0]));
+    NewNode = New;
+  } else {
+    // Just create the new leaf node.
+    NewNode = new DeltaTreeNode();
+  }
+
+  // Move over the last 'WidthFactor-1' values from here to NewNode.
+  memcpy(&NewNode->Values[0], &Values[WidthFactor],
+         (WidthFactor-1)*sizeof(Values[0]));
+
+  // Decrease the number of values in the two nodes.
+  NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
+
+  // Recompute the two nodes' full delta.
+  NewNode->RecomputeFullDeltaLocally();
+  RecomputeFullDeltaLocally();
+
+  InsertRes.LHS = this;
+  InsertRes.RHS = NewNode;
+  InsertRes.Split = Values[WidthFactor-1];
+}
+
+
+
+//===----------------------------------------------------------------------===//
+//                        DeltaTree Implementation
+//===----------------------------------------------------------------------===//
+
+//#define VERIFY_TREE
+
+#ifdef VERIFY_TREE
+/// VerifyTree - Walk the btree performing assertions on various properties to
+/// verify consistency.  This is useful for debugging new changes to the tree.
+static void VerifyTree(const DeltaTreeNode *N) {
+  const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N);
+  if (IN == 0) {
+    // Verify leaves, just ensure that FullDelta matches up and the elements
+    // are in proper order.
+    int FullDelta = 0;
+    for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
+      if (i)
+        assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
+      FullDelta += N->getValue(i).Delta;
+    }
+    assert(FullDelta == N->getFullDelta());
+    return;
+  }
+
+  // Verify interior nodes: Ensure that FullDelta matches up and the
+  // elements are in proper order and the children are in proper order.
+  int FullDelta = 0;
+  for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
+    const SourceDelta &IVal = N->getValue(i);
+    const DeltaTreeNode *IChild = IN->getChild(i);
+    if (i)
+      assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
+    FullDelta += IVal.Delta;
+    FullDelta += IChild->getFullDelta();
+
+    // The largest value in child #i should be smaller than FileLoc.
+    assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
+           IVal.FileLoc);
+
+    // The smallest value in child #i+1 should be larger than FileLoc.
+    assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
+    VerifyTree(IChild);
+  }
+
+  FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
+
+  assert(FullDelta == N->getFullDelta());
+}
+#endif  // VERIFY_TREE
+
+static DeltaTreeNode *getRoot(void *Root) {
+  return (DeltaTreeNode*)Root;
+}
+
+DeltaTree::DeltaTree() {
+  Root = new DeltaTreeNode();
+}
+DeltaTree::DeltaTree(const DeltaTree &RHS) {
+  // Currently we only support copying when the RHS is empty.
+  assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
+         "Can only copy empty tree");
+  Root = new DeltaTreeNode();
+}
+
+DeltaTree::~DeltaTree() {
+  getRoot(Root)->Destroy();
+}
+
+/// getDeltaAt - Return the accumulated delta at the specified file offset.
+/// This includes all insertions or delections that occurred *before* the
+/// specified file index.
+int DeltaTree::getDeltaAt(unsigned FileIndex) const {
+  const DeltaTreeNode *Node = getRoot(Root);
+
+  int Result = 0;
+
+  // Walk down the tree.
+  while (1) {
+    // For all nodes, include any local deltas before the specified file
+    // index by summing them up directly.  Keep track of how many were
+    // included.
+    unsigned NumValsGreater = 0;
+    for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
+         ++NumValsGreater) {
+      const SourceDelta &Val = Node->getValue(NumValsGreater);
+
+      if (Val.FileLoc >= FileIndex)
+        break;
+      Result += Val.Delta;
+    }
+
+    // If we have an interior node, include information about children and
+    // recurse.  Otherwise, if we have a leaf, we're done.
+    const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
+    if (!IN) return Result;
+
+    // Include any children to the left of the values we skipped, all of
+    // their deltas should be included as well.
+    for (unsigned i = 0; i != NumValsGreater; ++i)
+      Result += IN->getChild(i)->getFullDelta();
+
+    // If we found exactly the value we were looking for, break off the
+    // search early.  There is no need to search the RHS of the value for
+    // partial results.
+    if (NumValsGreater != Node->getNumValuesUsed() &&
+        Node->getValue(NumValsGreater).FileLoc == FileIndex)
+      return Result+IN->getChild(NumValsGreater)->getFullDelta();
+
+    // Otherwise, traverse down the tree.  The selected subtree may be
+    // partially included in the range.
+    Node = IN->getChild(NumValsGreater);
+  }
+  // NOT REACHED.
+}
+
+/// AddDelta - When a change is made that shifts around the text buffer,
+/// this method is used to record that info.  It inserts a delta of 'Delta'
+/// into the current DeltaTree at offset FileIndex.
+void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
+  assert(Delta && "Adding a noop?");
+  DeltaTreeNode *MyRoot = getRoot(Root);
+
+  DeltaTreeNode::InsertResult InsertRes;
+  if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
+    Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
+  }
+
+#ifdef VERIFY_TREE
+  VerifyTree(MyRoot);
+#endif
+}
+