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