extern crate alloc;
pub mod error;
pub mod repeat;
pub mod also;
pub mod chain;
pub mod reduce;
mod fail;
use alloc::rc::Rc;
use core::{
slice,
iter::{self, FromIterator},
cell::RefCell,
borrow::Borrow,
};
use crate::{
error::{ParseError, DefaultParseError},
repeat::Repeat,
fail::{Fail, MayFail},
also::Also,
chain::Chain,
reduce::{ReduceLeft, ReduceRight},
};
type TokenIter<'a, T> = iter::Enumerate<iter::Cloned<slice::Iter<'a, T>>>;
pub struct Parser<'a, T: Clone + 'a, O: 'a = T, E: ParseError<'a, T> + 'a = DefaultParseError<T>> {
f: Rc<dyn Fn(&mut TokenIter<T>) -> Result<(MayFail<E>, O), Fail<E>> + 'a>,
}
impl<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a> Clone for Parser<'a, T, O, E> {
fn clone(&self) -> Self {
Self { f: self.f.clone() }
}
}
impl<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a> Parser<'a, T, O, E> {
fn custom(f: impl Fn(&mut TokenIter<T>) -> Result<(MayFail<E>, O), Fail<E>> + 'a) -> Self {
Self { f: Rc::new(move |tokens| attempt(tokens, &f)) }
}
fn maybe_map(f: impl Fn(T) -> Option<O> + 'a) -> Self {
Self::custom(move |tokens| try_parse(tokens, |(idx, tok), _| {
match f(tok.clone()) {
Some(output) => Ok((MayFail::none(), output)),
None => Err(Fail::new(idx, E::unexpected(tok))),
}
}))
}
fn call(f: impl Fn() -> Self + 'a) -> Self {
Self::custom(move |tokens| (f().f)(tokens))
}
pub fn link(&self) -> Self {
self.clone()
}
pub fn map<U: 'a>(self, f: impl Fn(O) -> U + 'a) -> Parser<'a, T, U, E> {
Parser::custom(move |tokens| (self.f)(tokens).map(|(e, o)| (e, f(o))))
}
pub fn map_err<G: ParseError<'a, T> + 'a>(self, f: impl Fn(E) -> G + 'a) -> Parser<'a, T, O, G> {
Parser::custom(move |tokens| match (self.f)(tokens) {
Ok((fail, output)) => Ok((fail.map_err(&f), output)),
Err(fail) => Err(fail.map_err(&f)),
})
}
pub fn discard(self) -> Parser<'a, T, (), E> {
self.map(|_| ())
}
pub fn to<U: Clone + 'a>(self, to: U) -> Parser<'a, T, U, E> {
self.map(move |_| to.clone())
}
pub fn or_not(self) -> Parser<'a, T, Option<O>, E> {
Parser::custom(move |tokens| {
match (self.f)(tokens) {
Ok((fail, output)) => Ok((fail, Some(output))),
Err(fail) => Ok((fail.into(), None)),
}
})
}
pub fn then<U: 'a>(self, other: Parser<'a, T, U, E>) -> Parser<'a, T, (O, U), E> {
Parser::custom(move |tokens| {
let (a_fail, a) = (self.f)(tokens)?;
let (b_fail, b) = (other.f)(tokens)?;
Ok((a_fail.max(b_fail), (a, b)))
})
}
pub fn also<U: 'a>(self, other: Parser<'a, T, U, E>) -> Parser<'a, T, O::Alsoed, E> where O: Also<U> {
Parser::custom(move |tokens| {
let (a_fail, a) = (self.f)(tokens)?;
let (b_fail, b) = (other.f)(tokens)?;
Ok((a_fail.max(b_fail), a.also(b)))
})
}
pub fn chain<U: 'a>(self, other: Parser<'a, T, U, E>) -> Parser<'a, T, O::Chained, E> where O: Chain<U> {
self.then(other).map(|(a, b)| a.chain(b))
}
pub fn delimiter_for<U: 'a>(self, other: Parser<'a, T, U, E>) -> Parser<'a, T, U, E> {
Parser::custom(move |tokens| {
let (a_fail, _) = (self.f)(tokens)?;
let (b_fail, b) = (other.f)(tokens)?;
Ok((a_fail.max(b_fail), b))
})
}
pub fn delimited_by<U: 'a>(self, other: Parser<'a, T, U, E>) -> Self {
Parser::custom(move |tokens| {
let (a_fail, a) = (self.f)(tokens)?;
let (b_fail, _) = (other.f)(tokens)?;
Ok((a_fail.max(b_fail), a))
})
}
pub fn padded_by(self, padding: impl Borrow<T> + 'a) -> Self where T: PartialEq {
self.delimited_by(sym(padding).repeat(..))
}
pub fn padded(self) -> Self where T: Borrow<char> {
self.delimited_by(permit(|c: T| c.borrow().is_whitespace()).repeat(..))
}
pub fn or(self, other: Parser<'a, T, O, E>) -> Self {
Parser::custom(move |tokens| {
let a = (self.f)(tokens);
let mut b_tokens = tokens.clone();
let b = (other.f)(&mut b_tokens);
match a {
Ok((a_fail, a)) => match b {
Ok((b_fail, _)) => Ok((a_fail.max(b_fail), a)),
Err(b_fail) => Ok((a_fail.max(b_fail), a)),
},
Err(a_fail) => match b {
Ok((b_fail, b)) => {
*tokens = b_tokens;
Ok((b_fail.max(a_fail), b))
},
Err(b_fail) => Err(a_fail.max(b_fail)),
},
}
})
}
pub fn or_fallback(self, other: Parser<'a, T, O, E>) -> Self {
Parser::custom(move |tokens| {
let a = (self.f)(tokens);
match a {
Ok((a_fail, a)) => Ok((a_fail, a)),
Err(a_fail) => match (other.f)(tokens) {
Ok((b_fail, b)) => Ok((b_fail.max(a_fail), b)),
Err(b_fail) => Err(a_fail.max(b_fail)),
},
}
})
}
pub fn repeat(self, repeat: impl Into<Repeat>) -> Parser<'a, T, Vec<O>, E> {
let repeat = repeat.into();
Parser::custom(move |tokens| {
let mut max_err = MayFail::none();
let mut outputs = Vec::new();
for i in 0..repeat.idx_upper_limit() {
match (self.f)(tokens) {
Ok((err, output)) => {
max_err = max_err.max(err);
outputs.push(output);
},
Err(err) if repeat.contains(i) => {
max_err = max_err.max(err);
break;
},
Err(err) => return Err(err.max(max_err)),
}
}
Ok((max_err, outputs))
})
}
pub fn collect<U: FromIterator<O::Item>>(self) -> Parser<'a, T, U, E> where O: IntoIterator {
self.map(|output| output.into_iter().collect())
}
pub fn reduce_left<A, B>(self, f: impl Fn(B, A) -> A + 'a) -> Parser<'a, T, A, E> where O: ReduceLeft<A, B> {
self.map(move |output| output.reduce_left(&f))
}
pub fn reduce_right<A, B>(self, f: impl Fn(A, B) -> A + 'a) -> Parser<'a, T, A, E> where O: ReduceRight<A, B> {
self.map(move |output| output.reduce_right(&f))
}
pub fn parse(&self, tokens: impl AsRef<[T]>) -> Result<O, E> {
let mut tokens = tokens.as_ref().iter().cloned().enumerate();
let (fail, output) = (self.f)(&mut tokens).map_err(|e| e.take_error())?;
if let Some((idx, tok)) = tokens.next() {
Err(Fail::new(idx, E::unexpected(tok)).max(fail).take_error())
} else {
Ok(output)
}
}
}
impl<'a, T: Clone + 'a, E: ParseError<'a, T> + 'a> Parser<'a, T, T, E> {
fn permit(f: impl Fn(T) -> bool + 'a) -> Self {
Self::maybe_map(move |tok| if f(tok.clone()) { Some(tok) } else { None })
}
fn sym(expected: impl Borrow<T> + 'a) -> Self where T: PartialEq {
Self::permit(move |tok| &tok == expected.borrow())
}
fn not_sym(expected: impl Borrow<T> + 'a) -> Self where T: PartialEq {
Self::permit(move |tok| &tok != expected.borrow())
}
fn one_of(expected: impl IntoIterator<Item=impl Borrow<T> + 'a>) -> Self where T: PartialEq {
let expected = expected.into_iter().collect::<Vec<_>>();
Self::permit(move |tok| expected.iter().any(|e| &tok == e.borrow()))
}
fn none_of(expected: impl IntoIterator<Item=impl Borrow<T> + 'a>) -> Self where T: PartialEq {
let expected = expected.into_iter().collect::<Vec<_>>();
Self::permit(move |tok| expected.iter().all(|e| &tok != e.borrow()))
}
fn all_of(expected: impl IntoIterator<Item=impl Borrow<T> + 'a>) -> Parser<'a, T, Vec<T>, E> where T: PartialEq {
let expected = expected.into_iter().collect::<Vec<_>>();
Parser::custom(move |tokens| {
let mut outputs = Vec::new();
for expected in &expected {
match tokens.next() {
Some((_, output)) if &output == expected.borrow() => outputs.push(output),
Some((idx, output)) => return Err(Fail::new(idx, E::unexpected(output))),
None => return Err(Fail::new(!0, E::unexpected_end())),
}
}
Ok((MayFail::none(), outputs))
})
}
}
pub struct Declaration<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> = DefaultParseError<T>> {
parser: Rc<RefCell<Option<Parser<'a, T, O, E>>>>,
}
impl<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a> Declaration<'a, T, O, E> {
pub fn new() -> Self {
Self { parser: Rc::new(RefCell::new(None)) }
}
pub fn link(&self) -> Parser<'a, T, O, E> {
let parser = Rc::downgrade(&self.parser);
Parser::custom(move |tokens| {
((*parser.upgrade().expect("Parser was dropped")).borrow().as_ref().expect("Parser was declared but not defined").f)(tokens)
})
}
pub fn define(self, parser: Parser<'a, T, O, E>) -> Parser<'a, T, O, E> {
*self.parser.borrow_mut() = Some(parser);
Parser::custom(move |tokens| ((*self.parser).borrow().as_ref().unwrap().f)(tokens))
}
}
pub fn declare<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a>() -> Declaration<'a, T, O, E> {
Declaration::new()
}
pub fn recursive<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a>(f: impl FnOnce(Parser<'a, T, O, E>) -> Parser<'a, T, O, E> + 'a) -> Parser<'a, T, O, E> {
let p = Declaration::new();
let p_link = p.link();
p.define(f(p_link))
}
fn attempt<'a, T: Clone + 'a, R, F, E: ParseError<'a, T> + 'a>(tokens: &mut TokenIter<T>, f: F) -> Result<R, Fail<E>>
where F: FnOnce(&mut TokenIter<T>) -> Result<R, Fail<E>>,
{
let mut tokens2 = tokens.clone();
let tok = f(&mut tokens2)?;
*tokens = tokens2;
Ok(tok)
}
fn try_parse<'a, T: Clone + 'a, R, F, E: ParseError<'a, T> + 'a>(tokens: &mut TokenIter<T>, f: F) -> Result<(MayFail<E>, R), Fail<E>>
where F: FnOnce((usize, T), &mut TokenIter<T>) -> Result<(MayFail<E>, R), Fail<E>>,
{
attempt(tokens, |tokens| f(tokens.next().ok_or(Fail::new(!0, E::unexpected_end()))?, tokens))
}
pub fn sym<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>(expected: impl Borrow<T> + 'a) -> Parser<'a, T, T, E> {
Parser::sym(expected)
}
pub fn not_sym<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>(expected: impl Borrow<T> + 'a) -> Parser<'a, T, T, E> {
Parser::not_sym(expected)
}
pub fn one_of<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>(expected: impl IntoIterator<Item=impl Borrow<T> + 'a>) -> Parser<'a, T, T, E> {
Parser::one_of(expected)
}
pub fn none_of<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>(expected: impl IntoIterator<Item=impl Borrow<T> + 'a>) -> Parser<'a, T, T, E> {
Parser::none_of(expected)
}
pub fn all_of<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>(expected: impl IntoIterator<Item=impl Borrow<T> + 'static>) -> Parser<'a, T, Vec<T>, E> {
Parser::all_of(expected)
}
pub fn permit<'a, T: Clone + 'a, E: ParseError<'a, T> + 'a>(f: impl Fn(T) -> bool + 'static) -> Parser<'a, T, T, E> {
Parser::permit(f)
}
pub fn maybe_map<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a>(f: impl Fn(T) -> Option<O> + 'static) -> Parser<'a, T, O, E> {
Parser::maybe_map(f)
}
pub fn any_sym<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>() -> Parser<'a, T, T, E> {
permit(|_| true)
}
pub fn all_sym<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>() -> Parser<'a, T, Vec<T>, E> {
permit(|_| true).repeat(..)
}
pub fn nothing<'a, T: Clone + 'a + PartialEq, E: ParseError<'a, T> + 'a>() -> Parser<'a, T, (), E> {
permit(|_| false).discard()
}
pub fn call<'a, T: Clone + 'a, O: 'a, E: ParseError<'a, T> + 'a>(f: impl Fn() -> Parser<'a, T, O, E> + 'a) -> Parser<'a, T, O, E> {
Parser::call(f)
}
pub mod prelude {
pub use super::{
error::{self, ParseError, DefaultParseError},
repeat::{self, Repeat, Repeat::Any},
Parser,
Declaration,
declare,
recursive,
sym,
not_sym,
one_of,
none_of,
all_of,
permit,
maybe_map,
call,
rule,
parsers,
};
}
#[macro_export]
macro_rules! parze_error {
() => {};
}
#[macro_export]
macro_rules! rule {
( ( $($inner:tt)* ) ) => { ($crate::rule!( $($inner)* )) };
( { $($inner:tt)* } ) => { { $($inner)* } };
( [ $inner:tt ] ) => { { $crate::all_of($crate::rule!(@AS_EXPR $inner)) } };
( @AS_EXPR $x:tt $($tail:tt)* ) => { $crate::rule!( { $x } $($tail)* ) };
( $x:literal $($tail:tt)* ) => { $crate::rule!( { $crate::sym($x) } $($tail)* ) };
( $x:ident $($tail:tt)* ) => { $crate::rule!( { $x.link() } $($tail)* ) };
( $a:tt -> $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).to($crate::rule!(@AS_EXPR $b)) } $($tail)*)
};
( $a:tt => $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).map($crate::rule!(@AS_EXPR $b)) } $($tail)*)
};
( $a:tt . $method:ident ( $($args:tt)* ) $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).$method($($args)*) } $($tail)*)
};
( $a:tt -& $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).delimiter_for($crate::rule!($b)) } $($tail)*)
};
( $a:tt &- $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).delimited_by($crate::rule!($b)) } $($tail)*)
};
( $a:tt & $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).then($crate::rule!($b)) } $($tail)*)
};
( $a:tt *= $b:tt $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).repeat($crate::rule!(@AS_EXPR $b)) } $($tail)*)
};
( $a:tt * $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).repeat(..) } $($tail)*)
};
( $a:tt + $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).repeat(1..) } $($tail)*)
};
( $a:tt ? $($tail:tt)* ) => {
$crate::rule!({ ($crate::rule!($a)).or_not() } $($tail)*)
};
( $a:tt | $($b:tt)* ) => {
{ ($crate::rule!($a)).or($crate::rule!($($b)*)) }
};
( | $($a:tt)* ) => {
$crate::rule!($($a)*)
};
( & $($a:tt)* ) => {
$crate::rule!($($a)*)
};
( $x:tt ) => { $x };
( $($tail:tt)* ) => {
$crate::parze_error!($($tail)*);
};
}
#[macro_export]
macro_rules! parsers {
( @NAMES ) => {};
( @NAMES $name:ident : $kind:ty = { $($rule:tt)* } $($tail:tt)* ) => {
let $name = $crate::declare();
$crate::parsers!(@NAMES $($tail)*);
};
( @NAMES $name:ident = { $($rule:tt)* } $($tail:tt)* ) => {
$crate::parsers!(@NAMES $name : _ = { $($rule)* } $($tail)*);
};
( @NAMES $($tail:tt)* ) => {
$crate::parze_error!($($tail)*);
};
( @DEFINITIONS ) => {};
( @DEFINITIONS $name:ident : $kind:ty = { $($rule:tt)* } $($tail:tt)* ) => {
let __tmp = $crate::rule!($($rule)*);
let $name : $kind = ($name).define(__tmp);
$crate::parsers!(@DEFINITIONS $($tail)*);
};
( @DEFINITIONS $name:ident = { $($rule:tt)* } $($tail:tt)* ) => {
$crate::parsers!(@DEFINITIONS $name : _ = { $($rule)* } $($tail)*);
};
( @DEFINITIONS $($tail:tt)* ) => {
$crate::parze_error!($($tail)*);
};
( $($tail:tt)* ) => {
$crate::parsers!(@NAMES $($tail)*);
$crate::parsers!(@DEFINITIONS $($tail)*);
};
}