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