Hi Vincent, > Le 23 janv. 2021 à 19:25, Vincent Imbimbo <[email protected]> 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 <[email protected]> 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 <[email protected]> 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); } }
