src/conflicts.c

/* Find and resolve or report look-ahead conflicts for bison,

   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003
   Free Software Foundation, Inc.

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

   Bison 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 2, or (at your option)
   any later version.

   Bison 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 Bison; see the file COPYING.  If not, write to the Free
   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */

#include "system.h"

#include <bitset.h>

#include "LR0.h"
#include "complain.h"
#include "conflicts.h"
#include "files.h"
#include "getargs.h"
#include "gram.h"
#include "lalr.h"
#include "reader.h"
#include "state.h"
#include "symtab.h"

/* -1 stands for not specified. */
int expected_conflicts = -1;
static char *conflicts = NULL;
struct obstack solved_conflicts_obstack;

static bitset shiftset;
static bitset lookaheadset;

\f

enum conflict_resolution
  {
    shift_resolution,
    reduce_resolution,
    left_resolution,
    right_resolution,
    nonassoc_resolution
  };


/*----------------------------------------------------------------.
| Explain how an SR conflict between TOKEN and RULE was resolved: |
| RESOLUTION.                                                     |
`----------------------------------------------------------------*/

static inline void
log_resolution (rule *r, symbol_number token,
		enum conflict_resolution resolution)
{
  if (report_flag & report_solved_conflicts)
    {
      /* The description of the resolution. */
      switch (resolution)
	{
	case shift_resolution:
	case right_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as shift"),
			  r->number,
			  symbols[token]->tag);
	  break;
	case reduce_resolution:
	case left_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as reduce"),
			  r->number,
			  symbols[token]->tag);
	  break;
	case nonassoc_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as an error"),
			  r->number,
			  symbols[token]->tag);
	  break;
	}

      /* The reason. */
      switch (resolution)
	{
	case shift_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  r->prec->tag,
			  symbols[token]->tag);
	  break;

	case reduce_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  symbols[token]->tag,
			  r->prec->tag);
	  break;

	case left_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%left %s)",
			  symbols[token]->tag);
	  break;

	case right_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%right %s)",
			  symbols[token]->tag);
	  break;
	case nonassoc_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%nonassoc %s)",
			  symbols[token]->tag);
	  break;
	}
      obstack_sgrow (&solved_conflicts_obstack, ".\n");
    }
}


/*------------------------------------------------------------------.
| Turn off the shift recorded for the specified token in the        |
| specified state.  Used when we resolve a shift-reduce conflict in |
| favor of the reduction.                                           |
`------------------------------------------------------------------*/

static void
flush_shift (state *s, int token)
{
  transitions *trans = s->transitions;
  int i;

  bitset_reset (lookaheadset, token);
  for (i = 0; i < trans->num; i++)
    if (!TRANSITION_IS_DISABLED (trans, i)
	&& TRANSITION_SYMBOL (trans, i) == token)
      TRANSITION_DISABLE (trans, i);
}


/*-------------------------------------------------------------------.
| Turn off the reduce recorded for the specified token for the       |
| specified lookahead.  Used when we resolve a shift-reduce conflict |
| in favor of the shift.                                             |
`-------------------------------------------------------------------*/

static void
flush_reduce (bitset lookaheads, int token)
{
  bitset_reset (lookaheads, token);
}


/*------------------------------------------------------------------.
| Attempt to resolve shift-reduce conflict for one rule by means of |
| precedence declarations.  It has already been checked that the    |
| rule has a precedence.  A conflict is resolved by modifying the   |
| shift or reduce tables so that there is no longer a conflict.     |
|                                                                   |
| LOOKAHEAD is the number of the lookahead bitset to consider.      |
|                                                                   |
| ERRORS can be used to store discovered explicit errors.           |
`------------------------------------------------------------------*/

