src/librustc/middle/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::{util, build_selcx, SelectionContext};
  21
  22 use middle::cstore::CrateStore;
  23 use middle::def_id::DefId;
  24 use middle::infer::{self, InferCtxt, TypeOrigin};
  25 use middle::region;
  26 use middle::subst::{Subst, Substs};
  27 use middle::traits;
  28 use middle::ty;
  29 use syntax::codemap::DUMMY_SP;
  30
  31 pub mod specialization_graph;
  32
  33 /// Information pertinent to an overlapping impl error.
  34 pub struct Overlap<'a, 'tcx: 'a> {
  35     pub in_context: InferCtxt<'a, 'tcx>,
  36     pub with_impl: DefId,
  37     pub on_trait_ref: ty::TraitRef<'tcx>,
  38 }
  39
  40 /// Given a subst for the requested impl, translate it to a subst
  41 /// appropriate for the actual item definition (whether it be in that impl,
  42 /// a parent impl, or the trait).
  43 pub fn translate_substs<'tcx>(tcx: &ty::ctxt<'tcx>,
  44                               from_impl: DefId,
  45                               from_impl_substs: Substs<'tcx>,
  46                               to_node: specialization_graph::Node)
  47                               -> Substs<'tcx> {
  48     match to_node {
  49         specialization_graph::Node::Impl(to_impl) => {
  50             // no need to translate if we're targetting the impl we started with
  51             if from_impl == to_impl {
  52                 return from_impl_substs;
  53             }
  54
  55             translate_substs_between_impls(tcx, from_impl, from_impl_substs, to_impl)
  56
  57         }
  58         specialization_graph::Node::Trait(..) => {
  59             translate_substs_from_impl_to_trait(tcx, from_impl, from_impl_substs)
  60         }
  61     }
  62 }
  63
  64 /// When we have selected one impl, but are actually using item definitions from
  65 /// a parent impl providing a default, we need a way to translate between the
  66 /// type parameters of the two impls. Here the `source_impl` is the one we've
  67 /// selected, and `source_substs` is a substitution of its generics (and
  68 /// possibly some relevant `FnSpace` variables as well). And `target_impl` is
  69 /// the impl we're actually going to get the definition from. The resulting
  70 /// substitution will map from `target_impl`'s generics to `source_impl`'s
  71 /// generics as instantiated by `source_subst`.
  72 ///
  73 /// For example, consider the following scenario:
  74 ///
  75 /// ```rust
  76 /// trait Foo { ... }
  77 /// impl<T, U> Foo for (T, U) { ... }  // target impl
  78 /// impl<V> Foo for (V, V) { ... }     // source impl
  79 /// ```
  80 ///
  81 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
  82 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
  83 ///
  84 /// Where clauses add some trickiness here, because they can be used to "define"
  85 /// an argument indirectly:
  86 ///
  87 /// ```rust
  88 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
  89 ///    where I: Iterator<Item=&'a T>, T: Clone
  90 /// ```
  91 ///
  92 /// In a case like this, the substitution for `T` is determined indirectly,
  93 /// through associated type projection. We deal with such cases by using
  94 /// *fulfillment* to relate the two impls, requiring that all projections are
  95 /// resolved.
  96 fn translate_substs_between_impls<'tcx>(tcx: &ty::ctxt<'tcx>,
  97                                         source_impl: DefId,
  98                                         source_substs: Substs<'tcx>,
  99                                         target_impl: DefId)
 100                                         -> Substs<'tcx> {
 101
 102     // We need to build a subst that covers all the generics of
 103     // `target_impl`. Start by introducing fresh infer variables:
 104     let target_generics = tcx.lookup_item_type(target_impl).generics;
 105     let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables);
 106     let mut target_substs = infcx.fresh_substs_for_generics(DUMMY_SP, &target_generics);
 107     if source_substs.regions.is_erased() {
 108         target_substs = target_substs.erase_regions()
 109     }
 110
 111     if !fulfill_implication(&mut infcx,
 112                             source_impl,
 113                             source_substs.clone(),
 114                             target_impl,
 115                             target_substs.clone()) {
 116         tcx.sess
 117            .bug("When translating substitutions for specialization, the expected specializaiton \
 118                  failed to hold")
 119     }
 120
 121     // Now resolve the *substitution* we built for the target earlier, replacing
 122     // the inference variables inside with whatever we got from fulfillment. We
 123     // also carry along any FnSpace substitutions, which don't need to be
 124     // adjusted when mapping from one impl to another.
 125     infcx.resolve_type_vars_if_possible(&target_substs)
 126          .with_method_from_subst(&source_substs)
 127 }
 128
 129 /// When we've selected an impl but need to use an item definition provided by
 130 /// the trait itself, we need to translate the substitution applied to the impl
 131 /// to one that makes sense for the trait.
 132 fn translate_substs_from_impl_to_trait<'tcx>(tcx: &ty::ctxt<'tcx>,
 133                                              source_impl: DefId,
 134                                              source_substs: Substs<'tcx>)
 135                                              -> Substs<'tcx> {
 136
 137     let source_trait_ref = tcx.impl_trait_ref(source_impl).unwrap().subst(tcx, &source_substs);
 138
 139     let mut new_substs = source_trait_ref.substs.clone();
 140     if source_substs.regions.is_erased() {
 141         new_substs = new_substs.erase_regions()
 142     }
 143
 144     // Carry any FnSpace substitutions along; they don't need to be adjusted
 145     new_substs.with_method_from_subst(&source_substs)
 146 }
 147
 148 fn skolemizing_subst_for_impl<'a>(tcx: &ty::ctxt<'a>, impl_def_id: DefId) -> Substs<'a> {
 149     let impl_generics = tcx.lookup_item_type(impl_def_id).generics;
 150
 151     let types = impl_generics.types.map(|def| tcx.mk_param_from_def(def));
 152
 153     // FIXME: figure out what we actually want here
 154     let regions = impl_generics.regions.map(|_| ty::Region::ReStatic);
 155     // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name)));
 156
 157     Substs::new(types, regions)
 158 }
 159
 160 /// Is impl1 a specialization of impl2?
 161 ///
 162 /// Specialization is determined by the sets of types to which the impls apply;
 163 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 164 /// to.
 165 pub fn specializes(tcx: &ty::ctxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
 166     if !tcx.sess.features.borrow().specialization {
 167         return false;
 168     }
 169
 170     // We determine whether there's a subset relationship by:
 171     //
 172     // - skolemizing impl1,
 173     // - instantiating impl2 with fresh inference variables,
 174     // - assuming the where clauses for impl1,
 175     // - unifying,
 176     // - attempting to prove the where clauses for impl2
 177     //
 178     // The last three steps are essentially checking for an implication between two impls
 179     // after appropriate substitutions. This is what `fulfill_implication` checks for.
 180     //
 181     // See RFC 1210 for more details and justification.
 182
 183     let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables);
 184
 185     let impl1_substs = skolemizing_subst_for_impl(tcx, impl1_def_id);
 186     let impl2_substs = util::fresh_type_vars_for_impl(&infcx, DUMMY_SP, impl2_def_id);
 187
 188     fulfill_implication(&mut infcx,
 189                         impl1_def_id,
 190                         impl1_substs,
 191                         impl2_def_id,
 192                         impl2_substs)
 193 }
 194
 195 /// Does impl1 (instantiated with the impl1_substs) imply impl2
 196 /// (instantiated with impl2_substs)?
 197 ///
 198 /// Mutates the `infcx` in two ways:
 199 /// - by adding the obligations of impl1 to the parameter environment
 200 /// - via fulfillment, so that if the implication holds the various unifications
 201 fn fulfill_implication<'a, 'tcx>(infcx: &mut InferCtxt<'a, 'tcx>,
 202                                  impl1_def_id: DefId,
 203                                  impl1_substs: Substs<'tcx>,
 204                                  impl2_def_id: DefId,
 205                                  impl2_substs: Substs<'tcx>)
 206                                  -> bool {
 207     let tcx = &infcx.tcx;
 208
 209     let (impl1_trait_ref, impl1_obligations) = {
 210         let selcx = &mut SelectionContext::new(&infcx);
 211         util::impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs)
 212     };
 213
 214     let impl1_predicates: Vec<_> = impl1_obligations.iter()
 215                                                     .cloned()
 216                                                     .map(|oblig| oblig.predicate)
 217                                                     .collect();
 218
 219     infcx.parameter_environment = ty::ParameterEnvironment {
 220         tcx: tcx,
 221         free_substs: impl1_substs,
 222         implicit_region_bound: ty::ReEmpty, // FIXME: is this OK?
 223         caller_bounds: impl1_predicates,
 224         selection_cache: traits::SelectionCache::new(),
 225         evaluation_cache: traits::EvaluationCache::new(),
 226         free_id_outlive: region::DUMMY_CODE_EXTENT, // FIXME: is this OK?
 227     };
 228
 229     let selcx = &mut build_selcx(&infcx).project_topmost().build();
 230     let (impl2_trait_ref, impl2_obligations) = util::impl_trait_ref_and_oblig(selcx,
 231                                                                               impl2_def_id,
 232                                                                               &impl2_substs);
 233
 234     // do the impls unify? If not, no specialization.
 235     if let Err(_) = infer::mk_eq_trait_refs(&infcx,
 236                                             true,
 237                                             TypeOrigin::Misc(DUMMY_SP),
 238                                             impl1_trait_ref,
 239                                             impl2_trait_ref) {
 240         debug!("fulfill_implication: {:?} does not unify with {:?}",
 241                impl1_trait_ref,
 242                impl2_trait_ref);
 243         return false;
 244     }
 245
 246     let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
 247
 248     // attempt to prove all of the predicates for impl2 given those for impl1
 249     // (which are packed up in penv)
 250
 251     for oblig in impl2_obligations.into_iter() {
 252         fulfill_cx.register_predicate_obligation(&infcx, oblig);
 253     }
 254
 255     if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) {
 256         // no dice!
 257         debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
 258                 {:?}",
 259                impl1_trait_ref,
 260                impl2_trait_ref,
 261                errors,
 262                infcx.parameter_environment.caller_bounds);
 263         false
 264     } else {
 265         debug!("fulfill_implication: an impl for {:?} specializes {:?} (`where` clauses elided)",
 266                impl1_trait_ref,
 267                impl2_trait_ref);
 268         true
 269     }
 270 }