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/ValueState.h"
#include "clang/Analysis/PathDiagnostic.h"
#include "clang/Analysis/LocalCheckers.h"
#include "clang/Analysis/PathDiagnostic.h"
#include "clang/Analysis/PathSensitive/BugReporter.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/Support/Compiler.h"
#include <ostream>
#include <sstream>

using namespace clang;

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

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

//===----------------------------------------------------------------------===//
// Symbolic Evaluation of Reference Counting Logic
//===----------------------------------------------------------------------===//

namespace {  
  enum ArgEffect { IncRef, DecRef, DoNothing };
  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 {
  
class RetEffect {
public:
  enum Kind { NoRet = 0x0, Alias = 0x1, OwnedSymbol = 0x2,
              NotOwnedSymbol = 0x3 };

private:
  unsigned Data;
  RetEffect(Kind k, unsigned D) { Data = (D << 2) | (unsigned) k; }
  
public:

  Kind getKind() const { return (Kind) (Data & 0x3); }

  unsigned getValue() const { 
    assert(getKind() == Alias);
    return Data >> 2;
  }
    
  static RetEffect MakeAlias(unsigned Idx) { return RetEffect(Alias, Idx); }
  
  static RetEffect MakeOwned() { return RetEffect(OwnedSymbol, 0); }
  
  static RetEffect MakeNotOwned() { return RetEffect(NotOwnedSymbol, 0); }
  
  static RetEffect MakeNoRet() { return RetEffect(NoRet, 0); }
  
  operator Kind() const { return getKind(); }
  
  void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger(Data); }
};

  
class CFRefSummary : public llvm::FoldingSetNode {
  ArgEffects* Args;
  RetEffect   Ret;
public:
  
  CFRefSummary(ArgEffects* A, RetEffect R) : Args(A), Ret(R) {}
  
  unsigned getNumArgs() const { return Args->size(); }
  
  ArgEffect getArg(unsigned idx) const {
    if (!Args)
      return DoNothing;
    
    // 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 DoNothing;
      
      if (idx == I->first)
        return I->second;
    }
    
    return DoNothing;
  }
  
  RetEffect getRet() const {
    return Ret;
  }
  
  typedef ArgEffects::const_iterator arg_iterator;
  
  arg_iterator begin_args() const { return Args->begin(); }
  arg_iterator end_args()   const { return Args->end(); }
  
  static void Profile(llvm::FoldingSetNodeID& ID, ArgEffects* A, RetEffect R) {
    ID.AddPointer(A);
    ID.Add(R);
  }
      
  void Profile(llvm::FoldingSetNodeID& ID) const {
    Profile(ID, Args, Ret);
  }
};

  
class CFRefSummaryManager {
  typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<ArgEffects> > AESetTy;
  typedef llvm::FoldingSet<CFRefSummary>                SummarySetTy;
  typedef llvm::DenseMap<FunctionDecl*, CFRefSummary*>  SummaryMapTy;
  
  ASTContext& Ctx;
  const bool GCEnabled;
  
  SummarySetTy SummarySet;
  SummaryMapTy SummaryMap;  
  AESetTy AESet;  
  llvm::BumpPtrAllocator BPAlloc;  
  ArgEffects ScratchArgs;  
  
  ArgEffects*   getArgEffects();

  enum CFUnaryFunc { cfretain, cfrelease, cfmakecollectable };  
  CFRefSummary* getUnaryCFSummary(FunctionTypeProto* FT, CFUnaryFunc func);
  
  CFRefSummary* getCFSummary(FunctionDecl* FD, const char* FName);
  
  CFRefSummary* getCFSummaryCreateRule(FunctionTypeProto* FT);
  CFRefSummary* getCFSummaryGetRule(FunctionTypeProto* FT);  
  
  CFRefSummary* getPersistentSummary(ArgEffects* AE, RetEffect RE);
    
public:
  CFRefSummaryManager(ASTContext& ctx, bool gcenabled)
   : Ctx(ctx), GCEnabled(gcenabled) {}
  
  ~CFRefSummaryManager();
  
  CFRefSummary* getSummary(FunctionDecl* FD, ASTContext& Ctx);
};
  
} // end anonymous namespace

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

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

ArgEffects* CFRefSummaryManager::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 =
    AESet.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);
  AESet.InsertNode(E, InsertPos);

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

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


CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD,
                                              ASTContext& Ctx) {

  SourceLocation Loc = FD->getLocation();
  
  if (!Loc.isFileID())
    return NULL;
  

  // Look up a summary in our cache of FunctionDecls -> Summaries.
  SummaryMapTy::iterator I = SummaryMap.find(FD);

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

  // No summary.  Generate one.
  const char* FName = FD->getIdentifier()->getName();
    
  if (FName[0] == 'C' && FName[1] == 'F') {
    CFRefSummary* S = getCFSummary(FD, FName);
    SummaryMap[FD] = S;
    return S;
  }

  // Function has no ref-count effects.  Return the NULL summary.
  return NULL;  
}

CFRefSummary* CFRefSummaryManager::getCFSummary(FunctionDecl* FD,
                                                const char* FName) {
  
  // For now, only generate summaries for functions that have a prototype.
  
  FunctionTypeProto* FT =
    dyn_cast<FunctionTypeProto>(FD->getType().getTypePtr());
  
  if (!FT)
    return NULL;
  
  FName += 2;

  if (strcmp(FName, "Retain") == 0)
    return getUnaryCFSummary(FT, cfretain);
  
  if (strcmp(FName, "Release") == 0)
    return getUnaryCFSummary(FT, cfrelease);

  if (strcmp(FName, "MakeCollectable") == 0)
    return getUnaryCFSummary(FT, cfmakecollectable);
  
  assert (ScratchArgs.empty());
  bool usesCreateRule = false;
  
  if (strstr(FName, "Create"))
    usesCreateRule = true;
  
  if (!usesCreateRule && strstr(FName, "Copy"))
    usesCreateRule = true;
  
  if (usesCreateRule)
    return getCFSummaryCreateRule(FT);

  if (strstr(FName, "Get"))
    return getCFSummaryGetRule(FT);
  
  return NULL;
}

CFRefSummary*
CFRefSummaryManager::getUnaryCFSummary(FunctionTypeProto* FT, CFUnaryFunc func) {
  
  if (FT->getNumArgs() != 1)
    return NULL;
  
  TypedefType* ArgT = dyn_cast<TypedefType>(FT->getArgType(0).getTypePtr());
  
  if (!ArgT)
    return NULL;
  
  // For CFRetain/CFRelease, the first (and only) argument is of type 
  // "CFTypeRef".
  
  const char* TDName = ArgT->getDecl()->getIdentifier()->getName();
  assert (TDName);
  
  if (strcmp("CFTypeRef", TDName) != 0)
    return NULL;
  
  if (!ArgT->isPointerType())
    return NULL;

  QualType RetTy = FT->getResultType();
  
  switch (func) {
    case cfretain: {
      
      // CFRetain: the return type should also be "CFTypeRef".
      if (RetTy.getTypePtr() != ArgT)
        return NULL;
      
      // The function's interface checks out.  Generate a canned summary.    
      assert (ScratchArgs.empty());
      ScratchArgs.push_back(std::make_pair(0, IncRef));
      return getPersistentSummary(getArgEffects(), RetEffect::MakeAlias(0));
    }
      
    case cfrelease: {

      // CFRelease: the return type should be void.
      
      if (RetTy != Ctx.VoidTy)
        return NULL;
      
      assert (ScratchArgs.empty());
      ScratchArgs.push_back(std::make_pair(0, DecRef));
      return getPersistentSummary(getArgEffects(), RetEffect::MakeNoRet());
    }
      
    case cfmakecollectable: {
      
      // CFRetain: the return type should also be "CFTypeRef".
      if (RetTy.getTypePtr() != ArgT)
        return NULL;
      
      // The function's interface checks out.  Generate a canned summary.    
      assert (ScratchArgs.empty());
      
      if (GCEnabled)
        ScratchArgs.push_back(std::make_pair(0, DecRef));
      
      return getPersistentSummary(getArgEffects(), RetEffect::MakeAlias(0));
      
      
    }
      
    default:
      assert (false && "Not a support unary function.");
  }
}

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;
}

CFRefSummary*
CFRefSummaryManager::getCFSummaryCreateRule(FunctionTypeProto* FT) {
 
  if (!isCFRefType(FT->getResultType()))
    return NULL;

  // FIXME: Add special-cases for functions that retain/release.  For now
  //  just handle the default case.

  assert (ScratchArgs.empty());
  return getPersistentSummary(getArgEffects(), RetEffect::MakeOwned());
}

