[PATCH] cex: Fix state-item pruning

[Vincent Imbimbo]

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.

---
 src/state-item.c | 50 +++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 30 deletions(-)

diff --git a/src/state-item.c b/src/state-item.c
index 2fa519ed..9507443d 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -384,11 +384,11 @@ 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 +398,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 +415,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 +431,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,8 +442,7 @@ 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);
 }
@@ -467,9 +459,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);
         }
     }
 }
-- 
2.24.3 (Apple Git-128)