1// RetainCountDiagnostics.cpp - Checks for leaks and other issues -*- C++ -*--//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9//  This file defines diagnostics for RetainCountChecker, which implements
10//  a reference count checker for Core Foundation and Cocoa on (Mac OS X).
11//
12//===----------------------------------------------------------------------===//
13
14#include "RetainCountDiagnostics.h"
15#include "RetainCountChecker.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include <optional>
19
20using namespace clang;
21using namespace ento;
22using namespace retaincountchecker;
23
24StringRef RefCountBug::bugTypeToName(RefCountBug::RefCountBugKind BT) {
25  switch (BT) {
26  case UseAfterRelease:
27    return "Use-after-release";
28  case ReleaseNotOwned:
29    return "Bad release";
30  case DeallocNotOwned:
31    return "-dealloc sent to non-exclusively owned object";
32  case FreeNotOwned:
33    return "freeing non-exclusively owned object";
34  case OverAutorelease:
35    return "Object autoreleased too many times";
36  case ReturnNotOwnedForOwned:
37    return "Method should return an owned object";
38  case LeakWithinFunction:
39    return "Leak";
40  case LeakAtReturn:
41    return "Leak of returned object";
42  }
43  llvm_unreachable("Unknown RefCountBugKind");
44}
45
46StringRef RefCountBug::getDescription() const {
47  switch (BT) {
48  case UseAfterRelease:
49    return "Reference-counted object is used after it is released";
50  case ReleaseNotOwned:
51    return "Incorrect decrement of the reference count of an object that is "
52           "not owned at this point by the caller";
53  case DeallocNotOwned:
54    return "-dealloc sent to object that may be referenced elsewhere";
55  case FreeNotOwned:
56    return  "'free' called on an object that may be referenced elsewhere";
57  case OverAutorelease:
58    return "Object autoreleased too many times";
59  case ReturnNotOwnedForOwned:
60    return "Object with a +0 retain count returned to caller where a +1 "
61           "(owning) retain count is expected";
62  case LeakWithinFunction:
63  case LeakAtReturn:
64    return "";
65  }
66  llvm_unreachable("Unknown RefCountBugKind");
67}
68
69RefCountBug::RefCountBug(CheckerNameRef Checker, RefCountBugKind BT)
70    : BugType(Checker, bugTypeToName(BT), categories::MemoryRefCount,
71              /*SuppressOnSink=*/BT == LeakWithinFunction ||
72                  BT == LeakAtReturn),
73      BT(BT) {}
74
75static bool isNumericLiteralExpression(const Expr *E) {
76  // FIXME: This set of cases was copied from SemaExprObjC.
77  return isa<IntegerLiteral, CharacterLiteral, FloatingLiteral,
78             ObjCBoolLiteralExpr, CXXBoolLiteralExpr>(E);
79}
80
81/// If type represents a pointer to CXXRecordDecl,
82/// and is not a typedef, return the decl name.
83/// Otherwise, return the serialization of type.
84static std::string getPrettyTypeName(QualType QT) {
85  QualType PT = QT->getPointeeType();
86  if (!PT.isNull() && !QT->getAs<TypedefType>())
87    if (const auto *RD = PT->getAsCXXRecordDecl())
88      return std::string(RD->getName());
89  return QT.getAsString();
90}
91
92/// Write information about the type state change to @c os,
93/// return whether the note should be generated.
94static bool shouldGenerateNote(llvm::raw_string_ostream &os,
95                               const RefVal *PrevT,
96                               const RefVal &CurrV,
97                               bool DeallocSent) {
98  // Get the previous type state.
99  RefVal PrevV = *PrevT;
100
101  // Specially handle -dealloc.
102  if (DeallocSent) {
103    // Determine if the object's reference count was pushed to zero.
104    assert(!PrevV.hasSameState(CurrV) && "The state should have changed.");
105    // We may not have transitioned to 'release' if we hit an error.
106    // This case is handled elsewhere.
107    if (CurrV.getKind() == RefVal::Released) {
108      assert(CurrV.getCombinedCounts() == 0);
109      os << "Object released by directly sending the '-dealloc' message";
110      return true;
111    }
112  }
113
114  // Determine if the typestate has changed.
115  if (!PrevV.hasSameState(CurrV))
116    switch (CurrV.getKind()) {
117    case RefVal::Owned:
118    case RefVal::NotOwned:
119      if (PrevV.getCount() == CurrV.getCount()) {
120        // Did an autorelease message get sent?
121        if (PrevV.getAutoreleaseCount() == CurrV.getAutoreleaseCount())
122          return false;
123
124        assert(PrevV.getAutoreleaseCount() < CurrV.getAutoreleaseCount());
125        os << "Object autoreleased";
126        return true;
127      }
128
129      if (PrevV.getCount() > CurrV.getCount())
130        os << "Reference count decremented.";
131      else
132        os << "Reference count incremented.";
133
134      if (unsigned Count = CurrV.getCount())
135        os << " The object now has a +" << Count << " retain count.";
136
137      return true;
138
139    case RefVal::Released:
140      if (CurrV.getIvarAccessHistory() ==
141              RefVal::IvarAccessHistory::ReleasedAfterDirectAccess &&
142          CurrV.getIvarAccessHistory() != PrevV.getIvarAccessHistory()) {
143        os << "Strong instance variable relinquished. ";
144      }
145      os << "Object released.";
146      return true;
147
148    case RefVal::ReturnedOwned:
149      // Autoreleases can be applied after marking a node ReturnedOwned.
150      if (CurrV.getAutoreleaseCount())
151        return false;
152
153      os << "Object returned to caller as an owning reference (single "
154            "retain count transferred to caller)";
155      return true;
156
157    case RefVal::ReturnedNotOwned:
158      os << "Object returned to caller with a +0 retain count";
159      return true;
160
161    default:
162      return false;
163    }
164  return true;
165}
166
167/// Finds argument index of the out paramter in the call @c S
168/// corresponding to the symbol @c Sym.
169/// If none found, returns std::nullopt.
170static std::optional<unsigned>
171findArgIdxOfSymbol(ProgramStateRef CurrSt, const LocationContext *LCtx,
172                   SymbolRef &Sym, std::optional<CallEventRef<>> CE) {
173  if (!CE)
174    return std::nullopt;
175
176  for (unsigned Idx = 0; Idx < (*CE)->getNumArgs(); Idx++)
177    if (const MemRegion *MR = (*CE)->getArgSVal(Idx).getAsRegion())
178      if (const auto *TR = dyn_cast<TypedValueRegion>(MR))
179        if (CurrSt->getSVal(MR, TR->getValueType()).getAsSymbol() == Sym)
180          return Idx;
181
182  return std::nullopt;
183}
184
185static std::optional<std::string> findMetaClassAlloc(const Expr *Callee) {
186  if (const auto *ME = dyn_cast<MemberExpr>(Callee)) {
187    if (ME->getMemberDecl()->getNameAsString() != "alloc")
188      return std::nullopt;
189    const Expr *This = ME->getBase()->IgnoreParenImpCasts();
190    if (const auto *DRE = dyn_cast<DeclRefExpr>(This)) {
191      const ValueDecl *VD = DRE->getDecl();
192      if (VD->getNameAsString() != "metaClass")
193        return std::nullopt;
194
195      if (const auto *RD = dyn_cast<CXXRecordDecl>(VD->getDeclContext()))
196        return RD->getNameAsString();
197
198    }
199  }
200  return std::nullopt;
201}
202
203static std::string findAllocatedObjectName(const Stmt *S, QualType QT) {
204  if (const auto *CE = dyn_cast<CallExpr>(S))
205    if (auto Out = findMetaClassAlloc(CE->getCallee()))
206      return *Out;
207  return getPrettyTypeName(QT);
208}
209
210static void generateDiagnosticsForCallLike(ProgramStateRef CurrSt,
211                                           const LocationContext *LCtx,
212                                           const RefVal &CurrV, SymbolRef &Sym,
213                                           const Stmt *S,
214                                           llvm::raw_string_ostream &os) {
215  CallEventManager &Mgr = CurrSt->getStateManager().getCallEventManager();
216  if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
217    // Get the name of the callee (if it is available)
218    // from the tracked SVal.
219    SVal X = CurrSt->getSValAsScalarOrLoc(CE->getCallee(), LCtx);
220    const FunctionDecl *FD = X.getAsFunctionDecl();
221
222    // If failed, try to get it from AST.
223    if (!FD)
224      FD = dyn_cast<FunctionDecl>(CE->getCalleeDecl());
225
226    if (const auto *MD = dyn_cast<CXXMethodDecl>(CE->getCalleeDecl())) {
227      os << "Call to method '" << MD->getQualifiedNameAsString() << '\'';
228    } else if (FD) {
229      os << "Call to function '" << FD->getQualifiedNameAsString() << '\'';
230    } else {
231      os << "function call";
232    }
233  } else if (isa<CXXNewExpr>(S)) {
234    os << "Operator 'new'";
235  } else {
236    assert(isa<ObjCMessageExpr>(S));
237    CallEventRef<ObjCMethodCall> Call = Mgr.getObjCMethodCall(
238        cast<ObjCMessageExpr>(S), CurrSt, LCtx, {nullptr, 0});
239
240    switch (Call->getMessageKind()) {
241    case OCM_Message:
242      os << "Method";
243      break;
244    case OCM_PropertyAccess:
245      os << "Property";
246      break;
247    case OCM_Subscript:
248      os << "Subscript";
249      break;
250    }
251  }
252
253  std::optional<CallEventRef<>> CE = Mgr.getCall(S, CurrSt, LCtx, {nullptr, 0});
254  auto Idx = findArgIdxOfSymbol(CurrSt, LCtx, Sym, CE);
255
256  // If index is not found, we assume that the symbol was returned.
257  if (!Idx) {
258    os << " returns ";
259  } else {
260    os << " writes ";
261  }
262
263  if (CurrV.getObjKind() == ObjKind::CF) {
264    os << "a Core Foundation object of type '" << Sym->getType() << "' with a ";
265  } else if (CurrV.getObjKind() == ObjKind::OS) {
266    os << "an OSObject of type '" << findAllocatedObjectName(S, Sym->getType())
267       << "' with a ";
268  } else if (CurrV.getObjKind() == ObjKind::Generalized) {
269    os << "an object of type '" << Sym->getType() << "' with a ";
270  } else {
271    assert(CurrV.getObjKind() == ObjKind::ObjC);
272    QualType T = Sym->getType();
273    if (!isa<ObjCObjectPointerType>(T)) {
274      os << "an Objective-C object with a ";
275    } else {
276      const ObjCObjectPointerType *PT = cast<ObjCObjectPointerType>(T);
277      os << "an instance of " << PT->getPointeeType() << " with a ";
278    }
279  }
280
281  if (CurrV.isOwned()) {
282    os << "+1 retain count";
283  } else {
284    assert(CurrV.isNotOwned());
285    os << "+0 retain count";
286  }
287
288  if (Idx) {
289    os << " into an out parameter '";
290    const ParmVarDecl *PVD = (*CE)->parameters()[*Idx];
291    PVD->getNameForDiagnostic(os, PVD->getASTContext().getPrintingPolicy(),
292                              /*Qualified=*/false);
293    os << "'";
294
295    QualType RT = (*CE)->getResultType();
296    if (!RT.isNull() && !RT->isVoidType()) {
297      SVal RV = (*CE)->getReturnValue();
298      if (CurrSt->isNull(RV).isConstrainedTrue()) {
299        os << " (assuming the call returns zero)";
300      } else if (CurrSt->isNonNull(RV).isConstrainedTrue()) {
301        os << " (assuming the call returns non-zero)";
302      }
303
304    }
305  }
306}
307
308namespace clang {
309namespace ento {
310namespace retaincountchecker {
311
312class RefCountReportVisitor : public BugReporterVisitor {
313protected:
314  SymbolRef Sym;
315
316public:
317  RefCountReportVisitor(SymbolRef sym) : Sym(sym) {}
318
319  void Profile(llvm::FoldingSetNodeID &ID) const override {
320    static int x = 0;
321    ID.AddPointer(&x);
322    ID.AddPointer(Sym);
323  }
324
325  PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
326                                   BugReporterContext &BRC,
327                                   PathSensitiveBugReport &BR) override;
328
329  PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC,
330                                    const ExplodedNode *N,
331                                    PathSensitiveBugReport &BR) override;
332};
333
334class RefLeakReportVisitor : public RefCountReportVisitor {
335public:
336  RefLeakReportVisitor(SymbolRef Sym, const MemRegion *LastBinding)
337      : RefCountReportVisitor(Sym), LastBinding(LastBinding) {}
338
339  PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC,
340                                    const ExplodedNode *N,
341                                    PathSensitiveBugReport &BR) override;
342
343private:
344  const MemRegion *LastBinding;
345};
346
347} // end namespace retaincountchecker
348} // end namespace ento
349} // end namespace clang
350
351
352/// Find the first node with the parent stack frame.
353static const ExplodedNode *getCalleeNode(const ExplodedNode *Pred) {
354  const StackFrameContext *SC = Pred->getStackFrame();
355  if (SC->inTopFrame())
356    return nullptr;
357  const StackFrameContext *PC = SC->getParent()->getStackFrame();
358  if (!PC)
359    return nullptr;
360
361  const ExplodedNode *N = Pred;
362  while (N && N->getStackFrame() != PC) {
363    N = N->getFirstPred();
364  }
365  return N;
366}
367
368
369/// Insert a diagnostic piece at function exit
370/// if a function parameter is annotated as "os_consumed",
371/// but it does not actually consume the reference.
372static std::shared_ptr<PathDiagnosticEventPiece>
373annotateConsumedSummaryMismatch(const ExplodedNode *N,
374                                CallExitBegin &CallExitLoc,
375                                const SourceManager &SM,
376                                CallEventManager &CEMgr) {
377
378  const ExplodedNode *CN = getCalleeNode(N);
379  if (!CN)
380    return nullptr;
381
382  CallEventRef<> Call = CEMgr.getCaller(N->getStackFrame(), N->getState());
383
384  std::string sbuf;
385  llvm::raw_string_ostream os(sbuf);
386  ArrayRef<const ParmVarDecl *> Parameters = Call->parameters();
387  for (unsigned I=0; I < Call->getNumArgs() && I < Parameters.size(); ++I) {
388    const ParmVarDecl *PVD = Parameters[I];
389
390    if (!PVD->hasAttr<OSConsumedAttr>())
391      continue;
392
393    if (SymbolRef SR = Call->getArgSVal(I).getAsLocSymbol()) {
394      const RefVal *CountBeforeCall = getRefBinding(CN->getState(), SR);
395      const RefVal *CountAtExit = getRefBinding(N->getState(), SR);
396
397      if (!CountBeforeCall || !CountAtExit)
398        continue;
399
400      unsigned CountBefore = CountBeforeCall->getCount();
401      unsigned CountAfter = CountAtExit->getCount();
402
403      bool AsExpected = CountBefore > 0 && CountAfter == CountBefore - 1;
404      if (!AsExpected) {
405        os << "Parameter '";
406        PVD->getNameForDiagnostic(os, PVD->getASTContext().getPrintingPolicy(),
407                                  /*Qualified=*/false);
408        os << "' is marked as consuming, but the function did not consume "
409           << "the reference\n";
410      }
411    }
412  }
413
414  if (os.str().empty())
415    return nullptr;
416
417  PathDiagnosticLocation L = PathDiagnosticLocation::create(CallExitLoc, SM);
418  return std::make_shared<PathDiagnosticEventPiece>(L, os.str());
419}
420
421/// Annotate the parameter at the analysis entry point.
422static std::shared_ptr<PathDiagnosticEventPiece>
423annotateStartParameter(const ExplodedNode *N, SymbolRef Sym,
424                       const SourceManager &SM) {
425  auto PP = N->getLocationAs<BlockEdge>();
426  if (!PP)
427    return nullptr;
428
429  const CFGBlock *Src = PP->getSrc();
430  const RefVal *CurrT = getRefBinding(N->getState(), Sym);
431
432  if (&Src->getParent()->getEntry() != Src || !CurrT ||
433      getRefBinding(N->getFirstPred()->getState(), Sym))
434    return nullptr;
435
436  const auto *VR = cast<VarRegion>(cast<SymbolRegionValue>(Sym)->getRegion());
437  const auto *PVD = cast<ParmVarDecl>(VR->getDecl());
438  PathDiagnosticLocation L = PathDiagnosticLocation(PVD, SM);
439
440  std::string s;
441  llvm::raw_string_ostream os(s);
442  os << "Parameter '" << PVD->getDeclName() << "' starts at +";
443  if (CurrT->getCount() == 1) {
444    os << "1, as it is marked as consuming";
445  } else {
446    assert(CurrT->getCount() == 0);
447    os << "0";
448  }
449  return std::make_shared<PathDiagnosticEventPiece>(L, os.str());
450}
451
452PathDiagnosticPieceRef
453RefCountReportVisitor::VisitNode(const ExplodedNode *N, BugReporterContext &BRC,
454                                 PathSensitiveBugReport &BR) {
455
456  const auto &BT = static_cast<const RefCountBug&>(BR.getBugType());
457
458  bool IsFreeUnowned = BT.getBugType() == RefCountBug::FreeNotOwned ||
459                       BT.getBugType() == RefCountBug::DeallocNotOwned;
460
461  const SourceManager &SM = BRC.getSourceManager();
462  CallEventManager &CEMgr = BRC.getStateManager().getCallEventManager();
463  if (auto CE = N->getLocationAs<CallExitBegin>())
464    if (auto PD = annotateConsumedSummaryMismatch(N, *CE, SM, CEMgr))
465      return PD;
466
467  if (auto PD = annotateStartParameter(N, Sym, SM))
468    return PD;
469
470  // FIXME: We will eventually need to handle non-statement-based events
471  // (__attribute__((cleanup))).
472  if (!N->getLocation().getAs<StmtPoint>())
473    return nullptr;
474
475  // Check if the type state has changed.
476  const ExplodedNode *PrevNode = N->getFirstPred();
477  ProgramStateRef PrevSt = PrevNode->getState();
478  ProgramStateRef CurrSt = N->getState();
479  const LocationContext *LCtx = N->getLocationContext();
480
481  const RefVal* CurrT = getRefBinding(CurrSt, Sym);
482  if (!CurrT)
483    return nullptr;
484
485  const RefVal &CurrV = *CurrT;
486  const RefVal *PrevT = getRefBinding(PrevSt, Sym);
487
488  // Create a string buffer to constain all the useful things we want
489  // to tell the user.
490  std::string sbuf;
491  llvm::raw_string_ostream os(sbuf);
492
493  if (PrevT && IsFreeUnowned && CurrV.isNotOwned() && PrevT->isOwned()) {
494    os << "Object is now not exclusively owned";
495    auto Pos = PathDiagnosticLocation::create(N->getLocation(), SM);
496    return std::make_shared<PathDiagnosticEventPiece>(Pos, os.str());
497  }
498
499  // This is the allocation site since the previous node had no bindings
500  // for this symbol.
501  if (!PrevT) {
502    const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
503
504    if (isa<ObjCIvarRefExpr>(S) &&
505        isSynthesizedAccessor(LCtx->getStackFrame())) {
506      S = LCtx->getStackFrame()->getCallSite();
507    }
508
509    if (isa<ObjCArrayLiteral>(S)) {
510      os << "NSArray literal is an object with a +0 retain count";
511    } else if (isa<ObjCDictionaryLiteral>(S)) {
512      os << "NSDictionary literal is an object with a +0 retain count";
513    } else if (const ObjCBoxedExpr *BL = dyn_cast<ObjCBoxedExpr>(S)) {
514      if (isNumericLiteralExpression(BL->getSubExpr()))
515        os << "NSNumber literal is an object with a +0 retain count";
516      else {
517        const ObjCInterfaceDecl *BoxClass = nullptr;
518        if (const ObjCMethodDecl *Method = BL->getBoxingMethod())
519          BoxClass = Method->getClassInterface();
520
521        // We should always be able to find the boxing class interface,
522        // but consider this future-proofing.
523        if (BoxClass) {
524          os << *BoxClass << " b";
525        } else {
526          os << "B";
527        }
528
529        os << "oxed expression produces an object with a +0 retain count";
530      }
531    } else if (isa<ObjCIvarRefExpr>(S)) {
532      os << "Object loaded from instance variable";
533    } else {
534      generateDiagnosticsForCallLike(CurrSt, LCtx, CurrV, Sym, S, os);
535    }
536
537    PathDiagnosticLocation Pos(S, SM, N->getLocationContext());
538    return std::make_shared<PathDiagnosticEventPiece>(Pos, os.str());
539  }
540
541  // Gather up the effects that were performed on the object at this
542  // program point
543  bool DeallocSent = false;
544
545  const ProgramPointTag *Tag = N->getLocation().getTag();
546
547  if (Tag == &RetainCountChecker::getCastFailTag()) {
548    os << "Assuming dynamic cast returns null due to type mismatch";
549  }
550
551  if (Tag == &RetainCountChecker::getDeallocSentTag()) {
552    // We only have summaries attached to nodes after evaluating CallExpr and
553    // ObjCMessageExprs.
554    const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
555
556    if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
557      // Iterate through the parameter expressions and see if the symbol
558      // was ever passed as an argument.
559      unsigned i = 0;
560
561      for (auto AI=CE->arg_begin(), AE=CE->arg_end(); AI!=AE; ++AI, ++i) {
562
563        // Retrieve the value of the argument.  Is it the symbol
564        // we are interested in?
565        if (CurrSt->getSValAsScalarOrLoc(*AI, LCtx).getAsLocSymbol() != Sym)
566          continue;
567
568        // We have an argument.  Get the effect!
569        DeallocSent = true;
570      }
571    } else if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(S)) {
572      if (const Expr *receiver = ME->getInstanceReceiver()) {
573        if (CurrSt->getSValAsScalarOrLoc(receiver, LCtx)
574              .getAsLocSymbol() == Sym) {
575          // The symbol we are tracking is the receiver.
576          DeallocSent = true;
577        }
578      }
579    }
580  }
581
582  if (!shouldGenerateNote(os, PrevT, CurrV, DeallocSent))
583    return nullptr;
584
585  if (os.str().empty())
586    return nullptr; // We have nothing to say!
587
588  const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
589  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
590                                N->getLocationContext());
591  auto P = std::make_shared<PathDiagnosticEventPiece>(Pos, os.str());
592
593  // Add the range by scanning the children of the statement for any bindings
594  // to Sym.
595  for (const Stmt *Child : S->children())
596    if (const Expr *Exp = dyn_cast_or_null<Expr>(Child))
597      if (CurrSt->getSValAsScalarOrLoc(Exp, LCtx).getAsLocSymbol() == Sym) {
598        P->addRange(Exp->getSourceRange());
599        break;
600      }
601
602  return std::move(P);
603}
604
605static std::optional<std::string> describeRegion(const MemRegion *MR) {
606  if (const auto *VR = dyn_cast_or_null<VarRegion>(MR))
607    return std::string(VR->getDecl()->getName());
608  // Once we support more storage locations for bindings,
609  // this would need to be improved.
610  return std::nullopt;
611}
612
613using Bindings = llvm::SmallVector<std::pair<const MemRegion *, SVal>, 4>;
614
615namespace {
616class VarBindingsCollector : public StoreManager::BindingsHandler {
617  SymbolRef Sym;
618  Bindings &Result;
619
620public:
621  VarBindingsCollector(SymbolRef Sym, Bindings &ToFill)
622      : Sym(Sym), Result(ToFill) {}
623
624  bool HandleBinding(StoreManager &SMgr, Store Store, const MemRegion *R,
625                     SVal Val) override {
626    SymbolRef SymV = Val.getAsLocSymbol();
627    if (!SymV || SymV != Sym)
628      return true;
629
630    if (isa<NonParamVarRegion>(R))
631      Result.emplace_back(R, Val);
632
633    return true;
634  }
635};
636} // namespace
637
638Bindings getAllVarBindingsForSymbol(ProgramStateManager &Manager,
639                                    const ExplodedNode *Node, SymbolRef Sym) {
640  Bindings Result;
641  VarBindingsCollector Collector{Sym, Result};
642  while (Result.empty() && Node) {
643    Manager.iterBindings(Node->getState(), Collector);
644    Node = Node->getFirstPred();
645  }
646
647  return Result;
648}
649
650namespace {
651// Find the first node in the current function context that referred to the
652// tracked symbol and the memory location that value was stored to. Note, the
653// value is only reported if the allocation occurred in the same function as
654// the leak. The function can also return a location context, which should be
655// treated as interesting.
656struct AllocationInfo {
657  const ExplodedNode* N;
658  const MemRegion *R;
659  const LocationContext *InterestingMethodContext;
660  AllocationInfo(const ExplodedNode *InN,
661                 const MemRegion *InR,
662                 const LocationContext *InInterestingMethodContext) :
663    N(InN), R(InR), InterestingMethodContext(InInterestingMethodContext) {}
664};
665} // end anonymous namespace
666
667static AllocationInfo GetAllocationSite(ProgramStateManager &StateMgr,
668                                        const ExplodedNode *N, SymbolRef Sym) {
669  const ExplodedNode *AllocationNode = N;
670  const ExplodedNode *AllocationNodeInCurrentOrParentContext = N;
671  const MemRegion *FirstBinding = nullptr;
672  const LocationContext *LeakContext = N->getLocationContext();
673
674  // The location context of the init method called on the leaked object, if
675  // available.
676  const LocationContext *InitMethodContext = nullptr;
677
678  while (N) {
679    ProgramStateRef St = N->getState();
680    const LocationContext *NContext = N->getLocationContext();
681
682    if (!getRefBinding(St, Sym))
683      break;
684
685    StoreManager::FindUniqueBinding FB(Sym);
686    StateMgr.iterBindings(St, FB);
687
688    if (FB) {
689      const MemRegion *R = FB.getRegion();
690      // Do not show local variables belonging to a function other than
691      // where the error is reported.
692      if (auto MR = dyn_cast<StackSpaceRegion>(R->getMemorySpace()))
693        if (MR->getStackFrame() == LeakContext->getStackFrame())
694          FirstBinding = R;
695    }
696
697    // AllocationNode is the last node in which the symbol was tracked.
698    AllocationNode = N;
699
700    // AllocationNodeInCurrentContext, is the last node in the current or
701    // parent context in which the symbol was tracked.
702    //
703    // Note that the allocation site might be in the parent context. For example,
704    // the case where an allocation happens in a block that captures a reference
705    // to it and that reference is overwritten/dropped by another call to
706    // the block.
707    if (NContext == LeakContext || NContext->isParentOf(LeakContext))
708      AllocationNodeInCurrentOrParentContext = N;
709
710    // Find the last init that was called on the given symbol and store the
711    // init method's location context.
712    if (!InitMethodContext)
713      if (auto CEP = N->getLocation().getAs<CallEnter>()) {
714        const Stmt *CE = CEP->getCallExpr();
715        if (const auto *ME = dyn_cast_or_null<ObjCMessageExpr>(CE)) {
716          const Stmt *RecExpr = ME->getInstanceReceiver();
717          if (RecExpr) {
718            SVal RecV = St->getSVal(RecExpr, NContext);
719            if (ME->getMethodFamily() == OMF_init && RecV.getAsSymbol() == Sym)
720              InitMethodContext = CEP->getCalleeContext();
721          }
722        }
723      }
724
725    N = N->getFirstPred();
726  }
727
728  // If we are reporting a leak of the object that was allocated with alloc,
729  // mark its init method as interesting.
730  const LocationContext *InterestingMethodContext = nullptr;
731  if (InitMethodContext) {
732    const ProgramPoint AllocPP = AllocationNode->getLocation();
733    if (std::optional<StmtPoint> SP = AllocPP.getAs<StmtPoint>())
734      if (const ObjCMessageExpr *ME = SP->getStmtAs<ObjCMessageExpr>())
735        if (ME->getMethodFamily() == OMF_alloc)
736          InterestingMethodContext = InitMethodContext;
737  }
738
739  // If allocation happened in a function different from the leak node context,
740  // do not report the binding.
741  assert(N && "Could not find allocation node");
742
743  if (AllocationNodeInCurrentOrParentContext &&
744      AllocationNodeInCurrentOrParentContext->getLocationContext() !=
745      LeakContext)
746    FirstBinding = nullptr;
747
748  return AllocationInfo(AllocationNodeInCurrentOrParentContext, FirstBinding,
749                        InterestingMethodContext);
750}
751
752PathDiagnosticPieceRef
753RefCountReportVisitor::getEndPath(BugReporterContext &BRC,
754                                  const ExplodedNode *EndN,
755                                  PathSensitiveBugReport &BR) {
756  BR.markInteresting(Sym);
757  return BugReporterVisitor::getDefaultEndPath(BRC, EndN, BR);
758}
759
760PathDiagnosticPieceRef
761RefLeakReportVisitor::getEndPath(BugReporterContext &BRC,
762                                 const ExplodedNode *EndN,
763                                 PathSensitiveBugReport &BR) {
764
765  // Tell the BugReporterContext to report cases when the tracked symbol is
766  // assigned to different variables, etc.
767  BR.markInteresting(Sym);
768
769  PathDiagnosticLocation L = cast<RefLeakReport>(BR).getEndOfPath();
770
771  std::string sbuf;
772  llvm::raw_string_ostream os(sbuf);
773
774  os << "Object leaked: ";
775
776  std::optional<std::string> RegionDescription = describeRegion(LastBinding);
777  if (RegionDescription) {
778    os << "object allocated and stored into '" << *RegionDescription << '\'';
779  } else {
780    os << "allocated object of type '" << getPrettyTypeName(Sym->getType())
781       << "'";
782  }
783
784  // Get the retain count.
785  const RefVal *RV = getRefBinding(EndN->getState(), Sym);
786  assert(RV);
787
788  if (RV->getKind() == RefVal::ErrorLeakReturned) {
789    const Decl *D = &EndN->getCodeDecl();
790
791    os << (isa<ObjCMethodDecl>(D) ? " is returned from a method "
792                                  : " is returned from a function ");
793
794    if (D->hasAttr<CFReturnsNotRetainedAttr>()) {
795      os << "that is annotated as CF_RETURNS_NOT_RETAINED";
796    } else if (D->hasAttr<NSReturnsNotRetainedAttr>()) {
797      os << "that is annotated as NS_RETURNS_NOT_RETAINED";
798    } else if (D->hasAttr<OSReturnsNotRetainedAttr>()) {
799      os << "that is annotated as OS_RETURNS_NOT_RETAINED";
800    } else {
801      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
802        if (BRC.getASTContext().getLangOpts().ObjCAutoRefCount) {
803          os << "managed by Automatic Reference Counting";
804        } else {
805          os << "whose name ('" << MD->getSelector().getAsString()
806             << "') does not start with "
807                "'copy', 'mutableCopy', 'alloc' or 'new'."
808                "  This violates the naming convention rules"
809                " given in the Memory Management Guide for Cocoa";
810        }
811      } else {
812        const FunctionDecl *FD = cast<FunctionDecl>(D);
813        ObjKind K = RV->getObjKind();
814        if (K == ObjKind::ObjC || K == ObjKind::CF) {
815          os << "whose name ('" << *FD
816             << "') does not contain 'Copy' or 'Create'.  This violates the "
817                "naming"
818                " convention rules given in the Memory Management Guide for "
819                "Core"
820                " Foundation";
821        } else if (RV->getObjKind() == ObjKind::OS) {
822          std::string FuncName = FD->getNameAsString();
823          os << "whose name ('" << FuncName << "') starts with '"
824             << StringRef(FuncName).substr(0, 3) << "'";
825        }
826      }
827    }
828  } else {
829    os << " is not referenced later in this execution path and has a retain "
830          "count of +"
831       << RV->getCount();
832  }
833
834  return std::make_shared<PathDiagnosticEventPiece>(L, os.str());
835}
836
837RefCountReport::RefCountReport(const RefCountBug &D, const LangOptions &LOpts,
838                               ExplodedNode *n, SymbolRef sym, bool isLeak)
839    : PathSensitiveBugReport(D, D.getDescription(), n), Sym(sym),
840      isLeak(isLeak) {
841  if (!isLeak)
842    addVisitor<RefCountReportVisitor>(sym);
843}
844
845RefCountReport::RefCountReport(const RefCountBug &D, const LangOptions &LOpts,
846                               ExplodedNode *n, SymbolRef sym,
847                               StringRef endText)
848    : PathSensitiveBugReport(D, D.getDescription(), endText, n) {
849
850  addVisitor<RefCountReportVisitor>(sym);
851}
852
853void RefLeakReport::deriveParamLocation(CheckerContext &Ctx) {
854  const SourceManager &SMgr = Ctx.getSourceManager();
855
856  if (!Sym->getOriginRegion())
857    return;
858
859  auto *Region = dyn_cast<DeclRegion>(Sym->getOriginRegion());
860  if (Region) {
861    const Decl *PDecl = Region->getDecl();
862    if (isa_and_nonnull<ParmVarDecl>(PDecl)) {
863      PathDiagnosticLocation ParamLocation =
864          PathDiagnosticLocation::create(PDecl, SMgr);
865      Location = ParamLocation;
866      UniqueingLocation = ParamLocation;
867      UniqueingDecl = Ctx.getLocationContext()->getDecl();
868    }
869  }
870}
871
872void RefLeakReport::deriveAllocLocation(CheckerContext &Ctx) {
873  // Most bug reports are cached at the location where they occurred.
874  // With leaks, we want to unique them by the location where they were
875  // allocated, and only report a single path.  To do this, we need to find
876  // the allocation site of a piece of tracked memory, which we do via a
877  // call to GetAllocationSite.  This will walk the ExplodedGraph backwards.
878  // Note that this is *not* the trimmed graph; we are guaranteed, however,
879  // that all ancestor nodes that represent the allocation site have the
880  // same SourceLocation.
881  const ExplodedNode *AllocNode = nullptr;
882
883  const SourceManager &SMgr = Ctx.getSourceManager();
884
885  AllocationInfo AllocI =
886      GetAllocationSite(Ctx.getStateManager(), getErrorNode(), Sym);
887
888  AllocNode = AllocI.N;
889  AllocFirstBinding = AllocI.R;
890  markInteresting(AllocI.InterestingMethodContext);
891
892  // Get the SourceLocation for the allocation site.
893  // FIXME: This will crash the analyzer if an allocation comes from an
894  // implicit call (ex: a destructor call).
895  // (Currently there are no such allocations in Cocoa, though.)
896  AllocStmt = AllocNode->getStmtForDiagnostics();
897
898  if (!AllocStmt) {
899    AllocFirstBinding = nullptr;
900    return;
901  }
902
903  PathDiagnosticLocation AllocLocation = PathDiagnosticLocation::createBegin(
904      AllocStmt, SMgr, AllocNode->getLocationContext());
905  Location = AllocLocation;
906
907  // Set uniqieing info, which will be used for unique the bug reports. The
908  // leaks should be uniqued on the allocation site.
909  UniqueingLocation = AllocLocation;
910  UniqueingDecl = AllocNode->getLocationContext()->getDecl();
911}
912
913void RefLeakReport::createDescription(CheckerContext &Ctx) {
914  assert(Location.isValid() && UniqueingDecl && UniqueingLocation.isValid());
915  Description.clear();
916  llvm::raw_string_ostream os(Description);
917  os << "Potential leak of an object";
918
919  std::optional<std::string> RegionDescription =
920      describeRegion(AllocBindingToReport);
921  if (RegionDescription) {
922    os << " stored into '" << *RegionDescription << '\'';
923  } else {
924
925    // If we can't figure out the name, just supply the type information.
926    os << " of type '" << getPrettyTypeName(Sym->getType()) << "'";
927  }
928}
929
930void RefLeakReport::findBindingToReport(CheckerContext &Ctx,
931                                        ExplodedNode *Node) {
932  if (!AllocFirstBinding)
933    // If we don't have any bindings, we won't be able to find any
934    // better binding to report.
935    return;
936
937  // If the original region still contains the leaking symbol...
938  if (Node->getState()->getSVal(AllocFirstBinding).getAsSymbol() == Sym) {
939    // ...it is the best binding to report.
940    AllocBindingToReport = AllocFirstBinding;
941    return;
942  }
943
944  // At this point, we know that the original region doesn't contain the leaking
945  // when the actual leak happens.  It means that it can be confusing for the
946  // user to see such description in the message.
947  //
948  // Let's consider the following example:
949  //   Object *Original = allocate(...);
950  //   Object *New = Original;
951  //   Original = allocate(...);
952  //   Original->release();
953  //
954  // Complaining about a leaking object "stored into Original" might cause a
955  // rightful confusion because 'Original' is actually released.
956  // We should complain about 'New' instead.
957  Bindings AllVarBindings =
958      getAllVarBindingsForSymbol(Ctx.getStateManager(), Node, Sym);
959
960  // While looking for the last var bindings, we can still find
961  // `AllocFirstBinding` to be one of them.  In situations like this,
962  // it would still be the easiest case to explain to our users.
963  if (!AllVarBindings.empty() &&
964      llvm::count_if(AllVarBindings,
965                     [this](const std::pair<const MemRegion *, SVal> Binding) {
966                       return Binding.first == AllocFirstBinding;
967                     }) == 0) {
968    // Let's pick one of them at random (if there is something to pick from).
969    AllocBindingToReport = AllVarBindings[0].first;
970
971    // Because 'AllocBindingToReport' is not the same as
972    // 'AllocFirstBinding', we need to explain how the leaking object
973    // got from one to another.
974    //
975    // NOTE: We use the actual SVal stored in AllocBindingToReport here because
976    //       trackStoredValue compares SVal's and it can get trickier for
977    //       something like derived regions if we want to construct SVal from
978    //       Sym. Instead, we take the value that is definitely stored in that
979    //       region, thus guaranteeing that trackStoredValue will work.
980    bugreporter::trackStoredValue(AllVarBindings[0].second.castAs<KnownSVal>(),
981                                  AllocBindingToReport, *this);
982  } else {
983    AllocBindingToReport = AllocFirstBinding;
984  }
985}
986
987RefLeakReport::RefLeakReport(const RefCountBug &D, const LangOptions &LOpts,
988                             ExplodedNode *N, SymbolRef Sym,
989                             CheckerContext &Ctx)
990    : RefCountReport(D, LOpts, N, Sym, /*isLeak=*/true) {
991
992  deriveAllocLocation(Ctx);
993  findBindingToReport(Ctx, N);
994
995  if (!AllocFirstBinding)
996    deriveParamLocation(Ctx);
997
998  createDescription(Ctx);
999
1000  addVisitor<RefLeakReportVisitor>(Sym, AllocBindingToReport);
1001}
1002