Stack overflow when impl'ing on recursive types

[apoelstra]

See https://gist.github.com/apoelstra/0c5e05a2d57a91be3c0b

Here I have a structure like

struct List<T> {
data: T,
next: Option<Box<List<T>>>
}

and am trying to implement a deserialization trait on it. When I try to call deserialize on a Vec<u8> to produce a List<u8> say, rustc overflows, presumably chasing <T> through an infinite chain of Option<Box<List<T>>>s somehow.

Note that if the data field and parameter <T> are removed, there is no stack overflow.

[apoelstra]

This is similar to #11824 but I don't believe it is the same bug since #11824 triggers just by defining the Trait, while this requires an actual call to a trait method.

[apoelstra]

After some experimentation I have determined that the cause of the recursion is that the exact type of I:Iterator is propagated from the original function call List<T>::deserialize, through to called deserialization routines as ByRef<I>, through to List<T>::deserialize again, through as ByRef<ByRef<I>>, and so on.

So now I am unsure if this is an actual bug.

[chris-morgan]

I would classify a stack overflow as a bug in rustc. If it’s not legal, it should complain with an appropriate error, not with stack overflow.

[steveklabnik]

Triage: there have been a lot of changes to Rust since this sample code was made. @apoelstra , have you seen this error lately?

[apoelstra]

No, I have not encountered this bug since I filed it.

[steveklabnik]

Okay, I'm going to give it a close, then.

Anyone else coming along later, if you see this, please let me know and I'll re-open.

[rphmeier]

not sure about that: https://play.rust-lang.org/?gist=d202841280e5d7a9e28f&version=nightly

On nightly/beta it appears to time out, on stable it's still a stack overflow.

[rphmeier]

(I just ported it to stable Rust)

[Mark-Simulacrum]

This now provides a proper, if very long, error message:

rustc 1.18.0-nightly (128aa262e 2017-04-28)
warning: field is never used: `data`
  --> <anon>:39:3
   |
39 |   data: T,
   |   ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> <anon>:40:3
   |
40 |   next: Option<Box<List<T>>>
   |   ^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: unused variable: `deserialize`
  --> <anon>:55:7
   |
55 |   let deserialize: Result<List<u8>, _> = Serial::deserialize(serialized.iter().map(|x| *x));
   |       ^^^^^^^^^^^
   |
   = note: #[warn(unused_variables)] on by default

error[E0275]: overflow evaluating the requirement `<std::slice::Iter<u8> as std::iter::Iterator>::Item`
  |
  = help: consider adding a `#![recursion_limit="512"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::iter::Iterator` for `std::iter::Map<std::slice::Iter<u8>, [closure@<anon>:55:84: 55:90]>`
  = note: required because of the requirements on the impl of `std::iter::Iterator` for `&mut std::iter::Map<std::slice::Iter<u8>, [closure@<anon>:55:84: 55:90]>`
   .... snip 200+ lines

error: aborting due to previous error