CFRefCount.cpp

    return RefVal(ReturnedNotOwned);
  }
  
  // State creation: errors.

#if 0
  static RefVal makeLeak(unsigned Count) { return RefVal(ErrorLeak, Count); }  
  static RefVal makeReleased() { return RefVal(Released); }
  static RefVal makeUseAfterRelease() { return RefVal(ErrorUseAfterRelease); }
  static RefVal makeReleaseNotOwned() { return RefVal(ErrorReleaseNotOwned); }
#endif
  
  // Comparison, profiling, and pretty-printing.
  
  bool operator==(const RefVal& X) const {
    return kind == X.kind && Cnt == X.Cnt && T == X.T;
  }
  
  RefVal operator-(size_t i) const {
    return RefVal(getKind(), getCount() - i, getType());
  }
  
  RefVal operator+(size_t i) const {
    return RefVal(getKind(), getCount() + i, getType());
  }
  
  RefVal operator^(Kind k) const {
    return RefVal(k, getCount(), getType());
  }
    
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    ID.AddInteger((unsigned) kind);
    ID.AddInteger(Cnt);
    ID.Add(T);
  }

  void print(std::ostream& Out) const;
};
  
void RefVal::print(std::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 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.
  
  RetainSummaryManager Summaries;  
  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),
      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 Summaries.isGCEnabled(); }
  const LangOptions& getLangOptions() const { return LOpts; }
  
  // Calls.

  void EvalSummary(ExplodedNodeSet<ValueState>& Dst,
                   GRExprEngine& Eng,
                   GRStmtNodeBuilder<ValueState>& Builder,
                   Expr* Ex,
                   Expr* Receiver,
                   RetainSummary* Summ,
                   ExprIterator arg_beg, ExprIterator arg_end,                             
                   ExplodedNode<ValueState>* Pred);
    
  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(RetainSummary* Summ, unsigned idx) {
  return Summ ? Summ->getArg(idx) : MayEscape;
}

static inline RetEffect GetRetEffect(RetainSummary* Summ) {
  return Summ ? Summ->getRetEffect() : RetEffect::MakeNoRet();
}

static inline ArgEffect GetReceiverE(RetainSummary* Summ) {
  return Summ ? Summ->getReceiverEffect() : DoNothing;
}

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

/// GetReturnType - Used to get the return type of a message expression or
///  function call with the intention of affixing that type to a tracked symbol.
///  While the the return type can be queried directly from RetEx, when
///  invoking class methods we augment to the return type to be that of
///  a pointer to the class (as opposed it just being id).
static QualType GetReturnType(Expr* RetE, ASTContext& Ctx) {

  QualType RetTy = RetE->getType();

  // FIXME: We aren't handling id<...>.
  const PointerType* PT = RetTy.getCanonicalType()->getAsPointerType();
  
  if (!PT)
    return RetTy;
    
  // If RetEx is not a message expression just return its type.
  // If RetEx is a message expression, return its types if it is something
  /// more specific than id.
  
  ObjCMessageExpr* ME = dyn_cast<ObjCMessageExpr>(RetE);
  
  if (!ME || !Ctx.isObjCIdType(PT->getPointeeType()))
    return RetTy;
  
  ObjCInterfaceDecl* D = ME->getClassInfo().first;  

  // At this point we know the return type of the message expression is id.
  // If we have an ObjCInterceDecl, we know this is a call to a class method
  // whose type we can resolve.  In such cases, promote the return type to
  // Class*.  
  return !D ? RetTy : Ctx.getPointerType(Ctx.getObjCInterfaceType(D));
}


