CFRefCount.cpp

// CFRefCount.cpp - Transfer functions for tracking simple values -*- C++ -*--//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines the methods for CFRefCount, which implements
//  a reference count checker for Core Foundation (Mac OS X).
//
//===----------------------------------------------------------------------===//

#include "GRSimpleVals.h"
#include "clang/Basic/LangOptions.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Analysis/PathSensitive/GRState.h"
#include "clang/Analysis/PathSensitive/GRStateTrait.h"
#include "clang/Analysis/PathDiagnostic.h"
#include "clang/Analysis/LocalCheckers.h"
#include "clang/Analysis/PathDiagnostic.h"
#include "clang/Analysis/PathSensitive/BugReporter.h"
#include "clang/AST/DeclObjC.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/ImmutableList.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/STLExtras.h"
#include <ostream>
#include <sstream>
#include <stdarg.h>

using namespace clang;

//===----------------------------------------------------------------------===//
// Utility functions.
//===----------------------------------------------------------------------===//

using llvm::CStrInCStrNoCase;

// The "fundamental rule" for naming conventions of methods:
//  (url broken into two lines)
//  http://developer.apple.com/documentation/Cocoa/Conceptual/
//     MemoryMgmt/Tasks/MemoryManagementRules.html
//
// "You take ownership of an object if you create it using a method whose name
//  begins with “alloc” or “new” or contains “copy” (for example, alloc, 
//  newObject, or mutableCopy), or if you send it a retain message. You are
//  responsible for relinquishing ownership of objects you own using release
//  or autorelease. Any other time you receive an object, you must
//  not release it."
//
static bool followsFundamentalRule(const char* s) {
  return CStrInCStrNoCase(s, "create") || CStrInCStrNoCase(s, "copy")  || 
  CStrInCStrNoCase(s, "new") == s || CStrInCStrNoCase(s, "alloc") == s;
}  

//===----------------------------------------------------------------------===//
// Selector creation functions.
//===----------------------------------------------------------------------===//

static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
  IdentifierInfo* II = &Ctx.Idents.get(name);
  return Ctx.Selectors.getSelector(0, &II);
}

static inline Selector GetUnarySelector(const char* name, ASTContext& Ctx) {
  IdentifierInfo* II = &Ctx.Idents.get(name);
  return Ctx.Selectors.getSelector(1, &II);
}

//===----------------------------------------------------------------------===//
// Type querying functions.
//===----------------------------------------------------------------------===//

static bool isCFRefType(QualType T) {
  
  if (!T->isPointerType())
    return false;
  
  // Check the typedef for the name "CF" and the substring "Ref".  
  TypedefType* TD = dyn_cast<TypedefType>(T.getTypePtr());
  
  if (!TD)
    return false;
  
  const char* TDName = TD->getDecl()->getIdentifier()->getName();
  assert (TDName);
  
  if (TDName[0] != 'C' || TDName[1] != 'F')
    return false;
  
  if (strstr(TDName, "Ref") == 0)
    return false;
  
  return true;
}

static bool isCGRefType(QualType T) {
  
  if (!T->isPointerType())
    return false;
  
  // Check the typedef for the name "CG" and the substring "Ref".  
  TypedefType* TD = dyn_cast<TypedefType>(T.getTypePtr());
  
  if (!TD)
    return false;
  
  const char* TDName = TD->getDecl()->getIdentifier()->getName();
  assert (TDName);
  
  if (TDName[0] != 'C' || TDName[1] != 'G')
    return false;
  
  if (strstr(TDName, "Ref") == 0)
    return false;
  
  return true;
}

static bool isNSType(QualType T) {
  
  if (!T->isPointerType())
    return false;
  
  ObjCInterfaceType* OT = dyn_cast<ObjCInterfaceType>(T.getTypePtr());
  
  if (!OT)
    return false;
  
  const char* ClsName = OT->getDecl()->getIdentifier()->getName();
  assert (ClsName);
  
  if (ClsName[0] != 'N' || ClsName[1] != 'S')
    return false;
  
  return true;
}

//===----------------------------------------------------------------------===//
// Primitives used for constructing summaries for function/method calls.
//===----------------------------------------------------------------------===//

