From fbaa420ed550e9c3e7cdc09d4a8ec22bfbd782a6 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 27 Feb 2023 12:36:41 +0800 Subject: before a major refactor I decide to adopt a new approach of recording and updating item derivation forests. Since this affects a lot of things, I decide to commit before the refactor, so that I can create a branch for that refactor. --- chain/src/atom/default.rs | 226 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 211 insertions(+), 15 deletions(-) (limited to 'chain/src/atom/default.rs') diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs index ec53596..a55087a 100644 --- a/chain/src/atom/default.rs +++ b/chain/src/atom/default.rs @@ -2,18 +2,24 @@ //! [`Atom`][super::Atom] trait. use super::*; -use grammar::Grammar; +use grammar::{Grammar, GrammarLabel, GrammarLabelType}; use graph::{error::Error as GraphError, Graph, LabelExtGraph, LabelGraph}; use nfa::{ default::{nfa::DefaultNFA, regex::DefaultRegex}, + error::Error as NFAError, LabelType, NfaLabel, }; use core::fmt::Display; -use std::collections::BTreeMap as Map; +use std::{ + collections::{hash_set::Iter, BTreeMap as Map, HashMap, HashSet}, + iter::Copied, +}; + +use crate::item::{default::DefaultForest, ForestLabel}; /// A virtual node represents the derivative of a non-terminal symbol -/// `S` with respect to a terminal symbol `t`. +/// `s` with respect to a terminal symbol `t`. #[derive(Debug, Clone, Copy, Eq, PartialEq, Hash, Ord, PartialOrd)] struct VirtualNode { s: usize, @@ -34,6 +40,33 @@ impl VirtualNode { type VirtualMap = Map; +/// A virtual trace stores the rule positions that are responsible for +/// an edge from the virtual node \[nt\]^s to `target`. +#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash, Ord, PartialOrd)] +struct VirtualTrace { + nt: usize, + t: usize, + target: usize, +} + +impl Display for VirtualTrace { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "VT[{}]^({}) -> {}", self.nt, self.t, self.target) + } +} + +impl VirtualTrace { + fn new(nt: usize, t: usize, target: usize) -> Self { + Self { nt, t, target } + } +} + +type VirtualTraceMap = Map>; + +type VirtualFrag = DefaultForest>; + +type VirtualFragMap = Map>; + /// The type of atomic languages. #[derive(Debug, Clone, Default)] pub struct DefaultAtom { @@ -43,6 +76,8 @@ pub struct DefaultAtom { // NOTE: This is mostly for printing and debugging regexp: Vec>, virtual_nodes: VirtualMap, + virtual_traces: VirtualTraceMap, + virtual_frags: VirtualFragMap, } impl DefaultAtom { @@ -260,9 +295,9 @@ impl Nfa> for DefaultAtom { #[inline] fn to_nfa( _regexps: &[impl nfa::Regex>>], - _sub_pred: impl Fn(LabelType) -> Result>, nfa::error::Error>, + _sub_pred: impl Fn(LabelType) -> Result>, NFAError>, _default: Option>, - ) -> Result>>, nfa::error::Error> { + ) -> Result>>, NFAError> { // NOTE: We cannot construct an atom from a set of regular // languages alone. So it is appropriate to panic here, if // one tries to do so, for some reason. @@ -270,7 +305,7 @@ impl Nfa> for DefaultAtom { } #[inline] - fn remove_dead(&mut self, reserve: impl FnMut(usize) -> bool) -> Result<(), nfa::error::Error> { + fn remove_dead(&mut self, reserve: impl FnMut(usize) -> bool) -> Result<(), NFAError> { self.nfa.remove_dead(reserve) } @@ -281,7 +316,7 @@ impl Nfa> for DefaultAtom { remove_after_p: bool, transform: impl FnMut(nfa::TwoEdges>) -> LabelType, remove_predicate: impl FnMut(LabelType) -> bool, - ) -> Result<(), nfa::error::Error> { + ) -> Result<(), NFAError> { self.nfa .closure(predicate, remove_after_p, transform, remove_predicate) } @@ -296,8 +331,6 @@ impl DefaultAtom { let mut nfa = grammar.left_closure_to_nfa(®exp)?; - use std::collections::{HashMap, HashSet}; - let accumulators: Vec = { let mut result = Vec::with_capacity(regexp.len() + 1); result.push(0); @@ -388,6 +421,12 @@ impl DefaultAtom { // Now add the virtual nodes. let mut virtual_nodes: VirtualMap = Default::default(); + // Record virtual traces. + let mut virtual_traces: VirtualTraceMap = Default::default(); + + // Record virtual fragments. + let mut virtual_frags: VirtualFragMap = Default::default(); + let nt_num = grammar.non_num(); assert!(nt_num <= accumulators.len()); @@ -403,19 +442,35 @@ impl DefaultAtom { GraphError::IndexOutOfBounds(index, bound) => { GrammarError::IndexOutOfBounds(index, bound) } - _ => unreachable!(), + // This is supposed to be unreachable, but we still + // give it a valid value. + _ => GrammarError::NFAFail(NFAError::Graph(ge)), } } for nt in 0..nt_num { + // This is safe because of the above assertion. + let nt_start = *accumulators.get(nt).unwrap(); + let children: std::collections::HashMap<_, _> = nfa - // This is safe because of the above assertion. - .labels_of(*accumulators.get(nt).unwrap()) + .labels_of(nt_start) .map_err(index_out_of_bounds_conversion)? .map(|(label, target_iter)| (*label, target_iter)) .collect(); - type TerminalsValue = (HashSet<(LabelType, usize, Option>)>, bool); + /// The tuples have the following meanings in order: + /// + /// - `LabelType` => the label for the edge + /// + /// - `usize` => the target of the edge + /// + /// - `Option>` => reduction information + /// + /// - `usize` => the rule position that caused this edge + type TerminalsValue = ( + HashSet<(LabelType, usize, Option>, usize)>, + bool, + ); let mut terminals_map: HashMap = HashMap::new(); @@ -431,9 +486,72 @@ impl DefaultAtom { result }; + let virtual_trace = label.get_moved(); + let mut accepting = false; for child in children_iter { + // add a virtual fragment + + let line: Vec = grammar + .query_expansion(nt_start, child)? + .iter() + .copied() + .flatten() + .flat_map(|(nt, rule)| [(*rule).into(), TNT::Non(*nt).into()]) + .rev() + .chain(std::iter::once(TNT::Ter(t).into())) + .collect(); + + assert!(line.len() > 1); + + // by our construction this must be a rule + let rule = line.get(line.len() - 2).unwrap().rule().unwrap(); + + use crate::default::Error as DError; + + let frag = crate::item::genins::generate_fragment(line, 0).map_err( + |fe: DError| -> GrammarError { + match fe { + DError::IndexOutOfBounds(index, bound) => { + GrammarError::IndexOutOfBounds(index, bound) + } + DError::DuplicateNode(n) => GrammarError::NFAFail( + NFAError::Graph(GraphError::DuplicatedNode(n)), + ), + DError::DuplicateEdge(source, target) => GrammarError::NFAFail( + NFAError::Graph(GraphError::DuplicatedEdge(source, target)), + ), + DError::NodeNoLabel(n) => { + panic!("node {n} has no label!") + } + DError::CannotReserve(_) => unreachable!( + "generate_fragment should not signal this error" + ), + DError::CannotClone(_) => { + unreachable!("we are not cloning") + } + DError::CannotPlant => { + unreachable!("why can we not plant?") + } + DError::SplitPack(_) => { + unreachable!("we not not splitting") + } + DError::InvalidClone(_) => { + unreachable!("we are not cloning") + } + DError::Invalid => { + panic!("a label is wrongly planted?") + } + } + }, + )?; + + virtual_frags + .entry(VirtualNode::new(nt, t)) + .or_insert_with(Default::default) + .insert(rule, frag); + accepting = accepting || *accepting_vec.get(child).ok_or( @@ -462,6 +580,7 @@ impl DefaultAtom { .query_reduction(child, target) .unwrap() .map(|slice| slice.to_vec()), + virtual_trace, ) })); } @@ -470,8 +589,21 @@ impl DefaultAtom { } for (t, (set, accepting)) in terminals_map.into_iter() { + // update virtual traces + + for (_, target, _, pos) in set.iter() { + let trace = VirtualTrace::new(nt, t, *target); + + virtual_traces + .entry(trace) + .or_insert_with(Default::default) + .insert(*pos); + } + + // add a virtual node + let new_index = nfa - .extend(set.iter().map(|(label, target, _)| (*label, *target))) + .extend(set.iter().map(|(label, target, _, _)| (*label, *target))) .map_err(index_out_of_bounds_conversion)?; if accepting_vec.get(new_index).is_none() { @@ -486,7 +618,7 @@ impl DefaultAtom { virtual_nodes.insert(virtual_node, new_index); // update the reduction information - for (_, target, info) in set.into_iter() { + for (_, target, info, _) in set { if let Some(info) = info { if !matches!( grammar.query_reduction(new_index, target)?, @@ -507,8 +639,60 @@ impl DefaultAtom { regexp, virtual_nodes, accepting_vec, + virtual_traces, + virtual_frags, }) } + + /// Generate a vector of virtual fragments for a non-terminal and + /// a terminal. + /// + /// # RULE + /// + /// If one passes `Some(rule)` as the paramter, then this returns + /// only those fragments that begin with the specified rule. + /// + /// On the other hand, if one passes `None`, then this returns + /// only those fragments that can end the non-terminal expansion. + /// + /// # Guarantee + /// + /// It is guaranteed that the 1-th node of each fragment is a rule + /// number. + pub(crate) fn generate_virtual_frags( + &self, + nt: usize, + t: usize, + rule: Option, + ) -> Option> { + let vn = VirtualNode::new(nt, t); + + if let Some(rule) = rule { + self.virtual_frags + .get(&vn) + .and_then(|map| map.get(&rule)) + .map(|f| vec![f]) + } else { + let result: Vec<&VirtualFrag> = self + .virtual_frags + .get(&vn) + .iter() + .copied() + .flatten() + .filter_map(|(rule, frag)| { + self.is_accepting(rule * 2 + 1) + .unwrap_or(false) + .then_some(frag) + }) + .collect(); + + if result.is_empty() { + None + } else { + Some(result) + } + } + } } /// A convenient getter for the map of virtual nodes. @@ -550,4 +734,16 @@ impl Atom for DefaultAtom { self.accepting_vec.len(), )) } + + type Iter<'a> = Copied> + where + Self: 'a; + + fn trace(&self, nt: usize, t: usize, target: usize) -> Option<::Iter<'_>> { + let trace = VirtualTrace::new(nt, t, target); + + self.virtual_traces + .get(&trace) + .map(|set| set.iter().copied()) + } } -- cgit v1.2.3-18-g5258