src/conflicts.c

/* Find and resolve or report lookahead conflicts for bison,

   Copyright (C) 1984, 1989, 1992, 2000-2007, 2009-2012 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 <bitset.h>

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

/* -1 stands for not specified. */
int expected_sr_conflicts = -1;
int expected_rr_conflicts = -1;
static char *conflicts;
static struct obstack solved_conflicts_obstack;
static struct obstack solved_conflicts_xml_obstack;

static bitset shift_set;
static bitset lookahead_set;

\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");
    }

  /* XML report */
  if (xml_flag)
    {
      /* The description of the resolution. */
      switch (resolution)
        {
        case shift_resolution:
        case right_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"shift\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;

        case reduce_resolution:
        case left_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"reduce\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;

        case nonassoc_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "        <resolution rule=\"%d\" symbol=\"%s\""
                          " type=\"error\">",
                          r->number,
                          xml_escape (symbols[token]->tag));
          break;
        }

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

        case reduce_resolution:
          obstack_fgrow2 (&solved_conflicts_xml_obstack,
                          "%s &lt; %s",
                          xml_escape_n (0, symbols[token]->tag),
                          xml_escape_n (1, r->prec->tag));
          break;

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

        case right_resolution:
          obstack_fgrow1 (&solved_conflicts_xml_obstack,
                          "%%right %s",
                          xml_escape (symbols[token]->tag));
          break;

        case nonassoc_resolution:
          obstack_fgrow1 (&solved_conflicts_xml_obstack,
                          "%%nonassoc %s",
                          xml_escape (symbols[token]->tag));
      break;
        }

      obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\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 or as an error (%nonassoc).                |
`------------------------------------------------------------------*/

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

  bitset_reset (lookahead_set, 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 in the         |
| specified lookahead set.  Used when we resolve a shift-reduce       |
| conflict in favor of the shift or as an error (%nonassoc).          |
`--------------------------------------------------------------------*/

