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