static void
resolve_sr_conflict (state *s, int ruleno, symbol **errors)
{
  symbol_number i;
  reductions *reds = s->reductions;
  /* Find the rule to reduce by to get precedence of reduction.  */
  rule *redrule = reds->rules[ruleno];
  int redprec = redrule->prec->prec;
  bitset lookaheads = reds->lookaheads[ruleno];
  int nerrs = 0;

  for (i = 0; i < ntokens; i++)
    if (bitset_test (lookaheads, i)
	&& bitset_test (lookaheadset, i)
	&& symbols[i]->prec)
      {
	/* Shift-reduce conflict occurs for token number i
	   and it has a precedence.
	   The precedence of shifting is that of token i.  */
	if (symbols[i]->prec < redprec)
	  {
	    log_resolution (redrule, i, reduce_resolution);
	    flush_shift (s, i);
	  }
	else if (symbols[i]->prec > redprec)
	  {
	    log_resolution (redrule, i, shift_resolution);
	    flush_reduce (lookaheads, i);
	  }
	else
	  /* Matching precedence levels.
	     For left association, keep only the reduction.
	     For right association, keep only the shift.
	     For nonassociation, keep neither.  */

	  switch (symbols[i]->assoc)
	    {
	    case right_assoc:
	      log_resolution (redrule, i, right_resolution);
	      flush_reduce (lookaheads, i);
	      break;

	    case left_assoc:
	      log_resolution (redrule, i, left_resolution);
	      flush_shift (s, i);
	      break;

	    case non_assoc:
	      log_resolution (redrule, i, nonassoc_resolution);
	      flush_shift (s, i);
	      flush_reduce (lookaheads, i);
	      /* Record an explicit error for this token.  */
	      errors[nerrs++] = symbols[i];
	      break;

	    case undef_assoc:
	      abort ();
	    }
      }

  if (nerrs)
    {
      /* Some tokens have been explicitly made errors.  Allocate a
	 permanent errs structure for this state, to record them.  */
      state_errs_set (s, nerrs, errors);
    }

  if (obstack_object_size (&solved_conflicts_obstack))
    {
      obstack_1grow (&solved_conflicts_obstack, '\0');
      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
    }
}


/*-------------------------------------------------------------------.
| Solve the S/R conflicts of state S using the                       |
| precedence/associativity, and flag it inconsistent if it still has |
| conflicts.  ERRORS can be used as storage to compute the list of   |
| lookaheads on which S raises a syntax error (%nonassoc).           |
`-------------------------------------------------------------------*/

static void
set_conflicts (state *s, symbol **errors)
{
  int i;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;

  if (s->consistent)
    return;

  bitset_zero (lookaheadset);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (lookaheadset, TRANSITION_SYMBOL (trans, i));

  /* Loop over all rules which require lookahead in this state.  First
     check for shift-reduce conflict, and try to resolve using
     precedence.  */
  for (i = 0; i < reds->num; ++i)
    if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	&& !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
      resolve_sr_conflict (s, i, errors);

  /* Loop over all rules which require lookahead in this state.  Check
     for conflicts not resolved above.  */
  for (i = 0; i < reds->num; ++i)
    {
      if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
	conflicts[s->number] = 1;

      bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
    }
}


/*----------------------------------------------------------------.
| Solve all the S/R conflicts using the precedence/associativity, |
| and flag as inconsistent the states that still have conflicts.  |
`----------------------------------------------------------------*/

void
conflicts_solve (void)
{
  state_number i;
  /* List of lookaheads on which we explicitly raise a syntax error.  */
  symbol **errors = MALLOC (errors, ntokens + 1);

  CALLOC (conflicts, nstates);
  shiftset = bitset_create (ntokens, BITSET_FIXED);
  lookaheadset = bitset_create (ntokens, BITSET_FIXED);
  obstack_init (&solved_conflicts_obstack);

  for (i = 0; i < nstates; i++)
    {
      set_conflicts (states[i], errors);

      /* For uniformity of the code, make sure all the states have a valid
	 `errs' member.  */
      if (!states[i]->errs)
	states[i]->errs = errs_new (0, 0);
    }

  free (errors);
}


/*---------------------------------------------.
| Count the number of shift/reduce conflicts.  |
`---------------------------------------------*/

static int
count_sr_conflicts (state *s)
{
  int i;
  int src_count = 0;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;

  if (!trans)
    return 0;

  bitset_zero (lookaheadset);
  bitset_zero (shiftset);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));

  for (i = 0; i < reds->num; ++i)
    bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);

  bitset_and (lookaheadset, lookaheadset, shiftset);

  src_count = bitset_count (lookaheadset);

  return src_count;
}


