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