CFRefCount.cpp

  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.
  state = state.set<RefBindings>(Sym, X);
  Builder.MakeNode(Dst, S, Pred, state);
}

// Assumptions.

const GRState* CFRefCount::EvalAssume(GRStateManager& VMgr,
                                         const GRState* St,
                                         SVal 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 = St->get<RefBindings>();
  
  if (B.isEmpty())
    return St;
  
  bool changed = false;
  
  GRStateRef state(St, VMgr);
  RefBindings::Factory& RefBFactory = state.get_context<RefBindings>();

  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 (VMgr.getSymVal(St, I.getKey())) {
      changed = true;
      B = RefBFactory.Remove(B, I.getKey());
    }
  }
  
  if (changed)
    state = state.set<RefBindings>(B);
  
  return state;
}

RefBindings CFRefCount::Update(RefBindings B, SymbolID sym,
                               RefVal V, ArgEffect E,
                               RefVal::Kind& hasErr,
                               RefBindings::Factory& RefBFactory) {
  
  // 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;
      // Fall-through.      
    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; }

    const char* getCategory() const { 
      return "Memory (Core Foundation/Objective-C)";
    }
  };
  
  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 {
  public:
    BadRelease(CFRefCount& tf) : CFRefBug(tf) {}
    
    virtual const char* getName() const {
      return "bad release";
    }
    virtual const char* getDescription() const {
      return "Incorrect decrement of the reference count of a "
      "CoreFoundation object: "
      "The object is not owned at this point by the caller.";
    }
    
    virtual void EmitWarnings(BugReporter& BR);
  };
  
  class VISIBILITY_HIDDEN Leak : public CFRefBug {
    bool isReturn;
  public:
    Leak(CFRefCount& tf) : CFRefBug(tf) {}
    
    void setIsReturn(bool x) { isReturn = x; }
    
    virtual const char* getName() const {
      
      if (!isReturn) {
        if (getTF().isGCEnabled())
          return "leak (GC)";
        
        if (getTF().getLangOptions().getGCMode() == LangOptions::HybridGC)
          return "leak (hybrid MM, non-GC)";
        
        assert (getTF().getLangOptions().getGCMode() == LangOptions::NonGC);
        return "leak";
      }
      else {
        if (getTF().isGCEnabled())
          return "leak of returned object (GC)";
        
        if (getTF().getLangOptions().getGCMode() == LangOptions::HybridGC)
          return "leak of returned object (hybrid MM, non-GC)";
        
        assert (getTF().getLangOptions().getGCMode() == LangOptions::NonGC);
        return "leak of returned object";        
      }
    }
    
    virtual const char* getDescription() const {
      return "Object leaked";
    }
    
    virtual void EmitWarnings(BugReporter& BR);
    virtual void GetErrorNodes(std::vector<ExplodedNode<GRState>*>& Nodes);
    virtual bool isLeak() const { return true; }
    virtual bool isCached(BugReport& R);
  };
  
  //===---------===//
  // Bug Reports.  //
  //===---------===//
  
  class VISIBILITY_HIDDEN CFRefReport : public RangedBugReport {
    SymbolID Sym;
  public:
    CFRefReport(CFRefBug& D, ExplodedNode<GRState> *n, SymbolID sym)
      : RangedBugReport(D, n), Sym(sym) {}
        
    virtual ~CFRefReport() {}
    
    CFRefBug& getBugType() {
      return (CFRefBug&) RangedBugReport::getBugType();
    }
    const CFRefBug& getBugType() const {
      return (const CFRefBug&) RangedBugReport::getBugType();
    }
    
    virtual void getRanges(BugReporter& BR, const SourceRange*& beg,           
                           const SourceRange*& end) {
      
      if (!getBugType().isLeak())
        RangedBugReport::getRanges(BR, beg, end);
      else
        beg = end = 0;
    }
    
    SymbolID getSymbol() const { return Sym; }
    
    virtual PathDiagnosticPiece* getEndPath(BugReporter& BR,
                                            ExplodedNode<GRState>* N);
    
    virtual std::pair<const char**,const char**> getExtraDescriptiveText();
    
    virtual PathDiagnosticPiece* VisitNode(ExplodedNode<GRState>* N,
                                           ExplodedNode<GRState>* PrevN,
                                           ExplodedGraph<GRState>& G,
                                           BugReporter& BR);
  };
  
  
} // end anonymous namespace

