Coverage Report

Created: 2020-11-24 06:42

/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
244k
  const LocationContext *getCurrLocationContext() const {
144
244k
    assert(CurrentNode && "Already reached the root!");
145
244k
    return CurrentNode->getLocationContext();
146
244k
  }
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
434k
  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
215k
  bool ascendToPrevNode() {
160
215k
    CurrentNode = CurrentNode->getFirstPred();
161
215k
    return static_cast<bool>(CurrentNode);
162
215k
  }
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.21k
  const LocationContext *getLocationContextFor(const PathPieces *Path) const {
180
9.21k
    assert(LCM.count(Path) &&
181
9.21k
           "Failed to find the context associated with these pieces!");
182
9.21k
    return LCM.find(Path)->getSecond();
183
9.21k
  }
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.4k
  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.49k
  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
287
20
  ProgramPoint P = N->getLocation();
288
20
  CallExitEnd CExit = P.castAs<CallExitEnd>();
289
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
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
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
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
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
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
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
354
1.12k
  if (X->getLocation() != Y->getLocation())
355
992
    return nullptr;
356
357
137
  if (X->getTag() == tagPreferred && 
Y->getTag() == tagLesser113
)
358
93
    return ConditionBRVisitor::isPieceMessageGeneric(X) ? 
Y5
:
X88
;
359
360
44
  if (Y->getTag() == tagPreferred && 
X->getTag() == tagLesser17
)
361
15
    return ConditionBRVisitor::isPieceMessageGeneric(Y) ? 
X2
:
Y13
;
362
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.48k
  
for (unsigned i = 0; 1.83k
i < N;
++i7.64k
) {
380
7.64k
    auto piece = std::move(path.front());
381
7.64k
    path.pop_front();
382
383
7.64k
    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.14k
      case PathDiagnosticPiece::Event: {
391
4.14k
        if (i == N-1)
392
1.66k
          break;
393
394
2.48k
        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.48k
        break;
408
2.48k
      }
409
3.13k
      case PathDiagnosticPiece::ControlFlow:
410
3.13k
      case PathDiagnosticPiece::Note:
411
3.13k
      case PathDiagnosticPiece::PopUp:
412
3.13k
        break;
413
7.64k
    }
414
7.64k
    path.push_back(std::move(piece));
415
7.64k
  }
416
1.83k
}
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.86k
                                bool IsInteresting = false) {
425
8.86k
  bool containsSomethingInteresting = IsInteresting;
426
8.86k
  const unsigned N = pieces.size();
427
428
33.5k
  for (unsigned i = 0 ; i < N ; 
++i24.7k
) {
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.7k
    auto piece = std::move(pieces.front());
432
24.7k
    pieces.pop_front();
433
434
24.7k
    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.56k
          continue;
442
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.73k
      case PathDiagnosticPiece::Event: {
454
4.73k
        auto &event = cast<PathDiagnosticEventPiece>(*piece);
455
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.73k
        containsSomethingInteresting |= !event.isPrunable();
459
4.73k
        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
467
18.1k
    pieces.push_back(std::move(piece));
468
18.1k
  }
469
470
8.86k
  return containsSomethingInteresting;
471
8.86k
}
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.9k
  for (const auto &I : Pieces) {
496
17.9k
    auto *Call = dyn_cast<PathDiagnosticCallPiece>(I.get());
497
498
17.9k
    if (!Call)
499
17.4k
      continue;
500
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
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
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.17k
    if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
529
421
      removeEdgesToDefaultInitializers(C->path);
530
531
8.17k
    if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))
532
0
      removeEdgesToDefaultInitializers(M->subPieces);
533
534
8.17k
    if (auto *CF = dyn_cast<PathDiagnosticControlFlowPiece>(I->get())) {
535
3.02k
      const Stmt *Start = CF->getStartLocation().asStmt();
536
3.02k
      const Stmt *End = CF->getEndLocation().asStmt();
537
3.02k
      if (Start && 
isa<CXXDefaultInitExpr>(Start)2.08k
) {
538
0
        I = Pieces.erase(I);
539
0
        continue;
540
3.02k
      } 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.17k
    }
552
553
8.17k
    I++;
554
8.17k
  }
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.2k
  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
562
17.9k
    if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
563
421
      removePiecesWithInvalidLocations(C->path);
564
565
17.9k
    if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))
566
0
      removePiecesWithInvalidLocations(M->subPieces);
567
568
17.9k
    if (!(*I)->getLocation().isValid() ||
569
17.9k
        !(*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
796
    const PathDiagnosticConstruct &C) const {
579
796
  if (const Stmt *S = C.getCurrentNode()->getNextStmtForDiagnostics())
580
796
    return PathDiagnosticLocation(S, getSourceManager(),
581
796
                                  C.getCurrLocationContext());
582
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
593
73
  const PathDiagnosticLocation &Loc = ExecutionContinues(C);
594
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
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.55k
    return PM.getParentIgnoreParens(S);
619
620
8.22k
  const Stmt *Parent = PM.getParentIgnoreParens(S);
621
8.22k
  if (!Parent)
622
60
    return nullptr;
623
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
635
8.07k
  return nullptr;
636
8.07k
}
637
638
static PathDiagnosticLocation
639
getEnclosingStmtLocation(const Stmt *S, const LocationContext *LC,
640
8.67k
                         bool allowNestedContexts = false) {
641
8.67k
  if (!S)
642
324
    return {};
643
644
8.34k
  const SourceManager &SMgr = LC->getDecl()->getASTContext().getSourceManager();
645
646
12.7k
  while (const Stmt *Parent = getEnclosingParent(S, LC->getParentMap())) {
647
4.64k
    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.43k
    }
698
699
4.43k
    S = Parent;
700
4.43k
  }
701
702
8.13k
  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
703
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.90k
    PathDiagnosticPieceRef P, const CallWithEntryStack &CallStack) const {
723
2.90k
  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
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.90k
}
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
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
750
15
  if (const Stmt *S = Dst->getLabel()) {
751
15
    End = PathDiagnosticLocation(S, SM, C.getCurrLocationContext());
752
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
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
769
      // Determine if it is an enum.
770
13
      bool GetRawInt = true;
771
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
777
1
        if (D) {
778
1
          GetRawInt = false;
779
1
          os << *D;
780
1
        }
781
1
      }
782
783
13
      if (GetRawInt)
784
12
        os << LHS->EvaluateKnownConstInt(getASTContext());
785
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
813
81
  const SourceManager &SM = getSourceManager();
814
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
821
81
  if (B->getOpcode() == BO_LAnd) {
822
59
    os << "&&"
823
59
      << "' is ";
824
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
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.6k
    return;
866
867
890
  auto Start = PathDiagnosticLocation::createBegin(T, SM, LC);
868
890
  switch (T->getStmtClass()) {
869
29
  default:
870
29
    break;
871
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
879
15
  case Stmt::SwitchStmtClass: {
880
15
    C.getActivePath().push_front(generateDiagForSwitchOP(C, Dst, Start));
881
15
    break;
882
1
  }
883
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
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
901
27
    if (*(Src->succ_begin() + 1) == Dst)
902
11
      os << "false";
903
16
    else
904
16
      os << "true";
905
906
27
    PathDiagnosticLocation End = ExecutionContinues(C);
907
908
27
    if (const Stmt *S = End.asStmt())
909
27
      End = getEnclosingStmtLocation(S, C.getCurrLocationContext());
910
911
27
    C.getActivePath().push_front(
912
27
        std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
913
27
    break;
914
27
  }
915
916
  // Determine control-flow for short-circuited '&&' and '||'.
917
81
  case Stmt::BinaryOperatorClass: {
918
81
    if (!C.supportsLogicalOpControlFlow())
919
0
      break;
920
921
81
    C.getActivePath().push_front(generateDiagForBinaryOP(C, T, Src, Dst));
922
81
    break;
923
81
  }
924
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
930
1
      os << "Loop condition is true. ";
931
1
      PathDiagnosticLocation End = ExecutionContinues(os, C);
932
933
1
      if (const Stmt *S = End.asStmt())
934
1
        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());
935
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
942
10
      if (const Stmt *S = End.asStmt())
943
10
        End = getEnclosingStmtLocation(S, C.getCurrLocationContext());
944
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
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
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
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
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
975
157
    break;
976
977
563
  case Stmt::IfStmtClass: {
978
563
    PathDiagnosticLocation End = ExecutionContinues(C);
979
980
563
    if (const Stmt *S = End.asStmt())
981
508
      End = getEnclosingStmtLocation(S, C.getCurrLocationContext());
982
983
563
    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
295
    else
988
295
      C.getActivePath().push_front(
989
295
          std::make_shared<PathDiagnosticControlFlowPiece>(
990
295
              Start, End, "Taking true branch"));
991
992
563
    break;
993
157
  }
994
890
  }
995
890
}
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.1k
                          PathDiagnosticLocation NewLoc) {
1081
21.1k
  if (!NewLoc.isValid())
1082
0
    return;
1083
1084
21.1k
  SourceLocation NewLocL = NewLoc.asLocation();
1085
21.1k
  if (NewLocL.isInvalid())
1086
157
    return;
1087
1088
20.9k
  if (!PrevLoc.isValid() || 
!PrevLoc.asLocation().isValid()20.8k
) {
1089
118
    PrevLoc = NewLoc;
1090
118
    return;
1091
118
  }
1092
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()20.0k
)
1096
8.83k
    return;
