]>
Commit | Line | Data |
---|---|---|
17df50a5 | 1 | #![feature(min_specialization)] |
923072b8 | 2 | #![feature(rustc_attrs)] |
17df50a5 | 3 | |
fc512014 XL |
4 | #[macro_use] |
5 | extern crate bitflags; | |
5869c6ff XL |
6 | #[macro_use] |
7 | extern crate rustc_macros; | |
fc512014 XL |
8 | |
9 | use rustc_data_structures::stable_hasher::{HashStable, StableHasher}; | |
5869c6ff | 10 | use rustc_data_structures::unify::{EqUnifyValue, UnifyKey}; |
923072b8 | 11 | use smallvec::SmallVec; |
5869c6ff | 12 | use std::fmt; |
923072b8 FG |
13 | use std::fmt::Debug; |
14 | use std::hash::Hash; | |
5869c6ff | 15 | use std::mem::discriminant; |
fc512014 | 16 | |
923072b8 FG |
17 | pub mod codec; |
18 | pub mod sty; | |
19 | ||
20 | pub use codec::*; | |
21 | pub use sty::*; | |
22 | ||
23 | pub trait Interner { | |
24 | type AdtDef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
25 | type SubstsRef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
26 | type DefId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
27 | type Ty: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
28 | type Const: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
29 | type Region: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
30 | type TypeAndMut: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
31 | type Mutability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
32 | type Movability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
33 | type PolyFnSig: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
34 | type ListBinderExistentialPredicate: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
35 | type BinderListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
36 | type ListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
37 | type ProjectionTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
38 | type ParamTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
39 | type BoundTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
40 | type PlaceholderType: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
41 | type InferTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
42 | type DelaySpanBugEmitted: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
43 | type PredicateKind: Clone + Debug + Hash + PartialEq + Eq; | |
44 | type AllocId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
45 | ||
46 | type EarlyBoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
47 | type BoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
48 | type FreeRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
49 | type RegionVid: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
50 | type PlaceholderRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord; | |
51 | } | |
52 | ||
53 | pub trait InternAs<T: ?Sized, R> { | |
54 | type Output; | |
55 | fn intern_with<F>(self, f: F) -> Self::Output | |
56 | where | |
57 | F: FnOnce(&T) -> R; | |
58 | } | |
59 | ||
60 | impl<I, T, R, E> InternAs<[T], R> for I | |
61 | where | |
62 | E: InternIteratorElement<T, R>, | |
63 | I: Iterator<Item = E>, | |
64 | { | |
65 | type Output = E::Output; | |
66 | fn intern_with<F>(self, f: F) -> Self::Output | |
67 | where | |
68 | F: FnOnce(&[T]) -> R, | |
69 | { | |
70 | E::intern_with(self, f) | |
71 | } | |
72 | } | |
73 | ||
74 | pub trait InternIteratorElement<T, R>: Sized { | |
75 | type Output; | |
76 | fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output; | |
77 | } | |
78 | ||
79 | impl<T, R> InternIteratorElement<T, R> for T { | |
80 | type Output = R; | |
81 | fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>( | |
82 | mut iter: I, | |
83 | f: F, | |
84 | ) -> Self::Output { | |
85 | // This code is hot enough that it's worth specializing for the most | |
86 | // common length lists, to avoid the overhead of `SmallVec` creation. | |
87 | // Lengths 0, 1, and 2 typically account for ~95% of cases. If | |
88 | // `size_hint` is incorrect a panic will occur via an `unwrap` or an | |
89 | // `assert`. | |
90 | match iter.size_hint() { | |
91 | (0, Some(0)) => { | |
92 | assert!(iter.next().is_none()); | |
93 | f(&[]) | |
94 | } | |
95 | (1, Some(1)) => { | |
96 | let t0 = iter.next().unwrap(); | |
97 | assert!(iter.next().is_none()); | |
98 | f(&[t0]) | |
99 | } | |
100 | (2, Some(2)) => { | |
101 | let t0 = iter.next().unwrap(); | |
102 | let t1 = iter.next().unwrap(); | |
103 | assert!(iter.next().is_none()); | |
104 | f(&[t0, t1]) | |
105 | } | |
106 | _ => f(&iter.collect::<SmallVec<[_; 8]>>()), | |
107 | } | |
108 | } | |
109 | } | |
110 | ||
111 | impl<'a, T, R> InternIteratorElement<T, R> for &'a T | |
112 | where | |
113 | T: Clone + 'a, | |
114 | { | |
115 | type Output = R; | |
116 | fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output { | |
117 | // This code isn't hot. | |
118 | f(&iter.cloned().collect::<SmallVec<[_; 8]>>()) | |
119 | } | |
120 | } | |
121 | ||
122 | impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> { | |
123 | type Output = Result<R, E>; | |
124 | fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>( | |
125 | mut iter: I, | |
126 | f: F, | |
127 | ) -> Self::Output { | |
128 | // This code is hot enough that it's worth specializing for the most | |
129 | // common length lists, to avoid the overhead of `SmallVec` creation. | |
130 | // Lengths 0, 1, and 2 typically account for ~95% of cases. If | |
131 | // `size_hint` is incorrect a panic will occur via an `unwrap` or an | |
132 | // `assert`, unless a failure happens first, in which case the result | |
133 | // will be an error anyway. | |
134 | Ok(match iter.size_hint() { | |
135 | (0, Some(0)) => { | |
136 | assert!(iter.next().is_none()); | |
137 | f(&[]) | |
138 | } | |
139 | (1, Some(1)) => { | |
140 | let t0 = iter.next().unwrap()?; | |
141 | assert!(iter.next().is_none()); | |
142 | f(&[t0]) | |
143 | } | |
144 | (2, Some(2)) => { | |
145 | let t0 = iter.next().unwrap()?; | |
146 | let t1 = iter.next().unwrap()?; | |
147 | assert!(iter.next().is_none()); | |
148 | f(&[t0, t1]) | |
149 | } | |
150 | _ => f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?), | |
151 | }) | |
152 | } | |
153 | } | |
154 | ||
fc512014 XL |
155 | bitflags! { |
156 | /// Flags that we track on types. These flags are propagated upwards | |
157 | /// through the type during type construction, so that we can quickly check | |
158 | /// whether the type has various kinds of types in it without recursing | |
159 | /// over the type itself. | |
160 | pub struct TypeFlags: u32 { | |
161 | // Does this have parameters? Used to determine whether substitution is | |
162 | // required. | |
163 | /// Does this have `Param`? | |
5099ac24 | 164 | const HAS_TY_PARAM = 1 << 0; |
fc512014 | 165 | /// Does this have `ReEarlyBound`? |
5099ac24 | 166 | const HAS_RE_PARAM = 1 << 1; |
fc512014 | 167 | /// Does this have `ConstKind::Param`? |
5099ac24 | 168 | const HAS_CT_PARAM = 1 << 2; |
fc512014 | 169 | |
5099ac24 FG |
170 | const NEEDS_SUBST = TypeFlags::HAS_TY_PARAM.bits |
171 | | TypeFlags::HAS_RE_PARAM.bits | |
172 | | TypeFlags::HAS_CT_PARAM.bits; | |
fc512014 XL |
173 | |
174 | /// Does this have `Infer`? | |
5099ac24 | 175 | const HAS_TY_INFER = 1 << 3; |
fc512014 | 176 | /// Does this have `ReVar`? |
5099ac24 | 177 | const HAS_RE_INFER = 1 << 4; |
fc512014 | 178 | /// Does this have `ConstKind::Infer`? |
5099ac24 | 179 | const HAS_CT_INFER = 1 << 5; |
fc512014 XL |
180 | |
181 | /// Does this have inference variables? Used to determine whether | |
182 | /// inference is required. | |
5099ac24 FG |
183 | const NEEDS_INFER = TypeFlags::HAS_TY_INFER.bits |
184 | | TypeFlags::HAS_RE_INFER.bits | |
185 | | TypeFlags::HAS_CT_INFER.bits; | |
fc512014 XL |
186 | |
187 | /// Does this have `Placeholder`? | |
5099ac24 | 188 | const HAS_TY_PLACEHOLDER = 1 << 6; |
fc512014 | 189 | /// Does this have `RePlaceholder`? |
5099ac24 | 190 | const HAS_RE_PLACEHOLDER = 1 << 7; |
fc512014 | 191 | /// Does this have `ConstKind::Placeholder`? |
5099ac24 | 192 | const HAS_CT_PLACEHOLDER = 1 << 8; |
fc512014 XL |
193 | |
194 | /// `true` if there are "names" of regions and so forth | |
195 | /// that are local to a particular fn/inferctxt | |
5099ac24 | 196 | const HAS_FREE_LOCAL_REGIONS = 1 << 9; |
fc512014 XL |
197 | |
198 | /// `true` if there are "names" of types and regions and so forth | |
199 | /// that are local to a particular fn | |
5099ac24 FG |
200 | const HAS_FREE_LOCAL_NAMES = TypeFlags::HAS_TY_PARAM.bits |
201 | | TypeFlags::HAS_CT_PARAM.bits | |
202 | | TypeFlags::HAS_TY_INFER.bits | |
203 | | TypeFlags::HAS_CT_INFER.bits | |
204 | | TypeFlags::HAS_TY_PLACEHOLDER.bits | |
205 | | TypeFlags::HAS_CT_PLACEHOLDER.bits | |
206 | // We consider 'freshened' types and constants | |
207 | // to depend on a particular fn. | |
208 | // The freshening process throws away information, | |
209 | // which can make things unsuitable for use in a global | |
210 | // cache. Note that there is no 'fresh lifetime' flag - | |
211 | // freshening replaces all lifetimes with `ReErased`, | |
212 | // which is different from how types/const are freshened. | |
213 | | TypeFlags::HAS_TY_FRESH.bits | |
214 | | TypeFlags::HAS_CT_FRESH.bits | |
215 | | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits; | |
fc512014 XL |
216 | |
217 | /// Does this have `Projection`? | |
5099ac24 | 218 | const HAS_TY_PROJECTION = 1 << 10; |
fc512014 | 219 | /// Does this have `Opaque`? |
5099ac24 | 220 | const HAS_TY_OPAQUE = 1 << 11; |
fc512014 | 221 | /// Does this have `ConstKind::Unevaluated`? |
5099ac24 | 222 | const HAS_CT_PROJECTION = 1 << 12; |
fc512014 XL |
223 | |
224 | /// Could this type be normalized further? | |
5099ac24 FG |
225 | const HAS_PROJECTION = TypeFlags::HAS_TY_PROJECTION.bits |
226 | | TypeFlags::HAS_TY_OPAQUE.bits | |
227 | | TypeFlags::HAS_CT_PROJECTION.bits; | |
fc512014 XL |
228 | |
229 | /// Is an error type/const reachable? | |
5099ac24 | 230 | const HAS_ERROR = 1 << 13; |
fc512014 XL |
231 | |
232 | /// Does this have any region that "appears free" in the type? | |
233 | /// Basically anything but `ReLateBound` and `ReErased`. | |
5099ac24 | 234 | const HAS_FREE_REGIONS = 1 << 14; |
fc512014 XL |
235 | |
236 | /// Does this have any `ReLateBound` regions? Used to check | |
237 | /// if a global bound is safe to evaluate. | |
5099ac24 | 238 | const HAS_RE_LATE_BOUND = 1 << 15; |
fc512014 XL |
239 | |
240 | /// Does this have any `ReErased` regions? | |
5099ac24 | 241 | const HAS_RE_ERASED = 1 << 16; |
fc512014 XL |
242 | |
243 | /// Does this value have parameters/placeholders/inference variables which could be | |
244 | /// replaced later, in a way that would change the results of `impl` specialization? | |
5099ac24 | 245 | const STILL_FURTHER_SPECIALIZABLE = 1 << 17; |
17df50a5 XL |
246 | |
247 | /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`? | |
5099ac24 | 248 | const HAS_TY_FRESH = 1 << 18; |
17df50a5 XL |
249 | |
250 | /// Does this value have `InferConst::Fresh`? | |
5099ac24 | 251 | const HAS_CT_FRESH = 1 << 19; |
fc512014 XL |
252 | } |
253 | } | |
254 | ||
255 | rustc_index::newtype_index! { | |
256 | /// A [De Bruijn index][dbi] is a standard means of representing | |
257 | /// regions (and perhaps later types) in a higher-ranked setting. In | |
258 | /// particular, imagine a type like this: | |
04454e1e FG |
259 | /// ```ignore (illustrative) |
260 | /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char) | |
261 | /// // ^ ^ | | | | |
262 | /// // | | | | | | |
263 | /// // | +------------+ 0 | | | |
264 | /// // | | | | |
265 | /// // +----------------------------------+ 1 | | |
266 | /// // | | | |
267 | /// // +----------------------------------------------+ 0 | |
268 | /// ``` | |
fc512014 XL |
269 | /// In this type, there are two binders (the outer fn and the inner |
270 | /// fn). We need to be able to determine, for any given region, which | |
271 | /// fn type it is bound by, the inner or the outer one. There are | |
272 | /// various ways you can do this, but a De Bruijn index is one of the | |
273 | /// more convenient and has some nice properties. The basic idea is to | |
274 | /// count the number of binders, inside out. Some examples should help | |
275 | /// clarify what I mean. | |
276 | /// | |
277 | /// Let's start with the reference type `&'b isize` that is the first | |
278 | /// argument to the inner function. This region `'b` is assigned a De | |
279 | /// Bruijn index of 0, meaning "the innermost binder" (in this case, a | |
280 | /// fn). The region `'a` that appears in the second argument type (`&'a | |
281 | /// isize`) would then be assigned a De Bruijn index of 1, meaning "the | |
282 | /// second-innermost binder". (These indices are written on the arrows | |
283 | /// in the diagram). | |
284 | /// | |
285 | /// What is interesting is that De Bruijn index attached to a particular | |
286 | /// variable will vary depending on where it appears. For example, | |
287 | /// the final type `&'a char` also refers to the region `'a` declared on | |
288 | /// the outermost fn. But this time, this reference is not nested within | |
289 | /// any other binders (i.e., it is not an argument to the inner fn, but | |
290 | /// rather the outer one). Therefore, in this case, it is assigned a | |
291 | /// De Bruijn index of 0, because the innermost binder in that location | |
292 | /// is the outer fn. | |
293 | /// | |
294 | /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index | |
295 | pub struct DebruijnIndex { | |
296 | DEBUG_FORMAT = "DebruijnIndex({})", | |
297 | const INNERMOST = 0, | |
298 | } | |
299 | } | |
300 | ||
301 | impl DebruijnIndex { | |
302 | /// Returns the resulting index when this value is moved into | |
303 | /// `amount` number of new binders. So, e.g., if you had | |
304 | /// | |
305 | /// for<'a> fn(&'a x) | |
306 | /// | |
307 | /// and you wanted to change it to | |
308 | /// | |
309 | /// for<'a> fn(for<'b> fn(&'a x)) | |
310 | /// | |
311 | /// you would need to shift the index for `'a` into a new binder. | |
312 | #[must_use] | |
313 | pub fn shifted_in(self, amount: u32) -> DebruijnIndex { | |
314 | DebruijnIndex::from_u32(self.as_u32() + amount) | |
315 | } | |
316 | ||
317 | /// Update this index in place by shifting it "in" through | |
318 | /// `amount` number of binders. | |
319 | pub fn shift_in(&mut self, amount: u32) { | |
320 | *self = self.shifted_in(amount); | |
321 | } | |
322 | ||
323 | /// Returns the resulting index when this value is moved out from | |
324 | /// `amount` number of new binders. | |
325 | #[must_use] | |
326 | pub fn shifted_out(self, amount: u32) -> DebruijnIndex { | |
327 | DebruijnIndex::from_u32(self.as_u32() - amount) | |
328 | } | |
329 | ||
330 | /// Update in place by shifting out from `amount` binders. | |
331 | pub fn shift_out(&mut self, amount: u32) { | |
332 | *self = self.shifted_out(amount); | |
333 | } | |
334 | ||
335 | /// Adjusts any De Bruijn indices so as to make `to_binder` the | |
336 | /// innermost binder. That is, if we have something bound at `to_binder`, | |
337 | /// it will now be bound at INNERMOST. This is an appropriate thing to do | |
338 | /// when moving a region out from inside binders: | |
339 | /// | |
04454e1e | 340 | /// ```ignore (illustrative) |
fc512014 XL |
341 | /// for<'a> fn(for<'b> for<'c> fn(&'a u32), _) |
342 | /// // Binder: D3 D2 D1 ^^ | |
343 | /// ``` | |
344 | /// | |
345 | /// Here, the region `'a` would have the De Bruijn index D3, | |
346 | /// because it is the bound 3 binders out. However, if we wanted | |
347 | /// to refer to that region `'a` in the second argument (the `_`), | |
348 | /// those two binders would not be in scope. In that case, we | |
349 | /// might invoke `shift_out_to_binder(D3)`. This would adjust the | |
350 | /// De Bruijn index of `'a` to D1 (the innermost binder). | |
351 | /// | |
352 | /// If we invoke `shift_out_to_binder` and the region is in fact | |
353 | /// bound by one of the binders we are shifting out of, that is an | |
354 | /// error (and should fail an assertion failure). | |
355 | pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self { | |
356 | self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32()) | |
357 | } | |
358 | } | |
359 | ||
5869c6ff XL |
360 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] |
361 | #[derive(Encodable, Decodable)] | |
362 | pub enum IntTy { | |
363 | Isize, | |
364 | I8, | |
365 | I16, | |
366 | I32, | |
367 | I64, | |
368 | I128, | |
369 | } | |
370 | ||
371 | impl IntTy { | |
372 | pub fn name_str(&self) -> &'static str { | |
373 | match *self { | |
374 | IntTy::Isize => "isize", | |
375 | IntTy::I8 => "i8", | |
376 | IntTy::I16 => "i16", | |
377 | IntTy::I32 => "i32", | |
378 | IntTy::I64 => "i64", | |
379 | IntTy::I128 => "i128", | |
380 | } | |
381 | } | |
382 | ||
383 | pub fn bit_width(&self) -> Option<u64> { | |
384 | Some(match *self { | |
385 | IntTy::Isize => return None, | |
386 | IntTy::I8 => 8, | |
387 | IntTy::I16 => 16, | |
388 | IntTy::I32 => 32, | |
389 | IntTy::I64 => 64, | |
390 | IntTy::I128 => 128, | |
391 | }) | |
392 | } | |
393 | ||
394 | pub fn normalize(&self, target_width: u32) -> Self { | |
395 | match self { | |
396 | IntTy::Isize => match target_width { | |
397 | 16 => IntTy::I16, | |
398 | 32 => IntTy::I32, | |
399 | 64 => IntTy::I64, | |
400 | _ => unreachable!(), | |
401 | }, | |
402 | _ => *self, | |
403 | } | |
404 | } | |
405 | } | |
406 | ||
407 | #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Debug)] | |
408 | #[derive(Encodable, Decodable)] | |
409 | pub enum UintTy { | |
410 | Usize, | |
411 | U8, | |
412 | U16, | |
413 | U32, | |
414 | U64, | |
415 | U128, | |
416 | } | |
417 | ||
418 | impl UintTy { | |
419 | pub fn name_str(&self) -> &'static str { | |
420 | match *self { | |
421 | UintTy::Usize => "usize", | |
422 | UintTy::U8 => "u8", | |
423 | UintTy::U16 => "u16", | |
424 | UintTy::U32 => "u32", | |
425 | UintTy::U64 => "u64", | |
426 | UintTy::U128 => "u128", | |
427 | } | |
428 | } | |
429 | ||
430 | pub fn bit_width(&self) -> Option<u64> { | |
431 | Some(match *self { | |
432 | UintTy::Usize => return None, | |
433 | UintTy::U8 => 8, | |
434 | UintTy::U16 => 16, | |
435 | UintTy::U32 => 32, | |
436 | UintTy::U64 => 64, | |
437 | UintTy::U128 => 128, | |
438 | }) | |
439 | } | |
440 | ||
441 | pub fn normalize(&self, target_width: u32) -> Self { | |
442 | match self { | |
443 | UintTy::Usize => match target_width { | |
444 | 16 => UintTy::U16, | |
445 | 32 => UintTy::U32, | |
446 | 64 => UintTy::U64, | |
447 | _ => unreachable!(), | |
448 | }, | |
449 | _ => *self, | |
450 | } | |
451 | } | |
452 | } | |
453 | ||
454 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)] | |
455 | #[derive(Encodable, Decodable)] | |
456 | pub enum FloatTy { | |
457 | F32, | |
458 | F64, | |
459 | } | |
460 | ||
461 | impl FloatTy { | |
462 | pub fn name_str(self) -> &'static str { | |
463 | match self { | |
464 | FloatTy::F32 => "f32", | |
465 | FloatTy::F64 => "f64", | |
466 | } | |
467 | } | |
468 | ||
469 | pub fn bit_width(self) -> u64 { | |
470 | match self { | |
471 | FloatTy::F32 => 32, | |
472 | FloatTy::F64 => 64, | |
473 | } | |
474 | } | |
475 | } | |
476 | ||
477 | #[derive(Clone, Copy, PartialEq, Eq)] | |
478 | pub enum IntVarValue { | |
479 | IntType(IntTy), | |
480 | UintType(UintTy), | |
481 | } | |
482 | ||
483 | #[derive(Clone, Copy, PartialEq, Eq)] | |
484 | pub struct FloatVarValue(pub FloatTy); | |
485 | ||
c295e0f8 XL |
486 | rustc_index::newtype_index! { |
487 | /// A **ty**pe **v**ariable **ID**. | |
488 | pub struct TyVid { | |
489 | DEBUG_FORMAT = "_#{}t" | |
490 | } | |
5869c6ff XL |
491 | } |
492 | ||
493 | /// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**. | |
494 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] | |
495 | pub struct IntVid { | |
496 | pub index: u32, | |
497 | } | |
498 | ||
499 | /// An **float**ing-point (`f32` or `f64`) type **v**ariable **ID**. | |
500 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] | |
501 | pub struct FloatVid { | |
502 | pub index: u32, | |
503 | } | |
504 | ||
505 | /// A placeholder for a type that hasn't been inferred yet. | |
506 | /// | |
507 | /// E.g., if we have an empty array (`[]`), then we create a fresh | |
508 | /// type variable for the element type since we won't know until it's | |
509 | /// used what the element type is supposed to be. | |
510 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)] | |
511 | pub enum InferTy { | |
512 | /// A type variable. | |
513 | TyVar(TyVid), | |
514 | /// An integral type variable (`{integer}`). | |
515 | /// | |
516 | /// These are created when the compiler sees an integer literal like | |
517 | /// `1` that could be several different types (`u8`, `i32`, `u32`, etc.). | |
518 | /// We don't know until it's used what type it's supposed to be, so | |
519 | /// we create a fresh type variable. | |
520 | IntVar(IntVid), | |
521 | /// A floating-point type variable (`{float}`). | |
522 | /// | |
523 | /// These are created when the compiler sees an float literal like | |
524 | /// `1.0` that could be either an `f32` or an `f64`. | |
525 | /// We don't know until it's used what type it's supposed to be, so | |
526 | /// we create a fresh type variable. | |
527 | FloatVar(FloatVid), | |
528 | ||
529 | /// A [`FreshTy`][Self::FreshTy] is one that is generated as a replacement | |
530 | /// for an unbound type variable. This is convenient for caching etc. See | |
531 | /// `rustc_infer::infer::freshen` for more details. | |
532 | /// | |
533 | /// Compare with [`TyVar`][Self::TyVar]. | |
534 | FreshTy(u32), | |
535 | /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`IntVar`][Self::IntVar]. | |
536 | FreshIntTy(u32), | |
537 | /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`FloatVar`][Self::FloatVar]. | |
538 | FreshFloatTy(u32), | |
539 | } | |
540 | ||
541 | /// Raw `TyVid` are used as the unification key for `sub_relations`; | |
542 | /// they carry no values. | |
543 | impl UnifyKey for TyVid { | |
544 | type Value = (); | |
5099ac24 | 545 | #[inline] |
5869c6ff | 546 | fn index(&self) -> u32 { |
c295e0f8 | 547 | self.as_u32() |
5869c6ff | 548 | } |
5099ac24 | 549 | #[inline] |
5869c6ff | 550 | fn from_index(i: u32) -> TyVid { |
c295e0f8 | 551 | TyVid::from_u32(i) |
5869c6ff XL |
552 | } |
553 | fn tag() -> &'static str { | |
554 | "TyVid" | |
555 | } | |
556 | } | |
557 | ||
558 | impl EqUnifyValue for IntVarValue {} | |
559 | ||
560 | impl UnifyKey for IntVid { | |
561 | type Value = Option<IntVarValue>; | |
c295e0f8 | 562 | #[inline] // make this function eligible for inlining - it is quite hot. |
5869c6ff XL |
563 | fn index(&self) -> u32 { |
564 | self.index | |
565 | } | |
5099ac24 | 566 | #[inline] |
5869c6ff XL |
567 | fn from_index(i: u32) -> IntVid { |
568 | IntVid { index: i } | |
569 | } | |
570 | fn tag() -> &'static str { | |
571 | "IntVid" | |
572 | } | |
573 | } | |
574 | ||
575 | impl EqUnifyValue for FloatVarValue {} | |
576 | ||
577 | impl UnifyKey for FloatVid { | |
578 | type Value = Option<FloatVarValue>; | |
5099ac24 | 579 | #[inline] |
5869c6ff XL |
580 | fn index(&self) -> u32 { |
581 | self.index | |
582 | } | |
5099ac24 | 583 | #[inline] |
5869c6ff XL |
584 | fn from_index(i: u32) -> FloatVid { |
585 | FloatVid { index: i } | |
586 | } | |
587 | fn tag() -> &'static str { | |
588 | "FloatVid" | |
589 | } | |
590 | } | |
591 | ||
6a06907d | 592 | #[derive(Copy, Clone, PartialEq, Decodable, Encodable, Hash)] |
5869c6ff XL |
593 | pub enum Variance { |
594 | Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type | |
595 | Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell | |
596 | Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type | |
597 | Bivariant, // T<A> <: T<B> -- e.g., unused type parameter | |
598 | } | |
599 | ||
600 | impl Variance { | |
601 | /// `a.xform(b)` combines the variance of a context with the | |
602 | /// variance of a type with the following meaning. If we are in a | |
603 | /// context with variance `a`, and we encounter a type argument in | |
604 | /// a position with variance `b`, then `a.xform(b)` is the new | |
605 | /// variance with which the argument appears. | |
606 | /// | |
607 | /// Example 1: | |
04454e1e FG |
608 | /// ```ignore (illustrative) |
609 | /// *mut Vec<i32> | |
610 | /// ``` | |
5869c6ff XL |
611 | /// Here, the "ambient" variance starts as covariant. `*mut T` is |
612 | /// invariant with respect to `T`, so the variance in which the | |
613 | /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which | |
614 | /// yields `Invariant`. Now, the type `Vec<T>` is covariant with | |
615 | /// respect to its type argument `T`, and hence the variance of | |
616 | /// the `i32` here is `Invariant.xform(Covariant)`, which results | |
617 | /// (again) in `Invariant`. | |
618 | /// | |
619 | /// Example 2: | |
04454e1e FG |
620 | /// ```ignore (illustrative) |
621 | /// fn(*const Vec<i32>, *mut Vec<i32) | |
622 | /// ``` | |
5869c6ff XL |
623 | /// The ambient variance is covariant. A `fn` type is |
624 | /// contravariant with respect to its parameters, so the variance | |
625 | /// within which both pointer types appear is | |
626 | /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const | |
627 | /// T` is covariant with respect to `T`, so the variance within | |
628 | /// which the first `Vec<i32>` appears is | |
629 | /// `Contravariant.xform(Covariant)` or `Contravariant`. The same | |
630 | /// is true for its `i32` argument. In the `*mut T` case, the | |
631 | /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`, | |
632 | /// and hence the outermost type is `Invariant` with respect to | |
633 | /// `Vec<i32>` (and its `i32` argument). | |
634 | /// | |
635 | /// Source: Figure 1 of "Taming the Wildcards: | |
636 | /// Combining Definition- and Use-Site Variance" published in PLDI'11. | |
637 | pub fn xform(self, v: Variance) -> Variance { | |
638 | match (self, v) { | |
639 | // Figure 1, column 1. | |
640 | (Variance::Covariant, Variance::Covariant) => Variance::Covariant, | |
641 | (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant, | |
642 | (Variance::Covariant, Variance::Invariant) => Variance::Invariant, | |
643 | (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant, | |
644 | ||
645 | // Figure 1, column 2. | |
646 | (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant, | |
647 | (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant, | |
648 | (Variance::Contravariant, Variance::Invariant) => Variance::Invariant, | |
649 | (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant, | |
650 | ||
651 | // Figure 1, column 3. | |
652 | (Variance::Invariant, _) => Variance::Invariant, | |
653 | ||
654 | // Figure 1, column 4. | |
655 | (Variance::Bivariant, _) => Variance::Bivariant, | |
656 | } | |
657 | } | |
658 | } | |
659 | ||
fc512014 XL |
660 | impl<CTX> HashStable<CTX> for DebruijnIndex { |
661 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
662 | self.as_u32().hash_stable(ctx, hasher); | |
663 | } | |
664 | } | |
5869c6ff XL |
665 | |
666 | impl<CTX> HashStable<CTX> for IntTy { | |
667 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
668 | discriminant(self).hash_stable(ctx, hasher); | |
669 | } | |
670 | } | |
671 | ||
672 | impl<CTX> HashStable<CTX> for UintTy { | |
673 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
674 | discriminant(self).hash_stable(ctx, hasher); | |
675 | } | |
676 | } | |
677 | ||
678 | impl<CTX> HashStable<CTX> for FloatTy { | |
679 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
680 | discriminant(self).hash_stable(ctx, hasher); | |
681 | } | |
682 | } | |
683 | ||
684 | impl<CTX> HashStable<CTX> for InferTy { | |
685 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
686 | use InferTy::*; | |
3c0e092e | 687 | discriminant(self).hash_stable(ctx, hasher); |
5869c6ff | 688 | match self { |
c295e0f8 | 689 | TyVar(v) => v.as_u32().hash_stable(ctx, hasher), |
5869c6ff XL |
690 | IntVar(v) => v.index.hash_stable(ctx, hasher), |
691 | FloatVar(v) => v.index.hash_stable(ctx, hasher), | |
692 | FreshTy(v) | FreshIntTy(v) | FreshFloatTy(v) => v.hash_stable(ctx, hasher), | |
693 | } | |
694 | } | |
695 | } | |
696 | ||
697 | impl<CTX> HashStable<CTX> for Variance { | |
698 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
699 | discriminant(self).hash_stable(ctx, hasher); | |
700 | } | |
701 | } | |
702 | ||
703 | impl fmt::Debug for IntVarValue { | |
704 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
705 | match *self { | |
706 | IntVarValue::IntType(ref v) => v.fmt(f), | |
707 | IntVarValue::UintType(ref v) => v.fmt(f), | |
708 | } | |
709 | } | |
710 | } | |
711 | ||
712 | impl fmt::Debug for FloatVarValue { | |
713 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
714 | self.0.fmt(f) | |
715 | } | |
716 | } | |
717 | ||
5869c6ff XL |
718 | impl fmt::Debug for IntVid { |
719 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
720 | write!(f, "_#{}i", self.index) | |
721 | } | |
722 | } | |
723 | ||
724 | impl fmt::Debug for FloatVid { | |
725 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
726 | write!(f, "_#{}f", self.index) | |
727 | } | |
728 | } | |
729 | ||
730 | impl fmt::Debug for InferTy { | |
731 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
732 | use InferTy::*; | |
733 | match *self { | |
734 | TyVar(ref v) => v.fmt(f), | |
735 | IntVar(ref v) => v.fmt(f), | |
736 | FloatVar(ref v) => v.fmt(f), | |
737 | FreshTy(v) => write!(f, "FreshTy({:?})", v), | |
738 | FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v), | |
739 | FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v), | |
740 | } | |
741 | } | |
742 | } | |
743 | ||
744 | impl fmt::Debug for Variance { | |
745 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
746 | f.write_str(match *self { | |
747 | Variance::Covariant => "+", | |
748 | Variance::Contravariant => "-", | |
749 | Variance::Invariant => "o", | |
750 | Variance::Bivariant => "*", | |
751 | }) | |
752 | } | |
753 | } | |
754 | ||
755 | impl fmt::Display for InferTy { | |
756 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
757 | use InferTy::*; | |
758 | match *self { | |
759 | TyVar(_) => write!(f, "_"), | |
760 | IntVar(_) => write!(f, "{}", "{integer}"), | |
761 | FloatVar(_) => write!(f, "{}", "{float}"), | |
762 | FreshTy(v) => write!(f, "FreshTy({})", v), | |
763 | FreshIntTy(v) => write!(f, "FreshIntTy({})", v), | |
764 | FreshFloatTy(v) => write!(f, "FreshFloatTy({})", v), | |
765 | } | |
766 | } | |
767 | } | |
923072b8 FG |
768 | |
769 | rustc_index::newtype_index! { | |
770 | /// "Universes" are used during type- and trait-checking in the | |
771 | /// presence of `for<..>` binders to control what sets of names are | |
772 | /// visible. Universes are arranged into a tree: the root universe | |
773 | /// contains names that are always visible. Each child then adds a new | |
774 | /// set of names that are visible, in addition to those of its parent. | |
775 | /// We say that the child universe "extends" the parent universe with | |
776 | /// new names. | |
777 | /// | |
778 | /// To make this more concrete, consider this program: | |
779 | /// | |
780 | /// ```ignore (illustrative) | |
781 | /// struct Foo { } | |
782 | /// fn bar<T>(x: T) { | |
783 | /// let y: for<'a> fn(&'a u8, Foo) = ...; | |
784 | /// } | |
785 | /// ``` | |
786 | /// | |
787 | /// The struct name `Foo` is in the root universe U0. But the type | |
788 | /// parameter `T`, introduced on `bar`, is in an extended universe U1 | |
789 | /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside | |
790 | /// of `bar`, we cannot name `T`. Then, within the type of `y`, the | |
791 | /// region `'a` is in a universe U2 that extends U1, because we can | |
792 | /// name it inside the fn type but not outside. | |
793 | /// | |
794 | /// Universes are used to do type- and trait-checking around these | |
795 | /// "forall" binders (also called **universal quantification**). The | |
796 | /// idea is that when, in the body of `bar`, we refer to `T` as a | |
797 | /// type, we aren't referring to any type in particular, but rather a | |
798 | /// kind of "fresh" type that is distinct from all other types we have | |
799 | /// actually declared. This is called a **placeholder** type, and we | |
800 | /// use universes to talk about this. In other words, a type name in | |
801 | /// universe 0 always corresponds to some "ground" type that the user | |
802 | /// declared, but a type name in a non-zero universe is a placeholder | |
803 | /// type -- an idealized representative of "types in general" that we | |
804 | /// use for checking generic functions. | |
805 | pub struct UniverseIndex { | |
806 | DEBUG_FORMAT = "U{}", | |
807 | } | |
808 | } | |
809 | ||
810 | impl UniverseIndex { | |
811 | pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0); | |
812 | ||
813 | /// Returns the "next" universe index in order -- this new index | |
814 | /// is considered to extend all previous universes. This | |
815 | /// corresponds to entering a `forall` quantifier. So, for | |
816 | /// example, suppose we have this type in universe `U`: | |
817 | /// | |
818 | /// ```ignore (illustrative) | |
819 | /// for<'a> fn(&'a u32) | |
820 | /// ``` | |
821 | /// | |
822 | /// Once we "enter" into this `for<'a>` quantifier, we are in a | |
823 | /// new universe that extends `U` -- in this new universe, we can | |
824 | /// name the region `'a`, but that region was not nameable from | |
825 | /// `U` because it was not in scope there. | |
826 | pub fn next_universe(self) -> UniverseIndex { | |
827 | UniverseIndex::from_u32(self.private.checked_add(1).unwrap()) | |
828 | } | |
829 | ||
830 | /// Returns `true` if `self` can name a name from `other` -- in other words, | |
831 | /// if the set of names in `self` is a superset of those in | |
832 | /// `other` (`self >= other`). | |
833 | pub fn can_name(self, other: UniverseIndex) -> bool { | |
834 | self.private >= other.private | |
835 | } | |
836 | ||
837 | /// Returns `true` if `self` cannot name some names from `other` -- in other | |
838 | /// words, if the set of names in `self` is a strict subset of | |
839 | /// those in `other` (`self < other`). | |
840 | pub fn cannot_name(self, other: UniverseIndex) -> bool { | |
841 | self.private < other.private | |
842 | } | |
843 | } | |
844 | ||
845 | impl<CTX> HashStable<CTX> for UniverseIndex { | |
846 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
847 | self.private.hash_stable(ctx, hasher); | |
848 | } | |
849 | } |