Bad associated type usage causes infinite build/check/run

[Avi-D-coder]

Bad: compilation never completes

struct Elem<'r, T: Life> {
    next: List<'r, T::L<'r>>,
    value: T,
}

Good: compilation completes

struct Elem<'r, T: Life> {
    next: List<'r, T>,
    value: T,
}

Common

#![allow(incomplete_features)]
#![feature(generic_associated_types)]

fn main() {
    println!("Hello, world!");
}

unsafe trait Life {
    type L<'l>: 'l + Life;
}

struct Gc<'r, T>(&'r T);
unsafe impl<'r, T: Life> Life for Gc<'r, T> {
    type L<'l> = Gc<'l, T::L<'l>>;
}

unsafe impl<'r, T: Life> Life for Option<T> {
    type L<'l> = Option<T::L<'l>>;
}


unsafe impl<'r, T: Life> Life for List<'r, T> {
    type L<'l> = List<'l, T::L<'l>>;
}

unsafe impl<'r, T: Life> Life for Elem<'r, T> {
    type L<'l> = Elem<'l, T::L<'l>>;
}

struct List<'r, T: Life>(Option<Gc<'r, Elem<'r, T>>>);

[jackh726]

A slightly more minimized example:

// build-pass

#![feature(generic_associated_types)]
//~^ WARNING: the feature `generic_associated_types` is incomplete

fn main() {}

trait Life {
    type L<'l>: 'l + Life;
}

struct Gc<'r, T>(&'r T);
impl<'r, T: Life> Life for Gc<'r, T> {
    type L<'l> = Gc<'l, T::L<'l>>;
}

impl<'r, T: Life> Life for List<'r, T> {
    type L<'l> = List<'l, T::L<'l>>;
}

impl<'r, T: Life> Life for Elem<'r, T> {
    type L<'l> = Elem<'l, T::L<'l>>;
}

struct List<'r, T: Life>(Gc<'r, Elem<'r, T>>);

struct Elem<'r, T: Life> {
    next: List<'r, T::L<'r>>,
}

[jackh726]

I've started to dig into this a little. I think there is an infinite loop happening in the implict outlives bit of typechecking.

Basically, the unsubstituted_predicates here are growing really large: <<<<T as Life>::L<'r> as Life>::L<'r> as Life>::L<'r> as Life>::L<'r>. I'm really not familiar with this code, so I'm not exactly sure what I'm looking for.

I've reached my time limit for now, but here a gist of a full debug log into a couple cycles of this loop in case in it would be helpful to anyone (or just me later): https://gist.github.com/jackh726/0ac343d575d1aca3d786b7773a3c0401

[jackh726]

Okay, digging in some more.

In outlives checking, here's the sequence of events I'm seeing:

We ask for required predicates for List<'r, <T as Life>::L<'r>>
Unsubstituted predicates are: 'r: 'r and T: 'r
We get back required predicates of 'r: 'r (existing) and <T as Life>::L<'r>: 'r

This is a new "global predicate", so we add it to map.

Next round:

We ask for required predicates for: List<'r, <T as Life>::L<'r>>
Unsubstituted predicates are: 'r: 'r, T: 'r, and <T as Life>::L<'r>: 'r
We get back required predicates of 'r: 'r (existing) and <T as Life>::L<'r>: 'r (existing), and <<T as Life>::L<'r> as Life>::L<'r>: 'r

This is a new "global predicate", so we add it to map.

repeat

Have to think of a proper solution here.

[jackh726]

Much shorter repro

// build-pass

#![feature(generic_associated_types)]
//~^ WARNING: the feature `generic_associated_types` is incomplete

fn main() {}

trait Life {
    type L<'l>: 'l + Life;
}

struct Gc<'r, T>(&'r T);

struct List<'r, T: Life>(Gc<'r, Elem<'r, T>>);

struct Elem<'r, T: Life> {
    next: List<'r, T::L<'r>>,
}

[jackh726]

Very short repro that doesn't use GATs

// build-pass

fn main() {}

trait Life {
    type L;
}

struct List<'r, T>(&'r Elem<'r, T>);

struct Elem<'r, T: Life> {
    next: List<'r, T::L>,
}

[jackh726]

This looks a lot like #63650.

As this isn't a GAT issue, I'm removing that label.

[AE1020]

I don't know anything 😇 just skimming Rust source to see how it works... and tracing a few nontrivial issues (with easy repro cases) to try to motivate my understanding.

Seeing this one, it made me curious about how cycles are ever handled in datatypes--lifetime or not. I found a comment in the definition of Adt which says:

/// It may seem impossible to represent recursive types using [`Ty`],
/// since [`TyKind::Adt`] includes [`AdtDef`], which includes its fields,
/// creating a cycle. However, `AdtDef` does not actually include the *types*
/// of its fields; it includes just their [`DefId`]s.

Perhaps worth noticing. Anyway, looking at this case, there is global_inferred_outlives which is FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>.

( Note: Circa October 2022, the cited code is located in /compiler/rustc_hir_analysis/src/outlives/implicit_infer.rs#L140 )

So there's a DefId on the left hand side of the map. In the repro case that's not exploding with IDs (it just flips back and forth between a single ID for each of Elem and List, but those two IDs are mapping to an ever-increasing amount of stuff.)

Here's a targeted debug dump of that, which adds some type information to what @jackh726 has already summarized:

DefId(0:11 ~ repro[18e4]::Elem) =>
    (nothing)

DefId(0:6 ~ repro[18e4]::List) =>
    EarlyBinder({OutlivesPredicate(ReEarlyBound(0, 'r), ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(T, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0)})

DefId(0:11 ~ repro[18e4]::Elem) =>
    EarlyBinder({OutlivesPredicate(ReEarlyBound(0, 'r), ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(<T as Life>::L, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0)})

DefId(0:6 ~ repro[18e4]::List) =>
    EarlyBinder({OutlivesPredicate(ReEarlyBound(0, 'r), ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(<T as Life>::L, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(T, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0)})

DefId(0:11 ~ repro[18e4]::Elem) =>
    EarlyBinder({OutlivesPredicate(ReEarlyBound(0, 'r), ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(<<T as Life>::L as Life>::L, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0), OutlivesPredicate(<T as Life>::L, ReEarlyBound(0, 'r)): repro.rs:9:20: 9:35 (#0)})

...

That first argument to OutlivesPredicate is a GenericArg:

pub struct GenericArg<'tcx> {
    ptr: NonZeroUsize,
    marker: PhantomData<(Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>)>,
}

The terminology is that T is a Param, e.g. Type Parameter:

/// A type parameter; for example, `T` in `fn f<T>(x: T) {}`.
Param(I::ParamTy),

The substitution that turns T into T as Life happens in the subst() here:

let predicate = unsubstituted_predicates
    .rebind(*unsubstituted_predicate)
    .subst(tcx, substs);

What happens is that the GenericArg gets walked through deeply running "Type Folding". TypeFoldable is implemented for GenericArg, which when it contains a Type (vs Region/Const) it runs this code:

fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
    if !t.needs_subst() {
        return t;
    }

    match *t.kind() {
        ty::Param(p) => self.ty_for_param(p, t),
        _ => t.super_fold_with(self),
    }
}

When the T Param is seen--arbitrarily deeply--it has an index of 1 (because it is the second generic argument, e.g. second thing in angle brackets of List<'r, T>). What is substituted is what was in the substs array at index 1.