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