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