Re: [PATCH] cex: fix pruning crash

[Akim Demaille]

Hi Vincent,

Thanks a lot for the after-sales service!

I confirm it still passes the whole test suite with ASAN and leak detection, 
and passes properly on the GNU Cim grammar.

Installed as follows in master.

commit 50cd3f16debae7ea727901ff1350fdf4e5284a07
Author: Vincent Imbimbo <address@hidden>
Date:   Sat May 23 11:20:46 2020 -0400

    cex: fix pruning crash
    
    Fixes a crash on Cim's grammar.
    https://lists.gnu.org/r/bison-patches/2020-05/msg00107.html
    
    * src/state-item.c (prune_disabled_paths): Prune forward and backwards
    paths in seperate passes.
    (prune_forward, prune_backward): New.
    (disable_state_item): Change function argument from state_item_number
    to state_item.
    (state_items_report): Add disabling to graph print-out.
    * src/conflicts.c (find_state_item_number,
    report_state_counterexamples): Add SI_DISABLED checks.

diff --git a/src/conflicts.c b/src/conflicts.c
index 63b07d47..ddea8366 100644
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -361,7 +361,8 @@ set_conflicts (state *s, symbol **errors)
      check for shift-reduce conflict, and try to resolve using
      precedence.  */
   for (int i = 0; i < reds->num; ++i)
-    if (reds->rules[i]->prec && reds->rules[i]->prec->prec
+    if (reds->rules[i]->prec
+        && reds->rules[i]->prec->prec
         && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
       resolve_sr_conflict (s, i, errors, &nerrs);
 
@@ -629,7 +630,8 @@ static state_item_number
 find_state_item_number (const rule *r, state_number sn)
 {
   for (int i = state_item_map[sn]; i < state_item_map[sn + 1]; ++i)
-    if (item_number_as_rule_number (*state_items[i].item) == r->number)
+    if (!SI_DISABLED (i)
+        && item_number_as_rule_number (*state_items[i].item) == r->number)
       return i;
   abort ();
 }
@@ -649,8 +651,8 @@ report_state_counterexamples (const state *s)
             continue;
           state_item *si = state_items + j;
           item_number conf = *si->item;
-          if (item_number_is_symbol_number (conf) &&
-              bitset_test (reds->lookahead_tokens[i], conf))
+          if (item_number_is_symbol_number (conf)
+              && bitset_test (reds->lookahead_tokens[i], conf))
             {
               counterexample_report_shift_reduce (c1, j, conf);
               break;
@@ -668,6 +670,8 @@ report_state_counterexamples (const state *s)
               for (int k = state_item_map[sn];
                    k < state_item_map[sn + 1]; ++k)
                 {
+                  if (SI_DISABLED (k))
+                    continue;
                   state_item *si = state_items + k;
                   const rule *r = item_rule (si->item);
                   if (r == r2)
diff --git a/src/state-item.c b/src/state-item.c
index 90e473a5..691ce015 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -378,15 +378,85 @@ init_firsts (void)
 }
 
 static inline void
-disable_state_item (state_item_number sin)
+disable_state_item (state_item *si)
 {
-  state_item *si = state_items + sin;
   si->trans = -2;
   bitset_free (si->revs);
   if (si->prods)
     bitset_free (si->prods);
 }
 
+/* disable all transitions and productions that can only be
+ * reached through this state_item.
+ */
+static void
+prune_forward (const state_item *si)
+{
+  gl_list_t 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);
+      if (dsi->trans >= 0)
+        gl_list_add_last (queue, state_items + dsi->trans);
+
+      if (dsi->prods)
+        {
+          bitset_iterator biter;
+          state_item_number sin;
+          BITSET_FOR_EACH (biter, dsi->prods, sin, 0)
+            {
+              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)
+{
+  gl_list_t 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)
+        {
+          if (SI_DISABLED (sin))
+            continue;
+          state_item *rev = state_items + sin;
+          if (rev->prods)
+            {
+              bitset_reset (rev->prods, dsi - state_items);
+              if (bitset_empty_p (rev->prods))
+                gl_list_add_last (queue, rev);
+            }
+          else
+            gl_list_add_last (queue, rev);
+        }
+      if (dsi != si)
+        disable_state_item (dsi);
+    }
+  gl_list_free (queue);
+}
+
 /*
  To make searches more efficient, we can prune away paths that are
  caused by disabled transitions.
@@ -399,40 +469,9 @@ prune_disabled_paths (void)
       state_item *si = state_items + i;
       if (si->trans == -1 && item_number_is_symbol_number (*si->item))
         {
-          // disable the transitions out of i
-          for (state_item_number j = si->trans; j != -1; j = 
state_items[j].trans)
-            disable_state_item (j);
-
-          gl_list_t queue =
-            gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
-                            (const void **) &si);
-
-          // For each disabled transition, traverse through all state_items
-          // accessible through reverse transition steps, and set their
-          // lookaheads to the reduction items lookahead
-          while (gl_list_size (queue) > 0)
-            {
-              const state_item *prev = gl_list_get_at (queue, 0);
-              gl_list_remove_at (queue, 0);
-              state_item_number prev_num = prev - state_items;
-
-              bitset rsi = prev->revs;
-              bitset_iterator biter;
-              state_item_number sin;
-              BITSET_FOR_EACH (biter, rsi, sin, 0)
-              {
-                if (SI_TRANSITION (prev))
-                  gl_list_add_first (queue, &state_items[sin]);
-                else
-                  {
-                    bitset p = state_items[sin].prods;
-                    if (p)
-                      bitset_reset (p, prev_num);
-                  }
-              }
-              disable_state_item (prev_num);
-            }
-          gl_list_free (queue);
+          prune_forward (si);
+          prune_backward (si);
+          disable_state_item (si);
         }
     }
 }
@@ -459,6 +498,12 @@ state_items_report (void)
         {
           state_item *si = state_items + j;
           item_print (si->item, NULL, stdout);
+          if (SI_DISABLED (j))
+            {
+              item_print (si->item, NULL, stdout);
+              puts (" DISABLED");
+              continue;
+            }
           puts ("");
           if (si->trans >= 0)
             {