compiler/rustc_borrowck/src/region_infer/opaque_types.rs

   1 use rustc_data_structures::fx::{FxHashMap, FxIndexSet};
   2 use rustc_data_structures::vec_map::VecMap;
   3 use rustc_hir::def_id::LocalDefId;
   4 use rustc_hir::OpaqueTyOrigin;
   5 use rustc_infer::infer::TyCtxtInferExt as _;
   6 use rustc_infer::infer::{DefiningAnchor, InferCtxt};
   7 use rustc_infer::traits::{Obligation, ObligationCause};
   8 use rustc_middle::ty::subst::{GenericArgKind, InternalSubsts};
   9 use rustc_middle::ty::visit::TypeVisitable;
  10 use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable};
  11 use rustc_span::Span;
  12 use rustc_trait_selection::traits::error_reporting::TypeErrCtxtExt as _;
  13 use rustc_trait_selection::traits::ObligationCtxt;
  14
  15 use super::RegionInferenceContext;
  16
  17 impl<'tcx> RegionInferenceContext<'tcx> {
  18     /// Resolve any opaque types that were encountered while borrow checking
  19     /// this item. This is then used to get the type in the `type_of` query.
  20     ///
  21     /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`.
  22     /// This is lowered to give HIR something like
  23     ///
  24     /// type f<'a>::_Return<'_a> = impl Sized + '_a;
  25     /// fn f<'a>(x: &'a i32) -> f<'static>::_Return<'a> { x }
  26     ///
  27     /// When checking the return type record the type from the return and the
  28     /// type used in the return value. In this case they might be `_Return<'1>`
  29     /// and `&'2 i32` respectively.
  30     ///
  31     /// Once we to this method, we have completed region inference and want to
  32     /// call `infer_opaque_definition_from_instantiation` to get the inferred
  33     /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation`
  34     /// compares lifetimes directly, so we need to map the inference variables
  35     /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`.
  36     ///
  37     /// First we map all the lifetimes in the concrete type to an equal
  38     /// universal region that occurs in the concrete type's substs, in this case
  39     /// this would result in `&'1 i32`. We only consider regions in the substs
  40     /// in case there is an equal region that does not. For example, this should
  41     /// be allowed:
  42     /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }`
  43     ///
  44     /// Then we map the regions in both the type and the subst to their
  45     /// `external_name` giving `concrete_type = &'a i32`,
  46     /// `substs = ['static, 'a]`. This will then allow
  47     /// `infer_opaque_definition_from_instantiation` to determine that
  48     /// `_Return<'_a> = &'_a i32`.
  49     ///
  50     /// There's a slight complication around closures. Given
  51     /// `fn f<'a: 'a>() { || {} }` the closure's type is something like
  52     /// `f::<'a>::{{closure}}`. The region parameter from f is essentially
  53     /// ignored by type checking so ends up being inferred to an empty region.
  54     /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`,
  55     /// which has no `external_name` in which case we use `'empty` as the
  56     /// region to pass to `infer_opaque_definition_from_instantiation`.
  57     #[instrument(level = "debug", skip(self, infcx), ret)]
  58     pub(crate) fn infer_opaque_types(
  59         &self,
  60         infcx: &InferCtxt<'tcx>,
  61         opaque_ty_decls: VecMap<OpaqueTypeKey<'tcx>, (OpaqueHiddenType<'tcx>, OpaqueTyOrigin)>,
  62     ) -> VecMap<LocalDefId, OpaqueHiddenType<'tcx>> {
  63         let mut result: VecMap<LocalDefId, OpaqueHiddenType<'tcx>> = VecMap::new();
  64
  65         let member_constraints: FxHashMap<_, _> = self
  66             .member_constraints
  67             .all_indices()
  68             .map(|ci| (self.member_constraints[ci].key, ci))
  69             .collect();
  70         debug!(?member_constraints);
  71
  72         for (opaque_type_key, (concrete_type, origin)) in opaque_ty_decls {
  73             let substs = opaque_type_key.substs;
  74             debug!(?concrete_type, ?substs);
  75
  76             let mut subst_regions = vec![self.universal_regions.fr_static];
  77
  78             let to_universal_region = |vid, subst_regions: &mut Vec<_>| {
  79                 trace!(?vid);
  80                 let scc = self.constraint_sccs.scc(vid);
  81                 trace!(?scc);
  82                 match self.scc_values.universal_regions_outlived_by(scc).find_map(|lb| {
  83                     self.eval_equal(vid, lb).then_some(self.definitions[lb].external_name?)
  84                 }) {
  85                     Some(region) => {
  86                         let vid = self.universal_regions.to_region_vid(region);
  87                         subst_regions.push(vid);
  88                         region
  89                     }
  90                     None => {
  91                         subst_regions.push(vid);
  92                         infcx.tcx.sess.delay_span_bug(
  93                             concrete_type.span,
  94                             "opaque type with non-universal region substs",
  95                         );
  96                         infcx.tcx.lifetimes.re_static
  97                     }
  98                 }
  99             };
 100
 101             // Start by inserting universal regions from the member_constraint choice regions.
 102             // This will ensure they get precedence when folding the regions in the concrete type.
 103             if let Some(&ci) = member_constraints.get(&opaque_type_key) {
 104                 for &vid in self.member_constraints.choice_regions(ci) {
 105                     to_universal_region(vid, &mut subst_regions);
 106                 }
 107             }
 108             debug!(?subst_regions);
 109
 110             // Next, insert universal regions from substs, so we can translate regions that appear
 111             // in them but are not subject to member constraints, for instance closure substs.
 112             let universal_substs = infcx.tcx.fold_regions(substs, |region, _| {
 113                 if let ty::RePlaceholder(..) = region.kind() {
 114                     // Higher kinded regions don't need remapping, they don't refer to anything outside of this the substs.
 115                     return region;
 116                 }
 117                 let vid = self.to_region_vid(region);
 118                 to_universal_region(vid, &mut subst_regions)
 119             });
 120             debug!(?universal_substs);
 121             debug!(?subst_regions);
 122
 123             // Deduplicate the set of regions while keeping the chosen order.
 124             let subst_regions = subst_regions.into_iter().collect::<FxIndexSet<_>>();
 125             debug!(?subst_regions);
 126
 127             let universal_concrete_type =
 128                 infcx.tcx.fold_regions(concrete_type, |region, _| match *region {
 129                     ty::ReVar(vid) => subst_regions
 130                         .iter()
 131                         .find(|ur_vid| self.eval_equal(vid, **ur_vid))
 132                         .and_then(|ur_vid| self.definitions[*ur_vid].external_name)
 133                         .unwrap_or(infcx.tcx.lifetimes.re_erased),
 134                     _ => region,
 135                 });
 136             debug!(?universal_concrete_type);
 137
 138             let opaque_type_key =
 139                 OpaqueTypeKey { def_id: opaque_type_key.def_id, substs: universal_substs };
 140             let ty = infcx.infer_opaque_definition_from_instantiation(
 141                 opaque_type_key,
 142                 universal_concrete_type,
 143                 origin,
 144             );
 145             // Sometimes two opaque types are the same only after we remap the generic parameters
 146             // back to the opaque type definition. E.g. we may have `OpaqueType<X, Y>` mapped to `(X, Y)`
 147             // and `OpaqueType<Y, X>` mapped to `(Y, X)`, and those are the same, but we only know that
 148             // once we convert the generic parameters to those of the opaque type.
 149             if let Some(prev) = result.get_mut(&opaque_type_key.def_id) {
 150                 if prev.ty != ty {
 151                     if !ty.references_error() {
 152                         prev.report_mismatch(
 153                             &OpaqueHiddenType { ty, span: concrete_type.span },
 154                             infcx.tcx,
 155                         );
 156                     }
 157                     prev.ty = infcx.tcx.ty_error();
 158                 }
 159                 // Pick a better span if there is one.
 160                 // FIXME(oli-obk): collect multiple spans for better diagnostics down the road.
 161                 prev.span = prev.span.substitute_dummy(concrete_type.span);
 162             } else {
 163                 result.insert(
 164                     opaque_type_key.def_id,
 165                     OpaqueHiddenType { ty, span: concrete_type.span },
 166                 );
 167             }
 168         }
 169         result
 170     }
 171
 172     /// Map the regions in the type to named regions. This is similar to what
 173     /// `infer_opaque_types` does, but can infer any universal region, not only
 174     /// ones from the substs for the opaque type. It also doesn't double check
 175     /// that the regions produced are in fact equal to the named region they are
 176     /// replaced with. This is fine because this function is only to improve the
 177     /// region names in error messages.
 178     pub(crate) fn name_regions<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T
 179     where
 180         T: TypeFoldable<'tcx>,
 181     {
 182         tcx.fold_regions(ty, |region, _| match *region {
 183             ty::ReVar(vid) => {
 184                 // Find something that we can name
 185                 let upper_bound = self.approx_universal_upper_bound(vid);
 186                 let upper_bound = &self.definitions[upper_bound];
 187                 match upper_bound.external_name {
 188                     Some(reg) => reg,
 189                     None => {
 190                         // Nothing exact found, so we pick the first one that we find.
 191                         let scc = self.constraint_sccs.scc(vid);
 192                         for vid in self.rev_scc_graph.as_ref().unwrap().upper_bounds(scc) {
 193                             match self.definitions[vid].external_name {
 194                                 None => {}
 195                                 Some(region) if region.is_static() => {}
 196                                 Some(region) => return region,
 197                             }
 198                         }
 199                         region
 200                     }
 201                 }
 202             }
 203             _ => region,
 204         })
 205     }
 206 }
 207
 208 pub trait InferCtxtExt<'tcx> {
 209     fn infer_opaque_definition_from_instantiation(
 210         &self,
 211         opaque_type_key: OpaqueTypeKey<'tcx>,
 212         instantiated_ty: OpaqueHiddenType<'tcx>,
 213         origin: OpaqueTyOrigin,
 214     ) -> Ty<'tcx>;
 215 }
 216
 217 impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> {
 218     /// Given the fully resolved, instantiated type for an opaque
 219     /// type, i.e., the value of an inference variable like C1 or C2
 220     /// (*), computes the "definition type" for an opaque type
 221     /// definition -- that is, the inferred value of `Foo1<'x>` or
 222     /// `Foo2<'x>` that we would conceptually use in its definition:
 223     /// ```ignore (illustrative)
 224     /// type Foo1<'x> = impl Bar<'x> = AAA;  // <-- this type AAA
 225     /// type Foo2<'x> = impl Bar<'x> = BBB;  // <-- or this type BBB
 226     /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. }
 227     /// ```
 228     /// Note that these values are defined in terms of a distinct set of
 229     /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main
 230     /// purpose of this function is to do that translation.
 231     ///
 232     /// (*) C1 and C2 were introduced in the comments on
 233     /// `register_member_constraints`. Read that comment for more context.
 234     ///
 235     /// # Parameters
 236     ///
 237     /// - `def_id`, the `impl Trait` type
 238     /// - `substs`, the substs  used to instantiate this opaque type
 239     /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of
 240     ///   `opaque_defn.concrete_ty`
 241     #[instrument(level = "debug", skip(self))]
 242     fn infer_opaque_definition_from_instantiation(
 243         &self,
 244         opaque_type_key: OpaqueTypeKey<'tcx>,
 245         instantiated_ty: OpaqueHiddenType<'tcx>,
 246         origin: OpaqueTyOrigin,
 247     ) -> Ty<'tcx> {
 248         if let Some(e) = self.tainted_by_errors() {
 249             return self.tcx.ty_error_with_guaranteed(e);
 250         }
 251
 252         let definition_ty = instantiated_ty
 253             .remap_generic_params_to_declaration_params(opaque_type_key, self.tcx, false, origin)
 254             .ty;
 255
 256         if !check_opaque_type_parameter_valid(
 257             self.tcx,
 258             opaque_type_key,
 259             origin,
 260             instantiated_ty.span,
 261         ) {
 262             return self.tcx.ty_error();
 263         }
 264
 265         // Only check this for TAIT. RPIT already supports `tests/ui/impl-trait/nested-return-type2.rs`
 266         // on stable and we'd break that.
 267         let OpaqueTyOrigin::TyAlias = origin else {
 268             return definition_ty;
 269         };
 270         let def_id = opaque_type_key.def_id;
 271         // This logic duplicates most of `check_opaque_meets_bounds`.
 272         // FIXME(oli-obk): Also do region checks here and then consider removing `check_opaque_meets_bounds` entirely.
 273         let param_env = self.tcx.param_env(def_id);
 274         let body_id = self.tcx.local_def_id_to_hir_id(def_id);
 275         // HACK This bubble is required for this tests to pass:
 276         // type-alias-impl-trait/issue-67844-nested-opaque.rs
 277         let infcx =
 278             self.tcx.infer_ctxt().with_opaque_type_inference(DefiningAnchor::Bubble).build();
 279         let ocx = ObligationCtxt::new(&infcx);
 280         // Require the hidden type to be well-formed with only the generics of the opaque type.
 281         // Defining use functions may have more bounds than the opaque type, which is ok, as long as the
 282         // hidden type is well formed even without those bounds.
 283         let predicate = ty::Binder::dummy(ty::PredicateKind::WellFormed(definition_ty.into()));
 284
 285         let id_substs = InternalSubsts::identity_for_item(self.tcx, def_id.to_def_id());
 286
 287         // Require that the hidden type actually fulfills all the bounds of the opaque type, even without
 288         // the bounds that the function supplies.
 289         let opaque_ty = self.tcx.mk_opaque(def_id.to_def_id(), id_substs);
 290         if let Err(err) = ocx.eq(
 291             &ObligationCause::misc(instantiated_ty.span, body_id),
 292             param_env,
 293             opaque_ty,
 294             definition_ty,
 295         ) {
 296             infcx
 297                 .err_ctxt()
 298                 .report_mismatched_types(
 299                     &ObligationCause::misc(instantiated_ty.span, body_id),
 300                     opaque_ty,
 301                     definition_ty,
 302                     err,
 303                 )
 304                 .emit();
 305         }
 306
 307         ocx.register_obligation(Obligation::misc(
 308             infcx.tcx,
 309             instantiated_ty.span,
 310             body_id,
 311             param_env,
 312             predicate,
 313         ));
 314
 315         // Check that all obligations are satisfied by the implementation's
 316         // version.
 317         let errors = ocx.select_all_or_error();
 318
 319         // This is still required for many(half of the tests in ui/type-alias-impl-trait)
 320         // tests to pass
 321         let _ = infcx.take_opaque_types();
 322
 323         if errors.is_empty() {
 324             definition_ty
 325         } else {
 326             let reported = infcx.err_ctxt().report_fulfillment_errors(&errors, None);
 327             self.tcx.ty_error_with_guaranteed(reported)
 328         }
 329     }
 330 }
 331
 332 fn check_opaque_type_parameter_valid(
 333     tcx: TyCtxt<'_>,
 334     opaque_type_key: OpaqueTypeKey<'_>,
 335     origin: OpaqueTyOrigin,
 336     span: Span,
 337 ) -> bool {
 338     match origin {
 339         // No need to check return position impl trait (RPIT)
 340         // because for type and const parameters they are correct
 341         // by construction: we convert
 342         //
 343         // fn foo<P0..Pn>() -> impl Trait
 344         //
 345         // into
 346         //
 347         // type Foo<P0...Pn>
 348         // fn foo<P0..Pn>() -> Foo<P0...Pn>.
 349         //
 350         // For lifetime parameters we convert
 351         //
 352         // fn foo<'l0..'ln>() -> impl Trait<'l0..'lm>
 353         //
 354         // into
 355         //
 356         // type foo::<'p0..'pn>::Foo<'q0..'qm>
 357         // fn foo<l0..'ln>() -> foo::<'static..'static>::Foo<'l0..'lm>.
 358         //
 359         // which would error here on all of the `'static` args.
 360         OpaqueTyOrigin::FnReturn(..) | OpaqueTyOrigin::AsyncFn(..) => return true,
 361         // Check these
 362         OpaqueTyOrigin::TyAlias => {}
 363     }
 364     let opaque_generics = tcx.generics_of(opaque_type_key.def_id);
 365     let mut seen_params: FxHashMap<_, Vec<_>> = FxHashMap::default();
 366     for (i, arg) in opaque_type_key.substs.iter().enumerate() {
 367         let arg_is_param = match arg.unpack() {
 368             GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)),
 369             GenericArgKind::Lifetime(lt) if lt.is_static() => {
 370                 tcx.sess
 371                     .struct_span_err(span, "non-defining opaque type use in defining scope")
 372                     .span_label(
 373                         tcx.def_span(opaque_generics.param_at(i, tcx).def_id),
 374                         "cannot use static lifetime; use a bound lifetime \
 375                                     instead or remove the lifetime parameter from the \
 376                                     opaque type",
 377                     )
 378                     .emit();
 379                 return false;
 380             }
 381             GenericArgKind::Lifetime(lt) => {
 382                 matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_))
 383             }
 384             GenericArgKind::Const(ct) => matches!(ct.kind(), ty::ConstKind::Param(_)),
 385         };
 386
 387         if arg_is_param {
 388             seen_params.entry(arg).or_default().push(i);
 389         } else {
 390             // Prevent `fn foo() -> Foo<u32>` from being defining.
 391             let opaque_param = opaque_generics.param_at(i, tcx);
 392             tcx.sess
 393                 .struct_span_err(span, "non-defining opaque type use in defining scope")
 394                 .span_note(
 395                     tcx.def_span(opaque_param.def_id),
 396                     &format!(
 397                         "used non-generic {} `{}` for generic parameter",
 398                         opaque_param.kind.descr(),
 399                         arg,
 400                     ),
 401                 )
 402                 .emit();
 403             return false;
 404         }
 405     }
 406
 407     for (_, indices) in seen_params {
 408         if indices.len() > 1 {
 409             let descr = opaque_generics.param_at(indices[0], tcx).kind.descr();
 410             let spans: Vec<_> = indices
 411                 .into_iter()
 412                 .map(|i| tcx.def_span(opaque_generics.param_at(i, tcx).def_id))
 413                 .collect();
 414             tcx.sess
 415                 .struct_span_err(span, "non-defining opaque type use in defining scope")
 416                 .span_note(spans, &format!("{} used multiple times", descr))
 417                 .emit();
 418             return false;
 419         }
 420     }
 421     true
 422 }