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