CheckerManager.h revision cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22
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 24namespace clang { 25 class Decl; 26 class Stmt; 27 class CallExpr; 28 29namespace 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 46class GraphExpander { 47public: 48 virtual ~GraphExpander(); 49 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) = 0; 50}; 51 52template <typename T> class CheckerFn; 53 54template <typename RET, typename P1, typename P2, typename P3, typename P4> 55class CheckerFn<RET(P1, P2, P3, P4)> { 56 typedef RET (*Func)(void *, P1, P2, P3, P4); 57 Func Fn; 58public: 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 66template <typename RET, typename P1, typename P2, typename P3> 67class CheckerFn<RET(P1, P2, P3)> { 68 typedef RET (*Func)(void *, P1, P2, P3); 69 Func Fn; 70public: 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 76template <typename RET, typename P1, typename P2> 77class CheckerFn<RET(P1, P2)> { 78 typedef RET (*Func)(void *, P1, P2); 79 Func Fn; 80public: 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 86template <typename RET, typename P1> 87class CheckerFn<RET(P1)> { 88 typedef RET (*Func)(void *, P1); 89 Func Fn; 90public: 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 96template <typename RET> 97class CheckerFn<RET()> { 98 typedef RET (*Func)(void *); 99 Func Fn; 100public: 101 CheckerBase *Checker; 102 CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { } 103 RET operator()() const { return Fn(Checker); } 104}; 105 106class CheckerManager { 107 const LangOptions LangOpts; 108 109public: 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, ExprEngine &Eng); 236 237 /// \brief Run checkers for live symbols. 238 /// 239 /// Allows modifying SymbolReaper object. For example, checkers can explicitly 240 /// register symbols of interest as live. These symbols will not be marked 241 /// dead and removed. 242 void runCheckersForLiveSymbols(const ProgramState *state, 243 SymbolReaper &SymReaper); 244 245 /// \brief Run checkers for dead symbols. 246 /// 247 /// Notifies checkers when symbols become dead. For example, this allows 248 /// checkers to aggressively clean up/reduce the checker state and produce 249 /// precise diagnostics. 250 void runCheckersForDeadSymbols(ExplodedNodeSet &Dst, 251 const ExplodedNodeSet &Src, 252 SymbolReaper &SymReaper, const Stmt *S, 253 ExprEngine &Eng); 254 255 /// \brief True if at least one checker wants to check region changes. 256 bool wantsRegionChangeUpdate(const ProgramState *state); 257 258 /// \brief Run checkers for region changes. 259 /// 260 /// This corresponds to the check::RegionChanges callback. 261 /// \param state The current program state. 262 /// \param invalidated A set of all symbols potentially touched by the change. 263 /// \param ExplicitRegions The regions explicitly requested for invalidation. 264 /// For example, in the case of a function call, these would be arguments. 265 /// \param Regions The transitive closure of accessible regions, 266 /// i.e. all regions that may have been touched by this change. 267 const ProgramState * 268 runCheckersForRegionChanges(const ProgramState *state, 269 const StoreManager::InvalidatedSymbols *invalidated, 270 ArrayRef<const MemRegion *> ExplicitRegions, 271 ArrayRef<const MemRegion *> Regions); 272 273 /// \brief Run checkers for handling assumptions on symbolic values. 274 const ProgramState *runCheckersForEvalAssume(const ProgramState *state, 275 SVal Cond, bool Assumption); 276 277 /// \brief Run checkers for evaluating a call. 278 void runCheckersForEvalCall(ExplodedNodeSet &Dst, 279 const ExplodedNodeSet &Src, 280 const CallExpr *CE, ExprEngine &Eng, 281 GraphExpander *defaultEval = 0); 282 283 /// \brief Run checkers for the entire Translation Unit. 284 void runCheckersOnEndOfTranslationUnit(const TranslationUnitDecl *TU, 285 AnalysisManager &mgr, 286 BugReporter &BR); 287 288 /// \brief Run checkers for debug-printing a ProgramState. 289 /// 290 /// Unlike most other callbacks, any checker can simply implement the virtual 291 /// method CheckerBase::printState if it has custom data to print. 292 /// \param Out The output stream 293 /// \param State The state being printed 294 /// \param NL The preferred representation of a newline. 295 /// \param Sep The preferred separator between different kinds of data. 296 void runCheckersForPrintState(raw_ostream &Out, const ProgramState *State, 297 const char *NL, const char *Sep); 298 299//===----------------------------------------------------------------------===// 300// Internal registration functions for AST traversing. 301//===----------------------------------------------------------------------===// 302 303 // Functions used by the registration mechanism, checkers should not touch 304 // these directly. 305 306 typedef CheckerFn<void (const Decl *, AnalysisManager&, BugReporter &)> 307 CheckDeclFunc; 308 309 typedef bool (*HandlesDeclFunc)(const Decl *D); 310 void _registerForDecl(CheckDeclFunc checkfn, HandlesDeclFunc isForDeclFn); 311 312 void _registerForBody(CheckDeclFunc checkfn); 313 314//===----------------------------------------------------------------------===// 315// Internal registration functions for path-sensitive checking. 316//===----------------------------------------------------------------------===// 317 318 typedef CheckerFn<void (const Stmt *, CheckerContext &)> CheckStmtFunc; 319 320 typedef CheckerFn<void (const ObjCMessage &, CheckerContext &)> 321 CheckObjCMessageFunc; 322 323 typedef CheckerFn<void (const SVal &location, bool isLoad, const Stmt *S, 324 CheckerContext &)> 325 CheckLocationFunc; 326 327 typedef CheckerFn<void (const SVal &location, const SVal &val, 328 const Stmt *S, CheckerContext &)> 329 CheckBindFunc; 330 331 typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)> 332 CheckEndAnalysisFunc; 333 334 typedef CheckerFn<void (EndOfFunctionNodeBuilder &, ExprEngine &)> 335 CheckEndPathFunc; 336 337 typedef CheckerFn<void (const Stmt *, NodeBuilder &, ExprEngine &)> 338 CheckBranchConditionFunc; 339 340 typedef CheckerFn<void (SymbolReaper &, CheckerContext &)> 341 CheckDeadSymbolsFunc; 342 343 typedef CheckerFn<void (const ProgramState *,SymbolReaper &)> CheckLiveSymbolsFunc; 344 345 typedef CheckerFn<const ProgramState * (const ProgramState *, 346 const StoreManager::InvalidatedSymbols *symbols, 347 ArrayRef<const MemRegion *> ExplicitRegions, 348 ArrayRef<const MemRegion *> Regions)> 349 CheckRegionChangesFunc; 350 351 typedef CheckerFn<bool (const ProgramState *)> WantsRegionChangeUpdateFunc; 352 353 typedef CheckerFn<const ProgramState * (const ProgramState *, 354 const SVal &cond, bool assumption)> 355 EvalAssumeFunc; 356 357 typedef CheckerFn<bool (const CallExpr *, CheckerContext &)> 358 EvalCallFunc; 359 360 typedef CheckerFn<bool (const CallExpr *, ExprEngine &Eng, 361 ExplodedNode *Pred, 362 ExplodedNodeSet &Dst)> 363 InlineCallFunc; 364 365 typedef CheckerFn<void (const TranslationUnitDecl *, 366 AnalysisManager&, BugReporter &)> 367 CheckEndOfTranslationUnit; 368 369 typedef bool (*HandlesStmtFunc)(const Stmt *D); 370 void _registerForPreStmt(CheckStmtFunc checkfn, 371 HandlesStmtFunc isForStmtFn); 372 void _registerForPostStmt(CheckStmtFunc checkfn, 373 HandlesStmtFunc isForStmtFn); 374 375 void _registerForPreObjCMessage(CheckObjCMessageFunc checkfn); 376 void _registerForPostObjCMessage(CheckObjCMessageFunc checkfn); 377 378 void _registerForLocation(CheckLocationFunc checkfn); 379 380 void _registerForBind(CheckBindFunc checkfn); 381 382 void _registerForEndAnalysis(CheckEndAnalysisFunc checkfn); 383 384 void _registerForEndPath(CheckEndPathFunc checkfn); 385 386 void _registerForBranchCondition(CheckBranchConditionFunc checkfn); 387 388 void _registerForLiveSymbols(CheckLiveSymbolsFunc checkfn); 389 390 void _registerForDeadSymbols(CheckDeadSymbolsFunc checkfn); 391 392 void _registerForRegionChanges(CheckRegionChangesFunc checkfn, 393 WantsRegionChangeUpdateFunc wantUpdateFn); 394 395 void _registerForEvalAssume(EvalAssumeFunc checkfn); 396 397 void _registerForEvalCall(EvalCallFunc checkfn); 398 399 void _registerForInlineCall(InlineCallFunc checkfn); 400 401 void _registerForEndOfTranslationUnit(CheckEndOfTranslationUnit checkfn); 402 403//===----------------------------------------------------------------------===// 404// Internal registration functions for events. 405//===----------------------------------------------------------------------===// 406 407 typedef void *EventTag; 408 typedef CheckerFn<void (const void *event)> CheckEventFunc; 409 410 template <typename EVENT> 411 void _registerListenerForEvent(CheckEventFunc checkfn) { 412 EventInfo &info = Events[getTag<EVENT>()]; 413 info.Checkers.push_back(checkfn); 414 } 415 416 template <typename EVENT> 417 void _registerDispatcherForEvent() { 418 EventInfo &info = Events[getTag<EVENT>()]; 419 info.HasDispatcher = true; 420 } 421 422 template <typename EVENT> 423 void _dispatchEvent(const EVENT &event) const { 424 EventsTy::const_iterator I = Events.find(getTag<EVENT>()); 425 if (I == Events.end()) 426 return; 427 const EventInfo &info = I->second; 428 for (unsigned i = 0, e = info.Checkers.size(); i != e; ++i) 429 info.Checkers[i](&event); 430 } 431 432//===----------------------------------------------------------------------===// 433// Implementation details. 434//===----------------------------------------------------------------------===// 435 436private: 437 template <typename CHECKER> 438 static void destruct(void *obj) { delete static_cast<CHECKER *>(obj); } 439 440 template <typename T> 441 static void *getTag() { static int tag; return &tag; } 442 443 llvm::DenseMap<CheckerTag, CheckerRef> CheckerTags; 444 445 std::vector<CheckerDtor> CheckerDtors; 446 447 struct DeclCheckerInfo { 448 CheckDeclFunc CheckFn; 449 HandlesDeclFunc IsForDeclFn; 450 }; 451 std::vector<DeclCheckerInfo> DeclCheckers; 452 453 std::vector<CheckDeclFunc> BodyCheckers; 454 455 typedef SmallVector<CheckDeclFunc, 4> CachedDeclCheckers; 456 typedef llvm::DenseMap<unsigned, CachedDeclCheckers> CachedDeclCheckersMapTy; 457 CachedDeclCheckersMapTy CachedDeclCheckersMap; 458 459 struct StmtCheckerInfo { 460 CheckStmtFunc CheckFn; 461 HandlesStmtFunc IsForStmtFn; 462 bool IsPreVisit; 463 }; 464 std::vector<StmtCheckerInfo> StmtCheckers; 465 466 struct CachedStmtCheckersKey { 467 unsigned StmtKind; 468 bool IsPreVisit; 469 470 CachedStmtCheckersKey() : StmtKind(0), IsPreVisit(0) { } 471 CachedStmtCheckersKey(unsigned stmtKind, bool isPreVisit) 472 : StmtKind(stmtKind), IsPreVisit(isPreVisit) { } 473 474 static CachedStmtCheckersKey getSentinel() { 475 return CachedStmtCheckersKey(~0U, 0); 476 } 477 unsigned getHashValue() const { 478 llvm::FoldingSetNodeID ID; 479 ID.AddInteger(StmtKind); 480 ID.AddBoolean(IsPreVisit); 481 return ID.ComputeHash(); 482 } 483 bool operator==(const CachedStmtCheckersKey &RHS) const { 484 return StmtKind == RHS.StmtKind && IsPreVisit == RHS.IsPreVisit; 485 } 486 }; 487 friend struct llvm::DenseMapInfo<CachedStmtCheckersKey>; 488 489 typedef SmallVector<CheckStmtFunc, 4> CachedStmtCheckers; 490 typedef llvm::DenseMap<CachedStmtCheckersKey, CachedStmtCheckers> 491 CachedStmtCheckersMapTy; 492 CachedStmtCheckersMapTy CachedStmtCheckersMap; 493 494 CachedStmtCheckers *getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit); 495 496 std::vector<CheckObjCMessageFunc> PreObjCMessageCheckers; 497 std::vector<CheckObjCMessageFunc> PostObjCMessageCheckers; 498 499 std::vector<CheckLocationFunc> LocationCheckers; 500 501 std::vector<CheckBindFunc> BindCheckers; 502 503 std::vector<CheckEndAnalysisFunc> EndAnalysisCheckers; 504 505 std::vector<CheckEndPathFunc> EndPathCheckers; 506 507 std::vector<CheckBranchConditionFunc> BranchConditionCheckers; 508 509 std::vector<CheckLiveSymbolsFunc> LiveSymbolsCheckers; 510 511 std::vector<CheckDeadSymbolsFunc> DeadSymbolsCheckers; 512 513 struct RegionChangesCheckerInfo { 514 CheckRegionChangesFunc CheckFn; 515 WantsRegionChangeUpdateFunc WantUpdateFn; 516 }; 517 std::vector<RegionChangesCheckerInfo> RegionChangesCheckers; 518 519 std::vector<EvalAssumeFunc> EvalAssumeCheckers; 520 521 std::vector<EvalCallFunc> EvalCallCheckers; 522 523 std::vector<InlineCallFunc> InlineCallCheckers; 524 525 std::vector<CheckEndOfTranslationUnit> EndOfTranslationUnitCheckers; 526 527 struct EventInfo { 528 SmallVector<CheckEventFunc, 4> Checkers; 529 bool HasDispatcher; 530 EventInfo() : HasDispatcher(false) { } 531 }; 532 533 typedef llvm::DenseMap<EventTag, EventInfo> EventsTy; 534 EventsTy Events; 535}; 536 537} // end ento namespace 538 539} // end clang namespace 540 541namespace llvm { 542 /// Define DenseMapInfo so that CachedStmtCheckersKey can be used as key 543 /// in DenseMap and DenseSets. 544 template <> 545 struct DenseMapInfo<clang::ento::CheckerManager::CachedStmtCheckersKey> { 546 static inline clang::ento::CheckerManager::CachedStmtCheckersKey 547 getEmptyKey() { 548 return clang::ento::CheckerManager::CachedStmtCheckersKey(); 549 } 550 static inline clang::ento::CheckerManager::CachedStmtCheckersKey 551 getTombstoneKey() { 552 return clang::ento::CheckerManager::CachedStmtCheckersKey::getSentinel(); 553 } 554 555 static unsigned 556 getHashValue(clang::ento::CheckerManager::CachedStmtCheckersKey S) { 557 return S.getHashValue(); 558 } 559 560 static bool isEqual(clang::ento::CheckerManager::CachedStmtCheckersKey LHS, 561 clang::ento::CheckerManager::CachedStmtCheckersKey RHS) { 562 return LHS == RHS; 563 } 564 }; 565} // end namespace llvm 566 567#endif 568