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