lib/StaticAnalyzer/Core/BugReporter.cpp

   1 // BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
   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 //  This file defines BugReporter, a utility class for generating
  11 //  PathDiagnostics.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/Analysis/CFG.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/ParentMap.h"
  22 #include "clang/AST/StmtObjC.h"
  23 #include "clang/Basic/SourceManager.h"
  24 #include "clang/Analysis/ProgramPoint.h"
  25 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 #include "llvm/ADT/OwningPtr.h"
  30 #include <queue>
  31
  32 using namespace clang;
  33 using namespace ento;
  34
  35 BugReporterVisitor::~BugReporterVisitor() {}
  36 BugReporterContext::~BugReporterContext() {
  37   for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I)
  38     if ((*I)->isOwnedByReporterContext()) delete *I;
  39 }
  40
  41 void BugReporterContext::addVisitor(BugReporterVisitor* visitor) {
  42   if (!visitor)
  43     return;
  44
  45   llvm::FoldingSetNodeID ID;
  46   visitor->Profile(ID);
  47   void *InsertPos;
  48
  49   if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
  50     delete visitor;
  51     return;
  52   }
  53
  54   CallbacksSet.InsertNode(visitor, InsertPos);
  55   Callbacks = F.add(visitor, Callbacks);
  56 }
  57
  58 //===----------------------------------------------------------------------===//
  59 // Helper routines for walking the ExplodedGraph and fetching statements.
  60 //===----------------------------------------------------------------------===//
  61
  62 static inline const Stmt* GetStmt(const ProgramPoint &P) {
  63   if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P))
  64     return SP->getStmt();
  65   else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P))
  66     return BE->getSrc()->getTerminator();
  67
  68   return 0;
  69 }
  70
  71 static inline const ExplodedNode*
  72 GetPredecessorNode(const ExplodedNode* N) {
  73   return N->pred_empty() ? NULL : *(N->pred_begin());
  74 }
  75
  76 static inline const ExplodedNode*
  77 GetSuccessorNode(const ExplodedNode* N) {
  78   return N->succ_empty() ? NULL : *(N->succ_begin());
  79 }
  80
  81 static const Stmt* GetPreviousStmt(const ExplodedNode* N) {
  82   for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
  83     if (const Stmt *S = GetStmt(N->getLocation()))
  84       return S;
  85
  86   return 0;
  87 }
  88
  89 static const Stmt* GetNextStmt(const ExplodedNode* N) {
  90   for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
  91     if (const Stmt *S = GetStmt(N->getLocation())) {
  92       // Check if the statement is '?' or '&&'/'||'.  These are "merges",
  93       // not actual statement points.
  94       switch (S->getStmtClass()) {
  95         case Stmt::ChooseExprClass:
  96         case Stmt::BinaryConditionalOperatorClass: continue;
  97         case Stmt::ConditionalOperatorClass: continue;
  98         case Stmt::BinaryOperatorClass: {
  99           BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
 100           if (Op == BO_LAnd || Op == BO_LOr)
 101             continue;
 102           break;
 103         }
 104         default:
 105           break;
 106       }
 107
 108       // Some expressions don't have locations.
 109       if (S->getLocStart().isInvalid())
 110         continue;
 111
 112       return S;
 113     }
 114
 115   return 0;
 116 }
 117
 118 static inline const Stmt*
 119 GetCurrentOrPreviousStmt(const ExplodedNode* N) {
 120   if (const Stmt *S = GetStmt(N->getLocation()))
 121     return S;
 122
 123   return GetPreviousStmt(N);
 124 }
 125
 126 static inline const Stmt*
 127 GetCurrentOrNextStmt(const ExplodedNode* N) {
 128   if (const Stmt *S = GetStmt(N->getLocation()))
 129     return S;
 130
 131   return GetNextStmt(N);
 132 }
 133
 134 //===----------------------------------------------------------------------===//
 135 // PathDiagnosticBuilder and its associated routines and helper objects.
 136 //===----------------------------------------------------------------------===//
 137
 138 typedef llvm::DenseMap<const ExplodedNode*,
 139 const ExplodedNode*> NodeBackMap;
 140
 141 namespace {
 142 class NodeMapClosure : public BugReport::NodeResolver {
 143   NodeBackMap& M;
 144 public:
 145   NodeMapClosure(NodeBackMap *m) : M(*m) {}
 146   ~NodeMapClosure() {}
 147
 148   const ExplodedNode* getOriginalNode(const ExplodedNode* N) {
 149     NodeBackMap::iterator I = M.find(N);
 150     return I == M.end() ? 0 : I->second;
 151   }
 152 };
 153
 154 class PathDiagnosticBuilder : public BugReporterContext {
 155   BugReport *R;
 156   PathDiagnosticClient *PDC;
 157   llvm::OwningPtr<ParentMap> PM;
 158   NodeMapClosure NMC;
 159 public:
 160   PathDiagnosticBuilder(GRBugReporter &br,
 161                         BugReport *r, NodeBackMap *Backmap,
 162                         PathDiagnosticClient *pdc)
 163     : BugReporterContext(br),
 164       R(r), PDC(pdc), NMC(Backmap) {
 165     addVisitor(R);
 166   }
 167
 168   PathDiagnosticLocation ExecutionContinues(const ExplodedNode* N);
 169
 170   PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream& os,
 171                                             const ExplodedNode* N);
 172
 173   Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
 174
 175   ParentMap& getParentMap() { return R->getErrorNode()->getParentMap(); }
 176
 177   const Stmt *getParent(const Stmt *S) {
 178     return getParentMap().getParent(S);
 179   }
 180
 181   virtual NodeMapClosure& getNodeResolver() { return NMC; }
 182
 183   PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
 184
 185   PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const {
 186     return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive;
 187   }
 188
 189   bool supportsLogicalOpControlFlow() const {
 190     return PDC ? PDC->supportsLogicalOpControlFlow() : true;
 191   }
 192 };
 193 } // end anonymous namespace
 194
 195 PathDiagnosticLocation
 196 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode* N) {
 197   if (const Stmt *S = GetNextStmt(N))
 198     return PathDiagnosticLocation(S, getSourceManager());
 199
 200   return FullSourceLoc(N->getLocationContext()->getDecl()->getBodyRBrace(),
 201                        getSourceManager());
 202 }
 203
 204 PathDiagnosticLocation
 205 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream& os,
 206                                           const ExplodedNode* N) {
 207
 208   // Slow, but probably doesn't matter.
 209   if (os.str().empty())
 210     os << ' ';
 211
 212   const PathDiagnosticLocation &Loc = ExecutionContinues(N);
 213
 214   if (Loc.asStmt())
 215     os << "Execution continues on line "
 216        << getSourceManager().getInstantiationLineNumber(Loc.asLocation())
 217        << '.';
 218   else {
 219     os << "Execution jumps to the end of the ";
 220     const Decl *D = N->getLocationContext()->getDecl();
 221     if (isa<ObjCMethodDecl>(D))
 222       os << "method";
 223     else if (isa<FunctionDecl>(D))
 224       os << "function";
 225     else {
 226       assert(isa<BlockDecl>(D));
 227       os << "anonymous block";
 228     }
 229     os << '.';
 230   }
 231
 232   return Loc;
 233 }
 234
 235 static bool IsNested(const Stmt *S, ParentMap &PM) {
 236   if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
 237     return true;
 238
 239   const Stmt *Parent = PM.getParentIgnoreParens(S);
 240
 241   if (Parent)
 242     switch (Parent->getStmtClass()) {
 243       case Stmt::ForStmtClass:
 244       case Stmt::DoStmtClass:
 245       case Stmt::WhileStmtClass:
 246         return true;
 247       default:
 248         break;
 249     }
 250
 251   return false;
 252 }
 253
 254 PathDiagnosticLocation
 255 PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
 256   assert(S && "Null Stmt* passed to getEnclosingStmtLocation");
 257   ParentMap &P = getParentMap();
 258   SourceManager &SMgr = getSourceManager();
 259
 260   while (IsNested(S, P)) {
 261     const Stmt *Parent = P.getParentIgnoreParens(S);
 262
 263     if (!Parent)
 264       break;
 265
 266     switch (Parent->getStmtClass()) {
 267       case Stmt::BinaryOperatorClass: {
 268         const BinaryOperator *B = cast<BinaryOperator>(Parent);
 269         if (B->isLogicalOp())
 270           return PathDiagnosticLocation(S, SMgr);
 271         break;
 272       }
 273       case Stmt::CompoundStmtClass:
 274       case Stmt::StmtExprClass:
 275         return PathDiagnosticLocation(S, SMgr);
 276       case Stmt::ChooseExprClass:
 277         // Similar to '?' if we are referring to condition, just have the edge
 278         // point to the entire choose expression.
 279         if (cast<ChooseExpr>(Parent)->getCond() == S)
 280           return PathDiagnosticLocation(Parent, SMgr);
 281         else
 282           return PathDiagnosticLocation(S, SMgr);
 283       case Stmt::BinaryConditionalOperatorClass:
 284       case Stmt::ConditionalOperatorClass:
 285         // For '?', if we are referring to condition, just have the edge point
 286         // to the entire '?' expression.
 287         if (cast<AbstractConditionalOperator>(Parent)->getCond() == S)
 288           return PathDiagnosticLocation(Parent, SMgr);
 289         else
 290           return PathDiagnosticLocation(S, SMgr);
 291       case Stmt::DoStmtClass:
 292           return PathDiagnosticLocation(S, SMgr);
 293       case Stmt::ForStmtClass:
 294         if (cast<ForStmt>(Parent)->getBody() == S)
 295           return PathDiagnosticLocation(S, SMgr);
 296         break;
 297       case Stmt::IfStmtClass:
 298         if (cast<IfStmt>(Parent)->getCond() != S)
 299           return PathDiagnosticLocation(S, SMgr);
 300         break;
 301       case Stmt::ObjCForCollectionStmtClass:
 302         if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
 303           return PathDiagnosticLocation(S, SMgr);
 304         break;
 305       case Stmt::WhileStmtClass:
 306         if (cast<WhileStmt>(Parent)->getCond() != S)
 307           return PathDiagnosticLocation(S, SMgr);
 308         break;
 309       default:
 310         break;
 311     }
 312
 313     S = Parent;
 314   }
 315
 316   assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
 317
 318   // Special case: DeclStmts can appear in for statement declarations, in which
 319   //  case the ForStmt is the context.
 320   if (isa<DeclStmt>(S)) {
 321     if (const Stmt *Parent = P.getParent(S)) {
 322       switch (Parent->getStmtClass()) {
 323         case Stmt::ForStmtClass:
 324         case Stmt::ObjCForCollectionStmtClass:
 325           return PathDiagnosticLocation(Parent, SMgr);
 326         default:
 327           break;
 328       }
 329     }
 330   }
 331   else if (isa<BinaryOperator>(S)) {
 332     // Special case: the binary operator represents the initialization
 333     // code in a for statement (this can happen when the variable being
 334     // initialized is an old variable.
 335     if (const ForStmt *FS =
 336           dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
 337       if (FS->getInit() == S)
 338         return PathDiagnosticLocation(FS, SMgr);
 339     }
 340   }
 341
 342   return PathDiagnosticLocation(S, SMgr);
 343 }
 344
 345 //===----------------------------------------------------------------------===//
 346 // ScanNotableSymbols: closure-like callback for scanning Store bindings.
 347 //===----------------------------------------------------------------------===//
 348
 349 static const VarDecl*
 350 GetMostRecentVarDeclBinding(const ExplodedNode* N,
 351                             GRStateManager& VMgr, SVal X) {
 352
 353   for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
 354
 355     ProgramPoint P = N->getLocation();
 356
 357     if (!isa<PostStmt>(P))
 358       continue;
 359
 360     const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
 361
 362     if (!DR)
 363       continue;
 364
 365     SVal Y = N->getState()->getSVal(DR);
 366
 367     if (X != Y)
 368       continue;
 369
 370     const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
 371
 372     if (!VD)
 373       continue;
 374
 375     return VD;
 376   }
 377
 378   return 0;
 379 }
 380
 381 namespace {
 382 class NotableSymbolHandler
 383 : public StoreManager::BindingsHandler {
 384
 385   SymbolRef Sym;
 386   const GRState* PrevSt;
 387   const Stmt* S;
 388   GRStateManager& VMgr;
 389   const ExplodedNode* Pred;
 390   PathDiagnostic& PD;
 391   BugReporter& BR;
 392
 393 public:
 394
 395   NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s,
 396                        GRStateManager& vmgr, const ExplodedNode* pred,
 397                        PathDiagnostic& pd, BugReporter& br)
 398   : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
 399
 400   bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
 401                      SVal V) {
 402
 403     SymbolRef ScanSym = V.getAsSymbol();
 404
 405     if (ScanSym != Sym)
 406       return true;
 407
 408     // Check if the previous state has this binding.
 409     SVal X = PrevSt->getSVal(loc::MemRegionVal(R));
 410
 411     if (X == V) // Same binding?
 412       return true;
 413
 414     // Different binding.  Only handle assignments for now.  We don't pull
 415     // this check out of the loop because we will eventually handle other
 416     // cases.
 417
 418     VarDecl *VD = 0;
 419
 420     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
 421       if (!B->isAssignmentOp())
 422         return true;
 423
 424       // What variable did we assign to?
 425       DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
 426
 427       if (!DR)
 428         return true;
 429
 430       VD = dyn_cast<VarDecl>(DR->getDecl());
 431     }
 432     else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
 433       // FIXME: Eventually CFGs won't have DeclStmts.  Right now we
 434       //  assume that each DeclStmt has a single Decl.  This invariant
 435       //  holds by contruction in the CFG.
 436       VD = dyn_cast<VarDecl>(*DS->decl_begin());
 437     }
 438
 439     if (!VD)
 440       return true;
 441
 442     // What is the most recently referenced variable with this binding?
 443     const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
 444
 445     if (!MostRecent)
 446       return true;
 447
 448     // Create the diagnostic.
 449     FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
 450
 451     if (Loc::isLocType(VD->getType())) {
 452       std::string msg = "'" + std::string(VD->getNameAsString()) +
 453       "' now aliases '" + MostRecent->getNameAsString() + "'";
 454
 455       PD.push_front(new PathDiagnosticEventPiece(L, msg));
 456     }
 457
 458     return true;
 459   }
 460 };
 461 }
 462
 463 static void HandleNotableSymbol(const ExplodedNode* N,
 464                                 const Stmt* S,
 465                                 SymbolRef Sym, BugReporter& BR,
 466                                 PathDiagnostic& PD) {
 467
 468   const ExplodedNode* Pred = N->pred_empty() ? 0 : *N->pred_begin();
 469   const GRState* PrevSt = Pred ? Pred->getState() : 0;
 470
 471   if (!PrevSt)
 472     return;
 473
 474   // Look at the region bindings of the current state that map to the
 475   // specified symbol.  Are any of them not in the previous state?
 476   GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
 477   NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
 478   cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
 479 }
 480
 481 namespace {
 482 class ScanNotableSymbols
 483 : public StoreManager::BindingsHandler {
 484
 485   llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
 486   const ExplodedNode* N;
 487   const Stmt* S;
 488   GRBugReporter& BR;
 489   PathDiagnostic& PD;
 490
 491 public:
 492   ScanNotableSymbols(const ExplodedNode* n, const Stmt* s,
 493                      GRBugReporter& br, PathDiagnostic& pd)
 494   : N(n), S(s), BR(br), PD(pd) {}
 495
 496   bool HandleBinding(StoreManager& SMgr, Store store,
 497                      const MemRegion* R, SVal V) {
 498
 499     SymbolRef ScanSym = V.getAsSymbol();
 500
 501     if (!ScanSym)
 502       return true;
 503
 504     if (!BR.isNotable(ScanSym))
 505       return true;
 506
 507     if (AlreadyProcessed.count(ScanSym))
 508       return true;
 509
 510     AlreadyProcessed.insert(ScanSym);
 511
 512     HandleNotableSymbol(N, S, ScanSym, BR, PD);
 513     return true;
 514   }
 515 };
 516 } // end anonymous namespace
 517
 518 //===----------------------------------------------------------------------===//
 519 // "Minimal" path diagnostic generation algorithm.
 520 //===----------------------------------------------------------------------===//
 521
 522 static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM);
 523
 524 static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
 525                                           PathDiagnosticBuilder &PDB,
 526                                           const ExplodedNode *N) {
 527
 528   SourceManager& SMgr = PDB.getSourceManager();
 529   const ExplodedNode* NextNode = N->pred_empty()
 530                                         ? NULL : *(N->pred_begin());
 531   while (NextNode) {
 532     N = NextNode;
 533     NextNode = GetPredecessorNode(N);
 534
 535     ProgramPoint P = N->getLocation();
 536
 537     if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
 538       const CFGBlock* Src = BE->getSrc();
 539       const CFGBlock* Dst = BE->getDst();
 540       const Stmt* T = Src->getTerminator();
 541
 542       if (!T)
 543         continue;
 544
 545       FullSourceLoc Start(T->getLocStart(), SMgr);
 546
 547       switch (T->getStmtClass()) {
 548         default:
 549           break;
 550
 551         case Stmt::GotoStmtClass:
 552         case Stmt::IndirectGotoStmtClass: {
 553           const Stmt* S = GetNextStmt(N);
 554
 555           if (!S)
 556             continue;
 557
 558           std::string sbuf;
 559           llvm::raw_string_ostream os(sbuf);
 560           const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
 561
 562           os << "Control jumps to line "
 563           << End.asLocation().getInstantiationLineNumber();
 564           PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 565                                                            os.str()));
 566           break;
 567         }
 568
 569         case Stmt::SwitchStmtClass: {
 570           // Figure out what case arm we took.
 571           std::string sbuf;
 572           llvm::raw_string_ostream os(sbuf);
 573
 574           if (const Stmt* S = Dst->getLabel()) {
 575             PathDiagnosticLocation End(S, SMgr);
 576
 577             switch (S->getStmtClass()) {
 578               default:
 579                 os << "No cases match in the switch statement. "
 580                 "Control jumps to line "
 581                 << End.asLocation().getInstantiationLineNumber();
 582                 break;
 583               case Stmt::DefaultStmtClass:
 584                 os << "Control jumps to the 'default' case at line "
 585                 << End.asLocation().getInstantiationLineNumber();
 586                 break;
 587
 588               case Stmt::CaseStmtClass: {
 589                 os << "Control jumps to 'case ";
 590                 const CaseStmt* Case = cast<CaseStmt>(S);
 591                 const Expr* LHS = Case->getLHS()->IgnoreParenCasts();
 592
 593                 // Determine if it is an enum.
 594                 bool GetRawInt = true;
 595
 596                 if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
 597                   // FIXME: Maybe this should be an assertion.  Are there cases
 598                   // were it is not an EnumConstantDecl?
 599                   const EnumConstantDecl* D =
 600                     dyn_cast<EnumConstantDecl>(DR->getDecl());
 601
 602                   if (D) {
 603                     GetRawInt = false;
 604                     os << D;
 605                   }
 606                 }
 607
 608                 if (GetRawInt)
 609                   os << LHS->EvaluateAsInt(PDB.getASTContext());
 610
 611                 os << ":'  at line "
 612                 << End.asLocation().getInstantiationLineNumber();
 613                 break;
 614               }
 615             }
 616             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 617                                                              os.str()));
 618           }
 619           else {
 620             os << "'Default' branch taken. ";
 621             const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
 622             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 623                                                              os.str()));
 624           }
 625
 626           break;
 627         }
 628
 629         case Stmt::BreakStmtClass:
 630         case Stmt::ContinueStmtClass: {
 631           std::string sbuf;
 632           llvm::raw_string_ostream os(sbuf);
 633           PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 634           PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 635                                                            os.str()));
 636           break;
 637         }
 638
 639           // Determine control-flow for ternary '?'.
 640         case Stmt::BinaryConditionalOperatorClass:
 641         case Stmt::ConditionalOperatorClass: {
 642           std::string sbuf;
 643           llvm::raw_string_ostream os(sbuf);
 644           os << "'?' condition is ";
 645
 646           if (*(Src->succ_begin()+1) == Dst)
 647             os << "false";
 648           else
 649             os << "true";
 650
 651           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 652
 653           if (const Stmt *S = End.asStmt())
 654             End = PDB.getEnclosingStmtLocation(S);
 655
 656           PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 657                                                            os.str()));
 658           break;
 659         }
 660
 661           // Determine control-flow for short-circuited '&&' and '||'.
 662         case Stmt::BinaryOperatorClass: {
 663           if (!PDB.supportsLogicalOpControlFlow())
 664             break;
 665
 666           const BinaryOperator *B = cast<BinaryOperator>(T);
 667           std::string sbuf;
 668           llvm::raw_string_ostream os(sbuf);
 669           os << "Left side of '";
 670
 671           if (B->getOpcode() == BO_LAnd) {
 672             os << "&&" << "' is ";
 673
 674             if (*(Src->succ_begin()+1) == Dst) {
 675               os << "false";
 676               PathDiagnosticLocation End(B->getLHS(), SMgr);
 677               PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
 678               PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 679                                                                os.str()));
 680             }
 681             else {
 682               os << "true";
 683               PathDiagnosticLocation Start(B->getLHS(), SMgr);
 684               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 685               PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 686                                                                os.str()));
 687             }
 688           }
 689           else {
 690             assert(B->getOpcode() == BO_LOr);
 691             os << "||" << "' is ";
 692
 693             if (*(Src->succ_begin()+1) == Dst) {
 694               os << "false";
 695               PathDiagnosticLocation Start(B->getLHS(), SMgr);
 696               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 697               PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 698                                                                os.str()));
 699             }
 700             else {
 701               os << "true";
 702               PathDiagnosticLocation End(B->getLHS(), SMgr);
 703               PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
 704               PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 705                                                                os.str()));
 706             }
 707           }
 708
 709           break;
 710         }
 711
 712         case Stmt::DoStmtClass:  {
 713           if (*(Src->succ_begin()) == Dst) {
 714             std::string sbuf;
 715             llvm::raw_string_ostream os(sbuf);
 716
 717             os << "Loop condition is true. ";
 718             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 719
 720             if (const Stmt *S = End.asStmt())
 721               End = PDB.getEnclosingStmtLocation(S);
 722
 723             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 724                                                              os.str()));
 725           }
 726           else {
 727             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 728
 729             if (const Stmt *S = End.asStmt())
 730               End = PDB.getEnclosingStmtLocation(S);
 731
 732             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 733                               "Loop condition is false.  Exiting loop"));
 734           }
 735
 736           break;
 737         }
 738
 739         case Stmt::WhileStmtClass:
 740         case Stmt::ForStmtClass: {
 741           if (*(Src->succ_begin()+1) == Dst) {
 742             std::string sbuf;
 743             llvm::raw_string_ostream os(sbuf);
 744
 745             os << "Loop condition is false. ";
 746             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 747             if (const Stmt *S = End.asStmt())
 748               End = PDB.getEnclosingStmtLocation(S);
 749
 750             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 751                                                              os.str()));
 752           }
 753           else {
 754             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 755             if (const Stmt *S = End.asStmt())
 756               End = PDB.getEnclosingStmtLocation(S);
 757
 758             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 759                             "Loop condition is true.  Entering loop body"));
 760           }
 761
 762           break;
 763         }
 764
 765         case Stmt::IfStmtClass: {
 766           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 767
 768           if (const Stmt *S = End.asStmt())
 769             End = PDB.getEnclosingStmtLocation(S);
 770
 771           if (*(Src->succ_begin()+1) == Dst)
 772             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 773                                                         "Taking false branch"));
 774           else
 775             PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
 776                                                          "Taking true branch"));
 777
 778           break;
 779         }
 780       }
 781     }
 782
 783     if (NextNode) {
 784       for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
 785            E = PDB.visitor_end(); I!=E; ++I) {
 786         if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB))
 787           PD.push_front(p);
 788       }
 789     }
 790
 791     if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
 792       // Scan the region bindings, and see if a "notable" symbol has a new
 793       // lval binding.
 794       ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD);
 795       PDB.getStateManager().iterBindings(N->getState(), SNS);
 796     }
 797   }
 798
 799   // After constructing the full PathDiagnostic, do a pass over it to compact
 800   // PathDiagnosticPieces that occur within a macro.
 801   CompactPathDiagnostic(PD, PDB.getSourceManager());
 802 }
 803
 804 //===----------------------------------------------------------------------===//
 805 // "Extensive" PathDiagnostic generation.
 806 //===----------------------------------------------------------------------===//
 807
 808 static bool IsControlFlowExpr(const Stmt *S) {
 809   const Expr *E = dyn_cast<Expr>(S);
 810
 811   if (!E)
 812     return false;
 813
 814   E = E->IgnoreParenCasts();
 815
 816   if (isa<AbstractConditionalOperator>(E))
 817     return true;
 818
 819   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
 820     if (B->isLogicalOp())
 821       return true;
 822
 823   return false;
 824 }
 825
 826 namespace {
 827 class ContextLocation : public PathDiagnosticLocation {
 828   bool IsDead;
 829 public:
 830   ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
 831     : PathDiagnosticLocation(L), IsDead(isdead) {}
 832
 833   void markDead() { IsDead = true; }
 834   bool isDead() const { return IsDead; }
 835 };
 836
 837 class EdgeBuilder {
 838   std::vector<ContextLocation> CLocs;
 839   typedef std::vector<ContextLocation>::iterator iterator;
 840   PathDiagnostic &PD;
 841   PathDiagnosticBuilder &PDB;
 842   PathDiagnosticLocation PrevLoc;
 843
 844   bool IsConsumedExpr(const PathDiagnosticLocation &L);
 845
 846   bool containsLocation(const PathDiagnosticLocation &Container,
 847                         const PathDiagnosticLocation &Containee);
 848
 849   PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
 850
 851   PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
 852                                          bool firstCharOnly = false) {
 853     if (const Stmt *S = L.asStmt()) {
 854       const Stmt *Original = S;
 855       while (1) {
 856         // Adjust the location for some expressions that are best referenced
 857         // by one of their subexpressions.
 858         switch (S->getStmtClass()) {
 859           default:
 860             break;
 861           case Stmt::ParenExprClass:
 862             S = cast<ParenExpr>(S)->IgnoreParens();
 863             firstCharOnly = true;
 864             continue;
 865           case Stmt::BinaryConditionalOperatorClass:
 866           case Stmt::ConditionalOperatorClass:
 867             S = cast<AbstractConditionalOperator>(S)->getCond();
 868             firstCharOnly = true;
 869             continue;
 870           case Stmt::ChooseExprClass:
 871             S = cast<ChooseExpr>(S)->getCond();
 872             firstCharOnly = true;
 873             continue;
 874           case Stmt::BinaryOperatorClass:
 875             S = cast<BinaryOperator>(S)->getLHS();
 876             firstCharOnly = true;
 877             continue;
 878         }
 879
 880         break;
 881       }
 882
 883       if (S != Original)
 884         L = PathDiagnosticLocation(S, L.getManager());
 885     }
 886
 887     if (firstCharOnly)
 888       L = PathDiagnosticLocation(L.asLocation());
 889
 890     return L;
 891   }
 892
 893   void popLocation() {
 894     if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
 895       // For contexts, we only one the first character as the range.
 896       rawAddEdge(cleanUpLocation(CLocs.back(), true));
 897     }
 898     CLocs.pop_back();
 899   }
 900
 901 public:
 902   EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
 903     : PD(pd), PDB(pdb) {
 904
 905       // If the PathDiagnostic already has pieces, add the enclosing statement
 906       // of the first piece as a context as well.
 907       if (!PD.empty()) {
 908         PrevLoc = PD.begin()->getLocation();
 909
 910         if (const Stmt *S = PrevLoc.asStmt())
 911           addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
 912       }
 913   }
 914
 915   ~EdgeBuilder() {
 916     while (!CLocs.empty()) popLocation();
 917
 918     // Finally, add an initial edge from the start location of the first
 919     // statement (if it doesn't already exist).
 920     // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
 921     if (const CompoundStmt *CS =
 922           dyn_cast_or_null<CompoundStmt>(PDB.getCodeDecl().getBody()))
 923       if (!CS->body_empty()) {
 924         SourceLocation Loc = (*CS->body_begin())->getLocStart();
 925         rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager()));
 926       }
 927
 928   }
 929
 930   void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
 931
 932   void rawAddEdge(PathDiagnosticLocation NewLoc);
 933
 934   void addContext(const Stmt *S);
 935   void addExtendedContext(const Stmt *S);
 936 };
 937 } // end anonymous namespace
 938
 939
 940 PathDiagnosticLocation
 941 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
 942   if (const Stmt *S = L.asStmt()) {
 943     if (IsControlFlowExpr(S))
 944       return L;
 945
 946     return PDB.getEnclosingStmtLocation(S);
 947   }
 948
 949   return L;
 950 }
 951
 952 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
 953                                    const PathDiagnosticLocation &Containee) {
 954
 955   if (Container == Containee)
 956     return true;
 957
 958   if (Container.asDecl())
 959     return true;
 960
 961   if (const Stmt *S = Containee.asStmt())
 962     if (const Stmt *ContainerS = Container.asStmt()) {
 963       while (S) {
 964         if (S == ContainerS)
 965           return true;
 966         S = PDB.getParent(S);
 967       }
 968       return false;
 969     }
 970
 971   // Less accurate: compare using source ranges.
 972   SourceRange ContainerR = Container.asRange();
 973   SourceRange ContaineeR = Containee.asRange();
 974
 975   SourceManager &SM = PDB.getSourceManager();
 976   SourceLocation ContainerRBeg = SM.getInstantiationLoc(ContainerR.getBegin());
 977   SourceLocation ContainerREnd = SM.getInstantiationLoc(ContainerR.getEnd());
 978   SourceLocation ContaineeRBeg = SM.getInstantiationLoc(ContaineeR.getBegin());
 979   SourceLocation ContaineeREnd = SM.getInstantiationLoc(ContaineeR.getEnd());
 980
 981   unsigned ContainerBegLine = SM.getInstantiationLineNumber(ContainerRBeg);
 982   unsigned ContainerEndLine = SM.getInstantiationLineNumber(ContainerREnd);
 983   unsigned ContaineeBegLine = SM.getInstantiationLineNumber(ContaineeRBeg);
 984   unsigned ContaineeEndLine = SM.getInstantiationLineNumber(ContaineeREnd);
 985
 986   assert(ContainerBegLine <= ContainerEndLine);
 987   assert(ContaineeBegLine <= ContaineeEndLine);
 988
 989   return (ContainerBegLine <= ContaineeBegLine &&
 990           ContainerEndLine >= ContaineeEndLine &&
 991           (ContainerBegLine != ContaineeBegLine ||
 992            SM.getInstantiationColumnNumber(ContainerRBeg) <=
 993            SM.getInstantiationColumnNumber(ContaineeRBeg)) &&
 994           (ContainerEndLine != ContaineeEndLine ||
 995            SM.getInstantiationColumnNumber(ContainerREnd) >=
 996            SM.getInstantiationColumnNumber(ContainerREnd)));
 997 }
 998
 999 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1000   if (!PrevLoc.isValid()) {
1001     PrevLoc = NewLoc;
1002     return;
1003   }
1004
1005   const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
1006   const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
1007
1008   if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1009     return;
1010
1011   // FIXME: Ignore intra-macro edges for now.
1012   if (NewLocClean.asLocation().getInstantiationLoc() ==
1013       PrevLocClean.asLocation().getInstantiationLoc())
1014     return;
1015
1016   PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1017   PrevLoc = NewLoc;
1018 }
1019
1020 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
1021
1022   if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1023     return;
1024
1025   const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1026
1027   while (!CLocs.empty()) {
1028     ContextLocation &TopContextLoc = CLocs.back();
1029
1030     // Is the top location context the same as the one for the new location?
1031     if (TopContextLoc == CLoc) {
1032       if (alwaysAdd) {
1033         if (IsConsumedExpr(TopContextLoc) &&
1034             !IsControlFlowExpr(TopContextLoc.asStmt()))
1035             TopContextLoc.markDead();
1036
1037         rawAddEdge(NewLoc);
1038       }
1039
1040       return;
1041     }
1042
1043     if (containsLocation(TopContextLoc, CLoc)) {
1044       if (alwaysAdd) {
1045         rawAddEdge(NewLoc);
1046
1047         if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
1048           CLocs.push_back(ContextLocation(CLoc, true));
1049           return;
1050         }
1051       }
1052
1053       CLocs.push_back(CLoc);
1054       return;
1055     }
1056
1057     // Context does not contain the location.  Flush it.
1058     popLocation();
1059   }
1060
1061   // If we reach here, there is no enclosing context.  Just add the edge.
1062   rawAddEdge(NewLoc);
1063 }
1064
1065 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1066   if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1067     return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1068
1069   return false;
1070 }
1071
1072 void EdgeBuilder::addExtendedContext(const Stmt *S) {
1073   if (!S)
1074     return;
1075
1076   const Stmt *Parent = PDB.getParent(S);
1077   while (Parent) {
1078     if (isa<CompoundStmt>(Parent))
1079       Parent = PDB.getParent(Parent);
1080     else
1081       break;
1082   }
1083
1084   if (Parent) {
1085     switch (Parent->getStmtClass()) {
1086       case Stmt::DoStmtClass:
1087       case Stmt::ObjCAtSynchronizedStmtClass:
1088         addContext(Parent);
1089       default:
1090         break;
1091     }
1092   }
1093
1094   addContext(S);
1095 }
1096
1097 void EdgeBuilder::addContext(const Stmt *S) {
1098   if (!S)
1099     return;
1100
1101   PathDiagnosticLocation L(S, PDB.getSourceManager());
1102
1103   while (!CLocs.empty()) {
1104     const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1105
1106     // Is the top location context the same as the one for the new location?
1107     if (TopContextLoc == L)
1108       return;
1109
1110     if (containsLocation(TopContextLoc, L)) {
1111       CLocs.push_back(L);
1112       return;
1113     }
1114
1115     // Context does not contain the location.  Flush it.
1116     popLocation();
1117   }
1118
1119   CLocs.push_back(L);
1120 }
1121
1122 static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1123                                             PathDiagnosticBuilder &PDB,
1124                                             const ExplodedNode *N) {
1125   EdgeBuilder EB(PD, PDB);
1126
1127   const ExplodedNode* NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
1128   while (NextNode) {
1129     N = NextNode;
1130     NextNode = GetPredecessorNode(N);
1131     ProgramPoint P = N->getLocation();
1132
1133     do {
1134       // Block edges.
1135       if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
1136         const CFGBlock &Blk = *BE->getSrc();
1137         const Stmt *Term = Blk.getTerminator();
1138
1139         // Are we jumping to the head of a loop?  Add a special diagnostic.
1140         if (const Stmt *Loop = BE->getDst()->getLoopTarget()) {
1141           PathDiagnosticLocation L(Loop, PDB.getSourceManager());
1142           const CompoundStmt *CS = NULL;
1143
1144           if (!Term) {
1145             if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1146               CS = dyn_cast<CompoundStmt>(FS->getBody());
1147             else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1148               CS = dyn_cast<CompoundStmt>(WS->getBody());
1149           }
1150
1151           PathDiagnosticEventPiece *p =
1152             new PathDiagnosticEventPiece(L,
1153                                         "Looping back to the head of the loop");
1154
1155           EB.addEdge(p->getLocation(), true);
1156           PD.push_front(p);
1157
1158           if (CS) {
1159             PathDiagnosticLocation BL(CS->getRBracLoc(),
1160                                       PDB.getSourceManager());
1161             BL = PathDiagnosticLocation(BL.asLocation());
1162             EB.addEdge(BL);
1163           }
1164         }
1165
1166         if (Term)
1167           EB.addContext(Term);
1168
1169         break;
1170       }
1171
1172       if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
1173         if (CFGStmt S = BE->getFirstElement().getAs<CFGStmt>()) {
1174           if (IsControlFlowExpr(S)) {
1175             // Add the proper context for '&&', '||', and '?'.
1176             EB.addContext(S);
1177           }
1178           else
1179             EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1180         }
1181
1182         break;
1183       }
1184     } while (0);
1185
1186     if (!NextNode)
1187       continue;
1188
1189     for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
1190          E = PDB.visitor_end(); I!=E; ++I) {
1191       if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) {
1192         const PathDiagnosticLocation &Loc = p->getLocation();
1193         EB.addEdge(Loc, true);
1194         PD.push_front(p);
1195         if (const Stmt *S = Loc.asStmt())
1196           EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1197       }
1198     }
1199   }
1200 }
1201
1202 //===----------------------------------------------------------------------===//
1203 // Methods for BugType and subclasses.
1204 //===----------------------------------------------------------------------===//
1205 BugType::~BugType() {
1206   // Free up the equivalence class objects.  Observe that we get a pointer to
1207   // the object first before incrementing the iterator, as destroying the
1208   // node before doing so means we will read from freed memory.
1209   for (iterator I = begin(), E = end(); I !=E; ) {
1210     BugReportEquivClass *EQ = &*I;
1211     ++I;
1212     delete EQ;
1213   }
1214 }
1215 void BugType::FlushReports(BugReporter &BR) {}
1216
1217 //===----------------------------------------------------------------------===//
1218 // Methods for BugReport and subclasses.
1219 //===----------------------------------------------------------------------===//
1220 BugReport::~BugReport() {}
1221 RangedBugReport::~RangedBugReport() {}
1222
1223 const Stmt* BugReport::getStmt() const {
1224   ProgramPoint ProgP = ErrorNode->getLocation();
1225   const Stmt *S = NULL;
1226
1227   if (BlockEntrance* BE = dyn_cast<BlockEntrance>(&ProgP)) {
1228     CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
1229     if (BE->getBlock() == &Exit)
1230       S = GetPreviousStmt(ErrorNode);
1231   }
1232   if (!S)
1233     S = GetStmt(ProgP);
1234
1235   return S;
1236 }
1237
1238 PathDiagnosticPiece*
1239 BugReport::getEndPath(BugReporterContext& BRC,
1240                       const ExplodedNode* EndPathNode) {
1241
1242   const Stmt* S = getStmt();
1243
1244   if (!S)
1245     return NULL;
1246
1247   BugReport::ranges_iterator Beg, End;
1248   llvm::tie(Beg, End) = getRanges();
1249   PathDiagnosticLocation L(S, BRC.getSourceManager());
1250
1251   // Only add the statement itself as a range if we didn't specify any
1252   // special ranges for this report.
1253   PathDiagnosticPiece* P = new PathDiagnosticEventPiece(L, getDescription(),
1254                                                         Beg == End);
1255
1256   for (; Beg != End; ++Beg)
1257     P->addRange(*Beg);
1258
1259   return P;
1260 }
1261
1262 std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
1263 BugReport::getRanges() const {
1264   if (const Expr* E = dyn_cast_or_null<Expr>(getStmt())) {
1265     R = E->getSourceRange();
1266     assert(R.isValid());
1267     return std::make_pair(&R, &R+1);
1268   }
1269   else
1270     return std::make_pair(ranges_iterator(), ranges_iterator());
1271 }
1272
1273 SourceLocation BugReport::getLocation() const {
1274   if (ErrorNode)
1275     if (const Stmt* S = GetCurrentOrPreviousStmt(ErrorNode)) {
1276       // For member expressions, return the location of the '.' or '->'.
1277       if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
1278         return ME->getMemberLoc();
1279       // For binary operators, return the location of the operator.
1280       if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
1281         return B->getOperatorLoc();
1282
1283       return S->getLocStart();
1284     }
1285
1286   return FullSourceLoc();
1287 }
1288
1289 PathDiagnosticPiece* BugReport::VisitNode(const ExplodedNode* N,
1290                                           const ExplodedNode* PrevN,
1291                                           BugReporterContext &BRC) {
1292   return NULL;
1293 }
1294
1295 //===----------------------------------------------------------------------===//
1296 // Methods for BugReporter and subclasses.
1297 //===----------------------------------------------------------------------===//
1298
1299 BugReportEquivClass::~BugReportEquivClass() {
1300   for (iterator I=begin(), E=end(); I!=E; ++I) delete *I;
1301 }
1302
1303 GRBugReporter::~GRBugReporter() { }
1304 BugReporterData::~BugReporterData() {}
1305
1306 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
1307
1308 GRStateManager&
1309 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1310
1311 BugReporter::~BugReporter() { FlushReports(); }
1312
1313 void BugReporter::FlushReports() {
1314   if (BugTypes.isEmpty())
1315     return;
1316
1317   // First flush the warnings for each BugType.  This may end up creating new
1318   // warnings and new BugTypes.  Because ImmutableSet is a functional data
1319   // structure, we do not need to worry about the iterators being invalidated.
1320   for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
1321     const_cast<BugType*>(*I)->FlushReports(*this);
1322
1323   // Iterate through BugTypes a second time.  BugTypes may have been updated
1324   // with new BugType objects and new warnings.
1325   for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I) {
1326     BugType *BT = const_cast<BugType*>(*I);
1327
1328     typedef llvm::FoldingSet<BugReportEquivClass> SetTy;
1329     SetTy& EQClasses = BT->EQClasses;
1330
1331     for (SetTy::iterator EI=EQClasses.begin(), EE=EQClasses.end(); EI!=EE;++EI){
1332       BugReportEquivClass& EQ = *EI;
1333       FlushReport(EQ);
1334     }
1335
1336     // Delete the BugType object.
1337     delete BT;
1338   }
1339
1340   // Remove all references to the BugType objects.
1341   BugTypes = F.getEmptySet();
1342 }
1343
1344 //===----------------------------------------------------------------------===//
1345 // PathDiagnostics generation.
1346 //===----------------------------------------------------------------------===//
1347
1348 static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1349                  std::pair<ExplodedNode*, unsigned> >
1350 MakeReportGraph(const ExplodedGraph* G,
1351                 llvm::SmallVectorImpl<const ExplodedNode*> &nodes) {
1352
1353   // Create the trimmed graph.  It will contain the shortest paths from the
1354   // error nodes to the root.  In the new graph we should only have one
1355   // error node unless there are two or more error nodes with the same minimum
1356   // path length.
1357   ExplodedGraph* GTrim;
1358   InterExplodedGraphMap* NMap;
1359
1360   llvm::DenseMap<const void*, const void*> InverseMap;
1361   llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(),
1362                                    &InverseMap);
1363
1364   // Create owning pointers for GTrim and NMap just to ensure that they are
1365   // released when this function exists.
1366   llvm::OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
1367   llvm::OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
1368
1369   // Find the (first) error node in the trimmed graph.  We just need to consult
1370   // the node map (NMap) which maps from nodes in the original graph to nodes
1371   // in the new graph.
1372
1373   std::queue<const ExplodedNode*> WS;
1374   typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
1375   IndexMapTy IndexMap;
1376
1377   for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) {
1378     const ExplodedNode *originalNode = nodes[nodeIndex];
1379     if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) {
1380       WS.push(N);
1381       IndexMap[originalNode] = nodeIndex;
1382     }
1383   }
1384
1385   assert(!WS.empty() && "No error node found in the trimmed graph.");
1386
1387   // Create a new (third!) graph with a single path.  This is the graph
1388   // that will be returned to the caller.
1389   ExplodedGraph *GNew = new ExplodedGraph();
1390
1391   // Sometimes the trimmed graph can contain a cycle.  Perform a reverse BFS
1392   // to the root node, and then construct a new graph that contains only
1393   // a single path.
1394   llvm::DenseMap<const void*,unsigned> Visited;
1395
1396   unsigned cnt = 0;
1397   const ExplodedNode* Root = 0;
1398
1399   while (!WS.empty()) {
1400     const ExplodedNode* Node = WS.front();
1401     WS.pop();
1402
1403     if (Visited.find(Node) != Visited.end())
1404       continue;
1405
1406     Visited[Node] = cnt++;
1407
1408     if (Node->pred_empty()) {
1409       Root = Node;
1410       break;
1411     }
1412
1413     for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
1414          E=Node->pred_end(); I!=E; ++I)
1415       WS.push(*I);
1416   }
1417
1418   assert(Root);
1419
1420   // Now walk from the root down the BFS path, always taking the successor
1421   // with the lowest number.
1422   ExplodedNode *Last = 0, *First = 0;
1423   NodeBackMap *BM = new NodeBackMap();
1424   unsigned NodeIndex = 0;
1425
1426   for ( const ExplodedNode *N = Root ;;) {
1427     // Lookup the number associated with the current node.
1428     llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
1429     assert(I != Visited.end());
1430
1431     // Create the equivalent node in the new graph with the same state
1432     // and location.
1433     ExplodedNode* NewN = GNew->getNode(N->getLocation(), N->getState());
1434
1435     // Store the mapping to the original node.
1436     llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
1437     assert(IMitr != InverseMap.end() && "No mapping to original node.");
1438     (*BM)[NewN] = (const ExplodedNode*) IMitr->second;
1439
1440     // Link up the new node with the previous node.
1441     if (Last)
1442       NewN->addPredecessor(Last, *GNew);
1443
1444     Last = NewN;
1445
1446     // Are we at the final node?
1447     IndexMapTy::iterator IMI =
1448       IndexMap.find((const ExplodedNode*)(IMitr->second));
1449     if (IMI != IndexMap.end()) {
1450       First = NewN;
1451       NodeIndex = IMI->second;
1452       break;
1453     }
1454
1455     // Find the next successor node.  We choose the node that is marked
1456     // with the lowest DFS number.
1457     ExplodedNode::const_succ_iterator SI = N->succ_begin();
1458     ExplodedNode::const_succ_iterator SE = N->succ_end();
1459     N = 0;
1460
1461     for (unsigned MinVal = 0; SI != SE; ++SI) {
1462
1463       I = Visited.find(*SI);
1464
1465       if (I == Visited.end())
1466         continue;
1467
1468       if (!N || I->second < MinVal) {
1469         N = *SI;
1470         MinVal = I->second;
1471       }
1472     }
1473
1474     assert(N);
1475   }
1476
1477   assert(First);
1478
1479   return std::make_pair(std::make_pair(GNew, BM),
1480                         std::make_pair(First, NodeIndex));
1481 }
1482
1483 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
1484 ///  and collapses PathDiagosticPieces that are expanded by macros.
1485 static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM) {
1486   typedef std::vector<std::pair<PathDiagnosticMacroPiece*, SourceLocation> >
1487           MacroStackTy;
1488
1489   typedef std::vector<PathDiagnosticPiece*>
1490           PiecesTy;
1491
1492   MacroStackTy MacroStack;
1493   PiecesTy Pieces;
1494
1495   for (PathDiagnostic::iterator I = PD.begin(), E = PD.end(); I!=E; ++I) {
1496     // Get the location of the PathDiagnosticPiece.
1497     const FullSourceLoc Loc = I->getLocation().asLocation();
1498
1499     // Determine the instantiation location, which is the location we group
1500     // related PathDiagnosticPieces.
1501     SourceLocation InstantiationLoc = Loc.isMacroID() ?
1502                                       SM.getInstantiationLoc(Loc) :
1503                                       SourceLocation();
1504
1505     if (Loc.isFileID()) {
1506       MacroStack.clear();
1507       Pieces.push_back(&*I);
1508       continue;
1509     }
1510
1511     assert(Loc.isMacroID());
1512
1513     // Is the PathDiagnosticPiece within the same macro group?
1514     if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
1515       MacroStack.back().first->push_back(&*I);
1516       continue;
1517     }
1518
1519     // We aren't in the same group.  Are we descending into a new macro
1520     // or are part of an old one?
1521     PathDiagnosticMacroPiece *MacroGroup = 0;
1522
1523     SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
1524                                           SM.getInstantiationLoc(Loc) :
1525                                           SourceLocation();
1526
1527     // Walk the entire macro stack.
1528     while (!MacroStack.empty()) {
1529       if (InstantiationLoc == MacroStack.back().second) {
1530         MacroGroup = MacroStack.back().first;
1531         break;
1532       }
1533
1534       if (ParentInstantiationLoc == MacroStack.back().second) {
1535         MacroGroup = MacroStack.back().first;
1536         break;
1537       }
1538
1539       MacroStack.pop_back();
1540     }
1541
1542     if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
1543       // Create a new macro group and add it to the stack.
1544       PathDiagnosticMacroPiece *NewGroup = new PathDiagnosticMacroPiece(Loc);
1545
1546       if (MacroGroup)
1547         MacroGroup->push_back(NewGroup);
1548       else {
1549         assert(InstantiationLoc.isFileID());
1550         Pieces.push_back(NewGroup);
1551       }
1552
1553       MacroGroup = NewGroup;
1554       MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
1555     }
1556
1557     // Finally, add the PathDiagnosticPiece to the group.
1558     MacroGroup->push_back(&*I);
1559   }
1560
1561   // Now take the pieces and construct a new PathDiagnostic.
1562   PD.resetPath(false);
1563
1564   for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I) {
1565     if (PathDiagnosticMacroPiece *MP=dyn_cast<PathDiagnosticMacroPiece>(*I))
1566       if (!MP->containsEvent()) {
1567         delete MP;
1568         continue;
1569       }
1570
1571     PD.push_back(*I);
1572   }
1573 }
1574
1575 void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
1576                         llvm::SmallVectorImpl<BugReport *> &bugReports) {
1577
1578   assert(!bugReports.empty());
1579   llvm::SmallVector<const ExplodedNode *, 10> errorNodes;
1580   for (llvm::SmallVectorImpl<BugReport*>::iterator I = bugReports.begin(),
1581     E = bugReports.end(); I != E; ++I) {
1582       errorNodes.push_back((*I)->getErrorNode());
1583   }
1584
1585   // Construct a new graph that contains only a single path from the error
1586   // node to a root.
1587   const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1588   std::pair<ExplodedNode*, unsigned> >&
1589     GPair = MakeReportGraph(&getGraph(), errorNodes);
1590
1591   // Find the BugReport with the original location.
1592   assert(GPair.second.second < bugReports.size());
1593   BugReport *R = bugReports[GPair.second.second];
1594   assert(R && "No original report found for sliced graph.");
1595
1596   llvm::OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
1597   llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second);
1598   const ExplodedNode *N = GPair.second.first;
1599
1600   // Start building the path diagnostic...
1601   PathDiagnosticBuilder PDB(*this, R, BackMap.get(), getPathDiagnosticClient());
1602
1603   if (PathDiagnosticPiece* Piece = R->getEndPath(PDB, N))
1604     PD.push_back(Piece);
1605   else
1606     return;
1607
1608   // Register node visitors.
1609   R->registerInitialVisitors(PDB, N);
1610   bugreporter::registerNilReceiverVisitor(PDB);
1611
1612   switch (PDB.getGenerationScheme()) {
1613     case PathDiagnosticClient::Extensive:
1614       GenerateExtensivePathDiagnostic(PD, PDB, N);
1615       break;
1616     case PathDiagnosticClient::Minimal:
1617       GenerateMinimalPathDiagnostic(PD, PDB, N);
1618       break;
1619   }
1620 }
1621
1622 void BugReporter::Register(BugType *BT) {
1623   BugTypes = F.add(BugTypes, BT);
1624 }
1625
1626 void BugReporter::EmitReport(BugReport* R) {
1627   // Compute the bug report's hash to determine its equivalence class.
1628   llvm::FoldingSetNodeID ID;
1629   R->Profile(ID);
1630
1631   // Lookup the equivance class.  If there isn't one, create it.
1632   BugType& BT = R->getBugType();
1633   Register(&BT);
1634   void *InsertPos;
1635   BugReportEquivClass* EQ = BT.EQClasses.FindNodeOrInsertPos(ID, InsertPos);
1636
1637   if (!EQ) {
1638     EQ = new BugReportEquivClass(R);
1639     BT.EQClasses.InsertNode(EQ, InsertPos);
1640   }
1641   else
1642     EQ->AddReport(R);
1643 }
1644
1645
1646 //===----------------------------------------------------------------------===//
1647 // Emitting reports in equivalence classes.
1648 //===----------------------------------------------------------------------===//
1649
1650 namespace {
1651 struct FRIEC_WLItem {
1652   const ExplodedNode *N;
1653   ExplodedNode::const_succ_iterator I, E;
1654
1655   FRIEC_WLItem(const ExplodedNode *n)
1656   : N(n), I(N->succ_begin()), E(N->succ_end()) {}
1657 };
1658 }
1659
1660 static BugReport *
1661 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
1662                              llvm::SmallVectorImpl<BugReport*> &bugReports) {
1663
1664   BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
1665   assert(I != E);
1666   BugReport *R = *I;
1667   BugType& BT = R->getBugType();
1668
1669   // If we don't need to suppress any of the nodes because they are
1670   // post-dominated by a sink, simply add all the nodes in the equivalence class
1671   // to 'Nodes'.  Any of the reports will serve as a "representative" report.
1672   if (!BT.isSuppressOnSink()) {
1673     for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
1674       const ExplodedNode* N = I->getErrorNode();
1675       if (N) {
1676         R = *I;
1677         bugReports.push_back(R);
1678       }
1679     }
1680     return R;
1681   }
1682
1683   // For bug reports that should be suppressed when all paths are post-dominated
1684   // by a sink node, iterate through the reports in the equivalence class
1685   // until we find one that isn't post-dominated (if one exists).  We use a
1686   // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
1687   // this as a recursive function, but we don't want to risk blowing out the
1688   // stack for very long paths.
1689   BugReport *exampleReport = 0;
1690
1691   for (; I != E; ++I) {
1692     R = *I;
1693     const ExplodedNode *errorNode = R->getErrorNode();
1694
1695     if (!errorNode)
1696       continue;
1697     if (errorNode->isSink()) {
1698       assert(false &&
1699            "BugType::isSuppressSink() should not be 'true' for sink end nodes");
1700       return 0;
1701     }
1702     // No successors?  By definition this nodes isn't post-dominated by a sink.
1703     if (errorNode->succ_empty()) {
1704       bugReports.push_back(R);
1705       if (!exampleReport)
1706         exampleReport = R;
1707       continue;
1708     }
1709
1710     // At this point we know that 'N' is not a sink and it has at least one
1711     // successor.  Use a DFS worklist to find a non-sink end-of-path node.
1712     typedef FRIEC_WLItem WLItem;
1713     typedef llvm::SmallVector<WLItem, 10> DFSWorkList;
1714     llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
1715
1716     DFSWorkList WL;
1717     WL.push_back(errorNode);
1718     Visited[errorNode] = 1;
1719
1720     while (!WL.empty()) {
1721       WLItem &WI = WL.back();
1722       assert(!WI.N->succ_empty());
1723
1724       for (; WI.I != WI.E; ++WI.I) {
1725         const ExplodedNode *Succ = *WI.I;
1726         // End-of-path node?
1727         if (Succ->succ_empty()) {
1728           // If we found an end-of-path node that is not a sink.
1729           if (!Succ->isSink()) {
1730             bugReports.push_back(R);
1731             if (!exampleReport)
1732               exampleReport = R;
1733             WL.clear();
1734             break;
1735           }
1736           // Found a sink?  Continue on to the next successor.
1737           continue;
1738         }
1739         // Mark the successor as visited.  If it hasn't been explored,
1740         // enqueue it to the DFS worklist.
1741         unsigned &mark = Visited[Succ];
1742         if (!mark) {
1743           mark = 1;
1744           WL.push_back(Succ);
1745           break;
1746         }
1747       }
1748
1749       // The worklist may have been cleared at this point.  First
1750       // check if it is empty before checking the last item.
1751       if (!WL.empty() && &WL.back() == &WI)
1752         WL.pop_back();
1753     }
1754   }
1755
1756   // ExampleReport will be NULL if all the nodes in the equivalence class
1757   // were post-dominated by sinks.
1758   return exampleReport;
1759 }
1760
1761 //===----------------------------------------------------------------------===//
1762 // DiagnosticCache.  This is a hack to cache analyzer diagnostics.  It
1763 // uses global state, which eventually should go elsewhere.
1764 //===----------------------------------------------------------------------===//
1765 namespace {
1766 class DiagCacheItem : public llvm::FoldingSetNode {
1767   llvm::FoldingSetNodeID ID;
1768 public:
1769   DiagCacheItem(BugReport *R, PathDiagnostic *PD) {
1770     ID.AddString(R->getBugType().getName());
1771     ID.AddString(R->getBugType().getCategory());
1772     ID.AddString(R->getDescription());
1773     ID.AddInteger(R->getLocation().getRawEncoding());
1774     PD->Profile(ID);
1775   }
1776
1777   void Profile(llvm::FoldingSetNodeID &id) {
1778     id = ID;
1779   }
1780
1781   llvm::FoldingSetNodeID &getID() { return ID; }
1782 };
1783 }
1784
1785 static bool IsCachedDiagnostic(BugReport *R, PathDiagnostic *PD) {
1786   // FIXME: Eventually this diagnostic cache should reside in something
1787   // like AnalysisManager instead of being a static variable.  This is
1788   // really unsafe in the long term.
1789   typedef llvm::FoldingSet<DiagCacheItem> DiagnosticCache;
1790   static DiagnosticCache DC;
1791
1792   void *InsertPos;
1793   DiagCacheItem *Item = new DiagCacheItem(R, PD);
1794
1795   if (DC.FindNodeOrInsertPos(Item->getID(), InsertPos)) {
1796     delete Item;
1797     return true;
1798   }
1799
1800   DC.InsertNode(Item, InsertPos);
1801   return false;
1802 }
1803
1804 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
1805   llvm::SmallVector<BugReport*, 10> bugReports;
1806   BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
1807   if (!exampleReport)
1808     return;
1809
1810   PathDiagnosticClient* PD = getPathDiagnosticClient();
1811
1812   // FIXME: Make sure we use the 'R' for the path that was actually used.
1813   // Probably doesn't make a difference in practice.
1814   BugType& BT = exampleReport->getBugType();
1815
1816   llvm::OwningPtr<PathDiagnostic>
1817     D(new PathDiagnostic(exampleReport->getBugType().getName(),
1818                          !PD || PD->useVerboseDescription()
1819                          ? exampleReport->getDescription()
1820                          : exampleReport->getShortDescription(),
1821                          BT.getCategory()));
1822
1823   if (!bugReports.empty())
1824     GeneratePathDiagnostic(*D.get(), bugReports);
1825
1826   if (IsCachedDiagnostic(exampleReport, D.get()))
1827     return;
1828
1829   // Get the meta data.
1830   std::pair<const char**, const char**> Meta =
1831     exampleReport->getExtraDescriptiveText();
1832   for (const char** s = Meta.first; s != Meta.second; ++s)
1833     D->addMeta(*s);
1834
1835   // Emit a summary diagnostic to the regular Diagnostics engine.
1836   BugReport::ranges_iterator Beg, End;
1837   llvm::tie(Beg, End) = exampleReport->getRanges();
1838   Diagnostic &Diag = getDiagnostic();
1839   FullSourceLoc L(exampleReport->getLocation(), getSourceManager());
1840
1841   // Search the description for '%', as that will be interpretted as a
1842   // format character by FormatDiagnostics.
1843   llvm::StringRef desc = exampleReport->getShortDescription();
1844   unsigned ErrorDiag;
1845   {
1846     llvm::SmallString<512> TmpStr;
1847     llvm::raw_svector_ostream Out(TmpStr);
1848     for (llvm::StringRef::iterator I=desc.begin(), E=desc.end(); I!=E; ++I)
1849       if (*I == '%')
1850         Out << "%%";
1851       else
1852         Out << *I;
1853
1854     Out.flush();
1855     ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, TmpStr);
1856   }
1857
1858   {
1859     DiagnosticBuilder diagBuilder = Diag.Report(L, ErrorDiag);
1860     for (BugReport::ranges_iterator I = Beg; I != End; ++I)
1861       diagBuilder << *I;
1862   }
1863
1864   // Emit a full diagnostic for the path if we have a PathDiagnosticClient.
1865   if (!PD)
1866     return;
1867
1868   if (D->empty()) {
1869     PathDiagnosticPiece* piece =
1870       new PathDiagnosticEventPiece(L, exampleReport->getDescription());
1871
1872     for ( ; Beg != End; ++Beg) piece->addRange(*Beg);
1873     D->push_back(piece);
1874   }
1875
1876   PD->HandlePathDiagnostic(D.take());
1877 }
1878
1879 void BugReporter::EmitBasicReport(llvm::StringRef name, llvm::StringRef str,
1880                                   SourceLocation Loc,
1881                                   SourceRange* RBeg, unsigned NumRanges) {
1882   EmitBasicReport(name, "", str, Loc, RBeg, NumRanges);
1883 }
1884
1885 void BugReporter::EmitBasicReport(llvm::StringRef name,
1886                                   llvm::StringRef category,
1887                                   llvm::StringRef str, SourceLocation Loc,
1888                                   SourceRange* RBeg, unsigned NumRanges) {
1889
1890   // 'BT' will be owned by BugReporter as soon as we call 'EmitReport'.
1891   BugType *BT = new BugType(name, category);
1892   FullSourceLoc L = getContext().getFullLoc(Loc);
1893   RangedBugReport *R = new DiagBugReport(*BT, str, L);
1894   for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
1895   EmitReport(R);
1896 }