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