#![no_std]
#![feature(generic_associated_types)]
#![allow(incomplete_features)]
pub const VERSION: &str = env!("CARGO_PKG_VERSION");
use {
crate::iter::*,
core::{borrow::Borrow, iter::FromIterator, str::FromStr},
};
pub trait Expression
where
Self: Into<Expr<Self>>,
{
type Atom;
type Group: IntoIteratorGen<Self>;
fn cases(&self) -> ExprRef<Self>;
fn from_atom(atom: Self::Atom) -> Self;
fn from_group(group: Self::Group) -> Self;
#[must_use]
#[inline]
fn from_expr(expr: Expr<Self>) -> Self {
match expr {
Expr::Atom(atom) => Self::from_atom(atom),
Expr::Group(group) => Self::from_group(group),
}
}
#[inline]
fn from_str(s: &str) -> parse::Result<Self>
where
Self::Atom: FromIterator<char>,
Self::Group: FromIterator<Self>,
{
parse::from_str(s)
}
#[must_use]
#[inline]
fn is_atom(&self) -> bool {
self.cases().is_atom()
}
#[must_use]
#[inline]
fn is_group(&self) -> bool {
self.cases().is_group()
}
#[must_use]
#[inline]
fn atom(self) -> Option<Self::Atom> {
self.into().atom()
}
#[must_use]
#[inline]
fn group(self) -> Option<Self::Group> {
self.into().group()
}
#[inline]
#[track_caller]
fn unwrap_atom(self) -> Self::Atom {
self.into().unwrap_atom()
}
#[inline]
#[track_caller]
fn unwrap_group(self) -> Self::Group {
self.into().unwrap_group()
}
#[inline]
fn empty_atom<T>() -> Self
where
Self::Atom: FromIterator<T>,
{
Self::from_atom(None.into_iter().collect())
}
#[inline]
fn empty_group() -> Self
where
Self::Group: FromIterator<Self>,
{
Self::from_group(None.into_iter().collect())
}
#[inline]
fn default() -> Self
where
Self::Group: FromIterator<Self>,
{
Self::empty_group()
}
#[inline]
fn clone(&self) -> Self
where
Self::Atom: Clone,
Self::Group: FromIterator<Self>,
{
Self::from_expr(self.cases().into())
}
#[inline]
fn eq<E>(&self, other: &E) -> bool
where
E: Expression,
Self::Atom: PartialEq<E::Atom>,
{
self.cases() == other.cases()
}
#[inline]
fn is_subexpression<E>(&self, other: &E) -> bool
where
E: Expression,
Self::Atom: PartialEq<E::Atom>,
{
self.cases().is_subexpression(&other.cases())
}
#[inline]
fn map<E, F>(self, f: F) -> E
where
Self::Group: IntoIterator<Item = Self>,
E: Expression,
E::Group: FromIterator<E>,
F: FnMut(Self::Atom) -> E::Atom,
{
self.into().map(f)
}
#[inline]
fn map_ref<E, F>(&self, f: F) -> E
where
E: Expression,
E::Group: FromIterator<E>,
F: FnMut(&Self::Atom) -> E::Atom,
{
self.cases().map_ref(f)
}
#[inline]
fn substitute<F>(self, f: F) -> Self
where
Self::Group: FromIterator<Self> + IntoIterator<Item = Self>,
F: FnMut(Self::Atom) -> Self,
{
self.into().substitute(f)
}
#[inline]
fn substitute_ref<F>(&self, f: F) -> Self
where
Self::Group: FromIterator<Self>,
F: FnMut(&Self::Atom) -> Self,
{
self.cases().substitute_ref(f)
}
}
pub enum ExprRef<'e, E>
where
E: 'e + Expression,
{
Atom(&'e E::Atom),
Group(<E::Group as IntoIteratorGen<E>>::IterGen<'e>),
}
impl<'e, E> ExprRef<'e, E>
where
E: Expression,
{
#[must_use]
#[inline]
pub fn is_atom(&self) -> bool {
matches!(self, ExprRef::Atom(_))
}
#[must_use]
#[inline]
pub fn is_group(&self) -> bool {
matches!(self, ExprRef::Group(_))
}
#[must_use]
#[inline]
pub fn atom(self) -> Option<&'e E::Atom> {
match self {
ExprRef::Atom(atom) => Some(atom),
_ => None,
}
}
#[must_use]
#[inline]
pub fn group(self) -> Option<<E::Group as IntoIteratorGen<E>>::IterGen<'e>> {
match self {
ExprRef::Group(group) => Some(group),
_ => None,
}
}
#[inline]
#[track_caller]
pub fn unwrap_atom(self) -> &'e E::Atom {
self.atom().unwrap()
}
#[inline]
#[track_caller]
pub fn unwrap_group(self) -> <E::Group as IntoIteratorGen<E>>::IterGen<'e> {
self.group().unwrap()
}
pub fn is_subexpression<'r, R>(&self, other: &ExprRef<'r, R>) -> bool
where
R: Expression,
E::Atom: PartialEq<R::Atom>,
{
match self {
ExprRef::Atom(atom) => match other {
ExprRef::Atom(other) => atom == other,
ExprRef::Group(other) => other
.iter()
.any(move |e| self.is_subexpression(&e.borrow().cases())),
},
ExprRef::Group(group) => match other {
ExprRef::Atom(_) => false,
ExprRef::Group(other) => {
other
.iter()
.any(move |e| self.is_subexpression(&e.borrow().cases()))
|| eq_by(group.iter(), other.iter(), move |l, r| {
l.borrow().eq(r.borrow())
})
}
},
}
}
#[inline]
pub fn map_ref<O, F>(&self, mut f: F) -> O
where
O: Expression,
O::Group: FromIterator<O>,
F: FnMut(&E::Atom) -> O::Atom,
{
self.map_ref_inner(&mut f)
}
#[inline]
fn map_ref_inner<O, F>(&self, f: &mut F) -> O
where
O: Expression,
O::Group: FromIterator<O>,
F: FnMut(&E::Atom) -> O::Atom,
{
match self {
ExprRef::Atom(atom) => O::from_atom(f(atom)),
ExprRef::Group(group) => O::from_group(
group
.iter()
.map(move |e| e.borrow().cases().map_ref_inner(f))
.collect(),
),
}
}
#[inline]
pub fn substitute_ref<F>(&self, mut f: F) -> E
where
E::Group: FromIterator<E>,
F: FnMut(&E::Atom) -> E,
{
self.substitute_ref_inner(&mut f)
}
#[inline]
fn substitute_ref_inner<F>(&self, f: &mut F) -> E
where
E::Group: FromIterator<E>,
F: FnMut(&E::Atom) -> E,
{
match self {
ExprRef::Atom(atom) => f(atom),
ExprRef::Group(group) => E::from_group(
group
.iter()
.map(move |e| e.borrow().cases().substitute_ref_inner(f))
.collect(),
),
}
}
}
impl<'l, 'r, L, R> PartialEq<ExprRef<'r, R>> for ExprRef<'l, L>
where
L: Expression,
R: Expression,
L::Atom: PartialEq<R::Atom>,
{
fn eq(&self, other: &ExprRef<'r, R>) -> bool {
match (self, other) {
(ExprRef::Atom(lhs), ExprRef::Atom(rhs)) => *lhs == *rhs,
(ExprRef::Group(lhs), ExprRef::Group(rhs)) => {
eq_by(lhs.iter(), rhs.iter(), move |l, r| {
l.borrow().eq(r.borrow())
})
}
_ => false,
}
}
}
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum Expr<E>
where
E: Expression,
{
Atom(E::Atom),
Group(E::Group),
}
impl<'e, E> From<ExprRef<'e, E>> for Expr<E>
where
E::Atom: Clone,
E::Group: FromIterator<E>,
E: Expression,
{
#[must_use]
#[inline]
fn from(expr_ref: ExprRef<'e, E>) -> Self {
match expr_ref {
ExprRef::Atom(atom) => Self::Atom(atom.clone()),
ExprRef::Group(group) => {
Self::Group(group.iter().map(move |e| e.borrow().clone()).collect())
}
}
}
}
impl<E> FromStr for Expr<E>
where
E: Expression,
E::Atom: FromIterator<char>,
E::Group: FromIterator<E>,
{
type Err = parse::Error;
#[inline]
fn from_str(s: &str) -> Result<Self, Self::Err> {
E::from_str(s).map(E::into)
}
}
impl<E> Expr<E>
where
E: Expression,
{
#[must_use]
#[inline]
pub fn is_atom(&self) -> bool {
matches!(self, Expr::Atom(_))
}
#[must_use]
#[inline]
pub fn is_group(&self) -> bool {
matches!(self, Expr::Group(_))
}
#[must_use]
#[inline]
pub fn atom(self) -> Option<E::Atom> {
match self {
Expr::Atom(atom) => Some(atom),
_ => None,
}
}
#[must_use]
#[inline]
pub fn group(self) -> Option<E::Group> {
match self {
Expr::Group(group) => Some(group),
_ => None,
}
}
#[inline]
#[track_caller]
pub fn unwrap_atom(self) -> E::Atom {
self.atom().unwrap()
}
#[inline]
#[track_caller]
pub fn unwrap_group(self) -> E::Group {
self.group().unwrap()
}
#[inline]
pub fn map<O, F>(self, mut f: F) -> O
where
E::Group: IntoIterator<Item = E>,
O: Expression,
O::Group: FromIterator<O>,
F: FnMut(E::Atom) -> O::Atom,
{
self.map_inner(&mut f)
}
fn map_inner<O, F>(self, f: &mut F) -> O
where
E::Group: IntoIterator<Item = E>,
O: Expression,
O::Group: FromIterator<O>,
F: FnMut(E::Atom) -> O::Atom,
{
match self {
Expr::Atom(atom) => O::from_atom(f(atom)),
Expr::Group(group) => O::from_group(
group
.into_iter()
.map(move |e| e.into().map_inner(f))
.collect(),
),
}
}
#[inline]
pub fn substitute<F>(self, mut f: F) -> E
where
E::Group: FromIterator<E> + IntoIterator<Item = E>,
F: FnMut(E::Atom) -> E,
{
self.substitute_inner(&mut f)
}
fn substitute_inner<F>(self, f: &mut F) -> E
where
E::Group: FromIterator<E> + IntoIterator<Item = E>,
F: FnMut(E::Atom) -> E,
{
match self {
Expr::Atom(atom) => f(atom),
Expr::Group(group) => E::from_group(
group
.into_iter()
.map(move |e| e.into().substitute_inner(f))
.collect(),
),
}
}
}
impl<E> Default for Expr<E>
where
E: Expression,
E::Group: FromIterator<E>,
{
fn default() -> Self {
E::default().into()
}
}
pub mod parse {
use {
super::Expression,
core::{
iter::{from_fn, FromIterator, Peekable},
result,
},
};
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum Error {
MultiExpr,
MissingQuote,
OpenGroup,
UnopenedGroup,
BadEmptyGroup,
LeadingWhitespace,
TrailingSymbols,
BadOpenGroup,
BadStartAtom,
}
pub type Result<T> = result::Result<T, Error>;
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum SymbolType {
Whitespace,
GroupOpen,
GroupClose,
Quote,
Other,
}
pub fn parse<I, F, E>(iter: I, classify: F) -> Result<E>
where
I: IntoIterator,
F: Fn(&I::Item) -> SymbolType,
E: Expression,
E::Atom: FromIterator<I::Item>,
E::Group: FromIterator<E>,
{
let mut iter = iter.into_iter().peekable();
if let Some(true) = iter.peek().map(|p| classify(p) == SymbolType::Whitespace) {
return Err(Error::LeadingWhitespace);
}
let expr = parse_continue(&mut iter, &classify);
iter.next()
.map(move |_| Err(Error::MultiExpr))
.unwrap_or(expr)
}
pub fn parse_continue<I, F, E>(iter: &mut Peekable<I>, classify: F) -> Result<E>
where
I: Iterator,
F: Fn(&I::Item) -> SymbolType,
E: Expression,
E::Atom: FromIterator<I::Item>,
E::Group: FromIterator<E>,
{
match iter.peek() {
Some(peek) => match classify(&peek) {
SymbolType::GroupClose => Err(Error::UnopenedGroup),
SymbolType::GroupOpen => {
parse_group_continue::<_, _, E>(iter, &classify).map(E::from_group)
}
_ => parse_atom_continue(iter, &classify).map(E::from_atom),
},
_ => Ok(E::empty_atom()),
}
}
pub fn parse_group<I, F, E>(iter: I, classify: F) -> Result<E::Group>
where
I: IntoIterator,
F: Fn(&I::Item) -> SymbolType,
E: Expression,
E::Atom: FromIterator<I::Item>,
E::Group: FromIterator<E>,
{
let mut iter = iter.into_iter().peekable();
let group = parse_group_continue::<_, _, E>(&mut iter, &classify);
iter.next()
.map(move |_| Err(Error::TrailingSymbols))
.unwrap_or(group)
}
pub fn parse_group_continue<I, F, E>(iter: &mut Peekable<I>, classify: &F) -> Result<E::Group>
where
I: Iterator,
F: Fn(&I::Item) -> SymbolType,
E: Expression,
E::Atom: FromIterator<I::Item>,
E::Group: FromIterator<E>,
{
match iter.peek() {
Some(peek) => match classify(&peek) {
SymbolType::Whitespace => return Err(Error::LeadingWhitespace),
SymbolType::GroupClose => return Err(Error::UnopenedGroup),
SymbolType::GroupOpen => {
let _ = iter.next();
}
_ => return Err(Error::BadStartAtom),
},
_ => return Err(Error::BadEmptyGroup),
}
from_fn(parse_group_continue_inner(iter, classify)).collect()
}
#[inline]
fn parse_group_continue_inner<'f, I, F, E>(
iter: &'f mut Peekable<I>,
classify: &'f F,
) -> impl 'f + FnMut() -> Option<Result<E>>
where
I: Iterator,
F: 'f + Fn(&I::Item) -> SymbolType,
E: Expression,
E::Atom: FromIterator<I::Item>,
E::Group: FromIterator<E>,
{
move || loop {
match iter.peek() {
Some(peek) => match classify(&peek) {
SymbolType::Whitespace => {
let _ = iter.next();
}
SymbolType::GroupClose => {
let _ = iter.next();
return None;
}
SymbolType::GroupOpen => {
return Some(
parse_group_continue::<_, _, E>(iter, classify).map(E::from_group),
);
}
_ => return Some(parse_atom_continue(iter, classify).map(E::from_atom)),
},
_ => return Some(Err(Error::OpenGroup)),
}
}
}
pub fn parse_atom<I, F, A>(iter: I, classify: F) -> Result<A>
where
I: IntoIterator,
F: Fn(&I::Item) -> SymbolType,
A: FromIterator<I::Item>,
{
let mut iter = iter.into_iter().peekable();
if let Some(peek) = iter.peek() {
match classify(&peek) {
SymbolType::Whitespace => return Err(Error::LeadingWhitespace),
SymbolType::GroupClose => return Err(Error::UnopenedGroup),
SymbolType::GroupOpen => return Err(Error::BadOpenGroup),
_ => {}
}
}
let atom = parse_atom_continue(&mut iter, &classify);
iter.next()
.map(move |_| Err(Error::TrailingSymbols))
.unwrap_or(atom)
}
pub fn parse_atom_continue<I, F, A>(iter: &mut Peekable<I>, classify: &F) -> Result<A>
where
I: Iterator,
F: Fn(&I::Item) -> SymbolType,
A: FromIterator<I::Item>,
{
let mut inside_quote = false;
let atom = from_fn(parse_atom_continue_inner(iter, classify, &mut inside_quote)).collect();
if inside_quote {
Err(Error::MissingQuote)
} else {
Ok(atom)
}
}
#[inline]
fn parse_atom_continue_inner<'f, I, F>(
iter: &'f mut Peekable<I>,
classify: &'f F,
inside_quote: &'f mut bool,
) -> impl 'f + FnMut() -> Option<I::Item>
where
I: Iterator,
F: 'f + Fn(&I::Item) -> SymbolType,
{
move || match iter.peek() {
Some(peek) => {
if *inside_quote {
if classify(&peek) == SymbolType::Quote {
*inside_quote = false;
}
} else {
match classify(&peek) {
SymbolType::Quote => *inside_quote = true,
SymbolType::Other => {}
_ => return None,
}
}
iter.next()
}
_ => None,
}
}
#[inline]
pub fn default_char_classification(c: &char) -> SymbolType {
match c {
'(' => SymbolType::GroupOpen,
')' => SymbolType::GroupClose,
'"' => SymbolType::Quote,
c => {
if c.is_whitespace() {
SymbolType::Whitespace
} else {
SymbolType::Other
}
}
}
}
#[inline]
pub fn from_chars<I, E>(iter: I) -> Result<E>
where
I: IntoIterator<Item = char>,
E: Expression,
E::Atom: FromIterator<char>,
E::Group: FromIterator<E>,
{
parse(iter, default_char_classification)
}
#[inline]
pub fn from_str<S, E>(s: S) -> Result<E>
where
S: AsRef<str>,
E: Expression,
E::Atom: FromIterator<char>,
E::Group: FromIterator<E>,
{
from_chars(s.as_ref().chars())
}
#[inline]
#[track_caller]
pub fn from_chars_as_group<I, E>(iter: I) -> Result<E::Group>
where
I: IntoIterator<Item = char>,
E: Expression,
E::Atom: FromIterator<char>,
E::Group: FromIterator<E>,
{
from_chars(Some('(').into_iter().chain(iter).chain(Some(')'))).map(E::unwrap_group)
}
#[inline]
#[track_caller]
pub fn from_str_as_group<S, E>(s: S) -> Result<E::Group>
where
S: AsRef<str>,
E: Expression,
E::Atom: FromIterator<char>,
E::Group: FromIterator<E>,
{
from_chars_as_group::<_, E>(s.as_ref().chars())
}
}
pub mod iter {
use core::borrow::Borrow;
pub trait IteratorGen<T> {
type Item<'t>: Borrow<T>
where
T: 't;
type Iter<'t>: Iterator<Item = Self::Item<'t>>
where
T: 't;
fn iter(&self) -> Self::Iter<'_>;
}
pub trait IntoIteratorGen<T> {
type IterGen<'t>: IteratorGen<T>
where
T: 't;
fn gen(&self) -> Self::IterGen<'_>;
}
pub(crate) fn eq_by<L, R, F>(lhs: L, rhs: R, mut eq: F) -> bool
where
L: IntoIterator,
R: IntoIterator,
F: FnMut(L::Item, R::Item) -> bool,
{
let mut lhs = lhs.into_iter();
let mut rhs = rhs.into_iter();
loop {
let x = match lhs.next() {
None => return rhs.next().is_none(),
Some(val) => val,
};
let y = match rhs.next() {
None => return false,
Some(val) => val,
};
if !eq(x, y) {
return false;
}
}
}
}