item.cc

来自「This is a resource based on j2me embedde」· CC 代码 · 共 1,241 行 · 第 1/2 页

/*
 * @(#)item.cc	1.10 06/10/10
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program is free software; you can redistribute it and/or  
 * modify it under the terms of the GNU General Public License version  
 * 2 only, as published by the Free Software Foundation.   
 *   
 * This program is distributed in the hope that it will be useful, but  
 * WITHOUT ANY WARRANTY; without even the implied warranty of  
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU  
 * General Public License version 2 for more details (a copy is  
 * included at /legal/license.txt).   
 *   
 * You should have received a copy of the GNU General Public License  
 * version 2 along with this work; if not, write to the Free Software  
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  
 * 02110-1301 USA   
 *   
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa  
 * Clara, CA 95054 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include "symbol.h"
#include "rule.h"
#include "path.h"
#include "item.h"
#include "POINTERLIST.h"

/*****************************************************************
 * formerly the contents of pattern_implementation.{cc,h}.
 * placed here only for the convenience of the optimizing inliner.
 *
 *****************************************************************/
/*
 * This declares the following classes:
 *	item_body
 * A path plus a rule make an item.
 */

int n_setalloc, n_setfree, max_setactive, n_setactive;
int n_sparsealloc, n_sparsefree, max_sparseactive, n_sparseactive;

#define DID_SETALLOC	{ n_setalloc+=1; n_setactive+= 1; if ( n_setactive > max_setactive ) max_setactive = n_setactive; }
#define SETFREE(p) { free ((char*)(p)); n_setfree++; n_setactive--; }

#define DID_SPARSEALLOC(n) { n_sparsealloc += (n); n_sparseactive += (n); if ( n_sparseactive > max_sparseactive ) max_sparseactive = n_sparseactive; }
#define DID_SPARSE_REALLOC(n) DID_SPARSEALLOC( (n)/2)
#define DID_SPARSEFREE(n) { n_sparseactive-=(n); n_sparsefree+=(n); }

class symbol;

/*
 * A "path" is used for navigating in a binary tree.
 * It is used as part of an item, and names the subtree match
 * to which the item corresponds. (See below)
 * Think of a path as a string of L's and R's. Thus
 * the path "LLR" corresponds to a subtree that, starting
 * from the tree's root, can be found by descending via the
 * left link, then another left link, then a right link.
 * A zero-length path is allowed.
 * Path comparison is used when comparing items, and
 * in defining an item collating sequence.
 */

/*
 * A item represents a full or partial match of a rule,
 * without cost information. It has two representations:
 * (a) the rule + path + other info struct-sort-of-thing,
 * which we call a item_body, and
 * (b) a cookie which we will call either a item or a
 * item: we'll see.
 * "Other info" includes larger matches for partial rule matches.
 */

class item_body {
	path   			p_path;
	rule * 			p_rule;
	ruletree *		p_subtree;
	item		p_parent_match;
public:
	/*
	 * construct a null item.
	 */
	item_body(void) : p_path()
	    { p_rule = 0; p_parent_match = item_none; }

	/*
	 * construct a item from a path and a rule and a subtree
	 */
	item_body( path p, rule * r, ruletree * );

	/*
	 * add parent match to existing item.
	 * Ensures that item is currently without parent.
	 */
	void add_parent_item( item );

	/*
	 * extract components.
	 */
	rule *		item_rule()   { return p_rule; }
	path   		item_path()   { return p_path; }
	ruletree * 	item_subtree(){ return p_subtree; }
	item	item_parent() { return p_parent_match; }
		

	/*
	 * print a item.
	 * Usage:
	 *	item  pt;
	 *	pt.print(stdout);
	 * Prints out partial rule match only: not other information.
	 */
	void print(FILE * out = stdout);

	/*
	 * determine if a item represents a match of the
	 * full body of a rule, or whether it is on the left
	 * or the right of its parent operator node.
	 * Usage:
	 *	item * ptmp;
	 *	if (ptmp->parent_subpart() == item_table::fullmatch) ...
	 */

