Bug Summary

File:src/gnu/usr.bin/clang/libclangRewrite/../../../llvm/clang/lib/Rewrite/DeltaTree.cpp
Warning:line 244, 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 -cc1 -triple amd64-unknown-openbsd7.0 -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 -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libclangRewrite/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libclangRewrite/../../../llvm/clang/include -I /usr/src/gnu/usr.bin/clang/libclangRewrite/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libclangRewrite/../include -I /usr/src/gnu/usr.bin/clang/libclangRewrite/obj -I /usr/src/gnu/usr.bin/clang/libclangRewrite/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libclangRewrite/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libclangRewrite/../../../llvm/clang/lib/Rewrite/DeltaTree.cpp
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
19using 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
36namespace {
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; }
31
←
Returning zero, 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 #")((void)0);
97 return Values[i];
98 }
99
100 SourceDelta &getValue(unsigned i) {
101 assert(i < NumValuesUsed && "Invalid value #")((void)0);
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")((void)0);
147 return Children[i];
148 }
149
150 DeltaTreeNode *getChild(unsigned i) {
151 assert(i < getNumValuesUsed()+1 && "Invalid child")((void)0);
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.
161void 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.
170void 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.
184bool 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)
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'
→
14
←
Loop condition is false. Execution continues on line 196
→
24
←
Assuming 'i' is equal to 'e'
→
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
2.1
'i' is equal to 'e'
7.1
'i' is equal to 'e'
14.1
'i' is not equal to 'e'
24.1
'i' is equal to 'e'
 != e && getValue(i).FileLoc == FileIndex) {
15
←
Assuming 'FileIndex' is not equal to field 'FileLoc'
→
16
←
Taking false branch
→
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()) {
3
←
Assuming the condition is false
→
4
←
Taking false branch
→
8
←
Assuming the condition is false
→
9
←
Taking false branch
→
17
←
Assuming the condition is true
→
18
←
Taking true branch
→
25
←
Assuming the condition is false
→
26
←
Taking false branch
→
208 if (!isFull()) {
19
←
Taking false branch
→
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")((void)0);
221 DoSplit(*InsertRes);
222
223 if (InsertRes->Split.FileLoc > FileIndex)
20
←
Assuming 'FileIndex' is >= field 'FileLoc'
→
21
←
Taking false branch
→
224 InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
225 else
226 InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);
22
←
Passing null pointer value via 3rd parameter 'InsertRes'
→
23
←
Calling 'DeltaTreeNode::DoInsertion'
→
227 return true;
228 }
229
230 // Otherwise, this is an interior node. Send the request down the tree.
231 auto *IN = cast<DeltaTreeInteriorNode>(this);
5
←
The object is a 'DeltaTreeInteriorNode'
→
10
←
The object is a 'DeltaTreeInteriorNode'
→
27
←
The object is a 'DeltaTreeInteriorNode'
→
232 if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
6
←
Calling 'DeltaTreeNode::DoInsertion'
→
11
←
Calling 'DeltaTreeNode::DoInsertion'
→
28
←
Assuming the condition is false
→
29
←
Taking false branch
→
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()) {
30
←
Calling 'DeltaTreeNode::isFull'
→
32
←
Returning from 'DeltaTreeNode::isFull'
→
33
←
Taking true branch
→
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
33.1
'i' is equal to 'e'
 != e)
34
←
Taking false branch
→
242 memmove(&IN->Children[i+2], &IN->Children[i+1],
243 (e-i)*sizeof(IN->Children[0]));
244 IN->Children[i] = InsertRes->LHS;
35
←
Access to field 'LHS' results in a dereference of a null pointer (loaded from variable 'InsertRes')
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.
298void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
299 assert(isFull() && "Why split a non-full node?")((void)0);
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.
345static 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)((void)0);
354 FullDelta += N->getValue(i).Delta;
355 }
356 assert(FullDelta == N->getFullDelta())((void)0);
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)((void)0);
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 <((void)0)
373 IVal.FileLoc)((void)0);
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)((void)0);
377 VerifyTree(IChild);
378 }
379
380 FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
381
382 assert(FullDelta == N->getFullDelta())((void)0);
383}
384#endif // VERIFY_TREE
385
386static DeltaTreeNode *getRoot(void *Root) {
387 return (DeltaTreeNode*)Root;
388}
389
390DeltaTree::DeltaTree() {
391 Root = new DeltaTreeNode();
392}
393
394DeltaTree::DeltaTree(const DeltaTree &RHS) {
395 // Currently we only support copying when the RHS is empty.
396 assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&((void)0)
397 "Can only copy empty tree")((void)0);
398 Root = new DeltaTreeNode();
399}
400
401DeltaTree::~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.
408int 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.
455void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
456 assert(Delta && "Adding a noop?")((void)0);
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}