1//===- ExprEngine.h - Path-Sensitive Expression-Level Dataflow --*- C++ -*-===//
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#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
16#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
17
18#include "clang/AST/Expr.h"
19#include "clang/AST/Type.h"
20#include "clang/Analysis/CFG.h"
21#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
22#include "clang/Analysis/ProgramPoint.h"
23#include "clang/Basic/LLVM.h"
24#include "clang/StaticAnalyzer/Core/CheckerManager.h"
25#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
26#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h"
27#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
28#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
29#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
31#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
32#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
33#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
34#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
35#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
36#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
37#include "llvm/ADT/ArrayRef.h"
38#include <cassert>
39#include <optional>
40#include <utility>
41
42namespace clang {
43
44class AnalysisDeclContextManager;
45class AnalyzerOptions;
46class ASTContext;
47class CFGBlock;
48class CFGElement;
49class ConstructionContext;
50class CXXBindTemporaryExpr;
51class CXXCatchStmt;
52class CXXConstructExpr;
53class CXXDeleteExpr;
54class CXXNewExpr;
55class CXXThisExpr;
56class Decl;
57class DeclStmt;
58class GCCAsmStmt;
59class LambdaExpr;
60class LocationContext;
61class MaterializeTemporaryExpr;
62class MSAsmStmt;
63class NamedDecl;
64class ObjCAtSynchronizedStmt;
65class ObjCForCollectionStmt;
66class ObjCIvarRefExpr;
67class ObjCMessageExpr;
68class ReturnStmt;
69class Stmt;
70
71namespace cross_tu {
72
73class CrossTranslationUnitContext;
74
75} // namespace cross_tu
76
77namespace ento {
78
79class AnalysisManager;
80class BasicValueFactory;
81class CallEvent;
82class CheckerManager;
83class ConstraintManager;
84class ExplodedNodeSet;
85class ExplodedNode;
86class IndirectGotoNodeBuilder;
87class MemRegion;
88class NodeBuilderContext;
89class NodeBuilderWithSinks;
90class ProgramState;
91class ProgramStateManager;
92class RegionAndSymbolInvalidationTraits;
93class SymbolManager;
94class SwitchNodeBuilder;
95
96/// Hints for figuring out of a call should be inlined during evalCall().
97struct EvalCallOptions {
98 /// This call is a constructor or a destructor for which we do not currently
99 /// compute the this-region correctly.
100 bool IsCtorOrDtorWithImproperlyModeledTargetRegion = false;
101
102 /// This call is a constructor or a destructor for a single element within
103 /// an array, a part of array construction or destruction.
104 bool IsArrayCtorOrDtor = false;
105
106 /// This call is a constructor or a destructor of a temporary value.
107 bool IsTemporaryCtorOrDtor = false;
108
109 /// This call is a constructor for a temporary that is lifetime-extended
110 /// by binding it to a reference-type field within an aggregate,
111 /// for example 'A { const C &c; }; A a = { C() };'
112 bool IsTemporaryLifetimeExtendedViaAggregate = false;
113
114 /// This call is a pre-C++17 elidable constructor that we failed to elide
115 /// because we failed to compute the target region into which
116 /// this constructor would have been ultimately elided. Analysis that
117 /// we perform in this case is still correct but it behaves differently,
118 /// as if copy elision is disabled.
119 bool IsElidableCtorThatHasNotBeenElided = false;
120
121 EvalCallOptions() {}
122};
123
124class ExprEngine {
125 void anchor();
126
127public:
128 /// The modes of inlining, which override the default analysis-wide settings.
129 enum InliningModes {
130 /// Follow the default settings for inlining callees.
131 Inline_Regular = 0,
132
133 /// Do minimal inlining of callees.
134 Inline_Minimal = 0x1
135 };
136
137private:
138 cross_tu::CrossTranslationUnitContext &CTU;
139 bool IsCTUEnabled;
140
141 AnalysisManager &AMgr;
142
143 AnalysisDeclContextManager &AnalysisDeclContexts;
144
145 CoreEngine Engine;
146
147 /// G - the simulation graph.
148 ExplodedGraph &G;
149
150 /// StateMgr - Object that manages the data for all created states.
151 ProgramStateManager StateMgr;
152
153 /// SymMgr - Object that manages the symbol information.
154 SymbolManager &SymMgr;
155
156 /// MRMgr - MemRegionManager object that creates memory regions.
157 MemRegionManager &MRMgr;
158
159 /// svalBuilder - SValBuilder object that creates SVals from expressions.
160 SValBuilder &svalBuilder;
161
162 unsigned int currStmtIdx = 0;
163 const NodeBuilderContext *currBldrCtx = nullptr;
164
165 /// Helper object to determine if an Objective-C message expression
166 /// implicitly never returns.
167 ObjCNoReturn ObjCNoRet;
168
169 /// The BugReporter associated with this engine. It is important that
170 /// this object be placed at the very end of member variables so that its
171 /// destructor is called before the rest of the ExprEngine is destroyed.
172 PathSensitiveBugReporter BR;
173
174 /// The functions which have been analyzed through inlining. This is owned by
175 /// AnalysisConsumer. It can be null.
176 SetOfConstDecls *VisitedCallees;
177
178 /// The flag, which specifies the mode of inlining for the engine.
179 InliningModes HowToInline;
180
181public:
182 ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, AnalysisManager &mgr,
183 SetOfConstDecls *VisitedCalleesIn,
184 FunctionSummariesTy *FS, InliningModes HowToInlineIn);
185
186 virtual ~ExprEngine() = default;
187
188 /// Returns true if there is still simulation state on the worklist.
189 bool ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
190 assert(L->inTopFrame());
191 BR.setAnalysisEntryPoint(L->getDecl());
192 return Engine.ExecuteWorkList(L, Steps, InitState: nullptr);
193 }
194
195 /// getContext - Return the ASTContext associated with this analysis.
196 ASTContext &getContext() const { return AMgr.getASTContext(); }
197
198 AnalysisManager &getAnalysisManager() { return AMgr; }
199
200 AnalysisDeclContextManager &getAnalysisDeclContextManager() {
201 return AMgr.getAnalysisDeclContextManager();
202 }
203
204 CheckerManager &getCheckerManager() const {
205 return *AMgr.getCheckerManager();
206 }
207
208 SValBuilder &getSValBuilder() { return svalBuilder; }
209
210 BugReporter &getBugReporter() { return BR; }
211
212 cross_tu::CrossTranslationUnitContext *
213 getCrossTranslationUnitContext() {
214 return &CTU;
215 }
216
217 const NodeBuilderContext &getBuilderContext() {
218 assert(currBldrCtx);
219 return *currBldrCtx;
220 }
221
222 const Stmt *getStmt() const;
223
224 const LocationContext *getRootLocationContext() const {
225 assert(G.roots_begin() != G.roots_end());
226 return (*G.roots_begin())->getLocation().getLocationContext();
227 }
228
229 CFGBlock::ConstCFGElementRef getCFGElementRef() const {
230 const CFGBlock *blockPtr = currBldrCtx ? currBldrCtx->getBlock() : nullptr;
231 return {blockPtr, currStmtIdx};
232 }
233
234 /// Dump graph to the specified filename.
235 /// If filename is empty, generate a temporary one.
236 /// \return The filename the graph is written into.
237 std::string DumpGraph(bool trim = false, StringRef Filename="");
238
239 /// Dump the graph consisting of the given nodes to a specified filename.
240 /// Generate a temporary filename if it's not provided.
241 /// \return The filename the graph is written into.
242 std::string DumpGraph(ArrayRef<const ExplodedNode *> Nodes,
243 StringRef Filename = "");
244
245 /// Visualize the ExplodedGraph created by executing the simulation.
246 void ViewGraph(bool trim = false);
247
248 /// Visualize a trimmed ExplodedGraph that only contains paths to the given
249 /// nodes.
250 void ViewGraph(ArrayRef<const ExplodedNode *> Nodes);
251
252 /// getInitialState - Return the initial state used for the root vertex
253 /// in the ExplodedGraph.
254 ProgramStateRef getInitialState(const LocationContext *InitLoc);
255
256 ExplodedGraph &getGraph() { return G; }
257 const ExplodedGraph &getGraph() const { return G; }
258
259 /// Run the analyzer's garbage collection - remove dead symbols and
260 /// bindings from the state.
261 ///
262 /// Checkers can participate in this process with two callbacks:
263 /// \c checkLiveSymbols and \c checkDeadSymbols. See the CheckerDocumentation
264 /// class for more information.
265 ///
266 /// \param Node The predecessor node, from which the processing should start.
267 /// \param Out The returned set of output nodes.
268 /// \param ReferenceStmt The statement which is about to be processed.
269 /// Everything needed for this statement should be considered live.
270 /// A null statement means that everything in child LocationContexts
271 /// is dead.
272 /// \param LC The location context of the \p ReferenceStmt. A null location
273 /// context means that we have reached the end of analysis and that
274 /// all statements and local variables should be considered dead.
275 /// \param DiagnosticStmt Used as a location for any warnings that should
276 /// occur while removing the dead (e.g. leaks). By default, the
277 /// \p ReferenceStmt is used.
278 /// \param K Denotes whether this is a pre- or post-statement purge. This
279 /// must only be ProgramPoint::PostStmtPurgeDeadSymbolsKind if an
280 /// entire location context is being cleared, in which case the
281 /// \p ReferenceStmt must either be a ReturnStmt or \c NULL. Otherwise,
282 /// it must be ProgramPoint::PreStmtPurgeDeadSymbolsKind (the default)
283 /// and \p ReferenceStmt must be valid (non-null).
284 void removeDead(ExplodedNode *Node, ExplodedNodeSet &Out,
285 const Stmt *ReferenceStmt, const LocationContext *LC,
286 const Stmt *DiagnosticStmt = nullptr,
287 ProgramPoint::Kind K = ProgramPoint::PreStmtPurgeDeadSymbolsKind);
288
289 /// processCFGElement - Called by CoreEngine. Used to generate new successor
290 /// nodes by processing the 'effects' of a CFG element.
291 void processCFGElement(const CFGElement E, ExplodedNode *Pred,
292 unsigned StmtIdx, NodeBuilderContext *Ctx);
293
294 void ProcessStmt(const Stmt *S, ExplodedNode *Pred);
295
296 void ProcessLoopExit(const Stmt* S, ExplodedNode *Pred);
297
298 void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred);
299
300 void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
301
302 void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred);
303
304 void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
305 ExplodedNode *Pred, ExplodedNodeSet &Dst);
306 void ProcessDeleteDtor(const CFGDeleteDtor D,
307 ExplodedNode *Pred, ExplodedNodeSet &Dst);
308 void ProcessBaseDtor(const CFGBaseDtor D,
309 ExplodedNode *Pred, ExplodedNodeSet &Dst);
310 void ProcessMemberDtor(const CFGMemberDtor D,
311 ExplodedNode *Pred, ExplodedNodeSet &Dst);
312 void ProcessTemporaryDtor(const CFGTemporaryDtor D,
313 ExplodedNode *Pred, ExplodedNodeSet &Dst);
314
315 /// Called by CoreEngine when processing the entrance of a CFGBlock.
316 void processCFGBlockEntrance(const BlockEdge &L,
317 NodeBuilderWithSinks &nodeBuilder,
318 ExplodedNode *Pred);
319
320 /// ProcessBranch - Called by CoreEngine. Used to generate successor
321 /// nodes by processing the 'effects' of a branch condition.
322 void processBranch(const Stmt *Condition,
323 NodeBuilderContext& BuilderCtx,
324 ExplodedNode *Pred,
325 ExplodedNodeSet &Dst,
326 const CFGBlock *DstT,
327 const CFGBlock *DstF);
328
329 /// Called by CoreEngine.
330 /// Used to generate successor nodes for temporary destructors depending
331 /// on whether the corresponding constructor was visited.
332 void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
333 NodeBuilderContext &BldCtx,
334 ExplodedNode *Pred, ExplodedNodeSet &Dst,
335 const CFGBlock *DstT,
336 const CFGBlock *DstF);
337
338 /// Called by CoreEngine. Used to processing branching behavior
339 /// at static initializers.
340 void processStaticInitializer(const DeclStmt *DS,
341 NodeBuilderContext& BuilderCtx,
342 ExplodedNode *Pred,
343 ExplodedNodeSet &Dst,
344 const CFGBlock *DstT,
345 const CFGBlock *DstF);
346
347 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
348 /// nodes by processing the 'effects' of a computed goto jump.
349 void processIndirectGoto(IndirectGotoNodeBuilder& builder);
350
351 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
352 /// nodes by processing the 'effects' of a switch statement.
353 void processSwitch(SwitchNodeBuilder& builder);
354
355 /// Called by CoreEngine. Used to notify checkers that processing a
356 /// function has begun. Called for both inlined and top-level functions.
357 void processBeginOfFunction(NodeBuilderContext &BC,
358 ExplodedNode *Pred, ExplodedNodeSet &Dst,
359 const BlockEdge &L);
360
361 /// Called by CoreEngine. Used to notify checkers that processing a
362 /// function has ended. Called for both inlined and top-level functions.
363 void processEndOfFunction(NodeBuilderContext& BC,
364 ExplodedNode *Pred,
365 const ReturnStmt *RS = nullptr);
366
367 /// Remove dead bindings/symbols before exiting a function.
368 void removeDeadOnEndOfFunction(NodeBuilderContext& BC,
369 ExplodedNode *Pred,
370 ExplodedNodeSet &Dst);
371
372 /// Generate the entry node of the callee.
373 void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
374 ExplodedNode *Pred);
375
376 /// Generate the sequence of nodes that simulate the call exit and the post
377 /// visit for CallExpr.
378 void processCallExit(ExplodedNode *Pred);
379
380 /// Called by CoreEngine when the analysis worklist has terminated.
381 void processEndWorklist();
382
383 /// evalAssume - Callback function invoked by the ConstraintManager when
384 /// making assumptions about state values.
385 ProgramStateRef processAssume(ProgramStateRef state, SVal cond,
386 bool assumption);
387
388 /// processRegionChanges - Called by ProgramStateManager whenever a change is made
389 /// to the store. Used to update checkers that track region values.
390 ProgramStateRef
391 processRegionChanges(ProgramStateRef state,
392 const InvalidatedSymbols *invalidated,
393 ArrayRef<const MemRegion *> ExplicitRegions,
394 ArrayRef<const MemRegion *> Regions,
395 const LocationContext *LCtx,
396 const CallEvent *Call);
397
398 inline ProgramStateRef
399 processRegionChange(ProgramStateRef state,
400 const MemRegion* MR,
401 const LocationContext *LCtx) {
402 return processRegionChanges(state, invalidated: nullptr, ExplicitRegions: MR, Regions: MR, LCtx, Call: nullptr);
403 }
404
405 /// printJson - Called by ProgramStateManager to print checker-specific data.
406 void printJson(raw_ostream &Out, ProgramStateRef State,
407 const LocationContext *LCtx, const char *NL,
408 unsigned int Space, bool IsDot) const;
409
410 ProgramStateManager &getStateManager() { return StateMgr; }
411
412 StoreManager &getStoreManager() { return StateMgr.getStoreManager(); }
413
414 ConstraintManager &getConstraintManager() {
415 return StateMgr.getConstraintManager();
416 }
417
418 // FIXME: Remove when we migrate over to just using SValBuilder.
419 BasicValueFactory &getBasicVals() {
420 return StateMgr.getBasicVals();
421 }
422
423 SymbolManager &getSymbolManager() { return SymMgr; }
424 MemRegionManager &getRegionManager() { return MRMgr; }
425
426 DataTag::Factory &getDataTags() { return Engine.getDataTags(); }
427
428 // Functions for external checking of whether we have unfinished work
429 bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
430 bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
431 bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
432
433 const CoreEngine &getCoreEngine() const { return Engine; }
434
435public:
436 /// Visit - Transfer function logic for all statements. Dispatches to
437 /// other functions that handle specific kinds of statements.
438 void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst);
439
440 /// VisitArrayInitLoopExpr - Transfer function for array init loop.
441 void VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex, ExplodedNode *Pred,
442 ExplodedNodeSet &Dst);
443
444 /// VisitArraySubscriptExpr - Transfer function for array accesses.
445 void VisitArraySubscriptExpr(const ArraySubscriptExpr *Ex,
446 ExplodedNode *Pred,
447 ExplodedNodeSet &Dst);
448
449 /// VisitGCCAsmStmt - Transfer function logic for inline asm.
450 void VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
451 ExplodedNodeSet &Dst);
452
453 /// VisitMSAsmStmt - Transfer function logic for MS inline asm.
454 void VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
455 ExplodedNodeSet &Dst);
456
457 /// VisitBlockExpr - Transfer function logic for BlockExprs.
458 void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
459 ExplodedNodeSet &Dst);
460
461 /// VisitLambdaExpr - Transfer function logic for LambdaExprs.
462 void VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred,
463 ExplodedNodeSet &Dst);
464
465 /// VisitBinaryOperator - Transfer function logic for binary operators.
466 void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred,
467 ExplodedNodeSet &Dst);
468
469
470 /// VisitCall - Transfer function for function calls.
471 void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
472 ExplodedNodeSet &Dst);
473
474 /// VisitCast - Transfer function logic for all casts (implicit and explicit).
475 void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
476 ExplodedNodeSet &Dst);
477
478 /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
479 void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
480 ExplodedNode *Pred, ExplodedNodeSet &Dst);
481
482 /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
483 void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D,
484 ExplodedNode *Pred, ExplodedNodeSet &Dst);
485
486 /// VisitDeclStmt - Transfer function logic for DeclStmts.
487 void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
488 ExplodedNodeSet &Dst);
489
490 /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
491 void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R,
492 ExplodedNode *Pred, ExplodedNodeSet &Dst);
493
494 void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred,
495 ExplodedNodeSet &Dst);
496
497 /// VisitLogicalExpr - Transfer function logic for '&&', '||'
498 void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
499 ExplodedNodeSet &Dst);
500
501 /// VisitMemberExpr - Transfer function for member expressions.
502 void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
503 ExplodedNodeSet &Dst);
504
505 /// VisitAtomicExpr - Transfer function for builtin atomic expressions
506 void VisitAtomicExpr(const AtomicExpr *E, ExplodedNode *Pred,
507 ExplodedNodeSet &Dst);
508
509 /// Transfer function logic for ObjCAtSynchronizedStmts.
510 void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
511 ExplodedNode *Pred, ExplodedNodeSet &Dst);
512
513 /// Transfer function logic for computing the lvalue of an Objective-C ivar.
514 void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
515 ExplodedNodeSet &Dst);
516
517 /// VisitObjCForCollectionStmt - Transfer function logic for
518 /// ObjCForCollectionStmt.
519 void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
520 ExplodedNode *Pred, ExplodedNodeSet &Dst);
521
522 void VisitObjCMessage(const ObjCMessageExpr *ME, ExplodedNode *Pred,
523 ExplodedNodeSet &Dst);
524
525 /// VisitReturnStmt - Transfer function logic for return statements.
526 void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
527 ExplodedNodeSet &Dst);
528
529 /// VisitOffsetOfExpr - Transfer function for offsetof.
530 void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
531 ExplodedNodeSet &Dst);
532
533 /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
534 void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
535 ExplodedNode *Pred, ExplodedNodeSet &Dst);
536
537 /// VisitUnaryOperator - Transfer function logic for unary operators.
538 void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
539 ExplodedNodeSet &Dst);
540
541 /// Handle ++ and -- (both pre- and post-increment).
542 void VisitIncrementDecrementOperator(const UnaryOperator* U,
543 ExplodedNode *Pred,
544 ExplodedNodeSet &Dst);
545
546 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
547 ExplodedNodeSet &PreVisit,
548 ExplodedNodeSet &Dst);
549
550 void VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred,
551 ExplodedNodeSet &Dst);
552
553 void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
554 ExplodedNodeSet & Dst);
555
556 void VisitCXXConstructExpr(const CXXConstructExpr *E, ExplodedNode *Pred,
557 ExplodedNodeSet &Dst);
558
559 void VisitCXXInheritedCtorInitExpr(const CXXInheritedCtorInitExpr *E,
560 ExplodedNode *Pred, ExplodedNodeSet &Dst);
561
562 void VisitCXXDestructor(QualType ObjectType, const MemRegion *Dest,
563 const Stmt *S, bool IsBaseDtor,
564 ExplodedNode *Pred, ExplodedNodeSet &Dst,
565 EvalCallOptions &Options);
566
567 void VisitCXXNewAllocatorCall(const CXXNewExpr *CNE,
568 ExplodedNode *Pred,
569 ExplodedNodeSet &Dst);
570
571 void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
572 ExplodedNodeSet &Dst);
573
574 void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
575 ExplodedNodeSet &Dst);
576
577 /// Create a C++ temporary object for an rvalue.
578 void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
579 ExplodedNode *Pred,
580 ExplodedNodeSet &Dst);
581
582 /// evalEagerlyAssumeBinOpBifurcation - Given the nodes in 'Src', eagerly assume symbolic
583 /// expressions of the form 'x != 0' and generate new nodes (stored in Dst)
584 /// with those assumptions.
585 void evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
586 const Expr *Ex);
587
588 static std::pair<const ProgramPointTag *, const ProgramPointTag *>
589 geteagerlyAssumeBinOpBifurcationTags();
590
591 ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex,
592 const LocationContext *LCtx, QualType T,
593 QualType ExTy, const CastExpr *CastE,
594 StmtNodeBuilder &Bldr,
595 ExplodedNode *Pred);
596
597 void handleUOExtension(ExplodedNode *N, const UnaryOperator *U,
598 StmtNodeBuilder &Bldr);
599
600public:
601 SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op,
602 SVal LHS, SVal RHS, QualType T) {
603 return svalBuilder.evalBinOp(state: ST, op: Op, lhs: LHS, rhs: RHS, type: T);
604 }
605
606 /// Retreives which element is being constructed in a non-POD type array.
607 static std::optional<unsigned>
608 getIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E,
609 const LocationContext *LCtx);
610
611 /// Retreives which element is being destructed in a non-POD type array.
612 static std::optional<unsigned>
613 getPendingArrayDestruction(ProgramStateRef State,
614 const LocationContext *LCtx);
615
616 /// Retreives the size of the array in the pending ArrayInitLoopExpr.
617 static std::optional<unsigned>
618 getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E,
619 const LocationContext *LCtx);
620
621 /// By looking at a certain item that may be potentially part of an object's
622 /// ConstructionContext, retrieve such object's location. A particular
623 /// statement can be transparently passed as \p Item in most cases.
624 static std::optional<SVal>
625 getObjectUnderConstruction(ProgramStateRef State,
626 const ConstructionContextItem &Item,
627 const LocationContext *LC);
628
629 /// Call PointerEscape callback when a value escapes as a result of bind.
630 ProgramStateRef processPointerEscapedOnBind(
631 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
632 const LocationContext *LCtx, PointerEscapeKind Kind,
633 const CallEvent *Call);
634
635 /// Call PointerEscape callback when a value escapes as a result of
636 /// region invalidation.
637 /// \param[in] ITraits Specifies invalidation traits for regions/symbols.
638 ProgramStateRef notifyCheckersOfPointerEscape(
639 ProgramStateRef State,
640 const InvalidatedSymbols *Invalidated,
641 ArrayRef<const MemRegion *> ExplicitRegions,
642 const CallEvent *Call,
643 RegionAndSymbolInvalidationTraits &ITraits);
644
645private:
646 /// evalBind - Handle the semantics of binding a value to a specific location.
647 /// This method is used by evalStore, VisitDeclStmt, and others.
648 void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
649 SVal location, SVal Val, bool atDeclInit = false,
650 const ProgramPoint *PP = nullptr);
651
652 ProgramStateRef
653 processPointerEscapedOnBind(ProgramStateRef State,
654 SVal Loc, SVal Val,
655 const LocationContext *LCtx);
656
657 /// A simple wrapper when you only need to notify checkers of pointer-escape
658 /// of some values.
659 ProgramStateRef escapeValues(ProgramStateRef State, ArrayRef<SVal> Vs,
660 PointerEscapeKind K,
661 const CallEvent *Call = nullptr) const;
662
663public:
664 // FIXME: 'tag' should be removed, and a LocationContext should be used
665 // instead.
666 // FIXME: Comment on the meaning of the arguments, when 'St' may not
667 // be the same as Pred->state, and when 'location' may not be the
668 // same as state->getLValue(Ex).
669 /// Simulate a read of the result of Ex.
670 void evalLoad(ExplodedNodeSet &Dst,
671 const Expr *NodeEx, /* Eventually will be a CFGStmt */
672 const Expr *BoundExpr,
673 ExplodedNode *Pred,
674 ProgramStateRef St,
675 SVal location,
676 const ProgramPointTag *tag = nullptr,
677 QualType LoadTy = QualType());
678
679 // FIXME: 'tag' should be removed, and a LocationContext should be used
680 // instead.
681 void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
682 ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val,
683 const ProgramPointTag *tag = nullptr);
684
685 /// Return the CFG element corresponding to the worklist element
686 /// that is currently being processed by ExprEngine.
687 CFGElement getCurrentCFGElement() {
688 return (*currBldrCtx->getBlock())[currStmtIdx];
689 }
690
691 /// Create a new state in which the call return value is binded to the
692 /// call origin expression.
693 ProgramStateRef bindReturnValue(const CallEvent &Call,
694 const LocationContext *LCtx,
695 ProgramStateRef State);
696
697 /// Evaluate a call, running pre- and post-call checkers and allowing checkers
698 /// to be responsible for handling the evaluation of the call itself.
699 void evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
700 const CallEvent &Call);
701
702 /// Default implementation of call evaluation.
703 void defaultEvalCall(NodeBuilder &B, ExplodedNode *Pred,
704 const CallEvent &Call,
705 const EvalCallOptions &CallOpts = {});
706
707 /// Find location of the object that is being constructed by a given
708 /// constructor. This should ideally always succeed but due to not being
709 /// fully implemented it sometimes indicates that it failed via its
710 /// out-parameter CallOpts; in such cases a fake temporary region is
711 /// returned, which is better than nothing but does not represent
712 /// the actual behavior of the program. The Idx parameter is used if we
713 /// construct an array of objects. In that case it points to the index
714 /// of the continuous memory region.
715 /// E.g.:
716 /// For `int arr[4]` this index can be 0,1,2,3.
717 /// For `int arr2[3][3]` this index can be 0,1,...,7,8.
718 /// A multi-dimensional array is also a continuous memory location in a
719 /// row major order, so for arr[0][0] Idx is 0 and for arr[2][2] Idx is 8.
720 SVal computeObjectUnderConstruction(const Expr *E, ProgramStateRef State,
721 const NodeBuilderContext *BldrCtx,
722 const LocationContext *LCtx,
723 const ConstructionContext *CC,
724 EvalCallOptions &CallOpts,
725 unsigned Idx = 0);
726
727 /// Update the program state with all the path-sensitive information
728 /// that's necessary to perform construction of an object with a given
729 /// syntactic construction context. V and CallOpts have to be obtained from
730 /// computeObjectUnderConstruction() invoked with the same set of
731 /// the remaining arguments (E, State, LCtx, CC).
732 ProgramStateRef updateObjectsUnderConstruction(
733 SVal V, const Expr *E, ProgramStateRef State, const LocationContext *LCtx,
734 const ConstructionContext *CC, const EvalCallOptions &CallOpts);
735
736 /// A convenient wrapper around computeObjectUnderConstruction
737 /// and updateObjectsUnderConstruction.
738 std::pair<ProgramStateRef, SVal> handleConstructionContext(
739 const Expr *E, ProgramStateRef State, const NodeBuilderContext *BldrCtx,
740 const LocationContext *LCtx, const ConstructionContext *CC,
741 EvalCallOptions &CallOpts, unsigned Idx = 0) {
742
743 SVal V = computeObjectUnderConstruction(E, State, BldrCtx, LCtx, CC,
744 CallOpts, Idx);
745 State = updateObjectsUnderConstruction(V, E, State, LCtx, CC, CallOpts);
746
747 return std::make_pair(x&: State, y&: V);
748 }
749
750private:
751 ProgramStateRef finishArgumentConstruction(ProgramStateRef State,
752 const CallEvent &Call);
753 void finishArgumentConstruction(ExplodedNodeSet &Dst, ExplodedNode *Pred,
754 const CallEvent &Call);
755
756 void evalLocation(ExplodedNodeSet &Dst,
757 const Stmt *NodeEx, /* This will eventually be a CFGStmt */
758 const Stmt *BoundEx,
759 ExplodedNode *Pred,
760 ProgramStateRef St,
761 SVal location,
762 bool isLoad);
763
764 /// Count the stack depth and determine if the call is recursive.
765 void examineStackFrames(const Decl *D, const LocationContext *LCtx,
766 bool &IsRecursive, unsigned &StackDepth);
767
768 enum CallInlinePolicy {
769 CIP_Allowed,
770 CIP_DisallowedOnce,
771 CIP_DisallowedAlways
772 };
773
774 /// See if a particular call should be inlined, by only looking
775 /// at the call event and the current state of analysis.
776 CallInlinePolicy mayInlineCallKind(const CallEvent &Call,
777 const ExplodedNode *Pred,
778 AnalyzerOptions &Opts,
779 const EvalCallOptions &CallOpts);
780
781 /// See if the given AnalysisDeclContext is built for a function that we
782 /// should always inline simply because it's small enough.
783 /// Apart from "small" functions, we also have "large" functions
784 /// (cf. isLarge()), some of which are huge (cf. isHuge()), and we classify
785 /// the remaining functions as "medium".
786 bool isSmall(AnalysisDeclContext *ADC) const;
787
788 /// See if the given AnalysisDeclContext is built for a function that we
789 /// should inline carefully because it looks pretty large.
790 bool isLarge(AnalysisDeclContext *ADC) const;
791
792 /// See if the given AnalysisDeclContext is built for a function that we
793 /// should never inline because it's legit gigantic.
794 bool isHuge(AnalysisDeclContext *ADC) const;
795
796 /// See if the given AnalysisDeclContext is built for a function that we
797 /// should inline, just by looking at the declaration of the function.
798 bool mayInlineDecl(AnalysisDeclContext *ADC) const;
799
800 /// Checks our policies and decides weither the given call should be inlined.
801 bool shouldInlineCall(const CallEvent &Call, const Decl *D,
802 const ExplodedNode *Pred,
803 const EvalCallOptions &CallOpts = {});
804
805 /// Checks whether our policies allow us to inline a non-POD type array
806 /// construction.
807 bool shouldInlineArrayConstruction(const ProgramStateRef State,
808 const CXXConstructExpr *CE,
809 const LocationContext *LCtx);
810
811 /// Checks whether our policies allow us to inline a non-POD type array
812 /// destruction.
813 /// \param Size The size of the array.
814 bool shouldInlineArrayDestruction(uint64_t Size);
815
816 /// Prepares the program state for array destruction. If no error happens
817 /// the function binds a 'PendingArrayDestruction' entry to the state, which
818 /// it returns along with the index. If any error happens (we fail to read
819 /// the size, the index would be -1, etc.) the function will return the
820 /// original state along with an index of 0. The actual element count of the
821 /// array can be accessed by the optional 'ElementCountVal' parameter. \param
822 /// State The program state. \param Region The memory region where the array
823 /// is stored. \param ElementTy The type an element in the array. \param LCty
824 /// The location context. \param ElementCountVal A pointer to an optional
825 /// SVal. If specified, the size of the array will be returned in it. It can
826 /// be Unknown.
827 std::pair<ProgramStateRef, uint64_t> prepareStateForArrayDestruction(
828 const ProgramStateRef State, const MemRegion *Region,
829 const QualType &ElementTy, const LocationContext *LCtx,
830 SVal *ElementCountVal = nullptr);
831
832 /// Checks whether we construct an array of non-POD type, and decides if the
833 /// constructor should be inkoved once again.
834 bool shouldRepeatCtorCall(ProgramStateRef State, const CXXConstructExpr *E,
835 const LocationContext *LCtx);
836
837 void inlineCall(WorkList *WList, const CallEvent &Call, const Decl *D,
838 NodeBuilder &Bldr, ExplodedNode *Pred, ProgramStateRef State);
839
840 void ctuBifurcate(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
841 ExplodedNode *Pred, ProgramStateRef State);
842
843 /// Returns true if the CTU analysis is running its second phase.
844 bool isSecondPhaseCTU() { return IsCTUEnabled && !Engine.getCTUWorkList(); }
845
846 /// Conservatively evaluate call by invalidating regions and binding
847 /// a conjured return value.
848 void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
849 ExplodedNode *Pred, ProgramStateRef State);
850
851 /// Either inline or process the call conservatively (or both), based
852 /// on DynamicDispatchBifurcation data.
853 void BifurcateCall(const MemRegion *BifurReg,
854 const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
855 ExplodedNode *Pred);
856
857 bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
858
859 /// Models a trivial copy or move constructor or trivial assignment operator
860 /// call with a simple bind.
861 void performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred,
862 const CallEvent &Call);
863
864 /// If the value of the given expression \p InitWithAdjustments is a NonLoc,
865 /// copy it into a new temporary object region, and replace the value of the
866 /// expression with that.
867 ///
868 /// If \p Result is provided, the new region will be bound to this expression
869 /// instead of \p InitWithAdjustments.
870 ///
871 /// Returns the temporary region with adjustments into the optional
872 /// OutRegionWithAdjustments out-parameter if a new region was indeed needed,
873 /// otherwise sets it to nullptr.
874 ProgramStateRef createTemporaryRegionIfNeeded(
875 ProgramStateRef State, const LocationContext *LC,
876 const Expr *InitWithAdjustments, const Expr *Result = nullptr,
877 const SubRegion **OutRegionWithAdjustments = nullptr);
878
879 /// Returns a region representing the `Idx`th element of a (possibly
880 /// multi-dimensional) array, for the purposes of element construction or
881 /// destruction.
882 ///
883 /// On return, \p Ty will be set to the base type of the array.
884 ///
885 /// If the type is not an array type at all, the original value is returned.
886 /// Otherwise the "IsArray" flag is set.
887 static SVal makeElementRegion(ProgramStateRef State, SVal LValue,
888 QualType &Ty, bool &IsArray, unsigned Idx = 0);
889
890 /// Common code that handles either a CXXConstructExpr or a
891 /// CXXInheritedCtorInitExpr.
892 void handleConstructor(const Expr *E, ExplodedNode *Pred,
893 ExplodedNodeSet &Dst);
894
895public:
896 /// Note whether this loop has any more iteratios to model. These methods are
897 /// essentially an interface for a GDM trait. Further reading in
898 /// ExprEngine::VisitObjCForCollectionStmt().
899 [[nodiscard]] static ProgramStateRef
900 setWhetherHasMoreIteration(ProgramStateRef State,
901 const ObjCForCollectionStmt *O,
902 const LocationContext *LC, bool HasMoreIteraton);
903
904 [[nodiscard]] static ProgramStateRef
905 removeIterationState(ProgramStateRef State, const ObjCForCollectionStmt *O,
906 const LocationContext *LC);
907
908 [[nodiscard]] static bool hasMoreIteration(ProgramStateRef State,
909 const ObjCForCollectionStmt *O,
910 const LocationContext *LC);
911
912private:
913 /// Assuming we construct an array of non-POD types, this method allows us
914 /// to store which element is to be constructed next.
915 static ProgramStateRef
916 setIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E,
917 const LocationContext *LCtx, unsigned Idx);
918
919 static ProgramStateRef
920 removeIndexOfElementToConstruct(ProgramStateRef State,
921 const CXXConstructExpr *E,
922 const LocationContext *LCtx);
923
924 /// Assuming we destruct an array of non-POD types, this method allows us
925 /// to store which element is to be destructed next.
926 static ProgramStateRef setPendingArrayDestruction(ProgramStateRef State,
927 const LocationContext *LCtx,
928 unsigned Idx);
929
930 static ProgramStateRef
931 removePendingArrayDestruction(ProgramStateRef State,
932 const LocationContext *LCtx);
933
934 /// Sets the size of the array in a pending ArrayInitLoopExpr.
935 static ProgramStateRef setPendingInitLoop(ProgramStateRef State,
936 const CXXConstructExpr *E,
937 const LocationContext *LCtx,
938 unsigned Idx);
939
940 static ProgramStateRef removePendingInitLoop(ProgramStateRef State,
941 const CXXConstructExpr *E,
942 const LocationContext *LCtx);
943
944 static ProgramStateRef
945 removeStateTraitsUsedForArrayEvaluation(ProgramStateRef State,
946 const CXXConstructExpr *E,
947 const LocationContext *LCtx);
948
949 /// Store the location of a C++ object corresponding to a statement
950 /// until the statement is actually encountered. For example, if a DeclStmt
951 /// has CXXConstructExpr as its initializer, the object would be considered
952 /// to be "under construction" between CXXConstructExpr and DeclStmt.
953 /// This allows, among other things, to keep bindings to variable's fields
954 /// made within the constructor alive until its declaration actually
955 /// goes into scope.
956 static ProgramStateRef
957 addObjectUnderConstruction(ProgramStateRef State,
958 const ConstructionContextItem &Item,
959 const LocationContext *LC, SVal V);
960
961 /// Mark the object sa fully constructed, cleaning up the state trait
962 /// that tracks objects under construction.
963 static ProgramStateRef
964 finishObjectConstruction(ProgramStateRef State,
965 const ConstructionContextItem &Item,
966 const LocationContext *LC);
967
968 /// If the given expression corresponds to a temporary that was used for
969 /// passing into an elidable copy/move constructor and that constructor
970 /// was actually elided, track that we also need to elide the destructor.
971 static ProgramStateRef elideDestructor(ProgramStateRef State,
972 const CXXBindTemporaryExpr *BTE,
973 const LocationContext *LC);
974
975 /// Stop tracking the destructor that corresponds to an elided constructor.
976 static ProgramStateRef
977 cleanupElidedDestructor(ProgramStateRef State,
978 const CXXBindTemporaryExpr *BTE,
979 const LocationContext *LC);
980
981 /// Returns true if the given expression corresponds to a temporary that
982 /// was constructed for passing into an elidable copy/move constructor
983 /// and that constructor was actually elided.
984 static bool isDestructorElided(ProgramStateRef State,
985 const CXXBindTemporaryExpr *BTE,
986 const LocationContext *LC);
987
988 /// Check if all objects under construction have been fully constructed
989 /// for the given context range (including FromLC, not including ToLC).
990 /// This is useful for assertions. Also checks if elided destructors
991 /// were cleaned up.
992 static bool areAllObjectsFullyConstructed(ProgramStateRef State,
993 const LocationContext *FromLC,
994 const LocationContext *ToLC);
995};
996
997/// Traits for storing the call processing policy inside GDM.
998/// The GDM stores the corresponding CallExpr pointer.
999// FIXME: This does not use the nice trait macros because it must be accessible
1000// from multiple translation units.
1001struct ReplayWithoutInlining{};
1002template <>
1003struct ProgramStateTrait<ReplayWithoutInlining> :
1004 public ProgramStatePartialTrait<const void*> {
1005 static void *GDMIndex();
1006};
1007
1008} // namespace ento
1009
1010} // namespace clang
1011
1012#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
1013

source code of clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h