Subversion Repositories tendra.SVN

/*

 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 * 3. Neither the name of The TenDRA Project nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific, prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS

 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,

 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;

 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,

 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR

 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * $Id$

 */

/*

    		 Crown Copyright (c) 1997

    This TenDRA(r) Computer Program is subject to Copyright

    owned by the United Kingdom Secretary of State for Defence

    acting through the Defence Evaluation and Research Agency

    (DERA).  It is made available to Recipients with a

    royalty-free licence for its use, reproduction, transfer

    to other parties and amendment for any purpose not excluding

    product development provided that any such use et cetera

    shall be deemed to be acceptance of the following conditions:-

        (1) Its Recipients shall ensure that this Notice is

        reproduced upon any copies or amended versions of it;

        (2) Any amended version of it shall be clearly marked to

        show both the nature of and the organisation responsible

        for the relevant amendment or amendments;

        (3) Its onward transfer from a recipient to another

        party shall be deemed to be that party's acceptance of

        these conditions;

        (4) DERA gives no warranty or assurance as to its

        quality or suitability for any purpose and DERA accepts

        no liability whatsoever in relation to any use to which

        it may be put.

*/

/*** rule-lre.c --- Left recursion elimination routines.

 *

 ** Author: Steve Folkes <smf@hermes.mod.uk>

 *

 *** Commentary:

 *

 * This file implements the SID left recursion elimination routines.

 *

 * The generic cycle detection functions defined in the file ``rule.c'' are

 * used to find left cycles in the grammar (this is done by the function

 * ``grammar_remove_left_recursion'' in the file "grammar.c").  If the

 * functions find any such cycles, the function ``rule_remove_left_cycle'' is

 * called on the group of productions to remove the left recursion.  Left

 * recursion is transformed into right recursion in the manner described

 * below.

 *

 * Given a set of productions, expressed as

 *

 *	Ai = Aj Bji, Ci;

 *

 * this can be transformed into

 *

 *	Ai  = Cj Xji;

 *	Xij = Yij, Bik Xkj;

 *

 * Where the rules "Xij" are generated automatically, and Yij is the identity

 * operation if i = j, or an error otherwise.  The generated rule has the same

 * parameters and results, which are the results of "Ai" augmented with those

 * parameters of "Ai" that are used by "Bji".

 *

 * In order for the transform to work, all of the "Ai" must have the same

 * parameter and result types, and the same exception handler.  Also, the

 * initial call to "Aj" must take exactly the formals of "Ai" as parameters.

 * This is checked by the ``rule_check_cycle_types'' function, which also

 * ensures that names are consistent throughout all of the rules.  The

 * transform is performed by the function ``rule_left_cycle_general_case''.

 *

 * In addition to the general case, two special cases are looked for.  The

 * first of these transforms:

 *

 *	A = A B, $;

 *

 * into

 *

 *	A = B A, $;

 *

 * whilst the second transforms:

 *

 *	A = A C B, B;

 *

 * into

 *

 *	A = B X;

 *	X = C A;

 *

 * These special cases are handled by the ``rule_left_cycle_special_case''

 * function.

 *

 *** Change Log:

 * $Log: rule-lre.c,v $

 * Revision 1.1.1.1  1998/01/17  15:57:47  release

 * First version to be checked into rolling release.

 *

 * Revision 1.3  1995/02/10  16:29:42  smf

 * Fixed bugs "CR95_111.sid-inline-no-var-check" and "CR95_112.sid-lre-var-call".

 *

 * Revision 1.2  1994/12/15  09:58:41  smf

 * Brought into line with OSSG C Coding Standards Document, as per

 * "CR94_178.sid+tld-update".

 *

 * Revision 1.1.1.1  1994/07/25  16:04:39  smf

 * Initial import of SID 1.8 non shared files.

 *

**/

/****************************************************************************/

#include "rule.h"

#include "dstring.h"

#include "gen-errors.h"

/*--------------------------------------------------------------------------*/

typedef struct MatrixEntryT {

    AltP			alt;

    BoolT			inited;

    TypeTupleT			param;

} MatrixEntryT, *MatrixEntryP;

