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        /// Does this type have any coroutines in it?
135        const HAS_TY_CORO                 = 1 << 24;
136
137        /// Does this have have a `Bound(BoundVarIndexKind::Canonical, _)`?
138        const HAS_CANONICAL_BOUND      = 1 << 25;
139    }
140}
141
142#[derive(Debug)]
143pub struct FlagComputation<I> {
144    pub flags: TypeFlags,
145
146    /// see `Ty::outer_exclusive_binder` for details
147    pub outer_exclusive_binder: ty::DebruijnIndex,
148
149    interner: std::marker::PhantomData<I>,
150}
151
152impl<I: Interner> FlagComputation<I> {
153    fn new() -> FlagComputation<I> {
154        FlagComputation {
155            flags: TypeFlags::empty(),
156            outer_exclusive_binder: ty::INNERMOST,
157            interner: std::marker::PhantomData,
158        }
159    }
160
161    #[allow(rustc::usage_of_ty_tykind)]
162    pub fn for_kind(kind: &ty::TyKind<I>) -> FlagComputation<I> {
163        let mut result = FlagComputation::new();
164        result.add_kind(kind);
165        result
166    }
167
168    pub fn for_predicate(binder: ty::Binder<I, ty::PredicateKind<I>>) -> FlagComputation<I> {
169        let mut result = FlagComputation::new();
170        result.add_predicate(binder);
171        result
172    }
173
174    pub fn for_const_kind(kind: &ty::ConstKind<I>) -> FlagComputation<I> {
175        let mut result = FlagComputation::new();
176        result.add_const_kind(kind);
177        result
178    }
179
180    pub fn for_clauses(clauses: &[I::Clause]) -> FlagComputation<I> {
181        let mut result = FlagComputation::new();
182        for c in clauses {
183            result.add_flags(c.as_predicate().flags());
184            result.add_exclusive_binder(c.as_predicate().outer_exclusive_binder());
185        }
186        result
187    }
188
189    fn add_flags(&mut self, flags: TypeFlags) {
190        self.flags = self.flags | flags;
191    }
192
193    /// indicates that `self` refers to something at binding level `binder`
194    fn add_bound_var(&mut self, binder: ty::DebruijnIndex) {
195        let exclusive_binder = binder.shifted_in(1);
196        self.add_exclusive_binder(exclusive_binder);
197    }
198
199    /// indicates that `self` refers to something *inside* binding
200    /// level `binder` -- not bound by `binder`, but bound by the next
201    /// binder internal to it
202    fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) {
203        self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder);
204    }
205
206    /// Adds the flags/depth from a set of types that appear within the current type, but within a
207    /// region binder.
208    fn bound_computation<T, F>(&mut self, value: ty::Binder<I, T>, f: F)
209    where
210        F: FnOnce(&mut Self, T),
211    {
212        let mut computation = FlagComputation::new();
213
214        if !value.bound_vars().is_empty() {
215            computation.add_flags(TypeFlags::HAS_BINDER_VARS);
216        }
217
218        f(&mut computation, value.skip_binder());
219
220        self.add_flags(computation.flags);
221
222        // The types that contributed to `computation` occurred within
223        // a region binder, so subtract one from the region depth
224        // within when adding the depth to `self`.
225        let outer_exclusive_binder = computation.outer_exclusive_binder;
226        if outer_exclusive_binder > ty::INNERMOST {
227            self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1));
228        } // otherwise, this binder captures nothing
229    }
230
231    #[allow(rustc::usage_of_ty_tykind)]
232    fn add_kind(&mut self, kind: &ty::TyKind<I>) {
233        match *kind {
234            ty::Bool
235            | ty::Char
236            | ty::Int(_)
237            | ty::Float(_)
238            | ty::Uint(_)
239            | ty::Never
240            | ty::Str
241            | ty::Foreign(..) => {}
242
243            ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
244
245            ty::Param(_) => {
246                self.add_flags(TypeFlags::HAS_TY_PARAM);
247            }
248
249            ty::Closure(_, args)
250            | ty::CoroutineClosure(_, args)
251            | ty::CoroutineWitness(_, args) => {
252                self.add_args(args.as_slice());
253            }
254
255            ty::Coroutine(_, args) => {
256                self.add_flags(TypeFlags::HAS_TY_CORO);
257                self.add_args(args.as_slice());
258            }
259
260            ty::Bound(ty::BoundVarIndexKind::Canonical, _) => {
261                self.add_flags(TypeFlags::HAS_TY_BOUND);
262                self.add_flags(TypeFlags::HAS_CANONICAL_BOUND);
263            }
264
265            ty::Bound(ty::BoundVarIndexKind::Bound(debruijn), _) => {
266                self.add_bound_var(debruijn);
267                self.add_flags(TypeFlags::HAS_TY_BOUND);
268            }
269
270            ty::Placeholder(..) => {
271                self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER);
272            }
273
274            ty::Infer(infer) => match infer {
275                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
276                    self.add_flags(TypeFlags::HAS_TY_FRESH)
277                }
278
279                ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => {
280                    self.add_flags(TypeFlags::HAS_TY_INFER)
281                }
282            },
283
284            ty::Adt(_, args) => {
285                self.add_args(args.as_slice());
286            }
287
288            ty::Alias(kind, data) => {
289                self.add_flags(match kind {
290                    ty::Projection => TypeFlags::HAS_TY_PROJECTION,
291                    ty::Free => TypeFlags::HAS_TY_FREE_ALIAS,
292                    ty::Opaque => TypeFlags::HAS_TY_OPAQUE,
293                    ty::Inherent => TypeFlags::HAS_TY_INHERENT,
294                });
295
296                self.add_alias_ty(data);
297            }
298
299            ty::Dynamic(obj, r) => {
300                for predicate in obj.iter() {
301                    self.bound_computation(predicate, |computation, predicate| match predicate {
302                        ty::ExistentialPredicate::Trait(tr) => {
303                            computation.add_args(tr.args.as_slice())
304                        }
305                        ty::ExistentialPredicate::Projection(p) => {
306                            computation.add_existential_projection(&p);
307                        }
308                        ty::ExistentialPredicate::AutoTrait(_) => {}
309                    });
310                }
311
312                self.add_region(r);
313            }
314
315            ty::Array(tt, len) => {
316                self.add_ty(tt);
317                self.add_const(len);
318            }
319
320            ty::Pat(ty, pat) => {
321                self.add_ty(ty);
322                self.add_ty_pat(pat);
323            }
324
325            ty::Slice(tt) => self.add_ty(tt),
326
327            ty::RawPtr(ty, _) => {
328                self.add_ty(ty);
329            }
330
331            ty::Ref(r, ty, _) => {
332                self.add_region(r);
333                self.add_ty(ty);
334            }
335
336            ty::Tuple(types) => {
337                self.add_tys(types);
338            }
339
340            ty::FnDef(_, args) => {
341                self.add_args(args.as_slice());
342            }
343
344            ty::FnPtr(sig_tys, _) => self.bound_computation(sig_tys, |computation, sig_tys| {
345                computation.add_tys(sig_tys.inputs_and_output);
346            }),
347
348            ty::UnsafeBinder(bound_ty) => {
349                self.bound_computation(bound_ty.into(), |computation, ty| {
350                    computation.add_ty(ty);
351                })
352            }
353        }
354    }
355
356    fn add_ty_pat(&mut self, pat: <I as Interner>::Pat) {
357        self.add_flags(pat.flags());
358        self.add_exclusive_binder(pat.outer_exclusive_binder());
359    }
360
361    fn add_predicate(&mut self, binder: ty::Binder<I, ty::PredicateKind<I>>) {
362        self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom));
363    }
364
365    fn add_predicate_atom(&mut self, atom: ty::PredicateKind<I>) {
366        match atom {
367            ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => {
368                self.add_args(trait_pred.trait_ref.args.as_slice());
369            }
370            ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(ty::HostEffectPredicate {
371                trait_ref,
372                constness: _,
373            })) => {
374                self.add_args(trait_ref.args.as_slice());
375            }
376            ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(
377                a,
378                b,
379            ))) => {
380                self.add_region(a);
381                self.add_region(b);
382            }
383            ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
384                ty,
385                region,
386            ))) => {
387                self.add_ty(ty);
388                self.add_region(region);
389            }
390            ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
391                self.add_const(ct);
392                self.add_ty(ty);
393            }
394            ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => {
395                self.add_ty(a);
396                self.add_ty(b);
397            }
398            ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => {
399                self.add_ty(a);
400                self.add_ty(b);
401            }
402            ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate {
403                projection_term,
404                term,
405            })) => {
406                self.add_alias_term(projection_term);
407                self.add_term(term);
408            }
409            ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
410                self.add_term(term);
411            }
412            ty::PredicateKind::DynCompatible(_def_id) => {}
413            ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
414                self.add_const(uv);
415            }
416            ty::PredicateKind::ConstEquate(expected, found) => {
417                self.add_const(expected);
418                self.add_const(found);
419            }
420            ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term }) => {
421                self.add_alias_term(alias);
422                self.add_term(term);
423            }
424            ty::PredicateKind::AliasRelate(t1, t2, _) => {
425                self.add_term(t1);
426                self.add_term(t2);
427            }
428            ty::PredicateKind::Clause(ty::ClauseKind::UnstableFeature(_sym)) => {}
429            ty::PredicateKind::Ambiguous => {}
430        }
431    }
432
433    fn add_ty(&mut self, ty: I::Ty) {
434        self.add_flags(ty.flags());
435        self.add_exclusive_binder(ty.outer_exclusive_binder());
436    }
437
438    fn add_tys(&mut self, tys: I::Tys) {
439        for ty in tys.iter() {
440            self.add_ty(ty);
441        }
442    }
443
444    fn add_region(&mut self, r: I::Region) {
445        self.add_flags(r.flags());
446        if let ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), _) = r.kind() {
447            self.add_bound_var(debruijn);
448        }
449    }
450
451    fn add_const(&mut self, c: I::Const) {
452        self.add_flags(c.flags());
453        self.add_exclusive_binder(c.outer_exclusive_binder());
454    }
455
456    fn add_const_kind(&mut self, c: &ty::ConstKind<I>) {
457        match *c {
458            ty::ConstKind::Unevaluated(uv) => {
459                self.add_args(uv.args.as_slice());
460                self.add_flags(TypeFlags::HAS_CT_PROJECTION);
461            }
462            ty::ConstKind::Infer(infer) => match infer {
463                ty::InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH),
464                ty::InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER),
465            },
466            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(debruijn), _) => {
467                self.add_bound_var(debruijn);
468                self.add_flags(TypeFlags::HAS_CT_BOUND);
469            }
470            ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, _) => {
471                self.add_flags(TypeFlags::HAS_CT_BOUND);
472                self.add_flags(TypeFlags::HAS_CANONICAL_BOUND);
473            }
474            ty::ConstKind::Param(_) => {
475                self.add_flags(TypeFlags::HAS_CT_PARAM);
476            }
477            ty::ConstKind::Placeholder(_) => {
478                self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER);
479            }
480            ty::ConstKind::Value(cv) => self.add_ty(cv.ty()),
481            ty::ConstKind::Expr(e) => self.add_args(e.args().as_slice()),
482            ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR),
483        }
484    }
485
486    fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<I>) {
487        self.add_args(projection.args.as_slice());
488        match projection.term.kind() {
489            ty::TermKind::Ty(ty) => self.add_ty(ty),
490            ty::TermKind::Const(ct) => self.add_const(ct),
491        }
492    }
493
494    fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<I>) {
495        self.add_args(alias_ty.args.as_slice());
496    }
497
498    fn add_alias_term(&mut self, alias_term: ty::AliasTerm<I>) {
499        self.add_args(alias_term.args.as_slice());
500    }
501
502    fn add_args(&mut self, args: &[I::GenericArg]) {
503        for arg in args {
504            match arg.kind() {
505                ty::GenericArgKind::Type(ty) => self.add_ty(ty),
506                ty::GenericArgKind::Lifetime(lt) => self.add_region(lt),
507                ty::GenericArgKind::Const(ct) => self.add_const(ct),
508            }
509        }
510    }
511
512    fn add_term(&mut self, term: I::Term) {
513        match term.kind() {
514            ty::TermKind::Ty(ty) => self.add_ty(ty),
515            ty::TermKind::Const(ct) => self.add_const(ct),
516        }
517    }
518}
rustc_type_ir/flags.rs

rustc_type_ir/
flags.rs
