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