typedef struct VectorEntryT {

    BoolT			empty_alt;

    AltP			alt;

    BoolT			inited;

    TypeTupleT			param;

} VectorEntryT, *VectorEntryP;

/*--------------------------------------------------------------------------*/

static MatrixEntryP

rule_left_cycle_matrix(unsigned size)

{

    static MatrixEntryP array      = NIL(MatrixEntryP);

    static unsigned     array_size = 0;

    unsigned            i;

    if (size > array_size) {

	DEALLOCATE(array);

	array      = ALLOCATE_VECTOR(MatrixEntryT, size);

	array_size = size;

    }

    for (i = 0; i < size; i++) {

	array[i].alt    = NIL(AltP);

	array[i].inited = FALSE;

    }

    return(array);

}

static VectorEntryP

rule_left_cycle_vector(unsigned size)

{

    static VectorEntryP array      = NIL(VectorEntryP);

    static unsigned     array_size = 0;

    unsigned            i;

    if (size > array_size) {

	DEALLOCATE(array);

	array      = ALLOCATE_VECTOR(VectorEntryT, size);

	array_size = size;

    }

    for (i = 0; i < size; i++) {

	array[i].empty_alt = FALSE;

	array[i].alt       = NIL(AltP);

	array[i].inited    = FALSE;

    }

    return(array);

}

static void

rule_destroy_cycle_matrix(MatrixEntryP matrix, unsigned size)

{

    unsigned i;

    for (i = 0; i < size; i++) {

	if (matrix[i].inited) {

	    AltP alt = matrix[i].alt;

	    while (alt) {

		alt = alt_deallocate(alt);

	    }

	    types_destroy(&(matrix[i].param));

	}

    }

}

static void

rule_destroy_cycle_vector(VectorEntryP vector, unsigned size)

{

    unsigned i;

    for (i = 0; i < size; i++) {

	if (vector[i].inited) {

	    AltP alt = vector[i].alt;

	    while (alt) {

		alt = alt_deallocate(alt);

	    }

	    types_destroy(&(vector[i].param));

	}

    }

}

/*--------------------------------------------------------------------------*/

static ItemP

rule_find_suffix(ItemP rec_item, ItemP non_rec_item)

{

    ItemP    tmp_rec_item     = rec_item;

    ItemP    tmp_non_rec_item = non_rec_item;

    unsigned diff             = 0;

    while (tmp_rec_item && tmp_non_rec_item) {

	tmp_rec_item     = item_next(tmp_rec_item);

	tmp_non_rec_item = item_next(tmp_non_rec_item);

    }

    while (tmp_rec_item) {

	diff++;

	tmp_rec_item = item_next(tmp_rec_item);

    }

    if (diff == 0) {

	return(NIL(ItemP));

    }

    do {

	rec_item = item_next(rec_item);

    } while (--diff);

    tmp_rec_item     = rec_item;

    tmp_non_rec_item = non_rec_item;

    while (tmp_rec_item && tmp_non_rec_item) {

	if (item_entry(tmp_rec_item) != item_entry(tmp_non_rec_item)) {

	    return(NIL(ItemP));

	}

	tmp_rec_item     = item_next(tmp_rec_item);

	tmp_non_rec_item = item_next(tmp_non_rec_item);

    }

    ASSERT((tmp_rec_item == NIL(ItemP)) && (tmp_non_rec_item == NIL(ItemP)));

    return(rec_item);

}

static void

rule_renumber_item_list(ItemP item, TypeNTransP translator)

{

    ntrans_init(translator);

    for (; item; item = item_next(item)) {

	types_renumber(item_param(item), translator);

	types_renumber(item_result(item), translator);

    }

}

static BoolT

rule_compare_item_lists(ItemP rec_suffix, ItemP non_rec_item)

{

    while (rec_suffix) {

	ASSERT(non_rec_item);

	if (!((types_equal_numbers(item_param(rec_suffix),

				   item_param(non_rec_item))) &&

	      (types_equal_numbers(item_result(rec_suffix),

				   item_result(non_rec_item))))) {

	    return(FALSE);

	}

	rec_suffix   = item_next(rec_suffix);

	non_rec_item = item_next(non_rec_item);

    }

    ASSERT(non_rec_item == NIL(ItemP));

    return(TRUE);

}

