Where is the recursion in my (non-)recursive type?


Unfortunately, my minimal repro doesn’t seem to be very minimal :frowning: On the plus side, I think this problem is either a “just a minor syntax problem” or a “you are doing it so completely wrong I’ll rewrite it in six lines of code” problem.


In words, I’ve got a trait, ListIterThing, and a struct MetaIter that has a field pointing to Box<ListIterThing>.

Both the struct and the trait implement IntoIter for references, and both IntoIter return a clone of the underlying values.

All the structs and implementations compile, but when I go to use them, I get a fascinating overflow evaluating the requirement '&_: std::marker::Sized'. It’s the most awe-inspiring Rust error I’ve encountered yet. :slight_smile:

I seem to have hidden a recursive unsized type in my code somehow, and I can’t find it.

Getting iteration to cooperate has been the hardest thing I’ve encountered in Rust, especially once I throw in traits.



You don’t get to exclude any structure from being capable of implementing a Trat.
It is just an oddity that the evaluation is done when you construct rather than define the impl.
More minimal

trait It{}
struct MetaIter<T> where for<'a> &'a T: It { list: T }
impl<'r, T> It for &'r MetaIter<T> where for<'a> &'a T: It {}
let meta = MetaIter { list: () };


Wow, I dock myself all the points for not reducing the problem further.

So going from Jonh’s example instead of my own, the problem is that it would never be legal to write:

let something: MetaIter<MetaIter> = ...

and so Rust chokes.

Going back to my code, is there a way that works to wrap a struct that is IntoIterator with another one that is IntoIterator for the same struct? I could do it without traits (ie: add an iter() method), but I have been under the impression that I should try and use IntoIterator when possible, for convention’s sake.



I made a version that doesn’t use IntoIter here. It returns a Box from the iteration functions. I had to search all over the web to find the Box<X + 'lifetime> syntax, and I still don’t fully understand what’s going on there.

It seems it’s not possible to do what I want to do using IntoIterator, though, because of the way I’m implementing it only for the & type.



I’m not sure exactly which part you don’t understand.

The box is just a heap allocation, since you can’t know the exact final layout of the data ahead of time (because self references structure), so instead of storing it in the stack you need to store it in the heap which is more flexible with sizing and doesn’t have to be setup at compile time by the compiler.

The angle brackets just specify extra type information to the compiler, like attaching lifetimes or telling which type you want to use (when using generics, since there could be multiple choices for which type to use)



Thanks, that makes more sense.

It’s specifically the + 'lifetime syntax that I couldn’t find documentation for. Is that unique to Box because it’s a smart pointer, or is it more widely applicable? It seems unusual to me because everywhere else I’ve seen, lifetimes are documenting facts that the compiler confirms to be true. But in this case, it feels like the lifetime is actually causing the compiler to make a decision about how long the Box has to live.

Not sure if that made sense, so I’ll try again:

In a line like impl<'a> MyStruct<'a>, I am telling the compiler, “MyStruct has to live as long as 'a, as do any references attached to a given MyStruct that are also flagged as 'a, can you please confirm that I didn’t mess this up anywhere?” It’s entirely static analysis.

But in a line like fn a_function<'a>(&'a self) -> Box<Iterator<Item = T>> + 'a>, I feel like I’m telling the compiler, “When you construct this Box, please attach the lifetime 'a to it for future lifetime checks.” In this case, it’s an actual instruction that changes compiler behaviour/decisions.



The syntax is confusing because Trait Objects are being used. Trait Objects are a mechanism to erase type information (regarding data layout, for instance) so that only the bare minimum is kept: the behavior.

The full syntax being (wrapping them behind a Box pointer):

// In general
Box<dyn(Trait1 + Trait2 + ... + TraitN + 'lifetime1 + 'lifetime2 + ... + 'lifetimeN)>
/* meaning:
  - a `Box`ed something, where the only thing that is known about something is that:
  - it **outlives** all the lifetimes enumerated above,
  - it has all the object-safe methods of all the traits enumerated above,

// In practice:
Box<Trait> == Box<dyn(Trait + 'static)> // i.e. it **outlives everything**

// So to get a looser bound,
// you can for some lifetime parameter 'a, 
Box<dyn(Trait + 'a)> // it just has to outlive 'a

More about lifetimes of trait objects here: Inference of Trait Object lifetimes

Regarding object-safe methods: Object safety is required for trait objects

1 Like


Now I have looked at your code and what you were trying to accomplish, and here is a version without Trait Objects.


trait ListIterThing<'a> {
    type SomeThing : Clone;

    /// We are not allowed to return an existential `impl Iterator<Item = Self::SomeThing>` here
    fn iter_things (&'a self) -> Self::Iter;

    /// We thus need to explicitly the output type so that we can bound it    
    type Iter : Iterator<Item = Self::SomeThing>;

    // This will need that we have a way to have `Self::Iter` depend on the lifetime
    // parameter of the `&self` borrow,
    // which in turn "infects" the trait by having to add the lifetime parameter.

// Which, in turn, gets uglier later on...

Be warned, though, that it involves its fair share of Higher-Rank Trait Bounds given the lack of GATs.

So, long story short, you are trying to write something that is very hard to express right in Rust, but Rust is working to make it simpler (c.f., GATs)

1 Like


Thank you so much for the clear explanation and links. I’m happy to hear that this is “very hard to express right in Rust” because I was feeling exceptionally incompetent. :wink: Iteration was not something that I expected to trip me up.



The issue came from the lifetime parameter in iter_things(&'iter self) (in hindsight I should have renamed it everywhere to 'iter; the could would have been a little bit more readable).

I think that changing the trait to using into_iter_things(self) (thus requiring an explicit .clone() call before iterating) would have made the code much simpler.