1097
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
213k
    PathDiagnosticConstruct &C, PathDiagnosticLocation &PrevLoc) const {
1124
213k
  ProgramPoint P = C.getCurrentNode()->getLocation();
1125
213k
  const SourceManager &SM = getSourceManager();
1126
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
213k
  if (auto CE = P.getAs<CallEnter>()) {
1132
1133
6.98k
    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
1148
    // Did we visit an entire call?
1149
6.98k
    bool VisitedEntireCall = C.PD->isWithinCall();
1150
6.98k
    C.PD->popActivePath();
1151
1152
6.98k
    PathDiagnosticCallPiece *Call;
1153
6.98k
    if (VisitedEntireCall) {
1154
6.81k
      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
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
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.98k
    Call->setCallee(*CE, SM);
1178
1179
    // Update the previous location in the active path.
1180
6.98k
    PrevLoc = Call->getLocation();
1181
1182
6.98k
    if (!C.CallStack.empty()) {
1183
6.81k
      assert(C.CallStack.back().first == Call);
1184
6.81k
      C.CallStack.pop_back();
1185
6.81k
    }
1186
6.98k
    return;
1187
6.98k
  }
1188
1189
206k
  assert(C.getCurrLocationContext() == C.getLocationContextForActivePath() &&
1190
206k
         "The current position in the bug path is out of sync with the "
1191
206k
         "location context associated with the active path!");
1192
1193
  // Have we encountered an exit from a function call?
1194
206k
  if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1195
1196
    // We are descending into a call (backwards).  Construct
1197
    // a new call piece to contain the path pieces for that call.
1198
6.81k
    auto Call = PathDiagnosticCallPiece::construct(*CE, SM);
1199
    // Record the mapping from call piece to LocationContext.
1200
6.81k
    assert(!C.isInLocCtxMap(&Call->path) &&
1201
6.81k
           "We just entered a call, this must've been the first time we "
1202
6.81k
           "encounter its context!");
1203
6.81k
    C.updateLocCtxMap(&Call->path, CE->getCalleeContext());
1204
1205
6.81k
    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
1211
6.81k
    auto *P = Call.get();
1212
6.81k
    C.getActivePath().push_front(std::move(Call));
1213
1214
    // Make the contents of the call the active path for now.
1215
6.81k
    C.PD->pushActivePath(&P->path);
1216
6.81k
    C.CallStack.push_back(CallWithEntry(P, C.getCurrentNode()));
1217
6.81k
    return;
1218
6.81k
  }
1219
1220
199k
  if (auto PS = P.getAs<PostStmt>()) {
1221
116k
    if (!C.shouldAddPathEdges())
1222
96.9k
      return;
1223
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
1233
83.3k
  } else if (auto BE = P.getAs<BlockEdge>()) {
1234
1235
17.0k
    if (!C.shouldAddPathEdges()) {
1236
15.4k
      generateMinimalDiagForBlockEdge(C, *BE);
1237
15.4k
      return;
1238
15.4k
    }
1239
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
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
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
1261
27
      addEdgeToPath(C.getActivePath(), PrevLoc, p->getLocation());
1262
27
      C.getActivePath().push_front(std::move(p));
1263
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
1270
1.59k
    const CFGBlock *BSrc = BE->getSrc();
1271
1.59k
    const ParentMap &PM = C.getParentMap();
1272
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
1281
91
        StringRef str;
1282
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
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
199k
}
1313
1314
static std::unique_ptr<PathDiagnostic>
1315
1.27k
generateDiagnosticForBasicReport(const BasicBugReport *R) {
1316
1.27k
  const BugType &BT = R->getBugType();
1317
1.27k
  return std::make_unique<PathDiagnostic>(
1318
1.27k
      BT.getCheckerName(), R->getDeclWithIssue(), BT.getDescription(),
1319
1.27k
      R->getDescription(), R->getShortDescription(/*UseFallback=*/false),
1320
1.27k
      BT.getCategory(), R->getUniqueingLocation(), R->getUniqueingDecl(),
1321
1.27k
      std::make_unique<FilesToLineNumsMap>());
1322
1.27k
}
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.11k
    return nullptr;
1338
1339
50.4k
  
while (50.0k
true) {
1340
50.4k
    S = PM.getParentIgnoreParens(S);
1341
1342
50.4k
    if (!S)
1343
42
      break;
1344
1345
50.3k
    if (isa<FullExpr>(S) ||
1346
50.0k
        isa<CXXBindTemporaryExpr>(S) ||
1347
50.0k
        isa<SubstNonTypeTemplateParmExpr>(S))
1348
325
      continue;
1349
1350
50.0k
    break;
1351
50.0k
  }
1352
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
766
static void addContextEdges(PathPieces &pieces, const LocationContext *LC) {
1414
766
  const ParentMap &PM = LC->getParentMap();
1415
766
  PathPieces::iterator Prev = pieces.end();
1416
6.23k
  for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;
1417
5.47k
       Prev = I, ++I) {
1418
5.47k
    auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1419
1420
5.47k
    if (!Piece)
1421
1.86k
      continue;
1422
1423
3.61k
    PathDiagnosticLocation SrcLoc = Piece->getStartLocation();
1424
3.61k
    SmallVector<PathDiagnosticLocation, 4> SrcContexts;
1425
1426
3.61k
    PathDiagnosticLocation NextSrcContext = SrcLoc;
1427
3.61k
    const Stmt *InnerStmt = nullptr;
1428
7.31k
    while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {
1429
3.70k
      SrcContexts.push_back(NextSrcContext);
1430
3.70k
      InnerStmt = NextSrcContext.asStmt();
1431
3.70k
      NextSrcContext = getEnclosingStmtLocation(InnerStmt, LC,
1432
3.70k
                                                /*allowNested=*/true);
1433
3.70k
    }
1434
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
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.68k
        break;
1447
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
1452
      // Update the subexpression node to point to the context edge.
1453
800
      Piece->setStartLocation(DstContext);
1454
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
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
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.61k
  }
1482
766
}
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
766
static void simplifySimpleBranches(PathPieces &pieces) {
1495
5.53k
  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
1498
4.78k
    if (!PieceI)
1499
1.80k
      continue;
1500
1501
2.98k
    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1502
2.98k
    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();
1503
1504
2.98k
    if (!s1Start || 
!s1End2.19k
)
1505
1.11k
      continue;
1506
1507
1.87k
    PathPieces::iterator NextI = I; ++NextI;
1508
1.87k
    if (NextI == E)
1509
20
      break;
1510
1511
1.85k
    PathDiagnosticControlFlowPiece *PieceNextI = nullptr;
1512
1513
1.91k
    while (true) {
1514
1.91k
      if (NextI == E)
1515
0
        break;
1516
1517
1.91k
      const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1518
1.91k
      if (EV) {
1519
936
        StringRef S = EV->getString();
1520
936
        if (S == StrEnteringLoop || 
S == StrLoopBodyZero895
||
1521
886
            S == StrLoopCollectionEmpty || 
S == StrLoopRangeEmpty880
) {
1522
62
          ++NextI;
1523
62
          continue;
1524
62
        }
1525
874
        break;
1526
874
      }
1527
1528
981
      PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1529
981
      break;
1530
981
    }
1531
1532
1.85k
    if (!PieceNextI)
1533
970
      continue;
1534
1535
885
    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1536
885
    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();
1537
1538
885
    if (!s2Start || !s2End || 
s1End != s2Start713
)
1539
172
      continue;
1540
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
1548
    // Is s1End the branch condition?
1549
163
    if (!isConditionForTerminator(s1Start, s1End))
1550
57
      continue;
1551
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
766
}
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
1569
2.81k
  FileID FID = SM.getFileID(ExpansionRange.getBegin());
1570
2.81k
  if (FID != SM.getFileID(ExpansionRange.getEnd()))
1571
0
    return None;
1572
1573
2.81k
  Optional<MemoryBufferRef> Buffer = SM.getBufferOrNone(FID);
1574
2.81k
  if (!Buffer)
1575
0
    return None;
1576
1577
2.81k
  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
1578
2.81k
  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
1579
2.81k
  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
1580
1581
  // We're searching the raw bytes of the buffer here, which might include
1582
  // escaped newlines and such. That's okay; we're trying to decide whether the
1583
  // SourceRange is covering a large or small amount of space in the user's
1584
  // editor.
1585
2.81k
  if (Snippet.find_first_of("\r\n") != StringRef::npos)
1586
1.14k
    return None;
1587
1588
  // This isn't Unicode-aware, but it doesn't need to be.
1589
1.67k
  return Snippet.size();
1590
1.67k
}
1591
1592
/// \sa getLengthOnSingleLine(SourceManager, SourceRange)
1593
static Optional<size_t> getLengthOnSingleLine(const SourceManager &SM,
1594
589
                                              const Stmt *S) {
1595
589
  return getLengthOnSingleLine(SM, S->getSourceRange());
1596
589
}
1597
1598
/// Eliminate two-edge cycles created by addContextEdges().
1599
///
1600
/// Once all the context edges are in place, there are plenty of cases where
1601
/// there's a single edge from a top-level statement to a subexpression,
1602
/// followed by a single path note, and then a reverse edge to get back out to
1603
/// the top level. If the statement is simple enough, the subexpression edges
1604
/// just add noise and make it harder to understand what's going on.
1605
///
1606
/// This function only removes edges in pairs, because removing only one edge
1607
/// might leave other edges dangling.
1608
///
1609
/// This will not remove edges in more complicated situations:
1610
/// - if there is more than one "hop" leading to or from a subexpression.
1611
/// - if there is an inlined call between the edges instead of a single event.
1612
/// - if the whole statement is large enough that having subexpression arrows
1613
///   might be helpful.
1614
766
static void removeContextCycles(PathPieces &Path, const SourceManager &SM) {
1615
4.39k
  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
1616
    // Pattern match the current piece and its successor.
1617
4.27k
    const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1618
1619
4.27k
    if (!PieceI) {
1620
949
      ++I;
1621
949
      continue;
1622
949
    }
1623
1624
3.32k
    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1625
3.32k
    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();
1626
1627
3.32k
    PathPieces::iterator NextI = I; ++NextI;
1628
3.32k
    if (NextI == E)
1629
23
      break;
1630
1631
3.30k
    const auto *PieceNextI =
1632
3.30k
        dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1633
1634
3.30k
    if (!PieceNextI) {
1635
1.73k
      if (isa<PathDiagnosticEventPiece>(NextI->get())) {
1636
1.57k
        ++NextI;
1637
1.57k
        if (NextI == E)
1638
624
          break;
1639
950
        PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1640
950
      }
1641
1642
1.11k
      if (!PieceNextI) {
1643
233
        ++I;
1644
233
        continue;
1645
233
      }
1646
2.44k
    }
1647
1648
2.44k
    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1649
2.44k
    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();
1650
1651
2.44k
    if (s1Start && 
s2Start1.72k
&&
s1Start == s2End1.69k
&&
s2Start == s1End301
) {
1652
301
      const size_t MAX_SHORT_LINE_LENGTH = 80;
1653
301
      Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
1654
301
      if (s1Length && 
*s1Length <= MAX_SHORT_LINE_LENGTH289
) {
1655
288
        Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
1656
288
        if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
1657
288
          Path.erase(I);
1658
288
          I = Path.erase(NextI);
1659
288
          continue;
1660
288
        }
1661
2.15k
      }
1662
301
    }
1663
1664
2.15k
    ++I;
1665
2.15k
  }
1666
766
}
1667
1668
/// Return true if X is contained by Y.
1669
2.94k
static bool lexicalContains(const ParentMap &PM, const Stmt *X, const Stmt *Y) {
1670
10.3k
  while (X) {
1671
7.93k
    if (X == Y)
1672
524
      return true;
1673
7.41k
    X = PM.getParent(X);
1674
7.41k
  }
1675
2.42k
  return false;
1676
2.94k
}
1677
1678
// Remove short edges on the same line less than 3 columns in difference.
1679
static void removePunyEdges(PathPieces &path, const SourceManager &SM,
1680
766
                            const ParentMap &PM) {
1681
766
  bool erased = false;
1682
1683
5.55k
  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
1684
4.78k
       erased ? 
I80
:
++I4.70k
) {
1685
4.78k
    erased = false;
1686
1687
4.78k
    const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1688
1689
4.78k
    if (!PieceI)
1690
1.86k
      continue;
1691
1692
2.92k
    const Stmt *start = PieceI->getStartLocation().getStmtOrNull();
1693
2.92k
    const Stmt *end   = PieceI->getEndLocation().getStmtOrNull();
1694
1695
2.92k
    if (!start || 
!end2.13k
)
1696
1.11k
      continue;
1697
1698
1.81k
    const Stmt *endParent = PM.getParent(end);
1699
1.81k
    if (!endParent)
1700
2
      continue;
1701
1702
1.81k
    if (isConditionForTerminator(end, endParent))
1703
0
      continue;
1704
1705
1.81k
    SourceLocation FirstLoc = start->getBeginLoc();
1706
1.81k
    SourceLocation SecondLoc = end->getBeginLoc();
1707
1708
1.81k
    if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
1709
84
      continue;
1710
1.73k
    if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
1711
105
      std::swap(SecondLoc, FirstLoc);
1712
1713
1.73k
    SourceRange EdgeRange(FirstLoc, SecondLoc);
1714
1.73k
    Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
1715
1716
    // If the statements are on different lines, continue.
1717
1.73k
    if (!ByteWidth)
1718
1.12k
      continue;
1719
1720
607
    const size_t MAX_PUNY_EDGE_LENGTH = 2;
1721
607
    if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
1722
      // FIXME: There are enough /bytes/ between the endpoints of the edge, but
1723
      // there might not be enough /columns/. A proper user-visible column count
1724
      // is probably too expensive, though.
1725
80
      I = path.erase(I);
1726
80
      erased = true;
1727
80
      continue;
1728
80
    }
1729
607
  }
1730
766
}
1731
1732
766
static void removeIdenticalEvents(PathPieces &path) {
1733
4.80k
  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; 
++I4.04k
) {
1734
4.70k
    const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());
1735
1736
4.70k
    if (!PieceI)
1737
3.03k
      continue;
1738
1739
1.67k
    PathPieces::iterator NextI = I; ++NextI;
1740
1.67k
    if (NextI == E)
1741
665
      return;
1742
1743
1.00k
    const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1744
1745
1.00k
    if (!PieceNextI)
1746
864
      continue;
1747
1748
    // Erase the second piece if it has the same exact message text.
1749
144
    if (PieceI->getString() == PieceNextI->getString()) {
1750
1
      path.erase(NextI);
1751
1
    }
1752
144
  }
