lib/StaticAnalyzer/Core/PathDiagnostic.cpp

   1 //===- PathDiagnostic.cpp - Path-Specific Diagnostic Handling -------------===//
   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 the PathDiagnostic-related interfaces.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
  15 #include "clang/AST/Decl.h"
  16 #include "clang/AST/DeclBase.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/DeclObjC.h"
  19 #include "clang/AST/DeclTemplate.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/ExprCXX.h"
  22 #include "clang/AST/OperationKinds.h"
  23 #include "clang/AST/ParentMap.h"
  24 #include "clang/AST/Stmt.h"
  25 #include "clang/AST/Type.h"
  26 #include "clang/Analysis/AnalysisDeclContext.h"
  27 #include "clang/Analysis/CFG.h"
  28 #include "clang/Analysis/ProgramPoint.h"
  29 #include "clang/Basic/FileManager.h"
  30 #include "clang/Basic/LLVM.h"
  31 #include "clang/Basic/SourceLocation.h"
  32 #include "clang/Basic/SourceManager.h"
  33 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  34 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  35 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  36 #include "llvm/ADT/ArrayRef.h"
  37 #include "llvm/ADT/FoldingSet.h"
  38 #include "llvm/ADT/None.h"
  39 #include "llvm/ADT/Optional.h"
  40 #include "llvm/ADT/STLExtras.h"
  41 #include "llvm/ADT/SmallString.h"
  42 #include "llvm/ADT/SmallVector.h"
  43 #include "llvm/ADT/StringExtras.h"
  44 #include "llvm/ADT/StringRef.h"
  45 #include "llvm/Support/Casting.h"
  46 #include "llvm/Support/ErrorHandling.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include <cassert>
  49 #include <cstring>
  50 #include <memory>
  51 #include <utility>
  52 #include <vector>
  53
  54 using namespace clang;
  55 using namespace ento;
  56
  57 bool PathDiagnosticMacroPiece::containsEvent() const {
  58   for (const auto &P : subPieces) {
  59     if (isa<PathDiagnosticEventPiece>(*P))
  60       return true;
  61     if (const auto *MP = dyn_cast<PathDiagnosticMacroPiece>(P.get()))
  62       if (MP->containsEvent())
  63         return true;
  64   }
  65   return false;
  66 }
  67
  68 static StringRef StripTrailingDots(StringRef s) {
  69   for (StringRef::size_type i = s.size(); i != 0; --i)
  70     if (s[i - 1] != '.')
  71       return s.substr(0, i);
  72   return {};
  73 }
  74
  75 PathDiagnosticPiece::PathDiagnosticPiece(StringRef s,
  76                                          Kind k, DisplayHint hint)
  77     : str(StripTrailingDots(s)), kind(k), Hint(hint) {}
  78
  79 PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint)
  80     : kind(k), Hint(hint) {}
  81
  82 PathDiagnosticPiece::~PathDiagnosticPiece() = default;
  83
  84 PathDiagnosticEventPiece::~PathDiagnosticEventPiece() = default;
  85
  86 PathDiagnosticCallPiece::~PathDiagnosticCallPiece() = default;
  87
  88 PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() = default;
  89
  90 PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() = default;
  91
  92 PathDiagnosticNotePiece::~PathDiagnosticNotePiece() = default;
  93
  94 void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current,
  95                            bool ShouldFlattenMacros) const {
  96   for (auto &Piece : *this) {
  97     switch (Piece->getKind()) {
  98     case PathDiagnosticPiece::Call: {
  99       auto &Call = cast<PathDiagnosticCallPiece>(*Piece);
 100       if (auto CallEnter = Call.getCallEnterEvent())
 101         Current.push_back(std::move(CallEnter));
 102       Call.path.flattenTo(Primary, Primary, ShouldFlattenMacros);
 103       if (auto callExit = Call.getCallExitEvent())
 104         Current.push_back(std::move(callExit));
 105       break;
 106     }
 107     case PathDiagnosticPiece::Macro: {
 108       auto &Macro = cast<PathDiagnosticMacroPiece>(*Piece);
 109       if (ShouldFlattenMacros) {
 110         Macro.subPieces.flattenTo(Primary, Primary, ShouldFlattenMacros);
 111       } else {
 112         Current.push_back(Piece);
 113         PathPieces NewPath;
 114         Macro.subPieces.flattenTo(Primary, NewPath, ShouldFlattenMacros);
 115         // FIXME: This probably shouldn't mutate the original path piece.
 116         Macro.subPieces = NewPath;
 117       }
 118       break;
 119     }
 120     case PathDiagnosticPiece::Event:
 121     case PathDiagnosticPiece::ControlFlow:
 122     case PathDiagnosticPiece::Note:
 123       Current.push_back(Piece);
 124       break;
 125     }
 126   }
 127 }
 128
 129 PathDiagnostic::~PathDiagnostic() = default;
 130
 131 PathDiagnostic::PathDiagnostic(
 132     StringRef CheckName, const Decl *declWithIssue, StringRef bugtype,
 133     StringRef verboseDesc, StringRef shortDesc, StringRef category,
 134     PathDiagnosticLocation LocationToUnique, const Decl *DeclToUnique,
 135     std::unique_ptr<FilesToLineNumsMap> ExecutedLines)
 136     : CheckName(CheckName), DeclWithIssue(declWithIssue),
 137       BugType(StripTrailingDots(bugtype)),
 138       VerboseDesc(StripTrailingDots(verboseDesc)),
 139       ShortDesc(StripTrailingDots(shortDesc)),
 140       Category(StripTrailingDots(category)), UniqueingLoc(LocationToUnique),
 141       UniqueingDecl(DeclToUnique), ExecutedLines(std::move(ExecutedLines)),
 142       path(pathImpl) {}
 143
 144 static PathDiagnosticCallPiece *
 145 getFirstStackedCallToHeaderFile(PathDiagnosticCallPiece *CP,
 146                                 const SourceManager &SMgr) {
 147   SourceLocation CallLoc = CP->callEnter.asLocation();
 148
 149   // If the call is within a macro, don't do anything (for now).
 150   if (CallLoc.isMacroID())
 151     return nullptr;
 152
 153   assert(AnalysisManager::isInCodeFile(CallLoc, SMgr) &&
 154          "The call piece should not be in a header file.");
 155
 156   // Check if CP represents a path through a function outside of the main file.
 157   if (!AnalysisManager::isInCodeFile(CP->callEnterWithin.asLocation(), SMgr))
 158     return CP;
 159
 160   const PathPieces &Path = CP->path;
 161   if (Path.empty())
 162     return nullptr;
 163
 164   // Check if the last piece in the callee path is a call to a function outside
 165   // of the main file.
 166   if (auto *CPInner = dyn_cast<PathDiagnosticCallPiece>(Path.back().get()))
 167     return getFirstStackedCallToHeaderFile(CPInner, SMgr);
 168
 169   // Otherwise, the last piece is in the main file.
 170   return nullptr;
 171 }
 172
 173 void PathDiagnostic::resetDiagnosticLocationToMainFile() {
 174   if (path.empty())
 175     return;
 176
 177   PathDiagnosticPiece *LastP = path.back().get();
 178   assert(LastP);
 179   const SourceManager &SMgr = LastP->getLocation().getManager();
 180
 181   // We only need to check if the report ends inside headers, if the last piece
 182   // is a call piece.
 183   if (auto *CP = dyn_cast<PathDiagnosticCallPiece>(LastP)) {
 184     CP = getFirstStackedCallToHeaderFile(CP, SMgr);
 185     if (CP) {
 186       // Mark the piece.
 187        CP->setAsLastInMainSourceFile();
 188
 189       // Update the path diagnostic message.
 190       const auto *ND = dyn_cast<NamedDecl>(CP->getCallee());
 191       if (ND) {
 192         SmallString<200> buf;
 193         llvm::raw_svector_ostream os(buf);
 194         os << " (within a call to '" << ND->getDeclName() << "')";
 195         appendToDesc(os.str());
 196       }
 197
 198       // Reset the report containing declaration and location.
 199       DeclWithIssue = CP->getCaller();
 200       Loc = CP->getLocation();
 201
 202       return;
 203     }
 204   }
 205 }
 206
 207 void PathDiagnosticConsumer::anchor() {}
 208
 209 PathDiagnosticConsumer::~PathDiagnosticConsumer() {
 210   // Delete the contents of the FoldingSet if it isn't empty already.
 211   for (auto &Diag : Diags)
 212     delete &Diag;
 213 }
 214
 215 void PathDiagnosticConsumer::HandlePathDiagnostic(
 216     std::unique_ptr<PathDiagnostic> D) {
 217   if (!D || D->path.empty())
 218     return;
 219
 220   // We need to flatten the locations (convert Stmt* to locations) because
 221   // the referenced statements may be freed by the time the diagnostics
 222   // are emitted.
 223   D->flattenLocations();
 224
 225   // If the PathDiagnosticConsumer does not support diagnostics that
 226   // cross file boundaries, prune out such diagnostics now.
 227   if (!supportsCrossFileDiagnostics()) {
 228     // Verify that the entire path is from the same FileID.
 229     FileID FID;
 230     const SourceManager &SMgr = D->path.front()->getLocation().getManager();
 231     SmallVector<const PathPieces *, 5> WorkList;
 232     WorkList.push_back(&D->path);
 233     SmallString<128> buf;
 234     llvm::raw_svector_ostream warning(buf);
 235     warning << "warning: Path diagnostic report is not generated. Current "
 236             << "output format does not support diagnostics that cross file "
 237             << "boundaries. Refer to --analyzer-output for valid output "
 238             << "formats\n";
 239
 240     while (!WorkList.empty()) {
 241       const PathPieces &path = *WorkList.pop_back_val();
 242
 243       for (const auto &I : path) {
 244         const PathDiagnosticPiece *piece = I.get();
 245         FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc();
 246
 247         if (FID.isInvalid()) {
 248           FID = SMgr.getFileID(L);
 249         } else if (SMgr.getFileID(L) != FID) {
 250           llvm::errs() << warning.str();
 251           return;
 252         }
 253
 254         // Check the source ranges.
 255         ArrayRef<SourceRange> Ranges = piece->getRanges();
 256         for (const auto &I : Ranges) {
 257           SourceLocation L = SMgr.getExpansionLoc(I.getBegin());
 258           if (!L.isFileID() || SMgr.getFileID(L) != FID) {
 259             llvm::errs() << warning.str();
 260             return;
 261           }
 262           L = SMgr.getExpansionLoc(I.getEnd());
 263           if (!L.isFileID() || SMgr.getFileID(L) != FID) {
 264             llvm::errs() << warning.str();
 265             return;
 266           }
 267         }
 268
 269         if (const auto *call = dyn_cast<PathDiagnosticCallPiece>(piece))
 270           WorkList.push_back(&call->path);
 271         else if (const auto *macro = dyn_cast<PathDiagnosticMacroPiece>(piece))
 272           WorkList.push_back(&macro->subPieces);
 273       }
 274     }
 275
 276     if (FID.isInvalid())
 277       return; // FIXME: Emit a warning?
 278   }
 279
 280   // Profile the node to see if we already have something matching it
 281   llvm::FoldingSetNodeID profile;
 282   D->Profile(profile);
 283   void *InsertPos = nullptr;
 284
 285   if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) {
 286     // Keep the PathDiagnostic with the shorter path.
 287     // Note, the enclosing routine is called in deterministic order, so the
 288     // results will be consistent between runs (no reason to break ties if the
 289     // size is the same).
 290     const unsigned orig_size = orig->full_size();
 291     const unsigned new_size = D->full_size();
 292     if (orig_size <= new_size)
 293       return;
 294
 295     assert(orig != D.get());
 296     Diags.RemoveNode(orig);
 297     delete orig;
 298   }
 299
 300   Diags.InsertNode(D.release());
 301 }
 302
 303 static Optional<bool> comparePath(const PathPieces &X, const PathPieces &Y);
 304
 305 static Optional<bool>
 306 compareControlFlow(const PathDiagnosticControlFlowPiece &X,
 307                    const PathDiagnosticControlFlowPiece &Y) {
 308   FullSourceLoc XSL = X.getStartLocation().asLocation();
 309   FullSourceLoc YSL = Y.getStartLocation().asLocation();
 310   if (XSL != YSL)
 311     return XSL.isBeforeInTranslationUnitThan(YSL);
 312   FullSourceLoc XEL = X.getEndLocation().asLocation();
 313   FullSourceLoc YEL = Y.getEndLocation().asLocation();
 314   if (XEL != YEL)
 315     return XEL.isBeforeInTranslationUnitThan(YEL);
 316   return None;
 317 }
 318
 319 static Optional<bool> compareMacro(const PathDiagnosticMacroPiece &X,
 320                                    const PathDiagnosticMacroPiece &Y) {
 321   return comparePath(X.subPieces, Y.subPieces);
 322 }
 323
 324 static Optional<bool> compareCall(const PathDiagnosticCallPiece &X,
 325                                   const PathDiagnosticCallPiece &Y) {
 326   FullSourceLoc X_CEL = X.callEnter.asLocation();
 327   FullSourceLoc Y_CEL = Y.callEnter.asLocation();
 328   if (X_CEL != Y_CEL)
 329     return X_CEL.isBeforeInTranslationUnitThan(Y_CEL);
 330   FullSourceLoc X_CEWL = X.callEnterWithin.asLocation();
 331   FullSourceLoc Y_CEWL = Y.callEnterWithin.asLocation();
 332   if (X_CEWL != Y_CEWL)
 333     return X_CEWL.isBeforeInTranslationUnitThan(Y_CEWL);
 334   FullSourceLoc X_CRL = X.callReturn.asLocation();
 335   FullSourceLoc Y_CRL = Y.callReturn.asLocation();
 336   if (X_CRL != Y_CRL)
 337     return X_CRL.isBeforeInTranslationUnitThan(Y_CRL);
 338   return comparePath(X.path, Y.path);
 339 }
 340
 341 static Optional<bool> comparePiece(const PathDiagnosticPiece &X,
 342                                    const PathDiagnosticPiece &Y) {
 343   if (X.getKind() != Y.getKind())
 344     return X.getKind() < Y.getKind();
 345
 346   FullSourceLoc XL = X.getLocation().asLocation();
 347   FullSourceLoc YL = Y.getLocation().asLocation();
 348   if (XL != YL)
 349     return XL.isBeforeInTranslationUnitThan(YL);
 350
 351   if (X.getString() != Y.getString())
 352     return X.getString() < Y.getString();
 353
 354   if (X.getRanges().size() != Y.getRanges().size())
 355     return X.getRanges().size() < Y.getRanges().size();
 356
 357   const SourceManager &SM = XL.getManager();
 358
 359   for (unsigned i = 0, n = X.getRanges().size(); i < n; ++i) {
 360     SourceRange XR = X.getRanges()[i];
 361     SourceRange YR = Y.getRanges()[i];
 362     if (XR != YR) {
 363       if (XR.getBegin() != YR.getBegin())
 364         return SM.isBeforeInTranslationUnit(XR.getBegin(), YR.getBegin());
 365       return SM.isBeforeInTranslationUnit(XR.getEnd(), YR.getEnd());
 366     }
 367   }
 368
 369   switch (X.getKind()) {
 370     case PathDiagnosticPiece::ControlFlow:
 371       return compareControlFlow(cast<PathDiagnosticControlFlowPiece>(X),
 372                                 cast<PathDiagnosticControlFlowPiece>(Y));
 373     case PathDiagnosticPiece::Event:
 374     case PathDiagnosticPiece::Note:
 375       return None;
 376     case PathDiagnosticPiece::Macro:
 377       return compareMacro(cast<PathDiagnosticMacroPiece>(X),
 378                           cast<PathDiagnosticMacroPiece>(Y));
 379     case PathDiagnosticPiece::Call:
 380       return compareCall(cast<PathDiagnosticCallPiece>(X),
 381                          cast<PathDiagnosticCallPiece>(Y));
 382   }
 383   llvm_unreachable("all cases handled");
 384 }
 385
 386 static Optional<bool> comparePath(const PathPieces &X, const PathPieces &Y) {
 387   if (X.size() != Y.size())
 388     return X.size() < Y.size();
 389
 390   PathPieces::const_iterator X_I = X.begin(), X_end = X.end();
 391   PathPieces::const_iterator Y_I = Y.begin(), Y_end = Y.end();
 392
 393   for ( ; X_I != X_end && Y_I != Y_end; ++X_I, ++Y_I) {
 394     Optional<bool> b = comparePiece(**X_I, **Y_I);
 395     if (b.hasValue())
 396       return b.getValue();
 397   }
 398
 399   return None;
 400 }
 401
 402 static bool compareCrossTUSourceLocs(FullSourceLoc XL, FullSourceLoc YL) {
 403   std::pair<FileID, unsigned> XOffs = XL.getDecomposedLoc();
 404   std::pair<FileID, unsigned> YOffs = YL.getDecomposedLoc();
 405   const SourceManager &SM = XL.getManager();
 406   std::pair<bool, bool> InSameTU = SM.isInTheSameTranslationUnit(XOffs, YOffs);
 407   if (InSameTU.first)
 408     return XL.isBeforeInTranslationUnitThan(YL);
 409   const FileEntry *XFE = SM.getFileEntryForID(XL.getSpellingLoc().getFileID());
 410   const FileEntry *YFE = SM.getFileEntryForID(YL.getSpellingLoc().getFileID());
 411   if (!XFE || !YFE)
 412     return XFE && !YFE;
 413   int NameCmp = XFE->getName().compare(YFE->getName());
 414   if (NameCmp != 0)
 415     return NameCmp == -1;
 416   // Last resort: Compare raw file IDs that are possibly expansions.
 417   return XL.getFileID() < YL.getFileID();
 418 }
 419
 420 static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y) {
 421   FullSourceLoc XL = X.getLocation().asLocation();
 422   FullSourceLoc YL = Y.getLocation().asLocation();
 423   if (XL != YL)
 424     return compareCrossTUSourceLocs(XL, YL);
 425   if (X.getBugType() != Y.getBugType())
 426     return X.getBugType() < Y.getBugType();
 427   if (X.getCategory() != Y.getCategory())
 428     return X.getCategory() < Y.getCategory();
 429   if (X.getVerboseDescription() != Y.getVerboseDescription())
 430     return X.getVerboseDescription() < Y.getVerboseDescription();
 431   if (X.getShortDescription() != Y.getShortDescription())
 432     return X.getShortDescription() < Y.getShortDescription();
 433   if (X.getDeclWithIssue() != Y.getDeclWithIssue()) {
 434     const Decl *XD = X.getDeclWithIssue();
 435     if (!XD)
 436       return true;
 437     const Decl *YD = Y.getDeclWithIssue();
 438     if (!YD)
 439       return false;
 440     SourceLocation XDL = XD->getLocation();
 441     SourceLocation YDL = YD->getLocation();
 442     if (XDL != YDL) {
 443       const SourceManager &SM = XL.getManager();
 444       return compareCrossTUSourceLocs(FullSourceLoc(XDL, SM),
 445                                       FullSourceLoc(YDL, SM));
 446     }
 447   }
 448   PathDiagnostic::meta_iterator XI = X.meta_begin(), XE = X.meta_end();
 449   PathDiagnostic::meta_iterator YI = Y.meta_begin(), YE = Y.meta_end();
 450   if (XE - XI != YE - YI)
 451     return (XE - XI) < (YE - YI);
 452   for ( ; XI != XE ; ++XI, ++YI) {
 453     if (*XI != *YI)
 454       return (*XI) < (*YI);
 455   }
 456   Optional<bool> b = comparePath(X.path, Y.path);
 457   assert(b.hasValue());
 458   return b.getValue();
 459 }
 460
 461 void PathDiagnosticConsumer::FlushDiagnostics(
 462                                      PathDiagnosticConsumer::FilesMade *Files) {
 463   if (flushed)
 464     return;
 465
 466   flushed = true;
 467
 468   std::vector<const PathDiagnostic *> BatchDiags;
 469   for (const auto &D : Diags)
 470     BatchDiags.push_back(&D);
 471
 472   // Sort the diagnostics so that they are always emitted in a deterministic
 473   // order.
 474   int (*Comp)(const PathDiagnostic *const *, const PathDiagnostic *const *) =
 475       [](const PathDiagnostic *const *X, const PathDiagnostic *const *Y) {
 476         assert(*X != *Y && "PathDiagnostics not uniqued!");
 477         if (compare(**X, **Y))
 478           return -1;
 479         assert(compare(**Y, **X) && "Not a total order!");
 480         return 1;
 481       };
 482   array_pod_sort(BatchDiags.begin(), BatchDiags.end(), Comp);
 483
 484   FlushDiagnosticsImpl(BatchDiags, Files);
 485
 486   // Delete the flushed diagnostics.
 487   for (const auto D : BatchDiags)
 488     delete D;
 489
 490   // Clear out the FoldingSet.
 491   Diags.clear();
 492 }
 493
 494 PathDiagnosticConsumer::FilesMade::~FilesMade() {
 495   for (PDFileEntry &Entry : Set)
 496     Entry.~PDFileEntry();
 497 }
 498
 499 void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,
 500                                                       StringRef ConsumerName,
 501                                                       StringRef FileName) {
 502   llvm::FoldingSetNodeID NodeID;
 503   NodeID.Add(PD);
 504   void *InsertPos;
 505   PDFileEntry *Entry = Set.FindNodeOrInsertPos(NodeID, InsertPos);
 506   if (!Entry) {
 507     Entry = Alloc.Allocate<PDFileEntry>();
 508     Entry = new (Entry) PDFileEntry(NodeID);
 509     Set.InsertNode(Entry, InsertPos);
 510   }
 511
 512   // Allocate persistent storage for the file name.
 513   char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);
 514   memcpy(FileName_cstr, FileName.data(), FileName.size());
 515
 516   Entry->files.push_back(std::make_pair(ConsumerName,
 517                                         StringRef(FileName_cstr,
 518                                                   FileName.size())));
 519 }
 520
 521 PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *
 522 PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {
 523   llvm::FoldingSetNodeID NodeID;
 524   NodeID.Add(PD);
 525   void *InsertPos;
 526   PDFileEntry *Entry = Set.FindNodeOrInsertPos(NodeID, InsertPos);
 527   if (!Entry)
 528     return nullptr;
 529   return &Entry->files;
 530 }
 531
 532 //===----------------------------------------------------------------------===//
 533 // PathDiagnosticLocation methods.
 534 //===----------------------------------------------------------------------===//
 535
 536 static SourceLocation getValidSourceLocation(const Stmt* S,
 537                                              LocationOrAnalysisDeclContext LAC,
 538                                              bool UseEnd = false) {
 539   SourceLocation L = UseEnd ? S->getLocEnd() : S->getLocStart();
 540   assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
 541                           "be passed to PathDiagnosticLocation upon creation.");
 542
 543   // S might be a temporary statement that does not have a location in the
 544   // source code, so find an enclosing statement and use its location.
 545   if (!L.isValid()) {
 546     AnalysisDeclContext *ADC;
 547     if (LAC.is<const LocationContext*>())
 548       ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();
 549     else
 550       ADC = LAC.get<AnalysisDeclContext*>();
 551
 552     ParentMap &PM = ADC->getParentMap();
 553
 554     const Stmt *Parent = S;
 555     do {
 556       Parent = PM.getParent(Parent);
 557
 558       // In rare cases, we have implicit top-level expressions,
 559       // such as arguments for implicit member initializers.
 560       // In this case, fall back to the start of the body (even if we were
 561       // asked for the statement end location).
 562       if (!Parent) {
 563         const Stmt *Body = ADC->getBody();
 564         if (Body)
 565           L = Body->getLocStart();
 566         else
 567           L = ADC->getDecl()->getLocEnd();
 568         break;
 569       }
 570
 571       L = UseEnd ? Parent->getLocEnd() : Parent->getLocStart();
 572     } while (!L.isValid());
 573   }
 574
 575   return L;
 576 }
 577
 578 static PathDiagnosticLocation
 579 getLocationForCaller(const StackFrameContext *SFC,
 580                      const LocationContext *CallerCtx,
 581                      const SourceManager &SM) {
 582   const CFGBlock &Block = *SFC->getCallSiteBlock();
 583   CFGElement Source = Block[SFC->getIndex()];
 584
 585   switch (Source.getKind()) {
 586   case CFGElement::Statement:
 587   case CFGElement::Constructor:
 588   case CFGElement::CXXRecordTypedCall:
 589     return PathDiagnosticLocation(Source.castAs<CFGStmt>().getStmt(),
 590                                   SM, CallerCtx);
 591   case CFGElement::Initializer: {
 592     const CFGInitializer &Init = Source.castAs<CFGInitializer>();
 593     return PathDiagnosticLocation(Init.getInitializer()->getInit(),
 594                                   SM, CallerCtx);
 595   }
 596   case CFGElement::AutomaticObjectDtor: {
 597     const CFGAutomaticObjDtor &Dtor = Source.castAs<CFGAutomaticObjDtor>();
 598     return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),
 599                                              SM, CallerCtx);
 600   }
 601   case CFGElement::DeleteDtor: {
 602     const CFGDeleteDtor &Dtor = Source.castAs<CFGDeleteDtor>();
 603     return PathDiagnosticLocation(Dtor.getDeleteExpr(), SM, CallerCtx);
 604   }
 605   case CFGElement::BaseDtor:
 606   case CFGElement::MemberDtor: {
 607     const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
 608     if (const Stmt *CallerBody = CallerInfo->getBody())
 609       return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
 610     return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
 611   }
 612   case CFGElement::NewAllocator: {
 613     const CFGNewAllocator &Alloc = Source.castAs<CFGNewAllocator>();
 614     return PathDiagnosticLocation(Alloc.getAllocatorExpr(), SM, CallerCtx);
 615   }
 616   case CFGElement::TemporaryDtor: {
 617     // Temporary destructors are for temporaries. They die immediately at around
 618     // the location of CXXBindTemporaryExpr. If they are lifetime-extended,
 619     // they'd be dealt with via an AutomaticObjectDtor instead.
 620     const auto &Dtor = Source.castAs<CFGTemporaryDtor>();
 621     return PathDiagnosticLocation::createEnd(Dtor.getBindTemporaryExpr(), SM,
 622                                              CallerCtx);
 623   }
 624   case CFGElement::ScopeBegin:
 625   case CFGElement::ScopeEnd:
 626     llvm_unreachable("not yet implemented!");
 627   case CFGElement::LifetimeEnds:
 628   case CFGElement::LoopExit:
 629     llvm_unreachable("CFGElement kind should not be on callsite!");
 630   }
 631
 632   llvm_unreachable("Unknown CFGElement kind");
 633 }
 634
 635 PathDiagnosticLocation
 636 PathDiagnosticLocation::createBegin(const Decl *D,
 637                                     const SourceManager &SM) {
 638   return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
 639 }
 640
 641 PathDiagnosticLocation
 642 PathDiagnosticLocation::createBegin(const Stmt *S,
 643                                     const SourceManager &SM,
 644                                     LocationOrAnalysisDeclContext LAC) {
 645   return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
 646                                 SM, SingleLocK);
 647 }
 648
 649 PathDiagnosticLocation
 650 PathDiagnosticLocation::createEnd(const Stmt *S,
 651                                   const SourceManager &SM,
 652                                   LocationOrAnalysisDeclContext LAC) {
 653   if (const auto *CS = dyn_cast<CompoundStmt>(S))
 654     return createEndBrace(CS, SM);
 655   return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
 656                                 SM, SingleLocK);
 657 }
 658
 659 PathDiagnosticLocation
 660 PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
 661                                           const SourceManager &SM) {
 662   return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
 663 }
 664
 665 PathDiagnosticLocation
 666 PathDiagnosticLocation::createConditionalColonLoc(
 667                                             const ConditionalOperator *CO,
 668                                             const SourceManager &SM) {
 669   return PathDiagnosticLocation(CO->getColonLoc(), SM, SingleLocK);
 670 }
 671
 672 PathDiagnosticLocation
 673 PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
 674                                         const SourceManager &SM) {
 675   return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
 676 }
 677
 678 PathDiagnosticLocation
 679 PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
 680                                          const SourceManager &SM) {
 681   SourceLocation L = CS->getLBracLoc();
 682   return PathDiagnosticLocation(L, SM, SingleLocK);
 683 }
 684
 685 PathDiagnosticLocation
 686 PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
 687                                        const SourceManager &SM) {
 688   SourceLocation L = CS->getRBracLoc();
 689   return PathDiagnosticLocation(L, SM, SingleLocK);
 690 }
 691
 692 PathDiagnosticLocation
 693 PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
 694                                         const SourceManager &SM) {
 695   // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
 696   if (const auto *CS = dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
 697     if (!CS->body_empty()) {
 698       SourceLocation Loc = (*CS->body_begin())->getLocStart();
 699       return PathDiagnosticLocation(Loc, SM, SingleLocK);
 700     }
 701
 702   return PathDiagnosticLocation();
 703 }
 704
 705 PathDiagnosticLocation
 706 PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
 707                                       const SourceManager &SM) {
 708   SourceLocation L = LC->getDecl()->getBodyRBrace();
 709   return PathDiagnosticLocation(L, SM, SingleLocK);
 710 }
 711
 712 PathDiagnosticLocation
 713 PathDiagnosticLocation::create(const ProgramPoint& P,
 714                                const SourceManager &SMng) {
 715   const Stmt* S = nullptr;
 716   if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
 717     const CFGBlock *BSrc = BE->getSrc();
 718     S = BSrc->getTerminatorCondition();
 719   } else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
 720     S = SP->getStmt();
 721     if (P.getAs<PostStmtPurgeDeadSymbols>())
 722       return PathDiagnosticLocation::createEnd(S, SMng, P.getLocationContext());
 723   } else if (Optional<PostInitializer> PIP = P.getAs<PostInitializer>()) {
 724     return PathDiagnosticLocation(PIP->getInitializer()->getSourceLocation(),
 725                                   SMng);
 726   } else if (Optional<PostImplicitCall> PIE = P.getAs<PostImplicitCall>()) {
 727     return PathDiagnosticLocation(PIE->getLocation(), SMng);
 728   } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
 729     return getLocationForCaller(CE->getCalleeContext(),
 730                                 CE->getLocationContext(),
 731                                 SMng);
 732   } else if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>()) {
 733     return getLocationForCaller(CEE->getCalleeContext(),
 734                                 CEE->getLocationContext(),
 735                                 SMng);
 736   } else if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
 737     CFGElement BlockFront = BE->getBlock()->front();
 738     if (auto StmtElt = BlockFront.getAs<CFGStmt>()) {
 739       return PathDiagnosticLocation(StmtElt->getStmt()->getLocStart(), SMng);
 740     } else if (auto NewAllocElt = BlockFront.getAs<CFGNewAllocator>()) {
 741       return PathDiagnosticLocation(
 742           NewAllocElt->getAllocatorExpr()->getLocStart(), SMng);
 743     }
 744     llvm_unreachable("Unexpected CFG element at front of block");
 745   } else {
 746     llvm_unreachable("Unexpected ProgramPoint");
 747   }
 748
 749   return PathDiagnosticLocation(S, SMng, P.getLocationContext());
 750 }
 751
 752 static const LocationContext *
 753 findTopAutosynthesizedParentContext(const LocationContext *LC) {
 754   assert(LC->getAnalysisDeclContext()->isBodyAutosynthesized());
 755   const LocationContext *ParentLC = LC->getParent();
 756   assert(ParentLC && "We don't start analysis from autosynthesized code");
 757   while (ParentLC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
 758     LC = ParentLC;
 759     ParentLC = LC->getParent();
 760     assert(ParentLC && "We don't start analysis from autosynthesized code");
 761   }
 762   return LC;
 763 }
 764
 765 const Stmt *PathDiagnosticLocation::getStmt(const ExplodedNode *N) {
 766   // We cannot place diagnostics on autosynthesized code.
 767   // Put them onto the call site through which we jumped into autosynthesized
 768   // code for the first time.
 769   const LocationContext *LC = N->getLocationContext();
 770   if (LC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
 771     // It must be a stack frame because we only autosynthesize functions.
 772     return cast<StackFrameContext>(findTopAutosynthesizedParentContext(LC))
 773         ->getCallSite();
 774   }
 775   // Otherwise, see if the node's program point directly points to a statement.
 776   ProgramPoint P = N->getLocation();
 777   if (Optional<StmtPoint> SP = P.getAs<StmtPoint>())
 778     return SP->getStmt();
 779   if (Optional<BlockEdge> BE = P.getAs<BlockEdge>())
 780     return BE->getSrc()->getTerminator();
 781   if (Optional<CallEnter> CE = P.getAs<CallEnter>())
 782     return CE->getCallExpr();
 783   if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>())
 784     return CEE->getCalleeContext()->getCallSite();
 785   if (Optional<PostInitializer> PIPP = P.getAs<PostInitializer>())
 786     return PIPP->getInitializer()->getInit();
 787   if (Optional<CallExitBegin> CEB = P.getAs<CallExitBegin>())
 788     return CEB->getReturnStmt();
 789
 790   return nullptr;
 791 }
 792
 793 const Stmt *PathDiagnosticLocation::getNextStmt(const ExplodedNode *N) {
 794   for (N = N->getFirstSucc(); N; N = N->getFirstSucc()) {
 795     if (const Stmt *S = getStmt(N)) {
 796       // Check if the statement is '?' or '&&'/'||'.  These are "merges",
 797       // not actual statement points.
 798       switch (S->getStmtClass()) {
 799         case Stmt::ChooseExprClass:
 800         case Stmt::BinaryConditionalOperatorClass:
 801         case Stmt::ConditionalOperatorClass:
 802           continue;
 803         case Stmt::BinaryOperatorClass: {
 804           BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
 805           if (Op == BO_LAnd || Op == BO_LOr)
 806             continue;
 807           break;
 808         }
 809         default:
 810           break;
 811       }
 812       // We found the statement, so return it.
 813       return S;
 814     }
 815   }
 816
 817   return nullptr;
 818 }
 819
 820 PathDiagnosticLocation
 821   PathDiagnosticLocation::createEndOfPath(const ExplodedNode *N,
 822                                           const SourceManager &SM) {
 823   assert(N && "Cannot create a location with a null node.");
 824   const Stmt *S = getStmt(N);
 825
 826   if (!S) {
 827     // If this is an implicit call, return the implicit call point location.
 828     if (Optional<PreImplicitCall> PIE = N->getLocationAs<PreImplicitCall>())
 829       return PathDiagnosticLocation(PIE->getLocation(), SM);
 830     S = getNextStmt(N);
 831   }
 832
 833   if (S) {
 834     ProgramPoint P = N->getLocation();
 835     const LocationContext *LC = N->getLocationContext();
 836
 837     // For member expressions, return the location of the '.' or '->'.
 838     if (const auto *ME = dyn_cast<MemberExpr>(S))
 839       return PathDiagnosticLocation::createMemberLoc(ME, SM);
 840
 841     // For binary operators, return the location of the operator.
 842     if (const auto *B = dyn_cast<BinaryOperator>(S))
 843       return PathDiagnosticLocation::createOperatorLoc(B, SM);
 844
 845     if (P.getAs<PostStmtPurgeDeadSymbols>())
 846       return PathDiagnosticLocation::createEnd(S, SM, LC);
 847
 848     if (S->getLocStart().isValid())
 849       return PathDiagnosticLocation(S, SM, LC);
 850     return PathDiagnosticLocation(getValidSourceLocation(S, LC), SM);
 851   }
 852
 853   return createDeclEnd(N->getLocationContext(), SM);
 854 }
 855
 856 PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
 857                                            const PathDiagnosticLocation &PDL) {
 858   FullSourceLoc L = PDL.asLocation();
 859   return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
 860 }
 861
 862 FullSourceLoc
 863   PathDiagnosticLocation::genLocation(SourceLocation L,
 864                                       LocationOrAnalysisDeclContext LAC) const {
 865   assert(isValid());
 866   // Note that we want a 'switch' here so that the compiler can warn us in
 867   // case we add more cases.
 868   switch (K) {
 869     case SingleLocK:
 870     case RangeK:
 871       break;
 872     case StmtK:
 873       // Defensive checking.
 874       if (!S)
 875         break;
 876       return FullSourceLoc(getValidSourceLocation(S, LAC),
 877                            const_cast<SourceManager&>(*SM));
 878     case DeclK:
 879       // Defensive checking.
 880       if (!D)
 881         break;
 882       return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
 883   }
 884
 885   return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
 886 }
 887
 888 PathDiagnosticRange
 889   PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
 890   assert(isValid());
 891   // Note that we want a 'switch' here so that the compiler can warn us in
 892   // case we add more cases.
 893   switch (K) {
 894     case SingleLocK:
 895       return PathDiagnosticRange(SourceRange(Loc,Loc), true);
 896     case RangeK:
 897       break;
 898     case StmtK: {
 899       const Stmt *S = asStmt();
 900       switch (S->getStmtClass()) {
 901         default:
 902           break;
 903         case Stmt::DeclStmtClass: {
 904           const auto *DS = cast<DeclStmt>(S);
 905           if (DS->isSingleDecl()) {
 906             // Should always be the case, but we'll be defensive.
 907             return SourceRange(DS->getLocStart(),
 908                                DS->getSingleDecl()->getLocation());
 909           }
 910           break;
 911         }
 912           // FIXME: Provide better range information for different
 913           //  terminators.
 914         case Stmt::IfStmtClass:
 915         case Stmt::WhileStmtClass:
 916         case Stmt::DoStmtClass:
 917         case Stmt::ForStmtClass:
 918         case Stmt::ChooseExprClass:
 919         case Stmt::IndirectGotoStmtClass:
 920         case Stmt::SwitchStmtClass:
 921         case Stmt::BinaryConditionalOperatorClass:
 922         case Stmt::ConditionalOperatorClass:
 923         case Stmt::ObjCForCollectionStmtClass: {
 924           SourceLocation L = getValidSourceLocation(S, LAC);
 925           return SourceRange(L, L);
 926         }
 927       }
 928       SourceRange R = S->getSourceRange();
 929       if (R.isValid())
 930         return R;
 931       break;
 932     }
 933     case DeclK:
 934       if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
 935         return MD->getSourceRange();
 936       if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 937         if (Stmt *Body = FD->getBody())
 938           return Body->getSourceRange();
 939       }
 940       else {
 941         SourceLocation L = D->getLocation();
 942         return PathDiagnosticRange(SourceRange(L, L), true);
 943       }
 944   }
 945
 946   return SourceRange(Loc, Loc);
 947 }
 948
 949 void PathDiagnosticLocation::flatten() {
 950   if (K == StmtK) {
 951     K = RangeK;
 952     S = nullptr;
 953     D = nullptr;
 954   }
 955   else if (K == DeclK) {
 956     K = SingleLocK;
 957     S = nullptr;
 958     D = nullptr;
 959   }
 960 }
 961
 962 //===----------------------------------------------------------------------===//
 963 // Manipulation of PathDiagnosticCallPieces.
 964 //===----------------------------------------------------------------------===//
 965
 966 std::shared_ptr<PathDiagnosticCallPiece>
 967 PathDiagnosticCallPiece::construct(const ExplodedNode *N, const CallExitEnd &CE,
 968                                    const SourceManager &SM) {
 969   const Decl *caller = CE.getLocationContext()->getDecl();
 970   PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
 971                                                     CE.getLocationContext(),
 972                                                     SM);
 973   return std::shared_ptr<PathDiagnosticCallPiece>(
 974       new PathDiagnosticCallPiece(caller, pos));
 975 }
 976
 977 PathDiagnosticCallPiece *
 978 PathDiagnosticCallPiece::construct(PathPieces &path,
 979                                    const Decl *caller) {
 980   std::shared_ptr<PathDiagnosticCallPiece> C(
 981       new PathDiagnosticCallPiece(path, caller));
 982   path.clear();
 983   auto *R = C.get();
 984   path.push_front(std::move(C));
 985   return R;
 986 }
 987
 988 void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
 989                                         const SourceManager &SM) {
 990   const StackFrameContext *CalleeCtx = CE.getCalleeContext();
 991   Callee = CalleeCtx->getDecl();
 992
 993   callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
 994   callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
 995
 996   // Autosynthesized property accessors are special because we'd never
 997   // pop back up to non-autosynthesized code until we leave them.
 998   // This is not generally true for autosynthesized callees, which may call
 999   // non-autosynthesized callbacks.
1000   // Unless set here, the IsCalleeAnAutosynthesizedPropertyAccessor flag
1001   // defaults to false.
1002   if (const auto *MD = dyn_cast<ObjCMethodDecl>(Callee))
1003     IsCalleeAnAutosynthesizedPropertyAccessor = (
1004         MD->isPropertyAccessor() &&
1005         CalleeCtx->getAnalysisDeclContext()->isBodyAutosynthesized());
1006 }
1007
1008 static void describeTemplateParameters(raw_ostream &Out,
1009                                        const ArrayRef<TemplateArgument> TAList,
1010                                        const LangOptions &LO,
1011                                        StringRef Prefix = StringRef(),
1012                                        StringRef Postfix = StringRef());
1013
1014 static void describeTemplateParameter(raw_ostream &Out,
1015                                       const TemplateArgument &TArg,
1016                                       const LangOptions &LO) {
1017
1018   if (TArg.getKind() == TemplateArgument::ArgKind::Pack) {
1019     describeTemplateParameters(Out, TArg.getPackAsArray(), LO);
1020   } else {
1021     TArg.print(PrintingPolicy(LO), Out);
1022   }
1023 }
1024
1025 static void describeTemplateParameters(raw_ostream &Out,
1026                                        const ArrayRef<TemplateArgument> TAList,
1027                                        const LangOptions &LO,
1028                                        StringRef Prefix, StringRef Postfix) {
1029   if (TAList.empty())
1030     return;
1031
1032   Out << Prefix;
1033   for (int I = 0, Last = TAList.size() - 1; I != Last; ++I) {
1034     describeTemplateParameter(Out, TAList[I], LO);
1035     Out << ", ";
1036   }
1037   describeTemplateParameter(Out, TAList[TAList.size() - 1], LO);
1038   Out << Postfix;
1039 }
1040
1041 static void describeClass(raw_ostream &Out, const CXXRecordDecl *D,
1042                           StringRef Prefix = StringRef()) {
1043   if (!D->getIdentifier())
1044     return;
1045   Out << Prefix << '\'' << *D;
1046   if (const auto T = dyn_cast<ClassTemplateSpecializationDecl>(D))
1047     describeTemplateParameters(Out, T->getTemplateArgs().asArray(),
1048                                D->getASTContext().getLangOpts(), "<", ">");
1049
1050   Out << '\'';
1051 }
1052
1053 static bool describeCodeDecl(raw_ostream &Out, const Decl *D,
1054                              bool ExtendedDescription,
1055                              StringRef Prefix = StringRef()) {
1056   if (!D)
1057     return false;
1058
1059   if (isa<BlockDecl>(D)) {
1060     if (ExtendedDescription)
1061       Out << Prefix << "anonymous block";
1062     return ExtendedDescription;
1063   }
1064
1065   if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
1066     Out << Prefix;
1067     if (ExtendedDescription && !MD->isUserProvided()) {
1068       if (MD->isExplicitlyDefaulted())
1069         Out << "defaulted ";
1070       else
1071         Out << "implicit ";
1072     }
1073
1074     if (const auto *CD = dyn_cast<CXXConstructorDecl>(MD)) {
1075       if (CD->isDefaultConstructor())
1076         Out << "default ";
1077       else if (CD->isCopyConstructor())
1078         Out << "copy ";
1079       else if (CD->isMoveConstructor())
1080         Out << "move ";
1081
1082       Out << "constructor";
1083       describeClass(Out, MD->getParent(), " for ");
1084     } else if (isa<CXXDestructorDecl>(MD)) {
1085       if (!MD->isUserProvided()) {
1086         Out << "destructor";
1087         describeClass(Out, MD->getParent(), " for ");
1088       } else {
1089         // Use ~Foo for explicitly-written destructors.
1090         Out << "'" << *MD << "'";
1091       }
1092     } else if (MD->isCopyAssignmentOperator()) {
1093         Out << "copy assignment operator";
1094         describeClass(Out, MD->getParent(), " for ");
1095     } else if (MD->isMoveAssignmentOperator()) {
1096         Out << "move assignment operator";
1097         describeClass(Out, MD->getParent(), " for ");
1098     } else {
1099       if (MD->getParent()->getIdentifier())
1100         Out << "'" << *MD->getParent() << "::" << *MD << "'";
1101       else
1102         Out << "'" << *MD << "'";
1103     }
1104
1105     return true;
1106   }
1107
1108   Out << Prefix << '\'' << cast<NamedDecl>(*D);
1109
1110   // Adding template parameters.
1111   if (const auto FD = dyn_cast<FunctionDecl>(D))
1112     if (const TemplateArgumentList *TAList =
1113                                     FD->getTemplateSpecializationArgs())
1114       describeTemplateParameters(Out, TAList->asArray(),
1115                                  FD->getASTContext().getLangOpts(), "<", ">");
1116
1117   Out << '\'';
1118   return true;
1119 }
1120
1121 std::shared_ptr<PathDiagnosticEventPiece>
1122 PathDiagnosticCallPiece::getCallEnterEvent() const {
1123   // We do not produce call enters and call exits for autosynthesized property
1124   // accessors. We do generally produce them for other functions coming from
1125   // the body farm because they may call callbacks that bring us back into
1126   // visible code.
1127   if (!Callee || IsCalleeAnAutosynthesizedPropertyAccessor)
1128     return nullptr;
1129
1130   SmallString<256> buf;
1131   llvm::raw_svector_ostream Out(buf);
1132
1133   Out << "Calling ";
1134   describeCodeDecl(Out, Callee, /*ExtendedDescription=*/true);
1135
1136   assert(callEnter.asLocation().isValid());
1137   return std::make_shared<PathDiagnosticEventPiece>(callEnter, Out.str());
1138 }
1139
1140 std::shared_ptr<PathDiagnosticEventPiece>
1141 PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
1142   if (!callEnterWithin.asLocation().isValid())
1143     return nullptr;
1144   if (Callee->isImplicit() || !Callee->hasBody())
1145     return nullptr;
1146   if (const auto *MD = dyn_cast<CXXMethodDecl>(Callee))
1147     if (MD->isDefaulted())
1148       return nullptr;
1149
1150   SmallString<256> buf;
1151   llvm::raw_svector_ostream Out(buf);
1152
1153   Out << "Entered call";
1154   describeCodeDecl(Out, Caller, /*ExtendedDescription=*/false, " from ");
1155
1156   return std::make_shared<PathDiagnosticEventPiece>(callEnterWithin, Out.str());
1157 }
1158
1159 std::shared_ptr<PathDiagnosticEventPiece>
1160 PathDiagnosticCallPiece::getCallExitEvent() const {
1161   // We do not produce call enters and call exits for autosynthesized property
1162   // accessors. We do generally produce them for other functions coming from
1163   // the body farm because they may call callbacks that bring us back into
1164   // visible code.
1165   if (NoExit || IsCalleeAnAutosynthesizedPropertyAccessor)
1166     return nullptr;
1167
1168   SmallString<256> buf;
1169   llvm::raw_svector_ostream Out(buf);
1170
1171   if (!CallStackMessage.empty()) {
1172     Out << CallStackMessage;
1173   } else {
1174     bool DidDescribe = describeCodeDecl(Out, Callee,
1175                                         /*ExtendedDescription=*/false,
1176                                         "Returning from ");
1177     if (!DidDescribe)
1178       Out << "Returning to caller";
1179   }
1180
1181   assert(callReturn.asLocation().isValid());
1182   return std::make_shared<PathDiagnosticEventPiece>(callReturn, Out.str());
1183 }
1184
1185 static void compute_path_size(const PathPieces &pieces, unsigned &size) {
1186   for (const auto &I : pieces) {
1187     const PathDiagnosticPiece *piece = I.get();
1188     if (const auto *cp = dyn_cast<PathDiagnosticCallPiece>(piece))
1189       compute_path_size(cp->path, size);
1190     else
1191       ++size;
1192   }
1193 }
1194
1195 unsigned PathDiagnostic::full_size() {
1196   unsigned size = 0;
1197   compute_path_size(path, size);
1198   return size;
1199 }
1200
1201 //===----------------------------------------------------------------------===//
1202 // FoldingSet profiling methods.
1203 //===----------------------------------------------------------------------===//
1204
1205 void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
1206   ID.AddInteger(Range.getBegin().getRawEncoding());
1207   ID.AddInteger(Range.getEnd().getRawEncoding());
1208   ID.AddInteger(Loc.getRawEncoding());
1209 }
1210
1211 void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1212   ID.AddInteger((unsigned) getKind());
1213   ID.AddString(str);
1214   // FIXME: Add profiling support for code hints.
1215   ID.AddInteger((unsigned) getDisplayHint());
1216   ArrayRef<SourceRange> Ranges = getRanges();
1217   for (const auto &I : Ranges) {
1218     ID.AddInteger(I.getBegin().getRawEncoding());
1219     ID.AddInteger(I.getEnd().getRawEncoding());
1220   }
1221 }
1222
1223 void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1224   PathDiagnosticPiece::Profile(ID);
1225   for (const auto &I : path)
1226     ID.Add(*I);
1227 }
1228
1229 void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1230   PathDiagnosticPiece::Profile(ID);
1231   ID.Add(Pos);
1232 }
1233
1234 void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1235   PathDiagnosticPiece::Profile(ID);
1236   for (const auto &I : *this)
1237     ID.Add(I);
1238 }
1239
1240 void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1241   PathDiagnosticSpotPiece::Profile(ID);
1242   for (const auto &I : subPieces)
1243     ID.Add(*I);
1244 }
1245
1246 void PathDiagnosticNotePiece::Profile(llvm::FoldingSetNodeID &ID) const {
1247   PathDiagnosticSpotPiece::Profile(ID);
1248 }
1249
1250 void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
1251   ID.Add(getLocation());
1252   ID.AddString(BugType);
1253   ID.AddString(VerboseDesc);
1254   ID.AddString(Category);
1255 }
1256
1257 void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
1258   Profile(ID);
1259   for (const auto &I : path)
1260     ID.Add(*I);
1261   for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
1262     ID.AddString(*I);
1263 }
1264
1265 StackHintGenerator::~StackHintGenerator() = default;
1266
1267 std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
1268   if (!N)
1269     return getMessageForSymbolNotFound();
1270
1271   ProgramPoint P = N->getLocation();
1272   CallExitEnd CExit = P.castAs<CallExitEnd>();
1273
1274   // FIXME: Use CallEvent to abstract this over all calls.
1275   const Stmt *CallSite = CExit.getCalleeContext()->getCallSite();
1276   const auto *CE = dyn_cast_or_null<CallExpr>(CallSite);
1277   if (!CE)
1278     return {};
1279
1280   // Check if one of the parameters are set to the interesting symbol.
1281   unsigned ArgIndex = 0;
1282   for (CallExpr::const_arg_iterator I = CE->arg_begin(),
1283                                     E = CE->arg_end(); I != E; ++I, ++ArgIndex){
1284     SVal SV = N->getSVal(*I);
1285
1286     // Check if the variable corresponding to the symbol is passed by value.
1287     SymbolRef AS = SV.getAsLocSymbol();
1288     if (AS == Sym) {
1289       return getMessageForArg(*I, ArgIndex);
1290     }
1291
1292     // Check if the parameter is a pointer to the symbol.
1293     if (Optional<loc::MemRegionVal> Reg = SV.getAs<loc::MemRegionVal>()) {
1294       // Do not attempt to dereference void*.
1295       if ((*I)->getType()->isVoidPointerType())
1296         continue;
1297       SVal PSV = N->getState()->getSVal(Reg->getRegion());
1298       SymbolRef AS = PSV.getAsLocSymbol();
1299       if (AS == Sym) {
1300         return getMessageForArg(*I, ArgIndex);
1301       }
1302     }
1303   }
1304
1305   // Check if we are returning the interesting symbol.
1306   SVal SV = N->getSVal(CE);
1307   SymbolRef RetSym = SV.getAsLocSymbol();
1308   if (RetSym == Sym) {
1309     return getMessageForReturn(CE);
1310   }
1311
1312   return getMessageForSymbolNotFound();
1313 }
1314
1315 std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
1316                                                           unsigned ArgIndex) {
1317   // Printed parameters start at 1, not 0.
1318   ++ArgIndex;
1319
1320   SmallString<200> buf;
1321   llvm::raw_svector_ostream os(buf);
1322
1323   os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
1324      << " parameter";
1325
1326   return os.str();
1327 }
1328
1329 LLVM_DUMP_METHOD void PathPieces::dump() const {
1330   unsigned index = 0;
1331   for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
1332     llvm::errs() << "[" << index++ << "]  ";
1333     (*I)->dump();
1334     llvm::errs() << "\n";
1335   }
1336 }
1337
1338 LLVM_DUMP_METHOD void PathDiagnosticCallPiece::dump() const {
1339   llvm::errs() << "CALL\n--------------\n";
1340
1341   if (const Stmt *SLoc = getLocation().getStmtOrNull())
1342     SLoc->dump();
1343   else if (const auto *ND = dyn_cast_or_null<NamedDecl>(getCallee()))
1344     llvm::errs() << *ND << "\n";
1345   else
1346     getLocation().dump();
1347 }
1348
1349 LLVM_DUMP_METHOD void PathDiagnosticEventPiece::dump() const {
1350   llvm::errs() << "EVENT\n--------------\n";
1351   llvm::errs() << getString() << "\n";
1352   llvm::errs() << " ---- at ----\n";
1353   getLocation().dump();
1354 }
1355
1356 LLVM_DUMP_METHOD void PathDiagnosticControlFlowPiece::dump() const {
1357   llvm::errs() << "CONTROL\n--------------\n";
1358   getStartLocation().dump();
1359   llvm::errs() << " ---- to ----\n";
1360   getEndLocation().dump();
1361 }
1362
1363 LLVM_DUMP_METHOD void PathDiagnosticMacroPiece::dump() const {
1364   llvm::errs() << "MACRO\n--------------\n";
1365   // FIXME: Print which macro is being invoked.
1366 }
1367
1368 LLVM_DUMP_METHOD void PathDiagnosticNotePiece::dump() const {
1369   llvm::errs() << "NOTE\n--------------\n";
1370   llvm::errs() << getString() << "\n";
1371   llvm::errs() << " ---- at ----\n";
1372   getLocation().dump();
1373 }
1374
1375 LLVM_DUMP_METHOD void PathDiagnosticLocation::dump() const {
1376   if (!isValid()) {
1377     llvm::errs() << "<INVALID>\n";
1378     return;
1379   }
1380
1381   switch (K) {
1382   case RangeK:
1383     // FIXME: actually print the range.
1384     llvm::errs() << "<range>\n";
1385     break;
1386   case SingleLocK:
1387     asLocation().dump();
1388     llvm::errs() << "\n";
1389     break;
1390   case StmtK:
1391     if (S)
1392       S->dump();
1393     else
1394       llvm::errs() << "<NULL STMT>\n";
1395     break;
1396   case DeclK:
1397     if (const auto *ND = dyn_cast_or_null<NamedDecl>(D))
1398       llvm::errs() << *ND << "\n";
1399     else if (isa<BlockDecl>(D))
1400       // FIXME: Make this nicer.
1401       llvm::errs() << "<block>\n";
1402     else if (D)
1403       llvm::errs() << "<unknown decl>\n";
1404     else
1405       llvm::errs() << "<NULL DECL>\n";
1406     break;
1407   }
1408 }