Subversion Repositories tendra.SVN

Rev

Rev 5 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 5 Rev 6
Line -... Line 1...
- 
 
 1 
/*
- 
 
 2 
 * Copyright (c) 2002-2005 The TenDRA Project <http://www.tendra.org/>.
- 
 
 3 
 * All rights reserved.
- 
 
 4 
 *
- 
 
 5 
 * Redistribution and use in source and binary forms, with or without
- 
 
 6 
 * modification, are permitted provided that the following conditions are met:
- 
 
 7 
 *
- 
 
 8 
 * 1. Redistributions of source code must retain the above copyright notice,
- 
 
 9 
 *    this list of conditions and the following disclaimer.
- 
 
 10 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
- 
 
 11 
 *    this list of conditions and the following disclaimer in the documentation
- 
 
 12 
 *    and/or other materials provided with the distribution.
- 
 
 13 
 * 3. Neither the name of The TenDRA Project nor the names of its contributors
- 
 
 14 
 *    may be used to endorse or promote products derived from this software
- 
 
 15 
 *    without specific, prior written permission.
- 
 
 16 
 *
- 
 
 17 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
- 
 
 18 
 * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- 
 
 19 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- 
 
 20 
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
- 
 
 21 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- 
 
 22 
 * EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- 
 
 23 
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
- 
 
 24 
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- 
 
 25 
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
- 
 
 26 
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- 
 
 27 
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- 
 
 28 
 *
- 
 
 29 
 * $Id$
- 
 
 30 
 */
1 
/*
 31 
/*
2 
    		 Crown Copyright (c) 1997
 32 
    		 Crown Copyright (c) 1997
3
33 
 
4 
    This TenDRA(r) Computer Program is subject to Copyright
 34 
    This TenDRA(r) Computer Program is subject to Copyright
5 
    owned by the United Kingdom Secretary of State for Defence
 35 
    owned by the United Kingdom Secretary of State for Defence
6 
    acting through the Defence Evaluation and Research Agency
 36 
    acting through the Defence Evaluation and Research Agency
7 
    (DERA).  It is made available to Recipients with a
 37 
    (DERA).  It is made available to Recipients with a
8 
    royalty-free licence for its use, reproduction, transfer
 38 
    royalty-free licence for its use, reproduction, transfer
9 
    to other parties and amendment for any purpose not excluding
 39 
    to other parties and amendment for any purpose not excluding
10 
    product development provided that any such use et cetera
 40 
    product development provided that any such use et cetera
11 
    shall be deemed to be acceptance of the following conditions:-
 41 
    shall be deemed to be acceptance of the following conditions:-
12
42 
 
13 
        (1) Its Recipients shall ensure that this Notice is
 43 
        (1) Its Recipients shall ensure that this Notice is
14 
        reproduced upon any copies or amended versions of it;
 44 
        reproduced upon any copies or amended versions of it;
15
45 
 
16 
        (2) Any amended version of it shall be clearly marked to
 46 
        (2) Any amended version of it shall be clearly marked to
17 
        show both the nature of and the organisation responsible
 47 
        show both the nature of and the organisation responsible
18 
        for the relevant amendment or amendments;
 48 
        for the relevant amendment or amendments;
19
49 
 
20 
        (3) Its onward transfer from a recipient to another
 50 
        (3) Its onward transfer from a recipient to another
21 
        party shall be deemed to be that party's acceptance of
 51 
        party shall be deemed to be that party's acceptance of
22 
        these conditions;
 52 
        these conditions;
23
53 
 
24 
        (4) DERA gives no warranty or assurance as to its
 54 
        (4) DERA gives no warranty or assurance as to its
25 
        quality or suitability for any purpose and DERA accepts
 55 
        quality or suitability for any purpose and DERA accepts
26 
        no liability whatsoever in relation to any use to which
 56 
        no liability whatsoever in relation to any use to which
27 
        it may be put.
 57 
        it may be put.
28 
*/
 58 
*/
Line 125... Line 155...
125 
} VectorEntryT, *VectorEntryP;
 155 
} VectorEntryT, *VectorEntryP;
126 
 
 156 
 
127 
/*--------------------------------------------------------------------------*/
 157 
/*--------------------------------------------------------------------------*/
128 
 
 158 
 
129 
static MatrixEntryP
 159 
static MatrixEntryP
130 
rule_left_cycle_matrix PROTO_N ((size))
 160 
rule_left_cycle_matrix(unsigned size)
131 
		       PROTO_T (unsigned size)
 - 
 
132 
{
 161 
{
133 
    static MatrixEntryP array      = NIL (MatrixEntryP);
 162 
    static MatrixEntryP array      = NIL(MatrixEntryP);
134 
    static unsigned     array_size = 0;
 163 
    static unsigned     array_size = 0;
135 
    unsigned            i;
 164 
    unsigned            i;
136 
 
 165 
 
137 
    if (size > array_size) {
 166 
    if (size > array_size) {
138 
	DEALLOCATE (array);
 167 
	DEALLOCATE(array);
139 
	array      = ALLOCATE_VECTOR (MatrixEntryT, size);
 168 
	array      = ALLOCATE_VECTOR(MatrixEntryT, size);
140 
	array_size = size;
 169 
	array_size = size;
141 
    }
 170 
    }
142 
    for (i = 0; i < size; i ++) {
 171 
    for (i = 0; i < size; i++) {
143 
	array [i].alt    = NIL (AltP);
 172 
	array[i].alt    = NIL(AltP);
144 
	array [i].inited = FALSE;
 173 
	array[i].inited = FALSE;
145 
    }
 174 
    }
146 
    return (array);
 175 
    return(array);
147 
}
 176 
}
148 
 
 177 
 
149 
static VectorEntryP
 178 
static VectorEntryP
150 
rule_left_cycle_vector PROTO_N ((size))
 179 
rule_left_cycle_vector(unsigned size)
151 
		       PROTO_T (unsigned size)
 - 
 
152 
{
 180 
{
153 
    static VectorEntryP array      = NIL (VectorEntryP);
 181 
    static VectorEntryP array      = NIL(VectorEntryP);
154 
    static unsigned     array_size = 0;
 182 
    static unsigned     array_size = 0;
155 
    unsigned            i;
 183 
    unsigned            i;
156 
 
 184 
 
157 
    if (size > array_size) {
 185 
    if (size > array_size) {
158 
	DEALLOCATE (array);
 186 
	DEALLOCATE(array);
159 
	array      = ALLOCATE_VECTOR (VectorEntryT, size);
 187 
	array      = ALLOCATE_VECTOR(VectorEntryT, size);
160 
	array_size = size;
 188 
	array_size = size;
161 
    }
 189 
    }
162 
    for (i = 0; i < size; i ++) {
 190 
    for (i = 0; i < size; i++) {
163 
	array [i].empty_alt = FALSE;
 191 
	array[i].empty_alt = FALSE;
164 
	array [i].alt       = NIL (AltP);
 192 
	array[i].alt       = NIL(AltP);
165 
	array [i].inited    = FALSE;
 193 
	array[i].inited    = FALSE;
166 
    }
 194 
    }
167 
    return (array);
 195 
    return(array);
168 
}
 196 
}
169 
 
 197 
 
170 
static void
 198 
static void
171 
rule_destroy_cycle_matrix PROTO_N ((matrix, size))
 199 
rule_destroy_cycle_matrix(MatrixEntryP matrix, unsigned size)
172 
			  PROTO_T (MatrixEntryP matrix X
 - 
 
173 
				   unsigned     size)
 - 
 
174 
{
 200 
{
175 
    unsigned i;
 201 
    unsigned i;
176 
 
 202 
 
177 
    for (i = 0; i < size; i ++) {
 203 
    for (i = 0; i < size; i++) {
178 
	if (matrix [i].inited) {
 204 
	if (matrix[i].inited) {
179 
	    AltP alt = matrix [i].alt;
 205 
	    AltP alt = matrix[i].alt;
180 
 
 206 
 
181 
	    while (alt) {
 207 
	    while (alt) {
182 
		alt = alt_deallocate (alt);
 208 
		alt = alt_deallocate(alt);
183 
	    }
 209 
	    }
184 
	    types_destroy (&(matrix [i].param));
 210 
	    types_destroy(&(matrix[i].param));
185 
	}
 211 
	}
186 
    }
 212 
    }
187 
}
 213 
}
188 
 
 214 
 
189 
static void
 215 
static void
190 
rule_destroy_cycle_vector PROTO_N ((vector, size))
 216 
rule_destroy_cycle_vector(VectorEntryP vector, unsigned size)
191 
			  PROTO_T (VectorEntryP vector X
 - 
 
192 
				   unsigned     size)
 - 
 
