src/state.c

/* Type definitions for nondeterministic finite state machine for Bison.

   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
   Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include <config.h>
#include "system.h"

#include <hash.h>

#include "complain.h"
#include "gram.h"
#include "state.h"
#include "print-xml.h"


			/*-------------------.
			| Shifts and Gotos.  |
			`-------------------*/


/*-----------------------------------------.
| Create a new array of NUM shifts/gotos.  |
`-----------------------------------------*/

static transitions *
transitions_new (int num, state **the_states)
{
  size_t states_size = num * sizeof *the_states;
  transitions *res = xmalloc (offsetof (transitions, states) + states_size);
  res->num = num;
  memcpy (res->states, the_states, states_size);
  return res;
}


/*-------------------------------------------------------.
| Return the state such that SHIFTS contain a shift/goto |
| to it on SYM.  Abort if none found.                    |
`-------------------------------------------------------*/

state *
transitions_to (transitions *shifts, symbol_number sym)
{
  int j;
  for (j = 0; ; j++)
    {
      aver (j < shifts->num);
      if (TRANSITION_SYMBOL (shifts, j) == sym)
	return shifts->states[j];
    }
}


			/*--------------------.
			| Error transitions.  |
			`--------------------*/


/*---------------------------------.
| Create a new array of NUM errs.  |
`---------------------------------*/

errs *
errs_new (int num, symbol **tokens)
{
  size_t symbols_size = num * sizeof *tokens;
  errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
  res->num = num;
  memcpy (res->symbols, tokens, symbols_size);
  return res;
}


			/*-------------.
			| Reductions.  |
			`-------------*/


/*---------------------------------------.
| Create a new array of NUM reductions.  |
`---------------------------------------*/

static reductions *
reductions_new (int num, rule **reds)
{
  size_t rules_size = num * sizeof *reds;
  reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
  res->num = num;
  res->lookahead_tokens = NULL;
  memcpy (res->rules, reds, rules_size);
  return res;
}


			/*---------.
			| States.  |
			`---------*/


state_number nstates = 0;
/* FINAL_STATE is properly set by new_state when it recognizes its
   accessing symbol: $end.  */
state *final_state = NULL;


/*------------------------------------------------------------------.
| Create a new state with ACCESSING_SYMBOL, for those items.  Store |
| it in the state hash table.                                       |
`------------------------------------------------------------------*/

state *
state_new (symbol_number accessing_symbol,
	   size_t nitems, item_number *core)
{
  state *res;
  size_t items_size = nitems * sizeof *core;

  aver (nstates < STATE_NUMBER_MAXIMUM);

  res = xmalloc (offsetof (state, items) + items_size);
  res->number = nstates++;
  res->accessing_symbol = accessing_symbol;
  res->transitions = NULL;
  res->reductions = NULL;
  res->errs = NULL;
  res->consistent = 0;
  res->solved_conflicts = NULL;
  res->solved_conflicts_xml = NULL;

  res->nitems = nitems;
  memcpy (res->items, core, items_size);

  state_hash_insert (res);

  return res;
}


/*---------.
| Free S.  |
`---------*/

static void
state_free (state *s)
{
  free (s->transitions);
  free (s->reductions);
  free (s->errs);
  free (s);
}


/*---------------------------.
| Set the transitions of S.  |
`---------------------------*/

void
state_transitions_set (state *s, int num, state **trans)
{
  aver (!s->transitions);
  s->transitions = transitions_new (num, trans);
}


/*--------------------------.
| Set the reductions of S.  |
`--------------------------*/

void
state_reductions_set (state *s, int num, rule **reds)
{
  aver (!s->reductions);
  s->reductions = reductions_new (num, reds);
}


int
state_reduction_find (state *s, rule *r)
{
  int i;
  reductions *reds = s->reductions;
  for (i = 0; i < reds->num; ++i)
    if (reds->rules[i] == r)
      return i;
  return -1;
}


/*--------------------.
| Set the errs of S.  |
`--------------------*/

void
state_errs_set (state *s, int num, symbol **tokens)
{
  aver (!s->errs);
  s->errs = errs_new (num, tokens);
}


/*--------------------------------------------------.
| Print on OUT all the lookahead tokens such that S |
| wants to reduce R.                                |
`--------------------------------------------------*/

