use crate::PatternTypes; use crate::Predicate; use crate::errors::MatchError; use std::collections::BTreeMap; use std::marker::PhantomData; pub(crate) const MAX_CALLS: usize = 250; type Matches<'a, 'b, T> = BTreeMap<&'a str, (&'b ::Value, &'b ::Value)>; // TODO: use a builder for this? /// The constant pool for a pattern. pub(crate) struct PatternConstants { // last proto is implicitly the whole pattern. pub(crate) protos: Vec>>, // Note that we can borrow these when creating the output map. // https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=da26f9175e96273fa0b94971a4e6172f pub(crate) strings: Vec, pub(crate) regices: Vec<()/* TODO */>, pub(crate) predicates: Vec>>, // NOTE these are part of the constant pool and so have lifetime analogous // to 'a (consistently used to indicate constant pool lifetime) when used // elsewhere. In particular, they can't be yielded by the iterator. pub(crate) defs: Vec, } /// A pattern element. pub(crate) enum PatternElement { Arrow, Identifier(usize), StringKey(usize, bool), RegexKey(usize, bool), ParameterKey(usize, bool), KeySubtree(usize, bool), ValueSubtree(usize, bool), ApplyPredicate(usize, bool, PhantomData) -> &Predicate>), End } impl Copy for PatternElement {} impl Clone for PatternElement { fn clone(&self) -> Self { *self } } struct Frame<'a, 'b, T: PatternTypes> { obj: &'b T::Value, ops: &'a Vec>, iar: Option, depth: usize, path: Vec>, in_key: bool, } impl<'a, 'b, T: PatternTypes> Frame<'a, 'b, T> { /// Advances the instruction address register. /// /// # Returns /// /// `true` if successful, `false` otherwise. fn next(&mut self) -> bool { let new = self.iar.map_or(0, |v| v + 1); new < self.ops.len() && { self.iar = Some(new); true } } /// Returns the current instruction. fn op(&self) -> PatternElement { self.ops[self.iar.expect("ops[iar]")] } /// Rewinds the instruction address register. /// /// # Returns /// /// `true` if successful, `false` otherwise. fn prev(&mut self) -> bool { let new = self.iar.expect("iar").checked_sub(1); new.is_some() && { self.iar = new; true } } } /// Stores a single match. /// /// See also Holder. enum HolderState<'a, 'b, T: PatternTypes> { EmptyKey, EmptySubtree, Key((&'b T::Value, &'b T::Value)), Subtree(Matches<'a, 'b, T>, &'b T::Value), } impl<'a, 'b, T: PatternTypes> Clone for HolderState<'a, 'b, T> { fn clone(&self) -> Self { match self { HolderState::EmptyKey => HolderState::EmptyKey, HolderState::EmptySubtree => HolderState::EmptySubtree, HolderState::Key(v) => HolderState::Key(*v), HolderState::Subtree(m, v) => HolderState::Subtree(m.clone(), *v), } } } impl<'a, 'b, T: PatternTypes> HolderState<'a, 'b, T> { fn is_empty(&self) -> bool { matches!(self, HolderState::EmptyKey | HolderState::EmptySubtree) } fn is_subtree(&self) -> bool { matches!(self, HolderState::EmptySubtree | HolderState::Subtree {..}) } fn value(&self) -> Option<&'b T::Value> { match self { HolderState::Key((_, value)) => Some(value), HolderState::Subtree(_, value) => Some(value), _ => None } } } /// Stores a single match and associated metadata. /// /// A single match is generally a key-value pair, but may be a collection of /// named pairs in the case of subtree matches. struct Holder<'a, 'b, T: PatternTypes> { name: Option<&'a str>, value: HolderState<'a, 'b, T>, parent: Option<&'b T::Value>, iterator: Box + 'b>, filters: Vec Fn(&'c mut HolderState<'a, 'b, T>) + 'a>>, } impl<'a, 'b, T: PatternTypes> Holder<'a, 'b, T> { fn next(&mut self) -> Option> { if let Self { value: ref mut v, iterator: ref mut it, .. } = self { let is_subtree = v.is_subtree(); *v = match it.next() { Some(pair) => HolderState::Key(pair), None => return None }; // just try to make sure the type doesn't change. // (and that if we get to this point the result isn't empty.) assert!(!v.is_empty() && v.is_subtree() == is_subtree); } Some(Ok(())) } } impl<'a, 'b, T: PatternTypes> Default for Holder<'a, 'b, T> { fn default() -> Self { Self { name: Default::default(), value: HolderState::EmptyKey, parent: Default::default(), // TODO https://github.com/rust-lang/rfcs/issues/3059 iterator: Box::new(std::iter::empty()), filters: Default::default(), } } } pub struct Matcher<'a, 'b, T: PatternTypes> { defs: &'a PatternConstants, frame: Frame<'a, 'b, T>, } impl<'a, 'b, T: PatternTypes> Matcher<'a, 'b, T> { pub(crate) fn new(obj: &'b T::Value, defs: &'a PatternConstants, proto: usize, rlimit: usize) -> Result { let depth = rlimit.checked_sub(1).ok_or(MatchError::StackOverflow)?; let ops: &Vec<_> = &defs.protos[proto]; Ok(Self { defs: defs, frame: Frame { obj: obj, ops: ops, iar: None, depth: depth, path: if ops.is_empty() { Default::default() } else { vec![Holder::default()] }, in_key: false, }, }) } fn on_in_key(&mut self) -> Result { match self.frame.op() { PatternElement::End => { unimplemented!() } _ => unreachable!("on_in_key") } } fn on_not_in_key(&mut self) -> Result { match self.frame.op() { _ => unreachable!("on_not_in_key") } } fn on_end(&mut self) -> Result<(bool, Matches<'a, 'b, T>), MatchError> { match self.frame.op() { PatternElement::End => { assert!(!self.frame.path.last().expect("path").value.is_empty()); // TODO this for loop is duplicated with ApplyPredicate // TODO figure out how to deduplicate them let mut res: Matches<'a, 'b, T> = Default::default(); for holder in &self.frame.path { match holder.value { HolderState::Subtree(ref matches, _) => { res.extend(matches); }, HolderState::Key(pair) => { if let Some(name) = holder.name { res.insert(name, pair); } }, _ => unreachable!("on_end (End)"), } } if !self.frame.prev() { // frame.prev() should always be called, even if this gets // replaced with debug_assert!(). assert!(false, "frame.prev()"); } Ok((true, res)) }, PatternElement::ApplyPredicate {..} => { assert!(!self.frame.in_key); let mut res: Matches<'a, 'b, T> = Default::default(); for holder in &self.frame.path { match holder.value { HolderState::Subtree(ref matches, _) => { res.extend(matches); }, HolderState::Key(pair) => { if let Some(name) = holder.name { res.insert(name, pair); } }, _ => unreachable!("on_end (ApplyPredicate)"), } } self.frame.path.clear(); Ok((false, res)) } _ => unreachable!("on_end") } } } impl<'a, 'b, T: PatternTypes> Iterator for Matcher<'a, 'b, T> { type Item = Result, MatchError>; fn next(&mut self) -> Option { while !self.frame.path.is_empty() { if !self.frame.next() { let (in_key, res) = match self.on_end() { Ok(v) => v, Err(e) => { self.frame.path.clear(); return Some(Err(e)) }, }; self.frame.in_key = in_key; return Some(Ok(res)); } else { let in_key = if self.frame.in_key { self.on_in_key() } else { self.on_not_in_key() }; match in_key { Ok(in_key) => self.frame.in_key = in_key, Err(e) => { self.frame.path.clear(); return Some(Err(e)) }, } } } None } }