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::impl_trait_ref_and_oblig;
  22
  23 use rustc_data_structures::fx::FxHashMap;
  24 use hir::def_id::DefId;
  25 use infer::{InferCtxt, InferOk};
  26 use middle::region;
  27 use ty::subst::{Subst, Substs};
  28 use traits::{self, Reveal, ObligationCause};
  29 use ty::{self, TyCtxt, TypeFoldable};
  30 use syntax_pos::DUMMY_SP;
  31
  32 use syntax::ast;
  33
  34 pub mod specialization_graph;
  35
  36 /// Information pertinent to an overlapping impl error.
  37 pub struct OverlapError {
  38     pub with_impl: DefId,
  39     pub trait_desc: String,
  40     pub self_desc: Option<String>
  41 }
  42
  43 /// Given a subst for the requested impl, translate it to a subst
  44 /// appropriate for the actual item definition (whether it be in that impl,
  45 /// a parent impl, or the trait).
  46 /// When we have selected one impl, but are actually using item definitions from
  47 /// a parent impl providing a default, we need a way to translate between the
  48 /// type parameters of the two impls. Here the `source_impl` is the one we've
  49 /// selected, and `source_substs` is a substitution of its generics.
  50 /// And `target_node` is the impl/trait we're actually going to get the
  51 /// definition from. The resulting substitution will map from `target_node`'s
  52 /// generics to `source_impl`'s generics as instantiated by `source_subst`.
  53 ///
  54 /// For example, consider the following scenario:
  55 ///
  56 /// ```rust
  57 /// trait Foo { ... }
  58 /// impl<T, U> Foo for (T, U) { ... }  // target impl
  59 /// impl<V> Foo for (V, V) { ... }     // source impl
  60 /// ```
  61 ///
  62 /// Suppose we have selected "source impl" with `V` instantiated with `u32`.
  63 /// This function will produce a substitution with `T` and `U` both mapping to `u32`.
  64 ///
  65 /// Where clauses add some trickiness here, because they can be used to "define"
  66 /// an argument indirectly:
  67 ///
  68 /// ```rust
  69 /// impl<'a, I, T: 'a> Iterator for Cloned<I>
  70 ///    where I: Iterator<Item=&'a T>, T: Clone
  71 /// ```
  72 ///
  73 /// In a case like this, the substitution for `T` is determined indirectly,
  74 /// through associated type projection. We deal with such cases by using
  75 /// *fulfillment* to relate the two impls, requiring that all projections are
  76 /// resolved.
  77 pub fn translate_substs<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  78                                         source_impl: DefId,
  79                                         source_substs: &'tcx Substs<'tcx>,
  80                                         target_node: specialization_graph::Node)
  81                                         -> &'tcx Substs<'tcx> {
  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                 bug!("When translating substitutions for specialization, the expected \
  98                       specializaiton failed to hold")
  99             })
 100         }
 101         specialization_graph::Node::Trait(..) => source_trait_ref.substs,
 102     };
 103
 104     // directly inherent the method generics, since those do not vary across impls
 105     source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
 106 }
 107
 108 /// Given a selected impl described by `impl_data`, returns the
 109 /// definition and substitions for the method with the name `name`,
 110 /// and trait method substitutions `substs`, in that impl, a less
 111 /// specialized impl, or the trait default, whichever applies.
 112 pub fn find_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 113                              name: ast::Name,
 114                              substs: &'tcx Substs<'tcx>,
 115                              impl_data: &super::VtableImplData<'tcx, ()>)
 116                              -> (DefId, &'tcx Substs<'tcx>)
 117 {
 118     assert!(!substs.needs_infer());
 119
 120     let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
 121     let trait_def = tcx.lookup_trait_def(trait_def_id);
 122
 123     let ancestors = trait_def.ancestors(impl_data.impl_def_id);
 124     match ancestors.defs(tcx, name, ty::AssociatedKind::Method).next() {
 125         Some(node_item) => {
 126             let substs = tcx.infer_ctxt((), Reveal::All).enter(|infcx| {
 127                 let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
 128                 let substs = translate_substs(&infcx, impl_data.impl_def_id,
 129                                               substs, node_item.node);
 130                 let substs = infcx.tcx.erase_regions(&substs);
 131                 tcx.lift(&substs).unwrap_or_else(|| {
 132                     bug!("find_method: translate_substs \
 133                           returned {:?} which contains inference types/regions",
 134                          substs);
 135                 })
 136             });
 137             (node_item.item.def_id, substs)
 138         }
 139         None => {
 140             bug!("method {:?} not found in {:?}", name, impl_data.impl_def_id)
 141         }
 142     }
 143 }
 144
 145 /// Is impl1 a specialization of impl2?
 146 ///
 147 /// Specialization is determined by the sets of types to which the impls apply;
 148 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 149 /// to.
 150 pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 151                              impl1_def_id: DefId,
 152                              impl2_def_id: DefId) -> bool {
 153     debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
 154
 155     if let Some(r) = tcx.specializes_cache.borrow().check(impl1_def_id, impl2_def_id) {
 156         return r;
 157     }
 158
 159     // The feature gate should prevent introducing new specializations, but not
 160     // taking advantage of upstream ones.
 161     if !tcx.sess.features.borrow().specialization &&
 162         (impl1_def_id.is_local() || impl2_def_id.is_local()) {
 163         return false;
 164     }
 165
 166     // We determine whether there's a subset relationship by:
 167     //
 168     // - skolemizing impl1,
 169     // - assuming the where clauses for impl1,
 170     // - instantiating impl2 with fresh inference variables,
 171     // - unifying,
 172     // - attempting to prove the where clauses for impl2
 173     //
 174     // The last three steps are encapsulated in `fulfill_implication`.
 175     //
 176     // See RFC 1210 for more details and justification.
 177
 178     // Currently we do not allow e.g. a negative impl to specialize a positive one
 179     if tcx.trait_impl_polarity(impl1_def_id) != tcx.trait_impl_polarity(impl2_def_id) {
 180         return false;
 181     }
 182
 183     // create a parameter environment corresponding to a (skolemized) instantiation of impl1
 184     let penv = tcx.construct_parameter_environment(DUMMY_SP,
 185                                                    impl1_def_id,
 186                                                    region::DUMMY_CODE_EXTENT);
 187     let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id)
 188                              .unwrap()
 189                              .subst(tcx, &penv.free_substs);
 190
 191     // Create a infcx, taking the predicates of impl1 as assumptions:
 192     let result = tcx.infer_ctxt(penv, Reveal::UserFacing).enter(|infcx| {
 193         // Normalize the trait reference. The WF rules ought to ensure
 194         // that this always succeeds.
 195         let impl1_trait_ref =
 196             match traits::fully_normalize(&infcx, ObligationCause::dummy(), &impl1_trait_ref) {
 197                 Ok(impl1_trait_ref) => impl1_trait_ref,
 198                 Err(err) => {
 199                     bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
 200                 }
 201             };
 202
 203         // Attempt to prove that impl2 applies, given all of the above.
 204         fulfill_implication(&infcx, impl1_trait_ref, impl2_def_id).is_ok()
 205     });
 206
 207     tcx.specializes_cache.borrow_mut().insert(impl1_def_id, impl2_def_id, result);
 208     result
 209 }
 210
 211 /// Attempt to fulfill all obligations of `target_impl` after unification with
 212 /// `source_trait_ref`. If successful, returns a substitution for *all* the
 213 /// generics of `target_impl`, including both those needed to unify with
 214 /// `source_trait_ref` and those whose identity is determined via a where
 215 /// clause in the impl.
 216 fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 217                                        source_trait_ref: ty::TraitRef<'tcx>,
 218                                        target_impl: DefId)
 219                                        -> Result<&'tcx Substs<'tcx>, ()> {
 220     let selcx = &mut SelectionContext::new(&infcx);
 221     let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
 222     let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
 223                                                                    target_impl,
 224                                                                    target_substs);
 225
 226     // do the impls unify? If not, no specialization.
 227     match infcx.eq_trait_refs(true,
 228                               &ObligationCause::dummy(),
 229                               source_trait_ref,
 230                               target_trait_ref) {
 231         Ok(InferOk { obligations, .. }) => {
 232             // FIXME(#32730) propagate obligations
 233             assert!(obligations.is_empty())
 234         }
 235         Err(_) => {
 236             debug!("fulfill_implication: {:?} does not unify with {:?}",
 237                    source_trait_ref,
 238                    target_trait_ref);
 239             return Err(());
 240         }
 241     }
 242
 243     // attempt to prove all of the predicates for impl2 given those for impl1
 244     // (which are packed up in penv)
 245
 246     infcx.save_and_restore_obligations_in_snapshot_flag(|infcx| {
 247         let mut fulfill_cx = FulfillmentContext::new();
 248         for oblig in obligations.into_iter() {
 249             fulfill_cx.register_predicate_obligation(&infcx, oblig);
 250         }
 251         match fulfill_cx.select_all_or_error(infcx) {
 252             Err(errors) => {
 253                 // no dice!
 254                 debug!("fulfill_implication: for impls on {:?} and {:?}, \
 255                         could not fulfill: {:?} given {:?}",
 256                        source_trait_ref,
 257                        target_trait_ref,
 258                        errors,
 259                        infcx.parameter_environment.caller_bounds);
 260                 Err(())
 261             }
 262
 263             Ok(()) => {
 264                 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
 265                        source_trait_ref,
 266                        target_trait_ref);
 267
 268                 // Now resolve the *substitution* we built for the target earlier, replacing
 269                 // the inference variables inside with whatever we got from fulfillment.
 270                 Ok(infcx.resolve_type_vars_if_possible(&target_substs))
 271             }
 272         }
 273     })
 274 }
 275
 276 pub struct SpecializesCache {
 277     map: FxHashMap<(DefId, DefId), bool>
 278 }
 279
 280 impl SpecializesCache {
 281     pub fn new() -> Self {
 282         SpecializesCache {
 283             map: FxHashMap()
 284         }
 285     }
 286
 287     pub fn check(&self, a: DefId, b: DefId) -> Option<bool> {
 288         self.map.get(&(a, b)).cloned()
 289     }
 290
 291     pub fn insert(&mut self, a: DefId, b: DefId, result: bool) {
 292         self.map.insert((a, b), result);
 293     }
 294 }