void
state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out)
{
  /* Find the reduction we are handling.  */
  reductions *reds = s->reductions;
  int red = state_reduction_find (s, r);

  /* Print them if there are.  */
  if (reds->lookahead_tokens && red != -1)
    {
      bitset_iterator biter;
      int k;
      char const *sep = "";
      fprintf (out, "  [");
      BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	{
	  fprintf (out, "%s%s", sep, symbols[k]->tag);
	  sep = ", ";
	}
      fprintf (out, "]");
    }
}

void
state_rule_lookahead_tokens_print_xml (state *s, rule *r,
				       FILE *out, int level)
{
  /* Find the reduction we are handling.  */
  reductions *reds = s->reductions;
  int red = state_reduction_find (s, r);

  /* Print them if there are.  */
  if (reds->lookahead_tokens && red != -1)
    {
      bitset_iterator biter;
      int k;
      xml_puts (out, level, "<lookaheads>");
      BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	{
	  xml_printf (out, level + 1, "<symbol>%s</symbol>",
		      xml_escape (symbols[k]->tag));
	}
      xml_puts (out, level, "</lookaheads>");
    }
}


/*---------------------.
| A state hash table.  |
`---------------------*/

/* Initial capacity of states hash table.  */
#define HT_INITIAL_CAPACITY 257

static struct hash_table *state_table = NULL;

/* Two states are equal if they have the same core items.  */
static inline bool
state_compare (state const *s1, state const *s2)
{
  size_t i;

  if (s1->nitems != s2->nitems)
    return false;

  for (i = 0; i < s1->nitems; ++i)
    if (s1->items[i] != s2->items[i])
      return false;

  return true;
}

static bool
state_comparator (void const *s1, void const *s2)
{
  return state_compare (s1, s2);
}

static inline size_t
state_hash (state const *s, size_t tablesize)
{
  /* Add up the state's item numbers to get a hash key.  */
  size_t key = 0;
  size_t i;
  for (i = 0; i < s->nitems; ++i)
    key += s->items[i];
  return key % tablesize;
}

static size_t
state_hasher (void const *s, size_t tablesize)
{
  return state_hash (s, tablesize);
}


/*-------------------------------.
| Create the states hash table.  |
`-------------------------------*/

void
state_hash_new (void)
{
  state_table = hash_initialize (HT_INITIAL_CAPACITY,
				 NULL,
				 state_hasher,
				 state_comparator,
				 NULL);
}


/*---------------------------------------------.
| Free the states hash table, not the states.  |
`---------------------------------------------*/

void
state_hash_free (void)
{
  hash_free (state_table);
}


/*-----------------------------------.
| Insert S in the state hash table.  |
`-----------------------------------*/

void
state_hash_insert (state *s)
{
  hash_insert (state_table, s);
}


/*------------------------------------------------------------------.
| Find the state associated to the CORE, and return it.  If it does |
| not exist yet, return NULL.                                       |
`------------------------------------------------------------------*/

state *
state_hash_lookup (size_t nitems, item_number *core)
{
  size_t items_size = nitems * sizeof *core;
  state *probe = xmalloc (offsetof (state, items) + items_size);
  state *entry;

  probe->nitems = nitems;
  memcpy (probe->items, core, items_size);
  entry = hash_lookup (state_table, probe);
  free (probe);
  return entry;
}


/*--------------------------------------------------------.
| Record S and all states reachable from S in REACHABLE.  |
`--------------------------------------------------------*/

static void
state_record_reachable_states (state *s, bitset reachable)
{
  if (bitset_test (reachable, s->number))
    return;
  bitset_set (reachable, s->number);
  {
    int i;
    for (i = 0; i < s->transitions->num; ++i)
      if (!TRANSITION_IS_DISABLED (s->transitions, i))
        state_record_reachable_states (s->transitions->states[i], reachable);
  }
}

void
state_remove_unreachable_states (state_number old_to_new[])
{
  state_number nstates_reachable = 0;
  bitset reachable = bitset_create (nstates, BITSET_FIXED);
  state_record_reachable_states (states[0], reachable);
  {
    state_number i;
    for (i = 0; i < nstates; ++i)
      {
        if (bitset_test (reachable, states[i]->number))
          {
            states[nstates_reachable] = states[i];
            states[nstates_reachable]->number = nstates_reachable;
            old_to_new[i] = nstates_reachable++;
          }
        else
          {
            state_free (states[i]);
            old_to_new[i] = nstates;
          }
      }
  }
  nstates = nstates_reachable;
  bitset_free (reachable);
}

