CheckerManager.cpp revision 312dbec867f6b8d6b86fd562c53352cd4db27468 
1//===--- CheckerManager.cpp - Static Analyzer Checker Manager -------------===//
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#include "clang/StaticAnalyzer/Core/CheckerManager.h"
15#include "clang/StaticAnalyzer/Core/CheckerProvider.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
17#include "clang/Analysis/ProgramPoint.h"
18#include "clang/AST/DeclBase.h"
19
20using namespace clang;
21using namespace ento;
22
23//===----------------------------------------------------------------------===//
24// Functions for running checkers for AST traversing..
25//===----------------------------------------------------------------------===//
26
27void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
28                                          BugReporter &BR) {
29  assert(D);
30
31  unsigned DeclKind = D->getKind();
32  CachedDeclCheckers *checkers = 0;
33  CachedDeclCheckersMapTy::iterator CCI = CachedDeclCheckersMap.find(DeclKind);
34  if (CCI != CachedDeclCheckersMap.end()) {
35    checkers = &(CCI->second);
36  } else {
37    // Find the checkers that should run for this Decl and cache them.
38    checkers = &CachedDeclCheckersMap[DeclKind];
39    for (unsigned i = 0, e = DeclCheckers.size(); i != e; ++i) {
40      DeclCheckerInfo &info = DeclCheckers[i];
41      if (info.IsForDeclFn(D))
42        checkers->push_back(info.CheckFn);
43    }
44  }
45
46  assert(checkers);
47  for (CachedDeclCheckers::iterator
48         I = checkers->begin(), E = checkers->end(); I != E; ++I)
49    (*I)(D, mgr, BR);
50}
51
52void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
53                                          BugReporter &BR) {
54  assert(D && D->hasBody());
55
56  for (unsigned i = 0, e = BodyCheckers.size(); i != e; ++i)
57    BodyCheckers[i](D, mgr, BR);
58}
59
60//===----------------------------------------------------------------------===//
61// Functions for running checkers for path-sensitive checking.
62//===----------------------------------------------------------------------===//
63
64template <typename CHECK_CTX>
65static void expandGraphWithCheckers(CHECK_CTX checkCtx,
66                                    ExplodedNodeSet &Dst,
67                                    const ExplodedNodeSet &Src) {
68
69  typename CHECK_CTX::CheckersTy::const_iterator
70      I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
71  if (I == E) {
72    Dst.insert(Src);
73    return;
74  }
75
76  ExplodedNodeSet Tmp1, Tmp2;
77  const ExplodedNodeSet *PrevSet = &Src;
78
79  for (; I != E; ++I) {
80    ExplodedNodeSet *CurrSet = 0;
81    if (I+1 == E)
82      CurrSet = &Dst;
83    else {
84      CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
85      CurrSet->clear();
86    }
87
88    for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
89         NI != NE; ++NI)
90      checkCtx.runChecker(*I, *CurrSet, *NI);
91
92    // Update which NodeSet is the current one.
93    PrevSet = CurrSet;
94  }
95}
96
97namespace {
98  struct CheckStmtContext {
99    typedef llvm::SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
100    bool IsPreVisit;
101    const CheckersTy &Checkers;
102    const Stmt *S;
103    ExprEngine &Eng;
104
105    CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
106    CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
107
108    CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
109                     const Stmt *s, ExprEngine &eng)
110      : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { }
111
112    void runChecker(CheckerManager::CheckStmtFunc checkFn,
113                    ExplodedNodeSet &Dst, ExplodedNode *Pred) {
114      // FIXME: Remove respondsToCallback from CheckerContext;
115      CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
116                       IsPreVisit ? ProgramPoint::PreStmtKind :
117                                    ProgramPoint::PostStmtKind, 0, S);
118      checkFn(S, C);
119    }
120  };
121}
122
123/// \brief Run checkers for visiting Stmts.
124void CheckerManager::runCheckersForStmt(bool isPreVisit,
125                                        ExplodedNodeSet &Dst,
126                                        const ExplodedNodeSet &Src,
127                                        const Stmt *S,
128                                        ExprEngine &Eng) {
129  CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
130                     S, Eng);
131  expandGraphWithCheckers(C, Dst, Src);
132}
133
134namespace {
135  struct CheckObjCMessageContext {
136    typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
137    bool IsPreVisit;
138    const CheckersTy &Checkers;
139    const ObjCMessage &Msg;
140    ExprEngine &Eng;
141
142    CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
143    CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
144
145    CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
146                            const ObjCMessage &msg, ExprEngine &eng)
147      : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
148
149    void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
150                    ExplodedNodeSet &Dst, ExplodedNode *Pred) {
151      CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
152                       IsPreVisit ? ProgramPoint::PreStmtKind :
153                                    ProgramPoint::PostStmtKind, 0,
154                       Msg.getOriginExpr());
155      checkFn(Msg, C);
156    }
157  };
158}
159
160/// \brief Run checkers for visiting obj-c messages.
161void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
162                                               ExplodedNodeSet &Dst,
163                                               const ExplodedNodeSet &Src,
164                                               const ObjCMessage &msg,
165                                               ExprEngine &Eng) {
166  CheckObjCMessageContext C(isPreVisit,
167                            isPreVisit ? PreObjCMessageCheckers
168                                       : PostObjCMessageCheckers,
169                            msg, Eng);
170  expandGraphWithCheckers(C, Dst, Src);
171}
172
173namespace {
174  struct CheckLocationContext {
175    typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
176    const CheckersTy &Checkers;
177    SVal Loc;
178    bool IsLoad;
179    const Stmt *S;
180    ExprEngine &Eng;
181
182    CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
183    CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
184
185    CheckLocationContext(const CheckersTy &checkers,
186                         SVal loc, bool isLoad, const Stmt *s, ExprEngine &eng)
187      : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { }
188
189    void runChecker(CheckerManager::CheckLocationFunc checkFn,
190                    ExplodedNodeSet &Dst, ExplodedNode *Pred) {
191      CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
192                       IsLoad ? ProgramPoint::PreLoadKind :
193                       ProgramPoint::PreStoreKind, 0, S);
194      checkFn(Loc, IsLoad, C);
195    }
196  };
197}
198
199/// \brief Run checkers for load/store of a location.
200void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
201                                            const ExplodedNodeSet &Src,
202                                            SVal location, bool isLoad,
203                                            const Stmt *S, ExprEngine &Eng) {
204  CheckLocationContext C(LocationCheckers, location, isLoad, S, Eng);
205  expandGraphWithCheckers(C, Dst, Src);
206}
207
208namespace {
209  struct CheckBindContext {
210    typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
211    const CheckersTy &Checkers;
212    SVal Loc;
213    SVal Val;
214    const Stmt *S;
215    ExprEngine &Eng;
216
217    CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
218    CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
219
220    CheckBindContext(const CheckersTy &checkers,
221                     SVal loc, SVal val, const Stmt *s, ExprEngine &eng)
222      : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { }
223
224    void runChecker(CheckerManager::CheckBindFunc checkFn,
225                    ExplodedNodeSet &Dst, ExplodedNode *Pred) {
226      CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
227                       ProgramPoint::PreStmtKind, 0, S);
228      checkFn(Loc, Val, C);
229    }
230  };
231}
232
233/// \brief Run checkers for binding of a value to a location.
234void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
235                                        const ExplodedNodeSet &Src,
236                                        SVal location, SVal val,
237                                        const Stmt *S, ExprEngine &Eng) {
238  CheckBindContext C(BindCheckers, location, val, S, Eng);
239  expandGraphWithCheckers(C, Dst, Src);
240}
241
242void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
243                                               BugReporter &BR,
244                                               ExprEngine &Eng) {
245  for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
246    EndAnalysisCheckers[i](G, BR, Eng);
247}
248
249/// \brief Run checkers for end of path.
250void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B,
251                                           ExprEngine &Eng) {
252  for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
253    CheckEndPathFunc fn = EndPathCheckers[i];
254    EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker);
255    fn(specialB, Eng);
256  }
257}
258
259/// \brief Run checkers for live symbols.
260void CheckerManager::runCheckersForLiveSymbols(const GRState *state,
261                                               SymbolReaper &SymReaper) {
262  for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i)
263    LiveSymbolsCheckers[i](state, SymReaper);
264}
265
266namespace {
267  struct CheckDeadSymbolsContext {
268    typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
269    const CheckersTy &Checkers;
270    SymbolReaper &SR;
271    const Stmt *S;
272    ExprEngine &Eng;
273
274    CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
275    CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
276
277    CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
278                            const Stmt *s, ExprEngine &eng)
279      : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
280
281    void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
282                    ExplodedNodeSet &Dst, ExplodedNode *Pred) {
283      CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
284                       ProgramPoint::PostPurgeDeadSymbolsKind, 0, S);
285      checkFn(SR, C);
286    }
287  };
288}
289
290/// \brief Run checkers for dead symbols.
291void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
292                                               const ExplodedNodeSet &Src,
293                                               SymbolReaper &SymReaper,
294                                               const Stmt *S,
295                                               ExprEngine &Eng) {
296  CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng);
297  expandGraphWithCheckers(C, Dst, Src);
298}
299
300/// \brief True if at least one checker wants to check region changes.
301bool CheckerManager::wantsRegionChangeUpdate(const GRState *state) {
302  for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
303    if (RegionChangesCheckers[i].WantUpdateFn(state))
304      return true;
305
306  return false;
307}
308
309/// \brief Run checkers for region changes.
310const GRState *
311CheckerManager::runCheckersForRegionChanges(const GRState *state,
312                                            const MemRegion * const *Begin,
313                                            const MemRegion * const *End) {
314  for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
315    // If any checker declares the state infeasible (or if it starts that way),
316    // bail out.
317    if (!state)
318      return NULL;
319    state = RegionChangesCheckers[i].CheckFn(state, Begin, End);
320  }
321  return state;
322}
323
324/// \brief Run checkers for handling assumptions on symbolic values.
325const GRState *
326CheckerManager::runCheckersForEvalAssume(const GRState *state,
327                                         SVal Cond, bool Assumption) {
328  for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
329    // If any checker declares the state infeasible (or if it starts that way),
330    // bail out.
331    if (!state)
332      return NULL;
333    state = EvalAssumeCheckers[i](state, Cond, Assumption);
334  }
335  return state;
336}
337
338/// \brief Run checkers for evaluating a call.
339/// Only one checker will evaluate the call.
340void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
341                                            const ExplodedNodeSet &Src,
342                                            const CallExpr *CE,
343                                            ExprEngine &Eng,
344                                            GraphExpander *defaultEval) {
345  if (EvalCallCheckers.empty() && defaultEval == 0) {
346    Dst.insert(Src);
347    return;
348  }
349
350  for (ExplodedNodeSet::iterator
351         NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
352
353    ExplodedNode *Pred = *NI;
354    bool anyEvaluated = false;
355    for (std::vector<EvalCallFunc>::iterator
356           EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
357         EI != EE; ++EI) {
358      ExplodedNodeSet checkDst;
359      CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker,
360                       ProgramPoint::PostStmtKind, 0, CE);
361      bool evaluated = (*EI)(CE, C);
362      assert(!(evaluated && anyEvaluated)
363             && "There are more than one checkers evaluating the call");
364      if (evaluated) {
365        anyEvaluated = true;
366        Dst.insert(checkDst);
367#ifdef NDEBUG
368        break; // on release don't check that no other checker also evals.
369#endif
370      }
371    }
372
373    if (!anyEvaluated) {
374      if (defaultEval)
375        defaultEval->expandGraph(Dst, Pred);
376      else
377        Dst.insert(Pred);
378    }
379  }
380}
381
382//===----------------------------------------------------------------------===//
383// Internal registration functions for AST traversing.
384//===----------------------------------------------------------------------===//
385
386void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
387                                      HandlesDeclFunc isForDeclFn) {
388  DeclCheckerInfo info = { checkfn, isForDeclFn };
389  DeclCheckers.push_back(info);
390}
391
392void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
393  BodyCheckers.push_back(checkfn);
394}
395
396//===----------------------------------------------------------------------===//
397// Internal registration functions for path-sensitive checking.
398//===----------------------------------------------------------------------===//
399
400void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
401                                         HandlesStmtFunc isForStmtFn) {
402  StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
403  StmtCheckers.push_back(info);
404}
405void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
406                                          HandlesStmtFunc isForStmtFn) {
407  StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
408  StmtCheckers.push_back(info);
409}
410
411void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
412  PreObjCMessageCheckers.push_back(checkfn);
413}
414void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
415  PostObjCMessageCheckers.push_back(checkfn);
416}
417
418void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
419  LocationCheckers.push_back(checkfn);
420}
421
422void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
423  BindCheckers.push_back(checkfn);
424}
425
426void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
427  EndAnalysisCheckers.push_back(checkfn);
428}
429
430void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
431  EndPathCheckers.push_back(checkfn);
432}
433
434void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
435  LiveSymbolsCheckers.push_back(checkfn);
436}
437
438void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
439  DeadSymbolsCheckers.push_back(checkfn);
440}
441
442void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
443                                     WantsRegionChangeUpdateFunc wantUpdateFn) {
444  RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
445  RegionChangesCheckers.push_back(info);
446}
447
448void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
449  EvalAssumeCheckers.push_back(checkfn);
450}
451
452void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
453  EvalCallCheckers.push_back(checkfn);
454}
455
456//===----------------------------------------------------------------------===//
457// Implementation details.
458//===----------------------------------------------------------------------===//
459
460CheckerManager::CachedStmtCheckers *
461CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
462  assert(S);
463
464  CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
465  CachedStmtCheckers *checkers = 0;
466  CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
467  if (CCI != CachedStmtCheckersMap.end()) {
468    checkers = &(CCI->second);
469  } else {
470    // Find the checkers that should run for this Stmt and cache them.
471    checkers = &CachedStmtCheckersMap[key];
472    for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
473      StmtCheckerInfo &info = StmtCheckers[i];
474      if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
475        checkers->push_back(info.CheckFn);
476    }
477  }
478
479  assert(checkers);
480  return checkers;
481}
482
483CheckerManager::~CheckerManager() {
484  for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
485    CheckerDtors[i]();
486}
487
488// Anchor for the vtable.
489CheckerProvider::~CheckerProvider() { }
490
491// Anchor for the vtable.
492GraphExpander::~GraphExpander() { }
493