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