	item_table::subgraph_part parent_subpart( void );

	/*
	 * The weak comparison functions.
	 * Usage:
	 *	item * ptmp;
	 *	item * ptmp2;
	 *	if ( ptmp->same_match( *ptmp2 ) )...
	 *	if ( ptmp->lessthan_match( *ptmp2 ) )...
	 */
	// a weaker equality than  ==
	inline int same_match ( register const item_body &other ) const
	{
		return( this->p_rule == other.p_rule
		     && this->p_path == other.p_path );
	}

	/*
	 * Precedence for inequality is:
	 * rule pointer (rules are unique, of course),
	 * then path.
	 */
	inline int lessthan_match ( register const item_body &b ) const
	{
		register int result;
		if ( this->p_rule == b.p_rule ){
			result = this->p_path < b.p_path;
		} else {
			result = this->p_rule < b.p_rule;
		}
		return result;
	}
}; // end class item_body

ruletree*
follow_path( class path &p, ruletree *rtp )
{
	int n;
	int bits;

	for( n=1, bits=p.path_bits; n<= p.path_length; n+=1, bits>>=1)
		if ((bits&1) == p.left)
			rtp = rtp->left;
		else
			rtp = rtp->right;
	return rtp;
}

void
path::print(FILE * out) const
{
	int n;
	int bits;

	n = path_length;
	bits = path_bits;
	while( n-->0){
		switch( bits&1){
		case left:  putc('L', out); break;
		case right: putc('R', out); break;
		default:    putc('X', out); break;
		}
		bits >>=1;
	}
	fflush( out );
}

static void
print_tree( struct ruletree * t, path match_path, path cur_path, FILE * out )
{
	symbol * s = t->node;
	int /*Boolean*/ submatch;
	path left_path;


	submatch = match_path == cur_path;
	left_path = cur_path;
	left_path.descend( left_path.left );
	if (submatch)
		fputs("< ", out);
	fprintf(out, "%s ", s->name() );
	switch( s->type() ){
	case symbol::terminal:
	case symbol::nonterminal: 
		// done
		break;
	case symbol::unaryop:
		// print subtree
		print_tree( t->left, match_path, left_path, out );
		break;
	case symbol::binaryop:
		// print subtrees
		print_tree( t->left, match_path, left_path, out );
		cur_path.descend( cur_path.right );
		print_tree( t->right, match_path, cur_path, out );
		break;
	}
	if (submatch)
		fputs("> ", out);
}

void
item_body::print( FILE* out )
{
	path z;
	path p = p_path;
	rule * r = p_rule;
	fprintf( out, "[%3d] %s -> ", r->ruleno(), r->lhs()->name());
	print_tree( r->rhs(), p, z, out );
}

item_body::item_body( path p, rule * r, ruletree * t )
{
	p_path = p;
	p_rule = r;
	p_subtree = t;
	p_parent_match = item_none;
}

void
item_body::add_parent_item( item x )
{
	assert( p_parent_match == item_none);
	assert( x <=item_max );
	p_parent_match = x;
}

item_table::subgraph_part
item_body::parent_subpart()
{
	switch( p_path.last_move() ){
	case path::left:
		return item_table::leftpart;
	case path::right:
		return item_table::rightpart;
	case path::XX:
		return item_table::fullmatch;
	default:
		assert(0);
	}
}
/*
 * end of inlined implementation stuff..
 */
/*****************************************************************/

DERIVED_POINTERLIST_CLASS( plist, item_body *, plist_iterator );

/*
 * item table. 
 * The one real residence of information about items.
 * Created once after rule reading, using create,
 * then probed using other routines. A item_table contains
 * all possible partial and full rule matches, given the
 * rulelist argument to create.
 * Outside this table, items are represented by the item.
 */
item_table all_items;

/*
 * print a item table
 * for debugging 
 */
