Move the trait `Forest` to the crate "forest".

The purpose of this change is to share this trait with other crates,
such as the forth-coming "semiring" crate that will be responsible for
handling some simple semiring operations as well as the querying, in
my plans.

13 files changed, 304 insertions, 255 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 399eafb..ef6f2da 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -27,6 +27,7 @@ crate-type = ["cdylib"]
 chain = { path = "./chain" }
 grammar = { path = "./grammar" }
 graph = { path = "./graph" }
+forest = { path = "./forest" }
 
 [features]
 default = []
diff --git a/chain/Cargo.toml b/chain/Cargo.toml
index e5499ee..6a1b089 100644
--- a/chain/Cargo.toml
+++ b/chain/Cargo.toml
@@ -14,6 +14,7 @@ nfa = { path = "../nfa" }
 graph = { path = "../graph" }
 graph_macro = { path = "../graph_macro" }
 grammar = { path = "../grammar" }
+forest = { path = "../forest" }
 
 [dev-dependencies]
 grammar = { path = "../grammar", features = ["test-helper"] }
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index fa0cc3b..df61b6f 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -18,7 +18,8 @@ use std::{
     iter::Copied,
 };
 
-use crate::item::{default::DefaultForest, ForestLabel};
+use crate::item::default::DefaultForest;
+use forest::ForestLabel;
 
 /// A virtual node represents the derivative of a non-terminal symbol
 /// `s` with respect to a terminal symbol `t`.
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 11f0c93..85e3c8f 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -8,9 +8,11 @@
 use super::*;
 use crate::atom::{Atom, DefaultAtom};
 use crate::item::{
-    default::DefaultForest, generate_fragment, genins::index_out_of_bounds_conversion, Forest,
-    ForestLabel, ForestLabelError,
+    default::DefaultForest, generate_fragment, genins::index_out_of_bounds_conversion,
 };
