| /* Conflict counterexample generation |
| |
| Copyright (C) 2020-2021 Free Software Foundation, Inc. |
| |
| This file is part of Bison, the GNU Compiler Compiler. |
| |
| This program is free software: you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation, either version 3 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| |
| #include <config.h> |
| |
| #include "counterexample.h" |
| |
| #include "system.h" |
| |
| #include <errno.h> |
| #include <gl_linked_list.h> |
| #include <gl_rbtreehash_list.h> |
| #include <hash.h> |
| #include <mbswidth.h> |
| #include <stdlib.h> |
| #include <textstyle.h> |
| #include <time.h> |
| |
| #include "closure.h" |
| #include "complain.h" |
| #include "derivation.h" |
| #include "getargs.h" |
| #include "gram.h" |
| #include "lalr.h" |
| #include "lssi.h" |
| #include "nullable.h" |
| #include "parse-simulation.h" |
| |
| |
| #define TIME_LIMIT_ENFORCED true |
| /** If set to false, only consider the states on the shortest |
| * lookahead-sensitive path when constructing a unifying counterexample. */ |
| #define EXTENDED_SEARCH false |
| |
| /* costs for making various steps in a search */ |
| #define PRODUCTION_COST 50 |
| #define REDUCE_COST 1 |
| #define SHIFT_COST 1 |
| #define UNSHIFT_COST 1 |
| #define EXTENDED_COST 10000 |
| |
| /** The time limit before printing an assurance message to the user to |
| * indicate that the search is still running. */ |
| #define ASSURANCE_LIMIT 2.0 |
| |
| /* The time limit before giving up looking for unifying counterexample. */ |
| static double time_limit = 5.0; |
| |
| #define CUMULATIVE_TIME_LIMIT 120.0 |
| |
| // This is the fastest way to get the tail node from the gl_list API. |
| static gl_list_node_t |
| list_get_end (gl_list_t list) |
| { |
| gl_list_node_t sentinel = gl_list_add_last (list, NULL); |
| gl_list_node_t res = gl_list_previous_node (list, sentinel); |
| gl_list_remove_node (list, sentinel); |
| return res; |
| } |
| |
| typedef struct |
| { |
| derivation *d1; |
| derivation *d2; |
| bool shift_reduce; |
| bool unifying; |
| bool timeout; |
| } counterexample; |
| |
| static counterexample * |
| new_counterexample (derivation *d1, derivation *d2, |
| bool shift_reduce, |
| bool u, bool t) |
| { |
| counterexample *res = xmalloc (sizeof *res); |
| res->shift_reduce = shift_reduce; |
| if (shift_reduce) |
| { |
| // Display the shift first. |
| res->d1 = d2; |
| res->d2 = d1; |
| } |
| else |
| { |
| res->d1 = d1; |
| res->d2 = d2; |
| } |
| res->unifying = u; |
| res->timeout = t; |
| return res; |
| } |
| |
| static void |
| free_counterexample (counterexample *cex) |
| { |
| derivation_free (cex->d1); |
| derivation_free (cex->d2); |
| free (cex); |
| } |
| |
| static void |
| counterexample_print (const counterexample *cex, FILE *out, const char *prefix) |
| { |
| const bool flat = getenv ("YYFLAT"); |
| const char *example1_label |
| = cex->unifying ? _("Example") : _("First example"); |
| const char *example2_label |
| = cex->unifying ? _("Example") : _("Second example"); |
| const char *deriv1_label |
| = cex->shift_reduce ? _("Shift derivation") : _("First reduce derivation"); |
| const char *deriv2_label |
| = cex->shift_reduce ? _("Reduce derivation") : _("Second reduce derivation"); |
| const int width = |
| max_int (max_int (mbswidth (example1_label, 0), mbswidth (example2_label, 0)), |
| max_int (mbswidth (deriv1_label, 0), mbswidth (deriv2_label, 0))); |
| if (flat) |
| fprintf (out, " %s%s%*s ", prefix, |
| example1_label, width - mbswidth (example1_label, 0), ""); |
| else |
| fprintf (out, " %s%s: ", prefix, example1_label); |
| derivation_print_leaves (cex->d1, out); |
| if (flat) |
| fprintf (out, " %s%s%*s ", prefix, |
| deriv1_label, width - mbswidth (deriv1_label, 0), ""); |
| else |
| fprintf (out, " %s%s", prefix, deriv1_label); |
| derivation_print (cex->d1, out, prefix); |
| |
| // If we output to the terminal (via stderr) and we have color |
| // support, display unifying examples a second time, as color allows |
| // to see the differences. |
| if (!cex->unifying || is_styled (stderr)) |
| { |
| if (flat) |
| fprintf (out, " %s%s%*s ", prefix, |
| example2_label, width - mbswidth (example2_label, 0), ""); |
| else |
| fprintf (out, " %s%s: ", prefix, example2_label); |
| derivation_print_leaves (cex->d2, out); |
| } |
| if (flat) |
| fprintf (out, " %s%s%*s ", prefix, |
| deriv2_label, width - mbswidth (deriv2_label, 0), ""); |
| else |
| fprintf (out, " %s%s", prefix, deriv2_label); |
| derivation_print (cex->d2, out, prefix); |
| |
| if (out != stderr) |
| putc ('\n', out); |
| } |
| |
| /* |
| * |
| * NON UNIFYING COUNTER EXAMPLES |
| * |
| */ |
| |
| // Search node for BFS on state items |
| struct si_bfs_node; |
| typedef struct si_bfs_node |
| { |
| state_item_number si; |
| struct si_bfs_node *parent; |
| int reference_count; |
| } si_bfs_node; |
| |
| static si_bfs_node * |
| si_bfs_new (state_item_number si, si_bfs_node *parent) |
| { |
| si_bfs_node *res = xcalloc (1, sizeof *res); |
| res->si = si; |
| res->parent = parent; |
| res->reference_count = 1; |
| if (parent) |
| ++parent->reference_count; |
| return res; |
| } |
| |
| static bool |
| si_bfs_contains (const si_bfs_node *n, state_item_number sin) |
| { |
| for (const si_bfs_node *search = n; search != NULL; search = search->parent) |
| if (search->si == sin) |
| return true; |
| return false; |
| } |
| |
| static void |
| si_bfs_free (si_bfs_node *n) |
| { |
| if (n == NULL) |
| return; |
| --n->reference_count; |
| if (n->reference_count == 0) |
| { |
| si_bfs_free (n->parent); |
| free (n); |
| } |
| } |
| |
| typedef gl_list_t si_bfs_node_list; |
| |
| /** |
| * start is a state_item such that conflict_sym is an element of FIRSTS of the |
| * nonterminal after the dot in start. Because of this, we should be able to |
| * find a production item starting with conflict_sym by only searching productions |
| * of the nonterminal and shifting over nullable nonterminals |
| * |
| * this returns the derivation of the productions that lead to conflict_sym |
| */ |
| static inline derivation_list |
| expand_to_conflict (state_item_number start, symbol_number conflict_sym) |
| { |
| si_bfs_node *init = si_bfs_new (start, NULL); |
| |
| si_bfs_node_list queue |
| = gl_list_create (GL_LINKED_LIST, NULL, NULL, |
| (gl_listelement_dispose_fn) si_bfs_free, |
| true, 1, (const void **) &init); |
| si_bfs_node *node = NULL; |
| // breadth-first search for a path of productions to the conflict symbol |
| while (gl_list_size (queue) > 0) |
| { |
| node = (si_bfs_node *) gl_list_get_at (queue, 0); |
| state_item *silast = &state_items[node->si]; |
| symbol_number sym = item_number_as_symbol_number (*silast->item); |
| if (sym == conflict_sym) |
| break; |
| if (ISVAR (sym)) |
| { |
| // add each production to the search |
| bitset_iterator biter; |
| state_item_number sin; |
| bitset sib = silast->prods; |
| BITSET_FOR_EACH (biter, sib, sin, 0) |
| { |
| // ignore productions already in the path |
| if (si_bfs_contains (node, sin)) |
| continue; |
| si_bfs_node *next = si_bfs_new (sin, node); |
| gl_list_add_last (queue, next); |
| } |
| // for nullable nonterminals, add its goto to the search |
| if (nullable[sym - ntokens]) |
| { |
| si_bfs_node *next = si_bfs_new (silast->trans, node); |
| gl_list_add_last (queue, next); |
| } |
| } |
| gl_list_remove_at (queue, 0); |
| } |
| if (gl_list_size (queue) == 0) |
| { |
| gl_list_free (queue); |
| fputs ("Error expanding derivation\n", stderr); |
| abort (); |
| } |
| |
| derivation *dinit = derivation_new_leaf (conflict_sym); |
| derivation_list result = derivation_list_new (); |
| derivation_list_append (result, dinit); |
| // iterate backwards through the generated path to create a derivation |
| // of the conflict symbol containing derivations of each production step. |
| |
| for (si_bfs_node *n = node; n != NULL; n = n->parent) |
| { |
| state_item *si = &state_items[n->si]; |
| item_number *pos = si->item; |
| if (SI_PRODUCTION (si)) |
| { |
| item_number *i = NULL; |
| for (i = pos + 1; !item_number_is_rule_number (*i); ++i) |
| derivation_list_append (result, derivation_new_leaf (*i)); |
| symbol_number lhs = |
| rules[item_number_as_rule_number (*i)].lhs->number; |
| derivation *deriv = derivation_new (lhs, result, |
| state_item_rule (si)); |
| result = derivation_list_new (); |
| derivation_list_append (result, deriv); |
| } |
| else |
| { |
| symbol_number sym = item_number_as_symbol_number (*(pos - 1)); |
| derivation *deriv = derivation_new_leaf (sym); |
| derivation_list_prepend (result, deriv); |
| } |
| } |
| gl_list_free (queue); |
| derivation_free ((derivation*)gl_list_get_at (result, 0)); |
| gl_list_remove_at (result, 0); |
| return result; |
| } |
| |
| /** |
| * Complete derivations for any pending productions in the given |
| * sequence of state-items. For example, the input could be a path |
| * of states that would give us the following input: |
| * Stmt ::= [lval ::= [VAR] '=' e ::=[ e::=['0'] '+' • |
| * So to complete the derivation of Stmt, we need an output like: |
| * Stmt ::= [lval ::= [VAR] '=' e ::=[ e::=['0'] '+' • e ] ';' ] |
| */ |
| static derivation * |
| complete_diverging_example (symbol_number conflict_sym, |
| state_item_list path, derivation_list derivs) |
| { |
| // The idea is to transfer each pending symbol on the productions |
| // associated with the given StateItems to the resulting derivation. |
| derivation_list result = derivation_list_new (); |
| bool lookahead_required = false; |
| if (!derivs) |
| { |
| derivs = derivation_list_new (); |
| gl_list_add_last (result, derivation_dot ()); |
| lookahead_required = true; |
| } |
| |
| gl_list_node_t deriv = list_get_end (derivs); |
| |
| // We go backwards through the path to create the derivation tree bottom-up. |
| // Effectively this loops through each production once, and generates a |
| // derivation of the left hand side by appending all of the rhs symbols. |
| // this becomes the derivation of the nonterminal after the dot in the |
| // next production, and all of the other symbols of the rule are added as normal. |
| for (gl_list_node_t state_node = list_get_end (path); |
| state_node != NULL; |
| state_node = gl_list_previous_node (path, state_node)) |
| { |
| state_item *si = (state_item *) gl_list_node_value (path, state_node); |
| item_number *item = si->item; |
| item_number pos = *item; |
| // symbols after dot |
| if (gl_list_size (result) == 1 && !item_number_is_rule_number (pos) |
| && gl_list_get_at (result, 0) == derivation_dot ()) |
| { |
| derivation_list_append (result, |
| derivation_new_leaf (item_number_as_symbol_number (pos))); |
| lookahead_required = false; |
| } |
| item_number *i = item; |
| // go through each symbol after the dot in the current rule, and |
| // add each symbol to its derivation. |
| for (state_item_number nsi = si - state_items; |
| !item_number_is_rule_number (*i); |
| ++i, nsi = state_items[nsi].trans) |
| { |
| // if the item is a reduction, we could skip to the wrong rule |
| // by starting at i + 1, so this continue is necessary |
| if (i == item) |
| continue; |
| symbol_number sym = item_number_as_symbol_number (*i); |
| if (!lookahead_required || sym == conflict_sym) |
| { |
| derivation_list_append (result, derivation_new_leaf (sym)); |
| lookahead_required = false; |
| continue; |
| } |
| // Since PATH is a path to the conflict state-item, |
| // for a reduce conflict item, we will want to have a derivation |
| // that shows the conflict symbol from its lookahead set being used. |
| // |
| // Since reductions have the dot at the end of the item, |
| // this loop will be first executed on the last item in the path |
| // that's not a reduction. When that happens, |
| // the symbol after the dot should be a nonterminal, |
| // and we can look through successive nullable nonterminals |
| // for one with the conflict symbol in its first set. |
| if (bitset_test (FIRSTS (sym), conflict_sym)) |
| { |
| lookahead_required = false; |
| derivation_list next_derivs = |
| expand_to_conflict (nsi, conflict_sym); |
| derivation *d = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (next_derivs); |
| derivation_list_next (&it, &d);) |
| derivation_list_append (result, d); |
| i += gl_list_size (next_derivs) - 1; |
| derivation_list_free (next_derivs); |
| } |
| else if (nullable[sym - ntokens]) |
| { |
| derivation *d = derivation_new_leaf (sym); |
| derivation_list_append (result, d); |
| } |
| else |
| { |
| // We found a path to the conflict item, and despite it |
| // having the conflict symbol in its lookahead, no example |
| // containing the symbol after the conflict item |
| // can be found. |
| derivation_list_append (result, derivation_new_leaf (1)); |
| lookahead_required = false; |
| } |
| } |
| const rule *r = &rules[item_number_as_rule_number (*i)]; |
| // add derivations for symbols before dot |
| for (i = item - 1; !item_number_is_rule_number (*i) && i >= ritem; i--) |
| { |
| gl_list_node_t p = gl_list_previous_node (path, state_node); |
| if (p) |
| state_node = p; |
| if (deriv) |
| { |
| const void *tmp_deriv = gl_list_node_value (derivs, deriv); |
| deriv = gl_list_previous_node (derivs, deriv); |
| derivation_list_prepend (result, (derivation*)tmp_deriv); |
| } |
| else |
| derivation_list_prepend (result, derivation_new_leaf (*i)); |
| } |
| // completing the derivation |
| derivation *new_deriv = derivation_new (r->lhs->number, result, r); |
| result = derivation_list_new (); |
| derivation_list_append (result, new_deriv); |
| } |
| derivation *res = (derivation *) gl_list_get_at (result, 0); |
| derivation_retain (res); |
| derivation_list_free (result); |
| derivation_list_free (derivs); |
| return res; |
| } |
| |
| /* Iterate backwards through the shifts of the path in the reduce |
| conflict, and find a path of shifts from the shift conflict that |
| goes through the same states. */ |
| static state_item_list |
| nonunifying_shift_path (state_item_list reduce_path, state_item *shift_conflict) |
| { |
| gl_list_node_t tmp = gl_list_add_last (reduce_path, NULL); |
| gl_list_node_t next_node = gl_list_previous_node (reduce_path, tmp); |
| gl_list_node_t node = gl_list_previous_node (reduce_path, next_node); |
| gl_list_remove_node (reduce_path, tmp); |
| state_item *si = shift_conflict; |
| state_item_list result = |
| gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true); |
| // FIXME: bool paths_merged; |
| for (; node != NULL; next_node = node, |
| node = gl_list_previous_node (reduce_path, node)) |
| { |
| state_item *refsi = |
| (state_item *) gl_list_node_value (reduce_path, node); |
| state_item *nextrefsi = |
| (state_item *) gl_list_node_value (reduce_path, next_node); |
| if (nextrefsi == si) |
| { |
| gl_list_add_first (result, refsi); |
| si = refsi; |
| continue; |
| } |
| // skip reduction items |
| if (nextrefsi->item != refsi->item + 1 && refsi->item != ritem) |
| continue; |
| |
| // bfs to find a shift to the right state |
| si_bfs_node *init = si_bfs_new (si - state_items, NULL); |
| si_bfs_node_list queue |
| = gl_list_create (GL_LINKED_LIST, NULL, NULL, |
| (gl_listelement_dispose_fn) si_bfs_free, |
| true, 1, (const void **) &init); |
| si_bfs_node *sis = NULL; |
| state_item *prevsi = NULL; |
| while (gl_list_size (queue) > 0) |
| { |
| sis = (si_bfs_node *) gl_list_get_at (queue, 0); |
| // if we end up in the start state, the shift couldn't be found. |
| if (sis->si == 0) |
| break; |
| |
| state_item *search_si = &state_items[sis->si]; |
| // if the current state-item is a production item, |
| // its reverse production items get added to the queue. |
| // Otherwise, look for a reverse transition to the target state. |
| bitset rsi = search_si->revs; |
| bitset_iterator biter; |
| state_item_number sin; |
| BITSET_FOR_EACH (biter, rsi, sin, 0) |
| { |
| prevsi = &state_items[sin]; |
| if (SI_TRANSITION (search_si)) |
| { |
| if (prevsi->state == refsi->state) |
| goto search_end; |
| } |
| else if (!si_bfs_contains (sis, sin)) |
| { |
| si_bfs_node *prevsis = si_bfs_new (sin, sis); |
| gl_list_add_last (queue, prevsis); |
| } |
| } |
| gl_list_remove_at (queue, 0); |
| } |
| search_end: |
| // prepend path to shift we found |
| if (sis) |
| { |
| gl_list_node_t ln = gl_list_add_first (result, &state_items[sis->si]); |
| for (si_bfs_node *n = sis->parent; n; n = n->parent) |
| ln = gl_list_add_after (result, ln, &state_items[n->si]); |
| |
| } |
| si = prevsi; |
| gl_list_free (queue); |
| } |
| if (trace_flag & trace_cex) |
| { |
| fputs ("SHIFT ITEM PATH:\n", stderr); |
| state_item *sip = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (result); |
| state_item_list_next (&it, &sip); |
| ) |
| state_item_print (sip, stderr, ""); |
| } |
| return result; |
| } |
| |
| |
| /** |
| * Construct a nonunifying counterexample from the shortest |
| * lookahead-sensitive path. |
| */ |
| static counterexample * |
| example_from_path (bool shift_reduce, |
| state_item_number itm2, |
| state_item_list shortest_path, symbol_number next_sym) |
| { |
| derivation *deriv1 = |
| complete_diverging_example (next_sym, shortest_path, NULL); |
| state_item_list path_2 |
| = shift_reduce |
| ? nonunifying_shift_path (shortest_path, &state_items [itm2]) |
| : shortest_path_from_start (itm2, next_sym); |
| derivation *deriv2 = complete_diverging_example (next_sym, path_2, NULL); |
| gl_list_free (path_2); |
| return new_counterexample (deriv1, deriv2, shift_reduce, false, true); |
| } |
| |
| /* |
| * |
| * UNIFYING COUNTER EXAMPLES |
| * |
| */ |
| |
| /* A search state keeps track of two parser simulations, |
| * one starting at each conflict. Complexity is a metric |
| * which sums different parser actions with varying weights. |
| */ |
| typedef struct |
| { |
| parse_state *states[2]; |
| int complexity; |
| } search_state; |
| |
| static search_state * |
| initial_search_state (state_item *conflict1, state_item *conflict2) |
| { |
| search_state *res = xmalloc (sizeof *res); |
| res->states[0] = new_parse_state (conflict1); |
| res->states[1] = new_parse_state (conflict2); |
| parse_state_retain (res->states[0]); |
| parse_state_retain (res->states[1]); |
| res->complexity = 0; |
| return res; |
| } |
| |
| static search_state * |
| new_search_state (parse_state *ps1, parse_state *ps2, int complexity) |
| { |
| search_state *res = xmalloc (sizeof *res); |
| res->states[0] = ps1; |
| res->states[1] = ps2; |
| parse_state_retain (res->states[0]); |
| parse_state_retain (res->states[1]); |
| res->complexity = complexity; |
| return res; |
| } |
| |
| static search_state * |
| copy_search_state (search_state *parent) |
| { |
| search_state *res = xmalloc (sizeof *res); |
| *res = *parent; |
| parse_state_retain (res->states[0]); |
| parse_state_retain (res->states[1]); |
| return res; |
| } |
| |
| static void |
| search_state_free_children (search_state *ss) |
| { |
| free_parse_state (ss->states[0]); |
| free_parse_state (ss->states[1]); |
| } |
| |
| static void |
| search_state_free (search_state *ss) |
| { |
| if (ss == NULL) |
| return; |
| search_state_free_children (ss); |
| free (ss); |
| } |
| |
| /* For debugging traces. */ |
| static void |
| search_state_print (search_state *ss) |
| { |
| fputs ("CONFLICT 1 ", stderr); |
| print_parse_state (ss->states[0]); |
| fputs ("CONFLICT 2 ", stderr); |
| print_parse_state (ss->states[1]); |
| putc ('\n', stderr); |
| } |
| |
| typedef gl_list_t search_state_list; |
| |
| static inline bool |
| search_state_list_next (gl_list_iterator_t *it, search_state **ss) |
| { |
| const void *p = NULL; |
| bool res = gl_list_iterator_next (it, &p, NULL); |
| if (res) |
| *ss = (search_state*) p; |
| else |
| gl_list_iterator_free (it); |
| return res; |
| } |
| |
| /* |
| * When a search state is copied, this is used to |
| * directly set one of the parse states |
| */ |
| static inline void |
| ss_set_parse_state (search_state *ss, int idx, parse_state *ps) |
| { |
| free_parse_state (ss->states[idx]); |
| ss->states[idx] = ps; |
| parse_state_retain (ps); |
| } |
| |
| /* |
| * Construct a nonunifying example from a search state |
| * which has its parse states unified at the beginning |
| * but not the end of the example. |
| */ |
| static counterexample * |
| complete_diverging_examples (search_state *ss, |
| symbol_number next_sym, |
| bool shift_reduce) |
| { |
| derivation *new_derivs[2]; |
| for (int i = 0; i < 2; ++i) |
| { |
| state_item_list sitems; |
| derivation_list derivs; |
| parse_state_lists (ss->states[i], &sitems, &derivs); |
| new_derivs[i] = complete_diverging_example (next_sym, sitems, derivs); |
| gl_list_free (sitems); |
| } |
| return new_counterexample (new_derivs[0], new_derivs[1], |
| shift_reduce, false, true); |
| } |
| |
| /* |
| * Search states are stored in bundles with those that |
| * share the same complexity. This is so the priority |
| * queue takes less overhead. |
| */ |
| typedef struct |
| { |
| search_state_list states; |
| int complexity; |
| } search_state_bundle; |
| |
| static void |
| ssb_free (search_state_bundle *ssb) |
| { |
| gl_list_free (ssb->states); |
| free (ssb); |
| } |
| |
| static size_t |
| ssb_hasher (search_state_bundle *ssb) |
| { |
| return ssb->complexity; |
| } |
| |
| static int |
| ssb_comp (const search_state_bundle *s1, const search_state_bundle *s2) |
| { |
| return s1->complexity - s2->complexity; |
| } |
| |
| static bool |
| ssb_equals (const search_state_bundle *s1, const search_state_bundle *s2) |
| { |
| return s1->complexity == s2->complexity; |
| } |
| |
| typedef gl_list_t ssb_list; |
| |
| static size_t |
| visited_hasher (const search_state *ss, size_t max) |
| { |
| return (parse_state_hasher (ss->states[0], max) |
| + parse_state_hasher (ss->states[1], max)) % max; |
| } |
| |
| static bool |
| visited_comparator (const search_state *ss1, const search_state *ss2) |
| { |
| return parse_state_comparator (ss1->states[0], ss2->states[0]) |
| && parse_state_comparator (ss1->states[1], ss2->states[1]); |
| } |
| |
| /* Priority queue for search states with minimal complexity. */ |
| static ssb_list ssb_queue; |
| static Hash_table *visited; |
| /* The set of parser states on the shortest lookahead-sensitive path. */ |
| static bitset scp_set = NULL; |
| /* The set of parser states used for the conflict reduction rule. */ |
| static bitset rpp_set = NULL; |
| |
| static void |
| ssb_append (search_state *ss) |
| { |
| if (hash_lookup (visited, ss)) |
| { |
| search_state_free (ss); |
| return; |
| } |
| hash_xinsert (visited, ss); |
| // if states are only referenced by the visited set, |
| // their contents should be freed as we only need |
| // the metadata necessary to compute a hash. |
| parse_state_free_contents_early (ss->states[0]); |
| parse_state_free_contents_early (ss->states[1]); |
| parse_state_retain (ss->states[0]); |
| parse_state_retain (ss->states[1]); |
| search_state_bundle *ssb = xmalloc (sizeof *ssb); |
| ssb->complexity = ss->complexity; |
| gl_list_node_t n = gl_list_search (ssb_queue, ssb); |
| if (!n) |
| { |
| ssb->states = |
| gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, |
| (gl_listelement_dispose_fn)search_state_free_children, |
| true); |
| gl_sortedlist_add (ssb_queue, (gl_listelement_compar_fn) ssb_comp, ssb); |
| } |
| else |
| { |
| free (ssb); |
| ssb = (search_state_bundle *) gl_list_node_value (ssb_queue, n); |
| } |
| gl_list_add_last (ssb->states, ss); |
| } |
| |
| /* |
| * The following functions perform various actions on parse states |
| * and assign complexities to the newly generated search states. |
| */ |
| static void |
| production_step (search_state *ss, int parser_state) |
| { |
| const state_item *other_si = parse_state_tail (ss->states[1 - parser_state]); |
| symbol_number other_sym = item_number_as_symbol_number (*other_si->item); |
| parse_state_list prods = |
| simulate_production (ss->states[parser_state], other_sym); |
| int complexity = ss->complexity + PRODUCTION_COST; |
| |
| parse_state *ps = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (prods); |
| parse_state_list_next (&it, &ps); |
| ) |
| { |
| search_state *copy = copy_search_state (ss); |
| ss_set_parse_state (copy, parser_state, ps); |
| copy->complexity = complexity; |
| ssb_append (copy); |
| } |
| gl_list_free (prods); |
| } |
| |
| static inline int |
| reduction_cost (const parse_state *ps) |
| { |
| int shifts; |
| int productions; |
| parse_state_completed_steps (ps, &shifts, &productions); |
| return SHIFT_COST * shifts + PRODUCTION_COST * productions; |
| } |
| |
| static search_state_list |
| reduction_step (search_state *ss, const item_number *conflict_item, |
| int parser_state, int rule_len) |
| { |
| (void) conflict_item; // FIXME: Unused |
| search_state_list result = |
| gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, 1); |
| |
| parse_state *ps = ss->states[parser_state]; |
| const state_item *si = parse_state_tail (ps); |
| bitset symbol_set = si->lookahead; |
| parse_state *other = ss->states[1 - parser_state]; |
| const state_item *other_si = parse_state_tail (other); |
| // if the other state can transition on a symbol, |
| // the reduction needs to have that symbol in its lookahead |
| if (item_number_is_symbol_number (*other_si->item)) |
| { |
| symbol_number other_sym = |
| item_number_as_symbol_number (*other_si->item); |
| if (!intersect_symbol (other_sym, symbol_set)) |
| return result; |
| symbol_set = bitset_create (nsyms, BITSET_FIXED); |
| bitset_set (symbol_set, other_sym); |
| } |
| |
| // FIXME: search_state *new_root = copy_search_state (ss); |
| parse_state_list reduced = |
| simulate_reduction (ps, rule_len, symbol_set); |
| parse_state *reduced_ps = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (reduced); |
| parse_state_list_next (&it, &reduced_ps); |
| ) |
| { |
| search_state *copy = copy_search_state (ss); |
| ss_set_parse_state (copy, parser_state, reduced_ps); |
| int r_cost = reduction_cost (reduced_ps); |
| copy->complexity += r_cost + PRODUCTION_COST + 2 * SHIFT_COST; |
| gl_list_add_last (result, copy); |
| } |
| gl_list_free (reduced); |
| if (symbol_set != si->lookahead) |
| bitset_free (symbol_set); |
| return result; |
| } |
| |
| /** |
| * Attempt to prepend the given symbol to this search state, respecting |
| * the given subsequent next symbol on each path. If a reverse transition |
| * cannot be made on both states, possible reverse productions are prepended |
| */ |
| static void |
| search_state_prepend (search_state *ss, symbol_number sym, bitset guide) |
| { |
| (void) sym; // FIXME: Unused. |
| const state_item *si1src = parse_state_head (ss->states[0]); |
| const state_item *si2src = parse_state_head (ss->states[1]); |
| |
| bool prod1 = SI_PRODUCTION (si1src); |
| // If one can make a reverse transition and the other can't, only apply |
| // the reverse productions that the other state can make in an attempt to |
| // make progress. |
| if (prod1 != SI_PRODUCTION (si2src)) |
| { |
| int prod_state = prod1 ? 0 : 1; |
| parse_state_list prev = parser_prepend (ss->states[prod_state]); |
| parse_state *ps = NULL; |
| for (gl_list_iterator_t iter = gl_list_iterator (prev); |
| parse_state_list_next (&iter, &ps); |
| ) |
| { |
| const state_item *psi = parse_state_head (ps); |
| bool guided = bitset_test (guide, psi->state->number); |
| if (!guided && !EXTENDED_SEARCH) |
| continue; |
| |
| search_state *copy = copy_search_state (ss); |
| ss_set_parse_state (copy, prod_state, ps); |
| copy->complexity += PRODUCTION_COST; |
| if (!guided) |
| copy->complexity += EXTENDED_COST; |
| ssb_append (copy); |
| } |
| gl_list_free (prev); |
| return; |
| } |
| // The parse state heads are either both production items or both |
| // transition items. So all prepend options will either be |
| // reverse transitions or reverse productions |
| int complexity_cost = prod1 ? PRODUCTION_COST : UNSHIFT_COST; |
| complexity_cost *= 2; |
| |
| parse_state_list prev1 = parser_prepend (ss->states[0]); |
| parse_state_list prev2 = parser_prepend (ss->states[1]); |
| |
| // loop through each pair of possible prepend states and append search |
| // states for each pair where the parser states correspond to the same |
| // parsed input. |
| parse_state *ps1 = NULL; |
| for (gl_list_iterator_t iter1 = gl_list_iterator (prev1); |
| parse_state_list_next (&iter1, &ps1); |
| ) |
| { |
| const state_item *psi1 = parse_state_head (ps1); |
| bool guided1 = bitset_test (guide, psi1->state->number); |
| if (!guided1 && !EXTENDED_SEARCH) |
| continue; |
| |
| parse_state *ps2 = NULL; |
| for (gl_list_iterator_t iter2 = gl_list_iterator (prev2); |
| parse_state_list_next (&iter2, &ps2); |
| ) |
| { |
| const state_item *psi2 = parse_state_head (ps2); |
| |
| bool guided2 = bitset_test (guide, psi2->state->number); |
| if (!guided2 && !EXTENDED_SEARCH) |
| continue; |
| // Only consider prepend state items that share the same state. |
| if (psi1->state != psi2->state) |
| continue; |
| |
| int complexity = ss->complexity; |
| if (prod1) |
| complexity += PRODUCTION_COST * 2; |
| else |
| complexity += UNSHIFT_COST * 2; |
| // penalty for not being along the guide path |
| if (!guided1 || !guided2) |
| complexity += EXTENDED_COST; |
| ssb_append (new_search_state (ps1, ps2, complexity)); |
| } |
| } |
| gl_list_free (prev1); |
| gl_list_free (prev2); |
| } |
| |
| /** |
| * Determine if the productions associated with the given parser items have |
| * the same prefix up to the dot. |
| */ |
| static bool |
| have_common_prefix (const item_number *itm1, const item_number *itm2) |
| { |
| int i = 0; |
| for (; !item_number_is_rule_number (itm1[i]); ++i) |
| if (itm1[i] != itm2[i]) |
| return false; |
| return item_number_is_rule_number (itm2[i]); |
| } |
| |
| /* |
| * The start and end locations of an item in ritem. |
| */ |
| static const item_number * |
| item_rule_start (const item_number *item) |
| { |
| const item_number *res = NULL; |
| for (res = item; |
| ritem < res && item_number_is_symbol_number (*(res - 1)); |
| --res) |
| continue; |
| return res; |
| } |
| |
| static const item_number * |
| item_rule_end (const item_number *item) |
| { |
| const item_number *res = NULL; |
| for (res = item; item_number_is_symbol_number (*res); ++res) |
| continue; |
| return res; |
| } |
| |
| /* |
| * Perform the appropriate possible parser actions |
| * on a search state and add the results to the |
| * search state priority queue. |
| */ |
| static inline void |
| generate_next_states (search_state *ss, state_item *conflict1, |
| state_item *conflict2) |
| { |
| // Compute the successor configurations. |
| parse_state *ps1 = ss->states[0]; |
| parse_state *ps2 = ss->states[1]; |
| const state_item *si1 = parse_state_tail (ps1); |
| const state_item *si2 = parse_state_tail (ps2); |
| bool si1reduce = item_number_is_rule_number (*si1->item); |
| bool si2reduce = item_number_is_rule_number (*si2->item); |
| if (!si1reduce && !si2reduce) |
| { |
| // Transition if both paths end at the same symbol |
| if (*si1->item == *si2->item) |
| { |
| int complexity = ss->complexity + 2 * SHIFT_COST; |
| parse_state_list trans1 = simulate_transition (ps1); |
| parse_state_list trans2 = simulate_transition (ps2); |
| parse_state *tps1 = NULL; |
| parse_state *tps2 = NULL; |
| for (gl_list_iterator_t it1 = gl_list_iterator (trans1); |
| parse_state_list_next (&it1, &tps1); |
| ) |
| for (gl_list_iterator_t it2 = gl_list_iterator (trans2); |
| parse_state_list_next (&it2, &tps2); |
| ) |
| ssb_append (new_search_state (tps1, tps2, complexity)); |
| gl_list_free (trans1); |
| gl_list_free (trans2); |
| } |
| |
| // Take production steps if possible. |
| production_step (ss, 0); |
| production_step (ss, 1); |
| } |
| // One of the states requires a reduction |
| else |
| { |
| const item_number *rhs1 = item_rule_start (si1->item); |
| const item_number *rhe1 = item_rule_end (si1->item); |
| int len1 = rhe1 - rhs1; |
| int size1 = parse_state_length (ps1); |
| bool ready1 = si1reduce && len1 < size1; |
| |
| const item_number *rhs2 = item_rule_start (si2->item); |
| const item_number *rhe2 = item_rule_end (si2->item); |
| int len2 = rhe2 - rhs2; |
| int size2 = parse_state_length (ps2); |
| bool ready2 = si2reduce && len2 < size2; |
| // If there is a path ready for reduction without being |
| // prepended further, reduce. |
| if (ready1 && ready2) |
| { |
| search_state_list reduced1 = reduction_step (ss, conflict1->item, 0, len1); |
| gl_list_add_last (reduced1, ss); |
| search_state *red1 = NULL; |
| for (gl_list_iterator_t iter = gl_list_iterator (reduced1); |
| search_state_list_next (&iter, &red1); |
| ) |
| { |
| search_state_list reduced2 = |
| reduction_step (red1, conflict2->item, 1, len2); |
| search_state *red2 = NULL; |
| for (gl_list_iterator_t iter2 = gl_list_iterator (reduced2); |
| search_state_list_next (&iter2, &red2); |
| ) |
| ssb_append (red2); |
| // Avoid duplicates. |
| if (red1 != ss) |
| ssb_append (red1); |
| gl_list_free (reduced2); |
| } |
| gl_list_free (reduced1); |
| } |
| else if (ready1) |
| { |
| search_state_list reduced1 = reduction_step (ss, conflict1->item, 0, len1); |
| search_state *red1 = NULL; |
| for (gl_list_iterator_t iter = gl_list_iterator (reduced1); |
| search_state_list_next (&iter, &red1); |
| ) |
| ssb_append (red1); |
| gl_list_free (reduced1); |
| } |
| else if (ready2) |
| { |
| search_state_list reduced2 = reduction_step (ss, conflict2->item, 1, len2); |
| search_state *red2 = NULL; |
| for (gl_list_iterator_t iter2 = gl_list_iterator (reduced2); |
| search_state_list_next (&iter2, &red2); |
| ) |
| ssb_append (red2); |
| gl_list_free (reduced2); |
| } |
| /* Both states end with a reduction, yet they don't have enough symbols |
| * to reduce. This means symbols are missing from the beginning of the |
| * rule, so we must prepend */ |
| else |
| { |
| const symbol_number sym |
| = si1reduce && !ready1 |
| ? *(rhe1 - size1) |
| : *(rhe2 - size2); |
| search_state_prepend (ss, sym, |
| parse_state_depth (ss->states[0]) >= 0 |
| ? rpp_set : scp_set); |
| } |
| } |
| } |
| |
| /* |
| * Perform the actual counterexample search, |
| * keeps track of what stage of the search algorithm |
| * we are at and gives the appropriate counterexample |
| * type based off of time constraints. |
| */ |
| static counterexample * |
| unifying_example (state_item_number itm1, |
| state_item_number itm2, |
| bool shift_reduce, |
| state_item_list reduce_path, symbol_number next_sym) |
| { |
| state_item *conflict1 = &state_items[itm1]; |
| state_item *conflict2 = &state_items[itm2]; |
| search_state *initial = initial_search_state (conflict1, conflict2); |
| ssb_queue = gl_list_create_empty (GL_RBTREEHASH_LIST, |
| (gl_listelement_equals_fn) ssb_equals, |
| (gl_listelement_hashcode_fn) ssb_hasher, |
| (gl_listelement_dispose_fn) ssb_free, |
| false); |
| visited = |
| hash_initialize (32, NULL, (Hash_hasher) visited_hasher, |
| (Hash_comparator) visited_comparator, |
| (Hash_data_freer) search_state_free); |
| ssb_append (initial); |
| time_t start = time (NULL); |
| bool assurance_printed = false; |
| search_state *stage3result = NULL; |
| counterexample *cex = NULL; |
| while (gl_list_size (ssb_queue) > 0) |
| { |
| const search_state_bundle *ssb = gl_list_get_at (ssb_queue, 0); |
| |
| search_state *ss = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (ssb->states); |
| search_state_list_next (&it, &ss); |
| ) |
| { |
| if (trace_flag & trace_cex) |
| search_state_print (ss); |
| // Stage 1/2 completing the rules containing the conflicts |
| parse_state *ps1 = ss->states[0]; |
| parse_state *ps2 = ss->states[1]; |
| if (parse_state_depth (ps1) < 0 && parse_state_depth (ps2) < 0) |
| { |
| // Stage 3: reduce and shift conflict items completed. |
| const state_item *si1src = parse_state_head (ps1); |
| const state_item *si2src = parse_state_head (ps2); |
| if (item_rule (si1src->item)->lhs == item_rule (si2src->item)->lhs |
| && have_common_prefix (si1src->item, si2src->item)) |
| { |
| // Stage 4: both paths share a prefix |
| derivation *d1 = parse_state_derivation (ps1); |
| derivation *d2 = parse_state_derivation (ps2); |
| if (parse_state_derivation_completed (ps1) |
| && parse_state_derivation_completed (ps2)) |
| { |
| // Once we have two derivations for the same symbol, |
| // we've found a unifying counterexample. |
| cex = new_counterexample (d1, d2, shift_reduce, true, false); |
| derivation_retain (d1); |
| derivation_retain (d2); |
| goto cex_search_end; |
| } |
| if (!stage3result) |
| stage3result = copy_search_state (ss); |
| } |
| } |
| if (TIME_LIMIT_ENFORCED) |
| { |
| double time_passed = difftime (time (NULL), start); |
| if (!assurance_printed && time_passed > ASSURANCE_LIMIT |
| && stage3result) |
| { |
| fputs ("Productions leading up to the conflict state found. " |
| "Still finding a possible unifying counterexample...", |
| stderr); |
| assurance_printed = true; |
| } |
| if (time_passed > time_limit) |
| { |
| fprintf (stderr, "time limit exceeded: %f\n", time_passed); |
| goto cex_search_end; |
| } |
| } |
| generate_next_states (ss, conflict1, conflict2); |
| } |
| gl_sortedlist_remove (ssb_queue, |
| (gl_listelement_compar_fn) ssb_comp, ssb); |
| } |
| cex_search_end:; |
| if (!cex) |
| { |
| // No unifying counterexamples |
| // If a search state from Stage 3 is available, use it |
| // to construct a more compact nonunifying counterexample. |
| if (stage3result) |
| cex = complete_diverging_examples (stage3result, next_sym, shift_reduce); |
| // Otherwise, construct a nonunifying counterexample that |
| // begins from the start state using the shortest |
| // lookahead-sensitive path to the reduce item. |
| else |
| cex = example_from_path (shift_reduce, itm2, reduce_path, next_sym); |
| } |
| gl_list_free (ssb_queue); |
| hash_free (visited); |
| if (stage3result) |
| search_state_free (stage3result); |
| return cex; |
| } |
| |
| static time_t cumulative_time; |
| |
| void |
| counterexample_init (void) |
| { |
| /* Recognize $TIME_LIMIT. Not a public feature, just to help |
| debugging. If we need something public, a %define/-D/-F variable |
| would be more appropriate. */ |
| { |
| const char *cp = getenv ("TIME_LIMIT"); |
| if (cp) |
| { |
| char *end = NULL; |
| double v = strtod (cp, &end); |
| if (*end == '\0' && errno == 0) |
| time_limit = v; |
| } |
| } |
| time (&cumulative_time); |
| scp_set = bitset_create (nstates, BITSET_FIXED); |
| rpp_set = bitset_create (nstates, BITSET_FIXED); |
| state_items_init (); |
| } |
| |
| |
| void |
| counterexample_free (void) |
| { |
| if (scp_set) |
| { |
| bitset_free (scp_set); |
| bitset_free (rpp_set); |
| state_items_free (); |
| } |
| } |
| |
| /** |
| * Report a counterexample for conflict on symbol next_sym |
| * between the given state-items |
| */ |
| static void |
| counterexample_report (state_item_number itm1, state_item_number itm2, |
| symbol_number next_sym, bool shift_reduce, |
| FILE *out, const char *prefix) |
| { |
| // Compute the shortest lookahead-sensitive path and associated sets of |
| // parser states. |
| state_item_list shortest_path = shortest_path_from_start (itm1, next_sym); |
| bool reduce_prod_reached = false; |
| const rule *reduce_rule = item_rule (state_items[itm1].item); |
| |
| bitset_zero (scp_set); |
| bitset_zero (rpp_set); |
| |
| state_item *si = NULL; |
| for (gl_list_iterator_t it = gl_list_iterator (shortest_path); |
| state_item_list_next (&it, &si); |
| ) |
| { |
| bitset_set (scp_set, si->state->number); |
| reduce_prod_reached = reduce_prod_reached |
| || item_rule (si->item) == reduce_rule; |
| if (reduce_prod_reached) |
| bitset_set (rpp_set, si->state->number); |
| } |
| time_t t = time (NULL); |
| counterexample *cex |
| = difftime (t, cumulative_time) < CUMULATIVE_TIME_LIMIT |
| ? unifying_example (itm1, itm2, shift_reduce, shortest_path, next_sym) |
| : example_from_path (shift_reduce, itm2, shortest_path, next_sym); |
| |
| gl_list_free (shortest_path); |
| counterexample_print (cex, out, prefix); |
| free_counterexample (cex); |
| } |
| |
| |
| // ITM1 denotes a shift, ITM2 a reduce. |
| static void |
| counterexample_report_shift_reduce (state_item_number itm1, state_item_number itm2, |
| symbol_number next_sym, |
| FILE *out, const char *prefix) |
| { |
| if (out == stderr) |
| complain (NULL, Wcounterexamples, |
| _("shift/reduce conflict on token %s"), symbols[next_sym]->tag); |
| else |
| { |
| fputs (prefix, out); |
| fprintf (out, _("shift/reduce conflict on token %s"), symbols[next_sym]->tag); |
| fprintf (out, "%s\n", _(":")); |
| } |
| // In the report, print the items. |
| if (out != stderr || trace_flag & trace_cex) |
| { |
| state_item_print (&state_items[itm1], out, prefix); |
| state_item_print (&state_items[itm2], out, prefix); |
| } |
| counterexample_report (itm1, itm2, next_sym, true, out, prefix); |
| } |
| |
| static void |
| counterexample_report_reduce_reduce (state_item_number itm1, state_item_number itm2, |
| bitset conflict_syms, |
| FILE *out, const char *prefix) |
| { |
| { |
| struct obstack obstack; |
| obstack_init (&obstack); |
| bitset_iterator biter; |
| state_item_number sym; |
| const char *sep = ""; |
| BITSET_FOR_EACH (biter, conflict_syms, sym, 0) |
| { |
| obstack_printf (&obstack, "%s%s", sep, symbols[sym]->tag); |
| sep = ", "; |
| } |
| char *tokens = obstack_finish0 (&obstack); |
| if (out == stderr) |
| complain (NULL, Wcounterexamples, |
| ngettext ("reduce/reduce conflict on token %s", |
| "reduce/reduce conflict on tokens %s", |
| bitset_count (conflict_syms)), |
| tokens); |
| else |
| { |
| fputs (prefix, out); |
| fprintf (out, |
| ngettext ("reduce/reduce conflict on token %s", |
| "reduce/reduce conflict on tokens %s", |
| bitset_count (conflict_syms)), |
| tokens); |
| fprintf (out, "%s\n", _(":")); |
| } |
| obstack_free (&obstack, NULL); |
| } |
| // In the report, print the items. |
| if (out != stderr || trace_flag & trace_cex) |
| { |
| state_item_print (&state_items[itm1], out, prefix); |
| state_item_print (&state_items[itm2], out, prefix); |
| } |
| counterexample_report (itm1, itm2, bitset_first (conflict_syms), |
| false, out, prefix); |
| } |
| |
| static state_item_number |
| find_state_item_number (const rule *r, state_number sn) |
| { |
| for (state_item_number i = state_item_map[sn]; i < state_item_map[sn + 1]; ++i) |
| if (!SI_DISABLED (i) |
| && item_number_as_rule_number (*state_items[i].item) == r->number) |
| return i; |
| abort (); |
| } |
| |
| void |
| counterexample_report_state (const state *s, FILE *out, const char *prefix) |
| { |
| const state_number sn = s->number; |
| const reductions *reds = s->reductions; |
| bitset lookaheads = bitset_create (ntokens, BITSET_FIXED); |
| for (int i = 0; i < reds->num; ++i) |
| { |
| const rule *r1 = reds->rules[i]; |
| const state_item_number c1 = find_state_item_number (r1, sn); |
| for (state_item_number c2 = state_item_map[sn]; c2 < state_item_map[sn + 1]; ++c2) |
| if (!SI_DISABLED (c2)) |
| { |
| item_number conf = *state_items[c2].item; |
| if (item_number_is_symbol_number (conf) |
| && bitset_test (reds->lookaheads[i], conf)) |
| counterexample_report_shift_reduce (c1, c2, conf, out, prefix); |
| } |
| for (int j = i+1; j < reds->num; ++j) |
| { |
| const rule *r2 = reds->rules[j]; |
| // Conflicts: common lookaheads. |
| bitset_intersection (lookaheads, |
| reds->lookaheads[i], |
| reds->lookaheads[j]); |
| if (!bitset_empty_p (lookaheads)) |
| for (state_item_number c2 = state_item_map[sn]; c2 < state_item_map[sn + 1]; ++c2) |
| if (!SI_DISABLED (c2) |
| && item_rule (state_items[c2].item) == r2) |
| { |
| counterexample_report_reduce_reduce (c1, c2, lookaheads, out, prefix); |
| break; |
| } |
| } |
| } |
| bitset_free (lookaheads); |
| } |
