Coverage Report

Created: 2018-07-21 08:31

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/Rewrite/DeltaTree.cpp
Line
Count
Source
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
403k
    static SourceDelta get(unsigned Loc, int D) {
47
403k
      SourceDelta Delta;
48
403k
      Delta.FileLoc = Loc;
49
403k
      Delta.Delta = D;
50
403k
      return Delta;
51
403k
    }
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
75.6k
    DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}
89
90
4.36M
    bool isLeaf() const { return IsLeaf; }
91
9.90M
    int getFullDelta() const { return FullDelta; }
92
473k
    bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
93
94
5.97M
    unsigned getNumValuesUsed() const { return NumValuesUsed; }
95
96
15.6M
    const SourceDelta &getValue(unsigned i) const {
97
15.6M
      assert(i < NumValuesUsed && "Invalid value #");
98
15.6M
      return Values[i];
99
15.6M
    }
100
101
16.0M
    SourceDelta &getValue(unsigned i) {
102
16.0M
      assert(i < NumValuesUsed && "Invalid value #");
103
16.0M
      return Values[i];
104
16.0M
    }
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
4.74k
    ~DeltaTreeInteriorNode() {
130
42.8k
      for (unsigned i = 0, e = NumValuesUsed+1; i != e; 
++i38.0k
)
131
38.0k
        Children[i]->Destroy();
132
4.74k
    }
133
134
  public:
135
4.36k
    DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
136
137
    DeltaTreeInteriorNode(const InsertResult &IR)
138
381
        : DeltaTreeNode(false /*nonleaf*/) {
139
381
      Children[0] = IR.LHS;
140
381
      Children[1] = IR.RHS;
141
381
      Values[0] = IR.Split;
142
381
      FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
143
381
      NumValuesUsed = 1;
144
381
    }
145
146
11.4M
    const DeltaTreeNode *getChild(unsigned i) const {
147
11.4M
      assert(i < getNumValuesUsed()+1 && "Invalid child");
148
11.4M
      return Children[i];
149
11.4M
    }
150
151
69.8k
    DeltaTreeNode *getChild(unsigned i) {
152
69.8k
      assert(i < getNumValuesUsed()+1 && "Invalid child");
153
69.8k
      return Children[i];
154
69.8k
    }
155
156
2.24M
    static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
157
  };
158
159
} // namespace
160
161
/// Destroy - A 'virtual' destructor.
162
75.6k
void DeltaTreeNode::Destroy() {
163
75.6k
  if (isLeaf())
164
70.8k
    delete this;
165
4.74k
  else
166
4.74k
    delete cast<DeltaTreeInteriorNode>(this);
167
75.6k
}
168
169
/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
170
/// local walk over our contained deltas.
171
75.3k
void DeltaTreeNode::RecomputeFullDeltaLocally() {
172
75.3k
  int NewFullDelta = 0;
173
603k
  for (unsigned i = 0, e = getNumValuesUsed(); i != e; 
++i527k
)
174
527k
    NewFullDelta += Values[i].Delta;
175
75.3k
  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this))
176
78.6k
    
for (unsigned i = 0, e = getNumValuesUsed()+1; 8.73k
i != e;
++i69.8k
)
177
69.8k
      NewFullDelta += IN->getChild(i)->getFullDelta();
178
75.3k
  FullDelta = NewFullDelta;
