rexact_core/

language.rs

//! The user-facing handle: a compiled language with matching, minimal
//! automaton and fingerprint.

use crate::alphabet::Alphabet;
use crate::dfa::{Dfa, MinDfa};
use crate::limits::{Budget, Limits};
use crate::lower::Lower;
use crate::term::{TermId, TermStore};
use rexact_syntax::error::{ErrorCode, RexactError};
use rexact_syntax::Pattern;

/// Full: the pattern must match the entire input. Search: any substring may
/// match (FR-A11).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
    /// Whole-input match.
    Full,
    /// Match anywhere.
    Search,
}

/// A pattern compiled to a term and a lazily built automaton.
pub struct Language {
    store: TermStore,
    dfa: Dfa,
    root: TermId,
    alphabet: Alphabet,
    limits: Limits,
}

fn limit(code: ErrorCode) -> RexactError {
    RexactError::new(code)
}

impl Language {
    /// Compile a parsed pattern. `alphabet` defaults per dialect.
    pub fn compile(
        p: &Pattern,
        alphabet: Option<Alphabet>,
        mode: Mode,
        limits: &Limits,
    ) -> Result<Language, RexactError> {
        let alphabet = alphabet.unwrap_or_else(|| Alphabet::default_for(p.dialect, p.flags));
        let mut store = TermStore::new(alphabet.universe());
        let root = lower_into(&mut store, p, alphabet, mode, limits)?;
        Self::from_parts(store, root, alphabet, limits)
    }

    /// Wrap an existing term (used by the analyses and by tests).
    pub fn from_parts(
        mut store: TermStore,
        root: TermId,
        alphabet: Alphabet,
        limits: &Limits,
    ) -> Result<Language, RexactError> {
        let mut budget = Budget::new(limits.clone());
        let dfa = Dfa::new(&mut store, root, alphabet.name(), &mut budget).map_err(limit)?;
        Ok(Language {
            store,
            dfa,
            root,
            alphabet,
            limits: limits.clone(),
        })
    }

    /// The alphabet mode, reported with every result.
    pub fn alphabet(&self) -> Alphabet {
        self.alphabet
    }
    /// The root term.
    pub fn root(&self) -> TermId {
        self.root
    }
    /// The term store (read-only).
    pub fn store(&self) -> &TermStore {
        &self.store
    }

    /// Full-match test on text, encoded per the alphabet mode.
    pub fn matches(&mut self, input: &str) -> Result<bool, RexactError> {
        let units = self.alphabet.encode(input);
        self.matches_units(&units)
    }

    /// Full-match test on symbols.
    pub fn matches_units(&mut self, input: &[u32]) -> Result<bool, RexactError> {
        let mut budget = Budget::new(self.limits.clone());
        self.dfa
            .matches(&mut self.store, input, &mut budget)
            .map_err(limit)
    }

    /// Minimal complete automaton in canonical form.
    pub fn minimal(&mut self) -> Result<MinDfa, RexactError> {
        let mut budget = Budget::new(self.limits.clone());
        self.dfa
            .minimize(&mut self.store, &mut budget)
            .map_err(limit)
    }

    /// Language fingerprint: equal for equal languages in the same alphabet.
    pub fn fingerprint(&mut self) -> Result<String, RexactError> {
        Ok(self.minimal()?.fingerprint())
    }

    /// (states built so far, symbol classes).
    pub fn stats(&self) -> (usize, usize) {
        (self.dfa.num_states(), self.dfa.num_classes())
    }
}

/// Fingerprint of a term that lives in a caller-owned store. Equal results
/// mean equal languages over `alphabet` (the canonical form is the authority;
/// see [`MinDfa::canonical_form`]).
pub fn fingerprint_term(
    store: &mut TermStore,
    root: TermId,
    alphabet: Alphabet,
    limits: &Limits,
) -> Result<String, RexactError> {
    let mut budget = Budget::new(limits.clone());
    let mut dfa = Dfa::new(store, root, alphabet.name(), &mut budget).map_err(limit)?;
    Ok(dfa
        .minimize(store, &mut budget)
        .map_err(limit)?
        .fingerprint())
}

/// Lower a pattern into an existing store, so several patterns can be analysed
/// together (equivalence, comparison). `store` must have been created with
/// `alphabet.universe()`.
pub fn lower_into(
    store: &mut TermStore,
    p: &Pattern,
    alphabet: Alphabet,
    mode: Mode,
    limits: &Limits,
) -> Result<TermId, RexactError> {
    let mut budget = Budget::new(limits.clone());
    budget
        .check_length(p.source.chars().count() as u64)
        .map_err(limit)?;
    let (term, _) = {
        let mut l = Lower {
            store,
            alphabet,
            dialect: p.dialect,
            chars: p.source.chars().collect(),
            budget: &mut budget,
        };
        l.pattern(p)?
    };
    Ok(match mode {
        Mode::Full => term,
        Mode::Search => {
            let any = store.any_symbol();
            let all = store.star(any);
            store.concat_all(&[all, term, all])
        }
    })
}

/// Minimal automaton of a term that lives in a caller-owned store.
pub fn minimal_of_term(
    store: &mut TermStore,
    root: TermId,
    alphabet: Alphabet,
    limits: &Limits,
) -> Result<crate::dfa::MinDfa, RexactError> {
    let mut budget = Budget::new(limits.clone());
    let mut dfa = Dfa::new(store, root, alphabet.name(), &mut budget).map_err(limit)?;
    dfa.minimize(store, &mut budget).map_err(limit)
}

/// A pattern resolved for backtracking analysis, with the store its
/// zero-width terms live in.
pub struct Resolved {
    /// The tree.
    pub root: crate::resolved::RNode,
    /// Store holding assertion terms.
    pub store: TermStore,
    /// Alphabet mode in force.
    pub alphabet: Alphabet,
}

/// Resolve `p` for analysis (does not build any automaton).
pub fn resolve(
    p: &Pattern,
    alphabet: Option<Alphabet>,
    limits: &Limits,
) -> Result<Resolved, RexactError> {
    let alphabet = alphabet.unwrap_or_else(|| Alphabet::default_for(p.dialect, p.flags));
    let mut store = TermStore::new(alphabet.universe());
    let mut budget = Budget::new(limits.clone());
    budget
        .check_length(p.source.chars().count() as u64)
        .map_err(limit)?;
    let root = {
        let mut l = Lower {
            store: &mut store,
            alphabet,
            dialect: p.dialect,
            chars: p.source.chars().collect(),
            budget: &mut budget,
        };
        l.resolve_pattern(p)?
    };
    Ok(Resolved {
        root,
        store,
        alphabet,
    })
}