FYI: Fix the computation of YYFINAL

[Akim Demaille]

I introduced the following bug years ago, and it was "harmless" until
we (i.e., I, again...) allowed the user to use $end in her grammar.  I
opened a can of worms without realizing it.

At least one issue is addressed here.

Index: ChangeLog
from  Akim Demaille  <address@hidden>

        In some (weird) cases, the final state number is incorrect.
        Reported by Alexandre Duret-Lutz.
        * src/LR0.c (state_list_append): Remove the computation of
        final_state.
        (save_reductions): Do it here.
        (get_state): Alpha conversion.
        (generate_states): Use a for loop.
        * src/gram.h (item_number_is_rule_number)
        (item_number_is_symbol_number): New.
        * src/state.c: Use assert.
        * src/system.h: Include assert.h.
        * tests/sets.at (Accept): New.

Index: src/LR0.c
===================================================================
RCS file: /cvsroot/bison/bison/src/LR0.c,v
retrieving revision 1.93
diff -u -u -r1.93 LR0.c
--- src/LR0.c 14 May 2005 06:49:47 -0000 1.93
+++ src/LR0.c 3 Nov 2005 15:20:53 -0000
@@ -1,6 +1,6 @@
 /* Generate the nondeterministic finite state machine for Bison.
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004 Free
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005 Free
    Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -66,11 +66,6 @@
     fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
             nstates, sym, symbols[sym]->tag);
 
-  /* If this is the endtoken, and this is not the initial state, then
-     this is the final state.  */
-  if (sym == 0 && first_state)
-    final_state = s;
-
   node->next = NULL;
   node->state = s;
 
@@ -213,20 +208,20 @@
 static state *
 get_state (symbol_number sym, size_t core_size, item_number *core)
 {
-  state *sp;
+  state *s;
 
   if (trace_flag & trace_automaton)
     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
             sym, symbols[sym]->tag);
 
-  sp = state_hash_lookup (core_size, core);
-  if (!sp)
-    sp = state_list_append (sym, core_size, core);
+  s = state_hash_lookup (core_size, core);
+  if (!s)
+    s = state_list_append (sym, core_size, core);
 
   if (trace_flag & trace_automaton)
-    fprintf (stderr, "Exiting get_state => %d\n", sp->number);
+    fprintf (stderr, "Exiting get_state => %d\n", s->number);
 
-  return sp;
+  return s;
 }
 
 /*---------------------------------------------------------------.
@@ -278,9 +273,18 @@
   /* Find and count the active items that represent ends of rules. */
   for (i = 0; i < nritemset; ++i)
     {
-      int item = ritem[itemset[i]];
-      if (item < 0)
-       redset[count++] = &rules[item_number_as_rule_number (item)];
+      item_number item = ritem[itemset[i]];
+      if (item_number_is_rule_number (item))
+       {
+         rule_number r = item_number_as_rule_number (item);
+         redset[count++] = &rules[r];
+         if (r == 0)
+           {
+             /* This is "reduce 0", i.e., accept. */
+             assert (!final_state);
+             final_state = s;
+           }
+       }
     }
 
   /* Make a reductions structure and copy the data into it.  */
@@ -338,9 +342,8 @@
      item of this initial rule.  */
   state_list_append (0, 1, &initial_core);
 
-  list = first_state;
-
-  while (list)
+  /* States are queued when they are created; process them all.  */
+  for (list = first_state; list; list = list->next)
     {
       state *s = list->state;
       if (trace_flag & trace_automaton)
@@ -362,10 +365,6 @@
       /* Create the shifts structures for the shifts to those states,
         now that the state numbers transitioning to are known.  */
       state_transitions_set (s, nshifts, shiftset);
-
-      /* states are queued when they are created; process them all.
-        */
-      list = list->next;
     }
 
   /* discard various storage */