/*----------------------------------------------------------------.
| Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
| count one conflict for each token that has any reduce/reduce    |
| conflicts.  Otherwise, count one conflict for each pair of      |
| conflicting reductions.                                         |
+`----------------------------------------------------------------*/

static int
count_rr_conflicts (state *s, bool one_per_token)
{
  int i;
  reductions *reds = s->reductions;
  int rrc_count = 0;

  for (i = 0; i < ntokens; i++)
    {
      int count = 0;
      int j;
      for (j = 0; j < reds->num; ++j)
	if (bitset_test (reds->lookaheads[j], i))
	  count++;

      if (count >= 2)
	rrc_count += one_per_token ? 1 : count-1;
    }

  return rrc_count;
}


/*--------------------------------------------------------.
| Report the number of conflicts, using the Yacc format.  |
`--------------------------------------------------------*/

static void
conflict_report (FILE *out, int src_num, int rrc_num)
{
  if (src_num && rrc_num)
    fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	     src_num, rrc_num);
  else if (src_num)
    fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
  else if (rrc_num)
    fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
}


/*-----------------------------------------------------------.
| Output the detailed description of states with conflicts.  |
`-----------------------------------------------------------*/

void
conflicts_output (FILE *out)
{
  bool printed_sth = false;
  state_number i;
  for (i = 0; i < nstates; i++)
    {
      state *s = states[i];
      if (conflicts[i])
	{
	  fprintf (out, _("State %d "), i);
	  conflict_report (out, count_sr_conflicts (s),
			   count_rr_conflicts (s, true));
	  printed_sth = true;
	}
    }
  if (printed_sth)
    fputs ("\n\n", out);
}

/*--------------------------------------------------------.
| Total the number of S/R and R/R conflicts.  Unlike the  |
| code in conflicts_output, however, count EACH pair of   |
| reductions for the same state and lookahead as one      |
| conflict.						  |
`--------------------------------------------------------*/

int
conflicts_total_count (void)
{
  state_number i;
  int count;

  /* Conflicts by state.  */
  count = 0;
  for (i = 0; i < nstates; i++)
    if (conflicts[i])
      {
	count += count_sr_conflicts (states[i]);
	count += count_rr_conflicts (states[i], false);
      }
  return count;
}


/*------------------------------------------.
| Reporting the total number of conflicts.  |
`------------------------------------------*/

void
conflicts_print (void)
{
  /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
     not set, and then we want 0 SR, or else it is specified, in which
     case we want equality.  */
  bool src_ok = false;

  int src_total = 0;
  int rrc_total = 0;

  /* Conflicts by state.  */
  {
    state_number i;

    for (i = 0; i < nstates; i++)
      if (conflicts[i])
	{
	  src_total += count_sr_conflicts (states[i]);
	  rrc_total += count_rr_conflicts (states[i], true);
	}
  }

  src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);

  /* If there are no RR conflicts, and as many SR conflicts as
     expected, then there is nothing to report.  */
  if (!rrc_total && src_ok)
    return;

  /* Report the total number of conflicts on STDERR.  */
  if (! yacc_flag)
    fprintf (stderr, "%s: ", current_file);
  conflict_report (stderr, src_total, rrc_total);

  if (expected_conflicts != -1)
    {
      if (! src_ok)
	warn (ngettext ("expected %d shift/reduce conflict",
			"expected %d shift/reduce conflicts",
			expected_conflicts),
	      expected_conflicts);
      if (rrc_total)
	warn (_("expected 0 reduce/reduce conflicts"));
    }
}


