Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Rewrite/RewriteRope.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- RewriteRope.cpp - Rope specialized for rewriter --------------------===//
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 RewriteRope class, which is a powerful string.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "clang/Rewrite/Core/RewriteRope.h"
14
#include "clang/Basic/LLVM.h"
15
#include "llvm/Support/Casting.h"
16
#include <algorithm>
17
#include <cassert>
18
#include <cstring>
19
20
using namespace clang;
21
22
/// RewriteRope is a "strong" string class, designed to make insertions and
23
/// deletions in the middle of the string nearly constant time (really, they are
24
/// O(log N), but with a very low constant factor).
25
///
26
/// The implementation of this datastructure is a conceptual linear sequence of
27
/// RopePiece elements.  Each RopePiece represents a view on a separately
28
/// allocated and reference counted string.  This means that splitting a very
29
/// long string can be done in constant time by splitting a RopePiece that
30
/// references the whole string into two rope pieces that reference each half.
31
/// Once split, another string can be inserted in between the two halves by
32
/// inserting a RopePiece in between the two others.  All of this is very
33
/// inexpensive: it takes time proportional to the number of RopePieces, not the
34
/// length of the strings they represent.
35
///
36
/// While a linear sequences of RopePieces is the conceptual model, the actual
37
/// implementation captures them in an adapted B+ Tree.  Using a B+ tree (which
38
/// is a tree that keeps the values in the leaves and has where each node
39
/// contains a reasonable number of pointers to children/values) allows us to
40
/// maintain efficient operation when the RewriteRope contains a *huge* number
41
/// of RopePieces.  The basic idea of the B+ Tree is that it allows us to find
42
/// the RopePiece corresponding to some offset very efficiently, and it
43
/// automatically balances itself on insertions of RopePieces (which can happen
44
/// for both insertions and erases of string ranges).
45
///
46
/// The one wrinkle on the theory is that we don't attempt to keep the tree
47
/// properly balanced when erases happen.  Erases of string data can both insert
48
/// new RopePieces (e.g. when the middle of some other rope piece is deleted,
49
/// which results in two rope pieces, which is just like an insert) or it can
50
/// reduce the number of RopePieces maintained by the B+Tree.  In the case when
51
/// the number of RopePieces is reduced, we don't attempt to maintain the
52
/// standard 'invariant' that each node in the tree contains at least
53
/// 'WidthFactor' children/values.  For our use cases, this doesn't seem to
54
/// matter.
55
///
56
/// The implementation below is primarily implemented in terms of three classes:
57
///   RopePieceBTreeNode - Common base class for:
58
///
59
///     RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
60
///          nodes.  This directly represents a chunk of the string with those
61
///          RopePieces concatenated.
62
///     RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
63
///          up to '2*WidthFactor' other nodes in the tree.
64
65
namespace {
66
67
//===----------------------------------------------------------------------===//
68
// RopePieceBTreeNode Class
69
//===----------------------------------------------------------------------===//
70
71
  /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
72
  /// RopePieceBTreeInterior.  This provides some 'virtual' dispatching methods
73
  /// and a flag that determines which subclass the instance is.  Also
74
  /// important, this node knows the full extend of the node, including any
75
  /// children that it has.  This allows efficient skipping over entire subtrees
76
  /// when looking for an offset in the BTree.
77
  class RopePieceBTreeNode {
78
  protected:
79
    /// WidthFactor - This controls the number of K/V slots held in the BTree:
80
    /// how wide it is.  Each level of the BTree is guaranteed to have at least
81
    /// 'WidthFactor' elements in it (either ropepieces or children), (except
82
    /// the root, which may have less) and may have at most 2*WidthFactor
83
    /// elements.
84
    enum { WidthFactor = 8 };
85
86
    /// Size - This is the number of bytes of file this node (including any
87
    /// potential children) covers.
88
    unsigned Size = 0;
89
90
    /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
91
    /// is an instance of RopePieceBTreeInterior.
92
    bool IsLeaf;
93
94
59.7k
    RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {}
95
    ~RopePieceBTreeNode() = default;
96
97
  public:
98
1.69M
    bool isLeaf() const { return IsLeaf; }
99
6.46M
    unsigned size() const { return Size; }
100
101
    void Destroy();
102
103
    /// split - Split the range containing the specified offset so that we are
104
    /// guaranteed that there is a place to do an insertion at the specified
105
    /// offset.  The offset is relative, so "0" is the start of the node.
106
    ///
107
    /// If there is no space in this subtree for the extra piece, the extra tree
108
    /// node is returned and must be inserted into a parent.
109
    RopePieceBTreeNode *split(unsigned Offset);
110
111
    /// insert - Insert the specified ropepiece into this tree node at the
112
    /// specified offset.  The offset is relative, so "0" is the start of the
113
    /// node.
114
    ///
115
    /// If there is no space in this subtree for the extra piece, the extra tree
116
    /// node is returned and must be inserted into a parent.
117
    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
118
119
    /// erase - Remove NumBytes from this node at the specified offset.  We are
120
    /// guaranteed that there is a split at Offset.
121
    void erase(unsigned Offset, unsigned NumBytes);
122
  };
123
124
//===----------------------------------------------------------------------===//
125
// RopePieceBTreeLeaf Class
126
//===----------------------------------------------------------------------===//
127
128
  /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
129
  /// nodes.  This directly represents a chunk of the string with those
130
  /// RopePieces concatenated.  Since this is a B+Tree, all values (in this case
131
  /// instances of RopePiece) are stored in leaves like this.  To make iteration
132
  /// over the leaves efficient, they maintain a singly linked list through the
133
  /// NextLeaf field.  This allows the B+Tree forward iterator to be constant
134
  /// time for all increments.
135
  class RopePieceBTreeLeaf : public RopePieceBTreeNode {
136
    /// NumPieces - This holds the number of rope pieces currently active in the
137
    /// Pieces array.
138
    unsigned char NumPieces = 0;
139
140
    /// Pieces - This tracks the file chunks currently in this leaf.
141
    RopePiece Pieces[2*WidthFactor];
142
143
    /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
144
    /// efficient in-order forward iteration of the tree without traversal.
145
    RopePieceBTreeLeaf **PrevLeaf = nullptr;
146
    RopePieceBTreeLeaf *NextLeaf = nullptr;
147
148
  public:
149
57.2k
    RopePieceBTreeLeaf() : RopePieceBTreeNode(true) {}
150
151
57.2k
    ~RopePieceBTreeLeaf() {
152
57.2k
      if (PrevLeaf || 
NextLeaf57.2k
)
153
15.1k
        removeFromLeafInOrder();
154
57.2k
      clear();
155
57.2k
    }
156
157
261k
    bool isFull() const { return NumPieces == 2*WidthFactor; }
158
159
    /// clear - Remove all rope pieces from this leaf.
160
71.3k
    void clear() {
161
316k
      while (NumPieces)
162
245k
        Pieces[--NumPieces] = RopePiece();
163
71.3k
      Size = 0;
164
71.3k
    }
165
166
2.31M
    unsigned getNumPieces() const { return NumPieces; }
167
168
1.74M
    const RopePiece &getPiece(unsigned i) const {
169
1.74M
      assert(i < getNumPieces() && "Invalid piece ID");
170
1.74M
      return Pieces[i];
171
1.74M
    }
172
173
30.2k
    const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
174
175
15.1k
    void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
176
15.1k
      assert(!PrevLeaf && !NextLeaf && "Already in ordering");
177
15.1k
178
15.1k
      NextLeaf = Node->NextLeaf;
179
15.1k
      if (NextLeaf)
180
12.0k
        NextLeaf->PrevLeaf = &NextLeaf;
181
15.1k
      PrevLeaf = &Node->NextLeaf;
182
15.1k
      Node->NextLeaf = this;
183
15.1k
    }
184
185
15.1k
    void removeFromLeafInOrder() {
186
15.1k
      if (PrevLeaf) {
187
1
        *PrevLeaf = NextLeaf;
188
1
        if (NextLeaf)
189
1
          NextLeaf->PrevLeaf = PrevLeaf;
190
15.1k
      } else if (NextLeaf) {
191
15.1k
        NextLeaf->PrevLeaf = nullptr;
192
15.1k
      }
193
15.1k
    }
194
195
    /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
196
    /// summing the size of all RopePieces.
197
30.2k
    void FullRecomputeSizeLocally() {
198
30.2k
      Size = 0;
199
272k
      for (unsigned i = 0, e = getNumPieces(); i != e; 
++i241k
)
200
241k
        Size += getPiece(i).size();
201
30.2k
    }
202
203
    /// split - Split the range containing the specified offset so that we are
204
    /// guaranteed that there is a place to do an insertion at the specified
205
    /// offset.  The offset is relative, so "0" is the start of the node.
206
    ///
207
    /// If there is no space in this subtree for the extra piece, the extra tree
208
    /// node is returned and must be inserted into a parent.
209
    RopePieceBTreeNode *split(unsigned Offset);
210
211
    /// insert - Insert the specified ropepiece into this tree node at the
212
    /// specified offset.  The offset is relative, so "0" is the start of the
213
    /// node.
214
    ///
215
    /// If there is no space in this subtree for the extra piece, the extra tree
216
    /// node is returned and must be inserted into a parent.
217
    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
218
219
    /// erase - Remove NumBytes from this node at the specified offset.  We are
220
    /// guaranteed that there is a split at Offset.
221
    void erase(unsigned Offset, unsigned NumBytes);
222
223
1.28M
    static bool classof(const RopePieceBTreeNode *N) {
224
1.28M
      return N->isLeaf();
225
1.28M
    }
226
  };
