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