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