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