namespace {
/// ArgEffect is used to summarize a function/method call's effect on a
/// particular argument.
enum ArgEffect { IncRef, DecRef, DoNothing, DoNothingByRef,
                 StopTracking, MayEscape, SelfOwn, Autorelease };

/// ArgEffects summarizes the effects of a function/method call on all of
/// its arguments.
typedef std::vector<std::pair<unsigned,ArgEffect> > ArgEffects;
}

namespace llvm {
template <> struct FoldingSetTrait<ArgEffects> {
  static void Profile(const ArgEffects& X, FoldingSetNodeID& ID) {
    for (ArgEffects::const_iterator I = X.begin(), E = X.end(); I!= E; ++I) {
      ID.AddInteger(I->first);
      ID.AddInteger((unsigned) I->second);
    }
  }    
};
} // end llvm namespace

namespace {

///  RetEffect is used to summarize a function/method call's behavior with
///  respect to its return value.  
class VISIBILITY_HIDDEN RetEffect {
public:
  enum Kind { NoRet, Alias, OwnedSymbol, OwnedAllocatedSymbol,
              NotOwnedSymbol, ReceiverAlias };
  
private:
  unsigned Data;
  RetEffect(Kind k, unsigned D = 0) { Data = (D << 3) | (unsigned) k; }
  
public:
  
  Kind getKind() const { return (Kind) (Data & 0x7); }
  
  unsigned getIndex() const { 
    assert(getKind() == Alias);
    return Data >> 3;
  }
  
  static RetEffect MakeAlias(unsigned Idx) {
    return RetEffect(Alias, Idx);
  }
  static RetEffect MakeReceiverAlias() {
    return RetEffect(ReceiverAlias);
  }  
  static RetEffect MakeOwned(bool isAllocated = false) {
    return RetEffect(isAllocated ? OwnedAllocatedSymbol : OwnedSymbol);
  }  
  static RetEffect MakeNotOwned() {
    return RetEffect(NotOwnedSymbol);
  }  
  static RetEffect MakeNoRet() {
    return RetEffect(NoRet);
  }
  
  operator Kind() const {
    return getKind();
  }  
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger(Data);
  }
};
  
  
class VISIBILITY_HIDDEN RetainSummary : public llvm::FoldingSetNode {
  /// Args - an ordered vector of (index, ArgEffect) pairs, where index
  ///  specifies the argument (starting from 0).  This can be sparsely
  ///  populated; arguments with no entry in Args use 'DefaultArgEffect'.
  ArgEffects* Args;
  
  /// DefaultArgEffect - The default ArgEffect to apply to arguments that
  ///  do not have an entry in Args.
  ArgEffect   DefaultArgEffect;
  
  /// Receiver - If this summary applies to an Objective-C message expression,
  ///  this is the effect applied to the state of the receiver.
  ArgEffect   Receiver;
  
  /// Ret - The effect on the return value.  Used to indicate if the
  ///  function/method call returns a new tracked symbol, returns an
  ///  alias of one of the arguments in the call, and so on.
  RetEffect   Ret;
  
  /// EndPath - Indicates that execution of this method/function should
  ///  terminate the simulation of a path.
  bool EndPath;
  
public:
  
  RetainSummary(ArgEffects* A, RetEffect R, ArgEffect defaultEff,
                ArgEffect ReceiverEff, bool endpath = false)
    : Args(A), DefaultArgEffect(defaultEff), Receiver(ReceiverEff), Ret(R),
      EndPath(endpath) {}  
  
  /// getArg - Return the argument effect on the argument specified by
  ///  idx (starting from 0).
  ArgEffect getArg(unsigned idx) const {

    if (!Args)
      return DefaultArgEffect;
    
    // If Args is present, it is likely to contain only 1 element.
    // Just do a linear search.  Do it from the back because functions with
    // large numbers of arguments will be tail heavy with respect to which
    // argument they actually modify with respect to the reference count.    
    for (ArgEffects::reverse_iterator I=Args->rbegin(), E=Args->rend();
           I!=E; ++I) {
      
      if (idx > I->first)
        return DefaultArgEffect;
      
      if (idx == I->first)
        return I->second;
    }
    
    return DefaultArgEffect;
  }
  
  /// getRetEffect - Returns the effect on the return value of the call.
  RetEffect getRetEffect() const {
    return Ret;
  }
  
