PathDiagnostic.cpp revision b4b4523cc52bebc5ed47cc501959ab31286a1065 
1//===--- PathDiagnostic.cpp - Path-Specific Diagnostic Handling -*- 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 the PathDiagnostic-related interfaces.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
15#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
16#include "clang/Basic/SourceManager.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/Decl.h"
19#include "clang/AST/DeclCXX.h"
20#include "clang/AST/DeclObjC.h"
21#include "clang/AST/ParentMap.h"
22#include "clang/AST/StmtCXX.h"
23#include "llvm/ADT/SmallString.h"
24
25using namespace clang;
26using namespace ento;
27
28bool PathDiagnosticMacroPiece::containsEvent() const {
29  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
30       I!=E; ++I) {
31    if (isa<PathDiagnosticEventPiece>(*I))
32      return true;
33    if (PathDiagnosticMacroPiece *MP = dyn_cast<PathDiagnosticMacroPiece>(*I))
34      if (MP->containsEvent())
35        return true;
36  }
37  return false;
38}
39
40static StringRef StripTrailingDots(StringRef s) {
41  for (StringRef::size_type i = s.size(); i != 0; --i)
42    if (s[i - 1] != '.')
43      return s.substr(0, i);
44  return "";
45}
46
47PathDiagnosticPiece::PathDiagnosticPiece(StringRef s,
48                                         Kind k, DisplayHint hint)
49  : str(StripTrailingDots(s)), kind(k), Hint(hint) {}
50
51PathDiagnosticPiece::PathDiagnosticPiece(Kind k, DisplayHint hint)
52  : kind(k), Hint(hint) {}
53
54PathDiagnosticPiece::~PathDiagnosticPiece() {}
55PathDiagnosticEventPiece::~PathDiagnosticEventPiece() {}
56PathDiagnosticCallPiece::~PathDiagnosticCallPiece() {}
57PathDiagnosticControlFlowPiece::~PathDiagnosticControlFlowPiece() {}
58PathDiagnosticMacroPiece::~PathDiagnosticMacroPiece() {}
59
60
61PathPieces::~PathPieces() {}
62
63void PathPieces::flattenTo(PathPieces &Primary, PathPieces &Current,
64                           bool ShouldFlattenMacros) const {
65  for (PathPieces::const_iterator I = begin(), E = end(); I != E; ++I) {
66    PathDiagnosticPiece *Piece = I->getPtr();
67
68    switch (Piece->getKind()) {
69    case PathDiagnosticPiece::Call: {
70      PathDiagnosticCallPiece *Call = cast<PathDiagnosticCallPiece>(Piece);
71      IntrusiveRefCntPtr<PathDiagnosticEventPiece> CallEnter =
72        Call->getCallEnterEvent();
73      if (CallEnter)
74        Current.push_back(CallEnter);
75      Call->path.flattenTo(Primary, Primary, ShouldFlattenMacros);
76      IntrusiveRefCntPtr<PathDiagnosticEventPiece> callExit =
77        Call->getCallExitEvent();
78      if (callExit)
79        Current.push_back(callExit);
80      break;
81    }
82    case PathDiagnosticPiece::Macro: {
83      PathDiagnosticMacroPiece *Macro = cast<PathDiagnosticMacroPiece>(Piece);
84      if (ShouldFlattenMacros) {
85        Macro->subPieces.flattenTo(Primary, Primary, ShouldFlattenMacros);
86      } else {
87        Current.push_back(Piece);
88        PathPieces NewPath;
89        Macro->subPieces.flattenTo(Primary, NewPath, ShouldFlattenMacros);
90        // FIXME: This probably shouldn't mutate the original path piece.
91        Macro->subPieces = NewPath;
92      }
93      break;
94    }
95    case PathDiagnosticPiece::Event:
96    case PathDiagnosticPiece::ControlFlow:
97      Current.push_back(Piece);
98      break;
99    }
100  }
101}
102
103
104PathDiagnostic::~PathDiagnostic() {}
105
106PathDiagnostic::PathDiagnostic(const Decl *declWithIssue,
107                               StringRef bugtype, StringRef verboseDesc,
108                               StringRef shortDesc, StringRef category)
109  : DeclWithIssue(declWithIssue),
110    BugType(StripTrailingDots(bugtype)),
111    VerboseDesc(StripTrailingDots(verboseDesc)),
112    ShortDesc(StripTrailingDots(shortDesc)),
113    Category(StripTrailingDots(category)),
114    path(pathImpl) {}
115
116void PathDiagnosticConsumer::anchor() { }
117
118PathDiagnosticConsumer::~PathDiagnosticConsumer() {
119  // Delete the contents of the FoldingSet if it isn't empty already.
120  for (llvm::FoldingSet<PathDiagnostic>::iterator it =
121       Diags.begin(), et = Diags.end() ; it != et ; ++it) {
122    delete &*it;
123  }
124}
125
126void PathDiagnosticConsumer::HandlePathDiagnostic(PathDiagnostic *D) {
127  llvm::OwningPtr<PathDiagnostic> OwningD(D);
128
129  if (!D || D->path.empty())
130    return;
131
132  // We need to flatten the locations (convert Stmt* to locations) because
133  // the referenced statements may be freed by the time the diagnostics
134  // are emitted.
135  D->flattenLocations();
136
137  // If the PathDiagnosticConsumer does not support diagnostics that
138  // cross file boundaries, prune out such diagnostics now.
139  if (!supportsCrossFileDiagnostics()) {
140    // Verify that the entire path is from the same FileID.
141    FileID FID;
142    const SourceManager &SMgr = (*D->path.begin())->getLocation().getManager();
143    llvm::SmallVector<const PathPieces *, 5> WorkList;
144    WorkList.push_back(&D->path);
145
146    while (!WorkList.empty()) {
147      const PathPieces &path = *WorkList.back();
148      WorkList.pop_back();
149
150      for (PathPieces::const_iterator I = path.begin(), E = path.end();
151           I != E; ++I) {
152        const PathDiagnosticPiece *piece = I->getPtr();
153        FullSourceLoc L = piece->getLocation().asLocation().getExpansionLoc();
154
155        if (FID.isInvalid()) {
156          FID = SMgr.getFileID(L);
157        } else if (SMgr.getFileID(L) != FID)
158          return; // FIXME: Emit a warning?
159
160        // Check the source ranges.
161        ArrayRef<SourceRange> Ranges = piece->getRanges();
162        for (ArrayRef<SourceRange>::iterator I = Ranges.begin(),
163                                             E = Ranges.end(); I != E; ++I) {
164          SourceLocation L = SMgr.getExpansionLoc(I->getBegin());
165          if (!L.isFileID() || SMgr.getFileID(L) != FID)
166            return; // FIXME: Emit a warning?
167          L = SMgr.getExpansionLoc(I->getEnd());
168          if (!L.isFileID() || SMgr.getFileID(L) != FID)
169            return; // FIXME: Emit a warning?
170        }
171
172        if (const PathDiagnosticCallPiece *call =
173            dyn_cast<PathDiagnosticCallPiece>(piece)) {
174          WorkList.push_back(&call->path);
175        }
176        else if (const PathDiagnosticMacroPiece *macro =
177                 dyn_cast<PathDiagnosticMacroPiece>(piece)) {
178          WorkList.push_back(&macro->subPieces);
179        }
180      }
181    }
182
183    if (FID.isInvalid())
184      return; // FIXME: Emit a warning?
185  }
186
187  // Profile the node to see if we already have something matching it
188  llvm::FoldingSetNodeID profile;
189  D->Profile(profile);
190  void *InsertPos = 0;
191
192  if (PathDiagnostic *orig = Diags.FindNodeOrInsertPos(profile, InsertPos)) {
193    // Keep the PathDiagnostic with the shorter path.
194    // Note, the enclosing routine is called in deterministic order, so the
195    // results will be consistent between runs (no reason to break ties if the
196    // size is the same).
197    const unsigned orig_size = orig->full_size();
198    const unsigned new_size = D->full_size();
199    if (orig_size <= new_size)
200      return;
201
202    Diags.RemoveNode(orig);
203    delete orig;
204  }
205
206  Diags.InsertNode(OwningD.take());
207}
208
209
210namespace {
211
212static llvm::Optional<bool> comparePiece(PathDiagnosticPiece &X,
213                                         PathDiagnosticPiece &Y) {
214  PathDiagnosticPiece::Kind XK = X.getKind(), YK = Y.getKind();
215  if (XK != YK) {
216    return XK < YK;
217  }
218  FullSourceLoc XL = X.getLocation().asLocation();
219  FullSourceLoc YL = Y.getLocation().asLocation();
220  if (XL < YL)
221    return true;
222  if (YL < XL)
223    return false;
224  const std::string &XS = X.getString();
225  const std::string &YS = Y.getString();
226  if (XS != YS)
227    return XS < YS;
228  return llvm::Optional<bool>();
229}
230
231static bool comparePathPieces(const PathPieces &X, const PathPieces &Y) {
232  if (X.size() < Y.size())
233    return true;
234  if (X.size() > Y.size())
235    return false;
236  // Compare individual parts of the path.
237  assert(X.size() == Y.size());
238  for (unsigned i = 0, n = X.size(); i < n; ++i) {
239    llvm::Optional<bool> B = comparePiece(*X[i], *Y[i]);
240    if (B.hasValue())
241      return B.getValue();
242  }
243  return false;
244}
245
246struct CompareDiagnostics {
247  // Compare if 'X' is "<" than 'Y'.
248  bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
249    // First compare by location
250    const FullSourceLoc &XLoc = X->getLocation().asLocation();
251    const FullSourceLoc &YLoc = Y->getLocation().asLocation();
252    if (XLoc < YLoc)
253      return true;
254    if (YLoc < XLoc)
255      return false;
256
257    // Next, compare by bug type.
258    StringRef XBugType = X->getBugType();
259    StringRef YBugType = Y->getBugType();
260    if (XBugType < YBugType)
261      return true;
262    if (XBugType != YBugType)
263      return false;
264
265    // Next, compare by bug description.
266    StringRef XDesc = X->getVerboseDescription();
267    StringRef YDesc = Y->getVerboseDescription();
268    if (XDesc < YDesc)
269      return true;
270    if (XDesc != YDesc)
271      return false;
272
273    // Fall back to comparing path pieces.
274    return comparePathPieces(X->path, Y->path);
275  }
276};
277}
278
279void PathDiagnosticConsumer::FlushDiagnostics(
280                                     PathDiagnosticConsumer::FilesMade *Files) {
281  if (flushed)
282    return;
283
284  flushed = true;
285
286  std::vector<const PathDiagnostic *> BatchDiags;
287  for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(),
288       et = Diags.end(); it != et; ++it) {
289    BatchDiags.push_back(&*it);
290  }
291
292  // Clear out the FoldingSet.
293  Diags.clear();
294
295  // Sort the diagnostics so that they are always emitted in a deterministic
296  // order.
297  if (!BatchDiags.empty())
298    std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics());
299
300  FlushDiagnosticsImpl(BatchDiags, Files);
301
302  // Delete the flushed diagnostics.
303  for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(),
304       et = BatchDiags.end(); it != et; ++it) {
305    const PathDiagnostic *D = *it;
306    delete D;
307  }
308}
309
310void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,
311                                                      StringRef ConsumerName,
312                                                      StringRef FileName) {
313  llvm::FoldingSetNodeID NodeID;
314  NodeID.Add(PD);
315  void *InsertPos;
316  PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
317  if (!Entry) {
318    Entry = Alloc.Allocate<PDFileEntry>();
319    Entry = new (Entry) PDFileEntry(NodeID);
320    InsertNode(Entry, InsertPos);
321  }
322
323  // Allocate persistent storage for the file name.
324  char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);
325  memcpy(FileName_cstr, FileName.data(), FileName.size());
326
327  Entry->files.push_back(std::make_pair(ConsumerName,
328                                        StringRef(FileName_cstr,
329                                                  FileName.size())));
330}
331
332PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *
333PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {
334  llvm::FoldingSetNodeID NodeID;
335  NodeID.Add(PD);
336  void *InsertPos;
337  PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
338  if (!Entry)
339    return 0;
340  return &Entry->files;
341}
342
343//===----------------------------------------------------------------------===//
344// PathDiagnosticLocation methods.
345//===----------------------------------------------------------------------===//
346
347static SourceLocation getValidSourceLocation(const Stmt* S,
348                                             LocationOrAnalysisDeclContext LAC,
349                                             bool UseEnd = false) {
350  SourceLocation L = UseEnd ? S->getLocEnd() : S->getLocStart();
351  assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
352                          "be passed to PathDiagnosticLocation upon creation.");
353
354  // S might be a temporary statement that does not have a location in the
355  // source code, so find an enclosing statement and use its location.
356  if (!L.isValid()) {
357
358    AnalysisDeclContext *ADC;
359    if (LAC.is<const LocationContext*>())
360      ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();
361    else
362      ADC = LAC.get<AnalysisDeclContext*>();
363
364    ParentMap &PM = ADC->getParentMap();
365
366    const Stmt *Parent = S;
367    do {
368      Parent = PM.getParent(Parent);
369
370      // In rare cases, we have implicit top-level expressions,
371      // such as arguments for implicit member initializers.
372      // In this case, fall back to the start of the body (even if we were
373      // asked for the statement end location).
374      if (!Parent) {
375        const Stmt *Body = ADC->getBody();
376        if (Body)
377          L = Body->getLocStart();
378        else
379          L = ADC->getDecl()->getLocEnd();
380        break;
381      }
382
383      L = UseEnd ? Parent->getLocEnd() : Parent->getLocStart();
384    } while (!L.isValid());
385  }
386
387  return L;
388}
389
390static PathDiagnosticLocation
391getLocationForCaller(const StackFrameContext *SFC,
392                     const LocationContext *CallerCtx,
393                     const SourceManager &SM) {
394  const CFGBlock &Block = *SFC->getCallSiteBlock();
395  CFGElement Source = Block[SFC->getIndex()];
396
397  switch (Source.getKind()) {
398  case CFGElement::Invalid:
399    llvm_unreachable("Invalid CFGElement");
400  case CFGElement::Statement:
401    return PathDiagnosticLocation(cast<CFGStmt>(Source).getStmt(),
402                                  SM, CallerCtx);
403  case CFGElement::Initializer: {
404    const CFGInitializer &Init = cast<CFGInitializer>(Source);
405    return PathDiagnosticLocation(Init.getInitializer()->getInit(),
406                                  SM, CallerCtx);
407  }
408  case CFGElement::AutomaticObjectDtor: {
409    const CFGAutomaticObjDtor &Dtor = cast<CFGAutomaticObjDtor>(Source);
410    return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),
411                                             SM, CallerCtx);
412  }
413  case CFGElement::BaseDtor:
414  case CFGElement::MemberDtor: {
415    const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
416    if (const Stmt *CallerBody = CallerInfo->getBody())
417      return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
418    return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
419  }
420  case CFGElement::TemporaryDtor:
421    llvm_unreachable("not yet implemented!");
422  }
423
424  llvm_unreachable("Unknown CFGElement kind");
425}
426
427
428PathDiagnosticLocation
429  PathDiagnosticLocation::createBegin(const Decl *D,
430                                      const SourceManager &SM) {
431  return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
432}
433
434PathDiagnosticLocation
435  PathDiagnosticLocation::createBegin(const Stmt *S,
436                                      const SourceManager &SM,
437                                      LocationOrAnalysisDeclContext LAC) {
438  return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
439                                SM, SingleLocK);
440}
441
442
443PathDiagnosticLocation
444PathDiagnosticLocation::createEnd(const Stmt *S,
445                                  const SourceManager &SM,
446                                  LocationOrAnalysisDeclContext LAC) {
447  if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(S))
448    return createEndBrace(CS, SM);
449  return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
450                                SM, SingleLocK);
451}
452
453PathDiagnosticLocation
454  PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
455                                            const SourceManager &SM) {
456  return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
457}
458
459PathDiagnosticLocation
460  PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
461                                          const SourceManager &SM) {
462  return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
463}
464
465PathDiagnosticLocation
466  PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
467                                           const SourceManager &SM) {
468  SourceLocation L = CS->getLBracLoc();
469  return PathDiagnosticLocation(L, SM, SingleLocK);
470}
471
472PathDiagnosticLocation
473  PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
474                                         const SourceManager &SM) {
475  SourceLocation L = CS->getRBracLoc();
476  return PathDiagnosticLocation(L, SM, SingleLocK);
477}
478
479PathDiagnosticLocation
480  PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
481                                          const SourceManager &SM) {
482  // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
483  if (const CompoundStmt *CS =
484        dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
485    if (!CS->body_empty()) {
486      SourceLocation Loc = (*CS->body_begin())->getLocStart();
487      return PathDiagnosticLocation(Loc, SM, SingleLocK);
488    }
489
490  return PathDiagnosticLocation();
491}
492
493PathDiagnosticLocation
494  PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
495                                        const SourceManager &SM) {
496  SourceLocation L = LC->getDecl()->getBodyRBrace();
497  return PathDiagnosticLocation(L, SM, SingleLocK);
498}
499
500PathDiagnosticLocation
501  PathDiagnosticLocation::create(const ProgramPoint& P,
502                                 const SourceManager &SMng) {
503
504  const Stmt* S = 0;
505  if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
506    const CFGBlock *BSrc = BE->getSrc();
507    S = BSrc->getTerminatorCondition();
508  }
509  else if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) {
510    S = PS->getStmt();
511  }
512  else if (const PostImplicitCall *PIE = dyn_cast<PostImplicitCall>(&P)) {
513    return PathDiagnosticLocation(PIE->getLocation(), SMng);
514  }
515  else if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) {
516    return getLocationForCaller(CE->getCalleeContext(),
517                                CE->getLocationContext(),
518                                SMng);
519  }
520  else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&P)) {
521    return getLocationForCaller(CEE->getCalleeContext(),
522                                CEE->getLocationContext(),
523                                SMng);
524  }
525
526  return PathDiagnosticLocation(S, SMng, P.getLocationContext());
527}
528
529PathDiagnosticLocation
530  PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
531                                          const SourceManager &SM) {
532  assert(N && "Cannot create a location with a null node.");
533
534  const ExplodedNode *NI = N;
535
536  while (NI) {
537    ProgramPoint P = NI->getLocation();
538    const LocationContext *LC = P.getLocationContext();
539    if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P))
540      return PathDiagnosticLocation(PS->getStmt(), SM, LC);
541    else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
542      const Stmt *Term = BE->getSrc()->getTerminator();
543      if (Term) {
544        return PathDiagnosticLocation(Term, SM, LC);
545      }
546    }
547    NI = NI->succ_empty() ? 0 : *(NI->succ_begin());
548  }
549
550  return createDeclEnd(N->getLocationContext(), SM);
551}
552
553PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
554                                           const PathDiagnosticLocation &PDL) {
555  FullSourceLoc L = PDL.asLocation();
556  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
557}
558
559FullSourceLoc
560  PathDiagnosticLocation::genLocation(SourceLocation L,
561                                      LocationOrAnalysisDeclContext LAC) const {
562  assert(isValid());
563  // Note that we want a 'switch' here so that the compiler can warn us in
564  // case we add more cases.
565  switch (K) {
566    case SingleLocK:
567    case RangeK:
568      break;
569    case StmtK:
570      // Defensive checking.
571      if (!S)
572        break;
573      return FullSourceLoc(getValidSourceLocation(S, LAC),
574                           const_cast<SourceManager&>(*SM));
575    case DeclK:
576      // Defensive checking.
577      if (!D)
578        break;
579      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
580  }
581
582  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
583}
584
585PathDiagnosticRange
586  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
587  assert(isValid());
588  // Note that we want a 'switch' here so that the compiler can warn us in
589  // case we add more cases.
590  switch (K) {
591    case SingleLocK:
592      return PathDiagnosticRange(SourceRange(Loc,Loc), true);
593    case RangeK:
594      break;
595    case StmtK: {
596      const Stmt *S = asStmt();
597      switch (S->getStmtClass()) {
598        default:
599          break;
600        case Stmt::DeclStmtClass: {
601          const DeclStmt *DS = cast<DeclStmt>(S);
602          if (DS->isSingleDecl()) {
603            // Should always be the case, but we'll be defensive.
604            return SourceRange(DS->getLocStart(),
605                               DS->getSingleDecl()->getLocation());
606          }
607          break;
608        }
609          // FIXME: Provide better range information for different
610          //  terminators.
611        case Stmt::IfStmtClass:
612        case Stmt::WhileStmtClass:
613        case Stmt::DoStmtClass:
614        case Stmt::ForStmtClass:
615        case Stmt::ChooseExprClass:
616        case Stmt::IndirectGotoStmtClass:
617        case Stmt::SwitchStmtClass:
618        case Stmt::BinaryConditionalOperatorClass:
619        case Stmt::ConditionalOperatorClass:
620        case Stmt::ObjCForCollectionStmtClass: {
621          SourceLocation L = getValidSourceLocation(S, LAC);
622          return SourceRange(L, L);
623        }
624      }
625      SourceRange R = S->getSourceRange();
626      if (R.isValid())
627        return R;
628      break;
629    }
630    case DeclK:
631      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
632        return MD->getSourceRange();
633      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
634        if (Stmt *Body = FD->getBody())
635          return Body->getSourceRange();
636      }
637      else {
638        SourceLocation L = D->getLocation();
639        return PathDiagnosticRange(SourceRange(L, L), true);
640      }
641  }
642
643  return SourceRange(Loc,Loc);
644}
645
646void PathDiagnosticLocation::flatten() {
647  if (K == StmtK) {
648    K = RangeK;
649    S = 0;
650    D = 0;
651  }
652  else if (K == DeclK) {
653    K = SingleLocK;
654    S = 0;
655    D = 0;
656  }
657}
658
659//===----------------------------------------------------------------------===//
660// Manipulation of PathDiagnosticCallPieces.
661//===----------------------------------------------------------------------===//
662
663PathDiagnosticCallPiece *
664PathDiagnosticCallPiece::construct(const ExplodedNode *N,
665                                   const CallExitEnd &CE,
666                                   const SourceManager &SM) {
667  const Decl *caller = CE.getLocationContext()->getDecl();
668  PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
669                                                    CE.getLocationContext(),
670                                                    SM);
671  return new PathDiagnosticCallPiece(caller, pos);
672}
673
674PathDiagnosticCallPiece *
675PathDiagnosticCallPiece::construct(PathPieces &path,
676                                   const Decl *caller) {
677  PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path, caller);
678  path.clear();
679  path.push_front(C);
680  return C;
681}
682
683void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
684                                        const SourceManager &SM) {
685  const StackFrameContext *CalleeCtx = CE.getCalleeContext();
686  Callee = CalleeCtx->getDecl();
687
688  callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
689  callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
690}
691
692IntrusiveRefCntPtr<PathDiagnosticEventPiece>
693PathDiagnosticCallPiece::getCallEnterEvent() const {
694  if (!Callee)
695    return 0;
696  SmallString<256> buf;
697  llvm::raw_svector_ostream Out(buf);
698  if (isa<BlockDecl>(Callee))
699    Out << "Calling anonymous block";
700  else if (const NamedDecl *ND = dyn_cast<NamedDecl>(Callee))
701    Out << "Calling '" << *ND << "'";
702  StringRef msg = Out.str();
703  if (msg.empty())
704    return 0;
705  return new PathDiagnosticEventPiece(callEnter, msg);
706}
707
708IntrusiveRefCntPtr<PathDiagnosticEventPiece>
709PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
710  SmallString<256> buf;
711  llvm::raw_svector_ostream Out(buf);
712  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Caller))
713    Out << "Entered call from '" << *ND << "'";
714  else
715    Out << "Entered call";
716  StringRef msg = Out.str();
717  if (msg.empty())
718    return 0;
719  return new PathDiagnosticEventPiece(callEnterWithin, msg);
720}
721
722IntrusiveRefCntPtr<PathDiagnosticEventPiece>
723PathDiagnosticCallPiece::getCallExitEvent() const {
724  if (NoExit)
725    return 0;
726  SmallString<256> buf;
727  llvm::raw_svector_ostream Out(buf);
728  if (!CallStackMessage.empty())
729    Out << CallStackMessage;
730  else if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Callee))
731    Out << "Returning from '" << *ND << "'";
732  else
733    Out << "Returning to caller";
734  return new PathDiagnosticEventPiece(callReturn, Out.str());
735}
736
737static void compute_path_size(const PathPieces &pieces, unsigned &size) {
738  for (PathPieces::const_iterator it = pieces.begin(),
739                                  et = pieces.end(); it != et; ++it) {
740    const PathDiagnosticPiece *piece = it->getPtr();
741    if (const PathDiagnosticCallPiece *cp =
742        dyn_cast<PathDiagnosticCallPiece>(piece)) {
743      compute_path_size(cp->path, size);
744    }
745    else
746      ++size;
747  }
748}
749
750unsigned PathDiagnostic::full_size() {
751  unsigned size = 0;
752  compute_path_size(path, size);
753  return size;
754}
755
756//===----------------------------------------------------------------------===//
757// FoldingSet profiling methods.
758//===----------------------------------------------------------------------===//
759
760void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
761  ID.AddInteger(Range.getBegin().getRawEncoding());
762  ID.AddInteger(Range.getEnd().getRawEncoding());
763  ID.AddInteger(Loc.getRawEncoding());
764  return;
765}
766
767void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
768  ID.AddInteger((unsigned) getKind());
769  ID.AddString(str);
770  // FIXME: Add profiling support for code hints.
771  ID.AddInteger((unsigned) getDisplayHint());
772  ArrayRef<SourceRange> Ranges = getRanges();
773  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
774                                        I != E; ++I) {
775    ID.AddInteger(I->getBegin().getRawEncoding());
776    ID.AddInteger(I->getEnd().getRawEncoding());
777  }
778}
779
780void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
781  PathDiagnosticPiece::Profile(ID);
782  for (PathPieces::const_iterator it = path.begin(),
783       et = path.end(); it != et; ++it) {
784    ID.Add(**it);
785  }
786}
787
788void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
789  PathDiagnosticPiece::Profile(ID);
790  ID.Add(Pos);
791}
792
793void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
794  PathDiagnosticPiece::Profile(ID);
795  for (const_iterator I = begin(), E = end(); I != E; ++I)
796    ID.Add(*I);
797}
798
799void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
800  PathDiagnosticSpotPiece::Profile(ID);
801  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
802       I != E; ++I)
803    ID.Add(**I);
804}
805
806void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
807  ID.Add(getLocation());
808  ID.AddString(BugType);
809  ID.AddString(VerboseDesc);
810  ID.AddString(Category);
811}
812
813void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
814  Profile(ID);
815  for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
816    ID.Add(**I);
817  for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
818    ID.AddString(*I);
819}
820
821StackHintGenerator::~StackHintGenerator() {}
822
823std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
824  ProgramPoint P = N->getLocation();
825  const CallExitEnd *CExit = dyn_cast<CallExitEnd>(&P);
826  assert(CExit && "Stack Hints should be constructed at CallExitEnd points.");
827
828  // FIXME: Use CallEvent to abstract this over all calls.
829  const Stmt *CallSite = CExit->getCalleeContext()->getCallSite();
830  const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
831  if (!CE)
832    return "";
833
834  if (!N)
835    return getMessageForSymbolNotFound();
836
837  // Check if one of the parameters are set to the interesting symbol.
838  ProgramStateRef State = N->getState();
839  const LocationContext *LCtx = N->getLocationContext();
840  unsigned ArgIndex = 0;
841  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
842                                    E = CE->arg_end(); I != E; ++I, ++ArgIndex){
843    SVal SV = State->getSVal(*I, LCtx);
844
845    // Check if the variable corresponding to the symbol is passed by value.
846    SymbolRef AS = SV.getAsLocSymbol();
847    if (AS == Sym) {
848      return getMessageForArg(*I, ArgIndex);
849    }
850
851    // Check if the parameter is a pointer to the symbol.
852    if (const loc::MemRegionVal *Reg = dyn_cast<loc::MemRegionVal>(&SV)) {
853      SVal PSV = State->getSVal(Reg->getRegion());
854      SymbolRef AS = PSV.getAsLocSymbol();
855      if (AS == Sym) {
856        return getMessageForArg(*I, ArgIndex);
857      }
858    }
859  }
860
861  // Check if we are returning the interesting symbol.
862  SVal SV = State->getSVal(CE, LCtx);
863  SymbolRef RetSym = SV.getAsLocSymbol();
864  if (RetSym == Sym) {
865    return getMessageForReturn(CE);
866  }
867
868  return getMessageForSymbolNotFound();
869}
870
871/// TODO: This is copied from clang diagnostics. Maybe we could just move it to
872/// some common place. (Same as HandleOrdinalModifier.)
873void StackHintGeneratorForSymbol::printOrdinal(unsigned ValNo,
874                                               llvm::raw_svector_ostream &Out) {
875  assert(ValNo != 0 && "ValNo must be strictly positive!");
876
877  // We could use text forms for the first N ordinals, but the numeric
878  // forms are actually nicer in diagnostics because they stand out.
879  Out << ValNo;
880
881  // It is critically important that we do this perfectly for
882  // user-written sequences with over 100 elements.
883  switch (ValNo % 100) {
884  case 11:
885  case 12:
886  case 13:
887    Out << "th"; return;
888  default:
889    switch (ValNo % 10) {
890    case 1: Out << "st"; return;
891    case 2: Out << "nd"; return;
892    case 3: Out << "rd"; return;
893    default: Out << "th"; return;
894    }
895  }
896}
897
898std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
899                                                        unsigned ArgIndex) {
900  SmallString<200> buf;
901  llvm::raw_svector_ostream os(buf);
902
903  os << Msg << " via ";
904  // Printed parameters start at 1, not 0.
905  printOrdinal(++ArgIndex, os);
906  os << " parameter";
907
908  return os.str();
909}
910