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

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.

@lcnr

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

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

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.

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))),
             })

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.

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.

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

Rollup merge of rust-lang#123302 - compiler-errors:sized-bound-first,…

Unrolled build for rust-lang#123302

Navigation Menu

Repository navigation

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

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

	// 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());
	}

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

Description

Activity

compiler-errors commented on Mar 31, 2024

compiler-errors commented on Mar 31, 2024

compiler-errors commented on Mar 31, 2024

compiler-errors commented on Mar 31, 2024

compiler-errors commented on Apr 1, 2024

lcnr commented on Apr 2, 2024

lcnr commented on Apr 2, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

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