src/librustc/traits/coherence.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! See `README.md` for high-level documentation
  12
  13 use hir::def_id::{DefId, LOCAL_CRATE};
  14 use syntax_pos::DUMMY_SP;
  15 use traits::{self, Normalized, SelectionContext, Obligation, ObligationCause, Reveal};
  16 use traits::IntercrateMode;
  17 use traits::select::IntercrateAmbiguityCause;
  18 use ty::{self, Ty, TyCtxt};
  19 use ty::fold::TypeFoldable;
  20 use ty::subst::Subst;
  21
  22 use infer::{InferCtxt, InferOk};
  23
  24 /// Whether we do the orphan check relative to this crate or
  25 /// to some remote crate.
  26 #[derive(Copy, Clone, Debug)]
  27 enum InCrate {
  28     Local,
  29     Remote
  30 }
  31
  32 #[derive(Debug, Copy, Clone)]
  33 pub enum Conflict {
  34     Upstream,
  35     Downstream { used_to_be_broken: bool }
  36 }
  37
  38 pub struct OverlapResult<'tcx> {
  39     pub impl_header: ty::ImplHeader<'tcx>,
  40     pub intercrate_ambiguity_causes: Vec<IntercrateAmbiguityCause>,
  41 }
  42
  43 /// If there are types that satisfy both impls, returns a suitably-freshened
  44 /// `ImplHeader` with those types substituted
  45 pub fn overlapping_impls<'cx, 'gcx, 'tcx>(infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
  46                                           impl1_def_id: DefId,
  47                                           impl2_def_id: DefId,
  48                                           intercrate_mode: IntercrateMode)
  49                                           -> Option<OverlapResult<'tcx>>
  50 {
  51     debug!("impl_can_satisfy(\
  52            impl1_def_id={:?}, \
  53            impl2_def_id={:?},
  54            intercrate_mode={:?})",
  55            impl1_def_id,
  56            impl2_def_id,
  57            intercrate_mode);
  58
  59     let selcx = &mut SelectionContext::intercrate(infcx, intercrate_mode);
  60     overlap(selcx, impl1_def_id, impl2_def_id)
  61 }
  62
  63 fn with_fresh_ty_vars<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
  64                                        param_env: ty::ParamEnv<'tcx>,
  65                                        impl_def_id: DefId)
  66                                        -> ty::ImplHeader<'tcx>
  67 {
  68     let tcx = selcx.tcx();
  69     let impl_substs = selcx.infcx().fresh_substs_for_item(DUMMY_SP, impl_def_id);
  70
  71     let header = ty::ImplHeader {
  72         impl_def_id,
  73         self_ty: tcx.type_of(impl_def_id),
  74         trait_ref: tcx.impl_trait_ref(impl_def_id),
  75         predicates: tcx.predicates_of(impl_def_id).predicates
  76     }.subst(tcx, impl_substs);
  77
  78     let Normalized { value: mut header, obligations } =
  79         traits::normalize(selcx, param_env, ObligationCause::dummy(), &header);
  80
  81     header.predicates.extend(obligations.into_iter().map(|o| o.predicate));
  82     header
  83 }
  84
  85 /// Can both impl `a` and impl `b` be satisfied by a common type (including
  86 /// `where` clauses)? If so, returns an `ImplHeader` that unifies the two impls.
  87 fn overlap<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
  88                             a_def_id: DefId,
  89                             b_def_id: DefId)
  90                             -> Option<OverlapResult<'tcx>>
  91 {
  92     debug!("overlap(a_def_id={:?}, b_def_id={:?})",
  93            a_def_id,
  94            b_def_id);
  95
  96     // For the purposes of this check, we don't bring any skolemized
  97     // types into scope; instead, we replace the generic types with
  98     // fresh type variables, and hence we do our evaluations in an
  99     // empty environment.
 100     let param_env = ty::ParamEnv::empty(Reveal::UserFacing);
 101
 102     let a_impl_header = with_fresh_ty_vars(selcx, param_env, a_def_id);
 103     let b_impl_header = with_fresh_ty_vars(selcx, param_env, b_def_id);
 104
 105     debug!("overlap: a_impl_header={:?}", a_impl_header);
 106     debug!("overlap: b_impl_header={:?}", b_impl_header);
 107
 108     // Do `a` and `b` unify? If not, no overlap.
 109     let obligations = match selcx.infcx().at(&ObligationCause::dummy(), param_env)
 110                                          .eq_impl_headers(&a_impl_header, &b_impl_header) {
 111         Ok(InferOk { obligations, value: () }) => {
 112             obligations
 113         }
 114         Err(_) => return None
 115     };
 116
 117     debug!("overlap: unification check succeeded");
 118
 119     // Are any of the obligations unsatisfiable? If so, no overlap.
 120     let infcx = selcx.infcx();
 121     let opt_failing_obligation =
 122         a_impl_header.predicates
 123                      .iter()
 124                      .chain(&b_impl_header.predicates)
 125                      .map(|p| infcx.resolve_type_vars_if_possible(p))
 126                      .map(|p| Obligation { cause: ObligationCause::dummy(),
 127                                            param_env,
 128                                            recursion_depth: 0,
 129                                            predicate: p })
 130                      .chain(obligations)
 131                      .find(|o| !selcx.evaluate_obligation(o));
 132
 133     if let Some(failing_obligation) = opt_failing_obligation {
 134         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
 135         return None
 136     }
 137
 138     Some(OverlapResult {
 139         impl_header: selcx.infcx().resolve_type_vars_if_possible(&a_impl_header),
 140         intercrate_ambiguity_causes: selcx.intercrate_ambiguity_causes().to_vec(),
 141     })
 142 }
 143
 144 pub fn trait_ref_is_knowable<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 145                                              trait_ref: ty::TraitRef<'tcx>)
 146                                              -> Option<Conflict>
 147 {
 148     debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref);
 149     if orphan_check_trait_ref(tcx, trait_ref, InCrate::Remote).is_ok() {
 150         // A downstream or cousin crate is allowed to implement some
 151         // substitution of this trait-ref.
 152
 153         // A trait can be implementable for a trait ref by both the current
 154         // crate and crates downstream of it. Older versions of rustc
 155         // were not aware of this, causing incoherence (issue #43355).
 156         let used_to_be_broken =
 157             orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok();
 158         if used_to_be_broken {
 159             debug!("trait_ref_is_knowable({:?}) - USED TO BE BROKEN", trait_ref);
 160         }
 161         return Some(Conflict::Downstream { used_to_be_broken });
 162     }
 163
 164     if trait_ref_is_local_or_fundamental(tcx, trait_ref) {
 165         // This is a local or fundamental trait, so future-compatibility
 166         // is no concern. We know that downstream/cousin crates are not
 167         // allowed to implement a substitution of this trait ref, which
 168         // means impls could only come from dependencies of this crate,
 169         // which we already know about.
 170         return None;
 171     }
 172
 173     // This is a remote non-fundamental trait, so if another crate
 174     // can be the "final owner" of a substitution of this trait-ref,
 175     // they are allowed to implement it future-compatibly.
 176     //
 177     // However, if we are a final owner, then nobody else can be,
 178     // and if we are an intermediate owner, then we don't care
 179     // about future-compatibility, which means that we're OK if
 180     // we are an owner.
 181     if orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok() {
 182         debug!("trait_ref_is_knowable: orphan check passed");
 183         return None;
 184     } else {
 185         debug!("trait_ref_is_knowable: nonlocal, nonfundamental, unowned");
 186         return Some(Conflict::Upstream);
 187     }
 188 }
 189
 190 pub fn trait_ref_is_local_or_fundamental<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 191                                                          trait_ref: ty::TraitRef<'tcx>)
 192                                                          -> bool {
 193     trait_ref.def_id.krate == LOCAL_CRATE || tcx.has_attr(trait_ref.def_id, "fundamental")
 194 }
 195
 196 pub enum OrphanCheckErr<'tcx> {
 197     NoLocalInputType,
 198     UncoveredTy(Ty<'tcx>),
 199 }
 200
 201 /// Checks the coherence orphan rules. `impl_def_id` should be the
 202 /// def-id of a trait impl. To pass, either the trait must be local, or else
 203 /// two conditions must be satisfied:
 204 ///
 205 /// 1. All type parameters in `Self` must be "covered" by some local type constructor.
 206 /// 2. Some local type must appear in `Self`.
 207 pub fn orphan_check<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 208                                     impl_def_id: DefId)
 209                                     -> Result<(), OrphanCheckErr<'tcx>>
 210 {
 211     debug!("orphan_check({:?})", impl_def_id);
 212
 213     // We only except this routine to be invoked on implementations
 214     // of a trait, not inherent implementations.
 215     let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
 216     debug!("orphan_check: trait_ref={:?}", trait_ref);
 217
 218     // If the *trait* is local to the crate, ok.
 219     if trait_ref.def_id.is_local() {
 220         debug!("trait {:?} is local to current crate",
 221                trait_ref.def_id);
 222         return Ok(());
 223     }
 224
 225     orphan_check_trait_ref(tcx, trait_ref, InCrate::Local)
 226 }
 227
 228 /// Check whether a trait-ref is potentially implementable by a crate.
 229 ///
 230 /// The current rule is that a trait-ref orphan checks in a crate C:
 231 ///
 232 /// 1. Order the parameters in the trait-ref in subst order - Self first,
 233 ///    others linearly (e.g. `<U as Foo<V, W>>` is U < V < W).
 234 /// 2. Of these type parameters, there is at least one type parameter
 235 ///    in which, walking the type as a tree, you can reach a type local
 236 ///    to C where all types in-between are fundamental types. Call the
 237 ///    first such parameter the "local key parameter".
 238 ///     - e.g. `Box<LocalType>` is OK, because you can visit LocalType
 239 ///       going through `Box`, which is fundamental.
 240 ///     - similarly, `FundamentalPair<Vec<()>, Box<LocalType>>` is OK for
 241 ///       the same reason.
 242 ///     - but (knowing that `Vec<T>` is non-fundamental, and assuming it's
 243 ///       not local), `Vec<LocalType>` is bad, because `Vec<->` is between
 244 ///       the local type and the type parameter.
 245 /// 3. Every type parameter before the local key parameter is fully known in C.
 246 ///     - e.g. `impl<T> T: Trait<LocalType>` is bad, because `T` might be
 247 ///       an unknown type.
 248 ///     - but `impl<T> LocalType: Trait<T>` is OK, because `LocalType`
 249 ///       occurs before `T`.
 250 /// 4. Every type in the local key parameter not known in C, going
 251 ///    through the parameter's type tree, must appear only as a subtree of
 252 ///    a type local to C, with only fundamental types between the type
 253 ///    local to C and the local key parameter.
 254 ///     - e.g. `Vec<LocalType<T>>>` (or equivalently `Box<Vec<LocalType<T>>>`)
 255 ///     is bad, because the only local type with `T` as a subtree is
 256 ///     `LocalType<T>`, and `Vec<->` is between it and the type parameter.
 257 ///     - similarly, `FundamentalPair<LocalType<T>, T>` is bad, because
 258 ///     the second occurence of `T` is not a subtree of *any* local type.
 259 ///     - however, `LocalType<Vec<T>>` is OK, because `T` is a subtree of
 260 ///     `LocalType<Vec<T>>`, which is local and has no types between it and
 261 ///     the type parameter.
 262 ///
 263 /// The orphan rules actually serve several different purposes:
 264 ///
 265 /// 1. They enable link-safety - i.e. 2 mutually-unknowing crates (where
 266 ///    every type local to one crate is unknown in the other) can't implement
 267 ///    the same trait-ref. This follows because it can be seen that no such
 268 ///    type can orphan-check in 2 such crates.
 269 ///
 270 ///    To check that a local impl follows the orphan rules, we check it in
 271 ///    InCrate::Local mode, using type parameters for the "generic" types.
 272 ///
 273 /// 2. They ground negative reasoning for coherence. If a user wants to
 274 ///    write both a conditional blanket impl and a specific impl, we need to
 275 ///    make sure they do not overlap. For example, if we write
 276 ///    ```
 277 ///    impl<T> IntoIterator for Vec<T>
 278 ///    impl<T: Iterator> IntoIterator for T
 279 ///    ```
 280 ///    We need to be able to prove that `Vec<$0>: !Iterator` for every type $0.
 281 ///    We can observe that this holds in the current crate, but we need to make
 282 ///    sure this will also hold in all unknown crates (both "independent" crates,
 283 ///    which we need for link-safety, and also child crates, because we don't want
 284 ///    child crates to get error for impl conflicts in a *dependency*).
 285 ///
 286 ///    For that, we only allow negative reasoning if, for every assignment to the
 287 ///    inference variables, every unknown crate would get an orphan error if they
 288 ///    try to implement this trait-ref. To check for this, we use InCrate::Remote
 289 ///    mode. That is sound because we already know all the impls from known crates.
 290 ///
 291 /// 3. For non-#[fundamental] traits, they guarantee that parent crates can
 292 ///    add "non-blanket" impls without breaking negative reasoning in dependent
 293 ///    crates. This is the "rebalancing coherence" (RFC 1023) restriction.
 294 ///
 295 ///    For that, we only a allow crate to perform negative reasoning on
 296 ///    non-local-non-#[fundamental] only if there's a local key parameter as per (2).
 297 ///
 298 ///    Because we never perform negative reasoning generically (coherence does
 299 ///    not involve type parameters), this can be interpreted as doing the full
 300 ///    orphan check (using InCrate::Local mode), substituting non-local known
 301 ///    types for all inference variables.
 302 ///
 303 ///    This allows for crates to future-compatibly add impls as long as they
 304 ///    can't apply to types with a key parameter in a child crate - applying
 305 ///    the rules, this basically means that every type parameter in the impl
 306 ///    must appear behind a non-fundamental type (because this is not a
 307 ///    type-system requirement, crate owners might also go for "semantic
 308 ///    future-compatibility" involving things such as sealed traits, but
 309 ///    the above requirement is sufficient, and is necessary in "open world"
 310 ///    cases).
 311 ///
 312 /// Note that this function is never called for types that have both type
 313 /// parameters and inference variables.
 314 fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt,
 315                                 trait_ref: ty::TraitRef<'tcx>,
 316                                 in_crate: InCrate)
 317                                 -> Result<(), OrphanCheckErr<'tcx>>
 318 {
 319     debug!("orphan_check_trait_ref(trait_ref={:?}, in_crate={:?})",
 320            trait_ref, in_crate);
 321
 322     if trait_ref.needs_infer() && trait_ref.needs_subst() {
 323         bug!("can't orphan check a trait ref with both params and inference variables {:?}",
 324              trait_ref);
 325     }
 326
 327     // First, create an ordered iterator over all the type parameters to the trait, with the self
 328     // type appearing first.
 329     // Find the first input type that either references a type parameter OR
 330     // some local type.
 331     for input_ty in trait_ref.input_types() {
 332         if ty_is_local(tcx, input_ty, in_crate) {
 333             debug!("orphan_check_trait_ref: ty_is_local `{:?}`", input_ty);
 334
 335             // First local input type. Check that there are no
 336             // uncovered type parameters.
 337             let uncovered_tys = uncovered_tys(tcx, input_ty, in_crate);
 338             for uncovered_ty in uncovered_tys {
 339                 if let Some(param) = uncovered_ty.walk()
 340                     .find(|t| is_possibly_remote_type(t, in_crate))
 341                 {
 342                     debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
 343                     return Err(OrphanCheckErr::UncoveredTy(param));
 344                 }
 345             }
 346
 347             // OK, found local type, all prior types upheld invariant.
 348             return Ok(());
 349         }
 350
 351         // Otherwise, enforce invariant that there are no type
 352         // parameters reachable.
 353         if let Some(param) = input_ty.walk()
 354             .find(|t| is_possibly_remote_type(t, in_crate))
 355         {
 356             debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
 357             return Err(OrphanCheckErr::UncoveredTy(param));
 358         }
 359     }
 360
 361     // If we exit above loop, never found a local type.
 362     debug!("orphan_check_trait_ref: no local type");
 363     return Err(OrphanCheckErr::NoLocalInputType);
 364 }
 365
 366 fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, in_crate: InCrate)
 367                        -> Vec<Ty<'tcx>> {
 368     if ty_is_local_constructor(ty, in_crate) {
 369         vec![]
 370     } else if fundamental_ty(tcx, ty) {
 371         ty.walk_shallow()
 372           .flat_map(|t| uncovered_tys(tcx, t, in_crate))
 373           .collect()
 374     } else {
 375         vec![ty]
 376     }
 377 }
 378
 379 fn is_possibly_remote_type(ty: Ty, _in_crate: InCrate) -> bool {
 380     match ty.sty {
 381         ty::TyProjection(..) | ty::TyParam(..) => true,
 382         _ => false,
 383     }
 384 }
 385
 386 fn ty_is_local(tcx: TyCtxt, ty: Ty, in_crate: InCrate) -> bool {
 387     ty_is_local_constructor(ty, in_crate) ||
 388         fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, in_crate))
 389 }
 390
 391 fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool {
 392     match ty.sty {
 393         ty::TyRef(..) => true,
 394         ty::TyAdt(def, _) => def.is_fundamental(),
 395         ty::TyDynamic(ref data, ..) => {
 396             data.principal().map_or(false, |p| tcx.has_attr(p.def_id(), "fundamental"))
 397         }
 398         _ => false
 399     }
 400 }
 401
 402 fn def_id_is_local(def_id: DefId, in_crate: InCrate) -> bool {
 403     match in_crate {
 404         // The type is local to *this* crate - it will not be
 405         // local in any other crate.
 406         InCrate::Remote => false,
 407         InCrate::Local => def_id.is_local()
 408     }
 409 }
 410
 411 fn ty_is_local_constructor(ty: Ty, in_crate: InCrate) -> bool {
 412     debug!("ty_is_local_constructor({:?})", ty);
 413
 414     match ty.sty {
 415         ty::TyBool |
 416         ty::TyChar |
 417         ty::TyInt(..) |
 418         ty::TyUint(..) |
 419         ty::TyFloat(..) |
 420         ty::TyStr |
 421         ty::TyFnDef(..) |
 422         ty::TyFnPtr(_) |
 423         ty::TyArray(..) |
 424         ty::TySlice(..) |
 425         ty::TyRawPtr(..) |
 426         ty::TyRef(..) |
 427         ty::TyNever |
 428         ty::TyTuple(..) |
 429         ty::TyParam(..) |
 430         ty::TyProjection(..) => {
 431             false
 432         }
 433
 434         ty::TyInfer(..) => match in_crate {
 435             InCrate::Local => false,
 436             // The inference variable might be unified with a local
 437             // type in that remote crate.
 438             InCrate::Remote => true,
 439         },
 440
 441         ty::TyAdt(def, _) => def_id_is_local(def.did, in_crate),
 442         ty::TyForeign(did) => def_id_is_local(did, in_crate),
 443
 444         ty::TyDynamic(ref tt, ..) => {
 445             tt.principal().map_or(false, |p| {
 446                 def_id_is_local(p.def_id(), in_crate)
 447             })
 448         }
 449
 450         ty::TyError => {
 451             true
 452         }
 453
 454         ty::TyClosure(..) | ty::TyGenerator(..) | ty::TyAnon(..) => {
 455             bug!("ty_is_local invoked on unexpected type: {:?}", ty)
 456         }
 457     }
 458 }