  /// isEndPath - Returns true if executing the given method/function should
  ///  terminate the path.
  bool isEndPath() const { return EndPath; }
  
  /// getReceiverEffect - Returns the effect on the receiver of the call.
  ///  This is only meaningful if the summary applies to an ObjCMessageExpr*.
  ArgEffect getReceiverEffect() const {
    return Receiver;
  }
  
  typedef ArgEffects::const_iterator ExprIterator;
  
  ExprIterator begin_args() const { return Args->begin(); }
  ExprIterator end_args()   const { return Args->end(); }
  
  static void Profile(llvm::FoldingSetNodeID& ID, ArgEffects* A,
                      RetEffect RetEff, ArgEffect DefaultEff,
                      ArgEffect ReceiverEff, bool EndPath) {
    ID.AddPointer(A);
    ID.Add(RetEff);
    ID.AddInteger((unsigned) DefaultEff);
    ID.AddInteger((unsigned) ReceiverEff);
    ID.AddInteger((unsigned) EndPath);
  }
      
  void Profile(llvm::FoldingSetNodeID& ID) const {
    Profile(ID, Args, Ret, DefaultArgEffect, Receiver, EndPath);
  }
};
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Data structures for constructing summaries.
//===----------------------------------------------------------------------===//

namespace {
class VISIBILITY_HIDDEN ObjCSummaryKey {
  IdentifierInfo* II;
  Selector S;
public:    
  ObjCSummaryKey(IdentifierInfo* ii, Selector s)
    : II(ii), S(s) {}

  ObjCSummaryKey(ObjCInterfaceDecl* d, Selector s)
    : II(d ? d->getIdentifier() : 0), S(s) {}
  
  ObjCSummaryKey(Selector s)
    : II(0), S(s) {}
  
  IdentifierInfo* getIdentifier() const { return II; }
  Selector getSelector() const { return S; }
};
}

namespace llvm {
template <> struct DenseMapInfo<ObjCSummaryKey> {
  static inline ObjCSummaryKey getEmptyKey() {
    return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getEmptyKey(),
                          DenseMapInfo<Selector>::getEmptyKey());
  }
    
  static inline ObjCSummaryKey getTombstoneKey() {
    return ObjCSummaryKey(DenseMapInfo<IdentifierInfo*>::getTombstoneKey(),
                          DenseMapInfo<Selector>::getTombstoneKey());      
  }
  
  static unsigned getHashValue(const ObjCSummaryKey &V) {
    return (DenseMapInfo<IdentifierInfo*>::getHashValue(V.getIdentifier())
            & 0x88888888) 
        | (DenseMapInfo<Selector>::getHashValue(V.getSelector())
            & 0x55555555);
  }
  
  static bool isEqual(const ObjCSummaryKey& LHS, const ObjCSummaryKey& RHS) {
    return DenseMapInfo<IdentifierInfo*>::isEqual(LHS.getIdentifier(),
                                                  RHS.getIdentifier()) &&
           DenseMapInfo<Selector>::isEqual(LHS.getSelector(),
                                           RHS.getSelector());
  }
  
  static bool isPod() {
    return DenseMapInfo<ObjCInterfaceDecl*>::isPod() &&
           DenseMapInfo<Selector>::isPod();
  }
};
} // end llvm namespace
  
namespace {
class VISIBILITY_HIDDEN ObjCSummaryCache {
  typedef llvm::DenseMap<ObjCSummaryKey, RetainSummary*> MapTy;
  MapTy M;
public:
  ObjCSummaryCache() {}
  
  typedef MapTy::iterator iterator;
  
  iterator find(ObjCInterfaceDecl* D, Selector S) {
    
    // Do a lookup with the (D,S) pair.  If we find a match return
    // the iterator.
    ObjCSummaryKey K(D, S);
    MapTy::iterator I = M.find(K);
    
    if (I != M.end() || !D)
      return I;
    
    // Walk the super chain.  If we find a hit with a parent, we'll end
    // up returning that summary.  We actually allow that key (null,S), as
    // we cache summaries for the null ObjCInterfaceDecl* to allow us to
    // generate initial summaries without having to worry about NSObject
    // being declared.
    // FIXME: We may change this at some point.
    for (ObjCInterfaceDecl* C=D->getSuperClass() ;; C=C->getSuperClass()) {
      if ((I = M.find(ObjCSummaryKey(C, S))) != M.end())
        break;
      
      if (!C)
        return I;
    }
    
    // Cache the summary with original key to make the next lookup faster 
    // and return the iterator.
    M[K] = I->second;
    return I;
  }
  

