[PATCH 1/7] cex: dervation reference counting

* src/derivation.h, src/derivation.c: Make derivation struct opaque.
Add derivation_list type for clarity.
(derivation_list_new): New.
(derivation_list_append): New.
(derivation_list_prepend): New.
(derivation_new_leaf): New constructor for derivations with no children.
* src/counterexample.c, src/parse-simulation.c, src/parse-simulation.h: Replace uses of gl_list_t containing derivations with derivation_list and its API.
Replace calls of dervation_new using null children with derivation_new_leaf
* src/parse-simulation.c: replace ps_chunk and its API with typed versions si_chunk and deriv_chunk.
* src/parse-simlation.h, src/parse-simulation.c: Remove parse_state_retain_deriv in favor of derivation reference counting.
* src/counterexample.c: Remove search_state_retain_deriv.
---
 src/counterexample.c   |  95 +++++++++++--------------
 src/derivation.c       |  71 +++++++++++++++++--
 src/derivation.h       |  26 +++++--
 src/parse-simulation.c | 157 +++++++++++++++++++++++------------------
 src/parse-simulation.h |   5 +-
 5 files changed, 215 insertions(+), 139 deletions(-)

diff --git a/src/counterexample.c b/src/counterexample.c
index 497d8229..83813162 100644
--- a/src/counterexample.c
+++ b/src/counterexample.c
@@ -169,7 +169,7 @@ si_bfs_free (si_bfs_node *n)
  *
  * this returns the derivation of the productions that lead to conflict_sym
  */
-static inline gl_list_t
+static inline derivation_list
 expand_to_conflict (state_item_number start, symbol_number conflict_sym)
 {
   si_bfs_node *init = si_bfs_new (start, NULL);
@@ -216,11 +216,9 @@ expand_to_conflict (state_item_number start, symbol_number conflict_sym)
       exit (1);
     }
 
-  derivation *dinit = derivation_new (conflict_sym, NULL);
-  gl_list_t result =
-    gl_list_create (GL_LINKED_LIST, NULL, NULL,
-                    (gl_listelement_dispose_fn) derivation_free,
-                    true, 1, (const void **) &dinit);
+  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.
 
@@ -232,23 +230,22 @@ expand_to_conflict (state_item_number start, symbol_number conflict_sym)
         {
           item_number *i = NULL;
           for (i = pos + 1; !item_number_is_rule_number (*i); ++i)
-            gl_list_add_last (result, derivation_new (*i, NULL));
+            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);
-          result =
-            gl_list_create (GL_LINKED_LIST, NULL, NULL,
-                            (gl_listelement_dispose_fn) derivation_free,
-                            true, 1, (const void **) &deriv);
+          result = derivation_list_new ();
+          derivation_list_append (result, deriv);
         }
       else
         {
           symbol_number sym = item_number_as_symbol_number (*(pos - 1));
-          derivation *deriv = derivation_new (sym, NULL);
-          gl_list_add_first (result, deriv);
+          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;
 }
