Compiler in infinite loop with generics & lifetimes

1

I have a pretty minimal test case that causes rustc to spin (probably) forever computing a query about generic type substitution. We're talking rustc stable 1.64, beta, nightly, the lot.

struct Node<'a, G: NodeGenerics<'a>> {
    kind: Kind<'a, G>,
}

enum Kind<'a, G: NodeGenerics<'a>> {
    Empty,
    Var(Var<'a, G::R>),
}

trait NodeGenerics<'a> {
    type R: 'a;
}

struct RGen<T>;
impl<'a, T: 'a> NodeGenerics<'a> for RGen<T> {
    type R = T;
}

struct Var<'a, R: 'a> {
    node: Box<Node<'a, RGen<R>>>,
    _phantom: std::marker::PhantomData<R>,
}

You can see for yourself that the playground times out: Rust Playground. When I sample the rustc process, the spin is around this query (mangled, sorry), which appears many times in the sample at many depths:

_RNvXs4_NtNtCsiVaogSVR4MG_12rustc_middle2ty4listINtB5_4ListNtNtB7_5subst10GenericArgENtNtCs669WPFKHeg5_4core3cmp3Ord3cmpB9_  (in librustc_driver-2bbd7f122e6c8090.dylib) + 68  [0x10e219090]

There are three changes you can make, any one of which gets it to compile fine.

  1. Remove the "carrier trait" NodeGenerics, replace it with T: 'a and use T instead of G::R. You would think that adding a carrier trait with the same bounds would not really change anything. But it does. (In my code, NodeGenerics has a bunch of different types attached to it, which are used in many different arms of Kind. It makes everything a lot neater.)
  2. Changing RGen<T> to just RGen and its implementation of NodeGenerics to have a constant type R = ().
  3. Don't use lifetimes at all, put 'static bounds in everywhere instead, i.e. make NodeGenerics take type R: 'static.

Why is this spinning? Is there something I'm missing about lifetime variance that is deeply upsetting to Rustc? Is the solution to whack a well-placed PhantomData<&'a T> in there? Or is this a rustc bug?

2

Rustc isn't supposed to diverge (crash or get into an infinite loop), ever. So this is surely a bug, just because there is any sort of input that can cause rustc not to terminate.

Whether the code is correct is not is another question (I haven't looked deeply enough to know), but even if it's incorrect, the expected behavior is getting a compiler error, not sending the compiler to an infinite loop.

2 Likes
3

Fair enough. Filed a bug. Compiler hangs on some types threading lifetimes through a carrier trait · Issue #102966 · rust-lang/rust · GitHub

1 Like
4

The compiler has some known infinite-recursion bugs, and this is perhaps related:

1 Like
5

I don't think it's infinite recursion, because there is no stack overflow, nor is there one if you add #![recursion_limit = "5"].

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.