summaryrefslogtreecommitdiff
path: root/chain
diff options
context:
space:
mode:
Diffstat (limited to 'chain')
-rw-r--r--chain/src/atom/default.rs2
-rw-r--r--chain/src/default.rs11
-rw-r--r--chain/src/item/default/mod.rs122
-rw-r--r--chain/src/item/default/splone.rs37
-rw-r--r--chain/src/item/genins.rs23
-rw-r--r--chain/src/item/reduction.rs21
6 files changed, 186 insertions, 30 deletions
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index e156178..6ae924f 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -123,7 +123,7 @@ impl DefaultAtom {
.accepting_vec
.iter()
.enumerate()
- .filter_map(|(index, pred)| (*pred).then(|| index))
+ .filter_map(|(index, pred)| (*pred).then_some(index))
{
print!("{nullable}, ");
}
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 5f83115..618e560 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -594,13 +594,10 @@ impl Chain for DefaultChain {
&& matches!(self.forest.degree(1), Ok(d) if d > 0)
{
// dbg!(self.forest.vertex_label(1)?, self.atom.empty());
- match self.forest.vertex_label(1) {
- Ok(Some(label)) => {
- if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) {
- self.forest.remove_node(1)?;
- }
+ if let Ok(Some(label)) = self.forest.vertex_label(1) {
+ if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) {
+ self.forest.remove_node(1)?;
}
- _ => {}
}
}
@@ -1189,7 +1186,7 @@ mod test_chain {
let no_item = false;
- let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1];
+ let input: &[usize] = &[3, 0, 2, 1, 1, 0, 1, 4, 0, 2, 1];
let input_len = input.len();
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index b84d4ea..de43f37 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -965,7 +965,8 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
return Ok(node);
}
- fragment.set_root(1)?;
+ // fragment.set_root(1)?;
+ fragment.remove_prefix(1)?;
let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
@@ -1056,6 +1057,45 @@ impl<T: GraphLabel> DefaultForest<T> {
Self { graph, root }
}
+ /// Remove a prefix of the fragment.
+ ///
+ /// The new forest will have root set to 0, unless the entire
+ /// forest is removed.
+ pub fn remove_prefix(&mut self, prefix_len: usize) -> Result<(), Error> {
+ let nodes_len = self.nodes_len();
+
+ if prefix_len >= nodes_len {
+ self.graph = Default::default();
+ self.root = None;
+
+ return Ok(());
+ }
+
+ let mut new_graph = Default::default();
+ let mut new_builder = PLGBuilderMut::from_graph_mut(&mut new_graph);
+
+ let dummy_label = self.vertex_label(0)?.ok_or(Error::NodeNoLabel(0))?;
+
+ for i in prefix_len..nodes_len {
+ let label = self.vertex_label(i)?.ok_or(Error::NodeNoLabel(i))?;
+
+ new_builder.add_vertex(label);
+ }
+
+ for (i, j) in self.edges() {
+ if i < prefix_len || j < prefix_len {
+ continue;
+ }
+
+ new_builder.add_edge(i - prefix_len, j - prefix_len, dummy_label)?;
+ }
+
+ self.graph = new_graph;
+ self.root = Some(0);
+
+ Ok(())
+ }
+
/// Set the root to the given node.
pub fn set_root(&mut self, root: usize) -> Result<(), Error> {
if root >= self.nodes_len() {
@@ -1173,14 +1213,18 @@ 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
+ /// If ALLP is `true` or if the node is a terminal node, also set
/// the ending position whereever reasonable.
+ ///
+ /// If ALLP is `false` , always return `true`. Otherwise return
+ /// `true` if and only if the root is set to closed. If the
+ /// forest is empty, this returns `false`.
pub(crate) fn set_pos(
&mut self,
atom: &DefaultAtom,
pos: usize,
allp: bool,
- ) -> Result<(), Error> {
+ ) -> Result<bool, Error> {
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
let nodes_len = builder.nodes_len();
@@ -1200,7 +1244,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
builder.set_label(node, new_label)?;
}
- return Ok(());
+ return Ok(true);
}
// We assign every node to be open first, and then start from
@@ -1267,7 +1311,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
builder.set_label(node, new_label)?;
}
- Ok(())
+ let root = if let Some(root) = self.root() {
+ root
+ } else {
+ return Ok(false);
+ };
+
+ let result = closed_nodes
+ .get(root)
+ .copied()
+ .ok_or(Error::IndexOutOfBounds(root, nodes_len))?;
+
+ Ok(result)
}
}
@@ -1559,6 +1614,40 @@ mod item_test {
}
#[test]
+ fn test_remove_prefix() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = leaf!(0, usize);
+
+ forest.plant(0, leaf!(1), false)?;
+ forest.plant(1, leaf!(2), false)?;
+ forest.plant(2, leaf!(3), false)?;
+ forest.plant(3, leaf!(4), false)?;
+ forest.plant(4, leaf!(5), false)?;
+
+ forest.remove_prefix(2)?;
+
+ dbg!(&forest);
+
+ assert_eq!(forest.nodes_len(), 4);
+ assert_eq!(forest.root(), Some(0));
+
+ for i in 0..4 {
+ assert!(matches!(forest.vertex_label(i),
+ Ok(Some(label)) if
+ label == ForestLabel::new(i + 2, ForestLabelType::Plain)));
+
+ for j in 0..4 {
+ if i + 1 == j {
+ assert!(matches!(forest.has_edge(i, j), Ok(true)));
+ } else {
+ assert!(matches!(forest.has_edge(i, j), Ok(false)));
+ }
+ }
+ }
+
+ Ok(())
+ }
+
+ #[test]
fn test_eq() -> Result<(), Box<dyn std::error::Error>> {
let mut forest = leaf!(0, usize);
@@ -1598,6 +1687,25 @@ mod item_test {
atom.print_nullables();
+ let non_nullable: usize = {
+ let mut result = 0usize;
+
+ for i in 0..(atom.total()) {
+ if !atom.is_accepting(2 * i + 1)? {
+ result = i;
+ break;
+ }
+ }
+
+ if result != 0 {
+ result
+ } else {
+ panic!("grammar has no non-nullable position?");
+ }
+ };
+
+ println!("the chosen non-nullable is {non_nullable}");
+
let mut forest: DefaultForest<ForestLabel<GrammarLabel>> = DefaultForest::new_leaf_raw(
ForestLabel::new(GrammarLabel::new(TNT::Non(0), 0), ForestLabelType::Plain),
);
@@ -1623,7 +1731,7 @@ mod item_test {
forest.plant(
2,
DefaultForest::new_leaf_raw(ForestLabel::new(
- GrammarLabel::new(104, 0),
+ GrammarLabel::new(non_nullable, 0),
ForestLabelType::Plain,
)),
false,
@@ -1658,7 +1766,7 @@ mod item_test {
// forest.print_viz("test.gv")?;
- forest.set_pos(&atom, 1, true)?;
+ assert!(!forest.set_pos(&atom, 1, true)?);
// forest.print_viz("test set.gv")?;
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 2ac3d73..9da156a 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -125,6 +125,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let new_label = self.create_new_label(node, end, edge_index, None)?;
+ // if node == 15 {
+ // dbg!(end, new_label, node_label);
+ // }
+
let new_label = match new_label {
Eon::Nex(label) => label,
Eon::Ex(existing) => {
@@ -374,7 +378,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
///
/// 1. Copy the old label.
///
- /// 2. Set the end to `pos`.
+ /// 2. Set the end to `end`.
///
/// 3. Pack the label.
///
@@ -412,9 +416,24 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
copied_label.set_end_option(end);
- let label = ForestLabel::new(copied_label, ForestLabelType::Packed);
+ let packed_label = ForestLabel::new(copied_label, ForestLabelType::Packed);
+ let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
+
+ let root = if let Some(root) = self.root() {
+ root
+ } else {
+ return Ok(Eon::Nex(plain_label));
+ };
+
+ let packed_query = self.query_label(packed_label);
+
+ // We ignore nodes without parents which are not roots.
+ if matches!(packed_query, Some(packed) if packed == root ||
+ self.parents_of(packed)?.len() > 0)
+ {
+ // this is safe because of the 'if' guard
+ let packed = packed_query.unwrap();
- if let Some(packed) = self.query_label(label) {
for child in self.children_of(packed)? {
let child_degree = self.degree(child)?;
@@ -457,9 +476,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
Ok(Eon::Nex(cloned_label))
} else {
- let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
+ let plain_query = self.query_label(plain_label);
+
+ if matches!(plain_query, Some(plain) if plain == root ||
+ self.parents_of(plain)?.len() > 0)
+ {
+ let existing = plain_query.unwrap();
- if let Some(existing) = self.query_label(plain_label) {
let existing_degree = self.degree(existing)?;
if self.has_same_children(existing, node, existing_degree, edge_index + 1)? {
@@ -622,7 +645,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
for parent in parents {
let mut parent_label = self
.vertex_label(parent)?
- .ok_or_else(|| Error::NodeNoLabel(parent))?
+ .ok_or(Error::NodeNoLabel(parent))?
.label();
#[cfg(debug_assertions)]
@@ -803,7 +826,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
for rule_parent in rule_parents {
let mut rule_parent_label = self
.vertex_label(rule_parent)?
- .ok_or_else(|| Error::NodeNoLabel(rule_parent))?
+ .ok_or(Error::NodeNoLabel(rule_parent))?
.label();
#[cfg(debug_assertions)]
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index bad0cfd..d5fb678 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -378,6 +378,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let reduced = self.reduction(nth_child, pos, ter, atom.borrow(), false)?;
+ // dbg!(reduced, nth_child, self.is_empty_node(reduced)?);
+
if reduced != nth_child && !self.is_empty_node(reduced)? {
parents.clear();
parents.extend(self.parents_of(reduced)?);
@@ -514,6 +516,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
if stack.is_empty() {
dbg!(
+ is_empty_segment,
label,
atom_child,
parents,
@@ -698,12 +701,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
Ok(nth_child)
}
}
- PaVi::Virtual(nt, t, mut node) => {
- let node_label_start = self
+ PaVi::Virtual(nt, t, node) => {
+ let node_label = self
.vertex_label(node)?
.ok_or(Error::NodeNoLabel(node))?
- .label()
- .start();
+ .label();
+
+ let node_label_start = node_label.start();
let reduction_fragment = atom.generate_virtual_frags(nt, t, None);
@@ -719,9 +723,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
for frag in reduction_fragment.into_iter().flatten() {
let mut frag = frag.clone();
- frag.set_pos(atom, node_label_start, true)?;
+ let _root_closed_p = frag.set_pos(atom, node_label_start, true)?;
+
+ // NOTE: If the root is closed, planting it might
+ // affect the original node, but we shall not deal
+ // with this phenomenon here.
+ //
+ // Instead, we will ignore the extra node at later
+ // stages.
- node = self.plant_at_start(node, frag)?;
+ self.plant_at_start(node, frag)?;
}
Ok(node)
diff --git a/chain/src/item/reduction.rs b/chain/src/item/reduction.rs
index 3c76c1e..512862a 100644
--- a/chain/src/item/reduction.rs
+++ b/chain/src/item/reduction.rs
@@ -139,6 +139,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
) -> Result<usize, Error> {
let mut result = node;
+ // if node == 15 && pos == 2 {
+ // let _ = self.print_viz("pos really before splone.gv");
+ // }
+
// step 1: Determine if this needs reductions.
if !accept_root && self.root() == Some(node) {
@@ -346,10 +350,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
panic!("a terminal node {top} has no ending position?");
}
Some(TNT::Non(nt)) => {
- correct_ends.insert(top, Correct);
-
self.close_pavi(atom.borrow(), PaVi::Virtual(nt, ter, top), pos)?;
+ // dbg!(top, nt, ter, pos, self.degree(top)?, degree);
+
+ let correctness = self.degree(top)? > 0;
+
+ correct_ends.insert(top, correctness.into());
+
continue 'stack_loop;
}
None => {
@@ -404,6 +412,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
// NOTE: We must fix the order from top to bottom: this is the
// reverse order of `order_of_correct_ends` .
+ // if node == 15 && pos == 2 {
+ // dbg!(&order_of_correct_ends);
+ // let _ = self.print_viz("pos before splone.gv");
+ // }
+
for node in order_of_correct_ends.into_iter().rev() {
let label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
let degree = self.degree(node)?;
@@ -421,6 +434,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let last_index = degree - 1;
+ // if node == 15 && pos == 2 {
+ // let _ = self.print_viz("before splone.gv");
+ // }
+
self.splone(node, Some(pos), last_index, false)?;
}