static void

rule_left_cycle_special_case_2(RuleP rule, TableP table, AltP non_rec_alt,

			       AltP rec_alt, TypeTupleP param, ItemP rec_suffix)

{

    EntryP      entry    = table_add_generated_rule(table, TRUE);

    RuleP       new_rule = entry_get_rule(entry);

    ItemP       new_item = item_create(entry);

    ItemP       rec_item = alt_unlink_item_head(rec_alt);

    AltP        new_alt  = alt_create();

    AltP        handler;

    ItemP       item;

    TypeBTransT tmp_trans;

    TypeTupleT  result;

    rule_reinit(rule);

    alt_set_next(non_rec_alt, NIL(AltP));

    btrans_init(&tmp_trans);

    types_copy(&result, rule_result(rule));

    btrans_generate_names(&tmp_trans, &result, table);

    types_translate(&result, &tmp_trans);

    if ((handler = rule_get_handler(rule)) != NIL(AltP)) {

	ItemP handler_items = alt_item_head(handler);

	item_translate_list(handler_items, &tmp_trans);

    }

    btrans_destroy(&tmp_trans);

    types_assign(item_param(new_item), rule_result(rule));

    types_copy(item_result(new_item), &result);

    types_copy(rule_result(rule), &result);

    alt_add_item(non_rec_alt, new_item);

    rule_add_alt(rule, non_rec_alt);

    types_copy(rule_param(new_rule), item_result(rec_item));

    types_copy(rule_result(new_rule), &result);

   (void)item_deallocate(rec_item);

    while (item = alt_item_head(rec_alt), item != rec_suffix) {

	alt_add_item(new_alt, alt_unlink_item_head(rec_alt));

    }

   (void)alt_deallocate(rec_alt);

    new_item = item_create(rule_entry(rule));

    if (param) {

	types_assign(item_param(new_item), param);

    } else {

	types_copy(item_param(new_item), rule_param(new_rule));

    }

    types_assign(item_result(new_item), &result);

    alt_add_item(new_alt, new_item);

    rule_add_alt(new_rule, new_alt);

    if (types_equal_zero_tuple(rule_param(new_rule))) {

	rule_add_empty_alt(new_rule);

    } else {

	new_alt  = alt_create();

	new_item = item_create(table_add_rename(table));

	types_copy(item_param(new_item), rule_param(new_rule));

	types_copy(item_result(new_item), rule_result(new_rule));

	alt_add_item(new_alt, new_item);

	rule_add_alt(new_rule, new_alt);

    }

}

static BoolT

rule_left_cycle_special_case_1(RuleP rule, TableP table)

{

    AltP        rec_alt = rule_alt_head(rule);

    AltP        non_rec_alt;

    ItemP       rec_item;

    ItemP       rec_next;

    ItemP       rec_suffix;

    ItemP       non_rec_item;

    TypeTupleT  param;

    TypeNTransT rec_translator;

    TypeNTransT non_rec_translator;

    if (((non_rec_alt = alt_next(rec_alt)) == NIL(AltP)) ||

	(alt_next(non_rec_alt))) {

	return(FALSE);

    }

    if ((item_is_rule(non_rec_item = alt_item_head(non_rec_alt))) &&

	(entry_get_rule(item_entry(non_rec_item)) == rule)) {

	non_rec_alt  = rec_alt;

	rec_alt      = alt_next(rec_alt);

	non_rec_item = alt_item_head(non_rec_alt);

    }

    if ((item_is_rule(non_rec_item)) &&

	(entry_get_rule(item_entry(non_rec_item)) == rule)) {

	return(FALSE);

    }

    rec_item = alt_item_head(rec_alt);

    if (!((types_equal_names(rule_param(rule), item_param(rec_item))) &&

	  (types_equal(rule_param(rule), rule_result(rule))))) {

	return(FALSE);

    }

    rec_next = item_next(rec_item);

    if (item_names_used_in_list(rec_next, rule_param(rule))) {

	return(FALSE);

    }

    if ((rec_suffix = rule_find_suffix(rec_item, non_rec_item)) ==

	NIL(ItemP)) {

	return(FALSE);

    }

    if ((rec_suffix != rec_next) &&

	(item_names_used_in_list(rec_suffix, item_result(rec_item)))) {

	return(FALSE);

    }

    rule_renumber_item_list(non_rec_item, &non_rec_translator);

    rule_renumber_item_list(rec_suffix, &rec_translator);

    if (!rule_compare_item_lists(rec_suffix, non_rec_item)) {

	ntrans_destroy(&non_rec_translator);

	ntrans_destroy(&rec_translator);

	return(FALSE);

    }

    if (rec_suffix == rec_next) {

	ntrans_destroy(&non_rec_translator);

	ntrans_destroy(&rec_translator);

	rule_left_cycle_special_case_2(rule, table, non_rec_alt, rec_alt,

				       NIL(TypeTupleP), rec_suffix);

    } else {

	types_compute_param_from_trans(&param, &non_rec_translator,

				       &rec_translator, rule_param(rule));

	ntrans_destroy(&non_rec_translator);

	ntrans_destroy(&rec_translator);

	rule_left_cycle_special_case_2(rule, table, non_rec_alt, rec_alt,

				       &param, rec_suffix);

    }

    return(TRUE);

}

