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