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

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