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(PD, 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(SelfD, 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(InitWithAdjustments, 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(Result, LC, *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(Init, 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(Result, LC, Reg);
464 } else {
465 State = State->BindExpr(Result, LC, 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(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(Context.getSourceManager()) << " '"
837 << QualType::getAsString(E->getType().split(), 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(decl, 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(Init, 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(BMI->getInit(), stackFrame);
1221 }
1222
1223 PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
1224 evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &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(Init, stackFrame);
1233 evalBind(Tmp, Init, Pred, BaseLoc, InitVal, /*isInit=*/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(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, 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(CurDtor,
1492 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(CurDtor, 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(D.getBindTemporaryExpr(), Pred, 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(T, MR, D.getBindTemporaryExpr(),
1638 /*IsBase=*/false, CleanPred, Dst, 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(BTE, Node, 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::TypoExprClass:
1736 case Stmt::RecoveryExprClass:
1737 case Stmt::CXXNoexceptExprClass:
1738 case Stmt::PackExpansionExprClass:
1739 case Stmt::PackIndexingExprClass:
1740 case Stmt::SubstNonTypeTemplateParmPackExprClass:
1741 case Stmt::FunctionParmPackExprClass:
1742 case Stmt::CoroutineBodyStmtClass:
1743 case Stmt::CoawaitExprClass:
1744 case Stmt::DependentCoawaitExprClass:
1745 case Stmt::CoreturnStmtClass:
1746 case Stmt::CoyieldExprClass:
1747 case Stmt::SEHTryStmtClass:
1748 case Stmt::SEHExceptStmtClass:
1749 case Stmt::SEHLeaveStmtClass:
1750 case Stmt::SEHFinallyStmtClass:
1751 case Stmt::OMPCanonicalLoopClass:
1752 case Stmt::OMPParallelDirectiveClass:
1753 case Stmt::OMPSimdDirectiveClass:
1754 case Stmt::OMPForDirectiveClass:
1755 case Stmt::OMPForSimdDirectiveClass:
1756 case Stmt::OMPSectionsDirectiveClass:
1757 case Stmt::OMPSectionDirectiveClass:
1758 case Stmt::OMPScopeDirectiveClass:
1759 case Stmt::OMPSingleDirectiveClass:
1760 case Stmt::OMPMasterDirectiveClass:
1761 case Stmt::OMPCriticalDirectiveClass:
1762 case Stmt::OMPParallelForDirectiveClass:
1763 case Stmt::OMPParallelForSimdDirectiveClass:
1764 case Stmt::OMPParallelSectionsDirectiveClass:
1765 case Stmt::OMPParallelMasterDirectiveClass:
1766 case Stmt::OMPParallelMaskedDirectiveClass:
1767 case Stmt::OMPTaskDirectiveClass:
1768 case Stmt::OMPTaskyieldDirectiveClass:
1769 case Stmt::OMPBarrierDirectiveClass:
1770 case Stmt::OMPTaskwaitDirectiveClass:
1771 case Stmt::OMPErrorDirectiveClass:
1772 case Stmt::OMPTaskgroupDirectiveClass:
1773 case Stmt::OMPFlushDirectiveClass:
1774 case Stmt::OMPDepobjDirectiveClass:
1775 case Stmt::OMPScanDirectiveClass:
1776 case Stmt::OMPOrderedDirectiveClass:
1777 case Stmt::OMPAtomicDirectiveClass:
1778 case Stmt::OMPAssumeDirectiveClass:
1779 case Stmt::OMPTargetDirectiveClass:
1780 case Stmt::OMPTargetDataDirectiveClass:
1781 case Stmt::OMPTargetEnterDataDirectiveClass:
1782 case Stmt::OMPTargetExitDataDirectiveClass:
1783 case Stmt::OMPTargetParallelDirectiveClass:
1784 case Stmt::OMPTargetParallelForDirectiveClass:
1785 case Stmt::OMPTargetUpdateDirectiveClass:
1786 case Stmt::OMPTeamsDirectiveClass:
1787 case Stmt::OMPCancellationPointDirectiveClass:
1788 case Stmt::OMPCancelDirectiveClass:
1789 case Stmt::OMPTaskLoopDirectiveClass:
1790 case Stmt::OMPTaskLoopSimdDirectiveClass:
1791 case Stmt::OMPMasterTaskLoopDirectiveClass:
1792 case Stmt::OMPMaskedTaskLoopDirectiveClass:
1793 case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1794 case Stmt::OMPMaskedTaskLoopSimdDirectiveClass:
1795 case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1796 case Stmt::OMPParallelMaskedTaskLoopDirectiveClass:
1797 case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:
1798 case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass:
1799 case Stmt::OMPDistributeDirectiveClass:
1800 case Stmt::OMPDistributeParallelForDirectiveClass:
1801 case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1802 case Stmt::OMPDistributeSimdDirectiveClass:
1803 case Stmt::OMPTargetParallelForSimdDirectiveClass:
1804 case Stmt::OMPTargetSimdDirectiveClass:
1805 case Stmt::OMPTeamsDistributeDirectiveClass:
1806 case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1807 case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1808 case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1809 case Stmt::OMPTargetTeamsDirectiveClass:
1810 case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1811 case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1812 case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1813 case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1814 case Stmt::OMPReverseDirectiveClass:
1815 case Stmt::OMPStripeDirectiveClass:
1816 case Stmt::OMPTileDirectiveClass:
1817 case Stmt::OMPInterchangeDirectiveClass:
1818 case Stmt::OMPInteropDirectiveClass:
1819 case Stmt::OMPDispatchDirectiveClass:
1820 case Stmt::OMPMaskedDirectiveClass:
1821 case Stmt::OMPGenericLoopDirectiveClass:
1822 case Stmt::OMPTeamsGenericLoopDirectiveClass:
1823 case Stmt::OMPTargetTeamsGenericLoopDirectiveClass:
1824 case Stmt::OMPParallelGenericLoopDirectiveClass:
1825 case Stmt::OMPTargetParallelGenericLoopDirectiveClass:
1826 case Stmt::CapturedStmtClass:
1827 case Stmt::SYCLKernelCallStmtClass:
1828 case Stmt::OpenACCComputeConstructClass:
1829 case Stmt::OpenACCLoopConstructClass:
1830 case Stmt::OpenACCCombinedConstructClass:
1831 case Stmt::OpenACCDataConstructClass:
1832 case Stmt::OpenACCEnterDataConstructClass:
1833 case Stmt::OpenACCExitDataConstructClass:
1834 case Stmt::OpenACCHostDataConstructClass:
1835 case Stmt::OpenACCWaitConstructClass:
1836 case Stmt::OpenACCCacheConstructClass:
1837 case Stmt::OpenACCInitConstructClass:
1838 case Stmt::OpenACCShutdownConstructClass:
1839 case Stmt::OpenACCSetConstructClass:
1840 case Stmt::OpenACCUpdateConstructClass:
1841 case Stmt::OpenACCAtomicConstructClass:
1842 case Stmt::OMPUnrollDirectiveClass:
1843 case Stmt::OMPMetaDirectiveClass:
1844 case Stmt::HLSLOutArgExprClass: {
1845 const ExplodedNode *node = Bldr.generateSink(S, Pred, St: Pred->getState());
1846 Engine.addAbortedBlock(node, block: currBldrCtx->getBlock());
1847 break;
1848 }
1849
1850 case Stmt::ParenExprClass:
1851 llvm_unreachable("ParenExprs already handled.");
1852 case Stmt::GenericSelectionExprClass:
1853 llvm_unreachable("GenericSelectionExprs already handled.");
1854 // Cases that should never be evaluated simply because they shouldn't
1855 // appear in the CFG.
1856 case Stmt::BreakStmtClass:
1857 case Stmt::CaseStmtClass:
1858 case Stmt::CompoundStmtClass:
1859 case Stmt::ContinueStmtClass:
1860 case Stmt::CXXForRangeStmtClass:
1861 case Stmt::DefaultStmtClass:
1862 case Stmt::DoStmtClass:
1863 case Stmt::ForStmtClass:
1864 case Stmt::GotoStmtClass:
1865 case Stmt::IfStmtClass:
1866 case Stmt::IndirectGotoStmtClass:
1867 case Stmt::LabelStmtClass:
1868 case Stmt::NoStmtClass:
1869 case Stmt::NullStmtClass:
1870 case Stmt::SwitchStmtClass:
1871 case Stmt::WhileStmtClass:
1872 case Expr::MSDependentExistsStmtClass:
1873 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
1874 case Stmt::ImplicitValueInitExprClass:
1875 // These nodes are shared in the CFG and would case caching out.
1876 // Moreover, no additional evaluation required for them, the
1877 // analyzer can reconstruct these values from the AST.
1878 llvm_unreachable("Should be pruned from CFG");
1879
1880 case Stmt::ObjCSubscriptRefExprClass:
1881 case Stmt::ObjCPropertyRefExprClass:
1882 llvm_unreachable("These are handled by PseudoObjectExpr");
1883
1884 case Stmt::GNUNullExprClass: {
1885 // GNU __null is a pointer-width integer, not an actual pointer.
1886 ProgramStateRef state = Pred->getState();
1887 state = state->BindExpr(
1888 S, LCtx: Pred->getLocationContext(),
1889 V: svalBuilder.makeIntValWithWidth(ptrType: getContext().VoidPtrTy, integer: 0));
1890 Bldr.generateNode(S, Pred, St: state);
1891 break;
1892 }
1893
1894 case Stmt::ObjCAtSynchronizedStmtClass:
1895 Bldr.takeNodes(N: Pred);
1896 VisitObjCAtSynchronizedStmt(S: cast<ObjCAtSynchronizedStmt>(Val: S), Pred, Dst);
1897 Bldr.addNodes(S: Dst);
1898 break;
1899
1900 case Expr::ConstantExprClass:
1901 case Stmt::ExprWithCleanupsClass:
1902 // Handled due to fully linearised CFG.
1903 break;
1904
1905 case Stmt::CXXBindTemporaryExprClass: {
1906 Bldr.takeNodes(N: Pred);
1907 ExplodedNodeSet PreVisit;
1908 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
1909 ExplodedNodeSet Next;
1910 VisitCXXBindTemporaryExpr(BTE: cast<CXXBindTemporaryExpr>(Val: S), PreVisit, Dst&: Next);
1911 getCheckerManager().runCheckersForPostStmt(Dst, Src: Next, S, Eng&: *this);
1912 Bldr.addNodes(S: Dst);
1913 break;
1914 }
1915
1916 case Stmt::ArrayInitLoopExprClass:
1917 Bldr.takeNodes(N: Pred);
1918 VisitArrayInitLoopExpr(Ex: cast<ArrayInitLoopExpr>(Val: S), Pred, Dst);
1919 Bldr.addNodes(S: Dst);
1920 break;
1921 // Cases not handled yet; but will handle some day.
1922 case Stmt::DesignatedInitExprClass:
1923 case Stmt::DesignatedInitUpdateExprClass:
1924 case Stmt::ArrayInitIndexExprClass:
1925 case Stmt::ExtVectorElementExprClass:
1926 case Stmt::ImaginaryLiteralClass:
1927 case Stmt::ObjCAtCatchStmtClass:
1928 case Stmt::ObjCAtFinallyStmtClass:
1929 case Stmt::ObjCAtTryStmtClass:
1930 case Stmt::ObjCAutoreleasePoolStmtClass:
1931 case Stmt::ObjCEncodeExprClass:
1932 case Stmt::ObjCIsaExprClass:
1933 case Stmt::ObjCProtocolExprClass:
1934 case Stmt::ObjCSelectorExprClass:
1935 case Stmt::ParenListExprClass:
1936 case Stmt::ShuffleVectorExprClass:
1937 case Stmt::ConvertVectorExprClass:
1938 case Stmt::VAArgExprClass:
1939 case Stmt::CUDAKernelCallExprClass:
1940 case Stmt::OpaqueValueExprClass:
1941 case Stmt::AsTypeExprClass:
1942 case Stmt::ConceptSpecializationExprClass:
1943 case Stmt::CXXRewrittenBinaryOperatorClass:
1944 case Stmt::RequiresExprClass:
1945 case Expr::CXXParenListInitExprClass:
1946 case Stmt::EmbedExprClass:
1947 // Fall through.
1948
1949 // Cases we intentionally don't evaluate, since they don't need
1950 // to be explicitly evaluated.
1951 case Stmt::PredefinedExprClass:
1952 case Stmt::AddrLabelExprClass:
1953 case Stmt::IntegerLiteralClass:
1954 case Stmt::FixedPointLiteralClass:
1955 case Stmt::CharacterLiteralClass:
1956 case Stmt::CXXScalarValueInitExprClass:
1957 case Stmt::CXXBoolLiteralExprClass:
1958 case Stmt::ObjCBoolLiteralExprClass:
1959 case Stmt::ObjCAvailabilityCheckExprClass:
1960 case Stmt::FloatingLiteralClass:
1961 case Stmt::NoInitExprClass:
1962 case Stmt::SizeOfPackExprClass:
1963 case Stmt::StringLiteralClass:
1964 case Stmt::SourceLocExprClass:
1965 case Stmt::ObjCStringLiteralClass:
1966 case Stmt::CXXPseudoDestructorExprClass:
1967 case Stmt::SubstNonTypeTemplateParmExprClass:
1968 case Stmt::CXXNullPtrLiteralExprClass:
1969 case Stmt::ArraySectionExprClass:
1970 case Stmt::OMPArrayShapingExprClass:
1971 case Stmt::OMPIteratorExprClass:
1972 case Stmt::SYCLUniqueStableNameExprClass:
1973 case Stmt::OpenACCAsteriskSizeExprClass:
1974 case Stmt::TypeTraitExprClass: {
1975 Bldr.takeNodes(N: Pred);
1976 ExplodedNodeSet preVisit;
1977 getCheckerManager().runCheckersForPreStmt(Dst&: preVisit, Src: Pred, S, Eng&: *this);
1978 getCheckerManager().runCheckersForPostStmt(Dst, Src: preVisit, S, Eng&: *this);
1979 Bldr.addNodes(S: Dst);
1980 break;
1981 }
1982
1983 case Stmt::AttributedStmtClass: {
1984 Bldr.takeNodes(N: Pred);
1985 VisitAttributedStmt(A: cast<AttributedStmt>(Val: S), Pred, Dst);
1986 Bldr.addNodes(S: Dst);
1987 break;
1988 }
1989
1990 case Stmt::CXXDefaultArgExprClass:
1991 case Stmt::CXXDefaultInitExprClass: {
1992 Bldr.takeNodes(N: Pred);
1993 ExplodedNodeSet PreVisit;
1994 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
1995
1996 ExplodedNodeSet Tmp;
1997 StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
1998
1999 const Expr *ArgE;
2000 if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(Val: S))
2001 ArgE = DefE->getExpr();
2002 else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(Val: S))
2003 ArgE = DefE->getExpr();
2004 else
2005 llvm_unreachable("unknown constant wrapper kind");
2006
2007 bool IsTemporary = false;
2008 if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(Val: ArgE)) {
2009 ArgE = MTE->getSubExpr();
2010 IsTemporary = true;
2011 }
2012
2013 std::optional<SVal> ConstantVal = svalBuilder.getConstantVal(E: ArgE);
2014 if (!ConstantVal)
2015 ConstantVal = UnknownVal();
2016
2017 const LocationContext *LCtx = Pred->getLocationContext();
2018 for (const auto I : PreVisit) {
2019 ProgramStateRef State = I->getState();
2020 State = State->BindExpr(S, LCtx, V: *ConstantVal);
2021 if (IsTemporary)
2022 State = createTemporaryRegionIfNeeded(State, LC: LCtx,
2023 InitWithAdjustments: cast<Expr>(Val: S),
2024 Result: cast<Expr>(Val: S));
2025 Bldr2.generateNode(S, Pred: I, St: State);
2026 }
2027
2028 getCheckerManager().runCheckersForPostStmt(Dst, Src: Tmp, S, Eng&: *this);
2029 Bldr.addNodes(S: Dst);
2030 break;
2031 }
2032
2033 // Cases we evaluate as opaque expressions, conjuring a symbol.
2034 case Stmt::CXXStdInitializerListExprClass:
2035 case Expr::ObjCArrayLiteralClass:
2036 case Expr::ObjCDictionaryLiteralClass:
2037 case Expr::ObjCBoxedExprClass: {
2038 Bldr.takeNodes(N: Pred);
2039
2040 ExplodedNodeSet preVisit;
2041 getCheckerManager().runCheckersForPreStmt(Dst&: preVisit, Src: Pred, S, Eng&: *this);
2042
2043 ExplodedNodeSet Tmp;
2044 StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
2045
2046 const auto *Ex = cast<Expr>(Val: S);
2047 QualType resultType = Ex->getType();
2048
2049 for (const auto N : preVisit) {
2050 const LocationContext *LCtx = N->getLocationContext();
2051 SVal result = svalBuilder.conjureSymbolVal(
2052 /*symbolTag=*/nullptr, elem: getCFGElementRef(), LCtx, type: resultType,
2053 count: currBldrCtx->blockCount());
2054 ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
2055
2056 // Escape pointers passed into the list, unless it's an ObjC boxed
2057 // expression which is not a boxable C structure.
2058 if (!(isa<ObjCBoxedExpr>(Ex) &&
2059 !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
2060 ->getType()->isRecordType()))
2061 for (auto Child : Ex->children()) {
2062 assert(Child);
2063 SVal Val = State->getSVal(Child, LCtx);
2064 State = escapeValues(State, Val, PSK_EscapeOther);
2065 }
2066
2067 Bldr2.generateNode(S, Pred: N, St: State);
2068 }
2069
2070 getCheckerManager().runCheckersForPostStmt(Dst, Src: Tmp, S, Eng&: *this);
2071 Bldr.addNodes(S: Dst);
2072 break;
2073 }
2074
2075 case Stmt::ArraySubscriptExprClass:
2076 Bldr.takeNodes(N: Pred);
2077 VisitArraySubscriptExpr(Ex: cast<ArraySubscriptExpr>(Val: S), Pred, Dst);
2078 Bldr.addNodes(S: Dst);
2079 break;
2080
2081 case Stmt::MatrixSubscriptExprClass:
2082 llvm_unreachable("Support for MatrixSubscriptExpr is not implemented.");
2083 break;
2084
2085 case Stmt::GCCAsmStmtClass: {
2086 Bldr.takeNodes(N: Pred);
2087 ExplodedNodeSet PreVisit;
2088 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2089 ExplodedNodeSet PostVisit;
2090 for (ExplodedNode *const N : PreVisit)
2091 VisitGCCAsmStmt(A: cast<GCCAsmStmt>(Val: S), Pred: N, Dst&: PostVisit);
2092 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2093 Bldr.addNodes(S: Dst);
2094 break;
2095 }
2096
2097 case Stmt::MSAsmStmtClass:
2098 Bldr.takeNodes(N: Pred);
2099 VisitMSAsmStmt(A: cast<MSAsmStmt>(Val: S), Pred, Dst);
2100 Bldr.addNodes(S: Dst);
2101 break;
2102
2103 case Stmt::BlockExprClass:
2104 Bldr.takeNodes(N: Pred);
2105 VisitBlockExpr(BE: cast<BlockExpr>(Val: S), Pred, Dst);
2106 Bldr.addNodes(S: Dst);
2107 break;
2108
2109 case Stmt::LambdaExprClass:
2110 if (AMgr.options.ShouldInlineLambdas) {
2111 Bldr.takeNodes(N: Pred);
2112 VisitLambdaExpr(LE: cast<LambdaExpr>(Val: S), Pred, Dst);
2113 Bldr.addNodes(S: Dst);
2114 } else {
2115 const ExplodedNode *node = Bldr.generateSink(S, Pred, St: Pred->getState());
2116 Engine.addAbortedBlock(node, block: currBldrCtx->getBlock());
2117 }
2118 break;
2119
2120 case Stmt::BinaryOperatorClass: {
2121 const auto *B = cast<BinaryOperator>(Val: S);
2122 if (B->isLogicalOp()) {
2123 Bldr.takeNodes(N: Pred);
2124 VisitLogicalExpr(B, Pred, Dst);
2125 Bldr.addNodes(S: Dst);
2126 break;
2127 }
2128 else if (B->getOpcode() == BO_Comma) {
2129 ProgramStateRef state = Pred->getState();
2130 Bldr.generateNode(B, Pred,
2131 state->BindExpr(B, Pred->getLocationContext(),
2132 state->getSVal(B->getRHS(),
2133 Pred->getLocationContext())));
2134 break;
2135 }
2136
2137 Bldr.takeNodes(N: Pred);
2138
2139 if (AMgr.options.ShouldEagerlyAssume &&
2140 (B->isRelationalOp() || B->isEqualityOp())) {
2141 ExplodedNodeSet Tmp;
2142 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst&: Tmp);
2143 evalEagerlyAssumeBifurcation(Dst, Src&: Tmp, Ex: cast<Expr>(Val: S));
2144 }
2145 else
2146 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst);
2147
2148 Bldr.addNodes(S: Dst);
2149 break;
2150 }
2151
2152 case Stmt::CXXOperatorCallExprClass: {
2153 const auto *OCE = cast<CXXOperatorCallExpr>(Val: S);
2154
2155 // For instance method operators, make sure the 'this' argument has a
2156 // valid region.
2157 const Decl *Callee = OCE->getCalleeDecl();
2158 if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
2159 if (MD->isImplicitObjectMemberFunction()) {
2160 ProgramStateRef State = Pred->getState();
2161 const LocationContext *LCtx = Pred->getLocationContext();
2162 ProgramStateRef NewState =
2163 createTemporaryRegionIfNeeded(State, LC: LCtx, InitWithAdjustments: OCE->getArg(0));
2164 if (NewState != State) {
2165 Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
2166 ProgramPoint::PreStmtKind);
2167 // Did we cache out?
2168 if (!Pred)
2169 break;
2170 }
2171 }
2172 }
2173 [[fallthrough]];
2174 }
2175
2176 case Stmt::CallExprClass:
2177 case Stmt::CXXMemberCallExprClass:
2178 case Stmt::UserDefinedLiteralClass:
2179 Bldr.takeNodes(N: Pred);
2180 VisitCallExpr(CE: cast<CallExpr>(Val: S), Pred, Dst);
2181 Bldr.addNodes(S: Dst);
2182 break;
2183
2184 case Stmt::CXXCatchStmtClass:
2185 Bldr.takeNodes(N: Pred);
2186 VisitCXXCatchStmt(CS: cast<CXXCatchStmt>(Val: S), Pred, Dst);
2187 Bldr.addNodes(S: Dst);
2188 break;
2189
2190 case Stmt::CXXTemporaryObjectExprClass:
2191 case Stmt::CXXConstructExprClass:
2192 Bldr.takeNodes(N: Pred);
2193 VisitCXXConstructExpr(E: cast<CXXConstructExpr>(Val: S), Pred, Dst);
2194 Bldr.addNodes(S: Dst);
2195 break;
2196
2197 case Stmt::CXXInheritedCtorInitExprClass:
2198 Bldr.takeNodes(N: Pred);
2199 VisitCXXInheritedCtorInitExpr(E: cast<CXXInheritedCtorInitExpr>(Val: S), Pred,
2200 Dst);
2201 Bldr.addNodes(S: Dst);
2202 break;
2203
2204 case Stmt::CXXNewExprClass: {
2205 Bldr.takeNodes(N: Pred);
2206
2207 ExplodedNodeSet PreVisit;
2208 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2209
2210 ExplodedNodeSet PostVisit;
2211 for (const auto i : PreVisit)
2212 VisitCXXNewExpr(CNE: cast<CXXNewExpr>(Val: S), Pred: i, Dst&: PostVisit);
2213
2214 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2215 Bldr.addNodes(S: Dst);
2216 break;
2217 }
2218
2219 case Stmt::CXXDeleteExprClass: {
2220 Bldr.takeNodes(N: Pred);
2221 ExplodedNodeSet PreVisit;
2222 const auto *CDE = cast<CXXDeleteExpr>(Val: S);
2223 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2224 ExplodedNodeSet PostVisit;
2225 getCheckerManager().runCheckersForPostStmt(Dst&: PostVisit, Src: PreVisit, S, Eng&: *this);
2226
2227 for (const auto i : PostVisit)
2228 VisitCXXDeleteExpr(CDE, Pred: i, Dst);
2229
2230 Bldr.addNodes(S: Dst);
2231 break;
2232 }
2233 // FIXME: ChooseExpr is really a constant. We need to fix
2234 // the CFG do not model them as explicit control-flow.
2235
2236 case Stmt::ChooseExprClass: { // __builtin_choose_expr
2237 Bldr.takeNodes(N: Pred);
2238 const auto *C = cast<ChooseExpr>(Val: S);
2239 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
2240 Bldr.addNodes(S: Dst);
2241 break;
2242 }
2243
2244 case Stmt::CompoundAssignOperatorClass:
2245 Bldr.takeNodes(N: Pred);
2246 VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), Pred, Dst);
2247 Bldr.addNodes(S: Dst);
2248 break;
2249
2250 case Stmt::CompoundLiteralExprClass:
2251 Bldr.takeNodes(N: Pred);
2252 VisitCompoundLiteralExpr(CL: cast<CompoundLiteralExpr>(Val: S), Pred, Dst);
2253 Bldr.addNodes(S: Dst);
2254 break;
2255
2256 case Stmt::BinaryConditionalOperatorClass:
2257 case Stmt::ConditionalOperatorClass: { // '?' operator
2258 Bldr.takeNodes(N: Pred);
2259 const auto *C = cast<AbstractConditionalOperator>(Val: S);
2260 VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
2261 Bldr.addNodes(S: Dst);
2262 break;
2263 }
2264
2265 case Stmt::CXXThisExprClass:
2266 Bldr.takeNodes(N: Pred);
2267 VisitCXXThisExpr(TE: cast<CXXThisExpr>(Val: S), Pred, Dst);
2268 Bldr.addNodes(S: Dst);
2269 break;
2270
2271 case Stmt::DeclRefExprClass: {
2272 Bldr.takeNodes(N: Pred);
2273 const auto *DE = cast<DeclRefExpr>(Val: S);
2274 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
2275 Bldr.addNodes(S: Dst);
2276 break;
2277 }
2278
2279 case Stmt::DeclStmtClass:
2280 Bldr.takeNodes(N: Pred);
2281 VisitDeclStmt(DS: cast<DeclStmt>(Val: S), Pred, Dst);
2282 Bldr.addNodes(S: Dst);
2283 break;
2284
2285 case Stmt::ImplicitCastExprClass:
2286 case Stmt::CStyleCastExprClass:
2287 case Stmt::CXXStaticCastExprClass:
2288 case Stmt::CXXDynamicCastExprClass:
2289 case Stmt::CXXReinterpretCastExprClass:
2290 case Stmt::CXXConstCastExprClass:
2291 case Stmt::CXXFunctionalCastExprClass:
2292 case Stmt::BuiltinBitCastExprClass:
2293 case Stmt::ObjCBridgedCastExprClass:
2294 case Stmt::CXXAddrspaceCastExprClass: {
2295 Bldr.takeNodes(N: Pred);
2296 const auto *C = cast<CastExpr>(Val: S);
2297 ExplodedNodeSet dstExpr;
2298 VisitCast(CastE: C, Ex: C->getSubExpr(), Pred, Dst&: dstExpr);
2299
2300 // Handle the postvisit checks.
2301 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
2302 Bldr.addNodes(S: Dst);
2303 break;
2304 }
2305
2306 case Expr::MaterializeTemporaryExprClass: {
2307 Bldr.takeNodes(N: Pred);
2308 const auto *MTE = cast<MaterializeTemporaryExpr>(Val: S);
2309 ExplodedNodeSet dstPrevisit;
2310 getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
2311 ExplodedNodeSet dstExpr;
2312 for (const auto i : dstPrevisit)
2313 CreateCXXTemporaryObject(ME: MTE, Pred: i, Dst&: dstExpr);
2314 getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
2315 Bldr.addNodes(S: Dst);
2316 break;
2317 }
2318
2319 case Stmt::InitListExprClass:
2320 Bldr.takeNodes(N: Pred);
2321 VisitInitListExpr(E: cast<InitListExpr>(Val: S), Pred, Dst);
2322 Bldr.addNodes(S: Dst);
2323 break;
2324
2325 case Stmt::MemberExprClass:
2326 Bldr.takeNodes(N: Pred);
2327 VisitMemberExpr(M: cast<MemberExpr>(Val: S), Pred, Dst);
2328 Bldr.addNodes(S: Dst);
2329 break;
2330
2331 case Stmt::AtomicExprClass:
2332 Bldr.takeNodes(N: Pred);
2333 VisitAtomicExpr(E: cast<AtomicExpr>(Val: S), Pred, Dst);
2334 Bldr.addNodes(S: Dst);
2335 break;
2336
2337 case Stmt::ObjCIvarRefExprClass:
2338 Bldr.takeNodes(N: Pred);
2339 VisitLvalObjCIvarRefExpr(DR: cast<ObjCIvarRefExpr>(Val: S), Pred, Dst);
2340 Bldr.addNodes(S: Dst);
2341 break;
2342
2343 case Stmt::ObjCForCollectionStmtClass:
2344 Bldr.takeNodes(N: Pred);
2345 VisitObjCForCollectionStmt(S: cast<ObjCForCollectionStmt>(Val: S), Pred, Dst);
2346 Bldr.addNodes(S: Dst);
2347 break;
2348
2349 case Stmt::ObjCMessageExprClass:
2350 Bldr.takeNodes(N: Pred);
2351 VisitObjCMessage(ME: cast<ObjCMessageExpr>(Val: S), Pred, Dst);
2352 Bldr.addNodes(S: Dst);
2353 break;
2354
2355 case Stmt::ObjCAtThrowStmtClass:
2356 case Stmt::CXXThrowExprClass:
2357 // FIXME: This is not complete. We basically treat @throw as
2358 // an abort.
2359 Bldr.generateSink(S, Pred, St: Pred->getState());
2360 break;
2361
2362 case Stmt::ReturnStmtClass:
2363 Bldr.takeNodes(N: Pred);
2364 VisitReturnStmt(R: cast<ReturnStmt>(Val: S), Pred, Dst);
2365 Bldr.addNodes(S: Dst);
2366 break;
2367
2368 case Stmt::OffsetOfExprClass: {
2369 Bldr.takeNodes(N: Pred);
2370 ExplodedNodeSet PreVisit;
2371 getCheckerManager().runCheckersForPreStmt(Dst&: PreVisit, Src: Pred, S, Eng&: *this);
2372
2373 ExplodedNodeSet PostVisit;
2374 for (const auto Node : PreVisit)
2375 VisitOffsetOfExpr(Ex: cast<OffsetOfExpr>(Val: S), Pred: Node, Dst&: PostVisit);
2376
2377 getCheckerManager().runCheckersForPostStmt(Dst, Src: PostVisit, S, Eng&: *this);
2378 Bldr.addNodes(S: Dst);
2379 break;
2380 }
2381
2382 case Stmt::UnaryExprOrTypeTraitExprClass:
2383 Bldr.takeNodes(N: Pred);
2384 VisitUnaryExprOrTypeTraitExpr(Ex: cast<UnaryExprOrTypeTraitExpr>(Val: S),
2385 Pred, Dst);
2386 Bldr.addNodes(S: Dst);
2387 break;
2388
2389 case Stmt::StmtExprClass: {
2390 const auto *SE = cast<StmtExpr>(Val: S);
2391
2392 if (SE->getSubStmt()->body_empty()) {
2393 // Empty statement expression.
2394 assert(SE->getType() == getContext().VoidTy
2395 && "Empty statement expression must have void type.");
2396 break;
2397 }
2398
2399 if (const auto *LastExpr =
2400 dyn_cast<Expr>(Val: *SE->getSubStmt()->body_rbegin())) {
2401 ProgramStateRef state = Pred->getState();
2402 Bldr.generateNode(SE, Pred,
2403 state->BindExpr(SE, Pred->getLocationContext(),
2404 state->getSVal(LastExpr,
2405 Pred->getLocationContext())));
2406 }
2407 break;
2408 }
2409
2410 case Stmt::UnaryOperatorClass: {
2411 Bldr.takeNodes(N: Pred);
2412 const auto *U = cast<UnaryOperator>(Val: S);
2413 if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
2414 ExplodedNodeSet Tmp;
2415 VisitUnaryOperator(B: U, Pred, Dst&: Tmp);
2416 evalEagerlyAssumeBifurcation(Dst, Tmp, U);
2417 }
2418 else
2419 VisitUnaryOperator(B: U, Pred, Dst);
2420 Bldr.addNodes(S: Dst);
2421 break;
2422 }
2423
2424 case Stmt::PseudoObjectExprClass: {
2425 Bldr.takeNodes(N: Pred);
2426 ProgramStateRef state = Pred->getState();
2427 const auto *PE = cast<PseudoObjectExpr>(Val: S);
2428 if (const Expr *Result = PE->getResultExpr()) {
2429 SVal V = state->getSVal(Result, Pred->getLocationContext());
2430 Bldr.generateNode(S, Pred,
2431 St: state->BindExpr(S, LCtx: Pred->getLocationContext(), V));
2432 }
2433 else
2434 Bldr.generateNode(S, Pred,
2435 St: state->BindExpr(S, LCtx: Pred->getLocationContext(),
2436 V: UnknownVal()));
2437
2438 Bldr.addNodes(S: Dst);
2439 break;
2440 }
2441
2442 case Expr::ObjCIndirectCopyRestoreExprClass: {
2443 // ObjCIndirectCopyRestoreExpr implies passing a temporary for
2444 // correctness of lifetime management. Due to limited analysis
2445 // of ARC, this is implemented as direct arg passing.
2446 Bldr.takeNodes(N: Pred);
2447 ProgramStateRef state = Pred->getState();
2448 const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(Val: S);
2449 const Expr *E = OIE->getSubExpr();
2450 SVal V = state->getSVal(E, Pred->getLocationContext());
2451 Bldr.generateNode(S, Pred,
2452 St: state->BindExpr(S, LCtx: Pred->getLocationContext(), V));
2453 Bldr.addNodes(S: Dst);
2454 break;
2455 }
2456 }
2457}
2458
2459bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
2460 const LocationContext *CalleeLC) {
2461 const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
2462 const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
2463 assert(CalleeSF && CallerSF);
2464 ExplodedNode *BeforeProcessingCall = nullptr;
2465 const Stmt *CE = CalleeSF->getCallSite();
2466
2467 // Find the first node before we started processing the call expression.
2468 while (N) {
2469 ProgramPoint L = N->getLocation();
2470 BeforeProcessingCall = N;
2471 N = N->pred_empty() ? nullptr : *(N->pred_begin());
2472
2473 // Skip the nodes corresponding to the inlined code.
2474 if (L.getStackFrame() != CallerSF)
2475 continue;
2476 // We reached the caller. Find the node right before we started
2477 // processing the call.
2478 if (L.isPurgeKind())
2479 continue;
2480 if (L.getAs<PreImplicitCall>())
2481 continue;
2482 if (L.getAs<CallEnter>())
2483 continue;
2484 if (std::optional<StmtPoint> SP = L.getAs<StmtPoint>())
2485 if (SP->getStmt() == CE)
2486 continue;
2487 break;
2488 }
2489
2490 if (!BeforeProcessingCall)
2491 return false;
2492
2493 // TODO: Clean up the unneeded nodes.
2494
2495 // Build an Epsilon node from which we will restart the analyzes.
2496 // Note that CE is permitted to be NULL!
2497 static SimpleProgramPointTag PT("ExprEngine", "Replay without inlining");
2498 ProgramPoint NewNodeLoc = EpsilonPoint(
2499 BeforeProcessingCall->getLocationContext(), CE, nullptr, &PT);
2500 // Add the special flag to GDM to signal retrying with no inlining.
2501 // Note, changing the state ensures that we are not going to cache out.
2502 ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
2503 NewNodeState =
2504 NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
2505
2506 // Make the new node a successor of BeforeProcessingCall.
2507 bool IsNew = false;
2508 ExplodedNode *NewNode = G.getNode(L: NewNodeLoc, State: NewNodeState, IsSink: false, IsNew: &IsNew);
2509 // We cached out at this point. Caching out is common due to us backtracking
2510 // from the inlined function, which might spawn several paths.
2511 if (!IsNew)
2512 return true;
2513
2514 NewNode->addPredecessor(V: BeforeProcessingCall, G);
2515
2516 // Add the new node to the work list.
2517 Engine.enqueueStmtNode(N: NewNode, Block: CalleeSF->getCallSiteBlock(),
2518 Idx: CalleeSF->getIndex());
2519 NumTimesRetriedWithoutInlining++;
2520 return true;
2521}
2522
2523/// Return the innermost location context which is inlined at `Node`, unless
2524/// it's the top-level (entry point) location context.
2525static const LocationContext *getInlinedLocationContext(ExplodedNode *Node,
2526 ExplodedGraph &G) {
2527 const LocationContext *CalleeLC = Node->getLocation().getLocationContext();
2528 const LocationContext *RootLC =
2529 G.getRoot()->getLocation().getLocationContext();
2530
2531 if (CalleeLC->getStackFrame() == RootLC->getStackFrame())
2532 return nullptr;
2533
2534 return CalleeLC;
2535}
2536
2537/// Block entrance. (Update counters).
2538void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
2539 NodeBuilderWithSinks &nodeBuilder,
2540 ExplodedNode *Pred) {
2541 // If we reach a loop which has a known bound (and meets
2542 // other constraints) then consider completely unrolling it.
2543 if(AMgr.options.ShouldUnrollLoops) {
2544 unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
2545 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
2546 if (Term) {
2547 ProgramStateRef NewState = updateLoopStack(LoopStmt: Term, ASTCtx&: AMgr.getASTContext(),
2548 Pred, maxVisitOnPath: maxBlockVisitOnPath);
2549 if (NewState != Pred->getState()) {
2550 ExplodedNode *UpdatedNode = nodeBuilder.generateNode(State: NewState, Pred);
2551 if (!UpdatedNode)
2552 return;
2553 Pred = UpdatedNode;
2554 }
2555 }
2556 // Is we are inside an unrolled loop then no need the check the counters.
2557 if(isUnrolledState(State: Pred->getState()))
2558 return;
2559 }
2560
2561 // If this block is terminated by a loop and it has already been visited the
2562 // maximum number of times, widen the loop.
2563 unsigned int BlockCount = nodeBuilder.getContext().blockCount();
2564 if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
2565 AMgr.options.ShouldWidenLoops) {
2566 const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
2567 if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Val: Term))
2568 return;
2569
2570 // Widen.
2571 const LocationContext *LCtx = Pred->getLocationContext();
2572
2573 // FIXME:
2574 // We cannot use the CFG element from the via `ExprEngine::getCFGElementRef`
2575 // since we are currently at the block entrance and the current reference
2576 // would be stale. Ideally, we should pass on the terminator of the CFG
2577 // block, but the terminator cannot be referred as a CFG element.
2578 // Here we just pass the the first CFG element in the block.
2579 ProgramStateRef WidenedState =
2580 getWidenedLoopState(PrevState: Pred->getState(), LCtx, BlockCount,
2581 Elem: *nodeBuilder.getContext().getBlock()->ref_begin());
2582 nodeBuilder.generateNode(State: WidenedState, Pred);
2583 return;
2584 }
2585
2586 // FIXME: Refactor this into a checker.
2587 if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
2588 static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
2589 const ExplodedNode *Sink =
2590 nodeBuilder.generateSink(State: Pred->getState(), Pred, Tag: &tag);
2591
2592 if (const LocationContext *LC = getInlinedLocationContext(Node: Pred, G)) {
2593 // FIXME: This will unconditionally prevent inlining this function (even
2594 // from other entry points), which is not a reasonable heuristic: even if
2595 // we reached max block count on this particular execution path, there
2596 // may be other execution paths (especially with other parametrizations)
2597 // where the analyzer can reach the end of the function (so there is no
2598 // natural reason to avoid inlining it). However, disabling this would
2599 // significantly increase the analysis time (because more entry points
2600 // would exhaust their allocated budget), so it must be compensated by a
2601 // different (more reasonable) reduction of analysis scope.
2602 Engine.FunctionSummaries->markShouldNotInline(
2603 D: LC->getStackFrame()->getDecl());
2604
2605 // Re-run the call evaluation without inlining it, by storing the
2606 // no-inlining policy in the state and enqueuing the new work item on
2607 // the list. Replay should almost never fail. Use the stats to catch it
2608 // if it does.
2609 if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(N: Pred, CalleeLC: LC)))
2610 return;
2611 NumMaxBlockCountReachedInInlined++;
2612 } else
2613 NumMaxBlockCountReached++;
2614
2615 // Make sink nodes as exhausted(for stats) only if retry failed.
2616 Engine.blocksExhausted.push_back(x: std::make_pair(x: L, y&: Sink));
2617 }
2618}
2619
2620void ExprEngine::runCheckersForBlockEntrance(const NodeBuilderContext &BldCtx,
2621 const BlockEntrance &Entrance,
2622 ExplodedNode *Pred,
2623 ExplodedNodeSet &Dst) {
2624 llvm::PrettyStackTraceFormat CrashInfo(
2625 "Processing block entrance B%d -> B%d",
2626 Entrance.getPreviousBlock()->getBlockID(),
2627 Entrance.getBlock()->getBlockID());
2628 currBldrCtx = &BldCtx;
2629 getCheckerManager().runCheckersForBlockEntrance(Dst, Src: Pred, Entrance, Eng&: *this);
2630 currBldrCtx = nullptr;
2631}
2632
2633//===----------------------------------------------------------------------===//
2634// Branch processing.
2635//===----------------------------------------------------------------------===//
2636
2637/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
2638/// to try to recover some path-sensitivity for casts of symbolic
2639/// integers that promote their values (which are currently not tracked well).
2640/// This function returns the SVal bound to Condition->IgnoreCasts if all the
2641// cast(s) did was sign-extend the original value.
2642static SVal RecoverCastedSymbol(ProgramStateRef state,
2643 const Stmt *Condition,
2644 const LocationContext *LCtx,
2645 ASTContext &Ctx) {
2646
2647 const auto *Ex = dyn_cast<Expr>(Val: Condition);
2648 if (!Ex)
2649 return UnknownVal();
2650
2651 uint64_t bits = 0;
2652 bool bitsInit = false;
2653
2654 while (const auto *CE = dyn_cast<CastExpr>(Val: Ex)) {
2655 QualType T = CE->getType();
2656
2657 if (!T->isIntegralOrEnumerationType())
2658 return UnknownVal();
2659
2660 uint64_t newBits = Ctx.getTypeSize(T);
2661 if (!bitsInit || newBits < bits) {
2662 bitsInit = true;
2663 bits = newBits;
2664 }
2665
2666 Ex = CE->getSubExpr();
2667 }
2668
2669 // We reached a non-cast. Is it a symbolic value?
2670 QualType T = Ex->getType();
2671
2672 if (!bitsInit || !T->isIntegralOrEnumerationType() ||
2673 Ctx.getTypeSize(T) > bits)
2674 return UnknownVal();
2675
2676 return state->getSVal(Ex, LCtx);
2677}
2678
2679#ifndef NDEBUG
2680static const Stmt *getRightmostLeaf(const Stmt *Condition) {
2681 while (Condition) {
2682 const auto *BO = dyn_cast<BinaryOperator>(Val: Condition);
2683 if (!BO || !BO->isLogicalOp()) {
2684 return Condition;
2685 }
2686 Condition = BO->getRHS()->IgnoreParens();
2687 }
2688 return nullptr;
2689}
2690#endif
2691
2692// Returns the condition the branch at the end of 'B' depends on and whose value
2693// has been evaluated within 'B'.
2694// In most cases, the terminator condition of 'B' will be evaluated fully in
2695// the last statement of 'B'; in those cases, the resolved condition is the
2696// given 'Condition'.
2697// If the condition of the branch is a logical binary operator tree, the CFG is
2698// optimized: in that case, we know that the expression formed by all but the
2699// rightmost leaf of the logical binary operator tree must be true, and thus
2700// the branch condition is at this point equivalent to the truth value of that
2701// rightmost leaf; the CFG block thus only evaluates this rightmost leaf
2702// expression in its final statement. As the full condition in that case was
2703// not evaluated, and is thus not in the SVal cache, we need to use that leaf
2704// expression to evaluate the truth value of the condition in the current state
2705// space.
2706static const Stmt *ResolveCondition(const Stmt *Condition,
2707 const CFGBlock *B) {
2708 if (const auto *Ex = dyn_cast<Expr>(Val: Condition))
2709 Condition = Ex->IgnoreParens();
2710
2711 const auto *BO = dyn_cast<BinaryOperator>(Val: Condition);
2712 if (!BO || !BO->isLogicalOp())
2713 return Condition;
2714
2715 assert(B->getTerminator().isStmtBranch() &&
2716 "Other kinds of branches are handled separately!");
2717
2718 // For logical operations, we still have the case where some branches
2719 // use the traditional "merge" approach and others sink the branch
2720 // directly into the basic blocks representing the logical operation.
2721 // We need to distinguish between those two cases here.
2722
2723 // The invariants are still shifting, but it is possible that the
2724 // last element in a CFGBlock is not a CFGStmt. Look for the last
2725 // CFGStmt as the value of the condition.
2726 for (CFGElement Elem : llvm::reverse(C: *B)) {
2727 std::optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
2728 if (!CS)
2729 continue;
2730 const Stmt *LastStmt = CS->getStmt();
2731 assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
2732 return LastStmt;
2733 }
2734 llvm_unreachable("could not resolve condition");
2735}
2736
2737using ObjCForLctxPair =
2738 std::pair<const ObjCForCollectionStmt *, const LocationContext *>;
2739
2740REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool)
2741
2742ProgramStateRef ExprEngine::setWhetherHasMoreIteration(
2743 ProgramStateRef State, const ObjCForCollectionStmt *O,
2744 const LocationContext *LC, bool HasMoreIteraton) {
2745 assert(!State->contains<ObjCForHasMoreIterations>({O, LC}));
2746 return State->set<ObjCForHasMoreIterations>(K: {O, LC}, E: HasMoreIteraton);
2747}
2748
2749ProgramStateRef
2750ExprEngine::removeIterationState(ProgramStateRef State,
2751 const ObjCForCollectionStmt *O,
2752 const LocationContext *LC) {
2753 assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2754 return State->remove<ObjCForHasMoreIterations>(K: {O, LC});
2755}
2756
2757bool ExprEngine::hasMoreIteration(ProgramStateRef State,
2758 const ObjCForCollectionStmt *O,
2759 const LocationContext *LC) {
2760 assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2761 return *State->get<ObjCForHasMoreIterations>(key: {O, LC});
2762}
2763
2764/// Split the state on whether there are any more iterations left for this loop.
2765/// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or std::nullopt when
2766/// the acquisition of the loop condition value failed.
2767static std::optional<std::pair<ProgramStateRef, ProgramStateRef>>
2768assumeCondition(const Stmt *Condition, ExplodedNode *N) {
2769 ProgramStateRef State = N->getState();
2770 if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Val: Condition)) {
2771 bool HasMoreIteraton =
2772 ExprEngine::hasMoreIteration(State, O: ObjCFor, LC: N->getLocationContext());
2773 // Checkers have already ran on branch conditions, so the current
2774 // information as to whether the loop has more iteration becomes outdated
2775 // after this point.
2776 State = ExprEngine::removeIterationState(State, O: ObjCFor,
2777 LC: N->getLocationContext());
2778 if (HasMoreIteraton)
2779 return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr};
2780 else
2781 return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State};
2782 }
2783 SVal X = State->getSVal(Ex: Condition, LCtx: N->getLocationContext());
2784
2785 if (X.isUnknownOrUndef()) {
2786 // Give it a chance to recover from unknown.
2787 if (const auto *Ex = dyn_cast<Expr>(Val: Condition)) {
2788 if (Ex->getType()->isIntegralOrEnumerationType()) {
2789 // Try to recover some path-sensitivity. Right now casts of symbolic
2790 // integers that promote their values are currently not tracked well.
2791 // If 'Condition' is such an expression, try and recover the
2792 // underlying value and use that instead.
2793 SVal recovered =
2794 RecoverCastedSymbol(state: State, Condition, LCtx: N->getLocationContext(),
2795 Ctx&: N->getState()->getStateManager().getContext());
2796
2797 if (!recovered.isUnknown()) {
2798 X = recovered;
2799 }
2800 }
2801 }
2802 }
2803
2804 // If the condition is still unknown, give up.
2805 if (X.isUnknownOrUndef())
2806 return std::nullopt;
2807
2808 DefinedSVal V = X.castAs<DefinedSVal>();
2809
2810 ProgramStateRef StTrue, StFalse;
2811 return State->assume(Cond: V);
2812}
2813
2814void ExprEngine::processBranch(
2815 const Stmt *Condition, NodeBuilderContext &BldCtx, ExplodedNode *Pred,
2816 ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF,
2817 std::optional<unsigned> IterationsCompletedInLoop) {
2818 assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
2819 "CXXBindTemporaryExprs are handled by processBindTemporary.");
2820 currBldrCtx = &BldCtx;
2821
2822 // Check for NULL conditions; e.g. "for(;;)"
2823 if (!Condition) {
2824 BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
2825 NullCondBldr.generateNode(State: Pred->getState(), branch: true, Pred);
2826 return;
2827 }
2828
2829 if (const auto *Ex = dyn_cast<Expr>(Val: Condition))
2830 Condition = Ex->IgnoreParens();
2831
2832 Condition = ResolveCondition(Condition, B: BldCtx.getBlock());
2833 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
2834 Condition->getBeginLoc(),
2835 "Error evaluating branch");
2836
2837 ExplodedNodeSet CheckersOutSet;
2838 getCheckerManager().runCheckersForBranchCondition(condition: Condition, Dst&: CheckersOutSet,
2839 Pred, Eng&: *this);
2840 // We generated only sinks.
2841 if (CheckersOutSet.empty())
2842 return;
2843
2844 BranchNodeBuilder Builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
2845 for (ExplodedNode *PredN : CheckersOutSet) {
2846 if (PredN->isSink())
2847 continue;
2848
2849 ProgramStateRef PrevState = PredN->getState();
2850
2851 ProgramStateRef StTrue = PrevState, StFalse = PrevState;
2852 if (const auto KnownCondValueAssumption = assumeCondition(Condition, N: PredN))
2853 std::tie(args&: StTrue, args&: StFalse) = *KnownCondValueAssumption;
2854
2855 if (StTrue && StFalse)
2856 assert(!isa<ObjCForCollectionStmt>(Condition));
2857
2858 // We want to ensure consistent behavior between `eagerly-assume=false`,
2859 // when the state split is always performed by the `assumeCondition()`
2860 // call within this function and `eagerly-assume=true` (the default), when
2861 // some conditions (comparison operators, unary negation) can trigger a
2862 // state split before this callback. There are some contrived corner cases
2863 // that behave differently with and without `eagerly-assume`, but I don't
2864 // know about an example that could plausibly appear in "real" code.
2865 bool BothFeasible =
2866 (StTrue && StFalse) ||
2867 didEagerlyAssumeBifurcateAt(State: PrevState, Ex: dyn_cast<Expr>(Val: Condition));
2868
2869 if (StTrue) {
2870 // In a loop, if both branches are feasible (i.e. the analyzer doesn't
2871 // understand the loop condition) and two iterations have already been
2872 // completed, then don't assume a third iteration because it is a
2873 // redundant execution path (unlikely to be different from earlier loop
2874 // exits) and can cause false positives if e.g. the loop iterates over a
2875 // two-element structure with an opaque condition.
2876 //
2877 // The iteration count "2" is hardcoded because it's the natural limit:
2878 // * the fact that the programmer wrote a loop (and not just an `if`)
2879 // implies that they thought that the loop body might be executed twice;
2880 // * however, there are situations where the programmer knows that there
2881 // are at most two iterations but writes a loop that appears to be
2882 // generic, because there is no special syntax for "loop with at most
2883 // two iterations". (This pattern is common in FFMPEG and appears in
2884 // many other projects as well.)
2885 bool CompletedTwoIterations = IterationsCompletedInLoop.value_or(u: 0) >= 2;
2886 bool SkipTrueBranch = BothFeasible && CompletedTwoIterations;
2887
2888 // FIXME: This "don't assume third iteration" heuristic partially
2889 // conflicts with the widen-loop analysis option (which is off by
2890 // default). If we intend to support and stabilize the loop widening,
2891 // we must ensure that it 'plays nicely' with this logic.
2892 if (!SkipTrueBranch || AMgr.options.ShouldWidenLoops) {
2893 Builder.generateNode(State: StTrue, branch: true, Pred: PredN);
2894 } else if (!AMgr.options.InlineFunctionsWithAmbiguousLoops) {
2895 // FIXME: There is an ancient and arbitrary heuristic in
2896 // `ExprEngine::processCFGBlockEntrance` which prevents all further
2897 // inlining of a function if it finds an execution path within that
2898 // function which reaches the `MaxBlockVisitOnPath` limit (a/k/a
2899 // `analyzer-max-loop`, by default four iterations in a loop). Adding
2900 // this "don't assume third iteration" logic significantly increased
2901 // the analysis runtime on some inputs because less functions were
2902 // arbitrarily excluded from being inlined, so more entry points used
2903 // up their full allocated budget. As a hacky compensation for this,
2904 // here we apply the "should not inline" mark in cases when the loop
2905 // could potentially reach the `MaxBlockVisitOnPath` limit without the
2906 // "don't assume third iteration" logic. This slightly overcompensates
2907 // (activates if the third iteration can be entered, and will not
2908 // recognize cases where the fourth iteration would't be completed), but
2909 // should be good enough for practical purposes.
2910 if (const LocationContext *LC = getInlinedLocationContext(Node: Pred, G)) {
2911 Engine.FunctionSummaries->markShouldNotInline(
2912 D: LC->getStackFrame()->getDecl());
2913 }
2914 }
2915 }
2916
2917 if (StFalse) {
2918 // In a loop, if both branches are feasible (i.e. the analyzer doesn't
2919 // understand the loop condition), we are before the first iteration and
2920 // the analyzer option `assume-at-least-one-iteration` is set to `true`,
2921 // then avoid creating the execution path where the loop is skipped.
2922 //
2923 // In some situations this "loop is skipped" execution path is an
2924 // important corner case that may evade the notice of the developer and
2925 // hide significant bugs -- however, there are also many situations where
2926 // it's guaranteed that at least one iteration will happen (e.g. some
2927 // data structure is always nonempty), but the analyzer cannot realize
2928 // this and will produce false positives when it assumes that the loop is
2929 // skipped.
2930 bool BeforeFirstIteration = IterationsCompletedInLoop == std::optional{0};
2931 bool SkipFalseBranch = BothFeasible && BeforeFirstIteration &&
2932 AMgr.options.ShouldAssumeAtLeastOneIteration;
2933 if (!SkipFalseBranch)
2934 Builder.generateNode(State: StFalse, branch: false, Pred: PredN);
2935 }
2936 }
2937 currBldrCtx = nullptr;
2938}
2939
2940/// The GDM component containing the set of global variables which have been
2941/// previously initialized with explicit initializers.
2942REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
2943 llvm::ImmutableSet<const VarDecl *>)
2944
2945void ExprEngine::processStaticInitializer(
2946 const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred,
2947 ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) {
2948 currBldrCtx = &BuilderCtx;
2949
2950 const auto *VD = cast<VarDecl>(Val: DS->getSingleDecl());
2951 ProgramStateRef state = Pred->getState();
2952 bool initHasRun = state->contains<InitializedGlobalsSet>(key: VD);
2953 BranchNodeBuilder Builder(Pred, Dst, BuilderCtx, DstT, DstF);
2954
2955 if (!initHasRun) {
2956 state = state->add<InitializedGlobalsSet>(K: VD);
2957 }
2958
2959 Builder.generateNode(State: state, branch: initHasRun, Pred);
2960
2961 currBldrCtx = nullptr;
2962}
2963
2964/// processIndirectGoto - Called by CoreEngine. Used to generate successor
2965/// nodes by processing the 'effects' of a computed goto jump.
2966void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
2967 ProgramStateRef state = builder.getState();
2968 SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
2969
2970 // Three possibilities:
2971 //
2972 // (1) We know the computed label.
2973 // (2) The label is NULL (or some other constant), or Undefined.
2974 // (3) We have no clue about the label. Dispatch to all targets.
2975 //
2976
2977 using iterator = IndirectGotoNodeBuilder::iterator;
2978
2979 if (std::optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
2980 const LabelDecl *L = LV->getLabel();
2981
2982 for (iterator Succ : builder) {
2983 if (Succ.getLabel() == L) {
2984 builder.generateNode(I: Succ, State: state);
2985 return;
2986 }
2987 }
2988
2989 llvm_unreachable("No block with label.");
2990 }
2991
2992 if (isa<UndefinedVal, loc::ConcreteInt>(Val: V)) {
2993 // Dispatch to the first target and mark it as a sink.
2994 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
2995 // FIXME: add checker visit.
2996 // UndefBranches.insert(N);
2997 return;
2998 }
2999
3000 // This is really a catch-all. We don't support symbolics yet.
3001 // FIXME: Implement dispatch for symbolic pointers.
3002
3003 for (iterator Succ : builder)
3004 builder.generateNode(I: Succ, State: state);
3005}
3006
3007void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
3008 ExplodedNode *Pred,
3009 ExplodedNodeSet &Dst,
3010 const BlockEdge &L) {
3011 SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
3012 getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, Eng&: *this);
3013}
3014
3015/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
3016/// nodes when the control reaches the end of a function.
3017void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
3018 ExplodedNode *Pred,
3019 const ReturnStmt *RS) {
3020 ProgramStateRef State = Pred->getState();
3021
3022 if (!Pred->getStackFrame()->inTopFrame())
3023 State = finishArgumentConstruction(
3024 State, Call: *getStateManager().getCallEventManager().getCaller(
3025 CalleeCtx: Pred->getStackFrame(), State: Pred->getState()));
3026
3027 // FIXME: We currently cannot assert that temporaries are clear, because
3028 // lifetime extended temporaries are not always modelled correctly. In some
3029 // cases when we materialize the temporary, we do
3030 // createTemporaryRegionIfNeeded(), and the region changes, and also the
3031 // respective destructor becomes automatic from temporary. So for now clean up
3032 // the state manually before asserting. Ideally, this braced block of code
3033 // should go away.
3034 {
3035 const LocationContext *FromLC = Pred->getLocationContext();
3036 const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
3037 const LocationContext *LC = FromLC;
3038 while (LC != ToLC) {
3039 assert(LC && "ToLC must be a parent of FromLC!");
3040 for (auto I : State->get<ObjectsUnderConstruction>())
3041 if (I.first.getLocationContext() == LC) {
3042 // The comment above only pardons us for not cleaning up a
3043 // temporary destructor. If any other statements are found here,
3044 // it must be a separate problem.
3045 assert(I.first.getItem().getKind() ==
3046 ConstructionContextItem::TemporaryDestructorKind ||
3047 I.first.getItem().getKind() ==
3048 ConstructionContextItem::ElidedDestructorKind);
3049 State = State->remove<ObjectsUnderConstruction>(K: I.first);
3050 }
3051 LC = LC->getParent();
3052 }
3053 }
3054
3055 // Perform the transition with cleanups.
3056 if (State != Pred->getState()) {
3057 ExplodedNodeSet PostCleanup;
3058 NodeBuilder Bldr(Pred, PostCleanup, BC);
3059 Pred = Bldr.generateNode(PP: Pred->getLocation(), State, Pred);
3060 if (!Pred) {
3061 // The node with clean temporaries already exists. We might have reached
3062 // it on a path on which we initialize different temporaries.
3063 return;
3064 }
3065 }
3066
3067 assert(areAllObjectsFullyConstructed(Pred->getState(),
3068 Pred->getLocationContext(),
3069 Pred->getStackFrame()->getParent()));
3070 ExplodedNodeSet Dst;
3071 if (Pred->getLocationContext()->inTopFrame()) {
3072 // Remove dead symbols.
3073 ExplodedNodeSet AfterRemovedDead;
3074 removeDeadOnEndOfFunction(BC, Pred, Dst&: AfterRemovedDead);
3075
3076 // Notify checkers.
3077 for (const auto I : AfterRemovedDead)
3078 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred: I, Eng&: *this, RS);
3079 } else {
3080 getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, Eng&: *this, RS);
3081 }
3082
3083 Engine.enqueueEndOfFunction(Set&: Dst, RS);
3084}
3085
3086/// ProcessSwitch - Called by CoreEngine. Used to generate successor
3087/// nodes by processing the 'effects' of a switch statement.
3088void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
3089 using iterator = SwitchNodeBuilder::iterator;
3090
3091 ProgramStateRef state = builder.getState();
3092 const Expr *CondE = builder.getCondition();
3093 SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
3094
3095 if (CondV_untested.isUndef()) {
3096 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
3097 // FIXME: add checker
3098 //UndefBranches.insert(N);
3099
3100 return;
3101 }
3102 DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
3103
3104 ProgramStateRef DefaultSt = state;
3105
3106 iterator I = builder.begin(), EI = builder.end();
3107 bool defaultIsFeasible = I == EI;
3108
3109 for ( ; I != EI; ++I) {
3110 // Successor may be pruned out during CFG construction.
3111 if (!I.getBlock())
3112 continue;
3113
3114 const CaseStmt *Case = I.getCase();
3115
3116 // Evaluate the LHS of the case value.
3117 llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(Ctx: getContext());
3118 assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
3119
3120 // Get the RHS of the case, if it exists.
3121 llvm::APSInt V2;
3122 if (const Expr *E = Case->getRHS())
3123 V2 = E->EvaluateKnownConstInt(Ctx: getContext());
3124 else
3125 V2 = V1;
3126
3127 ProgramStateRef StateCase;
3128 if (std::optional<NonLoc> NL = CondV.getAs<NonLoc>())
3129 std::tie(args&: StateCase, args&: DefaultSt) =
3130 DefaultSt->assumeInclusiveRange(Val: *NL, From: V1, To: V2);
3131 else // UnknownVal
3132 StateCase = DefaultSt;
3133
3134 if (StateCase)
3135 builder.generateCaseStmtNode(I, State: StateCase);
3136
3137 // Now "assume" that the case doesn't match. Add this state
3138 // to the default state (if it is feasible).
3139 if (DefaultSt)
3140 defaultIsFeasible = true;
3141 else {
3142 defaultIsFeasible = false;
3143 break;
3144 }
3145 }
3146
3147 if (!defaultIsFeasible)
3148 return;
3149
3150 // If we have switch(enum value), the default branch is not
3151 // feasible if all of the enum constants not covered by 'case:' statements
3152 // are not feasible values for the switch condition.
3153 //
3154 // Note that this isn't as accurate as it could be. Even if there isn't
3155 // a case for a particular enum value as long as that enum value isn't
3156 // feasible then it shouldn't be considered for making 'default:' reachable.
3157 const SwitchStmt *SS = builder.getSwitch();
3158 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
3159 if (CondExpr->getType()->getAs<EnumType>()) {
3160 if (SS->isAllEnumCasesCovered())
3161 return;
3162 }
3163
3164 builder.generateDefaultCaseNode(State: DefaultSt);
3165}
3166
3167//===----------------------------------------------------------------------===//
3168// Transfer functions: Loads and stores.
3169//===----------------------------------------------------------------------===//
3170
3171void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
3172 ExplodedNode *Pred,
3173 ExplodedNodeSet &Dst) {
3174 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3175
3176 ProgramStateRef state = Pred->getState();
3177 const LocationContext *LCtx = Pred->getLocationContext();
3178
3179 auto resolveAsLambdaCapturedVar =
3180 [&](const ValueDecl *VD) -> std::optional<std::pair<SVal, QualType>> {
3181 const auto *MD = dyn_cast<CXXMethodDecl>(Val: LCtx->getDecl());
3182 const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Val: Ex);
3183 if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
3184 DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
3185 MD->getParent()->isLambda()) {
3186 // Lookup the field of the lambda.
3187 const CXXRecordDecl *CXXRec = MD->getParent();
3188 llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;
3189 FieldDecl *LambdaThisCaptureField;
3190 CXXRec->getCaptureFields(Captures&: LambdaCaptureFields, ThisCapture&: LambdaThisCaptureField);
3191
3192 // Sema follows a sequence of complex rules to determine whether the
3193 // variable should be captured.
3194 if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
3195 Loc CXXThis = svalBuilder.getCXXThis(D: MD, SFC: LCtx->getStackFrame());
3196 SVal CXXThisVal = state->getSVal(LV: CXXThis);
3197 return std::make_pair(state->getLValue(decl: FD, Base: CXXThisVal), FD->getType());
3198 }
3199 }
3200
3201 return std::nullopt;
3202 };
3203
3204 if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
3205 // C permits "extern void v", and if you cast the address to a valid type,
3206 // you can even do things with it. We simply pretend
3207 assert(Ex->isGLValue() || VD->getType()->isVoidType());
3208 const LocationContext *LocCtxt = Pred->getLocationContext();
3209 std::optional<std::pair<SVal, QualType>> VInfo =
3210 resolveAsLambdaCapturedVar(VD);
3211
3212 if (!VInfo)
3213 VInfo = std::make_pair(state->getLValue(VD, LC: LocCtxt), VD->getType());
3214
3215 SVal V = VInfo->first;
3216 bool IsReference = VInfo->second->isReferenceType();
3217
3218 // For references, the 'lvalue' is the pointer address stored in the
3219 // reference region.
3220 if (IsReference) {
3221 if (const MemRegion *R = V.getAsRegion())
3222 V = state->getSVal(R);
3223 else
3224 V = UnknownVal();
3225 }
3226
3227 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
3228 ProgramPoint::PostLValueKind);
3229 return;
3230 }
3231 if (const auto *ED = dyn_cast<EnumConstantDecl>(Val: D)) {
3232 assert(!Ex->isGLValue());
3233 SVal V = svalBuilder.makeIntVal(integer: ED->getInitVal());
3234 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
3235 return;
3236 }
3237 if (const auto *FD = dyn_cast<FunctionDecl>(Val: D)) {
3238 SVal V = svalBuilder.getFunctionPointer(func: FD);
3239 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
3240 ProgramPoint::PostLValueKind);
3241 return;
3242 }
3243 if (isa<FieldDecl, IndirectFieldDecl>(Val: D)) {
3244 // Delegate all work related to pointer to members to the surrounding
3245 // operator&.
3246 return;
3247 }
3248 if (const auto *BD = dyn_cast<BindingDecl>(Val: D)) {
3249 // Handle structured bindings captured by lambda.
3250 if (std::optional<std::pair<SVal, QualType>> VInfo =
3251 resolveAsLambdaCapturedVar(BD)) {
3252 auto [V, T] = VInfo.value();
3253
3254 if (T->isReferenceType()) {
3255 if (const MemRegion *R = V.getAsRegion())
3256 V = state->getSVal(R);
3257 else
3258 V = UnknownVal();
3259 }
3260
3261 Bldr.generateNode(Ex, Pred, state->BindExpr(S: Ex, LCtx, V: V), nullptr,
3262 ProgramPoint::PostLValueKind);
3263 return;
3264 }
3265
3266 const auto *DD = cast<DecompositionDecl>(Val: BD->getDecomposedDecl());
3267
3268 SVal Base = state->getLValue(DD, LCtx);
3269 if (DD->getType()->isReferenceType()) {
3270 if (const MemRegion *R = Base.getAsRegion())
3271 Base = state->getSVal(R);
3272 else
3273 Base = UnknownVal();
3274 }
3275
3276 SVal V = UnknownVal();
3277
3278 // Handle binding to data members
3279 if (const auto *ME = dyn_cast<MemberExpr>(Val: BD->getBinding())) {
3280 const auto *Field = cast<FieldDecl>(Val: ME->getMemberDecl());
3281 V = state->getLValue(decl: Field, Base);
3282 }
3283 // Handle binding to arrays
3284 else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(Val: BD->getBinding())) {
3285 SVal Idx = state->getSVal(ASE->getIdx(), LCtx);
3286
3287 // Note: the index of an element in a structured binding is automatically
3288 // created and it is a unique identifier of the specific element. Thus it
3289 // cannot be a value that varies at runtime.
3290 assert(Idx.isConstant() && "BindingDecl array index is not a constant!");
3291
3292 V = state->getLValue(BD->getType(), Idx, Base);
3293 }
3294 // Handle binding to tuple-like structures
3295 else if (const auto *HV = BD->getHoldingVar()) {
3296 V = state->getLValue(VD: HV, LC: LCtx);
3297
3298 if (HV->getType()->isReferenceType()) {
3299 if (const MemRegion *R = V.getAsRegion())
3300 V = state->getSVal(R);
3301 else
3302 V = UnknownVal();
3303 }
3304 } else
3305 llvm_unreachable("An unknown case of structured binding encountered!");
3306
3307 // In case of tuple-like types the references are already handled, so we
3308 // don't want to handle them again.
3309 if (BD->getType()->isReferenceType() && !BD->getHoldingVar()) {
3310 if (const MemRegion *R = V.getAsRegion())
3311 V = state->getSVal(R);
3312 else
3313 V = UnknownVal();
3314 }
3315
3316 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
3317 ProgramPoint::PostLValueKind);
3318
3319 return;
3320 }
3321
3322 if (const auto *TPO = dyn_cast<TemplateParamObjectDecl>(Val: D)) {
3323 // FIXME: We should meaningfully implement this.
3324 (void)TPO;
3325 return;
3326 }
3327
3328 llvm_unreachable("Support for this Decl not implemented.");
3329}
3330
3331/// VisitArrayInitLoopExpr - Transfer function for array init loop.
3332void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex,
3333 ExplodedNode *Pred,
3334 ExplodedNodeSet &Dst) {
3335 ExplodedNodeSet CheckerPreStmt;
3336 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, Ex, *this);
3337
3338 ExplodedNodeSet EvalSet;
3339 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
3340
3341 const Expr *Arr = Ex->getCommonExpr()->getSourceExpr();
3342
3343 for (auto *Node : CheckerPreStmt) {
3344
3345 // The constructor visitior has already taken care of everything.
3346 if (isa<CXXConstructExpr>(Val: Ex->getSubExpr()))
3347 break;
3348
3349 const LocationContext *LCtx = Node->getLocationContext();
3350 ProgramStateRef state = Node->getState();
3351
3352 SVal Base = UnknownVal();
3353
3354 // As in case of this expression the sub-expressions are not visited by any
3355 // other transfer functions, they are handled by matching their AST.
3356
3357 // Case of implicit copy or move ctor of object with array member
3358 //
3359 // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the
3360 // environment.
3361 //
3362 // struct S {
3363 // int arr[2];
3364 // };
3365 //
3366 //
3367 // S a;
3368 // S b = a;
3369 //
3370 // The AST in case of a *copy constructor* looks like this:
3371 // ArrayInitLoopExpr
3372 // |-OpaqueValueExpr
3373 // | `-MemberExpr <-- match this
3374 // | `-DeclRefExpr
3375 // ` ...
3376 //
3377 //
3378 // S c;
3379 // S d = std::move(d);
3380 //
3381 // In case of a *move constructor* the resulting AST looks like:
3382 // ArrayInitLoopExpr
3383 // |-OpaqueValueExpr
3384 // | `-MemberExpr <-- match this first
3385 // | `-CXXStaticCastExpr <-- match this after
3386 // | `-DeclRefExpr
3387 // ` ...
3388 if (const auto *ME = dyn_cast<MemberExpr>(Val: Arr)) {
3389 Expr *MEBase = ME->getBase();
3390
3391 // Move ctor
3392 if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(Val: MEBase)) {
3393 MEBase = CXXSCE->getSubExpr();
3394 }
3395
3396 auto ObjDeclExpr = cast<DeclRefExpr>(Val: MEBase);
3397 SVal Obj = state->getLValue(VD: cast<VarDecl>(Val: ObjDeclExpr->getDecl()), LC: LCtx);
3398
3399 Base = state->getLValue(decl: cast<FieldDecl>(Val: ME->getMemberDecl()), Base: Obj);
3400 }
3401
3402 // Case of lambda capture and decomposition declaration
3403 //
3404 // int arr[2];
3405 //
3406 // [arr]{ int a = arr[0]; }();
3407 // auto[a, b] = arr;
3408 //
3409 // In both of these cases the AST looks like the following:
3410 // ArrayInitLoopExpr
3411 // |-OpaqueValueExpr
3412 // | `-DeclRefExpr <-- match this
3413 // ` ...
3414 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Val: Arr))
3415 Base = state->getLValue(VD: cast<VarDecl>(Val: DRE->getDecl()), LC: LCtx);
3416
3417 // Create a lazy compound value to the original array
3418 if (const MemRegion *R = Base.getAsRegion())
3419 Base = state->getSVal(R);
3420 else
3421 Base = UnknownVal();
3422
3423 Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, Base));
3424 }
3425
3426 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this);
3427}
3428
3429/// VisitArraySubscriptExpr - Transfer function for array accesses
3430void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
3431 ExplodedNode *Pred,
3432 ExplodedNodeSet &Dst){
3433 const Expr *Base = A->getBase()->IgnoreParens();
3434 const Expr *Idx = A->getIdx()->IgnoreParens();
3435
3436 ExplodedNodeSet CheckerPreStmt;
3437 getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
3438
3439 ExplodedNodeSet EvalSet;
3440 StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
3441
3442 bool IsVectorType = A->getBase()->getType()->isVectorType();
3443
3444 // The "like" case is for situations where C standard prohibits the type to
3445 // be an lvalue, e.g. taking the address of a subscript of an expression of
3446 // type "void *".
3447 bool IsGLValueLike = A->isGLValue() ||
3448 (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
3449
3450 for (auto *Node : CheckerPreStmt) {
3451 const LocationContext *LCtx = Node->getLocationContext();
3452 ProgramStateRef state = Node->getState();
3453
3454 if (IsGLValueLike) {
3455 QualType T = A->getType();
3456
3457 // One of the forbidden LValue types! We still need to have sensible
3458 // symbolic locations to represent this stuff. Note that arithmetic on
3459 // void pointers is a GCC extension.
3460 if (T->isVoidType())
3461 T = getContext().CharTy;
3462
3463 SVal V = state->getLValue(ElementType: T,
3464 Idx: state->getSVal(Idx, LCtx),
3465 Base: state->getSVal(Base, LCtx));
3466 Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
3467 ProgramPoint::PostLValueKind);
3468 } else if (IsVectorType) {
3469 // FIXME: non-glvalue vector reads are not modelled.
3470 Bldr.generateNode(A, Node, state, nullptr);
3471 } else {
3472 llvm_unreachable("Array subscript should be an lValue when not \
3473a vector and not a forbidden lvalue type");
3474 }
3475 }
3476
3477 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
3478}
3479
3480/// VisitMemberExpr - Transfer function for member expressions.
3481void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
3482 ExplodedNodeSet &Dst) {
3483 // FIXME: Prechecks eventually go in ::Visit().
3484 ExplodedNodeSet CheckedSet;
3485 getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
3486
3487 ExplodedNodeSet EvalSet;
3488 ValueDecl *Member = M->getMemberDecl();
3489
3490 // Handle static member variables and enum constants accessed via
3491 // member syntax.
3492 if (isa<VarDecl, EnumConstantDecl>(Val: Member)) {
3493 for (const auto I : CheckedSet)
3494 VisitCommonDeclRefExpr(M, Member, I, EvalSet);
3495 } else {
3496 StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
3497 ExplodedNodeSet Tmp;
3498
3499 for (const auto I : CheckedSet) {
3500 ProgramStateRef state = I->getState();
3501 const LocationContext *LCtx = I->getLocationContext();
3502 Expr *BaseExpr = M->getBase();
3503
3504 // Handle C++ method calls.
3505 if (const auto *MD = dyn_cast<CXXMethodDecl>(Val: Member)) {
3506 if (MD->isImplicitObjectMemberFunction())
3507 state = createTemporaryRegionIfNeeded(State: state, LC: LCtx, InitWithAdjustments: BaseExpr);
3508
3509 SVal MDVal = svalBuilder.getFunctionPointer(MD);
3510 state = state->BindExpr(M, LCtx, MDVal);
3511
3512 Bldr.generateNode(M, I, state);
3513 continue;
3514 }
3515
3516 // Handle regular struct fields / member variables.
3517 const SubRegion *MR = nullptr;
3518 state = createTemporaryRegionIfNeeded(State: state, LC: LCtx, InitWithAdjustments: BaseExpr,
3519 /*Result=*/nullptr,
3520 /*OutRegionWithAdjustments=*/&MR);
3521 SVal baseExprVal =
3522 MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);
3523
3524 // FIXME: Copied from RegionStoreManager::bind()
3525 if (const auto *SR =
3526 dyn_cast_or_null<SymbolicRegion>(baseExprVal.getAsRegion())) {
3527 QualType T = SR->getPointeeStaticType();
3528 baseExprVal =
3529 loc::MemRegionVal(getStoreManager().GetElementZeroRegion(R: SR, T));
3530 }
3531
3532 const auto *field = cast<FieldDecl>(Val: Member);
3533 SVal L = state->getLValue(decl: field, Base: baseExprVal);
3534
3535 if (M->isGLValue() || M->getType()->isArrayType()) {
3536 // We special-case rvalues of array type because the analyzer cannot
3537 // reason about them, since we expect all regions to be wrapped in Locs.
3538 // We instead treat these as lvalues and assume that they will decay to
3539 // pointers as soon as they are used.
3540 if (!M->isGLValue()) {
3541 assert(M->getType()->isArrayType());
3542 const auto *PE =
3543 dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
3544 if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
3545 llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
3546 }
3547 }
3548
3549 if (field->getType()->isReferenceType()) {
3550 if (const MemRegion *R = L.getAsRegion())
3551 L = state->getSVal(R);
3552 else
3553 L = UnknownVal();
3554 }
3555
3556 Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
3557 ProgramPoint::PostLValueKind);
3558 } else {
3559 Bldr.takeNodes(N: I);
3560 evalLoad(Tmp, M, M, I, state, L);
3561 Bldr.addNodes(S: Tmp);
3562 }
3563 }
3564 }
3565
3566 getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
3567}
3568
3569void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
3570 ExplodedNodeSet &Dst) {
3571 ExplodedNodeSet AfterPreSet;
3572 getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
3573
3574 // For now, treat all the arguments to C11 atomics as escaping.
3575 // FIXME: Ideally we should model the behavior of the atomics precisely here.
3576
3577 ExplodedNodeSet AfterInvalidateSet;
3578 StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
3579
3580 for (const auto I : AfterPreSet) {
3581 ProgramStateRef State = I->getState();
3582 const LocationContext *LCtx = I->getLocationContext();
3583
3584 SmallVector<SVal, 8> ValuesToInvalidate;
3585 for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
3586 const Expr *SubExpr = AE->getSubExprs()[SI];
3587 SVal SubExprVal = State->getSVal(SubExpr, LCtx);
3588 ValuesToInvalidate.push_back(Elt: SubExprVal);
3589 }
3590
3591 State = State->invalidateRegions(Values: ValuesToInvalidate, Elem: getCFGElementRef(),
3592 BlockCount: currBldrCtx->blockCount(), LCtx,
3593 /*CausedByPointerEscape*/ CausesPointerEscape: true,
3594 /*Symbols=*/IS: nullptr);
3595
3596 SVal ResultVal = UnknownVal();
3597 State = State->BindExpr(AE, LCtx, ResultVal);
3598 Bldr.generateNode(AE, I, State, nullptr,
3599 ProgramPoint::PostStmtKind);
3600 }
3601
3602 getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
3603}
3604
3605// A value escapes in four possible cases:
3606// (1) We are binding to something that is not a memory region.
3607// (2) We are binding to a MemRegion that does not have stack storage.
3608// (3) We are binding to a top-level parameter region with a non-trivial
3609// destructor. We won't see the destructor during analysis, but it's there.
3610// (4) We are binding to a MemRegion with stack storage that the store
3611// does not understand.
3612ProgramStateRef ExprEngine::processPointerEscapedOnBind(
3613 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
3614 const LocationContext *LCtx, PointerEscapeKind Kind,
3615 const CallEvent *Call) {
3616 SmallVector<SVal, 8> Escaped;
3617 for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
3618 // Cases (1) and (2).
3619 const MemRegion *MR = LocAndVal.first.getAsRegion();
3620 const MemSpaceRegion *Space = MR ? MR->getMemorySpace(State) : nullptr;
3621 if (!MR || !isa<StackSpaceRegion, StaticGlobalSpaceRegion>(Val: Space)) {
3622 Escaped.push_back(Elt: LocAndVal.second);
3623 continue;
3624 }
3625
3626 // Case (3).
3627 if (const auto *VR = dyn_cast<VarRegion>(Val: MR->getBaseRegion()))
3628 if (isa<StackArgumentsSpaceRegion>(Val: Space) &&
3629 VR->getStackFrame()->inTopFrame())
3630 if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
3631 if (!RD->hasTrivialDestructor()) {
3632 Escaped.push_back(Elt: LocAndVal.second);
3633 continue;
3634 }
3635
3636 // Case (4): in order to test that, generate a new state with the binding
3637 // added. If it is the same state, then it escapes (since the store cannot
3638 // represent the binding).
3639 // Do this only if we know that the store is not supposed to generate the
3640 // same state.
3641 SVal StoredVal = State->getSVal(R: MR);
3642 if (StoredVal != LocAndVal.second)
3643 if (State ==
3644 (State->bindLoc(location: loc::MemRegionVal(MR), V: LocAndVal.second, LCtx)))
3645 Escaped.push_back(Elt: LocAndVal.second);
3646 }
3647
3648 if (Escaped.empty())
3649 return State;
3650
3651 return escapeValues(State, Vs: Escaped, K: Kind, Call);
3652}
3653
3654ProgramStateRef
3655ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
3656 SVal Val, const LocationContext *LCtx) {
3657 std::pair<SVal, SVal> LocAndVal(Loc, Val);
3658 return processPointerEscapedOnBind(State, LocAndVals: LocAndVal, LCtx, Kind: PSK_EscapeOnBind,
3659 Call: nullptr);
3660}
3661
3662ProgramStateRef
3663ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
3664 const InvalidatedSymbols *Invalidated,
3665 ArrayRef<const MemRegion *> ExplicitRegions,
3666 const CallEvent *Call,
3667 RegionAndSymbolInvalidationTraits &ITraits) {
3668 if (!Invalidated || Invalidated->empty())
3669 return State;
3670
3671 if (!Call)
3672 return getCheckerManager().runCheckersForPointerEscape(State,
3673 Escaped: *Invalidated,
3674 Call: nullptr,
3675 Kind: PSK_EscapeOther,
3676 ITraits: &ITraits);
3677
3678 // If the symbols were invalidated by a call, we want to find out which ones
3679 // were invalidated directly due to being arguments to the call.
3680 InvalidatedSymbols SymbolsDirectlyInvalidated;
3681 for (const auto I : ExplicitRegions) {
3682 if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
3683 SymbolsDirectlyInvalidated.insert(V: R->getSymbol());
3684 }
3685
3686 InvalidatedSymbols SymbolsIndirectlyInvalidated;
3687 for (const auto &sym : *Invalidated) {
3688 if (SymbolsDirectlyInvalidated.count(V: sym))
3689 continue;
3690 SymbolsIndirectlyInvalidated.insert(V: sym);
3691 }
3692
3693 if (!SymbolsDirectlyInvalidated.empty())
3694 State = getCheckerManager().runCheckersForPointerEscape(State,
3695 Escaped: SymbolsDirectlyInvalidated, Call, Kind: PSK_DirectEscapeOnCall, ITraits: &ITraits);
3696
3697 // Notify about the symbols that get indirectly invalidated by the call.
3698 if (!SymbolsIndirectlyInvalidated.empty())
3699 State = getCheckerManager().runCheckersForPointerEscape(State,
3700 Escaped: SymbolsIndirectlyInvalidated, Call, Kind: PSK_IndirectEscapeOnCall, ITraits: &ITraits);
3701
3702 return State;
3703}
3704
3705/// evalBind - Handle the semantics of binding a value to a specific location.
3706/// This method is used by evalStore and (soon) VisitDeclStmt, and others.
3707void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
3708 ExplodedNode *Pred,
3709 SVal location, SVal Val,
3710 bool atDeclInit, const ProgramPoint *PP) {
3711 const LocationContext *LC = Pred->getLocationContext();
3712 PostStmt PS(StoreE, LC);
3713 if (!PP)
3714 PP = &PS;
3715
3716 // Do a previsit of the bind.
3717 ExplodedNodeSet CheckedSet;
3718 getCheckerManager().runCheckersForBind(Dst&: CheckedSet, Src: Pred, location, val: Val,
3719 S: StoreE, Eng&: *this, PP: *PP);
3720
3721 StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
3722
3723 // If the location is not a 'Loc', it will already be handled by
3724 // the checkers. There is nothing left to do.
3725 if (!isa<Loc>(Val: location)) {
3726 const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
3727 /*tag*/nullptr);
3728 ProgramStateRef state = Pred->getState();
3729 state = processPointerEscapedOnBind(State: state, Loc: location, Val, LCtx: LC);
3730 Bldr.generateNode(PP: L, State: state, Pred);
3731 return;
3732 }
3733
3734 for (const auto PredI : CheckedSet) {
3735 ProgramStateRef state = PredI->getState();
3736
3737 state = processPointerEscapedOnBind(State: state, Loc: location, Val, LCtx: LC);
3738
3739 // When binding the value, pass on the hint that this is a initialization.
3740 // For initializations, we do not need to inform clients of region
3741 // changes.
3742 state = state->bindLoc(location: location.castAs<Loc>(),
3743 V: Val, LCtx: LC, /* notifyChanges = */ !atDeclInit);
3744
3745 const MemRegion *LocReg = nullptr;
3746 if (std::optional<loc::MemRegionVal> LocRegVal =
3747 location.getAs<loc::MemRegionVal>()) {
3748 LocReg = LocRegVal->getRegion();
3749 }
3750
3751 const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
3752 Bldr.generateNode(PP: L, State: state, Pred: PredI);
3753 }
3754}
3755
3756/// evalStore - Handle the semantics of a store via an assignment.
3757/// @param Dst The node set to store generated state nodes
3758/// @param AssignE The assignment expression if the store happens in an
3759/// assignment.
3760/// @param LocationE The location expression that is stored to.
3761/// @param state The current simulation state
3762/// @param location The location to store the value
3763/// @param Val The value to be stored
3764void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
3765 const Expr *LocationE,
3766 ExplodedNode *Pred,
3767 ProgramStateRef state, SVal location, SVal Val,
3768 const ProgramPointTag *tag) {
3769 // Proceed with the store. We use AssignE as the anchor for the PostStore
3770 // ProgramPoint if it is non-NULL, and LocationE otherwise.
3771 const Expr *StoreE = AssignE ? AssignE : LocationE;
3772
3773 // Evaluate the location (checks for bad dereferences).
3774 ExplodedNodeSet Tmp;
3775 evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
3776
3777 if (Tmp.empty())
3778 return;
3779
3780 if (location.isUndef())
3781 return;
3782
3783 for (const auto I : Tmp)
3784 evalBind(Dst, StoreE, I, location, Val, false);
3785}
3786
3787void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
3788 const Expr *NodeEx,
3789 const Expr *BoundEx,
3790 ExplodedNode *Pred,
3791 ProgramStateRef state,
3792 SVal location,
3793 const ProgramPointTag *tag,
3794 QualType LoadTy) {
3795 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
3796 assert(NodeEx);
3797 assert(BoundEx);
3798 // Evaluate the location (checks for bad dereferences).
3799 ExplodedNodeSet Tmp;
3800 evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
3801 if (Tmp.empty())
3802 return;
3803
3804 StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
3805 if (location.isUndef())
3806 return;
3807
3808 // Proceed with the load.
3809 for (const auto I : Tmp) {
3810 state = I->getState();
3811 const LocationContext *LCtx = I->getLocationContext();
3812
3813 SVal V = UnknownVal();
3814 if (location.isValid()) {
3815 if (LoadTy.isNull())
3816 LoadTy = BoundEx->getType();
3817 V = state->getSVal(LV: location.castAs<Loc>(), T: LoadTy);
3818 }
3819
3820 Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
3821 ProgramPoint::PostLoadKind);
3822 }
3823}
3824
3825void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
3826 const Stmt *NodeEx,
3827 const Stmt *BoundEx,
3828 ExplodedNode *Pred,
3829 ProgramStateRef state,
3830 SVal location,
3831 bool isLoad) {
3832 StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
3833 // Early checks for performance reason.
3834 if (location.isUnknown()) {
3835 return;
3836 }
3837
3838 ExplodedNodeSet Src;
3839 BldrTop.takeNodes(N: Pred);
3840 StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
3841 if (Pred->getState() != state) {
3842 // Associate this new state with an ExplodedNode.
3843 // FIXME: If I pass null tag, the graph is incorrect, e.g for
3844 // int *p;
3845 // p = 0;
3846 // *p = 0xDEADBEEF;
3847 // "p = 0" is not noted as "Null pointer value stored to 'p'" but
3848 // instead "int *p" is noted as
3849 // "Variable 'p' initialized to a null pointer value"
3850
3851 static SimpleProgramPointTag tag(TagProviderName, "Location");
3852 Bldr.generateNode(S: NodeEx, Pred, St: state, tag: &tag);
3853 }
3854 ExplodedNodeSet Tmp;
3855 getCheckerManager().runCheckersForLocation(Dst&: Tmp, Src, location, isLoad,
3856 NodeEx, BoundEx, Eng&: *this);
3857 BldrTop.addNodes(S: Tmp);
3858}
3859
3860std::pair<const ProgramPointTag *, const ProgramPointTag *>
3861ExprEngine::getEagerlyAssumeBifurcationTags() {
3862 static SimpleProgramPointTag TrueTag(TagProviderName, "Eagerly Assume True"),
3863 FalseTag(TagProviderName, "Eagerly Assume False");
3864
3865 return std::make_pair(x: &TrueTag, y: &FalseTag);
3866}
3867
3868/// If the last EagerlyAssume attempt was successful (i.e. the true and false
3869/// cases were both feasible), this state trait stores the expression where it
3870/// happened; otherwise this holds nullptr.
3871REGISTER_TRAIT_WITH_PROGRAMSTATE(LastEagerlyAssumeExprIfSuccessful,
3872 const Expr *)
3873
3874void ExprEngine::evalEagerlyAssumeBifurcation(ExplodedNodeSet &Dst,
3875 ExplodedNodeSet &Src,
3876 const Expr *Ex) {
3877 StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
3878
3879 for (ExplodedNode *Pred : Src) {
3880 // Test if the previous node was as the same expression. This can happen
3881 // when the expression fails to evaluate to anything meaningful and
3882 // (as an optimization) we don't generate a node.
3883 ProgramPoint P = Pred->getLocation();
3884 if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
3885 continue;
3886 }
3887
3888 ProgramStateRef State = Pred->getState();
3889 State = State->set<LastEagerlyAssumeExprIfSuccessful>(nullptr);
3890 SVal V = State->getSVal(Ex, Pred->getLocationContext());
3891 std::optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
3892 if (SEV && SEV->isExpression()) {
3893 const auto &[TrueTag, FalseTag] = getEagerlyAssumeBifurcationTags();
3894
3895 auto [StateTrue, StateFalse] = State->assume(Cond: *SEV);
3896
3897 if (StateTrue && StateFalse) {
3898 StateTrue = StateTrue->set<LastEagerlyAssumeExprIfSuccessful>(Ex);
3899 StateFalse = StateFalse->set<LastEagerlyAssumeExprIfSuccessful>(Ex);
3900 }
3901
3902 // First assume that the condition is true.
3903 if (StateTrue) {
3904 SVal Val = svalBuilder.makeIntVal(integer: 1U, type: Ex->getType());
3905 StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
3906 Bldr.generateNode(Ex, Pred, StateTrue, TrueTag);
3907 }
3908
3909 // Next, assume that the condition is false.
3910 if (StateFalse) {
3911 SVal Val = svalBuilder.makeIntVal(integer: 0U, type: Ex->getType());
3912 StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
3913 Bldr.generateNode(Ex, Pred, StateFalse, FalseTag);
3914 }
3915 }
3916 }
3917}
3918
3919bool ExprEngine::didEagerlyAssumeBifurcateAt(ProgramStateRef State,
3920 const Expr *Ex) const {
3921 return Ex && State->get<LastEagerlyAssumeExprIfSuccessful>() == Ex;
3922}
3923
3924void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
3925 ExplodedNodeSet &Dst) {
3926 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3927 // We have processed both the inputs and the outputs. All of the outputs
3928 // should evaluate to Locs. Nuke all of their values.
3929
3930 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3931 // which interprets the inline asm and stores proper results in the
3932 // outputs.
3933
3934 ProgramStateRef state = Pred->getState();
3935
3936 for (const Expr *O : A->outputs()) {
3937 SVal X = state->getSVal(O, Pred->getLocationContext());
3938 assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
3939
3940 if (std::optional<Loc> LV = X.getAs<Loc>())
3941 state = state->invalidateRegions(*LV, getCFGElementRef(),
3942 currBldrCtx->blockCount(),
3943 Pred->getLocationContext(),
3944 /*CausedByPointerEscape=*/true);
3945 }
3946
3947 // Do not reason about locations passed inside inline assembly.
3948 for (const Expr *I : A->inputs()) {
3949 SVal X = state->getSVal(I, Pred->getLocationContext());
3950
3951 if (std::optional<Loc> LV = X.getAs<Loc>())
3952 state = state->invalidateRegions(*LV, getCFGElementRef(),
3953 currBldrCtx->blockCount(),
3954 Pred->getLocationContext(),
3955 /*CausedByPointerEscape=*/true);
3956 }
3957
3958 Bldr.generateNode(S: A, Pred, St: state);
3959}
3960
3961void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
3962 ExplodedNodeSet &Dst) {
3963 StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3964 Bldr.generateNode(S: A, Pred, St: Pred->getState());
3965}
3966
3967//===----------------------------------------------------------------------===//
3968// Visualization.
3969//===----------------------------------------------------------------------===//
3970
3971namespace llvm {
3972
3973template<>
3974struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
3975 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
3976
3977 static bool nodeHasBugReport(const ExplodedNode *N) {
3978 BugReporter &BR = static_cast<ExprEngine &>(
3979 N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3980
3981 for (const auto &Class : BR.equivalenceClasses()) {
3982 for (const auto &Report : Class.getReports()) {
3983 const auto *PR = dyn_cast<PathSensitiveBugReport>(Val: Report.get());
3984 if (!PR)
3985 continue;
3986 const ExplodedNode *EN = PR->getErrorNode();
3987 if (EN->getState() == N->getState() &&
3988 EN->getLocation() == N->getLocation())
3989 return true;
3990 }
3991 }
3992 return false;
3993 }
3994
3995 /// \p PreCallback: callback before break.
3996 /// \p PostCallback: callback after break.
3997 /// \p Stop: stop iteration if returns @c true
3998 /// \return Whether @c Stop ever returned @c true.
3999 static bool traverseHiddenNodes(
4000 const ExplodedNode *N,
4001 llvm::function_ref<void(const ExplodedNode *)> PreCallback,
4002 llvm::function_ref<void(const ExplodedNode *)> PostCallback,
4003 llvm::function_ref<bool(const ExplodedNode *)> Stop) {
4004 while (true) {
4005 PreCallback(N);
4006 if (Stop(N))
4007 return true;
4008
4009 if (N->succ_size() != 1 || !isNodeHidden(N: N->getFirstSucc(), G: nullptr))
4010 break;
4011 PostCallback(N);
4012
4013 N = N->getFirstSucc();
4014 }
4015 return false;
4016 }
4017
4018 static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) {
4019 return N->isTrivial();
4020 }
4021
4022 static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
4023 std::string Buf;
4024 llvm::raw_string_ostream Out(Buf);
4025
4026 const bool IsDot = true;
4027 const unsigned int Space = 1;
4028 ProgramStateRef State = N->getState();
4029
4030 Out << "{ \"state_id\": " << State->getID()
4031 << ",\\l";
4032
4033 Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
4034
4035 // Dump program point for all the previously skipped nodes.
4036 traverseHiddenNodes(
4037 N,
4038 PreCallback: [&](const ExplodedNode *OtherNode) {
4039 Indent(Out, Space: Space + 1, IsDot) << "{ ";
4040 OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
4041 Out << ", \"tag\": ";
4042 if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
4043 Out << '\"' << Tag->getDebugTag() << '\"';
4044 else
4045 Out << "null";
4046 Out << ", \"node_id\": " << OtherNode->getID() <<
4047 ", \"is_sink\": " << OtherNode->isSink() <<
4048 ", \"has_report\": " << nodeHasBugReport(N: OtherNode) << " }";
4049 },
4050 // Adds a comma and a new-line between each program point.
4051 PostCallback: [&](const ExplodedNode *) { Out << ",\\l"; },
4052 Stop: [&](const ExplodedNode *) { return false; });
4053
4054 Out << "\\l"; // Adds a new-line to the last program point.
4055 Indent(Out, Space, IsDot) << "],\\l";
4056
4057 State->printDOT(Out, LCtx: N->getLocationContext(), Space);
4058
4059 Out << "\\l}\\l";
4060 return Buf;
4061 }
4062};
4063
4064} // namespace llvm
4065
4066void ExprEngine::ViewGraph(bool trim) {
4067 std::string Filename = DumpGraph(trim);
4068 llvm::DisplayGraph(Filename, wait: false, program: llvm::GraphProgram::DOT);
4069}
4070
4071void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) {
4072 std::string Filename = DumpGraph(Nodes);
4073 llvm::DisplayGraph(Filename, wait: false, program: llvm::GraphProgram::DOT);
4074}
4075
4076std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
4077 if (trim) {
4078 std::vector<const ExplodedNode *> Src;
4079
4080 // Iterate through the reports and get their nodes.
4081 for (const auto &Class : BR.equivalenceClasses()) {
4082 const auto *R =
4083 dyn_cast<PathSensitiveBugReport>(Val: Class.getReports()[0].get());
4084 if (!R)
4085 continue;
4086 const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
4087 Src.push_back(x: N);
4088 }
4089 return DumpGraph(Nodes: Src, Filename);
4090 }
4091
4092 return llvm::WriteGraph(G: &G, Name: "ExprEngine", /*ShortNames=*/false,
4093 /*Title=*/"Exploded Graph",
4094 /*Filename=*/std::string(Filename));
4095}
4096
4097std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes,
4098 StringRef Filename) {
4099 std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
4100
4101 if (!TrimmedG) {
4102 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
4103 return "";
4104 }
4105
4106 return llvm::WriteGraph(G: TrimmedG.get(), Name: "TrimmedExprEngine",
4107 /*ShortNames=*/false,
4108 /*Title=*/"Trimmed Exploded Graph",
4109 /*Filename=*/std::string(Filename));
4110}
4111
4112void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
4113 static int index = 0;
4114 return &index;
4115}
4116
4117void ExprEngine::anchor() { }
4118

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of clang/lib/StaticAnalyzer/Core/ExprEngine.cpp