@@ -263,16 +260,15 @@ expand_to_conflict (state_item_number start, symbol_number conflict_sym)
  */
 static derivation *
 complete_diverging_example (symbol_number conflict_sym,
-                            gl_list_t path, gl_list_t derivs)
+                            gl_list_t path, derivation_list derivs)
 {
   // The idea is to transfer each pending symbol on the productions
   // associated with the given StateItems to the resulting derivation.
-  gl_list_t result =
-    gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+  derivation_list result = derivation_list_new ();
   bool lookahead_required = false;
   if (!derivs)
     {
-      derivs = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+      derivs = derivation_list_new ();
       gl_list_add_last (result, derivation_dot ());
       lookahead_required = true;
     }
@@ -295,9 +291,8 @@ complete_diverging_example (symbol_number conflict_sym,
       if (gl_list_size (result) == 1 && !item_number_is_rule_number (pos)
           && gl_list_get_at (result, 0) == derivation_dot() )
         {
-          gl_list_add_last (result,
-                            derivation_new (item_number_as_symbol_number
-                                            (pos), NULL));
+          derivation_list_append (result,
+            derivation_new_leaf (item_number_as_symbol_number (pos)));
           lookahead_required = false;
         }
       item_number *i = item;
@@ -313,7 +308,7 @@ complete_diverging_example (symbol_number conflict_sym,
           symbol_number sym = item_number_as_symbol_number (*i);
           if (!lookahead_required || sym == conflict_sym)
             {
-              gl_list_add_last (result, derivation_new (sym, NULL));
+              derivation_list_append (result, derivation_new_leaf (sym));
               lookahead_required = false;
               continue;
             }
@@ -330,25 +325,19 @@ complete_diverging_example (symbol_number conflict_sym,
           if (bitset_test (FIRSTS (sym), conflict_sym))
             {
               lookahead_required = false;
-              gl_list_t next_derivs = expand_to_conflict (nsi,
-                                                          conflict_sym);
+              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))
-                gl_list_add_last (result, d);
+                derivation_list_append (result, d);
               i += gl_list_size (next_derivs) - 1;
-              // next_derivs is leaked to prevent the copied derivations from
-              // being freed. It is somewhat difficult to for expand_to_conflict
-              // to decide which derivation list will be the final one that is
-              // returned, so each list frees its derivations when freed.
+              derivation_list_free (next_derivs);
             }
           else if (nullable[sym - ntokens])
             {
-              derivation *d = derivation_new (sym,
-                                              gl_list_create_empty
-                                              (GL_LINKED_LIST, NULL,
-                                               NULL, NULL, 1));
-              gl_list_add_last (result, d);
+              derivation *d = derivation_new_leaf (sym);
+              derivation_list_append (result, d);
             }
           else
             {
@@ -356,7 +345,7 @@ complete_diverging_example (symbol_number conflict_sym,
               // having the conflict symbol in its lookahead, no example
               // containing the symbol after the conflict item
               // can be found.
-              gl_list_add_last (result, derivation_new (1, NULL));
+              derivation_list_append (result, derivation_new_leaf (1));
               lookahead_required = false;
             }
         }
@@ -371,19 +360,20 @@ complete_diverging_example (symbol_number conflict_sym,
             {
               const void *tmp_deriv = gl_list_node_value (derivs, deriv);
               deriv = gl_list_previous_node (derivs, deriv);
-              gl_list_add_first (result, tmp_deriv);
+              derivation_list_prepend (result, (derivation*)tmp_deriv);
             }
           else
-            gl_list_add_first (result, derivation_new (*i, NULL));
+            derivation_list_prepend (result, derivation_new_leaf (*i));
         }
       // completing the derivation
       derivation *new_deriv = derivation_new (rules[r].lhs->number, result);
-      result =
-        gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
-                        (const void **) &new_deriv);
+      result = derivation_list_new ();
+      derivation_list_append (result, new_deriv);
     }
   derivation *res = (derivation *) gl_list_get_at (result, 0);
-  gl_list_free (result);
+  derivation_retain (res);
+  derivation_list_free (result);
+  derivation_list_free (derivs);
   return res;
 }
 
@@ -567,13 +557,6 @@ search_state_free (search_state *ss)
   free (ss);
 }
 
-static inline void
-search_state_retain_derivs (search_state *ss)
-{
-  parse_state_retain_deriv (ss->states[0]);
-  parse_state_retain_deriv (ss->states[1]);
-}
-
 static void
 search_state_print (search_state *ss)
 {
@@ -608,9 +591,11 @@ complete_diverging_examples(search_state *ss,
   derivation *new_derivs[2];
   for (int i = 0; i < 2; ++i)
     {
-      gl_list_t sitems, derivs;
+      gl_list_t 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], false, true);
 }
@@ -778,6 +763,8 @@ reduction_step (search_state *ss, const item_number *conflict_item,
       gl_list_add_last (result, copy);
     }
   gl_list_free (reduced);
