diff options
25 files changed, 274 insertions, 56 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs index 56f126e9157..be48447e27c 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs @@ -19,21 +19,25 @@ rustc_index::newtype_index! { #[derive(Debug, Clone)] pub(super) struct ProvisionalEntry<'tcx> { - // In case we have a coinductive cycle, this is the - // the currently least restrictive result of this goal. - pub(super) response: QueryResult<'tcx>, - // In case of a cycle, the position of deepest stack entry involved - // in that cycle. This is monotonically decreasing in the stack as all - // elements between the current stack element in the deepest stack entry - // involved have to also be involved in that cycle. - // - // We can only move entries to the global cache once we're complete done - // with the cycle. If this entry has not been involved in a cycle, - // this is just its own depth. + /// In case we have a coinductive cycle, this is the + /// the current provisional result of this goal. + /// + /// This starts out as `None` for all goals and gets to some + /// when the goal gets popped from the stack or we rerun evaluation + /// for this goal to reach a fixpoint. + pub(super) response: Option<QueryResult<'tcx>>, + /// In case of a cycle, the position of deepest stack entry involved + /// in that cycle. This is monotonically decreasing in the stack as all + /// elements between the current stack element in the deepest stack entry + /// involved have to also be involved in that cycle. + /// + /// We can only move entries to the global cache once we're complete done + /// with the cycle. If this entry has not been involved in a cycle, + /// this is just its own depth. pub(super) depth: StackDepth, - // The goal for this entry. Should always be equal to the corresponding goal - // in the lookup table. + /// The goal for this entry. Should always be equal to the corresponding goal + /// in the lookup table. pub(super) input: CanonicalInput<'tcx>, } @@ -92,7 +96,7 @@ impl<'tcx> ProvisionalCache<'tcx> { self.entries[entry_index].depth } - pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> { + pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> Option<QueryResult<'tcx>> { self.entries[entry_index].response } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs index 21c8d476902..b860f374c0a 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -13,7 +13,7 @@ use rustc_middle::traits::solve::CacheData; use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult}; use rustc_middle::ty::TyCtxt; use rustc_session::Limit; -use std::{collections::hash_map::Entry, mem}; +use std::collections::hash_map::Entry; rustc_index::newtype_index! { pub struct StackDepth {} @@ -216,8 +216,8 @@ impl<'tcx> SearchGraph<'tcx> { cycle_participants: Default::default(), }; assert_eq!(self.stack.push(entry), depth); - let response = Self::response_no_constraints(tcx, input, Certainty::Yes); - let entry_index = cache.entries.push(ProvisionalEntry { response, depth, input }); + let entry_index = + cache.entries.push(ProvisionalEntry { response: None, depth, input }); v.insert(entry_index); } // We have a nested goal which relies on a goal `root` deeper in the stack. @@ -243,23 +243,31 @@ impl<'tcx> SearchGraph<'tcx> { root.cycle_participants.insert(e.input); } - // NOTE: The goals on the stack aren't the only goals involved in this cycle. - // We can also depend on goals which aren't part of the stack but coinductively - // depend on the stack themselves. We already checked whether all the goals - // between these goals and their root on the stack. This means that as long as - // each goal in a cycle is checked for coinductivity by itself, simply checking - // the stack is enough. - if self.stack.raw[stack_depth.index()..] - .iter() - .all(|g| g.input.value.goal.predicate.is_coinductive(tcx)) - { - // If we're in a coinductive cycle, we have to retry proving the current goal - // until we reach a fixpoint. - self.stack[stack_depth].has_been_used = true; - return cache.provisional_result(entry_index); + // If we're in a cycle, we have to retry proving the current goal + // until we reach a fixpoint. + self.stack[stack_depth].has_been_used = true; + return if let Some(result) = cache.provisional_result(entry_index) { + result } else { - return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); - } + // If we don't have a provisional result yet, the goal has to + // still be on the stack. + let mut goal_on_stack = false; + let mut is_coinductive = true; + for entry in self.stack.raw[stack_depth.index()..] + .iter() + .skip_while(|entry| entry.input != input) + { + goal_on_stack = true; + is_coinductive &= entry.input.value.goal.predicate.is_coinductive(tcx); + } + debug_assert!(goal_on_stack); + + if is_coinductive { + Self::response_no_constraints(tcx, input, Certainty::Yes) + } else { + Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) + } + }; } } @@ -288,15 +296,18 @@ impl<'tcx> SearchGraph<'tcx> { let provisional_entry_index = *cache.lookup_table.get(&stack_entry.input).unwrap(); let provisional_entry = &mut cache.entries[provisional_entry_index]; - let prev_response = mem::replace(&mut provisional_entry.response, response); - if stack_entry.has_been_used && prev_response != response { - // If so, remove all entries whose result depends on this goal - // from the provisional cache... + if stack_entry.has_been_used + && provisional_entry.response.map_or(true, |r| r != response) + { + // If so, update the provisional result for this goal and remove + // all entries whose result depends on this goal from the provisional + // cache... // - // That's not completely correct, as a nested goal can also + // That's not completely correct, as a nested goal can also only // depend on a goal which is lower in the stack so it doesn't // actually depend on the current goal. This should be fairly // rare and is hopefully not relevant for performance. + provisional_entry.response = Some(response); #[allow(rustc::potential_query_instability)] cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index); cache.entries.truncate(provisional_entry_index.index() + 1); @@ -315,8 +326,8 @@ impl<'tcx> SearchGraph<'tcx> { }); // We're now done with this goal. In case this goal is involved in a larger cycle - // do not remove it from the provisional cache and do not add it to the global - // cache. + // do not remove it from the provisional cache and update its provisional result. + // We only add the root of cycles to the global cache. // // It is not possible for any nested goal to depend on something deeper on the // stack, as this would have also updated the depth of the current goal. @@ -348,6 +359,8 @@ impl<'tcx> SearchGraph<'tcx> { dep_node, result, ) + } else { + provisional_entry.response = Some(result); } result diff --git a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.rs b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.rs index 1dca86d3630..1dca86d3630 100644 --- a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.rs +++ b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.rs diff --git a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.stderr b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.stderr index 47004821ad7..47004821ad7 100644 --- a/tests/ui/traits/new-solver/runaway-impl-candidate-selection.stderr +++ b/tests/ui/traits/new-solver/assembly/runaway-impl-candidate-selection.stderr diff --git a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.rs b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs index fcafdcf637a..fcafdcf637a 100644 --- a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.rs +++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.rs diff --git a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.stderr b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr index 7d3535e1f01..7d3535e1f01 100644 --- a/tests/ui/traits/new-solver/coinduction/fixpoint-exponential-growth.stderr +++ b/tests/ui/traits/new-solver/cycles/coinduction/fixpoint-exponential-growth.stderr diff --git a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs index 0cd14f05c8d..0cd14f05c8d 100644 --- a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs +++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.rs diff --git a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.stderr b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr index f1871ff0564..f1871ff0564 100644 --- a/tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.stderr +++ b/tests/ui/traits/new-solver/cycles/coinduction/incompleteness-unstable-result.stderr diff --git a/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs new file mode 100644 index 00000000000..5617e45adf6 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.rs @@ -0,0 +1,37 @@ +// compile-flags: -Ztrait-solver=next +#![feature(rustc_attrs)] + +// Test that having both an inductive and a coinductive cycle +// is handled correctly. + +#[rustc_coinductive] +trait Trait {} +impl<T: Inductive + Coinductive> Trait for T {} + +trait Inductive {} +impl<T: Trait> Inductive for T {} +#[rustc_coinductive] +trait Coinductive {} +impl<T: Trait> Coinductive for T {} + +fn impls_trait<T: Trait>() {} + +#[rustc_coinductive] +trait TraitRev {} +impl<T: CoinductiveRev + InductiveRev> TraitRev for T {} + +trait InductiveRev {} +impl<T: TraitRev> InductiveRev for T {} +#[rustc_coinductive] +trait CoinductiveRev {} +impl<T: TraitRev> CoinductiveRev for T {} + +fn impls_trait_rev<T: TraitRev>() {} + +fn main() { + impls_trait::<()>(); + //~^ ERROR overflow evaluating the requirement + + impls_trait_rev::<()>(); + //~^ ERROR overflow evaluating the requirement +} diff --git a/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr new file mode 100644 index 00000000000..4b8846da535 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/double-cycle-inductive-coinductive.stderr @@ -0,0 +1,29 @@ +error[E0275]: overflow evaluating the requirement `(): Trait` + --> $DIR/double-cycle-inductive-coinductive.rs:32:5 + | +LL | impls_trait::<()>(); + | ^^^^^^^^^^^^^^^^^ + | + = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`double_cycle_inductive_coinductive`) +note: required by a bound in `impls_trait` + --> $DIR/double-cycle-inductive-coinductive.rs:17:19 + | +LL | fn impls_trait<T: Trait>() {} + | ^^^^^ required by this bound in `impls_trait` + +error[E0275]: overflow evaluating the requirement `(): TraitRev` + --> $DIR/double-cycle-inductive-coinductive.rs:35:5 + | +LL | impls_trait_rev::<()>(); + | ^^^^^^^^^^^^^^^^^^^^^ + | + = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`double_cycle_inductive_coinductive`) +note: required by a bound in `impls_trait_rev` + --> $DIR/double-cycle-inductive-coinductive.rs:29:23 + | +LL | fn impls_trait_rev<T: TraitRev>() {} + | ^^^^^^^^ required by this bound in `impls_trait_rev` + +error: aborting due to 2 previous errors + +For more information about this error, try `rustc --explain E0275`. diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs new file mode 100644 index 00000000000..cda98789886 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.rs @@ -0,0 +1,48 @@ +// compile-flags: -Ztrait-solver=next +#![feature(trivial_bounds, marker_trait_attr)] +#![allow(trivial_bounds)] +// This previously triggered a bug in the provisional cache. +// +// This has the proof tree +// - `MultipleCandidates: Trait` proven via impl-one +// - `MultipleNested: Trait` via impl +// - `MultipleCandidates: Trait` (inductive cycle ~> OVERFLOW) +// - `DoesNotImpl: Trait` (ERR) +// - `MultipleCandidates: Trait` proven via impl-two +// - `MultipleNested: Trait` (in provisional cache ~> OVERFLOW) +// +// We previously incorrectly treated the `MultipleCandidates: Trait` as +// overflow because it was in the cache and reached via an inductive cycle. +// It should be `NoSolution`. + +struct MultipleCandidates; +struct MultipleNested; +struct DoesNotImpl; + +#[marker] +trait Trait {} + +// impl-one +impl Trait for MultipleCandidates +where + MultipleNested: Trait +{} + +// impl-two +impl Trait for MultipleCandidates +where + MultipleNested: Trait, +{} + +impl Trait for MultipleNested +where + MultipleCandidates: Trait, + DoesNotImpl: Trait, +{} + +fn impls_trait<T: Trait>() {} + +fn main() { + impls_trait::<MultipleCandidates>(); + //~^ ERROR the trait bound `MultipleCandidates: Trait` is not satisfied +} diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr new file mode 100644 index 00000000000..57227321a6d --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-err.stderr @@ -0,0 +1,16 @@ +error[E0277]: the trait bound `MultipleCandidates: Trait` is not satisfied + --> $DIR/inductive-cycle-but-err.rs:46:19 + | +LL | impls_trait::<MultipleCandidates>(); + | ^^^^^^^^^^^^^^^^^^ the trait `Trait` is not implemented for `MultipleCandidates` + | + = help: the trait `Trait` is implemented for `MultipleCandidates` +note: required by a bound in `impls_trait` + --> $DIR/inductive-cycle-but-err.rs:43:19 + | +LL | fn impls_trait<T: Trait>() {} + | ^^^^^ required by this bound in `impls_trait` + +error: aborting due to previous error + +For more information about this error, try `rustc --explain E0277`. diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs new file mode 100644 index 00000000000..d4851eb694b --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-but-ok.rs @@ -0,0 +1,44 @@ +// compile-flags: -Ztrait-solver=next +// check-pass +#![feature(trivial_bounds, marker_trait_attr)] +#![allow(trivial_bounds)] + +// This previously triggered a bug in the provisional cache. +// +// This has the proof tree +// - `Root: Trait` proven via impl +// - `MultipleCandidates: Trait` +// - candidate: overflow-impl +// - `Root: Trait` (inductive cycle ~> OVERFLOW) +// - candidate: trivial-impl ~> YES +// - merge respones ~> YES +// - `MultipleCandidates: Trait` (in provisional cache ~> OVERFLOW) +// +// We previously incorrectly treated the `MultipleCandidates: Trait` as +// overflow because it was in the cache and reached via an inductive cycle. +// It should be `YES`. + +struct Root; +struct MultipleCandidates; + +#[marker] +trait Trait {} +impl Trait for Root +where + MultipleCandidates: Trait, + MultipleCandidates: Trait, +{} + +// overflow-impl +impl Trait for MultipleCandidates +where + Root: Trait, +{} +// trivial-impl +impl Trait for MultipleCandidates {} + +fn impls_trait<T: Trait>() {} + +fn main() { + impls_trait::<Root>(); +} diff --git a/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs b/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs new file mode 100644 index 00000000000..530e6d0ecf3 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/inductive-cycle-discarded-coinductive-constraints.rs @@ -0,0 +1,36 @@ +// check-pass +// compile-flags: -Ztrait-solver=next +#![feature(rustc_attrs, marker_trait_attr)] +#[rustc_coinductive] +trait Trait {} + +impl<T, U> Trait for (T, U) +where + (U, T): Trait, + (T, U): Inductive, + (): ConstrainToU32<T>, +{} + +trait ConstrainToU32<T> {} +impl ConstrainToU32<u32> for () {} + +// We only prefer the candidate without an inductive cycle +// once the inductive cycle has the same constraints as the +// other goal. +#[marker] +trait Inductive {} +impl<T, U> Inductive for (T, U) +where + (T, U): Trait, +{} + +impl Inductive for (u32, u32) {} + +fn impls_trait<T, U>() +where + (T, U): Trait, +{} + +fn main() { + impls_trait::<_, _>(); +} diff --git a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs index f06b98a79cf..3cfe7ab87f6 100644 --- a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs +++ b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.rs @@ -39,7 +39,7 @@ fn impls_ar<T: AR>() {} fn main() { impls_a::<()>(); - //~^ ERROR overflow evaluating the requirement `(): A` + // FIXME(-Ztrait-solver=next): This is broken and should error. impls_ar::<()>(); //~^ ERROR overflow evaluating the requirement `(): AR` diff --git a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr index 33fac603cbd..0e1c86c1bb3 100644 --- a/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr +++ b/tests/ui/traits/new-solver/cycles/inductive-not-on-stack.stderr @@ -1,16 +1,3 @@ -error[E0275]: overflow evaluating the requirement `(): A` - --> $DIR/inductive-not-on-stack.rs:41:5 - | -LL | impls_a::<()>(); - | ^^^^^^^^^^^^^ - | - = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`inductive_not_on_stack`) -note: required by a bound in `impls_a` - --> $DIR/inductive-not-on-stack.rs:25:15 - | -LL | fn impls_a<T: A>() {} - | ^ required by this bound in `impls_a` - error[E0275]: overflow evaluating the requirement `(): AR` --> $DIR/inductive-not-on-stack.rs:44:5 | @@ -24,6 +11,6 @@ note: required by a bound in `impls_ar` LL | fn impls_ar<T: AR>() {} | ^^ required by this bound in `impls_ar` -error: aborting due to 2 previous errors +error: aborting due to previous error For more information about this error, try `rustc --explain E0275`. diff --git a/tests/ui/traits/new-solver/leak-check-coinductive-cycle.rs b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs index 1f7d4a49c90..a6d31872673 100644 --- a/tests/ui/traits/new-solver/leak-check-coinductive-cycle.rs +++ b/tests/ui/traits/new-solver/cycles/leak-check-coinductive-cycle.rs @@ -1,5 +1,5 @@ -// check-pass // compile-flags: -Ztrait-solver=next +// check-pass #![feature(rustc_attrs)] #[rustc_coinductive] diff --git a/tests/ui/traits/new-solver/provisional-result-done.rs b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs index 589d34dd7ab..589d34dd7ab 100644 --- a/tests/ui/traits/new-solver/provisional-result-done.rs +++ b/tests/ui/traits/new-solver/cycles/provisional-result-done.rs diff --git a/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs b/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs index 7d15b8c6392..af35a6195e0 100644 --- a/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs +++ b/tests/ui/traits/new-solver/dyn-any-dont-prefer-impl.rs @@ -1,6 +1,10 @@ // compile-flags: -Ztrait-solver=next // check-pass +// Test that selection prefers the builtin trait object impl for `Any` +// instead of the user defined impl. Both impls apply to the trait +// object. + use std::any::Any; fn needs_usize(_: &usize) {} diff --git a/tests/ui/traits/new-solver/exponential-trait-goals.rs b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.rs index b37f09ee185..b37f09ee185 100644 --- a/tests/ui/traits/new-solver/exponential-trait-goals.rs +++ b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.rs diff --git a/tests/ui/traits/new-solver/exponential-trait-goals.stderr b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.stderr index 28a99cbbca6..28a99cbbca6 100644 --- a/tests/ui/traits/new-solver/exponential-trait-goals.stderr +++ b/tests/ui/traits/new-solver/overflow/exponential-trait-goals.stderr diff --git a/tests/ui/traits/new-solver/recursive-self-normalization-2.rs b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.rs index d086db475ac..d086db475ac 100644 --- a/tests/ui/traits/new-solver/recursive-self-normalization-2.rs +++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.rs diff --git a/tests/ui/traits/new-solver/recursive-self-normalization-2.stderr b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.stderr index eebaf21d7df..eebaf21d7df 100644 --- a/tests/ui/traits/new-solver/recursive-self-normalization-2.stderr +++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization-2.stderr diff --git a/tests/ui/traits/new-solver/recursive-self-normalization.rs b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.rs index d15df7dea73..d15df7dea73 100644 --- a/tests/ui/traits/new-solver/recursive-self-normalization.rs +++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.rs diff --git a/tests/ui/traits/new-solver/recursive-self-normalization.stderr b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.stderr index 6a87fe2f121..6a87fe2f121 100644 --- a/tests/ui/traits/new-solver/recursive-self-normalization.stderr +++ b/tests/ui/traits/new-solver/overflow/recursive-self-normalization.stderr |