179
75.3k
}
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
2.14M
                                InsertResult *InsertRes) {
187
2.14M
  // Maintain full delta for this node.
188
2.14M
  FullDelta += Delta;
189
2.14M
190
2.14M
  // Find the insertion point, the first delta whose index is >= FileIndex.
191
2.14M
  unsigned i = 0, e = getNumValuesUsed();
192
16.1M
  while (i != e && 
FileIndex > getValue(i).FileLoc15.0M
)
193
14.0M
    ++i;
194
2.14M
195
2.14M
  // If we found an a record for exactly this file index, just merge this
196
2.14M
  // value into the pre-existing record and finish early.
197
2.14M
  if (i != e && 
getValue(i).FileLoc == FileIndex974k
) {
198
104k
    // NOTE: Delta could drop to zero here.  This means that the delta entry is
199
104k
    // useless and could be removed.  Supporting erases is more complex than
200
104k
    // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
201
104k
    // the tree.
202
104k
    Values[i].Delta += Delta;
203
104k
    return false;
204
104k
  }
205
2.04M
206
2.04M
  // Otherwise, we found an insertion point, and we know that the value at the
207
2.04M
  // specified index is > FileIndex.  Handle the leaf case first.
208
2.04M
  if (isLeaf()) {
209
436k
    if (!isFull()) {
210
403k
      // For an insertion into a non-full leaf node, just insert the value in
211
403k
      // its sorted position.  This requires moving later values over.
212
403k
      if (i != e)
213
145k
        memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
214
403k
      Values[i] = SourceDelta::get(FileIndex, Delta);
215
403k
      ++NumValuesUsed;
216
403k
      return false;
217
403k
    }
218
33.3k
219
33.3k
    // Otherwise, if this is leaf is full, split the node at its median, insert
220
33.3k
    // the value into one of the children, and return the result.
221
33.3k
    assert(InsertRes && "No result location specified");
222
33.3k
    DoSplit(*InsertRes);
223
33.3k
224
33.3k
    if (InsertRes->Split.FileLoc > FileIndex)
225
563
      InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
226
32.7k
    else
227
32.7k
      InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
228
33.3k
    return true;
229
33.3k
  }
230
1.60M
231
1.60M
  // Otherwise, this is an interior node.  Send the request down the tree.
232
1.60M
  auto *IN = cast<DeltaTreeInteriorNode>(this);
233
1.60M
  if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
234
1.56M
    return false; // If there was space in the child, just return.
235
37.3k
236
37.3k
  // Okay, this split the subtree, producing a new value and two children to
237
37.3k
  // insert here.  If this node is non-full, we can just insert it directly.
238
37.3k
  if (!isFull()) {
239
32.9k
    // Now that we have two nodes and a new element, insert the perclated value
240
32.9k
    // into ourself by moving all the later values/children down, then inserting
241
32.9k
    // the new one.
242
32.9k
    if (i != e)
243
4.60k
      memmove(&IN->Children[i+2], &IN->Children[i+1],
244
4.60k
              (e-i)*sizeof(IN->Children[0]));
245
32.9k
    IN->Children[i] = InsertRes->LHS;
246
32.9k
    IN->Children[i+1] = InsertRes->RHS;
247
32.9k
248
32.9k
    if (e != i)
249
4.60k
      memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
250
32.9k
    Values[i] = InsertRes->Split;
251
32.9k
    ++NumValuesUsed;
252
32.9k
    return false;
253
32.9k
  }
254
4.36k
255
4.36k
  // Finally, if this interior node was full and a node is percolated up, split
256
4.36k
  // ourself and return that up the chain.  Start by saving all our info to
257
4.36k
  // avoid having the split clobber it.
258
4.36k
  IN->Children[i] = InsertRes->LHS;
259
4.36k
  DeltaTreeNode *SubRHS = InsertRes->RHS;
260
4.36k
  SourceDelta SubSplit = InsertRes->Split;
261
4.36k
262
4.36k
  // Do the split.
263
4.36k
  DoSplit(*InsertRes);
264
4.36k
265
4.36k
  // Figure out where to insert SubRHS/NewSplit.
266
4.36k
  DeltaTreeInteriorNode *InsertSide;
267
4.36k
  if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
268
9
    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
269
4.35k
  else
270
4.35k
    InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
271
4.36k
272
4.36k
  // We now have a non-empty interior node 'InsertSide' to insert
273
4.36k
  // SubRHS/SubSplit into.  Find out where to insert SubSplit.
274
4.36k
275
4.36k
  // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
276
4.36k
  i = 0; e = InsertSide->getNumValuesUsed();
277
33.1k
  while (i != e && 
SubSplit.FileLoc > InsertSide->getValue(i).FileLoc29.3k
)
278
28.8k
    ++i;
279
4.36k
280
4.36k
  // Now we know that i is the place to insert the split value into.  Insert it
281
4.36k
  // and the child right after it.
282
4.36k
  if (i != e)
283
523
    memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
284
523
            (e-i)*sizeof(IN->Children[0]));
285
4.36k
  InsertSide->Children[i+1] = SubRHS;
286
4.36k
287
4.36k
  if (e != i)
288
523
    memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
289
523
            (e-i)*sizeof(Values[0]));
290
4.36k
  InsertSide->Values[i] = SubSplit;
291
4.36k
  ++InsertSide->NumValuesUsed;
292
4.36k
  InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
293
4.36k
  return true;
294
4.36k
}
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
37.6k
void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
300
37.6k
  assert(isFull() && "Why split a non-full node?");
301
37.6k
302
37.6k
  // Since this node is full, it contains 2*WidthFactor-1 values.  We move
303
37.6k
  // the first 'WidthFactor-1' values to the LHS child (which we leave in this
304
37.6k
  // node), propagate one value up, and move the last 'WidthFactor-1' values
305
37.6k
  // into the RHS child.
306
37.6k
307
37.6k
  // Create the new child node.
308
37.6k
  DeltaTreeNode *NewNode;
309
37.6k
  if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