193 
{
 217 
{
194 
    unsigned i;
 218 
    unsigned i;
195 
 
 219 
 
196 
    for (i = 0; i < size; i ++) {
 220 
    for (i = 0; i < size; i++) {
197 
	if (vector [i].inited) {
 221 
	if (vector[i].inited) {
198 
	    AltP alt = vector [i].alt;
 222 
	    AltP alt = vector[i].alt;
199 
 
 223 
 
200 
	    while (alt) {
 224 
	    while (alt) {
201 
		alt = alt_deallocate (alt);
 225 
		alt = alt_deallocate(alt);
202 
	    }
 226 
	    }
203 
	    types_destroy (&(vector [i].param));
 227 
	    types_destroy(&(vector[i].param));
204 
	}
 228 
	}
205 
    }
 229 
    }
206 
}
 230 
}
207 
 
 231 
 
208 
/*--------------------------------------------------------------------------*/
 232 
/*--------------------------------------------------------------------------*/
209 
 
 233 
 
210 
static ItemP
 234 
static ItemP
211 
rule_find_suffix PROTO_N ((rec_item, non_rec_item))
 235 
rule_find_suffix(ItemP rec_item, ItemP non_rec_item)
212 
		 PROTO_T (ItemP rec_item X
 - 
 
213 
			  ItemP non_rec_item)
 - 
 
214 
{
 236 
{
215 
    ItemP    tmp_rec_item     = rec_item;
 237 
    ItemP    tmp_rec_item     = rec_item;
216 
    ItemP    tmp_non_rec_item = non_rec_item;
 238 
    ItemP    tmp_non_rec_item = non_rec_item;
217 
    unsigned diff             = 0;
 239 
    unsigned diff             = 0;
218 
 
 240 
 
219 
    while (tmp_rec_item && tmp_non_rec_item) {
 241 
    while (tmp_rec_item && tmp_non_rec_item) {
220 
	tmp_rec_item     = item_next (tmp_rec_item);
 242 
	tmp_rec_item     = item_next(tmp_rec_item);
221 
	tmp_non_rec_item = item_next (tmp_non_rec_item);
 243 
	tmp_non_rec_item = item_next(tmp_non_rec_item);
222 
    }
 244 
    }
223 
    while (tmp_rec_item) {
 245 
    while (tmp_rec_item) {
224 
	diff ++;
 246 
	diff++;
225 
	tmp_rec_item = item_next (tmp_rec_item);
 247 
	tmp_rec_item = item_next(tmp_rec_item);
226 
    }
 248 
    }
227 
    if (diff == 0) {
 249 
    if (diff == 0) {
228 
	return (NIL (ItemP));
 250 
	return(NIL(ItemP));
229 
    }
 251 
    }
230 
    do {
 252 
    do {
231 
	rec_item = item_next (rec_item);
 253 
	rec_item = item_next(rec_item);
232 
    } while (-- diff);
 254 
    } while (--diff);
233 
    tmp_rec_item     = rec_item;
 255 
    tmp_rec_item     = rec_item;
234 
    tmp_non_rec_item = non_rec_item;
 256 
    tmp_non_rec_item = non_rec_item;
235 
    while (tmp_rec_item && tmp_non_rec_item) {
 257 
    while (tmp_rec_item && tmp_non_rec_item) {
236 
	if (item_entry (tmp_rec_item) != item_entry (tmp_non_rec_item)) {
 258 
	if (item_entry(tmp_rec_item) != item_entry(tmp_non_rec_item)) {
237 
	    return (NIL (ItemP));
 259 
	    return(NIL(ItemP));
238 
	}
 260 
	}
239 
	tmp_rec_item     = item_next (tmp_rec_item);
 261 
	tmp_rec_item     = item_next(tmp_rec_item);
240 
	tmp_non_rec_item = item_next (tmp_non_rec_item);
 262 
	tmp_non_rec_item = item_next(tmp_non_rec_item);
241 
    }
 263 
    }
242 
    ASSERT ((tmp_rec_item == NIL (ItemP)) &&
 264 
    ASSERT((tmp_rec_item == NIL(ItemP)) && (tmp_non_rec_item == NIL(ItemP)));
243 
	    (tmp_non_rec_item == NIL (ItemP)));
 - 
 
244 
    return (rec_item);
 265 
    return(rec_item);
245 
}
 266 
}
246 
 
 267 
 
247 
static void
 268 
static void
248 
rule_renumber_item_list PROTO_N ((item, translator))
 269 
rule_renumber_item_list(ItemP item, TypeNTransP translator)
249 
			PROTO_T (ItemP       item X
 - 
 
250 
				 TypeNTransP translator)
 - 
 
251 
{
 270 
{
252 
    ntrans_init (translator);
 271 
    ntrans_init(translator);
253 
    for (; item; item = item_next (item)) {
 272 
    for (; item; item = item_next(item)) {
254 
	types_renumber (item_param (item), translator);
 273 
	types_renumber(item_param(item), translator);
255 
	types_renumber (item_result (item), translator);
 274 
	types_renumber(item_result(item), translator);
256 
    }
 275 
    }
257 
}
 276 
}
258 
 
 277 
 
259 
static BoolT
 278 
static BoolT
260 
rule_compare_item_lists PROTO_N ((rec_suffix, non_rec_item))
 279 
rule_compare_item_lists(ItemP rec_suffix, ItemP non_rec_item)
261 
			PROTO_T (ItemP rec_suffix X
 - 
 
262 
				 ItemP non_rec_item)
 - 
 
263 
{
 280 
{
264 
    while (rec_suffix) {
 281 
    while (rec_suffix) {
265 
	ASSERT (non_rec_item);
 282 
	ASSERT(non_rec_item);
266 
	if (!((types_equal_numbers (item_param (rec_suffix),
 283 
	if (!((types_equal_numbers(item_param(rec_suffix),
267 
				    item_param (non_rec_item))) &&
 284 
				   item_param(non_rec_item))) &&
268 
	      (types_equal_numbers (item_result (rec_suffix),
 285 
	      (types_equal_numbers(item_result(rec_suffix),
269 
				    item_result (non_rec_item))))) {
 286 
				   item_result(non_rec_item))))) {
270 
	    return (FALSE);
 287 
	    return(FALSE);
271 
	}
 288 
	}
272 
	rec_suffix   = item_next (rec_suffix);
 289 
	rec_suffix   = item_next(rec_suffix);
273 
	non_rec_item = item_next (non_rec_item);
 290 
	non_rec_item = item_next(non_rec_item);
274 
    }
 291 
    }
275 
    ASSERT (non_rec_item == NIL (ItemP));
 292 
    ASSERT(non_rec_item == NIL(ItemP));
276 
    return (TRUE);
 293 
    return(TRUE);
277 
}
 294 
}
278 
 
 295 
 
279 
static void
 296 
static void
280 
rule_left_cycle_special_case_2 PROTO_N ((rule, table, non_rec_alt, rec_alt,
 297 
rule_left_cycle_special_case_2(RuleP rule, TableP table, AltP non_rec_alt,
281 
					 param, rec_suffix))
 - 
 
282 
			       PROTO_T (RuleP      rule X
 298 
			       AltP rec_alt, TypeTupleP param, ItemP rec_suffix)
283 
					TableP     table X
 - 
 
284 
					AltP       non_rec_alt X
 - 
 
285 
					AltP       rec_alt X
 - 
 
286 
					TypeTupleP param X
 - 
 
287 
					ItemP      rec_suffix)
 - 
 