void CFRefCount::RegisterChecks(GRExprEngine& Eng) {
  Eng.Register(new UseAfterRelease(*this));
  Eng.Register(new BadRelease(*this));
  Eng.Register(new Leak(*this));
}


static const char* Msgs[] = {
  "Code is compiled in garbage collection only mode"  // GC only
  "  (the bug occurs with garbage collection enabled).",
  
  "Code is compiled without garbage collection.", // No GC.
  
  "Code is compiled for use with and without garbage collection (GC)."
  "  The bug occurs with GC enabled.", // Hybrid, with GC.
  
  "Code is compiled for use with and without garbage collection (GC)."
  "  The bug occurs in non-GC mode."  // Hyrbird, without GC/
};

std::pair<const char**,const char**> CFRefReport::getExtraDescriptiveText() {
  CFRefCount& TF = static_cast<CFRefBug&>(getBugType()).getTF();

  switch (TF.getLangOptions().getGCMode()) {
    default:
      assert(false);
          
    case LangOptions::GCOnly:
      assert (TF.isGCEnabled());
      return std::make_pair(&Msgs[0], &Msgs[0]+1);      

    case LangOptions::NonGC:
      assert (!TF.isGCEnabled());
      return std::make_pair(&Msgs[1], &Msgs[1]+1);
    
    case LangOptions::HybridGC:
      if (TF.isGCEnabled())
        return std::make_pair(&Msgs[2], &Msgs[2]+1);
      else
        return std::make_pair(&Msgs[3], &Msgs[3]+1);
  }
}

PathDiagnosticPiece* CFRefReport::VisitNode(ExplodedNode<GRState>* N,
                                            ExplodedNode<GRState>* PrevN,
                                            ExplodedGraph<GRState>& G,
                                            BugReporter& BR) {

  // Check if the type state has changed.
  
  const GRState* PrevSt = PrevN->getState();
  const GRState* CurrSt = N->getState();
  
  RefBindings PrevB = PrevSt->get<RefBindings>();
  RefBindings CurrB = CurrSt->get<RefBindings>();
  
  const RefVal* PrevT = PrevB.lookup(Sym);
  const RefVal* CurrT = CurrB.lookup(Sym);
  
  if (!CurrT)
    return NULL;  
  
  const char* Msg = NULL;  
  const RefVal& CurrV = *CurrB.lookup(Sym);

  if (!PrevT) {
    
    Stmt* S = cast<PostStmt>(N->getLocation()).getStmt();

    if (CurrV.isOwned()) {

      if (isa<CallExpr>(S))
        Msg = "Function call returns an object with a +1 retain count"
              " (owning reference).";
      else {
        assert (isa<ObjCMessageExpr>(S));
        Msg = "Method returns an object with a +1 retain count"
              " (owning reference).";
      }
    }
    else {
      assert (CurrV.isNotOwned());
      
      if (isa<CallExpr>(S))
        Msg = "Function call returns an object with a +0 retain count"
              " (non-owning reference).";
      else {
        assert (isa<ObjCMessageExpr>(S));
        Msg = "Method returns an object with a +0 retain count"
              " (non-owning reference).";
      }      
    }
    
    FullSourceLoc Pos(S->getLocStart(), BR.getContext().getSourceManager());
    PathDiagnosticPiece* P = new PathDiagnosticPiece(Pos, Msg);
    
    if (Expr* Exp = dyn_cast<Expr>(S))
      P->addRange(Exp->getSourceRange());
    
    return P;    
  }
  
  // Determine if the typestate has changed.  
  RefVal PrevV = *PrevB.lookup(Sym);
  
  if (PrevV == CurrV)
    return NULL;
  
  // The typestate has changed.
  
  std::ostringstream os;
  std::string s;
  
  switch (CurrV.getKind()) {
    case RefVal::Owned:
    case RefVal::NotOwned:

      if (PrevV.getCount() == CurrV.getCount())
        return 0;
      
      if (PrevV.getCount() > CurrV.getCount())
        os << "Reference count decremented.";
      else
        os << "Reference count incremented.";
      
      if (unsigned Count = CurrV.getCount()) {

        os << " Object has +" << Count;
        
        if (Count > 1)
          os << " retain counts.";
        else
          os << " retain count.";
      }
      
      s = os.str();
      Msg = s.c_str();
      
      break;
      
    case RefVal::Released:
      Msg = "Object released.";
      break;
      
    case RefVal::ReturnedOwned:
      Msg = "Object returned to caller as an owning reference (single retain "
            "count transferred to caller).";
      break;
      
    case RefVal::ReturnedNotOwned:
      Msg = "Object returned to caller with a +0 (non-owning) retain count.";
      break;

    default:
      return NULL;
  }
  
  Stmt* S = cast<PostStmt>(N->getLocation()).getStmt();    
  FullSourceLoc Pos(S->getLocStart(), BR.getContext().getSourceManager());
  PathDiagnosticPiece* P = new PathDiagnosticPiece(Pos, Msg);
  
  // Add the range by scanning the children of the statement for any bindings
  // to Sym.
  
  GRStateManager& VSM = cast<GRBugReporter>(BR).getStateManager();
  
  for (Stmt::child_iterator I = S->child_begin(), E = S->child_end(); I!=E; ++I)
    if (Expr* Exp = dyn_cast_or_null<Expr>(*I)) {
      SVal X = VSM.GetSVal(CurrSt, Exp);
      
      if (loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&X))
        if (SV->getSymbol() == Sym) {
          P->addRange(Exp->getSourceRange()); break;
        }
    }
  
  return P;
}

