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::{build_selcx, SelectionContext, FulfillmentContext};
  21 use super::util::{fresh_type_vars_for_impl, impl_trait_ref_and_oblig};
  22
  23 use middle::cstore::CrateStore;
  24 use middle::def_id::DefId;
  25 use middle::infer::{self, InferCtxt, TypeOrigin};
  26 use middle::region;
  27 use middle::subst::{Subst, Substs};
  28 use middle::traits;
  29 use middle::ty;
  30 use syntax::codemap::DUMMY_SP;
  31
  32 pub mod specialization_graph;
  33
  34 /// Information pertinent to an overlapping impl error.
  35 pub struct Overlap<'a, 'tcx: 'a> {
  36     pub in_context: InferCtxt<'a, 'tcx>,
  37     pub with_impl: DefId,
  38     pub on_trait_ref: ty::TraitRef<'tcx>,
  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, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
  77                                   source_impl: DefId,
  78                                   source_substs: Substs<'tcx>,
  79                                   target_node: specialization_graph::Node)
  80                                   -> Substs<'tcx>
  81 {
  82     let source_trait_ref = infcx.tcx
  83                                 .impl_trait_ref(source_impl)
  84                                 .unwrap()
  85                                 .subst(infcx.tcx, &source_substs);
  86
  87     // translate the Self and TyParam parts of the substitution, since those
  88     // vary across impls
  89     let target_substs = match target_node {
  90         specialization_graph::Node::Impl(target_impl) => {
  91             // no need to translate if we're targetting the impl we started with
  92             if source_impl == target_impl {
  93                 return source_substs;
  94             }
  95
  96             fulfill_implication(infcx, source_trait_ref, target_impl).unwrap_or_else(|_| {
  97                 infcx.tcx
  98                      .sess
  99                      .bug("When translating substitutions for specialization, the expected \
 100                            specializaiton failed to hold")
 101             })
 102         }
 103         specialization_graph::Node::Trait(..) => source_trait_ref.substs.clone(),
 104     };
 105
 106     // retain erasure mode
 107     // NB: this must happen before inheriting method generics below
 108     let target_substs = if source_substs.regions.is_erased() {
 109         target_substs.erase_regions()
 110     } else {
 111         target_substs
 112     };
 113
 114     // directly inherent the method generics, since those do not vary across impls
 115     target_substs.with_method_from_subst(&source_substs)
 116 }
 117
 118
 119 fn skolemizing_subst_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
 120                                         impl_def_id: DefId)
 121                                         -> Substs<'tcx>
 122 {
 123     let impl_generics = infcx.tcx.lookup_item_type(impl_def_id).generics;
 124
 125     let types = impl_generics.types.map(|def| infcx.tcx.mk_param_from_def(def));
 126
 127     // TODO: figure out what we actually want here
 128     let regions = impl_generics.regions.map(|_| ty::Region::ReStatic);
 129     // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name)));
 130
 131     Substs::new(types, regions)
 132 }
 133
 134 /// Is impl1 a specialization of impl2?
 135 ///
 136 /// Specialization is determined by the sets of types to which the impls apply;
 137 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 138 /// to.
 139 pub fn specializes(tcx: &ty::ctxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
 140     if !tcx.sess.features.borrow().specialization {
 141         return false;
 142     }
 143
 144     // We determine whether there's a subset relationship by:
 145     //
 146     // - skolemizing impl1,
 147     // - assuming the where clauses for impl1,
 148     // - instantiating impl2 with fresh inference variables,
 149     // - unifying,
 150     // - attempting to prove the where clauses for impl2
 151     //
 152     // The last three steps are encapsulated in `fulfill_implication`.
 153     //
 154     // See RFC 1210 for more details and justification.
 155
 156     let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables);
 157
 158     // Skiolemize impl1: we want to prove that "for all types matched by impl1,
 159     // those types are also matched by impl2".
 160     let impl1_substs = skolemizing_subst_for_impl(&infcx, impl1_def_id);
 161     let (impl1_trait_ref, impl1_obligations) = {
 162         let selcx = &mut SelectionContext::new(&infcx);
 163         impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs)
 164     };
 165
 166     // Add impl1's obligations as assumptions to the environment.
 167     let impl1_predicates: Vec<_> = impl1_obligations.iter()
 168                                                     .cloned()
 169                                                     .map(|oblig| oblig.predicate)
 170                                                     .collect();
 171     infcx.parameter_environment = ty::ParameterEnvironment {
 172         tcx: tcx,
 173         free_substs: impl1_substs,
 174         implicit_region_bound: ty::ReEmpty, // TODO: is this OK?
 175         caller_bounds: impl1_predicates,
 176         selection_cache: traits::SelectionCache::new(),
 177         evaluation_cache: traits::EvaluationCache::new(),
 178         free_id_outlive: region::DUMMY_CODE_EXTENT, // TODO: is this OK?
 179     };
 180
 181     // Attempt to prove that impl2 applies, given all of the above.
 182     fulfill_implication(&infcx, impl1_trait_ref, impl2_def_id).is_ok()
 183 }
 184
 185 /// Attempt to fulfill all obligations of `target_impl` after unification with
 186 /// `source_trait_ref`. If successful, returns a substitution for *all* the
 187 /// generics of `target_impl`, including both those needed to unify with
 188 /// `source_trait_ref` and those whose identity is determined via a where
 189 /// clause in the impl.
 190 fn fulfill_implication<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
 191                                  source_trait_ref: ty::TraitRef<'tcx>,
 192                                  target_impl: DefId)
 193                                  -> Result<Substs<'tcx>, ()>
 194 {
 195     infcx.probe(|_| {
 196         let selcx = &mut build_selcx(&infcx).project_topmost().build();
 197         let target_substs = fresh_type_vars_for_impl(&infcx, DUMMY_SP, target_impl);
 198         let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
 199                                                                        target_impl,
 200                                                                        &target_substs);
 201
 202         // do the impls unify? If not, no specialization.
 203         if let Err(_) = infer::mk_eq_trait_refs(&infcx,
 204                                                 true,
 205                                                 TypeOrigin::Misc(DUMMY_SP),
 206                                                 source_trait_ref,
 207                                                 target_trait_ref) {
 208             debug!("fulfill_implication: {:?} does not unify with {:?}",
 209                    source_trait_ref,
 210                    target_trait_ref);
 211             return Err(());
 212         }
 213
 214         // attempt to prove all of the predicates for impl2 given those for impl1
 215         // (which are packed up in penv)
 216
 217         let mut fulfill_cx = FulfillmentContext::new();
 218         for oblig in obligations.into_iter() {
 219             fulfill_cx.register_predicate_obligation(&infcx, oblig);
 220         }
 221
 222         if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) {
 223             // no dice!
 224             debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} \
 225                     given {:?}",
 226                    source_trait_ref,
 227                    target_trait_ref,
 228                    errors,
 229                    infcx.parameter_environment.caller_bounds);
 230             Err(())
 231         } else {
 232             debug!("fulfill_implication: an impl for {:?} specializes {:?} (`where` clauses \
 233                     elided)",
 234                    source_trait_ref,
 235                    target_trait_ref);
 236
 237             // Now resolve the *substitution* we built for the target earlier, replacing
 238             // the inference variables inside with whatever we got from fulfillment.
 239
 240             // TODO: should this use `fully_resolve` instead?
 241             Ok(infcx.resolve_type_vars_if_possible(&target_substs))
 242         }
 243     })
 244 }