clang  6.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 <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, nullptr /*can't fail*/);
220  else
221  InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*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 
388  Root = new DeltaTreeNode();
389 }
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 
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 
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:451
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static DeltaTreeNode * getRoot(void *Root)
Definition: DeltaTree.cpp:383
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:404
The result type of a method or function.
DeltaTree - a multiway search tree (BTree) structure with some fancy features.
Definition: DeltaTree.h:28
#define false
Definition: stdbool.h:33
ast_type_traits::DynTypedNode Node
Dataflow Directional Tag Classes.
static bool classof(const OMPClause *T)