void CFRefCount::EvalSummary(ExplodedNodeSet<ValueState>& Dst,
                             GRExprEngine& Eng,
                             GRStmtNodeBuilder<ValueState>& Builder,
                             Expr* Ex,
                             Expr* Receiver,
                             RetainSummary* Summ,
                             ExprIterator arg_beg, ExprIterator arg_end,                             
                             ExplodedNode<ValueState>* Pred) {
  
  // Get the state.
  ValueStateManager& StateMgr = Eng.getStateManager();  
  ValueState* St = Builder.GetState(Pred);

  // Evaluate the effect of the arguments.
  ValueState StVals = *St;
  RefVal::Kind hasErr = (RefVal::Kind) 0;
  unsigned idx = 0;
  Expr* ErrorExpr = NULL;
  SymbolID ErrorSym = 0;                                        
  
  for (ExprIterator I = arg_beg; I != arg_end; ++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::data_type* T = B.lookup(Sym)) {
        B = Update(B, Sym, *T, GetArgE(Summ, idx), hasErr);
        SetRefBindings(StVals, B);
        
        if (hasErr) {
          ErrorExpr = *I;
          ErrorSym = Sym;
          break;
        }
      }
    }  
    else if (isa<LVal>(V)) {
#if 0
      // Nuke all arguments passed by reference.
      StateMgr.Unbind(StVals, cast<LVal>(V));
#else
      if (lval::DeclVal* DV = dyn_cast<lval::DeclVal>(&V)) {

        if (GetArgE(Summ, idx) == DoNothingByRef)
          continue;
        
        // Invalidate the value of the variable passed by reference.
        
        // FIXME: Either this logic should also be replicated in GRSimpleVals
        //  or should be pulled into a separate "constraint engine."
        
        // FIXME: We can have collisions on the conjured symbol if the
        //  expression *I also creates conjured symbols.  We probably want
        //  to identify conjured symbols by an expression pair: the enclosing
        //  expression (the context) and the expression itself.  This should
        //  disambiguate conjured symbols. 

        // Is the invalidated variable something that we were tracking?
        RVal X = StateMgr.GetRVal(&StVals, *DV);
        
        if (isa<lval::SymbolVal>(X)) {
          SymbolID Sym = cast<lval::SymbolVal>(X).getSymbol();
          SetRefBindings(StVals,RefBFactory.Remove(GetRefBindings(StVals),Sym));
        }

        // Set the value of the variable to be a conjured symbol.
        unsigned Count = Builder.getCurrentBlockCount();
        SymbolID NewSym = Eng.getSymbolManager().getConjuredSymbol(*I, Count);
      
        StateMgr.BindVar(StVals, DV->getDecl(),
                         LVal::IsLValType(DV->getDecl()->getType())
                         ? cast<RVal>(lval::SymbolVal(NewSym))
                         : cast<RVal>(nonlval::SymbolVal(NewSym)));
      }
      else {
        // Nuke all other arguments passed by reference.
        StateMgr.Unbind(StVals, cast<LVal>(V));
      }
#endif
    }
    else if (isa<nonlval::LValAsInteger>(V))
      StateMgr.Unbind(StVals, cast<nonlval::LValAsInteger>(V).getLVal());
  } 
  
  // Evaluate the effect on the message receiver.  
  if (!ErrorExpr && Receiver) {
    RVal V = StateMgr.GetRVal(St, Receiver);

    if (isa<lval::SymbolVal>(V)) {
      SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
      RefBindings B = GetRefBindings(StVals);      
      
      if (const RefVal* T = B.lookup(Sym)) {
        B = Update(B, Sym, *T, GetReceiverE(Summ), hasErr);
        SetRefBindings(StVals, B);
        
        if (hasErr) {
          ErrorExpr = Receiver;
          ErrorSym = Sym;
        }
      }
    }
  }

  // Get the persistent state.  
  St = StateMgr.getPersistentState(StVals);
  
  // Process any errors.  
  if (hasErr) {
    ProcessNonLeakError(Dst, Builder, Ex, ErrorExpr, Pred, St,
                        hasErr, ErrorSym);
    return;
  }
  
  // Finally, consult the summary for the return value.  
  RetEffect RE = GetRetEffect(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 (Ex->getType() != Eng.getContext().VoidTy) {    
        unsigned Count = Builder.getCurrentBlockCount();
        SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(Ex, Count);
        
        RVal X = LVal::IsLValType(Ex->getType())
               ? cast<RVal>(lval::SymbolVal(Sym)) 
               : cast<RVal>(nonlval::SymbolVal(Sym));
        
        St = StateMgr.SetRVal(St, Ex, X, Eng.getCFG().isBlkExpr(Ex), false);
      }      
      
      break;
      
    case RetEffect::Alias: {
      unsigned idx = RE.getIndex();
      assert (arg_end >= arg_beg);
      assert (idx < (unsigned) (arg_end - arg_beg));
      RVal V = StateMgr.GetRVal(St, *(arg_beg+idx));
      St = StateMgr.SetRVal(St, Ex, V, Eng.getCFG().isBlkExpr(Ex), false);
      break;
    }
      
    case RetEffect::ReceiverAlias: {
      assert (Receiver);
      RVal V = StateMgr.GetRVal(St, Receiver);
      St = StateMgr.SetRVal(St, Ex, V, Eng.getCFG().isBlkExpr(Ex), false);
      break;
    }
      
    case RetEffect::OwnedAllocatedSymbol:
    case RetEffect::OwnedSymbol: {
      unsigned Count = Builder.getCurrentBlockCount();
      SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(Ex, Count);
      QualType RetT = GetReturnType(Ex, Eng.getContext());
      
      ValueState StImpl = *St;
      RefBindings B = GetRefBindings(StImpl);
      SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeOwned(RetT)));
      
      St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
                            Ex, lval::SymbolVal(Sym),
                            Eng.getCFG().isBlkExpr(Ex), false);
      
      // FIXME: Add a flag to the checker where allocations are allowed to fail.      
      if (RE.getKind() == RetEffect::OwnedAllocatedSymbol)
        St = StateMgr.AddNE(St, Sym, Eng.getBasicVals().getZeroWithPtrWidth());
      
      break;
    }
      
    case RetEffect::NotOwnedSymbol: {
      unsigned Count = Builder.getCurrentBlockCount();
      SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(Ex, Count);
      QualType RetT = GetReturnType(Ex, Eng.getContext());
      
      ValueState StImpl = *St;
      RefBindings B = GetRefBindings(StImpl);
      SetRefBindings(StImpl, RefBFactory.Add(B, Sym,
                                             RefVal::makeNotOwned(RetT)));
      
      St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
                            Ex, lval::SymbolVal(Sym),
                            Eng.getCFG().isBlkExpr(Ex), false);
      
      break;
    }
  }
  
  Builder.MakeNode(Dst, Ex, Pred, St);
}


