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