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.rs257
-rw-r--r--chain/src/item/default/splone.rs7
2 files changed, 41 insertions, 223 deletions
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 6d28956..47e8c90 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -250,7 +250,12 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
frag_stack.pop();
self_stack.pop();
- if fragment.vertex_label(frag_top)? != self.vertex_label(self_top)? {
+ // NOTE: The labels might defer by the status. We test
+ // for the equalities of inner labels only.
+
+ if fragment.vertex_label(frag_top)?.map(|label| label.label())
+ != self.vertex_label(self_top)?.map(|label| label.label())
+ {
// not a prefix
// dbg!(
// frag_top,
@@ -589,11 +594,15 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
return Ok(node);
}
+ fragment.set_root(1)?;
+
let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
if node_label.is_packed() || node_label.clone_index().is_some() {
let mut planted = false;
+ let mut to_plant: Option<usize> = None;
+
let mut node = node;
if node_label.clone_index().is_some() {
@@ -607,17 +616,25 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
for clone in self.children_of(node)? {
node = clone;
- if self.is_prefix(clone, &fragment)? {
- planted = true;
+ if !self.is_empty_node(clone)? {
+ let first_child = self.nth_child(clone, 0)?;
+
+ if self.is_prefix(first_child, &fragment)? {
+ planted = true;
- break;
+ break;
+ }
+ } else if to_plant.is_none() {
+ to_plant = Some(clone);
}
}
if !planted {
- let clone = self.clone_node(node, 0, false)?;
-
- fragment.set_root(1)?;
+ let clone = if let Some(cloned_node) = to_plant {
+ cloned_node
+ } else {
+ self.clone_node(node, 0, false)?
+ };
self.plant(clone, fragment, false)?;
@@ -626,51 +643,29 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
} else {
let clone_threshold = if self.root == Some(node) { 1 } else { 0 };
- let planted = self.is_prefix(node, &fragment)?;
+ let satisfy_threshold = self.degree(node)? > clone_threshold;
- fragment.set_root(1)?;
+ if !satisfy_threshold {
+ self.plant(node, fragment, false)?;
- if !planted && self.degree(node)? > clone_threshold {
+ return Ok(node);
+ }
+
+ let first_child = self.nth_child(node, clone_threshold)?;
+
+ let planted = self.is_prefix(first_child, &fragment)?;
+
+ if !planted {
let clone = self.clone_node(node, 0, false)?;
self.plant(clone, fragment, false)?;
return Ok(clone);
- } else if !planted {
- self.plant(node, fragment, false)?;
}
}
Ok(node)
}
-
- /// Extract the node from `pavi`.
- ///
- /// If pavi is a parent, this returns the child pointed to by the
- /// represented edge.
- ///
- /// If pavi is a virtual node, this simply returns the virtual
- /// node.
- ///
- /// If pavi is empty, this returns the root, unless the forest is
- /// empty.
- ///
- /// # Guarantee
- ///
- /// The returned node is guaranteed to be a valid node.
- pub(crate) fn node_from_pavi(&self, pavi: PaVi) -> Result<usize, Error> {
- match pavi {
- PaVi::Parent(node, edge) => Ok(self.nth_child(node, edge)?),
- PaVi::Virtual(_, _, node) => {
- if node >= self.nodes_len() {
- return Err(Error::IndexOutOfBounds(node, self.nodes_len()));
- }
-
- Ok(node)
- }
- PaVi::Empty => Ok(self.root().ok_or(Error::IndexOutOfBounds(0, 0))?),
- }
- }
}
pub mod splone;
@@ -850,188 +845,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
Ok(None)
}
- // /// Check if every child already has an end.
- // fn every_child_is_completed(&self, node_id: usize, atom: &DefaultAtom) -> Result<bool, Error> {
- // let children = self.children_of(node_id)?;
-
- // if children.len() == 0 {
- // return Ok(true);
- // }
-
- // let mut pos = self
- // .vertex_label(node_id)?
- // .ok_or(Error::NodeNoLabel(node_id))?
- // .label()
- // .start();
-
- // let mut last_child_label = None;
-
- // for child in children {
- // let child_label = self
- // .vertex_label(child)?
- // .ok_or(Error::NodeNoLabel(child))?
- // .label();
-
- // last_child_label = Some(child_label);
-
- // if child_label.start() != pos || child_label.end().is_none() {
- // return Ok(false);
- // }
-
- // pos = child_label.end().unwrap();
- // }
-
- // if let Some(label) = last_child_label {
- // if let Some(rule) = label.label().rule() {
- // if !atom
- // .is_accepting(2 * rule + 1)
- // .map_err(|_| Error::IndexOutOfBounds(2 * rule + 1, atom.nodes_len()))?
- // {
- // return Ok(false);
- // }
- // }
- // }
-
- // Ok(true)
- // }
-
- // /// Complete the forest by trying to set the ending position of
- // /// every node that does not have an end, by the ending position
- // /// of its last child.
- // pub fn complete(&mut self, atom: &DefaultAtom) -> Result<(), Error> {
- // let mut stack: Vec<_> = self
- // .nodes()
- // .filter(|node| {
- // let label = self.vertex_label(*node).unwrap().unwrap().label();
-
- // label.label().rule().is_some() && label.end().is_some()
- // })
- // .collect();
-
- // let mut second_stack: Vec<usize> = Vec::new();
-
- // let mut pending_candidates: Vec<usize> = Vec::new();
-
- // let nodes_len = self.nodes_len();
-
- // let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(nodes_len);
-
- // while !stack.is_empty() {
- // while let Some(mut top) = stack.pop() {
- // if seen_nodes.contains(&top) {
- // continue;
- // }
-
- // seen_nodes.insert(top);
-
- // let top_label = self.vertex_label(top)?.unwrap();
-
- // if top_label.clone_index().is_some() {
- // let mut top_parents = self.parents_of(top)?;
-
- // if top_parents.len() != 1 {
- // return Err(Error::InvalidClone(top));
- // }
-
- // top = top_parents.next().unwrap().node();
- // }
-
- // let rule_parents = self.parents_of(top)?;
-
- // let candidates = {
- // let mut result = Vec::with_capacity(rule_parents.len());
-
- // for parent in rule_parents {
- // // for parent in self.parents_of(parent.node())? {
- // // if self.degree(parent.node())? <= parent.edge() + 1 {
- // result.push(parent);
- // // }
- // // }
- // }
-
- // result
- // };
-
- // for candidate in candidates {
- // if matches!(self.vertex_label(candidate.node())?, Some(label) if label.label().end().is_none())
- // {
- // if self.every_child_is_completed(candidate.node(), atom)? {
- // let last_child = self
- // .nth_child(candidate.node(), self.degree(candidate.node())? - 1)?;
- // let end = self
- // .vertex_label(last_child)?
- // .ok_or(Error::NodeNoLabel(last_child))?
- // .label()
- // .end();
-
- // let sploned_node = self.splone(
- // candidate.node(),
- // end,
- // self.degree(candidate.node())? - 1,
- // true,
- // )?;
-
- // second_stack.push(sploned_node);
- // } else {
- // pending_candidates.push(candidate.node());
- // }
- // } else {
- // second_stack.push(candidate.node());
- // }
- // }
-
- // let mut new_pending = Vec::with_capacity(pending_candidates.len());
-
- // while let Some(node) = pending_candidates.pop() {
- // if self.every_child_is_completed(node, atom)? {
- // let last_edge = self.degree(node)? - 1;
- // let last_child = self.nth_child(node, last_edge)?;
- // let end = self
- // .vertex_label(last_child)?
- // .ok_or(Error::NodeNoLabel(last_child))?
- // .label()
- // .end();
-
- // let sploned_node = self.splone(node, end, last_edge, true)?;
-
- // second_stack.push(sploned_node);
- // } else {
- // new_pending.push(node);
- // }
- // }
-
- // std::mem::swap(&mut pending_candidates, &mut new_pending);
- // }
-
- // std::mem::swap(&mut stack, &mut second_stack);
- // }
-
- // Ok(())
- // }
-
- // /// Unconditionally set the label of the node to be the new label.
- // ///
- // /// # Warning
- // ///
- // /// Use with caution: it does not do anything special, so it is
- // /// the responsibility of the caller to ensure this operation is
- // /// legal.
- // #[allow(dead_code)]
- // pub(crate) fn set_label(&mut self, node: usize, label: GrammarLabel) -> Result<(), Error> {
- // let status = self
- // .vertex_label(node)?
- // .ok_or(Error::NodeNoLabel(node))?
- // .status;
-
- // let label = ForestLabel::new(label, status);
-
- // let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
-
- // builder.set_label(node, label)?;
-
- // Ok(())
- // }
-
/// Set the position of every node.
///
/// If ALLP is non-nil or if the node is a terminal node, also set
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index d77686e..581d1dc 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -555,7 +555,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let modified_degree = std::cmp::max(existing_degree, 1) - 1;
if existing_degree != 0
- && self.has_same_children(existing, node, modified_degree, edge_index)?
+ && self.has_same_children(
+ existing,
+ node,
+ modified_degree,
+ edge_index + 1,
+ )?
{
let last_child = self.nth_child(existing, existing_degree - 1)?;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 22:21:43 +0000