Segfault on cyclic trait type parameter bounds.

[brendanzab]

trait A<T: B>{}
trait B<T: A> {}

boom.

Segmentation fault
application terminated with error code 139

Edit: HAH!

trait A<T:A> {}

Segmentation fault
application terminated with error code 139

[huonw]

I guess this is "just" infinite recursion overflowing the stack:

#0  0x00007ffff6186748 in middle::ty::__extensions__::meth_43052::iter_bytes::_b965143dcf3ece80::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#1  0x00007ffff61aaa5b in middle::ty::mk_t::_e931c6ec37273d78::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#2  0x00007ffff61ae75a in middle::ty::mk_param::_32dd632be817fb3e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#3  0x00007ffff63f6b29 in middle::typeck::collect::ty_generics::compute_bounds::_35286487a393fe63::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#4  0x00007ffff63e3033 in middle::typeck::collect::ty_generics::_2a33f4ab7a74e87c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#5  0x00007ffff63eecb3 in middle::typeck::collect::mk_item_substs::_3c1e735eaadfcd1c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#6  0x00007ffff63ee3de in middle::typeck::collect::trait_def_of_item::_c8767b261a4275e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#7  0x00007ffff63d3733 in middle::typeck::collect::get_trait_def::_41decb3a7c6f898e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#8  0x00007ffff63d8f60 in middle::typeck::astconv::ast_path_to_trait_ref_61794::_a09e937eb343dd22::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#9  0x00007ffff63e7e2f in middle::typeck::collect::instantiate_trait_ref::_302fe93b4bc5025::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#10 0x00007ffff63f6b64 in middle::typeck::collect::ty_generics::compute_bounds::_35286487a393fe63::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#11 0x00007ffff63e3033 in middle::typeck::collect::ty_generics::_2a33f4ab7a74e87c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#12 0x00007ffff63eecb3 in middle::typeck::collect::mk_item_substs::_3c1e735eaadfcd1c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#13 0x00007ffff63ee3de in middle::typeck::collect::trait_def_of_item::_c8767b261a4275e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#14 0x00007ffff63d3733 in middle::typeck::collect::get_trait_def::_41decb3a7c6f898e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#15 0x00007ffff63d8f60 in middle::typeck::astconv::ast_path_to_trait_ref_61794::_a09e937eb343dd22::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#16 0x00007ffff63e7e2f in middle::typeck::collect::instantiate_trait_ref::_302fe93b4bc5025::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#17 0x00007ffff63f6b64 in middle::typeck::collect::ty_generics::compute_bounds::_35286487a393fe63::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#18 0x00007ffff63e3033 in middle::typeck::collect::ty_generics::_2a33f4ab7a74e87c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#19 0x00007ffff63eecb3 in middle::typeck::collect::mk_item_substs::_3c1e735eaadfcd1c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#20 0x00007ffff63ee3de in middle::typeck::collect::trait_def_of_item::_c8767b261a4275e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#21 0x00007ffff63d3733 in middle::typeck::collect::get_trait_def::_41decb3a7c6f898e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#22 0x00007ffff63d8f60 in middle::typeck::astconv::ast_path_to_trait_ref_61794::_a09e937eb343dd22::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#23 0x00007ffff63e7e2f in middle::typeck::collect::instantiate_trait_ref::_302fe93b4bc5025::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#24 0x00007ffff63f6b64 in middle::typeck::collect::ty_generics::compute_bounds::_35286487a393fe63::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#25 0x00007ffff63e3033 in middle::typeck::collect::ty_generics::_2a33f4ab7a74e87c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#26 0x00007ffff63eecb3 in middle::typeck::collect::mk_item_substs::_3c1e735eaadfcd1c::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#27 0x00007ffff63ee3de in middle::typeck::collect::trait_def_of_item::_c8767b261a4275e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#28 0x00007ffff63d3733 in middle::typeck::collect::get_trait_def::_41decb3a7c6f898e::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#29 0x00007ffff63d8f60 in middle::typeck::astconv::ast_path_to_trait_ref_61794::_a09e937eb343dd22::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#30 0x00007ffff63e7e2f in middle::typeck::collect::instantiate_trait_ref::_302fe93b4bc5025::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
#31 0x00007ffff63f6b64 in middle::typeck::collect::ty_generics::compute_bounds::_35286487a393fe63::_0$x2e8$x2dpre () from /usr/local/bin/../lib/librustc-d3cb8c2ccd84a7a7-0.8-pre.so
[ ... ]

