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