Bug Summary

File:tools/clang/lib/Rewrite/DeltaTree.cpp
Warning:line 245, column 23
Access to field 'LHS' results in a dereference of a null pointer (loaded from variable 'InsertRes')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeltaTree.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/clang/lib/Rewrite -I /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite -I /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/clang/lib/Rewrite -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp -faddrsig
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
20using 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
37namespace {
38
39 /// SourceDelta - As code in the original input buffer is added and deleted,
40 /// SourceDelta records are used to keep track of how the input SourceLocation
41 /// object is mapped into the output buffer.
42 struct SourceDelta {
43 unsigned FileLoc;
44 int Delta;
45
46 static SourceDelta get(unsigned Loc, int D) {
47 SourceDelta Delta;
48 Delta.FileLoc = Loc;
49 Delta.Delta = D;
50 return Delta;
51 }
52 };
53
54 /// DeltaTreeNode - The common part of all nodes.
55 ///
56 class DeltaTreeNode {
57 public:
58 struct InsertResult {
59 DeltaTreeNode *LHS, *RHS;
60 SourceDelta Split;
61 };
62
63 private:
64 friend class DeltaTreeInteriorNode;
65
66 /// WidthFactor - This controls the number of K/V slots held in the BTree:
67 /// how wide it is. Each level of the BTree is guaranteed to have at least
68 /// WidthFactor-1 K/V pairs (except the root) and may have at most
69 /// 2*WidthFactor-1 K/V pairs.
70 enum { WidthFactor = 8 };
71
72 /// Values - This tracks the SourceDelta's currently in this node.
73 SourceDelta Values[2*WidthFactor-1];
74
75 /// NumValuesUsed - This tracks the number of values this node currently
76 /// holds.
77 unsigned char NumValuesUsed = 0;
78
79 /// IsLeaf - This is true if this is a leaf of the btree. If false, this is
80 /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
81 bool IsLeaf;
82
83 /// FullDelta - This is the full delta of all the values in this node and
84 /// all children nodes.
85 int FullDelta = 0;
86
87 public:
88 DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {}
89
90 bool isLeaf() const { return IsLeaf; }
91 int getFullDelta() const { return FullDelta; }
92 bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
93
94 unsigned getNumValuesUsed() const { return NumValuesUsed; }
95
96 const SourceDelta &getValue(unsigned i) const {
97 assert(i < NumValuesUsed && "Invalid value #")((i < NumValuesUsed && "Invalid value #") ? static_cast
<void> (0) : __assert_fail ("i < NumValuesUsed && \"Invalid value #\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 97, __PRETTY_FUNCTION__))
;
98 return Values[i];
99 }
100
101 SourceDelta &getValue(unsigned i) {
102 assert(i < NumValuesUsed && "Invalid value #")((i < NumValuesUsed && "Invalid value #") ? static_cast
<void> (0) : __assert_fail ("i < NumValuesUsed && \"Invalid value #\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 102, __PRETTY_FUNCTION__))
;
103 return Values[i];
104 }
105
106 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
107 /// this node. If insertion is easy, do it and return false. Otherwise,
108 /// split the node, populate InsertRes with info about the split, and return
109 /// true.
110 bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
111
112 void DoSplit(InsertResult &InsertRes);
113
114
115 /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
116 /// local walk over our contained deltas.
117 void RecomputeFullDeltaLocally();
118
119 void Destroy();
120 };
121
122 /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
123 /// This class tracks them.
124 class DeltaTreeInteriorNode : public DeltaTreeNode {
125 friend class DeltaTreeNode;
126
127 DeltaTreeNode *Children[2*WidthFactor];
128
129 ~DeltaTreeInteriorNode() {
130 for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
131 Children[i]->Destroy();
132 }
133
134 public:
135 DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
136
137 DeltaTreeInteriorNode(const InsertResult &IR)
138 : DeltaTreeNode(false /*nonleaf*/) {
139 Children[0] = IR.LHS;
140 Children[1] = IR.RHS;
141 Values[0] = IR.Split;
142 FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
143 NumValuesUsed = 1;
144 }
145
146 const DeltaTreeNode *getChild(unsigned i) const {
147 assert(i < getNumValuesUsed()+1 && "Invalid child")((i < getNumValuesUsed()+1 && "Invalid child") ? static_cast
<void> (0) : __assert_fail ("i < getNumValuesUsed()+1 && \"Invalid child\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 147, __PRETTY_FUNCTION__))
;
148 return Children[i];
149 }
150
151 DeltaTreeNode *getChild(unsigned i) {
152 assert(i < getNumValuesUsed()+1 && "Invalid child")((i < getNumValuesUsed()+1 && "Invalid child") ? static_cast
<void> (0) : __assert_fail ("i < getNumValuesUsed()+1 && \"Invalid child\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 152, __PRETTY_FUNCTION__))
;
153 return Children[i];
154 }
155
156 static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
157 };
158
159} // namespace
160
161/// Destroy - A 'virtual' destructor.
162void DeltaTreeNode::Destroy() {
163 if (isLeaf())
164 delete this;
165 else
166 delete cast<DeltaTreeInteriorNode>(this);
167}
168
169/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
170/// local walk over our contained deltas.
171void DeltaTreeNode::RecomputeFullDeltaLocally() {
172 int NewFullDelta = 0;
173 for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
174 NewFullDelta += Values[i].Delta;
175 if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this))
176 for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
177 NewFullDelta += IN->getChild(i)->getFullDelta();
178 FullDelta = NewFullDelta;
179}
180
181/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
182/// this node. If insertion is easy, do it and return false. Otherwise,
183/// split the node, populate InsertRes with info about the split, and return
184/// true.
185bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
186 InsertResult *InsertRes) {
187 // Maintain full delta for this node.
188 FullDelta += Delta;
189
190 // Find the insertion point, the first delta whose index is >= FileIndex.
191 unsigned i = 0, e = getNumValuesUsed();
192 while (i != e && FileIndex > getValue(i).FileLoc)
2
Assuming 'i' is equal to 'e'
6
Assuming 'i' is equal to 'e'
10
Assuming 'i' is not equal to 'e'
11
Assuming the condition is false
12
Loop condition is false. Execution continues on line 197
22
Assuming 'i' is equal to 'e'
193 ++i;
194
195 // If we found an a record for exactly this file index, just merge this
196 // value into the pre-existing record and finish early.
197 if (i != e && getValue(i).FileLoc == FileIndex) {
13
Assuming the condition is false
14
Taking false branch
198 // NOTE: Delta could drop to zero here. This means that the delta entry is
199 // useless and could be removed. Supporting erases is more complex than
200 // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
201 // the tree.
202 Values[i].Delta += Delta;
203 return false;
204 }
205
206 // Otherwise, we found an insertion point, and we know that the value at the
207 // specified index is > FileIndex. Handle the leaf case first.
208 if (isLeaf()) {
3
Assuming the condition is false
4
Taking false branch
7
Assuming the condition is false
8
Taking false branch
15
Assuming the condition is true
16
Taking true branch
23
Assuming the condition is false
24
Taking false branch
209 if (!isFull()) {
17
Taking false branch
210 // For an insertion into a non-full leaf node, just insert the value in
211 // its sorted position. This requires moving later values over.
212 if (i != e)
213 memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
214 Values[i] = SourceDelta::get(FileIndex, Delta);
215 ++NumValuesUsed;
216 return false;
217 }
218
219 // Otherwise, if this is leaf is full, split the node at its median, insert
220 // the value into one of the children, and return the result.
221 assert(InsertRes && "No result location specified")((InsertRes && "No result location specified") ? static_cast
<void> (0) : __assert_fail ("InsertRes && \"No result location specified\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 221, __PRETTY_FUNCTION__))
;
222 DoSplit(*InsertRes);
223
224 if (InsertRes->Split.FileLoc > FileIndex)
18
Assuming the condition is false
19
Taking false branch
225 InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
226 else
227 InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
20
Passing null pointer value via 3rd parameter 'InsertRes'
21
Calling 'DeltaTreeNode::DoInsertion'
228 return true;
229 }
230
231 // Otherwise, this is an interior node. Send the request down the tree.
232 auto *IN = cast<DeltaTreeInteriorNode>(this);
233 if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
5
Calling 'DeltaTreeNode::DoInsertion'
9
Calling 'DeltaTreeNode::DoInsertion'
25
Assuming the condition is false
26
Taking false branch
234 return false; // If there was space in the child, just return.
235
236 // Okay, this split the subtree, producing a new value and two children to
237 // insert here. If this node is non-full, we can just insert it directly.
238 if (!isFull()) {
27
Taking true branch
239 // Now that we have two nodes and a new element, insert the perclated value
240 // into ourself by moving all the later values/children down, then inserting
241 // the new one.
242 if (i != e)
28
Taking false branch
243 memmove(&IN->Children[i+2], &IN->Children[i+1],
244 (e-i)*sizeof(IN->Children[0]));
245 IN->Children[i] = InsertRes->LHS;
29
Access to field 'LHS' results in a dereference of a null pointer (loaded from variable 'InsertRes')
246 IN->Children[i+1] = InsertRes->RHS;
247
248 if (e != i)
249 memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
250 Values[i] = InsertRes->Split;
251 ++NumValuesUsed;
252 return false;
253 }
254
255 // Finally, if this interior node was full and a node is percolated up, split
256 // ourself and return that up the chain. Start by saving all our info to
257 // avoid having the split clobber it.
258 IN->Children[i] = InsertRes->LHS;
259 DeltaTreeNode *SubRHS = InsertRes->RHS;
260 SourceDelta SubSplit = InsertRes->Split;
261
262 // Do the split.
263 DoSplit(*InsertRes);
264
265 // Figure out where to insert SubRHS/NewSplit.
266 DeltaTreeInteriorNode *InsertSide;
267 if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
268 InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
269 else
270 InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
271
272 // We now have a non-empty interior node 'InsertSide' to insert
273 // SubRHS/SubSplit into. Find out where to insert SubSplit.
274
275 // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
276 i = 0; e = InsertSide->getNumValuesUsed();
277 while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
278 ++i;
279
280 // Now we know that i is the place to insert the split value into. Insert it
281 // and the child right after it.
282 if (i != e)
283 memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
284 (e-i)*sizeof(IN->Children[0]));
285 InsertSide->Children[i+1] = SubRHS;
286
287 if (e != i)
288 memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
289 (e-i)*sizeof(Values[0]));
290 InsertSide->Values[i] = SubSplit;
291 ++InsertSide->NumValuesUsed;
292 InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
293 return true;
294}
295
296/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
297/// into two subtrees each with "WidthFactor-1" values and a pivot value.
298/// Return the pieces in InsertRes.
299void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
300 assert(isFull() && "Why split a non-full node?")((isFull() && "Why split a non-full node?") ? static_cast
<void> (0) : __assert_fail ("isFull() && \"Why split a non-full node?\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 300, __PRETTY_FUNCTION__))
;
301
302 // Since this node is full, it contains 2*WidthFactor-1 values. We move
303 // the first 'WidthFactor-1' values to the LHS child (which we leave in this
304 // node), propagate one value up, and move the last 'WidthFactor-1' values
305 // into the RHS child.
306
307 // Create the new child node.
308 DeltaTreeNode *NewNode;
309 if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
310 // If this is an interior node, also move over 'WidthFactor' children
311 // into the new node.
312 DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
313 memcpy(&New->Children[0], &IN->Children[WidthFactor],
314 WidthFactor*sizeof(IN->Children[0]));
315 NewNode = New;
316 } else {
317 // Just create the new leaf node.
318 NewNode = new DeltaTreeNode();
319 }
320
321 // Move over the last 'WidthFactor-1' values from here to NewNode.
322 memcpy(&NewNode->Values[0], &Values[WidthFactor],
323 (WidthFactor-1)*sizeof(Values[0]));
324
325 // Decrease the number of values in the two nodes.
326 NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
327
328 // Recompute the two nodes' full delta.
329 NewNode->RecomputeFullDeltaLocally();
330 RecomputeFullDeltaLocally();
331
332 InsertRes.LHS = this;
333 InsertRes.RHS = NewNode;
334 InsertRes.Split = Values[WidthFactor-1];
335}
336
337//===----------------------------------------------------------------------===//
338// DeltaTree Implementation
339//===----------------------------------------------------------------------===//
340
341//#define VERIFY_TREE
342
343#ifdef VERIFY_TREE
344/// VerifyTree - Walk the btree performing assertions on various properties to
345/// verify consistency. This is useful for debugging new changes to the tree.
346static 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)((N->getValue(i-1).FileLoc < N->getValue(i).FileLoc)
? static_cast<void> (0) : __assert_fail ("N->getValue(i-1).FileLoc < N->getValue(i).FileLoc"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 354, __PRETTY_FUNCTION__))
;
355 FullDelta += N->getValue(i).Delta;
356 }
357 assert(FullDelta == N->getFullDelta())((FullDelta == N->getFullDelta()) ? static_cast<void>
(0) : __assert_fail ("FullDelta == N->getFullDelta()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 357, __PRETTY_FUNCTION__))
;
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)((IN->getValue(i-1).FileLoc < IVal.FileLoc) ? static_cast
<void> (0) : __assert_fail ("IN->getValue(i-1).FileLoc < IVal.FileLoc"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 368, __PRETTY_FUNCTION__))
;
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 <((IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc
< IVal.FileLoc) ? static_cast<void> (0) : __assert_fail
("IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < IVal.FileLoc"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 374, __PRETTY_FUNCTION__))
374 IVal.FileLoc)((IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc
< IVal.FileLoc) ? static_cast<void> (0) : __assert_fail
("IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < IVal.FileLoc"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 374, __PRETTY_FUNCTION__))
;
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)((IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc
) ? static_cast<void> (0) : __assert_fail ("IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 377, __PRETTY_FUNCTION__))
;
378 VerifyTree(IChild);
379 }
380
381 FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
382
383 assert(FullDelta == N->getFullDelta())((FullDelta == N->getFullDelta()) ? static_cast<void>
(0) : __assert_fail ("FullDelta == N->getFullDelta()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 383, __PRETTY_FUNCTION__))
;
384}
385#endif // VERIFY_TREE
386
387static DeltaTreeNode *getRoot(void *Root) {
388 return (DeltaTreeNode*)Root;
389}
390
391DeltaTree::DeltaTree() {
392 Root = new DeltaTreeNode();
393}
394
395DeltaTree::DeltaTree(const DeltaTree &RHS) {
396 // Currently we only support copying when the RHS is empty.
397 assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&((getRoot(RHS.Root)->getNumValuesUsed() == 0 && "Can only copy empty tree"
) ? static_cast<void> (0) : __assert_fail ("getRoot(RHS.Root)->getNumValuesUsed() == 0 && \"Can only copy empty tree\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 398, __PRETTY_FUNCTION__))
398 "Can only copy empty tree")((getRoot(RHS.Root)->getNumValuesUsed() == 0 && "Can only copy empty tree"
) ? static_cast<void> (0) : __assert_fail ("getRoot(RHS.Root)->getNumValuesUsed() == 0 && \"Can only copy empty tree\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 398, __PRETTY_FUNCTION__))
;
399 Root = new DeltaTreeNode();
400}
401
402DeltaTree::~DeltaTree() {
403 getRoot(Root)->Destroy();
404}
405
406/// getDeltaAt - Return the accumulated delta at the specified file offset.
407/// This includes all insertions or delections that occurred *before* the
408/// specified file index.
409int DeltaTree::getDeltaAt(unsigned FileIndex) const {
410 const DeltaTreeNode *Node = getRoot(Root);
411
412 int Result = 0;
413
414 // Walk down the tree.
415 while (true) {
416 // For all nodes, include any local deltas before the specified file
417 // index by summing them up directly. Keep track of how many were
418 // included.
419 unsigned NumValsGreater = 0;
420 for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
421 ++NumValsGreater) {
422 const SourceDelta &Val = Node->getValue(NumValsGreater);
423
424 if (Val.FileLoc >= FileIndex)
425 break;
426 Result += Val.Delta;
427 }
428
429 // If we have an interior node, include information about children and
430 // recurse. Otherwise, if we have a leaf, we're done.
431 const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
432 if (!IN) return Result;
433
434 // Include any children to the left of the values we skipped, all of
435 // their deltas should be included as well.
436 for (unsigned i = 0; i != NumValsGreater; ++i)
437 Result += IN->getChild(i)->getFullDelta();
438
439 // If we found exactly the value we were looking for, break off the
440 // search early. There is no need to search the RHS of the value for
441 // partial results.
442 if (NumValsGreater != Node->getNumValuesUsed() &&
443 Node->getValue(NumValsGreater).FileLoc == FileIndex)
444 return Result+IN->getChild(NumValsGreater)->getFullDelta();
445
446 // Otherwise, traverse down the tree. The selected subtree may be
447 // partially included in the range.
448 Node = IN->getChild(NumValsGreater);
449 }
450 // NOT REACHED.
451}
452
453/// AddDelta - When a change is made that shifts around the text buffer,
454/// this method is used to record that info. It inserts a delta of 'Delta'
455/// into the current DeltaTree at offset FileIndex.
456void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
457 assert(Delta && "Adding a noop?")((Delta && "Adding a noop?") ? static_cast<void>
(0) : __assert_fail ("Delta && \"Adding a noop?\"", "/build/llvm-toolchain-snapshot-8~svn345461/tools/clang/lib/Rewrite/DeltaTree.cpp"
, 457, __PRETTY_FUNCTION__))
;
458 DeltaTreeNode *MyRoot = getRoot(Root);
459
460 DeltaTreeNode::InsertResult InsertRes;
461 if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
1
Calling 'DeltaTreeNode::DoInsertion'
462 Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
463 }
464
465#ifdef VERIFY_TREE
466 VerifyTree(MyRoot);
467#endif
468}