[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 2/4] lists: fix various issues with the use of gnulib's list
|
From: |
Akim Demaille |
|
Subject: |
[PATCH 2/4] lists: fix various issues with the use of gnulib's list |
|
Date: |
Mon, 1 Jun 2020 07:51:18 +0200 |
First, we should avoid code such as
gl_list_iterator_t it = gl_list_iterator (deriv->children);
derivation *child = NULL;
while (gl_list_iterator_next (&it, (const void **) &child, NULL))
{
derivation_print (child, f);
because of -Wstrict-aliasing (whose job is to catch type-punning
issues). See https://lists.gnu.org/r/bug-bison/2020-05/msg00039.html.
Rather we need
gl_list_iterator_t it = gl_list_iterator (deriv->children);
const void **p = NULL;
while (gl_list_iterator_next (&it, &p, NULL))
{
derivation *child = (derivation *) p;
derivation_print (child, f);
Second, list iterators actually have destructors. Even though there
are noop in the case of linked-list, we should use them.
Let's address both issues we typed wrappers such as
derivation_list_next that take care of both issues, and besides allow
to better scope the iterators:
derivation *child;
for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
derivation_list_next (&it, &child);
)
{
derivation_print (child, f);
* src/derivation.h, src/derivation.c (derivation_list_next): New.
Use it where appropriate.
* src/counterexample.c (search_state_list_next): New.
Use it where appropriate.
* src/parse-simulation.h, src/parse-simulation.c
* src/state-item.h (state_item_list_next): New.
Use it where appropriate.
---
src/counterexample.c | 148 ++++++++++++++++++++++++-----------------
src/derivation.c | 34 ++++++----
src/derivation.h | 12 ++++
src/parse-simulation.c | 47 +++++++------
src/parse-simulation.h | 12 ++++
src/state-item.h | 13 ++++
6 files changed, 170 insertions(+), 96 deletions(-)
diff --git a/src/counterexample.c b/src/counterexample.c
index 90ab72f7..0f08f652 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -334,9 +334,9 @@ complete_diverging_example (symbol_number conflict_sym,
lookahead_required = false;
derivation_list next_derivs =
expand_to_conflict (nsi, conflict_sym);
- gl_list_iterator_t it = gl_list_iterator (next_derivs);
derivation *d = NULL;
- while (gl_list_iterator_next (&it, (const void **) &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);
@@ -469,9 +469,10 @@ nonunifying_shift_path (gl_list_t reduce_path, state_item
*shift_conflict)
if (trace_flag & trace_cex)
{
fputs ("SHIFT ITEM PATH:\n", stderr);
- gl_list_iterator_t it = gl_list_iterator (result);
state_item *sip = NULL;
- while (gl_list_iterator_next (&it, (const void **) &sip, NULL))
+ for (gl_list_iterator_t it = gl_list_iterator (result);
+ state_item_list_next (&it, &sip);
+ )
print_state_item (sip, stderr);
}
return result;
@@ -574,6 +575,18 @@ search_state_print (search_state *ss)
putc ('\n', stderr);
}
+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
@@ -712,9 +725,10 @@ production_step (search_state *ss, int parser_state)
simulate_production (ss->states[parser_state], other_sym);
int complexity = ss->complexity + PRODUCTION_COST;
- gl_list_iterator_t it = gl_list_iterator (prods);
parse_state *ps = NULL;
- while (gl_list_iterator_next (&it, (const void **) &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);
@@ -761,9 +775,10 @@ reduction_step (search_state *ss, const item_number
*conflict_item,
// FIXME: search_state *new_root = copy_search_state (ss);
parse_state_list reduced =
simulate_reduction (ps, rule_len, symbol_set);
- gl_list_iterator_t it = gl_list_iterator (reduced);
- parse_state *reduced_ps;
- while (gl_list_iterator_next (&it, (const void **) &reduced_ps, NULL))
+ 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);
@@ -797,9 +812,10 @@ search_state_prepend (search_state *ss, symbol_number sym,
bitset guide)
{
int prod_state = prod1 ? 0 : 1;
parse_state_list prev = parser_prepend (ss->states[prod_state]);
- gl_list_iterator_t iter = gl_list_iterator (prev);
parse_state *ps = NULL;
- while (gl_list_iterator_next (&iter, (const void **)&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);
@@ -828,18 +844,20 @@ search_state_prepend (search_state *ss, symbol_number
sym, bitset guide)
// 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.
- gl_list_iterator_t iter1 = gl_list_iterator (prev1);
- parse_state *ps1;
- while (gl_list_iterator_next (&iter1, (const void **)&ps1, NULL))
+ 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;
- gl_list_iterator_t iter2 = gl_list_iterator (prev2);
- parse_state *ps2;
- while (gl_list_iterator_next (&iter2, (const void **)&ps2, NULL))
+ 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);
@@ -926,16 +944,15 @@ generate_next_states (search_state *ss, state_item
*conflict1,
int complexity = ss->complexity + 2 * SHIFT_COST;
parse_state_list trans1 = simulate_transition (ps1);
parse_state_list trans2 = simulate_transition (ps2);
- gl_list_iterator_t it1 = gl_list_iterator (trans1);
- parse_state *tps1;
- while (gl_list_iterator_next (&it1, (const void **) &tps1, NULL))
- {
- gl_list_iterator_t it2 = gl_list_iterator (trans2);
- parse_state *tps2;
- while (gl_list_iterator_next
- (&it2, (const void **) &tps2, NULL))
- ssb_append (new_search_state (tps1, tps2, complexity));
- }
+ 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);
}
@@ -958,43 +975,48 @@ generate_next_states (search_state *ss, state_item
*conflict1,
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)
+ // If there is a path ready for reduction without being
+ // prepended further, reduce.
+ if (ready1 && ready2)
{
gl_list_t reduced1 = reduction_step (ss, conflict1->item, 0, len1);
- gl_list_iterator_t iter = gl_list_iterator (reduced1);
+ gl_list_add_last (reduced1, ss);
search_state *red1 = NULL;
- if (ready2)
+ for (gl_list_iterator_t iter = gl_list_iterator (reduced1);
+ search_state_list_next (&iter, &red1);
+ )
{
- gl_list_add_last (reduced1, ss);
- while (gl_list_iterator_next
- (&iter, (const void **) &red1, NULL))
- {
- gl_list_t reduced2 =
- reduction_step (red1, conflict2->item, 1, len2);
- gl_list_iterator_t iter2 = gl_list_iterator (reduced2);
- search_state *red2;
- while (gl_list_iterator_next
- (&iter2, (const void **) &red2, NULL))
- ssb_append (red2);
- // avoid duplicates
- if (red1 != ss)
- ssb_append (red1);
- gl_list_free (reduced2);
- }
+ gl_list_t 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);
}
- else
- while (gl_list_iterator_next (&iter, (const void **) &red1, NULL))
- ssb_append (red1);
+ gl_list_free (reduced1);
+ }
+ else if (ready1)
+ {
+ gl_list_t 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)
{
gl_list_t reduced2 = reduction_step (ss, conflict2->item, 1, len2);
- gl_list_iterator_t iter2 = gl_list_iterator (reduced2);
- search_state *red2;
- while (gl_list_iterator_next (&iter2, (const void **) &red2, NULL))
+ 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);
}
@@ -1046,9 +1068,11 @@ unifying_example (state_item_number itm1,
while (gl_list_size (ssb_queue) > 0)
{
const search_state_bundle *ssb = gl_list_get_at (ssb_queue, 0);
- gl_list_iterator_t it = gl_list_iterator (ssb->states);
+
search_state *ss = NULL;
- while (gl_list_iterator_next (&it, (const void **) &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);
@@ -1157,19 +1181,21 @@ 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);
- bool reduceProdReached = false;
+ bool reduce_prod_reached = false;
const rule *reduce_rule = item_rule (state_items[itm1].item);
bitset_zero (scp_set);
bitset_zero (rpp_set);
- gl_list_iterator_t it = gl_list_iterator (shortest_path);
+
state_item *si = NULL;
- while (gl_list_iterator_next (&it, (const void **) &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);
- reduceProdReached = reduceProdReached
+ reduce_prod_reached = reduce_prod_reached
|| item_rule (si->item) == reduce_rule;
- if (reduceProdReached)
+ if (reduce_prod_reached)
bitset_set (rpp_set, si->state->number);
}
time_t t = time (NULL);
diff --git a/src/derivation.c b/src/derivation.c
index 8f16e17a..2f6a81e5 100644
--- a/src/derivation.c
+++ b/src/derivation.c
@@ -55,9 +55,10 @@ derivation_list_prepend (derivation_list dl, derivation *d)
void derivation_list_free (derivation_list dl)
{
- gl_list_iterator_t it = gl_list_iterator (dl);
- derivation *d;
- while (gl_list_iterator_next (&it, (const void **) &d, NULL))
+ derivation *d = NULL;
+ for (gl_list_iterator_t it = gl_list_iterator (dl);
+ derivation_list_next (&it, &d);
+ )
if (d != &d_dot)
derivation_free (d);
gl_list_free (dl);
@@ -94,9 +95,10 @@ derivation_free (derivation *d)
{
if (deriv->children)
{
- gl_list_iterator_t it = gl_list_iterator (deriv->children);
- derivation *child;
- while (gl_list_iterator_next (&it, (const void **) &child, NULL))
+ derivation *child = NULL;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
if (child != &d_dot)
gl_list_add_last (free_queue, child);
gl_list_free (deriv->children);
@@ -114,9 +116,10 @@ derivation_size (const derivation *deriv)
if (!deriv->children)
return 1;
int size = 1;
- gl_list_iterator_t it = gl_list_iterator (deriv->children);
- derivation *child;
- while (gl_list_iterator_next (&it, (const void **) &child, NULL))
+ derivation *child = NULL;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
size += derivation_size (child);
return size;
}
@@ -136,10 +139,12 @@ derivation_print (const derivation *deriv, FILE *f)
fprintf (f, " %s", sym->tag);
return;
}
- gl_list_iterator_t it = gl_list_iterator (deriv->children);
- derivation *child;
+
fprintf (f, " %s ::=[", sym->tag);
- while (gl_list_iterator_next (&it, (const void **) &child, NULL))
+ derivation *child;
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
{
derivation_print (child, f);
fputs (" ", f);
@@ -162,10 +167,11 @@ derivation_print_leaves (const derivation *deriv, FILE *f)
return;
}
- gl_list_iterator_t it = gl_list_iterator (deriv->children);
const char *sep = "";
derivation *child;
- while (gl_list_iterator_next (&it, (const void **) &child, NULL))
+ for (gl_list_iterator_t it = gl_list_iterator (deriv->children);
+ derivation_list_next (&it, &child);
+ )
{
fputs (sep, f);
sep = " ";
diff --git a/src/derivation.h b/src/derivation.h
index 849c85bb..397a5be6 100644
--- a/src/derivation.h
+++ b/src/derivation.h
@@ -37,6 +37,18 @@ static inline derivation_list derivation_list_new (void)
return gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
}
+static inline bool
+derivation_list_next (gl_list_iterator_t *it, derivation **d)
+{
+ const void *p = NULL;
+ bool res = gl_list_iterator_next (it, &p, NULL);
+ if (res)
+ *d = (derivation *) p;
+ else
+ gl_list_iterator_free (it);
+ return res;
+}
+
void derivation_list_append (derivation_list dl, derivation *d);
void derivation_list_prepend (derivation_list dl, derivation *d);
void derivation_list_free (derivation_list dl);
diff --git a/src/parse-simulation.c b/src/parse-simulation.c
index 0dc9a1dd..d22502ed 100644
--- a/src/parse-simulation.c
+++ b/src/parse-simulation.c
@@ -253,10 +253,12 @@ parse_state_completed_steps (const parse_state *ps, int
*shifts, int *production
gl_list_t sis = root_ps->state_items.contents;
int count = 0;
- gl_list_iterator_t it = gl_list_iterator (sis);
+
state_item *last = NULL;
state_item *next = NULL;
- while (gl_list_iterator_next (&it, (const void **) &next, NULL))
+ for (gl_list_iterator_t it = gl_list_iterator (sis);
+ state_item_list_next (&it, &next);
+ )
{
if (last && last->state == next->state)
++count;
@@ -285,22 +287,24 @@ list_flatten_and_split (gl_list_t *list, gl_list_t *rets,
int split, int n,
int ret_array = 0;
for (int i = 0; i < n; ++i)
{
+ const void *p = NULL;
gl_list_iterator_t it = gl_list_iterator (list[i]);
- gl_list_t l;
- while (gl_list_iterator_next (&it, (const void **) &l, NULL))
- {
- if (!l)
- continue;
- gl_list_iterator_t it2 = gl_list_iterator (l);
- void *si;
- while (gl_list_iterator_next (&it2, (const void **) &si, NULL))
- {
- if (ret_index++ == split)
- ++ret_array;
- if (rets[ret_array])
- append_fn (rets[ret_array], si);
- }
- }
+ while (gl_list_iterator_next (&it, &p, NULL))
+ if (p)
+ {
+ gl_list_t l = (gl_list_t) p;
+ const void *si = NULL;
+ gl_list_iterator_t it2 = gl_list_iterator (l);
+ while (gl_list_iterator_next (&it2, &si, NULL))
+ {
+ if (ret_index++ == split)
+ ++ret_array;
+ if (rets[ret_array])
+ append_fn (rets[ret_array], si);
+ }
+ gl_list_iterator_free (&it2);
+ }
+ gl_list_iterator_free (&it);
}
}
@@ -540,11 +544,12 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
}
else
{
- gl_list_iterator_t it = gl_list_iterator (prev);
- state_item *psis;
- while (gl_list_iterator_next (&it, (const void **) &psis, NULL))
+ state_item *psis = NULL;
+ for (gl_list_iterator_t it = gl_list_iterator (prev);
+ state_item_list_next (&it, &psis);
+ )
{
- //Prepend the result from the reverse production
+ // Prepend the result from the reverse production.
parse_state *copy = copy_parse_state (true, new_root);
ps_si_prepend (copy, psis);
diff --git a/src/parse-simulation.h b/src/parse-simulation.h
index 66650970..2e49d769 100644
--- a/src/parse-simulation.h
+++ b/src/parse-simulation.h
@@ -74,6 +74,18 @@
typedef struct parse_state parse_state;
typedef gl_list_t parse_state_list;
+static inline bool
+parse_state_list_next (gl_list_iterator_t *it, parse_state **ps)
+{
+ const void *p = NULL;
+ bool res = gl_list_iterator_next (it, &p, NULL);
+ if (res)
+ *ps = (parse_state *) p;
+ else
+ gl_list_iterator_free (it);
+ return res;
+}
+
parse_state *new_parse_state (const state_item *conflict);
size_t parse_state_hasher (const parse_state *ps, size_t max);
diff --git a/src/state-item.h b/src/state-item.h
index 3e606b6e..63841a2a 100644
--- a/src/state-item.h
+++ b/src/state-item.h
@@ -92,4 +92,17 @@ void state_items_free (void);
bool production_allowed (const state_item *si, const state_item *next);
+static inline bool
+state_item_list_next (gl_list_iterator_t *it, state_item **si)
+{
+ const void *p = NULL;
+ bool res = gl_list_iterator_next (it, &p, NULL);
+ if (res)
+ *si = (state_item *) p;
+ else
+ gl_list_iterator_free (it);
+ return res;
+}
+
+
#endif /* STATE_ITEM_H */
--
2.26.2