[brendanzab]

@huonw Should this be an error, or should it be allowed?

[huonw]

No idea; but it certainly shouldn't be infinite recursion.

[brendanzab]

Here's a use case that currently seg-faults:

pub trait Matrix
<
    S: Field,
    RV: VectorSpace<S>,
    CV: VectorSpace<S>,
    MT: Matrix<S, CV, RV, Self>
>
:   Ring
{
    fn transpose(&self) -> MT;
}

[msullivan]

It should be an error, I think.

[brendanzab]

Why?

[msullivan]

Well, hm. Maybe not an error, but how could it ever be implemented?

[glaebhoerl]

As usual let's look at what Haskell does:

$ cat > test311.hs
class A a => A a
$ ghc test311.hs
[1 of 1] Compiling Main             ( test311.hs, test311.o )

test311.hs:1:1:
    Cycle in class declaration (via superclasses): A -> A
    In the class declaration for `A'

[nikomatsakis]

This is tied in with trait reform (#5527). I'm way behind in writing up my thoughts on this. In some cases, you can detect cyclic recursion, but in some cases you cannot -- you either have to impose arbitrary limits on the kinds of trait interactions that are permitted or you just have to check (and handle gracefully) the cycle.

Haskell tends to take the "impose arbitrary limits" approach (see e.g. http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/type-class-extensions.html#instance-rules), though users can opt to suspend those limits.
Note also that the Haskell example given by @glehel is not equivalent to the Rust example: that would be trait A: A in Rust, which is a rather different situation that is more easily detected.

[nikomatsakis]

Note: I did not intend that as a criticism of Haskell, despite using the word "arbitrary". I described the limits as "arbitrary" because I do not see a readily explainable and intuitive way to summarize them in plain English, so they feel quite arbitrary.

[glaebhoerl]

Oh right, sorry. But then the Rust examples are invalid even before being cyclic:

trait A<T:A> {}

A expects a type argument, but in T:A none is supplied (which is what GHC complains about for the correctly translated example).

For the Matrix example translated as:

class Ring self
class Field self
class VectorSpace a self
class (Ring self, Field s, VectorSpace s rv, VectorSpace s cv, Matrix s cv rv self mt) => Matrix s rv cv mt self where
    transpose :: self -> mt

it does complain about a cycle.

Haskell tends to take the "impose arbitrary limits" approach ... though users can opt to suspend those limits.

If you mean FlexibleContexts and UndecidableInstances, I suspect those might not be entirely the same issue. In particular class cycle checking seems to be independent of them (turning on UndecidableInstances makes no difference).

[nikomatsakis]

I am referring to undecidable instances and the issue is not entirely independent. In this particular case, the cycle is readily detectable, but there are other ways to induce unbounded recursion that cannot be so easily detected (hence the paterson conditions etc).

[sruggier]

I just ran into this issue, with a use case like the following. The intent was to have two implementors. The first one would construct instances of the second one, and the second one would construct instances of itself. See below:

trait Thing<T: Thing> {
    fn make_vanilla_thing() -> T;
}

struct A;
struct B;

impl Thing<B> for A {
    fn make_vanilla_thing() -> B { B }
}

impl Thing<B> for B {
    fn make_vanilla_thing() -> B { B }
}

In context, I wasn't trying to do anything crazy, in my humble opinion, so I wasn't really expecting it to fail, although I guess it's not surprising in hindsight. If it's feasible, I think rustc should allow this kind of construct. The above example compiles if : Thing is removed from the first line.

Edit: fixed syntax and formatting, and added concrete types to the example.

[tamird]

This is the same as #15477, which is fixed. I've confirmed independently that this no longer reproduces.