1341825Sdim//===- BugReporter.cpp - Generate PathDiagnostics for bugs ----------------===// 2218887Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218887Sdim// 7218887Sdim//===----------------------------------------------------------------------===// 8218887Sdim// 9218887Sdim// This file defines BugReporter, a utility class for generating 10218887Sdim// PathDiagnostics. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 15341825Sdim#include "clang/AST/Decl.h" 16341825Sdim#include "clang/AST/DeclBase.h" 17234353Sdim#include "clang/AST/DeclObjC.h" 18218887Sdim#include "clang/AST/Expr.h" 19261991Sdim#include "clang/AST/ExprCXX.h" 20218887Sdim#include "clang/AST/ParentMap.h" 21341825Sdim#include "clang/AST/Stmt.h" 22276479Sdim#include "clang/AST/StmtCXX.h" 23218887Sdim#include "clang/AST/StmtObjC.h" 24341825Sdim#include "clang/Analysis/AnalysisDeclContext.h" 25249423Sdim#include "clang/Analysis/CFG.h" 26314564Sdim#include "clang/Analysis/CFGStmtMap.h" 27360784Sdim#include "clang/Analysis/PathDiagnostic.h" 28249423Sdim#include "clang/Analysis/ProgramPoint.h" 29341825Sdim#include "clang/Basic/LLVM.h" 30341825Sdim#include "clang/Basic/SourceLocation.h" 31218887Sdim#include "clang/Basic/SourceManager.h" 32341825Sdim#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" 33341825Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h" 34249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 35341825Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 36341825Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 37341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 38249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 39341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 40341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 41341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 42341825Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 43341825Sdim#include "llvm/ADT/ArrayRef.h" 44218887Sdim#include "llvm/ADT/DenseMap.h" 45341825Sdim#include "llvm/ADT/DenseSet.h" 46341825Sdim#include "llvm/ADT/FoldingSet.h" 47341825Sdim#include "llvm/ADT/None.h" 48341825Sdim#include "llvm/ADT/Optional.h" 49249423Sdim#include "llvm/ADT/STLExtras.h" 50341825Sdim#include "llvm/ADT/SmallPtrSet.h" 51234353Sdim#include "llvm/ADT/SmallString.h" 52341825Sdim#include "llvm/ADT/SmallVector.h" 53249423Sdim#include "llvm/ADT/Statistic.h" 54341825Sdim#include "llvm/ADT/StringRef.h" 55341825Sdim#include "llvm/ADT/iterator_range.h" 56341825Sdim#include "llvm/Support/Casting.h" 57341825Sdim#include "llvm/Support/Compiler.h" 58341825Sdim#include "llvm/Support/ErrorHandling.h" 59341825Sdim#include "llvm/Support/MemoryBuffer.h" 60249423Sdim#include "llvm/Support/raw_ostream.h" 61341825Sdim#include <algorithm> 62341825Sdim#include <cassert> 63341825Sdim#include <cstddef> 64341825Sdim#include <iterator> 65276479Sdim#include <memory> 66218887Sdim#include <queue> 67341825Sdim#include <string> 68341825Sdim#include <tuple> 69341825Sdim#include <utility> 70341825Sdim#include <vector> 71218887Sdim 72218887Sdimusing namespace clang; 73218887Sdimusing namespace ento; 74360784Sdimusing namespace llvm; 75218887Sdim 76276479Sdim#define DEBUG_TYPE "BugReporter" 77276479Sdim 78249423SdimSTATISTIC(MaxBugClassSize, 79249423Sdim "The maximum number of bug reports in the same equivalence class"); 80249423SdimSTATISTIC(MaxValidBugClassSize, 81249423Sdim "The maximum number of bug reports in the same equivalence class " 82249423Sdim "where at least one report is valid (not suppressed)"); 83249423Sdim 84341825SdimBugReporterVisitor::~BugReporterVisitor() = default; 85218887Sdim 86234353Sdimvoid BugReporterContext::anchor() {} 87234353Sdim 88218887Sdim//===----------------------------------------------------------------------===// 89360784Sdim// PathDiagnosticBuilder and its associated routines and helper objects. 90218887Sdim//===----------------------------------------------------------------------===// 91218887Sdim 92360784Sdimnamespace { 93218887Sdim 94360784Sdim/// A (CallPiece, node assiciated with its CallEnter) pair. 95360784Sdimusing CallWithEntry = 96360784Sdim std::pair<PathDiagnosticCallPiece *, const ExplodedNode *>; 97360784Sdimusing CallWithEntryStack = SmallVector<CallWithEntry, 6>; 98360784Sdim 99360784Sdim/// Map from each node to the diagnostic pieces visitors emit for them. 100360784Sdimusing VisitorsDiagnosticsTy = 101360784Sdim llvm::DenseMap<const ExplodedNode *, std::vector<PathDiagnosticPieceRef>>; 102360784Sdim 103360784Sdim/// A map from PathDiagnosticPiece to the LocationContext of the inlined 104360784Sdim/// function call it represents. 105360784Sdimusing LocationContextMap = 106360784Sdim llvm::DenseMap<const PathPieces *, const LocationContext *>; 107360784Sdim 108360784Sdim/// A helper class that contains everything needed to construct a 109360784Sdim/// PathDiagnostic object. It does no much more then providing convenient 110360784Sdim/// getters and some well placed asserts for extra security. 111360784Sdimclass PathDiagnosticConstruct { 112360784Sdim /// The consumer we're constructing the bug report for. 113360784Sdim const PathDiagnosticConsumer *Consumer; 114360784Sdim /// Our current position in the bug path, which is owned by 115360784Sdim /// PathDiagnosticBuilder. 116360784Sdim const ExplodedNode *CurrentNode; 117360784Sdim /// A mapping from parts of the bug path (for example, a function call, which 118360784Sdim /// would span backwards from a CallExit to a CallEnter with the nodes in 119360784Sdim /// between them) with the location contexts it is associated with. 120360784Sdim LocationContextMap LCM; 121360784Sdim const SourceManager &SM; 122360784Sdim 123360784Sdimpublic: 124360784Sdim /// We keep stack of calls to functions as we're ascending the bug path. 125360784Sdim /// TODO: PathDiagnostic has a stack doing the same thing, shouldn't we use 126360784Sdim /// that instead? 127360784Sdim CallWithEntryStack CallStack; 128360784Sdim /// The bug report we're constructing. For ease of use, this field is kept 129360784Sdim /// public, though some "shortcut" getters are provided for commonly used 130360784Sdim /// methods of PathDiagnostic. 131360784Sdim std::unique_ptr<PathDiagnostic> PD; 132360784Sdim 133360784Sdimpublic: 134360784Sdim PathDiagnosticConstruct(const PathDiagnosticConsumer *PDC, 135360784Sdim const ExplodedNode *ErrorNode, 136360784Sdim const PathSensitiveBugReport *R); 137360784Sdim 138360784Sdim /// \returns the location context associated with the current position in the 139360784Sdim /// bug path. 140360784Sdim const LocationContext *getCurrLocationContext() const { 141360784Sdim assert(CurrentNode && "Already reached the root!"); 142360784Sdim return CurrentNode->getLocationContext(); 143360784Sdim } 144360784Sdim 145360784Sdim /// Same as getCurrLocationContext (they should always return the same 146360784Sdim /// location context), but works after reaching the root of the bug path as 147360784Sdim /// well. 148360784Sdim const LocationContext *getLocationContextForActivePath() const { 149360784Sdim return LCM.find(&PD->getActivePath())->getSecond(); 150360784Sdim } 151360784Sdim 152360784Sdim const ExplodedNode *getCurrentNode() const { return CurrentNode; } 153360784Sdim 154360784Sdim /// Steps the current node to its predecessor. 155360784Sdim /// \returns whether we reached the root of the bug path. 156360784Sdim bool ascendToPrevNode() { 157360784Sdim CurrentNode = CurrentNode->getFirstPred(); 158360784Sdim return static_cast<bool>(CurrentNode); 159360784Sdim } 160360784Sdim 161360784Sdim const ParentMap &getParentMap() const { 162360784Sdim return getCurrLocationContext()->getParentMap(); 163360784Sdim } 164360784Sdim 165360784Sdim const SourceManager &getSourceManager() const { return SM; } 166360784Sdim 167360784Sdim const Stmt *getParent(const Stmt *S) const { 168360784Sdim return getParentMap().getParent(S); 169360784Sdim } 170360784Sdim 171360784Sdim void updateLocCtxMap(const PathPieces *Path, const LocationContext *LC) { 172360784Sdim assert(Path && LC); 173360784Sdim LCM[Path] = LC; 174360784Sdim } 175360784Sdim 176360784Sdim const LocationContext *getLocationContextFor(const PathPieces *Path) const { 177360784Sdim assert(LCM.count(Path) && 178360784Sdim "Failed to find the context associated with these pieces!"); 179360784Sdim return LCM.find(Path)->getSecond(); 180360784Sdim } 181360784Sdim 182360784Sdim bool isInLocCtxMap(const PathPieces *Path) const { return LCM.count(Path); } 183360784Sdim 184360784Sdim PathPieces &getActivePath() { return PD->getActivePath(); } 185360784Sdim PathPieces &getMutablePieces() { return PD->getMutablePieces(); } 186360784Sdim 187360784Sdim bool shouldAddPathEdges() const { return Consumer->shouldAddPathEdges(); } 188360784Sdim bool shouldGenerateDiagnostics() const { 189360784Sdim return Consumer->shouldGenerateDiagnostics(); 190360784Sdim } 191360784Sdim bool supportsLogicalOpControlFlow() const { 192360784Sdim return Consumer->supportsLogicalOpControlFlow(); 193360784Sdim } 194360784Sdim}; 195360784Sdim 196360784Sdim/// Contains every contextual information needed for constructing a 197360784Sdim/// PathDiagnostic object for a given bug report. This class and its fields are 198360784Sdim/// immutable, and passes a BugReportConstruct object around during the 199360784Sdim/// construction. 200360784Sdimclass PathDiagnosticBuilder : public BugReporterContext { 201360784Sdim /// A linear path from the error node to the root. 202360784Sdim std::unique_ptr<const ExplodedGraph> BugPath; 203360784Sdim /// The bug report we're describing. Visitors create their diagnostics with 204360784Sdim /// them being the last entities being able to modify it (for example, 205360784Sdim /// changing interestingness here would cause inconsistencies as to how this 206360784Sdim /// file and visitors construct diagnostics), hence its const. 207360784Sdim const PathSensitiveBugReport *R; 208360784Sdim /// The leaf of the bug path. This isn't the same as the bug reports error 209360784Sdim /// node, which refers to the *original* graph, not the bug path. 210360784Sdim const ExplodedNode *const ErrorNode; 211360784Sdim /// The diagnostic pieces visitors emitted, which is expected to be collected 212360784Sdim /// by the time this builder is constructed. 213360784Sdim std::unique_ptr<const VisitorsDiagnosticsTy> VisitorsDiagnostics; 214360784Sdim 215360784Sdimpublic: 216360784Sdim /// Find a non-invalidated report for a given equivalence class, and returns 217360784Sdim /// a PathDiagnosticBuilder able to construct bug reports for different 218360784Sdim /// consumers. Returns None if no valid report is found. 219360784Sdim static Optional<PathDiagnosticBuilder> 220360784Sdim findValidReport(ArrayRef<PathSensitiveBugReport *> &bugReports, 221360784Sdim PathSensitiveBugReporter &Reporter); 222360784Sdim 223360784Sdim PathDiagnosticBuilder( 224360784Sdim BugReporterContext BRC, std::unique_ptr<ExplodedGraph> BugPath, 225360784Sdim PathSensitiveBugReport *r, const ExplodedNode *ErrorNode, 226360784Sdim std::unique_ptr<VisitorsDiagnosticsTy> VisitorsDiagnostics); 227360784Sdim 228360784Sdim /// This function is responsible for generating diagnostic pieces that are 229360784Sdim /// *not* provided by bug report visitors. 230360784Sdim /// These diagnostics may differ depending on the consumer's settings, 231360784Sdim /// and are therefore constructed separately for each consumer. 232360784Sdim /// 233360784Sdim /// There are two path diagnostics generation modes: with adding edges (used 234360784Sdim /// for plists) and without (used for HTML and text). When edges are added, 235360784Sdim /// the path is modified to insert artificially generated edges. 236360784Sdim /// Otherwise, more detailed diagnostics is emitted for block edges, 237360784Sdim /// explaining the transitions in words. 238360784Sdim std::unique_ptr<PathDiagnostic> 239360784Sdim generate(const PathDiagnosticConsumer *PDC) const; 240360784Sdim 241360784Sdimprivate: 242360784Sdim void updateStackPiecesWithMessage(PathDiagnosticPieceRef P, 243360784Sdim const CallWithEntryStack &CallStack) const; 244360784Sdim void generatePathDiagnosticsForNode(PathDiagnosticConstruct &C, 245360784Sdim PathDiagnosticLocation &PrevLoc) const; 246360784Sdim 247360784Sdim void generateMinimalDiagForBlockEdge(PathDiagnosticConstruct &C, 248360784Sdim BlockEdge BE) const; 249360784Sdim 250360784Sdim PathDiagnosticPieceRef 251360784Sdim generateDiagForGotoOP(const PathDiagnosticConstruct &C, const Stmt *S, 252360784Sdim PathDiagnosticLocation &Start) const; 253360784Sdim 254360784Sdim PathDiagnosticPieceRef 255360784Sdim generateDiagForSwitchOP(const PathDiagnosticConstruct &C, const CFGBlock *Dst, 256360784Sdim PathDiagnosticLocation &Start) const; 257360784Sdim 258360784Sdim PathDiagnosticPieceRef 259360784Sdim generateDiagForBinaryOP(const PathDiagnosticConstruct &C, const Stmt *T, 260360784Sdim const CFGBlock *Src, const CFGBlock *DstC) const; 261360784Sdim 262360784Sdim PathDiagnosticLocation 263360784Sdim ExecutionContinues(const PathDiagnosticConstruct &C) const; 264360784Sdim 265360784Sdim PathDiagnosticLocation 266360784Sdim ExecutionContinues(llvm::raw_string_ostream &os, 267360784Sdim const PathDiagnosticConstruct &C) const; 268360784Sdim 269360784Sdim const PathSensitiveBugReport *getBugReport() const { return R; } 270360784Sdim}; 271360784Sdim 272360784Sdim} // namespace 273360784Sdim 274360784Sdim//===----------------------------------------------------------------------===// 275360784Sdim// Base implementation of stack hint generators. 276360784Sdim//===----------------------------------------------------------------------===// 277360784Sdim 278360784SdimStackHintGenerator::~StackHintGenerator() = default; 279360784Sdim 280360784Sdimstd::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){ 281360784Sdim if (!N) 282360784Sdim return getMessageForSymbolNotFound(); 283360784Sdim 284360784Sdim ProgramPoint P = N->getLocation(); 285360784Sdim CallExitEnd CExit = P.castAs<CallExitEnd>(); 286360784Sdim 287360784Sdim // FIXME: Use CallEvent to abstract this over all calls. 288360784Sdim const Stmt *CallSite = CExit.getCalleeContext()->getCallSite(); 289360784Sdim const auto *CE = dyn_cast_or_null<CallExpr>(CallSite); 290360784Sdim if (!CE) 291360784Sdim return {}; 292360784Sdim 293360784Sdim // Check if one of the parameters are set to the interesting symbol. 294360784Sdim unsigned ArgIndex = 0; 295360784Sdim for (CallExpr::const_arg_iterator I = CE->arg_begin(), 296360784Sdim E = CE->arg_end(); I != E; ++I, ++ArgIndex){ 297360784Sdim SVal SV = N->getSVal(*I); 298360784Sdim 299360784Sdim // Check if the variable corresponding to the symbol is passed by value. 300360784Sdim SymbolRef AS = SV.getAsLocSymbol(); 301360784Sdim if (AS == Sym) { 302360784Sdim return getMessageForArg(*I, ArgIndex); 303360784Sdim } 304360784Sdim 305360784Sdim // Check if the parameter is a pointer to the symbol. 306360784Sdim if (Optional<loc::MemRegionVal> Reg = SV.getAs<loc::MemRegionVal>()) { 307360784Sdim // Do not attempt to dereference void*. 308360784Sdim if ((*I)->getType()->isVoidPointerType()) 309360784Sdim continue; 310360784Sdim SVal PSV = N->getState()->getSVal(Reg->getRegion()); 311360784Sdim SymbolRef AS = PSV.getAsLocSymbol(); 312360784Sdim if (AS == Sym) { 313360784Sdim return getMessageForArg(*I, ArgIndex); 314360784Sdim } 315360784Sdim } 316360784Sdim } 317360784Sdim 318360784Sdim // Check if we are returning the interesting symbol. 319360784Sdim SVal SV = N->getSVal(CE); 320360784Sdim SymbolRef RetSym = SV.getAsLocSymbol(); 321360784Sdim if (RetSym == Sym) { 322360784Sdim return getMessageForReturn(CE); 323360784Sdim } 324360784Sdim 325360784Sdim return getMessageForSymbolNotFound(); 326218887Sdim} 327218887Sdim 328360784Sdimstd::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE, 329360784Sdim unsigned ArgIndex) { 330360784Sdim // Printed parameters start at 1, not 0. 331360784Sdim ++ArgIndex; 332218887Sdim 333360784Sdim return (llvm::Twine(Msg) + " via " + std::to_string(ArgIndex) + 334360784Sdim llvm::getOrdinalSuffix(ArgIndex) + " parameter").str(); 335218887Sdim} 336218887Sdim 337218887Sdim//===----------------------------------------------------------------------===// 338234353Sdim// Diagnostic cleanup. 339234353Sdim//===----------------------------------------------------------------------===// 340234353Sdim 341243830Sdimstatic PathDiagnosticEventPiece * 342243830SdimeventsDescribeSameCondition(PathDiagnosticEventPiece *X, 343243830Sdim PathDiagnosticEventPiece *Y) { 344243830Sdim // Prefer diagnostics that come from ConditionBRVisitor over 345314564Sdim // those that came from TrackConstraintBRVisitor, 346314564Sdim // unless the one from ConditionBRVisitor is 347314564Sdim // its generic fallback diagnostic. 348243830Sdim const void *tagPreferred = ConditionBRVisitor::getTag(); 349243830Sdim const void *tagLesser = TrackConstraintBRVisitor::getTag(); 350296417Sdim 351243830Sdim if (X->getLocation() != Y->getLocation()) 352276479Sdim return nullptr; 353276479Sdim 354243830Sdim if (X->getTag() == tagPreferred && Y->getTag() == tagLesser) 355314564Sdim return ConditionBRVisitor::isPieceMessageGeneric(X) ? Y : X; 356296417Sdim 357243830Sdim if (Y->getTag() == tagPreferred && X->getTag() == tagLesser) 358314564Sdim return ConditionBRVisitor::isPieceMessageGeneric(Y) ? X : Y; 359276479Sdim 360276479Sdim return nullptr; 361243830Sdim} 362243830Sdim 363243830Sdim/// An optimization pass over PathPieces that removes redundant diagnostics 364243830Sdim/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both 365243830Sdim/// BugReporterVisitors use different methods to generate diagnostics, with 366243830Sdim/// one capable of emitting diagnostics in some cases but not in others. This 367243830Sdim/// can lead to redundant diagnostic pieces at the same point in a path. 368243830Sdimstatic void removeRedundantMsgs(PathPieces &path) { 369243830Sdim unsigned N = path.size(); 370243830Sdim if (N < 2) 371243830Sdim return; 372243830Sdim // NOTE: this loop intentionally is not using an iterator. Instead, we 373243830Sdim // are streaming the path and modifying it in place. This is done by 374243830Sdim // grabbing the front, processing it, and if we decide to keep it append 375243830Sdim // it to the end of the path. The entire path is processed in this way. 376243830Sdim for (unsigned i = 0; i < N; ++i) { 377314564Sdim auto piece = std::move(path.front()); 378243830Sdim path.pop_front(); 379296417Sdim 380243830Sdim switch (piece->getKind()) { 381314564Sdim case PathDiagnosticPiece::Call: 382314564Sdim removeRedundantMsgs(cast<PathDiagnosticCallPiece>(*piece).path); 383243830Sdim break; 384314564Sdim case PathDiagnosticPiece::Macro: 385314564Sdim removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(*piece).subPieces); 386243830Sdim break; 387314564Sdim case PathDiagnosticPiece::Event: { 388243830Sdim if (i == N-1) 389243830Sdim break; 390296417Sdim 391341825Sdim if (auto *nextEvent = 392276479Sdim dyn_cast<PathDiagnosticEventPiece>(path.front().get())) { 393341825Sdim auto *event = cast<PathDiagnosticEventPiece>(piece.get()); 394243830Sdim // Check to see if we should keep one of the two pieces. If we 395243830Sdim // come up with a preference, record which piece to keep, and consume 396243830Sdim // another piece from the path. 397314564Sdim if (auto *pieceToKeep = 398314564Sdim eventsDescribeSameCondition(event, nextEvent)) { 399314564Sdim piece = std::move(pieceToKeep == event ? piece : path.front()); 400243830Sdim path.pop_front(); 401243830Sdim ++i; 402243830Sdim } 403243830Sdim } 404243830Sdim break; 405243830Sdim } 406353358Sdim case PathDiagnosticPiece::ControlFlow: 407314564Sdim case PathDiagnosticPiece::Note: 408353358Sdim case PathDiagnosticPiece::PopUp: 409314564Sdim break; 410243830Sdim } 411314564Sdim path.push_back(std::move(piece)); 412243830Sdim } 413243830Sdim} 414243830Sdim 415234353Sdim/// Recursively scan through a path and prune out calls and macros pieces 416234353Sdim/// that aren't needed. Return true if afterwards the path contains 417249423Sdim/// "interesting stuff" which means it shouldn't be pruned from the parent path. 418360784Sdimstatic bool removeUnneededCalls(const PathDiagnosticConstruct &C, 419360784Sdim PathPieces &pieces, 420360784Sdim const PathSensitiveBugReport *R, 421341825Sdim bool IsInteresting = false) { 422341825Sdim bool containsSomethingInteresting = IsInteresting; 423234353Sdim const unsigned N = pieces.size(); 424296417Sdim 425234353Sdim for (unsigned i = 0 ; i < N ; ++i) { 426234353Sdim // Remove the front piece from the path. If it is still something we 427234353Sdim // want to keep once we are done, we will push it back on the end. 428314564Sdim auto piece = std::move(pieces.front()); 429234353Sdim pieces.pop_front(); 430296417Sdim 431234353Sdim switch (piece->getKind()) { 432234353Sdim case PathDiagnosticPiece::Call: { 433314564Sdim auto &call = cast<PathDiagnosticCallPiece>(*piece); 434243830Sdim // Check if the location context is interesting. 435360784Sdim if (!removeUnneededCalls( 436360784Sdim C, call.path, R, 437360784Sdim R->isInteresting(C.getLocationContextFor(&call.path)))) 438234353Sdim continue; 439296417Sdim 440234353Sdim containsSomethingInteresting = true; 441234353Sdim break; 442234353Sdim } 443234353Sdim case PathDiagnosticPiece::Macro: { 444314564Sdim auto ¯o = cast<PathDiagnosticMacroPiece>(*piece); 445360784Sdim if (!removeUnneededCalls(C, macro.subPieces, R, IsInteresting)) 446234353Sdim continue; 447234353Sdim containsSomethingInteresting = true; 448234353Sdim break; 449234353Sdim } 450234353Sdim case PathDiagnosticPiece::Event: { 451314564Sdim auto &event = cast<PathDiagnosticEventPiece>(*piece); 452296417Sdim 453234353Sdim // We never throw away an event, but we do throw it away wholesale 454234353Sdim // as part of a path if we throw the entire path away. 455314564Sdim containsSomethingInteresting |= !event.isPrunable(); 456234353Sdim break; 457234353Sdim } 458234353Sdim case PathDiagnosticPiece::ControlFlow: 459314564Sdim case PathDiagnosticPiece::Note: 460353358Sdim case PathDiagnosticPiece::PopUp: 461314564Sdim break; 462234353Sdim } 463296417Sdim 464314564Sdim pieces.push_back(std::move(piece)); 465234353Sdim } 466296417Sdim 467234353Sdim return containsSomethingInteresting; 468234353Sdim} 469234353Sdim 470353358Sdim/// Same logic as above to remove extra pieces. 471353358Sdimstatic void removePopUpNotes(PathPieces &Path) { 472353358Sdim for (unsigned int i = 0; i < Path.size(); ++i) { 473353358Sdim auto Piece = std::move(Path.front()); 474353358Sdim Path.pop_front(); 475353358Sdim if (!isa<PathDiagnosticPopUpPiece>(*Piece)) 476353358Sdim Path.push_back(std::move(Piece)); 477353358Sdim } 478353358Sdim} 479353358Sdim 480261991Sdim/// Returns true if the given decl has been implicitly given a body, either by 481261991Sdim/// the analyzer or by the compiler proper. 482261991Sdimstatic bool hasImplicitBody(const Decl *D) { 483261991Sdim assert(D); 484261991Sdim return D->isImplicit() || !D->hasBody(); 485261991Sdim} 486261991Sdim 487249423Sdim/// Recursively scan through a path and make sure that all call pieces have 488296417Sdim/// valid locations. 489276479Sdimstatic void 490276479SdimadjustCallLocations(PathPieces &Pieces, 491276479Sdim PathDiagnosticLocation *LastCallLocation = nullptr) { 492341825Sdim for (const auto &I : Pieces) { 493341825Sdim auto *Call = dyn_cast<PathDiagnosticCallPiece>(I.get()); 494249423Sdim 495341825Sdim if (!Call) 496249423Sdim continue; 497249423Sdim 498249423Sdim if (LastCallLocation) { 499261991Sdim bool CallerIsImplicit = hasImplicitBody(Call->getCaller()); 500261991Sdim if (CallerIsImplicit || !Call->callEnter.asLocation().isValid()) 501249423Sdim Call->callEnter = *LastCallLocation; 502261991Sdim if (CallerIsImplicit || !Call->callReturn.asLocation().isValid()) 503249423Sdim Call->callReturn = *LastCallLocation; 504249423Sdim } 505249423Sdim 506249423Sdim // Recursively clean out the subclass. Keep this call around if 507249423Sdim // it contains any informative diagnostics. 508249423Sdim PathDiagnosticLocation *ThisCallLocation; 509249423Sdim if (Call->callEnterWithin.asLocation().isValid() && 510261991Sdim !hasImplicitBody(Call->getCallee())) 511249423Sdim ThisCallLocation = &Call->callEnterWithin; 512249423Sdim else 513249423Sdim ThisCallLocation = &Call->callEnter; 514249423Sdim 515249423Sdim assert(ThisCallLocation && "Outermost call has an invalid location"); 516249423Sdim adjustCallLocations(Call->path, ThisCallLocation); 517249423Sdim } 518249423Sdim} 519249423Sdim 520261991Sdim/// Remove edges in and out of C++ default initializer expressions. These are 521261991Sdim/// for fields that have in-class initializers, as opposed to being initialized 522261991Sdim/// explicitly in a constructor or braced list. 523261991Sdimstatic void removeEdgesToDefaultInitializers(PathPieces &Pieces) { 524261991Sdim for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 525314564Sdim if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get())) 526261991Sdim removeEdgesToDefaultInitializers(C->path); 527261991Sdim 528314564Sdim if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get())) 529261991Sdim removeEdgesToDefaultInitializers(M->subPieces); 530261991Sdim 531314564Sdim if (auto *CF = dyn_cast<PathDiagnosticControlFlowPiece>(I->get())) { 532261991Sdim const Stmt *Start = CF->getStartLocation().asStmt(); 533261991Sdim const Stmt *End = CF->getEndLocation().asStmt(); 534261991Sdim if (Start && isa<CXXDefaultInitExpr>(Start)) { 535261991Sdim I = Pieces.erase(I); 536261991Sdim continue; 537261991Sdim } else if (End && isa<CXXDefaultInitExpr>(End)) { 538276479Sdim PathPieces::iterator Next = std::next(I); 539261991Sdim if (Next != E) { 540314564Sdim if (auto *NextCF = 541314564Sdim dyn_cast<PathDiagnosticControlFlowPiece>(Next->get())) { 542261991Sdim NextCF->setStartLocation(CF->getStartLocation()); 543261991Sdim } 544261991Sdim } 545261991Sdim I = Pieces.erase(I); 546261991Sdim continue; 547261991Sdim } 548261991Sdim } 549261991Sdim 550261991Sdim I++; 551261991Sdim } 552261991Sdim} 553261991Sdim 554261991Sdim/// Remove all pieces with invalid locations as these cannot be serialized. 555261991Sdim/// We might have pieces with invalid locations as a result of inlining Body 556261991Sdim/// Farm generated functions. 557261991Sdimstatic void removePiecesWithInvalidLocations(PathPieces &Pieces) { 558261991Sdim for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) { 559314564Sdim if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get())) 560261991Sdim removePiecesWithInvalidLocations(C->path); 561261991Sdim 562314564Sdim if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get())) 563261991Sdim removePiecesWithInvalidLocations(M->subPieces); 564261991Sdim 565261991Sdim if (!(*I)->getLocation().isValid() || 566261991Sdim !(*I)->getLocation().asLocation().isValid()) { 567261991Sdim I = Pieces.erase(I); 568261991Sdim continue; 569261991Sdim } 570261991Sdim I++; 571261991Sdim } 572261991Sdim} 573261991Sdim 574360784SdimPathDiagnosticLocation PathDiagnosticBuilder::ExecutionContinues( 575360784Sdim const PathDiagnosticConstruct &C) const { 576360784Sdim if (const Stmt *S = C.getCurrentNode()->getNextStmtForDiagnostics()) 577360784Sdim return PathDiagnosticLocation(S, getSourceManager(), 578360784Sdim C.getCurrLocationContext()); 579218887Sdim 580360784Sdim return PathDiagnosticLocation::createDeclEnd(C.getCurrLocationContext(), 581226633Sdim getSourceManager()); 582218887Sdim} 583218887Sdim 584360784SdimPathDiagnosticLocation PathDiagnosticBuilder::ExecutionContinues( 585360784Sdim llvm::raw_string_ostream &os, const PathDiagnosticConstruct &C) const { 586218887Sdim // Slow, but probably doesn't matter. 587218887Sdim if (os.str().empty()) 588218887Sdim os << ' '; 589218887Sdim 590360784Sdim const PathDiagnosticLocation &Loc = ExecutionContinues(C); 591218887Sdim 592218887Sdim if (Loc.asStmt()) 593218887Sdim os << "Execution continues on line " 594226633Sdim << getSourceManager().getExpansionLineNumber(Loc.asLocation()) 595218887Sdim << '.'; 596218887Sdim else { 597218887Sdim os << "Execution jumps to the end of the "; 598360784Sdim const Decl *D = C.getCurrLocationContext()->getDecl(); 599218887Sdim if (isa<ObjCMethodDecl>(D)) 600218887Sdim os << "method"; 601218887Sdim else if (isa<FunctionDecl>(D)) 602218887Sdim os << "function"; 603218887Sdim else { 604218887Sdim assert(isa<BlockDecl>(D)); 605218887Sdim os << "anonymous block"; 606218887Sdim } 607218887Sdim os << '.'; 608218887Sdim } 609218887Sdim 610218887Sdim return Loc; 611218887Sdim} 612218887Sdim 613261991Sdimstatic const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) { 614218887Sdim if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S))) 615261991Sdim return PM.getParentIgnoreParens(S); 616218887Sdim 617218887Sdim const Stmt *Parent = PM.getParentIgnoreParens(S); 618261991Sdim if (!Parent) 619276479Sdim return nullptr; 620218887Sdim 621261991Sdim switch (Parent->getStmtClass()) { 622261991Sdim case Stmt::ForStmtClass: 623261991Sdim case Stmt::DoStmtClass: 624261991Sdim case Stmt::WhileStmtClass: 625261991Sdim case Stmt::ObjCForCollectionStmtClass: 626261991Sdim case Stmt::CXXForRangeStmtClass: 627261991Sdim return Parent; 628261991Sdim default: 629261991Sdim break; 630261991Sdim } 631218887Sdim 632276479Sdim return nullptr; 633218887Sdim} 634218887Sdim 635261991Sdimstatic PathDiagnosticLocation 636360784SdimgetEnclosingStmtLocation(const Stmt *S, const LocationContext *LC, 637360784Sdim bool allowNestedContexts = false) { 638261991Sdim if (!S) 639341825Sdim return {}; 640218887Sdim 641360784Sdim const SourceManager &SMgr = LC->getDecl()->getASTContext().getSourceManager(); 642360784Sdim 643360784Sdim while (const Stmt *Parent = getEnclosingParent(S, LC->getParentMap())) { 644218887Sdim switch (Parent->getStmtClass()) { 645218887Sdim case Stmt::BinaryOperatorClass: { 646341825Sdim const auto *B = cast<BinaryOperator>(Parent); 647218887Sdim if (B->isLogicalOp()) 648261991Sdim return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC); 649218887Sdim break; 650218887Sdim } 651218887Sdim case Stmt::CompoundStmtClass: 652218887Sdim case Stmt::StmtExprClass: 653226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 654218887Sdim case Stmt::ChooseExprClass: 655218887Sdim // Similar to '?' if we are referring to condition, just have the edge 656218887Sdim // point to the entire choose expression. 657261991Sdim if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S) 658226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 659218887Sdim else 660226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 661218887Sdim case Stmt::BinaryConditionalOperatorClass: 662218887Sdim case Stmt::ConditionalOperatorClass: 663218887Sdim // For '?', if we are referring to condition, just have the edge point 664218887Sdim // to the entire '?' expression. 665261991Sdim if (allowNestedContexts || 666261991Sdim cast<AbstractConditionalOperator>(Parent)->getCond() == S) 667226633Sdim return PathDiagnosticLocation(Parent, SMgr, LC); 668218887Sdim else 669226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 670261991Sdim case Stmt::CXXForRangeStmtClass: 671261991Sdim if (cast<CXXForRangeStmt>(Parent)->getBody() == S) 672261991Sdim return PathDiagnosticLocation(S, SMgr, LC); 673261991Sdim break; 674218887Sdim case Stmt::DoStmtClass: 675226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 676218887Sdim case Stmt::ForStmtClass: 677218887Sdim if (cast<ForStmt>(Parent)->getBody() == S) 678226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 679218887Sdim break; 680218887Sdim case Stmt::IfStmtClass: 681218887Sdim if (cast<IfStmt>(Parent)->getCond() != S) 682226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 683218887Sdim break; 684218887Sdim case Stmt::ObjCForCollectionStmtClass: 685218887Sdim if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S) 686226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 687218887Sdim break; 688218887Sdim case Stmt::WhileStmtClass: 689218887Sdim if (cast<WhileStmt>(Parent)->getCond() != S) 690226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 691218887Sdim break; 692218887Sdim default: 693218887Sdim break; 694218887Sdim } 695218887Sdim 696218887Sdim S = Parent; 697218887Sdim } 698218887Sdim 699218887Sdim assert(S && "Cannot have null Stmt for PathDiagnosticLocation"); 700218887Sdim 701226633Sdim return PathDiagnosticLocation(S, SMgr, LC); 702218887Sdim} 703218887Sdim 704218887Sdim//===----------------------------------------------------------------------===// 705234353Sdim// "Minimal" path diagnostic generation algorithm. 706218887Sdim//===----------------------------------------------------------------------===// 707218887Sdim 708360784Sdim/// If the piece contains a special message, add it to all the call pieces on 709360784Sdim/// the active stack. For example, my_malloc allocated memory, so MallocChecker 710360784Sdim/// will construct an event at the call to malloc(), and add a stack hint that 711360784Sdim/// an allocated memory was returned. We'll use this hint to construct a message 712360784Sdim/// when returning from the call to my_malloc 713360784Sdim/// 714360784Sdim/// void *my_malloc() { return malloc(sizeof(int)); } 715360784Sdim/// void fishy() { 716360784Sdim/// void *ptr = my_malloc(); // returned allocated memory 717360784Sdim/// } // leak 718360784Sdimvoid PathDiagnosticBuilder::updateStackPiecesWithMessage( 719360784Sdim PathDiagnosticPieceRef P, const CallWithEntryStack &CallStack) const { 720360784Sdim if (R->hasCallStackHint(P)) 721360784Sdim for (const auto &I : CallStack) { 722360784Sdim PathDiagnosticCallPiece *CP = I.first; 723360784Sdim const ExplodedNode *N = I.second; 724360784Sdim std::string stackMsg = R->getCallStackMessage(P, N); 725218887Sdim 726360784Sdim // The last message on the path to final bug is the most important 727360784Sdim // one. Since we traverse the path backwards, do not add the message 728360784Sdim // if one has been previously added. 729360784Sdim if (!CP->hasCallStackMessage()) 730360784Sdim CP->setCallStackMessage(stackMsg); 731360784Sdim } 732218887Sdim} 733218887Sdim 734344779Sdimstatic void CompactMacroExpandedPieces(PathPieces &path, 735344779Sdim const SourceManager& SM); 736218887Sdim 737360784SdimPathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForSwitchOP( 738360784Sdim const PathDiagnosticConstruct &C, const CFGBlock *Dst, 739360784Sdim PathDiagnosticLocation &Start) const { 740218887Sdim 741360784Sdim const SourceManager &SM = getSourceManager(); 742341825Sdim // Figure out what case arm we took. 743341825Sdim std::string sbuf; 744341825Sdim llvm::raw_string_ostream os(sbuf); 745341825Sdim PathDiagnosticLocation End; 746234353Sdim 747341825Sdim if (const Stmt *S = Dst->getLabel()) { 748360784Sdim End = PathDiagnosticLocation(S, SM, C.getCurrLocationContext()); 749234353Sdim 750341825Sdim switch (S->getStmtClass()) { 751341825Sdim default: 752341825Sdim os << "No cases match in the switch statement. " 753341825Sdim "Control jumps to line " 754341825Sdim << End.asLocation().getExpansionLineNumber(); 755341825Sdim break; 756341825Sdim case Stmt::DefaultStmtClass: 757341825Sdim os << "Control jumps to the 'default' case at line " 758341825Sdim << End.asLocation().getExpansionLineNumber(); 759341825Sdim break; 760218887Sdim 761341825Sdim case Stmt::CaseStmtClass: { 762341825Sdim os << "Control jumps to 'case "; 763341825Sdim const auto *Case = cast<CaseStmt>(S); 764341825Sdim const Expr *LHS = Case->getLHS()->IgnoreParenCasts(); 765239462Sdim 766341825Sdim // Determine if it is an enum. 767341825Sdim bool GetRawInt = true; 768239462Sdim 769341825Sdim if (const auto *DR = dyn_cast<DeclRefExpr>(LHS)) { 770341825Sdim // FIXME: Maybe this should be an assertion. Are there cases 771341825Sdim // were it is not an EnumConstantDecl? 772341825Sdim const auto *D = dyn_cast<EnumConstantDecl>(DR->getDecl()); 773243830Sdim 774341825Sdim if (D) { 775341825Sdim GetRawInt = false; 776341825Sdim os << *D; 777243830Sdim } 778234353Sdim } 779218887Sdim 780341825Sdim if (GetRawInt) 781360784Sdim os << LHS->EvaluateKnownConstInt(getASTContext()); 782218887Sdim 783341825Sdim os << ":' at line " << End.asLocation().getExpansionLineNumber(); 784341825Sdim break; 785218887Sdim } 786341825Sdim } 787341825Sdim } else { 788341825Sdim os << "'Default' branch taken. "; 789360784Sdim End = ExecutionContinues(os, C); 790218887Sdim } 791341825Sdim return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 792341825Sdim os.str()); 793218887Sdim} 794218887Sdim 795360784SdimPathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForGotoOP( 796360784Sdim const PathDiagnosticConstruct &C, const Stmt *S, 797360784Sdim PathDiagnosticLocation &Start) const { 798360784Sdim std::string sbuf; 799360784Sdim llvm::raw_string_ostream os(sbuf); 800360784Sdim const PathDiagnosticLocation &End = 801360784Sdim getEnclosingStmtLocation(S, C.getCurrLocationContext()); 802360784Sdim os << "Control jumps to line " << End.asLocation().getExpansionLineNumber(); 803360784Sdim return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()); 804360784Sdim} 805218887Sdim 806360784SdimPathDiagnosticPieceRef PathDiagnosticBuilder::generateDiagForBinaryOP( 807360784Sdim const PathDiagnosticConstruct &C, const Stmt *T, const CFGBlock *Src, 808360784Sdim const CFGBlock *Dst) const { 809218887Sdim 810360784Sdim const SourceManager &SM = getSourceManager(); 811218887Sdim 812341825Sdim const auto *B = cast<BinaryOperator>(T); 813341825Sdim std::string sbuf; 814341825Sdim llvm::raw_string_ostream os(sbuf); 815341825Sdim os << "Left side of '"; 816341825Sdim PathDiagnosticLocation Start, End; 817218887Sdim 818341825Sdim if (B->getOpcode() == BO_LAnd) { 819341825Sdim os << "&&" 820341825Sdim << "' is "; 821218887Sdim 822341825Sdim if (*(Src->succ_begin() + 1) == Dst) { 823341825Sdim os << "false"; 824360784Sdim End = PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext()); 825341825Sdim Start = 826341825Sdim PathDiagnosticLocation::createOperatorLoc(B, SM); 827341825Sdim } else { 828341825Sdim os << "true"; 829360784Sdim Start = 830360784Sdim PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext()); 831360784Sdim End = ExecutionContinues(C); 832341825Sdim } 833341825Sdim } else { 834341825Sdim assert(B->getOpcode() == BO_LOr); 835341825Sdim os << "||" 836341825Sdim << "' is "; 837251662Sdim 838341825Sdim if (*(Src->succ_begin() + 1) == Dst) { 839341825Sdim os << "false"; 840360784Sdim Start = 841360784Sdim PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext()); 842360784Sdim End = ExecutionContinues(C); 843341825Sdim } else { 844341825Sdim os << "true"; 845360784Sdim End = PathDiagnosticLocation(B->getLHS(), SM, C.getCurrLocationContext()); 846341825Sdim Start = 847341825Sdim PathDiagnosticLocation::createOperatorLoc(B, SM); 848251662Sdim } 849251662Sdim } 850341825Sdim return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 851341825Sdim os.str()); 852251662Sdim} 853251662Sdim 854360784Sdimvoid PathDiagnosticBuilder::generateMinimalDiagForBlockEdge( 855360784Sdim PathDiagnosticConstruct &C, BlockEdge BE) const { 856360784Sdim const SourceManager &SM = getSourceManager(); 857360784Sdim const LocationContext *LC = C.getCurrLocationContext(); 858341825Sdim const CFGBlock *Src = BE.getSrc(); 859341825Sdim const CFGBlock *Dst = BE.getDst(); 860353358Sdim const Stmt *T = Src->getTerminatorStmt(); 861341825Sdim if (!T) 862341825Sdim return; 863218887Sdim 864341825Sdim auto Start = PathDiagnosticLocation::createBegin(T, SM, LC); 865341825Sdim switch (T->getStmtClass()) { 866341825Sdim default: 867341825Sdim break; 868218887Sdim 869341825Sdim case Stmt::GotoStmtClass: 870341825Sdim case Stmt::IndirectGotoStmtClass: { 871360784Sdim if (const Stmt *S = C.getCurrentNode()->getNextStmtForDiagnostics()) 872360784Sdim C.getActivePath().push_front(generateDiagForGotoOP(C, S, Start)); 873341825Sdim break; 874218887Sdim } 875218887Sdim 876341825Sdim case Stmt::SwitchStmtClass: { 877360784Sdim C.getActivePath().push_front(generateDiagForSwitchOP(C, Dst, Start)); 878341825Sdim break; 879218887Sdim } 880218887Sdim 881341825Sdim case Stmt::BreakStmtClass: 882341825Sdim case Stmt::ContinueStmtClass: { 883341825Sdim std::string sbuf; 884341825Sdim llvm::raw_string_ostream os(sbuf); 885360784Sdim PathDiagnosticLocation End = ExecutionContinues(os, C); 886360784Sdim C.getActivePath().push_front( 887341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str())); 888341825Sdim break; 889218887Sdim } 890218887Sdim 891341825Sdim // Determine control-flow for ternary '?'. 892341825Sdim case Stmt::BinaryConditionalOperatorClass: 893341825Sdim case Stmt::ConditionalOperatorClass: { 894341825Sdim std::string sbuf; 895341825Sdim llvm::raw_string_ostream os(sbuf); 896341825Sdim os << "'?' condition is "; 897296417Sdim 898341825Sdim if (*(Src->succ_begin() + 1) == Dst) 899341825Sdim os << "false"; 900341825Sdim else 901341825Sdim os << "true"; 902218887Sdim 903360784Sdim PathDiagnosticLocation End = ExecutionContinues(C); 904218887Sdim 905341825Sdim if (const Stmt *S = End.asStmt()) 906360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 907218887Sdim 908360784Sdim C.getActivePath().push_front( 909341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str())); 910341825Sdim break; 911218887Sdim } 912218887Sdim 913341825Sdim // Determine control-flow for short-circuited '&&' and '||'. 914341825Sdim case Stmt::BinaryOperatorClass: { 915360784Sdim if (!C.supportsLogicalOpControlFlow()) 916341825Sdim break; 917218887Sdim 918360784Sdim C.getActivePath().push_front(generateDiagForBinaryOP(C, T, Src, Dst)); 919341825Sdim break; 920218887Sdim } 921218887Sdim 922341825Sdim case Stmt::DoStmtClass: 923341825Sdim if (*(Src->succ_begin()) == Dst) { 924341825Sdim std::string sbuf; 925341825Sdim llvm::raw_string_ostream os(sbuf); 926218887Sdim 927341825Sdim os << "Loop condition is true. "; 928360784Sdim PathDiagnosticLocation End = ExecutionContinues(os, C); 929296417Sdim 930341825Sdim if (const Stmt *S = End.asStmt()) 931360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 932218887Sdim 933360784Sdim C.getActivePath().push_front( 934341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 935341825Sdim os.str())); 936341825Sdim } else { 937360784Sdim PathDiagnosticLocation End = ExecutionContinues(C); 938218887Sdim 939341825Sdim if (const Stmt *S = End.asStmt()) 940360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 941218887Sdim 942360784Sdim C.getActivePath().push_front( 943341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>( 944341825Sdim Start, End, "Loop condition is false. Exiting loop")); 945341825Sdim } 946341825Sdim break; 947218887Sdim 948341825Sdim case Stmt::WhileStmtClass: 949341825Sdim case Stmt::ForStmtClass: 950341825Sdim if (*(Src->succ_begin() + 1) == Dst) { 951341825Sdim std::string sbuf; 952341825Sdim llvm::raw_string_ostream os(sbuf); 953218887Sdim 954341825Sdim os << "Loop condition is false. "; 955360784Sdim PathDiagnosticLocation End = ExecutionContinues(os, C); 956341825Sdim if (const Stmt *S = End.asStmt()) 957360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 958218887Sdim 959360784Sdim C.getActivePath().push_front( 960341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, 961341825Sdim os.str())); 962341825Sdim } else { 963360784Sdim PathDiagnosticLocation End = ExecutionContinues(C); 964341825Sdim if (const Stmt *S = End.asStmt()) 965360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 966218887Sdim 967360784Sdim C.getActivePath().push_front( 968341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>( 969341825Sdim Start, End, "Loop condition is true. Entering loop body")); 970218887Sdim } 971218887Sdim 972341825Sdim break; 973218887Sdim 974341825Sdim case Stmt::IfStmtClass: { 975360784Sdim PathDiagnosticLocation End = ExecutionContinues(C); 976218887Sdim 977341825Sdim if (const Stmt *S = End.asStmt()) 978360784Sdim End = getEnclosingStmtLocation(S, C.getCurrLocationContext()); 979218887Sdim 980341825Sdim if (*(Src->succ_begin() + 1) == Dst) 981360784Sdim C.getActivePath().push_front( 982341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>( 983341825Sdim Start, End, "Taking false branch")); 984218887Sdim else 985360784Sdim C.getActivePath().push_front( 986341825Sdim std::make_shared<PathDiagnosticControlFlowPiece>( 987341825Sdim Start, End, "Taking true branch")); 988218887Sdim 989341825Sdim break; 990218887Sdim } 991218887Sdim } 992218887Sdim} 993218887Sdim 994249423Sdim//===----------------------------------------------------------------------===// 995249423Sdim// Functions for determining if a loop was executed 0 times. 996249423Sdim//===----------------------------------------------------------------------===// 997249423Sdim 998261991Sdimstatic bool isLoop(const Stmt *Term) { 999249423Sdim switch (Term->getStmtClass()) { 1000249423Sdim case Stmt::ForStmtClass: 1001249423Sdim case Stmt::WhileStmtClass: 1002249423Sdim case Stmt::ObjCForCollectionStmtClass: 1003261991Sdim case Stmt::CXXForRangeStmtClass: 1004261991Sdim return true; 1005249423Sdim default: 1006249423Sdim // Note that we intentionally do not include do..while here. 1007249423Sdim return false; 1008249423Sdim } 1009261991Sdim} 1010249423Sdim 1011261991Sdimstatic bool isJumpToFalseBranch(const BlockEdge *BE) { 1012249423Sdim const CFGBlock *Src = BE->getSrc(); 1013249423Sdim assert(Src->succ_size() == 2); 1014249423Sdim return (*(Src->succ_begin()+1) == BE->getDst()); 1015249423Sdim} 1016249423Sdim 1017360784Sdimstatic bool isContainedByStmt(const ParentMap &PM, const Stmt *S, 1018360784Sdim const Stmt *SubS) { 1019249423Sdim while (SubS) { 1020249423Sdim if (SubS == S) 1021249423Sdim return true; 1022249423Sdim SubS = PM.getParent(SubS); 1023249423Sdim } 1024249423Sdim return false; 1025249423Sdim} 1026249423Sdim 1027360784Sdimstatic const Stmt *getStmtBeforeCond(const ParentMap &PM, const Stmt *Term, 1028249423Sdim const ExplodedNode *N) { 1029249423Sdim while (N) { 1030249423Sdim Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>(); 1031249423Sdim if (SP) { 1032249423Sdim const Stmt *S = SP->getStmt(); 1033249423Sdim if (!isContainedByStmt(PM, Term, S)) 1034249423Sdim return S; 1035249423Sdim } 1036251662Sdim N = N->getFirstPred(); 1037249423Sdim } 1038276479Sdim return nullptr; 1039249423Sdim} 1040249423Sdim 1041360784Sdimstatic bool isInLoopBody(const ParentMap &PM, const Stmt *S, const Stmt *Term) { 1042276479Sdim const Stmt *LoopBody = nullptr; 1043249423Sdim switch (Term->getStmtClass()) { 1044261991Sdim case Stmt::CXXForRangeStmtClass: { 1045341825Sdim const auto *FR = cast<CXXForRangeStmt>(Term); 1046261991Sdim if (isContainedByStmt(PM, FR->getInc(), S)) 1047261991Sdim return true; 1048261991Sdim if (isContainedByStmt(PM, FR->getLoopVarStmt(), S)) 1049261991Sdim return true; 1050261991Sdim LoopBody = FR->getBody(); 1051261991Sdim break; 1052261991Sdim } 1053249423Sdim case Stmt::ForStmtClass: { 1054341825Sdim const auto *FS = cast<ForStmt>(Term); 1055249423Sdim if (isContainedByStmt(PM, FS->getInc(), S)) 1056249423Sdim return true; 1057249423Sdim LoopBody = FS->getBody(); 1058249423Sdim break; 1059249423Sdim } 1060249423Sdim case Stmt::ObjCForCollectionStmtClass: { 1061341825Sdim const auto *FC = cast<ObjCForCollectionStmt>(Term); 1062249423Sdim LoopBody = FC->getBody(); 1063249423Sdim break; 1064249423Sdim } 1065249423Sdim case Stmt::WhileStmtClass: 1066249423Sdim LoopBody = cast<WhileStmt>(Term)->getBody(); 1067249423Sdim break; 1068249423Sdim default: 1069249423Sdim return false; 1070249423Sdim } 1071249423Sdim return isContainedByStmt(PM, LoopBody, S); 1072249423Sdim} 1073249423Sdim 1074341825Sdim/// Adds a sanitized control-flow diagnostic edge to a path. 1075251662Sdimstatic void addEdgeToPath(PathPieces &path, 1076251662Sdim PathDiagnosticLocation &PrevLoc, 1077344779Sdim PathDiagnosticLocation NewLoc) { 1078251662Sdim if (!NewLoc.isValid()) 1079251662Sdim return; 1080251662Sdim 1081251662Sdim SourceLocation NewLocL = NewLoc.asLocation(); 1082261991Sdim if (NewLocL.isInvalid()) 1083251662Sdim return; 1084251662Sdim 1085261991Sdim if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) { 1086251662Sdim PrevLoc = NewLoc; 1087251662Sdim return; 1088251662Sdim } 1089251662Sdim 1090261991Sdim // Ignore self-edges, which occur when there are multiple nodes at the same 1091261991Sdim // statement. 1092261991Sdim if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt()) 1093251662Sdim return; 1094251662Sdim 1095314564Sdim path.push_front( 1096314564Sdim std::make_shared<PathDiagnosticControlFlowPiece>(NewLoc, PrevLoc)); 1097251662Sdim PrevLoc = NewLoc; 1098251662Sdim} 1099251662Sdim 1100261991Sdim/// A customized wrapper for CFGBlock::getTerminatorCondition() 1101261991Sdim/// which returns the element for ObjCForCollectionStmts. 1102261991Sdimstatic const Stmt *getTerminatorCondition(const CFGBlock *B) { 1103261991Sdim const Stmt *S = B->getTerminatorCondition(); 1104341825Sdim if (const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(S)) 1105261991Sdim return FS->getElement(); 1106261991Sdim return S; 1107261991Sdim} 1108261991Sdim 1109360784Sdimconstexpr llvm::StringLiteral StrEnteringLoop = "Entering loop body"; 1110360784Sdimconstexpr llvm::StringLiteral StrLoopBodyZero = "Loop body executed 0 times"; 1111360784Sdimconstexpr llvm::StringLiteral StrLoopRangeEmpty = 1112360784Sdim "Loop body skipped when range is empty"; 1113360784Sdimconstexpr llvm::StringLiteral StrLoopCollectionEmpty = 1114360784Sdim "Loop body skipped when collection is empty"; 1115261991Sdim 1116341825Sdimstatic std::unique_ptr<FilesToLineNumsMap> 1117360784SdimfindExecutedLines(const SourceManager &SM, const ExplodedNode *N); 1118251662Sdim 1119360784Sdimvoid PathDiagnosticBuilder::generatePathDiagnosticsForNode( 1120360784Sdim PathDiagnosticConstruct &C, PathDiagnosticLocation &PrevLoc) const { 1121360784Sdim ProgramPoint P = C.getCurrentNode()->getLocation(); 1122360784Sdim const SourceManager &SM = getSourceManager(); 1123251662Sdim 1124341825Sdim // Have we encountered an entrance to a call? It may be 1125341825Sdim // the case that we have not encountered a matching 1126341825Sdim // call exit before this point. This means that the path 1127341825Sdim // terminated within the call itself. 1128341825Sdim if (auto CE = P.getAs<CallEnter>()) { 1129251662Sdim 1130360784Sdim if (C.shouldAddPathEdges()) { 1131341825Sdim // Add an edge to the start of the function. 1132341825Sdim const StackFrameContext *CalleeLC = CE->getCalleeContext(); 1133341825Sdim const Decl *D = CalleeLC->getDecl(); 1134341825Sdim // Add the edge only when the callee has body. We jump to the beginning 1135341825Sdim // of the *declaration*, however we expect it to be followed by the 1136341825Sdim // body. This isn't the case for autosynthesized property accessors in 1137341825Sdim // Objective-C. No need for a similar extra check for CallExit points 1138341825Sdim // because the exit edge comes from a statement (i.e. return), 1139341825Sdim // not from declaration. 1140341825Sdim if (D->hasBody()) 1141360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, 1142360784Sdim PathDiagnosticLocation::createBegin(D, SM)); 1143341825Sdim } 1144251662Sdim 1145341825Sdim // Did we visit an entire call? 1146360784Sdim bool VisitedEntireCall = C.PD->isWithinCall(); 1147360784Sdim C.PD->popActivePath(); 1148251662Sdim 1149360784Sdim PathDiagnosticCallPiece *Call; 1150341825Sdim if (VisitedEntireCall) { 1151360784Sdim Call = cast<PathDiagnosticCallPiece>(C.getActivePath().front().get()); 1152341825Sdim } else { 1153360784Sdim // The path terminated within a nested location context, create a new 1154360784Sdim // call piece to encapsulate the rest of the path pieces. 1155341825Sdim const Decl *Caller = CE->getLocationContext()->getDecl(); 1156360784Sdim Call = PathDiagnosticCallPiece::construct(C.getActivePath(), Caller); 1157360784Sdim assert(C.getActivePath().size() == 1 && 1158360784Sdim C.getActivePath().front().get() == Call); 1159261991Sdim 1160360784Sdim // Since we just transferred the path over to the call piece, reset the 1161360784Sdim // mapping of the active path to the current location context. 1162360784Sdim assert(C.isInLocCtxMap(&C.getActivePath()) && 1163360784Sdim "When we ascend to a previously unvisited call, the active path's " 1164360784Sdim "address shouldn't change, but rather should be compacted into " 1165360784Sdim "a single CallEvent!"); 1166360784Sdim C.updateLocCtxMap(&C.getActivePath(), C.getCurrLocationContext()); 1167261991Sdim 1168360784Sdim // Record the location context mapping for the path within the call. 1169360784Sdim assert(!C.isInLocCtxMap(&Call->path) && 1170360784Sdim "When we ascend to a previously unvisited call, this must be the " 1171360784Sdim "first time we encounter the caller context!"); 1172360784Sdim C.updateLocCtxMap(&Call->path, CE->getCalleeContext()); 1173341825Sdim } 1174360784Sdim Call->setCallee(*CE, SM); 1175261991Sdim 1176341825Sdim // Update the previous location in the active path. 1177360784Sdim PrevLoc = Call->getLocation(); 1178261991Sdim 1179360784Sdim if (!C.CallStack.empty()) { 1180360784Sdim assert(C.CallStack.back().first == Call); 1181360784Sdim C.CallStack.pop_back(); 1182341825Sdim } 1183341825Sdim return; 1184341825Sdim } 1185261991Sdim 1186360784Sdim assert(C.getCurrLocationContext() == C.getLocationContextForActivePath() && 1187360784Sdim "The current position in the bug path is out of sync with the " 1188360784Sdim "location context associated with the active path!"); 1189341825Sdim 1190341825Sdim // Have we encountered an exit from a function call? 1191341825Sdim if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) { 1192341825Sdim 1193341825Sdim // We are descending into a call (backwards). Construct 1194341825Sdim // a new call piece to contain the path pieces for that call. 1195360784Sdim auto Call = PathDiagnosticCallPiece::construct(*CE, SM); 1196341825Sdim // Record the mapping from call piece to LocationContext. 1197360784Sdim assert(!C.isInLocCtxMap(&Call->path) && 1198360784Sdim "We just entered a call, this must've been the first time we " 1199360784Sdim "encounter its context!"); 1200360784Sdim C.updateLocCtxMap(&Call->path, CE->getCalleeContext()); 1201341825Sdim 1202360784Sdim if (C.shouldAddPathEdges()) { 1203341825Sdim // Add the edge to the return site. 1204360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, Call->callReturn); 1205341825Sdim PrevLoc.invalidate(); 1206341825Sdim } 1207251662Sdim 1208360784Sdim auto *P = Call.get(); 1209360784Sdim C.getActivePath().push_front(std::move(Call)); 1210261991Sdim 1211341825Sdim // Make the contents of the call the active path for now. 1212360784Sdim C.PD->pushActivePath(&P->path); 1213360784Sdim C.CallStack.push_back(CallWithEntry(P, C.getCurrentNode())); 1214341825Sdim return; 1215341825Sdim } 1216261991Sdim 1217341825Sdim if (auto PS = P.getAs<PostStmt>()) { 1218360784Sdim if (!C.shouldAddPathEdges()) 1219341825Sdim return; 1220251662Sdim 1221341825Sdim // Add an edge. If this is an ObjCForCollectionStmt do 1222341825Sdim // not add an edge here as it appears in the CFG both 1223341825Sdim // as a terminator and as a terminator condition. 1224341825Sdim if (!isa<ObjCForCollectionStmt>(PS->getStmt())) { 1225341825Sdim PathDiagnosticLocation L = 1226360784Sdim PathDiagnosticLocation(PS->getStmt(), SM, C.getCurrLocationContext()); 1227360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, L); 1228341825Sdim } 1229251662Sdim 1230341825Sdim } else if (auto BE = P.getAs<BlockEdge>()) { 1231251662Sdim 1232360784Sdim if (!C.shouldAddPathEdges()) { 1233360784Sdim generateMinimalDiagForBlockEdge(C, *BE); 1234341825Sdim return; 1235341825Sdim } 1236341825Sdim 1237341825Sdim // Are we jumping to the head of a loop? Add a special diagnostic. 1238341825Sdim if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { 1239360784Sdim PathDiagnosticLocation L(Loop, SM, C.getCurrLocationContext()); 1240341825Sdim const Stmt *Body = nullptr; 1241251662Sdim 1242341825Sdim if (const auto *FS = dyn_cast<ForStmt>(Loop)) 1243341825Sdim Body = FS->getBody(); 1244341825Sdim else if (const auto *WS = dyn_cast<WhileStmt>(Loop)) 1245341825Sdim Body = WS->getBody(); 1246341825Sdim else if (const auto *OFS = dyn_cast<ObjCForCollectionStmt>(Loop)) { 1247341825Sdim Body = OFS->getBody(); 1248341825Sdim } else if (const auto *FRS = dyn_cast<CXXForRangeStmt>(Loop)) { 1249341825Sdim Body = FRS->getBody(); 1250251662Sdim } 1251341825Sdim // do-while statements are explicitly excluded here 1252251662Sdim 1253341825Sdim auto p = std::make_shared<PathDiagnosticEventPiece>( 1254341825Sdim L, "Looping back to the head " 1255341825Sdim "of the loop"); 1256341825Sdim p->setPrunable(true); 1257251662Sdim 1258360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, p->getLocation()); 1259360784Sdim C.getActivePath().push_front(std::move(p)); 1260251662Sdim 1261341825Sdim if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Body)) { 1262360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, 1263360784Sdim PathDiagnosticLocation::createEndBrace(CS, SM)); 1264341825Sdim } 1265341825Sdim } 1266251662Sdim 1267341825Sdim const CFGBlock *BSrc = BE->getSrc(); 1268360784Sdim const ParentMap &PM = C.getParentMap(); 1269251662Sdim 1270353358Sdim if (const Stmt *Term = BSrc->getTerminatorStmt()) { 1271341825Sdim // Are we jumping past the loop body without ever executing the 1272341825Sdim // loop (because the condition was false)? 1273341825Sdim if (isLoop(Term)) { 1274341825Sdim const Stmt *TermCond = getTerminatorCondition(BSrc); 1275360784Sdim bool IsInLoopBody = isInLoopBody( 1276360784Sdim PM, getStmtBeforeCond(PM, TermCond, C.getCurrentNode()), Term); 1277251662Sdim 1278360784Sdim StringRef str; 1279261991Sdim 1280341825Sdim if (isJumpToFalseBranch(&*BE)) { 1281341825Sdim if (!IsInLoopBody) { 1282341825Sdim if (isa<ObjCForCollectionStmt>(Term)) { 1283341825Sdim str = StrLoopCollectionEmpty; 1284341825Sdim } else if (isa<CXXForRangeStmt>(Term)) { 1285341825Sdim str = StrLoopRangeEmpty; 1286261991Sdim } else { 1287341825Sdim str = StrLoopBodyZero; 1288261991Sdim } 1289251662Sdim } 1290341825Sdim } else { 1291341825Sdim str = StrEnteringLoop; 1292251662Sdim } 1293251662Sdim 1294360784Sdim if (!str.empty()) { 1295360784Sdim PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, 1296360784Sdim C.getCurrLocationContext()); 1297341825Sdim auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str); 1298341825Sdim PE->setPrunable(true); 1299360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, PE->getLocation()); 1300360784Sdim C.getActivePath().push_front(std::move(PE)); 1301341825Sdim } 1302341825Sdim } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) || 1303341825Sdim isa<GotoStmt>(Term)) { 1304360784Sdim PathDiagnosticLocation L(Term, SM, C.getCurrLocationContext()); 1305360784Sdim addEdgeToPath(C.getActivePath(), PrevLoc, L); 1306251662Sdim } 1307251662Sdim } 1308251662Sdim } 1309251662Sdim} 1310251662Sdim 1311341825Sdimstatic std::unique_ptr<PathDiagnostic> 1312360784SdimgenerateDiagnosticForBasicReport(const BasicBugReport *R) { 1313353358Sdim const BugType &BT = R->getBugType(); 1314360784Sdim return std::make_unique<PathDiagnostic>( 1315360784Sdim BT.getCheckerName(), R->getDeclWithIssue(), BT.getDescription(), 1316360784Sdim R->getDescription(), R->getShortDescription(/*UseFallback=*/false), 1317360784Sdim BT.getCategory(), R->getUniqueingLocation(), R->getUniqueingDecl(), 1318360784Sdim std::make_unique<FilesToLineNumsMap>()); 1319360784Sdim} 1320360784Sdim 1321360784Sdimstatic std::unique_ptr<PathDiagnostic> 1322360784SdimgenerateEmptyDiagnosticForReport(const PathSensitiveBugReport *R, 1323360784Sdim const SourceManager &SM) { 1324360784Sdim const BugType &BT = R->getBugType(); 1325360784Sdim return std::make_unique<PathDiagnostic>( 1326360784Sdim BT.getCheckerName(), R->getDeclWithIssue(), BT.getDescription(), 1327360784Sdim R->getDescription(), R->getShortDescription(/*UseFallback=*/false), 1328360784Sdim BT.getCategory(), R->getUniqueingLocation(), R->getUniqueingDecl(), 1329341825Sdim findExecutedLines(SM, R->getErrorNode())); 1330251662Sdim} 1331251662Sdim 1332261991Sdimstatic const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) { 1333251662Sdim if (!S) 1334276479Sdim return nullptr; 1335261991Sdim 1336261991Sdim while (true) { 1337261991Sdim S = PM.getParentIgnoreParens(S); 1338261991Sdim 1339261991Sdim if (!S) 1340261991Sdim break; 1341261991Sdim 1342344779Sdim if (isa<FullExpr>(S) || 1343261991Sdim isa<CXXBindTemporaryExpr>(S) || 1344261991Sdim isa<SubstNonTypeTemplateParmExpr>(S)) 1345261991Sdim continue; 1346261991Sdim 1347261991Sdim break; 1348261991Sdim } 1349261991Sdim 1350261991Sdim return S; 1351251662Sdim} 1352251662Sdim 1353251662Sdimstatic bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) { 1354251662Sdim switch (S->getStmtClass()) { 1355261991Sdim case Stmt::BinaryOperatorClass: { 1356341825Sdim const auto *BO = cast<BinaryOperator>(S); 1357261991Sdim if (!BO->isLogicalOp()) 1358261991Sdim return false; 1359261991Sdim return BO->getLHS() == Cond || BO->getRHS() == Cond; 1360261991Sdim } 1361261991Sdim case Stmt::IfStmtClass: 1362261991Sdim return cast<IfStmt>(S)->getCond() == Cond; 1363251662Sdim case Stmt::ForStmtClass: 1364251662Sdim return cast<ForStmt>(S)->getCond() == Cond; 1365251662Sdim case Stmt::WhileStmtClass: 1366251662Sdim return cast<WhileStmt>(S)->getCond() == Cond; 1367251662Sdim case Stmt::DoStmtClass: 1368251662Sdim return cast<DoStmt>(S)->getCond() == Cond; 1369251662Sdim case Stmt::ChooseExprClass: 1370251662Sdim return cast<ChooseExpr>(S)->getCond() == Cond; 1371251662Sdim case Stmt::IndirectGotoStmtClass: 1372251662Sdim return cast<IndirectGotoStmt>(S)->getTarget() == Cond; 1373251662Sdim case Stmt::SwitchStmtClass: 1374251662Sdim return cast<SwitchStmt>(S)->getCond() == Cond; 1375251662Sdim case Stmt::BinaryConditionalOperatorClass: 1376251662Sdim return cast<BinaryConditionalOperator>(S)->getCond() == Cond; 1377261991Sdim case Stmt::ConditionalOperatorClass: { 1378341825Sdim const auto *CO = cast<ConditionalOperator>(S); 1379261991Sdim return CO->getCond() == Cond || 1380261991Sdim CO->getLHS() == Cond || 1381261991Sdim CO->getRHS() == Cond; 1382261991Sdim } 1383251662Sdim case Stmt::ObjCForCollectionStmtClass: 1384251662Sdim return cast<ObjCForCollectionStmt>(S)->getElement() == Cond; 1385261991Sdim case Stmt::CXXForRangeStmtClass: { 1386341825Sdim const auto *FRS = cast<CXXForRangeStmt>(S); 1387261991Sdim return FRS->getCond() == Cond || FRS->getRangeInit() == Cond; 1388261991Sdim } 1389251662Sdim default: 1390251662Sdim return false; 1391251662Sdim } 1392251662Sdim} 1393251662Sdim 1394261991Sdimstatic bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) { 1395341825Sdim if (const auto *FS = dyn_cast<ForStmt>(FL)) 1396261991Sdim return FS->getInc() == S || FS->getInit() == S; 1397341825Sdim if (const auto *FRS = dyn_cast<CXXForRangeStmt>(FL)) 1398261991Sdim return FRS->getInc() == S || FRS->getRangeStmt() == S || 1399261991Sdim FRS->getLoopVarStmt() || FRS->getRangeInit() == S; 1400261991Sdim return false; 1401261991Sdim} 1402251662Sdim 1403341825Sdimusing OptimizedCallsSet = llvm::DenseSet<const PathDiagnosticCallPiece *>; 1404251662Sdim 1405261991Sdim/// Adds synthetic edges from top-level statements to their subexpressions. 1406261991Sdim/// 1407261991Sdim/// This avoids a "swoosh" effect, where an edge from a top-level statement A 1408261991Sdim/// points to a sub-expression B.1 that's not at the start of B. In these cases, 1409261991Sdim/// we'd like to see an edge from A to B, then another one from B to B.1. 1410360784Sdimstatic void addContextEdges(PathPieces &pieces, const LocationContext *LC) { 1411360784Sdim const ParentMap &PM = LC->getParentMap(); 1412261991Sdim PathPieces::iterator Prev = pieces.end(); 1413261991Sdim for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E; 1414261991Sdim Prev = I, ++I) { 1415341825Sdim auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1416261991Sdim 1417261991Sdim if (!Piece) 1418261991Sdim continue; 1419261991Sdim 1420261991Sdim PathDiagnosticLocation SrcLoc = Piece->getStartLocation(); 1421261991Sdim SmallVector<PathDiagnosticLocation, 4> SrcContexts; 1422261991Sdim 1423261991Sdim PathDiagnosticLocation NextSrcContext = SrcLoc; 1424276479Sdim const Stmt *InnerStmt = nullptr; 1425261991Sdim while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) { 1426261991Sdim SrcContexts.push_back(NextSrcContext); 1427261991Sdim InnerStmt = NextSrcContext.asStmt(); 1428360784Sdim NextSrcContext = getEnclosingStmtLocation(InnerStmt, LC, 1429261991Sdim /*allowNested=*/true); 1430261991Sdim } 1431261991Sdim 1432261991Sdim // Repeatedly split the edge as necessary. 1433261991Sdim // This is important for nested logical expressions (||, &&, ?:) where we 1434261991Sdim // want to show all the levels of context. 1435261991Sdim while (true) { 1436341825Sdim const Stmt *Dst = Piece->getEndLocation().getStmtOrNull(); 1437261991Sdim 1438261991Sdim // We are looking at an edge. Is the destination within a larger 1439261991Sdim // expression? 1440261991Sdim PathDiagnosticLocation DstContext = 1441360784Sdim getEnclosingStmtLocation(Dst, LC, /*allowNested=*/true); 1442261991Sdim if (!DstContext.isValid() || DstContext.asStmt() == Dst) 1443261991Sdim break; 1444261991Sdim 1445261991Sdim // If the source is in the same context, we're already good. 1446353358Sdim if (llvm::find(SrcContexts, DstContext) != SrcContexts.end()) 1447261991Sdim break; 1448261991Sdim 1449261991Sdim // Update the subexpression node to point to the context edge. 1450261991Sdim Piece->setStartLocation(DstContext); 1451261991Sdim 1452261991Sdim // Try to extend the previous edge if it's at the same level as the source 1453261991Sdim // context. 1454261991Sdim if (Prev != E) { 1455314564Sdim auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get()); 1456261991Sdim 1457261991Sdim if (PrevPiece) { 1458341825Sdim if (const Stmt *PrevSrc = 1459341825Sdim PrevPiece->getStartLocation().getStmtOrNull()) { 1460261991Sdim const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM); 1461341825Sdim if (PrevSrcParent == 1462341825Sdim getStmtParent(DstContext.getStmtOrNull(), PM)) { 1463261991Sdim PrevPiece->setEndLocation(DstContext); 1464261991Sdim break; 1465261991Sdim } 1466261991Sdim } 1467261991Sdim } 1468261991Sdim } 1469261991Sdim 1470261991Sdim // Otherwise, split the current edge into a context edge and a 1471261991Sdim // subexpression edge. Note that the context statement may itself have 1472261991Sdim // context. 1473314564Sdim auto P = 1474314564Sdim std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext); 1475314564Sdim Piece = P.get(); 1476314564Sdim I = pieces.insert(I, std::move(P)); 1477261991Sdim } 1478261991Sdim } 1479251662Sdim} 1480251662Sdim 1481341825Sdim/// Move edges from a branch condition to a branch target 1482261991Sdim/// when the condition is simple. 1483261991Sdim/// 1484261991Sdim/// This restructures some of the work of addContextEdges. That function 1485261991Sdim/// creates edges this may destroy, but they work together to create a more 1486261991Sdim/// aesthetically set of edges around branches. After the call to 1487261991Sdim/// addContextEdges, we may have (1) an edge to the branch, (2) an edge from 1488261991Sdim/// the branch to the branch condition, and (3) an edge from the branch 1489261991Sdim/// condition to the branch target. We keep (1), but may wish to remove (2) 1490261991Sdim/// and move the source of (3) to the branch if the branch condition is simple. 1491261991Sdimstatic void simplifySimpleBranches(PathPieces &pieces) { 1492261991Sdim for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) { 1493341825Sdim const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1494261991Sdim 1495261991Sdim if (!PieceI) 1496261991Sdim continue; 1497261991Sdim 1498341825Sdim const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1499341825Sdim const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1500261991Sdim 1501261991Sdim if (!s1Start || !s1End) 1502261991Sdim continue; 1503261991Sdim 1504261991Sdim PathPieces::iterator NextI = I; ++NextI; 1505261991Sdim if (NextI == E) 1506261991Sdim break; 1507261991Sdim 1508276479Sdim PathDiagnosticControlFlowPiece *PieceNextI = nullptr; 1509261991Sdim 1510261991Sdim while (true) { 1511261991Sdim if (NextI == E) 1512261991Sdim break; 1513261991Sdim 1514341825Sdim const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get()); 1515261991Sdim if (EV) { 1516261991Sdim StringRef S = EV->getString(); 1517261991Sdim if (S == StrEnteringLoop || S == StrLoopBodyZero || 1518261991Sdim S == StrLoopCollectionEmpty || S == StrLoopRangeEmpty) { 1519261991Sdim ++NextI; 1520261991Sdim continue; 1521261991Sdim } 1522261991Sdim break; 1523261991Sdim } 1524261991Sdim 1525314564Sdim PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1526261991Sdim break; 1527261991Sdim } 1528261991Sdim 1529261991Sdim if (!PieceNextI) 1530261991Sdim continue; 1531261991Sdim 1532341825Sdim const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1533341825Sdim const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1534261991Sdim 1535261991Sdim if (!s2Start || !s2End || s1End != s2Start) 1536261991Sdim continue; 1537261991Sdim 1538261991Sdim // We only perform this transformation for specific branch kinds. 1539261991Sdim // We don't want to do this for do..while, for example. 1540261991Sdim if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) || 1541261991Sdim isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) || 1542261991Sdim isa<CXXForRangeStmt>(s1Start))) 1543261991Sdim continue; 1544261991Sdim 1545261991Sdim // Is s1End the branch condition? 1546261991Sdim if (!isConditionForTerminator(s1Start, s1End)) 1547261991Sdim continue; 1548261991Sdim 1549261991Sdim // Perform the hoisting by eliminating (2) and changing the start 1550261991Sdim // location of (3). 1551261991Sdim PieceNextI->setStartLocation(PieceI->getStartLocation()); 1552261991Sdim I = pieces.erase(I); 1553261991Sdim } 1554261991Sdim} 1555261991Sdim 1556261991Sdim/// Returns the number of bytes in the given (character-based) SourceRange. 1557261991Sdim/// 1558261991Sdim/// If the locations in the range are not on the same line, returns None. 1559261991Sdim/// 1560261991Sdim/// Note that this does not do a precise user-visible character or column count. 1561360784Sdimstatic Optional<size_t> getLengthOnSingleLine(const SourceManager &SM, 1562261991Sdim SourceRange Range) { 1563261991Sdim SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()), 1564341825Sdim SM.getExpansionRange(Range.getEnd()).getEnd()); 1565261991Sdim 1566261991Sdim FileID FID = SM.getFileID(ExpansionRange.getBegin()); 1567261991Sdim if (FID != SM.getFileID(ExpansionRange.getEnd())) 1568261991Sdim return None; 1569261991Sdim 1570261991Sdim bool Invalid; 1571261991Sdim const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid); 1572261991Sdim if (Invalid) 1573261991Sdim return None; 1574261991Sdim 1575261991Sdim unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin()); 1576261991Sdim unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd()); 1577261991Sdim StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset); 1578261991Sdim 1579261991Sdim // We're searching the raw bytes of the buffer here, which might include 1580261991Sdim // escaped newlines and such. That's okay; we're trying to decide whether the 1581261991Sdim // SourceRange is covering a large or small amount of space in the user's 1582261991Sdim // editor. 1583261991Sdim if (Snippet.find_first_of("\r\n") != StringRef::npos) 1584261991Sdim return None; 1585261991Sdim 1586261991Sdim // This isn't Unicode-aware, but it doesn't need to be. 1587261991Sdim return Snippet.size(); 1588261991Sdim} 1589261991Sdim 1590261991Sdim/// \sa getLengthOnSingleLine(SourceManager, SourceRange) 1591360784Sdimstatic Optional<size_t> getLengthOnSingleLine(const SourceManager &SM, 1592261991Sdim const Stmt *S) { 1593261991Sdim return getLengthOnSingleLine(SM, S->getSourceRange()); 1594261991Sdim} 1595261991Sdim 1596261991Sdim/// Eliminate two-edge cycles created by addContextEdges(). 1597261991Sdim/// 1598261991Sdim/// Once all the context edges are in place, there are plenty of cases where 1599261991Sdim/// there's a single edge from a top-level statement to a subexpression, 1600261991Sdim/// followed by a single path note, and then a reverse edge to get back out to 1601261991Sdim/// the top level. If the statement is simple enough, the subexpression edges 1602261991Sdim/// just add noise and make it harder to understand what's going on. 1603261991Sdim/// 1604261991Sdim/// This function only removes edges in pairs, because removing only one edge 1605261991Sdim/// might leave other edges dangling. 1606261991Sdim/// 1607261991Sdim/// This will not remove edges in more complicated situations: 1608261991Sdim/// - if there is more than one "hop" leading to or from a subexpression. 1609261991Sdim/// - if there is an inlined call between the edges instead of a single event. 1610261991Sdim/// - if the whole statement is large enough that having subexpression arrows 1611261991Sdim/// might be helpful. 1612360784Sdimstatic void removeContextCycles(PathPieces &Path, const SourceManager &SM) { 1613261991Sdim for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) { 1614261991Sdim // Pattern match the current piece and its successor. 1615341825Sdim const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1616261991Sdim 1617261991Sdim if (!PieceI) { 1618261991Sdim ++I; 1619261991Sdim continue; 1620261991Sdim } 1621261991Sdim 1622341825Sdim const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1623341825Sdim const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1624261991Sdim 1625261991Sdim PathPieces::iterator NextI = I; ++NextI; 1626261991Sdim if (NextI == E) 1627261991Sdim break; 1628261991Sdim 1629341825Sdim const auto *PieceNextI = 1630314564Sdim dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1631261991Sdim 1632261991Sdim if (!PieceNextI) { 1633314564Sdim if (isa<PathDiagnosticEventPiece>(NextI->get())) { 1634261991Sdim ++NextI; 1635261991Sdim if (NextI == E) 1636261991Sdim break; 1637314564Sdim PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1638261991Sdim } 1639261991Sdim 1640261991Sdim if (!PieceNextI) { 1641261991Sdim ++I; 1642261991Sdim continue; 1643261991Sdim } 1644261991Sdim } 1645261991Sdim 1646341825Sdim const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1647341825Sdim const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1648261991Sdim 1649261991Sdim if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) { 1650261991Sdim const size_t MAX_SHORT_LINE_LENGTH = 80; 1651261991Sdim Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start); 1652261991Sdim if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) { 1653261991Sdim Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start); 1654261991Sdim if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) { 1655261991Sdim Path.erase(I); 1656261991Sdim I = Path.erase(NextI); 1657261991Sdim continue; 1658261991Sdim } 1659261991Sdim } 1660261991Sdim } 1661261991Sdim 1662261991Sdim ++I; 1663261991Sdim } 1664261991Sdim} 1665261991Sdim 1666341825Sdim/// Return true if X is contained by Y. 1667360784Sdimstatic bool lexicalContains(const ParentMap &PM, const Stmt *X, const Stmt *Y) { 1668261991Sdim while (X) { 1669261991Sdim if (X == Y) 1670261991Sdim return true; 1671261991Sdim X = PM.getParent(X); 1672261991Sdim } 1673261991Sdim return false; 1674261991Sdim} 1675261991Sdim 1676261991Sdim// Remove short edges on the same line less than 3 columns in difference. 1677360784Sdimstatic void removePunyEdges(PathPieces &path, const SourceManager &SM, 1678360784Sdim const ParentMap &PM) { 1679261991Sdim bool erased = false; 1680261991Sdim 1681261991Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 1682261991Sdim erased ? I : ++I) { 1683261991Sdim erased = false; 1684261991Sdim 1685341825Sdim const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1686261991Sdim 1687261991Sdim if (!PieceI) 1688261991Sdim continue; 1689261991Sdim 1690341825Sdim const Stmt *start = PieceI->getStartLocation().getStmtOrNull(); 1691341825Sdim const Stmt *end = PieceI->getEndLocation().getStmtOrNull(); 1692261991Sdim 1693261991Sdim if (!start || !end) 1694261991Sdim continue; 1695261991Sdim 1696261991Sdim const Stmt *endParent = PM.getParent(end); 1697261991Sdim if (!endParent) 1698261991Sdim continue; 1699261991Sdim 1700261991Sdim if (isConditionForTerminator(end, endParent)) 1701261991Sdim continue; 1702261991Sdim 1703344779Sdim SourceLocation FirstLoc = start->getBeginLoc(); 1704344779Sdim SourceLocation SecondLoc = end->getBeginLoc(); 1705261991Sdim 1706261991Sdim if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc)) 1707261991Sdim continue; 1708261991Sdim if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc)) 1709261991Sdim std::swap(SecondLoc, FirstLoc); 1710261991Sdim 1711261991Sdim SourceRange EdgeRange(FirstLoc, SecondLoc); 1712261991Sdim Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange); 1713261991Sdim 1714261991Sdim // If the statements are on different lines, continue. 1715261991Sdim if (!ByteWidth) 1716261991Sdim continue; 1717261991Sdim 1718261991Sdim const size_t MAX_PUNY_EDGE_LENGTH = 2; 1719261991Sdim if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) { 1720261991Sdim // FIXME: There are enough /bytes/ between the endpoints of the edge, but 1721261991Sdim // there might not be enough /columns/. A proper user-visible column count 1722261991Sdim // is probably too expensive, though. 1723261991Sdim I = path.erase(I); 1724261991Sdim erased = true; 1725261991Sdim continue; 1726261991Sdim } 1727261991Sdim } 1728261991Sdim} 1729261991Sdim 1730261991Sdimstatic void removeIdenticalEvents(PathPieces &path) { 1731261991Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) { 1732341825Sdim const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get()); 1733261991Sdim 1734261991Sdim if (!PieceI) 1735261991Sdim continue; 1736261991Sdim 1737261991Sdim PathPieces::iterator NextI = I; ++NextI; 1738261991Sdim if (NextI == E) 1739261991Sdim return; 1740261991Sdim 1741341825Sdim const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get()); 1742261991Sdim 1743261991Sdim if (!PieceNextI) 1744261991Sdim continue; 1745261991Sdim 1746261991Sdim // Erase the second piece if it has the same exact message text. 1747261991Sdim if (PieceI->getString() == PieceNextI->getString()) { 1748261991Sdim path.erase(NextI); 1749261991Sdim } 1750261991Sdim } 1751261991Sdim} 1752261991Sdim 1753360784Sdimstatic bool optimizeEdges(const PathDiagnosticConstruct &C, PathPieces &path, 1754360784Sdim OptimizedCallsSet &OCS) { 1755251662Sdim bool hasChanges = false; 1756360784Sdim const LocationContext *LC = C.getLocationContextFor(&path); 1757251662Sdim assert(LC); 1758360784Sdim const ParentMap &PM = LC->getParentMap(); 1759360784Sdim const SourceManager &SM = C.getSourceManager(); 1760251662Sdim 1761251662Sdim for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) { 1762251662Sdim // Optimize subpaths. 1763314564Sdim if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) { 1764251662Sdim // Record the fact that a call has been optimized so we only do the 1765251662Sdim // effort once. 1766251662Sdim if (!OCS.count(CallI)) { 1767360784Sdim while (optimizeEdges(C, CallI->path, OCS)) { 1768360784Sdim } 1769251662Sdim OCS.insert(CallI); 1770251662Sdim } 1771251662Sdim ++I; 1772251662Sdim continue; 1773251662Sdim } 1774251662Sdim 1775251662Sdim // Pattern match the current piece and its successor. 1776314564Sdim auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get()); 1777251662Sdim 1778251662Sdim if (!PieceI) { 1779251662Sdim ++I; 1780251662Sdim continue; 1781251662Sdim } 1782251662Sdim 1783341825Sdim const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull(); 1784341825Sdim const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull(); 1785251662Sdim const Stmt *level1 = getStmtParent(s1Start, PM); 1786251662Sdim const Stmt *level2 = getStmtParent(s1End, PM); 1787251662Sdim 1788251662Sdim PathPieces::iterator NextI = I; ++NextI; 1789251662Sdim if (NextI == E) 1790251662Sdim break; 1791251662Sdim 1792341825Sdim const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get()); 1793251662Sdim 1794251662Sdim if (!PieceNextI) { 1795251662Sdim ++I; 1796251662Sdim continue; 1797251662Sdim } 1798251662Sdim 1799341825Sdim const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull(); 1800341825Sdim const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull(); 1801251662Sdim const Stmt *level3 = getStmtParent(s2Start, PM); 1802251662Sdim const Stmt *level4 = getStmtParent(s2End, PM); 1803251662Sdim 1804251662Sdim // Rule I. 1805251662Sdim // 1806251662Sdim // If we have two consecutive control edges whose end/begin locations 1807251662Sdim // are at the same level (e.g. statements or top-level expressions within 1808251662Sdim // a compound statement, or siblings share a single ancestor expression), 1809251662Sdim // then merge them if they have no interesting intermediate event. 1810251662Sdim // 1811251662Sdim // For example: 1812251662Sdim // 1813251662Sdim // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common 1814251662Sdim // parent is '1'. Here 'x.y.z' represents the hierarchy of statements. 1815251662Sdim // 1816251662Sdim // NOTE: this will be limited later in cases where we add barriers 1817251662Sdim // to prevent this optimization. 1818251662Sdim if (level1 && level1 == level2 && level1 == level3 && level1 == level4) { 1819251662Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 1820251662Sdim path.erase(NextI); 1821251662Sdim hasChanges = true; 1822251662Sdim continue; 1823251662Sdim } 1824251662Sdim 1825251662Sdim // Rule II. 1826251662Sdim // 1827261991Sdim // Eliminate edges between subexpressions and parent expressions 1828261991Sdim // when the subexpression is consumed. 1829251662Sdim // 1830251662Sdim // NOTE: this will be limited later in cases where we add barriers 1831251662Sdim // to prevent this optimization. 1832261991Sdim if (s1End && s1End == s2Start && level2) { 1833261991Sdim bool removeEdge = false; 1834261991Sdim // Remove edges into the increment or initialization of a 1835261991Sdim // loop that have no interleaving event. This means that 1836261991Sdim // they aren't interesting. 1837261991Sdim if (isIncrementOrInitInForLoop(s1End, level2)) 1838261991Sdim removeEdge = true; 1839261991Sdim // Next only consider edges that are not anchored on 1840261991Sdim // the condition of a terminator. This are intermediate edges 1841261991Sdim // that we might want to trim. 1842261991Sdim else if (!isConditionForTerminator(level2, s1End)) { 1843261991Sdim // Trim edges on expressions that are consumed by 1844261991Sdim // the parent expression. 1845261991Sdim if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) { 1846296417Sdim removeEdge = true; 1847261991Sdim } 1848261991Sdim // Trim edges where a lexical containment doesn't exist. 1849261991Sdim // For example: 1850261991Sdim // 1851261991Sdim // X -> Y -> Z 1852261991Sdim // 1853261991Sdim // If 'Z' lexically contains Y (it is an ancestor) and 1854261991Sdim // 'X' does not lexically contain Y (it is a descendant OR 1855261991Sdim // it has no lexical relationship at all) then trim. 1856261991Sdim // 1857261991Sdim // This can eliminate edges where we dive into a subexpression 1858261991Sdim // and then pop back out, etc. 1859261991Sdim else if (s1Start && s2End && 1860261991Sdim lexicalContains(PM, s2Start, s2End) && 1861261991Sdim !lexicalContains(PM, s1End, s1Start)) { 1862261991Sdim removeEdge = true; 1863261991Sdim } 1864261991Sdim // Trim edges from a subexpression back to the top level if the 1865261991Sdim // subexpression is on a different line. 1866261991Sdim // 1867261991Sdim // A.1 -> A -> B 1868261991Sdim // becomes 1869261991Sdim // A.1 -> B 1870261991Sdim // 1871261991Sdim // These edges just look ugly and don't usually add anything. 1872261991Sdim else if (s1Start && s2End && 1873261991Sdim lexicalContains(PM, s1Start, s1End)) { 1874261991Sdim SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), 1875261991Sdim PieceI->getStartLocation().asLocation()); 1876261991Sdim if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) 1877261991Sdim removeEdge = true; 1878261991Sdim } 1879261991Sdim } 1880251662Sdim 1881261991Sdim if (removeEdge) { 1882261991Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 1883261991Sdim path.erase(NextI); 1884261991Sdim hasChanges = true; 1885261991Sdim continue; 1886261991Sdim } 1887251662Sdim } 1888251662Sdim 1889261991Sdim // Optimize edges for ObjC fast-enumeration loops. 1890251662Sdim // 1891261991Sdim // (X -> collection) -> (collection -> element) 1892251662Sdim // 1893261991Sdim // becomes: 1894251662Sdim // 1895261991Sdim // (X -> element) 1896261991Sdim if (s1End == s2Start) { 1897341825Sdim const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3); 1898261991Sdim if (FS && FS->getCollection()->IgnoreParens() == s2Start && 1899261991Sdim s2End == FS->getElement()) { 1900261991Sdim PieceI->setEndLocation(PieceNextI->getEndLocation()); 1901261991Sdim path.erase(NextI); 1902251662Sdim hasChanges = true; 1903251662Sdim continue; 1904251662Sdim } 1905251662Sdim } 1906251662Sdim 1907251662Sdim // No changes at this index? Move to the next one. 1908251662Sdim ++I; 1909251662Sdim } 1910251662Sdim 1911261991Sdim if (!hasChanges) { 1912261991Sdim // Adjust edges into subexpressions to make them more uniform 1913261991Sdim // and aesthetically pleasing. 1914360784Sdim addContextEdges(path, LC); 1915261991Sdim // Remove "cyclical" edges that include one or more context edges. 1916344779Sdim removeContextCycles(path, SM); 1917261991Sdim // Hoist edges originating from branch conditions to branches 1918261991Sdim // for simple branches. 1919261991Sdim simplifySimpleBranches(path); 1920261991Sdim // Remove any puny edges left over after primary optimization pass. 1921261991Sdim removePunyEdges(path, SM, PM); 1922261991Sdim // Remove identical events. 1923261991Sdim removeIdenticalEvents(path); 1924261991Sdim } 1925261991Sdim 1926251662Sdim return hasChanges; 1927251662Sdim} 1928251662Sdim 1929261991Sdim/// Drop the very first edge in a path, which should be a function entry edge. 1930261991Sdim/// 1931261991Sdim/// If the first edge is not a function entry edge (say, because the first 1932261991Sdim/// statement had an invalid source location), this function does nothing. 1933261991Sdim// FIXME: We should just generate invalid edges anyway and have the optimizer 1934261991Sdim// deal with them. 1935360784Sdimstatic void dropFunctionEntryEdge(const PathDiagnosticConstruct &C, 1936360784Sdim PathPieces &Path) { 1937314564Sdim const auto *FirstEdge = 1938314564Sdim dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get()); 1939261991Sdim if (!FirstEdge) 1940261991Sdim return; 1941261991Sdim 1942360784Sdim const Decl *D = C.getLocationContextFor(&Path)->getDecl(); 1943360784Sdim PathDiagnosticLocation EntryLoc = 1944360784Sdim PathDiagnosticLocation::createBegin(D, C.getSourceManager()); 1945261991Sdim if (FirstEdge->getStartLocation() != EntryLoc) 1946261991Sdim return; 1947261991Sdim 1948261991Sdim Path.pop_front(); 1949261991Sdim} 1950261991Sdim 1951344779Sdim/// Populate executes lines with lines containing at least one diagnostics. 1952360784Sdimstatic void updateExecutedLinesWithDiagnosticPieces(PathDiagnostic &PD) { 1953344779Sdim 1954344779Sdim PathPieces path = PD.path.flatten(/*ShouldFlattenMacros=*/true); 1955344779Sdim FilesToLineNumsMap &ExecutedLines = PD.getExecutedLines(); 1956344779Sdim 1957344779Sdim for (const auto &P : path) { 1958344779Sdim FullSourceLoc Loc = P->getLocation().asLocation().getExpansionLoc(); 1959344779Sdim FileID FID = Loc.getFileID(); 1960344779Sdim unsigned LineNo = Loc.getLineNumber(); 1961344779Sdim assert(FID.isValid()); 1962344779Sdim ExecutedLines[FID].insert(LineNo); 1963344779Sdim } 1964344779Sdim} 1965344779Sdim 1966360784SdimPathDiagnosticConstruct::PathDiagnosticConstruct( 1967360784Sdim const PathDiagnosticConsumer *PDC, const ExplodedNode *ErrorNode, 1968360784Sdim const PathSensitiveBugReport *R) 1969360784Sdim : Consumer(PDC), CurrentNode(ErrorNode), 1970360784Sdim SM(CurrentNode->getCodeDecl().getASTContext().getSourceManager()), 1971360784Sdim PD(generateEmptyDiagnosticForReport(R, getSourceManager())) { 1972360784Sdim LCM[&PD->getActivePath()] = ErrorNode->getLocationContext(); 1973360784Sdim} 1974341825Sdim 1975360784SdimPathDiagnosticBuilder::PathDiagnosticBuilder( 1976360784Sdim BugReporterContext BRC, std::unique_ptr<ExplodedGraph> BugPath, 1977360784Sdim PathSensitiveBugReport *r, const ExplodedNode *ErrorNode, 1978360784Sdim std::unique_ptr<VisitorsDiagnosticsTy> VisitorsDiagnostics) 1979360784Sdim : BugReporterContext(BRC), BugPath(std::move(BugPath)), R(r), 1980360784Sdim ErrorNode(ErrorNode), 1981360784Sdim VisitorsDiagnostics(std::move(VisitorsDiagnostics)) {} 1982341825Sdim 1983360784Sdimstd::unique_ptr<PathDiagnostic> 1984360784SdimPathDiagnosticBuilder::generate(const PathDiagnosticConsumer *PDC) const { 1985360784Sdim PathDiagnosticConstruct Construct(PDC, ErrorNode, R); 1986360784Sdim 1987360784Sdim const SourceManager &SM = getSourceManager(); 1988360784Sdim const AnalyzerOptions &Opts = getAnalyzerOptions(); 1989360784Sdim StringRef ErrorTag = ErrorNode->getLocation().getTag()->getTagDescription(); 1990360784Sdim 1991360784Sdim // See whether we need to silence the checker/package. 1992360784Sdim // FIXME: This will not work if the report was emitted with an incorrect tag. 1993360784Sdim for (const std::string &CheckerOrPackage : Opts.SilencedCheckersAndPackages) { 1994360784Sdim if (ErrorTag.startswith(CheckerOrPackage)) 1995360784Sdim return nullptr; 1996341825Sdim } 1997341825Sdim 1998360784Sdim if (!PDC->shouldGenerateDiagnostics()) 1999360784Sdim return generateEmptyDiagnosticForReport(R, getSourceManager()); 2000341825Sdim 2001360784Sdim // Construct the final (warning) event for the bug report. 2002360784Sdim auto EndNotes = VisitorsDiagnostics->find(ErrorNode); 2003360784Sdim PathDiagnosticPieceRef LastPiece; 2004360784Sdim if (EndNotes != VisitorsDiagnostics->end()) { 2005360784Sdim assert(!EndNotes->second.empty()); 2006360784Sdim LastPiece = EndNotes->second[0]; 2007360784Sdim } else { 2008360784Sdim LastPiece = BugReporterVisitor::getDefaultEndPath(*this, ErrorNode, 2009360784Sdim *getBugReport()); 2010360784Sdim } 2011360784Sdim Construct.PD->setEndOfPath(LastPiece); 2012360784Sdim 2013360784Sdim PathDiagnosticLocation PrevLoc = Construct.PD->getLocation(); 2014360784Sdim // From the error node to the root, ascend the bug path and construct the bug 2015360784Sdim // report. 2016360784Sdim while (Construct.ascendToPrevNode()) { 2017360784Sdim generatePathDiagnosticsForNode(Construct, PrevLoc); 2018360784Sdim 2019360784Sdim auto VisitorNotes = VisitorsDiagnostics->find(Construct.getCurrentNode()); 2020360784Sdim if (VisitorNotes == VisitorsDiagnostics->end()) 2021341825Sdim continue; 2022341825Sdim 2023341825Sdim // This is a workaround due to inability to put shared PathDiagnosticPiece 2024341825Sdim // into a FoldingSet. 2025341825Sdim std::set<llvm::FoldingSetNodeID> DeduplicationSet; 2026341825Sdim 2027341825Sdim // Add pieces from custom visitors. 2028360784Sdim for (const PathDiagnosticPieceRef &Note : VisitorNotes->second) { 2029341825Sdim llvm::FoldingSetNodeID ID; 2030341825Sdim Note->Profile(ID); 2031360784Sdim if (!DeduplicationSet.insert(ID).second) 2032341825Sdim continue; 2033341825Sdim 2034360784Sdim if (PDC->shouldAddPathEdges()) 2035360784Sdim addEdgeToPath(Construct.getActivePath(), PrevLoc, Note->getLocation()); 2036360784Sdim updateStackPiecesWithMessage(Note, Construct.CallStack); 2037360784Sdim Construct.getActivePath().push_front(Note); 2038341825Sdim } 2039341825Sdim } 2040341825Sdim 2041360784Sdim if (PDC->shouldAddPathEdges()) { 2042341825Sdim // Add an edge to the start of the function. 2043341825Sdim // We'll prune it out later, but it helps make diagnostics more uniform. 2044360784Sdim const StackFrameContext *CalleeLC = 2045360784Sdim Construct.getLocationContextForActivePath()->getStackFrame(); 2046341825Sdim const Decl *D = CalleeLC->getDecl(); 2047360784Sdim addEdgeToPath(Construct.getActivePath(), PrevLoc, 2048344779Sdim PathDiagnosticLocation::createBegin(D, SM)); 2049341825Sdim } 2050341825Sdim 2051341825Sdim 2052341825Sdim // Finally, prune the diagnostic path of uninteresting stuff. 2053360784Sdim if (!Construct.PD->path.empty()) { 2054344779Sdim if (R->shouldPrunePath() && Opts.ShouldPrunePaths) { 2055341825Sdim bool stillHasNotes = 2056360784Sdim removeUnneededCalls(Construct, Construct.getMutablePieces(), R); 2057341825Sdim assert(stillHasNotes); 2058341825Sdim (void)stillHasNotes; 2059341825Sdim } 2060341825Sdim 2061353358Sdim // Remove pop-up notes if needed. 2062353358Sdim if (!Opts.ShouldAddPopUpNotes) 2063360784Sdim removePopUpNotes(Construct.getMutablePieces()); 2064353358Sdim 2065341825Sdim // Redirect all call pieces to have valid locations. 2066360784Sdim adjustCallLocations(Construct.getMutablePieces()); 2067360784Sdim removePiecesWithInvalidLocations(Construct.getMutablePieces()); 2068341825Sdim 2069360784Sdim if (PDC->shouldAddPathEdges()) { 2070341825Sdim 2071341825Sdim // Reduce the number of edges from a very conservative set 2072341825Sdim // to an aesthetically pleasing subset that conveys the 2073341825Sdim // necessary information. 2074341825Sdim OptimizedCallsSet OCS; 2075360784Sdim while (optimizeEdges(Construct, Construct.getMutablePieces(), OCS)) { 2076360784Sdim } 2077341825Sdim 2078341825Sdim // Drop the very first function-entry edge. It's not really necessary 2079341825Sdim // for top-level functions. 2080360784Sdim dropFunctionEntryEdge(Construct, Construct.getMutablePieces()); 2081341825Sdim } 2082341825Sdim 2083341825Sdim // Remove messages that are basically the same, and edges that may not 2084341825Sdim // make sense. 2085341825Sdim // We have to do this after edge optimization in the Extensive mode. 2086360784Sdim removeRedundantMsgs(Construct.getMutablePieces()); 2087360784Sdim removeEdgesToDefaultInitializers(Construct.getMutablePieces()); 2088341825Sdim } 2089344779Sdim 2090360784Sdim if (Opts.ShouldDisplayMacroExpansions) 2091360784Sdim CompactMacroExpandedPieces(Construct.getMutablePieces(), SM); 2092344779Sdim 2093360784Sdim return std::move(Construct.PD); 2094341825Sdim} 2095341825Sdim 2096218887Sdim//===----------------------------------------------------------------------===// 2097218887Sdim// Methods for BugType and subclasses. 2098218887Sdim//===----------------------------------------------------------------------===// 2099219077Sdim 2100341825Sdimvoid BugType::anchor() {} 2101341825Sdim 2102234353Sdimvoid BuiltinBug::anchor() {} 2103234353Sdim 2104218887Sdim//===----------------------------------------------------------------------===// 2105218887Sdim// Methods for BugReport and subclasses. 2106218887Sdim//===----------------------------------------------------------------------===// 2107218887Sdim 2108360784Sdimvoid PathSensitiveBugReport::addVisitor( 2109360784Sdim std::unique_ptr<BugReporterVisitor> visitor) { 2110226633Sdim if (!visitor) 2111226633Sdim return; 2112226633Sdim 2113226633Sdim llvm::FoldingSetNodeID ID; 2114226633Sdim visitor->Profile(ID); 2115226633Sdim 2116341825Sdim void *InsertPos = nullptr; 2117341825Sdim if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) { 2118226633Sdim return; 2119341825Sdim } 2120226633Sdim 2121280031Sdim Callbacks.push_back(std::move(visitor)); 2122226633Sdim} 2123226633Sdim 2124360784Sdimvoid PathSensitiveBugReport::clearVisitors() { 2125341825Sdim Callbacks.clear(); 2126341825Sdim} 2127341825Sdim 2128360784Sdimconst Decl *PathSensitiveBugReport::getDeclWithIssue() const { 2129234353Sdim const ExplodedNode *N = getErrorNode(); 2130234353Sdim if (!N) 2131276479Sdim return nullptr; 2132276479Sdim 2133234353Sdim const LocationContext *LC = N->getLocationContext(); 2134341825Sdim return LC->getStackFrame()->getDecl(); 2135234353Sdim} 2136234353Sdim 2137360784Sdimvoid BasicBugReport::Profile(llvm::FoldingSetNodeID& hash) const { 2138360784Sdim hash.AddInteger(static_cast<int>(getKind())); 2139226633Sdim hash.AddPointer(&BT); 2140226633Sdim hash.AddString(Description); 2141360784Sdim assert(Location.isValid()); 2142360784Sdim Location.Profile(hash); 2143360784Sdim 2144360784Sdim for (SourceRange range : Ranges) { 2145360784Sdim if (!range.isValid()) 2146360784Sdim continue; 2147360784Sdim hash.AddInteger(range.getBegin().getRawEncoding()); 2148360784Sdim hash.AddInteger(range.getEnd().getRawEncoding()); 2149360784Sdim } 2150360784Sdim} 2151360784Sdim 2152360784Sdimvoid PathSensitiveBugReport::Profile(llvm::FoldingSetNodeID &hash) const { 2153360784Sdim hash.AddInteger(static_cast<int>(getKind())); 2154360784Sdim hash.AddPointer(&BT); 2155360784Sdim hash.AddString(Description); 2156249423Sdim PathDiagnosticLocation UL = getUniqueingLocation(); 2157249423Sdim if (UL.isValid()) { 2158249423Sdim UL.Profile(hash); 2159226633Sdim } else { 2160360784Sdim // TODO: The statement may be null if the report was emitted before any 2161360784Sdim // statements were executed. In particular, some checkers by design 2162360784Sdim // occasionally emit their reports in empty functions (that have no 2163360784Sdim // statements in their body). Do we profile correctly in this case? 2164360784Sdim hash.AddPointer(ErrorNode->getCurrentOrPreviousStmtForDiagnostics()); 2165226633Sdim } 2166226633Sdim 2167296417Sdim for (SourceRange range : Ranges) { 2168226633Sdim if (!range.isValid()) 2169226633Sdim continue; 2170226633Sdim hash.AddInteger(range.getBegin().getRawEncoding()); 2171226633Sdim hash.AddInteger(range.getEnd().getRawEncoding()); 2172226633Sdim } 2173226633Sdim} 2174226633Sdim 2175360784Sdimtemplate <class T> 2176360784Sdimstatic void insertToInterestingnessMap( 2177360784Sdim llvm::DenseMap<T, bugreporter::TrackingKind> &InterestingnessMap, T Val, 2178360784Sdim bugreporter::TrackingKind TKind) { 2179360784Sdim auto Result = InterestingnessMap.insert({Val, TKind}); 2180360784Sdim 2181360784Sdim if (Result.second) 2182360784Sdim return; 2183360784Sdim 2184360784Sdim // Even if this symbol/region was already marked as interesting as a 2185360784Sdim // condition, if we later mark it as interesting again but with 2186360784Sdim // thorough tracking, overwrite it. Entities marked with thorough 2187360784Sdim // interestiness are the most important (or most interesting, if you will), 2188360784Sdim // and we wouldn't like to downplay their importance. 2189360784Sdim 2190360784Sdim switch (TKind) { 2191360784Sdim case bugreporter::TrackingKind::Thorough: 2192360784Sdim Result.first->getSecond() = bugreporter::TrackingKind::Thorough; 2193360784Sdim return; 2194360784Sdim case bugreporter::TrackingKind::Condition: 2195360784Sdim return; 2196360784Sdim } 2197360784Sdim 2198360784Sdim llvm_unreachable( 2199360784Sdim "BugReport::markInteresting currently can only handle 2 different " 2200360784Sdim "tracking kinds! Please define what tracking kind should this entitiy" 2201360784Sdim "have, if it was already marked as interesting with a different kind!"); 2202360784Sdim} 2203360784Sdim 2204360784Sdimvoid PathSensitiveBugReport::markInteresting(SymbolRef sym, 2205360784Sdim bugreporter::TrackingKind TKind) { 2206234353Sdim if (!sym) 2207234353Sdim return; 2208234353Sdim 2209360784Sdim insertToInterestingnessMap(InterestingSymbols, sym, TKind); 2210234353Sdim 2211341825Sdim if (const auto *meta = dyn_cast<SymbolMetadata>(sym)) 2212360784Sdim markInteresting(meta->getRegion(), TKind); 2213234353Sdim} 2214234353Sdim 2215360784Sdimvoid PathSensitiveBugReport::markInteresting(const MemRegion *R, 2216360784Sdim bugreporter::TrackingKind TKind) { 2217234353Sdim if (!R) 2218234353Sdim return; 2219234353Sdim 2220234353Sdim R = R->getBaseRegion(); 2221360784Sdim insertToInterestingnessMap(InterestingRegions, R, TKind); 2222234353Sdim 2223341825Sdim if (const auto *SR = dyn_cast<SymbolicRegion>(R)) 2224360784Sdim markInteresting(SR->getSymbol(), TKind); 2225234353Sdim} 2226234353Sdim 2227360784Sdimvoid PathSensitiveBugReport::markInteresting(SVal V, 2228360784Sdim bugreporter::TrackingKind TKind) { 2229360784Sdim markInteresting(V.getAsRegion(), TKind); 2230360784Sdim markInteresting(V.getAsSymbol(), TKind); 2231234353Sdim} 2232234353Sdim 2233360784Sdimvoid PathSensitiveBugReport::markInteresting(const LocationContext *LC) { 2234243830Sdim if (!LC) 2235243830Sdim return; 2236243830Sdim InterestingLocationContexts.insert(LC); 2237243830Sdim} 2238243830Sdim 2239360784SdimOptional<bugreporter::TrackingKind> 2240360784SdimPathSensitiveBugReport::getInterestingnessKind(SVal V) const { 2241360784Sdim auto RKind = getInterestingnessKind(V.getAsRegion()); 2242360784Sdim auto SKind = getInterestingnessKind(V.getAsSymbol()); 2243360784Sdim if (!RKind) 2244360784Sdim return SKind; 2245360784Sdim if (!SKind) 2246360784Sdim return RKind; 2247360784Sdim 2248360784Sdim // If either is marked with throrough tracking, return that, we wouldn't like 2249360784Sdim // to downplay a note's importance by 'only' mentioning it as a condition. 2250360784Sdim switch(*RKind) { 2251360784Sdim case bugreporter::TrackingKind::Thorough: 2252360784Sdim return RKind; 2253360784Sdim case bugreporter::TrackingKind::Condition: 2254360784Sdim return SKind; 2255360784Sdim } 2256360784Sdim 2257360784Sdim llvm_unreachable( 2258360784Sdim "BugReport::getInterestingnessKind currently can only handle 2 different " 2259360784Sdim "tracking kinds! Please define what tracking kind should we return here " 2260360784Sdim "when the kind of getAsRegion() and getAsSymbol() is different!"); 2261360784Sdim return None; 2262234353Sdim} 2263234353Sdim 2264360784SdimOptional<bugreporter::TrackingKind> 2265360784SdimPathSensitiveBugReport::getInterestingnessKind(SymbolRef sym) const { 2266234353Sdim if (!sym) 2267360784Sdim return None; 2268234353Sdim // We don't currently consider metadata symbols to be interesting 2269234353Sdim // even if we know their region is interesting. Is that correct behavior? 2270360784Sdim auto It = InterestingSymbols.find(sym); 2271360784Sdim if (It == InterestingSymbols.end()) 2272360784Sdim return None; 2273360784Sdim return It->getSecond(); 2274234353Sdim} 2275234353Sdim 2276360784SdimOptional<bugreporter::TrackingKind> 2277360784SdimPathSensitiveBugReport::getInterestingnessKind(const MemRegion *R) const { 2278234353Sdim if (!R) 2279360784Sdim return None; 2280360784Sdim 2281234353Sdim R = R->getBaseRegion(); 2282360784Sdim auto It = InterestingRegions.find(R); 2283360784Sdim if (It != InterestingRegions.end()) 2284360784Sdim return It->getSecond(); 2285360784Sdim 2286341825Sdim if (const auto *SR = dyn_cast<SymbolicRegion>(R)) 2287360784Sdim return getInterestingnessKind(SR->getSymbol()); 2288360784Sdim return None; 2289234353Sdim} 2290234353Sdim 2291360784Sdimbool PathSensitiveBugReport::isInteresting(SVal V) const { 2292360784Sdim return getInterestingnessKind(V).hasValue(); 2293243830Sdim} 2294243830Sdim 2295360784Sdimbool PathSensitiveBugReport::isInteresting(SymbolRef sym) const { 2296360784Sdim return getInterestingnessKind(sym).hasValue(); 2297239462Sdim} 2298239462Sdim 2299360784Sdimbool PathSensitiveBugReport::isInteresting(const MemRegion *R) const { 2300360784Sdim return getInterestingnessKind(R).hasValue(); 2301239462Sdim} 2302239462Sdim 2303360784Sdimbool PathSensitiveBugReport::isInteresting(const LocationContext *LC) const { 2304360784Sdim if (!LC) 2305360784Sdim return false; 2306360784Sdim return InterestingLocationContexts.count(LC); 2307239462Sdim} 2308239462Sdim 2309360784Sdimconst Stmt *PathSensitiveBugReport::getStmt() const { 2310226633Sdim if (!ErrorNode) 2311276479Sdim return nullptr; 2312226633Sdim 2313218887Sdim ProgramPoint ProgP = ErrorNode->getLocation(); 2314276479Sdim const Stmt *S = nullptr; 2315218887Sdim 2316249423Sdim if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) { 2317218887Sdim CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit(); 2318218887Sdim if (BE->getBlock() == &Exit) 2319360784Sdim S = ErrorNode->getPreviousStmtForDiagnostics(); 2320218887Sdim } 2321218887Sdim if (!S) 2322360784Sdim S = ErrorNode->getStmtForDiagnostics(); 2323218887Sdim 2324218887Sdim return S; 2325218887Sdim} 2326218887Sdim 2327360784SdimArrayRef<SourceRange> 2328360784SdimPathSensitiveBugReport::getRanges() const { 2329288943Sdim // If no custom ranges, add the range of the statement corresponding to 2330288943Sdim // the error node. 2331360784Sdim if (Ranges.empty() && isa_and_nonnull<Expr>(getStmt())) 2332360784Sdim return ErrorNodeRange; 2333360784Sdim 2334360784Sdim return Ranges; 2335360784Sdim} 2336360784Sdim 2337360784SdimPathDiagnosticLocation 2338360784SdimPathSensitiveBugReport::getLocation() const { 2339360784Sdim assert(ErrorNode && "Cannot create a location with a null node."); 2340360784Sdim const Stmt *S = ErrorNode->getStmtForDiagnostics(); 2341360784Sdim ProgramPoint P = ErrorNode->getLocation(); 2342360784Sdim const LocationContext *LC = P.getLocationContext(); 2343360784Sdim SourceManager &SM = 2344360784Sdim ErrorNode->getState()->getStateManager().getContext().getSourceManager(); 2345360784Sdim 2346360784Sdim if (!S) { 2347360784Sdim // If this is an implicit call, return the implicit call point location. 2348360784Sdim if (Optional<PreImplicitCall> PIE = P.getAs<PreImplicitCall>()) 2349360784Sdim return PathDiagnosticLocation(PIE->getLocation(), SM); 2350360784Sdim if (auto FE = P.getAs<FunctionExitPoint>()) { 2351360784Sdim if (const ReturnStmt *RS = FE->getStmt()) 2352360784Sdim return PathDiagnosticLocation::createBegin(RS, SM, LC); 2353360784Sdim } 2354360784Sdim S = ErrorNode->getNextStmtForDiagnostics(); 2355288943Sdim } 2356218887Sdim 2357360784Sdim if (S) { 2358360784Sdim // For member expressions, return the location of the '.' or '->'. 2359360784Sdim if (const auto *ME = dyn_cast<MemberExpr>(S)) 2360360784Sdim return PathDiagnosticLocation::createMemberLoc(ME, SM); 2361218887Sdim 2362360784Sdim // For binary operators, return the location of the operator. 2363360784Sdim if (const auto *B = dyn_cast<BinaryOperator>(S)) 2364360784Sdim return PathDiagnosticLocation::createOperatorLoc(B, SM); 2365218887Sdim 2366360784Sdim if (P.getAs<PostStmtPurgeDeadSymbols>()) 2367360784Sdim return PathDiagnosticLocation::createEnd(S, SM, LC); 2368360784Sdim 2369360784Sdim if (S->getBeginLoc().isValid()) 2370360784Sdim return PathDiagnosticLocation(S, SM, LC); 2371360784Sdim 2372360784Sdim return PathDiagnosticLocation( 2373360784Sdim PathDiagnosticLocation::getValidSourceLocation(S, LC), SM); 2374226633Sdim } 2375218887Sdim 2376360784Sdim return PathDiagnosticLocation::createDeclEnd(ErrorNode->getLocationContext(), 2377360784Sdim SM); 2378218887Sdim} 2379218887Sdim 2380218887Sdim//===----------------------------------------------------------------------===// 2381218887Sdim// Methods for BugReporter and subclasses. 2382218887Sdim//===----------------------------------------------------------------------===// 2383218887Sdim 2384360784Sdimconst ExplodedGraph &PathSensitiveBugReporter::getGraph() const { 2385360784Sdim return Eng.getGraph(); 2386360784Sdim} 2387218887Sdim 2388360784SdimProgramStateManager &PathSensitiveBugReporter::getStateManager() const { 2389360784Sdim return Eng.getStateManager(); 2390360784Sdim} 2391341825Sdim 2392226633SdimBugReporter::~BugReporter() { 2393360784Sdim // Make sure reports are flushed. 2394360784Sdim assert(StrBugTypes.empty() && 2395360784Sdim "Destroying BugReporter before diagnostics are emitted!"); 2396218887Sdim 2397226633Sdim // Free the bug reports we are tracking. 2398341825Sdim for (const auto I : EQClassesVector) 2399341825Sdim delete I; 2400226633Sdim} 2401226633Sdim 2402218887Sdimvoid BugReporter::FlushReports() { 2403239462Sdim // We need to flush reports in deterministic order to ensure the order 2404239462Sdim // of the reports is consistent between runs. 2405341825Sdim for (const auto EQ : EQClassesVector) 2406341825Sdim FlushReport(*EQ); 2407218887Sdim 2408219077Sdim // BugReporter owns and deletes only BugTypes created implicitly through 2409219077Sdim // EmitBasicReport. 2410219077Sdim // FIXME: There are leaks from checkers that assume that the BugTypes they 2411219077Sdim // create will be destroyed by the BugReporter. 2412276479Sdim llvm::DeleteContainerSeconds(StrBugTypes); 2413218887Sdim} 2414218887Sdim 2415218887Sdim//===----------------------------------------------------------------------===// 2416218887Sdim// PathDiagnostics generation. 2417218887Sdim//===----------------------------------------------------------------------===// 2418218887Sdim 2419249423Sdimnamespace { 2420341825Sdim 2421360784Sdim/// A wrapper around an ExplodedGraph that contains a single path from the root 2422360784Sdim/// to the error node. 2423360784Sdimclass BugPathInfo { 2424249423Sdimpublic: 2425360784Sdim std::unique_ptr<ExplodedGraph> BugPath; 2426360784Sdim PathSensitiveBugReport *Report; 2427249423Sdim const ExplodedNode *ErrorNode; 2428249423Sdim}; 2429218887Sdim 2430360784Sdim/// A wrapper around an ExplodedGraph whose leafs are all error nodes. Can 2431360784Sdim/// conveniently retrieve bug paths from a single error node to the root. 2432360784Sdimclass BugPathGetter { 2433360784Sdim std::unique_ptr<ExplodedGraph> TrimmedGraph; 2434218887Sdim 2435341825Sdim using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>; 2436341825Sdim 2437360784Sdim /// Assign each node with its distance from the root. 2438249423Sdim PriorityMapTy PriorityMap; 2439218887Sdim 2440360784Sdim /// Since the getErrorNode() or BugReport refers to the original ExplodedGraph, 2441360784Sdim /// we need to pair it to the error node of the constructed trimmed graph. 2442360784Sdim using ReportNewNodePair = 2443360784Sdim std::pair<PathSensitiveBugReport *, const ExplodedNode *>; 2444360784Sdim SmallVector<ReportNewNodePair, 32> ReportNodes; 2445341825Sdim 2446360784Sdim BugPathInfo CurrentBugPath; 2447218887Sdim 2448249423Sdim /// A helper class for sorting ExplodedNodes by priority. 2449249423Sdim template <bool Descending> 2450249423Sdim class PriorityCompare { 2451249423Sdim const PriorityMapTy &PriorityMap; 2452249423Sdim 2453249423Sdim public: 2454249423Sdim PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {} 2455249423Sdim 2456249423Sdim bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const { 2457249423Sdim PriorityMapTy::const_iterator LI = PriorityMap.find(LHS); 2458249423Sdim PriorityMapTy::const_iterator RI = PriorityMap.find(RHS); 2459249423Sdim PriorityMapTy::const_iterator E = PriorityMap.end(); 2460249423Sdim 2461249423Sdim if (LI == E) 2462249423Sdim return Descending; 2463249423Sdim if (RI == E) 2464249423Sdim return !Descending; 2465249423Sdim 2466249423Sdim return Descending ? LI->second > RI->second 2467249423Sdim : LI->second < RI->second; 2468249423Sdim } 2469249423Sdim 2470360784Sdim bool operator()(const ReportNewNodePair &LHS, 2471360784Sdim const ReportNewNodePair &RHS) const { 2472360784Sdim return (*this)(LHS.second, RHS.second); 2473249423Sdim } 2474249423Sdim }; 2475249423Sdim 2476249423Sdimpublic: 2477360784Sdim BugPathGetter(const ExplodedGraph *OriginalGraph, 2478360784Sdim ArrayRef<PathSensitiveBugReport *> &bugReports); 2479249423Sdim 2480360784Sdim BugPathInfo *getNextBugPath(); 2481249423Sdim}; 2482249423Sdim 2483341825Sdim} // namespace 2484341825Sdim 2485360784SdimBugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph, 2486360784Sdim ArrayRef<PathSensitiveBugReport *> &bugReports) { 2487360784Sdim SmallVector<const ExplodedNode *, 32> Nodes; 2488360784Sdim for (const auto I : bugReports) { 2489360784Sdim assert(I->isValid() && 2490360784Sdim "We only allow BugReporterVisitors and BugReporter itself to " 2491360784Sdim "invalidate reports!"); 2492360784Sdim Nodes.emplace_back(I->getErrorNode()); 2493360784Sdim } 2494360784Sdim 2495249423Sdim // The trimmed graph is created in the body of the constructor to ensure 2496249423Sdim // that the DenseMaps have been initialized already. 2497249423Sdim InterExplodedGraphMap ForwardMap; 2498360784Sdim TrimmedGraph = OriginalGraph->trim(Nodes, &ForwardMap); 2499249423Sdim 2500218887Sdim // Find the (first) error node in the trimmed graph. We just need to consult 2501249423Sdim // the node map which maps from nodes in the original graph to nodes 2502218887Sdim // in the new graph. 2503249423Sdim llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes; 2504218887Sdim 2505360784Sdim for (PathSensitiveBugReport *Report : bugReports) { 2506360784Sdim const ExplodedNode *NewNode = ForwardMap.lookup(Report->getErrorNode()); 2507360784Sdim assert(NewNode && 2508360784Sdim "Failed to construct a trimmed graph that contains this error " 2509360784Sdim "node!"); 2510360784Sdim ReportNodes.emplace_back(Report, NewNode); 2511360784Sdim RemainingNodes.insert(NewNode); 2512218887Sdim } 2513218887Sdim 2514249423Sdim assert(!RemainingNodes.empty() && "No error node found in the trimmed graph"); 2515218887Sdim 2516249423Sdim // Perform a forward BFS to find all the shortest paths. 2517249423Sdim std::queue<const ExplodedNode *> WS; 2518218887Sdim 2519360784Sdim assert(TrimmedGraph->num_roots() == 1); 2520360784Sdim WS.push(*TrimmedGraph->roots_begin()); 2521249423Sdim unsigned Priority = 0; 2522218887Sdim 2523218887Sdim while (!WS.empty()) { 2524226633Sdim const ExplodedNode *Node = WS.front(); 2525218887Sdim WS.pop(); 2526218887Sdim 2527249423Sdim PriorityMapTy::iterator PriorityEntry; 2528249423Sdim bool IsNew; 2529360784Sdim std::tie(PriorityEntry, IsNew) = PriorityMap.insert({Node, Priority}); 2530249423Sdim ++Priority; 2531249423Sdim 2532249423Sdim if (!IsNew) { 2533249423Sdim assert(PriorityEntry->second <= Priority); 2534218887Sdim continue; 2535249423Sdim } 2536218887Sdim 2537249423Sdim if (RemainingNodes.erase(Node)) 2538249423Sdim if (RemainingNodes.empty()) 2539249423Sdim break; 2540218887Sdim 2541360784Sdim for (const ExplodedNode *Succ : Node->succs()) 2542360784Sdim WS.push(Succ); 2543218887Sdim } 2544218887Sdim 2545249423Sdim // Sort the error paths from longest to shortest. 2546344779Sdim llvm::sort(ReportNodes, PriorityCompare<true>(PriorityMap)); 2547249423Sdim} 2548218887Sdim 2549360784SdimBugPathInfo *BugPathGetter::getNextBugPath() { 2550249423Sdim if (ReportNodes.empty()) 2551360784Sdim return nullptr; 2552218887Sdim 2553249423Sdim const ExplodedNode *OrigN; 2554360784Sdim std::tie(CurrentBugPath.Report, OrigN) = ReportNodes.pop_back_val(); 2555249423Sdim assert(PriorityMap.find(OrigN) != PriorityMap.end() && 2556249423Sdim "error node not accessible from root"); 2557218887Sdim 2558360784Sdim // Create a new graph with a single path. This is the graph that will be 2559360784Sdim // returned to the caller. 2560360784Sdim auto GNew = std::make_unique<ExplodedGraph>(); 2561249423Sdim 2562249423Sdim // Now walk from the error node up the BFS path, always taking the 2563249423Sdim // predeccessor with the lowest number. 2564276479Sdim ExplodedNode *Succ = nullptr; 2565249423Sdim while (true) { 2566218887Sdim // Create the equivalent node in the new graph with the same state 2567218887Sdim // and location. 2568360784Sdim ExplodedNode *NewN = GNew->createUncachedNode( 2569360784Sdim OrigN->getLocation(), OrigN->getState(), 2570360784Sdim OrigN->getID(), OrigN->isSink()); 2571218887Sdim 2572218887Sdim // Link up the new node with the previous node. 2573249423Sdim if (Succ) 2574249423Sdim Succ->addPredecessor(NewN, *GNew); 2575249423Sdim else 2576360784Sdim CurrentBugPath.ErrorNode = NewN; 2577218887Sdim 2578249423Sdim Succ = NewN; 2579218887Sdim 2580218887Sdim // Are we at the final node? 2581249423Sdim if (OrigN->pred_empty()) { 2582249423Sdim GNew->addRoot(NewN); 2583218887Sdim break; 2584218887Sdim } 2585218887Sdim 2586249423Sdim // Find the next predeccessor node. We choose the node that is marked 2587249423Sdim // with the lowest BFS number. 2588249423Sdim OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(), 2589360784Sdim PriorityCompare<false>(PriorityMap)); 2590218887Sdim } 2591218887Sdim 2592360784Sdim CurrentBugPath.BugPath = std::move(GNew); 2593280031Sdim 2594360784Sdim return &CurrentBugPath; 2595218887Sdim} 2596218887Sdim 2597344779Sdim/// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic 2598344779Sdim/// object and collapses PathDiagosticPieces that are expanded by macros. 2599344779Sdimstatic void CompactMacroExpandedPieces(PathPieces &path, 2600344779Sdim const SourceManager& SM) { 2601360784Sdim using MacroStackTy = std::vector< 2602360784Sdim std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>; 2603218887Sdim 2604360784Sdim using PiecesTy = std::vector<PathDiagnosticPieceRef>; 2605218887Sdim 2606218887Sdim MacroStackTy MacroStack; 2607218887Sdim PiecesTy Pieces; 2608218887Sdim 2609234353Sdim for (PathPieces::const_iterator I = path.begin(), E = path.end(); 2610341825Sdim I != E; ++I) { 2611341825Sdim const auto &piece = *I; 2612296417Sdim 2613234353Sdim // Recursively compact calls. 2614314564Sdim if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) { 2615344779Sdim CompactMacroExpandedPieces(call->path, SM); 2616234353Sdim } 2617296417Sdim 2618218887Sdim // Get the location of the PathDiagnosticPiece. 2619234353Sdim const FullSourceLoc Loc = piece->getLocation().asLocation(); 2620218887Sdim 2621218887Sdim // Determine the instantiation location, which is the location we group 2622218887Sdim // related PathDiagnosticPieces. 2623218887Sdim SourceLocation InstantiationLoc = Loc.isMacroID() ? 2624226633Sdim SM.getExpansionLoc(Loc) : 2625218887Sdim SourceLocation(); 2626218887Sdim 2627218887Sdim if (Loc.isFileID()) { 2628218887Sdim MacroStack.clear(); 2629234353Sdim Pieces.push_back(piece); 2630218887Sdim continue; 2631218887Sdim } 2632218887Sdim 2633218887Sdim assert(Loc.isMacroID()); 2634218887Sdim 2635218887Sdim // Is the PathDiagnosticPiece within the same macro group? 2636218887Sdim if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) { 2637234353Sdim MacroStack.back().first->subPieces.push_back(piece); 2638218887Sdim continue; 2639218887Sdim } 2640218887Sdim 2641218887Sdim // We aren't in the same group. Are we descending into a new macro 2642218887Sdim // or are part of an old one? 2643314564Sdim std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup; 2644218887Sdim 2645218887Sdim SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ? 2646226633Sdim SM.getExpansionLoc(Loc) : 2647218887Sdim SourceLocation(); 2648218887Sdim 2649218887Sdim // Walk the entire macro stack. 2650218887Sdim while (!MacroStack.empty()) { 2651218887Sdim if (InstantiationLoc == MacroStack.back().second) { 2652218887Sdim MacroGroup = MacroStack.back().first; 2653218887Sdim break; 2654218887Sdim } 2655218887Sdim 2656218887Sdim if (ParentInstantiationLoc == MacroStack.back().second) { 2657218887Sdim MacroGroup = MacroStack.back().first; 2658218887Sdim break; 2659218887Sdim } 2660218887Sdim 2661218887Sdim MacroStack.pop_back(); 2662218887Sdim } 2663218887Sdim 2664218887Sdim if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) { 2665218887Sdim // Create a new macro group and add it to the stack. 2666314564Sdim auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>( 2667234353Sdim PathDiagnosticLocation::createSingleLocation(piece->getLocation())); 2668218887Sdim 2669218887Sdim if (MacroGroup) 2670234353Sdim MacroGroup->subPieces.push_back(NewGroup); 2671218887Sdim else { 2672218887Sdim assert(InstantiationLoc.isFileID()); 2673218887Sdim Pieces.push_back(NewGroup); 2674218887Sdim } 2675218887Sdim 2676218887Sdim MacroGroup = NewGroup; 2677218887Sdim MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc)); 2678218887Sdim } 2679218887Sdim 2680218887Sdim // Finally, add the PathDiagnosticPiece to the group. 2681234353Sdim MacroGroup->subPieces.push_back(piece); 2682218887Sdim } 2683218887Sdim 2684218887Sdim // Now take the pieces and construct a new PathDiagnostic. 2685234353Sdim path.clear(); 2686218887Sdim 2687288943Sdim path.insert(path.end(), Pieces.begin(), Pieces.end()); 2688218887Sdim} 2689218887Sdim 2690341825Sdim/// Generate notes from all visitors. 2691341825Sdim/// Notes associated with {@code ErrorNode} are generated using 2692341825Sdim/// {@code getEndPath}, and the rest are generated with {@code VisitNode}. 2693341825Sdimstatic std::unique_ptr<VisitorsDiagnosticsTy> 2694360784SdimgenerateVisitorsDiagnostics(PathSensitiveBugReport *R, 2695360784Sdim const ExplodedNode *ErrorNode, 2696341825Sdim BugReporterContext &BRC) { 2697360784Sdim std::unique_ptr<VisitorsDiagnosticsTy> Notes = 2698360784Sdim std::make_unique<VisitorsDiagnosticsTy>(); 2699360784Sdim PathSensitiveBugReport::VisitorList visitors; 2700218887Sdim 2701341825Sdim // Run visitors on all nodes starting from the node *before* the last one. 2702341825Sdim // The last node is reserved for notes generated with {@code getEndPath}. 2703341825Sdim const ExplodedNode *NextNode = ErrorNode->getFirstPred(); 2704341825Sdim while (NextNode) { 2705341825Sdim 2706360784Sdim // At each iteration, move all visitors from report to visitor list. This is 2707360784Sdim // important, because the Profile() functions of the visitors make sure that 2708360784Sdim // a visitor isn't added multiple times for the same node, but it's fine 2709360784Sdim // to add the a visitor with Profile() for different nodes (e.g. tracking 2710360784Sdim // a region at different points of the symbolic execution). 2711360784Sdim for (std::unique_ptr<BugReporterVisitor> &Visitor : R->visitors()) 2712360784Sdim visitors.push_back(std::move(Visitor)); 2713360784Sdim 2714341825Sdim R->clearVisitors(); 2715218887Sdim 2716341825Sdim const ExplodedNode *Pred = NextNode->getFirstPred(); 2717341825Sdim if (!Pred) { 2718360784Sdim PathDiagnosticPieceRef LastPiece; 2719341825Sdim for (auto &V : visitors) { 2720341825Sdim V->finalizeVisitor(BRC, ErrorNode, *R); 2721243830Sdim 2722341825Sdim if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) { 2723341825Sdim assert(!LastPiece && 2724341825Sdim "There can only be one final piece in a diagnostic."); 2725360784Sdim assert(Piece->getKind() == PathDiagnosticPiece::Kind::Event && 2726360784Sdim "The final piece must contain a message!"); 2727341825Sdim LastPiece = std::move(Piece); 2728341825Sdim (*Notes)[ErrorNode].push_back(LastPiece); 2729341825Sdim } 2730341825Sdim } 2731341825Sdim break; 2732341825Sdim } 2733218887Sdim 2734341825Sdim for (auto &V : visitors) { 2735344779Sdim auto P = V->VisitNode(NextNode, BRC, *R); 2736341825Sdim if (P) 2737341825Sdim (*Notes)[NextNode].push_back(std::move(P)); 2738251662Sdim } 2739341825Sdim 2740341825Sdim if (!R->isValid()) 2741341825Sdim break; 2742341825Sdim 2743341825Sdim NextNode = Pred; 2744251662Sdim } 2745251662Sdim 2746341825Sdim return Notes; 2747341825Sdim} 2748218887Sdim 2749360784SdimOptional<PathDiagnosticBuilder> PathDiagnosticBuilder::findValidReport( 2750360784Sdim ArrayRef<PathSensitiveBugReport *> &bugReports, 2751360784Sdim PathSensitiveBugReporter &Reporter) { 2752341825Sdim 2753360784Sdim BugPathGetter BugGraph(&Reporter.getGraph(), bugReports); 2754360784Sdim 2755360784Sdim while (BugPathInfo *BugPath = BugGraph.getNextBugPath()) { 2756249423Sdim // Find the BugReport with the original location. 2757360784Sdim PathSensitiveBugReport *R = BugPath->Report; 2758249423Sdim assert(R && "No original report found for sliced graph."); 2759249423Sdim assert(R->isValid() && "Report selected by trimmed graph marked invalid."); 2760360784Sdim const ExplodedNode *ErrorNode = BugPath->ErrorNode; 2761218887Sdim 2762341825Sdim // Register refutation visitors first, if they mark the bug invalid no 2763341825Sdim // further analysis is required 2764360784Sdim R->addVisitor(std::make_unique<LikelyFalsePositiveSuppressionBRVisitor>()); 2765218887Sdim 2766249423Sdim // Register additional node visitors. 2767360784Sdim R->addVisitor(std::make_unique<NilReceiverBRVisitor>()); 2768360784Sdim R->addVisitor(std::make_unique<ConditionBRVisitor>()); 2769360784Sdim R->addVisitor(std::make_unique<TagVisitor>()); 2770226633Sdim 2771360784Sdim BugReporterContext BRC(Reporter); 2772234353Sdim 2773341825Sdim // Run all visitors on a given graph, once. 2774341825Sdim std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes = 2775341825Sdim generateVisitorsDiagnostics(R, ErrorNode, BRC); 2776234353Sdim 2777341825Sdim if (R->isValid()) { 2778360784Sdim if (Reporter.getAnalyzerOptions().ShouldCrosscheckWithZ3) { 2779341825Sdim // If crosscheck is enabled, remove all visitors, add the refutation 2780341825Sdim // visitor and check again 2781341825Sdim R->clearVisitors(); 2782360784Sdim R->addVisitor(std::make_unique<FalsePositiveRefutationBRVisitor>()); 2783234353Sdim 2784341825Sdim // We don't overrite the notes inserted by other visitors because the 2785341825Sdim // refutation manager does not add any new note to the path 2786360784Sdim generateVisitorsDiagnostics(R, BugPath->ErrorNode, BRC); 2787234353Sdim } 2788249423Sdim 2789341825Sdim // Check if the bug is still valid 2790341825Sdim if (R->isValid()) 2791360784Sdim return PathDiagnosticBuilder( 2792360784Sdim std::move(BRC), std::move(BugPath->BugPath), BugPath->Report, 2793360784Sdim BugPath->ErrorNode, std::move(visitorNotes)); 2794341825Sdim } 2795341825Sdim } 2796218887Sdim 2797360784Sdim return {}; 2798341825Sdim} 2799251662Sdim 2800341825Sdimstd::unique_ptr<DiagnosticForConsumerMapTy> 2801360784SdimPathSensitiveBugReporter::generatePathDiagnostics( 2802341825Sdim ArrayRef<PathDiagnosticConsumer *> consumers, 2803360784Sdim ArrayRef<PathSensitiveBugReport *> &bugReports) { 2804341825Sdim assert(!bugReports.empty()); 2805234353Sdim 2806360784Sdim auto Out = std::make_unique<DiagnosticForConsumerMapTy>(); 2807234353Sdim 2808360784Sdim Optional<PathDiagnosticBuilder> PDB = 2809360784Sdim PathDiagnosticBuilder::findValidReport(bugReports, *this); 2810234353Sdim 2811360784Sdim if (PDB) { 2812341825Sdim for (PathDiagnosticConsumer *PC : consumers) { 2813360784Sdim if (std::unique_ptr<PathDiagnostic> PD = PDB->generate(PC)) { 2814360784Sdim (*Out)[PC] = std::move(PD); 2815360784Sdim } 2816243830Sdim } 2817239462Sdim } 2818243830Sdim 2819341825Sdim return Out; 2820218887Sdim} 2821218887Sdim 2822288943Sdimvoid BugReporter::emitReport(std::unique_ptr<BugReport> R) { 2823360784Sdim bool ValidSourceLoc = R->getLocation().isValid(); 2824261991Sdim assert(ValidSourceLoc); 2825261991Sdim // If we mess up in a release build, we'd still prefer to just drop the bug 2826261991Sdim // instead of trying to go on. 2827261991Sdim if (!ValidSourceLoc) 2828261991Sdim return; 2829261991Sdim 2830218887Sdim // Compute the bug report's hash to determine its equivalence class. 2831218887Sdim llvm::FoldingSetNodeID ID; 2832218887Sdim R->Profile(ID); 2833218887Sdim 2834218887Sdim // Lookup the equivance class. If there isn't one, create it. 2835218887Sdim void *InsertPos; 2836219077Sdim BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos); 2837218887Sdim 2838218887Sdim if (!EQ) { 2839288943Sdim EQ = new BugReportEquivClass(std::move(R)); 2840219077Sdim EQClasses.InsertNode(EQ, InsertPos); 2841226633Sdim EQClassesVector.push_back(EQ); 2842280031Sdim } else 2843288943Sdim EQ->AddReport(std::move(R)); 2844218887Sdim} 2845218887Sdim 2846360784Sdimvoid PathSensitiveBugReporter::emitReport(std::unique_ptr<BugReport> R) { 2847360784Sdim if (auto PR = dyn_cast<PathSensitiveBugReport>(R.get())) 2848360784Sdim if (const ExplodedNode *E = PR->getErrorNode()) { 2849360784Sdim // An error node must either be a sink or have a tag, otherwise 2850360784Sdim // it could get reclaimed before the path diagnostic is created. 2851360784Sdim assert((E->isSink() || E->getLocation().getTag()) && 2852360784Sdim "Error node must either be a sink or have a tag"); 2853360784Sdim 2854360784Sdim const AnalysisDeclContext *DeclCtx = 2855360784Sdim E->getLocationContext()->getAnalysisDeclContext(); 2856360784Sdim // The source of autosynthesized body can be handcrafted AST or a model 2857360784Sdim // file. The locations from handcrafted ASTs have no valid source 2858360784Sdim // locations and have to be discarded. Locations from model files should 2859360784Sdim // be preserved for processing and reporting. 2860360784Sdim if (DeclCtx->isBodyAutosynthesized() && 2861360784Sdim !DeclCtx->isBodyAutosynthesizedFromModelFile()) 2862360784Sdim return; 2863360784Sdim } 2864360784Sdim 2865360784Sdim BugReporter::emitReport(std::move(R)); 2866360784Sdim} 2867360784Sdim 2868218887Sdim//===----------------------------------------------------------------------===// 2869218887Sdim// Emitting reports in equivalence classes. 2870218887Sdim//===----------------------------------------------------------------------===// 2871218887Sdim 2872218887Sdimnamespace { 2873341825Sdim 2874218887Sdimstruct FRIEC_WLItem { 2875218887Sdim const ExplodedNode *N; 2876218887Sdim ExplodedNode::const_succ_iterator I, E; 2877296417Sdim 2878218887Sdim FRIEC_WLItem(const ExplodedNode *n) 2879341825Sdim : N(n), I(N->succ_begin()), E(N->succ_end()) {} 2880296417Sdim}; 2881218887Sdim 2882341825Sdim} // namespace 2883341825Sdim 2884360784SdimBugReport *PathSensitiveBugReporter::findReportInEquivalenceClass( 2885360784Sdim BugReportEquivClass &EQ, SmallVectorImpl<BugReport *> &bugReports) { 2886218887Sdim // If we don't need to suppress any of the nodes because they are 2887218887Sdim // post-dominated by a sink, simply add all the nodes in the equivalence class 2888218887Sdim // to 'Nodes'. Any of the reports will serve as a "representative" report. 2889360784Sdim assert(EQ.getReports().size() > 0); 2890360784Sdim const BugType& BT = EQ.getReports()[0]->getBugType(); 2891218887Sdim if (!BT.isSuppressOnSink()) { 2892360784Sdim BugReport *R = EQ.getReports()[0].get(); 2893360784Sdim for (auto &J : EQ.getReports()) { 2894360784Sdim if (auto *PR = dyn_cast<PathSensitiveBugReport>(J.get())) { 2895360784Sdim R = PR; 2896360784Sdim bugReports.push_back(PR); 2897218887Sdim } 2898218887Sdim } 2899218887Sdim return R; 2900218887Sdim } 2901218887Sdim 2902218887Sdim // For bug reports that should be suppressed when all paths are post-dominated 2903218887Sdim // by a sink node, iterate through the reports in the equivalence class 2904218887Sdim // until we find one that isn't post-dominated (if one exists). We use a 2905218887Sdim // DFS traversal of the ExplodedGraph to find a non-sink node. We could write 2906218887Sdim // this as a recursive function, but we don't want to risk blowing out the 2907218887Sdim // stack for very long paths. 2908276479Sdim BugReport *exampleReport = nullptr; 2909218887Sdim 2910360784Sdim for (const auto &I: EQ.getReports()) { 2911360784Sdim auto *R = dyn_cast<PathSensitiveBugReport>(I.get()); 2912360784Sdim if (!R) 2913360784Sdim continue; 2914218887Sdim 2915360784Sdim const ExplodedNode *errorNode = R->getErrorNode(); 2916218887Sdim if (errorNode->isSink()) { 2917226633Sdim llvm_unreachable( 2918218887Sdim "BugType::isSuppressSink() should not be 'true' for sink end nodes"); 2919218887Sdim } 2920218887Sdim // No successors? By definition this nodes isn't post-dominated by a sink. 2921218887Sdim if (errorNode->succ_empty()) { 2922360784Sdim bugReports.push_back(R); 2923218887Sdim if (!exampleReport) 2924360784Sdim exampleReport = R; 2925218887Sdim continue; 2926218887Sdim } 2927218887Sdim 2928314564Sdim // See if we are in a no-return CFG block. If so, treat this similarly 2929314564Sdim // to being post-dominated by a sink. This works better when the analysis 2930327952Sdim // is incomplete and we have never reached the no-return function call(s) 2931327952Sdim // that we'd inevitably bump into on this path. 2932360784Sdim if (const CFGBlock *ErrorB = errorNode->getCFGBlock()) 2933360784Sdim if (ErrorB->isInevitablySinking()) 2934360784Sdim continue; 2935314564Sdim 2936218887Sdim // At this point we know that 'N' is not a sink and it has at least one 2937296417Sdim // successor. Use a DFS worklist to find a non-sink end-of-path node. 2938341825Sdim using WLItem = FRIEC_WLItem; 2939341825Sdim using DFSWorkList = SmallVector<WLItem, 10>; 2940341825Sdim 2941218887Sdim llvm::DenseMap<const ExplodedNode *, unsigned> Visited; 2942296417Sdim 2943218887Sdim DFSWorkList WL; 2944218887Sdim WL.push_back(errorNode); 2945218887Sdim Visited[errorNode] = 1; 2946296417Sdim 2947218887Sdim while (!WL.empty()) { 2948218887Sdim WLItem &WI = WL.back(); 2949218887Sdim assert(!WI.N->succ_empty()); 2950296417Sdim 2951218887Sdim for (; WI.I != WI.E; ++WI.I) { 2952296417Sdim const ExplodedNode *Succ = *WI.I; 2953218887Sdim // End-of-path node? 2954218887Sdim if (Succ->succ_empty()) { 2955218887Sdim // If we found an end-of-path node that is not a sink. 2956218887Sdim if (!Succ->isSink()) { 2957360784Sdim bugReports.push_back(R); 2958218887Sdim if (!exampleReport) 2959360784Sdim exampleReport = R; 2960218887Sdim WL.clear(); 2961218887Sdim break; 2962218887Sdim } 2963218887Sdim // Found a sink? Continue on to the next successor. 2964218887Sdim continue; 2965218887Sdim } 2966218887Sdim // Mark the successor as visited. If it hasn't been explored, 2967218887Sdim // enqueue it to the DFS worklist. 2968218887Sdim unsigned &mark = Visited[Succ]; 2969218887Sdim if (!mark) { 2970218887Sdim mark = 1; 2971218887Sdim WL.push_back(Succ); 2972218887Sdim break; 2973218887Sdim } 2974218887Sdim } 2975218887Sdim 2976218887Sdim // The worklist may have been cleared at this point. First 2977218887Sdim // check if it is empty before checking the last item. 2978218887Sdim if (!WL.empty() && &WL.back() == &WI) 2979218887Sdim WL.pop_back(); 2980218887Sdim } 2981218887Sdim } 2982218887Sdim 2983218887Sdim // ExampleReport will be NULL if all the nodes in the equivalence class 2984218887Sdim // were post-dominated by sinks. 2985218887Sdim return exampleReport; 2986218887Sdim} 2987218887Sdim 2988239462Sdimvoid BugReporter::FlushReport(BugReportEquivClass& EQ) { 2989239462Sdim SmallVector<BugReport*, 10> bugReports; 2990360784Sdim BugReport *report = findReportInEquivalenceClass(EQ, bugReports); 2991341825Sdim if (!report) 2992341825Sdim return; 2993341825Sdim 2994341825Sdim ArrayRef<PathDiagnosticConsumer*> Consumers = getPathDiagnosticConsumers(); 2995341825Sdim std::unique_ptr<DiagnosticForConsumerMapTy> Diagnostics = 2996341825Sdim generateDiagnosticForConsumerMap(report, Consumers, bugReports); 2997341825Sdim 2998341825Sdim for (auto &P : *Diagnostics) { 2999341825Sdim PathDiagnosticConsumer *Consumer = P.first; 3000341825Sdim std::unique_ptr<PathDiagnostic> &PD = P.second; 3001341825Sdim 3002341825Sdim // If the path is empty, generate a single step path with the location 3003341825Sdim // of the issue. 3004341825Sdim if (PD->path.empty()) { 3005360784Sdim PathDiagnosticLocation L = report->getLocation(); 3006360784Sdim auto piece = std::make_unique<PathDiagnosticEventPiece>( 3007341825Sdim L, report->getDescription()); 3008341825Sdim for (SourceRange Range : report->getRanges()) 3009341825Sdim piece->addRange(Range); 3010341825Sdim PD->setEndOfPath(std::move(piece)); 3011239462Sdim } 3012341825Sdim 3013341825Sdim PathPieces &Pieces = PD->getMutablePieces(); 3014344779Sdim if (getAnalyzerOptions().ShouldDisplayNotesAsEvents) { 3015341825Sdim // For path diagnostic consumers that don't support extra notes, 3016341825Sdim // we may optionally convert those to path notes. 3017341825Sdim for (auto I = report->getNotes().rbegin(), 3018341825Sdim E = report->getNotes().rend(); I != E; ++I) { 3019341825Sdim PathDiagnosticNotePiece *Piece = I->get(); 3020341825Sdim auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>( 3021341825Sdim Piece->getLocation(), Piece->getString()); 3022341825Sdim for (const auto &R: Piece->getRanges()) 3023341825Sdim ConvertedPiece->addRange(R); 3024341825Sdim 3025341825Sdim Pieces.push_front(std::move(ConvertedPiece)); 3026341825Sdim } 3027341825Sdim } else { 3028341825Sdim for (auto I = report->getNotes().rbegin(), 3029341825Sdim E = report->getNotes().rend(); I != E; ++I) 3030341825Sdim Pieces.push_front(*I); 3031341825Sdim } 3032341825Sdim 3033360784Sdim for (const auto &I : report->getFixits()) 3034360784Sdim Pieces.back()->addFixit(I); 3035341825Sdim 3036344779Sdim updateExecutedLinesWithDiagnosticPieces(*PD); 3037341825Sdim Consumer->HandlePathDiagnostic(std::move(PD)); 3038218887Sdim } 3039218887Sdim} 3040218887Sdim 3041341825Sdim/// Insert all lines participating in the function signature \p Signature 3042341825Sdim/// into \p ExecutedLines. 3043341825Sdimstatic void populateExecutedLinesWithFunctionSignature( 3044360784Sdim const Decl *Signature, const SourceManager &SM, 3045344779Sdim FilesToLineNumsMap &ExecutedLines) { 3046341825Sdim SourceRange SignatureSourceRange; 3047341825Sdim const Stmt* Body = Signature->getBody(); 3048341825Sdim if (const auto FD = dyn_cast<FunctionDecl>(Signature)) { 3049341825Sdim SignatureSourceRange = FD->getSourceRange(); 3050341825Sdim } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) { 3051341825Sdim SignatureSourceRange = OD->getSourceRange(); 3052341825Sdim } else { 3053341825Sdim return; 3054341825Sdim } 3055341825Sdim SourceLocation Start = SignatureSourceRange.getBegin(); 3056341825Sdim SourceLocation End = Body ? Body->getSourceRange().getBegin() 3057341825Sdim : SignatureSourceRange.getEnd(); 3058344779Sdim if (!Start.isValid() || !End.isValid()) 3059344779Sdim return; 3060341825Sdim unsigned StartLine = SM.getExpansionLineNumber(Start); 3061341825Sdim unsigned EndLine = SM.getExpansionLineNumber(End); 3062218887Sdim 3063341825Sdim FileID FID = SM.getFileID(SM.getExpansionLoc(Start)); 3064341825Sdim for (unsigned Line = StartLine; Line <= EndLine; Line++) 3065344779Sdim ExecutedLines[FID].insert(Line); 3066341825Sdim} 3067218887Sdim 3068341825Sdimstatic void populateExecutedLinesWithStmt( 3069360784Sdim const Stmt *S, const SourceManager &SM, 3070344779Sdim FilesToLineNumsMap &ExecutedLines) { 3071341825Sdim SourceLocation Loc = S->getSourceRange().getBegin(); 3072344779Sdim if (!Loc.isValid()) 3073344779Sdim return; 3074341825Sdim SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc); 3075341825Sdim FileID FID = SM.getFileID(ExpansionLoc); 3076341825Sdim unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc); 3077344779Sdim ExecutedLines[FID].insert(LineNo); 3078341825Sdim} 3079218887Sdim 3080341825Sdim/// \return all executed lines including function signatures on the path 3081341825Sdim/// starting from \p N. 3082341825Sdimstatic std::unique_ptr<FilesToLineNumsMap> 3083360784SdimfindExecutedLines(const SourceManager &SM, const ExplodedNode *N) { 3084360784Sdim auto ExecutedLines = std::make_unique<FilesToLineNumsMap>(); 3085249423Sdim 3086341825Sdim while (N) { 3087341825Sdim if (N->getFirstPred() == nullptr) { 3088341825Sdim // First node: show signature of the entrance point. 3089341825Sdim const Decl *D = N->getLocationContext()->getDecl(); 3090344779Sdim populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines); 3091341825Sdim } else if (auto CE = N->getLocationAs<CallEnter>()) { 3092341825Sdim // Inlined function: show signature. 3093341825Sdim const Decl* D = CE->getCalleeContext()->getDecl(); 3094344779Sdim populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines); 3095360784Sdim } else if (const Stmt *S = N->getStmtForDiagnostics()) { 3096344779Sdim populateExecutedLinesWithStmt(S, SM, *ExecutedLines); 3097314564Sdim 3098341825Sdim // Show extra context for some parent kinds. 3099341825Sdim const Stmt *P = N->getParentMap().getParent(S); 3100218887Sdim 3101341825Sdim // The path exploration can die before the node with the associated 3102341825Sdim // return statement is generated, but we do want to show the whole 3103341825Sdim // return. 3104341825Sdim if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) { 3105344779Sdim populateExecutedLinesWithStmt(RS, SM, *ExecutedLines); 3106341825Sdim P = N->getParentMap().getParent(RS); 3107341825Sdim } 3108249423Sdim 3109341825Sdim if (P && (isa<SwitchCase>(P) || isa<LabelStmt>(P))) 3110344779Sdim populateExecutedLinesWithStmt(P, SM, *ExecutedLines); 3111341825Sdim } 3112261991Sdim 3113341825Sdim N = N->getFirstPred(); 3114218887Sdim } 3115341825Sdim return ExecutedLines; 3116341825Sdim} 3117218887Sdim 3118341825Sdimstd::unique_ptr<DiagnosticForConsumerMapTy> 3119341825SdimBugReporter::generateDiagnosticForConsumerMap( 3120360784Sdim BugReport *exampleReport, ArrayRef<PathDiagnosticConsumer *> consumers, 3121341825Sdim ArrayRef<BugReport *> bugReports) { 3122360784Sdim auto *basicReport = cast<BasicBugReport>(exampleReport); 3123360784Sdim auto Out = std::make_unique<DiagnosticForConsumerMapTy>(); 3124360784Sdim for (auto *Consumer : consumers) 3125360784Sdim (*Out)[Consumer] = generateDiagnosticForBasicReport(basicReport); 3126360784Sdim return Out; 3127360784Sdim} 3128314564Sdim 3129360784Sdimstatic PathDiagnosticCallPiece * 3130360784SdimgetFirstStackedCallToHeaderFile(PathDiagnosticCallPiece *CP, 3131360784Sdim const SourceManager &SMgr) { 3132360784Sdim SourceLocation CallLoc = CP->callEnter.asLocation(); 3133360784Sdim 3134360784Sdim // If the call is within a macro, don't do anything (for now). 3135360784Sdim if (CallLoc.isMacroID()) 3136360784Sdim return nullptr; 3137360784Sdim 3138360784Sdim assert(AnalysisManager::isInCodeFile(CallLoc, SMgr) && 3139360784Sdim "The call piece should not be in a header file."); 3140360784Sdim 3141360784Sdim // Check if CP represents a path through a function outside of the main file. 3142360784Sdim if (!AnalysisManager::isInCodeFile(CP->callEnterWithin.asLocation(), SMgr)) 3143360784Sdim return CP; 3144360784Sdim 3145360784Sdim const PathPieces &Path = CP->path; 3146360784Sdim if (Path.empty()) 3147360784Sdim return nullptr; 3148360784Sdim 3149360784Sdim // Check if the last piece in the callee path is a call to a function outside 3150360784Sdim // of the main file. 3151360784Sdim if (auto *CPInner = dyn_cast<PathDiagnosticCallPiece>(Path.back().get())) 3152360784Sdim return getFirstStackedCallToHeaderFile(CPInner, SMgr); 3153360784Sdim 3154360784Sdim // Otherwise, the last piece is in the main file. 3155360784Sdim return nullptr; 3156360784Sdim} 3157360784Sdim 3158360784Sdimstatic void resetDiagnosticLocationToMainFile(PathDiagnostic &PD) { 3159360784Sdim if (PD.path.empty()) 3160360784Sdim return; 3161360784Sdim 3162360784Sdim PathDiagnosticPiece *LastP = PD.path.back().get(); 3163360784Sdim assert(LastP); 3164360784Sdim const SourceManager &SMgr = LastP->getLocation().getManager(); 3165360784Sdim 3166360784Sdim // We only need to check if the report ends inside headers, if the last piece 3167360784Sdim // is a call piece. 3168360784Sdim if (auto *CP = dyn_cast<PathDiagnosticCallPiece>(LastP)) { 3169360784Sdim CP = getFirstStackedCallToHeaderFile(CP, SMgr); 3170360784Sdim if (CP) { 3171360784Sdim // Mark the piece. 3172360784Sdim CP->setAsLastInMainSourceFile(); 3173360784Sdim 3174360784Sdim // Update the path diagnostic message. 3175360784Sdim const auto *ND = dyn_cast<NamedDecl>(CP->getCallee()); 3176360784Sdim if (ND) { 3177360784Sdim SmallString<200> buf; 3178360784Sdim llvm::raw_svector_ostream os(buf); 3179360784Sdim os << " (within a call to '" << ND->getDeclName() << "')"; 3180360784Sdim PD.appendToDesc(os.str()); 3181360784Sdim } 3182360784Sdim 3183360784Sdim // Reset the report containing declaration and location. 3184360784Sdim PD.setDeclWithIssue(CP->getCaller()); 3185360784Sdim PD.setLocation(CP->getLocation()); 3186360784Sdim 3187360784Sdim return; 3188360784Sdim } 3189314564Sdim } 3190360784Sdim} 3191314564Sdim 3192360784Sdim 3193360784Sdim 3194360784Sdimstd::unique_ptr<DiagnosticForConsumerMapTy> 3195360784SdimPathSensitiveBugReporter::generateDiagnosticForConsumerMap( 3196360784Sdim BugReport *exampleReport, ArrayRef<PathDiagnosticConsumer *> consumers, 3197360784Sdim ArrayRef<BugReport *> bugReports) { 3198360784Sdim std::vector<BasicBugReport *> BasicBugReports; 3199360784Sdim std::vector<PathSensitiveBugReport *> PathSensitiveBugReports; 3200360784Sdim if (isa<BasicBugReport>(exampleReport)) 3201360784Sdim return BugReporter::generateDiagnosticForConsumerMap(exampleReport, 3202360784Sdim consumers, bugReports); 3203360784Sdim 3204341825Sdim // Generate the full path sensitive diagnostic, using the generation scheme 3205341825Sdim // specified by the PathDiagnosticConsumer. Note that we have to generate 3206341825Sdim // path diagnostics even for consumers which do not support paths, because 3207341825Sdim // the BugReporterVisitors may mark this bug as a false positive. 3208341825Sdim assert(!bugReports.empty()); 3209341825Sdim MaxBugClassSize.updateMax(bugReports.size()); 3210239462Sdim 3211360784Sdim // Avoid copying the whole array because there may be a lot of reports. 3212360784Sdim ArrayRef<PathSensitiveBugReport *> convertedArrayOfReports( 3213360784Sdim reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.begin()), 3214360784Sdim reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.end())); 3215360784Sdim std::unique_ptr<DiagnosticForConsumerMapTy> Out = generatePathDiagnostics( 3216360784Sdim consumers, convertedArrayOfReports); 3217360784Sdim 3218341825Sdim if (Out->empty()) 3219341825Sdim return Out; 3220341825Sdim 3221341825Sdim MaxValidBugClassSize.updateMax(bugReports.size()); 3222341825Sdim 3223341825Sdim // Examine the report and see if the last piece is in a header. Reset the 3224341825Sdim // report location to the last piece in the main source file. 3225360784Sdim const AnalyzerOptions &Opts = getAnalyzerOptions(); 3226341825Sdim for (auto const &P : *Out) 3227344779Sdim if (Opts.ShouldReportIssuesInMainSourceFile && !Opts.AnalyzeAll) 3228360784Sdim resetDiagnosticLocationToMainFile(*P.second); 3229341825Sdim 3230341825Sdim return Out; 3231218887Sdim} 3232218887Sdim 3233234353Sdimvoid BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3234360784Sdim const CheckerBase *Checker, StringRef Name, 3235360784Sdim StringRef Category, StringRef Str, 3236360784Sdim PathDiagnosticLocation Loc, 3237360784Sdim ArrayRef<SourceRange> Ranges, 3238360784Sdim ArrayRef<FixItHint> Fixits) { 3239360784Sdim EmitBasicReport(DeclWithIssue, Checker->getCheckerName(), Name, Category, Str, 3240360784Sdim Loc, Ranges, Fixits); 3241276479Sdim} 3242341825Sdim 3243276479Sdimvoid BugReporter::EmitBasicReport(const Decl *DeclWithIssue, 3244360784Sdim CheckerNameRef CheckName, 3245276479Sdim StringRef name, StringRef category, 3246226633Sdim StringRef str, PathDiagnosticLocation Loc, 3247360784Sdim ArrayRef<SourceRange> Ranges, 3248360784Sdim ArrayRef<FixItHint> Fixits) { 3249219077Sdim // 'BT' is owned by BugReporter. 3250276479Sdim BugType *BT = getBugTypeForName(CheckName, name, category); 3251360784Sdim auto R = std::make_unique<BasicBugReport>(*BT, str, Loc); 3252234353Sdim R->setDeclWithIssue(DeclWithIssue); 3253360784Sdim for (const auto &SR : Ranges) 3254360784Sdim R->addRange(SR); 3255360784Sdim for (const auto &FH : Fixits) 3256360784Sdim R->addFixItHint(FH); 3257288943Sdim emitReport(std::move(R)); 3258218887Sdim} 3259219077Sdim 3260360784SdimBugType *BugReporter::getBugTypeForName(CheckerNameRef CheckName, 3261360784Sdim StringRef name, StringRef category) { 3262234353Sdim SmallString<136> fullDesc; 3263276479Sdim llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name 3264276479Sdim << ":" << category; 3265280031Sdim BugType *&BT = StrBugTypes[fullDesc]; 3266280031Sdim if (!BT) 3267276479Sdim BT = new BugType(CheckName, name, category); 3268219077Sdim return BT; 3269219077Sdim} 3270