CFRefSummary*
CFRefSummaryManager::getCFSummaryGetRule(FunctionTypeProto* 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 NULL;
  
  // FIXME: Add special-cases for functions that retain/release.  For now
  //  just handle the default case.
  
  assert (ScratchArgs.empty());  
  return getPersistentSummary(getArgEffects(), RetEffect::MakeNotOwned());
}

//===----------------------------------------------------------------------===//
// Reference-counting logic (typestate + counts).
//===----------------------------------------------------------------------===//

namespace {
  
class VISIBILITY_HIDDEN 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.
    ErrorUseAfterRelease, // Object used after released.    
    ErrorReleaseNotOwned, // Release of an object that was not owned.
    ErrorLeak  // A memory leak due to excessive reference counts.
  };
  
private:
  
  Kind kind;
  unsigned Cnt;
    
  RefVal(Kind k, unsigned cnt) : kind(k), Cnt(cnt) {}
  
  RefVal(Kind k) : kind(k), Cnt(0) {}

public:  
  
  Kind getKind() const { return kind; }

  unsigned getCount() const { return Cnt; }
  
  // Useful predicates.
  
  static bool isError(Kind k) { return k >= ErrorUseAfterRelease; }
  
  static bool isLeak(Kind k) { return k == ErrorLeak; }
  
  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);
  }
  
  // State creation: normal state.
  
  static RefVal makeOwned(unsigned Count = 0) {
    return RefVal(Owned, Count);
  }
  
  static RefVal makeNotOwned(unsigned Count = 0) {
    return RefVal(NotOwned, Count);
  }

  static RefVal makeReturnedOwned(unsigned Count) {
    return RefVal(ReturnedOwned, Count);
  }
  
  static RefVal makeReturnedNotOwned() {
    return RefVal(ReturnedNotOwned);
  }
  
  // State creation: errors.
  
  static RefVal makeLeak() { return RefVal(ErrorLeak); }  
  static RefVal makeReleased() { return RefVal(Released); }
  static RefVal makeUseAfterRelease() { return RefVal(ErrorUseAfterRelease); }
  static RefVal makeReleaseNotOwned() { return RefVal(ErrorReleaseNotOwned); }
    
  // Comparison, profiling, and pretty-printing.
  
  bool operator==(const RefVal& X) const {
    return kind == X.kind && Cnt == X.Cnt;
  }
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger((unsigned) kind);
    ID.AddInteger(Cnt);
  }

  void print(std::ostream& Out) const;
};
  
void RefVal::print(std::ostream& Out) const {
  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 ErrorLeak:
      Out << "Leaked";
      break;            
      
    case ErrorUseAfterRelease:
      Out << "Use-After-Release [ERROR]";
      break;
      
    case ErrorReleaseNotOwned:
      Out << "Release of Not-Owned [ERROR]";
      break;
  }
}
  
//===----------------------------------------------------------------------===//
// Transfer functions.
//===----------------------------------------------------------------------===//

class VISIBILITY_HIDDEN CFRefCount : public GRSimpleVals {
public:
  // Type definitions.
  
  typedef llvm::ImmutableMap<SymbolID, RefVal> RefBindings;
  typedef RefBindings::Factory RefBFactoryTy;
  
  typedef llvm::DenseMap<GRExprEngine::NodeTy*,std::pair<Expr*, SymbolID> >
          ReleasesNotOwnedTy;
  
  typedef ReleasesNotOwnedTy UseAfterReleasesTy;
    
  typedef llvm::DenseMap<GRExprEngine::NodeTy*, std::vector<SymbolID>*>
          LeaksTy;

  class BindingsPrinter : public ValueState::CheckerStatePrinter {
  public:
    virtual void PrintCheckerState(std::ostream& Out, void* State,
                                   const char* nl, const char* sep);
  };

private:
  // Instance variables.
  
  CFRefSummaryManager Summaries;  
  const bool          GCEnabled;
  const bool          EmitStandardWarnings;  
  const LangOptions&  LOpts;
  RefBFactoryTy       RefBFactory;
     
  UseAfterReleasesTy UseAfterReleases;
  ReleasesNotOwnedTy ReleasesNotOwned;
  LeaksTy            Leaks;
  
  BindingsPrinter Printer;
  
