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