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