  Selector RetainSelector;
  Selector ReleaseSelector;
  Selector AutoreleaseSelector;

public:
  
  static RefBindings GetRefBindings(ValueState& StImpl) {
    return RefBindings((RefBindings::TreeTy*) StImpl.CheckerState);
  }

private:
  
  static void SetRefBindings(ValueState& StImpl, RefBindings B) {
    StImpl.CheckerState = B.getRoot();
  }

  RefBindings Remove(RefBindings B, SymbolID sym) {
    return RefBFactory.Remove(B, sym);
  }
  
  RefBindings Update(RefBindings B, SymbolID sym, RefVal V, ArgEffect E,
                     RefVal::Kind& hasErr);
  
  void ProcessNonLeakError(ExplodedNodeSet<ValueState>& Dst,
                           GRStmtNodeBuilder<ValueState>& Builder,
                           Expr* NodeExpr, Expr* ErrorExpr,                        
                           ExplodedNode<ValueState>* Pred,
                           ValueState* St,
                           RefVal::Kind hasErr, SymbolID Sym);
  
  ValueState* HandleSymbolDeath(ValueStateManager& VMgr, ValueState* St,
                                SymbolID sid, RefVal V, bool& hasLeak);
  
  ValueState* NukeBinding(ValueStateManager& VMgr, ValueState* St,
                          SymbolID sid);
  
public:
  
  CFRefCount(ASTContext& Ctx, bool gcenabled, bool StandardWarnings,
             const LangOptions& lopts)
    : Summaries(Ctx, gcenabled),
      GCEnabled(gcenabled),
      EmitStandardWarnings(StandardWarnings),
      LOpts(lopts),
      RetainSelector(GetNullarySelector("retain", Ctx)),
      ReleaseSelector(GetNullarySelector("release", Ctx)),
      AutoreleaseSelector(GetNullarySelector("autorelease", Ctx)) {}
  
  virtual ~CFRefCount() {
    for (LeaksTy::iterator I = Leaks.begin(), E = Leaks.end(); I!=E; ++I)
      delete I->second;
  }
  
  virtual void RegisterChecks(GRExprEngine& Eng);
 
  virtual ValueState::CheckerStatePrinter* getCheckerStatePrinter() {
    return &Printer;
  }
  
  bool isGCEnabled() const { return GCEnabled; }
  const LangOptions& getLangOptions() const { return LOpts; }
  
  // Calls.
  
  virtual void EvalCall(ExplodedNodeSet<ValueState>& Dst,
                        GRExprEngine& Eng,
                        GRStmtNodeBuilder<ValueState>& Builder,
                        CallExpr* CE, RVal L,
                        ExplodedNode<ValueState>* Pred);  
  
  virtual void EvalObjCMessageExpr(ExplodedNodeSet<ValueState>& Dst,
                                   GRExprEngine& Engine,
                                   GRStmtNodeBuilder<ValueState>& Builder,
                                   ObjCMessageExpr* ME,
                                   ExplodedNode<ValueState>* Pred);
  
  bool EvalObjCMessageExprAux(ExplodedNodeSet<ValueState>& Dst,
                              GRExprEngine& Engine,
                              GRStmtNodeBuilder<ValueState>& Builder,
                              ObjCMessageExpr* ME,
                              ExplodedNode<ValueState>* Pred);

  // Stores.
  
  virtual void EvalStore(ExplodedNodeSet<ValueState>& Dst,
                         GRExprEngine& Engine,
                         GRStmtNodeBuilder<ValueState>& Builder,
                         Expr* E, ExplodedNode<ValueState>* Pred,
                         ValueState* St, RVal TargetLV, RVal Val);
  // End-of-path.
  
  virtual void EvalEndPath(GRExprEngine& Engine,
                           GREndPathNodeBuilder<ValueState>& Builder);
  
  virtual void EvalDeadSymbols(ExplodedNodeSet<ValueState>& Dst,
                               GRExprEngine& Engine,
                               GRStmtNodeBuilder<ValueState>& Builder,
                               ExplodedNode<ValueState>* Pred,
                               Stmt* S,
                               ValueState* St,
                               const ValueStateManager::DeadSymbolsTy& Dead);
  // Return statements.
  
  virtual void EvalReturn(ExplodedNodeSet<ValueState>& Dst,
                          GRExprEngine& Engine,
                          GRStmtNodeBuilder<ValueState>& Builder,
                          ReturnStmt* S,
                          ExplodedNode<ValueState>* Pred);

