compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs

   1 use rustc_data_structures::fx::FxHashMap;
   2 use rustc_hir::{def_id::DefId, Movability, Mutability};
   3 use rustc_infer::traits::query::NoSolution;
   4 use rustc_middle::ty::{
   5     self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
   6 };
   7
   8 use crate::solve::EvalCtxt;
   9
  10 // Calculates the constituent types of a type for `auto trait` purposes.
  11 //
  12 // For types with an "existential" binder, i.e. generator witnesses, we also
  13 // instantiate the binder with placeholders eagerly.
  14 pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
  15     ecx: &EvalCtxt<'_, 'tcx>,
  16     ty: Ty<'tcx>,
  17 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
  18     let tcx = ecx.tcx();
  19     match *ty.kind() {
  20         ty::Uint(_)
  21         | ty::Int(_)
  22         | ty::Bool
  23         | ty::Float(_)
  24         | ty::FnDef(..)
  25         | ty::FnPtr(_)
  26         | ty::Error(_)
  27         | ty::Never
  28         | ty::Char => Ok(vec![]),
  29
  30         // Treat `str` like it's defined as `struct str([u8]);`
  31         ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]),
  32
  33         ty::Dynamic(..)
  34         | ty::Param(..)
  35         | ty::Foreign(..)
  36         | ty::Alias(ty::Projection, ..)
  37         | ty::Placeholder(..)
  38         | ty::Bound(..)
  39         | ty::Infer(_) => {
  40             bug!("unexpected type `{ty}`")
  41         }
  42
  43         ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => {
  44             Ok(vec![element_ty])
  45         }
  46
  47         ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]),
  48
  49         ty::Tuple(ref tys) => {
  50             // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
  51             Ok(tys.iter().collect())
  52         }
  53
  54         ty::Closure(_, ref substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
  55
  56         ty::Generator(_, ref substs, _) => {
  57             let generator_substs = substs.as_generator();
  58             Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()])
  59         }
  60
  61         ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()),
  62
  63         ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx
  64             .tcx()
  65             .generator_hidden_types(def_id)
  66             .map(|bty| {
  67                 ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars(
  68                     tcx,
  69                     bty.subst(tcx, substs),
  70                 ))
  71             })
  72             .collect()),
  73
  74         // For `PhantomData<T>`, we pass `T`.
  75         ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]),
  76
  77         ty::Adt(def, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()),
  78
  79         ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => {
  80             // We can resolve the `impl Trait` to its concrete type,
  81             // which enforces a DAG between the functions requiring
  82             // the auto trait bounds in question.
  83             Ok(vec![tcx.type_of(def_id).subst(tcx, substs)])
  84         }
  85     }
  86 }
  87
  88 pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>(
  89     tcx: TyCtxt<'tcx>,
  90     ty: Ty<'tcx>,
  91 ) -> ty::Binder<'tcx, Ty<'tcx>> {
  92     debug_assert!(!ty.has_late_bound_regions());
  93     let mut counter = 0;
  94     let ty = tcx.fold_regions(ty, |mut r, current_depth| {
  95         if let ty::ReErased = r.kind() {
  96             let br =
  97                 ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) };
  98             counter += 1;
  99             r = tcx.mk_re_late_bound(current_depth, br);
 100         }
 101         r
 102     });
 103     let bound_vars = tcx.mk_bound_variable_kinds_from_iter(
 104         (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))),
 105     );
 106     ty::Binder::bind_with_vars(ty, bound_vars)
 107 }
 108
 109 pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
 110     ecx: &EvalCtxt<'_, 'tcx>,
 111     ty: Ty<'tcx>,
 112 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
 113     match *ty.kind() {
 114         ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 115         | ty::Uint(_)
 116         | ty::Int(_)
 117         | ty::Bool
 118         | ty::Float(_)
 119         | ty::FnDef(..)
 120         | ty::FnPtr(_)
 121         | ty::RawPtr(..)
 122         | ty::Char
 123         | ty::Ref(..)
 124         | ty::Generator(..)
 125         | ty::GeneratorWitness(..)
 126         | ty::GeneratorWitnessMIR(..)
 127         | ty::Array(..)
 128         | ty::Closure(..)
 129         | ty::Never
 130         | ty::Dynamic(_, _, ty::DynStar)
 131         | ty::Error(_) => Ok(vec![]),
 132
 133         ty::Str
 134         | ty::Slice(_)
 135         | ty::Dynamic(..)
 136         | ty::Foreign(..)
 137         | ty::Alias(..)
 138         | ty::Param(_)
 139         | ty::Placeholder(..) => Err(NoSolution),
 140
 141         ty::Bound(..)
 142         | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
 143             bug!("unexpected type `{ty}`")
 144         }
 145
 146         ty::Tuple(tys) => Ok(tys.to_vec()),
 147
 148         ty::Adt(def, substs) => {
 149             let sized_crit = def.sized_constraint(ecx.tcx());
 150             Ok(sized_crit
 151                 .0
 152                 .iter()
 153                 .map(|ty| sized_crit.rebind(*ty).subst(ecx.tcx(), substs))
 154                 .collect())
 155         }
 156     }
 157 }
 158
 159 pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
 160     ecx: &EvalCtxt<'_, 'tcx>,
 161     ty: Ty<'tcx>,
 162 ) -> Result<Vec<Ty<'tcx>>, NoSolution> {
 163     match *ty.kind() {
 164         ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 165         | ty::FnDef(..)
 166         | ty::FnPtr(_)
 167         | ty::Error(_) => Ok(vec![]),
 168
 169         // Implementations are provided in core
 170         ty::Uint(_)
 171         | ty::Int(_)
 172         | ty::Bool
 173         | ty::Float(_)
 174         | ty::Char
 175         | ty::RawPtr(..)
 176         | ty::Never
 177         | ty::Ref(_, _, Mutability::Not)
 178         | ty::Array(..) => Err(NoSolution),
 179
 180         ty::Dynamic(..)
 181         | ty::Str
 182         | ty::Slice(_)
 183         | ty::Generator(_, _, Movability::Static)
 184         | ty::Foreign(..)
 185         | ty::Ref(_, _, Mutability::Mut)
 186         | ty::Adt(_, _)
 187         | ty::Alias(_, _)
 188         | ty::Param(_)
 189         | ty::Placeholder(..) => Err(NoSolution),
 190
 191         ty::Bound(..)
 192         | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
 193             bug!("unexpected type `{ty}`")
 194         }
 195
 196         ty::Tuple(tys) => Ok(tys.to_vec()),
 197
 198         ty::Closure(_, substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
 199
 200         ty::Generator(_, substs, Movability::Movable) => {
 201             if ecx.tcx().features().generator_clone {
 202                 let generator = substs.as_generator();
 203                 Ok(vec![generator.tupled_upvars_ty(), generator.witness()])
 204             } else {
 205                 Err(NoSolution)
 206             }
 207         }
 208
 209         ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()),
 210
 211         ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx
 212             .tcx()
 213             .generator_hidden_types(def_id)
 214             .map(|bty| {
 215                 ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars(
 216                     ecx.tcx(),
 217                     bty.subst(ecx.tcx(), substs),
 218                 ))
 219             })
 220             .collect()),
 221     }
 222 }
 223
 224 // Returns a binder of the tupled inputs types and output type from a builtin callable type.
 225 pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
 226     tcx: TyCtxt<'tcx>,
 227     self_ty: Ty<'tcx>,
 228     goal_kind: ty::ClosureKind,
 229 ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> {
 230     match *self_ty.kind() {
 231         // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
 232         ty::FnDef(def_id, substs) => {
 233             let sig = tcx.fn_sig(def_id);
 234             if sig.skip_binder().is_fn_trait_compatible()
 235                 && tcx.codegen_fn_attrs(def_id).target_features.is_empty()
 236             {
 237                 Ok(Some(
 238                     sig.subst(tcx, substs)
 239                         .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())),
 240                 ))
 241             } else {
 242                 Err(NoSolution)
 243             }
 244         }
 245         // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed.
 246         ty::FnPtr(sig) => {
 247             if sig.is_fn_trait_compatible() {
 248                 Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output()))))
 249             } else {
 250                 Err(NoSolution)
 251             }
 252         }
 253         ty::Closure(_, substs) => {
 254             let closure_substs = substs.as_closure();
 255             match closure_substs.kind_ty().to_opt_closure_kind() {
 256                 // If the closure's kind doesn't extend the goal kind,
 257                 // then the closure doesn't implement the trait.
 258                 Some(closure_kind) => {
 259                     if !closure_kind.extends(goal_kind) {
 260                         return Err(NoSolution);
 261                     }
 262                 }
 263                 // Closure kind is not yet determined, so we return ambiguity unless
 264                 // the expected kind is `FnOnce` as that is always implemented.
 265                 None => {
 266                     if goal_kind != ty::ClosureKind::FnOnce {
 267                         return Ok(None);
 268                     }
 269                 }
 270             }
 271             Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output()))))
 272         }
 273         ty::Bool
 274         | ty::Char
 275         | ty::Int(_)
 276         | ty::Uint(_)
 277         | ty::Float(_)
 278         | ty::Adt(_, _)
 279         | ty::Foreign(_)
 280         | ty::Str
 281         | ty::Array(_, _)
 282         | ty::Slice(_)
 283         | ty::RawPtr(_)
 284         | ty::Ref(_, _, _)
 285         | ty::Dynamic(_, _, _)
 286         | ty::Generator(_, _, _)
 287         | ty::GeneratorWitness(_)
 288         | ty::GeneratorWitnessMIR(..)
 289         | ty::Never
 290         | ty::Tuple(_)
 291         | ty::Alias(_, _)
 292         | ty::Param(_)
 293         | ty::Placeholder(..)
 294         | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
 295         | ty::Error(_) => Err(NoSolution),
 296
 297         ty::Bound(..)
 298         | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
 299             bug!("unexpected type `{self_ty}`")
 300         }
 301     }
 302 }
 303
 304 /// Assemble a list of predicates that would be present on a theoretical
 305 /// user impl for an object type. These predicates must be checked any time
 306 /// we assemble a built-in object candidate for an object type, since they
 307 /// are not implied by the well-formedness of the type.
 308 ///
 309 /// For example, given the following traits:
 310 ///
 311 /// ```rust,ignore (theoretical code)
 312 /// trait Foo: Baz {
 313 ///     type Bar: Copy;
 314 /// }
 315 ///
 316 /// trait Baz {}
 317 /// ```
 318 ///
 319 /// For the dyn type `dyn Foo<Item = Ty>`, we can imagine there being a
 320 /// pair of theoretical impls:
 321 ///
 322 /// ```rust,ignore (theoretical code)
 323 /// impl Foo for dyn Foo<Item = Ty>
 324 /// where
 325 ///     Self: Baz,
 326 ///     <Self as Foo>::Bar: Copy,
 327 /// {
 328 ///     type Bar = Ty;
 329 /// }
 330 ///
 331 /// impl Baz for dyn Foo<Item = Ty> {}
 332 /// ```
 333 ///
 334 /// However, in order to make such impls well-formed, we need to do an
 335 /// additional step of eagerly folding the associated types in the where
 336 /// clauses of the impl. In this example, that means replacing
 337 /// `<Self as Foo>::Bar` with `Ty` in the first impl.
 338 ///
 339 // FIXME: This is only necessary as `<Self as Trait>::Assoc: ItemBound`
 340 // bounds in impls are trivially proven using the item bound candidates.
 341 // This is unsound in general and once that is fixed, we don't need to
 342 // normalize eagerly here. See https://github.com/lcnr/solver-woes/issues/9
 343 // for more details.
 344 pub(in crate::solve) fn predicates_for_object_candidate<'tcx>(
 345     ecx: &EvalCtxt<'_, 'tcx>,
 346     param_env: ty::ParamEnv<'tcx>,
 347     trait_ref: ty::TraitRef<'tcx>,
 348     object_bound: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
 349 ) -> Vec<ty::Predicate<'tcx>> {
 350     let tcx = ecx.tcx();
 351     let mut requirements = vec![];
 352     requirements.extend(
 353         tcx.super_predicates_of(trait_ref.def_id).instantiate(tcx, trait_ref.substs).predicates,
 354     );
 355     for item in tcx.associated_items(trait_ref.def_id).in_definition_order() {
 356         // FIXME(associated_const_equality): Also add associated consts to
 357         // the requirements here.
 358         if item.kind == ty::AssocKind::Type {
 359             requirements.extend(tcx.item_bounds(item.def_id).subst(tcx, trait_ref.substs));
 360         }
 361     }
 362
 363     let mut replace_projection_with = FxHashMap::default();
 364     for bound in object_bound {
 365         if let ty::ExistentialPredicate::Projection(proj) = bound.skip_binder() {
 366             let proj = proj.with_self_ty(tcx, trait_ref.self_ty());
 367             let old_ty = replace_projection_with.insert(proj.def_id(), bound.rebind(proj));
 368             assert_eq!(
 369                 old_ty,
 370                 None,
 371                 "{} has two substitutions: {} and {}",
 372                 proj.projection_ty,
 373                 proj.term,
 374                 old_ty.unwrap()
 375             );
 376         }
 377     }
 378
 379     requirements.fold_with(&mut ReplaceProjectionWith {
 380         ecx,
 381         param_env,
 382         mapping: replace_projection_with,
 383     })
 384 }
 385
 386 struct ReplaceProjectionWith<'a, 'tcx> {
 387     ecx: &'a EvalCtxt<'a, 'tcx>,
 388     param_env: ty::ParamEnv<'tcx>,
 389     mapping: FxHashMap<DefId, ty::PolyProjectionPredicate<'tcx>>,
 390 }
 391
 392 impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> {
 393     fn interner(&self) -> TyCtxt<'tcx> {
 394         self.ecx.tcx()
 395     }
 396
 397     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 398         if let ty::Alias(ty::Projection, alias_ty) = *ty.kind()
 399             && let Some(replacement) = self.mapping.get(&alias_ty.def_id)
 400         {
 401             // We may have a case where our object type's projection bound is higher-ranked,
 402             // but the where clauses we instantiated are not. We can solve this by instantiating
 403             // the binder at the usage site.
 404             let proj = self.ecx.instantiate_binder_with_infer(*replacement);
 405             // FIXME: Technically this folder could be fallible?
 406             let nested = self
 407                 .ecx
 408                 .eq_and_get_goals(self.param_env, alias_ty, proj.projection_ty)
 409                 .expect("expected to be able to unify goal projection with dyn's projection");
 410             // FIXME: Technically we could register these too..
 411             assert!(nested.is_empty(), "did not expect unification to have any nested goals");
 412             proj.term.ty().unwrap()
 413         } else {
 414             ty.super_fold_with(self)
 415         }
 416     }
 417 }