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