1753
766
}
1754
1755
static bool optimizeEdges(const PathDiagnosticConstruct &C, PathPieces &path,
1756
1.62k
                          OptimizedCallsSet &OCS) {
1757
1.62k
  bool hasChanges = false;
1758
1.62k
  const LocationContext *LC = C.getLocationContextFor(&path);
1759
1.62k
  assert(LC);
1760
1.62k
  const ParentMap &PM = LC->getParentMap();
1761
1.62k
  const SourceManager &SM = C.getSourceManager();
1762
1763
21.2k
  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
1764
    // Optimize subpaths.
1765
19.6k
    if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {
1766
      // Record the fact that a call has been optimized so we only do the
1767
      // effort once.
1768
311
      if (!OCS.count(CallI)) {
1769
295
        while (optimizeEdges(C, CallI->path, OCS)) {
1770
144
        }
1771
151
        OCS.insert(CallI);
1772
151
      }
1773
311
      ++I;
1774
311
      continue;
1775
311
    }
1776
1777
    // Pattern match the current piece and its successor.
1778
19.3k
    auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1779
1780
19.3k
    if (!PieceI) {
1781
3.71k
      ++I;
1782
3.71k
      continue;
1783
3.71k
    }
1784
1785
15.6k
    const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1786
15.6k
    const Stmt *s1End   = PieceI->getEndLocation().getStmtOrNull();
1787
15.6k
    const Stmt *level1 = getStmtParent(s1Start, PM);
1788
15.6k
    const Stmt *level2 = getStmtParent(s1End, PM);
1789
1790
15.6k
    PathPieces::iterator NextI = I; ++NextI;
1791
15.6k
    if (NextI == E)
1792
72
      break;
1793
1794
15.5k
    const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1795
1796
15.5k
    if (!PieceNextI) {
1797
3.86k
      ++I;
1798
3.86k
      continue;
1799
3.86k
    }
1800
1801
11.7k
    const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1802
11.7k
    const Stmt *s2End   = PieceNextI->getEndLocation().getStmtOrNull();
1803
11.7k
    const Stmt *level3 = getStmtParent(s2Start, PM);
1804
11.7k
    const Stmt *level4 = getStmtParent(s2End, PM);
1805
1806
    // Rule I.
1807
    //
1808
    // If we have two consecutive control edges whose end/begin locations
1809
    // are at the same level (e.g. statements or top-level expressions within
1810
    // a compound statement, or siblings share a single ancestor expression),
1811
    // then merge them if they have no interesting intermediate event.
1812
    //
1813
    // For example:
1814
    //
1815
    // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
1816
    // parent is '1'.  Here 'x.y.z' represents the hierarchy of statements.
1817
    //
1818
    // NOTE: this will be limited later in cases where we add barriers
1819
    // to prevent this optimization.
1820
11.7k
    if (level1 && 
level1 == level28.96k
&&
level1 == level31.21k
&&
level1 == level41.21k
) {
1821
280
      PieceI->setEndLocation(PieceNextI->getEndLocation());
1822
280
      path.erase(NextI);
1823
280
      hasChanges = true;
1824
280
      continue;
1825
280
    }
1826
1827
    // Rule II.
1828
    //
1829
    // Eliminate edges between subexpressions and parent expressions
1830
    // when the subexpression is consumed.
1831
    //
1832
    // NOTE: this will be limited later in cases where we add barriers
1833
    // to prevent this optimization.
1834
11.4k
    if (s1End && 
s1End == s2Start11.3k
&&
level211.3k
) {
1835
11.3k
      bool removeEdge = false;
1836
      // Remove edges into the increment or initialization of a
1837
      // loop that have no interleaving event.  This means that
1838
      // they aren't interesting.
1839
11.3k
      if (isIncrementOrInitInForLoop(s1End, level2))
1840
100
        removeEdge = true;
1841
      // Next only consider edges that are not anchored on
1842
      // the condition of a terminator.  This are intermediate edges
1843
      // that we might want to trim.
1844
11.2k
      else if (!isConditionForTerminator(level2, s1End)) {
1845
        // Trim edges on expressions that are consumed by
1846
        // the parent expression.
1847
11.0k
        if (isa<Expr>(s1End) && 
PM.isConsumedExpr(cast<Expr>(s1End))9.81k
) {
1848
8.53k
          removeEdge = true;
1849
8.53k
        }
1850
        // Trim edges where a lexical containment doesn't exist.
1851
        // For example:
1852
        //
1853
        //  X -> Y -> Z
1854
        //
1855
        // If 'Z' lexically contains Y (it is an ancestor) and
1856
        // 'X' does not lexically contain Y (it is a descendant OR
1857
        // it has no lexical relationship at all) then trim.
1858
        //
1859
        // This can eliminate edges where we dive into a subexpression
1860
        // and then pop back out, etc.
1861
2.53k
        else if (s1Start && 
s2End1.92k
&&
1862
1.47k
                 lexicalContains(PM, s2Start, s2End) &&
1863
31
                 !lexicalContains(PM, s1End, s1Start)) {
1864
31
          removeEdge = true;
1865
31
        }
1866
        // Trim edges from a subexpression back to the top level if the
1867
        // subexpression is on a different line.
1868
        //
1869
        // A.1 -> A -> B
1870
        // becomes
1871
        // A.1 -> B
1872
        //
1873
        // These edges just look ugly and don't usually add anything.
1874
2.50k
        else if (s1Start && 
s2End1.89k
&&
1875
1.44k
                 lexicalContains(PM, s1Start, s1End)) {
1876
493
          SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
1877
493
                                PieceI->getStartLocation().asLocation());
1878
493
          if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
1879
3
            removeEdge = true;
1880
493
        }
1881
11.0k
      }
1882
1883
11.3k
      if (removeEdge) {
1884
8.67k
        PieceI->setEndLocation(PieceNextI->getEndLocation());
1885
8.67k
        path.erase(NextI);
1886
8.67k
        hasChanges = true;
1887
8.67k
        continue;
1888
8.67k
      }
1889
2.76k
    }
1890
1891
    // Optimize edges for ObjC fast-enumeration loops.
1892
    //
1893
    // (X -> collection) -> (collection -> element)
1894
    //
1895
    // becomes:
1896
    //
1897
    // (X -> element)
1898
2.76k
    if (s1End == s2Start) {
1899
2.76k
      const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3);
1900
2.76k
      if (FS && 
FS->getCollection()->IgnoreParens() == s2Start2
&&
1901
0
          s2End == FS->getElement()) {
1902
0
        PieceI->setEndLocation(PieceNextI->getEndLocation());
1903
0
        path.erase(NextI);
1904
0
        hasChanges = true;
1905
0
        continue;
1906
0
      }
1907
2.76k
    }
1908
1909
    // No changes at this index?  Move to the next one.
1910
2.76k
    ++I;
1911
2.76k
  }
1912
1913
1.62k
  if (!hasChanges) {
1914
    // Adjust edges into subexpressions to make them more uniform
1915
    // and aesthetically pleasing.
1916
766
    addContextEdges(path, LC);
1917
    // Remove "cyclical" edges that include one or more context edges.
1918
766
    removeContextCycles(path, SM);
1919
    // Hoist edges originating from branch conditions to branches
1920
    // for simple branches.
1921
766
    simplifySimpleBranches(path);
1922
    // Remove any puny edges left over after primary optimization pass.
1923
766
    removePunyEdges(path, SM, PM);
1924
    // Remove identical events.
1925
766
    removeIdenticalEvents(path);
1926
766
  }
1927
1928
1.62k
  return hasChanges;
1929
1.62k
}
1930
1931
/// Drop the very first edge in a path, which should be a function entry edge.
1932
///
1933
/// If the first edge is not a function entry edge (say, because the first
1934
/// statement had an invalid source location), this function does nothing.
1935
// FIXME: We should just generate invalid edges anyway and have the optimizer
1936
// deal with them.
1937
static void dropFunctionEntryEdge(const PathDiagnosticConstruct &C,
1938
615
                                  PathPieces &Path) {
1939
615
  const auto *FirstEdge =
1940
615
      dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());
1941
615
  if (!FirstEdge)
1942
1
    return;
1943
1944
614
  const Decl *D = C.getLocationContextFor(&Path)->getDecl();
1945
614
  PathDiagnosticLocation EntryLoc =
1946
614
      PathDiagnosticLocation::createBegin(D, C.getSourceManager());
1947
614
  if (FirstEdge->getStartLocation() != EntryLoc)
1948
0
    return;
1949
1950
614
  Path.pop_front();
1951
614
}
1952
1953
/// Populate executes lines with lines containing at least one diagnostics.
1954
16.0k
static void updateExecutedLinesWithDiagnosticPieces(PathDiagnostic &PD) {
1955
1956
16.0k
  PathPieces path = PD.path.flatten(/*ShouldFlattenMacros=*/true);
1957
16.0k
  FilesToLineNumsMap &ExecutedLines = PD.getExecutedLines();
1958
1959
22.7k
  for (const auto &P : path) {
1960
22.7k
    FullSourceLoc Loc = P->getLocation().asLocation().getExpansionLoc();
1961
22.7k
    FileID FID = Loc.getFileID();
1962
22.7k
    unsigned LineNo = Loc.getLineNumber();
1963
22.7k
    assert(FID.isValid());
1964
22.7k
    ExecutedLines[FID].insert(LineNo);
1965
22.7k
  }
1966
16.0k
}
1967
1968
PathDiagnosticConstruct::PathDiagnosticConstruct(
1969
    const PathDiagnosticConsumer *PDC, const ExplodedNode *ErrorNode,
1970
    const PathSensitiveBugReport *R)
1971
    : Consumer(PDC), CurrentNode(ErrorNode),
1972
      SM(CurrentNode->getCodeDecl().getASTContext().getSourceManager()),
1973
14.7k
      PD(generateEmptyDiagnosticForReport(R, getSourceManager())) {
1974
14.7k
  LCM[&PD->getActivePath()] = ErrorNode->getLocationContext();
1975
14.7k
}
1976
1977
PathDiagnosticBuilder::PathDiagnosticBuilder(
1978
    BugReporterContext BRC, std::unique_ptr<ExplodedGraph> BugPath,
1979
    PathSensitiveBugReport *r, const ExplodedNode *ErrorNode,
1980
    std::unique_ptr<VisitorsDiagnosticsTy> VisitorsDiagnostics)
1981
    : BugReporterContext(BRC), BugPath(std::move(BugPath)), R(r),
1982
      ErrorNode(ErrorNode),
1983
14.0k
      VisitorsDiagnostics(std::move(VisitorsDiagnostics)) {}
