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) {
96 const NodeBuilderContext &BldrCtx = checkCtx.Eng.getBuilderContext();
100 typename CHECK_CTX::CheckersTy::const_iterator
101 I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
107 ExplodedNodeSet Tmp1, Tmp2;
108 const ExplodedNodeSet *PrevSet = &Src;
110 for (; I != E; ++I) {
111 ExplodedNodeSet *CurrSet = 0;
115 CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
119 NodeBuilder B(*PrevSet, *CurrSet, BldrCtx);
120 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
122 checkCtx.runChecker(*I, B, *NI);
125 // If all the produced transitions are sinks, stop.
126 if (CurrSet->empty())
129 // Update which NodeSet is the current one.
135 struct CheckStmtContext {
136 typedef SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
138 const CheckersTy &Checkers;
143 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
144 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
146 CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
147 const Stmt *s, ExprEngine &eng, bool wasInlined = false)
148 : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng),
149 wasInlined(wasInlined) {}
151 void runChecker(CheckerManager::CheckStmtFunc checkFn,
152 NodeBuilder &Bldr, ExplodedNode *Pred) {
153 // FIXME: Remove respondsToCallback from CheckerContext;
154 ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind :
155 ProgramPoint::PostStmtKind;
156 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
157 Pred->getLocationContext(), checkFn.Checker);
158 CheckerContext C(Bldr, Eng, Pred, L, wasInlined);
164 /// \brief Run checkers for visiting Stmts.
165 void CheckerManager::runCheckersForStmt(bool isPreVisit,
166 ExplodedNodeSet &Dst,
167 const ExplodedNodeSet &Src,
171 CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
173 expandGraphWithCheckers(C, Dst, Src);
177 struct CheckObjCMessageContext {
178 typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
180 const CheckersTy &Checkers;
181 const ObjCMessage &Msg;
184 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
185 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
187 CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
188 const ObjCMessage &msg, ExprEngine &eng)
189 : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
191 void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
192 NodeBuilder &Bldr, ExplodedNode *Pred) {
193 ProgramPoint::Kind K = IsPreVisit ? ProgramPoint::PreStmtKind :
194 ProgramPoint::PostStmtKind;
195 const ProgramPoint &L =
196 ProgramPoint::getProgramPoint(Msg.getMessageExpr(),
197 K, Pred->getLocationContext(),
199 CheckerContext C(Bldr, Eng, Pred, L);
206 /// \brief Run checkers for visiting obj-c messages.
207 void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
208 ExplodedNodeSet &Dst,
209 const ExplodedNodeSet &Src,
210 const ObjCMessage &msg,
212 CheckObjCMessageContext C(isPreVisit,
213 isPreVisit ? PreObjCMessageCheckers
214 : PostObjCMessageCheckers,
216 expandGraphWithCheckers(C, Dst, Src);
220 struct CheckLocationContext {
221 typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
222 const CheckersTy &Checkers;
225 const Stmt *NodeEx; /* Will become a CFGStmt */
229 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
230 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
232 CheckLocationContext(const CheckersTy &checkers,
233 SVal loc, bool isLoad, const Stmt *NodeEx,
236 : Checkers(checkers), Loc(loc), IsLoad(isLoad), NodeEx(NodeEx),
237 BoundEx(BoundEx), Eng(eng) {}
239 void runChecker(CheckerManager::CheckLocationFunc checkFn,
240 NodeBuilder &Bldr, ExplodedNode *Pred) {
241 ProgramPoint::Kind K = IsLoad ? ProgramPoint::PreLoadKind :
242 ProgramPoint::PreStoreKind;
243 const ProgramPoint &L =
244 ProgramPoint::getProgramPoint(NodeEx, K,
245 Pred->getLocationContext(),
247 CheckerContext C(Bldr, Eng, Pred, L);
248 checkFn(Loc, IsLoad, BoundEx, C);
253 /// \brief Run checkers for load/store of a location.
255 void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
256 const ExplodedNodeSet &Src,
257 SVal location, bool isLoad,
261 CheckLocationContext C(LocationCheckers, location, isLoad, NodeEx,
263 expandGraphWithCheckers(C, Dst, Src);
267 struct CheckBindContext {
268 typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
269 const CheckersTy &Checkers;
274 ProgramPoint::Kind PointKind;
276 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
277 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
279 CheckBindContext(const CheckersTy &checkers,
280 SVal loc, SVal val, const Stmt *s, ExprEngine &eng,
281 ProgramPoint::Kind PK)
282 : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng), PointKind(PK) {}
284 void runChecker(CheckerManager::CheckBindFunc checkFn,
285 NodeBuilder &Bldr, ExplodedNode *Pred) {
286 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, PointKind,
287 Pred->getLocationContext(), checkFn.Checker);
288 CheckerContext C(Bldr, Eng, Pred, L);
290 checkFn(Loc, Val, S, C);
295 /// \brief Run checkers for binding of a value to a location.
296 void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
297 const ExplodedNodeSet &Src,
298 SVal location, SVal val,
299 const Stmt *S, ExprEngine &Eng,
300 ProgramPoint::Kind PointKind) {
301 CheckBindContext C(BindCheckers, location, val, S, Eng, PointKind);
302 expandGraphWithCheckers(C, Dst, Src);
305 void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
308 for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
309 EndAnalysisCheckers[i](G, BR, Eng);
312 /// \brief Run checkers for end of path.
313 // Note, We do not chain the checker output (like in expandGraphWithCheckers)
314 // for this callback since end of path nodes are expected to be final.
315 void CheckerManager::runCheckersForEndPath(NodeBuilderContext &BC,
316 ExplodedNodeSet &Dst,
318 ExplodedNode *Pred = BC.Pred;
320 // We define the builder outside of the loop bacause if at least one checkers
321 // creates a sucsessor for Pred, we do not need to generate an
322 // autotransition for it.
323 NodeBuilder Bldr(Pred, Dst, BC);
324 for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
325 CheckEndPathFunc checkFn = EndPathCheckers[i];
327 const ProgramPoint &L = BlockEntrance(BC.Block,
328 Pred->getLocationContext(),
330 CheckerContext C(Bldr, Eng, Pred, L);
336 struct CheckBranchConditionContext {
337 typedef std::vector<CheckerManager::CheckBranchConditionFunc> CheckersTy;
338 const CheckersTy &Checkers;
339 const Stmt *Condition;
342 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
343 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
345 CheckBranchConditionContext(const CheckersTy &checkers,
346 const Stmt *Cond, ExprEngine &eng)
347 : Checkers(checkers), Condition(Cond), Eng(eng) {}
349 void runChecker(CheckerManager::CheckBranchConditionFunc checkFn,
350 NodeBuilder &Bldr, ExplodedNode *Pred) {
351 ProgramPoint L = PostCondition(Condition, Pred->getLocationContext(),
353 CheckerContext C(Bldr, Eng, Pred, L);
354 checkFn(Condition, C);
359 /// \brief Run checkers for branch condition.
360 void CheckerManager::runCheckersForBranchCondition(const Stmt *Condition,
361 ExplodedNodeSet &Dst,
366 CheckBranchConditionContext C(BranchConditionCheckers, Condition, Eng);
367 expandGraphWithCheckers(C, Dst, Src);
370 /// \brief Run checkers for live symbols.
371 void CheckerManager::runCheckersForLiveSymbols(ProgramStateRef state,
372 SymbolReaper &SymReaper) {
373 for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i)
374 LiveSymbolsCheckers[i](state, SymReaper);
378 struct CheckDeadSymbolsContext {
379 typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
380 const CheckersTy &Checkers;
385 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
386 CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
388 CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
389 const Stmt *s, ExprEngine &eng)
390 : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
392 void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
393 NodeBuilder &Bldr, ExplodedNode *Pred) {
394 ProgramPoint::Kind K = ProgramPoint::PostPurgeDeadSymbolsKind;
395 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
396 Pred->getLocationContext(), checkFn.Checker);
397 CheckerContext C(Bldr, Eng, Pred, L);
404 /// \brief Run checkers for dead symbols.
405 void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
406 const ExplodedNodeSet &Src,
407 SymbolReaper &SymReaper,
410 CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng);
411 expandGraphWithCheckers(C, Dst, Src);
414 /// \brief True if at least one checker wants to check region changes.
415 bool CheckerManager::wantsRegionChangeUpdate(ProgramStateRef state) {
416 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
417 if (RegionChangesCheckers[i].WantUpdateFn(state))
423 /// \brief Run checkers for region changes.
425 CheckerManager::runCheckersForRegionChanges(ProgramStateRef state,
426 const StoreManager::InvalidatedSymbols *invalidated,
427 ArrayRef<const MemRegion *> ExplicitRegions,
428 ArrayRef<const MemRegion *> Regions,
429 const CallOrObjCMessage *Call) {
430 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
431 // If any checker declares the state infeasible (or if it starts that way),
435 state = RegionChangesCheckers[i].CheckFn(state, invalidated,
436 ExplicitRegions, Regions, Call);
441 /// \brief Run checkers for handling assumptions on symbolic values.
443 CheckerManager::runCheckersForEvalAssume(ProgramStateRef state,
444 SVal Cond, bool Assumption) {
445 for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
446 // If any checker declares the state infeasible (or if it starts that way),
450 state = EvalAssumeCheckers[i](state, Cond, Assumption);
455 /// \brief Run checkers for evaluating a call.
456 /// Only one checker will evaluate the call.
457 void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
458 const ExplodedNodeSet &Src,
461 GraphExpander *defaultEval) {
462 if (EvalCallCheckers.empty() &&
463 InlineCallCheckers.empty() &&
469 for (ExplodedNodeSet::iterator
470 NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
472 ExplodedNode *Pred = *NI;
473 bool anyEvaluated = false;
475 // First, check if any of the InlineCall callbacks can evaluate the call.
476 assert(InlineCallCheckers.size() <= 1 &&
477 "InlineCall is a special hacky callback to allow intrusive"
478 "evaluation of the call (which simulates inlining). It is "
479 "currently only used by OSAtomicChecker and should go away "
481 for (std::vector<InlineCallFunc>::iterator
482 EI = InlineCallCheckers.begin(), EE = InlineCallCheckers.end();
484 ExplodedNodeSet checkDst;
485 bool evaluated = (*EI)(CE, Eng, Pred, checkDst);
486 assert(!(evaluated && anyEvaluated)
487 && "There are more than one checkers evaluating the call");
490 Dst.insert(checkDst);
492 break; // on release don't check that no other checker also evals.
497 #ifdef NDEBUG // on release don't check that no other checker also evals.
503 ExplodedNodeSet checkDst;
504 NodeBuilder B(Pred, checkDst, Eng.getBuilderContext());
505 // Next, check if any of the EvalCall callbacks can evaluate the call.
506 for (std::vector<EvalCallFunc>::iterator
507 EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
509 ProgramPoint::Kind K = ProgramPoint::PostStmtKind;
510 const ProgramPoint &L = ProgramPoint::getProgramPoint(CE, K,
511 Pred->getLocationContext(), EI->Checker);
512 bool evaluated = false;
513 { // CheckerContext generates transitions(populates checkDest) on
514 // destruction, so introduce the scope to make sure it gets properly
516 CheckerContext C(B, Eng, Pred, L);
517 evaluated = (*EI)(CE, C);
519 assert(!(evaluated && anyEvaluated)
520 && "There are more than one checkers evaluating the call");
523 Dst.insert(checkDst);
525 break; // on release don't check that no other checker also evals.
530 // If none of the checkers evaluated the call, ask ExprEngine to handle it.
533 defaultEval->expandGraph(Dst, Pred);
540 /// \brief Run checkers for the entire Translation Unit.
541 void CheckerManager::runCheckersOnEndOfTranslationUnit(
542 const TranslationUnitDecl *TU,
543 AnalysisManager &mgr,
545 for (unsigned i = 0, e = EndOfTranslationUnitCheckers.size(); i != e; ++i)
546 EndOfTranslationUnitCheckers[i](TU, mgr, BR);
549 void CheckerManager::runCheckersForPrintState(raw_ostream &Out,
550 ProgramStateRef State,
551 const char *NL, const char *Sep) {
552 for (llvm::DenseMap<CheckerTag, CheckerRef>::iterator
553 I = CheckerTags.begin(), E = CheckerTags.end(); I != E; ++I)
554 I->second->printState(Out, State, NL, Sep);
557 //===----------------------------------------------------------------------===//
558 // Internal registration functions for AST traversing.
559 //===----------------------------------------------------------------------===//
561 void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
562 HandlesDeclFunc isForDeclFn) {
563 DeclCheckerInfo info = { checkfn, isForDeclFn };
564 DeclCheckers.push_back(info);
567 void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
568 BodyCheckers.push_back(checkfn);
571 //===----------------------------------------------------------------------===//
572 // Internal registration functions for path-sensitive checking.
573 //===----------------------------------------------------------------------===//
575 void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
576 HandlesStmtFunc isForStmtFn) {
577 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
578 StmtCheckers.push_back(info);
580 void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
581 HandlesStmtFunc isForStmtFn) {
582 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
583 StmtCheckers.push_back(info);
586 void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
587 PreObjCMessageCheckers.push_back(checkfn);
589 void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
590 PostObjCMessageCheckers.push_back(checkfn);
593 void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
594 LocationCheckers.push_back(checkfn);
597 void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
598 BindCheckers.push_back(checkfn);
601 void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
602 EndAnalysisCheckers.push_back(checkfn);
605 void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
606 EndPathCheckers.push_back(checkfn);
609 void CheckerManager::_registerForBranchCondition(
610 CheckBranchConditionFunc checkfn) {
611 BranchConditionCheckers.push_back(checkfn);
614 void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
615 LiveSymbolsCheckers.push_back(checkfn);
618 void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
619 DeadSymbolsCheckers.push_back(checkfn);
622 void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
623 WantsRegionChangeUpdateFunc wantUpdateFn) {
624 RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
625 RegionChangesCheckers.push_back(info);
628 void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
629 EvalAssumeCheckers.push_back(checkfn);
632 void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
633 EvalCallCheckers.push_back(checkfn);
636 void CheckerManager::_registerForInlineCall(InlineCallFunc checkfn) {
637 InlineCallCheckers.push_back(checkfn);
640 void CheckerManager::_registerForEndOfTranslationUnit(
641 CheckEndOfTranslationUnit checkfn) {
642 EndOfTranslationUnitCheckers.push_back(checkfn);
645 //===----------------------------------------------------------------------===//
646 // Implementation details.
647 //===----------------------------------------------------------------------===//
649 CheckerManager::CachedStmtCheckers *
650 CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
653 CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
654 CachedStmtCheckers *checkers = 0;
655 CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
656 if (CCI != CachedStmtCheckersMap.end()) {
657 checkers = &(CCI->second);
659 // Find the checkers that should run for this Stmt and cache them.
660 checkers = &CachedStmtCheckersMap[key];
661 for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
662 StmtCheckerInfo &info = StmtCheckers[i];
663 if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
664 checkers->push_back(info.CheckFn);
672 CheckerManager::~CheckerManager() {
673 for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
677 // Anchor for the vtable.
678 GraphExpander::~GraphExpander() { }