+  if (symbol_set != si->lookahead)
+    bitset_free (symbol_set);
   return result;
 }
 
@@ -1068,17 +1055,16 @@ unifying_example (state_item_number itm1,
                   && has_common_prefix (si1src->item, si2src->item))
                 {
                   // Stage 4: both paths share a prefix
-                  const derivation *d1 = parse_state_derivation (ps1);
-                  const derivation *d2 = parse_state_derivation (ps2);
+                  derivation *d1 = parse_state_derivation (ps1);
+                  derivation *d2 = parse_state_derivation (ps2);
                   if (parse_state_derivation_completed (ps1)
-                      && parse_state_derivation_completed (ps2)
-                      && d1->sym == d2->sym)
+                      && 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, true, false);
-                      // prevent d1/d2 from being freed.
-                      search_state_retain_derivs (ss);
+                      derivation_retain (d1);
+                      derivation_retain (d2);
                       goto cex_search_end;
                     }
                   if (!stage3result)
@@ -1116,7 +1102,6 @@ cex_search_end:;
       if (stage3result)
         {
           cex = complete_diverging_examples (stage3result, next_sym);
-          search_state_retain_derivs (stage3result);
           search_state_free (stage3result);
         }
       // Otherwise, construct a nonunifying counterexample that
diff --git a/src/derivation.c b/src/derivation.c
index 612cb2f9..8f16e17a 100644
--- a/src/derivation.c
+++ b/src/derivation.c
@@ -18,37 +18,94 @@
    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 #include <config.h>
+#include <gl_linked_list.h>
 
 #include "system.h"
 
 #include "derivation.h"
 
-static derivation d_dot = { -1, NULL };
+struct derivation
+{
+  symbol_number sym;
+  gl_list_t children;
+  int reference_count;
+};
+
+static derivation d_dot = { -1, NULL, -1 };
 
-const derivation *
+derivation *
 derivation_dot (void)
 {
   return &d_dot;
 }
 
+void
+derivation_list_append (derivation_list dl, derivation *d)
+{
+  derivation_retain (d);
+  gl_list_add_last (dl, d);
+}
+
+void
+derivation_list_prepend (derivation_list dl, derivation *d)
+{
+  derivation_retain (d);
+  gl_list_add_first (dl, 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))
+    if (d != &d_dot)
+      derivation_free (d);
+  gl_list_free (dl);
+}
+
 derivation *
-derivation_new (symbol_number sym, gl_list_t children)
+derivation_new (symbol_number sym, derivation_list children)
 {
   derivation *deriv = xmalloc (sizeof (derivation));
   deriv->sym = sym;
   deriv->children = children;
+  deriv->reference_count = 0;
   return deriv;
 }
 
+void
+derivation_retain (derivation *d)
+{
+  ++d->reference_count;
+}
+
 void
 derivation_free (derivation *d)
 {
-  if (d && d != &d_dot)
+  if (!d)
+    return;
+  derivation_list free_queue =
+    gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true,
+                    1, (const void **)&d);
+  while (gl_list_size (free_queue) > 0)
     {
-      if (d->children)
-        gl_list_free (d->children);
-      free (d);
+      derivation *deriv = (derivation *) gl_list_get_at (free_queue, 0);
+      if (--deriv->reference_count == 0)
+        {
+          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))
+                if (child != &d_dot)
+                  gl_list_add_last (free_queue, child);
+              gl_list_free (deriv->children);
+            }
+          free (deriv);
+        }
+      gl_list_remove_at (free_queue, 0);
     }
+  gl_list_free (free_queue);
 }
 
 size_t
diff --git a/src/derivation.h b/src/derivation.h
index 0b4c964d..849c85bb 100644
--- a/src/derivation.h
+++ b/src/derivation.h
@@ -20,7 +20,7 @@
 #ifndef DERIVATION_H
 # define DERIVATION_H
 
