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