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