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