BugReporter.cpp revision cc08ca9b3cd2b715a699bcc772ce2e83a502915a 
1// BugReporter.cpp - Generate PathDiagnostics for Bugs ------------*- C++ -*--//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines BugReporter, a utility class for generating
11//  PathDiagnostics.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "BugReporter"
16
17#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
18#include "clang/AST/ASTContext.h"
19#include "clang/AST/DeclObjC.h"
20#include "clang/AST/Expr.h"
21#include "clang/AST/ParentMap.h"
22#include "clang/AST/StmtObjC.h"
23#include "clang/Analysis/CFG.h"
24#include "clang/Analysis/ProgramPoint.h"
25#include "clang/Basic/SourceManager.h"
26#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
27#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
28#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/IntrusiveRefCntPtr.h"
31#include "llvm/ADT/OwningPtr.h"
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/SmallString.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/Support/raw_ostream.h"
36#include <queue>
37
38using namespace clang;
39using namespace ento;
40
41STATISTIC(MaxBugClassSize,
42          "The maximum number of bug reports in the same equivalence class");
43STATISTIC(MaxValidBugClassSize,
44          "The maximum number of bug reports in the same equivalence class "
45          "where at least one report is valid (not suppressed)");
46
47BugReporterVisitor::~BugReporterVisitor() {}
48
49void BugReporterContext::anchor() {}
50
51//===----------------------------------------------------------------------===//
52// Helper routines for walking the ExplodedGraph and fetching statements.
53//===----------------------------------------------------------------------===//
54
55static inline const Stmt *GetStmt(const ProgramPoint &P) {
56  if (Optional<StmtPoint> SP = P.getAs<StmtPoint>())
57    return SP->getStmt();
58  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>())
59    return BE->getSrc()->getTerminator();
60  if (Optional<CallEnter> CE = P.getAs<CallEnter>())
61    return CE->getCallExpr();
62  if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>())
63    return CEE->getCalleeContext()->getCallSite();
64
65  return 0;
66}
67
68static inline const ExplodedNode*
69GetPredecessorNode(const ExplodedNode *N) {
70  return N->pred_empty() ? NULL : *(N->pred_begin());
71}
72
73static inline const ExplodedNode*
74GetSuccessorNode(const ExplodedNode *N) {
75  return N->succ_empty() ? NULL : *(N->succ_begin());
76}
77
78static const Stmt *GetPreviousStmt(const ExplodedNode *N) {
79  for (N = GetPredecessorNode(N); N; N = GetPredecessorNode(N))
80    if (const Stmt *S = GetStmt(N->getLocation()))
81      return S;
82
83  return 0;
84}
85
86static const Stmt *GetNextStmt(const ExplodedNode *N) {
87  for (N = GetSuccessorNode(N); N; N = GetSuccessorNode(N))
88    if (const Stmt *S = GetStmt(N->getLocation())) {
89      // Check if the statement is '?' or '&&'/'||'.  These are "merges",
90      // not actual statement points.
91      switch (S->getStmtClass()) {
92        case Stmt::ChooseExprClass:
93        case Stmt::BinaryConditionalOperatorClass: continue;
94        case Stmt::ConditionalOperatorClass: continue;
95        case Stmt::BinaryOperatorClass: {
96          BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
97          if (Op == BO_LAnd || Op == BO_LOr)
98            continue;
99          break;
100        }
101        default:
102          break;
103      }
104      return S;
105    }
106
107  return 0;
108}
109
110static inline const Stmt*
111GetCurrentOrPreviousStmt(const ExplodedNode *N) {
112  if (const Stmt *S = GetStmt(N->getLocation()))
113    return S;
114
115  return GetPreviousStmt(N);
116}
117
118static inline const Stmt*
119GetCurrentOrNextStmt(const ExplodedNode *N) {
120  if (const Stmt *S = GetStmt(N->getLocation()))
121    return S;
122
123  return GetNextStmt(N);
124}
125
126//===----------------------------------------------------------------------===//
127// Diagnostic cleanup.
128//===----------------------------------------------------------------------===//
129
130static PathDiagnosticEventPiece *
131eventsDescribeSameCondition(PathDiagnosticEventPiece *X,
132                            PathDiagnosticEventPiece *Y) {
133  // Prefer diagnostics that come from ConditionBRVisitor over
134  // those that came from TrackConstraintBRVisitor.
135  const void *tagPreferred = ConditionBRVisitor::getTag();
136  const void *tagLesser = TrackConstraintBRVisitor::getTag();
137
138  if (X->getLocation() != Y->getLocation())
139    return 0;
140
141  if (X->getTag() == tagPreferred && Y->getTag() == tagLesser)
142    return X;
143
144  if (Y->getTag() == tagPreferred && X->getTag() == tagLesser)
145    return Y;
146
147  return 0;
148}
149
150/// An optimization pass over PathPieces that removes redundant diagnostics
151/// generated by both ConditionBRVisitor and TrackConstraintBRVisitor.  Both
152/// BugReporterVisitors use different methods to generate diagnostics, with
153/// one capable of emitting diagnostics in some cases but not in others.  This
154/// can lead to redundant diagnostic pieces at the same point in a path.
155static void removeRedundantMsgs(PathPieces &path) {
156  unsigned N = path.size();
157  if (N < 2)
158    return;
159  // NOTE: this loop intentionally is not using an iterator.  Instead, we
160  // are streaming the path and modifying it in place.  This is done by
161  // grabbing the front, processing it, and if we decide to keep it append
162  // it to the end of the path.  The entire path is processed in this way.
163  for (unsigned i = 0; i < N; ++i) {
164    IntrusiveRefCntPtr<PathDiagnosticPiece> piece(path.front());
165    path.pop_front();
166
167    switch (piece->getKind()) {
168      case clang::ento::PathDiagnosticPiece::Call:
169        removeRedundantMsgs(cast<PathDiagnosticCallPiece>(piece)->path);
170        break;
171      case clang::ento::PathDiagnosticPiece::Macro:
172        removeRedundantMsgs(cast<PathDiagnosticMacroPiece>(piece)->subPieces);
173        break;
174      case clang::ento::PathDiagnosticPiece::ControlFlow:
175        break;
176      case clang::ento::PathDiagnosticPiece::Event: {
177        if (i == N-1)
178          break;
179
180        if (PathDiagnosticEventPiece *nextEvent =
181            dyn_cast<PathDiagnosticEventPiece>(path.front().getPtr())) {
182          PathDiagnosticEventPiece *event =
183            cast<PathDiagnosticEventPiece>(piece);
184          // Check to see if we should keep one of the two pieces.  If we
185          // come up with a preference, record which piece to keep, and consume
186          // another piece from the path.
187          if (PathDiagnosticEventPiece *pieceToKeep =
188              eventsDescribeSameCondition(event, nextEvent)) {
189            piece = pieceToKeep;
190            path.pop_front();
191            ++i;
192          }
193        }
194        break;
195      }
196    }
197    path.push_back(piece);
198  }
199}
200
201/// Recursively scan through a path and prune out calls and macros pieces
202/// that aren't needed.  Return true if afterwards the path contains
203/// "interesting stuff" which means it shouldn't be pruned from the parent path.
204bool BugReporter::RemoveUnneededCalls(PathPieces &pieces, BugReport *R) {
205  bool containsSomethingInteresting = false;
206  const unsigned N = pieces.size();
207
208  for (unsigned i = 0 ; i < N ; ++i) {
209    // Remove the front piece from the path.  If it is still something we
210    // want to keep once we are done, we will push it back on the end.
211    IntrusiveRefCntPtr<PathDiagnosticPiece> piece(pieces.front());
212    pieces.pop_front();
213
214    // Throw away pieces with invalid locations. Note that we can't throw away
215    // calls just yet because they might have something interesting inside them.
216    // If so, their locations will be adjusted as necessary later.
217    if (piece->getKind() != PathDiagnosticPiece::Call &&
218        piece->getLocation().asLocation().isInvalid())
219      continue;
220
221    switch (piece->getKind()) {
222      case PathDiagnosticPiece::Call: {
223        PathDiagnosticCallPiece *call = cast<PathDiagnosticCallPiece>(piece);
224        // Check if the location context is interesting.
225        assert(LocationContextMap.count(call));
226        if (R->isInteresting(LocationContextMap[call])) {
227          containsSomethingInteresting = true;
228          break;
229        }
230
231        if (!RemoveUnneededCalls(call->path, R))
232          continue;
233
234        containsSomethingInteresting = true;
235        break;
236      }
237      case PathDiagnosticPiece::Macro: {
238        PathDiagnosticMacroPiece *macro = cast<PathDiagnosticMacroPiece>(piece);
239        if (!RemoveUnneededCalls(macro->subPieces, R))
240          continue;
241        containsSomethingInteresting = true;
242        break;
243      }
244      case PathDiagnosticPiece::Event: {
245        PathDiagnosticEventPiece *event = cast<PathDiagnosticEventPiece>(piece);
246
247        // We never throw away an event, but we do throw it away wholesale
248        // as part of a path if we throw the entire path away.
249        containsSomethingInteresting |= !event->isPrunable();
250        break;
251      }
252      case PathDiagnosticPiece::ControlFlow:
253        break;
254    }
255
256    pieces.push_back(piece);
257  }
258
259  return containsSomethingInteresting;
260}
261
262/// Recursively scan through a path and make sure that all call pieces have
263/// valid locations. Note that all other pieces with invalid locations should
264/// have already been pruned out.
265static void adjustCallLocations(PathPieces &Pieces,
266                                PathDiagnosticLocation *LastCallLocation = 0) {
267  for (PathPieces::iterator I = Pieces.begin(), E = Pieces.end(); I != E; ++I) {
268    PathDiagnosticCallPiece *Call = dyn_cast<PathDiagnosticCallPiece>(*I);
269
270    if (!Call) {
271      assert((*I)->getLocation().asLocation().isValid());
272      continue;
273    }
274
275    if (LastCallLocation) {
276      if (!Call->callEnter.asLocation().isValid() ||
277          Call->getCaller()->isImplicit())
278        Call->callEnter = *LastCallLocation;
279      if (!Call->callReturn.asLocation().isValid() ||
280          Call->getCaller()->isImplicit())
281        Call->callReturn = *LastCallLocation;
282    }
283
284    // Recursively clean out the subclass.  Keep this call around if
285    // it contains any informative diagnostics.
286    PathDiagnosticLocation *ThisCallLocation;
287    if (Call->callEnterWithin.asLocation().isValid() &&
288        !Call->getCallee()->isImplicit())
289      ThisCallLocation = &Call->callEnterWithin;
290    else
291      ThisCallLocation = &Call->callEnter;
292
293    assert(ThisCallLocation && "Outermost call has an invalid location");
294    adjustCallLocations(Call->path, ThisCallLocation);
295  }
296}
297
298//===----------------------------------------------------------------------===//
299// PathDiagnosticBuilder and its associated routines and helper objects.
300//===----------------------------------------------------------------------===//
301
302typedef llvm::DenseMap<const ExplodedNode*,
303const ExplodedNode*> NodeBackMap;
304
305namespace {
306class NodeMapClosure : public BugReport::NodeResolver {
307  NodeBackMap& M;
308public:
309  NodeMapClosure(NodeBackMap *m) : M(*m) {}
310  ~NodeMapClosure() {}
311
312  const ExplodedNode *getOriginalNode(const ExplodedNode *N) {
313    NodeBackMap::iterator I = M.find(N);
314    return I == M.end() ? 0 : I->second;
315  }
316};
317
318class PathDiagnosticBuilder : public BugReporterContext {
319  BugReport *R;
320  PathDiagnosticConsumer *PDC;
321  NodeMapClosure NMC;
322public:
323  const LocationContext *LC;
324
325  PathDiagnosticBuilder(GRBugReporter &br,
326                        BugReport *r, NodeBackMap *Backmap,
327                        PathDiagnosticConsumer *pdc)
328    : BugReporterContext(br),
329      R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext())
330  {}
331
332  PathDiagnosticLocation ExecutionContinues(const ExplodedNode *N);
333
334  PathDiagnosticLocation ExecutionContinues(llvm::raw_string_ostream &os,
335                                            const ExplodedNode *N);
336
337  BugReport *getBugReport() { return R; }
338
339  Decl const &getCodeDecl() { return R->getErrorNode()->getCodeDecl(); }
340
341  ParentMap& getParentMap() { return LC->getParentMap(); }
342
343  const Stmt *getParent(const Stmt *S) {
344    return getParentMap().getParent(S);
345  }
346
347  virtual NodeMapClosure& getNodeResolver() { return NMC; }
348
349  PathDiagnosticLocation getEnclosingStmtLocation(const Stmt *S);
350
351  PathDiagnosticConsumer::PathGenerationScheme getGenerationScheme() const {
352    return PDC ? PDC->getGenerationScheme() : PathDiagnosticConsumer::Extensive;
353  }
354
355  bool supportsLogicalOpControlFlow() const {
356    return PDC ? PDC->supportsLogicalOpControlFlow() : true;
357  }
358};
359} // end anonymous namespace
360
361PathDiagnosticLocation
362PathDiagnosticBuilder::ExecutionContinues(const ExplodedNode *N) {
363  if (const Stmt *S = GetNextStmt(N))
364    return PathDiagnosticLocation(S, getSourceManager(), LC);
365
366  return PathDiagnosticLocation::createDeclEnd(N->getLocationContext(),
367                                               getSourceManager());
368}
369
370PathDiagnosticLocation
371PathDiagnosticBuilder::ExecutionContinues(llvm::raw_string_ostream &os,
372                                          const ExplodedNode *N) {
373
374  // Slow, but probably doesn't matter.
375  if (os.str().empty())
376    os << ' ';
377
378  const PathDiagnosticLocation &Loc = ExecutionContinues(N);
379
380  if (Loc.asStmt())
381    os << "Execution continues on line "
382       << getSourceManager().getExpansionLineNumber(Loc.asLocation())
383       << '.';
384  else {
385    os << "Execution jumps to the end of the ";
386    const Decl *D = N->getLocationContext()->getDecl();
387    if (isa<ObjCMethodDecl>(D))
388      os << "method";
389    else if (isa<FunctionDecl>(D))
390      os << "function";
391    else {
392      assert(isa<BlockDecl>(D));
393      os << "anonymous block";
394    }
395    os << '.';
396  }
397
398  return Loc;
399}
400
401static bool IsNested(const Stmt *S, ParentMap &PM) {
402  if (isa<Expr>(S) && PM.isConsumedExpr(cast<Expr>(S)))
403    return true;
404
405  const Stmt *Parent = PM.getParentIgnoreParens(S);
406
407  if (Parent)
408    switch (Parent->getStmtClass()) {
409      case Stmt::ForStmtClass:
410      case Stmt::DoStmtClass:
411      case Stmt::WhileStmtClass:
412        return true;
413      default:
414        break;
415    }
416
417  return false;
418}
419
420PathDiagnosticLocation
421PathDiagnosticBuilder::getEnclosingStmtLocation(const Stmt *S) {
422  assert(S && "Null Stmt *passed to getEnclosingStmtLocation");
423  ParentMap &P = getParentMap();
424  SourceManager &SMgr = getSourceManager();
425
426  while (IsNested(S, P)) {
427    const Stmt *Parent = P.getParentIgnoreParens(S);
428
429    if (!Parent)
430      break;
431
432    switch (Parent->getStmtClass()) {
433      case Stmt::BinaryOperatorClass: {
434        const BinaryOperator *B = cast<BinaryOperator>(Parent);
435        if (B->isLogicalOp())
436          return PathDiagnosticLocation(S, SMgr, LC);
437        break;
438      }
439      case Stmt::CompoundStmtClass:
440      case Stmt::StmtExprClass:
441        return PathDiagnosticLocation(S, SMgr, LC);
442      case Stmt::ChooseExprClass:
443        // Similar to '?' if we are referring to condition, just have the edge
444        // point to the entire choose expression.
445        if (cast<ChooseExpr>(Parent)->getCond() == S)
446          return PathDiagnosticLocation(Parent, SMgr, LC);
447        else
448          return PathDiagnosticLocation(S, SMgr, LC);
449      case Stmt::BinaryConditionalOperatorClass:
450      case Stmt::ConditionalOperatorClass:
451        // For '?', if we are referring to condition, just have the edge point
452        // to the entire '?' expression.
453        if (cast<AbstractConditionalOperator>(Parent)->getCond() == S)
454          return PathDiagnosticLocation(Parent, SMgr, LC);
455        else
456          return PathDiagnosticLocation(S, SMgr, LC);
457      case Stmt::DoStmtClass:
458          return PathDiagnosticLocation(S, SMgr, LC);
459      case Stmt::ForStmtClass:
460        if (cast<ForStmt>(Parent)->getBody() == S)
461          return PathDiagnosticLocation(S, SMgr, LC);
462        break;
463      case Stmt::IfStmtClass:
464        if (cast<IfStmt>(Parent)->getCond() != S)
465          return PathDiagnosticLocation(S, SMgr, LC);
466        break;
467      case Stmt::ObjCForCollectionStmtClass:
468        if (cast<ObjCForCollectionStmt>(Parent)->getBody() == S)
469          return PathDiagnosticLocation(S, SMgr, LC);
470        break;
471      case Stmt::WhileStmtClass:
472        if (cast<WhileStmt>(Parent)->getCond() != S)
473          return PathDiagnosticLocation(S, SMgr, LC);
474        break;
475      default:
476        break;
477    }
478
479    S = Parent;
480  }
481
482  assert(S && "Cannot have null Stmt for PathDiagnosticLocation");
483
484  // Special case: DeclStmts can appear in for statement declarations, in which
485  //  case the ForStmt is the context.
486  if (isa<DeclStmt>(S)) {
487    if (const Stmt *Parent = P.getParent(S)) {
488      switch (Parent->getStmtClass()) {
489        case Stmt::ForStmtClass:
490        case Stmt::ObjCForCollectionStmtClass:
491          return PathDiagnosticLocation(Parent, SMgr, LC);
492        default:
493          break;
494      }
495    }
496  }
497  else if (isa<BinaryOperator>(S)) {
498    // Special case: the binary operator represents the initialization
499    // code in a for statement (this can happen when the variable being
500    // initialized is an old variable.
501    if (const ForStmt *FS =
502          dyn_cast_or_null<ForStmt>(P.getParentIgnoreParens(S))) {
503      if (FS->getInit() == S)
504        return PathDiagnosticLocation(FS, SMgr, LC);
505    }
506  }
507
508  return PathDiagnosticLocation(S, SMgr, LC);
509}
510
511//===----------------------------------------------------------------------===//
512// "Visitors only" path diagnostic generation algorithm.
513//===----------------------------------------------------------------------===//
514static bool GenerateVisitorsOnlyPathDiagnostic(PathDiagnostic &PD,
515                                               PathDiagnosticBuilder &PDB,
516                                               const ExplodedNode *N,
517                                      ArrayRef<BugReporterVisitor *> visitors) {
518  // All path generation skips the very first node (the error node).
519  // This is because there is special handling for the end-of-path note.
520  N = N->getFirstPred();
521  if (!N)
522    return true;
523
524  BugReport *R = PDB.getBugReport();
525  while (const ExplodedNode *Pred = N->getFirstPred()) {
526    for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
527                                                  E = visitors.end();
528         I != E; ++I) {
529      // Visit all the node pairs, but throw the path pieces away.
530      PathDiagnosticPiece *Piece = (*I)->VisitNode(N, Pred, PDB, *R);
531      delete Piece;
532    }
533
534    N = Pred;
535  }
536
537  return R->isValid();
538}
539
540//===----------------------------------------------------------------------===//
541// "Minimal" path diagnostic generation algorithm.
542//===----------------------------------------------------------------------===//
543typedef std::pair<PathDiagnosticCallPiece*, const ExplodedNode*> StackDiagPair;
544typedef SmallVector<StackDiagPair, 6> StackDiagVector;
545
546static void updateStackPiecesWithMessage(PathDiagnosticPiece *P,
547                                         StackDiagVector &CallStack) {
548  // If the piece contains a special message, add it to all the call
549  // pieces on the active stack.
550  if (PathDiagnosticEventPiece *ep =
551        dyn_cast<PathDiagnosticEventPiece>(P)) {
552
553    if (ep->hasCallStackHint())
554      for (StackDiagVector::iterator I = CallStack.begin(),
555                                     E = CallStack.end(); I != E; ++I) {
556        PathDiagnosticCallPiece *CP = I->first;
557        const ExplodedNode *N = I->second;
558        std::string stackMsg = ep->getCallStackMessage(N);
559
560        // The last message on the path to final bug is the most important
561        // one. Since we traverse the path backwards, do not add the message
562        // if one has been previously added.
563        if  (!CP->hasCallStackMessage())
564          CP->setCallStackMessage(stackMsg);
565      }
566  }
567}
568
569static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM);
570
571static bool GenerateMinimalPathDiagnostic(PathDiagnostic& PD,
572                                          PathDiagnosticBuilder &PDB,
573                                          const ExplodedNode *N,
574                                      ArrayRef<BugReporterVisitor *> visitors) {
575
576  SourceManager& SMgr = PDB.getSourceManager();
577  const LocationContext *LC = PDB.LC;
578  const ExplodedNode *NextNode = N->pred_empty()
579                                        ? NULL : *(N->pred_begin());
580
581  StackDiagVector CallStack;
582
583  while (NextNode) {
584    N = NextNode;
585    PDB.LC = N->getLocationContext();
586    NextNode = GetPredecessorNode(N);
587
588    ProgramPoint P = N->getLocation();
589
590    do {
591      if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
592        PathDiagnosticCallPiece *C =
593            PathDiagnosticCallPiece::construct(N, *CE, SMgr);
594        GRBugReporter& BR = PDB.getBugReporter();
595        BR.addCallPieceLocationContextPair(C, CE->getCalleeContext());
596        PD.getActivePath().push_front(C);
597        PD.pushActivePath(&C->path);
598        CallStack.push_back(StackDiagPair(C, N));
599        break;
600      }
601
602      if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
603        // Flush all locations, and pop the active path.
604        bool VisitedEntireCall = PD.isWithinCall();
605        PD.popActivePath();
606
607        // Either we just added a bunch of stuff to the top-level path, or
608        // we have a previous CallExitEnd.  If the former, it means that the
609        // path terminated within a function call.  We must then take the
610        // current contents of the active path and place it within
611        // a new PathDiagnosticCallPiece.
612        PathDiagnosticCallPiece *C;
613        if (VisitedEntireCall) {
614          C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
615        } else {
616          const Decl *Caller = CE->getLocationContext()->getDecl();
617          C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
618          GRBugReporter& BR = PDB.getBugReporter();
619          BR.addCallPieceLocationContextPair(C, CE->getCalleeContext());
620        }
621
622        C->setCallee(*CE, SMgr);
623        if (!CallStack.empty()) {
624          assert(CallStack.back().first == C);
625          CallStack.pop_back();
626        }
627        break;
628      }
629
630      if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
631        const CFGBlock *Src = BE->getSrc();
632        const CFGBlock *Dst = BE->getDst();
633        const Stmt *T = Src->getTerminator();
634
635        if (!T)
636          break;
637
638        PathDiagnosticLocation Start =
639            PathDiagnosticLocation::createBegin(T, SMgr,
640                N->getLocationContext());
641
642        switch (T->getStmtClass()) {
643        default:
644          break;
645
646        case Stmt::GotoStmtClass:
647        case Stmt::IndirectGotoStmtClass: {
648          const Stmt *S = GetNextStmt(N);
649
650          if (!S)
651            break;
652
653          std::string sbuf;
654          llvm::raw_string_ostream os(sbuf);
655          const PathDiagnosticLocation &End = PDB.getEnclosingStmtLocation(S);
656
657          os << "Control jumps to line "
658              << End.asLocation().getExpansionLineNumber();
659          PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
660              Start, End, os.str()));
661          break;
662        }
663
664        case Stmt::SwitchStmtClass: {
665          // Figure out what case arm we took.
666          std::string sbuf;
667          llvm::raw_string_ostream os(sbuf);
668
669          if (const Stmt *S = Dst->getLabel()) {
670            PathDiagnosticLocation End(S, SMgr, LC);
671
672            switch (S->getStmtClass()) {
673            default:
674              os << "No cases match in the switch statement. "
675              "Control jumps to line "
676              << End.asLocation().getExpansionLineNumber();
677              break;
678            case Stmt::DefaultStmtClass:
679              os << "Control jumps to the 'default' case at line "
680              << End.asLocation().getExpansionLineNumber();
681              break;
682
683            case Stmt::CaseStmtClass: {
684              os << "Control jumps to 'case ";
685              const CaseStmt *Case = cast<CaseStmt>(S);
686              const Expr *LHS = Case->getLHS()->IgnoreParenCasts();
687
688              // Determine if it is an enum.
689              bool GetRawInt = true;
690
691              if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
692                // FIXME: Maybe this should be an assertion.  Are there cases
693                // were it is not an EnumConstantDecl?
694                const EnumConstantDecl *D =
695                    dyn_cast<EnumConstantDecl>(DR->getDecl());
696
697                if (D) {
698                  GetRawInt = false;
699                  os << *D;
700                }
701              }
702
703              if (GetRawInt)
704                os << LHS->EvaluateKnownConstInt(PDB.getASTContext());
705
706              os << ":'  at line "
707                  << End.asLocation().getExpansionLineNumber();
708              break;
709            }
710            }
711            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
712                Start, End, os.str()));
713          }
714          else {
715            os << "'Default' branch taken. ";
716            const PathDiagnosticLocation &End = PDB.ExecutionContinues(os, N);
717            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
718                Start, End, os.str()));
719          }
720
721          break;
722        }
723
724        case Stmt::BreakStmtClass:
725        case Stmt::ContinueStmtClass: {
726          std::string sbuf;
727          llvm::raw_string_ostream os(sbuf);
728          PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
729          PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
730              Start, End, os.str()));
731          break;
732        }
733
734        // Determine control-flow for ternary '?'.
735        case Stmt::BinaryConditionalOperatorClass:
736        case Stmt::ConditionalOperatorClass: {
737          std::string sbuf;
738          llvm::raw_string_ostream os(sbuf);
739          os << "'?' condition is ";
740
741          if (*(Src->succ_begin()+1) == Dst)
742            os << "false";
743          else
744            os << "true";
745
746          PathDiagnosticLocation End = PDB.ExecutionContinues(N);
747
748          if (const Stmt *S = End.asStmt())
749            End = PDB.getEnclosingStmtLocation(S);
750
751          PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
752              Start, End, os.str()));
753          break;
754        }
755
756        // Determine control-flow for short-circuited '&&' and '||'.
757        case Stmt::BinaryOperatorClass: {
758          if (!PDB.supportsLogicalOpControlFlow())
759            break;
760
761          const BinaryOperator *B = cast<BinaryOperator>(T);
762          std::string sbuf;
763          llvm::raw_string_ostream os(sbuf);
764          os << "Left side of '";
765
766          if (B->getOpcode() == BO_LAnd) {
767            os << "&&" << "' is ";
768
769            if (*(Src->succ_begin()+1) == Dst) {
770              os << "false";
771              PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
772              PathDiagnosticLocation Start =
773                  PathDiagnosticLocation::createOperatorLoc(B, SMgr);
774              PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
775                  Start, End, os.str()));
776            }
777            else {
778              os << "true";
779              PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
780              PathDiagnosticLocation End = PDB.ExecutionContinues(N);
781              PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
782                  Start, End, os.str()));
783            }
784          }
785          else {
786            assert(B->getOpcode() == BO_LOr);
787            os << "||" << "' is ";
788
789            if (*(Src->succ_begin()+1) == Dst) {
790              os << "false";
791              PathDiagnosticLocation Start(B->getLHS(), SMgr, LC);
792              PathDiagnosticLocation End = PDB.ExecutionContinues(N);
793              PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
794                  Start, End, os.str()));
795            }
796            else {
797              os << "true";
798              PathDiagnosticLocation End(B->getLHS(), SMgr, LC);
799              PathDiagnosticLocation Start =
800                  PathDiagnosticLocation::createOperatorLoc(B, SMgr);
801              PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
802                  Start, End, os.str()));
803            }
804          }
805
806          break;
807        }
808
809        case Stmt::DoStmtClass:  {
810          if (*(Src->succ_begin()) == Dst) {
811            std::string sbuf;
812            llvm::raw_string_ostream os(sbuf);
813
814            os << "Loop condition is true. ";
815            PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
816
817            if (const Stmt *S = End.asStmt())
818              End = PDB.getEnclosingStmtLocation(S);
819
820            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
821                Start, End, os.str()));
822          }
823          else {
824            PathDiagnosticLocation End = PDB.ExecutionContinues(N);
825
826            if (const Stmt *S = End.asStmt())
827              End = PDB.getEnclosingStmtLocation(S);
828
829            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
830                Start, End, "Loop condition is false.  Exiting loop"));
831          }
832
833          break;
834        }
835
836        case Stmt::WhileStmtClass:
837        case Stmt::ForStmtClass: {
838          if (*(Src->succ_begin()+1) == Dst) {
839            std::string sbuf;
840            llvm::raw_string_ostream os(sbuf);
841
842            os << "Loop condition is false. ";
843            PathDiagnosticLocation End = PDB.ExecutionContinues(os, N);
844            if (const Stmt *S = End.asStmt())
845              End = PDB.getEnclosingStmtLocation(S);
846
847            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
848                Start, End, os.str()));
849          }
850          else {
851            PathDiagnosticLocation End = PDB.ExecutionContinues(N);
852            if (const Stmt *S = End.asStmt())
853              End = PDB.getEnclosingStmtLocation(S);
854
855            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
856                Start, End, "Loop condition is true.  Entering loop body"));
857          }
858
859          break;
860        }
861
862        case Stmt::IfStmtClass: {
863          PathDiagnosticLocation End = PDB.ExecutionContinues(N);
864
865          if (const Stmt *S = End.asStmt())
866            End = PDB.getEnclosingStmtLocation(S);
867
868          if (*(Src->succ_begin()+1) == Dst)
869            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
870                Start, End, "Taking false branch"));
871          else
872            PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(
873                Start, End, "Taking true branch"));
874
875          break;
876        }
877        }
878      }
879    } while(0);
880
881    if (NextNode) {
882      // Add diagnostic pieces from custom visitors.
883      BugReport *R = PDB.getBugReport();
884      for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
885                                                    E = visitors.end();
886           I != E; ++I) {
887        if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
888          PD.getActivePath().push_front(p);
889          updateStackPiecesWithMessage(p, CallStack);
890        }
891      }
892    }
893  }
894
895  if (!PDB.getBugReport()->isValid())
896    return false;
897
898  // After constructing the full PathDiagnostic, do a pass over it to compact
899  // PathDiagnosticPieces that occur within a macro.
900  CompactPathDiagnostic(PD.getMutablePieces(), PDB.getSourceManager());
901  return true;
902}
903
904//===----------------------------------------------------------------------===//
905// "Extensive" PathDiagnostic generation.
906//===----------------------------------------------------------------------===//
907
908static bool IsControlFlowExpr(const Stmt *S) {
909  const Expr *E = dyn_cast<Expr>(S);
910
911  if (!E)
912    return false;
913
914  E = E->IgnoreParenCasts();
915
916  if (isa<AbstractConditionalOperator>(E))
917    return true;
918
919  if (const BinaryOperator *B = dyn_cast<BinaryOperator>(E))
920    if (B->isLogicalOp())
921      return true;
922
923  return false;
924}
925
926namespace {
927class ContextLocation : public PathDiagnosticLocation {
928  bool IsDead;
929public:
930  ContextLocation(const PathDiagnosticLocation &L, bool isdead = false)
931    : PathDiagnosticLocation(L), IsDead(isdead) {}
932
933  void markDead() { IsDead = true; }
934  bool isDead() const { return IsDead; }
935};
936
937class EdgeBuilder {
938  std::vector<ContextLocation> CLocs;
939  typedef std::vector<ContextLocation>::iterator iterator;
940  PathDiagnostic &PD;
941  PathDiagnosticBuilder &PDB;
942  PathDiagnosticLocation PrevLoc;
943
944  bool IsConsumedExpr(const PathDiagnosticLocation &L);
945
946  bool containsLocation(const PathDiagnosticLocation &Container,
947                        const PathDiagnosticLocation &Containee);
948
949  PathDiagnosticLocation getContextLocation(const PathDiagnosticLocation &L);
950
951  PathDiagnosticLocation cleanUpLocation(PathDiagnosticLocation L,
952                                         bool firstCharOnly = false) {
953    if (const Stmt *S = L.asStmt()) {
954      const Stmt *Original = S;
955      while (1) {
956        // Adjust the location for some expressions that are best referenced
957        // by one of their subexpressions.
958        switch (S->getStmtClass()) {
959          default:
960            break;
961          case Stmt::ParenExprClass:
962          case Stmt::GenericSelectionExprClass:
963            S = cast<Expr>(S)->IgnoreParens();
964            firstCharOnly = true;
965            continue;
966          case Stmt::BinaryConditionalOperatorClass:
967          case Stmt::ConditionalOperatorClass:
968            S = cast<AbstractConditionalOperator>(S)->getCond();
969            firstCharOnly = true;
970            continue;
971          case Stmt::ChooseExprClass:
972            S = cast<ChooseExpr>(S)->getCond();
973            firstCharOnly = true;
974            continue;
975          case Stmt::BinaryOperatorClass:
976            S = cast<BinaryOperator>(S)->getLHS();
977            firstCharOnly = true;
978            continue;
979        }
980
981        break;
982      }
983
984      if (S != Original)
985        L = PathDiagnosticLocation(S, L.getManager(), PDB.LC);
986    }
987
988    if (firstCharOnly)
989      L  = PathDiagnosticLocation::createSingleLocation(L);
990
991    return L;
992  }
993
994  void popLocation() {
995    if (!CLocs.back().isDead() && CLocs.back().asLocation().isFileID()) {
996      // For contexts, we only one the first character as the range.
997      rawAddEdge(cleanUpLocation(CLocs.back(), true));
998    }
999    CLocs.pop_back();
1000  }
1001
1002public:
1003  EdgeBuilder(PathDiagnostic &pd, PathDiagnosticBuilder &pdb)
1004    : PD(pd), PDB(pdb) {
1005
1006      // If the PathDiagnostic already has pieces, add the enclosing statement
1007      // of the first piece as a context as well.
1008      if (!PD.path.empty()) {
1009        PrevLoc = (*PD.path.begin())->getLocation();
1010
1011        if (const Stmt *S = PrevLoc.asStmt())
1012          addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1013      }
1014  }
1015
1016  ~EdgeBuilder() {
1017    while (!CLocs.empty()) popLocation();
1018
1019    // Finally, add an initial edge from the start location of the first
1020    // statement (if it doesn't already exist).
1021    PathDiagnosticLocation L = PathDiagnosticLocation::createDeclBegin(
1022                                                       PDB.LC,
1023                                                       PDB.getSourceManager());
1024    if (L.isValid())
1025      rawAddEdge(L);
1026  }
1027
1028  void flushLocations() {
1029    while (!CLocs.empty())
1030      popLocation();
1031    PrevLoc = PathDiagnosticLocation();
1032  }
1033
1034  void addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd = false);
1035
1036  void rawAddEdge(PathDiagnosticLocation NewLoc);
1037
1038  void addContext(const Stmt *S);
1039  void addContext(const PathDiagnosticLocation &L);
1040  void addExtendedContext(const Stmt *S);
1041};
1042} // end anonymous namespace
1043
1044
1045PathDiagnosticLocation
1046EdgeBuilder::getContextLocation(const PathDiagnosticLocation &L) {
1047  if (const Stmt *S = L.asStmt()) {
1048    if (IsControlFlowExpr(S))
1049      return L;
1050
1051    return PDB.getEnclosingStmtLocation(S);
1052  }
1053
1054  return L;
1055}
1056
1057bool EdgeBuilder::containsLocation(const PathDiagnosticLocation &Container,
1058                                   const PathDiagnosticLocation &Containee) {
1059
1060  if (Container == Containee)
1061    return true;
1062
1063  if (Container.asDecl())
1064    return true;
1065
1066  if (const Stmt *S = Containee.asStmt())
1067    if (const Stmt *ContainerS = Container.asStmt()) {
1068      while (S) {
1069        if (S == ContainerS)
1070          return true;
1071        S = PDB.getParent(S);
1072      }
1073      return false;
1074    }
1075
1076  // Less accurate: compare using source ranges.
1077  SourceRange ContainerR = Container.asRange();
1078  SourceRange ContaineeR = Containee.asRange();
1079
1080  SourceManager &SM = PDB.getSourceManager();
1081  SourceLocation ContainerRBeg = SM.getExpansionLoc(ContainerR.getBegin());
1082  SourceLocation ContainerREnd = SM.getExpansionLoc(ContainerR.getEnd());
1083  SourceLocation ContaineeRBeg = SM.getExpansionLoc(ContaineeR.getBegin());
1084  SourceLocation ContaineeREnd = SM.getExpansionLoc(ContaineeR.getEnd());
1085
1086  unsigned ContainerBegLine = SM.getExpansionLineNumber(ContainerRBeg);
1087  unsigned ContainerEndLine = SM.getExpansionLineNumber(ContainerREnd);
1088  unsigned ContaineeBegLine = SM.getExpansionLineNumber(ContaineeRBeg);
1089  unsigned ContaineeEndLine = SM.getExpansionLineNumber(ContaineeREnd);
1090
1091  assert(ContainerBegLine <= ContainerEndLine);
1092  assert(ContaineeBegLine <= ContaineeEndLine);
1093
1094  return (ContainerBegLine <= ContaineeBegLine &&
1095          ContainerEndLine >= ContaineeEndLine &&
1096          (ContainerBegLine != ContaineeBegLine ||
1097           SM.getExpansionColumnNumber(ContainerRBeg) <=
1098           SM.getExpansionColumnNumber(ContaineeRBeg)) &&
1099          (ContainerEndLine != ContaineeEndLine ||
1100           SM.getExpansionColumnNumber(ContainerREnd) >=
1101           SM.getExpansionColumnNumber(ContaineeREnd)));
1102}
1103
1104void EdgeBuilder::rawAddEdge(PathDiagnosticLocation NewLoc) {
1105  if (!PrevLoc.isValid()) {
1106    PrevLoc = NewLoc;
1107    return;
1108  }
1109
1110  const PathDiagnosticLocation &NewLocClean = cleanUpLocation(NewLoc);
1111  const PathDiagnosticLocation &PrevLocClean = cleanUpLocation(PrevLoc);
1112
1113  if (PrevLocClean.asLocation().isInvalid()) {
1114    PrevLoc = NewLoc;
1115    return;
1116  }
1117
1118  if (NewLocClean.asLocation() == PrevLocClean.asLocation())
1119    return;
1120
1121  // FIXME: Ignore intra-macro edges for now.
1122  if (NewLocClean.asLocation().getExpansionLoc() ==
1123      PrevLocClean.asLocation().getExpansionLoc())
1124    return;
1125
1126  PD.getActivePath().push_front(new PathDiagnosticControlFlowPiece(NewLocClean, PrevLocClean));
1127  PrevLoc = NewLoc;
1128}
1129
1130void EdgeBuilder::addEdge(PathDiagnosticLocation NewLoc, bool alwaysAdd) {
1131
1132  if (!alwaysAdd && NewLoc.asLocation().isMacroID())
1133    return;
1134
1135  const PathDiagnosticLocation &CLoc = getContextLocation(NewLoc);
1136
1137  while (!CLocs.empty()) {
1138    ContextLocation &TopContextLoc = CLocs.back();
1139
1140    // Is the top location context the same as the one for the new location?
1141    if (TopContextLoc == CLoc) {
1142      if (alwaysAdd) {
1143        if (IsConsumedExpr(TopContextLoc) &&
1144            !IsControlFlowExpr(TopContextLoc.asStmt()))
1145            TopContextLoc.markDead();
1146
1147        rawAddEdge(NewLoc);
1148      }
1149
1150      return;
1151    }
1152
1153    if (containsLocation(TopContextLoc, CLoc)) {
1154      if (alwaysAdd) {
1155        rawAddEdge(NewLoc);
1156
1157        if (IsConsumedExpr(CLoc) && !IsControlFlowExpr(CLoc.asStmt())) {
1158          CLocs.push_back(ContextLocation(CLoc, true));
1159          return;
1160        }
1161      }
1162
1163      CLocs.push_back(CLoc);
1164      return;
1165    }
1166
1167    // Context does not contain the location.  Flush it.
1168    popLocation();
1169  }
1170
1171  // If we reach here, there is no enclosing context.  Just add the edge.
1172  rawAddEdge(NewLoc);
1173}
1174
1175bool EdgeBuilder::IsConsumedExpr(const PathDiagnosticLocation &L) {
1176  if (const Expr *X = dyn_cast_or_null<Expr>(L.asStmt()))
1177    return PDB.getParentMap().isConsumedExpr(X) && !IsControlFlowExpr(X);
1178
1179  return false;
1180}
1181
1182void EdgeBuilder::addExtendedContext(const Stmt *S) {
1183  if (!S)
1184    return;
1185
1186  const Stmt *Parent = PDB.getParent(S);
1187  while (Parent) {
1188    if (isa<CompoundStmt>(Parent))
1189      Parent = PDB.getParent(Parent);
1190    else
1191      break;
1192  }
1193
1194  if (Parent) {
1195    switch (Parent->getStmtClass()) {
1196      case Stmt::DoStmtClass:
1197      case Stmt::ObjCAtSynchronizedStmtClass:
1198        addContext(Parent);
1199      default:
1200        break;
1201    }
1202  }
1203
1204  addContext(S);
1205}
1206
1207void EdgeBuilder::addContext(const Stmt *S) {
1208  if (!S)
1209    return;
1210
1211  PathDiagnosticLocation L(S, PDB.getSourceManager(), PDB.LC);
1212  addContext(L);
1213}
1214
1215void EdgeBuilder::addContext(const PathDiagnosticLocation &L) {
1216  while (!CLocs.empty()) {
1217    const PathDiagnosticLocation &TopContextLoc = CLocs.back();
1218
1219    // Is the top location context the same as the one for the new location?
1220    if (TopContextLoc == L)
1221      return;
1222
1223    if (containsLocation(TopContextLoc, L)) {
1224      CLocs.push_back(L);
1225      return;
1226    }
1227
1228    // Context does not contain the location.  Flush it.
1229    popLocation();
1230  }
1231
1232  CLocs.push_back(L);
1233}
1234
1235// Cone-of-influence: support the reverse propagation of "interesting" symbols
1236// and values by tracing interesting calculations backwards through evaluated
1237// expressions along a path.  This is probably overly complicated, but the idea
1238// is that if an expression computed an "interesting" value, the child
1239// expressions are are also likely to be "interesting" as well (which then
1240// propagates to the values they in turn compute).  This reverse propagation
1241// is needed to track interesting correlations across function call boundaries,
1242// where formal arguments bind to actual arguments, etc.  This is also needed
1243// because the constraint solver sometimes simplifies certain symbolic values
1244// into constants when appropriate, and this complicates reasoning about
1245// interesting values.
1246typedef llvm::DenseSet<const Expr *> InterestingExprs;
1247
1248static void reversePropagateIntererstingSymbols(BugReport &R,
1249                                                InterestingExprs &IE,
1250                                                const ProgramState *State,
1251                                                const Expr *Ex,
1252                                                const LocationContext *LCtx) {
1253  SVal V = State->getSVal(Ex, LCtx);
1254  if (!(R.isInteresting(V) || IE.count(Ex)))
1255    return;
1256
1257  switch (Ex->getStmtClass()) {
1258    default:
1259      if (!isa<CastExpr>(Ex))
1260        break;
1261      // Fall through.
1262    case Stmt::BinaryOperatorClass:
1263    case Stmt::UnaryOperatorClass: {
1264      for (Stmt::const_child_iterator CI = Ex->child_begin(),
1265            CE = Ex->child_end();
1266            CI != CE; ++CI) {
1267        if (const Expr *child = dyn_cast_or_null<Expr>(*CI)) {
1268          IE.insert(child);
1269          SVal ChildV = State->getSVal(child, LCtx);
1270          R.markInteresting(ChildV);
1271        }
1272        break;
1273      }
1274    }
1275  }
1276
1277  R.markInteresting(V);
1278}
1279
1280static void reversePropagateInterestingSymbols(BugReport &R,
1281                                               InterestingExprs &IE,
1282                                               const ProgramState *State,
1283                                               const LocationContext *CalleeCtx,
1284                                               const LocationContext *CallerCtx)
1285{
1286  // FIXME: Handle non-CallExpr-based CallEvents.
1287  const StackFrameContext *Callee = CalleeCtx->getCurrentStackFrame();
1288  const Stmt *CallSite = Callee->getCallSite();
1289  if (const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite)) {
1290    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeCtx->getDecl())) {
1291      FunctionDecl::param_const_iterator PI = FD->param_begin(),
1292                                         PE = FD->param_end();
1293      CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
1294      for (; AI != AE && PI != PE; ++AI, ++PI) {
1295        if (const Expr *ArgE = *AI) {
1296          if (const ParmVarDecl *PD = *PI) {
1297            Loc LV = State->getLValue(PD, CalleeCtx);
1298            if (R.isInteresting(LV) || R.isInteresting(State->getRawSVal(LV)))
1299              IE.insert(ArgE);
1300          }
1301        }
1302      }
1303    }
1304  }
1305}
1306
1307//===----------------------------------------------------------------------===//
1308// Functions for determining if a loop was executed 0 times.
1309//===----------------------------------------------------------------------===//
1310
1311/// Return true if the terminator is a loop and the destination is the
1312/// false branch.
1313static bool isLoopJumpPastBody(const Stmt *Term, const BlockEdge *BE) {
1314  switch (Term->getStmtClass()) {
1315    case Stmt::ForStmtClass:
1316    case Stmt::WhileStmtClass:
1317    case Stmt::ObjCForCollectionStmtClass:
1318      break;
1319    default:
1320      // Note that we intentionally do not include do..while here.
1321      return false;
1322  }
1323
1324  // Did we take the false branch?
1325  const CFGBlock *Src = BE->getSrc();
1326  assert(Src->succ_size() == 2);
1327  return (*(Src->succ_begin()+1) == BE->getDst());
1328}
1329
1330static bool isContainedByStmt(ParentMap &PM, const Stmt *S, const Stmt *SubS) {
1331  while (SubS) {
1332    if (SubS == S)
1333      return true;
1334    SubS = PM.getParent(SubS);
1335  }
1336  return false;
1337}
1338
1339static const Stmt *getStmtBeforeCond(ParentMap &PM, const Stmt *Term,
1340                                     const ExplodedNode *N) {
1341  while (N) {
1342    Optional<StmtPoint> SP = N->getLocation().getAs<StmtPoint>();
1343    if (SP) {
1344      const Stmt *S = SP->getStmt();
1345      if (!isContainedByStmt(PM, Term, S))
1346        return S;
1347    }
1348    N = GetPredecessorNode(N);
1349  }
1350  return 0;
1351}
1352
1353static bool isInLoopBody(ParentMap &PM, const Stmt *S, const Stmt *Term) {
1354  const Stmt *LoopBody = 0;
1355  switch (Term->getStmtClass()) {
1356    case Stmt::ForStmtClass: {
1357      const ForStmt *FS = cast<ForStmt>(Term);
1358      if (isContainedByStmt(PM, FS->getInc(), S))
1359        return true;
1360      LoopBody = FS->getBody();
1361      break;
1362    }
1363    case Stmt::ObjCForCollectionStmtClass: {
1364      const ObjCForCollectionStmt *FC = cast<ObjCForCollectionStmt>(Term);
1365      LoopBody = FC->getBody();
1366      break;
1367    }
1368    case Stmt::WhileStmtClass:
1369      LoopBody = cast<WhileStmt>(Term)->getBody();
1370      break;
1371    default:
1372      return false;
1373  }
1374  return isContainedByStmt(PM, LoopBody, S);
1375}
1376
1377//===----------------------------------------------------------------------===//
1378// Top-level logic for generating extensive path diagnostics.
1379//===----------------------------------------------------------------------===//
1380
1381static bool GenerateExtensivePathDiagnostic(PathDiagnostic& PD,
1382                                            PathDiagnosticBuilder &PDB,
1383                                            const ExplodedNode *N,
1384                                      ArrayRef<BugReporterVisitor *> visitors) {
1385  EdgeBuilder EB(PD, PDB);
1386  const SourceManager& SM = PDB.getSourceManager();
1387  StackDiagVector CallStack;
1388  InterestingExprs IE;
1389
1390  const ExplodedNode *NextNode = N->pred_empty() ? NULL : *(N->pred_begin());
1391  while (NextNode) {
1392    N = NextNode;
1393    NextNode = GetPredecessorNode(N);
1394    ProgramPoint P = N->getLocation();
1395
1396    do {
1397      if (Optional<PostStmt> PS = P.getAs<PostStmt>()) {
1398        if (const Expr *Ex = PS->getStmtAs<Expr>())
1399          reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1400                                              N->getState().getPtr(), Ex,
1401                                              N->getLocationContext());
1402      }
1403
1404      if (Optional<CallExitEnd> CE = P.getAs<CallExitEnd>()) {
1405        const Stmt *S = CE->getCalleeContext()->getCallSite();
1406        if (const Expr *Ex = dyn_cast_or_null<Expr>(S)) {
1407            reversePropagateIntererstingSymbols(*PDB.getBugReport(), IE,
1408                                                N->getState().getPtr(), Ex,
1409                                                N->getLocationContext());
1410        }
1411
1412        PathDiagnosticCallPiece *C =
1413          PathDiagnosticCallPiece::construct(N, *CE, SM);
1414        GRBugReporter& BR = PDB.getBugReporter();
1415        BR.addCallPieceLocationContextPair(C, CE->getCalleeContext());
1416
1417        EB.addEdge(C->callReturn, true);
1418        EB.flushLocations();
1419
1420        PD.getActivePath().push_front(C);
1421        PD.pushActivePath(&C->path);
1422        CallStack.push_back(StackDiagPair(C, N));
1423        break;
1424      }
1425
1426      // Pop the call hierarchy if we are done walking the contents
1427      // of a function call.
1428      if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
1429        // Add an edge to the start of the function.
1430        const Decl *D = CE->getCalleeContext()->getDecl();
1431        PathDiagnosticLocation pos =
1432          PathDiagnosticLocation::createBegin(D, SM);
1433        EB.addEdge(pos);
1434
1435        // Flush all locations, and pop the active path.
1436        bool VisitedEntireCall = PD.isWithinCall();
1437        EB.flushLocations();
1438        PD.popActivePath();
1439        PDB.LC = N->getLocationContext();
1440
1441        // Either we just added a bunch of stuff to the top-level path, or
1442        // we have a previous CallExitEnd.  If the former, it means that the
1443        // path terminated within a function call.  We must then take the
1444        // current contents of the active path and place it within
1445        // a new PathDiagnosticCallPiece.
1446        PathDiagnosticCallPiece *C;
1447        if (VisitedEntireCall) {
1448          C = cast<PathDiagnosticCallPiece>(PD.getActivePath().front());
1449        } else {
1450          const Decl *Caller = CE->getLocationContext()->getDecl();
1451          C = PathDiagnosticCallPiece::construct(PD.getActivePath(), Caller);
1452          GRBugReporter& BR = PDB.getBugReporter();
1453          BR.addCallPieceLocationContextPair(C, CE->getCalleeContext());
1454        }
1455
1456        C->setCallee(*CE, SM);
1457        EB.addContext(C->getLocation());
1458
1459        if (!CallStack.empty()) {
1460          assert(CallStack.back().first == C);
1461          CallStack.pop_back();
1462        }
1463        break;
1464      }
1465
1466      // Note that is important that we update the LocationContext
1467      // after looking at CallExits.  CallExit basically adds an
1468      // edge in the *caller*, so we don't want to update the LocationContext
1469      // too soon.
1470      PDB.LC = N->getLocationContext();
1471
1472      // Block edges.
1473      if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
1474        // Does this represent entering a call?  If so, look at propagating
1475        // interesting symbols across call boundaries.
1476        if (NextNode) {
1477          const LocationContext *CallerCtx = NextNode->getLocationContext();
1478          const LocationContext *CalleeCtx = PDB.LC;
1479          if (CallerCtx != CalleeCtx) {
1480            reversePropagateInterestingSymbols(*PDB.getBugReport(), IE,
1481                                               N->getState().getPtr(),
1482                                               CalleeCtx, CallerCtx);
1483          }
1484        }
1485
1486        // Are we jumping to the head of a loop?  Add a special diagnostic.
1487        if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) {
1488          PathDiagnosticLocation L(Loop, SM, PDB.LC);
1489          const CompoundStmt *CS = NULL;
1490
1491          if (const ForStmt *FS = dyn_cast<ForStmt>(Loop))
1492            CS = dyn_cast<CompoundStmt>(FS->getBody());
1493          else if (const WhileStmt *WS = dyn_cast<WhileStmt>(Loop))
1494            CS = dyn_cast<CompoundStmt>(WS->getBody());
1495
1496          PathDiagnosticEventPiece *p =
1497            new PathDiagnosticEventPiece(L,
1498                                        "Looping back to the head of the loop");
1499          p->setPrunable(true);
1500
1501          EB.addEdge(p->getLocation(), true);
1502          PD.getActivePath().push_front(p);
1503
1504          if (CS) {
1505            PathDiagnosticLocation BL =
1506              PathDiagnosticLocation::createEndBrace(CS, SM);
1507            EB.addEdge(BL);
1508          }
1509        }
1510
1511        const CFGBlock *BSrc = BE->getSrc();
1512        ParentMap &PM = PDB.getParentMap();
1513
1514        if (const Stmt *Term = BSrc->getTerminator()) {
1515          // Are we jumping past the loop body without ever executing the
1516          // loop (because the condition was false)?
1517          if (isLoopJumpPastBody(Term, &*BE) &&
1518              !isInLoopBody(PM,
1519                            getStmtBeforeCond(PM,
1520                                              BSrc->getTerminatorCondition(),
1521                                              N),
1522                            Term)) {
1523            PathDiagnosticLocation L(Term, SM, PDB.LC);
1524            PathDiagnosticEventPiece *PE =
1525                new PathDiagnosticEventPiece(L, "Loop body executed 0 times");
1526            PE->setPrunable(true);
1527
1528            EB.addEdge(PE->getLocation(), true);
1529            PD.getActivePath().push_front(PE);
1530          }
1531
1532          // In any case, add the terminator as the current statement
1533          // context for control edges.
1534          EB.addContext(Term);
1535        }
1536
1537        break;
1538      }
1539
1540      if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
1541        Optional<CFGElement> First = BE->getFirstElement();
1542        if (Optional<CFGStmt> S = First ? First->getAs<CFGStmt>() : None) {
1543          const Stmt *stmt = S->getStmt();
1544          if (IsControlFlowExpr(stmt)) {
1545            // Add the proper context for '&&', '||', and '?'.
1546            EB.addContext(stmt);
1547          }
1548          else
1549            EB.addExtendedContext(PDB.getEnclosingStmtLocation(stmt).asStmt());
1550        }
1551
1552        break;
1553      }
1554
1555
1556    } while (0);
1557
1558    if (!NextNode)
1559      continue;
1560
1561    // Add pieces from custom visitors.
1562    BugReport *R = PDB.getBugReport();
1563    for (ArrayRef<BugReporterVisitor *>::iterator I = visitors.begin(),
1564                                                  E = visitors.end();
1565         I != E; ++I) {
1566      if (PathDiagnosticPiece *p = (*I)->VisitNode(N, NextNode, PDB, *R)) {
1567        const PathDiagnosticLocation &Loc = p->getLocation();
1568        EB.addEdge(Loc, true);
1569        PD.getActivePath().push_front(p);
1570        updateStackPiecesWithMessage(p, CallStack);
1571
1572        if (const Stmt *S = Loc.asStmt())
1573          EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt());
1574      }
1575    }
1576  }
1577
1578  return PDB.getBugReport()->isValid();
1579}
1580
1581//===----------------------------------------------------------------------===//
1582// Methods for BugType and subclasses.
1583//===----------------------------------------------------------------------===//
1584BugType::~BugType() { }
1585
1586void BugType::FlushReports(BugReporter &BR) {}
1587
1588void BuiltinBug::anchor() {}
1589
1590//===----------------------------------------------------------------------===//
1591// Methods for BugReport and subclasses.
1592//===----------------------------------------------------------------------===//
1593
1594void BugReport::NodeResolver::anchor() {}
1595
1596void BugReport::addVisitor(BugReporterVisitor* visitor) {
1597  if (!visitor)
1598    return;
1599
1600  llvm::FoldingSetNodeID ID;
1601  visitor->Profile(ID);
1602  void *InsertPos;
1603
1604  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
1605    delete visitor;
1606    return;
1607  }
1608
1609  CallbacksSet.InsertNode(visitor, InsertPos);
1610  Callbacks.push_back(visitor);
1611  ++ConfigurationChangeToken;
1612}
1613
1614BugReport::~BugReport() {
1615  for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
1616    delete *I;
1617  }
1618  while (!interestingSymbols.empty()) {
1619    popInterestingSymbolsAndRegions();
1620  }
1621}
1622
1623const Decl *BugReport::getDeclWithIssue() const {
1624  if (DeclWithIssue)
1625    return DeclWithIssue;
1626
1627  const ExplodedNode *N = getErrorNode();
1628  if (!N)
1629    return 0;
1630
1631  const LocationContext *LC = N->getLocationContext();
1632  return LC->getCurrentStackFrame()->getDecl();
1633}
1634
1635void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
1636  hash.AddPointer(&BT);
1637  hash.AddString(Description);
1638  PathDiagnosticLocation UL = getUniqueingLocation();
1639  if (UL.isValid()) {
1640    UL.Profile(hash);
1641  } else if (Location.isValid()) {
1642    Location.Profile(hash);
1643  } else {
1644    assert(ErrorNode);
1645    hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
1646  }
1647
1648  for (SmallVectorImpl<SourceRange>::const_iterator I =
1649      Ranges.begin(), E = Ranges.end(); I != E; ++I) {
1650    const SourceRange range = *I;
1651    if (!range.isValid())
1652      continue;
1653    hash.AddInteger(range.getBegin().getRawEncoding());
1654    hash.AddInteger(range.getEnd().getRawEncoding());
1655  }
1656}
1657
1658void BugReport::markInteresting(SymbolRef sym) {
1659  if (!sym)
1660    return;
1661
1662  // If the symbol wasn't already in our set, note a configuration change.
1663  if (getInterestingSymbols().insert(sym).second)
1664    ++ConfigurationChangeToken;
1665
1666  if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
1667    getInterestingRegions().insert(meta->getRegion());
1668}
1669
1670void BugReport::markInteresting(const MemRegion *R) {
1671  if (!R)
1672    return;
1673
1674  // If the base region wasn't already in our set, note a configuration change.
1675  R = R->getBaseRegion();
1676  if (getInterestingRegions().insert(R).second)
1677    ++ConfigurationChangeToken;
1678
1679  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1680    getInterestingSymbols().insert(SR->getSymbol());
1681}
1682
1683void BugReport::markInteresting(SVal V) {
1684  markInteresting(V.getAsRegion());
1685  markInteresting(V.getAsSymbol());
1686}
1687
1688void BugReport::markInteresting(const LocationContext *LC) {
1689  if (!LC)
1690    return;
1691  InterestingLocationContexts.insert(LC);
1692}
1693
1694bool BugReport::isInteresting(SVal V) {
1695  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
1696}
1697
1698bool BugReport::isInteresting(SymbolRef sym) {
1699  if (!sym)
1700    return false;
1701  // We don't currently consider metadata symbols to be interesting
1702  // even if we know their region is interesting. Is that correct behavior?
1703  return getInterestingSymbols().count(sym);
1704}
1705
1706bool BugReport::isInteresting(const MemRegion *R) {
1707  if (!R)
1708    return false;
1709  R = R->getBaseRegion();
1710  bool b = getInterestingRegions().count(R);
1711  if (b)
1712    return true;
1713  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1714    return getInterestingSymbols().count(SR->getSymbol());
1715  return false;
1716}
1717
1718bool BugReport::isInteresting(const LocationContext *LC) {
1719  if (!LC)
1720    return false;
1721  return InterestingLocationContexts.count(LC);
1722}
1723
1724void BugReport::lazyInitializeInterestingSets() {
1725  if (interestingSymbols.empty()) {
1726    interestingSymbols.push_back(new Symbols());
1727    interestingRegions.push_back(new Regions());
1728  }
1729}
1730
1731BugReport::Symbols &BugReport::getInterestingSymbols() {
1732  lazyInitializeInterestingSets();
1733  return *interestingSymbols.back();
1734}
1735
1736BugReport::Regions &BugReport::getInterestingRegions() {
1737  lazyInitializeInterestingSets();
1738  return *interestingRegions.back();
1739}
1740
1741void BugReport::pushInterestingSymbolsAndRegions() {
1742  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
1743  interestingRegions.push_back(new Regions(getInterestingRegions()));
1744}
1745
1746void BugReport::popInterestingSymbolsAndRegions() {
1747  delete interestingSymbols.back();
1748  interestingSymbols.pop_back();
1749  delete interestingRegions.back();
1750  interestingRegions.pop_back();
1751}
1752
1753const Stmt *BugReport::getStmt() const {
1754  if (!ErrorNode)
1755    return 0;
1756
1757  ProgramPoint ProgP = ErrorNode->getLocation();
1758  const Stmt *S = NULL;
1759
1760  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
1761    CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
1762    if (BE->getBlock() == &Exit)
1763      S = GetPreviousStmt(ErrorNode);
1764  }
1765  if (!S)
1766    S = GetStmt(ProgP);
1767
1768  return S;
1769}
1770
1771std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
1772BugReport::getRanges() {
1773    // If no custom ranges, add the range of the statement corresponding to
1774    // the error node.
1775    if (Ranges.empty()) {
1776      if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
1777        addRange(E->getSourceRange());
1778      else
1779        return std::make_pair(ranges_iterator(), ranges_iterator());
1780    }
1781
1782    // User-specified absence of range info.
1783    if (Ranges.size() == 1 && !Ranges.begin()->isValid())
1784      return std::make_pair(ranges_iterator(), ranges_iterator());
1785
1786    return std::make_pair(Ranges.begin(), Ranges.end());
1787}
1788
1789PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
1790  if (ErrorNode) {
1791    assert(!Location.isValid() &&
1792     "Either Location or ErrorNode should be specified but not both.");
1793
1794    if (const Stmt *S = GetCurrentOrPreviousStmt(ErrorNode)) {
1795      const LocationContext *LC = ErrorNode->getLocationContext();
1796
1797      // For member expressions, return the location of the '.' or '->'.
1798      if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
1799        return PathDiagnosticLocation::createMemberLoc(ME, SM);
1800      // For binary operators, return the location of the operator.
1801      if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
1802        return PathDiagnosticLocation::createOperatorLoc(B, SM);
1803
1804      if (ErrorNode->getLocation().getAs<PostStmtPurgeDeadSymbols>())
1805        return PathDiagnosticLocation::createEnd(S, SM, LC);
1806
1807      return PathDiagnosticLocation::createBegin(S, SM, LC);
1808    }
1809  } else {
1810    assert(Location.isValid());
1811    return Location;
1812  }
1813
1814  return PathDiagnosticLocation();
1815}
1816
1817//===----------------------------------------------------------------------===//
1818// Methods for BugReporter and subclasses.
1819//===----------------------------------------------------------------------===//
1820
1821BugReportEquivClass::~BugReportEquivClass() { }
1822GRBugReporter::~GRBugReporter() { }
1823BugReporterData::~BugReporterData() {}
1824
1825ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
1826
1827ProgramStateManager&
1828GRBugReporter::getStateManager() { return Eng.getStateManager(); }
1829
1830BugReporter::~BugReporter() {
1831  FlushReports();
1832
1833  // Free the bug reports we are tracking.
1834  typedef std::vector<BugReportEquivClass *> ContTy;
1835  for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
1836       I != E; ++I) {
1837    delete *I;
1838  }
1839}
1840
1841void BugReporter::FlushReports() {
1842  if (BugTypes.isEmpty())
1843    return;
1844
1845  // First flush the warnings for each BugType.  This may end up creating new
1846  // warnings and new BugTypes.
1847  // FIXME: Only NSErrorChecker needs BugType's FlushReports.
1848  // Turn NSErrorChecker into a proper checker and remove this.
1849  SmallVector<const BugType*, 16> bugTypes;
1850  for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
1851    bugTypes.push_back(*I);
1852  for (SmallVector<const BugType*, 16>::iterator
1853         I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
1854    const_cast<BugType*>(*I)->FlushReports(*this);
1855
1856  // We need to flush reports in deterministic order to ensure the order
1857  // of the reports is consistent between runs.
1858  typedef std::vector<BugReportEquivClass *> ContVecTy;
1859  for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end();
1860       EI != EE; ++EI){
1861    BugReportEquivClass& EQ = **EI;
1862    FlushReport(EQ);
1863  }
1864
1865  // BugReporter owns and deletes only BugTypes created implicitly through
1866  // EmitBasicReport.
1867  // FIXME: There are leaks from checkers that assume that the BugTypes they
1868  // create will be destroyed by the BugReporter.
1869  for (llvm::StringMap<BugType*>::iterator
1870         I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
1871    delete I->second;
1872
1873  // Remove all references to the BugType objects.
1874  BugTypes = F.getEmptySet();
1875}
1876
1877//===----------------------------------------------------------------------===//
1878// PathDiagnostics generation.
1879//===----------------------------------------------------------------------===//
1880
1881static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
1882                 std::pair<ExplodedNode*, unsigned> >
1883MakeReportGraph(const ExplodedGraph* G,
1884                SmallVectorImpl<const ExplodedNode*> &nodes) {
1885
1886  // Create the trimmed graph.  It will contain the shortest paths from the
1887  // error nodes to the root.  In the new graph we should only have one
1888  // error node unless there are two or more error nodes with the same minimum
1889  // path length.
1890  ExplodedGraph* GTrim;
1891  InterExplodedGraphMap* NMap;
1892
1893  llvm::DenseMap<const void*, const void*> InverseMap;
1894  llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(),
1895                                   &InverseMap);
1896
1897  // Create owning pointers for GTrim and NMap just to ensure that they are
1898  // released when this function exists.
1899  OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
1900  OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
1901
1902  // Find the (first) error node in the trimmed graph.  We just need to consult
1903  // the node map (NMap) which maps from nodes in the original graph to nodes
1904  // in the new graph.
1905
1906  std::queue<const ExplodedNode*> WS;
1907  typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
1908  IndexMapTy IndexMap;
1909
1910  for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) {
1911    const ExplodedNode *originalNode = nodes[nodeIndex];
1912    if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) {
1913      WS.push(N);
1914      IndexMap[originalNode] = nodeIndex;
1915    }
1916  }
1917
1918  assert(!WS.empty() && "No error node found in the trimmed graph.");
1919
1920  // Create a new (third!) graph with a single path.  This is the graph
1921  // that will be returned to the caller.
1922  ExplodedGraph *GNew = new ExplodedGraph();
1923
1924  // Sometimes the trimmed graph can contain a cycle.  Perform a reverse BFS
1925  // to the root node, and then construct a new graph that contains only
1926  // a single path.
1927  llvm::DenseMap<const void*,unsigned> Visited;
1928
1929  unsigned cnt = 0;
1930  const ExplodedNode *Root = 0;
1931
1932  while (!WS.empty()) {
1933    const ExplodedNode *Node = WS.front();
1934    WS.pop();
1935
1936    if (Visited.find(Node) != Visited.end())
1937      continue;
1938
1939    Visited[Node] = cnt++;
1940
1941    if (Node->pred_empty()) {
1942      Root = Node;
1943      break;
1944    }
1945
1946    for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
1947         E=Node->pred_end(); I!=E; ++I)
1948      WS.push(*I);
1949  }
1950
1951  assert(Root);
1952
1953  // Now walk from the root down the BFS path, always taking the successor
1954  // with the lowest number.
1955  ExplodedNode *Last = 0, *First = 0;
1956  NodeBackMap *BM = new NodeBackMap();
1957  unsigned NodeIndex = 0;
1958
1959  for ( const ExplodedNode *N = Root ;;) {
1960    // Lookup the number associated with the current node.
1961    llvm::DenseMap<const void*,unsigned>::iterator I = Visited.find(N);
1962    assert(I != Visited.end());
1963
1964    // Create the equivalent node in the new graph with the same state
1965    // and location.
1966    ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState());
1967
1968    // Store the mapping to the original node.
1969    llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
1970    assert(IMitr != InverseMap.end() && "No mapping to original node.");
1971    (*BM)[NewN] = (const ExplodedNode*) IMitr->second;
1972
1973    // Link up the new node with the previous node.
1974    if (Last)
1975      NewN->addPredecessor(Last, *GNew);
1976
1977    Last = NewN;
1978
1979    // Are we at the final node?
1980    IndexMapTy::iterator IMI =
1981      IndexMap.find((const ExplodedNode*)(IMitr->second));
1982    if (IMI != IndexMap.end()) {
1983      First = NewN;
1984      NodeIndex = IMI->second;
1985      break;
1986    }
1987
1988    // Find the next successor node.  We choose the node that is marked
1989    // with the lowest DFS number.
1990    ExplodedNode::const_succ_iterator SI = N->succ_begin();
1991    ExplodedNode::const_succ_iterator SE = N->succ_end();
1992    N = 0;
1993
1994    for (unsigned MinVal = 0; SI != SE; ++SI) {
1995
1996      I = Visited.find(*SI);
1997
1998      if (I == Visited.end())
1999        continue;
2000
2001      if (!N || I->second < MinVal) {
2002        N = *SI;
2003        MinVal = I->second;
2004      }
2005    }
2006
2007    assert(N);
2008  }
2009
2010  assert(First);
2011
2012  return std::make_pair(std::make_pair(GNew, BM),
2013                        std::make_pair(First, NodeIndex));
2014}
2015
2016/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2017///  and collapses PathDiagosticPieces that are expanded by macros.
2018static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2019  typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>,
2020                                SourceLocation> > MacroStackTy;
2021
2022  typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> >
2023          PiecesTy;
2024
2025  MacroStackTy MacroStack;
2026  PiecesTy Pieces;
2027
2028  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2029       I!=E; ++I) {
2030
2031    PathDiagnosticPiece *piece = I->getPtr();
2032
2033    // Recursively compact calls.
2034    if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
2035      CompactPathDiagnostic(call->path, SM);
2036    }
2037
2038    // Get the location of the PathDiagnosticPiece.
2039    const FullSourceLoc Loc = piece->getLocation().asLocation();
2040
2041    // Determine the instantiation location, which is the location we group
2042    // related PathDiagnosticPieces.
2043    SourceLocation InstantiationLoc = Loc.isMacroID() ?
2044                                      SM.getExpansionLoc(Loc) :
2045                                      SourceLocation();
2046
2047    if (Loc.isFileID()) {
2048      MacroStack.clear();
2049      Pieces.push_back(piece);
2050      continue;
2051    }
2052
2053    assert(Loc.isMacroID());
2054
2055    // Is the PathDiagnosticPiece within the same macro group?
2056    if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
2057      MacroStack.back().first->subPieces.push_back(piece);
2058      continue;
2059    }
2060
2061    // We aren't in the same group.  Are we descending into a new macro
2062    // or are part of an old one?
2063    IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup;
2064
2065    SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2066                                          SM.getExpansionLoc(Loc) :
2067                                          SourceLocation();
2068
2069    // Walk the entire macro stack.
2070    while (!MacroStack.empty()) {
2071      if (InstantiationLoc == MacroStack.back().second) {
2072        MacroGroup = MacroStack.back().first;
2073        break;
2074      }
2075
2076      if (ParentInstantiationLoc == MacroStack.back().second) {
2077        MacroGroup = MacroStack.back().first;
2078        break;
2079      }
2080
2081      MacroStack.pop_back();
2082    }
2083
2084    if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
2085      // Create a new macro group and add it to the stack.
2086      PathDiagnosticMacroPiece *NewGroup =
2087        new PathDiagnosticMacroPiece(
2088          PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2089
2090      if (MacroGroup)
2091        MacroGroup->subPieces.push_back(NewGroup);
2092      else {
2093        assert(InstantiationLoc.isFileID());
2094        Pieces.push_back(NewGroup);
2095      }
2096
2097      MacroGroup = NewGroup;
2098      MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2099    }
2100
2101    // Finally, add the PathDiagnosticPiece to the group.
2102    MacroGroup->subPieces.push_back(piece);
2103  }
2104
2105  // Now take the pieces and construct a new PathDiagnostic.
2106  path.clear();
2107
2108  for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I)
2109    path.push_back(*I);
2110}
2111
2112bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
2113                                           PathDiagnosticConsumer &PC,
2114                                           ArrayRef<BugReport *> &bugReports) {
2115  assert(!bugReports.empty());
2116
2117  bool HasValid = false;
2118  SmallVector<const ExplodedNode *, 10> errorNodes;
2119  for (ArrayRef<BugReport*>::iterator I = bugReports.begin(),
2120                                      E = bugReports.end(); I != E; ++I) {
2121    if ((*I)->isValid()) {
2122      HasValid = true;
2123      errorNodes.push_back((*I)->getErrorNode());
2124    } else {
2125      errorNodes.push_back(0);
2126    }
2127  }
2128
2129  // If all the reports have been marked invalid, we're done.
2130  if (!HasValid)
2131    return false;
2132
2133  // Construct a new graph that contains only a single path from the error
2134  // node to a root.
2135  const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
2136  std::pair<ExplodedNode*, unsigned> >&
2137    GPair = MakeReportGraph(&getGraph(), errorNodes);
2138
2139  // Find the BugReport with the original location.
2140  assert(GPair.second.second < bugReports.size());
2141  BugReport *R = bugReports[GPair.second.second];
2142  assert(R && "No original report found for sliced graph.");
2143  assert(R->isValid() && "Report selected from trimmed graph marked invalid.");
2144
2145  OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
2146  OwningPtr<NodeBackMap> BackMap(GPair.first.second);
2147  const ExplodedNode *N = GPair.second.first;
2148
2149  // Start building the path diagnostic...
2150  PathDiagnosticBuilder PDB(*this, R, BackMap.get(), &PC);
2151
2152  // Register additional node visitors.
2153  R->addVisitor(new NilReceiverBRVisitor());
2154  R->addVisitor(new ConditionBRVisitor());
2155  R->addVisitor(new LikelyFalsePositiveSuppressionBRVisitor());
2156
2157  BugReport::VisitorList visitors;
2158  unsigned originalReportConfigToken, finalReportConfigToken;
2159
2160  // While generating diagnostics, it's possible the visitors will decide
2161  // new symbols and regions are interesting, or add other visitors based on
2162  // the information they find. If they do, we need to regenerate the path
2163  // based on our new report configuration.
2164  do {
2165    // Get a clean copy of all the visitors.
2166    for (BugReport::visitor_iterator I = R->visitor_begin(),
2167                                     E = R->visitor_end(); I != E; ++I)
2168       visitors.push_back((*I)->clone());
2169
2170    // Clear out the active path from any previous work.
2171    PD.resetPath();
2172    originalReportConfigToken = R->getConfigurationChangeToken();
2173
2174    // Generate the very last diagnostic piece - the piece is visible before
2175    // the trace is expanded.
2176    PathDiagnosticPiece *LastPiece = 0;
2177    for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
2178        I != E; ++I) {
2179      if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
2180        assert (!LastPiece &&
2181            "There can only be one final piece in a diagnostic.");
2182        LastPiece = Piece;
2183      }
2184    }
2185
2186    if (PDB.getGenerationScheme() != PathDiagnosticConsumer::None) {
2187      if (!LastPiece)
2188        LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
2189      if (LastPiece)
2190        PD.setEndOfPath(LastPiece);
2191      else
2192        return false;
2193    }
2194
2195    switch (PDB.getGenerationScheme()) {
2196    case PathDiagnosticConsumer::Extensive:
2197      if (!GenerateExtensivePathDiagnostic(PD, PDB, N, visitors)) {
2198        assert(!R->isValid() && "Failed on valid report");
2199        // Try again. We'll filter out the bad report when we trim the graph.
2200        // FIXME: It would be more efficient to use the same intermediate
2201        // trimmed graph, and just repeat the shortest-path search.
2202        return generatePathDiagnostic(PD, PC, bugReports);
2203      }
2204      break;
2205    case PathDiagnosticConsumer::Minimal:
2206      if (!GenerateMinimalPathDiagnostic(PD, PDB, N, visitors)) {
2207        assert(!R->isValid() && "Failed on valid report");
2208        // Try again. We'll filter out the bad report when we trim the graph.
2209        return generatePathDiagnostic(PD, PC, bugReports);
2210      }
2211      break;
2212    case PathDiagnosticConsumer::None:
2213      if (!GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors)) {
2214        assert(!R->isValid() && "Failed on valid report");
2215        // Try again. We'll filter out the bad report when we trim the graph.
2216        return generatePathDiagnostic(PD, PC, bugReports);
2217      }
2218      break;
2219    }
2220
2221    // Clean up the visitors we used.
2222    llvm::DeleteContainerPointers(visitors);
2223
2224    // Did anything change while generating this path?
2225    finalReportConfigToken = R->getConfigurationChangeToken();
2226  } while(finalReportConfigToken != originalReportConfigToken);
2227
2228  // Finally, prune the diagnostic path of uninteresting stuff.
2229  if (!PD.path.empty()) {
2230    // Remove messages that are basically the same.
2231    removeRedundantMsgs(PD.getMutablePieces());
2232
2233    if (R->shouldPrunePath() &&
2234        getEngine().getAnalysisManager().options.shouldPrunePaths()) {
2235      bool hasSomethingInteresting = RemoveUnneededCalls(PD.getMutablePieces(),
2236                                                         R);
2237      assert(hasSomethingInteresting);
2238      (void) hasSomethingInteresting;
2239    }
2240
2241    adjustCallLocations(PD.getMutablePieces());
2242  }
2243
2244  return true;
2245}
2246
2247void BugReporter::Register(BugType *BT) {
2248  BugTypes = F.add(BugTypes, BT);
2249}
2250
2251void BugReporter::emitReport(BugReport* R) {
2252  // Compute the bug report's hash to determine its equivalence class.
2253  llvm::FoldingSetNodeID ID;
2254  R->Profile(ID);
2255
2256  // Lookup the equivance class.  If there isn't one, create it.
2257  BugType& BT = R->getBugType();
2258  Register(&BT);
2259  void *InsertPos;
2260  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
2261
2262  if (!EQ) {
2263    EQ = new BugReportEquivClass(R);
2264    EQClasses.InsertNode(EQ, InsertPos);
2265    EQClassesVector.push_back(EQ);
2266  }
2267  else
2268    EQ->AddReport(R);
2269}
2270
2271
2272//===----------------------------------------------------------------------===//
2273// Emitting reports in equivalence classes.
2274//===----------------------------------------------------------------------===//
2275
2276namespace {
2277struct FRIEC_WLItem {
2278  const ExplodedNode *N;
2279  ExplodedNode::const_succ_iterator I, E;
2280
2281  FRIEC_WLItem(const ExplodedNode *n)
2282  : N(n), I(N->succ_begin()), E(N->succ_end()) {}
2283};
2284}
2285
2286static BugReport *
2287FindReportInEquivalenceClass(BugReportEquivClass& EQ,
2288                             SmallVectorImpl<BugReport*> &bugReports) {
2289
2290  BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
2291  assert(I != E);
2292  BugType& BT = I->getBugType();
2293
2294  // If we don't need to suppress any of the nodes because they are
2295  // post-dominated by a sink, simply add all the nodes in the equivalence class
2296  // to 'Nodes'.  Any of the reports will serve as a "representative" report.
2297  if (!BT.isSuppressOnSink()) {
2298    BugReport *R = I;
2299    for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
2300      const ExplodedNode *N = I->getErrorNode();
2301      if (N) {
2302        R = I;
2303        bugReports.push_back(R);
2304      }
2305    }
2306    return R;
2307  }
2308
2309  // For bug reports that should be suppressed when all paths are post-dominated
2310  // by a sink node, iterate through the reports in the equivalence class
2311  // until we find one that isn't post-dominated (if one exists).  We use a
2312  // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
2313  // this as a recursive function, but we don't want to risk blowing out the
2314  // stack for very long paths.
2315  BugReport *exampleReport = 0;
2316
2317  for (; I != E; ++I) {
2318    const ExplodedNode *errorNode = I->getErrorNode();
2319
2320    if (!errorNode)
2321      continue;
2322    if (errorNode->isSink()) {
2323      llvm_unreachable(
2324           "BugType::isSuppressSink() should not be 'true' for sink end nodes");
2325    }
2326    // No successors?  By definition this nodes isn't post-dominated by a sink.
2327    if (errorNode->succ_empty()) {
2328      bugReports.push_back(I);
2329      if (!exampleReport)
2330        exampleReport = I;
2331      continue;
2332    }
2333
2334    // At this point we know that 'N' is not a sink and it has at least one
2335    // successor.  Use a DFS worklist to find a non-sink end-of-path node.
2336    typedef FRIEC_WLItem WLItem;
2337    typedef SmallVector<WLItem, 10> DFSWorkList;
2338    llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
2339
2340    DFSWorkList WL;
2341    WL.push_back(errorNode);
2342    Visited[errorNode] = 1;
2343
2344    while (!WL.empty()) {
2345      WLItem &WI = WL.back();
2346      assert(!WI.N->succ_empty());
2347
2348      for (; WI.I != WI.E; ++WI.I) {
2349        const ExplodedNode *Succ = *WI.I;
2350        // End-of-path node?
2351        if (Succ->succ_empty()) {
2352          // If we found an end-of-path node that is not a sink.
2353          if (!Succ->isSink()) {
2354            bugReports.push_back(I);
2355            if (!exampleReport)
2356              exampleReport = I;
2357            WL.clear();
2358            break;
2359          }
2360          // Found a sink?  Continue on to the next successor.
2361          continue;
2362        }
2363        // Mark the successor as visited.  If it hasn't been explored,
2364        // enqueue it to the DFS worklist.
2365        unsigned &mark = Visited[Succ];
2366        if (!mark) {
2367          mark = 1;
2368          WL.push_back(Succ);
2369          break;
2370        }
2371      }
2372
2373      // The worklist may have been cleared at this point.  First
2374      // check if it is empty before checking the last item.
2375      if (!WL.empty() && &WL.back() == &WI)
2376        WL.pop_back();
2377    }
2378  }
2379
2380  // ExampleReport will be NULL if all the nodes in the equivalence class
2381  // were post-dominated by sinks.
2382  return exampleReport;
2383}
2384
2385void BugReporter::FlushReport(BugReportEquivClass& EQ) {
2386  SmallVector<BugReport*, 10> bugReports;
2387  BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
2388  if (exampleReport) {
2389    const PathDiagnosticConsumers &C = getPathDiagnosticConsumers();
2390    for (PathDiagnosticConsumers::const_iterator I=C.begin(),
2391                                                 E=C.end(); I != E; ++I) {
2392      FlushReport(exampleReport, **I, bugReports);
2393    }
2394  }
2395}
2396
2397void BugReporter::FlushReport(BugReport *exampleReport,
2398                              PathDiagnosticConsumer &PD,
2399                              ArrayRef<BugReport*> bugReports) {
2400
2401  // FIXME: Make sure we use the 'R' for the path that was actually used.
2402  // Probably doesn't make a difference in practice.
2403  BugType& BT = exampleReport->getBugType();
2404
2405  OwningPtr<PathDiagnostic>
2406    D(new PathDiagnostic(exampleReport->getDeclWithIssue(),
2407                         exampleReport->getBugType().getName(),
2408                         exampleReport->getDescription(),
2409                         exampleReport->getShortDescription(/*Fallback=*/false),
2410                         BT.getCategory(),
2411                         exampleReport->getUniqueingLocation(),
2412                         exampleReport->getUniqueingDecl()));
2413
2414  MaxBugClassSize = std::max(bugReports.size(),
2415                             static_cast<size_t>(MaxBugClassSize));
2416
2417  // Generate the full path diagnostic, using the generation scheme
2418  // specified by the PathDiagnosticConsumer. Note that we have to generate
2419  // path diagnostics even for consumers which do not support paths, because
2420  // the BugReporterVisitors may mark this bug as a false positive.
2421  if (!bugReports.empty())
2422    if (!generatePathDiagnostic(*D.get(), PD, bugReports))
2423      return;
2424
2425  MaxValidBugClassSize = std::max(bugReports.size(),
2426                                  static_cast<size_t>(MaxValidBugClassSize));
2427
2428  // If the path is empty, generate a single step path with the location
2429  // of the issue.
2430  if (D->path.empty()) {
2431    PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
2432    PathDiagnosticPiece *piece =
2433      new PathDiagnosticEventPiece(L, exampleReport->getDescription());
2434    BugReport::ranges_iterator Beg, End;
2435    llvm::tie(Beg, End) = exampleReport->getRanges();
2436    for ( ; Beg != End; ++Beg)
2437      piece->addRange(*Beg);
2438    D->setEndOfPath(piece);
2439  }
2440
2441  // Get the meta data.
2442  const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
2443  for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
2444                                                e = Meta.end(); i != e; ++i) {
2445    D->addMeta(*i);
2446  }
2447
2448  PD.HandlePathDiagnostic(D.take());
2449}
2450
2451void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
2452                                  StringRef name,
2453                                  StringRef category,
2454                                  StringRef str, PathDiagnosticLocation Loc,
2455                                  SourceRange* RBeg, unsigned NumRanges) {
2456
2457  // 'BT' is owned by BugReporter.
2458  BugType *BT = getBugTypeForName(name, category);
2459  BugReport *R = new BugReport(*BT, str, Loc);
2460  R->setDeclWithIssue(DeclWithIssue);
2461  for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
2462  emitReport(R);
2463}
2464
2465BugType *BugReporter::getBugTypeForName(StringRef name,
2466                                        StringRef category) {
2467  SmallString<136> fullDesc;
2468  llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
2469  llvm::StringMapEntry<BugType *> &
2470      entry = StrBugTypes.GetOrCreateValue(fullDesc);
2471  BugType *BT = entry.getValue();
2472  if (!BT) {
2473    BT = new BugType(name, category);
2474    entry.setValue(BT);
2475  }
2476  return BT;
2477}
2478