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