PathDiagnostic.cpp revision 344472ebeded2fca2ed5013b9e87f81d09bfa908 
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::BaseDtor:
563  case CFGElement::MemberDtor: {
564    const AnalysisDeclContext *CallerInfo = CallerCtx->getAnalysisDeclContext();
565    if (const Stmt *CallerBody = CallerInfo->getBody())
566      return PathDiagnosticLocation::createEnd(CallerBody, SM, CallerCtx);
567    return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
568  }
569  case CFGElement::TemporaryDtor:
570    llvm_unreachable("not yet implemented!");
571  }
572
573  llvm_unreachable("Unknown CFGElement kind");
574}
575
576
577PathDiagnosticLocation
578  PathDiagnosticLocation::createBegin(const Decl *D,
579                                      const SourceManager &SM) {
580  return PathDiagnosticLocation(D->getLocStart(), SM, SingleLocK);
581}
582
583PathDiagnosticLocation
584  PathDiagnosticLocation::createBegin(const Stmt *S,
585                                      const SourceManager &SM,
586                                      LocationOrAnalysisDeclContext LAC) {
587  return PathDiagnosticLocation(getValidSourceLocation(S, LAC),
588                                SM, SingleLocK);
589}
590
591
592PathDiagnosticLocation
593PathDiagnosticLocation::createEnd(const Stmt *S,
594                                  const SourceManager &SM,
595                                  LocationOrAnalysisDeclContext LAC) {
596  if (const CompoundStmt *CS = dyn_cast<CompoundStmt>(S))
597    return createEndBrace(CS, SM);
598  return PathDiagnosticLocation(getValidSourceLocation(S, LAC, /*End=*/true),
599                                SM, SingleLocK);
600}
601
602PathDiagnosticLocation
603  PathDiagnosticLocation::createOperatorLoc(const BinaryOperator *BO,
604                                            const SourceManager &SM) {
605  return PathDiagnosticLocation(BO->getOperatorLoc(), SM, SingleLocK);
606}
607
608PathDiagnosticLocation
609  PathDiagnosticLocation::createMemberLoc(const MemberExpr *ME,
610                                          const SourceManager &SM) {
611  return PathDiagnosticLocation(ME->getMemberLoc(), SM, SingleLocK);
612}
613
614PathDiagnosticLocation
615  PathDiagnosticLocation::createBeginBrace(const CompoundStmt *CS,
616                                           const SourceManager &SM) {
617  SourceLocation L = CS->getLBracLoc();
618  return PathDiagnosticLocation(L, SM, SingleLocK);
619}
620
621PathDiagnosticLocation
622  PathDiagnosticLocation::createEndBrace(const CompoundStmt *CS,
623                                         const SourceManager &SM) {
624  SourceLocation L = CS->getRBracLoc();
625  return PathDiagnosticLocation(L, SM, SingleLocK);
626}
627
628PathDiagnosticLocation
629  PathDiagnosticLocation::createDeclBegin(const LocationContext *LC,
630                                          const SourceManager &SM) {
631  // FIXME: Should handle CXXTryStmt if analyser starts supporting C++.
632  if (const CompoundStmt *CS =
633        dyn_cast_or_null<CompoundStmt>(LC->getDecl()->getBody()))
634    if (!CS->body_empty()) {
635      SourceLocation Loc = (*CS->body_begin())->getLocStart();
636      return PathDiagnosticLocation(Loc, SM, SingleLocK);
637    }
638
639  return PathDiagnosticLocation();
640}
641
642PathDiagnosticLocation
643  PathDiagnosticLocation::createDeclEnd(const LocationContext *LC,
644                                        const SourceManager &SM) {
645  SourceLocation L = LC->getDecl()->getBodyRBrace();
646  return PathDiagnosticLocation(L, SM, SingleLocK);
647}
648
649PathDiagnosticLocation
650  PathDiagnosticLocation::create(const ProgramPoint& P,
651                                 const SourceManager &SMng) {
652
653  const Stmt* S = 0;
654  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
655    const CFGBlock *BSrc = BE->getSrc();
656    S = BSrc->getTerminatorCondition();
657  } else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
658    S = SP->getStmt();
659    if (P.getAs<PostStmtPurgeDeadSymbols>())
660      return PathDiagnosticLocation::createEnd(S, SMng, P.getLocationContext());
661  } else if (Optional<PostInitializer> PIP = P.getAs<PostInitializer>()) {
662    return PathDiagnosticLocation(PIP->getInitializer()->getSourceLocation(),
663                                  SMng);
664  } else if (Optional<PostImplicitCall> PIE = P.getAs<PostImplicitCall>()) {
665    return PathDiagnosticLocation(PIE->getLocation(), SMng);
666  } else if (Optional<CallEnter> CE = P.getAs<CallEnter>()) {
667    return getLocationForCaller(CE->getCalleeContext(),
668                                CE->getLocationContext(),
669                                SMng);
670  } else if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>()) {
671    return getLocationForCaller(CEE->getCalleeContext(),
672                                CEE->getLocationContext(),
673                                SMng);
674  } else {
675    llvm_unreachable("Unexpected ProgramPoint");
676  }
677
678  return PathDiagnosticLocation(S, SMng, P.getLocationContext());
679}
680
681const Stmt *PathDiagnosticLocation::getStmt(const ExplodedNode *N) {
682  ProgramPoint P = N->getLocation();
683  if (Optional<StmtPoint> SP = P.getAs<StmtPoint>())
684    return SP->getStmt();
685  if (Optional<BlockEdge> BE = P.getAs<BlockEdge>())
686    return BE->getSrc()->getTerminator();
687  if (Optional<CallEnter> CE = P.getAs<CallEnter>())
688    return CE->getCallExpr();
689  if (Optional<CallExitEnd> CEE = P.getAs<CallExitEnd>())
690    return CEE->getCalleeContext()->getCallSite();
691  if (Optional<PostInitializer> PIPP = P.getAs<PostInitializer>())
692    return PIPP->getInitializer()->getInit();
693
694  return 0;
695}
696
697const Stmt *PathDiagnosticLocation::getNextStmt(const ExplodedNode *N) {
698  for (N = N->getFirstSucc(); N; N = N->getFirstSucc()) {
699    if (const Stmt *S = getStmt(N)) {
700      // Check if the statement is '?' or '&&'/'||'.  These are "merges",
701      // not actual statement points.
702      switch (S->getStmtClass()) {
703        case Stmt::ChooseExprClass:
704        case Stmt::BinaryConditionalOperatorClass:
705        case Stmt::ConditionalOperatorClass:
706          continue;
707        case Stmt::BinaryOperatorClass: {
708          BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
709          if (Op == BO_LAnd || Op == BO_LOr)
710            continue;
711          break;
712        }
713        default:
714          break;
715      }
716      // We found the statement, so return it.
717      return S;
718    }
719  }
720
721  return 0;
722}
723
724PathDiagnosticLocation
725  PathDiagnosticLocation::createEndOfPath(const ExplodedNode *N,
726                                          const SourceManager &SM) {
727  assert(N && "Cannot create a location with a null node.");
728  const Stmt *S = getStmt(N);
729
730  if (!S)
731    S = getNextStmt(N);
732
733  if (S) {
734    ProgramPoint P = N->getLocation();
735    const LocationContext *LC = N->getLocationContext();
736
737    // For member expressions, return the location of the '.' or '->'.
738    if (const MemberExpr *ME = dyn_cast<MemberExpr>(S))
739      return PathDiagnosticLocation::createMemberLoc(ME, SM);
740
741    // For binary operators, return the location of the operator.
742    if (const BinaryOperator *B = dyn_cast<BinaryOperator>(S))
743      return PathDiagnosticLocation::createOperatorLoc(B, SM);
744
745    if (P.getAs<PostStmtPurgeDeadSymbols>())
746      return PathDiagnosticLocation::createEnd(S, SM, LC);
747
748    if (S->getLocStart().isValid())
749      return PathDiagnosticLocation(S, SM, LC);
750    return PathDiagnosticLocation(getValidSourceLocation(S, LC), SM);
751  }
752
753  return createDeclEnd(N->getLocationContext(), SM);
754}
755
756PathDiagnosticLocation PathDiagnosticLocation::createSingleLocation(
757                                           const PathDiagnosticLocation &PDL) {
758  FullSourceLoc L = PDL.asLocation();
759  return PathDiagnosticLocation(L, L.getManager(), SingleLocK);
760}
761
762FullSourceLoc
763  PathDiagnosticLocation::genLocation(SourceLocation L,
764                                      LocationOrAnalysisDeclContext LAC) const {
765  assert(isValid());
766  // Note that we want a 'switch' here so that the compiler can warn us in
767  // case we add more cases.
768  switch (K) {
769    case SingleLocK:
770    case RangeK:
771      break;
772    case StmtK:
773      // Defensive checking.
774      if (!S)
775        break;
776      return FullSourceLoc(getValidSourceLocation(S, LAC),
777                           const_cast<SourceManager&>(*SM));
778    case DeclK:
779      // Defensive checking.
780      if (!D)
781        break;
782      return FullSourceLoc(D->getLocation(), const_cast<SourceManager&>(*SM));
783  }
784
785  return FullSourceLoc(L, const_cast<SourceManager&>(*SM));
786}
787
788PathDiagnosticRange
789  PathDiagnosticLocation::genRange(LocationOrAnalysisDeclContext LAC) const {
790  assert(isValid());
791  // Note that we want a 'switch' here so that the compiler can warn us in
792  // case we add more cases.
793  switch (K) {
794    case SingleLocK:
795      return PathDiagnosticRange(SourceRange(Loc,Loc), true);
796    case RangeK:
797      break;
798    case StmtK: {
799      const Stmt *S = asStmt();
800      switch (S->getStmtClass()) {
801        default:
802          break;
803        case Stmt::DeclStmtClass: {
804          const DeclStmt *DS = cast<DeclStmt>(S);
805          if (DS->isSingleDecl()) {
806            // Should always be the case, but we'll be defensive.
807            return SourceRange(DS->getLocStart(),
808                               DS->getSingleDecl()->getLocation());
809          }
810          break;
811        }
812          // FIXME: Provide better range information for different
813          //  terminators.
814        case Stmt::IfStmtClass:
815        case Stmt::WhileStmtClass:
816        case Stmt::DoStmtClass:
817        case Stmt::ForStmtClass:
818        case Stmt::ChooseExprClass:
819        case Stmt::IndirectGotoStmtClass:
820        case Stmt::SwitchStmtClass:
821        case Stmt::BinaryConditionalOperatorClass:
822        case Stmt::ConditionalOperatorClass:
823        case Stmt::ObjCForCollectionStmtClass: {
824          SourceLocation L = getValidSourceLocation(S, LAC);
825          return SourceRange(L, L);
826        }
827      }
828      SourceRange R = S->getSourceRange();
829      if (R.isValid())
830        return R;
831      break;
832    }
833    case DeclK:
834      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
835        return MD->getSourceRange();
836      if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
837        if (Stmt *Body = FD->getBody())
838          return Body->getSourceRange();
839      }
840      else {
841        SourceLocation L = D->getLocation();
842        return PathDiagnosticRange(SourceRange(L, L), true);
843      }
844  }
845
846  return SourceRange(Loc,Loc);
847}
848
849void PathDiagnosticLocation::flatten() {
850  if (K == StmtK) {
851    K = RangeK;
852    S = 0;
853    D = 0;
854  }
855  else if (K == DeclK) {
856    K = SingleLocK;
857    S = 0;
858    D = 0;
859  }
860}
861
862//===----------------------------------------------------------------------===//
863// Manipulation of PathDiagnosticCallPieces.
864//===----------------------------------------------------------------------===//
865
866PathDiagnosticCallPiece *
867PathDiagnosticCallPiece::construct(const ExplodedNode *N,
868                                   const CallExitEnd &CE,
869                                   const SourceManager &SM) {
870  const Decl *caller = CE.getLocationContext()->getDecl();
871  PathDiagnosticLocation pos = getLocationForCaller(CE.getCalleeContext(),
872                                                    CE.getLocationContext(),
873                                                    SM);
874  return new PathDiagnosticCallPiece(caller, pos);
875}
876
877PathDiagnosticCallPiece *
878PathDiagnosticCallPiece::construct(PathPieces &path,
879                                   const Decl *caller) {
880  PathDiagnosticCallPiece *C = new PathDiagnosticCallPiece(path, caller);
881  path.clear();
882  path.push_front(C);
883  return C;
884}
885
886void PathDiagnosticCallPiece::setCallee(const CallEnter &CE,
887                                        const SourceManager &SM) {
888  const StackFrameContext *CalleeCtx = CE.getCalleeContext();
889  Callee = CalleeCtx->getDecl();
890
891  callEnterWithin = PathDiagnosticLocation::createBegin(Callee, SM);
892  callEnter = getLocationForCaller(CalleeCtx, CE.getLocationContext(), SM);
893}
894
895static inline void describeClass(raw_ostream &Out, const CXXRecordDecl *D,
896                                 StringRef Prefix = StringRef()) {
897  if (!D->getIdentifier())
898    return;
899  Out << Prefix << '\'' << *D << '\'';
900}
901
902static bool describeCodeDecl(raw_ostream &Out, const Decl *D,
903                             bool ExtendedDescription,
904                             StringRef Prefix = StringRef()) {
905  if (!D)
906    return false;
907
908  if (isa<BlockDecl>(D)) {
909    if (ExtendedDescription)
910      Out << Prefix << "anonymous block";
911    return ExtendedDescription;
912  }
913
914  if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
915    Out << Prefix;
916    if (ExtendedDescription && !MD->isUserProvided()) {
917      if (MD->isExplicitlyDefaulted())
918        Out << "defaulted ";
919      else
920        Out << "implicit ";
921    }
922
923    if (const CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(MD)) {
924      if (CD->isDefaultConstructor())
925        Out << "default ";
926      else if (CD->isCopyConstructor())
927        Out << "copy ";
928      else if (CD->isMoveConstructor())
929        Out << "move ";
930
931      Out << "constructor";
932      describeClass(Out, MD->getParent(), " for ");
933
934    } else if (isa<CXXDestructorDecl>(MD)) {
935      if (!MD->isUserProvided()) {
936        Out << "destructor";
937        describeClass(Out, MD->getParent(), " for ");
938      } else {
939        // Use ~Foo for explicitly-written destructors.
940        Out << "'" << *MD << "'";
941      }
942
943    } else if (MD->isCopyAssignmentOperator()) {
944        Out << "copy assignment operator";
945        describeClass(Out, MD->getParent(), " for ");
946
947    } else if (MD->isMoveAssignmentOperator()) {
948        Out << "move assignment operator";
949        describeClass(Out, MD->getParent(), " for ");
950
951    } else {
952      if (MD->getParent()->getIdentifier())
953        Out << "'" << *MD->getParent() << "::" << *MD << "'";
954      else
955        Out << "'" << *MD << "'";
956    }
957
958    return true;
959  }
960
961  Out << Prefix << '\'' << cast<NamedDecl>(*D) << '\'';
962  return true;
963}
964
965IntrusiveRefCntPtr<PathDiagnosticEventPiece>
966PathDiagnosticCallPiece::getCallEnterEvent() const {
967  if (!Callee)
968    return 0;
969
970  SmallString<256> buf;
971  llvm::raw_svector_ostream Out(buf);
972
973  Out << "Calling ";
974  describeCodeDecl(Out, Callee, /*ExtendedDescription=*/true);
975
976  assert(callEnter.asLocation().isValid());
977  return new PathDiagnosticEventPiece(callEnter, Out.str());
978}
979
980IntrusiveRefCntPtr<PathDiagnosticEventPiece>
981PathDiagnosticCallPiece::getCallEnterWithinCallerEvent() const {
982  if (!callEnterWithin.asLocation().isValid())
983    return 0;
984  if (Callee->isImplicit() || !Callee->hasBody())
985    return 0;
986  if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Callee))
987    if (MD->isDefaulted())
988      return 0;
989
990  SmallString<256> buf;
991  llvm::raw_svector_ostream Out(buf);
992
993  Out << "Entered call";
994  describeCodeDecl(Out, Caller, /*ExtendedDescription=*/false, " from ");
995
996  return new PathDiagnosticEventPiece(callEnterWithin, Out.str());
997}
998
999IntrusiveRefCntPtr<PathDiagnosticEventPiece>
1000PathDiagnosticCallPiece::getCallExitEvent() const {
1001  if (NoExit)
1002    return 0;
1003
1004  SmallString<256> buf;
1005  llvm::raw_svector_ostream Out(buf);
1006
1007  if (!CallStackMessage.empty()) {
1008    Out << CallStackMessage;
1009  } else {
1010    bool DidDescribe = describeCodeDecl(Out, Callee,
1011                                        /*ExtendedDescription=*/false,
1012                                        "Returning from ");
1013    if (!DidDescribe)
1014      Out << "Returning to caller";
1015  }
1016
1017  assert(callReturn.asLocation().isValid());
1018  return new PathDiagnosticEventPiece(callReturn, Out.str());
1019}
1020
1021static void compute_path_size(const PathPieces &pieces, unsigned &size) {
1022  for (PathPieces::const_iterator it = pieces.begin(),
1023                                  et = pieces.end(); it != et; ++it) {
1024    const PathDiagnosticPiece *piece = it->getPtr();
1025    if (const PathDiagnosticCallPiece *cp =
1026        dyn_cast<PathDiagnosticCallPiece>(piece)) {
1027      compute_path_size(cp->path, size);
1028    }
1029    else
1030      ++size;
1031  }
1032}
1033
1034unsigned PathDiagnostic::full_size() {
1035  unsigned size = 0;
1036  compute_path_size(path, size);
1037  return size;
1038}
1039
1040//===----------------------------------------------------------------------===//
1041// FoldingSet profiling methods.
1042//===----------------------------------------------------------------------===//
1043
1044void PathDiagnosticLocation::Profile(llvm::FoldingSetNodeID &ID) const {
1045  ID.AddInteger(Range.getBegin().getRawEncoding());
1046  ID.AddInteger(Range.getEnd().getRawEncoding());
1047  ID.AddInteger(Loc.getRawEncoding());
1048  return;
1049}
1050
1051void PathDiagnosticPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1052  ID.AddInteger((unsigned) getKind());
1053  ID.AddString(str);
1054  // FIXME: Add profiling support for code hints.
1055  ID.AddInteger((unsigned) getDisplayHint());
1056  ArrayRef<SourceRange> Ranges = getRanges();
1057  for (ArrayRef<SourceRange>::iterator I = Ranges.begin(), E = Ranges.end();
1058                                        I != E; ++I) {
1059    ID.AddInteger(I->getBegin().getRawEncoding());
1060    ID.AddInteger(I->getEnd().getRawEncoding());
1061  }
1062}
1063
1064void PathDiagnosticCallPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1065  PathDiagnosticPiece::Profile(ID);
1066  for (PathPieces::const_iterator it = path.begin(),
1067       et = path.end(); it != et; ++it) {
1068    ID.Add(**it);
1069  }
1070}
1071
1072void PathDiagnosticSpotPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1073  PathDiagnosticPiece::Profile(ID);
1074  ID.Add(Pos);
1075}
1076
1077void PathDiagnosticControlFlowPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1078  PathDiagnosticPiece::Profile(ID);
1079  for (const_iterator I = begin(), E = end(); I != E; ++I)
1080    ID.Add(*I);
1081}
1082
1083void PathDiagnosticMacroPiece::Profile(llvm::FoldingSetNodeID &ID) const {
1084  PathDiagnosticSpotPiece::Profile(ID);
1085  for (PathPieces::const_iterator I = subPieces.begin(), E = subPieces.end();
1086       I != E; ++I)
1087    ID.Add(**I);
1088}
1089
1090void PathDiagnostic::Profile(llvm::FoldingSetNodeID &ID) const {
1091  ID.Add(getLocation());
1092  ID.AddString(BugType);
1093  ID.AddString(VerboseDesc);
1094  ID.AddString(Category);
1095}
1096
1097void PathDiagnostic::FullProfile(llvm::FoldingSetNodeID &ID) const {
1098  Profile(ID);
1099  for (PathPieces::const_iterator I = path.begin(), E = path.end(); I != E; ++I)
1100    ID.Add(**I);
1101  for (meta_iterator I = meta_begin(), E = meta_end(); I != E; ++I)
1102    ID.AddString(*I);
1103}
1104
1105StackHintGenerator::~StackHintGenerator() {}
1106
1107std::string StackHintGeneratorForSymbol::getMessage(const ExplodedNode *N){
1108  ProgramPoint P = N->getLocation();
1109  CallExitEnd CExit = P.castAs<CallExitEnd>();
1110
1111  // FIXME: Use CallEvent to abstract this over all calls.
1112  const Stmt *CallSite = CExit.getCalleeContext()->getCallSite();
1113  const CallExpr *CE = dyn_cast_or_null<CallExpr>(CallSite);
1114  if (!CE)
1115    return "";
1116
1117  if (!N)
1118    return getMessageForSymbolNotFound();
1119
1120  // Check if one of the parameters are set to the interesting symbol.
1121  ProgramStateRef State = N->getState();
1122  const LocationContext *LCtx = N->getLocationContext();
1123  unsigned ArgIndex = 0;
1124  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
1125                                    E = CE->arg_end(); I != E; ++I, ++ArgIndex){
1126    SVal SV = State->getSVal(*I, LCtx);
1127
1128    // Check if the variable corresponding to the symbol is passed by value.
1129    SymbolRef AS = SV.getAsLocSymbol();
1130    if (AS == Sym) {
1131      return getMessageForArg(*I, ArgIndex);
1132    }
1133
1134    // Check if the parameter is a pointer to the symbol.
1135    if (Optional<loc::MemRegionVal> Reg = SV.getAs<loc::MemRegionVal>()) {
1136      SVal PSV = State->getSVal(Reg->getRegion());
1137      SymbolRef AS = PSV.getAsLocSymbol();
1138      if (AS == Sym) {
1139        return getMessageForArg(*I, ArgIndex);
1140      }
1141    }
1142  }
1143
1144  // Check if we are returning the interesting symbol.
1145  SVal SV = State->getSVal(CE, LCtx);
1146  SymbolRef RetSym = SV.getAsLocSymbol();
1147  if (RetSym == Sym) {
1148    return getMessageForReturn(CE);
1149  }
1150
1151  return getMessageForSymbolNotFound();
1152}
1153
1154std::string StackHintGeneratorForSymbol::getMessageForArg(const Expr *ArgE,
1155                                                          unsigned ArgIndex) {
1156  // Printed parameters start at 1, not 0.
1157  ++ArgIndex;
1158
1159  SmallString<200> buf;
1160  llvm::raw_svector_ostream os(buf);
1161
1162  os << Msg << " via " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
1163     << " parameter";
1164
1165  return os.str();
1166}
1167