  iterator find(Expr* Receiver, Selector S) {
    return find(getReceiverDecl(Receiver), S);
  }
  
  iterator find(IdentifierInfo* II, Selector S) {
    // FIXME: Class method lookup.  Right now we dont' have a good way
    // of going between IdentifierInfo* and the class hierarchy.
    iterator I = M.find(ObjCSummaryKey(II, S));
    return I == M.end() ? M.find(ObjCSummaryKey(S)) : I;
  }
  
  ObjCInterfaceDecl* getReceiverDecl(Expr* E) {
    
    const PointerType* PT = E->getType()->getAsPointerType();
    if (!PT) return 0;
    
    ObjCInterfaceType* OI = dyn_cast<ObjCInterfaceType>(PT->getPointeeType());
    if (!OI) return 0;
    
    return OI ? OI->getDecl() : 0;
  }
  
  iterator end() { return M.end(); }
  
  RetainSummary*& operator[](ObjCMessageExpr* ME) {
    
    Selector S = ME->getSelector();
    
    if (Expr* Receiver = ME->getReceiver()) {
      ObjCInterfaceDecl* OD = getReceiverDecl(Receiver);
      return OD ? M[ObjCSummaryKey(OD->getIdentifier(), S)] : M[S];
    }
    
    return M[ObjCSummaryKey(ME->getClassName(), S)];
  }
  
  RetainSummary*& operator[](ObjCSummaryKey K) {
    return M[K];
  }
  
  RetainSummary*& operator[](Selector S) {
    return M[ ObjCSummaryKey(S) ];
  }
};   
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Data structures for managing collections of summaries.
//===----------------------------------------------------------------------===//

namespace {
class VISIBILITY_HIDDEN RetainSummaryManager {

  //==-----------------------------------------------------------------==//
  //  Typedefs.
  //==-----------------------------------------------------------------==//
  
  typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<ArgEffects> >
          ArgEffectsSetTy;
  
  typedef llvm::FoldingSet<RetainSummary>
          SummarySetTy;
  
  typedef llvm::DenseMap<FunctionDecl*, RetainSummary*>
          FuncSummariesTy;
  
  typedef ObjCSummaryCache ObjCMethodSummariesTy;
    
  //==-----------------------------------------------------------------==//
  //  Data.
  //==-----------------------------------------------------------------==//
  
  /// Ctx - The ASTContext object for the analyzed ASTs.
  ASTContext& Ctx;

  /// CFDictionaryCreateII - An IdentifierInfo* representing the indentifier
  ///  "CFDictionaryCreate".
  IdentifierInfo* CFDictionaryCreateII;
  
  /// GCEnabled - Records whether or not the analyzed code runs in GC mode.
  const bool GCEnabled;
  
  /// SummarySet - A FoldingSet of uniqued summaries.
  SummarySetTy SummarySet;
  
  /// FuncSummaries - A map from FunctionDecls to summaries.
  FuncSummariesTy FuncSummaries; 
  
  /// ObjCClassMethodSummaries - A map from selectors (for instance methods)
  ///  to summaries.
  ObjCMethodSummariesTy ObjCClassMethodSummaries;

  /// ObjCMethodSummaries - A map from selectors to summaries.
  ObjCMethodSummariesTy ObjCMethodSummaries;

  /// ArgEffectsSet - A FoldingSet of uniqued ArgEffects.
  ArgEffectsSetTy ArgEffectsSet;
  
  /// BPAlloc - A BumpPtrAllocator used for allocating summaries, ArgEffects,
  ///  and all other data used by the checker.
  llvm::BumpPtrAllocator BPAlloc;
  
  /// ScratchArgs - A holding buffer for construct ArgEffects.
  ArgEffects ScratchArgs;
  
  RetainSummary* StopSummary;
  
  //==-----------------------------------------------------------------==//
  //  Methods.
  //==-----------------------------------------------------------------==//
  
