Recursive Enum Types

1

Hi,

I stumbled over the fact, that the following code does not compile with rust's type system.

pub enum BTree<T> {
    Node(T),
    Branch(BTree<T>, BTree<T>)
}

test.rs:1:1: 4:2 error: invalid recursive enum type [E0072]
test.rs:1 pub enum BTree {
test.rs:2     Node(T),
test.rs:3     Branch(BTree, BTree)
test.rs:4 }

This puzzles me a bit, because I would have suspected this to work. Of course I can imagine that recursion adds a whole new set of complexity problems for the type system and probably even more so the checkers.

I then figured that probably T needed to be boxed here anyway (unless it was Sized) so I added it to the (not compiling) code:


pub enum BTree<T> {
    Node(Box<T>),
    Branch(BTree<Box<T>>, BTree<Box<T>>)
}

To my surprise this made the error a lot worse.

test.rs:3:12: 3:25 error: overflow evaluating the requirement `Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> : core::marker::Sized` [E0275]
test.rs:3     Branch(BTree<Box>, BTree<Box>)
                     ^~~~~~~~~~~~~
test.rs:3:12: 3:25 help: run `rustc --explain E0275` to see a detailed explanation
test.rs:3:12: 3:25 note: consider adding a `#![recursion_limit="128"]` attribute to your crate
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box<Box>>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box<Box>>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box<Box>>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box<Box>>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box<Box>>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box<Box>>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box<Box>>`
test.rs:3:12: 3:25 note: required because it appears within the type `BTree<Box>`
test.rs:3:12: 3:25 note: only the last field of a struct or enum variant may have a dynamically sized type
error: aborting due to previous error

Are recursive Types with type parameters to be supported at any time in the future? If not, what are the patterns to avoid this?

Why does adding Box make the compiler fail with a stack trace? Concepetionally I think it should fail with the same error as the first example.

How can I work around this kind of limitation at the moment.

2 Likes
2

Your enum is still recursive

pub enum BTree<T> {
    Node(T),
    Branch(Box<BTree<T>>, Box<BTree<T>>)
}

Boxing the T isn't necessary here, but you need to box all recursive things.

The problem with recursive enums is that they don't have a well-defined size. Something like Branch(Branch(Branch(......))) can go on forever, and the whole thing needs to be stored in statically allocated memory -- impossible for something which is possibly infinitely-sized.

Putting a Box<> around the recursive bit means that a single Btree<T> is either a node or a branch, containing pointers to other btrees. Thus, the stack representation is bounded by the size of a node or two pointers.

Recursive enums are supported as long as you use indirection.

4 Likes
3

This article would help you: r4cppp/README.md at master · nrc/r4cppp · GitHub

4

By the way, a twice branched tree is a binary tree but not a B-tree

5

<enter pedantic man>
It's could still be a valid B-tree.
<exit pedantic man>