[analyzer] Move the files in lib/StaticAnalyzer to lib/StaticAnalyzer/Core.

Eventually there will also be a lib/StaticAnalyzer/Frontend that will handle initialization and checker registration.
Yet another library to avoid cyclic dependencies between Core and Checkers.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125124 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1892 insertions, 0 deletions

diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp
new file mode 100644
index 0000000000..8edbe14878
--- /dev/null
+++ b/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -0,0 +1,1892 @@
+// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines BugReporter, a utility class for generating
+//  PathDiagnostics.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/AST/StmtObjC.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Analysis/ProgramPoint.h"
+#include "clang/StaticAnalyzer/BugReporter/PathDiagnostic.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/OwningPtr.h"
+#include <queue>
+
+using namespace clang;
+using namespace ento;
+
+BugReporterVisitor::~BugReporterVisitor() {}
+BugReporterContext::~BugReporterContext() {
+  for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I)
+    if ((*I)->isOwnedByReporterContext()) delete *I;
+}
+
+void BugReporterContext::addVisitor(BugReporterVisitor* visitor) {
+  if (!visitor)
+    return;
+
+  llvm::FoldingSetNodeID ID;
+  visitor->Profile(ID);
+  void *InsertPos;
+
+  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
+    delete visitor;
+    return;
+  }
+
+  CallbacksSet.InsertNode(visitor, InsertPos);
+  Callbacks = F.add(visitor, Callbacks);
+}
+
+//===----------------------------------------------------------------------===//
+// Helper routines for walking the ExplodedGraph and fetching statements.
+//===----------------------------------------------------------------------===//
+
+static inline const Stmt* GetStmt(const ProgramPoint &P) {
+  if (const StmtPoint* SP = dyn_cast<StmtPoint>(&P))
+    return SP->getStmt();
+  else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P))
+    return BE->getSrc()->getTerminator();
+
+  return 0;
+}
+
+static inline const ExplodedNode*
+GetPredecessorNode(const ExplodedNode* N) {
+  return N->pred_empty() ? NULL : *(N->pred_begin());
+}
+
+static inline const ExplodedNode*
+GetSuccessorNode(const ExplodedNode* N) {
+  return N->succ_empty() ? NULL : *(N->succ_begin());
+}
+
+static const Stmt* GetPreviousStmt(const ExplodedNode* N) {
+  for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
+    if (const Stmt *S = GetStmt(N->getLocation()))
+      return S;
+
+  return 0;
+}
+
+static const Stmt* GetNextStmt(const ExplodedNode* N) {
+  for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
+    if (const Stmt *S = GetStmt(N->getLocation())) {
+      // Check if the statement is '?' or '&&'/'||'.  These are "merges",
+      // not actual statement points.
+      switch (S->getStmtClass()) {
+        case Stmt::ChooseExprClass:
+        case Stmt::ConditionalOperatorClass: continue;
+        case Stmt::BinaryOperatorClass: {
+          BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
+          if (Op == BO_LAnd || Op == BO_LOr)
+            continue;
+          break;
+        }
+        default:
+          break;
+      }
+
+      // Some expressions don't have locations.
+      if (S->getLocStart().isInvalid())
+        continue;
+
+      return S;
+    }
+
+  return 0;
+}
+
+static inline const Stmt*
+GetCurrentOrPreviousStmt(const ExplodedNode* N) {
+  if (const Stmt *S = GetStmt(N->getLocation()))
+    return S;
+
+  return GetPreviousStmt(N);
+}
+
+static inline const Stmt*
+GetCurrentOrNextStmt(const ExplodedNode* N) {
+  if (const Stmt *S = GetStmt(N->getLocation()))
+    return S;
+
+  return GetNextStmt(N);
+}
+
+//===----------------------------------------------------------------------===//
+// PathDiagnosticBuilder and its associated routines and helper objects.
+//===----------------------------------------------------------------------===//
+
+typedef llvm::DenseMap<const ExplodedNode*,
+const ExplodedNode*> NodeBackMap;
+
+namespace {
+class NodeMapClosure : public BugReport::NodeResolver {
+  NodeBackMap& M;
+public:
+  NodeMapClosure(NodeBackMap *m) : M(*m) {}
+  ~NodeMapClosure() {}
+
+  const ExplodedNode* getOriginalNode(const ExplodedNode* N) {
+    NodeBackMap::iterator I = M.find(N);
+    return I == M.end() ? 0 : I->second;
+  }
+};
+
+class PathDiagnosticBuilder : public BugReporterContext {
+  BugReport *R;
+  PathDiagnosticClient *PDC;
+  llvm::OwningPtr<ParentMap> PM;
+  NodeMapClosure NMC;
+public:
+  PathDiagnosticBuilder(GRBugReporter &br,
+                        BugReport *r, NodeBackMap *Backmap,
+                        PathDiagnosticClient *pdc)
+    : BugReporterContext(br),
+      R(r), PDC(pdc), NMC(Backmap) {
+    addVisitor(R);
+  }
+
+  PathDiagnosticLocation ExecutionContinues(const ExplodedNode* N);
+
+  PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream& os,
+                                            const ExplodedNode* N);
+
+  Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
+
+  ParentMap& getParentMap() { return R->getErrorNode()->getParentMap(); }
+
+  const Stmt *getParent(const Stmt *S) {
+    return getParentMap().getParent(S);
+  }
+
+  virtual NodeMapClosure& getNodeResolver() { return NMC; }
+
+  PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
+
+  PathDiagnosticClient::PathGenerationScheme getGenerationScheme() const {
+    return PDC ? PDC->getGenerationScheme() : PathDiagnosticClient::Extensive;
+  }
+
+  bool supportsLogicalOpControlFlow() const {
+    return PDC ? PDC->supportsLogicalOpControlFlow() : true;
+  }
+};
+} // end anonymous namespace
+
+PathDiagnosticLocation
+PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode* N) {
+  if (const Stmt *S = GetNextStmt(N))
+    return PathDiagnosticLocation(S, getSourceManager());
+
+  return FullSourceLoc(N->getLocationContext()->getDecl()->getBodyRBrace(),
+                       getSourceManager());
+}
+
+PathDiagnosticLocation
+PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream& os,
+                                          const ExplodedNode* N) {
+
+  // Slow, but probably doesn't matter.
+  if (os.str().empty())
+    os << ' ';
+
+  const PathDiagnosticLocation &Loc = ExecutionContinues(N);
+
+  if (Loc.asStmt())
+    os << "Execution continues on line "
+       << getSourceManager().getInstantiationLineNumber(Loc.asLocation())
+       << '.';
+  else {
+    os << "Execution jumps to the end of the ";
+    const Decl *D = N->getLocationContext()->getDecl();
+    if (isa<ObjCMethodDecl>(D))
+      os << "method";
+    else if (isa<FunctionDecl>(D))
+      os << "function";
+    else {
+      assert(isa<BlockDecl>(D));
+      os << "anonymous block";
+    }
+    os << '.';
+  }
+
+  return Loc;
+}
+
+static bool IsNested(const Stmt *S, ParentMap &PM) {
+  if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
+    return true;
+
+  const Stmt *Parent = PM.getParentIgnoreParens(S);
+
+  if (Parent)
+    switch (Parent->getStmtClass()) {
+      case Stmt::ForStmtClass:
+      case Stmt::DoStmtClass:
+      case Stmt::WhileStmtClass:
+        return true;
+      default:
+        break;
+    }
+
+  return false;
+}
+
+PathDiagnosticLocation
+PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
+  assert(S && "Null Stmt* passed to getEnclosingStmtLocation");
+  ParentMap &P = getParentMap();
+  SourceManager &SMgr = getSourceManager();
+
+  while (IsNested(S, P)) {
+    const Stmt *Parent = P.getParentIgnoreParens(S);
+
+    if (!Parent)
+      break;
+
+    switch (Parent->getStmtClass()) {
+      case Stmt::BinaryOperatorClass: {
+        const BinaryOperator *B = cast<BinaryOperator>(Parent);
+        if (B->isLogicalOp())
+          return PathDiagnosticLocation(S, SMgr);
+        break;
+      }
+      case Stmt::CompoundStmtClass:
+      case Stmt::StmtExprClass:
+        return PathDiagnosticLocation(S, SMgr);
+      case Stmt::ChooseExprClass:
+        // Similar to '?' if we are referring to condition, just have the edge
+        // point to the entire choose expression.
+        if (cast<ChooseExpr>(Parent)->getCond() == S)
+          return PathDiagnosticLocation(Parent, SMgr);
+        else
+          return PathDiagnosticLocation(S, SMgr);
+      case Stmt::ConditionalOperatorClass:
+        // For '?', if we are referring to condition, just have the edge point
+        // to the entire '?' expression.
+        if (cast<ConditionalOperator>(Parent)->getCond() == S)
+          return PathDiagnosticLocation(Parent, SMgr);
+        else
+          return PathDiagnosticLocation(S, SMgr);
+      case Stmt::DoStmtClass:
+          return PathDiagnosticLocation(S, SMgr);
+      case Stmt::ForStmtClass:
+        if (cast<ForStmt>(Parent)->getBody() == S)
+          return PathDiagnosticLocation(S, SMgr);
+        break;
+      case Stmt::IfStmtClass:
+        if (cast<IfStmt>(Parent)->getCond() != S)
+          return PathDiagnosticLocation(S, SMgr);
+        break;
+      case Stmt::ObjCForCollectionStmtClass:
+        if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
+          return PathDiagnosticLocation(S, SMgr);
+        break;
+      case Stmt::WhileStmtClass:
+        if (cast<WhileStmt>(Parent)->getCond() != S)
+          return PathDiagnosticLocation(S, SMgr);
+        break;
+      default:
+        break;
+    }
+
+    S = Parent;
+  }
+
+  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
+
+  // Special case: DeclStmts can appear in for statement declarations, in which
+  //  case the ForStmt is the context.
+  if (isa<DeclStmt>(S)) {
+    if (const Stmt *Parent = P.getParent(S)) {
+      switch (Parent->getStmtClass()) {
+        case Stmt::ForStmtClass:
+        case Stmt::ObjCForCollectionStmtClass:
+          return PathDiagnosticLocation(Parent, SMgr);
+        default:
+          break;
+      }
+    }
+  }
+  else if (isa<BinaryOperator>(S)) {
+    // Special case: the binary operator represents the initialization
+    // code in a for statement (this can happen when the variable being
+    // initialized is an old variable.
+    if (const ForStmt *FS =
+          dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
+      if (FS->getInit() == S)
+        return PathDiagnosticLocation(FS, SMgr);
+    }
+  }
+
+  return PathDiagnosticLocation(S, SMgr);
+}
+
+//===----------------------------------------------------------------------===//
+// ScanNotableSymbols: closure-like callback for scanning Store bindings.
+//===----------------------------------------------------------------------===//
+
+static const VarDecl*
+GetMostRecentVarDeclBinding(const ExplodedNode* N,
+                            GRStateManager& VMgr, SVal X) {
+
+  for ( ; N ; N = N->pred_empty() ? 0 : *N->pred_begin()) {
+
+    ProgramPoint P = N->getLocation();
+
+    if (!isa<PostStmt>(P))
+      continue;
+
+    const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(cast<PostStmt>(P).getStmt());
+
+    if (!DR)
+      continue;
+
+    SVal Y = N->getState()->getSVal(DR);
+
+    if (X != Y)
+      continue;
+
+    const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl());
+
+    if (!VD)
+      continue;
+
+    return VD;
+  }
+
+  return 0;
+}
+
+namespace {
+class NotableSymbolHandler
+: public StoreManager::BindingsHandler {
+
+  SymbolRef Sym;
+  const GRState* PrevSt;
+  const Stmt* S;
+  GRStateManager& VMgr;
+  const ExplodedNode* Pred;
+  PathDiagnostic& PD;
+  BugReporter& BR;
+
+public:
+
+  NotableSymbolHandler(SymbolRef sym, const GRState* prevst, const Stmt* s,
+                       GRStateManager& vmgr, const ExplodedNode* pred,
+                       PathDiagnostic& pd, BugReporter& br)
+  : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
+
+  bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
+                     SVal V) {
+
+    SymbolRef ScanSym = V.getAsSymbol();
+
+    if (ScanSym != Sym)
+      return true;
+
+    // Check if the previous state has this binding.
+    SVal X = PrevSt->getSVal(loc::MemRegionVal(R));
+
+    if (X == V) // Same binding?
+      return true;
+
+    // Different binding.  Only handle assignments for now.  We don't pull
+    // this check out of the loop because we will eventually handle other
+    // cases.
+
+    VarDecl *VD = 0;
+
+    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+      if (!B->isAssignmentOp())
+        return true;
+
+      // What variable did we assign to?
+      DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
+
+      if (!DR)
+        return true;
+
+      VD = dyn_cast<VarDecl>(DR->getDecl());
+    }
+    else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
+      // FIXME: Eventually CFGs won't have DeclStmts.  Right now we
+      //  assume that each DeclStmt has a single Decl.  This invariant
+      //  holds by contruction in the CFG.
+      VD = dyn_cast<VarDecl>(*DS->decl_begin());
+    }
+
+    if (!VD)
+      return true;
+
+    // What is the most recently referenced variable with this binding?
+    const VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
+
+    if (!MostRecent)
+      return true;
+
+    // Create the diagnostic.
+    FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
+
+    if (Loc::IsLocType(VD->getType())) {
+      std::string msg = "'" + std::string(VD->getNameAsString()) +
+      "' now aliases '" + MostRecent->getNameAsString() + "'";
+
+      PD.push_front(new PathDiagnosticEventPiece(L, msg));
+    }
+
+    return true;
+  }
+};
+}
+
+static void HandleNotableSymbol(const ExplodedNode* N,
+                                const Stmt* S,
+                                SymbolRef Sym, BugReporter& BR,
+                                PathDiagnostic& PD) {
+
+  const ExplodedNode* Pred = N->pred_empty() ? 0 : *N->pred_begin();
+  const GRState* PrevSt = Pred ? Pred->getState() : 0;
+
+  if (!PrevSt)
+    return;
+
+  // Look at the region bindings of the current state that map to the
+  // specified symbol.  Are any of them not in the previous state?
+  GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
+  NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
+  cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
+}
+
+namespace {
+class ScanNotableSymbols
+: public StoreManager::BindingsHandler {
+
+  llvm::SmallSet<SymbolRef, 10> AlreadyProcessed;
+  const ExplodedNode* N;
+  const Stmt* S;
+  GRBugReporter& BR;
+  PathDiagnostic& PD;
+
+public:
+  ScanNotableSymbols(const ExplodedNode* n, const Stmt* s,
+                     GRBugReporter& br, PathDiagnostic& pd)
+  : N(n), S(s), BR(br), PD(pd) {}
+
+  bool HandleBinding(StoreManager& SMgr, Store store,
+                     const MemRegion* R, SVal V) {
+
+    SymbolRef ScanSym = V.getAsSymbol();
+
+    if (!ScanSym)
+      return true;
+
+    if (!BR.isNotable(ScanSym))
+      return true;
+
+    if (AlreadyProcessed.count(ScanSym))
+      return true;
+
+    AlreadyProcessed.insert(ScanSym);
+
+    HandleNotableSymbol(N, S, ScanSym, BR, PD);
+    return true;
+  }
+};
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// "Minimal" path diagnostic generation algorithm.
+//===----------------------------------------------------------------------===//
+
+static void CompactPathDiagnostic(PathDiagnostic &PD, const SourceManager& SM);
+
+static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
+                                          PathDiagnosticBuilder &PDB,
+                                          const ExplodedNode *N) {
+
+  SourceManager& SMgr = PDB.getSourceManager();
+  const ExplodedNode* NextNode = N->pred_empty()
+                                        ? NULL : *(N->pred_begin());
+  while (NextNode) {
+    N = NextNode;
+    NextNode = GetPredecessorNode(N);
+
+    ProgramPoint P = N->getLocation();
+
+    if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
+      const CFGBlock* Src = BE->getSrc();
+      const CFGBlock* Dst = BE->getDst();
+      const Stmt* T = Src->getTerminator();
+
+      if (!T)
+        continue;
+
+      FullSourceLoc Start(T->getLocStart(), SMgr);
+
+      switch (T->getStmtClass()) {
+        default:
+          break;
+
+        case Stmt::GotoStmtClass:
+        case Stmt::IndirectGotoStmtClass: {
+          const Stmt* S = GetNextStmt(N);
+
+          if (!S)
+            continue;
+
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+          const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
+
+          os << "Control jumps to line "
+          << End.asLocation().getInstantiationLineNumber();
+          PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                           os.str()));
+          break;
+        }
+
+        case Stmt::SwitchStmtClass: {
+          // Figure out what case arm we took.
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+
+          if (const Stmt* S = Dst->getLabel()) {
+            PathDiagnosticLocation End(S, SMgr);
+
+            switch (S->getStmtClass()) {
+              default:
+                os << "No cases match in the switch statement. "
+                "Control jumps to line "
+                << End.asLocation().getInstantiationLineNumber();
+                break;
+              case Stmt::DefaultStmtClass:
+                os << "Control jumps to the 'default' case at line "
+                << End.asLocation().getInstantiationLineNumber();
+                break;
+
+              case Stmt::CaseStmtClass: {
+                os << "Control jumps to 'case ";
+                const CaseStmt* Case = cast<CaseStmt>(S);
+                const Expr* LHS = Case->getLHS()->IgnoreParenCasts();
+
+                // Determine if it is an enum.
+                bool GetRawInt = true;
+
+                if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
+                  // FIXME: Maybe this should be an assertion.  Are there cases
+                  // were it is not an EnumConstantDecl?
+                  const EnumConstantDecl* D =
+                    dyn_cast<EnumConstantDecl>(DR->getDecl());
+
+                  if (D) {
+                    GetRawInt = false;
+                    os << D;
+                  }
+                }
+
+                if (GetRawInt)
+                  os << LHS->EvaluateAsInt(PDB.getASTContext());
+
+                os << ":'  at line "
+                << End.asLocation().getInstantiationLineNumber();
+                break;
+              }
+            }
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                             os.str()));
+          }
+          else {
+            os << "'Default' branch taken. ";
+            const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                             os.str()));
+          }
+
+          break;
+        }
+
+        case Stmt::BreakStmtClass:
+        case Stmt::ContinueStmtClass: {
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+          PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
+          PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                           os.str()));
+          break;
+        }
+
+          // Determine control-flow for ternary '?'.
+        case Stmt::ConditionalOperatorClass: {
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+          os << "'?' condition is ";
+
+          if (*(Src->succ_begin()+1) == Dst)
+            os << "false";
+          else
+            os << "true";
+
+          PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+
+          if (const Stmt *S = End.asStmt())
+            End = PDB.getEnclosingStmtLocation(S);
+
+          PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                           os.str()));
+          break;
+        }
+
+          // Determine control-flow for short-circuited '&&' and '||'.
+        case Stmt::BinaryOperatorClass: {
+          if (!PDB.supportsLogicalOpControlFlow())
+            break;
+
+          const BinaryOperator *B = cast<BinaryOperator>(T);
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+          os << "Left side of '";
+
+          if (B->getOpcode() == BO_LAnd) {
+            os << "&&" << "' is ";
+
+            if (*(Src->succ_begin()+1) == Dst) {
+              os << "false";
+              PathDiagnosticLocation End(B->getLHS(), SMgr);
+              PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
+              PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                               os.str()));
+            }
+            else {
+              os << "true";
+              PathDiagnosticLocation Start(B->getLHS(), SMgr);
+              PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+              PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                               os.str()));
+            }
+          }
+          else {
+            assert(B->getOpcode() == BO_LOr);
+            os << "||" << "' is ";
+
+            if (*(Src->succ_begin()+1) == Dst) {
+              os << "false";
+              PathDiagnosticLocation Start(B->getLHS(), SMgr);
+              PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+              PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                               os.str()));
+            }
+            else {
+              os << "true";
+              PathDiagnosticLocation End(B->getLHS(), SMgr);
+              PathDiagnosticLocation Start(B->getOperatorLoc(), SMgr);
+              PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                               os.str()));
+            }
+          }
+
+          break;
+        }
+
+        case Stmt::DoStmtClass:  {
+          if (*(Src->succ_begin()) == Dst) {
+            std::string sbuf;
+            llvm::raw_string_ostream os(sbuf);
+
+            os << "Loop condition is true. ";
+            PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
+
+            if (const Stmt *S = End.asStmt())
+              End = PDB.getEnclosingStmtLocation(S);
+
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                             os.str()));
+          }
+          else {
+            PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+
+            if (const Stmt *S = End.asStmt())
+              End = PDB.getEnclosingStmtLocation(S);
+
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                              "Loop condition is false.  Exiting loop"));
+          }
+
+          break;
+        }
+
+        case Stmt::WhileStmtClass:
+        case Stmt::ForStmtClass: {
+          if (*(Src->succ_begin()+1) == Dst) {
+            std::string sbuf;
+            llvm::raw_string_ostream os(sbuf);
+
+            os << "Loop condition is false. ";
+            PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
+            if (const Stmt *S = End.asStmt())
+              End = PDB.getEnclosingStmtLocation(S);
+
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                             os.str()));
+          }
+          else {
+            PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+            if (const Stmt *S = End.asStmt())
+              End = PDB.getEnclosingStmtLocation(S);
+
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                            "Loop condition is true.  Entering loop body"));
+          }
+
+          break;
+        }
+
+        case Stmt::IfStmtClass: {
+          PathDiagnosticLocation End = PDB.ExecutionContinues(N);
+
+          if (const Stmt *S = End.asStmt())
+            End = PDB.getEnclosingStmtLocation(S);
+
+          if (*(Src->succ_begin()+1) == Dst)
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                        "Taking false branch"));
+          else
+            PD.push_front(new PathDiagnosticControlFlowPiece(Start, End,
+                                                         "Taking true branch"));
+
+          break;
+        }
+      }
+    }
+
+    if (NextNode) {
+      for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(),
+           E = PDB.visitor_end(); I!=E; ++I) {
+        if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB))
+          PD.push_front(p);
+      }
+    }
+
+    if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
+      // Scan the region bindings, and see if a "notable" symbol has a new
+      // lval binding.
+      ScanNotableSymbols SNS(N, PS->getStmt(), PDB.getBugReporter(), PD);
+      PDB.getStateManager().iterBindings(N->getState(), SNS);
+    }
+  }
+
+  // After constructing the full PathDiagnostic, do a pass over it to compact
+  // PathDiagnosticPieces that occur within a macro.
+  CompactPathDiagnostic(PD, PDB.getSourceManager());
+}
+
+//===----------------------------------------------------------------------===//
+// "Extensive" PathDiagnostic generation.
+//===----------------------------------------------------------------------===//
+
+static bool IsControlFlowExpr(const Stmt *S) {
+  const Expr *E = dyn_cast<Expr>(S);
+
+  if (!E)
+    return false;
+
+  E = E->IgnoreParenCasts();
+
+  if (isa<ConditionalOperator>(E))
+    return true;
+
+  if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
+    if (B->isLogicalOp())
+      return true;
+
+  return false;
+}
+
+namespace {
+class ContextLocation : public PathDiagnosticLocation {
+  bool IsDead;
+public:
+  ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
+    : PathDiagnosticLocation(L), IsDead(isdead) {}
+
+  void markDead() { IsDead = true; }
+  bool isDead() const { return IsDead; }
+};
+
+class EdgeBuilder {
+  std::vector<ContextLocation> CLocs;
+  typedef std::vector<ContextLocation>::iterator iterator;
+  PathDiagnostic &PD;
+  PathDiagnosticBuilder &PDB;
+  PathDiagnosticLocation PrevLoc;
+
+  bool IsConsumedExpr(const PathDiagnosticLocation &L);
+
+  bool containsLocation(const PathDiagnosticLocation &Container,
+                        const PathDiagnosticLocation &Containee);
+
+  PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
+
+  PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
+                                         bool firstCharOnly = false) {
+    if (const Stmt *S = L.asStmt()) {
+      const Stmt *Original = S;
+      while (1) {
+        // Adjust the location for some expressions that are best referenced
+        // by one of their subexpressions.
+        switch (S->getStmtClass()) {
+          default:
+            break;
+          case Stmt::ParenExprClass:
+            S = cast<ParenExpr>(S)->IgnoreParens();
+            firstCharOnly = true;
+            continue;
+          case Stmt::ConditionalOperatorClass:
+            S = cast<ConditionalOperator>(S)->getCond();
+            firstCharOnly = true;
+            continue;
+          case Stmt::ChooseExprClass:
+            S = cast<ChooseExpr>(S)->getCond();
+            firstCharOnly = true;
+            continue;
+          case Stmt::BinaryOperatorClass:
+            S = cast<BinaryOperator>(S)->getLHS();
+            firstCharOnly = true;
+            continue;
+        }
+
+        break;
+      }
+
+      if (S != Original)
+        L = PathDiagnosticLocation(S, L.getManager());
+    }
+
+    if (firstCharOnly)
+      L = PathDiagnosticLocation(L.asLocation());
+
+    return L;
+  }
+
+  void popLocation() {
+    if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
+      // For contexts, we only one the first character as the range.
+      rawAddEdge(cleanUpLocation(CLocs.back(), true));
+    }
+    CLocs.pop_back();
+  }
+
+public:
+  EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
+    : PD(pd), PDB(pdb) {
+
+      // If the PathDiagnostic already has pieces, add the enclosing statement
+      // of the first piece as a context as well.
+      if (!PD.empty()) {
+        PrevLoc = PD.begin()->getLocation();
+
+        if (const Stmt *S = PrevLoc.asStmt())
+          addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
+      }
+  }
+
+  ~EdgeBuilder() {
+    while (!CLocs.empty()) popLocation();
+
+    // Finally, add an initial edge from the start location of the first
+    // statement (if it doesn't already exist).
+    // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
+    if (const CompoundStmt *CS =
+          dyn_cast_or_null<CompoundStmt>(PDB.getCodeDecl().getBody()))
+      if (!CS->body_empty()) {
+        SourceLocation Loc = (*CS->body_begin())->getLocStart();
+        rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager()));
+      }
+
+  }
+
+  void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
+
+  void rawAddEdge(PathDiagnosticLocation NewLoc);
+
+  void addContext(const Stmt *S);
+  void addExtendedContext(const Stmt *S);
+};
+} // end anonymous namespace
+
+
+PathDiagnosticLocation
+EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
+  if (const Stmt *S = L.asStmt()) {
+    if (IsControlFlowExpr(S))
+      return L;
+
+    return PDB.getEnclosingStmtLocation(S);
+  }
+
+  return L;
+}
+
+bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
+                                   const PathDiagnosticLocation &Containee) {
+
+  if (Container == Containee)
+    return true;
+
+  if (Container.asDecl())
+    return true;
+
+  if (const Stmt *S = Containee.asStmt())
+    if (const Stmt *ContainerS = Container.asStmt()) {
+      while (S) {
+        if (S == ContainerS)
+          return true;
+        S = PDB.getParent(S);
+      }
+      return false;
+    }
+
+  // Less accurate: compare using source ranges.
+  SourceRange ContainerR = Container.asRange();
+  SourceRange ContaineeR = Containee.asRange();
+
+  SourceManager &SM = PDB.getSourceManager();
+  SourceLocation ContainerRBeg = SM.getInstantiationLoc(ContainerR.getBegin());
+  SourceLocation ContainerREnd = SM.getInstantiationLoc(ContainerR.getEnd());
+  SourceLocation ContaineeRBeg = SM.getInstantiationLoc(ContaineeR.getBegin());
+  SourceLocation ContaineeREnd = SM.getInstantiationLoc(ContaineeR.getEnd());
+
+  unsigned ContainerBegLine = SM.getInstantiationLineNumber(ContainerRBeg);
+  unsigned ContainerEndLine = SM.getInstantiationLineNumber(ContainerREnd);
+  unsigned ContaineeBegLine = SM.getInstantiationLineNumber(ContaineeRBeg);
+  unsigned ContaineeEndLine = SM.getInstantiationLineNumber(ContaineeREnd);
+
+  assert(ContainerBegLine <= ContainerEndLine);
+  assert(ContaineeBegLine <= ContaineeEndLine);
+
+  return (ContainerBegLine <= ContaineeBegLine &&
+          ContainerEndLine >= ContaineeEndLine &&
+          (ContainerBegLine != ContaineeBegLine ||
+           SM.getInstantiationColumnNumber(ContainerRBeg) <=
+           SM.getInstantiationColumnNumber(ContaineeRBeg)) &&
+          (ContainerEndLine != ContaineeEndLine ||
+           SM.getInstantiationColumnNumber(ContainerREnd) >=
+           SM.getInstantiationColumnNumber(ContainerREnd)));
+}
+
+void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
+  if (!PrevLoc.isValid()) {
+    PrevLoc = NewLoc;
+    return;
+  }
+
+  const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
+  const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
+
+  if (NewLocClean.asLocation() == PrevLocClean.asLocation())
+    return;
+
+  // FIXME: Ignore intra-macro edges for now.
+  if (NewLocClean.asLocation().getInstantiationLoc() ==
+      PrevLocClean.asLocation().getInstantiationLoc())
+    return;
+
+  PD.push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
+  PrevLoc = NewLoc;
+}
+
+void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
+
+  if (!alwaysAdd && NewLoc.asLocation().isMacroID())
+    return;
+
+  const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
+
+  while (!CLocs.empty()) {
+    ContextLocation &TopContextLoc = CLocs.back();
+
+    // Is the top location context the same as the one for the new location?
+    if (TopContextLoc == CLoc) {
+      if (alwaysAdd) {
+        if (IsConsumedExpr(TopContextLoc) &&
+            !IsControlFlowExpr(TopContextLoc.asStmt()))
+            TopContextLoc.markDead();
+
+        rawAddEdge(NewLoc);
+      }
+
+      return;
+    }
+
+    if (containsLocation(TopContextLoc, CLoc)) {
+      if (alwaysAdd) {
+        rawAddEdge(NewLoc);
+