Rev 6 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* 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.h --- Rule ADT.
*
** Author: Steve Folkes <smf@hermes.mod.uk>
*
*** Commentary:
*
* This file specifies the interface to the SID rule, alternative and item
* handling routines. The actual implementations are spread across a number
* of files, but are all logically part of the same file. See the files named
* in the declarations for more information.
*
*** Change Log:
* $Log: rule.h,v $
* Revision 1.1.1.1 1998/01/17 15:57:46 release
* First version to be checked into rolling release.
*
* Revision 1.3 1994/12/15 09:58:58 smf
* Brought into line with OSSG C Coding Standards Document, as per
* "CR94_178.sid+tld-update".
*
* Revision 1.2 1994/08/22 09:37:29 smf
* Fixed bug DR114:ids-too-long.
*
* Revision 1.1.1.1 1994/07/25 16:04:42 smf
* Initial import of SID 1.8 non shared files.
*
**/
/****************************************************************************/
#ifndef H_RULE
#define H_RULE
#include "os-interface.h"
#include "bitvec.h"
#include "dalloc.h"
#include "entry.h"
#include "entry-list.h"
#include "non-local.h"
#include "ostream.h"
#include "rstack.h"
#include "table.h"
#include "types.h"
/*--------------------------------------------------------------------------*/
#ifdef FS_NO_ENUM
typedef int DFSStateT, *DFSStateP;
#define DFS_UNTRACED (0)
#define DFS_TRACING (1)
#define DFS_CYCLING (2)
#define DFS_TRACED (3)
#else
typedef enum {
DFS_UNTRACED,
DFS_TRACING,
DFS_CYCLING,
DFS_TRACED
} DFSStateT, *DFSStateP;
#endif /* defined (FS_NO_ENUM) */
#ifdef FS_NO_ENUM
typedef int CycleTypeT, *CycleTypeP;
#define CT_LEFT (0)
#define CT_TAIL (1)
#define CT_ALL (2)
#define CT_MUTATE (3)
#else
typedef enum {
CT_LEFT,
CT_TAIL,
CT_ALL,
CT_MUTATE
} CycleTypeT, *CycleTypeP;
#endif /* defined (FS_NO_ENUM) */
typedef struct ItemT {
struct ItemT *next;
TypeTupleT param;
TypeTupleT result;
EntryTypeT type;
EntryP entry;
BoolT inlinable;
BoolT tail_call;
} ItemT, *ItemP;
typedef struct AltT {
struct AltT *next;
TypeTupleT names;
BitVecT first_set;
ItemP item_head;
ItemP *item_tail;
} AltT, *AltP;
typedef struct RuleT {
EntryP entry;
TypeTupleT param;
TypeTupleT result;
NonLocalListT non_locals;
NStringT maximum_scope;
BoolT defined;
BoolT has_empty_alt;
BoolT required;
EntryListT reverse_list;
DFSStateT dfs_state;
struct RuleT *next_in_root_list;
struct RuleT *next_in_dfs;
struct RuleT *next_in_reverse_dfs;
BoolT no_cycles;
unsigned cycle_index;
BoolT computed_first_set;
BoolT computing_first_set;
BitVecT first_set;
EntryListT predicate_first;
BoolT see_through;
unsigned priority;
BoolT factored;
struct RuleT *tail_group;
BoolT being_inlined;
BoolT checked_for_inlining;
EntryListT call_list;
struct RuleT *next_in_table;
BitVecT follow_set;
EntryListT predicate_follow;
BoolT started_follows;
AltP see_through_alt;
BoolT needs_function;
BoolT all_basics;
SaveRStackT rstack_state;
SaveRStackT non_local_state;
BoolT being_output;
unsigned start_label;
unsigned call_count;
unsigned end_label;
BoolT used_end_label;
unsigned next_label;
unsigned handler_label;
BoolT used_handler_label;
AltP handler;
AltP alt_head;
AltP *alt_tail;
} RuleT, *RuleP;
typedef struct RuleListT {
RuleP head;
RuleP *tail;
} RuleListT, *RuleListP;
typedef struct FactorClosureT {
BitVecT bitvec1;
BitVecT bitvec2;
TableP table;
EntryP predicate_id;
} FactorClosureT, *FactorClosureP;
typedef struct SimpClosureT {
BoolT did_inline;
TableP table;
} SimpClosureT, *SimpClosureP;
typedef struct ClashListT {
struct ClashListT *next;
RuleP rule;
AltP alt;
ItemP item;
} ClashListT, *ClashListP;
/*--------------------------------------------------------------------------*/
/* Defined in "rule.c": */
extern RuleP rule_create(EntryP);
extern void rule_reinit(RuleP);
extern EntryP rule_entry(RuleP);
extern TypeTupleP rule_param(RuleP);
extern TypeTupleP rule_result(RuleP);
extern NonLocalListP rule_non_locals(RuleP);
extern NStringP rule_maximum_scope(RuleP);
extern BoolT rule_is_defined(RuleP);
extern void rule_defined(RuleP);
extern void rule_add_alt(RuleP, AltP);
extern BoolT rule_has_empty_alt(RuleP);
extern void rule_add_empty_alt(RuleP);
extern BoolT rule_has_one_alt(RuleP);
extern void rule_compute_result_intersect(RuleP);
extern void rule_compute_minimal_dataflow(RuleP, TypeTupleP);
extern BoolT rule_is_required(RuleP);
extern void rule_required(RuleP);
extern void rule_compute_reverse_list(RuleP, CycleTypeT);
extern void rule_reinit_reverse_list(RuleP);
extern EntryListP rule_reverse_list(RuleP);
extern void rule_set_dfs_state(RuleP, DFSStateT);
extern RuleP rule_next_in_root_list(RuleP);
extern void rule_build_root_list(EntryP, GenericP);
extern RuleP rule_get_next_in_dfs(RuleP);
extern void rule_compute_dfs(RuleP, CycleTypeT, RuleP *);
extern RuleP rule_get_next_in_reverse_dfs(RuleP);
extern RuleP *rule_next_in_reverse_dfs_ref(RuleP);
extern void rule_compute_reverse_dfs(RuleP, RuleP, RuleP *);
extern BoolT rule_has_no_cycles(RuleP);
extern void rule_no_cycles(RuleP);
extern unsigned rule_get_cycle_index(RuleP);
extern void rule_set_cycle_index(RuleP, unsigned);
extern void rule_reset_cycle_index(RuleP);
extern BoolT rule_has_computed_first_set(RuleP);
extern void rule_computed_first_set(RuleP);
extern BoolT rule_is_computing_first_set(RuleP);
extern void rule_computing_first_set(RuleP);
extern BitVecP rule_first_set(RuleP);
extern EntryListP rule_predicate_first(RuleP);
extern BoolT rule_is_see_through(RuleP);
extern void rule_see_through(RuleP);
extern unsigned rule_get_priority(RuleP);
extern void rule_set_priority(RuleP, unsigned);
extern BoolT rule_is_factored(RuleP);
extern void rule_factored(RuleP);
extern RuleP rule_get_tail_group(RuleP);
extern void rule_set_tail_group(RuleP, RuleP);
extern BoolT rule_is_being_inlined(RuleP);
extern void rule_being_inlined(RuleP);
extern BoolT rule_is_checked_for_inlining(RuleP);
extern void rule_checked_for_inlining(RuleP);
extern EntryListP rule_call_list(RuleP);
extern RuleP rule_get_next_in_table(RuleP);
extern RuleP *rule_get_next_in_table_ref(RuleP);
extern void rule_set_next_in_table(RuleP, RuleP);
extern BitVecP rule_follow_set(RuleP);
extern EntryListP rule_predicate_follow(RuleP);
extern BoolT rule_has_started_follows(RuleP);
extern void rule_started_follows(RuleP);
extern void rule_set_see_through_alt(RuleP, AltP);
extern AltP rule_see_through_alt(RuleP);
extern BoolT rule_needs_function(RuleP);
extern void rule_will_need_function(RuleP);
extern BoolT rule_is_all_basics(RuleP);
extern void rule_all_basics(RuleP);
extern SaveRStackP rule_rstack_state(RuleP);
extern SaveRStackP rule_non_local_state(RuleP);
extern BoolT rule_is_being_output(RuleP);
extern void rule_being_output(RuleP);
extern void rule_not_being_output(RuleP);
extern unsigned rule_get_start_label(RuleP);
extern void rule_set_start_label(RuleP, unsigned);
extern unsigned rule_get_call_count(RuleP);
extern void rule_inc_call_count(RuleP);
extern unsigned rule_get_end_label(RuleP);
extern void rule_set_end_label(RuleP, unsigned);
extern BoolT rule_used_end_label(RuleP);
extern unsigned rule_get_next_label(RuleP);
extern void rule_set_next_label(RuleP, unsigned);
extern unsigned rule_get_handler_label(RuleP);
extern void rule_set_handler_label(RuleP, unsigned);
extern BoolT rule_used_handler_label(RuleP);
extern AltP rule_get_handler(RuleP);
extern void rule_set_handler(RuleP, AltP);
extern AltP rule_alt_head(RuleP);
extern void rule_renumber(RuleP, BoolT, EntryP);
extern void rule_iter_for_table(RuleP, BoolT,
void(*)(EntryP, GenericP),
GenericP);
extern void rule_deallocate(RuleP);
extern void write_rule_lhs(OStreamP, RuleP);
extern void write_rule(OStreamP, RuleP);
extern void rule_list_init(RuleListP);
extern void rule_list_append (RuleListP, RuleP, RuleP *);
extern void rule_list_terminate(RuleListP);
extern RuleP rule_list_head(RuleListP);
/* Defined in "rule-check.c": */
extern void rule_check_first_set(EntryP, GenericP);
extern void rule_compute_follow_set(EntryP, GenericP);
extern void rule_compute_see_through_alt(EntryP, GenericP);
extern void rule_compute_alt_first_sets(EntryP, GenericP);
extern void write_clashes(OStreamP, ClashListP);
/* Defined in "rule-error.c": */
extern void rule_compute_error_list(EntryP, GenericP);
/* Defined in "rule-factor.c": */
extern void rule_factor(EntryP, GenericP);
extern void rule_set_factor_limit(unsigned);
/* Defined in "rule-firsts.c": */
extern void rule_compute_first_set_1(RuleP);
extern void rule_compute_first_set(EntryP, GenericP);
/* Defined in "rule-lre.c": */
extern void rule_remove_left_cycle(RuleP, EntryP, TableP);
/* Defined in "rule-mutate.c": */
extern void rule_compute_mutations(EntryP, GenericP);
/* Defined in "rule-name.c": */
extern void rule_recompute_alt_names(EntryP, GenericP);
/* Defined in "rule-simp.c": */
extern void rule_remove_duplicates(TableP, EntryP);
/* Defined in "rule-tail.c": */
extern void rule_handle_tails(RuleP);
extern void rule_compute_all_basics(EntryP, GenericP);
extern void rule_compute_inlining(EntryP, GenericP);
extern void rule_compute_needed_functions(EntryP, GenericP);
extern void rule_handle_need_functions(RuleP);
extern BoolT rule_get_inline_tail_calls(void);
extern void rule_set_inline_tail_calls(BoolT);
extern void rule_set_inline_all_basics(BoolT);
extern void rule_set_inline_singles(BoolT);
extern void rule_set_inline_non_tail_calls(BoolT);
extern void rule_set_multiple_inlining(BoolT);
/* Defined in "alt.c": */
extern AltP alt_create(void);
extern AltP alt_create_merge(ItemP, ItemP, TypeTransP, TableP);
extern AltP alt_duplicate(AltP);
extern BoolT alt_less_than(AltP, AltP);
extern BoolT alt_equal(AltP, AltP);
extern AltP alt_next(AltP);
extern AltP *alt_next_ref(AltP);
extern void alt_set_next(AltP, AltP);
extern TypeTupleP alt_names(AltP);
extern BitVecP alt_first_set(AltP);
extern ItemP alt_item_head(AltP);
extern ItemP alt_unlink_item_head(AltP);
extern void alt_add_item(AltP, ItemP);
extern AltP alt_deallocate(AltP);
extern void write_alt(OStreamP, AltP);
extern void write_alt_highlighting(OStreamP, AltP, ItemP);
/* Defined in "item.c": */
extern ItemP item_create(EntryP);
extern ItemP item_duplicate(ItemP);
extern ItemP item_duplicate_and_translate(ItemP, TypeTransP, TableP);
extern void item_translate_list(ItemP, TypeBTransP);
extern void item_to_predicate(ItemP);
extern ItemP item_next (ItemP);
extern ItemP *item_next_ref(ItemP);
extern void item_set_next(ItemP, ItemP);
extern EntryP item_entry(ItemP);
extern void item_set_entry(ItemP, EntryP);
extern EntryTypeT item_type(ItemP);
extern BoolT item_is_rule(ItemP);
extern BoolT item_is_action(ItemP);
extern BoolT item_is_predicate(ItemP);
extern BoolT item_is_basic(ItemP);
extern BoolT item_is_rename(ItemP);
extern TypeTupleP item_param(ItemP);
extern void item_add_param(ItemP, TypeTupleP);
extern TypeTupleP item_result(ItemP);
extern void item_add_result(ItemP, TypeTupleP);
extern BoolT item_is_inlinable(ItemP);
extern void item_inlinable(ItemP);
extern BoolT item_is_tail_call(ItemP);
extern void item_tail_call(ItemP);
extern BoolT item_names_used_in_list(ItemP, TypeTupleP);
extern void item_compute_minimal_dataflow(ItemP, TypeTupleP);
extern ItemP item_deallocate(ItemP);
extern void write_item(OStreamP, ItemP);
/*--------------------------------------------------------------------------*/
#ifdef FS_FAST
#define rule_entry(r) ((r)->entry)
#define rule_param(r) (&((r)->param))
#define rule_result(r) (&((r)->result))
#define rule_non_locals(r) (&((r)->non_locals))
#define rule_maximum_scope(r) (&((r)->maximum_scope))
#define rule_is_defined(r) ((r)->defined)
#define rule_defined(r) ((r)->defined = TRUE)
#define rule_has_empty_alt(r) ((r)->has_empty_alt)
#define rule_add_empty_alt(r) ((r)->has_empty_alt = TRUE)
#define rule_is_required(r) ((r)->required)
#define rule_required(r) ((r)->required = TRUE)
#define rule_reverse_list(r) (&((r)->reverse_list))
#define rule_set_dfs_state(r, s) ((r)->dfs_state = (s))
#define rule_next_in_root_list(r) ((r)->next_in_root_list)
#define rule_get_next_in_dfs(r) ((r)->next_in_dfs)
#define rule_get_next_in_reverse_dfs(r) ((r)->next_in_reverse_dfs)
#define rule_next_in_reverse_dfs_ref(r) (&((r)->next_in_reverse_dfs))
#define rule_has_no_cycles(r) ((r)->no_cycles)
#define rule_no_cycles(r) ((r)->no_cycles = TRUE)
#define rule_get_cycle_index(r) ((r)->cycle_index)
#define rule_set_cycle_index(r, i) ((r)->cycle_index = (i))
#define rule_reset_cycle_index(r) ((r)->cycle_index = 0)
#define rule_has_computed_first_set(r) ((r)->computed_first_set)
#define rule_computed_first_set(r) ((r)->computed_first_set = TRUE)
#define rule_is_computing_first_set(r) ((r)->computing_first_set)
#define rule_computing_first_set(r) ((r)->computing_first_set = TRUE)
#define rule_first_set(r) (&((r)->first_set))
#define rule_predicate_first(r) (&((r)->predicate_first))
#define rule_is_see_through(r) ((r)->see_through)
#define rule_see_through(r) ((r)->see_through = TRUE)
#define rule_get_priority(r) ((r)->priority)
#define rule_set_priority(r, p) ((r)->priority = (p))
#define rule_is_factored(r) ((r)->factored)
#define rule_factored(r) ((r)->factored = TRUE)
#define rule_get_tail_group(r) ((r)->tail_group)
#define rule_set_tail_group(r1, r2) ((r1)->tail_group = (r2))
#define rule_is_being_inlined(r) ((r)->being_inlined)
#define rule_being_inlined(r) ((r)->being_inlined = TRUE)
#define rule_is_checked_for_inlining(r) ((r)->checked_for_inlining)
#define rule_checked_for_inlining(r) ((r)->checked_for_inlining = TRUE)
#define rule_call_list(r) (&((r)->call_list))
#define rule_get_next_in_table(r) ((r)->next_in_table)
#define rule_get_next_in_table_ref(r) (&((r)->next_in_table))
#define rule_set_next_in_table(r1, r2) ((r1)->next_in_table = (r2))
#define rule_follow_set(r) (&((r)->follow_set))
#define rule_predicate_follow(r) (&((r)->predicate_follow))
#define rule_has_started_follows(r) ((r)->started_follows)
#define rule_started_follows(r) ((r)->started_follows = TRUE)
#define rule_set_all_action_alt(r, a) ((r)->all_action_alt = (a))
#define rule_all_action_alt(r) ((r)->all_action_alt)
#define rule_needs_function(r) ((r)->needs_function)
#define rule_will_need_function(r) ((r)->needs_function = TRUE)
#define rule_is_all_basics(r) ((r)->all_basics)
#define rule_all_basics(r) ((r)->all_basics = TRUE)
#define rule_rstack_state(r) (&((r)->rstack_state))
#define rule_non_local_state(r) (&((r)->non_local_state))
#define rule_is_being_output(r) ((r)->being_output)
#define rule_being_output(r) ((r)->being_output = TRUE)
#define rule_not_being_output(r) ((r)->being_output = FALSE)
#define rule_get_start_label(r) ((r)->start_label)
#define rule_set_start_label(r, l) ((r)->start_label = (l))
#define rule_get_call_count(r) ((r)->call_count)
#define rule_inc_call_count(r) ((r)->call_count++)
#define rule_used_end_label(r) ((r)->used_end_label)
#define rule_get_next_label(r) ((r)->next_label)
#define rule_set_next_label(r, l) ((r)->next_label = (l))
#define rule_used_handler_label(r) ((r)->used_handler_label)
#define rule_get_handler(r) ((r)->handler)
#define rule_set_handler(r, a) ((r)->handler = (a))
#define rule_alt_head(r) ((r)->alt_head)
#define rule_list_terminate(r) ((*((r)->tail)) = NIL(RuleP))
#define rule_list_head(r) ((r)->head)
#define alt_next(a) ((a)->next)
#define alt_next_ref(a) (&((a)->next))
#define alt_set_next(a1, a2) ((a1)->next = (a2))
#define alt_names(a) (&((a)->names))
#define alt_first_set(a) (&((a)->first_set))
#define alt_item_head(a) ((a)->item_head)
#define item_next(i) ((i)->next)
#define item_next_ref(i) (&((i)->next))
#define item_set_next(i1, i2) ((i1)->next = (i2))
#define item_entry(i) ((i)->entry)
#define item_set_entry(i, e) ((i)->entry = (e))
#define item_type(i) ((i)->type)
#define item_is_rule(i) ((i)->type == ET_RULE)
#define item_is_action(i) ((i)->type == ET_ACTION)
#define item_is_predicate(i) ((i)->type == ET_PREDICATE)
#define item_is_basic(i) ((i)->type == ET_BASIC)
#define item_is_rename(i) ((i)->type == ET_RENAME)
#define item_param(i) (&((i)->param))
#define item_add_param(i, t) (types_assign(&((i)->param), (t)))
#define item_result(i) (&((i)->result))
#define item_add_result(i, t) (types_assign(&((i)->result), (t)))
#define item_is_inlinable(i) ((i)->inlinable)
#define item_inlinable(i) ((i)->inlinable = TRUE)
#define item_is_tail_call(i) ((i)->tail_call)
#define item_tail_call(i) ((i)->tail_call = TRUE)
#endif /* defined (FS_FAST) */
#endif /* !defined (H_RULE) */
/*
* Local variables(smf):
* eval: (include::add-path-entry "../os-interface" "../library")
* eval: (include::add-path-entry "../generated")
* end:
**/