  // Assumptions.

  virtual ValueState* EvalAssume(GRExprEngine& Engine, ValueState* St,
                                 RVal Cond, bool Assumption, bool& isFeasible);

  // Error iterators.

  typedef UseAfterReleasesTy::iterator use_after_iterator;  
  typedef ReleasesNotOwnedTy::iterator bad_release_iterator;
  typedef LeaksTy::iterator            leaks_iterator;
  
  use_after_iterator use_after_begin() { return UseAfterReleases.begin(); }
  use_after_iterator use_after_end() { return UseAfterReleases.end(); }
  
  bad_release_iterator bad_release_begin() { return ReleasesNotOwned.begin(); }
  bad_release_iterator bad_release_end() { return ReleasesNotOwned.end(); }
  
  leaks_iterator leaks_begin() { return Leaks.begin(); }
  leaks_iterator leaks_end() { return Leaks.end(); }
};

} // end anonymous namespace




void CFRefCount::BindingsPrinter::PrintCheckerState(std::ostream& Out,
                                                    void* State, const char* nl,
                                                    const char* sep) {
  RefBindings B((RefBindings::TreeTy*) State);
  
  if (State)
    Out << sep << nl;
  
  for (RefBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
    Out << (*I).first << " : ";
    (*I).second.print(Out);
    Out << nl;
  }
}

static inline ArgEffect GetArgE(CFRefSummary* Summ, unsigned idx) {
  return Summ ? Summ->getArg(idx) : DoNothing;
}

static inline RetEffect GetRetE(CFRefSummary* Summ) {
  return Summ ? Summ->getRet() : RetEffect::MakeNoRet();
}

void CFRefCount::ProcessNonLeakError(ExplodedNodeSet<ValueState>& Dst,
                                     GRStmtNodeBuilder<ValueState>& Builder,
                                     Expr* NodeExpr, Expr* ErrorExpr,                        
                                     ExplodedNode<ValueState>* Pred,
                                     ValueState* St,
                                     RefVal::Kind hasErr, SymbolID Sym) {
  Builder.BuildSinks = true;
  GRExprEngine::NodeTy* N  = Builder.MakeNode(Dst, NodeExpr, Pred, St);

  if (!N) return;
    
  switch (hasErr) {
    default: assert(false);
    case RefVal::ErrorUseAfterRelease:
      UseAfterReleases[N] = std::make_pair(ErrorExpr, Sym);
      break;
      
    case RefVal::ErrorReleaseNotOwned:
      ReleasesNotOwned[N] = std::make_pair(ErrorExpr, Sym);
      break;
  }
}

