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