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