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