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