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