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