[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 3/9] cex: use better type names
|
From: |
Akim Demaille |
|
Subject: |
[PATCH 3/9] cex: use better type names |
|
Date: |
Sun, 12 Jul 2020 19:23:12 +0200 |
There are too many gl_list_t in there, it's hard to understand what is
going on. Introduce and use more precise types. I sure can be wrong
in some places, it's hard to tell without proper tool support.
* src/counterexample.c, src/lssi.c, src/lssi.h, src/parse-simulation.c,
* src/parse-simulation.h, src/state-item.c, src/state-item.h
(si_bfs_node_list, search_state_list, ssb_list, lssi_list)
(state_item_list): New.
---
src/counterexample.c | 61 ++++++++++++++++++++++++------------------
src/lssi.c | 16 ++++++-----
src/lssi.h | 6 ++---
src/parse-simulation.c | 48 ++++++++++++++++-----------------
src/parse-simulation.h | 2 +-
src/state-item.c | 6 ++---
src/state-item.h | 4 +++
7 files changed, 78 insertions(+), 65 deletions(-)
diff --git a/src/counterexample.c b/src/counterexample.c
index ca0f4a0d..bfab304c 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -175,6 +175,8 @@ si_bfs_free (si_bfs_node *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
@@ -188,9 +190,10 @@ expand_to_conflict (state_item_number start, symbol_number
conflict_sym)
{
si_bfs_node *init = si_bfs_new (start, NULL);
- gl_list_t queue = gl_list_create (GL_LINKED_LIST, NULL, NULL,
- (gl_listelement_dispose_fn) si_bfs_free,
- true, 1, (const void **) &init);
+ 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)
@@ -274,7 +277,7 @@ expand_to_conflict (state_item_number start, symbol_number
conflict_sym)
*/
static derivation *
complete_diverging_example (symbol_number conflict_sym,
- gl_list_t path, derivation_list derivs)
+ 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.
@@ -395,15 +398,15 @@ complete_diverging_example (symbol_number conflict_sym,
/* 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 gl_list_t
-nonunifying_shift_path (gl_list_t reduce_path, state_item *shift_conflict)
+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;
- gl_list_t result =
+ 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,
@@ -425,10 +428,10 @@ nonunifying_shift_path (gl_list_t reduce_path, state_item
*shift_conflict)
// bfs to find a shift to the right state
si_bfs_node *init = si_bfs_new (si - state_items, NULL);
- gl_list_t queue =
- gl_list_create (GL_LINKED_LIST, NULL, NULL,
- (gl_listelement_dispose_fn) si_bfs_free,
- true, 1, (const void **) &init);
+ 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)
@@ -493,11 +496,11 @@ nonunifying_shift_path (gl_list_t reduce_path, state_item
*shift_conflict)
static counterexample *
example_from_path (bool shift_reduce,
state_item_number itm2,
- gl_list_t shortest_path, symbol_number next_sym)
+ state_item_list shortest_path, symbol_number next_sym)
{
derivation *deriv1 =
complete_diverging_example (next_sym, shortest_path, NULL);
- gl_list_t path_2
+ state_item_list path_2
= shift_reduce
? nonunifying_shift_path (shortest_path, &state_items [itm2])
: shortest_path_from_start (itm2, next_sym);
@@ -583,6 +586,8 @@ search_state_print (search_state *ss)
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)
{
@@ -619,7 +624,7 @@ complete_diverging_examples (search_state *ss,
derivation *new_derivs[2];
for (int i = 0; i < 2; ++i)
{
- gl_list_t sitems;
+ 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);
@@ -635,7 +640,7 @@ complete_diverging_examples (search_state *ss,
*/
typedef struct
{
- gl_list_t states;
+ search_state_list states;
int complexity;
} search_state_bundle;
@@ -664,6 +669,8 @@ 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)
{
@@ -679,7 +686,7 @@ visited_comparator (const search_state *ss1, const
search_state *ss2)
}
/* Priority queue for search states with minimal complexity. */
-static gl_list_t ssb_queue;
+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;
@@ -756,12 +763,12 @@ reduction_cost (const parse_state *ps)
return SHIFT_COST * shifts + PRODUCTION_COST * productions;
}
-static gl_list_t
+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
- gl_list_t result =
+ search_state_list result =
gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, 1);
parse_state *ps = ss->states[parser_state];
@@ -988,14 +995,14 @@ generate_next_states (search_state *ss, state_item
*conflict1,
// prepended further, reduce.
if (ready1 && ready2)
{
- gl_list_t reduced1 = reduction_step (ss, conflict1->item, 0, len1);
+ 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);
)
{
- gl_list_t reduced2 =
+ 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);
@@ -1011,7 +1018,7 @@ generate_next_states (search_state *ss, state_item
*conflict1,
}
else if (ready1)
{
- gl_list_t reduced1 = reduction_step (ss, conflict1->item, 0, len1);
+ 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);
@@ -1021,7 +1028,7 @@ generate_next_states (search_state *ss, state_item
*conflict1,
}
else if (ready2)
{
- gl_list_t reduced2 = reduction_step (ss, conflict2->item, 1, len2);
+ 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);
@@ -1055,7 +1062,7 @@ static counterexample *
unifying_example (state_item_number itm1,
state_item_number itm2,
bool shift_reduce,
- gl_list_t reduce_path, symbol_number next_sym)
+ state_item_list reduce_path, symbol_number next_sym)
{
state_item *conflict1 = &state_items[itm1];
state_item *conflict2 = &state_items[itm2];
@@ -1190,7 +1197,7 @@ counterexample_report (state_item_number itm1,
state_item_number itm2,
{
// Compute the shortest lookahead-sensitive path and associated sets of
// parser states.
- gl_list_t shortest_path = shortest_path_from_start (itm1, next_sym);
+ 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);
@@ -1226,7 +1233,8 @@ counterexample_report_shift_reduce (state_item_number
itm1, state_item_number it
{
fputs (prefix, out);
fprintf (out, _("Shift/reduce conflict on token %s:\n"),
symbols[next_sym]->tag);
- if (*prefix)
+ // In the report, print the items.
+ if (*prefix || trace_flag & trace_cex)
{
print_state_item (&state_items[itm1], out, prefix);
print_state_item (&state_items[itm2], out, prefix);
@@ -1254,7 +1262,8 @@ counterexample_report_reduce_reduce (state_item_number
itm1, state_item_number i
}
fputs (_(":\n"), out);
}
- if (*prefix)
+ // In the report, print the items.
+ if (*prefix || trace_flag & trace_cex)
{
print_state_item (&state_items[itm1], out, prefix);
print_state_item (&state_items[itm2], out, prefix);
diff --git a/src/lssi.c b/src/lssi.c
index 86516d58..8448482c 100644
--- a/src/lssi.c
+++ b/src/lssi.c
@@ -82,8 +82,10 @@ lssi_comparator (lssi *s1, lssi *s2)
return false;
}
+typedef gl_list_t lssi_list;
+
static inline bool
-append_lssi (lssi *sn, Hash_table *visited, gl_list_t queue)
+append_lssi (lssi *sn, Hash_table *visited, lssi_list queue)
{
if (hash_lookup (visited, sn))
{
@@ -121,7 +123,7 @@ static bitset
eligible_state_items (state_item *target)
{
bitset result = bitset_create (nstate_items, BITSET_FIXED);
- gl_list_t queue =
+ state_item_list queue =
gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
(const void **) &target);
while (gl_list_size (queue) > 0)
@@ -147,7 +149,7 @@ eligible_state_items (state_item *target)
* this conflict. If optimized is true, only consider parser states
* that can reach the conflict state.
*/
-gl_list_t
+state_item_list
shortest_path_from_start (state_item_number target, symbol_number next_sym)
{
bitset eligible = eligible_state_items (&state_items[target]);
@@ -159,7 +161,7 @@ shortest_path_from_start (state_item_number target,
symbol_number next_sym)
bitset il = bitset_create (nsyms, BITSET_FIXED);
bitset_set (il, 0);
lssi *init = new_lssi (0, NULL, il, true);
- gl_list_t queue = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL,
+ lssi_list queue = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL,
NULL, true);
append_lssi (init, visited, queue);
// breadth-first search
@@ -240,7 +242,7 @@ shortest_path_from_start (state_item_number target,
symbol_number next_sym)
fputs ("Cannot find shortest path to conflict state.", stderr);
abort ();
}
- gl_list_t res =
+ state_item_list res =
gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
for (lssi *sn = n; sn != NULL; sn = sn->parent)
gl_list_add_first (res, &state_items[sn->si]);
@@ -306,10 +308,10 @@ intersect (bitset ts, bitset syms)
* Compute a list of state_items that have a production to n with respect
* to its lookahead
*/
-gl_list_t
+state_item_list
lssi_reverse_production (const state_item *si, bitset lookahead)
{
- gl_list_t result =
+ state_item_list result =
gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
if (SI_TRANSITION (si))
return result;
diff --git a/src/lssi.h b/src/lssi.h
index dcdb8ef8..6aaf2bc4 100644
--- a/src/lssi.h
+++ b/src/lssi.h
@@ -32,8 +32,8 @@
* find shortest lookahead-sensitive path of state-items to target such that
* next_sym is in the follow_L set of target in that position.
*/
-gl_list_t shortest_path_from_start (state_item_number target,
- symbol_number next_sym);
+state_item_list shortest_path_from_start (state_item_number target,
+ symbol_number next_sym);
/**
* Determine if the given terminal is in the given symbol set or can begin
@@ -52,6 +52,6 @@ bool intersect (bitset ts, bitset syms);
* to this state-item such that the resulting possible lookahead symbols are
* as given.
*/
-gl_list_t lssi_reverse_production (const state_item *si, bitset lookahead);
+state_item_list lssi_reverse_production (const state_item *si, bitset
lookahead);
#endif /* LSSI_H */
diff --git a/src/parse-simulation.c b/src/parse-simulation.c
index ce6ece9a..940a99fe 100644
--- a/src/parse-simulation.c
+++ b/src/parse-simulation.c
@@ -34,7 +34,7 @@ typedef struct parse_state
struct si_chunk
{
// elements newly added in this chunk
- gl_list_t contents;
+ state_item_list contents;
// properties of the linked list this chunk represents
const state_item *head_elt;
const state_item *tail_elt;
@@ -252,7 +252,7 @@ parse_state_completed_steps (const parse_state *ps, int
*shifts, int *production
while (root_ps->parent)
root_ps = root_ps->parent;
- gl_list_t sis = root_ps->state_items.contents;
+ state_item_list sis = root_ps->state_items.contents;
int count = 0;
state_item *last = NULL;
@@ -337,19 +337,17 @@ parser_pop (parse_state *ps, int deriv_index,
for (int i = 0; i < 4; ++i)
chunks[i] = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
for (parse_state *pn = ps; pn != NULL; pn = pn->parent)
- {
- if (pn->prepend)
- {
- gl_list_add_last (chunks[0], pn->state_items.contents);
- gl_list_add_last (chunks[2], pn->derivs.contents);
- }
- else
- {
- gl_list_add_first (chunks[1], pn->state_items.contents);
- gl_list_add_first (chunks[3], pn->derivs.contents);
- }
- }
- gl_list_t popped_derivs = derivation_list_new ();
+ if (pn->prepend)
+ {
+ gl_list_add_last (chunks[0], pn->state_items.contents);
+ gl_list_add_last (chunks[2], pn->derivs.contents);
+ }
+ else
+ {
+ gl_list_add_first (chunks[1], pn->state_items.contents);
+ gl_list_add_first (chunks[3], pn->derivs.contents);
+ }
+ derivation_list popped_derivs = derivation_list_new ();
gl_list_t ret_chunks[4] = { ret->state_items.contents, NULL,
ret->derivs.contents, popped_derivs
};
@@ -390,7 +388,7 @@ parser_pop (parse_state *ps, int deriv_index,
}
void
-parse_state_lists (parse_state *ps, gl_list_t *sitems,
+parse_state_lists (parse_state *ps, state_item_list *sitems,
derivation_list *derivs)
{
parse_state *temp = empty_parse_state ();
@@ -431,14 +429,14 @@ nullable_closure (parse_state *ps, state_item *si,
parse_state_list state_list)
}
}
-gl_list_t
+parse_state_list
simulate_transition (parse_state *ps)
{
const state_item *si = ps->state_items.tail_elt;
symbol_number sym = item_number_as_symbol_number (*si->item);
// Transition on the same next symbol, taking nullable
// symbols into account.
- gl_list_t result = parse_state_list_new ();
+ parse_state_list result = parse_state_list_new ();
state_item_number si_next = si->trans;
// check for disabled transition, shouldn't happen
// as any state_items that lead to these should be
@@ -473,10 +471,10 @@ compatible (symbol_number sym1, symbol_number sym2)
return false;
}
-gl_list_t
+parse_state_list
simulate_production (parse_state *ps, symbol_number compat_sym)
{
- gl_list_t result = parse_state_list_new ();
+ parse_state_list result = parse_state_list_new ();
const state_item *si = parse_state_tail (ps);
if (si->prods)
{
@@ -504,10 +502,10 @@ simulate_production (parse_state *ps, symbol_number
compat_sym)
// simulates a reduction on the given parse state, conflict_item is the
// item associated with ps's conflict. symbol_set is a lookahead set this
// reduction must be compatible with
-gl_list_t
+parse_state_list
simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set)
{
- gl_list_t result = parse_state_list_new ();
+ parse_state_list result = parse_state_list_new ();
int s_size = ps->state_items.total_size;
int d_size = ps->derivs.total_size;
@@ -537,7 +535,7 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
// The head state_item is a production item, so we need to prepend
// with possible source state-items.
const state_item *head = ps->state_items.head_elt;
- gl_list_t prev = lssi_reverse_production (head, symbol_set);
+ state_item_list prev = lssi_reverse_production (head, symbol_set);
// TODO: better understand what causes this case.
if (gl_list_size (prev) == 0)
{
@@ -570,10 +568,10 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
return result;
}
-gl_list_t
+parse_state_list
parser_prepend (parse_state *ps)
{
- gl_list_t res = parse_state_list_new ();
+ parse_state_list res = parse_state_list_new ();
const state_item *head = ps->state_items.head_elt;
symbol_number prepend_sym =
item_number_as_symbol_number (*(head->item - 1));
diff --git a/src/parse-simulation.h b/src/parse-simulation.h
index 6b0549ad..92eea21c 100644
--- a/src/parse-simulation.h
+++ b/src/parse-simulation.h
@@ -113,7 +113,7 @@ int parse_state_length (const parse_state *ps);
int parse_state_depth (const parse_state *ps);
/* returns the linked lists that the parse state is supposed to represent */
-void parse_state_lists (parse_state *ps, gl_list_t *state_items,
+void parse_state_lists (parse_state *ps, state_item_list *state_items,
derivation_list *derivs);
/* various functions that return a list of states based off of
diff --git a/src/state-item.c b/src/state-item.c
index 5542d26b..a3194e16 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -304,7 +304,7 @@ gen_lookaheads (void)
continue;
bitset lookahead = si->lookahead;
- gl_list_t queue =
+ state_item_list queue =
gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
(const void **) &si);
@@ -390,7 +390,7 @@ disable_state_item (state_item *si)
static void
prune_forward (const state_item *si)
{
- gl_list_t queue =
+ state_item_list queue =
gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
(const void **) &si);
@@ -425,7 +425,7 @@ prune_forward (const state_item *si)
static void
prune_backward (const state_item *si)
{
- gl_list_t queue =
+ state_item_list queue =
gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
(const void **) &si);
diff --git a/src/state-item.h b/src/state-item.h
index d8b46843..dc2b36c8 100644
--- a/src/state-item.h
+++ b/src/state-item.h
@@ -69,6 +69,9 @@ typedef struct
bitset lookahead;
} state_item;
+// A path of state-items.
+typedef gl_list_t state_item_list;
+
extern bitsetv firsts;
# define FIRSTS(sym) firsts[(sym) - ntokens]
@@ -92,6 +95,7 @@ void state_items_free (void);
bool production_allowed (const state_item *si, const state_item *next);
+// Iterating on a state_item_list.
static inline bool
state_item_list_next (gl_list_iterator_t *it, state_item **si)
{
--
2.27.0
- [PATCH 0/9] cex: shift derivation vs reduce derivation, Akim Demaille, 2020/07/12
- [PATCH 1/9] tests: beware of version numbers from git describe, Akim Demaille, 2020/07/12
- [PATCH 2/9] cex: minor style changes, Akim Demaille, 2020/07/12
- [PATCH 3/9] cex: use better type names,
Akim Demaille <=
- [PATCH 4/9] cex: minor renaming, Akim Demaille, 2020/07/12
- [PATCH 5/9] cex: more consistent memory allocation/copy, Akim Demaille, 2020/07/12
- [PATCH 6/9] cex: use state_item_number consistently, Akim Demaille, 2020/07/12
- [PATCH 7/9] cex: factor memory allocation, Akim Demaille, 2020/07/12
- [PATCH 8/9] style: s/lookahead_tokens/lookaheads/g, Akim Demaille, 2020/07/12
- [PATCH 9/9] cex: display shifts before reductions, Akim Demaille, 2020/07/12