renaming core to chain and some other changes

Some changes:

- The core crate is renamed to "chain".

- The crate "viz" is added, which will provide layered graph drawing
  algorithms.

- A function is added to convert from a grammar to the regular
  language of its left-linear closures.

- A function is added to convert from a nondeterministic finite
  automaton to its "null" closure.  A null closure is the same
  automaton with edges added, as if some edges are "null".  Whether an
  edge is null is determined by a function.
  Combined with the previous change, we can convert a grammar to the
  regular language of the null closure of its left-linear closures.

---

Now it remains to test more grammars and add an Atom trait, before
finishing the part about compilations.

1 files changed, 385 insertions, 5 deletions

diff --git a/graph/src/labelled.rs b/graph/src/labelled.rs
index d02e301..d0a02d0 100644
--- a/graph/src/labelled.rs
+++ b/graph/src/labelled.rs
@@ -7,10 +7,9 @@
 //! needs to be implemented efficiently, we store the mappings between
 //! labels and edges in both directions.
 
-#[allow(unused_imports)]
-use super::{Graph, GraphLabel, LabelExtGraph, LabelGraph};
-#[allow(unused_imports)]
-use crate::error::Error;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, Graph, GraphLabel, LabelExtGraph, LabelGraph};
 
 // We use BTreeMap and BTreeSet here as we need to exclude duplicate
 // edge sets, while an ordinary hashmap and hashset do not allow
@@ -21,13 +20,23 @@ use std::collections::{
     BTreeMap as Map, BTreeSet as Set, HashMap as HMap,
 };
 
-#[derive(Debug, Clone, Default)]
+#[derive(Debug, Clone)]
 struct DLNode<T: GraphLabel> {
     by_target: Map<usize, Set<T>>,
     by_label: Map<T, Set<usize>>,
     flat: Vec<(T, usize)>,
 }
 
+impl<T: GraphLabel> Default for DLNode<T> {
+    fn default() -> Self {
+        Self {
+            by_target: Default::default(),
+            by_label: Default::default(),
+            flat: Default::default(),
+        }
+    }
+}
+
 impl<T: GraphLabel> DLNode<T> {
     fn new(
         by_target: Map<usize, Set<T>>,
@@ -66,6 +75,18 @@ impl<T: GraphLabel> DLGraph<T> {
             edges_table: HMap::default(),
         }
     }
+
+    /// Return a builder.
+    #[inline]
+    pub fn builder(self) -> DLGBuilder<T> {
+        DLGBuilder(self)
+    }
+
+    /// Return a builder from a reference.
+    #[inline]
+    pub fn builder_ref(&self) -> DLGBuilder<T> {
+        DLGBuilder(self.clone())
+    }
 }
 
 impl<T: GraphLabel> Default for DLGraph<T> {
@@ -129,6 +150,49 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
             None => Err(Error::IndexOutOfBounds(source, self.nodes.len())),
         }
     }
+
+    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let preamble = "digraph nfa {
+    fontname=\"Helvetica,Arial,sans-serif\"
+    node [fontname=\"Helvetica,Arial,sans-serif\"]
+    edge [fontname=\"Helvetica,Arial,sans-serif\"]
+    rankdir=LR;\n";
+
+        let mut post = String::new();
+
+        use std::fmt::Write as FWrite;
+
+        for (source, target) in self.edges() {
+            for label in self.edge_label(source, target).unwrap() {
+                let _ = writeln!(post, "    {source} -> {target} [label = \"{label}\"]");
+            }
+        }
+
+        post.push_str("}\n");
+
+        let result = format!("{preamble}{post}");
+
+        if std::fs::metadata(filename).is_ok() {
+            std::fs::remove_file(filename)?;
+        }
+
+        let mut file = std::fs::File::options()
+            .write(true)
+            .create(true)
+            .open(filename)?;
+
+        use std::io::Write;
+
+        file.write_all(result.as_bytes())
+    }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let new_graph = builder.build();
+
+        self.nodes = new_graph.nodes;
+        self.edges_table = new_graph.edges_table;
+    }
 }
 
 /// A delegation of iterators.
@@ -261,6 +325,25 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
             None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())),
         }
     }
+
+    fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> {
+        let nodes_len = self.nodes.len();
+
+        match self.nodes.get(node_id) {
+            Some(node) => {
+                if target >= nodes_len {
+                    return Err(Error::IndexOutOfBounds(target, nodes_len));
+                }
+
+                if let Some(labels) = node.by_target.get(&target) {
+                    Ok(labels.contains(label))
+                } else {
+                    Ok(false)
+                }
+            }
+            None => Err(Error::IndexOutOfBounds(node_id, nodes_len)),
+        }
+    }
 }
 
 impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
@@ -315,6 +398,181 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
     }
 }
 
