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