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