+
+use forest::{Forest, ForestLabel, ForestLabelError};
+
 use grammar::{GrammarLabel, GrammarLabelType, START_NONTERMINAL, TNT};
 #[allow(unused_imports)]
 use graph::{
diff --git a/chain/src/item/archive.txt b/chain/src/item/archive.txt
new file mode 100644
index 0000000..fab3814
--- /dev/null
+++ b/chain/src/item/archive.txt
@@ -0,0 +1,207 @@
+// /// An internal type that indicates the status of a node as either a
+// /// packed, cloned, or plain node.
+// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
+// pub enum ForestLabelType {
+//     /// A packed node
+//     Packed,
+//     /// A plain node
+//     #[default]
+//     Plain,
+//     /// A cloned node
+//     Cloned(usize),
+// }
+// 
+// impl std::fmt::Display for ForestLabelType {
+//     fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+//         match self {
+//             Self::Packed => write!(f, "packed"),
+//             Self::Plain => write!(f, "plain"),
+//             Self::Cloned(index) => write!(f, "clone({index})"),
+//         }
+//     }
+// }
+// 
+// /// A type that encodes the properties demanded by a forest.
+// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+// pub struct ForestLabel<T: GraphLabel> {
+//     label: T,
+//     status: ForestLabelType,
+// }
+// 
+// impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> {
+//     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+//         if !matches!(self.status, ForestLabelType::Plain) {
+//             write!(f, "{}, {}", self.label, self.status)
+//         } else {
+//             write!(f, "{}", self.label)
+//         }
+//     }
+// }
+// 
+// /// The type of erros for converting forest labels.
+// #[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
+// pub enum ForestLabelError {
+//     /// Try to pack a cloned node.
+//     PackClone,
+//     /// Try to clone a packed node.
+//     ClonePack,
+// }
+// 
+// impl std::fmt::Display for ForestLabelError {
+//     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+//         match self {
+//             Self::PackClone => write!(f, "cannot pack a cloned node"),
+//             Self::ClonePack => write!(f, "cannot clone a packed node"),
+//         }
+//     }
+// }
+// 
+// impl std::error::Error for ForestLabelError {}
+// 
+// impl<T: GraphLabel> ForestLabel<T> {
+//     /// Construct a new label with the inner `label` and `status`.
+//     pub fn new(label: T, status: ForestLabelType) -> Self {
+//         Self { label, status }
+//     }
+// 
+//     /// Retrieve the label.
+//     pub fn label(&self) -> T {
+//         self.label
+//     }
+// 
+//     /// Return true if and only if this node is packed.
+//     pub fn is_packed(&self) -> bool {
+//         self.status == ForestLabelType::Packed
+//     }
+// 
+//     /// Retrieve the optional clone index.
+//     pub fn clone_index(&self) -> Option<usize> {
+//         match self.status {
+//             ForestLabelType::Cloned(index) => Some(index),
+//             _ => None,
+//         }
+//     }
+// 
+//     /// Return true if and only if this node is a plain node.
+//     pub fn is_plain(&self) -> bool {
+//         self.status == ForestLabelType::Plain
+//     }
+// 
+//     /// Try to clone a node.
+//     pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
+//     where
+//         F: LabelGraph<ForestLabel<T>>,
+//     {
+//         if self.is_packed() {
+//             dbg!();
+//             Err(ForestLabelError::ClonePack)
+//         } else {
+//             let clone_index = if let Some(old_index) = self.clone_index() {
+//                 let mut new_index: usize = old_index + 1;
+// 
+//                 let mut new_label = Self {
+//                     status: ForestLabelType::Cloned(new_index),
+//                     ..self
+//                 };
+// 
+//                 while forest.query_label(new_label).is_some() {
+//                     new_index += 1;
+//                     new_label = Self {
+//                         status: ForestLabelType::Cloned(new_index),
+//                         ..self
+//                     };
+//                 }
+// 
+//                 new_index
+//             } else {
+//                 0
+//             };
+// 
+//             Ok(Self {
+//                 status: ForestLabelType::Cloned(clone_index),
+//                 ..self
+//             })
+//         }
+//     }
+// 
+//     /// Try to pack a node.
+//     pub fn pack(self) -> Result<Self, ForestLabelError> {
+//         if self.clone_index().is_some() {
+//             Err(ForestLabelError::PackClone)
+//         } else {
+//             let new_label = Self {
+//                 status: ForestLabelType::Packed,
+//                 ..self
+//             };
+// 
+//             Ok(new_label)
+//         }
+//     }
+// }
+// 
+// impl<T: GraphLabel> From<T> for ForestLabel<T> {
+//     fn from(label: T) -> Self {
+//         let status = ForestLabelType::default();
+//         Self { label, status }
+//     }
+// }
+// 
+// // REVIEW: Should we move this trait (and only this trait) to a
+// // separate crate, or is it enough to keep it here?
+// 
+// /// The expected behaviours of an item derivation forest.
+// ///
+// /// Note that it requires only a subset of the functionalities of
+// /// labelled graphs.
+// pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
+//     /// The type of errors for operations on the forest.
+//     type Error: std::error::Error + From<GError> + From<ForestLabelError>;
+// 
+//     /// Return the root of the forest.
+//     ///
+//     /// A forest without a root is regarded as empty.
+//     fn root(&self) -> Option<usize>;
+// 
+//     /// Construct a forest consisting of one leaf node with the given
+//     /// label.
+//     fn new_leaf(label: T) -> Self;
+// 
+//     /// Transform the label at the given node.
+//     fn transform_label(
+//         &mut self,
+//         node_id: usize,
+//         transform: impl FnOnce(T) -> T,
+//     ) -> Result<(), Self::Error>;
+// 
+//     /// Detect if the fragment is a prefix of the sub-forest rooted at
+//     /// `node_id`.
+//     fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
+//     where
+//         F: Borrow<Self>;
+// 
+//     /// Extend the forest by adjoining another forest at a given node.
+//     fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
+//     where
+//         F: Borrow<Self>;
+// 
+//     /// Clone a node by making a new node and making all the nodes
+//     /// that previously pointed to the old node now point to the new
+//     /// node, and the new node points to the old node.  Return the
+//     /// index of the new node.  However, if, and only if,
+//     /// `no_new_clone` is `true`, do not make a new clone; instead
+//     /// return the clone index that would be used if a new clone was
+//     /// made.
+//     ///
+//     /// Also, `preserved_edges_num` many edges out of the old node
+//     /// will be copied to be the children of the new node.
+//     ///
+//     /// The labels of the representing node and of the cloned node
+//     /// will be handled automatically.
+//     fn clone_node(
+//         &mut self,
+//         node_id: usize,
+//         preserved_edges_num: usize,
+//         no_new_clone: bool,
+//     ) -> Result<usize, Self::Error>;
+// }
+// 
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index de43f37..01e463e 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -200,7 +200,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
 
         let transformed_label = transform(vertex_label.label());
 
-        let transformed_label = ForestLabel::new(transformed_label, vertex_label.status);
+        let transformed_label = ForestLabel::new(transformed_label, vertex_label.status());
 
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
@@ -1239,7 +1239,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
                 label_label.set_start(pos);
 
-                let new_label = ForestLabel::new(label_label, label.status);
+                let new_label = ForestLabel::new(label_label, label.status());
 
                 builder.set_label(node, new_label)?;
             }