288 
{
 299 
{
289 
    EntryP      entry    = table_add_generated_rule (table, TRUE);
 300 
    EntryP      entry    = table_add_generated_rule(table, TRUE);
290 
    RuleP       new_rule = entry_get_rule (entry);
 301 
    RuleP       new_rule = entry_get_rule(entry);
291 
    ItemP       new_item = item_create (entry);
 302 
    ItemP       new_item = item_create(entry);
292 
    ItemP       rec_item = alt_unlink_item_head (rec_alt);
 303 
    ItemP       rec_item = alt_unlink_item_head(rec_alt);
293 
    AltP        new_alt  = alt_create ();
 304 
    AltP        new_alt  = alt_create();
294 
    AltP        handler;
 305 
    AltP        handler;
295 
    ItemP       item;
 306 
    ItemP       item;
296 
    TypeBTransT tmp_trans;
 307 
    TypeBTransT tmp_trans;
297 
    TypeTupleT  result;
 308 
    TypeTupleT  result;
298 
 
 309 
 
299 
    rule_reinit (rule);
 310 
    rule_reinit(rule);
300 
    alt_set_next (non_rec_alt, NIL (AltP));
 311 
    alt_set_next(non_rec_alt, NIL(AltP));
301 
    btrans_init (&tmp_trans);
 312 
    btrans_init(&tmp_trans);
302 
    types_copy (&result, rule_result (rule));
 313 
    types_copy(&result, rule_result(rule));
303 
    btrans_generate_names (&tmp_trans, &result, table);
 314 
    btrans_generate_names(&tmp_trans, &result, table);
304 
    types_translate (&result, &tmp_trans);
 315 
    types_translate(&result, &tmp_trans);
305 
    if ((handler = rule_get_handler (rule)) != NIL (AltP)) {
 316 
    if ((handler = rule_get_handler(rule)) != NIL(AltP)) {
306 
	ItemP handler_items = alt_item_head (handler);
 317 
	ItemP handler_items = alt_item_head(handler);
307 
 
 318 
 
308 
	item_translate_list (handler_items, &tmp_trans);
 319 
	item_translate_list(handler_items, &tmp_trans);
309 
    }
 320 
    }
310 
    btrans_destroy (&tmp_trans);
 321 
    btrans_destroy(&tmp_trans);
311 
    types_assign (item_param (new_item), rule_result (rule));
 322 
    types_assign(item_param(new_item), rule_result(rule));
312 
    types_copy (item_result (new_item), &result);
 323 
    types_copy(item_result(new_item), &result);
313 
    types_copy (rule_result (rule), &result);
 324 
    types_copy(rule_result(rule), &result);
314 
    alt_add_item (non_rec_alt, new_item);
 325 
    alt_add_item(non_rec_alt, new_item);
315 
    rule_add_alt (rule, non_rec_alt);
 326 
    rule_add_alt(rule, non_rec_alt);
316 
    types_copy (rule_param (new_rule), item_result (rec_item));
 327 
    types_copy(rule_param(new_rule), item_result(rec_item));
317 
    types_copy (rule_result (new_rule), &result);
 328 
    types_copy(rule_result(new_rule), &result);
318 
    (void) item_deallocate (rec_item);
 329 
   (void)item_deallocate(rec_item);
319 
    while (item = alt_item_head (rec_alt), item != rec_suffix) {
 330 
    while (item = alt_item_head(rec_alt), item != rec_suffix) {
320 
	alt_add_item (new_alt, alt_unlink_item_head (rec_alt));
 331 
	alt_add_item(new_alt, alt_unlink_item_head(rec_alt));
321 
    }
 332 
    }
322 
    (void) alt_deallocate (rec_alt);
 333 
   (void)alt_deallocate(rec_alt);
323 
    new_item = item_create (rule_entry (rule));
 334 
    new_item = item_create(rule_entry(rule));
324 
    if (param) {
 335 
    if (param) {
325 
	types_assign (item_param (new_item), param);
 336 
	types_assign(item_param(new_item), param);
326 
    } else {
 337 
    } else {
327 
	types_copy (item_param (new_item), rule_param (new_rule));
 338 
	types_copy(item_param(new_item), rule_param(new_rule));
328 
    }
 339 
    }
329 
    types_assign (item_result (new_item), &result);
 340 
    types_assign(item_result(new_item), &result);
330 
    alt_add_item (new_alt, new_item);
 341 
    alt_add_item(new_alt, new_item);
331 
    rule_add_alt (new_rule, new_alt);
 342 
    rule_add_alt(new_rule, new_alt);
332 
    if (types_equal_zero_tuple (rule_param (new_rule))) {
 343 
    if (types_equal_zero_tuple(rule_param(new_rule))) {
333 
	rule_add_empty_alt (new_rule);
 344 
	rule_add_empty_alt(new_rule);
334 
    } else {
 345 
    } else {
335 
	new_alt  = alt_create ();
 346 
	new_alt  = alt_create();
336 
	new_item = item_create (table_add_rename (table));
 347 
	new_item = item_create(table_add_rename(table));
337 
	types_copy (item_param (new_item), rule_param (new_rule));
 348 
	types_copy(item_param(new_item), rule_param(new_rule));
338 
	types_copy (item_result (new_item), rule_result (new_rule));
 349 
	types_copy(item_result(new_item), rule_result(new_rule));
339 
	alt_add_item (new_alt, new_item);
 350 
	alt_add_item(new_alt, new_item);
340 
	rule_add_alt (new_rule, new_alt);
 351 
	rule_add_alt(new_rule, new_alt);
341 
    }
 352 
    }
342 
}
 353 
}
343 
 
 354 
 
344 
static BoolT
 355 
static BoolT
345 
rule_left_cycle_special_case_1 PROTO_N ((rule, table))
 356 
rule_left_cycle_special_case_1(RuleP rule, TableP table)
346 
			       PROTO_T (RuleP  rule X
 - 
 
347 
					TableP table)
 - 
 
348 
{
 357 
{
349 
    AltP        rec_alt = rule_alt_head (rule);
 358 
    AltP        rec_alt = rule_alt_head(rule);
350 
    AltP        non_rec_alt;
 359 
    AltP        non_rec_alt;
351 
    ItemP       rec_item;
 360 
    ItemP       rec_item;
352 
    ItemP       rec_next;
 361 
    ItemP       rec_next;
353 
    ItemP       rec_suffix;
 362 
    ItemP       rec_suffix;
354 
    ItemP       non_rec_item;
 363 
    ItemP       non_rec_item;
355 
    TypeTupleT  param;
 364 
    TypeTupleT  param;
356 
    TypeNTransT rec_translator;
 365 
    TypeNTransT rec_translator;
357 
    TypeNTransT non_rec_translator;
 366 
    TypeNTransT non_rec_translator;
358 
 
 367 
 
359 
    if (((non_rec_alt = alt_next (rec_alt)) == NIL (AltP)) ||
 368 
    if (((non_rec_alt = alt_next(rec_alt)) == NIL(AltP)) ||
360 
	(alt_next (non_rec_alt))) {
 369 
	(alt_next(non_rec_alt))) {
361 
	return (FALSE);
 370 
	return(FALSE);
362 
    }
 371 
    }
363 
    if ((item_is_rule (non_rec_item = alt_item_head (non_rec_alt))) &&
 372 
    if ((item_is_rule(non_rec_item = alt_item_head(non_rec_alt))) &&
364 
	(entry_get_rule (item_entry (non_rec_item)) == rule)) {
 373 
	(entry_get_rule(item_entry(non_rec_item)) == rule)) {
365 
	non_rec_alt  = rec_alt;
 374 
	non_rec_alt  = rec_alt;
366 
	rec_alt      = alt_next (rec_alt);
 375 
	rec_alt      = alt_next(rec_alt);
367 
	non_rec_item = alt_item_head (non_rec_alt);
 376 
	non_rec_item = alt_item_head(non_rec_alt);
368 
    }
 377 
    }
369 
    if ((item_is_rule (non_rec_item)) &&
 378 
    if ((item_is_rule(non_rec_item)) &&
370 
	(entry_get_rule (item_entry (non_rec_item)) == rule)) {
 379 
	(entry_get_rule(item_entry(non_rec_item)) == rule)) {
371 
	return (FALSE);
 380 
	return(FALSE);
372 
    }
 381 
    }
373 
    rec_item = alt_item_head (rec_alt);
 382 
    rec_item = alt_item_head(rec_alt);
374 
    if (!((types_equal_names (rule_param (rule), item_param (rec_item))) &&
 383 
    if (!((types_equal_names(rule_param(rule), item_param(rec_item))) &&
375 
	  (types_equal (rule_param (rule), rule_result (rule))))) {
 384 
	  (types_equal(rule_param(rule), rule_result(rule))))) {
376 
	return (FALSE);
 385 
	return(FALSE);
377 
    }
 386 
    }
378 
    rec_next = item_next (rec_item);
 387 
    rec_next = item_next(rec_item);
379 
    if (item_names_used_in_list (rec_next, rule_param (rule))) {
 388 
    if (item_names_used_in_list(rec_next, rule_param(rule))) {
380 
	return (FALSE);
 389 
	return(FALSE);
381 
    }
 390 
    }
382 
    if ((rec_suffix = rule_find_suffix (rec_item, non_rec_item)) ==
 391 
    if ((rec_suffix = rule_find_suffix(rec_item, non_rec_item)) ==
383 
	NIL (ItemP)) {
 392 
	NIL(ItemP)) {
384 
	return (FALSE);
 393 
	return(FALSE);
385 
    }
 394 
    }
386 
    if ((rec_suffix != rec_next) &&
 395 
    if ((rec_suffix != rec_next) &&
387 
	(item_names_used_in_list (rec_suffix, item_result (rec_item)))) {
 396 
	(item_names_used_in_list(rec_suffix, item_result(rec_item)))) {
388 
	return (FALSE);
 397 
	return(FALSE);
389 
    }
 398 
    }
390 
    rule_renumber_item_list (non_rec_item, &non_rec_translator);
 399 
    rule_renumber_item_list(non_rec_item, &non_rec_translator);
391 
    rule_renumber_item_list (rec_suffix, &rec_translator);
 400 
    rule_renumber_item_list(rec_suffix, &rec_translator);
392 
    if (!rule_compare_item_lists (rec_suffix, non_rec_item)) {
 401 
    if (!rule_compare_item_lists(rec_suffix, non_rec_item)) {
393 
	ntrans_destroy (&non_rec_translator);
 402 
	ntrans_destroy(&non_rec_translator);
394 
	ntrans_destroy (&rec_translator);
 403 
	ntrans_destroy(&rec_translator);
395 
	return (FALSE);
 404 
	return(FALSE);
396 
    }
 405 
    }
397 
    if (rec_suffix == rec_next) {
 406 
    if (rec_suffix == rec_next) {
398 
	ntrans_destroy (&non_rec_translator);
 407 
	ntrans_destroy(&non_rec_translator);
399 
	ntrans_destroy (&rec_translator);
 408 
	ntrans_destroy(&rec_translator);
400 
	rule_left_cycle_special_case_2 (rule, table, non_rec_alt, rec_alt,
 409 
	rule_left_cycle_special_case_2(rule, table, non_rec_alt, rec_alt,
401 
					NIL (TypeTupleP), rec_suffix);
 410 
				       NIL(TypeTupleP), rec_suffix);
402 
    } else {
 411 
    } else {
403 
	types_compute_param_from_trans (&param, &non_rec_translator,
 412 
	types_compute_param_from_trans(&param, &non_rec_translator,
404 
					&rec_translator, rule_param (rule));
 413 
				       &rec_translator, rule_param(rule));
405 
	ntrans_destroy (&non_rec_translator);
 414 
	ntrans_destroy(&non_rec_translator);
406 
	ntrans_destroy (&rec_translator);
 415 
	ntrans_destroy(&rec_translator);
407 
	rule_left_cycle_special_case_2 (rule, table, non_rec_alt, rec_alt,
 416 
	rule_left_cycle_special_case_2(rule, table, non_rec_alt, rec_alt,
408 
					&param, rec_suffix);
 417 
				       &param, rec_suffix);
409 
    }
 418 
    }
410 
    return (TRUE);
 419 
    return(TRUE);
411 
}
 420 
}
412 
 
 421 
 
