Order-dependence of `dyn Trait: Supertrait` goals causes incompleteness (old solver)

[compiler-errors]

pub trait Trait: Supertrait {}

trait Impossible {}
impl<F: ?Sized + Impossible> Trait for F {}

pub trait Supertrait {}

impl<T: ?Sized + Trait + Impossible> Supertrait for T {}

fn needs_supertrait<T: ?Sized + Supertrait>() {}
fn needs_trait<T: ?Sized + Trait>() {}

fn main() {
    needs_trait::<dyn Trait>(); // Comment this and it'll fail
    needs_supertrait::<dyn Trait>();
    needs_trait::<dyn Trait>();
}

Trying to prove dyn Trait: Trait only after we prove dyn Trait: Supertrait will cause the goal to fail. This seems bad.

[compiler-errors]

cc @lcnr who may know if this issue already is tracked

[compiler-errors]

Actually this is just because EvaluatedToErrStackDependent is super scuffed. This will be fixed by #122791.

[compiler-errors]

So what happens here:

• We try to prove dyn Trait: Supertrait
  • Assemble impl candidate first, which requires dyn Trait: Trait and dyn Trait: Impossible
    • We try to prove dyn Trait: Trait
      • Assemble object-bound candidate, which requires dyn Trait: Supertrait to hold
        • We see this is a stack-dependent overflow, so it gets EvaluatedToErrStackDependent
      • Assemble impl candidate, which requires dyn Trait: impossible, so it gets EvaluatedToErr
      • During winnowing, neither candiate holds, so we filter both of them, and return SelectionError::Unimplemented THIS IS THE IMPORTANT PART
  • (at this point, we will assemble the object bound candidate, however we've already cached dyn Trait: Trait as ErrorGuaranteed, which causes the later goal to fail.)

Specifically, winnowing does not take into account stack dependence:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 495 to 497 in 8058136

	Ok(eval) if eval.may_apply() => {
	Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }))
	}

And so therefore it may inadvertently "downgrade" a result that may be stack dependent to one that isn't stack dependent by removing it from the list of candidates, meaning we return SelectionError::Unimplemented (since we now have 0 candidates).

Unfortunately, this is only hit when we actually do winnowing -- if there's only one candidate, then we won't winnow:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 472 to 488 in 8058136

	// If there is more than one candidate, first winnow them down
	// by considering extra conditions (nested obligations and so
	// forth). We don't winnow if there is exactly one
	// candidate. This is a relatively minor distinction but it
	// can lead to better inference and error-reporting. An
	// example would be if there was an impl:
	//
	// impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
	//
	// and we were to see some code `foo.push_clone()` where `boo`
	// is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
	// we were to winnow, we'd wind up with zero candidates.
	// Instead, we select the right impl now but report "`Bar` does
	// not implement `Clone`".
	if candidates.len() == 1 {
	return self.filter_reservation_impls(candidates.pop().unwrap());
	}

So that's why we don't see this more often.

[compiler-errors]

If #122791 weren't so close to landing, then I would probably instead fix this by changing winnowing:

diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 1894fbba302..09d1df586c3 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -492,10 +492,16 @@ fn candidate_from_obligation_no_cache<'o>(
         let mut candidates = candidates
             .into_iter()
             .map(|c| match self.evaluate_candidate(stack, &c) {
-                Ok(eval) if eval.may_apply() => {
+                // We CANNOT winnow `EvaluateToErrStackDependent`, since if we do,
+                // then we may end up with NO candidates in this list. If that's
+                // the case, then we will return `SelectionError::Unimplemented`,
+                // which results in `EvaluatedToErr` which is NOT stack dependent.
+                // This will cause us to incompletely cache a stack-dependent trait
+                // result as `EvaluatedToErr`.
+                Ok(EvaluatedToErr) => Ok(None),
+                Ok(eval) => {
                     Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }))
                 }
-                Ok(_) => Ok(None),
                 Err(OverflowError::Canonical) => Err(Overflow(OverflowError::Canonical)),
                 Err(OverflowError::Error(e)) => Err(Overflow(OverflowError::Error(e))),
             })

[compiler-errors]

This has probably failed since forever -- this example only fails since 1.49 which is when we started to enforce supertrait bounds hold (#73905) for object built-in candidates, but I wouldn't be surprised if you could construct an example which fails for even longer.

[lcnr]

To clarify this a bit and to make sure I understand it correctly, the underlying issue here is the following afaict:

• GoalA
  • CandA1
    • GoalB
      • CandB1
        • GoalA (inductive cycle -> error)
      • CandB1
        • Impossible (necessary to evaluate nested goals of CandB1 during selection)
  • CandA2 (trivially true)

when first evaluating GoalA, GoalB gets moved to the global cache as an error, evne though it only errors when used as a nested goal of GoalA. Later proving GoalB therefore fails.

[lcnr]

I expect this to also affect EvaluatedToAmbigStackDependent with the following setup:

• GoalA
  • CandA1
    • GoalB
      • CandB1
        • GoalA (inductive cycle -> ambig)
        • AssertInferenceConstraintsApplied (fails due to incompleteness if the inference constraints from CandA2 have not yet been applied)
      • CandB2
        • Impossible (necessary to evaluate nested goals of CandB1 during selection)
  • CandA2
    • guide inference ~> Ok, but inference constraints