src/librustc/middle/traits/specialize.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 use super::util;
  18 use super::SelectionContext;
  19
  20 use middle::cstore::CrateStore;
  21 use middle::def_id::DefId;
  22 use middle::infer::{self, InferCtxt, TypeOrigin};
  23 use middle::region;
  24 use middle::subst::{Subst, Substs};
  25 use middle::traits;
  26 use middle::ty::{self, ImplOrTraitItem};
  27 use syntax::codemap::DUMMY_SP;
  28 use util::nodemap::DefIdMap;
  29
  30 /// A per-trait graph of impls in specialization order.
  31 ///
  32 /// The graph provides two key services:
  33 ///
  34 /// - Construction, which implicitly checks for overlapping impls (i.e., impls
  35 ///   that overlap but where neither specializes the other -- an artifact of the
  36 ///   simple "chain" rule.
  37 ///
  38 /// - Parent extraction. In particular, the graph can give you the *immediate*
  39 ///   parents of a given specializing impl, which is needed for extracting
  40 ///   default items amongst other thigns. In the simple "chain" rule, every impl
  41 ///   has at most one parent.
  42 pub struct SpecializationGraph {
  43     // all impls have a parent; the "root" impls have as their parent the def_id
  44     // of the trait
  45     parent: DefIdMap<DefId>,
  46
  47     // the "root" impls are found by looking up the trait's def_id.
  48     children: DefIdMap<Vec<DefId>>,
  49 }
  50
  51 /// Information pertinent to an overlapping impl error.
  52 pub struct Overlap<'tcx> {
  53     pub with_impl: DefId,
  54
  55     /// NB: this TraitRef can contain inference variables!
  56     pub on_trait_ref: ty::TraitRef<'tcx>,
  57 }
  58
  59 impl SpecializationGraph {
  60     pub fn new() -> SpecializationGraph {
  61         SpecializationGraph {
  62             parent: Default::default(),
  63             children: Default::default(),
  64         }
  65     }
  66
  67     /// Insert a local impl into the specialization graph. If an existing impl
  68     /// conflicts with it (has overlap, but neither specializes the other),
  69     /// information about the area of overlap is returned in the `Err`.
  70     pub fn insert<'tcx>(&mut self,
  71                         tcx: &ty::ctxt<'tcx>,
  72                         impl_def_id: DefId,
  73                         trait_ref: ty::TraitRef)
  74                         -> Result<(), Overlap<'tcx>> {
  75         assert!(impl_def_id.is_local());
  76
  77         let mut parent = trait_ref.def_id;
  78         let mut my_children = vec![];
  79
  80         // descend the existing tree, looking for the right location to add this impl
  81         'descend: loop {
  82             let mut possible_siblings = self.children.entry(parent).or_insert(vec![]);
  83
  84             for slot in possible_siblings.iter_mut() {
  85                 let possible_sibling = *slot;
  86
  87                 let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
  88                 let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
  89
  90                 if let Some(trait_ref) = overlap {
  91                     let le = specializes(tcx, impl_def_id, possible_sibling);
  92                     let ge = specializes(tcx, possible_sibling, impl_def_id);
  93
  94                     if le && !ge {
  95                         // the impl specializes possible_sibling
  96                         parent = possible_sibling;
  97                         continue 'descend;
  98                     } else if ge && !le {
  99                         // possible_sibling specializes the impl
 100                         *slot = impl_def_id;
 101                         self.parent.insert(possible_sibling, impl_def_id);
 102                         my_children.push(possible_sibling);
 103                     } else {
 104                         // overlap, but no specialization; error out
 105                         return Err(Overlap {
 106                             with_impl: possible_sibling,
 107                             on_trait_ref: trait_ref,
 108                         });
 109                     }
 110
 111                     break 'descend;
 112                 }
 113             }
 114
 115             // no overlap with any potential siblings, so add as a new sibling
 116             self.parent.insert(impl_def_id, parent);
 117             possible_siblings.push(impl_def_id);
 118             break;
 119         }
 120
 121         if self.children.insert(impl_def_id, my_children).is_some() {
 122             tcx.sess
 123                .bug("When inserting an impl into the specialization graph, existing children for \
 124                      the impl were already present.");
 125         }
 126
 127         Ok(())
 128     }
 129
 130     /// Insert cached metadata mapping from a child impl back to its parent.
 131     pub fn record_impl_from_cstore(&mut self, parent: DefId, child: DefId) {
 132         if self.parent.insert(child, parent).is_some() {
 133             panic!("When recording an impl from the crate store, information about its parent \
 134                     was already present.");
 135         }
 136
 137         self.children.entry(parent).or_insert(vec![]).push(child);
 138     }
 139
 140     /// The parent of a given impl, which is the def id of the trait when the
 141     /// impl is a "specialization root".
 142     pub fn parent(&self, child: DefId) -> DefId {
 143         *self.parent.get(&child).unwrap()
 144     }
 145 }
 146
 147 /// When we have selected one impl, but are actually using item definitions from
 148 /// a parent impl providing a default, we need a way to translate between the
 149 /// type parameters of the two impls. Here the `source_impl` is the one we've
 150 /// selected, and `source_substs` is a substitution of its generics (and possibly
 151 /// some relevant `FnSpace` variables as well). And `target_impl` is the impl
 152 /// we're actually going to get the definition from.
 153 fn translate_substs_between_impls<'tcx>(tcx: &ty::ctxt<'tcx>,
 154                                         source_impl: DefId,
 155                                         source_substs: Substs<'tcx>,
 156                                         target_impl: DefId)
 157                                         -> Substs<'tcx> {
 158
 159     // We need to build a subst that covers all the generics of
 160     // `target_impl`. Start by introducing fresh infer variables:
 161     let target_generics = tcx.lookup_item_type(target_impl).generics;
 162     let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables);
 163     let mut target_substs = infcx.fresh_substs_for_generics(DUMMY_SP, &target_generics);
 164     if source_substs.regions.is_erased() {
 165         target_substs = target_substs.erase_regions()
 166     }
 167
 168     if !fulfill_implication(&mut infcx,
 169                             source_impl,
 170                             source_substs.clone(),
 171                             target_impl,
 172                             target_substs.clone()) {
 173         tcx.sess
 174            .bug("When translating substitutions for specialization, the expected specializaiton \
 175                  failed to hold")
 176     }
 177
 178     // Now resolve the *substitution* we built for the target earlier, replacing
 179     // the inference variables inside with whatever we got from fulfillment. We
 180     // also carry along any FnSpace substitutions, which don't need to be
 181     // adjusted when mapping from one impl to another.
 182     infcx.resolve_type_vars_if_possible(&target_substs)
 183          .with_method_from_subst(&source_substs)
 184 }
 185
 186 /// When we've selected an impl but need to use an item definition provided by
 187 /// the trait itself, we need to translate the substitution applied to the impl
 188 /// to one that makes sense for the trait.
 189 fn translate_substs_from_impl_to_trait<'tcx>(tcx: &ty::ctxt<'tcx>,
 190                                              source_impl: DefId,
 191                                              source_substs: Substs<'tcx>)
 192                                              -> Substs<'tcx> {
 193
 194     let source_trait_ref = tcx.impl_trait_ref(source_impl).unwrap().subst(tcx, &source_substs);
 195
 196     let mut new_substs = source_trait_ref.substs.clone();
 197     if source_substs.regions.is_erased() {
 198         new_substs = new_substs.erase_regions()
 199     }
 200
 201     // Carry any FnSpace substitutions along; they don't need to be adjusted
 202     new_substs.with_method_from_subst(&source_substs)
 203 }
 204
 205 #[derive(Debug, Copy, Clone)]
 206 /// When looking up an item in an impl, it may turn out that the item
 207 /// is actually provided as a default by a more generic impl, or by
 208 /// the trait itself. This enum says where the item came from.
 209 pub enum ItemSource {
 210     Impl {
 211         requested_impl: DefId,
 212         actual_impl: DefId,
 213     },
 214     Trait {
 215         requested_impl: DefId,
 216     },
 217 }
 218
 219 impl ItemSource {
 220     pub fn is_from_trait(&self) -> bool {
 221         match *self {
 222             ItemSource::Trait { .. } => true,
 223             _ => false,
 224         }
 225     }
 226
 227     /// Given a subst for the requested impl, translate it to a subst
 228     /// appropriate for the actual item definition (whether it be in that impl,
 229     /// a parent impl, or the trait).
 230     pub fn translate_substs<'tcx>(&self,
 231                                   tcx: &ty::ctxt<'tcx>,
 232                                   requested_impl_substs: Substs<'tcx>)
 233                                   -> Substs<'tcx> {
 234         match *self {
 235             ItemSource::Impl { requested_impl, actual_impl } => {
 236                 // no need to translate if we're targetting the impl we started with
 237                 if requested_impl == actual_impl {
 238                     return requested_impl_substs;
 239                 }
 240
 241                 translate_substs_between_impls(tcx,
 242                                                requested_impl,
 243                                                requested_impl_substs,
 244                                                actual_impl)
 245
 246             }
 247             ItemSource::Trait { requested_impl } => {
 248                 translate_substs_from_impl_to_trait(tcx, requested_impl, requested_impl_substs)
 249             }
 250         }
 251     }
 252 }
 253
 254 /// Lookup the definition of an item within `requested_impl` or its specialization
 255 /// parents, including provided items from the trait itself.
 256 ///
 257 /// The closure `f` works in the style of `filter_map`.
 258 pub fn get_impl_item_or_default<'tcx, I, F>(tcx: &ty::ctxt<'tcx>,
 259                                             requested_impl: DefId,
 260                                             mut f: F)
 261                                             -> Option<(I, ItemSource)>
 262     where F: for<'a> FnMut(&ImplOrTraitItem<'tcx>) -> Option<I>
 263 {
 264     let impl_or_trait_items_map = tcx.impl_or_trait_items.borrow();
 265     let trait_def_id = tcx.trait_id_of_impl(requested_impl).unwrap();
 266     let trait_def = tcx.lookup_trait_def(trait_def_id);
 267
 268     // Walk up the specialization tree, looking for a matching item definition
 269
 270     let mut current_impl = requested_impl;
 271     loop {
 272         for impl_item_id in &tcx.impl_items.borrow()[&current_impl] {
 273             let impl_item = &impl_or_trait_items_map[&impl_item_id.def_id()];
 274             if let Some(t) = f(impl_item) {
 275                 let source = ItemSource::Impl {
 276                     requested_impl: requested_impl,
 277                     actual_impl: current_impl,
 278                 };
 279                 return Some((t, source));
 280             }
 281         }
 282
 283         if let Some(parent) = trait_def.parent_of_impl(current_impl) {
 284             current_impl = parent;
 285         } else {
 286             break;
 287         }
 288     }
 289
 290     // The item isn't defined anywhere in the hierarchy. Get the
 291     // default from the trait.
 292
 293     for trait_item in tcx.trait_items(trait_def_id).iter() {
 294         if let Some(t) = f(trait_item) {
 295             return Some((t, ItemSource::Trait { requested_impl: requested_impl }));
 296         }
 297     }
 298
 299     None
 300 }
 301
 302 fn skolemizing_subst_for_impl<'a>(tcx: &ty::ctxt<'a>, impl_def_id: DefId) -> Substs<'a> {
 303     let impl_generics = tcx.lookup_item_type(impl_def_id).generics;
 304
 305     let types = impl_generics.types.map(|def| tcx.mk_param_from_def(def));
 306
 307     // FIXME: figure out what we actually want here
 308     let regions = impl_generics.regions.map(|_| ty::Region::ReStatic);
 309     // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name)));
 310
 311     Substs::new(types, regions)
 312 }
 313
 314 /// Is impl1 a specialization of impl2?
 315 ///
 316 /// Specialization is determined by the sets of types to which the impls apply;
 317 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 318 /// to.
 319 pub fn specializes(tcx: &ty::ctxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
 320     // We determine whether there's a subset relationship by:
 321     //
 322     // - skolemizing impl1,
 323     // - instantiating impl2 with fresh inference variables,
 324     // - assuming the where clauses for impl1,
 325     // - unifying,
 326     // - attempting to prove the where clauses for impl2
 327     //
 328     // The last three steps are essentially checking for an implication between two impls
 329     // after appropriate substitutions. This is what `fulfill_implication` checks for.
 330     //
 331     // See RFC 1210 for more details and justification.
 332
 333     let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables);
 334
 335     let impl1_substs = skolemizing_subst_for_impl(tcx, impl1_def_id);
 336     let impl2_substs = util::fresh_type_vars_for_impl(&infcx, DUMMY_SP, impl2_def_id);
 337
 338     fulfill_implication(&mut infcx,
 339                         impl1_def_id,
 340                         impl1_substs,
 341                         impl2_def_id,
 342                         impl2_substs)
 343 }
 344
 345 /// Does impl1 (instantiated with the impl1_substs) imply impl2
 346 /// (instantiated with impl2_substs)?
 347 ///
 348 /// Mutates the `infcx` in two ways:
 349 /// - by adding the obligations of impl1 to the parameter environment
 350 /// - via fulfillment, so that if the implication holds the various unifications
 351 fn fulfill_implication<'a, 'tcx>(infcx: &mut InferCtxt<'a, 'tcx>,
 352                                  impl1_def_id: DefId,
 353                                  impl1_substs: Substs<'tcx>,
 354                                  impl2_def_id: DefId,
 355                                  impl2_substs: Substs<'tcx>)
 356                                  -> bool {
 357     let tcx = &infcx.tcx;
 358
 359     let (impl1_trait_ref, impl1_obligations) = {
 360         let selcx = &mut SelectionContext::new(&infcx);
 361         util::impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs)
 362     };
 363
 364     let impl1_predicates: Vec<_> = impl1_obligations.iter()
 365                                                     .cloned()
 366                                                     .map(|oblig| oblig.predicate)
 367                                                     .collect();
 368
 369     infcx.parameter_environment = ty::ParameterEnvironment {
 370         tcx: tcx,
 371         free_substs: impl1_substs,
 372         implicit_region_bound: ty::ReEmpty, // FIXME: is this OK?
 373         caller_bounds: impl1_predicates,
 374         selection_cache: traits::SelectionCache::new(),
 375         evaluation_cache: traits::EvaluationCache::new(),
 376         free_id_outlive: region::DUMMY_CODE_EXTENT, // FIXME: is this OK?
 377     };
 378
 379     let selcx = &mut SelectionContext::new(&infcx);
 380     let (impl2_trait_ref, impl2_obligations) = util::impl_trait_ref_and_oblig(selcx,
 381                                                                               impl2_def_id,
 382                                                                               &impl2_substs);
 383
 384     // do the impls unify? If not, no specialization.
 385     if let Err(_) = infer::mk_eq_trait_refs(&infcx,
 386                                             true,
 387                                             TypeOrigin::Misc(DUMMY_SP),
 388                                             impl1_trait_ref,
 389                                             impl2_trait_ref) {
 390         debug!("fulfill_implication: {:?} does not unify with {:?}",
 391                impl1_trait_ref,
 392                impl2_trait_ref);
 393         return false;
 394     }
 395
 396     let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
 397
 398     // attempt to prove all of the predicates for impl2 given those for impl1
 399     // (which are packed up in penv)
 400
 401     for oblig in impl2_obligations.into_iter() {
 402         fulfill_cx.register_predicate_obligation(&infcx, oblig);
 403     }
 404
 405     if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) {
 406         // no dice!
 407         debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
 408                 {:?}",
 409                impl1_trait_ref,
 410                impl2_trait_ref,
 411                errors,
 412                infcx.parameter_environment.caller_bounds);
 413         false
 414     } else {
 415         debug!("fulfill_implication: an impl for {:?} specializes {:?} (`where` clauses elided)",
 416                impl1_trait_ref,
 417                impl2_trait_ref);
 418         true
 419     }
 420 }