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