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