Rustdoc: where bounds order in synthetic impls is not deterministic

[SimonSapin]

Unrelated changes to the standard library can cause src/test/rustdoc to fail until a change like this is applied:

diff --git a/src/test/rustdoc/synthetic_auto/no-redundancy.rs b/src/test/rustdoc/synthetic_auto/no-redundancy.rs
index 0b37f2ed31..9f860f4226 100644
--- a/src/test/rustdoc/synthetic_auto/no-redundancy.rs
+++ b/src/test/rustdoc/synthetic_auto/no-redundancy.rs
@@ -20,7 +20,7 @@ where
 
 // @has no_redundancy/struct.Outer.html
 // @has - '//*[@id="synthetic-implementations-list"]/*[@class="impl"]/*/code' "impl<T> Send for \
-// Outer<T> where T: Copy + Send"
+// Outer<T> where T: Send + Copy"
 pub struct Outer<T> {
     inner_field: Inner<T>,
 }

CC @GuillaumeGomez

[GuillaumeGomez]

I don't think the issue comes from rustdoc. I tried to get this issue and wasn't able to... Last example:

use std::fmt::Debug;

struct Foo<T>(T);

unsafe impl<T> Send for Foo<T>
where T: Copy + Send + Clone + Debug {}

The generated docs have the correct output. No clue where it could come from...

[SimonSapin]

The generated output sometimes changes when the standard library changes. This has happened that I know of in:

• Add 12 num::NonZero* types for primitive integers, deprecate core::nonzero #48265 (but not anymore after a recent rebase)
• Implement Integer methods for Wrapping #48810
• replace convert::Infallible with ! #49038

[Phlosioneer]

I suspect it may be something in #47833. I'm investigating, since one of the affected PR's is mine, so I can reproduce it.

[QuietMisdreavus]

This test is running the "synthetic impls" functionality of rustdoc, where it will create an impl of Send/Sync if there is not an explicit one. This is entirely defined in src/librustdoc/clean/auto_trait.rs, so it's possible we can sort any where-clauses this generates.

[QuietMisdreavus]

If i understand it correctly, the generics are handled in this section in that file. Sorting the collections in the resulting Generics will make the output deterministic.

rust/src/librustdoc/clean/auto_trait.rs

Lines 135 to 167 in a04b88d

	let new_generics = match result {
	AutoTraitResult::PositiveImpl(new_generics) => {
	polarity = None;
	new_generics
	}
	AutoTraitResult::NegativeImpl => {
	polarity = Some(ImplPolarity::Negative);
	// For negative impls, we use the generic params, but *not* the predicates,
	// from the original type. Otherwise, the displayed impl appears to be a
	// conditional negative impl, when it's really unconditional.
	//
	// For example, consider the struct Foo<T: Copy>(*mut T). Using
	// the original predicates in our impl would cause us to generate
	// `impl !Send for Foo<T: Copy>`, which makes it appear that Foo
	// implements Send where T is not copy.
	//
	// Instead, we generate `impl !Send for Foo<T>`, which better
	// expresses the fact that `Foo<T>` never implements `Send`,
	// regardless of the choice of `T`.
	let real_generics = (&generics, &Default::default());
	// Clean the generics, but ignore the '?Sized' bounds generated
	// by the `Clean` impl
	let clean_generics = real_generics.clean(self.cx);
	Generics {
	params: clean_generics.params,
	where_predicates: Vec::new(),
	}
	}
	_ => unreachable!(),
	};

The key would be figuring out a proper sort, because with where clauses you can get arbitrary types in there, so we'd effectively need to be able to sort those somehow. I'm building something right now to test a hunch.

[kennytm]

Reminder. The rustdoc/synthetic_auto/no-redundancy.rs test will be ignored after #49058. If #49058 landed first (likely due to p=100), please make sure to remove the // ignore header from that test in the fix.

[Phlosioneer]

@QuietMisdreavus I was under the impression that all impls are sorted, after the auto-generated ones are added to the list. That's why I mentioned #47833, which is the commit that added sorting of the impls for deterministic outputs. Specifically, the first commit in that PR.

If more stuff is being added to the list after that sort, that is our bug. Otherwise, it should already be handled, and therefore the bug is within the sorting function.

[QuietMisdreavus]

@Phlosioneer Looking at that PR again, it looks like it does sort the where predicates. However, it looks like the issue is about sorting the conditions within a single predicate, which the last commit in that PR doesn't address. That should help the implementation some.

(Also, thanks for pointing that out; i didn't realize that was there >_>)

[Phlosioneer]

Ah, okay then, I think I found the error: make_final_bounds does a .collect() on an .into_iter() on a FxHashMap, but the order of .into_iter() is non-deterministic. The output vec of make_final_bounds just needs to be sorted.

rust/src/librustdoc/clean/auto_trait.rs

Lines 1017 to 1025 in ddfbf2b

	fn make_final_bounds<'b, 'c, 'cx>(
	&self,
	ty_to_bounds: FxHashMap<Type, FxHashSet<TyParamBound>>,
	ty_to_fn: FxHashMap<Type, (Option<PolyTrait>, Option<Type>)>,
	lifetime_to_bounds: FxHashMap<Lifetime, FxHashSet<Lifetime>>,
	) -> Vec<WherePredicate> {
	ty_to_bounds
	.into_iter()
	.flat_map(|(ty, mut bounds)| {

rust/src/librustdoc/clean/auto_trait.rs

Lines 1097 to 1099 in ddfbf2b

	)
	.collect()
	}

I'll make a PR that adds a sort to that method.

[QuietMisdreavus]

I don't think that will affect it. Like i said, it's not a matter of sorting between WherePredicates, it's about sorting the bounds within a predicate. It would be worth seeing how that function creates those predicates to sort within the flat_map, not after the final collect.

[Phlosioneer]

Oh, so really we need to sort the bounds within that function, after .into_iter().collect():

rust/src/librustdoc/clean/auto_trait.rs

Lines 1084 to 1096 in ddfbf2b

	Some(WherePredicate::BoundPredicate {
	ty,
	bounds: bounds.into_iter().collect(),
	})
	})
	.chain(
	lifetime_to_bounds
	.into_iter()
	.filter(|&(_, ref bounds)| !bounds.is_empty())
	.map(|(lifetime, bounds)| WherePredicate::RegionPredicate {
	lifetime,
	bounds: bounds.into_iter().collect(),
	}),

Because bounds is also a FxHashMap.

[QuietMisdreavus]

Yes, that's what i think the culprit is. Now that #49058 is merged, re-enabling the test should make it fail, so whatever you add to librustdoc should either make it pass or make it stop toggling whenever a new type or impl is added to libstd.