RetainCountChecker.cpp revision 1a45a5ff5d495cb6cd9a3d4d06317af79c0f634d
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  bool isTrackedLoc = false;
1197
1198  // Effects on the receiver.
1199  if (MD->getAttr<NSConsumesSelfAttr>()) {
1200    if (!GCEnabled)
1201      Template->setReceiverEffect(DecRefMsg);
1202  }
1203
1204  // Effects on the parameters.
1205  unsigned parm_idx = 0;
1206  for (ObjCMethodDecl::param_const_iterator
1207         pi=MD->param_begin(), pe=MD->param_end();
1208       pi != pe; ++pi, ++parm_idx) {
1209    const ParmVarDecl *pd = *pi;
1210    if (pd->getAttr<NSConsumedAttr>()) {
1211      if (!GCEnabled)
1212        Template->addArg(AF, parm_idx, DecRef);
1213    }
1214    else if(pd->getAttr<CFConsumedAttr>()) {
1215      Template->addArg(AF, parm_idx, DecRef);
1216    }
1217  }
1218
1219  // Determine if there is a special return effect for this method.
1220  if (cocoa::isCocoaObjectRef(MD->getResultType())) {
1221    if (MD->getAttr<NSReturnsRetainedAttr>()) {
1222      Template->setRetEffect(ObjCAllocRetE);
1223      return;
1224    }
1225    if (MD->getAttr<NSReturnsNotRetainedAttr>()) {
1226      Template->setRetEffect(RetEffect::MakeNotOwned(RetEffect::ObjC));
1227      return;
1228    }
1229
1230    isTrackedLoc = true;
1231  } else {
1232    isTrackedLoc = MD->getResultType()->getAs<PointerType>() != NULL;
1233  }
1234
1235  if (isTrackedLoc) {
1236    if (MD->getAttr<CFReturnsRetainedAttr>())
1237      Template->setRetEffect(RetEffect::MakeOwned(RetEffect::CF, true));
1238    else if (MD->getAttr<CFReturnsNotRetainedAttr>())
1239      Template->setRetEffect(RetEffect::MakeNotOwned(RetEffect::CF));
1240  }
1241}
1242
1243const RetainSummary *
1244RetainSummaryManager::getCommonMethodSummary(const ObjCMethodDecl *MD,
1245                                             Selector S, QualType RetTy) {
1246
1247  if (MD) {
1248    // Scan the method decl for 'void*' arguments.  These should be treated
1249    // as 'StopTracking' because they are often used with delegates.
1250    // Delegates are a frequent form of false positives with the retain
1251    // count checker.
1252    unsigned i = 0;
1253    for (ObjCMethodDecl::param_const_iterator I = MD->param_begin(),
1254         E = MD->param_end(); I != E; ++I, ++i)
1255      if (const ParmVarDecl *PD = *I) {
1256        QualType Ty = Ctx.getCanonicalType(PD->getType());
1257        if (Ty.getLocalUnqualifiedType() == Ctx.VoidPtrTy)
1258          ScratchArgs = AF.add(ScratchArgs, i, StopTracking);
1259      }
1260  }
1261
1262  // Any special effect for the receiver?
1263  ArgEffect ReceiverEff = DoNothing;
1264
1265  // If one of the arguments in the selector has the keyword 'delegate' we
1266  // should stop tracking the reference count for the receiver.  This is
1267  // because the reference count is quite possibly handled by a delegate
1268  // method.
1269  if (S.isKeywordSelector()) {
1270    const std::string &str = S.getAsString();
1271    assert(!str.empty());
1272    if (StrInStrNoCase(str, "delegate:") != StringRef::npos)
1273      ReceiverEff = StopTracking;
1274  }
1275
1276  // Look for methods that return an owned object.
1277  if (cocoa::isCocoaObjectRef(RetTy)) {
1278    // EXPERIMENTAL: assume the Cocoa conventions for all objects returned
1279    //  by instance methods.
1280    RetEffect E = cocoa::followsFundamentalRule(S, MD)
1281                  ? ObjCAllocRetE : RetEffect::MakeNotOwned(RetEffect::ObjC);
1282
1283    return getPersistentSummary(E, ReceiverEff, MayEscape);
1284  }
1285
1286  // Look for methods that return an owned core foundation object.
1287  if (coreFoundation::isCFObjectRef(RetTy)) {
1288    RetEffect E = cocoa::followsFundamentalRule(S, MD)
1289      ? RetEffect::MakeOwned(RetEffect::CF, true)
1290      : RetEffect::MakeNotOwned(RetEffect::CF);
1291
1292    return getPersistentSummary(E, ReceiverEff, MayEscape);
1293  }
1294
1295  if (ScratchArgs.isEmpty() && ReceiverEff == DoNothing)
1296    return getDefaultSummary();
1297
1298  return getPersistentSummary(RetEffect::MakeNoRet(), ReceiverEff, MayEscape);
1299}
1300
1301const RetainSummary *
1302RetainSummaryManager::getInstanceMethodSummary(const ObjCMessage &msg,
1303                                               ProgramStateRef state,
1304                                               const LocationContext *LC) {
1305
1306  // We need the type-information of the tracked receiver object
1307  // Retrieve it from the state.
1308  const Expr *Receiver = msg.getInstanceReceiver();
1309  const ObjCInterfaceDecl *ID = 0;
1310
1311  // FIXME: Is this really working as expected?  There are cases where
1312  //  we just use the 'ID' from the message expression.
1313  SVal receiverV;
1314
1315  if (Receiver) {
1316    receiverV = state->getSValAsScalarOrLoc(Receiver, LC);
1317
1318    // FIXME: Eventually replace the use of state->get<RefBindings> with
1319    // a generic API for reasoning about the Objective-C types of symbolic
1320    // objects.
1321    if (SymbolRef Sym = receiverV.getAsLocSymbol())
1322      if (const RefVal *T = state->get<RefBindings>(Sym))
1323        if (const ObjCObjectPointerType* PT =
1324            T->getType()->getAs<ObjCObjectPointerType>())
1325          ID = PT->getInterfaceDecl();
1326
1327    // FIXME: this is a hack.  This may or may not be the actual method
1328    //  that is called.
1329    if (!ID) {
1330      if (const ObjCObjectPointerType *PT =
1331          Receiver->getType()->getAs<ObjCObjectPointerType>())
1332        ID = PT->getInterfaceDecl();
1333    }
1334  } else {
1335    // FIXME: Hack for 'super'.
1336    ID = msg.getReceiverInterface();
1337  }
1338
1339  // FIXME: The receiver could be a reference to a class, meaning that
1340  //  we should use the class method.
1341  return getInstanceMethodSummary(msg, ID);
1342}
1343
1344const RetainSummary *
1345RetainSummaryManager::getInstanceMethodSummary(Selector S,
1346                                               IdentifierInfo *ClsName,
1347                                               const ObjCInterfaceDecl *ID,
1348                                               const ObjCMethodDecl *MD,
1349                                               QualType RetTy) {
1350
1351  // Look up a summary in our summary cache.
1352  const RetainSummary *Summ = ObjCMethodSummaries.find(ID, ClsName, S);
1353
1354  if (!Summ) {
1355    assert(ScratchArgs.isEmpty());
1356
1357    // "initXXX": pass-through for receiver.
1358    if (cocoa::deriveNamingConvention(S, MD) == cocoa::InitRule)
1359      Summ = getInitMethodSummary(RetTy);
1360    else
1361      Summ = getCommonMethodSummary(MD, S, RetTy);
1362
1363    // Annotations override defaults.
1364    updateSummaryFromAnnotations(Summ, MD);
1365
1366    // Memoize the summary.
1367    ObjCMethodSummaries[ObjCSummaryKey(ID, ClsName, S)] = Summ;
1368  }
1369
1370  return Summ;
1371}
1372
1373const RetainSummary *
1374RetainSummaryManager::getClassMethodSummary(Selector S, IdentifierInfo *ClsName,
1375                                            const ObjCInterfaceDecl *ID,
1376                                            const ObjCMethodDecl *MD,
1377                                            QualType RetTy) {
1378
1379  assert(ClsName && "Class name must be specified.");
1380  const RetainSummary *Summ = ObjCClassMethodSummaries.find(ID, ClsName, S);
1381
1382  if (!Summ) {
1383    Summ = getCommonMethodSummary(MD, S, RetTy);
1384
1385    // Annotations override defaults.
1386    updateSummaryFromAnnotations(Summ, MD);
1387
1388    // Memoize the summary.
1389    ObjCClassMethodSummaries[ObjCSummaryKey(ID, ClsName, S)] = Summ;
1390  }
1391
1392  return Summ;
1393}
1394
1395void RetainSummaryManager::InitializeClassMethodSummaries() {
1396  assert(ScratchArgs.isEmpty());
1397  // Create the [NSAssertionHandler currentHander] summary.
1398  addClassMethSummary("NSAssertionHandler", "currentHandler",
1399                getPersistentSummary(RetEffect::MakeNotOwned(RetEffect::ObjC)));
1400
1401  // Create the [NSAutoreleasePool addObject:] summary.
1402  ScratchArgs = AF.add(ScratchArgs, 0, Autorelease);
1403  addClassMethSummary("NSAutoreleasePool", "addObject",
1404                      getPersistentSummary(RetEffect::MakeNoRet(),
1405                                           DoNothing, Autorelease));
1406
1407  // Create the summaries for [NSObject performSelector...].  We treat
1408  // these as 'stop tracking' for the arguments because they are often
1409  // used for delegates that can release the object.  When we have better
1410  // inter-procedural analysis we can potentially do something better.  This
1411  // workaround is to remove false positives.
1412  const RetainSummary *Summ =
1413    getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, StopTracking);
1414  IdentifierInfo *NSObjectII = &Ctx.Idents.get("NSObject");
1415  addClsMethSummary(NSObjectII, Summ, "performSelector", "withObject",
1416                    "afterDelay", NULL);
1417  addClsMethSummary(NSObjectII, Summ, "performSelector", "withObject",
1418                    "afterDelay", "inModes", NULL);
1419  addClsMethSummary(NSObjectII, Summ, "performSelectorOnMainThread",
1420                    "withObject", "waitUntilDone", NULL);
1421  addClsMethSummary(NSObjectII, Summ, "performSelectorOnMainThread",
1422                    "withObject", "waitUntilDone", "modes", NULL);
1423  addClsMethSummary(NSObjectII, Summ, "performSelector", "onThread",
1424                    "withObject", "waitUntilDone", NULL);
1425  addClsMethSummary(NSObjectII, Summ, "performSelector", "onThread",
1426                    "withObject", "waitUntilDone", "modes", NULL);
1427  addClsMethSummary(NSObjectII, Summ, "performSelectorInBackground",
1428                    "withObject", NULL);
1429}
1430
1431void RetainSummaryManager::InitializeMethodSummaries() {
1432
1433  assert (ScratchArgs.isEmpty());
1434
1435  // Create the "init" selector.  It just acts as a pass-through for the
1436  // receiver.
1437  const RetainSummary *InitSumm = getPersistentSummary(ObjCInitRetE, DecRefMsg);
1438  addNSObjectMethSummary(GetNullarySelector("init", Ctx), InitSumm);
1439
1440  // awakeAfterUsingCoder: behaves basically like an 'init' method.  It
1441  // claims the receiver and returns a retained object.
1442  addNSObjectMethSummary(GetUnarySelector("awakeAfterUsingCoder", Ctx),
1443                         InitSumm);
1444
1445  // The next methods are allocators.
1446  const RetainSummary *AllocSumm = getPersistentSummary(ObjCAllocRetE);
1447  const RetainSummary *CFAllocSumm =
1448    getPersistentSummary(RetEffect::MakeOwned(RetEffect::CF, true));
1449
1450  // Create the "retain" selector.
1451  RetEffect NoRet = RetEffect::MakeNoRet();
1452  const RetainSummary *Summ = getPersistentSummary(NoRet, IncRefMsg);
1453  addNSObjectMethSummary(GetNullarySelector("retain", Ctx), Summ);
1454
1455  // Create the "release" selector.
1456  Summ = getPersistentSummary(NoRet, DecRefMsg);
1457  addNSObjectMethSummary(GetNullarySelector("release", Ctx), Summ);
1458
1459  // Create the "drain" selector.
1460  Summ = getPersistentSummary(NoRet, isGCEnabled() ? DoNothing : DecRef);
1461  addNSObjectMethSummary(GetNullarySelector("drain", Ctx), Summ);
1462
1463  // Create the -dealloc summary.
1464  Summ = getPersistentSummary(NoRet, Dealloc);
1465  addNSObjectMethSummary(GetNullarySelector("dealloc", Ctx), Summ);
1466
1467  // Create the "autorelease" selector.
1468  Summ = getPersistentSummary(NoRet, Autorelease);
1469  addNSObjectMethSummary(GetNullarySelector("autorelease", Ctx), Summ);
1470
1471  // Specially handle NSAutoreleasePool.
1472  addInstMethSummary("NSAutoreleasePool", "init",
1473                     getPersistentSummary(NoRet, NewAutoreleasePool));
1474
1475  // For NSWindow, allocated objects are (initially) self-owned.
1476  // FIXME: For now we opt for false negatives with NSWindow, as these objects
1477  //  self-own themselves.  However, they only do this once they are displayed.
1478  //  Thus, we need to track an NSWindow's display status.
1479  //  This is tracked in <rdar://problem/6062711>.
1480  //  See also http://llvm.org/bugs/show_bug.cgi?id=3714.
1481  const RetainSummary *NoTrackYet = getPersistentSummary(RetEffect::MakeNoRet(),
1482                                                   StopTracking,
1483                                                   StopTracking);
1484
1485  addClassMethSummary("NSWindow", "alloc", NoTrackYet);
1486
1487#if 0
1488  addInstMethSummary("NSWindow", NoTrackYet, "initWithContentRect",
1489                     "styleMask", "backing", "defer", NULL);
1490
1491  addInstMethSummary("NSWindow", NoTrackYet, "initWithContentRect",
1492                     "styleMask", "backing", "defer", "screen", NULL);
1493#endif
1494
1495  // For NSPanel (which subclasses NSWindow), allocated objects are not
1496  //  self-owned.
1497  // FIXME: For now we don't track NSPanels. object for the same reason
1498  //   as for NSWindow objects.
1499  addClassMethSummary("NSPanel", "alloc", NoTrackYet);
1500
1501#if 0
1502  addInstMethSummary("NSPanel", NoTrackYet, "initWithContentRect",
1503                     "styleMask", "backing", "defer", NULL);
1504
1505  addInstMethSummary("NSPanel", NoTrackYet, "initWithContentRect",
1506                     "styleMask", "backing", "defer", "screen", NULL);
1507#endif
1508
1509  // Don't track allocated autorelease pools yet, as it is okay to prematurely
1510  // exit a method.
1511  addClassMethSummary("NSAutoreleasePool", "alloc", NoTrackYet);
1512  addClassMethSummary("NSAutoreleasePool", "allocWithZone", NoTrackYet, false);
1513
1514  // Create summaries QCRenderer/QCView -createSnapShotImageOfType:
1515  addInstMethSummary("QCRenderer", AllocSumm,
1516                     "createSnapshotImageOfType", NULL);
1517  addInstMethSummary("QCView", AllocSumm,
1518                     "createSnapshotImageOfType", NULL);
1519
1520  // Create summaries for CIContext, 'createCGImage' and
1521  // 'createCGLayerWithSize'.  These objects are CF objects, and are not
1522  // automatically garbage collected.
1523  addInstMethSummary("CIContext", CFAllocSumm,
1524                     "createCGImage", "fromRect", NULL);
1525  addInstMethSummary("CIContext", CFAllocSumm,
1526                     "createCGImage", "fromRect", "format", "colorSpace", NULL);
1527  addInstMethSummary("CIContext", CFAllocSumm, "createCGLayerWithSize",
1528           "info", NULL);
1529}
1530
1531//===----------------------------------------------------------------------===//
1532// AutoreleaseBindings - State used to track objects in autorelease pools.
1533//===----------------------------------------------------------------------===//
1534
1535typedef llvm::ImmutableMap<SymbolRef, unsigned> ARCounts;
1536typedef llvm::ImmutableMap<SymbolRef, ARCounts> ARPoolContents;
1537typedef llvm::ImmutableList<SymbolRef> ARStack;
1538
1539static int AutoRCIndex = 0;
1540static int AutoRBIndex = 0;
1541
1542namespace { class AutoreleasePoolContents {}; }
1543namespace { class AutoreleaseStack {}; }
1544
1545namespace clang {
1546namespace ento {
1547template<> struct ProgramStateTrait<AutoreleaseStack>
1548  : public ProgramStatePartialTrait<ARStack> {
1549  static inline void *GDMIndex() { return &AutoRBIndex; }
1550};
1551
1552template<> struct ProgramStateTrait<AutoreleasePoolContents>
1553  : public ProgramStatePartialTrait<ARPoolContents> {
1554  static inline void *GDMIndex() { return &AutoRCIndex; }
1555};
1556} // end GR namespace
1557} // end clang namespace
1558
1559static SymbolRef GetCurrentAutoreleasePool(ProgramStateRef state) {
1560  ARStack stack = state->get<AutoreleaseStack>();
1561  return stack.isEmpty() ? SymbolRef() : stack.getHead();
1562}
1563
1564static ProgramStateRef
1565SendAutorelease(ProgramStateRef state,
1566                ARCounts::Factory &F,
1567                SymbolRef sym) {
1568  SymbolRef pool = GetCurrentAutoreleasePool(state);
1569  const ARCounts *cnts = state->get<AutoreleasePoolContents>(pool);
1570  ARCounts newCnts(0);
1571
1572  if (cnts) {
1573    const unsigned *cnt = (*cnts).lookup(sym);
1574    newCnts = F.add(*cnts, sym, cnt ? *cnt  + 1 : 1);
1575  }
1576  else
1577    newCnts = F.add(F.getEmptyMap(), sym, 1);
1578
1579  return state->set<AutoreleasePoolContents>(pool, newCnts);
1580}
1581
1582//===----------------------------------------------------------------------===//
1583// Error reporting.
1584//===----------------------------------------------------------------------===//
1585namespace {
1586  typedef llvm::DenseMap<const ExplodedNode *, const RetainSummary *>
1587    SummaryLogTy;
1588
1589  //===-------------===//
1590  // Bug Descriptions. //
1591  //===-------------===//
1592
1593  class CFRefBug : public BugType {
1594  protected:
1595    CFRefBug(StringRef name)
1596    : BugType(name, "Memory (Core Foundation/Objective-C)") {}
1597  public:
1598
1599    // FIXME: Eventually remove.
1600    virtual const char *getDescription() const = 0;
1601
1602    virtual bool isLeak() const { return false; }
1603  };
1604
1605  class UseAfterRelease : public CFRefBug {
1606  public:
1607    UseAfterRelease() : CFRefBug("Use-after-release") {}
1608
1609    const char *getDescription() const {
1610      return "Reference-counted object is used after it is released";
1611    }
1612  };
1613
1614  class BadRelease : public CFRefBug {
1615  public:
1616    BadRelease() : CFRefBug("Bad release") {}
1617
1618    const char *getDescription() const {
1619      return "Incorrect decrement of the reference count of an object that is "
1620             "not owned at this point by the caller";
1621    }
1622  };
1623
1624  class DeallocGC : public CFRefBug {
1625  public:
1626    DeallocGC()
1627    : CFRefBug("-dealloc called while using garbage collection") {}
1628
1629    const char *getDescription() const {
1630      return "-dealloc called while using garbage collection";
1631    }
1632  };
1633
1634  class DeallocNotOwned : public CFRefBug {
1635  public:
1636    DeallocNotOwned()
1637    : CFRefBug("-dealloc sent to non-exclusively owned object") {}
1638
1639    const char *getDescription() const {
1640      return "-dealloc sent to object that may be referenced elsewhere";
1641    }
1642  };
1643
1644  class OverAutorelease : public CFRefBug {
1645  public:
1646    OverAutorelease()
1647    : CFRefBug("Object sent -autorelease too many times") {}
1648
1649    const char *getDescription() const {
1650      return "Object sent -autorelease too many times";
1651    }
1652  };
1653
1654  class ReturnedNotOwnedForOwned : public CFRefBug {
1655  public:
1656    ReturnedNotOwnedForOwned()
1657    : CFRefBug("Method should return an owned object") {}
1658
1659    const char *getDescription() const {
1660      return "Object with a +0 retain count returned to caller where a +1 "
1661             "(owning) retain count is expected";
1662    }
1663  };
1664
1665  class Leak : public CFRefBug {
1666    const bool isReturn;
1667  protected:
1668    Leak(StringRef name, bool isRet)
1669    : CFRefBug(name), isReturn(isRet) {
1670      // Leaks should not be reported if they are post-dominated by a sink.
1671      setSuppressOnSink(true);
1672    }
1673  public:
1674
1675    const char *getDescription() const { return ""; }
1676
1677    bool isLeak() const { return true; }
1678  };
1679
1680  class LeakAtReturn : public Leak {
1681  public:
1682    LeakAtReturn(StringRef name)
1683    : Leak(name, true) {}
1684  };
1685
1686  class LeakWithinFunction : public Leak {
1687  public:
1688    LeakWithinFunction(StringRef name)
1689    : Leak(name, false) {}
1690  };
1691
1692  //===---------===//
1693  // Bug Reports.  //
1694  //===---------===//
1695
1696  class CFRefReportVisitor : public BugReporterVisitor {
1697  protected:
1698    SymbolRef Sym;
1699    const SummaryLogTy &SummaryLog;
1700    bool GCEnabled;
1701
1702  public:
1703    CFRefReportVisitor(SymbolRef sym, bool gcEnabled, const SummaryLogTy &log)
1704       : Sym(sym), SummaryLog(log), GCEnabled(gcEnabled) {}
1705
1706    virtual void Profile(llvm::FoldingSetNodeID &ID) const {
1707      static int x = 0;
1708      ID.AddPointer(&x);
1709      ID.AddPointer(Sym);
1710    }
1711
1712    virtual PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
1713                                           const ExplodedNode *PrevN,
1714                                           BugReporterContext &BRC,
1715                                           BugReport &BR);
1716
1717    virtual PathDiagnosticPiece *getEndPath(BugReporterContext &BRC,
1718                                            const ExplodedNode *N,
1719                                            BugReport &BR);
1720  };
1721
1722  class CFRefLeakReportVisitor : public CFRefReportVisitor {
1723  public:
1724    CFRefLeakReportVisitor(SymbolRef sym, bool GCEnabled,
1725                           const SummaryLogTy &log)
1726       : CFRefReportVisitor(sym, GCEnabled, log) {}
1727
1728    PathDiagnosticPiece *getEndPath(BugReporterContext &BRC,
1729                                    const ExplodedNode *N,
1730                                    BugReport &BR);
1731  };
1732
1733  class CFRefReport : public BugReport {
1734    void addGCModeDescription(const LangOptions &LOpts, bool GCEnabled);
1735
1736  public:
1737    CFRefReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1738                const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1739                bool registerVisitor = true)
1740      : BugReport(D, D.getDescription(), n) {
1741      if (registerVisitor)
1742        addVisitor(new CFRefReportVisitor(sym, GCEnabled, Log));
1743      addGCModeDescription(LOpts, GCEnabled);
1744    }
1745
1746    CFRefReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1747                const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1748                StringRef endText)
1749      : BugReport(D, D.getDescription(), endText, n) {
1750      addVisitor(new CFRefReportVisitor(sym, GCEnabled, Log));
1751      addGCModeDescription(LOpts, GCEnabled);
1752    }
1753
1754    virtual std::pair<ranges_iterator, ranges_iterator> getRanges() {
1755      const CFRefBug& BugTy = static_cast<CFRefBug&>(getBugType());
1756      if (!BugTy.isLeak())
1757        return BugReport::getRanges();
1758      else
1759        return std::make_pair(ranges_iterator(), ranges_iterator());
1760    }
1761  };
1762
1763  class CFRefLeakReport : public CFRefReport {
1764    const MemRegion* AllocBinding;
1765
1766  public:
1767    CFRefLeakReport(CFRefBug &D, const LangOptions &LOpts, bool GCEnabled,
1768                    const SummaryLogTy &Log, ExplodedNode *n, SymbolRef sym,
1769                    CheckerContext &Ctx);
1770
1771    PathDiagnosticLocation getLocation(const SourceManager &SM) const {
1772      assert(Location.isValid());
1773      return Location;
1774    }
1775  };
1776} // end anonymous namespace
1777
1778void CFRefReport::addGCModeDescription(const LangOptions &LOpts,
1779                                       bool GCEnabled) {
1780  const char *GCModeDescription = 0;
1781
1782  switch (LOpts.getGC()) {
1783  case LangOptions::GCOnly:
1784    assert(GCEnabled);
1785    GCModeDescription = "Code is compiled to only use garbage collection";
1786    break;
1787
1788  case LangOptions::NonGC:
1789    assert(!GCEnabled);
1790    GCModeDescription = "Code is compiled to use reference counts";
1791    break;
1792
1793  case LangOptions::HybridGC:
1794    if (GCEnabled) {
1795      GCModeDescription = "Code is compiled to use either garbage collection "
1796                          "(GC) or reference counts (non-GC).  The bug occurs "
1797                          "with GC enabled";
1798      break;
1799    } else {
1800      GCModeDescription = "Code is compiled to use either garbage collection "
1801                          "(GC) or reference counts (non-GC).  The bug occurs "
1802                          "in non-GC mode";
1803      break;
1804    }
1805  }
1806
1807  assert(GCModeDescription && "invalid/unknown GC mode");
1808  addExtraText(GCModeDescription);
1809}
1810
1811// FIXME: This should be a method on SmallVector.
1812static inline bool contains(const SmallVectorImpl<ArgEffect>& V,
1813                            ArgEffect X) {
1814  for (SmallVectorImpl<ArgEffect>::const_iterator I=V.begin(), E=V.end();
1815       I!=E; ++I)
1816    if (*I == X) return true;
1817
1818  return false;
1819}
1820
1821static bool isPropertyAccess(const Stmt *S, ParentMap &PM) {
1822  unsigned maxDepth = 4;
1823  while (S && maxDepth) {
1824    if (const PseudoObjectExpr *PO = dyn_cast<PseudoObjectExpr>(S)) {
1825      if (!isa<ObjCMessageExpr>(PO->getSyntacticForm()))
1826        return true;
1827      return false;
1828    }
1829    S = PM.getParent(S);
1830    --maxDepth;
1831  }
1832  return false;
1833}
1834
1835PathDiagnosticPiece *CFRefReportVisitor::VisitNode(const ExplodedNode *N,
1836                                                   const ExplodedNode *PrevN,
1837                                                   BugReporterContext &BRC,
1838                                                   BugReport &BR) {
1839
1840  if (!isa<StmtPoint>(N->getLocation()))
1841    return NULL;
1842
1843  // Check if the type state has changed.
1844  ProgramStateRef PrevSt = PrevN->getState();
1845  ProgramStateRef CurrSt = N->getState();
1846  const LocationContext *LCtx = N->getLocationContext();
1847
1848  const RefVal* CurrT = CurrSt->get<RefBindings>(Sym);
1849  if (!CurrT) return NULL;
1850
1851  const RefVal &CurrV = *CurrT;
1852  const RefVal *PrevT = PrevSt->get<RefBindings>(Sym);
1853
1854  // Create a string buffer to constain all the useful things we want
1855  // to tell the user.
1856  std::string sbuf;
1857  llvm::raw_string_ostream os(sbuf);
1858
1859  // This is the allocation site since the previous node had no bindings
1860  // for this symbol.
1861  if (!PrevT) {
1862    const Stmt *S = cast<StmtPoint>(N->getLocation()).getStmt();
1863
1864    if (isa<ObjCArrayLiteral>(S)) {
1865      os << "NSArray literal is an object with a +0 retain count";
1866    }
1867    else if (isa<ObjCDictionaryLiteral>(S)) {
1868      os << "NSDictionary literal is an object with a +0 retain count";
1869    }
1870    else {
1871      if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
1872        // Get the name of the callee (if it is available).
1873        SVal X = CurrSt->getSValAsScalarOrLoc(CE->getCallee(), LCtx);
1874        if (const FunctionDecl *FD = X.getAsFunctionDecl())
1875          os << "Call to function '" << *FD << '\'';
1876        else
1877          os << "function call";
1878      }
1879      else {
1880        assert(isa<ObjCMessageExpr>(S));
1881        // The message expression may have between written directly or as
1882        // a property access.  Lazily determine which case we are looking at.
1883        os << (isPropertyAccess(S, N->getParentMap()) ? "Property" : "Method");
1884      }
1885
1886      if (CurrV.getObjKind() == RetEffect::CF) {
1887        os << " returns a Core Foundation object with a ";
1888      }
1889      else {
1890        assert (CurrV.getObjKind() == RetEffect::ObjC);
1891        os << " returns an Objective-C object with a ";
1892      }
1893
1894      if (CurrV.isOwned()) {
1895        os << "+1 retain count";
1896
1897        if (GCEnabled) {
1898          assert(CurrV.getObjKind() == RetEffect::CF);
1899          os << ".  "
1900          "Core Foundation objects are not automatically garbage collected.";
1901        }
1902      }
1903      else {
1904        assert (CurrV.isNotOwned());
1905        os << "+0 retain count";
1906      }
1907    }
1908
1909    PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
1910                                  N->getLocationContext());
1911    return new PathDiagnosticEventPiece(Pos, os.str());
1912  }
1913
1914  // Gather up the effects that were performed on the object at this
1915  // program point
1916  SmallVector<ArgEffect, 2> AEffects;
1917
1918  const ExplodedNode *OrigNode = BRC.getNodeResolver().getOriginalNode(N);
1919  if (const RetainSummary *Summ = SummaryLog.lookup(OrigNode)) {
1920    // We only have summaries attached to nodes after evaluating CallExpr and
1921    // ObjCMessageExprs.
1922    const Stmt *S = cast<StmtPoint>(N->getLocation()).getStmt();
1923
1924    if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
1925      // Iterate through the parameter expressions and see if the symbol
1926      // was ever passed as an argument.
1927      unsigned i = 0;
1928
1929      for (CallExpr::const_arg_iterator AI=CE->arg_begin(), AE=CE->arg_end();
1930           AI!=AE; ++AI, ++i) {
1931
1932        // Retrieve the value of the argument.  Is it the symbol
1933        // we are interested in?
1934        if (CurrSt->getSValAsScalarOrLoc(*AI, LCtx).getAsLocSymbol() != Sym)
1935          continue;
1936
1937        // We have an argument.  Get the effect!
1938        AEffects.push_back(Summ->getArg(i));
1939      }
1940    }
1941    else if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(S)) {
1942      if (const Expr *receiver = ME->getInstanceReceiver())
1943        if (CurrSt->getSValAsScalarOrLoc(receiver, LCtx)
1944              .getAsLocSymbol() == Sym) {
1945          // The symbol we are tracking is the receiver.
1946          AEffects.push_back(Summ->getReceiverEffect());
1947        }
1948    }
1949  }
1950
1951  do {
1952    // Get the previous type state.
1953    RefVal PrevV = *PrevT;
1954
1955    // Specially handle -dealloc.
1956    if (!GCEnabled && contains(AEffects, Dealloc)) {
1957      // Determine if the object's reference count was pushed to zero.
1958      assert(!(PrevV == CurrV) && "The typestate *must* have changed.");
1959      // We may not have transitioned to 'release' if we hit an error.
1960      // This case is handled elsewhere.
1961      if (CurrV.getKind() == RefVal::Released) {
1962        assert(CurrV.getCombinedCounts() == 0);
1963        os << "Object released by directly sending the '-dealloc' message";
1964        break;
1965      }
1966    }
1967
1968    // Specially handle CFMakeCollectable and friends.
1969    if (contains(AEffects, MakeCollectable)) {
1970      // Get the name of the function.
1971      const Stmt *S = cast<StmtPoint>(N->getLocation()).getStmt();
1972      SVal X =
1973        CurrSt->getSValAsScalarOrLoc(cast<CallExpr>(S)->getCallee(), LCtx);
1974      const FunctionDecl *FD = X.getAsFunctionDecl();
1975
1976      if (GCEnabled) {
1977        // Determine if the object's reference count was pushed to zero.
1978        assert(!(PrevV == CurrV) && "The typestate *must* have changed.");
1979
1980        os << "In GC mode a call to '" << *FD
1981        <<  "' decrements an object's retain count and registers the "
1982        "object with the garbage collector. ";
1983
1984        if (CurrV.getKind() == RefVal::Released) {
1985          assert(CurrV.getCount() == 0);
1986          os << "Since it now has a 0 retain count the object can be "
1987          "automatically collected by the garbage collector.";
1988        }
1989        else
1990          os << "An object must have a 0 retain count to be garbage collected. "
1991          "After this call its retain count is +" << CurrV.getCount()
1992          << '.';
1993      }
1994      else
1995        os << "When GC is not enabled a call to '" << *FD
1996        << "' has no effect on its argument.";
1997
1998      // Nothing more to say.
1999      break;
2000    }
2001
2002    // Determine if the typestate has changed.
2003    if (!(PrevV == CurrV))
2004      switch (CurrV.getKind()) {
2005        case RefVal::Owned:
2006        case RefVal::NotOwned:
2007
2008          if (PrevV.getCount() == CurrV.getCount()) {
2009            // Did an autorelease message get sent?
2010            if (PrevV.getAutoreleaseCount() == CurrV.getAutoreleaseCount())
2011              return 0;
2012
2013            assert(PrevV.getAutoreleaseCount() < CurrV.getAutoreleaseCount());
2014            os << "Object sent -autorelease message";
2015            break;
2016          }
2017
2018          if (PrevV.getCount() > CurrV.getCount())
2019            os << "Reference count decremented.";
2020          else
2021            os << "Reference count incremented.";
2022
2023          if (unsigned Count = CurrV.getCount())
2024            os << " The object now has a +" << Count << " retain count.";
2025
2026          if (PrevV.getKind() == RefVal::Released) {
2027            assert(GCEnabled && CurrV.getCount() > 0);
2028            os << " The object is not eligible for garbage collection until the "
2029            "retain count reaches 0 again.";
2030          }
2031
2032          break;
2033
2034        case RefVal::Released:
2035          os << "Object released.";
2036          break;
2037
2038        case RefVal::ReturnedOwned:
2039          os << "Object returned to caller as an owning reference (single retain "
2040          "count transferred to caller)";
2041          break;
2042
2043        case RefVal::ReturnedNotOwned:
2044          os << "Object returned to caller with a +0 retain count";
2045          break;
2046
2047        default:
2048          return NULL;
2049      }
2050
2051    // Emit any remaining diagnostics for the argument effects (if any).
2052    for (SmallVectorImpl<ArgEffect>::iterator I=AEffects.begin(),
2053         E=AEffects.end(); I != E; ++I) {
2054
2055      // A bunch of things have alternate behavior under GC.
2056      if (GCEnabled)
2057        switch (*I) {
2058          default: break;
2059          case Autorelease:
2060            os << "In GC mode an 'autorelease' has no effect.";
2061            continue;
2062          case IncRefMsg:
2063            os << "In GC mode the 'retain' message has no effect.";
2064            continue;
2065          case DecRefMsg:
2066            os << "In GC mode the 'release' message has no effect.";
2067            continue;
2068        }
2069    }
2070  } while (0);
2071
2072  if (os.str().empty())
2073    return 0; // We have nothing to say!
2074
2075  const Stmt *S = cast<StmtPoint>(N->getLocation()).getStmt();
2076  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
2077                                N->getLocationContext());
2078  PathDiagnosticPiece *P = new PathDiagnosticEventPiece(Pos, os.str());
2079
2080  // Add the range by scanning the children of the statement for any bindings
2081  // to Sym.
2082  for (Stmt::const_child_iterator I = S->child_begin(), E = S->child_end();
2083       I!=E; ++I)
2084    if (const Expr *Exp = dyn_cast_or_null<Expr>(*I))
2085      if (CurrSt->getSValAsScalarOrLoc(Exp, LCtx).getAsLocSymbol() == Sym) {
2086        P->addRange(Exp->getSourceRange());
2087        break;
2088      }
2089
2090  return P;
2091}
2092
2093namespace {
2094  class FindUniqueBinding :
2095  public StoreManager::BindingsHandler {
2096    SymbolRef Sym;
2097    const MemRegion* Binding;
2098    bool First;
2099
2100  public:
2101    FindUniqueBinding(SymbolRef sym) : Sym(sym), Binding(0), First(true) {}
2102
2103    bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
2104                       SVal val) {
2105
2106      SymbolRef SymV = val.getAsSymbol();
2107      if (!SymV || SymV != Sym)
2108        return true;
2109
2110      if (Binding) {
2111        First = false;
2112        return false;
2113      }
2114      else
2115        Binding = R;
2116
2117      return true;
2118    }
2119
2120    operator bool() { return First && Binding; }
2121    const MemRegion *getRegion() { return Binding; }
2122  };
2123}
2124
2125// Find the first node in the current function context that referred to the
2126// tracked symbol and the memory location that value was stored to. Note, the
2127// value is only reported if the allocation occurred in the same function as
2128// the leak.
2129static std::pair<const ExplodedNode*,const MemRegion*>
2130GetAllocationSite(ProgramStateManager& StateMgr, const ExplodedNode *N,
2131                  SymbolRef Sym) {
2132  const ExplodedNode *Last = N;
2133  const MemRegion* FirstBinding = 0;
2134  const LocationContext *LeakContext = N->getLocationContext();
2135
2136  while (N) {
2137    ProgramStateRef St = N->getState();
2138    RefBindings B = St->get<RefBindings>();
2139
2140    if (!B.lookup(Sym))
2141      break;
2142
2143    FindUniqueBinding FB(Sym);
2144    StateMgr.iterBindings(St, FB);
2145    if (FB) FirstBinding = FB.getRegion();
2146
2147    // Allocation node, is the last node in the current context in which the
2148    // symbol was tracked.
2149    if (N->getLocationContext() == LeakContext)
2150      Last = N;
2151
2152    N = N->pred_empty() ? NULL : *(N->pred_begin());
2153  }
2154
2155  // If allocation happened in a function different from the leak node context,
2156  // do not report the binding.
2157  if (N->getLocationContext() != LeakContext) {
2158    FirstBinding = 0;
2159  }
2160
2161  return std::make_pair(Last, FirstBinding);
2162}
2163
2164PathDiagnosticPiece*
2165CFRefReportVisitor::getEndPath(BugReporterContext &BRC,
2166                               const ExplodedNode *EndN,
2167                               BugReport &BR) {
2168  // Tell the BugReporterContext to report cases when the tracked symbol is
2169  // assigned to different variables, etc.
2170  BRC.addNotableSymbol(Sym);
2171  return BugReporterVisitor::getDefaultEndPath(BRC, EndN, BR);
2172}
2173
2174PathDiagnosticPiece*
2175CFRefLeakReportVisitor::getEndPath(BugReporterContext &BRC,
2176                                   const ExplodedNode *EndN,
2177                                   BugReport &BR) {
2178
2179  // Tell the BugReporterContext to report cases when the tracked symbol is
2180  // assigned to different variables, etc.
2181  BRC.addNotableSymbol(Sym);
2182
2183  // We are reporting a leak.  Walk up the graph to get to the first node where
2184  // the symbol appeared, and also get the first VarDecl that tracked object
2185  // is stored to.
2186  const ExplodedNode *AllocNode = 0;
2187  const MemRegion* FirstBinding = 0;
2188
2189  llvm::tie(AllocNode, FirstBinding) =
2190    GetAllocationSite(BRC.getStateManager(), EndN, Sym);
2191
2192  SourceManager& SM = BRC.getSourceManager();
2193
2194  // Compute an actual location for the leak.  Sometimes a leak doesn't
2195  // occur at an actual statement (e.g., transition between blocks; end
2196  // of function) so we need to walk the graph and compute a real location.
2197  const ExplodedNode *LeakN = EndN;
2198  PathDiagnosticLocation L = PathDiagnosticLocation::createEndOfPath(LeakN, SM);
2199
2200  std::string sbuf;
2201  llvm::raw_string_ostream os(sbuf);
2202
2203  os << "Object leaked: ";
2204
2205  if (FirstBinding) {
2206    os << "object allocated and stored into '"
2207       << FirstBinding->getString() << '\'';
2208  }
2209  else
2210    os << "allocated object";
2211
2212  // Get the retain count.
2213  const RefVal* RV = EndN->getState()->get<RefBindings>(Sym);
2214
2215  if (RV->getKind() == RefVal::ErrorLeakReturned) {
2216    // FIXME: Per comments in rdar://6320065, "create" only applies to CF
2217    // objects.  Only "copy", "alloc", "retain" and "new" transfer ownership
2218    // to the caller for NS objects.
2219    const Decl *D = &EndN->getCodeDecl();
2220    if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
2221      os << " is returned from a method whose name ('"
2222         << MD->getSelector().getAsString()
2223         << "') does not start with 'copy', 'mutableCopy', 'alloc' or 'new'."
2224            "  This violates the naming convention rules"
2225            " given in the Memory Management Guide for Cocoa";
2226    }
2227    else {
2228      const FunctionDecl *FD = cast<FunctionDecl>(D);
2229      os << " is returned from a function whose name ('"
2230         << *FD
2231         << "') does not contain 'Copy' or 'Create'.  This violates the naming"
2232            " convention rules given in the Memory Management Guide for Core"
2233            " Foundation";
2234    }
2235  }
2236  else if (RV->getKind() == RefVal::ErrorGCLeakReturned) {
2237    ObjCMethodDecl &MD = cast<ObjCMethodDecl>(EndN->getCodeDecl());
2238    os << " and returned from method '" << MD.getSelector().getAsString()
2239       << "' is potentially leaked when using garbage collection.  Callers "
2240          "of this method do not expect a returned object with a +1 retain "
2241          "count since they expect the object to be managed by the garbage "
2242          "collector";
2243  }
2244  else
2245    os << " is not referenced later in this execution path and has a retain "
2246          "count of +" << RV->getCount();
2247
2248  return new PathDiagnosticEventPiece(L, os.str());
2249}
2250
2251CFRefLeakReport::CFRefLeakReport(CFRefBug &D, const LangOptions &LOpts,
2252                                 bool GCEnabled, const SummaryLogTy &Log,
2253                                 ExplodedNode *n, SymbolRef sym,
2254                                 CheckerContext &Ctx)
2255: CFRefReport(D, LOpts, GCEnabled, Log, n, sym, false) {
2256
2257  // Most bug reports are cached at the location where they occurred.
2258  // With leaks, we want to unique them by the location where they were
2259  // allocated, and only report a single path.  To do this, we need to find
2260  // the allocation site of a piece of tracked memory, which we do via a
2261  // call to GetAllocationSite.  This will walk the ExplodedGraph backwards.
2262  // Note that this is *not* the trimmed graph; we are guaranteed, however,
2263  // that all ancestor nodes that represent the allocation site have the
2264  // same SourceLocation.
2265  const ExplodedNode *AllocNode = 0;
2266
2267  const SourceManager& SMgr = Ctx.getSourceManager();
2268
2269  llvm::tie(AllocNode, AllocBinding) =  // Set AllocBinding.
2270    GetAllocationSite(Ctx.getStateManager(), getErrorNode(), sym);
2271
2272  // Get the SourceLocation for the allocation site.
2273  ProgramPoint P = AllocNode->getLocation();
2274  const Stmt *AllocStmt = cast<PostStmt>(P).getStmt();
2275  Location = PathDiagnosticLocation::createBegin(AllocStmt, SMgr,
2276                                                  n->getLocationContext());
2277  // Fill in the description of the bug.
2278  Description.clear();
2279  llvm::raw_string_ostream os(Description);
2280  os << "Potential leak ";
2281  if (GCEnabled)
2282    os << "(when using garbage collection) ";
2283  os << "of an object";
2284
2285  // FIXME: AllocBinding doesn't get populated for RegionStore yet.
2286  if (AllocBinding)
2287    os << " stored into '" << AllocBinding->getString() << '\'';
2288
2289  addVisitor(new CFRefLeakReportVisitor(sym, GCEnabled, Log));
2290}
2291
2292//===----------------------------------------------------------------------===//
2293// Main checker logic.
2294//===----------------------------------------------------------------------===//
2295
2296namespace {
2297class RetainCountChecker
2298  : public Checker< check::Bind,
2299                    check::DeadSymbols,
2300                    check::EndAnalysis,
2301                    check::EndPath,
2302                    check::PostStmt<BlockExpr>,
2303                    check::PostStmt<CastExpr>,
2304                    check::PostStmt<CallExpr>,
2305                    check::PostStmt<CXXConstructExpr>,
2306                    check::PostStmt<ObjCArrayLiteral>,
2307                    check::PostStmt<ObjCDictionaryLiteral>,
2308                    check::PostObjCMessage,
2309                    check::PreStmt<ReturnStmt>,
2310                    check::RegionChanges,
2311                    eval::Assume,
2312                    eval::Call > {
2313  mutable OwningPtr<CFRefBug> useAfterRelease, releaseNotOwned;
2314  mutable OwningPtr<CFRefBug> deallocGC, deallocNotOwned;
2315  mutable OwningPtr<CFRefBug> overAutorelease, returnNotOwnedForOwned;
2316  mutable OwningPtr<CFRefBug> leakWithinFunction, leakAtReturn;
2317  mutable OwningPtr<CFRefBug> leakWithinFunctionGC, leakAtReturnGC;
2318
2319  typedef llvm::DenseMap<SymbolRef, const SimpleProgramPointTag *> SymbolTagMap;
2320
2321  // This map is only used to ensure proper deletion of any allocated tags.
2322  mutable SymbolTagMap DeadSymbolTags;
2323
2324  mutable OwningPtr<RetainSummaryManager> Summaries;
2325  mutable OwningPtr<RetainSummaryManager> SummariesGC;
2326
2327  mutable ARCounts::Factory ARCountFactory;
2328
2329  mutable SummaryLogTy SummaryLog;
2330  mutable bool ShouldResetSummaryLog;
2331
2332public:
2333  RetainCountChecker() : ShouldResetSummaryLog(false) {}
2334
2335  virtual ~RetainCountChecker() {
2336    DeleteContainerSeconds(DeadSymbolTags);
2337  }
2338
2339  void checkEndAnalysis(ExplodedGraph &G, BugReporter &BR,
2340                        ExprEngine &Eng) const {
2341    // FIXME: This is a hack to make sure the summary log gets cleared between
2342    // analyses of different code bodies.
2343    //
2344    // Why is this necessary? Because a checker's lifetime is tied to a
2345    // translation unit, but an ExplodedGraph's lifetime is just a code body.
2346    // Once in a blue moon, a new ExplodedNode will have the same address as an
2347    // old one with an associated summary, and the bug report visitor gets very
2348    // confused. (To make things worse, the summary lifetime is currently also
2349    // tied to a code body, so we get a crash instead of incorrect results.)
2350    //
2351    // Why is this a bad solution? Because if the lifetime of the ExplodedGraph
2352    // changes, things will start going wrong again. Really the lifetime of this
2353    // log needs to be tied to either the specific nodes in it or the entire
2354    // ExplodedGraph, not to a specific part of the code being analyzed.
2355    //
2356    // (Also, having stateful local data means that the same checker can't be
2357    // used from multiple threads, but a lot of checkers have incorrect
2358    // assumptions about that anyway. So that wasn't a priority at the time of
2359    // this fix.)
2360    //
2361    // This happens at the end of analysis, but bug reports are emitted /after/
2362    // this point. So we can't just clear the summary log now. Instead, we mark
2363    // that the next time we access the summary log, it should be cleared.
2364
2365    // If we never reset the summary log during /this/ code body analysis,
2366    // there were no new summaries. There might still have been summaries from
2367    // the /last/ analysis, so clear them out to make sure the bug report
2368    // visitors don't get confused.
2369    if (ShouldResetSummaryLog)
2370      SummaryLog.clear();
2371
2372    ShouldResetSummaryLog = !SummaryLog.empty();
2373  }
2374
2375  CFRefBug *getLeakWithinFunctionBug(const LangOptions &LOpts,
2376                                     bool GCEnabled) const {
2377    if (GCEnabled) {
2378      if (!leakWithinFunctionGC)
2379        leakWithinFunctionGC.reset(new LeakWithinFunction("Leak of object when "
2380                                                          "using garbage "
2381                                                          "collection"));
2382      return leakWithinFunctionGC.get();
2383    } else {
2384      if (!leakWithinFunction) {
2385        if (LOpts.getGC() == LangOptions::HybridGC) {
2386          leakWithinFunction.reset(new LeakWithinFunction("Leak of object when "
2387                                                          "not using garbage "
2388                                                          "collection (GC) in "
2389                                                          "dual GC/non-GC "
2390                                                          "code"));
2391        } else {
2392          leakWithinFunction.reset(new LeakWithinFunction("Leak"));
2393        }
2394      }
2395      return leakWithinFunction.get();
2396    }
2397  }
2398
2399  CFRefBug *getLeakAtReturnBug(const LangOptions &LOpts, bool GCEnabled) const {
2400    if (GCEnabled) {
2401      if (!leakAtReturnGC)
2402        leakAtReturnGC.reset(new LeakAtReturn("Leak of returned object when "
2403                                              "using garbage collection"));
2404      return leakAtReturnGC.get();
2405    } else {
2406      if (!leakAtReturn) {
2407        if (LOpts.getGC() == LangOptions::HybridGC) {
2408          leakAtReturn.reset(new LeakAtReturn("Leak of returned object when "
2409                                              "not using garbage collection "
2410                                              "(GC) in dual GC/non-GC code"));
2411        } else {
2412          leakAtReturn.reset(new LeakAtReturn("Leak of returned object"));
2413        }
2414      }
2415      return leakAtReturn.get();
2416    }
2417  }
2418
2419  RetainSummaryManager &getSummaryManager(ASTContext &Ctx,
2420                                          bool GCEnabled) const {
2421    // FIXME: We don't support ARC being turned on and off during one analysis.
2422    // (nor, for that matter, do we support changing ASTContexts)
2423    bool ARCEnabled = (bool)Ctx.getLangOptions().ObjCAutoRefCount;
2424    if (GCEnabled) {
2425      if (!SummariesGC)
2426        SummariesGC.reset(new RetainSummaryManager(Ctx, true, ARCEnabled));
2427      else
2428        assert(SummariesGC->isARCEnabled() == ARCEnabled);
2429      return *SummariesGC;
2430    } else {
2431      if (!Summaries)
2432        Summaries.reset(new RetainSummaryManager(Ctx, false, ARCEnabled));
2433      else
2434        assert(Summaries->isARCEnabled() == ARCEnabled);
2435      return *Summaries;
2436    }
2437  }
2438
2439  RetainSummaryManager &getSummaryManager(CheckerContext &C) const {
2440    return getSummaryManager(C.getASTContext(), C.isObjCGCEnabled());
2441  }
2442
2443  void printState(raw_ostream &Out, ProgramStateRef State,
2444                  const char *NL, const char *Sep) const;
2445
2446  void checkBind(SVal loc, SVal val, const Stmt *S, CheckerContext &C) const;
2447  void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
2448  void checkPostStmt(const CastExpr *CE, CheckerContext &C) const;
2449
2450  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
2451  void checkPostStmt(const CXXConstructExpr *CE, CheckerContext &C) const;
2452  void checkPostStmt(const ObjCArrayLiteral *AL, CheckerContext &C) const;
2453  void checkPostStmt(const ObjCDictionaryLiteral *DL, CheckerContext &C) const;
2454  void checkPostObjCMessage(const ObjCMessage &Msg, CheckerContext &C) const;
2455
2456  void checkSummary(const RetainSummary &Summ, const CallOrObjCMessage &Call,
2457                    CheckerContext &C) const;
2458
2459  bool evalCall(const CallExpr *CE, CheckerContext &C) const;
2460
2461  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
2462                                 bool Assumption) const;
2463
2464  ProgramStateRef
2465  checkRegionChanges(ProgramStateRef state,
2466                     const StoreManager::InvalidatedSymbols *invalidated,
2467                     ArrayRef<const MemRegion *> ExplicitRegions,
2468                     ArrayRef<const MemRegion *> Regions,
2469                     const CallOrObjCMessage *Call) const;
2470
2471  bool wantsRegionChangeUpdate(ProgramStateRef state) const {
2472    return true;
2473  }
2474
2475  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
2476  void checkReturnWithRetEffect(const ReturnStmt *S, CheckerContext &C,
2477                                ExplodedNode *Pred, RetEffect RE, RefVal X,
2478                                SymbolRef Sym, ProgramStateRef state) const;
2479
2480  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
2481  void checkEndPath(CheckerContext &C) const;
2482
2483  ProgramStateRef updateSymbol(ProgramStateRef state, SymbolRef sym,
2484                                   RefVal V, ArgEffect E, RefVal::Kind &hasErr,
2485                                   CheckerContext &C) const;
2486
2487  void processNonLeakError(ProgramStateRef St, SourceRange ErrorRange,
2488                           RefVal::Kind ErrorKind, SymbolRef Sym,
2489                           CheckerContext &C) const;
2490
2491  void processObjCLiterals(CheckerContext &C, const Expr *Ex) const;
2492
2493  const ProgramPointTag *getDeadSymbolTag(SymbolRef sym) const;
2494
2495  ProgramStateRef handleSymbolDeath(ProgramStateRef state,
2496                                        SymbolRef sid, RefVal V,
2497                                      SmallVectorImpl<SymbolRef> &Leaked) const;
2498
2499  std::pair<ExplodedNode *, ProgramStateRef >
2500  handleAutoreleaseCounts(ProgramStateRef state,
2501                          GenericNodeBuilderRefCount Bd, ExplodedNode *Pred,
2502                          CheckerContext &Ctx, SymbolRef Sym, RefVal V) const;
2503
2504  ExplodedNode *processLeaks(ProgramStateRef state,
2505                             SmallVectorImpl<SymbolRef> &Leaked,
2506                             GenericNodeBuilderRefCount &Builder,
2507                             CheckerContext &Ctx,
2508                             ExplodedNode *Pred = 0) const;
2509};
2510} // end anonymous namespace
2511
2512namespace {
2513class StopTrackingCallback : public SymbolVisitor {
2514  ProgramStateRef state;
2515public:
2516  StopTrackingCallback(ProgramStateRef st) : state(st) {}
2517  ProgramStateRef getState() const { return state; }
2518
2519  bool VisitSymbol(SymbolRef sym) {
2520    state = state->remove<RefBindings>(sym);
2521    return true;
2522  }
2523};
2524} // end anonymous namespace
2525
2526//===----------------------------------------------------------------------===//
2527// Handle statements that may have an effect on refcounts.
2528//===----------------------------------------------------------------------===//
2529
2530void RetainCountChecker::checkPostStmt(const BlockExpr *BE,
2531                                       CheckerContext &C) const {
2532
2533  // Scan the BlockDecRefExprs for any object the retain count checker
2534  // may be tracking.
2535  if (!BE->getBlockDecl()->hasCaptures())
2536    return;
2537
2538  ProgramStateRef state = C.getState();
2539  const BlockDataRegion *R =
2540    cast<BlockDataRegion>(state->getSVal(BE,
2541                                         C.getLocationContext()).getAsRegion());
2542
2543  BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
2544                                            E = R->referenced_vars_end();
2545
2546  if (I == E)
2547    return;
2548
2549  // FIXME: For now we invalidate the tracking of all symbols passed to blocks
2550  // via captured variables, even though captured variables result in a copy
2551  // and in implicit increment/decrement of a retain count.
2552  SmallVector<const MemRegion*, 10> Regions;
2553  const LocationContext *LC = C.getLocationContext();
2554  MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
2555
2556  for ( ; I != E; ++I) {
2557    const VarRegion *VR = *I;
2558    if (VR->getSuperRegion() == R) {
2559      VR = MemMgr.getVarRegion(VR->getDecl(), LC);
2560    }
2561    Regions.push_back(VR);
2562  }
2563
2564  state =
2565    state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
2566                                    Regions.data() + Regions.size()).getState();
2567  C.addTransition(state);
2568}
2569
2570void RetainCountChecker::checkPostStmt(const CastExpr *CE,
2571                                       CheckerContext &C) const {
2572  const ObjCBridgedCastExpr *BE = dyn_cast<ObjCBridgedCastExpr>(CE);
2573  if (!BE)
2574    return;
2575
2576  ArgEffect AE = IncRef;
2577
2578  switch (BE->getBridgeKind()) {
2579    case clang::OBC_Bridge:
2580      // Do nothing.
2581      return;
2582    case clang::OBC_BridgeRetained:
2583      AE = IncRef;
2584      break;
2585    case clang::OBC_BridgeTransfer:
2586      AE = DecRefBridgedTransfered;
2587      break;
2588  }
2589
2590  ProgramStateRef state = C.getState();
2591  SymbolRef Sym = state->getSVal(CE, C.getLocationContext()).getAsLocSymbol();
2592  if (!Sym)
2593    return;
2594  const RefVal* T = state->get<RefBindings>(Sym);
2595  if (!T)
2596    return;
2597
2598  RefVal::Kind hasErr = (RefVal::Kind) 0;
2599  state = updateSymbol(state, Sym, *T, AE, hasErr, C);
2600
2601  if (hasErr) {
2602    // FIXME: If we get an error during a bridge cast, should we report it?
2603    // Should we assert that there is no error?
2604    return;
2605  }
2606
2607  C.addTransition(state);
2608}
2609
2610void RetainCountChecker::checkPostStmt(const CallExpr *CE,
2611                                       CheckerContext &C) const {
2612  // Get the callee.
2613  ProgramStateRef state = C.getState();
2614  const Expr *Callee = CE->getCallee();
2615  SVal L = state->getSVal(Callee, C.getLocationContext());
2616
2617  RetainSummaryManager &Summaries = getSummaryManager(C);
2618  const RetainSummary *Summ = 0;
2619
2620  // FIXME: Better support for blocks.  For now we stop tracking anything
2621  // that is passed to blocks.
2622  // FIXME: Need to handle variables that are "captured" by the block.
2623  if (dyn_cast_or_null<BlockDataRegion>(L.getAsRegion())) {
2624    Summ = Summaries.getPersistentStopSummary();
2625  } else if (const FunctionDecl *FD = L.getAsFunctionDecl()) {
2626    Summ = Summaries.getSummary(FD);
2627  } else if (const CXXMemberCallExpr *me = dyn_cast<CXXMemberCallExpr>(CE)) {
2628    if (const CXXMethodDecl *MD = me->getMethodDecl())
2629      Summ = Summaries.getSummary(MD);
2630  }
2631
2632  if (!Summ)
2633    Summ = Summaries.getDefaultSummary();
2634
2635  checkSummary(*Summ, CallOrObjCMessage(CE, state, C.getLocationContext()), C);
2636}
2637
2638void RetainCountChecker::checkPostStmt(const CXXConstructExpr *CE,
2639                                       CheckerContext &C) const {
2640  const CXXConstructorDecl *Ctor = CE->getConstructor();
2641  if (!Ctor)
2642    return;
2643
2644  RetainSummaryManager &Summaries = getSummaryManager(C);
2645  const RetainSummary *Summ = Summaries.getSummary(Ctor);
2646
2647  // If we didn't get a summary, this constructor doesn't affect retain counts.
2648  if (!Summ)
2649    return;
2650
2651  ProgramStateRef state = C.getState();
2652  checkSummary(*Summ, CallOrObjCMessage(CE, state, C.getLocationContext()), C);
2653}
2654
2655void RetainCountChecker::processObjCLiterals(CheckerContext &C,
2656                                             const Expr *Ex) const {
2657  ProgramStateRef state = C.getState();
2658  const ExplodedNode *pred = C.getPredecessor();
2659  for (Stmt::const_child_iterator it = Ex->child_begin(), et = Ex->child_end() ;
2660       it != et ; ++it) {
2661    const Stmt *child = *it;
2662    SVal V = state->getSVal(child, pred->getLocationContext());
2663    if (SymbolRef sym = V.getAsSymbol())
2664      if (const RefVal* T = state->get<RefBindings>(sym)) {
2665        RefVal::Kind hasErr = (RefVal::Kind) 0;
2666        state = updateSymbol(state, sym, *T, MayEscape, hasErr, C);
2667        if (hasErr) {
2668          processNonLeakError(state, child->getSourceRange(), hasErr, sym, C);
2669          return;
2670        }
2671      }
2672  }
2673
2674  // Return the object as autoreleased.
2675  //  RetEffect RE = RetEffect::MakeNotOwned(RetEffect::ObjC);
2676  if (SymbolRef sym =
2677        state->getSVal(Ex, pred->getLocationContext()).getAsSymbol()) {
2678    QualType ResultTy = Ex->getType();
2679    state = state->set<RefBindings>(sym, RefVal::makeNotOwned(RetEffect::ObjC,
2680                                                              ResultTy));
2681  }
2682
2683  C.addTransition(state);
2684}
2685
2686void RetainCountChecker::checkPostStmt(const ObjCArrayLiteral *AL,
2687                                       CheckerContext &C) const {
2688  // Apply the 'MayEscape' to all values.
2689  processObjCLiterals(C, AL);
2690}
2691
2692void RetainCountChecker::checkPostStmt(const ObjCDictionaryLiteral *DL,
2693                                       CheckerContext &C) const {
2694  // Apply the 'MayEscape' to all keys and values.
2695  processObjCLiterals(C, DL);
2696}
2697
2698void RetainCountChecker::checkPostObjCMessage(const ObjCMessage &Msg,
2699                                              CheckerContext &C) const {
2700  ProgramStateRef state = C.getState();
2701
2702  RetainSummaryManager &Summaries = getSummaryManager(C);
2703
2704  const RetainSummary *Summ;
2705  if (Msg.isInstanceMessage()) {
2706    const LocationContext *LC = C.getLocationContext();
2707    Summ = Summaries.getInstanceMethodSummary(Msg, state, LC);
2708  } else {
2709    Summ = Summaries.getClassMethodSummary(Msg);
2710  }
2711
2712  // If we didn't get a summary, this message doesn't affect retain counts.
2713  if (!Summ)
2714    return;
2715
2716  checkSummary(*Summ, CallOrObjCMessage(Msg, state, C.getLocationContext()), C);
2717}
2718
2719/// GetReturnType - Used to get the return type of a message expression or
2720///  function call with the intention of affixing that type to a tracked symbol.
2721///  While the the return type can be queried directly from RetEx, when
2722///  invoking class methods we augment to the return type to be that of
2723///  a pointer to the class (as opposed it just being id).
2724// FIXME: We may be able to do this with related result types instead.
2725// This function is probably overestimating.
2726static QualType GetReturnType(const Expr *RetE, ASTContext &Ctx) {
2727  QualType RetTy = RetE->getType();
2728  // If RetE is not a message expression just return its type.
2729  // If RetE is a message expression, return its types if it is something
2730  /// more specific than id.
2731  if (const ObjCMessageExpr *ME = dyn_cast<ObjCMessageExpr>(RetE))
2732    if (const ObjCObjectPointerType *PT = RetTy->getAs<ObjCObjectPointerType>())
2733      if (PT->isObjCQualifiedIdType() || PT->isObjCIdType() ||
2734          PT->isObjCClassType()) {
2735        // At this point we know the return type of the message expression is
2736        // id, id<...>, or Class. If we have an ObjCInterfaceDecl, we know this
2737        // is a call to a class method whose type we can resolve.  In such
2738        // cases, promote the return type to XXX* (where XXX is the class).
2739        const ObjCInterfaceDecl *D = ME->getReceiverInterface();
2740        return !D ? RetTy :
2741                    Ctx.getObjCObjectPointerType(Ctx.getObjCInterfaceType(D));
2742      }
2743
2744  return RetTy;
2745}
2746
2747void RetainCountChecker::checkSummary(const RetainSummary &Summ,
2748                                      const CallOrObjCMessage &CallOrMsg,
2749                                      CheckerContext &C) const {
2750  ProgramStateRef state = C.getState();
2751
2752  // Evaluate the effect of the arguments.
2753  RefVal::Kind hasErr = (RefVal::Kind) 0;
2754  SourceRange ErrorRange;
2755  SymbolRef ErrorSym = 0;
2756
2757  for (unsigned idx = 0, e = CallOrMsg.getNumArgs(); idx != e; ++idx) {
2758    SVal V = CallOrMsg.getArgSVal(idx);
2759
2760    if (SymbolRef Sym = V.getAsLocSymbol()) {
2761      if (RefBindings::data_type *T = state->get<RefBindings>(Sym)) {
2762        state = updateSymbol(state, Sym, *T, Summ.getArg(idx), hasErr, C);
2763        if (hasErr) {
2764          ErrorRange = CallOrMsg.getArgSourceRange(idx);
2765          ErrorSym = Sym;
2766          break;
2767        }
2768      }
2769    }
2770  }
2771
2772  // Evaluate the effect on the message receiver.
2773  bool ReceiverIsTracked = false;
2774  if (!hasErr && CallOrMsg.isObjCMessage()) {
2775    const LocationContext *LC = C.getLocationContext();
2776    SVal Receiver = CallOrMsg.getInstanceMessageReceiver(LC);
2777    if (SymbolRef Sym = Receiver.getAsLocSymbol()) {
2778      if (const RefVal *T = state->get<RefBindings>(Sym)) {
2779        ReceiverIsTracked = true;
2780        state = updateSymbol(state, Sym, *T, Summ.getReceiverEffect(),
2781                             hasErr, C);
2782        if (hasErr) {
2783          ErrorRange = CallOrMsg.getReceiverSourceRange();
2784          ErrorSym = Sym;
2785        }
2786      }
2787    }
2788  }
2789
2790  // Process any errors.
2791  if (hasErr) {
2792    processNonLeakError(state, ErrorRange, hasErr, ErrorSym, C);
2793    return;
2794  }
2795
2796  // Consult the summary for the return value.
2797  RetEffect RE = Summ.getRetEffect();
2798
2799  if (RE.getKind() == RetEffect::OwnedWhenTrackedReceiver) {
2800    if (ReceiverIsTracked)
2801      RE = getSummaryManager(C).getObjAllocRetEffect();
2802    else
2803      RE = RetEffect::MakeNoRet();
2804  }
2805
2806  switch (RE.getKind()) {
2807    default:
2808      llvm_unreachable("Unhandled RetEffect.");
2809
2810    case RetEffect::NoRet:
2811      // No work necessary.
2812      break;
2813
2814    case RetEffect::OwnedAllocatedSymbol:
2815    case RetEffect::OwnedSymbol: {
2816      SymbolRef Sym = state->getSVal(CallOrMsg.getOriginExpr(),
2817                                     C.getLocationContext()).getAsSymbol();
2818      if (!Sym)
2819        break;
2820
2821      // Use the result type from callOrMsg as it automatically adjusts
2822      // for methods/functions that return references.
2823      QualType ResultTy = CallOrMsg.getResultType(C.getASTContext());
2824      state = state->set<RefBindings>(Sym, RefVal::makeOwned(RE.getObjKind(),
2825                                                             ResultTy));
2826
2827      // FIXME: Add a flag to the checker where allocations are assumed to
2828      // *not* fail. (The code below is out-of-date, though.)
2829#if 0
2830      if (RE.getKind() == RetEffect::OwnedAllocatedSymbol) {
2831        bool isFeasible;
2832        state = state.assume(loc::SymbolVal(Sym), true, isFeasible);
2833        assert(isFeasible && "Cannot assume fresh symbol is non-null.");
2834      }
2835#endif
2836
2837      break;
2838    }
2839
2840    case RetEffect::GCNotOwnedSymbol:
2841    case RetEffect::ARCNotOwnedSymbol:
2842    case RetEffect::NotOwnedSymbol: {
2843      const Expr *Ex = CallOrMsg.getOriginExpr();
2844      SymbolRef Sym = state->getSVal(Ex, C.getLocationContext()).getAsSymbol();
2845      if (!Sym)
2846        break;
2847
2848      // Use GetReturnType in order to give [NSFoo alloc] the type NSFoo *.
2849      QualType ResultTy = GetReturnType(Ex, C.getASTContext());
2850      state = state->set<RefBindings>(Sym, RefVal::makeNotOwned(RE.getObjKind(),
2851                                                                ResultTy));
2852      break;
2853    }
2854  }
2855
2856  // This check is actually necessary; otherwise the statement builder thinks
2857  // we've hit a previously-found path.
2858  // Normally addTransition takes care of this, but we want the node pointer.
2859  ExplodedNode *NewNode;
2860  if (state == C.getState()) {
2861    NewNode = C.getPredecessor();
2862  } else {
2863    NewNode = C.addTransition(state);
2864  }
2865
2866  // Annotate the node with summary we used.
2867  if (NewNode) {
2868    // FIXME: This is ugly. See checkEndAnalysis for why it's necessary.
2869    if (ShouldResetSummaryLog) {
2870      SummaryLog.clear();
2871      ShouldResetSummaryLog = false;
2872    }
2873    SummaryLog[NewNode] = &Summ;
2874  }
2875}
2876
2877
2878ProgramStateRef
2879RetainCountChecker::updateSymbol(ProgramStateRef state, SymbolRef sym,
2880                                 RefVal V, ArgEffect E, RefVal::Kind &hasErr,
2881                                 CheckerContext &C) const {
2882  // In GC mode [... release] and [... retain] do nothing.
2883  // In ARC mode they shouldn't exist at all, but we just ignore them.
2884  bool IgnoreRetainMsg = C.isObjCGCEnabled();
2885  if (!IgnoreRetainMsg)
2886    IgnoreRetainMsg = (bool)C.getASTContext().getLangOptions().ObjCAutoRefCount;
2887
2888  switch (E) {
2889    default: break;
2890    case IncRefMsg: E = IgnoreRetainMsg ? DoNothing : IncRef; break;
2891    case DecRefMsg: E = IgnoreRetainMsg ? DoNothing : DecRef; break;
2892    case MakeCollectable: E = C.isObjCGCEnabled() ? DecRef : DoNothing; break;
2893    case NewAutoreleasePool: E = C.isObjCGCEnabled() ? DoNothing :
2894                                                      NewAutoreleasePool; break;
2895  }
2896
2897  // Handle all use-after-releases.
2898  if (!C.isObjCGCEnabled() && V.getKind() == RefVal::Released) {
2899    V = V ^ RefVal::ErrorUseAfterRelease;
2900    hasErr = V.getKind();
2901    return state->set<RefBindings>(sym, V);
2902  }
2903
2904  switch (E) {
2905    case DecRefMsg:
2906    case IncRefMsg:
2907    case MakeCollectable:
2908      llvm_unreachable("DecRefMsg/IncRefMsg/MakeCollectable already converted");
2909
2910    case Dealloc:
2911      // Any use of -dealloc in GC is *bad*.
2912      if (C.isObjCGCEnabled()) {
2913        V = V ^ RefVal::ErrorDeallocGC;
2914        hasErr = V.getKind();
2915        break;
2916      }
2917
2918      switch (V.getKind()) {
2919        default:
2920          llvm_unreachable("Invalid RefVal state for an explicit dealloc.");
2921        case RefVal::Owned:
2922          // The object immediately transitions to the released state.
2923          V = V ^ RefVal::Released;
2924          V.clearCounts();
2925          return state->set<RefBindings>(sym, V);
2926        case RefVal::NotOwned:
2927          V = V ^ RefVal::ErrorDeallocNotOwned;
2928          hasErr = V.getKind();
2929          break;
2930      }
2931      break;
2932
2933    case NewAutoreleasePool:
2934      assert(!C.isObjCGCEnabled());
2935      return state->add<AutoreleaseStack>(sym);
2936
2937    case MayEscape:
2938      if (V.getKind() == RefVal::Owned) {
2939        V = V ^ RefVal::NotOwned;
2940        break;
2941      }
2942
2943      // Fall-through.
2944
2945    case DoNothing:
2946      return state;
2947
2948    case Autorelease:
2949      if (C.isObjCGCEnabled())
2950        return state;
2951
2952      // Update the autorelease counts.
2953      state = SendAutorelease(state, ARCountFactory, sym);
2954      V = V.autorelease();
2955      break;
2956
2957    case StopTracking:
2958      return state->remove<RefBindings>(sym);
2959
2960    case IncRef:
2961      switch (V.getKind()) {
2962        default:
2963          llvm_unreachable("Invalid RefVal state for a retain.");
2964        case RefVal::Owned:
2965        case RefVal::NotOwned:
2966          V = V + 1;
2967          break;
2968        case RefVal::Released:
2969          // Non-GC cases are handled above.
2970          assert(C.isObjCGCEnabled());
2971          V = (V ^ RefVal::Owned) + 1;
2972          break;
2973      }
2974      break;
2975
2976    case SelfOwn:
2977      V = V ^ RefVal::NotOwned;
2978      // Fall-through.
2979    case DecRef:
2980    case DecRefBridgedTransfered:
2981      switch (V.getKind()) {
2982        default:
2983          // case 'RefVal::Released' handled above.
2984          llvm_unreachable("Invalid RefVal state for a release.");
2985
2986        case RefVal::Owned:
2987          assert(V.getCount() > 0);
2988          if (V.getCount() == 1)
2989            V = V ^ (E == DecRefBridgedTransfered ?
2990                      RefVal::NotOwned : RefVal::Released);
2991          V = V - 1;
2992          break;
2993
2994        case RefVal::NotOwned:
2995          if (V.getCount() > 0)
2996            V = V - 1;
2997          else {
2998            V = V ^ RefVal::ErrorReleaseNotOwned;
2999            hasErr = V.getKind();
3000          }
3001          break;
3002
3003        case RefVal::Released:
3004          // Non-GC cases are handled above.
3005          assert(C.isObjCGCEnabled());
3006          V = V ^ RefVal::ErrorUseAfterRelease;
3007          hasErr = V.getKind();
3008          break;
3009      }
3010      break;
3011  }
3012  return state->set<RefBindings>(sym, V);
3013}
3014
3015void RetainCountChecker::processNonLeakError(ProgramStateRef St,
3016                                             SourceRange ErrorRange,
3017                                             RefVal::Kind ErrorKind,
3018                                             SymbolRef Sym,
3019                                             CheckerContext &C) const {
3020  ExplodedNode *N = C.generateSink(St);
3021  if (!N)
3022    return;
3023
3024  CFRefBug *BT;
3025  switch (ErrorKind) {
3026    default:
3027      llvm_unreachable("Unhandled error.");
3028    case RefVal::ErrorUseAfterRelease:
3029      if (!useAfterRelease)
3030        useAfterRelease.reset(new UseAfterRelease());
3031      BT = &*useAfterRelease;
3032      break;
3033    case RefVal::ErrorReleaseNotOwned:
3034      if (!releaseNotOwned)
3035        releaseNotOwned.reset(new BadRelease());
3036      BT = &*releaseNotOwned;
3037      break;
3038    case RefVal::ErrorDeallocGC:
3039      if (!deallocGC)
3040        deallocGC.reset(new DeallocGC());
3041      BT = &*deallocGC;
3042      break;
3043    case RefVal::ErrorDeallocNotOwned:
3044      if (!deallocNotOwned)
3045        deallocNotOwned.reset(new DeallocNotOwned());
3046      BT = &*deallocNotOwned;
3047      break;
3048  }
3049
3050  assert(BT);
3051  CFRefReport *report = new CFRefReport(*BT, C.getASTContext().getLangOptions(),
3052                                        C.isObjCGCEnabled(), SummaryLog,
3053                                        N, Sym);
3054  report->addRange(ErrorRange);
3055  C.EmitReport(report);
3056}
3057
3058//===----------------------------------------------------------------------===//
3059// Handle the return values of retain-count-related functions.
3060//===----------------------------------------------------------------------===//
3061
3062bool RetainCountChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
3063  // Get the callee. We're only interested in simple C functions.
3064  ProgramStateRef state = C.getState();
3065  const FunctionDecl *FD = C.getCalleeDecl(CE);
3066  if (!FD)
3067    return false;
3068
3069  IdentifierInfo *II = FD->getIdentifier();
3070  if (!II)
3071    return false;
3072
3073  // For now, we're only handling the functions that return aliases of their
3074  // arguments: CFRetain and CFMakeCollectable (and their families).
3075  // Eventually we should add other functions we can model entirely,
3076  // such as CFRelease, which don't invalidate their arguments or globals.
3077  if (CE->getNumArgs() != 1)
3078    return false;
3079
3080  // Get the name of the function.
3081  StringRef FName = II->getName();
3082  FName = FName.substr(FName.find_first_not_of('_'));
3083
3084  // See if it's one of the specific functions we know how to eval.
3085  bool canEval = false;
3086
3087  QualType ResultTy = CE->getCallReturnType();
3088  if (ResultTy->isObjCIdType()) {
3089    // Handle: id NSMakeCollectable(CFTypeRef)
3090    canEval = II->isStr("NSMakeCollectable");
3091  } else if (ResultTy->isPointerType()) {
3092    // Handle: (CF|CG)Retain
3093    //         CFMakeCollectable
3094    // It's okay to be a little sloppy here (CGMakeCollectable doesn't exist).
3095    if (cocoa::isRefType(ResultTy, "CF", FName) ||
3096        cocoa::isRefType(ResultTy, "CG", FName)) {
3097      canEval = isRetain(FD, FName) || isMakeCollectable(FD, FName);
3098    }
3099  }
3100
3101  if (!canEval)
3102    return false;
3103
3104  // Bind the return value.
3105  const LocationContext *LCtx = C.getLocationContext();
3106  SVal RetVal = state->getSVal(CE->getArg(0), LCtx);
3107  if (RetVal.isUnknown()) {
3108    // If the receiver is unknown, conjure a return value.
3109    SValBuilder &SVB = C.getSValBuilder();
3110    unsigned Count = C.getCurrentBlockCount();
3111    SVal RetVal = SVB.getConjuredSymbolVal(0, CE, LCtx, ResultTy, Count);
3112  }
3113  state = state->BindExpr(CE, LCtx, RetVal, false);
3114
3115  // FIXME: This should not be necessary, but otherwise the argument seems to be
3116  // considered alive during the next statement.
3117  if (const MemRegion *ArgRegion = RetVal.getAsRegion()) {
3118    // Save the refcount status of the argument.
3119    SymbolRef Sym = RetVal.getAsLocSymbol();
3120    RefBindings::data_type *Binding = 0;
3121    if (Sym)
3122      Binding = state->get<RefBindings>(Sym);
3123
3124    // Invalidate the argument region.
3125    unsigned Count = C.getCurrentBlockCount();
3126    state = state->invalidateRegions(ArgRegion, CE, Count, LCtx);
3127
3128    // Restore the refcount status of the argument.
3129    if (Binding)
3130      state = state->set<RefBindings>(Sym, *Binding);
3131  }
3132
3133  C.addTransition(state);
3134  return true;
3135}
3136
3137//===----------------------------------------------------------------------===//
3138// Handle return statements.
3139//===----------------------------------------------------------------------===//
3140
3141// Return true if the current LocationContext has no caller context.
3142static bool inTopFrame(CheckerContext &C) {
3143  const LocationContext *LC = C.getLocationContext();
3144  return LC->getParent() == 0;
3145}
3146
3147void RetainCountChecker::checkPreStmt(const ReturnStmt *S,
3148                                      CheckerContext &C) const {
3149
3150  // Only adjust the reference count if this is the top-level call frame,
3151  // and not the result of inlining.  In the future, we should do
3152  // better checking even for inlined calls, and see if they match
3153  // with their expected semantics (e.g., the method should return a retained
3154  // object, etc.).
3155  if (!inTopFrame(C))
3156    return;
3157
3158  const Expr *RetE = S->getRetValue();
3159  if (!RetE)
3160    return;
3161
3162  ProgramStateRef state = C.getState();
3163  SymbolRef Sym =
3164    state->getSValAsScalarOrLoc(RetE, C.getLocationContext()).getAsLocSymbol();
3165  if (!Sym)
3166    return;
3167
3168  // Get the reference count binding (if any).
3169  const RefVal *T = state->get<RefBindings>(Sym);
3170  if (!T)
3171    return;
3172
3173  // Change the reference count.
3174  RefVal X = *T;
3175
3176  switch (X.getKind()) {
3177    case RefVal::Owned: {
3178      unsigned cnt = X.getCount();
3179      assert(cnt > 0);
3180      X.setCount(cnt - 1);
3181      X = X ^ RefVal::ReturnedOwned;
3182      break;
3183    }
3184
3185    case RefVal::NotOwned: {
3186      unsigned cnt = X.getCount();
3187      if (cnt) {
3188        X.setCount(cnt - 1);
3189        X = X ^ RefVal::ReturnedOwned;
3190      }
3191      else {
3192        X = X ^ RefVal::ReturnedNotOwned;
3193      }
3194      break;
3195    }
3196
3197    default:
3198      return;
3199  }
3200
3201  // Update the binding.
3202  state = state->set<RefBindings>(Sym, X);
3203  ExplodedNode *Pred = C.addTransition(state);
3204
3205  // At this point we have updated the state properly.
3206  // Everything after this is merely checking to see if the return value has
3207  // been over- or under-retained.
3208
3209  // Did we cache out?
3210  if (!Pred)
3211    return;
3212
3213  // Update the autorelease counts.
3214  static SimpleProgramPointTag
3215         AutoreleaseTag("RetainCountChecker : Autorelease");
3216  GenericNodeBuilderRefCount Bd(C, &AutoreleaseTag);
3217  llvm::tie(Pred, state) = handleAutoreleaseCounts(state, Bd, Pred, C, Sym, X);
3218
3219  // Did we cache out?
3220  if (!Pred)
3221    return;
3222
3223  // Get the updated binding.
3224  T = state->get<RefBindings>(Sym);
3225  assert(T);
3226  X = *T;
3227
3228  // Consult the summary of the enclosing method.
3229  RetainSummaryManager &Summaries = getSummaryManager(C);
3230  const Decl *CD = &Pred->getCodeDecl();
3231
3232  if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(CD)) {
3233    // Unlike regular functions, /all/ ObjC methods are assumed to always
3234    // follow Cocoa retain-count conventions, not just those with special
3235    // names or attributes.
3236    const RetainSummary *Summ = Summaries.getMethodSummary(MD);
3237    RetEffect RE = Summ ? Summ->getRetEffect() : RetEffect::MakeNoRet();
3238    checkReturnWithRetEffect(S, C, Pred, RE, X, Sym, state);
3239  }
3240
3241  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CD)) {
3242    if (!isa<CXXMethodDecl>(FD))
3243      if (const RetainSummary *Summ = Summaries.getSummary(FD))
3244        checkReturnWithRetEffect(S, C, Pred, Summ->getRetEffect(), X,
3245                                 Sym, state);
3246  }
3247}
3248
3249void RetainCountChecker::checkReturnWithRetEffect(const ReturnStmt *S,
3250                                                  CheckerContext &C,
3251                                                  ExplodedNode *Pred,
3252                                                  RetEffect RE, RefVal X,
3253                                                  SymbolRef Sym,
3254                                              ProgramStateRef state) const {
3255  // Any leaks or other errors?
3256  if (X.isReturnedOwned() && X.getCount() == 0) {
3257    if (RE.getKind() != RetEffect::NoRet) {
3258      bool hasError = false;
3259      if (C.isObjCGCEnabled() && RE.getObjKind() == RetEffect::ObjC) {
3260        // Things are more complicated with garbage collection.  If the
3261        // returned object is suppose to be an Objective-C object, we have
3262        // a leak (as the caller expects a GC'ed object) because no
3263        // method should return ownership unless it returns a CF object.
3264        hasError = true;
3265        X = X ^ RefVal::ErrorGCLeakReturned;
3266      }
3267      else if (!RE.isOwned()) {
3268        // Either we are using GC and the returned object is a CF type
3269        // or we aren't using GC.  In either case, we expect that the
3270        // enclosing method is expected to return ownership.
3271        hasError = true;
3272        X = X ^ RefVal::ErrorLeakReturned;
3273      }
3274
3275      if (hasError) {
3276        // Generate an error node.
3277        state = state->set<RefBindings>(Sym, X);
3278
3279        static SimpleProgramPointTag
3280               ReturnOwnLeakTag("RetainCountChecker : ReturnsOwnLeak");
3281        ExplodedNode *N = C.addTransition(state, Pred, &ReturnOwnLeakTag);
3282        if (N) {
3283          const LangOptions &LOpts = C.getASTContext().getLangOptions();
3284          bool GCEnabled = C.isObjCGCEnabled();
3285          CFRefReport *report =
3286            new CFRefLeakReport(*getLeakAtReturnBug(LOpts, GCEnabled),
3287                                LOpts, GCEnabled, SummaryLog,
3288                                N, Sym, C);
3289          C.EmitReport(report);
3290        }
3291      }
3292    }
3293  } else if (X.isReturnedNotOwned()) {
3294    if (RE.isOwned()) {
3295      // Trying to return a not owned object to a caller expecting an
3296      // owned object.
3297      state = state->set<RefBindings>(Sym, X ^ RefVal::ErrorReturnedNotOwned);
3298
3299      static SimpleProgramPointTag
3300             ReturnNotOwnedTag("RetainCountChecker : ReturnNotOwnedForOwned");
3301      ExplodedNode *N = C.addTransition(state, Pred, &ReturnNotOwnedTag);
3302      if (N) {
3303        if (!returnNotOwnedForOwned)
3304          returnNotOwnedForOwned.reset(new ReturnedNotOwnedForOwned());
3305
3306        CFRefReport *report =
3307            new CFRefReport(*returnNotOwnedForOwned,
3308                            C.getASTContext().getLangOptions(),
3309                            C.isObjCGCEnabled(), SummaryLog, N, Sym);
3310        C.EmitReport(report);
3311      }
3312    }
3313  }
3314}
3315
3316//===----------------------------------------------------------------------===//
3317// Check various ways a symbol can be invalidated.
3318//===----------------------------------------------------------------------===//
3319
3320void RetainCountChecker::checkBind(SVal loc, SVal val, const Stmt *S,
3321                                   CheckerContext &C) const {
3322  // Are we storing to something that causes the value to "escape"?
3323  bool escapes = true;
3324
3325  // A value escapes in three possible cases (this may change):
3326  //
3327  // (1) we are binding to something that is not a memory region.
3328  // (2) we are binding to a memregion that does not have stack storage
3329  // (3) we are binding to a memregion with stack storage that the store
3330  //     does not understand.
3331  ProgramStateRef state = C.getState();
3332
3333  if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
3334    escapes = !regionLoc->getRegion()->hasStackStorage();
3335
3336    if (!escapes) {
3337      // To test (3), generate a new state with the binding added.  If it is
3338      // the same state, then it escapes (since the store cannot represent
3339      // the binding).
3340      escapes = (state == (state->bindLoc(*regionLoc, val)));
3341    }
3342  }
3343
3344  // If our store can represent the binding and we aren't storing to something
3345  // that doesn't have local storage then just return and have the simulation
3346  // state continue as is.
3347  if (!escapes)
3348      return;
3349
3350  // Otherwise, find all symbols referenced by 'val' that we are tracking
3351  // and stop tracking them.
3352  state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
3353  C.addTransition(state);
3354}
3355
3356ProgramStateRef RetainCountChecker::evalAssume(ProgramStateRef state,
3357                                                   SVal Cond,
3358                                                   bool Assumption) const {
3359
3360  // FIXME: We may add to the interface of evalAssume the list of symbols
3361  //  whose assumptions have changed.  For now we just iterate through the
3362  //  bindings and check if any of the tracked symbols are NULL.  This isn't
3363  //  too bad since the number of symbols we will track in practice are
3364  //  probably small and evalAssume is only called at branches and a few
3365  //  other places.
3366  RefBindings B = state->get<RefBindings>();
3367
3368  if (B.isEmpty())
3369    return state;
3370
3371  bool changed = false;
3372  RefBindings::Factory &RefBFactory = state->get_context<RefBindings>();
3373
3374  for (RefBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3375    // Check if the symbol is null (or equal to any constant).
3376    // If this is the case, stop tracking the symbol.
3377    if (state->getSymVal(I.getKey())) {
3378      changed = true;
3379      B = RefBFactory.remove(B, I.getKey());
3380    }
3381  }
3382
3383  if (changed)
3384    state = state->set<RefBindings>(B);
3385
3386  return state;
3387}
3388
3389ProgramStateRef
3390RetainCountChecker::checkRegionChanges(ProgramStateRef state,
3391                            const StoreManager::InvalidatedSymbols *invalidated,
3392                                    ArrayRef<const MemRegion *> ExplicitRegions,
3393                                    ArrayRef<const MemRegion *> Regions,
3394                                    const CallOrObjCMessage *Call) const {
3395  if (!invalidated)
3396    return state;
3397
3398  llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
3399  for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
3400       E = ExplicitRegions.end(); I != E; ++I) {
3401    if (const SymbolicRegion *SR = (*I)->StripCasts()->getAs<SymbolicRegion>())
3402      WhitelistedSymbols.insert(SR->getSymbol());
3403  }
3404
3405  for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
3406       E = invalidated->end(); I!=E; ++I) {
3407    SymbolRef sym = *I;
3408    if (WhitelistedSymbols.count(sym))
3409      continue;
3410    // Remove any existing reference-count binding.
3411    state = state->remove<RefBindings>(sym);
3412  }
3413  return state;
3414}
3415
3416//===----------------------------------------------------------------------===//
3417// Handle dead symbols and end-of-path.
3418//===----------------------------------------------------------------------===//
3419
3420std::pair<ExplodedNode *, ProgramStateRef >
3421RetainCountChecker::handleAutoreleaseCounts(ProgramStateRef state,
3422                                            GenericNodeBuilderRefCount Bd,
3423                                            ExplodedNode *Pred,
3424                                            CheckerContext &Ctx,
3425                                            SymbolRef Sym, RefVal V) const {
3426  unsigned ACnt = V.getAutoreleaseCount();
3427
3428  // No autorelease counts?  Nothing to be done.
3429  if (!ACnt)
3430    return std::make_pair(Pred, state);
3431
3432  assert(!Ctx.isObjCGCEnabled() && "Autorelease counts in GC mode?");
3433  unsigned Cnt = V.getCount();
3434
3435  // FIXME: Handle sending 'autorelease' to already released object.
3436
3437  if (V.getKind() == RefVal::ReturnedOwned)
3438    ++Cnt;
3439
3440  if (ACnt <= Cnt) {
3441    if (ACnt == Cnt) {
3442      V.clearCounts();
3443      if (V.getKind() == RefVal::ReturnedOwned)
3444        V = V ^ RefVal::ReturnedNotOwned;
3445      else
3446        V = V ^ RefVal::NotOwned;
3447    } else {
3448      V.setCount(Cnt - ACnt);
3449      V.setAutoreleaseCount(0);
3450    }
3451    state = state->set<RefBindings>(Sym, V);
3452    ExplodedNode *N = Bd.MakeNode(state, Pred);
3453    if (N == 0)
3454      state = 0;
3455    return std::make_pair(N, state);
3456  }
3457
3458  // Woah!  More autorelease counts then retain counts left.
3459  // Emit hard error.
3460  V = V ^ RefVal::ErrorOverAutorelease;
3461  state = state->set<RefBindings>(Sym, V);
3462
3463  if (ExplodedNode *N = Bd.MakeNode(state, Pred, true)) {
3464    SmallString<128> sbuf;
3465    llvm::raw_svector_ostream os(sbuf);
3466    os << "Object over-autoreleased: object was sent -autorelease ";
3467    if (V.getAutoreleaseCount() > 1)
3468      os << V.getAutoreleaseCount() << " times ";
3469    os << "but the object has a +" << V.getCount() << " retain count";
3470
3471    if (!overAutorelease)
3472      overAutorelease.reset(new OverAutorelease());
3473
3474    const LangOptions &LOpts = Ctx.getASTContext().getLangOptions();
3475    CFRefReport *report =
3476      new CFRefReport(*overAutorelease, LOpts, /* GCEnabled = */ false,
3477                      SummaryLog, N, Sym, os.str());
3478    Ctx.EmitReport(report);
3479  }
3480
3481  return std::make_pair((ExplodedNode *)0, (ProgramStateRef )0);
3482}
3483
3484ProgramStateRef
3485RetainCountChecker::handleSymbolDeath(ProgramStateRef state,
3486                                      SymbolRef sid, RefVal V,
3487                                    SmallVectorImpl<SymbolRef> &Leaked) const {
3488  bool hasLeak = false;
3489  if (V.isOwned())
3490    hasLeak = true;
3491  else if (V.isNotOwned() || V.isReturnedOwned())
3492    hasLeak = (V.getCount() > 0);
3493
3494  if (!hasLeak)
3495    return state->remove<RefBindings>(sid);
3496
3497  Leaked.push_back(sid);
3498  return state->set<RefBindings>(sid, V ^ RefVal::ErrorLeak);
3499}
3500
3501ExplodedNode *
3502RetainCountChecker::processLeaks(ProgramStateRef state,
3503                                 SmallVectorImpl<SymbolRef> &Leaked,
3504                                 GenericNodeBuilderRefCount &Builder,
3505                                 CheckerContext &Ctx,
3506                                 ExplodedNode *Pred) const {
3507  if (Leaked.empty())
3508    return Pred;
3509
3510  // Generate an intermediate node representing the leak point.
3511  ExplodedNode *N = Builder.MakeNode(state, Pred);
3512
3513  if (N) {
3514    for (SmallVectorImpl<SymbolRef>::iterator
3515         I = Leaked.begin(), E = Leaked.end(); I != E; ++I) {
3516
3517      const LangOptions &LOpts = Ctx.getASTContext().getLangOptions();
3518      bool GCEnabled = Ctx.isObjCGCEnabled();
3519      CFRefBug *BT = Pred ? getLeakWithinFunctionBug(LOpts, GCEnabled)
3520                          : getLeakAtReturnBug(LOpts, GCEnabled);
3521      assert(BT && "BugType not initialized.");
3522
3523      CFRefLeakReport *report = new CFRefLeakReport(*BT, LOpts, GCEnabled,
3524                                                    SummaryLog, N, *I, Ctx);
3525      Ctx.EmitReport(report);
3526    }
3527  }
3528
3529  return N;
3530}
3531
3532void RetainCountChecker::checkEndPath(CheckerContext &Ctx) const {
3533  ProgramStateRef state = Ctx.getState();
3534  GenericNodeBuilderRefCount Bd(Ctx);
3535  RefBindings B = state->get<RefBindings>();
3536  ExplodedNode *Pred = Ctx.getPredecessor();
3537
3538  for (RefBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3539    llvm::tie(Pred, state) = handleAutoreleaseCounts(state, Bd, Pred, Ctx,
3540                                                     I->first, I->second);
3541    if (!state)
3542      return;
3543  }
3544
3545  // If the current LocationContext has a parent, don't check for leaks.
3546  // We will do that later.
3547  // FIXME: we should instead check for imblances of the retain/releases,
3548  // and suggest annotations.
3549  if (Ctx.getLocationContext()->getParent())
3550    return;
3551
3552  B = state->get<RefBindings>();
3553  SmallVector<SymbolRef, 10> Leaked;
3554
3555  for (RefBindings::iterator I = B.begin(), E = B.end(); I != E; ++I)
3556    state = handleSymbolDeath(state, I->first, I->second, Leaked);
3557
3558  processLeaks(state, Leaked, Bd, Ctx, Pred);
3559}
3560
3561const ProgramPointTag *
3562RetainCountChecker::getDeadSymbolTag(SymbolRef sym) const {
3563  const SimpleProgramPointTag *&tag = DeadSymbolTags[sym];
3564  if (!tag) {
3565    SmallString<64> buf;
3566    llvm::raw_svector_ostream out(buf);
3567    out << "RetainCountChecker : Dead Symbol : ";
3568    sym->dumpToStream(out);
3569    tag = new SimpleProgramPointTag(out.str());
3570  }
3571  return tag;
3572}
3573
3574void RetainCountChecker::checkDeadSymbols(SymbolReaper &SymReaper,
3575                                          CheckerContext &C) const {
3576  ExplodedNode *Pred = C.getPredecessor();
3577
3578  ProgramStateRef state = C.getState();
3579  RefBindings B = state->get<RefBindings>();
3580
3581  // Update counts from autorelease pools
3582  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
3583       E = SymReaper.dead_end(); I != E; ++I) {
3584    SymbolRef Sym = *I;
3585    if (const RefVal *T = B.lookup(Sym)){
3586      // Use the symbol as the tag.
3587      // FIXME: This might not be as unique as we would like.
3588      GenericNodeBuilderRefCount Bd(C, getDeadSymbolTag(Sym));
3589      llvm::tie(Pred, state) = handleAutoreleaseCounts(state, Bd, Pred, C,
3590                                                       Sym, *T);
3591      if (!state)
3592        return;
3593    }
3594  }
3595
3596  B = state->get<RefBindings>();
3597  SmallVector<SymbolRef, 10> Leaked;
3598
3599  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
3600       E = SymReaper.dead_end(); I != E; ++I) {
3601    if (const RefVal *T = B.lookup(*I))
3602      state = handleSymbolDeath(state, *I, *T, Leaked);
3603  }
3604
3605  {
3606    GenericNodeBuilderRefCount Bd(C, this);
3607    Pred = processLeaks(state, Leaked, Bd, C, Pred);
3608  }
3609
3610  // Did we cache out?
3611  if (!Pred)
3612    return;
3613
3614  // Now generate a new node that nukes the old bindings.
3615  RefBindings::Factory &F = state->get_context<RefBindings>();
3616
3617  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
3618       E = SymReaper.dead_end(); I != E; ++I)
3619    B = F.remove(B, *I);
3620
3621  state = state->set<RefBindings>(B);
3622  C.addTransition(state, Pred);
3623}
3624
3625//===----------------------------------------------------------------------===//
3626// Debug printing of refcount bindings and autorelease pools.
3627//===----------------------------------------------------------------------===//
3628
3629static void PrintPool(raw_ostream &Out, SymbolRef Sym,
3630                      ProgramStateRef State) {
3631  Out << ' ';
3632  if (Sym)
3633    Sym->dumpToStream(Out);
3634  else
3635    Out << "<pool>";
3636  Out << ":{";
3637
3638  // Get the contents of the pool.
3639  if (const ARCounts *Cnts = State->get<AutoreleasePoolContents>(Sym))
3640    for (ARCounts::iterator I = Cnts->begin(), E = Cnts->end(); I != E; ++I)
3641      Out << '(' << I.getKey() << ',' << I.getData() << ')';
3642
3643  Out << '}';
3644}
3645
3646static bool UsesAutorelease(ProgramStateRef state) {
3647  // A state uses autorelease if it allocated an autorelease pool or if it has
3648  // objects in the caller's autorelease pool.
3649  return !state->get<AutoreleaseStack>().isEmpty() ||
3650          state->get<AutoreleasePoolContents>(SymbolRef());
3651}
3652
3653void RetainCountChecker::printState(raw_ostream &Out, ProgramStateRef State,
3654                                    const char *NL, const char *Sep) const {
3655
3656  RefBindings B = State->get<RefBindings>();
3657
3658  if (!B.isEmpty())
3659    Out << Sep << NL;
3660
3661  for (RefBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
3662    Out << I->first << " : ";
3663    I->second.print(Out);
3664    Out << NL;
3665  }
3666
3667  // Print the autorelease stack.
3668  if (UsesAutorelease(State)) {
3669    Out << Sep << NL << "AR pool stack:";
3670    ARStack Stack = State->get<AutoreleaseStack>();
3671
3672    PrintPool(Out, SymbolRef(), State);  // Print the caller's pool.
3673    for (ARStack::iterator I = Stack.begin(), E = Stack.end(); I != E; ++I)
3674      PrintPool(Out, *I, State);
3675
3676    Out << NL;
3677  }
3678}
3679
3680//===----------------------------------------------------------------------===//
3681// Checker registration.
3682//===----------------------------------------------------------------------===//
3683
3684void ento::registerRetainCountChecker(CheckerManager &Mgr) {
3685  Mgr.registerChecker<RetainCountChecker>();
3686}
3687
3688