1 //===--- CheckerManager.h - Static Analyzer Checker Manager -----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Defines the Static Analyzer Checker Manager. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_SA_CORE_CHECKERMANAGER_H 15 #define LLVM_CLANG_SA_CORE_CHECKERMANAGER_H 16 17 #include "clang/Basic/LangOptions.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/FoldingSet.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 22 #include "clang/Analysis/ProgramPoint.h" 23 #include <vector> 24 25 namespace clang { 26 class Decl; 27 class Stmt; 28 class CallExpr; 29 30 namespace ento { 31 class CheckerBase; 32 class ExprEngine; 33 class AnalysisManager; 34 class BugReporter; 35 class CheckerContext; 36 class ObjCMessage; 37 class SVal; 38 class ExplodedNode; 39 class ExplodedNodeSet; 40 class ExplodedGraph; 41 class ProgramState; 42 class NodeBuilder; 43 struct NodeBuilderContext; 44 class MemRegion; 45 class SymbolReaper; 46 47 class GraphExpander { 48 public: 49 virtual ~GraphExpander(); 50 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) = 0; 51 }; 52 53 template <typename T> class CheckerFn; 54 55 template <typename RET, typename P1, typename P2, typename P3, typename P4, 56 typename P5> 57 class CheckerFn<RET(P1, P2, P3, P4, P5)> { 58 typedef RET (*Func)(void *, P1, P2, P3, P4, P5); 59 Func Fn; 60 public: 61 CheckerBase *Checker; 62 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 63 RET operator()(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) const { 64 return Fn(Checker, p1, p2, p3, p4, p5); 65 } 66 }; 67 68 template <typename RET, typename P1, typename P2, typename P3, typename P4> 69 class CheckerFn<RET(P1, P2, P3, P4)> { 70 typedef RET (*Func)(void *, P1, P2, P3, P4); 71 Func Fn; 72 public: 73 CheckerBase *Checker; 74 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 75 RET operator()(P1 p1, P2 p2, P3 p3, P4 p4) const { 76 return Fn(Checker, p1, p2, p3, p4); 77 } 78 }; 79 80 template <typename RET, typename P1, typename P2, typename P3> 81 class CheckerFn<RET(P1, P2, P3)> { 82 typedef RET (*Func)(void *, P1, P2, P3); 83 Func Fn; 84 public: 85 CheckerBase *Checker; 86 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 87 RET operator()(P1 p1, P2 p2, P3 p3) const { return Fn(Checker, p1, p2, p3); } 88 }; 89 90 template <typename RET, typename P1, typename P2> 91 class CheckerFn<RET(P1, P2)> { 92 typedef RET (*Func)(void *, P1, P2); 93 Func Fn; 94 public: 95 CheckerBase *Checker; 96 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 97 RET operator()(P1 p1, P2 p2) const { return Fn(Checker, p1, p2); } 98 }; 99 100 template <typename RET, typename P1> 101 class CheckerFn<RET(P1)> { 102 typedef RET (*Func)(void *, P1); 103 Func Fn; 104 public: 105 CheckerBase *Checker; 106 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 107 RET operator()(P1 p1) const { return Fn(Checker, p1); } 108 }; 109 110 template <typename RET> 111 class CheckerFn<RET()> { 112 typedef RET (*Func)(void *); 113 Func Fn; 114 public: 115 CheckerBase *Checker; 116 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 117 RET operator()() const { return Fn(Checker); } 118 }; 119 120 class CheckerManager { 121 const LangOptions LangOpts; 122 123 public: 124 CheckerManager(const LangOptions &langOpts) : LangOpts(langOpts) { } 125 ~CheckerManager(); 126 127 bool hasPathSensitiveCheckers() const; 128 129 void finishedCheckerRegistration(); 130 131 const LangOptions &getLangOpts() const { return LangOpts; } 132 133 typedef CheckerBase *CheckerRef; 134 typedef const void *CheckerTag; 135 typedef CheckerFn<void ()> CheckerDtor; 136 137 //===----------------------------------------------------------------------===// 138 // registerChecker 139 //===----------------------------------------------------------------------===// 140 141 /// \brief Used to register checkers. 142 /// 143 /// \returns a pointer to the checker object. 144 template <typename CHECKER> 145 CHECKER *registerChecker() { 146 CheckerTag tag = getTag<CHECKER>(); 147 CheckerRef &ref = CheckerTags[tag]; 148 if (ref) 149 return static_cast<CHECKER *>(ref); // already registered. 150 151 CHECKER *checker = new CHECKER(); 152 CheckerDtors.push_back(CheckerDtor(checker, destruct<CHECKER>)); 153 CHECKER::_register(checker, *this); 154 ref = checker; 155 return checker; 156 } 157 158 //===----------------------------------------------------------------------===// 159 // Functions for running checkers for AST traversing.. 160 //===----------------------------------------------------------------------===// 161 162 /// \brief Run checkers handling Decls. 163 void runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr, 164 BugReporter &BR); 165 166 /// \brief Run checkers handling Decls containing a Stmt body. 167 void runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr, 168 BugReporter &BR); 169 170 //===----------------------------------------------------------------------===// 171 // Functions for running checkers for path-sensitive checking. 172 //===----------------------------------------------------------------------===// 173 174 /// \brief Run checkers for pre-visiting Stmts. 175 /// 176 /// The notification is performed for every explored CFGElement, which does 177 /// not include the control flow statements such as IfStmt. 178 /// 179 /// \sa runCheckersForBranchCondition, runCheckersForPostStmt 180 void runCheckersForPreStmt(ExplodedNodeSet &Dst, 181 const ExplodedNodeSet &Src, 182 const Stmt *S, 183 ExprEngine &Eng) { 184 runCheckersForStmt(/*isPreVisit=*/true, Dst, Src, S, Eng); 185 } 186 187 /// \brief Run checkers for post-visiting Stmts. 188 /// 189 /// The notification is performed for every explored CFGElement, which does 190 /// not include the control flow statements such as IfStmt. 191 /// 192 /// \sa runCheckersForBranchCondition, runCheckersForPreStmt 193 void runCheckersForPostStmt(ExplodedNodeSet &Dst, 194 const ExplodedNodeSet &Src, 195 const Stmt *S, 196 ExprEngine &Eng, 197 bool wasInlined = false) { 198 runCheckersForStmt(/*isPreVisit=*/false, Dst, Src, S, Eng, wasInlined); 199 } 200 201 /// \brief Run checkers for visiting Stmts. 202 void runCheckersForStmt(bool isPreVisit, 203 ExplodedNodeSet &Dst, const ExplodedNodeSet &Src, 204 const Stmt *S, ExprEngine &Eng, 205 bool wasInlined = false); 206 207 /// \brief Run checkers for pre-visiting obj-c messages. 208 void runCheckersForPreObjCMessage(ExplodedNodeSet &Dst, 209 const ExplodedNodeSet &Src, 210 const ObjCMessage &msg, 211 ExprEngine &Eng) { 212 runCheckersForObjCMessage(/*isPreVisit=*/true, Dst, Src, msg, Eng); 213 } 214 215 /// \brief Run checkers for post-visiting obj-c messages. 216 void runCheckersForPostObjCMessage(ExplodedNodeSet &Dst, 217 const ExplodedNodeSet &Src, 218 const ObjCMessage &msg, 219 ExprEngine &Eng) { 220 runCheckersForObjCMessage(/*isPreVisit=*/false, Dst, Src, msg, Eng); 221 } 222 223 /// \brief Run checkers for visiting obj-c messages. 224 void runCheckersForObjCMessage(bool isPreVisit, 225 ExplodedNodeSet &Dst, 226 const ExplodedNodeSet &Src, 227 const ObjCMessage &msg, ExprEngine &Eng); 228 229 /// \brief Run checkers for load/store of a location. 230 void runCheckersForLocation(ExplodedNodeSet &Dst, 231 const ExplodedNodeSet &Src, 232 SVal location, 233 bool isLoad, 234 const Stmt *NodeEx, 235 const Stmt *BoundEx, 236 ExprEngine &Eng); 237 238 /// \brief Run checkers for binding of a value to a location. 239 void runCheckersForBind(ExplodedNodeSet &Dst, 240 const ExplodedNodeSet &Src, 241 SVal location, SVal val, 242 const Stmt *S, ExprEngine &Eng, 243 ProgramPoint::Kind PointKind); 244 245 /// \brief Run checkers for end of analysis. 246 void runCheckersForEndAnalysis(ExplodedGraph &G, BugReporter &BR, 247 ExprEngine &Eng); 248 249 /// \brief Run checkers for end of path. 250 void runCheckersForEndPath(NodeBuilderContext &BC, 251 ExplodedNodeSet &Dst, 252 ExprEngine &Eng); 253 254 /// \brief Run checkers for branch condition. 255 void runCheckersForBranchCondition(const Stmt *condition, 256 ExplodedNodeSet &Dst, ExplodedNode *Pred, 257 ExprEngine &Eng); 258 259 /// \brief Run checkers for live symbols. 260 /// 261 /// Allows modifying SymbolReaper object. For example, checkers can explicitly 262 /// register symbols of interest as live. These symbols will not be marked 263 /// dead and removed. 264 void runCheckersForLiveSymbols(ProgramStateRef state, 265 SymbolReaper &SymReaper); 266 267 /// \brief Run checkers for dead symbols. 268 /// 269 /// Notifies checkers when symbols become dead. For example, this allows 270 /// checkers to aggressively clean up/reduce the checker state and produce 271 /// precise diagnostics. 272 void runCheckersForDeadSymbols(ExplodedNodeSet &Dst, 273 const ExplodedNodeSet &Src, 274 SymbolReaper &SymReaper, const Stmt *S, 275 ExprEngine &Eng); 276 277 /// \brief True if at least one checker wants to check region changes. 278 bool wantsRegionChangeUpdate(ProgramStateRef state); 279 280 /// \brief Run checkers for region changes. 281 /// 282 /// This corresponds to the check::RegionChanges callback. 283 /// \param state The current program state. 284 /// \param invalidated A set of all symbols potentially touched by the change. 285 /// \param ExplicitRegions The regions explicitly requested for invalidation. 286 /// For example, in the case of a function call, these would be arguments. 287 /// \param Regions The transitive closure of accessible regions, 288 /// i.e. all regions that may have been touched by this change. 289 /// \param The call expression wrapper if the regions are invalidated by a 290 /// call. 291 ProgramStateRef 292 runCheckersForRegionChanges(ProgramStateRef state, 293 const StoreManager::InvalidatedSymbols *invalidated, 294 ArrayRef<const MemRegion *> ExplicitRegions, 295 ArrayRef<const MemRegion *> Regions, 296 const CallOrObjCMessage *Call); 297 298 /// \brief Run checkers for handling assumptions on symbolic values. 299 ProgramStateRef runCheckersForEvalAssume(ProgramStateRef state, 300 SVal Cond, bool Assumption); 301 302 /// \brief Run checkers for evaluating a call. 303 void runCheckersForEvalCall(ExplodedNodeSet &Dst, 304 const ExplodedNodeSet &Src, 305 const CallExpr *CE, ExprEngine &Eng, 306 GraphExpander *defaultEval = 0); 307 308 /// \brief Run checkers for the entire Translation Unit. 309 void runCheckersOnEndOfTranslationUnit(const TranslationUnitDecl *TU, 310 AnalysisManager &mgr, 311 BugReporter &BR); 312 313 /// \brief Run checkers for debug-printing a ProgramState. 314 /// 315 /// Unlike most other callbacks, any checker can simply implement the virtual 316 /// method CheckerBase::printState if it has custom data to print. 317 /// \param Out The output stream 318 /// \param State The state being printed 319 /// \param NL The preferred representation of a newline. 320 /// \param Sep The preferred separator between different kinds of data. 321 void runCheckersForPrintState(raw_ostream &Out, ProgramStateRef State, 322 const char *NL, const char *Sep); 323 324 //===----------------------------------------------------------------------===// 325 // Internal registration functions for AST traversing. 326 //===----------------------------------------------------------------------===// 327 328 // Functions used by the registration mechanism, checkers should not touch 329 // these directly. 330 331 typedef CheckerFn<void (const Decl *, AnalysisManager&, BugReporter &)> 332 CheckDeclFunc; 333 334 typedef bool (*HandlesDeclFunc)(const Decl *D); 335 void _registerForDecl(CheckDeclFunc checkfn, HandlesDeclFunc isForDeclFn); 336 337 void _registerForBody(CheckDeclFunc checkfn); 338 339 //===----------------------------------------------------------------------===// 340 // Internal registration functions for path-sensitive checking. 341 //===----------------------------------------------------------------------===// 342 343 typedef CheckerFn<void (const Stmt *, CheckerContext &)> CheckStmtFunc; 344 345 typedef CheckerFn<void (const ObjCMessage &, CheckerContext &)> 346 CheckObjCMessageFunc; 347 348 typedef CheckerFn<void (const SVal &location, bool isLoad, 349 const Stmt *S, 350 CheckerContext &)> 351 CheckLocationFunc; 352 353 typedef CheckerFn<void (const SVal &location, const SVal &val, 354 const Stmt *S, CheckerContext &)> 355 CheckBindFunc; 356 357 typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)> 358 CheckEndAnalysisFunc; 359 360 typedef CheckerFn<void (CheckerContext &)> 361 CheckEndPathFunc; 362 363 typedef CheckerFn<void (const Stmt *, CheckerContext &)> 364 CheckBranchConditionFunc; 365 366 typedef CheckerFn<void (SymbolReaper &, CheckerContext &)> 367 CheckDeadSymbolsFunc; 368 369 typedef CheckerFn<void (ProgramStateRef,SymbolReaper &)> CheckLiveSymbolsFunc; 370 371 typedef CheckerFn<ProgramStateRef (ProgramStateRef, 372 const StoreManager::InvalidatedSymbols *symbols, 373 ArrayRef<const MemRegion *> ExplicitRegions, 374 ArrayRef<const MemRegion *> Regions, 375 const CallOrObjCMessage *Call)> 376 CheckRegionChangesFunc; 377 378 typedef CheckerFn<bool (ProgramStateRef)> WantsRegionChangeUpdateFunc; 379 380 typedef CheckerFn<ProgramStateRef (ProgramStateRef, 381 const SVal &cond, bool assumption)> 382 EvalAssumeFunc; 383 384 typedef CheckerFn<bool (const CallExpr *, CheckerContext &)> 385 EvalCallFunc; 386 387 typedef CheckerFn<bool (const CallExpr *, ExprEngine &Eng, 388 ExplodedNode *Pred, 389 ExplodedNodeSet &Dst)> 390 InlineCallFunc; 391 392 typedef CheckerFn<void (const TranslationUnitDecl *, 393 AnalysisManager&, BugReporter &)> 394 CheckEndOfTranslationUnit; 395 396 typedef bool (*HandlesStmtFunc)(const Stmt *D); 397 void _registerForPreStmt(CheckStmtFunc checkfn, 398 HandlesStmtFunc isForStmtFn); 399 void _registerForPostStmt(CheckStmtFunc checkfn, 400 HandlesStmtFunc isForStmtFn); 401 402 void _registerForPreObjCMessage(CheckObjCMessageFunc checkfn); 403 void _registerForPostObjCMessage(CheckObjCMessageFunc checkfn); 404 405 void _registerForLocation(CheckLocationFunc checkfn); 406 407 void _registerForBind(CheckBindFunc checkfn); 408 409 void _registerForEndAnalysis(CheckEndAnalysisFunc checkfn); 410 411 void _registerForEndPath(CheckEndPathFunc checkfn); 412 413 void _registerForBranchCondition(CheckBranchConditionFunc checkfn); 414 415 void _registerForLiveSymbols(CheckLiveSymbolsFunc checkfn); 416 417 void _registerForDeadSymbols(CheckDeadSymbolsFunc checkfn); 418 419 void _registerForRegionChanges(CheckRegionChangesFunc checkfn, 420 WantsRegionChangeUpdateFunc wantUpdateFn); 421 422 void _registerForEvalAssume(EvalAssumeFunc checkfn); 423 424 void _registerForEvalCall(EvalCallFunc checkfn); 425 426 void _registerForInlineCall(InlineCallFunc checkfn); 427 428 void _registerForEndOfTranslationUnit(CheckEndOfTranslationUnit checkfn); 429 430 //===----------------------------------------------------------------------===// 431 // Internal registration functions for events. 432 //===----------------------------------------------------------------------===// 433 434 typedef void *EventTag; 435 typedef CheckerFn<void (const void *event)> CheckEventFunc; 436 437 template <typename EVENT> 438 void _registerListenerForEvent(CheckEventFunc checkfn) { 439 EventInfo &info = Events[getTag<EVENT>()]; 440 info.Checkers.push_back(checkfn); 441 } 442 443 template <typename EVENT> 444 void _registerDispatcherForEvent() { 445 EventInfo &info = Events[getTag<EVENT>()]; 446 info.HasDispatcher = true; 447 } 448 449 template <typename EVENT> 450 void _dispatchEvent(const EVENT &event) const { 451 EventsTy::const_iterator I = Events.find(getTag<EVENT>()); 452 if (I == Events.end()) 453 return; 454 const EventInfo &info = I->second; 455 for (unsigned i = 0, e = info.Checkers.size(); i != e; ++i) 456 info.Checkers[i](&event); 457 } 458 459 //===----------------------------------------------------------------------===// 460 // Implementation details. 461 //===----------------------------------------------------------------------===// 462 463 private: 464 template <typename CHECKER> 465 static void destruct(void *obj) { delete static_cast<CHECKER *>(obj); } 466 467 template <typename T> 468 static void *getTag() { static int tag; return &tag; } 469 470 llvm::DenseMap<CheckerTag, CheckerRef> CheckerTags; 471 472 std::vector<CheckerDtor> CheckerDtors; 473 474 struct DeclCheckerInfo { 475 CheckDeclFunc CheckFn; 476 HandlesDeclFunc IsForDeclFn; 477 }; 478 std::vector<DeclCheckerInfo> DeclCheckers; 479 480 std::vector<CheckDeclFunc> BodyCheckers; 481 482 typedef SmallVector<CheckDeclFunc, 4> CachedDeclCheckers; 483 typedef llvm::DenseMap<unsigned, CachedDeclCheckers> CachedDeclCheckersMapTy; 484 CachedDeclCheckersMapTy CachedDeclCheckersMap; 485 486 struct StmtCheckerInfo { 487 CheckStmtFunc CheckFn; 488 HandlesStmtFunc IsForStmtFn; 489 bool IsPreVisit; 490 }; 491 std::vector<StmtCheckerInfo> StmtCheckers; 492 493 struct CachedStmtCheckersKey { 494 unsigned StmtKind; 495 bool IsPreVisit; 496 497 CachedStmtCheckersKey() : StmtKind(0), IsPreVisit(0) { } 498 CachedStmtCheckersKey(unsigned stmtKind, bool isPreVisit) 499 : StmtKind(stmtKind), IsPreVisit(isPreVisit) { } 500 501 static CachedStmtCheckersKey getSentinel() { 502 return CachedStmtCheckersKey(~0U, 0); 503 } 504 unsigned getHashValue() const { 505 llvm::FoldingSetNodeID ID; 506 ID.AddInteger(StmtKind); 507 ID.AddBoolean(IsPreVisit); 508 return ID.ComputeHash(); 509 } 510 bool operator==(const CachedStmtCheckersKey &RHS) const { 511 return StmtKind == RHS.StmtKind && IsPreVisit == RHS.IsPreVisit; 512 } 513 }; 514 friend struct llvm::DenseMapInfo<CachedStmtCheckersKey>; 515 516 typedef SmallVector<CheckStmtFunc, 4> CachedStmtCheckers; 517 typedef llvm::DenseMap<CachedStmtCheckersKey, CachedStmtCheckers> 518 CachedStmtCheckersMapTy; 519 CachedStmtCheckersMapTy CachedStmtCheckersMap; 520 521 CachedStmtCheckers *getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit); 522 523 std::vector<CheckObjCMessageFunc> PreObjCMessageCheckers; 524 std::vector<CheckObjCMessageFunc> PostObjCMessageCheckers; 525 526 std::vector<CheckLocationFunc> LocationCheckers; 527 528 std::vector<CheckBindFunc> BindCheckers; 529 530 std::vector<CheckEndAnalysisFunc> EndAnalysisCheckers; 531 532 std::vector<CheckEndPathFunc> EndPathCheckers; 533 534 std::vector<CheckBranchConditionFunc> BranchConditionCheckers; 535 536 std::vector<CheckLiveSymbolsFunc> LiveSymbolsCheckers; 537 538 std::vector<CheckDeadSymbolsFunc> DeadSymbolsCheckers; 539 540 struct RegionChangesCheckerInfo { 541 CheckRegionChangesFunc CheckFn; 542 WantsRegionChangeUpdateFunc WantUpdateFn; 543 }; 544 std::vector<RegionChangesCheckerInfo> RegionChangesCheckers; 545 546 std::vector<EvalAssumeFunc> EvalAssumeCheckers; 547 548 std::vector<EvalCallFunc> EvalCallCheckers; 549 550 std::vector<InlineCallFunc> InlineCallCheckers; 551 552 std::vector<CheckEndOfTranslationUnit> EndOfTranslationUnitCheckers; 553 554 struct EventInfo { 555 SmallVector<CheckEventFunc, 4> Checkers; 556 bool HasDispatcher; 557 EventInfo() : HasDispatcher(false) { } 558 }; 559 560 typedef llvm::DenseMap<EventTag, EventInfo> EventsTy; 561 EventsTy Events; 562 }; 563 564 } // end ento namespace 565 566 } // end clang namespace 567 568 namespace llvm { 569 /// Define DenseMapInfo so that CachedStmtCheckersKey can be used as key 570 /// in DenseMap and DenseSets. 571 template <> 572 struct DenseMapInfo<clang::ento::CheckerManager::CachedStmtCheckersKey> { 573 static inline clang::ento::CheckerManager::CachedStmtCheckersKey 574 getEmptyKey() { 575 return clang::ento::CheckerManager::CachedStmtCheckersKey(); 576 } 577 static inline clang::ento::CheckerManager::CachedStmtCheckersKey 578 getTombstoneKey() { 579 return clang::ento::CheckerManager::CachedStmtCheckersKey::getSentinel(); 580 } 581 582 static unsigned 583 getHashValue(clang::ento::CheckerManager::CachedStmtCheckersKey S) { 584 return S.getHashValue(); 585 } 586 587 static bool isEqual(clang::ento::CheckerManager::CachedStmtCheckersKey LHS, 588 clang::ento::CheckerManager::CachedStmtCheckersKey RHS) { 589 return LHS == RHS; 590 } 591 }; 592 } // end namespace llvm 593 594 #endif 595