compiler/rustc_borrowck/src/region_infer/opaque_types.rs

   1 use rustc_data_structures::vec_map::VecMap;
   2 use rustc_hir::def_id::DefId;
   3 use rustc_hir::OpaqueTyOrigin;
   4 use rustc_infer::infer::InferCtxt;
   5 use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey, TyCtxt, TypeFoldable};
   6 use rustc_trait_selection::opaque_types::InferCtxtExt;
   7
   8 use super::RegionInferenceContext;
   9
  10 impl<'tcx> RegionInferenceContext<'tcx> {
  11     /// Resolve any opaque types that were encountered while borrow checking
  12     /// this item. This is then used to get the type in the `type_of` query.
  13     ///
  14     /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`.
  15     /// This is lowered to give HIR something like
  16     ///
  17     /// type f<'a>::_Return<'_a> = impl Sized + '_a;
  18     /// fn f<'a>(x: &'a i32) -> f<'static>::_Return<'a> { x }
  19     ///
  20     /// When checking the return type record the type from the return and the
  21     /// type used in the return value. In this case they might be `_Return<'1>`
  22     /// and `&'2 i32` respectively.
  23     ///
  24     /// Once we to this method, we have completed region inference and want to
  25     /// call `infer_opaque_definition_from_instantiation` to get the inferred
  26     /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation`
  27     /// compares lifetimes directly, so we need to map the inference variables
  28     /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`.
  29     ///
  30     /// First we map all the lifetimes in the concrete type to an equal
  31     /// universal region that occurs in the concrete type's substs, in this case
  32     /// this would result in `&'1 i32`. We only consider regions in the substs
  33     /// in case there is an equal region that does not. For example, this should
  34     /// be allowed:
  35     /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }`
  36     ///
  37     /// Then we map the regions in both the type and the subst to their
  38     /// `external_name` giving `concrete_type = &'a i32`,
  39     /// `substs = ['static, 'a]`. This will then allow
  40     /// `infer_opaque_definition_from_instantiation` to determine that
  41     /// `_Return<'_a> = &'_a i32`.
  42     ///
  43     /// There's a slight complication around closures. Given
  44     /// `fn f<'a: 'a>() { || {} }` the closure's type is something like
  45     /// `f::<'a>::{{closure}}`. The region parameter from f is essentially
  46     /// ignored by type checking so ends up being inferred to an empty region.
  47     /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`,
  48     /// which has no `external_name` in which case we use `'empty` as the
  49     /// region to pass to `infer_opaque_definition_from_instantiation`.
  50     #[instrument(level = "debug", skip(self, infcx))]
  51     pub(crate) fn infer_opaque_types(
  52         &self,
  53         infcx: &InferCtxt<'_, 'tcx>,
  54         opaque_ty_decls: VecMap<OpaqueTypeKey<'tcx>, (OpaqueHiddenType<'tcx>, OpaqueTyOrigin)>,
  55     ) -> VecMap<DefId, OpaqueHiddenType<'tcx>> {
  56         let mut result: VecMap<DefId, OpaqueHiddenType<'tcx>> = VecMap::new();
  57         for (opaque_type_key, (concrete_type, origin)) in opaque_ty_decls {
  58             let substs = opaque_type_key.substs;
  59             debug!(?concrete_type, ?substs);
  60
  61             let mut subst_regions = vec![self.universal_regions.fr_static];
  62             let universal_substs = infcx.tcx.fold_regions(substs, &mut false, |region, _| {
  63                 if let ty::RePlaceholder(..) = region.kind() {
  64                     // Higher kinded regions don't need remapping, they don't refer to anything outside of this the substs.
  65                     return region;
  66                 }
  67                 let vid = self.to_region_vid(region);
  68                 trace!(?vid);
  69                 let scc = self.constraint_sccs.scc(vid);
  70                 trace!(?scc);
  71                 match self.scc_values.universal_regions_outlived_by(scc).find_map(|lb| {
  72                     self.eval_equal(vid, lb).then_some(self.definitions[lb].external_name?)
  73                 }) {
  74                     Some(region) => {
  75                         let vid = self.universal_regions.to_region_vid(region);
  76                         subst_regions.push(vid);
  77                         region
  78                     }
  79                     None => {
  80                         subst_regions.push(vid);
  81                         infcx.tcx.sess.delay_span_bug(
  82                             concrete_type.span,
  83                             "opaque type with non-universal region substs",
  84                         );
  85                         infcx.tcx.lifetimes.re_static
  86                     }
  87                 }
  88             });
  89
  90             subst_regions.sort();
  91             subst_regions.dedup();
  92
  93             let universal_concrete_type =
  94                 infcx.tcx.fold_regions(concrete_type, &mut false, |region, _| match *region {
  95                     ty::ReVar(vid) => subst_regions
  96                         .iter()
  97                         .find(|ur_vid| self.eval_equal(vid, **ur_vid))
  98                         .and_then(|ur_vid| self.definitions[*ur_vid].external_name)
  99                         .unwrap_or(infcx.tcx.lifetimes.re_root_empty),
 100                     _ => region,
 101                 });
 102
 103             debug!(?universal_concrete_type, ?universal_substs);
 104
 105             let opaque_type_key =
 106                 OpaqueTypeKey { def_id: opaque_type_key.def_id, substs: universal_substs };
 107             let ty = infcx.infer_opaque_definition_from_instantiation(
 108                 opaque_type_key,
 109                 universal_concrete_type,
 110                 origin,
 111             );
 112             // Sometimes two opaque types are the same only after we remap the generic parameters
 113             // back to the opaque type definition. E.g. we may have `OpaqueType<X, Y>` mapped to `(X, Y)`
 114             // and `OpaqueType<Y, X>` mapped to `(Y, X)`, and those are the same, but we only know that
 115             // once we convert the generic parameters to those of the opaque type.
 116             if let Some(prev) = result.get_mut(&opaque_type_key.def_id) {
 117                 if prev.ty != ty {
 118                     if !ty.references_error() {
 119                         prev.report_mismatch(
 120                             &OpaqueHiddenType { ty, span: concrete_type.span },
 121                             infcx.tcx,
 122                         );
 123                     }
 124                     prev.ty = infcx.tcx.ty_error();
 125                 }
 126                 // Pick a better span if there is one.
 127                 // FIXME(oli-obk): collect multiple spans for better diagnostics down the road.
 128                 prev.span = prev.span.substitute_dummy(concrete_type.span);
 129             } else {
 130                 result.insert(
 131                     opaque_type_key.def_id,
 132                     OpaqueHiddenType { ty, span: concrete_type.span },
 133                 );
 134             }
 135         }
 136         result
 137     }
 138
 139     /// Map the regions in the type to named regions. This is similar to what
 140     /// `infer_opaque_types` does, but can infer any universal region, not only
 141     /// ones from the substs for the opaque type. It also doesn't double check
 142     /// that the regions produced are in fact equal to the named region they are
 143     /// replaced with. This is fine because this function is only to improve the
 144     /// region names in error messages.
 145     pub(crate) fn name_regions<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T
 146     where
 147         T: TypeFoldable<'tcx>,
 148     {
 149         tcx.fold_regions(ty, &mut false, |region, _| match *region {
 150             ty::ReVar(vid) => {
 151                 // Find something that we can name
 152                 let upper_bound = self.approx_universal_upper_bound(vid);
 153                 let upper_bound = &self.definitions[upper_bound];
 154                 match upper_bound.external_name {
 155                     Some(reg) => reg,
 156                     None => {
 157                         // Nothing exact found, so we pick the first one that we find.
 158                         let scc = self.constraint_sccs.scc(vid);
 159                         for vid in self.rev_scc_graph.as_ref().unwrap().upper_bounds(scc) {
 160                             match self.definitions[vid].external_name {
 161                                 None => {}
 162                                 Some(region) if region.is_static() => {}
 163                                 Some(region) => return region,
 164                             }
 165                         }
 166                         region
 167                     }
 168                 }
 169             }
 170             _ => region,
 171         })
 172     }
 173 }