413 
static BoolT
 422 
static BoolT
414 
rule_left_cycle_special_case PROTO_N ((rule, table))
 423 
rule_left_cycle_special_case(RuleP rule, TableP table)
415 
			     PROTO_T (RuleP  rule X
 - 
 
416 
				      TableP table)
 - 
 
417 
{
 424 
{
418 
    if (rule_has_empty_alt (rule)) {
 425 
    if (rule_has_empty_alt(rule)) {
419 
	AltP  alt = rule_alt_head (rule);
 426 
	AltP  alt = rule_alt_head(rule);
420 
	ItemP item;
 427 
	ItemP item;
421 
 
 428 
 
422 
	if ((alt == NIL (AltP)) || (alt_next (alt) != NIL (AltP))) {
 429 
	if ((alt == NIL(AltP)) || (alt_next(alt) != NIL(AltP))) {
423 
	    return (FALSE);
 430 
	    return(FALSE);
424 
	}
 431 
	}
425 
	item = alt_unlink_item_head (alt);
 432 
	item = alt_unlink_item_head(alt);
426 
	alt_add_item (alt, item);
 433 
	alt_add_item(alt, item);
427 
	return (TRUE);
 434 
	return(TRUE);
428 
    } else {
 435 
    } else {
429 
	return (rule_left_cycle_special_case_1 (rule, table));
 436 
	return(rule_left_cycle_special_case_1(rule, table));
430 
    }
 437 
    }
431 
}
 438 
}
432 
 
 439 
 
433 
/*--------------------------------------------------------------------------*/
 440 
/*--------------------------------------------------------------------------*/
434 
 
 441 
 
435 
static BoolT
 442 
static BoolT
436 
rule_check_non_locals PROTO_N ((this_rule, rule_list, real_size))
 443 
rule_check_non_locals(RuleP this_rule, RuleP rule_list, unsigned real_size)
437 
		      PROTO_T (RuleP    this_rule X
 - 
 
438 
			       RuleP    rule_list X
 - 
 
439 
			       unsigned real_size)
 - 
 
440 
{
 444 
{
441 
    NStringP scope  = rule_maximum_scope (this_rule);
 445 
    NStringP scope  = rule_maximum_scope(this_rule);
442 
    unsigned length = nstring_length (scope);
 446 
    unsigned length = nstring_length(scope);
443 
    RuleP    rule;
 447 
    RuleP    rule;
444 
 
 448 
 
445 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs (rule)) {
 449 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
446 
	KeyP key = entry_key (rule_entry (rule));
 450 
	KeyP key = entry_key(rule_entry(rule));
447 
 
 451 
 
448 
	if ((rule != this_rule) && key_is_string (key)) {
 452 
	if ((rule != this_rule) && key_is_string(key)) {
449 
	    NStringP string = key_get_string (key);
 453 
	    NStringP string = key_get_string(key);
450 
 
 454 
 
451 
	    if (!(nstring_is_prefix (string, scope) ||
 455 
	    if (!(nstring_is_prefix(string, scope) ||
452 
		  (nstring_is_prefix (scope, string) &&
 456 
		  (nstring_is_prefix(scope, string) &&
453 
		   ((nstring_length (string) + 2) == length)))) {
 457 
		   ((nstring_length(string) + 2) == length)))) {
454 
		E_out_of_scope_non_local (this_rule, rule, rule_list);
 458 
		E_out_of_scope_non_local(this_rule, rule, rule_list);
455 
		return (FALSE);
 459 
		return(FALSE);
456 
	    }
 460 
	    }
457 
	}
 461 
	}
458 
    }
 462 
    }
459 
    if (non_local_list_is_empty (rule_non_locals (this_rule)) ||
 463 
    if (non_local_list_is_empty(rule_non_locals(this_rule)) ||
460 
	(real_size == 1)) {
 464 
	(real_size == 1)) {
461 
	return (TRUE);
 465 
	return(TRUE);
462 
    } else {
 466 
    } else {
463 
	E_left_recursion_nl_entry (this_rule, rule_list);
 467 
	E_left_recursion_nl_entry(this_rule, rule_list);
464 
	return (FALSE);
 468 
	return(FALSE);
465 
    }
 469 
    }
466 
}
 470 
}
467 
 
 471 
 
468 
static BoolT
 472 
static BoolT
469 
rule_check_alt_cycle_types PROTO_N ((rule, rule_list, alt, need_check,
 473 
rule_check_alt_cycle_types(RuleP rule, RuleP rule_list, AltP alt,
470 
				     translator1, translator2, table,
 - 
 
471 
				     generate_ref))
 - 
 
472 
			   PROTO_T (RuleP       rule X
 - 
 
473 
				    RuleP       rule_list X
 - 
 
474 
				    AltP        alt X
 - 
 
475 
				    BoolT       need_check X
 - 
 
476 
				    TypeBTransP translator1 X
 474 
			   BoolT need_check, TypeBTransP translator1,
477 
				    TypeBTransP translator2 X
 475 
			   TypeBTransP translator2, TableP table,
478 
				    TableP      table X
 - 
 
479 
				    BoolP       generate_ref)
 476 
			   BoolP generate_ref)