1984
1985
std::unique_ptr<PathDiagnostic>
1986
14.7k
PathDiagnosticBuilder::generate(const PathDiagnosticConsumer *PDC) const {
1987
14.7k
  PathDiagnosticConstruct Construct(PDC, ErrorNode, R);
1988
1989
14.7k
  const SourceManager &SM = getSourceManager();
1990
14.7k
  const AnalyzerOptions &Opts = getAnalyzerOptions();
1991
14.7k
  StringRef ErrorTag = ErrorNode->getLocation().getTag()->getTagDescription();
1992
1993
  // See whether we need to silence the checker/package.
1994
  // FIXME: This will not work if the report was emitted with an incorrect tag.
1995
21
  for (const std::string &CheckerOrPackage : Opts.SilencedCheckersAndPackages) {
1996
21
    if (ErrorTag.startswith(CheckerOrPackage))
1997
13
      return nullptr;
1998
21
  }
1999
2000
14.7k
  if (!PDC->shouldGenerateDiagnostics())
2001
12.8k
    return generateEmptyDiagnosticForReport(R, getSourceManager());
2002
2003
  // Construct the final (warning) event for the bug report.
2004
1.88k
  auto EndNotes = VisitorsDiagnostics->find(ErrorNode);
2005
1.88k
  PathDiagnosticPieceRef LastPiece;
2006
1.88k
  if (EndNotes != VisitorsDiagnostics->end()) {
2007
396
    assert(!EndNotes->second.empty());
2008
396
    LastPiece = EndNotes->second[0];
2009
1.49k
  } else {
2010
1.49k
    LastPiece = BugReporterVisitor::getDefaultEndPath(*this, ErrorNode,
2011
1.49k
                                                      *getBugReport());
2012
1.49k
  }
2013
1.88k
  Construct.PD->setEndOfPath(LastPiece);
2014
2015
1.88k
  PathDiagnosticLocation PrevLoc = Construct.PD->getLocation();
2016
  // From the error node to the root, ascend the bug path and construct the bug
2017
  // report.
2018
215k
  while (Construct.ascendToPrevNode()) {
2019
213k
    generatePathDiagnosticsForNode(Construct, PrevLoc);
2020
2021
213k
    auto VisitorNotes = VisitorsDiagnostics->find(Construct.getCurrentNode());
2022
213k
    if (VisitorNotes == VisitorsDiagnostics->end())
2023
210k
      continue;
2024
2025
    // This is a workaround due to inability to put shared PathDiagnosticPiece
2026
    // into a FoldingSet.
2027
2.75k
    std::set<llvm::FoldingSetNodeID> DeduplicationSet;
2028
2029
    // Add pieces from custom visitors.
2030
2.93k
    for (const PathDiagnosticPieceRef &Note : VisitorNotes->second) {
2031
2.93k
      llvm::FoldingSetNodeID ID;
2032
2.93k
      Note->Profile(ID);
2033
2.93k
      if (!DeduplicationSet.insert(ID).second)
2034
28
        continue;
2035
2036
2.90k
      if (PDC->shouldAddPathEdges())
2037
1.00k
        addEdgeToPath(Construct.getActivePath(), PrevLoc, Note->getLocation());
2038
2.90k
      updateStackPiecesWithMessage(Note, Construct.CallStack);
2039
2.90k
      Construct.getActivePath().push_front(Note);
2040
2.90k
    }
2041
2.75k
  }
2042
2043
1.88k
  if (PDC->shouldAddPathEdges()) {
2044
    // Add an edge to the start of the function.
2045
    // We'll prune it out later, but it helps make diagnostics more uniform.
2046
615
    const StackFrameContext *CalleeLC =
2047
615
        Construct.getLocationContextForActivePath()->getStackFrame();
2048
615
    const Decl *D = CalleeLC->getDecl();
2049
615
    addEdgeToPath(Construct.getActivePath(), PrevLoc,
2050
615
                  PathDiagnosticLocation::createBegin(D, SM));
2051
615
  }
2052
2053
2054
  // Finally, prune the diagnostic path of uninteresting stuff.
2055
1.88k
  if (!Construct.PD->path.empty()) {
2056
1.88k
    if (R->shouldPrunePath() && 
Opts.ShouldPrunePaths1.88k
) {
2057
1.88k
      bool stillHasNotes =
2058
1.88k
          removeUnneededCalls(Construct, Construct.getMutablePieces(), R);
2059
1.88k
      assert(stillHasNotes);
2060
1.88k
      (void)stillHasNotes;
2061
1.88k
    }
2062
2063
    // Remove pop-up notes if needed.
2064
1.88k
    if (!Opts.ShouldAddPopUpNotes)
2065
6
      removePopUpNotes(Construct.getMutablePieces());
2066
2067
    // Redirect all call pieces to have valid locations.
2068
1.88k
    adjustCallLocations(Construct.getMutablePieces());
2069
1.88k
    removePiecesWithInvalidLocations(Construct.getMutablePieces());
2070
2071
1.88k
    if (PDC->shouldAddPathEdges()) {
2072
2073
      // Reduce the number of edges from a very conservative set
2074
      // to an aesthetically pleasing subset that conveys the
2075
      // necessary information.
2076
615
      OptimizedCallsSet OCS;
2077
1.33k
      while (optimizeEdges(Construct, Construct.getMutablePieces(), OCS)) {
2078
715
      }
2079
2080
      // Drop the very first function-entry edge. It's not really necessary
2081
      // for top-level functions.
2082
615
      dropFunctionEntryEdge(Construct, Construct.getMutablePieces());
2083
615
    }
2084
2085
    // Remove messages that are basically the same, and edges that may not
2086
    // make sense.
2087
    // We have to do this after edge optimization in the Extensive mode.
2088
1.88k
    removeRedundantMsgs(Construct.getMutablePieces());
2089
1.88k
    removeEdgesToDefaultInitializers(Construct.getMutablePieces());
2090
1.88k
  }
2091
2092
1.88k
  if (Opts.ShouldDisplayMacroExpansions)
2093
41
    CompactMacroExpandedPieces(Construct.getMutablePieces(), SM);
2094
2095
1.88k
  return std::move(Construct.PD);
2096
1.88k
}
2097
2098
//===----------------------------------------------------------------------===//
2099
// Methods for BugType and subclasses.
2100
//===----------------------------------------------------------------------===//
2101
2102
0
void BugType::anchor() {}
2103
2104
0
void BuiltinBug::anchor() {}
2105
2106
//===----------------------------------------------------------------------===//
2107
// Methods for BugReport and subclasses.
2108
//===----------------------------------------------------------------------===//
2109
2110
LLVM_ATTRIBUTE_USED static bool
2111
15.4k
isDependency(const CheckerRegistryData &Registry, StringRef CheckerName) {
2112
940k
  for (const std::pair<StringRef, StringRef> &Pair : Registry.Dependencies) {
2113
940k
    if (Pair.second == CheckerName)
2114
0
      return true;
2115
940k
  }
2116
15.4k
  return false;
2117
15.4k
}
2118
2119
LLVM_ATTRIBUTE_USED static bool isHidden(const CheckerRegistryData &Registry,
2120
5.24k
                                         StringRef CheckerName) {
2121
480k
  for (const CheckerInfo &Checker : Registry.Checkers) {
2122
480k
    if (Checker.FullName == CheckerName)
2123
5.24k
      return Checker.IsHidden;
2124
480k
  }
2125
5.24k
  
llvm_unreachable0
(
2126
5.24k
      "Checker name not found in CheckerRegistry -- did you retrieve it "
2127
5.24k
      "correctly from CheckerManager::getCurrentCheckerName?");
2128
5.24k
}
2129
2130
PathSensitiveBugReport::PathSensitiveBugReport(
2131
    const BugType &bt, StringRef shortDesc, StringRef desc,
2132
    const ExplodedNode *errorNode, PathDiagnosticLocation LocationToUnique,
2133
    const Decl *DeclToUnique)
2134
    : BugReport(Kind::PathSensitive, bt, shortDesc, desc), ErrorNode(errorNode),
2135
      ErrorNodeRange(getStmt() ? getStmt()->getSourceRange() : SourceRange()),
2136
15.4k
      UniqueingLocation(LocationToUnique), UniqueingDecl(DeclToUnique) {
2137
15.4k
  assert(!isDependency(ErrorNode->getState()
2138
15.4k
                           ->getAnalysisManager()
2139
15.4k
                           .getCheckerManager()
2140
15.4k
                           ->getCheckerRegistryData(),
2141
15.4k
                       bt.getCheckerName()) &&
2142
15.4k
         "Some checkers depend on this one! We don't allow dependency "
2143
15.4k
         "checkers to emit warnings, because checkers should depend on "
2144
15.4k
         "*modeling*, not *diagnostics*.");
2145
2146
15.4k
  assert(
2147
15.4k
      (bt.getCheckerName().startswith("debug") ||
2148
15.4k
       !isHidden(ErrorNode->getState()
2149
15.4k
                     ->getAnalysisManager()
2150
15.4k
                     .getCheckerManager()
2151
15.4k
                     ->getCheckerRegistryData(),
2152
15.4k
                 bt.getCheckerName())) &&
2153
15.4k
          "Hidden checkers musn't emit diagnostics as they are by definition "
2154
15.4k
          "non-user facing!");
2155
15.4k
}
2156
2157
void PathSensitiveBugReport::addVisitor(
2158
73.5k
    std::unique_ptr<BugReporterVisitor> visitor) {
2159
73.5k
  if (!visitor)
2160
236
    return;
2161
2162
73.3k
  llvm::FoldingSetNodeID ID;
2163
73.3k
  visitor->Profile(ID);
2164
2165
73.3k
  void *InsertPos = nullptr;
2166
73.3k
  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2167
0
    return;
2168
0
  }
2169
2170
73.3k
  Callbacks.push_back(std::move(visitor));
2171
73.3k
}
2172
2173
1.67M
void PathSensitiveBugReport::clearVisitors() {
2174
1.67M
  Callbacks.clear();
2175
1.67M
}
2176
2177
27.6k
const Decl *PathSensitiveBugReport::getDeclWithIssue() const {
2178
27.6k
  const ExplodedNode *N = getErrorNode();
2179
27.6k
  if (!N)
2180
0
    return nullptr;
2181
2182
27.6k
  const LocationContext *LC = N->getLocationContext();
2183
27.6k
  return LC->getStackFrame()->getDecl();
2184
27.6k
}
2185
2186
1.36k
void BasicBugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2187
1.36k
  hash.AddInteger(static_cast<int>(getKind()));
2188
1.36k
  hash.AddPointer(&BT);
2189
1.36k
  hash.AddString(Description);
2190
1.36k
  assert(Location.isValid());
2191
1.36k
  Location.Profile(hash);
2192
2193
1.28k
  for (SourceRange range : Ranges) {
2194
1.28k
    if (!range.isValid())
2195
1
      continue;
2196
1.27k
    hash.Add(range.getBegin());
2197
1.27k
    hash.Add(range.getEnd());
2198
1.27k
  }
2199
1.36k
}
2200
2201
17.0k
void PathSensitiveBugReport::Profile(llvm::FoldingSetNodeID &hash) const {
2202
17.0k
  hash.AddInteger(static_cast<int>(getKind()));
2203
17.0k
  hash.AddPointer(&BT);
2204
17.0k
  hash.AddString(Description);
2205
17.0k
  PathDiagnosticLocation UL = getUniqueingLocation();
2206
17.0k
  if (UL.isValid()) {
2207
1.18k
    UL.Profile(hash);
2208
15.8k
  } else {
2209
    // TODO: The statement may be null if the report was emitted before any
2210
    // statements were executed. In particular, some checkers by design
2211
    // occasionally emit their reports in empty functions (that have no
2212
    // statements in their body). Do we profile correctly in this case?
2213
15.8k
    hash.AddPointer(ErrorNode->getCurrentOrPreviousStmtForDiagnostics());
2214
15.8k
  }
2215
2216
3.26k
  for (SourceRange range : Ranges) {
2217
3.26k
    if (!range.isValid())
2218
4
      continue;
2219
3.25k
    hash.Add(range.getBegin());
2220
3.25k
    hash.Add(range.getEnd());
2221
3.25k
  }
2222
17.0k
}
2223
2224
template <class T>
2225
static void insertToInterestingnessMap(
2226
    llvm::DenseMap<T, bugreporter::TrackingKind> &InterestingnessMap, T Val,
2227
6.24k
    bugreporter::TrackingKind TKind) {
2228
6.24k
  auto Result = InterestingnessMap.insert({Val, TKind});
2229
2230
6.24k
  if (Result.second)
2231
5.19k
    return;
2232
2233
  // Even if this symbol/region was already marked as interesting as a
2234
  // condition, if we later mark it as interesting again but with
2235
  // thorough tracking, overwrite it. Entities marked with thorough
2236
  // interestiness are the most important (or most interesting, if you will),
2237
  // and we wouldn't like to downplay their importance.
2238
2239
1.05k
  switch (TKind) {
2240
468
    case bugreporter::TrackingKind::Thorough:
2241
468
      Result.first->getSecond() = bugreporter::TrackingKind::Thorough;
2242
468
      return;
2243
591
    case bugreporter::TrackingKind::Condition:
2244
591
      return;
2245
0
    }
2246
2247
0
    llvm_unreachable(
2248
0
        "BugReport::markInteresting currently can only handle 2 different "
2249
0
        "tracking kinds! Please define what tracking kind should this entitiy"
2250
0
        "have, if it was already marked as interesting with a different kind!");
2251
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
2227
4.50k
    bugreporter::TrackingKind TKind) {
2228
4.50k
  auto Result = InterestingnessMap.insert({Val, TKind});
2229
2230
4.50k
  if (Result.second)
2231
3.68k
    return;
2232
2233
  // Even if this symbol/region was already marked as interesting as a
2234
  // condition, if we later mark it as interesting again but with
2235
  // thorough tracking, overwrite it. Entities marked with thorough
2236
  // interestiness are the most important (or most interesting, if you will),
2237
  // and we wouldn't like to downplay their importance.
2238
2239
821
  switch (TKind) {
2240
411
    case bugreporter::TrackingKind::Thorough:
2241
411
      Result.first->getSecond() = bugreporter::TrackingKind::Thorough;
2242
411
      return;
2243
410
    case bugreporter::TrackingKind::Condition:
2244
410
      return;
2245
0
    }
2246
2247
0
    llvm_unreachable(
2248
0
        "BugReport::markInteresting currently can only handle 2 different "
2249
0
        "tracking kinds! Please define what tracking kind should this entitiy"
2250
0
        "have, if it was already marked as interesting with a different kind!");
2251
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
2227
1.74k
    bugreporter::TrackingKind TKind) {
2228
1.74k
  auto Result = InterestingnessMap.insert({Val, TKind});
2229
2230
1.74k
  if (Result.second)
2231
1.50k
    return;
2232
2233
  // Even if this symbol/region was already marked as interesting as a
2234
  // condition, if we later mark it as interesting again but with
2235
  // thorough tracking, overwrite it. Entities marked with thorough
2236
  // interestiness are the most important (or most interesting, if you will),
2237
  // and we wouldn't like to downplay their importance.
2238
2239
238
  switch (TKind) {
2240
57
    case bugreporter::TrackingKind::Thorough:
2241
57
      Result.first->getSecond() = bugreporter::TrackingKind::Thorough;
2242
57
      return;
2243
181
    case bugreporter::TrackingKind::Condition:
2244
181
      return;
2245
0
    }
2246
2247
0
    llvm_unreachable(
2248
0
        "BugReport::markInteresting currently can only handle 2 different "
2249
0
        "tracking kinds! Please define what tracking kind should this entitiy"
2250
0
        "have, if it was already marked as interesting with a different kind!");
2251
0
}
2252
2253
void PathSensitiveBugReport::markInteresting(SymbolRef sym,
2254
6.41k
                                             bugreporter::TrackingKind TKind) {
2255
6.41k
  if (!sym)
2256
1.91k
    return;
2257
2258
4.50k
  insertToInterestingnessMap(InterestingSymbols, sym, TKind);
2259
2260
4.50k
  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
2261
0
    markInteresting(meta->getRegion(), TKind);
2262
4.50k
}
2263
2264
void PathSensitiveBugReport::markInteresting(const MemRegion *R,
2265
4.83k
                                             bugreporter::TrackingKind TKind) {
2266
4.83k
  if (!R)
2267
3.08k
    return;
2268
2269
1.74k
  R = R->getBaseRegion();
2270
1.74k
  insertToInterestingnessMap(InterestingRegions, R, TKind);
2271
2272
1.74k
  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2273
1.40k
    markInteresting(SR->getSymbol(), TKind);
2274
1.74k
}
2275
2276
void PathSensitiveBugReport::markInteresting(SVal V,
2277
3.78k
                                             bugreporter::TrackingKind TKind) {
2278
3.78k
  markInteresting(V.getAsRegion(), TKind);
2279
3.78k
  markInteresting(V.getAsSymbol(), TKind);
2280
3.78k
}
2281
2282
1.15k
void PathSensitiveBugReport::markInteresting(const LocationContext *LC) {
2283
1.15k
  if (!LC)
2284
782
    return;
2285
372
  InterestingLocationContexts.insert(LC);
2286
372
}
2287
2288
Optional<bugreporter::TrackingKind>
2289
7.13k
PathSensitiveBugReport::getInterestingnessKind(SVal V) const {
2290
7.13k
  auto RKind = getInterestingnessKind(V.getAsRegion());
2291
7.13k
  auto SKind = getInterestingnessKind(V.getAsSymbol());
2292
7.13k
  if (!RKind)
2293
6.75k
    return SKind;
2294
375
  if (!SKind)
2295
4
    return RKind;
2296
2297
  // If either is marked with throrough tracking, return that, we wouldn't like
2298
  // to downplay a note's importance by 'only' mentioning it as a condition.
2299
371
  switch(*RKind) {
2300
347
    case bugreporter::TrackingKind::Thorough:
2301
347
      return RKind;
2302
24
    case bugreporter::TrackingKind::Condition:
2303
24
      return SKind;
2304
0
  }
2305
2306
0
  llvm_unreachable(
2307
0
      "BugReport::getInterestingnessKind currently can only handle 2 different "
2308
0
      "tracking kinds! Please define what tracking kind should we return here "
2309
0
      "when the kind of getAsRegion() and getAsSymbol() is different!");
2310
0
  return None;
2311
0
}
2312
2313
Optional<bugreporter::TrackingKind>
2314
11.8k
PathSensitiveBugReport::getInterestingnessKind(SymbolRef sym) const {
2315
11.8k
  if (!sym)
2316
493
    return None;
2317
  // We don't currently consider metadata symbols to be interesting
2318
  // even if we know their region is interesting. Is that correct behavior?
2319
11.3k
  auto It = InterestingSymbols.find(sym);
2320
11.3k
  if (It == InterestingSymbols.end())
2321
10.1k
    return None;
2322
1.22k
  return It->getSecond();
2323
1.22k
}
2324
2325
Optional<bugreporter::TrackingKind>
2326
13.5k
PathSensitiveBugReport::getInterestingnessKind(const MemRegion *R) const {
2327
13.5k
  if (!R)
2328
6.21k
    return None;
2329
2330
7.33k
  R = R->getBaseRegion();
2331
7.33k
  auto It = InterestingRegions.find(R);
2332
7.33k
  if (It != InterestingRegions.end())
2333
478
    return It->getSecond();
2334
2335
6.85k
  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2336
959
    return getInterestingnessKind(SR->getSymbol());
2337
5.89k
  return None;
2338
5.89k
}
2339
2340
5.81k
bool PathSensitiveBugReport::isInteresting(SVal V) const {
2341
5.81k
  return getInterestingnessKind(V).hasValue();
2342
5.81k
}
2343
2344
3.73k
bool PathSensitiveBugReport::isInteresting(SymbolRef sym) const {
2345
3.73k
  return getInterestingnessKind(sym).hasValue();
2346
3.73k
}
2347
2348
6.40k
bool PathSensitiveBugReport::isInteresting(const MemRegion *R) const {
2349
6.40k
  return getInterestingnessKind(R).hasValue();
2350
6.40k
}
2351
2352
6.97k
bool PathSensitiveBugReport::isInteresting(const LocationContext *LC)  const {
2353
6.97k
  if (!LC)
2354
0
    return false;
2355
6.97k
  return InterestingLocationContexts.count(LC);
2356
6.97k
}
2357
2358
41.7k
const Stmt *PathSensitiveBugReport::getStmt() const {
2359
41.7k
  if (!ErrorNode)
2360
0
    return nullptr;
2361
2362
41.7k
  ProgramPoint ProgP = ErrorNode->getLocation();
2363
41.7k
  const Stmt *S = nullptr;
2364
2365
41.7k
  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2366
0
    CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2367
0
    if (BE->getBlock() == &Exit)
2368
0
      S = ErrorNode->getPreviousStmtForDiagnostics();
2369
0
  }
