MultiSource/Applications/Burg/trim.c

char rcsid_trim[] = "$Id$";

#include <stdio.h>
#include "b.h"
#include "fe.h"

Relation *allpairs;

int trimflag = 0;
int debugTrim = 0;

static void siblings ARGS((int, int));
static void findAllNexts ARGS((void));
static Relation *newAllPairs ARGS((void));

static void
siblings(i, j) int i; int j;
{
	int k;
	List pl;
	DeltaCost Max;
	int foundmax;

	allpairs[i][j].sibComputed = 1;

	if (i == 1) {
		return; /* never trim start symbol */
	}
	if (i==j) {
		return;
	}

	ZEROCOST(Max);
	foundmax = 0;

	for (k = 1; k < max_nonterminal; k++) {
		DeltaCost tmp;

		if (k==i || k==j) {
			continue;
		}
		if (!allpairs[k][i].rule) {
			continue;
		}
		if (!allpairs[k][j].rule) {
			return;
		}
		ASSIGNCOST(tmp, allpairs[k][j].chain);
		MINUSCOST(tmp, allpairs[k][i].chain);
		if (foundmax) {
			if (LESSCOST(Max, tmp)) {
				ASSIGNCOST(Max, tmp);
			}
		} else {
			foundmax = 1;
			ASSIGNCOST(Max, tmp);
		}
	}

	for (pl = rules; pl; pl = pl->next) {
		Rule p = (Rule) pl->x;
		Operator op = p->pat->op;
		List oprule;
		DeltaCost Min;
		int foundmin;
		
		if (!op) {
			continue;
		}
		switch (op->arity) {
		case 0:
			continue;
		case 1:
			if (!allpairs[p->pat->children[0]->num ][ i].rule) {
				continue;
			}
			foundmin = 0;
			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
				Rule s = (Rule) oprule->x;
				DeltaPtr Cx;
				DeltaPtr Csj;
				DeltaPtr Cpi;
				DeltaCost tmp;

				if (!allpairs[p->lhs->num ][ s->lhs->num].rule
				 || !allpairs[s->pat->children[0]->num ][ j].rule) {
					continue;
				}
				Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
				Csj= allpairs[s->pat->children[0]->num ][ j].chain;
				Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
				ASSIGNCOST(tmp, Cx);
				ADDCOST(tmp, s->delta);
				ADDCOST(tmp, Csj);
				MINUSCOST(tmp, Cpi);
				MINUSCOST(tmp, p->delta);
				if (foundmin) {
					if (LESSCOST(tmp, Min)) {
						ASSIGNCOST(Min, tmp);
					}
				} else {
					foundmin = 1;
					ASSIGNCOST(Min, tmp);
				}
			}
			if (!foundmin) {
				return;
			}
			if (foundmax) {
				if (LESSCOST(Max, Min)) {
					ASSIGNCOST(Max, Min);
				}
			} else {
				foundmax = 1;
				ASSIGNCOST(Max, Min);
			}
			break;
		case 2:
		/* do first dimension */
		if (allpairs[p->pat->children[0]->num ][ i].rule) {
			foundmin = 0;
			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
				Rule s = (Rule) oprule->x;
				DeltaPtr Cx;
				DeltaPtr Cb;
				DeltaPtr Csj;
				DeltaPtr Cpi;
				DeltaCost tmp;

				if (allpairs[p->lhs->num ][ s->lhs->num].rule
				 && allpairs[s->pat->children[0]->num ][ j].rule
				 && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
					Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
					Csj= allpairs[s->pat->children[0]->num ][ j].chain;
					Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
					Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
					ASSIGNCOST(tmp, Cx);
					ADDCOST(tmp, s->delta);
					ADDCOST(tmp, Csj);
					ADDCOST(tmp, Cb);
					MINUSCOST(tmp, Cpi);
					MINUSCOST(tmp, p->delta);
					if (foundmin) {
						if (LESSCOST(tmp, Min)) {
							ASSIGNCOST(Min, tmp);
						}
					} else {
						foundmin = 1;
						ASSIGNCOST(Min, tmp);
					}
				}
			}
			if (!foundmin) {
				return;
			}
			if (foundmax) {
				if (LESSCOST(Max, Min)) {
					ASSIGNCOST(Max, Min);
				}
			} else {
				foundmax = 1;
				ASSIGNCOST(Max, Min);
			}
		}
		/* do second dimension */
		if (allpairs[p->pat->children[1]->num ][ i].rule) {
			foundmin = 0;
			for (oprule = op->table->rules; oprule; oprule = oprule->next) {
				Rule s = (Rule) oprule->x;
				DeltaPtr Cx;
				DeltaPtr Cb;
				DeltaPtr Csj;
				DeltaPtr Cpi;
				DeltaCost tmp;

				if (allpairs[p->lhs->num ][ s->lhs->num].rule
				 && allpairs[s->pat->children[1]->num ][ j].rule
				 && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
					Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
					Csj= allpairs[s->pat->children[1]->num ][ j].chain;
					Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
					Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
					ASSIGNCOST(tmp, Cx);
					ADDCOST(tmp, s->delta);
					ADDCOST(tmp, Csj);
					ADDCOST(tmp, Cb);
					MINUSCOST(tmp, Cpi);
					MINUSCOST(tmp, p->delta);
					if (foundmin) {
						if (LESSCOST(tmp, Min)) {
							ASSIGNCOST(Min, tmp);
						}
					} else {
						foundmin = 1;
						ASSIGNCOST(Min, tmp);
					}
				}
			}
			if (!foundmin) {
				return;
			}
			if (foundmax) {
				if (LESSCOST(Max, Min)) {
					ASSIGNCOST(Max, Min);
				}
			} else {
				foundmax = 1;
				ASSIGNCOST(Max, Min);
			}
		}
		break;
		default:
			assert(0);
		}
	}
	allpairs[i ][ j].sibFlag = foundmax;
	ASSIGNCOST(allpairs[i ][ j].sibling, Max);
}