227
228
} // namespace
229
230
/// split - Split the range containing the specified offset so that we are
231
/// guaranteed that there is a place to do an insertion at the specified
232
/// offset.  The offset is relative, so "0" is the start of the node.
233
///
234
/// If there is no space in this subtree for the extra piece, the extra tree
235
/// node is returned and must be inserted into a parent.
236
180k
RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
237
180k
  // Find the insertion point.  We are guaranteed that there is a split at the
238
180k
  // specified offset so find it.
239
180k
  if (Offset == 0 || 
Offset == size()165k
) {
240
15.5k
    // Fastpath for a common case.  There is already a splitpoint at the end.
241
15.5k
    return nullptr;
242
15.5k
  }
243
164k
244
164k
  // Find the piece that this offset lands in.
245
164k
  unsigned PieceOffs = 0;
246
164k
  unsigned i = 0;
247
860k
  while (Offset >= PieceOffs+Pieces[i].size()) {
248
695k
    PieceOffs += Pieces[i].size();
249
695k
    ++i;
250
695k
  }
251
164k
252
164k
  // If there is already a split point at the specified offset, just return
253
164k
  // success.
254
164k
  if (PieceOffs == Offset)
255
55.6k
    return nullptr;
256
109k
257
109k
  // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
258
109k
  // to being Piece relative.
