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