use alloc::vec::Vec;
use core::hash::{Hash, Hasher};
use core::slice;
use token_lang::{Span, Token};
use crate::Context;
#[derive(Debug, Eq)]
pub enum Tree<K> {
Token {
token: Token<K>,
ctx: Context,
},
Group {
open: Token<K>,
close: Token<K>,
trees: Vec<Tree<K>>,
},
}
impl<K> Tree<K> {
#[inline]
#[must_use]
pub const fn token(kind: K, span: Span) -> Self {
Self::Token {
token: Token::new(kind, span),
ctx: Context::ROOT,
}
}
#[inline]
#[must_use]
pub const fn span(&self) -> Span {
match self {
Self::Token { token, .. } => token.span,
Self::Group { open, close, .. } => open.span.merge(close.span),
}
}
pub fn dismantle(trees: impl IntoIterator<Item = Self>) {
let mut stack: Vec<Self> = trees.into_iter().collect();
while let Some(tree) = stack.pop() {
if let Self::Group { trees, .. } = tree {
stack.extend(trees);
}
}
}
}
struct CloneFrame<'a, K> {
open: Token<K>,
close: Token<K>,
rest: slice::Iter<'a, Tree<K>>,
trees: Vec<Tree<K>>,
}
impl<'a, K: Clone> CloneFrame<'a, K> {
fn new(open: &Token<K>, close: &Token<K>, trees: &'a [Tree<K>]) -> Self {
Self {
open: open.clone(),
close: close.clone(),
rest: trees.iter(),
trees: Vec::with_capacity(trees.len()),
}
}
}
impl<K: Clone> Clone for Tree<K> {
fn clone(&self) -> Self {
let (open, close, trees) = match self {
Self::Token { token, ctx } => {
return Self::Token {
token: token.clone(),
ctx: *ctx,
};
}
Self::Group { open, close, trees } => (open, close, trees),
};
let mut stack = Vec::new();
let mut frame = CloneFrame::new(open, close, trees);
loop {
match frame.rest.next() {
Some(Self::Token { token, ctx }) => frame.trees.push(Self::Token {
token: token.clone(),
ctx: *ctx,
}),
Some(Self::Group { open, close, trees }) => {
let child = CloneFrame::new(open, close, trees);
stack.push(core::mem::replace(&mut frame, child));
}
None => {
let done = Self::Group {
open: frame.open,
close: frame.close,
trees: frame.trees,
};
match stack.pop() {
Some(parent) => {
frame = parent;
frame.trees.push(done);
}
None => return done,
}
}
}
}
}
}
impl<K: PartialEq> PartialEq for Tree<K> {
fn eq(&self, other: &Self) -> bool {
let mut stack: Vec<(slice::Iter<'_, Self>, slice::Iter<'_, Self>)> = Vec::new();
let mut pair = (self, other);
loop {
match pair {
(
Self::Token { token, ctx },
Self::Token {
token: other_token,
ctx: other_ctx,
},
) => {
if token != other_token || ctx != other_ctx {
return false;
}
}
(
Self::Group { open, close, trees },
Self::Group {
open: other_open,
close: other_close,
trees: other_trees,
},
) => {
if open != other_open
|| close != other_close
|| trees.len() != other_trees.len()
{
return false;
}
stack.push((trees.iter(), other_trees.iter()));
}
_ => return false,
}
loop {
let Some((left, right)) = stack.last_mut() else {
return true;
};
if let (Some(a), Some(b)) = (left.next(), right.next()) {
pair = (a, b);
break;
}
let _ = stack.pop();
}
}
}
}
impl<K: Hash> Hash for Tree<K> {
fn hash<H: Hasher>(&self, state: &mut H) {
let mut stack: Vec<slice::Iter<'_, Self>> = Vec::new();
let mut next = Some(self);
while let Some(tree) = next {
match tree {
Self::Token { token, ctx } => {
state.write_isize(0);
token.hash(state);
ctx.hash(state);
}
Self::Group { open, close, trees } => {
state.write_isize(1);
open.hash(state);
close.hash(state);
state.write_usize(trees.len());
stack.push(trees.iter());
}
}
next = None;
while let Some(children) = stack.last_mut() {
if let Some(child) = children.next() {
next = Some(child);
break;
}
let _ = stack.pop();
}
}
}
}
#[cfg(test)]
mod tests {
use alloc::vec;
use super::*;
#[test]
fn test_token_uses_root_context() {
let tree = Tree::token(1u8, Span::new(0, 1));
assert_eq!(
tree,
Tree::Token {
token: Token::new(1, Span::new(0, 1)),
ctx: Context::ROOT
}
);
}
#[test]
fn test_group_span_covers_both_delimiters() {
let tree = Tree::Group {
open: Token::new(0u8, Span::new(3, 4)),
close: Token::new(1u8, Span::new(9, 10)),
trees: vec![Tree::token(2u8, Span::new(5, 6))],
};
assert_eq!(tree.span(), Span::new(3, 10));
}
}