/*
    mmorph, MULTEXT morphology tool
    Version 2.3, October 1995
    Copyright (c) 1994,1995 ISSCO/SUISSETRA, Geneva, Switzerland
    Dominique Petitpierre, <petitp@divsun.unige.ch>
*/
/*
    unify.c

    handle unification of typed feature structures and rule applications

    Dominique Petitpierre, ISSCO Summer 1994
*/

#include "user.h"

static s_bitmap *rule_map;
int         goal_card;
t_index     largest_type;

t_letter    concatenation[CONCAT_SIZE];

t_boolean
match_tfs(rule_tfs, lex_tfs)
s_tfs      *rule_tfs;
s_tfs      *lex_tfs;

{

    if (rule_tfs->type != lex_tfs->type)
	return (FALSE);
    else {
	register t_value *r;
	register t_value *l;

	r = rule_tfs->att_list;
	l = lex_tfs->att_list;
	while (*r & *l) {
	    r++;
	    l++;
	}
	return (*r == NO_BITS);	/* sentinel */
    }
}

t_boolean
subsume_tfs(subsuming_tfs, subsumed_tfs)
s_tfs      *subsuming_tfs;
s_tfs      *subsumed_tfs;

{

    if (subsuming_tfs->type != subsumed_tfs->type)
	return (FALSE);
    else {
	register t_value *a;
	register t_value *b;

	a = subsuming_tfs->att_list;
	b = subsumed_tfs->att_list;
	while (*a && ((*a & *b) == *b)) {	/* a includes b */
	    a++;
	    b++;
	}
	return (*a == NO_BITS);	/* sentinel */
    }
}

static s_tfs *
make_tfs(lhs, rule_tfs, lex_tfs)
s_tfs      *lhs;
s_tfs      *rule_tfs;
s_tfs      *lex_tfs;

{
    s_tfs      *tfs;

    tfs = new_tfs(lhs->type);
    {
	register t_value *val;
	register t_value *val_lhs;

	val = tfs->att_list;
	val_lhs = lhs->att_list;
	do {
	    *val++ = *val_lhs++;
	} while (*val_lhs != NO_BITS);
    }
    tfs->var_map = lhs->var_map;	/* copy map for percolation time */
    if (lhs->var_map != NULL) {

	register s_var_map **v;

	for (v = lhs->var_map; *v != NULL; v++)
	    tfs->att_list[(*v)->local_index] =
		rule_tfs->att_list[(*v)->foreign_index]
		& lex_tfs->att_list[(*v)->foreign_index];
    }
    return (tfs);
}

static      t_boolean
apply_rule(result, rule, lex_rule)
s_rule_instance *result;
s_rule_instance *rule;
s_rule_instance *lex_rule;

{
    if (match_tfs(rule->first, lex_rule->lhs)) {
	result->lhs =
	    make_tfs(rule->lhs, rule->first, lex_rule->lhs);
	/* fill in historical information */
	result->first = rule->first;
	result->second = rule->second;
	result->rule_kind = rule->rule_kind;
	result->branch = lex_rule;
/*
	result->rule_link=rule->rule_link;
*/
	result->base_lex = lex_rule->base_lex;	/* just percolate upwards */
	switch (rule->rule_kind) {
	    case Goal:
		if ((lex_rule->lex - 1) < concatenation)
		    /* TODO: print actual string */
		    fatal_error("prefix size limit (%d characters) %s",
				PREFIX_CONCAT_SIZE,
				"reached when prepending word boundary");
		result->lex = lex_rule->lex - 1;
		*result->lex = *word_boundary;
		result->lex_length = lex_rule->lex_length + 2;
		if (result->lex_length + (lex_rule->lex - concatenation)
		    >= (t_card) CONCAT_SIZE)
		    /* TODO: print string */
		    fatal_error("suffix size limit (%d characters) %s",
				SUFFIX_CONCAT_SIZE,
				"reached when appending word boundary");
		result->lex[result->lex_length - 1] = *word_boundary;
		result->lex[result->lex_length] = NUL_LETTER;
		break;
	    case Unary:
		result->lex = lex_rule->lex;
		result->lex_length = lex_rule->lex_length;
		break;
	    case Prefix:
		if ((result->lex = lex_rule->lex - rule->lex_length - 1)
		    < concatenation)
		    /* TODO: print actual string */
		    fatal_error("prefix size limit (%d characters) %s",
				PREFIX_CONCAT_SIZE,
				"reached when prepending prefix string");
		else {
		    (void) strncpy((char *) result->lex, (char *) rule->lex,
				   rule->lex_length);
		    result->lex[rule->lex_length] = *morpheme_boundary;
		    result->lex_length = lex_rule->lex_length
			+ rule->lex_length + 1;
		}
		break;
	    case Suffix:
		result->lex_length = lex_rule->lex_length + rule->lex_length
		    + 1;
		if (result->lex_length + (lex_rule->lex - concatenation)
		    >= (t_card) CONCAT_SIZE)
		    /* TODO: print string */
		    fatal_error("suffix size limit (%d characters) %s",
				SUFFIX_CONCAT_SIZE,
				"reached when appending suffix string");
		else {
		    (void) strncpy((char *) lex_rule->lex
				   + lex_rule->lex_length + 1,
				   (char *) rule->lex, rule->lex_length);
		    lex_rule->lex[lex_rule->lex_length] = *morpheme_boundary;
		    result->lex = lex_rule->lex;
		    result->lex[result->lex_length] = NUL_LETTER;
		}
		break;
	    default:
		break;
	}
	return (TRUE);
    }
    else
	return (FALSE);
}


