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