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