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