Coverage Report

Created: 2020-02-18 08:44

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