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