1 //! Orphan checker: every impl either implements a trait defined in this
2 //! crate or pertains to a type defined in this crate.
4 use rustc_data_structures::fx::FxHashSet;
5 use rustc_errors::struct_span_err;
6 use rustc_errors::ErrorReported;
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};
15 use rustc_trait_selection::traits;
16 use std::ops::ControlFlow;
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) {
24 Err(ErrorReported) => errors.push(impl_of_trait),
28 if tcx.trait_is_auto(trait_def_id) {
29 lint_auto_trait_impls(tcx, trait_def_id, impls_of_trait);
32 tcx.arena.alloc_slice(&errors)
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;
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),
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()) {
49 Err(err) => emit_orphan_check_error(
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:
68 // fn two_foos<A:Foo,B:Foo>(..) {
69 // one_foo::<(A,B)>(..)
71 // fn one_foo<T:Foo>(..) { .. }
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`.
78 // Now imagine that crate B comes along and does the following:
85 // impl !Send for (A, B) { }
88 // This final impl is legal according to the orphan
89 // rules, but it invalidates the reasoning from
92 "trait_ref={:?} trait_def_id={:?} trait_is_auto={}",
95 tcx.trait_is_auto(trait_def_id)
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),
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() {
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)
122 "can't implement cross-crate trait for type in another crate",
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),
133 "can't implement cross-crate trait with a default impl for \
134 non-struct/enum type",
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);
144 if let ty::Opaque(def_id, _) = *trait_ref.self_ty().kind() {
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")
149 return Err(ErrorReported);
155 fn emit_orphan_check_error<'tcx>(
160 generics: &hir::Generics<'tcx>,
161 err: traits::OrphanCheckErr<'tcx>,
162 ) -> Result<!, ErrorReported> {
164 traits::OrphanCheckErr::NonLocalInputType(tys) => {
165 let mut err = struct_span_err!(
169 "only traits defined in the current crate can be implemented for \
172 err.span_label(sp, "impl doesn't use only types from inside the current crate");
173 for (ty, is_target_ty) in &tys {
175 tcx.infer_ctxt().enter(|infcx| {
176 // Remove the lifetimes unnecessary for this error.
177 ty = infcx.freshen(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()),
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), ""),
195 let msg = format!("{} is not defined in the current crate{}", ty, postfix);
197 // Point at `D<A>` in `impl<A, B> for C<B> in D<A>`
198 err.span_label(self_ty_span, &msg);
200 // Point at `C<B>` in `impl<A, B> for C<B> in D<A>`
201 err.span_label(trait_span, &msg);
204 err.note("define and implement a trait or new type instead");
207 traits::OrphanCheckErr::UncoveredTy(param_ty, local_type) => {
209 for param in generics.params {
210 if param.name.ident().to_string() == param_ty.to_string() {
216 Some(local_type) => struct_span_err!(
220 "type parameter `{}` must be covered by another type \
221 when it appears before the first local type (`{}`)",
228 "type parameter `{}` must be covered by another type \
229 when it appears before the first local type (`{}`)",
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 \
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",
245 None => struct_span_err!(
249 "type parameter `{}` must be used as the type parameter for some \
250 local type (e.g., `MyStruct<{}>`)",
257 "type parameter `{}` must be used as the type parameter for some \
263 "implementing a foreign trait is only possible if at \
264 least one of the types for which it is implemented is local",
267 "only traits defined in the current crate can be \
268 implemented for a type parameter",
279 struct AreUniqueParamsVisitor {
280 seen: GrowableBitSet<u32>,
283 #[derive(Copy, Clone)]
284 enum NotUniqueParam<'tcx> {
285 DuplicateParam(GenericArg<'tcx>),
286 NotParam(GenericArg<'tcx>),
289 impl<'tcx> TypeVisitor<'tcx> for AreUniqueParamsVisitor {
290 type BreakTy = NotUniqueParam<'tcx>;
291 fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
294 if self.seen.insert(p.index) {
295 ControlFlow::CONTINUE
297 ControlFlow::Break(NotUniqueParam::DuplicateParam(t.into()))
300 _ => ControlFlow::Break(NotUniqueParam::NotParam(t.into())),
303 fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
305 ty::ReEarlyBound(p) => {
306 if self.seen.insert(p.index) {
307 ControlFlow::CONTINUE
309 ControlFlow::Break(NotUniqueParam::DuplicateParam(r.into()))
312 _ => ControlFlow::Break(NotUniqueParam::NotParam(r.into())),
315 fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
317 ty::ConstKind::Param(p) => {
318 if self.seen.insert(p.index) {
319 ControlFlow::CONTINUE
321 ControlFlow::Break(NotUniqueParam::DuplicateParam(c.into()))
324 _ => ControlFlow::Break(NotUniqueParam::NotParam(c.into())),
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() {
339 if tcx.impl_polarity(impl_def_id) != ImplPolarity::Positive {
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),
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.
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) => {
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
368 // What we do here is a bit simpler:
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) {
376 non_covering_impls.push((impl_def_id, self_type_did, arg));
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),
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),
393 let item_span = tcx.def_span(self_type_did);
394 let self_descr = tcx.def_kind(self_type_did).descr(self_type_did);
398 "try using the same sequence of generic parameters as the {} definition",
403 NotUniqueParam::DuplicateParam(arg) => {
404 err.note(&format!("`{}` is mentioned multiple times", arg));
406 NotUniqueParam::NotParam(arg) => {
407 err.note(&format!("`{}` is not a generic parameter", arg));
416 fn fast_reject_auto_impl<'tcx>(tcx: TyCtxt<'tcx>, trait_def_id: DefId, self_ty: Ty<'tcx>) -> bool {
417 struct DisableAutoTraitVisitor<'tcx> {
420 self_ty_root: Ty<'tcx>,
421 seen: FxHashSet<DefId>,
424 impl<'tcx> TypeVisitor<'tcx> for DisableAutoTraitVisitor<'tcx> {
426 fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
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
435 // We might just want to take the rustdoc code and somehow avoid
436 // explicit impls for `Self`.
437 ImplPolarity::Positive => return ControlFlow::CONTINUE,
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.
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)?;
454 ControlFlow::CONTINUE
456 _ => t.super_visit_with(self),
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),
467 .visit_with(&mut DisableAutoTraitVisitor {
471 seen: FxHashSet::default(),