static void
print_lexical(lex_rule)
s_rule_instance *lex_rule;

{
    print_log("\"");
    print_string_l(logfile, lex_rule->lex, (int) lex_rule->lex_length);
    print_log("\" = \"");
    print_string(logfile, lex_rule->base_lex);
    print_log("\" ");
    print_tfs(lex_rule->lhs);
}

static void
indent(indent_level)
int         indent_level;

{
    int         i;

    for (i = 0; i < indent_level; i++)
	print_log("  ");
}

static s_tfs *
duplicate_tfs(master_tfs)
s_tfs      *master_tfs;	/* master for the result */

{
    s_tfs      *result_tfs;	/* result to build */
    t_value    *val_result;
    t_value    *val;

    /* copy master template */
    result_tfs = new_tfs(master_tfs->type);
    val_result = result_tfs->att_list;
    val = master_tfs->att_list;
    while ((*val_result++ = *val++) != NO_BITS) {
    }
    result_tfs->var_map = master_tfs->var_map;
    return (result_tfs);
}

static void
percolate_foreign(result_tfs, source_tfs)
s_tfs      *result_tfs;	/* result to build, allready allocated */
s_tfs      *source_tfs;	/* where to take the new values from */

{
    t_value    *val_result;
    t_value    *val;
    s_var_map **v;

    /* percolate down according to variable map of source */
    if ((v = source_tfs->var_map) != NULL) {
	val_result = result_tfs->att_list;
	val = source_tfs->att_list;
	for (; *v != NULL; v++)
	    val_result[(*v)->foreign_index] = val[(*v)->local_index];
    }
}
static void
percolate_local(result_tfs, source_tfs)
s_tfs      *result_tfs;	/* result to build, allready allocated */
s_tfs      *source_tfs;	/* where to take the new values from */

{
    t_value    *val_result;
    t_value    *val;
    s_var_map **v;

    /* percolate down according to variable map of result */
    if ((v = result_tfs->var_map) != NULL) {
	val_result = result_tfs->att_list;
	val = source_tfs->att_list;
	for (; *v != NULL; v++)
	    val_result[(*v)->local_index] = val[(*v)->foreign_index];
    }
}

/* according to the position of concatenation, find the tfs of the affix */
s_tfs      *
get_tfs(lex_rule, concat_point, has_concat_point, stem_length)
s_rule_instance *lex_rule;
t_letter   *concat_point;
t_boolean   has_concat_point;
t_card      stem_length;

{

#define LEFT_SIDE	-1
#define NO_SIDE		 0
#define RIGHT_SIDE	 1

    s_rule_instance *node;	/* current tree node when traversing down */
    s_rule_instance *daughter;	/* daughter of node */
    t_boolean   has_adjacent_right;
    t_boolean   has_adjacent_left;
    int         closest_side;	/* which side was last seen: *_SIDE */
    s_tfs      *adjacent_right;	/* last prefix seen */
    s_tfs      *adjacent_left;	/* last suffix seen */

    node = lex_rule;
    daughter = node->branch;
    if (has_concat_point) {
	/* find which affix caused the concatenation point */
	while (daughter != NULL) {
	    if ((node->rule_kind == Suffix
		 && concat_point == (daughter->lex + daughter->lex_length
				     + stem_length))
		|| (node->rule_kind == Prefix
		    && concat_point == (daughter->lex - 1))) {
		return (node->second);	/* tfs of affix */
	    }
	    node = daughter;
	    daughter = node->branch;
	}
	/* now reached the bottom of the tree: lexical leaf */
	fatal_error("program bug: no matching concatenation point found");
    }
    else {	/* find within which affix the focus starts */
	closest_side = NO_SIDE;
	has_adjacent_right = FALSE;
	has_adjacent_left = FALSE;
	while (daughter != NULL) {
	    if (node->rule_kind == Suffix) {
		if (concat_point >= (daughter->lex + daughter->lex_length
				     + stem_length))
		    if (has_adjacent_right)
			/* tfs after the suffix */
			return (adjacent_right);
		    else
			return (node->second);
		else {
		    adjacent_right = node->second;
		    closest_side = RIGHT_SIDE;
		    has_adjacent_right = TRUE;
		}
	    }
	    else if (node->rule_kind == Prefix) {
		if (concat_point < daughter->lex)
		    if (has_adjacent_left)
			return (adjacent_left);	/* tfs before the prefix */
		    else
			return (node->second);
		else {
		    adjacent_left = node->second;
		    closest_side = LEFT_SIDE;
		    has_adjacent_left = TRUE;
		}
	    }
	    /* move down the tree */
	    node = daughter;
	    daughter = node->branch;
	}
	/* now reached the bottom of the tree: lexical leaf */
	if (closest_side == RIGHT_SIDE)
	    return (adjacent_right);
	else if (closest_side == LEFT_SIDE)
	    return (adjacent_left);
	else {	/* closest_side== NO_SIDE : no affix was concateneted */
	    return (node->lhs);	/* lexical's tfs */
	}
    }
    fatal_error("program bug: no affix found in get_tfs");
    /* NOTREACHED */
    return (NULL);	/* shut up gcc -Wall */
}