+// Builder for this implementation of graph
+
+/// A builder for labelled adjacency doubly linked graphs.
+#[derive(Debug, Clone)]
+pub struct DLGBuilder<T: GraphLabel>(DLGraph<T>);
+
+impl<T: GraphLabel> Default for DLGBuilder<T> {
+    fn default() -> Self {
+        Self(Default::default())
+    }
+}
+
+impl<T: GraphLabel> Deref for DLGBuilder<T> {
+    type Target = DLGraph<T>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl<T: GraphLabel> DerefMut for DLGBuilder<T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl<T: GraphLabel> Builder for DLGBuilder<T> {
+    type Label = T;
+
+    type Result = DLGraph<T>;
+
+    #[inline]
+    fn with_capacity(size: usize) -> Self {
+        Self(DLGraph {
+            nodes: Vec::with_capacity(size),
+            edges_table: Default::default(),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(DLNode::default());
+        self.nodes.len() - 1
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> {
+        let nodes_len = self.nodes.len();
+
+        let source_node = self
+            .nodes
+            .get_mut(source)
+            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+        if !(0..nodes_len).contains(&target) {
+            return Err(Error::IndexOutOfBounds(target, nodes_len));
+        }
+
+        let new_edge_p = !matches!(
+            source_node
+                .by_target
+                .get(&target)
+                .map(|set| set.contains(&label)),
+            Some(true)
+        );
+
+        if new_edge_p {
+            let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+            source_node
+                .by_target
+                .entry(target)
+                .or_insert_with(Set::default)
+                .insert(label);
+
+            source_node
+                .by_label
+                .entry(label)
+                .or_insert_with(Set::default)
+                .insert(target);
+
+            source_node.flat.push((label, target));
+
+            let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+            // When source_node is in use, we cannot borrow self
+            // mutably again, so we move the following two statements
+            // to after all uses of source_node.
+
+            self.edges_table.remove(&old_children_set);
+
+            self.edges_table.insert(new_children_set, source);
+        }
+
+        Ok(())
+    }
+
+    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
+    where
+        F: Fn(Self::Label) -> bool,
+    {
+        let nodes_len = self.nodes.len();
+
+        let source_node = self
+            .nodes
+            .get_mut(source)
+            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+        if !(0..nodes_len).contains(&target) {
+            return Err(Error::IndexOutOfBounds(target, nodes_len));
+        }
+
+        if let Some(target_labels_set) = source_node.by_target.get(&target) {
+            let mut to_remove = Vec::new();
+
+            for label in target_labels_set.iter() {
+                if predicate(*label) {
+                    to_remove.push(*label);
+                }
+            }
+
+            if !to_remove.is_empty() {
+                let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+                for label in to_remove.iter().copied() {
+                    // This must be "Some", as the outer "if" checks
+                    source_node
+                        .by_target
+                        .get_mut(&target)
+                        .map(|set| set.remove(&label));
+
+                    source_node
+                        .by_label
+                        .get_mut(&label)
+                        .map(|set| set.remove(&target));
+
+                    source_node.flat.retain(|(child_label, child_target)| {
+                        (*child_label, *child_target) != (label, target)
+                    });
+                }
+
+                // If after removal no labels remain for the target,
+                // we remove the edge entirely, to avoid false empty
+                // edges.
+                if source_node.flat.is_empty() {
+                    source_node.by_target.remove(&target);
+
+                    for label in to_remove.iter() {
+                        source_node.by_label.remove(label);
+                    }
+                }
+
+                let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+                // When source_node is in use, we cannot borrow self
+                // mutably again, so we move the following two
+                // statements to after all uses of source_node.
+
+                self.edges_table.remove(&old_children_set);
+
+                self.edges_table.insert(new_children_set, source);
+            }
+        }
+
+        Ok(())
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+}
+
 #[cfg(test)]
 mod label_test {
     use super::*;
@@ -424,3 +682,125 @@ mod label_test {
         Ok(())
     }
 }
+
+// TODO: Test print_viz
+
+#[cfg(test)]
+mod test_dlgraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = DLGBuilder::<usize>::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Link each node to its successor and link the last node with
+        // the first one to form a cycle.
+        for i in 0..5 {
+            builder.add_edge(i, if i < 4 { i + 1 } else { 0 }, i)?;
+        }
+
+        println!("a cycle of five nodes: {builder:?}");
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        println!("a line of five nodes: {builder:?}");
+
+        // build a graph
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = DLGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Errors in add_edge
+
+        println!();
+        println!("Testing errors in add_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.add_edge(0, 5, 0),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.add_edge(10, 5, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.add_edge(10, 50, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        // Errors in remove_edge
+
+        println!();
+        println!("Testing errors in remove_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        println!("No errors for removing a non-existing edge");
+
+        println!();
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+}