Builder API on a Tree

[cyypherus]

Hello! I would love to be able to implement a builder API with this tree + it's generic constraints, but it seems I've run into a limitation of rust.

trait Scopable: Sized {
    type SubType: Scopable;
}

enum Tree<T: Scopable> {
    Group(Vec<Tree<T>>),
    Subtree(Box<Tree<T::SubType>>),
    Leaf(T),
}

impl<T: Scopable> Tree<T> {
    fn foo(self) -> Self { // error[E0320]: overflow while adding drop-check rules for Tree<T>
        self
    }
}

Is there a workaround that would allow me to do this? I did notice that using references in foo do not trigger the drop check overflow, but I can't implement a builder pattern without owned values.

If possible, I would also like to understand a little better why this type is problematic when it is conceptually just as infinite as a recursing enum with no trait constraints.

Is it a limitation of rust's design or a bad idea on my part? It is often hard to distinguish the two

Thank you in advance

Rust Playground

[jumpnbrownweasel]

I'm not a Rust type system expert, but I don't see what would cause the recursion in this trait to terminate.

        trait Scopable: Sized {
            type SubType: Scopable;
        }

[cyypherus]

The terminating type can use a subtype of () which can use a subtype of itself.

It does compile & the type can be meaningfully used without the foo function.

[quinedot]

You could comment here or open a new issue since your use case does not unconditionally introduce a type of infinite length. (No need for recursion to bottom out; I think it just needs to be able to normalize.)

It's also easy to hit an ICE with small modifications to your example. That's this issue, I'm pretty sure. You could add your example there too.

I don't know if there are any workarounds or if supporting the OP is feasible or not.

[quinedot]

@quinedot

any workarounds

// Abritrary self-type workaround too 😅
trait ScopableBuilder {
    fn foo(self) -> Self;
}

//                                    vvvvvvvvvvvvvvvvvvvvv
impl<T: Scopable> ScopableBuilder for ManuallyDrop<Tree<T>> {
    fn foo(self) -> Self {
        self
    }
}

Rust Playground

Probably only a context with a normalized type could pull the inner tree out. So a builder pattern where a separate builder holds the ManuallyDrop<_> would still probably not be complete (you couldn't have a fully generic finalize(self) -> Tree<T> method.

(Higher-level workaround: use the &mut self builder pattern instead.)

[quinedot]

Sorry for the flood of replies, but I realized there may be an actually palatable workaround.

struct Subtree<T: Scopable>(ManuallyDrop<Box<Tree<T::SubType>>>);

impl<T: Scopable> Drop for Subtree<T> { ... }

impl<T: Scopable> DerefMut for Subtree<T> { ... }
impl<T: Scopable> Deref for Subtree<T> {
    type Target = Tree<T::SubType>;
    ...
}

enum Tree<T: Scopable> {
    Group(Vec<Tree<T>>),
    Subtree(Subtree<T>),
    Leaf(T),
}

Rust Playground