static void
flush_reduce (bitset lookahead_tokens, int token)
{
  bitset_reset (lookahead_tokens, 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.     |
|                                                                   |
| RULENO is the number of the lookahead bitset to consider.         |
|                                                                   |
| ERRORS and NERRS can be used to store discovered explicit         |
| errors.                                                           |
`------------------------------------------------------------------*/

static void
resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
{
  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 lookahead_tokens = reds->lookahead_tokens[ruleno];

  for (i = 0; i < ntokens; i++)
    if (bitset_test (lookahead_tokens, i)
	&& bitset_test (lookahead_set, 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 (lookahead_tokens, 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)
	    {
	    default:
	      abort ();

	    case right_assoc:
	      log_resolution (redrule, i, right_resolution);
	      flush_reduce (lookahead_tokens, 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 (lookahead_tokens, i);
	      /* Record an explicit error for this token.  */
	      errors[(*nerrs)++] = symbols[i];
	      break;
	    }
      }
}


/*-------------------------------------------------------------------.
| 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   |
| lookahead tokens 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;
  int nerrs = 0;

  if (s->consistent)
    return;

  bitset_zero (lookahead_set);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (lookahead_set, 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->lookahead_tokens[i], lookahead_set))
      resolve_sr_conflict (s, i, errors, &nerrs);

  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);
    }
  if (obstack_object_size (&solved_conflicts_xml_obstack))
    {
      obstack_1grow (&solved_conflicts_xml_obstack, '\0');
      s->solved_conflicts_xml = obstack_finish (&solved_conflicts_xml_obstack);
    }

  /* 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->lookahead_tokens[i], lookahead_set))
	conflicts[s->number] = 1;
      bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[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 lookahead tokens on which we explicitly raise a syntax error.  */
  symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);

  conflicts = xcalloc (nstates, sizeof *conflicts);
  shift_set = bitset_create (ntokens, BITSET_FIXED);
  lookahead_set = bitset_create (ntokens, BITSET_FIXED);
  obstack_init (&solved_conflicts_obstack);
  obstack_init (&solved_conflicts_xml_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);
}


void
conflicts_update_state_numbers (state_number old_to_new[],
                                state_number nstates_old)
{
  state_number i;
  for (i = 0; i < nstates_old; ++i)
    if (old_to_new[i] != nstates_old)
      conflicts[old_to_new[i]] = conflicts[i];
}


/*---------------------------------------------.
| 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 (lookahead_set);
  bitset_zero (shift_set);

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

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

  bitset_and (lookahead_set, lookahead_set, shift_set);

  src_count = bitset_count (lookahead_set);

  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->lookahead_tokens[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;
  bool rrc_ok;

  int src_total = 0;
  int rrc_total = 0;
  int src_expected;
  int rrc_expected;

  /* 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);
	}
  }

  if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
    {
      warn (_("%%expect-rr applies only to GLR parsers"));
      expected_rr_conflicts = -1;
    }

  src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
  rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
  src_ok = src_total == src_expected;
  rrc_ok = rrc_total == rrc_expected;

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

  /* Report the total number of conflicts on STDERR.  */
  if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
    {
      if (!(warnings_flag & warnings_conflicts_sr))
        src_total = 0;
      if (!(warnings_flag & warnings_conflicts_rr))
        rrc_total = 0;
    }
  if (src_total | rrc_total)
    {
      if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
        set_warning_issued ();
      if (! yacc_flag)
	fprintf (stderr, "%s: ", current_file);
      conflict_report (stderr, src_total, rrc_total);
    }

  if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
    {
      if (! src_ok)
	complain (ngettext ("expected %d shift/reduce conflict",
			    "expected %d shift/reduce conflicts",
			    src_expected),
		  src_expected);
      if (! rrc_ok)
	complain (ngettext ("expected %d reduce/reduce conflict",
			    "expected %d reduce/reduce conflicts",
			    rrc_expected),
		  rrc_expected);
    }
}


void
conflicts_free (void)
{
  free (conflicts);
  bitset_free (shift_set);
  bitset_free (lookahead_set);
  obstack_free (&solved_conflicts_obstack, NULL);
  obstack_free (&solved_conflicts_xml_obstack, NULL);
}
Commit	Line	Data
	1	/* Find and resolve or report lookahead conflicts for bison,
	2
	3	Copyright (C) 1984, 1989, 1992, 2000-2007, 2009-2012 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 <bitset.h>
	25
	26	#include "LR0.h"
	27	#include "complain.h"
	28	#include "conflicts.h"
	29	#include "files.h"
	30	#include "getargs.h"
	31	#include "gram.h"
	32	#include "lalr.h"
	33	#include "print-xml.h"
	34	#include "reader.h"
	35	#include "state.h"
	36	#include "symtab.h"
	37
	38	/* -1 stands for not specified. */
	39	int expected_sr_conflicts = -1;
	40	int expected_rr_conflicts = -1;
	41	static char *conflicts;
	42	static struct obstack solved_conflicts_obstack;
	43	static struct obstack solved_conflicts_xml_obstack;
	44
	45	static bitset shift_set;
	46	static bitset lookahead_set;
	47
	48	\f
	49
	50	enum conflict_resolution
	51	{
	52	shift_resolution,
	53	reduce_resolution,
	54	left_resolution,
	55	right_resolution,
	56	nonassoc_resolution
	57	};
	58
	59
	60	/*----------------------------------------------------------------.
	61	\| Explain how an SR conflict between TOKEN and RULE was resolved: \|
	62	\| RESOLUTION. \|
	63	`----------------------------------------------------------------*/
	64
	65	static inline void
	66	log_resolution (rule *r, symbol_number token,
	67	enum conflict_resolution resolution)
	68	{
	69	if (report_flag & report_solved_conflicts)
	70	{
	71	/* The description of the resolution. */
	72	switch (resolution)
	73	{
	74	case shift_resolution:
	75	case right_resolution:
	76	obstack_fgrow2 (&solved_conflicts_obstack,
	77	_(" Conflict between rule %d and token %s"
	78	" resolved as shift"),
	79	r->number,
	80	symbols[token]->tag);
	81	break;
	82
	83	case reduce_resolution:
	84	case left_resolution:
	85	obstack_fgrow2 (&solved_conflicts_obstack,
	86	_(" Conflict between rule %d and token %s"
	87	" resolved as reduce"),
	88	r->number,
	89	symbols[token]->tag);
	90	break;
	91
	92	case nonassoc_resolution:
	93	obstack_fgrow2 (&solved_conflicts_obstack,
	94	_(" Conflict between rule %d and token %s"
	95	" resolved as an error"),
	96	r->number,
	97	symbols[token]->tag);
	98	break;
	99	}
	100
	101	/* The reason. */
	102	switch (resolution)
	103	{
	104	case shift_resolution:
	105	obstack_fgrow2 (&solved_conflicts_obstack,
	106	" (%s < %s)",
	107	r->prec->tag,
	108	symbols[token]->tag);
	109	break;
	110
	111	case reduce_resolution:
	112	obstack_fgrow2 (&solved_conflicts_obstack,
	113	" (%s < %s)",
	114	symbols[token]->tag,
	115	r->prec->tag);
	116	break;
	117
	118	case left_resolution:
	119	obstack_fgrow1 (&solved_conflicts_obstack,
	120	" (%%left %s)",
	121	symbols[token]->tag);
	122	break;
	123
	124	case right_resolution:
	125	obstack_fgrow1 (&solved_conflicts_obstack,
	126	" (%%right %s)",
	127	symbols[token]->tag);
	128	break;
	129
	130	case nonassoc_resolution:
	131	obstack_fgrow1 (&solved_conflicts_obstack,
	132	" (%%nonassoc %s)",
	133	symbols[token]->tag);
	134	break;
	135	}
	136
	137	obstack_sgrow (&solved_conflicts_obstack, ".\n");
	138	}
	139
	140	/* XML report */
	141	if (xml_flag)
	142	{
	143	/* The description of the resolution. */
	144	switch (resolution)
	145	{
	146	case shift_resolution:
	147	case right_resolution:
	148	obstack_fgrow2 (&solved_conflicts_xml_obstack,
	149	" <resolution rule=\"%d\" symbol=\"%s\""
	150	" type=\"shift\">",
	151	r->number,
	152	xml_escape (symbols[token]->tag));
	153	break;
	154
	155	case reduce_resolution:
	156	case left_resolution:
	157	obstack_fgrow2 (&solved_conflicts_xml_obstack,
	158	" <resolution rule=\"%d\" symbol=\"%s\""
	159	" type=\"reduce\">",
	160	r->number,
	161	xml_escape (symbols[token]->tag));
	162	break;
	163
	164	case nonassoc_resolution:
	165	obstack_fgrow2 (&solved_conflicts_xml_obstack,
	166	" <resolution rule=\"%d\" symbol=\"%s\""
	167	" type=\"error\">",
	168	r->number,
	169	xml_escape (symbols[token]->tag));
	170	break;
	171	}
	172
	173	/* The reason. */
	174	switch (resolution)
	175	{
	176	case shift_resolution:
	177	obstack_fgrow2 (&solved_conflicts_xml_obstack,
	178	"%s < %s",
	179	xml_escape_n (0, r->prec->tag),
	180	xml_escape_n (1, symbols[token]->tag));
	181	break;
	182
	183	case reduce_resolution:
	184	obstack_fgrow2 (&solved_conflicts_xml_obstack,
	185	"%s < %s",
	186	xml_escape_n (0, symbols[token]->tag),
	187	xml_escape_n (1, r->prec->tag));
	188	break;
	189
	190	case left_resolution:
	191	obstack_fgrow1 (&solved_conflicts_xml_obstack,
	192	"%%left %s",
	193	xml_escape (symbols[token]->tag));
	194	break;
	195
	196	case right_resolution:
	197	obstack_fgrow1 (&solved_conflicts_xml_obstack,
	198	"%%right %s",
	199	xml_escape (symbols[token]->tag));
	200	break;
	201
	202	case nonassoc_resolution:
	203	obstack_fgrow1 (&solved_conflicts_xml_obstack,
	204	"%%nonassoc %s",
	205	xml_escape (symbols[token]->tag));
	206	break;
	207	}
	208
	209	obstack_sgrow (&solved_conflicts_xml_obstack, "</resolution>\n");
	210	}
	211	}
	212
	213
	214	/*------------------------------------------------------------------.
	215	\| Turn off the shift recorded for the specified token in the \|
	216	\| specified state. Used when we resolve a shift-reduce conflict in \|
	217	\| favor of the reduction or as an error (%nonassoc). \|
	218	`------------------------------------------------------------------*/
	219
	220	static void
	221	flush_shift (state *s, int token)
	222	{
	223	transitions *trans = s->transitions;
	224	int i;
	225
	226	bitset_reset (lookahead_set, token);
	227	for (i = 0; i < trans->num; i++)
	228	if (!TRANSITION_IS_DISABLED (trans, i)
	229	&& TRANSITION_SYMBOL (trans, i) == token)
	230	TRANSITION_DISABLE (trans, i);
	231	}
	232
	233
	234	/*--------------------------------------------------------------------.
	235	\| Turn off the reduce recorded for the specified token in the \|
	236	\| specified lookahead set. Used when we resolve a shift-reduce \|
	237	\| conflict in favor of the shift or as an error (%nonassoc). \|
	238	`--------------------------------------------------------------------*/
	239
	240	static void
	241	flush_reduce (bitset lookahead_tokens, int token)
	242	{
	243	bitset_reset (lookahead_tokens, token);
	244	}
	245
	246
	247	/*------------------------------------------------------------------.
	248	\| Attempt to resolve shift-reduce conflict for one rule by means of \|
	249	\| precedence declarations. It has already been checked that the \|
	250	\| rule has a precedence. A conflict is resolved by modifying the \|
	251	\| shift or reduce tables so that there is no longer a conflict. \|
	252	\| \|
	253	\| RULENO is the number of the lookahead bitset to consider. \|
	254	\| \|
	255	\| ERRORS and NERRS can be used to store discovered explicit \|
	256	\| errors. \|
	257	`------------------------------------------------------------------*/
	258
	259	static void
	260	resolve_sr_conflict (state s, int ruleno, symbol errors, int nerrs)
	261	{
	262	symbol_number i;
	263	reductions *reds = s->reductions;
	264	/* Find the rule to reduce by to get precedence of reduction. */
	265	rule *redrule = reds->rules[ruleno];
	266	int redprec = redrule->prec->prec;
	267	bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
	268
	269	for (i = 0; i < ntokens; i++)
	270	if (bitset_test (lookahead_tokens, i)
	271	&& bitset_test (lookahead_set, i)
	272	&& symbols[i]->prec)
	273	{
	274	/* Shift-reduce conflict occurs for token number i
	275	and it has a precedence.
	276	The precedence of shifting is that of token i. */
	277	if (symbols[i]->prec < redprec)
	278	{
	279	log_resolution (redrule, i, reduce_resolution);
	280	flush_shift (s, i);
	281	}
	282	else if (symbols[i]->prec > redprec)
	283	{
	284	log_resolution (redrule, i, shift_resolution);
	285	flush_reduce (lookahead_tokens, i);
	286	}
	287	else
	288	/* Matching precedence levels.
	289	For left association, keep only the reduction.
	290	For right association, keep only the shift.
	291	For nonassociation, keep neither. */
	292
	293	switch (symbols[i]->assoc)
	294	{
	295	default:
	296	abort ();
	297
	298	case right_assoc:
	299	log_resolution (redrule, i, right_resolution);
	300	flush_reduce (lookahead_tokens, i);
	301	break;
	302
	303	case left_assoc:
	304	log_resolution (redrule, i, left_resolution);
	305	flush_shift (s, i);
	306	break;
	307
	308	case non_assoc:
	309	log_resolution (redrule, i, nonassoc_resolution);
	310	flush_shift (s, i);
	311	flush_reduce (lookahead_tokens, i);
	312	/* Record an explicit error for this token. */
	313	errors[(*nerrs)++] = symbols[i];
	314	break;
	315	}
	316	}
	317	}
	318
	319
	320	/*-------------------------------------------------------------------.
	321	\| Solve the S/R conflicts of state S using the \|
	322	\| precedence/associativity, and flag it inconsistent if it still has \|
	323	\| conflicts. ERRORS can be used as storage to compute the list of \|
	324	\| lookahead tokens on which S raises a syntax error (%nonassoc). \|
	325	`-------------------------------------------------------------------*/
	326
	327	static void
	328	set_conflicts (state s, symbol *errors)
	329	{
	330	int i;
	331	transitions *trans = s->transitions;
	332	reductions *reds = s->reductions;
	333	int nerrs = 0;
	334
	335	if (s->consistent)
	336	return;
	337
	338	bitset_zero (lookahead_set);
	339
	340	FOR_EACH_SHIFT (trans, i)
	341	bitset_set (lookahead_set, TRANSITION_SYMBOL (trans, i));
	342
	343	/* Loop over all rules which require lookahead in this state. First
	344	check for shift-reduce conflict, and try to resolve using
	345	precedence. */
	346	for (i = 0; i < reds->num; ++i)
	347	if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	348	&& !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
	349	resolve_sr_conflict (s, i, errors, &nerrs);
	350
	351	if (nerrs)
	352	{
	353	/* Some tokens have been explicitly made errors. Allocate a
	354	permanent errs structure for this state, to record them. */
	355	state_errs_set (s, nerrs, errors);
	356	}
	357	if (obstack_object_size (&solved_conflicts_obstack))
	358	{
	359	obstack_1grow (&solved_conflicts_obstack, '\0');
	360	s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
	361	}
	362	if (obstack_object_size (&solved_conflicts_xml_obstack))
	363	{
	364	obstack_1grow (&solved_conflicts_xml_obstack, '\0');
	365	s->solved_conflicts_xml = obstack_finish (&solved_conflicts_xml_obstack);
	366	}
	367
	368	/* Loop over all rules which require lookahead in this state. Check
	369	for conflicts not resolved above. */
	370	for (i = 0; i < reds->num; ++i)
	371	{
	372	if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
	373	conflicts[s->number] = 1;
	374	bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
	375	}
	376	}
	377
	378
	379	/*----------------------------------------------------------------.
	380	\| Solve all the S/R conflicts using the precedence/associativity, \|
	381	\| and flag as inconsistent the states that still have conflicts. \|
	382	`----------------------------------------------------------------*/
	383
	384	void
	385	conflicts_solve (void)
	386	{
	387	state_number i;
	388	/* List of lookahead tokens on which we explicitly raise a syntax error. */
	389	symbol *errors = xnmalloc (ntokens + 1, sizeof errors);
	390
	391	conflicts = xcalloc (nstates, sizeof *conflicts);
	392	shift_set = bitset_create (ntokens, BITSET_FIXED);
	393	lookahead_set = bitset_create (ntokens, BITSET_FIXED);
	394	obstack_init (&solved_conflicts_obstack);
	395	obstack_init (&solved_conflicts_xml_obstack);
	396
	397	for (i = 0; i < nstates; i++)
	398	{
	399	set_conflicts (states[i], errors);
	400
	401	/* For uniformity of the code, make sure all the states have a valid
	402	`errs' member. */
	403	if (!states[i]->errs)
	404	states[i]->errs = errs_new (0, 0);
	405	}
	406
	407	free (errors);
	408	}
	409
	410
	411	void
	412	conflicts_update_state_numbers (state_number old_to_new[],
	413	state_number nstates_old)
	414	{
	415	state_number i;
	416	for (i = 0; i < nstates_old; ++i)
	417	if (old_to_new[i] != nstates_old)
	418	conflicts[old_to_new[i]] = conflicts[i];
	419	}
	420
	421
	422	/*---------------------------------------------.
	423	\| Count the number of shift/reduce conflicts. \|
	424	`---------------------------------------------*/
	425
	426	static int
	427	count_sr_conflicts (state *s)
	428	{
	429	int i;
	430	int src_count = 0;
	431	transitions *trans = s->transitions;
	432	reductions *reds = s->reductions;
	433
	434	if (!trans)
	435	return 0;
	436
	437	bitset_zero (lookahead_set);
	438	bitset_zero (shift_set);
	439
	440	FOR_EACH_SHIFT (trans, i)
	441	bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
	442
	443	for (i = 0; i < reds->num; ++i)
	444	bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
	445
	446	bitset_and (lookahead_set, lookahead_set, shift_set);
	447
	448	src_count = bitset_count (lookahead_set);
	449
	450	return src_count;
	451	}
	452
	453
	454	/*----------------------------------------------------------------.
	455	\| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, \|
	456	\| count one conflict for each token that has any reduce/reduce \|
	457	\| conflicts. Otherwise, count one conflict for each pair of \|
	458	\| conflicting reductions. \|
	459	+`----------------------------------------------------------------*/
	460
	461	static int
	462	count_rr_conflicts (state *s, bool one_per_token)
	463	{
	464	int i;
	465	reductions *reds = s->reductions;
	466	int rrc_count = 0;
	467
	468	for (i = 0; i < ntokens; i++)
	469	{
	470	int count = 0;
	471	int j;
	472	for (j = 0; j < reds->num; ++j)
	473	if (bitset_test (reds->lookahead_tokens[j], i))
	474	count++;
	475
	476	if (count >= 2)
	477	rrc_count += one_per_token ? 1 : count-1;
	478	}
	479
	480	return rrc_count;
	481	}
	482
	483
	484	/*--------------------------------------------------------.
	485	\| Report the number of conflicts, using the Yacc format. \|
	486	`--------------------------------------------------------*/
	487
	488	static void
	489	conflict_report (FILE *out, int src_num, int rrc_num)
	490	{
	491	if (src_num && rrc_num)
	492	fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	493	src_num, rrc_num);
	494	else if (src_num)
	495	fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
	496	else if (rrc_num)
	497	fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
	498	}
	499
	500
	501	/*-----------------------------------------------------------.
	502	\| Output the detailed description of states with conflicts. \|
	503	`-----------------------------------------------------------*/
	504
	505	void
	506	conflicts_output (FILE *out)
	507	{
	508	bool printed_sth = false;
	509	state_number i;
	510	for (i = 0; i < nstates; i++)
	511	{
	512	state *s = states[i];
	513	if (conflicts[i])
	514	{
	515	fprintf (out, _("State %d "), i);
	516	conflict_report (out, count_sr_conflicts (s),
	517	count_rr_conflicts (s, true));
	518	printed_sth = true;
	519	}
	520	}
	521	if (printed_sth)
	522	fputs ("\n\n", out);
	523	}
	524
	525	/*--------------------------------------------------------.
	526	\| Total the number of S/R and R/R conflicts. Unlike the \|
	527	\| code in conflicts_output, however, count EACH pair of \|
	528	\| reductions for the same state and lookahead as one \|
	529	\| conflict. \|
	530	`--------------------------------------------------------*/
	531
	532	int
	533	conflicts_total_count (void)
	534	{
	535	state_number i;
	536	int count;
	537
	538	/* Conflicts by state. */
	539	count = 0;
	540	for (i = 0; i < nstates; i++)
	541	if (conflicts[i])
	542	{
	543	count += count_sr_conflicts (states[i]);
	544	count += count_rr_conflicts (states[i], false);
	545	}
	546	return count;
	547	}
	548
	549
	550	/*------------------------------------------.
	551	\| Reporting the total number of conflicts. \|
	552	`------------------------------------------*/
	553
	554	void
	555	conflicts_print (void)
	556	{
	557	/* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
	558	not set, and then we want 0 SR, or else it is specified, in which
	559	case we want equality. */
	560	bool src_ok;
	561	bool rrc_ok;
	562
	563	int src_total = 0;
	564	int rrc_total = 0;
	565	int src_expected;
	566	int rrc_expected;
	567
	568	/* Conflicts by state. */
	569	{
	570	state_number i;
	571
	572	for (i = 0; i < nstates; i++)
	573	if (conflicts[i])
	574	{
	575	src_total += count_sr_conflicts (states[i]);
	576	rrc_total += count_rr_conflicts (states[i], true);
	577	}
	578	}
	579
	580	if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
	581	{
	582	warn (_("%%expect-rr applies only to GLR parsers"));
	583	expected_rr_conflicts = -1;
	584	}
	585
	586	src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
	587	rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
	588	src_ok = src_total == src_expected;
	589	rrc_ok = rrc_total == rrc_expected;
	590
	591	/* If there are as many RR conflicts and SR conflicts as
	592	expected, then there is nothing to report. */
	593	if (rrc_ok & src_ok)
	594	return;
	595
	596	/* Report the total number of conflicts on STDERR. */
	597	if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
	598	{
	599	if (!(warnings_flag & warnings_conflicts_sr))
	600	src_total = 0;
	601	if (!(warnings_flag & warnings_conflicts_rr))
	602	rrc_total = 0;
	603	}
	604	if (src_total \| rrc_total)
	605	{
	606	if (expected_sr_conflicts == -1 && expected_rr_conflicts == -1)
	607	set_warning_issued ();
	608	if (! yacc_flag)
	609	fprintf (stderr, "%s: ", current_file);
	610	conflict_report (stderr, src_total, rrc_total);
	611	}
	612
	613	if (expected_sr_conflicts != -1 \|\| expected_rr_conflicts != -1)
	614	{
	615	if (! src_ok)
	616	complain (ngettext ("expected %d shift/reduce conflict",
	617	"expected %d shift/reduce conflicts",
	618	src_expected),
	619	src_expected);
	620	if (! rrc_ok)
	621	complain (ngettext ("expected %d reduce/reduce conflict",
	622	"expected %d reduce/reduce conflicts",
	623	rrc_expected),
	624	rrc_expected);
	625	}
	626	}
	627
	628
	629	void
	630	conflicts_free (void)
	631	{
	632	free (conflicts);
	633	bitset_free (shift_set);
	634	bitset_free (lookahead_set);
	635	obstack_free (&solved_conflicts_obstack, NULL);
	636	obstack_free (&solved_conflicts_xml_obstack, NULL);
	637	}