static void
findAllNexts()
{
	int i,j;
	int last;

	for (i = 1; i < max_nonterminal; i++) {
		last = 0;
		for (j = 1; j < max_nonterminal; j++) {
			if (allpairs[i ][j].rule) {
				allpairs[i ][ last].nextchain = j;
				last = j;
			}
		}
	}
	/*
	for (i = 1; i < max_nonterminal; i++) {
		last = 0;
		for (j = 1; j < max_nonterminal; j++) {
			if (allpairs[i ][j].sibFlag) {
				allpairs[i ][ last].nextsibling = j;
				last = j;
			}
		}
	}
	*/
}

static Relation *
newAllPairs()
{
	int i;
	Relation *rv;

	rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
	for (i = 0; i < max_nonterminal; i++) {
		rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
	}
	return rv;
}

void
findAllPairs()
{
	List pl;
	int changes;
	int j;

	allpairs = newAllPairs();
	for (pl = chainrules; pl; pl = pl->next) {
		Rule p = (Rule) pl->x;
		NonTerminalNum rhs = p->pat->children[0]->num;
		NonTerminalNum lhs = p->lhs->num;
		Relation r = &allpairs[lhs ][ rhs];

		if (LESSCOST(p->delta, r->chain)) {
			ASSIGNCOST(r->chain, p->delta);
			r->rule = p;
		}
	}
	for (j = 1; j < max_nonterminal; j++) {
		Relation r = &allpairs[j ][ j];
		ZEROCOST(r->chain);
		r->rule = &stub_rule;
	}
	changes = 1;
	while (changes) {
		changes = 0;
		for (pl = chainrules; pl; pl = pl->next) {
			Rule p = (Rule) pl->x;
			NonTerminalNum rhs = p->pat->children[0]->num;
			NonTerminalNum lhs = p->lhs->num;
			int i;

			for (i = 1; i < max_nonterminal; i++) {
				Relation r = &allpairs[rhs ][ i];
				Relation s = &allpairs[lhs ][ i];
				DeltaCost dc;
				if (!r->rule) {
					continue;
				}
				ASSIGNCOST(dc, p->delta);
				ADDCOST(dc, r->chain);
				if (!s->rule || LESSCOST(dc, s->chain)) {
					s->rule = p;
					ASSIGNCOST(s->chain, dc);
					changes = 1;
				}
			}
		}
	}
	findAllNexts();
}

void
trim(t) Item_Set t;
{
	int m,n;
	static short *vec = 0;
	int last;

	assert(!t->closed);
	debug(debugTrim, printf("Begin Trim\n"));
	debug(debugTrim, dumpItem_Set(t));

	last = 0;
	if (!vec) {
		vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
	}
	for (m = 1; m < max_nonterminal; m++) {
		if (t->virgin[m].rule) {
			vec[last++] = m;
		}
	}
	for (m = 0; m < last; m++) {
		DeltaCost tmp;
		int j;
		int i;

		i = vec[m];

		for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {

			if (i == j) {
				continue;
			}
			if (!t->virgin[j].rule) {
				continue;
			}
			ASSIGNCOST(tmp, t->virgin[j].delta);
			ADDCOST(tmp, allpairs[i ][ j].chain);
			if (!LESSCOST(t->virgin[i].delta, tmp)) {
				t->virgin[i].rule = 0;
				ZEROCOST(t->virgin[i].delta);
				debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
				goto outer;
			}
			
		}
		if (!trimflag) {
			continue;
		}
		for (n = 0; n < last; n++) {
			j = vec[n];
			if (i == j) {
				continue;
			}

			if (!t->virgin[j].rule) {
				continue;
			}

			if (!allpairs[i][j].sibComputed) {
				siblings(i,j);
			}
			if (!allpairs[i][j].sibFlag) {
				continue;
			}
			ASSIGNCOST(tmp, t->virgin[j].delta);
			ADDCOST(tmp, allpairs[i ][ j].sibling);
			if (!LESSCOST(t->virgin[i].delta, tmp)) {
				t->virgin[i].rule = 0;
				ZEROCOST(t->virgin[i].delta);
				goto outer;
			}
		}

		outer: ;
	}

	debug(debugTrim, dumpItem_Set(t));
	debug(debugTrim, printf("End Trim\n"));
}

void
dumpRelation(r) Relation r;
{
	printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
}

void
dumpAllPairs()
{
	int i,j;

	printf("Dumping AllPairs\n");
	for (i = 1; i < max_nonterminal; i++) {
		for (j = 1; j < max_nonterminal; j++) {
			dumpRelation(&allpairs[i ][j]);
		}
		printf("\n");
	}
}