480 
{
 477 
{
481 
    ItemP item = alt_item_head (alt);
 478 
    ItemP item = alt_item_head(alt);
482 
 
 479 
 
483 
    item_translate_list (item, translator1);
 480 
    item_translate_list(item, translator1);
484 
    if (item_is_rule (item)) {
 481 
    if (item_is_rule(item)) {
485 
	RuleP item_rule = entry_get_rule (item_entry (item));
 482 
	RuleP item_rule = entry_get_rule(item_entry(item));
486 
 
 483 
 
487 
	if (rule_get_cycle_index (item_rule) != 0) {
 484 
	if (rule_get_cycle_index(item_rule) != 0) {
488 
	    TypeTupleT result_intersect;
 485 
	    TypeTupleT result_intersect;
489 
 
 486 
 
490 
	    if (need_check && (!types_equal_names (rule_param (rule),
 487 
	    if (need_check && (!types_equal_names(rule_param(rule),
491 
						   item_param (item)))) {
 488 
						  item_param(item)))) {
492 
		btrans_destroy (translator1);
 489 
		btrans_destroy(translator1);
493 
		btrans_destroy (translator2);
 490 
		btrans_destroy(translator2);
494 
		E_left_recursion_name_mismatch (rule_list);
 491 
		E_left_recursion_name_mismatch(rule_list);
495 
		return (FALSE);
 492 
		return(FALSE);
496 
	    }
 493 
	    }
497 
/* If a result identifier is returned by the left recursive call, it is
 494 
/* If a result identifier is returned by the left recursive call, it is
498 
 * necessary to rename that return value, and use an identity afterwards to
 495 
 * necessary to rename that return value, and use an identity afterwards to
499 
 * rename it.
 496 
 * rename it.
500 
 **/
 497 
 **/
501 
	    types_init (&result_intersect);
 498 
	    types_init(&result_intersect);
502 
	    types_compute_intersection (&result_intersect, rule_result (rule),
 499 
	    types_compute_intersection(&result_intersect, rule_result(rule),
503 
					item_result (item));
 500 
				       item_result(item));
504 
	    if (!types_equal_zero_tuple (&result_intersect)) {
 501 
	    if (!types_equal_zero_tuple(&result_intersect)) {
505 
		EntryP      new_entry = table_add_rename (table);
 502 
		EntryP      new_entry = table_add_rename(table);
506 
		ItemP       new_item  = item_create (new_entry);
 503 
		ItemP       new_item  = item_create(new_entry);
507 
		TypeBTransT tmp_trans;
 504 
		TypeBTransT tmp_trans;
508 
		TypeTupleT  tmp_tuple;
 505 
		TypeTupleT  tmp_tuple;
509 
 
 506 
 
510 
		btrans_init (&tmp_trans);
 507 
		btrans_init(&tmp_trans);
511 
		types_copy (&tmp_tuple, &result_intersect);
 508 
		types_copy(&tmp_tuple, &result_intersect);
512 
		btrans_generate_names (&tmp_trans, &tmp_tuple, table);
 509 
		btrans_generate_names(&tmp_trans, &tmp_tuple, table);
513 
		types_translate (&tmp_tuple, &tmp_trans);
 510 
		types_translate(&tmp_tuple, &tmp_trans);
514 
		types_translate (item_result (item), &tmp_trans);
 511 
		types_translate(item_result(item), &tmp_trans);
515 
		btrans_destroy (&tmp_trans);
 512 
		btrans_destroy(&tmp_trans);
516 
		types_assign (item_param (new_item), &tmp_tuple);
 513 
		types_assign(item_param(new_item), &tmp_tuple);
517 
		types_assign (item_result (new_item), &result_intersect);
 514 
		types_assign(item_result(new_item), &result_intersect);
518 
		item_set_next (new_item, item_next (item));
 515 
		item_set_next(new_item, item_next(item));
519 
		item_set_next (item, new_item);
 516 
		item_set_next(item, new_item);
520 
	    } else {
 517 
	    } else {
521 
		types_destroy (&result_intersect);
 518 
		types_destroy(&result_intersect);
522 
	    }
 519 
	    }
523 
	    if (*generate_ref) {
 520 
	    if (*generate_ref) {
524 
		btrans_generate_names (translator2, item_result (item),
 521 
		btrans_generate_names(translator2, item_result(item), table);
525 
				       table);
 - 
 
526 
		*generate_ref = FALSE;
 522 
		*generate_ref = FALSE;
527 
	    } else {
 523 
	    } else {
528 
		btrans_regenerate_names (translator2, item_result (item));
 524 
		btrans_regenerate_names(translator2, item_result(item));
529 
	    }
 525 
	    }
530 
	    types_translate (item_result (item), translator2);
 526 
	    types_translate(item_result(item), translator2);
531 
	    item_translate_list (item_next (item), translator2);
 527 
	    item_translate_list(item_next(item), translator2);
532 
	}
 528 
	}
533 
    }
 529 
    }
534 
    return (TRUE);
 530 
    return(TRUE);
535 
}
 531 
}
536 
 
 532 
 
537 
static BoolT
 533 
static BoolT
538 
rule_check_cycle_types PROTO_N ((rule_list, predicate_id, real_size, table))
 534 
rule_check_cycle_types(RuleP rule_list, EntryP predicate_id,
539 
		       PROTO_T (RuleP    rule_list X
 - 
 
540 
				EntryP   predicate_id X
 - 
 
541 
				unsigned real_size X
 535 
		       unsigned real_size, TableP table)
542 
				TableP   table)
 - 
 
543 
{
 536 
{
544 
    TypeTupleP  param    = rule_param (rule_list);
 537 
    TypeTupleP  param    = rule_param(rule_list);
545 
    TypeTupleP  result   = rule_result (rule_list);
 538 
    TypeTupleP  result   = rule_result(rule_list);
546 
    AltP        handler  = rule_get_handler (rule_list);
 539 
    AltP        handler  = rule_get_handler(rule_list);
547 
    BoolT       generate = TRUE;
 540 
    BoolT       generate = TRUE;
548 
    RuleP       rule;
 541 
    RuleP       rule;
549 
    TypeBTransT translator1;
 542 
    TypeBTransT translator1;
550 
    TypeBTransT translator2;
 543 
    TypeBTransT translator2;
551 
 
 544 
 
552 
    rule_renumber (rule_list, TRUE, predicate_id);
 545 
    rule_renumber(rule_list, TRUE, predicate_id);
553 
    if (!rule_check_non_locals (rule_list, rule_list, real_size)) {
 546 
    if (!rule_check_non_locals(rule_list, rule_list, real_size)) {
554 
	return (FALSE);
 547 
	return(FALSE);
555 
    }
 548 
    }
556 
    for (rule = rule_get_next_in_reverse_dfs (rule_list); rule;
 549 
    for (rule = rule_get_next_in_reverse_dfs(rule_list); rule;
557 
	 rule = rule_get_next_in_reverse_dfs (rule)) {
 550 
	 rule = rule_get_next_in_reverse_dfs(rule)) {
558 
	if (!((types_equal (param, rule_param (rule))) &&
 551 
	if (!((types_equal(param, rule_param(rule))) &&
559 
	      (types_equal (result, rule_result (rule))))) {
 552 
	      (types_equal(result, rule_result(rule))))) {
560 
	    E_left_recursion_type_mismatch (rule_list);
 553 
	    E_left_recursion_type_mismatch(rule_list);
561 
	    return (FALSE);
 554 
	    return(FALSE);
562 
	}
 555 
	}
563 
	rule_renumber (rule, TRUE, predicate_id);
 556 
	rule_renumber(rule, TRUE, predicate_id);
564 
	if (!alt_equal (handler, rule_get_handler (rule))) {
 557 
	if (!alt_equal(handler, rule_get_handler(rule))) {
565 
	    E_left_rec_handler_mismatch (rule_list);
 558 
	    E_left_rec_handler_mismatch(rule_list);
566 
	    return (FALSE);
 559 
	    return(FALSE);
567 
	}
 560 
	}
568 
	if (!rule_check_non_locals (rule, rule_list, real_size)) {
 561 
	if (!rule_check_non_locals(rule, rule_list, real_size)) {
569 
	    return (FALSE);
 562 
	    return(FALSE);
570 
	}
 563 
	}
571 
    }
 564 
    }
572 
    btrans_init (&translator1);
 565 
    btrans_init(&translator1);
573 
    btrans_init (&translator2);
 566 
    btrans_init(&translator2);
574 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs (rule)) {
 567 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
575 
	AltP alt;
 568 
	AltP alt;
576 
 
 569 
 
577 
	if (rule == rule_list) {
 570 
	if (rule == rule_list) {
578 
	    btrans_generate_names (&translator1, rule_param (rule), table);
 571 
	    btrans_generate_names(&translator1, rule_param(rule), table);
579 
	} else {
 572 
	} else {
580 
	    btrans_regenerate_names (&translator1, rule_param (rule));
 573 
	    btrans_regenerate_names(&translator1, rule_param(rule));
581 
	}
 574 
	}
582 
	types_translate (rule_param (rule), &translator1);
 575 
	types_translate(rule_param(rule), &translator1);
583 
	if ((alt = rule_get_handler (rule)) != NIL (AltP)) {
 576 
	if ((alt = rule_get_handler(rule)) != NIL(AltP)) {
584 
	    (void) rule_check_alt_cycle_types (rule, rule_list, alt, FALSE,
 577 
	   (void)rule_check_alt_cycle_types(rule, rule_list, alt, FALSE,
585 
					       &translator1, &translator2,
 578 
					    &translator1, &translator2, table,
586 
					       table, &generate);
 579 
					    &generate);
587 
	}
 580 
	}
588 
	for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
 581 
	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
589 
	    if (!rule_check_alt_cycle_types (rule, rule_list, alt, TRUE,
 582 
	    if (!rule_check_alt_cycle_types(rule, rule_list, alt, TRUE,
590 
					     &translator1, &translator2, table,
 583 
					    &translator1, &translator2, table,
591 
					     &generate)) {
 584 
					    &generate)) {
592 
		return (FALSE);
 585 
		return(FALSE);
593 
	    }
 586 
	    }
594 
	}
 587 
	}
