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

[package]
name = "test2"
version = "0.1.0"
edition = "2021"

[profile.dev]
codegen-units = <insert num codegen-units here>

[dependencies]
dep = { path = "dep" }

the output of cargo c is unstable:

with 1 codegen unit it's

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

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

rust/compiler/rustc_metadata/src/rmeta/encoder.rs

Lines 2005 to 2024 in 69db514

	// Bring everything into deterministic order for hashing
	all_impls.sort_by_cached_key(|&(trait_def_id, _)| tcx.def_path_hash(trait_def_id));
	let all_impls: Vec<_> = all_impls
	.into_iter()
	.map(|(trait_def_id, mut impls)| {
	// Bring everything into deterministic order for hashing
	impls.sort_by_cached_key(|&(index, _)| {
	tcx.hir().def_path_hash(LocalDefId { local_def_index: index })
	});
	TraitImpls {
	trait_id: (trait_def_id.krate.as_u32(), trait_def_id.index),
	impls: self.lazy_array(&impls),
	}
	})
	.collect();
	self.lazy_array(&all_impls)
	}

@cjgillot said:

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