clang -cc1 -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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -relaxed-aliasing -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/clang/lib/Rewrite -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/clang/lib/Rewrite -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/clang/lib/Rewrite -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/clang/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/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-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/clang/lib/Rewrite -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/clang/lib/Rewrite/DeltaTree.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
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 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | namespace { |
37 | |
38 | |
39 | |
40 | |
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 | |
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 | |
66 | |
67 | |
68 | |
69 | enum { WidthFactor = 8 }; |
70 | |
71 | |
72 | SourceDelta Values[2*WidthFactor-1]; |
73 | |
74 | |
75 | |
76 | unsigned char NumValuesUsed = 0; |
77 | |
78 | |
79 | |
80 | bool IsLeaf; |
81 | |
82 | |
83 | |
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; } |
| 30 | | Assuming the condition is true | |
|
| 31 | | Returning the value 1, which participates in a condition later | |
|
92 | |
93 | unsigned getNumValuesUsed() const { return NumValuesUsed; } |
94 | |
95 | const SourceDelta &getValue(unsigned i) const { |
96 | assert(i < NumValuesUsed && "Invalid value #"); |
97 | return Values[i]; |
98 | } |
99 | |
100 | SourceDelta &getValue(unsigned i) { |
101 | assert(i < NumValuesUsed && "Invalid value #"); |
102 | return Values[i]; |
103 | } |
104 | |
105 | |
106 | |
107 | |
108 | |
109 | bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); |
110 | |
111 | void DoSplit(InsertResult &InsertRes); |
112 | |
113 | |
114 | |
115 | |
116 | void RecomputeFullDeltaLocally(); |
117 | |
118 | void Destroy(); |
119 | }; |
120 | |
121 | |
122 | |
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 ) {} |
135 | |
136 | DeltaTreeInteriorNode(const InsertResult &IR) |
137 | : DeltaTreeNode(false ) { |
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"); |
147 | return Children[i]; |
148 | } |
149 | |
150 | DeltaTreeNode *getChild(unsigned i) { |
151 | assert(i < getNumValuesUsed()+1 && "Invalid child"); |
152 | return Children[i]; |
153 | } |
154 | |
155 | static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } |
156 | }; |
157 | |
158 | } |
159 | |
160 | |
161 | void DeltaTreeNode::Destroy() { |
162 | if (isLeaf()) |
163 | delete this; |
164 | else |
165 | delete cast<DeltaTreeInteriorNode>(this); |
166 | } |
167 | |
168 | |
169 | |
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 | |
181 | |
182 | |
183 | |
184 | bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, |
185 | InsertResult *InsertRes) { |
186 | |
187 | FullDelta += Delta; |
188 | |
189 | |
190 | unsigned i = 0, e = getNumValuesUsed(); |
191 | while (i != e && FileIndex > getValue(i).FileLoc) |
| 2 | | Assuming 'i' is equal to 'e' | |
|
| 7 | | Assuming 'i' is equal to 'e' | |
|
| 12 | | Assuming 'i' is not equal to 'e' | |
|
| 13 | | Assuming 'FileIndex' is <= field 'FileLoc' | |
|
| 23 | | Assuming 'i' is not equal to 'e' | |
|
| 24 | | Assuming 'FileIndex' is <= field 'FileLoc' | |
|
192 | ++i; |
193 | |
194 | |
195 | |
196 | if (i != e && getValue(i).FileLoc == FileIndex) { |
| 14 | | Assuming 'FileIndex' is not equal to field 'FileLoc' | |
|
| |
| 25 | | Assuming 'FileIndex' is not equal to field 'FileLoc' | |
|
| |
197 | |
198 | |
199 | |
200 | |
201 | Values[i].Delta += Delta; |
202 | return false; |
203 | } |
204 | |
205 | |
206 | |
207 | if (isLeaf()) { |
| 3 | | Assuming the condition is false | |
|
| |
| 8 | | Assuming the condition is false | |
|
| |
| 16 | | Assuming the condition is true | |
|
| |
| 27 | | Assuming the condition is true | |
|
| |
208 | if (!isFull()) { |
| |
| 29 | | Calling 'DeltaTreeNode::isFull' | |
|
| 32 | | Returning from 'DeltaTreeNode::isFull' | |
|
| |
209 | |
210 | |
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 | |
219 | |
220 | assert(InsertRes && "No result location specified"); |
221 | DoSplit(*InsertRes); |
| 34 | | Forming reference to null pointer |
|
222 | |
223 | if (InsertRes->Split.FileLoc > FileIndex) |
| 19 | | Assuming 'FileIndex' is >= field 'FileLoc' | |
|
| |
224 | InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr ); |
225 | else |
226 | InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr ); |
| 21 | | Passing null pointer value via 3rd parameter 'InsertRes' | |
|
| 22 | | Calling 'DeltaTreeNode::DoInsertion' | |
|
227 | return true; |
228 | } |
229 | |
230 | |
231 | auto *IN = cast<DeltaTreeInteriorNode>(this); |
| 5 | | The object is a 'DeltaTreeInteriorNode' | |
|
| 10 | | The object is a 'DeltaTreeInteriorNode' | |
|
232 | if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) |
| 6 | | Calling 'DeltaTreeNode::DoInsertion' | |
|
| 11 | | Calling 'DeltaTreeNode::DoInsertion' | |
|
233 | return false; |
234 | |
235 | |
236 | |
237 | if (!isFull()) { |
238 | |
239 | |
240 | |
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 | |
255 | |
256 | |
257 | IN->Children[i] = InsertRes->LHS; |
258 | DeltaTreeNode *SubRHS = InsertRes->RHS; |
259 | SourceDelta SubSplit = InsertRes->Split; |
260 | |
261 | |
262 | DoSplit(*InsertRes); |
263 | |
264 | |
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 | |
272 | |
273 | |
274 | |
275 | i = 0; e = InsertSide->getNumValuesUsed(); |
276 | while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) |
277 | ++i; |
278 | |
279 | |
280 | |
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 | |
296 | |
297 | |
298 | void DeltaTreeNode::DoSplit(InsertResult &InsertRes) { |
299 | assert(isFull() && "Why split a non-full node?"); |
300 | |
301 | |
302 | |
303 | |
304 | |
305 | |
306 | |
307 | DeltaTreeNode *NewNode; |
308 | if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { |
309 | |
310 | |
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 | |
317 | NewNode = new DeltaTreeNode(); |
318 | } |
319 | |
320 | |
321 | memcpy(&NewNode->Values[0], &Values[WidthFactor], |
322 | (WidthFactor-1)*sizeof(Values[0])); |
323 | |
324 | |
325 | NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; |
326 | |
327 | |
328 | NewNode->RecomputeFullDeltaLocally(); |
329 | RecomputeFullDeltaLocally(); |
330 | |
331 | InsertRes.LHS = this; |
332 | InsertRes.RHS = NewNode; |
333 | InsertRes.Split = Values[WidthFactor-1]; |
334 | } |
335 | |
336 | |
337 | |
338 | |
339 | |
340 | |
341 | |
342 | #ifdef VERIFY_TREE |
343 | |
344 | |
345 | static void VerifyTree(const DeltaTreeNode *N) { |
346 | const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N); |
347 | if (IN == 0) { |
348 | |
349 | |
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 | |
361 | |
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 | |
372 | assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < |
373 | IVal.FileLoc); |
374 | |
375 | |
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 | 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 | |
396 | assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && |
397 | "Can only copy empty tree"); |
398 | Root = new DeltaTreeNode(); |
399 | } |
400 | |
401 | DeltaTree::~DeltaTree() { |
402 | getRoot(Root)->Destroy(); |
403 | } |
404 | |
405 | |
406 | |
407 | |
408 | int DeltaTree::getDeltaAt(unsigned FileIndex) const { |
409 | const DeltaTreeNode *Node = getRoot(Root); |
410 | |
411 | int Result = 0; |
412 | |
413 | |
414 | while (true) { |
415 | |
416 | |
417 | |
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 | |
429 | |
430 | const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node); |
431 | if (!IN) return Result; |
432 | |
433 | |
434 | |
435 | for (unsigned i = 0; i != NumValsGreater; ++i) |
436 | Result += IN->getChild(i)->getFullDelta(); |
437 | |
438 | |
439 | |
440 | |
441 | if (NumValsGreater != Node->getNumValuesUsed() && |
442 | Node->getValue(NumValsGreater).FileLoc == FileIndex) |
443 | return Result+IN->getChild(NumValsGreater)->getFullDelta(); |
444 | |
445 | |
446 | |
447 | Node = IN->getChild(NumValsGreater); |
448 | } |
449 | |
450 | } |
451 | |
452 | |
453 | |
454 | |
455 | void DeltaTree::AddDelta(unsigned FileIndex, int Delta) { |
456 | assert(Delta && "Adding a noop?"); |
457 | DeltaTreeNode *MyRoot = getRoot(Root); |
458 | |
459 | DeltaTreeNode::InsertResult InsertRes; |
460 | if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { |
| 1 | Calling 'DeltaTreeNode::DoInsertion' | |
|
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 | } |