cex: fix state-item pruning

There were several bugs in pruning that would leave the state-item
graph in an inconsistent state which could cause crashes later on:

- Pruning now happens in one pass instead of two.

- Disabled state-items no longer prune the state-items they transition
  to if that state-item has other states that transition to it.

- State-items that transition to disabled state-items are always
  pruned even if they have productions.

Reported by Michal Bartkowiak <michal.bartkowiak@nokia.com>
https://lists.gnu.org/r/bug-bison/2021-01/msg00000.html
and Zartaj Majeed
https://github.com/akimd/bison/issues/71

* src/state-item.c (prune_forward, prune_backward): Fuse into...
(prune_state_item): this.
Adjust callers.

1 files changed, 22 insertions, 37 deletions

diff --git a/src/state-item.c b/src/state-item.c
index d8957c8e..a2e0f957 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -384,11 +384,10 @@ disable_state_item (state_item *si)
     bitset_free (si->prods);
 }
 
-/* disable all transitions and productions that can only be
- * reached through this state_item.
- */
+/* Disable all state_item paths that lead to/from SI and nowhere
+   else.  */
 static void
-prune_forward (const state_item *si)
+prune_state_item (const state_item *si)
 {
   state_item_list queue =
     gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
@@ -398,8 +397,16 @@ prune_forward (const state_item *si)
     {
       state_item *dsi = (state_item *) gl_list_get_at (queue, 0);
       gl_list_remove_at (queue, 0);
-      if (dsi->trans >= 0)
-        gl_list_add_last (queue, &state_items[dsi->trans]);
+      if (SI_DISABLED (dsi - state_items))
+        continue;
+
+      if (dsi->trans >= 0 && !SI_DISABLED (dsi->trans))
+      {
+        const state_item *trans = &state_items[dsi->trans];
+        bitset_reset (trans->revs, dsi - state_items);
+        if (bitset_empty_p (trans->revs))
+          gl_list_add_last (queue, trans);
+      }
 
       if (dsi->prods)
         {
@@ -407,32 +414,15 @@ prune_forward (const state_item *si)
           state_item_number sin;
           BITSET_FOR_EACH (biter, dsi->prods, sin, 0)
             {
+              if (SI_DISABLED (sin))
+                continue;
               const state_item *prod = &state_items[sin];
               bitset_reset (prod->revs, dsi - state_items);
               if (bitset_empty_p (prod->revs))
                 gl_list_add_last (queue, prod);
             }
         }
-      if (dsi != si)
-        disable_state_item (dsi);
-    }
-  gl_list_free (queue);
-}
 
-/* disable all state_item paths that lead to
- * si and nowhere else.
- */
-static void
-prune_backward (const state_item *si)
-{
-  state_item_list queue =
-    gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
-                    (const void **) &si);
-
-  while (gl_list_size (queue) > 0)
-    {
-      state_item *dsi = (state_item *) gl_list_get_at (queue, 0);
-      gl_list_remove_at (queue, 0);
       bitset_iterator biter;
       state_item_number sin;
       BITSET_FOR_EACH (biter, dsi->revs, sin, 0)
@@ -440,7 +430,9 @@ prune_backward (const state_item *si)
           if (SI_DISABLED (sin))
             continue;
           state_item *rev = &state_items[sin];
-          if (rev->prods)
+          if (&state_items[rev->trans] == dsi)
+            gl_list_add_last (queue, rev);
+          else if (rev->prods)
             {
               bitset_reset (rev->prods, dsi - state_items);
               if (bitset_empty_p (rev->prods))
@@ -449,16 +441,13 @@ prune_backward (const state_item *si)
           else
             gl_list_add_last (queue, rev);
         }
-      if (dsi != si)
-        disable_state_item (dsi);
+      disable_state_item (dsi);
     }
   gl_list_free (queue);
 }
 
-/*
- To make searches more efficient, we can prune away paths that are
- caused by disabled transitions.
- */
+/* To make searches more efficient, prune away paths that are caused
+   by disabled transitions.  */
 static void
 prune_disabled_paths (void)
 {
@@ -466,11 +455,7 @@ prune_disabled_paths (void)
     {
       state_item *si = &state_items[i];
       if (si->trans == -1 && item_number_is_symbol_number (*si->item))
-        {
-          prune_forward (si);
-          prune_backward (si);
-          disable_state_item (si);
-        }
+        prune_state_item (si);
     }
 }