src/conflicts.c

/* Find and resolve or report look-ahead conflicts for bison,
   Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002
   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 "complain.h"
#include "getargs.h"
#include "symtab.h"
#include "files.h"
#include "gram.h"
#include "state.h"
#include "lalr.h"
#include "conflicts.h"
#include "reader.h"
#include "LR0.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_e
  {
    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_t *rule, int token,
		enum conflict_resolution_e resolution)
{
  if (report_flag & report_solved_conflicts)
    {
      /* The description of the resolution. */
      switch (resolution)
	{
	case shift_resolution:
	case left_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as shift"),
			  rule->number,
			  symbols[token]->tag);
	  break;
	case reduce_resolution:
	case right_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as reduce"),
			  rule->number,
			  symbols[token]->tag);
	  break;
	case nonassoc_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as an error"),
			  rule->number,
			  symbols[token]->tag);
	  break;
	}

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

	case reduce_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  symbols[token]->tag,
			  rule->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_t *state, int token)
{
  shifts *shiftp = state->shifts;
  int i;

  bitset_reset (lookaheadset, token);
  for (i = 0; i < shiftp->nshifts; i++)
    if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
      SHIFT_DISABLE (shiftp, 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.      |
`------------------------------------------------------------------*/

static void
resolve_sr_conflict (state_t *state, int lookahead)
{
  int i;
  /* Find the rule to reduce by to get precedence of reduction.  */
  rule_t *redrule = state->lookaheads_rule[lookahead];
  int redprec = redrule->prec->prec;
  bitset lookaheads = state->lookaheads[lookahead];
  errs *errp = errs_new (ntokens + 1);
  errp->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 (state, 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 (state, i);
	      break;

	    case non_assoc:
	      log_resolution (redrule, i, nonassoc_resolution);
	      flush_shift (state, i);
	      flush_reduce (lookaheads, i);
	      /* Record an explicit error for this token.  */
	      errp->errs[errp->nerrs++] = i;
	      break;

	    case undef_assoc:
	      assert (symbols[i]->assoc != undef_assoc);
	      break;
	    }
      }

  /* Some tokens have been explicitly made errors.  Allocate a
     permanent errs structure for this state, to record them.  */
  state->errs = errs_dup (errp);
  free (errp);

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


static void
set_conflicts (state_t *state)
{
  int i;
  shifts *shiftp;

  if (state->consistent)
    return;

  bitset_zero (lookaheadset);

  shiftp = state->shifts;
  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
    if (!SHIFT_IS_DISABLED (shiftp, i))
      bitset_set (lookaheadset, SHIFT_SYMBOL (shiftp, 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 < state->nlookaheads; ++i)
    if (state->lookaheads_rule[i]->prec
	&& state->lookaheads_rule[i]->prec->prec
	&& !bitset_disjoint_p (state->lookaheads[i], lookaheadset))
      {
	resolve_sr_conflict (state, i);
	break;
      }

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

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

void
conflicts_solve (void)
{
  size_t i;

  conflicts = XCALLOC (char, 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]);
}


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

static int
count_sr_conflicts (state_t *state)
{
  int i;
  int src_count = 0;
  shifts *shiftp = state->shifts;

  if (!shiftp)
    return 0;

  bitset_zero (lookaheadset);
  bitset_zero (shiftset);

  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
    if (!SHIFT_IS_DISABLED (shiftp, i))
      bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));

  for (i = 0; i < state->nlookaheads; ++i)
    bitset_or (lookaheadset, lookaheadset, state->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_t *state, int one_per_token)
{
  int i;
  int rrc_count = 0;

  if (state->nlookaheads < 2)
    return 0;

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

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

  return rrc_count;
}

/*--------------------------------------------------------------.
| Return a human readable string which reports shift/reduce and |
| reduce/reduce conflict numbers (SRC_NUM, RRC_NUM).            |
`--------------------------------------------------------------*/

static const char *
conflict_report (int src_num, int rrc_num)
{
  static char res[4096];
  char *cp = res;

  if (src_num >= 1)
    {
      sprintf (cp, ngettext ("%d shift/reduce conflict",
			     "%d shift/reduce conflicts", src_num), src_num);
      cp += strlen (cp);
    }

  if (src_num > 0 && rrc_num > 0)
    {
      sprintf (cp, " %s ", _("and"));
      cp += strlen (cp);
    }

  if (rrc_num >= 1)
    {
      sprintf (cp, ngettext ("%d reduce/reduce conflict",
			     "%d reduce/reduce conflicts", rrc_num), rrc_num);
      cp += strlen (cp);
    }

  *cp++ = '.';
  *cp++ = '\n';
  *cp++ = '\0';

  return res;
}


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

void
conflicts_output (FILE *out)
{
  bool printed_sth = FALSE;
  size_t i;
  for (i = 0; i < nstates; i++)
    if (conflicts[i])
      {
	fprintf (out, _("State %d contains "), i);
	fputs (conflict_report (count_sr_conflicts (states[i]),
				count_rr_conflicts (states[i], TRUE)), out);
	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)
{
  unsigned 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)
{
  size_t i;

  /* 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.  */
  int src_ok = 0;

  int src_total = 0;
  int rrc_total = 0;

  /* Conflicts by state.  */
  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)
    {
      /* If invoked with `--yacc', use the output format specified by
	 POSIX.  */
      fprintf (stderr, _("conflicts: "));
      if (src_total > 0)
	fprintf (stderr, _(" %d shift/reduce"), src_total);
      if (src_total > 0 && rrc_total > 0)
	fprintf (stderr, ",");
      if (rrc_total > 0)
	fprintf (stderr, _(" %d reduce/reduce"), rrc_total);
      putc ('\n', stderr);
    }
  else
    {
      fprintf (stderr, _("%s contains "), infile);
      fputs (conflict_report (src_total, rrc_total), stderr);
    }

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