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