595 
    }
 588 
    }
596 
    btrans_destroy (&translator1);
 589 
    btrans_destroy(&translator1);
597 
    btrans_destroy (&translator2);
 590 
    btrans_destroy(&translator2);
598 
    return (TRUE);
 591 
    return(TRUE);
599 
}
 592 
}
600 
 
 593 
 
601 
static void
 594 
static void
602 
rule_compute_param_subset PROTO_N ((rule_list, subset))
 595 
rule_compute_param_subset(RuleP rule_list, TypeTupleP subset)
603 
			  PROTO_T (RuleP      rule_list X
 - 
 
604 
				   TypeTupleP subset)
 - 
 
605 
{
 596 
{
606 
    RuleP rule;
 597 
    RuleP rule;
607 
 
 598 
 
608 
    types_init (subset);
 599 
    types_init(subset);
609 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs (rule)) {
 600 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
610 
	TypeTupleP param = rule_param (rule);
 601 
	TypeTupleP param = rule_param(rule);
611 
	AltP       alt;
 602 
	AltP       alt;
612 
 
 603 
 
613 
	for (alt = rule_alt_head (rule); alt; alt = alt_next (alt)) {
 604 
	for (alt = rule_alt_head(rule); alt; alt = alt_next(alt)) {
614 
	    ItemP item = alt_item_head (alt);
 605 
	    ItemP item = alt_item_head(alt);
615 
 
 606 
 
616 
	    if (item_is_rule (item)) {
 607 
	    if (item_is_rule(item)) {
617 
		RuleP item_rule = entry_get_rule (item_entry (item));
 608 
		RuleP item_rule = entry_get_rule(item_entry(item));
618 
 
 609 
 
619 
		if (rule_get_cycle_index (item_rule) != 0) {
 610 
		if (rule_get_cycle_index(item_rule) != 0) {
620 
		    for (item = item_next (item); item;
 611 
		    for (item = item_next(item); item;
621 
			 item = item_next (item)) {
 612 
			 item = item_next(item)) {
622 
			types_compute_intersection (subset, param,
 613 
			types_compute_intersection(subset, param,
623 
						    item_param (item));
 614 
						   item_param(item));
624 
		    }
 615 
		    }
625 
		}
 616 
		}
626 
	    }
 617 
	    }
627 
	}
 618 
	}
628 
    }
 619 
    }
629 
}
 620 
}
630 
 
 621 
 
631 
static void
 622 
static void
632 
rule_left_cycle_general_case_1 PROTO_N ((rule_list, size, matrix, vector,
 623 
rule_left_cycle_general_case_1(RuleP rule_list, unsigned size,
633 
					 table, gen_param, gen_result))
 - 
 
634 
			       PROTO_T (RuleP        rule_list X
 - 
 
635 
					unsigned     size X
 - 
 
636 
					MatrixEntryP matrix X
 624 
			       MatrixEntryP matrix, VectorEntryP vector,
637 
					VectorEntryP vector X
 - 
 
638 
					TableP       table X
 - 
 
639 
					TypeTupleP   gen_param X
 625 
			       TableP table, TypeTupleP gen_param,
640 
					TypeTupleP   gen_result)
 626 
			       TypeTupleP gen_result)
641 
{
 627 
{
642 
    unsigned    i               = 0;
 628 
    unsigned    i               = 0;
643 
    BoolT       generate        = TRUE;
 629 
    BoolT       generate        = TRUE;
644 
    BoolT       generate_param  = TRUE;
 630 
    BoolT       generate_param  = TRUE;
645 
    BoolT       generate_result = TRUE;
 631 
    BoolT       generate_result = TRUE;
Line 647... Line 633...
647 
    TypeBTransT translator;
 633 
    TypeBTransT translator;
648 
    TypeBTransT tmp_trans;
 634 
    TypeBTransT tmp_trans;
649 
    TypeTupleT  dummy;
 635 
    TypeTupleT  dummy;
650 
    TypeTupleT  param_subset;
 636 
    TypeTupleT  param_subset;
651 
 
 637 
 
652 
    btrans_init (&translator);
 638 
    btrans_init(&translator);
653 
    rule_compute_param_subset (rule_list, &param_subset);
 639 
    rule_compute_param_subset(rule_list, &param_subset);
654 
    btrans_init (&tmp_trans);
 640 
    btrans_init(&tmp_trans);
655 
    types_copy (&dummy, &param_subset);
 641 
    types_copy(&dummy, &param_subset);
656 
    btrans_generate_names (&tmp_trans, &dummy, table);
 642 
    btrans_generate_names(&tmp_trans, &dummy, table);
657 
    types_translate (&dummy, &tmp_trans);
 643 
    types_translate(&dummy, &tmp_trans);
658 
    btrans_destroy (&tmp_trans);
 644 
    btrans_destroy(&tmp_trans);
659 
    for (rule = rule_list; rule;
 645 
    for (rule = rule_list; rule;
660 
	 rule = rule_get_next_in_reverse_dfs (rule), i ++) {
 646 
	 rule = rule_get_next_in_reverse_dfs(rule), i++) {
661 
	AltP       alt = rule_alt_head (rule);
 647 
	AltP       alt = rule_alt_head(rule);
662 
	AltP       handler;
 648 
	AltP       handler;
663 
	TypeTupleT old_result;
 649 
	TypeTupleT old_result;
664 
 
 650 
 
665 
	types_copy (&old_result, rule_result (rule));
 651 
	types_copy(&old_result, rule_result(rule));
666 
	if (generate) {
 652 
	if (generate) {
667 
	    btrans_generate_names (&translator, rule_result (rule), table);
 653 
	    btrans_generate_names(&translator, rule_result(rule), table);
668 
	    generate = FALSE;
 654 
	    generate = FALSE;
669 
	} else {
 655 
	} else {
670 
	    btrans_regenerate_names (&translator, rule_result (rule));
 656 
	    btrans_regenerate_names(&translator, rule_result(rule));
671 
	}
 657 
	}
672 
	types_translate (rule_result (rule), &translator);
 658 
	types_translate(rule_result(rule), &translator);
673 
	if ((handler = rule_get_handler (rule)) != NIL (AltP)) {
 659 
	if ((handler = rule_get_handler(rule)) != NIL(AltP)) {
674 
	    ItemP handler_items = alt_item_head (handler);
 660 
	    ItemP handler_items = alt_item_head(handler);
675 
 
 661 
 
676 
	    item_translate_list (handler_items, &translator);
 662 
	    item_translate_list(handler_items, &translator);
677 
	}
 663 
	}
678 
	if (rule_has_empty_alt (rule)) {
 664 
	if (rule_has_empty_alt(rule)) {
679 
	    vector [i].empty_alt = TRUE;
 665 
	    vector[i].empty_alt = TRUE;
680 
	}
 666 
	}
681 
	while (alt) {
 667 
	while (alt) {
682 
	    ItemP    item    = alt_item_head (alt);
 668 
	    ItemP    item    = alt_item_head(alt);
683 
	    AltP     tmp_alt = alt;
 669 
	    AltP     tmp_alt = alt;
684 
	    RuleP    item_rule;
 670 
	    RuleP    item_rule;
685 
	    unsigned item_index;
 671 
	    unsigned item_index;
686 
 
 672 
 
687 
	    alt = alt_next (alt);
 673 
	    alt = alt_next(alt);
688 
	    if ((item_is_rule (item)) &&
 674 
	    if ((item_is_rule(item)) &&
689 
		((item_rule = entry_get_rule (item_entry (item))),
 675 
		((item_rule = entry_get_rule(item_entry(item))),
690 
		 ((item_index = rule_get_cycle_index (item_rule)) != 0))) {
 676 
		 ((item_index = rule_get_cycle_index(item_rule)) != 0))) {
691 
		unsigned matrix_index = (size * (item_index - 1) + i);
 677 
		unsigned matrix_index = (size *(item_index - 1) + i);
692 
 
 678 
 
693 
		if (!(matrix [matrix_index].inited)) {
 679 
		if (!(matrix[matrix_index].inited)) {
694 
		    TypeTupleP param = &(matrix [matrix_index].param);
 680 
		    TypeTupleP param = &(matrix[matrix_index].param);
695 
 
 681 
 
696 
		    types_copy (param, &param_subset);
 682 
		    types_copy(param, &param_subset);
697 
		    types_append_copy (param, &old_result);
 683 
		    types_append_copy(param, &old_result);
698 
		    matrix [matrix_index].inited = TRUE;
 684 
		    matrix[matrix_index].inited = TRUE;
699 
		}
 685 
		}
700 
		if (generate_param) {
 686 
		if (generate_param) {
701 
		    ItemP item_head = alt_item_head (tmp_alt);
 687 
		    ItemP item_head = alt_item_head(tmp_alt);
702 
 
 688 
 
703 
		    types_copy (gen_param, &param_subset);
 689 
		    types_copy(gen_param, &param_subset);
704 
		    types_append_copy (gen_param, item_result (item_head));
 690 
		    types_append_copy(gen_param, item_result(item_head));
705 
		    generate_param = FALSE;
 691 
		    generate_param = FALSE;
706 
		}
 692 
		}
707 
		(void) item_deallocate (alt_unlink_item_head (tmp_alt));
 693 
		(void)item_deallocate(alt_unlink_item_head(tmp_alt));
708 
		alt_set_next (tmp_alt, matrix [matrix_index].alt);
 694 
		alt_set_next(tmp_alt, matrix[matrix_index].alt);
709 
		matrix [matrix_index].alt = tmp_alt;
 695 
		matrix[matrix_index].alt = tmp_alt;
710 
	    } else {
 696 
	    } else {
711 
		if (!(vector [i].inited)) {
 697 
		if (!(vector[i].inited)) {
712 
		    TypeTupleP param = &(vector [i].param);
 698 
		    TypeTupleP param = &(vector[i].param);
713 
 
 699 
 
714 
		    types_copy (param, &param_subset);
 700 
		    types_copy(param, &param_subset);
715 
		    types_append_copy (param, &old_result);
 701 
		    types_append_copy(param, &old_result);
716 
		    vector [i].inited = TRUE;
 702 
		    vector[i].inited = TRUE;
717 
		}
 703 
		}
718 
		if (generate_result) {
 704 
		if (generate_result) {
719 
		    types_copy (gen_result, &dummy);
 705 
		    types_copy(gen_result, &dummy);
720 
		    types_append_copy (gen_result, rule_result (rule));
 706 
		    types_append_copy(gen_result, rule_result(rule));
721 
		    generate_result = FALSE;
 707 
		    generate_result = FALSE;
722 
		}
 708 
		}
723 
		alt_set_next (tmp_alt, vector [i].alt);
 709 
		alt_set_next(tmp_alt, vector[i].alt);
724 
		vector [i].alt = tmp_alt;
 710 
		vector[i].alt = tmp_alt;
725 
	    }
 711 
	    }
726 
	}
 712 
	}
727 
	rule_reinit (rule);
 713 
	rule_reinit(rule);
728 
	types_destroy (&old_result);
 714 
	types_destroy(&old_result);
729 
    }
 715 
    }
730 
    types_destroy (&param_subset);
 716 
    types_destroy(&param_subset);
731 
    btrans_destroy (&translator);
 717 
    btrans_destroy(&translator);
732 
}
 718 
}
733 
 
 719 
 