259
109k
  unsigned IntraPieceOffset = Offset-PieceOffs;
260
109k
261
109k
  // We do this by shrinking the RopePiece and then doing an insert of the tail.
262
109k
  RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
263
109k
                 Pieces[i].EndOffs);
264
109k
  Size -= Pieces[i].size();
265
109k
  Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
266
109k
  Size += Pieces[i].size();
267
109k
268
109k
  return insert(Offset, Tail);
269
109k
}
270
271
/// insert - Insert the specified RopePiece into this tree node at the
272
/// specified offset.  The offset is relative, so "0" is the start of the node.
273
///
274
/// If there is no space in this subtree for the extra piece, the extra tree
275
/// node is returned and must be inserted into a parent.
276
RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
277
261k
                                               const RopePiece &R) {
278
261k
  // If this node is not full, insert the piece.
279
261k
  if (!isFull()) {
280
246k
    // Find the insertion point.  We are guaranteed that there is a split at the
281
246k
    // specified offset so find it.
282
246k
    unsigned i = 0, e = getNumPieces();
283
246k
    if (Offset == size()) {
284
46.6k
      // Fastpath for a common case.
285
46.6k
      i = e;
286
199k
    } else {
287
199k
      unsigned SlotOffs = 0;
288
1.17M
      for (; Offset > SlotOffs; 
++i974k
)
289
974k
        SlotOffs += getPiece(i).size();
290
199k
      assert(SlotOffs == Offset && "Split didn't occur before insertion!");
291
199k
    }
292
246k
293
246k
    // For an insertion into a non-full leaf node, just insert the value in
294
246k
    // its sorted position.  This requires moving later values over.
295
1.14M
    for (; i != e; 
--e901k
)
296
901k
      Pieces[e] = Pieces[e-1];
297
246k
    Pieces[i] = R;
298
246k
    ++NumPieces;
299
246k
    Size += R.size();
300
246k
    return nullptr;
301
246k
  }
302
15.1k
303
15.1k
  // Otherwise, if this is leaf is full, split it in two halves.  Since this
304
15.1k
  // node is full, it contains 2*WidthFactor values.  We move the first
305
15.1k
  // 'WidthFactor' values to the LHS child (which we leave in this node) and
306
15.1k
  // move the last 'WidthFactor' values into the RHS child.
307
15.1k
308
15.1k
  // Create the new node.
309
15.1k
  RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
310
15.1k
311
15.1k
  // Move over the last 'WidthFactor' values from here to NewNode.
312
15.1k
  std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
313
15.1k
            &NewNode->Pieces[0]);
