Coverage Report

Created: 2020-02-25 14:32

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