CheckerManager.cpp revision 9c0d6891b3ec4b0d20b8a295946c0dc5426d147c
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 208void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G, 209 BugReporter &BR, 210 ExprEngine &Eng) { 211 for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i) 212 EndAnalysisCheckers[i](G, BR, Eng); 213} 214 215/// \brief Run checkers for end of path. 216void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B, 217 ExprEngine &Eng) { 218 for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) { 219 CheckEndPathFunc fn = EndPathCheckers[i]; 220 EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker); 221 fn(specialB, Eng); 222 } 223} 224 225/// \brief Run checkers for live symbols. 226void CheckerManager::runCheckersForLiveSymbols(const GRState *state, 227 SymbolReaper &SymReaper) { 228 for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i) 229 LiveSymbolsCheckers[i](state, SymReaper); 230} 231 232namespace { 233 struct CheckDeadSymbolsContext { 234 typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy; 235 const CheckersTy &Checkers; 236 SymbolReaper &SR; 237 const Stmt *S; 238 ExprEngine &Eng; 239 240 CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); } 241 CheckersTy::const_iterator checkers_end() { return Checkers.end(); } 242 243 CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr, 244 const Stmt *s, ExprEngine &eng) 245 : Checkers(checkers), SR(sr), S(s), Eng(eng) { } 246 247 void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn, 248 ExplodedNodeSet &Dst, ExplodedNode *Pred) { 249 CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker, 250 ProgramPoint::PostPurgeDeadSymbolsKind, 0, S); 251 checkFn(SR, C); 252 } 253 }; 254} 255 256/// \brief Run checkers for dead symbols. 257void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst, 258 const ExplodedNodeSet &Src, 259 SymbolReaper &SymReaper, 260 const Stmt *S, 261 ExprEngine &Eng) { 262 CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng); 263 expandGraphWithCheckers(C, Dst, Src); 264} 265 266/// \brief True if at least one checker wants to check region changes. 267bool CheckerManager::wantsRegionChangeUpdate(const GRState *state) { 268 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) 269 if (RegionChangesCheckers[i].WantUpdateFn(state)) 270 return true; 271 272 return false; 273} 274 275/// \brief Run checkers for region changes. 276const GRState * 277CheckerManager::runCheckersForRegionChanges(const GRState *state, 278 const MemRegion * const *Begin, 279 const MemRegion * const *End) { 280 for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) { 281 // If any checker declares the state infeasible (or if it starts that way), 282 // bail out. 283 if (!state) 284 return NULL; 285 state = RegionChangesCheckers[i].CheckFn(state, Begin, End); 286 } 287 return state; 288} 289 290/// \brief Run checkers for evaluating a call. 291/// Only one checker will evaluate the call. 292void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst, 293 const ExplodedNodeSet &Src, 294 const CallExpr *CE, 295 ExprEngine &Eng, 296 GraphExpander *defaultEval) { 297 if (EvalCallCheckers.empty() && defaultEval == 0) { 298 Dst.insert(Src); 299 return; 300 } 301 302 for (ExplodedNodeSet::iterator 303 NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) { 304 305 ExplodedNode *Pred = *NI; 306 bool anyEvaluated = false; 307 for (std::vector<EvalCallFunc>::iterator 308 EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end(); 309 EI != EE; ++EI) { 310 ExplodedNodeSet checkDst; 311 CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker, 312 ProgramPoint::PostStmtKind, 0, CE); 313 bool evaluated = (*EI)(CE, C); 314 assert(!(evaluated && anyEvaluated) 315 && "There are more than one checkers evaluating the call"); 316 if (evaluated) { 317 anyEvaluated = true; 318 Dst.insert(checkDst); 319#ifdef NDEBUG 320 break; // on release don't check that no other checker also evals. 321#endif 322 } 323 } 324 325 if (!anyEvaluated) { 326 if (defaultEval) 327 defaultEval->expandGraph(Dst, Pred); 328 else 329 Dst.insert(Pred); 330 } 331 } 332} 333 334//===----------------------------------------------------------------------===// 335// Internal registration functions for AST traversing. 336//===----------------------------------------------------------------------===// 337 338void CheckerManager::_registerForDecl(CheckDeclFunc checkfn, 339 HandlesDeclFunc isForDeclFn) { 340 DeclCheckerInfo info = { checkfn, isForDeclFn }; 341 DeclCheckers.push_back(info); 342} 343 344void CheckerManager::_registerForBody(CheckDeclFunc checkfn) { 345 BodyCheckers.push_back(checkfn); 346} 347 348//===----------------------------------------------------------------------===// 349// Internal registration functions for path-sensitive checking. 350//===----------------------------------------------------------------------===// 351 352void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn, 353 HandlesStmtFunc isForStmtFn) { 354 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true }; 355 StmtCheckers.push_back(info); 356} 357void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn, 358 HandlesStmtFunc isForStmtFn) { 359 StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false }; 360 StmtCheckers.push_back(info); 361} 362 363void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) { 364 PreObjCMessageCheckers.push_back(checkfn); 365} 366void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) { 367 PostObjCMessageCheckers.push_back(checkfn); 368} 369 370void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) { 371 LocationCheckers.push_back(checkfn); 372} 373 374void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) { 375 EndAnalysisCheckers.push_back(checkfn); 376} 377 378void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) { 379 EndPathCheckers.push_back(checkfn); 380} 381 382void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) { 383 LiveSymbolsCheckers.push_back(checkfn); 384} 385 386void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) { 387 DeadSymbolsCheckers.push_back(checkfn); 388} 389 390void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn, 391 WantsRegionChangeUpdateFunc wantUpdateFn) { 392 RegionChangesCheckerInfo info = {checkfn, wantUpdateFn}; 393 RegionChangesCheckers.push_back(info); 394} 395 396void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) { 397 EvalCallCheckers.push_back(checkfn); 398} 399 400//===----------------------------------------------------------------------===// 401// Implementation details. 402//===----------------------------------------------------------------------===// 403 404CheckerManager::CachedStmtCheckers * 405CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) { 406 assert(S); 407 408 CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit); 409 CachedStmtCheckers *checkers = 0; 410 CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key); 411 if (CCI != CachedStmtCheckersMap.end()) { 412 checkers = &(CCI->second); 413 } else { 414 // Find the checkers that should run for this Stmt and cache them. 415 checkers = &CachedStmtCheckersMap[key]; 416 for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) { 417 StmtCheckerInfo &info = StmtCheckers[i]; 418 if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S)) 419 checkers->push_back(info.CheckFn); 420 } 421 } 422 423 assert(checkers); 424 return checkers; 425} 426 427CheckerManager::~CheckerManager() { 428 for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i) 429 CheckerDtors[i](); 430} 431 432// Anchor for the vtable. 433CheckerProvider::~CheckerProvider() { } 434 435// Anchor for the vtable. 436GraphExpander::~GraphExpander() { } 437