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