@@ -1306,7 +1306,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 label_label.set_end(pos + 1);
             }
 
-            let new_label = ForestLabel::new(label_label, label.status);
+            let new_label = ForestLabel::new(label_label, label.status());
 
             builder.set_label(node, new_label)?;
         }
@@ -1339,7 +1339,7 @@ pub fn print_labels(
         let label = forest.vertex_label(node)?;
 
         if let Some(label) = label {
-            let label = label.label.label();
+            let label = label.label().label();
 
             match label {
                 GrammarLabelType::TNT(tnt) => {
diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs
index ed41c61..54ea168 100644
--- a/chain/src/item/mod.rs
+++ b/chain/src/item/mod.rs
@@ -9,6 +9,8 @@ use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph
 
 use std::borrow::Borrow;
 
+use forest::{Forest, ForestLabel, ForestLabelError, ForestLabelType};
+
 /// A parent or a virtual segment.
 ///
 /// # Parent
@@ -86,213 +88,6 @@ impl PaVi {
     }
 }
 
-/// An internal type that indicates the status of a node as either a
-/// packed, cloned, or plain node.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
-pub enum ForestLabelType {
-    /// A packed node
-    Packed,
-    /// A plain node
-    #[default]
-    Plain,
-    /// A cloned node
-    Cloned(usize),
-}
-
-impl std::fmt::Display for ForestLabelType {
-    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
-        match self {
-            Self::Packed => write!(f, "packed"),
-            Self::Plain => write!(f, "plain"),
-            Self::Cloned(index) => write!(f, "clone({index})"),
-        }
-    }
-}
-
-/// A type that encodes the properties demanded by a forest.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
-pub struct ForestLabel<T: GraphLabel> {
-    label: T,
-    status: ForestLabelType,
-}
-
-impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        if !matches!(self.status, ForestLabelType::Plain) {
-            write!(f, "{}, {}", self.label, self.status)
-        } else {
-            write!(f, "{}", self.label)
-        }
-    }
-}
-
-/// The type of erros for converting forest labels.
-#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
-pub enum ForestLabelError {
-    /// Try to pack a cloned node.
-    PackClone,
-    /// Try to clone a packed node.
-    ClonePack,
-}
-
-impl std::fmt::Display for ForestLabelError {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        match self {
-            Self::PackClone => write!(f, "cannot pack a cloned node"),
-            Self::ClonePack => write!(f, "cannot clone a packed node"),
-        }
-    }
-}
-
-impl std::error::Error for ForestLabelError {}
-
-impl<T: GraphLabel> ForestLabel<T> {
-    /// Construct a new label with the inner `label` and `status`.
-    pub fn new(label: T, status: ForestLabelType) -> Self {
-        Self { label, status }
-    }
-
-    /// Retrieve the label.
-    pub fn label(&self) -> T {
-        self.label
-    }
-
-    /// Return true if and only if this node is packed.
-    pub fn is_packed(&self) -> bool {
-        self.status == ForestLabelType::Packed
-    }
-
-    /// Retrieve the optional clone index.
-    pub fn clone_index(&self) -> Option<usize> {
-        match self.status {
-            ForestLabelType::Cloned(index) => Some(index),
-            _ => None,
-        }
-    }
-
-    /// Return true if and only if this node is a plain node.
-    pub fn is_plain(&self) -> bool {
-        self.status == ForestLabelType::Plain
-    }
-
-    /// Try to clone a node.
-    pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
-    where
-        F: LabelGraph<ForestLabel<T>>,
-    {
-        if self.is_packed() {
-            dbg!();
-            Err(ForestLabelError::ClonePack)
-        } else {
-            let clone_index = if let Some(old_index) = self.clone_index() {
-                let mut new_index: usize = old_index + 1;
-
-                let mut new_label = Self {
-                    status: ForestLabelType::Cloned(new_index),
-                    ..self
-                };
-
-                while forest.query_label(new_label).is_some() {
-                    new_index += 1;
-                    new_label = Self {
-                        status: ForestLabelType::Cloned(new_index),
-                        ..self
-                    };
-                }
-
-                new_index
-            } else {
-                0
-            };
-
-            Ok(Self {
-                status: ForestLabelType::Cloned(clone_index),
-                ..self
-            })
-        }
-    }
-
-    /// Try to pack a node.
-    pub fn pack(self) -> Result<Self, ForestLabelError> {
-        if self.clone_index().is_some() {
-            Err(ForestLabelError::PackClone)
-        } else {
-            let new_label = Self {
-                status: ForestLabelType::Packed,
-                ..self
-            };
-
-            Ok(new_label)
-        }
-    }
-}
-
-impl<T: GraphLabel> From<T> for ForestLabel<T> {
-    fn from(label: T) -> Self {
-        let status = ForestLabelType::default();
-        Self { label, status }
-    }
-}
-
-// REVIEW: Should we move this trait (and only this trait) to a
-// separate crate, or is it enough to keep it here?
-
-/// The expected behaviours of an item derivation forest.
-///
-/// Note that it requires only a subset of the functionalities of
-/// labelled graphs.
-pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
-    /// The type of errors for operations on the forest.
-    type Error: std::error::Error + From<GError> + From<ForestLabelError>;
-
-    /// Return the root of the forest.
-    ///
-    /// A forest without a root is regarded as empty.
-    fn root(&self) -> Option<usize>;
-
-    /// Construct a forest consisting of one leaf node with the given
-    /// label.
-    fn new_leaf(label: T) -> Self;
-
-    /// Transform the label at the given node.
-    fn transform_label(
-        &mut self,
-        node_id: usize,
-        transform: impl FnOnce(T) -> T,
-    ) -> Result<(), Self::Error>;
-
-    /// Detect if the fragment is a prefix of the sub-forest rooted at
-    /// `node_id`.
-    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
-    where
-        F: Borrow<Self>;
-
-    /// Extend the forest by adjoining another forest at a given node.
-    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
-    where
-        F: Borrow<Self>;
-
-    /// Clone a node by making a new node and making all the nodes
-    /// that previously pointed to the old node now point to the new
-    /// node, and the new node points to the old node.  Return the
-    /// index of the new node.  However, if, and only if,
-    /// `no_new_clone` is `true`, do not make a new clone; instead
-    /// return the clone index that would be used if a new clone was
-    /// made.
-    ///
-    /// Also, `preserved_edges_num` many edges out of the old node
-    /// will be copied to be the children of the new node.
-    ///
-    /// The labels of the representing node and of the cloned node
-    /// will be handled automatically.
-    fn clone_node(
-        &mut self,
-        node_id: usize,
-        preserved_edges_num: usize,
-        no_new_clone: bool,
-    ) -> Result<usize, Self::Error>;
-}
-
 pub mod default;
 
 pub mod genins;
