Re: unreachable states after conflict resolution

[Joel E. Denny]

On Sun, 27 May 2007, Paul Eggert wrote:

> "Joel E. Denny" <address@hidden> writes:
> 
> > It looks like I've been slipping into C99 lately.  Do we expect our users' 
> > compilers to support C99?
> 
> Not yet.  I'd wait another couple of years at least.  Coreutils ships
> with C99 source but has a patch for those with older compilers to use,
> and it still regularly gets email from people who need to apply the
> patch.

Thanks.  I committed the following, which I believe fixes this and does 
some other cleanup.

Index: ChangeLog
===================================================================
RCS file: /sources/bison/bison/ChangeLog,v
retrieving revision 1.1702
diff -p -u -r1.1702 ChangeLog
--- ChangeLog   26 May 2007 20:08:18 -0000      1.1702
+++ ChangeLog   28 May 2007 01:02:07 -0000
@@ -1,3 +1,20 @@
+2007-05-27  Joel E. Denny  <address@hidden>
+
+       Don't depend on C99 features.
+       * src/conflicts.c (conflicts_update_state_numbers): Fix for-loop.
+       * src/lalr.c (lalr_update_state_numbers): Fix for-loop.
+       * src/reader.c (check_and_convert_grammar): Fix for-loop.
+       * src/state.c (state_mark_reachable_states): Fix for-loop.
+       (state_remove_unreachable_states): Fix for-loop.
+
+       Don't widen struct state with member reachable just to temporarily
+       record reachability.  Instead, use a local bitset.
+       * src/state.h (struct state): Remove member.
+       * src/state.c (state_new): Don't initialize it.
+       (state_mark_reachable_states): Rename to...
+       (state_record_reachable_states): ... this, and use bitset.
+       (state_remove_unreachable_states): Use bitset.
+
 2007-05-26  Joel E. Denny  <address@hidden>
 
        * src/Makefile.am (yacc): Quote target action commands properly so
Index: src/conflicts.c
===================================================================
RCS file: /sources/bison/bison/src/conflicts.c,v
retrieving revision 1.118
diff -p -u -r1.118 conflicts.c
--- src/conflicts.c     8 May 2007 05:03:53 -0000       1.118
+++ src/conflicts.c     28 May 2007 01:02:08 -0000
@@ -331,7 +331,8 @@ void
 conflicts_update_state_numbers (state_number old_to_new[],
                                 state_number nstates_old)
 {
-  for (state_number i = 0; i < nstates_old; ++i)
+  state_number i;
+  for (i = 0; i < nstates_old; ++i)
     if (old_to_new[i] != nstates_old)
       conflicts[old_to_new[i]] = conflicts[i];
 }