static BoolT

rule_left_cycle_special_case(RuleP rule, TableP table)

{

    if (rule_has_empty_alt(rule)) {

	AltP  alt = rule_alt_head(rule);

	ItemP item;

	if ((alt == NIL(AltP)) || (alt_next(alt) != NIL(AltP))) {

	    return(FALSE);

	}

	item = alt_unlink_item_head(alt);

	alt_add_item(alt, item);

	return(TRUE);

    } else {

	return(rule_left_cycle_special_case_1(rule, table));

    }

}

/*--------------------------------------------------------------------------*/

static BoolT

rule_check_non_locals(RuleP this_rule, RuleP rule_list, unsigned real_size)

{

    NStringP scope  = rule_maximum_scope(this_rule);

    unsigned length = nstring_length(scope);

    RuleP    rule;

    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {

	KeyP key = entry_key(rule_entry(rule));

	if ((rule != this_rule) && key_is_string(key)) {

	    NStringP string = key_get_string(key);

	    if (!(nstring_is_prefix(string, scope) ||

		  (nstring_is_prefix(scope, string) &&

		   ((nstring_length(string) + 2) == length)))) {

		E_out_of_scope_non_local(this_rule, rule, rule_list);

		return(FALSE);

	    }

	}

    }

    if (non_local_list_is_empty(rule_non_locals(this_rule)) ||

	(real_size == 1)) {

	return(TRUE);

    } else {

	E_left_recursion_nl_entry(this_rule, rule_list);

	return(FALSE);

    }

}

static BoolT

rule_check_alt_cycle_types(RuleP rule, RuleP rule_list, AltP alt,

			   BoolT need_check, TypeBTransP translator1,

			   TypeBTransP translator2, TableP table,

			   BoolP generate_ref)

{

    ItemP item = alt_item_head(alt);

    item_translate_list(item, translator1);

    if (item_is_rule(item)) {

	RuleP item_rule = entry_get_rule(item_entry(item));

	if (rule_get_cycle_index(item_rule) != 0) {

	    TypeTupleT result_intersect;

	    if (need_check && (!types_equal_names(rule_param(rule),

						  item_param(item)))) {

		btrans_destroy(translator1);

		btrans_destroy(translator2);

		E_left_recursion_name_mismatch(rule_list);

		return(FALSE);

	    }

/* If a result identifier is returned by the left recursive call, it is

 * necessary to rename that return value, and use an identity afterwards to

 * rename it.

 **/

	    types_init(&result_intersect);

	    types_compute_intersection(&result_intersect, rule_result(rule),

				       item_result(item));

	    if (!types_equal_zero_tuple(&result_intersect)) {

		EntryP      new_entry = table_add_rename(table);

		ItemP       new_item  = item_create(new_entry);

		TypeBTransT tmp_trans;

		TypeTupleT  tmp_tuple;

		btrans_init(&tmp_trans);

		types_copy(&tmp_tuple, &result_intersect);

		btrans_generate_names(&tmp_trans, &tmp_tuple, table);

		types_translate(&tmp_tuple, &tmp_trans);

		types_translate(item_result(item), &tmp_trans);

		btrans_destroy(&tmp_trans);

		types_assign(item_param(new_item), &tmp_tuple);

		types_assign(item_result(new_item), &result_intersect);

		item_set_next(new_item, item_next(item));

		item_set_next(item, new_item);

	    } else {

		types_destroy(&result_intersect);

	    }

	    if (*generate_ref) {

		btrans_generate_names(translator2, item_result(item), table);

		*generate_ref = FALSE;

	    } else {

		btrans_regenerate_names(translator2, item_result(item));

	    }

	    types_translate(item_result(item), translator2);

	    item_translate_list(item_next(item), translator2);

	}

    }

    return(TRUE);

}