void CFRefCount::EvalCall(ExplodedNodeSet<ValueState>& Dst,
                          GRExprEngine& Eng,
                          GRStmtNodeBuilder<ValueState>& Builder,
                          CallExpr* CE, RVal L,
                          ExplodedNode<ValueState>* Pred) {
  
  
  RetainSummary* 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);
  }
  
  EvalSummary(Dst, Eng, Builder, CE, 0, Summ,
              CE->arg_begin(), CE->arg_end(), Pred);
}


void CFRefCount::EvalObjCMessageExpr(ExplodedNodeSet<ValueState>& Dst,
                                     GRExprEngine& Eng,
                                     GRStmtNodeBuilder<ValueState>& Builder,
                                     ObjCMessageExpr* ME,
                                     ExplodedNode<ValueState>* Pred) {
  
  RetainSummary* Summ;
  
  if (Expr* Receiver = ME->getReceiver()) {
    // We need the type-information of the tracked receiver object
    // Retrieve it from the state.
    ObjCInterfaceDecl* ID = 0;

    // FIXME: Wouldn't it be great if this code could be reduced?  It's just
    // a chain of lookups.
    ValueState* St = Builder.GetState(Pred);
    RVal V = Eng.getStateManager().GetRVal(St, Receiver );

    if (isa<lval::SymbolVal>(V)) {
      SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
      
      if (const RefVal* T  = GetRefBindings(*St).lookup(Sym)) {
        QualType Ty = T->getType();
        
        if (const PointerType* PT = Ty->getAsPointerType()) {
          QualType PointeeTy = PT->getPointeeType();
          
          if (ObjCInterfaceType* IT = dyn_cast<ObjCInterfaceType>(PointeeTy))
            ID = IT->getDecl();
        }
      }
    }
    
    Summ = Summaries.getMethodSummary(ME, ID);
  }
  else
    Summ = Summaries.getClassMethodSummary(ME->getClassName(),
                                           ME->getSelector());

  EvalSummary(Dst, Eng, Builder, ME, ME->getReceiver(), Summ,
              ME->arg_begin(), ME->arg_end(), Pred);
}
  
