circular set of associated types cause cargo build to hang

[martinjrobins]

I have a linear algebra based project (https://github.com/martinjrobins/diffsol) which has a set of Scalar, Vector and Matrix traits that refer to each other via associated traits. On stable (rustc 1.77.1) this builds fine, but on beta (1.78.0) and nightly (1.79.0) the build hangs (martinjrobins/diffsol#3). A MRE is:

use std::ops::{Add, Sub};

pub trait Scalar {}

pub trait VectorCommon: Sized {
    type T: Scalar;
}

pub trait VectorOpsByValue<Rhs = Self, Output = Self>:
    VectorCommon + Add<Rhs, Output = Output> + Sub<Rhs, Output = Output>
{
}

pub trait VectorView<'a>:
    VectorOpsByValue<Self, Self::Owned> + VectorOpsByValue<Self::Owned, Self::Owned>
{
    type Owned;
}

pub trait Vector: VectorOpsByValue<Self> + for<'a> VectorOpsByValue<Self::View<'a>> {
    type View<'a>: VectorView<'a, T = Self::T, Owned = Self>
    where
        Self: 'a;
}

pub trait MatrixCommon {
    type V: Vector;
}

If I look at the compiler log with RUSTC_LOG=TRACE I see an endless repitition of text like:

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=128)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

Note that if I remove the MatrixCommon trait everything builds fine.

Meta

The bug does not exist in stable:
rustup run stable rustc --version:

rustc 1.77.1 (7cf61ebde 2024-03-27)

The bug exists in beta and nightly:
rustup run beta rustc --version:

rustc 1.78.0-beta.4 (c1195518c 2024-03-29)

rustup run nightly rustc --version:

rustc 1.79.0-nightly (1684a753d 2024-04-01)

Backtrace

here is some more of the logs:

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as MatrixCommon>::V as Vector>

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=<<Self as MatrixCommon>::V as Vector>

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=127, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?126], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?126], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=127)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=128)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=129)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=129)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=<<Self as MatrixCommon>::V as Vector>

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=128, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }), true], def_id: DefId(2:3146 ~ core[191c]::ops::arith::Add::Output) }

rustc_trait_selection::traits::project::project obligation=Obligation(predicate=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?127], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) }, depth=128)

rustc_trait_selection::traits::normalize::normalize_with_depth_to depth=129, value=AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), Alias(Projection, AliasTy { args: [Alias(Projection, AliasTy { args: [Self/#0], def_id: DefId(0:20 ~ nightly_bug[62a3]::MatrixCommon::V) }), '?128], def_id: DefId(0:17 ~ nightly_bug[62a3]::Vector::View) })], def_id: DefId(2:3151 ~ core[191c]::ops::arith::Sub::Output) }

[lqd]

IIUC that's from #120584 cc @compiler-errors (it also only happens with the old solver ofc)

[compiler-errors]

I'm fascinated that this wasn't fixed by #121123. Perhaps there's somewhere else we need to be calling item_super_predicates instead of item_bounds in the solver...

[compiler-errors]

Oh lol, I found the bug.