rustc_type_ir/
flags.rs

1use crate::inherent::*;
2use crate::visit::Flags;
3use crate::{self as ty, Interner};
4
5bitflags::bitflags! {
6    /// Flags that we track on types. These flags are propagated upwards
7    /// through the type during type construction, so that we can quickly check
8    /// whether the type has various kinds of types in it without recursing
9    /// over the type itself.
10    #[derive(Debug, PartialEq, Eq, Clone, Copy)]
11    pub struct TypeFlags: u32 {
12        // Does this have parameters? Used to determine whether instantiation is
13        // required.
14        /// Does this have `Param`?
15        const HAS_TY_PARAM                = 1 << 0;
16        /// Does this have `ReEarlyParam`?
17        const HAS_RE_PARAM                = 1 << 1;
18        /// Does this have `ConstKind::Param`?
19        const HAS_CT_PARAM                = 1 << 2;
20
21        const HAS_PARAM                   = TypeFlags::HAS_TY_PARAM.bits()
22                                          | TypeFlags::HAS_RE_PARAM.bits()
23                                          | TypeFlags::HAS_CT_PARAM.bits();
24
25        /// Does this have `Infer`?
26        const HAS_TY_INFER                = 1 << 3;
27        /// Does this have `ReVar`?
28        const HAS_RE_INFER                = 1 << 4;
29        /// Does this have `ConstKind::Infer`?
30        const HAS_CT_INFER                = 1 << 5;
31
32        /// Does this have inference variables? Used to determine whether
33        /// inference is required.
34        const HAS_INFER                   = TypeFlags::HAS_TY_INFER.bits()
35                                          | TypeFlags::HAS_RE_INFER.bits()
36                                          | TypeFlags::HAS_CT_INFER.bits();
37
38        /// Does this have `Placeholder`?
39        const HAS_TY_PLACEHOLDER          = 1 << 6;
40        /// Does this have `RePlaceholder`?
41        const HAS_RE_PLACEHOLDER          = 1 << 7;
42        /// Does this have `ConstKind::Placeholder`?
43        const HAS_CT_PLACEHOLDER          = 1 << 8;
44
45        /// Does this have placeholders?
46        const HAS_PLACEHOLDER             = TypeFlags::HAS_TY_PLACEHOLDER.bits()
47                                          | TypeFlags::HAS_RE_PLACEHOLDER.bits()
48                                          | TypeFlags::HAS_CT_PLACEHOLDER.bits();
49
50        /// `true` if there are "names" of regions and so forth
51        /// that are local to a particular fn/inferctxt
52        const HAS_FREE_LOCAL_REGIONS      = 1 << 9;
53
54        /// `true` if there are "names" of types and regions and so forth
55        /// that are local to a particular fn
56        const HAS_FREE_LOCAL_NAMES        = TypeFlags::HAS_TY_PARAM.bits()
57                                          | TypeFlags::HAS_CT_PARAM.bits()
58                                          | TypeFlags::HAS_TY_INFER.bits()
59                                          | TypeFlags::HAS_CT_INFER.bits()
60                                          | TypeFlags::HAS_TY_PLACEHOLDER.bits()
61                                          | TypeFlags::HAS_CT_PLACEHOLDER.bits()
62                                          // We consider 'freshened' types and constants
63                                          // to depend on a particular fn.
64                                          // The freshening process throws away information,
65                                          // which can make things unsuitable for use in a global
66                                          // cache. Note that there is no 'fresh lifetime' flag -
67                                          // freshening replaces all lifetimes with `ReErased`,
68                                          // which is different from how types/const are freshened.
69                                          | TypeFlags::HAS_TY_FRESH.bits()
70                                          | TypeFlags::HAS_CT_FRESH.bits()
71                                          | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits()
72                                          | TypeFlags::HAS_RE_ERASED.bits();
73
74        /// Does this have `Projection`?
75        const HAS_TY_PROJECTION           = 1 << 10;
76        /// Does this have `Free` aliases?
77        const HAS_TY_FREE_ALIAS                 = 1 << 11;
78        /// Does this have `Opaque`?
79        const HAS_TY_OPAQUE               = 1 << 12;
80        /// Does this have `Inherent`?
81        const HAS_TY_INHERENT             = 1 << 13;
82        /// Does this have `ConstKind::Unevaluated`?
83        const HAS_CT_PROJECTION           = 1 << 14;
84
85        /// Does this have `Alias` or `ConstKind::Unevaluated`?
86        ///
87        /// Rephrased, could this term be normalized further?
88        const HAS_ALIAS                   = TypeFlags::HAS_TY_PROJECTION.bits()
89                                          | TypeFlags::HAS_TY_FREE_ALIAS.bits()
90                                          | TypeFlags::HAS_TY_OPAQUE.bits()
91                                          | TypeFlags::HAS_TY_INHERENT.bits()
92                                          | TypeFlags::HAS_CT_PROJECTION.bits();
93
94        /// Is an error type/lifetime/const reachable?
95        const HAS_ERROR                   = 1 << 15;
96
97        /// Does this have any region that "appears free" in the type?
98        /// Basically anything but `ReBound` and `ReErased`.
99        const HAS_FREE_REGIONS            = 1 << 16;
100
101        /// Does this have any `ReBound` regions?
102        const HAS_RE_BOUND                = 1 << 17;
103        /// Does this have any `Bound` types?
104        const HAS_TY_BOUND                = 1 << 18;
105        /// Does this have any `ConstKind::Bound` consts?
106        const HAS_CT_BOUND                = 1 << 19;
107        /// Does this have any bound variables?
108        /// Used to check if a global bound is safe to evaluate.
109        const HAS_BOUND_VARS              = TypeFlags::HAS_RE_BOUND.bits()
110                                          | TypeFlags::HAS_TY_BOUND.bits()
111                                          | TypeFlags::HAS_CT_BOUND.bits();
112
113        /// Does this have any `ReErased` regions?
114        const HAS_RE_ERASED               = 1 << 20;
115
116        /// Does this value have parameters/placeholders/inference variables which could be
117        /// replaced later, in a way that would change the results of `impl` specialization?
118        const STILL_FURTHER_SPECIALIZABLE = TypeFlags::HAS_TY_PARAM.bits()
119                                          | TypeFlags::HAS_TY_PLACEHOLDER.bits()
120                                          | TypeFlags::HAS_TY_INFER.bits()
121                                          | TypeFlags::HAS_CT_PARAM.bits()
122                                          | TypeFlags::HAS_CT_PLACEHOLDER.bits()
123                                          | TypeFlags::HAS_CT_INFER.bits();
124
125        /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`?
126        const HAS_TY_FRESH                = 1 << 21;
127
128        /// Does this value have `InferConst::Fresh`?
129        const HAS_CT_FRESH                = 1 << 22;
130
131        /// Does this have any binders with bound vars (e.g. that need to be anonymized)?
132        const HAS_BINDER_VARS             = 1 << 23;
133    }
134}
135
136#[derive(Debug)]
137pub struct FlagComputation<I> {
138    pub flags: TypeFlags,
139
140    /// see `Ty::outer_exclusive_binder` for details
141    pub outer_exclusive_binder: ty::DebruijnIndex,
142
143    interner: std::marker::PhantomData<I>,
144}
145
146impl<I: Interner> FlagComputation<I> {
147    fn new() -> FlagComputation<I> {
148        FlagComputation {
149            flags: TypeFlags::empty(),
150            outer_exclusive_binder: ty::INNERMOST,
151            interner: std::marker::PhantomData,
152        }
153    }
154
155    #[allow(rustc::usage_of_ty_tykind)]
156    pub fn for_kind(kind: &ty::TyKind<I>) -> FlagComputation<I> {
157        let mut result = FlagComputation::new();
158        result.add_kind(kind);
159        result
160    }
161
162    pub fn for_predicate(binder: ty::Binder<I, ty::PredicateKind<I>>) -> FlagComputation<I> {
163        let mut result = FlagComputation::new();
164        result.add_predicate(binder);
165        result
166    }
167
168    pub fn for_const_kind(kind: &ty::ConstKind<I>) -> FlagComputation<I> {
169        let mut result = FlagComputation::new();
170        result.add_const_kind(kind);
171        result
172    }
173
174    pub fn for_clauses(clauses: &[I::Clause]) -> FlagComputation<I> {
175        let mut result = FlagComputation::new();
176        for c in clauses {
177            result.add_flags(c.as_predicate().flags());
178            result.add_exclusive_binder(c.as_predicate().outer_exclusive_binder());
179        }
180        result
181    }
182
183    fn add_flags(&mut self, flags: TypeFlags) {
184        self.flags = self.flags | flags;
185    }
186
187    /// indicates that `self` refers to something at binding level `binder`
188    fn add_bound_var(&mut self, binder: ty::DebruijnIndex) {
189        let exclusive_binder = binder.shifted_in(1);
190        self.add_exclusive_binder(exclusive_binder);
191    }
192
193    /// indicates that `self` refers to something *inside* binding
194    /// level `binder` -- not bound by `binder`, but bound by the next
195    /// binder internal to it
196    fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) {
197        self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder);
198    }
199
200    /// Adds the flags/depth from a set of types that appear within the current type, but within a
201    /// region binder.
202    fn bound_computation<T, F>(&mut self, value: ty::Binder<I, T>, f: F)
203    where
204        F: FnOnce(&mut Self, T),
205    {
206        let mut computation = FlagComputation::new();
207
208        if !value.bound_vars().is_empty() {
209            computation.add_flags(TypeFlags::HAS_BINDER_VARS);
210        }
211
212        f(&mut computation, value.skip_binder());
213
214        self.add_flags(computation.flags);
215
216        // The types that contributed to `computation` occurred within
217        // a region binder, so subtract one from the region depth
218        // within when adding the depth to `self`.
219        let outer_exclusive_binder = computation.outer_exclusive_binder;
220        if outer_exclusive_binder > ty::INNERMOST {
221            self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1));
222        } // otherwise, this binder captures nothing
223    }
224
225    #[allow(rustc::usage_of_ty_tykind)]
226    fn add_kind(&mut self, kind: &ty::TyKind<I>) {
227        match *kind {
228            ty::Bool
229            | ty::Char
230            | ty::Int(_)
231            | ty::Float(_)
232            | ty::Uint(_)
233            | ty::Never
234            | ty::Str
235            | ty::Foreign(..) => {}
236
237            ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
238
239            ty::Param(_) => {
240                self.add_flags(TypeFlags::HAS_TY_PARAM);
241            }
242
243            ty::Closure(_, args)
244            | ty::Coroutine(_, args)
245            | ty::CoroutineClosure(_, args)
246            | ty::CoroutineWitness(_, args) => {
247                self.add_args(args.as_slice());
248            }
249
250            ty::Bound(debruijn, _) => {
251                self.add_bound_var(debruijn);
252                self.add_flags(TypeFlags::HAS_TY_BOUND);
253            }
254
255            ty::Placeholder(..) => {
256                self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER);
257            }
258
259            ty::Infer(infer) => match infer {
260                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
261                    self.add_flags(TypeFlags::HAS_TY_FRESH)
262                }
263
264                ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => {
265                    self.add_flags(TypeFlags::HAS_TY_INFER)
266                }
267            },
268
269            ty::Adt(_, args) => {
270                self.add_args(args.as_slice());
271            }
272
273            ty::Alias(kind, data) => {
274                self.add_flags(match kind {
275                    ty::Projection => TypeFlags::HAS_TY_PROJECTION,
276                    ty::Free => TypeFlags::HAS_TY_FREE_ALIAS,
277                    ty::Opaque => TypeFlags::HAS_TY_OPAQUE,
278                    ty::Inherent => TypeFlags::HAS_TY_INHERENT,
279                });
280
281                self.add_alias_ty(data);
282            }
283
284            ty::Dynamic(obj, r, _) => {
285                for predicate in obj.iter() {
286                    self.bound_computation(predicate, |computation, predicate| match predicate {
287                        ty::ExistentialPredicate::Trait(tr) => {
288                            computation.add_args(tr.args.as_slice())
289                        }
290                        ty::ExistentialPredicate::Projection(p) => {
291                            computation.add_existential_projection(&p);
292                        }
293                        ty::ExistentialPredicate::AutoTrait(_) => {}
294                    });
295                }
296
297                self.add_region(r);
298            }
299
300            ty::Array(tt, len) => {
301                self.add_ty(tt);
302                self.add_const(len);
303            }
304
305            ty::Pat(ty, pat) => {
306                self.add_ty(ty);
307                self.add_ty_pat(pat);
308            }
309
310            ty::Slice(tt) => self.add_ty(tt),
311
312            ty::RawPtr(ty, _) => {
313                self.add_ty(ty);
314            }
315
316            ty::Ref(r, ty, _) => {
317                self.add_region(r);
318                self.add_ty(ty);
319            }
320
321            ty::Tuple(types) => {
322                self.add_tys(types);
323            }
324
325            ty::FnDef(_, args) => {
326                self.add_args(args.as_slice());
327            }
328
329            ty::FnPtr(sig_tys, _) => self.bound_computation(sig_tys, |computation, sig_tys| {
330                computation.add_tys(sig_tys.inputs_and_output);
331            }),
332
333            ty::UnsafeBinder(bound_ty) => {
334                self.bound_computation(bound_ty.into(), |computation, ty| {
335                    computation.add_ty(ty);
336                })
337            }
338        }
339    }
340
341    fn add_ty_pat(&mut self, pat: <I as Interner>::Pat) {
342        self.add_flags(pat.flags());
343    }
344
345    fn add_predicate(&mut self, binder: ty::Binder<I, ty::PredicateKind<I>>) {
346        self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom));
347    }
348
349    fn add_predicate_atom(&mut self, atom: ty::PredicateKind<I>) {
350        match atom {
351            ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => {
352                self.add_args(trait_pred.trait_ref.args.as_slice());
353            }
354            ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(ty::HostEffectPredicate {
355                trait_ref,
356                constness: _,
357            })) => {
358                self.add_args(trait_ref.args.as_slice());
359            }
360            ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(
361                a,
362                b,
363            ))) => {
364                self.add_region(a);
365                self.add_region(b);
366            }
367            ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
368                ty,
369                region,
370            ))) => {
371                self.add_ty(ty);
372                self.add_region(region);
373            }
374            ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
375                self.add_const(ct);
376                self.add_ty(ty);
377            }
378            ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => {
379                self.add_ty(a);
380                self.add_ty(b);
381            }
382            ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => {
383                self.add_ty(a);
384                self.add_ty(b);
385            }
386            ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate {
387                projection_term,
388                term,
389            })) => {
390                self.add_alias_term(projection_term);
391                self.add_term(term);
392            }
393            ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
394                self.add_term(term);
395            }
396            ty::PredicateKind::DynCompatible(_def_id) => {}
397            ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
398                self.add_const(uv);
399            }
400            ty::PredicateKind::ConstEquate(expected, found) => {
401                self.add_const(expected);
402                self.add_const(found);
403            }
404            ty::PredicateKind::Ambiguous => {}
405            ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term }) => {
406                self.add_alias_term(alias);
407                self.add_term(term);
408            }
409            ty::PredicateKind::AliasRelate(t1, t2, _) => {
410                self.add_term(t1);
411                self.add_term(t2);
412            }
413        }
414    }
415
416    fn add_ty(&mut self, ty: I::Ty) {
417        self.add_flags(ty.flags());
418        self.add_exclusive_binder(ty.outer_exclusive_binder());
419    }
420
421    fn add_tys(&mut self, tys: I::Tys) {
422        for ty in tys.iter() {
423            self.add_ty(ty);
424        }
425    }
426
427    fn add_region(&mut self, r: I::Region) {
428        self.add_flags(r.flags());
429        if let ty::ReBound(debruijn, _) = r.kind() {
430            self.add_bound_var(debruijn);
431        }
432    }
433
434    fn add_const(&mut self, c: I::Const) {
435        self.add_flags(c.flags());
436        self.add_exclusive_binder(c.outer_exclusive_binder());
437    }
438
439    fn add_const_kind(&mut self, c: &ty::ConstKind<I>) {
440        match *c {
441            ty::ConstKind::Unevaluated(uv) => {
442                self.add_args(uv.args.as_slice());
443                self.add_flags(TypeFlags::HAS_CT_PROJECTION);
444            }
445            ty::ConstKind::Infer(infer) => match infer {
446                ty::InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH),
447                ty::InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER),
448            },
449            ty::ConstKind::Bound(debruijn, _) => {
450                self.add_bound_var(debruijn);
451                self.add_flags(TypeFlags::HAS_CT_BOUND);
452            }
453            ty::ConstKind::Param(_) => {
454                self.add_flags(TypeFlags::HAS_CT_PARAM);
455            }
456            ty::ConstKind::Placeholder(_) => {
457                self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER);
458            }
459            ty::ConstKind::Value(cv) => self.add_ty(cv.ty()),
460            ty::ConstKind::Expr(e) => self.add_args(e.args().as_slice()),
461            ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
462        }
463    }
464
465    fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<I>) {
466        self.add_args(projection.args.as_slice());
467        match projection.term.kind() {
468            ty::TermKind::Ty(ty) => self.add_ty(ty),
469            ty::TermKind::Const(ct) => self.add_const(ct),
470        }
471    }
472
473    fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<I>) {
474        self.add_args(alias_ty.args.as_slice());
475    }
476
477    fn add_alias_term(&mut self, alias_term: ty::AliasTerm<I>) {
478        self.add_args(alias_term.args.as_slice());
479    }
480
481    fn add_args(&mut self, args: &[I::GenericArg]) {
482        for kind in args {
483            match kind.kind() {
484                ty::GenericArgKind::Type(ty) => self.add_ty(ty),
485                ty::GenericArgKind::Lifetime(lt) => self.add_region(lt),
486                ty::GenericArgKind::Const(ct) => self.add_const(ct),
487            }
488        }
489    }
490
491    fn add_term(&mut self, term: I::Term) {
492        match term.kind() {
493            ty::TermKind::Ty(ty) => self.add_ty(ty),
494            ty::TermKind::Const(ct) => self.add_const(ct),
495        }
496    }
497}
rustc_type_ir/flags.rs

rustc_type_ir/
flags.rs
