Split libAnalysis into two libraries: libAnalysis and libChecker.

(1) libAnalysis is a generic analysis library that can be used by
    Sema.  It defines the CFG, basic dataflow analysis primitives, and
    inexpensive flow-sensitive analyses (e.g. LiveVariables).

(2) libChecker contains the guts of the static analyzer, incuding the
    path-sensitive analysis engine and domain-specific checks.

Now any clients that want to use the frontend to build their own tools
don't need to link in the entire static analyzer.

This change exposes various obvious cleanups that can be made to the
layout of files and headers in libChecker.  More changes pending.  :)

This change also exposed a layering violation between AnalysisContext
and MemRegion.  BlockInvocationContext shouldn't explicitly know about
BlockDataRegions.  For now I've removed the BlockDataRegion* from
BlockInvocationContext (removing context-sensitivity; although this
wasn't used yet).  We need to have a better way to extend
BlockInvocationContext (and any LocationContext) to add
context-sensitivty.


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

1 files changed, 1879 insertions, 0 deletions

diff --git a/lib/Checker/BugReporter.cpp b/lib/Checker/BugReporter.cpp
new file mode 100644
index 0000000000..1afb8c76c0
--- /dev/null
+++ b/lib/Checker/BugReporter.cpp
@@ -0,0 +1,1879 @@
+// 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/Checker/PathSensitive/BugReporter.h"
+#include "clang/Checker/PathSensitive/GRExprEngine.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/Checker/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;
+
+BugReporterVisitor::~BugReporterVisitor() {}
+BugReporterContext::~BugReporterContext() {
+  for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I)
+    if ((*I)->isOwnedByReporterContext()) delete *I;
+}
+
+//===----------------------------------------------------------------------===//
+// Helper routines for walking the ExplodedGraph and fetching statements.
+//===----------------------------------------------------------------------===//
+
+static inline const Stmt* GetStmt(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: {
+          BinaryOperator::Opcode Op = cast<BinaryOperator>(S)->getOpcode();
+          if (Op == BinaryOperator::LAnd || Op == BinaryOperator::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->getEndNode()->getCodeDecl(); }
+
+  ParentMap& getParentMap() { return R->getEndNode()->getParentMap(); }
+
+  const Stmt *getParent(const Stmt *S) {
+    return getParentMap().getParent(S);
+  }
+
+  virtual NodeMapClosure& getNodeResolver() { return NMC; }
+  BugReport& getReport() { return *R; }
+
+  PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
+
+  PathDiagnosticLocation
+  getEnclosingStmtLocation(const PathDiagnosticLocation &L) {
+    if (const Stmt *S = L.asStmt())
+      return getEnclosingStmtLocation(S);
+
+    return L;
+  }
+
+  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)) {
+      CFGBlock* Src = BE->getSrc();
+      CFGBlock* Dst = BE->getDst();
+      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 (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 ";
+                CaseStmt* Case = cast<CaseStmt>(S);
+                Expr* LHS = Case->getLHS()->IgnoreParenCasts();
+
+                // Determine if it is an enum.
+                bool GetRawInt = true;
+
+                if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
+                  // FIXME: Maybe this should be an assertion.  Are there cases
+                  // were it is not an EnumConstantDecl?
+                  EnumConstantDecl* D =
+                  dyn_cast<EnumConstantDecl>(DR->getDecl());
+
+                  if (D) {
+                    GetRawInt = false;
+                    os << D->getNameAsString();
+                  }
+                }
+
+                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;
+
+          BinaryOperator *B = cast<BinaryOperator>(T);
+          std::string sbuf;
+          llvm::raw_string_ostream os(sbuf);
+          os << "Left side of '";
+
+          if (B->getOpcode() == BinaryOperator::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() == BinaryOperator::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();
+  }
+
+  PathDiagnosticLocation IgnoreParens(const PathDiagnosticLocation &L);
+
+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 =
+          PDB.getCodeDecl().getCompoundBody())
+      if (!CS->body_empty()) {
+        SourceLocation Loc = (*CS->body_begin())->getLocStart();
+        rawAddEdge(PathDiagnosticLocation(Loc, PDB.getSourceManager()));
+      }
+
+  }
+
+  void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
+
+  void addEdge(const Stmt *S, bool alwaysAdd = false) {
+    addEdge(PathDiagnosticLocation(S, PDB.getSourceManager()), alwaysAdd);
+  }
+
+  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)));
+}
+
+PathDiagnosticLocation
+EdgeBuilder::IgnoreParens(const PathDiagnosticLocation &L) {
+  if (const Expr* E = dyn_cast_or_null<Expr>(L.asStmt()))
+      return PathDiagnosticLocation(E->IgnoreParenCasts(),
+                                    PDB.getSourceManager());
+  return L;
+}
+
+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 PathDiagnosticLoc