/*
  Copyright Dave Bone 1998 - 2014 
  All Rights Reserved. 
  No part of this document may be reproduced without written consent from the author.
	
FILE:		rules_use_cnt.lex
Dates:		23 Sept. 2005
Purpose:	used to optimize the recycled rules table use.
*/
/@
@i "/usr/local/yacco2/copyright.w"
@** |rules_use_cnt| grammar.\fbreak
Determine each rule's use count for generating recycled rules tables.
It answers the question: What is the maximum number of rules
needed in each recycled rules table?.
If the rule has recursion then indicate in rule's definition.
The heart of the algorithm is to determine the maximum rule's use count 
against all rules rhs. 
The grammar tree is walked in top-down fashion: prefix
using a filter for only rule-def, subrule-def, and referenced-rules. \fbreak
\fbreak
Stage 1: Build per rule its rule use skeleton. This is done upon entry
into the grammar using the ``op directive'' before the grammar parses.
Removeal of all the T vocabulary from the rhs leave its bones.
If the resultant rhs is empty then it does not partake
in the analysis as there are no rule used.
The rule's skeleton is deposited within its ``rule-def''
for the balance of the stages.\fbreak
\fbreak
Stage 2: Determine rule's use count per skeleton.\fbreak
The max use count is posted in the rule's definition 
to generate the space requirement for the rule's
recycling table.
\fbreak
\fbreak
Remarks:\fbreak
The walked skeleton checks the use count of indirect rule's in use.
For example:\fbreak
\settabs\+\indent&1in\qquad&\qquad&\qquad&\cr
\+&\it Rule&&{\it subrule's symbols}\cr
\+&Rs &$\rightarrow$ &Ra Rxx Ra Rxxx $\bot$\cr
\+&Ra &$\rightarrow$ &a \cr
\+&&$\rightarrow$ &Ra a\cr
\+&Rxx&$\rightarrow$ &x Ra x Ra b\cr
\+&Rxxx&$\rightarrow$ &x Ra x Ra x Ra\cr
\fbreak
What is the maximum use count of Ra in the above grammar?
It is 6 caused by the 1st rule. 
Why?
Here is an example to support my statement.\fbreak
\settabs\+\indent&a a x a x a b a x a x a x a a\&\qquad&a a x a x a b a x a x a x a a a&Comments\cr
\+&{\it Parse Stack}&{\it input string to parse}&Comments\cr
\+& & a a x a x a b a x a x a x a a\cr
\+&a & a x a x a b a x a x a x a a\cr
\+&Ra & a x a x a b a x a x a x a a\cr
\+&Ra a & x a x a b a x a x a x a a& recursion: 2 Ra --- lhs and stacked rhs\cr
\+&Ra & x a x a b a x a x a x a a& Ra lhs, popped rhs Ra recycled \cr
\+&Ra x & a x a b a x a x a x a a\cr
\+&Ra x a & x a b a x a x a x a a\cr
\+&Ra x Ra & x a b a x a x a x a a\cr
\+&Ra x Ra x & a b a x a x a x a a\cr
\+&Ra x Ra x a & b a x a x a x a a\cr
\+&Ra x Ra x Ra & b a x a x a x a a\cr
\+&Ra x Ra x Ra b & a x a x a x a a\cr
\+&Ra Rxx & a x a x a x a a\cr
\+&Ra Rxx a & x a x a x a a\cr
\+&Ra Rxx Ra & x a x a x a a\cr
\+&Ra Rxx Ra x & a x a x a a\cr
\+&Ra Rxx Ra x a & x a x a a\cr
\+&Ra Rxx Ra x Ra & x a x a a\cr
\+&Ra Rxx Ra x Ra x & a x a a\cr
\+&Ra Rxx Ra x Ra x a& x a a\cr
\+&Ra Rxx Ra x Ra x Ra& x a a\cr
\+&Ra Rxx Ra x Ra x Ra x& a a\cr
\+&Ra Rxx Ra x Ra x Ra x a& a\cr
\+&Ra Rxx Ra x Ra x Ra x Ra& a\cr
\+&Ra Rxx Ra x Ra x Ra x Ra a& note: extra Ra for lhs/rhs from recursion\cr
\+&Ra Rxx Ra x Ra x Ra x Ra& though 5 Ra on stack, above lhs/rhs requires 6\cr
\+&Ra Rxx Ra Rxxx& where Rxxx's rhs needs 4 before it reduces\cr
\fbreak
There are 2 direct Ra used and 4 indirect Ra from Rxxx's rhs 
before it is reduced: 3 direct Ra used + 1 Ra for the recursion
on its last recognized Ra before Rxxx's rhs is completely recognized.
Recursion of Ra demands 2 Ra: lhs / rhs.
The first ``a'' recognized creates a Ra that is pushed onto the stack.
The following ``a'' get recognized by the Ra left recursion rule.
The first Ra sits on the parse stack whilst the second Ra 
representing the lhs gets ready for the reduce to take place.
With each recurse reduction the rhs's popped Ra is freed up for recycling.
After the Rxxx reduction, its 3 Ra also get recycled for use.
On the parse stack there still remains 2 active Ra
 of Rs's rhs that remains
to be recognized.
If Rxxx was not present in the grammar, the Ra maximum use count
would be
5: 2 direct and 2+1 indirect counts from Rxx.\fbreak

@/

fsm	
(fsm-id "rules_use_cnt.lex"
,fsm-filename rules_use_cnt
,fsm-namespace NS_rules_use_cnt
,fsm-class Crules_use_cnt{
  user-prefix-declaration
#include "o2_externs.h"
extern int MAX_USE_CNT_RxR
	(NS_yacco2_terminals::rule_def* Rule_use
	,NS_yacco2_terminals::rule_def* Against_rule);
  ***
  user-declaration
    public:
	std::list<NS_yacco2_terminals::rule_def* > rules_list_for_use_cnt_;
	NS_yacco2_terminals::rule_def* rule_def_;
	NS_yacco2_terminals::T_subrule_def* subrule_def_;
	void mark_recursion_rule_use(NS_yacco2_terminals::refered_rule* Refered_rule);
        yacco2::AST* bld_rule_s_use_skeleton(yacco2::AST* Rule_t);
  ***
  user-implementation       
   void Crules_use_cnt::mark_recursion_rule_use
	(NS_yacco2_terminals::refered_rule* Refered_rule){
	    using namespace NS_yacco2_terminals;
	    rule_in_stbl* rule_in_tbl = Refered_rule->Rule_in_stbl();
		rule_def* rd = rule_in_tbl->r_def();
		if(rd == rule_def_){
		  rd->recursive(YES);
		  rd->lhs_use_cnt(1);
		}
	}
/@
@*3 |bld_rule_s_use_skeleton|.
@/
        AST* Crules_use_cnt::bld_rule_s_use_skeleton(AST* Rule_t){
		using namespace NS_yacco2_T_enum;
		set<int> rules_use_cnt_filter;
		rules_use_cnt_filter.insert(T_Enum::T_T_subrule_def_);  
		rules_use_cnt_filter.insert(T_Enum::T_rule_def_);
		rules_use_cnt_filter.insert(T_Enum::T_refered_rule_);

		tok_can_ast_functor rules_use_walk_functr;
		ast_postfix rules_use_walk(*Rule_t,&rules_use_walk_functr
		,&rules_use_cnt_filter,ACCEPT_FILTER);
		tok_can<AST*> rules_use_can(rules_use_walk);
		int x(0);
		CAbs_lr1_sym* sym = rules_use_can[x];
		rule_def* rd(0);
		AST* lk_rr_t(0);
		AST* rr_t(0);
		AST* sr_t(0);
		AST* lk_sr_t(0);
		AST* r_t(0);
		for(;sym->enumerated_id() != LR1_Eog;++x,sym=rules_use_can[x]){
		  switch(sym->enumerated_id()){
		    case T_Enum::T_rule_def_:{
			if(sr_t == 0) return 0;// no rhs with refered rules
			r_t = new AST(*sym);
			AST::join_pts(*r_t,*sr_t);
			return r_t;
		    }
		    case T_Enum::T_T_subrule_def_:{
			if(rr_t == 0) break;// no refered rules
			AST* srt = new AST(*sym);
			AST::join_pts(*srt,*rr_t);
			lk_rr_t = 0;
			rr_t = 0;
			if(sr_t == 0){
			  sr_t = srt;
			  lk_sr_t = srt;
			}else{
			  AST::join_sts(*lk_sr_t,*srt);
			  lk_sr_t = srt;
			}
			break;
		    }
		    case T_Enum::T_refered_rule_:{
			AST* rrt = new AST(*sym);
			if(rr_t == 0){
			  rr_t = rrt;
			  lk_rr_t = rrt;
			}else{
			  AST::join_sts(*lk_rr_t,*rrt);
			  lk_rr_t = rrt;
			}
			break;
		    }
		  }//switch
		}//for
	    return 0;
	}
  ***
/@
Build use skeletons per rule definition.
As the container is of tree type, the first token is
the ``start'' rule.
I can get its tree node and breadth walk it for its brothers.
The rules list for ``use count'' assessment is built: Rules vocabulary - ``start'' rule.
The ``start'' rule is removed as it never appears within a rhs as per a grammar's definition. 
@/
  op
    tok_can<AST*>* can = (tok_can<AST*>*)parser()->token_supplier();
    AST* start_rule_t = can->ast(0);
    AST* t = start_rule_t;
    for(;t != 0;t=AST::get_younger_sibling(*t,1)){
	rule_def* rd = (rule_def*)AST::content(*t);
        AST* use_skeleton_t = bld_rule_s_use_skeleton(t);
	if(use_skeleton_t != 0) rd->rule_use_skeleton(use_skeleton_t);
        if(t != start_rule_t) rules_list_for_use_cnt_.push_back(rd);
    }
    rule_def_ = 0;
    subrule_def_ = 0;
  ***
}
,fsm-version "1.0",fsm-date "6 July 2007",fsm-debug "false"
,fsm-comments "Optimization: Count ``rules used'' \n to lower new / delete rule cycles while parsing.")
@"/usr/local/yacco2/compiler/grammars/yacco2_T_includes.T"

rules{
Rrules_use_cnt  
(){
  -> Rrules eog
}

Rrules  (){
  -> Rrule
  -> Rrules Rrule
}

Rrule  (){
  -> Rrule_def Rsubrules 
}

Rrule_def  (){
  -> "rule-def" {
/@
Post the rule's used cnt within its definition to be used
in generating the recycle tables.
Remember the current rule is assessing its
indirect rule usage. It is the rule usage definition that gets updated
for its recycle table requirements and not the current rule.
@/
  op
    Crules_use_cnt* fsm = (Crules_use_cnt*)rule_info__.parser__->fsm_tbl__;
    fsm->rule_def_ = sf->p1__;
    std::list<NS_yacco2_terminals::rule_def* >::iterator i =  fsm->rules_list_for_use_cnt_.begin();
    std::list<NS_yacco2_terminals::rule_def* >::iterator ie =  fsm->rules_list_for_use_cnt_.end();
    for(;i != ie;++i){
	rule_def* for_rule = *i;
        int use_cnt = MAX_USE_CNT_RxR(for_rule,fsm->rule_def_);
	if(for_rule->rhs_use_cnt() < use_cnt){
          for_rule->rhs_use_cnt(use_cnt);
	}
    }
  ***
  }
}

Rsubrules  (){
  -> Rsubrule Rsubrule_s_used_rules_epi 
  -> Rsubrules Rsubrule Rsubrule_s_used_rules_epi
}

Rsubrule  (){
  -> Rsubrule_def
}

Rsubrule_def  (){
  -> "subrule-def" {
  op
    Crules_use_cnt* fsm = (Crules_use_cnt*)rule_info__.parser__->fsm_tbl__;
    fsm->subrule_def_ = sf->p1__;
  ***
  }
}

Rsubrule_s_used_rules_epi  (){
  -> 
  -> Rsubrule_s_used_rules
}

Rsubrule_s_used_rules  (){
  -> "refered-rule"  {
  op
    Crules_use_cnt* fsm = (Crules_use_cnt*)rule_info__.parser__->fsm_tbl__;
    fsm->mark_recursion_rule_use(sf->p1__);
  ***
  }
  -> Rsubrule_s_used_rules "refered-rule"  {
  op
    Crules_use_cnt* fsm = (Crules_use_cnt*)rule_info__.parser__->fsm_tbl__;
    fsm->mark_recursion_rule_use(sf->p2__);
  ***
  }
}

}// end of rules