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