-# include <gl_list.h>
+# include <gl_xlist.h>
 
 # include "gram.h"
 
@@ -29,18 +29,30 @@
    relevant to the counterexample. The leaves of a derivation form a
    counterexample when printed. */
 
-typedef struct derivation
+typedef gl_list_t derivation_list;
+typedef struct derivation derivation;
+
+static inline derivation_list derivation_list_new (void)
 {
-  symbol_number sym;
-  gl_list_t children;
-} derivation;
+  return gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+}
+
+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);
 
-derivation *derivation_new (symbol_number sym, gl_list_t children);
+derivation *derivation_new (symbol_number sym, derivation_list children);
+
+static inline derivation *derivation_new_leaf (symbol_number sym)
+{
+  return derivation_new (sym, NULL);
+}
 size_t derivation_size (const derivation *deriv);
 void derivation_print (const derivation *deriv, FILE *f);
 void derivation_print_leaves (const derivation *deriv, FILE *f);
 void derivation_free (derivation *deriv);
+void derivation_retain (derivation *deriv);
 
-const derivation *derivation_dot (void);
+derivation *derivation_dot (void);
 
 #endif /* DERIVATION_H */
diff --git a/src/parse-simulation.c b/src/parse-simulation.c
index 0c399e64..5648bd5a 100644
--- a/src/parse-simulation.c
+++ b/src/parse-simulation.c
@@ -27,22 +27,26 @@
 #include "nullable.h"
 #include "parse-simulation.h"
 
-typedef struct
-{
-  // elements newly added in this chunk
-  gl_list_t contents;
-  // properties of the linked list this chunk represents
-  const void *head_elt;
-  const void *tail_elt;
-  size_t total_size;
-} ps_chunk;
-
 typedef struct parse_state
 {
   // path of state-items the parser has traversed
-  ps_chunk state_items;
+  struct si_chunk
+  {
+    // elements newly added in this chunk
+    gl_list_t contents;
+    // properties of the linked list this chunk represents
+    const state_item *head_elt;
+    const state_item *tail_elt;
+    size_t total_size;
+  } state_items;
   // list of derivations of the symbols
-  ps_chunk derivs;
+  struct deriv_chunk
+  {
+    derivation_list contents;
+    const derivation *head_elt;
+    const derivation *tail_elt;
+    size_t total_size;
+  } derivs;
   struct parse_state *parent;
   int reference_count;
   // incremented during productions,
@@ -60,23 +64,47 @@ typedef struct parse_state
 
 
 static void
-ps_chunk_prepend (ps_chunk *chunk, const void *element)
+ps_si_prepend (parse_state *ps, const state_item *si)
+{
+  struct si_chunk *sic = &ps->state_items;
+  gl_list_add_first (sic->contents, si);
+  sic->head_elt = si;
+  ++sic->total_size;
+  if (!sic->tail_elt)
+    sic->tail_elt = si;
+}
+
+static void
+ps_si_append (parse_state *ps, const state_item *si)
 {
-  gl_list_add_first (chunk->contents, element);
-  chunk->head_elt = element;
-  ++chunk->total_size;
-  if (!chunk->tail_elt)
-    chunk->tail_elt = element;
+  struct si_chunk *sic = &ps->state_items;
+  gl_list_add_last (sic->contents, si);
+  sic->tail_elt = si;
+  ++sic->total_size;
+  if (!sic->head_elt)
+    sic->head_elt = si;
 }
 
 static void
-ps_chunk_append (ps_chunk *chunk, const void *element)
+ps_derivs_prepend (parse_state *ps, derivation *d)
 {
-  gl_list_add_last (chunk->contents, element);
-  chunk->tail_elt = element;
-  ++chunk->total_size;
-  if (!chunk->head_elt)
-    chunk->head_elt = element;
+  struct deriv_chunk *dc = &ps->derivs;
+  derivation_list_prepend (dc->contents, d);
+  dc->head_elt = d;
+  ++dc->total_size;
+  if (!dc->tail_elt)
+    dc->tail_elt = d;
+}
+
+static void
+ps_derivs_append (parse_state *ps, derivation *d)
+{
+  struct deriv_chunk *dc = &ps->derivs;
+  derivation_list_append (dc->contents, d);
+  dc->tail_elt = d;
+  ++dc->total_size;
+  if (!dc->head_elt)
+    dc->head_elt = d;
 }
 
 static int allocs = 0;
@@ -88,8 +116,7 @@ empty_parse_state (void)
   parse_state *res = xcalloc (1, sizeof *res);
   res->state_items.contents
     = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
-  res->derivs.contents
-    = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+  res->derivs.contents = derivation_list_new ();
   ++allocs;
   return res;
 }
