Rust recursive type difficulty

Question

This code is a simplification of more complex code to isolate the issue:

use std::marker::PhantomData;

pub trait ExtWrite {
    fn write_end<W>(&mut self, &mut W);
}

pub struct ST;

impl ExtWrite for ST {
    fn write_end<W>(&mut self, _: &mut W) {}
}

struct MCW<'a, 'b, W: 'a, EW: 'b + ExtWrite>(&'a mut W, &'b mut [EW]);

impl<'a, 'b, W: 'a, EW: 'b + ExtWrite> MCW<'a, 'b, W, EW> {
    fn write_end_all(&mut self) {
        if let Some((f, last)) = self.1.split_first_mut() {
            let mut el = MCW(self.0, last);
            f.write_end(&mut el);
            // do on current el.write_end();
        }
    }
}

pub fn rec_test() {
    let mut buff = ();
    let v: Vec<TSW<ST>> = Vec::new();
    let mut el: TSW<ST> = TSW(Box::new(v), PhantomData);
    el.write_end(&mut buff);
}

pub struct TSW<E: ExtWrite>(Box<Vec<TSW<E>>>, PhantomData<E>);

impl<E: ExtWrite> ExtWrite for TSW<E> {
    fn write_end<W>(&mut self, w: &mut W) {
        let mut el = MCW(w, &mut self.0[..]);
        el.write_end_all();
    }
}

fn main() {}

Leads to the following error:

error: reached the recursion limit while instantiating `<TSW<E> as ExtWrite><ST>::write_end::<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<MCW<(), TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>, TSW<ST>>>`
  --> <anon>:40:3
   |
40 |   fn write_end<W>(&mut self, w: &mut W) {
   |   ^

I am using Rust nightly (9c31d76e9 2016-10-03).

The code is a struct containing a pointer to a Vec of an array of the same struct kind. Those imbricated arrays are called recursively to apply some writing in a writer (the W trait constraint was removed because it is not relevant for the issue), and in the real code the ExtWrite becomes Writer in some cases.

There is some place where trait resolution goes funky leading to the recursion on type, the recursion seems fairly logical when considering monomorphism in the resolution of the W trait. MCW, depending on the depth of the recursion, will contain an infinite number of possible types, but this is really related to the usage of MCW (needed in original code), and the fact that W parameters of read_end functions are not linked to the struct definition but with the infinite possible variation of this function.

Yet, in this snippet, W is always () and MCW should always be MCW<(),TSW<ST>>.

A similar case that I encountered when looking for simplification:

struct IntSt<'a, W: 'a>(&'a W);

pub fn comp_err() {
    let w: u8 = 0;
    rec(true, &w);
}

pub struct A(bool);

fn rec<W>(b: bool, w: &W) {
    if (b) {
        rec(false, &IntSt(w).0);
        //      rec(false, w)
    }
}

fn main() {}

Resulting in:

error: reached the recursion limit while instantiating `rec::<&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&u8>`
  --> <anon>:14:1
   |
14 | fn rec<W>(b: bool, w: &W) {
   | ^

It behaves correctly with this, but I do not really see how to make this kind of change in my previous case:

struct IntSt<'a, W: 'a>(&'a W);

pub fn comp_err() {
    let w: u8 = 0;
    rec(true, &w);
}

pub struct A(bool);

fn rec<W>(b: bool, w: &W) {
    if (b) {
        rec(false, IntSt(w).0);
        //      rec(false, w)
    }
}

fn main() {}

It looks like MCW, a light structure used as a temporary writer, leads to complication with its lifetime. This only happens with the recursive case. This seems really borderline and I do not know if its more a bug or a expected limitation. I also tried to use higher-ranked trait bounds but in this case we really work on structs and my few attempts were unsuccessful.

I could simply redesign TSW (in my real case I only have optional pointer to a struct containing the Vec of TSW on one level) and introduce a TSW_2 without a pointer to the Vec, but it would really feel bad (unsatisfying at least) as a solution.

-- Edit

Yes, thanks Matthieu, that's the right diagnostic (MCW misleaded me (when testing I removed it and all ran fine but it did not do the same thing) :

- TSW<ST>::write_end<()> (&mut sel, w : &mut ())
- MCW<(), TSW<ST>>::write_end_all(&mut self)
- (f from slipt_first mut ) 
        TSW<ST>::write_end<MCW<(),TSW<ST>>
        MCW<MCW<(),TSW<ST>, > ...

In fact when thinking about the original problem the type should exactly be ...MCW<MCW<(),TSW, > imbricated N times, N being the size of the vector. (the elements in the vec are Writers extension which should apply over the previous elements of the Vec (kind of layered writer)).

Retrospectively I remember first having this issue for chaining my W and then solving it by using a vec to store them (then I got single Type with iterative multiple layer of writing), but then I need to use this Vec to write some payload in previous Vec and here I should have use the same reasonning and a double array). But the way I did it was to simply try it with a fat pointer over an optional struct. That did not go smoothly because I did something like "Option<Box<otherstructcontainingvec>>" but the other struct containing vec is no trait, and similarily in this sample code Vec is also no trait.

So I hope I finally got my solution : use Vec<TSW<E>> (my struct containing it in real code) as a trait and have a real fat pointer (more optimized solution would be double dimension vec (but my use case is in fact a single imbrication).

I do not think your issue is linked to lifetimes. What rustc is telling you is that when instantiating the function write_end it got into an infinite loop in the recursive call. Is there a reason you use recursion and not iteration here? — Matthieu M.

Matthieu M. Matthieu M. · Accepted Answer · 2016-10-10T11:20:59

You have a ping-pong going on here, with no end in sight.

call TSW<E>::write_end<W>(&mut self, w : &mut W)
which calls MCW<W, TSW<E>>::write_end_all(&mut self)
which calls TSW<E>::write_end<MCW<W, TCW<E>>>(&mut self, w: &mut )
which calls ...

Each new level of recursion piles on a new type there, which is why the type in the error message is so big. The rustc compiler, rather than entering in an infinite loop, is telling you that you probably don't want to instantiate an infinite number of functions.

There's something wrong with your logic, here. And that's not lifetime.

When starting a recursion, you need a plan for an exit strategy: it should end, predictably.

In the particular case of a recursion in generic types, it should end, predictably, whatever the run-time values of the arguments.

Not knowing what the correct logic should be, I present you an iterative solution:

fn write_end_all(&mut self) {
    for ew in self.1.iter_mut().rev() {
        ew.write_end(self.0);
        // do on current el.write_end();
    }
}

it is much simpler, does not cause an attempt to instantiate an infinite number of functions, and may not be the functionality you were looking for at all :)

Rust recursive type difficulty

1 Answers