CheckerManager.cpp revision 537716ad8dd10f984b6cfe6985afade1185c5e3c 
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/Checker.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 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 ProgramState *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 ProgramState *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 ProgramState *
347CheckerManager::runCheckersForRegionChanges(const ProgramState *state,
348                            const StoreManager::InvalidatedSymbols *invalidated,
349                                    ArrayRef<const MemRegion *> ExplicitRegions,
350                                          ArrayRef<const MemRegion *> Regions) {
351  for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
352    // If any checker declares the state infeasible (or if it starts that way),
353    // bail out.
354    if (!state)
355      return NULL;
356    state = RegionChangesCheckers[i].CheckFn(state, invalidated,
357                                             ExplicitRegions, Regions);
358  }
359  return state;
360}
361
362/// \brief Run checkers for handling assumptions on symbolic values.
363const ProgramState *
364CheckerManager::runCheckersForEvalAssume(const ProgramState *state,
365                                         SVal Cond, bool Assumption) {
366  for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
367    // If any checker declares the state infeasible (or if it starts that way),
368    // bail out.
369    if (!state)
370      return NULL;
371    state = EvalAssumeCheckers[i](state, Cond, Assumption);
372  }
373  return state;
374}
375
376/// \brief Run checkers for evaluating a call.
377/// Only one checker will evaluate the call.
378void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
379                                            const ExplodedNodeSet &Src,
380                                            const CallExpr *CE,
381                                            ExprEngine &Eng,
382                                            GraphExpander *defaultEval) {
383  if (EvalCallCheckers.empty() && defaultEval == 0) {
384    Dst.insert(Src);
385    return;
386  }
387
388  for (ExplodedNodeSet::iterator
389         NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
390
391    ExplodedNode *Pred = *NI;
392    bool anyEvaluated = false;
393    for (std::vector<EvalCallFunc>::iterator
394           EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
395         EI != EE; ++EI) {
396      ExplodedNodeSet checkDst;
397      CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker,
398                       ProgramPoint::PostStmtKind, 0, CE);
399      bool evaluated = (*EI)(CE, C);
400      assert(!(evaluated && anyEvaluated)
401             && "There are more than one checkers evaluating the call");
402      if (evaluated) {
403        anyEvaluated = true;
404        Dst.insert(checkDst);
405#ifdef NDEBUG
406        break; // on release don't check that no other checker also evals.
407#endif
408      }
409    }
410
411    if (!anyEvaluated) {
412      if (defaultEval)
413        defaultEval->expandGraph(Dst, Pred);
414      else
415        Dst.insert(Pred);
416    }
417  }
418}
419
420/// \brief Run checkers for the entire Translation Unit.
421void CheckerManager::runCheckersOnEndOfTranslationUnit(
422                                                  const TranslationUnitDecl *TU,
423                                                  AnalysisManager &mgr,
424                                                  BugReporter &BR) {
425  for (unsigned i = 0, e = EndOfTranslationUnitCheckers.size(); i != e; ++i)
426    EndOfTranslationUnitCheckers[i](TU, mgr, BR);
427}
428
429//===----------------------------------------------------------------------===//
430// Internal registration functions for AST traversing.
431//===----------------------------------------------------------------------===//
432
433void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
434                                      HandlesDeclFunc isForDeclFn) {
435  DeclCheckerInfo info = { checkfn, isForDeclFn };
436  DeclCheckers.push_back(info);
437}
438
439void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
440  BodyCheckers.push_back(checkfn);
441}
442
443//===----------------------------------------------------------------------===//
444// Internal registration functions for path-sensitive checking.
445//===----------------------------------------------------------------------===//
446
447void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
448                                         HandlesStmtFunc isForStmtFn) {
449  StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
450  StmtCheckers.push_back(info);
451}
452void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
453                                          HandlesStmtFunc isForStmtFn) {
454  StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
455  StmtCheckers.push_back(info);
456}
457
458void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
459  PreObjCMessageCheckers.push_back(checkfn);
460}
461void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
462  PostObjCMessageCheckers.push_back(checkfn);
463}
464
465void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
466  LocationCheckers.push_back(checkfn);
467}
468
469void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
470  BindCheckers.push_back(checkfn);
471}
472
473void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
474  EndAnalysisCheckers.push_back(checkfn);
475}
476
477void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
478  EndPathCheckers.push_back(checkfn);
479}
480
481void CheckerManager::_registerForBranchCondition(
482                                             CheckBranchConditionFunc checkfn) {
483  BranchConditionCheckers.push_back(checkfn);
484}
485
486void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
487  LiveSymbolsCheckers.push_back(checkfn);
488}
489
490void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
491  DeadSymbolsCheckers.push_back(checkfn);
492}
493
494void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
495                                     WantsRegionChangeUpdateFunc wantUpdateFn) {
496  RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
497  RegionChangesCheckers.push_back(info);
498}
499
500void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
501  EvalAssumeCheckers.push_back(checkfn);
502}
503
504void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
505  EvalCallCheckers.push_back(checkfn);
506}
507
508void CheckerManager::_registerForEndOfTranslationUnit(
509                                            CheckEndOfTranslationUnit checkfn) {
510  EndOfTranslationUnitCheckers.push_back(checkfn);
511}
512
513//===----------------------------------------------------------------------===//
514// Implementation details.
515//===----------------------------------------------------------------------===//
516
517CheckerManager::CachedStmtCheckers *
518CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
519  assert(S);
520
521  CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
522  CachedStmtCheckers *checkers = 0;
523  CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
524  if (CCI != CachedStmtCheckersMap.end()) {
525    checkers = &(CCI->second);
526  } else {
527    // Find the checkers that should run for this Stmt and cache them.
528    checkers = &CachedStmtCheckersMap[key];
529    for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
530      StmtCheckerInfo &info = StmtCheckers[i];
531      if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
532        checkers->push_back(info.CheckFn);
533    }
534  }
535
536  assert(checkers);
537  return checkers;
538}
539
540CheckerManager::~CheckerManager() {
541  for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
542    CheckerDtors[i]();
543}
544
545// Anchor for the vtable.
546GraphExpander::~GraphExpander() { }
547