use std::{collections::HashSet, sync::Arc};
use crate::{
AstKind, ClassItem, ClassRange, ClassSet, GroupInfo, GroupKind, Node, NodeId, ParseError,
ParseErrorKind, Pattern, PerlClass, RepKind, Span,
};
const MAX_REPEAT: u32 = 1_000;
pub fn parse(src: &str) -> Result<Pattern, ParseError> {
Parser::new(src).parse()
}
struct Parser {
src: Arc<str>,
pos: usize,
nodes: Vec<Node>,
groups: Vec<GroupInfo>,
names: HashSet<Box<str>>,
}
type ParsedClassAtom = (char, bool, Option<(PerlClass, bool)>);
struct Frame {
group: Option<GroupFrame>,
expression_start: usize,
arm_start: usize,
arms: Vec<NodeId>,
parts: Vec<NodeId>,
}
struct GroupFrame {
start: usize,
kind: GroupKind,
group_slot: Option<usize>,
}
impl Frame {
const fn root() -> Self {
Self {
group: None,
expression_start: 0,
arm_start: 0,
arms: Vec::new(),
parts: Vec::new(),
}
}
const fn group(group: GroupFrame, inner_start: usize) -> Self {
Self {
group: Some(group),
expression_start: inner_start,
arm_start: inner_start,
arms: Vec::new(),
parts: Vec::new(),
}
}
}
impl Parser {
fn new(src: &str) -> Self {
Self {
src: Arc::from(src),
pos: 0,
nodes: Vec::new(),
groups: Vec::new(),
names: HashSet::new(),
}
}
fn parse(mut self) -> Result<Pattern, ParseError> {
let mut stack = vec![Frame::root()];
while let Some(c) = self.peek() {
match c {
'(' => {
let group = self.open_group()?;
stack.push(group);
}
')' => self.close_group(&mut stack)?,
'|' => self.finish_arm(&mut stack),
'*' | '+' | '?' => {
return Err(self.error(
ParseErrorKind::DanglingQuantifier,
self.pos,
self.pos + 1,
));
}
_ => {
let start = self.pos;
let atom = self.atom()?;
let repeated = self.quantify(atom, start)?;
stack
.last_mut()
.expect("root frame exists")
.parts
.push(repeated);
}
}
}
if stack.len() != 1 {
let start = stack
.last()
.and_then(|frame| frame.group.as_ref())
.map_or(self.pos, |group| group.start);
return Err(self.error(ParseErrorKind::UnbalancedParen, start, self.pos));
}
let root = self.finish_frame(stack.pop().expect("root frame exists"), self.pos);
Ok(Pattern {
src: self.src,
nodes: self.nodes,
groups: self.groups,
root,
})
}
fn open_group(&mut self) -> Result<Frame, ParseError> {
let start = self.pos;
self.bump();
let kind = self.group_kind(start)?;
let group_slot = if let GroupKind::Capture { index, name } = &kind {
let slot = self.groups.len();
self.groups.push(GroupInfo {
index: *index,
name: name.clone(),
node: NodeId(u32::MAX),
});
Some(slot)
} else {
None
};
Ok(Frame::group(
GroupFrame {
start,
kind,
group_slot,
},
self.pos,
))
}
fn group_kind(&mut self, start: usize) -> Result<GroupKind, ParseError> {
if self.peek() != Some('?') {
return Ok(GroupKind::Capture {
index: self.next_group_index(),
name: None,
});
}
self.bump();
match self.bump() {
Some(':') => Ok(GroupKind::NonCapture),
Some('<') => self.named_group(start),
_ => Err(self.error(
ParseErrorKind::UnsupportedFeature("lookaround or inline flags"),
start,
self.pos,
)),
}
}
fn named_group(&mut self, start: usize) -> Result<GroupKind, ParseError> {
let name_start = self.pos;
while self.peek().is_some_and(|c| c != '>') {
self.bump();
}
if self.peek() != Some('>') || self.pos == name_start {
return Err(self.error(
ParseErrorKind::UnsupportedFeature("invalid named group"),
start,
self.pos,
));
}
let name: Box<str> = self.src[name_start..self.pos].into();
self.bump();
if !self.names.insert(name.clone()) {
return Err(self.error(
ParseErrorKind::DuplicateGroupName(name),
name_start,
self.pos - 1,
));
}
Ok(GroupKind::Capture {
index: self.next_group_index(),
name: Some(name),
})
}
fn next_group_index(&self) -> u32 {
u32::try_from(self.groups.len()).expect("group arena exceeds u32") + 1
}
fn close_group(&mut self, stack: &mut Vec<Frame>) -> Result<(), ParseError> {
if stack.len() == 1 {
return Err(self.error(ParseErrorKind::UnbalancedParen, self.pos, self.pos + 1));
}
let end = self.pos;
self.bump();
let frame = stack.pop().expect("non-root frame exists");
let group = frame.group.as_ref().expect("group frame");
let start = group.start;
let kind = group.kind.clone();
let group_slot = group.group_slot;
let inner = self.finish_frame(frame, end);
let node = self.add_parent(AstKind::Group { kind, inner }, Span::new(start, self.pos));
if let Some(slot) = group_slot {
self.groups[slot].node = node;
}
let repeated = self.quantify(node, start)?;
stack
.last_mut()
.expect("parent frame exists")
.parts
.push(repeated);
Ok(())
}
fn finish_arm(&mut self, stack: &mut [Frame]) {
let frame = stack.last_mut().expect("root frame exists");
let parts = std::mem::take(&mut frame.parts);
let arm = self.finish_concat(parts, frame.arm_start, self.pos);
frame.arms.push(arm);
self.bump();
frame.arm_start = self.pos;
}
fn finish_frame(&mut self, mut frame: Frame, end: usize) -> NodeId {
let last = self.finish_concat(frame.parts, frame.arm_start, end);
if frame.arms.is_empty() {
return last;
}
frame.arms.push(last);
self.add_parent(
AstKind::Alt { arms: frame.arms },
Span::new(frame.expression_start, end),
)
}
fn finish_concat(&mut self, parts: Vec<NodeId>, start: usize, end: usize) -> NodeId {
match parts.len() {
0 => self.add(AstKind::Empty, Span::new(start, start)),
1 => parts[0],
_ => self.add_parent(AstKind::Concat { parts }, Span::new(start, end)),
}
}
fn quantify(&mut self, inner: NodeId, start: usize) -> Result<NodeId, ParseError> {
let kind = match self.peek() {
Some('?') => {
self.bump();
Some(RepKind::ZeroOrOne)
}
Some('*') => {
self.bump();
Some(RepKind::ZeroOrMore)
}
Some('+') => {
self.bump();
Some(RepKind::OneOrMore)
}
Some('{') => self.counted()?,
_ => None,
};
let Some(kind) = kind else { return Ok(inner) };
let greedy = if self.peek() == Some('?') {
self.bump();
false
} else {
true
};
if matches!(self.peek(), Some('*' | '+' | '?')) {
return Err(self.error(ParseErrorKind::DanglingQuantifier, self.pos, self.pos + 1));
}
Ok(self.add_parent(
AstKind::Repeat {
inner,
kind,
greedy,
},
Span::new(start, self.pos),
))
}
fn counted(&mut self) -> Result<Option<RepKind>, ParseError> {
let start = self.pos;
let after_brace = start + 1;
if !self.src[after_brace..]
.chars()
.next()
.is_some_and(|c| c.is_ascii_digit())
{
return Ok(None);
}
self.bump();
let min = self.number()?;
let (max, had_comma) = if self.peek() == Some(',') {
self.bump();
let max = self
.peek()
.is_some_and(|c| c.is_ascii_digit())
.then(|| self.number())
.transpose()?;
(max, true)
} else {
(Some(min), false)
};
if self.peek() != Some('}') {
return Err(self.error(
ParseErrorKind::InvalidCounted,
start,
self.pos.max(start + 1),
));
}
self.bump();
if min > MAX_REPEAT || max.is_some_and(|max| min > max || max > MAX_REPEAT) {
return Err(self.error(ParseErrorKind::InvalidCounted, start, self.pos));
}
Ok(Some(RepKind::Range {
min,
max: if had_comma { max } else { Some(min) },
}))
}
fn number(&mut self) -> Result<u32, ParseError> {
let start = self.pos;
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
self.bump();
}
self.src[start..self.pos]
.parse()
.map_err(|_| self.error(ParseErrorKind::InvalidCounted, start, self.pos))
}
fn atom(&mut self) -> Result<NodeId, ParseError> {
let start = self.pos;
let Some(c) = self.bump() else {
return Ok(self.add(AstKind::Empty, Span::new(start, start)));
};
match c {
'[' => self.class(start),
'.' => Ok(self.add(AstKind::Dot, Span::new(start, self.pos))),
'\\' => self.escaped_atom(start),
'^' => Ok(self.add(
AstKind::Anchor {
kind: crate::AnchorKind::Start,
},
Span::new(start, self.pos),
)),
'$' => Ok(self.add(
AstKind::Anchor {
kind: crate::AnchorKind::End,
},
Span::new(start, self.pos),
)),
'(' | ')' | '|' => unreachable!("structural tokens are handled by parse loop"),
literal => Ok(self.add(
AstKind::Literal {
c: literal,
escaped: false,
},
Span::new(start, self.pos),
)),
}
}
fn escaped_atom(&mut self, start: usize) -> Result<NodeId, ParseError> {
let Some(escaped) = self.bump() else {
return Err(self.error(ParseErrorKind::InvalidEscape('\\'), start, self.pos));
};
if escaped.is_ascii_digit() {
return Err(self.error(
ParseErrorKind::UnsupportedFeature("backreferences"),
start,
self.pos,
));
}
if let Some((class, negated)) = perl_class(escaped) {
let mut set = class.set();
if negated {
set = set.negate();
}
return Ok(self.add(
AstKind::Class {
negated: false,
items: vec![ClassItem::Perl { class, negated }],
set,
},
Span::new(start, self.pos),
));
}
let c = escape_char(escaped)
.ok_or_else(|| self.error(ParseErrorKind::InvalidEscape(escaped), start, self.pos))?;
Ok(self.add(
AstKind::Literal { c, escaped: true },
Span::new(start, self.pos),
))
}
fn class(&mut self, start: usize) -> Result<NodeId, ParseError> {
let negated = if self.peek() == Some('^') {
self.bump();
true
} else {
false
};
let mut items = Vec::new();
let mut set = ClassSet::empty();
while let Some(c) = self.peek() {
if c == ']' && !items.is_empty() {
self.bump();
if negated {
set = set.negate();
}
return Ok(self.add(
AstKind::Class {
negated,
items,
set,
},
Span::new(start, self.pos),
));
}
let (left, escaped, perl) = self.class_atom(start)?;
if let Some((class, class_negated)) = perl {
let item_set = if class_negated {
class.set().negate()
} else {
class.set()
};
set = set.union(&item_set);
items.push(ClassItem::Perl {
class,
negated: class_negated,
});
continue;
}
if self.peek() == Some('-')
&& self.src[self.pos + 1..]
.chars()
.next()
.is_some_and(|c| c != ']')
{
self.bump();
let (right, _, right_perl) = self.class_atom(start)?;
if right_perl.is_some() || left > right {
return Err(self.error(
ParseErrorKind::InvalidRange {
lo: left,
hi: right,
},
start,
self.pos,
));
}
set = set.union(&ClassSet::from_ranges([ClassRange {
start: left,
end: right,
}]));
items.push(ClassItem::Range {
lo: left,
hi: right,
});
} else {
set = set.union(&ClassSet::singleton(left));
items.push(ClassItem::Single { c: left, escaped });
}
}
Err(self.error(ParseErrorKind::UnclosedClass, start, self.pos))
}
fn class_atom(&mut self, class_start: usize) -> Result<ParsedClassAtom, ParseError> {
let start = self.pos;
let Some(c) = self.bump() else {
return Err(self.error(ParseErrorKind::UnclosedClass, class_start, self.pos));
};
if c != '\\' {
return Ok((c, false, None));
}
let Some(escaped) = self.bump() else {
return Err(self.error(ParseErrorKind::InvalidEscape('\\'), start, self.pos));
};
if let Some(perl) = perl_class(escaped) {
return Ok(('\0', true, Some(perl)));
}
let value = escape_char(escaped)
.ok_or_else(|| self.error(ParseErrorKind::InvalidEscape(escaped), start, self.pos))?;
Ok((value, true, None))
}
fn add(&mut self, kind: AstKind, span: Span) -> NodeId {
let id = NodeId(u32::try_from(self.nodes.len()).expect("node arena exceeds u32"));
self.nodes.push(Node {
kind,
span,
parent: None,
});
id
}
fn add_parent(&mut self, kind: AstKind, span: Span) -> NodeId {
let children = kind.children().to_vec();
let id = self.add(kind, span);
for child in children {
self.nodes[child.0 as usize].parent = Some(id);
}
id
}
fn peek(&self) -> Option<char> {
self.src[self.pos..].chars().next()
}
fn bump(&mut self) -> Option<char> {
let c = self.peek()?;
self.pos += c.len_utf8();
Some(c)
}
fn error(&self, kind: ParseErrorKind, start: usize, end: usize) -> ParseError {
ParseError::new(kind, Span::new(start, end), &self.src)
}
}
fn perl_class(c: char) -> Option<(PerlClass, bool)> {
Some(match c {
'd' => (PerlClass::Digit, false),
'D' => (PerlClass::Digit, true),
'w' => (PerlClass::Word, false),
'W' => (PerlClass::Word, true),
's' => (PerlClass::Space, false),
'S' => (PerlClass::Space, true),
_ => return None,
})
}
fn escape_char(c: char) -> Option<char> {
Some(match c {
'n' => '\n',
'r' => '\r',
't' => '\t',
'\\' | '.' | '+' | '*' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|' | '^' | '$'
| '-' => c,
_ => return None,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn parses_complete_grammar_and_parent_links() {
let pattern = parse(r"(?<word>[a-z]+)(?:\s|_){1,3}?").unwrap();
assert_eq!(pattern.groups().len(), 1);
assert_eq!(pattern.root().text(), pattern.source());
for cursor in pattern.root().walk().skip(1) {
assert!(cursor.parent().is_some());
}
}
#[test]
fn is_lossless_for_escapes() {
let pattern = parse(r"\n[\dA-Z]").unwrap();
assert_eq!(pattern.root().text(), r"\n[\dA-Z]");
}
#[test]
fn reports_unsupported_features() {
assert!(matches!(
parse(r"(a)\1").unwrap_err().kind,
ParseErrorKind::UnsupportedFeature("backreferences")
));
}
#[test]
fn reports_each_structural_error() {
assert!(matches!(
parse("a**").unwrap_err().kind,
ParseErrorKind::DanglingQuantifier
));
assert!(matches!(
parse("[z-a]").unwrap_err().kind,
ParseErrorKind::InvalidRange { .. }
));
assert!(matches!(
parse("[abc").unwrap_err().kind,
ParseErrorKind::UnclosedClass
));
assert!(matches!(
parse("a{3,1}").unwrap_err().kind,
ParseErrorKind::InvalidCounted
));
assert!(matches!(
parse("a{1001}").unwrap_err().kind,
ParseErrorKind::InvalidCounted
));
assert!(matches!(
parse("(?<x>a)(?<x>b)").unwrap_err().kind,
ParseErrorKind::DuplicateGroupName(_)
));
assert!(matches!(
parse("(abc").unwrap_err().kind,
ParseErrorKind::UnbalancedParen
));
}
#[test]
fn raw_brace_is_a_literal_when_not_a_count() {
let pattern = parse("a{x}").unwrap();
assert_eq!(pattern.root().text(), "a{x}");
}
#[test]
fn parses_deep_groups_without_call_stack_growth() {
let depth = 20_000;
let source = format!("{}a{}", "(".repeat(depth), ")".repeat(depth));
let pattern = parse(&source).unwrap();
assert_eq!(pattern.groups().len(), depth);
assert_eq!(pattern.root().walk().count(), depth + 1);
assert_eq!(pattern.root().text(), source);
}
}