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;
  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     pub on_trait_ref: ty::TraitRef<'tcx>,
  55 }
  56
  57 impl SpecializationGraph {
  58     pub fn new() -> SpecializationGraph {
  59         SpecializationGraph {
  60             parent: Default::default(),
  61             children: Default::default(),
  62         }
  63     }
  64
  65     /// Insert a local impl into the specialization graph. If an existing impl
  66     /// conflicts with it (has overlap, but neither specializes the other),
  67     /// information about the area of overlap is returned in the `Err`.
  68     pub fn insert<'tcx>(&mut self,
  69                         tcx: &ty::ctxt<'tcx>,
  70                         impl_def_id: DefId,
  71                         trait_ref: ty::TraitRef)
  72                         -> Result<(), Overlap<'tcx>> {
  73         assert!(impl_def_id.is_local());
  74
  75         let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
  76         let mut parent = trait_ref.def_id;
  77
  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 overlap = infcx.probe(|_| {
  88                     traits::overlapping_impls(&infcx, possible_sibling, impl_def_id)
  89                 });
  90
  91                 if let Some(trait_ref) = overlap {
  92                     let le = specializes(&infcx, impl_def_id, possible_sibling);
  93                     let ge = specializes(&infcx, possible_sibling, impl_def_id);
  94
  95                     if le && !ge {
  96                         // the impl specializes possible_sibling
  97                         parent = possible_sibling;
  98                         continue 'descend;
  99                     } else if ge && !le {
 100                         // possible_sibling specializes the impl
 101                         *slot = impl_def_id;
 102                         self.parent.insert(possible_sibling, impl_def_id);
 103                         my_children.push(possible_sibling);
 104                     } else {
 105                         // overlap, but no specialization; error out
 106                         return Err(Overlap {
 107                             with_impl: possible_sibling,
 108                             on_trait_ref: trait_ref,
 109                         });
 110                     }
 111
 112                     break 'descend;
 113                 }
 114             }
 115
 116             // no overlap with any potential siblings, so add as a new sibling
 117             self.parent.insert(impl_def_id, parent);
 118             possible_siblings.push(impl_def_id);
 119             break;
 120         }
 121
 122         if self.children.insert(impl_def_id, my_children).is_some() {
 123             panic!("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, Some(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
 141 fn skolemizing_subst_for_impl<'a>(tcx: &ty::ctxt<'a>, impl_def_id: DefId) -> Substs<'a> {
 142     let impl_generics = tcx.lookup_item_type(impl_def_id).generics;
 143
 144     let types = impl_generics.types.map(|def| tcx.mk_param_from_def(def));
 145
 146     // FIXME: figure out what we actually want here
 147     let regions = impl_generics.regions.map(|_| ty::Region::ReStatic);
 148     // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name)));
 149
 150     Substs::new(types, regions)
 151 }
 152
 153 /// Is impl1 a specialization of impl2?
 154 ///
 155 /// Specialization is determined by the sets of types to which the impls apply;
 156 /// impl1 specializes impl2 if it applies to a subset of the types impl2 applies
 157 /// to.
 158 pub fn specializes(infcx: &InferCtxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
 159     let tcx = &infcx.tcx;
 160
 161     // We determine whether there's a subset relationship by:
 162     //
 163     // - skolemizing impl1,
 164     // - assuming the where clauses for impl1,
 165     // - unifying,
 166     // - attempting to prove the where clauses for impl2
 167     //
 168     // See RFC 1210 for more details and justification.
 169
 170     let impl1_substs = skolemizing_subst_for_impl(tcx, impl1_def_id);
 171     let (impl1_trait_ref, impl1_obligations) = {
 172         let selcx = &mut SelectionContext::new(&infcx);
 173         util::impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs)
 174     };
 175
 176     let impl1_predicates: Vec<_> = impl1_obligations.iter()
 177         .cloned()
 178         .map(|oblig| oblig.predicate)
 179         .collect();
 180
 181     let penv = ty::ParameterEnvironment {
 182         tcx: tcx,
 183         free_substs: impl1_substs,
 184         implicit_region_bound: ty::ReEmpty, // FIXME: is this OK?
 185         caller_bounds: impl1_predicates,
 186         selection_cache: traits::SelectionCache::new(),
 187         evaluation_cache: traits::EvaluationCache::new(),
 188         free_id_outlive: region::DUMMY_CODE_EXTENT, // FIXME: is this OK?
 189     };
 190
 191     // FIXME: unclear what `errors_will_be_reported` should be here...
 192     let infcx = infer::new_infer_ctxt(tcx, infcx.tables, Some(penv), true);
 193     let selcx = &mut SelectionContext::new(&infcx);
 194
 195     let impl2_substs = util::fresh_type_vars_for_impl(&infcx, DUMMY_SP, impl2_def_id);
 196     let (impl2_trait_ref, impl2_obligations) =
 197         util::impl_trait_ref_and_oblig(selcx, impl2_def_id, &impl2_substs);
 198
 199     // do the impls unify? If not, no specialization.
 200     if let Err(_) = infer::mk_eq_trait_refs(&infcx,
 201                                             true,
 202                                             TypeOrigin::Misc(DUMMY_SP),
 203                                             impl1_trait_ref,
 204                                             impl2_trait_ref) {
 205         debug!("specializes: {:?} does not unify with {:?}",
 206                impl1_trait_ref,
 207                impl2_trait_ref);
 208         return false;
 209     }
 210
 211     let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
 212
 213     // attempt to prove all of the predicates for impl2 given those for impl1
 214     // (which are packed up in penv)
 215     for oblig in impl2_obligations.into_iter() {
 216         fulfill_cx.register_predicate_obligation(&infcx, oblig);
 217     }
 218
 219     if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) {
 220         debug!("specializes: for impls on {:?} and {:?}, could not fulfill: {:?} given {:?}",
 221                impl1_trait_ref,
 222                impl2_trait_ref,
 223                errors,
 224                infcx.parameter_environment.caller_bounds);
 225         return false;
 226     }
 227
 228     debug!("specializes: an impl for {:?} specializes {:?} (`where` clauses elided)",
 229            impl1_trait_ref,
 230            impl2_trait_ref);
 231     true
 232 }