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