Coverage Report

Created: 2019-07-24 05:18

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