contrib/llvm-project/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp

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