1 //===--- CheckerManager.cpp - Static Analyzer Checker Manager -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Defines the Static Analyzer Checker Manager.
12 //===----------------------------------------------------------------------===//
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/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
18 #include "clang/Analysis/ProgramPoint.h"
19 #include "clang/AST/DeclBase.h"
21 using namespace clang;
24 bool CheckerManager::hasPathSensitiveCheckers() const {
25 return !StmtCheckers.empty() ||
26 !PreObjCMessageCheckers.empty() ||
27 !PostObjCMessageCheckers.empty() ||
28 !LocationCheckers.empty() ||
29 !BindCheckers.empty() ||
30 !EndAnalysisCheckers.empty() ||
31 !EndPathCheckers.empty() ||
32 !BranchConditionCheckers.empty() ||
33 !LiveSymbolsCheckers.empty() ||
34 !DeadSymbolsCheckers.empty() ||
35 !RegionChangesCheckers.empty() ||
36 !EvalAssumeCheckers.empty() ||
37 !EvalCallCheckers.empty() ||
38 !InlineCallCheckers.empty();
41 void CheckerManager::finishedCheckerRegistration() {
43 // Make sure that for every event that has listeners, there is at least
44 // one dispatcher registered for it.
45 for (llvm::DenseMap<EventTag, EventInfo>::iterator
46 I = Events.begin(), E = Events.end(); I != E; ++I)
47 assert(I->second.HasDispatcher && "No dispatcher registered for an event");
51 //===----------------------------------------------------------------------===//
52 // Functions for running checkers for AST traversing..
53 //===----------------------------------------------------------------------===//
55 void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
59 unsigned DeclKind = D->getKind();
60 CachedDeclCheckers *checkers = 0;
61 CachedDeclCheckersMapTy::iterator CCI = CachedDeclCheckersMap.find(DeclKind);
62 if (CCI != CachedDeclCheckersMap.end()) {
63 checkers = &(CCI->second);
65 // Find the checkers that should run for this Decl and cache them.
66 checkers = &CachedDeclCheckersMap[DeclKind];
67 for (unsigned i = 0, e = DeclCheckers.size(); i != e; ++i) {
68 DeclCheckerInfo &info = DeclCheckers[i];
69 if (info.IsForDeclFn(D))
70 checkers->push_back(info.CheckFn);
75 for (CachedDeclCheckers::iterator
76 I = checkers->begin(), E = checkers->end(); I != E; ++I)
80 void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
82 assert(D && D->hasBody());
84 for (unsigned i = 0, e = BodyCheckers.size(); i != e; ++i)
85 BodyCheckers[i](D, mgr, BR);
88 //===----------------------------------------------------------------------===//
89 // Functions for running checkers for path-sensitive checking.
90 //===----------------------------------------------------------------------===//
92 template <typename CHECK_CTX>
93 static void expandGraphWithCheckers(CHECK_CTX checkCtx,
95 const ExplodedNodeSet &Src) {
97 typename CHECK_CTX::CheckersTy::const_iterator
98 I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
104 ExplodedNodeSet Tmp1, Tmp2;
105 const ExplodedNodeSet *PrevSet = &Src;
107 for (; I != E; ++I) {
108 ExplodedNodeSet *CurrSet = 0;
112 CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
116 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
118 checkCtx.runChecker(*I, *CurrSet, *NI);
120 // Update which NodeSet is the current one.
126 struct CheckStmtContext {
127 typedef SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
129 const CheckersTy &Checkers;
133 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
134 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
136 CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
137 const Stmt *s, ExprEngine &eng)
138 : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { }
140 void runChecker(CheckerManager::CheckStmtFunc checkFn,
141 ExplodedNodeSet &Dst, ExplodedNode *Pred) {
142 // FIXME: Remove respondsToCallback from CheckerContext;
143 ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind :
144 ProgramPoint::PostStmtKind;
145 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
146 Pred->getLocationContext(), checkFn.Checker);
147 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0);
154 /// \brief Run checkers for visiting Stmts.
155 void CheckerManager::runCheckersForStmt(bool isPreVisit,
156 ExplodedNodeSet &Dst,
157 const ExplodedNodeSet &Src,
160 CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
162 expandGraphWithCheckers(C, Dst, Src);
166 struct CheckObjCMessageContext {
167 typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
169 const CheckersTy &Checkers;
170 const ObjCMessage &Msg;
173 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
174 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
176 CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
177 const ObjCMessage &msg, ExprEngine &eng)
178 : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
180 void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
181 ExplodedNodeSet &Dst, ExplodedNode *Pred) {
182 ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind :
183 ProgramPoint::PostStmtKind;
184 const ProgramPoint &L = ProgramPoint::getProgramPoint(Msg.getOriginExpr(),
185 K, Pred->getLocationContext(), checkFn.Checker);
186 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0);
193 /// \brief Run checkers for visiting obj-c messages.
194 void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
195 ExplodedNodeSet &Dst,
196 const ExplodedNodeSet &Src,
197 const ObjCMessage &msg,
199 CheckObjCMessageContext C(isPreVisit,
200 isPreVisit ? PreObjCMessageCheckers
201 : PostObjCMessageCheckers,
203 expandGraphWithCheckers(C, Dst, Src);
207 struct CheckLocationContext {
208 typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
209 const CheckersTy &Checkers;
215 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
216 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
218 CheckLocationContext(const CheckersTy &checkers,
219 SVal loc, bool isLoad, const Stmt *s, ExprEngine &eng)
220 : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { }
222 void runChecker(CheckerManager::CheckLocationFunc checkFn,
223 ExplodedNodeSet &Dst, ExplodedNode *Pred) {
224 ProgramPoint::Kind K = IsLoad ? ProgramPoint::PreLoadKind :
225 ProgramPoint::PreStoreKind;
226 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
227 Pred->getLocationContext(), checkFn.Checker);
228 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0);
230 checkFn(Loc, IsLoad, S, C);
235 /// \brief Run checkers for load/store of a location.
236 void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
237 const ExplodedNodeSet &Src,
238 SVal location, bool isLoad,
239 const Stmt *S, ExprEngine &Eng) {
240 CheckLocationContext C(LocationCheckers, location, isLoad, S, Eng);
241 expandGraphWithCheckers(C, Dst, Src);
245 struct CheckBindContext {
246 typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
247 const CheckersTy &Checkers;
253 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
254 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
256 CheckBindContext(const CheckersTy &checkers,
257 SVal loc, SVal val, const Stmt *s, ExprEngine &eng)
258 : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { }
260 void runChecker(CheckerManager::CheckBindFunc checkFn,
261 ExplodedNodeSet &Dst, ExplodedNode *Pred) {
262 ProgramPoint::Kind K = ProgramPoint::PreStmtKind;
263 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
264 Pred->getLocationContext(), checkFn.Checker);
265 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0);
267 checkFn(Loc, Val, S, C);
272 /// \brief Run checkers for binding of a value to a location.
273 void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
274 const ExplodedNodeSet &Src,
275 SVal location, SVal val,
276 const Stmt *S, ExprEngine &Eng) {
277 CheckBindContext C(BindCheckers, location, val, S, Eng);
278 expandGraphWithCheckers(C, Dst, Src);
281 void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
284 for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
285 EndAnalysisCheckers[i](G, BR, Eng);
288 /// \brief Run checkers for end of path.
289 void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B,
291 for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
292 CheckEndPathFunc fn = EndPathCheckers[i];
293 EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker);
298 /// \brief Run checkers for branch condition.
299 void CheckerManager::runCheckersForBranchCondition(const Stmt *condition,
300 BranchNodeBuilder &B,
302 for (unsigned i = 0, e = BranchConditionCheckers.size(); i != e; ++i) {
303 CheckBranchConditionFunc fn = BranchConditionCheckers[i];
304 fn(condition, B, Eng);
308 /// \brief Run checkers for live symbols.
309 void CheckerManager::runCheckersForLiveSymbols(const ProgramState *state,
310 SymbolReaper &SymReaper) {
311 for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i)
312 LiveSymbolsCheckers[i](state, SymReaper);
316 struct CheckDeadSymbolsContext {
317 typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
318 const CheckersTy &Checkers;
323 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
324 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
326 CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
327 const Stmt *s, ExprEngine &eng)
328 : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
330 void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
331 ExplodedNodeSet &Dst, ExplodedNode *Pred) {
332 ProgramPoint::Kind K = ProgramPoint::PostPurgeDeadSymbolsKind;
333 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
334 Pred->getLocationContext(), checkFn.Checker);
335 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, L, 0);
342 /// \brief Run checkers for dead symbols.
343 void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
344 const ExplodedNodeSet &Src,
345 SymbolReaper &SymReaper,
348 CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng);
349 expandGraphWithCheckers(C, Dst, Src);
352 /// \brief True if at least one checker wants to check region changes.
353 bool CheckerManager::wantsRegionChangeUpdate(const ProgramState *state) {
354 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
355 if (RegionChangesCheckers[i].WantUpdateFn(state))
361 /// \brief Run checkers for region changes.
363 CheckerManager::runCheckersForRegionChanges(const ProgramState *state,
364 const StoreManager::InvalidatedSymbols *invalidated,
365 ArrayRef<const MemRegion *> ExplicitRegions,
366 ArrayRef<const MemRegion *> Regions) {
367 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
368 // If any checker declares the state infeasible (or if it starts that way),
372 state = RegionChangesCheckers[i].CheckFn(state, invalidated,
373 ExplicitRegions, Regions);
378 /// \brief Run checkers for handling assumptions on symbolic values.
380 CheckerManager::runCheckersForEvalAssume(const ProgramState *state,
381 SVal Cond, bool Assumption) {
382 for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
383 // If any checker declares the state infeasible (or if it starts that way),
387 state = EvalAssumeCheckers[i](state, Cond, Assumption);
392 /// \brief Run checkers for evaluating a call.
393 /// Only one checker will evaluate the call.
394 void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
395 const ExplodedNodeSet &Src,
398 GraphExpander *defaultEval) {
399 if (EvalCallCheckers.empty() &&
400 InlineCallCheckers.empty() &&
406 for (ExplodedNodeSet::iterator
407 NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
409 ExplodedNode *Pred = *NI;
410 bool anyEvaluated = false;
412 // First, check if any of the InlineCall callbacks can evaluate the call.
413 assert(InlineCallCheckers.size() <= 1 &&
414 "InlineCall is a special hacky callback to allow intrusive"
415 "evaluation of the call (which simulates inlining). It is "
416 "currently only used by OSAtomicChecker and should go away "
418 for (std::vector<InlineCallFunc>::iterator
419 EI = InlineCallCheckers.begin(), EE = InlineCallCheckers.end();
421 ExplodedNodeSet checkDst;
422 bool evaluated = (*EI)(CE, Eng, Pred, checkDst);
423 assert(!(evaluated && anyEvaluated)
424 && "There are more than one checkers evaluating the call");
427 Dst.insert(checkDst);
429 break; // on release don't check that no other checker also evals.
434 #ifdef NDEBUG // on release don't check that no other checker also evals.
440 // Next, check if any of the EvalCall callbacks can evaluate the call.
441 for (std::vector<EvalCallFunc>::iterator
442 EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
444 ExplodedNodeSet checkDst;
445 ProgramPoint::Kind K = ProgramPoint::PostStmtKind;
446 const ProgramPoint &L = ProgramPoint::getProgramPoint(CE, K,
447 Pred->getLocationContext(), EI->Checker);
448 bool evaluated = false;
449 { // CheckerContext generates transitions(populates checkDest) on
450 // destruction, so introduce the scope to make sure it gets properly
452 CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, L, 0);
453 evaluated = (*EI)(CE, C);
455 assert(!(evaluated && anyEvaluated)
456 && "There are more than one checkers evaluating the call");
459 Dst.insert(checkDst);
461 break; // on release don't check that no other checker also evals.
466 // If none of the checkers evaluated the call, ask ExprEngine to handle it.
469 defaultEval->expandGraph(Dst, Pred);
476 /// \brief Run checkers for the entire Translation Unit.
477 void CheckerManager::runCheckersOnEndOfTranslationUnit(
478 const TranslationUnitDecl *TU,
479 AnalysisManager &mgr,
481 for (unsigned i = 0, e = EndOfTranslationUnitCheckers.size(); i != e; ++i)
482 EndOfTranslationUnitCheckers[i](TU, mgr, BR);
485 void CheckerManager::runCheckersForPrintState(raw_ostream &Out,
486 const ProgramState *State,
487 const char *NL, const char *Sep) {
488 for (llvm::DenseMap<CheckerTag, CheckerRef>::iterator
489 I = CheckerTags.begin(), E = CheckerTags.end(); I != E; ++I)
490 I->second->printState(Out, State, NL, Sep);
493 //===----------------------------------------------------------------------===//
494 // Internal registration functions for AST traversing.
495 //===----------------------------------------------------------------------===//
497 void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
498 HandlesDeclFunc isForDeclFn) {
499 DeclCheckerInfo info = { checkfn, isForDeclFn };
500 DeclCheckers.push_back(info);
503 void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
504 BodyCheckers.push_back(checkfn);
507 //===----------------------------------------------------------------------===//
508 // Internal registration functions for path-sensitive checking.
509 //===----------------------------------------------------------------------===//
511 void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
512 HandlesStmtFunc isForStmtFn) {
513 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
514 StmtCheckers.push_back(info);
516 void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
517 HandlesStmtFunc isForStmtFn) {
518 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
519 StmtCheckers.push_back(info);
522 void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
523 PreObjCMessageCheckers.push_back(checkfn);
525 void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
526 PostObjCMessageCheckers.push_back(checkfn);
529 void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
530 LocationCheckers.push_back(checkfn);
533 void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
534 BindCheckers.push_back(checkfn);
537 void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
538 EndAnalysisCheckers.push_back(checkfn);
541 void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
542 EndPathCheckers.push_back(checkfn);
545 void CheckerManager::_registerForBranchCondition(
546 CheckBranchConditionFunc checkfn) {
547 BranchConditionCheckers.push_back(checkfn);
550 void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
551 LiveSymbolsCheckers.push_back(checkfn);
554 void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
555 DeadSymbolsCheckers.push_back(checkfn);
558 void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
559 WantsRegionChangeUpdateFunc wantUpdateFn) {
560 RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
561 RegionChangesCheckers.push_back(info);
564 void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
565 EvalAssumeCheckers.push_back(checkfn);
568 void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
569 EvalCallCheckers.push_back(checkfn);
572 void CheckerManager::_registerForInlineCall(InlineCallFunc checkfn) {
573 InlineCallCheckers.push_back(checkfn);
576 void CheckerManager::_registerForEndOfTranslationUnit(
577 CheckEndOfTranslationUnit checkfn) {
578 EndOfTranslationUnitCheckers.push_back(checkfn);
581 //===----------------------------------------------------------------------===//
582 // Implementation details.
583 //===----------------------------------------------------------------------===//
585 CheckerManager::CachedStmtCheckers *
586 CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
589 CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
590 CachedStmtCheckers *checkers = 0;
591 CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
592 if (CCI != CachedStmtCheckersMap.end()) {
593 checkers = &(CCI->second);
595 // Find the checkers that should run for this Stmt and cache them.
596 checkers = &CachedStmtCheckersMap[key];
597 for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
598 StmtCheckerInfo &info = StmtCheckers[i];
599 if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
600 checkers->push_back(info.CheckFn);
608 CheckerManager::~CheckerManager() {
609 for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
613 // Anchor for the vtable.
614 GraphExpander::~GraphExpander() { }