clang  8.0.0svn
BugReporter.cpp
Go to the documentation of this file.
1 //===- BugReporter.cpp - Generate PathDiagnostics for bugs ----------------===//
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/Decl.h"
17 #include "clang/AST/DeclBase.h"
18 #include "clang/AST/DeclObjC.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/ParentMap.h"
22 #include "clang/AST/Stmt.h"
23 #include "clang/AST/StmtCXX.h"
24 #include "clang/AST/StmtObjC.h"
26 #include "clang/Analysis/CFG.h"
29 #include "clang/Basic/LLVM.h"
44 #include "llvm/ADT/ArrayRef.h"
45 #include "llvm/ADT/DenseMap.h"
46 #include "llvm/ADT/DenseSet.h"
47 #include "llvm/ADT/FoldingSet.h"
48 #include "llvm/ADT/None.h"
49 #include "llvm/ADT/Optional.h"
50 #include "llvm/ADT/STLExtras.h"
51 #include "llvm/ADT/SmallPtrSet.h"
52 #include "llvm/ADT/SmallString.h"
53 #include "llvm/ADT/SmallVector.h"
54 #include "llvm/ADT/Statistic.h"
55 #include "llvm/ADT/StringRef.h"
56 #include "llvm/ADT/iterator_range.h"
57 #include "llvm/Support/Casting.h"
58 #include "llvm/Support/Compiler.h"
59 #include "llvm/Support/ErrorHandling.h"
60 #include "llvm/Support/MemoryBuffer.h"
61 #include "llvm/Support/raw_ostream.h"
62 #include <algorithm>
63 #include <cassert>
64 #include <cstddef>
65 #include <iterator>
66 #include <memory>
67 #include <queue>
68 #include <string>
69 #include <tuple>
70 #include <utility>
71 #include <vector>
72 
73 using namespace clang;
74 using namespace ento;
75 
76 #define DEBUG_TYPE "BugReporter"
77 
78 STATISTIC(MaxBugClassSize,
79  "The maximum number of bug reports in the same equivalence class");
80 STATISTIC(MaxValidBugClassSize,
81  "The maximum number of bug reports in the same equivalence class "
82  "where at least one report is valid (not suppressed)");
83 
84 BugReporterVisitor::~BugReporterVisitor() = default;
85 
86 void BugReporterContext::anchor() {}
87 
88 //===----------------------------------------------------------------------===//
89 // Helper routines for walking the ExplodedGraph and fetching statements.
90 //===----------------------------------------------------------------------===//
91 
92 static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
93  for (N = N->getFirstPred(); N; N = N->getFirstPred())
94  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
95  return S;
96 
97  return nullptr;
98 }
99 
100 static inline const Stmt*
102  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
103  return S;
104 
105  return GetPreviousStmt(N);
106 }
107 
108 //===----------------------------------------------------------------------===//
109 // Diagnostic cleanup.
110 //===----------------------------------------------------------------------===//
111 
115  // Prefer diagnostics that come from ConditionBRVisitor over
116  // those that came from TrackConstraintBRVisitor,
117  // unless the one from ConditionBRVisitor is
118  // its generic fallback diagnostic.
119  const void *tagPreferred = ConditionBRVisitor::getTag();
120  const void *tagLesser = TrackConstraintBRVisitor::getTag();
121 
122  if (X->getLocation() != Y->getLocation())
123  return nullptr;
124 
125  if (X->getTag() == tagPreferred && Y->getTag() == tagLesser)
126  return ConditionBRVisitor::isPieceMessageGeneric(X) ? Y : X;
127 
128  if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)
129  return ConditionBRVisitor::isPieceMessageGeneric(Y) ? X : Y;
130 
131  return nullptr;
132 }
133 
134 /// An optimization pass over PathPieces that removes redundant diagnostics
135 /// generated by both ConditionBRVisitor and TrackConstraintBRVisitor. Both
136 /// BugReporterVisitors use different methods to generate diagnostics, with
137 /// one capable of emitting diagnostics in some cases but not in others. This
138 /// can lead to redundant diagnostic pieces at the same point in a path.
139 static void removeRedundantMsgs(PathPieces &path) {
140  unsigned N = path.size();
141  if (N < 2)
142  return;
143  // NOTE: this loop intentionally is not using an iterator. Instead, we
144  // are streaming the path and modifying it in place. This is done by
145  // grabbing the front, processing it, and if we decide to keep it append
146  // it to the end of the path. The entire path is processed in this way.
147  for (unsigned i = 0; i < N; ++i) {
148  auto piece = std::move(path.front());
149  path.pop_front();
150 
151  switch (piece->getKind()) {
153  removeRedundantMsgs(cast<PathDiagnosticCallPiece>(*piece).path);
154  break;
156  removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(*piece).subPieces);
157  break;
159  break;
161  if (i == N-1)
162  break;
163 
164  if (auto *nextEvent =
165  dyn_cast<PathDiagnosticEventPiece>(path.front().get())) {
166  auto *event = cast<PathDiagnosticEventPiece>(piece.get());
167  // Check to see if we should keep one of the two pieces. If we
168  // come up with a preference, record which piece to keep, and consume
169  // another piece from the path.
170  if (auto *pieceToKeep =
171  eventsDescribeSameCondition(event, nextEvent)) {
172  piece = std::move(pieceToKeep == event ? piece : path.front());
173  path.pop_front();
174  ++i;
175  }
176  }
177  break;
178  }
180  break;
181  }
182  path.push_back(std::move(piece));
183  }
184 }
185 
186 /// A map from PathDiagnosticPiece to the LocationContext of the inlined
187 /// function call it represents.
188 using LocationContextMap =
189  llvm::DenseMap<const PathPieces *, const LocationContext *>;
190 
191 /// Recursively scan through a path and prune out calls and macros pieces
192 /// that aren't needed. Return true if afterwards the path contains
193 /// "interesting stuff" which means it shouldn't be pruned from the parent path.
194 static bool removeUnneededCalls(PathPieces &pieces, BugReport *R,
195  LocationContextMap &LCM,
196  bool IsInteresting = false) {
197  bool containsSomethingInteresting = IsInteresting;
198  const unsigned N = pieces.size();
199 
200  for (unsigned i = 0 ; i < N ; ++i) {
201  // Remove the front piece from the path. If it is still something we
202  // want to keep once we are done, we will push it back on the end.
203  auto piece = std::move(pieces.front());
204  pieces.pop_front();
205 
206  switch (piece->getKind()) {
208  auto &call = cast<PathDiagnosticCallPiece>(*piece);
209  // Check if the location context is interesting.
210  assert(LCM.count(&call.path));
211  if (!removeUnneededCalls(call.path, R, LCM,
212  R->isInteresting(LCM[&call.path])))
213  continue;
214 
215  containsSomethingInteresting = true;
216  break;
217  }
219  auto &macro = cast<PathDiagnosticMacroPiece>(*piece);
220  if (!removeUnneededCalls(macro.subPieces, R, LCM, IsInteresting))
221  continue;
222  containsSomethingInteresting = true;
223  break;
224  }
226  auto &event = cast<PathDiagnosticEventPiece>(*piece);
227 
228  // We never throw away an event, but we do throw it away wholesale
229  // as part of a path if we throw the entire path away.
230  containsSomethingInteresting |= !event.isPrunable();
231  break;
232  }
234  break;
235 
237  break;
238  }
239 
240  pieces.push_back(std::move(piece));
241  }
242 
243  return containsSomethingInteresting;
244 }
245 
246 /// Returns true if the given decl has been implicitly given a body, either by
247 /// the analyzer or by the compiler proper.
248 static bool hasImplicitBody(const Decl *D) {
249  assert(D);
250  return D->isImplicit() || !D->hasBody();
251 }
252 
253 /// Recursively scan through a path and make sure that all call pieces have
254 /// valid locations.
255 static void
257  PathDiagnosticLocation *LastCallLocation = nullptr) {
258  for (const auto &I : Pieces) {
259  auto *Call = dyn_cast<PathDiagnosticCallPiece>(I.get());
260 
261  if (!Call)
262  continue;
263 
264  if (LastCallLocation) {
265  bool CallerIsImplicit = hasImplicitBody(Call->getCaller());
266  if (CallerIsImplicit || !Call->callEnter.asLocation().isValid())
267  Call->callEnter = *LastCallLocation;
268  if (CallerIsImplicit || !Call->callReturn.asLocation().isValid())
269  Call->callReturn = *LastCallLocation;
270  }
271 
272  // Recursively clean out the subclass. Keep this call around if
273  // it contains any informative diagnostics.
274  PathDiagnosticLocation *ThisCallLocation;
275  if (Call->callEnterWithin.asLocation().isValid() &&
276  !hasImplicitBody(Call->getCallee()))
277  ThisCallLocation = &Call->callEnterWithin;
278  else
279  ThisCallLocation = &Call->callEnter;
280 
281  assert(ThisCallLocation && "Outermost call has an invalid location");
282  adjustCallLocations(Call->path, ThisCallLocation);
283  }
284 }
285 
286 /// Remove edges in and out of C++ default initializer expressions. These are
287 /// for fields that have in-class initializers, as opposed to being initialized
288 /// explicitly in a constructor or braced list.
290  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
291  if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
293 
294  if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))
295  removeEdgesToDefaultInitializers(M->subPieces);
296 
297  if (auto *CF = dyn_cast<PathDiagnosticControlFlowPiece>(I->get())) {
298  const Stmt *Start = CF->getStartLocation().asStmt();
299  const Stmt *End = CF->getEndLocation().asStmt();
300  if (Start && isa<CXXDefaultInitExpr>(Start)) {
301  I = Pieces.erase(I);
302  continue;
303  } else if (End && isa<CXXDefaultInitExpr>(End)) {
304  PathPieces::iterator Next = std::next(I);
305  if (Next != E) {
306  if (auto *NextCF =
307  dyn_cast<PathDiagnosticControlFlowPiece>(Next->get())) {
308  NextCF->setStartLocation(CF->getStartLocation());
309  }
310  }
311  I = Pieces.erase(I);
312  continue;
313  }
314  }
315 
316  I++;
317  }
318 }
319 
320 /// Remove all pieces with invalid locations as these cannot be serialized.
321 /// We might have pieces with invalid locations as a result of inlining Body
322 /// Farm generated functions.
324  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E;) {
325  if (auto *C = dyn_cast<PathDiagnosticCallPiece>(I->get()))
327 
328  if (auto *M = dyn_cast<PathDiagnosticMacroPiece>(I->get()))
329  removePiecesWithInvalidLocations(M->subPieces);
330 
331  if (!(*I)->getLocation().isValid() ||
332  !(*I)->getLocation().asLocation().isValid()) {
333  I = Pieces.erase(I);
334  continue;
335  }
336  I++;
337  }
338 }
339 
340 //===----------------------------------------------------------------------===//
341 // PathDiagnosticBuilder and its associated routines and helper objects.
342 //===----------------------------------------------------------------------===//
343 
344 namespace {
345 
346 class PathDiagnosticBuilder : public BugReporterContext {
347  BugReport *R;
349 
350 public:
351  const LocationContext *LC;
352 
353  PathDiagnosticBuilder(GRBugReporter &br,
354  BugReport *r, InterExplodedGraphMap &Backmap,
356  : BugReporterContext(br, Backmap), R(r), PDC(pdc),
357  LC(r->getErrorNode()->getLocationContext()) {}
358 
359  PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
360 
361  PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
362  const ExplodedNode *N);
363 
364  BugReport *getBugReport() { return R; }
365 
366  Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
367 
368  ParentMap& getParentMap() { return LC->getParentMap(); }
369 
370  const Stmt *getParent(const Stmt *S) {
371  return getParentMap().getParent(S);
372  }
373 
375 
376  PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
378  }
379 
380  bool supportsLogicalOpControlFlow() const {
381  return PDC ? PDC->supportsLogicalOpControlFlow() : true;
382  }
383 };
384 
385 } // namespace
386 
388 PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
389  if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N))
390  return PathDiagnosticLocation(S, getSourceManager(), LC);
391 
393  getSourceManager());
394 }
395 
397 PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
398  const ExplodedNode *N) {
399  // Slow, but probably doesn't matter.
400  if (os.str().empty())
401  os << ' ';
402 
403  const PathDiagnosticLocation &Loc = ExecutionContinues(N);
404 
405  if (Loc.asStmt())
406  os << "Execution continues on line "
408  << '.';
409  else {
410  os << "Execution jumps to the end of the ";
411  const Decl *D = N->getLocationContext()->getDecl();
412  if (isa<ObjCMethodDecl>(D))
413  os << "method";
414  else if (isa<FunctionDecl>(D))
415  os << "function";
416  else {
417  assert(isa<BlockDecl>(D));
418  os << "anonymous block";
419  }
420  os << '.';
421  }
422 
423  return Loc;
424 }
425 
426 static const Stmt *getEnclosingParent(const Stmt *S, const ParentMap &PM) {
427  if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
428  return PM.getParentIgnoreParens(S);
429 
430  const Stmt *Parent = PM.getParentIgnoreParens(S);
431  if (!Parent)
432  return nullptr;
433 
434  switch (Parent->getStmtClass()) {
435  case Stmt::ForStmtClass:
436  case Stmt::DoStmtClass:
437  case Stmt::WhileStmtClass:
438  case Stmt::ObjCForCollectionStmtClass:
439  case Stmt::CXXForRangeStmtClass:
440  return Parent;
441  default:
442  break;
443  }
444 
445  return nullptr;
446 }
447 
450  const LocationContext *LC, bool allowNestedContexts) {
451  if (!S)
452  return {};
453 
454  while (const Stmt *Parent = getEnclosingParent(S, P)) {
455  switch (Parent->getStmtClass()) {
456  case Stmt::BinaryOperatorClass: {
457  const auto *B = cast<BinaryOperator>(Parent);
458  if (B->isLogicalOp())
459  return PathDiagnosticLocation(allowNestedContexts ? B : S, SMgr, LC);
460  break;
461  }
462  case Stmt::CompoundStmtClass:
463  case Stmt::StmtExprClass:
464  return PathDiagnosticLocation(S, SMgr, LC);
465  case Stmt::ChooseExprClass:
466  // Similar to '?' if we are referring to condition, just have the edge
467  // point to the entire choose expression.
468  if (allowNestedContexts || cast<ChooseExpr>(Parent)->getCond() == S)
469  return PathDiagnosticLocation(Parent, SMgr, LC);
470  else
471  return PathDiagnosticLocation(S, SMgr, LC);
472  case Stmt::BinaryConditionalOperatorClass:
473  case Stmt::ConditionalOperatorClass:
474  // For '?', if we are referring to condition, just have the edge point
475  // to the entire '?' expression.
476  if (allowNestedContexts ||
477  cast<AbstractConditionalOperator>(Parent)->getCond() == S)
478  return PathDiagnosticLocation(Parent, SMgr, LC);
479  else
480  return PathDiagnosticLocation(S, SMgr, LC);
481  case Stmt::CXXForRangeStmtClass:
482  if (cast<CXXForRangeStmt>(Parent)->getBody() == S)
483  return PathDiagnosticLocation(S, SMgr, LC);
484  break;
485  case Stmt::DoStmtClass:
486  return PathDiagnosticLocation(S, SMgr, LC);
487  case Stmt::ForStmtClass:
488  if (cast<ForStmt>(Parent)->getBody() == S)
489  return PathDiagnosticLocation(S, SMgr, LC);
490  break;
491  case Stmt::IfStmtClass:
492  if (cast<IfStmt>(Parent)->getCond() != S)
493  return PathDiagnosticLocation(S, SMgr, LC);
494  break;
495  case Stmt::ObjCForCollectionStmtClass:
496  if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
497  return PathDiagnosticLocation(S, SMgr, LC);
498  break;
499  case Stmt::WhileStmtClass:
500  if (cast<WhileStmt>(Parent)->getCond() != S)
501  return PathDiagnosticLocation(S, SMgr, LC);
502  break;
503  default:
504  break;
505  }
506 
507  S = Parent;
508  }
509 
510  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
511 
512  return PathDiagnosticLocation(S, SMgr, LC);
513 }
514 
517  assert(S && "Null Stmt passed to getEnclosingStmtLocation");
518  return ::getEnclosingStmtLocation(S, getSourceManager(), getParentMap(), LC,
519  /*allowNestedContexts=*/false);
520 }
521 
522 //===----------------------------------------------------------------------===//
523 // "Minimal" path diagnostic generation algorithm.
524 //===----------------------------------------------------------------------===//
525 using StackDiagPair =
526  std::pair<PathDiagnosticCallPiece *, const ExplodedNode *>;
528 
530  StackDiagVector &CallStack) {
531  // If the piece contains a special message, add it to all the call
532  // pieces on the active stack.
533  if (auto *ep = dyn_cast<PathDiagnosticEventPiece>(&P)) {
534  if (ep->hasCallStackHint())
535  for (const auto &I : CallStack) {
536  PathDiagnosticCallPiece *CP = I.first;
537  const ExplodedNode *N = I.second;
538  std::string stackMsg = ep->getCallStackMessage(N);
539 
540  // The last message on the path to final bug is the most important
541  // one. Since we traverse the path backwards, do not add the message
542  // if one has been previously added.
543  if (!CP->hasCallStackMessage())
544  CP->setCallStackMessage(stackMsg);
545  }
546  }
547 }
548 
549 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
550 
551 
552 std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForSwitchOP(
553  const ExplodedNode *N,
554  const CFGBlock *Dst,
555  const SourceManager &SM,
556  const LocationContext *LC,
557  PathDiagnosticBuilder &PDB,
559  ) {
560  // Figure out what case arm we took.
561  std::string sbuf;
562  llvm::raw_string_ostream os(sbuf);
564 
565  if (const Stmt *S = Dst->getLabel()) {
566  End = PathDiagnosticLocation(S, SM, LC);
567 
568  switch (S->getStmtClass()) {
569  default:
570  os << "No cases match in the switch statement. "
571  "Control jumps to line "
573  break;
574  case Stmt::DefaultStmtClass:
575  os << "Control jumps to the 'default' case at line "
577  break;
578 
579  case Stmt::CaseStmtClass: {
580  os << "Control jumps to 'case ";
581  const auto *Case = cast<CaseStmt>(S);
582  const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
583 
584  // Determine if it is an enum.
585  bool GetRawInt = true;
586 
587  if (const auto *DR = dyn_cast<DeclRefExpr>(LHS)) {
588  // FIXME: Maybe this should be an assertion. Are there cases
589  // were it is not an EnumConstantDecl?
590  const auto *D = dyn_cast<EnumConstantDecl>(DR->getDecl());
591 
592  if (D) {
593  GetRawInt = false;
594  os << *D;
595  }
596  }
597 
598  if (GetRawInt)
599  os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
600 
601  os << ":' at line " << End.asLocation().getExpansionLineNumber();
602  break;
603  }
604  }
605  } else {
606  os << "'Default' branch taken. ";
607  End = PDB.ExecutionContinues(os, N);
608  }
609  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
610  os.str());
611 }
612 
613 
614 std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForGotoOP(
615  const Stmt *S,
616  PathDiagnosticBuilder &PDB,
617  PathDiagnosticLocation &Start) {
618  std::string sbuf;
619  llvm::raw_string_ostream os(sbuf);
620  const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
621  os << "Control jumps to line " << End.asLocation().getExpansionLineNumber();
622  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str());
623 
624 }
625 
626 std::shared_ptr<PathDiagnosticControlFlowPiece> generateDiagForBinaryOP(
627  const ExplodedNode *N,
628  const Stmt *T,
629  const CFGBlock *Src,
630  const CFGBlock *Dst,
631  const SourceManager &SM,
632  PathDiagnosticBuilder &PDB,
633  const LocationContext *LC) {
634  const auto *B = cast<BinaryOperator>(T);
635  std::string sbuf;
636  llvm::raw_string_ostream os(sbuf);
637  os << "Left side of '";
639 
640  if (B->getOpcode() == BO_LAnd) {
641  os << "&&"
642  << "' is ";
643 
644  if (*(Src->succ_begin() + 1) == Dst) {
645  os << "false";
646  End = PathDiagnosticLocation(B->getLHS(), SM, LC);
647  Start =
649  } else {
650  os << "true";
651  Start = PathDiagnosticLocation(B->getLHS(), SM, LC);
652  End = PDB.ExecutionContinues(N);
653  }
654  } else {
655  assert(B->getOpcode() == BO_LOr);
656  os << "||"
657  << "' is ";
658 
659  if (*(Src->succ_begin() + 1) == Dst) {
660  os << "false";
661  Start = PathDiagnosticLocation(B->getLHS(), SM, LC);
662  End = PDB.ExecutionContinues(N);
663  } else {
664  os << "true";
665  End = PathDiagnosticLocation(B->getLHS(), SM, LC);
666  Start =
668  }
669  }
670  return std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
671  os.str());
672 }
673 
675  const SourceManager &SM,
676  PathDiagnosticBuilder &PDB,
677  PathDiagnostic &PD) {
678  const LocationContext *LC = N->getLocationContext();
679  const CFGBlock *Src = BE.getSrc();
680  const CFGBlock *Dst = BE.getDst();
681  const Stmt *T = Src->getTerminator();
682  if (!T)
683  return;
684 
685  auto Start = PathDiagnosticLocation::createBegin(T, SM, LC);
686  switch (T->getStmtClass()) {
687  default:
688  break;
689 
690  case Stmt::GotoStmtClass:
691  case Stmt::IndirectGotoStmtClass: {
692  if (const Stmt *S = PathDiagnosticLocation::getNextStmt(N))
693  PD.getActivePath().push_front(generateDiagForGotoOP(S, PDB, Start));
694  break;
695  }
696 
697  case Stmt::SwitchStmtClass: {
698  PD.getActivePath().push_front(
699  generateDiagForSwitchOP(N, Dst, SM, LC, PDB, Start));
700  break;
701  }
702 
703  case Stmt::BreakStmtClass:
704  case Stmt::ContinueStmtClass: {
705  std::string sbuf;
706  llvm::raw_string_ostream os(sbuf);
707  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
708  PD.getActivePath().push_front(
709  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
710  break;
711  }
712 
713  // Determine control-flow for ternary '?'.
714  case Stmt::BinaryConditionalOperatorClass:
715  case Stmt::ConditionalOperatorClass: {
716  std::string sbuf;
717  llvm::raw_string_ostream os(sbuf);
718  os << "'?' condition is ";
719 
720  if (*(Src->succ_begin() + 1) == Dst)
721  os << "false";
722  else
723  os << "true";
724 
725  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
726 
727  if (const Stmt *S = End.asStmt())
728  End = PDB.getEnclosingStmtLocation(S);
729 
730  PD.getActivePath().push_front(
731  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End, os.str()));
732  break;
733  }
734 
735  // Determine control-flow for short-circuited '&&' and '||'.
736  case Stmt::BinaryOperatorClass: {
737  if (!PDB.supportsLogicalOpControlFlow())
738  break;
739 
740  std::shared_ptr<PathDiagnosticControlFlowPiece> Diag =
741  generateDiagForBinaryOP(N, T, Src, Dst, SM, PDB, LC);
742  PD.getActivePath().push_front(Diag);
743  break;
744  }
745 
746  case Stmt::DoStmtClass:
747  if (*(Src->succ_begin()) == Dst) {
748  std::string sbuf;
749  llvm::raw_string_ostream os(sbuf);
750 
751  os << "Loop condition is true. ";
752  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
753 
754  if (const Stmt *S = End.asStmt())
755  End = PDB.getEnclosingStmtLocation(S);
756 
757  PD.getActivePath().push_front(
758  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
759  os.str()));
760  } else {
761  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
762 
763  if (const Stmt *S = End.asStmt())
764  End = PDB.getEnclosingStmtLocation(S);
765 
766  PD.getActivePath().push_front(
767  std::make_shared<PathDiagnosticControlFlowPiece>(
768  Start, End, "Loop condition is false. Exiting loop"));
769  }
770  break;
771 
772  case Stmt::WhileStmtClass:
773  case Stmt::ForStmtClass:
774  if (*(Src->succ_begin() + 1) == Dst) {
775  std::string sbuf;
776  llvm::raw_string_ostream os(sbuf);
777 
778  os << "Loop condition is false. ";
779  PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
780  if (const Stmt *S = End.asStmt())
781  End = PDB.getEnclosingStmtLocation(S);
782 
783  PD.getActivePath().push_front(
784  std::make_shared<PathDiagnosticControlFlowPiece>(Start, End,
785  os.str()));
786  } else {
787  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
788  if (const Stmt *S = End.asStmt())
789  End = PDB.getEnclosingStmtLocation(S);
790 
791  PD.getActivePath().push_front(
792  std::make_shared<PathDiagnosticControlFlowPiece>(
793  Start, End, "Loop condition is true. Entering loop body"));
794  }
795 
796  break;
797 
798  case Stmt::IfStmtClass: {
799  PathDiagnosticLocation End = PDB.ExecutionContinues(N);
800 
801  if (const Stmt *S = End.asStmt())
802  End = PDB.getEnclosingStmtLocation(S);
803 
804  if (*(Src->succ_begin() + 1) == Dst)
805  PD.getActivePath().push_front(
806  std::make_shared<PathDiagnosticControlFlowPiece>(
807  Start, End, "Taking false branch"));
808  else
809  PD.getActivePath().push_front(
810  std::make_shared<PathDiagnosticControlFlowPiece>(
811  Start, End, "Taking true branch"));
812 
813  break;
814  }
815  }
816 }
817 
818 // Cone-of-influence: support the reverse propagation of "interesting" symbols
819 // and values by tracing interesting calculations backwards through evaluated
820 // expressions along a path. This is probably overly complicated, but the idea
821 // is that if an expression computed an "interesting" value, the child
822 // expressions are are also likely to be "interesting" as well (which then
823 // propagates to the values they in turn compute). This reverse propagation
824 // is needed to track interesting correlations across function call boundaries,
825 // where formal arguments bind to actual arguments, etc. This is also needed
826 // because the constraint solver sometimes simplifies certain symbolic values
827 // into constants when appropriate, and this complicates reasoning about
828 // interesting values.
830 
832  InterestingExprs &IE,
833  const ProgramState *State,
834  const Expr *Ex,
835  const LocationContext *LCtx) {
836  SVal V = State->getSVal(Ex, LCtx);
837  if (!(R.isInteresting(V) || IE.count(Ex)))
838  return;
839 
840  switch (Ex->getStmtClass()) {
841  default:
842  if (!isa<CastExpr>(Ex))
843  break;
844  // Fall through.
845  case Stmt::BinaryOperatorClass:
846  case Stmt::UnaryOperatorClass: {
847  for (const Stmt *SubStmt : Ex->children()) {
848  if (const auto *child = dyn_cast_or_null<Expr>(SubStmt)) {
849  IE.insert(child);
850  SVal ChildV = State->getSVal(child, LCtx);
851  R.markInteresting(ChildV);
852  }
853  }
854  break;
855  }
856  }
857 
858  R.markInteresting(V);
859 }
860 
862  InterestingExprs &IE,
863  const ProgramState *State,
864  const LocationContext *CalleeCtx,
865  const LocationContext *CallerCtx)
866 {
867  // FIXME: Handle non-CallExpr-based CallEvents.
868  const StackFrameContext *Callee = CalleeCtx->getStackFrame();
869  const Stmt *CallSite = Callee->getCallSite();
870  if (const auto *CE = dyn_cast_or_null<CallExpr>(CallSite)) {
871  if (const auto *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) {
872  FunctionDecl::param_const_iterator PI = FD->param_begin(),
873  PE = FD->param_end();
874  CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
875  for (; AI != AE && PI != PE; ++AI, ++PI) {
876  if (const Expr *ArgE = *AI) {
877  if (const ParmVarDecl *PD = *PI) {
878  Loc LV = State->getLValue(PD, CalleeCtx);
879  if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV)))
880  IE.insert(ArgE);
881  }
882  }
883  }
884  }
885  }
886 }
887 
888 //===----------------------------------------------------------------------===//
889 // Functions for determining if a loop was executed 0 times.
890 //===----------------------------------------------------------------------===//
891 
892 static bool isLoop(const Stmt *Term) {
893  switch (Term->getStmtClass()) {
894  case Stmt::ForStmtClass:
895  case Stmt::WhileStmtClass:
896  case Stmt::ObjCForCollectionStmtClass:
897  case Stmt::CXXForRangeStmtClass:
898  return true;
899  default:
900  // Note that we intentionally do not include do..while here.
901  return false;
902  }
903 }
904 
905 static bool isJumpToFalseBranch(const BlockEdge *BE) {
906  const CFGBlock *Src = BE->getSrc();
907  assert(Src->succ_size() == 2);
908  return (*(Src->succ_begin()+1) == BE->getDst());
909 }
910 
911 static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
912  while (SubS) {
913  if (SubS == S)
914  return true;
915  SubS = PM.getParent(SubS);
916  }
917  return false;
918 }
919 
920 static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term,
921  const ExplodedNode *N) {
922  while (N) {
924  if (SP) {
925  const Stmt *S = SP->getStmt();
926  if (!isContainedByStmt(PM, Term, S))
927  return S;
928  }
929  N = N->getFirstPred();
930  }
931  return nullptr;
932 }
933 
934 static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) {
935  const Stmt *LoopBody = nullptr;
936  switch (Term->getStmtClass()) {
937  case Stmt::CXXForRangeStmtClass: {
938  const auto *FR = cast<CXXForRangeStmt>(Term);
939  if (isContainedByStmt(PM, FR->getInc(), S))
940  return true;
941  if (isContainedByStmt(PM, FR->getLoopVarStmt(), S))
942  return true;
943  LoopBody = FR->getBody();
944  break;
945  }
946  case Stmt::ForStmtClass: {
947  const auto *FS = cast<ForStmt>(Term);
948  if (isContainedByStmt(PM, FS->getInc(), S))
949  return true;
950  LoopBody = FS->getBody();
951  break;
952  }
953  case Stmt::ObjCForCollectionStmtClass: {
954  const auto *FC = cast<ObjCForCollectionStmt>(Term);
955  LoopBody = FC->getBody();
956  break;
957  }
958  case Stmt::WhileStmtClass:
959  LoopBody = cast<WhileStmt>(Term)->getBody();
960  break;
961  default:
962  return false;
963  }
964  return isContainedByStmt(PM, LoopBody, S);
965 }
966 
967 /// Adds a sanitized control-flow diagnostic edge to a path.
968 static void addEdgeToPath(PathPieces &path,
969  PathDiagnosticLocation &PrevLoc,
970  PathDiagnosticLocation NewLoc,
971  const LocationContext *LC) {
972  if (!NewLoc.isValid())
973  return;
974 
975  SourceLocation NewLocL = NewLoc.asLocation();
976  if (NewLocL.isInvalid())
977  return;
978 
979  if (!PrevLoc.isValid() || !PrevLoc.asLocation().isValid()) {
980  PrevLoc = NewLoc;
981  return;
982  }
983 
984  // Ignore self-edges, which occur when there are multiple nodes at the same
985  // statement.
986  if (NewLoc.asStmt() && NewLoc.asStmt() == PrevLoc.asStmt())
987  return;
988 
989  path.push_front(
990  std::make_shared<PathDiagnosticControlFlowPiece>(NewLoc, PrevLoc));
991  PrevLoc = NewLoc;
992 }
993 
994 /// A customized wrapper for CFGBlock::getTerminatorCondition()
995 /// which returns the element for ObjCForCollectionStmts.
996 static const Stmt *getTerminatorCondition(const CFGBlock *B) {
997  const Stmt *S = B->getTerminatorCondition();
998  if (const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(S))
999  return FS->getElement();
1000  return S;
1001 }
1002 
1003 static const char StrEnteringLoop[] = "Entering loop body";
1004 static const char StrLoopBodyZero[] = "Loop body executed 0 times";
1005 static const char StrLoopRangeEmpty[] =
1006  "Loop body skipped when range is empty";
1007 static const char StrLoopCollectionEmpty[] =
1008  "Loop body skipped when collection is empty";
1009 
1010 static std::unique_ptr<FilesToLineNumsMap>
1012 
1013 /// Generate diagnostics for the node \p N,
1014 /// and write it into \p PD.
1015 /// \p AddPathEdges Whether diagnostic consumer can generate path arrows
1016 /// showing both row and column.
1018  PathDiagnostic &PD,
1019  PathDiagnosticLocation &PrevLoc,
1020  PathDiagnosticBuilder &PDB,
1021  LocationContextMap &LCM,
1022  StackDiagVector &CallStack,
1023  InterestingExprs &IE,
1024  bool AddPathEdges) {
1025  ProgramPoint P = N->getLocation();
1026  const SourceManager& SM = PDB.getSourceManager();
1027 
1028  // Have we encountered an entrance to a call? It may be
1029  // the case that we have not encountered a matching
1030  // call exit before this point. This means that the path
1031  // terminated within the call itself.
1032  if (auto CE = P.getAs<CallEnter>()) {
1033 
1034  if (AddPathEdges) {
1035  // Add an edge to the start of the function.
1036  const StackFrameContext *CalleeLC = CE->getCalleeContext();
1037  const Decl *D = CalleeLC->getDecl();
1038  // Add the edge only when the callee has body. We jump to the beginning
1039  // of the *declaration*, however we expect it to be followed by the
1040  // body. This isn't the case for autosynthesized property accessors in
1041  // Objective-C. No need for a similar extra check for CallExit points
1042  // because the exit edge comes from a statement (i.e. return),
1043  // not from declaration.
1044  if (D->hasBody())
1045  addEdgeToPath(PD.getActivePath(), PrevLoc,
1046  PathDiagnosticLocation::createBegin(D, SM), CalleeLC);
1047  }
1048 
1049  // Did we visit an entire call?
1050  bool VisitedEntireCall = PD.isWithinCall();
1051  PD.popActivePath();
1052 
1054  if (VisitedEntireCall) {
1055  C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front().get());
1056  } else {
1057  const Decl *Caller = CE->getLocationContext()->getDecl();
1059 
1060  if (AddPathEdges) {
1061  // Since we just transferred the path over to the call piece,
1062  // reset the mapping from active to location context.
1063  assert(PD.getActivePath().size() == 1 &&
1064  PD.getActivePath().front().get() == C);
1065  LCM[&PD.getActivePath()] = nullptr;
1066  }
1067 
1068  // Record the location context mapping for the path within
1069  // the call.
1070  assert(LCM[&C->path] == nullptr ||
1071  LCM[&C->path] == CE->getCalleeContext());
1072  LCM[&C->path] = CE->getCalleeContext();
1073 
1074  // If this is the first item in the active path, record
1075  // the new mapping from active path to location context.
1076  const LocationContext *&NewLC = LCM[&PD.getActivePath()];
1077  if (!NewLC)
1078  NewLC = N->getLocationContext();
1079 
1080  PDB.LC = NewLC;
1081  }
1082  C->setCallee(*CE, SM);
1083 
1084  // Update the previous location in the active path.
1085  PrevLoc = C->getLocation();
1086 
1087  if (!CallStack.empty()) {
1088  assert(CallStack.back().first == C);
1089  CallStack.pop_back();
1090  }
1091  return;
1092  }
1093 
1094 
1095  if (AddPathEdges) {
1096  // Query the location context here and the previous location
1097  // as processing CallEnter may change the active path.
1098  PDB.LC = N->getLocationContext();
1099 
1100  // Record the mapping from the active path to the location
1101  // context.
1102  assert(!LCM[&PD.getActivePath()] || LCM[&PD.getActivePath()] == PDB.LC);
1103  LCM[&PD.getActivePath()] = PDB.LC;
1104  }
1105 
1106  // Have we encountered an exit from a function call?
1107  if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1108 
1109  // We are descending into a call (backwards). Construct
1110  // a new call piece to contain the path pieces for that call.
1111  auto C = PathDiagnosticCallPiece::construct(N, *CE, SM);
1112  // Record the mapping from call piece to LocationContext.
1113  LCM[&C->path] = CE->getCalleeContext();
1114 
1115  if (AddPathEdges) {
1116  const Stmt *S = CE->getCalleeContext()->getCallSite();
1117  // Propagate the interesting symbols accordingly.
1118  if (const auto *Ex = dyn_cast_or_null<Expr>(S)) {
1119  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1120  N->getState().get(), Ex,
1121  N->getLocationContext());
1122  }
1123  // Add the edge to the return site.
1124  addEdgeToPath(PD.getActivePath(), PrevLoc, C->callReturn, PDB.LC);
1125  PrevLoc.invalidate();
1126  }
1127 
1128  auto *P = C.get();
1129  PD.getActivePath().push_front(std::move(C));
1130 
1131  // Make the contents of the call the active path for now.
1132  PD.pushActivePath(&P->path);
1133  CallStack.push_back(StackDiagPair(P, N));
1134  return;
1135  }
1136 
1137  if (auto PS = P.getAs<PostStmt>()) {
1138  if (!AddPathEdges)
1139  return;
1140 
1141  // For expressions, make sure we propagate the
1142  // interesting symbols correctly.
1143  if (const Expr *Ex = PS->getStmtAs<Expr>())
1144  reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1145  N->getState().get(), Ex,
1146  N->getLocationContext());
1147 
1148  // Add an edge. If this is an ObjCForCollectionStmt do
1149  // not add an edge here as it appears in the CFG both
1150  // as a terminator and as a terminator condition.
1151  if (!isa<ObjCForCollectionStmt>(PS->getStmt())) {
1153  PathDiagnosticLocation(PS->getStmt(), SM, PDB.LC);
1154  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1155  }
1156 
1157  } else if (auto BE = P.getAs<BlockEdge>()) {
1158 
1159  if (!AddPathEdges) {
1160  generateMinimalDiagForBlockEdge(N, *BE, SM, PDB, PD);
1161  return;
1162  }
1163 
1164  // Does this represent entering a call? If so, look at propagating
1165  // interesting symbols across call boundaries.
1166  if (const ExplodedNode *NextNode = N->getFirstPred()) {
1167  const LocationContext *CallerCtx = NextNode->getLocationContext();
1168  const LocationContext *CalleeCtx = PDB.LC;
1169  if (CallerCtx != CalleeCtx && AddPathEdges) {
1170  reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1171  N->getState().get(),
1172  CalleeCtx, CallerCtx);
1173  }
1174  }
1175 
1176  // Are we jumping to the head of a loop? Add a special diagnostic.
1177  if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1178  PathDiagnosticLocation L(Loop, SM, PDB.LC);
1179  const Stmt *Body = nullptr;
1180 
1181  if (const auto *FS = dyn_cast<ForStmt>(Loop))
1182  Body = FS->getBody();
1183  else if (const auto *WS = dyn_cast<WhileStmt>(Loop))
1184  Body = WS->getBody();
1185  else if (const auto *OFS = dyn_cast<ObjCForCollectionStmt>(Loop)) {
1186  Body = OFS->getBody();
1187  } else if (const auto *FRS = dyn_cast<CXXForRangeStmt>(Loop)) {
1188  Body = FRS->getBody();
1189  }
1190  // do-while statements are explicitly excluded here
1191 
1192  auto p = std::make_shared<PathDiagnosticEventPiece>(
1193  L, "Looping back to the head "
1194  "of the loop");
1195  p->setPrunable(true);
1196 
1197  addEdgeToPath(PD.getActivePath(), PrevLoc, p->getLocation(), PDB.LC);
1198  PD.getActivePath().push_front(std::move(p));
1199 
1200  if (const auto *CS = dyn_cast_or_null<CompoundStmt>(Body)) {
1201  addEdgeToPath(PD.getActivePath(), PrevLoc,
1203  PDB.LC);
1204  }
1205  }
1206 
1207  const CFGBlock *BSrc = BE->getSrc();
1208  ParentMap &PM = PDB.getParentMap();
1209 
1210  if (const Stmt *Term = BSrc->getTerminator()) {
1211  // Are we jumping past the loop body without ever executing the
1212  // loop (because the condition was false)?
1213  if (isLoop(Term)) {
1214  const Stmt *TermCond = getTerminatorCondition(BSrc);
1215  bool IsInLoopBody =
1216  isInLoopBody(PM, getStmtBeforeCond(PM, TermCond, N), Term);
1217 
1218  const char *str = nullptr;
1219 
1220  if (isJumpToFalseBranch(&*BE)) {
1221  if (!IsInLoopBody) {
1222  if (isa<ObjCForCollectionStmt>(Term)) {
1223  str = StrLoopCollectionEmpty;
1224  } else if (isa<CXXForRangeStmt>(Term)) {
1225  str = StrLoopRangeEmpty;
1226  } else {
1227  str = StrLoopBodyZero;
1228  }
1229  }
1230  } else {
1231  str = StrEnteringLoop;
1232  }
1233 
1234  if (str) {
1235  PathDiagnosticLocation L(TermCond ? TermCond : Term, SM, PDB.LC);
1236  auto PE = std::make_shared<PathDiagnosticEventPiece>(L, str);
1237  PE->setPrunable(true);
1238  addEdgeToPath(PD.getActivePath(), PrevLoc,
1239  PE->getLocation(), PDB.LC);
1240  PD.getActivePath().push_front(std::move(PE));
1241  }
1242  } else if (isa<BreakStmt>(Term) || isa<ContinueStmt>(Term) ||
1243  isa<GotoStmt>(Term)) {
1244  PathDiagnosticLocation L(Term, SM, PDB.LC);
1245  addEdgeToPath(PD.getActivePath(), PrevLoc, L, PDB.LC);
1246  }
1247  }
1248  }
1249 }
1250 
1251 static std::unique_ptr<PathDiagnostic>
1253  BugType &BT = R->getBugType();
1254  return llvm::make_unique<PathDiagnostic>(
1256  R->getBugType().getName(), R->getDescription(),
1257  R->getShortDescription(/*Fallback=*/false), BT.getCategory(),
1259  findExecutedLines(SM, R->getErrorNode()));
1260 }
1261 
1262 static const Stmt *getStmtParent(const Stmt *S, const ParentMap &PM) {
1263  if (!S)
1264  return nullptr;
1265 
1266  while (true) {
1267  S = PM.getParentIgnoreParens(S);
1268 
1269  if (!S)
1270  break;
1271 
1272  if (isa<ExprWithCleanups>(S) ||
1273  isa<CXXBindTemporaryExpr>(S) ||
1274  isa<SubstNonTypeTemplateParmExpr>(S))
1275  continue;
1276 
1277  break;
1278  }
1279 
1280  return S;
1281 }
1282 
1283 static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond) {
1284  switch (S->getStmtClass()) {
1285  case Stmt::BinaryOperatorClass: {
1286  const auto *BO = cast<BinaryOperator>(S);
1287  if (!BO->isLogicalOp())
1288  return false;
1289  return BO->getLHS() == Cond || BO->getRHS() == Cond;
1290  }
1291  case Stmt::IfStmtClass:
1292  return cast<IfStmt>(S)->getCond() == Cond;
1293  case Stmt::ForStmtClass:
1294  return cast<ForStmt>(S)->getCond() == Cond;
1295  case Stmt::WhileStmtClass:
1296  return cast<WhileStmt>(S)->getCond() == Cond;
1297  case Stmt::DoStmtClass:
1298  return cast<DoStmt>(S)->getCond() == Cond;
1299  case Stmt::ChooseExprClass:
1300  return cast<ChooseExpr>(S)->getCond() == Cond;
1301  case Stmt::IndirectGotoStmtClass:
1302  return cast<IndirectGotoStmt>(S)->getTarget() == Cond;
1303  case Stmt::SwitchStmtClass:
1304  return cast<SwitchStmt>(S)->getCond() == Cond;
1305  case Stmt::BinaryConditionalOperatorClass:
1306  return cast<BinaryConditionalOperator>(S)->getCond() == Cond;
1307  case Stmt::ConditionalOperatorClass: {
1308  const auto *CO = cast<ConditionalOperator>(S);
1309  return CO->getCond() == Cond ||
1310  CO->getLHS() == Cond ||
1311  CO->getRHS() == Cond;
1312  }
1313  case Stmt::ObjCForCollectionStmtClass:
1314  return cast<ObjCForCollectionStmt>(S)->getElement() == Cond;
1315  case Stmt::CXXForRangeStmtClass: {
1316  const auto *FRS = cast<CXXForRangeStmt>(S);
1317  return FRS->getCond() == Cond || FRS->getRangeInit() == Cond;
1318  }
1319  default:
1320  return false;
1321  }
1322 }
1323 
1324 static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL) {
1325  if (const auto *FS = dyn_cast<ForStmt>(FL))
1326  return FS->getInc() == S || FS->getInit() == S;
1327  if (const auto *FRS = dyn_cast<CXXForRangeStmt>(FL))
1328  return FRS->getInc() == S || FRS->getRangeStmt() == S ||
1329  FRS->getLoopVarStmt() || FRS->getRangeInit() == S;
1330  return false;
1331 }
1332 
1334 
1335 /// Adds synthetic edges from top-level statements to their subexpressions.
1336 ///
1337 /// This avoids a "swoosh" effect, where an edge from a top-level statement A
1338 /// points to a sub-expression B.1 that's not at the start of B. In these cases,
1339 /// we'd like to see an edge from A to B, then another one from B to B.1.
1340 static void addContextEdges(PathPieces &pieces, SourceManager &SM,
1341  const ParentMap &PM, const LocationContext *LCtx) {
1342  PathPieces::iterator Prev = pieces.end();
1343  for (PathPieces::iterator I = pieces.begin(), E = Prev; I != E;
1344  Prev = I, ++I) {
1345  auto *Piece = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1346 
1347  if (!Piece)
1348  continue;
1349 
1350  PathDiagnosticLocation SrcLoc = Piece->getStartLocation();
1352 
1353  PathDiagnosticLocation NextSrcContext = SrcLoc;
1354  const Stmt *InnerStmt = nullptr;
1355  while (NextSrcContext.isValid() && NextSrcContext.asStmt() != InnerStmt) {
1356  SrcContexts.push_back(NextSrcContext);
1357  InnerStmt = NextSrcContext.asStmt();
1358  NextSrcContext = getEnclosingStmtLocation(InnerStmt, SM, PM, LCtx,
1359  /*allowNested=*/true);
1360  }
1361 
1362  // Repeatedly split the edge as necessary.
1363  // This is important for nested logical expressions (||, &&, ?:) where we
1364  // want to show all the levels of context.
1365  while (true) {
1366  const Stmt *Dst = Piece->getEndLocation().getStmtOrNull();
1367 
1368  // We are looking at an edge. Is the destination within a larger
1369  // expression?
1370  PathDiagnosticLocation DstContext =
1371  getEnclosingStmtLocation(Dst, SM, PM, LCtx, /*allowNested=*/true);
1372  if (!DstContext.isValid() || DstContext.asStmt() == Dst)
1373  break;
1374 
1375  // If the source is in the same context, we're already good.
1376  if (std::find(SrcContexts.begin(), SrcContexts.end(), DstContext) !=
1377  SrcContexts.end())
1378  break;
1379 
1380  // Update the subexpression node to point to the context edge.
1381  Piece->setStartLocation(DstContext);
1382 
1383  // Try to extend the previous edge if it's at the same level as the source
1384  // context.
1385  if (Prev != E) {
1386  auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get());
1387 
1388  if (PrevPiece) {
1389  if (const Stmt *PrevSrc =
1390  PrevPiece->getStartLocation().getStmtOrNull()) {
1391  const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);
1392  if (PrevSrcParent ==
1393  getStmtParent(DstContext.getStmtOrNull(), PM)) {
1394  PrevPiece->setEndLocation(DstContext);
1395  break;
1396  }
1397  }
1398  }
1399  }
1400 
1401  // Otherwise, split the current edge into a context edge and a
1402  // subexpression edge. Note that the context statement may itself have
1403  // context.
1404  auto P =
1405  std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext);
1406  Piece = P.get();
1407  I = pieces.insert(I, std::move(P));
1408  }
1409  }
1410 }
1411 
1412 /// Move edges from a branch condition to a branch target
1413 /// when the condition is simple.
1414 ///
1415 /// This restructures some of the work of addContextEdges. That function
1416 /// creates edges this may destroy, but they work together to create a more
1417 /// aesthetically set of edges around branches. After the call to
1418 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from
1419 /// the branch to the branch condition, and (3) an edge from the branch
1420 /// condition to the branch target. We keep (1), but may wish to remove (2)
1421 /// and move the source of (3) to the branch if the branch condition is simple.
1422 static void simplifySimpleBranches(PathPieces &pieces) {
1423  for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {
1424  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1425 
1426  if (!PieceI)
1427  continue;
1428 
1429  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1430  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1431 
1432  if (!s1Start || !s1End)
1433  continue;
1434 
1435  PathPieces::iterator NextI = I; ++NextI;
1436  if (NextI == E)
1437  break;
1438 
1439  PathDiagnosticControlFlowPiece *PieceNextI = nullptr;
1440 
1441  while (true) {
1442  if (NextI == E)
1443  break;
1444 
1445  const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1446  if (EV) {
1447  StringRef S = EV->getString();
1448  if (S == StrEnteringLoop || S == StrLoopBodyZero ||
1450  ++NextI;
1451  continue;
1452  }
1453  break;
1454  }
1455 
1456  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1457  break;
1458  }
1459 
1460  if (!PieceNextI)
1461  continue;
1462 
1463  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1464  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1465 
1466  if (!s2Start || !s2End || s1End != s2Start)
1467  continue;
1468 
1469  // We only perform this transformation for specific branch kinds.
1470  // We don't want to do this for do..while, for example.
1471  if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) ||
1472  isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) ||
1473  isa<CXXForRangeStmt>(s1Start)))
1474  continue;
1475 
1476  // Is s1End the branch condition?
1477  if (!isConditionForTerminator(s1Start, s1End))
1478  continue;
1479 
1480  // Perform the hoisting by eliminating (2) and changing the start
1481  // location of (3).
1482  PieceNextI->setStartLocation(PieceI->getStartLocation());
1483  I = pieces.erase(I);
1484  }
1485 }
1486 
1487 /// Returns the number of bytes in the given (character-based) SourceRange.
1488 ///
1489 /// If the locations in the range are not on the same line, returns None.
1490 ///
1491 /// Note that this does not do a precise user-visible character or column count.
1493  SourceRange Range) {
1494  SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),
1495  SM.getExpansionRange(Range.getEnd()).getEnd());
1496 
1497  FileID FID = SM.getFileID(ExpansionRange.getBegin());
1498  if (FID != SM.getFileID(ExpansionRange.getEnd()))
1499  return None;
1500 
1501  bool Invalid;
1502  const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid);
1503  if (Invalid)
1504  return None;
1505 
1506  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
1507  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
1508  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
1509 
1510  // We're searching the raw bytes of the buffer here, which might include
1511  // escaped newlines and such. That's okay; we're trying to decide whether the
1512  // SourceRange is covering a large or small amount of space in the user's
1513  // editor.
1514  if (Snippet.find_first_of("\r\n") != StringRef::npos)
1515  return None;
1516 
1517  // This isn't Unicode-aware, but it doesn't need to be.
1518  return Snippet.size();
1519 }
1520 
1521 /// \sa getLengthOnSingleLine(SourceManager, SourceRange)
1523  const Stmt *S) {
1524  return getLengthOnSingleLine(SM, S->getSourceRange());
1525 }
1526 
1527 /// Eliminate two-edge cycles created by addContextEdges().
1528 ///
1529 /// Once all the context edges are in place, there are plenty of cases where
1530 /// there's a single edge from a top-level statement to a subexpression,
1531 /// followed by a single path note, and then a reverse edge to get back out to
1532 /// the top level. If the statement is simple enough, the subexpression edges
1533 /// just add noise and make it harder to understand what's going on.
1534 ///
1535 /// This function only removes edges in pairs, because removing only one edge
1536 /// might leave other edges dangling.
1537 ///
1538 /// This will not remove edges in more complicated situations:
1539 /// - if there is more than one "hop" leading to or from a subexpression.
1540 /// - if there is an inlined call between the edges instead of a single event.
1541 /// - if the whole statement is large enough that having subexpression arrows
1542 /// might be helpful.
1544  ParentMap &PM) {
1545  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
1546  // Pattern match the current piece and its successor.
1547  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1548 
1549  if (!PieceI) {
1550  ++I;
1551  continue;
1552  }
1553 
1554  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1555  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1556 
1557  PathPieces::iterator NextI = I; ++NextI;
1558  if (NextI == E)
1559  break;
1560 
1561  const auto *PieceNextI =
1562  dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1563 
1564  if (!PieceNextI) {
1565  if (isa<PathDiagnosticEventPiece>(NextI->get())) {
1566  ++NextI;
1567  if (NextI == E)
1568  break;
1569  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1570  }
1571 
1572  if (!PieceNextI) {
1573  ++I;
1574  continue;
1575  }
1576  }
1577 
1578  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1579  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1580 
1581  if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
1582  const size_t MAX_SHORT_LINE_LENGTH = 80;
1583  Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
1584  if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {
1585  Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
1586  if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
1587  Path.erase(I);
1588  I = Path.erase(NextI);
1589  continue;
1590  }
1591  }
1592  }
1593 
1594  ++I;
1595  }
1596 }
1597 
1598 /// Return true if X is contained by Y.
1599 static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y) {
1600  while (X) {
1601  if (X == Y)
1602  return true;
1603  X = PM.getParent(X);
1604  }
1605  return false;
1606 }
1607 
1608 // Remove short edges on the same line less than 3 columns in difference.
1610  ParentMap &PM) {
1611  bool erased = false;
1612 
1613  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
1614  erased ? I : ++I) {
1615  erased = false;
1616 
1617  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1618 
1619  if (!PieceI)
1620  continue;
1621 
1622  const Stmt *start = PieceI->getStartLocation().getStmtOrNull();
1623  const Stmt *end = PieceI->getEndLocation().getStmtOrNull();
1624 
1625  if (!start || !end)
1626  continue;
1627 
1628  const Stmt *endParent = PM.getParent(end);
1629  if (!endParent)
1630  continue;
1631 
1632  if (isConditionForTerminator(end, endParent))
1633  continue;
1634 
1635  SourceLocation FirstLoc = start->getBeginLoc();
1636  SourceLocation SecondLoc = end->getBeginLoc();
1637 
1638  if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
1639  continue;
1640  if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
1641  std::swap(SecondLoc, FirstLoc);
1642 
1643  SourceRange EdgeRange(FirstLoc, SecondLoc);
1644  Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
1645 
1646  // If the statements are on different lines, continue.
1647  if (!ByteWidth)
1648  continue;
1649 
1650  const size_t MAX_PUNY_EDGE_LENGTH = 2;
1651  if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
1652  // FIXME: There are enough /bytes/ between the endpoints of the edge, but
1653  // there might not be enough /columns/. A proper user-visible column count
1654  // is probably too expensive, though.
1655  I = path.erase(I);
1656  erased = true;
1657  continue;
1658  }
1659  }
1660 }
1661 
1662 static void removeIdenticalEvents(PathPieces &path) {
1663  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
1664  const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());
1665 
1666  if (!PieceI)
1667  continue;
1668 
1669  PathPieces::iterator NextI = I; ++NextI;
1670  if (NextI == E)
1671  return;
1672 
1673  const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1674 
1675  if (!PieceNextI)
1676  continue;
1677 
1678  // Erase the second piece if it has the same exact message text.
1679  if (PieceI->getString() == PieceNextI->getString()) {
1680  path.erase(NextI);
1681  }
1682  }
1683 }
1684 
1685 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
1686  OptimizedCallsSet &OCS,
1687  LocationContextMap &LCM) {
1688  bool hasChanges = false;
1689  const LocationContext *LC = LCM[&path];
1690  assert(LC);
1691  ParentMap &PM = LC->getParentMap();
1692 
1693  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
1694  // Optimize subpaths.
1695  if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {
1696  // Record the fact that a call has been optimized so we only do the
1697  // effort once.
1698  if (!OCS.count(CallI)) {
1699  while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
1700  OCS.insert(CallI);
1701  }
1702  ++I;
1703  continue;
1704  }
1705 
1706  // Pattern match the current piece and its successor.
1707  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1708 
1709  if (!PieceI) {
1710  ++I;
1711  continue;
1712  }
1713 
1714  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1715  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1716  const Stmt *level1 = getStmtParent(s1Start, PM);
1717  const Stmt *level2 = getStmtParent(s1End, PM);
1718 
1719  PathPieces::iterator NextI = I; ++NextI;
1720  if (NextI == E)
1721  break;
1722 
1723  const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1724 
1725  if (!PieceNextI) {
1726  ++I;
1727  continue;
1728  }
1729 
1730  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1731  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1732  const Stmt *level3 = getStmtParent(s2Start, PM);
1733  const Stmt *level4 = getStmtParent(s2End, PM);
1734 
1735  // Rule I.
1736  //
1737  // If we have two consecutive control edges whose end/begin locations
1738  // are at the same level (e.g. statements or top-level expressions within
1739  // a compound statement, or siblings share a single ancestor expression),
1740  // then merge them if they have no interesting intermediate event.
1741  //
1742  // For example:
1743  //
1744  // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
1745  // parent is '1'. Here 'x.y.z' represents the hierarchy of statements.
1746  //
1747  // NOTE: this will be limited later in cases where we add barriers
1748  // to prevent this optimization.
1749  if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
1750  PieceI->setEndLocation(PieceNextI->getEndLocation());
1751  path.erase(NextI);
1752  hasChanges = true;
1753  continue;
1754  }
1755 
1756  // Rule II.
1757  //
1758  // Eliminate edges between subexpressions and parent expressions
1759  // when the subexpression is consumed.
1760  //
1761  // NOTE: this will be limited later in cases where we add barriers
1762  // to prevent this optimization.
1763  if (s1End && s1End == s2Start && level2) {
1764  bool removeEdge = false;
1765  // Remove edges into the increment or initialization of a
1766  // loop that have no interleaving event. This means that
1767  // they aren't interesting.
1768  if (isIncrementOrInitInForLoop(s1End, level2))
1769  removeEdge = true;
1770  // Next only consider edges that are not anchored on
1771  // the condition of a terminator. This are intermediate edges
1772  // that we might want to trim.
1773  else if (!isConditionForTerminator(level2, s1End)) {
1774  // Trim edges on expressions that are consumed by
1775  // the parent expression.
1776  if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
1777  removeEdge = true;
1778  }
1779  // Trim edges where a lexical containment doesn't exist.
1780  // For example:
1781  //
1782  // X -> Y -> Z
1783  //
1784  // If 'Z' lexically contains Y (it is an ancestor) and
1785  // 'X' does not lexically contain Y (it is a descendant OR
1786  // it has no lexical relationship at all) then trim.
1787  //
1788  // This can eliminate edges where we dive into a subexpression
1789  // and then pop back out, etc.
1790  else if (s1Start && s2End &&
1791  lexicalContains(PM, s2Start, s2End) &&
1792  !lexicalContains(PM, s1End, s1Start)) {
1793  removeEdge = true;
1794  }
1795  // Trim edges from a subexpression back to the top level if the
1796  // subexpression is on a different line.
1797  //
1798  // A.1 -> A -> B
1799  // becomes
1800  // A.1 -> B
1801  //
1802  // These edges just look ugly and don't usually add anything.
1803  else if (s1Start && s2End &&
1804  lexicalContains(PM, s1Start, s1End)) {
1805  SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
1806  PieceI->getStartLocation().asLocation());
1807  if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
1808  removeEdge = true;
1809  }
1810  }
1811 
1812  if (removeEdge) {
1813  PieceI->setEndLocation(PieceNextI->getEndLocation());
1814  path.erase(NextI);
1815  hasChanges = true;
1816  continue;
1817  }
1818  }
1819 
1820  // Optimize edges for ObjC fast-enumeration loops.
1821  //
1822  // (X -> collection) -> (collection -> element)
1823  //
1824  // becomes:
1825  //
1826  // (X -> element)
1827  if (s1End == s2Start) {
1828  const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3);
1829  if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
1830  s2End == FS->getElement()) {
1831  PieceI->setEndLocation(PieceNextI->getEndLocation());
1832  path.erase(NextI);
1833  hasChanges = true;
1834  continue;
1835  }
1836  }
1837 
1838  // No changes at this index? Move to the next one.
1839  ++I;
1840  }
1841 
1842  if (!hasChanges) {
1843  // Adjust edges into subexpressions to make them more uniform
1844  // and aesthetically pleasing.
1845  addContextEdges(path, SM, PM, LC);
1846  // Remove "cyclical" edges that include one or more context edges.
1847  removeContextCycles(path, SM, PM);
1848  // Hoist edges originating from branch conditions to branches
1849  // for simple branches.
1850  simplifySimpleBranches(path);
1851  // Remove any puny edges left over after primary optimization pass.
1852  removePunyEdges(path, SM, PM);
1853  // Remove identical events.
1854  removeIdenticalEvents(path);
1855  }
1856 
1857  return hasChanges;
1858 }
1859 
1860 /// Drop the very first edge in a path, which should be a function entry edge.
1861 ///
1862 /// If the first edge is not a function entry edge (say, because the first
1863 /// statement had an invalid source location), this function does nothing.
1864 // FIXME: We should just generate invalid edges anyway and have the optimizer
1865 // deal with them.
1867  SourceManager &SM) {
1868  const auto *FirstEdge =
1869  dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());
1870  if (!FirstEdge)
1871  return;
1872 
1873  const Decl *D = LCM[&Path]->getDecl();
1875  if (FirstEdge->getStartLocation() != EntryLoc)
1876  return;
1877 
1878  Path.pop_front();
1879 }
1880 
1881 using VisitorsDiagnosticsTy = llvm::DenseMap<const ExplodedNode *,
1882  std::vector<std::shared_ptr<PathDiagnosticPiece>>>;
1883 
1884 /// This function is responsible for generating diagnostic pieces that are
1885 /// *not* provided by bug report visitors.
1886 /// These diagnostics may differ depending on the consumer's settings,
1887 /// and are therefore constructed separately for each consumer.
1888 ///
1889 /// There are two path diagnostics generation modes: with adding edges (used
1890 /// for plists) and without (used for HTML and text).
1891 /// When edges are added (\p ActiveScheme is Extensive),
1892 /// the path is modified to insert artificially generated
1893 /// edges.
1894 /// Otherwise, more detailed diagnostics is emitted for block edges, explaining
1895 /// the transitions in words.
1896 static std::unique_ptr<PathDiagnostic> generatePathDiagnosticForConsumer(
1898  PathDiagnosticBuilder &PDB,
1899  const ExplodedNode *ErrorNode,
1900  const VisitorsDiagnosticsTy &VisitorsDiagnostics) {
1901 
1902  bool GenerateDiagnostics = (ActiveScheme != PathDiagnosticConsumer::None);
1903  bool AddPathEdges = (ActiveScheme == PathDiagnosticConsumer::Extensive);
1904  SourceManager &SM = PDB.getSourceManager();
1905  BugReport *R = PDB.getBugReport();
1906  AnalyzerOptions &Opts = PDB.getBugReporter().getAnalyzerOptions();
1907  StackDiagVector CallStack;
1908  InterestingExprs IE;
1909  LocationContextMap LCM;
1910  std::unique_ptr<PathDiagnostic> PD = generateEmptyDiagnosticForReport(R, SM);
1911 
1912  if (GenerateDiagnostics) {
1913  auto EndNotes = VisitorsDiagnostics.find(ErrorNode);
1914  std::shared_ptr<PathDiagnosticPiece> LastPiece;
1915  if (EndNotes != VisitorsDiagnostics.end()) {
1916  assert(!EndNotes->second.empty());
1917  LastPiece = EndNotes->second[0];
1918  } else {
1919  LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, ErrorNode, *R);
1920  }
1921  PD->setEndOfPath(LastPiece);
1922  }
1923 
1924  PathDiagnosticLocation PrevLoc = PD->getLocation();
1925  const ExplodedNode *NextNode = ErrorNode->getFirstPred();
1926  while (NextNode) {
1927  if (GenerateDiagnostics)
1929  NextNode, *PD, PrevLoc, PDB, LCM, CallStack, IE, AddPathEdges);
1930 
1931  auto VisitorNotes = VisitorsDiagnostics.find(NextNode);
1932  NextNode = NextNode->getFirstPred();
1933  if (!GenerateDiagnostics || VisitorNotes == VisitorsDiagnostics.end())
1934  continue;
1935 
1936  // This is a workaround due to inability to put shared PathDiagnosticPiece
1937  // into a FoldingSet.
1938  std::set<llvm::FoldingSetNodeID> DeduplicationSet;
1939 
1940  // Add pieces from custom visitors.
1941  for (const auto &Note : VisitorNotes->second) {
1942  llvm::FoldingSetNodeID ID;
1943  Note->Profile(ID);
1944  auto P = DeduplicationSet.insert(ID);
1945  if (!P.second)
1946  continue;
1947 
1948  if (AddPathEdges)
1949  addEdgeToPath(PD->getActivePath(), PrevLoc, Note->getLocation(),
1950  PDB.LC);
1951  updateStackPiecesWithMessage(*Note, CallStack);
1952  PD->getActivePath().push_front(Note);
1953  }
1954  }
1955 
1956  if (AddPathEdges) {
1957  // Add an edge to the start of the function.
1958  // We'll prune it out later, but it helps make diagnostics more uniform.
1959  const StackFrameContext *CalleeLC = PDB.LC->getStackFrame();
1960  const Decl *D = CalleeLC->getDecl();
1961  addEdgeToPath(PD->getActivePath(), PrevLoc,
1962  PathDiagnosticLocation::createBegin(D, SM), CalleeLC);
1963  }
1964 
1965  if (!AddPathEdges && GenerateDiagnostics)
1966  CompactPathDiagnostic(PD->getMutablePieces(), SM);
1967 
1968  // Finally, prune the diagnostic path of uninteresting stuff.
1969  if (!PD->path.empty()) {
1970  if (R->shouldPrunePath() && Opts.shouldPrunePaths()) {
1971  bool stillHasNotes =
1972  removeUnneededCalls(PD->getMutablePieces(), R, LCM);
1973  assert(stillHasNotes);
1974  (void)stillHasNotes;
1975  }
1976 
1977  // Redirect all call pieces to have valid locations.
1978  adjustCallLocations(PD->getMutablePieces());
1979  removePiecesWithInvalidLocations(PD->getMutablePieces());
1980 
1981  if (AddPathEdges) {
1982 
1983  // Reduce the number of edges from a very conservative set
1984  // to an aesthetically pleasing subset that conveys the
1985  // necessary information.
1986  OptimizedCallsSet OCS;
1987  while (optimizeEdges(PD->getMutablePieces(), SM, OCS, LCM)) {}
1988 
1989  // Drop the very first function-entry edge. It's not really necessary
1990  // for top-level functions.
1991  dropFunctionEntryEdge(PD->getMutablePieces(), LCM, SM);
1992  }
1993 
1994  // Remove messages that are basically the same, and edges that may not
1995  // make sense.
1996  // We have to do this after edge optimization in the Extensive mode.
1997  removeRedundantMsgs(PD->getMutablePieces());
1998  removeEdgesToDefaultInitializers(PD->getMutablePieces());
1999  }
2000  return PD;
2001 }
2002 
2003 
2004 //===----------------------------------------------------------------------===//
2005 // Methods for BugType and subclasses.
2006 //===----------------------------------------------------------------------===//
2007 
2008 void BugType::anchor() {}
2009 
2011 
2012 void BuiltinBug::anchor() {}
2013 
2014 //===----------------------------------------------------------------------===//
2015 // Methods for BugReport and subclasses.
2016 //===----------------------------------------------------------------------===//
2017 
2018 void BugReport::NodeResolver::anchor() {}
2019 
2020 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) {
2021  if (!visitor)
2022  return;
2023 
2024  llvm::FoldingSetNodeID ID;
2025  visitor->Profile(ID);
2026 
2027  void *InsertPos = nullptr;
2028  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2029  return;
2030  }
2031 
2032  Callbacks.push_back(std::move(visitor));
2033 }
2034 
2036  Callbacks.clear();
2037 }
2038 
2040  while (!interestingSymbols.empty()) {
2041  popInterestingSymbolsAndRegions();
2042  }
2043 }
2044 
2046  if (DeclWithIssue)
2047  return DeclWithIssue;
2048 
2049  const ExplodedNode *N = getErrorNode();
2050  if (!N)
2051  return nullptr;
2052 
2053  const LocationContext *LC = N->getLocationContext();
2054  return LC->getStackFrame()->getDecl();
2055 }
2056 
2057 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2058  hash.AddPointer(&BT);
2059  hash.AddString(Description);
2060  PathDiagnosticLocation UL = getUniqueingLocation();
2061  if (UL.isValid()) {
2062  UL.Profile(hash);
2063  } else if (Location.isValid()) {
2064  Location.Profile(hash);
2065  } else {
2066  assert(ErrorNode);
2067  hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2068  }
2069 
2070  for (SourceRange range : Ranges) {
2071  if (!range.isValid())
2072  continue;
2073  hash.AddInteger(range.getBegin().getRawEncoding());
2074  hash.AddInteger(range.getEnd().getRawEncoding());
2075  }
2076 }
2077 
2079  if (!sym)
2080  return;
2081 
2082  getInterestingSymbols().insert(sym);
2083 
2084  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
2085  getInterestingRegions().insert(meta->getRegion());
2086 }
2087 
2089  if (!R)
2090  return;
2091 
2092  R = R->getBaseRegion();
2093  getInterestingRegions().insert(R);
2094 
2095  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2096  getInterestingSymbols().insert(SR->getSymbol());
2097 }
2098 
2100  markInteresting(V.getAsRegion());
2101  markInteresting(V.getAsSymbol());
2102 }
2103 
2105  if (!LC)
2106  return;
2107  InterestingLocationContexts.insert(LC);
2108 }
2109 
2111  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2112 }
2113 
2115  if (!sym)
2116  return false;
2117  // We don't currently consider metadata symbols to be interesting
2118  // even if we know their region is interesting. Is that correct behavior?
2119  return getInterestingSymbols().count(sym);
2120 }
2121 
2123  if (!R)
2124  return false;
2125  R = R->getBaseRegion();
2126  bool b = getInterestingRegions().count(R);
2127  if (b)
2128  return true;
2129  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2130  return getInterestingSymbols().count(SR->getSymbol());
2131  return false;
2132 }
2133 
2135  if (!LC)
2136  return false;
2137  return InterestingLocationContexts.count(LC);
2138 }
2139 
2140 void BugReport::lazyInitializeInterestingSets() {
2141  if (interestingSymbols.empty()) {
2142  interestingSymbols.push_back(new Symbols());
2143  interestingRegions.push_back(new Regions());
2144  }
2145 }
2146 
2147 BugReport::Symbols &BugReport::getInterestingSymbols() {
2148  lazyInitializeInterestingSets();
2149  return *interestingSymbols.back();
2150 }
2151 
2152 BugReport::Regions &BugReport::getInterestingRegions() {
2153  lazyInitializeInterestingSets();
2154  return *interestingRegions.back();
2155 }
2156 
2157 void BugReport::pushInterestingSymbolsAndRegions() {
2158  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2159  interestingRegions.push_back(new Regions(getInterestingRegions()));
2160 }
2161 
2162 void BugReport::popInterestingSymbolsAndRegions() {
2163  delete interestingSymbols.pop_back_val();
2164  delete interestingRegions.pop_back_val();
2165 }
2166 
2167 const Stmt *BugReport::getStmt() const {
2168  if (!ErrorNode)
2169  return nullptr;
2170 
2171  ProgramPoint ProgP = ErrorNode->getLocation();
2172  const Stmt *S = nullptr;
2173 
2174  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2175  CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2176  if (BE->getBlock() == &Exit)
2177  S = GetPreviousStmt(ErrorNode);
2178  }
2179  if (!S)
2180  S = PathDiagnosticLocation::getStmt(ErrorNode);
2181 
2182  return S;
2183 }
2184 
2185 llvm::iterator_range<BugReport::ranges_iterator> BugReport::getRanges() {
2186  // If no custom ranges, add the range of the statement corresponding to
2187  // the error node.
2188  if (Ranges.empty()) {
2189  if (const auto *E = dyn_cast_or_null<Expr>(getStmt()))
2190  addRange(E->getSourceRange());
2191  else
2192  return llvm::make_range(ranges_iterator(), ranges_iterator());
2193  }
2194 
2195  // User-specified absence of range info.
2196  if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2197  return llvm::make_range(ranges_iterator(), ranges_iterator());
2198 
2199  return llvm::make_range(Ranges.begin(), Ranges.end());
2200 }
2201 
2203  if (ErrorNode) {
2204  assert(!Location.isValid() &&
2205  "Either Location or ErrorNode should be specified but not both.");
2206  return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2207  }
2208 
2209  assert(Location.isValid());
2210  return Location;
2211 }
2212 
2213 //===----------------------------------------------------------------------===//
2214 // Methods for BugReporter and subclasses.
2215 //===----------------------------------------------------------------------===//
2216 
2218 
2219 GRBugReporter::~GRBugReporter() = default;
2220 
2222 
2223 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2224 
2226 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2227 
2229  FlushReports();
2230 
2231  // Free the bug reports we are tracking.
2232  for (const auto I : EQClassesVector)
2233  delete I;
2234 }
2235 
2237  if (BugTypes.isEmpty())
2238  return;
2239 
2240  // First flush the warnings for each BugType. This may end up creating new
2241  // warnings and new BugTypes.
2242  // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2243  // Turn NSErrorChecker into a proper checker and remove this.
2244  SmallVector<const BugType *, 16> bugTypes(BugTypes.begin(), BugTypes.end());
2245  for (const auto I : bugTypes)
2246  const_cast<BugType*>(I)->FlushReports(*this);
2247 
2248  // We need to flush reports in deterministic order to ensure the order
2249  // of the reports is consistent between runs.
2250  for (const auto EQ : EQClassesVector)
2251  FlushReport(*EQ);
2252 
2253  // BugReporter owns and deletes only BugTypes created implicitly through
2254  // EmitBasicReport.
2255  // FIXME: There are leaks from checkers that assume that the BugTypes they
2256  // create will be destroyed by the BugReporter.
2257  llvm::DeleteContainerSeconds(StrBugTypes);
2258 
2259  // Remove all references to the BugType objects.
2260  BugTypes = F.getEmptySet();
2261 }
2262 
2263 //===----------------------------------------------------------------------===//
2264 // PathDiagnostics generation.
2265 //===----------------------------------------------------------------------===//
2266 
2267 namespace {
2268 
2269 /// A wrapper around a report graph, which contains only a single path, and its
2270 /// node maps.
2271 class ReportGraph {
2272 public:
2273  InterExplodedGraphMap BackMap;
2274  std::unique_ptr<ExplodedGraph> Graph;
2275  const ExplodedNode *ErrorNode;
2276  size_t Index;
2277 };
2278 
2279 /// A wrapper around a trimmed graph and its node maps.
2280 class TrimmedGraph {
2281  InterExplodedGraphMap InverseMap;
2282 
2283  using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;
2284 
2285  PriorityMapTy PriorityMap;
2286 
2287  using NodeIndexPair = std::pair<const ExplodedNode *, size_t>;
2288 
2289  SmallVector<NodeIndexPair, 32> ReportNodes;
2290 
2291  std::unique_ptr<ExplodedGraph> G;
2292 
2293  /// A helper class for sorting ExplodedNodes by priority.
2294  template <bool Descending>
2295  class PriorityCompare {
2296  const PriorityMapTy &PriorityMap;
2297 
2298  public:
2299  PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2300 
2301  bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2302  PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2303  PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2304  PriorityMapTy::const_iterator E = PriorityMap.end();
2305 
2306  if (LI == E)
2307  return Descending;
2308  if (RI == E)
2309  return !Descending;
2310 
2311  return Descending ? LI->second > RI->second
2312  : LI->second < RI->second;
2313  }
2314 
2315  bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2316  return (*this)(LHS.first, RHS.first);
2317  }
2318  };
2319 
2320 public:
2321  TrimmedGraph(const ExplodedGraph *OriginalGraph,
2323 
2324  bool popNextReportGraph(ReportGraph &GraphWrapper);
2325 };
2326 
2327 } // namespace
2328 
2329 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2331  // The trimmed graph is created in the body of the constructor to ensure
2332  // that the DenseMaps have been initialized already.
2333  InterExplodedGraphMap ForwardMap;
2334  G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
2335 
2336  // Find the (first) error node in the trimmed graph. We just need to consult
2337  // the node map which maps from nodes in the original graph to nodes
2338  // in the new graph.
2339  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2340 
2341  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2342  if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2343  ReportNodes.push_back(std::make_pair(NewNode, i));
2344  RemainingNodes.insert(NewNode);
2345  }
2346  }
2347 
2348  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2349 
2350  // Perform a forward BFS to find all the shortest paths.
2351  std::queue<const ExplodedNode *> WS;
2352 
2353  assert(G->num_roots() == 1);
2354  WS.push(*G->roots_begin());
2355  unsigned Priority = 0;
2356 
2357  while (!WS.empty()) {
2358  const ExplodedNode *Node = WS.front();
2359  WS.pop();
2360 
2361  PriorityMapTy::iterator PriorityEntry;
2362  bool IsNew;
2363  std::tie(PriorityEntry, IsNew) =
2364  PriorityMap.insert(std::make_pair(Node, Priority));
2365  ++Priority;
2366 
2367  if (!IsNew) {
2368  assert(PriorityEntry->second <= Priority);
2369  continue;
2370  }
2371 
2372  if (RemainingNodes.erase(Node))
2373  if (RemainingNodes.empty())
2374  break;
2375 
2377  E = Node->succ_end();
2378  I != E; ++I)
2379  WS.push(*I);
2380  }
2381 
2382  // Sort the error paths from longest to shortest.
2383  llvm::sort(ReportNodes.begin(), ReportNodes.end(),
2384  PriorityCompare<true>(PriorityMap));
2385 }
2386 
2387 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2388  if (ReportNodes.empty())
2389  return false;
2390 
2391  const ExplodedNode *OrigN;
2392  std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2393  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2394  "error node not accessible from root");
2395 
2396  // Create a new graph with a single path. This is the graph
2397  // that will be returned to the caller.
2398  auto GNew = llvm::make_unique<ExplodedGraph>();
2399  GraphWrapper.BackMap.clear();
2400 
2401  // Now walk from the error node up the BFS path, always taking the
2402  // predeccessor with the lowest number.
2403  ExplodedNode *Succ = nullptr;
2404  while (true) {
2405  // Create the equivalent node in the new graph with the same state
2406  // and location.
2407  ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
2408  OrigN->isSink());
2409 
2410  // Store the mapping to the original node.
2411  InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2412  assert(IMitr != InverseMap.end() && "No mapping to original node.");
2413  GraphWrapper.BackMap[NewN] = IMitr->second;
2414 
2415  // Link up the new node with the previous node.
2416  if (Succ)
2417  Succ->addPredecessor(NewN, *GNew);
2418  else
2419  GraphWrapper.ErrorNode = NewN;
2420 
2421  Succ = NewN;
2422 
2423  // Are we at the final node?
2424  if (OrigN->pred_empty()) {
2425  GNew->addRoot(NewN);
2426  break;
2427  }
2428 
2429  // Find the next predeccessor node. We choose the node that is marked
2430  // with the lowest BFS number.
2431  OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2432  PriorityCompare<false>(PriorityMap));
2433  }
2434 
2435  GraphWrapper.Graph = std::move(GNew);
2436 
2437  return true;
2438 }
2439 
2440 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2441 /// and collapses PathDiagosticPieces that are expanded by macros.
2442 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2443  using MacroStackTy =
2444  std::vector<
2445  std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>;
2446 
2447  using PiecesTy = std::vector<std::shared_ptr<PathDiagnosticPiece>>;
2448 
2449  MacroStackTy MacroStack;
2450  PiecesTy Pieces;
2451 
2452  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2453  I != E; ++I) {
2454  const auto &piece = *I;
2455 
2456  // Recursively compact calls.
2457  if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {
2458  CompactPathDiagnostic(call->path, SM);
2459  }
2460 
2461  // Get the location of the PathDiagnosticPiece.
2462  const FullSourceLoc Loc = piece->getLocation().asLocation();
2463 
2464  // Determine the instantiation location, which is the location we group
2465  // related PathDiagnosticPieces.
2466  SourceLocation InstantiationLoc = Loc.isMacroID() ?
2467  SM.getExpansionLoc(Loc) :
2468  SourceLocation();
2469 
2470  if (Loc.isFileID()) {
2471  MacroStack.clear();
2472  Pieces.push_back(piece);
2473  continue;
2474  }
2475 
2476  assert(Loc.isMacroID());
2477 
2478  // Is the PathDiagnosticPiece within the same macro group?
2479  if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
2480  MacroStack.back().first->subPieces.push_back(piece);
2481  continue;
2482  }
2483 
2484  // We aren't in the same group. Are we descending into a new macro
2485  // or are part of an old one?
2486  std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;
2487 
2488  SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2489  SM.getExpansionLoc(Loc) :
2490  SourceLocation();
2491 
2492  // Walk the entire macro stack.
2493  while (!MacroStack.empty()) {
2494  if (InstantiationLoc == MacroStack.back().second) {
2495  MacroGroup = MacroStack.back().first;
2496  break;
2497  }
2498 
2499  if (ParentInstantiationLoc == MacroStack.back().second) {
2500  MacroGroup = MacroStack.back().first;
2501  break;
2502  }
2503 
2504  MacroStack.pop_back();
2505  }
2506 
2507  if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
2508  // Create a new macro group and add it to the stack.
2509  auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(
2510  PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2511 
2512  if (MacroGroup)
2513  MacroGroup->subPieces.push_back(NewGroup);
2514  else {
2515  assert(InstantiationLoc.isFileID());
2516  Pieces.push_back(NewGroup);
2517  }
2518 
2519  MacroGroup = NewGroup;
2520  MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2521  }
2522 
2523  // Finally, add the PathDiagnosticPiece to the group.
2524  MacroGroup->subPieces.push_back(piece);
2525  }
2526 
2527  // Now take the pieces and construct a new PathDiagnostic.
2528  path.clear();
2529 
2530  path.insert(path.end(), Pieces.begin(), Pieces.end());
2531 }
2532 
2533 /// Generate notes from all visitors.
2534 /// Notes associated with {@code ErrorNode} are generated using
2535 /// {@code getEndPath}, and the rest are generated with {@code VisitNode}.
2536 static std::unique_ptr<VisitorsDiagnosticsTy>
2537 generateVisitorsDiagnostics(BugReport *R, const ExplodedNode *ErrorNode,
2538  BugReporterContext &BRC) {
2539  auto Notes = llvm::make_unique<VisitorsDiagnosticsTy>();
2540  BugReport::VisitorList visitors;
2541 
2542  // Run visitors on all nodes starting from the node *before* the last one.
2543  // The last node is reserved for notes generated with {@code getEndPath}.
2544  const ExplodedNode *NextNode = ErrorNode->getFirstPred();
2545  while (NextNode) {
2546 
2547  // At each iteration, move all visitors from report to visitor list.
2549  E = R->visitor_end();
2550  I != E; ++I) {
2551  visitors.push_back(std::move(*I));
2552  }
2553  R->clearVisitors();
2554 
2555  const ExplodedNode *Pred = NextNode->getFirstPred();
2556  if (!Pred) {
2557  std::shared_ptr<PathDiagnosticPiece> LastPiece;
2558  for (auto &V : visitors) {
2559  V->finalizeVisitor(BRC, ErrorNode, *R);
2560 
2561  if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) {
2562  assert(!LastPiece &&
2563  "There can only be one final piece in a diagnostic.");
2564  LastPiece = std::move(Piece);
2565  (*Notes)[ErrorNode].push_back(LastPiece);
2566  }
2567  }
2568  break;
2569  }
2570 
2571  for (auto &V : visitors) {
2572  auto P = V->VisitNode(NextNode, Pred, BRC, *R);
2573  if (P)
2574  (*Notes)[NextNode].push_back(std::move(P));
2575  }
2576 
2577  if (!R->isValid())
2578  break;
2579 
2580  NextNode = Pred;
2581  }
2582 
2583  return Notes;
2584 }
2585 
2586 /// Find a non-invalidated report for a given equivalence class,
2587 /// and return together with a cache of visitors notes.
2588 /// If none found, return a nullptr paired with an empty cache.
2589 static
2590 std::pair<BugReport*, std::unique_ptr<VisitorsDiagnosticsTy>> findValidReport(
2591  TrimmedGraph &TrimG,
2592  ReportGraph &ErrorGraph,
2593  ArrayRef<BugReport *> &bugReports,
2594  AnalyzerOptions &Opts,
2595  GRBugReporter &Reporter) {
2596 
2597  while (TrimG.popNextReportGraph(ErrorGraph)) {
2598  // Find the BugReport with the original location.
2599  assert(ErrorGraph.Index < bugReports.size());
2600  BugReport *R = bugReports[ErrorGraph.Index];
2601  assert(R && "No original report found for sliced graph.");
2602  assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
2603  const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode;
2604 
2605  // Register refutation visitors first, if they mark the bug invalid no
2606  // further analysis is required
2607  R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
2608 
2609  // Register additional node visitors.
2610  R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
2611  R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
2612  R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
2613 
2614  BugReporterContext BRC(Reporter, ErrorGraph.BackMap);
2615 
2616  // Run all visitors on a given graph, once.
2617  std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes =
2618  generateVisitorsDiagnostics(R, ErrorNode, BRC);
2619 
2620  if (R->isValid()) {
2621  if (Opts.shouldCrosscheckWithZ3()) {
2622  // If crosscheck is enabled, remove all visitors, add the refutation
2623  // visitor and check again
2624  R->clearVisitors();
2625  R->addVisitor(llvm::make_unique<FalsePositiveRefutationBRVisitor>());
2626 
2627  // We don't overrite the notes inserted by other visitors because the
2628  // refutation manager does not add any new note to the path
2629  generateVisitorsDiagnostics(R, ErrorGraph.ErrorNode, BRC);
2630  }
2631 
2632  // Check if the bug is still valid
2633  if (R->isValid())
2634  return std::make_pair(R, std::move(visitorNotes));
2635  }
2636  }
2637 
2638  return std::make_pair(nullptr, llvm::make_unique<VisitorsDiagnosticsTy>());
2639 }
2640 
2641 std::unique_ptr<DiagnosticForConsumerMapTy>
2644  ArrayRef<BugReport *> &bugReports) {
2645  assert(!bugReports.empty());
2646 
2647  auto Out = llvm::make_unique<DiagnosticForConsumerMapTy>();
2648  bool HasValid = false;
2650  for (const auto I : bugReports) {
2651  if (I->isValid()) {
2652  HasValid = true;
2653  errorNodes.push_back(I->getErrorNode());
2654  } else {
2655  // Keep the errorNodes list in sync with the bugReports list.
2656  errorNodes.push_back(nullptr);
2657  }
2658  }
2659 
2660  // If all the reports have been marked invalid by a previous path generation,
2661  // we're done.
2662  if (!HasValid)
2663  return Out;
2664 
2665  TrimmedGraph TrimG(&getGraph(), errorNodes);
2666  ReportGraph ErrorGraph;
2667  auto ReportInfo = findValidReport(TrimG, ErrorGraph, bugReports,
2668  getAnalyzerOptions(), *this);
2669  BugReport *R = ReportInfo.first;
2670 
2671  if (R && R->isValid()) {
2672  const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode;
2673  for (PathDiagnosticConsumer *PC : consumers) {
2674  PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, PC);
2675  std::unique_ptr<PathDiagnostic> PD = generatePathDiagnosticForConsumer(
2676  PC->getGenerationScheme(), PDB, ErrorNode, *ReportInfo.second);
2677  (*Out)[PC] = std::move(PD);
2678  }
2679  }
2680 
2681  return Out;
2682 }
2683 
2684 void BugReporter::Register(BugType *BT) {
2685  BugTypes = F.add(BugTypes, BT);
2686 }
2687 
2688 void BugReporter::emitReport(std::unique_ptr<BugReport> R) {
2689  if (const ExplodedNode *E = R->getErrorNode()) {
2690  // An error node must either be a sink or have a tag, otherwise
2691  // it could get reclaimed before the path diagnostic is created.
2692  assert((E->isSink() || E->getLocation().getTag()) &&
2693  "Error node must either be a sink or have a tag");
2694 
2695  const AnalysisDeclContext *DeclCtx =
2696  E->getLocationContext()->getAnalysisDeclContext();
2697  // The source of autosynthesized body can be handcrafted AST or a model
2698  // file. The locations from handcrafted ASTs have no valid source locations
2699  // and have to be discarded. Locations from model files should be preserved
2700  // for processing and reporting.
2701  if (DeclCtx->isBodyAutosynthesized() &&
2703  return;
2704  }
2705 
2706  bool ValidSourceLoc = R->getLocation(getSourceManager()).isValid();
2707  assert(ValidSourceLoc);
2708  // If we mess up in a release build, we'd still prefer to just drop the bug
2709  // instead of trying to go on.
2710  if (!ValidSourceLoc)
2711  return;
2712 
2713  // Compute the bug report's hash to determine its equivalence class.
2714  llvm::FoldingSetNodeID ID;
2715  R->Profile(ID);
2716 
2717  // Lookup the equivance class. If there isn't one, create it.
2718  BugType& BT = R->getBugType();
2719  Register(&BT);
2720  void *InsertPos;
2721  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
2722 
2723  if (!EQ) {
2724  EQ = new BugReportEquivClass(std::move(R));
2725  EQClasses.InsertNode(EQ, InsertPos);
2726  EQClassesVector.push_back(EQ);
2727  } else
2728  EQ->AddReport(std::move(R));
2729 }
2730 
2731 //===----------------------------------------------------------------------===//
2732 // Emitting reports in equivalence classes.
2733 //===----------------------------------------------------------------------===//
2734 
2735 namespace {
2736 
2737 struct FRIEC_WLItem {
2738  const ExplodedNode *N;
2740 
2741  FRIEC_WLItem(const ExplodedNode *n)
2742  : N(n), I(N->succ_begin()), E(N->succ_end()) {}
2743 };
2744 
2745 } // namespace
2746 
2747 static const CFGBlock *findBlockForNode(const ExplodedNode *N) {
2748  ProgramPoint P = N->getLocation();
2749  if (auto BEP = P.getAs<BlockEntrance>())
2750  return BEP->getBlock();
2751 
2752  // Find the node's current statement in the CFG.
2753  if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
2755  ->getCFGStmtMap()->getBlock(S);
2756 
2757  return nullptr;
2758 }
2759 
2760 // Returns true if by simply looking at the block, we can be sure that it
2761 // results in a sink during analysis. This is useful to know when the analysis
2762 // was interrupted, and we try to figure out if it would sink eventually.
2763 // There may be many more reasons why a sink would appear during analysis
2764 // (eg. checkers may generate sinks arbitrarily), but here we only consider
2765 // sinks that would be obvious by looking at the CFG.
2766 static bool isImmediateSinkBlock(const CFGBlock *Blk) {
2767  if (Blk->hasNoReturnElement())
2768  return true;
2769 
2770  // FIXME: Throw-expressions are currently generating sinks during analysis:
2771  // they're not supported yet, and also often used for actually terminating
2772  // the program. So we should treat them as sinks in this analysis as well,
2773  // at least for now, but once we have better support for exceptions,
2774  // we'd need to carefully handle the case when the throw is being
2775  // immediately caught.
2776  if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) {
2777  if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
2778  if (isa<CXXThrowExpr>(StmtElm->getStmt()))
2779  return true;
2780  return false;
2781  }))
2782  return true;
2783 
2784  return false;
2785 }
2786 
2787 // Returns true if by looking at the CFG surrounding the node's program
2788 // point, we can be sure that any analysis starting from this point would
2789 // eventually end with a sink. We scan the child CFG blocks in a depth-first
2790 // manner and see if all paths eventually end up in an immediate sink block.
2791 static bool isInevitablySinking(const ExplodedNode *N) {
2792  const CFG &Cfg = N->getCFG();
2793 
2794  const CFGBlock *StartBlk = findBlockForNode(N);
2795  if (!StartBlk)
2796  return false;
2797  if (isImmediateSinkBlock(StartBlk))
2798  return true;
2799 
2801  llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
2802 
2803  DFSWorkList.push_back(StartBlk);
2804  while (!DFSWorkList.empty()) {
2805  const CFGBlock *Blk = DFSWorkList.back();
2806  DFSWorkList.pop_back();
2807  Visited.insert(Blk);
2808 
2809  for (const auto &Succ : Blk->succs()) {
2810  if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
2811  if (SuccBlk == &Cfg.getExit()) {
2812  // If at least one path reaches the CFG exit, it means that control is
2813  // returned to the caller. For now, say that we are not sure what
2814  // happens next. If necessary, this can be improved to analyze
2815  // the parent StackFrameContext's call site in a similar manner.
2816  return false;
2817  }
2818 
2819  if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {
2820  // If the block has reachable child blocks that aren't no-return,
2821  // add them to the worklist.
2822  DFSWorkList.push_back(SuccBlk);
2823  }
2824  }
2825  }
2826  }
2827 
2828  // Nothing reached the exit. It can only mean one thing: there's no return.
2829  return true;
2830 }
2831 
2832 static BugReport *
2833 FindReportInEquivalenceClass(BugReportEquivClass& EQ,
2834  SmallVectorImpl<BugReport*> &bugReports) {
2835  BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
2836  assert(I != E);
2837  BugType& BT = I->getBugType();
2838 
2839  // If we don't need to suppress any of the nodes because they are
2840  // post-dominated by a sink, simply add all the nodes in the equivalence class
2841  // to 'Nodes'. Any of the reports will serve as a "representative" report.
2842  if (!BT.isSuppressOnSink()) {
2843  BugReport *R = &*I;
2844  for (auto &I : EQ) {
2845  const ExplodedNode *N = I.getErrorNode();
2846  if (N) {
2847  R = &I;
2848  bugReports.push_back(R);
2849  }
2850  }
2851  return R;
2852  }
2853 
2854  // For bug reports that should be suppressed when all paths are post-dominated
2855  // by a sink node, iterate through the reports in the equivalence class
2856  // until we find one that isn't post-dominated (if one exists). We use a
2857  // DFS traversal of the ExplodedGraph to find a non-sink node. We could write
2858  // this as a recursive function, but we don't want to risk blowing out the
2859  // stack for very long paths.
2860  BugReport *exampleReport = nullptr;
2861 
2862  for (; I != E; ++I) {
2863  const ExplodedNode *errorNode = I->getErrorNode();
2864 
2865  if (!errorNode)
2866  continue;
2867  if (errorNode->isSink()) {
2868  llvm_unreachable(
2869  "BugType::isSuppressSink() should not be 'true' for sink end nodes");
2870  }
2871  // No successors? By definition this nodes isn't post-dominated by a sink.
2872  if (errorNode->succ_empty()) {
2873  bugReports.push_back(&*I);
2874  if (!exampleReport)
2875  exampleReport = &*I;
2876  continue;
2877  }
2878 
2879  // See if we are in a no-return CFG block. If so, treat this similarly
2880  // to being post-dominated by a sink. This works better when the analysis
2881  // is incomplete and we have never reached the no-return function call(s)
2882  // that we'd inevitably bump into on this path.
2883  if (isInevitablySinking(errorNode))
2884  continue;
2885 
2886  // At this point we know that 'N' is not a sink and it has at least one
2887  // successor. Use a DFS worklist to find a non-sink end-of-path node.
2888  using WLItem = FRIEC_WLItem;
2889  using DFSWorkList = SmallVector<WLItem, 10>;
2890 
2891  llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
2892 
2893  DFSWorkList WL;
2894  WL.push_back(errorNode);
2895  Visited[errorNode] = 1;
2896 
2897  while (!WL.empty()) {
2898  WLItem &WI = WL.back();
2899  assert(!WI.N->succ_empty());
2900 
2901  for (; WI.I != WI.E; ++WI.I) {
2902  const ExplodedNode *Succ = *WI.I;
2903  // End-of-path node?
2904  if (Succ->succ_empty()) {
2905  // If we found an end-of-path node that is not a sink.
2906  if (!Succ->isSink()) {
2907  bugReports.push_back(&*I);
2908  if (!exampleReport)
2909  exampleReport = &*I;
2910  WL.clear();
2911  break;
2912  }
2913  // Found a sink? Continue on to the next successor.
2914  continue;
2915  }
2916  // Mark the successor as visited. If it hasn't been explored,
2917  // enqueue it to the DFS worklist.
2918  unsigned &mark = Visited[Succ];
2919  if (!mark) {
2920  mark = 1;
2921  WL.push_back(Succ);
2922  break;
2923  }
2924  }
2925 
2926  // The worklist may have been cleared at this point. First
2927  // check if it is empty before checking the last item.
2928  if (!WL.empty() && &WL.back() == &WI)
2929  WL.pop_back();
2930  }
2931  }
2932 
2933  // ExampleReport will be NULL if all the nodes in the equivalence class
2934  // were post-dominated by sinks.
2935  return exampleReport;
2936 }
2937 
2938 void BugReporter::FlushReport(BugReportEquivClass& EQ) {
2939  SmallVector<BugReport*, 10> bugReports;
2940  BugReport *report = FindReportInEquivalenceClass(EQ, bugReports);
2941  if (!report)
2942  return;
2943 
2944  ArrayRef<PathDiagnosticConsumer*> Consumers = getPathDiagnosticConsumers();
2945  std::unique_ptr<DiagnosticForConsumerMapTy> Diagnostics =
2946  generateDiagnosticForConsumerMap(report, Consumers, bugReports);
2947 
2948  for (auto &P : *Diagnostics) {
2949  PathDiagnosticConsumer *Consumer = P.first;
2950  std::unique_ptr<PathDiagnostic> &PD = P.second;
2951 
2952  // If the path is empty, generate a single step path with the location
2953  // of the issue.
2954  if (PD->path.empty()) {
2956  auto piece = llvm::make_unique<PathDiagnosticEventPiece>(
2957  L, report->getDescription());
2958  for (SourceRange Range : report->getRanges())
2959  piece->addRange(Range);
2960  PD->setEndOfPath(std::move(piece));
2961  }
2962 
2963  PathPieces &Pieces = PD->getMutablePieces();
2964  if (getAnalyzerOptions().shouldDisplayNotesAsEvents()) {
2965  // For path diagnostic consumers that don't support extra notes,
2966  // we may optionally convert those to path notes.
2967  for (auto I = report->getNotes().rbegin(),
2968  E = report->getNotes().rend(); I != E; ++I) {
2969  PathDiagnosticNotePiece *Piece = I->get();
2970  auto ConvertedPiece = std::make_shared<PathDiagnosticEventPiece>(
2971  Piece->getLocation(), Piece->getString());
2972  for (const auto &R: Piece->getRanges())
2973  ConvertedPiece->addRange(R);
2974 
2975  Pieces.push_front(std::move(ConvertedPiece));
2976  }
2977  } else {
2978  for (auto I = report->getNotes().rbegin(),
2979  E = report->getNotes().rend(); I != E; ++I)
2980  Pieces.push_front(*I);
2981  }
2982 
2983  // Get the meta data.
2984  const BugReport::ExtraTextList &Meta = report->getExtraText();
2985  for (const auto &i : Meta)
2986  PD->addMeta(i);
2987 
2988  Consumer->HandlePathDiagnostic(std::move(PD));
2989  }
2990 }
2991 
2992 /// Insert all lines participating in the function signature \p Signature
2993 /// into \p ExecutedLines.
2994 static void populateExecutedLinesWithFunctionSignature(
2995  const Decl *Signature, SourceManager &SM,
2996  std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) {
2997  SourceRange SignatureSourceRange;
2998  const Stmt* Body = Signature->getBody();
2999  if (const auto FD = dyn_cast<FunctionDecl>(Signature)) {
3000  SignatureSourceRange = FD->getSourceRange();
3001  } else if (const auto OD = dyn_cast<ObjCMethodDecl>(Signature)) {
3002  SignatureSourceRange = OD->getSourceRange();
3003  } else {
3004  return;
3005  }
3006  SourceLocation Start = SignatureSourceRange.getBegin();
3007  SourceLocation End = Body ? Body->getSourceRange().getBegin()
3008  : SignatureSourceRange.getEnd();
3009  unsigned StartLine = SM.getExpansionLineNumber(Start);
3010  unsigned EndLine = SM.getExpansionLineNumber(End);
3011 
3012  FileID FID = SM.getFileID(SM.getExpansionLoc(Start));
3013  for (unsigned Line = StartLine; Line <= EndLine; Line++)
3014  ExecutedLines->operator[](FID.getHashValue()).insert(Line);
3015 }
3016 
3017 static void populateExecutedLinesWithStmt(
3018  const Stmt *S, SourceManager &SM,
3019  std::unique_ptr<FilesToLineNumsMap> &ExecutedLines) {
3021  SourceLocation ExpansionLoc = SM.getExpansionLoc(Loc);
3022  FileID FID = SM.getFileID(ExpansionLoc);
3023  unsigned LineNo = SM.getExpansionLineNumber(ExpansionLoc);
3024  ExecutedLines->operator[](FID.getHashValue()).insert(LineNo);
3025 }
3026 
3027 /// \return all executed lines including function signatures on the path
3028 /// starting from \p N.
3029 static std::unique_ptr<FilesToLineNumsMap>
3031  auto ExecutedLines = llvm::make_unique<FilesToLineNumsMap>();
3032 
3033  while (N) {
3034  if (N->getFirstPred() == nullptr) {
3035  // First node: show signature of the entrance point.
3036  const Decl *D = N->getLocationContext()->getDecl();
3037  populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines);
3038  } else if (auto CE = N->getLocationAs<CallEnter>()) {
3039  // Inlined function: show signature.
3040  const Decl* D = CE->getCalleeContext()->getDecl();
3041  populateExecutedLinesWithFunctionSignature(D, SM, ExecutedLines);
3042  } else if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) {
3043  populateExecutedLinesWithStmt(S, SM, ExecutedLines);
3044 
3045  // Show extra context for some parent kinds.
3046  const Stmt *P = N->getParentMap().getParent(S);
3047 
3048  // The path exploration can die before the node with the associated
3049  // return statement is generated, but we do want to show the whole
3050  // return.
3051  if (const auto *RS = dyn_cast_or_null<ReturnStmt>(P)) {
3052  populateExecutedLinesWithStmt(RS, SM, ExecutedLines);
3053  P = N->getParentMap().getParent(RS);
3054  }
3055 
3056  if (P && (isa<SwitchCase>(P) || isa<LabelStmt>(P)))
3057  populateExecutedLinesWithStmt(P, SM, ExecutedLines);
3058  }
3059 
3060  N = N->getFirstPred();
3061  }
3062  return ExecutedLines;
3063 }
3064 
3065 std::unique_ptr<DiagnosticForConsumerMapTy>
3066 BugReporter::generateDiagnosticForConsumerMap(
3067  BugReport *report, ArrayRef<PathDiagnosticConsumer *> consumers,
3068  ArrayRef<BugReport *> bugReports) {
3069 
3070  if (!report->isPathSensitive()) {
3071  auto Out = llvm::make_unique<DiagnosticForConsumerMapTy>();
3072  for (auto *Consumer : consumers)
3073  (*Out)[Consumer] = generateEmptyDiagnosticForReport(report,
3074  getSourceManager());
3075  return Out;
3076  }
3077 
3078  // Generate the full path sensitive diagnostic, using the generation scheme
3079  // specified by the PathDiagnosticConsumer. Note that we have to generate
3080  // path diagnostics even for consumers which do not support paths, because
3081  // the BugReporterVisitors may mark this bug as a false positive.
3082  assert(!bugReports.empty());
3083  MaxBugClassSize.updateMax(bugReports.size());
3084  std::unique_ptr<DiagnosticForConsumerMapTy> Out =
3085  generatePathDiagnostics(consumers, bugReports);
3086 
3087  if (Out->empty())
3088  return Out;
3089 
3090  MaxValidBugClassSize.updateMax(bugReports.size());
3091 
3092  // Examine the report and see if the last piece is in a header. Reset the
3093  // report location to the last piece in the main source file.
3095  for (auto const &P : *Out)
3096  if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll)
3097  P.second->resetDiagnosticLocationToMainFile();
3098 
3099  return Out;
3100 }
3101 
3102 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3103  const CheckerBase *Checker,
3104  StringRef Name, StringRef Category,
3105  StringRef Str, PathDiagnosticLocation Loc,
3106  ArrayRef<SourceRange> Ranges) {
3107  EmitBasicReport(DeclWithIssue, Checker->getCheckName(), Name, Category, Str,
3108  Loc, Ranges);
3109 }
3110 
3111 void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3113  StringRef name, StringRef category,
3114  StringRef str, PathDiagnosticLocation Loc,
3115  ArrayRef<SourceRange> Ranges) {
3116  // 'BT' is owned by BugReporter.
3117  BugType *BT = getBugTypeForName(CheckName, name, category);
3118  auto R = llvm::make_unique<BugReport>(*BT, str, Loc);
3119  R->setDeclWithIssue(DeclWithIssue);
3120  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
3121  I != E; ++I)
3122  R->addRange(*I);
3123  emitReport(std::move(R));
3124 }
3125 
3126 BugType *BugReporter::getBugTypeForName(CheckName CheckName, StringRef name,
3127  StringRef category) {
3128  SmallString<136> fullDesc;
3129  llvm::raw_svector_ostream(fullDesc) << CheckName.getName() << ":" << name
3130  << ":" << category;
3131  BugType *&BT = StrBugTypes[fullDesc];
3132  if (!BT)
3133  BT = new BugType(CheckName, name, category);
3134  return BT;
3135 }
static void removeEdgesToDefaultInitializers(PathPieces &Pieces)
Remove edges in and out of C++ default initializer expressions.
bool isWrittenInSameFile(SourceLocation Loc1, SourceLocation Loc2) const
Returns true if the spelling locations for both SourceLocations are part of the same file buffer...
bool shouldPrunePath() const
Indicates whether or not any path pruning should take place when generating a PathDiagnostic from thi...
Definition: BugReporter.h:219
static DiagnosticBuilder Diag(DiagnosticsEngine *Diags, const LangOptions &Features, FullSourceLoc TokLoc, const char *TokBegin, const char *TokRangeBegin, const char *TokRangeEnd, unsigned DiagID)
Produce a diagnostic highlighting some portion of a literal.
static void removeRedundantMsgs(PathPieces &path)
An optimization pass over PathPieces that removes redundant diagnostics generated by both ConditionBR...
static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS)
static Optional< size_t > getLengthOnSingleLine(SourceManager &SM, SourceRange Range)
Returns the number of bytes in the given (character-based) SourceRange.
if(T->getSizeExpr()) TRY_TO(TraverseStmt(T -> getSizeExpr()))
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
static bool removeUnneededCalls(PathPieces &pieces, BugReport *R, LocationContextMap &LCM, bool IsInteresting=false)
Recursively scan through a path and prune out calls and macros pieces that aren&#39;t needed...
PathDiagnosticLocation getUniqueingLocation() const
Get the location on which the report should be uniqued.
Definition: BugReporter.h:310
bool isInteresting(SymbolRef sym)
PathDiagnosticLocation getLocation() const override
succ_iterator succ_begin()
Definition: CFG.h:751
virtual Stmt * getBody() const
getBody - If this Decl represents a declaration for a body of code, such as a function or method defi...
Definition: DeclBase.h:992
AnalyzerOptions & getAnalyzerOptions()
Definition: BugReporter.h:589
Stmt - This represents one statement.
Definition: Stmt.h:66
An instance of this object exists for each enum constant that is defined.
Definition: Decl.h:2761
Defines the SourceManager interface.
CheckName getCheckName() const
Definition: Checker.cpp:24
const CFGBlock * getSrc() const
Definition: ProgramPoint.h:485
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:604
StringRef getDescription() const
Definition: BugReporter.h:209
StringRef P
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
bool shouldPrunePaths()
Returns whether irrelevant parts of a bug report path should be pruned out of the final output...
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:123
void Profile(llvm::FoldingSetNodeID &ID) const
iterator begin()
Definition: CFG.h:703
A Range represents the closed range [from, to].
static void adjustCallLocations(PathPieces &Pieces, PathDiagnosticLocation *LastCallLocation=nullptr)
Recursively scan through a path and make sure that all call pieces have valid locations.
const ProgramStateRef & getState() const
static std::shared_ptr< PathDiagnosticCallPiece > construct(const ExplodedNode *N, const CallExitEnd &CE, const SourceManager &SM)
ArrayRef< ParmVarDecl * >::const_iterator param_const_iterator
Definition: Decl.h:2245
PathDiagnosticLocation getStartLocation() const
virtual PathDiagnosticLocation getLocation(const SourceManager &SM) const
Return the "definitive" location of the reported bug.
static PathDiagnosticLocation createEndBrace(const CompoundStmt *CS, const SourceManager &SM)
Create a location for the end of the compound statement.
unsigned succ_size() const
Definition: CFG.h:769
static bool optimizeEdges(PathPieces &path, SourceManager &SM, OptimizedCallsSet &OCS, LocationContextMap &LCM)
bool isConsumedExpr(Expr *E) const
Definition: ParentMap.cpp:160
static const Stmt * GetCurrentOrPreviousStmt(const ExplodedNode *N)
const Decl & getCodeDecl() const
static bool isConditionForTerminator(const Stmt *S, const Stmt *Cond)
Defines the Objective-C statement AST node classes.
static PathDiagnosticLocation createDeclEnd(const LocationContext *LC, const SourceManager &SM)
Constructs a location for the end of the enclosing declaration body.
Represents a parameter to a function.
Definition: Decl.h:1541
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
void clearVisitors()
Remove all visitors attached to this bug report.
Symbolic value.
Definition: SymExpr.h:30
PathDiagnostic - PathDiagnostic objects represent a single path-sensitive diagnostic.
void setStartLocation(const PathDiagnosticLocation &L)
void addRange(SourceRange R)
Add a range to a bug report.
Definition: BugReporter.h:328
LineState State
static std::unique_ptr< PathDiagnostic > generateEmptyDiagnosticForReport(BugReport *R, SourceManager &SM)
bool isValid() const
Returns whether or not this report should be considered valid.
Definition: BugReporter.h:238
succ_iterator succ_begin()
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: Stmt.cpp:280
static PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S, SourceManager &SMgr, const ParentMap &P, const LocationContext *LC, bool allowNestedContexts)
AnalysisDeclContext contains the context data for the function or method under analysis.
unsigned getHashValue() const
static void removeIdenticalEvents(PathPieces &path)
StringRef getName() const
Definition: BugType.h:49
static const char StrLoopBodyZero[]
std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy *> Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
Creates a trimmed version of the graph that only contains paths leading to the given nodes...
static std::unique_ptr< PathDiagnostic > generatePathDiagnosticForConsumer(PathDiagnosticConsumer::PathGenerationScheme ActiveScheme, PathDiagnosticBuilder &PDB, const ExplodedNode *ErrorNode, const VisitorsDiagnosticsTy &VisitorsDiagnostics)
This function is responsible for generating diagnostic pieces that are not provided by bug report vis...
succ_range succs()
Definition: CFG.h:761
void pushActivePath(PathPieces *p)
int Category
Definition: Format.cpp:1608
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
virtual bool supportsLogicalOpControlFlow() const
Optional< T > getLocationAs() const LLVM_LVALUE_FUNCTION
virtual llvm::iterator_range< ranges_iterator > getRanges()
Get the SourceRanges associated with the report.
StringRef getCategory() const
Definition: BugType.h:50
const Stmt * getStmt() const
llvm::DenseMap< const ExplodedNode *, std::vector< std::shared_ptr< PathDiagnosticPiece > >> VisitorsDiagnosticsTy
llvm::DenseMap< const PathPieces *, const LocationContext * > LocationContextMap
A map from PathDiagnosticPiece to the LocationContext of the inlined function call it represents...
virtual void FlushReports(BugReporter &BR)
const BugType & getBugType() const
Definition: BugReporter.h:192
void emitReport(std::unique_ptr< BugReport > R)
Add the given report to the set of reports tracked by BugReporter.
static void addEdgeToPath(PathPieces &path, PathDiagnosticLocation &PrevLoc, PathDiagnosticLocation NewLoc, const LocationContext *LC)
Adds a sanitized control-flow diagnostic edge to a path.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
static bool isJumpToFalseBranch(const BlockEdge *BE)
SourceLocation getExpansionLoc(SourceLocation Loc) const
Given a SourceLocation object Loc, return the expansion location referenced by the ID...
child_range children()
Definition: Stmt.cpp:229
const LocationContext * getLocationContext() const
Expr * IgnoreParenCasts() LLVM_READONLY
IgnoreParenCasts - Ignore parentheses and casts.
Definition: Expr.cpp:2544
const Decl * getDeclWithIssue() const
Return the canonical declaration, be it a method or class, where this issue semantically occurred...
static const Stmt * getStmtBeforeCond(ParentMap &PM, const Stmt *Term, const ExplodedNode *N)
ExplodedNode * getFirstPred()
static void reversePropagateIntererstingSymbols(BugReport &R, InterestingExprs &IE, const ProgramState *State, const Expr *Ex, const LocationContext *LCtx)
void addVisitor(std::unique_ptr< BugReporterVisitor > visitor)
Add custom or predefined bug report visitors to this report.
SVal getSVal(const Stmt *S, const LocationContext *LCtx) const
Returns the SVal bound to the statement &#39;S&#39; in the state&#39;s environment.
Definition: ProgramState.h:796
PathDiagnosticLocation getEndLocation() const
virtual const NoteList & getNotes()
Definition: BugReporter.h:287
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:127
NodeId Parent
Definition: ASTDiff.cpp:192
const ExplodedNode *const * const_succ_iterator
Const iterator for iterating over Stmt * arrays that contain only Expr *.
Definition: Stmt.h:359
const Stmt * getCallSite() const
StringRef getName() const
const void * getTag() const
Return the opaque tag (if any) on the PathDiagnosticPiece.
VisitorList::iterator visitor_iterator
Definition: BugReporter.h:90
void HandlePathDiagnostic(std::unique_ptr< PathDiagnostic > D)
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
Represents a point when we finish the call exit sequence (for inlined call).
Definition: ProgramPoint.h:662
bool isBodyAutosynthesizedFromModelFile() const
Checks if the body of the Decl is generated by the BodyFarm from a model file.
virtual const ExtraTextList & getExtraText()
Definition: BugReporter.h:298
STATISTIC(MaxBugClassSize, "The maximum number of bug reports in the same equivalence class")
ProgramState - This class encapsulates:
Definition: ProgramState.h:75
Expr - This represents one expression.
Definition: Expr.h:106
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:5441
SourceLocation End
pred_iterator pred_end()
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
visitor_iterator visitor_end()
Definition: BugReporter.h:351
const AnnotatedLine * Line
CFGBlock * getBlock(Stmt *S)
Returns the CFGBlock the specified Stmt* appears in.
Definition: CFGStmtMap.cpp:27
visitor_iterator visitor_begin()
Iterators through the custom diagnostic visitors.
Definition: BugReporter.h:350
bool isImplicit() const
isImplicit - Indicates whether the declaration was implicitly generated by the implementation.
Definition: DeclBase.h:560
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)
Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const
Get the lvalue for a base class object reference.
Definition: ProgramState.h:746
const Decl * getUniqueingDecl() const
Get the declaration containing the uniqueing location.
Definition: BugReporter.h:315
static const Stmt * getNextStmt(const ExplodedNode *N)
Retrieve the statement corresponding to the successor node.
void FlushReports()
Generate and flush diagnostics for all bug reports.
const CFGBlock * getDst() const
Definition: ProgramPoint.h:489
static void dropFunctionEntryEdge(PathPieces &Path, LocationContextMap &LCM, SourceManager &SM)
Drop the very first edge in a path, which should be a function entry edge.
bool isBodyAutosynthesized() const
Checks if the body of the Decl is generated by the BodyFarm.
SourceLocation getEnd() const
BugReporterContext(GRBugReporter &br, InterExplodedGraphMap &Backmap)
Definition: BugReporter.h:564
void markInteresting(SymbolRef sym)
static const Stmt * GetPreviousStmt(const ExplodedNode *N)
Definition: BugReporter.cpp:92
unsigned getExpansionLineNumber(SourceLocation Loc, bool *Invalid=nullptr) const
const SourceManager & SM
Definition: Format.cpp:1475
ParentMap & getParentMap() const
virtual bool hasBody() const
Returns true if this Decl represents a declaration for a body of code, such as a function or method d...
Definition: DeclBase.h:998
Only runs visitors, no output generated.
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:412
static const Stmt * getStmt(const ExplodedNode *N)
Given an exploded node, retrieve the statement that should be used for the diagnostic location...
unsigned getFileOffset(SourceLocation SpellingLoc) const
Returns the offset from the start of the file that the specified SourceLocation represents.
CFGTerminator getTerminator()
Definition: CFG.h:840
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)
llvm::MemoryBuffer * getBuffer(FileID FID, SourceLocation Loc, bool *Invalid=nullptr) const
Return the buffer for the specified FileID.
static void simplifySimpleBranches(PathPieces &pieces)
Move edges from a branch condition to a branch target when the condition is simple.
Encodes a location in the source.
Stmt * getLabel()
Definition: CFG.h:851
Stmt * getParentIgnoreParens(Stmt *) const
Definition: ParentMap.cpp:129
const MemRegion * getAsRegion() const
Definition: SVals.cpp:151
ExplodedGraph & getGraph()
getGraph - Get the exploded graph created by the analysis engine for the analyzed method or function...
static bool isIncrementOrInitInForLoop(const Stmt *S, const Stmt *FL)
void setCallee(const CallEnter &CE, const SourceManager &SM)
std::shared_ptr< PathDiagnosticControlFlowPiece > generateDiagForGotoOP(const Stmt *S, PathDiagnosticBuilder &PDB, PathDiagnosticLocation &Start)
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
std::shared_ptr< PathDiagnosticControlFlowPiece > generateDiagForSwitchOP(const ExplodedNode *N, const CFGBlock *Dst, const SourceManager &SM, const LocationContext *LC, PathDiagnosticBuilder &PDB, PathDiagnosticLocation &Start)
ParentMap & getParentMap() const
PathDiagnosticLocation getLocation() const override
static const Stmt * getEnclosingParent(const Stmt *S, const ParentMap &PM)
Used for plist output, used for "arrows" generation.
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...
ast_type_traits::DynTypedNode Node
An opaque identifier used by SourceManager which refers to a source file (MemoryBuffer) along with it...
std::unique_ptr< DiagnosticForConsumerMapTy > generatePathDiagnostics(ArrayRef< PathDiagnosticConsumer *> consumers, ArrayRef< BugReport *> &bugReports) override
bugReports A set of bug reports within a single equivalence class
ArrayRef< SourceRange > getRanges() const
Return the SourceRanges associated with this PathDiagnosticPiece.
Dataflow Directional Tag Classes.
static const char StrLoopCollectionEmpty[]
bool isValid() const
Return true if this is a valid SourceLocation object.
std::pair< PathDiagnosticCallPiece *, const ExplodedNode * > StackDiagPair
StmtClass getStmtClass() const
Definition: Stmt.h:391
static void updateStackPiecesWithMessage(PathDiagnosticPiece &P, StackDiagVector &CallStack)
StringRef getCheckName() const
Definition: BugType.h:51
static const Stmt * getTerminatorCondition(const CFGBlock *B)
A customized wrapper for CFGBlock::getTerminatorCondition() which returns the element for ObjCForColl...
static std::unique_ptr< FilesToLineNumsMap > findExecutedLines(SourceManager &SM, const ExplodedNode *N)
const Decl * getDecl() const
unsigned getExpansionLineNumber(bool *Invalid=nullptr) const
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
static bool isLoop(const Stmt *Term)
FileID getFileID(SourceLocation SpellingLoc) const
Return the FileID for a SourceLocation.
virtual PathGenerationScheme getGenerationScheme() const
succ_iterator succ_end()
const ExplodedNode * getErrorNode() const
Definition: BugReporter.h:207
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:180
virtual void Profile(llvm::FoldingSetNodeID &hash) const
Profile to identify equivalent bug reports for error report coalescing.
SVal getRawSVal(Loc LV, QualType T=QualType()) const
Returns the "raw" SVal bound to LV before any value simplfication.
Definition: ProgramState.h:815
const StackFrameContext * getStackFrame() const
StringRef getShortDescription(bool UseFallback=true) const
Definition: BugReporter.h:211
CharSourceRange getExpansionRange(SourceLocation Loc) const
Given a SourceLocation object, return the range of tokens covered by the expansion in the ultimate fi...
void generateMinimalDiagForBlockEdge(const ExplodedNode *N, BlockEdge BE, const SourceManager &SM, PathDiagnosticBuilder &PDB, PathDiagnostic &PD)
bool hasNoReturnElement() const
Definition: CFG.h:854
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:13790
llvm::ilist< BugReport >::iterator iterator
Definition: BugReporter.h:382
ProgramStateManager & getStateManager()
getStateManager - Return the state manager used by the analysis engine.
Used for HTML and text output.
static void CompactPathDiagnostic(PathPieces &path, const SourceManager &SM)
CompactPathDiagnostic - This function postprocesses a PathDiagnostic object and collapses PathDiagost...
Defines the clang::SourceLocation class and associated facilities.
PathPieces & getActivePath()
Return the path currently used by builders for constructing the PathDiagnostic.
bool shouldCrosscheckWithZ3()
Returns whether bug reports should be crosschecked with the Z3 constraint manager backend...
pred_iterator pred_begin()
static const Stmt * getStmtParent(const Stmt *S, const ParentMap &PM)
static PathDiagnosticLocation createEndOfPath(const ExplodedNode *N, const SourceManager &SM)
Create a location corresponding to the next valid ExplodedNode as end of path location.
void Register(BugType *BT)
Represents a top-level expression in a basic block.
Definition: CFG.h:56
GRBugReporter is used for generating path-sensitive reports.
Definition: BugReporter.h:513
static void removeContextCycles(PathPieces &Path, SourceManager &SM, ParentMap &PM)
Eliminate two-edge cycles created by addContextEdges().
const MemRegion * getBaseRegion() const
Definition: MemRegion.cpp:1126
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:268
A SourceLocation and its associated SourceManager.
static void generatePathDiagnosticsForNode(const ExplodedNode *N, PathDiagnostic &PD, PathDiagnosticLocation &PrevLoc, PathDiagnosticBuilder &PDB, LocationContextMap &LCM, StackDiagVector &CallStack, InterestingExprs &IE, bool AddPathEdges)
Generate diagnostics for the node N, and write it into PD.
bool isSuppressOnSink() const
isSuppressOnSink - Returns true if bug reports associated with this bug type should be suppressed if ...
Definition: BugType.h:66
const ExplodedNode *const * const_pred_iterator
std::shared_ptr< PathDiagnosticControlFlowPiece > generateDiagForBinaryOP(const ExplodedNode *N, const Stmt *T, const CFGBlock *Src, const CFGBlock *Dst, const SourceManager &SM, PathDiagnosticBuilder &PDB, const LocationContext *LC)
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.
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:152
This class provides an interface through which checkers can create individual bug reports...
Definition: BugReporter.h:76
iterator end()
Definition: CFG.h:704
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=None)
AnalysisDeclContext * getAnalysisDeclContext() const
bool shouldReportIssuesInMainSourceFile()
Returns whether or not the diagnostic report should be always reported in the main source file and no...
static const char StrEnteringLoop[]
SourceLocation getBegin() const
static const char StrLoopRangeEmpty[]
This class handles loading and caching of source files into memory.
SourceManager & getSourceManager()
Definition: BugReporter.h:585
void setDeclWithIssue(const Decl *declWithIssue)
Specifically set the Decl where an issue occurred.
Definition: BugReporter.h:261
bool isPathSensitive() const
True when the report has an execution path associated with it.
Definition: BugReporter.h:205
CFGBlock & getExit()
Definition: CFG.h:1095
static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term)