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