lib/StaticAnalyzer/Core/CheckerManager.cpp

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