namespace {
class VISIBILITY_HIDDEN FindUniqueBinding :
  public StoreManager::BindingsHandler {
    SymbolID Sym;
    MemRegion* Binding;
    bool First;
    
  public:
    FindUniqueBinding(SymbolID sym) : Sym(sym), Binding(0), First(true) {}
    
  bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, SVal val) {
    if (const loc::SymbolVal* SV = dyn_cast<loc::SymbolVal>(&val)) {
      if (SV->getSymbol() != Sym) 
        return true;
    }
    else if (const nonloc::SymbolVal* SV=dyn_cast<nonloc::SymbolVal>(&val)) {
      if (SV->getSymbol() != Sym)
        return true;
    }
    else
      return true;

    if (Binding) {
      First = false;
      return false;
    }
    else
      Binding = R;
    
    return true;    
  }
    
  operator bool() { return First && Binding; }
  MemRegion* getRegion() { return Binding; }
};  
}

static std::pair<ExplodedNode<GRState>*,MemRegion*>
GetAllocationSite(GRStateManager* StateMgr, ExplodedNode<GRState>* N,
                  SymbolID Sym) {

  // Find both first node that referred to the tracked symbol and the
  // memory location that value was store to.
  ExplodedNode<GRState>* Last = N;
  MemRegion* FirstBinding = 0;  
  
  while (N) {
    const GRState* St = N->getState();
    RefBindings B = St->get<RefBindings>();
    
    if (!B.lookup(Sym))
      break;

    if (StateMgr) {
      FindUniqueBinding FB(Sym);
      StateMgr->iterBindings(St, FB);      
      if (FB) FirstBinding = FB.getRegion();      
    }
    
    Last = N;
    N = N->pred_empty() ? NULL : *(N->pred_begin());    
  }
  
  return std::make_pair(Last, FirstBinding);
}

