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