contrib/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp

   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/DeltaTree.h"
  15 #include "clang/Basic/LLVM.h"
  16 #include <cstring>
  17 #include <cstdio>
  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     //static inline bool classof(const DeltaTreeNode *) { return true; }
 118   };
 119 } // end anonymous namespace
 120
 121 namespace {
 122   /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
 123   /// This class tracks them.
 124   class DeltaTreeInteriorNode : public DeltaTreeNode {
 125     DeltaTreeNode *Children[2*WidthFactor];
 126     ~DeltaTreeInteriorNode() {
 127       for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
 128         Children[i]->Destroy();
 129     }
 130     friend class DeltaTreeNode;
 131   public:
 132     DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
 133
 134     DeltaTreeInteriorNode(const InsertResult &IR)
 135       : DeltaTreeNode(false /*nonleaf*/) {
 136       Children[0] = IR.LHS;
 137       Children[1] = IR.RHS;
 138       Values[0] = IR.Split;
 139       FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
 140       NumValuesUsed = 1;
 141     }
 142
 143     const DeltaTreeNode *getChild(unsigned i) const {
 144       assert(i < getNumValuesUsed()+1 && "Invalid child");
 145       return Children[i];
 146     }
 147     DeltaTreeNode *getChild(unsigned i) {
 148       assert(i < getNumValuesUsed()+1 && "Invalid child");
 149       return Children[i];
 150     }
 151
 152   //static inline bool classof(const DeltaTreeInteriorNode *) { return true; }
 153     static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
 154   };
 155 }
 156
 157
 158 /// Destroy - A 'virtual' destructor.
 159 void DeltaTreeNode::Destroy() {
 160   if (isLeaf())
 161     delete this;
 162   else
 163     delete cast<DeltaTreeInteriorNode>(this);
 164 }
 165
 166 /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
 167 /// local walk over our contained deltas.
 168 void DeltaTreeNode::RecomputeFullDeltaLocally() {
 169   int NewFullDelta = 0;
 170   for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
 171     NewFullDelta += Values[i].Delta;
 172   if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this))
 173     for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
 174       NewFullDelta += IN->getChild(i)->getFullDelta();
 175   FullDelta = NewFullDelta;
 176 }
 177
 178 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
 179 /// this node.  If insertion is easy, do it and return false.  Otherwise,
 180 /// split the node, populate InsertRes with info about the split, and return
 181 /// true.
 182 bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
 183                                 InsertResult *InsertRes) {
 184   // Maintain full delta for this node.
 185   FullDelta += Delta;
 186
 187   // Find the insertion point, the first delta whose index is >= FileIndex.
 188   unsigned i = 0, e = getNumValuesUsed();
 189   while (i != e && FileIndex > getValue(i).FileLoc)
 190     ++i;
 191
 192   // If we found an a record for exactly this file index, just merge this
 193   // value into the pre-existing record and finish early.
 194   if (i != e && getValue(i).FileLoc == FileIndex) {
 195     // NOTE: Delta could drop to zero here.  This means that the delta entry is
 196     // useless and could be removed.  Supporting erases is more complex than
 197     // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
 198     // the tree.
 199     Values[i].Delta += Delta;
 200     return false;
 201   }
 202
 203   // Otherwise, we found an insertion point, and we know that the value at the
 204   // specified index is > FileIndex.  Handle the leaf case first.
 205   if (isLeaf()) {
 206     if (!isFull()) {
 207       // For an insertion into a non-full leaf node, just insert the value in
 208       // its sorted position.  This requires moving later values over.
 209       if (i != e)
 210         memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
 211       Values[i] = SourceDelta::get(FileIndex, Delta);
 212       ++NumValuesUsed;
 213       return false;
 214     }
 215
 216     // Otherwise, if this is leaf is full, split the node at its median, insert
 217     // the value into one of the children, and return the result.
 218     assert(InsertRes && "No result location specified");
 219     DoSplit(*InsertRes);
 220
 221     if (InsertRes->Split.FileLoc > FileIndex)
 222       InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
 223     else
 224       InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
 225     return true;
 226   }
 227
 228   // Otherwise, this is an interior node.  Send the request down the tree.
 229   DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
 230   if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
 231     return false; // If there was space in the child, just return.
 232
 233   // Okay, this split the subtree, producing a new value and two children to
 234   // insert here.  If this node is non-full, we can just insert it directly.
 235   if (!isFull()) {
 236     // Now that we have two nodes and a new element, insert the perclated value
 237     // into ourself by moving all the later values/children down, then inserting
 238     // the new one.
 239     if (i != e)
 240       memmove(&IN->Children[i+2], &IN->Children[i+1],
 241               (e-i)*sizeof(IN->Children[0]));
 242     IN->Children[i] = InsertRes->LHS;
 243     IN->Children[i+1] = InsertRes->RHS;
 244
 245     if (e != i)
 246       memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
 247     Values[i] = InsertRes->Split;
 248     ++NumValuesUsed;
 249     return false;
 250   }
 251
 252   // Finally, if this interior node was full and a node is percolated up, split
 253   // ourself and return that up the chain.  Start by saving all our info to
 254   // avoid having the split clobber it.
 255   IN->Children[i] = InsertRes->LHS;
 256   DeltaTreeNode *SubRHS = InsertRes->RHS;
 257   SourceDelta SubSplit = InsertRes->Split;
 258
 259   // Do the split.
 260   DoSplit(*InsertRes);
 261
 262   // Figure out where to insert SubRHS/NewSplit.
 263   DeltaTreeInteriorNode *InsertSide;
 264   if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
 265     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
 266   else
 267     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
 268
 269   // We now have a non-empty interior node 'InsertSide' to insert
 270   // SubRHS/SubSplit into.  Find out where to insert SubSplit.
 271
 272   // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
 273   i = 0; e = InsertSide->getNumValuesUsed();
 274   while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
 275     ++i;
 276
 277   // Now we know that i is the place to insert the split value into.  Insert it
 278   // and the child right after it.
 279   if (i != e)
 280     memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
 281             (e-i)*sizeof(IN->Children[0]));
 282   InsertSide->Children[i+1] = SubRHS;
 283
 284   if (e != i)
 285     memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
 286             (e-i)*sizeof(Values[0]));
 287   InsertSide->Values[i] = SubSplit;
 288   ++InsertSide->NumValuesUsed;
 289   InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
 290   return true;
 291 }
 292
 293 /// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
 294 /// into two subtrees each with "WidthFactor-1" values and a pivot value.
 295 /// Return the pieces in InsertRes.
 296 void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
 297   assert(isFull() && "Why split a non-full node?");
 298
 299   // Since this node is full, it contains 2*WidthFactor-1 values.  We move
 300   // the first 'WidthFactor-1' values to the LHS child (which we leave in this
 301   // node), propagate one value up, and move the last 'WidthFactor-1' values
 302   // into the RHS child.
 303
 304   // Create the new child node.
 305   DeltaTreeNode *NewNode;
 306   if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
 307     // If this is an interior node, also move over 'WidthFactor' children
 308     // into the new node.
 309     DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
 310     memcpy(&New->Children[0], &IN->Children[WidthFactor],
 311            WidthFactor*sizeof(IN->Children[0]));
 312     NewNode = New;
 313   } else {
 314     // Just create the new leaf node.
 315     NewNode = new DeltaTreeNode();
 316   }
 317
 318   // Move over the last 'WidthFactor-1' values from here to NewNode.
 319   memcpy(&NewNode->Values[0], &Values[WidthFactor],
 320          (WidthFactor-1)*sizeof(Values[0]));
 321
 322   // Decrease the number of values in the two nodes.
 323   NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
 324
 325   // Recompute the two nodes' full delta.
 326   NewNode->RecomputeFullDeltaLocally();
 327   RecomputeFullDeltaLocally();
 328
 329   InsertRes.LHS = this;
 330   InsertRes.RHS = NewNode;
 331   InsertRes.Split = Values[WidthFactor-1];
 332 }
 333
 334
 335
 336 //===----------------------------------------------------------------------===//
 337 //                        DeltaTree Implementation
 338 //===----------------------------------------------------------------------===//
 339
 340 //#define VERIFY_TREE
 341
 342 #ifdef VERIFY_TREE
 343 /// VerifyTree - Walk the btree performing assertions on various properties to
 344 /// verify consistency.  This is useful for debugging new changes to the tree.
 345 static void VerifyTree(const DeltaTreeNode *N) {
 346   const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N);
 347   if (IN == 0) {
 348     // Verify leaves, just ensure that FullDelta matches up and the elements
 349     // are in proper order.
 350     int FullDelta = 0;
 351     for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
 352       if (i)
 353         assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
 354       FullDelta += N->getValue(i).Delta;
 355     }
 356     assert(FullDelta == N->getFullDelta());
 357     return;
 358   }
 359
 360   // Verify interior nodes: Ensure that FullDelta matches up and the
 361   // elements are in proper order and the children are in proper order.
 362   int FullDelta = 0;
 363   for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
 364     const SourceDelta &IVal = N->getValue(i);
 365     const DeltaTreeNode *IChild = IN->getChild(i);
 366     if (i)
 367       assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
 368     FullDelta += IVal.Delta;
 369     FullDelta += IChild->getFullDelta();
 370
 371     // The largest value in child #i should be smaller than FileLoc.
 372     assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
 373            IVal.FileLoc);
 374
 375     // The smallest value in child #i+1 should be larger than FileLoc.
 376     assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
 377     VerifyTree(IChild);
 378   }
 379
 380   FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
 381
 382   assert(FullDelta == N->getFullDelta());
 383 }
 384 #endif  // VERIFY_TREE
 385
 386 static DeltaTreeNode *getRoot(void *Root) {
 387   return (DeltaTreeNode*)Root;
 388 }
 389
 390 DeltaTree::DeltaTree() {
 391   Root = new DeltaTreeNode();
 392 }
 393 DeltaTree::DeltaTree(const DeltaTree &RHS) {
 394   // Currently we only support copying when the RHS is empty.
 395   assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
 396          "Can only copy empty tree");
 397   Root = new DeltaTreeNode();
 398 }
 399
 400 DeltaTree::~DeltaTree() {
 401   getRoot(Root)->Destroy();
 402 }
 403
 404 /// getDeltaAt - Return the accumulated delta at the specified file offset.
 405 /// This includes all insertions or delections that occurred *before* the
 406 /// specified file index.
 407 int DeltaTree::getDeltaAt(unsigned FileIndex) const {
 408   const DeltaTreeNode *Node = getRoot(Root);
 409
 410   int Result = 0;
 411
 412   // Walk down the tree.
 413   while (1) {
 414     // For all nodes, include any local deltas before the specified file
 415     // index by summing them up directly.  Keep track of how many were
 416     // included.
 417     unsigned NumValsGreater = 0;
 418     for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
 419          ++NumValsGreater) {
 420       const SourceDelta &Val = Node->getValue(NumValsGreater);
 421
 422       if (Val.FileLoc >= FileIndex)
 423         break;
 424       Result += Val.Delta;
 425     }
 426
 427     // If we have an interior node, include information about children and
 428     // recurse.  Otherwise, if we have a leaf, we're done.
 429     const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
 430     if (!IN) return Result;
 431
 432     // Include any children to the left of the values we skipped, all of
 433     // their deltas should be included as well.
 434     for (unsigned i = 0; i != NumValsGreater; ++i)
 435       Result += IN->getChild(i)->getFullDelta();
 436
 437     // If we found exactly the value we were looking for, break off the
 438     // search early.  There is no need to search the RHS of the value for
 439     // partial results.
 440     if (NumValsGreater != Node->getNumValuesUsed() &&
 441         Node->getValue(NumValsGreater).FileLoc == FileIndex)
 442       return Result+IN->getChild(NumValsGreater)->getFullDelta();
 443
 444     // Otherwise, traverse down the tree.  The selected subtree may be
 445     // partially included in the range.
 446     Node = IN->getChild(NumValsGreater);
 447   }
 448   // NOT REACHED.
 449 }
 450
 451 /// AddDelta - When a change is made that shifts around the text buffer,
 452 /// this method is used to record that info.  It inserts a delta of 'Delta'
 453 /// into the current DeltaTree at offset FileIndex.
 454 void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
 455   assert(Delta && "Adding a noop?");
 456   DeltaTreeNode *MyRoot = getRoot(Root);
 457
 458   DeltaTreeNode::InsertResult InsertRes;
 459   if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
 460     Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
 461   }
 462
 463 #ifdef VERIFY_TREE
 464   VerifyTree(MyRoot);
 465 #endif
 466 }
 467