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