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