734 
static BoolT
 720 
static BoolT
735 
rule_left_cycle_general_case_2 PROTO_N ((rule_list, size, vector))
 721 
rule_left_cycle_general_case_2(RuleP rule_list, unsigned size,
736 
			       PROTO_T (RuleP        rule_list X
 - 
 
737 
					unsigned     size X
 - 
 
738 
					VectorEntryP vector)
 722 
			       VectorEntryP vector)
739 
{
 723 
{
740 
    BoolT    not_found = TRUE;
 724 
    BoolT    not_found = TRUE;
741 
    unsigned i;
 725 
    unsigned i;
742 
 
 726 
 
743 
    for (i = 0; i < size; i ++) {
 727 
    for (i = 0; i < size; i++) {
744 
	if ((vector [i].empty_alt) || (vector [i].alt)) {
 728 
	if ((vector[i].empty_alt) || (vector[i].alt)) {
745 
	    not_found = FALSE;
 729 
	    not_found = FALSE;
746 
	}
 730 
	}
747 
    }
 731 
    }
748 
    if (not_found) {
 732 
    if (not_found) {
749 
	E_cycle_no_terminator (rule_list);
 733 
	E_cycle_no_terminator(rule_list);
750 
	return (FALSE);
 734 
	return(FALSE);
751 
    }
 735 
    }
752 
    return (TRUE);
 736 
    return(TRUE);
753 
}
 737 
}
754 
 
 738 
 
755 
static void
 739 
static void
756 
rule_left_cycle_general_case_3 PROTO_N ((rule, size, vector, table,
 740 
rule_left_cycle_general_case_3(RuleP rule, unsigned size, VectorEntryP vector,
757 
					 new_rule_list_tail, param, result))
 - 
 
758 
			       PROTO_T (RuleP        rule X
 - 
 
759 
					unsigned     size X
 - 
 
760 
					VectorEntryP vector X
 - 
 
761 
					TableP       table X
 - 
 
762 
					RuleP       *new_rule_list_tail X
 741 
			       TableP table, RuleP *new_rule_list_tail,
763 
					TypeTupleP   param X
 - 
 
764 
					TypeTupleP   result)
 742 
			       TypeTupleP param, TypeTupleP result)
765 
{
 743 
{
766 
    unsigned j;
 744 
    unsigned j;
767 
 
 745 
 
768 
    for (j = 0; j < size; j ++) {
 746 
    for (j = 0; j < size; j++) {
769 
	EntryP entry    = table_add_generated_rule (table, TRUE);
 747 
	EntryP entry    = table_add_generated_rule(table, TRUE);
770 
	RuleP  new_rule = entry_get_rule (entry);
 748 
	RuleP  new_rule = entry_get_rule(entry);
771 
	AltP   alt;
 749 
	AltP   alt;
772 
 
 750 
 
773 
	types_copy (rule_param (new_rule), param);
 751 
	types_copy(rule_param(new_rule), param);
774 
	types_copy (rule_result (new_rule), result);
 752 
	types_copy(rule_result(new_rule), result);
775 
	*new_rule_list_tail = new_rule;
 753 
	*new_rule_list_tail = new_rule;
776 
	new_rule_list_tail  = rule_next_in_reverse_dfs_ref (new_rule);
 754 
	new_rule_list_tail  = rule_next_in_reverse_dfs_ref(new_rule);
777 
	if (vector [j].empty_alt) {
 755 
	if (vector[j].empty_alt) {
778 
	    AltP  new_alt  = alt_create ();
 756 
	    AltP  new_alt  = alt_create();
779 
	    ItemP new_item = item_create (entry);
 757 
	    ItemP new_item = item_create(entry);
780 
 
 758 
 
781 
	    types_copy (item_param (new_item), &(vector [j].param));
 759 
	    types_copy(item_param(new_item), &(vector[j].param));
782 
	    types_copy (item_result (new_item), result);
 760 
	    types_copy(item_result(new_item), result);
783 
	    alt_add_item (new_alt, new_item);
 761 
	    alt_add_item(new_alt, new_item);
784 
	    rule_add_alt (rule, new_alt);
 762 
	    rule_add_alt(rule, new_alt);
785 
	}
 763 
	}
786 
	for (alt = vector [j].alt; alt; alt = alt_next (alt)) {
 764 
	for (alt = vector[j].alt; alt; alt = alt_next(alt)) {
787 
	    AltP  new_alt  = alt_duplicate (alt);
 765 
	    AltP  new_alt  = alt_duplicate(alt);
788 
	    ItemP new_item = item_create (entry);
 766 
	    ItemP new_item = item_create(entry);
789 
 
 767 
 
790 
	    types_copy (item_param (new_item), &(vector [j].param));
 768 
	    types_copy(item_param(new_item), &(vector[j].param));
791 
	    types_copy (item_result (new_item), result);
 769 
	    types_copy(item_result(new_item), result);
792 
	    alt_add_item (new_alt, new_item);
 770 
	    alt_add_item(new_alt, new_item);
793 
	    rule_add_alt (rule, new_alt);
 771 
	    rule_add_alt(rule, new_alt);
794 
	}
 772 
	}
795 
    }
 773 
    }
796 
}
 774 
}
797 
 
 775 
 
798 
static void
 776 
static void
799 
rule_left_cycle_general_case_4 PROTO_N ((new_rule_list, i, size, matrix,
 777 
rule_left_cycle_general_case_4(RuleP new_rule_list, unsigned i, unsigned size,
800 
					 table))
 - 
 
801 
			       PROTO_T (RuleP        new_rule_list X
 - 
 
802 
					unsigned     i X
 - 
 
803 
					unsigned     size X
 - 
 
804 
					MatrixEntryP matrix X
 778 
			       MatrixEntryP matrix, TableP table)
805 
					TableP       table)
 - 
 