void
item_table::print()
{
	register int n, max;
	register item_body * p;
	item parent;
	char matchchar;

	max = n_items-1;
	p = items;
	for( n=0; n<=max; n++){
		printf("%d)\t", n );
		p[n].print();
		parent = p[n].item_parent();
		switch ( p[n].parent_subpart() ){
		case fullmatch:
			matchchar = 'M';
			break;
		case leftpart:
			matchchar = 'L';
			break;
		case rightpart:
			matchchar = 'R';
			break;
		default:
			matchchar = 'X';
			break;
		}
		printf("\t%c", matchchar);
		if ( parent != item_none )
			printf(" %d", parent );
		putchar('\n');
	}
	fflush(stdout);
}

/*
 * print a specific item
 */
void 
item_table::item_print( item c, FILE * out  )
{
	assert( c < (unsigned)n_items );
	items[c].print(out);
}

/*
 * Answer more specific questions about a item.
 */

/*
 * extract components.
 */
rule *
item_table::item_rule( item c )
{
	assert( c < (unsigned)n_items );
	return items[c].item_rule();
}

ruletree *
item_table::item_subtree( item c )
{
	assert( c < (unsigned)n_items );
	return items[c].item_subtree();
}

path   		
item_table::item_path( item c )
{
	assert( c < (unsigned)n_items );
	return items[c].item_path();
}

item	
item_table::item_parent( item c )
{
	assert( c < (unsigned)n_items );
	return items[c].item_parent();
}
	
/*
 * determine if a item represents a match of the
 * full body of a rule, or whether it is on the left
 * or the right of its parent operator node.
 * Usage:
 *	item ptmp;
 *	item_table  pt;
 *	if (pt.item_subpart(ptmp) == item_table::fullmatch) ...
 */

item_table::subgraph_part 
item_table::item_subpart( item c )
{
	assert( c < (unsigned)n_items );
	return items[c].parent_subpart();
}

/*
 * Create a item_table by
 * 1) reading each rule and creating all possible matches
 *    and submatches.
 * 2) Constructing parental relationships between them.
 * 3) Attaching information to each rule giving its relations
 *    to the table created, especially a item_costset table attached
 *    to its lhs symbol.
 * A slightly more clever program might be able to do all three in one
 * pass. If performance of this code becomes an issue, we could become
 * more clever.
 */

/*
 * 1) Routines to make a list of all matches for each rule. and
 * 2) Construct parential relationships, almost as a side effect.
 */

static void
find_submatch(
	rule *r,
	path p,
	ruletree *t,
	item parent_cookie,
	item * cur_cookie_p,
	plist *v )
{
	item_body * pbp;
	item my_cookie;
	path rpath;

	// register this match.
	// it is important here that v->add have ADD AT END semantics,
	// otherwise our indexing strategy is hopelessly flawed!

	pbp = new item_body( p, r, t );
	my_cookie = *cur_cookie_p;
	*cur_cookie_p += 1;
	if ( parent_cookie == item_none )
		r->fullmatch_item = my_cookie;
	else
		pbp->add_parent_item( parent_cookie );
	v->add( pbp );

	// descend to find further submatches.
	switch( t->node->type() ){
	case symbol::binaryop:
		rpath = p;
		rpath.descend( rpath.right );
		find_submatch( r, rpath, t->right, my_cookie, cur_cookie_p, v );
		// FALLTHROUGH
	case symbol::unaryop:
		p.descend( p.left );
		find_submatch( r, p, t->left, my_cookie, cur_cookie_p, v );
		break;
	case symbol::terminal:
	case symbol::nonterminal:
		// all done
		break;
	}
}

static void
find_all_submatches( rule *r, plist * v, item * cur_cookie_p )
{
	path p;
	find_submatch( r, p, r->rhs(), item_none, cur_cookie_p, v );
}


