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