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