CheckerManager.cpp 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507
  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. #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  14. #include "clang/StaticAnalyzer/Core/CheckerProvider.h"
  15. #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  16. #include "clang/Analysis/ProgramPoint.h"
  17. #include "clang/AST/DeclBase.h"
  18. using namespace clang;
  19. using namespace ento;
  20. //===----------------------------------------------------------------------===//
  21. // Functions for running checkers for AST traversing..
  22. //===----------------------------------------------------------------------===//
  23. void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
  24. BugReporter &BR) {
  25. assert(D);
  26. unsigned DeclKind = D->getKind();
  27. CachedDeclCheckers *checkers = 0;
  28. CachedDeclCheckersMapTy::iterator CCI = CachedDeclCheckersMap.find(DeclKind);
  29. if (CCI != CachedDeclCheckersMap.end()) {
  30. checkers = &(CCI->second);
  31. } else {
  32. // Find the checkers that should run for this Decl and cache them.
  33. checkers = &CachedDeclCheckersMap[DeclKind];
  34. for (unsigned i = 0, e = DeclCheckers.size(); i != e; ++i) {
  35. DeclCheckerInfo &info = DeclCheckers[i];
  36. if (info.IsForDeclFn(D))
  37. checkers->push_back(info.CheckFn);
  38. }
  39. }
  40. assert(checkers);
  41. for (CachedDeclCheckers::iterator
  42. I = checkers->begin(), E = checkers->end(); I != E; ++I)
  43. (*I)(D, mgr, BR);
  44. }
  45. void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
  46. BugReporter &BR) {
  47. assert(D && D->hasBody());
  48. for (unsigned i = 0, e = BodyCheckers.size(); i != e; ++i)
  49. BodyCheckers[i](D, mgr, BR);
  50. }
  51. //===----------------------------------------------------------------------===//
  52. // Functions for running checkers for path-sensitive checking.
  53. //===----------------------------------------------------------------------===//
  54. template <typename CHECK_CTX>
  55. static void expandGraphWithCheckers(CHECK_CTX checkCtx,
  56. ExplodedNodeSet &Dst,
  57. const ExplodedNodeSet &Src) {
  58. typename CHECK_CTX::CheckersTy::const_iterator
  59. I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
  60. if (I == E) {
  61. Dst.insert(Src);
  62. return;
  63. }
  64. ExplodedNodeSet Tmp1, Tmp2;
  65. const ExplodedNodeSet *PrevSet = &Src;
  66. for (; I != E; ++I) {
  67. ExplodedNodeSet *CurrSet = 0;
  68. if (I+1 == E)
  69. CurrSet = &Dst;
  70. else {
  71. CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
  72. CurrSet->clear();
  73. }
  74. for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
  75. NI != NE; ++NI)
  76. checkCtx.runChecker(*I, *CurrSet, *NI);
  77. // Update which NodeSet is the current one.
  78. PrevSet = CurrSet;
  79. }
  80. }
  81. namespace {
  82. struct CheckStmtContext {
  83. typedef llvm::SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
  84. bool IsPreVisit;
  85. const CheckersTy &Checkers;
  86. const Stmt *S;
  87. ExprEngine &Eng;
  88. CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
  89. CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
  90. CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
  91. const Stmt *s, ExprEngine &eng)
  92. : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { }
  93. void runChecker(CheckerManager::CheckStmtFunc checkFn,
  94. ExplodedNodeSet &Dst, ExplodedNode *Pred) {
  95. // FIXME: Remove respondsToCallback from CheckerContext;
  96. CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
  97. IsPreVisit ? ProgramPoint::PreStmtKind :
  98. ProgramPoint::PostStmtKind, 0, S);
  99. checkFn(S, C);
  100. }
  101. };
  102. }
  103. /// \brief Run checkers for visiting Stmts.
  104. void CheckerManager::runCheckersForStmt(bool isPreVisit,
  105. ExplodedNodeSet &Dst,
  106. const ExplodedNodeSet &Src,
  107. const Stmt *S,
  108. ExprEngine &Eng) {
  109. CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
  110. S, Eng);
  111. expandGraphWithCheckers(C, Dst, Src);
  112. }
  113. namespace {
  114. struct CheckObjCMessageContext {
  115. typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
  116. bool IsPreVisit;
  117. const CheckersTy &Checkers;
  118. const ObjCMessage &Msg;
  119. ExprEngine &Eng;
  120. CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
  121. CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
  122. CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
  123. const ObjCMessage &msg, ExprEngine &eng)
  124. : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
  125. void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
  126. ExplodedNodeSet &Dst, ExplodedNode *Pred) {
  127. CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
  128. IsPreVisit ? ProgramPoint::PreStmtKind :
  129. ProgramPoint::PostStmtKind, 0,
  130. Msg.getOriginExpr());
  131. checkFn(Msg, C);
  132. }
  133. };
  134. }
  135. /// \brief Run checkers for visiting obj-c messages.
  136. void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
  137. ExplodedNodeSet &Dst,
  138. const ExplodedNodeSet &Src,
  139. const ObjCMessage &msg,
  140. ExprEngine &Eng) {
  141. CheckObjCMessageContext C(isPreVisit,
  142. isPreVisit ? PreObjCMessageCheckers
  143. : PostObjCMessageCheckers,
  144. msg, Eng);
  145. expandGraphWithCheckers(C, Dst, Src);
  146. }
  147. namespace {
  148. struct CheckLocationContext {
  149. typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
  150. const CheckersTy &Checkers;
  151. SVal Loc;
  152. bool IsLoad;
  153. const Stmt *S;
  154. ExprEngine &Eng;
  155. CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
  156. CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
  157. CheckLocationContext(const CheckersTy &checkers,
  158. SVal loc, bool isLoad, const Stmt *s, ExprEngine &eng)
  159. : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { }
  160. void runChecker(CheckerManager::CheckLocationFunc checkFn,
  161. ExplodedNodeSet &Dst, ExplodedNode *Pred) {
  162. CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
  163. IsLoad ? ProgramPoint::PreLoadKind :
  164. ProgramPoint::PreStoreKind, 0, S);
  165. checkFn(Loc, IsLoad, C);
  166. }
  167. };
  168. }
  169. /// \brief Run checkers for load/store of a location.
  170. void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
  171. const ExplodedNodeSet &Src,
  172. SVal location, bool isLoad,
  173. const Stmt *S, ExprEngine &Eng) {
  174. CheckLocationContext C(LocationCheckers, location, isLoad, S, Eng);
  175. expandGraphWithCheckers(C, Dst, Src);
  176. }
  177. namespace {
  178. struct CheckBindContext {
  179. typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
  180. const CheckersTy &Checkers;
  181. SVal Loc;
  182. SVal Val;
  183. const Stmt *S;
  184. ExprEngine &Eng;
  185. CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
  186. CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
  187. CheckBindContext(const CheckersTy &checkers,
  188. SVal loc, SVal val, const Stmt *s, ExprEngine &eng)
  189. : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { }
  190. void runChecker(CheckerManager::CheckBindFunc checkFn,
  191. ExplodedNodeSet &Dst, ExplodedNode *Pred) {
  192. CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
  193. ProgramPoint::PreStmtKind, 0, S);
  194. checkFn(Loc, Val, C);
  195. }
  196. };
  197. }
  198. /// \brief Run checkers for binding of a value to a location.
  199. void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
  200. const ExplodedNodeSet &Src,
  201. SVal location, SVal val,
  202. const Stmt *S, ExprEngine &Eng) {
  203. CheckBindContext C(BindCheckers, location, val, S, Eng);
  204. expandGraphWithCheckers(C, Dst, Src);
  205. }
  206. void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
  207. BugReporter &BR,
  208. ExprEngine &Eng) {
  209. for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
  210. EndAnalysisCheckers[i](G, BR, Eng);
  211. }
  212. /// \brief Run checkers for end of path.
  213. void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B,
  214. ExprEngine &Eng) {
  215. for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
  216. CheckEndPathFunc fn = EndPathCheckers[i];
  217. EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker);
  218. fn(specialB, Eng);
  219. }
  220. }
  221. /// \brief Run checkers for branch condition.
  222. void CheckerManager::runCheckersForBranchCondition(const Stmt *condition,
  223. BranchNodeBuilder &B,
  224. ExprEngine &Eng) {
  225. for (unsigned i = 0, e = BranchConditionCheckers.size(); i != e; ++i) {
  226. CheckBranchConditionFunc fn = BranchConditionCheckers[i];
  227. fn(condition, B, Eng);
  228. }
  229. }
  230. /// \brief Run checkers for live symbols.
  231. void 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. namespace {
  237. struct CheckDeadSymbolsContext {
  238. typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
  239. const CheckersTy &Checkers;
  240. SymbolReaper &SR;
  241. const Stmt *S;
  242. ExprEngine &Eng;
  243. CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
  244. CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
  245. CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
  246. const Stmt *s, ExprEngine &eng)
  247. : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
  248. void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
  249. ExplodedNodeSet &Dst, ExplodedNode *Pred) {
  250. CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
  251. ProgramPoint::PostPurgeDeadSymbolsKind, 0, S);
  252. checkFn(SR, C);
  253. }
  254. };
  255. }
  256. /// \brief Run checkers for dead symbols.
  257. void 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. /// \brief True if at least one checker wants to check region changes.
  266. bool CheckerManager::wantsRegionChangeUpdate(const GRState *state) {
  267. for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
  268. if (RegionChangesCheckers[i].WantUpdateFn(state))
  269. return true;
  270. return false;
  271. }
  272. /// \brief Run checkers for region changes.
  273. const GRState *
  274. CheckerManager::runCheckersForRegionChanges(const GRState *state,
  275. const MemRegion * const *Begin,
  276. const MemRegion * const *End) {
  277. for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
  278. // If any checker declares the state infeasible (or if it starts that way),
  279. // bail out.
  280. if (!state)
  281. return NULL;
  282. state = RegionChangesCheckers[i].CheckFn(state, Begin, End);
  283. }
  284. return state;
  285. }
  286. /// \brief Run checkers for handling assumptions on symbolic values.
  287. const GRState *
  288. CheckerManager::runCheckersForEvalAssume(const GRState *state,
  289. SVal Cond, bool Assumption) {
  290. for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
  291. // If any checker declares the state infeasible (or if it starts that way),
  292. // bail out.
  293. if (!state)
  294. return NULL;
  295. state = EvalAssumeCheckers[i](state, Cond, Assumption);
  296. }
  297. return state;
  298. }
  299. /// \brief Run checkers for evaluating a call.
  300. /// Only one checker will evaluate the call.
  301. void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
  302. const ExplodedNodeSet &Src,
  303. const CallExpr *CE,
  304. ExprEngine &Eng,
  305. GraphExpander *defaultEval) {
  306. if (EvalCallCheckers.empty() && defaultEval == 0) {
  307. Dst.insert(Src);
  308. return;
  309. }
  310. for (ExplodedNodeSet::iterator
  311. NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
  312. ExplodedNode *Pred = *NI;
  313. bool anyEvaluated = false;
  314. for (std::vector<EvalCallFunc>::iterator
  315. EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
  316. EI != EE; ++EI) {
  317. ExplodedNodeSet checkDst;
  318. CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker,
  319. ProgramPoint::PostStmtKind, 0, CE);
  320. bool evaluated = (*EI)(CE, C);
  321. assert(!(evaluated && anyEvaluated)
  322. && "There are more than one checkers evaluating the call");
  323. if (evaluated) {
  324. anyEvaluated = true;
  325. Dst.insert(checkDst);
  326. #ifdef NDEBUG
  327. break; // on release don't check that no other checker also evals.
  328. #endif
  329. }
  330. }
  331. if (!anyEvaluated) {
  332. if (defaultEval)
  333. defaultEval->expandGraph(Dst, Pred);
  334. else
  335. Dst.insert(Pred);
  336. }
  337. }
  338. }
  339. //===----------------------------------------------------------------------===//
  340. // Internal registration functions for AST traversing.
  341. //===----------------------------------------------------------------------===//
  342. void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
  343. HandlesDeclFunc isForDeclFn) {
  344. DeclCheckerInfo info = { checkfn, isForDeclFn };
  345. DeclCheckers.push_back(info);
  346. }
  347. void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
  348. BodyCheckers.push_back(checkfn);
  349. }
  350. //===----------------------------------------------------------------------===//
  351. // Internal registration functions for path-sensitive checking.
  352. //===----------------------------------------------------------------------===//
  353. void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
  354. HandlesStmtFunc isForStmtFn) {
  355. StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
  356. StmtCheckers.push_back(info);
  357. }
  358. void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
  359. HandlesStmtFunc isForStmtFn) {
  360. StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
  361. StmtCheckers.push_back(info);
  362. }
  363. void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
  364. PreObjCMessageCheckers.push_back(checkfn);
  365. }
  366. void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
  367. PostObjCMessageCheckers.push_back(checkfn);
  368. }
  369. void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
  370. LocationCheckers.push_back(checkfn);
  371. }
  372. void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
  373. BindCheckers.push_back(checkfn);
  374. }
  375. void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
  376. EndAnalysisCheckers.push_back(checkfn);
  377. }
  378. void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
  379. EndPathCheckers.push_back(checkfn);
  380. }
  381. void CheckerManager::_registerForBranchCondition(
  382. CheckBranchConditionFunc checkfn) {
  383. BranchConditionCheckers.push_back(checkfn);
  384. }
  385. void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
  386. LiveSymbolsCheckers.push_back(checkfn);
  387. }
  388. void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
  389. DeadSymbolsCheckers.push_back(checkfn);
  390. }
  391. void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
  392. WantsRegionChangeUpdateFunc wantUpdateFn) {
  393. RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
  394. RegionChangesCheckers.push_back(info);
  395. }
  396. void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
  397. EvalAssumeCheckers.push_back(checkfn);
  398. }
  399. void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
  400. EvalCallCheckers.push_back(checkfn);
  401. }
  402. //===----------------------------------------------------------------------===//
  403. // Implementation details.
  404. //===----------------------------------------------------------------------===//
  405. CheckerManager::CachedStmtCheckers *
  406. CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
  407. assert(S);
  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. assert(checkers);
  423. return checkers;
  424. }
  425. CheckerManager::~CheckerManager() {
  426. for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
  427. CheckerDtors[i]();
  428. }
  429. // Anchor for the vtable.
  430. CheckerProvider::~CheckerProvider() { }
  431. // Anchor for the vtable.
  432. GraphExpander::~GraphExpander() { }