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