// Stores.

void CFRefCount::EvalStore(ExplodedNodeSet<ValueState>& Dst,
                           GRExprEngine& Eng,
                           GRStmtNodeBuilder<ValueState>& Builder,
                           Expr* E, ExplodedNode<ValueState>* Pred,
                           ValueState* St, RVal TargetLV, RVal Val) {
  
  // Check if we have a binding for "Val" and if we are storing it to something
  // we don't understand or otherwise the value "escapes" the function.
  
  if (!isa<lval::SymbolVal>(Val))
    return;
  
  // Are we storing to something that causes the value to "escape"?
  
  bool escapes = false;
  
  if (!isa<lval::DeclVal>(TargetLV))
    escapes = true;
  else
    escapes = cast<lval::DeclVal>(TargetLV).getDecl()->hasGlobalStorage();
  
  if (!escapes)
    return;
  
  SymbolID Sym = cast<lval::SymbolVal>(Val).getSymbol();
  
  if (!GetRefBindings(*St).lookup(Sym))
    return;
  
  // Nuke the binding.  
  St = NukeBinding(Eng.getStateManager(), St, Sym);
  
  // Hand of the remaining logic to the parent implementation.
  GRSimpleVals::EvalStore(Dst, Eng, Builder, E, Pred, St, TargetLV, Val);
}


ValueState* CFRefCount::NukeBinding(ValueStateManager& VMgr, ValueState* St,
                                    SymbolID sid) {
  ValueState StImpl = *St;
  RefBindings B = GetRefBindings(StImpl);
  StImpl.CheckerState = RefBFactory.Remove(B, sid).getRoot();
  return VMgr.getPersistentState(StImpl);
}

// End-of-path.

ValueState* CFRefCount::HandleSymbolDeath(ValueStateManager& VMgr,
                                          ValueState* St, SymbolID sid,
                                          RefVal V, bool& hasLeak) {
    
  hasLeak = V.isOwned() || 
            ((V.isNotOwned() || V.isReturnedOwned()) && V.getCount() > 0);

  if (!hasLeak)
    return NukeBinding(VMgr, St, sid);
  
  RefBindings B = GetRefBindings(*St);
  ValueState StImpl = *St;
  StImpl.CheckerState = RefBFactory.Add(B, sid, V^RefVal::ErrorLeak).getRoot();
  
  return VMgr.getPersistentState(StImpl);
}

void CFRefCount::EvalEndPath(GRExprEngine& Eng,
                             GREndPathNodeBuilder<ValueState>& Builder) {
  
  ValueState* St = Builder.getState();
  RefBindings B = GetRefBindings(*St);
  
  llvm::SmallVector<SymbolID, 10> Leaked;
  
  for (RefBindings::iterator I = B.begin(), E = B.end(); I != E; ++I) {
    bool hasLeak = false;
    
    St = HandleSymbolDeath(Eng.getStateManager(), St,
                           (*I).first, (*I).second, hasLeak);
    
    if (hasLeak) Leaked.push_back((*I).first);
  }

  if (Leaked.empty())
    return;
  
  ExplodedNode<ValueState>* N = Builder.MakeNode(St);  
  
  if (!N)
    return;
    
  std::vector<SymbolID>*& LeaksAtNode = Leaks[N];
  assert (!LeaksAtNode);
  LeaksAtNode = new std::vector<SymbolID>();
  
  for (llvm::SmallVector<SymbolID, 10>::iterator I=Leaked.begin(),
       E = Leaked.end(); I != E; ++I)
    (*LeaksAtNode).push_back(*I);
}