void
conflicts_free (void)
{
  XFREE (conflicts);
  bitset_free (shiftset);
  bitset_free (lookaheadset);
  obstack_free (&solved_conflicts_obstack, NULL);
}
Commit	Line	Data
	1	/* Find and resolve or report look-ahead conflicts for bison,
	2
	3	Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003
	4	Free Software Foundation, Inc.
	5
	6	This file is part of Bison, the GNU Compiler Compiler.
	7
	8	Bison is free software; you can redistribute it and/or modify it
	9	under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 2, or (at your option)
	11	any later version.
	12
	13	Bison is distributed in the hope that it will be useful, but
	14	WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	16	General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with Bison; see the file COPYING. If not, write to the Free
	20	Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
	21	02111-1307, USA. */
	22
	23	#include "system.h"
	24
	25	#include <bitset.h>
	26
	27	#include "LR0.h"
	28	#include "complain.h"
	29	#include "conflicts.h"
	30	#include "files.h"
	31	#include "getargs.h"
	32	#include "gram.h"
	33	#include "lalr.h"
	34	#include "reader.h"
	35	#include "state.h"
	36	#include "symtab.h"
	37
	38	/* -1 stands for not specified. */
	39	int expected_conflicts = -1;
	40	static char *conflicts = NULL;
	41	struct obstack solved_conflicts_obstack;
	42
	43	static bitset shiftset;
	44	static bitset lookaheadset;
	45
	46	\f
	47
	48	enum conflict_resolution
	49	{
	50	shift_resolution,
	51	reduce_resolution,
	52	left_resolution,
	53	right_resolution,
	54	nonassoc_resolution
	55	};
	56
	57
	58	/*----------------------------------------------------------------.
	59	\| Explain how an SR conflict between TOKEN and RULE was resolved: \|
	60	\| RESOLUTION. \|
	61	`----------------------------------------------------------------*/
	62
	63	static inline void
	64	log_resolution (rule *r, symbol_number token,
	65	enum conflict_resolution resolution)
	66	{
	67	if (report_flag & report_solved_conflicts)
	68	{
	69	/* The description of the resolution. */
	70	switch (resolution)
	71	{
	72	case shift_resolution:
	73	case right_resolution:
	74	obstack_fgrow2 (&solved_conflicts_obstack,
	75	_("\
	76	Conflict between rule %d and token %s resolved as shift"),
	77	r->number,
	78	symbols[token]->tag);
	79	break;
	80	case reduce_resolution:
	81	case left_resolution:
	82	obstack_fgrow2 (&solved_conflicts_obstack,
	83	_("\
	84	Conflict between rule %d and token %s resolved as reduce"),
	85	r->number,
	86	symbols[token]->tag);
	87	break;
	88	case nonassoc_resolution:
	89	obstack_fgrow2 (&solved_conflicts_obstack,
	90	_("\
	91	Conflict between rule %d and token %s resolved as an error"),
	92	r->number,
	93	symbols[token]->tag);
	94	break;
	95	}
	96
	97	/* The reason. */
	98	switch (resolution)
	99	{
	100	case shift_resolution:
	101	obstack_fgrow2 (&solved_conflicts_obstack,
	102	" (%s < %s)",
	103	r->prec->tag,
	104	symbols[token]->tag);
	105	break;
	106
	107	case reduce_resolution:
	108	obstack_fgrow2 (&solved_conflicts_obstack,
	109	" (%s < %s)",
	110	symbols[token]->tag,
	111	r->prec->tag);
	112	break;
	113
	114	case left_resolution:
	115	obstack_fgrow1 (&solved_conflicts_obstack,
	116	" (%%left %s)",
	117	symbols[token]->tag);
	118	break;
	119
	120	case right_resolution:
	121	obstack_fgrow1 (&solved_conflicts_obstack,
	122	" (%%right %s)",
	123	symbols[token]->tag);
	124	break;
	125	case nonassoc_resolution:
	126	obstack_fgrow1 (&solved_conflicts_obstack,
	127	" (%%nonassoc %s)",
	128	symbols[token]->tag);
	129	break;
	130	}
	131	obstack_sgrow (&solved_conflicts_obstack, ".\n");
	132	}
	133	}
	134
	135
	136	/*------------------------------------------------------------------.
	137	\| Turn off the shift recorded for the specified token in the \|
	138	\| specified state. Used when we resolve a shift-reduce conflict in \|
	139	\| favor of the reduction. \|
	140	`------------------------------------------------------------------*/
	141
	142	static void
	143	flush_shift (state *s, int token)
	144	{
	145	transitions *trans = s->transitions;
	146	int i;
	147
	148	bitset_reset (lookaheadset, token);
	149	for (i = 0; i < trans->num; i++)
	150	if (!TRANSITION_IS_DISABLED (trans, i)
	151	&& TRANSITION_SYMBOL (trans, i) == token)
	152	TRANSITION_DISABLE (trans, i);
	153	}
	154
	155
	156	/*-------------------------------------------------------------------.
	157	\| Turn off the reduce recorded for the specified token for the \|
	158	\| specified lookahead. Used when we resolve a shift-reduce conflict \|
	159	\| in favor of the shift. \|
	160	`-------------------------------------------------------------------*/
	161
	162	static void
	163	flush_reduce (bitset lookaheads, int token)
	164	{
	165	bitset_reset (lookaheads, token);
	166	}
	167
	168
	169	/*------------------------------------------------------------------.
	170	\| Attempt to resolve shift-reduce conflict for one rule by means of \|
	171	\| precedence declarations. It has already been checked that the \|
	172	\| rule has a precedence. A conflict is resolved by modifying the \|
	173	\| shift or reduce tables so that there is no longer a conflict. \|
	174	\| \|
	175	\| LOOKAHEAD is the number of the lookahead bitset to consider. \|
	176	\| \|
	177	\| ERRORS can be used to store discovered explicit errors. \|
	178	`------------------------------------------------------------------*/
	179
	180	static void
	181	resolve_sr_conflict (state s, int ruleno, symbol *errors)
	182	{
	183	symbol_number i;
	184	reductions *reds = s->reductions;
	185	/* Find the rule to reduce by to get precedence of reduction. */
	186	rule *redrule = reds->rules[ruleno];
	187	int redprec = redrule->prec->prec;
	188	bitset lookaheads = reds->lookaheads[ruleno];
	189	int nerrs = 0;
	190
	191	for (i = 0; i < ntokens; i++)
	192	if (bitset_test (lookaheads, i)
	193	&& bitset_test (lookaheadset, i)
	194	&& symbols[i]->prec)
	195	{
	196	/* Shift-reduce conflict occurs for token number i
	197	and it has a precedence.
	198	The precedence of shifting is that of token i. */
	199	if (symbols[i]->prec < redprec)
	200	{
	201	log_resolution (redrule, i, reduce_resolution);
	202	flush_shift (s, i);
	203	}
	204	else if (symbols[i]->prec > redprec)
	205	{
	206	log_resolution (redrule, i, shift_resolution);
	207	flush_reduce (lookaheads, i);
	208	}
	209	else
	210	/* Matching precedence levels.
	211	For left association, keep only the reduction.
	212	For right association, keep only the shift.
	213	For nonassociation, keep neither. */
	214
	215	switch (symbols[i]->assoc)
	216	{
	217	case right_assoc:
	218	log_resolution (redrule, i, right_resolution);
	219	flush_reduce (lookaheads, i);
	220	break;
	221
	222	case left_assoc:
	223	log_resolution (redrule, i, left_resolution);
	224	flush_shift (s, i);
	225	break;
	226
	227	case non_assoc:
	228	log_resolution (redrule, i, nonassoc_resolution);
	229	flush_shift (s, i);
	230	flush_reduce (lookaheads, i);
	231	/* Record an explicit error for this token. */
	232	errors[nerrs++] = symbols[i];
	233	break;
	234
	235	case undef_assoc:
	236	abort ();
	237	}
	238	}
	239
	240	if (nerrs)
	241	{
	242	/* Some tokens have been explicitly made errors. Allocate a
	243	permanent errs structure for this state, to record them. */
	244	state_errs_set (s, nerrs, errors);
	245	}
	246
	247	if (obstack_object_size (&solved_conflicts_obstack))
	248	{
	249	obstack_1grow (&solved_conflicts_obstack, '\0');
	250	s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
	251	}
	252	}
	253
	254
	255	/*-------------------------------------------------------------------.
	256	\| Solve the S/R conflicts of state S using the \|
	257	\| precedence/associativity, and flag it inconsistent if it still has \|
	258	\| conflicts. ERRORS can be used as storage to compute the list of \|
	259	\| lookaheads on which S raises a syntax error (%nonassoc). \|
	260	`-------------------------------------------------------------------*/
	261
	262	static void
	263	set_conflicts (state s, symbol *errors)
	264	{
	265	int i;
	266	transitions *trans = s->transitions;
	267	reductions *reds = s->reductions;
	268
	269	if (s->consistent)
	270	return;
	271
	272	bitset_zero (lookaheadset);
	273
	274	FOR_EACH_SHIFT (trans, i)
	275	bitset_set (lookaheadset, TRANSITION_SYMBOL (trans, i));
	276
	277	/* Loop over all rules which require lookahead in this state. First
	278	check for shift-reduce conflict, and try to resolve using
	279	precedence. */
	280	for (i = 0; i < reds->num; ++i)
	281	if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	282	&& !bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
	283	resolve_sr_conflict (s, i, errors);
	284
	285	/* Loop over all rules which require lookahead in this state. Check
	286	for conflicts not resolved above. */
	287	for (i = 0; i < reds->num; ++i)
	288	{
	289	if (!bitset_disjoint_p (reds->lookaheads[i], lookaheadset))
	290	conflicts[s->number] = 1;
	291
	292	bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
	293	}
	294	}
	295
	296
	297	/*----------------------------------------------------------------.
	298	\| Solve all the S/R conflicts using the precedence/associativity, \|
	299	\| and flag as inconsistent the states that still have conflicts. \|
	300	`----------------------------------------------------------------*/
	301
	302	void
	303	conflicts_solve (void)
	304	{
	305	state_number i;
	306	/* List of lookaheads on which we explicitly raise a syntax error. */
	307	symbol **errors = MALLOC (errors, ntokens + 1);
	308
	309	CALLOC (conflicts, nstates);
	310	shiftset = bitset_create (ntokens, BITSET_FIXED);
	311	lookaheadset = bitset_create (ntokens, BITSET_FIXED);
	312	obstack_init (&solved_conflicts_obstack);
	313
	314	for (i = 0; i < nstates; i++)
	315	{
	316	set_conflicts (states[i], errors);
	317
	318	/* For uniformity of the code, make sure all the states have a valid
	319	`errs' member. */
	320	if (!states[i]->errs)
	321	states[i]->errs = errs_new (0, 0);
	322	}
	323
	324	free (errors);
	325	}
	326
	327
	328	/*---------------------------------------------.
	329	\| Count the number of shift/reduce conflicts. \|
	330	`---------------------------------------------*/
	331
	332	static int
	333	count_sr_conflicts (state *s)
	334	{
	335	int i;
	336	int src_count = 0;
	337	transitions *trans = s->transitions;
	338	reductions *reds = s->reductions;
	339
	340	if (!trans)
	341	return 0;
	342
	343	bitset_zero (lookaheadset);
	344	bitset_zero (shiftset);
	345
	346	FOR_EACH_SHIFT (trans, i)
	347	bitset_set (shiftset, TRANSITION_SYMBOL (trans, i));
	348
	349	for (i = 0; i < reds->num; ++i)
	350	bitset_or (lookaheadset, lookaheadset, reds->lookaheads[i]);
	351
	352	bitset_and (lookaheadset, lookaheadset, shiftset);
	353
	354	src_count = bitset_count (lookaheadset);
	355
	356	return src_count;
	357	}
	358
	359
	360	/*----------------------------------------------------------------.
	361	\| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, \|
	362	\| count one conflict for each token that has any reduce/reduce \|
	363	\| conflicts. Otherwise, count one conflict for each pair of \|
	364	\| conflicting reductions. \|
	365	+`----------------------------------------------------------------*/
	366
	367	static int
	368	count_rr_conflicts (state *s, bool one_per_token)
	369	{
	370	int i;
	371	reductions *reds = s->reductions;
	372	int rrc_count = 0;
	373
	374	for (i = 0; i < ntokens; i++)
	375	{
	376	int count = 0;
	377	int j;
	378	for (j = 0; j < reds->num; ++j)
	379	if (bitset_test (reds->lookaheads[j], i))
	380	count++;
	381
	382	if (count >= 2)
	383	rrc_count += one_per_token ? 1 : count-1;
	384	}
	385
	386	return rrc_count;
	387	}
	388
	389
	390	/*--------------------------------------------------------.
	391	\| Report the number of conflicts, using the Yacc format. \|
	392	`--------------------------------------------------------*/
	393
	394	static void
	395	conflict_report (FILE *out, int src_num, int rrc_num)
	396	{
	397	if (src_num && rrc_num)
	398	fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	399	src_num, rrc_num);
	400	else if (src_num)
	401	fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
	402	else if (rrc_num)
	403	fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
	404	}
	405
	406
	407	/*-----------------------------------------------------------.
	408	\| Output the detailed description of states with conflicts. \|
	409	`-----------------------------------------------------------*/
	410
	411	void
	412	conflicts_output (FILE *out)
	413	{
	414	bool printed_sth = false;
	415	state_number i;
	416	for (i = 0; i < nstates; i++)
	417	{
	418	state *s = states[i];
	419	if (conflicts[i])
	420	{
	421	fprintf (out, _("State %d "), i);
	422	conflict_report (out, count_sr_conflicts (s),
	423	count_rr_conflicts (s, true));
	424	printed_sth = true;
	425	}
	426	}
	427	if (printed_sth)
	428	fputs ("\n\n", out);
	429	}
	430
	431	/*--------------------------------------------------------.
	432	\| Total the number of S/R and R/R conflicts. Unlike the \|
	433	\| code in conflicts_output, however, count EACH pair of \|
	434	\| reductions for the same state and lookahead as one \|
	435	\| conflict. \|
	436	`--------------------------------------------------------*/
	437
	438	int
	439	conflicts_total_count (void)
	440	{
	441	state_number i;
	442	int count;
	443
	444	/* Conflicts by state. */
	445	count = 0;
	446	for (i = 0; i < nstates; i++)
	447	if (conflicts[i])
	448	{
	449	count += count_sr_conflicts (states[i]);
	450	count += count_rr_conflicts (states[i], false);
	451	}
	452	return count;
	453	}
	454
	455
	456	/*------------------------------------------.
	457	\| Reporting the total number of conflicts. \|
	458	`------------------------------------------*/
	459
	460	void
	461	conflicts_print (void)
	462	{
	463	/* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
	464	not set, and then we want 0 SR, or else it is specified, in which
	465	case we want equality. */
	466	bool src_ok = false;
	467
	468	int src_total = 0;
	469	int rrc_total = 0;
	470
	471	/* Conflicts by state. */
	472	{
	473	state_number i;
	474
	475	for (i = 0; i < nstates; i++)
	476	if (conflicts[i])
	477	{
	478	src_total += count_sr_conflicts (states[i]);
	479	rrc_total += count_rr_conflicts (states[i], true);
	480	}
	481	}
	482
	483	src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
	484
	485	/* If there are no RR conflicts, and as many SR conflicts as
	486	expected, then there is nothing to report. */
	487	if (!rrc_total && src_ok)
	488	return;
	489
	490	/* Report the total number of conflicts on STDERR. */
	491	if (! yacc_flag)
	492	fprintf (stderr, "%s: ", current_file);
	493	conflict_report (stderr, src_total, rrc_total);
	494
	495	if (expected_conflicts != -1)
	496	{
	497	if (! src_ok)
	498	warn (ngettext ("expected %d shift/reduce conflict",
	499	"expected %d shift/reduce conflicts",
	500	expected_conflicts),
	501	expected_conflicts);
	502	if (rrc_total)
	503	warn (_("expected 0 reduce/reduce conflicts"));
	504	}
	505	}
	506
	507
	508	void
	509	conflicts_free (void)
	510	{
	511	XFREE (conflicts);
	512	bitset_free (shiftset);
	513	bitset_free (lookaheadset);
	514	obstack_free (&solved_conflicts_obstack, NULL);
	515	}