static BoolT

rule_check_cycle_types(RuleP rule_list, EntryP predicate_id,

		       unsigned real_size, TableP table)

{

    TypeTupleP  param    = rule_param(rule_list);

    TypeTupleP  result   = rule_result(rule_list);

    AltP        handler  = rule_get_handler(rule_list);

    BoolT       generate = TRUE;

    RuleP       rule;

    TypeBTransT translator1;

    TypeBTransT translator2;

    rule_renumber(rule_list, TRUE, predicate_id);

    if (!rule_check_non_locals(rule_list, rule_list, real_size)) {

	return(FALSE);

    }

    for (rule = rule_get_next_in_reverse_dfs(rule_list); rule;

	 rule = rule_get_next_in_reverse_dfs(rule)) {

	if (!((types_equal(param, rule_param(rule))) &&

	      (types_equal(result, rule_result(rule))))) {

	    E_left_recursion_type_mismatch(rule_list);

	    return(FALSE);

	}

	rule_renumber(rule, TRUE, predicate_id);

	if (!alt_equal(handler, rule_get_handler(rule))) {

	    E_left_rec_handler_mismatch(rule_list);

	    return(FALSE);

	}

	if (!rule_check_non_locals(rule, rule_list, real_size)) {

	    return(FALSE);

	}

    }

    btrans_init(&translator1);

    btrans_init(&translator2);

    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {

	AltP alt;

	if (rule == rule_list) {

	    btrans_generate_names(&translator1, rule_param(rule), table);

	} else {

	    btrans_regenerate_names(&translator1, rule_param(rule));

	}

	types_translate(rule_param(rule), &translator1);

	if ((alt = rule_get_handler(rule)) != NIL(AltP)) {

	   (void)rule_check_alt_cycle_types(rule, rule_list, alt, FALSE,

					    &translator1, &translator2, table,

					    &generate);

	}

	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {

	    if (!rule_check_alt_cycle_types(rule, rule_list, alt, TRUE,

					    &translator1, &translator2, table,

					    &generate)) {

		return(FALSE);

	    }

	}

    }

    btrans_destroy(&translator1);

    btrans_destroy(&translator2);

    return(TRUE);

}

static void

rule_compute_param_subset(RuleP rule_list, TypeTupleP subset)

{

    RuleP rule;

    types_init(subset);

    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {

	TypeTupleP param = rule_param(rule);

	AltP       alt;

	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {

	    ItemP item = alt_item_head(alt);

	    if (item_is_rule(item)) {

		RuleP item_rule = entry_get_rule(item_entry(item));

		if (rule_get_cycle_index(item_rule) != 0) {

		    for (item = item_next(item); item;

			 item = item_next(item)) {

			types_compute_intersection(subset, param,

						   item_param(item));

		    }

		}

	    }

	}

    }

}

static void

rule_left_cycle_general_case_1(RuleP rule_list, unsigned size,

			       MatrixEntryP matrix, VectorEntryP vector,

			       TableP table, TypeTupleP gen_param,

			       TypeTupleP gen_result)