314
15.1k
  // Replace old pieces with null RopePieces to drop refcounts.
315
15.1k
  std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
316
15.1k
317
15.1k
  // Decrease the number of values in the two nodes.
318
15.1k
  NewNode->NumPieces = NumPieces = WidthFactor;
319
15.1k
320
15.1k
  // Recompute the two nodes' size.
321
15.1k
  NewNode->FullRecomputeSizeLocally();
322
15.1k
  FullRecomputeSizeLocally();
323
15.1k
324
15.1k
  // Update the list of leaves.
325
15.1k
  NewNode->insertAfterLeafInOrder(this);
326
15.1k
327
15.1k
  // These insertions can't fail.
328
15.1k
  if (this->size() >= Offset)
329
2.42k
    this->insert(Offset, R);
330
12.6k
  else
331
12.6k
    NewNode->insert(Offset - this->size(), R);
332
15.1k
  return NewNode;
333
15.1k
}
334
335
/// erase - Remove NumBytes from this node at the specified offset.  We are
336
/// guaranteed that there is a split at Offset.
337
45.3k
void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
338
45.3k
  // Since we are guaranteed that there is a split at Offset, we start by
339
45.3k
  // finding the Piece that starts there.
340
45.3k
  unsigned PieceOffs = 0;
341
45.3k
  unsigned i = 0;
342
142k
  for (; Offset > PieceOffs; 
++i96.9k
)
343
96.9k
    PieceOffs += getPiece(i).size();
344
45.3k
  assert(PieceOffs == Offset && "Split didn't occur before erase!");
345
45.3k
346
45.3k
  unsigned StartPiece = i;
347
45.3k
348
45.3k
  // Figure out how many pieces completely cover 'NumBytes'.  We want to remove
349
45.3k
  // all of them.
350
45.9k
  for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); 
++i564
)
351
564
    PieceOffs += getPiece(i).size();
352
45.3k
353
45.3k
  // If we exactly include the last one, include it in the region to delete.
354
45.3k
  if (Offset+NumBytes == PieceOffs+getPiece(i).size()) {
355
834
    PieceOffs += getPiece(i).size();
356
834
    ++i;
357
834
  }
358
45.3k
359
45.3k
  // If we completely cover some RopePieces, erase them now.
360
45.3k
  if (i != StartPiece) {
361
1.07k
    unsigned NumDeleted = i-StartPiece;
362
4.27k
    for (; i != getNumPieces(); 
++i3.20k
)
363
3.20k
      Pieces[i-NumDeleted] = Pieces[i];
364
1.07k
365
1.07k
    // Drop references to dead rope pieces.
366
1.07k
    std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
367
1.07k
              RopePiece());
368
1.07k
    NumPieces -= NumDeleted;
369
1.07k
370
1.07k
    unsigned CoverBytes = PieceOffs-Offset;
371
1.07k
    NumBytes -= CoverBytes;
372
1.07k
    Size -= CoverBytes;
373
1.07k
  }
374
45.3k
375
45.3k
  // If we completely removed some stuff, we could be done.
376
45.3k
  if (NumBytes == 0) 
return834
;
377
44.5k
378
44.5k
  // Okay, now might be erasing part of some Piece.  If this is the case, then
379
44.5k
  // move the start point of the piece.
380
44.5k
  assert(getPiece(StartPiece).size() > NumBytes);
381
44.5k
  Pieces[StartPiece].StartOffs += NumBytes;
382
44.5k
383
44.5k
  // The size of this node just shrunk by NumBytes.
384
44.5k
  Size -= NumBytes;
