Rollup merge of #102947 - compiler-errors:sort-elaborated-existentials, r=cjgillot

Sort elaborated existential predicates in `object_ty_for_trait`

r? `@cjgillot`

I think that #102845 caused #102933. Depending on the order that we elaborate these existential projection predicates, there's no guarantee that they'll be sorted by def id, which is what is failing the assertion in the issue.

Fixes #102933
Fixes #102973

2 files changed, 43 insertions, 11 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs
index 1afa04007b8..545524f63a7 100644
--- a/compiler/rustc_trait_selection/src/traits/object_safety.rs
+++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs
@@ -581,17 +581,24 @@ fn object_ty_for_trait<'tcx>(
     });
     debug!(?trait_predicate);
 
-    let elaborated_predicates = elaborate_trait_ref(tcx, trait_ref).filter_map(|obligation| {
-        debug!(?obligation);
-        let pred = obligation.predicate.to_opt_poly_projection_pred()?;
-        Some(pred.map_bound(|p| {
-            ty::ExistentialPredicate::Projection(ty::ExistentialProjection {
-                item_def_id: p.projection_ty.item_def_id,
-                substs: p.projection_ty.substs,
-                term: p.term,
-            })
-        }))
-    });
+    let mut elaborated_predicates: Vec<_> = elaborate_trait_ref(tcx, trait_ref)
+        .filter_map(|obligation| {
+            debug!(?obligation);
+            let pred = obligation.predicate.to_opt_poly_projection_pred()?;
+            Some(pred.map_bound(|p| {
+                ty::ExistentialPredicate::Projection(ty::ExistentialProjection {
+                    item_def_id: p.projection_ty.item_def_id,
+                    substs: p.projection_ty.substs,
+                    term: p.term,
+                })
+            }))
+        })
+        .collect();
+    // NOTE: Since #37965, the existential predicates list has depended on the
+    // list of predicates to be sorted. This is mostly to enforce that the primary
+    // predicate comes first.
+    elaborated_predicates.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
+    elaborated_predicates.dedup();
 
     let existential_predicates = tcx
         .mk_poly_existential_predicates(iter::once(trait_predicate).chain(elaborated_predicates));
diff --git a/src/test/ui/object-safety/issue-102933.rs b/src/test/ui/object-safety/issue-102933.rs
new file mode 100644
index 00000000000..843391cffb2
--- /dev/null
+++ b/src/test/ui/object-safety/issue-102933.rs
@@ -0,0 +1,25 @@
+// check-pass
+
+use std::future::Future;
+
+pub trait Service {
+    type Response;
+    type Future: Future<Output = Self::Response>;
+}
+
+pub trait A1: Service<Response = i32> {}
+
+pub trait A2: Service<Future = Box<dyn Future<Output = i32>>> + A1 {
+    fn foo(&self) {}
+}
+
+pub trait B1: Service<Future = Box<dyn Future<Output = i32>>> {}
+
+pub trait B2: Service<Response = i32> + B1 {
+    fn foo(&self) {}
+}
+
+fn main() {
+    let x: &dyn A2 = todo!();
+    let x: &dyn B2 = todo!();
+}