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