Index: src/gram.h
===================================================================
RCS file: /cvsroot/bison/bison/src/gram.h,v
retrieving revision 1.57
diff -u -u -r1.57 gram.h
--- src/gram.h 14 May 2005 06:49:47 -0000 1.57
+++ src/gram.h 3 Nov 2005 15:20:53 -0000
@@ -1,6 +1,6 @@
 /* Data definitions for internal representation of Bison's input.
 
-   Copyright (C) 1984, 1986, 1989, 1992, 2001, 2002, 2003, 2004
+   Copyright (C) 1984, 1986, 1989, 1992, 2001, 2002, 2003, 2004, 2005
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -138,6 +138,12 @@
   return i;
 }
 
+static inline bool
+item_number_is_symbol_number (item_number i)
+{
+  return i >= 0;
+}
+
 /* Rule numbers.  */
 typedef int rule_number;
 extern rule_number nrules;
@@ -154,6 +160,11 @@
   return -1 - i;
 }
 
+static inline bool
+item_number_is_rule_number (item_number i)
+{
+  return i < 0;
+}
 
 /*--------.
 | Rules.  |
Index: src/state.c
===================================================================
RCS file: /cvsroot/bison/bison/src/state.c,v
retrieving revision 1.36
diff -u -u -r1.36 state.c
--- src/state.c 5 Oct 2005 06:39:08 -0000 1.36
+++ src/state.c 3 Nov 2005 15:20:53 -0000
@@ -1,6 +1,6 @@
 /* Type definitions for nondeterministic finite state machine for Bison.
 
-   Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -174,8 +174,7 @@
 void
 state_transitions_set (state *s, int num, state **trans)
 {
-  if (s->transitions)
-    abort ();
+  assert (!s->transitions);
   s->transitions = transitions_new (num, trans);
 }
 
@@ -187,8 +186,7 @@
 void
 state_reductions_set (state *s, int num, rule **reds)
 {
-  if (s->reductions)
-    abort ();
+  assert (!s->reductions);
   s->reductions = reductions_new (num, reds);
 }
 
@@ -248,9 +246,9 @@
 }
 
 
-/*----------------------.
+/*---------------------.
 | A state hash table.  |
-`----------------------*/
+`---------------------*/
 
 /* Initial capacity of states hash table.  */
 #define HT_INITIAL_CAPACITY 257
Index: src/system.h
===================================================================
RCS file: /cvsroot/bison/bison/src/system.h,v
retrieving revision 1.71
diff -u -u -r1.71 system.h
--- src/system.h 13 Oct 2005 10:13:24 -0000 1.71
+++ src/system.h 3 Nov 2005 15:20:53 -0000
@@ -52,6 +52,8 @@
 typedef size_t uintptr_t;
 #endif
 
+#include <assert.h>
+
 #include <verify.h>
 #include <xalloc.h>
 
Index: tests/sets.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/sets.at,v
retrieving revision 1.19
diff -u -u -r1.19 sets.at
--- tests/sets.at 24 Jul 2005 07:24:22 -0000 1.19
+++ tests/sets.at 3 Nov 2005 15:20:53 -0000
@@ -252,3 +252,51 @@
 ]])
 
 AT_CLEANUP
+
+
+
+
+## -------- ##
+## Accept.  ##
+## -------- ##
+
+# In some weird cases Bison could compute an incorrect final state
+# number.  This happens only if the $end token is used in the user
+# grammar, which is a very suspicious accidental feature introduce
+# as a side effect of allowing the user to name $end using
+# `%token END 0 "end of file"'.
+
+AT_SETUP([Accept])
+
+AT_DATA([input.y],
+[[%token END 0
+%%
+input:
+  'a'
+| '(' input ')'
+| '(' error END
+;
+]])
+
+AT_CHECK([[bison -v -o input.c input.y]])
+
+# Get the final state in the parser.
+AT_CHECK([sed -n 's/.*define YYFINAL *\([0-9][0-9]\)*/final state \1/p' 
input.c],
+         0, [stdout])
+mv stdout expout
+
+# Get the final state in the report, from the "accept" action..
+AT_CHECK([sed -n '
+           /^state \(.*\)/{
+            s//final state \1/
+            x
+          }
+          / accept/{
+            x
+            p
+            q
+          }
+       ' input.output],
+       0, [expout])
+
+AT_CLEANUP