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