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