1//===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===//
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 defines a meta-engine for path-sensitive dataflow analysis that
10// is built on CoreEngine, but provides the boilerplate to execute transfer
11// functions and build the ExplodedGraph at the expression level.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
16#include "PrettyStackTraceLocationContext.h"
17#include "clang/AST/ASTContext.h"
18#include "clang/AST/Decl.h"
19#include "clang/AST/DeclBase.h"
20#include "clang/AST/DeclCXX.h"
21#include "clang/AST/DeclObjC.h"
22#include "clang/AST/Expr.h"
23#include "clang/AST/ExprCXX.h"
24#include "clang/AST/ExprObjC.h"
25#include "clang/AST/ParentMap.h"
26#include "clang/AST/PrettyPrinter.h"
27#include "clang/AST/Stmt.h"
28#include "clang/AST/StmtCXX.h"
29#include "clang/AST/StmtObjC.h"
30#include "clang/AST/Type.h"
31#include "clang/Analysis/AnalysisDeclContext.h"
32#include "clang/Analysis/CFG.h"
33#include "clang/Analysis/ConstructionContext.h"
34#include "clang/Analysis/ProgramPoint.h"
35#include "clang/Basic/IdentifierTable.h"
36#include "clang/Basic/JsonSupport.h"
37#include "clang/Basic/LLVM.h"
38#include "clang/Basic/LangOptions.h"
39#include "clang/Basic/PrettyStackTrace.h"
40#include "clang/Basic/SourceLocation.h"
41#include "clang/Basic/Specifiers.h"
42#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
43#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
44#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
45#include "clang/StaticAnalyzer/Core/CheckerManager.h"
46#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
47#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
48#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
49#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
50#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
51#include "clang/StaticAnalyzer/Core/PathSensitive/EntryPointStats.h"
52#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
53#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
54#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
55#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
56#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
57#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
58#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
59#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
60#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
61#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
62#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
63#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
64#include "llvm/ADT/APSInt.h"
65#include "llvm/ADT/DenseMap.h"
66#include "llvm/ADT/ImmutableMap.h"
67#include "llvm/ADT/ImmutableSet.h"
68#include "llvm/ADT/STLExtras.h"
69#include "llvm/ADT/SmallVector.h"
70#include "llvm/Support/Casting.h"
71#include "llvm/Support/Compiler.h"
72#include "llvm/Support/DOTGraphTraits.h"
73#include "llvm/Support/ErrorHandling.h"
74#include "llvm/Support/GraphWriter.h"
75#include "llvm/Support/IOSandbox.h"
76#include "llvm/Support/TimeProfiler.h"
77#include "llvm/Support/raw_ostream.h"
78#include <cassert>
79#include <cstdint>
80#include <memory>
81#include <optional>
82#include <string>
83#include <tuple>
84#include <utility>
85#include <vector>
86
87using namespace clang;
88using namespace ento;
89
90#define DEBUG_TYPE "ExprEngine"
91
92STAT_COUNTER(NumRemoveDeadBindings,
93 "The # of times RemoveDeadBindings is called");
94STAT_COUNTER(
95 NumMaxBlockCountReached,
96 "The # of aborted paths due to reaching the maximum block count in "
97 "a top level function");
98STAT_COUNTER(
99 NumMaxBlockCountReachedInInlined,
100 "The # of aborted paths due to reaching the maximum block count in "
101 "an inlined function");
102STAT_COUNTER(NumTimesRetriedWithoutInlining,
103 "The # of times we re-evaluated a call without inlining");
104
105//===----------------------------------------------------------------------===//
106// Internal program state traits.
107//===----------------------------------------------------------------------===//
108
109namespace {
110
111// When modeling a C++ constructor, for a variety of reasons we need to track
112// the location of the object for the duration of its ConstructionContext.
113// ObjectsUnderConstruction maps statements within the construction context
114// to the object's location, so that on every such statement the location
115// could have been retrieved.
116
117/// ConstructedObjectKey is used for being able to find the path-sensitive
118/// memory region of a freshly constructed object while modeling the AST node
119/// that syntactically represents the object that is being constructed.
120/// Semantics of such nodes may sometimes require access to the region that's
121/// not otherwise present in the program state, or to the very fact that
122/// the construction context was present and contained references to these
123/// AST nodes.
124class ConstructedObjectKey {
125 using ConstructedObjectKeyImpl =
126 std::pair<ConstructionContextItem, const LocationContext *>;
127 const ConstructedObjectKeyImpl Impl;
128
129public:
130 explicit ConstructedObjectKey(const ConstructionContextItem &Item,
131 const LocationContext *LC)
132 : Impl(Item, LC) {}
133
134 const ConstructionContextItem &getItem() const { return Impl.first; }
135 const LocationContext *getLocationContext() const { return Impl.second; }
136
137 ASTContext &getASTContext() const {
138 return getLocationContext()->getDecl()->getASTContext();
139 }
140
141 void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,
142 PrintingPolicy &PP) const {
143 const Stmt *S = getItem().getStmtOrNull();
144 const CXXCtorInitializer *I = nullptr;
145 if (!S)
146 I = getItem().getCXXCtorInitializer();
147
148 if (S)
149 Out << "\"stmt_id\": " << S->getID(Context: getASTContext());
150 else
151 Out << "\"init_id\": " << I->getID(Context: getASTContext());
152
153 // Kind
154 Out << ", \"kind\": \"" << getItem().getKindAsString()
155 << "\", \"argument_index\": ";
156
157 if (getItem().getKind() == ConstructionContextItem::ArgumentKind)
158 Out << getItem().getIndex();
159 else
160 Out << "null";
161
162 // Pretty-print
163 Out << ", \"pretty\": ";
164
165 if (S) {
166 S->printJson(Out, Helper, Policy: PP, /*AddQuotes=*/true);
167 } else {
168 Out << '\"' << I->getAnyMember()->getDeclName() << '\"';
169 }
170 }
171
172 void Profile(llvm::FoldingSetNodeID &ID) const {
173 ID.Add(x: Impl.first);
174 ID.AddPointer(Ptr: Impl.second);
175 }
176
177 bool operator==(const ConstructedObjectKey &RHS) const {
178 return Impl == RHS.Impl;
179 }
180
181 bool operator<(const ConstructedObjectKey &RHS) const {
182 return Impl < RHS.Impl;
183 }
184};
185} // namespace
186
187typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
188 ObjectsUnderConstructionMap;
189REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
190 ObjectsUnderConstructionMap)
191
192// This trait is responsible for storing the index of the element that is to be
193// constructed in the next iteration. As a result a CXXConstructExpr is only
194// stored if it is array type. Also the index is the index of the continuous
195// memory region, which is important for multi-dimensional arrays. E.g:: int
196// arr[2][2]; assume arr[1][1] will be the next element under construction, so
197// the index is 3.
198typedef llvm::ImmutableMap<
199 std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned>
200 IndexOfElementToConstructMap;
201REGISTER_TRAIT_WITH_PROGRAMSTATE(IndexOfElementToConstruct,
202 IndexOfElementToConstructMap)
203
204// This trait is responsible for holding our pending ArrayInitLoopExprs.
205// It pairs the LocationContext and the initializer CXXConstructExpr with
206// the size of the array that's being copy initialized.
207typedef llvm::ImmutableMap<
208 std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned>
209 PendingInitLoopMap;
210REGISTER_TRAIT_WITH_PROGRAMSTATE(PendingInitLoop, PendingInitLoopMap)
211
212typedef llvm::ImmutableMap<const LocationContext *, unsigned>
213 PendingArrayDestructionMap;
214REGISTER_TRAIT_WITH_PROGRAMSTATE(PendingArrayDestruction,
215 PendingArrayDestructionMap)
216
217//===----------------------------------------------------------------------===//
218// Engine construction and deletion.
219//===----------------------------------------------------------------------===//
220
221static const char* TagProviderName = "ExprEngine";
222
223ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
224 AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn,
225 FunctionSummariesTy *FS, InliningModes HowToInlineIn)
226 : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled),
227 AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
228 Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
229 StateMgr(getContext(), mgr.getStoreManagerCreator(),
230 mgr.getConstraintManagerCreator(), G.getAllocator(), this),
231 SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()),
232 svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),
233 BR(mgr, *this), VisitedCallees(VisitedCalleesIn),
234 HowToInline(HowToInlineIn) {
235 unsigned TrimInterval = mgr.options.GraphTrimInterval;
236 if (TrimInterval != 0) {
237 // Enable eager node reclamation when constructing the ExplodedGraph.
238 G.enableNodeReclamation(Interval: TrimInterval);
239 }
240}
241
242//===----------------------------------------------------------------------===//
243// Utility methods.
244//===----------------------------------------------------------------------===//
245
246ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
247 ProgramStateRef state = StateMgr.getInitialState(InitLoc);
248 const Decl *D = InitLoc->getDecl();
249
250 // Preconditions.
251 // FIXME: It would be nice if we had a more general mechanism to add
252 // such preconditions. Some day.
253 do {
254 if (const auto *FD = dyn_cast<FunctionDecl>(Val: D)) {
255 // Precondition: the first argument of 'main' is an integer guaranteed
256 // to be > 0.
257 const IdentifierInfo *II = FD->getIdentifier();
258 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
259 break;
260
261 const ParmVarDecl *PD = FD->getParamDecl(i: 0);
262 QualType T = PD->getType();
263 const auto *BT = dyn_cast<BuiltinType>(Val&: T);
264 if (!BT || !BT->isInteger())
265 break;
266
267 const MemRegion *R = state->getRegion(D: PD, LC: InitLoc);
268 if (!R)
269 break;
270
271 SVal V = state->getSVal(LV: loc::MemRegionVal(R));
272 SVal Constraint_untested = evalBinOp(ST: state, Op: BO_GT, LHS: V,
273 RHS: svalBuilder.makeZeroVal(type: T),
274 T: svalBuilder.getConditionType());
275
276 std::optional<DefinedOrUnknownSVal> Constraint =
277 Constraint_untested.getAs<DefinedOrUnknownSVal>();
278
279 if (!Constraint)
280 break;
281
282 if (ProgramStateRef newState = state->assume(Cond: *Constraint, Assumption: true))
283 state = newState;
284 }
285 break;
286 }
287 while (false);
288
289 if (const auto *MD = dyn_cast<ObjCMethodDecl>(Val: D)) {
290 // Precondition: 'self' is always non-null upon entry to an Objective-C
291 // method.
292 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
293 const MemRegion *R = state->getRegion(D: SelfD, LC: InitLoc);
294 SVal V = state->getSVal(LV: loc::MemRegionVal(R));
295
296 if (std::optional<Loc> LV = V.getAs<Loc>()) {
297 // Assume that the pointer value in 'self' is non-null.
298 state = state->assume(Cond: *LV, Assumption: true);
299 assert(state && "'self' cannot be null");
300 }
301 }
302
303 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: D)) {
304 if (MD->isImplicitObjectMemberFunction()) {
305 // Precondition: 'this' is always non-null upon entry to the
306 // top-level function. This is our starting assumption for
307 // analyzing an "open" program.
308 const StackFrameContext *SFC = InitLoc->getStackFrame();
309 if (SFC->getParent() == nullptr) {
310 loc::MemRegionVal L = svalBuilder.getCXXThis(D: MD, SFC);
311 SVal V = state->getSVal(LV: L);
312 if (std::optional<Loc> LV = V.getAs<Loc>()) {
313 state = state->assume(Cond: *LV, Assumption: true);
314 assert(state && "'this' cannot be null");
315 }
316 }
317 }
318 }
319
320 return state;
321}
322
323ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(
324 ProgramStateRef State, const LocationContext *LC,
325 const Expr *InitWithAdjustments, const Expr *Result,
326 const SubRegion **OutRegionWithAdjustments) {
327 // FIXME: This function is a hack that works around the quirky AST
328 // we're often having with respect to C++ temporaries. If only we modelled
329 // the actual execution order of statements properly in the CFG,
330 // all the hassle with adjustments would not be necessary,
331 // and perhaps the whole function would be removed.
332 SVal InitValWithAdjustments = State->getSVal(Ex: InitWithAdjustments, LCtx: LC);
333 if (!Result) {
334 // If we don't have an explicit result expression, we're in "if needed"
335 // mode. Only create a region if the current value is a NonLoc.
336 if (!isa<NonLoc>(Val: InitValWithAdjustments)) {
337 if (OutRegionWithAdjustments)
338 *OutRegionWithAdjustments = nullptr;
339 return State;
340 }
341 Result = InitWithAdjustments;
342 } else {
343 // We need to create a region no matter what. Make sure we don't try to
344 // stuff a Loc into a non-pointer temporary region.
345 assert(!isa<Loc>(InitValWithAdjustments) ||
346 Loc::isLocType(Result->getType()) ||
347 Result->getType()->isMemberPointerType());
348 }
349
350 ProgramStateManager &StateMgr = State->getStateManager();
351 MemRegionManager &MRMgr = StateMgr.getRegionManager();
352 StoreManager &StoreMgr = StateMgr.getStoreManager();
353
354 // MaterializeTemporaryExpr may appear out of place, after a few field and
355 // base-class accesses have been made to the object, even though semantically
356 // it is the whole object that gets materialized and lifetime-extended.
357 //
358 // For example:
359 //
360 // `-MaterializeTemporaryExpr
361 // `-MemberExpr
362 // `-CXXTemporaryObjectExpr
363 //
364 // instead of the more natural
365 //
366 // `-MemberExpr
367 // `-MaterializeTemporaryExpr
368 // `-CXXTemporaryObjectExpr
369 //
370 // Use the usual methods for obtaining the expression of the base object,
371 // and record the adjustments that we need to make to obtain the sub-object
372 // that the whole expression 'Ex' refers to. This trick is usual,
373 // in the sense that CodeGen takes a similar route.
374
375 SmallVector<const Expr *, 2> CommaLHSs;
376 SmallVector<SubobjectAdjustment, 2> Adjustments;
377
378 const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(
379 CommaLHS&: CommaLHSs, Adjustments);
380
381 // Take the region for Init, i.e. for the whole object. If we do not remember
382 // the region in which the object originally was constructed, come up with
383 // a new temporary region out of thin air and copy the contents of the object
384 // (which are currently present in the Environment, because Init is an rvalue)
385 // into that region. This is not correct, but it is better than nothing.
386 const TypedValueRegion *TR = nullptr;
387 if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Val: Result)) {
388 if (std::optional<SVal> V = getObjectUnderConstruction(State, Item: MT, LC)) {
389 State = finishObjectConstruction(State, Item: MT, LC);
390 State = State->BindExpr(S: Result, LCtx: LC, V: *V);
391 return State;
392 } else if (const ValueDecl *VD = MT->getExtendingDecl()) {
393 StorageDuration SD = MT->getStorageDuration();
394 assert(SD != SD_FullExpression);
395 // If this object is bound to a reference with static storage duration, we
396 // put it in a different region to prevent "address leakage" warnings.
397 if (SD == SD_Static || SD == SD_Thread) {
398 TR = MRMgr.getCXXStaticLifetimeExtendedObjectRegion(Ex: Init, VD);
399 } else {
400 TR = MRMgr.getCXXLifetimeExtendedObjectRegion(Ex: Init, VD, LC);
401 }
402 } else {
403 assert(MT->getStorageDuration() == SD_FullExpression);
404 TR = MRMgr.getCXXTempObjectRegion(Ex: Init, LC);
405 }
406 } else {
407 TR = MRMgr.getCXXTempObjectRegion(Ex: Init, LC);
408 }
409
410 SVal Reg = loc::MemRegionVal(TR);
411 SVal BaseReg = Reg;
412
413 // Make the necessary adjustments to obtain the sub-object.
414 for (const SubobjectAdjustment &Adj : llvm::reverse(C&: Adjustments)) {
415 switch (Adj.Kind) {
416 case SubobjectAdjustment::DerivedToBaseAdjustment:
417 Reg = StoreMgr.evalDerivedToBase(Derived: Reg, Cast: Adj.DerivedToBase.BasePath);
418 break;
419 case SubobjectAdjustment::FieldAdjustment:
420 Reg = StoreMgr.getLValueField(D: Adj.Field, Base: Reg);
421 break;
422 case SubobjectAdjustment::MemberPointerAdjustment:
423 // FIXME: Unimplemented.
424 State = State->invalidateRegions(Values: Reg, Elem: getCFGElementRef(),
425 BlockCount: currBldrCtx->blockCount(), LCtx: LC, CausesPointerEscape: true,
426 IS: nullptr, Call: nullptr, ITraits: nullptr);
427 return State;
428 }
429 }
430
431 // What remains is to copy the value of the object to the new region.
432 // FIXME: In other words, what we should always do is copy value of the
433 // Init expression (which corresponds to the bigger object) to the whole
434 // temporary region TR. However, this value is often no longer present
435 // in the Environment. If it has disappeared, we instead invalidate TR.
436 // Still, what we can do is assign the value of expression Ex (which
437 // corresponds to the sub-object) to the TR's sub-region Reg. At least,
438 // values inside Reg would be correct.
439 SVal InitVal = State->getSVal(Ex: Init, LCtx: LC);
440 if (InitVal.isUnknown()) {
441 InitVal = getSValBuilder().conjureSymbolVal(
442 elem: getCFGElementRef(), LCtx: LC, type: Init->getType(), visitCount: currBldrCtx->blockCount());
443 State = State->bindLoc(location: BaseReg.castAs<Loc>(), V: InitVal, LCtx: LC, notifyChanges: false);
444
445 // Then we'd need to take the value that certainly exists and bind it
446 // over.
447 if (InitValWithAdjustments.isUnknown()) {
448 // Try to recover some path sensitivity in case we couldn't
449 // compute the value.
450 InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
451 elem: getCFGElementRef(), LCtx: LC, type: InitWithAdjustments->getType(),
452 visitCount: currBldrCtx->blockCount());
453 }
454 State =
455 State->bindLoc(location: Reg.castAs<Loc>(), V: InitValWithAdjustments, LCtx: LC, notifyChanges: false);
456 } else {
457 State = State->bindLoc(location: BaseReg.castAs<Loc>(), V: InitVal, LCtx: LC, notifyChanges: false);
458 }
459
460 // The result expression would now point to the correct sub-region of the
461 // newly created temporary region. Do this last in order to getSVal of Init
462 // correctly in case (Result == Init).
463 if (Result->isGLValue()) {
464 State = State->BindExpr(S: Result, LCtx: LC, V: Reg);
465 } else {
466 State = State->BindExpr(S: Result, LCtx: LC, V: InitValWithAdjustments);
467 }
468
469 // Notify checkers once for two bindLoc()s.
470 State = processRegionChange(state: State, MR: TR, LCtx: LC);
471
472 if (OutRegionWithAdjustments)
473 *OutRegionWithAdjustments = cast<SubRegion>(Val: Reg.getAsRegion());
474 return State;
475}
476
477ProgramStateRef ExprEngine::setIndexOfElementToConstruct(
478 ProgramStateRef State, const CXXConstructExpr *E,
479 const LocationContext *LCtx, unsigned Idx) {
480 auto Key = std::make_pair(x&: E, y: LCtx->getStackFrame());
481
482 assert(!State->contains<IndexOfElementToConstruct>(Key) || Idx > 0);
483
484 return State->set<IndexOfElementToConstruct>(K: Key, E: Idx);
485}
486
487std::optional<unsigned>
488ExprEngine::getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E,
489 const LocationContext *LCtx) {
490 const unsigned *V = State->get<PendingInitLoop>(key: {E, LCtx->getStackFrame()});
491 return V ? std::make_optional(t: *V) : std::nullopt;
492}
493
494ProgramStateRef ExprEngine::removePendingInitLoop(ProgramStateRef State,
495 const CXXConstructExpr *E,
496 const LocationContext *LCtx) {
497 auto Key = std::make_pair(x&: E, y: LCtx->getStackFrame());
498
499 assert(E && State->contains<PendingInitLoop>(Key));
500 return State->remove<PendingInitLoop>(K: Key);
501}
502
503ProgramStateRef ExprEngine::setPendingInitLoop(ProgramStateRef State,
504 const CXXConstructExpr *E,
505 const LocationContext *LCtx,
506 unsigned Size) {
507 auto Key = std::make_pair(x&: E, y: LCtx->getStackFrame());
508
509 assert(!State->contains<PendingInitLoop>(Key) && Size > 0);
510
511 return State->set<PendingInitLoop>(K: Key, E: Size);
512}
513
514std::optional<unsigned>
515ExprEngine::getIndexOfElementToConstruct(ProgramStateRef State,
516 const CXXConstructExpr *E,
517 const LocationContext *LCtx) {
518 const unsigned *V =
519 State->get<IndexOfElementToConstruct>(key: {E, LCtx->getStackFrame()});
520 return V ? std::make_optional(t: *V) : std::nullopt;
521}
522
523ProgramStateRef
524ExprEngine::removeIndexOfElementToConstruct(ProgramStateRef State,
525 const CXXConstructExpr *E,
526 const LocationContext *LCtx) {
527 auto Key = std::make_pair(x&: E, y: LCtx->getStackFrame());
528
529 assert(E && State->contains<IndexOfElementToConstruct>(Key));
530 return State->remove<IndexOfElementToConstruct>(K: Key);
531}
532
533std::optional<unsigned>
534ExprEngine::getPendingArrayDestruction(ProgramStateRef State,
535 const LocationContext *LCtx) {
536 assert(LCtx && "LocationContext shouldn't be null!");
537
538 const unsigned *V =
539 State->get<PendingArrayDestruction>(key: LCtx->getStackFrame());
540 return V ? std::make_optional(t: *V) : std::nullopt;
541}
542
543ProgramStateRef ExprEngine::setPendingArrayDestruction(
544 ProgramStateRef State, const LocationContext *LCtx, unsigned Idx) {
545 assert(LCtx && "LocationContext shouldn't be null!");
546
547 auto Key = LCtx->getStackFrame();
548
549 return State->set<PendingArrayDestruction>(K: Key, E: Idx);
550}
551
552ProgramStateRef
553ExprEngine::removePendingArrayDestruction(ProgramStateRef State,
554 const LocationContext *LCtx) {
555 assert(LCtx && "LocationContext shouldn't be null!");
556
557 auto Key = LCtx->getStackFrame();
558
559 assert(LCtx && State->contains<PendingArrayDestruction>(Key));
560 return State->remove<PendingArrayDestruction>(K: Key);
561}
562
563ProgramStateRef
564ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
565 const ConstructionContextItem &Item,
566 const LocationContext *LC, SVal V) {
567 ConstructedObjectKey Key(Item, LC->getStackFrame());
568
569 const Expr *Init = nullptr;
570
571 if (auto DS = dyn_cast_or_null<DeclStmt>(Val: Item.getStmtOrNull())) {
572 if (auto VD = dyn_cast_or_null<VarDecl>(Val: DS->getSingleDecl()))
573 Init = VD->getInit();
574 }
575
576 if (auto LE = dyn_cast_or_null<LambdaExpr>(Val: Item.getStmtOrNull()))
577 Init = *(LE->capture_init_begin() + Item.getIndex());
578
579 if (!Init && !Item.getStmtOrNull())
580 Init = Item.getCXXCtorInitializer()->getInit();
581
582 // In an ArrayInitLoopExpr the real initializer is returned by
583 // getSubExpr(). Note that AILEs can be nested in case of
584 // multidimesnional arrays.
585 if (const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Val: Init))
586 Init = extractElementInitializerFromNestedAILE(AILE);
587
588 // FIXME: Currently the state might already contain the marker due to
589 // incorrect handling of temporaries bound to default parameters.
590 // The state will already contain the marker if we construct elements
591 // in an array, as we visit the same statement multiple times before
592 // the array declaration. The marker is removed when we exit the
593 // constructor call.
594 assert((!State->get<ObjectsUnderConstruction>(Key) ||
595 Key.getItem().getKind() ==
596 ConstructionContextItem::TemporaryDestructorKind ||
597 State->contains<IndexOfElementToConstruct>(
598 {dyn_cast_or_null<CXXConstructExpr>(Init), LC})) &&
599 "The object is already marked as `UnderConstruction`, when it's not "
600 "supposed to!");
601 return State->set<ObjectsUnderConstruction>(K: Key, E: V);
602}
603
604std::optional<SVal>
605ExprEngine::getObjectUnderConstruction(ProgramStateRef State,
606 const ConstructionContextItem &Item,
607 const LocationContext *LC) {
608 ConstructedObjectKey Key(Item, LC->getStackFrame());
609 const SVal *V = State->get<ObjectsUnderConstruction>(key: Key);
610 return V ? std::make_optional(t: *V) : std::nullopt;
611}
612
613ProgramStateRef
614ExprEngine::finishObjectConstruction(ProgramStateRef State,
615 const ConstructionContextItem &Item,
616 const LocationContext *LC) {
617 ConstructedObjectKey Key(Item, LC->getStackFrame());
618 assert(State->contains<ObjectsUnderConstruction>(Key));
619 return State->remove<ObjectsUnderConstruction>(K: Key);
620}
621
622ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
623 const CXXBindTemporaryExpr *BTE,
624 const LocationContext *LC) {
625 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
626 // FIXME: Currently the state might already contain the marker due to
627 // incorrect handling of temporaries bound to default parameters.
628 return State->set<ObjectsUnderConstruction>(K: Key, E: UnknownVal());
629}
630
631ProgramStateRef
632ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
633 const CXXBindTemporaryExpr *BTE,
634 const LocationContext *LC) {
635 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
636 assert(State->contains<ObjectsUnderConstruction>(Key));
637 return State->remove<ObjectsUnderConstruction>(K: Key);
638}
639
640bool ExprEngine::isDestructorElided(ProgramStateRef State,
641 const CXXBindTemporaryExpr *BTE,
642 const LocationContext *LC) {
643 ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
644 return State->contains<ObjectsUnderConstruction>(key: Key);
645}
646
647bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
648 const LocationContext *FromLC,
649 const LocationContext *ToLC) {
650 const LocationContext *LC = FromLC;
651 while (LC != ToLC) {
652 assert(LC && "ToLC must be a parent of FromLC!");
653 for (auto I : State->get<ObjectsUnderConstruction>())
654 if (I.first.getLocationContext() == LC)
655 return false;
656
657 LC = LC->getParent();
658 }
659 return true;
660}
661
662
663//===----------------------------------------------------------------------===//
664// Top-level transfer function logic (Dispatcher).
665//===----------------------------------------------------------------------===//
666
667/// evalAssume - Called by ConstraintManager. Used to call checker-specific
668/// logic for handling assumptions on symbolic values.
669ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
670 SVal cond, bool assumption) {
671 return getCheckerManager().runCheckersForEvalAssume(state, Cond: cond, Assumption: assumption);
672}
673
674ProgramStateRef
675ExprEngine::processRegionChanges(ProgramStateRef state,
676 const InvalidatedSymbols *invalidated,
677 ArrayRef<const MemRegion *> Explicits,
678 ArrayRef<const MemRegion *> Regions,
679 const LocationContext *LCtx,
680 const CallEvent *Call) {
681 return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
682 ExplicitRegions: Explicits, Regions,
683 LCtx, Call);
684}
685
686static void
687printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,
688 const char *NL, const LocationContext *LCtx,
689 unsigned int Space = 0, bool IsDot = false) {
690 PrintingPolicy PP =
691 LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();
692
693 ++Space;
694 bool HasItem = false;
695
696 // Store the last key.
697 const ConstructedObjectKey *LastKey = nullptr;
698 for (const auto &I : State->get<ObjectsUnderConstruction>()) {
699 const ConstructedObjectKey &Key = I.first;
700 if (Key.getLocationContext() != LCtx)
701 continue;
702
703 if (!HasItem) {
704 Out << '[' << NL;
705 HasItem = true;
706 }
707
708 LastKey = &Key;
709 }
710
711 for (const auto &I : State->get<ObjectsUnderConstruction>()) {
712 const ConstructedObjectKey &Key = I.first;
713 SVal Value = I.second;
714 if (Key.getLocationContext() != LCtx)
715 continue;
716
717 Indent(Out, Space, IsDot) << "{ ";
718 Key.printJson(Out, Helper: nullptr, PP);
719 Out << ", \"value\": \"" << Value << "\" }";
720
721 if (&Key != LastKey)
722 Out << ',';
723 Out << NL;
724 }
725
726 if (HasItem)
727 Indent(Out, Space: --Space, IsDot) << ']'; // End of "location_context".
728 else {
729 Out << "null ";
730 }
731}
732
733static void printIndicesOfElementsToConstructJson(
734 raw_ostream &Out, ProgramStateRef State, const char *NL,
735 const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) {
736 using KeyT = std::pair<const Expr *, const LocationContext *>;
737
738 const auto &Context = LCtx->getAnalysisDeclContext()->getASTContext();
739 PrintingPolicy PP = Context.getPrintingPolicy();
740
741 ++Space;
742 bool HasItem = false;
743
744 // Store the last key.
745 KeyT LastKey;
746 for (const auto &I : State->get<IndexOfElementToConstruct>()) {
747 const KeyT &Key = I.first;
748 if (Key.second != LCtx)
749 continue;
750
751 if (!HasItem) {
752 Out << '[' << NL;
753 HasItem = true;
754 }
755
756 LastKey = Key;
757 }
758
759 for (const auto &I : State->get<IndexOfElementToConstruct>()) {
760 const KeyT &Key = I.first;
761 unsigned Value = I.second;
762 if (Key.second != LCtx)
763 continue;
764
765 Indent(Out, Space, IsDot) << "{ ";
766
767 // Expr
768 const Expr *E = Key.first;
769 Out << "\"stmt_id\": " << E->getID(Context);
770
771 // Kind
772 Out << ", \"kind\": null";
773
774 // Pretty-print
775 Out << ", \"pretty\": ";
776 Out << "\"" << E->getStmtClassName() << ' '
777 << E->getSourceRange().printToString(SM: Context.getSourceManager()) << " '"
778 << QualType::getAsString(split: E->getType().split(), Policy: PP);
779 Out << "'\"";
780
781 Out << ", \"value\": \"Current index: " << Value - 1 << "\" }";
782
783 if (Key != LastKey)
784 Out << ',';
785 Out << NL;
786 }
787
788 if (HasItem)
789 Indent(Out, Space: --Space, IsDot) << ']'; // End of "location_context".
790 else {
791 Out << "null ";
792 }
793}
794
795static void printPendingInitLoopJson(raw_ostream &Out, ProgramStateRef State,
796 const char *NL,
797 const LocationContext *LCtx,
798 unsigned int Space = 0,
799 bool IsDot = false) {
800 using KeyT = std::pair<const CXXConstructExpr *, const LocationContext *>;
801
802 const auto &Context = LCtx->getAnalysisDeclContext()->getASTContext();
803 PrintingPolicy PP = Context.getPrintingPolicy();
804
805 ++Space;
806 bool HasItem = false;
807
808 // Store the last key.
809 KeyT LastKey;
810 for (const auto &I : State->get<PendingInitLoop>()) {
811 const KeyT &Key = I.first;
812 if (Key.second != LCtx)
813 continue;
814
815 if (!HasItem) {
816 Out << '[' << NL;
817 HasItem = true;
818 }
819
820 LastKey = Key;
821 }
822
823 for (const auto &I : State->get<PendingInitLoop>()) {
824 const KeyT &Key = I.first;
825 unsigned Value = I.second;
826 if (Key.second != LCtx)
827 continue;
828
829 Indent(Out, Space, IsDot) << "{ ";
830
831 const CXXConstructExpr *E = Key.first;
832 Out << "\"stmt_id\": " << E->getID(Context);
833
834 Out << ", \"kind\": null";
835 Out << ", \"pretty\": ";
836 Out << '\"' << E->getStmtClassName() << ' '
837 << E->getSourceRange().printToString(SM: Context.getSourceManager()) << " '"
838 << QualType::getAsString(split: E->getType().split(), Policy: PP);
839 Out << "'\"";
840
841 Out << ", \"value\": \"Flattened size: " << Value << "\"}";
842
843 if (Key != LastKey)
844 Out << ',';
845 Out << NL;
846 }
847
848 if (HasItem)
849 Indent(Out, Space: --Space, IsDot) << ']'; // End of "location_context".
850 else {
851 Out << "null ";
852 }
853}
854
855static void
856printPendingArrayDestructionsJson(raw_ostream &Out, ProgramStateRef State,
857 const char *NL, const LocationContext *LCtx,
858 unsigned int Space = 0, bool IsDot = false) {
859 using KeyT = const LocationContext *;
860
861 ++Space;
862 bool HasItem = false;
863
864 // Store the last key.
865 KeyT LastKey = nullptr;
866 for (const auto &I : State->get<PendingArrayDestruction>()) {
867 const KeyT &Key = I.first;
868 if (Key != LCtx)
869 continue;
870
871 if (!HasItem) {
872 Out << '[' << NL;
873 HasItem = true;
874 }
875
876 LastKey = Key;
877 }
878
879 for (const auto &I : State->get<PendingArrayDestruction>()) {
880 const KeyT &Key = I.first;
881 if (Key != LCtx)
882 continue;
883
884 Indent(Out, Space, IsDot) << "{ ";
885
886 Out << "\"stmt_id\": null";
887 Out << ", \"kind\": null";
888 Out << ", \"pretty\": \"Current index: \"";
889 Out << ", \"value\": \"" << I.second << "\" }";
890
891 if (Key != LastKey)
892 Out << ',';
893 Out << NL;
894 }
895
896 if (HasItem)
897 Indent(Out, Space: --Space, IsDot) << ']'; // End of "location_context".
898 else {
899 Out << "null ";
900 }
901}
902
903/// A helper function to generalize program state trait printing.
904/// The function invokes Printer as 'Printer(Out, State, NL, LC, Space, IsDot,
905/// std::forward<Args>(args)...)'. \n One possible type for Printer is
906/// 'void()(raw_ostream &, ProgramStateRef, const char *, const LocationContext
907/// *, unsigned int, bool, ...)' \n \param Trait The state trait to be printed.
908/// \param Printer A void function that prints Trait.
909/// \param Args An additional parameter pack that is passed to Print upon
910/// invocation.
911template <typename Trait, typename Printer, typename... Args>
912static void printStateTraitWithLocationContextJson(
913 raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx,
914 const char *NL, unsigned int Space, bool IsDot,
915 const char *jsonPropertyName, Printer printer, Args &&...args) {
916
917 using RequiredType =
918 void (*)(raw_ostream &, ProgramStateRef, const char *,
919 const LocationContext *, unsigned int, bool, Args &&...);
920
921 // Try to do as much compile time checking as possible.
922 // FIXME: check for invocable instead of function?
923 static_assert(std::is_function_v<std::remove_pointer_t<Printer>>,
924 "Printer is not a function!");
925 static_assert(std::is_convertible_v<Printer, RequiredType>,
926 "Printer doesn't have the required type!");
927
928 if (LCtx && !State->get<Trait>().isEmpty()) {
929 Indent(Out, Space, IsDot) << '\"' << jsonPropertyName << "\": ";
930 ++Space;
931 Out << '[' << NL;
932 LCtx->printJson(Out, NL, Space, IsDot, printMoreInfoPerContext: [&](const LocationContext *LC) {
933 printer(Out, State, NL, LC, Space, IsDot, std::forward<Args>(args)...);
934 });
935
936 --Space;
937 Indent(Out, Space, IsDot) << "]," << NL; // End of "jsonPropertyName".
938 }
939}
940
941void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,
942 const LocationContext *LCtx, const char *NL,
943 unsigned int Space, bool IsDot) const {
944
945 printStateTraitWithLocationContextJson<ObjectsUnderConstruction>(
946 Out, State, LCtx, NL, Space, IsDot, jsonPropertyName: "constructing_objects",
947 printer: printObjectsUnderConstructionJson);
948 printStateTraitWithLocationContextJson<IndexOfElementToConstruct>(
949 Out, State, LCtx, NL, Space, IsDot, jsonPropertyName: "index_of_element",
950 printer: printIndicesOfElementsToConstructJson);
951 printStateTraitWithLocationContextJson<PendingInitLoop>(
952 Out, State, LCtx, NL, Space, IsDot, jsonPropertyName: "pending_init_loops",
953 printer: printPendingInitLoopJson);
954 printStateTraitWithLocationContextJson<PendingArrayDestruction>(
955 Out, State, LCtx, NL, Space, IsDot, jsonPropertyName: "pending_destructors",
956 printer: printPendingArrayDestructionsJson);
957
958 getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,
959 IsDot);
960}
961
962void ExprEngine::processEndWorklist() {
963 // This prints the name of the top-level function if we crash.
964 PrettyStackTraceLocationContext CrashInfo(getRootLocationContext());
965 getCheckerManager().runCheckersForEndAnalysis(G, BR, Eng&: *this);
966}
967
968void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
969 unsigned StmtIdx, NodeBuilderContext *Ctx) {
970 currStmtIdx = StmtIdx;
971 currBldrCtx = Ctx;
972
973 switch (E.getKind()) {
974 case CFGElement::Statement:
975 case CFGElement::Constructor:
976 case CFGElement::CXXRecordTypedCall:
977 ProcessStmt(S: E.castAs<CFGStmt>().getStmt(), Pred);
978 return;
979 case CFGElement::Initializer:
980 ProcessInitializer(I: E.castAs<CFGInitializer>(), Pred);
981 return;
982 case CFGElement::NewAllocator:
983 ProcessNewAllocator(NE: E.castAs<CFGNewAllocator>().getAllocatorExpr(),
984 Pred);
985 return;
986 case CFGElement::AutomaticObjectDtor:
987 case CFGElement::DeleteDtor:
988 case CFGElement::BaseDtor:
989 case CFGElement::MemberDtor:
990 case CFGElement::TemporaryDtor:
991 ProcessImplicitDtor(D: E.castAs<CFGImplicitDtor>(), Pred);
992 return;
993 case CFGElement::LoopExit:
994 ProcessLoopExit(S: E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
995 return;
996 case CFGElement::LifetimeEnds:
997 case CFGElement::CleanupFunction:
998 case CFGElement::FullExprCleanup:
999 case CFGElement::ScopeBegin:
1000 case CFGElement::ScopeEnd:
1001 return;
1002 }
1003}
1004
1005static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
1006 const Stmt *S,
1007 const ExplodedNode *Pred,
1008 const LocationContext *LC) {
1009 // Are we never purging state values?
1010 if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
1011 return false;
1012
1013 // Is this the beginning of a basic block?
1014 if (Pred->getLocation().getAs<BlockEntrance>())
1015 return true;
1016
1017 // Is this on a non-expression?
1018 if (!isa<Expr>(Val: S))
1019 return true;
1020
1021 // Run before processing a call.
1022 if (CallEvent::isCallStmt(S))
1023 return true;
1024
1025 // Is this an expression that is consumed by another expression? If so,
1026 // postpone cleaning out the state.
1027 ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
1028 return !PM.isConsumedExpr(E: cast<Expr>(Val: S));
1029}
1030
1031void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
1032 const Stmt *ReferenceStmt,
1033 const LocationContext *LC,
1034 const Stmt *DiagnosticStmt,
1035 ProgramPoint::Kind K) {
1036 llvm::TimeTraceScope TimeScope("ExprEngine::removeDead");
1037 assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
1038 ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))
1039 && "PostStmt is not generally supported by the SymbolReaper yet");
1040 assert(LC && "Must pass the current (or expiring) LocationContext");
1041
1042 if (!DiagnosticStmt) {
1043 DiagnosticStmt = ReferenceStmt;
1044 assert(DiagnosticStmt && "Required for clearing a LocationContext");
1045 }
1046
1047 NumRemoveDeadBindings++;
1048 ProgramStateRef CleanedState = Pred->getState();
1049
1050 // LC is the location context being destroyed, but SymbolReaper wants a
1051 // location context that is still live. (If this is the top-level stack
1052 // frame, this will be null.)
1053 if (!ReferenceStmt) {
1054 assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
1055 "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
1056 LC = LC->getParent();
1057 }
1058
1059 const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr;
1060 SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
1061
1062 for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
1063 if (SymbolRef Sym = I.second.getAsSymbol())
1064 SymReaper.markLive(sym: Sym);
1065 if (const MemRegion *MR = I.second.getAsRegion())
1066 SymReaper.markLive(region: MR);
1067 }
1068
1069 getCheckerManager().runCheckersForLiveSymbols(state: CleanedState, SymReaper);
1070
1071 // Create a state in which dead bindings are removed from the environment
1072 // and the store. TODO: The function should just return new env and store,
1073 // not a new state.
1074 CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
1075 St: CleanedState, LCtx: SFC, SymReaper);
1076
1077 // Process any special transfer function for dead symbols.
1078 // Call checkers with the non-cleaned state so that they could query the
1079 // values of the soon to be dead symbols.
1080 ExplodedNodeSet CheckedSet;
1081 getCheckerManager().runCheckersForDeadSymbols(Dst&: CheckedSet, Src: Pred, SymReaper,
1082 S: DiagnosticStmt, Eng&: *this, K);
1083
1084 // Extend lifetime of symbols used for dynamic extent while the parent region
1085 // is live. In this way size information about memory allocations is not lost
1086 // if the region remains live.
1087 markAllDynamicExtentLive(State: CleanedState, SymReaper);
1088
1089 // For each node in CheckedSet, generate CleanedNodes that have the
1090 // environment, the store, and the constraints cleaned up but have the
1091 // user-supplied states as the predecessors.
1092 NodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
1093 for (const auto I : CheckedSet) {
1094 ProgramStateRef CheckerState = I->getState();
1095
1096 // The constraint manager has not been cleaned up yet, so clean up now.
1097 CheckerState =
1098 getConstraintManager().removeDeadBindings(state: CheckerState, SymReaper);
1099
1100 assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
1101 "Checkers are not allowed to modify the Environment as a part of "
1102 "checkDeadSymbols processing.");
1103 assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
1104 "Checkers are not allowed to modify the Store as a part of "
1105 "checkDeadSymbols processing.");
1106
1107 // Create a state based on CleanedState with CheckerState GDM and
1108 // generate a transition to that state.
1109 ProgramStateRef CleanedCheckerSt =
1110 StateMgr.getPersistentStateWithGDM(FromState: CleanedState, GDMState: CheckerState);
1111 Bldr.generateNode(S: DiagnosticStmt, Pred: I, St: CleanedCheckerSt, tag: cleanupNodeTag(), K);
1112 }
1113}
1114
1115const ProgramPointTag *ExprEngine::cleanupNodeTag() {
1116 static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
1117 return &cleanupTag;
1118}
1119
1120void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
1121 // Reclaim any unnecessary nodes in the ExplodedGraph.
1122 G.reclaimRecentlyAllocatedNodes();
1123
1124 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1125 currStmt->getBeginLoc(),
1126 "Error evaluating statement");
1127
1128 // Remove dead bindings and symbols.
1129 ExplodedNodeSet CleanedStates;
1130 if (shouldRemoveDeadBindings(AMgr, S: currStmt, Pred,
1131 LC: Pred->getLocationContext())) {
1132 removeDead(Pred, Out&: CleanedStates, ReferenceStmt: currStmt,
1133 LC: Pred->getLocationContext());
1134 } else
1135 CleanedStates.Add(N: Pred);
1136
1137 // Visit the statement.
1138 ExplodedNodeSet Dst;
1139 for (const auto I : CleanedStates) {
1140 ExplodedNodeSet DstI;
1141 // Visit the statement.
1142 Visit(S: currStmt, Pred: I, Dst&: DstI);
1143 Dst.insert(S: DstI);
1144 }
1145
1146 // Enqueue the new nodes onto the work list.
1147 Engine.enqueue(Set&: Dst, Block: currBldrCtx->getBlock(), Idx: currStmtIdx);
1148}
1149
1150void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
1151 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1152 S->getBeginLoc(),
1153 "Error evaluating end of the loop");
1154 ExplodedNodeSet Dst;
1155 Dst.Add(N: Pred);
1156 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1157 ProgramStateRef NewState = Pred->getState();
1158
1159 if(AMgr.options.ShouldUnrollLoops)
1160 NewState = processLoopEnd(LoopStmt: S, State: NewState);
1161
1162 LoopExit PP(S, Pred->getLocationContext());
1163 Bldr.generateNode(PP, State: NewState, Pred);
1164 // Enqueue the new nodes onto the work list.
1165 Engine.enqueue(Set&: Dst, Block: currBldrCtx->getBlock(), Idx: currStmtIdx);
1166}
1167
1168void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,
1169 ExplodedNode *Pred) {
1170 const CXXCtorInitializer *BMI = CFGInit.getInitializer();
1171 const Expr *Init = BMI->getInit()->IgnoreImplicit();
1172 const LocationContext *LC = Pred->getLocationContext();
1173
1174 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1175 BMI->getSourceLocation(),
1176 "Error evaluating initializer");
1177
1178 // We don't clean up dead bindings here.
1179 const auto *stackFrame = cast<StackFrameContext>(Val: Pred->getLocationContext());
1180 const auto *decl = cast<CXXConstructorDecl>(Val: stackFrame->getDecl());
1181
1182 ProgramStateRef State = Pred->getState();
1183 SVal thisVal = State->getSVal(LV: svalBuilder.getCXXThis(D: decl, SFC: stackFrame));
1184
1185 ExplodedNodeSet Tmp;
1186 SVal FieldLoc;
1187
1188 // Evaluate the initializer, if necessary
1189 if (BMI->isAnyMemberInitializer()) {
1190 // Constructors build the object directly in the field,
1191 // but non-objects must be copied in from the initializer.
1192 if (getObjectUnderConstruction(State, Item: BMI, LC)) {
1193 // The field was directly constructed, so there is no need to bind.
1194 // But we still need to stop tracking the object under construction.
1195 State = finishObjectConstruction(State, Item: BMI, LC);
1196 NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
1197 PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);
1198 Bldr.generateNode(PP: PS, State, Pred);
1199 } else {
1200 const ValueDecl *Field;
1201 if (BMI->isIndirectMemberInitializer()) {
1202 Field = BMI->getIndirectMember();
1203 FieldLoc = State->getLValue(decl: BMI->getIndirectMember(), Base: thisVal);
1204 } else {
1205 Field = BMI->getMember();
1206 FieldLoc = State->getLValue(decl: BMI->getMember(), Base: thisVal);
1207 }
1208
1209 SVal InitVal;
1210 if (Init->getType()->isArrayType()) {
1211 // Handle arrays of trivial type. We can represent this with a
1212 // primitive load/copy from the base array region.
1213 const ArraySubscriptExpr *ASE;
1214 while ((ASE = dyn_cast<ArraySubscriptExpr>(Val: Init)))
1215 Init = ASE->getBase()->IgnoreImplicit();
1216
1217 InitVal = State->getSVal(Ex: Init, LCtx: stackFrame);
1218
1219 // If we fail to get the value for some reason, use a symbolic value.
1220 if (InitVal.isUnknownOrUndef()) {
1221 SValBuilder &SVB = getSValBuilder();
1222 InitVal =
1223 SVB.conjureSymbolVal(elem: getCFGElementRef(), LCtx: stackFrame,
1224 type: Field->getType(), visitCount: currBldrCtx->blockCount());
1225 }
1226 } else {
1227 InitVal = State->getSVal(Ex: BMI->getInit(), LCtx: stackFrame);
1228 }
1229
1230 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
1231 evalBind(Dst&: Tmp, StoreE: Init, Pred, location: FieldLoc, Val: InitVal, /*isInit=*/AtDeclInit: true, PP: &PP);
1232 }
1233 } else if (BMI->isBaseInitializer() && isa<InitListExpr>(Val: Init)) {
1234 // When the base class is initialized with an initialization list and the
1235 // base class does not have a ctor, there will not be a CXXConstructExpr to
1236 // initialize the base region. Hence, we need to make the bind for it.
1237 SVal BaseLoc = getStoreManager().evalDerivedToBase(
1238 Derived: thisVal, DerivedPtrType: QualType(BMI->getBaseClass(), 0), IsVirtual: BMI->isBaseVirtual());
1239 SVal InitVal = State->getSVal(Ex: Init, LCtx: stackFrame);
1240 evalBind(Dst&: Tmp, StoreE: Init, Pred, location: BaseLoc, Val: InitVal, /*isInit=*/AtDeclInit: true);
1241 } else {
1242 assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
1243 Tmp.insert(S: Pred);
1244 // We already did all the work when visiting the CXXConstructExpr.
1245 }
1246
1247 // Construct PostInitializer nodes whether the state changed or not,
1248 // so that the diagnostics don't get confused.
1249 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
1250 ExplodedNodeSet Dst;
1251 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
1252 for (const auto I : Tmp) {
1253 ProgramStateRef State = I->getState();
1254 Bldr.generateNode(PP, State, Pred: I);
1255 }
1256
1257 // Enqueue the new nodes onto the work list.
1258 Engine.enqueue(Set&: Dst, Block: currBldrCtx->getBlock(), Idx: currStmtIdx);
1259}
1260
1261std::pair<ProgramStateRef, uint64_t>
1262ExprEngine::prepareStateForArrayDestruction(const ProgramStateRef State,
1263 const MemRegion *Region,
1264 const QualType &ElementTy,
1265 const LocationContext *LCtx,
1266 SVal *ElementCountVal) {
1267 assert(Region != nullptr && "Not-null region expected");
1268
1269 QualType Ty = ElementTy.getDesugaredType(Context: getContext());
1270 while (const auto *NTy = dyn_cast<ArrayType>(Val&: Ty))
1271 Ty = NTy->getElementType().getDesugaredType(Context: getContext());
1272
1273 auto ElementCount = getDynamicElementCount(State, MR: Region, SVB&: svalBuilder, Ty);
1274
1275 if (ElementCountVal)
1276 *ElementCountVal = ElementCount;
1277
1278 // Note: the destructors are called in reverse order.
1279 unsigned Idx = 0;
1280 if (auto OptionalIdx = getPendingArrayDestruction(State, LCtx)) {
1281 Idx = *OptionalIdx;
1282 } else {
1283 // The element count is either unknown, or an SVal that's not an integer.
1284 if (!ElementCount.isConstant())
1285 return {State, 0};
1286
1287 Idx = ElementCount.getAsInteger()->getLimitedValue();
1288 }
1289
1290 if (Idx == 0)
1291 return {State, 0};
1292
1293 --Idx;
1294
1295 return {setPendingArrayDestruction(State, LCtx, Idx), Idx};
1296}
1297
1298void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
1299 ExplodedNode *Pred) {
1300 ExplodedNodeSet Dst;
1301 switch (D.getKind()) {
1302 case CFGElement::AutomaticObjectDtor:
1303 ProcessAutomaticObjDtor(D: D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
1304 break;
1305 case CFGElement::BaseDtor:
1306 ProcessBaseDtor(D: D.castAs<CFGBaseDtor>(), Pred, Dst);
1307 break;
1308 case CFGElement::MemberDtor:
1309 ProcessMemberDtor(D: D.castAs<CFGMemberDtor>(), Pred, Dst);
1310 break;
1311 case CFGElement::TemporaryDtor:
1312 ProcessTemporaryDtor(D: D.castAs<CFGTemporaryDtor>(), Pred, Dst);
1313 break;
1314 case CFGElement::DeleteDtor:
1315 ProcessDeleteDtor(D: D.castAs<CFGDeleteDtor>(), Pred, Dst);
1316 break;
1317 default:
1318 llvm_unreachable("Unexpected dtor kind.");
1319 }
1320
1321 // Enqueue the new nodes onto the work list.
1322 Engine.enqueue(Set&: Dst, Block: currBldrCtx->getBlock(), Idx: currStmtIdx);
1323}
1324
1325void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
1326 ExplodedNode *Pred) {
1327 ExplodedNodeSet Dst;
1328 AnalysisManager &AMgr = getAnalysisManager();
1329 AnalyzerOptions &Opts = AMgr.options;
1330 // TODO: We're not evaluating allocators for all cases just yet as
1331 // we're not handling the return value correctly, which causes false
1332 // positives when the alpha.cplusplus.NewDeleteLeaks check is on.
1333 if (Opts.MayInlineCXXAllocator)
1334 VisitCXXNewAllocatorCall(CNE: NE, Pred, Dst);
1335 else {
1336 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1337 const LocationContext *LCtx = Pred->getLocationContext();
1338 PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx,
1339 getCFGElementRef());
1340 Bldr.generateNode(PP, State: Pred->getState(), Pred);
1341 }
1342 Engine.enqueue(Set&: Dst, Block: currBldrCtx->getBlock(), Idx: currStmtIdx);
1343}
1344
1345void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
1346 ExplodedNode *Pred,
1347 ExplodedNodeSet &Dst) {
1348 const auto *DtorDecl = Dtor.getDestructorDecl(astContext&: getContext());
1349 const VarDecl *varDecl = Dtor.getVarDecl();
1350 QualType varType = varDecl->getType();
1351
1352 ProgramStateRef state = Pred->getState();
1353 const LocationContext *LCtx = Pred->getLocationContext();
1354
1355 SVal dest = state->getLValue(VD: varDecl, LC: LCtx);
1356 const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
1357
1358 if (varType->isReferenceType()) {
1359 const MemRegion *ValueRegion = state->getSVal(R: Region).getAsRegion();
1360 if (!ValueRegion) {
1361 // FIXME: This should not happen. The language guarantees a presence
1362 // of a valid initializer here, so the reference shall not be undefined.
1363 // It seems that we're calling destructors over variables that
1364 // were not initialized yet.
1365 return;
1366 }
1367 Region = ValueRegion->getBaseRegion();
1368 varType = cast<TypedValueRegion>(Val: Region)->getValueType();
1369 }
1370
1371 unsigned Idx = 0;
1372 if (isa<ArrayType>(Val: varType)) {
1373 SVal ElementCount;
1374 std::tie(args&: state, args&: Idx) = prepareStateForArrayDestruction(
1375 State: state, Region, ElementTy: varType, LCtx, ElementCountVal: &ElementCount);
1376
1377 if (ElementCount.isConstant()) {
1378 uint64_t ArrayLength = ElementCount.getAsInteger()->getLimitedValue();
1379 assert(ArrayLength &&
1380 "An automatic dtor for a 0 length array shouldn't be triggered!");
1381
1382 // Still handle this case if we don't have assertions enabled.
1383 if (!ArrayLength) {
1384 static SimpleProgramPointTag PT(
1385 "ExprEngine", "Skipping automatic 0 length array destruction, "
1386 "which shouldn't be in the CFG.");
1387 PostImplicitCall PP(DtorDecl, varDecl->getLocation(), LCtx,
1388 getCFGElementRef(), &PT);
1389 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1390 Bldr.generateSink(PP, State: Pred->getState(), Pred);
1391 return;
1392 }
1393 }
1394 }
1395
1396 EvalCallOptions CallOpts;
1397 Region = makeElementRegion(State: state, LValue: loc::MemRegionVal(Region), Ty&: varType,
1398 IsArray&: CallOpts.IsArrayCtorOrDtor, Idx)
1399 .getAsRegion();
1400
1401 NodeBuilder Bldr(Pred, Dst, getBuilderContext());
1402
1403 static SimpleProgramPointTag PT("ExprEngine",
1404 "Prepare for object destruction");
1405 PreImplicitCall PP(DtorDecl, varDecl->getLocation(), LCtx, getCFGElementRef(),
1406 &PT);
1407 Pred = Bldr.generateNode(PP, State: state, Pred);
1408
1409 if (!Pred)
1410 return;
1411 Bldr.takeNodes(N: Pred);
1412
1413 VisitCXXDestructor(ObjectType: varType, Dest: Region, S: Dtor.getTriggerStmt(),
1414 /*IsBase=*/IsBaseDtor: false, Pred, Dst, Options&: CallOpts);
1415}
1416
1417void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,
1418 ExplodedNode *Pred,
1419 ExplodedNodeSet &Dst) {
1420 ProgramStateRef State = Pred->getState();
1421 const LocationContext *LCtx = Pred->getLocationContext();
1422 const CXXDeleteExpr *DE = Dtor.getDeleteExpr();
1423 const Stmt *Arg = DE->getArgument();
1424 QualType DTy = DE->getDestroyedType();
1425 SVal ArgVal = State->getSVal(Ex: Arg, LCtx);
1426
1427 // If the argument to delete is known to be a null value,
1428 // don't run destructor.
1429 if (State->isNull(V: ArgVal).isConstrainedTrue()) {
1430 QualType BTy = getContext().getBaseElementType(QT: DTy);
1431 const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();
1432 const CXXDestructorDecl *Dtor = RD->getDestructor();
1433
1434 PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx, getCFGElementRef());
1435 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1436 Bldr.generateNode(PP, State: Pred->getState(), Pred);
1437 return;
1438 }
1439
1440 auto getDtorDecl = [](const QualType &DTy) {
1441 const CXXRecordDecl *RD = DTy->getAsCXXRecordDecl();
1442 return RD->getDestructor();
1443 };
1444
1445 unsigned Idx = 0;
1446 EvalCallOptions CallOpts;
1447 const MemRegion *ArgR = ArgVal.getAsRegion();
1448
1449 if (DE->isArrayForm()) {
1450 CallOpts.IsArrayCtorOrDtor = true;
1451 // Yes, it may even be a multi-dimensional array.
1452 while (const auto *AT = getContext().getAsArrayType(T: DTy))
1453 DTy = AT->getElementType();
1454
1455 if (ArgR) {
1456 SVal ElementCount;
1457 std::tie(args&: State, args&: Idx) = prepareStateForArrayDestruction(
1458 State, Region: ArgR, ElementTy: DTy, LCtx, ElementCountVal: &ElementCount);
1459
1460 // If we're about to destruct a 0 length array, don't run any of the
1461 // destructors.
1462 if (ElementCount.isConstant() &&
1463 ElementCount.getAsInteger()->getLimitedValue() == 0) {
1464
1465 static SimpleProgramPointTag PT(
1466 "ExprEngine", "Skipping 0 length array delete destruction");
1467 PostImplicitCall PP(getDtorDecl(DTy), DE->getBeginLoc(), LCtx,
1468 getCFGElementRef(), &PT);
1469 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1470 Bldr.generateNode(PP, State: Pred->getState(), Pred);
1471 return;
1472 }
1473
1474 ArgR = State->getLValue(ElementType: DTy, Idx: svalBuilder.makeArrayIndex(idx: Idx), Base: ArgVal)
1475 .getAsRegion();
1476 }
1477 }
1478
1479 NodeBuilder Bldr(Pred, Dst, getBuilderContext());
1480 static SimpleProgramPointTag PT("ExprEngine",
1481 "Prepare for object destruction");
1482 PreImplicitCall PP(getDtorDecl(DTy), DE->getBeginLoc(), LCtx,
1483 getCFGElementRef(), &PT);
1484 Pred = Bldr.generateNode(PP, State, Pred);
1485
1486 if (!Pred)
1487 return;
1488 Bldr.takeNodes(N: Pred);
1489
1490 VisitCXXDestructor(ObjectType: DTy, Dest: ArgR, S: DE, /*IsBase=*/IsBaseDtor: false, Pred, Dst, Options&: CallOpts);
1491}
1492
1493void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
1494 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1495 const LocationContext *LCtx = Pred->getLocationContext();
1496
1497 const auto *CurDtor = cast<CXXDestructorDecl>(Val: LCtx->getDecl());
1498 Loc ThisPtr = getSValBuilder().getCXXThis(D: CurDtor,
1499 SFC: LCtx->getStackFrame());
1500 SVal ThisVal = Pred->getState()->getSVal(LV: ThisPtr);
1501
1502 // Create the base object region.
1503 const CXXBaseSpecifier *Base = D.getBaseSpecifier();
1504 QualType BaseTy = Base->getType();
1505 SVal BaseVal = getStoreManager().evalDerivedToBase(Derived: ThisVal, DerivedPtrType: BaseTy,
1506 IsVirtual: Base->isVirtual());
1507
1508 EvalCallOptions CallOpts;
1509 VisitCXXDestructor(ObjectType: BaseTy, Dest: BaseVal.getAsRegion(), S: CurDtor->getBody(),
1510 /*IsBase=*/IsBaseDtor: true, Pred, Dst, Options&: CallOpts);
1511}
1512
1513void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
1514 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1515 const auto *DtorDecl = D.getDestructorDecl(astContext&: getContext());
1516 const FieldDecl *Member = D.getFieldDecl();
1517 QualType T = Member->getType();
1518 ProgramStateRef State = Pred->getState();
1519 const LocationContext *LCtx = Pred->getLocationContext();
1520
1521 const auto *CurDtor = cast<CXXDestructorDecl>(Val: LCtx->getDecl());
1522 Loc ThisStorageLoc =
1523 getSValBuilder().getCXXThis(D: CurDtor, SFC: LCtx->getStackFrame());
1524 Loc ThisLoc = State->getSVal(LV: ThisStorageLoc).castAs<Loc>();
1525 SVal FieldVal = State->getLValue(decl: Member, Base: ThisLoc);
1526
1527 unsigned Idx = 0;
1528 if (isa<ArrayType>(Val: T)) {
1529 SVal ElementCount;
1530 std::tie(args&: State, args&: Idx) = prepareStateForArrayDestruction(
1531 State, Region: FieldVal.getAsRegion(), ElementTy: T, LCtx, ElementCountVal: &ElementCount);
1532
1533 if (ElementCount.isConstant()) {
1534 uint64_t ArrayLength = ElementCount.getAsInteger()->getLimitedValue();
1535 assert(ArrayLength &&
1536 "A member dtor for a 0 length array shouldn't be triggered!");
1537
1538 // Still handle this case if we don't have assertions enabled.
1539 if (!ArrayLength) {
1540 static SimpleProgramPointTag PT(
1541 "ExprEngine", "Skipping member 0 length array destruction, which "
1542 "shouldn't be in the CFG.");
1543 PostImplicitCall PP(DtorDecl, Member->getLocation(), LCtx,
1544 getCFGElementRef(), &PT);
1545 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1546 Bldr.generateSink(PP, State: Pred->getState(), Pred);
1547 return;
1548 }
1549 }
1550 }
1551
1552 EvalCallOptions CallOpts;
1553 FieldVal =
1554 makeElementRegion(State, LValue: FieldVal, Ty&: T, IsArray&: CallOpts.IsArrayCtorOrDtor, Idx);
1555
1556 NodeBuilder Bldr(Pred, Dst, getBuilderContext());
1557
1558 static SimpleProgramPointTag PT("ExprEngine",
1559 "Prepare for object destruction");
1560 PreImplicitCall PP(DtorDecl, Member->getLocation(), LCtx, getCFGElementRef(),
1561 &PT);
1562 Pred = Bldr.generateNode(PP, State, Pred);
1563
1564 if (!Pred)
1565 return;
1566 Bldr.takeNodes(N: Pred);
1567
1568 VisitCXXDestructor(ObjectType: T, Dest: FieldVal.getAsRegion(), S: CurDtor->getBody(),
1569 /*IsBase=*/IsBaseDtor: false, Pred, Dst, Options&: CallOpts);
1570}
1571
1572void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
1573 ExplodedNode *Pred,
1574 ExplodedNodeSet &Dst) {
1575 const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
1576 ProgramStateRef State = Pred->getState();
1577 const LocationContext *LC = Pred->getLocationContext();
1578 const MemRegion *MR = nullptr;
1579
1580 if (std::optional<SVal> V = getObjectUnderConstruction(
1581 State, Item: D.getBindTemporaryExpr(), LC: Pred->getLocationContext())) {
1582 // FIXME: Currently we insert temporary destructors for default parameters,
1583 // but we don't insert the constructors, so the entry in
1584 // ObjectsUnderConstruction may be missing.
1585 State = finishObjectConstruction(State, Item: D.getBindTemporaryExpr(),
1586 LC: Pred->getLocationContext());
1587 MR = V->getAsRegion();
1588 }
1589
1590 // If copy elision has occurred, and the constructor corresponding to the
1591 // destructor was elided, we need to skip the destructor as well.
1592 if (isDestructorElided(State, BTE, LC)) {
1593 State = cleanupElidedDestructor(State, BTE, LC);
1594 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1595 PostImplicitCall PP(D.getDestructorDecl(astContext&: getContext()),
1596 D.getBindTemporaryExpr()->getBeginLoc(),
1597 Pred->getLocationContext(), getCFGElementRef());
1598 Bldr.generateNode(PP, State, Pred);
1599 return;
1600 }
1601
1602 ExplodedNodeSet CleanDtorState;
1603 NodeBuilder Builder(Pred, CleanDtorState, *currBldrCtx);
1604 Builder.generateNode(S: D.getBindTemporaryExpr(), Pred, St: State);
1605
1606 QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
1607 // FIXME: Currently CleanDtorState can be empty here due to temporaries being
1608 // bound to default parameters.
1609 assert(CleanDtorState.size() <= 1);
1610 ExplodedNode *CleanPred =
1611 CleanDtorState.empty() ? Pred : *CleanDtorState.begin();
1612
1613 EvalCallOptions CallOpts;
1614 CallOpts.IsTemporaryCtorOrDtor = true;
1615 if (!MR) {
1616 // FIXME: If we have no MR, we still need to unwrap the array to avoid
1617 // destroying the whole array at once.
1618 //
1619 // For this case there is no universal solution as there is no way to
1620 // directly create an array of temporary objects. There are some expressions
1621 // however which can create temporary objects and have an array type.
1622 //
1623 // E.g.: std::initializer_list<S>{S(), S()};
1624 //
1625 // The expression above has a type of 'const struct S[2]' but it's a single
1626 // 'std::initializer_list<>'. The destructors of the 2 temporary 'S()'
1627 // objects will be called anyway, because they are 2 separate objects in 2
1628 // separate clusters, i.e.: not an array.
1629 //
1630 // Now the 'std::initializer_list<>' is not an array either even though it
1631 // has the type of an array. The point is, we only want to invoke the
1632 // destructor for the initializer list once not twice or so.
1633 while (const ArrayType *AT = getContext().getAsArrayType(T)) {
1634 T = AT->getElementType();
1635
1636 // FIXME: Enable this flag once we handle this case properly.
1637 // CallOpts.IsArrayCtorOrDtor = true;
1638 }
1639 } else {
1640 // FIXME: We'd eventually need to makeElementRegion() trick here,
1641 // but for now we don't have the respective construction contexts,
1642 // so MR would always be null in this case. Do nothing for now.
1643 }
1644 VisitCXXDestructor(ObjectType: T, Dest: MR, S: D.getBindTemporaryExpr(),
1645 /*IsBase=*/IsBaseDtor: false, Pred: CleanPred, Dst, Options&: CallOpts);
1646}
1647
1648void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
1649 NodeBuilderContext &BldCtx,
1650 ExplodedNode *Pred,
1651 ExplodedNodeSet &Dst,
1652 const CFGBlock *DstT,
1653 const CFGBlock *DstF) {
1654 BranchNodeBuilder TempDtorBuilder(Dst, BldCtx, DstT, DstF);
1655 ProgramStateRef State = Pred->getState();
1656 const LocationContext *LC = Pred->getLocationContext();
1657 if (getObjectUnderConstruction(State, Item: BTE, LC)) {
1658 TempDtorBuilder.generateNode(State, branch: true, Pred);
1659 } else {
1660 TempDtorBuilder.generateNode(State, branch: false, Pred);
1661 }
1662}
1663
1664void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
1665 ExplodedNodeSet &PreVisit,
1666 ExplodedNodeSet &Dst) {
1667 // This is a fallback solution in case we didn't have a construction
1668 // context when we were constructing the temporary. Otherwise the map should
1669 // have been populated there.
1670 if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {
1671 // In case we don't have temporary destructors in the CFG, do not mark
1672 // the initialization - we would otherwise never clean it up.
1673 Dst = PreVisit;
1674 return;
1675 }
1676 NodeBuilder Builder(PreVisit, Dst, *currBldrCtx);
1677 for (ExplodedNode *Node : PreVisit) {
1678 ProgramStateRef State = Node->getState();
1679 const LocationContext *LC = Node->getLocationContext();
1680 if (!getObjectUnderConstruction(State, Item: BTE, LC)) {
1681 // FIXME: Currently the state might also already contain the marker due to
1682 // incorrect handling of temporaries bound to default parameters; for
1683 // those, we currently skip the CXXBindTemporaryExpr but rely on adding
1684 // temporary destructor nodes.
1685 State = addObjectUnderConstruction(State, Item: BTE, LC, V: UnknownVal());
1686 }
1687 Builder.generateNode(S: BTE, Pred: Node, St: State);
1688 }
1689}
1690
1691ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State,
1692 ArrayRef<SVal> Vs,
1693 PointerEscapeKind K,
1694 const CallEvent *Call) const {
1695 class CollectReachableSymbolsCallback final : public SymbolVisitor {
1696 InvalidatedSymbols &Symbols;
1697
1698 public:
1699 explicit CollectReachableSymbolsCallback(InvalidatedSymbols &Symbols)
1700 : Symbols(Symbols) {}
1701
1702 const InvalidatedSymbols &getSymbols() const { return Symbols; }
1703
1704 bool VisitSymbol(SymbolRef Sym) override {
1705 Symbols.insert(V: Sym);
1706 return true;
1707 }
1708 };
1709 InvalidatedSymbols Symbols;
1710 CollectReachableSymbolsCallback CallBack(Symbols);
1711 for (SVal V : Vs)
1712 State->scanReachableSymbols(val: V, visitor&: CallBack);
1713
1714 return getCheckerManager().runCheckersForPointerEscape(
1715 State, Escaped: CallBack.getSymbols(), Call, Kind: K, ITraits: nullptr);
1716}
1717
1718void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
1719 ExplodedNodeSet &DstTop) {
1720 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1721 S->getBeginLoc(), "Error evaluating statement");
1722 ExplodedNodeSet Dst;
1723 NodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
1724
1725 assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
1726
1727 switch (S->getStmtClass()) {
1728 // C++, OpenMP and ARC stuff we don't support yet.
1729 case Stmt::CXXDependentScopeMemberExprClass:
1730 case Stmt::CXXReflectExprClass:
1731 case Stmt::CXXTryStmtClass:
1732 case Stmt::CXXTypeidExprClass:
1733 case Stmt::CXXUuidofExprClass:
1734 case Stmt::CXXFoldExprClass:
1735 case Stmt::MSPropertyRefExprClass:
1736 case Stmt::MSPropertySubscriptExprClass:
1737 case Stmt::CXXUnresolvedConstructExprClass:
1738 case Stmt::DependentScopeDeclRefExprClass:
1739 case Stmt::ArrayTypeTraitExprClass:
1740 case Stmt::ExpressionTraitExprClass:
1741 case Stmt::UnresolvedLookupExprClass:
1742 case Stmt::UnresolvedMemberExprClass:
1743 case Stmt::RecoveryExprClass:
1744 case Stmt::CXXNoexceptExprClass:
1745 case Stmt::PackExpansionExprClass:
1746 case Stmt::PackIndexingExprClass:
1747 case Stmt::SubstNonTypeTemplateParmPackExprClass:
1748 case Stmt::FunctionParmPackExprClass:
1749 case Stmt::CoroutineBodyStmtClass:
1750 case Stmt::CoawaitExprClass:
1751 case Stmt::DependentCoawaitExprClass:
1752 case Stmt::CoreturnStmtClass:
1753 case Stmt::CoyieldExprClass:
1754 case Stmt::SEHTryStmtClass:
1755 case Stmt::SEHExceptStmtClass:
1756 case Stmt::SEHLeaveStmtClass:
1757 case Stmt::SEHFinallyStmtClass:
1758 case Stmt::OMPCanonicalLoopClass:
1759 case Stmt::OMPParallelDirectiveClass:
1760 case Stmt::OMPSimdDirectiveClass:
1761 case Stmt::OMPForDirectiveClass:
1762 case Stmt::OMPForSimdDirectiveClass:
1763 case Stmt::OMPSectionsDirectiveClass:
1764 case Stmt::OMPSectionDirectiveClass:
1765 case Stmt::OMPScopeDirectiveClass:
1766 case Stmt::OMPSingleDirectiveClass:
1767 case Stmt::OMPMasterDirectiveClass:
1768 case Stmt::OMPCriticalDirectiveClass:
1769 case Stmt::OMPParallelForDirectiveClass:
1770 case Stmt::OMPParallelForSimdDirectiveClass:
1771 case Stmt::OMPParallelSectionsDirectiveClass:
1772 case Stmt::OMPParallelMasterDirectiveClass:
1773 case Stmt::OMPParallelMaskedDirectiveClass:
1774 case Stmt::OMPTaskDirectiveClass:
1775 case Stmt::OMPTaskyieldDirectiveClass:
1776 case Stmt::OMPBarrierDirectiveClass:
1777 case Stmt::OMPTaskwaitDirectiveClass:
1778 case Stmt::OMPErrorDirectiveClass:
1779 case Stmt::OMPTaskgroupDirectiveClass:
1780 case Stmt::OMPFlushDirectiveClass:
1781 case Stmt::OMPDepobjDirectiveClass:
1782 case Stmt::OMPScanDirectiveClass:
1783 case Stmt::OMPOrderedDirectiveClass:
1784 case Stmt::OMPAtomicDirectiveClass:
1785 case Stmt::OMPAssumeDirectiveClass:
1786 case Stmt::OMPTargetDirectiveClass:
1787 case Stmt::OMPTargetDataDirectiveClass:
1788 case Stmt::OMPTargetEnterDataDirectiveClass:
1789 case Stmt::OMPTargetExitDataDirectiveClass:
1790 case Stmt::OMPTargetParallelDirectiveClass:
1791 case Stmt::OMPTargetParallelForDirectiveClass:
1792 case Stmt::OMPTargetUpdateDirectiveClass:
1793 case Stmt::OMPTeamsDirectiveClass:
1794 case Stmt::OMPCancellationPointDirectiveClass:
1795 case Stmt::OMPCancelDirectiveClass:
1796 case Stmt::OMPTaskLoopDirectiveClass:
1797 case Stmt::OMPTaskLoopSimdDirectiveClass:
1798 case Stmt::OMPMasterTaskLoopDirectiveClass:
1799 case Stmt::OMPMaskedTaskLoopDirectiveClass:
1800 case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1801 case Stmt::OMPMaskedTaskLoopSimdDirectiveClass:
1802 case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1803 case Stmt::OMPParallelMaskedTaskLoopDirectiveClass:
1804 case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:
1805 case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass:
1806 case Stmt::OMPDistributeDirectiveClass:
1807 case Stmt::OMPDistributeParallelForDirectiveClass:
1808 case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1809 case Stmt::OMPDistributeSimdDirectiveClass:
1810 case Stmt::OMPTargetParallelForSimdDirectiveClass:
1811 case Stmt::OMPTargetSimdDirectiveClass:
1812 case Stmt::OMPTeamsDistributeDirectiveClass:
1813 case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1814 case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1815 case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1816 case Stmt::OMPTargetTeamsDirectiveClass:
1817 case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1818 case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1819 case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1820 case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1821 case Stmt::OMPReverseDirectiveClass:
1822 case Stmt::OMPStripeDirectiveClass:
1823 case Stmt::OMPTileDirectiveClass:
1824 case Stmt::OMPInterchangeDirectiveClass:
1825 case Stmt::OMPFuseDirectiveClass:
1826 case Stmt::OMPInteropDirectiveClass:
1827 case Stmt::OMPDispatchDirectiveClass:
1828 case Stmt::OMPMaskedDirectiveClass:
1829 case Stmt::OMPGenericLoopDirectiveClass:
1830 case Stmt::OMPTeamsGenericLoopDirectiveClass:
1831 case Stmt::OMPTargetTeamsGenericLoopDirectiveClass:
1832 case Stmt::OMPParallelGenericLoopDirectiveClass:
1833 case Stmt::OMPTargetParallelGenericLoopDirectiveClass:
1834 case Stmt::CapturedStmtClass:
1835 case Stmt::SYCLKernelCallStmtClass:
1836 case Stmt::OpenACCComputeConstructClass:
1837 case Stmt::OpenACCLoopConstructClass:
1838 case Stmt::OpenACCCombinedConstructClass:
1839 case Stmt::OpenACCDataConstructClass:
1840 case Stmt::OpenACCEnterDataConstructClass:
1841 case Stmt::OpenACCExitDataConstructClass:
1842 case Stmt::OpenACCHostDataConstructClass:
1843 case Stmt::OpenACCWaitConstructClass:
1844 case Stmt::OpenACCCacheConstructClass:
1845 case Stmt::OpenACCInitConstructClass:
1846 case Stmt::OpenACCShutdownConstructClass:
1847 case Stmt::OpenACCSetConstructClass:
1848 case Stmt::OpenACCUpdateConstructClass:
1849 case Stmt::OpenACCAtomicConstructClass:
1850 case Stmt::OMPUnrollDirectiveClass:
1851 case Stmt::OMPMetaDirectiveClass:
1852 case Stmt::HLSLOutArgExprClass: {
1853 const ExplodedNode *node = Bldr.generateSink(S, Pred, St: Pred->getState());
1854 Engine.addAbortedBlock(node, block: currBldrCtx->getBlock());
1855 break;
1856 }
1857
1858 case Stmt::ParenExprClass:
1859 llvm_unreachable("ParenExprs already handled.");
1860 case Stmt::GenericSelectionExprClass:
1861 llvm_unreachable("GenericSelectionExprs already handled.");
1862 // Cases that should never be evaluated simply because they shouldn't
1863 // appear in the CFG.
1864 case Stmt::BreakStmtClass:
1865 case Stmt::CaseStmtClass:
1866 case Stmt::CompoundStmtClass:
1867 case Stmt::ContinueStmtClass:
1868 case Stmt::CXXForRangeStmtClass:
1869 case Stmt::DefaultStmtClass:
1870 case Stmt::DoStmtClass:
1871 case Stmt::ForStmtClass:
1872 case Stmt::GotoStmtClass:
1873 case Stmt::IfStmtClass:
1874 case Stmt::IndirectGotoStmtClass:
1875 case Stmt::LabelStmtClass:
1876 case Stmt::NoStmtClass:
1877 case Stmt::NullStmtClass:
1878 case Stmt::SwitchStmtClass:
1879 case Stmt::WhileStmtClass:
1880 case Stmt::DeferStmtClass:
1881 case Expr::MSDependentExistsStmtClass:
1882 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
1883 case Stmt::ImplicitValueInitExprClass:
1884 // These nodes are shared in the CFG and would case caching out.
1885 // Moreover, no additional evaluation required for them, the
1886 // analyzer can reconstruct these values from the AST.
1887 llvm_unreachable("Should be pruned from CFG");
1888
1889 case Stmt::ObjCSubscriptRefExprClass:
1890 case Stmt::ObjCPropertyRefExprClass:
1891 llvm_unreachable("These are handled by PseudoObjectExpr");
1892
1893 case Stmt::GNUNullExprClass: {
1894 // GNU __null is a pointer-width integer, not an actual pointer.
1895 ProgramStateRef state = Pred->getState();
1896 state = state->BindExpr(
1897 S, LCtx: Pred->getLocationContext(),
1898 V: svalBuilder.makeIntValWithWidth(ptrType: getContext().VoidPtrTy, integer: 0));
1899 Bldr.generateNode(S, Pred, St: state);
1900 break;
1901 }
1902
1903 case Stmt::ObjCAtSynchronizedStmtClass:
1904 Bldr.takeNodes(N: Pred);
1905 VisitObjCAtSynchronizedStmt(S: cast<ObjCAtSynchronizedStmt>(Val: S), Pred, Dst);
1906 Bldr.addNodes(S: Dst);
1907 break;
1908
1909 case Expr::ConstantExprClass:
1910 case Stmt::ExprWithCleanupsClass:
1911 // Handled due to fully linearised CFG.
1912 break;
1913
1914 case Stmt::CXXBindTemporaryExprClass: {
1915 Bldr.takeNodes(N: Pred);
1916 ExplodedNodeSet PreVisit;
1917 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
1918 ExplodedNodeSet Next;
1919 VisitCXXBindTemporaryExpr(BTE: cast<CXXBindTemporaryExpr>(Val: S), PreVisit, Dst&: Next);
1920 getCheckerManager().runCheckersForPostStmt(Dst, Src: Next, S, Eng&: *this);
1921 Bldr.addNodes(S: Dst);
1922 break;
1923 }
1924
1925 case Stmt::ArrayInitLoopExprClass:
1926 Bldr.takeNodes(N: Pred);
1927 VisitArrayInitLoopExpr(Ex: cast<ArrayInitLoopExpr>(Val: S), Pred, Dst);
1928 Bldr.addNodes(S: Dst);
1929 break;
1930 // Cases not handled yet; but will handle some day.
1931 case Stmt::DesignatedInitExprClass:
1932 case Stmt::DesignatedInitUpdateExprClass:
1933 case Stmt::ArrayInitIndexExprClass:
1934 case Stmt::ExtVectorElementExprClass:
1935 case Stmt::MatrixElementExprClass:
1936 case Stmt::ImaginaryLiteralClass:
1937 case Stmt::ObjCAtCatchStmtClass:
1938 case Stmt::ObjCAtFinallyStmtClass:
1939 case Stmt::ObjCAtTryStmtClass:
1940 case Stmt::ObjCAutoreleasePoolStmtClass:
1941 case Stmt::ObjCEncodeExprClass:
1942 case Stmt::ObjCIsaExprClass:
1943 case Stmt::ObjCProtocolExprClass:
1944 case Stmt::ObjCSelectorExprClass:
1945 case Stmt::ParenListExprClass:
1946 case Stmt::ShuffleVectorExprClass:
1947 case Stmt::ConvertVectorExprClass:
1948 case Stmt::VAArgExprClass:
1949 case Stmt::CUDAKernelCallExprClass:
1950 case Stmt::OpaqueValueExprClass:
1951 case Stmt::AsTypeExprClass:
1952 case Stmt::ConceptSpecializationExprClass:
1953 case Stmt::CXXRewrittenBinaryOperatorClass:
1954 case Stmt::RequiresExprClass:
1955 case Stmt::EmbedExprClass:
1956 // Fall through.
1957
1958 // Cases we intentionally don't evaluate, since they don't need
1959 // to be explicitly evaluated.
1960 case Stmt::PredefinedExprClass:
1961 case Stmt::AddrLabelExprClass:
1962 case Stmt::IntegerLiteralClass:
1963 case Stmt::FixedPointLiteralClass:
1964 case Stmt::CharacterLiteralClass:
1965 case Stmt::CXXScalarValueInitExprClass:
1966 case Stmt::CXXBoolLiteralExprClass:
1967 case Stmt::ObjCBoolLiteralExprClass:
1968 case Stmt::ObjCAvailabilityCheckExprClass:
1969 case Stmt::FloatingLiteralClass:
1970 case Stmt::NoInitExprClass:
1971 case Stmt::SizeOfPackExprClass:
1972 case Stmt::StringLiteralClass:
1973 case Stmt::SourceLocExprClass:
1974 case Stmt::ObjCStringLiteralClass:
1975 case Stmt::CXXPseudoDestructorExprClass:
1976 case Stmt::SubstNonTypeTemplateParmExprClass:
1977 case Stmt::CXXNullPtrLiteralExprClass:
1978 case Stmt::ArraySectionExprClass:
1979 case Stmt::OMPArrayShapingExprClass:
1980 case Stmt::OMPIteratorExprClass:
1981 case Stmt::SYCLUniqueStableNameExprClass:
1982 case Stmt::OpenACCAsteriskSizeExprClass:
1983 case Stmt::TypeTraitExprClass: {
1984 Bldr.takeNodes(N: Pred);
1985 ExplodedNodeSet preVisit;
1986 getCheckerManager().runCheckersForPreStmt(Dst&: preVisit, Src: Pred, S, Eng&: *this);
1987 getCheckerManager().runCheckersForPostStmt(Dst, Src: preVisit, S, Eng&: *this);
1988 Bldr.addNodes(S: Dst);
1989 break;
1990 }
1991
1992 case Stmt::AttributedStmtClass: {
1993 Bldr.takeNodes(N: Pred);
1994 VisitAttributedStmt(A: cast<AttributedStmt>(Val: S), Pred, Dst);
1995 Bldr.addNodes(S: Dst);
1996 break;
1997 }
1998
1999 case Stmt::CXXDefaultArgExprClass:
2000 case Stmt::CXXDefaultInitExprClass: {
2001 Bldr.takeNodes(N: Pred);
2002 ExplodedNodeSet PreVisit;
2003 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2004
2005 ExplodedNodeSet Tmp;
2006 NodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
2007
2008 const Expr *ArgE;
2009 if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(Val: S))
2010 ArgE = DefE->getExpr();
2011 else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(Val: S))
2012 ArgE = DefE->getExpr();
2013 else
2014 llvm_unreachable("unknown constant wrapper kind");
2015
2016 bool IsTemporary = false;
2017 if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(Val: ArgE)) {
2018 ArgE = MTE->getSubExpr();
2019 IsTemporary = true;
2020 }
2021
2022 std::optional<SVal> ConstantVal = svalBuilder.getConstantVal(E: ArgE);
2023 if (!ConstantVal)
2024 ConstantVal = UnknownVal();
2025
2026 const LocationContext *LCtx = Pred->getLocationContext();
2027 for (const auto I : PreVisit) {
2028 ProgramStateRef State = I->getState();
2029 State = State->BindExpr(S, LCtx, V: *ConstantVal);
2030 if (IsTemporary)
2031 State = createTemporaryRegionIfNeeded(State, LC: LCtx,
2032 InitWithAdjustments: cast<Expr>(Val: S),
2033 Result: cast<Expr>(Val: S));
2034 Bldr2.generateNode(S, Pred: I, St: State);
2035 }
2036
2037 getCheckerManager().runCheckersForPostStmt(Dst, Src: Tmp, S, Eng&: *this);
2038 Bldr.addNodes(S: Dst);
2039 break;
2040 }
2041
2042 // Cases we evaluate as opaque expressions, conjuring a symbol.
2043 case Stmt::CXXStdInitializerListExprClass:
2044 case Expr::ObjCArrayLiteralClass:
2045 case Expr::ObjCDictionaryLiteralClass:
2046 case Expr::ObjCBoxedExprClass: {
2047 Bldr.takeNodes(N: Pred);
2048
2049 ExplodedNodeSet preVisit;
2050 getCheckerManager().runCheckersForPreStmt(Dst&: preVisit, Src: Pred, S, Eng&: *this);
2051
2052 ExplodedNodeSet Tmp;
2053 NodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
2054
2055 const auto *Ex = cast<Expr>(Val: S);
2056 QualType resultType = Ex->getType();
2057
2058 for (const auto N : preVisit) {
2059 const LocationContext *LCtx = N->getLocationContext();
2060 SVal result = svalBuilder.conjureSymbolVal(
2061 /*symbolTag=*/nullptr, elem: getCFGElementRef(), LCtx, type: resultType,
2062 count: currBldrCtx->blockCount());
2063 ProgramStateRef State = N->getState()->BindExpr(S: Ex, LCtx, V: result);
2064
2065 // Escape pointers passed into the list, unless it's an ObjC boxed
2066 // expression which is not a boxable C structure.
2067 if (!(isa<ObjCBoxedExpr>(Val: Ex) &&
2068 !cast<ObjCBoxedExpr>(Val: Ex)->getSubExpr()
2069 ->getType()->isRecordType()))
2070 for (auto Child : Ex->children()) {
2071 assert(Child);
2072 SVal Val = State->getSVal(Ex: Child, LCtx);
2073 State = escapeValues(State, Vs: Val, K: PSK_EscapeOther);
2074 }
2075
2076 Bldr2.generateNode(S, Pred: N, St: State);
2077 }
2078
2079 getCheckerManager().runCheckersForPostStmt(Dst, Src: Tmp, S, Eng&: *this);
2080 Bldr.addNodes(S: Dst);
2081 break;
2082 }
2083
2084 case Stmt::ArraySubscriptExprClass:
2085 Bldr.takeNodes(N: Pred);
2086 VisitArraySubscriptExpr(Ex: cast<ArraySubscriptExpr>(Val: S), Pred, Dst);
2087 Bldr.addNodes(S: Dst);
2088 break;
2089
2090 case Stmt::MatrixSingleSubscriptExprClass:
2091 llvm_unreachable(
2092 "Support for MatrixSingleSubscriptExprClass is not implemented.");
2093 break;
2094
2095 case Stmt::MatrixSubscriptExprClass:
2096 llvm_unreachable("Support for MatrixSubscriptExpr is not implemented.");
2097 break;
2098
2099 case Stmt::GCCAsmStmtClass: {
2100 Bldr.takeNodes(N: Pred);
2101 ExplodedNodeSet PreVisit;
2102 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2103 ExplodedNodeSet PostVisit;
2104 for (ExplodedNode *const N : PreVisit)
2105 VisitGCCAsmStmt(A: cast<GCCAsmStmt>(Val: S), Pred: N, Dst&: PostVisit);
2106 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2107 Bldr.addNodes(S: Dst);
2108 break;
2109 }
2110
2111 case Stmt::MSAsmStmtClass:
2112 Bldr.takeNodes(N: Pred);
2113 VisitMSAsmStmt(A: cast<MSAsmStmt>(Val: S), Pred, Dst);
2114 Bldr.addNodes(S: Dst);
2115 break;
2116
2117 case Stmt::BlockExprClass:
2118 Bldr.takeNodes(N: Pred);
2119 VisitBlockExpr(BE: cast<BlockExpr>(Val: S), Pred, Dst);
2120 Bldr.addNodes(S: Dst);
2121 break;
2122
2123 case Stmt::LambdaExprClass:
2124 if (AMgr.options.ShouldInlineLambdas) {
2125 Bldr.takeNodes(N: Pred);
2126 VisitLambdaExpr(LE: cast<LambdaExpr>(Val: S), Pred, Dst);
2127 Bldr.addNodes(S: Dst);
2128 } else {
2129 const ExplodedNode *node = Bldr.generateSink(S, Pred, St: Pred->getState());
2130 Engine.addAbortedBlock(node, block: currBldrCtx->getBlock());
2131 }
2132 break;
2133
2134 case Stmt::BinaryOperatorClass: {
2135 const auto *B = cast<BinaryOperator>(Val: S);
2136 if (B->isLogicalOp()) {
2137 Bldr.takeNodes(N: Pred);
2138 VisitLogicalExpr(B, Pred, Dst);
2139 Bldr.addNodes(S: Dst);
2140 break;
2141 }
2142 else if (B->getOpcode() == BO_Comma) {
2143 ProgramStateRef state = Pred->getState();
2144 Bldr.generateNode(S: B, Pred,
2145 St: state->BindExpr(S: B, LCtx: Pred->getLocationContext(),
2146 V: state->getSVal(Ex: B->getRHS(),
2147 LCtx: Pred->getLocationContext())));
2148 break;
2149 }
2150
2151 Bldr.takeNodes(N: Pred);
2152
2153 if (AMgr.options.ShouldEagerlyAssume &&
2154 (B->isRelationalOp() || B->isEqualityOp())) {
2155 ExplodedNodeSet Tmp;
2156 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst&: Tmp);
2157 evalEagerlyAssumeBifurcation(Dst, Src&: Tmp, Ex: cast<Expr>(Val: S));
2158 }
2159 else
2160 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst);
2161
2162 Bldr.addNodes(S: Dst);
2163 break;
2164 }
2165
2166 case Stmt::CXXOperatorCallExprClass: {
2167 const auto *OCE = cast<CXXOperatorCallExpr>(Val: S);
2168
2169 // For instance method operators, make sure the 'this' argument has a
2170 // valid region.
2171 const Decl *Callee = OCE->getCalleeDecl();
2172 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Val: Callee)) {
2173 if (MD->isImplicitObjectMemberFunction()) {
2174 ProgramStateRef State = Pred->getState();
2175 const LocationContext *LCtx = Pred->getLocationContext();
2176 ProgramStateRef NewState =
2177 createTemporaryRegionIfNeeded(State, LC: LCtx, InitWithAdjustments: OCE->getArg(Arg: 0));
2178 if (NewState != State) {
2179 Pred = Bldr.generateNode(S: OCE, Pred, St: NewState, /*tag=*/nullptr,
2180 K: ProgramPoint::PreStmtKind);
2181 // Did we cache out?
2182 if (!Pred)
2183 break;
2184 }
2185 }
2186 }
2187 [[fallthrough]];
2188 }
2189
2190 case Stmt::CallExprClass:
2191 case Stmt::CXXMemberCallExprClass:
2192 case Stmt::UserDefinedLiteralClass:
2193 Bldr.takeNodes(N: Pred);
2194 VisitCallExpr(CE: cast<CallExpr>(Val: S), Pred, Dst);
2195 Bldr.addNodes(S: Dst);
2196 break;
2197
2198 case Stmt::CXXCatchStmtClass:
2199 Bldr.takeNodes(N: Pred);
2200 VisitCXXCatchStmt(CS: cast<CXXCatchStmt>(Val: S), Pred, Dst);
2201 Bldr.addNodes(S: Dst);
2202 break;
2203
2204 case Stmt::CXXTemporaryObjectExprClass:
2205 case Stmt::CXXConstructExprClass:
2206 Bldr.takeNodes(N: Pred);
2207 VisitCXXConstructExpr(E: cast<CXXConstructExpr>(Val: S), Pred, Dst);
2208 Bldr.addNodes(S: Dst);
2209 break;
2210
2211 case Stmt::CXXInheritedCtorInitExprClass:
2212 Bldr.takeNodes(N: Pred);
2213 VisitCXXInheritedCtorInitExpr(E: cast<CXXInheritedCtorInitExpr>(Val: S), Pred,
2214 Dst);
2215 Bldr.addNodes(S: Dst);
2216 break;
2217
2218 case Stmt::CXXNewExprClass: {
2219 Bldr.takeNodes(N: Pred);
2220
2221 ExplodedNodeSet PreVisit;
2222 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2223
2224 ExplodedNodeSet PostVisit;
2225 for (const auto i : PreVisit)
2226 VisitCXXNewExpr(CNE: cast<CXXNewExpr>(Val: S), Pred: i, Dst&: PostVisit);
2227
2228 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2229 Bldr.addNodes(S: Dst);
2230 break;
2231 }
2232
2233 case Stmt::CXXDeleteExprClass: {
2234 Bldr.takeNodes(N: Pred);
2235 ExplodedNodeSet PreVisit;
2236 const auto *CDE = cast<CXXDeleteExpr>(Val: S);
2237 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2238 ExplodedNodeSet PostVisit;
2239 getCheckerManager().runCheckersForPostStmt(Dst&: PostVisit, Src: PreVisit, S, Eng&: *this);
2240
2241 for (const auto i : PostVisit)
2242 VisitCXXDeleteExpr(CDE, Pred: i, Dst);
2243
2244 Bldr.addNodes(S: Dst);
2245 break;
2246 }
2247 // FIXME: ChooseExpr is really a constant. We need to fix
2248 // the CFG do not model them as explicit control-flow.
2249
2250 case Stmt::ChooseExprClass: { // __builtin_choose_expr
2251 Bldr.takeNodes(N: Pred);
2252 const auto *C = cast<ChooseExpr>(Val: S);
2253 VisitGuardedExpr(Ex: C, L: C->getLHS(), R: C->getRHS(), Pred, Dst);
2254 Bldr.addNodes(S: Dst);
2255 break;
2256 }
2257
2258 case Stmt::CompoundAssignOperatorClass:
2259 Bldr.takeNodes(N: Pred);
2260 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst);
2261 Bldr.addNodes(S: Dst);
2262 break;
2263
2264 case Stmt::CompoundLiteralExprClass:
2265 Bldr.takeNodes(N: Pred);
2266 VisitCompoundLiteralExpr(CL: cast<CompoundLiteralExpr>(Val: S), Pred, Dst);
2267 Bldr.addNodes(S: Dst);
2268 break;
2269
2270 case Stmt::BinaryConditionalOperatorClass:
2271 case Stmt::ConditionalOperatorClass: { // '?' operator
2272 Bldr.takeNodes(N: Pred);
2273 const auto *C = cast<AbstractConditionalOperator>(Val: S);
2274 VisitGuardedExpr(Ex: C, L: C->getTrueExpr(), R: C->getFalseExpr(), Pred, Dst);
2275 Bldr.addNodes(S: Dst);
2276 break;
2277 }
2278
2279 case Stmt::CXXThisExprClass:
2280 Bldr.takeNodes(N: Pred);
2281 VisitCXXThisExpr(TE: cast<CXXThisExpr>(Val: S), Pred, Dst);
2282 Bldr.addNodes(S: Dst);
2283 break;
2284
2285 case Stmt::DeclRefExprClass: {
2286 Bldr.takeNodes(N: Pred);
2287 const auto *DE = cast<DeclRefExpr>(Val: S);
2288 VisitCommonDeclRefExpr(DR: DE, D: DE->getDecl(), Pred, Dst);
2289 Bldr.addNodes(S: Dst);
2290 break;
2291 }
2292
2293 case Stmt::DeclStmtClass:
2294 Bldr.takeNodes(N: Pred);
2295 VisitDeclStmt(DS: cast<DeclStmt>(Val: S), Pred, Dst);
2296 Bldr.addNodes(S: Dst);
2297 break;
2298
2299 case Stmt::ImplicitCastExprClass:
2300 case Stmt::CStyleCastExprClass:
2301 case Stmt::CXXStaticCastExprClass:
2302 case Stmt::CXXDynamicCastExprClass:
2303 case Stmt::CXXReinterpretCastExprClass:
2304 case Stmt::CXXConstCastExprClass:
2305 case Stmt::CXXFunctionalCastExprClass:
2306 case Stmt::BuiltinBitCastExprClass:
2307 case Stmt::ObjCBridgedCastExprClass:
2308 case Stmt::CXXAddrspaceCastExprClass: {
2309 Bldr.takeNodes(N: Pred);
2310 const auto *C = cast<CastExpr>(Val: S);
2311 ExplodedNodeSet dstExpr;
2312 VisitCast(CastE: C, Ex: C->getSubExpr(), Pred, Dst&: dstExpr);
2313
2314 // Handle the postvisit checks.
2315 getCheckerManager().runCheckersForPostStmt(Dst, Src: dstExpr, S: C, Eng&: *this);
2316 Bldr.addNodes(S: Dst);
2317 break;
2318 }
2319
2320 case Expr::MaterializeTemporaryExprClass: {
2321 Bldr.takeNodes(N: Pred);
2322 const auto *MTE = cast<MaterializeTemporaryExpr>(Val: S);
2323 ExplodedNodeSet dstPrevisit;
2324 getCheckerManager().runCheckersForPreStmt(Dst&: dstPrevisit, Src: Pred, S: MTE, Eng&: *this);
2325 ExplodedNodeSet dstExpr;
2326 for (const auto i : dstPrevisit)
2327 CreateCXXTemporaryObject(ME: MTE, Pred: i, Dst&: dstExpr);
2328 getCheckerManager().runCheckersForPostStmt(Dst, Src: dstExpr, S: MTE, Eng&: *this);
2329 Bldr.addNodes(S: Dst);
2330 break;
2331 }
2332
2333 case Stmt::InitListExprClass: {
2334 const InitListExpr *E = cast<InitListExpr>(Val: S);
2335 Bldr.takeNodes(N: Pred);
2336 ConstructInitList(Source: E, Args: E->inits(), IsTransparent: E->isTransparent(), Pred, Dst);
2337 Bldr.addNodes(S: Dst);
2338 break;
2339 }
2340
2341 case Expr::CXXParenListInitExprClass: {
2342 const CXXParenListInitExpr *E = cast<CXXParenListInitExpr>(Val: S);
2343 Bldr.takeNodes(N: Pred);
2344 ConstructInitList(Source: E, Args: E->getInitExprs(), /*IsTransparent*/ false, Pred,
2345 Dst);
2346 Bldr.addNodes(S: Dst);
2347 break;
2348 }
2349
2350 case Stmt::MemberExprClass:
2351 Bldr.takeNodes(N: Pred);
2352 VisitMemberExpr(M: cast<MemberExpr>(Val: S), Pred, Dst);
2353 Bldr.addNodes(S: Dst);
2354 break;
2355
2356 case Stmt::AtomicExprClass:
2357 Bldr.takeNodes(N: Pred);
2358 VisitAtomicExpr(E: cast<AtomicExpr>(Val: S), Pred, Dst);
2359 Bldr.addNodes(S: Dst);
2360 break;
2361
2362 case Stmt::ObjCIvarRefExprClass:
2363 Bldr.takeNodes(N: Pred);
2364 VisitLvalObjCIvarRefExpr(DR: cast<ObjCIvarRefExpr>(Val: S), Pred, Dst);
2365 Bldr.addNodes(S: Dst);
2366 break;
2367
2368 case Stmt::ObjCForCollectionStmtClass:
2369 Bldr.takeNodes(N: Pred);
2370 VisitObjCForCollectionStmt(S: cast<ObjCForCollectionStmt>(Val: S), Pred, Dst);
2371 Bldr.addNodes(S: Dst);
2372 break;
2373
2374 case Stmt::ObjCMessageExprClass:
2375 Bldr.takeNodes(N: Pred);
2376 VisitObjCMessage(ME: cast<ObjCMessageExpr>(Val: S), Pred, Dst);
2377 Bldr.addNodes(S: Dst);
2378 break;
2379
2380 case Stmt::ObjCAtThrowStmtClass:
2381 case Stmt::CXXThrowExprClass:
2382 // FIXME: This is not complete. We basically treat @throw as
2383 // an abort.
2384 Bldr.generateSink(S, Pred, St: Pred->getState());
2385 break;
2386
2387 case Stmt::ReturnStmtClass:
2388 Bldr.takeNodes(N: Pred);
2389 VisitReturnStmt(R: cast<ReturnStmt>(Val: S), Pred, Dst);
2390 Bldr.addNodes(S: Dst);
2391 break;
2392
2393 case Stmt::OffsetOfExprClass: {
2394 Bldr.takeNodes(N: Pred);
2395 ExplodedNodeSet PreVisit;
2396 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2397
2398 ExplodedNodeSet PostVisit;
2399 for (const auto Node : PreVisit)
2400 VisitOffsetOfExpr(Ex: cast<OffsetOfExpr>(Val: S), Pred: Node, Dst&: PostVisit);
2401
2402 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2403 Bldr.addNodes(S: Dst);
2404 break;
2405 }
2406
2407 case Stmt::UnaryExprOrTypeTraitExprClass:
2408 Bldr.takeNodes(N: Pred);
2409 VisitUnaryExprOrTypeTraitExpr(Ex: cast<UnaryExprOrTypeTraitExpr>(Val: S),
2410 Pred, Dst);
2411 Bldr.addNodes(S: Dst);
2412 break;
2413
2414 case Stmt::StmtExprClass: {
2415 const auto *SE = cast<StmtExpr>(Val: S);
2416
2417 if (SE->getSubStmt()->body_empty()) {
2418 // Empty statement expression.
2419 assert(SE->getType() == getContext().VoidTy
2420 && "Empty statement expression must have void type.");
2421 break;
2422 }
2423
2424 if (const auto *LastExpr =
2425 dyn_cast<Expr>(Val: *SE->getSubStmt()->body_rbegin())) {
2426 ProgramStateRef state = Pred->getState();
2427 Bldr.generateNode(S: SE, Pred,
2428 St: state->BindExpr(S: SE, LCtx: Pred->getLocationContext(),
2429 V: state->getSVal(Ex: LastExpr,
2430 LCtx: Pred->getLocationContext())));
2431 }
2432 break;
2433 }
2434
2435 case Stmt::UnaryOperatorClass: {
2436 Bldr.takeNodes(N: Pred);
2437 const auto *U = cast<UnaryOperator>(Val: S);
2438 if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
2439 ExplodedNodeSet Tmp;
2440 VisitUnaryOperator(B: U, Pred, Dst&: Tmp);
2441 evalEagerlyAssumeBifurcation(Dst, Src&: Tmp, Ex: U);
2442 }
2443 else
2444 VisitUnaryOperator(B: U, Pred, Dst);
2445 Bldr.addNodes(S: Dst);
2446 break;
2447 }
2448
2449 case Stmt::PseudoObjectExprClass: {
2450 Bldr.takeNodes(N: Pred);
2451 ProgramStateRef state = Pred->getState();
2452 const auto *PE = cast<PseudoObjectExpr>(Val: S);
2453 if (const Expr *Result = PE->getResultExpr()) {
2454 SVal V = state->getSVal(Ex: Result, LCtx: Pred->getLocationContext());
2455 Bldr.generateNode(S, Pred,
2456 St: state->BindExpr(S, LCtx: Pred->getLocationContext(), V));
2457 }
2458 else
2459 Bldr.generateNode(S, Pred,
2460 St: state->BindExpr(S, LCtx: Pred->getLocationContext(),
2461 V: UnknownVal()));
2462
2463 Bldr.addNodes(S: Dst);
2464 break;
2465 }
2466
2467 case Expr::ObjCIndirectCopyRestoreExprClass: {
2468 // ObjCIndirectCopyRestoreExpr implies passing a temporary for
2469 // correctness of lifetime management. Due to limited analysis
2470 // of ARC, this is implemented as direct arg passing.
2471 Bldr.takeNodes(N: Pred);
2472 ProgramStateRef state = Pred->getState();
2473 const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(Val: S);
2474 const Expr *E = OIE->getSubExpr();
2475 SVal V = state->getSVal(Ex: E, LCtx: Pred->getLocationContext());
2476 Bldr.generateNode(S, Pred,
2477 St: state->BindExpr(S, LCtx: Pred->getLocationContext(), V));
2478 Bldr.addNodes(S: Dst);
2479 break;
2480 }
2481 }
2482}
2483
2484bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
2485 const LocationContext *CalleeLC) {
2486 const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
2487 const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
2488 assert(CalleeSF && CallerSF);
2489 ExplodedNode *BeforeProcessingCall = nullptr;
2490 const Stmt *CE = CalleeSF->getCallSite();
2491
2492 // Find the first node before we started processing the call expression.
2493 while (N) {
2494 ProgramPoint L = N->getLocation();
2495 BeforeProcessingCall = N;
2496 N = N->pred_empty() ? nullptr : *(N->pred_begin());
2497
2498 // Skip the nodes corresponding to the inlined code.
2499 if (L.getStackFrame() != CallerSF)
2500 continue;
2501 // We reached the caller. Find the node right before we started
2502 // processing the call.
2503 if (L.isPurgeKind())
2504 continue;
2505 if (L.getAs<PreImplicitCall>())
2506 continue;
2507 if (L.getAs<CallEnter>())
2508 continue;
2509 if (std::optional<StmtPoint> SP = L.getAs<StmtPoint>())
2510 if (SP->getStmt() == CE)
2511 continue;
2512 break;
2513 }
2514
2515 if (!BeforeProcessingCall)
2516 return false;
2517
2518 // TODO: Clean up the unneeded nodes.
2519
2520 // Build an Epsilon node from which we will restart the analyzes.
2521 // Note that CE is permitted to be NULL!
2522 static SimpleProgramPointTag PT("ExprEngine", "Replay without inlining");
2523 ProgramPoint NewNodeLoc = EpsilonPoint(
2524 BeforeProcessingCall->getLocationContext(), CE, nullptr, &PT);
2525 // Add the special flag to GDM to signal retrying with no inlining.
2526 // Note, changing the state ensures that we are not going to cache out.
2527 ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
2528 NewNodeState =
2529 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
2530
2531 // Make the new node a successor of BeforeProcessingCall.
2532 bool IsNew = false;
2533 ExplodedNode *NewNode = G.getNode(L: NewNodeLoc, State: NewNodeState, IsSink: false, IsNew: &IsNew);
2534 // We cached out at this point. Caching out is common due to us backtracking
2535 // from the inlined function, which might spawn several paths.
2536 if (!IsNew)
2537 return true;
2538
2539 NewNode->addPredecessor(V: BeforeProcessingCall, G);
2540
2541 // Add the new node to the work list.
2542 Engine.enqueueStmtNode(N: NewNode, Block: CalleeSF->getCallSiteBlock(),
2543 Idx: CalleeSF->getIndex());
2544 NumTimesRetriedWithoutInlining++;
2545 return true;
2546}
2547
2548/// Return the innermost location context which is inlined at `Node`, unless
2549/// it's the top-level (entry point) location context.
2550static const LocationContext *getInlinedLocationContext(ExplodedNode *Node,
2551 ExplodedGraph &G) {
2552 const LocationContext *CalleeLC = Node->getLocation().getLocationContext();
2553 const LocationContext *RootLC =
2554 G.getRoot()->getLocation().getLocationContext();
2555
2556 if (CalleeLC->getStackFrame() == RootLC->getStackFrame())
2557 return nullptr;
2558
2559 return CalleeLC;
2560}
2561
2562/// Block entrance. (Update counters).
2563/// FIXME: `BlockEdge &L` is only used for debug statistics, consider removing
2564/// it and using `BlockEntrance &BE` (where `BlockEntrance` is a subtype of
2565/// `ProgramPoint`) for statistical purposes.
2566void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
2567 const BlockEntrance &BE,
2568 NodeBuilder &Builder,
2569 ExplodedNode *Pred) {
2570 // If we reach a loop which has a known bound (and meets
2571 // other constraints) then consider completely unrolling it.
2572 if(AMgr.options.ShouldUnrollLoops) {
2573 unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
2574 const Stmt *Term = Builder.getContext().getBlock()->getTerminatorStmt();
2575 if (Term) {
2576 ProgramStateRef NewState = updateLoopStack(LoopStmt: Term, ASTCtx&: AMgr.getASTContext(),
2577 Pred, maxVisitOnPath: maxBlockVisitOnPath);
2578 if (NewState != Pred->getState()) {
2579 ExplodedNode *UpdatedNode = Builder.generateNode(PP: BE, State: NewState, Pred);
2580 if (!UpdatedNode)
2581 return;
2582 Pred = UpdatedNode;
2583 }
2584 }
2585 // Is we are inside an unrolled loop then no need the check the counters.
2586 if(isUnrolledState(State: Pred->getState()))
2587 return;
2588 }
2589
2590 // If this block is terminated by a loop and it has already been visited the
2591 // maximum number of times, widen the loop.
2592 unsigned int BlockCount = Builder.getContext().blockCount();
2593 if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
2594 AMgr.options.ShouldWidenLoops) {
2595 const Stmt *Term = Builder.getContext().getBlock()->getTerminatorStmt();
2596 if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Val: Term))
2597 return;
2598
2599 // Widen.
2600 const LocationContext *LCtx = Pred->getLocationContext();
2601
2602 // FIXME:
2603 // We cannot use the CFG element from the via `ExprEngine::getCFGElementRef`
2604 // since we are currently at the block entrance and the current reference
2605 // would be stale. Ideally, we should pass on the terminator of the CFG
2606 // block, but the terminator cannot be referred as a CFG element.
2607 // Here we just pass the the first CFG element in the block.
2608 ProgramStateRef WidenedState =
2609 getWidenedLoopState(PrevState: Pred->getState(), LCtx, BlockCount,
2610 Elem: *Builder.getContext().getBlock()->ref_begin());
2611 Builder.generateNode(PP: BE, State: WidenedState, Pred);
2612 return;
2613 }
2614
2615 // FIXME: Refactor this into a checker.
2616 if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
2617 static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded");
2618 const ProgramPoint TaggedLoc = BE.withTag(tag: &Tag);
2619 const ExplodedNode *Sink =
2620 Builder.generateSink(PP: TaggedLoc, State: Pred->getState(), Pred);
2621
2622 if (const LocationContext *LC = getInlinedLocationContext(Node: Pred, G)) {
2623 // FIXME: This will unconditionally prevent inlining this function (even
2624 // from other entry points), which is not a reasonable heuristic: even if
2625 // we reached max block count on this particular execution path, there
2626 // may be other execution paths (especially with other parametrizations)
2627 // where the analyzer can reach the end of the function (so there is no
2628 // natural reason to avoid inlining it). However, disabling this would
2629 // significantly increase the analysis time (because more entry points
2630 // would exhaust their allocated budget), so it must be compensated by a
2631 // different (more reasonable) reduction of analysis scope.
2632 Engine.FunctionSummaries->markShouldNotInline(
2633 D: LC->getStackFrame()->getDecl());
2634
2635 // Re-run the call evaluation without inlining it, by storing the
2636 // no-inlining policy in the state and enqueuing the new work item on
2637 // the list. Replay should almost never fail. Use the stats to catch it
2638 // if it does.
2639 if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(N: Pred, CalleeLC: LC)))
2640 return;
2641 NumMaxBlockCountReachedInInlined++;
2642 } else
2643 NumMaxBlockCountReached++;
2644
2645 // Make sink nodes as exhausted(for stats) only if retry failed.
2646 Engine.blocksExhausted.push_back(x: std::make_pair(x: L, y&: Sink));
2647 }
2648}
2649
2650void ExprEngine::runCheckersForBlockEntrance(const NodeBuilderContext &BldCtx,
2651 const BlockEntrance &Entrance,
2652 ExplodedNode *Pred,
2653 ExplodedNodeSet &Dst) {
2654 llvm::PrettyStackTraceFormat CrashInfo(
2655 "Processing block entrance B%d -> B%d",
2656 Entrance.getPreviousBlock()->getBlockID(),
2657 Entrance.getBlock()->getBlockID());
2658 currBldrCtx = &BldCtx;
2659 getCheckerManager().runCheckersForBlockEntrance(Dst, Src: Pred, Entrance, Eng&: *this);
2660 currBldrCtx = nullptr;
2661}
2662
2663//===----------------------------------------------------------------------===//
2664// Branch processing.
2665//===----------------------------------------------------------------------===//
2666
2667/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
2668/// to try to recover some path-sensitivity for casts of symbolic
2669/// integers that promote their values (which are currently not tracked well).
2670/// This function returns the SVal bound to Condition->IgnoreCasts if all the
2671// cast(s) did was sign-extend the original value.
2672static SVal RecoverCastedSymbol(ProgramStateRef state,
2673 const Stmt *Condition,
2674 const LocationContext *LCtx,
2675 ASTContext &Ctx) {
2676
2677 const auto *Ex = dyn_cast<Expr>(Val: Condition);
2678 if (!Ex)
2679 return UnknownVal();
2680
2681 uint64_t bits = 0;
2682 bool bitsInit = false;
2683
2684 while (const auto *CE = dyn_cast<CastExpr>(Val: Ex)) {
2685 QualType T = CE->getType();
2686
2687 if (!T->isIntegralOrEnumerationType())
2688 return UnknownVal();
2689
2690 uint64_t newBits = Ctx.getTypeSize(T);
2691 if (!bitsInit || newBits < bits) {
2692 bitsInit = true;
2693 bits = newBits;
2694 }
2695
2696 Ex = CE->getSubExpr();
2697 }
2698
2699 // We reached a non-cast. Is it a symbolic value?
2700 QualType T = Ex->getType();
2701
2702 if (!bitsInit || !T->isIntegralOrEnumerationType() ||
2703 Ctx.getTypeSize(T) > bits)
2704 return UnknownVal();
2705
2706 return state->getSVal(Ex, LCtx);
2707}
2708
2709#ifndef NDEBUG
2710static const Stmt *getRightmostLeaf(const Stmt *Condition) {
2711 while (Condition) {
2712 const auto *BO = dyn_cast<BinaryOperator>(Condition);
2713 if (!BO || !BO->isLogicalOp()) {
2714 return Condition;
2715 }
2716 Condition = BO->getRHS()->IgnoreParens();
2717 }
2718 return nullptr;
2719}
2720#endif
2721
2722// Returns the condition the branch at the end of 'B' depends on and whose value
2723// has been evaluated within 'B'.
2724// In most cases, the terminator condition of 'B' will be evaluated fully in
2725// the last statement of 'B'; in those cases, the resolved condition is the
2726// given 'Condition'.
2727// If the condition of the branch is a logical binary operator tree, the CFG is
2728// optimized: in that case, we know that the expression formed by all but the
2729// rightmost leaf of the logical binary operator tree must be true, and thus
2730// the branch condition is at this point equivalent to the truth value of that
2731// rightmost leaf; the CFG block thus only evaluates this rightmost leaf
2732// expression in its final statement. As the full condition in that case was
2733// not evaluated, and is thus not in the SVal cache, we need to use that leaf
2734// expression to evaluate the truth value of the condition in the current state
2735// space.
2736static const Stmt *ResolveCondition(const Stmt *Condition,
2737 const CFGBlock *B) {
2738 if (const auto *Ex = dyn_cast<Expr>(Val: Condition))
2739 Condition = Ex->IgnoreParens();
2740
2741 const auto *BO = dyn_cast<BinaryOperator>(Val: Condition);
2742 if (!BO || !BO->isLogicalOp())
2743 return Condition;
2744
2745 assert(B->getTerminator().isStmtBranch() &&
2746 "Other kinds of branches are handled separately!");
2747
2748 // For logical operations, we still have the case where some branches
2749 // use the traditional "merge" approach and others sink the branch
2750 // directly into the basic blocks representing the logical operation.
2751 // We need to distinguish between those two cases here.
2752
2753 // The invariants are still shifting, but it is possible that the
2754 // last element in a CFGBlock is not a CFGStmt. Look for the last
2755 // CFGStmt as the value of the condition.
2756 for (CFGElement Elem : llvm::reverse(C: *B)) {
2757 std::optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
2758 if (!CS)
2759 continue;
2760 const Stmt *LastStmt = CS->getStmt();
2761 assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
2762 return LastStmt;
2763 }
2764 llvm_unreachable("could not resolve condition");
2765}
2766
2767using ObjCForLctxPair =
2768 std::pair<const ObjCForCollectionStmt *, const LocationContext *>;
2769
2770REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool)
2771
2772ProgramStateRef ExprEngine::setWhetherHasMoreIteration(
2773 ProgramStateRef State, const ObjCForCollectionStmt *O,
2774 const LocationContext *LC, bool HasMoreIteraton) {
2775 assert(!State->contains<ObjCForHasMoreIterations>({O, LC}));
2776 return State->set<ObjCForHasMoreIterations>(K: {O, LC}, E: HasMoreIteraton);
2777}
2778
2779ProgramStateRef
2780ExprEngine::removeIterationState(ProgramStateRef State,
2781 const ObjCForCollectionStmt *O,
2782 const LocationContext *LC) {
2783 assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2784 return State->remove<ObjCForHasMoreIterations>(K: {O, LC});
2785}
2786
2787bool ExprEngine::hasMoreIteration(ProgramStateRef State,
2788 const ObjCForCollectionStmt *O,
2789 const LocationContext *LC) {
2790 assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2791 return *State->get<ObjCForHasMoreIterations>(key: {O, LC});
2792}
2793
2794/// Split the state on whether there are any more iterations left for this loop.
2795/// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or std::nullopt when
2796/// the acquisition of the loop condition value failed.
2797static std::optional<std::pair<ProgramStateRef, ProgramStateRef>>
2798assumeCondition(const Stmt *Condition, ExplodedNode *N) {
2799 ProgramStateRef State = N->getState();
2800 if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Val: Condition)) {
2801 bool HasMoreIteraton =
2802 ExprEngine::hasMoreIteration(State, O: ObjCFor, LC: N->getLocationContext());
2803 // Checkers have already ran on branch conditions, so the current
2804 // information as to whether the loop has more iteration becomes outdated
2805 // after this point.
2806 State = ExprEngine::removeIterationState(State, O: ObjCFor,
2807 LC: N->getLocationContext());
2808 if (HasMoreIteraton)
2809 return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr};
2810 else
2811 return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State};
2812 }
2813 SVal X = State->getSVal(Ex: Condition, LCtx: N->getLocationContext());
2814
2815 if (X.isUnknownOrUndef()) {
2816 // Give it a chance to recover from unknown.
2817 if (const auto *Ex = dyn_cast<Expr>(Val: Condition)) {
2818 if (Ex->getType()->isIntegralOrEnumerationType()) {
2819 // Try to recover some path-sensitivity. Right now casts of symbolic
2820 // integers that promote their values are currently not tracked well.
2821 // If 'Condition' is such an expression, try and recover the
2822 // underlying value and use that instead.
2823 SVal recovered =
2824 RecoverCastedSymbol(state: State, Condition, LCtx: N->getLocationContext(),
2825 Ctx&: N->getState()->getStateManager().getContext());
2826
2827 if (!recovered.isUnknown()) {
2828 X = recovered;
2829 }
2830 }
2831 }
2832 }
2833
2834 // If the condition is still unknown, give up.
2835 if (X.isUnknownOrUndef())
2836 return std::nullopt;
2837
2838 DefinedSVal V = X.castAs<DefinedSVal>();
2839
2840 ProgramStateRef StTrue, StFalse;
2841 return State->assume(Cond: V);
2842}
2843
2844void ExprEngine::processBranch(
2845 const Stmt *Condition, NodeBuilderContext &BldCtx, ExplodedNode *Pred,
2846 ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF,
2847 std::optional<unsigned> IterationsCompletedInLoop) {
2848 assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
2849 "CXXBindTemporaryExprs are handled by processBindTemporary.");
2850 currBldrCtx = &BldCtx;
2851
2852 // Check for NULL conditions; e.g. "for(;;)"
2853 if (!Condition) {
2854 BranchNodeBuilder NullCondBldr(Dst, BldCtx, DstT, DstF);
2855 NullCondBldr.generateNode(State: Pred->getState(), branch: true, Pred);
2856 return;
2857 }
2858
2859 if (const auto *Ex = dyn_cast<Expr>(Val: Condition))
2860 Condition = Ex->IgnoreParens();
2861
2862 Condition = ResolveCondition(Condition, B: BldCtx.getBlock());
2863 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
2864 Condition->getBeginLoc(),
2865 "Error evaluating branch");
2866
2867 ExplodedNodeSet CheckersOutSet;
2868 getCheckerManager().runCheckersForBranchCondition(condition: Condition, Dst&: CheckersOutSet,
2869 Pred, Eng&: *this);
2870 // We generated only sinks.
2871 if (CheckersOutSet.empty())
2872 return;
2873
2874 BranchNodeBuilder Builder(Dst, BldCtx, DstT, DstF);
2875 for (ExplodedNode *PredN : CheckersOutSet) {
2876 ProgramStateRef PrevState = PredN->getState();
2877
2878 ProgramStateRef StTrue = PrevState, StFalse = PrevState;
2879 if (const auto KnownCondValueAssumption = assumeCondition(Condition, N: PredN))
2880 std::tie(args&: StTrue, args&: StFalse) = *KnownCondValueAssumption;
2881
2882 if (StTrue && StFalse)
2883 assert(!isa<ObjCForCollectionStmt>(Condition));
2884
2885 // We want to ensure consistent behavior between `eagerly-assume=false`,
2886 // when the state split is always performed by the `assumeCondition()`
2887 // call within this function and `eagerly-assume=true` (the default), when
2888 // some conditions (comparison operators, unary negation) can trigger a
2889 // state split before this callback. There are some contrived corner cases
2890 // that behave differently with and without `eagerly-assume`, but I don't
2891 // know about an example that could plausibly appear in "real" code.
2892 bool BothFeasible =
2893 (StTrue && StFalse) ||
2894 didEagerlyAssumeBifurcateAt(State: PrevState, Ex: dyn_cast<Expr>(Val: Condition));
2895
2896 if (StTrue) {
2897 // In a loop, if both branches are feasible (i.e. the analyzer doesn't
2898 // understand the loop condition) and two iterations have already been
2899 // completed, then don't assume a third iteration because it is a
2900 // redundant execution path (unlikely to be different from earlier loop
2901 // exits) and can cause false positives if e.g. the loop iterates over a
2902 // two-element structure with an opaque condition.
2903 //
2904 // The iteration count "2" is hardcoded because it's the natural limit:
2905 // * the fact that the programmer wrote a loop (and not just an `if`)
2906 // implies that they thought that the loop body might be executed twice;
2907 // * however, there are situations where the programmer knows that there
2908 // are at most two iterations but writes a loop that appears to be
2909 // generic, because there is no special syntax for "loop with at most
2910 // two iterations". (This pattern is common in FFMPEG and appears in
2911 // many other projects as well.)
2912 bool CompletedTwoIterations = IterationsCompletedInLoop.value_or(u: 0) >= 2;
2913 bool SkipTrueBranch = BothFeasible && CompletedTwoIterations;
2914
2915 // FIXME: This "don't assume third iteration" heuristic partially
2916 // conflicts with the widen-loop analysis option (which is off by
2917 // default). If we intend to support and stabilize the loop widening,
2918 // we must ensure that it 'plays nicely' with this logic.
2919 if (!SkipTrueBranch || AMgr.options.ShouldWidenLoops) {
2920 Builder.generateNode(State: StTrue, branch: true, Pred: PredN);
2921 } else if (!AMgr.options.InlineFunctionsWithAmbiguousLoops) {
2922 // FIXME: There is an ancient and arbitrary heuristic in
2923 // `ExprEngine::processCFGBlockEntrance` which prevents all further
2924 // inlining of a function if it finds an execution path within that
2925 // function which reaches the `MaxBlockVisitOnPath` limit (a/k/a
2926 // `analyzer-max-loop`, by default four iterations in a loop). Adding
2927 // this "don't assume third iteration" logic significantly increased
2928 // the analysis runtime on some inputs because less functions were
2929 // arbitrarily excluded from being inlined, so more entry points used
2930 // up their full allocated budget. As a hacky compensation for this,
2931 // here we apply the "should not inline" mark in cases when the loop
2932 // could potentially reach the `MaxBlockVisitOnPath` limit without the
2933 // "don't assume third iteration" logic. This slightly overcompensates
2934 // (activates if the third iteration can be entered, and will not
2935 // recognize cases where the fourth iteration would't be completed), but
2936 // should be good enough for practical purposes.
2937 if (const LocationContext *LC = getInlinedLocationContext(Node: Pred, G)) {
2938 Engine.FunctionSummaries->markShouldNotInline(
2939 D: LC->getStackFrame()->getDecl());
2940 }
2941 }
2942 }
2943
2944 if (StFalse) {
2945 // In a loop, if both branches are feasible (i.e. the analyzer doesn't
2946 // understand the loop condition), we are before the first iteration and
2947 // the analyzer option `assume-at-least-one-iteration` is set to `true`,
2948 // then avoid creating the execution path where the loop is skipped.
2949 //
2950 // In some situations this "loop is skipped" execution path is an
2951 // important corner case that may evade the notice of the developer and
2952 // hide significant bugs -- however, there are also many situations where
2953 // it's guaranteed that at least one iteration will happen (e.g. some
2954 // data structure is always nonempty), but the analyzer cannot realize
2955 // this and will produce false positives when it assumes that the loop is
2956 // skipped.
2957 bool BeforeFirstIteration = IterationsCompletedInLoop == std::optional{0};
2958 bool SkipFalseBranch = BothFeasible && BeforeFirstIteration &&
2959 AMgr.options.ShouldAssumeAtLeastOneIteration;
2960 if (!SkipFalseBranch)
2961 Builder.generateNode(State: StFalse, branch: false, Pred: PredN);
2962 }
2963 }
2964 currBldrCtx = nullptr;
2965}
2966
2967/// The GDM component containing the set of global variables which have been
2968/// previously initialized with explicit initializers.
2969REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
2970 llvm::ImmutableSet<const VarDecl *>)
2971
2972void ExprEngine::processStaticInitializer(
2973 const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred,
2974 ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) {
2975 currBldrCtx = &BuilderCtx;
2976
2977 const auto *VD = cast<VarDecl>(Val: DS->getSingleDecl());
2978 ProgramStateRef state = Pred->getState();
2979 bool initHasRun = state->contains<InitializedGlobalsSet>(key: VD);
2980 BranchNodeBuilder Builder(Dst, BuilderCtx, DstT, DstF);
2981
2982 if (!initHasRun) {
2983 state = state->add<InitializedGlobalsSet>(K: VD);
2984 }
2985
2986 Builder.generateNode(State: state, branch: initHasRun, Pred);
2987
2988 currBldrCtx = nullptr;
2989}
2990
2991/// processIndirectGoto - Called by CoreEngine. Used to generate successor
2992/// nodes by processing the 'effects' of a computed goto jump.
2993void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &Builder,
2994 ExplodedNode *Pred) {
2995 ProgramStateRef State = Pred->getState();
2996 SVal V = State->getSVal(Ex: Builder.getTarget(), LCtx: Builder.getLocationContext());
2997
2998 // Case 1: We know the computed label.
2999 if (std::optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
3000 const LabelDecl *L = LV->getLabel();
3001
3002 for (const CFGBlock *Succ : Builder) {
3003 if (cast<LabelStmt>(Val: Succ->getLabel())->getDecl() == L) {
3004 Builder.generateNode(Block: Succ, State, Pred);
3005 return;
3006 }
3007 }
3008
3009 llvm_unreachable("No block with label.");
3010 }
3011
3012 // Case 2: The label is NULL (or some other constant), or Undefined.
3013 if (isa<UndefinedVal, loc::ConcreteInt>(Val: V)) {
3014 // FIXME: Emit warnings when the jump target is undefined or numerical.
3015 return;
3016 }
3017
3018 // Case 3: We have no clue about the label. Dispatch to all targets.
3019 // FIXME: Implement dispatch for symbolic pointers.
3020 for (const CFGBlock *Succ : Builder)
3021 Builder.generateNode(Block: Succ, State, Pred);
3022}
3023
3024void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
3025 ExplodedNode *Pred,
3026 ExplodedNodeSet &Dst,
3027 const BlockEdge &L) {
3028 SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
3029 getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, Eng&: *this);
3030}
3031
3032/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
3033/// nodes when the control reaches the end of a function.
3034void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
3035 ExplodedNode *Pred,
3036 const ReturnStmt *RS) {
3037 ProgramStateRef State = Pred->getState();
3038
3039 if (!Pred->getStackFrame()->inTopFrame())
3040 State = finishArgumentConstruction(
3041 State, Call: *getStateManager().getCallEventManager().getCaller(
3042 CalleeCtx: Pred->getStackFrame(), State: Pred->getState()));
3043
3044 // FIXME: We currently cannot assert that temporaries are clear, because
3045 // lifetime extended temporaries are not always modelled correctly. In some
3046 // cases when we materialize the temporary, we do
3047 // createTemporaryRegionIfNeeded(), and the region changes, and also the
3048 // respective destructor becomes automatic from temporary. So for now clean up
3049 // the state manually before asserting. Ideally, this braced block of code
3050 // should go away.
3051 {
3052 const LocationContext *FromLC = Pred->getLocationContext();
3053 const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
3054 const LocationContext *LC = FromLC;
3055 while (LC != ToLC) {
3056 assert(LC && "ToLC must be a parent of FromLC!");
3057 for (auto I : State->get<ObjectsUnderConstruction>())
3058 if (I.first.getLocationContext() == LC) {
3059 // The comment above only pardons us for not cleaning up a
3060 // temporary destructor. If any other statements are found here,
3061 // it must be a separate problem.
3062 assert(I.first.getItem().getKind() ==
3063 ConstructionContextItem::TemporaryDestructorKind ||
3064 I.first.getItem().getKind() ==
3065 ConstructionContextItem::ElidedDestructorKind);
3066 State = State->remove<ObjectsUnderConstruction>(K: I.first);
3067 }
3068 LC = LC->getParent();
3069 }
3070 }
3071
3072 // Perform the transition with cleanups.
3073 if (State != Pred->getState()) {
3074 ExplodedNodeSet PostCleanup;
3075 NodeBuilder Bldr(Pred, PostCleanup, BC);
3076 Pred = Bldr.generateNode(PP: Pred->getLocation(), State, Pred);
3077 if (!Pred) {
3078 // The node with clean temporaries already exists. We might have reached
3079 // it on a path on which we initialize different temporaries.
3080 return;
3081 }
3082 }
3083
3084 assert(areAllObjectsFullyConstructed(Pred->getState(),
3085 Pred->getLocationContext(),
3086 Pred->getStackFrame()->getParent()));
3087 ExplodedNodeSet Dst;
3088 if (Pred->getLocationContext()->inTopFrame()) {
3089 // Remove dead symbols.
3090 ExplodedNodeSet AfterRemovedDead;
3091 removeDeadOnEndOfFunction(BC, Pred, Dst&: AfterRemovedDead);
3092
3093 // Notify checkers.
3094 for (const auto I : AfterRemovedDead)
3095 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred: I, Eng&: *this, RS);
3096 } else {
3097 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, Eng&: *this, RS);
3098 }
3099
3100 Engine.enqueueEndOfFunction(Set&: Dst, RS);
3101}
3102
3103/// ProcessSwitch - Called by CoreEngine. Used to generate successor
3104/// nodes by processing the 'effects' of a switch statement.
3105void ExprEngine::processSwitch(NodeBuilderContext &BC, const SwitchStmt *Switch,
3106 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
3107 currBldrCtx = &BC;
3108 const Expr *Condition = Switch->getCond();
3109
3110 SwitchNodeBuilder Builder(Dst, BC);
3111 ExplodedNodeSet CheckersOutSet;
3112
3113 getCheckerManager().runCheckersForBranchCondition(
3114 condition: Condition->IgnoreParens(), Dst&: CheckersOutSet, Pred, Eng&: *this);
3115
3116 for (ExplodedNode *Node : CheckersOutSet) {
3117 ProgramStateRef State = Node->getState();
3118
3119 SVal CondV = State->getSVal(Ex: Condition, LCtx: Node->getLocationContext());
3120 if (CondV.isUndef()) {
3121 // This can only happen if core.uninitialized.Branch is disabled.
3122 continue;
3123 }
3124
3125 std::optional<NonLoc> CondNL = CondV.getAs<NonLoc>();
3126
3127 for (const CFGBlock *Block : Builder) {
3128 // Successor may be pruned out during CFG construction.
3129 if (!Block)
3130 continue;
3131
3132 const CaseStmt *Case = cast<CaseStmt>(Val: Block->getLabel());
3133
3134 // Evaluate the LHS of the case value.
3135 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(Ctx: getContext());
3136 assert(V1.getBitWidth() ==
3137 getContext().getIntWidth(Condition->getType()));
3138
3139 // Get the RHS of the case, if it exists.
3140 llvm::APSInt V2;
3141 if (const Expr *E = Case->getRHS())
3142 V2 = E->EvaluateKnownConstInt(Ctx: getContext());
3143 else
3144 V2 = V1;
3145
3146 ProgramStateRef StateMatching;
3147 if (CondNL) {
3148 // Split the state: this "case:" matches / does not match.
3149 std::tie(args&: StateMatching, args&: State) =
3150 State->assumeInclusiveRange(Val: *CondNL, From: V1, To: V2);
3151 } else {
3152 // The switch condition is UnknownVal, so we enter each "case:" without
3153 // any state update.
3154 StateMatching = State;
3155 }
3156
3157 if (StateMatching)
3158 Builder.generateCaseStmtNode(Block, State: StateMatching, Pred: Node);
3159
3160 // If _not_ entering the current case is infeasible, then we are done
3161 // with processing the paths through the current Node.
3162 if (!State)
3163 break;
3164 }
3165 if (!State)
3166 continue;
3167
3168 // If we have switch(enum value), the default branch is not
3169 // feasible if all of the enum constants not covered by 'case:' statements
3170 // are not feasible values for the switch condition.
3171 //
3172 // Note that this isn't as accurate as it could be. Even if there isn't
3173 // a case for a particular enum value as long as that enum value isn't
3174 // feasible then it shouldn't be considered for making 'default:' reachable.
3175 if (Condition->IgnoreParenImpCasts()->getType()->isEnumeralType()) {
3176 if (Switch->isAllEnumCasesCovered())
3177 continue;
3178 }
3179
3180 Builder.generateDefaultCaseNode(State, Pred: Node);
3181 }
3182
3183 currBldrCtx = nullptr;
3184}
3185
3186//===----------------------------------------------------------------------===//
3187// Transfer functions: Loads and stores.
3188//===----------------------------------------------------------------------===//
3189
3190void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
3191 ExplodedNode *Pred,
3192 ExplodedNodeSet &Dst) {
3193 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3194
3195 ProgramStateRef state = Pred->getState();
3196 const LocationContext *LCtx = Pred->getLocationContext();
3197
3198 auto resolveAsLambdaCapturedVar =
3199 [&](const ValueDecl *VD) -> std::optional<std::pair<SVal, QualType>> {
3200 const auto *MD = dyn_cast<CXXMethodDecl>(Val: LCtx->getDecl());
3201 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Val: Ex);
3202 if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
3203 DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
3204 MD->getParent()->isLambda()) {
3205 // Lookup the field of the lambda.
3206 const CXXRecordDecl *CXXRec = MD->getParent();
3207 llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;
3208 FieldDecl *LambdaThisCaptureField;
3209 CXXRec->getCaptureFields(Captures&: LambdaCaptureFields, ThisCapture&: LambdaThisCaptureField);
3210
3211 // Sema follows a sequence of complex rules to determine whether the
3212 // variable should be captured.
3213 if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
3214 Loc CXXThis = svalBuilder.getCXXThis(D: MD, SFC: LCtx->getStackFrame());
3215 SVal CXXThisVal = state->getSVal(LV: CXXThis);
3216 return std::make_pair(x: state->getLValue(decl: FD, Base: CXXThisVal), y: FD->getType());
3217 }
3218 }
3219
3220 return std::nullopt;
3221 };
3222
3223 if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
3224 // C permits "extern void v", and if you cast the address to a valid type,
3225 // you can even do things with it. We simply pretend
3226 assert(Ex->isGLValue() || VD->getType()->isVoidType());
3227 const LocationContext *LocCtxt = Pred->getLocationContext();
3228 std::optional<std::pair<SVal, QualType>> VInfo =
3229 resolveAsLambdaCapturedVar(VD);
3230
3231 if (!VInfo)
3232 VInfo = std::make_pair(x: state->getLValue(VD, LC: LocCtxt), y: VD->getType());
3233
3234 SVal V = VInfo->first;
3235 bool IsReference = VInfo->second->isReferenceType();
3236
3237 // For references, the 'lvalue' is the pointer address stored in the
3238 // reference region.
3239 if (IsReference) {
3240 if (const MemRegion *R = V.getAsRegion())
3241 V = state->getSVal(R);
3242 else
3243 V = UnknownVal();
3244 }
3245
3246 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V), tag: nullptr,
3247 K: ProgramPoint::PostLValueKind);
3248 return;
3249 }
3250 if (const auto *ED = dyn_cast<EnumConstantDecl>(Val: D)) {
3251 assert(!Ex->isGLValue());
3252 SVal V = svalBuilder.makeIntVal(integer: ED->getInitVal());
3253 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V));
3254 return;
3255 }
3256 if (const auto *FD = dyn_cast<FunctionDecl>(Val: D)) {
3257 SVal V = svalBuilder.getFunctionPointer(func: FD);
3258 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V), tag: nullptr,
3259 K: ProgramPoint::PostLValueKind);
3260 return;
3261 }
3262 if (isa<FieldDecl, IndirectFieldDecl>(Val: D)) {
3263 // Delegate all work related to pointer to members to the surrounding
3264 // operator&.
3265 return;
3266 }
3267 if (const auto *BD = dyn_cast<BindingDecl>(Val: D)) {
3268 // Handle structured bindings captured by lambda.
3269 if (std::optional<std::pair<SVal, QualType>> VInfo =
3270 resolveAsLambdaCapturedVar(BD)) {
3271 auto [V, T] = VInfo.value();
3272
3273 if (T->isReferenceType()) {
3274 if (const MemRegion *R = V.getAsRegion())
3275 V = state->getSVal(R);
3276 else
3277 V = UnknownVal();
3278 }
3279
3280 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V), tag: nullptr,
3281 K: ProgramPoint::PostLValueKind);
3282 return;
3283 }
3284
3285 const auto *DD = cast<DecompositionDecl>(Val: BD->getDecomposedDecl());
3286
3287 SVal Base = state->getLValue(VD: DD, LC: LCtx);
3288 if (DD->getType()->isReferenceType()) {
3289 if (const MemRegion *R = Base.getAsRegion())
3290 Base = state->getSVal(R);
3291 else
3292 Base = UnknownVal();
3293 }
3294
3295 SVal V = UnknownVal();
3296
3297 // Handle binding to data members
3298 if (const auto *ME = dyn_cast<MemberExpr>(Val: BD->getBinding())) {
3299 const auto *Field = cast<FieldDecl>(Val: ME->getMemberDecl());
3300 V = state->getLValue(decl: Field, Base);
3301 }
3302 // Handle binding to arrays
3303 else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(Val: BD->getBinding())) {
3304 SVal Idx = state->getSVal(Ex: ASE->getIdx(), LCtx);
3305
3306 // Note: the index of an element in a structured binding is automatically
3307 // created and it is a unique identifier of the specific element. Thus it
3308 // cannot be a value that varies at runtime.
3309 assert(Idx.isConstant() && "BindingDecl array index is not a constant!");
3310
3311 V = state->getLValue(ElementType: BD->getType(), Idx, Base);
3312 }
3313 // Handle binding to tuple-like structures
3314 else if (const auto *HV = BD->getHoldingVar()) {
3315 V = state->getLValue(VD: HV, LC: LCtx);
3316
3317 if (HV->getType()->isReferenceType()) {
3318 if (const MemRegion *R = V.getAsRegion())
3319 V = state->getSVal(R);
3320 else
3321 V = UnknownVal();
3322 }
3323 } else
3324 llvm_unreachable("An unknown case of structured binding encountered!");
3325
3326 // In case of tuple-like types the references are already handled, so we
3327 // don't want to handle them again.
3328 if (BD->getType()->isReferenceType() && !BD->getHoldingVar()) {
3329 if (const MemRegion *R = V.getAsRegion())
3330 V = state->getSVal(R);
3331 else
3332 V = UnknownVal();
3333 }
3334
3335 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V), tag: nullptr,
3336 K: ProgramPoint::PostLValueKind);
3337
3338 return;
3339 }
3340
3341 if (const auto *TPO = dyn_cast<TemplateParamObjectDecl>(Val: D)) {
3342 // FIXME: We should meaningfully implement this.
3343 (void)TPO;
3344 return;
3345 }
3346
3347 llvm_unreachable("Support for this Decl not implemented.");
3348}
3349
3350/// VisitArrayInitLoopExpr - Transfer function for array init loop.
3351void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex,
3352 ExplodedNode *Pred,
3353 ExplodedNodeSet &Dst) {
3354 ExplodedNodeSet CheckerPreStmt;
3355 getCheckerManager().runCheckersForPreStmt(Dst&: CheckerPreStmt, Src: Pred, S: Ex, Eng&: *this);
3356
3357 ExplodedNodeSet EvalSet;
3358 NodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
3359
3360 const Expr *Arr = Ex->getCommonExpr()->getSourceExpr();
3361
3362 for (auto *Node : CheckerPreStmt) {
3363
3364 // The constructor visitior has already taken care of everything.
3365 if (isa<CXXConstructExpr>(Val: Ex->getSubExpr()))
3366 break;
3367
3368 const LocationContext *LCtx = Node->getLocationContext();
3369 ProgramStateRef state = Node->getState();
3370
3371 SVal Base = UnknownVal();
3372
3373 // As in case of this expression the sub-expressions are not visited by any
3374 // other transfer functions, they are handled by matching their AST.
3375
3376 // Case of implicit copy or move ctor of object with array member
3377 //
3378 // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the
3379 // environment.
3380 //
3381 // struct S {
3382 // int arr[2];
3383 // };
3384 //
3385 //
3386 // S a;
3387 // S b = a;
3388 //
3389 // The AST in case of a *copy constructor* looks like this:
3390 // ArrayInitLoopExpr
3391 // |-OpaqueValueExpr
3392 // | `-MemberExpr <-- match this
3393 // | `-DeclRefExpr
3394 // ` ...
3395 //
3396 //
3397 // S c;
3398 // S d = std::move(d);
3399 //
3400 // In case of a *move constructor* the resulting AST looks like:
3401 // ArrayInitLoopExpr
3402 // |-OpaqueValueExpr
3403 // | `-MemberExpr <-- match this first
3404 // | `-CXXStaticCastExpr <-- match this after
3405 // | `-DeclRefExpr
3406 // ` ...
3407 if (const auto *ME = dyn_cast<MemberExpr>(Val: Arr)) {
3408 Expr *MEBase = ME->getBase();
3409
3410 // Move ctor
3411 if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(Val: MEBase)) {
3412 MEBase = CXXSCE->getSubExpr();
3413 }
3414
3415 auto ObjDeclExpr = cast<DeclRefExpr>(Val: MEBase);
3416 SVal Obj = state->getLValue(VD: cast<VarDecl>(Val: ObjDeclExpr->getDecl()), LC: LCtx);
3417
3418 Base = state->getLValue(decl: cast<FieldDecl>(Val: ME->getMemberDecl()), Base: Obj);
3419 }
3420
3421 // Case of lambda capture and decomposition declaration
3422 //
3423 // int arr[2];
3424 //
3425 // [arr]{ int a = arr[0]; }();
3426 // auto[a, b] = arr;
3427 //
3428 // In both of these cases the AST looks like the following:
3429 // ArrayInitLoopExpr
3430 // |-OpaqueValueExpr
3431 // | `-DeclRefExpr <-- match this
3432 // ` ...
3433 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Val: Arr))
3434 Base = state->getLValue(VD: cast<VarDecl>(Val: DRE->getDecl()), LC: LCtx);
3435
3436 // Create a lazy compound value to the original array
3437 if (const MemRegion *R = Base.getAsRegion())
3438 Base = state->getSVal(R);
3439 else
3440 Base = UnknownVal();
3441
3442 Bldr.generateNode(S: Ex, Pred, St: state->BindExpr(S: Ex, LCtx, V: Base));
3443 }
3444
3445 getCheckerManager().runCheckersForPostStmt(Dst, Src: EvalSet, S: Ex, Eng&: *this);
3446}
3447
3448/// VisitArraySubscriptExpr - Transfer function for array accesses
3449void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
3450 ExplodedNode *Pred,
3451 ExplodedNodeSet &Dst){
3452 const Expr *Base = A->getBase()->IgnoreParens();
3453 const Expr *Idx = A->getIdx()->IgnoreParens();
3454
3455 ExplodedNodeSet CheckerPreStmt;
3456 getCheckerManager().runCheckersForPreStmt(Dst&: CheckerPreStmt, Src: Pred, S: A, Eng&: *this);
3457
3458 ExplodedNodeSet EvalSet;
3459 NodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
3460
3461 bool IsVectorType = A->getBase()->getType()->isVectorType();
3462
3463 // The "like" case is for situations where C standard prohibits the type to
3464 // be an lvalue, e.g. taking the address of a subscript of an expression of
3465 // type "void *".
3466 bool IsGLValueLike = A->isGLValue() ||
3467 (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
3468
3469 for (auto *Node : CheckerPreStmt) {
3470 const LocationContext *LCtx = Node->getLocationContext();
3471 ProgramStateRef state = Node->getState();
3472
3473 if (IsGLValueLike) {
3474 QualType T = A->getType();
3475
3476 // One of the forbidden LValue types! We still need to have sensible
3477 // symbolic locations to represent this stuff. Note that arithmetic on
3478 // void pointers is a GCC extension.
3479 if (T->isVoidType())
3480 T = getContext().CharTy;
3481
3482 SVal V = state->getLValue(ElementType: T,
3483 Idx: state->getSVal(Ex: Idx, LCtx),
3484 Base: state->getSVal(Ex: Base, LCtx));
3485 Bldr.generateNode(S: A, Pred: Node, St: state->BindExpr(S: A, LCtx, V), tag: nullptr,
3486 K: ProgramPoint::PostLValueKind);
3487 } else if (IsVectorType) {
3488 // FIXME: non-glvalue vector reads are not modelled.
3489 Bldr.generateNode(S: A, Pred: Node, St: state, tag: nullptr);
3490 } else {
3491 llvm_unreachable("Array subscript should be an lValue when not \
3492a vector and not a forbidden lvalue type");
3493 }
3494 }
3495
3496 getCheckerManager().runCheckersForPostStmt(Dst, Src: EvalSet, S: A, Eng&: *this);
3497}
3498
3499/// VisitMemberExpr - Transfer function for member expressions.
3500void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
3501 ExplodedNodeSet &Dst) {
3502 // FIXME: Prechecks eventually go in ::Visit().
3503 ExplodedNodeSet CheckedSet;
3504 getCheckerManager().runCheckersForPreStmt(Dst&: CheckedSet, Src: Pred, S: M, Eng&: *this);
3505
3506 ExplodedNodeSet EvalSet;
3507 ValueDecl *Member = M->getMemberDecl();
3508
3509 // Handle static member variables and enum constants accessed via
3510 // member syntax.
3511 if (isa<VarDecl, EnumConstantDecl>(Val: Member)) {
3512 for (const auto I : CheckedSet)
3513 VisitCommonDeclRefExpr(Ex: M, D: Member, Pred: I, Dst&: EvalSet);
3514 } else {
3515 NodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
3516 ExplodedNodeSet Tmp;
3517
3518 for (const auto I : CheckedSet) {
3519 ProgramStateRef state = I->getState();
3520 const LocationContext *LCtx = I->getLocationContext();
3521 Expr *BaseExpr = M->getBase();
3522
3523 // Handle C++ method calls.
3524 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: Member)) {
3525 if (MD->isImplicitObjectMemberFunction())
3526 state = createTemporaryRegionIfNeeded(State: state, LC: LCtx, InitWithAdjustments: BaseExpr);
3527
3528 SVal MDVal = svalBuilder.getFunctionPointer(func: MD);
3529 state = state->BindExpr(S: M, LCtx, V: MDVal);
3530
3531 Bldr.generateNode(S: M, Pred: I, St: state);
3532 continue;
3533 }
3534
3535 // Handle regular struct fields / member variables.
3536 const SubRegion *MR = nullptr;
3537 state = createTemporaryRegionIfNeeded(State: state, LC: LCtx, InitWithAdjustments: BaseExpr,
3538 /*Result=*/nullptr,
3539 /*OutRegionWithAdjustments=*/&MR);
3540 SVal baseExprVal =
3541 MR ? loc::MemRegionVal(MR) : state->getSVal(Ex: BaseExpr, LCtx);
3542
3543 // FIXME: Copied from RegionStoreManager::bind()
3544 if (const auto *SR =
3545 dyn_cast_or_null<SymbolicRegion>(Val: baseExprVal.getAsRegion())) {
3546 QualType T = SR->getPointeeStaticType();
3547 baseExprVal =
3548 loc::MemRegionVal(getStoreManager().GetElementZeroRegion(R: SR, T));
3549 }
3550
3551 const auto *field = cast<FieldDecl>(Val: Member);
3552 SVal L = state->getLValue(decl: field, Base: baseExprVal);
3553
3554 if (M->isGLValue() || M->getType()->isArrayType()) {
3555 // We special-case rvalues of array type because the analyzer cannot
3556 // reason about them, since we expect all regions to be wrapped in Locs.
3557 // We instead treat these as lvalues and assume that they will decay to
3558 // pointers as soon as they are used.
3559 if (!M->isGLValue()) {
3560 assert(M->getType()->isArrayType());
3561 const auto *PE =
3562 dyn_cast<ImplicitCastExpr>(Val: I->getParentMap().getParentIgnoreParens(S: M));
3563 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
3564 llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
3565 }
3566 }
3567
3568 if (field->getType()->isReferenceType()) {
3569 if (const MemRegion *R = L.getAsRegion())
3570 L = state->getSVal(R);
3571 else
3572 L = UnknownVal();
3573 }
3574
3575 Bldr.generateNode(S: M, Pred: I, St: state->BindExpr(S: M, LCtx, V: L), tag: nullptr,
3576 K: ProgramPoint::PostLValueKind);
3577 } else {
3578 Bldr.takeNodes(N: I);
3579 evalLoad(Dst&: Tmp, NodeEx: M, BoundExpr: M, Pred: I, St: state, location: L);
3580 Bldr.addNodes(S: Tmp);
3581 }
3582 }
3583 }
3584
3585 getCheckerManager().runCheckersForPostStmt(Dst, Src: EvalSet, S: M, Eng&: *this);
3586}
3587
3588void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
3589 ExplodedNodeSet &Dst) {
3590 ExplodedNodeSet AfterPreSet;
3591 getCheckerManager().runCheckersForPreStmt(Dst&: AfterPreSet, Src: Pred, S: AE, Eng&: *this);
3592
3593 // For now, treat all the arguments to C11 atomics as escaping.
3594 // FIXME: Ideally we should model the behavior of the atomics precisely here.
3595
3596 ExplodedNodeSet AfterInvalidateSet;
3597 NodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
3598
3599 for (const auto I : AfterPreSet) {
3600 ProgramStateRef State = I->getState();
3601 const LocationContext *LCtx = I->getLocationContext();
3602
3603 SmallVector<SVal, 8> ValuesToInvalidate;
3604 for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
3605 const Expr *SubExpr = AE->getSubExprs()[SI];
3606 SVal SubExprVal = State->getSVal(Ex: SubExpr, LCtx);
3607 ValuesToInvalidate.push_back(Elt: SubExprVal);
3608 }
3609
3610 State = State->invalidateRegions(Values: ValuesToInvalidate, Elem: getCFGElementRef(),
3611 BlockCount: currBldrCtx->blockCount(), LCtx,
3612 /*CausedByPointerEscape*/ CausesPointerEscape: true,
3613 /*Symbols=*/IS: nullptr);
3614
3615 SVal ResultVal = UnknownVal();
3616 State = State->BindExpr(S: AE, LCtx, V: ResultVal);
3617 Bldr.generateNode(S: AE, Pred: I, St: State, tag: nullptr,
3618 K: ProgramPoint::PostStmtKind);
3619 }
3620
3621 getCheckerManager().runCheckersForPostStmt(Dst, Src: AfterInvalidateSet, S: AE, Eng&: *this);
3622}
3623
3624// A value escapes in four possible cases:
3625// (1) We are binding to something that is not a memory region.
3626// (2) We are binding to a MemRegion that does not have stack storage.
3627// (3) We are binding to a top-level parameter region with a non-trivial
3628// destructor. We won't see the destructor during analysis, but it's there.
3629// (4) We are binding to a MemRegion with stack storage that the store
3630// does not understand.
3631ProgramStateRef ExprEngine::processPointerEscapedOnBind(
3632 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
3633 const LocationContext *LCtx, PointerEscapeKind Kind,
3634 const CallEvent *Call) {
3635 SmallVector<SVal, 8> Escaped;
3636 for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
3637 // Cases (1) and (2).
3638 const MemRegion *MR = LocAndVal.first.getAsRegion();
3639 const MemSpaceRegion *Space = MR ? MR->getMemorySpace(State) : nullptr;
3640 if (!MR || !isa<StackSpaceRegion, StaticGlobalSpaceRegion>(Val: Space)) {
3641 Escaped.push_back(Elt: LocAndVal.second);
3642 continue;
3643 }
3644
3645 // Case (3).
3646 if (const auto *VR = dyn_cast<VarRegion>(Val: MR->getBaseRegion()))
3647 if (isa<StackArgumentsSpaceRegion>(Val: Space) &&
3648 VR->getStackFrame()->inTopFrame())
3649 if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
3650 if (!RD->hasTrivialDestructor()) {
3651 Escaped.push_back(Elt: LocAndVal.second);
3652 continue;
3653 }
3654
3655 // Case (4): in order to test that, generate a new state with the binding
3656 // added. If it is the same state, then it escapes (since the store cannot
3657 // represent the binding).
3658 // Do this only if we know that the store is not supposed to generate the
3659 // same state.
3660 SVal StoredVal = State->getSVal(R: MR);
3661 if (StoredVal != LocAndVal.second)
3662 if (State ==
3663 (State->bindLoc(location: loc::MemRegionVal(MR), V: LocAndVal.second, LCtx)))
3664 Escaped.push_back(Elt: LocAndVal.second);
3665 }
3666
3667 if (Escaped.empty())
3668 return State;
3669
3670 return escapeValues(State, Vs: Escaped, K: Kind, Call);
3671}
3672
3673ProgramStateRef
3674ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
3675 SVal Val, const LocationContext *LCtx) {
3676 std::pair<SVal, SVal> LocAndVal(Loc, Val);
3677 return processPointerEscapedOnBind(State, LocAndVals: LocAndVal, LCtx, Kind: PSK_EscapeOnBind,
3678 Call: nullptr);
3679}
3680
3681ProgramStateRef
3682ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
3683 const InvalidatedSymbols *Invalidated,
3684 ArrayRef<const MemRegion *> ExplicitRegions,
3685 const CallEvent *Call,
3686 RegionAndSymbolInvalidationTraits &ITraits) {
3687 if (!Invalidated || Invalidated->empty())
3688 return State;
3689
3690 if (!Call)
3691 return getCheckerManager().runCheckersForPointerEscape(State,
3692 Escaped: *Invalidated,
3693 Call: nullptr,
3694 Kind: PSK_EscapeOther,
3695 ITraits: &ITraits);
3696
3697 // If the symbols were invalidated by a call, we want to find out which ones
3698 // were invalidated directly due to being arguments to the call.
3699 InvalidatedSymbols SymbolsDirectlyInvalidated;
3700 for (const auto I : ExplicitRegions) {
3701 if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
3702 SymbolsDirectlyInvalidated.insert(V: R->getSymbol());
3703 }
3704
3705 InvalidatedSymbols SymbolsIndirectlyInvalidated;
3706 for (const auto &sym : *Invalidated) {
3707 if (SymbolsDirectlyInvalidated.count(V: sym))
3708 continue;
3709 SymbolsIndirectlyInvalidated.insert(V: sym);
3710 }
3711
3712 if (!SymbolsDirectlyInvalidated.empty())
3713 State = getCheckerManager().runCheckersForPointerEscape(State,
3714 Escaped: SymbolsDirectlyInvalidated, Call, Kind: PSK_DirectEscapeOnCall, ITraits: &ITraits);
3715
3716 // Notify about the symbols that get indirectly invalidated by the call.
3717 if (!SymbolsIndirectlyInvalidated.empty())
3718 State = getCheckerManager().runCheckersForPointerEscape(State,
3719 Escaped: SymbolsIndirectlyInvalidated, Call, Kind: PSK_IndirectEscapeOnCall, ITraits: &ITraits);
3720
3721 return State;
3722}
3723
3724/// evalBind - Handle the semantics of binding a value to a specific location.
3725/// This method is used by evalStore and (soon) VisitDeclStmt, and others.
3726void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
3727 ExplodedNode *Pred, SVal location, SVal Val,
3728 bool AtDeclInit, const ProgramPoint *PP) {
3729 const LocationContext *LC = Pred->getLocationContext();
3730 PostStmt PS(StoreE, LC);
3731 if (!PP)
3732 PP = &PS;
3733
3734 // Do a previsit of the bind.
3735 ExplodedNodeSet CheckedSet;
3736 getCheckerManager().runCheckersForBind(Dst&: CheckedSet, Src: Pred, location, val: Val,
3737 S: StoreE, AtDeclInit, Eng&: *this, PP: *PP);
3738
3739 NodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
3740
3741 // If the location is not a 'Loc', it will already be handled by
3742 // the checkers. There is nothing left to do.
3743 if (!isa<Loc>(Val: location)) {
3744 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
3745 /*tag*/nullptr);
3746 ProgramStateRef state = Pred->getState();
3747 state = processPointerEscapedOnBind(State: state, Loc: location, Val, LCtx: LC);
3748 Bldr.generateNode(PP: L, State: state, Pred);
3749 return;
3750 }
3751
3752 for (const auto PredI : CheckedSet) {
3753 ProgramStateRef state = PredI->getState();
3754
3755 state = processPointerEscapedOnBind(State: state, Loc: location, Val, LCtx: LC);
3756
3757 // When binding the value, pass on the hint that this is a initialization.
3758 // For initializations, we do not need to inform clients of region
3759 // changes.
3760 state = state->bindLoc(location: location.castAs<Loc>(), V: Val, LCtx: LC,
3761 /* notifyChanges = */ !AtDeclInit);
3762
3763 const MemRegion *LocReg = nullptr;
3764 if (std::optional<loc::MemRegionVal> LocRegVal =
3765 location.getAs<loc::MemRegionVal>()) {
3766 LocReg = LocRegVal->getRegion();
3767 }
3768
3769 const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
3770 Bldr.generateNode(PP: L, State: state, Pred: PredI);
3771 }
3772}
3773
3774/// evalStore - Handle the semantics of a store via an assignment.
3775/// @param Dst The node set to store generated state nodes
3776/// @param AssignE The assignment expression if the store happens in an
3777/// assignment.
3778/// @param LocationE The location expression that is stored to.
3779/// @param state The current simulation state
3780/// @param location The location to store the value
3781/// @param Val The value to be stored
3782void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
3783 const Expr *LocationE,
3784 ExplodedNode *Pred,
3785 ProgramStateRef state, SVal location, SVal Val,
3786 const ProgramPointTag *tag) {
3787 // Proceed with the store. We use AssignE as the anchor for the PostStore
3788 // ProgramPoint if it is non-NULL, and LocationE otherwise.
3789 const Expr *StoreE = AssignE ? AssignE : LocationE;
3790
3791 // Evaluate the location (checks for bad dereferences).
3792 ExplodedNodeSet Tmp;
3793 evalLocation(Dst&: Tmp, NodeEx: AssignE, BoundEx: LocationE, Pred, St: state, location, isLoad: false);
3794
3795 if (Tmp.empty())
3796 return;
3797
3798 if (location.isUndef())
3799 return;
3800
3801 for (const auto I : Tmp)
3802 evalBind(Dst, StoreE, Pred: I, location, Val, AtDeclInit: false);
3803}
3804
3805void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
3806 const Expr *NodeEx,
3807 const Expr *BoundEx,
3808 ExplodedNode *Pred,
3809 ProgramStateRef state,
3810 SVal location,
3811 const ProgramPointTag *tag,
3812 QualType LoadTy) {
3813 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
3814 assert(NodeEx);
3815 assert(BoundEx);
3816 // Evaluate the location (checks for bad dereferences).
3817 ExplodedNodeSet Tmp;
3818 evalLocation(Dst&: Tmp, NodeEx, BoundEx, Pred, St: state, location, isLoad: true);
3819 if (Tmp.empty())
3820 return;
3821
3822 NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
3823 if (location.isUndef())
3824 return;
3825
3826 // Proceed with the load.
3827 for (const auto I : Tmp) {
3828 state = I->getState();
3829 const LocationContext *LCtx = I->getLocationContext();
3830
3831 SVal V = UnknownVal();
3832 if (location.isValid()) {
3833 if (LoadTy.isNull())
3834 LoadTy = BoundEx->getType();
3835 V = state->getSVal(LV: location.castAs<Loc>(), T: LoadTy);
3836 }
3837
3838 Bldr.generateNode(S: NodeEx, Pred: I, St: state->BindExpr(S: BoundEx, LCtx, V), tag,
3839 K: ProgramPoint::PostLoadKind);
3840 }
3841}
3842
3843void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
3844 const Stmt *NodeEx,
3845 const Stmt *BoundEx,
3846 ExplodedNode *Pred,
3847 ProgramStateRef state,
3848 SVal location,
3849 bool isLoad) {
3850 NodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
3851 // Early checks for performance reason.
3852 if (location.isUnknown()) {
3853 return;
3854 }
3855
3856 ExplodedNodeSet Src;
3857 BldrTop.takeNodes(N: Pred);
3858 NodeBuilder Bldr(Pred, Src, *currBldrCtx);
3859 if (Pred->getState() != state) {
3860 // Associate this new state with an ExplodedNode.
3861 // FIXME: If I pass null tag, the graph is incorrect, e.g for
3862 // int *p;
3863 // p = 0;
3864 // *p = 0xDEADBEEF;
3865 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
3866 // instead "int *p" is noted as
3867 // "Variable 'p' initialized to a null pointer value"
3868
3869 static SimpleProgramPointTag tag(TagProviderName, "Location");
3870 Bldr.generateNode(S: NodeEx, Pred, St: state, tag: &tag);
3871 }
3872 ExplodedNodeSet Tmp;
3873 getCheckerManager().runCheckersForLocation(Dst&: Tmp, Src, location, isLoad,
3874 NodeEx, BoundEx, Eng&: *this);
3875 BldrTop.addNodes(S: Tmp);
3876}
3877
3878std::pair<const ProgramPointTag *, const ProgramPointTag *>
3879ExprEngine::getEagerlyAssumeBifurcationTags() {
3880 static SimpleProgramPointTag TrueTag(TagProviderName, "Eagerly Assume True"),
3881 FalseTag(TagProviderName, "Eagerly Assume False");
3882
3883 return std::make_pair(x: &TrueTag, y: &FalseTag);
3884}
3885
3886/// If the last EagerlyAssume attempt was successful (i.e. the true and false
3887/// cases were both feasible), this state trait stores the expression where it
3888/// happened; otherwise this holds nullptr.
3889REGISTER_TRAIT_WITH_PROGRAMSTATE(LastEagerlyAssumeExprIfSuccessful,
3890 const Expr *)
3891
3892void ExprEngine::evalEagerlyAssumeBifurcation(ExplodedNodeSet &Dst,
3893 ExplodedNodeSet &Src,
3894 const Expr *Ex) {
3895 NodeBuilder Bldr(Src, Dst, *currBldrCtx);
3896
3897 for (ExplodedNode *Pred : Src) {
3898 // Test if the previous node was as the same expression. This can happen
3899 // when the expression fails to evaluate to anything meaningful and
3900 // (as an optimization) we don't generate a node.
3901 ProgramPoint P = Pred->getLocation();
3902 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
3903 continue;
3904 }
3905
3906 ProgramStateRef State = Pred->getState();
3907 State = State->set<LastEagerlyAssumeExprIfSuccessful>(nullptr);
3908 SVal V = State->getSVal(Ex, LCtx: Pred->getLocationContext());
3909 std::optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
3910 if (SEV && SEV->isExpression()) {
3911 const auto &[TrueTag, FalseTag] = getEagerlyAssumeBifurcationTags();
3912
3913 auto [StateTrue, StateFalse] = State->assume(Cond: *SEV);
3914
3915 if (StateTrue && StateFalse) {
3916 StateTrue = StateTrue->set<LastEagerlyAssumeExprIfSuccessful>(Ex);
3917 StateFalse = StateFalse->set<LastEagerlyAssumeExprIfSuccessful>(Ex);
3918 }
3919
3920 // First assume that the condition is true.
3921 if (StateTrue) {
3922 SVal Val = svalBuilder.makeIntVal(integer: 1U, type: Ex->getType());
3923 StateTrue = StateTrue->BindExpr(S: Ex, LCtx: Pred->getLocationContext(), V: Val);
3924 Bldr.generateNode(S: Ex, Pred, St: StateTrue, tag: TrueTag);
3925 }
3926
3927 // Next, assume that the condition is false.
3928 if (StateFalse) {
3929 SVal Val = svalBuilder.makeIntVal(integer: 0U, type: Ex->getType());
3930 StateFalse = StateFalse->BindExpr(S: Ex, LCtx: Pred->getLocationContext(), V: Val);
3931 Bldr.generateNode(S: Ex, Pred, St: StateFalse, tag: FalseTag);
3932 }
3933 }
3934 }
3935}
3936
3937bool ExprEngine::didEagerlyAssumeBifurcateAt(ProgramStateRef State,
3938 const Expr *Ex) const {
3939 return Ex && State->get<LastEagerlyAssumeExprIfSuccessful>() == Ex;
3940}
3941
3942void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
3943 ExplodedNodeSet &Dst) {
3944 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3945 // We have processed both the inputs and the outputs. All of the outputs
3946 // should evaluate to Locs. Nuke all of their values.
3947
3948 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3949 // which interprets the inline asm and stores proper results in the
3950 // outputs.
3951
3952 ProgramStateRef state = Pred->getState();
3953
3954 for (const Expr *O : A->outputs()) {
3955 SVal X = state->getSVal(Ex: O, LCtx: Pred->getLocationContext());
3956 assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
3957
3958 if (std::optional<Loc> LV = X.getAs<Loc>())
3959 state = state->invalidateRegions(Values: *LV, Elem: getCFGElementRef(),
3960 BlockCount: currBldrCtx->blockCount(),
3961 LCtx: Pred->getLocationContext(),
3962 /*CausedByPointerEscape=*/CausesPointerEscape: true);
3963 }
3964
3965 // Do not reason about locations passed inside inline assembly.
3966 for (const Expr *I : A->inputs()) {
3967 SVal X = state->getSVal(Ex: I, LCtx: Pred->getLocationContext());
3968
3969 if (std::optional<Loc> LV = X.getAs<Loc>())
3970 state = state->invalidateRegions(Values: *LV, Elem: getCFGElementRef(),
3971 BlockCount: currBldrCtx->blockCount(),
3972 LCtx: Pred->getLocationContext(),
3973 /*CausedByPointerEscape=*/CausesPointerEscape: true);
3974 }
3975
3976 Bldr.generateNode(S: A, Pred, St: state);
3977}
3978
3979void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
3980 ExplodedNodeSet &Dst) {
3981 NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3982 Bldr.generateNode(S: A, Pred, St: Pred->getState());
3983}
3984
3985//===----------------------------------------------------------------------===//
3986// Visualization.
3987//===----------------------------------------------------------------------===//
3988
3989namespace llvm {
3990
3991template<>
3992struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
3993 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
3994
3995 static bool nodeHasBugReport(const ExplodedNode *N) {
3996 BugReporter &BR = static_cast<ExprEngine &>(
3997 N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3998
3999 for (const auto &Class : BR.equivalenceClasses()) {
4000 for (const auto &Report : Class.getReports()) {
4001 const auto *PR = dyn_cast<PathSensitiveBugReport>(Val: Report.get());
4002 if (!PR)
4003 continue;
4004 const ExplodedNode *EN = PR->getErrorNode();
4005 if (EN->getState() == N->getState() &&
4006 EN->getLocation() == N->getLocation())
4007 return true;
4008 }
4009 }
4010 return false;
4011 }
4012
4013 /// \p PreCallback: callback before break.
4014 /// \p PostCallback: callback after break.
4015 /// \p Stop: stop iteration if returns @c true
4016 /// \return Whether @c Stop ever returned @c true.
4017 static bool traverseHiddenNodes(
4018 const ExplodedNode *N,
4019 llvm::function_ref<void(const ExplodedNode *)> PreCallback,
4020 llvm::function_ref<void(const ExplodedNode *)> PostCallback,
4021 llvm::function_ref<bool(const ExplodedNode *)> Stop) {
4022 while (true) {
4023 PreCallback(N);
4024 if (Stop(N))
4025 return true;
4026
4027 if (N->succ_size() != 1 || !isNodeHidden(N: N->getFirstSucc(), G: nullptr))
4028 break;
4029 PostCallback(N);
4030
4031 N = N->getFirstSucc();
4032 }
4033 return false;
4034 }
4035
4036 static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) {
4037 return N->isTrivial();
4038 }
4039
4040 static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
4041 std::string Buf;
4042 llvm::raw_string_ostream Out(Buf);
4043
4044 const bool IsDot = true;
4045 const unsigned int Space = 1;
4046 ProgramStateRef State = N->getState();
4047
4048 Out << "{ \"state_id\": " << State->getID()
4049 << ",\\l";
4050
4051 Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
4052
4053 // Dump program point for all the previously skipped nodes.
4054 traverseHiddenNodes(
4055 N,
4056 PreCallback: [&](const ExplodedNode *OtherNode) {
4057 Indent(Out, Space: Space + 1, IsDot) << "{ ";
4058 OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
4059 Out << ", \"tag\": ";
4060 if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
4061 Out << '\"' << Tag->getDebugTag() << '\"';
4062 else
4063 Out << "null";
4064 Out << ", \"node_id\": " << OtherNode->getID() <<
4065 ", \"is_sink\": " << OtherNode->isSink() <<
4066 ", \"has_report\": " << nodeHasBugReport(N: OtherNode) << " }";
4067 },
4068 // Adds a comma and a new-line between each program point.
4069 PostCallback: [&](const ExplodedNode *) { Out << ",\\l"; },
4070 Stop: [&](const ExplodedNode *) { return false; });
4071
4072 Out << "\\l"; // Adds a new-line to the last program point.
4073 Indent(Out, Space, IsDot) << "],\\l";
4074
4075 State->printDOT(Out, LCtx: N->getLocationContext(), Space);
4076
4077 Out << "\\l}\\l";
4078 return Buf;
4079 }
4080};
4081
4082} // namespace llvm
4083
4084void ExprEngine::ViewGraph(bool trim) {
4085 std::string Filename = DumpGraph(trim);
4086 llvm::DisplayGraph(Filename, wait: false, program: llvm::GraphProgram::DOT);
4087}
4088
4089void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) {
4090 std::string Filename = DumpGraph(Nodes);
4091 llvm::DisplayGraph(Filename, wait: false, program: llvm::GraphProgram::DOT);
4092}
4093
4094std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
4095 if (trim) {
4096 std::vector<const ExplodedNode *> Src;
4097
4098 // Iterate through the reports and get their nodes.
4099 for (const auto &Class : BR.equivalenceClasses()) {
4100 const auto *R =
4101 dyn_cast<PathSensitiveBugReport>(Val: Class.getReports()[0].get());
4102 if (!R)
4103 continue;
4104 const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
4105 Src.push_back(x: N);
4106 }
4107 return DumpGraph(Nodes: Src, Filename);
4108 }
4109
4110 // FIXME(sandboxing): Remove this by adopting `llvm::vfs::OutputBackend`.
4111 auto BypassSandbox = llvm::sys::sandbox::scopedDisable();
4112 return llvm::WriteGraph(G: &G, Name: "ExprEngine", /*ShortNames=*/false,
4113 /*Title=*/"Exploded Graph",
4114 /*Filename=*/std::string(Filename));
4115}
4116
4117std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes,
4118 StringRef Filename) {
4119 std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
4120
4121 if (!TrimmedG) {
4122 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
4123 return "";
4124 }
4125
4126 // FIXME(sandboxing): Remove this by adopting `llvm::vfs::OutputBackend`.
4127 auto BypassSandbox = llvm::sys::sandbox::scopedDisable();
4128 return llvm::WriteGraph(G: TrimmedG.get(), Name: "TrimmedExprEngine",
4129 /*ShortNames=*/false,
4130 /*Title=*/"Trimmed Exploded Graph",
4131 /*Filename=*/std::string(Filename));
4132}
4133
4134void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
4135 static int index = 0;
4136 return &index;
4137}
4138
4139void ExprEngine::anchor() { }
4140
4141void ExprEngine::ConstructInitList(const Expr *E, ArrayRef<Expr *> Args,
4142 bool IsTransparent, ExplodedNode *Pred,
4143 ExplodedNodeSet &Dst) {
4144 assert((isa<InitListExpr, CXXParenListInitExpr>(E)));
4145
4146 const LocationContext *LC = Pred->getLocationContext();
4147
4148 NodeBuilder B(Pred, Dst, *currBldrCtx);
4149 ProgramStateRef S = Pred->getState();
4150 QualType T = E->getType().getCanonicalType();
4151
4152 bool IsCompound = T->isArrayType() || T->isRecordType() ||
4153 T->isAnyComplexType() || T->isVectorType();
4154
4155 if (Args.size() > 1 || (E->isPRValue() && IsCompound && !IsTransparent)) {
4156 llvm::ImmutableList<SVal> ArgList = getBasicVals().getEmptySValList();
4157 for (Expr *E : llvm::reverse(C&: Args))
4158 ArgList = getBasicVals().prependSVal(X: S->getSVal(Ex: E, LCtx: LC), L: ArgList);
4159
4160 B.generateNode(S: E, Pred,
4161 St: S->BindExpr(S: E, LCtx: LC, V: svalBuilder.makeCompoundVal(type: T, vals: ArgList)));
4162 } else {
4163 B.generateNode(S: E, Pred,
4164 St: S->BindExpr(S: E, LCtx: LC,
4165 V: Args.size() == 0
4166 ? getSValBuilder().makeZeroVal(type: T)
4167 : S->getSVal(Ex: Args.front(), LCtx: LC)));
4168 }
4169}
4170