2370
41.7k
  if (!S)
2371
41.7k
    S = ErrorNode->getStmtForDiagnostics();
2372
2373
41.7k
  return S;
2374
41.7k
}
2375
2376
ArrayRef<SourceRange>
2377
14.1k
PathSensitiveBugReport::getRanges() const {
2378
  // If no custom ranges, add the range of the statement corresponding to
2379
  // the error node.
2380
14.1k
  if (Ranges.empty() && 
isa_and_nonnull<Expr>(getStmt())11.0k
)
2381
10.5k
      return ErrorNodeRange;
2382
2383
3.60k
  return Ranges;
2384
3.60k
}
2385
2386
PathDiagnosticLocation
2387
43.5k
PathSensitiveBugReport::getLocation() const {
2388
43.5k
  assert(ErrorNode && "Cannot create a location with a null node.");
2389
43.5k
  const Stmt *S = ErrorNode->getStmtForDiagnostics();
2390
43.5k
    ProgramPoint P = ErrorNode->getLocation();
2391
43.5k
  const LocationContext *LC = P.getLocationContext();
2392
43.5k
  SourceManager &SM =
2393
43.5k
      ErrorNode->getState()->getStateManager().getContext().getSourceManager();
2394
2395
43.5k
  if (!S) {
2396
    // If this is an implicit call, return the implicit call point location.
2397
412
    if (Optional<PreImplicitCall> PIE = P.getAs<PreImplicitCall>())
2398
24
      return PathDiagnosticLocation(PIE->getLocation(), SM);
2399
388
    if (auto FE = P.getAs<FunctionExitPoint>()) {
2400
388
      if (const ReturnStmt *RS = FE->getStmt())
2401
0
        return PathDiagnosticLocation::createBegin(RS, SM, LC);
2402
388
    }
2403
388
    S = ErrorNode->getNextStmtForDiagnostics();
2404
388
  }
2405
2406
43.5k
  if (S) {
2407
    // For member expressions, return the location of the '.' or '->'.
2408
43.4k
    if (const auto *ME = dyn_cast<MemberExpr>(S))
2409
16
      return PathDiagnosticLocation::createMemberLoc(ME, SM);
2410
2411
    // For binary operators, return the location of the operator.
2412
43.3k
    if (const auto *B = dyn_cast<BinaryOperator>(S))
2413
3.32k
      return PathDiagnosticLocation::createOperatorLoc(B, SM);
2414
2415
40.0k
    if (P.getAs<PostStmtPurgeDeadSymbols>())
2416
658
      return PathDiagnosticLocation::createEnd(S, SM, LC);
2417
2418
39.3k
    if (S->getBeginLoc().isValid())
2419
39.3k
      return PathDiagnosticLocation(S, SM, LC);
2420
2421
2
    return PathDiagnosticLocation(
2422
2
        PathDiagnosticLocation::getValidSourceLocation(S, LC), SM);
2423
2
  }
2424
2425
156
  return PathDiagnosticLocation::createDeclEnd(ErrorNode->getLocationContext(),
2426
156
                                               SM);
2427
156
}
2428
2429
//===----------------------------------------------------------------------===//
2430
// Methods for BugReporter and subclasses.
2431
//===----------------------------------------------------------------------===//
2432
2433
14.2k
const ExplodedGraph &PathSensitiveBugReporter::getGraph() const {
2434
14.2k
  return Eng.getGraph();
2435
14.2k
}
2436
2437
36.3k
ProgramStateManager &PathSensitiveBugReporter::getStateManager() const {
2438
36.3k
  return Eng.getStateManager();
2439
36.3k
}
2440
2441
47.5k
BugReporter::BugReporter(BugReporterData &d) : D(d) {}
2442
47.5k
BugReporter::~BugReporter() {
2443
  // Make sure reports are flushed.
2444
47.5k
  assert(StrBugTypes.empty() &&
2445
47.5k
         "Destroying BugReporter before diagnostics are emitted!");
2446
2447
  // Free the bug reports we are tracking.
2448
47.5k
  for (const auto I : EQClassesVector)
2449
15.5k
    delete I;
2450
47.5k
}
2451
2452
47.5k
void BugReporter::FlushReports() {
2453
  // We need to flush reports in deterministic order to ensure the order
2454
  // of the reports is consistent between runs.
2455
47.5k
  for (const auto EQ : EQClassesVector)
2456
15.5k
    FlushReport(*EQ);
2457
2458
  // BugReporter owns and deletes only BugTypes created implicitly through
2459
  // EmitBasicReport.
2460
  // FIXME: There are leaks from checkers that assume that the BugTypes they
2461
  // create will be destroyed by the BugReporter.
2462
47.5k
  StrBugTypes.clear();
2463
47.5k
}
2464
2465
//===----------------------------------------------------------------------===//
2466
// PathDiagnostics generation.
2467
//===----------------------------------------------------------------------===//
2468
2469
namespace {
2470
2471
/// A wrapper around an ExplodedGraph that contains a single path from the root
2472
/// to the error node.
2473
class BugPathInfo {
2474
public:
2475
  std::unique_ptr<ExplodedGraph> BugPath;
2476
  PathSensitiveBugReport *Report;
2477
  const ExplodedNode *ErrorNode;
2478
};
2479
2480
/// A wrapper around an ExplodedGraph whose leafs are all error nodes. Can
2481
/// conveniently retrieve bug paths from a single error node to the root.
2482
class BugPathGetter {
2483
  std::unique_ptr<ExplodedGraph> TrimmedGraph;
2484
2485
  using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;
2486
2487
  /// Assign each node with its distance from the root.
2488
  PriorityMapTy PriorityMap;
2489
2490
  /// Since the getErrorNode() or BugReport refers to the original ExplodedGraph,
2491
  /// we need to pair it to the error node of the constructed trimmed graph.
2492
  using ReportNewNodePair =
2493
      std::pair<PathSensitiveBugReport *, const ExplodedNode *>;
2494
  SmallVector<ReportNewNodePair, 32> ReportNodes;
2495
2496
  BugPathInfo CurrentBugPath;
2497
2498
  /// A helper class for sorting ExplodedNodes by priority.
2499
  template <bool Descending>
2500
  class PriorityCompare {
2501
    const PriorityMapTy &PriorityMap;
2502
2503
  public:
2504
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
2504
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
2504
1.67M
    PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2505
2506
3.15k
    bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2507
3.15k
      PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2508
3.15k
      PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2509
3.15k
      PriorityMapTy::const_iterator E = PriorityMap.end();
2510
2511
3.15k
      if (LI == E)
2512
101
        return Descending;
2513
3.05k
      if (RI == E)
2514
38
        return !Descending;
2515
2516
3.01k
      return Descending ? 
LI->second > RI->second2.66k
2517
349
                        : LI->second < RI->second;
2518
3.01k
    }
BugReporter.cpp:(anonymous namespace)::BugPathGetter::PriorityCompare<true>::operator()(clang::ento::ExplodedNode const*, clang::ento::ExplodedNode const*) const
Line
Count
Source
2506
2.66k
    bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2507
2.66k
      PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2508
2.66k
      PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2509
2.66k
      PriorityMapTy::const_iterator E = PriorityMap.end();
2510
2511
2.66k
      if (LI == E)
2512
0
        return Descending;
2513
2.66k
      if (RI == E)
2514
0
        return !Descending;
2515
2516
2.66k
      return Descending ? LI->second > RI->second
2517
0
                        : LI->second < RI->second;
2518
2.66k
    }
BugReporter.cpp:(anonymous namespace)::BugPathGetter::PriorityCompare<false>::operator()(clang::ento::ExplodedNode const*, clang::ento::ExplodedNode const*) const
Line
Count
Source
2506
488
    bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2507
488
      PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2508
488
      PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2509
488
      PriorityMapTy::const_iterator E = PriorityMap.end();
2510
2511
488
      if (LI == E)
2512
101
        return Descending;
2513
387
      if (RI == E)
2514
38
        return !Descending;
2515
2516
349
      return Descending ? 
LI->second > RI->second0
2517
349
                        : LI->second < RI->second;
2518
349
    }
2519
2520
    bool operator()(const ReportNewNodePair &LHS,
2521
2.66k
                    const ReportNewNodePair &RHS) const {
2522
2.66k
      return (*this)(LHS.second, RHS.second);
2523
2.66k
    }
2524
  };
