src/librustc/traits/specialize/mod.rs

   1 // Copyright 2015 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 // Logic and data structures related to impl specialization, explained in
  12 // greater detail below.
  13 //
  14 // At the moment, this implementation support only the simple "chain" rule:
  15 // If any two impls overlap, one must be a strict subset of the other.
  16 //
  17 // See traits/README.md for a bit more detail on how specialization
  18 // fits together with the rest of the trait machinery.
  19
  20 use super::{SelectionContext, FulfillmentContext};
  21 use super::util::{fresh_type_vars_for_impl, impl_trait_ref_and_oblig};
  22
  23 use rustc_data_structures::fnv::FnvHashMap;
  24 use hir::def_id::DefId;
  25 use infer::{InferCtxt, TypeOrigin};
  26 use middle::region;
  27 use ty::subst::{Subst, Substs};
  28 use traits::{self, Reveal, ObligationCause, Normalized};
  29 use ty::{self, TyCtxt};
  30 use syntax_pos::DUMMY_SP;
  31
  32 pub mod specialization_graph;
  33
  34 /// Information pertinent to an overlapping impl error.
  35 pub struct OverlapError {
  36     pub with_impl: DefId,
  37     pub trait_desc: String,
  38     pub self_desc: Option<String>
  39 }
  40
  41 /// Given a subst for the requested impl, translate it to a subst
  42 /// appropriate for the actual item definition (whether it be in that impl,
  43 /// a parent impl, or the trait).
  44 /// When we have selected one impl, but are actually using item definitions from
  45 /// a parent impl providing a default, we need a way to translate between the
  46 /// type parameters of the two impls. Here the `source_impl` is the one we've
  47 /// selected, and `source_substs` is a substitution of its generics (and
  48 /// possibly some relevant `FnSpace` variables as well). And `target_node` is
  49 /// the impl/trait we're actually going to get the definition from. The resulting
  50 /// substitution will map from `target_node`'s generics to `source_impl`'s
  51 /// generics as instantiated by `source_subst`.
  52 ///
  53 /// For example, consider the following scenario:
  54 ///
  55 /// ```rust
  56 /// trait Foo { ... }
  57 /// impl<T, U> Foo for (T, U) { ... }  // target impl
  58 /// impl<V> Foo for (V, V) { ... }     // source impl
  59 /// ```
  60 ///
  61 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
  62 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
  63 ///
  64 /// Where clauses add some trickiness here, because they can be used to "define"
  65 /// an argument indirectly:
  66 ///
  67 /// ```rust
  68 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
  69 ///    where I: Iterator<Item=&'a T>, T: Clone
  70 /// ```
  71 ///
  72 /// In a case like this, the substitution for `T` is determined indirectly,
  73 /// through associated type projection. We deal with such cases by using
  74 /// *fulfillment* to relate the two impls, requiring that all projections are
  75 /// resolved.
  76 pub fn translate_substs<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  77                                         source_impl: DefId,
  78                                         source_substs: &'tcx Substs<'tcx>,
  79                                         target_node: specialization_graph::Node)
  80                                         -> &'tcx Substs<'tcx> {
  81     let source_trait_ref = infcx.tcx
  82                                 .impl_trait_ref(source_impl)
  83                                 .unwrap()
  84                                 .subst(infcx.tcx, &source_substs);
  85
  86     // translate the Self and TyParam parts of the substitution, since those
  87     // vary across impls
  88     let target_substs = match target_node {
  89         specialization_graph::Node::Impl(target_impl) => {
  90             // no need to translate if we're targetting the impl we started with
  91             if source_impl == target_impl {
  92                 return source_substs;
  93             }
  94
  95             fulfill_implication(infcx, source_trait_ref, target_impl).unwrap_or_else(|_| {
  96                 bug!("When translating substitutions for specialization, the expected \
  97                       specializaiton failed to hold")
  98             })
  99         }
 100         specialization_graph::Node::Trait(..) => source_trait_ref.substs,
 101     };
 102
 103     // directly inherent the method generics, since those do not vary across impls
 104     infcx.tcx.mk_substs(target_substs.with_method_from_subst(source_substs))
 105 }
 106
 107 /// Is impl1 a specialization of impl2?
 108 ///
 109 /// Specialization is determined by the sets of types to which the impls apply;
 110 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 111 /// to.
 112 pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 113                              impl1_def_id: DefId,
 114                              impl2_def_id: DefId) -> bool {
 115     if let Some(r) = tcx.specializes_cache.borrow().check(impl1_def_id, impl2_def_id) {
 116         return r;
 117     }
 118
 119     // The feature gate should prevent introducing new specializations, but not
 120     // taking advantage of upstream ones.
 121     if !tcx.sess.features.borrow().specialization &&
 122         (impl1_def_id.is_local() || impl2_def_id.is_local()) {
 123         return false;
 124     }
 125
 126     // We determine whether there's a subset relationship by:
 127     //
 128     // - skolemizing impl1,
 129     // - assuming the where clauses for impl1,
 130     // - instantiating impl2 with fresh inference variables,
 131     // - unifying,
 132     // - attempting to prove the where clauses for impl2
 133     //
 134     // The last three steps are encapsulated in `fulfill_implication`.
 135     //
 136     // See RFC 1210 for more details and justification.
 137
 138     // Currently we do not allow e.g. a negative impl to specialize a positive one
 139     if tcx.trait_impl_polarity(impl1_def_id) != tcx.trait_impl_polarity(impl2_def_id) {
 140         return false;
 141     }
 142
 143     // create a parameter environment corresponding to a (skolemized) instantiation of impl1
 144     let scheme = tcx.lookup_item_type(impl1_def_id);
 145     let predicates = tcx.lookup_predicates(impl1_def_id);
 146     let mut penv = tcx.construct_parameter_environment(DUMMY_SP,
 147                                                        &scheme.generics,
 148                                                        &predicates,
 149                                                        region::DUMMY_CODE_EXTENT);
 150     let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id)
 151                              .unwrap()
 152                              .subst(tcx, &penv.free_substs);
 153
 154     let result = tcx.normalizing_infer_ctxt(Reveal::ExactMatch).enter(|mut infcx| {
 155         // Normalize the trait reference, adding any obligations
 156         // that arise into the impl1 assumptions.
 157         let Normalized { value: impl1_trait_ref, obligations: normalization_obligations } = {
 158             let selcx = &mut SelectionContext::new(&infcx);
 159             traits::normalize(selcx, ObligationCause::dummy(), &impl1_trait_ref)
 160         };
 161         penv.caller_bounds.extend(normalization_obligations.into_iter().map(|o| {
 162             match tcx.lift_to_global(&o.predicate) {
 163                 Some(predicate) => predicate,
 164                 None => {
 165                     bug!("specializes: obligation `{:?}` has inference types/regions", o);
 166                 }
 167             }
 168         }));
 169
 170         // Install the parameter environment, taking the predicates of impl1 as assumptions:
 171         infcx.parameter_environment = penv;
 172
 173         // Attempt to prove that impl2 applies, given all of the above.
 174         fulfill_implication(&infcx, impl1_trait_ref, impl2_def_id).is_ok()
 175     });
 176
 177     tcx.specializes_cache.borrow_mut().insert(impl1_def_id, impl2_def_id, result);
 178     result
 179 }
 180
 181 /// Attempt to fulfill all obligations of `target_impl` after unification with
 182 /// `source_trait_ref`. If successful, returns a substitution for *all* the
 183 /// generics of `target_impl`, including both those needed to unify with
 184 /// `source_trait_ref` and those whose identity is determined via a where
 185 /// clause in the impl.
 186 fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 187                                        source_trait_ref: ty::TraitRef<'tcx>,
 188                                        target_impl: DefId)
 189                                        -> Result<&'tcx Substs<'tcx>, ()> {
 190     let selcx = &mut SelectionContext::new(&infcx);
 191     let target_substs = fresh_type_vars_for_impl(&infcx, DUMMY_SP, target_impl);
 192     let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
 193                                                                    target_impl,
 194                                                                    &target_substs);
 195
 196     // do the impls unify? If not, no specialization.
 197     if let Err(_) = infcx.eq_trait_refs(true,
 198                                         TypeOrigin::Misc(DUMMY_SP),
 199                                         source_trait_ref,
 200                                         target_trait_ref) {
 201         debug!("fulfill_implication: {:?} does not unify with {:?}",
 202                source_trait_ref,
 203                target_trait_ref);
 204         return Err(());
 205     }
 206
 207     // attempt to prove all of the predicates for impl2 given those for impl1
 208     // (which are packed up in penv)
 209
 210     let mut fulfill_cx = FulfillmentContext::new();
 211     for oblig in obligations.into_iter() {
 212         fulfill_cx.register_predicate_obligation(&infcx, oblig);
 213     }
 214
 215     if let Err(errors) = infcx.drain_fulfillment_cx(&mut fulfill_cx, &()) {
 216         // no dice!
 217         debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
 218                 {:?}",
 219                source_trait_ref,
 220                target_trait_ref,
 221                errors,
 222                infcx.parameter_environment.caller_bounds);
 223         Err(())
 224     } else {
 225         debug!("fulfill_implication: an impl for {:?} specializes {:?}",
 226                source_trait_ref,
 227                target_trait_ref);
 228
 229         // Now resolve the *substitution* we built for the target earlier, replacing
 230         // the inference variables inside with whatever we got from fulfillment.
 231         Ok(infcx.resolve_type_vars_if_possible(&target_substs))
 232     }
 233 }
 234
 235 pub struct SpecializesCache {
 236     map: FnvHashMap<(DefId, DefId), bool>
 237 }
 238
 239 impl SpecializesCache {
 240     pub fn new() -> Self {
 241         SpecializesCache {
 242             map: FnvHashMap()
 243         }
 244     }
 245
 246     pub fn check(&self, a: DefId, b: DefId) -> Option<bool> {
 247         self.map.get(&(a, b)).cloned()
 248     }
 249
 250     pub fn insert(&mut self, a: DefId, b: DefId, result: bool) {
 251         self.map.insert((a, b), result);
 252     }
 253 }