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 ty::subst::{Subst, Substs};
  27 use traits::{self, Reveal, ObligationCause};
  28 use ty::{self, TyCtxt, TypeFoldable};
  29 use syntax_pos::DUMMY_SP;
  30 use std::rc::Rc;
  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 ///
  45 /// When we have selected one impl, but are actually using item definitions from
  46 /// a parent impl providing a default, we need a way to translate between the
  47 /// type parameters of the two impls. Here the `source_impl` is the one we've
  48 /// selected, and `source_substs` is a substitution of its generics.
  49 /// And `target_node` is the impl/trait we're actually going to get the
  50 /// definition from. The resulting substitution will map from `target_node`'s
  51 /// generics to `source_impl`'s 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                                         param_env: ty::ParamEnv<'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, param_env, source_trait_ref, target_impl)
  97                 .unwrap_or_else(|_| {
  98                     bug!("When translating substitutions for specialization, the expected \
  99                           specializaiton failed to hold")
 100                 })
 101         }
 102         specialization_graph::Node::Trait(..) => source_trait_ref.substs,
 103     };
 104
 105     // directly inherent the method generics, since those do not vary across impls
 106     source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
 107 }
 108
 109 /// Given a selected impl described by `impl_data`, returns the
 110 /// definition and substitions for the method with the name `name`
 111 /// the kind `kind`, and trait method substitutions `substs`, in
 112 /// that impl, a less specialized impl, or the trait default,
 113 /// whichever applies.
 114 pub fn find_associated_item<'a, 'tcx>(
 115     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 116     item: &ty::AssociatedItem,
 117     substs: &'tcx Substs<'tcx>,
 118     impl_data: &super::VtableImplData<'tcx, ()>,
 119 ) -> (DefId, &'tcx Substs<'tcx>) {
 120     assert!(!substs.needs_infer());
 121
 122     let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
 123     let trait_def = tcx.trait_def(trait_def_id);
 124
 125     let ancestors = trait_def.ancestors(tcx, impl_data.impl_def_id);
 126     match ancestors.defs(tcx, item.name, item.kind).next() {
 127         Some(node_item) => {
 128             let substs = tcx.infer_ctxt(()).enter(|infcx| {
 129                 let param_env = ty::ParamEnv::empty(Reveal::All);
 130                 let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
 131                 let substs = translate_substs(&infcx, param_env, impl_data.impl_def_id,
 132                                               substs, node_item.node);
 133                 let substs = infcx.tcx.erase_regions(&substs);
 134                 tcx.lift(&substs).unwrap_or_else(|| {
 135                     bug!("find_method: translate_substs \
 136                           returned {:?} which contains inference types/regions",
 137                          substs);
 138                 })
 139             });
 140             (node_item.item.def_id, substs)
 141         }
 142         None => {
 143             bug!("{:?} not found in {:?}", item, impl_data.impl_def_id)
 144         }
 145     }
 146 }
 147
 148 /// Is impl1 a specialization of impl2?
 149 ///
 150 /// Specialization is determined by the sets of types to which the impls apply;
 151 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 152 /// to.
 153 pub fn specializes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 154                              impl1_def_id: DefId,
 155                              impl2_def_id: DefId) -> bool {
 156     debug!("specializes({:?}, {:?})", impl1_def_id, impl2_def_id);
 157
 158     if let Some(r) = tcx.specializes_cache.borrow().check(impl1_def_id, impl2_def_id) {
 159         return r;
 160     }
 161
 162     // The feature gate should prevent introducing new specializations, but not
 163     // taking advantage of upstream ones.
 164     if !tcx.sess.features.borrow().specialization &&
 165         (impl1_def_id.is_local() || impl2_def_id.is_local()) {
 166         return false;
 167     }
 168
 169     // We determine whether there's a subset relationship by:
 170     //
 171     // - skolemizing impl1,
 172     // - assuming the where clauses for impl1,
 173     // - instantiating impl2 with fresh inference variables,
 174     // - unifying,
 175     // - attempting to prove the where clauses for impl2
 176     //
 177     // The last three steps are encapsulated in `fulfill_implication`.
 178     //
 179     // See RFC 1210 for more details and justification.
 180
 181     // Currently we do not allow e.g. a negative impl to specialize a positive one
 182     if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
 183         return false;
 184     }
 185
 186     // create a parameter environment corresponding to a (skolemized) instantiation of impl1
 187     let penv = tcx.param_env(impl1_def_id);
 188     let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
 189
 190     // Create a infcx, taking the predicates of impl1 as assumptions:
 191     let result = tcx.infer_ctxt(()).enter(|infcx| {
 192         // Normalize the trait reference. The WF rules ought to ensure
 193         // that this always succeeds.
 194         let impl1_trait_ref =
 195             match traits::fully_normalize(&infcx,
 196                                           ObligationCause::dummy(),
 197                                           penv,
 198                                           &impl1_trait_ref) {
 199                 Ok(impl1_trait_ref) => impl1_trait_ref,
 200                 Err(err) => {
 201                     bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
 202                 }
 203             };
 204
 205         // Attempt to prove that impl2 applies, given all of the above.
 206         fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
 207     });
 208
 209     tcx.specializes_cache.borrow_mut().insert(impl1_def_id, impl2_def_id, result);
 210     result
 211 }
 212
 213 /// Attempt to fulfill all obligations of `target_impl` after unification with
 214 /// `source_trait_ref`. If successful, returns a substitution for *all* the
 215 /// generics of `target_impl`, including both those needed to unify with
 216 /// `source_trait_ref` and those whose identity is determined via a where
 217 /// clause in the impl.
 218 fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 219                                        param_env: ty::ParamEnv<'tcx>,
 220                                        source_trait_ref: ty::TraitRef<'tcx>,
 221                                        target_impl: DefId)
 222                                        -> Result<&'tcx Substs<'tcx>, ()> {
 223     let selcx = &mut SelectionContext::new(&infcx);
 224     let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl);
 225     let (target_trait_ref, mut obligations) = impl_trait_ref_and_oblig(selcx,
 226                                                                        param_env,
 227                                                                        target_impl,
 228                                                                        target_substs);
 229
 230     // do the impls unify? If not, no specialization.
 231     match infcx.at(&ObligationCause::dummy(), param_env)
 232                .eq(source_trait_ref, target_trait_ref) {
 233         Ok(InferOk { obligations: o, .. }) => {
 234             obligations.extend(o);
 235         }
 236         Err(_) => {
 237             debug!("fulfill_implication: {:?} does not unify with {:?}",
 238                    source_trait_ref,
 239                    target_trait_ref);
 240             return Err(());
 241         }
 242     }
 243
 244     // attempt to prove all of the predicates for impl2 given those for impl1
 245     // (which are packed up in penv)
 246
 247     infcx.save_and_restore_in_snapshot_flag(|infcx| {
 248         let mut fulfill_cx = FulfillmentContext::new();
 249         for oblig in obligations.into_iter() {
 250             fulfill_cx.register_predicate_obligation(&infcx, oblig);
 251         }
 252         match fulfill_cx.select_all_or_error(infcx) {
 253             Err(errors) => {
 254                 // no dice!
 255                 debug!("fulfill_implication: for impls on {:?} and {:?}, \
 256                         could not fulfill: {:?} given {:?}",
 257                        source_trait_ref,
 258                        target_trait_ref,
 259                        errors,
 260                        param_env.caller_bounds);
 261                 Err(())
 262             }
 263
 264             Ok(()) => {
 265                 debug!("fulfill_implication: an impl for {:?} specializes {:?}",
 266                        source_trait_ref,
 267                        target_trait_ref);
 268
 269                 // Now resolve the *substitution* we built for the target earlier, replacing
 270                 // the inference variables inside with whatever we got from fulfillment.
 271                 Ok(infcx.resolve_type_vars_if_possible(&target_substs))
 272             }
 273         }
 274     })
 275 }
 276
 277 pub struct SpecializesCache {
 278     map: FxHashMap<(DefId, DefId), bool>,
 279 }
 280
 281 impl SpecializesCache {
 282     pub fn new() -> Self {
 283         SpecializesCache {
 284             map: FxHashMap()
 285         }
 286     }
 287
 288     pub fn check(&self, a: DefId, b: DefId) -> Option<bool> {
 289         self.map.get(&(a, b)).cloned()
 290     }
 291
 292     pub fn insert(&mut self, a: DefId, b: DefId, result: bool) {
 293         self.map.insert((a, b), result);
 294     }
 295 }
 296
 297 // Query provider for `specialization_graph_of`.
 298 pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 299                                                       trait_id: DefId)
 300                                                       -> Rc<specialization_graph::Graph> {
 301     let mut sg = specialization_graph::Graph::new();
 302
 303     let mut trait_impls: Vec<DefId> = tcx.trait_impls_of(trait_id).iter().collect();
 304
 305     // The coherence checking implementation seems to rely on impls being
 306     // iterated over (roughly) in definition order, so we are sorting by
 307     // negated CrateNum (so remote definitions are visited first) and then
 308     // by a flattend version of the DefIndex.
 309     trait_impls.sort_unstable_by_key(|def_id| {
 310         (-(def_id.krate.as_u32() as i64),
 311          def_id.index.address_space().index(),
 312          def_id.index.as_array_index())
 313     });
 314
 315     for impl_def_id in trait_impls {
 316         if impl_def_id.is_local() {
 317             // This is where impl overlap checking happens:
 318             let insert_result = sg.insert(tcx, impl_def_id);
 319             // Report error if there was one.
 320             if let Err(overlap) = insert_result {
 321                 let mut err = struct_span_err!(tcx.sess,
 322                                                tcx.span_of_impl(impl_def_id).unwrap(),
 323                                                E0119,
 324                                                "conflicting implementations of trait `{}`{}:",
 325                                                overlap.trait_desc,
 326                                                overlap.self_desc.clone().map_or(String::new(),
 327                                                                                 |ty| {
 328                     format!(" for type `{}`", ty)
 329                 }));
 330
 331                 match tcx.span_of_impl(overlap.with_impl) {
 332                     Ok(span) => {
 333                         err.span_label(span, format!("first implementation here"));
 334                         err.span_label(tcx.span_of_impl(impl_def_id).unwrap(),
 335                                        format!("conflicting implementation{}",
 336                                                 overlap.self_desc
 337                                                     .map_or(String::new(),
 338                                                             |ty| format!(" for `{}`", ty))));
 339                     }
 340                     Err(cname) => {
 341                         err.note(&format!("conflicting implementation in crate `{}`", cname));
 342                     }
 343                 }
 344
 345                 err.emit();
 346             }
 347         } else {
 348             let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
 349             sg.record_impl_from_cstore(tcx, parent, impl_def_id)
 350         }
 351     }
 352
 353     Rc::new(sg)
 354 }