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

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