the order of `tcx.implementations_of_trait` is unstable

[lcnr]

given the following extern crate dep:

mod private {
    pub trait Hidden {}
    impl Hidden for &u128 {}
    impl Hidden for &u64 {}
    impl Hidden for &u32 {}
    impl Hidden for &u16 {}
    impl Hidden for &u8 {}
}

pub trait Sealed: private::Hidden {}

and the following root crate:

struct Local;
impl dep::Sealed for Local {} 

fn main() {}

The order in trait_impls_of depends on crate metadata of dep. The rest is only necessary to reproduce this issue.

with the following cargo.toml file ```rust [package] name = "test2" version = "0.1.0" edition = "2021" [profile.dev] codegen-units = [dependencies] dep = { path = "dep" } ``` the output of `cargo c` is unstable: with 1 codegen unit it's ```rust error[E0277]: the trait bound `Local: dep::private::Hidden` is not satisfied --> src/main.rs:2:22 | 2 | impl dep::Sealed for Local {} | ^^^^^ the trait `dep::private::Hidden` is not implemented for `Local` | = help: the following other types implement trait `dep::private::Hidden`: &u128 &u64 &u32 &u16 &u8 note: required by a bound in `Sealed` --> /home/lcnr/test2/dep/src/lib.rs:10:19 | 10 | pub trait Sealed: private::Hidden {} | ^^^^^^^^^^^^^^^ required by this bound in `Sealed` = note: `Sealed` is a "sealed trait", because to implement it you also need to implement `dep::private::Hidden`, which is not accessible; this is usually done to force you to use one of the provided types that already implement it = help: the following types implement the trait: &u32 &u8 &u16 &u64 &u128 ``` while with 2 it is ```rust error[E0277]: the trait bound `Local: dep::private::Hidden` is not satisfied --> src/main.rs:2:22 | 2 | impl dep::Sealed for Local {} | ^^^^^ the trait `dep::private::Hidden` is not implemented for `Local` | = help: the following other types implement trait `dep::private::Hidden`: &u128 &u64 &u32 &u16 &u8 note: required by a bound in `Sealed` --> /home/lcnr/test2/dep/src/lib.rs:10:19 | 10 | pub trait Sealed: private::Hidden {} | ^^^^^^^^^^^^^^^ required by this bound in `Sealed` = note: `Sealed` is a "sealed trait", because to implement it you also need to implement `dep::private::Hidden`, which is not accessible; this is usually done to force you to use one of the provided types that already implement it = help: the following types implement the trait: &u8 &u16 &u64 &u128 &u32 ```

[lcnr]

cc #120012

[lcnr]

discussed in https://rust-lang.zulipchat.com/#narrow/stream/131828-t-compiler/topic/codegen-units.20impacts.20order.20of.20impls

root cause is https://github.com/rust-lang/rust/blob/69db514ed9238bb11f5d2c576fe26020e3b99a52/compiler/rustc_metadata/src/rmeta/encoder.rs#L2005-L2024

@cjgillot said:

The input by calling tcx.hir().items is already in deterministic order. We can just remove the sorting.