PathDiagnostic.cpp revision 615a092a511cd2dfe1a5364ebf5f80e55e33034d 
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 PostStmt *PS = dyn_cast<PostStmt>(&P)) {
590    S = PS->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
606  return PathDiagnosticLocation(S, SMng, P.getLocationContext());
607}
608
609PathDiagnosticLocation
610  PathDiagnosticLocation::createEndOfPath(const ExplodedNode* N,
611                                          const SourceManager &SM) {
612  assert(N && "Cannot create a location with a null node.");
613
614  const ExplodedNode *NI = N;
615
616  while (NI) {
617    ProgramPoint P = NI->getLocation();
618    const LocationContext *LC = P.getLocationContext();
619    if (const StmtPoint *PS = dyn_cast<StmtPoint>(&P))
620      return PathDiagnosticLocation(PS->getStmt(), SM, LC);
621    else if (const BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
622      const Stmt *Term = BE->getSrc()->getTerminator();
623      if (Term) {
624        return PathDiagnosticLocation(Term, SM, LC);
625      }
626    }
627    NI = NI->succ_empty() ? 0 : *(NI->succ_begin());
628  }
629
630  return createDeclEnd(N->getLocationContext(), SM);
631}
632
633PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
634                                           const PathDiagnosticLocation &PDL) {
635  FullSourceLoc L = PDL.asLocation();
636  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
637}
638
639FullSourceLoc
640  PathDiagnosticLocation::genLocation(SourceLocation L,
641                                      LocationOrAnalysisDeclContext LAC) const {
642  assert(isValid());
643  // Note that we want a 'switch' here so that the compiler can warn us in
644  // case we add more cases.
645  switch (K) {
646    case SingleLocK:
647    case RangeK:
648      break;
649    case StmtK:
650      // Defensive checking.
651      if (!S)
652        break;
653      return FullSourceLoc(getValidSourceLocation(S, LAC),
654                           const_cast<SourceManager&>(*SM));
655    case DeclK:
656      // Defensive checking.
657      if (!D)
658        break;
659      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
660  }
661
662  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
663}
664
665PathDiagnosticRange
666  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
667  assert(isValid());
668  // Note that we want a 'switch' here so that the compiler can warn us in
669  // case we add more cases.
670  switch (K) {
671    case SingleLocK:
672      return PathDiagnosticRange(SourceRange(Loc,Loc), true);
673    case RangeK:
674      break;
675    case StmtK: {
676      const Stmt *S = asStmt();
677      switch (S->getStmtClass()) {
678        default:
679          break;
680        case Stmt::DeclStmtClass: {
681          const DeclStmt *DS = cast<DeclStmt>(S);
682          if (DS->isSingleDecl()) {
683            // Should always be the case, but we'll be defensive.
684            return SourceRange(DS->getLocStart(),
685                               DS->getSingleDecl()->getLocation());
686          }
687          break;
688        }
689          // FIXME: Provide better range information for different
690          //  terminators.
691        case Stmt::IfStmtClass:
692        case Stmt::WhileStmtClass:
693        case Stmt::DoStmtClass:
694        case Stmt::ForStmtClass:
695        case Stmt::ChooseExprClass:
696        case Stmt::IndirectGotoStmtClass:
697        case Stmt::SwitchStmtClass:
698        case Stmt::BinaryConditionalOperatorClass:
699        case Stmt::ConditionalOperatorClass:
700        case Stmt::ObjCForCollectionStmtClass: {
701          SourceLocation L = getValidSourceLocation(S, LAC);
702          return SourceRange(L, L);
703        }
704      }
705      SourceRange R = S->getSourceRange();
706      if (R.isValid())
707        return R;
708      break;
709    }
710    case DeclK:
711      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
712        return MD->getSourceRange();
713      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
714        if (Stmt *Body = FD->getBody())
715          return Body->getSourceRange();
716      }
717      else {
718        SourceLocation L = D->getLocation();
719        return PathDiagnosticRange(SourceRange(L, L), true);
720      }
721  }
722
723  return SourceRange(Loc,Loc);
724}
725
726void PathDiagnosticLocation::flatten() {
727  if (K == StmtK) {
728    K = RangeK;
729    S = 0;
730    D = 0;
731  }
732  else if (K == DeclK) {
733    K = SingleLocK;
734    S = 0;
735    D = 0;
736  }
737}
738
739//===----------------------------------------------------------------------===//
740// Manipulation of PathDiagnosticCallPieces.
741//===----------------------------------------------------------------------===//
742
743PathDiagnosticCallPiece *
744PathDiagnosticCallPiece::construct(const ExplodedNode *N,
745                                   const CallExitEnd &CE,
746                                   const SourceManager &SM) {
747  const Decl *caller = CE.getLocationContext()->getDecl();
748  PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
749                                                    CE.getLocationContext(),
750                                                    SM);
751  return new PathDiagnosticCallPiece(caller, pos);
752}
753
754PathDiagnosticCallPiece *
755PathDiagnosticCallPiece::construct(PathPieces &path,
756                                   const Decl *caller) {
757  PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path, caller);
758  path.clear();
759  path.push_front(C);
760  return C;
761}
762
763void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
764                                        const SourceManager &SM) {
765  const StackFrameContext *CalleeCtx = CE.getCalleeContext();
766  Callee = CalleeCtx->getDecl();
767
768  callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
769  callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
770}
771
772IntrusiveRefCntPtr<PathDiagnosticEventPiece>
773PathDiagnosticCallPiece::getCallEnterEvent() const {
774  if (!Callee)
775    return 0;
776  SmallString<256> buf;
777  llvm::raw_svector_ostream Out(buf);
778  if (isa<BlockDecl>(Callee))
779    Out << "Calling anonymous block";
780  else if (const NamedDecl *ND = dyn_cast<NamedDecl>(Callee))
781    Out << "Calling '" << *ND << "'";
782  StringRef msg = Out.str();
783  if (msg.empty())
784    return 0;
785  return new PathDiagnosticEventPiece(callEnter, msg);
786}
787
788IntrusiveRefCntPtr<PathDiagnosticEventPiece>
789PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
790  SmallString<256> buf;
791  llvm::raw_svector_ostream Out(buf);
792  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Caller))
793    Out << "Entered call from '" << *ND << "'";
794  else
795    Out << "Entered call";
796  StringRef msg = Out.str();
797  if (msg.empty())
798    return 0;
799  return new PathDiagnosticEventPiece(callEnterWithin, msg);
800}
801
802IntrusiveRefCntPtr<PathDiagnosticEventPiece>
803PathDiagnosticCallPiece::getCallExitEvent() const {
804  if (NoExit)
805    return 0;
806  SmallString<256> buf;
807  llvm::raw_svector_ostream Out(buf);
808  if (!CallStackMessage.empty())
809    Out << CallStackMessage;
810  else if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Callee))
811    Out << "Returning from '" << *ND << "'";
812  else
813    Out << "Returning to caller";
814  return new PathDiagnosticEventPiece(callReturn, Out.str());
815}
816
817static void compute_path_size(const PathPieces &pieces, unsigned &size) {
818  for (PathPieces::const_iterator it = pieces.begin(),
819                                  et = pieces.end(); it != et; ++it) {
820    const PathDiagnosticPiece *piece = it->getPtr();
821    if (const PathDiagnosticCallPiece *cp =
822        dyn_cast<PathDiagnosticCallPiece>(piece)) {
823      compute_path_size(cp->path, size);
824    }
825    else
826      ++size;
827  }
828}
829
830unsigned PathDiagnostic::full_size() {
831  unsigned size = 0;
832  compute_path_size(path, size);
833  return size;
834}
835
836//===----------------------------------------------------------------------===//
837// FoldingSet profiling methods.
838//===----------------------------------------------------------------------===//
839
840void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
841  ID.AddInteger(Range.getBegin().getRawEncoding());
842  ID.AddInteger(Range.getEnd().getRawEncoding());
843  ID.AddInteger(Loc.getRawEncoding());
844  return;
845}
846
847void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
848  ID.AddInteger((unsigned) getKind());
849  ID.AddString(str);
850  // FIXME: Add profiling support for code hints.
851  ID.AddInteger((unsigned) getDisplayHint());
852  ArrayRef<SourceRange> Ranges = getRanges();
853  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
854                                        I != E; ++I) {
855    ID.AddInteger(I->getBegin().getRawEncoding());
856    ID.AddInteger(I->getEnd().getRawEncoding());
857  }
858}
859
860void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
861  PathDiagnosticPiece::Profile(ID);
862  for (PathPieces::const_iterator it = path.begin(),
863       et = path.end(); it != et; ++it) {
864    ID.Add(**it);
865  }
866}
867
868void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
869  PathDiagnosticPiece::Profile(ID);
870  ID.Add(Pos);
871}
872
873void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
874  PathDiagnosticPiece::Profile(ID);
875  for (const_iterator I = begin(), E = end(); I != E; ++I)
876    ID.Add(*I);
877}
878
879void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
880  PathDiagnosticSpotPiece::Profile(ID);
881  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
882       I != E; ++I)
883    ID.Add(**I);
884}
885
886void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
887  ID.Add(getLocation());
888  ID.AddString(BugType);
889  ID.AddString(VerboseDesc);
890  ID.AddString(Category);
891}
892
893void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
894  Profile(ID);
895  for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
896    ID.Add(**I);
897  for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
898    ID.AddString(*I);
899}
900
901StackHintGenerator::~StackHintGenerator() {}
902
903std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
904  ProgramPoint P = N->getLocation();
905  const CallExitEnd *CExit = dyn_cast<CallExitEnd>(&P);
906  assert(CExit && "Stack Hints should be constructed at CallExitEnd points.");
907
908  // FIXME: Use CallEvent to abstract this over all calls.
909  const Stmt *CallSite = CExit->getCalleeContext()->getCallSite();
910  const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
911  if (!CE)
912    return "";
913
914  if (!N)
915    return getMessageForSymbolNotFound();
916
917  // Check if one of the parameters are set to the interesting symbol.
918  ProgramStateRef State = N->getState();
919  const LocationContext *LCtx = N->getLocationContext();
920  unsigned ArgIndex = 0;
921  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
922                                    E = CE->arg_end(); I != E; ++I, ++ArgIndex){
923    SVal SV = State->getSVal(*I, LCtx);
924
925    // Check if the variable corresponding to the symbol is passed by value.
926    SymbolRef AS = SV.getAsLocSymbol();
927    if (AS == Sym) {
928      return getMessageForArg(*I, ArgIndex);
929    }
930
931    // Check if the parameter is a pointer to the symbol.
932    if (const loc::MemRegionVal *Reg = dyn_cast<loc::MemRegionVal>(&SV)) {
933      SVal PSV = State->getSVal(Reg->getRegion());
934      SymbolRef AS = PSV.getAsLocSymbol();
935      if (AS == Sym) {
936        return getMessageForArg(*I, ArgIndex);
937      }
938    }
939  }
940
941  // Check if we are returning the interesting symbol.
942  SVal SV = State->getSVal(CE, LCtx);
943  SymbolRef RetSym = SV.getAsLocSymbol();
944  if (RetSym == Sym) {
945    return getMessageForReturn(CE);
946  }
947
948  return getMessageForSymbolNotFound();
949}
950
951std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
952                                                          unsigned ArgIndex) {
953  // Printed parameters start at 1, not 0.
954  ++ArgIndex;
955
956  SmallString<200> buf;
957  llvm::raw_svector_ostream os(buf);
958
959  os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
960     << " parameter";
961
962  return os.str();
963}
964