// Dead symbols.

void CFRefCount::EvalDeadSymbols(ExplodedNodeSet<ValueState>& Dst,
                                 GRExprEngine& Eng,
                                 GRStmtNodeBuilder<ValueState>& Builder,
                                 ExplodedNode<ValueState>* Pred,
                                 Stmt* S,
                                 ValueState* St,
                                 const ValueStateManager::DeadSymbolsTy& Dead) {
    
  // FIXME: a lot of copy-and-paste from EvalEndPath.  Refactor.
  
  RefBindings B = GetRefBindings(*St);
  llvm::SmallVector<SymbolID, 10> Leaked;
  
  for (ValueStateManager::DeadSymbolsTy::const_iterator
       I=Dead.begin(), E=Dead.end(); I!=E; ++I) {
    
    const RefVal* T = B.lookup(*I);

    if (!T)
      continue;
    
    bool hasLeak = false;
    
    St = HandleSymbolDeath(Eng.getStateManager(), St, *I, *T, hasLeak);
    
    if (hasLeak)
      Leaked.push_back(*I);    
  }
  
  if (Leaked.empty())
    return;    
  
  ExplodedNode<ValueState>* N = Builder.MakeNode(Dst, S, Pred, St);  
  
  if (!N)
    return;
  
  std::vector<SymbolID>*& LeaksAtNode = Leaks[N];
  assert (!LeaksAtNode);
  LeaksAtNode = new std::vector<SymbolID>();
  
  for (llvm::SmallVector<SymbolID, 10>::iterator I=Leaked.begin(),
       E = Leaked.end(); I != E; ++I)
    (*LeaksAtNode).push_back(*I);    
}

 // Return statements.

void CFRefCount::EvalReturn(ExplodedNodeSet<ValueState>& Dst,
                            GRExprEngine& Eng,
                            GRStmtNodeBuilder<ValueState>& Builder,
                            ReturnStmt* S,
                            ExplodedNode<ValueState>* Pred) {
  
  Expr* RetE = S->getRetValue();
  if (!RetE) return;
  
  ValueStateManager& StateMgr = Eng.getStateManager();
  ValueState* St = Builder.GetState(Pred);
  RVal V = StateMgr.GetRVal(St, RetE);
  
  if (!isa<lval::SymbolVal>(V))
    return;
  
  // Get the reference count binding (if any).
  SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
  RefBindings B = GetRefBindings(*St);
  const RefVal* T = B.lookup(Sym);
  
  if (!T)
    return;
  
  // Change the reference count.
  
  RefVal X = *T;  
  
  switch (X.getKind()) {
      
    case RefVal::Owned: { 
      unsigned cnt = X.getCount();
      assert (cnt > 0);
      X = RefVal::makeReturnedOwned(cnt - 1);
      break;
    }
      
    case RefVal::NotOwned: {
      unsigned cnt = X.getCount();
      X = cnt ? RefVal::makeReturnedOwned(cnt - 1)
              : RefVal::makeReturnedNotOwned();
      break;
    }
      
    default: 
      return;
  }
  
  // Update the binding.

  ValueState StImpl = *St;
  StImpl.CheckerState = RefBFactory.Add(B, Sym, X).getRoot();        
  Builder.MakeNode(Dst, S, Pred, StateMgr.getPersistentState(StImpl));
}

// Assumptions.