static item_body *
make_match_list( rulelist *rlp, int * n_pb_p )
{
	rulelist_iterator rl_i = *rlp;
	rule * rp;
	item_body * pbp;	// the collection of item's we're building
	item_body * pp;
	int i, n_pb;
	item si = 0;
	plist all_pattrns;
	plist_iterator pl_i;

	// for every rule 
	while ( (rp = rl_i.next() ) != 0 ){
		// make all possible item_bodies
		// and add them to my list.
		find_all_submatches( rp, &all_pattrns, &si );
	}
	// number of item bodies is ...
	n_pb = all_pattrns.n();
	assert(n_pb == si );
	* n_pb_p = n_pb;

	// turn my un-indexable list into a table.
	// remember: list was add-at-end, so cookies should work for indexing.
	pbp = (item_body*)malloc( all_pattrns.n()*sizeof(item_body) );
	assert( pbp != 0 );
	i = 0;
	pl_i = all_pattrns;
	while( (pp = pl_i.next() ) != 0 ){
		pbp[i] = *pp;
		delete pp;
		i += 1;
	}
	assert( i == n_pb );
	all_pattrns.destruct();
	return pbp;
}

void
item_table::create( rulelist * rlp )
{
	items = make_match_list( rlp, & n_items );
	assert( n_items > 0 );
	assert( n_items <= item_max );
}

void
printitems(){
	puts("\nITEM TABLE");
	all_items.print();
}

void
item_setup(){
	all_items.create( &all_rules );
}

/*
 * As a side effect of creating the items, we also attached to each
 * rule a cookie giving the name of the first item involving that rule.
 * We will use this fact in finding, for each symbol
 * the list of places it occure in any rule rhs. We will also use
 * find_instance, I suspect.
 */

void
item_costset::print( FILE * out ) const
{
	register item cookie_max;
	register item i;
	register item_cost * p = item_costset_p;

	if ( item_costset_p == 0 ){
		// empty set.
		return;
	}
	cookie_max = item_costset_table->n()-1;
	for( i = 0; i <= cookie_max; i++ ){
		if ( item_costset_p[i] != item_cost_none ){
			fputs( "\t[ ", out);
			item_costset_table->item_print( i, out );
			fprintf( out, " ; %d ]\n", item_costset_p[i] );
		}
	}
}

static int
find_instance(
	item_cost * item_costset_set,
	symbol * symp,
	rule *r,
	item_table * ptp,
	item_cost c )
{
	item v;
	item v_max = ptp->n()-1;
	int changed; // Boolean;
	ruletree * rtp;
	/*
	 * for every item involving this rule,
	 * see if the subtree matched is rooted by symbol s.
	 * If it is, then add it to the item_costset_set, using cost c,
	 * so long as the set doesn't already contain this cookie with
	 * equal or lower cost.
	 */
	changed = 0;
	for( v = r->fullmatch_item;
	    v <= v_max && ptp->item_rule(v) == r;
	    v++ ){
		// if it's already present and cheaper, don't bother.
		if ( item_costset_set[v] <= c )
			continue;
		rtp = ptp->item_subtree(v);
		if ( rtp->node == symp ){
			// found one. add.
			item_costset_set[v] = c;
			changed += 1;
		}
	}
	return changed;
}

static item_cost *
allocate_item_costset_space( unsigned n )
{
	item_cost * item_costset_set;
	item_costset_set = (item_cost*)malloc( n*sizeof(item_cost) );
	assert( item_costset_set != 0 );
	DID_SETALLOC;
	return item_costset_set;
}

static void
free_item_costset_space( item_cost * item_costset_set )
{
	SETFREE( item_costset_set );
}

static item_cost *
allocate_item_costset_array( unsigned n )
{
	unsigned i;
	item_cost * item_costset_set;

	item_costset_set = allocate_item_costset_space(n);
	for( i = 0 ; i < n ; i ++ )
		item_costset_set[i] = item_cost_none;
	return item_costset_set;
}

item_costset
item_costset::compute_item_costset(
	symbol * symp,
	register item_table * ptp, 
	item_costset * core_set_p )
{