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