Home | History | Annotate | Download | only in Core 
      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 }
   1957