diff options
6 files changed, 142 insertions, 188 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 deleted file mode 100644 index be48447e27c..00000000000 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ /dev/null @@ -1,102 +0,0 @@ -//! This module both handles the global cache which stores "finished" goals, -//! and the provisional cache which contains partially computed goals. -//! -//! The provisional cache is necessary when dealing with coinductive cycles. -//! -//! For more information about the provisional cache and coinduction in general, -//! check out the relevant section of the rustc-dev-guide. -//! -//! FIXME(@lcnr): Write that section, feel free to ping me if you need help here -//! before then or if I still haven't done that before January 2023. -use super::StackDepth; -use rustc_data_structures::fx::FxHashMap; -use rustc_index::IndexVec; -use rustc_middle::traits::solve::{CanonicalInput, QueryResult}; - -rustc_index::newtype_index! { - pub struct EntryIndex {} -} - -#[derive(Debug, Clone)] -pub(super) struct ProvisionalEntry<'tcx> { - /// 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. - pub(super) input: CanonicalInput<'tcx>, -} - -pub(super) struct ProvisionalCache<'tcx> { - pub(super) entries: IndexVec<EntryIndex, ProvisionalEntry<'tcx>>, - // FIXME: This is only used to quickly check whether a given goal - // is in the cache. We should experiment with using something like - // `SsoHashSet` here because in most cases there are only a few entries. - pub(super) lookup_table: FxHashMap<CanonicalInput<'tcx>, EntryIndex>, -} - -impl<'tcx> ProvisionalCache<'tcx> { - pub(super) fn empty() -> ProvisionalCache<'tcx> { - ProvisionalCache { entries: Default::default(), lookup_table: Default::default() } - } - - pub(super) fn is_empty(&self) -> bool { - self.entries.is_empty() && self.lookup_table.is_empty() - } - - /// Adds a dependency from the current leaf to `target` in the cache - /// to prevent us from moving any goals which depend on the current leaf - /// to the global cache while we're still computing `target`. - /// - /// Its important to note that `target` may already be part of a different cycle. - /// In this case we have to ensure that we also depend on all other goals - /// in the existing cycle in addition to the potentially direct cycle with `target`. - pub(super) fn add_dependency_of_leaf_on(&mut self, target: EntryIndex) { - let depth = self.entries[target].depth; - for provisional_entry in &mut self.entries.raw[target.index()..] { - // The depth of `target` is the position of the deepest goal in the stack - // on which `target` depends. That goal is the `root` of this cycle. - // - // Any entry which was added after `target` is either on the stack itself - // at which point its depth is definitely at least as high as the depth of - // `root`. If it's not on the stack itself it has to depend on a goal - // between `root` and `leaf`. If it were to depend on a goal deeper in the - // stack than `root`, then `root` would also depend on that goal, at which - // point `root` wouldn't be the root anymore. - debug_assert!(provisional_entry.depth >= depth); - provisional_entry.depth = depth; - } - - // We only update entries which were added after `target` as no other - // entry should have a higher depth. - // - // Any entry which previously had a higher depth than target has to - // be between `target` and `root`. Because of this we would have updated - // its depth when calling `add_dependency_of_leaf_on(root)` for `target`. - if cfg!(debug_assertions) { - self.entries.iter().all(|e| e.depth <= depth); - } - } - - pub(super) fn depth(&self, entry_index: EntryIndex) -> StackDepth { - self.entries[entry_index].depth - } - - 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 728d0fc1ae7..33513f6bd43 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -1,10 +1,7 @@ -mod cache; - -use self::cache::ProvisionalEntry; use super::inspect; use super::inspect::ProofTreeBuilder; use super::SolverMode; -use cache::ProvisionalCache; +use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::fx::FxHashSet; use rustc_index::Idx; use rustc_index::IndexVec; @@ -27,8 +24,14 @@ struct StackEntry<'tcx> { // The maximum depth reached by this stack entry, only up-to date // for the top of the stack and lazily updated for the rest. reached_depth: StackDepth, + // In case of a cycle, the depth of the root. + cycle_root_depth: StackDepth, + encountered_overflow: bool, has_been_used: bool, + /// Starts out as `None` and gets set when rerunning this + /// goal in case we encounter a cycle. + provisional_result: Option<QueryResult<'tcx>>, /// We put only the root goal of a coinductive cycle into the global cache. /// @@ -47,7 +50,7 @@ pub(super) struct SearchGraph<'tcx> { /// /// An element is *deeper* in the stack if its index is *lower*. stack: IndexVec<StackDepth, StackEntry<'tcx>>, - provisional_cache: ProvisionalCache<'tcx>, + stack_entries: FxHashMap<CanonicalInput<'tcx>, StackDepth>, } impl<'tcx> SearchGraph<'tcx> { @@ -56,7 +59,7 @@ impl<'tcx> SearchGraph<'tcx> { mode, local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize, stack: Default::default(), - provisional_cache: ProvisionalCache::empty(), + stack_entries: Default::default(), } } @@ -85,6 +88,7 @@ impl<'tcx> SearchGraph<'tcx> { /// would cause us to not track overflow and recursion depth correctly. fn pop_stack(&mut self) -> StackEntry<'tcx> { let elem = self.stack.pop().unwrap(); + assert!(self.stack_entries.remove(&elem.input).is_some()); if let Some(last) = self.stack.raw.last_mut() { last.reached_depth = last.reached_depth.max(elem.reached_depth); last.encountered_overflow |= elem.encountered_overflow; @@ -104,22 +108,17 @@ impl<'tcx> SearchGraph<'tcx> { } pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() && self.provisional_cache.is_empty() + self.stack.is_empty() } /// Whether we're currently in a cycle. This should only be used /// for debug assertions. pub(super) fn in_cycle(&self) -> bool { if let Some(stack_depth) = self.stack.last_index() { - // Either the current goal on the stack is the root of a cycle... - if self.stack[stack_depth].has_been_used { - return true; - } - - // ...or it depends on a goal with a lower depth. - let current_goal = self.stack[stack_depth].input; - let entry_index = self.provisional_cache.lookup_table[¤t_goal]; - self.provisional_cache.entries[entry_index].depth != stack_depth + // Either the current goal on the stack is the root of a cycle + // or it depends on a goal with a lower depth. + self.stack[stack_depth].has_been_used + || self.stack[stack_depth].cycle_root_depth != stack_depth } else { false } @@ -211,9 +210,8 @@ impl<'tcx> SearchGraph<'tcx> { } } - // Look at the provisional cache to detect cycles. - let cache = &mut self.provisional_cache; - match cache.lookup_table.entry(input) { + // Check whether we're in a cycle. + match self.stack_entries.entry(input) { // No entry, we push this goal on the stack and try to prove it. Entry::Vacant(v) => { let depth = self.stack.next_index(); @@ -221,14 +219,14 @@ impl<'tcx> SearchGraph<'tcx> { input, available_depth, reached_depth: depth, + cycle_root_depth: depth, encountered_overflow: false, has_been_used: false, + provisional_result: None, cycle_participants: Default::default(), }; assert_eq!(self.stack.push(entry), depth); - let entry_index = - cache.entries.push(ProvisionalEntry { response: None, depth, input }); - v.insert(entry_index); + v.insert(depth); } // We have a nested goal which relies on a goal `root` deeper in the stack. // @@ -239,41 +237,50 @@ impl<'tcx> SearchGraph<'tcx> { // // Finally we can return either the provisional response for that goal if we have a // coinductive cycle or an ambiguous result if the cycle is inductive. - Entry::Occupied(entry_index) => { + Entry::Occupied(entry) => { inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( CacheHit::Provisional, )); - let entry_index = *entry_index.get(); - let stack_depth = cache.depth(entry_index); + let stack_depth = *entry.get(); debug!("encountered cycle with depth {stack_depth:?}"); - - cache.add_dependency_of_leaf_on(entry_index); - let mut iter = self.stack.iter_mut(); - let root = iter.nth(stack_depth.as_usize()).unwrap(); - for e in iter { - root.cycle_participants.insert(e.input); + // We start by updating the root depth of all cycle participants, and + // add all cycle participants to the root. + let root_depth = self.stack[stack_depth].cycle_root_depth; + let (prev, participants) = self.stack.raw.split_at_mut(stack_depth.as_usize() + 1); + let root = &mut prev[root_depth.as_usize()]; + for entry in participants { + debug_assert!(entry.cycle_root_depth >= root_depth); + entry.cycle_root_depth = root_depth; + root.cycle_participants.insert(entry.input); + // FIXME(@lcnr): I believe that this line is needed as we could + // otherwise access a cache entry for the root of a cycle while + // computing the result for a cycle participant. This can result + // in unstable results due to incompleteness. + // + // However, a test for this would be an even more complex version of + // tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs. + // I did not bother to write such a test and we have no regression test + // for this. It would be good to have such a test :) + #[allow(rustc::potential_query_instability)] + root.cycle_participants.extend(entry.cycle_participants.drain()); } - // If we're in a cycle, we have to retry proving the current goal - // until we reach a fixpoint. + // If we're in a cycle, we have to retry proving the cycle head + // until we reach a fixpoint. It is not enough to simply retry the + // `root` goal of this cycle. + // + // See tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs + // for an example. self.stack[stack_depth].has_been_used = true; - return if let Some(result) = cache.provisional_result(entry_index) { + return if let Some(result) = self.stack[stack_depth].provisional_result { result } else { - // 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()..] + // If we don't have a provisional result yet we're in the first iteration, + // so we start with no constraints. + let is_coinductive = 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); - + .all(|entry| entry.input.value.goal.predicate.is_coinductive(tcx)); if is_coinductive { Self::response_no_constraints(tcx, input, Certainty::Yes) } else { @@ -294,40 +301,25 @@ impl<'tcx> SearchGraph<'tcx> { // of the previous iteration is equal to the final result, at which // point we are done. for _ in 0..self.local_overflow_limit() { - let response = prove_goal(self, inspect); + let result = prove_goal(self, inspect); // Check whether the current goal is the root of a cycle and whether // we have to rerun because its provisional result differed from the // final result. - // - // Also update the response for this goal stored in the provisional - // cache. let stack_entry = self.pop_stack(); debug_assert_eq!(stack_entry.input, input); - let cache = &mut self.provisional_cache; - let provisional_entry_index = - *cache.lookup_table.get(&stack_entry.input).unwrap(); - let provisional_entry = &mut cache.entries[provisional_entry_index]; if stack_entry.has_been_used - && provisional_entry.response.map_or(true, |r| r != response) + && stack_entry.provisional_result.map_or(true, |r| r != result) { - // 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 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); - - // ...and finally push our goal back on the stack and reevaluate it. - self.stack.push(StackEntry { has_been_used: false, ..stack_entry }); + // If so, update its provisional result and reevaluate it. + let depth = self.stack.push(StackEntry { + has_been_used: false, + provisional_result: Some(result), + ..stack_entry + }); + assert_eq!(self.stack_entries.insert(input, depth), None); } else { - return (stack_entry, response); + return (stack_entry, result); } } @@ -343,17 +335,7 @@ impl<'tcx> SearchGraph<'tcx> { // // 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. - let cache = &mut self.provisional_cache; - let provisional_entry_index = *cache.lookup_table.get(&input).unwrap(); - let provisional_entry = &mut cache.entries[provisional_entry_index]; - let depth = provisional_entry.depth; - if depth == self.stack.next_index() { - for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) { - let actual_index = cache.lookup_table.remove(&entry.input); - debug_assert_eq!(Some(i), actual_index); - debug_assert!(entry.depth == depth); - } - + if final_entry.cycle_root_depth == self.stack.next_index() { // When encountering a cycle, both inductive and coinductive, we only // move the root into the global cache. We also store all other cycle // participants involved. @@ -371,8 +353,6 @@ impl<'tcx> SearchGraph<'tcx> { dep_node, result, ) - } else { - provisional_entry.response = Some(result); } result diff --git a/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs b/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs new file mode 100644 index 00000000000..27906392340 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs @@ -0,0 +1,53 @@ +// compile-flags: -Ztrait-solver=next +#![feature(rustc_attrs)] + +// Check that we correctly rerun the trait solver for heads of cycles, +// even if they are not the root. + +struct A<T: ?Sized>(*const T); +struct B<T: ?Sized>(*const T); +struct C<T: ?Sized>(*const T); + +#[rustc_coinductive] +trait Trait<'a, 'b> {} +trait NotImplemented {} + +impl<'a, 'b, T: ?Sized> Trait<'a, 'b> for A<T> where B<T>: Trait<'a, 'b> {} + +// With this the root of `B<T>` is `A<T>`, even if the other impl does +// not have a cycle with `A<T>`. This candidate never applies because of +// the `A<T>: NotImplemented` bound. +impl<'a, 'b, T: ?Sized> Trait<'a, 'b> for B<T> +where + A<T>: Trait<'a, 'b>, + A<T>: NotImplemented, +{ +} + +// This impl directly requires 'b to be equal to 'static. +// +// Because of the coinductive cycle through `C<T>` it also requires +// 'a to be 'static. +impl<'a, T: ?Sized> Trait<'a, 'static> for B<T> +where + C<T>: Trait<'a, 'a>, +{} + +// In the first iteration of `B<T>: Trait<'a, 'b>` we don't add any +// constraints here, only after setting the provisional result to require +// `'b == 'static` do we also add that constraint for `'a`. +impl<'a, 'b, T: ?Sized> Trait<'a, 'b> for C<T> +where + B<T>: Trait<'a, 'b>, +{} + +fn impls_trait<'a, 'b, T: Trait<'a, 'b> + ?Sized>() {} + +fn check<'a, T: ?Sized>() { + impls_trait::<'a, 'static, A<T>>(); + //~^ ERROR lifetime may not live long enough +} + +fn main() { + check::<()>(); +} diff --git a/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr b/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr new file mode 100644 index 00000000000..4cbd0898148 --- /dev/null +++ b/tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.stderr @@ -0,0 +1,10 @@ +error: lifetime may not live long enough + --> $DIR/fixpoint-rerun-all-cycle-heads.rs:47:5 + | +LL | fn check<'a, T: ?Sized>() { + | -- lifetime `'a` defined here +LL | impls_trait::<'a, 'static, A<T>>(); + | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ requires that `'a` must outlive `'static` + +error: aborting due to previous error + 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 3cfe7ab87f6..f06b98a79cf 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::<()>(); - // FIXME(-Ztrait-solver=next): This is broken and should error. + //~^ ERROR overflow evaluating the requirement `(): A` 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 34115334063..859b3f3f1c7 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,3 +1,16 @@ +error[E0275]: overflow evaluating the requirement `(): A` + --> $DIR/inductive-not-on-stack.rs:41:15 + | +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:16 | @@ -11,6 +24,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 previous error +error: aborting due to 2 previous errors For more information about this error, try `rustc --explain E0275`. |