Coverage Report

Created: 2020-09-15 12:33

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