CheckerManager.h revision ca804539d908d3a0e8c72a0df5f1f571d29490bb 
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 GRState;
41  class EndOfFunctionNodeBuilder;
42  class BranchNodeBuilder;
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  void runCheckersForPreStmt(ExplodedNodeSet &Dst,
162                             const ExplodedNodeSet &Src,
163                             const Stmt *S,
164                             ExprEngine &Eng) {
165    runCheckersForStmt(/*isPreVisit=*/true, Dst, Src, S, Eng);
166  }
167
168  /// \brief Run checkers for post-visiting Stmts.
169  void runCheckersForPostStmt(ExplodedNodeSet &Dst,
170                              const ExplodedNodeSet &Src,
171                              const Stmt *S,
172                              ExprEngine &Eng) {
173    runCheckersForStmt(/*isPreVisit=*/false, Dst, Src, S, Eng);
174  }
175
176  /// \brief Run checkers for visiting Stmts.
177  void runCheckersForStmt(bool isPreVisit,
178                          ExplodedNodeSet &Dst, const ExplodedNodeSet &Src,
179                          const Stmt *S, ExprEngine &Eng);
180
181  /// \brief Run checkers for pre-visiting obj-c messages.
182  void runCheckersForPreObjCMessage(ExplodedNodeSet &Dst,
183                                    const ExplodedNodeSet &Src,
184                                    const ObjCMessage &msg,
185                                    ExprEngine &Eng) {
186    runCheckersForObjCMessage(/*isPreVisit=*/true, Dst, Src, msg, Eng);
187  }
188
189  /// \brief Run checkers for post-visiting obj-c messages.
190  void runCheckersForPostObjCMessage(ExplodedNodeSet &Dst,
191                                     const ExplodedNodeSet &Src,
192                                     const ObjCMessage &msg,
193                                     ExprEngine &Eng) {
194    runCheckersForObjCMessage(/*isPreVisit=*/false, Dst, Src, msg, Eng);
195  }
196
197  /// \brief Run checkers for visiting obj-c messages.
198  void runCheckersForObjCMessage(bool isPreVisit,
199                                 ExplodedNodeSet &Dst,
200                                 const ExplodedNodeSet &Src,
201                                 const ObjCMessage &msg, ExprEngine &Eng);
202
203  /// \brief Run checkers for load/store of a location.
204  void runCheckersForLocation(ExplodedNodeSet &Dst,
205                              const ExplodedNodeSet &Src,
206                              SVal location, bool isLoad,
207                              const Stmt *S,
208                              ExprEngine &Eng);
209
210  /// \brief Run checkers for binding of a value to a location.
211  void runCheckersForBind(ExplodedNodeSet &Dst,
212                          const ExplodedNodeSet &Src,
213                          SVal location, SVal val,
214                          const Stmt *S, ExprEngine &Eng);
215
216  /// \brief Run checkers for end of analysis.
217  void runCheckersForEndAnalysis(ExplodedGraph &G, BugReporter &BR,
218                                 ExprEngine &Eng);
219
220  /// \brief Run checkers for end of path.
221  void runCheckersForEndPath(EndOfFunctionNodeBuilder &B, ExprEngine &Eng);
222
223  /// \brief Run checkers for branch condition.
224  void runCheckersForBranchCondition(const Stmt *condition,
225                                     BranchNodeBuilder &B, ExprEngine &Eng);
226
227  /// \brief Run checkers for live symbols.
228  void runCheckersForLiveSymbols(const GRState *state,
229                                 SymbolReaper &SymReaper);
230
231  /// \brief Run checkers for dead symbols.
232  void runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
233                                 const ExplodedNodeSet &Src,
234                                 SymbolReaper &SymReaper, const Stmt *S,
235                                 ExprEngine &Eng);
236
237  /// \brief True if at least one checker wants to check region changes.
238  bool wantsRegionChangeUpdate(const GRState *state);
239
240  /// \brief Run checkers for region changes.
241  const GRState *
242  runCheckersForRegionChanges(const GRState *state,
243                            const StoreManager::InvalidatedSymbols *invalidated,
244                              const MemRegion * const *Begin,
245                              const MemRegion * const *End);
246
247  /// \brief Run checkers for handling assumptions on symbolic values.
248  const GRState *runCheckersForEvalAssume(const GRState *state,
249                                          SVal Cond, bool Assumption);
250
251  /// \brief Run checkers for evaluating a call.
252  void runCheckersForEvalCall(ExplodedNodeSet &Dst,
253                              const ExplodedNodeSet &Src,
254                              const CallExpr *CE, ExprEngine &Eng,
255                              GraphExpander *defaultEval = 0);
256
257  /// \brief Run checkers for the entire Translation Unit.
258  void runCheckersOnEndOfTranslationUnit(const TranslationUnitDecl* TU,
259                                         AnalysisManager &mgr,
260                                         BugReporter &BR);
261
262//===----------------------------------------------------------------------===//
263// Internal registration functions for AST traversing.
264//===----------------------------------------------------------------------===//
265
266  // Functions used by the registration mechanism, checkers should not touch
267  // these directly.
268
269  typedef CheckerFn<void (const Decl *, AnalysisManager&, BugReporter &)>
270      CheckDeclFunc;
271
272  typedef bool (*HandlesDeclFunc)(const Decl *D);
273  void _registerForDecl(CheckDeclFunc checkfn, HandlesDeclFunc isForDeclFn);
274
275  void _registerForBody(CheckDeclFunc checkfn);
276
277//===----------------------------------------------------------------------===//
278// Internal registration functions for path-sensitive checking.
279//===----------------------------------------------------------------------===//
280
281  typedef CheckerFn<void (const Stmt *, CheckerContext &)> CheckStmtFunc;
282
283  typedef CheckerFn<void (const ObjCMessage &, CheckerContext &)>
284      CheckObjCMessageFunc;
285
286  typedef CheckerFn<void (const SVal &location, bool isLoad, CheckerContext &)>
287      CheckLocationFunc;
288
289  typedef CheckerFn<void (const SVal &location, const SVal &val,
290                          CheckerContext &)> CheckBindFunc;
291
292  typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)>
293      CheckEndAnalysisFunc;
294
295  typedef CheckerFn<void (EndOfFunctionNodeBuilder &, ExprEngine &)>
296      CheckEndPathFunc;
297
298  typedef CheckerFn<void (const Stmt *, BranchNodeBuilder &, ExprEngine &)>
299      CheckBranchConditionFunc;
300
301  typedef CheckerFn<void (SymbolReaper &, CheckerContext &)>
302      CheckDeadSymbolsFunc;
303
304  typedef CheckerFn<void (const GRState *,SymbolReaper &)> CheckLiveSymbolsFunc;
305
306  typedef CheckerFn<const GRState * (const GRState *,
307                                const StoreManager::InvalidatedSymbols *symbols,
308                                     const MemRegion * const *begin,
309                                     const MemRegion * const *end)>
310      CheckRegionChangesFunc;
311
312  typedef CheckerFn<bool (const GRState *)> WantsRegionChangeUpdateFunc;
313
314  typedef CheckerFn<const GRState * (const GRState *,
315                                     const SVal &cond, bool assumption)>
316      EvalAssumeFunc;
317
318  typedef CheckerFn<bool (const CallExpr *, CheckerContext &)>
319      EvalCallFunc;
320
321  typedef CheckerFn<void (const TranslationUnitDecl *,
322                          AnalysisManager&, BugReporter &)>
323      CheckEndOfTranslationUnit;
324
325  typedef bool (*HandlesStmtFunc)(const Stmt *D);
326  void _registerForPreStmt(CheckStmtFunc checkfn,
327                           HandlesStmtFunc isForStmtFn);
328  void _registerForPostStmt(CheckStmtFunc checkfn,
329                            HandlesStmtFunc isForStmtFn);
330
331  void _registerForPreObjCMessage(CheckObjCMessageFunc checkfn);
332  void _registerForPostObjCMessage(CheckObjCMessageFunc checkfn);
333
334  void _registerForLocation(CheckLocationFunc checkfn);
335
336  void _registerForBind(CheckBindFunc checkfn);
337
338  void _registerForEndAnalysis(CheckEndAnalysisFunc checkfn);
339
340  void _registerForEndPath(CheckEndPathFunc checkfn);
341
342  void _registerForBranchCondition(CheckBranchConditionFunc checkfn);
343
344  void _registerForLiveSymbols(CheckLiveSymbolsFunc checkfn);
345
346  void _registerForDeadSymbols(CheckDeadSymbolsFunc checkfn);
347
348  void _registerForRegionChanges(CheckRegionChangesFunc checkfn,
349                                 WantsRegionChangeUpdateFunc wantUpdateFn);
350
351  void _registerForEvalAssume(EvalAssumeFunc checkfn);
352
353  void _registerForEvalCall(EvalCallFunc checkfn);
354
355  void _registerForEndOfTranslationUnit(CheckEndOfTranslationUnit checkfn);
356
357//===----------------------------------------------------------------------===//
358// Internal registration functions for events.
359//===----------------------------------------------------------------------===//
360
361  typedef void *EventTag;
362  typedef CheckerFn<void (const void *event)> CheckEventFunc;
363
364  template <typename EVENT>
365  void _registerListenerForEvent(CheckEventFunc checkfn) {
366    EventInfo &info = Events[getTag<EVENT>()];
367    info.Checkers.push_back(checkfn);
368  }
369
370  template <typename EVENT>
371  void _registerDispatcherForEvent() {
372    EventInfo &info = Events[getTag<EVENT>()];
373    info.HasDispatcher = true;
374  }
375
376  template <typename EVENT>
377  void _dispatchEvent(const EVENT &event) const {
378    EventsTy::const_iterator I = Events.find(getTag<EVENT>());
379    if (I == Events.end())
380      return;
381    const EventInfo &info = I->second;
382    for (unsigned i = 0, e = info.Checkers.size(); i != e; ++i)
383      info.Checkers[i](&event);
384  }
385
386//===----------------------------------------------------------------------===//
387// Implementation details.
388//===----------------------------------------------------------------------===//
389
390private:
391  template <typename CHECKER>
392  static void destruct(void *obj) { delete static_cast<CHECKER *>(obj); }
393
394  template <typename T>
395  static void *getTag() { static int tag; return &tag; }
396
397  llvm::DenseMap<CheckerTag, CheckerRef> CheckerTags;
398
399  std::vector<CheckerDtor> CheckerDtors;
400
401  struct DeclCheckerInfo {
402    CheckDeclFunc CheckFn;
403    HandlesDeclFunc IsForDeclFn;
404  };
405  std::vector<DeclCheckerInfo> DeclCheckers;
406
407  std::vector<CheckDeclFunc> BodyCheckers;
408
409  typedef SmallVector<CheckDeclFunc, 4> CachedDeclCheckers;
410  typedef llvm::DenseMap<unsigned, CachedDeclCheckers> CachedDeclCheckersMapTy;
411  CachedDeclCheckersMapTy CachedDeclCheckersMap;
412
413  struct StmtCheckerInfo {
414    CheckStmtFunc CheckFn;
415    HandlesStmtFunc IsForStmtFn;
416    bool IsPreVisit;
417  };
418  std::vector<StmtCheckerInfo> StmtCheckers;
419
420  struct CachedStmtCheckersKey {
421    unsigned StmtKind;
422    bool IsPreVisit;
423
424    CachedStmtCheckersKey() : StmtKind(0), IsPreVisit(0) { }
425    CachedStmtCheckersKey(unsigned stmtKind, bool isPreVisit)
426      : StmtKind(stmtKind), IsPreVisit(isPreVisit) { }
427
428    static CachedStmtCheckersKey getSentinel() {
429      return CachedStmtCheckersKey(~0U, 0);
430    }
431    unsigned getHashValue() const {
432      llvm::FoldingSetNodeID ID;
433      ID.AddInteger(StmtKind);
434      ID.AddBoolean(IsPreVisit);
435      return ID.ComputeHash();
436    }
437    bool operator==(const CachedStmtCheckersKey &RHS) const {
438      return StmtKind == RHS.StmtKind && IsPreVisit == RHS.IsPreVisit;
439    }
440  };
441  friend struct llvm::DenseMapInfo<CachedStmtCheckersKey>;
442
443  typedef SmallVector<CheckStmtFunc, 4> CachedStmtCheckers;
444  typedef llvm::DenseMap<CachedStmtCheckersKey, CachedStmtCheckers>
445      CachedStmtCheckersMapTy;
446  CachedStmtCheckersMapTy CachedStmtCheckersMap;
447
448  CachedStmtCheckers *getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit);
449
450  std::vector<CheckObjCMessageFunc> PreObjCMessageCheckers;
451  std::vector<CheckObjCMessageFunc> PostObjCMessageCheckers;
452
453  std::vector<CheckLocationFunc> LocationCheckers;
454
455  std::vector<CheckBindFunc> BindCheckers;
456
457  std::vector<CheckEndAnalysisFunc> EndAnalysisCheckers;
458
459  std::vector<CheckEndPathFunc> EndPathCheckers;
460
461  std::vector<CheckBranchConditionFunc> BranchConditionCheckers;
462
463  std::vector<CheckLiveSymbolsFunc> LiveSymbolsCheckers;
464
465  std::vector<CheckDeadSymbolsFunc> DeadSymbolsCheckers;
466
467  struct RegionChangesCheckerInfo {
468    CheckRegionChangesFunc CheckFn;
469    WantsRegionChangeUpdateFunc WantUpdateFn;
470  };
471  std::vector<RegionChangesCheckerInfo> RegionChangesCheckers;
472
473  std::vector<EvalAssumeFunc> EvalAssumeCheckers;
474
475  std::vector<EvalCallFunc> EvalCallCheckers;
476
477  std::vector<CheckEndOfTranslationUnit> EndOfTranslationUnitCheckers;
478
479  struct EventInfo {
480    SmallVector<CheckEventFunc, 4> Checkers;
481    bool HasDispatcher;
482    EventInfo() : HasDispatcher(false) { }
483  };
484
485  typedef llvm::DenseMap<EventTag, EventInfo> EventsTy;
486  EventsTy Events;
487};
488
489} // end ento namespace
490
491} // end clang namespace
492
493namespace llvm {
494  /// Define DenseMapInfo so that CachedStmtCheckersKey can be used as key
495  /// in DenseMap and DenseSets.
496  template <>
497  struct DenseMapInfo<clang::ento::CheckerManager::CachedStmtCheckersKey> {
498    static inline clang::ento::CheckerManager::CachedStmtCheckersKey
499        getEmptyKey() {
500      return clang::ento::CheckerManager::CachedStmtCheckersKey();
501    }
502    static inline clang::ento::CheckerManager::CachedStmtCheckersKey
503        getTombstoneKey() {
504      return clang::ento::CheckerManager::CachedStmtCheckersKey::getSentinel();
505    }
506
507    static unsigned
508        getHashValue(clang::ento::CheckerManager::CachedStmtCheckersKey S) {
509      return S.getHashValue();
510    }
511
512    static bool isEqual(clang::ento::CheckerManager::CachedStmtCheckersKey LHS,
513                       clang::ento::CheckerManager::CachedStmtCheckersKey RHS) {
514      return LHS == RHS;
515    }
516  };
517} // end namespace llvm
518
519#endif
520