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

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