clang  5.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  addEdgeToPath(PD.getActivePath(), PrevLoc,
1676  CalleeLC);
1677 
1678  // Did we visit an entire call?
1679  bool VisitedEntireCall = PD.isWithinCall();
1680  PD.popActivePath();
1681 
1683  if (VisitedEntireCall) {
1684  PathDiagnosticPiece *P = PD.getActivePath().front().get();
1685  C = cast<PathDiagnosticCallPiece>(P);
1686  } else {
1687  const Decl *Caller = CE->getLocationContext()->getDecl();
1689 
1690  // Since we just transferred the path over to the call piece,
1691  // reset the mapping from active to location context.
1692  assert(PD.getActivePath().size() == 1 &&
1693  PD.getActivePath().front().get() == C);
1694  LCM[&PD.getActivePath()] = nullptr;
1695 
1696  // Record the location context mapping for the path within
1697  // the call.
1698  assert(LCM[&C->path] == nullptr ||
1699  LCM[&C->path] == CE->getCalleeContext());
1700  LCM[&C->path] = CE->getCalleeContext();
1701 
1702  // If this is the first item in the active path, record
1703  // the new mapping from active path to location context.
1704  const LocationContext *&NewLC = LCM[&PD.getActivePath()];
1705  if (!NewLC)
1706  NewLC = N->getLocationContext();
1707 
1708  PDB.LC = NewLC;
1709  }
1710  C->setCallee(*CE, SM);
1711 
1712  // Update the previous location in the active path.
1713  PrevLoc = C->getLocation();
1714 
1715  if (!CallStack.empty()) {
1716  assert(CallStack.back().first == C);
1717  CallStack.pop_back();
1718  }
1719  break;
1720  }
1721 
1722  // Query the location context here and the previous location
1723  // as processing CallEnter may change the active path.
1724  PDB.LC = N->getLocationContext();
1725 
1726  // Record the mapping from the active path to the location
1727  // context.
1728  assert(!LCM[&PD.getActivePath()] ||
1729  LCM[&PD.getActivePath()] == PDB.LC);
1730  LCM[&PD.getActivePath()] = PDB.LC;
1731 
1732  // Have we encountered an exit from a function call?
1733  if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1734  const Stmt *S = CE->getCalleeContext()->getCallSite();
1735  // Propagate the interesting symbols accordingly.
1736  if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1737  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1738  N->getState().get(), Ex,
1739  N->getLocationContext());
1740  }
1741 
1742  // We are descending into a call (backwards). Construct
1743  // a new call piece to contain the path pieces for that call.
1744  auto C = PathDiagnosticCallPiece::construct(N, *CE, SM);
1745 
1746  // Record the location context for this call piece.
1747  LCM[&C->path] = CE->getCalleeContext();
1748 
1749  // Add the edge to the return site.
1750  addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC);
1751  auto *P = C.get();
1752  PD.getActivePath().push_front(std::move(C));
1753  PrevLoc.invalidate();
1754 
1755  // Make the contents of the call the active path for now.
1756  PD.pushActivePath(&P->path);
1757  CallStack.push_back(StackDiagPair(P, N));
1758  break;
1759  }
1760 
1761  if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1762  // For expressions, make sure we propagate the
1763  // interesting symbols correctly.
1764  if (const Expr *Ex = PS->getStmtAs<Expr>())
1765  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1766  N->getState().get(), Ex,
1767  N->getLocationContext());
1768 
1769  // Add an edge. If this is an ObjCForCollectionStmt do
1770  // not add an edge here as it appears in the CFG both
1771  // as a terminator and as a terminator condition.
1772  if (!isa<ObjCForCollectionStmt>(PS->getStmt())) {
1774  PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC);
1775  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1776  }
1777  break;
1778  }
1779 
1780  // Block edges.
1781  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1782  // Does this represent entering a call? If so, look at propagating
1783  // interesting symbols across call boundaries.
1784  if (NextNode) {
1785  const LocationContext *CallerCtx = NextNode->getLocationContext();
1786  const LocationContext *CalleeCtx = PDB.LC;
1787  if (CallerCtx != CalleeCtx) {
1788  reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1789  N->getState().get(),
1790  CalleeCtx, CallerCtx);
1791  }
1792  }
1793 
1794  // Are we jumping to the head of a loop? Add a special diagnostic.
1795  if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1796  PathDiagnosticLocation L(Loop, SM, PDB.LC);
1797  const Stmt *Body = nullptr;
1798 
1799  if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1800  Body = FS->getBody();
1801  else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1802  Body = WS->getBody();
1803  else if (const ObjCForCollectionStmt *OFS =
1804  dyn_cast<ObjCForCollectionStmt>(Loop)) {
1805  Body = OFS->getBody();
1806  } else if (const CXXForRangeStmt *FRS =
1807  dyn_cast<CXXForRangeStmt>(Loop)) {
1808  Body = FRS->getBody();
1809  }
1810  // do-while statements are explicitly excluded here
1811 
1812  auto p = std::make_shared<PathDiagnosticEventPiece>(
1813  L, "Looping back to the head "
1814  "of the loop");
1815  p->setPrunable(true);
1816 
1817  addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1818  PD.getActivePath().push_front(std::move(p));
1819 
1820  if (const CompoundStmt *CS = dyn_cast_or_null<CompoundStmt>(Body)) {
1821  addEdgeToPath(PD.getActivePath(), PrevLoc,
1823  PDB.LC);
1824  }
1825  }
1826 
1827  const CFGBlock *BSrc = BE->getSrc();
1828  ParentMap &PM = PDB.getParentMap();
1829 
1830  if (const Stmt *Term = BSrc->getTerminator()) {
1831  // Are we jumping past the loop body without ever executing the
1832  // loop (because the condition was false)?
1833  if (isLoop(Term)) {
1834  const Stmt *TermCond = getTerminatorCondition(BSrc);
1835  bool IsInLoopBody =
1836  isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term);
1837 
1838  const char *str = nullptr;
1839 
1840  if (isJumpToFalseBranch(&*BE)) {
1841  if (!IsInLoopBody) {
1842  if (isa<ObjCForCollectionStmt>(Term)) {
1843  str = StrLoopCollectionEmpty;
1844  } else if (isa<CXXForRangeStmt>(Term)) {
1845  str = StrLoopRangeEmpty;
1846  } else {
1847  str = StrLoopBodyZero;
1848  }
1849  }
1850  } else {
1851  str = StrEnteringLoop;
1852  }
1853 
1854  if (str) {
1855  PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC);
1856  auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str);
1857  PE->setPrunable(true);
1858  addEdgeToPath(PD.getActivePath(), PrevLoc,
1859  PE->getLocation(), PDB.LC);
1860  PD.getActivePath().push_front(std::move(PE));
1861  }
1862  } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) ||
1863  isa<GotoStmt>(Term)) {
1864  PathDiagnosticLocation L(Term, SM, PDB.LC);
1865  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1866  }
1867  }
1868  break;
1869  }
1870  } while (0);
1871 
1872  if (!NextNode)
1873  continue;
1874 
1875  // Add pieces from custom visitors.
1876  for (auto &V : visitors) {
1877  if (auto p = V->VisitNode(N, NextNode, PDB, *report)) {
1878  addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1879  updateStackPiecesWithMessage(*p, CallStack);
1880  PD.getActivePath().push_front(std::move(p));
1881  }
1882  }
1883  }
1884 
1885  // Add an edge to the start of the function.
1886  // We'll prune it out later, but it helps make diagnostics more uniform.
1887  const StackFrameContext *CalleeLC = PDB.LC->getCurrentStackFrame();
1888  const Decl *D = CalleeLC->getDecl();
1889  addEdgeToPath(PD.getActivePath(), PrevLoc,
1891  CalleeLC);
1892 
1893  return report->isValid();
1894 }
1895 
1897  if (!L.isValid())
1898  return nullptr;
1899  return L.asStmt();
1900 }
1901 
1902 static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) {
1903  if (!S)
1904  return nullptr;
1905 
1906  while (true) {
1907  S = PM.getParentIgnoreParens(S);
1908 
1909  if (!S)
1910  break;
1911 
1912  if (isa<ExprWithCleanups>(S) ||
1913  isa<CXXBindTemporaryExpr>(S) ||
1914  isa<SubstNonTypeTemplateParmExpr>(S))
1915  continue;
1916 
1917  break;
1918  }
1919 
1920  return S;
1921 }
1922 
1923 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {
1924  switch (S->getStmtClass()) {
1925  case Stmt::BinaryOperatorClass: {
1926  const BinaryOperator *BO = cast<BinaryOperator>(S);
1927  if (!BO->isLogicalOp())
1928  return false;
1929  return BO->getLHS() == Cond || BO->getRHS() == Cond;
1930  }
1931  case Stmt::IfStmtClass:
1932  return cast<IfStmt>(S)->getCond() == Cond;
1933  case Stmt::ForStmtClass:
1934  return cast<ForStmt>(S)->getCond() == Cond;
1935  case Stmt::WhileStmtClass:
1936  return cast<WhileStmt>(S)->getCond() == Cond;
1937  case Stmt::DoStmtClass:
1938  return cast<DoStmt>(S)->getCond() == Cond;
1939  case Stmt::ChooseExprClass:
1940  return cast<ChooseExpr>(S)->getCond() == Cond;
1941  case Stmt::IndirectGotoStmtClass:
1942  return cast<IndirectGotoStmt>(S)->getTarget() == Cond;
1943  case Stmt::SwitchStmtClass:
1944  return cast<SwitchStmt>(S)->getCond() == Cond;
1945  case Stmt::BinaryConditionalOperatorClass:
1946  return cast<BinaryConditionalOperator>(S)->getCond() == Cond;
1947  case Stmt::ConditionalOperatorClass: {
1948  const ConditionalOperator *CO = cast<ConditionalOperator>(S);
1949  return CO->getCond() == Cond ||
1950  CO->getLHS() == Cond ||
1951  CO->getRHS() == Cond;
1952  }
1953  case Stmt::ObjCForCollectionStmtClass:
1954  return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;
1955  case Stmt::CXXForRangeStmtClass: {
1956  const CXXForRangeStmt *FRS = cast<CXXForRangeStmt>(S);
1957  return FRS->getCond() == Cond || FRS->getRangeInit() == Cond;
1958  }
1959  default:
1960  return false;
1961  }
1962 }
1963 
1964 static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {
1965  if (const ForStmt *FS = dyn_cast<ForStmt>(FL))
1966  return FS->getInc() == S || FS->getInit() == S;
1967  if (const CXXForRangeStmt *FRS = dyn_cast<CXXForRangeStmt>(FL))
1968  return FRS->getInc() == S || FRS->getRangeStmt() == S ||
1969  FRS->getLoopVarStmt() || FRS->getRangeInit() == S;
1970  return false;
1971 }
1972 
1975 
1976 /// Adds synthetic edges from top-level statements to their subexpressions.
1977 ///
1978 /// This avoids a "swoosh" effect, where an edge from a top-level statement A
1979 /// points to a sub-expression B.1 that's not at the start of B. In these cases,
1980 /// we'd like to see an edge from A to B, then another one from B to B.1.
1981 static void addContextEdges(PathPieces &pieces, SourceManager &SM,
1982  const ParentMap &PM, const LocationContext *LCtx) {
1983  PathPieces::iterator Prev = pieces.end();
1984  for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;
1985  Prev = I, ++I) {
1987  dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1988 
1989  if (!Piece)
1990  continue;
1991 
1992  PathDiagnosticLocation SrcLoc = Piece->getStartLocation();
1994 
1995  PathDiagnosticLocation NextSrcContext = SrcLoc;
1996  const Stmt *InnerStmt = nullptr;
1997  while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {
1998  SrcContexts.push_back(NextSrcContext);
1999  InnerStmt = NextSrcContext.asStmt();
2000  NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx,
2001  /*allowNested=*/true);
2002  }
2003 
2004  // Repeatedly split the edge as necessary.
2005  // This is important for nested logical expressions (||, &&, ?:) where we
2006  // want to show all the levels of context.
2007  while (true) {
2008  const Stmt *Dst = getLocStmt(Piece->getEndLocation());
2009 
2010  // We are looking at an edge. Is the destination within a larger
2011  // expression?
2012  PathDiagnosticLocation DstContext =
2013  getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true);
2014  if (!DstContext.isValid() || DstContext.asStmt() == Dst)
2015  break;
2016 
2017  // If the source is in the same context, we're already good.
2018  if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) !=
2019  SrcContexts.end())
2020  break;
2021 
2022  // Update the subexpression node to point to the context edge.
2023  Piece->setStartLocation(DstContext);
2024 
2025  // Try to extend the previous edge if it's at the same level as the source
2026  // context.
2027  if (Prev != E) {
2028  auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get());
2029 
2030  if (PrevPiece) {
2031  if (const Stmt *PrevSrc = getLocStmt(PrevPiece->getStartLocation())) {
2032  const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);
2033  if (PrevSrcParent == getStmtParent(getLocStmt(DstContext), PM)) {
2034  PrevPiece->setEndLocation(DstContext);
2035  break;
2036  }
2037  }
2038  }
2039  }
2040 
2041  // Otherwise, split the current edge into a context edge and a
2042  // subexpression edge. Note that the context statement may itself have
2043  // context.
2044  auto P =
2045  std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext);
2046  Piece = P.get();
2047  I = pieces.insert(I, std::move(P));
2048  }
2049  }
2050 }
2051 
2052 /// \brief Move edges from a branch condition to a branch target
2053 /// when the condition is simple.
2054 ///
2055 /// This restructures some of the work of addContextEdges. That function
2056 /// creates edges this may destroy, but they work together to create a more
2057 /// aesthetically set of edges around branches. After the call to
2058 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from
2059 /// the branch to the branch condition, and (3) an edge from the branch
2060 /// condition to the branch target. We keep (1), but may wish to remove (2)
2061 /// and move the source of (3) to the branch if the branch condition is simple.
2062 ///
2063 static void simplifySimpleBranches(PathPieces &pieces) {
2064  for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {
2065 
2066  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2067 
2068  if (!PieceI)
2069  continue;
2070 
2071  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2072  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2073 
2074  if (!s1Start || !s1End)
2075  continue;
2076 
2077  PathPieces::iterator NextI = I; ++NextI;
2078  if (NextI == E)
2079  break;
2080 
2081  PathDiagnosticControlFlowPiece *PieceNextI = nullptr;
2082 
2083  while (true) {
2084  if (NextI == E)
2085  break;
2086 
2087  auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
2088  if (EV) {
2089  StringRef S = EV->getString();
2090  if (S == StrEnteringLoop || S == StrLoopBodyZero ||
2092  ++NextI;
2093  continue;
2094  }
2095  break;
2096  }
2097 
2098  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2099  break;
2100  }
2101 
2102  if (!PieceNextI)
2103  continue;
2104 
2105  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2106  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2107 
2108  if (!s2Start || !s2End || s1End != s2Start)
2109  continue;
2110 
2111  // We only perform this transformation for specific branch kinds.
2112  // We don't want to do this for do..while, for example.
2113  if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) ||
2114  isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) ||
2115  isa<CXXForRangeStmt>(s1Start)))
2116  continue;
2117 
2118  // Is s1End the branch condition?
2119  if (!isConditionForTerminator(s1Start, s1End))
2120  continue;
2121 
2122  // Perform the hoisting by eliminating (2) and changing the start
2123  // location of (3).
2124  PieceNextI->setStartLocation(PieceI->getStartLocation());
2125  I = pieces.erase(I);
2126  }
2127 }
2128 
2129 /// Returns the number of bytes in the given (character-based) SourceRange.
2130 ///
2131 /// If the locations in the range are not on the same line, returns None.
2132 ///
2133 /// Note that this does not do a precise user-visible character or column count.
2135  SourceRange Range) {
2136  SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),
2137  SM.getExpansionRange(Range.getEnd()).second);
2138 
2139  FileID FID = SM.getFileID(ExpansionRange.getBegin());
2140  if (FID != SM.getFileID(ExpansionRange.getEnd()))
2141  return None;
2142 
2143  bool Invalid;
2144  const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid);
2145  if (Invalid)
2146  return None;
2147 
2148  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
2149  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
2150  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
2151 
2152  // We're searching the raw bytes of the buffer here, which might include
2153  // escaped newlines and such. That's okay; we're trying to decide whether the
2154  // SourceRange is covering a large or small amount of space in the user's
2155  // editor.
2156  if (Snippet.find_first_of("\r\n") != StringRef::npos)
2157  return None;
2158 
2159  // This isn't Unicode-aware, but it doesn't need to be.
2160  return Snippet.size();
2161 }
2162 
2163 /// \sa getLengthOnSingleLine(SourceManager, SourceRange)
2165  const Stmt *S) {
2166  return getLengthOnSingleLine(SM, S->getSourceRange());
2167 }
2168 
2169 /// Eliminate two-edge cycles created by addContextEdges().
2170 ///
2171 /// Once all the context edges are in place, there are plenty of cases where
2172 /// there's a single edge from a top-level statement to a subexpression,
2173 /// followed by a single path note, and then a reverse edge to get back out to
2174 /// the top level. If the statement is simple enough, the subexpression edges
2175 /// just add noise and make it harder to understand what's going on.
2176 ///
2177 /// This function only removes edges in pairs, because removing only one edge
2178 /// might leave other edges dangling.
2179 ///
2180 /// This will not remove edges in more complicated situations:
2181 /// - if there is more than one "hop" leading to or from a subexpression.
2182 /// - if there is an inlined call between the edges instead of a single event.
2183 /// - if the whole statement is large enough that having subexpression arrows
2184 /// might be helpful.
2186  ParentMap &PM) {
2187  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
2188  // Pattern match the current piece and its successor.
2190  dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2191 
2192  if (!PieceI) {
2193  ++I;
2194  continue;
2195  }
2196 
2197  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2198  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2199 
2200  PathPieces::iterator NextI = I; ++NextI;
2201  if (NextI == E)
2202  break;
2203 
2204  PathDiagnosticControlFlowPiece *PieceNextI =
2205  dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2206 
2207  if (!PieceNextI) {
2208  if (isa<PathDiagnosticEventPiece>(NextI->get())) {
2209  ++NextI;
2210  if (NextI == E)
2211  break;
2212  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2213  }
2214 
2215  if (!PieceNextI) {
2216  ++I;
2217  continue;
2218  }
2219  }
2220 
2221  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2222  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2223 
2224  if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
2225  const size_t MAX_SHORT_LINE_LENGTH = 80;
2226  Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
2227  if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {
2228  Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
2229  if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
2230  Path.erase(I);
2231  I = Path.erase(NextI);
2232  continue;
2233  }
2234  }
2235  }
2236 
2237  ++I;
2238  }
2239 }
2240 
2241 /// \brief Return true if X is contained by Y.
2242 static bool lexicalContains(ParentMap &PM,
2243  const Stmt *X,
2244  const Stmt *Y) {
2245  while (X) {
2246  if (X == Y)
2247  return true;
2248  X = PM.getParent(X);
2249  }
2250  return false;
2251 }
2252 
2253 // Remove short edges on the same line less than 3 columns in difference.
2254 static void removePunyEdges(PathPieces &path,
2255  SourceManager &SM,
2256  ParentMap &PM) {
2257 
2258  bool erased = false;
2259 
2260  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
2261  erased ? I : ++I) {
2262 
2263  erased = false;
2264 
2265  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2266 
2267  if (!PieceI)
2268  continue;
2269 
2270  const Stmt *start = getLocStmt(PieceI->getStartLocation());
2271  const Stmt *end = getLocStmt(PieceI->getEndLocation());
2272 
2273  if (!start || !end)
2274  continue;
2275 
2276  const Stmt *endParent = PM.getParent(end);
2277  if (!endParent)
2278  continue;
2279 
2280  if (isConditionForTerminator(end, endParent))
2281  continue;
2282 
2283  SourceLocation FirstLoc = start->getLocStart();
2284  SourceLocation SecondLoc = end->getLocStart();
2285 
2286  if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
2287  continue;
2288  if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
2289  std::swap(SecondLoc, FirstLoc);
2290 
2291  SourceRange EdgeRange(FirstLoc, SecondLoc);
2292  Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
2293 
2294  // If the statements are on different lines, continue.
2295  if (!ByteWidth)
2296  continue;
2297 
2298  const size_t MAX_PUNY_EDGE_LENGTH = 2;
2299  if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
2300  // FIXME: There are enough /bytes/ between the endpoints of the edge, but
2301  // there might not be enough /columns/. A proper user-visible column count
2302  // is probably too expensive, though.
2303  I = path.erase(I);
2304  erased = true;
2305  continue;
2306  }
2307  }
2308 }
2309 
2310 static void removeIdenticalEvents(PathPieces &path) {
2311  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
2312  auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());
2313 
2314  if (!PieceI)
2315  continue;
2316 
2317  PathPieces::iterator NextI = I; ++NextI;
2318  if (NextI == E)
2319  return;
2320 
2321  auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
2322 
2323  if (!PieceNextI)
2324  continue;
2325 
2326  // Erase the second piece if it has the same exact message text.
2327  if (PieceI->getString() == PieceNextI->getString()) {
2328  path.erase(NextI);
2329  }
2330  }
2331 }
2332 
2333 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
2334  OptimizedCallsSet &OCS,
2335  LocationContextMap &LCM) {
2336  bool hasChanges = false;
2337  const LocationContext *LC = LCM[&path];
2338  assert(LC);
2339  ParentMap &PM = LC->getParentMap();
2340 
2341  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
2342  // Optimize subpaths.
2343  if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {
2344  // Record the fact that a call has been optimized so we only do the
2345  // effort once.
2346  if (!OCS.count(CallI)) {
2347  while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
2348  OCS.insert(CallI);
2349  }
2350  ++I;
2351  continue;
2352  }
2353 
2354  // Pattern match the current piece and its successor.
2355  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
2356 
2357  if (!PieceI) {
2358  ++I;
2359  continue;
2360  }
2361 
2362  const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2363  const Stmt *s1End = getLocStmt(PieceI->getEndLocation());
2364  const Stmt *level1 = getStmtParent(s1Start, PM);
2365  const Stmt *level2 = getStmtParent(s1End, PM);
2366 
2367  PathPieces::iterator NextI = I; ++NextI;
2368  if (NextI == E)
2369  break;
2370 
2371  auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
2372 
2373  if (!PieceNextI) {
2374  ++I;
2375  continue;
2376  }
2377 
2378  const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2379  const Stmt *s2End = getLocStmt(PieceNextI->getEndLocation());
2380  const Stmt *level3 = getStmtParent(s2Start, PM);
2381  const Stmt *level4 = getStmtParent(s2End, PM);
2382 
2383  // Rule I.
2384  //
2385  // If we have two consecutive control edges whose end/begin locations
2386  // are at the same level (e.g. statements or top-level expressions within
2387  // a compound statement, or siblings share a single ancestor expression),
2388  // then merge them if they have no interesting intermediate event.
2389  //
2390  // For example:
2391  //
2392  // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
2393  // parent is '1'. Here 'x.y.z' represents the hierarchy of statements.
2394  //
2395  // NOTE: this will be limited later in cases where we add barriers
2396  // to prevent this optimization.
2397  //
2398  if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
2399  PieceI->setEndLocation(PieceNextI->getEndLocation());
2400  path.erase(NextI);
2401  hasChanges = true;
2402  continue;
2403  }
2404 
2405  // Rule II.
2406  //
2407  // Eliminate edges between subexpressions and parent expressions
2408  // when the subexpression is consumed.
2409  //
2410  // NOTE: this will be limited later in cases where we add barriers
2411  // to prevent this optimization.
2412  //
2413  if (s1End && s1End == s2Start && level2) {
2414  bool removeEdge = false;
2415  // Remove edges into the increment or initialization of a
2416  // loop that have no interleaving event. This means that
2417  // they aren't interesting.
2418  if (isIncrementOrInitInForLoop(s1End, level2))
2419  removeEdge = true;
2420  // Next only consider edges that are not anchored on
2421  // the condition of a terminator. This are intermediate edges
2422  // that we might want to trim.
2423  else if (!isConditionForTerminator(level2, s1End)) {
2424  // Trim edges on expressions that are consumed by
2425  // the parent expression.
2426  if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
2427  removeEdge = true;
2428  }
2429  // Trim edges where a lexical containment doesn't exist.
2430  // For example:
2431  //
2432  // X -> Y -> Z
2433  //
2434  // If 'Z' lexically contains Y (it is an ancestor) and
2435  // 'X' does not lexically contain Y (it is a descendant OR
2436  // it has no lexical relationship at all) then trim.
2437  //
2438  // This can eliminate edges where we dive into a subexpression
2439  // and then pop back out, etc.
2440  else if (s1Start && s2End &&
2441  lexicalContains(PM, s2Start, s2End) &&
2442  !lexicalContains(PM, s1End, s1Start)) {
2443  removeEdge = true;
2444  }
2445  // Trim edges from a subexpression back to the top level if the
2446  // subexpression is on a different line.
2447  //
2448  // A.1 -> A -> B
2449  // becomes
2450  // A.1 -> B
2451  //
2452  // These edges just look ugly and don't usually add anything.
2453  else if (s1Start && s2End &&
2454  lexicalContains(PM, s1Start, s1End)) {
2455  SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
2456  PieceI->getStartLocation().asLocation());
2457  if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
2458  removeEdge = true;
2459  }
2460  }
2461 
2462  if (removeEdge) {
2463  PieceI->setEndLocation(PieceNextI->getEndLocation());
2464  path.erase(NextI);
2465  hasChanges = true;
2466  continue;
2467  }
2468  }
2469 
2470  // Optimize edges for ObjC fast-enumeration loops.
2471  //
2472  // (X -> collection) -> (collection -> element)
2473  //
2474  // becomes:
2475  //
2476  // (X -> element)
2477  if (s1End == s2Start) {
2478  const ObjCForCollectionStmt *FS =
2479  dyn_cast_or_null<ObjCForCollectionStmt>(level3);
2480  if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
2481  s2End == FS->getElement()) {
2482  PieceI->setEndLocation(PieceNextI->getEndLocation());
2483  path.erase(NextI);
2484  hasChanges = true;
2485  continue;
2486  }
2487  }
2488 
2489  // No changes at this index? Move to the next one.
2490  ++I;
2491  }
2492 
2493  if (!hasChanges) {
2494  // Adjust edges into subexpressions to make them more uniform
2495  // and aesthetically pleasing.
2496  addContextEdges(path, SM, PM, LC);
2497  // Remove "cyclical" edges that include one or more context edges.
2498  removeContextCycles(path, SM, PM);
2499  // Hoist edges originating from branch conditions to branches
2500  // for simple branches.
2501  simplifySimpleBranches(path);
2502  // Remove any puny edges left over after primary optimization pass.
2503  removePunyEdges(path, SM, PM);
2504  // Remove identical events.
2505  removeIdenticalEvents(path);
2506  }
2507 
2508  return hasChanges;
2509 }
2510 
2511 /// Drop the very first edge in a path, which should be a function entry edge.
2512 ///
2513 /// If the first edge is not a function entry edge (say, because the first
2514 /// statement had an invalid source location), this function does nothing.
2515 // FIXME: We should just generate invalid edges anyway and have the optimizer
2516 // deal with them.
2518  LocationContextMap &LCM,
2519  SourceManager &SM) {
2520  const auto *FirstEdge =
2521  dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());
2522  if (!FirstEdge)
2523  return;
2524 
2525  const Decl *D = LCM[&Path]->getDecl();
2527  if (FirstEdge->getStartLocation() != EntryLoc)
2528  return;
2529 
2530  Path.pop_front();
2531 }
2532 
2533 
2534 //===----------------------------------------------------------------------===//
2535 // Methods for BugType and subclasses.
2536 //===----------------------------------------------------------------------===//
2537 void BugType::anchor() { }
2538 
2540 
2541 void BuiltinBug::anchor() {}
2542 
2543 //===----------------------------------------------------------------------===//
2544 // Methods for BugReport and subclasses.
2545 //===----------------------------------------------------------------------===//
2546 
2547 void BugReport::NodeResolver::anchor() {}
2548 
2549 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) {
2550  if (!visitor)
2551  return;
2552 
2553  llvm::FoldingSetNodeID ID;
2554  visitor->Profile(ID);
2555  void *InsertPos;
2556 
2557  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos))
2558  return;
2559 
2560  CallbacksSet.InsertNode(visitor.get(), InsertPos);
2561  Callbacks.push_back(std::move(visitor));
2562  ++ConfigurationChangeToken;
2563 }
2564 
2566  while (!interestingSymbols.empty()) {
2567  popInterestingSymbolsAndRegions();
2568  }
2569 }
2570 
2572  if (DeclWithIssue)
2573  return DeclWithIssue;
2574 
2575  const ExplodedNode *N = getErrorNode();
2576  if (!N)
2577  return nullptr;
2578 
2579  const LocationContext *LC = N->getLocationContext();
2580  return LC->getCurrentStackFrame()->getDecl();
2581 }
2582 
2583 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2584  hash.AddPointer(&BT);
2585  hash.AddString(Description);
2586  PathDiagnosticLocation UL = getUniqueingLocation();
2587  if (UL.isValid()) {
2588  UL.Profile(hash);
2589  } else if (Location.isValid()) {
2590  Location.Profile(hash);
2591  } else {
2592  assert(ErrorNode);
2593  hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2594  }
2595 
2596  for (SourceRange range : Ranges) {
2597  if (!range.isValid())
2598  continue;
2599  hash.AddInteger(range.getBegin().getRawEncoding());
2600  hash.AddInteger(range.getEnd().getRawEncoding());
2601  }
2602 }
2603 
2605  if (!sym)
2606  return;
2607 
2608  // If the symbol wasn't already in our set, note a configuration change.
2609  if (getInterestingSymbols().insert(sym).second)
2610  ++ConfigurationChangeToken;
2611 
2612  if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
2613  getInterestingRegions().insert(meta->getRegion());
2614 }
2615 
2617  if (!R)
2618  return;
2619 
2620  // If the base region wasn't already in our set, note a configuration change.
2621  R = R->getBaseRegion();
2622  if (getInterestingRegions().insert(R).second)
2623  ++ConfigurationChangeToken;
2624 
2625  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2626  getInterestingSymbols().insert(SR->getSymbol());
2627 }
2628 
2630  markInteresting(V.getAsRegion());
2631  markInteresting(V.getAsSymbol());
2632 }
2633 
2635  if (!LC)
2636  return;
2637  InterestingLocationContexts.insert(LC);
2638 }
2639 
2641  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2642 }
2643 
2645  if (!sym)
2646  return false;
2647  // We don't currently consider metadata symbols to be interesting
2648  // even if we know their region is interesting. Is that correct behavior?
2649  return getInterestingSymbols().count(sym);
2650 }
2651 
2653  if (!R)
2654  return false;
2655  R = R->getBaseRegion();
2656  bool b = getInterestingRegions().count(R);
2657  if (b)
2658  return true;
2659  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2660  return getInterestingSymbols().count(SR->getSymbol());
2661  return false;
2662 }
2663 
2665  if (!LC)
2666  return false;
2667  return InterestingLocationContexts.count(LC);
2668 }
2669 
2670 void BugReport::lazyInitializeInterestingSets() {
2671  if (interestingSymbols.empty()) {
2672  interestingSymbols.push_back(new Symbols());
2673  interestingRegions.push_back(new Regions());
2674  }
2675 }
2676 
2677 BugReport::Symbols &BugReport::getInterestingSymbols() {
2678  lazyInitializeInterestingSets();
2679  return *interestingSymbols.back();
2680 }
2681 
2682 BugReport::Regions &BugReport::getInterestingRegions() {
2683  lazyInitializeInterestingSets();
2684  return *interestingRegions.back();
2685 }
2686 
2687 void BugReport::pushInterestingSymbolsAndRegions() {
2688  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2689  interestingRegions.push_back(new Regions(getInterestingRegions()));
2690 }
2691 
2692 void BugReport::popInterestingSymbolsAndRegions() {
2693  delete interestingSymbols.pop_back_val();
2694  delete interestingRegions.pop_back_val();
2695 }
2696 
2697 const Stmt *BugReport::getStmt() const {
2698  if (!ErrorNode)
2699  return nullptr;
2700 
2701  ProgramPoint ProgP = ErrorNode->getLocation();
2702  const Stmt *S = nullptr;
2703 
2704  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2705  CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2706  if (BE->getBlock() == &Exit)
2707  S = GetPreviousStmt(ErrorNode);
2708  }
2709  if (!S)
2710  S = PathDiagnosticLocation::getStmt(ErrorNode);
2711 
2712  return S;
2713 }
2714 
2715 llvm::iterator_range<BugReport::ranges_iterator> BugReport::getRanges() {
2716  // If no custom ranges, add the range of the statement corresponding to
2717  // the error node.
2718  if (Ranges.empty()) {
2719  if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
2720  addRange(E->getSourceRange());
2721  else
2722  return llvm::make_range(ranges_iterator(), ranges_iterator());
2723  }
2724 
2725  // User-specified absence of range info.
2726  if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2727  return llvm::make_range(ranges_iterator(), ranges_iterator());
2728 
2729  return llvm::make_range(Ranges.begin(), Ranges.end());
2730 }
2731 
2733  if (ErrorNode) {
2734  assert(!Location.isValid() &&
2735  "Either Location or ErrorNode should be specified but not both.");
2736  return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2737  }
2738 
2739  assert(Location.isValid());
2740  return Location;
2741 }
2742 
2743 //===----------------------------------------------------------------------===//
2744 // Methods for BugReporter and subclasses.
2745 //===----------------------------------------------------------------------===//
2746 
2750 
2751 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2752 
2754 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2755 
2757  FlushReports();
2758 
2759  // Free the bug reports we are tracking.
2760  typedef std::vector<BugReportEquivClass *> ContTy;
2761  for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
2762  I != E; ++I) {
2763  delete *I;
2764  }
2765 }
2766 
2768  if (BugTypes.isEmpty())
2769  return;
2770 
2771  // First flush the warnings for each BugType. This may end up creating new
2772  // warnings and new BugTypes.
2773  // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2774  // Turn NSErrorChecker into a proper checker and remove this.
2775  SmallVector<const BugType *, 16> bugTypes(BugTypes.begin(), BugTypes.end());
2777  I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
2778  const_cast<BugType*>(*I)->FlushReports(*this);
2779 
2780  // We need to flush reports in deterministic order to ensure the order
2781  // of the reports is consistent between runs.
2782  typedef std::vector<BugReportEquivClass *> ContVecTy;
2783  for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end();
2784  EI != EE; ++EI){
2785  BugReportEquivClass& EQ = **EI;
2786  FlushReport(EQ);
2787  }
2788 
2789  // BugReporter owns and deletes only BugTypes created implicitly through
2790  // EmitBasicReport.
2791  // FIXME: There are leaks from checkers that assume that the BugTypes they
2792  // create will be destroyed by the BugReporter.
2793  llvm::DeleteContainerSeconds(StrBugTypes);
2794 
2795  // Remove all references to the BugType objects.
2796  BugTypes = F.getEmptySet();
2797 }
2798 
2799 //===----------------------------------------------------------------------===//
2800 // PathDiagnostics generation.
2801 //===----------------------------------------------------------------------===//
2802 
2803 namespace {
2804 /// A wrapper around a report graph, which contains only a single path, and its
2805 /// node maps.
2806 class ReportGraph {
2807 public:
2808  InterExplodedGraphMap BackMap;
2809  std::unique_ptr<ExplodedGraph> Graph;
2810  const ExplodedNode *ErrorNode;
2811  size_t Index;
2812 };
2813 
2814 /// A wrapper around a trimmed graph and its node maps.
2815 class TrimmedGraph {
2816  InterExplodedGraphMap InverseMap;
2817 
2818  typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy;
2819  PriorityMapTy PriorityMap;
2820 
2821  typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair;
2822  SmallVector<NodeIndexPair, 32> ReportNodes;
2823 
2824  std::unique_ptr<ExplodedGraph> G;
2825 
2826  /// A helper class for sorting ExplodedNodes by priority.
2827  template <bool Descending>
2828  class PriorityCompare {
2829  const PriorityMapTy &PriorityMap;
2830 
2831  public:
2832  PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2833 
2834  bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2835  PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2836  PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2837  PriorityMapTy::const_iterator E = PriorityMap.end();
2838 
2839  if (LI == E)
2840  return Descending;
2841  if (RI == E)
2842  return !Descending;
2843 
2844  return Descending ? LI->second > RI->second
2845  : LI->second < RI->second;
2846  }
2847 
2848  bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2849  return (*this)(LHS.first, RHS.first);
2850  }
2851  };
2852 
2853 public:
2854  TrimmedGraph(const ExplodedGraph *OriginalGraph,
2856 
2857  bool popNextReportGraph(ReportGraph &GraphWrapper);
2858 };
2859 }
2860 
2861 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2863  // The trimmed graph is created in the body of the constructor to ensure
2864  // that the DenseMaps have been initialized already.
2865  InterExplodedGraphMap ForwardMap;
2866  G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
2867 
2868  // Find the (first) error node in the trimmed graph. We just need to consult
2869  // the node map which maps from nodes in the original graph to nodes
2870  // in the new graph.
2871  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2872 
2873  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2874  if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2875  ReportNodes.push_back(std::make_pair(NewNode, i));
2876  RemainingNodes.insert(NewNode);
2877  }
2878  }
2879 
2880  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2881 
2882  // Perform a forward BFS to find all the shortest paths.
2883  std::queue<const ExplodedNode *> WS;
2884 
2885  assert(G->num_roots() == 1);
2886  WS.push(*G->roots_begin());
2887  unsigned Priority = 0;
2888 
2889  while (!WS.empty()) {
2890  const ExplodedNode *Node = WS.front();
2891  WS.pop();
2892 
2893  PriorityMapTy::iterator PriorityEntry;
2894  bool IsNew;
2895  std::tie(PriorityEntry, IsNew) =
2896  PriorityMap.insert(std::make_pair(Node, Priority));
2897  ++Priority;
2898 
2899  if (!IsNew) {
2900  assert(PriorityEntry->second <= Priority);
2901  continue;
2902  }
2903 
2904  if (RemainingNodes.erase(Node))
2905  if (RemainingNodes.empty())
2906  break;
2907 
2909  E = Node->succ_end();
2910  I != E; ++I)
2911  WS.push(*I);
2912  }
2913 
2914  // Sort the error paths from longest to shortest.
2915  std::sort(ReportNodes.begin(), ReportNodes.end(),
2916  PriorityCompare<true>(PriorityMap));
2917 }
2918 
2919 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2920  if (ReportNodes.empty())
2921  return false;
2922 
2923  const ExplodedNode *OrigN;
2924  std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2925  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2926  "error node not accessible from root");
2927 
2928  // Create a new graph with a single path. This is the graph
2929  // that will be returned to the caller.
2930  auto GNew = llvm::make_unique<ExplodedGraph>();
2931  GraphWrapper.BackMap.clear();
2932 
2933  // Now walk from the error node up the BFS path, always taking the
2934  // predeccessor with the lowest number.
2935  ExplodedNode *Succ = nullptr;
2936  while (true) {
2937  // Create the equivalent node in the new graph with the same state
2938  // and location.
2939  ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
2940  OrigN->isSink());
2941 
2942  // Store the mapping to the original node.
2943  InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2944  assert(IMitr != InverseMap.end() && "No mapping to original node.");
2945  GraphWrapper.BackMap[NewN] = IMitr->second;
2946 
2947  // Link up the new node with the previous node.
2948  if (Succ)
2949  Succ->addPredecessor(NewN, *GNew);
2950  else
2951  GraphWrapper.ErrorNode = NewN;
2952 
2953  Succ = NewN;
2954 
2955  // Are we at the final node?
2956  if (OrigN->pred_empty()) {
2957  GNew->addRoot(NewN);
2958  break;
2959  }
2960 
2961  // Find the next predeccessor node. We choose the node that is marked
2962  // with the lowest BFS number.
2963  OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2964  PriorityCompare<false>(PriorityMap));
2965  }
2966 
2967  GraphWrapper.Graph = std::move(GNew);
2968 
2969  return true;
2970 }
2971 
2972 
2973 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2974 /// and collapses PathDiagosticPieces that are expanded by macros.
2975 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2976  typedef std::vector<
2977  std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>
2978  MacroStackTy;
2979 
2980  typedef std::vector<std::shared_ptr<PathDiagnosticPiece>> PiecesTy;
2981 
2982  MacroStackTy MacroStack;
2983  PiecesTy Pieces;
2984 
2985  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2986  I!=E; ++I) {
2987 
2988  auto &piece = *I;
2989 
2990  // Recursively compact calls.
2991  if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {
2992  CompactPathDiagnostic(call->path, SM);
2993  }
2994 
2995  // Get the location of the PathDiagnosticPiece.
2996  const FullSourceLoc Loc = piece->getLocation().asLocation();
2997 
2998  // Determine the instantiation location, which is the location we group
2999  // related PathDiagnosticPieces.
3000  SourceLocation InstantiationLoc = Loc.isMacroID() ?
3001  SM.getExpansionLoc(Loc) :
3002  SourceLocation();
3003 
3004  if (Loc.isFileID()) {
3005  MacroStack.clear();
3006  Pieces.push_back(piece);
3007  continue;
3008  }
3009 
3010  assert(Loc.isMacroID());
3011 
3012  // Is the PathDiagnosticPiece within the same macro group?
3013  if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
3014  MacroStack.back().first->subPieces.push_back(piece);
3015  continue;
3016  }
3017 
3018  // We aren't in the same group. Are we descending into a new macro
3019  // or are part of an old one?
3020  std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;
3021 
3022  SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
3023  SM.getExpansionLoc(Loc) :
3024  SourceLocation();
3025 
3026  // Walk the entire macro stack.
3027  while (!MacroStack.empty()) {
3028  if (InstantiationLoc == MacroStack.back().second) {
3029  MacroGroup = MacroStack.back().first;
3030  break;
3031  }
3032 
3033  if (ParentInstantiationLoc == MacroStack.back().second) {
3034  MacroGroup = MacroStack.back().first;
3035  break;
3036  }
3037 
3038  MacroStack.pop_back();
3039  }
3040 
3041  if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
3042  // Create a new macro group and add it to the stack.
3043  auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(
3044  PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
3045 
3046  if (MacroGroup)
3047  MacroGroup->subPieces.push_back(NewGroup);
3048  else {
3049  assert(InstantiationLoc.isFileID());
3050  Pieces.push_back(NewGroup);
3051  }
3052 
3053  MacroGroup = NewGroup;
3054  MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
3055  }
3056 
3057  // Finally, add the PathDiagnosticPiece to the group.
3058  MacroGroup->subPieces.push_back(piece);
3059  }
3060 
3061  // Now take the pieces and construct a new PathDiagnostic.
3062  path.clear();
3063 
3064  path.insert(path.end(), Pieces.begin(), Pieces.end());
3065 }
3066 
3069  ArrayRef<BugReport *> &bugReports) {
3070  assert(!bugReports.empty());
3071 
3072  bool HasValid = false;
3073  bool HasInvalid = false;
3075  for (ArrayRef<BugReport*>::iterator I = bugReports.begin(),
3076  E = bugReports.end(); I != E; ++I) {
3077  if ((*I)->isValid()) {
3078  HasValid = true;
3079  errorNodes.push_back((*I)->getErrorNode());
3080  } else {
3081  // Keep the errorNodes list in sync with the bugReports list.
3082  HasInvalid = true;
3083  errorNodes.push_back(nullptr);
3084  }
3085  }
3086 
3087  // If all the reports have been marked invalid by a previous path generation,
3088  // we're done.
3089  if (!HasValid)
3090  return false;
3091 
3092  typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme;
3093  PathGenerationScheme ActiveScheme = PC.getGenerationScheme();
3094 
3095  if (ActiveScheme == PathDiagnosticConsumer::Extensive) {
3096  AnalyzerOptions &options = getAnalyzerOptions();
3097  if (options.getBooleanOption("path-diagnostics-alternate", true)) {
3099  }
3100  }
3101 
3102  TrimmedGraph TrimG(&getGraph(), errorNodes);
3103  ReportGraph ErrorGraph;
3104 
3105  while (TrimG.popNextReportGraph(ErrorGraph)) {
3106  // Find the BugReport with the original location.
3107  assert(ErrorGraph.Index < bugReports.size());
3108  BugReport *R = bugReports[ErrorGraph.Index];
3109  assert(R && "No original report found for sliced graph.");
3110  assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
3111 
3112  // Start building the path diagnostic...
3113  PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
3114  const ExplodedNode *N = ErrorGraph.ErrorNode;
3115 
3116  // Register additional node visitors.
3117  R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
3118  R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
3119  R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
3120  R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
3121 
3122  BugReport::VisitorList visitors;
3123  unsigned origReportConfigToken, finalReportConfigToken;
3124  LocationContextMap LCM;
3125 
3126  // While generating diagnostics, it's possible the visitors will decide
3127  // new symbols and regions are interesting, or add other visitors based on
3128  // the information they find. If they do, we need to regenerate the path
3129  // based on our new report configuration.
3130  do {
3131  // Get a clean copy of all the visitors.
3132  for (BugReport::visitor_iterator I = R->visitor_begin(),
3133  E = R->visitor_end(); I != E; ++I)
3134  visitors.push_back((*I)->clone());
3135 
3136  // Clear out the active path from any previous work.
3137  PD.resetPath();
3138  origReportConfigToken = R->getConfigurationChangeToken();
3139 
3140  // Generate the very last diagnostic piece - the piece is visible before
3141  // the trace is expanded.
3142  std::unique_ptr<PathDiagnosticPiece> LastPiece;
3143  for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
3144  I != E; ++I) {
3145  if (std::unique_ptr<PathDiagnosticPiece> Piece =
3146  (*I)->getEndPath(PDB, N, *R)) {
3147  assert (!LastPiece &&
3148  "There can only be one final piece in a diagnostic.");
3149  LastPiece = std::move(Piece);
3150  }
3151  }
3152 
3153  if (ActiveScheme != PathDiagnosticConsumer::None) {
3154  if (!LastPiece)
3155  LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
3156  assert(LastPiece);
3157  PD.setEndOfPath(std::move(LastPiece));
3158  }
3159 
3160  // Make sure we get a clean location context map so we don't
3161  // hold onto old mappings.
3162  LCM.clear();
3163 
3164  switch (ActiveScheme) {
3166  GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3167  break;
3169  GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3170  break;
3172  GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors);
3173  break;
3175  GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors);
3176  break;
3177  }
3178 
3179  // Clean up the visitors we used.
3180  visitors.clear();
3181 
3182  // Did anything change while generating this path?
3183  finalReportConfigToken = R->getConfigurationChangeToken();
3184  } while (finalReportConfigToken != origReportConfigToken);
3185 
3186  if (!R->isValid())
3187  continue;
3188 
3189  // Finally, prune the diagnostic path of uninteresting stuff.
3190  if (!PD.path.empty()) {
3191  if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) {
3192  bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);
3193  assert(stillHasNotes);
3194  (void)stillHasNotes;
3195  }
3196 
3197  // Redirect all call pieces to have valid locations.
3200 
3201  if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) {
3202  SourceManager &SM = getSourceManager();
3203 
3204  // Reduce the number of edges from a very conservative set
3205  // to an aesthetically pleasing subset that conveys the
3206  // necessary information.
3207  OptimizedCallsSet OCS;
3208  while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {}
3209 
3210  // Drop the very first function-entry edge. It's not really necessary
3211  // for top-level functions.
3213  }
3214 
3215  // Remove messages that are basically the same, and edges that may not
3216  // make sense.
3217  // We have to do this after edge optimization in the Extensive mode.
3220  }
3221 
3222  // We found a report and didn't suppress it.
3223  return true;
3224  }
3225 
3226  // We suppressed all the reports in this equivalence class.
3227  assert(!HasInvalid && "Inconsistent suppression");
3228  (void)HasInvalid;
3229  return false;
3230 }
3231 
3233  BugTypes = F.add(BugTypes, BT);
3234 }
3235 
3236 void BugReporter::emitReport(std::unique_ptr<BugReport> R) {
3237  if (const ExplodedNode *E = R->getErrorNode()) {
3238  // An error node must either be a sink or have a tag, otherwise
3239  // it could get reclaimed before the path diagnostic is created.
3240  assert((E->isSink() || E->getLocation().getTag()) &&
3241  "Error node must either be a sink or have a tag");
3242 
3243  const AnalysisDeclContext *DeclCtx =
3244  E->getLocationContext()->getAnalysisDeclContext();
3245  // The source of autosynthesized body can be handcrafted AST or a model
3246  // file. The locations from handcrafted ASTs have no valid source locations
3247  // and have to be discarded. Locations from model files should be preserved
3248  // for processing and reporting.
3249  if (DeclCtx->isBodyAutosynthesized() &&
3251  return;
3252  }
3253 
3254  bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid();
3255  assert(ValidSourceLoc);
3256  // If we mess up in a release build, we'd still prefer to just drop the bug
3257  // instead of trying to go on.
3258  if (!ValidSourceLoc)
3259  return;
3260 
3261  // Compute the bug report's hash to determine its equivalence class.
3262  llvm::FoldingSetNodeID ID;
3263  R->Profile(ID);
3264 
3265  // Lookup the equivance class. If there isn't one, create it.
3266  BugType& BT = R->getBugType();
3267  Register(&BT);
3268  void *InsertPos;
3269  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
3270 
3271  if (!EQ) {
3272  EQ = new BugReportEquivClass(std::move(R));
3273  EQClasses.InsertNode(EQ, InsertPos);
3274  EQClassesVector.push_back(EQ);
3275  } else
3276  EQ->AddReport(std::move(R));
3277 }
3278 
3279 
3280 //===----------------------------------------------------------------------===//
3281 // Emitting reports in equivalence classes.
3282 //===----------------------------------------------------------------------===//
3283 
3284 namespace {
3285 struct FRIEC_WLItem {
3286  const ExplodedNode *N;
3288 
3289  FRIEC_WLItem(const ExplodedNode *n)
3290  : N(n), I(N->succ_begin()), E(N->succ_end()) {}
3291 };
3292 }
3293 
3294 static const CFGBlock *findBlockForNode(const ExplodedNode *N) {
3295  ProgramPoint P = N->getLocation();
3296  if (auto BEP = P.getAs<BlockEntrance>())
3297  return BEP->getBlock();
3298 
3299  // Find the node's current statement in the CFG.
3300  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
3302  ->getCFGStmtMap()->getBlock(S);
3303 
3304  return nullptr;
3305 }
3306 
3307 static BugReport *
3309  SmallVectorImpl<BugReport*> &bugReports) {
3310 
3311  BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
3312  assert(I != E);
3313  BugType& BT = I->getBugType();
3314 
3315  // If we don't need to suppress any of the nodes because they are
3316  // post-dominated by a sink, simply add all the nodes in the equivalence class
3317  // to 'Nodes'. Any of the reports will serve as a "representative" report.
3318  if (!BT.isSuppressOnSink()) {
3319  BugReport *R = &*I;
3320  for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
3321  const ExplodedNode *N = I->getErrorNode();
3322  if (N) {
3323  R = &*I;
3324  bugReports.push_back(R);
3325  }
3326  }
3327  return R;
3328  }
3329 
3330  // For bug reports that should be suppressed when all paths are post-dominated
3331  // by a sink node, iterate through the reports in the equivalence class
3332  // until we find one that isn't post-dominated (if one exists). We use a
3333  // DFS traversal of the ExplodedGraph to find a non-sink node. We could write
3334  // this as a recursive function, but we don't want to risk blowing out the
3335  // stack for very long paths.
3336  BugReport *exampleReport = nullptr;
3337 
3338  for (; I != E; ++I) {
3339  const ExplodedNode *errorNode = I->getErrorNode();
3340 
3341  if (!errorNode)
3342  continue;
3343  if (errorNode->isSink()) {
3344  llvm_unreachable(
3345  "BugType::isSuppressSink() should not be 'true' for sink end nodes");
3346  }
3347  // No successors? By definition this nodes isn't post-dominated by a sink.
3348  if (errorNode->succ_empty()) {
3349  bugReports.push_back(&*I);
3350  if (!exampleReport)
3351  exampleReport = &*I;
3352  continue;
3353  }
3354 
3355  // See if we are in a no-return CFG block. If so, treat this similarly
3356  // to being post-dominated by a sink. This works better when the analysis
3357  // is incomplete and we have never reached a no-return function
3358  // we're post-dominated by.
3359  // This is not quite enough to handle the incomplete analysis case.
3360  // We may be post-dominated in subsequent blocks, or even
3361  // inter-procedurally. However, it is not clear if more complicated
3362  // cases are generally worth suppressing.
3363  if (const CFGBlock *B = findBlockForNode(errorNode))
3364  if (B->hasNoReturnElement())
3365  continue;
3366 
3367  // At this point we know that 'N' is not a sink and it has at least one
3368  // successor. Use a DFS worklist to find a non-sink end-of-path node.
3369  typedef FRIEC_WLItem WLItem;
3370  typedef SmallVector<WLItem, 10> DFSWorkList;
3371  llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
3372 
3373  DFSWorkList WL;
3374  WL.push_back(errorNode);
3375  Visited[errorNode] = 1;
3376 
3377  while (!WL.empty()) {
3378  WLItem &WI = WL.back();
3379  assert(!WI.N->succ_empty());
3380 
3381  for (; WI.I != WI.E; ++WI.I) {
3382  const ExplodedNode *Succ = *WI.I;
3383  // End-of-path node?
3384  if (Succ->succ_empty()) {
3385  // If we found an end-of-path node that is not a sink.
3386  if (!Succ->isSink()) {
3387  bugReports.push_back(&*I);
3388  if (!exampleReport)
3389  exampleReport = &*I;
3390  WL.clear();
3391  break;
3392  }
3393  // Found a sink? Continue on to the next successor.
3394  continue;
3395  }
3396  // Mark the successor as visited. If it hasn't been explored,
3397  // enqueue it to the DFS worklist.
3398  unsigned &mark = Visited[Succ];
3399  if (!mark) {
3400  mark = 1;
3401  WL.push_back(Succ);
3402  break;
3403  }
3404  }
3405 
3406  // The worklist may have been cleared at this point. First
3407  // check if it is empty before checking the last item.
3408  if (!WL.empty() && &WL.back() == &WI)
3409  WL.pop_back();
3410  }
3411  }
3412 
3413  // ExampleReport will be NULL if all the nodes in the equivalence class
3414  // were post-dominated by sinks.
3415  return exampleReport;
3416 }
3417 
3418 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
3419  SmallVector<BugReport*, 10> bugReports;
3420  BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
3421  if (exampleReport) {
3422  for (PathDiagnosticConsumer *PDC : getPathDiagnosticConsumers()) {
3423  FlushReport(exampleReport, *PDC, bugReports);
3424  }
3425  }
3426 }
3427 
3428 void BugReporter::FlushReport(BugReport *exampleReport,
3430  ArrayRef<BugReport*> bugReports) {
3431 
3432  // FIXME: Make sure we use the 'R' for the path that was actually used.
3433  // Probably doesn't make a difference in practice.
3434  BugType& BT = exampleReport->getBugType();
3435 
3436  std::unique_ptr<PathDiagnostic> D(new PathDiagnostic(
3437  exampleReport->getBugType().getCheckName(),
3438  exampleReport->getDeclWithIssue(), exampleReport->getBugType().getName(),
3439  exampleReport->getDescription(),
3440  exampleReport->getShortDescription(/*Fallback=*/false), BT.getCategory(),
3441  exampleReport->getUniqueingLocation(),
3442  exampleReport->getUniqueingDecl()));
3443 
3444  if (exampleReport->isPathSensitive()) {
3445  // Generate the full path diagnostic, using the generation scheme
3446  // specified by the PathDiagnosticConsumer. Note that we have to generate
3447  // path diagnostics even for consumers which do not support paths, because
3448  // the BugReporterVisitors may mark this bug as a false positive.
3449  assert(!bugReports.empty());
3450 
3451  MaxBugClassSize =
3452  std::max(bugReports.size(), static_cast<size_t>(MaxBugClassSize));
3453 
3454  if (!generatePathDiagnostic(*D.get(), PD, bugReports))
3455  return;
3456 
3457  MaxValidBugClassSize =
3458  std::max(bugReports.size(), static_cast<size_t>(MaxValidBugClassSize));
3459 
3460  // Examine the report and see if the last piece is in a header. Reset the
3461  // report location to the last piece in the main source file.
3462  AnalyzerOptions &Opts = getAnalyzerOptions();
3463  if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll)
3464  D->resetDiagnosticLocationToMainFile();
3465  }
3466 
3467  // If the path is empty, generate a single step path with the location
3468  // of the issue.
3469  if (D->path.empty()) {
3470  PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
3471  auto piece = llvm::make_unique<PathDiagnosticEventPiece>(
3472  L, exampleReport->getDescription());
3473  for (SourceRange Range : exampleReport->getRanges())
3474  piece->addRange(Range);
3475  D->setEndOfPath(std::move(piece));
3476  }
3477 
3478  PathPieces &Pieces = D->getMutablePieces();
3479  if (getAnalyzerOptions().shouldDisplayNotesAsEvents()) {
3480  // For path diagnostic consumers that don't support extra notes,
3481  // we may optionally convert those to path notes.
3482  for (auto I = exampleReport->getNotes().rbegin(),
3483  E = exampleReport->getNotes().rend(); I != E; ++I) {
3484  PathDiagnosticNotePiece *Piece = I->get();
3485  auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>(
3486  Piece->getLocation(), Piece->getString());
3487  for (const auto &R: Piece->getRanges())
3488  ConvertedPiece->addRange(R);
3489 
3490  Pieces.push_front(std::move(ConvertedPiece));
3491  }
3492  } else {
3493  for (auto I = exampleReport->getNotes().rbegin(),
3494  E = exampleReport->getNotes().rend(); I != E; ++I)
3495  Pieces.push_front(*I);
3496  }
3497 
3498  // Get the meta data.
3499  const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
3500  for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
3501  e = Meta.end(); i != e; ++i) {
3502  D->addMeta(*i);
3503  }
3504 
3505  PD.HandlePathDiagnostic(std::move(D));
3506 }
3507 
3508 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3509  const CheckerBase *Checker,
3510  StringRef Name, StringRef Category,
3511  StringRef Str, PathDiagnosticLocation Loc,
3512  ArrayRef<SourceRange> Ranges) {
3513  EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str,
3514  Loc, Ranges);
3515 }
3516 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3518  StringRef name, StringRef category,
3519  StringRef str, PathDiagnosticLocation Loc,
3520  ArrayRef<SourceRange> Ranges) {
3521 
3522  // 'BT' is owned by BugReporter.
3523  BugType *BT = getBugTypeForName(CheckName, name, category);
3524  auto R = llvm::make_unique<BugReport>(*BT, str, Loc);
3525  R->setDeclWithIssue(DeclWithIssue);
3526  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
3527  I != E; ++I)
3528  R->addRange(*I);
3529  emitReport(std::move(R));
3530 }
3531 
3532 BugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name,
3533  StringRef category) {
3534  SmallString<136> fullDesc;
3535  llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name
3536  << ":" << category;
3537  BugType *&BT = StrBugTypes[fullDesc];
3538  if (!BT)
3539  BT = new BugType(CheckName, name, category);
3540  return BT;
3541 }
3542 
3543 LLVM_DUMP_METHOD void PathPieces::dump() const {
3544  unsigned index = 0;
3545  for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
3546  llvm::errs() << "[" << index++ << "] ";
3547  (*I)->dump();
3548  llvm::errs() << "\n";
3549  }
3550 }
3551 
3552 LLVM_DUMP_METHOD void PathDiagnosticCallPiece::dump() const {
3553  llvm::errs() << "CALL\n--------------\n";
3554 
3555  if (const Stmt *SLoc = getLocStmt(getLocation()))
3556  SLoc->dump();
3557  else if (const NamedDecl *ND = dyn_cast<NamedDecl>(getCallee()))
3558  llvm::errs() << *ND << "\n";
3559  else
3560  getLocation().dump();
3561 }
3562 
3563 LLVM_DUMP_METHOD void PathDiagnosticEventPiece::dump() const {
3564  llvm::errs() << "EVENT\n--------------\n";
3565  llvm::errs() << getString() << "\n";
3566  llvm::errs() << " ---- at ----\n";
3567  getLocation().dump();
3568 }
3569 
3570 LLVM_DUMP_METHOD void PathDiagnosticControlFlowPiece::dump() const {
3571  llvm::errs() << "CONTROL\n--------------\n";
3572  getStartLocation().dump();
3573  llvm::errs() << " ---- to ----\n";
3574  getEndLocation().dump();
3575 }
3576 
3577 LLVM_DUMP_METHOD void PathDiagnosticMacroPiece::dump() const {
3578  llvm::errs() << "MACRO\n--------------\n";
3579  // FIXME: Print which macro is being invoked.
3580 }
3581 
3582 LLVM_DUMP_METHOD void PathDiagnosticNotePiece::dump() const {
3583  llvm::errs() << "NOTE\n--------------\n";
3584  llvm::errs() << getString() << "\n";
3585  llvm::errs() << " ---- at ----\n";
3586  getLocation().dump();
3587 }
3588 
3589 LLVM_DUMP_METHOD void PathDiagnosticLocation::dump() const {
3590  if (!isValid()) {
3591  llvm::errs() << "<INVALID>\n";
3592  return;
3593  }
3594 
3595  switch (K) {
3596  case RangeK:
3597  // FIXME: actually print the range.
3598  llvm::errs() << "<range>\n";
3599  break;
3600  case SingleLocK:
3601  asLocation().dump();
3602  llvm::errs() << "\n";
3603  break;
3604  case StmtK:
3605  if (S)
3606  S->dump();
3607  else
3608  llvm::errs() << "<NULL STMT>\n";
3609  break;
3610  case DeclK:
3611  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(D))
3612  llvm::errs() << *ND << "\n";
3613  else if (isa<BlockDecl>(D))
3614  // FIXME: Make this nicer.
3615  llvm::errs() << "<block>\n";
3616  else if (D)
3617  llvm::errs() << "<unknown decl>\n";
3618  else
3619  llvm::errs() << "<NULL DECL>\n";
3620  break;
3621  }
3622 }
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:1586
Expr * getLHS() const
Definition: Expr.h:3234
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:553
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:2511
Defines the SourceManager interface.
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:80
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:2955
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:691
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:570
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:1402
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)
void pushActivePath(PathPieces *p)
int Category
Definition: Format.cpp:1247
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:2914
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:2390
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:725
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
ArrayRef< ParmVarDecl * >::const_iterator param_const_iterator
Definition: Decl.h:2029
ConditionalOperator - The ?: ternary operator.
Definition: Expr.h:3189
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:354
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 set of possible language-specific address spaces.
Definition: AddressSpaces.h:27
SymbolicRegion - A special, "non-concrete" region.
Definition: MemRegion.h:707
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:3223
ProgramState - This class encapsulates:
Definition: ProgramState.h:73
Expr - This represents one expression.
Definition: Expr.h:105
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:4580
pred_iterator pred_end()
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:517
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.
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:1236
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:885
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:641
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:652
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:47
PathDiagnosticLocation getLocation() const override
static const Stmt * getEnclosingParent(const Stmt *S, const ParentMap &PM)
static bool isLogicalOp(Opcode Opc)
Definition: Expr.h:3034
static void removePunyEdges(PathPieces &path, SourceManager &SM, ParentMap &PM)
Expr * getLHS() const
Definition: Expr.h:2958
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:2563
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:744
SymbolMetadata - Represents path-dependent metadata about a specific region.
StringRef getShortDescription(bool UseFallback=true) const
Definition: BugReporter.h:198
char __ovld __cnfn max(char x, char y)
Returns y if x < y, otherwise it returns x.
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:12750
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:3235
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...
static void removeContextCycles(PathPieces &Path, SourceManager &SM, ParentMap &PM)
Eliminate two-edge cycles created by addContextEdges().
const MemRegion * getBaseRegion() const
Definition: MemRegion.cpp:1089
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:2165
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:949
Expr * getRHS() const
Definition: Expr.h:2960
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
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:2359
static const char * getTag()
Return the tag associated with this visitor.
CFGBlock & getExit()
Definition: CFG.h:830
static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term)