From 204c9154e2ac43832cd12828216eff64810c50a7 Mon Sep 17 00:00:00 2001 From: Markus Westerlind Date: Tue, 25 Feb 2020 17:09:01 +0100 Subject: [PATCH] refactor: Extract the undo log to its own modules --- src/librustc_infer/infer/mod.rs | 234 +--------------- .../infer/region_constraints/leak_check.rs | 2 +- .../infer/region_constraints/mod.rs | 7 +- src/librustc_infer/infer/undo_log.rs | 259 ++++++++++++++++++ 4 files changed, 272 insertions(+), 230 deletions(-) create mode 100644 src/librustc_infer/infer/undo_log.rs diff --git a/src/librustc_infer/infer/mod.rs b/src/librustc_infer/infer/mod.rs index 90bc1ddc3eb..7bf13c90bf7 100644 --- a/src/librustc_infer/infer/mod.rs +++ b/src/librustc_infer/infer/mod.rs @@ -6,13 +6,14 @@ pub use self::SubregionOrigin::*; pub use self::ValuePairs::*; +pub(crate) use self::undo_log::{InferCtxtUndoLogs, Snapshot, UndoLog}; + use crate::traits::{self, ObligationCause, PredicateObligations, TraitEngine}; use rustc_ast::ast; use rustc_data_structures::fx::{FxHashMap, FxHashSet}; -use rustc_data_structures::snapshot_vec as sv; use rustc_data_structures::sync::Lrc; -use rustc_data_structures::undo_log::{Rollback, Snapshots, UndoLogs}; +use rustc_data_structures::undo_log::{Rollback, Snapshots}; use rustc_data_structures::unify as ut; use rustc_errors::DiagnosticBuilder; use rustc_hir as hir; @@ -69,6 +70,7 @@ pub mod resolve; mod sub; pub mod type_variable; +mod undo_log; use crate::infer::canonical::OriginalQueryValues; pub use rustc_middle::infer::unify_key; @@ -85,6 +87,10 @@ pub struct InferOk<'tcx, T> { pub type UnitResult<'tcx> = RelateResult<'tcx, ()>; // "unify result" pub type FixupResult<'tcx, T> = Result>; // "fixup result" +pub(crate) type UnificationTable<'a, 'tcx, T> = ut::UnificationTable< + ut::InPlace, &'a mut InferCtxtUndoLogs<'tcx>>, +>; + /// How we should handle region solving. /// /// This is used so that the region values inferred by HIR region solving are @@ -270,228 +276,6 @@ pub fn unwrap_region_constraints(&mut self) -> RegionConstraintCollector<'tcx, ' } } -pub struct Snapshot<'tcx> { - undo_len: usize, - _marker: PhantomData<&'tcx ()>, -} - -pub(crate) enum UndoLog<'tcx> { - TypeVariables(type_variable::UndoLog<'tcx>), - ConstUnificationTable(sv::UndoLog>>), - IntUnificationTable(sv::UndoLog>), - FloatUnificationTable(sv::UndoLog>), - RegionConstraintCollector(region_constraints::UndoLog<'tcx>), - RegionUnificationTable(sv::UndoLog>), - ProjectionCache(traits::UndoLog<'tcx>), - PushRegionObligation, -} - -impl<'tcx> From> for UndoLog<'tcx> { - fn from(l: region_constraints::UndoLog<'tcx>) -> Self { - UndoLog::RegionConstraintCollector(l) - } -} - -impl<'tcx> From>>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>>) -> Self { - UndoLog::TypeVariables(type_variable::UndoLog::EqRelation(l)) - } -} - -impl<'tcx> From>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>) -> Self { - UndoLog::TypeVariables(type_variable::UndoLog::SubRelation(l)) - } -} - -impl<'tcx> From> for UndoLog<'tcx> { - fn from(l: sv::UndoLog) -> Self { - UndoLog::TypeVariables(type_variable::UndoLog::Values(l)) - } -} - -impl<'tcx> From for UndoLog<'tcx> { - fn from(l: type_variable::Instantiate) -> Self { - UndoLog::TypeVariables(type_variable::UndoLog::from(l)) - } -} - -impl From> for UndoLog<'tcx> { - fn from(t: type_variable::UndoLog<'tcx>) -> Self { - Self::TypeVariables(t) - } -} - -impl<'tcx> From>>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>>) -> Self { - Self::ConstUnificationTable(l) - } -} - -impl<'tcx> From>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>) -> Self { - Self::IntUnificationTable(l) - } -} - -impl<'tcx> From>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>) -> Self { - Self::FloatUnificationTable(l) - } -} - -impl<'tcx> From>> for UndoLog<'tcx> { - fn from(l: sv::UndoLog>) -> Self { - Self::RegionUnificationTable(l) - } -} - -impl<'tcx> From> for UndoLog<'tcx> { - fn from(l: traits::UndoLog<'tcx>) -> Self { - Self::ProjectionCache(l) - } -} - -pub(crate) type UnificationTable<'a, 'tcx, T> = ut::UnificationTable< - ut::InPlace, &'a mut InferCtxtUndoLogs<'tcx>>, ->; - -struct RollbackView<'tcx, 'a> { - type_variables: &'a mut type_variable::TypeVariableStorage<'tcx>, - const_unification_table: &'a mut ut::UnificationStorage>, - int_unification_table: &'a mut ut::UnificationStorage, - float_unification_table: &'a mut ut::UnificationStorage, - region_constraints: &'a mut RegionConstraintStorage<'tcx>, - projection_cache: &'a mut traits::ProjectionCacheStorage<'tcx>, - region_obligations: &'a mut Vec<(hir::HirId, RegionObligation<'tcx>)>, -} - -impl<'tcx> Rollback> for RollbackView<'tcx, '_> { - fn reverse(&mut self, undo: UndoLog<'tcx>) { - match undo { - UndoLog::TypeVariables(undo) => self.type_variables.reverse(undo), - UndoLog::ConstUnificationTable(undo) => self.const_unification_table.reverse(undo), - UndoLog::IntUnificationTable(undo) => self.int_unification_table.reverse(undo), - UndoLog::FloatUnificationTable(undo) => self.float_unification_table.reverse(undo), - UndoLog::RegionConstraintCollector(undo) => self.region_constraints.reverse(undo), - UndoLog::RegionUnificationTable(undo) => { - self.region_constraints.unification_table.reverse(undo) - } - UndoLog::ProjectionCache(undo) => self.projection_cache.reverse(undo), - UndoLog::PushRegionObligation => { - self.region_obligations.pop(); - } - } - } -} - -pub(crate) struct InferCtxtUndoLogs<'tcx> { - logs: Vec>, - num_open_snapshots: usize, -} - -impl Default for InferCtxtUndoLogs<'_> { - fn default() -> Self { - Self { logs: Default::default(), num_open_snapshots: Default::default() } - } -} - -impl<'tcx, T> UndoLogs for InferCtxtUndoLogs<'tcx> -where - UndoLog<'tcx>: From, -{ - fn num_open_snapshots(&self) -> usize { - self.num_open_snapshots - } - fn push(&mut self, undo: T) { - if self.in_snapshot() { - self.logs.push(undo.into()) - } - } - fn clear(&mut self) { - self.logs.clear(); - self.num_open_snapshots = 0; - } - fn extend(&mut self, undos: J) - where - Self: Sized, - J: IntoIterator, - { - if self.in_snapshot() { - self.logs.extend(undos.into_iter().map(UndoLog::from)) - } - } -} - -impl<'tcx> Snapshots> for InferCtxtUndoLogs<'tcx> { - type Snapshot = Snapshot<'tcx>; - fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[UndoLog<'tcx>] { - &self.logs[snapshot.undo_len..] - } - - fn start_snapshot(&mut self) -> Self::Snapshot { - self.num_open_snapshots += 1; - Snapshot { undo_len: self.logs.len(), _marker: PhantomData } - } - - fn rollback_to(&mut self, values: impl FnOnce() -> R, snapshot: Self::Snapshot) - where - R: Rollback>, - { - debug!("rollback_to({})", snapshot.undo_len); - self.assert_open_snapshot(&snapshot); - - if self.logs.len() > snapshot.undo_len { - let mut values = values(); - while self.logs.len() > snapshot.undo_len { - values.reverse(self.logs.pop().unwrap()); - } - } - - if self.num_open_snapshots == 1 { - // The root snapshot. It's safe to clear the undo log because - // there's no snapshot further out that we might need to roll back - // to. - assert!(snapshot.undo_len == 0); - self.logs.clear(); - } - - self.num_open_snapshots -= 1; - } - - fn commit(&mut self, snapshot: Self::Snapshot) { - debug!("commit({})", snapshot.undo_len); - - if self.num_open_snapshots == 1 { - // The root snapshot. It's safe to clear the undo log because - // there's no snapshot further out that we might need to roll back - // to. - assert!(snapshot.undo_len == 0); - self.logs.clear(); - } - - self.num_open_snapshots -= 1; - } -} - -impl<'tcx> InferCtxtUndoLogs<'tcx> { - pub(crate) fn region_constraints( - &self, - after: usize, - ) -> impl Iterator> + Clone { - self.logs[after..].iter().filter_map(|log| match log { - UndoLog::RegionConstraintCollector(log) => Some(log), - _ => None, - }) - } - - fn assert_open_snapshot(&self, snapshot: &Snapshot<'tcx>) { - // Failures here may indicate a failure to follow a stack discipline. - assert!(self.logs.len() >= snapshot.undo_len); - assert!(self.num_open_snapshots > 0); - } -} - pub struct InferCtxt<'a, 'tcx> { pub tcx: TyCtxt<'tcx>, @@ -1097,7 +881,7 @@ fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot<'a, 'tcx>) { .. } = &mut *self.inner.borrow_mut(); undo_log.rollback_to( - || RollbackView { + || undo_log::RollbackView { type_variables, const_unification_table, int_unification_table, diff --git a/src/librustc_infer/infer/region_constraints/leak_check.rs b/src/librustc_infer/infer/region_constraints/leak_check.rs index 0178fa2eae6..480a5cb4dcc 100644 --- a/src/librustc_infer/infer/region_constraints/leak_check.rs +++ b/src/librustc_infer/infer/region_constraints/leak_check.rs @@ -48,7 +48,7 @@ pub fn leak_check( let mut taint_set = TaintSet::new(TaintDirections::both(), placeholder_region); taint_set.fixed_point( tcx, - self.undo_log.region_constraints(0), + self.undo_log.region_constraints(), &self.storage.data.verifys, ); let tainted_regions = taint_set.into_set(); diff --git a/src/librustc_infer/infer/region_constraints/mod.rs b/src/librustc_infer/infer/region_constraints/mod.rs index 5f6f82ddaf9..ead2494756c 100644 --- a/src/librustc_infer/infer/region_constraints/mod.rs +++ b/src/librustc_infer/infer/region_constraints/mod.rs @@ -500,7 +500,6 @@ pub fn pop_placeholders(&mut self, placeholders: &FxHashSet>) { let constraints_to_kill: Vec = self .undo_log - .logs .iter() .enumerate() .rev() @@ -514,7 +513,7 @@ pub fn pop_placeholders(&mut self, placeholders: &FxHashSet>) { .collect(); for index in constraints_to_kill { - let undo_entry = match &mut self.undo_log.logs[index] { + let undo_entry = match &mut self.undo_log[index] { super::UndoLog::RegionConstraintCollector(undo_entry) => { mem::replace(undo_entry, Purged) } @@ -790,9 +789,9 @@ pub fn vars_since_snapshot( } /// See [`RegionInference::region_constraints_added_in_snapshot`]. - pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'_>) -> Option { + pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option { self.undo_log - .region_constraints(mark.undo_len) + .region_constraints_in_snapshot(mark) .map(|&elt| match elt { AddConstraint(constraint) => Some(constraint.involves_placeholders()), _ => None, diff --git a/src/librustc_infer/infer/undo_log.rs b/src/librustc_infer/infer/undo_log.rs new file mode 100644 index 00000000000..beb71e9e2e8 --- /dev/null +++ b/src/librustc_infer/infer/undo_log.rs @@ -0,0 +1,259 @@ +use std::marker::PhantomData; + +use rustc::ty; +use rustc_data_structures::snapshot_vec as sv; +use rustc_data_structures::undo_log::{Rollback, Snapshots, UndoLogs}; +use rustc_data_structures::unify as ut; +use rustc_hir as hir; + +use crate::{ + infer::{ + region_constraints::{self, RegionConstraintStorage}, + type_variable, RegionObligation, + }, + traits, +}; + +pub struct Snapshot<'tcx> { + pub(crate) undo_len: usize, + _marker: PhantomData<&'tcx ()>, +} + +pub(crate) enum UndoLog<'tcx> { + TypeVariables(type_variable::UndoLog<'tcx>), + ConstUnificationTable(sv::UndoLog>>), + IntUnificationTable(sv::UndoLog>), + FloatUnificationTable(sv::UndoLog>), + RegionConstraintCollector(region_constraints::UndoLog<'tcx>), + RegionUnificationTable(sv::UndoLog>), + ProjectionCache(traits::UndoLog<'tcx>), + PushRegionObligation, +} + +impl<'tcx> From> for UndoLog<'tcx> { + fn from(l: region_constraints::UndoLog<'tcx>) -> Self { + UndoLog::RegionConstraintCollector(l) + } +} + +impl<'tcx> From>>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>>) -> Self { + UndoLog::TypeVariables(type_variable::UndoLog::EqRelation(l)) + } +} + +impl<'tcx> From>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>) -> Self { + UndoLog::TypeVariables(type_variable::UndoLog::SubRelation(l)) + } +} + +impl<'tcx> From> for UndoLog<'tcx> { + fn from(l: sv::UndoLog) -> Self { + UndoLog::TypeVariables(type_variable::UndoLog::Values(l)) + } +} + +impl<'tcx> From for UndoLog<'tcx> { + fn from(l: type_variable::Instantiate) -> Self { + UndoLog::TypeVariables(type_variable::UndoLog::from(l)) + } +} + +impl From> for UndoLog<'tcx> { + fn from(t: type_variable::UndoLog<'tcx>) -> Self { + Self::TypeVariables(t) + } +} + +impl<'tcx> From>>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>>) -> Self { + Self::ConstUnificationTable(l) + } +} + +impl<'tcx> From>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>) -> Self { + Self::IntUnificationTable(l) + } +} + +impl<'tcx> From>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>) -> Self { + Self::FloatUnificationTable(l) + } +} + +impl<'tcx> From>> for UndoLog<'tcx> { + fn from(l: sv::UndoLog>) -> Self { + Self::RegionUnificationTable(l) + } +} + +impl<'tcx> From> for UndoLog<'tcx> { + fn from(l: traits::UndoLog<'tcx>) -> Self { + Self::ProjectionCache(l) + } +} + +pub(super) struct RollbackView<'tcx, 'a> { + pub(super) type_variables: &'a mut type_variable::TypeVariableStorage<'tcx>, + pub(super) const_unification_table: &'a mut ut::UnificationStorage>, + pub(super) int_unification_table: &'a mut ut::UnificationStorage, + pub(super) float_unification_table: &'a mut ut::UnificationStorage, + pub(super) region_constraints: &'a mut RegionConstraintStorage<'tcx>, + pub(super) projection_cache: &'a mut traits::ProjectionCacheStorage<'tcx>, + pub(super) region_obligations: &'a mut Vec<(hir::HirId, RegionObligation<'tcx>)>, +} + +impl<'tcx> Rollback> for RollbackView<'tcx, '_> { + fn reverse(&mut self, undo: UndoLog<'tcx>) { + match undo { + UndoLog::TypeVariables(undo) => self.type_variables.reverse(undo), + UndoLog::ConstUnificationTable(undo) => self.const_unification_table.reverse(undo), + UndoLog::IntUnificationTable(undo) => self.int_unification_table.reverse(undo), + UndoLog::FloatUnificationTable(undo) => self.float_unification_table.reverse(undo), + UndoLog::RegionConstraintCollector(undo) => self.region_constraints.reverse(undo), + UndoLog::RegionUnificationTable(undo) => { + self.region_constraints.unification_table.reverse(undo) + } + UndoLog::ProjectionCache(undo) => self.projection_cache.reverse(undo), + UndoLog::PushRegionObligation => { + self.region_obligations.pop(); + } + } + } +} + +pub(crate) struct InferCtxtUndoLogs<'tcx> { + logs: Vec>, + num_open_snapshots: usize, +} + +impl Default for InferCtxtUndoLogs<'_> { + fn default() -> Self { + Self { logs: Default::default(), num_open_snapshots: Default::default() } + } +} + +impl<'tcx, T> UndoLogs for InferCtxtUndoLogs<'tcx> +where + UndoLog<'tcx>: From, +{ + fn num_open_snapshots(&self) -> usize { + self.num_open_snapshots + } + fn push(&mut self, undo: T) { + if self.in_snapshot() { + self.logs.push(undo.into()) + } + } + fn clear(&mut self) { + self.logs.clear(); + self.num_open_snapshots = 0; + } + fn extend(&mut self, undos: J) + where + Self: Sized, + J: IntoIterator, + { + if self.in_snapshot() { + self.logs.extend(undos.into_iter().map(UndoLog::from)) + } + } +} + +impl<'tcx> Snapshots> for InferCtxtUndoLogs<'tcx> { + type Snapshot = Snapshot<'tcx>; + fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[UndoLog<'tcx>] { + &self.logs[snapshot.undo_len..] + } + + fn start_snapshot(&mut self) -> Self::Snapshot { + self.num_open_snapshots += 1; + Snapshot { undo_len: self.logs.len(), _marker: PhantomData } + } + + fn rollback_to(&mut self, values: impl FnOnce() -> R, snapshot: Self::Snapshot) + where + R: Rollback>, + { + debug!("rollback_to({})", snapshot.undo_len); + self.assert_open_snapshot(&snapshot); + + if self.logs.len() > snapshot.undo_len { + let mut values = values(); + while self.logs.len() > snapshot.undo_len { + values.reverse(self.logs.pop().unwrap()); + } + } + + if self.num_open_snapshots == 1 { + // The root snapshot. It's safe to clear the undo log because + // there's no snapshot further out that we might need to roll back + // to. + assert!(snapshot.undo_len == 0); + self.logs.clear(); + } + + self.num_open_snapshots -= 1; + } + + fn commit(&mut self, snapshot: Self::Snapshot) { + debug!("commit({})", snapshot.undo_len); + + if self.num_open_snapshots == 1 { + // The root snapshot. It's safe to clear the undo log because + // there's no snapshot further out that we might need to roll back + // to. + assert!(snapshot.undo_len == 0); + self.logs.clear(); + } + + self.num_open_snapshots -= 1; + } +} + +impl<'tcx> InferCtxtUndoLogs<'tcx> { + pub(crate) fn region_constraints_in_snapshot( + &self, + s: &Snapshot<'tcx>, + ) -> impl Iterator> + Clone { + self.logs[s.undo_len..].iter().filter_map(|log| match log { + UndoLog::RegionConstraintCollector(log) => Some(log), + _ => None, + }) + } + + pub(crate) fn region_constraints( + &self, + ) -> impl Iterator> + Clone { + self.logs.iter().filter_map(|log| match log { + UndoLog::RegionConstraintCollector(log) => Some(log), + _ => None, + }) + } + + fn assert_open_snapshot(&self, snapshot: &Snapshot<'tcx>) { + // Failures here may indicate a failure to follow a stack discipline. + assert!(self.logs.len() >= snapshot.undo_len); + assert!(self.num_open_snapshots > 0); + } + + pub(crate) fn iter(&self) -> std::slice::Iter<'_, UndoLog<'tcx>> { + self.logs.iter() + } +} + +impl<'tcx> std::ops::Index for InferCtxtUndoLogs<'tcx> { + type Output = UndoLog<'tcx>; + fn index(&self, key: usize) -> &Self::Output { + &self.logs[key] + } +} + +impl<'tcx> std::ops::IndexMut for InferCtxtUndoLogs<'tcx> { + fn index_mut(&mut self, key: usize) -> &mut Self::Output { + &mut self.logs[key] + } +} -- 2.44.0