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