CheckerManager.h revision af498a28797c075c48d7e943df5f5a8e78ed8eb0
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 "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
22#include "clang/Analysis/ProgramPoint.h"
23#include <vector>
24
25namespace clang {
26  class Decl;
27  class Stmt;
28  class CallExpr;
29
30namespace ento {
31  class CheckerBase;
32  class ExprEngine;
33  class AnalysisManager;
34  class BugReporter;
35  class CheckerContext;
36  class ObjCMessage;
37  class SVal;
38  class ExplodedNode;
39  class ExplodedNodeSet;
40  class ExplodedGraph;
41  class ProgramState;
42  class NodeBuilder;
43  struct NodeBuilderContext;
44  class MemRegion;
45  class SymbolReaper;
46
47class GraphExpander {
48public:
49  virtual ~GraphExpander();
50  virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) = 0;
51};
52
53template <typename T> class CheckerFn;
54
55template <typename RET, typename P1, typename P2, typename P3, typename P4>
56class CheckerFn<RET(P1, P2, P3, P4)> {
57  typedef RET (*Func)(void *, P1, P2, P3, P4);
58  Func Fn;
59public:
60  CheckerBase *Checker;
61  CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { }
62  RET operator()(P1 p1, P2 p2, P3 p3, P4 p4) const {
63    return Fn(Checker, p1, p2, p3, p4);
64  }
65};
66
67template <typename RET, typename P1, typename P2, typename P3>
68class CheckerFn<RET(P1, P2, P3)> {
69  typedef RET (*Func)(void *, P1, P2, P3);
70  Func Fn;
71public:
72  CheckerBase *Checker;
73  CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { }
74  RET operator()(P1 p1, P2 p2, P3 p3) const { return Fn(Checker, p1, p2, p3); }
75};
76
77template <typename RET, typename P1, typename P2>
78class CheckerFn<RET(P1, P2)> {
79  typedef RET (*Func)(void *, P1, P2);
80  Func Fn;
81public:
82  CheckerBase *Checker;
83  CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { }
84  RET operator()(P1 p1, P2 p2) const { return Fn(Checker, p1, p2); }
85};
86
87template <typename RET, typename P1>
88class CheckerFn<RET(P1)> {
89  typedef RET (*Func)(void *, P1);
90  Func Fn;
91public:
92  CheckerBase *Checker;
93  CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { }
94  RET operator()(P1 p1) const { return Fn(Checker, p1); }
95};
96
97template <typename RET>
98class CheckerFn<RET()> {
99  typedef RET (*Func)(void *);
100  Func Fn;
101public:
102  CheckerBase *Checker;
103  CheckerFn(CheckerBase *checker, Func fn) : Fn(fn), Checker(checker) { }
104  RET operator()() const { return Fn(Checker); }
105};
106
107class CheckerManager {
108  const LangOptions LangOpts;
109
110public:
111  CheckerManager(const LangOptions &langOpts) : LangOpts(langOpts) { }
112  ~CheckerManager();
113
114  bool hasPathSensitiveCheckers() const;
115
116  void finishedCheckerRegistration();
117
118  const LangOptions &getLangOptions() const { return LangOpts; }
119
120  typedef CheckerBase *CheckerRef;
121  typedef const void *CheckerTag;
122  typedef CheckerFn<void ()> CheckerDtor;
123
124//===----------------------------------------------------------------------===//
125// registerChecker
126//===----------------------------------------------------------------------===//
127
128  /// \brief Used to register checkers.
129  ///
130  /// \returns a pointer to the checker object.
131  template <typename CHECKER>
132  CHECKER *registerChecker() {
133    CheckerTag tag = getTag<CHECKER>();
134    CheckerRef &ref = CheckerTags[tag];
135    if (ref)
136      return static_cast<CHECKER *>(ref); // already registered.
137
138    CHECKER *checker = new CHECKER();
139    CheckerDtors.push_back(CheckerDtor(checker, destruct<CHECKER>));
140    CHECKER::_register(checker, *this);
141    ref = checker;
142    return checker;
143  }
144
145//===----------------------------------------------------------------------===//
146// Functions for running checkers for AST traversing..
147//===----------------------------------------------------------------------===//
148
149  /// \brief Run checkers handling Decls.
150  void runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
151                            BugReporter &BR);
152
153  /// \brief Run checkers handling Decls containing a Stmt body.
154  void runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
155                            BugReporter &BR);
156
157//===----------------------------------------------------------------------===//
158// Functions for running checkers for path-sensitive checking.
159//===----------------------------------------------------------------------===//
160
161  /// \brief Run checkers for pre-visiting Stmts.
162  ///
163  /// The notification is performed for every explored CFGElement, which does
164  /// not include the control flow statements such as IfStmt.
165  ///
166  /// \sa runCheckersForBranchCondition, runCheckersForPostStmt
167  void runCheckersForPreStmt(ExplodedNodeSet &Dst,
168                             const ExplodedNodeSet &Src,
169                             const Stmt *S,
170                             ExprEngine &Eng) {
171    runCheckersForStmt(/*isPreVisit=*/true, Dst, Src, S, Eng);
172  }
173
174  /// \brief Run checkers for post-visiting Stmts.
175  ///
176  /// The notification is performed for every explored CFGElement, which does
177  /// not include the control flow statements such as IfStmt.
178  ///
179  /// \sa runCheckersForBranchCondition, runCheckersForPreStmt
180  void runCheckersForPostStmt(ExplodedNodeSet &Dst,
181                              const ExplodedNodeSet &Src,
182                              const Stmt *S,
183                              ExprEngine &Eng) {
184    runCheckersForStmt(/*isPreVisit=*/false, Dst, Src, S, Eng);
185  }
186
187  /// \brief Run checkers for visiting Stmts.
188  void runCheckersForStmt(bool isPreVisit,
189                          ExplodedNodeSet &Dst, const ExplodedNodeSet &Src,
190                          const Stmt *S, ExprEngine &Eng);
191
192  /// \brief Run checkers for pre-visiting obj-c messages.
193  void runCheckersForPreObjCMessage(ExplodedNodeSet &Dst,
194                                    const ExplodedNodeSet &Src,
195                                    const ObjCMessage &msg,
196                                    ExprEngine &Eng) {
197    runCheckersForObjCMessage(/*isPreVisit=*/true, Dst, Src, msg, Eng);
198  }
199
200  /// \brief Run checkers for post-visiting obj-c messages.
201  void runCheckersForPostObjCMessage(ExplodedNodeSet &Dst,
202                                     const ExplodedNodeSet &Src,
203                                     const ObjCMessage &msg,
204                                     ExprEngine &Eng) {
205    runCheckersForObjCMessage(/*isPreVisit=*/false, Dst, Src, msg, Eng);
206  }
207
208  /// \brief Run checkers for visiting obj-c messages.
209  void runCheckersForObjCMessage(bool isPreVisit,
210                                 ExplodedNodeSet &Dst,
211                                 const ExplodedNodeSet &Src,
212                                 const ObjCMessage &msg, ExprEngine &Eng);
213
214  /// \brief Run checkers for load/store of a location.
215  void runCheckersForLocation(ExplodedNodeSet &Dst,
216                              const ExplodedNodeSet &Src,
217                              SVal location, bool isLoad,
218                              const Stmt *S,
219                              ExprEngine &Eng);
220
221  /// \brief Run checkers for binding of a value to a location.
222  void runCheckersForBind(ExplodedNodeSet &Dst,
223                          const ExplodedNodeSet &Src,
224                          SVal location, SVal val,
225                          const Stmt *S, ExprEngine &Eng,
226                          ProgramPoint::Kind PointKind);
227
228  /// \brief Run checkers for end of analysis.
229  void runCheckersForEndAnalysis(ExplodedGraph &G, BugReporter &BR,
230                                 ExprEngine &Eng);
231
232  /// \brief Run checkers for end of path.
233  void runCheckersForEndPath(NodeBuilderContext &BC,
234                             ExplodedNodeSet &Dst,
235                             ExprEngine &Eng);
236
237  /// \brief Run checkers for branch condition.
238  void runCheckersForBranchCondition(const Stmt *condition,
239                                     NodeBuilder &B, ExplodedNode *Pred,
240                                     ExprEngine &Eng);
241
242  /// \brief Run checkers for live symbols.
243  ///
244  /// Allows modifying SymbolReaper object. For example, checkers can explicitly
245  /// register symbols of interest as live. These symbols will not be marked
246  /// dead and removed.
247  void runCheckersForLiveSymbols(const ProgramState *state,
248                                 SymbolReaper &SymReaper);
249
250  /// \brief Run checkers for dead symbols.
251  ///
252  /// Notifies checkers when symbols become dead. For example, this allows
253  /// checkers to aggressively clean up/reduce the checker state and produce
254  /// precise diagnostics.
255  void runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
256                                 const ExplodedNodeSet &Src,
257                                 SymbolReaper &SymReaper, const Stmt *S,
258                                 ExprEngine &Eng);
259
260  /// \brief True if at least one checker wants to check region changes.
261  bool wantsRegionChangeUpdate(const ProgramState *state);
262
263  /// \brief Run checkers for region changes.
264  ///
265  /// This corresponds to the check::RegionChanges callback.
266  /// \param state The current program state.
267  /// \param invalidated A set of all symbols potentially touched by the change.
268  /// \param ExplicitRegions The regions explicitly requested for invalidation.
269  ///   For example, in the case of a function call, these would be arguments.
270  /// \param Regions The transitive closure of accessible regions,
271  ///   i.e. all regions that may have been touched by this change.
272  const ProgramState *
273  runCheckersForRegionChanges(const ProgramState *state,
274                            const StoreManager::InvalidatedSymbols *invalidated,
275                              ArrayRef<const MemRegion *> ExplicitRegions,
276                              ArrayRef<const MemRegion *> Regions);
277
278  /// \brief Run checkers for handling assumptions on symbolic values.
279  const ProgramState *runCheckersForEvalAssume(const ProgramState *state,
280                                          SVal Cond, bool Assumption);
281
282  /// \brief Run checkers for evaluating a call.
283  void runCheckersForEvalCall(ExplodedNodeSet &Dst,
284                              const ExplodedNodeSet &Src,
285                              const CallExpr *CE, ExprEngine &Eng,
286                              GraphExpander *defaultEval = 0);
287
288  /// \brief Run checkers for the entire Translation Unit.
289  void runCheckersOnEndOfTranslationUnit(const TranslationUnitDecl *TU,
290                                         AnalysisManager &mgr,
291                                         BugReporter &BR);
292
293  /// \brief Run checkers for debug-printing a ProgramState.
294  ///
295  /// Unlike most other callbacks, any checker can simply implement the virtual
296  /// method CheckerBase::printState if it has custom data to print.
297  /// \param Out The output stream
298  /// \param State The state being printed
299  /// \param NL The preferred representation of a newline.
300  /// \param Sep The preferred separator between different kinds of data.
301  void runCheckersForPrintState(raw_ostream &Out, const ProgramState *State,
302                                const char *NL, const char *Sep);
303
304//===----------------------------------------------------------------------===//
305// Internal registration functions for AST traversing.
306//===----------------------------------------------------------------------===//
307
308  // Functions used by the registration mechanism, checkers should not touch
309  // these directly.
310
311  typedef CheckerFn<void (const Decl *, AnalysisManager&, BugReporter &)>
312      CheckDeclFunc;
313
314  typedef bool (*HandlesDeclFunc)(const Decl *D);
315  void _registerForDecl(CheckDeclFunc checkfn, HandlesDeclFunc isForDeclFn);
316
317  void _registerForBody(CheckDeclFunc checkfn);
318
319//===----------------------------------------------------------------------===//
320// Internal registration functions for path-sensitive checking.
321//===----------------------------------------------------------------------===//
322
323  typedef CheckerFn<void (const Stmt *, CheckerContext &)> CheckStmtFunc;
324
325  typedef CheckerFn<void (const ObjCMessage &, CheckerContext &)>
326      CheckObjCMessageFunc;
327
328  typedef CheckerFn<void (const SVal &location, bool isLoad, const Stmt *S,
329                          CheckerContext &)>
330      CheckLocationFunc;
331
332  typedef CheckerFn<void (const SVal &location, const SVal &val,
333                          const Stmt *S, CheckerContext &)>
334      CheckBindFunc;
335
336  typedef CheckerFn<void (ExplodedGraph &, BugReporter &, ExprEngine &)>
337      CheckEndAnalysisFunc;
338
339  typedef CheckerFn<void (CheckerContext &)>
340      CheckEndPathFunc;
341
342  typedef CheckerFn<void (const Stmt *, NodeBuilder &, ExplodedNode *Pred,
343                          ExprEngine &)>
344      CheckBranchConditionFunc;
345
346  typedef CheckerFn<void (SymbolReaper &, CheckerContext &)>
347      CheckDeadSymbolsFunc;
348
349  typedef CheckerFn<void (const ProgramState *,SymbolReaper &)> CheckLiveSymbolsFunc;
350
351  typedef CheckerFn<const ProgramState * (const ProgramState *,
352                                const StoreManager::InvalidatedSymbols *symbols,
353                                    ArrayRef<const MemRegion *> ExplicitRegions,
354                                          ArrayRef<const MemRegion *> Regions)>
355      CheckRegionChangesFunc;
356
357  typedef CheckerFn<bool (const ProgramState *)> WantsRegionChangeUpdateFunc;
358
359  typedef CheckerFn<const ProgramState * (const ProgramState *,
360                                          const SVal &cond, bool assumption)>
361      EvalAssumeFunc;
362
363  typedef CheckerFn<bool (const CallExpr *, CheckerContext &)>
364      EvalCallFunc;
365
366  typedef CheckerFn<bool (const CallExpr *, ExprEngine &Eng,
367                                            ExplodedNode *Pred,
368                                            ExplodedNodeSet &Dst)>
369      InlineCallFunc;
370
371  typedef CheckerFn<void (const TranslationUnitDecl *,
372                          AnalysisManager&, BugReporter &)>
373      CheckEndOfTranslationUnit;
374
375  typedef bool (*HandlesStmtFunc)(const Stmt *D);
376  void _registerForPreStmt(CheckStmtFunc checkfn,
377                           HandlesStmtFunc isForStmtFn);
378  void _registerForPostStmt(CheckStmtFunc checkfn,
379                            HandlesStmtFunc isForStmtFn);
380
381  void _registerForPreObjCMessage(CheckObjCMessageFunc checkfn);
382  void _registerForPostObjCMessage(CheckObjCMessageFunc checkfn);
383
384  void _registerForLocation(CheckLocationFunc checkfn);
385
386  void _registerForBind(CheckBindFunc checkfn);
387
388  void _registerForEndAnalysis(CheckEndAnalysisFunc checkfn);
389
390  void _registerForEndPath(CheckEndPathFunc checkfn);
391
392  void _registerForBranchCondition(CheckBranchConditionFunc checkfn);
393
394  void _registerForLiveSymbols(CheckLiveSymbolsFunc checkfn);
395
396  void _registerForDeadSymbols(CheckDeadSymbolsFunc checkfn);
397
398  void _registerForRegionChanges(CheckRegionChangesFunc checkfn,
399                                 WantsRegionChangeUpdateFunc wantUpdateFn);
400
401  void _registerForEvalAssume(EvalAssumeFunc checkfn);
402
403  void _registerForEvalCall(EvalCallFunc checkfn);
404
405  void _registerForInlineCall(InlineCallFunc checkfn);
406
407  void _registerForEndOfTranslationUnit(CheckEndOfTranslationUnit checkfn);
408
409//===----------------------------------------------------------------------===//
410// Internal registration functions for events.
411//===----------------------------------------------------------------------===//
412
413  typedef void *EventTag;
414  typedef CheckerFn<void (const void *event)> CheckEventFunc;
415
416  template <typename EVENT>
417  void _registerListenerForEvent(CheckEventFunc checkfn) {
418    EventInfo &info = Events[getTag<EVENT>()];
419    info.Checkers.push_back(checkfn);
420  }
421
422  template <typename EVENT>
423  void _registerDispatcherForEvent() {
424    EventInfo &info = Events[getTag<EVENT>()];
425    info.HasDispatcher = true;
426  }
427
428  template <typename EVENT>
429  void _dispatchEvent(const EVENT &event) const {
430    EventsTy::const_iterator I = Events.find(getTag<EVENT>());
431    if (I == Events.end())
432      return;
433    const EventInfo &info = I->second;
434    for (unsigned i = 0, e = info.Checkers.size(); i != e; ++i)
435      info.Checkers[i](&event);
436  }
437
438//===----------------------------------------------------------------------===//
439// Implementation details.
440//===----------------------------------------------------------------------===//
441
442private:
443  template <typename CHECKER>
444  static void destruct(void *obj) { delete static_cast<CHECKER *>(obj); }
445
446  template <typename T>
447  static void *getTag() { static int tag; return &tag; }
448
449  llvm::DenseMap<CheckerTag, CheckerRef> CheckerTags;
450
451  std::vector<CheckerDtor> CheckerDtors;
452
453  struct DeclCheckerInfo {
454    CheckDeclFunc CheckFn;
455    HandlesDeclFunc IsForDeclFn;
456  };
457  std::vector<DeclCheckerInfo> DeclCheckers;
458
459  std::vector<CheckDeclFunc> BodyCheckers;
460
461  typedef SmallVector<CheckDeclFunc, 4> CachedDeclCheckers;
462  typedef llvm::DenseMap<unsigned, CachedDeclCheckers> CachedDeclCheckersMapTy;
463  CachedDeclCheckersMapTy CachedDeclCheckersMap;
464
465  struct StmtCheckerInfo {
466    CheckStmtFunc CheckFn;
467    HandlesStmtFunc IsForStmtFn;
468    bool IsPreVisit;
469  };
470  std::vector<StmtCheckerInfo> StmtCheckers;
471
472  struct CachedStmtCheckersKey {
473    unsigned StmtKind;
474    bool IsPreVisit;
475
476    CachedStmtCheckersKey() : StmtKind(0), IsPreVisit(0) { }
477    CachedStmtCheckersKey(unsigned stmtKind, bool isPreVisit)
478      : StmtKind(stmtKind), IsPreVisit(isPreVisit) { }
479
480    static CachedStmtCheckersKey getSentinel() {
481      return CachedStmtCheckersKey(~0U, 0);
482    }
483    unsigned getHashValue() const {
484      llvm::FoldingSetNodeID ID;
485      ID.AddInteger(StmtKind);
486      ID.AddBoolean(IsPreVisit);
487      return ID.ComputeHash();
488    }
489    bool operator==(const CachedStmtCheckersKey &RHS) const {
490      return StmtKind == RHS.StmtKind && IsPreVisit == RHS.IsPreVisit;
491    }
492  };
493  friend struct llvm::DenseMapInfo<CachedStmtCheckersKey>;
494
495  typedef SmallVector<CheckStmtFunc, 4> CachedStmtCheckers;
496  typedef llvm::DenseMap<CachedStmtCheckersKey, CachedStmtCheckers>
497      CachedStmtCheckersMapTy;
498  CachedStmtCheckersMapTy CachedStmtCheckersMap;
499
500  CachedStmtCheckers *getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit);
501
502  std::vector<CheckObjCMessageFunc> PreObjCMessageCheckers;
503  std::vector<CheckObjCMessageFunc> PostObjCMessageCheckers;
504
505  std::vector<CheckLocationFunc> LocationCheckers;
506
507  std::vector<CheckBindFunc> BindCheckers;
508
509  std::vector<CheckEndAnalysisFunc> EndAnalysisCheckers;
510
511  std::vector<CheckEndPathFunc> EndPathCheckers;
512
513  std::vector<CheckBranchConditionFunc> BranchConditionCheckers;
514
515  std::vector<CheckLiveSymbolsFunc> LiveSymbolsCheckers;
516
517  std::vector<CheckDeadSymbolsFunc> DeadSymbolsCheckers;
518
519  struct RegionChangesCheckerInfo {
520    CheckRegionChangesFunc CheckFn;
521    WantsRegionChangeUpdateFunc WantUpdateFn;
522  };
523  std::vector<RegionChangesCheckerInfo> RegionChangesCheckers;
524
525  std::vector<EvalAssumeFunc> EvalAssumeCheckers;
526
527  std::vector<EvalCallFunc> EvalCallCheckers;
528
529  std::vector<InlineCallFunc> InlineCallCheckers;
530
531  std::vector<CheckEndOfTranslationUnit> EndOfTranslationUnitCheckers;
532
533  struct EventInfo {
534    SmallVector<CheckEventFunc, 4> Checkers;
535    bool HasDispatcher;
536    EventInfo() : HasDispatcher(false) { }
537  };
538
539  typedef llvm::DenseMap<EventTag, EventInfo> EventsTy;
540  EventsTy Events;
541};
542
543} // end ento namespace
544
545} // end clang namespace
546
547namespace llvm {
548  /// Define DenseMapInfo so that CachedStmtCheckersKey can be used as key
549  /// in DenseMap and DenseSets.
550  template <>
551  struct DenseMapInfo<clang::ento::CheckerManager::CachedStmtCheckersKey> {
552    static inline clang::ento::CheckerManager::CachedStmtCheckersKey
553        getEmptyKey() {
554      return clang::ento::CheckerManager::CachedStmtCheckersKey();
555    }
556    static inline clang::ento::CheckerManager::CachedStmtCheckersKey
557        getTombstoneKey() {
558      return clang::ento::CheckerManager::CachedStmtCheckersKey::getSentinel();
559    }
560
561    static unsigned
562        getHashValue(clang::ento::CheckerManager::CachedStmtCheckersKey S) {
563      return S.getHashValue();
564    }
565
566    static bool isEqual(clang::ento::CheckerManager::CachedStmtCheckersKey LHS,
567                       clang::ento::CheckerManager::CachedStmtCheckersKey RHS) {
568      return LHS == RHS;
569    }
570  };
571} // end namespace llvm
572
573#endif
574