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