use std::fmt;
use crate::{PathExpr, Step};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Token<A> {
Attribute(A),
Open,
Close,
Bar,
Star,
Plus,
Question,
Caret,
}
impl<A> Token<A> {
fn name(&self) -> &'static str {
match self {
Token::Attribute(_) => "an attribute",
Token::Open => "'('",
Token::Close => "')'",
Token::Bar => "'|'",
Token::Star => "'*'",
Token::Plus => "'+'",
Token::Question => "'?'",
Token::Caret => "'^'",
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Ast<A> {
Attribute(A),
Sequence(Vec<Ast<A>>),
Alternation(Vec<Ast<A>>),
Star(Box<Ast<A>>),
Plus(Box<Ast<A>>),
Optional(Box<Ast<A>>),
Inverse(Box<Ast<A>>),
}
impl<A> Ast<A> {
pub fn lower(&self, step: &impl Fn(&A) -> Step) -> PathExpr {
match self {
Ast::Attribute(a) => PathExpr::from(step(a)),
Ast::Sequence(items) => {
let mut items = items.iter();
let first = items.next().expect("a sequence has at least one item").lower(step);
items.fold(first, |acc, item| acc.then(item.lower(step)))
}
Ast::Alternation(items) => {
let mut items = items.iter();
let first = items
.next()
.expect("an alternation has at least one item")
.lower(step);
items.fold(first, |acc, item| acc.or(item.lower(step)))
}
Ast::Star(inner) => inner.lower(step).star(),
Ast::Plus(inner) => inner.lower(step).plus(),
Ast::Optional(inner) => inner.lower(step).optional(),
Ast::Inverse(inner) => inner.lower(step).inverse(),
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ParseError {
pub at: usize,
pub message: String,
}
impl fmt::Display for ParseError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.message)
}
}
impl std::error::Error for ParseError {}
pub fn parse<A: Clone>(tokens: &[Token<A>]) -> Result<Ast<A>, ParseError> {
let mut parser = Parser { tokens, at: 0 };
let ast = parser.alternation()?;
match parser.peek() {
None => Ok(ast),
Some(token) => Err(parser.error(format!(
"unexpected {} after a complete expression",
token.name()
))),
}
}
struct Parser<'t, A> {
tokens: &'t [Token<A>],
at: usize,
}
impl<'t, A: Clone> Parser<'t, A> {
fn peek(&self) -> Option<&'t Token<A>> {
self.tokens.get(self.at)
}
fn bump(&mut self) -> Option<&'t Token<A>> {
let token = self.tokens.get(self.at);
self.at += 1;
token
}
fn error(&self, message: String) -> ParseError {
ParseError {
at: self.at.min(self.tokens.len()),
message,
}
}
fn alternation(&mut self) -> Result<Ast<A>, ParseError> {
let mut items = vec![self.sequence()?];
while matches!(self.peek(), Some(Token::Bar)) {
self.bump();
items.push(self.sequence()?);
}
Ok(if items.len() == 1 {
items.pop().expect("one item")
} else {
Ast::Alternation(items)
})
}
fn sequence(&mut self) -> Result<Ast<A>, ParseError> {
let mut items = vec![self.unary()?];
while matches!(
self.peek(),
Some(Token::Attribute(_)) | Some(Token::Open) | Some(Token::Caret)
) {
items.push(self.unary()?);
}
Ok(if items.len() == 1 {
items.pop().expect("one item")
} else {
Ast::Sequence(items)
})
}
fn unary(&mut self) -> Result<Ast<A>, ParseError> {
let reverse = matches!(self.peek(), Some(Token::Caret));
if reverse {
self.bump();
}
let mut ast = self.atom()?;
if reverse {
ast = Ast::Inverse(Box::new(ast));
}
loop {
ast = match self.peek() {
Some(Token::Star) => Ast::Star(Box::new(ast)),
Some(Token::Plus) => Ast::Plus(Box::new(ast)),
Some(Token::Question) => Ast::Optional(Box::new(ast)),
_ => return Ok(ast),
};
self.bump();
}
}
fn atom(&mut self) -> Result<Ast<A>, ParseError> {
match self.bump() {
Some(Token::Attribute(a)) => Ok(Ast::Attribute(a.clone())),
Some(Token::Open) => {
let inner = self.alternation()?;
match self.bump() {
Some(Token::Close) => Ok(inner),
Some(token) => Err(self.error(format!("expected ')' but found {}", token.name()))),
None => Err(self.error("expected ')' but the expression ended".to_owned())),
}
}
Some(token) => Err(self.error(format!(
"expected an attribute or '(' but found {}",
token.name()
))),
None => Err(self.error(
"expected an attribute or '(' but the expression ended".to_owned(),
)),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::automaton_fingerprint;
fn raw(byte: u8) -> [u8; 16] {
[byte; 16]
}
fn a(byte: u8) -> Token<u8> {
Token::Attribute(byte)
}
fn lowered(tokens: &[Token<u8>]) -> PathExpr {
parse(tokens)
.unwrap()
.lower(&|byte| Step::Forward(raw(*byte)))
}
fn same(tokens: &[Token<u8>], built: PathExpr) {
assert_eq!(
automaton_fingerprint(&lowered(tokens).compile()),
automaton_fingerprint(&built.compile()),
"{tokens:?}"
);
}
#[test]
fn one_attribute_is_one_forward_step() {
same(&[a(1)], PathExpr::from(Step::Forward(raw(1))));
}
#[test]
fn juxtaposition_is_sequence_and_bar_is_alternation() {
same(
&[a(1), a(2), Token::Bar, a(3)],
PathExpr::from(Step::Forward(raw(1)))
.then(PathExpr::from(Step::Forward(raw(2))))
.or(PathExpr::from(Step::Forward(raw(3)))),
);
}
#[test]
fn repetitions_bind_tighter_than_sequence_and_caret_reverses() {
use Token::*;
same(
&[a(1), Open, Caret, a(2), Bar, a(3), Close, Plus, a(4), Question],
PathExpr::from(Step::Forward(raw(1)))
.then(
PathExpr::from(Step::Forward(raw(2)))
.inverse()
.or(PathExpr::from(Step::Forward(raw(3))))
.plus(),
)
.then(PathExpr::from(Step::Forward(raw(4))).optional()),
);
}
#[test]
fn a_reversed_group_reverses_the_whole_group() {
use Token::*;
same(
&[Caret, Open, a(1), a(2), Close, Star],
PathExpr::from(Step::Forward(raw(1)))
.then(PathExpr::from(Step::Forward(raw(2))))
.inverse()
.star(),
);
}
#[test]
fn errors_name_the_token() {
use Token::*;
let stray = parse(&[a(1), Close]).unwrap_err();
assert_eq!(stray.at, 1);
assert!(stray.message.contains("unexpected ')'"), "{stray}");
let open = parse(&[Open, a(1)]).unwrap_err();
assert!(open.message.contains("expected ')'"), "{open}");
let empty = parse::<u8>(&[]).unwrap_err();
assert!(empty.message.contains("expression ended"), "{empty}");
let bar = parse(&[a(1), Bar]).unwrap_err();
assert!(bar.message.contains("expression ended"), "{bar}");
}
}