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