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