@@ -98,8 +125,8 @@ parse_state *
 new_parse_state (const state_item *si)
 {
   parse_state *res = empty_parse_state ();
-  ps_chunk_append (&res->state_items, si);
-  ps_chunk_append (&res->derivs, derivation_dot ());
+  ps_si_append (res, si);
+  ps_derivs_append (res, derivation_dot ());
   return res;
 }
 
@@ -110,8 +137,7 @@ copy_parse_state (bool prepend, parse_state *parent)
   memcpy (res, parent, sizeof *res);
   res->state_items.contents
     = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
-  res->derivs.contents
-    = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+  res->derivs.contents = derivation_list_new ();
   res->parent = parent;
   res->prepend = prepend;
   res->reference_count = 0;
@@ -127,10 +153,10 @@ parse_state_derivation_completed (const parse_state *ps)
   return ps->derivs.total_size == 1;
 }
 
-const derivation *
+derivation *
 parse_state_derivation (const parse_state *ps)
 {
-  return ps->derivs.head_elt;
+  return (derivation *)ps->derivs.head_elt;
 }
 
 const state_item *
@@ -169,12 +195,6 @@ parse_state_free_contents_early (parse_state *ps)
   ps->free_contents_early = true;
 }
 
-void
-parse_state_retain_deriv (parse_state *ps)
-{
-  ps->derivs.contents = NULL;
-}
-
 void
 free_parse_state (parse_state *original_ps)
 {
@@ -191,7 +211,7 @@ free_parse_state (parse_state *original_ps)
           if (ps->state_items.contents)
             gl_list_free (ps->state_items.contents);
           if (ps->derivs.contents)
-            gl_list_free (ps->derivs.contents);
+            derivation_list_free (ps->derivs.contents);
         }
       if (ps->reference_count <= 0)
         {
@@ -205,7 +225,7 @@ free_parse_state (parse_state *original_ps)
 size_t
 parse_state_hasher (const parse_state *ps, size_t max)
 {
-  const ps_chunk *sis = &ps->state_items;
+  const struct si_chunk *sis = &ps->state_items;
   return ((state_item *) sis->head_elt - state_items +
           (state_item *) sis->tail_elt - state_items + sis->total_size) % max;
 }
@@ -213,8 +233,8 @@ parse_state_hasher (const parse_state *ps, size_t max)
 bool
 parse_state_comparator (const parse_state *ps1, const parse_state *ps2)
 {
-  const ps_chunk *sis1 = &ps1->state_items;
-  const ps_chunk *sis2 = &ps2->state_items;
+  const struct si_chunk *sis1 = &ps1->state_items;
+  const struct si_chunk *sis2 = &ps2->state_items;
   return sis1->head_elt == sis2->head_elt
     && sis1->tail_elt == sis2->tail_elt
     && sis1->total_size == sis2->total_size;
@@ -245,10 +265,12 @@ parse_state_completed_steps (const parse_state *ps, int *shifts, int *production
   *shifts = root_ps->state_items.total_size - count;
 }
 
+typedef void (*chunk_append_fn) (gl_list_t, void *);
 // takes an array of n gl_lists and flattens them into two list
 // based off of the index split
 static void
-list_flatten_and_split (gl_list_t *list, gl_list_t *rets, int split, int n)
+list_flatten_and_split (gl_list_t *list, gl_list_t *rets, int split, int n,
+                        chunk_append_fn append_fn)
 {
   int ret_index = 0;
   int ret_array = 0;
@@ -267,7 +289,7 @@ list_flatten_and_split (gl_list_t *list, gl_list_t *rets, int split, int n)
               if (ret_index++ == split)
                 ++ret_array;
               if (rets[ret_array])
-                gl_list_add_last (rets[ret_array], si);
+                append_fn (rets[ret_array], si);
             }
         }
     }
