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