  /// getArgEffects - Returns a persistent ArgEffects object based on the
  ///  data in ScratchArgs.
  ArgEffects*   getArgEffects();

  enum UnaryFuncKind { cfretain, cfrelease, cfmakecollectable };  
  
public:
  RetainSummary* getUnarySummary(FunctionDecl* FD, UnaryFuncKind func);
  
  RetainSummary* getNSSummary(FunctionDecl* FD, const char* FName);
  RetainSummary* getCFSummary(FunctionDecl* FD, const char* FName);
  RetainSummary* getCGSummary(FunctionDecl* FD, const char* FName);
  
  RetainSummary* getCFSummaryCreateRule(FunctionDecl* FD);
  RetainSummary* getCFSummaryGetRule(FunctionDecl* FD);  
  RetainSummary* getCFCreateGetRuleSummary(FunctionDecl* FD, const char* FName);  
  
  RetainSummary* getPersistentSummary(ArgEffects* AE, RetEffect RetEff,
                                      ArgEffect ReceiverEff = DoNothing,
                                      ArgEffect DefaultEff = MayEscape,
                                      bool isEndPath = false);
                 
  RetainSummary* getPersistentSummary(RetEffect RE,
                                      ArgEffect ReceiverEff = DoNothing,
                                      ArgEffect DefaultEff = MayEscape) {
    return getPersistentSummary(getArgEffects(), RE, ReceiverEff, DefaultEff);
  }
  
  RetainSummary* getPersistentStopSummary() {
    if (StopSummary)
      return StopSummary;
    
    StopSummary = getPersistentSummary(RetEffect::MakeNoRet(),
                                       StopTracking, StopTracking);
    
    return StopSummary;
  }  

  RetainSummary* getInitMethodSummary(ObjCMessageExpr* ME);

  void InitializeClassMethodSummaries();
  void InitializeMethodSummaries();
  
private:
  
  void addClsMethSummary(IdentifierInfo* ClsII, Selector S,
                         RetainSummary* Summ) {
    ObjCClassMethodSummaries[ObjCSummaryKey(ClsII, S)] = Summ;
  }
  
  void addNSObjectClsMethSummary(Selector S, RetainSummary *Summ) {
    ObjCClassMethodSummaries[S] = Summ;
  }
    
  void addNSObjectMethSummary(Selector S, RetainSummary *Summ) {
    ObjCMethodSummaries[S] = Summ;
  }
  
  void addInstMethSummary(const char* Cls, RetainSummary* Summ, va_list argp) {
    
    IdentifierInfo* ClsII = &Ctx.Idents.get(Cls);
    llvm::SmallVector<IdentifierInfo*, 10> II;
    
    while (const char* s = va_arg(argp, const char*))
      II.push_back(&Ctx.Idents.get(s));
    
    Selector S = Ctx.Selectors.getSelector(II.size(), &II[0]);
    ObjCMethodSummaries[ObjCSummaryKey(ClsII, S)] = Summ;
  }
  
  void addInstMethSummary(const char* Cls, RetainSummary* Summ, ...) {
    va_list argp;
    va_start(argp, Summ);
    addInstMethSummary(Cls, Summ, argp);
    va_end(argp);    
  }
          
  void addPanicSummary(const char* Cls, ...) {
    RetainSummary* Summ = getPersistentSummary(0, RetEffect::MakeNoRet(),
                                               DoNothing,  DoNothing, true);
    va_list argp;
    va_start (argp, Cls);
    addInstMethSummary(Cls, Summ, argp);
    va_end(argp);
  }  
  
public:
  
  RetainSummaryManager(ASTContext& ctx, bool gcenabled)
   : Ctx(ctx),
     CFDictionaryCreateII(&ctx.Idents.get("CFDictionaryCreate")),
     GCEnabled(gcenabled), StopSummary(0) {

    InitializeClassMethodSummaries();
    InitializeMethodSummaries();
  }
  
  ~RetainSummaryManager();
  
  RetainSummary* getSummary(FunctionDecl* FD);  
  RetainSummary* getMethodSummary(ObjCMessageExpr* ME, ObjCInterfaceDecl* ID);
  RetainSummary* getClassMethodSummary(IdentifierInfo* ClsName, Selector S);
  