385
44.5k
}
386
387
//===----------------------------------------------------------------------===//
388
// RopePieceBTreeInterior Class
389
//===----------------------------------------------------------------------===//
390
391
namespace {
392
393
  /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
394
  /// which holds up to 2*WidthFactor pointers to child nodes.
395
  class RopePieceBTreeInterior : public RopePieceBTreeNode {
396
    /// NumChildren - This holds the number of children currently active in the
397
    /// Children array.
398
    unsigned char NumChildren = 0;
399
400
    RopePieceBTreeNode *Children[2*WidthFactor];
401
402
  public:
403
1.25k
    RopePieceBTreeInterior() : RopePieceBTreeNode(false) {}
404
405
    RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
406
1.23k
        : RopePieceBTreeNode(false) {
407
1.23k
      Children[0] = LHS;
408
1.23k
      Children[1] = RHS;
409
1.23k
      NumChildren = 2;
410
1.23k
      Size = LHS->size() + RHS->size();
411
1.23k
    }
412
413
2.49k
    ~RopePieceBTreeInterior() {
414
20.1k
      for (unsigned i = 0, e = getNumChildren(); i != e; 
++i17.6k
)
415
17.6k
        Children[i]->Destroy();
416
2.49k
    }
417
418
16.3k
    bool isFull() const { return NumChildren == 2*WidthFactor; }
419
420
219k
    unsigned getNumChildren() const { return NumChildren; }
421
422
1.81k
    const RopePieceBTreeNode *getChild(unsigned i) const {
423
1.81k
      assert(i < NumChildren && "invalid child #");
424
1.81k
      return Children[i];
425
1.81k
    }
426
427
5.05M
    RopePieceBTreeNode *getChild(unsigned i) {
428
5.05M
      assert(i < NumChildren && "invalid child #");
429
5.05M
      return Children[i];
430
5.05M
    }
431
432
    /// FullRecomputeSizeLocally - Recompute the Size field of this node by
433
    /// summing up the sizes of the child nodes.
434
2.51k
    void FullRecomputeSizeLocally() {
435
2.51k
      Size = 0;
436
23.8k
      for (unsigned i = 0, e = getNumChildren(); i != e; 
++i21.3k
)
437
21.3k
        Size += getChild(i)->size();
438
2.51k
    }
439
440
    /// split - Split the range containing the specified offset so that we are
441
    /// guaranteed that there is a place to do an insertion at the specified
442
    /// offset.  The offset is relative, so "0" is the start of the node.
443
    ///
444
    /// If there is no space in this subtree for the extra piece, the extra tree
445
    /// node is returned and must be inserted into a parent.
446
    RopePieceBTreeNode *split(unsigned Offset);
447
448
    /// insert - Insert the specified ropepiece into this tree node at the
449
    /// specified offset.  The offset is relative, so "0" is the start of the
450
    /// node.
451
    ///
452
    /// If there is no space in this subtree for the extra piece, the extra tree
453
    /// node is returned and must be inserted into a parent.
454
    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
455
456
    /// HandleChildPiece - A child propagated an insertion result up to us.
457
    /// Insert the new child, and/or propagate the result further up the tree.
458
    RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
459
460
    /// erase - Remove NumBytes from this node at the specified offset.  We are
461
    /// guaranteed that there is a split at Offset.
462
    void erase(unsigned Offset, unsigned NumBytes);
463
464
416k
    static bool classof(const RopePieceBTreeNode *N) {
465
416k
      return !N->isLeaf();
466
416k
    }
467
  };
468
469
} // namespace
470
471
/// split - Split the range containing the specified offset so that we are
472
/// guaranteed that there is a place to do an insertion at the specified
473
/// offset.  The offset is relative, so "0" is the start of the node.
474
///
475
/// If there is no space in this subtree for the extra piece, the extra tree
476
/// node is returned and must be inserted into a parent.
477
196k
RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
478
196k
  // Figure out which child to split.
479
196k
  if (Offset == 0 || 
Offset == size()196k
)
480
1.08k
    return nullptr; // If we have an exact offset, we're already split.
481
195k
482
195k
  unsigned ChildOffset = 0;
483
195k
  unsigned i = 0;
484
1.25M
  for (; Offset >= ChildOffset+getChild(i)->size(); 
++i1.06M
)
485
1.06M
    ChildOffset += getChild(i)->size();
486
195k
487
195k
  // If already split there, we're done.
488
195k
  if (ChildOffset == Offset)
489
1.36k
    return nullptr;
490
194k
491
194k
  // Otherwise, recursively split the child.
492
194k
  if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
493
10.1k
    return HandleChildPiece(i, RHS);
494
184k
  return nullptr; // Done!