/* All the decorated states, indexed by the state number.  */
state **states = NULL;


/*----------------------.
| Free all the states.  |
`----------------------*/

void
states_free (void)
{
  state_number i;
  for (i = 0; i < nstates; ++i)
    state_free (states[i]);
  free (states);
}
Commit	Line	Data
	1	/* Type definitions for nondeterministic finite state machine for Bison.
	2
	3	Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
	4	Foundation, Inc.
	5
	6	This file is part of Bison, the GNU Compiler Compiler.
	7
	8	This program is free software: you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation, either version 3 of the License, or
	11	(at your option) any later version.
	12
	13	This program is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with this program. If not, see <http://www.gnu.org/licenses/>. */
	20
	21	#include <config.h>
	22	#include "system.h"
	23
	24	#include <hash.h>
	25
	26	#include "complain.h"
	27	#include "gram.h"
	28	#include "state.h"
	29	#include "print-xml.h"
	30
	31
	32	/*-------------------.
	33	\| Shifts and Gotos. \|
	34	`-------------------*/
	35
	36
	37	/*-----------------------------------------.
	38	\| Create a new array of NUM shifts/gotos. \|
	39	`-----------------------------------------*/
	40
	41	static transitions *
	42	transitions_new (int num, state **the_states)
	43	{
	44	size_t states_size = num * sizeof *the_states;
	45	transitions *res = xmalloc (offsetof (transitions, states) + states_size);
	46	res->num = num;
	47	memcpy (res->states, the_states, states_size);
	48	return res;
	49	}
	50
	51
	52	/*-------------------------------------------------------.
	53	\| Return the state such that SHIFTS contain a shift/goto \|
	54	\| to it on SYM. Abort if none found. \|
	55	`-------------------------------------------------------*/
	56
	57	state *
	58	transitions_to (transitions *shifts, symbol_number sym)
	59	{
	60	int j;
	61	for (j = 0; ; j++)
	62	{
	63	aver (j < shifts->num);
	64	if (TRANSITION_SYMBOL (shifts, j) == sym)
	65	return shifts->states[j];
	66	}
	67	}
	68
	69
	70	/*--------------------.
	71	\| Error transitions. \|
	72	`--------------------*/
	73
	74
	75	/*---------------------------------.
	76	\| Create a new array of NUM errs. \|
	77	`---------------------------------*/
	78
	79	errs *
	80	errs_new (int num, symbol **tokens)
	81	{
	82	size_t symbols_size = num * sizeof *tokens;
	83	errs *res = xmalloc (offsetof (errs, symbols) + symbols_size);
	84	res->num = num;
	85	memcpy (res->symbols, tokens, symbols_size);
	86	return res;
	87	}
	88
	89
	90
	91
	92	/*-------------.
	93	\| Reductions. \|
	94	`-------------*/
	95
	96
	97	/*---------------------------------------.
	98	\| Create a new array of NUM reductions. \|
	99	`---------------------------------------*/
	100
	101	static reductions *
	102	reductions_new (int num, rule **reds)
	103	{
	104	size_t rules_size = num * sizeof *reds;
	105	reductions *res = xmalloc (offsetof (reductions, rules) + rules_size);
	106	res->num = num;
	107	res->lookahead_tokens = NULL;
	108	memcpy (res->rules, reds, rules_size);
	109	return res;
	110	}
	111
	112
	113
	114	/*---------.
	115	\| States. \|
	116	`---------*/
	117
	118
	119	state_number nstates = 0;
	120	/* FINAL_STATE is properly set by new_state when it recognizes its
	121	accessing symbol: $end. */
	122	state *final_state = NULL;
	123
	124
	125	/*------------------------------------------------------------------.
	126	\| Create a new state with ACCESSING_SYMBOL, for those items. Store \|
	127	\| it in the state hash table. \|
	128	`------------------------------------------------------------------*/
	129
	130	state *
	131	state_new (symbol_number accessing_symbol,
	132	size_t nitems, item_number *core)
	133	{
	134	state *res;
	135	size_t items_size = nitems * sizeof *core;
	136
	137	aver (nstates < STATE_NUMBER_MAXIMUM);
	138
	139	res = xmalloc (offsetof (state, items) + items_size);
	140	res->number = nstates++;
	141	res->accessing_symbol = accessing_symbol;
	142	res->transitions = NULL;
	143	res->reductions = NULL;
	144	res->errs = NULL;
	145	res->consistent = 0;
	146	res->solved_conflicts = NULL;
	147	res->solved_conflicts_xml = NULL;
	148
	149	res->nitems = nitems;
	150	memcpy (res->items, core, items_size);
	151
	152	state_hash_insert (res);
	153
	154	return res;
	155	}
	156
	157
	158	/*---------.
	159	\| Free S. \|
	160	`---------*/
	161
	162	static void
	163	state_free (state *s)
	164	{
	165	free (s->transitions);
	166	free (s->reductions);
	167	free (s->errs);
	168	free (s);
	169	}
	170
	171
	172	/*---------------------------.
	173	\| Set the transitions of S. \|
	174	`---------------------------*/
	175
	176	void
	177	state_transitions_set (state s, int num, state *trans)
	178	{
	179	aver (!s->transitions);
	180	s->transitions = transitions_new (num, trans);
	181	}
	182
	183
	184	/*--------------------------.
	185	\| Set the reductions of S. \|
	186	`--------------------------*/
	187
	188	void
	189	state_reductions_set (state s, int num, rule *reds)
	190	{
	191	aver (!s->reductions);
	192	s->reductions = reductions_new (num, reds);
	193	}
	194
	195
	196	int
	197	state_reduction_find (state s, rule r)
	198	{
	199	int i;
	200	reductions *reds = s->reductions;
	201	for (i = 0; i < reds->num; ++i)
	202	if (reds->rules[i] == r)
	203	return i;
	204	return -1;
	205	}
	206
	207
	208	/*--------------------.
	209	\| Set the errs of S. \|
	210	`--------------------*/
	211
	212	void
	213	state_errs_set (state s, int num, symbol *tokens)
	214	{
	215	aver (!s->errs);
	216	s->errs = errs_new (num, tokens);
	217	}
	218
	219
	220
	221	/*--------------------------------------------------.
	222	\| Print on OUT all the lookahead tokens such that S \|
	223	\| wants to reduce R. \|
	224	`--------------------------------------------------*/
	225
	226	void
	227	state_rule_lookahead_tokens_print (state s, rule r, FILE *out)
	228	{
	229	/* Find the reduction we are handling. */
	230	reductions *reds = s->reductions;
	231	int red = state_reduction_find (s, r);
	232
	233	/* Print them if there are. */
	234	if (reds->lookahead_tokens && red != -1)
	235	{
	236	bitset_iterator biter;
	237	int k;
	238	char const *sep = "";
	239	fprintf (out, " [");
	240	BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	241	{
	242	fprintf (out, "%s%s", sep, symbols[k]->tag);
	243	sep = ", ";
	244	}
	245	fprintf (out, "]");
	246	}
	247	}
	248
	249	void
	250	state_rule_lookahead_tokens_print_xml (state s, rule r,
	251	FILE *out, int level)
	252	{
	253	/* Find the reduction we are handling. */
	254	reductions *reds = s->reductions;
	255	int red = state_reduction_find (s, r);
	256
	257	/* Print them if there are. */
	258	if (reds->lookahead_tokens && red != -1)
	259	{
	260	bitset_iterator biter;
	261	int k;
	262	xml_puts (out, level, "<lookaheads>");
	263	BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	264	{
	265	xml_printf (out, level + 1, "<symbol>%s</symbol>",
	266	xml_escape (symbols[k]->tag));
	267	}
	268	xml_puts (out, level, "</lookaheads>");
	269	}
	270	}
	271
	272
	273	/*---------------------.
	274	\| A state hash table. \|
	275	`---------------------*/
	276
	277	/* Initial capacity of states hash table. */
	278	#define HT_INITIAL_CAPACITY 257
	279
	280	static struct hash_table *state_table = NULL;
	281
	282	/* Two states are equal if they have the same core items. */
	283	static inline bool
	284	state_compare (state const s1, state const s2)
	285	{
	286	size_t i;
	287
	288	if (s1->nitems != s2->nitems)
	289	return false;
	290
	291	for (i = 0; i < s1->nitems; ++i)
	292	if (s1->items[i] != s2->items[i])
	293	return false;
	294
	295	return true;
	296	}
	297
	298	static bool
	299	state_comparator (void const s1, void const s2)
	300	{
	301	return state_compare (s1, s2);
	302	}
	303
	304	static inline size_t
	305	state_hash (state const *s, size_t tablesize)
	306	{
	307	/* Add up the state's item numbers to get a hash key. */
	308	size_t key = 0;
	309	size_t i;
	310	for (i = 0; i < s->nitems; ++i)
	311	key += s->items[i];
	312	return key % tablesize;
	313	}
	314
	315	static size_t
	316	state_hasher (void const *s, size_t tablesize)
	317	{
	318	return state_hash (s, tablesize);
	319	}
	320
	321
	322	/*-------------------------------.
	323	\| Create the states hash table. \|
	324	`-------------------------------*/
	325
	326	void
	327	state_hash_new (void)
	328	{
	329	state_table = hash_initialize (HT_INITIAL_CAPACITY,
	330	NULL,
	331	state_hasher,
	332	state_comparator,
	333	NULL);
	334	}
	335
	336
	337	/*---------------------------------------------.
	338	\| Free the states hash table, not the states. \|
	339	`---------------------------------------------*/
	340
	341	void
	342	state_hash_free (void)
	343	{
	344	hash_free (state_table);
	345	}
	346
	347
	348	/*-----------------------------------.
	349	\| Insert S in the state hash table. \|
	350	`-----------------------------------*/
	351
	352	void
	353	state_hash_insert (state *s)
	354	{
	355	hash_insert (state_table, s);
	356	}
	357
	358
	359	/*------------------------------------------------------------------.
	360	\| Find the state associated to the CORE, and return it. If it does \|
	361	\| not exist yet, return NULL. \|
	362	`------------------------------------------------------------------*/
	363
	364	state *
	365	state_hash_lookup (size_t nitems, item_number *core)
	366	{
	367	size_t items_size = nitems * sizeof *core;
	368	state *probe = xmalloc (offsetof (state, items) + items_size);
	369	state *entry;
	370
	371	probe->nitems = nitems;
	372	memcpy (probe->items, core, items_size);
	373	entry = hash_lookup (state_table, probe);
	374	free (probe);
	375	return entry;
	376	}
	377
	378
	379	/*--------------------------------------------------------.
	380	\| Record S and all states reachable from S in REACHABLE. \|
	381	`--------------------------------------------------------*/
	382
	383	static void
	384	state_record_reachable_states (state *s, bitset reachable)
	385	{
	386	if (bitset_test (reachable, s->number))
	387	return;
	388	bitset_set (reachable, s->number);
	389	{
	390	int i;
	391	for (i = 0; i < s->transitions->num; ++i)
	392	if (!TRANSITION_IS_DISABLED (s->transitions, i))
	393	state_record_reachable_states (s->transitions->states[i], reachable);
	394	}
	395	}
	396
	397	void
	398	state_remove_unreachable_states (state_number old_to_new[])
	399	{
	400	state_number nstates_reachable = 0;
	401	bitset reachable = bitset_create (nstates, BITSET_FIXED);
	402	state_record_reachable_states (states[0], reachable);
	403	{
	404	state_number i;
	405	for (i = 0; i < nstates; ++i)
	406	{
	407	if (bitset_test (reachable, states[i]->number))
	408	{
	409	states[nstates_reachable] = states[i];
	410	states[nstates_reachable]->number = nstates_reachable;
	411	old_to_new[i] = nstates_reachable++;
	412	}
	413	else
	414	{
	415	state_free (states[i]);
	416	old_to_new[i] = nstates;
	417	}
	418	}
	419	}
	420	nstates = nstates_reachable;
	421	bitset_free (reachable);
	422	}
	423
	424	/* All the decorated states, indexed by the state number. */
	425	state **states = NULL;
	426
	427
	428	/*----------------------.
	429	\| Free all the states. \|
	430	`----------------------*/
	431
	432	void
	433	states_free (void)
	434	{
	435	state_number i;
	436	for (i = 0; i < nstates; ++i)
	437	state_free (states[i]);
	438	free (states);
	439	}