Merge branch 'master' of https://github.com/redpony/cdec

1 files changed, 0 insertions, 656 deletions

diff --git a/decoder/cfg.cc b/decoder/cfg.cc
deleted file mode 100644
index d6ee651a..00000000
--- a/decoder/cfg.cc
+++ /dev/null
@@ -1,656 +0,0 @@
-#include "cfg.h"
-#include "hg.h"
-#include "cfg_format.h"
-#include "cfg_binarize.h"
-#include "hash.h"
-#include "batched_append.h"
-#include <limits>
-#include "fast_lexical_cast.hpp"
-//#include "indices_after.h"
-#include "show.h"
-#include "null_traits.h"
-
-#define DUNIQ(x) x
-#define DBIN(x)
-#define DSP(x) x
-//SP:binarize by splitting.
-#define DCFG(x) IF_CFG_DEBUG(x)
-
-#undef CFG_FOR_RULES
-#define CFG_FOR_RULES(i,expr)                                    \
-  for (CFG::NTs::const_iterator n=nts.begin(),nn=nts.end();n!=nn;++n) { \
-    NT const& nt=*n; \
-    for (CFG::Ruleids::const_iterator ir=nt.ruleids.begin(),er=nt.ruleids.end();ir!=er;++ir) {  \
-      RuleHandle i=*ir; \
-      expr; \
-    } \
-  }
-
-
-using namespace std;
-
-typedef CFG::Rule Rule;
-typedef CFG::NTOrder NTOrder;
-typedef CFG::RHS RHS;
-typedef CFG::BinRhs BinRhs;
-
-/////index ruleids:
-void CFG::UnindexRules() {
-  for (NTs::iterator n=nts.begin(),nn=nts.end();n!=nn;++n)
-    n->ruleids.clear();
-}
-
-void CFG::ReindexRules() {
-  UnindexRules();
-  for (int i=0,e=rules.size();i<e;++i)
-    if (!rules[i].is_null())
-      nts[rules[i].lhs].ruleids.push_back(i);
-}
-
-//////topo order:
-namespace {
-typedef std::vector<char> Seen; // 0 = unseen, 1 = seen+finished, 2 = open (for cycle detection; seen but not finished)
-enum { UNSEEN=0,SEEN,OPEN };
-
-// bottom -> top topo order (rev head->tails topo)
-template <class OutOrder>
-struct CFGTopo {
-// meaningless efficiency alternative: close over all the args except ni - so they're passed as a single pointer.  also makes visiting tail_nts simpler.
-  CFG const& cfg;
-  OutOrder outorder;
-  std::ostream *cerrp;
-  CFGTopo(CFG const& cfg,OutOrder const& outorder,std::ostream *cerrp=&std::cerr)
-    : cfg(cfg),outorder(outorder),cerrp(cerrp) // closure over args
-    , seen(cfg.nts.size()) {  }
-
-  Seen seen;
-  void operator()(CFG::NTHandle ni) {
-    char &seenthis=seen[ni];
-    if (seenthis==UNSEEN) {
-      seenthis=OPEN;
-
-      CFG::NT const& nt=cfg.nts[ni];
-      for (CFG::Ruleids::const_iterator i=nt.ruleids.begin(),e=nt.ruleids.end();i!=e;++i) {
-        Rule const& r=cfg.rules[*i];
-        r.visit_rhs_nts(*this); // recurse.
-      }
-
-      *outorder++=ni; // dfs finishing time order = reverse topo.
-      seenthis=SEEN;
-    } else if (cerrp && seenthis==OPEN) {
-      std::ostream &cerr=*cerrp;
-      cerr<<"WARNING: CFG Topo order attempt failed: NT ";
-      cfg.print_nt_name(cerr,ni);
-      cerr<<" already reached from goal(top) ";
-      cfg.print_nt_name(cerr,cfg.goal_nt);
-      cerr<<".  Continuing to reorder, but it's not fully topological.\n";
-    }
-  }
-
-};
-
-template <class O>
-void DoCFGTopo(CFG const& cfg,CFG::NTHandle goal,O const& o,std::ostream *w=0) {
-  CFGTopo<O> ct(cfg,o,w);
-  ct(goal);
-}
-
-}//ns
-
-// you would need to do this only if you didn't build from hg, or you Binarize without bin_topo option.  note: this doesn't sort the list of rules; it's assumed that if you care about the topo order you'll iterate over nodes.
-void CFG::OrderNTsTopo(NTOrder *o_,std::ostream *cycle_complain) {
-  NTOrder &o=*o_;
-  o.resize(nts.size());
-  DoCFGTopo(*this,goal_nt,o.begin(),cycle_complain);
-}
-
-
-/////sort/uniq:
-namespace {
-RHS null_rhs(1,INT_MIN);
-
-//sort
-struct ruleid_best_first {
-  CFG::Rules const* rulesp;
-  bool operator()(int a,int b) const { // true if a >(prob for ruleid) b
-    return (*rulesp)[b].p < (*rulesp)[a].p;
-  }
-};
-
-//uniq
-struct prob_pos {
-  prob_pos() {}
-  prob_pos(prob_t prob,int pos) : prob(prob),pos(pos) {}
-  prob_t prob;
-  int pos;
-  bool operator <(prob_pos const& o) const { return prob<o.prob; }
-};
-}//ns
-
-int CFG::UniqRules(NTHandle ni) {
-  typedef HASH_MAP<RHS,prob_pos,boost::hash<RHS> > BestRHS; // faster to use trie? maybe.
-  BestRHS bestp; // once inserted, the position part (output index) never changes.  but the prob may be improved (overwrite ruleid at that position).
-  HASH_MAP_EMPTY(bestp,null_rhs);
-  Ruleids &adj=nts[ni].ruleids;
-  Ruleids oldadj=adj;
-  int newpos=0;
-  for (int i=0,e=oldadj.size();i!=e;++i) { // this beautiful complexity is to ensure that adj' is a subsequence of adj (without duplicates)
-    int ri=oldadj[i];
-    Rule const& r=rules[ri];
-    prob_pos pi(r.p,newpos);
-    prob_pos &oldpi=get_default(bestp,r.rhs,pi);
-    if (oldpi.pos==newpos) {// newly inserted
-      adj[newpos++]=ri;
-    } else {
-      SHOWP(DUNIQ,"Uniq duplicate: ") SHOW4(DUNIQ,oldpi.prob,pi.prob,oldpi.pos,newpos);
-      SHOW(DUNIQ,ShowRule(ri));
-      SHOW(DUNIQ,ShowRule(adj[oldpi.pos]));
-      if (oldpi.prob<pi.prob) { // we improve prev. best (overwrite it @old pos)
-        oldpi.prob=pi.prob;
-        adj[oldpi.pos]=ri; // replace worse rule w/ better
-      }
-    }
-
-  }
-  // post: newpos = number of new adj
-  adj.resize(newpos);
-  return newpos;
-}
-
-void CFG::SortLocalBestFirst(NTHandle ni) {
-  ruleid_best_first r;
-  r.rulesp=&rules;
-  Ruleids &adj=nts[ni].ruleids;
-  std::stable_sort(adj.begin(),adj.end(),r);
-}
-
-
-/////binarization:
-namespace {
-
-BinRhs null_bin_rhs(std::numeric_limits<int>::min(),std::numeric_limits<int>::min());
-
-// index i >= N.size()?  then it's in M[i-N.size()]
-//WordID first,WordID second,
-string BinStr(BinRhs const& b,CFG::NTs const& N,CFG::NTs const& M)
-{
-  int nn=N.size();
-  ostringstream o;
-#undef BinNameOWORD
-#define BinNameOWORD(w)                                 \
-  do {                                                  \
-    int n=w; if (n>0) o << TD::Convert(n);              \
-    else {                                              \
-      int i=-n;                                         \
-      if (i<nn) o<<N[i].from<<i; else o<<M[i-nn].from;  \
-    }                                                   \
-  } while(0)
-
-  BinNameOWORD(b.first);
-  o<<'+';
-  BinNameOWORD(b.second);
-  return o.str();
-}
-
-string BinStr(RHS const& r,CFG::NTs const& N,CFG::NTs const& M)
-{
-  int nn=N.size();
-  ostringstream o;
-  for (int i=0,e=r.size();i!=e;++i) {
-    if (i)
-      o<<'+';
-    BinNameOWORD(r[i]);
-  }
-  return o.str();
-}
-
-
-WordID BinName(BinRhs const& b,CFG::NTs const& N,CFG::NTs const& M)
-{
-  return TD::Convert(BinStr(b,N,M));
-}
-
-WordID BinName(RHS const& b,CFG::NTs const& N,CFG::NTs const& M)
-{
-  return TD::Convert(BinStr(b,N,M));
-}
-
-/*
-template <class Rhs>
-struct null_for;
-
-
-template <>
-struct null_for<BinRhs> {
-  static BinRhs null;
-};
-
-template <>
-struct null_for<RHS> {
-  static RHS null;
-};
-
-template <>
-BinRhs null_traits<BinRhs>::xnull(std::numeric_limits<int>::min(),std::numeric_limits<int>::min());
-
-template <>
-RHS null_traits<RHS>::xnull(1,std::numeric_limits<int>::min());
-*/
-
-template <class Rhs>
-struct add_virtual_rules {
-  typedef CFG::RuleHandle RuleHandle;
-  typedef CFG::NTHandle NTHandle;
-  CFG::NTs &nts,new_nts;
-  CFG::Rules &rules, new_rules;
-// above will be appended at the end, so we don't have to worry about iterator invalidation
-  WordID newnt; //negative of NTHandle, or positive => unary lexical item (not to binarize).  fit for rhs of a rule
-  RuleHandle newruleid;
-  typedef HASH_MAP<Rhs,WordID,boost::hash<Rhs> > R2L;
-  R2L rhs2lhs; // an rhs maps to this -virtntid, or original id if length 1
-  bool name_nts;
-  add_virtual_rules(CFG &cfg,bool name_nts=false) : nts(cfg.nts),rules(cfg.rules),newnt(-nts.size()),newruleid(rules.size()),name_nts(name_nts) {
-    HASH_MAP_EMPTY(rhs2lhs,null_traits<Rhs>::xnull);
-  }
-  NTHandle get_virt(Rhs const& r) {
-    NTHandle nt=get_default(rhs2lhs,r,newnt);
-    SHOW(DBIN,newnt) SHOWP(DBIN,"bin="<<BinStr(r,nts,new_nts)<<"=>") SHOW(DBIN,nt);
-    if (newnt==nt) {
-      create(r);
-    }
-    return nt;
-  }
-  inline void set_nt_name(Rhs const& r) {
-    if (name_nts)
-      new_nts.back().from.nt=BinName(r,nts,new_nts);
-  }
-  inline void create_nt(Rhs const& rhs) {
-    new_nts.push_back(CFG::NT(newruleid++));
-    set_nt_name(rhs);
-  }
-  inline void create_rule(Rhs const& rhs) {
-    new_rules.push_back(CFG::Rule(-newnt,rhs));
-    --newnt;
-  }
-  inline void create_adding(Rhs const& rhs) {
-    NTHandle nt=get_default(rhs2lhs,rhs,newnt);
-    assert(nt==newnt);
-    create(rhs);
-  }
-  inline void create(Rhs const& rhs) {
-    SHOWP(DSP,"Create ") SHOW3(DSP,newnt,newruleid,BinStr(rhs,nts,new_nts))
-    create_nt(rhs);
-    create_rule(rhs);
-    assert(newruleid==rules.size()+new_rules.size());assert(-newnt==nts.size()+new_nts.size());
-  }
-
-  ~add_virtual_rules() {
-    append_rules();
-  }
-  void append_rules() {
-    // marginally more efficient
-    batched_append_swap(nts,new_nts);
-    batched_append_swap(rules,new_rules);
-  }
-  inline bool have(Rhs const& rhs,NTHandle &h) const {
-    if (rhs.size()==1) {     // stop creating virtual unary rules.
-      h=rhs[0];
-      return true;
-    }
-    typename R2L::const_iterator i=rhs2lhs.find(rhs);
-    if (i==rhs2lhs.end())
-      return false;
-    h=i->second;
-    return true;
-  }
-  //HACK: prevent this for instantiating for BinRhs.  we need to use rule index because we'll be adding rules before we can update.
-  // returns 1 per replaced NT (0,1, or 2)
-  inline std::string Str(Rhs const& rhs) const {
-    return BinStr(rhs,nts,new_nts);
-  }
-
-  template <class RHSi>
-  int split_rhs(RHSi &rhs,bool only_free=false,bool only_reusing_1=false) {
-    typedef WordID const* WP;
-    //TODO: don't actually build substrings of rhs; define key type that stores ref to rhs in new_nts by index (because it may grow), and also allows an int* [b,e) range to serve as key (i.e. don't insert the latter type of key).
-    int n=rhs.size();
-    if (n<=2) return 0;
-    int longest1=1; // all this other stuff is not uninitialized when used, based on checking this and other things (it's complicated, learn to prove theorems, gcc)
-    int mid=n/2;
-    int best_k;
-    enum {HAVE_L=-1,HAVE_NONE=0,HAVE_R=1};
-    int have1=HAVE_NONE; // will mean we already have some >1 length prefix or suffix as a virt. (it's free).  if we have both we use it immediately and return.
-    NTHandle ntr,ntl;
-    NTHandle bestntr,bestntl;
-    WP b=&rhs.front(),e=b+n;
-    WP wk=b;
-    SHOWM3(DSP,"Split",Str(rhs),only_free,only_reusing_1);
-    int rlen=n;
-    for (int k=1;k<n-1;++k) {
-      //TODO: handle length 1 l and r parts without explicitly building Rhs?
-      ++wk; assert(k==wk-b);
-      --rlen; assert(rlen==n-k);
-      Rhs l(b,wk);
-      if (have(l,ntl)) {
-        if (k>1) { SHOWM3(DSP,"Have l",k,n,Str(l)) }
-        Rhs r(wk,e);
-        if (have(r,ntr)) {
-          SHOWM3(DSP,"Have r too",k,n,Str(r))
-          rhs.resize(2);
-          rhs[0]=ntl;
-          rhs[1]=ntr;
-          return 2;
-        } else if (k>longest1) {
-          longest1=k;
-          have1=HAVE_L;
-          bestntl=ntl;
-          best_k=k;
-        }
-      } else if (rlen>longest1) { // > or >= favors l or r branching, maybe.  who cares.
-        Rhs r(wk,e);
-        if (have(r,ntr)) {
-          longest1=rlen;
-          if (rlen>1) { SHOWM3(DSP,"Have r (only) ",k,n,Str(r)) }
-          have1=HAVE_R;
-          bestntr=ntr;
-          best_k=k;
-        }
-      }
-      //TODO: swap order of consideration (l first or r?) depending on pre/post midpoint?  one will be useless to check for beating the longest single match so far.  check that second
-
-    }
-    // now we know how we're going to split the rule; what follows is just doing the actual splitting:
-
-    if (only_free) {
-      if (have1==HAVE_NONE)
-        return 0;
-      if (have1==HAVE_L) {
-        rhs.erase(rhs.begin()+1,rhs.begin()+best_k); //erase [1..best_k)
-        rhs[0]=bestntl;
-      } else {
-        assert(have1==HAVE_R);
-        rhs.erase(rhs.begin()+best_k+1,rhs.end()); // erase (best_k..)
-        rhs[best_k]=bestntr;
-      }
-      return 1;
-    }
-    /* now we have to add some new virtual rules.
-       some awkward constraints:
-
-       1. can't resize rhs until you save copy of l or r split portion
-
-       2. can't create new rule until you finished modifying rhs (this is why we store newnt then create).  due to vector push_back invalidation.  perhaps we could bypass this by reserving sufficient space first before a splitting pass (# rules and nts created is <= 2 * # of rules being passed over)
-
-    */
-    if (have1==HAVE_NONE) { // default: split down middle.
-      DSP(assert(longest1==1));
-      WP m=b+mid;
-      if (n%2==0) {
-        WP i=b;
-        WP j=m;
-        for (;i!=m;++i,++j)
-          if (*i!=*j) goto notleqr;
-        // [...mid]==[mid...]!
-        RHS l(b,m); // 1. // this is equal to RHS(m,e).
-        rhs.resize(2);
-        rhs[0]=rhs[1]=newnt; //2.
-        create_adding(l);
-        return 1; // only had to create 1 total when splitting down middle when l==r
-      }
-    notleqr:
-      if (only_reusing_1) return 0;
-      best_k=mid; // rounds down
-      if (mid==1) {
-        RHS r(m,e); //1.
-        rhs.resize(2);
-        rhs[1]=newnt; //2.
-        create_adding(r);
-        return 1;
-      } else {
-        Rhs l(b,m);
-        Rhs r(m,e); // 1.
-        rhs.resize(2);
-        rhs[0]=newnt;
-        rhs[1]=newnt-1; // 2.
-        create_adding(l);
-        create_adding(r);
-        return 2;
-      }
-    }
-    WP best_wk=b+best_k;
-    //we build these first because adding rules may invalidate the underlying pointers (we end up binarizing already split virt rules)!.
-    //wow, that decision (not to use index into new_nts instead of pointer to rhs), while adding new nts to it really added some pain.
-    if (have1==HAVE_L) {
-      Rhs r(best_wk,e); //1.
-      rhs.resize(2);
-      rhs[0]=bestntl;
-      DSP(assert(best_wk<e-1)); // because we would have returned having both if rhs was singleton
-      rhs[1]=newnt; //2.
-      create_adding(r);
-    } else {
-      DSP(assert(have1==HAVE_R));
-      DSP(assert(best_wk>b+1)); // because we would have returned having both if lhs was singleton
-      Rhs l(b,best_wk); //1.
-      rhs.resize(2);
-      rhs[0]=newnt; //2.
-      rhs[1]=bestntr;
-      create_adding(l);
-    }
-    return 1;
-  }
-};
-
-}//ns
-
-void CFG::BinarizeSplit(CFGBinarize const& b) {
-  add_virtual_rules<RHS> v(*this,b.bin_name_nts);
-  CFG_FOR_RULES(i,v.split_rhs(rules[i].rhs,false,false));
-  Rules &newr=v.new_rules;
-#undef CFG_FOR_VIRT
-#define CFG_FOR_VIRT(r,expr)                                                 \
-  for (int i=0,e=newr.size();i<e;++i) { \
-    Rule &r=newr[i];expr;  } // NOTE: must use indices since we'll be adding rules as we iterate.
-
-  int n_changed_total=0;
-  int n_changed=0; // quiets a warning
-#define CFG_SPLIT_PASS(N,free,just1) \
-  for (int pass=0;pass<b.N;++pass) { \
-    n_changed=0; \
-    CFG_FOR_VIRT(r,n_changed+=v.split_rhs(r.rhs,free,just1)); \
-    if (!n_changed) { \
-      break; \
-    } n_changed_total+=n_changed; }
-
-  CFG_SPLIT_PASS(split_passes,false,false)
-    if (n_changed==0) return;
-  CFG_SPLIT_PASS(split_share1_passes,false,true)
-  CFG_SPLIT_PASS(split_free_passes,true,false)
-
-}
-
-void CFG::Binarize(CFGBinarize const& b) {
-  if (!b.Binarizing()) return;
-  cerr << "Binarizing "<<b<<endl;
-  if (b.bin_thresh>0)
-    BinarizeThresh(b);
-  if (b.bin_split)
-    BinarizeSplit(b);
-  if (b.bin_l2r)
-    BinarizeL2R(false,b.bin_name_nts);
-  if (b.bin_topo) //TODO: more efficient (at least for l2r) maintenance of order?
-    OrderNTsTopo();
-
-}
-
-namespace {
-}
-
-void CFG::BinarizeThresh(CFGBinarize const& b) {
-  throw runtime_error("TODO: some fancy linked list thing - see NOTES.partial.binarize");
-}
-
-
-void CFG::BinarizeL2R(bool bin_unary,bool name) {
-  add_virtual_rules<BinRhs> v(*this,name);
-cerr << "Binarizing left->right " << (bin_unary?"real to unary":"stop at binary") <<endl;
-  HASH_MAP<BinRhs,NTHandle,boost::hash<BinRhs> > bin2lhs; // we're going to hash cons rather than build an explicit trie from right to left.
-  HASH_MAP_EMPTY(bin2lhs,null_bin_rhs);
-  // iterate using indices and not iterators because we'll be adding to both nts and rules list?  we could instead pessimistically reserve space for both, but this is simpler.  also: store original end of nts since we won't need to reprocess newly added ones.
-  int rhsmin=bin_unary?0:1;
-  //NTs new_nts;
-  //Rules new_rules;
-  //TODO: this could be factored easily into in-place (append to new_* like below) and functional (nondestructive copy) versions (copy orig to target and append to target)
-//  int newnt=nts.size(); // we're going to store binary rhs with -nt to keep distinct from words (>=0)
-//  int newruleid=rules.size();
-  BinRhs bin;
-  CFG_FOR_RULES(ruleid,
-/*  for (NTs::const_iterator n=nts.begin(),nn=nts.end();n!=nn;++n) {
-    NT const& nt=*n;
-    for (Ruleids::const_iterator ir=nt.ruleids.begin(),er=nt.ruleids.end();ir!=er;++ir) {
-    RuleHandle ruleid=*ir;*/
-//      SHOW2(DBIN,ruleid,ShowRule(ruleid));
-                Rule & rule=rules[ruleid];
-      RHS &rhs=rule.rhs; // we're going to binarize this while adding newly created rules to new_...
-      if (rhs.empty()) continue;
-      int r=rhs.size()-2; // loop below: [r,r+1) is to be reduced into a (maybe new) binary NT
-      if (rhsmin<=r) { // means r>=0 also
-        bin.second=rhs[r+1];
-        int bin_to; // the replacement for bin
-//        assert(newruleid==rules.size()+new_rules.size());assert(newnt==nts.size()+new_nts.size());
-        // also true at start/end of loop:
-        for (;;) { // pairs from right to left (normally we leave the last pair alone)
-          bin.first=rhs[r];
-          bin_to=v.get_virt(bin);
-/*          bin_to=get_default(bin2lhs,bin,v.newnt);
-//          SHOW(DBIN,r) SHOW(DBIN,newnt) SHOWP(DBIN,"bin="<<BinStr(bin,nts,new_nts)<<"=>") SHOW(DBIN,bin_to);
-          if (v.newnt==bin_to) { // it's new!
-            new_nts.push_back(NT(newruleid++));
-            //now newnt is the index of the last (after new_nts is appended) nt.  bin is its rhs.  bin_to is its lhs
-            new_rules.push_back(Rule(newnt,bin));
-            ++newnt;
-            if (name) new_nts.back().from.nt=BinName(bin,nts,new_nts);
-          }
-*/
-          bin.second=bin_to;
-          --r;
-          if (r<rhsmin) {
-            rhs[rhsmin]=bin_to;
-            rhs.resize(rhsmin+1);
-            break;
-          }
-        }
-      })
-                /*
-    }
-  }
-                */
-#if 0
-  // marginally more efficient
-  batched_append_swap(nts,new_nts);
-  batched_append_swap(rules,new_rules);
-//#else
-  batched_append(nts,new_nts);
-  batched_append(rules,new_rules);
-#endif
-}
-
-namespace {
-inline int nt_index(int nvar,Hypergraph::TailNodeVector const& t,bool target_side,int w) {
-  assert(w<0 || (target_side&&w==0));
-  return t[target_side?-w:nvar];
-}
-}
-
-void CFG::Init(Hypergraph const& hg,bool target_side,bool copy_features,bool push_weights) {
-  uninit=false;
-  hg_=&hg;
-  Hypergraph::NodeProbs np;
-  goal_inside=hg.ComputeNodeViterbi(&np);
-  pushed_inside=push_weights ? goal_inside : prob_t(1);
-  int nn=hg.nodes_.size(),ne=hg.edges_.size();
-  nts.resize(nn);
-  goal_nt=nn-1;
-  rules.resize(ne);
-  for (int i=0;i<nn;++i) {
-    nts[i].ruleids=hg.nodes_[i].in_edges_;
-    hg.SetNodeOrigin(i,nts[i].from);
-  }
-  for (int i=0;i<ne;++i) {
-    Rule &cfgr=rules[i];
-    Hypergraph::Edge const& e=hg.edges_[i];
-    prob_t &crp=cfgr.p;
-    crp=e.edge_prob_;
-    cfgr.lhs=e.head_node_;
-    IF_CFG_TRULE(cfgr.rule=e.rule_;)
-    if (copy_features) cfgr.f=e.feature_values_;
-    if (push_weights) crp /=np[e.head_node_];
-    TRule const& er=*e.rule_;
-    vector<WordID> const& rule_rhs=target_side?er.e():er.f();
-    int nr=rule_rhs.size();
-    RHS &rhs_out=cfgr.rhs;
-    rhs_out.resize(nr);
-    Hypergraph::TailNodeVector const& tails=e.tail_nodes_;
-    int nvar=0;
-    //split out into separate target_side, source_side loops?
-    for (int j=0;j<nr;++j) {
-      WordID w=rule_rhs[j];
-      if (w>0)
-        rhs_out[j]=w;
-      else {
-        int n=nt_index(nvar,tails,target_side,w);
-        ++nvar;
-        if (push_weights) crp*=np[n];
-        rhs_out[j]=-n;
-      }
-    }
-    assert(nvar==er.Arity());
-    assert(nvar==tails.size());
-  }
-}
-
-void CFG::Clear() {
-  rules.clear();
-  nts.clear();
-  goal_nt=-1;
-  hg_=0;
-}
-
-namespace {
-CFGFormat form;
-}
-
-void CFG::PrintRule(std::ostream &o,RuleHandle rulei,CFGFormat const& f) const {
-  Rule const& r=rules[rulei];
-  f.print_lhs(o,*this,r.lhs);
-  f.print_rhs(o,*this,r.rhs.begin(),r.rhs.end());
-  f.print_features(o,r.p,r.f);
-  IF_CFG_TRULE(if (r.rule) o<<f.partsep<<*r.rule;)
-}
-void CFG::PrintRule(std::ostream &o,RuleHandle rulei) const {
-  PrintRule(o,rulei,form);
-}
-string CFG::ShowRule(RuleHandle i) const {
-  ostringstream o;PrintRule(o,i);return o.str();
-}
-
-void CFG::Print(std::ostream &o,CFGFormat const& f) const {
-  assert(!uninit);
-  if (!f.goal_nt_name.empty()) {
-    o << '['<<f.goal_nt_name <<']';
-    WordID rhs=-goal_nt;
-    f.print_rhs(o,*this,&rhs,&rhs+1);
-    if (pushed_inside!=prob_t::One())
-      f.print_features(o,pushed_inside);
-    o<<'\n';
-  }
-  CFG_FOR_RULES(i,PrintRule(o,i,f);o<<'\n';)
-}
-
-void CFG::Print(std::ostream &o) const {
-  Print(o,form);
-}
-
-std::ostream &operator<<(std::ostream &o,CFG const &x) {
-  x.Print(o);
-  return o;
-}