compiler/rustc_hir_analysis/src/variance/mod.rs

   1 //! Module for inferring the variance of type and lifetime parameters. See the [rustc dev guide]
   2 //! chapter for more info.
   3 //!
   4 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/variance.html
   5
   6 use rustc_arena::DroplessArena;
   7 use rustc_hir::def::DefKind;
   8 use rustc_hir::def_id::{DefId, LocalDefId};
   9 use rustc_middle::ty::query::Providers;
  10 use rustc_middle::ty::{self, CrateVariancesMap, SubstsRef, Ty, TyCtxt};
  11 use rustc_middle::ty::{DefIdTree, TypeSuperVisitable, TypeVisitable};
  12 use std::ops::ControlFlow;
  13
  14 /// Defines the `TermsContext` basically houses an arena where we can
  15 /// allocate terms.
  16 mod terms;
  17
  18 /// Code to gather up constraints.
  19 mod constraints;
  20
  21 /// Code to solve constraints and write out the results.
  22 mod solve;
  23
  24 /// Code to write unit tests of variance.
  25 pub mod test;
  26
  27 /// Code for transforming variances.
  28 mod xform;
  29
  30 pub fn provide(providers: &mut Providers) {
  31     *providers = Providers { variances_of, crate_variances, ..*providers };
  32 }
  33
  34 fn crate_variances(tcx: TyCtxt<'_>, (): ()) -> CrateVariancesMap<'_> {
  35     let arena = DroplessArena::default();
  36     let terms_cx = terms::determine_parameters_to_be_inferred(tcx, &arena);
  37     let constraints_cx = constraints::add_constraints_from_crate(terms_cx);
  38     solve::solve_constraints(constraints_cx)
  39 }
  40
  41 fn variances_of(tcx: TyCtxt<'_>, item_def_id: DefId) -> &[ty::Variance] {
  42     // Skip items with no generics - there's nothing to infer in them.
  43     if tcx.generics_of(item_def_id).count() == 0 {
  44         return &[];
  45     }
  46
  47     match tcx.def_kind(item_def_id) {
  48         DefKind::Fn
  49         | DefKind::AssocFn
  50         | DefKind::Enum
  51         | DefKind::Struct
  52         | DefKind::Union
  53         | DefKind::Variant
  54         | DefKind::Ctor(..) => {}
  55         DefKind::OpaqueTy | DefKind::ImplTraitPlaceholder => {
  56             return variance_of_opaque(tcx, item_def_id.expect_local());
  57         }
  58         _ => {
  59             // Variance not relevant.
  60             span_bug!(tcx.def_span(item_def_id), "asked to compute variance for wrong kind of item")
  61         }
  62     }
  63
  64     // Everything else must be inferred.
  65
  66     let crate_map = tcx.crate_variances(());
  67     crate_map.variances.get(&item_def_id).copied().unwrap_or(&[])
  68 }
  69
  70 #[instrument(level = "trace", skip(tcx), ret)]
  71 fn variance_of_opaque(tcx: TyCtxt<'_>, item_def_id: LocalDefId) -> &[ty::Variance] {
  72     let generics = tcx.generics_of(item_def_id);
  73
  74     // Opaque types may only use regions that are bound. So for
  75     // ```rust
  76     // type Foo<'a, 'b, 'c> = impl Trait<'a> + 'b;
  77     // ```
  78     // we may not use `'c` in the hidden type.
  79     struct OpaqueTypeLifetimeCollector<'tcx> {
  80         tcx: TyCtxt<'tcx>,
  81         root_def_id: DefId,
  82         variances: Vec<ty::Variance>,
  83     }
  84
  85     impl<'tcx> OpaqueTypeLifetimeCollector<'tcx> {
  86         #[instrument(level = "trace", skip(self), ret)]
  87         fn visit_opaque(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) -> ControlFlow<!> {
  88             if def_id != self.root_def_id && self.tcx.is_descendant_of(def_id, self.root_def_id) {
  89                 let child_variances = self.tcx.variances_of(def_id);
  90                 for (a, v) in substs.iter().zip(child_variances) {
  91                     if *v != ty::Bivariant {
  92                         a.visit_with(self)?;
  93                     }
  94                 }
  95                 ControlFlow::Continue(())
  96             } else {
  97                 substs.visit_with(self)
  98             }
  99         }
 100     }
 101
 102     impl<'tcx> ty::TypeVisitor<'tcx> for OpaqueTypeLifetimeCollector<'tcx> {
 103         #[instrument(level = "trace", skip(self), ret)]
 104         fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 105             if let ty::RegionKind::ReEarlyBound(ebr) = r.kind() {
 106                 self.variances[ebr.index as usize] = ty::Invariant;
 107             }
 108             r.super_visit_with(self)
 109         }
 110
 111         #[instrument(level = "trace", skip(self), ret)]
 112         fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 113             match t.kind() {
 114                 ty::Alias(_, ty::AliasTy { def_id, substs, .. })
 115                     if matches!(
 116                         self.tcx.def_kind(*def_id),
 117                         DefKind::OpaqueTy | DefKind::ImplTraitPlaceholder
 118                     ) =>
 119                 {
 120                     self.visit_opaque(*def_id, substs)
 121                 }
 122                 _ => t.super_visit_with(self),
 123             }
 124         }
 125     }
 126
 127     // By default, RPIT are invariant wrt type and const generics, but they are bivariant wrt
 128     // lifetime generics.
 129     let mut variances: Vec<_> = std::iter::repeat(ty::Invariant).take(generics.count()).collect();
 130
 131     // Mark all lifetimes from parent generics as unused (Bivariant).
 132     // This will be overridden later if required.
 133     {
 134         let mut generics = generics;
 135         while let Some(def_id) = generics.parent {
 136             generics = tcx.generics_of(def_id);
 137             for param in &generics.params {
 138                 match param.kind {
 139                     ty::GenericParamDefKind::Lifetime => {
 140                         variances[param.index as usize] = ty::Bivariant;
 141                     }
 142                     ty::GenericParamDefKind::Type { .. }
 143                     | ty::GenericParamDefKind::Const { .. } => {}
 144                 }
 145             }
 146         }
 147     }
 148
 149     let mut collector =
 150         OpaqueTypeLifetimeCollector { tcx, root_def_id: item_def_id.to_def_id(), variances };
 151     let id_substs = ty::InternalSubsts::identity_for_item(tcx, item_def_id.to_def_id());
 152     for pred in tcx.bound_explicit_item_bounds(item_def_id.to_def_id()).transpose_iter() {
 153         let pred = pred.map_bound(|(pred, _)| *pred).subst(tcx, id_substs);
 154         debug!(?pred);
 155
 156         // We only ignore opaque type substs if the opaque type is the outermost type.
 157         // The opaque type may be nested within itself via recursion in e.g.
 158         // type Foo<'a> = impl PartialEq<Foo<'a>>;
 159         // which thus mentions `'a` and should thus accept hidden types that borrow 'a
 160         // instead of requiring an additional `+ 'a`.
 161         match pred.kind().skip_binder() {
 162             ty::PredicateKind::Clause(ty::Clause::Trait(ty::TraitPredicate {
 163                 trait_ref: ty::TraitRef { def_id: _, substs, .. },
 164                 constness: _,
 165                 polarity: _,
 166             })) => {
 167                 for subst in &substs[1..] {
 168                     subst.visit_with(&mut collector);
 169                 }
 170             }
 171             ty::PredicateKind::Clause(ty::Clause::Projection(ty::ProjectionPredicate {
 172                 projection_ty: ty::AliasTy { substs, .. },
 173                 term,
 174             })) => {
 175                 for subst in &substs[1..] {
 176                     subst.visit_with(&mut collector);
 177                 }
 178                 term.visit_with(&mut collector);
 179             }
 180             ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate(
 181                 _,
 182                 region,
 183             ))) => {
 184                 region.visit_with(&mut collector);
 185             }
 186             _ => {
 187                 pred.visit_with(&mut collector);
 188             }
 189         }
 190     }
 191     tcx.arena.alloc_from_iter(collector.variances.into_iter())
 192 }