Split libAnalysis into two libraries: libAnalysis and libChecker.

(1) libAnalysis is a generic analysis library that can be used by
    Sema.  It defines the CFG, basic dataflow analysis primitives, and
    inexpensive flow-sensitive analyses (e.g. LiveVariables).

(2) libChecker contains the guts of the static analyzer, incuding the
    path-sensitive analysis engine and domain-specific checks.

Now any clients that want to use the frontend to build their own tools
don't need to link in the entire static analyzer.

This change exposes various obvious cleanups that can be made to the
layout of files and headers in libChecker.  More changes pending.  :)

This change also exposed a layering violation between AnalysisContext
and MemRegion.  BlockInvocationContext shouldn't explicitly know about
BlockDataRegions.  For now I've removed the BlockDataRegion* from
BlockInvocationContext (removing context-sensitivity; although this
wasn't used yet).  We need to have a better way to extend
BlockInvocationContext (and any LocationContext) to add
context-sensitivty.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@94406 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 3790 insertions, 0 deletions

diff --git a/lib/Checker/CFRefCount.cpp b/lib/Checker/CFRefCount.cpp
new file mode 100644
index 0000000000..a128f9048d
--- /dev/null
+++ b/lib/Checker/CFRefCount.cpp
@@ -0,0 +1,3790 @@
+// 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 "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Checker/PathSensitive/GRExprEngineBuilders.h"
+#include "clang/Checker/PathSensitive/GRStateTrait.h"
+#include "clang/Checker/PathDiagnostic.h"
+#include "clang/Checker/LocalCheckers.h"
+#include "clang/Checker/PathDiagnostic.h"
+#include "clang/Checker/PathSensitive/BugReporter.h"
+#include "clang/Checker/PathSensitive/SymbolManager.h"
+#include "clang/Checker/PathSensitive/GRTransferFuncs.h"
+#include "clang/Checker/PathSensitive/CheckerVisitor.h"
+#include "clang/AST/DeclObjC.h"
+#include "clang/AST/StmtVisitor.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/ADT/STLExtras.h"
+#include <stdarg.h>
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Utility functions.
+//===----------------------------------------------------------------------===//
+
+// 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."
+//
+
+using llvm::StrInStrNoCase;
+using llvm::StringRef;
+
+enum NamingConvention { NoConvention, CreateRule, InitRule };
+
+static inline bool isWordEnd(char ch, char prev, char next) {
+  return ch == '\0'
+      || (islower(prev) && isupper(ch)) // xxxC
+      || (isupper(prev) && isupper(ch) && islower(next)) // XXCreate
+      || !isalpha(ch);
+}
+
+static inline const char* parseWord(const char* s) {
+  char ch = *s, prev = '\0';
+  assert(ch != '\0');
+  char next = *(s+1);
+  while (!isWordEnd(ch, prev, next)) {
+    prev = ch;
+    ch = next;
+    next = *((++s)+1);
+  }
+  return s;
+}
+
+static NamingConvention deriveNamingConvention(Selector S) {
+  IdentifierInfo *II = S.getIdentifierInfoForSlot(0);
+
+  if (!II)
+    return NoConvention;
+
+  const char *s = II->getNameStart();
+
+  // A method/function name may contain a prefix.  We don't know it is there,
+  // however, until we encounter the first '_'.
+  bool InPossiblePrefix = true;
+  bool AtBeginning = true;
+  NamingConvention C = NoConvention;
+
+  while (*s != '\0') {
+    // Skip '_'.
+    if (*s == '_') {
+      if (InPossiblePrefix) {
+        // If we already have a convention, return it.  Otherwise, skip
+        // the prefix as if it wasn't there.
+        if (C != NoConvention)
+          break;
+        
+        InPossiblePrefix = false;
+        AtBeginning = true;
+        assert(C == NoConvention);
+      }
+      ++s;
+      continue;
+    }
+
+    // Skip numbers, ':', etc.
+    if (!isalpha(*s)) {
+      ++s;
+      continue;
+    }
+
+    const char *wordEnd = parseWord(s);
+    assert(wordEnd > s);
+    unsigned len = wordEnd - s;
+
+    switch (len) {
+    default:
+      break;
+    case 3:
+      // Methods starting with 'new' follow the create rule.
+      if (AtBeginning && StringRef(s, len).equals_lower("new"))
+        C = CreateRule;
+      break;
+    case 4:
+      // Methods starting with 'alloc' or contain 'copy' follow the
+      // create rule
+      if (C == NoConvention && StringRef(s, len).equals_lower("copy"))
+        C = CreateRule;
+      else // Methods starting with 'init' follow the init rule.
+        if (AtBeginning && StringRef(s, len).equals_lower("init"))
+          C = InitRule;
+      break;
+    case 5:
+      if (AtBeginning && StringRef(s, len).equals_lower("alloc"))
+        C = CreateRule;
+      break;
+    }
+
+    // If we aren't in the prefix and have a derived convention then just
+    // return it now.
+    if (!InPossiblePrefix && C != NoConvention)
+      return C;
+
+    AtBeginning = false;
+    s = wordEnd;
+  }
+
+  // We will get here if there wasn't more than one word
+  // after the prefix.
+  return C;
+}
+
+static bool followsFundamentalRule(Selector S) {
+  return deriveNamingConvention(S) == CreateRule;
+}
+
+static const ObjCMethodDecl*
+ResolveToInterfaceMethodDecl(const ObjCMethodDecl *MD) {
+  ObjCInterfaceDecl *ID =
+    const_cast<ObjCInterfaceDecl*>(MD->getClassInterface());
+
+  return MD->isInstanceMethod()
+         ? ID->lookupInstanceMethod(MD->getSelector())
+         : ID->lookupClassMethod(MD->getSelector());
+}
+
+namespace {
+class GenericNodeBuilder {
+  GRStmtNodeBuilder *SNB;
+  Stmt *S;
+  const void *tag;
+  GREndPathNodeBuilder *ENB;
+public:
+  GenericNodeBuilder(GRStmtNodeBuilder &snb, Stmt *s,
+                     const void *t)
+  : SNB(&snb), S(s), tag(t), ENB(0) {}
+
+  GenericNodeBuilder(GREndPathNodeBuilder &enb)
+  : SNB(0), S(0), tag(0), ENB(&enb) {}
+
+  ExplodedNode *MakeNode(const GRState *state, ExplodedNode *Pred) {
+    if (SNB)
+      return SNB->generateNode(PostStmt(S, Pred->getLocationContext(), tag),
+                               state, Pred);
+
+    assert(ENB);
+    return ENB->generateNode(state, Pred);
+  }
+};
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Type querying functions.
+//===----------------------------------------------------------------------===//
+
+static bool isRefType(QualType RetTy, const char* prefix,
+                      ASTContext* Ctx = 0, const char* name = 0) {
+
+  // Recursively walk the typedef stack, allowing typedefs of reference types.
+  while (TypedefType* TD = dyn_cast<TypedefType>(RetTy.getTypePtr())) {
+    llvm::StringRef TDName = TD->getDecl()->getIdentifier()->getName();
+    if (TDName.startswith(prefix) && TDName.endswith("Ref"))
+      return true;
+
+    RetTy = TD->getDecl()->getUnderlyingType();
+  }
+
+  if (!Ctx || !name)
+    return false;
+
+  // Is the type void*?
+  const PointerType* PT = RetTy->getAs<PointerType>();
+  if (!(PT->getPointeeType().getUnqualifiedType() == Ctx->VoidTy))
+    return false;
+
+  // Does the name start with the prefix?
+  return llvm::StringRef(name).startswith(prefix);
+}
+
+//===----------------------------------------------------------------------===//
+// Primitives used for constructing summaries for function/method calls.
+//===----------------------------------------------------------------------===//
+
+/// ArgEffect is used to summarize a function/method call's effect on a
+/// particular argument.
+enum ArgEffect { Autorelease, Dealloc, DecRef, DecRefMsg, DoNothing,
+                 DoNothingByRef, IncRefMsg, IncRef, MakeCollectable, MayEscape,
+                 NewAutoreleasePool, SelfOwn, StopTracking };
+
+namespace llvm {
+template <> struct FoldingSetTrait<ArgEffect> {
+static inline void Profile(const ArgEffect X, FoldingSetNodeID& ID) {
+  ID.AddInteger((unsigned) X);
+}
+};
+} // end llvm namespace
+
+/// ArgEffects summarizes the effects of a function/method call on all of
+/// its arguments.
+typedef llvm::ImmutableMap<unsigned,ArgEffect> ArgEffects;
+
+namespace {
+
+///  RetEffect is used to summarize a function/method call's behavior with
+///  respect to its return value.
+class RetEffect {
+public:
+  enum Kind { NoRet, Alias, OwnedSymbol, OwnedAllocatedSymbol,
+              NotOwnedSymbol, GCNotOwnedSymbol, ReceiverAlias,
+              OwnedWhenTrackedReceiver };
+
+  enum ObjKind { CF, ObjC, AnyObj };
+
+private:
+  Kind K;
+  ObjKind O;
+  unsigned index;
+
+  RetEffect(Kind k, unsigned idx = 0) : K(k), O(AnyObj), index(idx) {}
+  RetEffect(Kind k, ObjKind o) : K(k), O(o), index(0) {}
+
+public:
+  Kind getKind() const { return K; }
+
+  ObjKind getObjKind() const { return O; }
+
+  unsigned getIndex() const {
+    assert(getKind() == Alias);
+    return index;
+  }
+
+  bool isOwned() const {
+    return K == OwnedSymbol || K == OwnedAllocatedSymbol ||
+           K == OwnedWhenTrackedReceiver;
+  }
+
+  static RetEffect MakeOwnedWhenTrackedReceiver() {
+    return RetEffect(OwnedWhenTrackedReceiver, ObjC);
+  }
+
+  static RetEffect MakeAlias(unsigned Idx) {
+    return RetEffect(Alias, Idx);
+  }
+  static RetEffect MakeReceiverAlias() {
+    return RetEffect(ReceiverAlias);
+  }
+  static RetEffect MakeOwned(ObjKind o, bool isAllocated = false) {
+    return RetEffect(isAllocated ? OwnedAllocatedSymbol : OwnedSymbol, o);
+  }
+  static RetEffect MakeNotOwned(ObjKind o) {
+    return RetEffect(NotOwnedSymbol, o);
+  }
+  static RetEffect MakeGCNotOwned() {
+    return RetEffect(GCNotOwnedSymbol, ObjC);
+  }
+
+  static RetEffect MakeNoRet() {
+    return RetEffect(NoRet);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& ID) const {
+    ID.AddInteger((unsigned)K);
+    ID.AddInteger((unsigned)O);
+    ID.AddInteger(index);
+  }
+};
+
+//===----------------------------------------------------------------------===//
+// Reference-counting logic (typestate + counts).
+//===----------------------------------------------------------------------===//
+
+class RefVal {
+public:
+  enum Kind {
+    Owned = 0, // Owning reference.
+    NotOwned,  // Reference is not owned by still valid (not freed).
+    Released,  // Object has been released.
+    ReturnedOwned, // Returned object passes ownership to caller.
+    ReturnedNotOwned, // Return object does not pass ownership to caller.
+    ERROR_START,
+    ErrorDeallocNotOwned, // -dealloc called on non-owned object.
+    ErrorDeallocGC, // Calling -dealloc with GC enabled.
+    ErrorUseAfterRelease, // Object used after released.
+    ErrorReleaseNotOwned, // Release of an object that was not owned.
+    ERROR_LEAK_START,
+    ErrorLeak,  // A memory leak due to excessive reference counts.
+    ErrorLeakReturned, // A memory leak due to the returning method not having
+                       // the correct naming conventions.
+    ErrorGCLeakReturned,
+    ErrorOverAutorelease,
+    ErrorReturnedNotOwned
+  };
+  
+private:
+  Kind kind;
+  RetEffect::ObjKind okind;
+  unsigned Cnt;
+  unsigned ACnt;
+  QualType T;
+  
+  RefVal(Kind k, RetEffect::ObjKind o, unsigned cnt, unsigned acnt, QualType t)
+  : kind(k), okind(o), Cnt(cnt), ACnt(acnt), T(t) {}
+  
+  RefVal(Kind k, unsigned cnt = 0)
+  : kind(k), okind(RetEffect::AnyObj), Cnt(cnt), ACnt(0) {}
+  
+public:
+  Kind getKind() const { return kind; }
+  
+  RetEffect::ObjKind getObjKind() const { return okind; }
+  
+  unsigned getCount() const { return Cnt; }
+  unsigned getAutoreleaseCount() const { return ACnt; }
+  unsigned getCombinedCounts() const { return Cnt + ACnt; }
+  void clearCounts() { Cnt = 0; ACnt = 0; }
+  void setCount(unsigned i) { Cnt = i; }
+  void setAutoreleaseCount(unsigned i) { ACnt = i; }
+  
+  QualType getType() const { return T; }
+  
+  // Useful predicates.
+  
+  static bool isError(Kind k) { return k >= ERROR_START; }
+  
+  static bool isLeak(Kind k) { return k >= ERROR_LEAK_START; }
+  
+  bool isOwned() const {
+    return getKind() == Owned;
+  }
+  
+  bool isNotOwned() const {
+    return getKind() == NotOwned;
+  }
+  
+  bool isReturnedOwned() const {
+    return getKind() == ReturnedOwned;
+  }
+  
+  bool isReturnedNotOwned() const {
+    return getKind() == ReturnedNotOwned;
+  }
+  
+  bool isNonLeakError() const {
+    Kind k = getKind();
+    return isError(k) && !isLeak(k);
+  }
+  
+  static RefVal makeOwned(RetEffect::ObjKind o, QualType t,
+                          unsigned Count = 1) {
+    return RefVal(Owned, o, Count, 0, t);
+  }
+  
+  static RefVal makeNotOwned(RetEffect::ObjKind o, QualType t,
+                             unsigned Count = 0) {
+    return RefVal(NotOwned, o, Count, 0, t);
+  }
+  
+  // Comparison, profiling, and pretty-printing.
+  
+  bool operator==(const RefVal& X) const {
+    return kind == X.kind && Cnt == X.Cnt && T == X.T && ACnt == X.ACnt;
+  }
+  
+  RefVal operator-(size_t i) const {
+    return RefVal(getKind(), getObjKind(), getCount() - i,
+                  getAutoreleaseCount(), getType());
+  }
+  
+  RefVal operator+(size_t i) const {
+    return RefVal(getKind(), getObjKind(), getCount() + i,
+                  getAutoreleaseCount(), getType());
+  }
+  
+  RefVal operator^(Kind k) const {
+    return RefVal(k, getObjKind(), getCount(), getAutoreleaseCount(),
+                  getType());
+  }
+  
+  RefVal autorelease() const {
+    return RefVal(getKind(), getObjKind(), getCount(), getAutoreleaseCount()+1,
+                  getType());
+  }
+  
+  void Profile(llvm::FoldingSetNodeID& ID) const {
+    ID.AddInteger((unsigned) kind);
+    ID.AddInteger(Cnt);
+    ID.AddInteger(ACnt);
+    ID.Add(T);
+  }
+  
+  void print(llvm::raw_ostream& Out) const;
+};
+
+void RefVal::print(llvm::raw_ostream& Out) const {
+  if (!T.isNull())
+    Out << "Tracked Type:" << T.getAsString() << '\n';
+  
+  switch (getKind()) {
+    default: assert(false);
+    case Owned: {
+      Out << "Owned";
+      unsigned cnt = getCount();
+      if (cnt) Out << " (+ " << cnt << ")";
+      break;
+    }
+      
+    case NotOwned: {
+      Out << "NotOwned";
+      unsigned cnt = getCount();
+      if (cnt) Out << " (+ " << cnt << ")";
+      break;
+    }
+      
+    case ReturnedOwned: {
+      Out << "ReturnedOwned";
+      unsigned cnt = getCount();
+      if (cnt) Out << " (+ " << cnt << ")";
+      break;
+    }
+      
+    case ReturnedNotOwned: {
+      Out << "ReturnedNotOwned";
+      unsigned cnt = getCount();
+      if (cnt) Out << " (+ " << cnt << ")";
+      break;
+    }
+      
+    case Released:
+      Out << "Released";
+      break;
+      
+    case ErrorDeallocGC:
+      Out << "-dealloc (GC)";
+      break;
+      
+    case ErrorDeallocNotOwned:
+      Out << "-dealloc (not-owned)";
+      break;
+      
+    case ErrorLeak:
+      Out << "Leaked";
+      break;
+      
+    case ErrorLeakReturned:
+      Out << "Leaked (Bad naming)";
+      break;
+      
+    case ErrorGCLeakReturned:
+      Out << "Leaked (GC-ed at return)";
+      break;
+      
+    case ErrorUseAfterRelease:
+      Out << "Use-After-Release [ERROR]";
+      break;
+      
+    case ErrorReleaseNotOwned:
+      Out << "Release of Not-Owned [ERROR]";
+      break;
+      
+    case RefVal::ErrorOverAutorelease:
+      Out << "Over autoreleased";
+      break;
+      
+    case RefVal::ErrorReturnedNotOwned:
+      Out << "Non-owned object returned instead of owned";
+      break;
+  }
+  
+  if (ACnt) {
+    Out << " [ARC +" << ACnt << ']';
+  }
+}
+} //end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// RefBindings - State used to track object reference counts.
+//===----------------------------------------------------------------------===//
+
+typedef llvm::ImmutableMap<SymbolRef, RefVal> RefBindings;
+
+namespace clang {
+  template<>
+  struct GRStateTrait<RefBindings> : public GRStatePartialTrait<RefBindings> {
+    static void* GDMIndex() {
+      static int RefBIndex = 0;
+      return &RefBIndex;
+    }
+  };
+}
+
+//===----------------------------------------------------------------------===//
+// Summaries
+//===----------------------------------------------------------------------===//
+
+namespace {
+class RetainSummary {
+  /// 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 (const ArgEffect *AE = Args.lookup(idx))
+      return *AE;
+
+    return DefaultArgEffect;
+  }
+
+  /// setDefaultArgEffect - Set the default argument effect.
+  void setDefaultArgEffect(ArgEffect E) {
+    DefaultArgEffect = E;
+  }
+
+  /// setArg - Set the argument effect on the argument specified by idx.
+  void setArgEffect(ArgEffects::Factory& AF, unsigned idx, ArgEffect E) {
+    Args = AF.Add(Args, idx, E);
+  }
+
+  /// getRetEffect - Returns the effect on the return value of the call.
+  RetEffect getRetEffect() const { return Ret; }
+
+  /// setRetEffect - Set the effect of the return value of the call.
+  void setRetEffect(RetEffect E) { Ret = E; }
+
+  /// 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; }
+
+  /// setReceiverEffect - Set the effect on the receiver of the call.
+  void setReceiverEffect(ArgEffect E) { Receiver = E; }
+
+  typedef ArgEffects::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.Add(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 ObjCSummaryKey {
+  IdentifierInfo* II;
+  Selector S;
+public:
+  ObjCSummaryKey(IdentifierInfo* ii, Selector s)
+    : II(ii), S(s) {}
+
+  ObjCSummaryKey(const ObjCInterfaceDecl* d, Selector s)
+    : II(d ? d->getIdentifier() : 0), S(s) {}
+
+  ObjCSummaryKey(const ObjCInterfaceDecl* d, IdentifierInfo *ii, Selector s)
+    : II(d ? d->getIdentifier() : ii), 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());
+  }
+
+};
+template <>
+struct isPodLike<ObjCSummaryKey> { static const bool value = true; };
+} // end llvm namespace
+
+namespace {
+class ObjCSummaryCache {
+  typedef llvm::DenseMap<ObjCSummaryKey, RetainSummary*> MapTy;
+  MapTy M;
+public:
+  ObjCSummaryCache() {}
+
+  RetainSummary* find(const ObjCInterfaceDecl* D, IdentifierInfo *ClsName,
+                Selector S) {
+    // Lookup the method using the decl for the class @interface.  If we
+    // have no decl, lookup using the class name.
+    return D ? find(D, S) : find(ClsName, S);
+  }
+
+  RetainSummary* find(const 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->second;
+
+    // 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 NULL;
+    }
+
+    // Cache the summary with original key to make the next lookup faster
+    // and return the iterator.
+    RetainSummary *Summ = I->second;
+    M[K] = Summ;
+    return Summ;
+  }
+
+
+  RetainSummary* find(Expr* Receiver, Selector S) {
+    return find(getReceiverDecl(Receiver), S);
+  }
+
+  RetainSummary* 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.
+    MapTy::iterator I = M.find(ObjCSummaryKey(II, S));
+
+    if (I == M.end())
+      I = M.find(ObjCSummaryKey(S));
+
+    return I == M.end() ? NULL : I->second;
+  }
+
+  const ObjCInterfaceDecl* getReceiverDecl(Expr* E) {
+    if (const ObjCObjectPointerType* PT =
+        E->getType()->getAs<ObjCObjectPointerType>())
+      return PT->getInterfaceDecl();
+
+    return NULL;
+  }
+
+  RetainSummary*& operator[](ObjCMessageExpr* ME) {
+
+    Selector S = ME->getSelector();
+
+    if (Expr* Receiver = ME->getReceiver()) {
+      const 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 RetainSummaryManager {
+
+  //==-----------------------------------------------------------------==//
+  //  Typedefs.
+  //==-----------------------------------------------------------------==//
+
+  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;
+
+  /// 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;
+
+  /// BPAlloc - A BumpPtrAllocator used for allocating summaries, ArgEffects,
+  ///  and all other data used by the checker.
+  llvm::BumpPtrAllocator BPAlloc;
+
+  /// AF - A factory for ArgEffects objects.
+  ArgEffects::Factory AF;
+
+  /// ScratchArgs - A holding buffer for construct ArgEffects.
+  ArgEffects ScratchArgs;
+
+  /// ObjCAllocRetE - Default return effect for methods returning Objective-C
+  ///  objects.
+  RetEffect ObjCAllocRetE;
+
+  /// ObjCInitRetE - Default return effect for init methods returning
+  ///   Objective-C objects.
+  RetEffect ObjCInitRetE;
+
+  RetainSummary DefaultSummary;
+  RetainSummary* StopSummary;
+
+  //==-----------------------------------------------------------------==//
+  //  Methods.
+  //==-----------------------------------------------------------------==//
+
+  /// getArgEffects - Returns a persistent ArgEffects object based on the
+  ///  data in ScratchArgs.
+  ArgEffects getArgEffects();
+
+  enum UnaryFuncKind { cfretain, cfrelease, cfmakecollectable };
+
+public:
+  RetEffect getObjAllocRetEffect() const { return ObjCAllocRetE; }
+
+  RetainSummary *getDefaultSummary() {
+    RetainSummary *Summ = (RetainSummary*) BPAlloc.Allocate<RetainSummary>();
+    return new (Summ) RetainSummary(DefaultSummary);
+  }
+
+  RetainSummary* getUnarySummary(const FunctionType* FT, UnaryFuncKind func);
+
+  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(QualType RetTy);
+
+  void InitializeClassMethodSummaries();
+  void InitializeMethodSummaries();
+
+  bool isTrackedObjCObjectType(QualType T);
+  bool isTrackedCFObjectType(QualType T);
+
+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 addClassMethSummary(const char* Cls, const char* nullaryName,
+                           RetainSummary *Summ) {
+    IdentifierInfo* ClsII = &Ctx.Idents.get(Cls);
+    Selector S = GetNullarySelector(nullaryName, Ctx);
+    ObjCClassMethodSummaries[ObjCSummaryKey(ClsII, S)]  = Summ;
+  }
+
+  void addInstMethSummary(const char* Cls, const char* nullaryName,
+                          RetainSummary *Summ) {
+    IdentifierInfo* ClsII = &Ctx.Idents.get(Cls);
+    Selector S = GetNullarySelector(nullaryName, Ctx);
+    ObjCMethodSummaries[ObjCSummaryKey(ClsII, S)]  = Summ;
+  }
+
+  Selector generateSelector(va_list argp) {
+    llvm::SmallVector<IdentifierInfo*, 10> II;
+
+    while (const char* s = va_arg(argp, const char*))
+      II.push_back(&Ctx.Idents.get(s));
+
+    return Ctx.Selectors.getSelector(II.size(), &II[0]);
+  }
+
+  void addMethodSummary(IdentifierInfo *ClsII, ObjCMethodSummariesTy& Summaries,
+                        RetainSummary* Summ, va_list argp) {
+    Selector S = generateSelector(argp);
+    Summaries[ObjCSummaryKey(ClsII, S)] = Summ;
+  }
+
+  void addInstMethSummary(const char* Cls, RetainSummary* Summ, ...) {
+    va_list argp;
+    va_start(argp, Summ);
+    addMethodSummary(&Ctx.Idents.get(Cls), ObjCMethodSummaries, Summ, argp);
+    va_end(argp);
+  }
+
+  void addClsMethSummary(const char* Cls, RetainSummary* Summ, ...) {
+    va_list argp;
+    va_start(argp, Summ);
+    addMethodSummary(&Ctx.Idents.get(Cls),ObjCClassMethodSummaries, Summ, argp);
+    va_end(argp);
+  }
+
+  void addClsMethSummary(IdentifierInfo *II, RetainSummary* Summ, ...) {
+    va_list argp;
+    va_start(argp, Summ);
+    addMethodSummary(II, ObjCClassMethodSummaries, Summ, argp);
+    va_end(argp);
+  }
+
+  void addPanicSummary(const char* Cls, ...) {
+    RetainSummary* Summ = getPersistentSummary(AF.GetEmptyMap(),
+                                               RetEffect::MakeNoRet(),
+                                               DoNothing,  DoNothing, true);
+    va_list argp;
+    va_start (argp, Cls);
+    addMethodSummary(&Ctx.Idents.get(Cls), ObjCMethodSummaries, Summ, argp);
+    va_end(argp);
+  }
+
+public:
+
+  RetainSummaryManager(ASTContext& ctx, bool gcenabled)
+   : Ctx(ctx),
+     CFDictionaryCreateII(&ctx.Idents.get("CFDictionaryCreate")),
+     GCEnabled(gcenabled), AF(BPAlloc), ScratchArgs(AF.GetEmptyMap()),
+     ObjCAllocRetE(gcenabled ? RetEffect::MakeGCNotOwned()
+                             : RetEffect::MakeOwned(RetEffect::ObjC, true)),
+     ObjCInitRetE(gcenabled ? RetEffect::MakeGCNotOwned()
+                            : RetEffect::MakeOwnedWhenTrackedReceiver()),
+     DefaultSummary(AF.GetEmptyMap() /* per-argument effects (none) */,
+                    RetEffect::MakeNoRet() /* return effect */,
+                    MayEscape, /* default argument effect */
+                    DoNothing /* receiver effect */),
+     StopSummary(0) {
+
+    InitializeClassMethodSummaries();
+    InitializeMethodSummaries();
+  }
+
+  ~RetainSummaryManager();
+
+  RetainSummary* getSummary(FunctionDecl* FD);
+
+  RetainSummary *getInstanceMethodSummary(const ObjCMessageExpr *ME,
+                                          const GRState *state,
+                                          const LocationContext *LC);
+  
+  RetainSummary* getInstanceMethodSummary(const ObjCMessageExpr* ME,
+                                          const ObjCInterfaceDecl* ID) {
+    return getInstanceMethodSummary(ME->getSelector(), ME->getClassName(),
+                            ID, ME->getMethodDecl(), ME->getType());
+  }
+
+  RetainSummary* getInstanceMethodSummary(Selector S, IdentifierInfo *ClsName,
+                                          const ObjCInterfaceDecl* ID,
+                                          const ObjCMethodDecl *MD,
+                                          QualType RetTy);
+
+  RetainSummary *getClassMethodSummary(Selector S, IdentifierInfo *ClsName,
+                                       const ObjCInterfaceDecl *ID,
+                                       const ObjCMethodDecl *MD,
+                                       QualType RetTy);
+
+  RetainSummary *getClassMethodSummary(const ObjCMessageExpr *ME) {
+    return getClassMethodSummary(ME->getSelector(), ME->getClassName(),
+                                 ME->getClassInfo().first,
+                                 ME->getMethodDecl(), ME->getType());
+  }
+
+  /// getMethodSummary - This version of getMethodSummary is used to query
+  ///  the summary for the current method being analyzed.
+  RetainSummary *getMethodSummary(const ObjCMethodDecl *MD) {
+    // FIXME: Eventually this should be unneeded.
+    const ObjCInterfaceDecl *ID = MD->getClassInterface();
+    Selector S = MD->getSelector();
+    IdentifierInfo *ClsName = ID->getIdentifier();
+    QualType ResultTy = MD->getResultType();
+
+    // Resolve the method decl last.
+    if (const ObjCMethodDecl *InterfaceMD = ResolveToInterfaceMethodDecl(MD))
+      MD = InterfaceMD;
+
+    if (MD->isInstanceMethod())
+      return getInstanceMethodSummary(S, ClsName, ID, MD, ResultTy);
+    else