310
4.36k
    // If this is an interior node, also move over 'WidthFactor' children
311
4.36k
    // into the new node.
312
4.36k
    DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
313
4.36k
    memcpy(&New->Children[0], &IN->Children[WidthFactor],
314
4.36k
           WidthFactor*sizeof(IN->Children[0]));
315
4.36k
    NewNode = New;
316
33.3k
  } else {
317
33.3k
    // Just create the new leaf node.
318
33.3k
    NewNode = new DeltaTreeNode();
319
33.3k
  }
320
37.6k
321
37.6k
  // Move over the last 'WidthFactor-1' values from here to NewNode.
322
37.6k
  memcpy(&NewNode->Values[0], &Values[WidthFactor],
323
37.6k
         (WidthFactor-1)*sizeof(Values[0]));
324
37.6k
325
37.6k
  // Decrease the number of values in the two nodes.
326
37.6k
  NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
327
37.6k
328
37.6k
  // Recompute the two nodes' full delta.
329
37.6k
  NewNode->RecomputeFullDeltaLocally();
330
37.6k
  RecomputeFullDeltaLocally();
331
37.6k
332
37.6k
  InsertRes.LHS = this;
333
37.6k
  InsertRes.RHS = NewNode;
334
37.6k
  InsertRes.Split = Values[WidthFactor-1];
335
37.6k
}
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
1.06M
static DeltaTreeNode *getRoot(void *Root) {
388
1.06M
  return (DeltaTreeNode*)Root;
389
1.06M
}
390
391
12.5k
DeltaTree::DeltaTree() {
392
12.5k
  Root = new DeltaTreeNode();
393
12.5k
}
394
395
25.0k
DeltaTree::DeltaTree(const DeltaTree &RHS) {
396
25.0k
  // Currently we only support copying when the RHS is empty.
397
25.0k
  assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
398
25.0k
         "Can only copy empty tree");
399
25.0k
  Root = new DeltaTreeNode();
400
25.0k
}
401
402
37.5k
DeltaTree::~DeltaTree() {
403
37.5k
  getRoot(Root)->Destroy();
404
37.5k
}
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
522k
int DeltaTree::getDeltaAt(unsigned FileIndex) const {
410
522k
  const DeltaTreeNode *Node = getRoot(Root);
411
522k
412
522k
  int Result = 0;
413
522k
414
522k
  // Walk down the tree.
415
2.13M
  while (true) {
416
2.13M
    // For all nodes, include any local deltas before the specified file
417
2.13M
    // index by summing them up directly.  Keep track of how many were
418
2.13M
    // included.
419
2.13M
    unsigned NumValsGreater = 0;
420
16.0M
    for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
421
14.9M
         
++NumValsGreater13.9M
) {
422
14.9M
      const SourceDelta &Val = Node->getValue(NumValsGreater);
423
14.9M
424
14.9M
      if (Val.FileLoc >= FileIndex)
425
962k
        break;
426
13.9M
      Result += Val.Delta;
427
13.9M
    }
428
2.13M
429
2.13M
    // If we have an interior node, include information about children and
430
2.13M
    // recurse.  Otherwise, if we have a leaf, we're done.
431
2.13M
    const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
432
2.13M
    if (!IN) 
return Result521k
;
433
1.61M
434
1.61M
    // Include any children to the left of the values we skipped, all of
435
1.61M
    // their deltas should be included as well.
436
11.4M
    
for (unsigned i = 0; 1.61M
i != NumValsGreater;
++i9.82M
)
437
9.82M
      Result += IN->getChild(i)->getFullDelta();
438
1.61M
439
1.61M
    // If we found exactly the value we were looking for, break off the
440
1.61M
    // search early.  There is no need to search the RHS of the value for
441
1.61M
    // partial results.
442
1.61M
    if (NumValsGreater != Node->getNumValuesUsed() &&
443
1.61M
        
Node->getValue(NumValsGreater).FileLoc == FileIndex720k
)
444
861
      return Result+IN->getChild(NumValsGreater)->getFullDelta();
445
1.60M
446
1.60M
    // Otherwise, traverse down the tree.  The selected subtree may be
447
1.60M
    // partially included in the range.
448
1.60M
    Node = IN->getChild(NumValsGreater);
449
1.60M
  }
450
522k
  // NOT REACHED.
451
522k
}
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
507k
void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
457
507k
  assert(Delta && "Adding a noop?");
458
507k
  DeltaTreeNode *MyRoot = getRoot(Root);
459
507k
460
507k
  DeltaTreeNode::InsertResult InsertRes;
461
507k
  if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
462
381
    Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
463
381
  }
464
507k
465
#ifdef VERIFY_TREE
466
  VerifyTree(MyRoot);
467
#endif
468
}