PathDiagnosticPiece* CFRefReport::getEndPath(BugReporter& br,
                                             ExplodedNode<GRState>* EndN) {

  GRBugReporter& BR = cast<GRBugReporter>(br);
  
  // Tell the BugReporter to report cases when the tracked symbol is
  // assigned to different variables, etc.
  cast<GRBugReporter>(BR).addNotableSymbol(Sym);
  
  if (!getBugType().isLeak())
    return RangedBugReport::getEndPath(BR, EndN);
  
  // We are a leak.  Walk up the graph to get to the first node where the
  // symbol appeared, and also get the first VarDecl that tracked object
  // is stored to.
  ExplodedNode<GRState>* AllocNode = 0;
  MemRegion* FirstBinding = 0;

  llvm::tie(AllocNode, FirstBinding) =
    GetAllocationSite(&BR.getStateManager(), EndN, Sym);
  
  // Get the allocate site.  
  assert (AllocNode);
  Stmt* FirstStmt = cast<PostStmt>(AllocNode->getLocation()).getStmt();

  SourceManager& SMgr = BR.getContext().getSourceManager();
  unsigned AllocLine = SMgr.getLogicalLineNumber(FirstStmt->getLocStart());

  // Get the leak site.  We may have multiple ExplodedNodes (one with the
  // leak) that occur on the same line number; if the node with the leak
  // has any immediate predecessor nodes with the same line number, find
  // any transitive-successors that have a different statement and use that
  // line number instead.  This avoids emiting a diagnostic like:
  //
  //    // 'y' is leaked.
  //  int x = foo(y);
  //
  //  instead we want:
  //
  //  int x = foo(y);
  //   // 'y' is leaked.
  
  Stmt* S = getStmt(BR);  // This is the statement where the leak occured.
  assert (S);
  unsigned EndLine = SMgr.getLogicalLineNumber(S->getLocStart());

  // Look in the *trimmed* graph at the immediate predecessor of EndN.  Does
  // it occur on the same line?
  PathDiagnosticPiece::DisplayHint Hint = PathDiagnosticPiece::Above;
  
  assert (!EndN->pred_empty()); // Not possible to have 0 predecessors.
  ExplodedNode<GRState> *Pred = *(EndN->pred_begin());
  ProgramPoint PredPos = Pred->getLocation();
  
  if (PostStmt* PredPS = dyn_cast<PostStmt>(&PredPos)) {

    Stmt* SPred = PredPS->getStmt();
    
    // Predecessor at same line?
    if (SMgr.getLogicalLineNumber(SPred->getLocStart()) != EndLine) {
      Hint = PathDiagnosticPiece::Below;
      S = SPred;
    }
  }
  
  // Generate the diagnostic.
  FullSourceLoc L( S->getLocStart(), SMgr);
  std::ostringstream os;
  
  os << "Object allocated on line " << AllocLine;
  
  if (FirstBinding)
    os << " and stored into '" << FirstBinding->getString() << '\'';  

  
  // Get the retain count.
  const RefVal* RV = EndN->getState()->get<RefBindings>(Sym);
  
  if (RV->getKind() == RefVal::ErrorLeakReturned) {
    ObjCMethodDecl& MD = cast<ObjCMethodDecl>(BR.getGraph().getCodeDecl());
    os << " is returned from a method whose name ('"
       << MD.getSelector().getName()
       << "') does not contain 'create', "
          "'copy', or 'new'.  This violates the naming convention rules given"
          " in the Memory Management Guide for Cocoa (object leaked).";
  }
  else
    os << " is no longer referenced after this point and has a retain count of +"
       << RV->getCount() << " (object leaked).";
  
  return new PathDiagnosticPiece(L, os.str(), Hint);
}

void UseAfterRelease::EmitWarnings(BugReporter& BR) {

  for (CFRefCount::use_after_iterator I = TF.use_after_begin(),
        E = TF.use_after_end(); I != E; ++I) {
    
    CFRefReport report(*this, I->first, I->second.second);
    report.addRange(I->second.first->getSourceRange());    
    BR.EmitWarning(report);    
  }
}

void BadRelease::EmitWarnings(BugReporter& BR) {
  
  for (CFRefCount::bad_release_iterator I = TF.bad_release_begin(),
       E = TF.bad_release_end(); I != E; ++I) {
    
    CFRefReport report(*this, I->first, I->second.second);
    report.addRange(I->second.first->getSourceRange());    
    BR.EmitWarning(report);    
  }  
}

void Leak::EmitWarnings(BugReporter& BR) {
  
  for (CFRefCount::leaks_iterator I = TF.leaks_begin(),
       E = TF.leaks_end(); I != E; ++I) {
    
    std::vector<std::pair<SymbolID, bool> >& SymV = *(I->second);
    unsigned n = SymV.size();
    
    for (unsigned i = 0; i < n; ++i) {
      setIsReturn(SymV[i].second);
      CFRefReport report(*this, I->first, SymV[i].first);
      BR.EmitWarning(report);
    }
  }  
}

void Leak::GetErrorNodes(std::vector<ExplodedNode<GRState>*>& Nodes) {
  for (CFRefCount::leaks_iterator I=TF.leaks_begin(), E=TF.leaks_end();
       I!=E; ++I)
    Nodes.push_back(I->first);
}

bool Leak::isCached(BugReport& R) {
  
  // Most bug reports are cached at the location where they occured.
  // With leaks, we want to unique them by the location where they were
  // allocated, and only report a single path.
  
  SymbolID Sym = static_cast<CFRefReport&>(R).getSymbol();

  ExplodedNode<GRState>* AllocNode =
    GetAllocationSite(0, R.getEndNode(), Sym).first;
  
  if (!AllocNode)
    return false;
  
  return BugTypeCacheLocation::isCached(AllocNode->getLocation());
}

//===----------------------------------------------------------------------===//
// Transfer function creation for external clients.
//===----------------------------------------------------------------------===//

GRTransferFuncs* clang::MakeCFRefCountTF(ASTContext& Ctx, bool GCEnabled,
                                         const LangOptions& lopts) {
  return new CFRefCount(Ctx, GCEnabled, lopts);
}