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 (llvm::find(SrcContexts, DstContext) != SrcContexts.end())
1373  break;
1374 
1375  // Update the subexpression node to point to the context edge.
1376  Piece->setStartLocation(DstContext);
1377 
1378  // Try to extend the previous edge if it's at the same level as the source
1379  // context.
1380  if (Prev != E) {
1381  auto *PrevPiece = dyn_cast<PathDiagnosticControlFlowPiece>(Prev->get());
1382 
1383  if (PrevPiece) {
1384  if (const Stmt *PrevSrc =
1385  PrevPiece->getStartLocation().getStmtOrNull()) {
1386  const Stmt *PrevSrcParent = getStmtParent(PrevSrc, PM);
1387  if (PrevSrcParent ==
1388  getStmtParent(DstContext.getStmtOrNull(), PM)) {
1389  PrevPiece->setEndLocation(DstContext);
1390  break;
1391  }
1392  }
1393  }
1394  }
1395 
1396  // Otherwise, split the current edge into a context edge and a
1397  // subexpression edge. Note that the context statement may itself have
1398  // context.
1399  auto P =
1400  std::make_shared<PathDiagnosticControlFlowPiece>(SrcLoc, DstContext);
1401  Piece = P.get();
1402  I = pieces.insert(I, std::move(P));
1403  }
1404  }
1405 }
1406 
1407 /// Move edges from a branch condition to a branch target
1408 /// when the condition is simple.
1409 ///
1410 /// This restructures some of the work of addContextEdges. That function
1411 /// creates edges this may destroy, but they work together to create a more
1412 /// aesthetically set of edges around branches. After the call to
1413 /// addContextEdges, we may have (1) an edge to the branch, (2) an edge from
1414 /// the branch to the branch condition, and (3) an edge from the branch
1415 /// condition to the branch target. We keep (1), but may wish to remove (2)
1416 /// and move the source of (3) to the branch if the branch condition is simple.
1417 static void simplifySimpleBranches(PathPieces &pieces) {
1418  for (PathPieces::iterator I = pieces.begin(), E = pieces.end(); I != E; ++I) {
1419  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1420 
1421  if (!PieceI)
1422  continue;
1423 
1424  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1425  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1426 
1427  if (!s1Start || !s1End)
1428  continue;
1429 
1430  PathPieces::iterator NextI = I; ++NextI;
1431  if (NextI == E)
1432  break;
1433 
1434  PathDiagnosticControlFlowPiece *PieceNextI = nullptr;
1435 
1436  while (true) {
1437  if (NextI == E)
1438  break;
1439 
1440  const auto *EV = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1441  if (EV) {
1442  StringRef S = EV->getString();
1443  if (S == StrEnteringLoop || S == StrLoopBodyZero ||
1445  ++NextI;
1446  continue;
1447  }
1448  break;
1449  }
1450 
1451  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1452  break;
1453  }
1454 
1455  if (!PieceNextI)
1456  continue;
1457 
1458  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1459  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1460 
1461  if (!s2Start || !s2End || s1End != s2Start)
1462  continue;
1463 
1464  // We only perform this transformation for specific branch kinds.
1465  // We don't want to do this for do..while, for example.
1466  if (!(isa<ForStmt>(s1Start) || isa<WhileStmt>(s1Start) ||
1467  isa<IfStmt>(s1Start) || isa<ObjCForCollectionStmt>(s1Start) ||
1468  isa<CXXForRangeStmt>(s1Start)))
1469  continue;
1470 
1471  // Is s1End the branch condition?
1472  if (!isConditionForTerminator(s1Start, s1End))
1473  continue;
1474 
1475  // Perform the hoisting by eliminating (2) and changing the start
1476  // location of (3).
1477  PieceNextI->setStartLocation(PieceI->getStartLocation());
1478  I = pieces.erase(I);
1479  }
1480 }
1481 
1482 /// Returns the number of bytes in the given (character-based) SourceRange.
1483 ///
1484 /// If the locations in the range are not on the same line, returns None.
1485 ///
1486 /// Note that this does not do a precise user-visible character or column count.
1488  SourceRange Range) {
1489  SourceRange ExpansionRange(SM.getExpansionLoc(Range.getBegin()),
1490  SM.getExpansionRange(Range.getEnd()).getEnd());
1491 
1492  FileID FID = SM.getFileID(ExpansionRange.getBegin());
1493  if (FID != SM.getFileID(ExpansionRange.getEnd()))
1494  return None;
1495 
1496  bool Invalid;
1497  const llvm::MemoryBuffer *Buffer = SM.getBuffer(FID, &Invalid);
1498  if (Invalid)
1499  return None;
1500 
1501  unsigned BeginOffset = SM.getFileOffset(ExpansionRange.getBegin());
1502  unsigned EndOffset = SM.getFileOffset(ExpansionRange.getEnd());
1503  StringRef Snippet = Buffer->getBuffer().slice(BeginOffset, EndOffset);
1504 
1505  // We're searching the raw bytes of the buffer here, which might include
1506  // escaped newlines and such. That's okay; we're trying to decide whether the
1507  // SourceRange is covering a large or small amount of space in the user's
1508  // editor.
1509  if (Snippet.find_first_of("\r\n") != StringRef::npos)
1510  return None;
1511 
1512  // This isn't Unicode-aware, but it doesn't need to be.
1513  return Snippet.size();
1514 }
1515 
1516 /// \sa getLengthOnSingleLine(SourceManager, SourceRange)
1518  const Stmt *S) {
1519  return getLengthOnSingleLine(SM, S->getSourceRange());
1520 }
1521 
1522 /// Eliminate two-edge cycles created by addContextEdges().
1523 ///
1524 /// Once all the context edges are in place, there are plenty of cases where
1525 /// there's a single edge from a top-level statement to a subexpression,
1526 /// followed by a single path note, and then a reverse edge to get back out to
1527 /// the top level. If the statement is simple enough, the subexpression edges
1528 /// just add noise and make it harder to understand what's going on.
1529 ///
1530 /// This function only removes edges in pairs, because removing only one edge
1531 /// might leave other edges dangling.
1532 ///
1533 /// This will not remove edges in more complicated situations:
1534 /// - if there is more than one "hop" leading to or from a subexpression.
1535 /// - if there is an inlined call between the edges instead of a single event.
1536 /// - if the whole statement is large enough that having subexpression arrows
1537 /// might be helpful.
1538 static void removeContextCycles(PathPieces &Path, SourceManager &SM) {
1539  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
1540  // Pattern match the current piece and its successor.
1541  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1542 
1543  if (!PieceI) {
1544  ++I;
1545  continue;
1546  }
1547 
1548  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1549  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1550 
1551  PathPieces::iterator NextI = I; ++NextI;
1552  if (NextI == E)
1553  break;
1554 
1555  const auto *PieceNextI =
1556  dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1557 
1558  if (!PieceNextI) {
1559  if (isa<PathDiagnosticEventPiece>(NextI->get())) {
1560  ++NextI;
1561  if (NextI == E)
1562  break;
1563  PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1564  }
1565 
1566  if (!PieceNextI) {
1567  ++I;
1568  continue;
1569  }
1570  }
1571 
1572  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1573  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1574 
1575  if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
1576  const size_t MAX_SHORT_LINE_LENGTH = 80;
1577  Optional<size_t> s1Length = getLengthOnSingleLine(SM, s1Start);
1578  if (s1Length && *s1Length <= MAX_SHORT_LINE_LENGTH) {
1579  Optional<size_t> s2Length = getLengthOnSingleLine(SM, s2Start);
1580  if (s2Length && *s2Length <= MAX_SHORT_LINE_LENGTH) {
1581  Path.erase(I);
1582  I = Path.erase(NextI);
1583  continue;
1584  }
1585  }
1586  }
1587 
1588  ++I;
1589  }
1590 }
1591 
1592 /// Return true if X is contained by Y.
1593 static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y) {
1594  while (X) {
1595  if (X == Y)
1596  return true;
1597  X = PM.getParent(X);
1598  }
1599  return false;
1600 }
1601 
1602 // Remove short edges on the same line less than 3 columns in difference.
1603 static void removePunyEdges(PathPieces &path, SourceManager &SM,
1604  ParentMap &PM) {
1605  bool erased = false;
1606 
1607  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
1608  erased ? I : ++I) {
1609  erased = false;
1610 
1611  const auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1612 
1613  if (!PieceI)
1614  continue;
1615 
1616  const Stmt *start = PieceI->getStartLocation().getStmtOrNull();
1617  const Stmt *end = PieceI->getEndLocation().getStmtOrNull();
1618 
1619  if (!start || !end)
1620  continue;
1621 
1622  const Stmt *endParent = PM.getParent(end);
1623  if (!endParent)
1624  continue;
1625 
1626  if (isConditionForTerminator(end, endParent))
1627  continue;
1628 
1629  SourceLocation FirstLoc = start->getBeginLoc();
1630  SourceLocation SecondLoc = end->getBeginLoc();
1631 
1632  if (!SM.isWrittenInSameFile(FirstLoc, SecondLoc))
1633  continue;
1634  if (SM.isBeforeInTranslationUnit(SecondLoc, FirstLoc))
1635  std::swap(SecondLoc, FirstLoc);
1636 
1637  SourceRange EdgeRange(FirstLoc, SecondLoc);
1638  Optional<size_t> ByteWidth = getLengthOnSingleLine(SM, EdgeRange);
1639 
1640  // If the statements are on different lines, continue.
1641  if (!ByteWidth)
1642  continue;
1643 
1644  const size_t MAX_PUNY_EDGE_LENGTH = 2;
1645  if (*ByteWidth <= MAX_PUNY_EDGE_LENGTH) {
1646  // FIXME: There are enough /bytes/ between the endpoints of the edge, but
1647  // there might not be enough /columns/. A proper user-visible column count
1648  // is probably too expensive, though.
1649  I = path.erase(I);
1650  erased = true;
1651  continue;
1652  }
1653  }
1654 }
1655 
1656 static void removeIdenticalEvents(PathPieces &path) {
1657  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
1658  const auto *PieceI = dyn_cast<PathDiagnosticEventPiece>(I->get());
1659 
1660  if (!PieceI)
1661  continue;
1662 
1663  PathPieces::iterator NextI = I; ++NextI;
1664  if (NextI == E)
1665  return;
1666 
1667  const auto *PieceNextI = dyn_cast<PathDiagnosticEventPiece>(NextI->get());
1668 
1669  if (!PieceNextI)
1670  continue;
1671 
1672  // Erase the second piece if it has the same exact message text.
1673  if (PieceI->getString() == PieceNextI->getString()) {
1674  path.erase(NextI);
1675  }
1676  }
1677 }
1678 
1679 static bool optimizeEdges(PathPieces &path, SourceManager &SM,
1680  OptimizedCallsSet &OCS,
1681  LocationContextMap &LCM) {
1682  bool hasChanges = false;
1683  const LocationContext *LC = LCM[&path];
1684  assert(LC);
1685  ParentMap &PM = LC->getParentMap();
1686 
1687  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
1688  // Optimize subpaths.
1689  if (auto *CallI = dyn_cast<PathDiagnosticCallPiece>(I->get())) {
1690  // Record the fact that a call has been optimized so we only do the
1691  // effort once.
1692  if (!OCS.count(CallI)) {
1693  while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
1694  OCS.insert(CallI);
1695  }
1696  ++I;
1697  continue;
1698  }
1699 
1700  // Pattern match the current piece and its successor.
1701  auto *PieceI = dyn_cast<PathDiagnosticControlFlowPiece>(I->get());
1702 
1703  if (!PieceI) {
1704  ++I;
1705  continue;
1706  }
1707 
1708  const Stmt *s1Start = PieceI->getStartLocation().getStmtOrNull();
1709  const Stmt *s1End = PieceI->getEndLocation().getStmtOrNull();
1710  const Stmt *level1 = getStmtParent(s1Start, PM);
1711  const Stmt *level2 = getStmtParent(s1End, PM);
1712 
1713  PathPieces::iterator NextI = I; ++NextI;
1714  if (NextI == E)
1715  break;
1716 
1717  const auto *PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(NextI->get());
1718 
1719  if (!PieceNextI) {
1720  ++I;
1721  continue;
1722  }
1723 
1724  const Stmt *s2Start = PieceNextI->getStartLocation().getStmtOrNull();
1725  const Stmt *s2End = PieceNextI->getEndLocation().getStmtOrNull();
1726  const Stmt *level3 = getStmtParent(s2Start, PM);
1727  const Stmt *level4 = getStmtParent(s2End, PM);
1728 
1729  // Rule I.
1730  //
1731  // If we have two consecutive control edges whose end/begin locations
1732  // are at the same level (e.g. statements or top-level expressions within
1733  // a compound statement, or siblings share a single ancestor expression),
1734  // then merge them if they have no interesting intermediate event.
1735  //
1736  // For example:
1737  //
1738  // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
1739  // parent is '1'. Here 'x.y.z' represents the hierarchy of statements.
1740  //
1741  // NOTE: this will be limited later in cases where we add barriers
1742  // to prevent this optimization.
1743  if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
1744  PieceI->setEndLocation(PieceNextI->getEndLocation());
1745  path.erase(NextI);
1746  hasChanges = true;
1747  continue;
1748  }
1749 
1750  // Rule II.
1751  //
1752  // Eliminate edges between subexpressions and parent expressions
1753  // when the subexpression is consumed.
1754  //
1755  // NOTE: this will be limited later in cases where we add barriers
1756  // to prevent this optimization.
1757  if (s1End && s1End == s2Start && level2) {
1758  bool removeEdge = false;
1759  // Remove edges into the increment or initialization of a
1760  // loop that have no interleaving event. This means that
1761  // they aren't interesting.
1762  if (isIncrementOrInitInForLoop(s1End, level2))
1763  removeEdge = true;
1764  // Next only consider edges that are not anchored on
1765  // the condition of a terminator. This are intermediate edges
1766  // that we might want to trim.
1767  else if (!isConditionForTerminator(level2, s1End)) {
1768  // Trim edges on expressions that are consumed by
1769  // the parent expression.
1770  if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
1771  removeEdge = true;
1772  }
1773  // Trim edges where a lexical containment doesn't exist.
1774  // For example:
1775  //
1776  // X -> Y -> Z
1777  //
1778  // If 'Z' lexically contains Y (it is an ancestor) and
1779  // 'X' does not lexically contain Y (it is a descendant OR
1780  // it has no lexical relationship at all) then trim.
1781  //
1782  // This can eliminate edges where we dive into a subexpression
1783  // and then pop back out, etc.
1784  else if (s1Start && s2End &&
1785  lexicalContains(PM, s2Start, s2End) &&
1786  !lexicalContains(PM, s1End, s1Start)) {
1787  removeEdge = true;
1788  }
1789  // Trim edges from a subexpression back to the top level if the
1790  // subexpression is on a different line.
1791  //
1792  // A.1 -> A -> B
1793  // becomes
1794  // A.1 -> B
1795  //
1796  // These edges just look ugly and don't usually add anything.
1797  else if (s1Start && s2End &&
1798  lexicalContains(PM, s1Start, s1End)) {
1799  SourceRange EdgeRange(PieceI->getEndLocation().asLocation(),
1800  PieceI->getStartLocation().asLocation());
1801  if (!getLengthOnSingleLine(SM, EdgeRange).hasValue())
1802  removeEdge = true;
1803  }
1804  }
1805 
1806  if (removeEdge) {
1807  PieceI->setEndLocation(PieceNextI->getEndLocation());
1808  path.erase(NextI);
1809  hasChanges = true;
1810  continue;
1811  }
1812  }
1813 
1814  // Optimize edges for ObjC fast-enumeration loops.
1815  //
1816  // (X -> collection) -> (collection -> element)
1817  //
1818  // becomes:
1819  //
1820  // (X -> element)
1821  if (s1End == s2Start) {
1822  const auto *FS = dyn_cast_or_null<ObjCForCollectionStmt>(level3);
1823  if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
1824  s2End == FS->getElement()) {
1825  PieceI->setEndLocation(PieceNextI->getEndLocation());
1826  path.erase(NextI);
1827  hasChanges = true;
1828  continue;
1829  }
1830  }
1831 
1832  // No changes at this index? Move to the next one.
1833  ++I;
1834  }
1835 
1836  if (!hasChanges) {
1837  // Adjust edges into subexpressions to make them more uniform
1838  // and aesthetically pleasing.
1839  addContextEdges(path, SM, PM, LC);
1840  // Remove "cyclical" edges that include one or more context edges.
1841  removeContextCycles(path, SM);
1842  // Hoist edges originating from branch conditions to branches
1843  // for simple branches.
1844  simplifySimpleBranches(path);
1845  // Remove any puny edges left over after primary optimization pass.
1846  removePunyEdges(path, SM, PM);
1847  // Remove identical events.
1848  removeIdenticalEvents(path);
1849  }
1850 
1851  return hasChanges;
1852 }
1853 
1854 /// Drop the very first edge in a path, which should be a function entry edge.
1855 ///
1856 /// If the first edge is not a function entry edge (say, because the first
1857 /// statement had an invalid source location), this function does nothing.
1858 // FIXME: We should just generate invalid edges anyway and have the optimizer
1859 // deal with them.
1860 static void dropFunctionEntryEdge(PathPieces &Path, LocationContextMap &LCM,
1861  SourceManager &SM) {
1862  const auto *FirstEdge =
1863  dyn_cast<PathDiagnosticControlFlowPiece>(Path.front().get());
1864  if (!FirstEdge)
1865  return;
1866 
1867  const Decl *D = LCM[&Path]->getDecl();
1868  PathDiagnosticLocation EntryLoc = PathDiagnosticLocation::createBegin(D, SM);
1869  if (FirstEdge->getStartLocation() != EntryLoc)
1870  return;
1871 
1872  Path.pop_front();
1873 }
1874 
1875 using VisitorsDiagnosticsTy = llvm::DenseMap<const ExplodedNode *,
1876  std::vector<std::shared_ptr<PathDiagnosticPiece>>>;
1877 
1878 /// Populate executes lines with lines containing at least one diagnostics.
1880  PathDiagnostic &PD) {
1881 
1882  PathPieces path = PD.path.flatten(/*ShouldFlattenMacros=*/true);
1883  FilesToLineNumsMap &ExecutedLines = PD.getExecutedLines();
1884 
1885  for (const auto &P : path) {
1886  FullSourceLoc Loc = P->getLocation().asLocation().getExpansionLoc();
1887  FileID FID = Loc.getFileID();
1888  unsigned LineNo = Loc.getLineNumber();
1889  assert(FID.isValid());
1890  ExecutedLines[FID].insert(LineNo);
1891  }
1892 }
1893 
1894 /// This function is responsible for generating diagnostic pieces that are
1895 /// *not* provided by bug report visitors.
1896 /// These diagnostics may differ depending on the consumer's settings,
1897 /// and are therefore constructed separately for each consumer.
1898 ///
1899 /// There are two path diagnostics generation modes: with adding edges (used
1900 /// for plists) and without (used for HTML and text).
1901 /// When edges are added (\p ActiveScheme is Extensive),
1902 /// the path is modified to insert artificially generated
1903 /// edges.
1904 /// Otherwise, more detailed diagnostics is emitted for block edges, explaining
1905 /// the transitions in words.
1906 static std::unique_ptr<PathDiagnostic> generatePathDiagnosticForConsumer(
1908  PathDiagnosticBuilder &PDB,
1909  const ExplodedNode *ErrorNode,
1910  const VisitorsDiagnosticsTy &VisitorsDiagnostics) {
1911 
1912  bool GenerateDiagnostics = (ActiveScheme != PathDiagnosticConsumer::None);
1913  bool AddPathEdges = (ActiveScheme == PathDiagnosticConsumer::Extensive);
1914  SourceManager &SM = PDB.getSourceManager();
1915  BugReport *R = PDB.getBugReport();
1916  AnalyzerOptions &Opts = PDB.getBugReporter().getAnalyzerOptions();
1917  StackDiagVector CallStack;
1918  InterestingExprs IE;
1919  LocationContextMap LCM;
1920  std::unique_ptr<PathDiagnostic> PD = generateEmptyDiagnosticForReport(R, SM);
1921 
1922  if (GenerateDiagnostics) {
1923  auto EndNotes = VisitorsDiagnostics.find(ErrorNode);
1924  std::shared_ptr<PathDiagnosticPiece> LastPiece;
1925  if (EndNotes != VisitorsDiagnostics.end()) {
1926  assert(!EndNotes->second.empty());
1927  LastPiece = EndNotes->second[0];
1928  } else {
1929  LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, ErrorNode, *R);
1930  }
1931  PD->setEndOfPath(LastPiece);
1932  }
1933 
1934  PathDiagnosticLocation PrevLoc = PD->getLocation();
1935  const ExplodedNode *NextNode = ErrorNode->getFirstPred();
1936  while (NextNode) {
1937  if (GenerateDiagnostics)
1939  NextNode, *PD, PrevLoc, PDB, LCM, CallStack, IE, AddPathEdges);
1940 
1941  auto VisitorNotes = VisitorsDiagnostics.find(NextNode);
1942  NextNode = NextNode->getFirstPred();
1943  if (!GenerateDiagnostics || VisitorNotes == VisitorsDiagnostics.end())
1944  continue;
1945 
1946  // This is a workaround due to inability to put shared PathDiagnosticPiece
1947  // into a FoldingSet.
1948  std::set<llvm::FoldingSetNodeID> DeduplicationSet;
1949 
1950  // Add pieces from custom visitors.
1951  for (const auto &Note : VisitorNotes->second) {
1952  llvm::FoldingSetNodeID ID;
1953  Note->Profile(ID);
1954  auto P = DeduplicationSet.insert(ID);
1955  if (!P.second)
1956  continue;
1957 
1958  if (AddPathEdges)
1959  addEdgeToPath(PD->getActivePath(), PrevLoc, Note->getLocation());
1960  updateStackPiecesWithMessage(*Note, CallStack);
1961  PD->getActivePath().push_front(Note);
1962  }
1963  }
1964 
1965  if (AddPathEdges) {
1966  // Add an edge to the start of the function.
1967  // We'll prune it out later, but it helps make diagnostics more uniform.
1968  const StackFrameContext *CalleeLC = PDB.LC->getStackFrame();
1969  const Decl *D = CalleeLC->getDecl();
1970  addEdgeToPath(PD->getActivePath(), PrevLoc,
1972  }
1973 
1974 
1975  // Finally, prune the diagnostic path of uninteresting stuff.
1976  if (!PD->path.empty()) {
1977  if (R->shouldPrunePath() && Opts.ShouldPrunePaths) {
1978  bool stillHasNotes =
1979  removeUnneededCalls(PD->getMutablePieces(), R, LCM);
1980  assert(stillHasNotes);
1981  (void)stillHasNotes;
1982  }
1983 
1984  // Redirect all call pieces to have valid locations.
1985  adjustCallLocations(PD->getMutablePieces());
1986  removePiecesWithInvalidLocations(PD->getMutablePieces());
1987 
1988  if (AddPathEdges) {
1989 
1990  // Reduce the number of edges from a very conservative set
1991  // to an aesthetically pleasing subset that conveys the
1992  // necessary information.
1993  OptimizedCallsSet OCS;
1994  while (optimizeEdges(PD->getMutablePieces(), SM, OCS, LCM)) {}
1995 
1996  // Drop the very first function-entry edge. It's not really necessary
1997  // for top-level functions.
1998  dropFunctionEntryEdge(PD->getMutablePieces(), LCM, SM);
1999  }
2000 
2001  // Remove messages that are basically the same, and edges that may not
2002  // make sense.
2003  // We have to do this after edge optimization in the Extensive mode.
2004  removeRedundantMsgs(PD->getMutablePieces());
2005  removeEdgesToDefaultInitializers(PD->getMutablePieces());
2006  }
2007 
2008  if (GenerateDiagnostics && Opts.ShouldDisplayMacroExpansions)
2009  CompactMacroExpandedPieces(PD->getMutablePieces(), SM);
2010 
2011  return PD;
2012 }
2013 
2014 
2015 //===----------------------------------------------------------------------===//
2016 // Methods for BugType and subclasses.
2017 //===----------------------------------------------------------------------===//
2018 
2019 void BugType::anchor() {}
2020 
2021 void BuiltinBug::anchor() {}
2022 
2023 //===----------------------------------------------------------------------===//
2024 // Methods for BugReport and subclasses.
2025 //===----------------------------------------------------------------------===//
2026 
2027 void BugReport::NodeResolver::anchor() {}
2028 
2029 void BugReport::addVisitor(std::unique_ptr<BugReporterVisitor> visitor) {
2030  if (!visitor)
2031  return;
2032 
2033  llvm::FoldingSetNodeID ID;
2034  visitor->Profile(ID);
2035 
2036  void *InsertPos = nullptr;
2037  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2038  return;
2039  }
2040 
2041  Callbacks.push_back(std::move(visitor));
2042 }
2043 
2045  Callbacks.clear();
2046 }
2047 
2049  while (!interestingSymbols.empty()) {
2050  popInterestingSymbolsAndRegions();
2051  }
2052 }
2053 
2055  if (DeclWithIssue)
2056  return DeclWithIssue;
2057 
2058  const ExplodedNode *N = getErrorNode();
2059  if (!N)
2060  return nullptr;
2061 
2062  const LocationContext *LC = N->getLocationContext();
2063  return LC->getStackFrame()->getDecl();
2064 }
2065 
2066 void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2067  hash.AddPointer(&BT);
2068  hash.AddString(Description);
2069  PathDiagnosticLocation UL = getUniqueingLocation();
2070  if (UL.isValid()) {
2071  UL.Profile(hash);
2072  } else if (Location.isValid()) {
2073  Location.Profile(hash);
2074  } else {
2075  assert(ErrorNode);
2076  hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2077  }
2078 
2079  for (SourceRange range : Ranges) {
2080  if (!range.isValid())
2081  continue;
2082  hash.AddInteger(range.getBegin().getRawEncoding());
2083  hash.AddInteger(range.getEnd().getRawEncoding());
2084  }
2085 }
2086 
2088  if (!sym)
2089  return;
2090 
2091  getInterestingSymbols().insert(sym);
2092 
2093  if (const auto *meta = dyn_cast<SymbolMetadata>(sym))
2094  getInterestingRegions().insert(meta->getRegion());
2095 }
2096 
2098  if (!R)
2099  return;
2100 
2101  R = R->getBaseRegion();
2102  getInterestingRegions().insert(R);
2103 
2104  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2105  getInterestingSymbols().insert(SR->getSymbol());
2106 }
2107 
2109  markInteresting(V.getAsRegion());
2110  markInteresting(V.getAsSymbol());
2111 }
2112 
2114  if (!LC)
2115  return;
2116  InterestingLocationContexts.insert(LC);
2117 }
2118 
2120  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2121 }
2122 
2124  if (!sym)
2125  return false;
2126  // We don't currently consider metadata symbols to be interesting
2127  // even if we know their region is interesting. Is that correct behavior?
2128  return getInterestingSymbols().count(sym);
2129 }
2130 
2132  if (!R)
2133  return false;
2134  R = R->getBaseRegion();
2135  bool b = getInterestingRegions().count(R);
2136  if (b)
2137  return true;
2138  if (const auto *SR = dyn_cast<SymbolicRegion>(R))
2139  return getInterestingSymbols().count(SR->getSymbol());
2140  return false;
2141 }
2142 
2144  if (!LC)
2145  return false;
2146  return InterestingLocationContexts.count(LC);
2147 }
2148 
2149 void BugReport::lazyInitializeInterestingSets() {
2150  if (interestingSymbols.empty()) {
2151  interestingSymbols.push_back(new Symbols());
2152  interestingRegions.push_back(new Regions());
2153  }
2154 }
2155 
2156 BugReport::Symbols &BugReport::getInterestingSymbols() {
2157  lazyInitializeInterestingSets();
2158  return *interestingSymbols.back();
2159 }
2160 
2161 BugReport::Regions &BugReport::getInterestingRegions() {
2162  lazyInitializeInterestingSets();
2163  return *interestingRegions.back();
2164 }
2165 
2166 void BugReport::pushInterestingSymbolsAndRegions() {
2167  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2168  interestingRegions.push_back(new Regions(getInterestingRegions()));
2169 }
2170 
2171 void BugReport::popInterestingSymbolsAndRegions() {
2172  delete interestingSymbols.pop_back_val();
2173  delete interestingRegions.pop_back_val();
2174 }
2175 
2176 const Stmt *BugReport::getStmt() const {
2177  if (!ErrorNode)
2178  return nullptr;
2179 
2180  ProgramPoint ProgP = ErrorNode->getLocation();
2181  const Stmt *S = nullptr;
2182 
2183  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2184  CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2185  if (BE->getBlock() == &Exit)
2186  S = GetPreviousStmt(ErrorNode);
2187  }
2188  if (!S)
2189  S = PathDiagnosticLocation::getStmt(ErrorNode);
2190 
2191  return S;
2192 }
2193 
2194 llvm::iterator_range<BugReport::ranges_iterator> BugReport::getRanges() {
2195  // If no custom ranges, add the range of the statement corresponding to
2196  // the error node.
2197  if (Ranges.empty()) {
2198  if (const auto *E = dyn_cast_or_null<Expr>(getStmt()))
2199  addRange(E->getSourceRange());
2200  else
2201  return llvm::make_range(ranges_iterator(), ranges_iterator());
2202  }
2203 
2204  // User-specified absence of range info.
2205  if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2206  return llvm::make_range(ranges_iterator(), ranges_iterator());
2207 
2208  return llvm::make_range(Ranges.begin(), Ranges.end());
2209 }
2210 
2212  if (ErrorNode) {
2213  assert(!Location.isValid() &&
2214  "Either Location or ErrorNode should be specified but not both.");
2215  return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2216  }
2217 
2218  assert(Location.isValid());
2219  return Location;
2220 }
2221 
2222 //===----------------------------------------------------------------------===//
2223 // Methods for BugReporter and subclasses.
2224 //===----------------------------------------------------------------------===//
2225 
2227 
2228 GRBugReporter::~GRBugReporter() = default;
2229 
2231 
2232 ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2233 
2235 GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2236 
2238  FlushReports();
2239 
2240  // Free the bug reports we are tracking.
2241  for (const auto I : EQClassesVector)
2242  delete I;
2243 }
2244 
2246  if (BugTypes.isEmpty())
2247  return;
2248 
2249  // We need to flush reports in deterministic order to ensure the order
2250  // of the reports is consistent between runs.
2251  for (const auto EQ : EQClassesVector)
2252  FlushReport(*EQ);
2253 
2254  // BugReporter owns and deletes only BugTypes created implicitly through
2255  // EmitBasicReport.
2256  // FIXME: There are leaks from checkers that assume that the BugTypes they
2257  // create will be destroyed by the BugReporter.
2258  llvm::DeleteContainerSeconds(StrBugTypes);
2259 
2260  // Remove all references to the BugType objects.
2261  BugTypes = F.getEmptySet();
2262 }
2263 
2264 //===----------------------------------------------------------------------===//
2265 // PathDiagnostics generation.
2266 //===----------------------------------------------------------------------===//
2267 
2268 namespace {
2269 
2270 /// A wrapper around a report graph, which contains only a single path, and its
2271 /// node maps.
2272 class ReportGraph {
2273 public:
2274  InterExplodedGraphMap BackMap;
2275  std::unique_ptr<ExplodedGraph> Graph;
2276  const ExplodedNode *ErrorNode;
2277  size_t Index;
2278 };
2279 
2280 /// A wrapper around a trimmed graph and its node maps.
2281 class TrimmedGraph {
2282  InterExplodedGraphMap InverseMap;
2283 
2284  using PriorityMapTy = llvm::DenseMap<const ExplodedNode *, unsigned>;
2285 
2286  PriorityMapTy PriorityMap;
2287 
2288  using NodeIndexPair = std::pair<const ExplodedNode *, size_t>;
2289 
2290  SmallVector<NodeIndexPair, 32> ReportNodes;
2291 
2292  std::unique_ptr<ExplodedGraph> G;
2293 
2294  /// A helper class for sorting ExplodedNodes by priority.
2295  template <bool Descending>
2296  class PriorityCompare {
2297  const PriorityMapTy &PriorityMap;
2298 
2299  public:
2300  PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2301 
2302  bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2303  PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2304  PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2305  PriorityMapTy::const_iterator E = PriorityMap.end();
2306 
2307  if (LI == E)
2308  return Descending;
2309  if (RI == E)
2310  return !Descending;
2311 
2312  return Descending ? LI->second > RI->second
2313  : LI->second < RI->second;
2314  }
2315 
2316  bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2317  return (*this)(LHS.first, RHS.first);
2318  }
2319  };
2320 
2321 public:
2322  TrimmedGraph(const ExplodedGraph *OriginalGraph,
2324 
2325  bool popNextReportGraph(ReportGraph &GraphWrapper);
2326 };
2327 
2328 } // namespace
2329 
2330 TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2332  // The trimmed graph is created in the body of the constructor to ensure
2333  // that the DenseMaps have been initialized already.
2334  InterExplodedGraphMap ForwardMap;
2335  G = OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap);
2336 
2337  // Find the (first) error node in the trimmed graph. We just need to consult
2338  // the node map which maps from nodes in the original graph to nodes
2339  // in the new graph.
2340  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2341 
2342  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2343  if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2344  ReportNodes.push_back(std::make_pair(NewNode, i));
2345  RemainingNodes.insert(NewNode);
2346  }
2347  }
2348 
2349  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2350 
2351  // Perform a forward BFS to find all the shortest paths.
2352  std::queue<const ExplodedNode *> WS;
2353 
2354  assert(G->num_roots() == 1);
2355  WS.push(*G->roots_begin());
2356  unsigned Priority = 0;
2357 
2358  while (!WS.empty()) {
2359  const ExplodedNode *Node = WS.front();
2360  WS.pop();
2361 
2362  PriorityMapTy::iterator PriorityEntry;
2363  bool IsNew;
2364  std::tie(PriorityEntry, IsNew) =
2365  PriorityMap.insert(std::make_pair(Node, Priority));
2366  ++Priority;
2367 
2368  if (!IsNew) {
2369  assert(PriorityEntry->second <= Priority);
2370  continue;
2371  }
2372 
2373  if (RemainingNodes.erase(Node))
2374  if (RemainingNodes.empty())
2375  break;
2376 
2378  E = Node->succ_end();
2379  I != E; ++I)
2380  WS.push(*I);
2381  }
2382 
2383  // Sort the error paths from longest to shortest.
2384  llvm::sort(ReportNodes, PriorityCompare<true>(PriorityMap));
2385 }
2386 
2387 bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2388  if (ReportNodes.empty())
2389  return false;
2390 
2391  const ExplodedNode *OrigN;
2392  std::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2393  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2394  "error node not accessible from root");
2395 
2396  // Create a new graph with a single path. This is the graph
2397  // that will be returned to the caller.
2398  auto GNew = llvm::make_unique<ExplodedGraph>();
2399  GraphWrapper.BackMap.clear();
2400 
2401  // Now walk from the error node up the BFS path, always taking the
2402  // predeccessor with the lowest number.
2403  ExplodedNode *Succ = nullptr;
2404  while (true) {
2405  // Create the equivalent node in the new graph with the same state
2406  // and location.
2407  ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
2408  OrigN->isSink());
2409 
2410  // Store the mapping to the original node.
2411  InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2412  assert(IMitr != InverseMap.end() && "No mapping to original node.");
2413  GraphWrapper.BackMap[NewN] = IMitr->second;
2414 
2415  // Link up the new node with the previous node.
2416  if (Succ)
2417  Succ->addPredecessor(NewN, *GNew);
2418  else
2419  GraphWrapper.ErrorNode = NewN;
2420 
2421  Succ = NewN;
2422 
2423  // Are we at the final node?
2424  if (OrigN->pred_empty()) {
2425  GNew->addRoot(NewN);
2426  break;
2427  }
2428 
2429  // Find the next predeccessor node. We choose the node that is marked
2430  // with the lowest BFS number.
2431  OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2432  PriorityCompare<false>(PriorityMap));
2433  }
2434 
2435  GraphWrapper.Graph = std::move(GNew);
2436 
2437  return true;
2438 }
2439 
2440 /// CompactMacroExpandedPieces - This function postprocesses a PathDiagnostic
2441 /// object and collapses PathDiagosticPieces that are expanded by macros.
2442 static void CompactMacroExpandedPieces(PathPieces &path,
2443  const SourceManager& SM) {
2444  using MacroStackTy =
2445  std::vector<
2446  std::pair<std::shared_ptr<PathDiagnosticMacroPiece>, SourceLocation>>;
2447 
2448  using PiecesTy = std::vector<std::shared_ptr<PathDiagnosticPiece>>;
2449 
2450  MacroStackTy MacroStack;
2451  PiecesTy Pieces;
2452 
2453  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2454  I != E; ++I) {
2455  const auto &piece = *I;
2456 
2457  // Recursively compact calls.
2458  if (auto *call = dyn_cast<PathDiagnosticCallPiece>(&*piece)) {
2459  CompactMacroExpandedPieces(call->path, SM);
2460  }
2461 
2462  // Get the location of the PathDiagnosticPiece.
2463  const FullSourceLoc Loc = piece->getLocation().asLocation();
2464 
2465  // Determine the instantiation location, which is the location we group
2466  // related PathDiagnosticPieces.
2467  SourceLocation InstantiationLoc = Loc.isMacroID() ?
2468  SM.getExpansionLoc(Loc) :
2469  SourceLocation();
2470 
2471  if (Loc.isFileID()) {
2472  MacroStack.clear();
2473  Pieces.push_back(piece);
2474  continue;
2475  }
2476 
2477  assert(Loc.isMacroID());
2478 
2479  // Is the PathDiagnosticPiece within the same macro group?
2480  if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
2481  MacroStack.back().first->subPieces.push_back(piece);
2482  continue;
2483  }
2484 
2485  // We aren't in the same group. Are we descending into a new macro
2486  // or are part of an old one?
2487  std::shared_ptr<PathDiagnosticMacroPiece> MacroGroup;
2488 
2489  SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2490  SM.getExpansionLoc(Loc) :
2491  SourceLocation();
2492 
2493  // Walk the entire macro stack.
2494  while (!MacroStack.empty()) {
2495  if (InstantiationLoc == MacroStack.back().second) {
2496  MacroGroup = MacroStack.back().first;
2497  break;
2498  }
2499 
2500  if (ParentInstantiationLoc == MacroStack.back().second) {
2501  MacroGroup = MacroStack.back().first;
2502  break;
2503  }
2504 
2505  MacroStack.pop_back();
2506  }
2507 
2508  if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
2509  // Create a new macro group and add it to the stack.
2510  auto NewGroup = std::make_shared<PathDiagnosticMacroPiece>(
2511  PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2512 
2513  if (MacroGroup)
2514  MacroGroup->subPieces.push_back(NewGroup);
2515  else {
2516  assert(InstantiationLoc.isFileID());
2517  Pieces.push_back(NewGroup);
2518  }
2519 
2520  MacroGroup = NewGroup;
2521  MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2522  }
2523 
2524  // Finally, add the PathDiagnosticPiece to the group.
2525  MacroGroup->subPieces.push_back(piece);
2526  }
2527 
2528  // Now take the pieces and construct a new PathDiagnostic.
2529  path.clear();
2530 
2531  path.insert(path.end(), Pieces.begin(), Pieces.end());
2532 }
2533 
2534 /// Generate notes from all visitors.
2535 /// Notes associated with {@code ErrorNode} are generated using
2536 /// {@code getEndPath}, and the rest are generated with {@code VisitNode}.
2537 static std::unique_ptr<VisitorsDiagnosticsTy>
2538 generateVisitorsDiagnostics(BugReport *R, const ExplodedNode *ErrorNode,
2539  BugReporterContext &BRC) {
2540  auto Notes = llvm::make_unique<VisitorsDiagnosticsTy>();
2541  BugReport::VisitorList visitors;
2542 
2543  // Run visitors on all nodes starting from the node *before* the last one.
2544  // The last node is reserved for notes generated with {@code getEndPath}.
2545  const ExplodedNode *NextNode = ErrorNode->getFirstPred();
2546  while (NextNode) {
2547 
2548  // At each iteration, move all visitors from report to visitor list.
2549  for (BugReport::visitor_iterator I = R->visitor_begin(),
2550  E = R->visitor_end();
2551  I != E; ++I) {
2552  visitors.push_back(std::move(*I));
2553  }
2554  R->clearVisitors();
2555 
2556  const ExplodedNode *Pred = NextNode->getFirstPred();
2557  if (!Pred) {
2558  std::shared_ptr<PathDiagnosticPiece> LastPiece;
2559  for (auto &V : visitors) {
2560  V->finalizeVisitor(BRC, ErrorNode, *R);
2561 
2562  if (auto Piece = V->getEndPath(BRC, ErrorNode, *R)) {
2563  assert(!LastPiece &&
2564  "There can only be one final piece in a diagnostic.");
2565  LastPiece = std::move(Piece);
2566  (*Notes)[ErrorNode].push_back(LastPiece);
2567  }
2568  }
2569  break;
2570  }
2571 
2572  for (auto &V : visitors) {
2573  auto P = V->VisitNode(NextNode, BRC, *R);
2574  if (P)
2575  (*Notes)[NextNode].push_back(std::move(P));
2576  }
2577 
2578  if (!R->isValid())
2579  break;
2580 
2581  NextNode = Pred;
2582  }
2583 
2584  return Notes;
2585 }
2586 
2587 /// Find a non-invalidated report for a given equivalence class,
2588 /// and return together with a cache of visitors notes.
2589 /// If none found, return a nullptr paired with an empty cache.
2590 static
2591 std::pair<BugReport*, std::unique_ptr<VisitorsDiagnosticsTy>> findValidReport(
2592  TrimmedGraph &TrimG,
2593  ReportGraph &ErrorGraph,
2594  ArrayRef<BugReport *> &bugReports,
2595  AnalyzerOptions &Opts,
2596  GRBugReporter &Reporter) {
2597 
2598  while (TrimG.popNextReportGraph(ErrorGraph)) {
2599  // Find the BugReport with the original location.
2600  assert(ErrorGraph.Index < bugReports.size());
2601  BugReport *R = bugReports[ErrorGraph.Index];
2602  assert(R && "No original report found for sliced graph.");
2603  assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
2604  const ExplodedNode *ErrorNode = ErrorGraph.ErrorNode;
2605 
2606  // Register refutation visitors first, if they mark the bug invalid no
2607  // further analysis is required
2608  R->addVisitor(llvm::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
2609 
2610  // Register additional node visitors.
2611  R->addVisitor(llvm::make_unique<NilReceiverBRVisitor>());
2612  R->addVisitor(llvm::make_unique<ConditionBRVisitor>());
2613  R->addVisitor(llvm::make_unique<CXXSelfAssignmentBRVisitor>());
2614  R->addVisitor(llvm::make_unique<TagVisitor>());
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:982
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:511
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:87
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:630
StringRef P
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
static void updateExecutedLinesWithDiagnosticPieces(PathDiagnostic &PD)
Populate executes lines with lines containing at least one diagnostics.
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:122
void Profile(llvm::FoldingSetNodeID &ID) const
iterator begin()
Definition: CFG.h: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:1710
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:2728
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:688
bool isBodyAutosynthesizedFromModelFile() const
Checks if the body of the Decl is generated by the BodyFarm from a model file.
STATISTIC(MaxBugClassSize, "The maximum number of bug reports in the same equivalence class")
This represents one expression.
Definition: Expr.h:108
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:5476
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:550
static bool lexicalContains(ParentMap &PM, const Stmt *X, const Stmt *Y)
Return true if X is contained by Y.
static const Stmt * getNextStmt(const ExplodedNode *N)
Retrieve the statement corresponding to the successor node.
void FlushReports()
Generate and flush diagnostics for all bug reports.
const CFGBlock * getDst() const
Definition: ProgramPoint.h:515
static void dropFunctionEntryEdge(PathPieces &Path, LocationContextMap &LCM, SourceManager &SM)
Drop the very first edge in a path, which should be a function entry edge.
bool isBodyAutosynthesized() const
Checks if the body of the Decl is generated by the BodyFarm.
SourceLocation getEnd() const
BugReporterContext(GRBugReporter &br, InterExplodedGraphMap &Backmap)
Definition: BugReporter.h:563
void markInteresting(SymbolRef sym)
static const Stmt * GetPreviousStmt(const ExplodedNode *N)
Definition: BugReporter.cpp:91
std::map< FileID, std::set< unsigned > > FilesToLineNumsMap
File IDs mapped to sets of line numbers.
unsigned getExpansionLineNumber(SourceLocation Loc, bool *Invalid=nullptr) const
const SourceManager & SM
Definition: Format.cpp:1568
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:988
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)
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
const llvm::MemoryBuffer * getBuffer(FileID FID, SourceLocation Loc, bool *Invalid=nullptr) const
Return the buffer for the specified FileID.
Dataflow Directional Tag Classes.
bool isValid() const
Return true if this is a valid SourceLocation object.
static const char StrLoopCollectionEmpty[]
std::pair< PathDiagnosticCallPiece *, const ExplodedNode * > StackDiagPair
static void addEdgeToPath(PathPieces &path, PathDiagnosticLocation &PrevLoc, PathDiagnosticLocation NewLoc)
Adds a sanitized control-flow diagnostic edge to a path.
StmtClass getStmtClass() const
Definition: Stmt.h:1041
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:1002
static void removeContextCycles(PathPieces &Path, SourceManager &SM)
Eliminate two-edge cycles created by addContextEdges().
succ_iterator succ_end()
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
virtual void Profile(llvm::FoldingSetNodeID &hash) const
Profile to identify equivalent bug reports for error report coalescing.
const StackFrameContext * getStackFrame() const
CharSourceRange getExpansionRange(SourceLocation Loc) const
Given a SourceLocation object, return the range of tokens covered by the expansion in the ultimate fi...
Stores options for the analyzer from the command line.
static std::shared_ptr< PathDiagnosticCallPiece > construct(const CallExitEnd &CE, const SourceManager &SM)
void generateMinimalDiagForBlockEdge(const ExplodedNode *N, BlockEdge BE, const SourceManager &SM, PathDiagnosticBuilder &PDB, PathDiagnostic &PD)
bool hasNoReturnElement() const
Definition: CFG.h: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:14051
llvm::ilist< BugReport >::iterator iterator
Definition: BugReporter.h:381
ProgramStateManager & getStateManager()
getStateManager - Return the state manager used by the analysis engine.
Used for HTML, SARIF, and text output.
Defines the clang::SourceLocation class and associated facilities.
static void reversePropagateInterestingSymbols(BugReport &R, InterestingExprs &IE, const ProgramState *State, const LocationContext *CalleeCtx)
pred_iterator pred_begin()
static const Stmt * getStmtParent(const Stmt *S, const ParentMap &PM)
static PathDiagnosticLocation createEndOfPath(const ExplodedNode *N, const SourceManager &SM)
Create a location corresponding to the next valid ExplodedNode as end of path location.
Represents a top-level expression in a basic block.
Definition: CFG.h:55
const MemRegion * getBaseRegion() const
Definition: MemRegion.cpp:1160
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:251
A SourceLocation and its associated SourceManager.
static void generatePathDiagnosticsForNode(const ExplodedNode *N, PathDiagnostic &PD, PathDiagnosticLocation &PrevLoc, PathDiagnosticBuilder &PDB, LocationContextMap &LCM, StackDiagVector &CallStack, InterestingExprs &IE, bool AddPathEdges)
Generate diagnostics for the node N, and write it into PD.
const ExplodedNode *const * const_pred_iterator
std::shared_ptr< PathDiagnosticControlFlowPiece > generateDiagForBinaryOP(const ExplodedNode *N, const Stmt *T, const CFGBlock *Src, const CFGBlock *Dst, const SourceManager &SM, PathDiagnosticBuilder &PDB, const LocationContext *LC)
A trivial tuple used to represent a source range.
static void addContextEdges(PathPieces &pieces, SourceManager &SM, const ParentMap &PM, const LocationContext *LCtx)
Adds synthetic edges from top-level statements to their subexpressions.
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
iterator end()
Definition: CFG.h: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)