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