lib/GR/CFRefCount.cpp

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