PathDiagnostic.cpp revision 2343b3d0c29356583a013d900f2817083ac2d4a0 
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 {
211struct CompareDiagnostics {
212  // Compare if 'X' is "<" than 'Y'.
213  bool operator()(const PathDiagnostic *X, const PathDiagnostic *Y) const {
214    // First sort by location, and if that doesn't work, do a full profile.
215    FullSourceLoc XL = X->getLocation().asLocation();
216    FullSourceLoc YL = Y->getLocation().asLocation();
217    if (XL != YL)
218      return XL < YL;
219
220    // Do a full profile.
221    llvm::FoldingSetNodeID XProfile, YProfile;
222    X->FullProfile(XProfile);
223    Y->FullProfile(YProfile);
224    return XProfile < YProfile;
225  }
226};
227}
228
229void PathDiagnosticConsumer::FlushDiagnostics(
230                                     PathDiagnosticConsumer::FilesMade *Files) {
231  if (flushed)
232    return;
233
234  flushed = true;
235
236  std::vector<const PathDiagnostic *> BatchDiags;
237  for (llvm::FoldingSet<PathDiagnostic>::iterator it = Diags.begin(),
238       et = Diags.end(); it != et; ++it) {
239    const PathDiagnostic *D = &*it;
240    BatchDiags.push_back(D);
241  }
242
243  // Sort the diagnostics so that they are always emitted in a deterministic
244  // order.
245  if (!BatchDiags.empty())
246    std::sort(BatchDiags.begin(), BatchDiags.end(), CompareDiagnostics());
247
248  FlushDiagnosticsImpl(BatchDiags, Files);
249
250  // Delete the flushed diagnostics.
251  for (std::vector<const PathDiagnostic *>::iterator it = BatchDiags.begin(),
252       et = BatchDiags.end(); it != et; ++it) {
253    const PathDiagnostic *D = *it;
254    delete D;
255  }
256
257  // Clear out the FoldingSet.
258  Diags.clear();
259}
260
261void PathDiagnosticConsumer::FilesMade::addDiagnostic(const PathDiagnostic &PD,
262                                                      StringRef ConsumerName,
263                                                      StringRef FileName) {
264  llvm::FoldingSetNodeID NodeID;
265  NodeID.Add(PD);
266  void *InsertPos;
267  PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
268  if (!Entry) {
269    Entry = Alloc.Allocate<PDFileEntry>();
270    Entry = new (Entry) PDFileEntry(NodeID);
271    InsertNode(Entry, InsertPos);
272  }
273
274  // Allocate persistent storage for the file name.
275  char *FileName_cstr = (char*) Alloc.Allocate(FileName.size(), 1);
276  memcpy(FileName_cstr, FileName.data(), FileName.size());
277
278  Entry->files.push_back(std::make_pair(ConsumerName,
279                                        StringRef(FileName_cstr,
280                                                  FileName.size())));
281}
282
283PathDiagnosticConsumer::PDFileEntry::ConsumerFiles *
284PathDiagnosticConsumer::FilesMade::getFiles(const PathDiagnostic &PD) {
285  llvm::FoldingSetNodeID NodeID;
286  NodeID.Add(PD);
287  void *InsertPos;
288  PDFileEntry *Entry = FindNodeOrInsertPos(NodeID, InsertPos);
289  if (!Entry)
290    return 0;
291  return &Entry->files;
292}
293
294//===----------------------------------------------------------------------===//
295// PathDiagnosticLocation methods.
296//===----------------------------------------------------------------------===//
297
298static SourceLocation getValidSourceLocation(const Stmt* S,
299                                             LocationOrAnalysisDeclContext LAC,
300                                             bool UseEnd = false) {
301  SourceLocation L = UseEnd ? S->getLocEnd() : S->getLocStart();
302  assert(!LAC.isNull() && "A valid LocationContext or AnalysisDeclContext should "
303                          "be passed to PathDiagnosticLocation upon creation.");
304
305  // S might be a temporary statement that does not have a location in the
306  // source code, so find an enclosing statement and use its location.
307  if (!L.isValid()) {
308
309    AnalysisDeclContext *ADC;
310    if (LAC.is<const LocationContext*>())
311      ADC = LAC.get<const LocationContext*>()->getAnalysisDeclContext();
312    else
313      ADC = LAC.get<AnalysisDeclContext*>();
314
315    ParentMap &PM = ADC->getParentMap();
316
317    const Stmt *Parent = S;
318    do {
319      Parent = PM.getParent(Parent);
320
321      // In rare cases, we have implicit top-level expressions,
322      // such as arguments for implicit member initializers.
323      // In this case, fall back to the start of the body (even if we were
324      // asked for the statement end location).
325      if (!Parent) {
326        const Stmt *Body = ADC->getBody();
327        if (Body)
328          L = Body->getLocStart();
329        else
330          L = ADC->getDecl()->getLocEnd();
331        break;
332      }
333
334      L = UseEnd ? Parent->getLocEnd() : Parent->getLocStart();
335    } while (!L.isValid());
336  }
337
338  return L;
339}
340
341static PathDiagnosticLocation
342getLocationForCaller(const StackFrameContext *SFC,
343                     const LocationContext *CallerCtx,
344                     const SourceManager &SM) {
345  const CFGBlock &Block = *SFC->getCallSiteBlock();
346  CFGElement Source = Block[SFC->getIndex()];
347
348  switch (Source.getKind()) {
349  case CFGElement::Invalid:
350    llvm_unreachable("Invalid CFGElement");
351  case CFGElement::Statement:
352    return PathDiagnosticLocation(cast<CFGStmt>(Source).getStmt(),
353                                  SM, CallerCtx);
354  case CFGElement::Initializer: {
355    const CFGInitializer &Init = cast<CFGInitializer>(Source);
356    return PathDiagnosticLocation(Init.getInitializer()->getInit(),
357                                  SM, CallerCtx);
358  }
359  case CFGElement::AutomaticObjectDtor: {
360    const CFGAutomaticObjDtor &Dtor = cast<CFGAutomaticObjDtor>(Source);
361    return PathDiagnosticLocation::createEnd(Dtor.getTriggerStmt(),
362                                             SM, CallerCtx);
363  }
364  case CFGElement::BaseDtor:
365  case CFGElement::MemberDtor: {
366    const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
367    if (const Stmt *CallerBody = CallerInfo->getBody())
368      return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
369    return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
370  }
371  case CFGElement::TemporaryDtor:
372    llvm_unreachable("not yet implemented!");
373  }
374
375  llvm_unreachable("Unknown CFGElement kind");
376}
377
378
379PathDiagnosticLocation
380  PathDiagnosticLocation::createBegin(const Decl *D,
381                                      const SourceManager &SM) {
382  return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
383}
384
385PathDiagnosticLocation
386  PathDiagnosticLocation::createBegin(const Stmt *S,
387                                      const SourceManager &SM,
388                                      LocationOrAnalysisDeclContext LAC) {
389  return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
390                                SM, SingleLocK);
391}
392
393
394PathDiagnosticLocation
395PathDiagnosticLocation::createEnd(const Stmt *S,
396                                  const SourceManager &SM,
397                                  LocationOrAnalysisDeclContext LAC) {
398  if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(S))
399    return createEndBrace(CS, SM);
400  return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
401                                SM, SingleLocK);
402}
403
404PathDiagnosticLocation
405  PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
406                                            const SourceManager &SM) {
407  return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
408}
409
410PathDiagnosticLocation
411  PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
412                                          const SourceManager &SM) {
413  return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
414}
415
416PathDiagnosticLocation
417  PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
418                                           const SourceManager &SM) {
419  SourceLocation L = CS->getLBracLoc();
420  return PathDiagnosticLocation(L, SM, SingleLocK);
421}
422
423PathDiagnosticLocation
424  PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
425                                         const SourceManager &SM) {
426  SourceLocation L = CS->getRBracLoc();
427  return PathDiagnosticLocation(L, SM, SingleLocK);
428}
429
430PathDiagnosticLocation
431  PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
432                                          const SourceManager &SM) {
433  // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
434  if (const CompoundStmt *CS =
435        dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
436    if (!CS->body_empty()) {
437      SourceLocation Loc = (*CS->body_begin())->getLocStart();
438      return PathDiagnosticLocation(Loc, SM, SingleLocK);
439    }
440
441  return PathDiagnosticLocation();
442}
443
444PathDiagnosticLocation
445  PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
446                                        const SourceManager &SM) {
447  SourceLocation L = LC->getDecl()->getBodyRBrace();
448  return PathDiagnosticLocation(L, SM, SingleLocK);
449}
450
451PathDiagnosticLocation
452  PathDiagnosticLocation::create(const ProgramPoint& P,
453                                 const SourceManager &SMng) {
454
455  const Stmt* S = 0;
456  if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
457    const CFGBlock *BSrc = BE->getSrc();
458    S = BSrc->getTerminatorCondition();
459  }
460  else if (const PostStmt *PS = dyn_cast<PostStmt>(&P)) {
461    S = PS->getStmt();
462  }
463  else if (const PostImplicitCall *PIE = dyn_cast<PostImplicitCall>(&P)) {
464    return PathDiagnosticLocation(PIE->getLocation(), SMng);
465  }
466  else if (const CallEnter *CE = dyn_cast<CallEnter>(&P)) {
467    return getLocationForCaller(CE->getCalleeContext(),
468                                CE->getLocationContext(),
469                                SMng);
470  }
471  else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&P)) {
472    return getLocationForCaller(CEE->getCalleeContext(),
473                                CEE->getLocationContext(),
474                                SMng);
475  }
476
477  return PathDiagnosticLocation(S, SMng, P.getLocationContext());
478}
479
480PathDiagnosticLocation
481  PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
482                                          const SourceManager &SM) {
483  assert(N && "Cannot create a location with a null node.");
484
485  const ExplodedNode *NI = N;
486
487  while (NI) {
488    ProgramPoint P = NI->getLocation();
489    const LocationContext *LC = P.getLocationContext();
490    if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P))
491      return PathDiagnosticLocation(PS->getStmt(), SM, LC);
492    else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
493      const Stmt *Term = BE->getSrc()->getTerminator();
494      if (Term) {
495        return PathDiagnosticLocation(Term, SM, LC);
496      }
497    }
498    NI = NI->succ_empty() ? 0 : *(NI->succ_begin());
499  }
500
501  return createDeclEnd(N->getLocationContext(), SM);
502}
503
504PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
505                                           const PathDiagnosticLocation &PDL) {
506  FullSourceLoc L = PDL.asLocation();
507  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
508}
509
510FullSourceLoc
511  PathDiagnosticLocation::genLocation(SourceLocation L,
512                                      LocationOrAnalysisDeclContext LAC) const {
513  assert(isValid());
514  // Note that we want a 'switch' here so that the compiler can warn us in
515  // case we add more cases.
516  switch (K) {
517    case SingleLocK:
518    case RangeK:
519      break;
520    case StmtK:
521      // Defensive checking.
522      if (!S)
523        break;
524      return FullSourceLoc(getValidSourceLocation(S, LAC),
525                           const_cast<SourceManager&>(*SM));
526    case DeclK:
527      // Defensive checking.
528      if (!D)
529        break;
530      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
531  }
532
533  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
534}
535
536PathDiagnosticRange
537  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
538  assert(isValid());
539  // Note that we want a 'switch' here so that the compiler can warn us in
540  // case we add more cases.
541  switch (K) {
542    case SingleLocK:
543      return PathDiagnosticRange(SourceRange(Loc,Loc), true);
544    case RangeK:
545      break;
546    case StmtK: {
547      const Stmt *S = asStmt();
548      switch (S->getStmtClass()) {
549        default:
550          break;
551        case Stmt::DeclStmtClass: {
552          const DeclStmt *DS = cast<DeclStmt>(S);
553          if (DS->isSingleDecl()) {
554            // Should always be the case, but we'll be defensive.
555            return SourceRange(DS->getLocStart(),
556                               DS->getSingleDecl()->getLocation());
557          }
558          break;
559        }
560          // FIXME: Provide better range information for different
561          //  terminators.
562        case Stmt::IfStmtClass:
563        case Stmt::WhileStmtClass:
564        case Stmt::DoStmtClass:
565        case Stmt::ForStmtClass:
566        case Stmt::ChooseExprClass:
567        case Stmt::IndirectGotoStmtClass:
568        case Stmt::SwitchStmtClass:
569        case Stmt::BinaryConditionalOperatorClass:
570        case Stmt::ConditionalOperatorClass:
571        case Stmt::ObjCForCollectionStmtClass: {
572          SourceLocation L = getValidSourceLocation(S, LAC);
573          return SourceRange(L, L);
574        }
575      }
576      SourceRange R = S->getSourceRange();
577      if (R.isValid())
578        return R;
579      break;
580    }
581    case DeclK:
582      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
583        return MD->getSourceRange();
584      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
585        if (Stmt *Body = FD->getBody())
586          return Body->getSourceRange();
587      }
588      else {
589        SourceLocation L = D->getLocation();
590        return PathDiagnosticRange(SourceRange(L, L), true);
591      }
592  }
593
594  return SourceRange(Loc,Loc);
595}
596
597void PathDiagnosticLocation::flatten() {
598  if (K == StmtK) {
599    K = RangeK;
600    S = 0;
601    D = 0;
602  }
603  else if (K == DeclK) {
604    K = SingleLocK;
605    S = 0;
606    D = 0;
607  }
608}
609
610//===----------------------------------------------------------------------===//
611// Manipulation of PathDiagnosticCallPieces.
612//===----------------------------------------------------------------------===//
613
614PathDiagnosticCallPiece *
615PathDiagnosticCallPiece::construct(const ExplodedNode *N,
616                                   const CallExitEnd &CE,
617                                   const SourceManager &SM) {
618  const Decl *caller = CE.getLocationContext()->getDecl();
619  PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
620                                                    CE.getLocationContext(),
621                                                    SM);
622  return new PathDiagnosticCallPiece(caller, pos);
623}
624
625PathDiagnosticCallPiece *
626PathDiagnosticCallPiece::construct(PathPieces &path,
627                                   const Decl *caller) {
628  PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path, caller);
629  path.clear();
630  path.push_front(C);
631  return C;
632}
633
634void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
635                                        const SourceManager &SM) {
636  const StackFrameContext *CalleeCtx = CE.getCalleeContext();
637  Callee = CalleeCtx->getDecl();
638
639  callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
640  callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
641}
642
643IntrusiveRefCntPtr<PathDiagnosticEventPiece>
644PathDiagnosticCallPiece::getCallEnterEvent() const {
645  if (!Callee)
646    return 0;
647  SmallString<256> buf;
648  llvm::raw_svector_ostream Out(buf);
649  if (isa<BlockDecl>(Callee))
650    Out << "Calling anonymous block";
651  else if (const NamedDecl *ND = dyn_cast<NamedDecl>(Callee))
652    Out << "Calling '" << *ND << "'";
653  StringRef msg = Out.str();
654  if (msg.empty())
655    return 0;
656  return new PathDiagnosticEventPiece(callEnter, msg);
657}
658
659IntrusiveRefCntPtr<PathDiagnosticEventPiece>
660PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
661  SmallString<256> buf;
662  llvm::raw_svector_ostream Out(buf);
663  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Caller))
664    Out << "Entered call from '" << *ND << "'";
665  else
666    Out << "Entered call";
667  StringRef msg = Out.str();
668  if (msg.empty())
669    return 0;
670  return new PathDiagnosticEventPiece(callEnterWithin, msg);
671}
672
673IntrusiveRefCntPtr<PathDiagnosticEventPiece>
674PathDiagnosticCallPiece::getCallExitEvent() const {
675  if (NoExit)
676    return 0;
677  SmallString<256> buf;
678  llvm::raw_svector_ostream Out(buf);
679  if (!CallStackMessage.empty())
680    Out << CallStackMessage;
681  else if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Callee))
682    Out << "Returning from '" << *ND << "'";
683  else
684    Out << "Returning to caller";
685  return new PathDiagnosticEventPiece(callReturn, Out.str());
686}
687
688static void compute_path_size(const PathPieces &pieces, unsigned &size) {
689  for (PathPieces::const_iterator it = pieces.begin(),
690                                  et = pieces.end(); it != et; ++it) {
691    const PathDiagnosticPiece *piece = it->getPtr();
692    if (const PathDiagnosticCallPiece *cp =
693        dyn_cast<PathDiagnosticCallPiece>(piece)) {
694      compute_path_size(cp->path, size);
695    }
696    else
697      ++size;
698  }
699}
700
701unsigned PathDiagnostic::full_size() {
702  unsigned size = 0;
703  compute_path_size(path, size);
704  return size;
705}
706
707//===----------------------------------------------------------------------===//
708// FoldingSet profiling methods.
709//===----------------------------------------------------------------------===//
710
711void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
712  ID.AddInteger(Range.getBegin().getRawEncoding());
713  ID.AddInteger(Range.getEnd().getRawEncoding());
714  ID.AddInteger(Loc.getRawEncoding());
715  return;
716}
717
718void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
719  ID.AddInteger((unsigned) getKind());
720  ID.AddString(str);
721  // FIXME: Add profiling support for code hints.
722  ID.AddInteger((unsigned) getDisplayHint());
723  ArrayRef<SourceRange> Ranges = getRanges();
724  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
725                                        I != E; ++I) {
726    ID.AddInteger(I->getBegin().getRawEncoding());
727    ID.AddInteger(I->getEnd().getRawEncoding());
728  }
729}
730
731void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
732  PathDiagnosticPiece::Profile(ID);
733  for (PathPieces::const_iterator it = path.begin(),
734       et = path.end(); it != et; ++it) {
735    ID.Add(**it);
736  }
737}
738
739void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
740  PathDiagnosticPiece::Profile(ID);
741  ID.Add(Pos);
742}
743
744void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
745  PathDiagnosticPiece::Profile(ID);
746  for (const_iterator I = begin(), E = end(); I != E; ++I)
747    ID.Add(*I);
748}
749
750void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
751  PathDiagnosticSpotPiece::Profile(ID);
752  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
753       I != E; ++I)
754    ID.Add(**I);
755}
756
757void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
758  ID.Add(getLocation());
759  ID.AddString(BugType);
760  ID.AddString(VerboseDesc);
761  ID.AddString(Category);
762}
763
764void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
765  Profile(ID);
766  for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
767    ID.Add(**I);
768  for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
769    ID.AddString(*I);
770}
771
772StackHintGenerator::~StackHintGenerator() {}
773
774std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
775  ProgramPoint P = N->getLocation();
776  const CallExitEnd *CExit = dyn_cast<CallExitEnd>(&P);
777  assert(CExit && "Stack Hints should be constructed at CallExitEnd points.");
778
779  // FIXME: Use CallEvent to abstract this over all calls.
780  const Stmt *CallSite = CExit->getCalleeContext()->getCallSite();
781  const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
782  if (!CE)
783    return "";
784
785  if (!N)
786    return getMessageForSymbolNotFound();
787
788  // Check if one of the parameters are set to the interesting symbol.
789  ProgramStateRef State = N->getState();
790  const LocationContext *LCtx = N->getLocationContext();
791  unsigned ArgIndex = 0;
792  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
793                                    E = CE->arg_end(); I != E; ++I, ++ArgIndex){
794    SVal SV = State->getSVal(*I, LCtx);
795
796    // Check if the variable corresponding to the symbol is passed by value.
797    SymbolRef AS = SV.getAsLocSymbol();
798    if (AS == Sym) {
799      return getMessageForArg(*I, ArgIndex);
800    }
801
802    // Check if the parameter is a pointer to the symbol.
803    if (const loc::MemRegionVal *Reg = dyn_cast<loc::MemRegionVal>(&SV)) {
804      SVal PSV = State->getSVal(Reg->getRegion());
805      SymbolRef AS = PSV.getAsLocSymbol();
806      if (AS == Sym) {
807        return getMessageForArg(*I, ArgIndex);
808      }
809    }
810  }
811
812  // Check if we are returning the interesting symbol.
813  SVal SV = State->getSVal(CE, LCtx);
814  SymbolRef RetSym = SV.getAsLocSymbol();
815  if (RetSym == Sym) {
816    return getMessageForReturn(CE);
817  }
818
819  return getMessageForSymbolNotFound();
820}
821
822/// TODO: This is copied from clang diagnostics. Maybe we could just move it to
823/// some common place. (Same as HandleOrdinalModifier.)
824void StackHintGeneratorForSymbol::printOrdinal(unsigned ValNo,
825                                               llvm::raw_svector_ostream &Out) {
826  assert(ValNo != 0 && "ValNo must be strictly positive!");
827
828  // We could use text forms for the first N ordinals, but the numeric
829  // forms are actually nicer in diagnostics because they stand out.
830  Out << ValNo;
831
832  // It is critically important that we do this perfectly for
833  // user-written sequences with over 100 elements.
834  switch (ValNo % 100) {
835  case 11:
836  case 12:
837  case 13:
838    Out << "th"; return;
839  default:
840    switch (ValNo % 10) {
841    case 1: Out << "st"; return;
842    case 2: Out << "nd"; return;
843    case 3: Out << "rd"; return;
844    default: Out << "th"; return;
845    }
846  }
847}
848
849std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
850                                                        unsigned ArgIndex) {
851  SmallString<200> buf;
852  llvm::raw_svector_ostream os(buf);
853
854  os << Msg << " via ";
855  // Printed parameters start at 1, not 0.
856  printOrdinal(++ArgIndex, os);
857  os << " parameter";
858
859  return os.str();
860}
861