CheckerManager.h revision 9be6e7ce5788e50c62d40c59b0bbc2ea423683f7 
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 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
45class GraphExpander {
46public:
47  virtual ~GraphExpander();
48  virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) = 0;
49};
50
51template <typename T> class CheckerFn;
52
53template <typename RET, typename P1, typename P2, typename P3, typename P4>
54class CheckerFn<RET(P1, P2, P3, P4)> {
55  typedef RET (*Func)(void *, P1, P2, P3, P4);
56  Func Fn;
57public:
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
65template <typename RET, typename P1, typename P2, typename P3>
66class CheckerFn<RET(P1, P2, P3)> {
67  typedef RET (*Func)(void *, P1, P2, P3);
68  Func Fn;
69public:
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
75template <typename RET, typename P1, typename P2>
76class CheckerFn<RET(P1, P2)> {
77  typedef RET (*Func)(void *, P1, P2);
78  Func Fn;
79public:
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
85template <typename RET, typename P1>
86class CheckerFn<RET(P1)> {
87  typedef RET (*Func)(void *, P1);
88  Func Fn;
89public:
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
95template <typename RET>
96class CheckerFn<RET()> {
97  typedef RET (*Func)(void *);
98  Func Fn;
99public:
100  void *Checker;
101  CheckerFn(void *checker, Func fn) : Fn(fn), Checker(checker) { }
102  RET operator()() const { return Fn(Checker); }
103};
104
105class CheckerManager {
106  const LangOptions LangOpts;
107
108public:
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
389private:
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
492namespace 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
519