summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--chain/Cargo.toml1
-rw-r--r--chain/src/atom/default.rs41
-rw-r--r--chain/src/default.rs122
-rw-r--r--chain/src/item/default/mod.rs57
-rw-r--r--chain/src/item/default/splone.rs189
-rw-r--r--chain/src/item/genins.rs103
-rw-r--r--chain/src/item/mod.rs12
-rw-r--r--grammar/src/lib.rs3
-rw-r--r--graph/src/labelled/binary.rs2
-rw-r--r--graph_macro/src/lib.rs55
-rw-r--r--graph_macro/tests/works.rs8
-rw-r--r--nfa/Cargo.toml5
-rw-r--r--nfa/src/default/nfa.rs56
-rw-r--r--nfa/src/default/regex.rs60
14 files changed, 362 insertions, 352 deletions
diff --git a/chain/Cargo.toml b/chain/Cargo.toml
index 496f5dd..b17c50d 100644
--- a/chain/Cargo.toml
+++ b/chain/Cargo.toml
@@ -12,6 +12,7 @@ test-print-viz = []
[dependencies]
nfa = { path = "../nfa" }
graph = { path = "../graph" }
+graph_macro = { path = "../graph_macro" }
grammar = { path = "../grammar" }
[dev-dependencies]
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index a55087a..6883907 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -10,6 +10,8 @@ use nfa::{
LabelType, NfaLabel,
};
+use graph_macro::Graph;
+
use core::fmt::Display;
use std::{
collections::{hash_set::Iter, BTreeMap as Map, HashMap, HashSet},
@@ -68,9 +70,10 @@ type VirtualFrag = DefaultForest<ForestLabel<GrammarLabel>>;
type VirtualFragMap = Map<VirtualNode, Map<usize, VirtualFrag>>;
/// The type of atomic languages.
-#[derive(Debug, Clone, Default)]
+#[derive(Debug, Clone, Default, Graph)]
pub struct DefaultAtom {
grammar: Grammar,
+ #[graph]
nfa: DefaultNFA<LabelType<TNT>>,
accepting_vec: Vec<bool>,
// NOTE: This is mostly for printing and debugging
@@ -189,42 +192,6 @@ impl Display for DefaultAtom {
// Some boiler-plate delegation implementations for Graph and
// LabelGraph, in order to implement Nfa.
-impl Graph for DefaultAtom {
- type Iter<'b> = <DefaultNFA<LabelType<TNT>> as Graph>::Iter<'b>
- where
- Self: 'b;
-
- fn is_empty(&self) -> bool {
- self.nfa.is_empty()
- }
-
- fn nodes_len(&self) -> usize {
- self.nfa.nodes_len()
- }
-
- fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GraphError> {
- self.nfa.children_of(node_id)
- }
-
- fn degree(&self, node_id: usize) -> Result<usize, GraphError> {
- self.nfa.degree(node_id)
- }
-
- fn is_empty_node(&self, node_id: usize) -> Result<bool, GraphError> {
- self.nfa.is_empty_node(node_id)
- }
-
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, GraphError> {
- self.nfa.has_edge(source, target)
- }
-
- fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
- // NOTE: We cannot replace by a builder whose result is an
- // atom, not the underlying graph type.
- unimplemented!()
- }
-}
-
impl LabelGraph<LabelType<TNT>> for DefaultAtom {
type Iter<'b> = <DefaultNFA<LabelType<TNT>> as LabelGraph<LabelType<TNT>>>::Iter<'b>
where
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 1df68b5..e61df41 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -17,6 +17,8 @@ use graph::{
labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph, ParentsGraph,
};
+use graph_macro::Graph;
+
use std::collections::{HashMap as Map, HashSet, TryReserveError};
/// The errors related to taking derivatives by chain rule.
@@ -204,6 +206,8 @@ impl Iterator for DerIter {
// we just query again with the new bottom and top. This means we do
// not need to clear the map.
+// REVIEW: Why is the above needed?
+
/// This represents a tuple of bottom and top forest positions.
///
/// It is supposed to be used as keys to query the reduction
@@ -241,12 +245,13 @@ impl BoTop {
/// The value records a set of tuples of the form `(non-terminal,
/// starting_position)`. Such a tuple means we want to reduce from
/// the expansion of the given `non-terminal`, which expands from the
-/// given starting position. We need to restrict the
+/// given starting position. We need to restrict the
pub(crate) type Reducer = Map<(usize, usize), HashSet<usize>>;
/// A default implementation for the [`Chain`] trait.
-#[derive(Debug, Clone, Default)]
+#[derive(Debug, Clone, Default, Graph)]
pub struct DefaultChain {
+ #[graph]
graph: DLGraph<Edge>,
atom: DefaultAtom,
current: usize,
@@ -292,51 +297,6 @@ impl DefaultChain {
}
}
-impl Graph for DefaultChain {
- type Iter<'a> = <DLGraph<Edge> as Graph>::Iter<'a>
- where
- Self: 'a;
-
- #[inline]
- fn is_empty(&self) -> bool {
- self.graph.is_empty()
- }
-
- #[inline]
- fn nodes_len(&self) -> usize {
- self.graph.nodes_len()
- }
-
- #[inline]
- fn edges_len(&self) -> Option<usize> {
- self.graph.edges_len()
- }
-
- #[inline]
- fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
- self.graph.children_of(node_id)
- }
-
- #[inline]
- fn degree(&self, node_id: usize) -> Result<usize, GError> {
- self.graph.degree(node_id)
- }
-
- #[inline]
- fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
- self.graph.is_empty_node(node_id)
- }
-
- #[inline]
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
- self.graph.has_edge(source, target)
- }
-
- fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
- unimplemented!("I shall refactor this")
- }
-}
-
impl LabelGraph<Edge> for DefaultChain {
type Iter<'a> = <DLGraph<Edge> as LabelGraph<Edge>>::Iter<'a>
where
@@ -689,49 +649,24 @@ impl Chain for DefaultChain {
let atom_moved = atom_label.get_moved();
- if pos == 4 {
- dbg!(atom_label);
- }
-
match *atom_label.get_value() {
Some(Ter(ter)) if ter == t => {
- let new_pavi: PaVi;
-
- if !no_item {
+ let new_pavi = if !no_item {
// prepare forest fragment
let fragment =
generate_fragment([atom_moved.into(), Ter(ter).into()], pos)?;
- if pos == 4 {
- dbg!(atom_moved, label);
- self.forest
- .print_viz(&format!(
- "pos4tb - {atom_moved}-{:?}.gv",
- label.true_source()
- ))
- .unwrap();
- }
-
- new_pavi = self.forest.insert_item(
+ self.forest.insert_item(
&self.reducer,
*label,
fragment,
atom_child_iter.clone(),
&self.atom,
- )?;
-
- if pos == 4 {
- self.forest
- .print_viz(&format!(
- "pos4ta - {atom_moved}-{:?}.gv",
- label.true_source()
- ))
- .unwrap();
- }
+ )?
} else {
- new_pavi = PaVi::default();
- }
+ PaVi::default()
+ };
let generator_input = (
&self.graph,
@@ -781,13 +716,6 @@ impl Chain for DefaultChain {
let first_fragment =
generate_fragment([atom_moved.into(), Non(non).into()], pos)?;
- if pos == 4 {
- dbg!(atom_moved, label);
- self.forest
- .print_viz(&format!("pos4nb - {atom_moved}-{:?}.gv", label))
- .unwrap();
- }
-
first_segment_pavi = self.forest.insert_item(
&self.reducer,
*label,
@@ -796,12 +724,6 @@ impl Chain for DefaultChain {
&self.atom,
)?;
- if pos == 4 {
- self.forest
- .print_viz(&format!("pos4na - {atom_moved}-{:?}.gv", label))
- .unwrap();
- }
-
let virtual_fragment =
DefaultForest::new_leaf(GrammarLabel::new(Ter(t), pos));
@@ -816,12 +738,6 @@ impl Chain for DefaultChain {
std::iter::empty(),
&self.atom,
)?;
-
- if pos == 4 {
- self.forest
- .print_viz(&format!("pos4va - {atom_moved}-{:?}.gv", label))
- .unwrap();
- }
} else {
first_segment_pavi = PaVi::default();
virtual_pavi = PaVi::default();
@@ -958,7 +874,7 @@ impl Chain for DefaultChain {
dbg!(&self.accepting_sources);
- self.forest.print_viz("dbg forest before.gv").unwrap();
+ // self.forest.print_viz("dbg forest before.gv").unwrap();
for pavi in self.accepting_sources.iter() {
match pavi {
@@ -997,9 +913,9 @@ impl Chain for DefaultChain {
let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(stack.len());
- dbg!(&stack);
+ // dbg!(&stack);
- self.forest.print_viz("dbg forest.gv").unwrap();
+ // self.forest.print_viz("dbg forest.gv").unwrap();
while let Some(mut top) = stack.pop() {
if seen_nodes.contains(&top) {
@@ -1251,10 +1167,12 @@ mod test_chain {
chain.forest.print_viz("forest3.gv")?;
chain.chain(1, 4, no_item)?;
chain.forest.print_viz("forest4.gv")?;
- chain.end_of_input()?;
- chain.forest.print_viz("forest.gv")?;
- chain.forest.print_closed_viz("closed.gv")?;
+ if !no_item {
+ chain.end_of_input()?;
+ chain.forest.print_viz("forest.gv")?;
+ chain.forest.print_closed_viz("closed.gv")?;
+ }
chain.graph.print_viz("chain.gv")?;
chain.atom.print_nfa("nfa.gv")?;
item::default::print_labels(&chain.atom, &chain.forest)?;
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 3903162..6d28956 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -8,6 +8,8 @@ use graph::{
builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph,
};
+use graph_macro::Graph;
+
use std::collections::HashSet;
use core::fmt::Display;
@@ -73,7 +75,7 @@ impl From<ForestLabelError> for Error {
}
/// A default implementation of forest.
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, Graph)]
pub struct DefaultForest<T: GraphLabel> {
pub(crate) graph: PLGraph<T>,
root: Option<usize>,
@@ -94,56 +96,6 @@ impl<T: GraphLabel> AsRef<DefaultForest<T>> for DefaultForest<T> {
}
}
-impl<T: GraphLabel> Graph for DefaultForest<T> {
- type Iter<'a> = <PLGraph<T> as Graph>::Iter<'a>
- where
- Self: 'a;
-
- #[inline]
- fn is_empty(&self) -> bool {
- self.graph.is_empty()
- }
-
- #[inline]
- fn nodes_len(&self) -> usize {
- self.graph.nodes_len()
- }
-
- #[inline]
- fn edges_len(&self) -> Option<usize> {
- self.graph.edges_len()
- }
-
- #[inline]
- fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
- self.graph.children_of(node_id)
- }
-
- #[inline]
- fn degree(&self, node_id: usize) -> Result<usize, GError> {
- self.graph.degree(node_id)
- }
-
- #[inline]
- fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
- self.graph.is_empty_node(node_id)
- }
-
- #[inline]
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
- self.graph.has_edge(source, target)
- }
-
- fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
- unimplemented!()
- }
-
- #[inline]
- fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
- self.graph.print_viz(filename)
- }
-}
-
impl<T: GraphLabel> ParentsGraph for DefaultForest<T> {
type Iter<'a>= <PLGraph<T> as ParentsGraph>::Iter<'a>
where
@@ -1081,6 +1033,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
// }
/// Set the position of every node.
+ ///
+ /// If ALLP is non-nil or if the node is a terminal node, also set
+ /// the ending position.
pub(crate) fn set_pos(&mut self, pos: usize, allp: bool) -> Result<(), Error> {
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 4cd11b9..d77686e 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -123,7 +123,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
return Ok(cloned);
}
- let new_label = self.create_new_label(node, end, edge_index)?;
+ let new_label = self.create_new_label(node, end, edge_index, None)?;
let new_label = match new_label {
Eon::Nex(label) => label,
@@ -140,7 +140,126 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
return self.split_node(new_label, node, edge_index, completingp);
}
- // replace the label directly
+ self.replace_label(node, new_label)?;
+
+ Ok(node)
+ }
+
+ /// Split or clone, and then plant.
+ ///
+ /// # Splone
+ ///
+ /// This function is similar to
+ /// [`splone`][DefaultForest::<ForestLabel<GrammarLabel>>::splone],
+ /// but this is specialized for planting a fragment under the
+ /// newly sploned node. See the above-mentionned function for
+ /// details on how to splone.
+ ///
+ /// # Parameter `planted`
+ ///
+ /// The function to plant a fragment takes a parameter `planted`,
+ /// which indicates whether or not the fragment had already been
+ /// planted before. This is used to avoid re-inserting fragments
+ /// into the forest. One can just add an edge and be done.
+ ///
+ /// # Special treatment
+ ///
+ /// This function is aimed at solving a specific problem that the
+ /// function
+ /// [`splone`][DefaultForest::<ForestLabel<GrammarLabel>>::splone]
+ /// faces: duplication of nodes after planting a fragment under
+ /// the newly sploned node. That is, if we splone a node and then
+ /// immediately plant a fragment under it, then that new node will
+ /// become a different node from the original sploned node, so if
+ /// we splone another node that ends up creating the same sploned
+ /// node, and if we plant the same fragment under it, we will end
+ /// up creating duplicated cloned nodes, which later mess up the
+ /// forests.
+ ///
+ /// So this function first checks if the would-be-sploned node
+ /// with the fragment planted already exists; if so, then just
+ /// return that node, otherwise we perform the usual sploning and
+ /// plant the fragment after the splone.
+ ///
+ /// # Special values of two parameters to `splone`
+ ///
+ /// Since we want to plant a fragment under the splone, the
+ /// parameter `end` to the splone function is set to `None`
+ /// automatically.
+ ///
+ /// Moreover, the parameter `completingp` is for completing the
+ /// forest at the end, while we are definitely not at the end if
+ /// we are going to plant a fragment after sploning, so that
+ /// parameter is automatically set to `false` as well.
+ pub(crate) fn splant(
+ &mut self,
+ node: usize,
+ edge_index: usize,
+ fragment: &DefaultForest<ForestLabel<GrammarLabel>>,
+ planted: bool,
+ ) -> Result<usize, Error> {
+ let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
+
+ assert!(get_nt_label(node_label.label()).is_some());
+
+ if node_label.is_packed() {
+ self.print_viz("dbg forest.gv").unwrap();
+ dbg!(self.vertex_label(node)?);
+ return Err(Error::SplitPack(node));
+ }
+
+ let node_end = node_label.label().end();
+ let node_degree = self.degree(node)?;
+
+ // We can check the end to know whether the new label is equal
+ // to the old label.
+ if node_end.is_none() {
+ if node_degree == edge_index + 2 {
+ let last_child = self.nth_child(node, node_degree - 1)?;
+
+ if self.is_prefix(last_child, fragment.borrow())? {
+ return Ok(node);
+ }
+ }
+
+ if node_degree <= edge_index + 1 {
+ self.plant(node, fragment, planted)?;
+
+ return Ok(node);
+ }
+
+ let cloned = self.clone_node(node, edge_index + 1, false)?;
+
+ self.plant(cloned, fragment, planted)?;
+
+ return Ok(cloned);
+ }
+
+ let new_label = self.create_new_label(node, None, edge_index, Some((fragment, planted)))?;
+
+ let new_label = match new_label {
+ Eon::Nex(label) => label,
+ Eon::Ex(existing) => {
+ return Ok(existing);
+ }
+ };
+
+ let splitted = self.split_node(new_label, node, edge_index, false)?;
+
+ self.plant(splitted, fragment, planted)?;
+
+ Ok(splitted)
+ }
+
+ /// Replace the label of a node by a new label.
+ ///
+ /// This also handles the labels of parents of the node.
+ fn replace_label(
+ &mut self,
+ node: usize,
+ new_label: ForestLabel<GrammarLabel>,
+ ) -> Result<(), Error> {
+ let end = new_label.label().end();
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
@@ -162,7 +281,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
panic!("assumption fails");
}
- assert!(get_rule_label(parent_label).is_some());
assert_eq!(builder.degree(parent)?, 1);
if let Some(pos) = end {
@@ -176,7 +294,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
builder.set_label(parent, parent_label)?;
}
- Ok(node)
+ Ok(())
}
/// Procedure to split the node:
@@ -352,11 +470,23 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
/// existing label, and return the clone of the cloned label.
///
/// 7. Else return the plain label.
+ ///
+ /// # Fragment planting
+ ///
+ /// If the parameter `fragment` contains a fragment, that means we
+ /// also check if an existing label is what we want by checking
+ /// whether it has the same children except for the last one,
+ /// whereas its last child contains the fragment as a prefix.
+ ///
+ /// Also, if an existing label is found to have exactly the same
+ /// children, then for the sake of consistency, we plant the
+ /// fragment under that existing node.
fn create_new_label(
&mut self,
node: usize,
end: Option<usize>,
edge_index: usize,
+ fragment: Option<(&DefaultForest<ForestLabel<GrammarLabel>>, bool)>,
) -> Result<Eon, Error> {
let mut copied_label = self
.vertex_label(node)?
@@ -373,9 +503,29 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
if let Some(packed) = self.query_label(label) {
for child in self.children_of(packed)? {
- if self.has_same_children(child, node, self.degree(child)?, edge_index + 1)? {
+ let child_degree = self.degree(child)?;
+
+ if self.has_same_children(child, node, child_degree, edge_index + 1)? {
+ if let Some((fragment, planted)) = fragment {
+ self.plant(child, fragment, planted)?;
+ }
+
return Ok(Eon::Ex(child));
}
+
+ if let Some((fragment, _planted)) = fragment {
+ let modified_degree = std::cmp::max(child_degree, 1) - 1;
+
+ if self.has_same_children(child, node, modified_degree, edge_index)?
+ && child_degree != 0
+ {
+ let last_child = self.nth_child(child, child_degree - 1)?;
+
+ if self.is_prefix(last_child, fragment)? {
+ return Ok(Eon::Ex(child));
+ }
+ }
+ }
}
let mut packed_children = self.children_of(packed)?;
@@ -384,18 +534,37 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let clone_index = self.clone_node(first_child, 0, true)?;
- Ok(Eon::Nex(ForestLabel::new(
- copied_label,
- ForestLabelType::Cloned(clone_index),
- )))
+ let cloned_label = ForestLabel::new(copied_label, ForestLabelType::Cloned(clone_index));
+
+ Ok(Eon::Nex(cloned_label))
} else {
let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
if let Some(existing) = self.query_label(plain_label) {
- if self.has_same_children(existing, node, self.degree(existing)?, edge_index + 1)? {
+ let existing_degree = self.degree(existing)?;
+
+ if self.has_same_children(existing, node, existing_degree, edge_index + 1)? {
+ if let Some((fragment, planted)) = fragment {
+ self.plant(existing, fragment, planted)?;
+ }
+
return Ok(Eon::Ex(existing));
}
+ if let Some((fragment, _planted)) = fragment {
+ let modified_degree = std::cmp::max(existing_degree, 1) - 1;
+
+ if existing_degree != 0
+ && self.has_same_children(existing, node, modified_degree, edge_index)?
+ {
+ let last_child = self.nth_child(existing, existing_degree - 1)?;
+
+ if self.is_prefix(last_child, fragment)? {
+ return Ok(Eon::Ex(existing));
+ }
+ }
+ }
+
let clone_index = self.clone_node(existing, 0, true)?;
Ok(Eon::Nex(ForestLabel::new(
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index 0c3f616..97d7ba9 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -190,7 +190,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let root = if let Some(root) = self.root() {
root
} else {
- panic!("the forest must be non-empty when we insert items");
+ unreachable!("the forest must be non-empty when we insert items");
};
let pavi = label.forest_source();
@@ -211,13 +211,50 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let pos = fragment_root_label.label().start();
+ dbg!((pos, label));
+
+ let tnt_string = {
+ let empty_p = atom_child_iter.len() == 0;
+ let label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap();
+
+ match label.label().label() {
+ GrammarLabelType::TNT(TNT::Ter(t)) => {
+ format!("t {t}")
+ }
+ GrammarLabelType::TNT(TNT::Non(n)) => {
+ format!("n {n} {}", if empty_p { "second" } else { "first" })
+ }
+ _ => "error".to_string(),
+ }
+ };
+
+ let num = {
+ let mut repetition = 0;
+
+ while std::fs::metadata(format!(
+ "/Users/durand/Desktop/Centre/A propos de programmes/Rust/rep/chain/output/pos {pos} {tnt_string} {repetition}.gv"
+ ))
+ .is_ok()
+ {
+ repetition += 1;
+ }
+
+ repetition
+ };
+
+ self.print_viz(&format!("pos {pos} {tnt_string} {num}.gv"))
+ .unwrap();
+
self.extra_reductions(
- BoTop::new(pavi, true_source),
+ BoTop::new(true_source, pavi),
pos,
reducer.borrow(),
atom.borrow(),
)?;
+ self.print_viz(&format!("pos {pos} {tnt_string} {num} stage 1.gv"))
+ .unwrap();
+
// Ensure the last node in the PaVi is a terminal or a
// non-terminal node, as an extra safety guard during
// development.
@@ -259,6 +296,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
}
}
+ // TODO: Print each and every step.
+
// TODO: Refactor this.
let is_empty_segment = pavi.is_empty();
@@ -290,15 +329,19 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
.vertex_label(frag_nodes_len - 2)?
.ok_or(Error::NodeNoLabel(frag_nodes_len - 2))?;
- // NOTE: The function
- // `plant_if_needed` assumes that we
- // want to plant the fragment as the
- // first child of the node. This
- // assumption holds in this case, but
- // not in general.
+ // NOTE: The function `plant_at_start`
+ // assumes that we want to plant the
+ // fragment as the first child of the
+ // node. This assumption holds in
+ // this case, but not in general.
self.plant_at_start(node, frag)?;
+ self.print_viz(&format!(
+ "pos {pos} {tnt_string} {num} stage 1.5 {node}.gv"
+ ))
+ .unwrap();
+
let rule_label_pos = self
.query_label(last_but_one_label)
.expect("the forest was wrongly planted");
@@ -370,6 +413,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let sploned_node =
self.splone(node.node(), Some(pos), node.edge(), false)?;
+ self.print_viz(&format!(
+ "pos {pos} {tnt_string} {num} stage 2 {} {}.gv",
+ node.node(),
+ node.edge(),
+ ))
+ .unwrap();
+
node_label = self
.vertex_label(sploned_node)?
.ok_or(Error::NodeNoLabel(sploned_node))?;
@@ -394,9 +444,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let parents_iter = self.parents_of(node.node())?;
for parent in parents_iter {
+ let parent_node = parent.node();
+
let parent_label = self
- .vertex_label(parent.node())?
- .ok_or_else(|| Error::NodeNoLabel(parent.node()))?
+ .vertex_label(parent_node)?
+ .ok_or(Error::NodeNoLabel(parent_node))?
.label();
if parent_label.label().rule().is_none() {
@@ -448,15 +500,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
return Err(Error::CannotPlant);
}
- if pos == 4 && matches!(true_source, PaVi::Virtual(_, _, _)) {
- dbg!(&stack, reduction_info, true_source, pavi);
- self.print_viz("pos4ib.gv").unwrap();
- }
-
for parent in stack {
- let sploned_node = self.splone(parent.node(), None, parent.edge(), false)?;
+ let splanted = self.splant(parent.node(), parent.edge(), fragment, non_empty)?;
- self.plant(sploned_node, fragment, non_empty)?;
+ self.print_viz(&format!(
+ "pos {pos} {tnt_string} {num} stage 3 {} {} {splanted}.gv",
+ parent.node(),
+ parent.edge(),
+ ))
+ .unwrap();
non_empty = true;
}
@@ -533,12 +585,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
}
};
- let t = match root_label.label().label().tnt().unwrap() {
+ let error_str = "a virtual fragment should consist of a single terminal node";
+
+ let t = match root_label.label().label().tnt().expect(error_str) {
TNT::Ter(t) => t,
_ => {
dbg!(root_label);
- panic!("a virtual fragment should consist of a single terminal node")
+ panic!("{error_str}")
}
};
@@ -550,7 +604,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
/// Perform extra reductions.
///
- /// To be precise, this functions first splones the bottom node,
+ /// To be precise, this function first splones the bottom node,
/// and then queries the reducer to find the next nodes to splone,
/// and repeats this process until either we find the top node, or
/// the reducer says to stop.
@@ -583,6 +637,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let mut stack = vec![bottom_node];
+ // Exclude duplicate nodes to ensure that no infinite
+ // recursion occurs. In the future I shall experiment if this
+ // is necessary, and get rid of this if possible.
let mut seen_nodes: HashSet<usize> = Default::default();
let mut result = Vec::new();
@@ -683,6 +740,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
// REVIEW: is this really correct?
dbg!("this should not really happen?");
+ // SUMMARY: splone every child of nth_child
+
let mut result: usize = nth_child;
for node in self.children_of(nth_child)?.collect::<Vec<_>>() {
@@ -806,8 +865,8 @@ mod genins_test {
assert!(matches!(atom.query_reduction(17, 9), Ok(Some(&[1]))));
- assert!(matches!(atom.query_reduction(35, 9), Ok(Some(&[1, 2]))));
- assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2]))));
+ // assert!(matches!(atom.query_reduction(35, 9), Ok(Some(&[1, 2]))));
+ // assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2]))));
Ok(())
}
diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs
index f8e0aa0..5efa710 100644
--- a/chain/src/item/mod.rs
+++ b/chain/src/item/mod.rs
@@ -21,11 +21,15 @@ use core::borrow::Borrow;
/// A virtual segment represents an expansion from a non-terminal by a
/// terminal. We do not directly add this segment when we encounter
/// this expansion at the start because this expansion might contain
-/// multiple derivations some of which will not be used.
+/// multiple derivations some of which might not be used.
///
/// If we add the expansion immediately when we encounter it, we have
/// to later discern and delete those unwanted derivations. This is
-/// asking for trouble, in my experiences.
+/// asking for trouble, as I learned from experiences.
+///
+/// # Empty
+///
+/// Also this might be empty if it represents the root node.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
pub enum PaVi {
/// An edge from a node, as the n-th child.
@@ -35,8 +39,8 @@ pub enum PaVi {
///
/// # Tuple elements
///
- /// The contained tuple is of the form (nt, t, node), which means
- /// a virtually added node at the `node` representing the
+ /// The contained tuple is of the form `(nt, t, node)` , which
+ /// means a virtually added node at the `node` representing the
/// expansion from the non-terminal `nt` by the terminal `t`.
Virtual(usize, usize, usize),
/// This is an empty segment that represents the root node. This
diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs
index 54d9ebc..135f668 100644
--- a/grammar/src/lib.rs
+++ b/grammar/src/lib.rs
@@ -82,6 +82,7 @@ pub enum TNT {
Ter(usize),
/// Nonterminal variant
Non(usize),
+ // TODO: Add a range type.
}
impl Display for TNT {
@@ -834,6 +835,8 @@ impl Display for Grammar {
}
}
+pub mod abnf;
+
// A helper module that provides some grammars for testing.
#[cfg(feature = "test-helper")]
pub mod test_grammar_helper;
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 3b96b92..9f3afa8 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -220,7 +220,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
for node in self.nodes() {
post.push_str(&format!(
- " {node} [label = \"{}\"]\n",
+ " {node} [label = \"{node}:{}\"]\n",
match self.vertex_label(node) {
Ok(Some(label)) => {
format!("{label}")
diff --git a/graph_macro/src/lib.rs b/graph_macro/src/lib.rs
index 0f56f57..3b7742a 100644
--- a/graph_macro/src/lib.rs
+++ b/graph_macro/src/lib.rs
@@ -84,20 +84,20 @@ impl CompileError {
// I cannot use the parse method of the type TokenStream, as
// that will not set the spans properly.
- let compile_error_ident = TokenTree::Ident(Ident::new("compile_error", self.span.clone()));
+ let compile_error_ident = TokenTree::Ident(Ident::new("compile_error", self.span));
let mut exclamation_punct = TokenTree::Punct(Punct::new('!', Spacing::Alone));
- exclamation_punct.set_span(self.span.clone());
+ exclamation_punct.set_span(self.span);
let mut arg_mes_literal = TokenTree::Literal(Literal::string(&self.mes));
- arg_mes_literal.set_span(self.span.clone());
+ arg_mes_literal.set_span(self.span);
let arg_mes_stream = [arg_mes_literal].into_iter().collect();
let mut arg_group = TokenTree::Group(Group::new(Delimiter::Parenthesis, arg_mes_stream));
- arg_group.set_span(self.span.clone());
+ arg_group.set_span(self.span);
let mut semi_colon_punct = TokenTree::Punct(Punct::new(';', Spacing::Alone));
@@ -158,7 +158,7 @@ pub fn graph_derive(input: TokenStream) -> TokenStream {
let mut result = String::new();
if !generics.is_empty() {
- result.push_str("<");
+ result.push('<');
}
for generic in generics.iter() {
@@ -166,7 +166,7 @@ pub fn graph_derive(input: TokenStream) -> TokenStream {
}
if !generics.is_empty() {
- result.push_str(">");
+ result.push('>');
}
result
@@ -176,7 +176,7 @@ pub fn graph_derive(input: TokenStream) -> TokenStream {
let mut result = String::new();
if !generics.is_empty() {
- result.push_str("<");
+ result.push('<');
}
for generic in generics.iter() {
@@ -184,7 +184,7 @@ pub fn graph_derive(input: TokenStream) -> TokenStream {
}
if !generics.is_empty() {
- result.push_str(">");
+ result.push('>');
}
result
@@ -236,6 +236,11 @@ self.{field_name}.has_edge(nodea, nodeb)
fn replace_by_builder(&mut self, _builder: impl graph::builder::Builder<Result = Self>) {{
unimplemented!()
}}
+
+#[inline]
+fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {{
+self.{field_name}.print_viz(filename)
+}}
}}"
);
@@ -386,6 +391,10 @@ fn get_graph_field_name_type(
let mut cloned_body = body.clone();
+ while move_attributes(&mut cloned_body).is_ok() {}
+
+ let _ = get_visibility_mod(&mut cloned_body)?;
+
let mut result_name = get_first_ident(&mut cloned_body, g.span())?.to_string();
move_punct(&mut cloned_body, ':')?;
@@ -418,12 +427,19 @@ fn get_graph_field_name_type(
break;
}
- let _ = move_punct(&mut attr_stream, ',');
+ get_until(
+ &mut attr_stream,
+ |tree| matches!(tree, TokenTree::Punct(p) if p.as_char() == ','),
+ true,
+ true,
+ )?;
}
body.next();
if found_attribute {
+ while move_attributes(&mut body).is_ok() {}
+
get_visibility_mod(&mut body)?;
result_name = get_ident(&mut body)?.to_string();
@@ -557,12 +573,9 @@ fn get_first_ident(
input: &mut Peekable<impl Iterator<Item = TokenTree>>,
span: Span,
) -> Result<Ident, CompileError> {
- while let Some(tree) = input.next() {
- match tree {
- TokenTree::Ident(id) => {
- return Ok(id);
- }
- _ => {}
+ for tree in input {
+ if let TokenTree::Ident(id) = tree {
+ return Ok(id);
}
}
@@ -580,7 +593,7 @@ fn get_until(
let mut found_predicate = false;
if consume_boundary {
- while let Some(tree) = input.next() {
+ for tree in input.by_ref() {
if predicate(&tree) {
found_predicate = true;
break;
@@ -647,16 +660,14 @@ fn move_attributes(
match input.peek() {
Some(TokenTree::Group(g)) if g.delimiter() == Delimiter::Bracket => {
input.next();
+
+ Ok(())
}
Some(_) => {
- return myerror!("expected a group in square brackets", input);
- }
- _ => {
- return end_of_input;
+ myerror!("expected a group in square brackets", input)
}
+ _ => end_of_input,
}
-
- Ok(())
}
Some(_) => myerror!(error_mes, input),
_ => end_of_input,
diff --git a/graph_macro/tests/works.rs b/graph_macro/tests/works.rs
index a57e866..dc0f75a 100644
--- a/graph_macro/tests/works.rs
+++ b/graph_macro/tests/works.rs
@@ -11,13 +11,17 @@ pub(crate) struct Haha {
#[derive(Debug)]
/// Testing docs
-#[allow(unused)]
+#[repr(C)]
#[derive(Default, Graph)]
+#[allow(unused)]
pub struct HahaU(pub(crate) graph::ALGraph);
#[derive(Debug, Graph)]
pub struct HahaG<T: graph::GraphLabel> {
- graph: graph::DLGraph<T>,
+ #[graph(haha)]
+ #[allow(unused)]
+ #[inline]
+ pub(crate) graph: graph::DLGraph<T>,
}
impl<T: graph::GraphLabel> Default for HahaG<T> {
diff --git a/nfa/Cargo.toml b/nfa/Cargo.toml
index 9eac932..75a6a43 100644
--- a/nfa/Cargo.toml
+++ b/nfa/Cargo.toml
@@ -6,10 +6,9 @@ edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
-graph = { path = "../graph", optional = true }
+graph = { path = "../graph" }
+graph_macro = { path = "../graph_macro" }
receme = { path = "../receme", optional = true }
[features]
-default = ["default-graph"]
-default-graph = ["dep:graph"]
recursion = ["dep:receme"]
diff --git a/nfa/src/default/nfa.rs b/nfa/src/default/nfa.rs
index 6b1e56f..d2fe88e 100644
--- a/nfa/src/default/nfa.rs
+++ b/nfa/src/default/nfa.rs
@@ -12,8 +12,10 @@ use crate::{
use core::fmt::{Debug, Display};
+use graph_macro::Graph;
+
/// Default NFA implementation.
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, Graph)]
pub struct DefaultNFA<T: GraphLabel> {
graph: DLGraph<T>,
}
@@ -31,51 +33,7 @@ impl<T: GraphLabel + Display> Default for DefaultNFA<T> {
// I deliberately avoid using [`Deref`][std::ops::Deref] here, as I do
// not want to dereference an NFA to a Graph.
-impl<T: GraphLabel + Display> Graph for DefaultNFA<T> {
- type Iter<'a> = <DLGraph<T> as Graph>::Iter<'a> where T: 'a;
-
- #[inline]
- fn is_empty(&self) -> bool {
- self.graph.is_empty()
- }
-
- #[inline]
- fn nodes_len(&self) -> usize {
- self.graph.nodes_len()
- }
-
- #[inline]
- fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
- self.graph.children_of(node_id)
- }
-
- #[inline]
- fn degree(&self, node_id: usize) -> Result<usize, GError> {
- self.graph.degree(node_id)
- }
-
- #[inline]
- fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
- self.graph.is_empty_node(node_id)
- }
-
- #[inline]
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
- self.graph.has_edge(source, target)
- }
-
- #[inline]
- fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
- self.graph.print_viz(filename)
- }
-
- #[inline]
- fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
- unimplemented!()
- }
-}
-
-impl<T: GraphLabel + Display> LabelGraph<T> for DefaultNFA<T> {
+impl<T: GraphLabel> LabelGraph<T> for DefaultNFA<T> {
type Iter<'a> = <DLGraph<T> as LabelGraph<T>>::Iter<'a> where T: 'a;
type LabelIter<'a> = <DLGraph<T> as LabelGraph<T>>::LabelIter<'a> where T: 'a;
@@ -119,14 +77,14 @@ impl<T: GraphLabel + Display> LabelGraph<T> for DefaultNFA<T> {
}
}
-impl<T: GraphLabel + Display> LabelExtGraph<T> for DefaultNFA<T> {
+impl<T: GraphLabel> LabelExtGraph<T> for DefaultNFA<T> {
#[inline]
fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, GError> {
self.graph.extend(edges)
}
}
-impl<T: GraphLabel + Display> Nfa<T> for DefaultNFA<T> {
+impl<T: GraphLabel> Nfa<T> for DefaultNFA<T> {
type FromRegex<S: GraphLabel + Display + Default> = DefaultNFA<S>;
// Reminder: This is an adopted version of Thompson's
@@ -484,7 +442,7 @@ impl<T: GraphLabel + Display> Nfa<T> for DefaultNFA<T> {
}
}
-impl<T: GraphLabel + Display + Debug> Display for DefaultNFA<T> {
+impl<T: GraphLabel> Display for DefaultNFA<T> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
Debug::fmt(self, f)
}
diff --git a/nfa/src/default/regex.rs b/nfa/src/default/regex.rs
index 1c22687..1b1b325 100644
--- a/nfa/src/default/regex.rs
+++ b/nfa/src/default/regex.rs
@@ -4,6 +4,8 @@ use graph::{error::Error as GError, ALGraph, ExtGraph, Graph, GraphLabel};
use crate::{desrec::DesRec, error::Error, Regex};
+use graph_macro::Graph;
+
#[cfg(feature = "recursion")]
use receme::{algebra::Algebra, catana::Cata};
@@ -64,9 +66,10 @@ impl<T: GraphLabel> Display for RegexType<T> {
}
/// A default implementation of regular expressions.
-#[derive(Debug, Clone)]
-pub struct DefaultRegex<T: GraphLabel + Display> {
+#[derive(Debug, Clone, Graph)]
+pub struct DefaultRegex<T: GraphLabel> {
/// The underlying graph is stored using adjacency lists.
+ #[graph]
graph: ALGraph,
/// The types of the underlying nodes.
types: Vec<RegexType<T>>,
@@ -76,7 +79,7 @@ pub struct DefaultRegex<T: GraphLabel + Display> {
root: Option<usize>,
}
-impl<T: GraphLabel + Display> Default for DefaultRegex<T> {
+impl<T: GraphLabel> Default for DefaultRegex<T> {
fn default() -> Self {
Self {
graph: Default::default(),
@@ -503,54 +506,13 @@ impl<T: GraphLabel> DefaultRegex<T> {
}
}
-impl<T: GraphLabel + Display + Debug> Display for DefaultRegex<T> {
+impl<T: GraphLabel> Display for DefaultRegex<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.to_string_with(|t| format!("{t}"))?)
}
}
-impl<T: GraphLabel + Display> Graph for DefaultRegex<T> {
- type Iter<'a> = <ALGraph as Graph>::Iter<'a>
- where
- Self: 'a;
-
- #[inline]
- fn is_empty(&self) -> bool {
- self.graph.is_empty()
- }
-
- #[inline]
- fn nodes_len(&self) -> usize {
- self.graph.nodes_len()
- }
-
- #[inline]
- fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
- self.graph.children_of(node_id)
- }
-
- #[inline]
- fn degree(&self, node_id: usize) -> Result<usize, GError> {
- self.graph.degree(node_id)
- }
-
- #[inline]
- fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
- self.graph.is_empty_node(node_id)
- }
-
- #[inline]
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
- self.graph.has_edge(source, target)
- }
-
- #[inline]
- fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
- unimplemented!()
- }
-}
-
-impl<T: GraphLabel + Display + Debug> Regex<RegexType<T>> for DefaultRegex<T> {
+impl<T: GraphLabel> Regex<RegexType<T>> for DefaultRegex<T> {
/// Return the root of the regular expression.
#[inline]
fn root(&self) -> Option<usize> {
@@ -649,7 +611,7 @@ pub struct DefaultRegParser<T: GraphLabel + Display> {
_phantom: PhantomData<T>,
}
-impl<T: GraphLabel + Display> DefaultRegParser<T> {
+impl<T: GraphLabel> DefaultRegParser<T> {
/// Query if a terminal or a non-terminal is already found.
///
/// If found, return the associated index of the terminal or
@@ -676,7 +638,7 @@ impl<T: GraphLabel + Display> DefaultRegParser<T> {
}
}
-impl<T: GraphLabel + Display> Default for DefaultRegParser<T> {
+impl<T: GraphLabel> Default for DefaultRegParser<T> {
fn default() -> Self {
Self {
ter_map: Default::default(),
@@ -686,7 +648,7 @@ impl<T: GraphLabel + Display> Default for DefaultRegParser<T> {
}
}
-impl<T: GraphLabel + Display + Debug> DesRec for DefaultRegParser<T> {
+impl<T: GraphLabel> DesRec for DefaultRegParser<T> {
type Label = RegexType<T>;
type Regex = DefaultRegex<T>;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-12-25 18:14:44 +0000