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/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"
20 
21 using namespace clang;
22 using namespace ento;
23 
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 }
39 
40 void CheckerManager::finishedCheckerRegistration() {
41 #ifndef NDEBUG
42   // Make sure that for every event that has listeners, there is at least
43   // one dispatcher registered for it.
44   for (llvm::DenseMap<EventTag, EventInfo>::iterator
45          I = Events.begin(), E = Events.end(); I != E; ++I)
46     assert(I->second.HasDispatcher && "No dispatcher registered for an event");
47 #endif
48 }
49 
50 //===----------------------------------------------------------------------===//
51 // Functions for running checkers for AST traversing..
52 //===----------------------------------------------------------------------===//
53 
54 void CheckerManager::runCheckersOnASTDecl(const Decl *D, AnalysisManager& mgr,
55                                           BugReporter &BR) {
56   assert(D);
57 
58   unsigned DeclKind = D->getKind();
59   CachedDeclCheckers *checkers = 0;
60   CachedDeclCheckersMapTy::iterator CCI = CachedDeclCheckersMap.find(DeclKind);
61   if (CCI != CachedDeclCheckersMap.end()) {
62     checkers = &(CCI->second);
63   } else {
64     // Find the checkers that should run for this Decl and cache them.
65     checkers = &CachedDeclCheckersMap[DeclKind];
66     for (unsigned i = 0, e = DeclCheckers.size(); i != e; ++i) {
67       DeclCheckerInfo &info = DeclCheckers[i];
68       if (info.IsForDeclFn(D))
69         checkers->push_back(info.CheckFn);
70     }
71   }
72 
73   assert(checkers);
74   for (CachedDeclCheckers::iterator
75          I = checkers->begin(), E = checkers->end(); I != E; ++I)
76     (*I)(D, mgr, BR);
77 }
78 
79 void CheckerManager::runCheckersOnASTBody(const Decl *D, AnalysisManager& mgr,
80                                           BugReporter &BR) {
81   assert(D && D->hasBody());
82 
83   for (unsigned i = 0, e = BodyCheckers.size(); i != e; ++i)
84     BodyCheckers[i](D, mgr, BR);
85 }
86 
87 //===----------------------------------------------------------------------===//
88 // Functions for running checkers for path-sensitive checking.
89 //===----------------------------------------------------------------------===//
90 
91 template <typename CHECK_CTX>
92 static void expandGraphWithCheckers(CHECK_CTX checkCtx,
93                                     ExplodedNodeSet &Dst,
94                                     const ExplodedNodeSet &Src) {
95 
96   typename CHECK_CTX::CheckersTy::const_iterator
97       I = checkCtx.checkers_begin(), E = checkCtx.checkers_end();
98   if (I == E) {
99     Dst.insert(Src);
100     return;
101   }
102 
103   ExplodedNodeSet Tmp1, Tmp2;
104   const ExplodedNodeSet *PrevSet = &Src;
105 
106   for (; I != E; ++I) {
107     ExplodedNodeSet *CurrSet = 0;
108     if (I+1 == E)
109       CurrSet = &Dst;
110     else {
111       CurrSet = (PrevSet == &Tmp1) ? &Tmp2 : &Tmp1;
112       CurrSet->clear();
113     }
114 
115     for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
116          NI != NE; ++NI)
117       checkCtx.runChecker(*I, *CurrSet, *NI);
118 
119     // Update which NodeSet is the current one.
120     PrevSet = CurrSet;
121   }
122 }
123 
124 namespace {
125   struct CheckStmtContext {
126     typedef SmallVectorImpl<CheckerManager::CheckStmtFunc> CheckersTy;
127     bool IsPreVisit;
128     const CheckersTy &Checkers;
129     const Stmt *S;
130     ExprEngine &Eng;
131 
132     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
133     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
134 
135     CheckStmtContext(bool isPreVisit, const CheckersTy &checkers,
136                      const Stmt *s, ExprEngine &eng)
137       : IsPreVisit(isPreVisit), Checkers(checkers), S(s), Eng(eng) { }
138 
139     void runChecker(CheckerManager::CheckStmtFunc checkFn,
140                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
141       // FIXME: Remove respondsToCallback from CheckerContext;
142       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
143                        IsPreVisit ? ProgramPoint::PreStmtKind :
144                                     ProgramPoint::PostStmtKind, 0, S);
145       checkFn(S, C);
146     }
147   };
148 }
149 
150 /// \brief Run checkers for visiting Stmts.
151 void CheckerManager::runCheckersForStmt(bool isPreVisit,
152                                         ExplodedNodeSet &Dst,
153                                         const ExplodedNodeSet &Src,
154                                         const Stmt *S,
155                                         ExprEngine &Eng) {
156   CheckStmtContext C(isPreVisit, *getCachedStmtCheckersFor(S, isPreVisit),
157                      S, Eng);
158   expandGraphWithCheckers(C, Dst, Src);
159 }
160 
161 namespace {
162   struct CheckObjCMessageContext {
163     typedef std::vector<CheckerManager::CheckObjCMessageFunc> CheckersTy;
164     bool IsPreVisit;
165     const CheckersTy &Checkers;
166     const ObjCMessage &Msg;
167     ExprEngine &Eng;
168 
169     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
170     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
171 
172     CheckObjCMessageContext(bool isPreVisit, const CheckersTy &checkers,
173                             const ObjCMessage &msg, ExprEngine &eng)
174       : IsPreVisit(isPreVisit), Checkers(checkers), Msg(msg), Eng(eng) { }
175 
176     void runChecker(CheckerManager::CheckObjCMessageFunc checkFn,
177                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
178       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
179                        IsPreVisit ? ProgramPoint::PreStmtKind :
180                                     ProgramPoint::PostStmtKind, 0,
181                        Msg.getOriginExpr());
182       checkFn(Msg, C);
183     }
184   };
185 }
186 
187 /// \brief Run checkers for visiting obj-c messages.
188 void CheckerManager::runCheckersForObjCMessage(bool isPreVisit,
189                                                ExplodedNodeSet &Dst,
190                                                const ExplodedNodeSet &Src,
191                                                const ObjCMessage &msg,
192                                                ExprEngine &Eng) {
193   CheckObjCMessageContext C(isPreVisit,
194                             isPreVisit ? PreObjCMessageCheckers
195                                        : PostObjCMessageCheckers,
196                             msg, Eng);
197   expandGraphWithCheckers(C, Dst, Src);
198 }
199 
200 namespace {
201   struct CheckLocationContext {
202     typedef std::vector<CheckerManager::CheckLocationFunc> CheckersTy;
203     const CheckersTy &Checkers;
204     SVal Loc;
205     bool IsLoad;
206     const Stmt *S;
207     ExprEngine &Eng;
208 
209     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
210     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
211 
212     CheckLocationContext(const CheckersTy &checkers,
213                          SVal loc, bool isLoad, const Stmt *s, ExprEngine &eng)
214       : Checkers(checkers), Loc(loc), IsLoad(isLoad), S(s), Eng(eng) { }
215 
216     void runChecker(CheckerManager::CheckLocationFunc checkFn,
217                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
218       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
219                        IsLoad ? ProgramPoint::PreLoadKind :
220                        ProgramPoint::PreStoreKind, 0, S);
221       checkFn(Loc, IsLoad, C);
222     }
223   };
224 }
225 
226 /// \brief Run checkers for load/store of a location.
227 void CheckerManager::runCheckersForLocation(ExplodedNodeSet &Dst,
228                                             const ExplodedNodeSet &Src,
229                                             SVal location, bool isLoad,
230                                             const Stmt *S, ExprEngine &Eng) {
231   CheckLocationContext C(LocationCheckers, location, isLoad, S, Eng);
232   expandGraphWithCheckers(C, Dst, Src);
233 }
234 
235 namespace {
236   struct CheckBindContext {
237     typedef std::vector<CheckerManager::CheckBindFunc> CheckersTy;
238     const CheckersTy &Checkers;
239     SVal Loc;
240     SVal Val;
241     const Stmt *S;
242     ExprEngine &Eng;
243 
244     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
245     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
246 
247     CheckBindContext(const CheckersTy &checkers,
248                      SVal loc, SVal val, const Stmt *s, ExprEngine &eng)
249       : Checkers(checkers), Loc(loc), Val(val), S(s), Eng(eng) { }
250 
251     void runChecker(CheckerManager::CheckBindFunc checkFn,
252                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
253       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
254                        ProgramPoint::PreStmtKind, 0, S);
255       checkFn(Loc, Val, C);
256     }
257   };
258 }
259 
260 /// \brief Run checkers for binding of a value to a location.
261 void CheckerManager::runCheckersForBind(ExplodedNodeSet &Dst,
262                                         const ExplodedNodeSet &Src,
263                                         SVal location, SVal val,
264                                         const Stmt *S, ExprEngine &Eng) {
265   CheckBindContext C(BindCheckers, location, val, S, Eng);
266   expandGraphWithCheckers(C, Dst, Src);
267 }
268 
269 void CheckerManager::runCheckersForEndAnalysis(ExplodedGraph &G,
270                                                BugReporter &BR,
271                                                ExprEngine &Eng) {
272   for (unsigned i = 0, e = EndAnalysisCheckers.size(); i != e; ++i)
273     EndAnalysisCheckers[i](G, BR, Eng);
274 }
275 
276 /// \brief Run checkers for end of path.
277 void CheckerManager::runCheckersForEndPath(EndOfFunctionNodeBuilder &B,
278                                            ExprEngine &Eng) {
279   for (unsigned i = 0, e = EndPathCheckers.size(); i != e; ++i) {
280     CheckEndPathFunc fn = EndPathCheckers[i];
281     EndOfFunctionNodeBuilder specialB = B.withCheckerTag(fn.Checker);
282     fn(specialB, Eng);
283   }
284 }
285 
286 /// \brief Run checkers for branch condition.
287 void CheckerManager::runCheckersForBranchCondition(const Stmt *condition,
288                                                    BranchNodeBuilder &B,
289                                                    ExprEngine &Eng) {
290   for (unsigned i = 0, e = BranchConditionCheckers.size(); i != e; ++i) {
291     CheckBranchConditionFunc fn = BranchConditionCheckers[i];
292     fn(condition, B, Eng);
293   }
294 }
295 
296 /// \brief Run checkers for live symbols.
297 void CheckerManager::runCheckersForLiveSymbols(const ProgramState *state,
298                                                SymbolReaper &SymReaper) {
299   for (unsigned i = 0, e = LiveSymbolsCheckers.size(); i != e; ++i)
300     LiveSymbolsCheckers[i](state, SymReaper);
301 }
302 
303 namespace {
304   struct CheckDeadSymbolsContext {
305     typedef std::vector<CheckerManager::CheckDeadSymbolsFunc> CheckersTy;
306     const CheckersTy &Checkers;
307     SymbolReaper &SR;
308     const Stmt *S;
309     ExprEngine &Eng;
310 
311     CheckersTy::const_iterator checkers_begin() { return Checkers.begin(); }
312     CheckersTy::const_iterator checkers_end() { return Checkers.end(); }
313 
314     CheckDeadSymbolsContext(const CheckersTy &checkers, SymbolReaper &sr,
315                             const Stmt *s, ExprEngine &eng)
316       : Checkers(checkers), SR(sr), S(s), Eng(eng) { }
317 
318     void runChecker(CheckerManager::CheckDeadSymbolsFunc checkFn,
319                     ExplodedNodeSet &Dst, ExplodedNode *Pred) {
320       CheckerContext C(Dst, Eng.getBuilder(), Eng, Pred, checkFn.Checker,
321                        ProgramPoint::PostPurgeDeadSymbolsKind, 0, S);
322       checkFn(SR, C);
323     }
324   };
325 }
326 
327 /// \brief Run checkers for dead symbols.
328 void CheckerManager::runCheckersForDeadSymbols(ExplodedNodeSet &Dst,
329                                                const ExplodedNodeSet &Src,
330                                                SymbolReaper &SymReaper,
331                                                const Stmt *S,
332                                                ExprEngine &Eng) {
333   CheckDeadSymbolsContext C(DeadSymbolsCheckers, SymReaper, S, Eng);
334   expandGraphWithCheckers(C, Dst, Src);
335 }
336 
337 /// \brief True if at least one checker wants to check region changes.
338 bool CheckerManager::wantsRegionChangeUpdate(const ProgramState *state) {
339   for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i)
340     if (RegionChangesCheckers[i].WantUpdateFn(state))
341       return true;
342 
343   return false;
344 }
345 
346 /// \brief Run checkers for region changes.
347 const ProgramState *
348 CheckerManager::runCheckersForRegionChanges(const ProgramState *state,
349                             const StoreManager::InvalidatedSymbols *invalidated,
350                                     ArrayRef<const MemRegion *> ExplicitRegions,
351                                           ArrayRef<const MemRegion *> Regions) {
352   for (unsigned i = 0, e = RegionChangesCheckers.size(); i != e; ++i) {
353     // If any checker declares the state infeasible (or if it starts that way),
354     // bail out.
355     if (!state)
356       return NULL;
357     state = RegionChangesCheckers[i].CheckFn(state, invalidated,
358                                              ExplicitRegions, Regions);
359   }
360   return state;
361 }
362 
363 /// \brief Run checkers for handling assumptions on symbolic values.
364 const ProgramState *
365 CheckerManager::runCheckersForEvalAssume(const ProgramState *state,
366                                          SVal Cond, bool Assumption) {
367   for (unsigned i = 0, e = EvalAssumeCheckers.size(); i != e; ++i) {
368     // If any checker declares the state infeasible (or if it starts that way),
369     // bail out.
370     if (!state)
371       return NULL;
372     state = EvalAssumeCheckers[i](state, Cond, Assumption);
373   }
374   return state;
375 }
376 
377 /// \brief Run checkers for evaluating a call.
378 /// Only one checker will evaluate the call.
379 void CheckerManager::runCheckersForEvalCall(ExplodedNodeSet &Dst,
380                                             const ExplodedNodeSet &Src,
381                                             const CallExpr *CE,
382                                             ExprEngine &Eng,
383                                             GraphExpander *defaultEval) {
384   if (EvalCallCheckers.empty() && defaultEval == 0) {
385     Dst.insert(Src);
386     return;
387   }
388 
389   for (ExplodedNodeSet::iterator
390          NI = Src.begin(), NE = Src.end(); NI != NE; ++NI) {
391 
392     ExplodedNode *Pred = *NI;
393     bool anyEvaluated = false;
394     for (std::vector<EvalCallFunc>::iterator
395            EI = EvalCallCheckers.begin(), EE = EvalCallCheckers.end();
396          EI != EE; ++EI) {
397       ExplodedNodeSet checkDst;
398       CheckerContext C(checkDst, Eng.getBuilder(), Eng, Pred, EI->Checker,
399                        ProgramPoint::PostStmtKind, 0, CE);
400       bool evaluated = (*EI)(CE, C);
401       assert(!(evaluated && anyEvaluated)
402              && "There are more than one checkers evaluating the call");
403       if (evaluated) {
404         anyEvaluated = true;
405         Dst.insert(checkDst);
406 #ifdef NDEBUG
407         break; // on release don't check that no other checker also evals.
408 #endif
409       }
410     }
411 
412     if (!anyEvaluated) {
413       if (defaultEval)
414         defaultEval->expandGraph(Dst, Pred);
415       else
416         Dst.insert(Pred);
417     }
418   }
419 }
420 
421 /// \brief Run checkers for the entire Translation Unit.
422 void CheckerManager::runCheckersOnEndOfTranslationUnit(
423                                                   const TranslationUnitDecl *TU,
424                                                   AnalysisManager &mgr,
425                                                   BugReporter &BR) {
426   for (unsigned i = 0, e = EndOfTranslationUnitCheckers.size(); i != e; ++i)
427     EndOfTranslationUnitCheckers[i](TU, mgr, BR);
428 }
429 
430 void CheckerManager::runCheckersForPrintState(raw_ostream &Out,
431                                               const ProgramState *State,
432                                               const char *NL, const char *Sep) {
433   for (llvm::DenseMap<CheckerTag, CheckerRef>::iterator
434         I = CheckerTags.begin(), E = CheckerTags.end(); I != E; ++I)
435     I->second->printState(Out, State, NL, Sep);
436 }
437 
438 //===----------------------------------------------------------------------===//
439 // Internal registration functions for AST traversing.
440 //===----------------------------------------------------------------------===//
441 
442 void CheckerManager::_registerForDecl(CheckDeclFunc checkfn,
443                                       HandlesDeclFunc isForDeclFn) {
444   DeclCheckerInfo info = { checkfn, isForDeclFn };
445   DeclCheckers.push_back(info);
446 }
447 
448 void CheckerManager::_registerForBody(CheckDeclFunc checkfn) {
449   BodyCheckers.push_back(checkfn);
450 }
451 
452 //===----------------------------------------------------------------------===//
453 // Internal registration functions for path-sensitive checking.
454 //===----------------------------------------------------------------------===//
455 
456 void CheckerManager::_registerForPreStmt(CheckStmtFunc checkfn,
457                                          HandlesStmtFunc isForStmtFn) {
458   StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/true };
459   StmtCheckers.push_back(info);
460 }
461 void CheckerManager::_registerForPostStmt(CheckStmtFunc checkfn,
462                                           HandlesStmtFunc isForStmtFn) {
463   StmtCheckerInfo info = { checkfn, isForStmtFn, /*IsPreVisit*/false };
464   StmtCheckers.push_back(info);
465 }
466 
467 void CheckerManager::_registerForPreObjCMessage(CheckObjCMessageFunc checkfn) {
468   PreObjCMessageCheckers.push_back(checkfn);
469 }
470 void CheckerManager::_registerForPostObjCMessage(CheckObjCMessageFunc checkfn) {
471   PostObjCMessageCheckers.push_back(checkfn);
472 }
473 
474 void CheckerManager::_registerForLocation(CheckLocationFunc checkfn) {
475   LocationCheckers.push_back(checkfn);
476 }
477 
478 void CheckerManager::_registerForBind(CheckBindFunc checkfn) {
479   BindCheckers.push_back(checkfn);
480 }
481 
482 void CheckerManager::_registerForEndAnalysis(CheckEndAnalysisFunc checkfn) {
483   EndAnalysisCheckers.push_back(checkfn);
484 }
485 
486 void CheckerManager::_registerForEndPath(CheckEndPathFunc checkfn) {
487   EndPathCheckers.push_back(checkfn);
488 }
489 
490 void CheckerManager::_registerForBranchCondition(
491                                              CheckBranchConditionFunc checkfn) {
492   BranchConditionCheckers.push_back(checkfn);
493 }
494 
495 void CheckerManager::_registerForLiveSymbols(CheckLiveSymbolsFunc checkfn) {
496   LiveSymbolsCheckers.push_back(checkfn);
497 }
498 
499 void CheckerManager::_registerForDeadSymbols(CheckDeadSymbolsFunc checkfn) {
500   DeadSymbolsCheckers.push_back(checkfn);
501 }
502 
503 void CheckerManager::_registerForRegionChanges(CheckRegionChangesFunc checkfn,
504                                      WantsRegionChangeUpdateFunc wantUpdateFn) {
505   RegionChangesCheckerInfo info = {checkfn, wantUpdateFn};
506   RegionChangesCheckers.push_back(info);
507 }
508 
509 void CheckerManager::_registerForEvalAssume(EvalAssumeFunc checkfn) {
510   EvalAssumeCheckers.push_back(checkfn);
511 }
512 
513 void CheckerManager::_registerForEvalCall(EvalCallFunc checkfn) {
514   EvalCallCheckers.push_back(checkfn);
515 }
516 
517 void CheckerManager::_registerForEndOfTranslationUnit(
518                                             CheckEndOfTranslationUnit checkfn) {
519   EndOfTranslationUnitCheckers.push_back(checkfn);
520 }
521 
522 //===----------------------------------------------------------------------===//
523 // Implementation details.
524 //===----------------------------------------------------------------------===//
525 
526 CheckerManager::CachedStmtCheckers *
527 CheckerManager::getCachedStmtCheckersFor(const Stmt *S, bool isPreVisit) {
528   assert(S);
529 
530   CachedStmtCheckersKey key(S->getStmtClass(), isPreVisit);
531   CachedStmtCheckers *checkers = 0;
532   CachedStmtCheckersMapTy::iterator CCI = CachedStmtCheckersMap.find(key);
533   if (CCI != CachedStmtCheckersMap.end()) {
534     checkers = &(CCI->second);
535   } else {
536     // Find the checkers that should run for this Stmt and cache them.
537     checkers = &CachedStmtCheckersMap[key];
538     for (unsigned i = 0, e = StmtCheckers.size(); i != e; ++i) {
539       StmtCheckerInfo &info = StmtCheckers[i];
540       if (info.IsPreVisit == isPreVisit && info.IsForStmtFn(S))
541         checkers->push_back(info.CheckFn);
542     }
543   }
544 
545   assert(checkers);
546   return checkers;
547 }
548 
549 CheckerManager::~CheckerManager() {
550   for (unsigned i = 0, e = CheckerDtors.size(); i != e; ++i)
551     CheckerDtors[i]();
552 }
553 
554 // Anchor for the vtable.
555 GraphExpander::~GraphExpander() { }
556