1 use crate::ty::subst::{GenericArg, GenericArgKind}; 2 use crate::ty::{self, InferConst, Ty, TypeFlags}; 3 use std::slice; 4 5 #[derive(Debug)] 6 pub struct FlagComputation { 7 pub flags: TypeFlags, 8 9 /// see `Ty::outer_exclusive_binder` for details 10 pub outer_exclusive_binder: ty::DebruijnIndex, 11 } 12 13 impl FlagComputation { new() -> FlagComputation14 fn new() -> FlagComputation { 15 FlagComputation { flags: TypeFlags::empty(), outer_exclusive_binder: ty::INNERMOST } 16 } 17 18 #[allow(rustc::usage_of_ty_tykind)] for_kind(kind: &ty::TyKind<'_>) -> FlagComputation19 pub fn for_kind(kind: &ty::TyKind<'_>) -> FlagComputation { 20 let mut result = FlagComputation::new(); 21 result.add_kind(kind); 22 result 23 } 24 for_predicate(binder: ty::Binder<'_, ty::PredicateKind<'_>>) -> FlagComputation25 pub fn for_predicate(binder: ty::Binder<'_, ty::PredicateKind<'_>>) -> FlagComputation { 26 let mut result = FlagComputation::new(); 27 result.add_predicate(binder); 28 result 29 } 30 for_const(c: ty::Const<'_>) -> TypeFlags31 pub fn for_const(c: ty::Const<'_>) -> TypeFlags { 32 let mut result = FlagComputation::new(); 33 result.add_const(c); 34 result.flags 35 } 36 add_flags(&mut self, flags: TypeFlags)37 fn add_flags(&mut self, flags: TypeFlags) { 38 self.flags = self.flags | flags; 39 } 40 41 /// indicates that `self` refers to something at binding level `binder` add_bound_var(&mut self, binder: ty::DebruijnIndex)42 fn add_bound_var(&mut self, binder: ty::DebruijnIndex) { 43 let exclusive_binder = binder.shifted_in(1); 44 self.add_exclusive_binder(exclusive_binder); 45 } 46 47 /// indicates that `self` refers to something *inside* binding 48 /// level `binder` -- not bound by `binder`, but bound by the next 49 /// binder internal to it add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex)50 fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) { 51 self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder); 52 } 53 54 /// Adds the flags/depth from a set of types that appear within the current type, but within a 55 /// region binder. bound_computation<T, F>(&mut self, value: ty::Binder<'_, T>, f: F) where F: FnOnce(&mut Self, T),56 fn bound_computation<T, F>(&mut self, value: ty::Binder<'_, T>, f: F) 57 where 58 F: FnOnce(&mut Self, T), 59 { 60 let mut computation = FlagComputation::new(); 61 62 for bv in value.bound_vars() { 63 match bv { 64 ty::BoundVariableKind::Ty(_) => { 65 computation.flags |= TypeFlags::HAS_TY_LATE_BOUND; 66 } 67 ty::BoundVariableKind::Region(_) => { 68 computation.flags |= TypeFlags::HAS_RE_LATE_BOUND; 69 } 70 ty::BoundVariableKind::Const => { 71 computation.flags |= TypeFlags::HAS_CT_LATE_BOUND; 72 } 73 } 74 } 75 76 f(&mut computation, value.skip_binder()); 77 78 self.add_flags(computation.flags); 79 80 // The types that contributed to `computation` occurred within 81 // a region binder, so subtract one from the region depth 82 // within when adding the depth to `self`. 83 let outer_exclusive_binder = computation.outer_exclusive_binder; 84 if outer_exclusive_binder > ty::INNERMOST { 85 self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1)); 86 } // otherwise, this binder captures nothing 87 } 88 89 #[allow(rustc::usage_of_ty_tykind)] add_kind(&mut self, kind: &ty::TyKind<'_>)90 fn add_kind(&mut self, kind: &ty::TyKind<'_>) { 91 match kind { 92 &ty::Bool 93 | &ty::Char 94 | &ty::Int(_) 95 | &ty::Float(_) 96 | &ty::Uint(_) 97 | &ty::Never 98 | &ty::Str 99 | &ty::Foreign(..) => {} 100 101 &ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR), 102 103 &ty::Param(_) => { 104 self.add_flags(TypeFlags::HAS_TY_PARAM); 105 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 106 } 107 108 ty::Generator(_, substs, _) => { 109 let substs = substs.as_generator(); 110 let should_remove_further_specializable = 111 !self.flags.contains(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 112 self.add_substs(substs.parent_substs()); 113 if should_remove_further_specializable { 114 self.flags -= TypeFlags::STILL_FURTHER_SPECIALIZABLE; 115 } 116 117 self.add_ty(substs.resume_ty()); 118 self.add_ty(substs.return_ty()); 119 self.add_ty(substs.witness()); 120 self.add_ty(substs.yield_ty()); 121 self.add_ty(substs.tupled_upvars_ty()); 122 } 123 124 &ty::GeneratorWitness(ts) => { 125 self.bound_computation(ts, |flags, ts| flags.add_tys(ts)); 126 } 127 128 ty::GeneratorWitnessMIR(_, substs) => { 129 let should_remove_further_specializable = 130 !self.flags.contains(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 131 self.add_substs(substs); 132 if should_remove_further_specializable { 133 self.flags -= TypeFlags::STILL_FURTHER_SPECIALIZABLE; 134 } 135 self.add_flags(TypeFlags::HAS_TY_GENERATOR); 136 } 137 138 &ty::Closure(_, substs) => { 139 let substs = substs.as_closure(); 140 let should_remove_further_specializable = 141 !self.flags.contains(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 142 self.add_substs(substs.parent_substs()); 143 if should_remove_further_specializable { 144 self.flags -= TypeFlags::STILL_FURTHER_SPECIALIZABLE; 145 } 146 147 self.add_ty(substs.sig_as_fn_ptr_ty()); 148 self.add_ty(substs.kind_ty()); 149 self.add_ty(substs.tupled_upvars_ty()); 150 } 151 152 &ty::Bound(debruijn, _) => { 153 self.add_bound_var(debruijn); 154 self.add_flags(TypeFlags::HAS_TY_LATE_BOUND); 155 } 156 157 &ty::Placeholder(..) => { 158 self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER); 159 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 160 } 161 162 &ty::Infer(infer) => { 163 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 164 match infer { 165 ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { 166 self.add_flags(TypeFlags::HAS_TY_FRESH) 167 } 168 169 ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => { 170 self.add_flags(TypeFlags::HAS_TY_INFER) 171 } 172 } 173 } 174 175 &ty::Adt(_, substs) => { 176 self.add_substs(substs); 177 } 178 179 &ty::Alias(kind, data) => { 180 self.add_flags(match kind { 181 ty::Weak | ty::Projection => TypeFlags::HAS_TY_PROJECTION, 182 ty::Inherent => TypeFlags::HAS_TY_INHERENT, 183 ty::Opaque => TypeFlags::HAS_TY_OPAQUE, 184 }); 185 186 self.add_alias_ty(data); 187 } 188 189 &ty::Dynamic(obj, r, _) => { 190 for predicate in obj.iter() { 191 self.bound_computation(predicate, |computation, predicate| match predicate { 192 ty::ExistentialPredicate::Trait(tr) => computation.add_substs(tr.substs), 193 ty::ExistentialPredicate::Projection(p) => { 194 computation.add_existential_projection(&p); 195 } 196 ty::ExistentialPredicate::AutoTrait(_) => {} 197 }); 198 } 199 200 self.add_region(r); 201 } 202 203 &ty::Array(tt, len) => { 204 self.add_ty(tt); 205 self.add_const(len); 206 } 207 208 &ty::Slice(tt) => self.add_ty(tt), 209 210 ty::RawPtr(m) => { 211 self.add_ty(m.ty); 212 } 213 214 &ty::Ref(r, ty, _) => { 215 self.add_region(r); 216 self.add_ty(ty); 217 } 218 219 &ty::Tuple(types) => { 220 self.add_tys(types); 221 } 222 223 &ty::FnDef(_, substs) => { 224 self.add_substs(substs); 225 } 226 227 &ty::FnPtr(fn_sig) => self.bound_computation(fn_sig, |computation, fn_sig| { 228 computation.add_tys(fn_sig.inputs()); 229 computation.add_ty(fn_sig.output()); 230 }), 231 } 232 } 233 add_predicate(&mut self, binder: ty::Binder<'_, ty::PredicateKind<'_>>)234 fn add_predicate(&mut self, binder: ty::Binder<'_, ty::PredicateKind<'_>>) { 235 self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom)); 236 } 237 add_predicate_atom(&mut self, atom: ty::PredicateKind<'_>)238 fn add_predicate_atom(&mut self, atom: ty::PredicateKind<'_>) { 239 match atom { 240 ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => { 241 self.add_substs(trait_pred.trait_ref.substs); 242 } 243 ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate( 244 a, 245 b, 246 ))) => { 247 self.add_region(a); 248 self.add_region(b); 249 } 250 ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate( 251 ty, 252 region, 253 ))) => { 254 self.add_ty(ty); 255 self.add_region(region); 256 } 257 ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => { 258 self.add_const(ct); 259 self.add_ty(ty); 260 } 261 ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => { 262 self.add_ty(a); 263 self.add_ty(b); 264 } 265 ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => { 266 self.add_ty(a); 267 self.add_ty(b); 268 } 269 ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate { 270 projection_ty, 271 term, 272 })) => { 273 self.add_alias_ty(projection_ty); 274 self.add_term(term); 275 } 276 ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => { 277 self.add_substs(slice::from_ref(&arg)); 278 } 279 ty::PredicateKind::ObjectSafe(_def_id) => {} 280 ty::PredicateKind::ClosureKind(_def_id, substs, _kind) => { 281 self.add_substs(substs); 282 } 283 ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => { 284 self.add_const(uv); 285 } 286 ty::PredicateKind::ConstEquate(expected, found) => { 287 self.add_const(expected); 288 self.add_const(found); 289 } 290 ty::PredicateKind::Ambiguous => {} 291 ty::PredicateKind::AliasRelate(t1, t2, _) => { 292 self.add_term(t1); 293 self.add_term(t2); 294 } 295 } 296 } 297 add_ty(&mut self, ty: Ty<'_>)298 fn add_ty(&mut self, ty: Ty<'_>) { 299 self.add_flags(ty.flags()); 300 self.add_exclusive_binder(ty.outer_exclusive_binder()); 301 } 302 add_tys(&mut self, tys: &[Ty<'_>])303 fn add_tys(&mut self, tys: &[Ty<'_>]) { 304 for &ty in tys { 305 self.add_ty(ty); 306 } 307 } 308 add_region(&mut self, r: ty::Region<'_>)309 fn add_region(&mut self, r: ty::Region<'_>) { 310 self.add_flags(r.type_flags()); 311 if let ty::ReLateBound(debruijn, _) = *r { 312 self.add_bound_var(debruijn); 313 } 314 } 315 add_const(&mut self, c: ty::Const<'_>)316 fn add_const(&mut self, c: ty::Const<'_>) { 317 self.add_ty(c.ty()); 318 match c.kind() { 319 ty::ConstKind::Unevaluated(uv) => { 320 self.add_substs(uv.substs); 321 self.add_flags(TypeFlags::HAS_CT_PROJECTION); 322 } 323 ty::ConstKind::Infer(infer) => { 324 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 325 match infer { 326 InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH), 327 InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER), 328 } 329 } 330 ty::ConstKind::Bound(debruijn, _) => { 331 self.add_bound_var(debruijn); 332 self.add_flags(TypeFlags::HAS_CT_LATE_BOUND); 333 } 334 ty::ConstKind::Param(_) => { 335 self.add_flags(TypeFlags::HAS_CT_PARAM); 336 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 337 } 338 ty::ConstKind::Placeholder(_) => { 339 self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER); 340 self.add_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE); 341 } 342 ty::ConstKind::Value(_) => {} 343 ty::ConstKind::Expr(e) => { 344 use ty::Expr; 345 match e { 346 Expr::Binop(_, l, r) => { 347 self.add_const(l); 348 self.add_const(r); 349 } 350 Expr::UnOp(_, v) => self.add_const(v), 351 Expr::FunctionCall(f, args) => { 352 self.add_const(f); 353 for arg in args { 354 self.add_const(arg); 355 } 356 } 357 Expr::Cast(_, c, t) => { 358 self.add_ty(t); 359 self.add_const(c); 360 } 361 } 362 } 363 ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR), 364 } 365 } 366 add_existential_projection(&mut self, projection: &ty::ExistentialProjection<'_>)367 fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<'_>) { 368 self.add_substs(projection.substs); 369 match projection.term.unpack() { 370 ty::TermKind::Ty(ty) => self.add_ty(ty), 371 ty::TermKind::Const(ct) => self.add_const(ct), 372 } 373 } 374 add_alias_ty(&mut self, alias_ty: ty::AliasTy<'_>)375 fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<'_>) { 376 self.add_substs(alias_ty.substs); 377 } 378 add_substs(&mut self, substs: &[GenericArg<'_>])379 fn add_substs(&mut self, substs: &[GenericArg<'_>]) { 380 for kind in substs { 381 match kind.unpack() { 382 GenericArgKind::Type(ty) => self.add_ty(ty), 383 GenericArgKind::Lifetime(lt) => self.add_region(lt), 384 GenericArgKind::Const(ct) => self.add_const(ct), 385 } 386 } 387 } 388 add_term(&mut self, term: ty::Term<'_>)389 fn add_term(&mut self, term: ty::Term<'_>) { 390 match term.unpack() { 391 ty::TermKind::Ty(ty) => self.add_ty(ty), 392 ty::TermKind::Const(ct) => self.add_const(ct), 393 } 394 } 395 } 396