The basic problem of this is that any scheme that doesn't use Dyn memory allocation can't allow mutation, since mutation can result in arbitrarily increasing the size required to store the type.
Even with a read-only approach, the approach proposed in the OP makes field lookup O(n) in the size of the preceding fields, which means that it is better represented with an iterator over the tree.
Alternatively, one could include the field offsets in the type, which would result in a read-only O(1) field lookup implementation, with some tradeoffs on how to store the fields (64-bit integer is fastest but most space-consuming, variable-sized int is tersest but most time-consuming).
Currently the best approach would be to write a macro to generate whatever is best for your use case, or just use Box if mutability is needed or optimization isn't critical.
This is an implementation supporting both mutable, indexed and iterator-based types.
pub enum Symbol<T = ()> {
Constant(NumberType),
NamedVariable(VarID),
Addition(T, T),
Multiplication(T, T),
Negation(T),
Reciprocal(T),
}
mod dyn_box {
/// SAFETY: layout_for(x.clone()) == layout_of(construct(x))
unsafe trait DynSize {
fn layout_of(&'a self) -> std::alloc::Layout;
}
/// SAFETY: layout_for(x.clone()) == layout_of(construct(x))
unsafe trait DynFrom<T> {
fn layout_for(x: &T) -> std::alloc::Layout;
fn construct<'a>(mem: &'a mut [MaybeUninit<u8>], x: T) -> &'a mut Self;
}
#[repr(transparent)]
pub struct DynBox<T: DynSize>(Pin<&'static mut T>);
impl<T: DynSize> DynBox<T> {
pub fn new<U>(x: U) -> Self where T: DynFrom<U> {
let layout = T::layout_for(&x);
let mem = alloc(layout);
Self(transmute(T::construct(mem, x)))
}
}
impl<T: DynSize> Drop for DynBox<T> {
fn drop(&mut self) {
let layout = T::layout_of(self.ptr);
drop_in_place(self.0);
dealloc(self.0, layout);
}
}
impl<T: DynSize> Deref for DynBox<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
self.0
}
}
impl<T: DynSize> DynBox<T> {
fn get_mut(&mut self) -> Pin<&mut T> {
self.0
}
}
}
mod tree {
use super::dyn_box::*;
trait NumChildren {
fn num_children(&self) -> usize
}
trait Children: NumChildren {
fn children(&self, first: usize, out: &mut [&Self]);
}
trait SetChild<T>: NumChildren {
fn set_child(self: Pin<&mut self>, idx: usize, value: T) -> T;
}
/// offsets so field access is O(1)
pub struct RaTree<T: NumChildren> {
pub head: T,
offsets: [usize; 0],
pinned: PhantomPinned,
tail: ()
}
impl<T: NumChildren> NumChildren for RaTree<T> {
fn num_children(&self) -> usize {self.head.num_children()}
}
impl<T: NumChildren> DynSize for RaTree<T> {
fn layout_of(&self) -> Layout {
// iteratively visit rightmost parent
}
}
impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for RaTree<T> {
// ...
}
/// Some(Tree) when opening a tree node, None when closing a tree node
impl<'a, T: NumChildren> IntoIterator for &'a RaTree<T> {
type Item = Option<T>;
// ...
}
impl<T: NumChildren> Deref for RaTree<T> {
type Target = T;
}
/// No offsets so field lookup is O(n)
pub struct IterTree<T: NumChildren> {
pub head: T,
pinned: PhantomPinned,
tail: ()
}
impl<T: NumChildren> NumChildren for IterTree<T> {
fn num_children(&self) -> usize {self.head.num_children()}
}
impl DynSize for IterTree {
fn layout_of(&self) -> Layout {
Self::layout_for(&self)
}
}
impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for IterTree<T> {
// ...
}
/// Some(Tree) when opening a tree node, None when closing a tree node
impl<'a, T: NumChildren> IntoIterator for &'a IterTree<T> {
type Item = Option<T>;
// ...
}
#[repr(trasparent)]
pub struct IterTreeChildrenIsSlow<T: NumChildren>(pub IterTree<T>);
impl<T: NumChildren> Children for IterTreeChildrenIsSlow<T> {
fn children(&self, first: usize, out: &mut [&Self]) {
// call layout_of on non-last children to compute size and thus offset of next child
}
}
impl<T: NumChildren> Deref for RaTree<T> {
type Target = T;
}
pub struct MutTree<T: NumChildren> {
pub head: T,
pinned: PhantomPinned,
tail: [DynBox<MutTree<T>>; 0]
}
impl<T: NumChildren> NumChildren for MutTree<T> {
fn num_children(&self) -> usize {self.head.num_children()}
}
impl DynSize for MutTree {
fn layout_of(&self) -> Layout {
}
}
impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for MutTree<T> {
// ...
}
/// Some(Tree) when opening a tree node, None when closing a tree node
impl<'a, T: NumChildren> IntoIterator for &'a MutTree<T> {
type Item = Option<T>;
// ...
}
impl<T: NumChildren> Children for MutTree<T> {
fn children(&self, first: usize, out: &mut [&Self]) {
}
}
impl<T: NumChildren> SetChild<DynBox<MutTree<T>>> for MutTree<T> {
}
impl<T: NumChildren> Deref for MutTree<T> {
type Target = T;
}
}
use tree:*;
impl<T> NumChildren for Symbol<T> {
fn num_children(&'a self) -> usize {
match self.deref() {
Symbol::Addition(_, _) => 2,
...
}
}
}
trait AsSymbol {
fn as_symbol(&'a self) -> Symbol<&'a Self>;
}
impl<T: Children + Deref<Item = Symbol>> AsSymbol for T
{
fn as_symbol(&'a self) -> Symbol<&'a Self> {
match self.deref() {
Symbol::Addition(_, _) => {let mut c = [self; 2]; self.children(0, &mut c); Symbol::Addition(c[0], c[1])},
...
}
}
}
type RaSymbol = RaTree<Symbol>;
type IterSymbol = IterTree<Symbol>;
type MutSymbol = MutTree<Symbol>;
type RaSymbolRef<'a> = Symbol<&'a RaSymbol>;
type IterSymbolRef<'a> = Symbol<&'a IterSymbol>;
type MutSymbolRef<'a> = Symbol<&'a MutSymbol>;
type BoxRaSymbol = DynBox<RaSymbol>;
type BoxIterSymbol = DynBox<IterSymbol>;
type BoxMutSymbol = DynBox<MutSymbol>;
For matching, match on symbol.as_symbol() for RaTree/MutTree or *symbol for any trees.