#![no_std]
#![feature(generic_associated_types)]
#![allow(incomplete_features)]
use {
crate::iter::*,
core::{borrow::Borrow, iter::FromIterator},
};
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),
}
}
#[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 default() -> Self
where
Self::Group: FromIterator<Self>,
{
Self::from_group(None.into_iter().collect())
}
#[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())
}
fn map<E, F>(self, mut f: F) -> E
where
Self::Group: IntoIterator<Item = Self>,
E: Expression,
E::Group: FromIterator<E>,
F: FnMut(Self::Atom) -> E::Atom,
{
match self.into() {
Expr::Atom(atom) => E::from_atom(f(atom)),
Expr::Group(group) => {
E::from_group(group.into_iter().map(move |e| e.map(&mut f)).collect())
}
}
}
fn map_ref<E, F>(&self, mut f: F) -> E
where
E: Expression,
E::Group: FromIterator<E>,
F: FnMut(&Self::Atom) -> E::Atom,
{
match self.cases() {
ExprRef::Atom(atom) => E::from_atom(f(atom)),
ExprRef::Group(group) => E::from_group(
group
.iter()
.map(move |e| e.borrow().map_ref(&mut f))
.collect(),
),
}
}
fn substitute<F>(self, mut f: F) -> Self
where
Self::Group: FromIterator<Self> + IntoIterator<Item = Self>,
F: FnMut(Self::Atom) -> Self,
{
match self.into() {
Expr::Atom(atom) => f(atom),
Expr::Group(group) => Self::from_group(
group
.into_iter()
.map(move |e| e.substitute(&mut f))
.collect(),
),
}
}
fn substitute_ref<F>(&self, mut f: F) -> Self
where
Self::Group: FromIterator<Self>,
F: FnMut(&Self::Atom) -> Self,
{
match self.cases() {
ExprRef::Atom(atom) => f(atom),
ExprRef::Group(group) => Self::from_group(
group
.iter()
.map(move |e| e.borrow().substitute_ref(&mut f))
.collect(),
),
}
}
}
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())
})
}
},
}
}
}
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> From<E> for Expr<E>
where
E: Expression,
{
#[must_use]
#[inline]
fn from(e: E) -> Self {
e.into()
}
}
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> 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()
}
}
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,
}
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,
}
impl SymbolType {
#[inline]
pub fn is_whitespace<T, F>(classify: F) -> impl Fn(&T) -> bool
where
F: Fn(&T) -> SymbolType,
{
move |t| classify(t) == SymbolType::Whitespace
}
#[inline]
pub fn is_not_whitespace<T, F>(classify: F) -> impl Fn(&T) -> bool
where
F: Fn(&T) -> SymbolType,
{
move |t| classify(t) != SymbolType::Whitespace
}
}
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 stripped = iter
.into_iter()
.skip_while(SymbolType::is_whitespace(&classify))
.peekable();
match stripped.peek() {
Some(peek) => match classify(&peek) {
SymbolType::GroupOpen => parse_group_continue(&mut stripped, &classify),
SymbolType::GroupClose => Err(Error::UnopenedGroup),
_ => {
let atom = parse_atom_continue(&mut stripped, &classify)?;
if let Some(next) = stripped.next() {
match classify(&next) {
SymbolType::Whitespace => {
if stripped.any(|t| SymbolType::is_not_whitespace(&classify)(&t)) {
return Err(Error::MultiExpr);
}
}
SymbolType::GroupOpen | SymbolType::GroupClose => {
return Err(Error::MultiExpr);
}
_ => {}
}
}
Ok(E::from_atom(atom))
}
},
_ => Ok(E::from_atom(E::Atom::from_iter(None))),
}
}
#[inline]
#[track_caller]
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>,
{
parse_group_continue(&mut iter.into_iter().peekable(), classify).map(E::unwrap_group)
}
#[inline]
fn parse_group_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>,
{
parse_group_continue_at_depth(0, iter, classify)
}
fn parse_group_continue_at_depth<I, F, E>(
depth: usize,
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>,
{
let target: Result<_> = from_fn(|| match iter.peek() {
Some(peek) => match classify(&peek) {
SymbolType::Whitespace => Some(None),
SymbolType::GroupOpen => Some(Some(parse_group_continue_at_depth(
depth + 1,
iter,
&classify,
))),
SymbolType::GroupClose => None,
_ => Some(Some(parse_atom_continue(iter, &classify).map(E::from_atom))),
},
_ => Some(Some(Err(Error::OpenGroup))),
})
.filter_map(move |t| t)
.collect();
if depth == 0 && iter.any(|t| SymbolType::is_not_whitespace(&classify)(&t)) {
Err(Error::MultiExpr)
} else {
target.map(E::from_group)
}
}
#[inline]
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>,
{
parse_atom_continue(&mut iter.into_iter(), classify)
}
fn parse_atom_continue<I, F, A>(iter: &mut I, classify: F) -> Result<A>
where
I: Iterator,
F: Fn(&I::Item) -> SymbolType,
A: FromIterator<I::Item>,
{
let mut inside_quote = false;
let atom = iter
.take_while(move |t| {
if inside_quote {
if classify(&t) == SymbolType::Quote {
inside_quote = false;
}
} else {
match classify(&t) {
SymbolType::Quote => inside_quote = true,
SymbolType::Other => {}
_ => return false,
}
}
true
})
.collect();
if inside_quote {
Err(Error::MissingQuote)
} else {
Ok(atom)
}
}
#[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::Group: FromIterator<E>,
E::Atom: FromIterator<char>,
{
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>,
{
parse_group::<_, _, E>(iter, default_char_classification)
}
#[inline]
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;
}
}
}
}