[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 2/7] cex: fix parse state leaks
From: |
Vincent Imbimbo |
Subject: |
[PATCH 2/7] cex: fix parse state leaks |
Date: |
Thu, 21 May 2020 22:13:12 -0400 |
* src/parse_simulation.c: Fix bug in parse_state_free.
Free new_root when simulate_reduction generates zero states.
* src/parse-simulation.c, src/parse-simulation.h: Create parse_state_list type.
(parse_state_list_append) New.
* src/parse-simulation.c, src/parse-simulation.h, src/counterexample.c:
Replace all uses of lists of parse states and appends to parse_state_lists with
the new API.
---
src/counterexample.c | 16 +++++-----
src/parse-simulation.c | 69 ++++++++++++++++++++++++------------------
src/parse-simulation.h | 9 +++---
3 files changed, 54 insertions(+), 40 deletions(-)
diff --git a/src/counterexample.c b/src/counterexample.c
index 83813162..7e9c5656 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -701,7 +701,8 @@ 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);
- gl_list_t prods = simulate_production (ss->states[parser_state], other_sym);
+ parse_state_list prods =
+ simulate_production (ss->states[parser_state], other_sym);
int complexity = ss->complexity + PRODUCTION_COST;
gl_list_iterator_t it = gl_list_iterator (prods);
@@ -751,7 +752,8 @@ reduction_step (search_state *ss, const item_number
*conflict_item,
}
// FIXME: search_state *new_root = copy_search_state (ss);
- gl_list_t reduced = simulate_reduction (ps, rule_len, symbol_set);
+ 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))
@@ -787,7 +789,7 @@ search_state_prepend (search_state *ss, symbol_number sym,
bitset guide)
if (prod1 != SI_PRODUCTION (si2src))
{
int prod_state = prod1 ? 0 : 1;
- gl_list_t prev = parser_prepend (ss->states[prod_state]);
+ 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))
@@ -813,8 +815,8 @@ search_state_prepend (search_state *ss, symbol_number sym,
bitset guide)
int complexity_cost = prod1 ? PRODUCTION_COST : UNSHIFT_COST;
complexity_cost *= 2;
- gl_list_t prev1 = parser_prepend (ss->states[0]);
- gl_list_t prev2 = parser_prepend (ss->states[1]);
+ 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
@@ -915,8 +917,8 @@ generate_next_states (search_state *ss, state_item
*conflict1,
if (*si1->item == *si2->item)
{
int complexity = ss->complexity + 2 * SHIFT_COST;
- gl_list_t trans1 = simulate_transition (ps1);
- gl_list_t trans2 = simulate_transition (ps2);
+ 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))
diff --git a/src/parse-simulation.c b/src/parse-simulation.c
index 5648bd5a..6886593e 100644
--- a/src/parse-simulation.c
+++ b/src/parse-simulation.c
@@ -199,7 +199,8 @@ void
free_parse_state (parse_state *original_ps)
{
bool free_contents = true;
- for (parse_state *ps = original_ps; ps && free_contents; ps = ps->parent)
+ parse_state *parent_ps = NULL;
+ for (parse_state *ps = original_ps; ps && free_contents; ps = parent_ps)
{
--ps->reference_count;
free_contents = (ps->reference_count == 1 && ps->free_contents_early)
@@ -213,11 +214,11 @@ free_parse_state (parse_state *original_ps)
if (ps->derivs.contents)
derivation_list_free (ps->derivs.contents);
}
+ parent_ps = ps->parent;
if (ps->reference_count <= 0)
{
free (ps);
++frees;
- break;
}
}
}
@@ -295,7 +296,7 @@ list_flatten_and_split (gl_list_t *list, gl_list_t *rets,
int split, int n,
}
}
-static gl_list_t
+static parse_state_list
parse_state_list_new (void)
{
return gl_list_create_empty (GL_LINKED_LIST, NULL, NULL,
@@ -303,6 +304,12 @@ parse_state_list_new (void)
true);
}
+void parse_state_list_append (parse_state_list pl, parse_state *ps)
+{
+ parse_state_retain (ps);
+ gl_list_add_last (pl, ps);
+}
+
// Emulates a reduction on a parse state by popping some amount of
// derivations and state_items off of the parse_state and returning
// the result in ret. Returns the derivation of what's popped.
@@ -389,7 +396,7 @@ parse_state_lists (parse_state *ps, gl_list_t *sitems,
* nullable symbols whenever possible from the given state_item.
*/
void
-nullable_closure (parse_state *ps, state_item *si, gl_list_t state_list)
+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;
@@ -405,8 +412,7 @@ nullable_closure (parse_state *ps, state_item *si,
gl_list_t state_list)
current_ps = copy_parse_state (false, current_ps);
ps_si_append (current_ps, nsi);
ps_derivs_append (current_ps, derivation_new_leaf (sp));
- parse_state_retain (current_ps);
- gl_list_add_last (state_list, current_ps);
+ parse_state_list_append (state_list, current_ps);
}
}
@@ -427,8 +433,7 @@ simulate_transition (parse_state *ps)
parse_state *next_ps = copy_parse_state (false, ps);
ps_si_append (next_ps, state_items + si_next);
ps_derivs_append (next_ps, derivation_new_leaf (sym));
- parse_state_retain (next_ps);
- gl_list_add_last (result, next_ps);
+ parse_state_list_append (result, next_ps);
nullable_closure (next_ps, state_items + si_next, result);
return result;
@@ -473,8 +478,7 @@ simulate_production (parse_state *ps, symbol_number
compat_sym)
continue;
parse_state *next_ps = copy_parse_state (false, ps);
ps_si_append (next_ps, next);
- parse_state_retain (next_ps);
- gl_list_add_last (result, next_ps);
+ parse_state_list_append (result, next_ps);
if (next_ps->depth >= 0)
++next_ps->depth;
nullable_closure (next_ps, next, result);
@@ -512,8 +516,7 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
{
state_item *tail = (state_item *) new_root->state_items.tail_elt;
ps_si_append (new_root, state_items + si_trans[tail - state_items]);
- parse_state_retain (new_root);
- gl_list_add_last (result, new_root);
+ parse_state_list_append (result, new_root);
}
else
{
@@ -521,22 +524,31 @@ simulate_reduction (parse_state *ps, int rule_len, bitset
symbol_set)
// with possible source state-items.
const state_item *head = ps->state_items.head_elt;
gl_list_t prev = lssi_reverse_production (head, symbol_set);
- gl_list_iterator_t it = gl_list_iterator (prev);
- state_item *psis;
- while (gl_list_iterator_next (&it, (const void **) &psis, NULL))
+ // TODO: better understand what causes this case.
+ if (gl_list_size (prev) == 0)
+ {
+ // new_root needs to have an RC of 1 to be freed correctly here.
+ parse_state_retain (new_root);
+ free_parse_state (new_root);
+ }
+ else
{
- //Prepend the result from the reverse production
- parse_state *copy = copy_parse_state (true, new_root);
- ps_si_prepend (copy, psis);
-
- // Append the left hand side to the end of the parser state
- 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]);
- parse_state_retain (copy);
- gl_list_add_last (result, copy);
- nullable_closure (copy, (state_item *) sis->tail_elt, result);
+ gl_list_iterator_t it = gl_list_iterator (prev);
+ state_item *psis;
+ while (gl_list_iterator_next (&it, (const void **) &psis, NULL))
+ {
+ //Prepend the result from the reverse production
+ parse_state *copy = copy_parse_state (true, new_root);
+ ps_si_prepend (copy, psis);
+
+ // Append the left hand side to the end of the parser state
+ 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]);
+ parse_state_list_append (result, copy);
+ nullable_closure (copy, (state_item *) sis->tail_elt, result);
+ }
}
gl_list_free (prev);
}
@@ -556,11 +568,10 @@ parser_prepend (parse_state *ps)
BITSET_FOR_EACH (biter, prev, sin, 0)
{
parse_state *copy = copy_parse_state (true, ps);
- parse_state_retain (copy);
ps_si_prepend (copy, state_items + sin);
if (SI_TRANSITION (head))
ps_derivs_prepend (copy, derivation_new_leaf (prepend_sym));
- gl_list_add_last (result, copy);
+ parse_state_list_append (result, copy);
}
return result;
}
diff --git a/src/parse-simulation.h b/src/parse-simulation.h
index a912f012..ae9410f6 100644
--- a/src/parse-simulation.h
+++ b/src/parse-simulation.h
@@ -72,6 +72,7 @@
*/
typedef struct parse_state parse_state;
+typedef gl_list_t parse_state_list;
parse_state *new_parse_state (const state_item *conflict);
@@ -110,22 +111,22 @@ void parse_state_lists (parse_state *ps, gl_list_t
*state_items,
/* Look at the tail state-item of the parse state and transition on the symbol
* after its dot. The symbol gets added to derivs, and the resulting state-item
* is appended to state-items. */
-gl_list_t simulate_transition (parse_state *ps);
+parse_state_list simulate_transition (parse_state *ps);
/* Look at all of the productions for the non-terminal following the dot in
the tail
* state-item. Appends to state-items each production state-item which may
start with
* compat_sym. */
-gl_list_t simulate_production (parse_state *ps, symbol_number compat_sym);
+parse_state_list simulate_production (parse_state *ps, symbol_number
compat_sym);
/* Removes the last rule_len state-items along with their derivations. A new
state-item is
* appended representing the goto after the reduction. A derivation for the
non-terminal that
* was just reduced is appended which consists of the list of derivations that
were just removed. */
-gl_list_t simulate_reduction (parse_state *ps, int rule_len,
+parse_state_list simulate_reduction (parse_state *ps, int rule_len,
bitset symbol_set);
/* Generate states with a state-item prepended for each state-item that has a
* transition or production step to ps's head. */
-gl_list_t parser_prepend (parse_state *ps);
+parse_state_list parser_prepend (parse_state *ps);
void print_parse_state (parse_state *ps);
--
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 <=
- [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, 2020/05/21
- Re: [PATCH 0/7] Fixing all cex leaks, Akim Demaille, 2020/05/22