Index: src/lalr.c
===================================================================
RCS file: /sources/bison/bison/src/lalr.c,v
retrieving revision 1.113
diff -p -u -r1.113 lalr.c
--- src/lalr.c  8 May 2007 05:03:53 -0000       1.113
+++ src/lalr.c  28 May 2007 01:02:09 -0000
@@ -459,22 +459,25 @@ lalr_update_state_numbers (state_number 
   goto_number ngotos_reachable = 0;
   symbol_number nonterminal = 0;
   aver (nsyms == nvars + ntokens);
-  for (goto_number i = 0; i < ngotos; ++i)
-    {
-      while (i == goto_map[nonterminal])
-        goto_map[nonterminal++] = ngotos_reachable;
-      /* If old_to_new[from_state[i]] = nstates_old, remove this goto
-         entry.  */
-      if (old_to_new[from_state[i]] != nstates_old)
-        {
-          /* from_state[i] is not removed, so it and thus to_state[i] are
-             reachable, so to_state[i] != nstates_old.  */
-          aver (old_to_new[to_state[i]] != nstates_old);
-          from_state[ngotos_reachable] = old_to_new[from_state[i]];
-          to_state[ngotos_reachable] = old_to_new[to_state[i]];
-          ++ngotos_reachable;
-        }
-    }
+  {
+    goto_number i;
+    for (i = 0; i < ngotos; ++i)
+      {
+        while (i == goto_map[nonterminal])
+          goto_map[nonterminal++] = ngotos_reachable;
+        /* If old_to_new[from_state[i]] = nstates_old, remove this goto
+           entry.  */
+        if (old_to_new[from_state[i]] != nstates_old)
+          {
+            /* from_state[i] is not removed, so it and thus to_state[i] are
+               reachable, so to_state[i] != nstates_old.  */
+            aver (old_to_new[to_state[i]] != nstates_old);
+            from_state[ngotos_reachable] = old_to_new[from_state[i]];
+            to_state[ngotos_reachable] = old_to_new[to_state[i]];
+            ++ngotos_reachable;
+          }
+      }
+  }
   while (nonterminal <= nvars)
     {
       aver (ngotos == goto_map[nonterminal]);
Index: src/reader.c
===================================================================
RCS file: /sources/bison/bison/src/reader.c,v
retrieving revision 1.283
diff -p -u -r1.283 reader.c
--- src/reader.c        11 Feb 2007 07:34:26 -0000      1.283
+++ src/reader.c        28 May 2007 01:02:11 -0000
@@ -640,8 +640,11 @@ check_and_convert_grammar (void)
      rule.  For the same reason, all the `used' flags must be set before
      checking whether to remove `$' from any midrule symbol name (also in
      packgram).  */
-  for (symbol_list *sym = grammar; sym; sym = sym->next)
-    code_props_translate_code (&sym->action_props);
+  {
+    symbol_list *sym;
+    for (sym = grammar; sym; sym = sym->next)
+      code_props_translate_code (&sym->action_props);
+  }
 
   /* Convert the grammar into the format described in gram.h.  */
   packgram ();
Index: src/state.c
===================================================================
RCS file: /sources/bison/bison/src/state.c,v
retrieving revision 1.44
diff -p -u -r1.44 state.c
--- src/state.c 8 May 2007 05:03:53 -0000       1.44
+++ src/state.c 28 May 2007 01:02:11 -0000
@@ -145,7 +145,6 @@ state_new (symbol_number accessing_symbo
   res->errs = NULL;
   res->consistent = 0;
   res->solved_conflicts = NULL;
-  res->reachable = false;
 
   res->nitems = nitems;
   memcpy (res->items, core, items_size);
@@ -354,41 +353,49 @@ state_hash_lookup (size_t nitems, item_n
 }
 
 
-/*------------------------------------------------------.
-| Mark S and all states reachable from S as reachable.  |
-`------------------------------------------------------*/
+/*--------------------------------------------------------.
+| Record S and all states reachable from S in REACHABLE.  |
+`--------------------------------------------------------*/
 
 static void
-state_mark_reachable_states (state *s)
+state_record_reachable_states (state *s, bitset reachable)
 {
-  if (s->reachable)
+  if (bitset_test (reachable, s->number))
     return;
-  s->reachable = true;
-  for (int i = 0; i < s->transitions->num; ++i)
-    if (!TRANSITION_IS_DISABLED (s->transitions, i))
-      state_mark_reachable_states (s->transitions->states[i]);
+  bitset_set (reachable, s->number);
+  {
+    int i;
+    for (i = 0; i < s->transitions->num; ++i)
+      if (!TRANSITION_IS_DISABLED (s->transitions, i))
+        state_record_reachable_states (s->transitions->states[i], reachable);
+  }
 }
 
 void
 state_remove_unreachable_states (state_number old_to_new[])
 {
   state_number nstates_reachable = 0;
-  state_mark_reachable_states (states[0]);
-  for (state_number i = 0; i < nstates; ++i)
-    {
-      if (states[i]->reachable)
-        {
-          states[nstates_reachable] = states[i];
-          states[nstates_reachable]->number = nstates_reachable;
-          old_to_new[i] = nstates_reachable++;
-        }
-      else
-        {
-          state_free (states[i]);
-          old_to_new[i] = nstates;
-        }
-    }
+  bitset reachable = bitset_create (nstates, BITSET_FIXED);
+  state_record_reachable_states (states[0], reachable);
+  {
+    state_number i;
+    for (i = 0; i < nstates; ++i)
+      {
+        if (bitset_test (reachable, states[i]->number))
+          {
+            states[nstates_reachable] = states[i];
+            states[nstates_reachable]->number = nstates_reachable;
+            old_to_new[i] = nstates_reachable++;
+          }
+        else
+          {
+            state_free (states[i]);
+            old_to_new[i] = nstates;
+          }
+      }
+  }
   nstates = nstates_reachable;
+  bitset_free (reachable);
 }
 
 /* All the decorated states, indexed by the state number.  */
Index: src/state.h
===================================================================
RCS file: /sources/bison/bison/src/state.h,v
retrieving revision 1.53
diff -p -u -r1.53 state.h
--- src/state.h 8 May 2007 05:03:53 -0000       1.53
+++ src/state.h 28 May 2007 01:02:11 -0000
@@ -209,11 +209,6 @@ struct state
      a human readable description of the resolution.  */
   const char *solved_conflicts;
 
-  /* Conflict resolution sometimes makes states unreachable.  Initialized to 0
-     in state_new and then used by state_remove_unreachable_states after
-     conflicts_solve.  */
-  bool reachable;
-
   /* Its items.  Must be last, since ITEMS can be arbitrarily large.
      */
   size_t nitems;