806 
{
 779 
{
807 
    unsigned j;
 780 
    unsigned j;
808 
    RuleP    rule;
 781 
    RuleP    rule;
809 
 
 782 
 
810 
    for (rule = new_rule_list, j = 0; j < size;
 783 
    for (rule = new_rule_list, j = 0; j < size;
811 
	 rule = rule_get_next_in_reverse_dfs (rule), j ++) {
 784 
	 rule = rule_get_next_in_reverse_dfs(rule), j++) {
812 
	RuleP    inner_rule;
 785 
	RuleP    inner_rule;
813 
	unsigned k = 0;
 786 
	unsigned k = 0;
814 
 
 787 
 
815 
	if (i == j) {
 788 
	if (i == j) {
816 
	    if (types_equal_zero_tuple (rule_param (rule))) {
 789 
	    if (types_equal_zero_tuple(rule_param(rule))) {
817 
		rule_add_empty_alt (rule);
 790 
		rule_add_empty_alt(rule);
818 
	    } else {
 791 
	    } else {
819 
		AltP   new_alt  = alt_create ();
 792 
		AltP   new_alt  = alt_create();
820 
		EntryP entry    = table_add_rename (table);
 793 
		EntryP entry    = table_add_rename(table);
821 
		ItemP  new_item = item_create (entry);
 794 
		ItemP  new_item = item_create(entry);
822 
 
 795 
 
823 
		types_copy (item_param (new_item), rule_param (rule));
 796 
		types_copy(item_param(new_item), rule_param(rule));
824 
		types_copy (item_result (new_item), rule_result (rule));
 797 
		types_copy(item_result(new_item), rule_result(rule));
825 
		alt_add_item (new_alt, new_item);
 798 
		alt_add_item(new_alt, new_item);
826 
		rule_add_alt (rule, new_alt);
 799 
		rule_add_alt(rule, new_alt);
827 
	    }
 800 
	    }
828 
	}
 801 
	}
829 
	for (inner_rule = new_rule_list; inner_rule;
 802 
	for (inner_rule = new_rule_list; inner_rule;
830 
	     inner_rule = rule_get_next_in_reverse_dfs (inner_rule), k ++) {
 803 
	     inner_rule = rule_get_next_in_reverse_dfs(inner_rule), k++) {
831 
	    AltP alt;
 804 
	    AltP alt;
832 
 
 805 
 
833 
	    for (alt = matrix [k].alt; alt; alt = alt_next (alt)) {
 806 
	    for (alt = matrix[k].alt; alt; alt = alt_next(alt)) {
834 
		AltP  new_alt  = alt_duplicate (alt);
 807 
		AltP  new_alt  = alt_duplicate(alt);
835 
		ItemP new_item = item_create (rule_entry (inner_rule));
 808 
		ItemP new_item = item_create(rule_entry(inner_rule));
836 
 
 809 
 
837 
		types_copy (item_param (new_item), &(matrix [k].param));
 810 
		types_copy(item_param(new_item), &(matrix[k].param));
838 
		types_copy (item_result (new_item), rule_result (rule));
 811 
		types_copy(item_result(new_item), rule_result(rule));
839 
		alt_add_item (new_alt, new_item);
 812 
		alt_add_item(new_alt, new_item);
840 
		rule_add_alt (rule, new_alt);
 813 
		rule_add_alt(rule, new_alt);
841 
	    }
 814 
	    }
842 
	}
 815 
	}
843 
    }
 816 
    }
844 
}
 817 
}
845 
 
 818 
 
846 
static void
 819 
static void
847 
rule_left_cycle_general_case PROTO_N ((rule_list, size, table))
 820 
rule_left_cycle_general_case(RuleP rule_list, unsigned size, TableP table)
848 
			     PROTO_T (RuleP    rule_list X
 - 
 
849 
				      unsigned size X
 - 
 
850 
				      TableP   table)
 - 
 
851 
{
 821 
{
852 
    unsigned     matrix_size = (size * size);
 822 
    unsigned     matrix_size = (size * size);
853 
    MatrixEntryP matrix      = rule_left_cycle_matrix (matrix_size);
 823 
    MatrixEntryP matrix      = rule_left_cycle_matrix(matrix_size);
854 
    VectorEntryP vector      = rule_left_cycle_vector (size);
 824 
    VectorEntryP vector      = rule_left_cycle_vector(size);
855 
    TypeTupleT   param;
 825 
    TypeTupleT   param;
856 
    TypeTupleT   result;
 826 
    TypeTupleT   result;
857 
 
 827 
 
858 
    rule_left_cycle_general_case_1 (rule_list, size, matrix, vector, table,
 828 
    rule_left_cycle_general_case_1(rule_list, size, matrix, vector, table,
859 
				    &param, &result);
 829 
				    &param, &result);
860 
    if (rule_left_cycle_general_case_2 (rule_list, size, vector)) {
 830 
    if (rule_left_cycle_general_case_2(rule_list, size, vector)) {
861 
	unsigned i = 0;
 831 
	unsigned i = 0;
862 
	RuleP    rule;
 832 
	RuleP    rule;
863 
 
 833 
 
864 
	for (rule = rule_list; rule;
 834 
	for (rule = rule_list; rule;
865 
	     rule = rule_get_next_in_reverse_dfs (rule), i ++) {
 835 
	     rule = rule_get_next_in_reverse_dfs(rule), i++) {
866 
	    RuleP new_rule_list;
 836 
	    RuleP new_rule_list;
867 
 
 837 
 
868 
	    rule_left_cycle_general_case_3 (rule, size, vector, table,
 838 
	    rule_left_cycle_general_case_3(rule, size, vector, table,
869 
					    &new_rule_list, &param, &result);
 839 
					   &new_rule_list, &param, &result);
870 
	    rule_left_cycle_general_case_4 (new_rule_list, i, size, matrix,
 840 
	    rule_left_cycle_general_case_4(new_rule_list, i, size, matrix,
871 
					    table);
 841 
					   table);
872 
	}
 842 
	}
873 
    }
 843 
    }
874 
    types_destroy (&param);
 844 
    types_destroy(&param);
875 
    types_destroy (&result);
 845 
    types_destroy(&result);
876 
    rule_destroy_cycle_matrix (matrix, matrix_size);
 846 
    rule_destroy_cycle_matrix(matrix, matrix_size);
877 
    rule_destroy_cycle_vector (vector, size);
 847 
    rule_destroy_cycle_vector(vector, size);
878 
}
 848 
}
879 
 
 849 
 
880 
/*--------------------------------------------------------------------------*/
 850 
/*--------------------------------------------------------------------------*/
881 
 
 851 
 
882 
void
 852 
void
883 
rule_remove_left_cycle PROTO_N ((rule_list, predicate_id, table))
 853 
rule_remove_left_cycle(RuleP rule_list, EntryP predicate_id, TableP table)
884 
		       PROTO_T (RuleP  rule_list X
 - 
 
885 
				EntryP predicate_id X
 - 
 
886 
				TableP table)
 - 
 
887 
{
 854 
{
888 
    unsigned size      = 0;
 855 
    unsigned size      = 0;
889 
    unsigned real_size = 0;
 856 
    unsigned real_size = 0;
890 
    RuleP    rule;
 857 
    RuleP    rule;
891 
 
 858 
 
892 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs (rule)) {
 859 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
893 
	size ++;
 860 
	size++;
894 
	if (key_is_string (entry_key (rule_entry (rule)))) {
 861 
	if (key_is_string(entry_key(rule_entry(rule)))) {
895 
	    real_size ++;
 862 
	    real_size++;
896 
	}
 863 
	}
897 
	rule_set_cycle_index (rule, size);
 864 
	rule_set_cycle_index(rule, size);
898 
    }
 865 
    }
899 
    if (((size != 1) || (!rule_left_cycle_special_case (rule_list, table))) &&
 866 
    if (((size != 1) || (!rule_left_cycle_special_case(rule_list, table))) &&
900 
	(rule_check_cycle_types (rule_list, predicate_id, real_size, table))) {
 867 
	(rule_check_cycle_types(rule_list, predicate_id, real_size, table))) {
901 
	rule_left_cycle_general_case (rule_list, size, table);
 868 
	rule_left_cycle_general_case(rule_list, size, table);
902 
    }
 869 
    }
903 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs (rule)) {
 870 
    for (rule = rule_list; rule; rule = rule_get_next_in_reverse_dfs(rule)) {
904 
	rule_reset_cycle_index (rule);
 871 
	rule_reset_cycle_index(rule);
905 
	rule_no_cycles (rule);
 872 
	rule_no_cycles(rule);
906 
    }
 873 
    }
907 
}
 874 
}
908
875
909 
/*
 876 
/*
910 
 * Local variables(smf):
 877 
 * Local variables(smf):