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