#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Error {
pub message: &'static str,
pub unimplemented: bool,
}
impl Error {
pub(super) fn at(message: &'static str) -> Self {
Self {
message,
unimplemented: false,
}
}
pub(super) fn unsupported(message: &'static str) -> Self {
Self {
message,
unimplemented: true,
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Flags {
pub indices: bool,
pub global: bool,
pub ignore_case: bool,
pub multiline: bool,
pub dot_all: bool,
pub unicode: bool,
pub unicode_sets: bool,
pub sticky: bool,
}
impl Flags {
pub fn parse(text: &str) -> Result<Self, Error> {
let mut flags = Self::default();
for letter in text.chars() {
let seen = match letter {
'd' => &mut flags.indices,
'g' => &mut flags.global,
'i' => &mut flags.ignore_case,
'm' => &mut flags.multiline,
's' => &mut flags.dot_all,
'u' => &mut flags.unicode,
'v' => &mut flags.unicode_sets,
'y' => &mut flags.sticky,
_ => return Err(Error::at("this is not a regular expression flag")),
};
if *seen {
return Err(Error::at("a regular expression flag is repeated"));
}
*seen = true;
}
if flags.unicode && flags.unicode_sets {
return Err(Error::at("the u and v flags cannot be used together"));
}
Ok(flags)
}
#[must_use]
pub fn unicode_mode(self) -> bool {
self.unicode || self.unicode_sets
}
#[must_use]
pub fn spelled(self) -> String {
let mut text = String::new();
for (present, letter) in [
(self.indices, 'd'),
(self.global, 'g'),
(self.ignore_case, 'i'),
(self.multiline, 'm'),
(self.dot_all, 's'),
(self.unicode, 'u'),
(self.unicode_sets, 'v'),
(self.sticky, 'y'),
] {
if present {
text.push(letter);
}
}
text
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Assertion {
Start,
End,
WordBoundary,
NotWordBoundary,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ClassEscape {
Digit(bool),
Space(bool),
Word(bool),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ClassItem {
Single(u32),
Range(u32, u32),
Escape(ClassEscape),
Property(crate::unicode_property::Property),
Strings(Vec<Vec<u32>>),
Nested(ClassSet),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ClassSet {
pub negated: bool,
pub operation: ClassOperation,
pub items: Vec<ClassItem>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ClassOperation {
Union,
Intersection,
Difference,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum GroupKind {
Capturing(u32),
NonCapturing,
Named(u32, String),
Lookahead(bool),
Lookbehind(bool),
}
pub(crate) fn fold(code: u32) -> u32 {
match code {
0x61..=0x7A => code - 32,
_ => code,
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum First {
Any,
Only {
ascii: u128,
wide: bool,
},
}
impl First {
#[must_use]
pub fn may_start(self, code: u32) -> bool {
match self {
Self::Any => true,
Self::Only { ascii, wide } => {
Self::holds(ascii, wide, code) || Self::holds(ascii, wide, fold(code))
}
}
}
fn holds(ascii: u128, wide: bool, code: u32) -> bool {
match code < 128 {
true => ascii & (1u128 << code) != 0,
false => wide,
}
}
fn none() -> Self {
Self::Only {
ascii: 0,
wide: false,
}
}
fn only(code: u32) -> Self {
let mut ascii = 0u128;
let mut wide = false;
for member in [code, fold(code)] {
match member < 128 {
true => ascii |= 1u128 << member,
false => wide = true,
}
}
Self::Only { ascii, wide }
}
fn union(self, other: Self) -> Self {
match (self, other) {
(Self::Any, _) | (_, Self::Any) => Self::Any,
(
Self::Only { ascii, wide },
Self::Only {
ascii: other,
wide: other_wide,
},
) => Self::Only {
ascii: ascii | other,
wide: wide || other_wide,
},
}
}
#[must_use]
pub fn of(node: &Node) -> Self {
match node {
Node::Character(code) => Self::only(*code),
Node::Sequence(terms) => terms.first().map_or(Self::Any, Self::of),
Node::Alternation { firsts, .. } => {
firsts.iter().copied().fold(Self::none(), Self::union)
}
Node::Group { kind, body } => match kind {
GroupKind::Lookahead(_) | GroupKind::Lookbehind(_) => Self::Any,
GroupKind::Capturing(_) | GroupKind::NonCapturing | GroupKind::Named(_, _) => {
Self::of(body)
}
},
Node::Repeat { node, min, .. } if *min >= 1 => Self::of(node),
_ => Self::Any,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Node {
Empty,
Alternation {
branches: Vec<Node>,
firsts: Vec<First>,
},
Sequence(Vec<Node>),
Character(u32),
Any,
Class {
negated: bool,
items: Vec<ClassItem>,
strings: Vec<Vec<u32>>,
},
Escape(ClassEscape),
Property(crate::unicode_property::Property),
Group {
kind: GroupKind,
body: Box<Node>,
},
Backreference(u32),
NamedBackreference(String),
Assert(Assertion),
Repeat {
node: Box<Node>,
min: u32,
max: Option<u32>,
greedy: bool,
},
}
impl Node {
#[must_use]
pub fn alternation(branches: Vec<Node>) -> Self {
let firsts = branches.iter().map(First::of).collect();
Self::Alternation { branches, firsts }
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Pattern {
pub node: Node,
pub groups: u32,
pub names: Vec<(String, u32)>,
pub flags: Flags,
}
#[cfg(test)]
mod tests {
use super::{First, Flags, GroupKind, Node};
fn bits(codes: &[u32]) -> u128 {
codes.iter().fold(0u128, |set, code| set | (1u128 << code))
}
#[test]
fn a_first_set_holds_each_literal_and_its_fold() {
assert_eq!(
First::of(&Node::Character(97)),
First::Only {
ascii: bits(&[65, 97]),
wide: false
},
"a lower-case letter brings its upper-case fold with it"
);
assert_eq!(
First::of(&Node::Character(65)),
First::Only {
ascii: bits(&[65]),
wide: false
}
);
assert_eq!(
First::of(&Node::Character(128)),
First::Only {
ascii: 0,
wide: true
}
);
assert_eq!(
First::of(&Node::Character(0x1F600)),
First::Only {
ascii: 0,
wide: true
}
);
}
#[test]
fn only_the_shapes_that_must_consume_get_a_set() {
let a = First::Only {
ascii: bits(&[65, 97]),
wide: false,
};
assert_eq!(
First::of(&Node::Sequence(vec![
Node::Character(97),
Node::Character(98)
])),
a
);
assert_eq!(
First::of(&Node::Group {
kind: GroupKind::NonCapturing,
body: Box::new(Node::Character(97)),
}),
a
);
assert_eq!(
First::of(&Node::Group {
kind: GroupKind::Lookahead(false),
body: Box::new(Node::Character(97)),
}),
First::Any
);
assert_eq!(
First::of(&Node::Repeat {
node: Box::new(Node::Character(97)),
min: 1,
max: None,
greedy: true,
}),
a
);
assert_eq!(
First::of(&Node::Repeat {
node: Box::new(Node::Character(97)),
min: 0,
max: None,
greedy: true,
}),
First::Any
);
assert_eq!(First::of(&Node::Empty), First::Any);
assert_eq!(First::of(&Node::Any), First::Any);
assert_eq!(First::of(&Node::Backreference(1)), First::Any);
assert_eq!(First::of(&Node::Sequence(Vec::new())), First::Any);
}
#[test]
fn a_nested_alternation_contributes_every_branch() {
let inner = Node::alternation(vec![Node::Character(97), Node::Character(0xE9)]);
assert_eq!(
First::of(&inner),
First::Only {
ascii: bits(&[65, 97]),
wide: true
}
);
let ascii_only = Node::alternation(vec![Node::Character(97), Node::Character(98)]);
assert_eq!(
First::of(&ascii_only),
First::Only {
ascii: bits(&[65, 97, 66, 98]),
wide: false
}
);
let mixed = Node::alternation(vec![Node::Character(97), Node::Empty]);
assert_eq!(First::of(&mixed), First::Any);
}
#[test]
fn may_start_admits_a_character_and_its_fold_in_both_directions() {
let a = First::of(&Node::Character(97));
assert!(a.may_start(97), "the literal itself");
assert!(a.may_start(65), "its fold, for a pattern carrying `i`");
assert!(!a.may_start(98));
assert!(!a.may_start(0xE9));
let upper = First::of(&Node::Character(65));
assert!(upper.may_start(65));
assert!(upper.may_start(97), "folded on the way in");
assert!(!a.may_start(128));
let wide = First::of(&Node::Character(200));
assert!(wide.may_start(200));
assert!(
wide.may_start(128),
"any non-ASCII, which is all `wide` claims"
);
assert!(!wide.may_start(97));
assert!(First::Any.may_start(0));
assert!(First::Any.may_start(0x10FFFF));
}
#[test]
fn flags_are_a_set_and_a_repeat_is_an_error() {
assert_eq!(
Flags::parse("gimsuy").map(|f| f.spelled()).as_deref(),
Ok("gimsuy")
);
assert_eq!(
Flags::parse("yus").map(|f| f.spelled()).as_deref(),
Ok("suy")
);
assert_eq!(Flags::parse("").map(|f| f.spelled()).as_deref(), Ok(""));
assert_eq!(
Flags::parse("gg").err().map(|e| e.message),
Some("a regular expression flag is repeated")
);
assert_eq!(
Flags::parse("x").err().map(|e| e.message),
Some("this is not a regular expression flag")
);
assert_eq!(
Flags::parse("uv").err().map(|e| e.message),
Some("the u and v flags cannot be used together")
);
assert!(Flags::parse("v").is_ok_and(|f| f.unicode_mode() && !f.unicode));
}
}