Split library clangRewrite into clangRewriteCore and clangRewriteFrontend.

This is similar to how we divide up the StaticAnalyzer libraries to separate
core functionality to what is clearly associated with Frontend actions.

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

1 files changed, 467 insertions, 0 deletions

diff --git a/lib/Rewrite/Core/DeltaTree.cpp b/lib/Rewrite/Core/DeltaTree.cpp
new file mode 100644
index 0000000000..dff621d206
--- /dev/null
+++ b/lib/Rewrite/Core/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/Core/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
+}
+