regast_core/

matcher.rs

use std::{fmt, sync::Arc};

use regast_syntax::Pattern;

use crate::{
    Backend, Disambiguation, IrKind, IrPool, Lowering, Value,
    antimirov::partial_derivative_at,
    deriv::{deriv_at, nullable_at},
    inj::inj_at,
    lower::lower,
    mkeps::mkeps_at,
    simp::simp,
    tagged_nfa::TaggedNfa,
    tree::ParseTree,
    value_parser::parse_ir_value,
};

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NoMatch {
    pub char_index: usize,
    pub at_end: bool,
}

impl fmt::Display for NoMatch {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.at_end {
            write!(formatter, "input ended before the pattern could match")
        } else {
            write!(
                formatter,
                "pattern cannot match at character {}",
                self.char_index
            )
        }
    }
}

impl std::error::Error for NoMatch {}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum MatchError {
    NoMatch(NoMatch),
    SizeLimitExceeded { limit: usize, states: usize },
}

impl fmt::Display for MatchError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::NoMatch(error) => error.fmt(formatter),
            Self::SizeLimitExceeded { limit, states } => write!(
                formatter,
                "matching state limit exceeded: {states} states (limit {limit})"
            ),
        }
    }
}

impl std::error::Error for MatchError {}

impl From<NoMatch> for MatchError {
    fn from(error: NoMatch) -> Self {
        Self::NoMatch(error)
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TraceStep {
    pub char_index: usize,
    pub c: char,
    pub before: String,
    pub after: String,
}

#[derive(Clone, Debug)]
pub struct Matcher {
    pattern: Arc<Pattern>,
    pool: IrPool,
    lowering: Lowering,
    disambiguation: Disambiguation,
    size_limit: usize,
    backend: Backend,
    tagged_nfa: Option<TaggedNfa>,
}

impl Matcher {
    #[must_use]
    pub fn new(pattern: Pattern, disambiguation: Disambiguation, size_limit: usize) -> Self {
        Self::new_with_backend(pattern, disambiguation, size_limit, Backend::Derivative)
    }

    #[must_use]
    pub fn new_with_backend(
        pattern: Pattern,
        disambiguation: Disambiguation,
        size_limit: usize,
        backend: Backend,
    ) -> Self {
        let mut pool = IrPool::new();
        let lowering = lower(&pattern, &mut pool, disambiguation);
        let tagged_nfa =
            (backend == Backend::TaggedNfa).then(|| TaggedNfa::compile(&pool, lowering.root));
        Self {
            pattern: Arc::new(pattern),
            pool,
            lowering,
            disambiguation,
            size_limit,
            backend,
            tagged_nfa,
        }
    }

    #[must_use]
    pub fn pattern(&self) -> &Pattern {
        &self.pattern
    }

    #[must_use]
    pub const fn disambiguation(&self) -> Disambiguation {
        self.disambiguation
    }

    #[must_use]
    pub fn lowering(&self) -> &Lowering {
        &self.lowering
    }

    #[must_use]
    pub fn pool(&self) -> &IrPool {
        &self.pool
    }

    /// Parse an entire input and reconstruct its typed IR value.
    ///
    /// # Errors
    ///
    /// Returns [`MatchError::NoMatch`] when the selected backend rejects the input, and
    /// [`MatchError::SizeLimitExceeded`] on recognition or value-reconstruction exhaustion.
    pub fn parse_value(&mut self, input: &str) -> Result<Value, MatchError> {
        self.parse_value_at(input, 0, input.len())
    }

    fn parse_value_at(
        &mut self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<Value, MatchError> {
        if self.backend == Backend::Derivative && self.disambiguation == Disambiguation::Posix {
            return self.parse_value_derivative_at(input, base, full_len);
        }
        let matched = match self.backend {
            Backend::Derivative => self.try_is_match_at(input, base, full_len)?,
            Backend::Antimirov => self.try_is_match_antimirov(input, base, full_len)?,
            Backend::TaggedNfa => self.try_is_match_tagged_nfa(input, base, full_len)?,
        };
        if !matched {
            return Err(NoMatch {
                char_index: input.chars().count(),
                at_end: true,
            }
            .into());
        }
        self.parse_value_direct_at(input, base, full_len)
    }

    fn parse_value_derivative_at(
        &mut self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<Value, MatchError> {
        let mut trace = Vec::with_capacity(input.chars().count());
        let mut root = self.lowering.root;
        for (index, (byte_offset, c)) in input.char_indices().enumerate() {
            let position = base + byte_offset;
            let derivative = deriv_at(&mut self.pool, root, c, position, full_len);
            let (simple, rect) = simp(&mut self.pool, derivative);
            trace.push((root, c, rect, position));
            root = simple;
            if root == self.pool.zero() {
                return Err(NoMatch {
                    char_index: index,
                    at_end: false,
                }
                .into());
            }
            if self.pool.len() > self.size_limit {
                return Err(MatchError::SizeLimitExceeded {
                    limit: self.size_limit,
                    states: self.pool.len(),
                });
            }
        }
        let final_position = base + input.len();
        let (final_root, final_rect) = simp(&mut self.pool, root);
        if !nullable_at(&mut self.pool, final_root, final_position, full_len) {
            return Err(NoMatch {
                char_index: input.chars().count(),
                at_end: true,
            }
            .into());
        }
        let final_value = mkeps_at(&mut self.pool, final_root, final_position, full_len);
        let mut value = self.pool.rect(final_rect).apply(&self.pool, final_value);
        for (previous, c, rect, position) in trace.into_iter().rev() {
            value = self.pool.rect(rect).apply(&self.pool, value);
            value = inj_at(&mut self.pool, previous, c, value, position, full_len);
        }
        debug_assert!(value.typed_by(&self.pool, self.lowering.root));
        debug_assert_eq!(value.flatten(), input);
        Ok(value)
    }

    fn parse_value_direct_at(
        &self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<Value, MatchError> {
        let value = parse_ir_value(
            &self.pool,
            self.lowering.root,
            input,
            base,
            full_len,
            self.disambiguation,
            self.size_limit,
        )
        .map_err(|states| MatchError::SizeLimitExceeded {
            limit: self.size_limit,
            states,
        })?
        .ok_or_else(|| {
            MatchError::from(NoMatch {
                char_index: input.chars().count(),
                at_end: true,
            })
        })?;
        debug_assert!(
            value.typed_by(&self.pool, self.lowering.root),
            "direct value {value:?} is not typed by {:?}",
            self.pool.kind(self.lowering.root)
        );
        debug_assert_eq!(value.flatten(), input);
        Ok(value)
    }

    /// Parse an entire input and expose the derivation in AST vocabulary.
    ///
    /// # Errors
    ///
    /// Returns [`MatchError::NoMatch`] if the entire input is not in the pattern's language, and
    /// [`MatchError::SizeLimitExceeded`] on resource exhaustion.
    pub fn parse(&mut self, input: &str) -> Result<ParseTree, MatchError> {
        let value = self.parse_value(input)?;
        Ok(ParseTree::build(
            Arc::clone(&self.pattern),
            &self.lowering,
            &self.pool,
            value,
            input,
            self.disambiguation,
        ))
    }

    /// Find and parse the leftmost-longest matching substring.
    ///
    /// # Errors
    ///
    /// Returns [`MatchError::SizeLimitExceeded`] if the matching-state limit is exceeded.
    pub fn find_parse(&mut self, input: &str) -> Result<Option<ParseTree>, MatchError> {
        let mut boundaries: Vec<_> = input.char_indices().map(|(index, _)| index).collect();
        boundaries.push(input.len());
        for &start in &boundaries {
            for &end in boundaries.iter().rev() {
                if end < start {
                    break;
                }
                let matched = &input[start..end];
                if !self.try_is_match_at(matched, start, input.len())? {
                    continue;
                }
                let value = match (self.backend, self.disambiguation) {
                    (Backend::Derivative, Disambiguation::Posix) => {
                        self.parse_value_derivative_at(matched, start, input.len())?
                    }
                    (Backend::Derivative, Disambiguation::Greedy)
                    | (Backend::Antimirov | Backend::TaggedNfa, _) => {
                        self.parse_value_direct_at(matched, start, input.len())?
                    }
                };
                return Ok(Some(ParseTree::build_at(
                    Arc::clone(&self.pattern),
                    &self.lowering,
                    &self.pool,
                    value,
                    matched,
                    input,
                    start,
                    self.disambiguation,
                )));
            }
        }
        Ok(None)
    }

    /// Check an entire input without discarding resource-limit failures.
    ///
    /// # Errors
    ///
    /// Returns [`MatchError::SizeLimitExceeded`] if the matching-state limit is exceeded.
    pub fn try_is_match(&mut self, input: &str) -> Result<bool, MatchError> {
        self.try_is_match_at(input, 0, input.len())
    }

    fn try_is_match_at(
        &mut self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<bool, MatchError> {
        match self.backend {
            Backend::Antimirov => return self.try_is_match_antimirov(input, base, full_len),
            Backend::TaggedNfa => return self.try_is_match_tagged_nfa(input, base, full_len),
            Backend::Derivative => {}
        }
        let mut root = self.lowering.root;
        for (byte_offset, c) in input.char_indices() {
            let derivative = deriv_at(&mut self.pool, root, c, base + byte_offset, full_len);
            root = simp(&mut self.pool, derivative).0;
            if matches!(self.pool.kind(root), IrKind::Zero) {
                return Ok(false);
            }
            if self.pool.len() > self.size_limit {
                return Err(MatchError::SizeLimitExceeded {
                    limit: self.size_limit,
                    states: self.pool.len(),
                });
            }
        }
        let final_root = simp(&mut self.pool, root).0;
        Ok(nullable_at(
            &mut self.pool,
            final_root,
            base + input.len(),
            full_len,
        ))
    }

    fn try_is_match_antimirov(
        &mut self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<bool, MatchError> {
        let mut states = vec![self.lowering.root];
        for (byte_offset, c) in input.char_indices() {
            let mut next = Vec::new();
            for state in states {
                next.extend(partial_derivative_at(
                    &mut self.pool,
                    state,
                    c,
                    base + byte_offset,
                    full_len,
                ));
            }
            next.sort_unstable_by_key(|state| state.index());
            next.dedup();
            if next.is_empty() {
                return Ok(false);
            }
            states = next;
            self.check_size_limit()?;
        }
        let position = base + input.len();
        Ok(states
            .into_iter()
            .any(|state| nullable_at(&mut self.pool, state, position, full_len)))
    }

    fn try_is_match_tagged_nfa(
        &self,
        input: &str,
        base: usize,
        full_len: usize,
    ) -> Result<bool, MatchError> {
        let nfa = self
            .tagged_nfa
            .as_ref()
            .expect("tagged NFA is compiled for its backend");
        let states = nfa.state_count();
        if states > self.size_limit {
            return Err(MatchError::SizeLimitExceeded {
                limit: self.size_limit,
                states,
            });
        }
        Ok(nfa.is_match(&self.pool, input, base, full_len))
    }

    fn check_size_limit(&self) -> Result<(), MatchError> {
        if self.pool.len() <= self.size_limit {
            return Ok(());
        }
        Err(MatchError::SizeLimitExceeded {
            limit: self.size_limit,
            states: self.pool.len(),
        })
    }

    pub fn is_match(&mut self, input: &str) -> bool {
        self.try_is_match(input).unwrap_or(false)
    }

    pub fn trace(&mut self, input: &str) -> Vec<TraceStep> {
        let mut result = Vec::new();
        let mut root = self.lowering.root;
        for (index, (byte_offset, c)) in input.char_indices().enumerate() {
            let before = self.pool.display(root);
            let derivative = deriv_at(&mut self.pool, root, c, byte_offset, input.len());
            root = simp(&mut self.pool, derivative).0;
            result.push(TraceStep {
                char_index: index,
                c,
                before,
                after: self.pool.display(root),
            });
        }
        result
    }
}

#[cfg(test)]
#[path = "matcher_tests.rs"]
mod tests;