use hir::def_id::{DefId, LOCAL_CRATE};
use syntax_pos::DUMMY_SP;
use traits::{self, Normalized, SelectionContext, Obligation, ObligationCause, Reveal};
+use traits::IntercrateMode;
use traits::select::IntercrateAmbiguityCause;
use ty::{self, Ty, TyCtxt};
+use ty::fold::TypeFoldable;
use ty::subst::Subst;
-use infer::{InferCtxt, InferOk};
+use infer::{InferOk};
-#[derive(Copy, Clone)]
-struct InferIsLocal(bool);
+/// Whether we do the orphan check relative to this crate or
+/// to some remote crate.
+#[derive(Copy, Clone, Debug)]
+enum InCrate {
+ Local,
+ Remote
+}
+
+#[derive(Debug, Copy, Clone)]
+pub enum Conflict {
+ Upstream,
+ Downstream { used_to_be_broken: bool }
+}
pub struct OverlapResult<'tcx> {
pub impl_header: ty::ImplHeader<'tcx>,
pub intercrate_ambiguity_causes: Vec<IntercrateAmbiguityCause>,
}
-/// If there are types that satisfy both impls, returns a suitably-freshened
-/// `ImplHeader` with those types substituted
-pub fn overlapping_impls<'cx, 'gcx, 'tcx>(infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
- impl1_def_id: DefId,
- impl2_def_id: DefId)
- -> Option<OverlapResult<'tcx>>
+/// If there are types that satisfy both impls, invokes `on_overlap`
+/// with a suitably-freshened `ImplHeader` with those types
+/// substituted. Otherwise, invokes `no_overlap`.
+pub fn overlapping_impls<'gcx, F1, F2, R>(
+ tcx: TyCtxt<'_, 'gcx, 'gcx>,
+ impl1_def_id: DefId,
+ impl2_def_id: DefId,
+ intercrate_mode: IntercrateMode,
+ on_overlap: F1,
+ no_overlap: F2,
+) -> R
+where
+ F1: FnOnce(OverlapResult<'_>) -> R,
+ F2: FnOnce() -> R,
{
debug!("impl_can_satisfy(\
impl1_def_id={:?}, \
- impl2_def_id={:?})",
+ impl2_def_id={:?},
+ intercrate_mode={:?})",
impl1_def_id,
- impl2_def_id);
+ impl2_def_id,
+ intercrate_mode);
- let selcx = &mut SelectionContext::intercrate(infcx);
- overlap(selcx, impl1_def_id, impl2_def_id)
+ let overlaps = tcx.infer_ctxt().enter(|infcx| {
+ let selcx = &mut SelectionContext::intercrate(&infcx, intercrate_mode);
+ overlap(selcx, impl1_def_id, impl2_def_id).is_some()
+ });
+
+ if !overlaps {
+ return no_overlap();
+ }
+
+ // In the case where we detect an error, run the check again, but
+ // this time tracking intercrate ambuiguity causes for better
+ // diagnostics. (These take time and can lead to false errors.)
+ tcx.infer_ctxt().enter(|infcx| {
+ let selcx = &mut SelectionContext::intercrate(&infcx, intercrate_mode);
+ selcx.enable_tracking_intercrate_ambiguity_causes();
+ on_overlap(overlap(selcx, impl1_def_id, impl2_def_id).unwrap())
+ })
}
fn with_fresh_ty_vars<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
return None
}
- Some(OverlapResult {
- impl_header: selcx.infcx().resolve_type_vars_if_possible(&a_impl_header),
- intercrate_ambiguity_causes: selcx.intercrate_ambiguity_causes().to_vec(),
- })
+ let impl_header = selcx.infcx().resolve_type_vars_if_possible(&a_impl_header);
+ let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes();
+ debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes);
+ Some(OverlapResult { impl_header, intercrate_ambiguity_causes })
}
pub fn trait_ref_is_knowable<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
- trait_ref: ty::TraitRef<'tcx>) -> bool
+ trait_ref: ty::TraitRef<'tcx>)
+ -> Option<Conflict>
{
debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref);
-
- // if the orphan rules pass, that means that no ancestor crate can
- // impl this, so it's up to us.
- if orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false)).is_ok() {
- debug!("trait_ref_is_knowable: orphan check passed");
- return true;
+ if orphan_check_trait_ref(tcx, trait_ref, InCrate::Remote).is_ok() {
+ // A downstream or cousin crate is allowed to implement some
+ // substitution of this trait-ref.
+
+ // A trait can be implementable for a trait ref by both the current
+ // crate and crates downstream of it. Older versions of rustc
+ // were not aware of this, causing incoherence (issue #43355).
+ let used_to_be_broken =
+ orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok();
+ if used_to_be_broken {
+ debug!("trait_ref_is_knowable({:?}) - USED TO BE BROKEN", trait_ref);
+ }
+ return Some(Conflict::Downstream { used_to_be_broken });
}
- // if the trait is not marked fundamental, then it's always possible that
- // an ancestor crate will impl this in the future, if they haven't
- // already
- if !trait_ref_is_local_or_fundamental(tcx, trait_ref) {
- debug!("trait_ref_is_knowable: trait is neither local nor fundamental");
- return false;
+ if trait_ref_is_local_or_fundamental(tcx, trait_ref) {
+ // This is a local or fundamental trait, so future-compatibility
+ // is no concern. We know that downstream/cousin crates are not
+ // allowed to implement a substitution of this trait ref, which
+ // means impls could only come from dependencies of this crate,
+ // which we already know about.
+ return None;
}
- // find out when some downstream (or cousin) crate could impl this
- // trait-ref, presuming that all the parameters were instantiated
- // with downstream types. If not, then it could only be
- // implemented by an upstream crate, which means that the impl
- // must be visible to us, and -- since the trait is fundamental
- // -- we can test.
- orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(true)).is_err()
+ // This is a remote non-fundamental trait, so if another crate
+ // can be the "final owner" of a substitution of this trait-ref,
+ // they are allowed to implement it future-compatibly.
+ //
+ // However, if we are a final owner, then nobody else can be,
+ // and if we are an intermediate owner, then we don't care
+ // about future-compatibility, which means that we're OK if
+ // we are an owner.
+ if orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok() {
+ debug!("trait_ref_is_knowable: orphan check passed");
+ return None;
+ } else {
+ debug!("trait_ref_is_knowable: nonlocal, nonfundamental, unowned");
+ return Some(Conflict::Upstream);
+ }
}
pub fn trait_ref_is_local_or_fundamental<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
return Ok(());
}
- orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false))
+ orphan_check_trait_ref(tcx, trait_ref, InCrate::Local)
}
+/// Check whether a trait-ref is potentially implementable by a crate.
+///
+/// The current rule is that a trait-ref orphan checks in a crate C:
+///
+/// 1. Order the parameters in the trait-ref in subst order - Self first,
+/// others linearly (e.g. `<U as Foo<V, W>>` is U < V < W).
+/// 2. Of these type parameters, there is at least one type parameter
+/// in which, walking the type as a tree, you can reach a type local
+/// to C where all types in-between are fundamental types. Call the
+/// first such parameter the "local key parameter".
+/// - e.g. `Box<LocalType>` is OK, because you can visit LocalType
+/// going through `Box`, which is fundamental.
+/// - similarly, `FundamentalPair<Vec<()>, Box<LocalType>>` is OK for
+/// the same reason.
+/// - but (knowing that `Vec<T>` is non-fundamental, and assuming it's
+/// not local), `Vec<LocalType>` is bad, because `Vec<->` is between
+/// the local type and the type parameter.
+/// 3. Every type parameter before the local key parameter is fully known in C.
+/// - e.g. `impl<T> T: Trait<LocalType>` is bad, because `T` might be
+/// an unknown type.
+/// - but `impl<T> LocalType: Trait<T>` is OK, because `LocalType`
+/// occurs before `T`.
+/// 4. Every type in the local key parameter not known in C, going
+/// through the parameter's type tree, must appear only as a subtree of
+/// a type local to C, with only fundamental types between the type
+/// local to C and the local key parameter.
+/// - e.g. `Vec<LocalType<T>>>` (or equivalently `Box<Vec<LocalType<T>>>`)
+/// is bad, because the only local type with `T` as a subtree is
+/// `LocalType<T>`, and `Vec<->` is between it and the type parameter.
+/// - similarly, `FundamentalPair<LocalType<T>, T>` is bad, because
+/// the second occurence of `T` is not a subtree of *any* local type.
+/// - however, `LocalType<Vec<T>>` is OK, because `T` is a subtree of
+/// `LocalType<Vec<T>>`, which is local and has no types between it and
+/// the type parameter.
+///
+/// The orphan rules actually serve several different purposes:
+///
+/// 1. They enable link-safety - i.e. 2 mutually-unknowing crates (where
+/// every type local to one crate is unknown in the other) can't implement
+/// the same trait-ref. This follows because it can be seen that no such
+/// type can orphan-check in 2 such crates.
+///
+/// To check that a local impl follows the orphan rules, we check it in
+/// InCrate::Local mode, using type parameters for the "generic" types.
+///
+/// 2. They ground negative reasoning for coherence. If a user wants to
+/// write both a conditional blanket impl and a specific impl, we need to
+/// make sure they do not overlap. For example, if we write
+/// ```
+/// impl<T> IntoIterator for Vec<T>
+/// impl<T: Iterator> IntoIterator for T
+/// ```
+/// We need to be able to prove that `Vec<$0>: !Iterator` for every type $0.
+/// We can observe that this holds in the current crate, but we need to make
+/// sure this will also hold in all unknown crates (both "independent" crates,
+/// which we need for link-safety, and also child crates, because we don't want
+/// child crates to get error for impl conflicts in a *dependency*).
+///
+/// For that, we only allow negative reasoning if, for every assignment to the
+/// inference variables, every unknown crate would get an orphan error if they
+/// try to implement this trait-ref. To check for this, we use InCrate::Remote
+/// mode. That is sound because we already know all the impls from known crates.
+///
+/// 3. For non-#[fundamental] traits, they guarantee that parent crates can
+/// add "non-blanket" impls without breaking negative reasoning in dependent
+/// crates. This is the "rebalancing coherence" (RFC 1023) restriction.
+///
+/// For that, we only a allow crate to perform negative reasoning on
+/// non-local-non-#[fundamental] only if there's a local key parameter as per (2).
+///
+/// Because we never perform negative reasoning generically (coherence does
+/// not involve type parameters), this can be interpreted as doing the full
+/// orphan check (using InCrate::Local mode), substituting non-local known
+/// types for all inference variables.
+///
+/// This allows for crates to future-compatibly add impls as long as they
+/// can't apply to types with a key parameter in a child crate - applying
+/// the rules, this basically means that every type parameter in the impl
+/// must appear behind a non-fundamental type (because this is not a
+/// type-system requirement, crate owners might also go for "semantic
+/// future-compatibility" involving things such as sealed traits, but
+/// the above requirement is sufficient, and is necessary in "open world"
+/// cases).
+///
+/// Note that this function is never called for types that have both type
+/// parameters and inference variables.
fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt,
trait_ref: ty::TraitRef<'tcx>,
- infer_is_local: InferIsLocal)
+ in_crate: InCrate)
-> Result<(), OrphanCheckErr<'tcx>>
{
- debug!("orphan_check_trait_ref(trait_ref={:?}, infer_is_local={})",
- trait_ref, infer_is_local.0);
+ debug!("orphan_check_trait_ref(trait_ref={:?}, in_crate={:?})",
+ trait_ref, in_crate);
+
+ if trait_ref.needs_infer() && trait_ref.needs_subst() {
+ bug!("can't orphan check a trait ref with both params and inference variables {:?}",
+ trait_ref);
+ }
// First, create an ordered iterator over all the type parameters to the trait, with the self
// type appearing first.
// Find the first input type that either references a type parameter OR
// some local type.
for input_ty in trait_ref.input_types() {
- if ty_is_local(tcx, input_ty, infer_is_local) {
+ if ty_is_local(tcx, input_ty, in_crate) {
debug!("orphan_check_trait_ref: ty_is_local `{:?}`", input_ty);
// First local input type. Check that there are no
// uncovered type parameters.
- let uncovered_tys = uncovered_tys(tcx, input_ty, infer_is_local);
+ let uncovered_tys = uncovered_tys(tcx, input_ty, in_crate);
for uncovered_ty in uncovered_tys {
- if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) {
+ if let Some(param) = uncovered_ty.walk()
+ .find(|t| is_possibly_remote_type(t, in_crate))
+ {
debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
return Err(OrphanCheckErr::UncoveredTy(param));
}
// Otherwise, enforce invariant that there are no type
// parameters reachable.
- if !infer_is_local.0 {
- if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) {
- debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
- return Err(OrphanCheckErr::UncoveredTy(param));
- }
+ if let Some(param) = input_ty.walk()
+ .find(|t| is_possibly_remote_type(t, in_crate))
+ {
+ debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
+ return Err(OrphanCheckErr::UncoveredTy(param));
}
}
return Err(OrphanCheckErr::NoLocalInputType);
}
-fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, infer_is_local: InferIsLocal)
+fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, in_crate: InCrate)
-> Vec<Ty<'tcx>> {
- if ty_is_local_constructor(ty, infer_is_local) {
+ if ty_is_local_constructor(ty, in_crate) {
vec![]
} else if fundamental_ty(tcx, ty) {
ty.walk_shallow()
- .flat_map(|t| uncovered_tys(tcx, t, infer_is_local))
+ .flat_map(|t| uncovered_tys(tcx, t, in_crate))
.collect()
} else {
vec![ty]
}
}
-fn is_type_parameter(ty: Ty) -> bool {
+fn is_possibly_remote_type(ty: Ty, _in_crate: InCrate) -> bool {
match ty.sty {
ty::TyProjection(..) | ty::TyParam(..) => true,
_ => false,
}
}
-fn ty_is_local(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal) -> bool {
- ty_is_local_constructor(ty, infer_is_local) ||
- fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, infer_is_local))
+fn ty_is_local(tcx: TyCtxt, ty: Ty, in_crate: InCrate) -> bool {
+ ty_is_local_constructor(ty, in_crate) ||
+ fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, in_crate))
}
fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool {
}
}
-fn ty_is_local_constructor(ty: Ty, infer_is_local: InferIsLocal)-> bool {
+fn def_id_is_local(def_id: DefId, in_crate: InCrate) -> bool {
+ match in_crate {
+ // The type is local to *this* crate - it will not be
+ // local in any other crate.
+ InCrate::Remote => false,
+ InCrate::Local => def_id.is_local()
+ }
+}
+
+fn ty_is_local_constructor(ty: Ty, in_crate: InCrate) -> bool {
debug!("ty_is_local_constructor({:?})", ty);
match ty.sty {
false
}
- ty::TyInfer(..) => {
- infer_is_local.0
- }
-
- ty::TyAdt(def, _) => {
- def.did.is_local()
- }
+ ty::TyInfer(..) => match in_crate {
+ InCrate::Local => false,
+ // The inference variable might be unified with a local
+ // type in that remote crate.
+ InCrate::Remote => true,
+ },
- ty::TyForeign(did) => {
- did.is_local()
- }
+ ty::TyAdt(def, _) => def_id_is_local(def.did, in_crate),
+ ty::TyForeign(did) => def_id_is_local(did, in_crate),
ty::TyDynamic(ref tt, ..) => {
- tt.principal().map_or(false, |p| p.def_id().is_local())
+ tt.principal().map_or(false, |p| {
+ def_id_is_local(p.def_id(), in_crate)
+ })
}
ty::TyError => {
projects / rust.git / blobdiff