brzozowski_regex/

lib.rs

// Copyright 2024 Hendrik van Antwerpen
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! A regular expression library over sequences of arbitrary symbols, based on
//! the regular expression derivatives of Brzozowski (1964). The implementation
//! is is heavily based on the description by Owens et al (2009).
//!
//! Regular expressions can be defined over any alphabet type that implements the
//! traits `Clone`, `Eq`, `Hash`, and `Ord`. The following constructs are supported:
//!
//!  - The empty set `∅`
//!  - The empty string `ε`
//!  - A symbol _s_
//!  - Concatenation `R S`
//!  - Closure `R*`
//!  - Disjunction `R | S`
//!  - Conjunction `R & R`
//!  - Complement `¬R`
//!
//! ## Constructing regular expressions
//!
//! Regular expressions can be constructed using builder methods or, more conveniently,
//! using short-hands.
//!
//! An example using builder methods:
//!
//! ```
//! use brzozowski_regex::Regex;
//!
//! let r = Regex::and(
//!     Regex::complement(Regex::empty_set()),
//!     Regex::concat(
//!         Regex::concat(
//!           Regex::closure(Regex::symbol(5)),
//!           Regex::symbol(7),
//!         ),
//!         Regex::or(Regex::empty_string(), Regex::symbol(11)),
//!     ),
//! );
//! ```
//!
//! Constructing regular expression susing these builder methods can be quite verbose.
//! A set of short-hands is available to write regular expression literals more compactly:
//!
//!  - `EXPR.s()` builds a symbol from the expressions value.
//!  - `().r()` builds an empty set.
//!  - `[ REGEX* ].r()` builds a concatenation from the given regular expressions. If
//!    the array is empty, it builds the empty string.
//!  - `REGEX.c()` build the closure of the given regular expression.
//!
//! Additionally, the following operations are overloaded for regular expressions:
//!
//!  - `REGEX + REGEX` builds the concatenation of the two given regular expressions.
//!  - `REGEX | REGEX` builds the logical _or_ of the two given regular expressions.
//!  - `REGEX & REGEX` builds the logical _and_ of the two given regular expressions.
//!  - `!REGEX` builds the complement of the given regular expression.
//!
//! The same example using short-hands and operators:
//!
//! ```
//! use brzozowski_regex::syntax::*; // imports short-hands
//! use brzozowski_regex::Regex;
//!
//! let r = !().r() & [ 5.s().c(), 7.s(), ([].r() | 11.s()) ].r();
//! ```
//!
//! ## Matching with automata
//!
//! The recommended way to match regular expressions is to turn them into an automaton.
//! One can either match a whole sequence of symbols at once against the automaton, or
//! create a matcher for incremental matching.
//!
//! Matching a whole sequence at once works as follows:
//!
//! ```
//! use brzozowski_regex::syntax::*; // import short-hands
//! use brzozowski_regex::Regex;
//!
//! let r = !().r() & [ 5.s().c(), 7.s(), ([].r() | 11.s()) ].r();
//! let a = r.to_automaton();
//! assert!(a.matches([5, 5, 7, 11]));
//! ```
//!
//! Using a matcher allows for incremental matching. After matching a symbol or
//! sequence of symbols the matcher returns one of the following results:
//!
//!  - _accept_: the sequence until now matches the regular expression
//!  - _may-accept_: the sequence is not a match, but adding more symbols may
//!    lead to an accept.
//!  - _reject_: the sequence is not a match, and adding more symbols will not
//!    change that.
//!
//! The matcher can also return the current residual regular expression.
//!
//! A matcher is used as follows:
//!
//! ```
//! use brzozowski_regex::syntax::*; // import short-hands
//! use brzozowski_regex::Acceptance;
//! use brzozowski_regex::Regex;
//!
//! let r = !().r() & [ 5.s().c(), 7.s(), ([].r() | 11.s()) ].r();
//! let a = r.to_automaton();
//! let mut m = a.to_matcher();
//! assert_eq!(Acceptance::MayAccept, m.next(&5));
//! assert_eq!(Acceptance::Accept, m.next_iter([5, 7]));
//! assert_eq!(&(11.s() | [].r()), m.regex());
//! assert_eq!(Acceptance::Reject, m.next(&13));
//! ```
//!
//! ## Directly working with derivatives
//!
//! It is also possible to run operations on regular expressions directly, such as
//! testing for nullability, computing the derivative w.r.t. a symbol or a sequence
//! of symbols, and matching a sequence of symbols.  _Note that matching directly
//! against regular expression value is very inefficient compared to constructing an
//! automaton first!_
//!
//! Examples of operation on regular expression values:
//!
//! ```
//! use brzozowski_regex::syntax::*; // import short-hands
//! use brzozowski_regex::Regex;
//!
//! let r = [7.s(), 11.s().c()].r();
//! assert!(r.matches([7, 11]));
//!
//! let s = r.derive(&7);
//! assert!(s.is_nullable());
//!
//! let s = s.derive_iter([11, 13]);
//! assert!(!s.is_nullable());
//! ```
//!
//! ## References
//!
//!  - Brzozowski, Janusz A. “Derivatives of Regular Expressions.” J. ACM 11, no. 4 (October 1964): 481–94. <https://doi.org/10.1145/321239.321249>.
//!  - Owens, Scott, John Reppy, and Aaron Turon. “Regular-Expression Derivatives Re-Examined.” Journal of Functional Programming 19, no. 2 (March 2009): 173–90. <https://doi.org/10.1017/S0956796808007090>.

use std::hash::Hash;

mod automaton;
pub mod builder;
mod derivation;
mod display;
mod nullability;
mod ops;

/// Trait describing types that can be used as an alphabet for regular expression
/// queries.
pub trait Alphabet: Clone + Eq + Hash + Ord {}

impl<S> Alphabet for S where S: Clone + Eq + Hash + Ord {}

/// Regular expressions over symbols of the given alphabet.
pub type Regex<S> = builder::Regex<builder::Default<S>>;

#[doc(inline)]
pub use automaton::Acceptance;
#[doc(inline)]
pub use automaton::FiniteAutomaton;
#[doc(inline)]
pub use automaton::Matcher;

pub mod syntax {
    //! Short-hand syntax for writing regular expression literals.

    use super::*;

    pub trait IntoRegex<S: Alphabet> {
        fn r(self) -> Regex<S>;
    }

    impl<S: Alphabet, T> IntoRegex<S> for T
    where
        T: ops::IntoRegex<builder::Default<S>>,
    {
        fn r(self) -> Regex<S> {
            <Self as ops::IntoRegex<builder::Default<S>>>::r(self)
        }
    }

    pub trait IntoSymbol<S: Alphabet> {
        fn s(self) -> Regex<S>;
    }

    impl<S: Alphabet, T> IntoSymbol<S> for T
    where
        T: ops::IntoSymbol<builder::Default<S>>,
    {
        fn s(self) -> Regex<S> {
            <Self as ops::IntoSymbol<builder::Default<S>>>::s(self)
        }
    }

    pub trait IntoClosure<S: Alphabet> {
        fn c(self) -> Regex<S>;
    }

    impl<S: Alphabet, T> IntoClosure<S> for T
    where
        T: ops::IntoClosure<builder::Default<S>>,
    {
        fn c(self) -> Regex<S> {
            <Self as ops::IntoClosure<builder::Default<S>>>::c(self)
        }
    }
}