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