2525
2526
public:
2527
  BugPathGetter(const ExplodedGraph *OriginalGraph,
2528
                ArrayRef<PathSensitiveBugReport *> &bugReports);
2529
2530
  BugPathInfo *getNextBugPath();
2531
};
2532
2533
} // namespace
2534
2535
BugPathGetter::BugPathGetter(const ExplodedGraph *OriginalGraph,
2536
14.2k
                             ArrayRef<PathSensitiveBugReport *> &bugReports) {
2537
14.2k
  SmallVector<const ExplodedNode *, 32> Nodes;
2538
15.3k
  for (const auto I : bugReports) {
2539
15.3k
    assert(I->isValid() &&
2540
15.3k
           "We only allow BugReporterVisitors and BugReporter itself to "
2541
15.3k
           "invalidate reports!");
2542
15.3k
    Nodes.emplace_back(I->getErrorNode());
2543
15.3k
  }
2544
2545
  // The trimmed graph is created in the body of the constructor to ensure
2546
  // that the DenseMaps have been initialized already.
2547
14.2k
  InterExplodedGraphMap ForwardMap;
2548
14.2k
  TrimmedGraph = OriginalGraph->trim(Nodes, &ForwardMap);
2549
2550
  // Find the (first) error node in the trimmed graph.  We just need to consult
2551
  // the node map which maps from nodes in the original graph to nodes
2552
  // in the new graph.
2553
14.2k
  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2554
2555
15.3k
  for (PathSensitiveBugReport *Report : bugReports) {
2556
15.3k
    const ExplodedNode *NewNode = ForwardMap.lookup(Report->getErrorNode());
2557
15.3k
    assert(NewNode &&
2558
15.3k
           "Failed to construct a trimmed graph that contains this error "
2559
15.3k
           "node!");
2560
15.3k
    ReportNodes.emplace_back(Report, NewNode);
2561
15.3k
    RemainingNodes.insert(NewNode);
2562
15.3k
  }
2563
2564
14.2k
  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2565
2566
  // Perform a forward BFS to find all the shortest paths.
2567
14.2k
  std::queue<const ExplodedNode *> WS;
2568
2569
14.2k
  assert(TrimmedGraph->num_roots() == 1);
2570
14.2k
  WS.push(*TrimmedGraph->roots_begin());
2571
14.2k
  unsigned Priority = 0;
2572
2573
1.83M
  while (!WS.empty()) {
2574
1.83M
    const ExplodedNode *Node = WS.front();
2575
1.83M
    WS.pop();
2576
2577
1.83M
    PriorityMapTy::iterator PriorityEntry;
2578
1.83M
    bool IsNew;
2579
1.83M
    std::tie(PriorityEntry, IsNew) = PriorityMap.insert({Node, Priority});
2580
1.83M
    ++Priority;
2581
2582
1.83M
    if (!IsNew) {
2583
604
      assert(PriorityEntry->second <= Priority);
2584
604
      continue;
2585
604
    }
2586
2587
1.83M
    if (RemainingNodes.erase(Node))
2588
15.3k
      if (RemainingNodes.empty())
2589
14.2k
        break;
2590
2591
1.82M
    for (const ExplodedNode *Succ : Node->succs())
2592
1.82M
      WS.push(Succ);
2593
1.82M
  }
2594
2595
  // Sort the error paths from longest to shortest.
2596
14.2k
  llvm::sort(ReportNodes, PriorityCompare<true>(PriorityMap));
2597
14.2k
}
2598
2599
14.4k
BugPathInfo *BugPathGetter::getNextBugPath() {
2600
14.4k
  if (ReportNodes.empty())
2601
194
    return nullptr;
2602
2603
14.2k
  const ExplodedNode *OrigN;
2604
14.2k
  std::tie(CurrentBugPath.Report, OrigN) = ReportNodes.pop_back_val();
2605
14.2k
  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2606
14.2k
         "error node not accessible from root");
2607
2608
  // Create a new graph with a single path. This is the graph that will be
2609
  // returned to the caller.
2610
14.2k
  auto GNew = std::make_unique<ExplodedGraph>();
2611
2612
  // Now walk from the error node up the BFS path, always taking the
2613
  // predeccessor with the lowest number.
2614
14.2k
  ExplodedNode *Succ = nullptr;
2615
1.68M
  while (true) {
2616
    // Create the equivalent node in the new graph with the same state
2617
    // and location.
2618
1.68M
    ExplodedNode *NewN = GNew->createUncachedNode(
2619
1.68M
        OrigN->getLocation(), OrigN->getState(),
2620
1.68M
        OrigN->getID(), OrigN->isSink());
2621
2622
    // Link up the new node with the previous node.
2623
1.68M
    if (Succ)
2624
1.67M
      Succ->addPredecessor(NewN, *GNew);
2625
14.2k
    else
2626
14.2k
      CurrentBugPath.ErrorNode = NewN;
2627
2628
1.68M
    Succ = NewN;
2629
2630
    // Are we at the final node?
2631
1.68M
    if (OrigN->pred_empty()) {
2632
14.2k
      GNew->addRoot(NewN);
2633
14.2k
      break;
2634
14.2k
    }
2635
2636
    // Find the next predeccessor node.  We choose the node that is marked
2637
    // with the lowest BFS number.
2638
1.67M
    OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2639
1.67M
                              PriorityCompare<false>(PriorityMap));
2640
1.67M
  }
2641
2642
14.2k
  CurrentBugPath.BugPath = std::move(GNew);
2643
2644
14.2k
  return &CurrentBugPath;
2645
14.2k
}
2646
2647
/// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic
2648
/// object and collapses PathDiagosticPieces that are expanded by macros.
2649
static void CompactMacroExpandedPieces(PathPieces &path,
2650
60
                                       const SourceManager& SM) {
2651
60
  using MacroStackTy = std::vector<
2652
60
      std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>;
2653
2654
60
  using PiecesTy = std::vector<PathDiagnosticPieceRef>;
2655
2656
60
  MacroStackTy MacroStack;
2657
60
  PiecesTy Pieces;
2658
2659
60
  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2660
301
       I != E; 
++I241
) {
2661
241
    const auto &piece = *I;
2662
2663
    // Recursively compact calls.
2664
241
    if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {
2665
19
      CompactMacroExpandedPieces(call->path, SM);
2666
19
    }
2667
2668
    // Get the location of the PathDiagnosticPiece.
2669
241
    const FullSourceLoc Loc = piece->getLocation().asLocation();
2670
2671
    // Determine the instantiation location, which is the location we group
2672
    // related PathDiagnosticPieces.
2673
241
    SourceLocation InstantiationLoc = Loc.isMacroID() ?
2674
93
                                      SM.getExpansionLoc(Loc) :
2675
148
                                      SourceLocation();
2676
2677
241
    if (Loc.isFileID()) {
2678
148
      MacroStack.clear();
2679
148
      Pieces.push_back(piece);
2680
148
      continue;
2681
148
    }
2682
2683
93
    assert(Loc.isMacroID());
2684
2685
    // Is the PathDiagnosticPiece within the same macro group?
2686
93
    if (!MacroStack.empty() && 
InstantiationLoc == MacroStack.back().second49
) {
2687
48
      MacroStack.back().first->subPieces.push_back(piece);
2688
48
      continue;
2689
48
    }
2690
2691
    // We aren't in the same group.  Are we descending into a new macro
2692
    // or are part of an old one?
2693
45
    std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;
2694
2695
45
    SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2696
0
                                          SM.getExpansionLoc(Loc) :
2697
45
                                          SourceLocation();
2698
2699
    // Walk the entire macro stack.
2700
46
    while (!MacroStack.empty()) {
2701
1
      if (InstantiationLoc == MacroStack.back().second) {
2702
0
        MacroGroup = MacroStack.back().first;
2703
0
        break;
2704
0
      }
2705
2706
1
      if (ParentInstantiationLoc == MacroStack.back().second) {
2707
0
        MacroGroup = MacroStack.back().first;
2708
0
        break;
2709
0
      }
2710
2711
1
      MacroStack.pop_back();
2712
1
    }
2713
2714
45
    if (!MacroGroup || 
ParentInstantiationLoc == MacroStack.back().second0
) {
2715
      // Create a new macro group and add it to the stack.
2716
45
      auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(
2717
45
          PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2718
2719
45
      if (MacroGroup)
2720
0
        MacroGroup->subPieces.push_back(NewGroup);
2721
45
      else {
2722
45
        assert(InstantiationLoc.isFileID());
2723
45
        Pieces.push_back(NewGroup);
2724
45
      }
2725
2726
45
      MacroGroup = NewGroup;
2727
45
      MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2728
45
    }
2729
2730
    // Finally, add the PathDiagnosticPiece to the group.
2731
45
    MacroGroup->subPieces.push_back(piece);
2732
45
  }
2733
2734
  // Now take the pieces and construct a new PathDiagnostic.
2735
60
  path.clear();
2736
2737
60
  path.insert(path.end(), Pieces.begin(), Pieces.end());
2738
60
}
2739
2740
/// Generate notes from all visitors.
2741
/// Notes associated with {@code ErrorNode} are generated using
2742
/// {@code getEndPath}, and the rest are generated with {@code VisitNode}.
2743
static std::unique_ptr<VisitorsDiagnosticsTy>
2744
generateVisitorsDiagnostics(PathSensitiveBugReport *R,
2745
                            const ExplodedNode *ErrorNode,
2746
14.2k
                            BugReporterContext &BRC) {
2747
14.2k
  std::unique_ptr<VisitorsDiagnosticsTy> Notes =
2748
14.2k
      std::make_unique<VisitorsDiagnosticsTy>();
2749
14.2k
  PathSensitiveBugReport::VisitorList visitors;
2750
2751
  // Run visitors on all nodes starting from the node *before* the last one.
2752
  // The last node is reserved for notes generated with {@code getEndPath}.
2753
14.2k
  const ExplodedNode *NextNode = ErrorNode->getFirstPred();
2754
1.67M
  while (NextNode) {
2755
2756
    // At each iteration, move all visitors from report to visitor list. This is
2757
    // important, because the Profile() functions of the visitors make sure that
2758
    // a visitor isn't added multiple times for the same node, but it's fine
2759
    // to add the a visitor with Profile() for different nodes (e.g. tracking
2760
    // a region at different points of the symbolic execution).
2761
1.67M
    for (std::unique_ptr<BugReporterVisitor> &Visitor : R->visitors())
2762
72.7k
      visitors.push_back(std::move(Visitor));
2763
2764
1.67M
    R->clearVisitors();
2765
2766
1.67M
    const ExplodedNode *Pred = NextNode->getFirstPred();
2767
1.67M
    if (!Pred) {
2768
14.1k
      PathDiagnosticPieceRef LastPiece;
2769
71.6k
      for (auto &V : visitors) {
2770
71.6k
        V->finalizeVisitor(BRC, ErrorNode, *R);
2771
2772
71.6k
        if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) {
2773
800
          assert(!LastPiece &&
2774
800
                 "There can only be one final piece in a diagnostic.");
2775
800
          assert(Piece->getKind() == PathDiagnosticPiece::Kind::Event &&
2776
800
                 "The final piece must contain a message!");
2777
800
          LastPiece = std::move(Piece);
2778
800
          (*Notes)[ErrorNode].push_back(LastPiece);
2779
800
        }
2780
71.6k
      }
2781
14.1k
      break;
2782
14.1k
    }
2783
2784
7.43M
    
for (auto &V : visitors)1.65M
{
2785
7.43M
      auto P = V->VisitNode(NextNode, BRC, *R);
2786
7.43M
      if (P)
2787
11.7k
        (*Notes)[NextNode].push_back(std::move(P));
2788
7.43M
    }
2789
2790
1.65M
    if (!R->isValid())
2791
91
      break;
2792
2793
1.65M
    NextNode = Pred;
2794
1.65M
  }
2795
2796
14.2k
  return Notes;