{

    unsigned    i               = 0;

    BoolT       generate        = TRUE;

    BoolT       generate_param  = TRUE;

    BoolT       generate_result = TRUE;

    RuleP       rule;

    TypeBTransT translator;

    TypeBTransT tmp_trans;

    TypeTupleT  dummy;

    TypeTupleT  param_subset;

    btrans_init(&translator);

    rule_compute_param_subset(rule_list, &param_subset);

    btrans_init(&tmp_trans);

    types_copy(&dummy, &param_subset);

    btrans_generate_names(&tmp_trans, &dummy, table);

    types_translate(&dummy, &tmp_trans);

    btrans_destroy(&tmp_trans);

    for (rule = rule_list; rule;

	 rule = rule_get_next_in_reverse_dfs(rule), i++) {

	AltP       alt = rule_alt_head(rule);

	AltP       handler;

	TypeTupleT old_result;

	types_copy(&old_result, rule_result(rule));

	if (generate) {

	    btrans_generate_names(&translator, rule_result(rule), table);

	    generate = FALSE;

	} else {

	    btrans_regenerate_names(&translator, rule_result(rule));

	}

	types_translate(rule_result(rule), &translator);

	if ((handler = rule_get_handler(rule)) != NIL(AltP)) {

	    ItemP handler_items = alt_item_head(handler);

	    item_translate_list(handler_items, &translator);

	}

	if (rule_has_empty_alt(rule)) {

	    vector[i].empty_alt = TRUE;

	}

	while (alt) {

	    ItemP    item    = alt_item_head(alt);

	    AltP     tmp_alt = alt;

	    RuleP    item_rule;

	    unsigned item_index;

	    alt = alt_next(alt);

	    if ((item_is_rule(item)) &&

		((item_rule = entry_get_rule(item_entry(item))),

		 ((item_index = rule_get_cycle_index(item_rule)) != 0))) {

		unsigned matrix_index = (size *(item_index - 1) + i);

		if (!(matrix[matrix_index].inited)) {

		    TypeTupleP param = &(matrix[matrix_index].param);

		    types_copy(param, &param_subset);

		    types_append_copy(param, &old_result);

		    matrix[matrix_index].inited = TRUE;

		}

		if (generate_param) {

		    ItemP item_head = alt_item_head(tmp_alt);

		    types_copy(gen_param, &param_subset);

		    types_append_copy(gen_param, item_result(item_head));

		    generate_param = FALSE;

		}

		(void)item_deallocate(alt_unlink_item_head(tmp_alt));

		alt_set_next(tmp_alt, matrix[matrix_index].alt);

		matrix[matrix_index].alt = tmp_alt;

	    } else {

		if (!(vector[i].inited)) {

		    TypeTupleP param = &(vector[i].param);

		    types_copy(param, &param_subset);

		    types_append_copy(param, &old_result);

		    vector[i].inited = TRUE;

		}

		if (generate_result) {

		    types_copy(gen_result, &dummy);

		    types_append_copy(gen_result, rule_result(rule));

		    generate_result = FALSE;

		}

		alt_set_next(tmp_alt, vector[i].alt);

		vector[i].alt = tmp_alt;

	    }

	}

	rule_reinit(rule);

	types_destroy(&old_result);

    }

    types_destroy(&param_subset);

    btrans_destroy(&translator);

}

static BoolT

rule_left_cycle_general_case_2(RuleP rule_list, unsigned size,

			       VectorEntryP vector)

{

    BoolT    not_found = TRUE;

    unsigned i;

    for (i = 0; i < size; i++) {

	if ((vector[i].empty_alt) || (vector[i].alt)) {

	    not_found = FALSE;

	}

    }

    if (not_found) {

	E_cycle_no_terminator(rule_list);

	return(FALSE);

    }

    return(TRUE);

}

static void

rule_left_cycle_general_case_3(RuleP rule, unsigned size, VectorEntryP vector,

			       TableP table, RuleP *new_rule_list_tail,

			       TypeTupleP param, TypeTupleP result)

