clang  7.0.0svn
DeltaTree.cpp
Go to the documentation of this file.
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 
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 
392  Root = new DeltaTreeNode();
393 }
394 
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 
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 }
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:456
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static DeltaTreeNode * getRoot(void *Root)
Definition: DeltaTree.cpp:387
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:409
The result type of a method or function.
DeltaTree - a multiway search tree (BTree) structure with some fancy features.
Definition: DeltaTree.h:26
#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)