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