]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use rustc_hir::def_id::DefId; |
ba9703b0 | 2 | use rustc_middle::ty::{self, Ty, TyVid}; |
dfeec247 XL |
3 | use rustc_span::symbol::Symbol; |
4 | use rustc_span::Span; | |
c1a9b12d | 5 | |
f9f354fc XL |
6 | use crate::infer::InferCtxtUndoLogs; |
7 | ||
dfeec247 XL |
8 | use rustc_data_structures::snapshot_vec as sv; |
9 | use rustc_data_structures::unify as ut; | |
0531ce1d | 10 | use std::cmp; |
85aaf69f | 11 | use std::marker::PhantomData; |
532ac7d7 | 12 | use std::ops::Range; |
1a4d82fc | 13 | |
f9f354fc XL |
14 | use rustc_data_structures::undo_log::{Rollback, UndoLogs}; |
15 | ||
16 | /// Represents a single undo-able action that affects a type inference variable. | |
5099ac24 | 17 | #[derive(Clone)] |
f9f354fc XL |
18 | pub(crate) enum UndoLog<'tcx> { |
19 | EqRelation(sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>), | |
20 | SubRelation(sv::UndoLog<ut::Delegate<ty::TyVid>>), | |
21 | Values(sv::UndoLog<Delegate>), | |
22 | } | |
23 | ||
24 | /// Convert from a specific kind of undo to the more general UndoLog | |
25 | impl<'tcx> From<sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>> for UndoLog<'tcx> { | |
26 | fn from(l: sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>) -> Self { | |
27 | UndoLog::EqRelation(l) | |
28 | } | |
29 | } | |
30 | ||
31 | /// Convert from a specific kind of undo to the more general UndoLog | |
32 | impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::TyVid>>> for UndoLog<'tcx> { | |
33 | fn from(l: sv::UndoLog<ut::Delegate<ty::TyVid>>) -> Self { | |
34 | UndoLog::SubRelation(l) | |
35 | } | |
36 | } | |
37 | ||
38 | /// Convert from a specific kind of undo to the more general UndoLog | |
39 | impl<'tcx> From<sv::UndoLog<Delegate>> for UndoLog<'tcx> { | |
40 | fn from(l: sv::UndoLog<Delegate>) -> Self { | |
41 | UndoLog::Values(l) | |
42 | } | |
43 | } | |
44 | ||
45 | /// Convert from a specific kind of undo to the more general UndoLog | |
46 | impl<'tcx> From<Instantiate> for UndoLog<'tcx> { | |
47 | fn from(l: Instantiate) -> Self { | |
48 | UndoLog::Values(sv::UndoLog::Other(l)) | |
49 | } | |
50 | } | |
51 | ||
52 | impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> { | |
53 | fn reverse(&mut self, undo: UndoLog<'tcx>) { | |
54 | match undo { | |
55 | UndoLog::EqRelation(undo) => self.eq_relations.reverse(undo), | |
56 | UndoLog::SubRelation(undo) => self.sub_relations.reverse(undo), | |
57 | UndoLog::Values(undo) => self.values.reverse(undo), | |
58 | } | |
59 | } | |
60 | } | |
61 | ||
5099ac24 | 62 | #[derive(Clone)] |
f9f354fc XL |
63 | pub struct TypeVariableStorage<'tcx> { |
64 | values: sv::SnapshotVecStorage<Delegate>, | |
cc61c64b XL |
65 | |
66 | /// Two variables are unified in `eq_relations` when we have a | |
0531ce1d XL |
67 | /// constraint `?X == ?Y`. This table also stores, for each key, |
68 | /// the known value. | |
f9f354fc | 69 | eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>, |
cc61c64b | 70 | |
48663c56 | 71 | /// Two variables are unified in `sub_relations` when we have a |
cc61c64b XL |
72 | /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second |
73 | /// table exists only to help with the occurs check. In particular, | |
74 | /// we want to report constraints like these as an occurs check | |
75 | /// violation: | |
04454e1e FG |
76 | /// ``` text |
77 | /// ?1 <: ?3 | |
78 | /// Box<?3> <: ?1 | |
79 | /// ``` | |
94222f64 XL |
80 | /// Without this second table, what would happen in a case like |
81 | /// this is that we would instantiate `?1` with a generalized | |
82 | /// type like `Box<?6>`. We would then relate `Box<?3> <: Box<?6>` | |
83 | /// and infer that `?3 <: ?6`. Next, since `?1` was instantiated, | |
84 | /// we would process `?1 <: ?3`, generalize `?1 = Box<?6>` to `Box<?9>`, | |
85 | /// and instantiate `?3` with `Box<?9>`. Finally, we would relate | |
86 | /// `?6 <: ?9`. But now that we instantiated `?3`, we can process | |
87 | /// `?3 <: ?6`, which gives us `Box<?9> <: ?6`... and the cycle | |
88 | /// continues. (This is `occurs-check-2.rs`.) | |
89 | /// | |
90 | /// What prevents this cycle is that when we generalize | |
91 | /// `Box<?3>` to `Box<?6>`, we also sub-unify `?3` and `?6` | |
92 | /// (in the generalizer). When we then process `Box<?6> <: ?3`, | |
93 | /// the occurs check then fails because `?6` and `?3` are sub-unified, | |
94 | /// and hence generalization fails. | |
cc61c64b XL |
95 | /// |
96 | /// This is reasonable because, in Rust, subtypes have the same | |
97 | /// "skeleton" and hence there is no possible type such that | |
98 | /// (e.g.) `Box<?3> <: ?3` for any `?3`. | |
94222f64 XL |
99 | /// |
100 | /// In practice, we sometimes sub-unify variables in other spots, such | |
101 | /// as when processing subtype predicates. This is not necessary but is | |
102 | /// done to aid diagnostics, as it allows us to be more effective when | |
103 | /// we guide the user towards where they should insert type hints. | |
f9f354fc XL |
104 | sub_relations: ut::UnificationTableStorage<ty::TyVid>, |
105 | } | |
106 | ||
107 | pub struct TypeVariableTable<'a, 'tcx> { | |
108 | storage: &'a mut TypeVariableStorage<'tcx>, | |
109 | ||
110 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
1a4d82fc JJ |
111 | } |
112 | ||
dc9dc135 XL |
113 | #[derive(Copy, Clone, Debug)] |
114 | pub struct TypeVariableOrigin { | |
115 | pub kind: TypeVariableOriginKind, | |
116 | pub span: Span, | |
117 | } | |
118 | ||
476ff2be | 119 | /// Reasons to create a type inference variable |
cc61c64b | 120 | #[derive(Copy, Clone, Debug)] |
dc9dc135 XL |
121 | pub enum TypeVariableOriginKind { |
122 | MiscVariable, | |
123 | NormalizeProjectionType, | |
124 | TypeInference, | |
dfeec247 | 125 | TypeParameterDefinition(Symbol, Option<DefId>), |
ff7c6d11 | 126 | |
dc9dc135 XL |
127 | /// One of the upvars or closure kind parameters in a `ClosureSubsts` |
128 | /// (before it has been determined). | |
ba9703b0 | 129 | // FIXME(eddyb) distinguish upvar inference variables from the rest. |
dc9dc135 XL |
130 | ClosureSynthetic, |
131 | SubstitutionPlaceholder, | |
132 | AutoDeref, | |
133 | AdjustmentType, | |
c295e0f8 XL |
134 | |
135 | /// In type check, when we are type checking a function that | |
136 | /// returns `-> dyn Foo`, we substitute a type variable for the | |
137 | /// return type for diagnostic purposes. | |
138 | DynReturnFn, | |
dc9dc135 | 139 | LatticeVariable, |
476ff2be SL |
140 | } |
141 | ||
5099ac24 | 142 | #[derive(Clone)] |
f9f354fc | 143 | pub(crate) struct TypeVariableData { |
476ff2be | 144 | origin: TypeVariableOrigin, |
1a4d82fc JJ |
145 | } |
146 | ||
0531ce1d XL |
147 | #[derive(Copy, Clone, Debug)] |
148 | pub enum TypeVariableValue<'tcx> { | |
149 | Known { value: Ty<'tcx> }, | |
83c7162d | 150 | Unknown { universe: ty::UniverseIndex }, |
c1a9b12d SL |
151 | } |
152 | ||
0531ce1d | 153 | impl<'tcx> TypeVariableValue<'tcx> { |
83c7162d XL |
154 | /// If this value is known, returns the type it is known to be. |
155 | /// Otherwise, `None`. | |
0531ce1d XL |
156 | pub fn known(&self) -> Option<Ty<'tcx>> { |
157 | match *self { | |
158 | TypeVariableValue::Unknown { .. } => None, | |
159 | TypeVariableValue::Known { value } => Some(value), | |
160 | } | |
161 | } | |
162 | ||
163 | pub fn is_unknown(&self) -> bool { | |
164 | match *self { | |
165 | TypeVariableValue::Unknown { .. } => true, | |
166 | TypeVariableValue::Known { .. } => false, | |
167 | } | |
168 | } | |
1a4d82fc JJ |
169 | } |
170 | ||
5099ac24 | 171 | #[derive(Clone)] |
cdc7bbd5 | 172 | pub(crate) struct Instantiate; |
1a4d82fc | 173 | |
f9f354fc | 174 | pub(crate) struct Delegate; |
1a4d82fc | 175 | |
f9f354fc XL |
176 | impl<'tcx> TypeVariableStorage<'tcx> { |
177 | pub fn new() -> TypeVariableStorage<'tcx> { | |
178 | TypeVariableStorage { | |
179 | values: sv::SnapshotVecStorage::new(), | |
180 | eq_relations: ut::UnificationTableStorage::new(), | |
181 | sub_relations: ut::UnificationTableStorage::new(), | |
54a0048b | 182 | } |
1a4d82fc JJ |
183 | } |
184 | ||
f9f354fc XL |
185 | #[inline] |
186 | pub(crate) fn with_log<'a>( | |
187 | &'a mut self, | |
188 | undo_log: &'a mut InferCtxtUndoLogs<'tcx>, | |
189 | ) -> TypeVariableTable<'a, 'tcx> { | |
190 | TypeVariableTable { storage: self, undo_log } | |
191 | } | |
192 | } | |
193 | ||
194 | impl<'tcx> TypeVariableTable<'_, 'tcx> { | |
0531ce1d XL |
195 | /// Returns the origin that was given when `vid` was created. |
196 | /// | |
197 | /// Note that this function does not return care whether | |
198 | /// `vid` has been unified with something else or not. | |
476ff2be | 199 | pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin { |
c295e0f8 | 200 | &self.storage.values.get(vid.as_usize()).origin |
476ff2be SL |
201 | } |
202 | ||
cc61c64b | 203 | /// Records that `a == b`, depending on `dir`. |
1a4d82fc JJ |
204 | /// |
205 | /// Precondition: neither `a` nor `b` are known. | |
cc61c64b | 206 | pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) { |
0531ce1d XL |
207 | debug_assert!(self.probe(a).is_unknown()); |
208 | debug_assert!(self.probe(b).is_unknown()); | |
f9f354fc XL |
209 | self.eq_relations().union(a, b); |
210 | self.sub_relations().union(a, b); | |
1a4d82fc JJ |
211 | } |
212 | ||
cc61c64b | 213 | /// Records that `a <: b`, depending on `dir`. |
54a0048b | 214 | /// |
cc61c64b XL |
215 | /// Precondition: neither `a` nor `b` are known. |
216 | pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) { | |
0531ce1d XL |
217 | debug_assert!(self.probe(a).is_unknown()); |
218 | debug_assert!(self.probe(b).is_unknown()); | |
f9f354fc | 219 | self.sub_relations().union(a, b); |
cc61c64b XL |
220 | } |
221 | ||
222 | /// Instantiates `vid` with the type `ty`. | |
223 | /// | |
224 | /// Precondition: `vid` must not have been previously instantiated. | |
225 | pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) { | |
226 | let vid = self.root_var(vid); | |
0531ce1d | 227 | debug_assert!(self.probe(vid).is_unknown()); |
dfeec247 | 228 | debug_assert!( |
f9f354fc | 229 | self.eq_relations().probe_value(vid).is_unknown(), |
dfeec247 XL |
230 | "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}", |
231 | vid, | |
232 | ty, | |
f9f354fc | 233 | self.eq_relations().probe_value(vid) |
dfeec247 | 234 | ); |
f9f354fc | 235 | self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty }); |
0531ce1d XL |
236 | |
237 | // Hack: we only need this so that `types_escaping_snapshot` | |
238 | // can see what has been unified; see the Delegate impl for | |
239 | // more details. | |
cdc7bbd5 | 240 | self.undo_log.push(Instantiate); |
1a4d82fc JJ |
241 | } |
242 | ||
0531ce1d XL |
243 | /// Creates a new type variable. |
244 | /// | |
245 | /// - `diverging`: indicates if this is a "diverging" type | |
0731742a | 246 | /// variable, e.g., one created as the type of a `return` |
0531ce1d XL |
247 | /// expression. The code in this module doesn't care if a |
248 | /// variable is diverging, but the main Rust type-checker will | |
249 | /// sometimes "unify" such variables with the `!` or `()` types. | |
250 | /// - `origin`: indicates *why* the type variable was created. | |
251 | /// The code in this module doesn't care, but it can be useful | |
252 | /// for improving error messages. | |
dfeec247 XL |
253 | pub fn new_var( |
254 | &mut self, | |
255 | universe: ty::UniverseIndex, | |
dfeec247 XL |
256 | origin: TypeVariableOrigin, |
257 | ) -> ty::TyVid { | |
f9f354fc | 258 | let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe }); |
0531ce1d | 259 | |
f9f354fc | 260 | let sub_key = self.sub_relations().new_key(()); |
0531ce1d XL |
261 | assert_eq!(eq_key.vid, sub_key); |
262 | ||
c295e0f8 XL |
263 | let index = self.values().push(TypeVariableData { origin }); |
264 | assert_eq!(eq_key.vid.as_u32(), index as u32); | |
0531ce1d | 265 | |
5099ac24 | 266 | debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin); |
0531ce1d XL |
267 | |
268 | eq_key.vid | |
1a4d82fc JJ |
269 | } |
270 | ||
0531ce1d | 271 | /// Returns the number of type variables created thus far. |
476ff2be | 272 | pub fn num_vars(&self) -> usize { |
f9f354fc | 273 | self.storage.values.len() |
476ff2be SL |
274 | } |
275 | ||
cc61c64b XL |
276 | /// Returns the "root" variable of `vid` in the `eq_relations` |
277 | /// equivalence table. All type variables that have been equated | |
278 | /// will yield the same root variable (per the union-find | |
279 | /// algorithm), so `root_var(a) == root_var(b)` implies that `a == | |
280 | /// b` (transitively). | |
54a0048b | 281 | pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid { |
f9f354fc | 282 | self.eq_relations().find(vid).vid |
54a0048b SL |
283 | } |
284 | ||
cc61c64b XL |
285 | /// Returns the "root" variable of `vid` in the `sub_relations` |
286 | /// equivalence table. All type variables that have been are | |
287 | /// related via equality or subtyping will yield the same root | |
288 | /// variable (per the union-find algorithm), so `sub_root_var(a) | |
289 | /// == sub_root_var(b)` implies that: | |
04454e1e FG |
290 | /// ```text |
291 | /// exists X. (a <: X || X <: a) && (b <: X || X <: b) | |
292 | /// ``` | |
cc61c64b | 293 | pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid { |
f9f354fc | 294 | self.sub_relations().find(vid) |
cc61c64b XL |
295 | } |
296 | ||
9fa01778 | 297 | /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some |
cc61c64b XL |
298 | /// type X such that `forall i in {a, b}. (i <: X || X <: i)`. |
299 | pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool { | |
300 | self.sub_root_var(a) == self.sub_root_var(b) | |
301 | } | |
302 | ||
0531ce1d XL |
303 | /// Retrieves the type to which `vid` has been instantiated, if |
304 | /// any. | |
305 | pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> { | |
e74abb32 XL |
306 | self.inlined_probe(vid) |
307 | } | |
308 | ||
309 | /// An always-inlined variant of `probe`, for very hot call sites. | |
310 | #[inline(always)] | |
311 | pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> { | |
f9f354fc | 312 | self.eq_relations().inlined_probe_value(vid) |
1a4d82fc JJ |
313 | } |
314 | ||
0531ce1d XL |
315 | /// If `t` is a type-inference variable, and it has been |
316 | /// instantiated, then return the with which it was | |
317 | /// instantiated. Otherwise, returns `t`. | |
54a0048b | 318 | pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { |
1b1a35ee | 319 | match *t.kind() { |
dfeec247 XL |
320 | ty::Infer(ty::TyVar(v)) => match self.probe(v) { |
321 | TypeVariableValue::Unknown { .. } => t, | |
322 | TypeVariableValue::Known { value } => value, | |
323 | }, | |
1a4d82fc JJ |
324 | _ => t, |
325 | } | |
326 | } | |
327 | ||
f9f354fc XL |
328 | #[inline] |
329 | fn values( | |
330 | &mut self, | |
331 | ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> { | |
332 | self.storage.values.with_log(self.undo_log) | |
1a4d82fc JJ |
333 | } |
334 | ||
f9f354fc XL |
335 | #[inline] |
336 | fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> { | |
337 | self.storage.eq_relations.with_log(self.undo_log) | |
1a4d82fc JJ |
338 | } |
339 | ||
f9f354fc XL |
340 | #[inline] |
341 | fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> { | |
342 | self.storage.sub_relations.with_log(self.undo_log) | |
cc61c64b XL |
343 | } |
344 | ||
532ac7d7 XL |
345 | /// Returns a range of the type variables created during the snapshot. |
346 | pub fn vars_since_snapshot( | |
347 | &mut self, | |
f9f354fc | 348 | value_count: usize, |
532ac7d7 | 349 | ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) { |
c295e0f8 | 350 | let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars()); |
dfeec247 | 351 | ( |
f9f354fc | 352 | range.start..range.end, |
c295e0f8 XL |
353 | (range.start.as_usize()..range.end.as_usize()) |
354 | .map(|index| self.storage.values.get(index).origin) | |
dfeec247 XL |
355 | .collect(), |
356 | ) | |
1a4d82fc JJ |
357 | } |
358 | ||
0531ce1d XL |
359 | /// Returns indices of all variables that are not yet |
360 | /// instantiated. | |
54a0048b | 361 | pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> { |
f9f354fc | 362 | (0..self.storage.values.len()) |
54a0048b | 363 | .filter_map(|i| { |
c295e0f8 | 364 | let vid = ty::TyVid::from_usize(i); |
0531ce1d XL |
365 | match self.probe(vid) { |
366 | TypeVariableValue::Unknown { .. } => Some(vid), | |
367 | TypeVariableValue::Known { .. } => None, | |
54a0048b | 368 | } |
c1a9b12d SL |
369 | }) |
370 | .collect() | |
371 | } | |
1a4d82fc JJ |
372 | } |
373 | ||
0531ce1d XL |
374 | impl sv::SnapshotVecDelegate for Delegate { |
375 | type Value = TypeVariableData; | |
376 | type Undo = Instantiate; | |
377 | ||
378 | fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) { | |
379 | // We don't actually have to *do* anything to reverse an | |
48663c56 | 380 | // instantiation; the value for a variable is stored in the |
0531ce1d XL |
381 | // `eq_relations` and hence its rollback code will handle |
382 | // it. In fact, we could *almost* just remove the | |
383 | // `SnapshotVec` entirely, except that we would have to | |
384 | // reproduce *some* of its logic, since we want to know which | |
385 | // type variables have been instantiated since the snapshot | |
386 | // was started, so we can implement `types_escaping_snapshot`. | |
387 | // | |
388 | // (If we extended the `UnificationTable` to let us see which | |
389 | // values have been unified and so forth, that might also | |
390 | // suffice.) | |
391 | } | |
392 | } | |
393 | ||
394 | /////////////////////////////////////////////////////////////////////////// | |
395 | ||
396 | /// These structs (a newtyped TyVid) are used as the unification key | |
397 | /// for the `eq_relations`; they carry a `TypeVariableValue` along | |
398 | /// with them. | |
399 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
f9f354fc | 400 | pub(crate) struct TyVidEqKey<'tcx> { |
0531ce1d XL |
401 | vid: ty::TyVid, |
402 | ||
403 | // in the table, we map each ty-vid to one of these: | |
404 | phantom: PhantomData<TypeVariableValue<'tcx>>, | |
405 | } | |
406 | ||
407 | impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> { | |
c295e0f8 | 408 | #[inline] // make this function eligible for inlining - it is quite hot. |
0531ce1d XL |
409 | fn from(vid: ty::TyVid) -> Self { |
410 | TyVidEqKey { vid, phantom: PhantomData } | |
411 | } | |
412 | } | |
413 | ||
414 | impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> { | |
415 | type Value = TypeVariableValue<'tcx>; | |
136023e0 | 416 | #[inline(always)] |
dfeec247 | 417 | fn index(&self) -> u32 { |
c295e0f8 | 418 | self.vid.as_u32() |
dfeec247 | 419 | } |
5099ac24 | 420 | #[inline] |
dfeec247 | 421 | fn from_index(i: u32) -> Self { |
c295e0f8 | 422 | TyVidEqKey::from(ty::TyVid::from_u32(i)) |
dfeec247 XL |
423 | } |
424 | fn tag() -> &'static str { | |
425 | "TyVidEqKey" | |
426 | } | |
0531ce1d XL |
427 | } |
428 | ||
429 | impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> { | |
430 | type Error = ut::NoError; | |
431 | ||
432 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> { | |
433 | match (value1, value2) { | |
434 | // We never equate two type variables, both of which | |
435 | // have known types. Instead, we recursively equate | |
436 | // those types. | |
437 | (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => { | |
438 | bug!("equating two type variables, both of which have known types") | |
439 | } | |
440 | ||
441 | // If one side is known, prefer that one. | |
442 | (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1), | |
443 | (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2), | |
1a4d82fc | 444 | |
0531ce1d | 445 | // If both sides are *unknown*, it hardly matters, does it? |
dfeec247 XL |
446 | ( |
447 | &TypeVariableValue::Unknown { universe: universe1 }, | |
448 | &TypeVariableValue::Unknown { universe: universe2 }, | |
449 | ) => { | |
83c7162d XL |
450 | // If we unify two unbound variables, ?T and ?U, then whatever |
451 | // value they wind up taking (which must be the same value) must | |
452 | // be nameable by both universes. Therefore, the resulting | |
453 | // universe is the minimum of the two universes, because that is | |
454 | // the one which contains the fewest names in scope. | |
455 | let universe = cmp::min(universe1, universe2); | |
456 | Ok(TypeVariableValue::Unknown { universe }) | |
457 | } | |
0531ce1d | 458 | } |
1a4d82fc JJ |
459 | } |
460 | } |