summaryrefslogtreecommitdiff
path: root/chain/src/item/default
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/item/default')
-rw-r--r--chain/src/item/default/mod.rs122
-rw-r--r--chain/src/item/default/splone.rs37
2 files changed, 145 insertions, 14 deletions
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)]