contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp

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