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