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