2797
14.2k
}
2798
2799
Optional<PathDiagnosticBuilder> PathDiagnosticBuilder::findValidReport(
2800
    ArrayRef<PathSensitiveBugReport *> &bugReports,
2801
14.2k
    PathSensitiveBugReporter &Reporter) {
2802
2803
14.2k
  BugPathGetter BugGraph(&Reporter.getGraph(), bugReports);
2804
2805
14.4k
  while (BugPathInfo *BugPath = BugGraph.getNextBugPath()) {
2806
    // Find the BugReport with the original location.
2807
14.2k
    PathSensitiveBugReport *R = BugPath->Report;
2808
14.2k
    assert(R && "No original report found for sliced graph.");
2809
14.2k
    assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
2810
14.2k
    const ExplodedNode *ErrorNode = BugPath->ErrorNode;
2811
2812
    // Register refutation visitors first, if they mark the bug invalid no
2813
    // further analysis is required
2814
14.2k
    R->addVisitor(std::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
2815
2816
    // Register additional node visitors.
2817
14.2k
    R->addVisitor(std::make_unique<NilReceiverBRVisitor>());
2818
14.2k
    R->addVisitor(std::make_unique<ConditionBRVisitor>());
2819
14.2k
    R->addVisitor(std::make_unique<TagVisitor>());
2820
2821
14.2k
    BugReporterContext BRC(Reporter);
2822
2823
    // Run all visitors on a given graph, once.
2824
14.2k
    std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes =
2825
14.2k
        generateVisitorsDiagnostics(R, ErrorNode, BRC);
2826
2827
14.2k
    if (R->isValid()) {
2828
14.0k
      if (Reporter.getAnalyzerOptions().ShouldCrosscheckWithZ3) {
2829
        // If crosscheck is enabled, remove all visitors, add the refutation
2830
        // visitor and check again
2831
0
        R->clearVisitors();
2832
0
        R->addVisitor(std::make_unique<FalsePositiveRefutationBRVisitor>());
2833
2834
        // We don't overwrite the notes inserted by other visitors because the
2835
        // refutation manager does not add any new note to the path
2836
0
        generateVisitorsDiagnostics(R, BugPath->ErrorNode, BRC);
2837
0
      }
2838
2839
      // Check if the bug is still valid
2840
14.0k
      if (R->isValid())
2841
14.0k
        return PathDiagnosticBuilder(
2842
14.0k
            std::move(BRC), std::move(BugPath->BugPath), BugPath->Report,
2843
14.0k
            BugPath->ErrorNode, std::move(visitorNotes));
2844
14.0k
    }
2845
14.2k
  }
2846
2847
194
  return {};
2848
14.2k
}
2849
2850
std::unique_ptr<DiagnosticForConsumerMapTy>
2851
PathSensitiveBugReporter::generatePathDiagnostics(
2852
    ArrayRef<PathDiagnosticConsumer *> consumers,
2853
14.2k
    ArrayRef<PathSensitiveBugReport *> &bugReports) {
2854
14.2k
  assert(!bugReports.empty());
2855
2856
14.2k
  auto Out = std::make_unique<DiagnosticForConsumerMapTy>();
2857
2858
14.2k
  Optional<PathDiagnosticBuilder> PDB =
2859
14.2k
      PathDiagnosticBuilder::findValidReport(bugReports, *this);
2860
2861
14.2k
  if (PDB) {
2862
14.7k
    for (PathDiagnosticConsumer *PC : consumers) {
2863
14.7k
      if (std::unique_ptr<PathDiagnostic> PD = PDB->generate(PC)) {
2864
14.7k
        (*Out)[PC] = std::move(PD);
2865
14.7k
      }
2866
14.7k
    }
2867
14.0k
  }
2868
2869
14.2k
  return Out;
2870
14.2k
}
2871
2872
16.6k
void BugReporter::emitReport(std::unique_ptr<BugReport> R) {
2873
16.6k
  bool ValidSourceLoc = R->getLocation().isValid();
2874
16.6k
  assert(ValidSourceLoc);
2875
  // If we mess up in a release build, we'd still prefer to just drop the bug
2876
  // instead of trying to go on.
2877
16.6k
  if (!ValidSourceLoc)
2878
0
    return;
2879
2880
  // Compute the bug report's hash to determine its equivalence class.
2881
16.6k
  llvm::FoldingSetNodeID ID;
2882
16.6k
  R->Profile(ID);
2883
2884
  // Lookup the equivance class.  If there isn't one, create it.
2885
16.6k
  void *InsertPos;
2886
16.6k
  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
2887
2888
16.6k
  if (!EQ) {
2889
15.5k
    EQ = new BugReportEquivClass(std::move(R));
2890
15.5k
    EQClasses.InsertNode(EQ, InsertPos);
2891
15.5k
    EQClassesVector.push_back(EQ);
2892
15.5k
  } else
2893
1.18k
    EQ->AddReport(std::move(R));
2894
16.6k
}
2895
2896
15.4k
void PathSensitiveBugReporter::emitReport(std::unique_ptr<BugReport> R) {
2897
15.4k
  if (auto PR = dyn_cast<PathSensitiveBugReport>(R.get()))
2898
15.4k
    if (const ExplodedNode *E = PR->getErrorNode()) {
2899
      // An error node must either be a sink or have a tag, otherwise
2900
      // it could get reclaimed before the path diagnostic is created.
2901
15.4k
      assert((E->isSink() || E->getLocation().getTag()) &&
2902
15.4k
             "Error node must either be a sink or have a tag");
2903
2904
15.4k
      const AnalysisDeclContext *DeclCtx =
2905
15.4k
          E->getLocationContext()->getAnalysisDeclContext();
2906
      // The source of autosynthesized body can be handcrafted AST or a model
2907
      // file. The locations from handcrafted ASTs have no valid source
2908
      // locations and have to be discarded. Locations from model files should
2909
      // be preserved for processing and reporting.
2910
15.4k
      if (DeclCtx->isBodyAutosynthesized() &&
2911
3
          !DeclCtx->isBodyAutosynthesizedFromModelFile())
2912
3
        return;
2913
15.4k
    }
2914
2915
15.4k
  BugReporter::emitReport(std::move(R));
2916
15.4k
}
2917
2918
//===----------------------------------------------------------------------===//
2919
// Emitting reports in equivalence classes.
2920
//===----------------------------------------------------------------------===//
2921
2922
namespace {
2923
2924
struct FRIEC_WLItem {
2925
  const ExplodedNode *N;
2926
  ExplodedNode::const_succ_iterator I, E;
2927
2928
  FRIEC_WLItem(const ExplodedNode *n)
2929
18.8k
      : N(n), I(N->succ_begin()), E(N->succ_end()) {}
2930
};
2931
2932
} // namespace
2933
2934
BugReport *PathSensitiveBugReporter::findReportInEquivalenceClass(
2935
14.2k
    BugReportEquivClass &EQ, SmallVectorImpl<BugReport *> &bugReports) {
2936
  // If we don't need to suppress any of the nodes because they are
2937
  // post-dominated by a sink, simply add all the nodes in the equivalence class
2938
  // to 'Nodes'.  Any of the reports will serve as a "representative" report.
2939
14.2k
  assert(EQ.getReports().size() > 0);
2940
14.2k
  const BugType& BT = EQ.getReports()[0]->getBugType();
2941
14.2k
  if (!BT.isSuppressOnSink()) {
2942
13.5k
    BugReport *R = EQ.getReports()[0].get();
2943
14.6k
    for (auto &J : EQ.getReports()) {
2944
14.6k
      if (auto *PR = dyn_cast<PathSensitiveBugReport>(J.get())) {
2945
14.6k
        R = PR;
2946
14.6k
        bugReports.push_back(PR);
2947
14.6k
      }
2948
14.6k
    }
2949
13.5k
    return R;
2950
13.5k
  }
2951
2952
  // For bug reports that should be suppressed when all paths are post-dominated
2953
  // by a sink node, iterate through the reports in the equivalence class
2954
  // until we find one that isn't post-dominated (if one exists).  We use a
2955
  // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
2956
  // this as a recursive function, but we don't want to risk blowing out the
2957
  // stack for very long paths.
2958
720
  BugReport *exampleReport = nullptr;
2959
2960
776
  for (const auto &I: EQ.getReports()) {
2961
776
    auto *R = dyn_cast<PathSensitiveBugReport>(I.get());
2962
776
    if (!R)
2963
0
      continue;
2964
2965
776
    const ExplodedNode *errorNode = R->getErrorNode();
2966
776
    if (errorNode->isSink()) {
2967
0
      llvm_unreachable(
2968
0
           "BugType::isSuppressSink() should not be 'true' for sink end nodes");
2969
0
    }
2970
    // No successors?  By definition this nodes isn't post-dominated by a sink.
2971
776
    if (errorNode->succ_empty()) {
2972
11
      bugReports.push_back(R);
2973
11
      if (!exampleReport)
2974
11
        exampleReport = R;
2975
11
      continue;
2976
11
    }
2977
2978
    // See if we are in a no-return CFG block. If so, treat this similarly
2979
    // to being post-dominated by a sink. This works better when the analysis
2980
    // is incomplete and we have never reached the no-return function call(s)
2981
    // that we'd inevitably bump into on this path.
2982
765
    if (const CFGBlock *ErrorB = errorNode->getCFGBlock())
2983
474
      if (ErrorB->isInevitablySinking())
2984
23
        continue;
2985
2986
    // At this point we know that 'N' is not a sink and it has at least one
2987
    // successor.  Use a DFS worklist to find a non-sink end-of-path node.
2988
742
    using WLItem = FRIEC_WLItem;
2989
742
    using DFSWorkList = SmallVector<WLItem, 10>;
2990
2991
742
    llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
2992
2993
742
    DFSWorkList WL;
2994
742
    WL.push_back(errorNode);
2995
742
    Visited[errorNode] = 1;
2996
2997
21.5k
    while (!WL.empty()) {
2998
20.7k
      WLItem &WI = WL.back();
2999
20.7k
      assert(!WI.N->succ_empty());
3000
3001
22.7k
      for (; WI.I != WI.E; 
++WI.I1.95k
) {
3002
20.8k
        const ExplodedNode *Succ = *WI.I;
3003
        // End-of-path node?
3004
20.8k
        if (Succ->succ_empty()) {
3005
          // If we found an end-of-path node that is not a sink.
3006
768
          if (!Succ->isSink()) {
3007
722
            bugReports.push_back(R);
3008
722
            if (!exampleReport)
3009
679
              exampleReport = R;
3010
722
            WL.clear();
3011
722
            break;
3012
722
          }
3013
          // Found a sink?  Continue on to the next successor.
3014
46
          continue;
3015
46
        }
3016
        // Mark the successor as visited.  If it hasn't been explored,
3017
        // enqueue it to the DFS worklist.
3018
20.0k
        unsigned &mark = Visited[Succ];
3019
20.0k
        if (!mark) {
3020
18.1k
          mark = 1;
3021
18.1k
          WL.push_back(Succ);
3022
18.1k
          break;
3023
18.1k
        }
3024
20.0k
      }
3025
3026
      // The worklist may have been cleared at this point.  First
3027
      // check if it is empty before checking the last item.
3028
20.7k
      if (!WL.empty() && 
&WL.back() == &WI20.0k
)
3029
1.91k
        WL.pop_back();
3030
20.7k
    }
3031
742
  }
3032
3033
  // ExampleReport will be NULL if all the nodes in the equivalence class
3034
  // were post-dominated by sinks.
3035
720
  return exampleReport;
3036
720
}
3037
3038
15.5k
void BugReporter::FlushReport(BugReportEquivClass& EQ) {
3039
15.5k
  SmallVector<BugReport*, 10> bugReports;
3040
15.5k
  BugReport *report = findReportInEquivalenceClass(EQ, bugReports);
3041
15.5k
  if (!report)
3042
30
    return;
3043
3044
15.4k
  ArrayRef<PathDiagnosticConsumer*> Consumers = getPathDiagnosticConsumers();
3045
15.4k
  std::unique_ptr<DiagnosticForConsumerMapTy> Diagnostics =
3046
15.4k
      generateDiagnosticForConsumerMap(report, Consumers, bugReports);
3047
3048
16.0k
  for (auto &P : *Diagnostics) {
3049
16.0k
    PathDiagnosticConsumer *Consumer = P.first;
3050
16.0k
    std::unique_ptr<PathDiagnostic> &PD = P.second;
3051
3052
    // If the path is empty, generate a single step path with the location
3053
    // of the issue.
3054
16.0k
    if (PD->path.empty()) {
3055
14.1k
      PathDiagnosticLocation L = report->getLocation();
3056
14.1k
      auto piece = std::make_unique<PathDiagnosticEventPiece>(
3057
14.1k
        L, report->getDescription());
3058
14.1k
      for (SourceRange Range : report->getRanges())
3059
13.4k
        piece->addRange(Range);
3060
14.1k
      PD->setEndOfPath(std::move(piece));
3061
14.1k
    }
3062
3063
16.0k
    PathPieces &Pieces = PD->getMutablePieces();
3064
16.0k
    if (getAnalyzerOptions().ShouldDisplayNotesAsEvents) {
3065
      // For path diagnostic consumers that don't support extra notes,
3066
      // we may optionally convert those to path notes.
3067
2
      for (auto I = report->getNotes().rbegin(),
3068
4
           E = report->getNotes().rend(); I != E; 
++I2
) {
3069
2
        PathDiagnosticNotePiece *Piece = I->get();
3070
2
        auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>(
3071
2
          Piece->getLocation(), Piece->getString());
3072
2
        for (const auto &R: Piece->getRanges())
3073
2
          ConvertedPiece->addRange(R);
3074
3075
2
        Pieces.push_front(std::move(ConvertedPiece));
3076
2
      }
3077
16.0k
    } else {
3078
16.0k
      for (auto I = report->getNotes().rbegin(),
3079
16.2k
           E = report->getNotes().rend(); I != E; 
++I166
)
3080
166
        Pieces.push_front(*I);
3081
16.0k
    }
3082
3083
16.0k
    for (const auto &I : report->getFixits())
3084
13
      Pieces.back()->addFixit(I);
3085
3086
16.0k
    updateExecutedLinesWithDiagnosticPieces(*PD);
3087
16.0k
    Consumer->HandlePathDiagnostic(std::move(PD));
3088
16.0k
  }
3089
15.4k
}
3090
3091
/// Insert all lines participating in the function signature \p Signature
3092
/// into \p ExecutedLines.
3093
static void populateExecutedLinesWithFunctionSignature(
3094
    const Decl *Signature, const SourceManager &SM,
3095
82.1k
    FilesToLineNumsMap &ExecutedLines) {
3096
82.1k
  SourceRange SignatureSourceRange;
3097
82.1k
  const Stmt* Body = Signature->getBody();
3098
82.1k
  if (const auto FD = dyn_cast<FunctionDecl>(Signature)) {
3099
80.0k
    SignatureSourceRange = FD->getSourceRange();
3100
2.10k
  } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) {
3101
1.96k
    SignatureSourceRange = OD->getSourceRange();
3102
139
  } else {
3103
139
    return;
3104
139
  }
3105
81.9k
  SourceLocation Start = SignatureSourceRange.getBegin();
3106
81.3k
  SourceLocation End = Body ? Body->getSourceRange().getBegin()
3107
584
    : SignatureSourceRange.getEnd();
3108
81.9k
  if (!Start.isValid() || !End.isValid())
3109
0
    return;
3110
81.9k
  unsigned StartLine = SM.getExpansionLineNumber(Start);
3111
81.9k
  unsigned EndLine = SM.getExpansionLineNumber(End);
3112
3113
81.9k
  FileID FID = SM.getFileID(SM.getExpansionLoc(Start));
3114
166k
  for (unsigned Line = StartLine; Line <= EndLine; 
Line++84.0k
)
3115
84.0k
    ExecutedLines[FID].insert(Line);
3116
81.9k
}
3117
3118
static void populateExecutedLinesWithStmt(
3119
    const Stmt *S, const SourceManager &SM,
3120
2.88M
    FilesToLineNumsMap &ExecutedLines) {
3121
2.88M
  SourceLocation Loc = S->getSourceRange().getBegin();
3122
2.88M
  if (!Loc.isValid())
3123
6.73k
    return;
3124
2.88M
  SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc);
