rustc_infer/infer/snapshot/
undo_log.rs

Help
1use std::marker::PhantomData;
2
3use rustc_data_structures::undo_log::{Rollback, UndoLogs};
4use rustc_data_structures::{snapshot_vec as sv, unify as ut};
5use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey};
6use tracing::debug;
7
8use crate::infer::unify_key::{ConstVidKey, RegionVidKey};
9use crate::infer::{InferCtxtInner, region_constraints, type_variable};
10use crate::traits;
11
12pub struct Snapshot<'tcx> {
13    pub(crate) undo_len: usize,
14    _marker: PhantomData<&'tcx ()>,
15}
16
17/// Records the "undo" data for a single operation that affects some form of inference variable.
18#[derive(Clone)]
19pub(crate) enum UndoLog<'tcx> {
20    OpaqueTypes(OpaqueTypeKey<'tcx>, Option<OpaqueHiddenType<'tcx>>),
21    TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'tcx>>>),
22    ConstUnificationTable(sv::UndoLog<ut::Delegate<ConstVidKey<'tcx>>>),
23    IntUnificationTable(sv::UndoLog<ut::Delegate<ty::IntVid>>),
24    FloatUnificationTable(sv::UndoLog<ut::Delegate<ty::FloatVid>>),
25    RegionConstraintCollector(region_constraints::UndoLog<'tcx>),
26    RegionUnificationTable(sv::UndoLog<ut::Delegate<RegionVidKey<'tcx>>>),
27    ProjectionCache(traits::UndoLog<'tcx>),
28    PushRegionObligation,
29}
30
31macro_rules! impl_from {
32    ($($ctor:ident ($ty:ty),)*) => {
33        $(
34        impl<'tcx> From<$ty> for UndoLog<'tcx> {
35            fn from(x: $ty) -> Self {
36                UndoLog::$ctor(x.into())
37            }
38        }
39        )*
40    }
41}
42
43// Upcast from a single kind of "undoable action" to the general enum
44impl_from! {
45    RegionConstraintCollector(region_constraints::UndoLog<'tcx>),
46
47    TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'tcx>>>),
48    IntUnificationTable(sv::UndoLog<ut::Delegate<ty::IntVid>>),
49    FloatUnificationTable(sv::UndoLog<ut::Delegate<ty::FloatVid>>),
50
51    ConstUnificationTable(sv::UndoLog<ut::Delegate<ConstVidKey<'tcx>>>),
52
53    RegionUnificationTable(sv::UndoLog<ut::Delegate<RegionVidKey<'tcx>>>),
54    ProjectionCache(traits::UndoLog<'tcx>),
55}
56
57/// The Rollback trait defines how to rollback a particular action.
58impl<'tcx> Rollback<UndoLog<'tcx>> for InferCtxtInner<'tcx> {
59    fn reverse(&mut self, undo: UndoLog<'tcx>) {
60        match undo {
61            UndoLog::OpaqueTypes(key, idx) => self.opaque_type_storage.remove(key, idx),
62            UndoLog::TypeVariables(undo) => self.type_variable_storage.reverse(undo),
63            UndoLog::ConstUnificationTable(undo) => self.const_unification_storage.reverse(undo),
64            UndoLog::IntUnificationTable(undo) => self.int_unification_storage.reverse(undo),
65            UndoLog::FloatUnificationTable(undo) => self.float_unification_storage.reverse(undo),
66            UndoLog::RegionConstraintCollector(undo) => {
67                self.region_constraint_storage.as_mut().unwrap().reverse(undo)
68            }
69            UndoLog::RegionUnificationTable(undo) => {
70                self.region_constraint_storage.as_mut().unwrap().unification_table.reverse(undo)
71            }
72            UndoLog::ProjectionCache(undo) => self.projection_cache.reverse(undo),
73            UndoLog::PushRegionObligation => {
74                self.region_obligations.pop();
75            }
76        }
77    }
78}
79
80/// The combined undo log for all the various unification tables. For each change to the storage
81/// for any kind of inference variable, we record an UndoLog entry in the vector here.
82#[derive(Clone, Default)]
83pub(crate) struct InferCtxtUndoLogs<'tcx> {
84    logs: Vec<UndoLog<'tcx>>,
85    num_open_snapshots: usize,
86}
87
88/// The UndoLogs trait defines how we undo a particular kind of action (of type T). We can undo any
89/// action that is convertible into an UndoLog (per the From impls above).
90impl<'tcx, T> UndoLogs<T> for InferCtxtUndoLogs<'tcx>
91where
92    UndoLog<'tcx>: From<T>,
93{
94    #[inline]
95    fn num_open_snapshots(&self) -> usize {
96        self.num_open_snapshots
97    }
98
99    #[inline]
100    fn push(&mut self, undo: T) {
101        if self.in_snapshot() {
102            self.logs.push(undo.into())
103        }
104    }
105
106    fn clear(&mut self) {
107        self.logs.clear();
108        self.num_open_snapshots = 0;
109    }
110
111    fn extend<J>(&mut self, undos: J)
112    where
113        Self: Sized,
114        J: IntoIterator<Item = T>,
115    {
116        if self.in_snapshot() {
117            self.logs.extend(undos.into_iter().map(UndoLog::from))
118        }
119    }
120}
121
122impl<'tcx> InferCtxtInner<'tcx> {
123    pub fn rollback_to(&mut self, snapshot: Snapshot<'tcx>) {
124        debug!("rollback_to({})", snapshot.undo_len);
125        self.undo_log.assert_open_snapshot(&snapshot);
126
127        while self.undo_log.logs.len() > snapshot.undo_len {
128            let undo = self.undo_log.logs.pop().unwrap();
129            self.reverse(undo);
130        }
131
132        self.type_variable_storage.finalize_rollback();
133
134        if self.undo_log.num_open_snapshots == 1 {
135            // After the root snapshot the undo log should be empty.
136            assert!(snapshot.undo_len == 0);
137            assert!(self.undo_log.logs.is_empty());
138        }
139
140        self.undo_log.num_open_snapshots -= 1;
141    }
142
143    pub fn commit(&mut self, snapshot: Snapshot<'tcx>) {
144        debug!("commit({})", snapshot.undo_len);
145
146        if self.undo_log.num_open_snapshots == 1 {
147            // The root snapshot. It's safe to clear the undo log because
148            // there's no snapshot further out that we might need to roll back
149            // to.
150            assert!(snapshot.undo_len == 0);
151            self.undo_log.logs.clear();
152        }
153
154        self.undo_log.num_open_snapshots -= 1;
155    }
156}
157
158impl<'tcx> InferCtxtUndoLogs<'tcx> {
159    pub(crate) fn start_snapshot(&mut self) -> Snapshot<'tcx> {
160        self.num_open_snapshots += 1;
161        Snapshot { undo_len: self.logs.len(), _marker: PhantomData }
162    }
163
164    pub(crate) fn region_constraints_in_snapshot(
165        &self,
166        s: &Snapshot<'tcx>,
167    ) -> impl Iterator<Item = &'_ region_constraints::UndoLog<'tcx>> + Clone {
168        self.logs[s.undo_len..].iter().filter_map(|log| match log {
169            UndoLog::RegionConstraintCollector(log) => Some(log),
170            _ => None,
171        })
172    }
173
174    pub(crate) fn opaque_types_in_snapshot(&self, s: &Snapshot<'tcx>) -> bool {
175        self.logs[s.undo_len..].iter().any(|log| matches!(log, UndoLog::OpaqueTypes(..)))
176    }
177
178    fn assert_open_snapshot(&self, snapshot: &Snapshot<'tcx>) {
179        // Failures here may indicate a failure to follow a stack discipline.
180        assert!(self.logs.len() >= snapshot.undo_len);
181        assert!(self.num_open_snapshots > 0);
182    }
183}
184
185impl<'tcx> std::ops::Index<usize> for InferCtxtUndoLogs<'tcx> {
186    type Output = UndoLog<'tcx>;
187
188    fn index(&self, key: usize) -> &Self::Output {
189        &self.logs[key]
190    }
191}
192
193impl<'tcx> std::ops::IndexMut<usize> for InferCtxtUndoLogs<'tcx> {
194    fn index_mut(&mut self, key: usize) -> &mut Self::Output {
195        &mut self.logs[key]
196    }
197}
rustc_infer/infer/snapshot/undo_log.rs

rustc_infer/infer/snapshot/
undo_log.rs