/*
    duplicate a whole affix tree, while percolating down the variable
    values (which cannot be done in apply_rule).
*/
static s_rule_instance *
copy_affix_tree(master_tree, parent_first)
s_rule_instance *master_tree;
s_tfs      *parent_first;

{
    s_rule_instance *result_tree;
    s_tfs      *first;

    MY_MALLOC(result_tree, s_rule_instance);
    result_tree->rule_kind = master_tree->rule_kind;
    result_tree->rule_link = master_tree->rule_link;
    result_tree->lex_length = master_tree->lex_length;
    result_tree->lex = master_tree->lex;
    /* identify the lhs to the first of the parent */
    result_tree->lhs = duplicate_tfs(parent_first);
    /* restore the correct var_map incorrectly set in duplicate_tfs */
    result_tree->lhs->var_map = master_tree->lhs->var_map;
    if (master_tree->branch == NULL) {
	/* reached lexical leaf */
	result_tree->branch = NULL;
	result_tree->first = NULL;
	result_tree->second = NULL;
    }
    else {
	first = duplicate_tfs(master_tree->first);
	result_tree->first = first;
	percolate_foreign(first, result_tree->lhs);
	if (master_tree->second == NULL)
	    /* goal, unary or lexical rule */
	    result_tree->second = NULL;
	else {
	    /* (combined) prefix or suffix rule */
	    result_tree->second = duplicate_tfs(master_tree->second);
	    percolate_foreign(result_tree->second, first);
	    percolate_local(result_tree->second, result_tree->lhs);
	}
	result_tree->branch = copy_affix_tree(master_tree->branch, first);
    }
    return (result_tree);
}

static s_affix_tree *
new_affix_tree(master_tree)
s_rule_instance *master_tree;

{
    s_affix_tree *affix_tree;

    MY_MALLOC(affix_tree, s_affix_tree);
    /* TODO no need to copy the top node: top->lhs == top->first */
    affix_tree->tree = copy_affix_tree(master_tree, master_tree->lhs);
    affix_tree->prefix_length =
	concatenation + PREFIX_CONCAT_SIZE - master_tree->lex;
    affix_tree->suffix_length =
	master_tree->lex_length - affix_tree->prefix_length;
    MY_STRDUP(affix_tree->lex, master_tree->lex);
    affix_tree->tfs_index = -1;
    return (affix_tree);
}

/* global parameter to generate, set in build_affix_trees */
static s_chain *affix_tree_chain;

/*
  create all possible structures according to the tfs in lex_rule
  and collect them in a chain of word trees
*/
static void
generate(lex_rule, rule_map, level)
s_rule_instance *lex_rule;
s_bitmap   *rule_map;
int         level;

{
    s_rule_instance **rule_ref;
    long        rule_index;
    s_rule_instance *rule;
    s_affix_tree *affix_tree;
    s_rule_instance result;
    t_boolean   applied;

    /* try to apply all rules of rule_map to the lexical */
    rule_ref = rule_instance_ref;
    FOR_EACH_BIT(rule_map, rule_index) {
	rule = rule_ref[rule_index];
	applied = apply_rule(&result, rule, lex_rule);
	if (trace_level >= TRACE_FAIL
	    || (trace_level >= TRACE_RULE && applied)) {
	    indent(level);
	    print_log("%s\n", rule_ref[rule_index]->rule_link->name);
	}
	if (applied) {
	    if (rule->rule_kind == Goal) {
		if (trace_level >= TRACE_GOAL)
		    print_lexical(&result);
		affix_tree = new_affix_tree(&result);
		affix_tree_chain =
		    insert_chain_link(affix_tree_chain, (t_ptr) affix_tree);
	    }
	    else {
		unset_bit(rule_map, rule_index);	/* dont apply again */
		generate(&result, rule_map, level + 1);
		set_bit(rule_map, rule_index);	/* restore before returning */
	    }
	    free_tfs(result.lhs);
	}
    }
}

