BugReporter.cpp revision 3b5977e690b3d4476938a548bbd6f66c4a4a6dcd 
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
2095static void removeContextCycles(PathPieces &Path, ParentMap &PM) {
2096  for (PathPieces::iterator I = Path.begin(), E = Path.end(); I != E; ) {
2097    // Pattern match the current piece and its successor.
2098    PathDiagnosticControlFlowPiece *PieceI =
2099      dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2100
2101    if (!PieceI) {
2102      ++I;
2103      continue;
2104    }
2105
2106    const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2107    const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
2108
2109    PathPieces::iterator NextI = I; ++NextI;
2110    if (NextI == E)
2111      break;
2112
2113    PathDiagnosticControlFlowPiece *PieceNextI =
2114      dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2115
2116    if (!PieceNextI) {
2117      if (isa<PathDiagnosticEventPiece>(*NextI)) {
2118        ++NextI;
2119        if (NextI == E)
2120          break;
2121        PieceNextI = dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2122      }
2123
2124      if (!PieceNextI) {
2125        ++I;
2126        continue;
2127      }
2128    }
2129
2130    const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2131    const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
2132
2133    if (s1Start && s2Start && s1Start == s2End && s2Start == s1End) {
2134      Path.erase(I);
2135      I = Path.erase(NextI);
2136      continue;
2137    }
2138
2139    ++I;
2140  }
2141}
2142
2143/// \brief Return true if X is contained by Y.
2144static bool lexicalContains(ParentMap &PM,
2145                            const Stmt *X,
2146                            const Stmt *Y) {
2147  while (X) {
2148    if (X == Y)
2149      return true;
2150    X = PM.getParent(X);
2151  }
2152  return false;
2153}
2154
2155// Remove short edges on the same line less than 3 columns in difference.
2156static void removePunyEdges(PathPieces &path,
2157                            SourceManager &SM,
2158                            ParentMap &PM) {
2159
2160  bool erased = false;
2161
2162  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E;
2163       erased ? I : ++I) {
2164
2165    erased = false;
2166
2167    PathDiagnosticControlFlowPiece *PieceI =
2168      dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2169
2170    if (!PieceI)
2171      continue;
2172
2173    const Stmt *start = getLocStmt(PieceI->getStartLocation());
2174    const Stmt *end   = getLocStmt(PieceI->getEndLocation());
2175
2176    if (!start || !end)
2177      continue;
2178
2179    const Stmt *endParent = PM.getParent(end);
2180    if (!endParent)
2181      continue;
2182
2183    if (isConditionForTerminator(end, endParent))
2184      continue;
2185
2186    bool Invalid = false;
2187    FullSourceLoc StartL(start->getLocStart(), SM);
2188    FullSourceLoc EndL(end->getLocStart(), SM);
2189
2190    unsigned startLine = StartL.getSpellingLineNumber(&Invalid);
2191    if (Invalid)
2192      continue;
2193
2194    unsigned endLine = EndL.getSpellingLineNumber(&Invalid);
2195    if (Invalid)
2196      continue;
2197
2198    if (startLine != endLine)
2199      continue;
2200
2201    unsigned startCol = StartL.getSpellingColumnNumber(&Invalid);
2202    if (Invalid)
2203      continue;
2204
2205    unsigned endCol = EndL.getSpellingColumnNumber(&Invalid);
2206    if (Invalid)
2207      continue;
2208
2209    if (abs((int)startCol - (int)endCol) <= 2) {
2210      I = path.erase(I);
2211      erased = true;
2212      continue;
2213    }
2214  }
2215}
2216
2217static void removeIdenticalEvents(PathPieces &path) {
2218  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ++I) {
2219    PathDiagnosticEventPiece *PieceI =
2220      dyn_cast<PathDiagnosticEventPiece>(*I);
2221
2222    if (!PieceI)
2223      continue;
2224
2225    PathPieces::iterator NextI = I; ++NextI;
2226    if (NextI == E)
2227      return;
2228
2229    PathDiagnosticEventPiece *PieceNextI =
2230      dyn_cast<PathDiagnosticEventPiece>(*NextI);
2231
2232    if (!PieceNextI)
2233      continue;
2234
2235    // Erase the second piece if it has the same exact message text.
2236    if (PieceI->getString() == PieceNextI->getString()) {
2237      path.erase(NextI);
2238    }
2239  }
2240}
2241
2242static bool optimizeEdges(PathPieces &path, SourceManager &SM,
2243                          OptimizedCallsSet &OCS,
2244                          LocationContextMap &LCM) {
2245  bool hasChanges = false;
2246  const LocationContext *LC = LCM[&path];
2247  assert(LC);
2248  ParentMap &PM = LC->getParentMap();
2249
2250  for (PathPieces::iterator I = path.begin(), E = path.end(); I != E; ) {
2251    // Optimize subpaths.
2252    if (PathDiagnosticCallPiece *CallI = dyn_cast<PathDiagnosticCallPiece>(*I)){
2253      // Record the fact that a call has been optimized so we only do the
2254      // effort once.
2255      if (!OCS.count(CallI)) {
2256        while (optimizeEdges(CallI->path, SM, OCS, LCM)) {}
2257        OCS.insert(CallI);
2258      }
2259      ++I;
2260      continue;
2261    }
2262
2263    // Pattern match the current piece and its successor.
2264    PathDiagnosticControlFlowPiece *PieceI =
2265      dyn_cast<PathDiagnosticControlFlowPiece>(*I);
2266
2267    if (!PieceI) {
2268      ++I;
2269      continue;
2270    }
2271
2272    const Stmt *s1Start = getLocStmt(PieceI->getStartLocation());
2273    const Stmt *s1End   = getLocStmt(PieceI->getEndLocation());
2274    const Stmt *level1 = getStmtParent(s1Start, PM);
2275    const Stmt *level2 = getStmtParent(s1End, PM);
2276
2277    PathPieces::iterator NextI = I; ++NextI;
2278    if (NextI == E)
2279      break;
2280
2281    PathDiagnosticControlFlowPiece *PieceNextI =
2282      dyn_cast<PathDiagnosticControlFlowPiece>(*NextI);
2283
2284    if (!PieceNextI) {
2285      ++I;
2286      continue;
2287    }
2288
2289    const Stmt *s2Start = getLocStmt(PieceNextI->getStartLocation());
2290    const Stmt *s2End   = getLocStmt(PieceNextI->getEndLocation());
2291    const Stmt *level3 = getStmtParent(s2Start, PM);
2292    const Stmt *level4 = getStmtParent(s2End, PM);
2293
2294    // Rule I.
2295    //
2296    // If we have two consecutive control edges whose end/begin locations
2297    // are at the same level (e.g. statements or top-level expressions within
2298    // a compound statement, or siblings share a single ancestor expression),
2299    // then merge them if they have no interesting intermediate event.
2300    //
2301    // For example:
2302    //
2303    // (1.1 -> 1.2) -> (1.2 -> 1.3) becomes (1.1 -> 1.3) because the common
2304    // parent is '1'.  Here 'x.y.z' represents the hierarchy of statements.
2305    //
2306    // NOTE: this will be limited later in cases where we add barriers
2307    // to prevent this optimization.
2308    //
2309    if (level1 && level1 == level2 && level1 == level3 && level1 == level4) {
2310      PieceI->setEndLocation(PieceNextI->getEndLocation());
2311      path.erase(NextI);
2312      hasChanges = true;
2313      continue;
2314    }
2315
2316    // Rule II.
2317    //
2318    // Eliminate edges between subexpressions and parent expressions
2319    // when the subexpression is consumed.
2320    //
2321    // NOTE: this will be limited later in cases where we add barriers
2322    // to prevent this optimization.
2323    //
2324    if (s1End && s1End == s2Start && level2) {
2325      bool removeEdge = false;
2326      // Remove edges into the increment or initialization of a
2327      // loop that have no interleaving event.  This means that
2328      // they aren't interesting.
2329      if (isIncrementOrInitInForLoop(s1End, level2))
2330        removeEdge = true;
2331      // Next only consider edges that are not anchored on
2332      // the condition of a terminator.  This are intermediate edges
2333      // that we might want to trim.
2334      else if (!isConditionForTerminator(level2, s1End)) {
2335        // Trim edges on expressions that are consumed by
2336        // the parent expression.
2337        if (isa<Expr>(s1End) && PM.isConsumedExpr(cast<Expr>(s1End))) {
2338          removeEdge = true;
2339        }
2340        // Trim edges where a lexical containment doesn't exist.
2341        // For example:
2342        //
2343        //  X -> Y -> Z
2344        //
2345        // If 'Z' lexically contains Y (it is an ancestor) and
2346        // 'X' does not lexically contain Y (it is a descendant OR
2347        // it has no lexical relationship at all) then trim.
2348        //
2349        // This can eliminate edges where we dive into a subexpression
2350        // and then pop back out, etc.
2351        else if (s1Start && s2End &&
2352                 lexicalContains(PM, s2Start, s2End) &&
2353                 !lexicalContains(PM, s1End, s1Start)) {
2354          removeEdge = true;
2355        }
2356      }
2357
2358      if (removeEdge) {
2359        PieceI->setEndLocation(PieceNextI->getEndLocation());
2360        path.erase(NextI);
2361        hasChanges = true;
2362        continue;
2363      }
2364    }
2365
2366    // Optimize edges for ObjC fast-enumeration loops.
2367    //
2368    // (X -> collection) -> (collection -> element)
2369    //
2370    // becomes:
2371    //
2372    // (X -> element)
2373    if (s1End == s2Start) {
2374      const ObjCForCollectionStmt *FS =
2375        dyn_cast_or_null<ObjCForCollectionStmt>(level3);
2376      if (FS && FS->getCollection()->IgnoreParens() == s2Start &&
2377          s2End == FS->getElement()) {
2378        PieceI->setEndLocation(PieceNextI->getEndLocation());
2379        path.erase(NextI);
2380        hasChanges = true;
2381        continue;
2382      }
2383    }
2384
2385    // No changes at this index?  Move to the next one.
2386    ++I;
2387  }
2388
2389  if (!hasChanges) {
2390    // Adjust edges into subexpressions to make them more uniform
2391    // and aesthetically pleasing.
2392    addContextEdges(path, SM, PM, LC);
2393    // Remove "cyclical" edges that include one or more context edges.
2394    removeContextCycles(path, PM);
2395    // Hoist edges originating from branch conditions to branches
2396    // for simple branches.
2397    simplifySimpleBranches(path);
2398    // Remove any puny edges left over after primary optimization pass.
2399    removePunyEdges(path, SM, PM);
2400    // Remove identical events.
2401    removeIdenticalEvents(path);
2402  }
2403
2404  return hasChanges;
2405}
2406
2407/// Drop the very first edge in a path, which should be a function entry edge.
2408static void dropFunctionEntryEdge(PathPieces &Path,
2409                                  LocationContextMap &LCM,
2410                                  SourceManager &SM) {
2411#ifndef NDEBUG
2412  const Decl *D = LCM[&Path]->getDecl();
2413  PathDiagnosticLocation EntryLoc =
2414    PathDiagnosticLocation::createBegin(D, SM);
2415  const PathDiagnosticControlFlowPiece *FirstEdge =
2416    cast<PathDiagnosticControlFlowPiece>(Path.front());
2417  assert(FirstEdge->getStartLocation() == EntryLoc && "not an entry edge");
2418#endif
2419
2420  Path.pop_front();
2421}
2422
2423
2424//===----------------------------------------------------------------------===//
2425// Methods for BugType and subclasses.
2426//===----------------------------------------------------------------------===//
2427BugType::~BugType() { }
2428
2429void BugType::FlushReports(BugReporter &BR) {}
2430
2431void BuiltinBug::anchor() {}
2432
2433//===----------------------------------------------------------------------===//
2434// Methods for BugReport and subclasses.
2435//===----------------------------------------------------------------------===//
2436
2437void BugReport::NodeResolver::anchor() {}
2438
2439void BugReport::addVisitor(BugReporterVisitor* visitor) {
2440  if (!visitor)
2441    return;
2442
2443  llvm::FoldingSetNodeID ID;
2444  visitor->Profile(ID);
2445  void *InsertPos;
2446
2447  if (CallbacksSet.FindNodeOrInsertPos(ID, InsertPos)) {
2448    delete visitor;
2449    return;
2450  }
2451
2452  CallbacksSet.InsertNode(visitor, InsertPos);
2453  Callbacks.push_back(visitor);
2454  ++ConfigurationChangeToken;
2455}
2456
2457BugReport::~BugReport() {
2458  for (visitor_iterator I = visitor_begin(), E = visitor_end(); I != E; ++I) {
2459    delete *I;
2460  }
2461  while (!interestingSymbols.empty()) {
2462    popInterestingSymbolsAndRegions();
2463  }
2464}
2465
2466const Decl *BugReport::getDeclWithIssue() const {
2467  if (DeclWithIssue)
2468    return DeclWithIssue;
2469
2470  const ExplodedNode *N = getErrorNode();
2471  if (!N)
2472    return 0;
2473
2474  const LocationContext *LC = N->getLocationContext();
2475  return LC->getCurrentStackFrame()->getDecl();
2476}
2477
2478void BugReport::Profile(llvm::FoldingSetNodeID& hash) const {
2479  hash.AddPointer(&BT);
2480  hash.AddString(Description);
2481  PathDiagnosticLocation UL = getUniqueingLocation();
2482  if (UL.isValid()) {
2483    UL.Profile(hash);
2484  } else if (Location.isValid()) {
2485    Location.Profile(hash);
2486  } else {
2487    assert(ErrorNode);
2488    hash.AddPointer(GetCurrentOrPreviousStmt(ErrorNode));
2489  }
2490
2491  for (SmallVectorImpl<SourceRange>::const_iterator I =
2492      Ranges.begin(), E = Ranges.end(); I != E; ++I) {
2493    const SourceRange range = *I;
2494    if (!range.isValid())
2495      continue;
2496    hash.AddInteger(range.getBegin().getRawEncoding());
2497    hash.AddInteger(range.getEnd().getRawEncoding());
2498  }
2499}
2500
2501void BugReport::markInteresting(SymbolRef sym) {
2502  if (!sym)
2503    return;
2504
2505  // If the symbol wasn't already in our set, note a configuration change.
2506  if (getInterestingSymbols().insert(sym).second)
2507    ++ConfigurationChangeToken;
2508
2509  if (const SymbolMetadata *meta = dyn_cast<SymbolMetadata>(sym))
2510    getInterestingRegions().insert(meta->getRegion());
2511}
2512
2513void BugReport::markInteresting(const MemRegion *R) {
2514  if (!R)
2515    return;
2516
2517  // If the base region wasn't already in our set, note a configuration change.
2518  R = R->getBaseRegion();
2519  if (getInterestingRegions().insert(R).second)
2520    ++ConfigurationChangeToken;
2521
2522  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2523    getInterestingSymbols().insert(SR->getSymbol());
2524}
2525
2526void BugReport::markInteresting(SVal V) {
2527  markInteresting(V.getAsRegion());
2528  markInteresting(V.getAsSymbol());
2529}
2530
2531void BugReport::markInteresting(const LocationContext *LC) {
2532  if (!LC)
2533    return;
2534  InterestingLocationContexts.insert(LC);
2535}
2536
2537bool BugReport::isInteresting(SVal V) {
2538  return isInteresting(V.getAsRegion()) || isInteresting(V.getAsSymbol());
2539}
2540
2541bool BugReport::isInteresting(SymbolRef sym) {
2542  if (!sym)
2543    return false;
2544  // We don't currently consider metadata symbols to be interesting
2545  // even if we know their region is interesting. Is that correct behavior?
2546  return getInterestingSymbols().count(sym);
2547}
2548
2549bool BugReport::isInteresting(const MemRegion *R) {
2550  if (!R)
2551    return false;
2552  R = R->getBaseRegion();
2553  bool b = getInterestingRegions().count(R);
2554  if (b)
2555    return true;
2556  if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
2557    return getInterestingSymbols().count(SR->getSymbol());
2558  return false;
2559}
2560
2561bool BugReport::isInteresting(const LocationContext *LC) {
2562  if (!LC)
2563    return false;
2564  return InterestingLocationContexts.count(LC);
2565}
2566
2567void BugReport::lazyInitializeInterestingSets() {
2568  if (interestingSymbols.empty()) {
2569    interestingSymbols.push_back(new Symbols());
2570    interestingRegions.push_back(new Regions());
2571  }
2572}
2573
2574BugReport::Symbols &BugReport::getInterestingSymbols() {
2575  lazyInitializeInterestingSets();
2576  return *interestingSymbols.back();
2577}
2578
2579BugReport::Regions &BugReport::getInterestingRegions() {
2580  lazyInitializeInterestingSets();
2581  return *interestingRegions.back();
2582}
2583
2584void BugReport::pushInterestingSymbolsAndRegions() {
2585  interestingSymbols.push_back(new Symbols(getInterestingSymbols()));
2586  interestingRegions.push_back(new Regions(getInterestingRegions()));
2587}
2588
2589void BugReport::popInterestingSymbolsAndRegions() {
2590  delete interestingSymbols.back();
2591  interestingSymbols.pop_back();
2592  delete interestingRegions.back();
2593  interestingRegions.pop_back();
2594}
2595
2596const Stmt *BugReport::getStmt() const {
2597  if (!ErrorNode)
2598    return 0;
2599
2600  ProgramPoint ProgP = ErrorNode->getLocation();
2601  const Stmt *S = NULL;
2602
2603  if (Optional<BlockEntrance> BE = ProgP.getAs<BlockEntrance>()) {
2604    CFGBlock &Exit = ProgP.getLocationContext()->getCFG()->getExit();
2605    if (BE->getBlock() == &Exit)
2606      S = GetPreviousStmt(ErrorNode);
2607  }
2608  if (!S)
2609    S = PathDiagnosticLocation::getStmt(ErrorNode);
2610
2611  return S;
2612}
2613
2614std::pair<BugReport::ranges_iterator, BugReport::ranges_iterator>
2615BugReport::getRanges() {
2616    // If no custom ranges, add the range of the statement corresponding to
2617    // the error node.
2618    if (Ranges.empty()) {
2619      if (const Expr *E = dyn_cast_or_null<Expr>(getStmt()))
2620        addRange(E->getSourceRange());
2621      else
2622        return std::make_pair(ranges_iterator(), ranges_iterator());
2623    }
2624
2625    // User-specified absence of range info.
2626    if (Ranges.size() == 1 && !Ranges.begin()->isValid())
2627      return std::make_pair(ranges_iterator(), ranges_iterator());
2628
2629    return std::make_pair(Ranges.begin(), Ranges.end());
2630}
2631
2632PathDiagnosticLocation BugReport::getLocation(const SourceManager &SM) const {
2633  if (ErrorNode) {
2634    assert(!Location.isValid() &&
2635     "Either Location or ErrorNode should be specified but not both.");
2636    return PathDiagnosticLocation::createEndOfPath(ErrorNode, SM);
2637  } else {
2638    assert(Location.isValid());
2639    return Location;
2640  }
2641
2642  return PathDiagnosticLocation();
2643}
2644
2645//===----------------------------------------------------------------------===//
2646// Methods for BugReporter and subclasses.
2647//===----------------------------------------------------------------------===//
2648
2649BugReportEquivClass::~BugReportEquivClass() { }
2650GRBugReporter::~GRBugReporter() { }
2651BugReporterData::~BugReporterData() {}
2652
2653ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
2654
2655ProgramStateManager&
2656GRBugReporter::getStateManager() { return Eng.getStateManager(); }
2657
2658BugReporter::~BugReporter() {
2659  FlushReports();
2660
2661  // Free the bug reports we are tracking.
2662  typedef std::vector<BugReportEquivClass *> ContTy;
2663  for (ContTy::iterator I = EQClassesVector.begin(), E = EQClassesVector.end();
2664       I != E; ++I) {
2665    delete *I;
2666  }
2667}
2668
2669void BugReporter::FlushReports() {
2670  if (BugTypes.isEmpty())
2671    return;
2672
2673  // First flush the warnings for each BugType.  This may end up creating new
2674  // warnings and new BugTypes.
2675  // FIXME: Only NSErrorChecker needs BugType's FlushReports.
2676  // Turn NSErrorChecker into a proper checker and remove this.
2677  SmallVector<const BugType*, 16> bugTypes;
2678  for (BugTypesTy::iterator I=BugTypes.begin(), E=BugTypes.end(); I!=E; ++I)
2679    bugTypes.push_back(*I);
2680  for (SmallVector<const BugType*, 16>::iterator
2681         I = bugTypes.begin(), E = bugTypes.end(); I != E; ++I)
2682    const_cast<BugType*>(*I)->FlushReports(*this);
2683
2684  // We need to flush reports in deterministic order to ensure the order
2685  // of the reports is consistent between runs.
2686  typedef std::vector<BugReportEquivClass *> ContVecTy;
2687  for (ContVecTy::iterator EI=EQClassesVector.begin(), EE=EQClassesVector.end();
2688       EI != EE; ++EI){
2689    BugReportEquivClass& EQ = **EI;
2690    FlushReport(EQ);
2691  }
2692
2693  // BugReporter owns and deletes only BugTypes created implicitly through
2694  // EmitBasicReport.
2695  // FIXME: There are leaks from checkers that assume that the BugTypes they
2696  // create will be destroyed by the BugReporter.
2697  for (llvm::StringMap<BugType*>::iterator
2698         I = StrBugTypes.begin(), E = StrBugTypes.end(); I != E; ++I)
2699    delete I->second;
2700
2701  // Remove all references to the BugType objects.
2702  BugTypes = F.getEmptySet();
2703}
2704
2705//===----------------------------------------------------------------------===//
2706// PathDiagnostics generation.
2707//===----------------------------------------------------------------------===//
2708
2709namespace {
2710/// A wrapper around a report graph, which contains only a single path, and its
2711/// node maps.
2712class ReportGraph {
2713public:
2714  InterExplodedGraphMap BackMap;
2715  OwningPtr<ExplodedGraph> Graph;
2716  const ExplodedNode *ErrorNode;
2717  size_t Index;
2718};
2719
2720/// A wrapper around a trimmed graph and its node maps.
2721class TrimmedGraph {
2722  InterExplodedGraphMap InverseMap;
2723
2724  typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy;
2725  PriorityMapTy PriorityMap;
2726
2727  typedef std::pair<const ExplodedNode *, size_t> NodeIndexPair;
2728  SmallVector<NodeIndexPair, 32> ReportNodes;
2729
2730  OwningPtr<ExplodedGraph> G;
2731
2732  /// A helper class for sorting ExplodedNodes by priority.
2733  template <bool Descending>
2734  class PriorityCompare {
2735    const PriorityMapTy &PriorityMap;
2736
2737  public:
2738    PriorityCompare(const PriorityMapTy &M) : PriorityMap(M) {}
2739
2740    bool operator()(const ExplodedNode *LHS, const ExplodedNode *RHS) const {
2741      PriorityMapTy::const_iterator LI = PriorityMap.find(LHS);
2742      PriorityMapTy::const_iterator RI = PriorityMap.find(RHS);
2743      PriorityMapTy::const_iterator E = PriorityMap.end();
2744
2745      if (LI == E)
2746        return Descending;
2747      if (RI == E)
2748        return !Descending;
2749
2750      return Descending ? LI->second > RI->second
2751                        : LI->second < RI->second;
2752    }
2753
2754    bool operator()(const NodeIndexPair &LHS, const NodeIndexPair &RHS) const {
2755      return (*this)(LHS.first, RHS.first);
2756    }
2757  };
2758
2759public:
2760  TrimmedGraph(const ExplodedGraph *OriginalGraph,
2761               ArrayRef<const ExplodedNode *> Nodes);
2762
2763  bool popNextReportGraph(ReportGraph &GraphWrapper);
2764};
2765}
2766
2767TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
2768                           ArrayRef<const ExplodedNode *> Nodes) {
2769  // The trimmed graph is created in the body of the constructor to ensure
2770  // that the DenseMaps have been initialized already.
2771  InterExplodedGraphMap ForwardMap;
2772  G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap));
2773
2774  // Find the (first) error node in the trimmed graph.  We just need to consult
2775  // the node map which maps from nodes in the original graph to nodes
2776  // in the new graph.
2777  llvm::SmallPtrSet<const ExplodedNode *, 32> RemainingNodes;
2778
2779  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
2780    if (const ExplodedNode *NewNode = ForwardMap.lookup(Nodes[i])) {
2781      ReportNodes.push_back(std::make_pair(NewNode, i));
2782      RemainingNodes.insert(NewNode);
2783    }
2784  }
2785
2786  assert(!RemainingNodes.empty() && "No error node found in the trimmed graph");
2787
2788  // Perform a forward BFS to find all the shortest paths.
2789  std::queue<const ExplodedNode *> WS;
2790
2791  assert(G->num_roots() == 1);
2792  WS.push(*G->roots_begin());
2793  unsigned Priority = 0;
2794
2795  while (!WS.empty()) {
2796    const ExplodedNode *Node = WS.front();
2797    WS.pop();
2798
2799    PriorityMapTy::iterator PriorityEntry;
2800    bool IsNew;
2801    llvm::tie(PriorityEntry, IsNew) =
2802      PriorityMap.insert(std::make_pair(Node, Priority));
2803    ++Priority;
2804
2805    if (!IsNew) {
2806      assert(PriorityEntry->second <= Priority);
2807      continue;
2808    }
2809
2810    if (RemainingNodes.erase(Node))
2811      if (RemainingNodes.empty())
2812        break;
2813
2814    for (ExplodedNode::const_pred_iterator I = Node->succ_begin(),
2815                                           E = Node->succ_end();
2816         I != E; ++I)
2817      WS.push(*I);
2818  }
2819
2820  // Sort the error paths from longest to shortest.
2821  std::sort(ReportNodes.begin(), ReportNodes.end(),
2822            PriorityCompare<true>(PriorityMap));
2823}
2824
2825bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
2826  if (ReportNodes.empty())
2827    return false;
2828
2829  const ExplodedNode *OrigN;
2830  llvm::tie(OrigN, GraphWrapper.Index) = ReportNodes.pop_back_val();
2831  assert(PriorityMap.find(OrigN) != PriorityMap.end() &&
2832         "error node not accessible from root");
2833
2834  // Create a new graph with a single path.  This is the graph
2835  // that will be returned to the caller.
2836  ExplodedGraph *GNew = new ExplodedGraph();
2837  GraphWrapper.Graph.reset(GNew);
2838  GraphWrapper.BackMap.clear();
2839
2840  // Now walk from the error node up the BFS path, always taking the
2841  // predeccessor with the lowest number.
2842  ExplodedNode *Succ = 0;
2843  while (true) {
2844    // Create the equivalent node in the new graph with the same state
2845    // and location.
2846    ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(),
2847                                       OrigN->isSink());
2848
2849    // Store the mapping to the original node.
2850    InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
2851    assert(IMitr != InverseMap.end() && "No mapping to original node.");
2852    GraphWrapper.BackMap[NewN] = IMitr->second;
2853
2854    // Link up the new node with the previous node.
2855    if (Succ)
2856      Succ->addPredecessor(NewN, *GNew);
2857    else
2858      GraphWrapper.ErrorNode = NewN;
2859
2860    Succ = NewN;
2861
2862    // Are we at the final node?
2863    if (OrigN->pred_empty()) {
2864      GNew->addRoot(NewN);
2865      break;
2866    }
2867
2868    // Find the next predeccessor node.  We choose the node that is marked
2869    // with the lowest BFS number.
2870    OrigN = *std::min_element(OrigN->pred_begin(), OrigN->pred_end(),
2871                          PriorityCompare<false>(PriorityMap));
2872  }
2873
2874  return true;
2875}
2876
2877
2878/// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
2879///  and collapses PathDiagosticPieces that are expanded by macros.
2880static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
2881  typedef std::vector<std::pair<IntrusiveRefCntPtr<PathDiagnosticMacroPiece>,
2882                                SourceLocation> > MacroStackTy;
2883
2884  typedef std::vector<IntrusiveRefCntPtr<PathDiagnosticPiece> >
2885          PiecesTy;
2886
2887  MacroStackTy MacroStack;
2888  PiecesTy Pieces;
2889
2890  for (PathPieces::const_iterator I = path.begin(), E = path.end();
2891       I!=E; ++I) {
2892
2893    PathDiagnosticPiece *piece = I->getPtr();
2894
2895    // Recursively compact calls.
2896    if (PathDiagnosticCallPiece *call=dyn_cast<PathDiagnosticCallPiece>(piece)){
2897      CompactPathDiagnostic(call->path, SM);
2898    }
2899
2900    // Get the location of the PathDiagnosticPiece.
2901    const FullSourceLoc Loc = piece->getLocation().asLocation();
2902
2903    // Determine the instantiation location, which is the location we group
2904    // related PathDiagnosticPieces.
2905    SourceLocation InstantiationLoc = Loc.isMacroID() ?
2906                                      SM.getExpansionLoc(Loc) :
2907                                      SourceLocation();
2908
2909    if (Loc.isFileID()) {
2910      MacroStack.clear();
2911      Pieces.push_back(piece);
2912      continue;
2913    }
2914
2915    assert(Loc.isMacroID());
2916
2917    // Is the PathDiagnosticPiece within the same macro group?
2918    if (!MacroStack.empty() && InstantiationLoc == MacroStack.back().second) {
2919      MacroStack.back().first->subPieces.push_back(piece);
2920      continue;
2921    }
2922
2923    // We aren't in the same group.  Are we descending into a new macro
2924    // or are part of an old one?
2925    IntrusiveRefCntPtr<PathDiagnosticMacroPiece> MacroGroup;
2926
2927    SourceLocation ParentInstantiationLoc = InstantiationLoc.isMacroID() ?
2928                                          SM.getExpansionLoc(Loc) :
2929                                          SourceLocation();
2930
2931    // Walk the entire macro stack.
2932    while (!MacroStack.empty()) {
2933      if (InstantiationLoc == MacroStack.back().second) {
2934        MacroGroup = MacroStack.back().first;
2935        break;
2936      }
2937
2938      if (ParentInstantiationLoc == MacroStack.back().second) {
2939        MacroGroup = MacroStack.back().first;
2940        break;
2941      }
2942
2943      MacroStack.pop_back();
2944    }
2945
2946    if (!MacroGroup || ParentInstantiationLoc == MacroStack.back().second) {
2947      // Create a new macro group and add it to the stack.
2948      PathDiagnosticMacroPiece *NewGroup =
2949        new PathDiagnosticMacroPiece(
2950          PathDiagnosticLocation::createSingleLocation(piece->getLocation()));
2951
2952      if (MacroGroup)
2953        MacroGroup->subPieces.push_back(NewGroup);
2954      else {
2955        assert(InstantiationLoc.isFileID());
2956        Pieces.push_back(NewGroup);
2957      }
2958
2959      MacroGroup = NewGroup;
2960      MacroStack.push_back(std::make_pair(MacroGroup, InstantiationLoc));
2961    }
2962
2963    // Finally, add the PathDiagnosticPiece to the group.
2964    MacroGroup->subPieces.push_back(piece);
2965  }
2966
2967  // Now take the pieces and construct a new PathDiagnostic.
2968  path.clear();
2969
2970  for (PiecesTy::iterator I=Pieces.begin(), E=Pieces.end(); I!=E; ++I)
2971    path.push_back(*I);
2972}
2973
2974bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
2975                                           PathDiagnosticConsumer &PC,
2976                                           ArrayRef<BugReport *> &bugReports) {
2977  assert(!bugReports.empty());
2978
2979  bool HasValid = false;
2980  bool HasInvalid = false;
2981  SmallVector<const ExplodedNode *, 32> errorNodes;
2982  for (ArrayRef<BugReport*>::iterator I = bugReports.begin(),
2983                                      E = bugReports.end(); I != E; ++I) {
2984    if ((*I)->isValid()) {
2985      HasValid = true;
2986      errorNodes.push_back((*I)->getErrorNode());
2987    } else {
2988      // Keep the errorNodes list in sync with the bugReports list.
2989      HasInvalid = true;
2990      errorNodes.push_back(0);
2991    }
2992  }
2993
2994  // If all the reports have been marked invalid by a previous path generation,
2995  // we're done.
2996  if (!HasValid)
2997    return false;
2998
2999  typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme;
3000  PathGenerationScheme ActiveScheme = PC.getGenerationScheme();
3001
3002  if (ActiveScheme == PathDiagnosticConsumer::Extensive) {
3003    AnalyzerOptions &options = getAnalyzerOptions();
3004    if (options.getBooleanOption("path-diagnostics-alternate", false)) {
3005      ActiveScheme = PathDiagnosticConsumer::AlternateExtensive;
3006    }
3007  }
3008
3009  TrimmedGraph TrimG(&getGraph(), errorNodes);
3010  ReportGraph ErrorGraph;
3011
3012  while (TrimG.popNextReportGraph(ErrorGraph)) {
3013    // Find the BugReport with the original location.
3014    assert(ErrorGraph.Index < bugReports.size());
3015    BugReport *R = bugReports[ErrorGraph.Index];
3016    assert(R && "No original report found for sliced graph.");
3017    assert(R->isValid() && "Report selected by trimmed graph marked invalid.");
3018
3019    // Start building the path diagnostic...
3020    PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC);
3021    const ExplodedNode *N = ErrorGraph.ErrorNode;
3022
3023    // Register additional node visitors.
3024    R->addVisitor(new NilReceiverBRVisitor());
3025    R->addVisitor(new ConditionBRVisitor());
3026    R->addVisitor(new LikelyFalsePositiveSuppressionBRVisitor());
3027
3028    BugReport::VisitorList visitors;
3029    unsigned origReportConfigToken, finalReportConfigToken;
3030    LocationContextMap LCM;
3031
3032    // While generating diagnostics, it's possible the visitors will decide
3033    // new symbols and regions are interesting, or add other visitors based on
3034    // the information they find. If they do, we need to regenerate the path
3035    // based on our new report configuration.
3036    do {
3037      // Get a clean copy of all the visitors.
3038      for (BugReport::visitor_iterator I = R->visitor_begin(),
3039                                       E = R->visitor_end(); I != E; ++I)
3040        visitors.push_back((*I)->clone());
3041
3042      // Clear out the active path from any previous work.
3043      PD.resetPath();
3044      origReportConfigToken = R->getConfigurationChangeToken();
3045
3046      // Generate the very last diagnostic piece - the piece is visible before
3047      // the trace is expanded.
3048      PathDiagnosticPiece *LastPiece = 0;
3049      for (BugReport::visitor_iterator I = visitors.begin(), E = visitors.end();
3050          I != E; ++I) {
3051        if (PathDiagnosticPiece *Piece = (*I)->getEndPath(PDB, N, *R)) {
3052          assert (!LastPiece &&
3053              "There can only be one final piece in a diagnostic.");
3054          LastPiece = Piece;
3055        }
3056      }
3057
3058      if (ActiveScheme != PathDiagnosticConsumer::None) {
3059        if (!LastPiece)
3060          LastPiece = BugReporterVisitor::getDefaultEndPath(PDB, N, *R);
3061        assert(LastPiece);
3062        PD.setEndOfPath(LastPiece);
3063      }
3064
3065      // Make sure we get a clean location context map so we don't
3066      // hold onto old mappings.
3067      LCM.clear();
3068
3069      switch (ActiveScheme) {
3070      case PathDiagnosticConsumer::AlternateExtensive:
3071        GenerateAlternateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3072        break;
3073      case PathDiagnosticConsumer::Extensive:
3074        GenerateExtensivePathDiagnostic(PD, PDB, N, LCM, visitors);
3075        break;
3076      case PathDiagnosticConsumer::Minimal:
3077        GenerateMinimalPathDiagnostic(PD, PDB, N, LCM, visitors);
3078        break;
3079      case PathDiagnosticConsumer::None:
3080        GenerateVisitorsOnlyPathDiagnostic(PD, PDB, N, visitors);
3081        break;
3082      }
3083
3084      // Clean up the visitors we used.
3085      llvm::DeleteContainerPointers(visitors);
3086
3087      // Did anything change while generating this path?
3088      finalReportConfigToken = R->getConfigurationChangeToken();
3089    } while (finalReportConfigToken != origReportConfigToken);
3090
3091    if (!R->isValid())
3092      continue;
3093
3094    // Finally, prune the diagnostic path of uninteresting stuff.
3095    if (!PD.path.empty()) {
3096      // Remove messages that are basically the same.
3097      removeRedundantMsgs(PD.getMutablePieces());
3098
3099      if (R->shouldPrunePath() && getAnalyzerOptions().shouldPrunePaths()) {
3100        bool stillHasNotes = removeUnneededCalls(PD.getMutablePieces(), R, LCM);
3101        assert(stillHasNotes);
3102        (void)stillHasNotes;
3103      }
3104
3105      adjustCallLocations(PD.getMutablePieces());
3106
3107      if (ActiveScheme == PathDiagnosticConsumer::AlternateExtensive) {
3108        SourceManager &SM = getSourceManager();
3109
3110        // Reduce the number of edges from a very conservative set
3111        // to an aesthetically pleasing subset that conveys the
3112        // necessary information.
3113        OptimizedCallsSet OCS;
3114        while (optimizeEdges(PD.getMutablePieces(), SM, OCS, LCM)) {}
3115
3116        // Drop the very first function-entry edge. It's not really necessary
3117        // for top-level functions.
3118        dropFunctionEntryEdge(PD.getMutablePieces(), LCM, SM);
3119      }
3120    }
3121
3122    // We found a report and didn't suppress it.
3123    return true;
3124  }
3125
3126  // We suppressed all the reports in this equivalence class.
3127  assert(!HasInvalid && "Inconsistent suppression");
3128  (void)HasInvalid;
3129  return false;
3130}
3131
3132void BugReporter::Register(BugType *BT) {
3133  BugTypes = F.add(BugTypes, BT);
3134}
3135
3136void BugReporter::emitReport(BugReport* R) {
3137  // Compute the bug report's hash to determine its equivalence class.
3138  llvm::FoldingSetNodeID ID;
3139  R->Profile(ID);
3140
3141  // Lookup the equivance class.  If there isn't one, create it.
3142  BugType& BT = R->getBugType();
3143  Register(&BT);
3144  void *InsertPos;
3145  BugReportEquivClass* EQ = EQClasses.FindNodeOrInsertPos(ID, InsertPos);
3146
3147  if (!EQ) {
3148    EQ = new BugReportEquivClass(R);
3149    EQClasses.InsertNode(EQ, InsertPos);
3150    EQClassesVector.push_back(EQ);
3151  }
3152  else
3153    EQ->AddReport(R);
3154}
3155
3156
3157//===----------------------------------------------------------------------===//
3158// Emitting reports in equivalence classes.
3159//===----------------------------------------------------------------------===//
3160
3161namespace {
3162struct FRIEC_WLItem {
3163  const ExplodedNode *N;
3164  ExplodedNode::const_succ_iterator I, E;
3165
3166  FRIEC_WLItem(const ExplodedNode *n)
3167  : N(n), I(N->succ_begin()), E(N->succ_end()) {}
3168};
3169}
3170
3171static BugReport *
3172FindReportInEquivalenceClass(BugReportEquivClass& EQ,
3173                             SmallVectorImpl<BugReport*> &bugReports) {
3174
3175  BugReportEquivClass::iterator I = EQ.begin(), E = EQ.end();
3176  assert(I != E);
3177  BugType& BT = I->getBugType();
3178
3179  // If we don't need to suppress any of the nodes because they are
3180  // post-dominated by a sink, simply add all the nodes in the equivalence class
3181  // to 'Nodes'.  Any of the reports will serve as a "representative" report.
3182  if (!BT.isSuppressOnSink()) {
3183    BugReport *R = I;
3184    for (BugReportEquivClass::iterator I=EQ.begin(), E=EQ.end(); I!=E; ++I) {
3185      const ExplodedNode *N = I->getErrorNode();
3186      if (N) {
3187        R = I;
3188        bugReports.push_back(R);
3189      }
3190    }
3191    return R;
3192  }
3193
3194  // For bug reports that should be suppressed when all paths are post-dominated
3195  // by a sink node, iterate through the reports in the equivalence class
3196  // until we find one that isn't post-dominated (if one exists).  We use a
3197  // DFS traversal of the ExplodedGraph to find a non-sink node.  We could write
3198  // this as a recursive function, but we don't want to risk blowing out the
3199  // stack for very long paths.
3200  BugReport *exampleReport = 0;
3201
3202  for (; I != E; ++I) {
3203    const ExplodedNode *errorNode = I->getErrorNode();
3204
3205    if (!errorNode)
3206      continue;
3207    if (errorNode->isSink()) {
3208      llvm_unreachable(
3209           "BugType::isSuppressSink() should not be 'true' for sink end nodes");
3210    }
3211    // No successors?  By definition this nodes isn't post-dominated by a sink.
3212    if (errorNode->succ_empty()) {
3213      bugReports.push_back(I);
3214      if (!exampleReport)
3215        exampleReport = I;
3216      continue;
3217    }
3218
3219    // At this point we know that 'N' is not a sink and it has at least one
3220    // successor.  Use a DFS worklist to find a non-sink end-of-path node.
3221    typedef FRIEC_WLItem WLItem;
3222    typedef SmallVector<WLItem, 10> DFSWorkList;
3223    llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
3224
3225    DFSWorkList WL;
3226    WL.push_back(errorNode);
3227    Visited[errorNode] = 1;
3228
3229    while (!WL.empty()) {
3230      WLItem &WI = WL.back();
3231      assert(!WI.N->succ_empty());
3232
3233      for (; WI.I != WI.E; ++WI.I) {
3234        const ExplodedNode *Succ = *WI.I;
3235        // End-of-path node?
3236        if (Succ->succ_empty()) {
3237          // If we found an end-of-path node that is not a sink.
3238          if (!Succ->isSink()) {
3239            bugReports.push_back(I);
3240            if (!exampleReport)
3241              exampleReport = I;
3242            WL.clear();
3243            break;
3244          }
3245          // Found a sink?  Continue on to the next successor.
3246          continue;
3247        }
3248        // Mark the successor as visited.  If it hasn't been explored,
3249        // enqueue it to the DFS worklist.
3250        unsigned &mark = Visited[Succ];
3251        if (!mark) {
3252          mark = 1;
3253          WL.push_back(Succ);
3254          break;
3255        }
3256      }
3257
3258      // The worklist may have been cleared at this point.  First
3259      // check if it is empty before checking the last item.
3260      if (!WL.empty() && &WL.back() == &WI)
3261        WL.pop_back();
3262    }
3263  }
3264
3265  // ExampleReport will be NULL if all the nodes in the equivalence class
3266  // were post-dominated by sinks.
3267  return exampleReport;
3268}
3269
3270void BugReporter::FlushReport(BugReportEquivClass& EQ) {
3271  SmallVector<BugReport*, 10> bugReports;
3272  BugReport *exampleReport = FindReportInEquivalenceClass(EQ, bugReports);
3273  if (exampleReport) {
3274    const PathDiagnosticConsumers &C = getPathDiagnosticConsumers();
3275    for (PathDiagnosticConsumers::const_iterator I=C.begin(),
3276                                                 E=C.end(); I != E; ++I) {
3277      FlushReport(exampleReport, **I, bugReports);
3278    }
3279  }
3280}
3281
3282void BugReporter::FlushReport(BugReport *exampleReport,
3283                              PathDiagnosticConsumer &PD,
3284                              ArrayRef<BugReport*> bugReports) {
3285
3286  // FIXME: Make sure we use the 'R' for the path that was actually used.
3287  // Probably doesn't make a difference in practice.
3288  BugType& BT = exampleReport->getBugType();
3289
3290  OwningPtr<PathDiagnostic>
3291    D(new PathDiagnostic(exampleReport->getDeclWithIssue(),
3292                         exampleReport->getBugType().getName(),
3293                         exampleReport->getDescription(),
3294                         exampleReport->getShortDescription(/*Fallback=*/false),
3295                         BT.getCategory(),
3296                         exampleReport->getUniqueingLocation(),
3297                         exampleReport->getUniqueingDecl()));
3298
3299  MaxBugClassSize = std::max(bugReports.size(),
3300                             static_cast<size_t>(MaxBugClassSize));
3301
3302  // Generate the full path diagnostic, using the generation scheme
3303  // specified by the PathDiagnosticConsumer. Note that we have to generate
3304  // path diagnostics even for consumers which do not support paths, because
3305  // the BugReporterVisitors may mark this bug as a false positive.
3306  if (!bugReports.empty())
3307    if (!generatePathDiagnostic(*D.get(), PD, bugReports))
3308      return;
3309
3310  MaxValidBugClassSize = std::max(bugReports.size(),
3311                                  static_cast<size_t>(MaxValidBugClassSize));
3312
3313  // Examine the report and see if the last piece is in a header. Reset the
3314  // report location to the last piece in the main source file.
3315  AnalyzerOptions& Opts = getAnalyzerOptions();
3316  if (Opts.shouldReportIssuesInMainSourceFile() && !Opts.AnalyzeAll)
3317    D->resetDiagnosticLocationToMainFile();
3318
3319  // If the path is empty, generate a single step path with the location
3320  // of the issue.
3321  if (D->path.empty()) {
3322    PathDiagnosticLocation L = exampleReport->getLocation(getSourceManager());
3323    PathDiagnosticPiece *piece =
3324      new PathDiagnosticEventPiece(L, exampleReport->getDescription());
3325    BugReport::ranges_iterator Beg, End;
3326    llvm::tie(Beg, End) = exampleReport->getRanges();
3327    for ( ; Beg != End; ++Beg)
3328      piece->addRange(*Beg);
3329    D->setEndOfPath(piece);
3330  }
3331
3332  // Get the meta data.
3333  const BugReport::ExtraTextList &Meta = exampleReport->getExtraText();
3334  for (BugReport::ExtraTextList::const_iterator i = Meta.begin(),
3335                                                e = Meta.end(); i != e; ++i) {
3336    D->addMeta(*i);
3337  }
3338
3339  PD.HandlePathDiagnostic(D.take());
3340}
3341
3342void BugReporter::EmitBasicReport(const Decl *DeclWithIssue,
3343                                  StringRef name,
3344                                  StringRef category,
3345                                  StringRef str, PathDiagnosticLocation Loc,
3346                                  SourceRange* RBeg, unsigned NumRanges) {
3347
3348  // 'BT' is owned by BugReporter.
3349  BugType *BT = getBugTypeForName(name, category);
3350  BugReport *R = new BugReport(*BT, str, Loc);
3351  R->setDeclWithIssue(DeclWithIssue);
3352  for ( ; NumRanges > 0 ; --NumRanges, ++RBeg) R->addRange(*RBeg);
3353  emitReport(R);
3354}
3355
3356BugType *BugReporter::getBugTypeForName(StringRef name,
3357                                        StringRef category) {
3358  SmallString<136> fullDesc;
3359  llvm::raw_svector_ostream(fullDesc) << name << ":" << category;
3360  llvm::StringMapEntry<BugType *> &
3361      entry = StrBugTypes.GetOrCreateValue(fullDesc);
3362  BugType *BT = entry.getValue();
3363  if (!BT) {
3364    BT = new BugType(name, category);
3365    entry.setValue(BT);
3366  }
3367  return BT;
3368}
3369