Home | History | Annotate | Download | only in Core
      1 //===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the DeltaTree and related classes.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "clang/Rewrite/Core/DeltaTree.h"
     15 #include "clang/Basic/LLVM.h"
     16 #include <cstdio>
     17 #include <cstring>
     18 using namespace clang;
     19 
     20 /// The DeltaTree class is a multiway search tree (BTree) structure with some
     21 /// fancy features.  B-Trees are generally more memory and cache efficient
     22 /// than binary trees, because they store multiple keys/values in each node.
     23 ///
     24 /// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
     25 /// fast lookup by FileIndex.  However, an added (important) bonus is that it
     26 /// can also efficiently tell us the full accumulated delta for a specific
     27 /// file offset as well, without traversing the whole tree.
     28 ///
     29 /// The nodes of the tree are made up of instances of two classes:
     30 /// DeltaTreeNode and DeltaTreeInteriorNode.  The later subclasses the
     31 /// former and adds children pointers.  Each node knows the full delta of all
     32 /// entries (recursively) contained inside of it, which allows us to get the
     33 /// full delta implied by a whole subtree in constant time.
     34 
     35 namespace {
     36   /// SourceDelta - As code in the original input buffer is added and deleted,
     37   /// SourceDelta records are used to keep track of how the input SourceLocation
     38   /// object is mapped into the output buffer.
     39   struct SourceDelta {
     40     unsigned FileLoc;
     41     int Delta;
     42 
     43     static SourceDelta get(unsigned Loc, int D) {
     44       SourceDelta Delta;
     45       Delta.FileLoc = Loc;
     46       Delta.Delta = D;
     47       return Delta;
     48     }
     49   };
     50 
     51   /// DeltaTreeNode - The common part of all nodes.
     52   ///
     53   class DeltaTreeNode {
     54   public:
     55     struct InsertResult {
     56       DeltaTreeNode *LHS, *RHS;
     57       SourceDelta Split;
     58     };
     59 
     60   private:
     61     friend class DeltaTreeInteriorNode;
     62 
     63     /// WidthFactor - This controls the number of K/V slots held in the BTree:
     64     /// how wide it is.  Each level of the BTree is guaranteed to have at least
     65     /// WidthFactor-1 K/V pairs (except the root) and may have at most
     66     /// 2*WidthFactor-1 K/V pairs.
     67     enum { WidthFactor = 8 };
     68 
     69     /// Values - This tracks the SourceDelta's currently in this node.
     70     ///
     71     SourceDelta Values[2*WidthFactor-1];
     72 
     73     /// NumValuesUsed - This tracks the number of values this node currently
     74     /// holds.
     75     unsigned char NumValuesUsed;
     76 
     77     /// IsLeaf - This is true if this is a leaf of the btree.  If false, this is
     78     /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
     79     bool IsLeaf;
     80 
     81     /// FullDelta - This is the full delta of all the values in this node and
     82     /// all children nodes.
     83     int FullDelta;
     84   public:
     85     DeltaTreeNode(bool isLeaf = true)
     86       : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {}
     87 
     88     bool isLeaf() const { return IsLeaf; }
     89     int getFullDelta() const { return FullDelta; }
     90     bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
     91 
     92     unsigned getNumValuesUsed() const { return NumValuesUsed; }
     93     const SourceDelta &getValue(unsigned i) const {
     94       assert(i < NumValuesUsed && "Invalid value #");
     95       return Values[i];
     96     }
     97     SourceDelta &getValue(unsigned i) {
     98       assert(i < NumValuesUsed && "Invalid value #");
     99       return Values[i];
    100     }
    101 
    102     /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
    103     /// this node.  If insertion is easy, do it and return false.  Otherwise,
    104     /// split the node, populate InsertRes with info about the split, and return
    105     /// true.
    106     bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
    107 
    108     void DoSplit(InsertResult &InsertRes);
    109 
    110 
    111     /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
    112     /// local walk over our contained deltas.
    113     void RecomputeFullDeltaLocally();
    114 
    115     void Destroy();
    116   };
    117 } // end anonymous namespace
    118 
    119 namespace {
    120   /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
    121   /// This class tracks them.
    122   class DeltaTreeInteriorNode : public DeltaTreeNode {
    123     DeltaTreeNode *Children[2*WidthFactor];
    124     ~DeltaTreeInteriorNode() {
    125       for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
    126         Children[i]->Destroy();
    127     }
    128     friend class DeltaTreeNode;
    129   public:
    130     DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
    131 
    132     DeltaTreeInteriorNode(const InsertResult &IR)
    133       : DeltaTreeNode(false /*nonleaf*/) {
    134       Children[0] = IR.LHS;
    135       Children[1] = IR.RHS;
    136       Values[0] = IR.Split;
    137       FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
    138       NumValuesUsed = 1;
    139     }
    140 
    141     const DeltaTreeNode *getChild(unsigned i) const {
    142       assert(i < getNumValuesUsed()+1 && "Invalid child");
    143       return Children[i];
    144     }
    145     DeltaTreeNode *getChild(unsigned i) {
    146       assert(i < getNumValuesUsed()+1 && "Invalid child");
    147       return Children[i];
    148     }
    149 
    150     static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
    151   };
    152 }
    153 
    154 
    155 /// Destroy - A 'virtual' destructor.
    156 void DeltaTreeNode::Destroy() {
    157   if (isLeaf())
    158     delete this;
    159   else
    160     delete cast<DeltaTreeInteriorNode>(this);
    161 }
    162 
    163 /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
    164 /// local walk over our contained deltas.
    165 void DeltaTreeNode::RecomputeFullDeltaLocally() {
    166   int NewFullDelta = 0;
    167   for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
    168     NewFullDelta += Values[i].Delta;
    169   if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this))
    170     for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
    171       NewFullDelta += IN->getChild(i)->getFullDelta();
    172   FullDelta = NewFullDelta;
    173 }
    174 
    175 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
    176 /// this node.  If insertion is easy, do it and return false.  Otherwise,
    177 /// split the node, populate InsertRes with info about the split, and return
    178 /// true.
    179 bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
    180                                 InsertResult *InsertRes) {
    181   // Maintain full delta for this node.
    182   FullDelta += Delta;
    183 
    184   // Find the insertion point, the first delta whose index is >= FileIndex.
    185   unsigned i = 0, e = getNumValuesUsed();
    186   while (i != e && FileIndex > getValue(i).FileLoc)
    187     ++i;
    188 
    189   // If we found an a record for exactly this file index, just merge this
    190   // value into the pre-existing record and finish early.
    191   if (i != e && getValue(i).FileLoc == FileIndex) {
    192     // NOTE: Delta could drop to zero here.  This means that the delta entry is
    193     // useless and could be removed.  Supporting erases is more complex than
    194     // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
    195     // the tree.
    196     Values[i].Delta += Delta;
    197     return false;
    198   }
    199 
    200   // Otherwise, we found an insertion point, and we know that the value at the
    201   // specified index is > FileIndex.  Handle the leaf case first.
    202   if (isLeaf()) {
    203     if (!isFull()) {
    204       // For an insertion into a non-full leaf node, just insert the value in
    205       // its sorted position.  This requires moving later values over.
    206       if (i != e)
    207         memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
    208       Values[i] = SourceDelta::get(FileIndex, Delta);
    209       ++NumValuesUsed;
    210       return false;
    211     }
    212 
    213     // Otherwise, if this is leaf is full, split the node at its median, insert
    214     // the value into one of the children, and return the result.
    215     assert(InsertRes && "No result location specified");
    216     DoSplit(*InsertRes);
    217 
    218     if (InsertRes->Split.FileLoc > FileIndex)
    219       InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
    220     else
    221       InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
    222     return true;
    223   }
    224 
    225   // Otherwise, this is an interior node.  Send the request down the tree.
    226   DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
    227   if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
    228     return false; // If there was space in the child, just return.
    229 
    230   // Okay, this split the subtree, producing a new value and two children to
    231   // insert here.  If this node is non-full, we can just insert it directly.
    232   if (!isFull()) {
    233     // Now that we have two nodes and a new element, insert the perclated value
    234     // into ourself by moving all the later values/children down, then inserting
    235     // the new one.
    236     if (i != e)
    237       memmove(&IN->Children[i+2], &IN->Children[i+1],
    238               (e-i)*sizeof(IN->Children[0]));
    239     IN->Children[i] = InsertRes->LHS;
    240     IN->Children[i+1] = InsertRes->RHS;
    241 
    242     if (e != i)
    243       memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
    244     Values[i] = InsertRes->Split;
    245     ++NumValuesUsed;
    246     return false;
    247   }
    248 
    249   // Finally, if this interior node was full and a node is percolated up, split
    250   // ourself and return that up the chain.  Start by saving all our info to
    251   // avoid having the split clobber it.
    252   IN->Children[i] = InsertRes->LHS;
    253   DeltaTreeNode *SubRHS = InsertRes->RHS;
    254   SourceDelta SubSplit = InsertRes->Split;
    255 
    256   // Do the split.
    257   DoSplit(*InsertRes);
    258 
    259   // Figure out where to insert SubRHS/NewSplit.
    260   DeltaTreeInteriorNode *InsertSide;
    261   if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
    262     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
    263   else
    264     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
    265 
    266   // We now have a non-empty interior node 'InsertSide' to insert
    267   // SubRHS/SubSplit into.  Find out where to insert SubSplit.
    268 
    269   // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
    270   i = 0; e = InsertSide->getNumValuesUsed();
    271   while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
    272     ++i;
    273 
    274   // Now we know that i is the place to insert the split value into.  Insert it
    275   // and the child right after it.
    276   if (i != e)
    277     memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
    278             (e-i)*sizeof(IN->Children[0]));
    279   InsertSide->Children[i+1] = SubRHS;
    280 
    281   if (e != i)
    282     memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
    283             (e-i)*sizeof(Values[0]));
    284   InsertSide->Values[i] = SubSplit;
    285   ++InsertSide->NumValuesUsed;
    286   InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
    287   return true;
    288 }
    289 
    290 /// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
    291 /// into two subtrees each with "WidthFactor-1" values and a pivot value.
    292 /// Return the pieces in InsertRes.
    293 void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
    294   assert(isFull() && "Why split a non-full node?");
    295 
    296   // Since this node is full, it contains 2*WidthFactor-1 values.  We move
    297   // the first 'WidthFactor-1' values to the LHS child (which we leave in this
    298   // node), propagate one value up, and move the last 'WidthFactor-1' values
    299   // into the RHS child.
    300 
    301   // Create the new child node.
    302   DeltaTreeNode *NewNode;
    303   if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
    304     // If this is an interior node, also move over 'WidthFactor' children
    305     // into the new node.
    306     DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
    307     memcpy(&New->Children[0], &IN->Children[WidthFactor],
    308            WidthFactor*sizeof(IN->Children[0]));
    309     NewNode = New;
    310   } else {
    311     // Just create the new leaf node.
    312     NewNode = new DeltaTreeNode();
    313   }
    314 
    315   // Move over the last 'WidthFactor-1' values from here to NewNode.
    316   memcpy(&NewNode->Values[0], &Values[WidthFactor],
    317          (WidthFactor-1)*sizeof(Values[0]));
    318 
    319   // Decrease the number of values in the two nodes.
    320   NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
    321 
    322   // Recompute the two nodes' full delta.
    323   NewNode->RecomputeFullDeltaLocally();
    324   RecomputeFullDeltaLocally();
    325 
    326   InsertRes.LHS = this;
    327   InsertRes.RHS = NewNode;
    328   InsertRes.Split = Values[WidthFactor-1];
    329 }
    330 
    331 
    332 
    333 //===----------------------------------------------------------------------===//
    334 //                        DeltaTree Implementation
    335 //===----------------------------------------------------------------------===//
    336 
    337 //#define VERIFY_TREE
    338 
    339 #ifdef VERIFY_TREE
    340 /// VerifyTree - Walk the btree performing assertions on various properties to
    341 /// verify consistency.  This is useful for debugging new changes to the tree.
    342 static void VerifyTree(const DeltaTreeNode *N) {
    343   const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N);
    344   if (IN == 0) {
    345     // Verify leaves, just ensure that FullDelta matches up and the elements
    346     // are in proper order.
    347     int FullDelta = 0;
    348     for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
    349       if (i)
    350         assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
    351       FullDelta += N->getValue(i).Delta;
    352     }
    353     assert(FullDelta == N->getFullDelta());
    354     return;
    355   }
    356 
    357   // Verify interior nodes: Ensure that FullDelta matches up and the
    358   // elements are in proper order and the children are in proper order.
    359   int FullDelta = 0;
    360   for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
    361     const SourceDelta &IVal = N->getValue(i);
    362     const DeltaTreeNode *IChild = IN->getChild(i);
    363     if (i)
    364       assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
    365     FullDelta += IVal.Delta;
    366     FullDelta += IChild->getFullDelta();
    367 
    368     // The largest value in child #i should be smaller than FileLoc.
    369     assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
    370            IVal.FileLoc);
    371 
    372     // The smallest value in child #i+1 should be larger than FileLoc.
    373     assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
    374     VerifyTree(IChild);
    375   }
    376 
    377   FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
    378 
    379   assert(FullDelta == N->getFullDelta());
    380 }
    381 #endif  // VERIFY_TREE
    382 
    383 static DeltaTreeNode *getRoot(void *Root) {
    384   return (DeltaTreeNode*)Root;
    385 }
    386 
    387 DeltaTree::DeltaTree() {
    388   Root = new DeltaTreeNode();
    389 }
    390 DeltaTree::DeltaTree(const DeltaTree &RHS) {
    391   // Currently we only support copying when the RHS is empty.
    392   assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
    393          "Can only copy empty tree");
    394   Root = new DeltaTreeNode();
    395 }
    396 
    397 DeltaTree::~DeltaTree() {
    398   getRoot(Root)->Destroy();
    399 }
    400 
    401 /// getDeltaAt - Return the accumulated delta at the specified file offset.
    402 /// This includes all insertions or delections that occurred *before* the
    403 /// specified file index.
    404 int DeltaTree::getDeltaAt(unsigned FileIndex) const {
    405   const DeltaTreeNode *Node = getRoot(Root);
    406 
    407   int Result = 0;
    408 
    409   // Walk down the tree.
    410   while (1) {
    411     // For all nodes, include any local deltas before the specified file
    412     // index by summing them up directly.  Keep track of how many were
    413     // included.
    414     unsigned NumValsGreater = 0;
    415     for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
    416          ++NumValsGreater) {
    417       const SourceDelta &Val = Node->getValue(NumValsGreater);
    418 
    419       if (Val.FileLoc >= FileIndex)
    420         break;
    421       Result += Val.Delta;
    422     }
    423 
    424     // If we have an interior node, include information about children and
    425     // recurse.  Otherwise, if we have a leaf, we're done.
    426     const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
    427     if (!IN) return Result;
    428 
    429     // Include any children to the left of the values we skipped, all of
    430     // their deltas should be included as well.
    431     for (unsigned i = 0; i != NumValsGreater; ++i)
    432       Result += IN->getChild(i)->getFullDelta();
    433 
    434     // If we found exactly the value we were looking for, break off the
    435     // search early.  There is no need to search the RHS of the value for
    436     // partial results.
    437     if (NumValsGreater != Node->getNumValuesUsed() &&
    438         Node->getValue(NumValsGreater).FileLoc == FileIndex)
    439       return Result+IN->getChild(NumValsGreater)->getFullDelta();
    440 
    441     // Otherwise, traverse down the tree.  The selected subtree may be
    442     // partially included in the range.
    443     Node = IN->getChild(NumValsGreater);
    444   }
    445   // NOT REACHED.
    446 }
    447 
    448 /// AddDelta - When a change is made that shifts around the text buffer,
    449 /// this method is used to record that info.  It inserts a delta of 'Delta'
    450 /// into the current DeltaTree at offset FileIndex.
    451 void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
    452   assert(Delta && "Adding a noop?");
    453   DeltaTreeNode *MyRoot = getRoot(Root);
    454 
    455   DeltaTreeNode::InsertResult InsertRes;
    456   if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
    457     Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
    458   }
    459 
    460 #ifdef VERIFY_TREE
    461   VerifyTree(MyRoot);
    462 #endif
    463 }
    464 
    465