3 files changed, 69 insertions, 15 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs
index 456413b..5e438d4 100644
--- a/forest/src/default.rs
+++ b/forest/src/default.rs
@@ -61,14 +61,6 @@ impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Graph for DefaultForest<NodeL
     }
 }
 
-impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> ExtGraph
-    for DefaultForest<NodeLabel, EdgeLabel>
-{
-    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, GraphError> {
-        self.graph.extend(edges)
-    }
-}
-
 #[derive(Debug)]
 pub struct LabelIter<'a> {
     set_iter: Iter<'a, usize>,
@@ -88,11 +80,7 @@ impl<'a> Iterator for LabelIter<'a> {
 
 impl<'a> ExactSizeIterator for LabelIter<'a> {
     fn len(&self) -> usize {
-        let (lower, upper) = self.size_hint();
-        // Note: This assertion is overly defensive, but it checks the
-        // invariant guaranteed by the trait.
-        debug_assert!(upper == Some(lower));
-        lower
+        self.set_iter.len()
     }
 }
 
diff --git a/forest/src/design.org b/forest/src/design.org
new file mode 100644
index 0000000..771ca4b
--- /dev/null
+++ b/forest/src/design.org
@@ -0,0 +1,66 @@
+#+TITLE: Format of a binarised shared packed parse forests
+#+AUTHOR: Durand
+#+DATE: <2023-01-05 Jeu 23:55>
+#+STARTUP: content
+
+* Introduction
+
+I want to design a format for shared packed parse forests.
+They are needed for the chain-rule machine because the graphs need to
+be labelled (indirectly) by fragments of forests so that we can
+correctly and efficiently compute the semi-ring values along the
+chain-rule machine operations.  Moreover, what we are really
+interested is the parse forests, so we will need to deal with this
+topic sooner or later, why not deal with it now?  ;P
+
+* Principles
+
+- The number of children of nodes is bounded by a constant, in theory.
+  So it is only bounded by the computer hardware (and the grammar):
+  this representation is closer to the grammar rules.
+- Labels of nodes are grammar slots, that is positions within the
+  rules.
+- Edges have no labels: they are simply not needed.
+- We need to have two lists of "plugs" that we can plug other forests
+  in.  For this we also need to know if a label is labelled on a node
+  that is a plug.  This implies the use of hashmaps I guess.
+- When there are alternations in the forest, we use a "packed node" to
+  represent this alternation.  Packed nodes are not labelled.  They
+  just serve the role of putting nodes together.
+
+* Some thoughts [1/3]
+
+We do not need to attach forest fragments to nodes of nondeterministic
+finite automata: we just attach to them lists of grammar slots, which
+represent a sequence of "nulling out" nullable non-terminals, until
+the main non-terminal appears as the last element of the list (or even
+a range of slots to be even more efficient).  A normal node would have
+a range with one element.
+
+That is it!  We do not need to worry about the forests now as we would
+know how to combine the forest segments when we are performing the
+chain-rule operations: we know exactly when we are expanding
+non-terminals.
+
+Some caveats:
+
+- [X] Every node in the forest needs to know its parents.  This is
+  needed for "reductions".  That is, after we have parsed the entire
+  expansion for a non-terminal, we need to go back to where that
+  non-terminal was and continue from there.
+- [ ] We need to record the expansions of those "virtual nodes".  That
+  is, the virtual nodes represent atomic languages such as [s]^{(t)}
+  where s is a non-terminal and t is a terminal.  To be more specific,
+  it represents the derivative of the left-linear closure of the
+  non-terminal s with respect to the terminal t.  The left-linear
+  closure of s is the set of all strings (consisting of terminals and
+  non-terminals alike) that are derivable from s alone, without
+  consuming any inputs, by expanding according to the grammar rules.
+  This means that we need to know if which non-terminals were expanded
+  in order to get to a state in [s]^{(t)}.
+- [ ] Each edge in the chain-rule machine needs to be labelled also
+  with a position in the forest.  This perfectly solves the problem of
+  those "plugs"!
+
+
+
diff --git a/forest/src/lib.rs b/forest/src/lib.rs
index 527a78c..3925bd5 100644
--- a/forest/src/lib.rs
+++ b/forest/src/lib.rs
@@ -10,7 +10,7 @@
 //! out-coming and in-coming plugs.  These plugs are used to join
 //! different fragments of forests together.
 
-use graph::{ExtGraph, GraphLabel};
+use graph::{Graph, GraphLabel};
 
 use core::fmt::Display;
 
@@ -60,7 +60,7 @@ pub trait ForestBuilder<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
 ///
 /// Note that it contains a "striped down" version of the labelled
 /// graphs.
-pub trait Forest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel>: ExtGraph {
+pub trait Forest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel>: Graph {
     /// Type of iterator of plug-in nodes.
     type PluginIter<'a>: Iterator<Item = usize> + 'a
     where