brintos / llvm-project-archived public Read only

1//===- BugReporter.cpp - Generate PathDiagnostics for bugs ----------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9//  This file defines BugReporter, a utility class for generating10//  PathDiagnostics.11//12//===----------------------------------------------------------------------===//13 14#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"15#include "clang/AST/ASTTypeTraits.h"16#include "clang/AST/Attr.h"17#include "clang/AST/Decl.h"18#include "clang/AST/DeclBase.h"19#include "clang/AST/DeclObjC.h"20#include "clang/AST/Expr.h"21#include "clang/AST/ExprCXX.h"22#include "clang/AST/ParentMap.h"23#include "clang/AST/Stmt.h"24#include "clang/AST/StmtCXX.h"25#include "clang/AST/StmtObjC.h"26#include "clang/Analysis/AnalysisDeclContext.h"27#include "clang/Analysis/CFG.h"28#include "clang/Analysis/CFGStmtMap.h"29#include "clang/Analysis/PathDiagnostic.h"30#include "clang/Analysis/ProgramPoint.h"31#include "clang/Basic/LLVM.h"32#include "clang/Basic/SourceLocation.h"33#include "clang/Basic/SourceManager.h"34#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"35#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h"36#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"37#include "clang/StaticAnalyzer/Core/BugReporter/Z3CrosscheckVisitor.h"38#include "clang/StaticAnalyzer/Core/Checker.h"39#include "clang/StaticAnalyzer/Core/CheckerManager.h"40#include "clang/StaticAnalyzer/Core/CheckerRegistryData.h"41#include "clang/StaticAnalyzer/Core/PathSensitive/EntryPointStats.h"42#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"43#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"44#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"45#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"46#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"47#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"48#include "llvm/ADT/ArrayRef.h"49#include "llvm/ADT/DenseMap.h"50#include "llvm/ADT/DenseSet.h"51#include "llvm/ADT/FoldingSet.h"52#include "llvm/ADT/STLExtras.h"53#include "llvm/ADT/SmallPtrSet.h"54#include "llvm/ADT/StringExtras.h"55#include "llvm/ADT/StringRef.h"56#include "llvm/Support/Compiler.h"57#include "llvm/Support/ErrorHandling.h"58#include "llvm/Support/TimeProfiler.h"59#include "llvm/Support/raw_ostream.h"60#include <algorithm>61#include <cassert>62#include <cstddef>63#include <iterator>64#include <memory>65#include <optional>66#include <queue>67#include <string>68#include <tuple>69#include <utility>70#include <vector>71 72using namespace clang;73using namespace ento;74using namespace llvm;75 76#define DEBUG_TYPE "BugReporter"77 78STAT_MAX(MaxBugClassSize,79         "The maximum number of bug reports in the same equivalence class");80STAT_MAX(MaxValidBugClassSize,81         "The maximum number of bug reports in the same equivalence class "82         "where at least one report is valid (not suppressed)");83 84STAT_COUNTER(NumTimesReportPassesZ3, "Number of reports passed Z3");85STAT_COUNTER(NumTimesReportRefuted, "Number of reports refuted by Z3");86STAT_COUNTER(NumTimesReportEQClassAborted,87             "Number of times a report equivalence class was aborted by the Z3 "88             "oracle heuristic");89STAT_COUNTER(NumTimesReportEQClassWasExhausted,90             "Number of times all reports of an equivalence class was refuted");91 92BugReporterVisitor::~BugReporterVisitor() = default;93 94void BugReporterContext::anchor() {}95 96//===----------------------------------------------------------------------===//97// PathDiagnosticBuilder and its associated routines and helper objects.98//===----------------------------------------------------------------------===//99 100namespace {101 102/// A (CallPiece, node assiciated with its CallEnter) pair.103using CallWithEntry =104    std::pair<PathDiagnosticCallPiece *, const ExplodedNode *>;105using CallWithEntryStack = SmallVector<CallWithEntry, 6>;106 107/// Map from each node to the diagnostic pieces visitors emit for them.108using VisitorsDiagnosticsTy =109    llvm::DenseMap<const ExplodedNode *, std::vector<PathDiagnosticPieceRef>>;110 111/// A map from PathDiagnosticPiece to the LocationContext of the inlined112/// function call it represents.113using LocationContextMap =114    llvm::DenseMap<const PathPieces *, const LocationContext *>;115 116/// A helper class that contains everything needed to construct a117/// PathDiagnostic object. It does no much more then providing convenient118/// getters and some well placed asserts for extra security.119class PathDiagnosticConstruct {120  /// The consumer we're constructing the bug report for.121  const PathDiagnosticConsumer *Consumer;122  /// Our current position in the bug path, which is owned by123  /// PathDiagnosticBuilder.124  const ExplodedNode *CurrentNode;125  /// A mapping from parts of the bug path (for example, a function call, which126  /// would span backwards from a CallExit to a CallEnter with the nodes in127  /// between them) with the location contexts it is associated with.128  LocationContextMap LCM;129  const SourceManager &SM;130 131public:132  /// We keep stack of calls to functions as we're ascending the bug path.133  /// TODO: PathDiagnostic has a stack doing the same thing, shouldn't we use134  /// that instead?135  CallWithEntryStack CallStack;136  /// The bug report we're constructing. For ease of use, this field is kept137  /// public, though some "shortcut" getters are provided for commonly used138  /// methods of PathDiagnostic.139  std::unique_ptr<PathDiagnostic> PD;140 141public:142  PathDiagnosticConstruct(const PathDiagnosticConsumer *PDC,143                          const ExplodedNode *ErrorNode,144                          const PathSensitiveBugReport *R,145                          const Decl *AnalysisEntryPoint);146 147  /// \returns the location context associated with the current position in the148  /// bug path.149  const LocationContext *getCurrLocationContext() const {150    assert(CurrentNode && "Already reached the root!");151    return CurrentNode->getLocationContext();152  }153 154  /// Same as getCurrLocationContext (they should always return the same155  /// location context), but works after reaching the root of the bug path as156  /// well.157  const LocationContext *getLocationContextForActivePath() const {158    return LCM.find(&PD->getActivePath())->getSecond();159  }160 161  const ExplodedNode *getCurrentNode() const { return CurrentNode; }162 163  /// Steps the current node to its predecessor.164  /// \returns whether we reached the root of the bug path.165  bool ascendToPrevNode() {166    CurrentNode = CurrentNode->getFirstPred();167    return static_cast<bool>(CurrentNode);168  }169 170  const ParentMap &getParentMap() const {171    return getCurrLocationContext()->getParentMap();172  }173 174  const SourceManager &getSourceManager() const { return SM; }175 176  const Stmt *getParent(const Stmt *S) const {177    return getParentMap().getParent(S);178  }179 180  void updateLocCtxMap(const PathPieces *Path, const LocationContext *LC) {181    assert(Path && LC);182    LCM[Path] = LC;183  }184 185  const LocationContext *getLocationContextFor(const PathPieces *Path) const {186    assert(LCM.count(Path) &&187           "Failed to find the context associated with these pieces!");188    return LCM.find(Path)->getSecond();189  }190 191  bool isInLocCtxMap(const PathPieces *Path) const { return LCM.count(Path); }192 193  PathPieces &getActivePath() { return PD->getActivePath(); }194  PathPieces &getMutablePieces() { return PD->getMutablePieces(); }195 196  bool shouldAddPathEdges() const { return Consumer->shouldAddPathEdges(); }197  bool shouldAddControlNotes() const {198    return Consumer->shouldAddControlNotes();199  }200  bool shouldGenerateDiagnostics() const {201    return Consumer->shouldGenerateDiagnostics();202  }203  bool supportsLogicalOpControlFlow() const {204    return Consumer->supportsLogicalOpControlFlow();205  }206};207 208/// Contains every contextual information needed for constructing a209/// PathDiagnostic object for a given bug report. This class and its fields are210/// immutable, and passes a BugReportConstruct object around during the211/// construction.212class PathDiagnosticBuilder : public BugReporterContext {213  /// A linear path from the error node to the root.214  std::unique_ptr<const ExplodedGraph> BugPath;215  /// The bug report we're describing. Visitors create their diagnostics with216  /// them being the last entities being able to modify it (for example,217  /// changing interestingness here would cause inconsistencies as to how this218  /// file and visitors construct diagnostics), hence its const.219  const PathSensitiveBugReport *R;220  /// The leaf of the bug path. This isn't the same as the bug reports error221  /// node, which refers to the *original* graph, not the bug path.222  const ExplodedNode *const ErrorNode;223  /// The diagnostic pieces visitors emitted, which is expected to be collected224  /// by the time this builder is constructed.225  std::unique_ptr<const VisitorsDiagnosticsTy> VisitorsDiagnostics;226 227public:228  /// Find a non-invalidated report for a given equivalence class,  and returns229  /// a PathDiagnosticBuilder able to construct bug reports for different230  /// consumers. Returns std::nullopt if no valid report is found.231  static std::optional<PathDiagnosticBuilder>232  findValidReport(ArrayRef<PathSensitiveBugReport *> &bugReports,233                  PathSensitiveBugReporter &Reporter);234 235  PathDiagnosticBuilder(236      BugReporterContext BRC, std::unique_ptr<ExplodedGraph> BugPath,237      PathSensitiveBugReport *r, const ExplodedNode *ErrorNode,238      std::unique_ptr<VisitorsDiagnosticsTy> VisitorsDiagnostics);239 240  /// This function is responsible for generating diagnostic pieces that are241  /// *not* provided by bug report visitors.242  /// These diagnostics may differ depending on the consumer's settings,243  /// and are therefore constructed separately for each consumer.244  ///245  /// There are two path diagnostics generation modes: with adding edges (used246  /// for plists) and without  (used for HTML and text). When edges are added,247  /// the path is modified to insert artificially generated edges.248  /// Otherwise, more detailed diagnostics is emitted for block edges,249  /// explaining the transitions in words.250  std::unique_ptr<PathDiagnostic>251  generate(const PathDiagnosticConsumer *PDC) const;252 253private:254  void updateStackPiecesWithMessage(PathDiagnosticPieceRef P,255                                    const CallWithEntryStack &CallStack) const;256  void generatePathDiagnosticsForNode(PathDiagnosticConstruct &C,257                                      PathDiagnosticLocation &PrevLoc) const;258 259  void generateMinimalDiagForBlockEdge(PathDiagnosticConstruct &C,260                                       BlockEdge BE) const;261 262  PathDiagnosticPieceRef263  generateDiagForGotoOP(const PathDiagnosticConstruct &C, const Stmt *S,264                        PathDiagnosticLocation &Start) const;265 266  PathDiagnosticPieceRef267  generateDiagForSwitchOP(const PathDiagnosticConstruct &C, const CFGBlock *Dst,268                          PathDiagnosticLocation &Start) const;269 270  PathDiagnosticPieceRef271  generateDiagForBinaryOP(const PathDiagnosticConstruct &C, const Stmt *T,272                          const CFGBlock *Src, const CFGBlock *DstC) const;273 274  PathDiagnosticLocation275  ExecutionContinues(const PathDiagnosticConstruct &C) const;276 277  PathDiagnosticLocation278  ExecutionContinues(llvm::raw_string_ostream &os,279                     const PathDiagnosticConstruct &C) const;280 281  const PathSensitiveBugReport *getBugReport() const { return R; }282};283 284std::string timeTraceName(const BugReportEquivClass &EQ) {285  if (!llvm::timeTraceProfilerEnabled())286    return "";287  const auto &BugReports = EQ.getReports();288  if (BugReports.empty())289    return "Empty Equivalence Class";290  const BugReport *R = BugReports.front().get();291  const auto &BT = R->getBugType();292  return ("Flushing EQC " + BT.getDescription()).str();293}294 295llvm::TimeTraceMetadata timeTraceMetadata(const BugReportEquivClass &EQ,296                                          const SourceManager &SM) {297  // Must be called only when constructing non-bogus TimeTraceScope298  assert(llvm::timeTraceProfilerEnabled());299 300  const auto &BugReports = EQ.getReports();301  if (BugReports.empty())302    return {};303  const BugReport *R = BugReports.front().get();304  const auto &BT = R->getBugType();305  auto Loc = R->getLocation().asLocation();306  std::string File = SM.getFilename(Loc).str();307  return {BT.getCheckerName().str(), std::move(File),308          static_cast<int>(Loc.getLineNumber())};309}310 311} // namespace312 313//===----------------------------------------------------------------------===//314// Base implementation of stack hint generators.315//===----------------------------------------------------------------------===//316 317StackHintGenerator::~StackHintGenerator() = default;318 319std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){320  if (!N)321    return getMessageForSymbolNotFound();322 323  ProgramPoint P = N->getLocation();324  CallExitEnd CExit = P.castAs<CallExitEnd>();325 326  // FIXME: Use CallEvent to abstract this over all calls.327  const Stmt *CallSite = CExit.getCalleeContext()->getCallSite();328  const auto *CE = dyn_cast_or_null<CallExpr>(CallSite);329  if (!CE)330    return {};331 332  // Check if one of the parameters are set to the interesting symbol.333  for (auto [Idx, ArgExpr] : llvm::enumerate(CE->arguments())) {334    SVal SV = N->getSVal(ArgExpr);335 336    // Check if the variable corresponding to the symbol is passed by value.337    SymbolRef AS = SV.getAsLocSymbol();338    if (AS == Sym) {339      return getMessageForArg(ArgExpr, Idx);340    }341 342    // Check if the parameter is a pointer to the symbol.343    if (std::optional<loc::MemRegionVal> Reg = SV.getAs<loc::MemRegionVal>()) {344      // Do not attempt to dereference void*.345      if (ArgExpr->getType()->isVoidPointerType())346        continue;347      SVal PSV = N->getState()->getSVal(Reg->getRegion());348      SymbolRef AS = PSV.getAsLocSymbol();349      if (AS == Sym) {350        return getMessageForArg(ArgExpr, Idx);351      }352    }353  }354 355  // Check if we are returning the interesting symbol.356  SVal SV = N->getSVal(CE);357  SymbolRef RetSym = SV.getAsLocSymbol();358  if (RetSym == Sym) {359    return getMessageForReturn(CE);360  }361 362  return getMessageForSymbolNotFound();363}364 365std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,366                                                          unsigned ArgIndex) {367  // Printed parameters start at 1, not 0.368  ++ArgIndex;369 370  return (llvm::Twine(Msg) + " via " + std::to_string(ArgIndex) +371          llvm::getOrdinalSuffix(ArgIndex) + " parameter").str();372}373 374//===----------------------------------------------------------------------===//375// Diagnostic cleanup.376//===----------------------------------------------------------------------===//377 378static PathDiagnosticEventPiece *379eventsDescribeSameCondition(PathDiagnosticEventPiece *X,380                            PathDiagnosticEventPiece *Y) {381  // Prefer diagnostics that come from ConditionBRVisitor over382  // those that came from TrackConstraintBRVisitor,383  // unless the one from ConditionBRVisitor is384  // its generic fallback diagnostic.385  const void *tagPreferred = ConditionBRVisitor::getTag();386  const void *tagLesser = TrackConstraintBRVisitor::getTag();387 388  if (X->getLocation() != Y->getLocation())389    return nullptr;390 391  if (X->getTag() == tagPreferred && Y->getTag() == tagLesser)392    return ConditionBRVisitor::isPieceMessageGeneric(X) ? Y : X;393 394  if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)395    return ConditionBRVisitor::isPieceMessageGeneric(Y) ? X : Y;396 397  return nullptr;398}399 400/// An optimization pass over PathPieces that removes redundant diagnostics401/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor.  Both402/// BugReporterVisitors use different methods to generate diagnostics, with403/// one capable of emitting diagnostics in some cases but not in others.  This404/// can lead to redundant diagnostic pieces at the same point in a path.405static void removeRedundantMsgs(PathPieces &path) {406  unsigned N = path.size();407  if (N < 2)408    return;409  // NOTE: this loop intentionally is not using an iterator.  Instead, we410  // are streaming the path and modifying it in place.  This is done by411  // grabbing the front, processing it, and if we decide to keep it append412  // it to the end of the path.  The entire path is processed in this way.413  for (unsigned i = 0; i < N; ++i) {414    auto piece = std::move(path.front());415    path.pop_front();416 417    switch (piece->getKind()) {418      case PathDiagnosticPiece::Call:419        removeRedundantMsgs(cast<PathDiagnosticCallPiece>(*piece).path);420        break;421      case PathDiagnosticPiece::Macro:422        removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(*piece).subPieces);423        break;424      case PathDiagnosticPiece::Event: {425        if (i == N-1)426          break;427 428        if (auto *nextEvent =429            dyn_cast<PathDiagnosticEventPiece>(path.front().get())) {430          auto *event = cast<PathDiagnosticEventPiece>(piece.get());431          // Check to see if we should keep one of the two pieces.  If we432          // come up with a preference, record which piece to keep, and consume433          // another piece from the path.434          if (auto *pieceToKeep =435                  eventsDescribeSameCondition(event, nextEvent)) {436            piece = std::move(pieceToKeep == event ? piece : path.front());437            path.pop_front();438            ++i;439          }440        }441        break;442      }443      case PathDiagnosticPiece::ControlFlow:444      case PathDiagnosticPiece::Note:445      case PathDiagnosticPiece::PopUp:446        break;447    }448    path.push_back(std::move(piece));449  }450}451 452/// Recursively scan through a path and prune out calls and macros pieces453/// that aren't needed.  Return true if afterwards the path contains454/// "interesting stuff" which means it shouldn't be pruned from the parent path.455static bool removeUnneededCalls(const PathDiagnosticConstruct &C,456                                PathPieces &pieces,457                                const PathSensitiveBugReport *R,458                                bool IsInteresting = false) {459  bool containsSomethingInteresting = IsInteresting;460  const unsigned N = pieces.size();461 462  for (unsigned i = 0 ; i < N ; ++i) {463    // Remove the front piece from the path.  If it is still something we464    // want to keep once we are done, we will push it back on the end.465    auto piece = std::move(pieces.front());466    pieces.pop_front();467 468    switch (piece->getKind()) {469      case PathDiagnosticPiece::Call: {470        auto &call = cast<PathDiagnosticCallPiece>(*piece);471        // Check if the location context is interesting.472        if (!removeUnneededCalls(473                C, call.path, R,474                R->isInteresting(C.getLocationContextFor(&call.path))))475          continue;476 477        containsSomethingInteresting = true;478        break;479      }480      case PathDiagnosticPiece::Macro: {481        auto &macro = cast<PathDiagnosticMacroPiece>(*piece);482        if (!removeUnneededCalls(C, macro.subPieces, R, IsInteresting))483          continue;484        containsSomethingInteresting = true;485        break;486      }487      case PathDiagnosticPiece::Event: {488        auto &event = cast<PathDiagnosticEventPiece>(*piece);489 490        // We never throw away an event, but we do throw it away wholesale491        // as part of a path if we throw the entire path away.492        containsSomethingInteresting |= !event.isPrunable();493        break;494      }495      case PathDiagnosticPiece::ControlFlow:496      case PathDiagnosticPiece::Note:497      case PathDiagnosticPiece::PopUp:498        break;499    }500 501    pieces.push_back(std::move(piece));502  }503 504  return containsSomethingInteresting;505}506 507/// Same logic as above to remove extra pieces.508static void removePopUpNotes(PathPieces &Path) {509  for (unsigned int i = 0; i < Path.size(); ++i) {510    auto Piece = std::move(Path.front());511    Path.pop_front();512    if (!isa<PathDiagnosticPopUpPiece>(*Piece))513      Path.push_back(std::move(Piece));514  }515}516 517/// Returns true if the given decl has been implicitly given a body, either by518/// the analyzer or by the compiler proper.519static bool hasImplicitBody(const Decl *D) {520  assert(D);521  return D->isImplicit() || !D->hasBody();522}523 524/// Recursively scan through a path and make sure that all call pieces have525/// valid locations.526static void527adjustCallLocations(PathPieces &Pieces,528                    PathDiagnosticLocation *LastCallLocation = nullptr) {529  for (const auto &I : Pieces) {530    auto *Call = dyn_cast<PathDiagnosticCallPiece>(I.get());531 532    if (!Call)533      continue;534 535    if (LastCallLocation) {536      bool CallerIsImplicit = hasImplicitBody(Call->getCaller());537      if (CallerIsImplicit || !Call->callEnter.asLocation().isValid())538        Call->callEnter = *LastCallLocation;539      if (CallerIsImplicit || !Call->callReturn.asLocation().isValid())540        Call->callReturn = *LastCallLocation;541    }542 543    // Recursively clean out the subclass.  Keep this call around if544    // it contains any informative diagnostics.545    PathDiagnosticLocation *ThisCallLocation;546    if (Call->callEnterWithin.asLocation().isValid() &&547        !hasImplicitBody(Call->getCallee()))548      ThisCallLocation = &Call->callEnterWithin;549    else550      ThisCallLocation = &Call->callEnter;551 552    assert(ThisCallLocation && "Outermost call has an invalid location");553    adjustCallLocations(Call->path, ThisCallLocation);554  }555}556 557/// Remove edges in and out of C++ default initializer expressions. These are558/// for fields that have in-class initializers, as opposed to being initialized559/// explicitly in a constructor or braced list.560static void removeEdgesToDefaultInitializers(PathPieces &Pieces) {561  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {562    if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))563      removeEdgesToDefaultInitializers(C->path);564 565    if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))566      removeEdgesToDefaultInitializers(M->subPieces);567 568    if (auto *CF = dyn_cast<PathDiagnosticControlFlowPiece>(I->get())) {569      const Stmt *Start = CF->getStartLocation().asStmt();570      const Stmt *End = CF->getEndLocation().asStmt();571      if (isa_and_nonnull<CXXDefaultInitExpr>(Start)) {572        I = Pieces.erase(I);573        continue;574      } else if (isa_and_nonnull<CXXDefaultInitExpr>(End)) {575        PathPieces::iterator Next = std::next(I);576        if (Next != E) {577          if (auto *NextCF =578                  dyn_cast<PathDiagnosticControlFlowPiece>(Next->get())) {579            NextCF->setStartLocation(CF->getStartLocation());580          }581        }582        I = Pieces.erase(I);583        continue;584      }585    }586 587    I++;588  }589}590 591/// Remove all pieces with invalid locations as these cannot be serialized.592/// We might have pieces with invalid locations as a result of inlining Body593/// Farm generated functions.594static void removePiecesWithInvalidLocations(PathPieces &Pieces) {595  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {596    if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))597      removePiecesWithInvalidLocations(C->path);598 599    if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))600      removePiecesWithInvalidLocations(M->subPieces);601 602    if (!(*I)->getLocation().isValid() ||603        !(*I)->getLocation().asLocation().isValid()) {604      I = Pieces.erase(I);605      continue;606    }607    I++;608  }609}610 611PathDiagnosticLocation PathDiagnosticBuilder::ExecutionContinues(612    const PathDiagnosticConstruct &C) const {613  if (const Stmt *S = C.getCurrentNode()->getNextStmtForDiagnostics())614    return PathDiagnosticLocation(S, getSourceManager(),615                                  C.getCurrLocationContext());616 617  return PathDiagnosticLocation::createDeclEnd(C.getCurrLocationContext(),618                                               getSourceManager());619}620 621PathDiagnosticLocation PathDiagnosticBuilder::ExecutionContinues(622    llvm::raw_string_ostream &os, const PathDiagnosticConstruct &C) const {623  // Slow, but probably doesn't matter.624  if (os.str().empty())625    os << ' ';626 627  const PathDiagnosticLocation &Loc = ExecutionContinues(C);628 629  if (Loc.asStmt())630    os << "Execution continues on line "631       << getSourceManager().getExpansionLineNumber(Loc.asLocation())632       << '.';633  else {634    os << "Execution jumps to the end of the ";635    const Decl *D = C.getCurrLocationContext()->getDecl();636    if (isa<ObjCMethodDecl>(D))637      os << "method";638    else if (isa<FunctionDecl>(D))639      os << "function";640    else {641      assert(isa<BlockDecl>(D));642      os << "anonymous block";643    }644    os << '.';645  }646 647  return Loc;648}649 650static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) {651  if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))652    return PM.getParentIgnoreParens(S);653 654  const Stmt *Parent = PM.getParentIgnoreParens(S);655  if (!Parent)656    return nullptr;657 658  switch (Parent->getStmtClass()) {659  case Stmt::ForStmtClass:660  case Stmt::DoStmtClass:661  case Stmt::WhileStmtClass:662  case Stmt::ObjCForCollectionStmtClass:663  case Stmt::CXXForRangeStmtClass:664    return Parent;665  default:666    break;667  }668 669  return nullptr;670}671 672static PathDiagnosticLocation673getEnclosingStmtLocation(const Stmt *S, const LocationContext *LC,674                         bool allowNestedContexts = false) {675  if (!S)676    return {};677 678  const SourceManager &SMgr = LC->getDecl()->getASTContext().getSourceManager();679 680  while (const Stmt *Parent = getEnclosingParent(S, LC->getParentMap())) {681    switch (Parent->getStmtClass()) {682      case Stmt::BinaryOperatorClass: {683        const auto *B = cast<BinaryOperator>(Parent);684        if (B->isLogicalOp())685          return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC);686        break;687      }688      case Stmt::CompoundStmtClass:689      case Stmt::StmtExprClass:690        return PathDiagnosticLocation(S, SMgr, LC);691      case Stmt::ChooseExprClass:692        // Similar to '?' if we are referring to condition, just have the edge693        // point to the entire choose expression.694        if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S)695          return PathDiagnosticLocation(Parent, SMgr, LC);696        else697          return PathDiagnosticLocation(S, SMgr, LC);698      case Stmt::BinaryConditionalOperatorClass:699      case Stmt::ConditionalOperatorClass:700        // For '?', if we are referring to condition, just have the edge point701        // to the entire '?' expression.702        if (allowNestedContexts ||703            cast<AbstractConditionalOperator>(Parent)->getCond() == S)704          return PathDiagnosticLocation(Parent, SMgr, LC);705        else706          return PathDiagnosticLocation(S, SMgr, LC);707      case Stmt::CXXForRangeStmtClass:708        if (cast<CXXForRangeStmt>(Parent)->getBody() == S)709          return PathDiagnosticLocation(S, SMgr, LC);710        break;711      case Stmt::DoStmtClass:712          return PathDiagnosticLocation(S, SMgr, LC);713      case Stmt::ForStmtClass:714        if (cast<ForStmt>(Parent)->getBody() == S)715          return PathDiagnosticLocation(S, SMgr, LC);716        break;717      case Stmt::IfStmtClass:718        if (cast<IfStmt>(Parent)->getCond() != S)719          return PathDiagnosticLocation(S, SMgr, LC);720        break;721      case Stmt::ObjCForCollectionStmtClass:722        if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)723          return PathDiagnosticLocation(S, SMgr, LC);724        break;725      case Stmt::WhileStmtClass:726        if (cast<WhileStmt>(Parent)->getCond() != S)727          return PathDiagnosticLocation(S, SMgr, LC);728        break;729      default:730        break;731    }732 733    S = Parent;734  }735 736  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");737 738  return PathDiagnosticLocation(S, SMgr, LC);739}740 741//===----------------------------------------------------------------------===//742// "Minimal" path diagnostic generation algorithm.743//===----------------------------------------------------------------------===//744 745/// If the piece contains a special message, add it to all the call pieces on746/// the active stack. For example, my_malloc allocated memory, so MallocChecker747/// will construct an event at the call to malloc(), and add a stack hint that748/// an allocated memory was returned. We'll use this hint to construct a message749/// when returning from the call to my_malloc750///751///   void *my_malloc() { return malloc(sizeof(int)); }752///   void fishy() {753///     void *ptr = my_malloc(); // returned allocated memory754///   } // leak755void PathDiagnosticBuilder::updateStackPiecesWithMessage(756    PathDiagnosticPieceRef P, const CallWithEntryStack &CallStack) const {757  if (R->hasCallStackHint(P))758    for (const auto &I : CallStack) {759      PathDiagnosticCallPiece *CP = I.first;760      const ExplodedNode *N = I.second;761      std::string stackMsg = R->getCallStackMessage(P, N);762 763      // The last message on the path to final bug is the most important764      // one. Since we traverse the path backwards, do not add the message765      // if one has been previously added.766      if (!CP->hasCallStackMessage())767        CP->setCallStackMessage(stackMsg);768    }769}770 771static void CompactMacroExpandedPieces(PathPieces &path,772                                       const SourceManager& SM);773 774PathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForSwitchOP(775    const PathDiagnosticConstruct &C, const CFGBlock *Dst,776    PathDiagnosticLocation &Start) const {777 778  const SourceManager &SM = getSourceManager();779  // Figure out what case arm we took.780  std::string sbuf;781  llvm::raw_string_ostream os(sbuf);782  PathDiagnosticLocation End;783 784  if (const Stmt *S = Dst->getLabel()) {785    End = PathDiagnosticLocation(S, SM, C.getCurrLocationContext());786 787    switch (S->getStmtClass()) {788    default:789      os << "No cases match in the switch statement. "790        "Control jumps to line "791        << End.asLocation().getExpansionLineNumber();792      break;793    case Stmt::DefaultStmtClass:794      os << "Control jumps to the 'default' case at line "795        << End.asLocation().getExpansionLineNumber();796      break;797 798    case Stmt::CaseStmtClass: {799      os << "Control jumps to 'case ";800      const auto *Case = cast<CaseStmt>(S);801      const Expr *LHS = Case->getLHS()->IgnoreParenImpCasts();802 803      // Determine if it is an enum.804      bool GetRawInt = true;805 806      if (const auto *DR = dyn_cast<DeclRefExpr>(LHS)) {807        // FIXME: Maybe this should be an assertion.  Are there cases808        // were it is not an EnumConstantDecl?809        const auto *D = dyn_cast<EnumConstantDecl>(DR->getDecl());810 811        if (D) {812          GetRawInt = false;813          os << *D;814        }815      }816 817      if (GetRawInt)818        os << LHS->EvaluateKnownConstInt(getASTContext());819 820      os << ":'  at line " << End.asLocation().getExpansionLineNumber();821      break;822    }823    }824  } else {825    os << "'Default' branch taken. ";826    End = ExecutionContinues(os, C);827  }828  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf);829}830 831PathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForGotoOP(832    const PathDiagnosticConstruct &C, const Stmt *S,833    PathDiagnosticLocation &Start) const {834  std::string sbuf;835  llvm::raw_string_ostream os(sbuf);836  const PathDiagnosticLocation &End =837      getEnclosingStmtLocation(S, C.getCurrLocationContext());838  os << "Control jumps to line " << End.asLocation().getExpansionLineNumber();839  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf);840}841 842PathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForBinaryOP(843    const PathDiagnosticConstruct &C, const Stmt *T, const CFGBlock *Src,844    const CFGBlock *Dst) const {845 846  const SourceManager &SM = getSourceManager();847 848  const auto *B = cast<BinaryOperator>(T);849  std::string sbuf;850  llvm::raw_string_ostream os(sbuf);851  os << "Left side of '";852  PathDiagnosticLocation Start, End;853 854  if (B->getOpcode() == BO_LAnd) {855    os << "&&"856      << "' is ";857 858    if (*(Src->succ_begin() + 1) == Dst) {859      os << "false";860      End = PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext());861      Start =862        PathDiagnosticLocation::createOperatorLoc(B, SM);863    } else {864      os << "true";865      Start =866          PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext());867      End = ExecutionContinues(C);868    }869  } else {870    assert(B->getOpcode() == BO_LOr);871    os << "||"872      << "' is ";873 874    if (*(Src->succ_begin() + 1) == Dst) {875      os << "false";876      Start =877          PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext());878      End = ExecutionContinues(C);879    } else {880      os << "true";881      End = PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext());882      Start =883        PathDiagnosticLocation::createOperatorLoc(B, SM);884    }885  }886  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf);887}888 889void PathDiagnosticBuilder::generateMinimalDiagForBlockEdge(890    PathDiagnosticConstruct &C, BlockEdge BE) const {891  const SourceManager &SM = getSourceManager();892  const LocationContext *LC = C.getCurrLocationContext();893  const CFGBlock *Src = BE.getSrc();894  const CFGBlock *Dst = BE.getDst();895  const Stmt *T = Src->getTerminatorStmt();896  if (!T)897    return;898 899  auto Start = PathDiagnosticLocation::createBegin(T, SM, LC);900  switch (T->getStmtClass()) {901  default:902    break;903 904  case Stmt::GotoStmtClass:905  case Stmt::IndirectGotoStmtClass: {906    if (const Stmt *S = C.getCurrentNode()->getNextStmtForDiagnostics())907      C.getActivePath().push_front(generateDiagForGotoOP(C, S, Start));908    break;909  }910 911  case Stmt::SwitchStmtClass: {912    C.getActivePath().push_front(generateDiagForSwitchOP(C, Dst, Start));913    break;914  }915 916  case Stmt::BreakStmtClass:917  case Stmt::ContinueStmtClass: {918    std::string sbuf;919    llvm::raw_string_ostream os(sbuf);920    PathDiagnosticLocation End = ExecutionContinues(os, C);921    C.getActivePath().push_front(922        std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf));923    break;924  }925 926  // Determine control-flow for ternary '?'.927  case Stmt::BinaryConditionalOperatorClass:928  case Stmt::ConditionalOperatorClass: {929    std::string sbuf;930    llvm::raw_string_ostream os(sbuf);931    os << "'?' condition is ";932 933    if (*(Src->succ_begin() + 1) == Dst)934      os << "false";935    else936      os << "true";937 938    PathDiagnosticLocation End = ExecutionContinues(C);939 940    if (const Stmt *S = End.asStmt())941      End = getEnclosingStmtLocation(S, C.getCurrLocationContext());942 943    C.getActivePath().push_front(944        std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf));945    break;946  }947 948  // Determine control-flow for short-circuited '&&' and '||'.949  case Stmt::BinaryOperatorClass: {950    if (!C.supportsLogicalOpControlFlow())951      break;952 953    C.getActivePath().push_front(generateDiagForBinaryOP(C, T, Src, Dst));954    break;955  }956 957  case Stmt::DoStmtClass:958    if (*(Src->succ_begin()) == Dst) {959      std::string sbuf;960      llvm::raw_string_ostream os(sbuf);961 962      os << "Loop condition is true. ";963      PathDiagnosticLocation End = ExecutionContinues(os, C);964 965      if (const Stmt *S = End.asStmt())966        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());967 968      C.getActivePath().push_front(969          std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf));970    } else {971      PathDiagnosticLocation End = ExecutionContinues(C);972 973      if (const Stmt *S = End.asStmt())974        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());975 976      C.getActivePath().push_front(977          std::make_shared<PathDiagnosticControlFlowPiece>(978              Start, End, "Loop condition is false.  Exiting loop"));979    }980    break;981 982  case Stmt::WhileStmtClass:983  case Stmt::ForStmtClass:984    if (*(Src->succ_begin() + 1) == Dst) {985      std::string sbuf;986      llvm::raw_string_ostream os(sbuf);987 988      os << "Loop condition is false. ";989      PathDiagnosticLocation End = ExecutionContinues(os, C);990      if (const Stmt *S = End.asStmt())991        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());992 993      C.getActivePath().push_front(994          std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, sbuf));995    } else {996      PathDiagnosticLocation End = ExecutionContinues(C);997      if (const Stmt *S = End.asStmt())998        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());999 1000      C.getActivePath().push_front(1001          std::make_shared<PathDiagnosticControlFlowPiece>(1002              Start, End, "Loop condition is true.  Entering loop body"));1003    }1004 1005    break;1006 1007  case Stmt::IfStmtClass: {1008    PathDiagnosticLocation End = ExecutionContinues(C);1009 1010    if (const Stmt *S = End.asStmt())1011      End = getEnclosingStmtLocation(S, C.getCurrLocationContext());1012 1013    if (*(Src->succ_begin() + 1) == Dst)1014      C.getActivePath().push_front(1015          std::make_shared<PathDiagnosticControlFlowPiece>(1016              Start, End, "Taking false branch"));1017    else1018      C.getActivePath().push_front(1019          std::make_shared<PathDiagnosticControlFlowPiece>(1020              Start, End, "Taking true branch"));1021 1022    break;1023  }1024  }1025}1026 1027//===----------------------------------------------------------------------===//1028// Functions for determining if a loop was executed 0 times.1029//===----------------------------------------------------------------------===//1030 1031static bool isLoop(const Stmt *Term) {1032  switch (Term->getStmtClass()) {1033    case Stmt::ForStmtClass:1034    case Stmt::WhileStmtClass:1035    case Stmt::ObjCForCollectionStmtClass:1036    case Stmt::CXXForRangeStmtClass:1037      return true;1038    default:1039      // Note that we intentionally do not include do..while here.1040      return false;1041  }1042}1043 1044static bool isJumpToFalseBranch(const BlockEdge *BE) {1045  const CFGBlock *Src = BE->getSrc();1046  assert(Src->succ_size() == 2);1047  return (*(Src->succ_begin()+1) == BE->getDst());1048}1049 1050static bool isContainedByStmt(const ParentMap &PM, const Stmt *S,1051                              const Stmt *SubS) {1052  while (SubS) {1053    if (SubS == S)1054      return true;1055    SubS = PM.getParent(SubS);1056  }1057  return false;1058}1059 1060static const Stmt *getStmtBeforeCond(const ParentMap &PM, const Stmt *Term,1061                                     const ExplodedNode *N) {1062  while (N) {1063    std::optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>();1064    if (SP) {1065      const Stmt *S = SP->getStmt();1066      if (!isContainedByStmt(PM, Term, S))1067        return S;1068    }1069    N = N->getFirstPred();1070  }1071  return nullptr;1072}1073 1074static bool isInLoopBody(const ParentMap &PM, const Stmt *S, const Stmt *Term) {1075  const Stmt *LoopBody = nullptr;1076  switch (Term->getStmtClass()) {1077    case Stmt::CXXForRangeStmtClass: {1078      const auto *FR = cast<CXXForRangeStmt>(Term);1079      if (isContainedByStmt(PM, FR->getInc(), S))1080        return true;1081      if (isContainedByStmt(PM, FR->getLoopVarStmt(), S))1082        return true;1083      LoopBody = FR->getBody();1084      break;1085    }1086    case Stmt::ForStmtClass: {1087      const auto *FS = cast<ForStmt>(Term);1088      if (isContainedByStmt(PM, FS->getInc(), S))1089        return true;1090      LoopBody = FS->getBody();1091      break;1092    }1093    case Stmt::ObjCForCollectionStmtClass: {1094      const auto *FC = cast<ObjCForCollectionStmt>(Term);1095      LoopBody = FC->getBody();1096      break;1097    }1098    case Stmt::WhileStmtClass:1099      LoopBody = cast<WhileStmt>(Term)->getBody();1100      break;1101    default:1102      return false;1103  }1104  return isContainedByStmt(PM, LoopBody, S);1105}1106 1107/// Adds a sanitized control-flow diagnostic edge to a path.1108static void addEdgeToPath(PathPieces &path,1109                          PathDiagnosticLocation &PrevLoc,1110                          PathDiagnosticLocation NewLoc) {1111  if (!NewLoc.isValid())1112    return;1113 1114  SourceLocation NewLocL = NewLoc.asLocation();1115  if (NewLocL.isInvalid())1116    return;1117 1118  if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) {1119    PrevLoc = NewLoc;1120    return;1121  }1122 1123  // Ignore self-edges, which occur when there are multiple nodes at the same1124  // statement.1125  if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt())1126    return;1127 1128  path.push_front(1129      std::make_shared<PathDiagnosticControlFlowPiece>(NewLoc, PrevLoc));1130  PrevLoc = NewLoc;1131}1132 1133/// A customized wrapper for CFGBlock::getTerminatorCondition()1134/// which returns the element for ObjCForCollectionStmts.1135static const Stmt *getTerminatorCondition(const CFGBlock *B) {1136  const Stmt *S = B->getTerminatorCondition();1137  if (const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(S))1138    return FS->getElement();1139  return S;1140}1141 1142constexpr llvm::StringLiteral StrEnteringLoop = "Entering loop body";1143constexpr llvm::StringLiteral StrLoopBodyZero = "Loop body executed 0 times";1144constexpr llvm::StringLiteral StrLoopRangeEmpty =1145    "Loop body skipped when range is empty";1146constexpr llvm::StringLiteral StrLoopCollectionEmpty =1147    "Loop body skipped when collection is empty";1148 1149static std::unique_ptr<FilesToLineNumsMap>1150findExecutedLines(const SourceManager &SM, const ExplodedNode *N);1151 1152void PathDiagnosticBuilder::generatePathDiagnosticsForNode(1153    PathDiagnosticConstruct &C, PathDiagnosticLocation &PrevLoc) const {1154  ProgramPoint P = C.getCurrentNode()->getLocation();1155  const SourceManager &SM = getSourceManager();1156 1157  // Have we encountered an entrance to a call?  It may be1158  // the case that we have not encountered a matching1159  // call exit before this point.  This means that the path1160  // terminated within the call itself.1161  if (auto CE = P.getAs<CallEnter>()) {1162 1163    if (C.shouldAddPathEdges()) {1164      // Add an edge to the start of the function.1165      const StackFrameContext *CalleeLC = CE->getCalleeContext();1166      const Decl *D = CalleeLC->getDecl();1167      // Add the edge only when the callee has body. We jump to the beginning1168      // of the *declaration*, however we expect it to be followed by the1169      // body. This isn't the case for autosynthesized property accessors in1170      // Objective-C. No need for a similar extra check for CallExit points1171      // because the exit edge comes from a statement (i.e. return),1172      // not from declaration.1173      if (D->hasBody())1174        addEdgeToPath(C.getActivePath(), PrevLoc,1175                      PathDiagnosticLocation::createBegin(D, SM));1176    }1177 1178    // Did we visit an entire call?1179    bool VisitedEntireCall = C.PD->isWithinCall();1180    C.PD->popActivePath();1181 1182    PathDiagnosticCallPiece *Call;1183    if (VisitedEntireCall) {1184      Call = cast<PathDiagnosticCallPiece>(C.getActivePath().front().get());1185    } else {1186      // The path terminated within a nested location context, create a new1187      // call piece to encapsulate the rest of the path pieces.1188      const Decl *Caller = CE->getLocationContext()->getDecl();1189      Call = PathDiagnosticCallPiece::construct(C.getActivePath(), Caller);1190      assert(C.getActivePath().size() == 1 &&1191             C.getActivePath().front().get() == Call);1192 1193      // Since we just transferred the path over to the call piece, reset the1194      // mapping of the active path to the current location context.1195      assert(C.isInLocCtxMap(&C.getActivePath()) &&1196             "When we ascend to a previously unvisited call, the active path's "1197             "address shouldn't change, but rather should be compacted into "1198             "a single CallEvent!");1199      C.updateLocCtxMap(&C.getActivePath(), C.getCurrLocationContext());1200 1201      // Record the location context mapping for the path within the call.1202      assert(!C.isInLocCtxMap(&Call->path) &&1203             "When we ascend to a previously unvisited call, this must be the "1204             "first time we encounter the caller context!");1205      C.updateLocCtxMap(&Call->path, CE->getCalleeContext());1206    }1207    Call->setCallee(*CE, SM);1208 1209    // Update the previous location in the active path.1210    PrevLoc = Call->getLocation();1211 1212    if (!C.CallStack.empty()) {1213      assert(C.CallStack.back().first == Call);1214      C.CallStack.pop_back();1215    }1216    return;1217  }1218 1219  assert(C.getCurrLocationContext() == C.getLocationContextForActivePath() &&1220         "The current position in the bug path is out of sync with the "1221         "location context associated with the active path!");1222 1223  // Have we encountered an exit from a function call?1224  if (std::optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {1225 1226    // We are descending into a call (backwards).  Construct1227    // a new call piece to contain the path pieces for that call.1228    auto Call = PathDiagnosticCallPiece::construct(*CE, SM);1229    // Record the mapping from call piece to LocationContext.1230    assert(!C.isInLocCtxMap(&Call->path) &&1231           "We just entered a call, this must've been the first time we "1232           "encounter its context!");1233    C.updateLocCtxMap(&Call->path, CE->getCalleeContext());1234 1235    if (C.shouldAddPathEdges()) {1236      // Add the edge to the return site.1237      addEdgeToPath(C.getActivePath(), PrevLoc, Call->callReturn);1238      PrevLoc.invalidate();1239    }1240 1241    auto *P = Call.get();1242    C.getActivePath().push_front(std::move(Call));1243 1244    // Make the contents of the call the active path for now.1245    C.PD->pushActivePath(&P->path);1246    C.CallStack.push_back(CallWithEntry(P, C.getCurrentNode()));1247    return;1248  }1249 1250  if (auto PS = P.getAs<PostStmt>()) {1251    if (!C.shouldAddPathEdges())1252      return;1253 1254    // Add an edge.  If this is an ObjCForCollectionStmt do1255    // not add an edge here as it appears in the CFG both1256    // as a terminator and as a terminator condition.1257    if (!isa<ObjCForCollectionStmt>(PS->getStmt())) {1258      PathDiagnosticLocation L =1259          PathDiagnosticLocation(PS->getStmt(), SM, C.getCurrLocationContext());1260      addEdgeToPath(C.getActivePath(), PrevLoc, L);1261    }1262 1263  } else if (auto BE = P.getAs<BlockEdge>()) {1264 1265    if (C.shouldAddControlNotes()) {1266      generateMinimalDiagForBlockEdge(C, *BE);1267    }1268 1269    if (!C.shouldAddPathEdges()) {1270      return;1271    }1272 1273    // Are we jumping to the head of a loop?  Add a special diagnostic.1274    if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {1275      PathDiagnosticLocation L(Loop, SM, C.getCurrLocationContext());1276      const Stmt *Body = nullptr;1277 1278      if (const auto *FS = dyn_cast<ForStmt>(Loop))1279        Body = FS->getBody();1280      else if (const auto *WS = dyn_cast<WhileStmt>(Loop))1281        Body = WS->getBody();1282      else if (const auto *OFS = dyn_cast<ObjCForCollectionStmt>(Loop)) {1283        Body = OFS->getBody();1284      } else if (const auto *FRS = dyn_cast<CXXForRangeStmt>(Loop)) {1285        Body = FRS->getBody();1286      }1287      // do-while statements are explicitly excluded here1288 1289      auto p = std::make_shared<PathDiagnosticEventPiece>(1290          L, "Looping back to the head of the loop");1291      p->setPrunable(true);1292 1293      addEdgeToPath(C.getActivePath(), PrevLoc, p->getLocation());1294      // We might've added a very similar control node already1295      if (!C.shouldAddControlNotes()) {1296        C.getActivePath().push_front(std::move(p));1297      }1298 1299      if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Body)) {1300        addEdgeToPath(C.getActivePath(), PrevLoc,1301                      PathDiagnosticLocation::createEndBrace(CS, SM));1302      }1303    }1304 1305    const CFGBlock *BSrc = BE->getSrc();1306    const ParentMap &PM = C.getParentMap();1307 1308    if (const Stmt *Term = BSrc->getTerminatorStmt()) {1309      // Are we jumping past the loop body without ever executing the1310      // loop (because the condition was false)?1311      if (isLoop(Term)) {1312        const Stmt *TermCond = getTerminatorCondition(BSrc);1313        bool IsInLoopBody = isInLoopBody(1314            PM, getStmtBeforeCond(PM, TermCond, C.getCurrentNode()), Term);1315 1316        StringRef str;1317 1318        if (isJumpToFalseBranch(&*BE)) {1319          if (!IsInLoopBody) {1320            if (isa<ObjCForCollectionStmt>(Term)) {1321              str = StrLoopCollectionEmpty;1322            } else if (isa<CXXForRangeStmt>(Term)) {1323              str = StrLoopRangeEmpty;1324            } else {1325              str = StrLoopBodyZero;1326            }1327          }1328        } else {1329          str = StrEnteringLoop;1330        }1331 1332        if (!str.empty()) {1333          PathDiagnosticLocation L(TermCond ? TermCond : Term, SM,1334                                   C.getCurrLocationContext());1335          auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str);1336          PE->setPrunable(true);1337          addEdgeToPath(C.getActivePath(), PrevLoc, PE->getLocation());1338 1339          // We might've added a very similar control node already1340          if (!C.shouldAddControlNotes()) {1341            C.getActivePath().push_front(std::move(PE));1342          }1343        }1344      } else if (isa<BreakStmt, ContinueStmt, GotoStmt>(Term)) {1345        PathDiagnosticLocation L(Term, SM, C.getCurrLocationContext());1346        addEdgeToPath(C.getActivePath(), PrevLoc, L);1347      }1348    }1349  }1350}1351 1352static std::unique_ptr<PathDiagnostic>1353generateDiagnosticForBasicReport(const BasicBugReport *R,1354                                 const Decl *AnalysisEntryPoint) {1355  const BugType &BT = R->getBugType();1356  return std::make_unique<PathDiagnostic>(1357      BT.getCheckerName(), R->getDeclWithIssue(), BT.getDescription(),1358      R->getDescription(), R->getShortDescription(/*UseFallback=*/false),1359      BT.getCategory(), R->getUniqueingLocation(), R->getUniqueingDecl(),1360      AnalysisEntryPoint, std::make_unique<FilesToLineNumsMap>());1361}1362 1363static std::unique_ptr<PathDiagnostic>1364generateEmptyDiagnosticForReport(const PathSensitiveBugReport *R,1365                                 const SourceManager &SM,1366                                 const Decl *AnalysisEntryPoint) {1367  const BugType &BT = R->getBugType();1368  return std::make_unique<PathDiagnostic>(1369      BT.getCheckerName(), R->getDeclWithIssue(), BT.getDescription(),1370      R->getDescription(), R->getShortDescription(/*UseFallback=*/false),1371      BT.getCategory(), R->getUniqueingLocation(), R->getUniqueingDecl(),1372      AnalysisEntryPoint, findExecutedLines(SM, R->getErrorNode()));1373}1374 1375static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) {1376  if (!S)1377    return nullptr;1378 1379  while (true) {1380    S = PM.getParentIgnoreParens(S);1381 1382    if (!S)1383      break;1384 1385    if (isa<FullExpr, CXXBindTemporaryExpr, SubstNonTypeTemplateParmExpr>(S))1386      continue;1387 1388    break;1389  }1390 1391  return S;1392}1393 1394static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {1395  switch (S->getStmtClass()) {1396    case Stmt::BinaryOperatorClass: {1397      const auto *BO = cast<BinaryOperator>(S);1398      if (!BO->isLogicalOp())1399        return false;1400      return BO->getLHS() == Cond || BO->getRHS() == Cond;1401    }1402    case Stmt::IfStmtClass:1403      return cast<IfStmt>(S)->getCond() == Cond;1404    case Stmt::ForStmtClass:1405      return cast<ForStmt>(S)->getCond() == Cond;1406    case Stmt::WhileStmtClass:1407      return cast<WhileStmt>(S)->getCond() == Cond;1408    case Stmt::DoStmtClass:1409      return cast<DoStmt>(S)->getCond() == Cond;1410    case Stmt::ChooseExprClass:1411      return cast<ChooseExpr>(S)->getCond() == Cond;1412    case Stmt::IndirectGotoStmtClass:1413      return cast<IndirectGotoStmt>(S)->getTarget() == Cond;1414    case Stmt::SwitchStmtClass:1415      return cast<SwitchStmt>(S)->getCond() == Cond;1416    case Stmt::BinaryConditionalOperatorClass:1417      return cast<BinaryConditionalOperator>(S)->getCond() == Cond;1418    case Stmt::ConditionalOperatorClass: {1419      const auto *CO = cast<ConditionalOperator>(S);1420      return CO->getCond() == Cond ||1421             CO->getLHS() == Cond ||1422             CO->getRHS() == Cond;1423    }1424    case Stmt::ObjCForCollectionStmtClass:1425      return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;1426    case Stmt::CXXForRangeStmtClass: {1427      const auto *FRS = cast<CXXForRangeStmt>(S);1428      return FRS->getCond() == Cond || FRS->getRangeInit() == Cond;1429    }1430    default:1431      return false;1432  }1433}1434 1435static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {1436  if (const auto *FS = dyn_cast<ForStmt>(FL))1437    return FS->getInc() == S || FS->getInit() == S;1438  if (const auto *FRS = dyn_cast<CXXForRangeStmt>(FL))1439    return FRS->getInc() == S || FRS->getRangeStmt() == S ||1440           FRS->getLoopVarStmt() || FRS->getRangeInit() == S;1441  return false;1442}1443 1444using OptimizedCallsSet = llvm::DenseSet<const PathDiagnosticCallPiece *>;1445 1446/// Adds synthetic edges from top-level statements to their subexpressions.1447///1448/// This avoids a "swoosh" effect, where an edge from a top-level statement A1449/// points to a sub-expression B.1 that's not at the start of B. In these cases,1450/// we'd like to see an edge from A to B, then another one from B to B.1.1451static void addContextEdges(PathPieces &pieces, const LocationContext *LC) {1452  const ParentMap &PM = LC->getParentMap();1453  PathPieces::iterator Prev = pieces.end();1454  for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;1455       Prev = I, ++I) {1456    auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());1457 1458    if (!Piece)1459      continue;1460 1461    PathDiagnosticLocation SrcLoc = Piece->getStartLocation();1462    SmallVector<PathDiagnosticLocation, 4> SrcContexts;1463 1464    PathDiagnosticLocation NextSrcContext = SrcLoc;1465    const Stmt *InnerStmt = nullptr;1466    while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {1467      SrcContexts.push_back(NextSrcContext);1468      InnerStmt = NextSrcContext.asStmt();1469      NextSrcContext = getEnclosingStmtLocation(InnerStmt, LC,1470                                                /*allowNested=*/true);1471    }1472 1473    // Repeatedly split the edge as necessary.1474    // This is important for nested logical expressions (||, &&, ?:) where we1475    // want to show all the levels of context.1476    while (true) {1477      const Stmt *Dst = Piece->getEndLocation().getStmtOrNull();1478 1479      // We are looking at an edge. Is the destination within a larger1480      // expression?1481      PathDiagnosticLocation DstContext =1482          getEnclosingStmtLocation(Dst, LC, /*allowNested=*/true);1483      if (!DstContext.isValid() || DstContext.asStmt() == Dst)1484        break;1485 1486      // If the source is in the same context, we're already good.1487      if (llvm::is_contained(SrcContexts, DstContext))1488        break;1489 1490      // Update the subexpression node to point to the context edge.1491      Piece->setStartLocation(DstContext);1492 1493      // Try to extend the previous edge if it's at the same level as the source1494      // context.1495      if (Prev != E) {1496        auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get());1497 1498        if (PrevPiece) {1499          if (const Stmt *PrevSrc =1500                  PrevPiece->getStartLocation().getStmtOrNull()) {1501            const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);1502            if (PrevSrcParent ==1503                getStmtParent(DstContext.getStmtOrNull(), PM)) {1504              PrevPiece->setEndLocation(DstContext);1505              break;1506            }1507          }1508        }1509      }1510 1511      // Otherwise, split the current edge into a context edge and a1512      // subexpression edge. Note that the context statement may itself have1513      // context.1514      auto P =1515          std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext);1516      Piece = P.get();1517      I = pieces.insert(I, std::move(P));1518    }1519  }1520}1521 1522/// Move edges from a branch condition to a branch target1523///        when the condition is simple.1524///1525/// This restructures some of the work of addContextEdges.  That function1526/// creates edges this may destroy, but they work together to create a more1527/// aesthetically set of edges around branches.  After the call to1528/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from1529/// the branch to the branch condition, and (3) an edge from the branch1530/// condition to the branch target.  We keep (1), but may wish to remove (2)1531/// and move the source of (3) to the branch if the branch condition is simple.1532static void simplifySimpleBranches(PathPieces &pieces) {1533  for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {1534    const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());1535 1536    if (!PieceI)1537      continue;1538 1539    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();1540    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();1541 1542    if (!s1Start || !s1End)1543      continue;1544 1545    PathPieces::iterator NextI = I; ++NextI;1546    if (NextI == E)1547      break;1548 1549    PathDiagnosticControlFlowPiece *PieceNextI = nullptr;1550 1551    while (true) {1552      if (NextI == E)1553        break;1554 1555      const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());1556      if (EV) {1557        StringRef S = EV->getString();1558        if (S == StrEnteringLoop || S == StrLoopBodyZero ||1559            S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) {1560          ++NextI;1561          continue;1562        }1563        break;1564      }1565 1566      PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());1567      break;1568    }1569 1570    if (!PieceNextI)1571      continue;1572 1573    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();1574    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();1575 1576    if (!s2Start || !s2End || s1End != s2Start)1577      continue;1578 1579    // We only perform this transformation for specific branch kinds.1580    // We don't want to do this for do..while, for example.1581    if (!isa<ForStmt, WhileStmt, IfStmt, ObjCForCollectionStmt,1582             CXXForRangeStmt>(s1Start))1583      continue;1584 1585    // Is s1End the branch condition?1586    if (!isConditionForTerminator(s1Start, s1End))1587      continue;1588 1589    // Perform the hoisting by eliminating (2) and changing the start1590    // location of (3).1591    PieceNextI->setStartLocation(PieceI->getStartLocation());1592    I = pieces.erase(I);1593  }1594}1595 1596/// Returns the number of bytes in the given (character-based) SourceRange.1597///1598/// If the locations in the range are not on the same line, returns1599/// std::nullopt.1600///1601/// Note that this does not do a precise user-visible character or column count.1602static std::optional<size_t> getLengthOnSingleLine(const SourceManager &SM,1603                                                   SourceRange Range) {1604  SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),1605                             SM.getExpansionRange(Range.getEnd()).getEnd());1606 1607  FileID FID = SM.getFileID(ExpansionRange.getBegin());1608  if (FID != SM.getFileID(ExpansionRange.getEnd()))1609    return std::nullopt;1610 1611  std::optional<MemoryBufferRef> Buffer = SM.getBufferOrNone(FID);1612  if (!Buffer)1613    return std::nullopt;1614 1615  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());1616  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());1617  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);1618 1619  // We're searching the raw bytes of the buffer here, which might include1620  // escaped newlines and such. That's okay; we're trying to decide whether the1621  // SourceRange is covering a large or small amount of space in the user's1622  // editor.1623  if (Snippet.find_first_of("\r\n") != StringRef::npos)1624    return std::nullopt;1625 1626  // This isn't Unicode-aware, but it doesn't need to be.1627  return Snippet.size();1628}1629 1630/// \sa getLengthOnSingleLine(SourceManager, SourceRange)1631static std::optional<size_t> getLengthOnSingleLine(const SourceManager &SM,1632                                                   const Stmt *S) {1633  return getLengthOnSingleLine(SM, S->getSourceRange());1634}1635 1636/// Eliminate two-edge cycles created by addContextEdges().1637///1638/// Once all the context edges are in place, there are plenty of cases where1639/// there's a single edge from a top-level statement to a subexpression,1640/// followed by a single path note, and then a reverse edge to get back out to1641/// the top level. If the statement is simple enough, the subexpression edges1642/// just add noise and make it harder to understand what's going on.1643///1644/// This function only removes edges in pairs, because removing only one edge1645/// might leave other edges dangling.1646///1647/// This will not remove edges in more complicated situations:1648/// - if there is more than one "hop" leading to or from a subexpression.1649/// - if there is an inlined call between the edges instead of a single event.1650/// - if the whole statement is large enough that having subexpression arrows1651///   might be helpful.1652static void removeContextCycles(PathPieces &Path, const SourceManager &SM) {1653  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {1654    // Pattern match the current piece and its successor.1655    const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());1656 1657    if (!PieceI) {1658      ++I;1659      continue;1660    }1661 1662    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();1663    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();1664 1665    PathPieces::iterator NextI = I; ++NextI;1666    if (NextI == E)1667      break;1668 1669    const auto *PieceNextI =1670        dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());1671 1672    if (!PieceNextI) {1673      if (isa<PathDiagnosticEventPiece>(NextI->get())) {1674        ++NextI;1675        if (NextI == E)1676          break;1677        PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());1678      }1679 1680      if (!PieceNextI) {1681        ++I;1682        continue;1683      }1684    }1685 1686    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();1687    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();1688 1689    if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {1690      const size_t MAX_SHORT_LINE_LENGTH = 80;1691      std::optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);1692      if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {1693        std::optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);1694        if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {1695          Path.erase(I);1696          I = Path.erase(NextI);1697          continue;1698        }1699      }1700    }1701 1702    ++I;1703  }1704}1705 1706/// Return true if X is contained by Y.1707static bool lexicalContains(const ParentMap &PM, const Stmt *X, const Stmt *Y) {1708  while (X) {1709    if (X == Y)1710      return true;1711    X = PM.getParent(X);1712  }1713  return false;1714}1715 1716// Remove short edges on the same line less than 3 columns in difference.1717static void removePunyEdges(PathPieces &path, const SourceManager &SM,1718                            const ParentMap &PM) {1719  bool erased = false;1720 1721  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;1722       erased ? I : ++I) {1723    erased = false;1724 1725    const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());1726 1727    if (!PieceI)1728      continue;1729 1730    const Stmt *start = PieceI->getStartLocation().getStmtOrNull();1731    const Stmt *end   = PieceI->getEndLocation().getStmtOrNull();1732 1733    if (!start || !end)1734      continue;1735 1736    const Stmt *endParent = PM.getParent(end);1737    if (!endParent)1738      continue;1739 1740    if (isConditionForTerminator(end, endParent))1741      continue;1742 1743    SourceLocation FirstLoc = start->getBeginLoc();1744    SourceLocation SecondLoc = end->getBeginLoc();1745 1746    if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))1747      continue;1748    if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))1749      std::swap(SecondLoc, FirstLoc);1750 1751    SourceRange EdgeRange(FirstLoc, SecondLoc);1752    std::optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);1753 1754    // If the statements are on different lines, continue.1755    if (!ByteWidth)1756      continue;1757 1758    const size_t MAX_PUNY_EDGE_LENGTH = 2;1759    if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {1760      // FIXME: There are enough /bytes/ between the endpoints of the edge, but1761      // there might not be enough /columns/. A proper user-visible column count1762      // is probably too expensive, though.1763      I = path.erase(I);1764      erased = true;1765      continue;1766    }1767  }1768}1769 1770static void removeIdenticalEvents(PathPieces &path) {1771  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {1772    const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());1773 1774    if (!PieceI)1775      continue;1776 1777    PathPieces::iterator NextI = I; ++NextI;1778    if (NextI == E)1779      return;1780 1781    const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());1782 1783    if (!PieceNextI)1784      continue;1785 1786    // Erase the second piece if it has the same exact message text.1787    if (PieceI->getString() == PieceNextI->getString()) {1788      path.erase(NextI);1789    }1790  }1791}1792 1793static bool optimizeEdges(const PathDiagnosticConstruct &C, PathPieces &path,1794                          OptimizedCallsSet &OCS) {1795  bool hasChanges = false;1796  const LocationContext *LC = C.getLocationContextFor(&path);1797  assert(LC);1798  const ParentMap &PM = LC->getParentMap();1799  const SourceManager &SM = C.getSourceManager();1800 1801  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {1802    // Optimize subpaths.1803    if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {1804      // Record the fact that a call has been optimized so we only do the1805      // effort once.1806      if (!OCS.count(CallI)) {1807        while (optimizeEdges(C, CallI->path, OCS)) {1808        }1809        OCS.insert(CallI);1810      }1811      ++I;1812      continue;1813    }1814 1815    // Pattern match the current piece and its successor.1816    auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());1817 1818    if (!PieceI) {1819      ++I;1820      continue;1821    }1822 1823    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();1824    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();1825    const Stmt *level1 = getStmtParent(s1Start, PM);1826    const Stmt *level2 = getStmtParent(s1End, PM);1827 1828    PathPieces::iterator NextI = I; ++NextI;1829    if (NextI == E)1830      break;1831 1832    const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());1833 1834    if (!PieceNextI) {1835      ++I;1836      continue;1837    }1838 1839    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();1840    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();1841    const Stmt *level3 = getStmtParent(s2Start, PM);1842    const Stmt *level4 = getStmtParent(s2End, PM);1843 1844    // Rule I.1845    //1846    // If we have two consecutive control edges whose end/begin locations1847    // are at the same level (e.g. statements or top-level expressions within1848    // a compound statement, or siblings share a single ancestor expression),1849    // then merge them if they have no interesting intermediate event.1850    //1851    // For example:1852    //1853    // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common1854    // parent is '1'.  Here 'x.y.z' represents the hierarchy of statements.1855    //1856    // NOTE: this will be limited later in cases where we add barriers1857    // to prevent this optimization.1858    if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {1859      PieceI->setEndLocation(PieceNextI->getEndLocation());1860      path.erase(NextI);1861      hasChanges = true;1862      continue;1863    }1864 1865    // Rule II.1866    //1867    // Eliminate edges between subexpressions and parent expressions1868    // when the subexpression is consumed.1869    //1870    // NOTE: this will be limited later in cases where we add barriers1871    // to prevent this optimization.1872    if (s1End && s1End == s2Start && level2) {1873      bool removeEdge = false;1874      // Remove edges into the increment or initialization of a1875      // loop that have no interleaving event.  This means that1876      // they aren't interesting.1877      if (isIncrementOrInitInForLoop(s1End, level2))1878        removeEdge = true;1879      // Next only consider edges that are not anchored on1880      // the condition of a terminator.  This are intermediate edges1881      // that we might want to trim.1882      else if (!isConditionForTerminator(level2, s1End)) {1883        // Trim edges on expressions that are consumed by1884        // the parent expression.1885        if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {1886          removeEdge = true;1887        }1888        // Trim edges where a lexical containment doesn't exist.1889        // For example:1890        //1891        //  X -> Y -> Z1892        //1893        // If 'Z' lexically contains Y (it is an ancestor) and1894        // 'X' does not lexically contain Y (it is a descendant OR1895        // it has no lexical relationship at all) then trim.1896        //1897        // This can eliminate edges where we dive into a subexpression1898        // and then pop back out, etc.1899        else if (s1Start && s2End &&1900                 lexicalContains(PM, s2Start, s2End) &&1901                 !lexicalContains(PM, s1End, s1Start)) {1902          removeEdge = true;1903        }1904        // Trim edges from a subexpression back to the top level if the1905        // subexpression is on a different line.1906        //1907        // A.1 -> A -> B1908        // becomes1909        // A.1 -> B1910        //1911        // These edges just look ugly and don't usually add anything.1912        else if (s1Start && s2End &&1913                 lexicalContains(PM, s1Start, s1End)) {1914          SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),1915                                PieceI->getStartLocation().asLocation());1916          if (!getLengthOnSingleLine(SM, EdgeRange))1917            removeEdge = true;1918        }1919      }1920 1921      if (removeEdge) {1922        PieceI->setEndLocation(PieceNextI->getEndLocation());1923        path.erase(NextI);1924        hasChanges = true;1925        continue;1926      }1927    }1928 1929    // Optimize edges for ObjC fast-enumeration loops.1930    //1931    // (X -> collection) -> (collection -> element)1932    //1933    // becomes:1934    //1935    // (X -> element)1936    if (s1End == s2Start) {1937      const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3);1938      if (FS && FS->getCollection()->IgnoreParens() == s2Start &&1939          s2End == FS->getElement()) {1940        PieceI->setEndLocation(PieceNextI->getEndLocation());1941        path.erase(NextI);1942        hasChanges = true;1943        continue;1944      }1945    }1946 1947    // No changes at this index?  Move to the next one.1948    ++I;1949  }1950 1951  if (!hasChanges) {1952    // Adjust edges into subexpressions to make them more uniform1953    // and aesthetically pleasing.1954    addContextEdges(path, LC);1955    // Remove "cyclical" edges that include one or more context edges.1956    removeContextCycles(path, SM);1957    // Hoist edges originating from branch conditions to branches1958    // for simple branches.1959    simplifySimpleBranches(path);1960    // Remove any puny edges left over after primary optimization pass.1961    removePunyEdges(path, SM, PM);1962    // Remove identical events.1963    removeIdenticalEvents(path);1964  }1965 1966  return hasChanges;1967}1968 1969/// Drop the very first edge in a path, which should be a function entry edge.1970///1971/// If the first edge is not a function entry edge (say, because the first1972/// statement had an invalid source location), this function does nothing.1973// FIXME: We should just generate invalid edges anyway and have the optimizer1974// deal with them.1975static void dropFunctionEntryEdge(const PathDiagnosticConstruct &C,1976                                  PathPieces &Path) {1977  const auto *FirstEdge =1978      dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());1979  if (!FirstEdge)1980    return;1981 1982  const Decl *D = C.getLocationContextFor(&Path)->getDecl();1983  PathDiagnosticLocation EntryLoc =1984      PathDiagnosticLocation::createBegin(D, C.getSourceManager());1985  if (FirstEdge->getStartLocation() != EntryLoc)1986    return;1987 1988  Path.pop_front();1989}1990 1991/// Populate executes lines with lines containing at least one diagnostics.1992static void updateExecutedLinesWithDiagnosticPieces(PathDiagnostic &PD) {1993 1994  PathPieces path = PD.path.flatten(/*ShouldFlattenMacros=*/true);1995  FilesToLineNumsMap &ExecutedLines = PD.getExecutedLines();1996 1997  for (const auto &P : path) {1998    FullSourceLoc Loc = P->getLocation().asLocation().getExpansionLoc();1999    FileID FID = Loc.getFileID();2000    unsigned LineNo = Loc.getLineNumber();2001    assert(FID.isValid());2002    ExecutedLines[FID].insert(LineNo);2003  }2004}2005 2006PathDiagnosticConstruct::PathDiagnosticConstruct(2007    const PathDiagnosticConsumer *PDC, const ExplodedNode *ErrorNode,2008    const PathSensitiveBugReport *R, const Decl *AnalysisEntryPoint)2009    : Consumer(PDC), CurrentNode(ErrorNode),2010      SM(CurrentNode->getCodeDecl().getASTContext().getSourceManager()),2011      PD(generateEmptyDiagnosticForReport(R, getSourceManager(),2012                                          AnalysisEntryPoint)) {2013  LCM[&PD->getActivePath()] = ErrorNode->getLocationContext();2014}2015 2016PathDiagnosticBuilder::PathDiagnosticBuilder(2017    BugReporterContext BRC, std::unique_ptr<ExplodedGraph> BugPath,2018    PathSensitiveBugReport *r, const ExplodedNode *ErrorNode,2019    std::unique_ptr<VisitorsDiagnosticsTy> VisitorsDiagnostics)2020    : BugReporterContext(BRC), BugPath(std::move(BugPath)), R(r),2021      ErrorNode(ErrorNode),2022      VisitorsDiagnostics(std::move(VisitorsDiagnostics)) {}2023 2024std::unique_ptr<PathDiagnostic>2025PathDiagnosticBuilder::generate(const PathDiagnosticConsumer *PDC) const {2026  const Decl *EntryPoint = getBugReporter().getAnalysisEntryPoint();2027  PathDiagnosticConstruct Construct(PDC, ErrorNode, R, EntryPoint);2028 2029  const SourceManager &SM = getSourceManager();2030  const AnalyzerOptions &Opts = getAnalyzerOptions();2031 2032  if (!PDC->shouldGenerateDiagnostics())2033    return generateEmptyDiagnosticForReport(R, getSourceManager(), EntryPoint);2034 2035  // Construct the final (warning) event for the bug report.2036  auto EndNotes = VisitorsDiagnostics->find(ErrorNode);2037  PathDiagnosticPieceRef LastPiece;2038  if (EndNotes != VisitorsDiagnostics->end()) {2039    assert(!EndNotes->second.empty());2040    LastPiece = EndNotes->second[0];2041  } else {2042    LastPiece = BugReporterVisitor::getDefaultEndPath(*this, ErrorNode,2043                                                      *getBugReport());2044  }2045  Construct.PD->setEndOfPath(LastPiece);2046 2047  PathDiagnosticLocation PrevLoc = Construct.PD->getLocation();2048  // From the error node to the root, ascend the bug path and construct the bug2049  // report.2050  while (Construct.ascendToPrevNode()) {2051    generatePathDiagnosticsForNode(Construct, PrevLoc);2052 2053    auto VisitorNotes = VisitorsDiagnostics->find(Construct.getCurrentNode());2054    if (VisitorNotes == VisitorsDiagnostics->end())2055      continue;2056 2057    // This is a workaround due to inability to put shared PathDiagnosticPiece2058    // into a FoldingSet.2059    std::set<llvm::FoldingSetNodeID> DeduplicationSet;2060 2061    // Add pieces from custom visitors.2062    for (const PathDiagnosticPieceRef &Note : VisitorNotes->second) {2063      llvm::FoldingSetNodeID ID;2064      Note->Profile(ID);2065      if (!DeduplicationSet.insert(ID).second)2066        continue;2067 2068      if (PDC->shouldAddPathEdges())2069        addEdgeToPath(Construct.getActivePath(), PrevLoc, Note->getLocation());2070      updateStackPiecesWithMessage(Note, Construct.CallStack);2071      Construct.getActivePath().push_front(Note);2072    }2073  }2074 2075  if (PDC->shouldAddPathEdges()) {2076    // Add an edge to the start of the function.2077    // We'll prune it out later, but it helps make diagnostics more uniform.2078    const StackFrameContext *CalleeLC =2079        Construct.getLocationContextForActivePath()->getStackFrame();2080    const Decl *D = CalleeLC->getDecl();2081    addEdgeToPath(Construct.getActivePath(), PrevLoc,2082                  PathDiagnosticLocation::createBegin(D, SM));2083  }2084 2085 2086  // Finally, prune the diagnostic path of uninteresting stuff.2087  if (!Construct.PD->path.empty()) {2088    if (R->shouldPrunePath() && Opts.ShouldPrunePaths) {2089      bool stillHasNotes =2090          removeUnneededCalls(Construct, Construct.getMutablePieces(), R);2091      assert(stillHasNotes);2092      (void)stillHasNotes;2093    }2094 2095    // Remove pop-up notes if needed.2096    if (!Opts.ShouldAddPopUpNotes)2097      removePopUpNotes(Construct.getMutablePieces());2098 2099    // Redirect all call pieces to have valid locations.2100    adjustCallLocations(Construct.getMutablePieces());2101    removePiecesWithInvalidLocations(Construct.getMutablePieces());2102 2103    if (PDC->shouldAddPathEdges()) {2104 2105      // Reduce the number of edges from a very conservative set2106      // to an aesthetically pleasing subset that conveys the2107      // necessary information.2108      OptimizedCallsSet OCS;2109      while (optimizeEdges(Construct, Construct.getMutablePieces(), OCS)) {2110      }2111 2112      // Drop the very first function-entry edge. It's not really necessary2113      // for top-level functions.2114      dropFunctionEntryEdge(Construct, Construct.getMutablePieces());2115    }2116 2117    // Remove messages that are basically the same, and edges that may not2118    // make sense.2119    // We have to do this after edge optimization in the Extensive mode.2120    removeRedundantMsgs(Construct.getMutablePieces());2121    removeEdgesToDefaultInitializers(Construct.getMutablePieces());2122  }2123 2124  if (Opts.ShouldDisplayMacroExpansions)2125    CompactMacroExpandedPieces(Construct.getMutablePieces(), SM);2126 2127  return std::move(Construct.PD);2128}2129 2130//===----------------------------------------------------------------------===//2131// Methods for BugType and subclasses.2132//===----------------------------------------------------------------------===//2133 2134void BugType::anchor() {}2135 2136//===----------------------------------------------------------------------===//2137// Methods for BugReport and subclasses.2138//===----------------------------------------------------------------------===//2139 2140LLVM_ATTRIBUTE_USED static bool2141isDependency(const CheckerRegistryData &Registry, StringRef CheckerName) {2142  for (const std::pair<StringRef, StringRef> &Pair : Registry.Dependencies) {2143    if (Pair.second == CheckerName)2144      return true;2145  }2146  return false;2147}2148 2149LLVM_ATTRIBUTE_USED static bool isHidden(const CheckerRegistryData &Registry,2150                                         StringRef CheckerName) {2151  for (const CheckerInfo &Checker : Registry.Checkers) {2152    if (Checker.FullName == CheckerName)2153      return Checker.IsHidden;2154  }2155  llvm_unreachable(2156      "Checker name not found in CheckerRegistry -- did you retrieve it "2157      "correctly from CheckerManager::getCurrentCheckerName?");2158}2159 2160PathSensitiveBugReport::PathSensitiveBugReport(2161    const BugType &bt, StringRef shortDesc, StringRef desc,2162    const ExplodedNode *errorNode, PathDiagnosticLocation LocationToUnique,2163    const Decl *DeclToUnique)2164    : BugReport(Kind::PathSensitive, bt, shortDesc, desc), ErrorNode(errorNode),2165      ErrorNodeRange(getStmt() ? getStmt()->getSourceRange() : SourceRange()),2166      UniqueingLocation(LocationToUnique), UniqueingDecl(DeclToUnique) {2167  assert(ErrorNode && "The error node must be non-null!");2168  assert(!isDependency(ErrorNode->getState()2169                           ->getAnalysisManager()2170                           .getCheckerManager()2171                           ->getCheckerRegistryData(),2172                       bt.getCheckerName()) &&2173         "Some checkers depend on this one! We don't allow dependency "2174         "checkers to emit warnings, because checkers should depend on "2175         "*modeling*, not *diagnostics*.");2176 2177  assert((bt.getCheckerName().starts_with("debug") ||2178          !isHidden(ErrorNode->getState()2179                        ->getAnalysisManager()2180                        .getCheckerManager()2181                        ->getCheckerRegistryData(),2182                    bt.getCheckerName())) &&2183         "Hidden checkers musn't emit diagnostics as they are by definition "2184         "non-user facing!");2185}2186 2187void PathSensitiveBugReport::addVisitor(2188    std::unique_ptr<BugReporterVisitor> visitor) {2189  if (!visitor)2190    return;2191 2192  llvm::FoldingSetNodeID ID;2193  visitor->Profile(ID);2194 2195  void *InsertPos = nullptr;2196  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {2197    return;2198  }2199 2200  Callbacks.push_back(std::move(visitor));2201}2202 2203void PathSensitiveBugReport::clearVisitors() {2204  Callbacks.clear();2205}2206 2207const Decl *PathSensitiveBugReport::getDeclWithIssue() const {2208  const ExplodedNode *N = getErrorNode();2209  if (!N)2210    return nullptr;2211 2212  const LocationContext *LC = N->getLocationContext();2213  return LC->getStackFrame()->getDecl();2214}2215 2216void BasicBugReport::Profile(llvm::FoldingSetNodeID& hash) const {2217  hash.AddInteger(static_cast<int>(getKind()));2218  hash.AddPointer(&BT);2219  hash.AddString(getShortDescription());2220  assert(Location.isValid());2221  Location.Profile(hash);2222 2223  for (SourceRange range : Ranges) {2224    if (!range.isValid())2225      continue;2226    hash.Add(range.getBegin());2227    hash.Add(range.getEnd());2228  }2229}2230 2231void PathSensitiveBugReport::Profile(llvm::FoldingSetNodeID &hash) const {2232  hash.AddInteger(static_cast<int>(getKind()));2233  hash.AddPointer(&BT);2234  hash.AddString(getShortDescription());2235  PathDiagnosticLocation UL = getUniqueingLocation();2236  if (UL.isValid()) {2237    UL.Profile(hash);2238  } else {2239    // TODO: The statement may be null if the report was emitted before any2240    // statements were executed. In particular, some checkers by design2241    // occasionally emit their reports in empty functions (that have no2242    // statements in their body). Do we profile correctly in this case?2243    hash.AddPointer(ErrorNode->getCurrentOrPreviousStmtForDiagnostics());2244  }2245 2246  for (SourceRange range : Ranges) {2247    if (!range.isValid())2248      continue;2249    hash.Add(range.getBegin());2250    hash.Add(range.getEnd());2251  }2252}2253 2254template <class T>2255static void insertToInterestingnessMap(2256    llvm::DenseMap<T, bugreporter::TrackingKind> &InterestingnessMap, T Val,2257    bugreporter::TrackingKind TKind) {2258  auto Result = InterestingnessMap.insert({Val, TKind});2259 2260  if (Result.second)2261    return;2262 2263  // Even if this symbol/region was already marked as interesting as a2264  // condition, if we later mark it as interesting again but with2265  // thorough tracking, overwrite it. Entities marked with thorough2266  // interestiness are the most important (or most interesting, if you will),2267  // and we wouldn't like to downplay their importance.2268 2269  switch (TKind) {2270    case bugreporter::TrackingKind::Thorough:2271      Result.first->getSecond() = bugreporter::TrackingKind::Thorough;2272      return;2273    case bugreporter::TrackingKind::Condition:2274      return;2275    }2276 2277    llvm_unreachable(2278        "BugReport::markInteresting currently can only handle 2 different "2279        "tracking kinds! Please define what tracking kind should this entitiy"2280        "have, if it was already marked as interesting with a different kind!");2281}2282 2283void PathSensitiveBugReport::markInteresting(SymbolRef sym,2284                                             bugreporter::TrackingKind TKind) {2285  if (!sym)2286    return;2287 2288  insertToInterestingnessMap(InterestingSymbols, sym, TKind);2289 2290  // FIXME: No tests exist for this code and it is questionable:2291  // How to handle multiple metadata for the same region?2292  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))2293    markInteresting(meta->getRegion(), TKind);2294}2295 2296void PathSensitiveBugReport::markNotInteresting(SymbolRef sym) {2297  if (!sym)2298    return;2299  InterestingSymbols.erase(sym);2300 2301  // The metadata part of markInteresting is not reversed here.2302  // Just making the same region not interesting is incorrect2303  // in specific cases.2304  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))2305    markNotInteresting(meta->getRegion());2306}2307 2308void PathSensitiveBugReport::markInteresting(const MemRegion *R,2309                                             bugreporter::TrackingKind TKind) {2310  if (!R)2311    return;2312 2313  R = R->getBaseRegion();2314  insertToInterestingnessMap(InterestingRegions, R, TKind);2315 2316  if (const auto *SR = dyn_cast<SymbolicRegion>(R))2317    markInteresting(SR->getSymbol(), TKind);2318}2319 2320void PathSensitiveBugReport::markNotInteresting(const MemRegion *R) {2321  if (!R)2322    return;2323 2324  R = R->getBaseRegion();2325  InterestingRegions.erase(R);2326 2327  if (const auto *SR = dyn_cast<SymbolicRegion>(R))2328    markNotInteresting(SR->getSymbol());2329}2330 2331void PathSensitiveBugReport::markInteresting(SVal V,2332                                             bugreporter::TrackingKind TKind) {2333  markInteresting(V.getAsRegion(), TKind);2334  markInteresting(V.getAsSymbol(), TKind);2335}2336 2337void PathSensitiveBugReport::markInteresting(const LocationContext *LC) {2338  if (!LC)2339    return;2340  InterestingLocationContexts.insert(LC);2341}2342 2343std::optional<bugreporter::TrackingKind>2344PathSensitiveBugReport::getInterestingnessKind(SVal V) const {2345  auto RKind = getInterestingnessKind(V.getAsRegion());2346  auto SKind = getInterestingnessKind(V.getAsSymbol());2347  if (!RKind)2348    return SKind;2349  if (!SKind)2350    return RKind;2351 2352  // If either is marked with throrough tracking, return that, we wouldn't like2353  // to downplay a note's importance by 'only' mentioning it as a condition.2354  switch(*RKind) {2355    case bugreporter::TrackingKind::Thorough:2356      return RKind;2357    case bugreporter::TrackingKind::Condition:2358      return SKind;2359  }2360 2361  llvm_unreachable(2362      "BugReport::getInterestingnessKind currently can only handle 2 different "2363      "tracking kinds! Please define what tracking kind should we return here "2364      "when the kind of getAsRegion() and getAsSymbol() is different!");2365  return std::nullopt;2366}2367 2368std::optional<bugreporter::TrackingKind>2369PathSensitiveBugReport::getInterestingnessKind(SymbolRef sym) const {2370  if (!sym)2371    return std::nullopt;2372  // We don't currently consider metadata symbols to be interesting2373  // even if we know their region is interesting. Is that correct behavior?2374  auto It = InterestingSymbols.find(sym);2375  if (It == InterestingSymbols.end())2376    return std::nullopt;2377  return It->getSecond();2378}2379 2380std::optional<bugreporter::TrackingKind>2381PathSensitiveBugReport::getInterestingnessKind(const MemRegion *R) const {2382  if (!R)2383    return std::nullopt;2384 2385  R = R->getBaseRegion();2386  auto It = InterestingRegions.find(R);2387  if (It != InterestingRegions.end())2388    return It->getSecond();2389 2390  if (const auto *SR = dyn_cast<SymbolicRegion>(R))2391    return getInterestingnessKind(SR->getSymbol());2392  return std::nullopt;2393}2394 2395bool PathSensitiveBugReport::isInteresting(SVal V) const {2396  return getInterestingnessKind(V).has_value();2397}2398 2399bool PathSensitiveBugReport::isInteresting(SymbolRef sym) const {2400  return getInterestingnessKind(sym).has_value();2401}2402 2403bool PathSensitiveBugReport::isInteresting(const MemRegion *R) const {2404  return getInterestingnessKind(R).has_value();2405}2406 2407bool PathSensitiveBugReport::isInteresting(const LocationContext *LC)  const {2408  if (!LC)2409    return false;2410  return InterestingLocationContexts.count(LC);2411}2412 2413const Stmt *PathSensitiveBugReport::getStmt() const {2414  if (!ErrorNode)2415    return nullptr;2416 2417  ProgramPoint ProgP = ErrorNode->getLocation();2418  const Stmt *S = nullptr;2419 2420  if (std::optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {2421    CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();2422    if (BE->getBlock() == &Exit)2423      S = ErrorNode->getPreviousStmtForDiagnostics();2424  }2425  if (!S)2426    S = ErrorNode->getStmtForDiagnostics();2427 2428  return S;2429}2430 2431ArrayRef<SourceRange>2432PathSensitiveBugReport::getRanges() const {2433  // If no custom ranges, add the range of the statement corresponding to2434  // the error node.2435  if (Ranges.empty() && isa_and_nonnull<Expr>(getStmt()))2436      return ErrorNodeRange;2437 2438  return Ranges;2439}2440 2441static bool exitingDestructor(const ExplodedNode *N) {2442  // Need to loop here, as some times the Error node is already outside of the2443  // destructor context, and the previous node is an edge that is also outside.2444  while (N && !N->getLocation().getAs<StmtPoint>()) {2445    N = N->getFirstPred();2446  }2447  return N && isa<CXXDestructorDecl>(N->getLocationContext()->getDecl());2448}2449 2450static const Stmt *2451findReasonableStmtCloseToFunctionExit(const ExplodedNode *N) {2452  if (exitingDestructor(N)) {2453    // If we are exiting a destructor call, it is more useful to point to2454    // the next stmt which is usually the temporary declaration.2455    if (const Stmt *S = N->getNextStmtForDiagnostics())2456      return S;2457    // If next stmt is not found, it is likely the end of a top-level2458    // function analysis. find the last execution statement then.2459  }2460  return N->getPreviousStmtForDiagnostics();2461}2462 2463PathDiagnosticLocation2464PathSensitiveBugReport::getLocation() const {2465  assert(ErrorNode && "Cannot create a location with a null node.");2466  const Stmt *S = ErrorNode->getStmtForDiagnostics();2467    ProgramPoint P = ErrorNode->getLocation();2468  const LocationContext *LC = P.getLocationContext();2469  SourceManager &SM =2470      ErrorNode->getState()->getStateManager().getContext().getSourceManager();2471 2472  if (!S) {2473    // If this is an implicit call, return the implicit call point location.2474      if (std::optional<PreImplicitCall> PIE = P.getAs<PreImplicitCall>())2475      return PathDiagnosticLocation(PIE->getLocation(), SM);2476    if (auto FE = P.getAs<FunctionExitPoint>()) {2477      if (const ReturnStmt *RS = FE->getStmt())2478        return PathDiagnosticLocation::createBegin(RS, SM, LC);2479 2480      S = findReasonableStmtCloseToFunctionExit(ErrorNode);2481    }2482    if (!S)2483      S = ErrorNode->getNextStmtForDiagnostics();2484  }2485 2486  if (S) {2487    // Attributed statements usually have corrupted begin locations,2488    // it's OK to ignore attributes for our purposes and deal with2489    // the actual annotated statement.2490    if (const auto *AS = dyn_cast<AttributedStmt>(S))2491      S = AS->getSubStmt();2492 2493    // For member expressions, return the location of the '.' or '->'.2494    if (const auto *ME = dyn_cast<MemberExpr>(S))2495      return PathDiagnosticLocation::createMemberLoc(ME, SM);2496 2497    // For binary operators, return the location of the operator.2498    if (const auto *B = dyn_cast<BinaryOperator>(S))2499      return PathDiagnosticLocation::createOperatorLoc(B, SM);2500 2501    if (P.getAs<PostStmtPurgeDeadSymbols>())2502      return PathDiagnosticLocation::createEnd(S, SM, LC);2503 2504    if (S->getBeginLoc().isValid())2505      return PathDiagnosticLocation(S, SM, LC);2506 2507    return PathDiagnosticLocation(2508        PathDiagnosticLocation::getValidSourceLocation(S, LC), SM);2509  }2510 2511  return PathDiagnosticLocation::createDeclEnd(ErrorNode->getLocationContext(),2512                                               SM);2513}2514 2515//===----------------------------------------------------------------------===//2516// Methods for BugReporter and subclasses.2517//===----------------------------------------------------------------------===//2518 2519const ExplodedGraph &PathSensitiveBugReporter::getGraph() const {2520  return Eng.getGraph();2521}2522 2523ProgramStateManager &PathSensitiveBugReporter::getStateManager() const {2524  return Eng.getStateManager();2525}2526 2527BugReporter::BugReporter(BugReporterData &D)2528    : D(D), UserSuppressions(D.getASTContext()) {}2529 2530BugReporter::~BugReporter() {2531  // Make sure reports are flushed.2532  assert(StrBugTypes.empty() &&2533         "Destroying BugReporter before diagnostics are emitted!");2534 2535  // Free the bug reports we are tracking.2536  for (const auto I : EQClassesVector)2537    delete I;2538}2539 2540void BugReporter::FlushReports() {2541  // We need to flush reports in deterministic order to ensure the order2542  // of the reports is consistent between runs.2543  for (const auto EQ : EQClassesVector)2544    FlushReport(*EQ);2545 2546  // BugReporter owns and deletes only BugTypes created implicitly through2547  // EmitBasicReport.2548  // FIXME: There are leaks from checkers that assume that the BugTypes they2549  // create will be destroyed by the BugReporter.2550  StrBugTypes.clear();2551}2552 2553//===----------------------------------------------------------------------===//2554// PathDiagnostics generation.2555//===----------------------------------------------------------------------===//2556 2557namespace {2558 2559/// A wrapper around an ExplodedGraph that contains a single path from the root2560/// to the error node.2561class BugPathInfo {2562public:2563  std::unique_ptr<ExplodedGraph> BugPath;2564  PathSensitiveBugReport *Report;2565  const ExplodedNode *ErrorNode;2566};2567 2568/// A wrapper around an ExplodedGraph whose leafs are all error nodes. Can2569/// conveniently retrieve bug paths from a single error node to the root.2570class BugPathGetter {2571  std::unique_ptr<ExplodedGraph> TrimmedGraph;2572 2573  using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;2574 2575  /// Assign each node with its distance from the root.2576  PriorityMapTy PriorityMap;2577 2578  /// Since the getErrorNode() or BugReport refers to the original ExplodedGraph,2579  /// we need to pair it to the error node of the constructed trimmed graph.2580  using ReportNewNodePair =2581      std::pair<PathSensitiveBugReport *, const ExplodedNode *>;2582  SmallVector<ReportNewNodePair, 32> ReportNodes;2583 2584  BugPathInfo CurrentBugPath;2585 2586  /// A helper class for sorting ExplodedNodes by priority.2587  template <bool Descending>2588  class PriorityCompare {2589    const PriorityMapTy &PriorityMap;2590 2591  public:2592    PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}2593 2594    bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {2595      PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);2596      PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);2597      PriorityMapTy::const_iterator E = PriorityMap.end();2598 2599      if (LI == E)2600        return Descending;2601      if (RI == E)2602        return !Descending;2603 2604      return Descending ? LI->second > RI->second2605                        : LI->second < RI->second;2606    }2607 2608    bool operator()(const ReportNewNodePair &LHS,2609                    const ReportNewNodePair &RHS) const {2610      return (*this)(LHS.second, RHS.second);2611    }2612  };2613 2614public:2615  BugPathGetter(const ExplodedGraph *OriginalGraph,2616                ArrayRef<PathSensitiveBugReport *> &bugReports);2617 2618  BugPathInfo *getNextBugPath();2619};2620 2621} // namespace2622 2623BugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph,2624                             ArrayRef<PathSensitiveBugReport *> &bugReports) {2625  SmallVector<const ExplodedNode *, 32> Nodes;2626  for (const auto I : bugReports) {2627    assert(I->isValid() &&2628           "We only allow BugReporterVisitors and BugReporter itself to "2629           "invalidate reports!");2630    Nodes.emplace_back(I->getErrorNode());2631  }2632 2633  // The trimmed graph is created in the body of the constructor to ensure2634  // that the DenseMaps have been initialized already.2635  InterExplodedGraphMap ForwardMap;2636  TrimmedGraph = OriginalGraph->trim(Nodes, &ForwardMap);2637 2638  // Find the (first) error node in the trimmed graph.  We just need to consult2639  // the node map which maps from nodes in the original graph to nodes2640  // in the new graph.2641  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;2642 2643  for (PathSensitiveBugReport *Report : bugReports) {2644    const ExplodedNode *NewNode = ForwardMap.lookup(Report->getErrorNode());2645    assert(NewNode &&2646           "Failed to construct a trimmed graph that contains this error "2647           "node!");2648    ReportNodes.emplace_back(Report, NewNode);2649    RemainingNodes.insert(NewNode);2650  }2651 2652  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");2653 2654  // Perform a forward BFS to find all the shortest paths.2655  std::queue<const ExplodedNode *> WS;2656 2657  WS.push(TrimmedGraph->getRoot());2658  unsigned Priority = 0;2659 2660  while (!WS.empty()) {2661    const ExplodedNode *Node = WS.front();2662    WS.pop();2663 2664    PriorityMapTy::iterator PriorityEntry;2665    bool IsNew;2666    std::tie(PriorityEntry, IsNew) = PriorityMap.insert({Node, Priority});2667    ++Priority;2668 2669    if (!IsNew) {2670      assert(PriorityEntry->second <= Priority);2671      continue;2672    }2673 2674    if (RemainingNodes.erase(Node))2675      if (RemainingNodes.empty())2676        break;2677 2678    for (const ExplodedNode *Succ : Node->succs())2679      WS.push(Succ);2680  }2681 2682  // Sort the error paths from longest to shortest.2683  llvm::sort(ReportNodes, PriorityCompare<true>(PriorityMap));2684}2685 2686BugPathInfo *BugPathGetter::getNextBugPath() {2687  if (ReportNodes.empty())2688    return nullptr;2689 2690  const ExplodedNode *OrigN;2691  std::tie(CurrentBugPath.Report, OrigN) = ReportNodes.pop_back_val();2692  assert(PriorityMap.contains(OrigN) && "error node not accessible from root");2693 2694  // Create a new graph with a single path. This is the graph that will be2695  // returned to the caller.2696  auto GNew = std::make_unique<ExplodedGraph>();2697 2698  // Now walk from the error node up the BFS path, always taking the2699  // predeccessor with the lowest number.2700  ExplodedNode *Succ = nullptr;2701  while (true) {2702    // Create the equivalent node in the new graph with the same state2703    // and location.2704    ExplodedNode *NewN = GNew->createUncachedNode(2705        OrigN->getLocation(), OrigN->getState(),2706        OrigN->getID(), OrigN->isSink());2707 2708    // Link up the new node with the previous node.2709    if (Succ)2710      Succ->addPredecessor(NewN, *GNew);2711    else2712      CurrentBugPath.ErrorNode = NewN;2713 2714    Succ = NewN;2715 2716    // Are we at the final node?2717    if (OrigN->pred_empty()) {2718      assert(OrigN == TrimmedGraph->getRoot() &&2719             "There should be only one root!");2720      GNew->designateAsRoot(NewN);2721      break;2722    }2723 2724    // Find the next predeccessor node.  We choose the node that is marked2725    // with the lowest BFS number.2726    OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),2727                              PriorityCompare<false>(PriorityMap));2728  }2729 2730  CurrentBugPath.BugPath = std::move(GNew);2731 2732  return &CurrentBugPath;2733}2734 2735/// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic2736/// object and collapses PathDiagosticPieces that are expanded by macros.2737static void CompactMacroExpandedPieces(PathPieces &path,2738                                       const SourceManager& SM) {2739  using MacroStackTy = std::vector<2740      std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>;2741 2742  using PiecesTy = std::vector<PathDiagnosticPieceRef>;2743 2744  MacroStackTy MacroStack;2745  PiecesTy Pieces;2746 2747  for (PathPieces::const_iterator I = path.begin(), E = path.end();2748       I != E; ++I) {2749    const auto &piece = *I;2750 2751    // Recursively compact calls.2752    if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {2753      CompactMacroExpandedPieces(call->path, SM);2754    }2755 2756    // Get the location of the PathDiagnosticPiece.2757    const FullSourceLoc Loc = piece->getLocation().asLocation();2758 2759    // Determine the instantiation location, which is the location we group2760    // related PathDiagnosticPieces.2761    SourceLocation InstantiationLoc = Loc.isMacroID() ?2762                                      SM.getExpansionLoc(Loc) :2763                                      SourceLocation();2764 2765    if (Loc.isFileID()) {2766      MacroStack.clear();2767      Pieces.push_back(piece);2768      continue;2769    }2770 2771    assert(Loc.isMacroID());2772 2773    // Is the PathDiagnosticPiece within the same macro group?2774    if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {2775      MacroStack.back().first->subPieces.push_back(piece);2776      continue;2777    }2778 2779    // We aren't in the same group.  Are we descending into a new macro2780    // or are part of an old one?2781    std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;2782 2783    SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?2784                                          SM.getExpansionLoc(Loc) :2785                                          SourceLocation();2786 2787    // Walk the entire macro stack.2788    while (!MacroStack.empty()) {2789      if (InstantiationLoc == MacroStack.back().second) {2790        MacroGroup = MacroStack.back().first;2791        break;2792      }2793 2794      if (ParentInstantiationLoc == MacroStack.back().second) {2795        MacroGroup = MacroStack.back().first;2796        break;2797      }2798 2799      MacroStack.pop_back();2800    }2801 2802    if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {2803      // Create a new macro group and add it to the stack.2804      auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(2805          PathDiagnosticLocation::createSingleLocation(piece->getLocation()));2806 2807      if (MacroGroup)2808        MacroGroup->subPieces.push_back(NewGroup);2809      else {2810        assert(InstantiationLoc.isFileID());2811        Pieces.push_back(NewGroup);2812      }2813 2814      MacroGroup = NewGroup;2815      MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));2816    }2817 2818    // Finally, add the PathDiagnosticPiece to the group.2819    MacroGroup->subPieces.push_back(piece);2820  }2821 2822  // Now take the pieces and construct a new PathDiagnostic.2823  path.clear();2824 2825  llvm::append_range(path, Pieces);2826}2827 2828/// Generate notes from all visitors.2829/// Notes associated with @c ErrorNode are generated using2830/// @c getEndPath, and the rest are generated with @c VisitNode.2831static std::unique_ptr<VisitorsDiagnosticsTy>2832generateVisitorsDiagnostics(PathSensitiveBugReport *R,2833                            const ExplodedNode *ErrorNode,2834                            BugReporterContext &BRC) {2835  std::unique_ptr<VisitorsDiagnosticsTy> Notes =2836      std::make_unique<VisitorsDiagnosticsTy>();2837  PathSensitiveBugReport::VisitorList visitors;2838 2839  // Run visitors on all nodes starting from the node *before* the last one.2840  // The last node is reserved for notes generated with @c getEndPath.2841  const ExplodedNode *NextNode = ErrorNode->getFirstPred();2842  while (NextNode) {2843 2844    // At each iteration, move all visitors from report to visitor list. This is2845    // important, because the Profile() functions of the visitors make sure that2846    // a visitor isn't added multiple times for the same node, but it's fine2847    // to add the a visitor with Profile() for different nodes (e.g. tracking2848    // a region at different points of the symbolic execution).2849    for (std::unique_ptr<BugReporterVisitor> &Visitor : R->visitors())2850      visitors.push_back(std::move(Visitor));2851 2852    R->clearVisitors();2853 2854    const ExplodedNode *Pred = NextNode->getFirstPred();2855    if (!Pred) {2856      PathDiagnosticPieceRef LastPiece;2857      for (auto &V : visitors) {2858        V->finalizeVisitor(BRC, ErrorNode, *R);2859 2860        if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) {2861          assert(!LastPiece &&2862                 "There can only be one final piece in a diagnostic.");2863          assert(Piece->getKind() == PathDiagnosticPiece::Kind::Event &&2864                 "The final piece must contain a message!");2865          LastPiece = std::move(Piece);2866          (*Notes)[ErrorNode].push_back(LastPiece);2867        }2868      }2869      break;2870    }2871 2872    for (auto &V : visitors) {2873      auto P = V->VisitNode(NextNode, BRC, *R);2874      if (P)2875        (*Notes)[NextNode].push_back(std::move(P));2876    }2877 2878    if (!R->isValid())2879      break;2880 2881    NextNode = Pred;2882  }2883 2884  return Notes;2885}2886 2887std::optional<PathDiagnosticBuilder> PathDiagnosticBuilder::findValidReport(2888    ArrayRef<PathSensitiveBugReport *> &bugReports,2889    PathSensitiveBugReporter &Reporter) {2890  Z3CrosscheckOracle Z3Oracle(Reporter.getAnalyzerOptions());2891 2892  BugPathGetter BugGraph(&Reporter.getGraph(), bugReports);2893 2894  while (BugPathInfo *BugPath = BugGraph.getNextBugPath()) {2895    // Find the BugReport with the original location.2896    PathSensitiveBugReport *R = BugPath->Report;2897    assert(R && "No original report found for sliced graph.");2898    assert(R->isValid() && "Report selected by trimmed graph marked invalid.");2899    const ExplodedNode *ErrorNode = BugPath->ErrorNode;2900 2901    // Register refutation visitors first, if they mark the bug invalid no2902    // further analysis is required2903    R->addVisitor<LikelyFalsePositiveSuppressionBRVisitor>();2904 2905    // Register additional node visitors.2906    R->addVisitor<NilReceiverBRVisitor>();2907    R->addVisitor<ConditionBRVisitor>();2908    R->addVisitor<TagVisitor>();2909 2910    BugReporterContext BRC(Reporter);2911 2912    // Run all visitors on a given graph, once.2913    std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes =2914        generateVisitorsDiagnostics(R, ErrorNode, BRC);2915 2916    if (R->isValid()) {2917      if (Reporter.getAnalyzerOptions().ShouldCrosscheckWithZ3) {2918        llvm::TimeTraceScope TCS{"Crosscheck with Z3"};2919        // If crosscheck is enabled, remove all visitors, add the refutation2920        // visitor and check again2921        R->clearVisitors();2922        Z3CrosscheckVisitor::Z3Result CrosscheckResult;2923        R->addVisitor<Z3CrosscheckVisitor>(CrosscheckResult,2924                                           Reporter.getAnalyzerOptions());2925 2926        // We don't overwrite the notes inserted by other visitors because the2927        // refutation manager does not add any new note to the path2928        generateVisitorsDiagnostics(R, BugPath->ErrorNode, BRC);2929        switch (Z3Oracle.interpretQueryResult(CrosscheckResult)) {2930        case Z3CrosscheckOracle::RejectReport:2931          ++NumTimesReportRefuted;2932          R->markInvalid("Infeasible constraints", /*Data=*/nullptr);2933          continue;2934        case Z3CrosscheckOracle::RejectEQClass:2935          ++NumTimesReportEQClassAborted;2936          return {};2937        case Z3CrosscheckOracle::AcceptReport:2938          ++NumTimesReportPassesZ3;2939          break;2940        }2941      }2942 2943      assert(R->isValid());2944      return PathDiagnosticBuilder(std::move(BRC), std::move(BugPath->BugPath),2945                                   BugPath->Report, BugPath->ErrorNode,2946                                   std::move(visitorNotes));2947    }2948  }2949 2950  ++NumTimesReportEQClassWasExhausted;2951  return {};2952}2953 2954std::unique_ptr<DiagnosticForConsumerMapTy>2955PathSensitiveBugReporter::generatePathDiagnostics(2956    ArrayRef<std::unique_ptr<PathDiagnosticConsumer>> consumers,2957    ArrayRef<PathSensitiveBugReport *> &bugReports) {2958  assert(!bugReports.empty());2959 2960  auto Out = std::make_unique<DiagnosticForConsumerMapTy>();2961 2962  std::optional<PathDiagnosticBuilder> PDB =2963      PathDiagnosticBuilder::findValidReport(bugReports, *this);2964 2965  if (PDB) {2966    for (const auto &PC : consumers) {2967      if (std::unique_ptr<PathDiagnostic> PD = PDB->generate(PC.get())) {2968        (*Out)[PC.get()] = std::move(PD);2969      }2970    }2971  }2972 2973  return Out;2974}2975 2976void BugReporter::emitReport(std::unique_ptr<BugReport> R) {2977  bool ValidSourceLoc = R->getLocation().isValid();2978  assert(ValidSourceLoc);2979  // If we mess up in a release build, we'd still prefer to just drop the bug2980  // instead of trying to go on.2981  if (!ValidSourceLoc)2982    return;2983 2984  // If the user asked to suppress this report, we should skip it.2985  if (UserSuppressions.isSuppressed(*R))2986    return;2987 2988  // Compute the bug report's hash to determine its equivalence class.2989  llvm::FoldingSetNodeID ID;2990  R->Profile(ID);2991 2992  // Lookup the equivance class.  If there isn't one, create it.2993  void *InsertPos;2994  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);2995 2996  if (!EQ) {2997    EQ = new BugReportEquivClass(std::move(R));2998    EQClasses.InsertNode(EQ, InsertPos);2999    EQClassesVector.push_back(EQ);3000  } else3001    EQ->AddReport(std::move(R));3002}3003 3004void PathSensitiveBugReporter::emitReport(std::unique_ptr<BugReport> R) {3005  if (auto PR = dyn_cast<PathSensitiveBugReport>(R.get()))3006    if (const ExplodedNode *E = PR->getErrorNode()) {3007      // An error node must either be a sink or have a tag, otherwise3008      // it could get reclaimed before the path diagnostic is created.3009      assert((E->isSink() || E->getLocation().getTag()) &&3010             "Error node must either be a sink or have a tag");3011 3012      const AnalysisDeclContext *DeclCtx =3013          E->getLocationContext()->getAnalysisDeclContext();3014      // The source of autosynthesized body can be handcrafted AST or a model3015      // file. The locations from handcrafted ASTs have no valid source3016      // locations and have to be discarded. Locations from model files should3017      // be preserved for processing and reporting.3018      if (DeclCtx->isBodyAutosynthesized() &&3019          !DeclCtx->isBodyAutosynthesizedFromModelFile())3020        return;3021    }3022 3023  BugReporter::emitReport(std::move(R));3024}3025 3026//===----------------------------------------------------------------------===//3027// Emitting reports in equivalence classes.3028//===----------------------------------------------------------------------===//3029 3030namespace {3031 3032struct FRIEC_WLItem {3033  const ExplodedNode *N;3034  ExplodedNode::const_succ_iterator I, E;3035 3036  FRIEC_WLItem(const ExplodedNode *n)3037      : N(n), I(N->succ_begin()), E(N->succ_end()) {}3038};3039 3040} // namespace3041 3042BugReport *PathSensitiveBugReporter::findReportInEquivalenceClass(3043    BugReportEquivClass &EQ, SmallVectorImpl<BugReport *> &bugReports) {3044  // If we don't need to suppress any of the nodes because they are3045  // post-dominated by a sink, simply add all the nodes in the equivalence class3046  // to 'Nodes'.  Any of the reports will serve as a "representative" report.3047  assert(EQ.getReports().size() > 0);3048  const BugType& BT = EQ.getReports()[0]->getBugType();3049  if (!BT.isSuppressOnSink()) {3050    BugReport *R = EQ.getReports()[0].get();3051    for (auto &J : EQ.getReports()) {3052      if (auto *PR = dyn_cast<PathSensitiveBugReport>(J.get())) {3053        R = PR;3054        bugReports.push_back(PR);3055      }3056    }3057    return R;3058  }3059 3060  // For bug reports that should be suppressed when all paths are post-dominated3061  // by a sink node, iterate through the reports in the equivalence class3062  // until we find one that isn't post-dominated (if one exists).  We use a3063  // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write3064  // this as a recursive function, but we don't want to risk blowing out the3065  // stack for very long paths.3066  BugReport *exampleReport = nullptr;3067 3068  for (const auto &I: EQ.getReports()) {3069    auto *R = dyn_cast<PathSensitiveBugReport>(I.get());3070    if (!R)3071      continue;3072 3073    const ExplodedNode *errorNode = R->getErrorNode();3074    if (errorNode->isSink()) {3075      llvm_unreachable(3076           "BugType::isSuppressSink() should not be 'true' for sink end nodes");3077    }3078    // No successors?  By definition this nodes isn't post-dominated by a sink.3079    if (errorNode->succ_empty()) {3080      bugReports.push_back(R);3081      if (!exampleReport)3082        exampleReport = R;3083      continue;3084    }3085 3086    // See if we are in a no-return CFG block. If so, treat this similarly3087    // to being post-dominated by a sink. This works better when the analysis3088    // is incomplete and we have never reached the no-return function call(s)3089    // that we'd inevitably bump into on this path.3090    if (const CFGBlock *ErrorB = errorNode->getCFGBlock())3091      if (ErrorB->isInevitablySinking())3092        continue;3093 3094    // At this point we know that 'N' is not a sink and it has at least one3095    // successor.  Use a DFS worklist to find a non-sink end-of-path node.3096    using WLItem = FRIEC_WLItem;3097    using DFSWorkList = SmallVector<WLItem, 10>;3098 3099    llvm::DenseMap<const ExplodedNode *, unsigned> Visited;3100 3101    DFSWorkList WL;3102    WL.push_back(errorNode);3103    Visited[errorNode] = 1;3104 3105    while (!WL.empty()) {3106      WLItem &WI = WL.back();3107      assert(!WI.N->succ_empty());3108 3109      for (; WI.I != WI.E; ++WI.I) {3110        const ExplodedNode *Succ = *WI.I;3111        // End-of-path node?3112        if (Succ->succ_empty()) {3113          // If we found an end-of-path node that is not a sink.3114          if (!Succ->isSink()) {3115            bugReports.push_back(R);3116            if (!exampleReport)3117              exampleReport = R;3118            WL.clear();3119            break;3120          }3121          // Found a sink?  Continue on to the next successor.3122          continue;3123        }3124        // Mark the successor as visited.  If it hasn't been explored,3125        // enqueue it to the DFS worklist.3126        unsigned &mark = Visited[Succ];3127        if (!mark) {3128          mark = 1;3129          WL.push_back(Succ);3130          break;3131        }3132      }3133 3134      // The worklist may have been cleared at this point.  First3135      // check if it is empty before checking the last item.3136      if (!WL.empty() && &WL.back() == &WI)3137        WL.pop_back();3138    }3139  }3140 3141  // ExampleReport will be NULL if all the nodes in the equivalence class3142  // were post-dominated by sinks.3143  return exampleReport;3144}3145 3146void BugReporter::FlushReport(BugReportEquivClass &EQ) {3147  llvm::TimeTraceScope TCS{timeTraceName(EQ), [&]() {3148                             return timeTraceMetadata(EQ, getSourceManager());3149                           }};3150  SmallVector<BugReport*, 10> bugReports;3151  BugReport *report = findReportInEquivalenceClass(EQ, bugReports);3152  if (!report)3153    return;3154 3155  // See whether we need to silence the checker/package.3156  for (const std::string &CheckerOrPackage :3157       getAnalyzerOptions().SilencedCheckersAndPackages) {3158    if (report->getBugType().getCheckerName().starts_with(CheckerOrPackage))3159      return;3160  }3161 3162  ArrayRef Consumers = getPathDiagnosticConsumers();3163  std::unique_ptr<DiagnosticForConsumerMapTy> Diagnostics =3164      generateDiagnosticForConsumerMap(report, Consumers, bugReports);3165 3166  for (auto &P : *Diagnostics) {3167    PathDiagnosticConsumer *Consumer = P.first;3168    std::unique_ptr<PathDiagnostic> &PD = P.second;3169 3170    // If the path is empty, generate a single step path with the location3171    // of the issue.3172    if (PD->path.empty()) {3173      PathDiagnosticLocation L = report->getLocation();3174      auto piece = std::make_unique<PathDiagnosticEventPiece>(3175        L, report->getDescription());3176      for (SourceRange Range : report->getRanges())3177        piece->addRange(Range);3178      PD->setEndOfPath(std::move(piece));3179    }3180 3181    PathPieces &Pieces = PD->getMutablePieces();3182    if (getAnalyzerOptions().ShouldDisplayNotesAsEvents) {3183      // For path diagnostic consumers that don't support extra notes,3184      // we may optionally convert those to path notes.3185      for (const auto &I : llvm::reverse(report->getNotes())) {3186        PathDiagnosticNotePiece *Piece = I.get();3187        auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>(3188          Piece->getLocation(), Piece->getString());3189        for (const auto &R: Piece->getRanges())3190          ConvertedPiece->addRange(R);3191 3192        Pieces.push_front(std::move(ConvertedPiece));3193      }3194    } else {3195      for (const auto &I : llvm::reverse(report->getNotes()))3196        Pieces.push_front(I);3197    }3198 3199    for (const auto &I : report->getFixits())3200      Pieces.back()->addFixit(I);3201 3202    updateExecutedLinesWithDiagnosticPieces(*PD);3203 3204    // If we are debugging, let's have the entry point as the first note.3205    if (getAnalyzerOptions().AnalyzerDisplayProgress ||3206        getAnalyzerOptions().AnalyzerNoteAnalysisEntryPoints) {3207      const Decl *EntryPoint = getAnalysisEntryPoint();3208      Pieces.push_front(std::make_shared<PathDiagnosticEventPiece>(3209          PathDiagnosticLocation{EntryPoint->getLocation(), getSourceManager()},3210          "[debug] analyzing from " +3211              AnalysisDeclContext::getFunctionName(EntryPoint)));3212    }3213    Consumer->HandlePathDiagnostic(std::move(PD));3214  }3215}3216 3217/// Insert all lines participating in the function signature \p Signature3218/// into \p ExecutedLines.3219static void populateExecutedLinesWithFunctionSignature(3220    const Decl *Signature, const SourceManager &SM,3221    FilesToLineNumsMap &ExecutedLines) {3222  SourceRange SignatureSourceRange;3223  const Stmt* Body = Signature->getBody();3224  if (const auto FD = dyn_cast<FunctionDecl>(Signature)) {3225    SignatureSourceRange = FD->getSourceRange();3226  } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) {3227    SignatureSourceRange = OD->getSourceRange();3228  } else {3229    return;3230  }3231  SourceLocation Start = SignatureSourceRange.getBegin();3232  SourceLocation End = Body ? Body->getSourceRange().getBegin()3233    : SignatureSourceRange.getEnd();3234  if (!Start.isValid() || !End.isValid())3235    return;3236  unsigned StartLine = SM.getExpansionLineNumber(Start);3237  unsigned EndLine = SM.getExpansionLineNumber(End);3238 3239  FileID FID = SM.getFileID(SM.getExpansionLoc(Start));3240  for (unsigned Line = StartLine; Line <= EndLine; Line++)3241    ExecutedLines[FID].insert(Line);3242}3243 3244static void populateExecutedLinesWithStmt(3245    const Stmt *S, const SourceManager &SM,3246    FilesToLineNumsMap &ExecutedLines) {3247  SourceLocation Loc = S->getSourceRange().getBegin();3248  if (!Loc.isValid())3249    return;3250  SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc);3251  FileID FID = SM.getFileID(ExpansionLoc);3252  unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc);3253  ExecutedLines[FID].insert(LineNo);3254}3255 3256/// \return all executed lines including function signatures on the path3257/// starting from \p N.3258static std::unique_ptr<FilesToLineNumsMap>3259findExecutedLines(const SourceManager &SM, const ExplodedNode *N) {3260  auto ExecutedLines = std::make_unique<FilesToLineNumsMap>();3261 3262  while (N) {3263    if (N->getFirstPred() == nullptr) {3264      // First node: show signature of the entrance point.3265      const Decl *D = N->getLocationContext()->getDecl();3266      populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines);3267    } else if (auto CE = N->getLocationAs<CallEnter>()) {3268      // Inlined function: show signature.3269      const Decl* D = CE->getCalleeContext()->getDecl();3270      populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines);3271    } else if (const Stmt *S = N->getStmtForDiagnostics()) {3272      populateExecutedLinesWithStmt(S, SM, *ExecutedLines);3273 3274      // Show extra context for some parent kinds.3275      const Stmt *P = N->getParentMap().getParent(S);3276 3277      // The path exploration can die before the node with the associated3278      // return statement is generated, but we do want to show the whole3279      // return.3280      if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) {3281        populateExecutedLinesWithStmt(RS, SM, *ExecutedLines);3282        P = N->getParentMap().getParent(RS);3283      }3284 3285      if (isa_and_nonnull<SwitchCase, LabelStmt>(P))3286        populateExecutedLinesWithStmt(P, SM, *ExecutedLines);3287    }3288 3289    N = N->getFirstPred();3290  }3291  return ExecutedLines;3292}3293 3294std::unique_ptr<DiagnosticForConsumerMapTy>3295BugReporter::generateDiagnosticForConsumerMap(3296    BugReport *exampleReport,3297    ArrayRef<std::unique_ptr<PathDiagnosticConsumer>> consumers,3298    ArrayRef<BugReport *> bugReports) {3299  auto *basicReport = cast<BasicBugReport>(exampleReport);3300  auto Out = std::make_unique<DiagnosticForConsumerMapTy>();3301  for (const auto &Consumer : consumers)3302    (*Out)[Consumer.get()] =3303        generateDiagnosticForBasicReport(basicReport, AnalysisEntryPoint);3304  return Out;3305}3306 3307static PathDiagnosticCallPiece *3308getFirstStackedCallToHeaderFile(PathDiagnosticCallPiece *CP,3309                                const SourceManager &SMgr) {3310  SourceLocation CallLoc = CP->callEnter.asLocation();3311 3312  // If the call is within a macro, don't do anything (for now).3313  if (CallLoc.isMacroID())3314    return nullptr;3315 3316  assert(AnalysisManager::isInCodeFile(CallLoc, SMgr) &&3317         "The call piece should not be in a header file.");3318 3319  // Check if CP represents a path through a function outside of the main file.3320  if (!AnalysisManager::isInCodeFile(CP->callEnterWithin.asLocation(), SMgr))3321    return CP;3322 3323  const PathPieces &Path = CP->path;3324  if (Path.empty())3325    return nullptr;3326 3327  // Check if the last piece in the callee path is a call to a function outside3328  // of the main file.3329  if (auto *CPInner = dyn_cast<PathDiagnosticCallPiece>(Path.back().get()))3330    return getFirstStackedCallToHeaderFile(CPInner, SMgr);3331 3332  // Otherwise, the last piece is in the main file.3333  return nullptr;3334}3335 3336static void resetDiagnosticLocationToMainFile(PathDiagnostic &PD) {3337  if (PD.path.empty())3338    return;3339 3340  PathDiagnosticPiece *LastP = PD.path.back().get();3341  assert(LastP);3342  const SourceManager &SMgr = LastP->getLocation().getManager();3343 3344  // We only need to check if the report ends inside headers, if the last piece3345  // is a call piece.3346  if (auto *CP = dyn_cast<PathDiagnosticCallPiece>(LastP)) {3347    CP = getFirstStackedCallToHeaderFile(CP, SMgr);3348    if (CP) {3349      // Mark the piece.3350       CP->setAsLastInMainSourceFile();3351 3352      // Update the path diagnostic message.3353      const auto *ND = dyn_cast<NamedDecl>(CP->getCallee());3354      if (ND) {3355        SmallString<200> buf;3356        llvm::raw_svector_ostream os(buf);3357        os << " (within a call to '" << ND->getDeclName() << "')";3358        PD.appendToDesc(os.str());3359      }3360 3361      // Reset the report containing declaration and location.3362      PD.setDeclWithIssue(CP->getCaller());3363      PD.setLocation(CP->getLocation());3364 3365      return;3366    }3367  }3368}3369 3370std::unique_ptr<DiagnosticForConsumerMapTy>3371PathSensitiveBugReporter::generateDiagnosticForConsumerMap(3372    BugReport *exampleReport,3373    ArrayRef<std::unique_ptr<PathDiagnosticConsumer>> consumers,3374    ArrayRef<BugReport *> bugReports) {3375  if (isa<BasicBugReport>(exampleReport))3376    return BugReporter::generateDiagnosticForConsumerMap(exampleReport,3377                                                         consumers, bugReports);3378 3379  // Generate the full path sensitive diagnostic, using the generation scheme3380  // specified by the PathDiagnosticConsumer. Note that we have to generate3381  // path diagnostics even for consumers which do not support paths, because3382  // the BugReporterVisitors may mark this bug as a false positive.3383  assert(!bugReports.empty());3384  MaxBugClassSize.updateMax(bugReports.size());3385 3386  // Avoid copying the whole array because there may be a lot of reports.3387  ArrayRef<PathSensitiveBugReport *> convertedArrayOfReports(3388      reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.begin()),3389      reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.end()));3390  std::unique_ptr<DiagnosticForConsumerMapTy> Out = generatePathDiagnostics(3391      consumers, convertedArrayOfReports);3392 3393  if (Out->empty())3394    return Out;3395 3396  MaxValidBugClassSize.updateMax(bugReports.size());3397 3398  // Examine the report and see if the last piece is in a header. Reset the3399  // report location to the last piece in the main source file.3400  const AnalyzerOptions &Opts = getAnalyzerOptions();3401  for (auto const &P : *Out)3402    if (Opts.ShouldReportIssuesInMainSourceFile && !Opts.AnalyzeAll)3403      resetDiagnosticLocationToMainFile(*P.second);3404 3405  return Out;3406}3407 3408void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,3409                                  const CheckerFrontend *Checker,3410                                  StringRef Name, StringRef Category,3411                                  StringRef Str, PathDiagnosticLocation Loc,3412                                  ArrayRef<SourceRange> Ranges,3413                                  ArrayRef<FixItHint> Fixits) {3414  EmitBasicReport(DeclWithIssue, Checker->getName(), Name, Category, Str, Loc,3415                  Ranges, Fixits);3416}3417 3418void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,3419                                  CheckerNameRef CheckName,3420                                  StringRef name, StringRef category,3421                                  StringRef str, PathDiagnosticLocation Loc,3422                                  ArrayRef<SourceRange> Ranges,3423                                  ArrayRef<FixItHint> Fixits) {3424  // 'BT' is owned by BugReporter.3425  BugType *BT = getBugTypeForName(CheckName, name, category);3426  auto R = std::make_unique<BasicBugReport>(*BT, str, Loc);3427  R->setDeclWithIssue(DeclWithIssue);3428  for (const auto &SR : Ranges)3429    R->addRange(SR);3430  for (const auto &FH : Fixits)3431    R->addFixItHint(FH);3432  emitReport(std::move(R));3433}3434 3435BugType *BugReporter::getBugTypeForName(CheckerNameRef CheckName,3436                                        StringRef name, StringRef category) {3437  SmallString<136> fullDesc;3438  llvm::raw_svector_ostream(fullDesc)3439      << CheckName << ":" << name << ":" << category;3440  std::unique_ptr<BugType> &BT = StrBugTypes[fullDesc];3441  if (!BT)3442    BT = std::make_unique<BugType>(CheckName, name, category);3443  return BT.get();3444}3445