3125
2.88M
  FileID FID = SM.getFileID(ExpansionLoc);
3126
2.88M
  unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc);
3127
2.88M
  ExecutedLines[FID].insert(LineNo);
3128
2.88M
}
3129
3130
/// \return all executed lines including function signatures on the path
3131
/// starting from \p N.
3132
static std::unique_ptr<FilesToLineNumsMap>
3133
27.6k
findExecutedLines(const SourceManager &SM, const ExplodedNode *N) {
3134
27.6k
  auto ExecutedLines = std::make_unique<FilesToLineNumsMap>();
3135
3136
3.23M
  while (N) {
3137
3.20M
    if (N->getFirstPred() == nullptr) {
3138
      // First node: show signature of the entrance point.
3139
27.6k
      const Decl *D = N->getLocationContext()->getDecl();
3140
27.6k
      populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines);
3141
3.17M
    } else if (auto CE = N->getLocationAs<CallEnter>()) {
3142
      // Inlined function: show signature.
3143
54.4k
      const Decl* D = CE->getCalleeContext()->getDecl();
3144
54.4k
      populateExecutedLinesWithFunctionSignature(D, SM, *ExecutedLines);
3145
3.12M
    } else if (const Stmt *S = N->getStmtForDiagnostics()) {
3146
2.85M
      populateExecutedLinesWithStmt(S, SM, *ExecutedLines);
3147
3148
      // Show extra context for some parent kinds.
3149
2.85M
      const Stmt *P = N->getParentMap().getParent(S);
3150
3151
      // The path exploration can die before the node with the associated
3152
      // return statement is generated, but we do want to show the whole
3153
      // return.
3154
2.85M
      if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) {
3155
37.9k
        populateExecutedLinesWithStmt(RS, SM, *ExecutedLines);
3156
37.9k
        P = N->getParentMap().getParent(RS);
3157
37.9k
      }
3158
3159
2.85M
      if (P && 
(2.69M
isa<SwitchCase>(P)2.69M
||
isa<LabelStmt>(P)2.69M
))
3160
949
        populateExecutedLinesWithStmt(P, SM, *ExecutedLines);
3161
2.85M
    }
3162
3163
3.20M
    N = N->getFirstPred();
3164
3.20M
  }
3165
27.6k
  return ExecutedLines;
3166
27.6k
}
3167
3168
std::unique_ptr<DiagnosticForConsumerMapTy>
3169
BugReporter::generateDiagnosticForConsumerMap(
3170
    BugReport *exampleReport, ArrayRef<PathDiagnosticConsumer *> consumers,
3171
1.25k
    ArrayRef<BugReport *> bugReports) {
3172
1.25k
  auto *basicReport = cast<BasicBugReport>(exampleReport);
3173
1.25k
  auto Out = std::make_unique<DiagnosticForConsumerMapTy>();
3174
1.25k
  for (auto *Consumer : consumers)
3175
1.27k
    (*Out)[Consumer] = generateDiagnosticForBasicReport(basicReport);
3176
1.25k
  return Out;
3177
1.25k
}
3178
3179
static PathDiagnosticCallPiece *
3180
getFirstStackedCallToHeaderFile(PathDiagnosticCallPiece *CP,
3181
9
                                const SourceManager &SMgr) {
3182
9
  SourceLocation CallLoc = CP->callEnter.asLocation();
3183
3184
  // If the call is within a macro, don't do anything (for now).
3185
9
  if (CallLoc.isMacroID())
3186
3
    return nullptr;
3187
3188
6
  assert(AnalysisManager::isInCodeFile(CallLoc, SMgr) &&
3189
6
         "The call piece should not be in a header file.");
3190
3191
  // Check if CP represents a path through a function outside of the main file.
3192
6
  if (!AnalysisManager::isInCodeFile(CP->callEnterWithin.asLocation(), SMgr))
3193
2
    return CP;
3194
3195
4
  const PathPieces &Path = CP->path;
3196
4
  if (Path.empty())
3197
0
    return nullptr;
3198
3199
  // Check if the last piece in the callee path is a call to a function outside
3200
  // of the main file.
3201
4
  if (auto *CPInner = dyn_cast<PathDiagnosticCallPiece>(Path.back().get()))
3202
2
    return getFirstStackedCallToHeaderFile(CPInner, SMgr);
3203
3204
  // Otherwise, the last piece is in the main file.
3205
2
  return nullptr;
3206
2
}
3207
3208
14
static void resetDiagnosticLocationToMainFile(PathDiagnostic &PD) {
3209
14
  if (PD.path.empty())
3210
7
    return;
3211
3212
7
  PathDiagnosticPiece *LastP = PD.path.back().get();
3213
7
  assert(LastP);
3214
7
  const SourceManager &SMgr = LastP->getLocation().getManager();
3215
3216
  // We only need to check if the report ends inside headers, if the last piece
3217
  // is a call piece.
3218
7
  if (auto *CP = dyn_cast<PathDiagnosticCallPiece>(LastP)) {
3219
7
    CP = getFirstStackedCallToHeaderFile(CP, SMgr);
3220
7
    if (CP) {
3221
      // Mark the piece.
3222
2
       CP->setAsLastInMainSourceFile();
3223
3224
      // Update the path diagnostic message.
3225
2
      const auto *ND = dyn_cast<NamedDecl>(CP->getCallee());
3226
2
      if (ND) {
3227
2
        SmallString<200> buf;
3228
2
        llvm::raw_svector_ostream os(buf);
3229
2
        os << " (within a call to '" << ND->getDeclName() << "')";
3230
2
        PD.appendToDesc(os.str());
3231
2
      }
3232
3233
      // Reset the report containing declaration and location.
3234
2
      PD.setDeclWithIssue(CP->getCaller());
3235
2
      PD.setLocation(CP->getLocation());
3236
3237
2
      return;
3238
2
    }
3239
7
  }
3240
7
}
3241
3242
3243
3244
std::unique_ptr<DiagnosticForConsumerMapTy>
3245
PathSensitiveBugReporter::generateDiagnosticForConsumerMap(
3246
    BugReport *exampleReport, ArrayRef<PathDiagnosticConsumer *> consumers,
3247
14.2k
    ArrayRef<BugReport *> bugReports) {
3248
14.2k
  std::vector<BasicBugReport *> BasicBugReports;
3249
14.2k
  std::vector<PathSensitiveBugReport *> PathSensitiveBugReports;
3250
14.2k
  if (isa<BasicBugReport>(exampleReport))
3251
21
    return BugReporter::generateDiagnosticForConsumerMap(exampleReport,
3252
21
                                                         consumers, bugReports);
3253
3254
  // Generate the full path sensitive diagnostic, using the generation scheme
3255
  // specified by the PathDiagnosticConsumer. Note that we have to generate
3256
  // path diagnostics even for consumers which do not support paths, because
3257
  // the BugReporterVisitors may mark this bug as a false positive.
3258
14.2k
  assert(!bugReports.empty());
3259
14.2k
  MaxBugClassSize.updateMax(bugReports.size());
3260
3261
  // Avoid copying the whole array because there may be a lot of reports.
3262
14.2k
  ArrayRef<PathSensitiveBugReport *> convertedArrayOfReports(
3263
14.2k
      reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.begin()),
3264
14.2k
      reinterpret_cast<PathSensitiveBugReport *const *>(&*bugReports.end()));
3265
14.2k
  std::unique_ptr<DiagnosticForConsumerMapTy> Out = generatePathDiagnostics(
3266
14.2k
      consumers, convertedArrayOfReports);
3267
3268
14.2k
  if (Out->empty())
3269
203
    return Out;
3270
3271
14.0k
  MaxValidBugClassSize.updateMax(bugReports.size());
3272
3273
  // Examine the report and see if the last piece is in a header. Reset the
3274
  // report location to the last piece in the main source file.
3275
14.0k
  const AnalyzerOptions &Opts = getAnalyzerOptions();
3276
14.0k
  for (auto const &P : *Out)
3277
14.7k
    if (Opts.ShouldReportIssuesInMainSourceFile && 
!Opts.AnalyzeAll14
)
3278
14
      resetDiagnosticLocationToMainFile(*P.second);
3279
3280
14.0k
  return Out;
3281
14.0k
}
3282
3283
void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3284
                                  const CheckerBase *Checker, StringRef Name,
3285
                                  StringRef Category, StringRef Str,
3286
                                  PathDiagnosticLocation Loc,
3287
                                  ArrayRef<SourceRange> Ranges,
3288
565
                                  ArrayRef<FixItHint> Fixits) {
3289
565
  EmitBasicReport(DeclWithIssue, Checker->getCheckerName(), Name, Category, Str,
3290
565
                  Loc, Ranges, Fixits);
3291
565
}
3292
3293
void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3294
                                  CheckerNameRef CheckName,
3295
                                  StringRef name, StringRef category,
3296
                                  StringRef str, PathDiagnosticLocation Loc,
3297
                                  ArrayRef<SourceRange> Ranges,
3298
1.15k
                                  ArrayRef<FixItHint> Fixits) {
3299
  // 'BT' is owned by BugReporter.
3300
1.15k
  BugType *BT = getBugTypeForName(CheckName, name, category);
3301
1.15k
  auto R = std::make_unique<BasicBugReport>(*BT, str, Loc);
3302
1.15k
  R->setDeclWithIssue(DeclWithIssue);
3303
1.15k
  for (const auto &SR : Ranges)
3304
1.09k
    R->addRange(SR);
3305
1.15k
  for (const auto &FH : Fixits)
3306
10
    R->addFixItHint(FH);
3307
1.15k
  emitReport(std::move(R));
3308
1.15k
}
3309
3310
BugType *BugReporter::getBugTypeForName(CheckerNameRef CheckName,
3311
1.15k
                                        StringRef name, StringRef category) {
3312
1.15k
  SmallString<136> fullDesc;
3313
1.15k
  llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name
3314
1.15k
                                      << ":" << category;
3315
1.15k
  std::unique_ptr<BugType> &BT = StrBugTypes[fullDesc];
3316
1.15k
  if (!BT)
3317
737
    BT = std::make_unique<BugType>(CheckName, name, category);
3318
1.15k
  return BT.get();
3319
1.15k
}