495
184k
}
496
497
/// insert - Insert the specified ropepiece into this tree node at the
498
/// specified offset.  The offset is relative, so "0" is the start of the
499
/// node.
500
///
501
/// If there is no space in this subtree for the extra piece, the extra tree
502
/// node is returned and must be inserted into a parent.
503
RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
504
187k
                                                   const RopePiece &R) {
505
187k
  // Find the insertion point.  We are guaranteed that there is a split at the
506
187k
  // specified offset so find it.
507
187k
  unsigned i = 0, e = getNumChildren();
508
187k
509
187k
  unsigned ChildOffs = 0;
510
187k
  if (Offset == size()) {
511
491
    // Fastpath for a common case.  Insert at end of last child.
512
491
    i = e-1;
513
491
    ChildOffs = size()-getChild(i)->size();
514
187k
  } else {
515
1.21M
    for (; Offset > ChildOffs+getChild(i)->size(); 
++i1.02M
)
516
1.02M
      ChildOffs += getChild(i)->size();
517
187k
  }
518
187k
519
187k
  Size += R.size();
520
187k
521
187k
  // Insert at the end of this child.
522
187k
  if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
523
4.97k
    return HandleChildPiece(i, RHS);
524
183k
525
183k
  return nullptr;
526
183k
}
527
528
/// HandleChildPiece - A child propagated an insertion result up to us.
529
/// Insert the new child, and/or propagate the result further up the tree.
530
RopePieceBTreeNode *
531
16.3k
RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
532
16.3k
  // Otherwise the child propagated a subtree up to us as a new child.  See if
533
16.3k
  // we have space for it here.
534
16.3k
  if (!isFull()) {
535
15.1k
    // Insert RHS after child 'i'.
536
15.1k
    if (i + 1 != getNumChildren())
537
11.6k
      memmove(&Children[i+2], &Children[i+1],
538
11.6k
              (getNumChildren()-i-1)*sizeof(Children[0]));
539
15.1k
    Children[i+1] = RHS;
540
15.1k
    ++NumChildren;
541
15.1k
    return nullptr;
542
15.1k
  }
543
1.25k
544
1.25k
  // Okay, this node is full.  Split it in half, moving WidthFactor children to
545
1.25k
  // a newly allocated interior node.
546
1.25k
547
1.25k
  // Create the new node.
548
1.25k
  RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
549
1.25k
550
1.25k
  // Move over the last 'WidthFactor' values from here to NewNode.
551
1.25k
  memcpy(&NewNode->Children[0], &Children[WidthFactor],
552
1.25k
         WidthFactor*sizeof(Children[0]));
553
1.25k
554
1.25k
  // Decrease the number of values in the two nodes.
555
1.25k
  NewNode->NumChildren = NumChildren = WidthFactor;
556
1.25k
557
1.25k
  // Finally, insert the two new children in the side the can (now) hold them.
558
1.25k
  // These insertions can't fail.
559
1.25k
  if (i < WidthFactor)
560
31
    this->HandleChildPiece(i, RHS);
561
1.22k
  else
562
1.22k
    NewNode->HandleChildPiece(i-WidthFactor, RHS);
563
1.25k
564
1.25k
  // Recompute the two nodes' size.
565
1.25k
  NewNode->FullRecomputeSizeLocally();
566
1.25k
  FullRecomputeSizeLocally();
567
1.25k
  return NewNode;
568
1.25k
}
569
570
/// erase - Remove NumBytes from this node at the specified offset.  We are
571
/// guaranteed that there is a split at Offset.
572
10.3k
void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
573
10.3k
  // This will shrink this node by NumBytes.
574
10.3k
  Size -= NumBytes;
575
10.3k
576
10.3k
  // Find the first child that overlaps with Offset.
577
10.3k
  unsigned i = 0;
578
47.0k
  for (; Offset >= getChild(i)->size(); 
++i36.7k
)
579
36.7k
    Offset -= getChild(i)->size();
580
10.3k
581
10.3k
  // Propagate the delete request into overlapping children, or completely
582
10.3k
  // delete the children as appropriate.