{

    unsigned j;

    for (j = 0; j < size; j++) {

	EntryP entry    = table_add_generated_rule(table, TRUE);

	RuleP  new_rule = entry_get_rule(entry);

	AltP   alt;

	types_copy(rule_param(new_rule), param);

	types_copy(rule_result(new_rule), result);

	*new_rule_list_tail = new_rule;

	new_rule_list_tail  = rule_next_in_reverse_dfs_ref(new_rule);

	if (vector[j].empty_alt) {

	    AltP  new_alt  = alt_create();

	    ItemP new_item = item_create(entry);

	    types_copy(item_param(new_item), &(vector[j].param));

	    types_copy(item_result(new_item), result);

	    alt_add_item(new_alt, new_item);

	    rule_add_alt(rule, new_alt);

	}

	for (alt = vector[j].alt; alt; alt = alt_next(alt)) {

	    AltP  new_alt  = alt_duplicate(alt);

	    ItemP new_item = item_create(entry);

	    types_copy(item_param(new_item), &(vector[j].param));

	    types_copy(item_result(new_item), result);

	    alt_add_item(new_alt, new_item);

	    rule_add_alt(rule, new_alt);

	}

    }

}

static void

rule_left_cycle_general_case_4(RuleP new_rule_list, unsigned i, unsigned size,

			       MatrixEntryP matrix, TableP table)

{

    unsigned j;

    RuleP    rule;

    for (rule = new_rule_list, j = 0; j < size;

	 rule = rule_get_next_in_reverse_dfs(rule), j++) {

	RuleP    inner_rule;

	unsigned k = 0;

	if (i == j) {

	    if (types_equal_zero_tuple(rule_param(rule))) {

		rule_add_empty_alt(rule);

	    } else {

		AltP   new_alt  = alt_create();

		EntryP entry    = table_add_rename(table);

		ItemP  new_item = item_create(entry);

		types_copy(item_param(new_item), rule_param(rule));

		types_copy(item_result(new_item), rule_result(rule));

		alt_add_item(new_alt, new_item);

		rule_add_alt(rule, new_alt);

	    }

	}

	for (inner_rule = new_rule_list; inner_rule;

	     inner_rule = rule_get_next_in_reverse_dfs(inner_rule), k++) {

	    AltP alt;

	    for (alt = matrix[k].alt; alt; alt = alt_next(alt)) {

		AltP  new_alt  = alt_duplicate(alt);

		ItemP new_item = item_create(rule_entry(inner_rule));

		types_copy(item_param(new_item), &(matrix[k].param));

		types_copy(item_result(new_item), rule_result(rule));

		alt_add_item(new_alt, new_item);

		rule_add_alt(rule, new_alt);

	    }

	}

    }

}

static void

rule_left_cycle_general_case(RuleP rule_list, unsigned size, TableP table)

{

    unsigned     matrix_size = (size * size);

    MatrixEntryP matrix      = rule_left_cycle_matrix(matrix_size);

    VectorEntryP vector      = rule_left_cycle_vector(size);

    TypeTupleT   param;

    TypeTupleT   result;

    rule_left_cycle_general_case_1(rule_list, size, matrix, vector, table,

				    &param, &result);

    if (rule_left_cycle_general_case_2(rule_list, size, vector)) {

	unsigned i = 0;

	RuleP    rule;

	for (rule = rule_list; rule;

	     rule = rule_get_next_in_reverse_dfs(rule), i++) {

	    RuleP new_rule_list;

	    rule_left_cycle_general_case_3(rule, size, vector, table,

					   &new_rule_list, &param, &result);

	    rule_left_cycle_general_case_4(new_rule_list, i, size, matrix,

					   table);

	}

    }

    types_destroy(&param);

    types_destroy(&result);

    rule_destroy_cycle_matrix(matrix, matrix_size);

    rule_destroy_cycle_vector(vector, size);

}

/*--------------------------------------------------------------------------*/

void

rule_remove_left_cycle(RuleP rule_list, EntryP predicate_id, TableP table)

{

    unsigned size      = 0;

    unsigned real_size = 0;

    RuleP    rule;

    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {

	size++;

	if (key_is_string(entry_key(rule_entry(rule)))) {

	    real_size++;

	}

	rule_set_cycle_index(rule, size);

    }

    if (((size != 1) || (!rule_left_cycle_special_case(rule_list, table))) &&

	(rule_check_cycle_types(rule_list, predicate_id, real_size, table))) {

	rule_left_cycle_general_case(rule_list, size, table);

    }