contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/CheckerManager.h

   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 BranchNodeBuilder;
  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                                      BranchNodeBuilder &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 *, BranchNodeBuilder &, 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
 436 private:
 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
 541 namespace 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