src/state.c

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

   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 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->state_list = 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;
}

state *
state_new_isocore (state const *s)
{
  state *res;
  size_t items_size = s->nitems * sizeof *s->items;

  aver (nstates < STATE_NUMBER_MAXIMUM);

  res = xmalloc (offsetof (state, items) + items_size);
  res->number = nstates++;
  res->accessing_symbol = s->accessing_symbol;
  res->transitions =
    transitions_new (s->transitions->num, s->transitions->states);
  res->reductions = reductions_new (s->reductions->num, s->reductions->rules);
  res->errs = NULL;
  res->state_list = NULL;
  res->consistent = s->consistent;
  res->solved_conflicts = NULL;
  res->solved_conflicts_xml = NULL;

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

  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)
{
  if (!hash_insert (state_table, s))
    xalloc_die ();
}


/*------------------------------------------------------------------.
| 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, 2009 Free
	4	Software 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->state_list = NULL;
	146	res->consistent = 0;
	147	res->solved_conflicts = NULL;
	148	res->solved_conflicts_xml = NULL;
	149
	150	res->nitems = nitems;
	151	memcpy (res->items, core, items_size);
	152
	153	state_hash_insert (res);
	154
	155	return res;
	156	}
	157
	158	state *
	159	state_new_isocore (state const *s)
	160	{
	161	state *res;
	162	size_t items_size = s->nitems * sizeof *s->items;
	163
	164	aver (nstates < STATE_NUMBER_MAXIMUM);
	165
	166	res = xmalloc (offsetof (state, items) + items_size);
	167	res->number = nstates++;
	168	res->accessing_symbol = s->accessing_symbol;
	169	res->transitions =
	170	transitions_new (s->transitions->num, s->transitions->states);
	171	res->reductions = reductions_new (s->reductions->num, s->reductions->rules);
	172	res->errs = NULL;
	173	res->state_list = NULL;
	174	res->consistent = s->consistent;
	175	res->solved_conflicts = NULL;
	176	res->solved_conflicts_xml = NULL;
	177
	178	res->nitems = s->nitems;
	179	memcpy (res->items, s->items, items_size);
	180
	181	return res;
	182	}
	183
	184
	185	/*---------.
	186	\| Free S. \|
	187	`---------*/
	188
	189	static void
	190	state_free (state *s)
	191	{
	192	free (s->transitions);
	193	free (s->reductions);
	194	free (s->errs);
	195	free (s);
	196	}
	197
	198
	199	/*---------------------------.
	200	\| Set the transitions of S. \|
	201	`---------------------------*/
	202
	203	void
	204	state_transitions_set (state s, int num, state *trans)
	205	{
	206	aver (!s->transitions);
	207	s->transitions = transitions_new (num, trans);
	208	}
	209
	210
	211	/*--------------------------.
	212	\| Set the reductions of S. \|
	213	`--------------------------*/
	214
	215	void
	216	state_reductions_set (state s, int num, rule *reds)
	217	{
	218	aver (!s->reductions);
	219	s->reductions = reductions_new (num, reds);
	220	}
	221
	222
	223	int
	224	state_reduction_find (state s, rule r)
	225	{
	226	int i;
	227	reductions *reds = s->reductions;
	228	for (i = 0; i < reds->num; ++i)
	229	if (reds->rules[i] == r)
	230	return i;
	231	return -1;
	232	}
	233
	234
	235	/*--------------------.
	236	\| Set the errs of S. \|
	237	`--------------------*/
	238
	239	void
	240	state_errs_set (state s, int num, symbol *tokens)
	241	{
	242	aver (!s->errs);
	243	s->errs = errs_new (num, tokens);
	244	}
	245
	246
	247
	248	/*--------------------------------------------------.
	249	\| Print on OUT all the lookahead tokens such that S \|
	250	\| wants to reduce R. \|
	251	`--------------------------------------------------*/
	252
	253	void
	254	state_rule_lookahead_tokens_print (state s, rule r, FILE *out)
	255	{
	256	/* Find the reduction we are handling. */
	257	reductions *reds = s->reductions;
	258	int red = state_reduction_find (s, r);
	259
	260	/* Print them if there are. */
	261	if (reds->lookahead_tokens && red != -1)
	262	{
	263	bitset_iterator biter;
	264	int k;
	265	char const *sep = "";
	266	fprintf (out, " [");
	267	BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	268	{
	269	fprintf (out, "%s%s", sep, symbols[k]->tag);
	270	sep = ", ";
	271	}
	272	fprintf (out, "]");
	273	}
	274	}
	275
	276	void
	277	state_rule_lookahead_tokens_print_xml (state s, rule r,
	278	FILE *out, int level)
	279	{
	280	/* Find the reduction we are handling. */
	281	reductions *reds = s->reductions;
	282	int red = state_reduction_find (s, r);
	283
	284	/* Print them if there are. */
	285	if (reds->lookahead_tokens && red != -1)
	286	{
	287	bitset_iterator biter;
	288	int k;
	289	xml_puts (out, level, "<lookaheads>");
	290	BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0)
	291	{
	292	xml_printf (out, level + 1, "<symbol>%s</symbol>",
	293	xml_escape (symbols[k]->tag));
	294	}
	295	xml_puts (out, level, "</lookaheads>");
	296	}
	297	}
	298
	299
	300	/*---------------------.
	301	\| A state hash table. \|
	302	`---------------------*/
	303
	304	/* Initial capacity of states hash table. */
	305	#define HT_INITIAL_CAPACITY 257
	306
	307	static struct hash_table *state_table = NULL;
	308
	309	/* Two states are equal if they have the same core items. */
	310	static inline bool
	311	state_compare (state const s1, state const s2)
	312	{
	313	size_t i;
	314
	315	if (s1->nitems != s2->nitems)
	316	return false;
	317
	318	for (i = 0; i < s1->nitems; ++i)
	319	if (s1->items[i] != s2->items[i])
	320	return false;
	321
	322	return true;
	323	}
	324
	325	static bool
	326	state_comparator (void const s1, void const s2)
	327	{
	328	return state_compare (s1, s2);
	329	}
	330
	331	static inline size_t
	332	state_hash (state const *s, size_t tablesize)
	333	{
	334	/* Add up the state's item numbers to get a hash key. */
	335	size_t key = 0;
	336	size_t i;
	337	for (i = 0; i < s->nitems; ++i)
	338	key += s->items[i];
	339	return key % tablesize;
	340	}
	341
	342	static size_t
	343	state_hasher (void const *s, size_t tablesize)
	344	{
	345	return state_hash (s, tablesize);
	346	}
	347
	348
	349	/*-------------------------------.
	350	\| Create the states hash table. \|
	351	`-------------------------------*/
	352
	353	void
	354	state_hash_new (void)
	355	{
	356	state_table = hash_initialize (HT_INITIAL_CAPACITY,
	357	NULL,
	358	state_hasher,
	359	state_comparator,
	360	NULL);
	361	}
	362
	363
	364	/*---------------------------------------------.
	365	\| Free the states hash table, not the states. \|
	366	`---------------------------------------------*/
	367
	368	void
	369	state_hash_free (void)
	370	{
	371	hash_free (state_table);
	372	}
	373
	374
	375	/*-----------------------------------.
	376	\| Insert S in the state hash table. \|
	377	`-----------------------------------*/
	378
	379	void
	380	state_hash_insert (state *s)
	381	{
	382	if (!hash_insert (state_table, s))
	383	xalloc_die ();
	384	}
	385
	386
	387	/*------------------------------------------------------------------.
	388	\| Find the state associated to the CORE, and return it. If it does \|
	389	\| not exist yet, return NULL. \|
	390	`------------------------------------------------------------------*/
	391
	392	state *
	393	state_hash_lookup (size_t nitems, item_number *core)
	394	{
	395	size_t items_size = nitems * sizeof *core;
	396	state *probe = xmalloc (offsetof (state, items) + items_size);
	397	state *entry;
	398
	399	probe->nitems = nitems;
	400	memcpy (probe->items, core, items_size);
	401	entry = hash_lookup (state_table, probe);
	402	free (probe);
	403	return entry;
	404	}
	405
	406
	407	/*--------------------------------------------------------.
	408	\| Record S and all states reachable from S in REACHABLE. \|
	409	`--------------------------------------------------------*/
	410
	411	static void
	412	state_record_reachable_states (state *s, bitset reachable)
	413	{
	414	if (bitset_test (reachable, s->number))
	415	return;
	416	bitset_set (reachable, s->number);
	417	{
	418	int i;
	419	for (i = 0; i < s->transitions->num; ++i)
	420	if (!TRANSITION_IS_DISABLED (s->transitions, i))
	421	state_record_reachable_states (s->transitions->states[i], reachable);
	422	}
	423	}
	424
	425	void
	426	state_remove_unreachable_states (state_number old_to_new[])
	427	{
	428	state_number nstates_reachable = 0;
	429	bitset reachable = bitset_create (nstates, BITSET_FIXED);
	430	state_record_reachable_states (states[0], reachable);
	431	{
	432	state_number i;
	433	for (i = 0; i < nstates; ++i)
	434	{
	435	if (bitset_test (reachable, states[i]->number))
	436	{
	437	states[nstates_reachable] = states[i];
	438	states[nstates_reachable]->number = nstates_reachable;
	439	old_to_new[i] = nstates_reachable++;
	440	}
	441	else
	442	{
	443	state_free (states[i]);
	444	old_to_new[i] = nstates;
	445	}
	446	}
	447	}
	448	nstates = nstates_reachable;
	449	bitset_free (reachable);
	450	}
	451
	452	/* All the decorated states, indexed by the state number. */
	453	state **states = NULL;
	454
	455
	456	/*----------------------.
	457	\| Free all the states. \|
	458	`----------------------*/
	459
	460	void
	461	states_free (void)
	462	{
	463	state_number i;
	464	for (i = 0; i < nstates; ++i)
	465	state_free (states[i]);
	466	free (states);
	467	}