diff options
3 files changed, 115 insertions, 153 deletions
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index 74f432a7967..07a96dd7dbb 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs @@ -42,7 +42,7 @@ //! now considered to be in error. //! //! When the call to `process_obligations` completes, you get back an `Outcome`, -//! which includes three bits of information: +//! which includes two bits of information: //! //! - `completed`: a list of obligations where processing was fully //! completed without error (meaning that all transitive subobligations @@ -53,13 +53,10 @@ //! all the obligations in `C` have been found completed. //! - `errors`: a list of errors that occurred and associated backtraces //! at the time of error, which can be used to give context to the user. -//! - `stalled`: if true, then none of the existing obligations were -//! *shallowly successful* (that is, no callback returned `Changed(_)`). -//! This implies that all obligations were either errors or returned an -//! ambiguous result, which means that any further calls to -//! `process_obligations` would simply yield back further ambiguous -//! results. This is used by the `FulfillmentContext` to decide when it -//! has reached a steady state. +//! +//! Upon completion, none of the existing obligations were *shallowly +//! successful* (that is, no callback returned `Changed(_)`). This implies that +//! all obligations were either errors or returned an ambiguous result. //! //! ### Implementation details //! @@ -99,6 +96,8 @@ pub trait ObligationProcessor { type Obligation: ForestObligation; type Error: Debug; + fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool; + fn process_obligation( &mut self, obligation: &mut Self::Obligation, @@ -146,7 +145,7 @@ pub struct ObligationForest<O: ForestObligation> { /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately, /// its contents are not guaranteed to match those of `nodes`. See the - /// comments in [`Self::process_obligation` for details. + /// comments in `Self::process_obligation` for details. active_cache: FxHashMap<O::CacheKey, usize>, /// A vector reused in [Self::compress()] and [Self::find_cycles_from_node()], @@ -260,8 +259,6 @@ pub trait OutcomeTrait { type Obligation; fn new() -> Self; - fn mark_not_stalled(&mut self); - fn is_stalled(&self) -> bool; fn record_completed(&mut self, outcome: &Self::Obligation); fn record_error(&mut self, error: Self::Error); } @@ -270,14 +267,6 @@ pub trait OutcomeTrait { pub struct Outcome<O, E> { /// Backtrace of obligations that were found to be in error. pub errors: Vec<Error<O, E>>, - - /// If true, then we saw no successful obligations, which means - /// there is no point in further iteration. This is based on the - /// assumption that when trait matching returns `Error` or - /// `Unchanged`, those results do not affect environmental - /// inference state. (Note that if we invoke `process_obligations` - /// with no pending obligations, stalled will be true.) - pub stalled: bool, } impl<O, E> OutcomeTrait for Outcome<O, E> { @@ -285,15 +274,7 @@ impl<O, E> OutcomeTrait for Outcome<O, E> { type Obligation = O; fn new() -> Self { - Self { stalled: true, errors: vec![] } - } - - fn mark_not_stalled(&mut self) { - self.stalled = false; - } - - fn is_stalled(&self) -> bool { - self.stalled + Self { errors: vec![] } } fn record_completed(&mut self, _outcome: &Self::Obligation) { @@ -415,10 +396,7 @@ impl<O: ForestObligation> ObligationForest<O> { .insert(node.obligation.as_cache_key()); } - /// Performs a pass through the obligation list. This must - /// be called in a loop until `outcome.stalled` is false. - /// - /// This _cannot_ be unrolled (presently, at least). + /// Performs a fixpoint computation over the obligation list. #[inline(never)] pub fn process_obligations<P, OUT>(&mut self, processor: &mut P) -> OUT where @@ -427,55 +405,69 @@ impl<O: ForestObligation> ObligationForest<O> { { let mut outcome = OUT::new(); - // Note that the loop body can append new nodes, and those new nodes - // will then be processed by subsequent iterations of the loop. - // - // We can't use an iterator for the loop because `self.nodes` is - // appended to and the borrow checker would complain. We also can't use - // `for index in 0..self.nodes.len() { ... }` because the range would - // be computed with the initial length, and we would miss the appended - // nodes. Therefore we use a `while` loop. - let mut index = 0; - while let Some(node) = self.nodes.get_mut(index) { - // `processor.process_obligation` can modify the predicate within - // `node.obligation`, and that predicate is the key used for - // `self.active_cache`. This means that `self.active_cache` can get - // out of sync with `nodes`. It's not very common, but it does - // happen, and code in `compress` has to allow for it. - if node.state.get() != NodeState::Pending { - index += 1; - continue; - } - - match processor.process_obligation(&mut node.obligation) { - ProcessResult::Unchanged => { - // No change in state. + // Fixpoint computation: we repeat until the inner loop stalls. + loop { + let mut has_changed = false; + + // Note that the loop body can append new nodes, and those new nodes + // will then be processed by subsequent iterations of the loop. + // + // We can't use an iterator for the loop because `self.nodes` is + // appended to and the borrow checker would complain. We also can't use + // `for index in 0..self.nodes.len() { ... }` because the range would + // be computed with the initial length, and we would miss the appended + // nodes. Therefore we use a `while` loop. + let mut index = 0; + while let Some(node) = self.nodes.get_mut(index) { + if node.state.get() != NodeState::Pending + || !processor.needs_process_obligation(&node.obligation) + { + index += 1; + continue; } - ProcessResult::Changed(children) => { - // We are not (yet) stalled. - outcome.mark_not_stalled(); - node.state.set(NodeState::Success); - - for child in children { - let st = self.register_obligation_at(child, Some(index)); - if let Err(()) = st { - // Error already reported - propagate it - // to our node. - self.error_at(index); + + // `processor.process_obligation` can modify the predicate within + // `node.obligation`, and that predicate is the key used for + // `self.active_cache`. This means that `self.active_cache` can get + // out of sync with `nodes`. It's not very common, but it does + // happen, and code in `compress` has to allow for it. + + match processor.process_obligation(&mut node.obligation) { + ProcessResult::Unchanged => { + // No change in state. + } + ProcessResult::Changed(children) => { + // We are not (yet) stalled. + has_changed = true; + node.state.set(NodeState::Success); + + for child in children { + let st = self.register_obligation_at(child, Some(index)); + if let Err(()) = st { + // Error already reported - propagate it + // to our node. + self.error_at(index); + } } } + ProcessResult::Error(err) => { + has_changed = true; + outcome.record_error(Error { error: err, backtrace: self.error_at(index) }); + } } - ProcessResult::Error(err) => { - outcome.mark_not_stalled(); - outcome.record_error(Error { error: err, backtrace: self.error_at(index) }); - } + index += 1; + } + + // If unchanged, then we saw no successful obligations, which means + // there is no point in further iteration. This is based on the + // assumption that when trait matching returns `Error` or + // `Unchanged`, those results do not affect environmental inference + // state. (Note that this will occur if we invoke + // `process_obligations` with no pending obligations.) + if !has_changed { + break; } - index += 1; - } - // There's no need to perform marking, cycle processing and compression when nothing - // changed. - if !outcome.is_stalled() { self.mark_successes(); self.process_cycles(processor); self.compress(|obl| outcome.record_completed(obl)); @@ -634,17 +626,14 @@ impl<O: ForestObligation> ObligationForest<O> { } } NodeState::Done => { - // This lookup can fail because the contents of + // The removal lookup might fail because the contents of // `self.active_cache` are not guaranteed to match those of // `self.nodes`. See the comment in `process_obligation` // for more details. - if let Some((predicate, _)) = - self.active_cache.remove_entry(&node.obligation.as_cache_key()) - { - self.done_cache.insert(predicate); - } else { - self.done_cache.insert(node.obligation.as_cache_key().clone()); - } + let cache_key = node.obligation.as_cache_key(); + self.active_cache.remove(&cache_key); + self.done_cache.insert(cache_key); + // Extract the success stories. outcome_cb(&node.obligation); node_rewrites[index] = orig_nodes_len; diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs index 371c62c063f..e2991aae174 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/tests.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs @@ -20,7 +20,6 @@ struct ClosureObligationProcessor<OF, BF, O, E> { struct TestOutcome<O, E> { pub completed: Vec<O>, pub errors: Vec<Error<O, E>>, - pub stalled: bool, } impl<O, E> OutcomeTrait for TestOutcome<O, E> @@ -31,15 +30,7 @@ where type Obligation = O; fn new() -> Self { - Self { errors: vec![], stalled: false, completed: vec![] } - } - - fn mark_not_stalled(&mut self) { - self.stalled = false; - } - - fn is_stalled(&self) -> bool { - self.stalled + Self { errors: vec![], completed: vec![] } } fn record_completed(&mut self, outcome: &Self::Obligation) { @@ -74,6 +65,10 @@ where type Obligation = O; type Error = E; + fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool { + true + } + fn process_obligation( &mut self, obligation: &mut Self::Obligation, diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs index 70d8fdae651..d61166437d7 100644 --- a/compiler/rustc_trait_selection/src/traits/fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs @@ -133,27 +133,16 @@ impl<'a, 'tcx> FulfillmentContext<'tcx> { let mut errors = Vec::new(); - loop { - debug!("select: starting another iteration"); + // Process pending obligations. + let outcome: Outcome<_, _> = self.predicates.process_obligations(&mut FulfillProcessor { + selcx, + register_region_obligations: self.register_region_obligations, + }); - // Process pending obligations. - let outcome: Outcome<_, _> = - self.predicates.process_obligations(&mut FulfillProcessor { - selcx, - register_region_obligations: self.register_region_obligations, - }); - debug!("select: outcome={:#?}", outcome); + // FIXME: if we kept the original cache key, we could mark projection + // obligations as complete for the projection cache here. - // FIXME: if we kept the original cache key, we could mark projection - // obligations as complete for the projection cache here. - - errors.extend(outcome.errors.into_iter().map(to_fulfillment_error)); - - // If nothing new was added, no need to keep looping. - if outcome.stalled { - break; - } - } + errors.extend(outcome.errors.into_iter().map(to_fulfillment_error)); debug!( "select({} predicates remaining, {} errors) done", @@ -264,22 +253,16 @@ impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> { type Obligation = PendingPredicateObligation<'tcx>; type Error = FulfillmentErrorCode<'tcx>; - /// Processes a predicate obligation and returns either: - /// - `Changed(v)` if the predicate is true, presuming that `v` are also true - /// - `Unchanged` if we don't have enough info to be sure - /// - `Error(e)` if the predicate does not hold + /// Identifies whether a predicate obligation needs processing. /// /// This is always inlined, despite its size, because it has a single /// callsite and it is called *very* frequently. #[inline(always)] - fn process_obligation( - &mut self, - pending_obligation: &mut Self::Obligation, - ) -> ProcessResult<Self::Obligation, Self::Error> { + fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool { // If we were stalled on some unresolved variables, first check whether // any of them have been resolved; if not, don't bother doing more work // yet. - let change = match pending_obligation.stalled_on.len() { + match pending_obligation.stalled_on.len() { // Match arms are in order of frequency, which matters because this // code is so hot. 1 and 0 dominate; 2+ is fairly rare. 1 => { @@ -302,42 +285,18 @@ impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> { false })() } - }; - - if !change { - debug!( - "process_predicate: pending obligation {:?} still stalled on {:?}", - self.selcx.infcx().resolve_vars_if_possible(pending_obligation.obligation.clone()), - pending_obligation.stalled_on - ); - return ProcessResult::Unchanged; - } - - self.process_changed_obligations(pending_obligation) - } - - fn process_backedge<'c, I>( - &mut self, - cycle: I, - _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>, - ) where - I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>, - { - if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) { - debug!("process_child_obligations: coinductive match"); - } else { - let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect(); - self.selcx.infcx().report_overflow_error_cycle(&cycle); } } -} -impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> { - // The code calling this method is extremely hot and only rarely - // actually uses this, so move this part of the code - // out of that loop. + /// Processes a predicate obligation and returns either: + /// - `Changed(v)` if the predicate is true, presuming that `v` are also true + /// - `Unchanged` if we don't have enough info to be sure + /// - `Error(e)` if the predicate does not hold + /// + /// This is called much less often than `needs_process_obligation`, so we + /// never inline it. #[inline(never)] - fn process_changed_obligations( + fn process_obligation( &mut self, pending_obligation: &mut PendingPredicateObligation<'tcx>, ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> { @@ -352,6 +311,8 @@ impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> { self.selcx.infcx().resolve_vars_if_possible(obligation.predicate); } + let obligation = &pending_obligation.obligation; + debug!(?obligation, ?obligation.cause, "process_obligation"); let infcx = self.selcx.infcx(); @@ -668,6 +629,23 @@ impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> { } } + fn process_backedge<'c, I>( + &mut self, + cycle: I, + _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>, + ) where + I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>, + { + if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) { + debug!("process_child_obligations: coinductive match"); + } else { + let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect(); + self.selcx.infcx().report_overflow_error_cycle(&cycle); + } + } +} + +impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, 'tcx> { #[instrument(level = "debug", skip(self, obligation, stalled_on))] fn process_trait_obligation( &mut self, |