diff --git a/chain/src/lib.rs b/chain/src/lib.rs
index f16ebb2..10143dd 100644
--- a/chain/src/lib.rs
+++ b/chain/src/lib.rs
@@ -321,7 +321,7 @@ pub trait Chain: LabelExtGraph<Edge> {
     // purpose, but I have not figured out yet wha the correct trait
     // should be.
     /// The type of output item that will be produced by this machine.
-    type Item: item::Forest<grammar::GrammarLabel>;
+    type Item: forest::Forest<grammar::GrammarLabel>;
 
     /// Signal to the parser that the end of the input is reached, so
     /// that the parser knows to generate suitable forests.
diff --git a/forest/Cargo.toml b/forest/Cargo.toml
index 8cc445b..5702265 100644
--- a/forest/Cargo.toml
+++ b/forest/Cargo.toml
@@ -13,5 +13,6 @@ test-print-viz = []
 
 [dependencies]
 graph = { path = "../graph" }
+grammar = { path = "../grammar" }
 
 # This should be integrated in the package, but it is not yet done.
\ No newline at end of file
diff --git a/forest/src/default.rs b/forest/src/archive_default.txt
index b96439f..5572ecc 100644
--- a/forest/src/default.rs
+++ b/forest/src/archive_default.txt
@@ -1,3 +1,5 @@
+// DEPRECATED: This file is deprecated.
+
 //! This file provides a default implementation for the
 //! [`Forest`][crate::Forest] trait.
 
diff --git a/src/bytes.rs b/forest/src/bytes.rs
index f764077..951abad 100644
--- a/src/bytes.rs
+++ b/forest/src/bytes.rs
@@ -76,11 +76,12 @@
 //!
 //! To sum up, each label occupies 34 bytes.
 
-use chain::item::{default::DefaultForest, ForestLabel};
+use super::Forest;
 use grammar::{GrammarLabel, GrammarLabelType, TNT};
-use graph::{Graph, LabelGraph};
 
-pub(super) fn forest_to_bytes(forest: &DefaultForest<ForestLabel<GrammarLabel>>) -> Vec<u8> {
+/// Convert any type that implements the `Forest` trait into a
+/// sequence of bytes.
+pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> {
     // First calculate the total number of bytes.
     let nodes_len = forest.nodes_len();
 
@@ -127,7 +128,7 @@ pub(super) fn forest_to_bytes(forest: &DefaultForest<ForestLabel<GrammarLabel>>)
     bytes.extend(forest.nodes().flat_map(|node| {
         forest
             .children_of(node)
-            .unwrap_or_default()
+            .unwrap()
             .flat_map(|child| child.to_be_bytes())
     }));
 
diff --git a/forest/src/lib.rs b/forest/src/lib.rs
index 0b1092f..a888fae 100644
--- a/forest/src/lib.rs
+++ b/forest/src/lib.rs
@@ -1,26 +1,27 @@
 #![warn(missing_docs)]
-//! This file defines the expected behaviours of forests, and provides
-//! a default implementation for forests.
+//! This file defines the expected behaviours of forests.
 //!
-//! The default forest actually implements the so-called shared packed
-//! parse forest, or SPPF.  It packs sub-trees with the same parents
-//! under the same branch, and lets nodes from different branches
-//! share the same children, and hence the name.
+//! The forests are the basis of the `semiring` crate.
 
 use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph};
 
+use std::borrow::Borrow;
+
 /// An internal type that indicates the status of a node as either a
 /// packed, cloned, or plain node.
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
-enum ForestLabelType {
+pub enum ForestLabelType {
+    /// A packed node
     Packed,
+    /// A plain node
     #[default]
     Plain,
+    /// A cloned node
     Cloned(usize),
 }
 
-impl core::fmt::Display for ForestLabelType {
-    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+impl std::fmt::Display for ForestLabelType {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Self::Packed => write!(f, "packed"),
             Self::Plain => write!(f, "plain"),
@@ -36,14 +37,17 @@ pub struct ForestLabel<T: GraphLabel> {
     status: ForestLabelType,
 }
 
-impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> {
-    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
-        writeln!(f, "label: {}, status: {}", self.label, self.status)
+impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        if !matches!(self.status, ForestLabelType::Plain) {
+            write!(f, "{}, {}", self.label, self.status)
+        } else {
+            write!(f, "{}", self.label)
+        }
     }
 }
 
 /// The type of erros for converting forest labels.
-#[non_exhaustive]
 #[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
 pub enum ForestLabelError {
     /// Try to pack a cloned node.
@@ -52,8 +56,8 @@ pub enum ForestLabelError {
     ClonePack,
 }
 
-impl core::fmt::Display for ForestLabelError {
-    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+impl std::fmt::Display for ForestLabelError {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Self::PackClone => write!(f, "cannot pack a cloned node"),
             Self::ClonePack => write!(f, "cannot clone a packed node"),
@@ -64,33 +68,50 @@ impl core::fmt::Display for ForestLabelError {
 impl std::error::Error for ForestLabelError {}
 
 impl<T: GraphLabel> ForestLabel<T> {
+    /// Construct a new label with the inner `label` and `status`.
+    pub fn new(label: T, status: ForestLabelType) -> Self {
+        Self { label, status }
+    }
+
     /// Retrieve the label.
     pub fn label(&self) -> T {
         self.label
     }
 
+    /// Retrieve the status.
+    pub fn status(&self) -> ForestLabelType {
+        self.status
+    }
+
     /// Return true if and only if this node is packed.
     pub fn is_packed(&self) -> bool {
-        matches!(self.status, ForestLabelType::Packed)
+        self.status == ForestLabelType::Packed
     }
 
     /// Retrieve the optional clone index.
-    pub fn is_cloned(&self) -> Option<usize> {
-        match self.status {
-            ForestLabelType::Cloned(index) => Some(index),
-            _ => None,
+    pub fn clone_index(&self) -> Option<usize> {
+        if let ForestLabelType::Cloned(index) = self.status {
+            Some(index)
+        } else {
+            None
         }
     }
 
+    /// Return true if and only if this node is a plain node.
+    pub fn is_plain(&self) -> bool {
+        self.status == ForestLabelType::Plain
+    }
+
     /// Try to clone a node.
     pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
     where
-        F: Forest<T>,
+        F: LabelGraph<ForestLabel<T>>,
     {
         if self.is_packed() {
+            dbg!();
             Err(ForestLabelError::ClonePack)
         } else {
-            let clone_index = if let Some(old_index) = self.is_cloned() {
+            let clone_index = if let Some(old_index) = self.clone_index() {
                 let mut new_index: usize = old_index + 1;
 
                 let mut new_label = Self {
@@ -120,7 +141,7 @@ impl<T: GraphLabel> ForestLabel<T> {
 
     /// Try to pack a node.
     pub fn pack(self) -> Result<Self, ForestLabelError> {
-        if self.is_cloned().is_some() {
+        if self.clone_index().is_some() {
             Err(ForestLabelError::PackClone)
         } else {
             let new_label = Self {
@@ -140,7 +161,7 @@ impl<T: GraphLabel> From<T> for ForestLabel<T> {
     }
 }
 
-/// The expected behaviours of a forest.
+/// The expected behaviours of an item derivation forest.
 ///
 /// Note that it requires only a subset of the functionalities of
 /// labelled graphs.
@@ -157,28 +178,45 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
     /// label.
     fn new_leaf(label: T) -> Self;
 
+    /// Transform the label at the given node.
+    fn transform_label(
+        &mut self,
+        node_id: usize,
+        transform: impl FnOnce(T) -> T,
+    ) -> Result<(), Self::Error>;
+
     /// Detect if the fragment is a prefix of the sub-forest rooted at
     /// `node_id`.
     fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
     where
-        F: AsRef<Self>;
+        F: Borrow<Self>;
 
     /// Extend the forest by adjoining another forest at a given node.
     fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
     where
-        F: AsRef<Self>;
+        F: Borrow<Self>;
 
     /// Clone a node by making a new node and making all the nodes
     /// that previously pointed to the old node now point to the new
     /// node, and the new node points to the old node.  Return the
-    /// index of the new node.  In addition, if the old node had
-    /// already been cloned, just return the index of its
-    /// representitave.
+    /// index of the new node.  However, if, and only if,
+    /// `no_new_clone` is `true`, do not make a new clone; instead
+    /// return the clone index that would be used if a new clone was
+    /// made.
+    ///
+    /// Also, `preserved_edges_num` many edges out of the old node
+    /// will be copied to be the children of the new node.
     ///
     /// The labels of the representing node and of the cloned node
     /// will be handled automatically.
-    fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>;
+    fn clone_node(
+        &mut self,
+        node_id: usize,
+        preserved_edges_num: usize,
+        no_new_clone: bool,
+    ) -> Result<usize, Self::Error>;
 }
 
-pub mod default;
-pub use default::Error;
+pub mod bytes;
+
+pub use bytes::forest_to_bytes;
diff --git a/src/lib.rs b/src/lib.rs
index 3483847..69be41f 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -9,10 +9,12 @@ use chain::{atom::DefaultAtom, default::DefaultChain, Chain};
 use grammar::Grammar;
 
 // For printing forests
-use chain::item::{default::DefaultForest, ForestLabel, ForestLabelType};
+use chain::item::default::DefaultForest;
 use grammar::{GrammarLabel, TNT};
 use graph::LabelGraph;
 
+use forest::{ForestLabel, ForestLabelType};
+
 /// This struct is the representation of a parser.
 ///
 /// When the user constructs a parser, an instance of this struct will
@@ -485,7 +487,7 @@ extern "C" fn parser_parse(
                     Ok(forest) => {
                         Box::leak(parser_box);
 
-                        let mut bytes = bytes::forest_to_bytes(&forest);
+                        let mut bytes = forest::forest_to_bytes(&forest);
 
                         let bytes_len = bytes.len().to_be_bytes().to_vec();
 
@@ -835,5 +837,3 @@ extern "C" fn print_forest_node(forest: *mut CForest, node: *mut std::os::raw::c
 
     println!("node {node} has label {label}");
 }
-
-pub mod bytes;