contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/BugReporter.cpp

   1 // BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines BugReporter, a utility class for generating
  11 //  PathDiagnostics.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "BugReporter"
  16
  17 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/ExprCXX.h"
  22 #include "clang/AST/ParentMap.h"
  23 #include "clang/AST/StmtObjC.h"
  24 #include "clang/AST/StmtCXX.h"
  25 #include "clang/Analysis/CFG.h"
  26 #include "clang/Analysis/ProgramPoint.h"
  27 #include "clang/Basic/SourceManager.h"
  28 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  29 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  30 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  31 #include "llvm/ADT/DenseMap.h"
  32 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  33 #include "llvm/ADT/OwningPtr.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include "llvm/ADT/SmallString.h"
  36 #include "llvm/ADT/Statistic.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include <queue>
  39
  40 using namespace clang;
  41 using namespace ento;
  42
  43 STATISTIC(MaxBugClassSize,
  44           "The maximum number of bug reports in the same equivalence class");
  45 STATISTIC(MaxValidBugClassSize,
  46           "The maximum number of bug reports in the same equivalence class "
  47           "where at least one report is valid (not suppressed)");
  48
  49 BugReporterVisitor::~BugReporterVisitor() {}
  50
  51 void BugReporterContext::anchor() {}
  52
  53 //===----------------------------------------------------------------------===//
  54 // Helper routines for walking the ExplodedGraph and fetching statements.
  55 //===----------------------------------------------------------------------===//
  56
  57 static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
  58   for (N = N->getFirstPred(); N; N = N->getFirstPred())
  59     if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
  60       return S;
  61
  62   return 0;
  63 }
  64
  65 static inline const Stmt*
  66 GetCurrentOrPreviousStmt(const ExplodedNode *N) {
  67   if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
  68     return S;
  69
  70   return GetPreviousStmt(N);
  71 }
  72
  73 //===----------------------------------------------------------------------===//
  74 // Diagnostic cleanup.
  75 //===----------------------------------------------------------------------===//
  76
  77 static PathDiagnosticEventPiece *
  78 eventsDescribeSameCondition(PathDiagnosticEventPiece *X,
  79                             PathDiagnosticEventPiece *Y) {
  80   // Prefer diagnostics that come from ConditionBRVisitor over
  81   // those that came from TrackConstraintBRVisitor.
  82   const void *tagPreferred = ConditionBRVisitor::getTag();
  83   const void *tagLesser = TrackConstraintBRVisitor::getTag();
  84
  85   if (X->getLocation() != Y->getLocation())
  86     return 0;
  87
  88   if (X->getTag() == tagPreferred && Y->getTag() == tagLesser)
  89     return X;
  90
  91   if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)
  92     return Y;
  93
  94   return 0;
  95 }
  96
  97 /// An optimization pass over PathPieces that removes redundant diagnostics
  98 /// generated by both ConditionBRVisitor and TrackConstraintBRVisitor.  Both
  99 /// BugReporterVisitors use different methods to generate diagnostics, with
 100 /// one capable of emitting diagnostics in some cases but not in others.  This
 101 /// can lead to redundant diagnostic pieces at the same point in a path.
 102 static void removeRedundantMsgs(PathPieces &path) {
 103   unsigned N = path.size();
 104   if (N < 2)
 105     return;
 106   // NOTE: this loop intentionally is not using an iterator.  Instead, we
 107   // are streaming the path and modifying it in place.  This is done by
 108   // grabbing the front, processing it, and if we decide to keep it append
 109   // it to the end of the path.  The entire path is processed in this way.
 110   for (unsigned i = 0; i < N; ++i) {
 111     IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front());
 112     path.pop_front();
 113
 114     switch (piece->getKind()) {
 115       case clang::ento::PathDiagnosticPiece::Call:
 116         removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path);
 117         break;
 118       case clang::ento::PathDiagnosticPiece::Macro:
 119         removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces);
 120         break;
 121       case clang::ento::PathDiagnosticPiece::ControlFlow:
 122         break;
 123       case clang::ento::PathDiagnosticPiece::Event: {
 124         if (i == N-1)
 125           break;
 126
 127         if (PathDiagnosticEventPiece *nextEvent =
 128             dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) {
 129           PathDiagnosticEventPiece *event =
 130             cast<PathDiagnosticEventPiece>(piece);
 131           // Check to see if we should keep one of the two pieces.  If we
 132           // come up with a preference, record which piece to keep, and consume
 133           // another piece from the path.
 134           if (PathDiagnosticEventPiece *pieceToKeep =
 135               eventsDescribeSameCondition(event, nextEvent)) {
 136             piece = pieceToKeep;
 137             path.pop_front();
 138             ++i;
 139           }
 140         }
 141         break;
 142       }
 143     }
 144     path.push_back(piece);
 145   }
 146 }
 147
 148 /// A map from PathDiagnosticPiece to the LocationContext of the inlined
 149 /// function call it represents.
 150 typedef llvm::DenseMap<const PathPieces *, const LocationContext *>
 151         LocationContextMap;
 152
 153 /// Recursively scan through a path and prune out calls and macros pieces
 154 /// that aren't needed.  Return true if afterwards the path contains
 155 /// "interesting stuff" which means it shouldn't be pruned from the parent path.
 156 static bool removeUnneededCalls(PathPieces &pieces, BugReport *R,
 157                                 LocationContextMap &LCM) {
 158   bool containsSomethingInteresting = false;
 159   const unsigned N = pieces.size();
 160
 161   for (unsigned i = 0 ; i < N ; ++i) {
 162     // Remove the front piece from the path.  If it is still something we
 163     // want to keep once we are done, we will push it back on the end.
 164     IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front());
 165     pieces.pop_front();
 166
 167     switch (piece->getKind()) {
 168       case PathDiagnosticPiece::Call: {
 169         PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece);
 170         // Check if the location context is interesting.
 171         assert(LCM.count(&call->path));
 172         if (R->isInteresting(LCM[&call->path])) {
 173           containsSomethingInteresting = true;
 174           break;
 175         }
 176
 177         if (!removeUnneededCalls(call->path, R, LCM))
 178           continue;
 179
 180         containsSomethingInteresting = true;
 181         break;
 182       }
 183       case PathDiagnosticPiece::Macro: {
 184         PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece);
 185         if (!removeUnneededCalls(macro->subPieces, R, LCM))
 186           continue;
 187         containsSomethingInteresting = true;
 188         break;
 189       }
 190       case PathDiagnosticPiece::Event: {
 191         PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece);
 192
 193         // We never throw away an event, but we do throw it away wholesale
 194         // as part of a path if we throw the entire path away.
 195         containsSomethingInteresting |= !event->isPrunable();
 196         break;
 197       }
 198       case PathDiagnosticPiece::ControlFlow:
 199         break;
 200     }
 201
 202     pieces.push_back(piece);
 203   }
 204
 205   return containsSomethingInteresting;
 206 }
 207
 208 /// Returns true if the given decl has been implicitly given a body, either by
 209 /// the analyzer or by the compiler proper.
 210 static bool hasImplicitBody(const Decl *D) {
 211   assert(D);
 212   return D->isImplicit() || !D->hasBody();
 213 }
 214
 215 /// Recursively scan through a path and make sure that all call pieces have
 216 /// valid locations.
 217 static void adjustCallLocations(PathPieces &Pieces,
 218                                 PathDiagnosticLocation *LastCallLocation = 0) {
 219   for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) {
 220     PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I);
 221
 222     if (!Call) {
 223       assert((*I)->getLocation().asLocation().isValid());
 224       continue;
 225     }
 226
 227     if (LastCallLocation) {
 228       bool CallerIsImplicit = hasImplicitBody(Call->getCaller());
 229       if (CallerIsImplicit || !Call->callEnter.asLocation().isValid())
 230         Call->callEnter = *LastCallLocation;
 231       if (CallerIsImplicit || !Call->callReturn.asLocation().isValid())
 232         Call->callReturn = *LastCallLocation;
 233     }
 234
 235     // Recursively clean out the subclass.  Keep this call around if
 236     // it contains any informative diagnostics.
 237     PathDiagnosticLocation *ThisCallLocation;
 238     if (Call->callEnterWithin.asLocation().isValid() &&
 239         !hasImplicitBody(Call->getCallee()))
 240       ThisCallLocation = &Call->callEnterWithin;
 241     else
 242       ThisCallLocation = &Call->callEnter;
 243
 244     assert(ThisCallLocation && "Outermost call has an invalid location");
 245     adjustCallLocations(Call->path, ThisCallLocation);
 246   }
 247 }
 248
 249 /// Remove edges in and out of C++ default initializer expressions. These are
 250 /// for fields that have in-class initializers, as opposed to being initialized
 251 /// explicitly in a constructor or braced list.
 252 static void removeEdgesToDefaultInitializers(PathPieces &Pieces) {
 253   for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
 254     if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I))
 255       removeEdgesToDefaultInitializers(C->path);
 256
 257     if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I))
 258       removeEdgesToDefaultInitializers(M->subPieces);
 259
 260     if (PathDiagnosticControlFlowPiece *CF =
 261           dyn_cast<PathDiagnosticControlFlowPiece>(*I)) {
 262       const Stmt *Start = CF->getStartLocation().asStmt();
 263       const Stmt *End = CF->getEndLocation().asStmt();
 264       if (Start && isa<CXXDefaultInitExpr>(Start)) {
 265         I = Pieces.erase(I);
 266         continue;
 267       } else if (End && isa<CXXDefaultInitExpr>(End)) {
 268         PathPieces::iterator Next = llvm::next(I);
 269         if (Next != E) {
 270           if (PathDiagnosticControlFlowPiece *NextCF =
 271                 dyn_cast<PathDiagnosticControlFlowPiece>(*Next)) {
 272             NextCF->setStartLocation(CF->getStartLocation());
 273           }
 274         }
 275         I = Pieces.erase(I);
 276         continue;
 277       }
 278     }
 279
 280     I++;
 281   }
 282 }
 283
 284 /// Remove all pieces with invalid locations as these cannot be serialized.
 285 /// We might have pieces with invalid locations as a result of inlining Body
 286 /// Farm generated functions.
 287 static void removePiecesWithInvalidLocations(PathPieces &Pieces) {
 288   for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
 289     if (PathDiagnosticCallPiece *C = dyn_cast<PathDiagnosticCallPiece>(*I))
 290       removePiecesWithInvalidLocations(C->path);
 291
 292     if (PathDiagnosticMacroPiece *M = dyn_cast<PathDiagnosticMacroPiece>(*I))
 293       removePiecesWithInvalidLocations(M->subPieces);
 294
 295     if (!(*I)->getLocation().isValid() ||
 296         !(*I)->getLocation().asLocation().isValid()) {
 297       I = Pieces.erase(I);
 298       continue;
 299     }
 300     I++;
 301   }
 302 }
 303
 304 //===----------------------------------------------------------------------===//
 305 // PathDiagnosticBuilder and its associated routines and helper objects.
 306 //===----------------------------------------------------------------------===//
 307
 308 namespace {
 309 class NodeMapClosure : public BugReport::NodeResolver {
 310   InterExplodedGraphMap &M;
 311 public:
 312   NodeMapClosure(InterExplodedGraphMap &m) : M(m) {}
 313
 314   const ExplodedNode *getOriginalNode(const ExplodedNode *N) {
 315     return M.lookup(N);
 316   }
 317 };
 318
 319 class PathDiagnosticBuilder : public BugReporterContext {
 320   BugReport *R;
 321   PathDiagnosticConsumer *PDC;
 322   NodeMapClosure NMC;
 323 public:
 324   const LocationContext *LC;
 325
 326   PathDiagnosticBuilder(GRBugReporter &br,
 327                         BugReport *r, InterExplodedGraphMap &Backmap,
 328                         PathDiagnosticConsumer *pdc)
 329     : BugReporterContext(br),
 330       R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext())
 331   {}
 332
 333   PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
 334
 335   PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
 336                                             const ExplodedNode *N);
 337
 338   BugReport *getBugReport() { return R; }
 339
 340   Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
 341
 342   ParentMap& getParentMap() { return LC->getParentMap(); }
 343
 344   const Stmt *getParent(const Stmt *S) {
 345     return getParentMap().getParent(S);
 346   }
 347
 348   virtual NodeMapClosure& getNodeResolver() { return NMC; }
 349
 350   PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
 351
 352   PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
 353     return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive;
 354   }
 355
 356   bool supportsLogicalOpControlFlow() const {
 357     return PDC ? PDC->supportsLogicalOpControlFlow() : true;
 358   }
 359 };
 360 } // end anonymous namespace
 361
 362 PathDiagnosticLocation
 363 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
 364   if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N))
 365     return PathDiagnosticLocation(S, getSourceManager(), LC);
 366
 367   return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(),
 368                                                getSourceManager());
 369 }
 370
 371 PathDiagnosticLocation
 372 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
 373                                           const ExplodedNode *N) {
 374
 375   // Slow, but probably doesn't matter.
 376   if (os.str().empty())
 377     os << ' ';
 378
 379   const PathDiagnosticLocation &Loc = ExecutionContinues(N);
 380
 381   if (Loc.asStmt())
 382     os << "Execution continues on line "
 383        << getSourceManager().getExpansionLineNumber(Loc.asLocation())
 384        << '.';
 385   else {
 386     os << "Execution jumps to the end of the ";
 387     const Decl *D = N->getLocationContext()->getDecl();
 388     if (isa<ObjCMethodDecl>(D))
 389       os << "method";
 390     else if (isa<FunctionDecl>(D))
 391       os << "function";
 392     else {
 393       assert(isa<BlockDecl>(D));
 394       os << "anonymous block";
 395     }
 396     os << '.';
 397   }
 398
 399   return Loc;
 400 }
 401
 402 static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) {
 403   if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
 404     return PM.getParentIgnoreParens(S);
 405
 406   const Stmt *Parent = PM.getParentIgnoreParens(S);
 407   if (!Parent)
 408     return 0;
 409
 410   switch (Parent->getStmtClass()) {
 411   case Stmt::ForStmtClass:
 412   case Stmt::DoStmtClass:
 413   case Stmt::WhileStmtClass:
 414   case Stmt::ObjCForCollectionStmtClass:
 415   case Stmt::CXXForRangeStmtClass:
 416     return Parent;
 417   default:
 418     break;
 419   }
 420
 421   return 0;
 422 }
 423
 424 static PathDiagnosticLocation
 425 getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P,
 426                          const LocationContext *LC, bool allowNestedContexts) {
 427   if (!S)
 428     return PathDiagnosticLocation();
 429
 430   while (const Stmt *Parent = getEnclosingParent(S, P)) {
 431     switch (Parent->getStmtClass()) {
 432       case Stmt::BinaryOperatorClass: {
 433         const BinaryOperator *B = cast<BinaryOperator>(Parent);
 434         if (B->isLogicalOp())
 435           return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC);
 436         break;
 437       }
 438       case Stmt::CompoundStmtClass:
 439       case Stmt::StmtExprClass:
 440         return PathDiagnosticLocation(S, SMgr, LC);
 441       case Stmt::ChooseExprClass:
 442         // Similar to '?' if we are referring to condition, just have the edge
 443         // point to the entire choose expression.
 444         if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S)
 445           return PathDiagnosticLocation(Parent, SMgr, LC);
 446         else
 447           return PathDiagnosticLocation(S, SMgr, LC);
 448       case Stmt::BinaryConditionalOperatorClass:
 449       case Stmt::ConditionalOperatorClass:
 450         // For '?', if we are referring to condition, just have the edge point
 451         // to the entire '?' expression.
 452         if (allowNestedContexts ||
 453             cast<AbstractConditionalOperator>(Parent)->getCond() == S)
 454           return PathDiagnosticLocation(Parent, SMgr, LC);
 455         else
 456           return PathDiagnosticLocation(S, SMgr, LC);
 457       case Stmt::CXXForRangeStmtClass:
 458         if (cast<CXXForRangeStmt>(Parent)->getBody() == S)
 459           return PathDiagnosticLocation(S, SMgr, LC);
 460         break;
 461       case Stmt::DoStmtClass:
 462           return PathDiagnosticLocation(S, SMgr, LC);
 463       case Stmt::ForStmtClass:
 464         if (cast<ForStmt>(Parent)->getBody() == S)
 465           return PathDiagnosticLocation(S, SMgr, LC);
 466         break;
 467       case Stmt::IfStmtClass:
 468         if (cast<IfStmt>(Parent)->getCond() != S)
 469           return PathDiagnosticLocation(S, SMgr, LC);
 470         break;
 471       case Stmt::ObjCForCollectionStmtClass:
 472         if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
 473           return PathDiagnosticLocation(S, SMgr, LC);
 474         break;
 475       case Stmt::WhileStmtClass:
 476         if (cast<WhileStmt>(Parent)->getCond() != S)
 477           return PathDiagnosticLocation(S, SMgr, LC);
 478         break;
 479       default:
 480         break;
 481     }
 482
 483     S = Parent;
 484   }
 485
 486   assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
 487
 488   return PathDiagnosticLocation(S, SMgr, LC);
 489 }
 490
 491 PathDiagnosticLocation
 492 PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
 493   assert(S && "Null Stmt passed to getEnclosingStmtLocation");
 494   return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC,
 495                                     /*allowNestedContexts=*/false);
 496 }
 497
 498 //===----------------------------------------------------------------------===//
 499 // "Visitors only" path diagnostic generation algorithm.
 500 //===----------------------------------------------------------------------===//
 501 static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD,
 502                                                PathDiagnosticBuilder &PDB,
 503                                                const ExplodedNode *N,
 504                                       ArrayRef<BugReporterVisitor *> visitors) {
 505   // All path generation skips the very first node (the error node).
 506   // This is because there is special handling for the end-of-path note.
 507   N = N->getFirstPred();
 508   if (!N)
 509     return true;
 510
 511   BugReport *R = PDB.getBugReport();
 512   while (const ExplodedNode *Pred = N->getFirstPred()) {
 513     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
 514                                                   E = visitors.end();
 515          I != E; ++I) {
 516       // Visit all the node pairs, but throw the path pieces away.
 517       PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R);
 518       delete Piece;
 519     }
 520
 521     N = Pred;
 522   }
 523
 524   return R->isValid();
 525 }
 526
 527 //===----------------------------------------------------------------------===//
 528 // "Minimal" path diagnostic generation algorithm.
 529 //===----------------------------------------------------------------------===//
 530 typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair;
 531 typedef SmallVector<StackDiagPair, 6> StackDiagVector;
 532
 533 static void updateStackPiecesWithMessage(PathDiagnosticPiece *P,
 534                                          StackDiagVector &CallStack) {
 535   // If the piece contains a special message, add it to all the call
 536   // pieces on the active stack.
 537   if (PathDiagnosticEventPiece *ep =
 538         dyn_cast<PathDiagnosticEventPiece>(P)) {
 539
 540     if (ep->hasCallStackHint())
 541       for (StackDiagVector::iterator I = CallStack.begin(),
 542                                      E = CallStack.end(); I != E; ++I) {
 543         PathDiagnosticCallPiece *CP = I->first;
 544         const ExplodedNode *N = I->second;
 545         std::string stackMsg = ep->getCallStackMessage(N);
 546
 547         // The last message on the path to final bug is the most important
 548         // one. Since we traverse the path backwards, do not add the message
 549         // if one has been previously added.
 550         if  (!CP->hasCallStackMessage())
 551           CP->setCallStackMessage(stackMsg);
 552       }
 553   }
 554 }
 555
 556 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
 557
 558 static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
 559                                           PathDiagnosticBuilder &PDB,
 560                                           const ExplodedNode *N,
 561                                           LocationContextMap &LCM,
 562                                       ArrayRef<BugReporterVisitor *> visitors) {
 563
 564   SourceManager& SMgr = PDB.getSourceManager();
 565   const LocationContext *LC = PDB.LC;
 566   const ExplodedNode *NextNode = N->pred_empty()
 567                                         ? NULL : *(N->pred_begin());
 568
 569   StackDiagVector CallStack;
 570
 571   while (NextNode) {
 572     N = NextNode;
 573     PDB.LC = N->getLocationContext();
 574     NextNode = N->getFirstPred();
 575
 576     ProgramPoint P = N->getLocation();
 577
 578     do {
 579       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
 580         PathDiagnosticCallPiece *C =
 581             PathDiagnosticCallPiece::construct(N, *CE, SMgr);
 582         // Record the mapping from call piece to LocationContext.
 583         LCM[&C->path] = CE->getCalleeContext();
 584         PD.getActivePath().push_front(C);
 585         PD.pushActivePath(&C->path);
 586         CallStack.push_back(StackDiagPair(C, N));
 587         break;
 588       }
 589
 590       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
 591         // Flush all locations, and pop the active path.
 592         bool VisitedEntireCall = PD.isWithinCall();
 593         PD.popActivePath();
 594
 595         // Either we just added a bunch of stuff to the top-level path, or
 596         // we have a previous CallExitEnd.  If the former, it means that the
 597         // path terminated within a function call.  We must then take the
 598         // current contents of the active path and place it within
 599         // a new PathDiagnosticCallPiece.
 600         PathDiagnosticCallPiece *C;
 601         if (VisitedEntireCall) {
 602           C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
 603         } else {
 604           const Decl *Caller = CE->getLocationContext()->getDecl();
 605           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
 606           // Record the mapping from call piece to LocationContext.
 607           LCM[&C->path] = CE->getCalleeContext();
 608         }
 609
 610         C->setCallee(*CE, SMgr);
 611         if (!CallStack.empty()) {
 612           assert(CallStack.back().first == C);
 613           CallStack.pop_back();
 614         }
 615         break;
 616       }
 617
 618       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
 619         const CFGBlock *Src = BE->getSrc();
 620         const CFGBlock *Dst = BE->getDst();
 621         const Stmt *T = Src->getTerminator();
 622
 623         if (!T)
 624           break;
 625
 626         PathDiagnosticLocation Start =
 627             PathDiagnosticLocation::createBegin(T, SMgr,
 628                 N->getLocationContext());
 629
 630         switch (T->getStmtClass()) {
 631         default:
 632           break;
 633
 634         case Stmt::GotoStmtClass:
 635         case Stmt::IndirectGotoStmtClass: {
 636           const Stmt *S = PathDiagnosticLocation::getNextStmt(N);
 637
 638           if (!S)
 639             break;
 640
 641           std::string sbuf;
 642           llvm::raw_string_ostream os(sbuf);
 643           const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
 644
 645           os << "Control jumps to line "
 646               << End.asLocation().getExpansionLineNumber();
 647           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 648               Start, End, os.str()));
 649           break;
 650         }
 651
 652         case Stmt::SwitchStmtClass: {
 653           // Figure out what case arm we took.
 654           std::string sbuf;
 655           llvm::raw_string_ostream os(sbuf);
 656
 657           if (const Stmt *S = Dst->getLabel()) {
 658             PathDiagnosticLocation End(S, SMgr, LC);
 659
 660             switch (S->getStmtClass()) {
 661             default:
 662               os << "No cases match in the switch statement. "
 663               "Control jumps to line "
 664               << End.asLocation().getExpansionLineNumber();
 665               break;
 666             case Stmt::DefaultStmtClass:
 667               os << "Control jumps to the 'default' case at line "
 668               << End.asLocation().getExpansionLineNumber();
 669               break;
 670
 671             case Stmt::CaseStmtClass: {
 672               os << "Control jumps to 'case ";
 673               const CaseStmt *Case = cast<CaseStmt>(S);
 674               const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
 675
 676               // Determine if it is an enum.
 677               bool GetRawInt = true;
 678
 679               if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
 680                 // FIXME: Maybe this should be an assertion.  Are there cases
 681                 // were it is not an EnumConstantDecl?
 682                 const EnumConstantDecl *D =
 683                     dyn_cast<EnumConstantDecl>(DR->getDecl());
 684
 685                 if (D) {
 686                   GetRawInt = false;
 687                   os << *D;
 688                 }
 689               }
 690
 691               if (GetRawInt)
 692                 os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
 693
 694               os << ":'  at line "
 695                   << End.asLocation().getExpansionLineNumber();
 696               break;
 697             }
 698             }
 699             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 700                 Start, End, os.str()));
 701           }
 702           else {
 703             os << "'Default' branch taken. ";
 704             const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
 705             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 706                 Start, End, os.str()));
 707           }
 708
 709           break;
 710         }
 711
 712         case Stmt::BreakStmtClass:
 713         case Stmt::ContinueStmtClass: {
 714           std::string sbuf;
 715           llvm::raw_string_ostream os(sbuf);
 716           PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 717           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 718               Start, End, os.str()));
 719           break;
 720         }
 721
 722         // Determine control-flow for ternary '?'.
 723         case Stmt::BinaryConditionalOperatorClass:
 724         case Stmt::ConditionalOperatorClass: {
 725           std::string sbuf;
 726           llvm::raw_string_ostream os(sbuf);
 727           os << "'?' condition is ";
 728
 729           if (*(Src->succ_begin()+1) == Dst)
 730             os << "false";
 731           else
 732             os << "true";
 733
 734           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 735
 736           if (const Stmt *S = End.asStmt())
 737             End = PDB.getEnclosingStmtLocation(S);
 738
 739           PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 740               Start, End, os.str()));
 741           break;
 742         }
 743
 744         // Determine control-flow for short-circuited '&&' and '||'.
 745         case Stmt::BinaryOperatorClass: {
 746           if (!PDB.supportsLogicalOpControlFlow())
 747             break;
 748
 749           const BinaryOperator *B = cast<BinaryOperator>(T);
 750           std::string sbuf;
 751           llvm::raw_string_ostream os(sbuf);
 752           os << "Left side of '";
 753
 754           if (B->getOpcode() == BO_LAnd) {
 755             os << "&&" << "' is ";
 756
 757             if (*(Src->succ_begin()+1) == Dst) {
 758               os << "false";
 759               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 760               PathDiagnosticLocation Start =
 761                   PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 762               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 763                   Start, End, os.str()));
 764             }
 765             else {
 766               os << "true";
 767               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 768               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 769               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 770                   Start, End, os.str()));
 771             }
 772           }
 773           else {
 774             assert(B->getOpcode() == BO_LOr);
 775             os << "||" << "' is ";
 776
 777             if (*(Src->succ_begin()+1) == Dst) {
 778               os << "false";
 779               PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
 780               PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 781               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 782                   Start, End, os.str()));
 783             }
 784             else {
 785               os << "true";
 786               PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
 787               PathDiagnosticLocation Start =
 788                   PathDiagnosticLocation::createOperatorLoc(B, SMgr);
 789               PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 790                   Start, End, os.str()));
 791             }
 792           }
 793
 794           break;
 795         }
 796
 797         case Stmt::DoStmtClass:  {
 798           if (*(Src->succ_begin()) == Dst) {
 799             std::string sbuf;
 800             llvm::raw_string_ostream os(sbuf);
 801
 802             os << "Loop condition is true. ";
 803             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 804
 805             if (const Stmt *S = End.asStmt())
 806               End = PDB.getEnclosingStmtLocation(S);
 807
 808             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 809                 Start, End, os.str()));
 810           }
 811           else {
 812             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 813
 814             if (const Stmt *S = End.asStmt())
 815               End = PDB.getEnclosingStmtLocation(S);
 816
 817             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 818                 Start, End, "Loop condition is false.  Exiting loop"));
 819           }
 820
 821           break;
 822         }
 823
 824         case Stmt::WhileStmtClass:
 825         case Stmt::ForStmtClass: {
 826           if (*(Src->succ_begin()+1) == Dst) {
 827             std::string sbuf;
 828             llvm::raw_string_ostream os(sbuf);
 829
 830             os << "Loop condition is false. ";
 831             PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
 832             if (const Stmt *S = End.asStmt())
 833               End = PDB.getEnclosingStmtLocation(S);
 834
 835             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 836                 Start, End, os.str()));
 837           }
 838           else {
 839             PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 840             if (const Stmt *S = End.asStmt())
 841               End = PDB.getEnclosingStmtLocation(S);
 842
 843             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 844                 Start, End, "Loop condition is true.  Entering loop body"));
 845           }
 846
 847           break;
 848         }
 849
 850         case Stmt::IfStmtClass: {
 851           PathDiagnosticLocation End = PDB.ExecutionContinues(N);
 852
 853           if (const Stmt *S = End.asStmt())
 854             End = PDB.getEnclosingStmtLocation(S);
 855
 856           if (*(Src->succ_begin()+1) == Dst)
 857             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 858                 Start, End, "Taking false branch"));
 859           else
 860             PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
 861                 Start, End, "Taking true branch"));
 862
 863           break;
 864         }
 865         }
 866       }
 867     } while(0);
 868
 869     if (NextNode) {
 870       // Add diagnostic pieces from custom visitors.
 871       BugReport *R = PDB.getBugReport();
 872       for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
 873                                                     E = visitors.end();
 874            I != E; ++I) {
 875         if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
 876           PD.getActivePath().push_front(p);
 877           updateStackPiecesWithMessage(p, CallStack);
 878         }
 879       }
 880     }
 881   }
 882
 883   if (!PDB.getBugReport()->isValid())
 884     return false;
 885
 886   // After constructing the full PathDiagnostic, do a pass over it to compact
 887   // PathDiagnosticPieces that occur within a macro.
 888   CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager());
 889   return true;
 890 }
 891
 892 //===----------------------------------------------------------------------===//
 893 // "Extensive" PathDiagnostic generation.
 894 //===----------------------------------------------------------------------===//
 895
 896 static bool IsControlFlowExpr(const Stmt *S) {
 897   const Expr *E = dyn_cast<Expr>(S);
 898
 899   if (!E)
 900     return false;
 901
 902   E = E->IgnoreParenCasts();
 903
 904   if (isa<AbstractConditionalOperator>(E))
 905     return true;
 906
 907   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
 908     if (B->isLogicalOp())
 909       return true;
 910
 911   return false;
 912 }
 913
 914 namespace {
 915 class ContextLocation : public PathDiagnosticLocation {
 916   bool IsDead;
 917 public:
 918   ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
 919     : PathDiagnosticLocation(L), IsDead(isdead) {}
 920
 921   void markDead() { IsDead = true; }
 922   bool isDead() const { return IsDead; }
 923 };
 924
 925 static PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
 926                                               const LocationContext *LC,
 927                                               bool firstCharOnly = false) {
 928   if (const Stmt *S = L.asStmt()) {
 929     const Stmt *Original = S;
 930     while (1) {
 931       // Adjust the location for some expressions that are best referenced
 932       // by one of their subexpressions.
 933       switch (S->getStmtClass()) {
 934         default:
 935           break;
 936         case Stmt::ParenExprClass:
 937         case Stmt::GenericSelectionExprClass:
 938           S = cast<Expr>(S)->IgnoreParens();
 939           firstCharOnly = true;
 940           continue;
 941         case Stmt::BinaryConditionalOperatorClass:
 942         case Stmt::ConditionalOperatorClass:
 943           S = cast<AbstractConditionalOperator>(S)->getCond();
 944           firstCharOnly = true;
 945           continue;
 946         case Stmt::ChooseExprClass:
 947           S = cast<ChooseExpr>(S)->getCond();
 948           firstCharOnly = true;
 949           continue;
 950         case Stmt::BinaryOperatorClass:
 951           S = cast<BinaryOperator>(S)->getLHS();
 952           firstCharOnly = true;
 953           continue;
 954       }
 955
 956       break;
 957     }
 958
 959     if (S != Original)
 960       L = PathDiagnosticLocation(S, L.getManager(), LC);
 961   }
 962
 963   if (firstCharOnly)
 964     L  = PathDiagnosticLocation::createSingleLocation(L);
 965
 966   return L;
 967 }
 968
 969 class EdgeBuilder {
 970   std::vector<ContextLocation> CLocs;
 971   typedef std::vector<ContextLocation>::iterator iterator;
 972   PathDiagnostic &PD;
 973   PathDiagnosticBuilder &PDB;
 974   PathDiagnosticLocation PrevLoc;
 975
 976   bool IsConsumedExpr(const PathDiagnosticLocation &L);
 977
 978   bool containsLocation(const PathDiagnosticLocation &Container,
 979                         const PathDiagnosticLocation &Containee);
 980
 981   PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
 982
 983
 984
 985   void popLocation() {
 986     if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
 987       // For contexts, we only one the first character as the range.
 988       rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true));
 989     }
 990     CLocs.pop_back();
 991   }
 992
 993 public:
 994   EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
 995     : PD(pd), PDB(pdb) {
 996
 997       // If the PathDiagnostic already has pieces, add the enclosing statement
 998       // of the first piece as a context as well.
 999       if (!PD.path.empty()) {
1000         PrevLoc = (*PD.path.begin())->getLocation();
1001
1002         if (const Stmt *S = PrevLoc.asStmt())
1003           addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1004       }
1005   }
1006
1007   ~EdgeBuilder() {
1008     while (!CLocs.empty()) popLocation();
1009
1010     // Finally, add an initial edge from the start location of the first
1011     // statement (if it doesn't already exist).
1012     PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin(
1013                                                        PDB.LC,
1014                                                        PDB.getSourceManager());
1015     if (L.isValid())
1016       rawAddEdge(L);
1017   }
1018
1019   void flushLocations() {
1020     while (!CLocs.empty())
1021       popLocation();
1022     PrevLoc = PathDiagnosticLocation();
1023   }
1024
1025   void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false,
1026                bool IsPostJump = false);
1027
1028   void rawAddEdge(PathDiagnosticLocation NewLoc);
1029
1030   void addContext(const Stmt *S);
1031   void addContext(const PathDiagnosticLocation &L);
1032   void addExtendedContext(const Stmt *S);
1033 };
1034 } // end anonymous namespace
1035
1036
1037 PathDiagnosticLocation
1038 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
1039   if (const Stmt *S = L.asStmt()) {
1040     if (IsControlFlowExpr(S))
1041       return L;
1042
1043     return PDB.getEnclosingStmtLocation(S);
1044   }
1045
1046   return L;
1047 }
1048
1049 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
1050                                    const PathDiagnosticLocation &Containee) {
1051
1052   if (Container == Containee)
1053     return true;
1054
1055   if (Container.asDecl())
1056     return true;
1057
1058   if (const Stmt *S = Containee.asStmt())
1059     if (const Stmt *ContainerS = Container.asStmt()) {
1060       while (S) {
1061         if (S == ContainerS)
1062           return true;
1063         S = PDB.getParent(S);
1064       }
1065       return false;
1066     }
1067
1068   // Less accurate: compare using source ranges.
1069   SourceRange ContainerR = Container.asRange();
1070   SourceRange ContaineeR = Containee.asRange();
1071
1072   SourceManager &SM = PDB.getSourceManager();
1073   SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
1074   SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
1075   SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
1076   SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
1077
1078   unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
1079   unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
1080   unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
1081   unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
1082
1083   assert(ContainerBegLine <= ContainerEndLine);
1084   assert(ContaineeBegLine <= ContaineeEndLine);
1085
1086   return (ContainerBegLine <= ContaineeBegLine &&
1087           ContainerEndLine >= ContaineeEndLine &&
1088           (ContainerBegLine != ContaineeBegLine ||
1089            SM.getExpansionColumnNumber(ContainerRBeg) <=
1090            SM.getExpansionColumnNumber(ContaineeRBeg)) &&
1091           (ContainerEndLine != ContaineeEndLine ||
1092            SM.getExpansionColumnNumber(ContainerREnd) >=
1093            SM.getExpansionColumnNumber(ContaineeREnd)));
1094 }
1095
1096 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1097   if (!PrevLoc.isValid()) {
1098     PrevLoc = NewLoc;
1099     return;
1100   }
1101
1102   const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC);
1103   const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC);
1104
1105   if (PrevLocClean.asLocation().isInvalid()) {
1106     PrevLoc = NewLoc;
1107     return;
1108   }
1109
1110   if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1111     return;
1112
1113   // FIXME: Ignore intra-macro edges for now.
1114   if (NewLocClean.asLocation().getExpansionLoc() ==
1115       PrevLocClean.asLocation().getExpansionLoc())
1116     return;
1117
1118   PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1119   PrevLoc = NewLoc;
1120 }
1121
1122 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd,
1123                           bool IsPostJump) {
1124
1125   if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1126     return;
1127
1128   const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1129
1130   while (!CLocs.empty()) {
1131     ContextLocation &TopContextLoc = CLocs.back();
1132
1133     // Is the top location context the same as the one for the new location?
1134     if (TopContextLoc == CLoc) {
1135       if (alwaysAdd) {
1136         if (IsConsumedExpr(TopContextLoc))
1137           TopContextLoc.markDead();
1138
1139         rawAddEdge(NewLoc);
1140       }
1141
1142       if (IsPostJump)
1143         TopContextLoc.markDead();
1144       return;
1145     }
1146
1147     if (containsLocation(TopContextLoc, CLoc)) {
1148       if (alwaysAdd) {
1149         rawAddEdge(NewLoc);
1150
1151         if (IsConsumedExpr(CLoc)) {
1152           CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true));
1153           return;
1154         }
1155       }
1156
1157       CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump));
1158       return;
1159     }
1160
1161     // Context does not contain the location.  Flush it.
1162     popLocation();
1163   }
1164
1165   // If we reach here, there is no enclosing context.  Just add the edge.
1166   rawAddEdge(NewLoc);
1167 }
1168
1169 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1170   if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1171     return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1172
1173   return false;
1174 }
1175
1176 void EdgeBuilder::addExtendedContext(const Stmt *S) {
1177   if (!S)
1178     return;
1179
1180   const Stmt *Parent = PDB.getParent(S);
1181   while (Parent) {
1182     if (isa<CompoundStmt>(Parent))
1183       Parent = PDB.getParent(Parent);
1184     else
1185       break;
1186   }
1187
1188   if (Parent) {
1189     switch (Parent->getStmtClass()) {
1190       case Stmt::DoStmtClass:
1191       case Stmt::ObjCAtSynchronizedStmtClass:
1192         addContext(Parent);
1193       default:
1194         break;
1195     }
1196   }
1197
1198   addContext(S);
1199 }
1200
1201 void EdgeBuilder::addContext(const Stmt *S) {
1202   if (!S)
1203     return;
1204
1205   PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC);
1206   addContext(L);
1207 }
1208
1209 void EdgeBuilder::addContext(const PathDiagnosticLocation &L) {
1210   while (!CLocs.empty()) {
1211     const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1212
1213     // Is the top location context the same as the one for the new location?
1214     if (TopContextLoc == L)
1215       return;
1216
1217     if (containsLocation(TopContextLoc, L)) {
1218       CLocs.push_back(L);
1219       return;
1220     }
1221
1222     // Context does not contain the location.  Flush it.
1223     popLocation();
1224   }
1225
1226   CLocs.push_back(L);
1227 }
1228
1229 // Cone-of-influence: support the reverse propagation of "interesting" symbols
1230 // and values by tracing interesting calculations backwards through evaluated
1231 // expressions along a path.  This is probably overly complicated, but the idea
1232 // is that if an expression computed an "interesting" value, the child
1233 // expressions are are also likely to be "interesting" as well (which then
1234 // propagates to the values they in turn compute).  This reverse propagation
1235 // is needed to track interesting correlations across function call boundaries,
1236 // where formal arguments bind to actual arguments, etc.  This is also needed
1237 // because the constraint solver sometimes simplifies certain symbolic values
1238 // into constants when appropriate, and this complicates reasoning about
1239 // interesting values.
1240 typedef llvm::DenseSet<const Expr *> InterestingExprs;
1241
1242 static void reversePropagateIntererstingSymbols(BugReport &R,
1243                                                 InterestingExprs &IE,
1244                                                 const ProgramState *State,
1245                                                 const Expr *Ex,
1246                                                 const LocationContext *LCtx) {
1247   SVal V = State->getSVal(Ex, LCtx);
1248   if (!(R.isInteresting(V) || IE.count(Ex)))
1249     return;
1250
1251   switch (Ex->getStmtClass()) {
1252     default:
1253       if (!isa<CastExpr>(Ex))
1254         break;
1255       // Fall through.
1256     case Stmt::BinaryOperatorClass:
1257     case Stmt::UnaryOperatorClass: {
1258       for (Stmt::const_child_iterator CI = Ex->child_begin(),
1259             CE = Ex->child_end();
1260             CI != CE; ++CI) {
1261         if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) {
1262           IE.insert(child);
1263           SVal ChildV = State->getSVal(child, LCtx);
1264           R.markInteresting(ChildV);
1265         }
1266         break;
1267       }
1268     }
1269   }
1270
1271   R.markInteresting(V);
1272 }
1273
1274 static void reversePropagateInterestingSymbols(BugReport &R,
1275                                                InterestingExprs &IE,
1276                                                const ProgramState *State,
1277                                                const LocationContext *CalleeCtx,
1278                                                const LocationContext *CallerCtx)
1279 {
1280   // FIXME: Handle non-CallExpr-based CallEvents.
1281   const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame();
1282   const Stmt *CallSite = Callee->getCallSite();
1283   if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) {
1284     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) {
1285       FunctionDecl::param_const_iterator PI = FD->param_begin(),
1286                                          PE = FD->param_end();
1287       CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1288       for (; AI != AE && PI != PE; ++AI, ++PI) {
1289         if (const Expr *ArgE = *AI) {
1290           if (const ParmVarDecl *PD = *PI) {
1291             Loc LV = State->getLValue(PD, CalleeCtx);
1292             if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV)))
1293               IE.insert(ArgE);
1294           }
1295         }
1296       }
1297     }
1298   }
1299 }
1300
1301 //===----------------------------------------------------------------------===//
1302 // Functions for determining if a loop was executed 0 times.
1303 //===----------------------------------------------------------------------===//
1304
1305 static bool isLoop(const Stmt *Term) {
1306   switch (Term->getStmtClass()) {
1307     case Stmt::ForStmtClass:
1308     case Stmt::WhileStmtClass:
1309     case Stmt::ObjCForCollectionStmtClass:
1310     case Stmt::CXXForRangeStmtClass:
1311       return true;
1312     default:
1313       // Note that we intentionally do not include do..while here.
1314       return false;
1315   }
1316 }
1317
1318 static bool isJumpToFalseBranch(const BlockEdge *BE) {
1319   const CFGBlock *Src = BE->getSrc();
1320   assert(Src->succ_size() == 2);
1321   return (*(Src->succ_begin()+1) == BE->getDst());
1322 }
1323
1324 /// Return true if the terminator is a loop and the destination is the
1325 /// false branch.
1326 static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
1327   if (!isLoop(Term))
1328     return false;
1329
1330   // Did we take the false branch?
1331   return isJumpToFalseBranch(BE);
1332 }
1333
1334 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
1335   while (SubS) {
1336     if (SubS == S)
1337       return true;
1338     SubS = PM.getParent(SubS);
1339   }
1340   return false;
1341 }
1342
1343 static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term,
1344                                      const ExplodedNode *N) {
1345   while (N) {
1346     Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>();
1347     if (SP) {
1348       const Stmt *S = SP->getStmt();
1349       if (!isContainedByStmt(PM, Term, S))
1350         return S;
1351     }
1352     N = N->getFirstPred();
1353   }
1354   return 0;
1355 }
1356
1357 static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) {
1358   const Stmt *LoopBody = 0;
1359   switch (Term->getStmtClass()) {
1360     case Stmt::CXXForRangeStmtClass: {
1361       const CXXForRangeStmt *FR = cast<CXXForRangeStmt>(Term);
1362       if (isContainedByStmt(PM, FR->getInc(), S))
1363         return true;
1364       if (isContainedByStmt(PM, FR->getLoopVarStmt(), S))
1365         return true;
1366       LoopBody = FR->getBody();
1367       break;
1368     }
1369     case Stmt::ForStmtClass: {
1370       const ForStmt *FS = cast<ForStmt>(Term);
1371       if (isContainedByStmt(PM, FS->getInc(), S))
1372         return true;
1373       LoopBody = FS->getBody();
1374       break;
1375     }
1376     case Stmt::ObjCForCollectionStmtClass: {
1377       const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term);
1378       LoopBody = FC->getBody();
1379       break;
1380     }
1381     case Stmt::WhileStmtClass:
1382       LoopBody = cast<WhileStmt>(Term)->getBody();
1383       break;
1384     default:
1385       return false;
1386   }
1387   return isContainedByStmt(PM, LoopBody, S);
1388 }
1389
1390 //===----------------------------------------------------------------------===//
1391 // Top-level logic for generating extensive path diagnostics.
1392 //===----------------------------------------------------------------------===//
1393
1394 static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1395                                             PathDiagnosticBuilder &PDB,
1396                                             const ExplodedNode *N,
1397                                             LocationContextMap &LCM,
1398                                       ArrayRef<BugReporterVisitor *> visitors) {
1399   EdgeBuilder EB(PD, PDB);
1400   const SourceManager& SM = PDB.getSourceManager();
1401   StackDiagVector CallStack;
1402   InterestingExprs IE;
1403
1404   const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
1405   while (NextNode) {
1406     N = NextNode;
1407     NextNode = N->getFirstPred();
1408     ProgramPoint P = N->getLocation();
1409
1410     do {
1411       if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1412         if (const Expr *Ex = PS->getStmtAs<Expr>())
1413           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1414                                               N->getState().getPtr(), Ex,
1415                                               N->getLocationContext());
1416       }
1417
1418       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1419         const Stmt *S = CE->getCalleeContext()->getCallSite();
1420         if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1421             reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1422                                                 N->getState().getPtr(), Ex,
1423                                                 N->getLocationContext());
1424         }
1425
1426         PathDiagnosticCallPiece *C =
1427           PathDiagnosticCallPiece::construct(N, *CE, SM);
1428         LCM[&C->path] = CE->getCalleeContext();
1429
1430         EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true);
1431         EB.flushLocations();
1432
1433         PD.getActivePath().push_front(C);
1434         PD.pushActivePath(&C->path);
1435         CallStack.push_back(StackDiagPair(C, N));
1436         break;
1437       }
1438
1439       // Pop the call hierarchy if we are done walking the contents
1440       // of a function call.
1441       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1442         // Add an edge to the start of the function.
1443         const Decl *D = CE->getCalleeContext()->getDecl();
1444         PathDiagnosticLocation pos =
1445           PathDiagnosticLocation::createBegin(D, SM);
1446         EB.addEdge(pos);
1447
1448         // Flush all locations, and pop the active path.
1449         bool VisitedEntireCall = PD.isWithinCall();
1450         EB.flushLocations();
1451         PD.popActivePath();
1452         PDB.LC = N->getLocationContext();
1453
1454         // Either we just added a bunch of stuff to the top-level path, or
1455         // we have a previous CallExitEnd.  If the former, it means that the
1456         // path terminated within a function call.  We must then take the
1457         // current contents of the active path and place it within
1458         // a new PathDiagnosticCallPiece.
1459         PathDiagnosticCallPiece *C;
1460         if (VisitedEntireCall) {
1461           C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
1462         } else {
1463           const Decl *Caller = CE->getLocationContext()->getDecl();
1464           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1465           LCM[&C->path] = CE->getCalleeContext();
1466         }
1467
1468         C->setCallee(*CE, SM);
1469         EB.addContext(C->getLocation());
1470
1471         if (!CallStack.empty()) {
1472           assert(CallStack.back().first == C);
1473           CallStack.pop_back();
1474         }
1475         break;
1476       }
1477
1478       // Note that is important that we update the LocationContext
1479       // after looking at CallExits.  CallExit basically adds an
1480       // edge in the *caller*, so we don't want to update the LocationContext
1481       // too soon.
1482       PDB.LC = N->getLocationContext();
1483
1484       // Block edges.
1485       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1486         // Does this represent entering a call?  If so, look at propagating
1487         // interesting symbols across call boundaries.
1488         if (NextNode) {
1489           const LocationContext *CallerCtx = NextNode->getLocationContext();
1490           const LocationContext *CalleeCtx = PDB.LC;
1491           if (CallerCtx != CalleeCtx) {
1492             reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1493                                                N->getState().getPtr(),
1494                                                CalleeCtx, CallerCtx);
1495           }
1496         }
1497
1498         // Are we jumping to the head of a loop?  Add a special diagnostic.
1499         if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1500           PathDiagnosticLocation L(Loop, SM, PDB.LC);
1501           const CompoundStmt *CS = NULL;
1502
1503           if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1504             CS = dyn_cast<CompoundStmt>(FS->getBody());
1505           else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1506             CS = dyn_cast<CompoundStmt>(WS->getBody());
1507
1508           PathDiagnosticEventPiece *p =
1509             new PathDiagnosticEventPiece(L,
1510                                         "Looping back to the head of the loop");
1511           p->setPrunable(true);
1512
1513           EB.addEdge(p->getLocation(), true);
1514           PD.getActivePath().push_front(p);
1515
1516           if (CS) {
1517             PathDiagnosticLocation BL =
1518               PathDiagnosticLocation::createEndBrace(CS, SM);
1519             EB.addEdge(BL);
1520           }
1521         }
1522
1523         const CFGBlock *BSrc = BE->getSrc();
1524         ParentMap &PM = PDB.getParentMap();
1525
1526         if (const Stmt *Term = BSrc->getTerminator()) {
1527           // Are we jumping past the loop body without ever executing the
1528           // loop (because the condition was false)?
1529           if (isLoopJumpPastBody(Term, &*BE) &&
1530               !isInLoopBody(PM,
1531                             getStmtBeforeCond(PM,
1532                                               BSrc->getTerminatorCondition(),
1533                                               N),
1534                             Term)) {
1535             PathDiagnosticLocation L(Term, SM, PDB.LC);
1536             PathDiagnosticEventPiece *PE =
1537                 new PathDiagnosticEventPiece(L, "Loop body executed 0 times");
1538             PE->setPrunable(true);
1539
1540             EB.addEdge(PE->getLocation(), true);
1541             PD.getActivePath().push_front(PE);
1542           }
1543
1544           // In any case, add the terminator as the current statement
1545           // context for control edges.
1546           EB.addContext(Term);
1547         }
1548
1549         break;
1550       }
1551
1552       if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
1553         Optional<CFGElement> First = BE->getFirstElement();
1554         if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) {
1555           const Stmt *stmt = S->getStmt();
1556           if (IsControlFlowExpr(stmt)) {
1557             // Add the proper context for '&&', '||', and '?'.
1558             EB.addContext(stmt);
1559           }
1560           else
1561             EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
1562         }
1563
1564         break;
1565       }
1566
1567
1568     } while (0);
1569
1570     if (!NextNode)
1571       continue;
1572
1573     // Add pieces from custom visitors.
1574     BugReport *R = PDB.getBugReport();
1575     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1576                                                   E = visitors.end();
1577          I != E; ++I) {
1578       if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
1579         const PathDiagnosticLocation &Loc = p->getLocation();
1580         EB.addEdge(Loc, true);
1581         PD.getActivePath().push_front(p);
1582         updateStackPiecesWithMessage(p, CallStack);
1583
1584         if (const Stmt *S = Loc.asStmt())
1585           EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1586       }
1587     }
1588   }
1589
1590   return PDB.getBugReport()->isValid();
1591 }
1592
1593 /// \brief Adds a sanitized control-flow diagnostic edge to a path.
1594 static void addEdgeToPath(PathPieces &path,
1595                           PathDiagnosticLocation &PrevLoc,
1596                           PathDiagnosticLocation NewLoc,
1597                           const LocationContext *LC) {
1598   if (!NewLoc.isValid())
1599     return;
1600
1601   SourceLocation NewLocL = NewLoc.asLocation();
1602   if (NewLocL.isInvalid())
1603     return;
1604
1605   if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) {
1606     PrevLoc = NewLoc;
1607     return;
1608   }
1609
1610   // Ignore self-edges, which occur when there are multiple nodes at the same
1611   // statement.
1612   if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt())
1613     return;
1614
1615   path.push_front(new PathDiagnosticControlFlowPiece(NewLoc,
1616                                                      PrevLoc));
1617   PrevLoc = NewLoc;
1618 }
1619
1620 /// A customized wrapper for CFGBlock::getTerminatorCondition()
1621 /// which returns the element for ObjCForCollectionStmts.
1622 static const Stmt *getTerminatorCondition(const CFGBlock *B) {
1623   const Stmt *S = B->getTerminatorCondition();
1624   if (const ObjCForCollectionStmt *FS =
1625       dyn_cast_or_null<ObjCForCollectionStmt>(S))
1626     return FS->getElement();
1627   return S;
1628 }
1629
1630 static const char StrEnteringLoop[] = "Entering loop body";
1631 static const char StrLoopBodyZero[] = "Loop body executed 0 times";
1632 static const char StrLoopRangeEmpty[] =
1633   "Loop body skipped when range is empty";
1634 static const char StrLoopCollectionEmpty[] =
1635   "Loop body skipped when collection is empty";
1636
1637 static bool
1638 GenerateAlternateExtensivePathDiagnostic(PathDiagnostic& PD,
1639                                          PathDiagnosticBuilder &PDB,
1640                                          const ExplodedNode *N,
1641                                          LocationContextMap &LCM,
1642                                       ArrayRef<BugReporterVisitor *> visitors) {
1643
1644   BugReport *report = PDB.getBugReport();
1645   const SourceManager& SM = PDB.getSourceManager();
1646   StackDiagVector CallStack;
1647   InterestingExprs IE;
1648
1649   PathDiagnosticLocation PrevLoc = PD.getLocation();
1650
1651   const ExplodedNode *NextNode = N->getFirstPred();
1652   while (NextNode) {
1653     N = NextNode;
1654     NextNode = N->getFirstPred();
1655     ProgramPoint P = N->getLocation();
1656
1657     do {
1658       // Have we encountered an entrance to a call?  It may be
1659       // the case that we have not encountered a matching
1660       // call exit before this point.  This means that the path
1661       // terminated within the call itself.
1662       if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1663         // Add an edge to the start of the function.
1664         const StackFrameContext *CalleeLC = CE->getCalleeContext();
1665         const Decl *D = CalleeLC->getDecl();
1666         addEdgeToPath(PD.getActivePath(), PrevLoc,
1667                       PathDiagnosticLocation::createBegin(D, SM),
1668                       CalleeLC);
1669
1670         // Did we visit an entire call?
1671         bool VisitedEntireCall = PD.isWithinCall();
1672         PD.popActivePath();
1673
1674         PathDiagnosticCallPiece *C;
1675         if (VisitedEntireCall) {
1676           PathDiagnosticPiece *P = PD.getActivePath().front().getPtr();
1677           C = cast<PathDiagnosticCallPiece>(P);
1678         } else {
1679           const Decl *Caller = CE->getLocationContext()->getDecl();
1680           C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1681
1682           // Since we just transferred the path over to the call piece,
1683           // reset the mapping from active to location context.
1684           assert(PD.getActivePath().size() == 1 &&
1685                  PD.getActivePath().front() == C);
1686           LCM[&PD.getActivePath()] = 0;
1687
1688           // Record the location context mapping for the path within
1689           // the call.
1690           assert(LCM[&C->path] == 0 ||
1691                  LCM[&C->path] == CE->getCalleeContext());
1692           LCM[&C->path] = CE->getCalleeContext();
1693
1694           // If this is the first item in the active path, record
1695           // the new mapping from active path to location context.
1696           const LocationContext *&NewLC = LCM[&PD.getActivePath()];
1697           if (!NewLC)
1698             NewLC = N->getLocationContext();
1699
1700           PDB.LC = NewLC;
1701         }
1702         C->setCallee(*CE, SM);
1703
1704         // Update the previous location in the active path.
1705         PrevLoc = C->getLocation();
1706
1707         if (!CallStack.empty()) {
1708           assert(CallStack.back().first == C);
1709           CallStack.pop_back();
1710         }
1711         break;
1712       }
1713
1714       // Query the location context here and the previous location
1715       // as processing CallEnter may change the active path.
1716       PDB.LC = N->getLocationContext();
1717
1718       // Record the mapping from the active path to the location
1719       // context.
1720       assert(!LCM[&PD.getActivePath()] ||
1721              LCM[&PD.getActivePath()] == PDB.LC);
1722       LCM[&PD.getActivePath()] = PDB.LC;
1723
1724       // Have we encountered an exit from a function call?
1725       if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1726         const Stmt *S = CE->getCalleeContext()->getCallSite();
1727         // Propagate the interesting symbols accordingly.
1728         if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1729           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1730                                               N->getState().getPtr(), Ex,
1731                                               N->getLocationContext());
1732         }
1733
1734         // We are descending into a call (backwards).  Construct
1735         // a new call piece to contain the path pieces for that call.
1736         PathDiagnosticCallPiece *C =
1737           PathDiagnosticCallPiece::construct(N, *CE, SM);
1738
1739         // Record the location context for this call piece.
1740         LCM[&C->path] = CE->getCalleeContext();
1741
1742         // Add the edge to the return site.
1743         addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC);
1744         PD.getActivePath().push_front(C);
1745         PrevLoc.invalidate();
1746
1747         // Make the contents of the call the active path for now.
1748         PD.pushActivePath(&C->path);
1749         CallStack.push_back(StackDiagPair(C, N));
1750         break;
1751       }
1752
1753       if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1754         // For expressions, make sure we propagate the
1755         // interesting symbols correctly.
1756         if (const Expr *Ex = PS->getStmtAs<Expr>())
1757           reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1758                                               N->getState().getPtr(), Ex,
1759                                               N->getLocationContext());
1760
1761         // Add an edge.  If this is an ObjCForCollectionStmt do
1762         // not add an edge here as it appears in the CFG both
1763         // as a terminator and as a terminator condition.
1764         if (!isa<ObjCForCollectionStmt>(PS->getStmt())) {
1765           PathDiagnosticLocation L =
1766             PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC);
1767           addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1768         }
1769         break;
1770       }
1771
1772       // Block edges.
1773       if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1774         // Does this represent entering a call?  If so, look at propagating
1775         // interesting symbols across call boundaries.
1776         if (NextNode) {
1777           const LocationContext *CallerCtx = NextNode->getLocationContext();
1778           const LocationContext *CalleeCtx = PDB.LC;
1779           if (CallerCtx != CalleeCtx) {
1780             reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1781                                                N->getState().getPtr(),
1782                                                CalleeCtx, CallerCtx);
1783           }
1784         }
1785
1786         // Are we jumping to the head of a loop?  Add a special diagnostic.
1787         if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1788           PathDiagnosticLocation L(Loop, SM, PDB.LC);
1789           const Stmt *Body = NULL;
1790
1791           if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1792             Body = FS->getBody();
1793           else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1794             Body = WS->getBody();
1795           else if (const ObjCForCollectionStmt *OFS =
1796                      dyn_cast<ObjCForCollectionStmt>(Loop)) {
1797             Body = OFS->getBody();
1798           } else if (const CXXForRangeStmt *FRS =
1799                        dyn_cast<CXXForRangeStmt>(Loop)) {
1800             Body = FRS->getBody();
1801           }
1802           // do-while statements are explicitly excluded here
1803
1804           PathDiagnosticEventPiece *p =
1805             new PathDiagnosticEventPiece(L, "Looping back to the head "
1806                                             "of the loop");
1807           p->setPrunable(true);
1808
1809           addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1810           PD.getActivePath().push_front(p);
1811
1812           if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) {
1813             addEdgeToPath(PD.getActivePath(), PrevLoc,
1814                           PathDiagnosticLocation::createEndBrace(CS, SM),
1815                           PDB.LC);
1816           }
1817         }
1818
1819         const CFGBlock *BSrc = BE->getSrc();
1820         ParentMap &PM = PDB.getParentMap();
1821
1822         if (const Stmt *Term = BSrc->getTerminator()) {
1823           // Are we jumping past the loop body without ever executing the
1824           // loop (because the condition was false)?
1825           if (isLoop(Term)) {
1826             const Stmt *TermCond = getTerminatorCondition(BSrc);
1827             bool IsInLoopBody =
1828               isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term);
1829
1830             const char *str = 0;
1831
1832             if (isJumpToFalseBranch(&*BE)) {
1833               if (!IsInLoopBody) {
1834                 if (isa<ObjCForCollectionStmt>(Term)) {
1835                   str = StrLoopCollectionEmpty;
1836                 } else if (isa<CXXForRangeStmt>(Term)) {
1837                   str = StrLoopRangeEmpty;
1838                 } else {
1839                   str = StrLoopBodyZero;
1840                 }
1841               }
1842             } else {
1843               str = StrEnteringLoop;
1844             }
1845
1846             if (str) {
1847               PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC);
1848               PathDiagnosticEventPiece *PE =
1849                 new PathDiagnosticEventPiece(L, str);
1850               PE->setPrunable(true);
1851               addEdgeToPath(PD.getActivePath(), PrevLoc,
1852                             PE->getLocation(), PDB.LC);
1853               PD.getActivePath().push_front(PE);
1854             }
1855           } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) ||
1856                      isa<GotoStmt>(Term)) {
1857             PathDiagnosticLocation L(Term, SM, PDB.LC);
1858             addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1859           }
1860         }
1861         break;
1862       }
1863     } while (0);
1864
1865     if (!NextNode)
1866       continue;
1867
1868     // Add pieces from custom visitors.
1869     for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1870          E = visitors.end();
1871          I != E; ++I) {
1872       if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *report)) {
1873         addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1874         PD.getActivePath().push_front(p);
1875         updateStackPiecesWithMessage(p, CallStack);
1876       }
1877     }
1878   }
1879
1880   // Add an edge to the start of the function.
1881   // We'll prune it out later, but it helps make diagnostics more uniform.
1882   const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame();
1883   const Decl *D = CalleeLC->getDecl();
1884   addEdgeToPath(PD.getActivePath(), PrevLoc,
1885                 PathDiagnosticLocation::createBegin(D, SM),
1886                 CalleeLC);
1887
1888   return report->isValid();
1889 }
1890
1891 static const Stmt *getLocStmt(PathDiagnosticLocation L) {
1892   if (!L.isValid())
1893     return 0;
1894   return L.asStmt();
1895 }
1896
1897 static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) {
1898   if (!S)
1899     return 0;
1900
1901   while (true) {
1902     S = PM.getParentIgnoreParens(S);
1903
1904     if (!S)
1905       break;
1906
1907     if (isa<ExprWithCleanups>(S) ||
1908         isa<CXXBindTemporaryExpr>(S) ||
1909         isa<SubstNonTypeTemplateParmExpr>(S))
1910       continue;
1911
1912     break;
1913   }
1914
1915   return S;
1916 }
1917
1918 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {
1919   switch (S->getStmtClass()) {
1920     case Stmt::BinaryOperatorClass: {
1921       const BinaryOperator *BO = cast<BinaryOperator>(S);
1922       if (!BO->isLogicalOp())
1923         return false;
1924       return BO->getLHS() == Cond || BO->getRHS() == Cond;
1925     }
1926     case Stmt::IfStmtClass:
1927       return cast<IfStmt>(S)->getCond() == Cond;
1928     case Stmt::ForStmtClass:
1929       return cast<ForStmt>(S)->getCond() == Cond;
1930     case Stmt::WhileStmtClass:
1931       return cast<WhileStmt>(S)->getCond() == Cond;
1932     case Stmt::DoStmtClass:
1933       return cast<DoStmt>(S)->getCond() == Cond;
1934     case Stmt::ChooseExprClass:
1935       return cast<ChooseExpr>(S)->getCond() == Cond;
1936     case Stmt::IndirectGotoStmtClass:
1937       return cast<IndirectGotoStmt>(S)->getTarget() == Cond;
1938     case Stmt::SwitchStmtClass:
1939       return cast<SwitchStmt>(S)->getCond() == Cond;
1940     case Stmt::BinaryConditionalOperatorClass:
1941       return cast<BinaryConditionalOperator>(S)->getCond() == Cond;
1942     case Stmt::ConditionalOperatorClass: {
1943       const ConditionalOperator *CO = cast<ConditionalOperator>(S);
1944       return CO->getCond() == Cond ||
1945              CO->getLHS() == Cond ||
1946              CO->getRHS() == Cond;
1947     }
1948     case Stmt::ObjCForCollectionStmtClass:
1949       return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;
1950     case Stmt::CXXForRangeStmtClass: {
1951       const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S);
1952       return FRS->getCond() == Cond || FRS->getRangeInit() == Cond;
1953     }
1954     default:
1955       return false;
1956   }
1957 }
1958
1959 static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {
1960   if (const ForStmt *FS = dyn_cast<ForStmt>(FL))
1961     return FS->getInc() == S || FS->getInit() == S;
1962   if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL))
1963     return FRS->getInc() == S || FRS->getRangeStmt() == S ||
1964            FRS->getLoopVarStmt() || FRS->getRangeInit() == S;
1965   return false;
1966 }
1967
1968 typedef llvm::DenseSet<const PathDiagnosticCallPiece *>
1969         OptimizedCallsSet;
1970
1971 /// Adds synthetic edges from top-level statements to their subexpressions.
1972 ///
1973 /// This avoids a "swoosh" effect, where an edge from a top-level statement A
1974 /// points to a sub-expression B.1 that's not at the start of B. In these cases,
1975 /// we'd like to see an edge from A to B, then another one from B to B.1.
1976 static void addContextEdges(PathPieces &pieces, SourceManager &SM,
1977                             const ParentMap &PM, const LocationContext *LCtx) {
1978   PathPieces::iterator Prev = pieces.end();
1979   for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;
1980        Prev = I, ++I) {
1981     PathDiagnosticControlFlowPiece *Piece =
1982       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
1983
1984     if (!Piece)
1985       continue;
1986
1987     PathDiagnosticLocation SrcLoc = Piece->getStartLocation();
1988     SmallVector<PathDiagnosticLocation, 4> SrcContexts;
1989
1990     PathDiagnosticLocation NextSrcContext = SrcLoc;
1991     const Stmt *InnerStmt = 0;
1992     while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {
1993       SrcContexts.push_back(NextSrcContext);
1994       InnerStmt = NextSrcContext.asStmt();
1995       NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx,
1996                                                 /*allowNested=*/true);
1997     }
1998
1999     // Repeatedly split the edge as necessary.
2000     // This is important for nested logical expressions (||, &&, ?:) where we
2001     // want to show all the levels of context.
2002     while (true) {
2003       const Stmt *Dst = getLocStmt(Piece->getEndLocation());
2004
2005       // We are looking at an edge. Is the destination within a larger
2006       // expression?
2007       PathDiagnosticLocation DstContext =
2008         getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true);
2009       if (!DstContext.isValid() || DstContext.asStmt() == Dst)
2010         break;
2011
2012       // If the source is in the same context, we're already good.
2013       if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) !=
2014           SrcContexts.end())
2015         break;
2016
2017       // Update the subexpression node to point to the context edge.
2018       Piece->setStartLocation(DstContext);
2019
2020       // Try to extend the previous edge if it's at the same level as the source
2021       // context.
2022       if (Prev != E) {
2023         PathDiagnosticControlFlowPiece *PrevPiece =
2024           dyn_cast<PathDiagnosticControlFlowPiece>(*Prev);
2025
2026         if (PrevPiece) {
2027           if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) {
2028             const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);
2029             if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) {
2030               PrevPiece->setEndLocation(DstContext);
2031               break;
2032             }
2033           }
2034         }
2035       }
2036
2037       // Otherwise, split the current edge into a context edge and a
2038       // subexpression edge. Note that the context statement may itself have
2039       // context.
2040       Piece = new PathDiagnosticControlFlowPiece(SrcLoc, DstContext);
2041       I = pieces.insert(I, Piece);
2042     }
2043   }
2044 }
2045
2046 /// \brief Move edges from a branch condition to a branch target
2047 ///        when the condition is simple.
2048 ///
2049 /// This restructures some of the work of addContextEdges.  That function
2050 /// creates edges this may destroy, but they work together to create a more
2051 /// aesthetically set of edges around branches.  After the call to
2052 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from
2053 /// the branch to the branch condition, and (3) an edge from the branch
2054 /// condition to the branch target.  We keep (1), but may wish to remove (2)
2055 /// and move the source of (3) to the branch if the branch condition is simple.
2056 ///
2057 static void simplifySimpleBranches(PathPieces &pieces) {
2058   for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {
2059
2060     PathDiagnosticControlFlowPiece *PieceI =
2061       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2062
2063     if (!PieceI)
2064       continue;
2065
2066     const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2067     const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
2068
2069     if (!s1Start || !s1End)
2070       continue;
2071
2072     PathPieces::iterator NextI = I; ++NextI;
2073     if (NextI == E)
2074       break;
2075
2076     PathDiagnosticControlFlowPiece *PieceNextI = 0;
2077
2078     while (true) {
2079       if (NextI == E)
2080         break;
2081
2082       PathDiagnosticEventPiece *EV = dyn_cast<PathDiagnosticEventPiece>(*NextI);
2083       if (EV) {
2084         StringRef S = EV->getString();
2085         if (S == StrEnteringLoop || S == StrLoopBodyZero ||
2086             S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) {
2087           ++NextI;
2088           continue;
2089         }
2090         break;
2091       }
2092
2093       PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2094       break;
2095     }
2096
2097     if (!PieceNextI)
2098       continue;
2099
2100     const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2101     const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
2102
2103     if (!s2Start || !s2End || s1End != s2Start)
2104       continue;
2105
2106     // We only perform this transformation for specific branch kinds.
2107     // We don't want to do this for do..while, for example.
2108     if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) ||
2109           isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) ||
2110           isa<CXXForRangeStmt>(s1Start)))
2111       continue;
2112
2113     // Is s1End the branch condition?
2114     if (!isConditionForTerminator(s1Start, s1End))
2115       continue;
2116
2117     // Perform the hoisting by eliminating (2) and changing the start
2118     // location of (3).
2119     PieceNextI->setStartLocation(PieceI->getStartLocation());
2120     I = pieces.erase(I);
2121   }
2122 }
2123
2124 /// Returns the number of bytes in the given (character-based) SourceRange.
2125 ///
2126 /// If the locations in the range are not on the same line, returns None.
2127 ///
2128 /// Note that this does not do a precise user-visible character or column count.
2129 static Optional<size_t> getLengthOnSingleLine(SourceManager &SM,
2130                                               SourceRange Range) {
2131   SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),
2132                              SM.getExpansionRange(Range.getEnd()).second);
2133
2134   FileID FID = SM.getFileID(ExpansionRange.getBegin());
2135   if (FID != SM.getFileID(ExpansionRange.getEnd()))
2136     return None;
2137
2138   bool Invalid;
2139   const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid);
2140   if (Invalid)
2141     return None;
2142
2143   unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
2144   unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
2145   StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
2146
2147   // We're searching the raw bytes of the buffer here, which might include
2148   // escaped newlines and such. That's okay; we're trying to decide whether the
2149   // SourceRange is covering a large or small amount of space in the user's
2150   // editor.
2151   if (Snippet.find_first_of("\r\n") != StringRef::npos)
2152     return None;
2153
2154   // This isn't Unicode-aware, but it doesn't need to be.
2155   return Snippet.size();
2156 }
2157
2158 /// \sa getLengthOnSingleLine(SourceManager, SourceRange)
2159 static Optional<size_t> getLengthOnSingleLine(SourceManager &SM,
2160                                               const Stmt *S) {
2161   return getLengthOnSingleLine(SM, S->getSourceRange());
2162 }
2163
2164 /// Eliminate two-edge cycles created by addContextEdges().
2165 ///
2166 /// Once all the context edges are in place, there are plenty of cases where
2167 /// there's a single edge from a top-level statement to a subexpression,
2168 /// followed by a single path note, and then a reverse edge to get back out to
2169 /// the top level. If the statement is simple enough, the subexpression edges
2170 /// just add noise and make it harder to understand what's going on.
2171 ///
2172 /// This function only removes edges in pairs, because removing only one edge
2173 /// might leave other edges dangling.
2174 ///
2175 /// This will not remove edges in more complicated situations:
2176 /// - if there is more than one "hop" leading to or from a subexpression.
2177 /// - if there is an inlined call between the edges instead of a single event.
2178 /// - if the whole statement is large enough that having subexpression arrows
2179 ///   might be helpful.
2180 static void removeContextCycles(PathPieces &Path, SourceManager &SM,
2181                                 ParentMap &PM) {
2182   for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
2183     // Pattern match the current piece and its successor.
2184     PathDiagnosticControlFlowPiece *PieceI =
2185       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2186
2187     if (!PieceI) {
2188       ++I;
2189       continue;
2190     }
2191
2192     const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2193     const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
2194
2195     PathPieces::iterator NextI = I; ++NextI;
2196     if (NextI == E)
2197       break;
2198
2199     PathDiagnosticControlFlowPiece *PieceNextI =
2200       dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2201
2202     if (!PieceNextI) {
2203       if (isa<PathDiagnosticEventPiece>(*NextI)) {
2204         ++NextI;
2205         if (NextI == E)
2206           break;
2207         PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2208       }
2209
2210       if (!PieceNextI) {
2211         ++I;
2212         continue;
2213       }
2214     }
2215
2216     const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2217     const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
2218
2219     if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
2220       const size_t MAX_SHORT_LINE_LENGTH = 80;
2221       Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
2222       if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {
2223         Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
2224         if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
2225           Path.erase(I);
2226           I = Path.erase(NextI);
2227           continue;
2228         }
2229       }
2230     }
2231
2232     ++I;
2233   }
2234 }
2235
2236 /// \brief Return true if X is contained by Y.
2237 static bool lexicalContains(ParentMap &PM,
2238                             const Stmt *X,
2239                             const Stmt *Y) {
2240   while (X) {
2241     if (X == Y)
2242       return true;
2243     X = PM.getParent(X);
2244   }
2245   return false;
2246 }
2247
2248 // Remove short edges on the same line less than 3 columns in difference.
2249 static void removePunyEdges(PathPieces &path,
2250                             SourceManager &SM,
2251                             ParentMap &PM) {
2252
2253   bool erased = false;
2254
2255   for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
2256        erased ? I : ++I) {
2257
2258     erased = false;
2259
2260     PathDiagnosticControlFlowPiece *PieceI =
2261       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2262
2263     if (!PieceI)
2264       continue;
2265
2266     const Stmt *start = getLocStmt(PieceI->getStartLocation());
2267     const Stmt *end   = getLocStmt(PieceI->getEndLocation());
2268
2269     if (!start || !end)
2270       continue;
2271
2272     const Stmt *endParent = PM.getParent(end);
2273     if (!endParent)
2274       continue;
2275
2276     if (isConditionForTerminator(end, endParent))
2277       continue;
2278
2279     SourceLocation FirstLoc = start->getLocStart();
2280     SourceLocation SecondLoc = end->getLocStart();
2281
2282     if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
2283       continue;
2284     if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
2285       std::swap(SecondLoc, FirstLoc);
2286
2287     SourceRange EdgeRange(FirstLoc, SecondLoc);
2288     Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
2289
2290     // If the statements are on different lines, continue.
2291     if (!ByteWidth)
2292       continue;
2293
2294     const size_t MAX_PUNY_EDGE_LENGTH = 2;
2295     if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
2296       // FIXME: There are enough /bytes/ between the endpoints of the edge, but
2297       // there might not be enough /columns/. A proper user-visible column count
2298       // is probably too expensive, though.
2299       I = path.erase(I);
2300       erased = true;
2301       continue;
2302     }
2303   }
2304 }
2305
2306 static void removeIdenticalEvents(PathPieces &path) {
2307   for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
2308     PathDiagnosticEventPiece *PieceI =
2309       dyn_cast<PathDiagnosticEventPiece>(*I);
2310
2311     if (!PieceI)
2312       continue;
2313
2314     PathPieces::iterator NextI = I; ++NextI;
2315     if (NextI == E)
2316       return;
2317
2318     PathDiagnosticEventPiece *PieceNextI =
2319       dyn_cast<PathDiagnosticEventPiece>(*NextI);
2320
2321     if (!PieceNextI)
2322       continue;
2323
2324     // Erase the second piece if it has the same exact message text.
2325     if (PieceI->getString() == PieceNextI->getString()) {
2326       path.erase(NextI);
2327     }
2328   }
2329 }
2330
2331 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
2332                           OptimizedCallsSet &OCS,
2333                           LocationContextMap &LCM) {
2334   bool hasChanges = false;
2335   const LocationContext *LC = LCM[&path];
2336   assert(LC);
2337   ParentMap &PM = LC->getParentMap();
2338
2339   for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
2340     // Optimize subpaths.
2341     if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){
2342       // Record the fact that a call has been optimized so we only do the
2343       // effort once.
2344       if (!OCS.count(CallI)) {
2345         while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
2346         OCS.insert(CallI);
2347       }
2348       ++I;
2349       continue;
2350     }
2351
2352     // Pattern match the current piece and its successor.
2353     PathDiagnosticControlFlowPiece *PieceI =
2354       dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2355
2356     if (!PieceI) {
2357       ++I;
2358       continue;
2359     }
2360
2361     const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2362     const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
2363     const Stmt *level1 = getStmtParent(s1Start, PM);
2364     const Stmt *level2 = getStmtParent(s1End, PM);
2365
2366     PathPieces::iterator NextI = I; ++NextI;
2367     if (NextI == E)
2368       break;
2369
2370     PathDiagnosticControlFlowPiece *PieceNextI =
2371       dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2372
2373     if (!PieceNextI) {
2374       ++I;
2375       continue;
2376     }
2377
2378     const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2379     const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
2380     const Stmt *level3 = getStmtParent(s2Start, PM);
2381     const Stmt *level4 = getStmtParent(s2End, PM);
2382
2383     // Rule I.
2384     //
2385     // If we have two consecutive control edges whose end/begin locations
2386     // are at the same level (e.g. statements or top-level expressions within
2387     // a compound statement, or siblings share a single ancestor expression),
2388     // then merge them if they have no interesting intermediate event.
2389     //
2390     // For example:
2391     //
2392     // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
2393     // parent is '1'.  Here 'x.y.z' represents the hierarchy of statements.
2394     //
2395     // NOTE: this will be limited later in cases where we add barriers
2396     // to prevent this optimization.
2397     //
2398     if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
2399       PieceI->setEndLocation(PieceNextI->getEndLocation());
2400       path.erase(NextI);
2401       hasChanges = true;
2402       continue;
2403     }
2404
2405     // Rule II.
2406     //
2407     // Eliminate edges between subexpressions and parent expressions
2408     // when the subexpression is consumed.
2409     //
2410     // NOTE: this will be limited later in cases where we add barriers
2411     // to prevent this optimization.
2412     //
2413     if (s1End && s1End == s2Start && level2) {
2414       bool removeEdge = false;
2415       // Remove edges into the increment or initialization of a
2416       // loop that have no interleaving event.  This means that
2417       // they aren't interesting.
2418       if (isIncrementOrInitInForLoop(s1End, level2))
2419         removeEdge = true;
2420       // Next only consider edges that are not anchored on
2421       // the condition of a terminator.  This are intermediate edges
2422       // that we might want to trim.
2423       else if (!isConditionForTerminator(level2, s1End)) {
2424         // Trim edges on expressions that are consumed by
2425         // the parent expression.
2426         if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
2427           removeEdge = true;
2428         }
2429         // Trim edges where a lexical containment doesn't exist.
2430         // For example:
2431         //
2432         //  X -> Y -> Z
2433         //
2434         // If 'Z' lexically contains Y (it is an ancestor) and
2435         // 'X' does not lexically contain Y (it is a descendant OR
2436         // it has no lexical relationship at all) then trim.
2437         //
2438         // This can eliminate edges where we dive into a subexpression
2439         // and then pop back out, etc.
2440         else if (s1Start && s2End &&
2441                  lexicalContains(PM, s2Start, s2End) &&
2442                  !lexicalContains(PM, s1End, s1Start)) {
2443           removeEdge = true;
2444         }
2445         // Trim edges from a subexpression back to the top level if the
2446         // subexpression is on a different line.
2447         //
2448         // A.1 -> A -> B
2449         // becomes
2450         // A.1 -> B
2451         //
2452         // These edges just look ugly and don't usually add anything.
2453         else if (s1Start && s2End &&
2454                  lexicalContains(PM, s1Start, s1End)) {
2455           SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
2456                                 PieceI->getStartLocation().asLocation());
2457           if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
2458             removeEdge = true;
2459         }
2460       }
2461
2462       if (removeEdge) {
2463         PieceI->setEndLocation(PieceNextI->getEndLocation());
2464         path.erase(NextI);
2465         hasChanges = true;
2466         continue;
2467       }
2468     }
2469
2470     // Optimize edges for ObjC fast-enumeration loops.
2471     //
2472     // (X -> collection) -> (collection -> element)
2473     //
2474     // becomes:
2475     //
2476     // (X -> element)
2477     if (s1End == s2Start) {
2478       const ObjCForCollectionStmt *FS =
2479         dyn_cast_or_null<ObjCForCollectionStmt>(level3);
2480       if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
2481           s2End == FS->getElement()) {
2482         PieceI->setEndLocation(PieceNextI->getEndLocation());
2483         path.erase(NextI);
2484         hasChanges = true;
2485         continue;
2486       }
2487     }
2488
2489     // No changes at this index?  Move to the next one.
2490     ++I;
2491   }
2492
2493   if (!hasChanges) {
2494     // Adjust edges into subexpressions to make them more uniform
2495     // and aesthetically pleasing.
2496     addContextEdges(path, SM, PM, LC);
2497     // Remove "cyclical" edges that include one or more context edges.
2498     removeContextCycles(path, SM, PM);
2499     // Hoist edges originating from branch conditions to branches
2500     // for simple branches.
2501     simplifySimpleBranches(path);
2502     // Remove any puny edges left over after primary optimization pass.
2503     removePunyEdges(path, SM, PM);
2504     // Remove identical events.
2505     removeIdenticalEvents(path);
2506   }
2507
2508   return hasChanges;
2509 }
2510
2511 /// Drop the very first edge in a path, which should be a function entry edge.
2512 ///
2513 /// If the first edge is not a function entry edge (say, because the first
2514 /// statement had an invalid source location), this function does nothing.
2515 // FIXME: We should just generate invalid edges anyway and have the optimizer
2516 // deal with them.
2517 static void dropFunctionEntryEdge(PathPieces &Path,
2518                                   LocationContextMap &LCM,
2519                                   SourceManager &SM) {
2520   const PathDiagnosticControlFlowPiece *FirstEdge =
2521     dyn_cast<PathDiagnosticControlFlowPiece>(Path.front());
2522   if (!FirstEdge)
2523     return;
2524
2525   const Decl *D = LCM[&Path]->getDecl();
2526   PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM);
2527   if (FirstEdge->getStartLocation() != EntryLoc)
2528     return;
2529
2530   Path.pop_front();
2531 }
2532
2533
2534 //===----------------------------------------------------------------------===//
2535 // Methods for BugType and subclasses.
2536 //===----------------------------------------------------------------------===//
2537 void BugType::anchor() { }
2538
2539 void BugType::FlushReports(BugReporter &BR) {}
2540
2541 void BuiltinBug::anchor() {}
2542
2543 //===----------------------------------------------------------------------===//
2544 // Methods for BugReport and subclasses.
2545 //===----------------------------------------------------------------------===//
2546
2547 void BugReport::NodeResolver::anchor() {}
2548
2549 void BugReport::addVisitor(BugReporterVisitor* visitor) {
2550   if (!visitor)
2551     return;
2552
2553   llvm::FoldingSetNodeID ID;
2554   visitor->Profile(ID);
2555   void *InsertPos;
2556
2557   if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2558     delete visitor;
2559     return;
2560   }
2561
2562   CallbacksSet.InsertNode(visitor, InsertPos);
2563   Callbacks.push_back(visitor);
2564   ++ConfigurationChangeToken;
2565 }
2566
2567 BugReport::~BugReport() {
2568   for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
2569     delete *I;
2570   }
2571   while (!interestingSymbols.empty()) {
2572     popInterestingSymbolsAndRegions();
2573   }
2574 }
2575
2576 const Decl *BugReport::getDeclWithIssue() const {
2577   if (DeclWithIssue)
2578     return DeclWithIssue;
2579
2580   const ExplodedNode *N = getErrorNode();
2581   if (!N)
2582     return 0;
2583
2584   const LocationContext *LC = N->getLocationContext();
2585   return LC->getCurrentStackFrame()->getDecl();
2586 }
2587
2588 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2589   hash.AddPointer(&BT);
2590   hash.AddString(Description);
2591   PathDiagnosticLocation UL = getUniqueingLocation();
2592   if (UL.isValid()) {
2593     UL.Profile(hash);
2594   } else if (Location.isValid()) {
2595     Location.Profile(hash);
2596   } else {
2597     assert(ErrorNode);
2598     hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2599   }
2600
2601   for (SmallVectorImpl<SourceRange>::const_iterator I =
2602       Ranges.begin(), E = Ranges.end(); I != E; ++I) {
2603     const SourceRange range = *I;
2604     if (!range.isValid())
2605       continue;
2606     hash.AddInteger(range.getBegin().getRawEncoding());
2607     hash.AddInteger(range.getEnd().getRawEncoding());
2608   }
2609 }
2610
2611 void BugReport::markInteresting(SymbolRef sym) {
2612   if (!sym)
2613     return;
2614
2615   // If the symbol wasn't already in our set, note a configuration change.
2616   if (getInterestingSymbols().insert(sym).second)
2617     ++ConfigurationChangeToken;
2618
2619   if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
2620     getInterestingRegions().insert(meta->getRegion());
2621 }
2622
2623 void BugReport::markInteresting(const MemRegion *R) {
2624   if (!R)
2625     return;
2626
2627   // If the base region wasn't already in our set, note a configuration change.
2628   R = R->getBaseRegion();
2629   if (getInterestingRegions().insert(R).second)
2630     ++ConfigurationChangeToken;
2631
2632   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2633     getInterestingSymbols().insert(SR->getSymbol());
2634 }
2635
2636 void BugReport::markInteresting(SVal V) {
2637   markInteresting(V.getAsRegion());
2638   markInteresting(V.getAsSymbol());
2639 }
2640
2641 void BugReport::markInteresting(const LocationContext *LC) {
2642   if (!LC)
2643     return;
2644   InterestingLocationContexts.insert(LC);
2645 }
2646
2647 bool BugReport::isInteresting(SVal V) {
2648   return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2649 }
2650
2651 bool BugReport::isInteresting(SymbolRef sym) {
2652   if (!sym)
2653     return false;
2654   // We don't currently consider metadata symbols to be interesting
2655   // even if we know their region is interesting. Is that correct behavior?
2656   return getInterestingSymbols().count(sym);
2657 }
2658
2659 bool BugReport::isInteresting(const MemRegion *R) {
2660   if (!R)
2661     return false;
2662   R = R->getBaseRegion();
2663   bool b = getInterestingRegions().count(R);
2664   if (b)
2665     return true;
2666   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2667     return getInterestingSymbols().count(SR->getSymbol());
2668   return false;
2669 }
2670
2671 bool BugReport::isInteresting(const LocationContext *LC) {
2672   if (!LC)
2673     return false;
2674   return InterestingLocationContexts.count(LC);
2675 }
2676
2677 void BugReport::lazyInitializeInterestingSets() {
2678   if (interestingSymbols.empty()) {
2679     interestingSymbols.push_back(new Symbols());
2680     interestingRegions.push_back(new Regions());
2681   }
2682 }
2683
2684 BugReport::Symbols &BugReport::getInterestingSymbols() {
2685   lazyInitializeInterestingSets();
2686   return *interestingSymbols.back();
2687 }
2688
2689 BugReport::Regions &BugReport::getInterestingRegions() {
2690   lazyInitializeInterestingSets();
2691   return *interestingRegions.back();
2692 }
2693
2694 void BugReport::pushInterestingSymbolsAndRegions() {
2695   interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2696   interestingRegions.push_back(new Regions(getInterestingRegions()));
2697 }
2698
2699 void BugReport::popInterestingSymbolsAndRegions() {
2700   delete interestingSymbols.pop_back_val();
2701   delete interestingRegions.pop_back_val();
2702 }
2703
2704 const Stmt *BugReport::getStmt() const {
2705   if (!ErrorNode)
2706     return 0;
2707
2708   ProgramPoint ProgP = ErrorNode->getLocation();
2709   const Stmt *S = NULL;
2710
2711   if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2712     CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2713     if (BE->getBlock() == &Exit)
2714       S = GetPreviousStmt(ErrorNode);
2715   }
2716   if (!S)
2717     S = PathDiagnosticLocation::getStmt(ErrorNode);
2718
2719   return S;
2720 }
2721
2722 std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
2723 BugReport::getRanges() {
2724     // If no custom ranges, add the range of the statement corresponding to
2725     // the error node.
2726     if (Ranges.empty()) {
2727       if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
2728         addRange(E->getSourceRange());
2729       else
2730         return std::make_pair(ranges_iterator(), ranges_iterator());
2731     }
2732
2733     // User-specified absence of range info.
2734     if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2735       return std::make_pair(ranges_iterator(), ranges_iterator());
2736
2737     return std::make_pair(Ranges.begin(), Ranges.end());
2738 }
2739
2740 PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
2741   if (ErrorNode) {
2742     assert(!Location.isValid() &&
2743      "Either Location or ErrorNode should be specified but not both.");
2744     return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2745   } else {
2746     assert(Location.isValid());
2747     return Location;
2748   }
2749
2750   return PathDiagnosticLocation();
2751 }
2752
2753 //===----------------------------------------------------------------------===//
2754 // Methods for BugReporter and subclasses.
2755 //===----------------------------------------------------------------------===//
2756
2757 BugReportEquivClass::~BugReportEquivClass() { }
2758 GRBugReporter::~GRBugReporter() { }
2759 BugReporterData::~BugReporterData() {}
2760
2761 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2762
2763 ProgramStateManager&
2764 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2765
2766 BugReporter::~BugReporter() {
2767   FlushReports();
2768
2769   // Free the bug reports we are tracking.
2770   typedef std::vector<BugReportEquivClass *> ContTy;
2771   for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
2772        I != E; ++I) {
2773     delete *I;
2774   }
2775 }
2776
2777 void BugReporter::FlushReports() {
2778   if (BugTypes.isEmpty())
2779     return;
2780
2781   // First flush the warnings for each BugType.  This may end up creating new
2782   // warnings and new BugTypes.
2783   // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2784   // Turn NSErrorChecker into a proper checker and remove this.
2785   SmallVector<const BugType*, 16> bugTypes;
2786   for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
2787     bugTypes.push_back(*I);
2788   for (SmallVectorImpl<const BugType *>::iterator
2789          I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
2790     const_cast<BugType*>(*I)->FlushReports(*this);
2791
2792   // We need to flush reports in deterministic order to ensure the order
2793   // of the reports is consistent between runs.
2794   typedef std::vector<BugReportEquivClass *> ContVecTy;
2795   for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end();
2796        EI != EE; ++EI){
2797     BugReportEquivClass& EQ = **EI;
2798     FlushReport(EQ);
2799   }
2800
2801   // BugReporter owns and deletes only BugTypes created implicitly through
2802   // EmitBasicReport.
2803   // FIXME: There are leaks from checkers that assume that the BugTypes they
2804   // create will be destroyed by the BugReporter.
2805   for (llvm::StringMap<BugType*>::iterator
2806          I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
2807     delete I->second;
2808
2809   // Remove all references to the BugType objects.
2810   BugTypes = F.getEmptySet();
2811 }
2812
2813 //===----------------------------------------------------------------------===//
2814 // PathDiagnostics generation.
2815 //===----------------------------------------------------------------------===//
2816
2817 namespace {
2818 /// A wrapper around a report graph, which contains only a single path, and its
2819 /// node maps.
2820 class ReportGraph {
2821 public:
2822   InterExplodedGraphMap BackMap;
2823   OwningPtr<ExplodedGraph> Graph;
2824   const ExplodedNode *ErrorNode;
2825   size_t Index;
2826 };
2827
2828 /// A wrapper around a trimmed graph and its node maps.
2829 class TrimmedGraph {
2830   InterExplodedGraphMap InverseMap;
2831
2832   typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy;
2833   PriorityMapTy PriorityMap;
2834
2835   typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair;
2836   SmallVector<NodeIndexPair, 32> ReportNodes;
2837
2838   OwningPtr<ExplodedGraph> G;
2839
2840   /// A helper class for sorting ExplodedNodes by priority.
2841   template <bool Descending>
2842   class PriorityCompare {
2843     const PriorityMapTy &PriorityMap;
2844
2845   public:
2846     PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2847
2848     bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2849       PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2850       PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2851       PriorityMapTy::const_iterator E = PriorityMap.end();
2852
2853       if (LI == E)
2854         return Descending;
2855       if (RI == E)
2856         return !Descending;
2857
2858       return Descending ? LI->second > RI->second
2859                         : LI->second < RI->second;
2860     }
2861
2862     bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2863       return (*this)(LHS.first, RHS.first);
2864     }
2865   };
2866
2867 public:
2868   TrimmedGraph(const ExplodedGraph *OriginalGraph,
2869                ArrayRef<const ExplodedNode *> Nodes);
2870
2871   bool popNextReportGraph(ReportGraph &GraphWrapper);
2872 };
2873 }
2874
2875 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2876                            ArrayRef<const ExplodedNode *> Nodes) {
2877   // The trimmed graph is created in the body of the constructor to ensure
2878   // that the DenseMaps have been initialized already.
2879   InterExplodedGraphMap ForwardMap;
2880   G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap));
2881
2882   // Find the (first) error node in the trimmed graph.  We just need to consult
2883   // the node map which maps from nodes in the original graph to nodes
2884   // in the new graph.
2885   llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2886
2887   for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2888     if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2889       ReportNodes.push_back(std::make_pair(NewNode, i));
2890       RemainingNodes.insert(NewNode);
2891     }
2892   }
2893
2894   assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2895
2896   // Perform a forward BFS to find all the shortest paths.
2897   std::queue<const ExplodedNode *> WS;
2898
2899   assert(G->num_roots() == 1);
2900   WS.push(*G->roots_begin());
2901   unsigned Priority = 0;
2902
2903   while (!WS.empty()) {
2904     const ExplodedNode *Node = WS.front();
2905     WS.pop();
2906
2907     PriorityMapTy::iterator PriorityEntry;
2908     bool IsNew;
2909     llvm::tie(PriorityEntry, IsNew) =
2910       PriorityMap.insert(std::make_pair(Node, Priority));
2911     ++Priority;
2912
2913     if (!IsNew) {
2914       assert(PriorityEntry->second <= Priority);
2915       continue;
2916     }
2917
2918     if (RemainingNodes.erase(Node))
2919       if (RemainingNodes.empty())
2920         break;
2921
2922     for (ExplodedNode::const_pred_iterator I = Node->succ_begin(),
2923                                            E = Node->succ_end();
2924          I != E; ++I)
2925       WS.push(*I);
2926   }
2927
2928   // Sort the error paths from longest to shortest.
2929   std::sort(ReportNodes.begin(), ReportNodes.end(),
2930             PriorityCompare<true>(PriorityMap));
2931 }
2932
2933 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2934   if (ReportNodes.empty())
2935     return false;
2936
2937   const ExplodedNode *OrigN;
2938   llvm::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2939   assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2940          "error node not accessible from root");
2941
2942   // Create a new graph with a single path.  This is the graph
2943   // that will be returned to the caller.
2944   ExplodedGraph *GNew = new ExplodedGraph();
2945   GraphWrapper.Graph.reset(GNew);
2946   GraphWrapper.BackMap.clear();
2947
2948   // Now walk from the error node up the BFS path, always taking the
2949   // predeccessor with the lowest number.
2950   ExplodedNode *Succ = 0;
2951   while (true) {
2952     // Create the equivalent node in the new graph with the same state
2953     // and location.
2954     ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(),
2955                                        OrigN->isSink());
2956
2957     // Store the mapping to the original node.
2958     InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2959     assert(IMitr != InverseMap.end() && "No mapping to original node.");
2960     GraphWrapper.BackMap[NewN] = IMitr->second;
2961
2962     // Link up the new node with the previous node.
2963     if (Succ)
2964       Succ->addPredecessor(NewN, *GNew);
2965     else
2966       GraphWrapper.ErrorNode = NewN;
2967
2968     Succ = NewN;
2969
2970     // Are we at the final node?
2971     if (OrigN->pred_empty()) {
2972       GNew->addRoot(NewN);
2973       break;
2974     }
2975
2976     // Find the next predeccessor node.  We choose the node that is marked
2977     // with the lowest BFS number.
2978     OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2979                           PriorityCompare<false>(PriorityMap));
2980   }
2981
2982   return true;
2983 }
2984
2985
2986 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2987 ///  and collapses PathDiagosticPieces that are expanded by macros.
2988 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2989   typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>,
2990                                 SourceLocation> > MacroStackTy;
2991
2992   typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> >
2993           PiecesTy;
2994
2995   MacroStackTy MacroStack;
2996   PiecesTy Pieces;
2997
2998   for (PathPieces::const_iterator I = path.begin(), E = path.end();
2999        I!=E; ++I) {
3000
3001     PathDiagnosticPiece *piece = I->getPtr();
3002
3003     // Recursively compact calls.
3004     if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
3005       CompactPathDiagnostic(call->path, SM);
3006     }
3007
3008     // Get the location of the PathDiagnosticPiece.
3009     const FullSourceLoc Loc = piece->getLocation().asLocation();
3010
3011     // Determine the instantiation location, which is the location we group
3012     // related PathDiagnosticPieces.
3013     SourceLocation InstantiationLoc = Loc.isMacroID() ?
3014                                       SM.getExpansionLoc(Loc) :
3015                                       SourceLocation();
3016
3017     if (Loc.isFileID()) {
3018       MacroStack.clear();
3019       Pieces.push_back(piece);
3020       continue;
3021     }
3022
3023     assert(Loc.isMacroID());
3024
3025     // Is the PathDiagnosticPiece within the same macro group?
3026     if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
3027       MacroStack.back().first->subPieces.push_back(piece);
3028       continue;
3029     }
3030
3031     // We aren't in the same group.  Are we descending into a new macro
3032     // or are part of an old one?
3033     IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup;
3034
3035     SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
3036                                           SM.getExpansionLoc(Loc) :
3037                                           SourceLocation();
3038
3039     // Walk the entire macro stack.
3040     while (!MacroStack.empty()) {
3041       if (InstantiationLoc == MacroStack.back().second) {
3042         MacroGroup = MacroStack.back().first;
3043         break;
3044       }
3045
3046       if (ParentInstantiationLoc == MacroStack.back().second) {
3047         MacroGroup = MacroStack.back().first;
3048         break;
3049       }
3050
3051       MacroStack.pop_back();
3052     }
3053
3054     if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
3055       // Create a new macro group and add it to the stack.
3056       PathDiagnosticMacroPiece *NewGroup =
3057         new PathDiagnosticMacroPiece(
3058           PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
3059
3060       if (MacroGroup)
3061         MacroGroup->subPieces.push_back(NewGroup);
3062       else {
3063         assert(InstantiationLoc.isFileID());
3064         Pieces.push_back(NewGroup);
3065       }
3066
3067       MacroGroup = NewGroup;
3068       MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
3069     }
3070
3071     // Finally, add the PathDiagnosticPiece to the group.
3072     MacroGroup->subPieces.push_back(piece);
3073   }
3074
3075   // Now take the pieces and construct a new PathDiagnostic.
3076   path.clear();
3077
3078   for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I)
3079     path.push_back(*I);
3080 }
3081
3082 bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
3083                                            PathDiagnosticConsumer &PC,
3084                                            ArrayRef<BugReport *> &bugReports) {
3085   assert(!bugReports.empty());
3086
3087   bool HasValid = false;
3088   bool HasInvalid = false;
3089   SmallVector<const ExplodedNode *, 32> errorNodes;
3090   for (ArrayRef<BugReport*>::iterator I = bugReports.begin(),
3091                                       E = bugReports.end(); I != E; ++I) {
3092     if ((*I)->isValid()) {
3093       HasValid = true;
3094       errorNodes.push_back((*I)->getErrorNode());
3095     } else {
3096       // Keep the errorNodes list in sync with the bugReports list.
3097       HasInvalid = true;
3098       errorNodes.push_back(0);
3099     }
3100   }
3101
3102   // If all the reports have been marked invalid by a previous path generation,
3103   // we're done.
3104   if (!HasValid)
3105     return false;
3106
3107   typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme;
3108   PathGenerationScheme ActiveScheme = PC.getGenerationScheme();
3109
3110   if (ActiveScheme == PathDiagnosticConsumer::Extensive) {
3111     AnalyzerOptions &options = getAnalyzerOptions();
3112     if (options.getBooleanOption("path-diagnostics-alternate", true)) {
3113       ActiveScheme = PathDiagnosticConsumer::AlternateExtensive;
3114     }
3115   }
3116
3117   TrimmedGraph TrimG(&getGraph(), errorNodes);
3118   ReportGraph ErrorGraph;
3119
3120   while (TrimG.popNextReportGraph(ErrorGraph)) {
3121     // Find the BugReport with the original location.
3122     assert(ErrorGraph.Index < bugReports.size());
3123     BugReport *R = bugReports[ErrorGraph.Index];
3124     assert(R && "No original report found for sliced graph.");
3125     assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
3126
3127     // Start building the path diagnostic...
3128     PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
3129     const ExplodedNode *N = ErrorGraph.ErrorNode;
3130
3131     // Register additional node visitors.
3132     R->addVisitor(new NilReceiverBRVisitor());
3133     R->addVisitor(new ConditionBRVisitor());
3134     R->addVisitor(new LikelyFalsePositiveSuppressionBRVisitor());
3135
3136     BugReport::VisitorList visitors;
3137     unsigned origReportConfigToken, finalReportConfigToken;
3138     LocationContextMap LCM;
3139
3140     // While generating diagnostics, it's possible the visitors will decide
3141     // new symbols and regions are interesting, or add other visitors based on
3142     // the information they find. If they do, we need to regenerate the path
3143     // based on our new report configuration.
3144     do {
3145       // Get a clean copy of all the visitors.
3146       for (BugReport::visitor_iterator I = R->visitor_begin(),
3147                                        E = R->visitor_end(); I != E; ++I)
3148         visitors.push_back((*I)->clone());
3149
3150       // Clear out the active path from any previous work.
3151       PD.resetPath();
3152       origReportConfigToken = R->getConfigurationChangeToken();
3153
3154       // Generate the very last diagnostic piece - the piece is visible before
3155       // the trace is expanded.
3156       PathDiagnosticPiece *LastPiece = 0;
3157       for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
3158           I != E; ++I) {
3159         if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
3160           assert (!LastPiece &&
3161               "There can only be one final piece in a diagnostic.");
3162           LastPiece = Piece;
3163         }
3164       }
3165
3166       if (ActiveScheme != PathDiagnosticConsumer::None) {
3167         if (!LastPiece)
3168           LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
3169         assert(LastPiece);
3170         PD.setEndOfPath(LastPiece);
3171       }
3172
3173       // Make sure we get a clean location context map so we don't
3174       // hold onto old mappings.
3175       LCM.clear();
3176
3177       switch (ActiveScheme) {
3178       case PathDiagnosticConsumer::AlternateExtensive:
3179         GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3180         break;
3181       case PathDiagnosticConsumer::Extensive:
3182         GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3183         break;
3184       case PathDiagnosticConsumer::Minimal:
3185         GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors);
3186         break;
3187       case PathDiagnosticConsumer::None:
3188         GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors);
3189         break;
3190       }
3191
3192       // Clean up the visitors we used.
3193       llvm::DeleteContainerPointers(visitors);
3194
3195       // Did anything change while generating this path?
3196       finalReportConfigToken = R->getConfigurationChangeToken();
3197     } while (finalReportConfigToken != origReportConfigToken);
3198
3199     if (!R->isValid())
3200       continue;
3201
3202     // Finally, prune the diagnostic path of uninteresting stuff.
3203     if (!PD.path.empty()) {
3204       if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) {
3205         bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);
3206         assert(stillHasNotes);
3207         (void)stillHasNotes;
3208       }
3209
3210       // Redirect all call pieces to have valid locations.
3211       adjustCallLocations(PD.getMutablePieces());
3212       removePiecesWithInvalidLocations(PD.getMutablePieces());
3213
3214       if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) {
3215         SourceManager &SM = getSourceManager();
3216
3217         // Reduce the number of edges from a very conservative set
3218         // to an aesthetically pleasing subset that conveys the
3219         // necessary information.
3220         OptimizedCallsSet OCS;
3221         while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {}
3222
3223         // Drop the very first function-entry edge. It's not really necessary
3224         // for top-level functions.
3225         dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM);
3226       }
3227
3228       // Remove messages that are basically the same, and edges that may not
3229       // make sense.
3230       // We have to do this after edge optimization in the Extensive mode.
3231       removeRedundantMsgs(PD.getMutablePieces());
3232       removeEdgesToDefaultInitializers(PD.getMutablePieces());
3233     }
3234
3235     // We found a report and didn't suppress it.
3236     return true;
3237   }
3238
3239   // We suppressed all the reports in this equivalence class.
3240   assert(!HasInvalid && "Inconsistent suppression");
3241   (void)HasInvalid;
3242   return false;
3243 }
3244
3245 void BugReporter::Register(BugType *BT) {
3246   BugTypes = F.add(BugTypes, BT);
3247 }
3248
3249 void BugReporter::emitReport(BugReport* R) {
3250   // Defensive checking: throw the bug away if it comes from a BodyFarm-
3251   // generated body. We do this very early because report processing relies
3252   // on the report's location being valid.
3253   // FIXME: Valid bugs can occur in BodyFarm-generated bodies, so really we
3254   // need to just find a reasonable location like we do later on with the path
3255   // pieces.
3256   if (const ExplodedNode *E = R->getErrorNode()) {
3257     const LocationContext *LCtx = E->getLocationContext();
3258     if (LCtx->getAnalysisDeclContext()->isBodyAutosynthesized())
3259       return;
3260   }
3261
3262   bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid();
3263   assert(ValidSourceLoc);
3264   // If we mess up in a release build, we'd still prefer to just drop the bug
3265   // instead of trying to go on.
3266   if (!ValidSourceLoc)
3267     return;
3268
3269   // Compute the bug report's hash to determine its equivalence class.
3270   llvm::FoldingSetNodeID ID;
3271   R->Profile(ID);
3272
3273   // Lookup the equivance class.  If there isn't one, create it.
3274   BugType& BT = R->getBugType();
3275   Register(&BT);
3276   void *InsertPos;
3277   BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
3278
3279   if (!EQ) {
3280     EQ = new BugReportEquivClass(R);
3281     EQClasses.InsertNode(EQ, InsertPos);
3282     EQClassesVector.push_back(EQ);
3283   }
3284   else
3285     EQ->AddReport(R);
3286 }
3287
3288
3289 //===----------------------------------------------------------------------===//
3290 // Emitting reports in equivalence classes.
3291 //===----------------------------------------------------------------------===//
3292
3293 namespace {
3294 struct FRIEC_WLItem {
3295   const ExplodedNode *N;
3296   ExplodedNode::const_succ_iterator I, E;
3297
3298   FRIEC_WLItem(const ExplodedNode *n)
3299   : N(n), I(N->succ_begin()), E(N->succ_end()) {}
3300 };
3301 }
3302
3303 static BugReport *
3304 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
3305                              SmallVectorImpl<BugReport*> &bugReports) {
3306
3307   BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
3308   assert(I != E);
3309   BugType& BT = I->getBugType();
3310
3311   // If we don't need to suppress any of the nodes because they are
3312   // post-dominated by a sink, simply add all the nodes in the equivalence class
3313   // to 'Nodes'.  Any of the reports will serve as a "representative" report.
3314   if (!BT.isSuppressOnSink()) {
3315     BugReport *R = I;
3316     for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
3317       const ExplodedNode *N = I->getErrorNode();
3318       if (N) {
3319         R = I;
3320         bugReports.push_back(R);
3321       }
3322     }
3323     return R;
3324   }
3325
3326   // For bug reports that should be suppressed when all paths are post-dominated
3327   // by a sink node, iterate through the reports in the equivalence class
3328   // until we find one that isn't post-dominated (if one exists).  We use a
3329   // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
3330   // this as a recursive function, but we don't want to risk blowing out the
3331   // stack for very long paths.
3332   BugReport *exampleReport = 0;
3333
3334   for (; I != E; ++I) {
3335     const ExplodedNode *errorNode = I->getErrorNode();
3336
3337     if (!errorNode)
3338       continue;
3339     if (errorNode->isSink()) {
3340       llvm_unreachable(
3341            "BugType::isSuppressSink() should not be 'true' for sink end nodes");
3342     }
3343     // No successors?  By definition this nodes isn't post-dominated by a sink.
3344     if (errorNode->succ_empty()) {
3345       bugReports.push_back(I);
3346       if (!exampleReport)
3347         exampleReport = I;
3348       continue;
3349     }
3350
3351     // At this point we know that 'N' is not a sink and it has at least one
3352     // successor.  Use a DFS worklist to find a non-sink end-of-path node.
3353     typedef FRIEC_WLItem WLItem;
3354     typedef SmallVector<WLItem, 10> DFSWorkList;
3355     llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
3356
3357     DFSWorkList WL;
3358     WL.push_back(errorNode);
3359     Visited[errorNode] = 1;
3360
3361     while (!WL.empty()) {
3362       WLItem &WI = WL.back();
3363       assert(!WI.N->succ_empty());
3364
3365       for (; WI.I != WI.E; ++WI.I) {
3366         const ExplodedNode *Succ = *WI.I;
3367         // End-of-path node?
3368         if (Succ->succ_empty()) {
3369           // If we found an end-of-path node that is not a sink.
3370           if (!Succ->isSink()) {
3371             bugReports.push_back(I);
3372             if (!exampleReport)
3373               exampleReport = I;
3374             WL.clear();
3375             break;
3376           }
3377           // Found a sink?  Continue on to the next successor.
3378           continue;
3379         }
3380         // Mark the successor as visited.  If it hasn't been explored,
3381         // enqueue it to the DFS worklist.
3382         unsigned &mark = Visited[Succ];
3383         if (!mark) {
3384           mark = 1;
3385           WL.push_back(Succ);
3386           break;
3387         }
3388       }
3389
3390       // The worklist may have been cleared at this point.  First
3391       // check if it is empty before checking the last item.
3392       if (!WL.empty() && &WL.back() == &WI)
3393         WL.pop_back();
3394     }
3395   }
3396
3397   // ExampleReport will be NULL if all the nodes in the equivalence class
3398   // were post-dominated by sinks.
3399   return exampleReport;
3400 }
3401
3402 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
3403   SmallVector<BugReport*, 10> bugReports;
3404   BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
3405   if (exampleReport) {
3406     const PathDiagnosticConsumers &C = getPathDiagnosticConsumers();
3407     for (PathDiagnosticConsumers::const_iterator I=C.begin(),
3408                                                  E=C.end(); I != E; ++I) {
3409       FlushReport(exampleReport, **I, bugReports);
3410     }
3411   }
3412 }
3413
3414 void BugReporter::FlushReport(BugReport *exampleReport,
3415                               PathDiagnosticConsumer &PD,
3416                               ArrayRef<BugReport*> bugReports) {
3417
3418   // FIXME: Make sure we use the 'R' for the path that was actually used.
3419   // Probably doesn't make a difference in practice.
3420   BugType& BT = exampleReport->getBugType();
3421
3422   OwningPtr<PathDiagnostic>
3423     D(new PathDiagnostic(exampleReport->getDeclWithIssue(),
3424                          exampleReport->getBugType().getName(),
3425                          exampleReport->getDescription(),
3426                          exampleReport->getShortDescription(/*Fallback=*/false),
3427                          BT.getCategory(),
3428                          exampleReport->getUniqueingLocation(),
3429                          exampleReport->getUniqueingDecl()));
3430
3431   MaxBugClassSize = std::max(bugReports.size(),
3432                              static_cast<size_t>(MaxBugClassSize));
3433
3434   // Generate the full path diagnostic, using the generation scheme
3435   // specified by the PathDiagnosticConsumer. Note that we have to generate
3436   // path diagnostics even for consumers which do not support paths, because
3437   // the BugReporterVisitors may mark this bug as a false positive.
3438   if (!bugReports.empty())
3439     if (!generatePathDiagnostic(*D.get(), PD, bugReports))
3440       return;
3441
3442   MaxValidBugClassSize = std::max(bugReports.size(),
3443                                   static_cast<size_t>(MaxValidBugClassSize));
3444
3445   // Examine the report and see if the last piece is in a header. Reset the
3446   // report location to the last piece in the main source file.
3447   AnalyzerOptions& Opts = getAnalyzerOptions();
3448   if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll)
3449     D->resetDiagnosticLocationToMainFile();
3450
3451   // If the path is empty, generate a single step path with the location
3452   // of the issue.
3453   if (D->path.empty()) {
3454     PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
3455     PathDiagnosticPiece *piece =
3456       new PathDiagnosticEventPiece(L, exampleReport->getDescription());
3457     BugReport::ranges_iterator Beg, End;
3458     llvm::tie(Beg, End) = exampleReport->getRanges();
3459     for ( ; Beg != End; ++Beg)
3460       piece->addRange(*Beg);
3461     D->setEndOfPath(piece);
3462   }
3463
3464   // Get the meta data.
3465   const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
3466   for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
3467                                                 e = Meta.end(); i != e; ++i) {
3468     D->addMeta(*i);
3469   }
3470
3471   PD.HandlePathDiagnostic(D.take());
3472 }
3473
3474 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3475                                   StringRef name,
3476                                   StringRef category,
3477                                   StringRef str, PathDiagnosticLocation Loc,
3478                                   ArrayRef<SourceRange> Ranges) {
3479
3480   // 'BT' is owned by BugReporter.
3481   BugType *BT = getBugTypeForName(name, category);
3482   BugReport *R = new BugReport(*BT, str, Loc);
3483   R->setDeclWithIssue(DeclWithIssue);
3484   for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
3485        I != E; ++I)
3486     R->addRange(*I);
3487   emitReport(R);
3488 }
3489
3490 BugType *BugReporter::getBugTypeForName(StringRef name,
3491                                         StringRef category) {
3492   SmallString<136> fullDesc;
3493   llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
3494   llvm::StringMapEntry<BugType *> &
3495       entry = StrBugTypes.GetOrCreateValue(fullDesc);
3496   BugType *BT = entry.getValue();
3497   if (!BT) {
3498     BT = new BugType(name, category);
3499     entry.setValue(BT);
3500   }
3501   return BT;
3502 }
3503
3504
3505 void PathPieces::dump() const {
3506   unsigned index = 0;
3507   for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
3508     llvm::errs() << "[" << index++ << "]  ";
3509     (*I)->dump();
3510     llvm::errs() << "\n";
3511   }
3512 }
3513
3514 void PathDiagnosticCallPiece::dump() const {
3515   llvm::errs() << "CALL\n--------------\n";
3516
3517   if (const Stmt *SLoc = getLocStmt(getLocation()))
3518     SLoc->dump();
3519   else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee()))
3520     llvm::errs() << *ND << "\n";
3521   else
3522     getLocation().dump();
3523 }
3524
3525 void PathDiagnosticEventPiece::dump() const {
3526   llvm::errs() << "EVENT\n--------------\n";
3527   llvm::errs() << getString() << "\n";
3528   llvm::errs() << " ---- at ----\n";
3529   getLocation().dump();
3530 }
3531
3532 void PathDiagnosticControlFlowPiece::dump() const {
3533   llvm::errs() << "CONTROL\n--------------\n";
3534   getStartLocation().dump();
3535   llvm::errs() << " ---- to ----\n";
3536   getEndLocation().dump();
3537 }
3538
3539 void PathDiagnosticMacroPiece::dump() const {
3540   llvm::errs() << "MACRO\n--------------\n";
3541   // FIXME: Print which macro is being invoked.
3542 }
3543
3544 void PathDiagnosticLocation::dump() const {
3545   if (!isValid()) {
3546     llvm::errs() << "<INVALID>\n";
3547     return;
3548   }
3549
3550   switch (K) {
3551   case RangeK:
3552     // FIXME: actually print the range.
3553     llvm::errs() << "<range>\n";
3554     break;
3555   case SingleLocK:
3556     asLocation().dump();
3557     llvm::errs() << "\n";
3558     break;
3559   case StmtK:
3560     if (S)
3561       S->dump();
3562     else
3563       llvm::errs() << "<NULL STMT>\n";
3564     break;
3565   case DeclK:
3566     if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
3567       llvm::errs() << *ND << "\n";
3568     else if (isa<BlockDecl>(D))
3569       // FIXME: Make this nicer.
3570       llvm::errs() << "<block>\n";
3571     else if (D)
3572       llvm::errs() << "<unknown decl>\n";
3573     else
3574       llvm::errs() << "<NULL DECL>\n";
3575     break;
3576   }
3577 }