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 
17 using namespace clang;
18 using namespace ento;
19 using namespace retaincountchecker;
20 
21 StringRef RefCountBug::bugTypeToName(RefCountBug::RefCountBugKind BT) {
22   switch (BT) {
23   case UseAfterRelease:
24     return "Use-after-release";
25   case ReleaseNotOwned:
26     return "Bad release";
27   case DeallocNotOwned:
28     return "-dealloc sent to non-exclusively owned object";
29   case FreeNotOwned:
30     return "freeing non-exclusively owned object";
31   case OverAutorelease:
32     return "Object autoreleased too many times";
33   case ReturnNotOwnedForOwned:
34     return "Method should return an owned object";
35   case LeakWithinFunction:
36     return "Leak";
37   case LeakAtReturn:
38     return "Leak of returned object";
39   }
40   llvm_unreachable("Unknown RefCountBugKind");
41 }
42 
43 StringRef RefCountBug::getDescription() const {
44   switch (BT) {
45   case UseAfterRelease:
46     return "Reference-counted object is used after it is released";
47   case ReleaseNotOwned:
48     return "Incorrect decrement of the reference count of an object that is "
49            "not owned at this point by the caller";
50   case DeallocNotOwned:
51     return "-dealloc sent to object that may be referenced elsewhere";
52   case FreeNotOwned:
53     return  "'free' called on an object that may be referenced elsewhere";
54   case OverAutorelease:
55     return "Object autoreleased too many times";
56   case ReturnNotOwnedForOwned:
57     return "Object with a +0 retain count returned to caller where a +1 "
58            "(owning) retain count is expected";
59   case LeakWithinFunction:
60   case LeakAtReturn:
61     return "";
62   }
63   llvm_unreachable("Unknown RefCountBugKind");
64 }
65 
66 RefCountBug::RefCountBug(CheckerNameRef Checker, RefCountBugKind BT)
67     : BugType(Checker, bugTypeToName(BT), categories::MemoryRefCount,
68               /*SuppressOnSink=*/BT == LeakWithinFunction ||
69                   BT == LeakAtReturn),
70       BT(BT) {}
71 
72 static bool isNumericLiteralExpression(const Expr *E) {
73   // FIXME: This set of cases was copied from SemaExprObjC.
74   return isa<IntegerLiteral>(E) ||
75          isa<CharacterLiteral>(E) ||
76          isa<FloatingLiteral>(E) ||
77          isa<ObjCBoolLiteralExpr>(E) ||
78          isa<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.
84 static 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 {@code os},
93 /// return whether the note should be generated.
94 static 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 {@code S}
168 /// corresponding to the symbol {@code Sym}.
169 /// If none found, returns None.
170 static Optional<unsigned> findArgIdxOfSymbol(ProgramStateRef CurrSt,
171                                              const LocationContext *LCtx,
172                                              SymbolRef &Sym,
173                                              Optional<CallEventRef<>> CE) {
174   if (!CE)
175     return None;
176 
177   for (unsigned Idx = 0; Idx < (*CE)->getNumArgs(); Idx++)
178     if (const MemRegion *MR = (*CE)->getArgSVal(Idx).getAsRegion())
179       if (const auto *TR = dyn_cast<TypedValueRegion>(MR))
180         if (CurrSt->getSVal(MR, TR->getValueType()).getAsSymbol() == Sym)
181           return Idx;
182 
183   return None;
184 }
185 
186 static Optional<std::string> findMetaClassAlloc(const Expr *Callee) {
187   if (const auto *ME = dyn_cast<MemberExpr>(Callee)) {
188     if (ME->getMemberDecl()->getNameAsString() != "alloc")
189       return None;
190     const Expr *This = ME->getBase()->IgnoreParenImpCasts();
191     if (const auto *DRE = dyn_cast<DeclRefExpr>(This)) {
192       const ValueDecl *VD = DRE->getDecl();
193       if (VD->getNameAsString() != "metaClass")
194         return None;
195 
196       if (const auto *RD = dyn_cast<CXXRecordDecl>(VD->getDeclContext()))
197         return RD->getNameAsString();
198 
199     }
200   }
201   return None;
202 }
203 
204 static std::string findAllocatedObjectName(const Stmt *S, QualType QT) {
205   if (const auto *CE = dyn_cast<CallExpr>(S))
206     if (auto Out = findMetaClassAlloc(CE->getCallee()))
207       return *Out;
208   return getPrettyTypeName(QT);
209 }
210 
211 static void generateDiagnosticsForCallLike(ProgramStateRef CurrSt,
212                                            const LocationContext *LCtx,
213                                            const RefVal &CurrV, SymbolRef &Sym,
214                                            const Stmt *S,
215                                            llvm::raw_string_ostream &os) {
216   CallEventManager &Mgr = CurrSt->getStateManager().getCallEventManager();
217   if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
218     // Get the name of the callee (if it is available)
219     // from the tracked SVal.
220     SVal X = CurrSt->getSValAsScalarOrLoc(CE->getCallee(), LCtx);
221     const FunctionDecl *FD = X.getAsFunctionDecl();
222 
223     // If failed, try to get it from AST.
224     if (!FD)
225       FD = dyn_cast<FunctionDecl>(CE->getCalleeDecl());
226 
227     if (const auto *MD = dyn_cast<CXXMethodDecl>(CE->getCalleeDecl())) {
228       os << "Call to method '" << MD->getQualifiedNameAsString() << '\'';
229     } else if (FD) {
230       os << "Call to function '" << FD->getQualifiedNameAsString() << '\'';
231     } else {
232       os << "function call";
233     }
234   } else if (isa<CXXNewExpr>(S)) {
235     os << "Operator 'new'";
236   } else {
237     assert(isa<ObjCMessageExpr>(S));
238     CallEventRef<ObjCMethodCall> Call =
239         Mgr.getObjCMethodCall(cast<ObjCMessageExpr>(S), CurrSt, LCtx);
240 
241     switch (Call->getMessageKind()) {
242     case OCM_Message:
243       os << "Method";
244       break;
245     case OCM_PropertyAccess:
246       os << "Property";
247       break;
248     case OCM_Subscript:
249       os << "Subscript";
250       break;
251     }
252   }
253 
254   Optional<CallEventRef<>> CE = Mgr.getCall(S, CurrSt, LCtx);
255   auto Idx = findArgIdxOfSymbol(CurrSt, LCtx, Sym, CE);
256 
257   // If index is not found, we assume that the symbol was returned.
258   if (!Idx) {
259     os << " returns ";
260   } else {
261     os << " writes ";
262   }
263 
264   if (CurrV.getObjKind() == ObjKind::CF) {
265     os << "a Core Foundation object of type '"
266        << Sym->getType().getAsString() << "' with a ";
267   } else if (CurrV.getObjKind() == ObjKind::OS) {
268     os << "an OSObject of type '" << findAllocatedObjectName(S, Sym->getType())
269        << "' with a ";
270   } else if (CurrV.getObjKind() == ObjKind::Generalized) {
271     os << "an object of type '" << Sym->getType().getAsString()
272        << "' with a ";
273   } else {
274     assert(CurrV.getObjKind() == ObjKind::ObjC);
275     QualType T = Sym->getType();
276     if (!isa<ObjCObjectPointerType>(T)) {
277       os << "an Objective-C object with a ";
278     } else {
279       const ObjCObjectPointerType *PT = cast<ObjCObjectPointerType>(T);
280       os << "an instance of " << PT->getPointeeType().getAsString()
281          << " with a ";
282     }
283   }
284 
285   if (CurrV.isOwned()) {
286     os << "+1 retain count";
287   } else {
288     assert(CurrV.isNotOwned());
289     os << "+0 retain count";
290   }
291 
292   if (Idx) {
293     os << " into an out parameter '";
294     const ParmVarDecl *PVD = (*CE)->parameters()[*Idx];
295     PVD->getNameForDiagnostic(os, PVD->getASTContext().getPrintingPolicy(),
296                               /*Qualified=*/false);
297     os << "'";
298 
299     QualType RT = (*CE)->getResultType();
300     if (!RT.isNull() && !RT->isVoidType()) {
301       SVal RV = (*CE)->getReturnValue();
302       if (CurrSt->isNull(RV).isConstrainedTrue()) {
303         os << " (assuming the call returns zero)";
304       } else if (CurrSt->isNonNull(RV).isConstrainedTrue()) {
305         os << " (assuming the call returns non-zero)";
306       }
307 
308     }
309   }
310 }
311 
312 namespace clang {
313 namespace ento {
314 namespace retaincountchecker {
315 
316 class RefCountReportVisitor : public BugReporterVisitor {
317 protected:
318   SymbolRef Sym;
319 
320 public:
321   RefCountReportVisitor(SymbolRef sym) : Sym(sym) {}
322 
323   void Profile(llvm::FoldingSetNodeID &ID) const override {
324     static int x = 0;
325     ID.AddPointer(&x);
326     ID.AddPointer(Sym);
327   }
328 
329   PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
330                                    BugReporterContext &BRC,
331                                    PathSensitiveBugReport &BR) override;
332 
333   PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC,
334                                     const ExplodedNode *N,
335                                     PathSensitiveBugReport &BR) override;
336 };
337 
338 class RefLeakReportVisitor : public RefCountReportVisitor {
339 public:
340   RefLeakReportVisitor(SymbolRef sym) : RefCountReportVisitor(sym) {}
341 
342   PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC,
343                                     const ExplodedNode *N,
344                                     PathSensitiveBugReport &BR) override;
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.
353 static 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.
372 static std::shared_ptr<PathDiagnosticEventPiece>
373 annotateConsumedSummaryMismatch(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.
422 static std::shared_ptr<PathDiagnosticEventPiece>
423 annotateStartParameter(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 
452 PathDiagnosticPieceRef
453 RefCountReportVisitor::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 
605 static 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 None;
611 }
612 
613 namespace {
614 // Find the first node in the current function context that referred to the
615 // tracked symbol and the memory location that value was stored to. Note, the
616 // value is only reported if the allocation occurred in the same function as
617 // the leak. The function can also return a location context, which should be
618 // treated as interesting.
619 struct AllocationInfo {
620   const ExplodedNode* N;
621   const MemRegion *R;
622   const LocationContext *InterestingMethodContext;
623   AllocationInfo(const ExplodedNode *InN,
624                  const MemRegion *InR,
625                  const LocationContext *InInterestingMethodContext) :
626     N(InN), R(InR), InterestingMethodContext(InInterestingMethodContext) {}
627 };
628 } // end anonymous namespace
629 
630 static AllocationInfo GetAllocationSite(ProgramStateManager &StateMgr,
631                                         const ExplodedNode *N, SymbolRef Sym) {
632   const ExplodedNode *AllocationNode = N;
633   const ExplodedNode *AllocationNodeInCurrentOrParentContext = N;
634   const MemRegion *FirstBinding = nullptr;
635   const LocationContext *LeakContext = N->getLocationContext();
636 
637   // The location context of the init method called on the leaked object, if
638   // available.
639   const LocationContext *InitMethodContext = nullptr;
640 
641   while (N) {
642     ProgramStateRef St = N->getState();
643     const LocationContext *NContext = N->getLocationContext();
644 
645     if (!getRefBinding(St, Sym))
646       break;
647 
648     StoreManager::FindUniqueBinding FB(Sym);
649     StateMgr.iterBindings(St, FB);
650 
651     if (FB) {
652       const MemRegion *R = FB.getRegion();
653       // Do not show local variables belonging to a function other than
654       // where the error is reported.
655       if (auto MR = dyn_cast<StackSpaceRegion>(R->getMemorySpace()))
656         if (MR->getStackFrame() == LeakContext->getStackFrame())
657           FirstBinding = R;
658     }
659 
660     // AllocationNode is the last node in which the symbol was tracked.
661     AllocationNode = N;
662 
663     // AllocationNodeInCurrentContext, is the last node in the current or
664     // parent context in which the symbol was tracked.
665     //
666     // Note that the allocation site might be in the parent context. For example,
667     // the case where an allocation happens in a block that captures a reference
668     // to it and that reference is overwritten/dropped by another call to
669     // the block.
670     if (NContext == LeakContext || NContext->isParentOf(LeakContext))
671       AllocationNodeInCurrentOrParentContext = N;
672 
673     // Find the last init that was called on the given symbol and store the
674     // init method's location context.
675     if (!InitMethodContext)
676       if (auto CEP = N->getLocation().getAs<CallEnter>()) {
677         const Stmt *CE = CEP->getCallExpr();
678         if (const auto *ME = dyn_cast_or_null<ObjCMessageExpr>(CE)) {
679           const Stmt *RecExpr = ME->getInstanceReceiver();
680           if (RecExpr) {
681             SVal RecV = St->getSVal(RecExpr, NContext);
682             if (ME->getMethodFamily() == OMF_init && RecV.getAsSymbol() == Sym)
683               InitMethodContext = CEP->getCalleeContext();
684           }
685         }
686       }
687 
688     N = N->getFirstPred();
689   }
690 
691   // If we are reporting a leak of the object that was allocated with alloc,
692   // mark its init method as interesting.
693   const LocationContext *InterestingMethodContext = nullptr;
694   if (InitMethodContext) {
695     const ProgramPoint AllocPP = AllocationNode->getLocation();
696     if (Optional<StmtPoint> SP = AllocPP.getAs<StmtPoint>())
697       if (const ObjCMessageExpr *ME = SP->getStmtAs<ObjCMessageExpr>())
698         if (ME->getMethodFamily() == OMF_alloc)
699           InterestingMethodContext = InitMethodContext;
700   }
701 
702   // If allocation happened in a function different from the leak node context,
703   // do not report the binding.
704   assert(N && "Could not find allocation node");
705 
706   if (AllocationNodeInCurrentOrParentContext &&
707       AllocationNodeInCurrentOrParentContext->getLocationContext() !=
708       LeakContext)
709     FirstBinding = nullptr;
710 
711   return AllocationInfo(AllocationNodeInCurrentOrParentContext, FirstBinding,
712                         InterestingMethodContext);
713 }
714 
715 PathDiagnosticPieceRef
716 RefCountReportVisitor::getEndPath(BugReporterContext &BRC,
717                                   const ExplodedNode *EndN,
718                                   PathSensitiveBugReport &BR) {
719   BR.markInteresting(Sym);
720   return BugReporterVisitor::getDefaultEndPath(BRC, EndN, BR);
721 }
722 
723 PathDiagnosticPieceRef
724 RefLeakReportVisitor::getEndPath(BugReporterContext &BRC,
725                                  const ExplodedNode *EndN,
726                                  PathSensitiveBugReport &BR) {
727 
728   // Tell the BugReporterContext to report cases when the tracked symbol is
729   // assigned to different variables, etc.
730   BR.markInteresting(Sym);
731 
732   // We are reporting a leak.  Walk up the graph to get to the first node where
733   // the symbol appeared, and also get the first VarDecl that tracked object
734   // is stored to.
735   AllocationInfo AllocI = GetAllocationSite(BRC.getStateManager(), EndN, Sym);
736 
737   const MemRegion* FirstBinding = AllocI.R;
738   BR.markInteresting(AllocI.InterestingMethodContext);
739 
740   PathDiagnosticLocation L = cast<RefLeakReport>(BR).getEndOfPath();
741 
742   std::string sbuf;
743   llvm::raw_string_ostream os(sbuf);
744 
745   os << "Object leaked: ";
746 
747   Optional<std::string> RegionDescription = describeRegion(FirstBinding);
748   if (RegionDescription) {
749     os << "object allocated and stored into '" << *RegionDescription << '\'';
750   } else {
751     os << "allocated object of type '" << getPrettyTypeName(Sym->getType())
752        << "'";
753   }
754 
755   // Get the retain count.
756   const RefVal* RV = getRefBinding(EndN->getState(), Sym);
757   assert(RV);
758 
759   if (RV->getKind() == RefVal::ErrorLeakReturned) {
760     // FIXME: Per comments in rdar://6320065, "create" only applies to CF
761     // objects.  Only "copy", "alloc", "retain" and "new" transfer ownership
762     // to the caller for NS objects.
763     const Decl *D = &EndN->getCodeDecl();
764 
765     os << (isa<ObjCMethodDecl>(D) ? " is returned from a method "
766                                   : " is returned from a function ");
767 
768     if (D->hasAttr<CFReturnsNotRetainedAttr>()) {
769       os << "that is annotated as CF_RETURNS_NOT_RETAINED";
770     } else if (D->hasAttr<NSReturnsNotRetainedAttr>()) {
771       os << "that is annotated as NS_RETURNS_NOT_RETAINED";
772     } else if (D->hasAttr<OSReturnsNotRetainedAttr>()) {
773       os << "that is annotated as OS_RETURNS_NOT_RETAINED";
774     } else {
775       if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
776         if (BRC.getASTContext().getLangOpts().ObjCAutoRefCount) {
777           os << "managed by Automatic Reference Counting";
778         } else {
779           os << "whose name ('" << MD->getSelector().getAsString()
780              << "') does not start with "
781                 "'copy', 'mutableCopy', 'alloc' or 'new'."
782                 "  This violates the naming convention rules"
783                 " given in the Memory Management Guide for Cocoa";
784         }
785       } else {
786         const FunctionDecl *FD = cast<FunctionDecl>(D);
787         ObjKind K = RV->getObjKind();
788         if (K == ObjKind::ObjC || K == ObjKind::CF) {
789           os << "whose name ('" << *FD
790              << "') does not contain 'Copy' or 'Create'.  This violates the "
791                 "naming"
792                 " convention rules given in the Memory Management Guide for "
793                 "Core"
794                 " Foundation";
795         } else if (RV->getObjKind() == ObjKind::OS) {
796           std::string FuncName = FD->getNameAsString();
797           os << "whose name ('" << FuncName
798             << "') starts with '" << StringRef(FuncName).substr(0, 3) << "'";
799         }
800       }
801     }
802   } else {
803     os << " is not referenced later in this execution path and has a retain "
804           "count of +" << RV->getCount();
805   }
806 
807   return std::make_shared<PathDiagnosticEventPiece>(L, os.str());
808 }
809 
810 RefCountReport::RefCountReport(const RefCountBug &D, const LangOptions &LOpts,
811                                ExplodedNode *n, SymbolRef sym, bool isLeak)
812     : PathSensitiveBugReport(D, D.getDescription(), n), Sym(sym),
813       isLeak(isLeak) {
814   if (!isLeak)
815     addVisitor(std::make_unique<RefCountReportVisitor>(sym));
816 }
817 
818 RefCountReport::RefCountReport(const RefCountBug &D, const LangOptions &LOpts,
819                                ExplodedNode *n, SymbolRef sym,
820                                StringRef endText)
821     : PathSensitiveBugReport(D, D.getDescription(), endText, n) {
822 
823   addVisitor(std::make_unique<RefCountReportVisitor>(sym));
824 }
825 
826 void RefLeakReport::deriveParamLocation(CheckerContext &Ctx, SymbolRef sym) {
827   const SourceManager& SMgr = Ctx.getSourceManager();
828 
829   if (!sym->getOriginRegion())
830     return;
831 
832   auto *Region = dyn_cast<DeclRegion>(sym->getOriginRegion());
833   if (Region) {
834     const Decl *PDecl = Region->getDecl();
835     if (PDecl && isa<ParmVarDecl>(PDecl)) {
836       PathDiagnosticLocation ParamLocation =
837           PathDiagnosticLocation::create(PDecl, SMgr);
838       Location = ParamLocation;
839       UniqueingLocation = ParamLocation;
840       UniqueingDecl = Ctx.getLocationContext()->getDecl();
841     }
842   }
843 }
844 
845 void RefLeakReport::deriveAllocLocation(CheckerContext &Ctx,
846                                           SymbolRef sym) {
847   // Most bug reports are cached at the location where they occurred.
848   // With leaks, we want to unique them by the location where they were
849   // allocated, and only report a single path.  To do this, we need to find
850   // the allocation site of a piece of tracked memory, which we do via a
851   // call to GetAllocationSite.  This will walk the ExplodedGraph backwards.
852   // Note that this is *not* the trimmed graph; we are guaranteed, however,
853   // that all ancestor nodes that represent the allocation site have the
854   // same SourceLocation.
855   const ExplodedNode *AllocNode = nullptr;
856 
857   const SourceManager& SMgr = Ctx.getSourceManager();
858 
859   AllocationInfo AllocI =
860       GetAllocationSite(Ctx.getStateManager(), getErrorNode(), sym);
861 
862   AllocNode = AllocI.N;
863   AllocBinding = AllocI.R;
864   markInteresting(AllocI.InterestingMethodContext);
865 
866   // Get the SourceLocation for the allocation site.
867   // FIXME: This will crash the analyzer if an allocation comes from an
868   // implicit call (ex: a destructor call).
869   // (Currently there are no such allocations in Cocoa, though.)
870   AllocStmt = AllocNode->getStmtForDiagnostics();
871 
872   if (!AllocStmt) {
873     AllocBinding = nullptr;
874     return;
875   }
876 
877   PathDiagnosticLocation AllocLocation =
878     PathDiagnosticLocation::createBegin(AllocStmt, SMgr,
879                                         AllocNode->getLocationContext());
880   Location = AllocLocation;
881 
882   // Set uniqieing info, which will be used for unique the bug reports. The
883   // leaks should be uniqued on the allocation site.
884   UniqueingLocation = AllocLocation;
885   UniqueingDecl = AllocNode->getLocationContext()->getDecl();
886 }
887 
888 void RefLeakReport::createDescription(CheckerContext &Ctx) {
889   assert(Location.isValid() && UniqueingDecl && UniqueingLocation.isValid());
890   Description.clear();
891   llvm::raw_string_ostream os(Description);
892   os << "Potential leak of an object";
893 
894   Optional<std::string> RegionDescription = describeRegion(AllocBinding);
895   if (RegionDescription) {
896     os << " stored into '" << *RegionDescription << '\'';
897   } else {
898 
899     // If we can't figure out the name, just supply the type information.
900     os << " of type '" << getPrettyTypeName(Sym->getType()) << "'";
901   }
902 }
903 
904 RefLeakReport::RefLeakReport(const RefCountBug &D, const LangOptions &LOpts,
905                              ExplodedNode *n, SymbolRef sym,
906                              CheckerContext &Ctx)
907     : RefCountReport(D, LOpts, n, sym, /*isLeak=*/true) {
908 
909   deriveAllocLocation(Ctx, sym);
910   if (!AllocBinding)
911     deriveParamLocation(Ctx, sym);
912 
913   createDescription(Ctx);
914 
915   addVisitor(std::make_unique<RefLeakReportVisitor>(sym));
916 }
917