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 42 namespace clang { 43 44 class AnalysisDeclContextManager; 45 class AnalyzerOptions; 46 class ASTContext; 47 class CFGBlock; 48 class CFGElement; 49 class ConstructionContext; 50 class CXXBindTemporaryExpr; 51 class CXXCatchStmt; 52 class CXXConstructExpr; 53 class CXXDeleteExpr; 54 class CXXNewExpr; 55 class CXXThisExpr; 56 class Decl; 57 class DeclStmt; 58 class GCCAsmStmt; 59 class LambdaExpr; 60 class LocationContext; 61 class MaterializeTemporaryExpr; 62 class MSAsmStmt; 63 class NamedDecl; 64 class ObjCAtSynchronizedStmt; 65 class ObjCForCollectionStmt; 66 class ObjCIvarRefExpr; 67 class ObjCMessageExpr; 68 class ReturnStmt; 69 class Stmt; 70 71 namespace cross_tu { 72 73 class CrossTranslationUnitContext; 74 75 } // namespace cross_tu 76 77 namespace ento { 78 79 class AnalysisManager; 80 class BasicValueFactory; 81 class CallEvent; 82 class CheckerManager; 83 class ConstraintManager; 84 class ExplodedNodeSet; 85 class ExplodedNode; 86 class IndirectGotoNodeBuilder; 87 class MemRegion; 88 class NodeBuilderContext; 89 class NodeBuilderWithSinks; 90 class ProgramState; 91 class ProgramStateManager; 92 class RegionAndSymbolInvalidationTraits; 93 class SymbolManager; 94 class SwitchNodeBuilder; 95 96 /// Hints for figuring out of a call should be inlined during evalCall(). 97 struct 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 EvalCallOptionsEvalCallOptions121 EvalCallOptions() {} 122 }; 123 124 class ExprEngine { 125 void anchor(); 126 127 public: 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 137 private: 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 181 public: 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, nullptr); 193 } 194 195 /// getContext - Return the ASTContext associated with this analysis. getContext()196 ASTContext &getContext() const { return AMgr.getASTContext(); } 197 getAnalysisManager()198 AnalysisManager &getAnalysisManager() { return AMgr; } 199 getAnalysisDeclContextManager()200 AnalysisDeclContextManager &getAnalysisDeclContextManager() { 201 return AMgr.getAnalysisDeclContextManager(); 202 } 203 getCheckerManager()204 CheckerManager &getCheckerManager() const { 205 return *AMgr.getCheckerManager(); 206 } 207 getSValBuilder()208 SValBuilder &getSValBuilder() { return svalBuilder; } 209 getBugReporter()210 BugReporter &getBugReporter() { return BR; } 211 212 cross_tu::CrossTranslationUnitContext * getCrossTranslationUnitContext()213 getCrossTranslationUnitContext() { 214 return &CTU; 215 } 216 getBuilderContext()217 const NodeBuilderContext &getBuilderContext() { 218 assert(currBldrCtx); 219 return *currBldrCtx; 220 } 221 222 const Stmt *getStmt() const; 223 getRootLocationContext()224 const LocationContext *getRootLocationContext() const { 225 assert(G.getRoot()); 226 return G.getRoot()->getLocation().getLocationContext(); 227 } 228 getCFGElementRef()229 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 getGraph()256 ExplodedGraph &getGraph() { return G; } getGraph()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 /// A tag to track convenience transitions, which can be removed at cleanup. 290 /// This tag applies to a node created after removeDead. 291 static const ProgramPointTag *cleanupNodeTag(); 292 293 /// processCFGElement - Called by CoreEngine. Used to generate new successor 294 /// nodes by processing the 'effects' of a CFG element. 295 void processCFGElement(const CFGElement E, ExplodedNode *Pred, 296 unsigned StmtIdx, NodeBuilderContext *Ctx); 297 298 void ProcessStmt(const Stmt *S, ExplodedNode *Pred); 299 300 void ProcessLoopExit(const Stmt* S, ExplodedNode *Pred); 301 302 void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred); 303 304 void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred); 305 306 void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred); 307 308 void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D, 309 ExplodedNode *Pred, ExplodedNodeSet &Dst); 310 void ProcessDeleteDtor(const CFGDeleteDtor D, 311 ExplodedNode *Pred, ExplodedNodeSet &Dst); 312 void ProcessBaseDtor(const CFGBaseDtor D, 313 ExplodedNode *Pred, ExplodedNodeSet &Dst); 314 void ProcessMemberDtor(const CFGMemberDtor D, 315 ExplodedNode *Pred, ExplodedNodeSet &Dst); 316 void ProcessTemporaryDtor(const CFGTemporaryDtor D, 317 ExplodedNode *Pred, ExplodedNodeSet &Dst); 318 319 /// Called by CoreEngine when processing the entrance of a CFGBlock. 320 void processCFGBlockEntrance(const BlockEdge &L, 321 NodeBuilderWithSinks &nodeBuilder, 322 ExplodedNode *Pred); 323 324 void runCheckersForBlockEntrance(const NodeBuilderContext &BldCtx, 325 const BlockEntrance &Entrance, 326 ExplodedNode *Pred, ExplodedNodeSet &Dst); 327 328 /// ProcessBranch - Called by CoreEngine. Used to generate successor nodes by 329 /// processing the 'effects' of a branch condition. If the branch condition 330 /// is a loop condition, IterationsCompletedInLoop is the number of completed 331 /// iterations (otherwise it's std::nullopt). 332 void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, 333 ExplodedNode *Pred, ExplodedNodeSet &Dst, 334 const CFGBlock *DstT, const CFGBlock *DstF, 335 std::optional<unsigned> IterationsCompletedInLoop); 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 processRegionChange(ProgramStateRef state,const MemRegion * MR,const LocationContext * LCtx)407 processRegionChange(ProgramStateRef state, 408 const MemRegion* MR, 409 const LocationContext *LCtx) { 410 return processRegionChanges(state, nullptr, MR, MR, LCtx, 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 getStateManager()418 ProgramStateManager &getStateManager() { return StateMgr; } 419 getStoreManager()420 StoreManager &getStoreManager() { return StateMgr.getStoreManager(); } 421 getConstraintManager()422 ConstraintManager &getConstraintManager() { 423 return StateMgr.getConstraintManager(); 424 } 425 426 // FIXME: Remove when we migrate over to just using SValBuilder. getBasicVals()427 BasicValueFactory &getBasicVals() { 428 return StateMgr.getBasicVals(); 429 } 430 getSymbolManager()431 SymbolManager &getSymbolManager() { return SymMgr; } getRegionManager()432 MemRegionManager &getRegionManager() { return MRMgr; } 433 getDataTags()434 DataTag::Factory &getDataTags() { return Engine.getDataTags(); } 435 436 // Functions for external checking of whether we have unfinished work. wasBlocksExhausted()437 bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); } hasEmptyWorkList()438 bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); } hasWorkRemaining()439 bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); } 440 getCoreEngine()441 const CoreEngine &getCoreEngine() const { return Engine; } 442 443 public: 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 /// VisitAttributedStmt - Transfer function logic for AttributedStmt. 506 void VisitAttributedStmt(const AttributedStmt *A, ExplodedNode *Pred, 507 ExplodedNodeSet &Dst); 508 509 /// VisitLogicalExpr - Transfer function logic for '&&', '||'. 510 void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred, 511 ExplodedNodeSet &Dst); 512 513 /// VisitMemberExpr - Transfer function for member expressions. 514 void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 515 ExplodedNodeSet &Dst); 516 517 /// VisitAtomicExpr - Transfer function for builtin atomic expressions. 518 void VisitAtomicExpr(const AtomicExpr *E, ExplodedNode *Pred, 519 ExplodedNodeSet &Dst); 520 521 /// Transfer function logic for ObjCAtSynchronizedStmts. 522 void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S, 523 ExplodedNode *Pred, ExplodedNodeSet &Dst); 524 525 /// Transfer function logic for computing the lvalue of an Objective-C ivar. 526 void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred, 527 ExplodedNodeSet &Dst); 528 529 /// VisitObjCForCollectionStmt - Transfer function logic for 530 /// ObjCForCollectionStmt. 531 void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S, 532 ExplodedNode *Pred, ExplodedNodeSet &Dst); 533 534 void VisitObjCMessage(const ObjCMessageExpr *ME, ExplodedNode *Pred, 535 ExplodedNodeSet &Dst); 536 537 /// VisitReturnStmt - Transfer function logic for return statements. 538 void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred, 539 ExplodedNodeSet &Dst); 540 541 /// VisitOffsetOfExpr - Transfer function for offsetof. 542 void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred, 543 ExplodedNodeSet &Dst); 544 545 /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof. 546 void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex, 547 ExplodedNode *Pred, ExplodedNodeSet &Dst); 548 549 /// VisitUnaryOperator - Transfer function logic for unary operators. 550 void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred, 551 ExplodedNodeSet &Dst); 552 553 /// Handle ++ and -- (both pre- and post-increment). 554 void VisitIncrementDecrementOperator(const UnaryOperator* U, 555 ExplodedNode *Pred, 556 ExplodedNodeSet &Dst); 557 558 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE, 559 ExplodedNodeSet &PreVisit, 560 ExplodedNodeSet &Dst); 561 562 void VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred, 563 ExplodedNodeSet &Dst); 564 565 void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred, 566 ExplodedNodeSet & Dst); 567 568 void VisitCXXConstructExpr(const CXXConstructExpr *E, ExplodedNode *Pred, 569 ExplodedNodeSet &Dst); 570 571 void VisitCXXInheritedCtorInitExpr(const CXXInheritedCtorInitExpr *E, 572 ExplodedNode *Pred, ExplodedNodeSet &Dst); 573 574 void VisitCXXDestructor(QualType ObjectType, const MemRegion *Dest, 575 const Stmt *S, bool IsBaseDtor, 576 ExplodedNode *Pred, ExplodedNodeSet &Dst, 577 EvalCallOptions &Options); 578 579 void VisitCXXNewAllocatorCall(const CXXNewExpr *CNE, 580 ExplodedNode *Pred, 581 ExplodedNodeSet &Dst); 582 583 void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, 584 ExplodedNodeSet &Dst); 585 586 void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred, 587 ExplodedNodeSet &Dst); 588 589 /// Create a C++ temporary object for an rvalue. 590 void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME, 591 ExplodedNode *Pred, 592 ExplodedNodeSet &Dst); 593 594 /// evalEagerlyAssumeBifurcation - Given the nodes in 'Src', eagerly assume 595 /// concrete boolean values for 'Ex', storing the resulting nodes in 'Dst'. 596 void evalEagerlyAssumeBifurcation(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, 597 const Expr *Ex); 598 599 bool didEagerlyAssumeBifurcateAt(ProgramStateRef State, const Expr *Ex) const; 600 601 static std::pair<const ProgramPointTag *, const ProgramPointTag *> 602 getEagerlyAssumeBifurcationTags(); 603 604 ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex, 605 const LocationContext *LCtx, QualType T, 606 QualType ExTy, const CastExpr *CastE, 607 StmtNodeBuilder &Bldr, 608 ExplodedNode *Pred); 609 610 void handleUOExtension(ExplodedNode *N, const UnaryOperator *U, 611 StmtNodeBuilder &Bldr); 612 613 public: evalBinOp(ProgramStateRef ST,BinaryOperator::Opcode Op,SVal LHS,SVal RHS,QualType T)614 SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op, 615 SVal LHS, SVal RHS, QualType T) { 616 return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T); 617 } 618 619 /// Retreives which element is being constructed in a non-POD type array. 620 static std::optional<unsigned> 621 getIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, 622 const LocationContext *LCtx); 623 624 /// Retreives which element is being destructed in a non-POD type array. 625 static std::optional<unsigned> 626 getPendingArrayDestruction(ProgramStateRef State, 627 const LocationContext *LCtx); 628 629 /// Retreives the size of the array in the pending ArrayInitLoopExpr. 630 static std::optional<unsigned> 631 getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E, 632 const LocationContext *LCtx); 633 634 /// By looking at a certain item that may be potentially part of an object's 635 /// ConstructionContext, retrieve such object's location. A particular 636 /// statement can be transparently passed as \p Item in most cases. 637 static std::optional<SVal> 638 getObjectUnderConstruction(ProgramStateRef State, 639 const ConstructionContextItem &Item, 640 const LocationContext *LC); 641 642 /// Call PointerEscape callback when a value escapes as a result of bind. 643 ProgramStateRef processPointerEscapedOnBind( 644 ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals, 645 const LocationContext *LCtx, PointerEscapeKind Kind, 646 const CallEvent *Call); 647 648 /// Call PointerEscape callback when a value escapes as a result of 649 /// region invalidation. 650 /// \param[in] ITraits Specifies invalidation traits for regions/symbols. 651 ProgramStateRef notifyCheckersOfPointerEscape( 652 ProgramStateRef State, 653 const InvalidatedSymbols *Invalidated, 654 ArrayRef<const MemRegion *> ExplicitRegions, 655 const CallEvent *Call, 656 RegionAndSymbolInvalidationTraits &ITraits); 657 658 private: 659 /// evalBind - Handle the semantics of binding a value to a specific location. 660 /// This method is used by evalStore, VisitDeclStmt, and others. 661 void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred, 662 SVal location, SVal Val, bool atDeclInit = false, 663 const ProgramPoint *PP = nullptr); 664 665 ProgramStateRef 666 processPointerEscapedOnBind(ProgramStateRef State, 667 SVal Loc, SVal Val, 668 const LocationContext *LCtx); 669 670 public: 671 /// A simple wrapper when you only need to notify checkers of pointer-escape 672 /// of some values. 673 ProgramStateRef escapeValues(ProgramStateRef State, ArrayRef<SVal> Vs, 674 PointerEscapeKind K, 675 const CallEvent *Call = nullptr) const; 676 677 // FIXME: 'tag' should be removed, and a LocationContext should be used 678 // instead. 679 // FIXME: Comment on the meaning of the arguments, when 'St' may not 680 // be the same as Pred->state, and when 'location' may not be the 681 // same as state->getLValue(Ex). 682 /// Simulate a read of the result of Ex. 683 void evalLoad(ExplodedNodeSet &Dst, 684 const Expr *NodeEx, /* Eventually will be a CFGStmt */ 685 const Expr *BoundExpr, 686 ExplodedNode *Pred, 687 ProgramStateRef St, 688 SVal location, 689 const ProgramPointTag *tag = nullptr, 690 QualType LoadTy = QualType()); 691 692 // FIXME: 'tag' should be removed, and a LocationContext should be used 693 // instead. 694 void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE, 695 ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val, 696 const ProgramPointTag *tag = nullptr); 697 698 /// Return the CFG element corresponding to the worklist element 699 /// that is currently being processed by ExprEngine. getCurrentCFGElement()700 CFGElement getCurrentCFGElement() { 701 return (*currBldrCtx->getBlock())[currStmtIdx]; 702 } 703 704 /// Create a new state in which the call return value is binded to the 705 /// call origin expression. 706 ProgramStateRef bindReturnValue(const CallEvent &Call, 707 const LocationContext *LCtx, 708 ProgramStateRef State); 709 710 /// Evaluate a call, running pre- and post-call checkers and allowing checkers 711 /// to be responsible for handling the evaluation of the call itself. 712 void evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred, 713 const CallEvent &Call); 714 715 /// Default implementation of call evaluation. 716 void defaultEvalCall(NodeBuilder &B, ExplodedNode *Pred, 717 const CallEvent &Call, 718 const EvalCallOptions &CallOpts = {}); 719 720 /// Find location of the object that is being constructed by a given 721 /// constructor. This should ideally always succeed but due to not being 722 /// fully implemented it sometimes indicates that it failed via its 723 /// out-parameter CallOpts; in such cases a fake temporary region is 724 /// returned, which is better than nothing but does not represent 725 /// the actual behavior of the program. The Idx parameter is used if we 726 /// construct an array of objects. In that case it points to the index 727 /// of the continuous memory region. 728 /// E.g.: 729 /// For `int arr[4]` this index can be 0,1,2,3. 730 /// For `int arr2[3][3]` this index can be 0,1,...,7,8. 731 /// A multi-dimensional array is also a continuous memory location in a 732 /// row major order, so for arr[0][0] Idx is 0 and for arr[3][3] Idx is 8. 733 SVal computeObjectUnderConstruction(const Expr *E, ProgramStateRef State, 734 const NodeBuilderContext *BldrCtx, 735 const LocationContext *LCtx, 736 const ConstructionContext *CC, 737 EvalCallOptions &CallOpts, 738 unsigned Idx = 0); 739 740 /// Update the program state with all the path-sensitive information 741 /// that's necessary to perform construction of an object with a given 742 /// syntactic construction context. V and CallOpts have to be obtained from 743 /// computeObjectUnderConstruction() invoked with the same set of 744 /// the remaining arguments (E, State, LCtx, CC). 745 ProgramStateRef updateObjectsUnderConstruction( 746 SVal V, const Expr *E, ProgramStateRef State, const LocationContext *LCtx, 747 const ConstructionContext *CC, const EvalCallOptions &CallOpts); 748 749 /// A convenient wrapper around computeObjectUnderConstruction 750 /// and updateObjectsUnderConstruction. 751 std::pair<ProgramStateRef, SVal> handleConstructionContext( 752 const Expr *E, ProgramStateRef State, const NodeBuilderContext *BldrCtx, 753 const LocationContext *LCtx, const ConstructionContext *CC, 754 EvalCallOptions &CallOpts, unsigned Idx = 0) { 755 756 SVal V = computeObjectUnderConstruction(E, State, BldrCtx, LCtx, CC, 757 CallOpts, Idx); 758 State = updateObjectsUnderConstruction(V, E, State, LCtx, CC, CallOpts); 759 760 return std::make_pair(State, V); 761 } 762 763 private: 764 ProgramStateRef finishArgumentConstruction(ProgramStateRef State, 765 const CallEvent &Call); 766 void finishArgumentConstruction(ExplodedNodeSet &Dst, ExplodedNode *Pred, 767 const CallEvent &Call); 768 769 void evalLocation(ExplodedNodeSet &Dst, 770 const Stmt *NodeEx, /* This will eventually be a CFGStmt */ 771 const Stmt *BoundEx, 772 ExplodedNode *Pred, 773 ProgramStateRef St, 774 SVal location, 775 bool isLoad); 776 777 /// Count the stack depth and determine if the call is recursive. 778 void examineStackFrames(const Decl *D, const LocationContext *LCtx, 779 bool &IsRecursive, unsigned &StackDepth); 780 781 enum CallInlinePolicy { 782 CIP_Allowed, 783 CIP_DisallowedOnce, 784 CIP_DisallowedAlways 785 }; 786 787 /// See if a particular call should be inlined, by only looking 788 /// at the call event and the current state of analysis. 789 CallInlinePolicy mayInlineCallKind(const CallEvent &Call, 790 const ExplodedNode *Pred, 791 AnalyzerOptions &Opts, 792 const EvalCallOptions &CallOpts); 793 794 /// See if the given AnalysisDeclContext is built for a function that we 795 /// should always inline simply because it's small enough. 796 /// Apart from "small" functions, we also have "large" functions 797 /// (cf. isLarge()), some of which are huge (cf. isHuge()), and we classify 798 /// the remaining functions as "medium". 799 bool isSmall(AnalysisDeclContext *ADC) const; 800 801 /// See if the given AnalysisDeclContext is built for a function that we 802 /// should inline carefully because it looks pretty large. 803 bool isLarge(AnalysisDeclContext *ADC) const; 804 805 /// See if the given AnalysisDeclContext is built for a function that we 806 /// should never inline because it's legit gigantic. 807 bool isHuge(AnalysisDeclContext *ADC) const; 808 809 /// See if the given AnalysisDeclContext is built for a function that we 810 /// should inline, just by looking at the declaration of the function. 811 bool mayInlineDecl(AnalysisDeclContext *ADC) const; 812 813 /// Checks our policies and decides whether the given call should be inlined. 814 bool shouldInlineCall(const CallEvent &Call, const Decl *D, 815 const ExplodedNode *Pred, 816 const EvalCallOptions &CallOpts = {}); 817 818 /// Checks whether our policies allow us to inline a non-POD type array 819 /// construction. 820 bool shouldInlineArrayConstruction(const ProgramStateRef State, 821 const CXXConstructExpr *CE, 822 const LocationContext *LCtx); 823 824 /// Checks whether our policies allow us to inline a non-POD type array 825 /// destruction. 826 /// \param Size The size of the array. 827 bool shouldInlineArrayDestruction(uint64_t Size); 828 829 /// Prepares the program state for array destruction. If no error happens 830 /// the function binds a 'PendingArrayDestruction' entry to the state, which 831 /// it returns along with the index. If any error happens (we fail to read 832 /// the size, the index would be -1, etc.) the function will return the 833 /// original state along with an index of 0. The actual element count of the 834 /// array can be accessed by the optional 'ElementCountVal' parameter. \param 835 /// State The program state. \param Region The memory region where the array 836 /// is stored. \param ElementTy The type an element in the array. \param LCty 837 /// The location context. \param ElementCountVal A pointer to an optional 838 /// SVal. If specified, the size of the array will be returned in it. It can 839 /// be Unknown. 840 std::pair<ProgramStateRef, uint64_t> prepareStateForArrayDestruction( 841 const ProgramStateRef State, const MemRegion *Region, 842 const QualType &ElementTy, const LocationContext *LCtx, 843 SVal *ElementCountVal = nullptr); 844 845 /// Checks whether we construct an array of non-POD type, and decides if the 846 /// constructor should be inkoved once again. 847 bool shouldRepeatCtorCall(ProgramStateRef State, const CXXConstructExpr *E, 848 const LocationContext *LCtx); 849 850 void inlineCall(WorkList *WList, const CallEvent &Call, const Decl *D, 851 NodeBuilder &Bldr, ExplodedNode *Pred, ProgramStateRef State); 852 853 void ctuBifurcate(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr, 854 ExplodedNode *Pred, ProgramStateRef State); 855 856 /// Returns true if the CTU analysis is running its second phase. isSecondPhaseCTU()857 bool isSecondPhaseCTU() { return IsCTUEnabled && !Engine.getCTUWorkList(); } 858 859 /// Conservatively evaluate call by invalidating regions and binding 860 /// a conjured return value. 861 void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr, 862 ExplodedNode *Pred, ProgramStateRef State); 863 864 /// Either inline or process the call conservatively (or both), based 865 /// on DynamicDispatchBifurcation data. 866 void BifurcateCall(const MemRegion *BifurReg, 867 const CallEvent &Call, const Decl *D, NodeBuilder &Bldr, 868 ExplodedNode *Pred); 869 870 bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC); 871 872 /// Models a trivial copy or move constructor or trivial assignment operator 873 /// call with a simple bind. 874 void performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred, 875 const CallEvent &Call); 876 877 /// If the value of the given expression \p InitWithAdjustments is a NonLoc, 878 /// copy it into a new temporary object region, and replace the value of the 879 /// expression with that. 880 /// 881 /// If \p Result is provided, the new region will be bound to this expression 882 /// instead of \p InitWithAdjustments. 883 /// 884 /// Returns the temporary region with adjustments into the optional 885 /// OutRegionWithAdjustments out-parameter if a new region was indeed needed, 886 /// otherwise sets it to nullptr. 887 ProgramStateRef createTemporaryRegionIfNeeded( 888 ProgramStateRef State, const LocationContext *LC, 889 const Expr *InitWithAdjustments, const Expr *Result = nullptr, 890 const SubRegion **OutRegionWithAdjustments = nullptr); 891 892 /// Returns a region representing the `Idx`th element of a (possibly 893 /// multi-dimensional) array, for the purposes of element construction or 894 /// destruction. 895 /// 896 /// On return, \p Ty will be set to the base type of the array. 897 /// 898 /// If the type is not an array type at all, the original value is returned. 899 /// Otherwise the "IsArray" flag is set. 900 static SVal makeElementRegion(ProgramStateRef State, SVal LValue, 901 QualType &Ty, bool &IsArray, unsigned Idx = 0); 902 903 /// Common code that handles either a CXXConstructExpr or a 904 /// CXXInheritedCtorInitExpr. 905 void handleConstructor(const Expr *E, ExplodedNode *Pred, 906 ExplodedNodeSet &Dst); 907 908 public: 909 /// Note whether this loop has any more iterations to model. These methods 910 // are essentially an interface for a GDM trait. Further reading in 911 /// ExprEngine::VisitObjCForCollectionStmt(). 912 [[nodiscard]] static ProgramStateRef 913 setWhetherHasMoreIteration(ProgramStateRef State, 914 const ObjCForCollectionStmt *O, 915 const LocationContext *LC, bool HasMoreIteraton); 916 917 [[nodiscard]] static ProgramStateRef 918 removeIterationState(ProgramStateRef State, const ObjCForCollectionStmt *O, 919 const LocationContext *LC); 920 921 [[nodiscard]] static bool hasMoreIteration(ProgramStateRef State, 922 const ObjCForCollectionStmt *O, 923 const LocationContext *LC); 924 925 private: 926 /// Assuming we construct an array of non-POD types, this method allows us 927 /// to store which element is to be constructed next. 928 static ProgramStateRef 929 setIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, 930 const LocationContext *LCtx, unsigned Idx); 931 932 static ProgramStateRef 933 removeIndexOfElementToConstruct(ProgramStateRef State, 934 const CXXConstructExpr *E, 935 const LocationContext *LCtx); 936 937 /// Assuming we destruct an array of non-POD types, this method allows us 938 /// to store which element is to be destructed next. 939 static ProgramStateRef setPendingArrayDestruction(ProgramStateRef State, 940 const LocationContext *LCtx, 941 unsigned Idx); 942 943 static ProgramStateRef 944 removePendingArrayDestruction(ProgramStateRef State, 945 const LocationContext *LCtx); 946 947 /// Sets the size of the array in a pending ArrayInitLoopExpr. 948 static ProgramStateRef setPendingInitLoop(ProgramStateRef State, 949 const CXXConstructExpr *E, 950 const LocationContext *LCtx, 951 unsigned Idx); 952 953 static ProgramStateRef removePendingInitLoop(ProgramStateRef State, 954 const CXXConstructExpr *E, 955 const LocationContext *LCtx); 956 957 static ProgramStateRef 958 removeStateTraitsUsedForArrayEvaluation(ProgramStateRef State, 959 const CXXConstructExpr *E, 960 const LocationContext *LCtx); 961 962 /// Store the location of a C++ object corresponding to a statement 963 /// until the statement is actually encountered. For example, if a DeclStmt 964 /// has CXXConstructExpr as its initializer, the object would be considered 965 /// to be "under construction" between CXXConstructExpr and DeclStmt. 966 /// This allows, among other things, to keep bindings to variable's fields 967 /// made within the constructor alive until its declaration actually 968 /// goes into scope. 969 static ProgramStateRef 970 addObjectUnderConstruction(ProgramStateRef State, 971 const ConstructionContextItem &Item, 972 const LocationContext *LC, SVal V); 973 974 /// Mark the object as fully constructed, cleaning up the state trait 975 /// that tracks objects under construction. 976 static ProgramStateRef 977 finishObjectConstruction(ProgramStateRef State, 978 const ConstructionContextItem &Item, 979 const LocationContext *LC); 980 981 /// If the given expression corresponds to a temporary that was used for 982 /// passing into an elidable copy/move constructor and that constructor 983 /// was actually elided, track that we also need to elide the destructor. 984 static ProgramStateRef elideDestructor(ProgramStateRef State, 985 const CXXBindTemporaryExpr *BTE, 986 const LocationContext *LC); 987 988 /// Stop tracking the destructor that corresponds to an elided constructor. 989 static ProgramStateRef 990 cleanupElidedDestructor(ProgramStateRef State, 991 const CXXBindTemporaryExpr *BTE, 992 const LocationContext *LC); 993 994 /// Returns true if the given expression corresponds to a temporary that 995 /// was constructed for passing into an elidable copy/move constructor 996 /// and that constructor was actually elided. 997 static bool isDestructorElided(ProgramStateRef State, 998 const CXXBindTemporaryExpr *BTE, 999 const LocationContext *LC); 1000 1001 /// Check if all objects under construction have been fully constructed 1002 /// for the given context range (including FromLC, not including ToLC). 1003 /// This is useful for assertions. Also checks if elided destructors 1004 /// were cleaned up. 1005 static bool areAllObjectsFullyConstructed(ProgramStateRef State, 1006 const LocationContext *FromLC, 1007 const LocationContext *ToLC); 1008 }; 1009 1010 /// Traits for storing the call processing policy inside GDM. 1011 /// The GDM stores the corresponding CallExpr pointer. 1012 // FIXME: This does not use the nice trait macros because it must be accessible 1013 // from multiple translation units. 1014 struct ReplayWithoutInlining{}; 1015 template <> 1016 struct ProgramStateTrait<ReplayWithoutInlining> : 1017 public ProgramStatePartialTrait<const void*> { 1018 static void *GDMIndex(); 1019 }; 1020 1021 } // namespace ento 1022 1023 } // namespace clang 1024 1025 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H 1026