clang  7.0.0svn
BugReporter.cpp
Go to the documentation of this file.
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 
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"
26 #include "clang/Analysis/CFG.h"
29 #include "clang/Basic/LLVM.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 
73 using namespace clang;
74 using namespace ento;
75 
76 #define DEBUG_TYPE "BugReporter"
77 
78 STATISTIC(MaxBugClassSize,
79  "The maximum number of bug reports in the same equivalence class");
80 STATISTIC(MaxValidBugClassSize,
81  "The maximum number of bug reports in the same equivalence class "
82  "where at least one report is valid (not suppressed)");
83 
85 
86 void BugReporterContext::anchor() {}
87 
88 //===----------------------------------------------------------------------===//
89 // Helper routines for walking the ExplodedGraph and fetching statements.
90 //===----------------------------------------------------------------------===//
91 
92 static 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 
100 static inline const Stmt*
102  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
103  return S;
104 
105  return GetPreviousStmt(N);
106 }
107 
108 //===----------------------------------------------------------------------===//
109 // Diagnostic cleanup.
110 //===----------------------------------------------------------------------===//
111 
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)
127 
128  if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)
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.
139 static 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()) {
153  removeRedundantMsgs(cast<PathDiagnosticCallPiece>(*piece).path);
154  break;
156  removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(*piece).subPieces);
157  break;
159  break;
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  }
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.
188 using 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.
194 static 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()) {
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  }
219  auto &macro = cast<PathDiagnosticMacroPiece>(*piece);
220  if (!removeUnneededCalls(macro.subPieces, R, LCM, IsInteresting))
221  continue;
222  containsSomethingInteresting = true;
223  break;
224  }
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  }
234  break;
235 
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.
248 static 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.
255 static void
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.
290  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
291  if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
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.
324  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
325  if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
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 
344 namespace {
345 
346 class NodeMapClosure : public BugReport::NodeResolver {
348 
349 public:
350  NodeMapClosure(InterExplodedGraphMap &m) : M(m) {}
351 
352  const ExplodedNode *getOriginalNode(const ExplodedNode *N) override {
353  return M.lookup(N);
354  }
355 };
356 
357 class PathDiagnosticBuilder : public BugReporterContext {
358  BugReport *R;
360  NodeMapClosure NMC;
361 
362 public:
363  const LocationContext *LC;
364 
365  PathDiagnosticBuilder(GRBugReporter &br,
366  BugReport *r, InterExplodedGraphMap &Backmap,
368  : BugReporterContext(br), R(r), PDC(pdc), NMC(Backmap),
369  LC(r->getErrorNode()->getLocationContext()) {}
370 
371  PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
372 
373  PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
374  const ExplodedNode *N);
375 
376  BugReport *getBugReport() { return R; }
377 
378  Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
379 
380  ParentMap& getParentMap() { return LC->getParentMap(); }
381 
382  const Stmt *getParent(const Stmt *S) {
383  return getParentMap().getParent(S);
384  }
385 
386  NodeMapClosure& getNodeResolver() override { return NMC; }
387 
389 
390  PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
392  }
393 
394  bool supportsLogicalOpControlFlow() const {
395  return PDC ? PDC->supportsLogicalOpControlFlow() : true;
396  }
397 };
398 
399 } // namespace
400 
402 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
403  if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N))
404  return PathDiagnosticLocation(S, getSourceManager(), LC);
405 
407  getSourceManager());
408 }
409 
411 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
412  const ExplodedNode *N) {
413  // Slow, but probably doesn't matter.
414  if (os.str().empty())
415  os << ' ';
416 
417  const PathDiagnosticLocation &Loc = ExecutionContinues(N);
418 
419  if (Loc.asStmt())
420  os << "Execution continues on line "
422  << '.';
423  else {
424  os << "Execution jumps to the end of the ";
425  const Decl *D = N->getLocationContext()->getDecl();
426  if (isa<ObjCMethodDecl>(D))
427  os << "method";
428  else if (isa<FunctionDecl>(D))
429  os << "function";
430  else {
431  assert(isa<BlockDecl>(D));
432  os << "anonymous block";
433  }
434  os << '.';
435  }
436 
437  return Loc;
438 }
439 
440 static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) {
441  if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
442  return PM.getParentIgnoreParens(S);
443 
444  const Stmt *Parent = PM.getParentIgnoreParens(S);
445  if (!Parent)
446  return nullptr;
447 
448  switch (Parent->getStmtClass()) {
449  case Stmt::ForStmtClass:
450  case Stmt::DoStmtClass:
451  case Stmt::WhileStmtClass:
452  case Stmt::ObjCForCollectionStmtClass:
453  case Stmt::CXXForRangeStmtClass:
454  return Parent;
455  default:
456  break;
457  }
458 
459  return nullptr;
460 }
461 
464  const LocationContext *LC, bool allowNestedContexts) {
465  if (!S)
466  return {};
467 
468  while (const Stmt *Parent = getEnclosingParent(S, P)) {
469  switch (Parent->getStmtClass()) {
470  case Stmt::BinaryOperatorClass: {
471  const auto *B = cast<BinaryOperator>(Parent);
472  if (B->isLogicalOp())
473  return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC);
474  break;
475  }
476  case Stmt::CompoundStmtClass:
477  case Stmt::StmtExprClass:
478  return PathDiagnosticLocation(S, SMgr, LC);
479  case Stmt::ChooseExprClass:
480  // Similar to '?' if we are referring to condition, just have the edge
481  // point to the entire choose expression.
482  if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S)
483  return PathDiagnosticLocation(Parent, SMgr, LC);
484  else
485  return PathDiagnosticLocation(S, SMgr, LC);
486  case Stmt::BinaryConditionalOperatorClass:
487  case Stmt::ConditionalOperatorClass:
488  // For '?', if we are referring to condition, just have the edge point
489  // to the entire '?' expression.
490  if (allowNestedContexts ||
491  cast<AbstractConditionalOperator>(Parent)->getCond() == S)
492  return PathDiagnosticLocation(Parent, SMgr, LC);
493  else
494  return PathDiagnosticLocation(S, SMgr, LC);
495  case Stmt::CXXForRangeStmtClass:
496  if (cast<CXXForRangeStmt>(Parent)->getBody() == S)
497  return PathDiagnosticLocation(S, SMgr, LC);
498  break;
499  case Stmt::DoStmtClass:
500  return PathDiagnosticLocation(S, SMgr, LC);
501  case Stmt::ForStmtClass:
502  if (cast<ForStmt>(Parent)->getBody() == S)
503  return PathDiagnosticLocation(S, SMgr, LC);
504  break;
505  case Stmt::IfStmtClass:
506  if (cast<IfStmt>(Parent)->getCond() != S)
507  return PathDiagnosticLocation(S, SMgr, LC);
508  break;
509  case Stmt::ObjCForCollectionStmtClass:
510  if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
511  return PathDiagnosticLocation(S, SMgr, LC);
512  break;
513  case Stmt::WhileStmtClass:
514  if (cast<WhileStmt>(Parent)->getCond() != S)
515  return PathDiagnosticLocation(S, SMgr, LC);
516  break;
517  default:
518  break;
519  }
520 
521  S = Parent;
522  }
523 
524  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
525 
526  return PathDiagnosticLocation(S, SMgr, LC);
527 }
528 
531  assert(S && "Null Stmt passed to getEnclosingStmtLocation");
532  return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC,
533  /*allowNestedContexts=*/false);
534 }
535 
536 //===----------------------------------------------------------------------===//
537 // "Visitors only" path diagnostic generation algorithm.
538 //===----------------------------------------------------------------------===//
540  PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N,
541  ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) {
542  // All path generation skips the very first node (the error node).
543  // This is because there is special handling for the end-of-path note.
544  N = N->getFirstPred();
545  if (!N)
546  return true;
547 
548  BugReport *R = PDB.getBugReport();
549  while (const ExplodedNode *Pred = N->getFirstPred()) {
550  for (auto &V : visitors)
551  // Visit all the node pairs, but throw the path pieces away.
552  V->VisitNode(N, Pred, PDB, *R);
553 
554  N = Pred;
555  }
556 
557  return R->isValid();
558 }
559 
560 //===----------------------------------------------------------------------===//
561 // "Minimal" path diagnostic generation algorithm.
562 //===----------------------------------------------------------------------===//
563 using StackDiagPair =
564  std::pair<PathDiagnosticCallPiece *, const ExplodedNode *>;
566 
568  StackDiagVector &CallStack) {
569  // If the piece contains a special message, add it to all the call
570  // pieces on the active stack.
571  if (auto *ep = dyn_cast<PathDiagnosticEventPiece>(&P)) {
572  if (ep->hasCallStackHint())
573  for (const auto &I : CallStack) {
574  PathDiagnosticCallPiece *CP = I.first;
575  const ExplodedNode *N = I.second;
576  std::string stackMsg = ep->getCallStackMessage(N);
577 
578  // The last message on the path to final bug is the most important
579  // one. Since we traverse the path backwards, do not add the message
580  // if one has been previously added.
581  if (!CP->hasCallStackMessage())
582  CP->setCallStackMessage(stackMsg);
583  }
584  }
585 }
586 
587 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
588 
589 /// Add path diagnostic for statement associated with node \p N
590 /// to diagnostics \p PD.
591 /// Precondition: location associated with \p N is a \c BlockEdge.
593  PathDiagnosticBuilder &PDB,
594  PathDiagnostic &PD) {
595  const LocationContext *LC = N->getLocationContext();
596  SourceManager& SMgr = PDB.getSourceManager();
597  BlockEdge BE = N->getLocation().castAs<BlockEdge>();
598  const CFGBlock *Src = BE.getSrc();
599  const CFGBlock *Dst = BE.getDst();
600  const Stmt *T = Src->getTerminator();
601  if (!T)
602  return;
603 
604  auto Start = PathDiagnosticLocation::createBegin(T, SMgr, LC);
605  switch (T->getStmtClass()) {
606  default:
607  break;
608 
609  case Stmt::GotoStmtClass:
610  case Stmt::IndirectGotoStmtClass: {
612 
613  if (!S)
614  break;
615 
616  std::string sbuf;
617  llvm::raw_string_ostream os(sbuf);
618  const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
619 
620  os << "Control jumps to line " << End.asLocation().getExpansionLineNumber();
621  PD.getActivePath().push_front(
622  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
623  break;
624  }
625 
626  case Stmt::SwitchStmtClass: {
627  // Figure out what case arm we took.
628  std::string sbuf;
629  llvm::raw_string_ostream os(sbuf);
630 
631  if (const Stmt *S = Dst->getLabel()) {
632  PathDiagnosticLocation End(S, SMgr, LC);
633 
634  switch (S->getStmtClass()) {
635  default:
636  os << "No cases match in the switch statement. "
637  "Control jumps to line "
639  break;
640  case Stmt::DefaultStmtClass:
641  os << "Control jumps to the 'default' case at line "
643  break;
644 
645  case Stmt::CaseStmtClass: {
646  os << "Control jumps to 'case ";
647  const auto *Case = cast<CaseStmt>(S);
648  const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
649 
650  // Determine if it is an enum.
651  bool GetRawInt = true;
652 
653  if (const auto *DR = dyn_cast<DeclRefExpr>(LHS)) {
654  // FIXME: Maybe this should be an assertion. Are there cases
655  // were it is not an EnumConstantDecl?
656  const auto *D = dyn_cast<EnumConstantDecl>(DR->getDecl());
657 
658  if (D) {
659  GetRawInt = false;
660  os << *D;
661  }
662  }
663 
664  if (GetRawInt)
665  os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
666 
667  os << ":' at line " << End.asLocation().getExpansionLineNumber();
668  break;
669  }
670  }
671  PD.getActivePath().push_front(
672  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
673  os.str()));
674  } else {
675  os << "'Default' branch taken. ";
676  const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
677  PD.getActivePath().push_front(
678  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
679  os.str()));
680  }
681 
682  break;
683  }
684 
685  case Stmt::BreakStmtClass:
686  case Stmt::ContinueStmtClass: {
687  std::string sbuf;
688  llvm::raw_string_ostream os(sbuf);
689  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
690  PD.getActivePath().push_front(
691  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
692  break;
693  }
694 
695  // Determine control-flow for ternary '?'.
696  case Stmt::BinaryConditionalOperatorClass:
697  case Stmt::ConditionalOperatorClass: {
698  std::string sbuf;
699  llvm::raw_string_ostream os(sbuf);
700  os << "'?' condition is ";
701 
702  if (*(Src->succ_begin() + 1) == Dst)
703  os << "false";
704  else
705  os << "true";
706 
707  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
708 
709  if (const Stmt *S = End.asStmt())
710  End = PDB.getEnclosingStmtLocation(S);
711 
712  PD.getActivePath().push_front(
713  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
714  break;
715  }
716 
717  // Determine control-flow for short-circuited '&&' and '||'.
718  case Stmt::BinaryOperatorClass: {
719  if (!PDB.supportsLogicalOpControlFlow())
720  break;
721 
722  const auto *B = cast<BinaryOperator>(T);
723  std::string sbuf;
724  llvm::raw_string_ostream os(sbuf);
725  os << "Left side of '";
726 
727  if (B->getOpcode() == BO_LAnd) {
728  os << "&&"
729  << "' is ";
730 
731  if (*(Src->succ_begin() + 1) == Dst) {
732  os << "false";
733  PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
734  PathDiagnosticLocation Start =
736  PD.getActivePath().push_front(
737  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
738  os.str()));
739  } else {
740  os << "true";
741  PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
742  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
743  PD.getActivePath().push_front(
744  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
745  os.str()));
746  }
747  } else {
748  assert(B->getOpcode() == BO_LOr);
749  os << "||"
750  << "' is ";
751 
752  if (*(Src->succ_begin() + 1) == Dst) {
753  os << "false";
754  PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
755  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
756  PD.getActivePath().push_front(
757  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
758  os.str()));
759  } else {
760  os << "true";
761  PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
762  PathDiagnosticLocation Start =
764  PD.getActivePath().push_front(
765  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
766  os.str()));
767  }
768  }
769 
770  break;
771  }
772 
773  case Stmt::DoStmtClass:
774  if (*(Src->succ_begin()) == Dst) {
775  std::string sbuf;
776  llvm::raw_string_ostream os(sbuf);
777 
778  os << "Loop condition is true. ";
779  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
780 
781  if (const Stmt *S = End.asStmt())
782  End = PDB.getEnclosingStmtLocation(S);
783 
784  PD.getActivePath().push_front(
785  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
786  os.str()));
787  } else {
788  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
789 
790  if (const Stmt *S = End.asStmt())
791  End = PDB.getEnclosingStmtLocation(S);
792 
793  PD.getActivePath().push_front(
794  std::make_shared<PathDiagnosticControlFlowPiece>(
795  Start, End, "Loop condition is false. Exiting loop"));
796  }
797  break;
798 
799  case Stmt::WhileStmtClass:
800  case Stmt::ForStmtClass:
801  if (*(Src->succ_begin() + 1) == Dst) {
802  std::string sbuf;
803  llvm::raw_string_ostream os(sbuf);
804 
805  os << "Loop condition is false. ";
806  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
807  if (const Stmt *S = End.asStmt())
808  End = PDB.getEnclosingStmtLocation(S);
809 
810  PD.getActivePath().push_front(
811  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
812  os.str()));
813  } else {
814  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
815  if (const Stmt *S = End.asStmt())
816  End = PDB.getEnclosingStmtLocation(S);
817 
818  PD.getActivePath().push_front(
819  std::make_shared<PathDiagnosticControlFlowPiece>(
820  Start, End, "Loop condition is true. Entering loop body"));
821  }
822 
823  break;
824 
825  case Stmt::IfStmtClass: {
826  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
827 
828  if (const Stmt *S = End.asStmt())
829  End = PDB.getEnclosingStmtLocation(S);
830 
831  if (*(Src->succ_begin() + 1) == Dst)
832  PD.getActivePath().push_front(
833  std::make_shared<PathDiagnosticControlFlowPiece>(
834  Start, End, "Taking false branch"));
835  else
836  PD.getActivePath().push_front(
837  std::make_shared<PathDiagnosticControlFlowPiece>(
838  Start, End, "Taking true branch"));
839 
840  break;
841  }
842  }
843 }
844 
845 /// Generate minimal diagnostics for node \p N, and write it into path
846 /// diagnostics \p PD.
848  PathDiagnosticBuilder &PDB,
849  PathDiagnostic &PD,
850  LocationContextMap &LCM,
851  StackDiagVector &CallStack) {
852  SourceManager &SMgr = PDB.getSourceManager();
853  ProgramPoint P = N->getLocation();
854 
855  if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
856  auto C = PathDiagnosticCallPiece::construct(N, *CE, SMgr);
857  // Record the mapping from call piece to LocationContext.
858  LCM[&C->path] = CE->getCalleeContext();
859  auto *P = C.get();
860  PD.getActivePath().push_front(std::move(C));
861  PD.pushActivePath(&P->path);
862  CallStack.push_back(StackDiagPair(P, N));
863  } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
864  // Flush all locations, and pop the active path.
865  bool VisitedEntireCall = PD.isWithinCall();
866  PD.popActivePath();
867 
868  // Either we just added a bunch of stuff to the top-level path, or
869  // we have a previous CallExitEnd. If the former, it means that the
870  // path terminated within a function call. We must then take the
871  // current contents of the active path and place it within
872  // a new PathDiagnosticCallPiece.
874  if (VisitedEntireCall) {
875  C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front().get());
876  } else {
877  const Decl *Caller = CE->getLocationContext()->getDecl();
879  // Record the mapping from call piece to LocationContext.
880  LCM[&C->path] = CE->getCalleeContext();
881  }
882 
883  C->setCallee(*CE, SMgr);
884  if (!CallStack.empty()) {
885  assert(CallStack.back().first == C);
886  CallStack.pop_back();
887  }
888  } else if (P.getKind() == ProgramPoint::BlockEdgeKind) {
890  }
891 }
892 
894  PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N,
895  LocationContextMap &LCM,
896  ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) {
897  const ExplodedNode *NextNode = N->pred_empty()
898  ? nullptr : *(N->pred_begin());
899  StackDiagVector CallStack;
900 
901  while (NextNode) {
902  N = NextNode;
903  PDB.LC = N->getLocationContext();
904  NextNode = N->getFirstPred();
905 
906  generateMinimalDiagnosticsForNode(N, PDB, PD, LCM, CallStack);
907 
908  if (NextNode) {
909  // Add diagnostic pieces from custom visitors.
910  BugReport *R = PDB.getBugReport();
911  llvm::FoldingSet<PathDiagnosticPiece> DeduplicationSet;
912  for (auto &V : visitors) {
913  if (auto p = V->VisitNode(N, NextNode, PDB, *R)) {
914  if (DeduplicationSet.GetOrInsertNode(p.get()) != p.get())
915  continue;
916 
917  updateStackPiecesWithMessage(*p, CallStack);
918  PD.getActivePath().push_front(std::move(p));
919  }
920  }
921  }
922  }
923 
924  if (!PDB.getBugReport()->isValid())
925  return false;
926 
927  // After constructing the full PathDiagnostic, do a pass over it to compact
928  // PathDiagnosticPieces that occur within a macro.
929  CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager());
930  return true;
931 }
932 
933 //===----------------------------------------------------------------------===//
934 // "Extensive" PathDiagnostic generation.
935 //===----------------------------------------------------------------------===//
936 
937 static bool IsControlFlowExpr(const Stmt *S) {
938  const auto *E = dyn_cast<Expr>(S);
939 
940  if (!E)
941  return false;
942 
943  E = E->IgnoreParenCasts();
944 
945  if (isa<AbstractConditionalOperator>(E))
946  return true;
947 
948  if (const auto *B = dyn_cast<BinaryOperator>(E))
949  if (B->isLogicalOp())
950  return true;
951 
952  return false;
953 }
954 
955 namespace {
956 
957 class ContextLocation : public PathDiagnosticLocation {
958  bool IsDead;
959 
960 public:
961  ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
962  : PathDiagnosticLocation(L), IsDead(isdead) {}
963 
964  void markDead() { IsDead = true; }
965  bool isDead() const { return IsDead; }
966 };
967 
968 } // namespace
969 
971  const LocationContext *LC,
972  bool firstCharOnly = false) {
973  if (const Stmt *S = L.asStmt()) {
974  const Stmt *Original = S;
975  while (true) {
976  // Adjust the location for some expressions that are best referenced
977  // by one of their subexpressions.
978  switch (S->getStmtClass()) {
979  default:
980  break;
981  case Stmt::ParenExprClass:
982  case Stmt::GenericSelectionExprClass:
983  S = cast<Expr>(S)->IgnoreParens();
984  firstCharOnly = true;
985  continue;
986  case Stmt::BinaryConditionalOperatorClass:
987  case Stmt::ConditionalOperatorClass:
988  S = cast<AbstractConditionalOperator>(S)->getCond();
989  firstCharOnly = true;
990  continue;
991  case Stmt::ChooseExprClass:
992  S = cast<ChooseExpr>(S)->getCond();
993  firstCharOnly = true;
994  continue;
995  case Stmt::BinaryOperatorClass:
996  S = cast<BinaryOperator>(S)->getLHS();
997  firstCharOnly = true;
998  continue;
999  }
1000  break;
1001  }
1002 
1003  if (S != Original)
1004  L = PathDiagnosticLocation(S, L.getManager(), LC);
1005  }
1006 
1007  if (firstCharOnly)
1009 
1010  return L;
1011 }
1012 
1013 namespace {
1014 
1015 class EdgeBuilder {
1016  std::vector<ContextLocation> CLocs;
1017 
1018  using iterator = std::vector<ContextLocation>::iterator;
1019 
1020  PathDiagnostic &PD;
1021  PathDiagnosticBuilder &PDB;
1022  PathDiagnosticLocation PrevLoc;
1023 
1024  bool IsConsumedExpr(const PathDiagnosticLocation &L);
1025 
1026  bool containsLocation(const PathDiagnosticLocation &Container,
1027  const PathDiagnosticLocation &Containee);
1028 
1029  PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
1030 
1031  void popLocation() {
1032  if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
1033  // For contexts, we only one the first character as the range.
1034  rawAddEdge(cleanUpLocation(CLocs.back(), PDB.LC, true));
1035  }
1036  CLocs.pop_back();
1037  }
1038 
1039 public:
1040  EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
1041  : PD(pd), PDB(pdb) {
1042  // If the PathDiagnostic already has pieces, add the enclosing statement
1043  // of the first piece as a context as well.
1044  if (!PD.path.empty()) {
1045  PrevLoc = (*PD.path.begin())->getLocation();
1046 
1047  if (const Stmt *S = PrevLoc.asStmt())
1048  addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1049  }
1050  }
1051 
1052  ~EdgeBuilder() {
1053  while (!CLocs.empty()) popLocation();
1054 
1055  // Finally, add an initial edge from the start location of the first
1056  // statement (if it doesn't already exist).
1058  PDB.LC,
1059  PDB.getSourceManager());
1060  if (L.isValid())
1061  rawAddEdge(L);
1062  }
1063 
1064  void flushLocations() {
1065  while (!CLocs.empty())
1066  popLocation();
1067  PrevLoc = PathDiagnosticLocation();
1068  }
1069 
1070  void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false,
1071  bool IsPostJump = false);
1072 
1073  void rawAddEdge(PathDiagnosticLocation NewLoc);
1074 
1075  void addContext(const Stmt *S);
1076  void addContext(const PathDiagnosticLocation &L);
1077  void addExtendedContext(const Stmt *S);
1078 };
1079 
1080 } // namespace
1081 
1083 EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
1084  if (const Stmt *S = L.asStmt()) {
1085  if (IsControlFlowExpr(S))
1086  return L;
1087 
1088  return PDB.getEnclosingStmtLocation(S);
1089  }
1090 
1091  return L;
1092 }
1093 
1094 bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
1095  const PathDiagnosticLocation &Containee) {
1096  if (Container == Containee)
1097  return true;
1098 
1099  if (Container.asDecl())
1100  return true;
1101 
1102  if (const Stmt *S = Containee.asStmt())
1103  if (const Stmt *ContainerS = Container.asStmt()) {
1104  while (S) {
1105  if (S == ContainerS)
1106  return true;
1107  S = PDB.getParent(S);
1108  }
1109  return false;
1110  }
1111 
1112  // Less accurate: compare using source ranges.
1113  SourceRange ContainerR = Container.asRange();
1114  SourceRange ContaineeR = Containee.asRange();
1115 
1116  SourceManager &SM = PDB.getSourceManager();
1117  SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
1118  SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
1119  SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
1120  SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
1121 
1122  unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
1123  unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
1124  unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
1125  unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
1126 
1127  assert(ContainerBegLine <= ContainerEndLine);
1128  assert(ContaineeBegLine <= ContaineeEndLine);
1129 
1130  return (ContainerBegLine <= ContaineeBegLine &&
1131  ContainerEndLine >= ContaineeEndLine &&
1132  (ContainerBegLine != ContaineeBegLine ||
1133  SM.getExpansionColumnNumber(ContainerRBeg) <=
1134  SM.getExpansionColumnNumber(ContaineeRBeg)) &&
1135  (ContainerEndLine != ContaineeEndLine ||
1136  SM.getExpansionColumnNumber(ContainerREnd) >=
1137  SM.getExpansionColumnNumber(ContaineeREnd)));
1138 }
1139 
1140 void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1141  if (!PrevLoc.isValid()) {
1142  PrevLoc = NewLoc;
1143  return;
1144  }
1145 
1146  const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc, PDB.LC);
1147  const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc, PDB.LC);
1148 
1149  if (PrevLocClean.asLocation().isInvalid()) {
1150  PrevLoc = NewLoc;
1151  return;
1152  }
1153 
1154  if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1155  return;
1156 
1157  // FIXME: Ignore intra-macro edges for now.
1158  if (NewLocClean.asLocation().getExpansionLoc() ==
1159  PrevLocClean.asLocation().getExpansionLoc())
1160  return;
1161 
1162  PD.getActivePath().push_front(
1163  std::make_shared<PathDiagnosticControlFlowPiece>(NewLocClean,
1164  PrevLocClean));
1165  PrevLoc = NewLoc;
1166 }
1167 
1168 void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd,
1169  bool IsPostJump) {
1170  if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1171  return;
1172 
1173  const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1174 
1175  while (!CLocs.empty()) {
1176  ContextLocation &TopContextLoc = CLocs.back();
1177 
1178  // Is the top location context the same as the one for the new location?
1179  if (TopContextLoc == CLoc) {
1180  if (alwaysAdd) {
1181  if (IsConsumedExpr(TopContextLoc))
1182  TopContextLoc.markDead();
1183 
1184  rawAddEdge(NewLoc);
1185  }
1186 
1187  if (IsPostJump)
1188  TopContextLoc.markDead();
1189  return;
1190  }
1191 
1192  if (containsLocation(TopContextLoc, CLoc)) {
1193  if (alwaysAdd) {
1194  rawAddEdge(NewLoc);
1195 
1196  if (IsConsumedExpr(CLoc)) {
1197  CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/true));
1198  return;
1199  }
1200  }
1201 
1202  CLocs.push_back(ContextLocation(CLoc, /*IsDead=*/IsPostJump));
1203  return;
1204  }
1205 
1206  // Context does not contain the location. Flush it.
1207  popLocation();
1208  }
1209 
1210  // If we reach here, there is no enclosing context. Just add the edge.
1211  rawAddEdge(NewLoc);
1212 }
1213 
1214 bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1215  if (const auto *X = dyn_cast_or_null<Expr>(L.asStmt()))
1216  return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1217 
1218  return false;
1219 }
1220 
1221 void EdgeBuilder::addExtendedContext(const Stmt *S) {
1222  if (!S)
1223  return;
1224 
1225  const Stmt *Parent = PDB.getParent(S);
1226  while (Parent) {
1227  if (isa<CompoundStmt>(Parent))
1228  Parent = PDB.getParent(Parent);
1229  else
1230  break;
1231  }
1232 
1233  if (Parent) {
1234  switch (Parent->getStmtClass()) {
1235  case Stmt::DoStmtClass:
1236  case Stmt::ObjCAtSynchronizedStmtClass:
1237  addContext(Parent);
1238  break;
1239  default:
1240  break;
1241  }
1242  }
1243 
1244  addContext(S);
1245 }
1246 
1247 void EdgeBuilder::addContext(const Stmt *S) {
1248  if (!S)
1249  return;
1250 
1251  PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC);
1252  addContext(L);
1253 }
1254 
1255 void EdgeBuilder::addContext(const PathDiagnosticLocation &L) {
1256  while (!CLocs.empty()) {
1257  const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1258 
1259  // Is the top location context the same as the one for the new location?
1260  if (TopContextLoc == L)
1261  return;
1262 
1263  if (containsLocation(TopContextLoc, L)) {
1264  CLocs.push_back(L);
1265  return;
1266  }
1267 
1268  // Context does not contain the location. Flush it.
1269  popLocation();
1270  }
1271 
1272  CLocs.push_back(L);
1273 }
1274 
1275 // Cone-of-influence: support the reverse propagation of "interesting" symbols
1276 // and values by tracing interesting calculations backwards through evaluated
1277 // expressions along a path. This is probably overly complicated, but the idea
1278 // is that if an expression computed an "interesting" value, the child
1279 // expressions are are also likely to be "interesting" as well (which then
1280 // propagates to the values they in turn compute). This reverse propagation
1281 // is needed to track interesting correlations across function call boundaries,
1282 // where formal arguments bind to actual arguments, etc. This is also needed
1283 // because the constraint solver sometimes simplifies certain symbolic values
1284 // into constants when appropriate, and this complicates reasoning about
1285 // interesting values.
1287 
1289  InterestingExprs &IE,
1290  const ProgramState *State,
1291  const Expr *Ex,
1292  const LocationContext *LCtx) {
1293  SVal V = State->getSVal(Ex, LCtx);
1294  if (!(R.isInteresting(V) || IE.count(Ex)))
1295  return;
1296 
1297  switch (Ex->getStmtClass()) {
1298  default:
1299  if (!isa<CastExpr>(Ex))
1300  break;
1301  // Fall through.
1302  case Stmt::BinaryOperatorClass:
1303  case Stmt::UnaryOperatorClass: {
1304  for (const Stmt *SubStmt : Ex->children()) {
1305  if (const auto *child = dyn_cast_or_null<Expr>(SubStmt)) {
1306  IE.insert(child);
1307  SVal ChildV = State->getSVal(child, LCtx);
1308  R.markInteresting(ChildV);
1309  }
1310  }
1311  break;
1312  }
1313  }
1314 
1315  R.markInteresting(V);
1316 }
1317 
1319  InterestingExprs &IE,
1320  const ProgramState *State,
1321  const LocationContext *CalleeCtx,
1322  const LocationContext *CallerCtx)
1323 {
1324  // FIXME: Handle non-CallExpr-based CallEvents.
1325  const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame();
1326  const Stmt *CallSite = Callee->getCallSite();
1327  if (const auto *CE = dyn_cast_or_null<CallExpr>(CallSite)) {
1328  if (const auto *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) {
1329  FunctionDecl::param_const_iterator PI = FD->param_begin(),
1330  PE = FD->param_end();
1331  CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1332  for (; AI != AE && PI != PE; ++AI, ++PI) {
1333  if (const Expr *ArgE = *AI) {
1334  if (const ParmVarDecl *PD = *PI) {
1335  Loc LV = State->getLValue(PD, CalleeCtx);
1336  if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV)))
1337  IE.insert(ArgE);
1338  }
1339  }
1340  }
1341  }
1342  }
1343 }
1344 
1345 //===----------------------------------------------------------------------===//
1346 // Functions for determining if a loop was executed 0 times.
1347 //===----------------------------------------------------------------------===//
1348 
1349 static bool isLoop(const Stmt *Term) {
1350  switch (Term->getStmtClass()) {
1351  case Stmt::ForStmtClass:
1352  case Stmt::WhileStmtClass:
1353  case Stmt::ObjCForCollectionStmtClass:
1354  case Stmt::CXXForRangeStmtClass:
1355  return true;
1356  default:
1357  // Note that we intentionally do not include do..while here.
1358  return false;
1359  }
1360 }
1361 
1362 static bool isJumpToFalseBranch(const BlockEdge *BE) {
1363  const CFGBlock *Src = BE->getSrc();
1364  assert(Src->succ_size() == 2);
1365  return (*(Src->succ_begin()+1) == BE->getDst());
1366 }
1367 
1368 /// Return true if the terminator is a loop and the destination is the
1369 /// false branch.
1370 static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
1371  if (!isLoop(Term))
1372  return false;
1373 
1374  // Did we take the false branch?
1375  return isJumpToFalseBranch(BE);
1376 }
1377 
1378 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
1379  while (SubS) {
1380  if (SubS == S)
1381  return true;
1382  SubS = PM.getParent(SubS);
1383  }
1384  return false;
1385 }
1386 
1387 static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term,
1388  const ExplodedNode *N) {
1389  while (N) {
1391  if (SP) {
1392  const Stmt *S = SP->getStmt();
1393  if (!isContainedByStmt(PM, Term, S))
1394  return S;
1395  }
1396  N = N->getFirstPred();
1397  }
1398  return nullptr;
1399 }
1400 
1401 static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) {
1402  const Stmt *LoopBody = nullptr;
1403  switch (Term->getStmtClass()) {
1404  case Stmt::CXXForRangeStmtClass: {
1405  const auto *FR = cast<CXXForRangeStmt>(Term);
1406  if (isContainedByStmt(PM, FR->getInc(), S))
1407  return true;
1408  if (isContainedByStmt(PM, FR->getLoopVarStmt(), S))
1409  return true;
1410  LoopBody = FR->getBody();
1411  break;
1412  }
1413  case Stmt::ForStmtClass: {
1414  const auto *FS = cast<ForStmt>(Term);
1415  if (isContainedByStmt(PM, FS->getInc(), S))
1416  return true;
1417  LoopBody = FS->getBody();
1418  break;
1419  }
1420  case Stmt::ObjCForCollectionStmtClass: {
1421  const auto *FC = cast<ObjCForCollectionStmt>(Term);
1422  LoopBody = FC->getBody();
1423  break;
1424  }
1425  case Stmt::WhileStmtClass:
1426  LoopBody = cast<WhileStmt>(Term)->getBody();
1427  break;
1428  default:
1429  return false;
1430  }
1431  return isContainedByStmt(PM, LoopBody, S);
1432 }
1433 
1434 /// Generate extensive diagnostics for statement associated with node \p N,
1435 /// and write it into \p PD.
1437  const ExplodedNode *N,
1438  PathDiagnosticBuilder &PDB,
1439  LocationContextMap &LCM,
1440  EdgeBuilder &EB,
1441  StackDiagVector &CallStack,
1442  PathDiagnostic &PD,
1443  InterestingExprs &IE) {
1444  const ExplodedNode *NextNode = N->getFirstPred();
1445  ProgramPoint P = N->getLocation();
1446  const SourceManager& SM = PDB.getSourceManager();
1447 
1448  if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1449  if (const Expr *Ex = PS->getStmtAs<Expr>())
1450  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1451  N->getState().get(), Ex,
1452  N->getLocationContext());
1453  return;
1454  } else if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1455  const Stmt *S = CE->getCalleeContext()->getCallSite();
1456  if (const auto *Ex = dyn_cast_or_null<Expr>(S)) {
1457  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1458  N->getState().get(), Ex,
1459  N->getLocationContext());
1460  }
1461 
1462  auto C = PathDiagnosticCallPiece::construct(N, *CE, SM);
1463  LCM[&C->path] = CE->getCalleeContext();
1464 
1465  EB.addEdge(C->callReturn, /*AlwaysAdd=*/true, /*IsPostJump=*/true);
1466  EB.flushLocations();
1467 
1468  auto *P = C.get();
1469  PD.getActivePath().push_front(std::move(C));
1470  PD.pushActivePath(&P->path);
1471  CallStack.push_back(StackDiagPair(P, N));
1472  return;
1473  } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1474  // Pop the call hierarchy if we are done walking the contents
1475  // of a function call.
1476 
1477  // Add an edge to the start of the function.
1478  const Decl *D = CE->getCalleeContext()->getDecl();
1481  EB.addEdge(pos);
1482 
1483  // Flush all locations, and pop the active path.
1484  bool VisitedEntireCall = PD.isWithinCall();
1485  EB.flushLocations();
1486  PD.popActivePath();
1487  PDB.LC = N->getLocationContext();
1488 
1489  // Either we just added a bunch of stuff to the top-level path, or
1490  // we have a previous CallExitEnd. If the former, it means that the
1491  // path terminated within a function call. We must then take the
1492  // current contents of the active path and place it within
1493  // a new PathDiagnosticCallPiece.
1495  if (VisitedEntireCall) {
1496  C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front().get());
1497  } else {
1498  const Decl *Caller = CE->getLocationContext()->getDecl();
1500  LCM[&C->path] = CE->getCalleeContext();
1501  }
1502 
1503  C->setCallee(*CE, SM);
1504  EB.addContext(C->getLocation());
1505 
1506  if (!CallStack.empty()) {
1507  assert(CallStack.back().first == C);
1508  CallStack.pop_back();
1509  }
1510  return;
1511  }
1512 
1513  // Note that is important that we update the LocationContext
1514  // after looking at CallExits. CallExit basically adds an
1515  // edge in the *caller*, so we don't want to update the LocationContext
1516  // too soon.
1517  PDB.LC = N->getLocationContext();
1518 
1519  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1520  // Does this represent entering a call? If so, look at propagating
1521  // interesting symbols across call boundaries.
1522  if (NextNode) {
1523  const LocationContext *CallerCtx = NextNode->getLocationContext();
1524  const LocationContext *CalleeCtx = PDB.LC;
1525  if (CallerCtx != CalleeCtx) {
1526  reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1527  N->getState().get(),
1528  CalleeCtx, CallerCtx);
1529  }
1530  }
1531 
1532  // Are we jumping to the head of a loop? Add a special diagnostic.
1533  if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1534  PathDiagnosticLocation L(Loop, SM, PDB.LC);
1535  const CompoundStmt *CS = nullptr;
1536 
1537  if (const auto *FS = dyn_cast<ForStmt>(Loop))
1538  CS = dyn_cast<CompoundStmt>(FS->getBody());
1539  else if (const auto *WS = dyn_cast<WhileStmt>(Loop))
1540  CS = dyn_cast<CompoundStmt>(WS->getBody());
1541 
1542  auto p = std::make_shared<PathDiagnosticEventPiece>(
1543  L, "Looping back to the head of the loop");
1544  p->setPrunable(true);
1545 
1546  EB.addEdge(p->getLocation(), true);
1547  PD.getActivePath().push_front(std::move(p));
1548 
1549  if (CS) {
1552  EB.addEdge(BL);
1553  }
1554  }
1555 
1556  const CFGBlock *BSrc = BE->getSrc();
1557  ParentMap &PM = PDB.getParentMap();
1558 
1559  if (const Stmt *Term = BSrc->getTerminator()) {
1560  // Are we jumping past the loop body without ever executing the
1561  // loop (because the condition was false)?
1562  if (isLoopJumpPastBody(Term, &*BE) &&
1563  !isInLoopBody(PM,
1564  getStmtBeforeCond(PM,
1565  BSrc->getTerminatorCondition(),
1566  N),
1567  Term)) {
1568  PathDiagnosticLocation L(Term, SM, PDB.LC);
1569  auto PE = std::make_shared<PathDiagnosticEventPiece>(
1570  L, "Loop body executed 0 times");
1571  PE->setPrunable(true);
1572 
1573  EB.addEdge(PE->getLocation(), true);
1574  PD.getActivePath().push_front(std::move(PE));
1575  }
1576 
1577  // In any case, add the terminator as the current statement
1578  // context for control edges.
1579  EB.addContext(Term);
1580  }
1581  } else if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
1582  Optional<CFGElement> First = BE->getFirstElement();
1583  if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) {
1584  const Stmt *stmt = S->getStmt();
1585  if (IsControlFlowExpr(stmt)) {
1586  // Add the proper context for '&&', '||', and '?'.
1587  EB.addContext(stmt);
1588  }
1589  else
1590  EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
1591  }
1592  }
1593 }
1594 
1595 //===----------------------------------------------------------------------===//
1596 // Top-level logic for generating extensive path diagnostics.
1597 //===----------------------------------------------------------------------===//
1598 
1600  PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N,
1601  LocationContextMap &LCM,
1602  ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) {
1603  EdgeBuilder EB(PD, PDB);
1604  StackDiagVector CallStack;
1605 
1606  InterestingExprs IE;
1607  const ExplodedNode *NextNode = N->pred_empty() ? nullptr : *(N->pred_begin());
1608  while (NextNode) {
1609  N = NextNode;
1610  NextNode = N->getFirstPred();
1611 
1612  generateExtensiveDiagnosticsForNode(N, PDB, LCM, EB, CallStack, PD, IE);
1613 
1614  if (!NextNode)
1615  continue;
1616 
1617  // Add pieces from custom visitors.
1618  BugReport *R = PDB.getBugReport();
1619  llvm::FoldingSet<PathDiagnosticPiece> DeduplicationSet;
1620  for (auto &V : visitors) {
1621  if (auto p = V->VisitNode(N, NextNode, PDB, *R)) {
1622  if (DeduplicationSet.GetOrInsertNode(p.get()) != p.get())
1623  continue;
1624 
1625  const PathDiagnosticLocation &Loc = p->getLocation();
1626  EB.addEdge(Loc, true);
1627  updateStackPiecesWithMessage(*p, CallStack);
1628  PD.getActivePath().push_front(std::move(p));
1629 
1630  if (const Stmt *S = Loc.asStmt())
1631  EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1632  }
1633  }
1634  }
1635 
1636  return PDB.getBugReport()->isValid();
1637 }
1638 
1639 /// \brief Adds a sanitized control-flow diagnostic edge to a path.
1640 static void addEdgeToPath(PathPieces &path,
1641  PathDiagnosticLocation &PrevLoc,
1642  PathDiagnosticLocation NewLoc,
1643  const LocationContext *LC) {
1644  if (!NewLoc.isValid())
1645  return;
1646 
1647  SourceLocation NewLocL = NewLoc.asLocation();
1648  if (NewLocL.isInvalid())
1649  return;
1650 
1651  if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) {
1652  PrevLoc = NewLoc;
1653  return;
1654  }
1655 
1656  // Ignore self-edges, which occur when there are multiple nodes at the same
1657  // statement.
1658  if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt())
1659  return;
1660 
1661  path.push_front(
1662  std::make_shared<PathDiagnosticControlFlowPiece>(NewLoc, PrevLoc));
1663  PrevLoc = NewLoc;
1664 }
1665 
1666 /// A customized wrapper for CFGBlock::getTerminatorCondition()
1667 /// which returns the element for ObjCForCollectionStmts.
1668 static const Stmt *getTerminatorCondition(const CFGBlock *B) {
1669  const Stmt *S = B->getTerminatorCondition();
1670  if (const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(S))
1671  return FS->getElement();
1672  return S;
1673 }
1674 
1675 static const char StrEnteringLoop[] = "Entering loop body";
1676 static const char StrLoopBodyZero[] = "Loop body executed 0 times";
1677 static const char StrLoopRangeEmpty[] =
1678  "Loop body skipped when range is empty";
1679 static const char StrLoopCollectionEmpty[] =
1680  "Loop body skipped when collection is empty";
1681 
1682 /// Generate alternate-extensive diagnostics for the node \p N,
1683 /// and write it into \p PD.
1685  PathDiagnostic &PD,
1686  PathDiagnosticLocation &PrevLoc,
1687  PathDiagnosticBuilder &PDB,
1688  LocationContextMap &LCM,
1689  StackDiagVector &CallStack,
1690  InterestingExprs &IE) {
1691  const ExplodedNode *NextNode = N->getFirstPred();
1692  ProgramPoint P = N->getLocation();
1693  const SourceManager& SM = PDB.getSourceManager();
1694 
1695  // Have we encountered an entrance to a call? It may be
1696  // the case that we have not encountered a matching
1697  // call exit before this point. This means that the path
1698  // terminated within the call itself.
1699  if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1700  // Add an edge to the start of the function.
1701  const StackFrameContext *CalleeLC = CE->getCalleeContext();
1702  const Decl *D = CalleeLC->getDecl();
1703  // Add the edge only when the callee has body. We jump to the beginning
1704  // of the *declaration*, however we expect it to be followed by the
1705  // body. This isn't the case for autosynthesized property accessors in
1706  // Objective-C. No need for a similar extra check for CallExit points
1707  // because the exit edge comes from a statement (i.e. return),
1708  // not from declaration.
1709  if (D->hasBody())
1710  addEdgeToPath(PD.getActivePath(), PrevLoc,
1711  PathDiagnosticLocation::createBegin(D, SM), CalleeLC);
1712 
1713  // Did we visit an entire call?
1714  bool VisitedEntireCall = PD.isWithinCall();
1715  PD.popActivePath();
1716 
1718  if (VisitedEntireCall) {
1719  PathDiagnosticPiece *P = PD.getActivePath().front().get();
1720  C = cast<PathDiagnosticCallPiece>(P);
1721  } else {
1722  const Decl *Caller = CE->getLocationContext()->getDecl();
1724 
1725  // Since we just transferred the path over to the call piece,
1726  // reset the mapping from active to location context.
1727  assert(PD.getActivePath().size() == 1 &&
1728  PD.getActivePath().front().get() == C);
1729  LCM[&PD.getActivePath()] = nullptr;
1730 
1731  // Record the location context mapping for the path within
1732  // the call.
1733  assert(LCM[&C->path] == nullptr ||
1734  LCM[&C->path] == CE->getCalleeContext());
1735  LCM[&C->path] = CE->getCalleeContext();
1736 
1737  // If this is the first item in the active path, record
1738  // the new mapping from active path to location context.
1739  const LocationContext *&NewLC = LCM[&PD.getActivePath()];
1740  if (!NewLC)
1741  NewLC = N->getLocationContext();
1742 
1743  PDB.LC = NewLC;
1744  }
1745  C->setCallee(*CE, SM);
1746 
1747  // Update the previous location in the active path.
1748  PrevLoc = C->getLocation();
1749 
1750  if (!CallStack.empty()) {
1751  assert(CallStack.back().first == C);
1752  CallStack.pop_back();
1753  }
1754  return;
1755  }
1756 
1757  // Query the location context here and the previous location
1758  // as processing CallEnter may change the active path.
1759  PDB.LC = N->getLocationContext();
1760 
1761  // Record the mapping from the active path to the location
1762  // context.
1763  assert(!LCM[&PD.getActivePath()] ||
1764  LCM[&PD.getActivePath()] == PDB.LC);
1765  LCM[&PD.getActivePath()] = PDB.LC;
1766 
1767  // Have we encountered an exit from a function call?
1768  if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1769  const Stmt *S = CE->getCalleeContext()->getCallSite();
1770  // Propagate the interesting symbols accordingly.
1771  if (const auto *Ex = dyn_cast_or_null<Expr>(S)) {
1772  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1773  N->getState().get(), Ex,
1774  N->getLocationContext());
1775  }
1776 
1777  // We are descending into a call (backwards). Construct
1778  // a new call piece to contain the path pieces for that call.
1779  auto C = PathDiagnosticCallPiece::construct(N, *CE, SM);
1780 
1781  // Record the location context for this call piece.
1782  LCM[&C->path] = CE->getCalleeContext();
1783 
1784  // Add the edge to the return site.
1785  addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC);
1786  auto *P = C.get();
1787  PD.getActivePath().push_front(std::move(C));
1788  PrevLoc.invalidate();
1789 
1790  // Make the contents of the call the active path for now.
1791  PD.pushActivePath(&P->path);
1792  CallStack.push_back(StackDiagPair(P, N));
1793  } else if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1794  // For expressions, make sure we propagate the
1795  // interesting symbols correctly.
1796  if (const Expr *Ex = PS->getStmtAs<Expr>())
1797  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1798  N->getState().get(), Ex,
1799  N->getLocationContext());
1800 
1801  // Add an edge. If this is an ObjCForCollectionStmt do
1802  // not add an edge here as it appears in the CFG both
1803  // as a terminator and as a terminator condition.
1804  if (!isa<ObjCForCollectionStmt>(PS->getStmt())) {
1806  PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC);
1807  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1808  }
1809  } else if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1810  // Does this represent entering a call? If so, look at propagating
1811  // interesting symbols across call boundaries.
1812  if (NextNode) {
1813  const LocationContext *CallerCtx = NextNode->getLocationContext();
1814  const LocationContext *CalleeCtx = PDB.LC;
1815  if (CallerCtx != CalleeCtx) {
1816  reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1817  N->getState().get(),
1818  CalleeCtx, CallerCtx);
1819  }
1820  }
1821 
1822  // Are we jumping to the head of a loop? Add a special diagnostic.
1823  if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1824  PathDiagnosticLocation L(Loop, SM, PDB.LC);
1825  const Stmt *Body = nullptr;
1826 
1827  if (const auto *FS = dyn_cast<ForStmt>(Loop))
1828  Body = FS->getBody();
1829  else if (const auto *WS = dyn_cast<WhileStmt>(Loop))
1830  Body = WS->getBody();
1831  else if (const auto *OFS = dyn_cast<ObjCForCollectionStmt>(Loop)) {
1832  Body = OFS->getBody();
1833  } else if (const auto *FRS = dyn_cast<CXXForRangeStmt>(Loop)) {
1834  Body = FRS->getBody();
1835  }
1836  // do-while statements are explicitly excluded here
1837 
1838  auto p = std::make_shared<PathDiagnosticEventPiece>(
1839  L, "Looping back to the head "
1840  "of the loop");
1841  p->setPrunable(true);
1842 
1843  addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1844  PD.getActivePath().push_front(std::move(p));
1845 
1846  if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Body)) {
1847  addEdgeToPath(PD.getActivePath(), PrevLoc,
1849  PDB.LC);
1850  }
1851  }
1852 
1853  const CFGBlock *BSrc = BE->getSrc();
1854  ParentMap &PM = PDB.getParentMap();
1855 
1856  if (const Stmt *Term = BSrc->getTerminator()) {
1857  // Are we jumping past the loop body without ever executing the
1858  // loop (because the condition was false)?
1859  if (isLoop(Term)) {
1860  const Stmt *TermCond = getTerminatorCondition(BSrc);
1861  bool IsInLoopBody =
1862  isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term);
1863 
1864  const char *str = nullptr;
1865 
1866  if (isJumpToFalseBranch(&*BE)) {
1867  if (!IsInLoopBody) {
1868  if (isa<ObjCForCollectionStmt>(Term)) {
1869  str = StrLoopCollectionEmpty;
1870  } else if (isa<CXXForRangeStmt>(Term)) {
1871  str = StrLoopRangeEmpty;
1872  } else {
1873  str = StrLoopBodyZero;
1874  }
1875  }
1876  } else {
1877  str = StrEnteringLoop;
1878  }
1879 
1880  if (str) {
1881  PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC);
1882  auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str);
1883  PE->setPrunable(true);
1884  addEdgeToPath(PD.getActivePath(), PrevLoc,
1885  PE->getLocation(), PDB.LC);
1886  PD.getActivePath().push_front(std::move(PE));
1887  }
1888  } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) ||
1889  isa<GotoStmt>(Term)) {
1890  PathDiagnosticLocation L(Term, SM, PDB.LC);
1891  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1892  }
1893  }
1894  }
1895 }
1896 
1898  PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N,
1899  LocationContextMap &LCM,
1900  ArrayRef<std::unique_ptr<BugReporterVisitor>> visitors) {
1901  BugReport *report = PDB.getBugReport();
1902  const SourceManager& SM = PDB.getSourceManager();
1903  StackDiagVector CallStack;
1904  InterestingExprs IE;
1905 
1906  PathDiagnosticLocation PrevLoc = PD.getLocation();
1907 
1908  const ExplodedNode *NextNode = N->getFirstPred();
1909  while (NextNode) {
1910  N = NextNode;
1911  NextNode = N->getFirstPred();
1912 
1914  N, PD, PrevLoc, PDB, LCM, CallStack, IE);
1915 
1916  if (!NextNode)
1917  continue;
1918 
1919  // Add pieces from custom visitors.
1920  llvm::FoldingSet<PathDiagnosticPiece> DeduplicationSet;
1921  for (auto &V : visitors) {
1922  if (auto p = V->VisitNode(N, NextNode, PDB, *report)) {
1923  if (DeduplicationSet.GetOrInsertNode(p.get()) != p.get())
1924  continue;
1925 
1926  addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1927  updateStackPiecesWithMessage(*p, CallStack);
1928  PD.getActivePath().push_front(std::move(p));
1929  }
1930  }
1931  }
1932 
1933  // Add an edge to the start of the function.
1934  // We'll prune it out later, but it helps make diagnostics more uniform.
1935  const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame();
1936  const Decl *D = CalleeLC->getDecl();
1937  addEdgeToPath(PD.getActivePath(), PrevLoc,
1939  CalleeLC);
1940 
1941  return report->isValid();
1942 }
1943 
1945  if (!L.isValid())
1946  return nullptr;
1947  return L.asStmt();
1948 }
1949 
1950 static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) {
1951  if (!S)
1952  return nullptr;
1953 
1954  while (true) {
1955  S = PM.getParentIgnoreParens(S);
1956 
1957  if (!S)
1958  break;
1959 
1960  if (isa<ExprWithCleanups>(S) ||
1961  isa<CXXBindTemporaryExpr>(S) ||
1962  isa<SubstNonTypeTemplateParmExpr>(S))
1963  continue;
1964 
1965  break;
1966  }
1967 
1968  return S;
1969 }
1970 
1971 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {
1972  switch (S->getStmtClass()) {
1973  case Stmt::BinaryOperatorClass: {
1974  const auto *BO = cast<BinaryOperator>(S);
1975  if (!BO->isLogicalOp())
1976  return false;
1977  return BO->getLHS() == Cond || BO->getRHS() == Cond;
1978  }
1979  case Stmt::IfStmtClass:
1980  return cast<IfStmt>(S)->getCond() == Cond;
1981  case Stmt::ForStmtClass:
1982  return cast<ForStmt>(S)->getCond() == Cond;
1983  case Stmt::WhileStmtClass:
1984  return cast<WhileStmt>(S)->getCond() == Cond;
1985  case Stmt::DoStmtClass:
1986  return cast<DoStmt>(S)->getCond() == Cond;
1987  case Stmt::ChooseExprClass:
1988  return cast<ChooseExpr>(S)->getCond() == Cond;
1989  case Stmt::IndirectGotoStmtClass:
1990  return cast<IndirectGotoStmt>(S)->getTarget() == Cond;
1991  case Stmt::SwitchStmtClass:
1992  return cast<SwitchStmt>(S)->getCond() == Cond;
1993  case Stmt::BinaryConditionalOperatorClass:
1994  return cast<BinaryConditionalOperator>(S)->getCond() == Cond;
1995  case Stmt::ConditionalOperatorClass: {
1996  const auto *CO = cast<ConditionalOperator>(S);
1997  return CO->getCond() == Cond ||
1998  CO->getLHS() == Cond ||
1999  CO->getRHS() == Cond;
2000  }
2001  case Stmt::ObjCForCollectionStmtClass:
2002  return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;
2003  case Stmt::CXXForRangeStmtClass: {
2004  const auto *FRS = cast<CXXForRangeStmt>(S);
2005  return FRS->getCond() == Cond || FRS->getRangeInit() == Cond;
2006  }
2007  default:
2008  return false;
2009  }
2010 }
2011 
2012 static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {
2013  if (const auto *FS = dyn_cast<ForStmt>(FL))
2014  return FS->getInc() == S || FS->getInit() == S;
2015  if (const auto *FRS = dyn_cast<CXXForRangeStmt>(FL))
2016  return FRS->getInc() == S || FRS->getRangeStmt() == S ||
2017  FRS->getLoopVarStmt() || FRS->getRangeInit() == S;
2018  return false;
2019 }
2020 
2022 
2023 /// Adds synthetic edges from top-level statements to their subexpressions.
2024 ///
2025 /// This avoids a "swoosh" effect, where an edge from a top-level statement A
2026 /// points to a sub-expression B.1 that's not at the start of B. In these cases,
2027 /// we'd like to see an edge from A to B, then another one from B to B.1.
2028 static void addContextEdges(PathPieces &pieces, SourceManager &SM,
2029  const ParentMap &PM, const LocationContext *LCtx) {
2030  PathPieces::iterator Prev = pieces.end();
2031  for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;
2032  Prev = I, ++I) {
2033  auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2034 
2035  if (!Piece)
2036  continue;
2037 
2038  PathDiagnosticLocation SrcLoc = Piece->getStartLocation();
2040 
2041  PathDiagnosticLocation NextSrcContext = SrcLoc;
2042  const Stmt *InnerStmt = nullptr;
2043  while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {
2044  SrcContexts.push_back(NextSrcContext);
2045  InnerStmt = NextSrcContext.asStmt();
2046  NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx,
2047  /*allowNested=*/true);
2048  }
2049 
2050  // Repeatedly split the edge as necessary.
2051  // This is important for nested logical expressions (||, &&, ?:) where we
2052  // want to show all the levels of context.
2053  while (true) {
2054  const Stmt *Dst = getLocStmt(Piece->getEndLocation());
2055 
2056  // We are looking at an edge. Is the destination within a larger
2057  // expression?
2058  PathDiagnosticLocation DstContext =
2059  getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true);
2060  if (!DstContext.isValid() || DstContext.asStmt() == Dst)
2061  break;
2062 
2063  // If the source is in the same context, we're already good.
2064  if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) !=
2065  SrcContexts.end())
2066  break;
2067 
2068  // Update the subexpression node to point to the context edge.
2069  Piece->setStartLocation(DstContext);
2070 
2071  // Try to extend the previous edge if it's at the same level as the source
2072  // context.
2073  if (Prev != E) {
2074  auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get());
2075 
2076  if (PrevPiece) {
2077  if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) {
2078  const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);
2079  if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) {
2080  PrevPiece->setEndLocation(DstContext);
2081  break;
2082  }
2083  }
2084  }
2085  }
2086 
2087  // Otherwise, split the current edge into a context edge and a
2088  // subexpression edge. Note that the context statement may itself have
2089  // context.
2090  auto P =
2091  std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext);
2092  Piece = P.get();
2093  I = pieces.insert(I, std::move(P));
2094  }
2095  }
2096 }
2097 
2098 /// \brief Move edges from a branch condition to a branch target
2099 /// when the condition is simple.
2100 ///
2101 /// This restructures some of the work of addContextEdges. That function
2102 /// creates edges this may destroy, but they work together to create a more
2103 /// aesthetically set of edges around branches. After the call to
2104 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from
2105 /// the branch to the branch condition, and (3) an edge from the branch
2106 /// condition to the branch target. We keep (1), but may wish to remove (2)
2107 /// and move the source of (3) to the branch if the branch condition is simple.
2108 static void simplifySimpleBranches(PathPieces &pieces) {
2109  for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {
2110  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2111 
2112  if (!PieceI)
2113  continue;
2114 
2115  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2116  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2117 
2118  if (!s1Start || !s1End)
2119  continue;
2120 
2121  PathPieces::iterator NextI = I; ++NextI;
2122  if (NextI == E)
2123  break;
2124 
2125  PathDiagnosticControlFlowPiece *PieceNextI = nullptr;
2126 
2127  while (true) {
2128  if (NextI == E)
2129  break;
2130 
2131  const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
2132  if (EV) {
2133  StringRef S = EV->getString();
2134  if (S == StrEnteringLoop || S == StrLoopBodyZero ||
2136  ++NextI;
2137  continue;
2138  }
2139  break;
2140  }
2141 
2142  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2143  break;
2144  }
2145 
2146  if (!PieceNextI)
2147  continue;
2148 
2149  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2150  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2151 
2152  if (!s2Start || !s2End || s1End != s2Start)
2153  continue;
2154 
2155  // We only perform this transformation for specific branch kinds.
2156  // We don't want to do this for do..while, for example.
2157  if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) ||
2158  isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) ||
2159  isa<CXXForRangeStmt>(s1Start)))
2160  continue;
2161 
2162  // Is s1End the branch condition?
2163  if (!isConditionForTerminator(s1Start, s1End))
2164  continue;
2165 
2166  // Perform the hoisting by eliminating (2) and changing the start
2167  // location of (3).
2168  PieceNextI->setStartLocation(PieceI->getStartLocation());
2169  I = pieces.erase(I);
2170  }
2171 }
2172 
2173 /// Returns the number of bytes in the given (character-based) SourceRange.
2174 ///
2175 /// If the locations in the range are not on the same line, returns None.
2176 ///
2177 /// Note that this does not do a precise user-visible character or column count.
2179  SourceRange Range) {
2180  SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),
2181  SM.getExpansionRange(Range.getEnd()).second);
2182 
2183  FileID FID = SM.getFileID(ExpansionRange.getBegin());
2184  if (FID != SM.getFileID(ExpansionRange.getEnd()))
2185  return None;
2186 
2187  bool Invalid;
2188  const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid);
2189  if (Invalid)
2190  return None;
2191 
2192  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
2193  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
2194  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
2195 
2196  // We're searching the raw bytes of the buffer here, which might include
2197  // escaped newlines and such. That's okay; we're trying to decide whether the
2198  // SourceRange is covering a large or small amount of space in the user's
2199  // editor.
2200  if (Snippet.find_first_of("\r\n") != StringRef::npos)
2201  return None;
2202 
2203  // This isn't Unicode-aware, but it doesn't need to be.
2204  return Snippet.size();
2205 }
2206 
2207 /// \sa getLengthOnSingleLine(SourceManager, SourceRange)
2209  const Stmt *S) {
2210  return getLengthOnSingleLine(SM, S->getSourceRange());
2211 }
2212 
2213 /// Eliminate two-edge cycles created by addContextEdges().
2214 ///
2215 /// Once all the context edges are in place, there are plenty of cases where
2216 /// there's a single edge from a top-level statement to a subexpression,
2217 /// followed by a single path note, and then a reverse edge to get back out to
2218 /// the top level. If the statement is simple enough, the subexpression edges
2219 /// just add noise and make it harder to understand what's going on.
2220 ///
2221 /// This function only removes edges in pairs, because removing only one edge
2222 /// might leave other edges dangling.
2223 ///
2224 /// This will not remove edges in more complicated situations:
2225 /// - if there is more than one "hop" leading to or from a subexpression.
2226 /// - if there is an inlined call between the edges instead of a single event.
2227 /// - if the whole statement is large enough that having subexpression arrows
2228 /// might be helpful.
2230  ParentMap &PM) {
2231  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
2232  // Pattern match the current piece and its successor.
2233  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2234 
2235  if (!PieceI) {
2236  ++I;
2237  continue;
2238  }
2239 
2240  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2241  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2242 
2243  PathPieces::iterator NextI = I; ++NextI;
2244  if (NextI == E)
2245  break;
2246 
2247  const auto *PieceNextI =
2248  dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2249 
2250  if (!PieceNextI) {
2251  if (isa<PathDiagnosticEventPiece>(NextI->get())) {
2252  ++NextI;
2253  if (NextI == E)
2254  break;
2255  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2256  }
2257 
2258  if (!PieceNextI) {
2259  ++I;
2260  continue;
2261  }
2262  }
2263 
2264  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2265  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2266 
2267  if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
2268  const size_t MAX_SHORT_LINE_LENGTH = 80;
2269  Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
2270  if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {
2271  Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
2272  if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
2273  Path.erase(I);
2274  I = Path.erase(NextI);
2275  continue;
2276  }
2277  }
2278  }
2279 
2280  ++I;
2281  }
2282 }
2283 
2284 /// \brief Return true if X is contained by Y.
2285 static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y) {
2286  while (X) {
2287  if (X == Y)
2288  return true;
2289  X = PM.getParent(X);
2290  }
2291  return false;
2292 }
2293 
2294 // Remove short edges on the same line less than 3 columns in difference.
2296  ParentMap &PM) {
2297  bool erased = false;
2298 
2299  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
2300  erased ? I : ++I) {
2301  erased = false;
2302 
2303  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2304 
2305  if (!PieceI)
2306  continue;
2307 
2308  const Stmt *start = getLocStmt(PieceI->getStartLocation());
2309  const Stmt *end = getLocStmt(PieceI->getEndLocation());
2310 
2311  if (!start || !end)
2312  continue;
2313 
2314  const Stmt *endParent = PM.getParent(end);
2315  if (!endParent)
2316  continue;
2317 
2318  if (isConditionForTerminator(end, endParent))
2319  continue;
2320 
2321  SourceLocation FirstLoc = start->getLocStart();
2322  SourceLocation SecondLoc = end->getLocStart();
2323 
2324  if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
2325  continue;
2326  if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
2327  std::swap(SecondLoc, FirstLoc);
2328 
2329  SourceRange EdgeRange(FirstLoc, SecondLoc);
2330  Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
2331 
2332  // If the statements are on different lines, continue.
2333  if (!ByteWidth)
2334  continue;
2335 
2336  const size_t MAX_PUNY_EDGE_LENGTH = 2;
2337  if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
2338  // FIXME: There are enough /bytes/ between the endpoints of the edge, but
2339  // there might not be enough /columns/. A proper user-visible column count
2340  // is probably too expensive, though.
2341  I = path.erase(I);
2342  erased = true;
2343  continue;
2344  }
2345  }
2346 }
2347 
2348 static void removeIdenticalEvents(PathPieces &path) {
2349  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
2350  const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());
2351 
2352  if (!PieceI)
2353  continue;
2354 
2355  PathPieces::iterator NextI = I; ++NextI;
2356  if (NextI == E)
2357  return;
2358 
2359  const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
2360 
2361  if (!PieceNextI)
2362  continue;
2363 
2364  // Erase the second piece if it has the same exact message text.
2365  if (PieceI->getString() == PieceNextI->getString()) {
2366  path.erase(NextI);
2367  }
2368  }
2369 }
2370 
2371 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
2372  OptimizedCallsSet &OCS,
2373  LocationContextMap &LCM) {
2374  bool hasChanges = false;
2375  const LocationContext *LC = LCM[&path];
2376  assert(LC);
2377  ParentMap &PM = LC->getParentMap();
2378 
2379  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
2380  // Optimize subpaths.
2381  if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {
2382  // Record the fact that a call has been optimized so we only do the
2383  // effort once.
2384  if (!OCS.count(CallI)) {
2385  while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
2386  OCS.insert(CallI);
2387  }
2388  ++I;
2389  continue;
2390  }
2391 
2392  // Pattern match the current piece and its successor.
2393  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2394 
2395  if (!PieceI) {
2396  ++I;
2397  continue;
2398  }
2399 
2400  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2401  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2402  const Stmt *level1 = getStmtParent(s1Start, PM);
2403  const Stmt *level2 = getStmtParent(s1End, PM);
2404 
2405  PathPieces::iterator NextI = I; ++NextI;
2406  if (NextI == E)
2407  break;
2408 
2409  const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2410 
2411  if (!PieceNextI) {
2412  ++I;
2413  continue;
2414  }
2415 
2416  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2417  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2418  const Stmt *level3 = getStmtParent(s2Start, PM);
2419  const Stmt *level4 = getStmtParent(s2End, PM);
2420 
2421  // Rule I.
2422  //
2423  // If we have two consecutive control edges whose end/begin locations
2424  // are at the same level (e.g. statements or top-level expressions within
2425  // a compound statement, or siblings share a single ancestor expression),
2426  // then merge them if they have no interesting intermediate event.
2427  //
2428  // For example:
2429  //
2430  // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
2431  // parent is '1'. Here 'x.y.z' represents the hierarchy of statements.
2432  //
2433  // NOTE: this will be limited later in cases where we add barriers
2434  // to prevent this optimization.
2435  if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
2436  PieceI->setEndLocation(PieceNextI->getEndLocation());
2437  path.erase(NextI);
2438  hasChanges = true;
2439  continue;
2440  }
2441 
2442  // Rule II.
2443  //
2444  // Eliminate edges between subexpressions and parent expressions
2445  // when the subexpression is consumed.
2446  //
2447  // NOTE: this will be limited later in cases where we add barriers
2448  // to prevent this optimization.
2449  if (s1End && s1End == s2Start && level2) {
2450  bool removeEdge = false;
2451  // Remove edges into the increment or initialization of a
2452  // loop that have no interleaving event. This means that
2453  // they aren't interesting.
2454  if (isIncrementOrInitInForLoop(s1End, level2))
2455  removeEdge = true;
2456  // Next only consider edges that are not anchored on
2457  // the condition of a terminator. This are intermediate edges
2458  // that we might want to trim.
2459  else if (!isConditionForTerminator(level2, s1End)) {
2460  // Trim edges on expressions that are consumed by
2461  // the parent expression.
2462  if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
2463  removeEdge = true;
2464  }
2465  // Trim edges where a lexical containment doesn't exist.
2466  // For example:
2467  //
2468  // X -> Y -> Z
2469  //
2470  // If 'Z' lexically contains Y (it is an ancestor) and
2471  // 'X' does not lexically contain Y (it is a descendant OR
2472  // it has no lexical relationship at all) then trim.
2473  //
2474  // This can eliminate edges where we dive into a subexpression
2475  // and then pop back out, etc.
2476  else if (s1Start && s2End &&
2477  lexicalContains(PM, s2Start, s2End) &&
2478  !lexicalContains(PM, s1End, s1Start)) {
2479  removeEdge = true;
2480  }
2481  // Trim edges from a subexpression back to the top level if the
2482  // subexpression is on a different line.
2483  //
2484  // A.1 -> A -> B
2485  // becomes
2486  // A.1 -> B
2487  //
2488  // These edges just look ugly and don't usually add anything.
2489  else if (s1Start && s2End &&
2490  lexicalContains(PM, s1Start, s1End)) {
2491  SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
2492  PieceI->getStartLocation().asLocation());
2493  if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
2494  removeEdge = true;
2495  }
2496  }
2497 
2498  if (removeEdge) {
2499  PieceI->setEndLocation(PieceNextI->getEndLocation());
2500  path.erase(NextI);
2501  hasChanges = true;
2502  continue;
2503  }
2504  }
2505 
2506  // Optimize edges for ObjC fast-enumeration loops.
2507  //
2508  // (X -> collection) -> (collection -> element)
2509  //
2510  // becomes:
2511  //
2512  // (X -> element)
2513  if (s1End == s2Start) {
2514  const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3);
2515  if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
2516  s2End == FS->getElement()) {
2517  PieceI->setEndLocation(PieceNextI->getEndLocation());
2518  path.erase(NextI);
2519  hasChanges = true;
2520  continue;
2521  }
2522  }
2523 
2524  // No changes at this index? Move to the next one.
2525  ++I;
2526  }
2527 
2528  if (!hasChanges) {
2529  // Adjust edges into subexpressions to make them more uniform
2530  // and aesthetically pleasing.
2531  addContextEdges(path, SM, PM, LC);
2532  // Remove "cyclical" edges that include one or more context edges.
2533  removeContextCycles(path, SM, PM);
2534  // Hoist edges originating from branch conditions to branches
2535  // for simple branches.
2536  simplifySimpleBranches(path);
2537  // Remove any puny edges left over after primary optimization pass.
2538  removePunyEdges(path, SM, PM);
2539  // Remove identical events.
2540  removeIdenticalEvents(path);
2541  }
2542 
2543  return hasChanges;
2544 }
2545 
2546 /// Drop the very first edge in a path, which should be a function entry edge.
2547 ///
2548 /// If the first edge is not a function entry edge (say, because the first
2549 /// statement had an invalid source location), this function does nothing.
2550 // FIXME: We should just generate invalid edges anyway and have the optimizer
2551 // deal with them.
2553  SourceManager &SM) {
2554  const auto *FirstEdge =
2555  dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());
2556  if (!FirstEdge)
2557  return;
2558 
2559  const Decl *D = LCM[&Path]->getDecl();
2561  if (FirstEdge->getStartLocation() != EntryLoc)
2562  return;
2563 
2564  Path.pop_front();
2565 }
2566 
2567 //===----------------------------------------------------------------------===//
2568 // Methods for BugType and subclasses.
2569 //===----------------------------------------------------------------------===//
2570 
2571 void BugType::anchor() {}
2572 
2574 
2575 void BuiltinBug::anchor() {}
2576 
2577 //===----------------------------------------------------------------------===//
2578 // Methods for BugReport and subclasses.
2579 //===----------------------------------------------------------------------===//
2580 
2581 void BugReport::NodeResolver::anchor() {}
2582 
2583 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) {
2584  if (!visitor)
2585  return;
2586 
2587  llvm::FoldingSetNodeID ID;
2588  visitor->Profile(ID);
2589  void *InsertPos;
2590 
2591  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos))
2592  return;
2593 
2594  CallbacksSet.InsertNode(visitor.get(), InsertPos);
2595  Callbacks.push_back(std::move(visitor));
2596  ++ConfigurationChangeToken;
2597 }
2598 
2600  while (!interestingSymbols.empty()) {
2601  popInterestingSymbolsAndRegions();
2602  }
2603 }
2604 
2606  if (DeclWithIssue)
2607  return DeclWithIssue;
2608 
2609  const ExplodedNode *N = getErrorNode();
2610  if (!N)
2611  return nullptr;
2612 
2613  const LocationContext *LC = N->getLocationContext();
2614  return LC->getCurrentStackFrame()->getDecl();
2615 }
2616 
2617 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2618  hash.AddPointer(&BT);
2619  hash.AddString(Description);
2620  PathDiagnosticLocation UL = getUniqueingLocation();
2621  if (UL.isValid()) {
2622  UL.Profile(hash);
2623  } else if (Location.isValid()) {
2624  Location.Profile(hash);
2625  } else {
2626  assert(ErrorNode);
2627  hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2628  }
2629 
2630  for (SourceRange range : Ranges) {
2631  if (!range.isValid())
2632  continue;
2633  hash.AddInteger(range.getBegin().getRawEncoding());
2634  hash.AddInteger(range.getEnd().getRawEncoding());
2635  }
2636 }
2637 
2639  if (!sym)
2640  return;
2641 
2642  // If the symbol wasn't already in our set, note a configuration change.
2643  if (getInterestingSymbols().insert(sym).second)
2644  ++ConfigurationChangeToken;
2645 
2646  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
2647  getInterestingRegions().insert(meta->getRegion());
2648 }
2649 
2651  if (!R)
2652  return;
2653 
2654  // If the base region wasn't already in our set, note a configuration change.
2655  R = R->getBaseRegion();
2656  if (getInterestingRegions().insert(R).second)
2657  ++ConfigurationChangeToken;
2658 
2659  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2660  getInterestingSymbols().insert(SR->getSymbol());
2661 }
2662 
2664  markInteresting(V.getAsRegion());
2665  markInteresting(V.getAsSymbol());
2666 }
2667 
2669  if (!LC)
2670  return;
2671  InterestingLocationContexts.insert(LC);
2672 }
2673 
2675  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2676 }
2677 
2679  if (!sym)
2680  return false;
2681  // We don't currently consider metadata symbols to be interesting
2682  // even if we know their region is interesting. Is that correct behavior?
2683  return getInterestingSymbols().count(sym);
2684 }
2685 
2687  if (!R)
2688  return false;
2689  R = R->getBaseRegion();
2690  bool b = getInterestingRegions().count(R);
2691  if (b)
2692  return true;
2693  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2694  return getInterestingSymbols().count(SR->getSymbol());
2695  return false;
2696 }
2697 
2699  if (!LC)
2700  return false;
2701  return InterestingLocationContexts.count(LC);
2702 }
2703 
2704 void BugReport::lazyInitializeInterestingSets() {
2705  if (interestingSymbols.empty()) {
2706  interestingSymbols.push_back(new Symbols());
2707  interestingRegions.push_back(new Regions());
2708  }
2709 }
2710 
2711 BugReport::Symbols &BugReport::getInterestingSymbols() {
2712  lazyInitializeInterestingSets();
2713  return *interestingSymbols.back();
2714 }
2715 
2716 BugReport::Regions &BugReport::getInterestingRegions() {
2717  lazyInitializeInterestingSets();
2718  return *interestingRegions.back();
2719 }
2720 
2721 void BugReport::pushInterestingSymbolsAndRegions() {
2722  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2723  interestingRegions.push_back(new Regions(getInterestingRegions()));
2724 }
2725 
2726 void BugReport::popInterestingSymbolsAndRegions() {
2727  delete interestingSymbols.pop_back_val();
2728  delete interestingRegions.pop_back_val();
2729 }
2730 
2731 const Stmt *BugReport::getStmt() const {
2732  if (!ErrorNode)
2733  return nullptr;
2734 
2735  ProgramPoint ProgP = ErrorNode->getLocation();
2736  const Stmt *S = nullptr;
2737 
2738  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2739  CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2740  if (BE->getBlock() == &Exit)
2741  S = GetPreviousStmt(ErrorNode);
2742  }
2743  if (!S)
2744  S = PathDiagnosticLocation::getStmt(ErrorNode);
2745 
2746  return S;
2747 }
2748 
2749 llvm::iterator_range<BugReport::ranges_iterator> BugReport::getRanges() {
2750  // If no custom ranges, add the range of the statement corresponding to
2751  // the error node.
2752  if (Ranges.empty()) {
2753  if (const auto *E = dyn_cast_or_null<Expr>(getStmt()))
2754  addRange(E->getSourceRange());
2755  else
2756  return llvm::make_range(ranges_iterator(), ranges_iterator());
2757  }
2758 
2759  // User-specified absence of range info.
2760  if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2761  return llvm::make_range(ranges_iterator(), ranges_iterator());
2762 
2763  return llvm::make_range(Ranges.begin(), Ranges.end());
2764 }
2765 
2767  if (ErrorNode) {
2768  assert(!Location.isValid() &&
2769  "Either Location or ErrorNode should be specified but not both.");
2770  return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2771  }
2772 
2773  assert(Location.isValid());
2774  return Location;
2775 }
2776 
2777 //===----------------------------------------------------------------------===//
2778 // Methods for BugReporter and subclasses.
2779 //===----------------------------------------------------------------------===//
2780 
2782 
2783 GRBugReporter::~GRBugReporter() = default;
2784 
2786 
2787 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2788 
2790 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2791 
2793  FlushReports();
2794 
2795  // Free the bug reports we are tracking.
2796  for (const auto I : EQClassesVector)
2797  delete I;
2798 }
2799 
2801  if (BugTypes.isEmpty())
2802  return;
2803 
2804  // First flush the warnings for each BugType. This may end up creating new
2805  // warnings and new BugTypes.
2806  // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2807  // Turn NSErrorChecker into a proper checker and remove this.
2808  SmallVector<const BugType *, 16> bugTypes(BugTypes.begin(), BugTypes.end());
2809  for (const auto I : bugTypes)
2810  const_cast<BugType*>(I)->FlushReports(*this);
2811 
2812  // We need to flush reports in deterministic order to ensure the order
2813  // of the reports is consistent between runs.
2814  for (const auto EQ : EQClassesVector)
2815  FlushReport(*EQ);
2816 
2817  // BugReporter owns and deletes only BugTypes created implicitly through
2818  // EmitBasicReport.
2819  // FIXME: There are leaks from checkers that assume that the BugTypes they
2820  // create will be destroyed by the BugReporter.
2821  llvm::DeleteContainerSeconds(StrBugTypes);
2822 
2823  // Remove all references to the BugType objects.
2824  BugTypes = F.getEmptySet();
2825 }
2826 
2827 //===----------------------------------------------------------------------===//
2828 // PathDiagnostics generation.
2829 //===----------------------------------------------------------------------===//
2830 
2831 namespace {
2832 
2833 /// A wrapper around a report graph, which contains only a single path, and its
2834 /// node maps.
2835 class ReportGraph {
2836 public:
2837  InterExplodedGraphMap BackMap;
2838  std::unique_ptr<ExplodedGraph> Graph;
2839  const ExplodedNode *ErrorNode;
2840  size_t Index;
2841 };
2842 
2843 /// A wrapper around a trimmed graph and its node maps.
2844 class TrimmedGraph {
2845  InterExplodedGraphMap InverseMap;
2846 
2847  using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;
2848 
2849  PriorityMapTy PriorityMap;
2850 
2851  using NodeIndexPair = std::pair<const ExplodedNode *, size_t>;
2852 
2853  SmallVector<NodeIndexPair, 32> ReportNodes;
2854 
2855  std::unique_ptr<ExplodedGraph> G;
2856 
2857  /// A helper class for sorting ExplodedNodes by priority.
2858  template <bool Descending>
2859  class PriorityCompare {
2860  const PriorityMapTy &PriorityMap;
2861 
2862  public:
2863  PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2864 
2865  bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2866  PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2867  PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2868  PriorityMapTy::const_iterator E = PriorityMap.end();
2869 
2870  if (LI == E)
2871  return Descending;
2872  if (RI == E)
2873  return !Descending;
2874 
2875  return Descending ? LI->second > RI->second
2876  : LI->second < RI->second;
2877  }
2878 
2879  bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2880  return (*this)(LHS.first, RHS.first);
2881  }
2882  };
2883 
2884 public:
2885  TrimmedGraph(const ExplodedGraph *OriginalGraph,
2887 
2888  bool popNextReportGraph(ReportGraph &GraphWrapper);
2889 };
2890 
2891 } // namespace
2892 
2893 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2895  // The trimmed graph is created in the body of the constructor to ensure
2896  // that the DenseMaps have been initialized already.
2897  InterExplodedGraphMap ForwardMap;
2898  G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
2899 
2900  // Find the (first) error node in the trimmed graph. We just need to consult
2901  // the node map which maps from nodes in the original graph to nodes
2902  // in the new graph.
2903  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2904 
2905  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2906  if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2907  ReportNodes.push_back(std::make_pair(NewNode, i));
2908  RemainingNodes.insert(NewNode);
2909  }
2910  }
2911 
2912  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2913 
2914  // Perform a forward BFS to find all the shortest paths.
2915  std::queue<const ExplodedNode *> WS;
2916 
2917  assert(G->num_roots() == 1);
2918  WS.push(*G->roots_begin());
2919  unsigned Priority = 0;
2920 
2921  while (!WS.empty()) {
2922  const ExplodedNode *Node = WS.front();
2923  WS.pop();
2924 
2925  PriorityMapTy::iterator PriorityEntry;
2926  bool IsNew;
2927  std::tie(PriorityEntry, IsNew) =
2928  PriorityMap.insert(std::make_pair(Node, Priority));
2929  ++Priority;
2930 
2931  if (!IsNew) {
2932  assert(PriorityEntry->second <= Priority);
2933  continue;
2934  }
2935 
2936  if (RemainingNodes.erase(Node))
2937  if (RemainingNodes.empty())
2938  break;
2939 
2941  E = Node->succ_end();
2942  I != E; ++I)
2943  WS.push(*I);
2944  }
2945 
2946  // Sort the error paths from longest to shortest.
2947  llvm::sort(ReportNodes.begin(), ReportNodes.end(),
2948  PriorityCompare<true>(PriorityMap));
2949 }
2950 
2951 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2952  if (ReportNodes.empty())
2953  return false;
2954 
2955  const ExplodedNode *OrigN;
2956  std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2957  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2958  "error node not accessible from root");
2959 
2960  // Create a new graph with a single path. This is the graph
2961  // that will be returned to the caller.
2962  auto GNew = llvm::make_unique<ExplodedGraph>();
2963  GraphWrapper.BackMap.clear();
2964 
2965  // Now walk from the error node up the BFS path, always taking the
2966  // predeccessor with the lowest number.
2967  ExplodedNode *Succ = nullptr;
2968  while (true) {
2969  // Create the equivalent node in the new graph with the same state
2970  // and location.
2971  ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
2972  OrigN->isSink());
2973 
2974  // Store the mapping to the original node.
2975  InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2976  assert(IMitr != InverseMap.end() && "No mapping to original node.");
2977  GraphWrapper.BackMap[NewN] = IMitr->second;
2978 
2979  // Link up the new node with the previous node.
2980  if (Succ)
2981  Succ->addPredecessor(NewN, *GNew);
2982  else
2983  GraphWrapper.ErrorNode = NewN;
2984 
2985  Succ = NewN;
2986 
2987  // Are we at the final node?
2988  if (OrigN->pred_empty()) {
2989  GNew->addRoot(NewN);
2990  break;
2991  }
2992 
2993  // Find the next predeccessor node. We choose the node that is marked
2994  // with the lowest BFS number.
2995  OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2996  PriorityCompare<false>(PriorityMap));
2997  }
2998 
2999  GraphWrapper.Graph = std::move(GNew);
3000 
3001  return true;
3002 }
3003 
3004 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
3005 /// and collapses PathDiagosticPieces that are expanded by macros.
3006 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
3007  using MacroStackTy =
3008  std::vector<
3009  std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>;
3010 
3011  using PiecesTy = std::vector<std::shared_ptr<PathDiagnosticPiece>>;
3012 
3013  MacroStackTy MacroStack;
3014  PiecesTy Pieces;
3015 
3016  for (PathPieces::const_iterator I = path.begin(), E = path.end();
3017  I != E; ++I) {
3018  const auto &piece = *I;
3019 
3020  // Recursively compact calls.
3021  if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {
3022  CompactPathDiagnostic(call->path, SM);
3023  }
3024 
3025  // Get the location of the PathDiagnosticPiece.
3026  const FullSourceLoc Loc = piece->getLocation().asLocation();
3027 
3028  // Determine the instantiation location, which is the location we group
3029  // related PathDiagnosticPieces.
3030  SourceLocation InstantiationLoc = Loc.isMacroID() ?
3031  SM.getExpansionLoc(Loc) :
3032  SourceLocation();
3033 
3034  if (Loc.isFileID()) {
3035  MacroStack.clear();
3036  Pieces.push_back(piece);
3037  continue;
3038  }
3039 
3040  assert(Loc.isMacroID());
3041 
3042  // Is the PathDiagnosticPiece within the same macro group?
3043  if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
3044  MacroStack.back().first->subPieces.push_back(piece);
3045  continue;
3046  }
3047 
3048  // We aren't in the same group. Are we descending into a new macro
3049  // or are part of an old one?
3050  std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;
3051 
3052  SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
3053  SM.getExpansionLoc(Loc) :
3054  SourceLocation();
3055 
3056  // Walk the entire macro stack.
3057  while (!MacroStack.empty()) {
3058  if (InstantiationLoc == MacroStack.back().second) {
3059  MacroGroup = MacroStack.back().first;
3060  break;
3061  }
3062 
3063  if (ParentInstantiationLoc == MacroStack.back().second) {
3064  MacroGroup = MacroStack.back().first;
3065  break;
3066  }
3067 
3068  MacroStack.pop_back();
3069  }
3070 
3071  if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
3072  // Create a new macro group and add it to the stack.
3073  auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(
3074  PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
3075 
3076  if (MacroGroup)
3077  MacroGroup->subPieces.push_back(NewGroup);
3078  else {
3079  assert(InstantiationLoc.isFileID());
3080  Pieces.push_back(NewGroup);
3081  }
3082 
3083  MacroGroup = NewGroup;
3084  MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
3085  }
3086 
3087  // Finally, add the PathDiagnosticPiece to the group.
3088  MacroGroup->subPieces.push_back(piece);
3089  }
3090 
3091  // Now take the pieces and construct a new PathDiagnostic.
3092  path.clear();
3093 
3094  path.insert(path.end(), Pieces.begin(), Pieces.end());
3095 }
3096 
3099  ArrayRef<BugReport *> &bugReports) {
3100  assert(!bugReports.empty());
3101 
3102  bool HasValid = false;
3103  bool HasInvalid = false;
3105  for (const auto I : bugReports) {
3106  if (I->isValid()) {
3107  HasValid = true;
3108  errorNodes.push_back(I->getErrorNode());
3109  } else {
3110  // Keep the errorNodes list in sync with the bugReports list.
3111  HasInvalid = true;
3112  errorNodes.push_back(nullptr);
3113  }
3114  }
3115 
3116  // If all the reports have been marked invalid by a previous path generation,
3117  // we're done.
3118  if (!HasValid)
3119  return false;
3120 
3121  using PathGenerationScheme = PathDiagnosticConsumer::PathGenerationScheme;
3122 
3123  PathGenerationScheme ActiveScheme = PC.getGenerationScheme();
3124 
3125  if (ActiveScheme == PathDiagnosticConsumer::Extensive) {
3126  AnalyzerOptions &options = getAnalyzerOptions();
3127  if (options.getBooleanOption("path-diagnostics-alternate", true)) {
3129  }
3130  }
3131 
3132  TrimmedGraph TrimG(&getGraph(), errorNodes);
3133  ReportGraph ErrorGraph;
3134 
3135  while (TrimG.popNextReportGraph(ErrorGraph)) {
3136  // Find the BugReport with the original location.
3137  assert(ErrorGraph.Index < bugReports.size());
3138  BugReport *R = bugReports[ErrorGraph.Index];
3139  assert(R && "No original report found for sliced graph.");
3140  assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
3141 
3142  // Start building the path diagnostic...
3143  PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
3144  const ExplodedNode *N = ErrorGraph.ErrorNode;
3145 
3146  // Register additional node visitors.
3147  R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
3148  R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
3149  R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
3150  R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
3151 
3152  BugReport::VisitorList visitors;
3153  unsigned origReportConfigToken, finalReportConfigToken;
3154  LocationContextMap LCM;
3155 
3156  // While generating diagnostics, it's possible the visitors will decide
3157  // new symbols and regions are interesting, or add other visitors based on
3158  // the information they find. If they do, we need to regenerate the path
3159  // based on our new report configuration.
3160  do {
3161  // Get a clean copy of all the visitors.
3162  for (BugReport::visitor_iterator I = R->visitor_begin(),
3163  E = R->visitor_end(); I != E; ++I)
3164  visitors.push_back((*I)->clone());
3165 
3166  // Clear out the active path from any previous work.
3167  PD.resetPath();
3168  origReportConfigToken = R->getConfigurationChangeToken();
3169 
3170  // Generate the very last diagnostic piece - the piece is visible before
3171  // the trace is expanded.
3172  std::unique_ptr<PathDiagnosticPiece> LastPiece;
3173  for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
3174  I != E; ++I) {
3175  if (std::unique_ptr<PathDiagnosticPiece> Piece =
3176  (*I)->getEndPath(PDB, N, *R)) {
3177  assert(!LastPiece &&
3178  "There can only be one final piece in a diagnostic.");
3179  LastPiece = std::move(Piece);
3180  }
3181  }
3182 
3183  if (ActiveScheme != PathDiagnosticConsumer::None) {
3184  if (!LastPiece)
3185  LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
3186  assert(LastPiece);
3187  PD.setEndOfPath(std::move(LastPiece));
3188  }
3189 
3190  // Make sure we get a clean location context map so we don't
3191  // hold onto old mappings.
3192  LCM.clear();
3193 
3194  switch (ActiveScheme) {
3196  GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3197  break;
3199  GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3200  break;
3202  GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors);
3203  break;
3205  GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors);
3206  break;
3207  }
3208 
3209  // Clean up the visitors we used.
3210  visitors.clear();
3211 
3212  // Did anything change while generating this path?
3213  finalReportConfigToken = R->getConfigurationChangeToken();
3214  } while (finalReportConfigToken != origReportConfigToken);
3215 
3216  if (!R->isValid())
3217  continue;
3218 
3219  // Finally, prune the diagnostic path of uninteresting stuff.
3220  if (!PD.path.empty()) {
3221  if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) {
3222  bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);
3223  assert(stillHasNotes);
3224  (void)stillHasNotes;
3225  }
3226 
3227  // Redirect all call pieces to have valid locations.
3230 
3231  if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) {
3233 
3234  // Reduce the number of edges from a very conservative set
3235  // to an aesthetically pleasing subset that conveys the
3236  // necessary information.
3237  OptimizedCallsSet OCS;
3238  while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {}
3239 
3240  // Drop the very first function-entry edge. It's not really necessary
3241  // for top-level functions.
3243  }
3244 
3245  // Remove messages that are basically the same, and edges that may not
3246  // make sense.
3247  // We have to do this after edge optimization in the Extensive mode.
3250  }
3251 
3252  // We found a report and didn't suppress it.
3253  return true;
3254  }
3255 
3256  // We suppressed all the reports in this equivalence class.
3257  assert(!HasInvalid && "Inconsistent suppression");
3258  (void)HasInvalid;
3259  return false;
3260 }
3261 
3263  BugTypes = F.add(BugTypes, BT);
3264 }
3265 
3266 void BugReporter::emitReport(std::unique_ptr<BugReport> R) {
3267  if (const ExplodedNode *E = R->getErrorNode()) {
3268  // An error node must either be a sink or have a tag, otherwise
3269  // it could get reclaimed before the path diagnostic is created.
3270  assert((E->isSink() || E->getLocation().getTag()) &&
3271  "Error node must either be a sink or have a tag");
3272 
3273  const AnalysisDeclContext *DeclCtx =
3274  E->getLocationContext()->getAnalysisDeclContext();
3275  // The source of autosynthesized body can be handcrafted AST or a model
3276  // file. The locations from handcrafted ASTs have no valid source locations
3277  // and have to be discarded. Locations from model files should be preserved
3278  // for processing and reporting.
3279  if (DeclCtx->isBodyAutosynthesized() &&
3281  return;
3282  }
3283 
3284  bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid();
3285  assert(ValidSourceLoc);
3286  // If we mess up in a release build, we'd still prefer to just drop the bug
3287  // instead of trying to go on.
3288  if (!ValidSourceLoc)
3289  return;
3290 
3291  // Compute the bug report's hash to determine its equivalence class.
3292  llvm::FoldingSetNodeID ID;
3293  R->Profile(ID);
3294 
3295  // Lookup the equivance class. If there isn't one, create it.
3296  BugType& BT = R->getBugType();
3297  Register(&BT);
3298  void *InsertPos;
3299  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
3300 
3301  if (!EQ) {
3302  EQ = new BugReportEquivClass(std::move(R));
3303  EQClasses.InsertNode(EQ, InsertPos);
3304  EQClassesVector.push_back(EQ);
3305  } else
3306  EQ->AddReport(std::move(R));
3307 }
3308 
3309 //===----------------------------------------------------------------------===//
3310 // Emitting reports in equivalence classes.
3311 //===----------------------------------------------------------------------===//
3312 
3313 namespace {
3314 
3315 struct FRIEC_WLItem {
3316  const ExplodedNode *N;
3318 
3319  FRIEC_WLItem(const ExplodedNode *n)
3320  : N(n), I(N->succ_begin()), E(N->succ_end()) {}
3321 };
3322 
3323 } // namespace
3324 
3325 static const CFGBlock *findBlockForNode(const ExplodedNode *N) {
3326  ProgramPoint P = N->getLocation();
3327  if (auto BEP = P.getAs<BlockEntrance>())
3328  return BEP->getBlock();
3329 
3330  // Find the node's current statement in the CFG.
3331  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
3333  ->getCFGStmtMap()->getBlock(S);
3334 
3335  return nullptr;
3336 }
3337 
3338 // Returns true if by simply looking at the block, we can be sure that it
3339 // results in a sink during analysis. This is useful to know when the analysis
3340 // was interrupted, and we try to figure out if it would sink eventually.
3341 // There may be many more reasons why a sink would appear during analysis
3342 // (eg. checkers may generate sinks arbitrarily), but here we only consider
3343 // sinks that would be obvious by looking at the CFG.
3344 static bool isImmediateSinkBlock(const CFGBlock *Blk) {
3345  if (Blk->hasNoReturnElement())
3346  return true;
3347 
3348  // FIXME: Throw-expressions are currently generating sinks during analysis:
3349  // they're not supported yet, and also often used for actually terminating
3350  // the program. So we should treat them as sinks in this analysis as well,
3351  // at least for now, but once we have better support for exceptions,
3352  // we'd need to carefully handle the case when the throw is being
3353  // immediately caught.
3354  if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) {
3355  if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
3356  if (isa<CXXThrowExpr>(StmtElm->getStmt()))
3357  return true;
3358  return false;
3359  }))
3360  return true;
3361 
3362  return false;
3363 }
3364 
3365 // Returns true if by looking at the CFG surrounding the node's program
3366 // point, we can be sure that any analysis starting from this point would
3367 // eventually end with a sink. We scan the child CFG blocks in a depth-first
3368 // manner and see if all paths eventually end up in an immediate sink block.
3369 static bool isInevitablySinking(const ExplodedNode *N) {
3370  const CFG &Cfg = N->getCFG();
3371 
3372  const CFGBlock *StartBlk = findBlockForNode(N);
3373  if (!StartBlk)
3374  return false;
3375  if (isImmediateSinkBlock(StartBlk))
3376  return true;
3377 
3379  llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
3380 
3381  DFSWorkList.push_back(StartBlk);
3382  while (!DFSWorkList.empty()) {
3383  const CFGBlock *Blk = DFSWorkList.back();
3384  DFSWorkList.pop_back();
3385  Visited.insert(Blk);
3386 
3387  for (const auto &Succ : Blk->succs()) {
3388  if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
3389  if (SuccBlk == &Cfg.getExit()) {
3390  // If at least one path reaches the CFG exit, it means that control is
3391  // returned to the caller. For now, say that we are not sure what
3392  // happens next. If necessary, this can be improved to analyze
3393  // the parent StackFrameContext's call site in a similar manner.
3394  return false;
3395  }
3396 
3397  if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {
3398  // If the block has reachable child blocks that aren't no-return,
3399  // add them to the worklist.
3400  DFSWorkList.push_back(SuccBlk);
3401  }
3402  }
3403  }
3404  }
3405 
3406  // Nothing reached the exit. It can only mean one thing: there's no return.
3407  return true;
3408 }
3409 
3410 static BugReport *
3412  SmallVectorImpl<BugReport*> &bugReports) {
3413  BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
3414  assert(I != E);
3415  BugType& BT = I->getBugType();
3416 
3417  // If we don't need to suppress any of the nodes because they are
3418  // post-dominated by a sink, simply add all the nodes in the equivalence class
3419  // to 'Nodes'. Any of the reports will serve as a "representative" report.
3420  if (!BT.isSuppressOnSink()) {
3421  BugReport *R = &*I;
3422  for (auto &I : EQ) {
3423  const ExplodedNode *N = I.getErrorNode();
3424  if (N) {
3425  R = &I;
3426  bugReports.push_back(R);
3427  }
3428  }
3429  return R;
3430  }
3431 
3432  // For bug reports that should be suppressed when all paths are post-dominated
3433  // by a sink node, iterate through the reports in the equivalence class
3434  // until we find one that isn't post-dominated (if one exists). We use a
3435  // DFS traversal of the ExplodedGraph to find a non-sink node. We could write
3436  // this as a recursive function, but we don't want to risk blowing out the
3437  // stack for very long paths.
3438  BugReport *exampleReport = nullptr;
3439 
3440  for (; I != E; ++I) {
3441  const ExplodedNode *errorNode = I->getErrorNode();
3442 
3443  if (!errorNode)
3444  continue;
3445  if (errorNode->isSink()) {
3446  llvm_unreachable(
3447  "BugType::isSuppressSink() should not be 'true' for sink end nodes");
3448  }
3449  // No successors? By definition this nodes isn't post-dominated by a sink.
3450  if (errorNode->succ_empty()) {
3451  bugReports.push_back(&*I);
3452  if (!exampleReport)
3453  exampleReport = &*I;
3454  continue;
3455  }
3456 
3457  // See if we are in a no-return CFG block. If so, treat this similarly
3458  // to being post-dominated by a sink. This works better when the analysis
3459  // is incomplete and we have never reached the no-return function call(s)
3460  // that we'd inevitably bump into on this path.
3461  if (isInevitablySinking(errorNode))
3462  continue;
3463 
3464  // At this point we know that 'N' is not a sink and it has at least one
3465  // successor. Use a DFS worklist to find a non-sink end-of-path node.
3466  using WLItem = FRIEC_WLItem;
3467  using DFSWorkList = SmallVector<WLItem, 10>;
3468 
3469  llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
3470 
3471  DFSWorkList WL;
3472  WL.push_back(errorNode);
3473  Visited[errorNode] = 1;
3474 
3475  while (!WL.empty()) {
3476  WLItem &WI = WL.back();
3477  assert(!WI.N->succ_empty());
3478 
3479  for (; WI.I != WI.E; ++WI.I) {
3480  const ExplodedNode *Succ = *WI.I;
3481  // End-of-path node?
3482  if (Succ->succ_empty()) {
3483  // If we found an end-of-path node that is not a sink.
3484  if (!Succ->isSink()) {
3485  bugReports.push_back(&*I);
3486  if (!exampleReport)
3487  exampleReport = &*I;
3488  WL.clear();
3489  break;
3490  }
3491  // Found a sink? Continue on to the next successor.
3492  continue;
3493  }
3494  // Mark the successor as visited. If it hasn't been explored,
3495  // enqueue it to the DFS worklist.
3496  unsigned &mark = Visited[Succ];
3497  if (!mark) {
3498  mark = 1;
3499  WL.push_back(Succ);
3500  break;
3501  }
3502  }
3503 
3504  // The worklist may have been cleared at this point. First
3505  // check if it is empty before checking the last item.
3506  if (!WL.empty() && &WL.back() == &WI)
3507  WL.pop_back();
3508  }
3509  }
3510 
3511  // ExampleReport will be NULL if all the nodes in the equivalence class
3512  // were post-dominated by sinks.
3513  return exampleReport;
3514 }
3515 
3516 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
3517  SmallVector<BugReport*, 10> bugReports;
3518  BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
3519  if (exampleReport) {
3520  for (PathDiagnosticConsumer *PDC : getPathDiagnosticConsumers()) {
3521  FlushReport(exampleReport, *PDC, bugReports);
3522  }
3523  }
3524 }
3525 
3526 /// Insert all lines participating in the function signature \p Signature
3527 /// into \p ExecutedLines.
3529  const Decl *Signature, SourceManager &SM,
3530  std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) {
3531  SourceRange SignatureSourceRange;
3532  const Stmt* Body = Signature->getBody();
3533  if (const auto FD = dyn_cast<FunctionDecl>(Signature)) {
3534  SignatureSourceRange = FD->getSourceRange();
3535  } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) {
3536  SignatureSourceRange = OD->getSourceRange();
3537  } else {
3538  return;
3539  }
3540  SourceLocation Start = SignatureSourceRange.getBegin();
3541  SourceLocation End = Body ? Body->getSourceRange().getBegin()
3542  : SignatureSourceRange.getEnd();
3543  unsigned StartLine = SM.getExpansionLineNumber(Start);
3544  unsigned EndLine = SM.getExpansionLineNumber(End);
3545 
3546  FileID FID = SM.getFileID(SM.getExpansionLoc(Start));
3547  for (unsigned Line = StartLine; Line <= EndLine; Line++)
3548  ExecutedLines->operator[](FID.getHashValue()).insert(Line);
3549 }
3550 
3552  const Stmt *S, SourceManager &SM,
3553  std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) {
3555  SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc);
3556  FileID FID = SM.getFileID(ExpansionLoc);
3557  unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc);
3558  ExecutedLines->operator[](FID.getHashValue()).insert(LineNo);
3559 }
3560 
3561 /// \return all executed lines including function signatures on the path
3562 /// starting from \p N.
3563 static std::unique_ptr<FilesToLineNumsMap>
3565  auto ExecutedLines = llvm::make_unique<FilesToLineNumsMap>();
3566 
3567  while (N) {
3568  if (N->getFirstPred() == nullptr) {
3569  // First node: show signature of the entrance point.
3570  const Decl *D = N->getLocationContext()->getDecl();
3571  populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines);
3572  } else if (auto CE = N->getLocationAs<CallEnter>()) {
3573  // Inlined function: show signature.
3574  const Decl* D = CE->getCalleeContext()->getDecl();
3575  populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines);
3576  } else if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) {
3577  populateExecutedLinesWithStmt(S, SM, ExecutedLines);
3578 
3579  // Show extra context for some parent kinds.
3580  const Stmt *P = N->getParentMap().getParent(S);
3581 
3582  // The path exploration can die before the node with the associated
3583  // return statement is generated, but we do want to show the whole
3584  // return.
3585  if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) {
3586  populateExecutedLinesWithStmt(RS, SM, ExecutedLines);
3587  P = N->getParentMap().getParent(RS);
3588  }
3589 
3590  if (P && (isa<SwitchCase>(P) || isa<LabelStmt>(P)))
3591  populateExecutedLinesWithStmt(P, SM, ExecutedLines);
3592  }
3593 
3594  N = N->getFirstPred();
3595  }
3596  return ExecutedLines;
3597 }
3598 
3599 void BugReporter::FlushReport(BugReport *exampleReport,
3601  ArrayRef<BugReport*> bugReports) {
3602  // FIXME: Make sure we use the 'R' for the path that was actually used.
3603  // Probably doesn't make a difference in practice.
3604  BugType& BT = exampleReport->getBugType();
3605 
3606  auto D = llvm::make_unique<PathDiagnostic>(
3607  exampleReport->getBugType().getCheckName(),
3608  exampleReport->getDeclWithIssue(), exampleReport->getBugType().getName(),
3609  exampleReport->getDescription(),
3610  exampleReport->getShortDescription(/*Fallback=*/false), BT.getCategory(),
3611  exampleReport->getUniqueingLocation(), exampleReport->getUniqueingDecl(),
3612  findExecutedLines(getSourceManager(), exampleReport->getErrorNode()));
3613 
3614  if (exampleReport->isPathSensitive()) {
3615  // Generate the full path diagnostic, using the generation scheme
3616  // specified by the PathDiagnosticConsumer. Note that we have to generate
3617  // path diagnostics even for consumers which do not support paths, because
3618  // the BugReporterVisitors may mark this bug as a false positive.
3619  assert(!bugReports.empty());
3620 
3621  MaxBugClassSize.updateMax(bugReports.size());
3622 
3623  if (!generatePathDiagnostic(*D.get(), PD, bugReports))
3624  return;
3625 
3626  MaxValidBugClassSize.updateMax(bugReports.size());
3627 
3628  // Examine the report and see if the last piece is in a header. Reset the
3629  // report location to the last piece in the main source file.
3630  AnalyzerOptions &Opts = getAnalyzerOptions();
3631  if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll)
3632  D->resetDiagnosticLocationToMainFile();
3633  }
3634 
3635  // If the path is empty, generate a single step path with the location
3636  // of the issue.
3637  if (D->path.empty()) {
3638  PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
3639  auto piece = llvm::make_unique<PathDiagnosticEventPiece>(
3640  L, exampleReport->getDescription());
3641  for (SourceRange Range : exampleReport->getRanges())
3642  piece->addRange(Range);
3643  D->setEndOfPath(std::move(piece));
3644  }
3645 
3646  PathPieces &Pieces = D->getMutablePieces();
3647  if (getAnalyzerOptions().shouldDisplayNotesAsEvents()) {
3648  // For path diagnostic consumers that don't support extra notes,
3649  // we may optionally convert those to path notes.
3650  for (auto I = exampleReport->getNotes().rbegin(),
3651  E = exampleReport->getNotes().rend(); I != E; ++I) {
3652  PathDiagnosticNotePiece *Piece = I->get();
3653  auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>(
3654  Piece->getLocation(), Piece->getString());
3655  for (const auto &R: Piece->getRanges())
3656  ConvertedPiece->addRange(R);
3657 
3658  Pieces.push_front(std::move(ConvertedPiece));
3659  }
3660  } else {
3661  for (auto I = exampleReport->getNotes().rbegin(),
3662  E = exampleReport->getNotes().rend(); I != E; ++I)
3663  Pieces.push_front(*I);
3664  }
3665 
3666  // Get the meta data.
3667  const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
3668  for (const auto &i : Meta)
3669  D->addMeta(i);
3670 
3671  PD.HandlePathDiagnostic(std::move(D));
3672 }
3673 
3674 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3675  const CheckerBase *Checker,
3676  StringRef Name, StringRef Category,
3677  StringRef Str, PathDiagnosticLocation Loc,
3678  ArrayRef<SourceRange> Ranges) {
3679  EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str,
3680  Loc, Ranges);
3681 }
3682 
3683 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3685  StringRef name, StringRef category,
3686  StringRef str, PathDiagnosticLocation Loc,
3687  ArrayRef<SourceRange> Ranges) {
3688  // 'BT' is owned by BugReporter.
3689  BugType *BT = getBugTypeForName(CheckName, name, category);
3690  auto R = llvm::make_unique<BugReport>(*BT, str, Loc);
3691  R->setDeclWithIssue(DeclWithIssue);
3692  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
3693  I != E; ++I)
3694  R->addRange(*I);
3695  emitReport(std::move(R));
3696 }
3697 
3698 BugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name,
3699  StringRef category) {
3700  SmallString<136> fullDesc;
3701  llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name
3702  << ":" << category;
3703  BugType *&BT = StrBugTypes[fullDesc];
3704  if (!BT)
3705  BT = new BugType(CheckName, name, category);
3706  return BT;
3707 }
3708 
3709 LLVM_DUMP_METHOD void PathPieces::dump() const {
3710  unsigned index = 0;
3711  for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
3712  llvm::errs() << "[" << index++ << "] ";
3713  (*I)->dump();
3714  llvm::errs() << "\n";
3715  }
3716 }
3717 
3718 LLVM_DUMP_METHOD void PathDiagnosticCallPiece::dump() const {
3719  llvm::errs() << "CALL\n--------------\n";
3720 
3721  if (const Stmt *SLoc = getLocStmt(getLocation()))
3722  SLoc->dump();
3723  else if (const auto *ND = dyn_cast<NamedDecl>(getCallee()))
3724  llvm::errs() << *ND << "\n";
3725  else
3726  getLocation().dump();
3727 }
3728 
3729 LLVM_DUMP_METHOD void PathDiagnosticEventPiece::dump() const {
3730  llvm::errs() << "EVENT\n--------------\n";
3731  llvm::errs() << getString() << "\n";
3732  llvm::errs() << " ---- at ----\n";
3733  getLocation().dump();
3734 }
3735 
3736 LLVM_DUMP_METHOD void PathDiagnosticControlFlowPiece::dump() const {
3737  llvm::errs() << "CONTROL\n--------------\n";
3738  getStartLocation().dump();
3739  llvm::errs() << " ---- to ----\n";
3740  getEndLocation().dump();
3741 }
3742 
3743 LLVM_DUMP_METHOD void PathDiagnosticMacroPiece::dump() const {
3744  llvm::errs() << "MACRO\n--------------\n";
3745  // FIXME: Print which macro is being invoked.
3746 }
3747 
3748 LLVM_DUMP_METHOD void PathDiagnosticNotePiece::dump() const {
3749  llvm::errs() << "NOTE\n--------------\n";
3750  llvm::errs() << getString() << "\n";
3751  llvm::errs() << " ---- at ----\n";
3752  getLocation().dump();
3753 }
3754 
3755 LLVM_DUMP_METHOD void PathDiagnosticLocation::dump() const {
3756  if (!isValid()) {
3757  llvm::errs() << "<INVALID>\n";
3758  return;
3759  }
3760 
3761  switch (K) {
3762  case RangeK:
3763  // FIXME: actually print the range.
3764  llvm::errs() << "<range>\n";
3765  break;
3766  case SingleLocK:
3767  asLocation().dump();
3768  llvm::errs() << "\n";
3769  break;
3770  case StmtK:
3771  if (S)
3772  S->dump();
3773  else
3774  llvm::errs() << "<NULL STMT>\n";
3775  break;
3776  case DeclK:
3777  if (const auto *ND = dyn_cast_or_null<NamedDecl>(D))
3778  llvm::errs() << *ND << "\n";
3779  else if (isa<BlockDecl>(D))
3780  // FIXME: Make this nicer.
3781  llvm::errs() << "<block>\n";
3782  else if (D)
3783  llvm::errs() << "<unknown decl>\n";
3784  else
3785  llvm::errs() << "<NULL DECL>\n";
3786  break;
3787  }
3788 }
static void removeEdgesToDefaultInitializers(PathPieces &Pieces)
Remove edges in and out of C++ default initializer expressions.
bool isWrittenInSameFile(SourceLocation Loc1, SourceLocation Loc2) const
Returns true if the spelling locations for both SourceLocations are part of the same file buffer...
static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE)
Return true if the terminator is a loop and the destination is the false branch.
static void removeRedundantMsgs(PathPieces &path)
An optimization pass over PathPieces that removes redundant diagnostics generated by both ConditionBR...
static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS)
static Optional< size_t > getLengthOnSingleLine(SourceManager &SM, SourceRange Range)
Returns the number of bytes in the given (character-based) SourceRange.
if(T->getSizeExpr()) TRY_TO(TraverseStmt(T -> getSizeExpr()))
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, LocationContextMap &LCM, bool IsInteresting=false)
Recursively scan through a path and prune out calls and macros pieces that aren&#39;t needed...
PathDiagnosticLocation getUniqueingLocation() const
Get the location on which the report should be uniqued.
Definition: BugReporter.h:319
bool isInteresting(SymbolRef sym)
PathDiagnosticLocation getLocation() const override
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
succ_iterator succ_begin()
Definition: CFG.h:750
virtual Stmt * getBody() const
getBody - If this Decl represents a declaration for a body of code, such as a function or method defi...
Definition: DeclBase.h:978
FullSourceLoc getExpansionLoc() const
Stmt - This represents one statement.
Definition: Stmt.h:66
An instance of this object exists for each enum constant that is defined.
Definition: Decl.h:2723
Defines the SourceManager interface.
CheckName getCheckName() const
Definition: Checker.cpp:24
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:481
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:600
StringRef getDescription() const
Definition: BugReporter.h:207
StringRef P
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:123
void Profile(llvm::FoldingSetNodeID &ID) const
Loc getLValue(const VarDecl *D, const LocationContext *LC) const
Get the lvalue for a variable reference.
Definition: ProgramState.h:716
iterator begin()
Definition: CFG.h:702
static void adjustCallLocations(PathPieces &Pieces, PathDiagnosticLocation *LastCallLocation=nullptr)
Recursively scan through a path and make sure that all call pieces have valid locations.
const ProgramStateRef & getState() const
static std::shared_ptr< PathDiagnosticCallPiece > construct(const ExplodedNode *N, const CallExitEnd &CE, const SourceManager &SM)
ArrayRef< ParmVarDecl * >::const_iterator param_const_iterator
Definition: Decl.h:2226
PathDiagnosticLocation getStartLocation() const
virtual PathDiagnosticLocation getLocation(const SourceManager &SM) const
Return the "definitive" location of the reported bug.
static PathDiagnosticLocation createEndBrace(const CompoundStmt *CS, const SourceManager &SM)
Create a location for the end of the compound statement.
unsigned succ_size() const
Definition: CFG.h:768
static bool optimizeEdges(PathPieces &path, SourceManager &SM, OptimizedCallsSet &OCS, LocationContextMap &LCM)
bool isConsumedExpr(Expr *E) const
Definition: ParentMap.cpp:160
static const Stmt * GetCurrentOrPreviousStmt(const ExplodedNode *N)
const Decl & getCodeDecl() const
static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond)
Defines the Objective-C statement AST node classes.
static PathDiagnosticLocation createDeclEnd(const LocationContext *LC, const SourceManager &SM)
Constructs a location for the end of the enclosing declaration body.
Represents a parameter to a function.
Definition: Decl.h:1528
Defines the clang::Expr interface and subclasses for C++ expressions.
static PathDiagnosticLocation createSingleLocation(const PathDiagnosticLocation &PDL)
Convert the given location into a single kind location.
static void removePiecesWithInvalidLocations(PathPieces &Pieces)
Remove all pieces with invalid locations as these cannot be serialized.
BoundNodesTreeBuilder Nodes
PathDiagnosticLocation getLocation() const
Symbolic value.
Definition: SymExpr.h:30
PathDiagnostic - PathDiagnostic objects represent a single path-sensitive diagnostic.
static PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L, const LocationContext *LC, bool firstCharOnly=false)
void setStartLocation(const PathDiagnosticLocation &L)
LineState State
bool isValid() const
Returns whether or not this report should be considered valid.
Definition: BugReporter.h:240
succ_iterator succ_begin()
static PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, const LocationContext *LC, bool allowNestedContexts)
AnalysisDeclContext contains the context data for the function or method under analysis.
unsigned getHashValue() const
static void removeIdenticalEvents(PathPieces &path)
StringRef getName() const
Definition: BugType.h:49
static const char StrLoopBodyZero[]
std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy *> Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
Creates a trimmed version of the graph that only contains paths leading to the given nodes...
static const CFGBlock * findBlockForNode(const ExplodedNode *N)
succ_range succs()
Definition: CFG.h:760
void pushActivePath(PathPieces *p)
int Category
Definition: Format.cpp:1555
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
virtual bool supportsLogicalOpControlFlow() const
Optional< T > getLocationAs() const LLVM_LVALUE_FUNCTION
PathPieces & getMutablePieces()
Return a mutable version of &#39;path&#39;.
virtual llvm::iterator_range< ranges_iterator > getRanges()
Get the SourceRanges associated with the report.
static bool IsControlFlowExpr(const Stmt *S)
StringRef getCategory() const
Definition: BugType.h:50
const Stmt * getStmt() const
llvm::DenseMap< const PathPieces *, const LocationContext * > LocationContextMap
A map from PathDiagnosticPiece to the LocationContext of the inlined function call it represents...
virtual void FlushReports(BugReporter &BR)
const BugType & getBugType() const
Definition: BugReporter.h:190
static void addEdgeToPath(PathPieces &path, PathDiagnosticLocation &PrevLoc, PathDiagnosticLocation NewLoc, const LocationContext *LC)
Adds a sanitized control-flow diagnostic edge to a path.
static void generateExtensiveDiagnosticsForNode(const ExplodedNode *N, PathDiagnosticBuilder &PDB, LocationContextMap &LCM, EdgeBuilder &EB, StackDiagVector &CallStack, PathDiagnostic &PD, InterestingExprs &IE)
Generate extensive diagnostics for statement associated with node N, and write it into PD...
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static bool isJumpToFalseBranch(const BlockEdge *BE)
SourceLocation getExpansionLoc(SourceLocation Loc) const
Given a SourceLocation object Loc, return the expansion location referenced by the ID...
const StackFrameContext * getCurrentStackFrame() const
child_range children()
Definition: Stmt.cpp:227
const LocationContext * getLocationContext() const
Expr * IgnoreParenCasts() LLVM_READONLY
IgnoreParenCasts - Ignore parentheses and casts.
Definition: Expr.cpp:2469
bool generatePathDiagnostic(PathDiagnostic &PD, PathDiagnosticConsumer &PC, ArrayRef< BugReport *> &bugReports) override
Generates a path corresponding to one of the given bug reports.
const Decl * getDeclWithIssue() const
Return the canonical declaration, be it a method or class, where this issue semantically occurred...
static const Stmt * getStmtBeforeCond(ParentMap &PM, const Stmt *Term, const ExplodedNode *N)
ExplodedNode * getFirstPred()
static void reversePropagateIntererstingSymbols(BugReport &R, InterestingExprs &IE, const ProgramState *State, const Expr *Ex, const LocationContext *LCtx)
BugReporterContext(GRBugReporter &br)
Definition: BugReporter.h:561
virtual BugReport::NodeResolver & getNodeResolver()=0
static BugReport * FindReportInEquivalenceClass(BugReportEquivClass &EQ, SmallVectorImpl< BugReport *> &bugReports)
void addVisitor(std::unique_ptr< BugReporterVisitor > visitor)
Add custom or predefined bug report visitors to this report.
SVal getSVal(const Stmt *S, const LocationContext *LCtx) const
Returns the SVal bound to the statement &#39;S&#39; in the state&#39;s environment.
Definition: ProgramState.h:750
PathDiagnosticLocation getEndLocation() const
virtual const NoteList & getNotes()
Definition: BugReporter.h:296
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:127
NodeId Parent
Definition: ASTDiff.cpp:192
const ExplodedNode *const * const_succ_iterator
Const iterator for iterating over Stmt * arrays that contain only Expr *.
Definition: Stmt.h:357
CompoundStmt - This represents a group of statements like { stmt stmt }.
Definition: Stmt.h:609
const Stmt * getCallSite() const
StringRef getName() const
const void * getTag() const
Return the opaque tag (if any) on the PathDiagnosticPiece.
VisitorList::iterator visitor_iterator
Definition: BugReporter.h:84
void HandlePathDiagnostic(std::unique_ptr< PathDiagnostic > D)
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:548
static const char * getTag()
Return the tag associated with this visitor.
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:658
bool isBodyAutosynthesizedFromModelFile() const
Checks if the body of the Decl is generated by the BodyFarm from a model file.
virtual const ExtraTextList & getExtraText()
Definition: BugReporter.h:307
STATISTIC(MaxBugClassSize, "The maximum number of bug reports in the same equivalence class")
ProgramState - This class encapsulates:
Definition: ProgramState.h:74
Expr - This represents one expression.
Definition: Expr.h:106
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:5335
SourceLocation End
pred_iterator pred_end()
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1002
const AnnotatedLine * Line
const FunctionProtoType * T
static bool isPieceMessageGeneric(const PathDiagnosticPiece *Piece)
CFGBlock * getBlock(Stmt *S)
Returns the CFGBlock the specified Stmt* appears in.
Definition: CFGStmtMap.cpp:27
Kind getKind() const
Definition: ProgramPoint.h:161
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:551
static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y)
Return true if X is contained by Y.
static void reversePropagateInterestingSymbols(BugReport &R, InterestingExprs &IE, const ProgramState *State, const LocationContext *CalleeCtx, const LocationContext *CallerCtx)
const SourceManager & getManager() const
const Decl * getUniqueingDecl() const
Get the declaration containing the uniqueing location.
Definition: BugReporter.h:324
void Register(BugType *BT)
static const Stmt * getNextStmt(const ExplodedNode *N)
Retrieve the statement corresponding to the successor node.
void FlushReports()
Generate and flush diagnostics for all bug reports.
const CFGBlock * getDst() const
Definition: ProgramPoint.h:485
static void dropFunctionEntryEdge(PathPieces &Path, LocationContextMap &LCM, SourceManager &SM)
Drop the very first edge in a path, which should be a function entry edge.
bool isBodyAutosynthesized() const
Checks if the body of the Decl is generated by the BodyFarm.
SourceLocation getEnd() const
void markInteresting(SymbolRef sym)
static const Stmt * GetPreviousStmt(const ExplodedNode *N)
Definition: BugReporter.cpp:92
unsigned getExpansionLineNumber(SourceLocation Loc, bool *Invalid=nullptr) const
bool getBooleanOption(StringRef Name, bool DefaultVal, const ento::CheckerBase *C=nullptr, bool SearchInParents=false)
Interprets an option&#39;s string value as a boolean.
const SourceManager & SM
Definition: Format.cpp:1422
ParentMap & getParentMap() const
static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, ArrayRef< std::unique_ptr< BugReporterVisitor >> visitors)
virtual bool hasBody() const
Returns true if this Decl represents a declaration for a body of code, such as a function or method d...
Definition: DeclBase.h:984
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:416
static const Stmt * getStmt(const ExplodedNode *N)
Given an exploded node, retrieve the statement that should be used for the diagnostic location...
unsigned getFileOffset(SourceLocation SpellingLoc) const
Returns the offset from the start of the file that the specified SourceLocation represents.
static PathDiagnosticLocation createDeclBegin(const LocationContext *LC, const SourceManager &SM)
Create a location for the beginning of the enclosing declaration body.
CFGTerminator getTerminator()
Definition: CFG.h:839
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
void generateMinimalDiagnosticsForNode(const ExplodedNode *N, PathDiagnosticBuilder &PDB, PathDiagnostic &PD, LocationContextMap &LCM, StackDiagVector &CallStack)
Generate minimal diagnostics for node N, and write it into path diagnostics PD.
static PathDiagnosticEventPiece * eventsDescribeSameCondition(PathDiagnosticEventPiece *X, PathDiagnosticEventPiece *Y)
static std::unique_ptr< PathDiagnosticPiece > getDefaultEndPath(BugReporterContext &BRC, const ExplodedNode *N, BugReport &BR)
Generates the default final diagnostic piece.
llvm::MemoryBuffer * getBuffer(FileID FID, SourceLocation Loc, bool *Invalid=nullptr) const
Return the buffer for the specified FileID.
static void simplifySimpleBranches(PathPieces &pieces)
Move edges from a branch condition to a branch target when the condition is simple.
Encodes a location in the source.
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=None)
Stmt * getLabel()
Definition: CFG.h:850
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type...
Definition: ProgramPoint.h:141
Stmt * getParentIgnoreParens(Stmt *) const
Definition: ParentMap.cpp:129
const MemRegion * getAsRegion() const
Definition: SVals.cpp:151
ExplodedGraph & getGraph()
getGraph - Get the exploded graph created by the analysis engine for the analyzed method or function...
void emitReport(std::unique_ptr< BugReport > R)
Add the given report to the set of reports tracked by BugReporter.
static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL)
void setCallee(const CallEnter &CE, const SourceManager &SM)
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
ParentMap & getParentMap() const
PathDiagnosticLocation getLocation() const override
static const Stmt * getEnclosingParent(const Stmt *S, const ParentMap &PM)
static void removePunyEdges(PathPieces &path, SourceManager &SM, ParentMap &PM)
static bool hasImplicitBody(const Decl *D)
Returns true if the given decl has been implicitly given a body, either by the analyzer or by the com...
ast_type_traits::DynTypedNode Node
An opaque identifier used by SourceManager which refers to a source file (MemoryBuffer) along with it...
unsigned getExpansionColumnNumber(SourceLocation Loc, bool *Invalid=nullptr) const
ArrayRef< SourceRange > getRanges() const
Return the SourceRanges associated with this PathDiagnosticPiece.
Dataflow Directional Tag Classes.
static const char StrLoopCollectionEmpty[]
bool isValid() const
Return true if this is a valid SourceLocation object.
std::pair< PathDiagnosticCallPiece *, const ExplodedNode * > StackDiagPair
static const Stmt * getLocStmt(PathDiagnosticLocation L)
std::pair< SourceLocation, SourceLocation > getExpansionRange(SourceLocation Loc) const
Given a SourceLocation object, return the range of tokens covered by the expansion in the ultimate fi...
PathDiagnosticRange asRange() const
StmtClass getStmtClass() const
Definition: Stmt.h:389
static void updateStackPiecesWithMessage(PathDiagnosticPiece &P, StackDiagVector &CallStack)
StringRef getCheckName() const
Definition: BugType.h:51
static bool GenerateMinimalPathDiagnostic(PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, LocationContextMap &LCM, ArrayRef< std::unique_ptr< BugReporterVisitor >> visitors)
static const Stmt * getTerminatorCondition(const CFGBlock *B)
A customized wrapper for CFGBlock::getTerminatorCondition() which returns the element for ObjCForColl...
static std::unique_ptr< FilesToLineNumsMap > findExecutedLines(SourceManager &SM, const ExplodedNode *N)
const Decl * getDecl() const
unsigned getExpansionLineNumber(bool *Invalid=nullptr) const
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
static bool isLoop(const Stmt *Term)
FileID getFileID(SourceLocation SpellingLoc) const
Return the FileID for a SourceLocation.
virtual PathGenerationScheme getGenerationScheme() const
void dump() const
Dumps the specified AST fragment and all subtrees to llvm::errs().
Definition: ASTDumper.cpp:2778
succ_iterator succ_end()
void setEndOfPath(std::unique_ptr< PathDiagnosticPiece > EndPiece)
static void populateExecutedLinesWithStmt(const Stmt *S, SourceManager &SM, std::unique_ptr< FilesToLineNumsMap > &ExecutedLines)
const ExplodedNode * getErrorNode() const
Definition: BugReporter.h:205
static void generateMinimalDiagnosticsForBlockEdge(const ExplodedNode *N, PathDiagnosticBuilder &PDB, PathDiagnostic &PD)
Add path diagnostic for statement associated with node N to diagnostics PD.
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:180
virtual void Profile(llvm::FoldingSetNodeID &hash) const
Profile to identify equivalent bug reports for error report coalescing.
SVal getRawSVal(Loc LV, QualType T=QualType()) const
Returns the "raw" SVal bound to LV before any value simplfication.
Definition: ProgramState.h:769
static void generateAlternateExtensiveDiagnosticsForNode(const ExplodedNode *N, PathDiagnostic &PD, PathDiagnosticLocation &PrevLoc, PathDiagnosticBuilder &PDB, LocationContextMap &LCM, StackDiagVector &CallStack, InterestingExprs &IE)
Generate alternate-extensive diagnostics for the node N, and write it into PD.
StringRef getShortDescription(bool UseFallback=true) const
Definition: BugReporter.h:209
static bool isInevitablySinking(const ExplodedNode *N)
bool hasNoReturnElement() const
Definition: CFG.h:853
static PathDiagnosticLocation createOperatorLoc(const BinaryOperator *BO, const SourceManager &SM)
Create the location for the operator of the binary expression.
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13483
llvm::ilist< BugReport >::iterator iterator
Definition: BugReporter.h:388
ProgramStateManager & getStateManager()
getStateManager - Return the state manager used by the analysis engine.
static void CompactPathDiagnostic(PathPieces &path, const SourceManager &SM)
CompactPathDiagnostic - This function postprocesses a PathDiagnostic object and collapses PathDiagost...
Defines the clang::SourceLocation class and associated facilities.
PathPieces & getActivePath()
Return the path currently used by builders for constructing the PathDiagnostic.
pred_iterator pred_begin()
static const Stmt * getStmtParent(const Stmt *S, const ParentMap &PM)
static PathDiagnosticLocation createEndOfPath(const ExplodedNode *N, const SourceManager &SM)
Create a location corresponding to the next valid ExplodedNode as end of path location.
CFGElement - Represents a top-level expression in a basic block.
Definition: CFG.h:55
static void removeContextCycles(PathPieces &Path, SourceManager &SM, ParentMap &PM)
Eliminate two-edge cycles created by addContextEdges().
const MemRegion * getBaseRegion() const
Definition: MemRegion.cpp:1125
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:266
static bool isImmediateSinkBlock(const CFGBlock *Blk)
static bool GenerateAlternateExtensivePathDiagnostic(PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, LocationContextMap &LCM, ArrayRef< std::unique_ptr< BugReporterVisitor >> visitors)
A SourceLocation and its associated SourceManager.
bool isSuppressOnSink() const
isSuppressOnSink - Returns true if bug reports associated with this bug type should be suppressed if ...
Definition: BugType.h:66
static bool GenerateExtensivePathDiagnostic(PathDiagnostic &PD, PathDiagnosticBuilder &PDB, const ExplodedNode *N, LocationContextMap &LCM, ArrayRef< std::unique_ptr< BugReporterVisitor >> visitors)
static void populateExecutedLinesWithFunctionSignature(const Decl *Signature, SourceManager &SM, std::unique_ptr< FilesToLineNumsMap > &ExecutedLines)
Insert all lines participating in the function signature Signature into ExecutedLines.
const ExplodedNode *const * const_pred_iterator
A trivial tuple used to represent a source range.
static void addContextEdges(PathPieces &pieces, SourceManager &SM, const ParentMap &PM, const LocationContext *LCtx)
Adds synthetic edges from top-level statements to their subexpressions.
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:152
This class provides an interface through which checkers can create individual bug reports...
Definition: BugReporter.h:70
iterator end()
Definition: CFG.h:703
AnalysisDeclContext * getAnalysisDeclContext() const
bool shouldReportIssuesInMainSourceFile()
Returns whether or not the diagnostic report should be always reported in the main source file and no...
static const char StrEnteringLoop[]
SourceLocation getLocStart() const LLVM_READONLY
Definition: Stmt.cpp:278
SourceLocation getBegin() const
static const char StrLoopRangeEmpty[]
This class handles loading and caching of source files into memory.
SourceManager & getSourceManager()
Definition: BugReporter.h:581
bool isPathSensitive() const
True when the report has an execution path associated with it.
Definition: BugReporter.h:203
static const char * getTag()
Return the tag associated with this visitor.
CFGBlock & getExit()
Definition: CFG.h:1093
static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term)