1//==-- RetainCountChecker.cpp - Checks for leaks and other issues -*- C++ -*--//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines the methods for RetainCountChecker, which implements
11//  a reference count checker for Core Foundation and Cocoa on (Mac OS X).
12//
13//===----------------------------------------------------------------------===//
14
15#include "AllocationDiagnostics.h"
16#include "ClangSACheckers.h"
17#include "SelectorExtras.h"
18#include "clang/AST/Attr.h"
19#include "clang/AST/DeclCXX.h"
20#include "clang/AST/DeclObjC.h"
21#include "clang/AST/ParentMap.h"
22#include "clang/Analysis/DomainSpecific/CocoaConventions.h"
23#include "clang/Basic/LangOptions.h"
24#include "clang/Basic/SourceManager.h"
25#include "clang/StaticAnalyzer/Checkers/ObjCRetainCount.h"
26#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
27#include "clang/StaticAnalyzer/Core/BugReporter/PathDiagnostic.h"
28#include "clang/StaticAnalyzer/Core/Checker.h"
29#include "clang/StaticAnalyzer/Core/CheckerManager.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
31#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
32#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
33#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
34#include "llvm/ADT/DenseMap.h"
35#include "llvm/ADT/FoldingSet.h"
36#include "llvm/ADT/ImmutableList.h"
37#include "llvm/ADT/ImmutableMap.h"
38#include "llvm/ADT/STLExtras.h"
39#include "llvm/ADT/SmallString.h"
40#include "llvm/ADT/StringExtras.h"
41#include <cstdarg>
42#include <utility>
43
44using namespace clang;
45using namespace ento;
46using namespace objc_retain;
47using llvm::StrInStrNoCase;
48
49//===----------------------------------------------------------------------===//
50// Adapters for FoldingSet.
51//===----------------------------------------------------------------------===//
52
53namespace llvm {
54template <> struct FoldingSetTrait<ArgEffect> {
55static inline void Profile(const ArgEffect X, FoldingSetNodeID &ID) {
56  ID.AddInteger((unsigned) X);
57}
58};
59template <> struct FoldingSetTrait<RetEffect> {
60  static inline void Profile(const RetEffect &X, FoldingSetNodeID &ID) {
61    ID.AddInteger((unsigned) X.getKind());
62    ID.AddInteger((unsigned) X.getObjKind());
63}
64};
65} // end llvm namespace
66
67//===----------------------------------------------------------------------===//
68// Reference-counting logic (typestate + counts).
69//===----------------------------------------------------------------------===//
70
71/// ArgEffects summarizes the effects of a function/method call on all of
72/// its arguments.
73typedef llvm::ImmutableMap<unsigned,ArgEffect> ArgEffects;
74
75namespace {
76class RefVal {
77public:
78  enum Kind {
79    Owned = 0, // Owning reference.
80    NotOwned,  // Reference is not owned by still valid (not freed).
81    Released,  // Object has been released.
82    ReturnedOwned, // Returned object passes ownership to caller.
83    ReturnedNotOwned, // Return object does not pass ownership to caller.
84    ERROR_START,
85    ErrorDeallocNotOwned, // -dealloc called on non-owned object.
86    ErrorDeallocGC, // Calling -dealloc with GC enabled.
87    ErrorUseAfterRelease, // Object used after released.
88    ErrorReleaseNotOwned, // Release of an object that was not owned.
89    ERROR_LEAK_START,
90    ErrorLeak,  // A memory leak due to excessive reference counts.
91    ErrorLeakReturned, // A memory leak due to the returning method not having
92                       // the correct naming conventions.
93    ErrorGCLeakReturned,
94    ErrorOverAutorelease,
95    ErrorReturnedNotOwned
96  };
97
98  /// Tracks how an object referenced by an ivar has been used.
99  ///
100  /// This accounts for us not knowing if an arbitrary ivar is supposed to be
101  /// stored at +0 or +1.
102  enum class IvarAccessHistory {
103    None,
104    AccessedDirectly,
105    ReleasedAfterDirectAccess
106  };
107
108private:
109  /// The number of outstanding retains.
110  unsigned Cnt;
111  /// The number of outstanding autoreleases.
112  unsigned ACnt;
113  /// The (static) type of the object at the time we started tracking it.
114  QualType T;
115
116  /// The current state of the object.
117  ///
118  /// See the RefVal::Kind enum for possible values.
119  unsigned RawKind : 5;
120
121  /// The kind of object being tracked (CF or ObjC), if known.
122  ///
123  /// See the RetEffect::ObjKind enum for possible values.
124  unsigned RawObjectKind : 2;
125
126  /// True if the current state and/or retain count may turn out to not be the
127  /// best possible approximation of the reference counting state.
128  ///
129  /// If true, the checker may decide to throw away ("override") this state
130  /// in favor of something else when it sees the object being used in new ways.
131  ///
132  /// This setting should not be propagated to state derived from this state.
133  /// Once we start deriving new states, it would be inconsistent to override
134  /// them.
135  unsigned RawIvarAccessHistory : 2;
136
137  RefVal(Kind k, RetEffect::ObjKind o, unsigned cnt, unsigned acnt, QualType t,
138         IvarAccessHistory IvarAccess)
139    : Cnt(cnt), ACnt(acnt), T(t), RawKind(static_cast<unsigned>(k)),
140      RawObjectKind(static_cast<unsigned>(o)),
141      RawIvarAccessHistory(static_cast<unsigned>(IvarAccess)) {
142    assert(getKind() == k && "not enough bits for the kind");
143    assert(getObjKind() == o && "not enough bits for the object kind");
144    assert(getIvarAccessHistory() == IvarAccess && "not enough bits");
145  }
146
147public:
148  Kind getKind() const { return static_cast<Kind>(RawKind); }
149
150  RetEffect::ObjKind getObjKind() const {
151    return static_cast<RetEffect::ObjKind>(RawObjectKind);
152  }
153
154  unsigned getCount() const { return Cnt; }
155  unsigned getAutoreleaseCount() const { return ACnt; }
156  unsigned getCombinedCounts() const { return Cnt + ACnt; }
157  void clearCounts() {
158    Cnt = 0;
159    ACnt = 0;
160  }
161  void setCount(unsigned i) {
162    Cnt = i;
163  }
164  void setAutoreleaseCount(unsigned i) {
165    ACnt = i;
166  }
167
168  QualType getType() const { return T; }
169
170  /// Returns what the analyzer knows about direct accesses to a particular
171  /// instance variable.
172  ///
173  /// If the object with this refcount wasn't originally from an Objective-C
174  /// ivar region, this should always return IvarAccessHistory::None.
175  IvarAccessHistory getIvarAccessHistory() const {
176    return static_cast<IvarAccessHistory>(RawIvarAccessHistory);
177  }
178
179  bool isOwned() const {
180    return getKind() == Owned;
181  }
182
183  bool isNotOwned() const {
184    return getKind() == NotOwned;
185  }
186
187  bool isReturnedOwned() const {
188    return getKind() == ReturnedOwned;
189  }
190
191  bool isReturnedNotOwned() const {
192    return getKind() == ReturnedNotOwned;
193  }
194
195  /// Create a state for an object whose lifetime is the responsibility of the
196  /// current function, at least partially.
197  ///
198  /// Most commonly, this is an owned object with a retain count of +1.
199  static RefVal makeOwned(RetEffect::ObjKind o, QualType t,
200                          unsigned Count = 1) {
201    return RefVal(Owned, o, Count, 0, t, IvarAccessHistory::None);
202  }
203
204  /// Create a state for an object whose lifetime is not the responsibility of
205  /// the current function.
206  ///
207  /// Most commonly, this is an unowned object with a retain count of +0.
208  static RefVal makeNotOwned(RetEffect::ObjKind o, QualType t,
209                             unsigned Count = 0) {
210    return RefVal(NotOwned, o, Count, 0, t, IvarAccessHistory::None);
211  }
212
213  RefVal operator-(size_t i) const {
214    return RefVal(getKind(), getObjKind(), getCount() - i,
215                  getAutoreleaseCount(), getType(), getIvarAccessHistory());
216  }
217
218  RefVal operator+(size_t i) const {
219    return RefVal(getKind(), getObjKind(), getCount() + i,
220                  getAutoreleaseCount(), getType(), getIvarAccessHistory());
221  }
222
223  RefVal operator^(Kind k) const {
224    return RefVal(k, getObjKind(), getCount(), getAutoreleaseCount(),
225                  getType(), getIvarAccessHistory());
226  }
227
228  RefVal autorelease() const {
229    return RefVal(getKind(), getObjKind(), getCount(), getAutoreleaseCount()+1,
230                  getType(), getIvarAccessHistory());
231  }
232
233  RefVal withIvarAccess() const {
234    assert(getIvarAccessHistory() == IvarAccessHistory::None);
235    return RefVal(getKind(), getObjKind(), getCount(), getAutoreleaseCount(),
236                  getType(), IvarAccessHistory::AccessedDirectly);
237  }
238
239  RefVal releaseViaIvar() const {
240    assert(getIvarAccessHistory() == IvarAccessHistory::AccessedDirectly);
241    return RefVal(getKind(), getObjKind(), getCount(), getAutoreleaseCount(),
242                  getType(), IvarAccessHistory::ReleasedAfterDirectAccess);
243  }
244
245  // Comparison, profiling, and pretty-printing.
246
247  bool hasSameState(const RefVal &X) const {
248    return getKind() == X.getKind() && Cnt == X.Cnt && ACnt == X.ACnt &&
249           getIvarAccessHistory() == X.getIvarAccessHistory();
250  }
251
252  bool operator==(const RefVal& X) const {
253    return T == X.T && hasSameState(X) && getObjKind() == X.getObjKind();
254  }
255
256  void Profile(llvm::FoldingSetNodeID& ID) const {
257    ID.Add(T);
258    ID.AddInteger(RawKind);
259    ID.AddInteger(Cnt);
260    ID.AddInteger(ACnt);
261    ID.AddInteger(RawObjectKind);
262    ID.AddInteger(RawIvarAccessHistory);
263  }
264
265  void print(raw_ostream &Out) const;
266};
267
268void RefVal::print(raw_ostream &Out) const {
269  if (!T.isNull())
270    Out << "Tracked " << T.getAsString() << '/';
271
272  switch (getKind()) {
273    default: llvm_unreachable("Invalid RefVal kind");
274    case Owned: {
275      Out << "Owned";
276      unsigned cnt = getCount();
277      if (cnt) Out << " (+ " << cnt << ")";
278      break;
279    }
280
281    case NotOwned: {
282      Out << "NotOwned";
283      unsigned cnt = getCount();
284      if (cnt) Out << " (+ " << cnt << ")";
285      break;
286    }
287
288    case ReturnedOwned: {
289      Out << "ReturnedOwned";
290      unsigned cnt = getCount();
291      if (cnt) Out << " (+ " << cnt << ")";
292      break;
293    }
294
295    case ReturnedNotOwned: {
296      Out << "ReturnedNotOwned";
297      unsigned cnt = getCount();
298      if (cnt) Out << " (+ " << cnt << ")";
299      break;
300    }
301
302    case Released:
303      Out << "Released";
304      break;
305
306    case ErrorDeallocGC:
307      Out << "-dealloc (GC)";
308      break;
309
310    case ErrorDeallocNotOwned:
311      Out << "-dealloc (not-owned)";
312      break;
313
314    case ErrorLeak:
315      Out << "Leaked";
316      break;
317
318    case ErrorLeakReturned:
319      Out << "Leaked (Bad naming)";
320      break;
321
322    case ErrorGCLeakReturned:
323      Out << "Leaked (GC-ed at return)";
324      break;
325
326    case ErrorUseAfterRelease:
327      Out << "Use-After-Release [ERROR]";
328      break;
329
330    case ErrorReleaseNotOwned:
331      Out << "Release of Not-Owned [ERROR]";
332      break;
333
334    case RefVal::ErrorOverAutorelease:
335      Out << "Over-autoreleased";
336      break;
337
338    case RefVal::ErrorReturnedNotOwned:
339      Out << "Non-owned object returned instead of owned";
340      break;
341  }
342
343  switch (getIvarAccessHistory()) {
344  case IvarAccessHistory::None:
345    break;
346  case IvarAccessHistory::AccessedDirectly:
347    Out << " [direct ivar access]";
348    break;
349  case IvarAccessHistory::ReleasedAfterDirectAccess:
350    Out << " [released after direct ivar access]";
351  }
352
353  if (ACnt) {
354    Out << " [autorelease -" << ACnt << ']';
355  }
356}
357} //end anonymous namespace
358
359//===----------------------------------------------------------------------===//
360// RefBindings - State used to track object reference counts.
361//===----------------------------------------------------------------------===//
362
363REGISTER_MAP_WITH_PROGRAMSTATE(RefBindings, SymbolRef, RefVal)
364
365static inline const RefVal *getRefBinding(ProgramStateRef State,
366                                          SymbolRef Sym) {
367  return State->get<RefBindings>(Sym);
368}
369
370static inline ProgramStateRef setRefBinding(ProgramStateRef State,
371                                            SymbolRef Sym, RefVal Val) {
372  return State->set<RefBindings>(Sym, Val);
373}
374
375static ProgramStateRef removeRefBinding(ProgramStateRef State, SymbolRef Sym) {
376  return State->remove<RefBindings>(Sym);
377}
378
379//===----------------------------------------------------------------------===//
380// Function/Method behavior summaries.
381//===----------------------------------------------------------------------===//
382
383namespace {
384class RetainSummary {
385  /// Args - a map of (index, ArgEffect) pairs, where index
386  ///  specifies the argument (starting from 0).  This can be sparsely
387  ///  populated; arguments with no entry in Args use 'DefaultArgEffect'.
388  ArgEffects Args;
389
390  /// DefaultArgEffect - The default ArgEffect to apply to arguments that
391  ///  do not have an entry in Args.
392  ArgEffect DefaultArgEffect;
393
394  /// Receiver - If this summary applies to an Objective-C message expression,
395  ///  this is the effect applied to the state of the receiver.
396  ArgEffect Receiver;
397
398  /// Ret - The effect on the return value.  Used to indicate if the
399  ///  function/method call returns a new tracked symbol.
400  RetEffect Ret;
401
402public:
403  RetainSummary(ArgEffects A, RetEffect R, ArgEffect defaultEff,
404                ArgEffect ReceiverEff)
405    : Args(A), DefaultArgEffect(defaultEff), Receiver(ReceiverEff), Ret(R) {}
406
407  /// getArg - Return the argument effect on the argument specified by
408  ///  idx (starting from 0).
409  ArgEffect getArg(unsigned idx) const {
410    if (const ArgEffect *AE = Args.lookup(idx))
411      return *AE;
412
413    return DefaultArgEffect;
414  }
415
416  void addArg(ArgEffects::Factory &af, unsigned idx, ArgEffect e) {
417    Args = af.add(Args, idx, e);
418  }
419
420  /// setDefaultArgEffect - Set the default argument effect.
421  void setDefaultArgEffect(ArgEffect E) {
422    DefaultArgEffect = E;
423  }
424
425  /// getRetEffect - Returns the effect on the return value of the call.
426  RetEffect getRetEffect() const { return Ret; }
427
428  /// setRetEffect - Set the effect of the return value of the call.
429  void setRetEffect(RetEffect E) { Ret = E; }
430
431
432  /// Sets the effect on the receiver of the message.
433  void setReceiverEffect(ArgEffect e) { Receiver = e; }
434
435  /// getReceiverEffect - Returns the effect on the receiver of the call.
436  ///  This is only meaningful if the summary applies to an ObjCMessageExpr*.
437  ArgEffect getReceiverEffect() const { return Receiver; }
438
439  /// Test if two retain summaries are identical. Note that merely equivalent
440  /// summaries are not necessarily identical (for example, if an explicit
441  /// argument effect matches the default effect).
442  bool operator==(const RetainSummary &Other) const {
443    return Args == Other.Args && DefaultArgEffect == Other.DefaultArgEffect &&
444           Receiver == Other.Receiver && Ret == Other.Ret;
445  }
446
447  /// Profile this summary for inclusion in a FoldingSet.
448  void Profile(llvm::FoldingSetNodeID& ID) const {
449    ID.Add(Args);
450    ID.Add(DefaultArgEffect);
451    ID.Add(Receiver);
452    ID.Add(Ret);
453  }
454
455  /// A retain summary is simple if it has no ArgEffects other than the default.
456  bool isSimple() const {
457    return Args.isEmpty();
458  }
459
460private:
461  ArgEffects getArgEffects() const { return Args; }
462  ArgEffect getDefaultArgEffect() const { return DefaultArgEffect; }
463
464  friend class RetainSummaryManager;
465};
466} // end anonymous namespace
467
468//===----------------------------------------------------------------------===//
469// Data structures for constructing summaries.
470//===----------------------------------------------------------------------===//
471
472namespace {
473class ObjCSummaryKey {
474  IdentifierInfo* II;
475  Selector S;
476public:
477  ObjCSummaryKey(IdentifierInfo* ii, Selector s)
478    : II(ii), S(s) {}
479
480  ObjCSummaryKey(const ObjCInterfaceDecl *d, Selector s)
481    : II(d ? d->getIdentifier() : nullptr), S(s) {}
482
483  ObjCSummaryKey(Selector s)
484    : II(nullptr), S(s) {}
485
486  IdentifierInfo *getIdentifier() const { return II; }
487  Selector getSelector() const { return S; }
488};
489} // end anonymous namespace
490
491namespace llvm {
492template <> struct DenseMapInfo<ObjCSummaryKey> {
493  static inline ObjCSummaryKey getEmptyKey() {
494    return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getEmptyKey(),
495                          DenseMapInfo<Selector>::getEmptyKey());
496  }
497
498  static inline ObjCSummaryKey getTombstoneKey() {
499    return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getTombstoneKey(),
500                          DenseMapInfo<Selector>::getTombstoneKey());
501  }
502
503  static unsigned getHashValue(const ObjCSummaryKey &V) {
504    typedef std::pair<IdentifierInfo*, Selector> PairTy;
505    return DenseMapInfo<PairTy>::getHashValue(PairTy(V.getIdentifier(),
506                                                     V.getSelector()));
507  }
508
509  static bool isEqual(const ObjCSummaryKey& LHS, const ObjCSummaryKey& RHS) {
510    return LHS.getIdentifier() == RHS.getIdentifier() &&
511           LHS.getSelector() == RHS.getSelector();
512  }
513
514};
515} // end llvm namespace
516
517namespace {
518class ObjCSummaryCache {
519  typedef llvm::DenseMap<ObjCSummaryKey, const RetainSummary *> MapTy;
520  MapTy M;
521public:
522  ObjCSummaryCache() {}
523
524  const RetainSummary * find(const ObjCInterfaceDecl *D, Selector S) {
525    // Do a lookup with the (D,S) pair.  If we find a match return
526    // the iterator.
527    ObjCSummaryKey K(D, S);
528    MapTy::iterator I = M.find(K);
529
530    if (I != M.end())
531      return I->second;
532    if (!D)
533      return nullptr;
534
535    // Walk the super chain.  If we find a hit with a parent, we'll end
536    // up returning that summary.  We actually allow that key (null,S), as
537    // we cache summaries for the null ObjCInterfaceDecl* to allow us to
538    // generate initial summaries without having to worry about NSObject
539    // being declared.
540    // FIXME: We may change this at some point.
541    for (ObjCInterfaceDecl *C=D->getSuperClass() ;; C=C->getSuperClass()) {
542      if ((I = M.find(ObjCSummaryKey(C, S))) != M.end())
543        break;
544
545      if (!C)
546        return nullptr;
547    }
548
549    // Cache the summary with original key to make the next lookup faster
550    // and return the iterator.
551    const RetainSummary *Summ = I->second;
552    M[K] = Summ;
553    return Summ;
554  }
555
556  const RetainSummary *find(IdentifierInfo* II, Selector S) {
557    // FIXME: Class method lookup.  Right now we dont' have a good way
558    // of going between IdentifierInfo* and the class hierarchy.
559    MapTy::iterator I = M.find(ObjCSummaryKey(II, S));
560
561    if (I == M.end())
562      I = M.find(ObjCSummaryKey(S));
563
564    return I == M.end() ? nullptr : I->second;
565  }
566
567  const RetainSummary *& operator[](ObjCSummaryKey K) {
568    return M[K];
569  }
570
571  const RetainSummary *& operator[](Selector S) {
572    return M[ ObjCSummaryKey(S) ];
573  }
574};
575} // end anonymous namespace
576
577//===----------------------------------------------------------------------===//
578// Data structures for managing collections of summaries.
579//===----------------------------------------------------------------------===//
580
581namespace {
582class RetainSummaryManager {
583
584  //==-----------------------------------------------------------------==//
585  //  Typedefs.
586  //==-----------------------------------------------------------------==//
587
588  typedef llvm::DenseMap<const FunctionDecl*, const RetainSummary *>
589          FuncSummariesTy;
590
591  typedef ObjCSummaryCache ObjCMethodSummariesTy;
592
593  typedef llvm::FoldingSetNodeWrapper<RetainSummary> CachedSummaryNode;
594
595  //==-----------------------------------------------------------------==//
596  //  Data.
597  //==-----------------------------------------------------------------==//
598
599  /// Ctx - The ASTContext object for the analyzed ASTs.
600  ASTContext &Ctx;
601
602  /// GCEnabled - Records whether or not the analyzed code runs in GC mode.
603  const bool GCEnabled;
604
605  /// Records whether or not the analyzed code runs in ARC mode.
606  const bool ARCEnabled;
607
608  /// FuncSummaries - A map from FunctionDecls to summaries.
609  FuncSummariesTy FuncSummaries;
610
611  /// ObjCClassMethodSummaries - A map from selectors (for instance methods)
612  ///  to summaries.
613  ObjCMethodSummariesTy ObjCClassMethodSummaries;
614
615  /// ObjCMethodSummaries - A map from selectors to summaries.
616  ObjCMethodSummariesTy ObjCMethodSummaries;
617
618  /// BPAlloc - A BumpPtrAllocator used for allocating summaries, ArgEffects,
619  ///  and all other data used by the checker.
620  llvm::BumpPtrAllocator BPAlloc;
621
622  /// AF - A factory for ArgEffects objects.
623  ArgEffects::Factory AF;
624
625  /// ScratchArgs - A holding buffer for construct ArgEffects.
626  ArgEffects ScratchArgs;
627
628  /// ObjCAllocRetE - Default return effect for methods returning Objective-C
629  ///  objects.
630  RetEffect ObjCAllocRetE;
631
632  /// ObjCInitRetE - Default return effect for init methods returning
633  ///   Objective-C objects.
634  RetEffect ObjCInitRetE;
635
636  /// SimpleSummaries - Used for uniquing summaries that don't have special
637  /// effects.
638  llvm::FoldingSet<CachedSummaryNode> SimpleSummaries;
639
640  //==-----------------------------------------------------------------==//
641  //  Methods.
642  //==-----------------------------------------------------------------==//
643
644  /// getArgEffects - Returns a persistent ArgEffects object based on the
645  ///  data in ScratchArgs.
646  ArgEffects getArgEffects();
647
648  enum UnaryFuncKind { cfretain, cfrelease, cfautorelease, cfmakecollectable };
649
650  const RetainSummary *getUnarySummary(const FunctionType* FT,
651                                       UnaryFuncKind func);
652
653  const RetainSummary *getCFSummaryCreateRule(const FunctionDecl *FD);
654  const RetainSummary *getCFSummaryGetRule(const FunctionDecl *FD);
655  const RetainSummary *getCFCreateGetRuleSummary(const FunctionDecl *FD);
656
657  const RetainSummary *getPersistentSummary(const RetainSummary &OldSumm);
658
659  const RetainSummary *getPersistentSummary(RetEffect RetEff,
660                                            ArgEffect ReceiverEff = DoNothing,
661                                            ArgEffect DefaultEff = MayEscape) {
662    RetainSummary Summ(getArgEffects(), RetEff, DefaultEff, ReceiverEff);
663    return getPersistentSummary(Summ);
664  }
665
666  const RetainSummary *getDoNothingSummary() {
667    return getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
668  }
669
670  const RetainSummary *getDefaultSummary() {
671    return getPersistentSummary(RetEffect::MakeNoRet(),
672                                DoNothing, MayEscape);
673  }
674
675  const RetainSummary *getPersistentStopSummary() {
676    return getPersistentSummary(RetEffect::MakeNoRet(),
677                                StopTracking, StopTracking);
678  }
679
680  void InitializeClassMethodSummaries();
681  void InitializeMethodSummaries();
682private:
683  void addNSObjectClsMethSummary(Selector S, const RetainSummary *Summ) {
684    ObjCClassMethodSummaries[S] = Summ;
685  }
686
687  void addNSObjectMethSummary(Selector S, const RetainSummary *Summ) {
688    ObjCMethodSummaries[S] = Summ;
689  }
690
691  void addClassMethSummary(const char* Cls, const char* name,
692                           const RetainSummary *Summ, bool isNullary = true) {
693    IdentifierInfo* ClsII = &Ctx.Idents.get(Cls);
694    Selector S = isNullary ? GetNullarySelector(name, Ctx)
695                           : GetUnarySelector(name, Ctx);
696    ObjCClassMethodSummaries[ObjCSummaryKey(ClsII, S)]  = Summ;
697  }
698
699  void addInstMethSummary(const char* Cls, const char* nullaryName,
700                          const RetainSummary *Summ) {
701    IdentifierInfo* ClsII = &Ctx.Idents.get(Cls);
702    Selector S = GetNullarySelector(nullaryName, Ctx);
703    ObjCMethodSummaries[ObjCSummaryKey(ClsII, S)]  = Summ;
704  }
705
706  void addMethodSummary(IdentifierInfo *ClsII, ObjCMethodSummariesTy &Summaries,
707                        const RetainSummary *Summ, va_list argp) {
708    Selector S = getKeywordSelector(Ctx, argp);
709    Summaries[ObjCSummaryKey(ClsII, S)] = Summ;
710  }
711
712  void addInstMethSummary(const char* Cls, const RetainSummary * Summ, ...) {
713    va_list argp;
714    va_start(argp, Summ);
715    addMethodSummary(&Ctx.Idents.get(Cls), ObjCMethodSummaries, Summ, argp);
716    va_end(argp);
717  }
718
719  void addClsMethSummary(const char* Cls, const RetainSummary * Summ, ...) {
720    va_list argp;
721    va_start(argp, Summ);
722    addMethodSummary(&Ctx.Idents.get(Cls),ObjCClassMethodSummaries, Summ, argp);
723    va_end(argp);
724  }
725
726  void addClsMethSummary(IdentifierInfo *II, const RetainSummary * Summ, ...) {
727    va_list argp;
728    va_start(argp, Summ);
729    addMethodSummary(II, ObjCClassMethodSummaries, Summ, argp);
730    va_end(argp);
731  }
732
733public:
734
735  RetainSummaryManager(ASTContext &ctx, bool gcenabled, bool usesARC)
736   : Ctx(ctx),
737     GCEnabled(gcenabled),
738     ARCEnabled(usesARC),
739     AF(BPAlloc), ScratchArgs(AF.getEmptyMap()),
740     ObjCAllocRetE(gcenabled
741                    ? RetEffect::MakeGCNotOwned()
742                    : (usesARC ? RetEffect::MakeNotOwned(RetEffect::ObjC)
743                               : RetEffect::MakeOwned(RetEffect::ObjC, true))),
744     ObjCInitRetE(gcenabled
745                    ? RetEffect::MakeGCNotOwned()
746                    : (usesARC ? RetEffect::MakeNotOwned(RetEffect::ObjC)
747                               : RetEffect::MakeOwnedWhenTrackedReceiver())) {
748    InitializeClassMethodSummaries();
749    InitializeMethodSummaries();
750  }
751
752  const RetainSummary *getSummary(const CallEvent &Call,
753                                  ProgramStateRef State = nullptr);
754
755  const RetainSummary *getFunctionSummary(const FunctionDecl *FD);
756
757  const RetainSummary *getMethodSummary(Selector S, const ObjCInterfaceDecl *ID,
758                                        const ObjCMethodDecl *MD,
759                                        QualType RetTy,
760                                        ObjCMethodSummariesTy &CachedSummaries);
761
762  const RetainSummary *getInstanceMethodSummary(const ObjCMethodCall &M,
763                                                ProgramStateRef State);
764
765  const RetainSummary *getClassMethodSummary(const ObjCMethodCall &M) {
766    assert(!M.isInstanceMessage());
767    const ObjCInterfaceDecl *Class = M.getReceiverInterface();
768
769    return getMethodSummary(M.getSelector(), Class, M.getDecl(),
770                            M.getResultType(), ObjCClassMethodSummaries);
771  }
772
773  /// getMethodSummary - This version of getMethodSummary is used to query
774  ///  the summary for the current method being analyzed.
775  const RetainSummary *getMethodSummary(const ObjCMethodDecl *MD) {
776    const ObjCInterfaceDecl *ID = MD->getClassInterface();
777    Selector S = MD->getSelector();
778    QualType ResultTy = MD->getReturnType();
779
780    ObjCMethodSummariesTy *CachedSummaries;
781    if (MD->isInstanceMethod())
782      CachedSummaries = &ObjCMethodSummaries;
783    else
784      CachedSummaries = &ObjCClassMethodSummaries;
785
786    return getMethodSummary(S, ID, MD, ResultTy, *CachedSummaries);
787  }
788
789  const RetainSummary *getStandardMethodSummary(const ObjCMethodDecl *MD,
790                                                Selector S, QualType RetTy);
791
792  /// Determine if there is a special return effect for this function or method.
793  Optional<RetEffect> getRetEffectFromAnnotations(QualType RetTy,
794                                                  const Decl *D);
795
796  void updateSummaryFromAnnotations(const RetainSummary *&Summ,
797                                    const ObjCMethodDecl *MD);
798
799  void updateSummaryFromAnnotations(const RetainSummary *&Summ,
800                                    const FunctionDecl *FD);
801
802  void updateSummaryForCall(const RetainSummary *&Summ,
803                            const CallEvent &Call);
804
805  bool isGCEnabled() const { return GCEnabled; }
806
807  bool isARCEnabled() const { return ARCEnabled; }
808
809  bool isARCorGCEnabled() const { return GCEnabled || ARCEnabled; }
810
811  RetEffect getObjAllocRetEffect() const { return ObjCAllocRetE; }
812
813  friend class RetainSummaryTemplate;
814};
815
816// Used to avoid allocating long-term (BPAlloc'd) memory for default retain
817// summaries. If a function or method looks like it has a default summary, but
818// it has annotations, the annotations are added to the stack-based template
819// and then copied into managed memory.
820class RetainSummaryTemplate {
821  RetainSummaryManager &Manager;
822  const RetainSummary *&RealSummary;
823  RetainSummary ScratchSummary;
824  bool Accessed;
825public:
826  RetainSummaryTemplate(const RetainSummary *&real, RetainSummaryManager &mgr)
827    : Manager(mgr), RealSummary(real), ScratchSummary(*real), Accessed(false) {}
828
829  ~RetainSummaryTemplate() {
830    if (Accessed)
831      RealSummary = Manager.getPersistentSummary(ScratchSummary);
832  }
833
834  RetainSummary &operator*() {
835    Accessed = true;
836    return ScratchSummary;
837  }
838
839  RetainSummary *operator->() {
840    Accessed = true;
841    return &ScratchSummary;
842  }
843};
844
845} // end anonymous namespace
846
847//===----------------------------------------------------------------------===//
848// Implementation of checker data structures.
849//===----------------------------------------------------------------------===//
850
851ArgEffects RetainSummaryManager::getArgEffects() {
852  ArgEffects AE = ScratchArgs;
853  ScratchArgs = AF.getEmptyMap();
854  return AE;
855}
856
857const RetainSummary *
858RetainSummaryManager::getPersistentSummary(const RetainSummary &OldSumm) {
859  // Unique "simple" summaries -- those without ArgEffects.
860  if (OldSumm.isSimple()) {
861    llvm::FoldingSetNodeID ID;
862    OldSumm.Profile(ID);
863
864    void *Pos;
865    CachedSummaryNode *N = SimpleSummaries.FindNodeOrInsertPos(ID, Pos);
866
867    if (!N) {
868      N = (CachedSummaryNode *) BPAlloc.Allocate<CachedSummaryNode>();
869      new (N) CachedSummaryNode(OldSumm);
870      SimpleSummaries.InsertNode(N, Pos);
871    }
872
873    return &N->getValue();
874  }
875
876  RetainSummary *Summ = (RetainSummary *) BPAlloc.Allocate<RetainSummary>();
877  new (Summ) RetainSummary(OldSumm);
878  return Summ;
879}
880
881//===----------------------------------------------------------------------===//
882// Summary creation for functions (largely uses of Core Foundation).
883//===----------------------------------------------------------------------===//
884
885static bool isRetain(const FunctionDecl *FD, StringRef FName) {
886  return FName.endswith("Retain");
887}
888
889static bool isRelease(const FunctionDecl *FD, StringRef FName) {
890  return FName.endswith("Release");
891}
892
893static bool isAutorelease(const FunctionDecl *FD, StringRef FName) {
894  return FName.endswith("Autorelease");
895}
896
897static bool isMakeCollectable(const FunctionDecl *FD, StringRef FName) {
898  // FIXME: Remove FunctionDecl parameter.
899  // FIXME: Is it really okay if MakeCollectable isn't a suffix?
900  return FName.find("MakeCollectable") != StringRef::npos;
901}
902
903static ArgEffect getStopTrackingHardEquivalent(ArgEffect E) {
904  switch (E) {
905  case DoNothing:
906  case Autorelease:
907  case DecRefBridgedTransferred:
908  case IncRef:
909  case IncRefMsg:
910  case MakeCollectable:
911  case UnretainedOutParameter:
912  case RetainedOutParameter:
913  case MayEscape:
914  case StopTracking:
915  case StopTrackingHard:
916    return StopTrackingHard;
917  case DecRef:
918  case DecRefAndStopTrackingHard:
919    return DecRefAndStopTrackingHard;
920  case DecRefMsg:
921  case DecRefMsgAndStopTrackingHard:
922    return DecRefMsgAndStopTrackingHard;
923  case Dealloc:
924    return Dealloc;
925  }
926
927  llvm_unreachable("Unknown ArgEffect kind");
928}
929
930void RetainSummaryManager::updateSummaryForCall(const RetainSummary *&S,
931                                                const CallEvent &Call) {
932  if (Call.hasNonZeroCallbackArg()) {
933    ArgEffect RecEffect =
934      getStopTrackingHardEquivalent(S->getReceiverEffect());
935    ArgEffect DefEffect =
936      getStopTrackingHardEquivalent(S->getDefaultArgEffect());
937
938    ArgEffects CustomArgEffects = S->getArgEffects();
939    for (ArgEffects::iterator I = CustomArgEffects.begin(),
940                              E = CustomArgEffects.end();
941         I != E; ++I) {
942      ArgEffect Translated = getStopTrackingHardEquivalent(I->second);
943      if (Translated != DefEffect)
944        ScratchArgs = AF.add(ScratchArgs, I->first, Translated);
945    }
946
947    RetEffect RE = RetEffect::MakeNoRetHard();
948
949    // Special cases where the callback argument CANNOT free the return value.
950    // This can generally only happen if we know that the callback will only be
951    // called when the return value is already being deallocated.
952    if (const SimpleFunctionCall *FC = dyn_cast<SimpleFunctionCall>(&Call)) {
953      if (IdentifierInfo *Name = FC->getDecl()->getIdentifier()) {
954        // When the CGBitmapContext is deallocated, the callback here will free
955        // the associated data buffer.
956        if (Name->isStr("CGBitmapContextCreateWithData"))
957          RE = S->getRetEffect();
958      }
959    }
960
961    S = getPersistentSummary(RE, RecEffect, DefEffect);
962  }
963
964  // Special case '[super init];' and '[self init];'
965  //
966  // Even though calling '[super init]' without assigning the result to self
967  // and checking if the parent returns 'nil' is a bad pattern, it is common.
968  // Additionally, our Self Init checker already warns about it. To avoid
969  // overwhelming the user with messages from both checkers, we model the case
970  // of '[super init]' in cases when it is not consumed by another expression
971  // as if the call preserves the value of 'self'; essentially, assuming it can
972  // never fail and return 'nil'.
973  // Note, we don't want to just stop tracking the value since we want the
974  // RetainCount checker to report leaks and use-after-free if SelfInit checker
975  // is turned off.
976  if (const ObjCMethodCall *MC = dyn_cast<ObjCMethodCall>(&Call)) {
977    if (MC->getMethodFamily() == OMF_init && MC->isReceiverSelfOrSuper()) {
978
979      // Check if the message is not consumed, we know it will not be used in
980      // an assignment, ex: "self = [super init]".
981      const Expr *ME = MC->getOriginExpr();
982      const LocationContext *LCtx = MC->getLocationContext();
983      ParentMap &PM = LCtx->getAnalysisDeclContext()->getParentMap();
984      if (!PM.isConsumedExpr(ME)) {
985        RetainSummaryTemplate ModifiableSummaryTemplate(S, *this);
986        ModifiableSummaryTemplate->setReceiverEffect(DoNothing);
987        ModifiableSummaryTemplate->setRetEffect(RetEffect::MakeNoRet());
988      }
989    }
990  }
991}
992
993const RetainSummary *
994RetainSummaryManager::getSummary(const CallEvent &Call,
995                                 ProgramStateRef State) {
996  const RetainSummary *Summ;
997  switch (Call.getKind()) {
998  case CE_Function:
999    Summ = getFunctionSummary(cast<SimpleFunctionCall>(Call).getDecl());
1000    break;
1001  case CE_CXXMember:
1002  case CE_CXXMemberOperator:
1003  case CE_Block:
1004  case CE_CXXConstructor:
1005  case CE_CXXDestructor:
1006  case CE_CXXAllocator:
1007    // FIXME: These calls are currently unsupported.
1008    return getPersistentStopSummary();
1009  case CE_ObjCMessage: {
1010    const ObjCMethodCall &Msg = cast<ObjCMethodCall>(Call);
1011    if (Msg.isInstanceMessage())
1012      Summ = getInstanceMethodSummary(Msg, State);
1013    else
1014      Summ = getClassMethodSummary(Msg);
1015    break;
1016  }
1017  }
1018
1019  updateSummaryForCall(Summ, Call);
1020
1021  assert(Summ && "Unknown call type?");
1022  return Summ;
1023}
1024
1025const RetainSummary *
1026RetainSummaryManager::getFunctionSummary(const FunctionDecl *FD) {
1027  // If we don't know what function we're calling, use our default summary.
1028  if (!FD)
1029    return getDefaultSummary();
1030
1031  // Look up a summary in our cache of FunctionDecls -> Summaries.
1032  FuncSummariesTy::iterator I = FuncSummaries.find(FD);
1033  if (I != FuncSummaries.end())
1034    return I->second;
1035
1036  // No summary?  Generate one.
1037  const RetainSummary *S = nullptr;
1038  bool AllowAnnotations = true;
1039
1040  do {
1041    // We generate "stop" summaries for implicitly defined functions.
1042    if (FD->isImplicit()) {
1043      S = getPersistentStopSummary();
1044      break;
1045    }
1046
1047    // [PR 3337] Use 'getAs<FunctionType>' to strip away any typedefs on the
1048    // function's type.
1049    const FunctionType* FT = FD->getType()->getAs<FunctionType>();
1050    const IdentifierInfo *II = FD->getIdentifier();
1051    if (!II)
1052      break;
1053
1054    StringRef FName = II->getName();
1055
1056    // Strip away preceding '_'.  Doing this here will effect all the checks
1057    // down below.
1058    FName = FName.substr(FName.find_first_not_of('_'));
1059
1060    // Inspect the result type.
1061    QualType RetTy = FT->getReturnType();
1062
1063    // FIXME: This should all be refactored into a chain of "summary lookup"
1064    //  filters.
1065    assert(ScratchArgs.isEmpty());
1066
1067    if (FName == "pthread_create" || FName == "pthread_setspecific") {
1068      // Part of: <rdar://problem/7299394> and <rdar://problem/11282706>.
1069      // This will be addressed better with IPA.
1070      S = getPersistentStopSummary();
1071    } else if (FName == "NSMakeCollectable") {
1072      // Handle: id NSMakeCollectable(CFTypeRef)
1073      S = (RetTy->isObjCIdType())
1074          ? getUnarySummary(FT, cfmakecollectable)
1075          : getPersistentStopSummary();
1076      // The headers on OS X 10.8 use cf_consumed/ns_returns_retained,
1077      // but we can fully model NSMakeCollectable ourselves.
1078      AllowAnnotations = false;
1079    } else if (FName == "CFPlugInInstanceCreate") {
1080      S = getPersistentSummary(RetEffect::MakeNoRet());
1081    } else if (FName == "IOBSDNameMatching" ||
1082               FName == "IOServiceMatching" ||
1083               FName == "IOServiceNameMatching" ||
1084               FName == "IORegistryEntrySearchCFProperty" ||
1085               FName == "IORegistryEntryIDMatching" ||
1086               FName == "IOOpenFirmwarePathMatching") {
1087      // Part of <rdar://problem/6961230>. (IOKit)
1088      // This should be addressed using a API table.
1089      S = getPersistentSummary(RetEffect::MakeOwned(RetEffect::CF, true),
1090                               DoNothing, DoNothing);
1091    } else if (FName == "IOServiceGetMatchingService" ||
1092               FName == "IOServiceGetMatchingServices") {
1093      // FIXES: <rdar://problem/6326900>
1094      // This should be addressed using a API table.  This strcmp is also
1095      // a little gross, but there is no need to super optimize here.
1096      ScratchArgs = AF.add(ScratchArgs, 1, DecRef);
1097      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1098    } else if (FName == "IOServiceAddNotification" ||
1099               FName == "IOServiceAddMatchingNotification") {
1100      // Part of <rdar://problem/6961230>. (IOKit)
1101      // This should be addressed using a API table.
1102      ScratchArgs = AF.add(ScratchArgs, 2, DecRef);
1103      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1104    } else if (FName == "CVPixelBufferCreateWithBytes") {
1105      // FIXES: <rdar://problem/7283567>
1106      // Eventually this can be improved by recognizing that the pixel
1107      // buffer passed to CVPixelBufferCreateWithBytes is released via
1108      // a callback and doing full IPA to make sure this is done correctly.
1109      // FIXME: This function has an out parameter that returns an
1110      // allocated object.
1111      ScratchArgs = AF.add(ScratchArgs, 7, StopTracking);
1112      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1113    } else if (FName == "CGBitmapContextCreateWithData") {
1114      // FIXES: <rdar://problem/7358899>
1115      // Eventually this can be improved by recognizing that 'releaseInfo'
1116      // passed to CGBitmapContextCreateWithData is released via
1117      // a callback and doing full IPA to make sure this is done correctly.
1118      ScratchArgs = AF.add(ScratchArgs, 8, StopTracking);
1119      S = getPersistentSummary(RetEffect::MakeOwned(RetEffect::CF, true),
1120                               DoNothing, DoNothing);
1121    } else if (FName == "CVPixelBufferCreateWithPlanarBytes") {
1122      // FIXES: <rdar://problem/7283567>
1123      // Eventually this can be improved by recognizing that the pixel
1124      // buffer passed to CVPixelBufferCreateWithPlanarBytes is released
1125      // via a callback and doing full IPA to make sure this is done
1126      // correctly.
1127      ScratchArgs = AF.add(ScratchArgs, 12, StopTracking);
1128      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1129    } else if (FName == "dispatch_set_context" ||
1130               FName == "xpc_connection_set_context") {
1131      // <rdar://problem/11059275> - The analyzer currently doesn't have
1132      // a good way to reason about the finalizer function for libdispatch.
1133      // If we pass a context object that is memory managed, stop tracking it.
1134      // <rdar://problem/13783514> - Same problem, but for XPC.
1135      // FIXME: this hack should possibly go away once we can handle
1136      // libdispatch and XPC finalizers.
1137      ScratchArgs = AF.add(ScratchArgs, 1, StopTracking);
1138      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1139    } else if (FName.startswith("NSLog")) {
1140      S = getDoNothingSummary();
1141    } else if (FName.startswith("NS") &&
1142                (FName.find("Insert") != StringRef::npos)) {
1143      // Whitelist NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
1144      // be deallocated by NSMapRemove. (radar://11152419)
1145      ScratchArgs = AF.add(ScratchArgs, 1, StopTracking);
1146      ScratchArgs = AF.add(ScratchArgs, 2, StopTracking);
1147      S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1148    }
1149
1150    // Did we get a summary?
1151    if (S)
1152      break;
1153
1154    if (RetTy->isPointerType()) {
1155      // For CoreFoundation ('CF') types.
1156      if (cocoa::isRefType(RetTy, "CF", FName)) {
1157        if (isRetain(FD, FName)) {
1158          S = getUnarySummary(FT, cfretain);
1159        } else if (isAutorelease(FD, FName)) {
1160          S = getUnarySummary(FT, cfautorelease);
1161          // The headers use cf_consumed, but we can fully model CFAutorelease
1162          // ourselves.
1163          AllowAnnotations = false;
1164        } else if (isMakeCollectable(FD, FName)) {
1165          S = getUnarySummary(FT, cfmakecollectable);
1166          AllowAnnotations = false;
1167        } else {
1168          S = getCFCreateGetRuleSummary(FD);
1169        }
1170
1171        break;
1172      }
1173
1174      // For CoreGraphics ('CG') types.
1175      if (cocoa::isRefType(RetTy, "CG", FName)) {
1176        if (isRetain(FD, FName))
1177          S = getUnarySummary(FT, cfretain);
1178        else
1179          S = getCFCreateGetRuleSummary(FD);
1180
1181        break;
1182      }
1183
1184      // For the Disk Arbitration API (DiskArbitration/DADisk.h)
1185      if (cocoa::isRefType(RetTy, "DADisk") ||
1186          cocoa::isRefType(RetTy, "DADissenter") ||
1187          cocoa::isRefType(RetTy, "DASessionRef")) {
1188        S = getCFCreateGetRuleSummary(FD);
1189        break;
1190      }
1191
1192      if (FD->hasAttr<CFAuditedTransferAttr>()) {
1193        S = getCFCreateGetRuleSummary(FD);
1194        break;
1195      }
1196
1197      break;
1198    }
1199
1200    // Check for release functions, the only kind of functions that we care
1201    // about that don't return a pointer type.
1202    if (FName[0] == 'C' && (FName[1] == 'F' || FName[1] == 'G')) {
1203      // Test for 'CGCF'.
1204      FName = FName.substr(FName.startswith("CGCF") ? 4 : 2);
1205
1206      if (isRelease(FD, FName))
1207        S = getUnarySummary(FT, cfrelease);
1208      else {
1209        assert (ScratchArgs.isEmpty());
1210        // Remaining CoreFoundation and CoreGraphics functions.
1211        // We use to assume that they all strictly followed the ownership idiom
1212        // and that ownership cannot be transferred.  While this is technically
1213        // correct, many methods allow a tracked object to escape.  For example:
1214        //
1215        //   CFMutableDictionaryRef x = CFDictionaryCreateMutable(...);
1216        //   CFDictionaryAddValue(y, key, x);
1217        //   CFRelease(x);
1218        //   ... it is okay to use 'x' since 'y' has a reference to it
1219        //
1220        // We handle this and similar cases with the follow heuristic.  If the
1221        // function name contains "InsertValue", "SetValue", "AddValue",
1222        // "AppendValue", or "SetAttribute", then we assume that arguments may
1223        // "escape."  This means that something else holds on to the object,
1224        // allowing it be used even after its local retain count drops to 0.
1225        ArgEffect E = (StrInStrNoCase(FName, "InsertValue") != StringRef::npos||
1226                       StrInStrNoCase(FName, "AddValue") != StringRef::npos ||
1227                       StrInStrNoCase(FName, "SetValue") != StringRef::npos ||
1228                       StrInStrNoCase(FName, "AppendValue") != StringRef::npos||
1229                       StrInStrNoCase(FName, "SetAttribute") != StringRef::npos)
1230                      ? MayEscape : DoNothing;
1231
1232        S = getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, E);
1233      }
1234    }
1235  }
1236  while (0);
1237
1238  // If we got all the way here without any luck, use a default summary.
1239  if (!S)
1240    S = getDefaultSummary();
1241
1242  // Annotations override defaults.
1243  if (AllowAnnotations)
1244    updateSummaryFromAnnotations(S, FD);
1245
1246  FuncSummaries[FD] = S;
1247  return S;
1248}
1249
1250const RetainSummary *
1251RetainSummaryManager::getCFCreateGetRuleSummary(const FunctionDecl *FD) {
1252  if (coreFoundation::followsCreateRule(FD))
1253    return getCFSummaryCreateRule(FD);
1254
1255  return getCFSummaryGetRule(FD);
1256}
1257
1258const RetainSummary *
1259RetainSummaryManager::getUnarySummary(const FunctionType* FT,
1260                                      UnaryFuncKind func) {
1261
1262  // Sanity check that this is *really* a unary function.  This can
1263  // happen if people do weird things.
1264  const FunctionProtoType* FTP = dyn_cast<FunctionProtoType>(FT);
1265  if (!FTP || FTP->getNumParams() != 1)
1266    return getPersistentStopSummary();
1267
1268  assert (ScratchArgs.isEmpty());
1269
1270  ArgEffect Effect;
1271  switch (func) {
1272  case cfretain: Effect = IncRef; break;
1273  case cfrelease: Effect = DecRef; break;
1274  case cfautorelease: Effect = Autorelease; break;
1275  case cfmakecollectable: Effect = MakeCollectable; break;
1276  }
1277
1278  ScratchArgs = AF.add(ScratchArgs, 0, Effect);
1279  return getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
1280}
1281
1282const RetainSummary *
1283RetainSummaryManager::getCFSummaryCreateRule(const FunctionDecl *FD) {
1284  assert (ScratchArgs.isEmpty());
1285
1286  return getPersistentSummary(RetEffect::MakeOwned(RetEffect::CF, true));
1287}
1288
1289const RetainSummary *
1290RetainSummaryManager::getCFSummaryGetRule(const FunctionDecl *FD) {
1291  assert (ScratchArgs.isEmpty());
1292  return getPersistentSummary(RetEffect::MakeNotOwned(RetEffect::CF),
1293                              DoNothing, DoNothing);
1294}
1295
1296//===----------------------------------------------------------------------===//
1297// Summary creation for Selectors.
1298//===----------------------------------------------------------------------===//
1299
1300Optional<RetEffect>
1301RetainSummaryManager::getRetEffectFromAnnotations(QualType RetTy,
1302                                                  const Decl *D) {
1303  if (cocoa::isCocoaObjectRef(RetTy)) {
1304    if (D->hasAttr<NSReturnsRetainedAttr>())
1305      return ObjCAllocRetE;
1306
1307    if (D->hasAttr<NSReturnsNotRetainedAttr>() ||
1308        D->hasAttr<NSReturnsAutoreleasedAttr>())
1309      return RetEffect::MakeNotOwned(RetEffect::ObjC);
1310
1311  } else if (!RetTy->isPointerType()) {
1312    return None;
1313  }
1314
1315  if (D->hasAttr<CFReturnsRetainedAttr>())
1316    return RetEffect::MakeOwned(RetEffect::CF, true);
1317
1318  if (D->hasAttr<CFReturnsNotRetainedAttr>())
1319    return RetEffect::MakeNotOwned(RetEffect::CF);
1320
1321  return None;
1322}
1323
1324void
1325RetainSummaryManager::updateSummaryFromAnnotations(const RetainSummary *&Summ,
1326                                                   const FunctionDecl *FD) {
1327  if (!FD)
1328    return;
1329
1330  assert(Summ && "Must have a summary to add annotations to.");
1331  RetainSummaryTemplate Template(Summ, *this);
1332
1333  // Effects on the parameters.
1334  unsigned parm_idx = 0;
1335  for (FunctionDecl::param_const_iterator pi = FD->param_begin(),
1336         pe = FD->param_end(); pi != pe; ++pi, ++parm_idx) {
1337    const ParmVarDecl *pd = *pi;
1338    if (pd->hasAttr<NSConsumedAttr>())
1339      Template->addArg(AF, parm_idx, DecRefMsg);
1340    else if (pd->hasAttr<CFConsumedAttr>())
1341      Template->addArg(AF, parm_idx, DecRef);
1342    else if (pd->hasAttr<CFReturnsRetainedAttr>()) {
1343      QualType PointeeTy = pd->getType()->getPointeeType();
1344      if (!PointeeTy.isNull())
1345        if (coreFoundation::isCFObjectRef(PointeeTy))
1346          Template->addArg(AF, parm_idx, RetainedOutParameter);
1347    } else if (pd->hasAttr<CFReturnsNotRetainedAttr>()) {
1348      QualType PointeeTy = pd->getType()->getPointeeType();
1349      if (!PointeeTy.isNull())
1350        if (coreFoundation::isCFObjectRef(PointeeTy))
1351          Template->addArg(AF, parm_idx, UnretainedOutParameter);
1352    }
1353  }
1354
1355  QualType RetTy = FD->getReturnType();
1356  if (Optional<RetEffect> RetE = getRetEffectFromAnnotations(RetTy, FD))
1357    Template->setRetEffect(*RetE);
1358}
1359
1360void
1361RetainSummaryManager::updateSummaryFromAnnotations(const RetainSummary *&Summ,
1362                                                   const ObjCMethodDecl *MD) {
1363  if (!MD)
1364    return;
1365
1366  assert(Summ && "Must have a valid summary to add annotations to");
1367  RetainSummaryTemplate Template(Summ, *this);
1368
1369  // Effects on the receiver.
1370  if (MD->hasAttr<NSConsumesSelfAttr>())
1371    Template->setReceiverEffect(DecRefMsg);
1372
1373  // Effects on the parameters.
1374  unsigned parm_idx = 0;
1375  for (ObjCMethodDecl::param_const_iterator
1376         pi=MD->param_begin(), pe=MD->param_end();
1377       pi != pe; ++pi, ++parm_idx) {
1378    const ParmVarDecl *pd = *pi;
1379    if (pd->hasAttr<NSConsumedAttr>())
1380      Template->addArg(AF, parm_idx, DecRefMsg);
1381    else if (pd->hasAttr<CFConsumedAttr>()) {
1382      Template->addArg(AF, parm_idx, DecRef);
1383    } else if (pd->hasAttr<CFReturnsRetainedAttr>()) {
1384      QualType PointeeTy = pd->getType()->getPointeeType();
1385      if (!PointeeTy.isNull())
1386        if (coreFoundation::isCFObjectRef(PointeeTy))
1387          Template->addArg(AF, parm_idx, RetainedOutParameter);
1388    } else if (pd->hasAttr<CFReturnsNotRetainedAttr>()) {
1389      QualType PointeeTy = pd->getType()->getPointeeType();
1390      if (!PointeeTy.isNull())
1391        if (coreFoundation::isCFObjectRef(PointeeTy))
1392          Template->addArg(AF, parm_idx, UnretainedOutParameter);
1393    }
1394  }
1395
1396  QualType RetTy = MD->getReturnType();
1397  if (Optional<RetEffect> RetE = getRetEffectFromAnnotations(RetTy, MD))
1398    Template->setRetEffect(*RetE);
1399}
1400
1401const RetainSummary *
1402RetainSummaryManager::getStandardMethodSummary(const ObjCMethodDecl *MD,
1403                                               Selector S, QualType RetTy) {
1404  // Any special effects?
1405  ArgEffect ReceiverEff = DoNothing;
1406  RetEffect ResultEff = RetEffect::MakeNoRet();
1407
1408  // Check the method family, and apply any default annotations.
1409  switch (MD ? MD->getMethodFamily() : S.getMethodFamily()) {
1410    case OMF_None:
1411    case OMF_initialize:
1412    case OMF_performSelector:
1413      // Assume all Objective-C methods follow Cocoa Memory Management rules.
1414      // FIXME: Does the non-threaded performSelector family really belong here?
1415      // The selector could be, say, @selector(copy).
1416      if (cocoa::isCocoaObjectRef(RetTy))
1417        ResultEff = RetEffect::MakeNotOwned(RetEffect::ObjC);
1418      else if (coreFoundation::isCFObjectRef(RetTy)) {
1419        // ObjCMethodDecl currently doesn't consider CF objects as valid return
1420        // values for alloc, new, copy, or mutableCopy, so we have to
1421        // double-check with the selector. This is ugly, but there aren't that
1422        // many Objective-C methods that return CF objects, right?
1423        if (MD) {
1424          switch (S.getMethodFamily()) {
1425          case OMF_alloc:
1426          case OMF_new:
1427          case OMF_copy:
1428          case OMF_mutableCopy:
1429            ResultEff = RetEffect::MakeOwned(RetEffect::CF, true);
1430            break;
1431          default:
1432            ResultEff = RetEffect::MakeNotOwned(RetEffect::CF);
1433            break;
1434          }
1435        } else {
1436          ResultEff = RetEffect::MakeNotOwned(RetEffect::CF);
1437        }
1438      }
1439      break;
1440    case OMF_init:
1441      ResultEff = ObjCInitRetE;
1442      ReceiverEff = DecRefMsg;
1443      break;
1444    case OMF_alloc:
1445    case OMF_new:
1446    case OMF_copy:
1447    case OMF_mutableCopy:
1448      if (cocoa::isCocoaObjectRef(RetTy))
1449        ResultEff = ObjCAllocRetE;
1450      else if (coreFoundation::isCFObjectRef(RetTy))
1451        ResultEff = RetEffect::MakeOwned(RetEffect::CF, true);
1452      break;
1453    case OMF_autorelease:
1454      ReceiverEff = Autorelease;
1455      break;
1456    case OMF_retain:
1457      ReceiverEff = IncRefMsg;
1458      break;
1459    case OMF_release:
1460      ReceiverEff = DecRefMsg;
1461      break;
1462    case OMF_dealloc:
1463      ReceiverEff = Dealloc;
1464      break;
1465    case OMF_self:
1466      // -self is handled specially by the ExprEngine to propagate the receiver.
1467      break;
1468    case OMF_retainCount:
1469    case OMF_finalize:
1470      // These methods don't return objects.
1471      break;
1472  }
1473
1474  // If one of the arguments in the selector has the keyword 'delegate' we
1475  // should stop tracking the reference count for the receiver.  This is
1476  // because the reference count is quite possibly handled by a delegate
1477  // method.
1478  if (S.isKeywordSelector()) {
1479    for (unsigned i = 0, e = S.getNumArgs(); i != e; ++i) {
1480      StringRef Slot = S.getNameForSlot(i);
1481      if (Slot.substr(Slot.size() - 8).equals_lower("delegate")) {
1482        if (ResultEff == ObjCInitRetE)
1483          ResultEff = RetEffect::MakeNoRetHard();
1484        else
1485          ReceiverEff = StopTrackingHard;
1486      }
1487    }
1488  }
1489
1490  if (ScratchArgs.isEmpty() && ReceiverEff == DoNothing &&
1491      ResultEff.getKind() == RetEffect::NoRet)
1492    return getDefaultSummary();
1493
1494  return getPersistentSummary(ResultEff, ReceiverEff, MayEscape);
1495}
1496
1497const RetainSummary *
1498RetainSummaryManager::getInstanceMethodSummary(const ObjCMethodCall &Msg,
1499                                               ProgramStateRef State) {
1500  const ObjCInterfaceDecl *ReceiverClass = nullptr;
1501
1502  // We do better tracking of the type of the object than the core ExprEngine.
1503  // See if we have its type in our private state.
1504  // FIXME: Eventually replace the use of state->get<RefBindings> with
1505  // a generic API for reasoning about the Objective-C types of symbolic
1506  // objects.
1507  SVal ReceiverV = Msg.getReceiverSVal();
1508  if (SymbolRef Sym = ReceiverV.getAsLocSymbol())
1509    if (const RefVal *T = getRefBinding(State, Sym))
1510      if (const ObjCObjectPointerType *PT =
1511            T->getType()->getAs<ObjCObjectPointerType>())
1512        ReceiverClass = PT->getInterfaceDecl();
1513
1514  // If we don't know what kind of object this is, fall back to its static type.
1515  if (!ReceiverClass)
1516    ReceiverClass = Msg.getReceiverInterface();
1517
1518  // FIXME: The receiver could be a reference to a class, meaning that
1519  //  we should use the class method.
1520  // id x = [NSObject class];
1521  // [x performSelector:... withObject:... afterDelay:...];
1522  Selector S = Msg.getSelector();
1523  const ObjCMethodDecl *Method = Msg.getDecl();
1524  if (!Method && ReceiverClass)
1525    Method = ReceiverClass->getInstanceMethod(S);
1526
1527  return getMethodSummary(S, ReceiverClass, Method, Msg.getResultType(),
1528                          ObjCMethodSummaries);
1529}
1530
1531const RetainSummary *
1532RetainSummaryManager::getMethodSummary(Selector S, const ObjCInterfaceDecl *ID,
1533                                       const ObjCMethodDecl *MD, QualType RetTy,
1534                                       ObjCMethodSummariesTy &CachedSummaries) {
1535
1536  // Look up a summary in our summary cache.
1537  const RetainSummary *Summ = CachedSummaries.find(ID, S);
1538
1539  if (!Summ) {
1540    Summ = getStandardMethodSummary(MD, S, RetTy);
1541
1542    // Annotations override defaults.
1543    updateSummaryFromAnnotations(Summ, MD);
1544
1545    // Memoize the summary.
1546    CachedSummaries[ObjCSummaryKey(ID, S)] = Summ;
1547  }
1548
1549  return Summ;
1550}
1551
1552void RetainSummaryManager::InitializeClassMethodSummaries() {
1553  assert(ScratchArgs.isEmpty());
1554  // Create the [NSAssertionHandler currentHander] summary.
1555  addClassMethSummary("NSAssertionHandler", "currentHandler",
1556                getPersistentSummary(RetEffect::MakeNotOwned(RetEffect::ObjC)));
1557
1558  // Create the [NSAutoreleasePool addObject:] summary.
1559  ScratchArgs = AF.add(ScratchArgs, 0, Autorelease);
1560  addClassMethSummary("NSAutoreleasePool", "addObject",
1561                      getPersistentSummary(RetEffect::MakeNoRet(),
1562                                           DoNothing, Autorelease));
1563}
1564
1565void RetainSummaryManager::InitializeMethodSummaries() {
1566
1567  assert (ScratchArgs.isEmpty());
1568
1569  // Create the "init" selector.  It just acts as a pass-through for the
1570  // receiver.
1571  const RetainSummary *InitSumm = getPersistentSummary(ObjCInitRetE, DecRefMsg);
1572  addNSObjectMethSummary(GetNullarySelector("init", Ctx), InitSumm);
1573
1574  // awakeAfterUsingCoder: behaves basically like an 'init' method.  It
1575  // claims the receiver and returns a retained object.
1576  addNSObjectMethSummary(GetUnarySelector("awakeAfterUsingCoder", Ctx),
1577                         InitSumm);
1578
1579  // The next methods are allocators.
1580  const RetainSummary *AllocSumm = getPersistentSummary(ObjCAllocRetE);
1581  const RetainSummary *CFAllocSumm =
1582    getPersistentSummary(RetEffect::MakeOwned(RetEffect::CF, true));
1583
1584  // Create the "retain" selector.
1585  RetEffect NoRet = RetEffect::MakeNoRet();
1586  const RetainSummary *Summ = getPersistentSummary(NoRet, IncRefMsg);
1587  addNSObjectMethSummary(GetNullarySelector("retain", Ctx), Summ);
1588
1589  // Create the "release" selector.
1590  Summ = getPersistentSummary(NoRet, DecRefMsg);
1591  addNSObjectMethSummary(GetNullarySelector("release", Ctx), Summ);
1592
1593  // Create the -dealloc summary.
1594  Summ = getPersistentSummary(NoRet, Dealloc);
1595  addNSObjectMethSummary(GetNullarySelector("dealloc", Ctx), Summ);
1596
1597  // Create the "autorelease" selector.
1598  Summ = getPersistentSummary(NoRet, Autorelease);
1599  addNSObjectMethSummary(GetNullarySelector("autorelease", Ctx), Summ);
1600
1601  // For NSWindow, allocated objects are (initially) self-owned.
1602  // FIXME: For now we opt for false negatives with NSWindow, as these objects
1603  //  self-own themselves.  However, they only do this once they are displayed.
1604  //  Thus, we need to track an NSWindow's display status.
1605  //  This is tracked in <rdar://problem/6062711>.
1606  //  See also http://llvm.org/bugs/show_bug.cgi?id=3714.
1607  const RetainSummary *NoTrackYet = getPersistentSummary(RetEffect::MakeNoRet(),
1608                                                   StopTracking,
1609                                                   StopTracking);
1610
1611  addClassMethSummary("NSWindow", "alloc", NoTrackYet);
1612
1613  // For NSPanel (which subclasses NSWindow), allocated objects are not
1614  //  self-owned.
1615  // FIXME: For now we don't track NSPanels. object for the same reason
1616  //   as for NSWindow objects.
1617  addClassMethSummary("NSPanel", "alloc", NoTrackYet);
1618
1619  // For NSNull, objects returned by +null are singletons that ignore
1620  // retain/release semantics.  Just don't track them.
1621  // <rdar://problem/12858915>
1622  addClassMethSummary("NSNull", "null", NoTrackYet);
1623
1624  // Don't track allocated autorelease pools, as it is okay to prematurely
1625  // exit a method.
1626  addClassMethSummary("NSAutoreleasePool", "alloc", NoTrackYet);
1627  addClassMethSummary("NSAutoreleasePool", "allocWithZone", NoTrackYet, false);
1628  addClassMethSummary("NSAutoreleasePool", "new", NoTrackYet);
1629
1630  // Create summaries QCRenderer/QCView -createSnapShotImageOfType:
1631  addInstMethSummary("QCRenderer", AllocSumm,
1632                     "createSnapshotImageOfType", nullptr);
1633  addInstMethSummary("QCView", AllocSumm,
1634                     "createSnapshotImageOfType", nullptr);
1635
1636  // Create summaries for CIContext, 'createCGImage' and
1637  // 'createCGLayerWithSize'.  These objects are CF objects, and are not
1638  // automatically garbage collected.
1639  addInstMethSummary("CIContext", CFAllocSumm,
1640                     "createCGImage", "fromRect", nullptr);
1641  addInstMethSummary("CIContext", CFAllocSumm, "createCGImage", "fromRect",
1642                     "format", "colorSpace", nullptr);
1643  addInstMethSummary("CIContext", CFAllocSumm, "createCGLayerWithSize", "info",
1644                     nullptr);
1645}
1646
1647//===----------------------------------------------------------------------===//
1648// Error reporting.
1649//===----------------------------------------------------------------------===//
1650namespace {
1651  typedef llvm::DenseMap<const ExplodedNode *, const RetainSummary *>
1652    SummaryLogTy;
1653
1654  //===-------------===//
1655  // Bug Descriptions. //
1656  //===-------------===//
1657
1658  class CFRefBug : public BugType {
1659  protected:
1660    CFRefBug(const CheckerBase *checker, StringRef name)
1661        : BugType(checker, name, categories::MemoryCoreFoundationObjectiveC) {}
1662
1663  public:
1664
1665    // FIXME: Eventually remove.
1666    virtual const char *getDescription() const = 0;
1667
1668    virtual bool isLeak() const { return false; }
1669  };
1670
1671  class UseAfterRelease : public CFRefBug {
1672  public:
1673    UseAfterRelease(const CheckerBase *checker)
1674        : CFRefBug(checker, "Use-after-release") {}
1675
1676    const char *getDescription() const override {
1677      return "Reference-counted object is used after it is released";
1678    }
1679  };
1680
1681  class BadRelease : public CFRefBug {
1682  public:
1683    BadRelease(const CheckerBase *checker) : CFRefBug(checker, "Bad release") {}
1684
1685    const char *getDescription() const override {
1686      return "Incorrect decrement of the reference count of an object that is "
1687             "not owned at this point by the caller";
1688    }
1689  };
1690
1691  class DeallocGC : public CFRefBug {
1692  public:
1693    DeallocGC(const CheckerBase *checker)
1694        : CFRefBug(checker, "-dealloc called while using garbage collection") {}
1695
1696    const char *getDescription() const override {
1697      return "-dealloc called while using garbage collection";
1698    }
1699  };
1700
1701  class DeallocNotOwned : public CFRefBug {
1702  public:
1703    DeallocNotOwned(const CheckerBase *checker)
1704        : CFRefBug(checker, "-dealloc sent to non-exclusively owned object") {}
1705
1706    const char *getDescription() const override {
1707      return "-dealloc sent to object that may be referenced elsewhere";
1708    }
1709  };
1710
1711  class OverAutorelease : public CFRefBug {
1712  public:
1713    OverAutorelease(const CheckerBase *checker)
1714        : CFRefBug(checker, "Object autoreleased too many times") {}
1715
1716    const char *getDescription() const override {
1717      return "Object autoreleased too many times";
1718    }
1719  };
1720
1721  class ReturnedNotOwnedForOwned : public CFRefBug {
1722  public:
1723    ReturnedNotOwnedForOwned(const CheckerBase *checker)
1724        : CFRefBug(checker, "Method should return an owned object") {}
1725
1726    const char *getDescription() const override {
1727      return "Object with a +0 retain count returned to caller where a +1 "
1728             "(owning) retain count is expected";
1729    }
1730  };
1731
1732  class Leak : public CFRefBug {
1733  public:
1734    Leak(const CheckerBase *checker, StringRef name) : CFRefBug(checker, name) {
1735      // Leaks should not be reported if they are post-dominated by a sink.
1736      setSuppressOnSink(true);
1737    }
1738
1739    const char *getDescription() const override { return ""; }
1740
1741    bool isLeak() const override { return true; }
1742  };
1743
1744  //===---------===//
1745  // Bug Reports.  //
1746  //===---------===//
1747
1748  class CFRefReportVisitor : public BugReporterVisitorImpl<CFRefReportVisitor> {
1749  protected:
1750    SymbolRef Sym;
1751    const SummaryLogTy &SummaryLog;
1752    bool GCEnabled;
1753
1754  public:
1755    CFRefReportVisitor(SymbolRef sym, bool gcEnabled, const SummaryLogTy &log)
1756       : Sym(sym), SummaryLog(log), GCEnabled(gcEnabled) {}
1757
1758    void Profile(llvm::FoldingSetNodeID &ID) const override {
1759      static int x = 0;
1760      ID.AddPointer(&x);
1761      ID.AddPointer(Sym);
1762    }
1763
1764    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
1765                                   const ExplodedNode *PrevN,
1766                                   BugReporterContext &BRC,
1767                                   BugReport &BR) override;
1768
1769    std::unique_ptr<PathDiagnosticPiece> getEndPath(BugReporterContext &BRC,
1770                                                    const ExplodedNode *N,
1771                                                    BugReport &BR) override;
1772  };
1773
1774  class CFRefLeakReportVisitor : public CFRefReportVisitor {
1775  public:
1776    CFRefLeakReportVisitor(SymbolRef sym, bool GCEnabled,
1777                           const SummaryLogTy &log)
1778       : CFRefReportVisitor(sym, GCEnabled, log) {}
1779
1780    std::unique_ptr<PathDiagnosticPiece> getEndPath(BugReporterContext &BRC,
1781                                                    const ExplodedNode *N,
1782                                                    BugReport &BR) override;
1783
1784    std::unique_ptr<BugReporterVisitor> clone() const override {
1785      // The curiously-recurring template pattern only works for one level of
1786      // subclassing. Rather than make a new template base for
1787      // CFRefReportVisitor, we simply override clone() to do the right thing.
1788      // This could be trouble someday if BugReporterVisitorImpl is ever
1789      // used for something else besides a convenient implementation of clone().
1790      return llvm::make_unique<CFRefLeakReportVisitor>(*this);
1791    }
1792  };
1793
1794  class CFRefReport : public BugReport {
1795    void addGCModeDescription(const LangOptions &LOpts, bool GCEnabled);
1796
1797  public:
1798    CFRefReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1799                const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1800                bool registerVisitor = true)
1801      : BugReport(D, D.getDescription(), n) {
1802      if (registerVisitor)
1803        addVisitor(llvm::make_unique<CFRefReportVisitor>(sym, GCEnabled, Log));
1804      addGCModeDescription(LOpts, GCEnabled);
1805    }
1806
1807    CFRefReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1808                const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1809                StringRef endText)
1810      : BugReport(D, D.getDescription(), endText, n) {
1811      addVisitor(llvm::make_unique<CFRefReportVisitor>(sym, GCEnabled, Log));
1812      addGCModeDescription(LOpts, GCEnabled);
1813    }
1814
1815    llvm::iterator_range<ranges_iterator> getRanges() override {
1816      const CFRefBug& BugTy = static_cast<CFRefBug&>(getBugType());
1817      if (!BugTy.isLeak())
1818        return BugReport::getRanges();
1819      return llvm::make_range(ranges_iterator(), ranges_iterator());
1820    }
1821  };
1822
1823  class CFRefLeakReport : public CFRefReport {
1824    const MemRegion* AllocBinding;
1825  public:
1826    CFRefLeakReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1827                    const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1828                    CheckerContext &Ctx,
1829                    bool IncludeAllocationLine);
1830
1831    PathDiagnosticLocation getLocation(const SourceManager &SM) const override {
1832      assert(Location.isValid());
1833      return Location;
1834    }
1835  };
1836} // end anonymous namespace
1837
1838void CFRefReport::addGCModeDescription(const LangOptions &LOpts,
1839                                       bool GCEnabled) {
1840  const char *GCModeDescription = nullptr;
1841
1842  switch (LOpts.getGC()) {
1843  case LangOptions::GCOnly:
1844    assert(GCEnabled);
1845    GCModeDescription = "Code is compiled to only use garbage collection";
1846    break;
1847
1848  case LangOptions::NonGC:
1849    assert(!GCEnabled);
1850    GCModeDescription = "Code is compiled to use reference counts";
1851    break;
1852
1853  case LangOptions::HybridGC:
1854    if (GCEnabled) {
1855      GCModeDescription = "Code is compiled to use either garbage collection "
1856                          "(GC) or reference counts (non-GC).  The bug occurs "
1857                          "with GC enabled";
1858      break;
1859    } else {
1860      GCModeDescription = "Code is compiled to use either garbage collection "
1861                          "(GC) or reference counts (non-GC).  The bug occurs "
1862                          "in non-GC mode";
1863      break;
1864    }
1865  }
1866
1867  assert(GCModeDescription && "invalid/unknown GC mode");
1868  addExtraText(GCModeDescription);
1869}
1870
1871static bool isNumericLiteralExpression(const Expr *E) {
1872  // FIXME: This set of cases was copied from SemaExprObjC.
1873  return isa<IntegerLiteral>(E) ||
1874         isa<CharacterLiteral>(E) ||
1875         isa<FloatingLiteral>(E) ||
1876         isa<ObjCBoolLiteralExpr>(E) ||
1877         isa<CXXBoolLiteralExpr>(E);
1878}
1879
1880/// Returns true if this stack frame is for an Objective-C method that is a
1881/// property getter or setter whose body has been synthesized by the analyzer.
1882static bool isSynthesizedAccessor(const StackFrameContext *SFC) {
1883  auto Method = dyn_cast_or_null<ObjCMethodDecl>(SFC->getDecl());
1884  if (!Method || !Method->isPropertyAccessor())
1885    return false;
1886
1887  return SFC->getAnalysisDeclContext()->isBodyAutosynthesized();
1888}
1889
1890PathDiagnosticPiece *CFRefReportVisitor::VisitNode(const ExplodedNode *N,
1891                                                   const ExplodedNode *PrevN,
1892                                                   BugReporterContext &BRC,
1893                                                   BugReport &BR) {
1894  // FIXME: We will eventually need to handle non-statement-based events
1895  // (__attribute__((cleanup))).
1896  if (!N->getLocation().getAs<StmtPoint>())
1897    return nullptr;
1898
1899  // Check if the type state has changed.
1900  ProgramStateRef PrevSt = PrevN->getState();
1901  ProgramStateRef CurrSt = N->getState();
1902  const LocationContext *LCtx = N->getLocationContext();
1903
1904  const RefVal* CurrT = getRefBinding(CurrSt, Sym);
1905  if (!CurrT) return nullptr;
1906
1907  const RefVal &CurrV = *CurrT;
1908  const RefVal *PrevT = getRefBinding(PrevSt, Sym);
1909
1910  // Create a string buffer to constain all the useful things we want
1911  // to tell the user.
1912  std::string sbuf;
1913  llvm::raw_string_ostream os(sbuf);
1914
1915  // This is the allocation site since the previous node had no bindings
1916  // for this symbol.
1917  if (!PrevT) {
1918    const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
1919
1920    if (isa<ObjCIvarRefExpr>(S) &&
1921        isSynthesizedAccessor(LCtx->getCurrentStackFrame())) {
1922      S = LCtx->getCurrentStackFrame()->getCallSite();
1923    }
1924
1925    if (isa<ObjCArrayLiteral>(S)) {
1926      os << "NSArray literal is an object with a +0 retain count";
1927    }
1928    else if (isa<ObjCDictionaryLiteral>(S)) {
1929      os << "NSDictionary literal is an object with a +0 retain count";
1930    }
1931    else if (const ObjCBoxedExpr *BL = dyn_cast<ObjCBoxedExpr>(S)) {
1932      if (isNumericLiteralExpression(BL->getSubExpr()))
1933        os << "NSNumber literal is an object with a +0 retain count";
1934      else {
1935        const ObjCInterfaceDecl *BoxClass = nullptr;
1936        if (const ObjCMethodDecl *Method = BL->getBoxingMethod())
1937          BoxClass = Method->getClassInterface();
1938
1939        // We should always be able to find the boxing class interface,
1940        // but consider this future-proofing.
1941        if (BoxClass)
1942          os << *BoxClass << " b";
1943        else
1944          os << "B";
1945
1946        os << "oxed expression produces an object with a +0 retain count";
1947      }
1948    }
1949    else if (isa<ObjCIvarRefExpr>(S)) {
1950      os << "Object loaded from instance variable";
1951    }
1952    else {
1953      if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
1954        // Get the name of the callee (if it is available).
1955        SVal X = CurrSt->getSValAsScalarOrLoc(CE->getCallee(), LCtx);
1956        if (const FunctionDecl *FD = X.getAsFunctionDecl())
1957          os << "Call to function '" << *FD << '\'';
1958        else
1959          os << "function call";
1960      }
1961      else {
1962        assert(isa<ObjCMessageExpr>(S));
1963        CallEventManager &Mgr = CurrSt->getStateManager().getCallEventManager();
1964        CallEventRef<ObjCMethodCall> Call
1965          = Mgr.getObjCMethodCall(cast<ObjCMessageExpr>(S), CurrSt, LCtx);
1966
1967        switch (Call->getMessageKind()) {
1968        case OCM_Message:
1969          os << "Method";
1970          break;
1971        case OCM_PropertyAccess:
1972          os << "Property";
1973          break;
1974        case OCM_Subscript:
1975          os << "Subscript";
1976          break;
1977        }
1978      }
1979
1980      if (CurrV.getObjKind() == RetEffect::CF) {
1981        os << " returns a Core Foundation object with a ";
1982      }
1983      else {
1984        assert (CurrV.getObjKind() == RetEffect::ObjC);
1985        os << " returns an Objective-C object with a ";
1986      }
1987
1988      if (CurrV.isOwned()) {
1989        os << "+1 retain count";
1990
1991        if (GCEnabled) {
1992          assert(CurrV.getObjKind() == RetEffect::CF);
1993          os << ".  "
1994          "Core Foundation objects are not automatically garbage collected.";
1995        }
1996      }
1997      else {
1998        assert (CurrV.isNotOwned());
1999        os << "+0 retain count";
2000      }
2001    }
2002
2003    PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
2004                                  N->getLocationContext());
2005    return new PathDiagnosticEventPiece(Pos, os.str());
2006  }
2007
2008  // Gather up the effects that were performed on the object at this
2009  // program point
2010  SmallVector<ArgEffect, 2> AEffects;
2011
2012  const ExplodedNode *OrigNode = BRC.getNodeResolver().getOriginalNode(N);
2013  if (const RetainSummary *Summ = SummaryLog.lookup(OrigNode)) {
2014    // We only have summaries attached to nodes after evaluating CallExpr and
2015    // ObjCMessageExprs.
2016    const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
2017
2018    if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
2019      // Iterate through the parameter expressions and see if the symbol
2020      // was ever passed as an argument.
2021      unsigned i = 0;
2022
2023      for (CallExpr::const_arg_iterator AI=CE->arg_begin(), AE=CE->arg_end();
2024           AI!=AE; ++AI, ++i) {
2025
2026        // Retrieve the value of the argument.  Is it the symbol
2027        // we are interested in?
2028        if (CurrSt->getSValAsScalarOrLoc(*AI, LCtx).getAsLocSymbol() != Sym)
2029          continue;
2030
2031        // We have an argument.  Get the effect!
2032        AEffects.push_back(Summ->getArg(i));
2033      }
2034    }
2035    else if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(S)) {
2036      if (const Expr *receiver = ME->getInstanceReceiver())
2037        if (CurrSt->getSValAsScalarOrLoc(receiver, LCtx)
2038              .getAsLocSymbol() == Sym) {
2039          // The symbol we are tracking is the receiver.
2040          AEffects.push_back(Summ->getReceiverEffect());
2041        }
2042    }
2043  }
2044
2045  do {
2046    // Get the previous type state.
2047    RefVal PrevV = *PrevT;
2048
2049    // Specially handle -dealloc.
2050    if (!GCEnabled && std::find(AEffects.begin(), AEffects.end(), Dealloc) !=
2051                          AEffects.end()) {
2052      // Determine if the object's reference count was pushed to zero.
2053      assert(!PrevV.hasSameState(CurrV) && "The state should have changed.");
2054      // We may not have transitioned to 'release' if we hit an error.
2055      // This case is handled elsewhere.
2056      if (CurrV.getKind() == RefVal::Released) {
2057        assert(CurrV.getCombinedCounts() == 0);
2058        os << "Object released by directly sending the '-dealloc' message";
2059        break;
2060      }
2061    }
2062
2063    // Specially handle CFMakeCollectable and friends.
2064    if (std::find(AEffects.begin(), AEffects.end(), MakeCollectable) !=
2065        AEffects.end()) {
2066      // Get the name of the function.
2067      const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
2068      SVal X =
2069        CurrSt->getSValAsScalarOrLoc(cast<CallExpr>(S)->getCallee(), LCtx);
2070      const FunctionDecl *FD = X.getAsFunctionDecl();
2071
2072      if (GCEnabled) {
2073        // Determine if the object's reference count was pushed to zero.
2074        assert(!PrevV.hasSameState(CurrV) && "The state should have changed.");
2075
2076        os << "In GC mode a call to '" << *FD
2077        <<  "' decrements an object's retain count and registers the "
2078        "object with the garbage collector. ";
2079
2080        if (CurrV.getKind() == RefVal::Released) {
2081          assert(CurrV.getCount() == 0);
2082          os << "Since it now has a 0 retain count the object can be "
2083          "automatically collected by the garbage collector.";
2084        }
2085        else
2086          os << "An object must have a 0 retain count to be garbage collected. "
2087          "After this call its retain count is +" << CurrV.getCount()
2088          << '.';
2089      }
2090      else
2091        os << "When GC is not enabled a call to '" << *FD
2092        << "' has no effect on its argument.";
2093
2094      // Nothing more to say.
2095      break;
2096    }
2097
2098    // Determine if the typestate has changed.
2099    if (!PrevV.hasSameState(CurrV))
2100      switch (CurrV.getKind()) {
2101        case RefVal::Owned:
2102        case RefVal::NotOwned:
2103          if (PrevV.getCount() == CurrV.getCount()) {
2104            // Did an autorelease message get sent?
2105            if (PrevV.getAutoreleaseCount() == CurrV.getAutoreleaseCount())
2106              return nullptr;
2107
2108            assert(PrevV.getAutoreleaseCount() < CurrV.getAutoreleaseCount());
2109            os << "Object autoreleased";
2110            break;
2111          }
2112
2113          if (PrevV.getCount() > CurrV.getCount())
2114            os << "Reference count decremented.";
2115          else
2116            os << "Reference count incremented.";
2117
2118          if (unsigned Count = CurrV.getCount())
2119            os << " The object now has a +" << Count << " retain count.";
2120
2121          if (PrevV.getKind() == RefVal::Released) {
2122            assert(GCEnabled && CurrV.getCount() > 0);
2123            os << " The object is not eligible for garbage collection until "
2124                  "the retain count reaches 0 again.";
2125          }
2126
2127          break;
2128
2129        case RefVal::Released:
2130          if (CurrV.getIvarAccessHistory() ==
2131                RefVal::IvarAccessHistory::ReleasedAfterDirectAccess &&
2132              CurrV.getIvarAccessHistory() != PrevV.getIvarAccessHistory()) {
2133            os << "Strong instance variable relinquished. ";
2134          }
2135          os << "Object released.";
2136          break;
2137
2138        case RefVal::ReturnedOwned:
2139          // Autoreleases can be applied after marking a node ReturnedOwned.
2140          if (CurrV.getAutoreleaseCount())
2141            return nullptr;
2142
2143          os << "Object returned to caller as an owning reference (single "
2144                "retain count transferred to caller)";
2145          break;
2146
2147        case RefVal::ReturnedNotOwned:
2148          os << "Object returned to caller with a +0 retain count";
2149          break;
2150
2151        default:
2152          return nullptr;
2153      }
2154
2155    // Emit any remaining diagnostics for the argument effects (if any).
2156    for (SmallVectorImpl<ArgEffect>::iterator I=AEffects.begin(),
2157         E=AEffects.end(); I != E; ++I) {
2158
2159      // A bunch of things have alternate behavior under GC.
2160      if (GCEnabled)
2161        switch (*I) {
2162          default: break;
2163          case Autorelease:
2164            os << "In GC mode an 'autorelease' has no effect.";
2165            continue;
2166          case IncRefMsg:
2167            os << "In GC mode the 'retain' message has no effect.";
2168            continue;
2169          case DecRefMsg:
2170            os << "In GC mode the 'release' message has no effect.";
2171            continue;
2172        }
2173    }
2174  } while (0);
2175
2176  if (os.str().empty())
2177    return nullptr; // We have nothing to say!
2178
2179  const Stmt *S = N->getLocation().castAs<StmtPoint>().getStmt();
2180  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
2181                                N->getLocationContext());
2182  PathDiagnosticPiece *P = new PathDiagnosticEventPiece(Pos, os.str());
2183
2184  // Add the range by scanning the children of the statement for any bindings
2185  // to Sym.
2186  for (const Stmt *Child : S->children())
2187    if (const Expr *Exp = dyn_cast_or_null<Expr>(Child))
2188      if (CurrSt->getSValAsScalarOrLoc(Exp, LCtx).getAsLocSymbol() == Sym) {
2189        P->addRange(Exp->getSourceRange());
2190        break;
2191      }
2192
2193  return P;
2194}
2195
2196namespace {
2197// Find the first node in the current function context that referred to the
2198// tracked symbol and the memory location that value was stored to. Note, the
2199// value is only reported if the allocation occurred in the same function as
2200// the leak. The function can also return a location context, which should be
2201// treated as interesting.
2202struct AllocationInfo {
2203  const ExplodedNode* N;
2204  const MemRegion *R;
2205  const LocationContext *InterestingMethodContext;
2206  AllocationInfo(const ExplodedNode *InN,
2207                 const MemRegion *InR,
2208                 const LocationContext *InInterestingMethodContext) :
2209    N(InN), R(InR), InterestingMethodContext(InInterestingMethodContext) {}
2210};
2211} // end anonymous namespace
2212
2213static AllocationInfo
2214GetAllocationSite(ProgramStateManager& StateMgr, const ExplodedNode *N,
2215                  SymbolRef Sym) {
2216  const ExplodedNode *AllocationNode = N;
2217  const ExplodedNode *AllocationNodeInCurrentOrParentContext = N;
2218  const MemRegion *FirstBinding = nullptr;
2219  const LocationContext *LeakContext = N->getLocationContext();
2220
2221  // The location context of the init method called on the leaked object, if
2222  // available.
2223  const LocationContext *InitMethodContext = nullptr;
2224
2225  while (N) {
2226    ProgramStateRef St = N->getState();
2227    const LocationContext *NContext = N->getLocationContext();
2228
2229    if (!getRefBinding(St, Sym))
2230      break;
2231
2232    StoreManager::FindUniqueBinding FB(Sym);
2233    StateMgr.iterBindings(St, FB);
2234
2235    if (FB) {
2236      const MemRegion *R = FB.getRegion();
2237      const VarRegion *VR = R->getBaseRegion()->getAs<VarRegion>();
2238      // Do not show local variables belonging to a function other than
2239      // where the error is reported.
2240      if (!VR || VR->getStackFrame() == LeakContext->getCurrentStackFrame())
2241        FirstBinding = R;
2242    }
2243
2244    // AllocationNode is the last node in which the symbol was tracked.
2245    AllocationNode = N;
2246
2247    // AllocationNodeInCurrentContext, is the last node in the current or
2248    // parent context in which the symbol was tracked.
2249    //
2250    // Note that the allocation site might be in the parent conext. For example,
2251    // the case where an allocation happens in a block that captures a reference
2252    // to it and that reference is overwritten/dropped by another call to
2253    // the block.
2254    if (NContext == LeakContext || NContext->isParentOf(LeakContext))
2255      AllocationNodeInCurrentOrParentContext = N;
2256
2257    // Find the last init that was called on the given symbol and store the
2258    // init method's location context.
2259    if (!InitMethodContext)
2260      if (Optional<CallEnter> CEP = N->getLocation().getAs<CallEnter>()) {
2261        const Stmt *CE = CEP->getCallExpr();
2262        if (const ObjCMessageExpr *ME = dyn_cast_or_null<ObjCMessageExpr>(CE)) {
2263          const Stmt *RecExpr = ME->getInstanceReceiver();
2264          if (RecExpr) {
2265            SVal RecV = St->getSVal(RecExpr, NContext);
2266            if (ME->getMethodFamily() == OMF_init && RecV.getAsSymbol() == Sym)
2267              InitMethodContext = CEP->getCalleeContext();
2268          }
2269        }
2270      }
2271
2272    N = N->pred_empty() ? nullptr : *(N->pred_begin());
2273  }
2274
2275  // If we are reporting a leak of the object that was allocated with alloc,
2276  // mark its init method as interesting.
2277  const LocationContext *InterestingMethodContext = nullptr;
2278  if (InitMethodContext) {
2279    const ProgramPoint AllocPP = AllocationNode->getLocation();
2280    if (Optional<StmtPoint> SP = AllocPP.getAs<StmtPoint>())
2281      if (const ObjCMessageExpr *ME = SP->getStmtAs<ObjCMessageExpr>())
2282        if (ME->getMethodFamily() == OMF_alloc)
2283          InterestingMethodContext = InitMethodContext;
2284  }
2285
2286  // If allocation happened in a function different from the leak node context,
2287  // do not report the binding.
2288  assert(N && "Could not find allocation node");
2289  if (N->getLocationContext() != LeakContext) {
2290    FirstBinding = nullptr;
2291  }
2292
2293  return AllocationInfo(AllocationNodeInCurrentOrParentContext,
2294                        FirstBinding,
2295                        InterestingMethodContext);
2296}
2297
2298std::unique_ptr<PathDiagnosticPiece>
2299CFRefReportVisitor::getEndPath(BugReporterContext &BRC,
2300                               const ExplodedNode *EndN, BugReport &BR) {
2301  BR.markInteresting(Sym);
2302  return BugReporterVisitor::getDefaultEndPath(BRC, EndN, BR);
2303}
2304
2305std::unique_ptr<PathDiagnosticPiece>
2306CFRefLeakReportVisitor::getEndPath(BugReporterContext &BRC,
2307                                   const ExplodedNode *EndN, BugReport &BR) {
2308
2309  // Tell the BugReporterContext to report cases when the tracked symbol is
2310  // assigned to different variables, etc.
2311  BR.markInteresting(Sym);
2312
2313  // We are reporting a leak.  Walk up the graph to get to the first node where
2314  // the symbol appeared, and also get the first VarDecl that tracked object
2315  // is stored to.
2316  AllocationInfo AllocI =
2317    GetAllocationSite(BRC.getStateManager(), EndN, Sym);
2318
2319  const MemRegion* FirstBinding = AllocI.R;
2320  BR.markInteresting(AllocI.InterestingMethodContext);
2321
2322  SourceManager& SM = BRC.getSourceManager();
2323
2324  // Compute an actual location for the leak.  Sometimes a leak doesn't
2325  // occur at an actual statement (e.g., transition between blocks; end
2326  // of function) so we need to walk the graph and compute a real location.
2327  const ExplodedNode *LeakN = EndN;
2328  PathDiagnosticLocation L = PathDiagnosticLocation::createEndOfPath(LeakN, SM);
2329
2330  std::string sbuf;
2331  llvm::raw_string_ostream os(sbuf);
2332
2333  os << "Object leaked: ";
2334
2335  if (FirstBinding) {
2336    os << "object allocated and stored into '"
2337       << FirstBinding->getString() << '\'';
2338  }
2339  else
2340    os << "allocated object";
2341
2342  // Get the retain count.
2343  const RefVal* RV = getRefBinding(EndN->getState(), Sym);
2344  assert(RV);
2345
2346  if (RV->getKind() == RefVal::ErrorLeakReturned) {
2347    // FIXME: Per comments in rdar://6320065, "create" only applies to CF
2348    // objects.  Only "copy", "alloc", "retain" and "new" transfer ownership
2349    // to the caller for NS objects.
2350    const Decl *D = &EndN->getCodeDecl();
2351
2352    os << (isa<ObjCMethodDecl>(D) ? " is returned from a method "
2353                                  : " is returned from a function ");
2354
2355    if (D->hasAttr<CFReturnsNotRetainedAttr>())
2356      os << "that is annotated as CF_RETURNS_NOT_RETAINED";
2357    else if (D->hasAttr<NSReturnsNotRetainedAttr>())
2358      os << "that is annotated as NS_RETURNS_NOT_RETAINED";
2359    else {
2360      if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
2361        os << "whose name ('" << MD->getSelector().getAsString()
2362           << "') does not start with 'copy', 'mutableCopy', 'alloc' or 'new'."
2363              "  This violates the naming convention rules"
2364              " given in the Memory Management Guide for Cocoa";
2365      }
2366      else {
2367        const FunctionDecl *FD = cast<FunctionDecl>(D);
2368        os << "whose name ('" << *FD
2369           << "') does not contain 'Copy' or 'Create'.  This violates the naming"
2370              " convention rules given in the Memory Management Guide for Core"
2371              " Foundation";
2372      }
2373    }
2374  }
2375  else if (RV->getKind() == RefVal::ErrorGCLeakReturned) {
2376    const ObjCMethodDecl &MD = cast<ObjCMethodDecl>(EndN->getCodeDecl());
2377    os << " and returned from method '" << MD.getSelector().getAsString()
2378       << "' is potentially leaked when using garbage collection.  Callers "
2379          "of this method do not expect a returned object with a +1 retain "
2380          "count since they expect the object to be managed by the garbage "
2381          "collector";
2382  }
2383  else
2384    os << " is not referenced later in this execution path and has a retain "
2385          "count of +" << RV->getCount();
2386
2387  return llvm::make_unique<PathDiagnosticEventPiece>(L, os.str());
2388}
2389
2390CFRefLeakReport::CFRefLeakReport(CFRefBug &D, const LangOptions &LOpts,
2391                                 bool GCEnabled, const SummaryLogTy &Log,
2392                                 ExplodedNode *n, SymbolRef sym,
2393                                 CheckerContext &Ctx,
2394                                 bool IncludeAllocationLine)
2395  : CFRefReport(D, LOpts, GCEnabled, Log, n, sym, false) {
2396
2397  // Most bug reports are cached at the location where they occurred.
2398  // With leaks, we want to unique them by the location where they were
2399  // allocated, and only report a single path.  To do this, we need to find
2400  // the allocation site of a piece of tracked memory, which we do via a
2401  // call to GetAllocationSite.  This will walk the ExplodedGraph backwards.
2402  // Note that this is *not* the trimmed graph; we are guaranteed, however,
2403  // that all ancestor nodes that represent the allocation site have the
2404  // same SourceLocation.
2405  const ExplodedNode *AllocNode = nullptr;
2406
2407  const SourceManager& SMgr = Ctx.getSourceManager();
2408
2409  AllocationInfo AllocI =
2410    GetAllocationSite(Ctx.getStateManager(), getErrorNode(), sym);
2411
2412  AllocNode = AllocI.N;
2413  AllocBinding = AllocI.R;
2414  markInteresting(AllocI.InterestingMethodContext);
2415
2416  // Get the SourceLocation for the allocation site.
2417  // FIXME: This will crash the analyzer if an allocation comes from an
2418  // implicit call (ex: a destructor call).
2419  // (Currently there are no such allocations in Cocoa, though.)
2420  const Stmt *AllocStmt = nullptr;
2421  ProgramPoint P = AllocNode->getLocation();
2422  if (Optional<CallExitEnd> Exit = P.getAs<CallExitEnd>())
2423    AllocStmt = Exit->getCalleeContext()->getCallSite();
2424  else
2425    AllocStmt = P.castAs<PostStmt>().getStmt();
2426  assert(AllocStmt && "Cannot find allocation statement");
2427
2428  PathDiagnosticLocation AllocLocation =
2429    PathDiagnosticLocation::createBegin(AllocStmt, SMgr,
2430                                        AllocNode->getLocationContext());
2431  Location = AllocLocation;
2432
2433  // Set uniqieing info, which will be used for unique the bug reports. The
2434  // leaks should be uniqued on the allocation site.
2435  UniqueingLocation = AllocLocation;
2436  UniqueingDecl = AllocNode->getLocationContext()->getDecl();
2437
2438  // Fill in the description of the bug.
2439  Description.clear();
2440  llvm::raw_string_ostream os(Description);
2441  os << "Potential leak ";
2442  if (GCEnabled)
2443    os << "(when using garbage collection) ";
2444  os << "of an object";
2445
2446  if (AllocBinding) {
2447    os << " stored into '" << AllocBinding->getString() << '\'';
2448    if (IncludeAllocationLine) {
2449      FullSourceLoc SL(AllocStmt->getLocStart(), Ctx.getSourceManager());
2450      os << " (allocated on line " << SL.getSpellingLineNumber() << ")";
2451    }
2452  }
2453
2454  addVisitor(llvm::make_unique<CFRefLeakReportVisitor>(sym, GCEnabled, Log));
2455}
2456
2457//===----------------------------------------------------------------------===//
2458// Main checker logic.
2459//===----------------------------------------------------------------------===//
2460
2461namespace {
2462class RetainCountChecker
2463  : public Checker< check::Bind,
2464                    check::DeadSymbols,
2465                    check::EndAnalysis,
2466                    check::EndFunction,
2467                    check::PostStmt<BlockExpr>,
2468                    check::PostStmt<CastExpr>,
2469                    check::PostStmt<ObjCArrayLiteral>,
2470                    check::PostStmt<ObjCDictionaryLiteral>,
2471                    check::PostStmt<ObjCBoxedExpr>,
2472                    check::PostStmt<ObjCIvarRefExpr>,
2473                    check::PostCall,
2474                    check::PreStmt<ReturnStmt>,
2475                    check::RegionChanges,
2476                    eval::Assume,
2477                    eval::Call > {
2478  mutable std::unique_ptr<CFRefBug> useAfterRelease, releaseNotOwned;
2479  mutable std::unique_ptr<CFRefBug> deallocGC, deallocNotOwned;
2480  mutable std::unique_ptr<CFRefBug> overAutorelease, returnNotOwnedForOwned;
2481  mutable std::unique_ptr<CFRefBug> leakWithinFunction, leakAtReturn;
2482  mutable std::unique_ptr<CFRefBug> leakWithinFunctionGC, leakAtReturnGC;
2483
2484  typedef llvm::DenseMap<SymbolRef, const CheckerProgramPointTag *> SymbolTagMap;
2485
2486  // This map is only used to ensure proper deletion of any allocated tags.
2487  mutable SymbolTagMap DeadSymbolTags;
2488
2489  mutable std::unique_ptr<RetainSummaryManager> Summaries;
2490  mutable std::unique_ptr<RetainSummaryManager> SummariesGC;
2491  mutable SummaryLogTy SummaryLog;
2492  mutable bool ShouldResetSummaryLog;
2493
2494  /// Optional setting to indicate if leak reports should include
2495  /// the allocation line.
2496  mutable bool IncludeAllocationLine;
2497
2498public:
2499  RetainCountChecker(AnalyzerOptions &AO)
2500    : ShouldResetSummaryLog(false),
2501      IncludeAllocationLine(shouldIncludeAllocationSiteInLeakDiagnostics(AO)) {}
2502
2503  ~RetainCountChecker() override { DeleteContainerSeconds(DeadSymbolTags); }
2504
2505  void checkEndAnalysis(ExplodedGraph &G, BugReporter &BR,
2506                        ExprEngine &Eng) const {
2507    // FIXME: This is a hack to make sure the summary log gets cleared between
2508    // analyses of different code bodies.
2509    //
2510    // Why is this necessary? Because a checker's lifetime is tied to a
2511    // translation unit, but an ExplodedGraph's lifetime is just a code body.
2512    // Once in a blue moon, a new ExplodedNode will have the same address as an
2513    // old one with an associated summary, and the bug report visitor gets very
2514    // confused. (To make things worse, the summary lifetime is currently also
2515    // tied to a code body, so we get a crash instead of incorrect results.)
2516    //
2517    // Why is this a bad solution? Because if the lifetime of the ExplodedGraph
2518    // changes, things will start going wrong again. Really the lifetime of this
2519    // log needs to be tied to either the specific nodes in it or the entire
2520    // ExplodedGraph, not to a specific part of the code being analyzed.
2521    //
2522    // (Also, having stateful local data means that the same checker can't be
2523    // used from multiple threads, but a lot of checkers have incorrect
2524    // assumptions about that anyway. So that wasn't a priority at the time of
2525    // this fix.)
2526    //
2527    // This happens at the end of analysis, but bug reports are emitted /after/
2528    // this point. So we can't just clear the summary log now. Instead, we mark
2529    // that the next time we access the summary log, it should be cleared.
2530
2531    // If we never reset the summary log during /this/ code body analysis,
2532    // there were no new summaries. There might still have been summaries from
2533    // the /last/ analysis, so clear them out to make sure the bug report
2534    // visitors don't get confused.
2535    if (ShouldResetSummaryLog)
2536      SummaryLog.clear();
2537
2538    ShouldResetSummaryLog = !SummaryLog.empty();
2539  }
2540
2541  CFRefBug *getLeakWithinFunctionBug(const LangOptions &LOpts,
2542                                     bool GCEnabled) const {
2543    if (GCEnabled) {
2544      if (!leakWithinFunctionGC)
2545        leakWithinFunctionGC.reset(new Leak(this, "Leak of object when using "
2546                                                  "garbage collection"));
2547      return leakWithinFunctionGC.get();
2548    } else {
2549      if (!leakWithinFunction) {
2550        if (LOpts.getGC() == LangOptions::HybridGC) {
2551          leakWithinFunction.reset(new Leak(this,
2552                                            "Leak of object when not using "
2553                                            "garbage collection (GC) in "
2554                                            "dual GC/non-GC code"));
2555        } else {
2556          leakWithinFunction.reset(new Leak(this, "Leak"));
2557        }
2558      }
2559      return leakWithinFunction.get();
2560    }
2561  }
2562
2563  CFRefBug *getLeakAtReturnBug(const LangOptions &LOpts, bool GCEnabled) const {
2564    if (GCEnabled) {
2565      if (!leakAtReturnGC)
2566        leakAtReturnGC.reset(new Leak(this,
2567                                      "Leak of returned object when using "
2568                                      "garbage collection"));
2569      return leakAtReturnGC.get();
2570    } else {
2571      if (!leakAtReturn) {
2572        if (LOpts.getGC() == LangOptions::HybridGC) {
2573          leakAtReturn.reset(new Leak(this,
2574                                      "Leak of returned object when not using "
2575                                      "garbage collection (GC) in dual "
2576                                      "GC/non-GC code"));
2577        } else {
2578          leakAtReturn.reset(new Leak(this, "Leak of returned object"));
2579        }
2580      }
2581      return leakAtReturn.get();
2582    }
2583  }
2584
2585  RetainSummaryManager &getSummaryManager(ASTContext &Ctx,
2586                                          bool GCEnabled) const {
2587    // FIXME: We don't support ARC being turned on and off during one analysis.
2588    // (nor, for that matter, do we support changing ASTContexts)
2589    bool ARCEnabled = (bool)Ctx.getLangOpts().ObjCAutoRefCount;
2590    if (GCEnabled) {
2591      if (!SummariesGC)
2592        SummariesGC.reset(new RetainSummaryManager(Ctx, true, ARCEnabled));
2593      else
2594        assert(SummariesGC->isARCEnabled() == ARCEnabled);
2595      return *SummariesGC;
2596    } else {
2597      if (!Summaries)
2598        Summaries.reset(new RetainSummaryManager(Ctx, false, ARCEnabled));
2599      else
2600        assert(Summaries->isARCEnabled() == ARCEnabled);
2601      return *Summaries;
2602    }
2603  }
2604
2605  RetainSummaryManager &getSummaryManager(CheckerContext &C) const {
2606    return getSummaryManager(C.getASTContext(), C.isObjCGCEnabled());
2607  }
2608
2609  void printState(raw_ostream &Out, ProgramStateRef State,
2610                  const char *NL, const char *Sep) const override;
2611
2612  void checkBind(SVal loc, SVal val, const Stmt *S, CheckerContext &C) const;
2613  void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
2614  void checkPostStmt(const CastExpr *CE, CheckerContext &C) const;
2615
2616  void checkPostStmt(const ObjCArrayLiteral *AL, CheckerContext &C) const;
2617  void checkPostStmt(const ObjCDictionaryLiteral *DL, CheckerContext &C) const;
2618  void checkPostStmt(const ObjCBoxedExpr *BE, CheckerContext &C) const;
2619
2620  void checkPostStmt(const ObjCIvarRefExpr *IRE, CheckerContext &C) const;
2621
2622  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
2623
2624  void checkSummary(const RetainSummary &Summ, const CallEvent &Call,
2625                    CheckerContext &C) const;
2626
2627  void processSummaryOfInlined(const RetainSummary &Summ,
2628                               const CallEvent &Call,
2629                               CheckerContext &C) const;
2630
2631  bool evalCall(const CallExpr *CE, CheckerContext &C) const;
2632
2633  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
2634                                 bool Assumption) const;
2635
2636  ProgramStateRef
2637  checkRegionChanges(ProgramStateRef state,
2638                     const InvalidatedSymbols *invalidated,
2639                     ArrayRef<const MemRegion *> ExplicitRegions,
2640                     ArrayRef<const MemRegion *> Regions,
2641                     const CallEvent *Call) const;
2642
2643  bool wantsRegionChangeUpdate(ProgramStateRef state) const {
2644    return true;
2645  }
2646
2647  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
2648  void checkReturnWithRetEffect(const ReturnStmt *S, CheckerContext &C,
2649                                ExplodedNode *Pred, RetEffect RE, RefVal X,
2650                                SymbolRef Sym, ProgramStateRef state) const;
2651
2652  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
2653  void checkEndFunction(CheckerContext &C) const;
2654
2655  ProgramStateRef updateSymbol(ProgramStateRef state, SymbolRef sym,
2656                               RefVal V, ArgEffect E, RefVal::Kind &hasErr,
2657                               CheckerContext &C) const;
2658
2659  void processNonLeakError(ProgramStateRef St, SourceRange ErrorRange,
2660                           RefVal::Kind ErrorKind, SymbolRef Sym,
2661                           CheckerContext &C) const;
2662
2663  void processObjCLiterals(CheckerContext &C, const Expr *Ex) const;
2664
2665  const ProgramPointTag *getDeadSymbolTag(SymbolRef sym) const;
2666
2667  ProgramStateRef handleSymbolDeath(ProgramStateRef state,
2668                                    SymbolRef sid, RefVal V,
2669                                    SmallVectorImpl<SymbolRef> &Leaked) const;
2670
2671  ProgramStateRef
2672  handleAutoreleaseCounts(ProgramStateRef state, ExplodedNode *Pred,
2673                          const ProgramPointTag *Tag, CheckerContext &Ctx,
2674                          SymbolRef Sym, RefVal V) const;
2675
2676  ExplodedNode *processLeaks(ProgramStateRef state,
2677                             SmallVectorImpl<SymbolRef> &Leaked,
2678                             CheckerContext &Ctx,
2679                             ExplodedNode *Pred = nullptr) const;
2680};
2681} // end anonymous namespace
2682
2683namespace {
2684class StopTrackingCallback final : public SymbolVisitor {
2685  ProgramStateRef state;
2686public:
2687  StopTrackingCallback(ProgramStateRef st) : state(std::move(st)) {}
2688  ProgramStateRef getState() const { return state; }
2689
2690  bool VisitSymbol(SymbolRef sym) override {
2691    state = state->remove<RefBindings>(sym);
2692    return true;
2693  }
2694};
2695} // end anonymous namespace
2696
2697//===----------------------------------------------------------------------===//
2698// Handle statements that may have an effect on refcounts.
2699//===----------------------------------------------------------------------===//
2700
2701void RetainCountChecker::checkPostStmt(const BlockExpr *BE,
2702                                       CheckerContext &C) const {
2703
2704  // Scan the BlockDecRefExprs for any object the retain count checker
2705  // may be tracking.
2706  if (!BE->getBlockDecl()->hasCaptures())
2707    return;
2708
2709  ProgramStateRef state = C.getState();
2710  const BlockDataRegion *R =
2711    cast<BlockDataRegion>(state->getSVal(BE,
2712                                         C.getLocationContext()).getAsRegion());
2713
2714  BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
2715                                            E = R->referenced_vars_end();
2716
2717  if (I == E)
2718    return;
2719
2720  // FIXME: For now we invalidate the tracking of all symbols passed to blocks
2721  // via captured variables, even though captured variables result in a copy
2722  // and in implicit increment/decrement of a retain count.
2723  SmallVector<const MemRegion*, 10> Regions;
2724  const LocationContext *LC = C.getLocationContext();
2725  MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
2726
2727  for ( ; I != E; ++I) {
2728    const VarRegion *VR = I.getCapturedRegion();
2729    if (VR->getSuperRegion() == R) {
2730      VR = MemMgr.getVarRegion(VR->getDecl(), LC);
2731    }
2732    Regions.push_back(VR);
2733  }
2734
2735  state =
2736    state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
2737                                    Regions.data() + Regions.size()).getState();
2738  C.addTransition(state);
2739}
2740
2741void RetainCountChecker::checkPostStmt(const CastExpr *CE,
2742                                       CheckerContext &C) const {
2743  const ObjCBridgedCastExpr *BE = dyn_cast<ObjCBridgedCastExpr>(CE);
2744  if (!BE)
2745    return;
2746
2747  ArgEffect AE = IncRef;
2748
2749  switch (BE->getBridgeKind()) {
2750    case clang::OBC_Bridge:
2751      // Do nothing.
2752      return;
2753    case clang::OBC_BridgeRetained:
2754      AE = IncRef;
2755      break;
2756    case clang::OBC_BridgeTransfer:
2757      AE = DecRefBridgedTransferred;
2758      break;
2759  }
2760
2761  ProgramStateRef state = C.getState();
2762  SymbolRef Sym = state->getSVal(CE, C.getLocationContext()).getAsLocSymbol();
2763  if (!Sym)
2764    return;
2765  const RefVal* T = getRefBinding(state, Sym);
2766  if (!T)
2767    return;
2768
2769  RefVal::Kind hasErr = (RefVal::Kind) 0;
2770  state = updateSymbol(state, Sym, *T, AE, hasErr, C);
2771
2772  if (hasErr) {
2773    // FIXME: If we get an error during a bridge cast, should we report it?
2774    return;
2775  }
2776
2777  C.addTransition(state);
2778}
2779
2780void RetainCountChecker::processObjCLiterals(CheckerContext &C,
2781                                             const Expr *Ex) const {
2782  ProgramStateRef state = C.getState();
2783  const ExplodedNode *pred = C.getPredecessor();
2784  for (const Stmt *Child : Ex->children()) {
2785    SVal V = state->getSVal(Child, pred->getLocationContext());
2786    if (SymbolRef sym = V.getAsSymbol())
2787      if (const RefVal* T = getRefBinding(state, sym)) {
2788        RefVal::Kind hasErr = (RefVal::Kind) 0;
2789        state = updateSymbol(state, sym, *T, MayEscape, hasErr, C);
2790        if (hasErr) {
2791          processNonLeakError(state, Child->getSourceRange(), hasErr, sym, C);
2792          return;
2793        }
2794      }
2795  }
2796
2797  // Return the object as autoreleased.
2798  //  RetEffect RE = RetEffect::MakeNotOwned(RetEffect::ObjC);
2799  if (SymbolRef sym =
2800        state->getSVal(Ex, pred->getLocationContext()).getAsSymbol()) {
2801    QualType ResultTy = Ex->getType();
2802    state = setRefBinding(state, sym,
2803                          RefVal::makeNotOwned(RetEffect::ObjC, ResultTy));
2804  }
2805
2806  C.addTransition(state);
2807}
2808
2809void RetainCountChecker::checkPostStmt(const ObjCArrayLiteral *AL,
2810                                       CheckerContext &C) const {
2811  // Apply the 'MayEscape' to all values.
2812  processObjCLiterals(C, AL);
2813}
2814
2815void RetainCountChecker::checkPostStmt(const ObjCDictionaryLiteral *DL,
2816                                       CheckerContext &C) const {
2817  // Apply the 'MayEscape' to all keys and values.
2818  processObjCLiterals(C, DL);
2819}
2820
2821void RetainCountChecker::checkPostStmt(const ObjCBoxedExpr *Ex,
2822                                       CheckerContext &C) const {
2823  const ExplodedNode *Pred = C.getPredecessor();
2824  const LocationContext *LCtx = Pred->getLocationContext();
2825  ProgramStateRef State = Pred->getState();
2826
2827  if (SymbolRef Sym = State->getSVal(Ex, LCtx).getAsSymbol()) {
2828    QualType ResultTy = Ex->getType();
2829    State = setRefBinding(State, Sym,
2830                          RefVal::makeNotOwned(RetEffect::ObjC, ResultTy));
2831  }
2832
2833  C.addTransition(State);
2834}
2835
2836void RetainCountChecker::checkPostStmt(const ObjCIvarRefExpr *IRE,
2837                                       CheckerContext &C) const {
2838  Optional<Loc> IVarLoc = C.getSVal(IRE).getAs<Loc>();
2839  if (!IVarLoc)
2840    return;
2841
2842  ProgramStateRef State = C.getState();
2843  SymbolRef Sym = State->getSVal(*IVarLoc).getAsSymbol();
2844  if (!Sym || !dyn_cast_or_null<ObjCIvarRegion>(Sym->getOriginRegion()))
2845    return;
2846
2847  // Accessing an ivar directly is unusual. If we've done that, be more
2848  // forgiving about what the surrounding code is allowed to do.
2849
2850  QualType Ty = Sym->getType();
2851  RetEffect::ObjKind Kind;
2852  if (Ty->isObjCRetainableType())
2853    Kind = RetEffect::ObjC;
2854  else if (coreFoundation::isCFObjectRef(Ty))
2855    Kind = RetEffect::CF;
2856  else
2857    return;
2858
2859  // If the value is already known to be nil, don't bother tracking it.
2860  ConstraintManager &CMgr = State->getConstraintManager();
2861  if (CMgr.isNull(State, Sym).isConstrainedTrue())
2862    return;
2863
2864  if (const RefVal *RV = getRefBinding(State, Sym)) {
2865    // If we've seen this symbol before, or we're only seeing it now because
2866    // of something the analyzer has synthesized, don't do anything.
2867    if (RV->getIvarAccessHistory() != RefVal::IvarAccessHistory::None ||
2868        isSynthesizedAccessor(C.getStackFrame())) {
2869      return;
2870    }
2871
2872    // Note that this value has been loaded from an ivar.
2873    C.addTransition(setRefBinding(State, Sym, RV->withIvarAccess()));
2874    return;
2875  }
2876
2877  RefVal PlusZero = RefVal::makeNotOwned(Kind, Ty);
2878
2879  // In a synthesized accessor, the effective retain count is +0.
2880  if (isSynthesizedAccessor(C.getStackFrame())) {
2881    C.addTransition(setRefBinding(State, Sym, PlusZero));
2882    return;
2883  }
2884
2885  State = setRefBinding(State, Sym, PlusZero.withIvarAccess());
2886  C.addTransition(State);
2887}
2888
2889void RetainCountChecker::checkPostCall(const CallEvent &Call,
2890                                       CheckerContext &C) const {
2891  RetainSummaryManager &Summaries = getSummaryManager(C);
2892  const RetainSummary *Summ = Summaries.getSummary(Call, C.getState());
2893
2894  if (C.wasInlined) {
2895    processSummaryOfInlined(*Summ, Call, C);
2896    return;
2897  }
2898  checkSummary(*Summ, Call, C);
2899}
2900
2901/// GetReturnType - Used to get the return type of a message expression or
2902///  function call with the intention of affixing that type to a tracked symbol.
2903///  While the return type can be queried directly from RetEx, when
2904///  invoking class methods we augment to the return type to be that of
2905///  a pointer to the class (as opposed it just being id).
2906// FIXME: We may be able to do this with related result types instead.
2907// This function is probably overestimating.
2908static QualType GetReturnType(const Expr *RetE, ASTContext &Ctx) {
2909  QualType RetTy = RetE->getType();
2910  // If RetE is not a message expression just return its type.
2911  // If RetE is a message expression, return its types if it is something
2912  /// more specific than id.
2913  if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(RetE))
2914    if (const ObjCObjectPointerType *PT = RetTy->getAs<ObjCObjectPointerType>())
2915      if (PT->isObjCQualifiedIdType() || PT->isObjCIdType() ||
2916          PT->isObjCClassType()) {
2917        // At this point we know the return type of the message expression is
2918        // id, id<...>, or Class. If we have an ObjCInterfaceDecl, we know this
2919        // is a call to a class method whose type we can resolve.  In such
2920        // cases, promote the return type to XXX* (where XXX is the class).
2921        const ObjCInterfaceDecl *D = ME->getReceiverInterface();
2922        return !D ? RetTy :
2923                    Ctx.getObjCObjectPointerType(Ctx.getObjCInterfaceType(D));
2924      }
2925
2926  return RetTy;
2927}
2928
2929// We don't always get the exact modeling of the function with regards to the
2930// retain count checker even when the function is inlined. For example, we need
2931// to stop tracking the symbols which were marked with StopTrackingHard.
2932void RetainCountChecker::processSummaryOfInlined(const RetainSummary &Summ,
2933                                                 const CallEvent &CallOrMsg,
2934                                                 CheckerContext &C) const {
2935  ProgramStateRef state = C.getState();
2936
2937  // Evaluate the effect of the arguments.
2938  for (unsigned idx = 0, e = CallOrMsg.getNumArgs(); idx != e; ++idx) {
2939    if (Summ.getArg(idx) == StopTrackingHard) {
2940      SVal V = CallOrMsg.getArgSVal(idx);
2941      if (SymbolRef Sym = V.getAsLocSymbol()) {
2942        state = removeRefBinding(state, Sym);
2943      }
2944    }
2945  }
2946
2947  // Evaluate the effect on the message receiver.
2948  const ObjCMethodCall *MsgInvocation = dyn_cast<ObjCMethodCall>(&CallOrMsg);
2949  if (MsgInvocation) {
2950    if (SymbolRef Sym = MsgInvocation->getReceiverSVal().getAsLocSymbol()) {
2951      if (Summ.getReceiverEffect() == StopTrackingHard) {
2952        state = removeRefBinding(state, Sym);
2953      }
2954    }
2955  }
2956
2957  // Consult the summary for the return value.
2958  RetEffect RE = Summ.getRetEffect();
2959  if (RE.getKind() == RetEffect::NoRetHard) {
2960    SymbolRef Sym = CallOrMsg.getReturnValue().getAsSymbol();
2961    if (Sym)
2962      state = removeRefBinding(state, Sym);
2963  }
2964
2965  C.addTransition(state);
2966}
2967
2968static ProgramStateRef updateOutParameter(ProgramStateRef State,
2969                                          SVal ArgVal,
2970                                          ArgEffect Effect) {
2971  auto *ArgRegion = dyn_cast_or_null<TypedValueRegion>(ArgVal.getAsRegion());
2972  if (!ArgRegion)
2973    return State;
2974
2975  QualType PointeeTy = ArgRegion->getValueType();
2976  if (!coreFoundation::isCFObjectRef(PointeeTy))
2977    return State;
2978
2979  SVal PointeeVal = State->getSVal(ArgRegion);
2980  SymbolRef Pointee = PointeeVal.getAsLocSymbol();
2981  if (!Pointee)
2982    return State;
2983
2984  switch (Effect) {
2985  case UnretainedOutParameter:
2986    State = setRefBinding(State, Pointee,
2987                          RefVal::makeNotOwned(RetEffect::CF, PointeeTy));
2988    break;
2989  case RetainedOutParameter:
2990    // Do nothing. Retained out parameters will either point to a +1 reference
2991    // or NULL, but the way you check for failure differs depending on the API.
2992    // Consequently, we don't have a good way to track them yet.
2993    break;
2994
2995  default:
2996    llvm_unreachable("only for out parameters");
2997  }
2998
2999  return State;
3000}
3001
3002void RetainCountChecker::checkSummary(const RetainSummary &Summ,
3003                                      const CallEvent &CallOrMsg,
3004                                      CheckerContext &C) const {
3005  ProgramStateRef state = C.getState();
3006
3007  // Evaluate the effect of the arguments.
3008  RefVal::Kind hasErr = (RefVal::Kind) 0;
3009  SourceRange ErrorRange;
3010  SymbolRef ErrorSym = nullptr;
3011
3012  for (unsigned idx = 0, e = CallOrMsg.getNumArgs(); idx != e; ++idx) {
3013    SVal V = CallOrMsg.getArgSVal(idx);
3014
3015    ArgEffect Effect = Summ.getArg(idx);
3016    if (Effect == RetainedOutParameter || Effect == UnretainedOutParameter) {
3017      state = updateOutParameter(state, V, Effect);
3018    } else if (SymbolRef Sym = V.getAsLocSymbol()) {
3019      if (const RefVal *T = getRefBinding(state, Sym)) {
3020        state = updateSymbol(state, Sym, *T, Effect, hasErr, C);
3021        if (hasErr) {
3022          ErrorRange = CallOrMsg.getArgSourceRange(idx);
3023          ErrorSym = Sym;
3024          break;
3025        }
3026      }
3027    }
3028  }
3029
3030  // Evaluate the effect on the message receiver.
3031  bool ReceiverIsTracked = false;
3032  if (!hasErr) {
3033    const ObjCMethodCall *MsgInvocation = dyn_cast<ObjCMethodCall>(&CallOrMsg);
3034    if (MsgInvocation) {
3035      if (SymbolRef Sym = MsgInvocation->getReceiverSVal().getAsLocSymbol()) {
3036        if (const RefVal *T = getRefBinding(state, Sym)) {
3037          ReceiverIsTracked = true;
3038          state = updateSymbol(state, Sym, *T, Summ.getReceiverEffect(),
3039                                 hasErr, C);
3040          if (hasErr) {
3041            ErrorRange = MsgInvocation->getOriginExpr()->getReceiverRange();
3042            ErrorSym = Sym;
3043          }
3044        }
3045      }
3046    }
3047  }
3048
3049  // Process any errors.
3050  if (hasErr) {
3051    processNonLeakError(state, ErrorRange, hasErr, ErrorSym, C);
3052    return;
3053  }
3054
3055  // Consult the summary for the return value.
3056  RetEffect RE = Summ.getRetEffect();
3057
3058  if (RE.getKind() == RetEffect::OwnedWhenTrackedReceiver) {
3059    if (ReceiverIsTracked)
3060      RE = getSummaryManager(C).getObjAllocRetEffect();
3061    else
3062      RE = RetEffect::MakeNoRet();
3063  }
3064
3065  switch (RE.getKind()) {
3066    default:
3067      llvm_unreachable("Unhandled RetEffect.");
3068
3069    case RetEffect::NoRet:
3070    case RetEffect::NoRetHard:
3071      // No work necessary.
3072      break;
3073
3074    case RetEffect::OwnedAllocatedSymbol:
3075    case RetEffect::OwnedSymbol: {
3076      SymbolRef Sym = CallOrMsg.getReturnValue().getAsSymbol();
3077      if (!Sym)
3078        break;
3079
3080      // Use the result type from the CallEvent as it automatically adjusts
3081      // for methods/functions that return references.
3082      QualType ResultTy = CallOrMsg.getResultType();
3083      state = setRefBinding(state, Sym, RefVal::makeOwned(RE.getObjKind(),
3084                                                          ResultTy));
3085
3086      // FIXME: Add a flag to the checker where allocations are assumed to
3087      // *not* fail.
3088      break;
3089    }
3090
3091    case RetEffect::GCNotOwnedSymbol:
3092    case RetEffect::NotOwnedSymbol: {
3093      const Expr *Ex = CallOrMsg.getOriginExpr();
3094      SymbolRef Sym = CallOrMsg.getReturnValue().getAsSymbol();
3095      if (!Sym)
3096        break;
3097      assert(Ex);
3098      // Use GetReturnType in order to give [NSFoo alloc] the type NSFoo *.
3099      QualType ResultTy = GetReturnType(Ex, C.getASTContext());
3100      state = setRefBinding(state, Sym, RefVal::makeNotOwned(RE.getObjKind(),
3101                                                             ResultTy));
3102      break;
3103    }
3104  }
3105
3106  // This check is actually necessary; otherwise the statement builder thinks
3107  // we've hit a previously-found path.
3108  // Normally addTransition takes care of this, but we want the node pointer.
3109  ExplodedNode *NewNode;
3110  if (state == C.getState()) {
3111    NewNode = C.getPredecessor();
3112  } else {
3113    NewNode = C.addTransition(state);
3114  }
3115
3116  // Annotate the node with summary we used.
3117  if (NewNode) {
3118    // FIXME: This is ugly. See checkEndAnalysis for why it's necessary.
3119    if (ShouldResetSummaryLog) {
3120      SummaryLog.clear();
3121      ShouldResetSummaryLog = false;
3122    }
3123    SummaryLog[NewNode] = &Summ;
3124  }
3125}
3126
3127ProgramStateRef
3128RetainCountChecker::updateSymbol(ProgramStateRef state, SymbolRef sym,
3129                                 RefVal V, ArgEffect E, RefVal::Kind &hasErr,
3130                                 CheckerContext &C) const {
3131  // In GC mode [... release] and [... retain] do nothing.
3132  // In ARC mode they shouldn't exist at all, but we just ignore them.
3133  bool IgnoreRetainMsg = C.isObjCGCEnabled();
3134  if (!IgnoreRetainMsg)
3135    IgnoreRetainMsg = (bool)C.getASTContext().getLangOpts().ObjCAutoRefCount;
3136
3137  switch (E) {
3138  default:
3139    break;
3140  case IncRefMsg:
3141    E = IgnoreRetainMsg ? DoNothing : IncRef;
3142    break;
3143  case DecRefMsg:
3144    E = IgnoreRetainMsg ? DoNothing : DecRef;
3145    break;
3146  case DecRefMsgAndStopTrackingHard:
3147    E = IgnoreRetainMsg ? StopTracking : DecRefAndStopTrackingHard;
3148    break;
3149  case MakeCollectable:
3150    E = C.isObjCGCEnabled() ? DecRef : DoNothing;
3151    break;
3152  }
3153
3154  // Handle all use-after-releases.
3155  if (!C.isObjCGCEnabled() && V.getKind() == RefVal::Released) {
3156    V = V ^ RefVal::ErrorUseAfterRelease;
3157    hasErr = V.getKind();
3158    return setRefBinding(state, sym, V);
3159  }
3160
3161  switch (E) {
3162    case DecRefMsg:
3163    case IncRefMsg:
3164    case MakeCollectable:
3165    case DecRefMsgAndStopTrackingHard:
3166      llvm_unreachable("DecRefMsg/IncRefMsg/MakeCollectable already converted");
3167
3168    case UnretainedOutParameter:
3169    case RetainedOutParameter:
3170      llvm_unreachable("Applies to pointer-to-pointer parameters, which should "
3171                       "not have ref state.");
3172
3173    case Dealloc:
3174      // Any use of -dealloc in GC is *bad*.
3175      if (C.isObjCGCEnabled()) {
3176        V = V ^ RefVal::ErrorDeallocGC;
3177        hasErr = V.getKind();
3178        break;
3179      }
3180
3181      switch (V.getKind()) {
3182        default:
3183          llvm_unreachable("Invalid RefVal state for an explicit dealloc.");
3184        case RefVal::Owned:
3185          // The object immediately transitions to the released state.
3186          V = V ^ RefVal::Released;
3187          V.clearCounts();
3188          return setRefBinding(state, sym, V);
3189        case RefVal::NotOwned:
3190          V = V ^ RefVal::ErrorDeallocNotOwned;
3191          hasErr = V.getKind();
3192          break;
3193      }
3194      break;
3195
3196    case MayEscape:
3197      if (V.getKind() == RefVal::Owned) {
3198        V = V ^ RefVal::NotOwned;
3199        break;
3200      }
3201
3202      // Fall-through.
3203
3204    case DoNothing:
3205      return state;
3206
3207    case Autorelease:
3208      if (C.isObjCGCEnabled())
3209        return state;
3210      // Update the autorelease counts.
3211      V = V.autorelease();
3212      break;
3213
3214    case StopTracking:
3215    case StopTrackingHard:
3216      return removeRefBinding(state, sym);
3217
3218    case IncRef:
3219      switch (V.getKind()) {
3220        default:
3221          llvm_unreachable("Invalid RefVal state for a retain.");
3222        case RefVal::Owned:
3223        case RefVal::NotOwned:
3224          V = V + 1;
3225          break;
3226        case RefVal::Released:
3227          // Non-GC cases are handled above.
3228          assert(C.isObjCGCEnabled());
3229          V = (V ^ RefVal::Owned) + 1;
3230          break;
3231      }
3232      break;
3233
3234    case DecRef:
3235    case DecRefBridgedTransferred:
3236    case DecRefAndStopTrackingHard:
3237      switch (V.getKind()) {
3238        default:
3239          // case 'RefVal::Released' handled above.
3240          llvm_unreachable("Invalid RefVal state for a release.");
3241
3242        case RefVal::Owned:
3243          assert(V.getCount() > 0);
3244          if (V.getCount() == 1) {
3245            if (E == DecRefBridgedTransferred ||
3246                V.getIvarAccessHistory() ==
3247                  RefVal::IvarAccessHistory::AccessedDirectly)
3248              V = V ^ RefVal::NotOwned;
3249            else
3250              V = V ^ RefVal::Released;
3251          } else if (E == DecRefAndStopTrackingHard) {
3252            return removeRefBinding(state, sym);
3253          }
3254
3255          V = V - 1;
3256          break;
3257
3258        case RefVal::NotOwned:
3259          if (V.getCount() > 0) {
3260            if (E == DecRefAndStopTrackingHard)
3261              return removeRefBinding(state, sym);
3262            V = V - 1;
3263          } else if (V.getIvarAccessHistory() ==
3264                       RefVal::IvarAccessHistory::AccessedDirectly) {
3265            // Assume that the instance variable was holding on the object at
3266            // +1, and we just didn't know.
3267            if (E == DecRefAndStopTrackingHard)
3268              return removeRefBinding(state, sym);
3269            V = V.releaseViaIvar() ^ RefVal::Released;
3270          } else {
3271            V = V ^ RefVal::ErrorReleaseNotOwned;
3272            hasErr = V.getKind();
3273          }
3274          break;
3275
3276        case RefVal::Released:
3277          // Non-GC cases are handled above.
3278          assert(C.isObjCGCEnabled());
3279          V = V ^ RefVal::ErrorUseAfterRelease;
3280          hasErr = V.getKind();
3281          break;
3282      }
3283      break;
3284  }
3285  return setRefBinding(state, sym, V);
3286}
3287
3288void RetainCountChecker::processNonLeakError(ProgramStateRef St,
3289                                             SourceRange ErrorRange,
3290                                             RefVal::Kind ErrorKind,
3291                                             SymbolRef Sym,
3292                                             CheckerContext &C) const {
3293  // HACK: Ignore retain-count issues on values accessed through ivars,
3294  // because of cases like this:
3295  //   [_contentView retain];
3296  //   [_contentView removeFromSuperview];
3297  //   [self addSubview:_contentView]; // invalidates 'self'
3298  //   [_contentView release];
3299  if (const RefVal *RV = getRefBinding(St, Sym))
3300    if (RV->getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
3301      return;
3302
3303  ExplodedNode *N = C.generateErrorNode(St);
3304  if (!N)
3305    return;
3306
3307  CFRefBug *BT;
3308  switch (ErrorKind) {
3309    default:
3310      llvm_unreachable("Unhandled error.");
3311    case RefVal::ErrorUseAfterRelease:
3312      if (!useAfterRelease)
3313        useAfterRelease.reset(new UseAfterRelease(this));
3314      BT = useAfterRelease.get();
3315      break;
3316    case RefVal::ErrorReleaseNotOwned:
3317      if (!releaseNotOwned)
3318        releaseNotOwned.reset(new BadRelease(this));
3319      BT = releaseNotOwned.get();
3320      break;
3321    case RefVal::ErrorDeallocGC:
3322      if (!deallocGC)
3323        deallocGC.reset(new DeallocGC(this));
3324      BT = deallocGC.get();
3325      break;
3326    case RefVal::ErrorDeallocNotOwned:
3327      if (!deallocNotOwned)
3328        deallocNotOwned.reset(new DeallocNotOwned(this));
3329      BT = deallocNotOwned.get();
3330      break;
3331  }
3332
3333  assert(BT);
3334  auto report = std::unique_ptr<BugReport>(
3335      new CFRefReport(*BT, C.getASTContext().getLangOpts(), C.isObjCGCEnabled(),
3336                      SummaryLog, N, Sym));
3337  report->addRange(ErrorRange);
3338  C.emitReport(std::move(report));
3339}
3340
3341//===----------------------------------------------------------------------===//
3342// Handle the return values of retain-count-related functions.
3343//===----------------------------------------------------------------------===//
3344
3345bool RetainCountChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
3346  // Get the callee. We're only interested in simple C functions.
3347  ProgramStateRef state = C.getState();
3348  const FunctionDecl *FD = C.getCalleeDecl(CE);
3349  if (!FD)
3350    return false;
3351
3352  IdentifierInfo *II = FD->getIdentifier();
3353  if (!II)
3354    return false;
3355
3356  // For now, we're only handling the functions that return aliases of their
3357  // arguments: CFRetain and CFMakeCollectable (and their families).
3358  // Eventually we should add other functions we can model entirely,
3359  // such as CFRelease, which don't invalidate their arguments or globals.
3360  if (CE->getNumArgs() != 1)
3361    return false;
3362
3363  // Get the name of the function.
3364  StringRef FName = II->getName();
3365  FName = FName.substr(FName.find_first_not_of('_'));
3366
3367  // See if it's one of the specific functions we know how to eval.
3368  bool canEval = false;
3369
3370  QualType ResultTy = CE->getCallReturnType(C.getASTContext());
3371  if (ResultTy->isObjCIdType()) {
3372    // Handle: id NSMakeCollectable(CFTypeRef)
3373    canEval = II->isStr("NSMakeCollectable");
3374  } else if (ResultTy->isPointerType()) {
3375    // Handle: (CF|CG)Retain
3376    //         CFAutorelease
3377    //         CFMakeCollectable
3378    // It's okay to be a little sloppy here (CGMakeCollectable doesn't exist).
3379    if (cocoa::isRefType(ResultTy, "CF", FName) ||
3380        cocoa::isRefType(ResultTy, "CG", FName)) {
3381      canEval = isRetain(FD, FName) || isAutorelease(FD, FName) ||
3382                isMakeCollectable(FD, FName);
3383    }
3384  }
3385
3386  if (!canEval)
3387    return false;
3388
3389  // Bind the return value.
3390  const LocationContext *LCtx = C.getLocationContext();
3391  SVal RetVal = state->getSVal(CE->getArg(0), LCtx);
3392  if (RetVal.isUnknown()) {
3393    // If the receiver is unknown, conjure a return value.
3394    SValBuilder &SVB = C.getSValBuilder();
3395    RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, ResultTy, C.blockCount());
3396  }
3397  state = state->BindExpr(CE, LCtx, RetVal, false);
3398
3399  // FIXME: This should not be necessary, but otherwise the argument seems to be
3400  // considered alive during the next statement.
3401  if (const MemRegion *ArgRegion = RetVal.getAsRegion()) {
3402    // Save the refcount status of the argument.
3403    SymbolRef Sym = RetVal.getAsLocSymbol();
3404    const RefVal *Binding = nullptr;
3405    if (Sym)
3406      Binding = getRefBinding(state, Sym);
3407
3408    // Invalidate the argument region.
3409    state = state->invalidateRegions(ArgRegion, CE, C.blockCount(), LCtx,
3410                                     /*CausesPointerEscape*/ false);
3411
3412    // Restore the refcount status of the argument.
3413    if (Binding)
3414      state = setRefBinding(state, Sym, *Binding);
3415  }
3416
3417  C.addTransition(state);
3418  return true;
3419}
3420
3421//===----------------------------------------------------------------------===//
3422// Handle return statements.
3423//===----------------------------------------------------------------------===//
3424
3425void RetainCountChecker::checkPreStmt(const ReturnStmt *S,
3426                                      CheckerContext &C) const {
3427
3428  // Only adjust the reference count if this is the top-level call frame,
3429  // and not the result of inlining.  In the future, we should do
3430  // better checking even for inlined calls, and see if they match
3431  // with their expected semantics (e.g., the method should return a retained
3432  // object, etc.).
3433  if (!C.inTopFrame())
3434    return;
3435
3436  const Expr *RetE = S->getRetValue();
3437  if (!RetE)
3438    return;
3439
3440  ProgramStateRef state = C.getState();
3441  SymbolRef Sym =
3442    state->getSValAsScalarOrLoc(RetE, C.getLocationContext()).getAsLocSymbol();
3443  if (!Sym)
3444    return;
3445
3446  // Get the reference count binding (if any).
3447  const RefVal *T = getRefBinding(state, Sym);
3448  if (!T)
3449    return;
3450
3451  // Change the reference count.
3452  RefVal X = *T;
3453
3454  switch (X.getKind()) {
3455    case RefVal::Owned: {
3456      unsigned cnt = X.getCount();
3457      assert(cnt > 0);
3458      X.setCount(cnt - 1);
3459      X = X ^ RefVal::ReturnedOwned;
3460      break;
3461    }
3462
3463    case RefVal::NotOwned: {
3464      unsigned cnt = X.getCount();
3465      if (cnt) {
3466        X.setCount(cnt - 1);
3467        X = X ^ RefVal::ReturnedOwned;
3468      }
3469      else {
3470        X = X ^ RefVal::ReturnedNotOwned;
3471      }
3472      break;
3473    }
3474
3475    default:
3476      return;
3477  }
3478
3479  // Update the binding.
3480  state = setRefBinding(state, Sym, X);
3481  ExplodedNode *Pred = C.addTransition(state);
3482
3483  // At this point we have updated the state properly.
3484  // Everything after this is merely checking to see if the return value has
3485  // been over- or under-retained.
3486
3487  // Did we cache out?
3488  if (!Pred)
3489    return;
3490
3491  // Update the autorelease counts.
3492  static CheckerProgramPointTag AutoreleaseTag(this, "Autorelease");
3493  state = handleAutoreleaseCounts(state, Pred, &AutoreleaseTag, C, Sym, X);
3494
3495  // Did we cache out?
3496  if (!state)
3497    return;
3498
3499  // Get the updated binding.
3500  T = getRefBinding(state, Sym);
3501  assert(T);
3502  X = *T;
3503
3504  // Consult the summary of the enclosing method.
3505  RetainSummaryManager &Summaries = getSummaryManager(C);
3506  const Decl *CD = &Pred->getCodeDecl();
3507  RetEffect RE = RetEffect::MakeNoRet();
3508
3509  // FIXME: What is the convention for blocks? Is there one?
3510  if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(CD)) {
3511    const RetainSummary *Summ = Summaries.getMethodSummary(MD);
3512    RE = Summ->getRetEffect();
3513  } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CD)) {
3514    if (!isa<CXXMethodDecl>(FD)) {
3515      const RetainSummary *Summ = Summaries.getFunctionSummary(FD);
3516      RE = Summ->getRetEffect();
3517    }
3518  }
3519
3520  checkReturnWithRetEffect(S, C, Pred, RE, X, Sym, state);
3521}
3522
3523void RetainCountChecker::checkReturnWithRetEffect(const ReturnStmt *S,
3524                                                  CheckerContext &C,
3525                                                  ExplodedNode *Pred,
3526                                                  RetEffect RE, RefVal X,
3527                                                  SymbolRef Sym,
3528                                                  ProgramStateRef state) const {
3529  // HACK: Ignore retain-count issues on values accessed through ivars,
3530  // because of cases like this:
3531  //   [_contentView retain];
3532  //   [_contentView removeFromSuperview];
3533  //   [self addSubview:_contentView]; // invalidates 'self'
3534  //   [_contentView release];
3535  if (X.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
3536    return;
3537
3538  // Any leaks or other errors?
3539  if (X.isReturnedOwned() && X.getCount() == 0) {
3540    if (RE.getKind() != RetEffect::NoRet) {
3541      bool hasError = false;
3542      if (C.isObjCGCEnabled() && RE.getObjKind() == RetEffect::ObjC) {
3543        // Things are more complicated with garbage collection.  If the
3544        // returned object is suppose to be an Objective-C object, we have
3545        // a leak (as the caller expects a GC'ed object) because no
3546        // method should return ownership unless it returns a CF object.
3547        hasError = true;
3548        X = X ^ RefVal::ErrorGCLeakReturned;
3549      }
3550      else if (!RE.isOwned()) {
3551        // Either we are using GC and the returned object is a CF type
3552        // or we aren't using GC.  In either case, we expect that the
3553        // enclosing method is expected to return ownership.
3554        hasError = true;
3555        X = X ^ RefVal::ErrorLeakReturned;
3556      }
3557
3558      if (hasError) {
3559        // Generate an error node.
3560        state = setRefBinding(state, Sym, X);
3561
3562        static CheckerProgramPointTag ReturnOwnLeakTag(this, "ReturnsOwnLeak");
3563        ExplodedNode *N = C.addTransition(state, Pred, &ReturnOwnLeakTag);
3564        if (N) {
3565          const LangOptions &LOpts = C.getASTContext().getLangOpts();
3566          bool GCEnabled = C.isObjCGCEnabled();
3567          C.emitReport(std::unique_ptr<BugReport>(new CFRefLeakReport(
3568              *getLeakAtReturnBug(LOpts, GCEnabled), LOpts, GCEnabled,
3569              SummaryLog, N, Sym, C, IncludeAllocationLine)));
3570        }
3571      }
3572    }
3573  } else if (X.isReturnedNotOwned()) {
3574    if (RE.isOwned()) {
3575      if (X.getIvarAccessHistory() ==
3576            RefVal::IvarAccessHistory::AccessedDirectly) {
3577        // Assume the method was trying to transfer a +1 reference from a
3578        // strong ivar to the caller.
3579        state = setRefBinding(state, Sym,
3580                              X.releaseViaIvar() ^ RefVal::ReturnedOwned);
3581      } else {
3582        // Trying to return a not owned object to a caller expecting an
3583        // owned object.
3584        state = setRefBinding(state, Sym, X ^ RefVal::ErrorReturnedNotOwned);
3585
3586        static CheckerProgramPointTag
3587            ReturnNotOwnedTag(this, "ReturnNotOwnedForOwned");
3588
3589        ExplodedNode *N = C.addTransition(state, Pred, &ReturnNotOwnedTag);
3590        if (N) {
3591          if (!returnNotOwnedForOwned)
3592            returnNotOwnedForOwned.reset(new ReturnedNotOwnedForOwned(this));
3593
3594          C.emitReport(std::unique_ptr<BugReport>(new CFRefReport(
3595              *returnNotOwnedForOwned, C.getASTContext().getLangOpts(),
3596              C.isObjCGCEnabled(), SummaryLog, N, Sym)));
3597        }
3598      }
3599    }
3600  }
3601}
3602
3603//===----------------------------------------------------------------------===//
3604// Check various ways a symbol can be invalidated.
3605//===----------------------------------------------------------------------===//
3606
3607void RetainCountChecker::checkBind(SVal loc, SVal val, const Stmt *S,
3608                                   CheckerContext &C) const {
3609  // Are we storing to something that causes the value to "escape"?
3610  bool escapes = true;
3611
3612  // A value escapes in three possible cases (this may change):
3613  //
3614  // (1) we are binding to something that is not a memory region.
3615  // (2) we are binding to a memregion that does not have stack storage
3616  // (3) we are binding to a memregion with stack storage that the store
3617  //     does not understand.
3618  ProgramStateRef state = C.getState();
3619
3620  if (Optional<loc::MemRegionVal> regionLoc = loc.getAs<loc::MemRegionVal>()) {
3621    escapes = !regionLoc->getRegion()->hasStackStorage();
3622
3623    if (!escapes) {
3624      // To test (3), generate a new state with the binding added.  If it is
3625      // the same state, then it escapes (since the store cannot represent
3626      // the binding).
3627      // Do this only if we know that the store is not supposed to generate the
3628      // same state.
3629      SVal StoredVal = state->getSVal(regionLoc->getRegion());
3630      if (StoredVal != val)
3631        escapes = (state == (state->bindLoc(*regionLoc, val)));
3632    }
3633    if (!escapes) {
3634      // Case 4: We do not currently model what happens when a symbol is
3635      // assigned to a struct field, so be conservative here and let the symbol
3636      // go. TODO: This could definitely be improved upon.
3637      escapes = !isa<VarRegion>(regionLoc->getRegion());
3638    }
3639  }
3640
3641  // If we are storing the value into an auto function scope variable annotated
3642  // with (__attribute__((cleanup))), stop tracking the value to avoid leak
3643  // false positives.
3644  if (const VarRegion *LVR = dyn_cast_or_null<VarRegion>(loc.getAsRegion())) {
3645    const VarDecl *VD = LVR->getDecl();
3646    if (VD->hasAttr<CleanupAttr>()) {
3647      escapes = true;
3648    }
3649  }
3650
3651  // If our store can represent the binding and we aren't storing to something
3652  // that doesn't have local storage then just return and have the simulation
3653  // state continue as is.
3654  if (!escapes)
3655      return;
3656
3657  // Otherwise, find all symbols referenced by 'val' that we are tracking
3658  // and stop tracking them.
3659  state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
3660  C.addTransition(state);
3661}
3662
3663ProgramStateRef RetainCountChecker::evalAssume(ProgramStateRef state,
3664                                                   SVal Cond,
3665                                                   bool Assumption) const {
3666  // FIXME: We may add to the interface of evalAssume the list of symbols
3667  //  whose assumptions have changed.  For now we just iterate through the
3668  //  bindings and check if any of the tracked symbols are NULL.  This isn't
3669  //  too bad since the number of symbols we will track in practice are
3670  //  probably small and evalAssume is only called at branches and a few
3671  //  other places.
3672  RefBindingsTy B = state->get<RefBindings>();
3673
3674  if (B.isEmpty())
3675    return state;
3676
3677  bool changed = false;
3678  RefBindingsTy::Factory &RefBFactory = state->get_context<RefBindings>();
3679
3680  for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3681    // Check if the symbol is null stop tracking the symbol.
3682    ConstraintManager &CMgr = state->getConstraintManager();
3683    ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
3684    if (AllocFailed.isConstrainedTrue()) {
3685      changed = true;
3686      B = RefBFactory.remove(B, I.getKey());
3687    }
3688  }
3689
3690  if (changed)
3691    state = state->set<RefBindings>(B);
3692
3693  return state;
3694}
3695
3696ProgramStateRef
3697RetainCountChecker::checkRegionChanges(ProgramStateRef state,
3698                                    const InvalidatedSymbols *invalidated,
3699                                    ArrayRef<const MemRegion *> ExplicitRegions,
3700                                    ArrayRef<const MemRegion *> Regions,
3701                                    const CallEvent *Call) const {
3702  if (!invalidated)
3703    return state;
3704
3705  llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
3706  for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
3707       E = ExplicitRegions.end(); I != E; ++I) {
3708    if (const SymbolicRegion *SR = (*I)->StripCasts()->getAs<SymbolicRegion>())
3709      WhitelistedSymbols.insert(SR->getSymbol());
3710  }
3711
3712  for (InvalidatedSymbols::const_iterator I=invalidated->begin(),
3713       E = invalidated->end(); I!=E; ++I) {
3714    SymbolRef sym = *I;
3715    if (WhitelistedSymbols.count(sym))
3716      continue;
3717    // Remove any existing reference-count binding.
3718    state = removeRefBinding(state, sym);
3719  }
3720  return state;
3721}
3722
3723//===----------------------------------------------------------------------===//
3724// Handle dead symbols and end-of-path.
3725//===----------------------------------------------------------------------===//
3726
3727ProgramStateRef
3728RetainCountChecker::handleAutoreleaseCounts(ProgramStateRef state,
3729                                            ExplodedNode *Pred,
3730                                            const ProgramPointTag *Tag,
3731                                            CheckerContext &Ctx,
3732                                            SymbolRef Sym, RefVal V) const {
3733  unsigned ACnt = V.getAutoreleaseCount();
3734
3735  // No autorelease counts?  Nothing to be done.
3736  if (!ACnt)
3737    return state;
3738
3739  assert(!Ctx.isObjCGCEnabled() && "Autorelease counts in GC mode?");
3740  unsigned Cnt = V.getCount();
3741
3742  // FIXME: Handle sending 'autorelease' to already released object.
3743
3744  if (V.getKind() == RefVal::ReturnedOwned)
3745    ++Cnt;
3746
3747  // If we would over-release here, but we know the value came from an ivar,
3748  // assume it was a strong ivar that's just been relinquished.
3749  if (ACnt > Cnt &&
3750      V.getIvarAccessHistory() == RefVal::IvarAccessHistory::AccessedDirectly) {
3751    V = V.releaseViaIvar();
3752    --ACnt;
3753  }
3754
3755  if (ACnt <= Cnt) {
3756    if (ACnt == Cnt) {
3757      V.clearCounts();
3758      if (V.getKind() == RefVal::ReturnedOwned)
3759        V = V ^ RefVal::ReturnedNotOwned;
3760      else
3761        V = V ^ RefVal::NotOwned;
3762    } else {
3763      V.setCount(V.getCount() - ACnt);
3764      V.setAutoreleaseCount(0);
3765    }
3766    return setRefBinding(state, Sym, V);
3767  }
3768
3769  // HACK: Ignore retain-count issues on values accessed through ivars,
3770  // because of cases like this:
3771  //   [_contentView retain];
3772  //   [_contentView removeFromSuperview];
3773  //   [self addSubview:_contentView]; // invalidates 'self'
3774  //   [_contentView release];
3775  if (V.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
3776    return state;
3777
3778  // Woah!  More autorelease counts then retain counts left.
3779  // Emit hard error.
3780  V = V ^ RefVal::ErrorOverAutorelease;
3781  state = setRefBinding(state, Sym, V);
3782
3783  ExplodedNode *N = Ctx.generateSink(state, Pred, Tag);
3784  if (N) {
3785    SmallString<128> sbuf;
3786    llvm::raw_svector_ostream os(sbuf);
3787    os << "Object was autoreleased ";
3788    if (V.getAutoreleaseCount() > 1)
3789      os << V.getAutoreleaseCount() << " times but the object ";
3790    else
3791      os << "but ";
3792    os << "has a +" << V.getCount() << " retain count";
3793
3794    if (!overAutorelease)
3795      overAutorelease.reset(new OverAutorelease(this));
3796
3797    const LangOptions &LOpts = Ctx.getASTContext().getLangOpts();
3798    Ctx.emitReport(std::unique_ptr<BugReport>(
3799        new CFRefReport(*overAutorelease, LOpts, /* GCEnabled = */ false,
3800                        SummaryLog, N, Sym, os.str())));
3801  }
3802
3803  return nullptr;
3804}
3805
3806ProgramStateRef
3807RetainCountChecker::handleSymbolDeath(ProgramStateRef state,
3808                                      SymbolRef sid, RefVal V,
3809                                    SmallVectorImpl<SymbolRef> &Leaked) const {
3810  bool hasLeak;
3811
3812  // HACK: Ignore retain-count issues on values accessed through ivars,
3813  // because of cases like this:
3814  //   [_contentView retain];
3815  //   [_contentView removeFromSuperview];
3816  //   [self addSubview:_contentView]; // invalidates 'self'
3817  //   [_contentView release];
3818  if (V.getIvarAccessHistory() != RefVal::IvarAccessHistory::None)
3819    hasLeak = false;
3820  else if (V.isOwned())
3821    hasLeak = true;
3822  else if (V.isNotOwned() || V.isReturnedOwned())
3823    hasLeak = (V.getCount() > 0);
3824  else
3825    hasLeak = false;
3826
3827  if (!hasLeak)
3828    return removeRefBinding(state, sid);
3829
3830  Leaked.push_back(sid);
3831  return setRefBinding(state, sid, V ^ RefVal::ErrorLeak);
3832}
3833
3834ExplodedNode *
3835RetainCountChecker::processLeaks(ProgramStateRef state,
3836                                 SmallVectorImpl<SymbolRef> &Leaked,
3837                                 CheckerContext &Ctx,
3838                                 ExplodedNode *Pred) const {
3839  // Generate an intermediate node representing the leak point.
3840  ExplodedNode *N = Ctx.addTransition(state, Pred);
3841
3842  if (N) {
3843    for (SmallVectorImpl<SymbolRef>::iterator
3844         I = Leaked.begin(), E = Leaked.end(); I != E; ++I) {
3845
3846      const LangOptions &LOpts = Ctx.getASTContext().getLangOpts();
3847      bool GCEnabled = Ctx.isObjCGCEnabled();
3848      CFRefBug *BT = Pred ? getLeakWithinFunctionBug(LOpts, GCEnabled)
3849                          : getLeakAtReturnBug(LOpts, GCEnabled);
3850      assert(BT && "BugType not initialized.");
3851
3852      Ctx.emitReport(std::unique_ptr<BugReport>(
3853          new CFRefLeakReport(*BT, LOpts, GCEnabled, SummaryLog, N, *I, Ctx,
3854                              IncludeAllocationLine)));
3855    }
3856  }
3857
3858  return N;
3859}
3860
3861void RetainCountChecker::checkEndFunction(CheckerContext &Ctx) const {
3862  ProgramStateRef state = Ctx.getState();
3863  RefBindingsTy B = state->get<RefBindings>();
3864  ExplodedNode *Pred = Ctx.getPredecessor();
3865
3866  // Don't process anything within synthesized bodies.
3867  const LocationContext *LCtx = Pred->getLocationContext();
3868  if (LCtx->getAnalysisDeclContext()->isBodyAutosynthesized()) {
3869    assert(LCtx->getParent());
3870    return;
3871  }
3872
3873  for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3874    state = handleAutoreleaseCounts(state, Pred, /*Tag=*/nullptr, Ctx,
3875                                    I->first, I->second);
3876    if (!state)
3877      return;
3878  }
3879
3880  // If the current LocationContext has a parent, don't check for leaks.
3881  // We will do that later.
3882  // FIXME: we should instead check for imbalances of the retain/releases,
3883  // and suggest annotations.
3884  if (LCtx->getParent())
3885    return;
3886
3887  B = state->get<RefBindings>();
3888  SmallVector<SymbolRef, 10> Leaked;
3889
3890  for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I)
3891    state = handleSymbolDeath(state, I->first, I->second, Leaked);
3892
3893  processLeaks(state, Leaked, Ctx, Pred);
3894}
3895
3896const ProgramPointTag *
3897RetainCountChecker::getDeadSymbolTag(SymbolRef sym) const {
3898  const CheckerProgramPointTag *&tag = DeadSymbolTags[sym];
3899  if (!tag) {
3900    SmallString<64> buf;
3901    llvm::raw_svector_ostream out(buf);
3902    out << "Dead Symbol : ";
3903    sym->dumpToStream(out);
3904    tag = new CheckerProgramPointTag(this, out.str());
3905  }
3906  return tag;
3907}
3908
3909void RetainCountChecker::checkDeadSymbols(SymbolReaper &SymReaper,
3910                                          CheckerContext &C) const {
3911  ExplodedNode *Pred = C.getPredecessor();
3912
3913  ProgramStateRef state = C.getState();
3914  RefBindingsTy B = state->get<RefBindings>();
3915  SmallVector<SymbolRef, 10> Leaked;
3916
3917  // Update counts from autorelease pools
3918  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
3919       E = SymReaper.dead_end(); I != E; ++I) {
3920    SymbolRef Sym = *I;
3921    if (const RefVal *T = B.lookup(Sym)){
3922      // Use the symbol as the tag.
3923      // FIXME: This might not be as unique as we would like.
3924      const ProgramPointTag *Tag = getDeadSymbolTag(Sym);
3925      state = handleAutoreleaseCounts(state, Pred, Tag, C, Sym, *T);
3926      if (!state)
3927        return;
3928
3929      // Fetch the new reference count from the state, and use it to handle
3930      // this symbol.
3931      state = handleSymbolDeath(state, *I, *getRefBinding(state, Sym), Leaked);
3932    }
3933  }
3934
3935  if (Leaked.empty()) {
3936    C.addTransition(state);
3937    return;
3938  }
3939
3940  Pred = processLeaks(state, Leaked, C, Pred);
3941
3942  // Did we cache out?
3943  if (!Pred)
3944    return;
3945
3946  // Now generate a new node that nukes the old bindings.
3947  // The only bindings left at this point are the leaked symbols.
3948  RefBindingsTy::Factory &F = state->get_context<RefBindings>();
3949  B = state->get<RefBindings>();
3950
3951  for (SmallVectorImpl<SymbolRef>::iterator I = Leaked.begin(),
3952                                            E = Leaked.end();
3953       I != E; ++I)
3954    B = F.remove(B, *I);
3955
3956  state = state->set<RefBindings>(B);
3957  C.addTransition(state, Pred);
3958}
3959
3960void RetainCountChecker::printState(raw_ostream &Out, ProgramStateRef State,
3961                                    const char *NL, const char *Sep) const {
3962
3963  RefBindingsTy B = State->get<RefBindings>();
3964
3965  if (B.isEmpty())
3966    return;
3967
3968  Out << Sep << NL;
3969
3970  for (RefBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3971    Out << I->first << " : ";
3972    I->second.print(Out);
3973    Out << NL;
3974  }
3975}
3976
3977//===----------------------------------------------------------------------===//
3978// Checker registration.
3979//===----------------------------------------------------------------------===//
3980
3981void ento::registerRetainCountChecker(CheckerManager &Mgr) {
3982  Mgr.registerChecker<RetainCountChecker>(Mgr.getAnalyzerOptions());
3983}
3984
3985//===----------------------------------------------------------------------===//
3986// Implementation of the CallEffects API.
3987//===----------------------------------------------------------------------===//
3988
3989namespace clang {
3990namespace ento {
3991namespace objc_retain {
3992
3993// This is a bit gross, but it allows us to populate CallEffects without
3994// creating a bunch of accessors.  This kind is very localized, so the
3995// damage of this macro is limited.
3996#define createCallEffect(D, KIND)\
3997  ASTContext &Ctx = D->getASTContext();\
3998  LangOptions L = Ctx.getLangOpts();\
3999  RetainSummaryManager M(Ctx, L.GCOnly, L.ObjCAutoRefCount);\
4000  const RetainSummary *S = M.get ## KIND ## Summary(D);\
4001  CallEffects CE(S->getRetEffect());\
4002  CE.Receiver = S->getReceiverEffect();\
4003  unsigned N = D->param_size();\
4004  for (unsigned i = 0; i < N; ++i) {\
4005    CE.Args.push_back(S->getArg(i));\
4006  }
4007
4008CallEffects CallEffects::getEffect(const ObjCMethodDecl *MD) {
4009  createCallEffect(MD, Method);
4010  return CE;
4011}
4012
4013CallEffects CallEffects::getEffect(const FunctionDecl *FD) {
4014  createCallEffect(FD, Function);
4015  return CE;
4016}
4017
4018#undef createCallEffect
4019
4020} // end namespace objc_retain
4021} // end namespace ento
4022} // end namespace clang
4023