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