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