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