583
10.3k
  while (NumBytes) {
584
10.3k
    RopePieceBTreeNode *CurChild = getChild(i);
585
10.3k
586
10.3k
    // If we are deleting something contained entirely in the child, pass on the
587
10.3k
    // request.
588
10.3k
    if (Offset+NumBytes < CurChild->size()) {
589
10.3k
      CurChild->erase(Offset, NumBytes);
590
10.3k
      return;
591
10.3k
    }
592
9
593
9
    // If this deletion request starts somewhere in the middle of the child, it
594
9
    // must be deleting to the end of the child.
595
9
    if (Offset) {
596
8
      unsigned BytesFromChild = CurChild->size()-Offset;
597
8
      CurChild->erase(Offset, BytesFromChild);
598
8
      NumBytes -= BytesFromChild;
599
8
      // Start at the beginning of the next child.
600
8
      Offset = 0;
601
8
      ++i;
602
8
      continue;
603
8
    }
604
1
605
1
    // If the deletion request completely covers the child, delete it and move
606
1
    // the rest down.
607
1
    NumBytes -= CurChild->size();
608
1
    CurChild->Destroy();
609
1
    --NumChildren;
610
1
    if (i != getNumChildren())
611
1
      memmove(&Children[i], &Children[i+1],
612
1
              (getNumChildren()-i)*sizeof(Children[0]));
613
1
  }
614
10.3k
}
615
616
//===----------------------------------------------------------------------===//
617
// RopePieceBTreeNode Implementation
618
//===----------------------------------------------------------------------===//
619
620
59.7k
void RopePieceBTreeNode::Destroy() {
621
59.7k
  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
622
57.2k
    delete Leaf;
623
2.49k
  else
624
2.49k
    delete cast<RopePieceBTreeInterior>(this);
625
59.7k
}
626
627
/// split - Split the range containing the specified offset so that we are
628
/// guaranteed that there is a place to do an insertion at the specified
629
/// offset.  The offset is relative, so "0" is the start of the node.
630
///
631
/// If there is no space in this subtree for the extra piece, the extra tree
632
/// node is returned and must be inserted into a parent.
633
377k
RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
634
377k
  assert(Offset <= size() && "Invalid offset to split!");
635
377k
  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
636
180k
    return Leaf->split(Offset);
637
196k
  return cast<RopePieceBTreeInterior>(this)->split(Offset);
638
196k
}
639
640
/// insert - Insert the specified ropepiece into this tree node at the
641
/// specified offset.  The offset is relative, so "0" is the start of the
642
/// node.
643
///
644
/// If there is no space in this subtree for the extra piece, the extra tree
645
/// node is returned and must be inserted into a parent.
646
RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
647
325k
                                               const RopePiece &R) {
648
325k
  assert(Offset <= size() && "Invalid offset to insert!");
649
325k
  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
650
137k
    return Leaf->insert(Offset, R);
651
187k
  return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
652
187k
}
653
654
/// erase - Remove NumBytes from this node at the specified offset.  We are
655
/// guaranteed that there is a split at Offset.
656
55.7k
void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
657
55.7k
  assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
658
55.7k
  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
659
45.3k
    return Leaf->erase(Offset, NumBytes);
660
10.3k
  return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
661
10.3k
}
662
663
//===----------------------------------------------------------------------===//
664
// RopePieceBTreeIterator Implementation
665
//===----------------------------------------------------------------------===//
666
667
615k
static const RopePieceBTreeLeaf *getCN(const void *P) {
668
615k
  return static_cast<const RopePieceBTreeLeaf*>(P);
669
615k
}
670
671
// begin iterator.
672
14.7k
RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
673
14.7k
  const auto *N = static_cast<const RopePieceBTreeNode *>(n);
674
14.7k
675
14.7k
  // Walk down the left side of the tree until we get to a leaf.
676
16.5k
  while (const auto *IN = dyn_cast<RopePieceBTreeInterior>(N))
677
1.81k
    N = IN->getChild(0);
678
14.7k
679
14.7k
  // We must have at least one leaf.
680
14.7k
  CurNode = cast<RopePieceBTreeLeaf>(N);
681
14.7k
682
14.7k
  // If we found a leaf that happens to be empty, skip over it until we get
683
14.7k
  // to something full.
684
14.7k
  while (CurNode && 
getCN(CurNode)->getNumPieces() == 014.7k
)
685
7
    CurNode = getCN(CurNode)->getNextLeafInOrder();
686
14.7k
687
14.7k
  if (CurNode)
688
14.7k
    CurPiece = &getCN(CurNode)->getPiece(0);
689
7
  else  // Empty tree, this is an end() iterator.
690
7
    CurPiece = nullptr;
691
14.7k
  CurChar = 0;
692
14.7k
}
693
694
261k
void RopePieceBTreeIterator::MoveToNextPiece() {
695
261k
  if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
696
230k
    CurChar = 0;
697
230k
    ++CurPiece;
698
230k
    return;
699
230k
  }
