Re: [PATCH] cex: Fix state-item pruning

[Akim Demaille]

Hi Vincent,

> Le 23 janv. 2021 à 19:25, Vincent Imbimbo <vmi6@cornell.edu> a écrit :
> 
> 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.

Wonderful!  Thanks a lot for this.  There's no way I could have found the right 
fix...

I'm installing your fix as follows, in the maint branch for 3.7.5.

Cheers!

commit 3b94105d213795ec4a2614e24abae970b6f4a7a1
Author: Vincent Imbimbo <vmi6@cornell.edu>
Date:   Sat Jan 23 13:25:18 2021 -0500

    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.

diff --git a/NEWS b/NEWS
index 4664e401c..720f2b1db 100644
--- a/NEWS
+++ b/NEWS
@@ -4,7 +4,11 @@ GNU Bison NEWS
 
 ** Bug fixes
 
-*** Fix table generation
+*** Counterexample Generation
+
+  In some cases counterexample generation could crash.  This is fixed.
+
+*** Fix Table Generation
 
   In some very rare conditions, when there are many useless tokens, it was
   possible to generate incorrect parsers.
diff --git a/src/state-item.c b/src/state-item.c
index d8957c8eb..a2e0f9575 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);
     }
 }