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