ValueState* CFRefCount::EvalAssume(GRExprEngine& Eng, ValueState* St,
                                   RVal Cond, bool Assumption,
                                   bool& isFeasible) {

  // FIXME: We may add to the interface of EvalAssume the list of symbols
  //  whose assumptions have changed.  For now we just iterate through the
  //  bindings and check if any of the tracked symbols are NULL.  This isn't
  //  too bad since the number of symbols we will track in practice are 
  //  probably small and EvalAssume is only called at branches and a few
  //  other places.
    
  RefBindings B = GetRefBindings(*St);
  
  if (B.isEmpty())
    return St;
  
  bool changed = false;

  for (RefBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {    

    // Check if the symbol is null (or equal to any constant).
    // If this is the case, stop tracking the symbol.
  
    if (St->getSymVal(I.getKey())) {
      changed = true;
      B = RefBFactory.Remove(B, I.getKey());
    }
  }
  
  if (!changed)
    return St;
  
  ValueState StImpl = *St;
  StImpl.CheckerState = B.getRoot();
  return Eng.getStateManager().getPersistentState(StImpl);
}

CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym,
                                           RefVal V, ArgEffect E,
                                           RefVal::Kind& hasErr) {
  
  // FIXME: This dispatch can potentially be sped up by unifiying it into
  //  a single switch statement.  Opt for simplicity for now.
  
  switch (E) {
    default:
      assert (false && "Unhandled CFRef transition.");

    case MayEscape:
      if (V.getKind() == RefVal::Owned) {
        V = V ^ RefVal::NotOwned;
        break;
      }

      // Fall-through.
      
    case DoNothingByRef:
    case DoNothing:
      if (!isGCEnabled() && V.getKind() == RefVal::Released) {
        V = V ^ RefVal::ErrorUseAfterRelease;
        hasErr = V.getKind();
        break;
      }
      
      return B;

    case Autorelease:          
    case StopTracking:
      return RefBFactory.Remove(B, sym);
      
    case IncRef:      
      switch (V.getKind()) {
        default:
          assert(false);

        case RefVal::Owned:
        case RefVal::NotOwned:
          V = V + 1;
          break;
          
        case RefVal::Released:
          if (isGCEnabled())
            V = V ^ RefVal::Owned;
          else {          
            V = V ^ RefVal::ErrorUseAfterRelease;
            hasErr = V.getKind();
          }
          
          break;
      }
      
      break;
      
    case SelfOwn:
      V = V ^ RefVal::NotOwned;
      
    case DecRef:
      switch (V.getKind()) {
        default:
          assert (false);
          
        case RefVal::Owned:
          V = V.getCount() > 1 ? V - 1 : V ^ RefVal::Released;
          break;
          
        case RefVal::NotOwned:
          if (V.getCount() > 0)
            V = V - 1;
          else {
            V = V ^ RefVal::ErrorReleaseNotOwned;
            hasErr = V.getKind();
          }
          
          break;

        case RefVal::Released:
          V = V ^ RefVal::ErrorUseAfterRelease;
          hasErr = V.getKind();
          break;          
      }
      
      break;
  }

  return RefBFactory.Add(B, sym, V);
}


//===----------------------------------------------------------------------===//
// Error reporting.
//===----------------------------------------------------------------------===//

namespace {
  
  //===-------------===//
  // Bug Descriptions. //
  //===-------------===//  
  
  class VISIBILITY_HIDDEN CFRefBug : public BugTypeCacheLocation {
  protected:
    CFRefCount& TF;
    
  public:
    CFRefBug(CFRefCount& tf) : TF(tf) {}
    
    CFRefCount& getTF() { return TF; }
    const CFRefCount& getTF() const { return TF; }

    virtual bool isLeak() const { return false; }
  };
  
  class VISIBILITY_HIDDEN UseAfterRelease : public CFRefBug {
  public:
    UseAfterRelease(CFRefCount& tf) : CFRefBug(tf) {}
    
    virtual const char* getName() const {
      return "Use-After-Release";
    }
    virtual const char* getDescription() const {
      return "Reference-counted object is used"
             " after it is released.";
    }
    
    virtual void EmitWarnings(BugReporter& BR);
  };
  
  class VISIBILITY_HIDDEN BadRelease : public CFRefBug {