@@ -284,7 +306,7 @@ parse_state_list_new (void)
 // 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.
-static gl_list_t
+static derivation_list
 parser_pop (parse_state *ps, int deriv_index,
             int si_index, parse_state *ret)
 {
@@ -305,13 +327,14 @@ parser_pop (parse_state *ps, int deriv_index,
           gl_list_add_first (chunks[3], pn->derivs.contents);
         }
     }
-  gl_list_t popped_derivs =
-    gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
+  gl_list_t popped_derivs = derivation_list_new ();
   gl_list_t ret_chunks[4] = { ret->state_items.contents, NULL,
     ret->derivs.contents, popped_derivs
   };
-  list_flatten_and_split (chunks, ret_chunks, si_index, 2);
-  list_flatten_and_split (chunks + 2, ret_chunks + 2, deriv_index, 2);
+  list_flatten_and_split (chunks, ret_chunks, si_index, 2,
+                          (chunk_append_fn)gl_list_add_last);
+  list_flatten_and_split (chunks + 2, ret_chunks + 2, deriv_index, 2,
+                          (chunk_append_fn)derivation_list_append);
   size_t s_size = gl_list_size (ret->state_items.contents);
   ret->state_items.total_size = s_size;
   if (s_size > 0)
@@ -346,18 +369,19 @@ parser_pop (parse_state *ps, int deriv_index,
 
 void
 parse_state_lists (parse_state *ps, gl_list_t *sitems,
-                   gl_list_t *derivs)
+                   derivation_list *derivs)
 {
   parse_state *temp = empty_parse_state ();
   size_t si_size = ps->state_items.total_size;
   size_t deriv_size = ps->derivs.total_size;
-  parser_pop (ps, si_size, deriv_size, temp);
+  derivation_list dl = parser_pop (ps, si_size, deriv_size, temp);
   *sitems = temp->state_items.contents;
   *derivs = temp->derivs.contents;
   // prevent the return lists from being freed
   temp->state_items.contents = NULL;
   temp->derivs.contents = NULL;
   free_parse_state (temp);
+  derivation_list_free (dl);
 }
 
 /**
@@ -379,8 +403,8 @@ nullable_closure (parse_state *ps, state_item *si, gl_list_t state_list)
 
       state_item *nsi = state_items + sin;
       current_ps = copy_parse_state (false, current_ps);
-      ps_chunk_append (&current_ps->state_items, nsi);
-      ps_chunk_append (&current_ps->derivs, derivation_new (sp, NULL));
+      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);
     }
@@ -401,8 +425,8 @@ simulate_transition (parse_state *ps)
   if (si_next < 0)
     return result;
   parse_state *next_ps = copy_parse_state (false, ps);
-  ps_chunk_append (&next_ps->state_items, state_items + si_next);
-  ps_chunk_append (&next_ps->derivs, derivation_new (sym, NULL));
+  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);
 
@@ -448,7 +472,7 @@ simulate_production (parse_state *ps, symbol_number compat_sym)
           if (!compatible (*itm1, compat_sym) || !production_allowed (si, next))
             continue;
           parse_state *next_ps = copy_parse_state (false, ps);
-          ps_chunk_append (&next_ps->state_items, next);
+          ps_si_append (next_ps, next);
           parse_state_retain (next_ps);
           gl_list_add_last (result, next_ps);
           if (next_ps->depth >= 0)
@@ -472,9 +496,9 @@ simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set)
   if (ps->depth >= 0)
     d_size--;                   // account for dot
   parse_state *new_root = empty_parse_state ();
-  gl_list_t popped_derivs = parser_pop (ps, d_size - rule_len,
-                                        s_size - rule_len - 1,
-                                        new_root);
+  derivation_list popped_derivs =
+    parser_pop (ps, d_size - rule_len,
+                s_size - rule_len - 1, new_root);
 
   // update derivation
   state_item *si = (state_item *) ps->state_items.tail_elt;
@@ -482,13 +506,12 @@ simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set)
   symbol_number lhs = r->lhs->number;
   derivation *deriv = derivation_new (lhs, popped_derivs);
   --new_root->depth;
-  ps_chunk_append (&new_root->derivs, deriv);
+  ps_derivs_append (new_root, deriv);
 
   if (s_size != rule_len + 1)
     {
       state_item *tail = (state_item *) new_root->state_items.tail_elt;
-      ps_chunk_append (&new_root->state_items,
-                       state_items + si_trans[tail - state_items]);
+      ps_si_append (new_root, state_items + si_trans[tail - state_items]);
       parse_state_retain (new_root);
       gl_list_add_last (result, new_root);
     }
@@ -504,13 +527,13 @@ simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set)
         {
           //Prepend the result from the reverse production
           parse_state *copy = copy_parse_state (true, new_root);
-          ps_chunk_prepend (&copy->state_items, psis);
+          ps_si_prepend (copy, psis);
 
           // Append the left hand side to the end of the parser state
           copy = copy_parse_state (false, copy);
-          ps_chunk *sis = &copy->state_items;
+          struct si_chunk *sis = &copy->state_items;
           const state_item *tail = sis->tail_elt;
-          ps_chunk_append (sis, state_items + si_trans[tail - state_items]);
+          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);
@@ -534,9 +557,9 @@ parser_prepend (parse_state *ps)
   {
     parse_state *copy = copy_parse_state (true, ps);
     parse_state_retain (copy);
-    ps_chunk_prepend (&copy->state_items, state_items + sin);
+    ps_si_prepend (copy, state_items + sin);
     if (SI_TRANSITION (head))
-      ps_chunk_prepend (&copy->derivs, derivation_new (prepend_sym, NULL));
+      ps_derivs_prepend (copy, derivation_new_leaf (prepend_sym));
     gl_list_add_last (result, copy);
   }
   return result;
diff --git a/src/parse-simulation.h b/src/parse-simulation.h
index 1bc7b54d..a912f012 100644
--- a/src/parse-simulation.h
+++ b/src/parse-simulation.h
@@ -86,7 +86,6 @@ void parse_state_retain (parse_state *ps);
  * when its reference count reaches 1. This is used to
  * free memory while the parse state is in a hash set. */
 void parse_state_free_contents_early (parse_state *ps);
-void parse_state_retain_deriv (parse_state *ps);
 void free_parse_state (parse_state *ps);
 
 /* counts the amount of shift and production steps in this parse state */
@@ -94,7 +93,7 @@ void parse_state_completed_steps (const parse_state *ps, int *shifts, int *produ
 
 /* parse state getters */
 bool parse_state_derivation_completed (const parse_state *ps);
-const derivation *parse_state_derivation (const parse_state *ps);
+derivation *parse_state_derivation (const parse_state *ps);
 const state_item *parse_state_head (const parse_state *ps);
 const state_item *parse_state_tail (const parse_state *ps);
 int parse_state_length (const parse_state *ps);
@@ -102,7 +101,7 @@ 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,
-                        gl_list_t *derivs);
+                        derivation_list *derivs);
 
 /* various functions that return a list of states based off of
  * whatever operation is simulated. After whatever operation, every possible
-- 
2.20.1 (Apple Git-117)