void CFRefCount::EvalCall(ExplodedNodeSet<ValueState>& Dst,
                          GRExprEngine& Eng,
                          GRStmtNodeBuilder<ValueState>& Builder,
                          CallExpr* CE, RVal L,
                          ExplodedNode<ValueState>* Pred) {
  
  ValueStateManager& StateMgr = Eng.getStateManager();
  
  CFRefSummary* Summ = NULL;
  
  // Get the summary.

  if (isa<lval::FuncVal>(L)) {  
    lval::FuncVal FV = cast<lval::FuncVal>(L);
    FunctionDecl* FD = FV.getDecl();
    Summ = Summaries.getSummary(FD, Eng.getContext());
  }

  // Get the state.
  
  ValueState* St = Builder.GetState(Pred);
  
  // Evaluate the effects of the call.
  
  ValueState StVals = *St;
  RefVal::Kind hasErr = (RefVal::Kind) 0;
 
  // This function has a summary.  Evaluate the effect of the arguments.
  
  unsigned idx = 0;
  
  Expr* ErrorExpr = NULL;
  SymbolID ErrorSym = 0;                                        
  
  for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
        I != E; ++I, ++idx) {
    
    RVal V = StateMgr.GetRVal(St, *I);
    
    if (isa<lval::SymbolVal>(V)) {
      SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
      RefBindings B = GetRefBindings(StVals);      
      
      if (RefBindings::TreeTy* T = B.SlimFind(Sym)) {
        B = Update(B, Sym, T->getValue().second, GetArgE(Summ, idx), hasErr);
        SetRefBindings(StVals, B);
        
        if (hasErr) {
          ErrorExpr = *I;
          ErrorSym = T->getValue().first;
          break;
        }
      }
    }  
    else if (isa<LVal>(V)) { // Nuke all arguments passed by reference.
      
      // FIXME: This is basically copy-and-paste from GRSimpleVals.  We 
      //  should compose behavior, not copy it.
      StateMgr.Unbind(StVals, cast<LVal>(V));
    }
    else if (isa<nonlval::LValAsInteger>(V))
      StateMgr.Unbind(StVals, cast<nonlval::LValAsInteger>(V).getLVal());
  }    
  
  St = StateMgr.getPersistentState(StVals);
    
  if (hasErr) {
    ProcessNonLeakError(Dst, Builder, CE, ErrorExpr, Pred, St,
                        hasErr, ErrorSym);
    return;
  }
    
  // Finally, consult the summary for the return value.
  
  RetEffect RE = GetRetE(Summ);
  
  switch (RE.getKind()) {
    default:
      assert (false && "Unhandled RetEffect."); break;
    
    case RetEffect::NoRet:
    
      // Make up a symbol for the return value (not reference counted).
      // FIXME: This is basically copy-and-paste from GRSimpleVals.  We 
      //  should compose behavior, not copy it.
      
      if (CE->getType() != Eng.getContext().VoidTy) {    
        unsigned Count = Builder.getCurrentBlockCount();
        SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
        
        RVal X = CE->getType()->isPointerType() 
          ? cast<RVal>(lval::SymbolVal(Sym)) 
          : cast<RVal>(nonlval::SymbolVal(Sym));
        
        St = StateMgr.SetRVal(St, CE, X, Eng.getCFG().isBlkExpr(CE), false);
      }      
      
      break;
      
    case RetEffect::Alias: {
      unsigned idx = RE.getValue();
      assert (idx < CE->getNumArgs());
      RVal V = StateMgr.GetRVal(St, CE->getArg(idx));
      St = StateMgr.SetRVal(St, CE, V, Eng.getCFG().isBlkExpr(CE), false);
      break;
    }
      
    case RetEffect::OwnedSymbol: {
      unsigned Count = Builder.getCurrentBlockCount();
      SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);

      ValueState StImpl = *St;
      RefBindings B = GetRefBindings(StImpl);
      SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeOwned()));
      
      St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
                            CE, lval::SymbolVal(Sym),
                            Eng.getCFG().isBlkExpr(CE), false);
      
      break;
    }
      
    case RetEffect::NotOwnedSymbol: {
      unsigned Count = Builder.getCurrentBlockCount();
      SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
      
      ValueState StImpl = *St;
      RefBindings B = GetRefBindings(StImpl);
      SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeNotOwned()));
      
      St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
                            CE, lval::SymbolVal(Sym),
                            Eng.getCFG().isBlkExpr(CE), false);
      
      break;
    }
  }
      
  Builder.MakeNode(Dst, CE, Pred, St);
}


void CFRefCount::EvalObjCMessageExpr(ExplodedNodeSet<ValueState>& Dst,
                                     GRExprEngine& Eng,
                                     GRStmtNodeBuilder<ValueState>& Builder,
                                     ObjCMessageExpr* ME,
                                     ExplodedNode<ValueState>* Pred) {
  
  if (!EvalObjCMessageExprAux(Dst, Eng, Builder, ME, Pred))
    return;
  
  // The basic transfer function logic for message expressions does nothing.
  // We just invalidate all arguments passed in by references.
  
  ValueStateManager& StateMgr = Eng.getStateManager();
  ValueState* St = Builder.GetState(Pred);
  RefBindings B = GetRefBindings(*St);
  
  for (ObjCMessageExpr::arg_iterator I = ME->arg_begin(), E = ME->arg_end();
       I != E; ++I) {
    
    RVal V = StateMgr.GetRVal(St, *I);
    
    if (isa<LVal>(V)) {

      LVal lv = cast<LVal>(V);
      
      // Did the lval bind to a symbol?
      RVal X = StateMgr.GetRVal(St, lv);
      
      if (isa<lval::SymbolVal>(X)) {
        SymbolID Sym = cast<lval::SymbolVal>(X).getSymbol();
        B = Remove(B, Sym);
        
        // Create a new state with the updated bindings.  
        ValueState StVals = *St;
        SetRefBindings(StVals, B);
        St = StateMgr.getPersistentState(StVals);
      }