| use rustc_data_structures::fx::FxIndexMap; |
| use rustc_hir::def::DefKind; |
| use rustc_hir::def_id::DefId; |
| use rustc_middle::ty::{self, Ty, TyCtxt}; |
| use rustc_middle::ty::{GenericArg, GenericArgKind}; |
| use rustc_span::Span; |
| |
| use super::explicit::ExplicitPredicatesMap; |
| use super::utils::*; |
| |
| /// Infer predicates for the items in the crate. |
| /// |
| /// `global_inferred_outlives`: this is initially the empty map that |
| /// was generated by walking the items in the crate. This will |
| /// now be filled with inferred predicates. |
| pub(super) fn infer_predicates( |
| tcx: TyCtxt<'_>, |
| ) -> FxIndexMap<DefId, ty::EarlyBinder<RequiredPredicates<'_>>> { |
| debug!("infer_predicates"); |
| |
| let mut explicit_map = ExplicitPredicatesMap::new(); |
| |
| let mut global_inferred_outlives = FxIndexMap::default(); |
| |
| // If new predicates were added then we need to re-calculate |
| // all crates since there could be new implied predicates. |
| 'outer: loop { |
| let mut predicates_added = false; |
| |
| // Visit all the crates and infer predicates |
| for id in tcx.hir().items() { |
| let item_did = id.owner_id; |
| |
| debug!("InferVisitor::visit_item(item={:?})", item_did); |
| |
| let mut item_required_predicates = RequiredPredicates::default(); |
| match tcx.def_kind(item_did) { |
| DefKind::Union | DefKind::Enum | DefKind::Struct => { |
| let adt_def = tcx.adt_def(item_did.to_def_id()); |
| |
| // Iterate over all fields in item_did |
| for field_def in adt_def.all_fields() { |
| // Calculating the predicate requirements necessary |
| // for item_did. |
| // |
| // For field of type &'a T (reference) or Adt |
| // (struct/enum/union) there will be outlive |
| // requirements for adt_def. |
| let field_ty = tcx.type_of(field_def.did).instantiate_identity(); |
| let field_span = tcx.def_span(field_def.did); |
| insert_required_predicates_to_be_wf( |
| tcx, |
| field_ty, |
| field_span, |
| &global_inferred_outlives, |
| &mut item_required_predicates, |
| &mut explicit_map, |
| ); |
| } |
| } |
| |
| DefKind::TyAlias if tcx.type_alias_is_lazy(item_did) => { |
| insert_required_predicates_to_be_wf( |
| tcx, |
| tcx.type_of(item_did).instantiate_identity(), |
| tcx.def_span(item_did), |
| &global_inferred_outlives, |
| &mut item_required_predicates, |
| &mut explicit_map, |
| ); |
| } |
| |
| _ => {} |
| }; |
| |
| // If new predicates were added (`local_predicate_map` has more |
| // predicates than the `global_inferred_outlives`), the new predicates |
| // might result in implied predicates for their parent types. |
| // Therefore mark `predicates_added` as true and which will ensure |
| // we walk the crates again and re-calculate predicates for all |
| // items. |
| let item_predicates_len: usize = global_inferred_outlives |
| .get(&item_did.to_def_id()) |
| .map_or(0, |p| p.as_ref().skip_binder().len()); |
| if item_required_predicates.len() > item_predicates_len { |
| predicates_added = true; |
| global_inferred_outlives |
| .insert(item_did.to_def_id(), ty::EarlyBinder::bind(item_required_predicates)); |
| } |
| } |
| |
| if !predicates_added { |
| break 'outer; |
| } |
| } |
| |
| global_inferred_outlives |
| } |
| |
| fn insert_required_predicates_to_be_wf<'tcx>( |
| tcx: TyCtxt<'tcx>, |
| ty: Ty<'tcx>, |
| span: Span, |
| global_inferred_outlives: &FxIndexMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>, |
| required_predicates: &mut RequiredPredicates<'tcx>, |
| explicit_map: &mut ExplicitPredicatesMap<'tcx>, |
| ) { |
| for arg in ty.walk() { |
| let leaf_ty = match arg.unpack() { |
| GenericArgKind::Type(ty) => ty, |
| |
| // No predicates from lifetimes or constants, except potentially |
| // constants' types, but `walk` will get to them as well. |
| GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue, |
| }; |
| |
| match *leaf_ty.kind() { |
| ty::Ref(region, rty, _) => { |
| // The type is `&'a T` which means that we will have |
| // a predicate requirement of `T: 'a` (`T` outlives `'a`). |
| // |
| // We also want to calculate potential predicates for the `T`. |
| debug!("Ref"); |
| insert_outlives_predicate(tcx, rty.into(), region, span, required_predicates); |
| } |
| |
| ty::Adt(def, args) => { |
| // For ADTs (structs/enums/unions), we check inferred and explicit predicates. |
| debug!("Adt"); |
| check_inferred_predicates( |
| tcx, |
| def.did(), |
| args, |
| global_inferred_outlives, |
| required_predicates, |
| ); |
| check_explicit_predicates( |
| tcx, |
| def.did(), |
| args, |
| required_predicates, |
| explicit_map, |
| None, |
| ); |
| } |
| |
| ty::Alias(ty::Weak, alias) => { |
| // This corresponds to a type like `Type<'a, T>`. |
| // We check inferred and explicit predicates. |
| debug!("Weak"); |
| check_inferred_predicates( |
| tcx, |
| alias.def_id, |
| alias.args, |
| global_inferred_outlives, |
| required_predicates, |
| ); |
| check_explicit_predicates( |
| tcx, |
| alias.def_id, |
| alias.args, |
| required_predicates, |
| explicit_map, |
| None, |
| ); |
| } |
| |
| ty::Dynamic(obj, ..) => { |
| // This corresponds to `dyn Trait<..>`. In this case, we should |
| // use the explicit predicates as well. |
| debug!("Dynamic"); |
| if let Some(ex_trait_ref) = obj.principal() { |
| // Here, we are passing the type `usize` as a |
| // placeholder value with the function |
| // `with_self_ty`, since there is no concrete type |
| // `Self` for a `dyn Trait` at this |
| // stage. Therefore when checking explicit |
| // predicates in `check_explicit_predicates` we |
| // need to ignore checking the explicit_map for |
| // Self type. |
| let args = ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().args; |
| check_explicit_predicates( |
| tcx, |
| ex_trait_ref.skip_binder().def_id, |
| args, |
| required_predicates, |
| explicit_map, |
| Some(tcx.types.self_param), |
| ); |
| } |
| } |
| |
| ty::Alias(ty::Projection, alias) => { |
| // This corresponds to a type like `<() as Trait<'a, T>>::Type`. |
| // We only use the explicit predicates of the trait but |
| // not the ones of the associated type itself. |
| debug!("Projection"); |
| check_explicit_predicates( |
| tcx, |
| tcx.parent(alias.def_id), |
| alias.args, |
| required_predicates, |
| explicit_map, |
| None, |
| ); |
| } |
| |
| // FIXME(inherent_associated_types): Use the explicit predicates from the parent impl. |
| ty::Alias(ty::Inherent, _) => {} |
| |
| _ => {} |
| } |
| } |
| } |
| |
| /// Check the explicit predicates declared on the type. |
| /// |
| /// ### Example |
| /// |
| /// ```ignore (illustrative) |
| /// struct Outer<'a, T> { |
| /// field: Inner<T>, |
| /// } |
| /// |
| /// struct Inner<U> where U: 'static, U: Outer { |
| /// // ... |
| /// } |
| /// ``` |
| /// Here, we should fetch the explicit predicates, which |
| /// will give us `U: 'static` and `U: Outer`. The latter we |
| /// can ignore, but we will want to process `U: 'static`, |
| /// applying the instantiation as above. |
| fn check_explicit_predicates<'tcx>( |
| tcx: TyCtxt<'tcx>, |
| def_id: DefId, |
| args: &[GenericArg<'tcx>], |
| required_predicates: &mut RequiredPredicates<'tcx>, |
| explicit_map: &mut ExplicitPredicatesMap<'tcx>, |
| ignored_self_ty: Option<Ty<'tcx>>, |
| ) { |
| debug!( |
| "check_explicit_predicates(def_id={:?}, \ |
| args={:?}, \ |
| explicit_map={:?}, \ |
| required_predicates={:?}, \ |
| ignored_self_ty={:?})", |
| def_id, args, explicit_map, required_predicates, ignored_self_ty, |
| ); |
| let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id); |
| |
| for (outlives_predicate, &span) in explicit_predicates.as_ref().skip_binder() { |
| debug!("outlives_predicate = {:?}", &outlives_predicate); |
| |
| // Careful: If we are inferring the effects of a `dyn Trait<..>` |
| // type, then when we look up the predicates for `Trait`, |
| // we may find some that reference `Self`. e.g., perhaps the |
| // definition of `Trait` was: |
| // |
| // ``` |
| // trait Trait<'a, T> where Self: 'a { .. } |
| // ``` |
| // |
| // we want to ignore such predicates here, because |
| // there is no type parameter for them to affect. Consider |
| // a struct containing `dyn Trait`: |
| // |
| // ``` |
| // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> } |
| // ``` |
| // |
| // The `where Self: 'a` predicate refers to the *existential, hidden type* |
| // that is represented by the `dyn Trait`, not to the `X` type parameter |
| // (or any other generic parameter) declared on `MyStruct`. |
| // |
| // Note that we do this check for self **before** applying `args`. In the |
| // case that `args` come from a `dyn Trait` type, our caller will have |
| // included `Self = usize` as the value for `Self`. If we were |
| // to apply the args, and not filter this predicate, we might then falsely |
| // conclude that e.g., `X: 'x` was a reasonable inferred requirement. |
| // |
| // Another similar case is where we have an inferred |
| // requirement like `<Self as Trait>::Foo: 'b`. We presently |
| // ignore such requirements as well (cc #54467)-- though |
| // conceivably it might be better if we could extract the `Foo |
| // = X` binding from the object type (there must be such a |
| // binding) and thus infer an outlives requirement that `X: |
| // 'b`. |
| if let Some(self_ty) = ignored_self_ty |
| && let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() |
| && ty.walk().any(|arg| arg == self_ty.into()) |
| { |
| debug!("skipping self ty = {:?}", &ty); |
| continue; |
| } |
| |
| let predicate = explicit_predicates.rebind(*outlives_predicate).instantiate(tcx, args); |
| debug!("predicate = {:?}", &predicate); |
| insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates); |
| } |
| } |
| |
| /// Check the inferred predicates declared on the type. |
| /// |
| /// ### Example |
| /// |
| /// ```ignore (illustrative) |
| /// struct Outer<'a, T> { |
| /// outer: Inner<'a, T>, |
| /// } |
| /// |
| /// struct Inner<'b, U> { |
| /// inner: &'b U, |
| /// } |
| /// ``` |
| /// |
| /// Here, when processing the type of field `outer`, we would request the |
| /// set of implicit predicates computed for `Inner` thus far. This will |
| /// initially come back empty, but in next round we will get `U: 'b`. |
| /// We then apply the instantiation `['b => 'a, U => T]` and thus get the |
| /// requirement that `T: 'a` holds for `Outer`. |
| fn check_inferred_predicates<'tcx>( |
| tcx: TyCtxt<'tcx>, |
| def_id: DefId, |
| args: ty::GenericArgsRef<'tcx>, |
| global_inferred_outlives: &FxIndexMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>, |
| required_predicates: &mut RequiredPredicates<'tcx>, |
| ) { |
| // Load the current set of inferred and explicit predicates from `global_inferred_outlives` |
| // and filter the ones that are `TypeOutlives`. |
| |
| let Some(predicates) = global_inferred_outlives.get(&def_id) else { |
| return; |
| }; |
| |
| for (&predicate, &span) in predicates.as_ref().skip_binder() { |
| // `predicate` is `U: 'b` in the example above. |
| // So apply the instantiation to get `T: 'a`. |
| let ty::OutlivesPredicate(arg, region) = |
| predicates.rebind(predicate).instantiate(tcx, args); |
| insert_outlives_predicate(tcx, arg, region, span, required_predicates); |
| } |
| } |