700
30.2k
701
30.2k
  // Find the next non-empty leaf node.
702
30.2k
  do
703
30.2k
    CurNode = getCN(CurNode)->getNextLeafInOrder();
704
30.2k
  while (CurNode && 
getCN(CurNode)->getNumPieces() == 016.2k
);
705
30.2k
706
30.2k
  if (CurNode)
707
16.2k
    CurPiece = &getCN(CurNode)->getPiece(0);
708
13.9k
  else // Hit end().
709
13.9k
    CurPiece = nullptr;
710
30.2k
  CurChar = 0;
711
30.2k
}
712
713
//===----------------------------------------------------------------------===//
714
// RopePieceBTree Implementation
715
//===----------------------------------------------------------------------===//
716
717
625k
static RopePieceBTreeNode *getRoot(void *P) {
718
625k
  return static_cast<RopePieceBTreeNode*>(P);
719
625k
}
720
721
14.0k
RopePieceBTree::RopePieceBTree() {
722
14.0k
  Root = new RopePieceBTreeLeaf();
723
14.0k
}
724
725
28.1k
RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
726
28.1k
  assert(RHS.empty() && "Can't copy non-empty tree yet");
727
28.1k
  Root = new RopePieceBTreeLeaf();
728
28.1k
}
729
730
42.1k
RopePieceBTree::~RopePieceBTree() {
731
42.1k
  getRoot(Root)->Destroy();
732
42.1k
}
733
734
202k
unsigned RopePieceBTree::size() const {
735
202k
  return getRoot(Root)->size();
736
202k
}
737
738
14.0k
void RopePieceBTree::clear() {
739
14.0k
  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
740
14.0k
    Leaf->clear();
741
0
  else {
742
0
    getRoot(Root)->Destroy();
743
0
    Root = new RopePieceBTreeLeaf();
744
0
  }
745
14.0k
}
746
747
137k
void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
748
137k
  // #1. Split at Offset.
749
137k
  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
750
93
    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
751
137k
752
137k
  // #2. Do the insertion.
753
137k
  if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
754
978
    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
755
137k
}
756
757
45.3k
void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
758
45.3k
  // #1. Split at Offset.
759
45.3k
  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
760
166
    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
761
45.3k
762
45.3k
  // #2. Do the erasing.
763
45.3k
  getRoot(Root)->erase(Offset, NumBytes);
764
45.3k
}
765
766
//===----------------------------------------------------------------------===//
767
// RewriteRope Implementation
768
//===----------------------------------------------------------------------===//
769
770
/// MakeRopeString - This copies the specified byte range into some instance of
771
/// RopeRefCountString, and return a RopePiece that represents it.  This uses
772
/// the AllocBuffer object to aggregate requests for small strings into one
773
/// allocation instead of doing tons of tiny allocations.
774
137k
RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
775
137k
  unsigned Len = End-Start;
776
137k
  assert(Len && "Zero length RopePiece is invalid!");
777
137k
778
137k
  // If we have space for this string in the current alloc buffer, use it.
779
137k
  if (AllocOffs+Len <= AllocChunkSize) {
780
122k
    memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
781
122k
    AllocOffs += Len;
782
122k
    return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
783
122k
  }
784
15.2k
785
15.2k
  // If we don't have enough room because this specific allocation is huge,
786
15.2k
  // just allocate a new rope piece for it alone.
787
15.2k
  if (Len > AllocChunkSize) {
788
268
    unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
789
268
    auto *Res = reinterpret_cast<RopeRefCountString *>(new char[Size]);
790
268
    Res->RefCount = 0;
791
268
    memcpy(Res->Data, Start, End-Start);
792
268
    return RopePiece(Res, 0, End-Start);
793
268
  }
794
15.0k
795
15.0k
  // Otherwise, this was a small request but we just don't have space for it
796
15.0k
  // Make a new chunk and share it with later allocations.
797
15.0k
798
15.0k
  unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
799
15.0k
  auto *Res = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
800
15.0k
  Res->RefCount = 0;
801
15.0k
  memcpy(Res->Data, Start, Len);
802
15.0k
  AllocBuffer = Res;
803
15.0k
  AllocOffs = Len;
804
15.0k
805
15.0k
  return RopePiece(AllocBuffer, 0, Len);
806
15.0k
}