compiler/rustc_typeck/src/coherence/orphan.rs

   1 //! Orphan checker: every impl either implements a trait defined in this
   2 //! crate or pertains to a type defined in this crate.
   3
   4 use rustc_data_structures::fx::FxHashSet;
   5 use rustc_errors::struct_span_err;
   6 use rustc_errors::{Diagnostic, ErrorGuaranteed};
   7 use rustc_hir as hir;
   8 use rustc_infer::infer::TyCtxtInferExt;
   9 use rustc_middle::ty::subst::GenericArgKind;
  10 use rustc_middle::ty::subst::InternalSubsts;
  11 use rustc_middle::ty::util::IgnoreRegions;
  12 use rustc_middle::ty::{
  13     self, ImplPolarity, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor,
  14 };
  15 use rustc_session::lint;
  16 use rustc_span::def_id::{DefId, LocalDefId};
  17 use rustc_span::Span;
  18 use rustc_trait_selection::traits;
  19 use std::ops::ControlFlow;
  20
  21 #[instrument(skip(tcx), level = "debug")]
  22 pub(crate) fn orphan_check_impl(
  23     tcx: TyCtxt<'_>,
  24     impl_def_id: LocalDefId,
  25 ) -> Result<(), ErrorGuaranteed> {
  26     let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
  27     if let Some(err) = trait_ref.error_reported() {
  28         return Err(err);
  29     }
  30
  31     let ret = do_orphan_check_impl(tcx, trait_ref, impl_def_id);
  32     if tcx.trait_is_auto(trait_ref.def_id) {
  33         lint_auto_trait_impl(tcx, trait_ref, impl_def_id);
  34     }
  35
  36     ret
  37 }
  38
  39 fn do_orphan_check_impl<'tcx>(
  40     tcx: TyCtxt<'tcx>,
  41     trait_ref: ty::TraitRef<'tcx>,
  42     def_id: LocalDefId,
  43 ) -> Result<(), ErrorGuaranteed> {
  44     let trait_def_id = trait_ref.def_id;
  45
  46     let item = tcx.hir().item(hir::ItemId { def_id });
  47     let hir::ItemKind::Impl(ref impl_) = item.kind else {
  48         bug!("{:?} is not an impl: {:?}", def_id, item);
  49     };
  50     let sp = tcx.def_span(def_id);
  51     let tr = impl_.of_trait.as_ref().unwrap();
  52
  53     // Ensure no opaque types are present in this impl header. See issues #76202 and #86411 for examples,
  54     // and #84660 where it would otherwise allow unsoundness.
  55     if trait_ref.has_opaque_types() {
  56         trace!("{:#?}", item);
  57         // First we find the opaque type in question.
  58         for ty in trait_ref.substs {
  59             for ty in ty.walk() {
  60                 let ty::subst::GenericArgKind::Type(ty) = ty.unpack() else { continue };
  61                 let ty::Opaque(def_id, _) = *ty.kind() else { continue };
  62                 trace!(?def_id);
  63
  64                 // Then we search for mentions of the opaque type's type alias in the HIR
  65                 struct SpanFinder<'tcx> {
  66                     sp: Span,
  67                     def_id: DefId,
  68                     tcx: TyCtxt<'tcx>,
  69                 }
  70                 impl<'v, 'tcx> hir::intravisit::Visitor<'v> for SpanFinder<'tcx> {
  71                     #[instrument(level = "trace", skip(self, _id))]
  72                     fn visit_path(&mut self, path: &'v hir::Path<'v>, _id: hir::HirId) {
  73                         // You can't mention an opaque type directly, so we look for type aliases
  74                         if let hir::def::Res::Def(hir::def::DefKind::TyAlias, def_id) = path.res {
  75                             // And check if that type alias's type contains the opaque type we're looking for
  76                             for arg in self.tcx.type_of(def_id).walk() {
  77                                 if let GenericArgKind::Type(ty) = arg.unpack() {
  78                                     if let ty::Opaque(def_id, _) = *ty.kind() {
  79                                         if def_id == self.def_id {
  80                                             // Finally we update the span to the mention of the type alias
  81                                             self.sp = path.span;
  82                                             return;
  83                                         }
  84                                     }
  85                                 }
  86                             }
  87                         }
  88                         hir::intravisit::walk_path(self, path)
  89                     }
  90                 }
  91
  92                 let mut visitor = SpanFinder { sp, def_id, tcx };
  93                 hir::intravisit::walk_item(&mut visitor, item);
  94                 let reported = tcx
  95                     .sess
  96                     .struct_span_err(visitor.sp, "cannot implement trait on type alias impl trait")
  97                     .span_note(tcx.def_span(def_id), "type alias impl trait defined here")
  98                     .emit();
  99                 return Err(reported);
 100             }
 101         }
 102         span_bug!(sp, "opaque type not found, but `has_opaque_types` is set")
 103     }
 104
 105     match traits::orphan_check(tcx, item.def_id.to_def_id()) {
 106         Ok(()) => {}
 107         Err(err) => emit_orphan_check_error(
 108             tcx,
 109             sp,
 110             item.span,
 111             tr.path.span,
 112             trait_ref.self_ty(),
 113             impl_.self_ty.span,
 114             &impl_.generics,
 115             err,
 116         )?,
 117     }
 118
 119     // In addition to the above rules, we restrict impls of auto traits
 120     // so that they can only be implemented on nominal types, such as structs,
 121     // enums or foreign types. To see why this restriction exists, consider the
 122     // following example (#22978). Imagine that crate A defines an auto trait
 123     // `Foo` and a fn that operates on pairs of types:
 124     //
 125     // ```
 126     // // Crate A
 127     // auto trait Foo { }
 128     // fn two_foos<A:Foo,B:Foo>(..) {
 129     //     one_foo::<(A,B)>(..)
 130     // }
 131     // fn one_foo<T:Foo>(..) { .. }
 132     // ```
 133     //
 134     // This type-checks fine; in particular the fn
 135     // `two_foos` is able to conclude that `(A,B):Foo`
 136     // because `A:Foo` and `B:Foo`.
 137     //
 138     // Now imagine that crate B comes along and does the following:
 139     //
 140     // ```
 141     // struct A { }
 142     // struct B { }
 143     // impl Foo for A { }
 144     // impl Foo for B { }
 145     // impl !Send for (A, B) { }
 146     // ```
 147     //
 148     // This final impl is legal according to the orphan
 149     // rules, but it invalidates the reasoning from
 150     // `two_foos` above.
 151     debug!(
 152         "trait_ref={:?} trait_def_id={:?} trait_is_auto={}",
 153         trait_ref,
 154         trait_def_id,
 155         tcx.trait_is_auto(trait_def_id)
 156     );
 157
 158     if tcx.trait_is_auto(trait_def_id) && !trait_def_id.is_local() {
 159         let self_ty = trait_ref.self_ty();
 160         let opt_self_def_id = match *self_ty.kind() {
 161             ty::Adt(self_def, _) => Some(self_def.did()),
 162             ty::Foreign(did) => Some(did),
 163             _ => None,
 164         };
 165
 166         let msg = match opt_self_def_id {
 167             // We only want to permit nominal types, but not *all* nominal types.
 168             // They must be local to the current crate, so that people
 169             // can't do `unsafe impl Send for Rc<SomethingLocal>` or
 170             // `impl !Send for Box<SomethingLocalAndSend>`.
 171             Some(self_def_id) => {
 172                 if self_def_id.is_local() {
 173                     None
 174                 } else {
 175                     Some((
 176                         format!(
 177                             "cross-crate traits with a default impl, like `{}`, \
 178                                     can only be implemented for a struct/enum type \
 179                                     defined in the current crate",
 180                             tcx.def_path_str(trait_def_id)
 181                         ),
 182                         "can't implement cross-crate trait for type in another crate",
 183                     ))
 184                 }
 185             }
 186             _ => Some((
 187                 format!(
 188                     "cross-crate traits with a default impl, like `{}`, can \
 189                                 only be implemented for a struct/enum type, not `{}`",
 190                     tcx.def_path_str(trait_def_id),
 191                     self_ty
 192                 ),
 193                 "can't implement cross-crate trait with a default impl for \
 194                         non-struct/enum type",
 195             )),
 196         };
 197
 198         if let Some((msg, label)) = msg {
 199             let reported =
 200                 struct_span_err!(tcx.sess, sp, E0321, "{}", msg).span_label(sp, label).emit();
 201             return Err(reported);
 202         }
 203     }
 204
 205     Ok(())
 206 }
 207
 208 fn emit_orphan_check_error<'tcx>(
 209     tcx: TyCtxt<'tcx>,
 210     sp: Span,
 211     full_impl_span: Span,
 212     trait_span: Span,
 213     self_ty: Ty<'tcx>,
 214     self_ty_span: Span,
 215     generics: &hir::Generics<'tcx>,
 216     err: traits::OrphanCheckErr<'tcx>,
 217 ) -> Result<!, ErrorGuaranteed> {
 218     Err(match err {
 219         traits::OrphanCheckErr::NonLocalInputType(tys) => {
 220             let msg = match self_ty.kind() {
 221                 ty::Adt(..) => "can be implemented for types defined outside of the crate",
 222                 _ if self_ty.is_primitive() => "can be implemented for primitive types",
 223                 _ => "can be implemented for arbitrary types",
 224             };
 225             let mut err = struct_span_err!(
 226                 tcx.sess,
 227                 sp,
 228                 E0117,
 229                 "only traits defined in the current crate {msg}"
 230             );
 231             err.span_label(sp, "impl doesn't use only types from inside the current crate");
 232             for (ty, is_target_ty) in &tys {
 233                 let mut ty = *ty;
 234                 tcx.infer_ctxt().enter(|infcx| {
 235                     // Remove the lifetimes unnecessary for this error.
 236                     ty = infcx.freshen(ty);
 237                 });
 238                 ty = match ty.kind() {
 239                     // Remove the type arguments from the output, as they are not relevant.
 240                     // You can think of this as the reverse of `resolve_vars_if_possible`.
 241                     // That way if we had `Vec<MyType>`, we will properly attribute the
 242                     // problem to `Vec<T>` and avoid confusing the user if they were to see
 243                     // `MyType` in the error.
 244                     ty::Adt(def, _) => tcx.mk_adt(*def, ty::List::empty()),
 245                     _ => ty,
 246                 };
 247                 let this = "this".to_string();
 248                 let (ty, postfix) = match &ty.kind() {
 249                     ty::Slice(_) => (this, " because slices are always foreign"),
 250                     ty::Array(..) => (this, " because arrays are always foreign"),
 251                     ty::Tuple(..) => (this, " because tuples are always foreign"),
 252                     ty::RawPtr(ptr_ty) => {
 253                         emit_newtype_suggestion_for_raw_ptr(
 254                             full_impl_span,
 255                             self_ty,
 256                             self_ty_span,
 257                             ptr_ty,
 258                             &mut err,
 259                         );
 260
 261                         (format!("`{}`", ty), " because raw pointers are always foreign")
 262                     }
 263                     _ => (format!("`{}`", ty), ""),
 264                 };
 265
 266                 let msg = format!("{} is not defined in the current crate{}", ty, postfix);
 267                 if *is_target_ty {
 268                     // Point at `D<A>` in `impl<A, B> for C<B> in D<A>`
 269                     err.span_label(self_ty_span, &msg);
 270                 } else {
 271                     // Point at `C<B>` in `impl<A, B> for C<B> in D<A>`
 272                     err.span_label(trait_span, &msg);
 273                 }
 274             }
 275             err.note("define and implement a trait or new type instead");
 276             err.emit()
 277         }
 278         traits::OrphanCheckErr::UncoveredTy(param_ty, local_type) => {
 279             let mut sp = sp;
 280             for param in generics.params {
 281                 if param.name.ident().to_string() == param_ty.to_string() {
 282                     sp = param.span;
 283                 }
 284             }
 285
 286             match local_type {
 287                 Some(local_type) => struct_span_err!(
 288                     tcx.sess,
 289                     sp,
 290                     E0210,
 291                     "type parameter `{}` must be covered by another type \
 292                     when it appears before the first local type (`{}`)",
 293                     param_ty,
 294                     local_type
 295                 )
 296                 .span_label(
 297                     sp,
 298                     format!(
 299                         "type parameter `{}` must be covered by another type \
 300                     when it appears before the first local type (`{}`)",
 301                         param_ty, local_type
 302                     ),
 303                 )
 304                 .note(
 305                     "implementing a foreign trait is only possible if at \
 306                         least one of the types for which it is implemented is local, \
 307                         and no uncovered type parameters appear before that first \
 308                         local type",
 309                 )
 310                 .note(
 311                     "in this case, 'before' refers to the following order: \
 312                         `impl<..> ForeignTrait<T1, ..., Tn> for T0`, \
 313                         where `T0` is the first and `Tn` is the last",
 314                 )
 315                 .emit(),
 316                 None => struct_span_err!(
 317                     tcx.sess,
 318                     sp,
 319                     E0210,
 320                     "type parameter `{}` must be used as the type parameter for some \
 321                     local type (e.g., `MyStruct<{}>`)",
 322                     param_ty,
 323                     param_ty
 324                 )
 325                 .span_label(
 326                     sp,
 327                     format!(
 328                         "type parameter `{}` must be used as the type parameter for some \
 329                     local type",
 330                         param_ty,
 331                     ),
 332                 )
 333                 .note(
 334                     "implementing a foreign trait is only possible if at \
 335                         least one of the types for which it is implemented is local",
 336                 )
 337                 .note(
 338                     "only traits defined in the current crate can be \
 339                         implemented for a type parameter",
 340                 )
 341                 .emit(),
 342             }
 343         }
 344     })
 345 }
 346
 347 fn emit_newtype_suggestion_for_raw_ptr(
 348     full_impl_span: Span,
 349     self_ty: Ty<'_>,
 350     self_ty_span: Span,
 351     ptr_ty: &ty::TypeAndMut<'_>,
 352     diag: &mut Diagnostic,
 353 ) {
 354     if !self_ty.needs_subst() {
 355         let mut_key = if ptr_ty.mutbl == rustc_middle::mir::Mutability::Mut { "mut " } else { "" };
 356         let msg_sugg = "consider introducing a new wrapper type".to_owned();
 357         let sugg = vec![
 358             (
 359                 full_impl_span.shrink_to_lo(),
 360                 format!("struct WrapperType(*{}{});\n\n", mut_key, ptr_ty.ty),
 361             ),
 362             (self_ty_span, "WrapperType".to_owned()),
 363         ];
 364         diag.multipart_suggestion(msg_sugg, sugg, rustc_errors::Applicability::MaybeIncorrect);
 365     }
 366 }
 367
 368 /// Lint impls of auto traits if they are likely to have
 369 /// unsound or surprising effects on auto impls.
 370 fn lint_auto_trait_impl<'tcx>(
 371     tcx: TyCtxt<'tcx>,
 372     trait_ref: ty::TraitRef<'tcx>,
 373     impl_def_id: LocalDefId,
 374 ) {
 375     if tcx.impl_polarity(impl_def_id) != ImplPolarity::Positive {
 376         return;
 377     }
 378
 379     assert_eq!(trait_ref.substs.len(), 1);
 380     let self_ty = trait_ref.self_ty();
 381     let (self_type_did, substs) = match self_ty.kind() {
 382         ty::Adt(def, substs) => (def.did(), substs),
 383         _ => {
 384             // FIXME: should also lint for stuff like `&i32` but
 385             // considering that auto traits are unstable, that
 386             // isn't too important for now as this only affects
 387             // crates using `nightly`, and std.
 388             return;
 389         }
 390     };
 391
 392     // Impls which completely cover a given root type are fine as they
 393     // disable auto impls entirely. So only lint if the substs
 394     // are not a permutation of the identity substs.
 395     let Err(arg) = tcx.uses_unique_generic_params(substs, IgnoreRegions::Yes) else {
 396         // ok
 397         return;
 398     };
 399
 400     // Ideally:
 401     //
 402     // - compute the requirements for the auto impl candidate
 403     // - check whether these are implied by the non covering impls
 404     // - if not, emit the lint
 405     //
 406     // What we do here is a bit simpler:
 407     //
 408     // - badly check if an auto impl candidate definitely does not apply
 409     //   for the given simplified type
 410     // - if so, do not lint
 411     if fast_reject_auto_impl(tcx, trait_ref.def_id, self_ty) {
 412         // ok
 413         return;
 414     }
 415
 416     tcx.struct_span_lint_hir(
 417         lint::builtin::SUSPICIOUS_AUTO_TRAIT_IMPLS,
 418         tcx.hir().local_def_id_to_hir_id(impl_def_id),
 419         tcx.def_span(impl_def_id),
 420         |err| {
 421             let item_span = tcx.def_span(self_type_did);
 422             let self_descr = tcx.def_kind(self_type_did).descr(self_type_did);
 423             let mut err = err.build(&format!(
 424                 "cross-crate traits with a default impl, like `{}`, \
 425                          should not be specialized",
 426                 tcx.def_path_str(trait_ref.def_id),
 427             ));
 428             match arg {
 429                 ty::util::NotUniqueParam::DuplicateParam(arg) => {
 430                     err.note(&format!("`{}` is mentioned multiple times", arg));
 431                 }
 432                 ty::util::NotUniqueParam::NotParam(arg) => {
 433                     err.note(&format!("`{}` is not a generic parameter", arg));
 434                 }
 435             }
 436             err.span_note(
 437                 item_span,
 438                 &format!(
 439                     "try using the same sequence of generic parameters as the {} definition",
 440                     self_descr,
 441                 ),
 442             );
 443             err.emit();
 444         },
 445     );
 446 }
 447
 448 fn fast_reject_auto_impl<'tcx>(tcx: TyCtxt<'tcx>, trait_def_id: DefId, self_ty: Ty<'tcx>) -> bool {
 449     struct DisableAutoTraitVisitor<'tcx> {
 450         tcx: TyCtxt<'tcx>,
 451         trait_def_id: DefId,
 452         self_ty_root: Ty<'tcx>,
 453         seen: FxHashSet<DefId>,
 454     }
 455
 456     impl<'tcx> TypeVisitor<'tcx> for DisableAutoTraitVisitor<'tcx> {
 457         type BreakTy = ();
 458         fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 459             let tcx = self.tcx;
 460             if t != self.self_ty_root {
 461                 for impl_def_id in tcx.non_blanket_impls_for_ty(self.trait_def_id, t) {
 462                     match tcx.impl_polarity(impl_def_id) {
 463                         ImplPolarity::Negative => return ControlFlow::BREAK,
 464                         ImplPolarity::Reservation => {}
 465                         // FIXME(@lcnr): That's probably not good enough, idk
 466                         //
 467                         // We might just want to take the rustdoc code and somehow avoid
 468                         // explicit impls for `Self`.
 469                         ImplPolarity::Positive => return ControlFlow::CONTINUE,
 470                     }
 471                 }
 472             }
 473
 474             match t.kind() {
 475                 ty::Adt(def, substs) if def.is_phantom_data() => substs.visit_with(self),
 476                 ty::Adt(def, substs) => {
 477                     // @lcnr: This is the only place where cycles can happen. We avoid this
 478                     // by only visiting each `DefId` once.
 479                     //
 480                     // This will be is incorrect in subtle cases, but I don't care :)
 481                     if self.seen.insert(def.did()) {
 482                         for ty in def.all_fields().map(|field| field.ty(tcx, substs)) {
 483                             ty.visit_with(self)?;
 484                         }
 485                     }
 486
 487                     ControlFlow::CONTINUE
 488                 }
 489                 _ => t.super_visit_with(self),
 490             }
 491         }
 492     }
 493
 494     let self_ty_root = match self_ty.kind() {
 495         ty::Adt(def, _) => tcx.mk_adt(*def, InternalSubsts::identity_for_item(tcx, def.did())),
 496         _ => unimplemented!("unexpected self ty {:?}", self_ty),
 497     };
 498
 499     self_ty_root
 500         .visit_with(&mut DisableAutoTraitVisitor {
 501             tcx,
 502             self_ty_root,
 503             trait_def_id,
 504             seen: FxHashSet::default(),
 505         })
 506         .is_break()
 507 }