[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 7/7] cex: replace state-item data structures
|
From: |
Vincent Imbimbo |
|
Subject: |
[PATCH 7/7] cex: replace state-item data structures |
|
Date: |
Thu, 21 May 2020 22:13:17 -0400 |
* src/state-item.h: add trans, prods, and revs edges to state-item struct.
Remove si_trans, si_revs, and si_prods_lookup.
* src/state-item.c, src/lssi.c, src/parse-simulation.c, src/counterexample.c:
update state-item API usage accordingly.
---
src/counterexample.c | 9 +++---
src/lssi.c | 20 ++++++-------
src/parse-simulation.c | 18 +++++-------
src/state-item.c | 66 ++++++++++++++++++++----------------------
src/state-item.h | 21 +++++---------
5 files changed, 62 insertions(+), 72 deletions(-)
diff --git a/src/counterexample.c b/src/counterexample.c
index 6201d9f3..d5dca5e3 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -196,7 +196,7 @@ expand_to_conflict (state_item_number start, symbol_number
conflict_sym)
// add each production to the search
bitset_iterator biter;
state_item_number sin;
- bitset sib = si_prods_lookup (node->si);
+ bitset sib = silast->prods;
BITSET_FOR_EACH (biter, sib, sin, 0)
{
// ignore productions already in the path
@@ -208,7 +208,7 @@ expand_to_conflict (state_item_number start, symbol_number
conflict_sym)
// for nullable nonterminals, add its goto to the search
if (nullable[sym - ntokens])
{
- si_bfs_node *next = si_bfs_new (si_trans[node->si], node);
+ si_bfs_node *next = si_bfs_new (silast->trans, node);
gl_list_add_last (queue, next);
}
}
@@ -304,7 +304,8 @@ complete_diverging_example (symbol_number conflict_sym,
// 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 = si_trans[nsi])
+ !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
@@ -433,7 +434,7 @@ nonunifying_shift_path (gl_list_t reduce_path, state_item
*shift_conflict)
// 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 = si_revs[sis->si];
+ bitset rsi = search_si->revs;
bitset_iterator biter;
state_item_number sin;
BITSET_FOR_EACH (biter, rsi, sin, 0)
diff --git a/src/lssi.c b/src/lssi.c
index 293daafb..406a5ebb 100644
--- a/src/lssi.c
+++ b/src/lssi.c
@@ -132,7 +132,7 @@ eligible_state_items (state_item *target)
continue;
bitset_set (result, si - state_items);
// search all reverse edges.
- bitset rsi = si_revs[si - state_items];
+ bitset rsi = si->revs;
bitset_iterator biter;
state_item_number sin;
BITSET_FOR_EACH (biter, rsi, sin, 0)
@@ -175,13 +175,13 @@ shortest_path_from_start (state_item_number target,
symbol_number next_sym)
finished = true;
break;
}
+ state_item *si = state_items + last;
// Transitions don't change follow_L
- if (si_trans[last] >= 0)
+ if (si->trans >= 0)
{
- state_item_number nextSI = si_trans[last];
- if (bitset_test (eligible, nextSI))
+ if (bitset_test (eligible, si->trans))
{
- lssi *next = new_lssi (nextSI, n, n->lookahead, false);
+ lssi *next = new_lssi (si->trans, n, n->lookahead, false);
append_lssi (next, visited, queue);
}
}
@@ -192,13 +192,11 @@ shortest_path_from_start (state_item_number target,
symbol_number next_sym)
// if the symbol is not nullable, follow_L is its FIRSTS set
// if the symbol is nullable, follow_L is its FIRSTS set unioned with
// this logic applied to the next symbol in the rule
- bitset p = si_prods_lookup (last);
- if (p)
+ if (si->prods)
{
- state_item si = state_items[last];
// Compute follow_L as above
bitset lookahead = bitset_create (nsyms, BITSET_FIXED);
- item_number *pos = si.item + 1;
+ item_number *pos = si->item + 1;
for (; !item_number_is_rule_number (*pos); ++pos)
{
item_number it = *pos;
@@ -221,7 +219,7 @@ shortest_path_from_start (state_item_number target,
symbol_number next_sym)
// Try all possible production steps within this parser state.
bitset_iterator biter;
state_item_number nextSI;
- BITSET_FOR_EACH (biter, p, nextSI, 0)
+ BITSET_FOR_EACH (biter, si->prods, nextSI, 0)
{
if (!bitset_test (eligible, nextSI))
continue;
@@ -320,7 +318,7 @@ lssi_reverse_production (const state_item *si, bitset
lookahead)
// compatible with the lookahead.
bitset_iterator biter;
state_item_number sin;
- BITSET_FOR_EACH (biter, si_revs[si - state_items], sin, 0)
+ BITSET_FOR_EACH (biter, si->revs, sin, 0)
{
state_item *prevsi = state_items + sin;
if (!production_allowed (prevsi, si))
diff --git a/src/parse-simulation.c b/src/parse-simulation.c
index 6886593e..e314bee2 100644
--- a/src/parse-simulation.c
+++ b/src/parse-simulation.c
@@ -400,8 +400,8 @@ nullable_closure (parse_state *ps, state_item *si,
parse_state_list state_list)
{
parse_state *current_ps = ps;
state_item_number prev_sin = si - state_items;
- for (state_item_number sin = si_trans[prev_sin];
- sin != -1; prev_sin = sin, sin = si_trans[sin])
+ for (state_item_number sin = si->trans; sin != -1;
+ prev_sin = sin, sin = state_items[sin].trans)
{
state_item *psi = state_items + prev_sin;
symbol_number sp = item_number_as_symbol_number (*psi->item);
@@ -424,7 +424,7 @@ simulate_transition (parse_state *ps)
// Transition on the same next symbol, taking nullable
// symbols into account.
gl_list_t result = parse_state_list_new ();
- state_item_number si_next = si_trans[si - state_items];
+ state_item_number si_next = si->trans;
// check for disabled transition, shouldn't happen
// as any state_items that lead to these should be
// disabled.
@@ -463,12 +463,11 @@ simulate_production (parse_state *ps, symbol_number
compat_sym)
{
gl_list_t result = parse_state_list_new ();
const state_item *si = parse_state_tail (ps);
- bitset prod = si_prods_lookup (si - state_items);
- if (prod)
+ if (si->prods)
{
bitset_iterator biter;
state_item_number sin;
- BITSET_FOR_EACH (biter, prod, sin, 0)
+ BITSET_FOR_EACH (biter, si->prods, sin, 0)
{
// Take production step only if lhs is not nullable and
// if first rhs symbol is compatible with compat_sym
@@ -515,7 +514,7 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
if (s_size != rule_len + 1)
{
state_item *tail = (state_item *) new_root->state_items.tail_elt;
- ps_si_append (new_root, state_items + si_trans[tail - state_items]);
+ ps_si_append (new_root, state_items + tail->trans);
parse_state_list_append (result, new_root);
}
else
@@ -545,7 +544,7 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
copy = copy_parse_state (false, copy);
struct si_chunk *sis = ©->state_items;
const state_item *tail = sis->tail_elt;
- ps_si_append (copy, state_items + si_trans[tail - state_items]);
+ ps_si_append (copy, state_items + tail->trans);
parse_state_list_append (result, copy);
nullable_closure (copy, (state_item *) sis->tail_elt, result);
}
@@ -560,12 +559,11 @@ parser_prepend (parse_state *ps)
{
gl_list_t result = parse_state_list_new ();
const state_item *head = ps->state_items.head_elt;
- bitset prev = si_revs[head - state_items];
symbol_number prepend_sym =
item_number_as_symbol_number (*(head->item - 1));
bitset_iterator biter;
state_item_number sin;
- BITSET_FOR_EACH (biter, prev, sin, 0)
+ BITSET_FOR_EACH (biter, head->revs, sin, 0)
{
parse_state *copy = copy_parse_state (true, ps);
ps_si_prepend (copy, state_items + sin);
diff --git a/src/state-item.c b/src/state-item.c
index 62d2d210..23561e87 100644
--- a/src/state-item.c
+++ b/src/state-item.c
@@ -35,10 +35,6 @@ size_t nstate_items;
state_item_number *state_item_map;
state_item *state_items;
-state_item_number *si_trans;
-bitsetv si_revs;
-Hash_table *si_prods;
-
// hash functions for index -> bitset hash maps
typedef struct
{
@@ -118,7 +114,9 @@ state_item_set (state_item_number sidx, const state *s,
item_number off)
state_items[sidx].state = s;
state_items[sidx].item = &ritem[off];
state_items[sidx].lookahead = NULL;
- si_trans[sidx] = -1;
+ state_items[sidx].trans = -1;
+ state_items[sidx].prods = NULL;
+ state_items[sidx].revs = bitset_create (nstate_items, BITSET_SPARSE);
}
/**
@@ -144,8 +142,6 @@ init_state_items (void)
}
state_item_map = xnmalloc (nstates + 1, sizeof (state_item_number));
state_items = xnmalloc (nstate_items, sizeof (state_item));
- si_trans = xnmalloc (nstate_items, sizeof (state_item_number));
- si_revs = bitsetv_create (nstate_items, nstate_items, BITSET_SPARSE);
state_item_number sidx = 0;
for (int i = 0; i < nstates; ++i)
{
@@ -240,8 +236,8 @@ init_trans (void)
state_item_number dstSI =
state_item_index_lookup (dst->number, k);
- si_trans[j] = dstSI;
- bitset_set (si_revs[dstSI], j);
+ state_items[j].trans = dstSI;
+ bitset_set (state_items[dstSI].revs, j);
break;
}
}
@@ -250,16 +246,9 @@ init_trans (void)
}
}
-bitset
-si_prods_lookup (state_item_number si)
-{
- return hash_pair_lookup (si_prods, si);
-}
-
static void
init_prods (void)
{
- si_prods = hash_pair_table_create (nstate_items);
for (int i = 0; i < nstates; ++i)
{
state *s = states[i];
@@ -299,13 +288,13 @@ init_prods (void)
bitset copy = bitset_create (nstate_items, BITSET_SPARSE);
bitset_copy (copy, lb);
// update prods.
- hash_pair_insert (si_prods, j, copy);
+ state_items[j].prods = copy;
// update revs.
bitset_iterator biter;
state_item_number prod;
BITSET_FOR_EACH (biter, copy, prod, 0)
- bitset_set (si_revs[prod], j);
+ bitset_set (state_items[prod].revs, j);
}
}
hash_free (closure_map);
@@ -340,7 +329,7 @@ gen_lookaheads (void)
prev->lookahead = lookahead;
if (SI_TRANSITION (prev))
{
- bitset rsi = si_revs[prev - state_items];
+ bitset rsi = state_items[prev - state_items].revs;
bitset_iterator biter;
state_item_number sin;
BITSET_FOR_EACH (biter, rsi, sin, 0)
@@ -400,8 +389,11 @@ init_firsts (void)
static inline void
disable_state_item (state_item_number sin)
{
- si_trans[sin] = -2;
- hash_pair_remove (si_prods, sin);
+ state_item *si = state_items + sin;
+ si->trans = -2;
+ bitset_free (si->revs);
+ if (si->prods)
+ bitset_free (si->prods);
}
/*
@@ -414,10 +406,10 @@ prune_disabled_paths (void)
for (int i = nstate_items - 1; i >= 0; --i)
{
state_item *si = state_items + i;
- if (si_trans[i] == -1 && item_number_is_symbol_number (*si->item))
+ if (si->trans == -1 && item_number_is_symbol_number (*si->item))
{
// disable the transitions out of i
- for (state_item_number j = si_trans[i]; j != -1; j = si_trans[j])
+ for (state_item_number j = si->trans; j != -1; j =
state_items[j].trans)
disable_state_item (j);
gl_list_t queue =
@@ -432,9 +424,8 @@ prune_disabled_paths (void)
const state_item *prev = gl_list_get_at (queue, 0);
gl_list_remove_at (queue, 0);
state_item_number prev_num = prev - state_items;
- disable_state_item (prev_num);
- bitset rsi = si_revs[prev_num];
+ bitset rsi = prev->revs;
bitset_iterator biter;
state_item_number sin;
BITSET_FOR_EACH (biter, rsi, sin, 0)
@@ -443,11 +434,12 @@ prune_disabled_paths (void)
gl_list_add_first (queue, &state_items[sin]);
else
{
- bitset p = si_prods_lookup (sin);
+ bitset p = state_items[sin].prods;
if (p)
bitset_reset (p, prev_num);
}
}
+ disable_state_item (prev_num);
}
gl_list_free (queue);
}
@@ -463,7 +455,7 @@ print_state_item (const state_item *si, FILE *out)
}
/**
- * Report set counts and the state_item graph if trace is enabled
+ * Report the state_item graph
*/
static void
state_items_report (void)
@@ -474,15 +466,16 @@ state_items_report (void)
printf ("State %d:\n", i);
for (int j = state_item_map[i]; j < state_item_map[i + 1]; ++j)
{
- item_print (state_items[j].item, NULL, stdout);
+ state_item *si = state_items + j;
+ item_print (si->item, NULL, stdout);
puts ("");
- if (si_trans[j] >= 0)
+ if (si->trans >= 0)
{
fputs (" -> ", stdout);
- print_state_item (state_items + si_trans[j], stdout);
+ print_state_item (state_items + si->trans, stdout);
}
- bitset sets[2] = { si_prods_lookup (j), si_revs[j] };
+ bitset sets[2] = { si->prods, si->revs };
const char *txt[2] = { " => ", " <- " };
for (int seti = 0; seti < 2; ++seti)
{
@@ -533,9 +526,14 @@ state_items_init (void)
void
state_items_free (void)
{
- hash_free (si_prods);
- bitsetv_free (si_revs);
- free (si_trans);
+ for (int i = 0; i < nstate_items; ++i)
+ if (!SI_DISABLED(i))
+ {
+ state_item *si = state_items + i;
+ if (si->prods)
+ bitset_free (si->prods);
+ bitset_free (si->revs);
+ }
free (state_items);
bitsetv_free (firsts);
}
diff --git a/src/state-item.h b/src/state-item.h
index 3b98132d..3e606b6e 100644
--- a/src/state-item.h
+++ b/src/state-item.h
@@ -42,20 +42,18 @@
There are two type of edges in this graph transitions and
productions. Transitions are the same as transitions from the
parser except edges are only between items from the same
- rule. These are stored as an array "si_trans" (as most items will
- have transitions) which are indexed the same way as state_items.
+ rule.
Productions are edges from items with a nonterminal after the dot to
the production of that nonterminal in the same state. These edges are
- stored as a hash map "si_prods" from a state_item to a set of what
productions
- it goes from/to
+ stored as a bitset in a state-item.
- The inverses of these edges are stored in an array of bitsets,
- "si_revs." A state-item that begins with a dot will have reverse
+ The inverses of these edges are stored in a bitset in the state-item,
+ "revs." A state-item that begins with a dot will have reverse
production edges, and all others will have reverse transition
edges. */
-# define SI_DISABLED(sin) (si_trans[sin] == -2)
+# define SI_DISABLED(sin) (state_items[sin].trans == -2)
# define SI_PRODUCTION(si) ((si) == state_items || *((si)->item - 1) < 0)
# define SI_TRANSITION(si) ((si) != state_items && *((si)->item - 1) >= 0)
@@ -65,6 +63,9 @@ typedef struct
{
const state *state;
item_number *item;
+ state_item_number trans;
+ bitset prods;
+ bitset revs;
bitset lookahead;
} state_item;
@@ -77,10 +78,6 @@ extern state_item_number *state_item_map;
/** Array mapping state_item_numbers to state_items */
extern state_item *state_items;
-/** state-item graph edges */
-extern state_item_number *si_trans;
-extern bitsetv si_revs;
-
state_item *state_item_lookup (state_number s, state_item_number off);
static inline state_item_number
@@ -89,8 +86,6 @@ state_item_index_lookup (state_number s, state_item_number
off)
return state_item_map[s] + off;
}
-bitset si_prods_lookup (state_item_number si);
-
void state_items_init (void);
void print_state_item (const state_item *si, FILE *out);
void state_items_free (void);
--
2.20.1 (Apple Git-117)
- [PATCH 0/7] Fixing all cex leaks, Vincent Imbimbo, 2020/05/21
- [PATCH 1/7] cex: dervation reference counting, Vincent Imbimbo, 2020/05/21
- [PATCH 2/7] cex: fix parse state leaks, Vincent Imbimbo, 2020/05/21
- [PATCH 3/7] cex: fix lssi leaks, Vincent Imbimbo, 2020/05/21
- [PATCH 4/7] cex: fix counterexample leak, Vincent Imbimbo, 2020/05/21
- [PATCH 5/7] cex: fix miscellaneous leaks, Vincent Imbimbo, 2020/05/21
- [PATCH 6/7] cex: fix bad reference counting, Vincent Imbimbo, 2020/05/21
- [PATCH 7/7] cex: replace state-item data structures,
Vincent Imbimbo <=
- Re: [PATCH 0/7] Fixing all cex leaks, Akim Demaille, 2020/05/22