are object bounds sound?

[compiler-errors]

^{(some older discussion here: https://hackmd.io/kw8vfb2oSFyQqatCjaFVSw)}

Making objects' built-in bounds sound

when proving a predicate for dyn Trait from one of its existential bounds, we need to prove that all of the supertraits of that bound's trait hold for dyn Trait, plus all of the associated types' item bounds hold.

For example, given:

trait Trait {
    type Assoc: Bound + ?Sized;
}

For dyn Trait<Assoc = i32>: Trait to be proven, we must check the item bounds on Assoc.

Without any additional work on top of just calling tcx.item_bounds({Trait::Assoc def-id}) and substituting Self = dyn Trait<Assoc = i32>, we get <dyn Trait<Assoc = i32> as Trait>::Assoc: Bound. However, in the new solver, this goal holds trivially via an alias bound candidate.

To fix this, rust-lang/rust#108333 folds these object bounds, eagerly replacing projections with the associated types' values that appear in the dyn Trait itself. This would give us i32: Bound, which would fail.

Is this sufficient?

It seems to work, but I'm not convinced that it's sufficient... it would be nice to more rigorously convince ourselves about this being a sound approach.

[lcnr]

given the following changes to rustc:

diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
index dec9f8016b0..0f633ab5cb6 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -484,6 +484,8 @@ pub(super) fn merge_candidates_and_discard_reservation_impls(
             _ => {}
         }

+        return self.try_merge_responses(candidates.iter().map(|c| Ok(c.result)));
+
         if candidates.len() > 1 {
             let mut i = 0;
             'outer: while i < candidates.len() {
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index f7559a3f10a..12eb6f7d1e7 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -463,7 +463,7 @@ fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
     }

     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
-        if !needs_normalization(&ty, self.param_env.reveal()) {
+        if !needs_normalization(&ty, self.param_env.reveal()) || self.interner().trait_solver_next() {
             return ty;
         }

these end up removing eager normalization, and choose always applicable candidates in case there are multiple. Both changes we consider to be desirable.

This ends up causing the following example to segfault:

use std::rc::Rc;
trait Trait {
    type Assoc: Send;
}

impl<T> Trait for T
where
    <T as Trait>::Assoc: Send,
{
    type Assoc = Rc<String>;
}

fn send<T: Clone>(x: &T) {
    let _ = x.clone();
}

fn foo(x: Rc<String>) {
    std::thread::scope(|s| {
        loop {
            println!("strong count: {}", Rc::strong_count(&x));
            for _ in 0..100 {
                s.spawn(|| 
                    // oh no, `Rc<String>` is not `Send`
                    send::<<() as Trait>::Assoc>(&x)
                );
            }
        }
    })
}

fn main() {
    foo(Rc::new(String::from("hey, this is a string")));
}

[compiler-errors]

i think the above comment is best moved to #9

[compiler-errors]

Closing in favor for rust-lang/trait-system-refactor-initiative#5