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