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