rustc_infer/infer/snapshot/
undo_log.rs

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

rustc_infer/infer/snapshot/
undo_log.rs
