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