  bool isGCEnabled() const { return GCEnabled; }
};
  
} // end anonymous namespace

//===----------------------------------------------------------------------===//
// Implementation of checker data structures.
//===----------------------------------------------------------------------===//

RetainSummaryManager::~RetainSummaryManager() {
  
  // FIXME: The ArgEffects could eventually be allocated from BPAlloc, 
  //   mitigating the need to do explicit cleanup of the
  //   Argument-Effect summaries.
  
  for (ArgEffectsSetTy::iterator I = ArgEffectsSet.begin(), 
                                 E = ArgEffectsSet.end(); I!=E; ++I)
    I->getValue().~ArgEffects();
}

ArgEffects* RetainSummaryManager::getArgEffects() {

  if (ScratchArgs.empty())
    return NULL;
  
  // Compute a profile for a non-empty ScratchArgs.
  llvm::FoldingSetNodeID profile;
  profile.Add(ScratchArgs);
  void* InsertPos;
  
  // Look up the uniqued copy, or create a new one.
  llvm::FoldingSetNodeWrapper<ArgEffects>* E =
    ArgEffectsSet.FindNodeOrInsertPos(profile, InsertPos);
  
  if (E) {
    ScratchArgs.clear();
    return &E->getValue();
  }
  
  E = (llvm::FoldingSetNodeWrapper<ArgEffects>*)
        BPAlloc.Allocate<llvm::FoldingSetNodeWrapper<ArgEffects> >();
                       
  new (E) llvm::FoldingSetNodeWrapper<ArgEffects>(ScratchArgs);
  ArgEffectsSet.InsertNode(E, InsertPos);

  ScratchArgs.clear();
  return &E->getValue();
}

RetainSummary*
RetainSummaryManager::getPersistentSummary(ArgEffects* AE, RetEffect RetEff,
                                           ArgEffect ReceiverEff,
                                           ArgEffect DefaultEff,
                                           bool isEndPath) {
  
  // Generate a profile for the summary.
  llvm::FoldingSetNodeID profile;
  RetainSummary::Profile(profile, AE, RetEff, DefaultEff, ReceiverEff,
                         isEndPath);
  
  // Look up the uniqued summary, or create one if it doesn't exist.
  void* InsertPos;  
  RetainSummary* Summ = SummarySet.FindNodeOrInsertPos(profile, InsertPos);
  
  if (Summ)
    return Summ;
  
  // Create the summary and return it.
  Summ = (RetainSummary*) BPAlloc.Allocate<RetainSummary>();
  new (Summ) RetainSummary(AE, RetEff, DefaultEff, ReceiverEff, isEndPath);
  SummarySet.InsertNode(Summ, InsertPos);
  
  return Summ;
}

//===----------------------------------------------------------------------===//
// Summary creation for functions (largely uses of Core Foundation).
//===----------------------------------------------------------------------===//

RetainSummary* RetainSummaryManager::getSummary(FunctionDecl* FD) {

  SourceLocation Loc = FD->getLocation();
  
  if (!Loc.isFileID())
    return NULL;
  
  // Look up a summary in our cache of FunctionDecls -> Summaries.
  FuncSummariesTy::iterator I = FuncSummaries.find(FD);

  if (I != FuncSummaries.end())
    return I->second;

  // No summary.  Generate one.
  const char* FName = FD->getIdentifier()->getName();
    
  RetainSummary *S = 0;
  
  FunctionType* FT = dyn_cast<FunctionType>(FD->getType());

  do {
    if (FT) {
      
      QualType T = FT->getResultType();
      
      if (isCFRefType(T)) {
        S = getCFSummary(FD, FName);
        break;
      }
      
      if (isCGRefType(T)) {
        S = getCGSummary(FD, FName );
        break;
      }
    }

    if (FName[0] == 'C') {
      if (FName[1] == 'F')
        S = getCFSummary(FD, FName);  
      else if (FName[1] == 'G')
        S = getCGSummary(FD, FName);
    }
    else if (FName[0] == 'N' && FName[1] == 'S')
      S = getNSSummary(FD, FName);
  }
  while (0);

  FuncSummaries[FD] = S;
  return S;  
}

RetainSummary* RetainSummaryManager::getNSSummary(FunctionDecl* FD,
                                                  const char* FName) {
  FName += 2;
  
  if (strcmp(FName, "MakeCollectable") == 0)
    return getUnarySummary(FD, cfmakecollectable);

  return 0;  
}

static bool isRetain(FunctionDecl* FD, const char* FName) {
  const char* loc = strstr(FName, "Retain");
  return loc && loc[sizeof("Retain")-1] == '\0';
}

static bool isRelease(FunctionDecl* FD, const char* FName) {
  const char* loc = strstr(FName, "Release");
  return loc && loc[sizeof("Release")-1] == '\0';
}

RetainSummary* RetainSummaryManager::getCFSummary(FunctionDecl* FD,
                                                  const char* FName) {

  if (FName[0] == 'C' && FName[1] == 'F')
    FName += 2;

  if (isRetain(FD, FName))
    return getUnarySummary(FD, cfretain);
  
  if (isRelease(FD, FName))
    return getUnarySummary(FD, cfrelease);
  
  if (strcmp(FName, "MakeCollectable") == 0)
    return getUnarySummary(FD, cfmakecollectable);

  return getCFCreateGetRuleSummary(FD, FName);
}

RetainSummary* RetainSummaryManager::getCGSummary(FunctionDecl* FD,
                                                  const char* FName) {
  
  if (FName[0] == 'C' && FName[1] == 'G')
    FName += 2;
  
  if (isRelease(FD, FName))
    return getUnarySummary(FD, cfrelease);
  
  if (isRetain(FD, FName))
    return getUnarySummary(FD, cfretain);
  
  return getCFCreateGetRuleSummary(FD, FName);
}

RetainSummary*
RetainSummaryManager::getCFCreateGetRuleSummary(FunctionDecl* FD,
                                                const char* FName) {
  
  if (strstr(FName, "Create") || strstr(FName, "Copy"))
    return getCFSummaryCreateRule(FD);
  
  if (strstr(FName, "Get"))
    return getCFSummaryGetRule(FD);
  
  return 0;
}

RetainSummary*
RetainSummaryManager::getUnarySummary(FunctionDecl* FD, UnaryFuncKind func) {
  
  FunctionTypeProto* FT =
    dyn_cast<FunctionTypeProto>(FD->getType().getTypePtr());
  
  if (FT) {
    
    if (FT->getNumArgs() != 1)
      return 0;
  
    TypedefType* ArgT = dyn_cast<TypedefType>(FT->getArgType(0).getTypePtr());
  
    if (!ArgT)
      return 0;

    if (!ArgT->isPointerType())
      return NULL;
  }
  
  assert (ScratchArgs.empty());
  
  switch (func) {
    case cfretain: {
      ScratchArgs.push_back(std::make_pair(0, IncRef));
      return getPersistentSummary(RetEffect::MakeAlias(0),
                                  DoNothing, DoNothing);
    }
      
    case cfrelease: {
      ScratchArgs.push_back(std::make_pair(0, DecRef));
      return getPersistentSummary(RetEffect::MakeNoRet(),
                                  DoNothing, DoNothing);
    }
      
    case cfmakecollectable: {
      if (GCEnabled)
        ScratchArgs.push_back(std::make_pair(0, DecRef));
      
      return getPersistentSummary(RetEffect::MakeAlias(0),
                                  DoNothing, DoNothing);    
    }
      
    default:
      assert (false && "Not a supported unary function.");
      return 0;
  }
}

RetainSummary* RetainSummaryManager::getCFSummaryCreateRule(FunctionDecl* FD) {
 
  FunctionType* FT =
    dyn_cast<FunctionType>(FD->getType().getTypePtr());

  if (FT) {
    QualType ResTy = FT->getResultType();
    
    if (!isCFRefType(ResTy) && !isCGRefType(ResTy))
      return getPersistentSummary(RetEffect::MakeNoRet());
  }
  
  assert (ScratchArgs.empty());
  
  if (FD->getIdentifier() == CFDictionaryCreateII) {
    ScratchArgs.push_back(std::make_pair(1, DoNothingByRef));
    ScratchArgs.push_back(std::make_pair(2, DoNothingByRef));
  }
  
  return getPersistentSummary(RetEffect::MakeOwned(true));
}

RetainSummary* RetainSummaryManager::getCFSummaryGetRule(FunctionDecl* FD) {
  
  FunctionType* FT =
    dyn_cast<FunctionType>(FD->getType().getTypePtr());
  
  if (FT) {
    QualType RetTy = FT->getResultType();
  
    // FIXME: For now we assume that all pointer types returned are referenced
    // counted.  Since this is the "Get" rule, we assume non-ownership, which
    // works fine for things that are not reference counted.  We do this because
    // some generic data structures return "void*".  We need something better
    // in the future.
  
    if (!isCFRefType(RetTy) && !RetTy->isPointerType())
      return getPersistentSummary(RetEffect::MakeNoRet(), DoNothing, DoNothing);
  }
  
  // FIXME: Add special-cases for functions that retain/release.  For now
  //  just handle the default case.
  
  assert (ScratchArgs.empty());  
  return getPersistentSummary(RetEffect::MakeNotOwned(), DoNothing, DoNothing);
}

//===----------------------------------------------------------------------===//
// Summary creation for Selectors.
//===----------------------------------------------------------------------===//

RetainSummary*
RetainSummaryManager::getInitMethodSummary(ObjCMessageExpr* ME) {
  assert(ScratchArgs.empty());
    
  RetainSummary* Summ =
    getPersistentSummary(RetEffect::MakeReceiverAlias());
  
  ObjCMethodSummaries[ME] = Summ;
  return Summ;
}


RetainSummary*
RetainSummaryManager::getMethodSummary(ObjCMessageExpr* ME,
                                       ObjCInterfaceDecl* ID) {

  Selector S = ME->getSelector();
  
  // Look up a summary in our summary cache.  
  ObjCMethodSummariesTy::iterator I = ObjCMethodSummaries.find(ID, S);
  
  if (I != ObjCMethodSummaries.end())
    return I->second;
    
  if (!ME->getType()->isPointerType())
    return 0;
  
  // "initXXX": pass-through for receiver.

  const char* s = S.getIdentifierInfoForSlot(0)->getName();
  assert (ScratchArgs.empty());
  
  if (strncmp(s, "init", 4) == 0 || strncmp(s, "_init", 5) == 0)
    return getInitMethodSummary(ME);  
  
  // "copyXXX", "createXXX", "newXXX": allocators.  

  if (!isNSType(ME->getReceiver()->getType()))
    return 0;
  
  if (followsFundamentalRule(s)) {
    
    RetEffect E = isGCEnabled() ? RetEffect::MakeNoRet()
                                : RetEffect::MakeOwned(true);  

    RetainSummary* Summ = getPersistentSummary(E);
    ObjCMethodSummaries[ME] = Summ;
    return Summ;
  }
  
  return 0;
}

RetainSummary*
RetainSummaryManager::getClassMethodSummary(IdentifierInfo* ClsName,
                                            Selector S) {
  
  // FIXME: Eventually we should properly do class method summaries, but
  // it requires us being able to walk the type hierarchy.  Unfortunately,
  // we cannot do this with just an IdentifierInfo* for the class name.
  
  // Look up a summary in our cache of Selectors -> Summaries.
  ObjCMethodSummariesTy::iterator I = ObjCClassMethodSummaries.find(ClsName, S);
  
  if (I != ObjCClassMethodSummaries.end())
    return I->second;
  
  return 0;
}

void RetainSummaryManager::InitializeClassMethodSummaries() {
  
  assert (ScratchArgs.empty());
  
  RetEffect E = isGCEnabled() ? RetEffect::MakeNoRet()
                              : RetEffect::MakeOwned(true);  
  
  RetainSummary* Summ = getPersistentSummary(E);
  
  // Create the summaries for "alloc", "new", and "allocWithZone:" for
  // NSObject and its derivatives.
  addNSObjectClsMethSummary(GetNullarySelector("alloc", Ctx), Summ);
  addNSObjectClsMethSummary(GetNullarySelector("new", Ctx), Summ);
  addNSObjectClsMethSummary(GetUnarySelector("allocWithZone", Ctx), Summ);
  
  // Create the [NSAssertionHandler currentHander] summary.  
  addClsMethSummary(&Ctx.Idents.get("NSAssertionHandler"),