static s_bitmap *
init_rule_map()
{
    s_bitmap   *rule_map;
    s_rule_instance **first_ref;
    s_rule_instance **rule_ref;

    rule_map = new_bitmap((long) rule_instance_card);
    first_ref = rule_instance_ref;
    for (rule_ref = first_ref; *rule_ref != NULL; rule_ref++)
	switch ((*rule_ref)->rule_kind) {
	    case Goal:
		/* FALLTHROUGH */
	    case Prefix:
		/* FALLTHROUGH */
	    case Suffix:
		/* FALLTHROUGH */
	    case Unary:
		set_bit(rule_map, (long) (rule_ref - first_ref));
		break;
	    default:
		break;
	}
    return (rule_map);
}

void
prepare_rules()
{
    e_rule_kind rule_kind;

    if (goal_card == 0)
	print_warning("no goal rules. No rule application will succeed");
    for (rule_kind = 0; rule_kind < _last_rule_kind; rule_kind++)
	rule_maps[rule_kind] = new_bitmap((long) symbol_set[Rule].card);
    fill_rule_maps(symbol_set[Rule].ref);
    /* prepare unary rules */
    combine_all(rule_maps[Binary], rule_maps[Lexical],
		symbol_set[Rule].ref);
    for (rule_kind = 0; rule_kind < _last_rule_kind; rule_kind++)
	MY_FREE(rule_maps[rule_kind]);
    rule_map = init_rule_map();
}

static void
free_affix_tree1(tree)
s_rule_instance *tree;

{
    if (tree->branch != NULL)
	free_affix_tree1(tree->branch);
    free_tfs(tree->lhs);
    free_tfs(tree->first);
    free_tfs(tree->second);
    MY_FREE(tree);
}

void
free_affix_tree(affix_tree)
s_affix_tree *affix_tree;

{
    free_affix_tree1(affix_tree->tree);
    MY_FREE(affix_tree->lex);
    MY_FREE(affix_tree);
}

s_chain    *
build_affix_trees(tfs)
s_tfs      *tfs;

{
    static t_boolean initialize = TRUE;
    static s_rule_instance lexical_rule;

    if (initialize) {
	lexical_rule.rule_kind = Lexical;
	lexical_rule.rule_link = NULL;	/* TODO: check non existant */
	lexical_rule.branch = NULL;
	lexical_rule.lex_length = 0;
	lexical_rule.lex = concatenation + PREFIX_CONCAT_SIZE;
	lexical_rule.lex[0] = NUL_LETTER;
	lexical_rule.base_lex = empty_string;
	lexical_rule.first = NULL;
	lexical_rule.second = NULL;
	initialize = FALSE;
    }
    lexical_rule.lhs = tfs;
    if (trace_level > TRACE_GOAL) {
	print_log("\ngenerating from\n");
	print_lexical(&lexical_rule);
    }
    affix_tree_chain = NULL;	/* global parameter to generate */
    generate(&lexical_rule, rule_map, 0);
    return (affix_tree_chain);
}


/* global parameter to generate_surface1 */

static t_card stem_length;
static t_letter *base_form;

static void
generate_surface1(affix_tree)
s_affix_tree *affix_tree;

{
    (void) strncpy((char *) affix_tree->tree->lex, (char *) affix_tree->lex,
		   affix_tree->prefix_length);
    (void) strcpy((char *) concatenation + PREFIX_CONCAT_SIZE + stem_length,
		  (char *) affix_tree->lex + affix_tree->prefix_length);
    if (trace_level > TRACE_GOAL) {
	print_log("\ngenerating surface from \"");
	print_string(logfile, affix_tree->tree->lex);
	print_log("\"\n");
    }
    fill_applicability_map(affix_tree->tree, stem_length);
    do_spell(affix_tree->tree->lex, base_form, affix_tree->tree->lhs,
	     &affix_tree->tfs_index);
}

void
generate_surface(lex, base_lex, affix_tree_chain)
t_letter   *lex;
t_letter   *base_lex;
s_chain    *affix_tree_chain;

{

    stem_length = strlen((char *) lex);
    (void) strcpy((char *) (concatenation + PREFIX_CONCAT_SIZE), (char *) lex);
    base_form = base_lex;	/* global parameter to generate_surface1 */
    map_chain(affix_tree_chain, generate_surface1);
}