rustc_infer/infer/
type_variable.rs

1use std::cmp;
2use std::marker::PhantomData;
3use std::ops::Range;
4
5use rustc_data_structures::undo_log::Rollback;
6use rustc_data_structures::{snapshot_vec as sv, unify as ut};
7use rustc_hir::def_id::DefId;
8use rustc_index::IndexVec;
9use rustc_middle::bug;
10use rustc_middle::ty::{self, Ty, TyVid};
11use rustc_span::Span;
12use tracing::debug;
13
14use crate::infer::InferCtxtUndoLogs;
15
16impl<'tcx> Rollback<sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>> for TypeVariableStorage<'tcx> {
17    fn reverse(&mut self, undo: sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>) {
18        self.eq_relations.reverse(undo)
19    }
20}
21
22#[derive(Clone, Default)]
23pub(crate) struct TypeVariableStorage<'tcx> {
24    /// The origins of each type variable.
25    values: IndexVec<TyVid, TypeVariableData>,
26    /// Two variables are unified in `eq_relations` when we have a
27    /// constraint `?X == ?Y`. This table also stores, for each key,
28    /// the known value.
29    eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
30}
31
32pub(crate) struct TypeVariableTable<'a, 'tcx> {
33    storage: &'a mut TypeVariableStorage<'tcx>,
34
35    undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
36}
37
38#[derive(Copy, Clone, Debug)]
39pub struct TypeVariableOrigin {
40    pub span: Span,
41    /// `DefId` of the type parameter this was instantiated for, if any.
42    ///
43    /// This should only be used for diagnostics.
44    pub param_def_id: Option<DefId>,
45}
46
47#[derive(Clone)]
48pub(crate) struct TypeVariableData {
49    origin: TypeVariableOrigin,
50}
51
52#[derive(Copy, Clone, Debug)]
53pub(crate) enum TypeVariableValue<'tcx> {
54    Known { value: Ty<'tcx> },
55    Unknown { universe: ty::UniverseIndex },
56}
57
58impl<'tcx> TypeVariableValue<'tcx> {
59    /// If this value is known, returns the type it is known to be.
60    /// Otherwise, `None`.
61    pub(crate) fn known(&self) -> Option<Ty<'tcx>> {
62        match *self {
63            TypeVariableValue::Unknown { .. } => None,
64            TypeVariableValue::Known { value } => Some(value),
65        }
66    }
67
68    pub(crate) fn is_unknown(&self) -> bool {
69        match *self {
70            TypeVariableValue::Unknown { .. } => true,
71            TypeVariableValue::Known { .. } => false,
72        }
73    }
74}
75
76impl<'tcx> TypeVariableStorage<'tcx> {
77    #[inline]
78    pub(crate) fn with_log<'a>(
79        &'a mut self,
80        undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
81    ) -> TypeVariableTable<'a, 'tcx> {
82        TypeVariableTable { storage: self, undo_log }
83    }
84
85    #[inline]
86    pub(crate) fn eq_relations_ref(&self) -> &ut::UnificationTableStorage<TyVidEqKey<'tcx>> {
87        &self.eq_relations
88    }
89
90    pub(super) fn finalize_rollback(&mut self) {
91        debug_assert!(self.values.len() >= self.eq_relations.len());
92        self.values.truncate(self.eq_relations.len());
93    }
94}
95
96impl<'tcx> TypeVariableTable<'_, 'tcx> {
97    /// Returns the origin that was given when `vid` was created.
98    ///
99    /// Note that this function does not return care whether
100    /// `vid` has been unified with something else or not.
101    pub(crate) fn var_origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
102        self.storage.values[vid].origin
103    }
104
105    /// Records that `a == b`, depending on `dir`.
106    ///
107    /// Precondition: neither `a` nor `b` are known.
108    pub(crate) fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
109        debug_assert!(self.probe(a).is_unknown());
110        debug_assert!(self.probe(b).is_unknown());
111        self.eq_relations().union(a, b);
112    }
113
114    /// Instantiates `vid` with the type `ty`.
115    ///
116    /// Precondition: `vid` must not have been previously instantiated.
117    pub(crate) fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
118        let vid = self.root_var(vid);
119        debug_assert!(!ty.is_ty_var(), "instantiating ty var with var: {vid:?} {ty:?}");
120        debug_assert!(self.probe(vid).is_unknown());
121        debug_assert!(
122            self.eq_relations().probe_value(vid).is_unknown(),
123            "instantiating type variable `{vid:?}` twice: new-value = {ty:?}, old-value={:?}",
124            self.eq_relations().probe_value(vid)
125        );
126        self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
127    }
128
129    /// Creates a new type variable.
130    ///
131    /// - `diverging`: indicates if this is a "diverging" type
132    ///   variable, e.g.,  one created as the type of a `return`
133    ///   expression. The code in this module doesn't care if a
134    ///   variable is diverging, but the main Rust type-checker will
135    ///   sometimes "unify" such variables with the `!` or `()` types.
136    /// - `origin`: indicates *why* the type variable was created.
137    ///   The code in this module doesn't care, but it can be useful
138    ///   for improving error messages.
139    pub(crate) fn new_var(
140        &mut self,
141        universe: ty::UniverseIndex,
142        origin: TypeVariableOrigin,
143    ) -> ty::TyVid {
144        let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
145        let index = self.storage.values.push(TypeVariableData { origin });
146        debug_assert_eq!(eq_key.vid, index);
147
148        debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin);
149
150        index
151    }
152
153    /// Returns the number of type variables created thus far.
154    pub(crate) fn num_vars(&self) -> usize {
155        self.storage.values.len()
156    }
157
158    /// Returns the "root" variable of `vid` in the `eq_relations`
159    /// equivalence table. All type variables that have been equated
160    /// will yield the same root variable (per the union-find
161    /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
162    /// b` (transitively).
163    pub(crate) fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
164        self.eq_relations().find(vid).vid
165    }
166
167    /// Retrieves the type to which `vid` has been instantiated, if
168    /// any.
169    pub(crate) fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
170        self.inlined_probe(vid)
171    }
172
173    /// An always-inlined variant of `probe`, for very hot call sites.
174    #[inline(always)]
175    pub(crate) fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
176        self.eq_relations().inlined_probe_value(vid)
177    }
178
179    #[inline]
180    fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
181        self.storage.eq_relations.with_log(self.undo_log)
182    }
183
184    /// Returns a range of the type variables created during the snapshot.
185    pub(crate) fn vars_since_snapshot(
186        &mut self,
187        value_count: usize,
188    ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
189        let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
190        (range.clone(), range.map(|index| self.var_origin(index)).collect())
191    }
192
193    /// Returns indices of all variables that are not yet
194    /// instantiated.
195    pub(crate) fn unresolved_variables(&mut self) -> Vec<ty::TyVid> {
196        (0..self.num_vars())
197            .filter_map(|i| {
198                let vid = ty::TyVid::from_usize(i);
199                match self.probe(vid) {
200                    TypeVariableValue::Unknown { .. } => Some(vid),
201                    TypeVariableValue::Known { .. } => None,
202                }
203            })
204            .collect()
205    }
206}
207
208///////////////////////////////////////////////////////////////////////////
209
210/// These structs (a newtyped TyVid) are used as the unification key
211/// for the `eq_relations`; they carry a `TypeVariableValue` along
212/// with them.
213#[derive(Copy, Clone, Debug, PartialEq, Eq)]
214pub(crate) struct TyVidEqKey<'tcx> {
215    vid: ty::TyVid,
216
217    // in the table, we map each ty-vid to one of these:
218    phantom: PhantomData<TypeVariableValue<'tcx>>,
219}
220
221impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
222    #[inline] // make this function eligible for inlining - it is quite hot.
223    fn from(vid: ty::TyVid) -> Self {
224        TyVidEqKey { vid, phantom: PhantomData }
225    }
226}
227
228impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
229    type Value = TypeVariableValue<'tcx>;
230    #[inline(always)]
231    fn index(&self) -> u32 {
232        self.vid.as_u32()
233    }
234    #[inline]
235    fn from_index(i: u32) -> Self {
236        TyVidEqKey::from(ty::TyVid::from_u32(i))
237    }
238    fn tag() -> &'static str {
239        "TyVidEqKey"
240    }
241    fn order_roots(a: Self, _: &Self::Value, b: Self, _: &Self::Value) -> Option<(Self, Self)> {
242        if a.vid.as_u32() < b.vid.as_u32() { Some((a, b)) } else { Some((b, a)) }
243    }
244}
245
246impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
247    type Error = ut::NoError;
248
249    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
250        match (value1, value2) {
251            // We never equate two type variables, both of which
252            // have known types. Instead, we recursively equate
253            // those types.
254            (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
255                bug!("equating two type variables, both of which have known types")
256            }
257
258            // If one side is known, prefer that one.
259            (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
260            (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
261
262            // If both sides are *unknown*, it hardly matters, does it?
263            (
264                &TypeVariableValue::Unknown { universe: universe1 },
265                &TypeVariableValue::Unknown { universe: universe2 },
266            ) => {
267                // If we unify two unbound variables, ?T and ?U, then whatever
268                // value they wind up taking (which must be the same value) must
269                // be nameable by both universes. Therefore, the resulting
270                // universe is the minimum of the two universes, because that is
271                // the one which contains the fewest names in scope.
272                let universe = cmp::min(universe1, universe2);
273                Ok(TypeVariableValue::Unknown { universe })
274            }
275        }
276    }
277}
rustc_infer/infer/type_variable.rs

rustc_infer/infer/
type_variable.rs
