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