diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc/middle/traits/coherence.rs | 3 | ||||
| -rw-r--r-- | src/librustc/middle/traits/mod.rs | 8 | ||||
| -rw-r--r-- | src/librustc/middle/traits/project.rs | 145 | ||||
| -rw-r--r-- | src/librustc/middle/traits/select.rs | 146 | ||||
| -rw-r--r-- | src/librustc/middle/traits/specialize.rs | 454 | ||||
| -rw-r--r-- | src/librustc/middle/traits/specialize/mod.rs | 244 | ||||
| -rw-r--r-- | src/librustc/middle/traits/specialize/specialization_graph.rs | 382 | ||||
| -rw-r--r-- | src/librustc/middle/ty/trait_def.rs | 14 | ||||
| -rw-r--r-- | src/librustc_data_structures/obligation_forest/README.md | 4 | ||||
| -rw-r--r-- | src/librustc_front/hir.rs | 10 | ||||
| -rw-r--r-- | src/librustc_metadata/encoder.rs | 9 | ||||
| -rw-r--r-- | src/librustc_trans/trans/common.rs | 4 | ||||
| -rw-r--r-- | src/librustc_trans/trans/meth.rs | 26 | ||||
| -rw-r--r-- | src/librustc_typeck/check/mod.rs | 180 | ||||
| -rw-r--r-- | src/librustc_typeck/coherence/overlap.rs | 6 | ||||
| -rw-r--r-- | src/test/compile-fail/specialization-no-default.rs | 4 |
16 files changed, 989 insertions, 650 deletions
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs index 33a1e3816e3..bc3d3e48d6b 100644 --- a/src/librustc/middle/traits/coherence.rs +++ b/src/librustc/middle/traits/coherence.rs @@ -10,6 +10,7 @@ //! See `README.md` for high-level documentation +use super::build_selcx; use super::{SelectionContext, Obligation, ObligationCause}; use super::util; @@ -36,7 +37,7 @@ pub fn overlapping_impls<'cx, 'tcx>(infcx: &InferCtxt<'cx, 'tcx>, impl1_def_id, impl2_def_id); - let selcx = &mut SelectionContext::intercrate(infcx); + let selcx = &mut build_selcx(infcx).project_topmost().intercrate().build(); overlap(selcx, impl1_def_id, impl2_def_id) } diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs index 180a1312e25..d9fc53ff2c2 100644 --- a/src/librustc/middle/traits/mod.rs +++ b/src/librustc/middle/traits/mod.rs @@ -45,13 +45,11 @@ pub use self::object_safety::object_safety_violations; pub use self::object_safety::ObjectSafetyViolation; pub use self::object_safety::MethodViolationCode; pub use self::object_safety::is_vtable_safe_method; -pub use self::select::EvaluationCache; -pub use self::select::SelectionContext; -pub use self::select::SelectionCache; +pub use self::select::{EvaluationCache, SelectionContextBuilder, build_selcx}; +pub use self::select::{ProjectionMode, SelectionContext, SelectionCache}; pub use self::select::{MethodMatchResult, MethodMatched, MethodAmbiguous, MethodDidNotMatch}; pub use self::select::{MethodMatchedData}; // intentionally don't export variants -pub use self::specialize::{Overlap, SpecializationGraph, specializes}; -pub use self::specialize::{ItemSource, get_impl_item_or_default, get_parent_impl_item}; +pub use self::specialize::{Overlap, specialization_graph, specializes, translate_substs}; pub use self::util::elaborate_predicates; pub use self::util::get_vtable_index_of_object_method; pub use self::util::trait_ref_for_builtin_bound; diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs index dc279aae32c..20d6c0b6fc0 100644 --- a/src/librustc/middle/traits/project.rs +++ b/src/librustc/middle/traits/project.rs @@ -11,8 +11,9 @@ //! Code for projecting associated types out of trait references. use super::elaborate_predicates; -use super::get_impl_item_or_default; use super::report_overflow_error; +use super::specialization_graph; +use super::translate_substs; use super::Obligation; use super::ObligationCause; use super::PredicateObligation; @@ -22,14 +23,18 @@ use super::VtableClosureData; use super::VtableImplData; use super::util; +use middle::def_id::DefId; use middle::infer::{self, TypeOrigin}; use middle::subst::Subst; use middle::ty::{self, ToPredicate, RegionEscape, HasTypeFlags, ToPolyTraitRef, Ty, TyCtxt}; use middle::ty::fold::{TypeFoldable, TypeFolder}; use rustc_front::hir; use syntax::parse::token; +use syntax::ast; use util::common::FN_OUTPUT_NAME; +use std::rc::Rc; + pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>; @@ -568,7 +573,49 @@ fn project_type<'cx,'tcx>( assert!(candidates.vec.len() <= 1); - match candidates.vec.pop() { + let possible_candidate = candidates.vec.pop().and_then(|candidate| { + // In Any (i.e. trans) mode, all projections succeed; + // otherwise, we need to be sensitive to `default` and + // specialization. + if !selcx.projection_mode().any() { + if let ProjectionTyCandidate::Impl(ref impl_data) = candidate { + if let Some(node_item) = assoc_ty_def(selcx, + impl_data.impl_def_id, + obligation.predicate.item_name) { + if node_item.node.is_from_trait() { + if node_item.item.ty.is_some() { + // If the associated type has a default from the + // trait, that should be considered `default` and + // hence not projected. + // + // Note, however, that we allow a projection from + // the trait specifically in the case that the trait + // does *not* give a default. This is purely to + // avoid spurious errors: the situation can only + // arise when *no* impl in the specialization chain + // has provided a definition for the type. When we + // confirm the candidate, we'll turn the projection + // into a TyError, since the actual error will be + // reported in `check_impl_items_against_trait`. + return None; + } + } else if node_item.item.defaultness.is_default() { + return None; + } + } else { + // Normally this situation could only arise througha + // compiler bug, but at coherence-checking time we only look + // at the topmost impl (we don't even consider the trait + // itself) for the definition -- so we can fail to find a + // definition of the type even if it exists. + return None; + } + } + } + Some(candidate) + }); + + match possible_candidate { Some(candidate) => { let (ty, obligations) = confirm_candidate(selcx, obligation, candidate); Ok(ProjectedTy::Progress(ty, obligations)) @@ -744,28 +791,6 @@ fn assemble_candidates_from_impls<'cx,'tcx>( match vtable { super::VtableImpl(data) => { - if data.substs.types.needs_infer() { - let assoc_ty_opt = get_impl_item_or_default(selcx.tcx(), data.impl_def_id, |cand| { - if let &ty::TypeTraitItem(ref assoc_ty) = cand { - if assoc_ty.name == obligation.predicate.item_name { - return Some(assoc_ty.defaultness); - } - } - None - }); - - if let Some((defaultness, source)) = assoc_ty_opt { - if !source.is_from_trait() && defaultness == hir::Defaultness::Default { - // FIXME: is it OK to not mark as ambiguous? - return Ok(()); - } - } else { - selcx.tcx().sess.span_bug(obligation.cause.span, - &format!("No associated type for {:?}", - obligation_trait_ref)); - } - } - debug!("assemble_candidates_from_impls: impl candidate {:?}", data); @@ -967,29 +992,59 @@ fn confirm_impl_candidate<'cx,'tcx>( { let VtableImplData { substs, nested, impl_def_id } = impl_vtable; - get_impl_item_or_default(selcx.tcx(), impl_def_id, |cand| { - if let &ty::TypeTraitItem(ref assoc_ty) = cand { - if assoc_ty.name == obligation.predicate.item_name { - if let Some(ty) = assoc_ty.ty { - return Some(ty) - } else { - // This means that the impl is missing a definition for the - // associated type. This error will be reported by the type - // checker method `check_impl_items_against_trait`, so here - // we just return TyError. - debug!("confirm_impl_candidate: no associated type {:?} for {:?}", - assoc_ty.name, - obligation.predicate.trait_ref); - return Some(selcx.tcx().types.err); + let tcx = selcx.tcx(); + let trait_ref = obligation.predicate.trait_ref; + let assoc_ty = assoc_ty_def(selcx, impl_def_id, obligation.predicate.item_name); + + match assoc_ty { + Some(node_item) => { + let ty = node_item.item.ty.unwrap_or_else(|| { + // This means that the impl is missing a definition for the + // associated type. This error will be reported by the type + // checker method `check_impl_items_against_trait`, so here we + // just return TyError. + debug!("confirm_impl_candidate: no associated type {:?} for {:?}", + node_item.item.name, + obligation.predicate.trait_ref); + tcx.types.err + }); + let substs = translate_substs(tcx, impl_def_id, substs, node_item.node); + (ty.subst(tcx, &substs), nested) + } + None => { + tcx.sess.span_bug(obligation.cause.span, + &format!("No associated type for {:?}", trait_ref)); + } + } +} + +/// Locate the definition of an associated type in the specialization hierarchy, +/// starting from the given impl. +/// +/// Based on the "projection mode", this lookup may in fact only examine the +/// topmost impl. See the comments for `ProjectionMode` for more details. +fn assoc_ty_def<'cx, 'tcx>(selcx: &SelectionContext<'cx, 'tcx>, impl_def_id: DefId, assoc_ty_name: ast::Name) + -> Option<specialization_graph::NodeItem<Rc<ty::AssociatedType<'tcx>>>> +{ + let trait_def_id = selcx.tcx().impl_trait_ref(impl_def_id).unwrap().def_id; + + if selcx.projection_mode().topmost() { + let impl_node = specialization_graph::Node::Impl(impl_def_id); + for item in impl_node.items(selcx.tcx()) { + if let ty::TypeTraitItem(assoc_ty) = item { + if assoc_ty.name == assoc_ty_name { + return Some(specialization_graph::NodeItem { + node: specialization_graph::Node::Impl(impl_def_id), + item: assoc_ty, + }); } } } None - }).map(|(ty, source)| { - (ty.subst(selcx.tcx(), &source.translate_substs(selcx.tcx(), substs)), nested) - }).unwrap_or_else(|| { - selcx.tcx().sess.span_bug(obligation.cause.span, - &format!("No associated type for {:?}", - obligation.predicate.trait_ref)); - }) + } else { + selcx.tcx().lookup_trait_def(trait_def_id) + .ancestors(impl_def_id) + .type_defs(selcx.tcx(), assoc_ty_name) + .next() + } } diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs index fd41007d0e2..83e02d16c3b 100644 --- a/src/librustc/middle/traits/select.rs +++ b/src/librustc/middle/traits/select.rs @@ -76,8 +76,99 @@ pub struct SelectionContext<'cx, 'tcx:'cx> { /// other words, we consider `$0 : Bar` to be unimplemented if /// there is no type that the user could *actually name* that /// would satisfy it. This avoids crippling inference, basically. - intercrate: bool, + + /// Sadly, the behavior of projection varies a bit depending on the + /// stage of compilation. The specifics are given in the + /// documentation for `ProjectionMode`. + projection_mode: ProjectionMode, +} + +/// Depending on the stage of compilation, we want projection to be +/// more or less conservative. +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum ProjectionMode { + /// At coherence-checking time, we're still constructing the + /// specialization graph, and thus we only project project + /// non-`default` associated types that are defined directly in + /// the applicable impl. (This behavior should be improved over + /// time, to allow for successful projections modulo cycles + /// between different impls). + // TODO: Add tracking issue to do better here. + /// + /// Here's an example that will fail due to the restriction: + /// + /// ``` + /// trait Assoc { + /// type Output; + /// } + /// + /// impl<T> Assoc for T { + /// type Output = bool; + /// } + /// + /// impl Assoc for u8 {} // <- inherits the non-default type from above + /// + /// trait Foo {} + /// impl Foo for u32 {} + /// impl Foo for <u8 as Assoc>::Output {} // <- this projection will fail + /// ``` + /// + /// The projection would succeed if `Output` had been defined + /// directly in the impl for `u8`. + // TODO: Add test + Topmost, + + /// At type-checking time, we refuse to project any associated + /// type that is marked `default`. Non-`default` ("final") types + /// are always projected. This is necessary in general for + /// soundness of specialization. However, we *could* allow + /// projections in fully-monomorphic cases. We choose not to, + /// because we prefer for `default type` to force the type + /// definition to be treated abstractly by any consumers of the + /// impl. Concretely, that means that the following example will + /// fail to compile: + /// + /// ``` + /// trait Assoc { + /// type Output; + /// } + /// + /// impl<T> Assoc for T { + /// default type Output = bool; + /// } + /// + /// fn main() { + /// let <() as Assoc>::Output = true; + /// } + // TODO: Add test + AnyFinal, + + /// At trans time, all projections will succeed. + Any, +} + +impl ProjectionMode { + pub fn topmost(&self) -> bool { + match *self { + ProjectionMode::Topmost => true, + _ => false, + } + } + + pub fn any_final(&self) -> bool { + match *self { + ProjectionMode::AnyFinal => true, + _ => false, + } + } + + pub fn any(&self) -> bool { + match *self { + ProjectionMode::Any => true, + _ => false, + } + } } // A stack that walks back up the stack frame. @@ -257,22 +348,45 @@ pub struct EvaluationCache<'tcx> { hashmap: RefCell<FnvHashMap<ty::PolyTraitRef<'tcx>, EvaluationResult>> } -impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { - pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>) - -> SelectionContext<'cx, 'tcx> { - SelectionContext { - infcx: infcx, - freshener: infcx.freshener(), - intercrate: false, - } +pub struct SelectionContextBuilder<'cx, 'tcx: 'cx>(SelectionContext<'cx, 'tcx>); + +impl<'cx, 'tcx> SelectionContextBuilder<'cx, 'tcx> { + pub fn intercrate(mut self) -> Self { + self.0.intercrate = true; + self } - pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>) - -> SelectionContext<'cx, 'tcx> { + pub fn project_any(mut self) -> Self { + self.0.projection_mode = ProjectionMode::Any; + self + } + + pub fn project_any_final(mut self) -> Self { + self.0.projection_mode = ProjectionMode::AnyFinal; + self + } + + pub fn project_topmost(mut self) -> Self { + self.0.projection_mode = ProjectionMode::Topmost; + self + } + + pub fn build(self) -> SelectionContext<'cx, 'tcx> { + self.0 + } +} + +pub fn build_selcx<'cx, 'tcx>(infcx: &'cx InferCtxt<'cx, 'tcx>) -> SelectionContextBuilder<'cx, 'tcx> { + SelectionContextBuilder(SelectionContext::new(infcx)) +} + +impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { + pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>) -> SelectionContext<'cx, 'tcx> { SelectionContext { infcx: infcx, freshener: infcx.freshener(), - intercrate: true, + intercrate: false, + projection_mode: ProjectionMode::AnyFinal, } } @@ -292,6 +406,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.infcx } + pub fn projection_mode(&self) -> ProjectionMode { + self.projection_mode + } + /////////////////////////////////////////////////////////////////////////// // Selection // @@ -565,7 +683,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // this crate, perhaps the type would be unified with // something from another crate that does provide an impl. // - // In intracrate mode, we must still be conservative. The reason is + // In intra mode, we must still be conservative. The reason is // that we want to avoid cycles. Imagine an impl like: // // impl<T:Eq> Eq for Vec<T> @@ -780,7 +898,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } if !self.is_knowable(stack) { - debug!("intercrate not knowable"); + debug!("coherence stage: not knowable"); return Ok(None); } diff --git a/src/librustc/middle/traits/specialize.rs b/src/librustc/middle/traits/specialize.rs deleted file mode 100644 index 2c501c1a481..00000000000 --- a/src/librustc/middle/traits/specialize.rs +++ /dev/null @@ -1,454 +0,0 @@ -// Copyright 2015 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// Logic and data structures related to impl specialization, explained in -// greater detail below. -// -// At the moment, this implementation support only the simple "chain" rule: -// If any two impls overlap, one must be a strict subset of the other. -// -// See traits/README.md for a bit more detail on how specialization -// fits together with the rest of the trait machinery. - -use super::util; -use super::SelectionContext; - -use middle::cstore::CrateStore; -use middle::def_id::DefId; -use middle::infer::{self, InferCtxt, TypeOrigin}; -use middle::region; -use middle::subst::{Subst, Substs}; -use middle::traits; -use middle::ty::{self, ImplOrTraitItem}; -use syntax::codemap::DUMMY_SP; -use util::nodemap::DefIdMap; - -/// A per-trait graph of impls in specialization order. -/// -/// The graph provides two key services: -/// -/// - Construction, which implicitly checks for overlapping impls (i.e., impls -/// that overlap but where neither specializes the other -- an artifact of the -/// simple "chain" rule. -/// -/// - Parent extraction. In particular, the graph can give you the *immediate* -/// parents of a given specializing impl, which is needed for extracting -/// default items amongst other thigns. In the simple "chain" rule, every impl -/// has at most one parent. -pub struct SpecializationGraph { - // all impls have a parent; the "root" impls have as their parent the def_id - // of the trait - parent: DefIdMap<DefId>, - - // the "root" impls are found by looking up the trait's def_id. - children: DefIdMap<Vec<DefId>>, -} - -/// Information pertinent to an overlapping impl error. -pub struct Overlap<'a, 'tcx: 'a> { - pub in_context: InferCtxt<'a, 'tcx>, - pub with_impl: DefId, - pub on_trait_ref: ty::TraitRef<'tcx>, -} - -impl SpecializationGraph { - pub fn new() -> SpecializationGraph { - SpecializationGraph { - parent: Default::default(), - children: Default::default(), - } - } - - /// Insert a local impl into the specialization graph. If an existing impl - /// conflicts with it (has overlap, but neither specializes the other), - /// information about the area of overlap is returned in the `Err`. - pub fn insert<'a, 'tcx>(&mut self, - tcx: &'a ty::ctxt<'tcx>, - impl_def_id: DefId) - -> Result<(), Overlap<'a, 'tcx>> { - assert!(impl_def_id.is_local()); - - let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); - let mut parent = trait_ref.def_id; - let mut my_children = vec![]; - - // descend the existing tree, looking for the right location to add this impl - 'descend: loop { - let mut possible_siblings = self.children.entry(parent).or_insert(vec![]); - - for slot in possible_siblings.iter_mut() { - let possible_sibling = *slot; - - let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None); - let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id); - - if let Some(trait_ref) = overlap { - if !tcx.sess.features.borrow().specialization { - // if specialization is not turned on, all overlaps - // should immediately trigger an error - - return Err(Overlap { - with_impl: possible_sibling, - on_trait_ref: trait_ref, - in_context: infcx, - }); - } - - let le = specializes(tcx, impl_def_id, possible_sibling); - let ge = specializes(tcx, possible_sibling, impl_def_id); - - if le && !ge { - // the impl specializes possible_sibling - parent = possible_sibling; - continue 'descend; - } else if ge && !le { - // possible_sibling specializes the impl - *slot = impl_def_id; - self.parent.insert(possible_sibling, impl_def_id); - my_children.push(possible_sibling); - } else { - // overlap, but no specialization; error out - return Err(Overlap { - with_impl: possible_sibling, - on_trait_ref: trait_ref, - in_context: infcx, - }); - } - - break 'descend; - } - } - - // no overlap with any potential siblings, so add as a new sibling - self.parent.insert(impl_def_id, parent); - possible_siblings.push(impl_def_id); - break; - } - - if self.children.insert(impl_def_id, my_children).is_some() { - tcx.sess - .bug("When inserting an impl into the specialization graph, existing children for \ - the impl were already present."); - } - - Ok(()) - } - - /// Insert cached metadata mapping from a child impl back to its parent. - pub fn record_impl_from_cstore(&mut self, parent: DefId, child: DefId) { - if self.parent.insert(child, parent).is_some() { - panic!("When recording an impl from the crate store, information about its parent \ - was already present."); - } - - self.children.entry(parent).or_insert(vec![]).push(child); - } - - /// The parent of a given impl, which is the def id of the trait when the - /// impl is a "specialization root". - pub fn parent(&self, child: DefId) -> DefId { - *self.parent.get(&child).unwrap() - } -} - -/// When we have selected one impl, but are actually using item definitions from -/// a parent impl providing a default, we need a way to translate between the -/// type parameters of the two impls. Here the `source_impl` is the one we've -/// selected, and `source_substs` is a substitution of its generics (and possibly -/// some relevant `FnSpace` variables as well). And `target_impl` is the impl -/// we're actually going to get the definition from. -fn translate_substs_between_impls<'tcx>(tcx: &ty::ctxt<'tcx>, - source_impl: DefId, - source_substs: Substs<'tcx>, - target_impl: DefId) - -> Substs<'tcx> { - - // We need to build a subst that covers all the generics of - // `target_impl`. Start by introducing fresh infer variables: - let target_generics = tcx.lookup_item_type(target_impl).generics; - let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); - let mut target_substs = infcx.fresh_substs_for_generics(DUMMY_SP, &target_generics); - if source_substs.regions.is_erased() { - target_substs = target_substs.erase_regions() - } - - if !fulfill_implication(&mut infcx, - source_impl, - source_substs.clone(), - target_impl, - target_substs.clone()) { - tcx.sess - .bug("When translating substitutions for specialization, the expected specializaiton \ - failed to hold") - } - - // Now resolve the *substitution* we built for the target earlier, replacing - // the inference variables inside with whatever we got from fulfillment. We - // also carry along any FnSpace substitutions, which don't need to be - // adjusted when mapping from one impl to another. - infcx.resolve_type_vars_if_possible(&target_substs) - .with_method_from_subst(&source_substs) -} - -/// When we've selected an impl but need to use an item definition provided by -/// the trait itself, we need to translate the substitution applied to the impl -/// to one that makes sense for the trait. -fn translate_substs_from_impl_to_trait<'tcx>(tcx: &ty::ctxt<'tcx>, - source_impl: DefId, - source_substs: Substs<'tcx>) - -> Substs<'tcx> { - - let source_trait_ref = tcx.impl_trait_ref(source_impl).unwrap().subst(tcx, &source_substs); - - let mut new_substs = source_trait_ref.substs.clone(); - if source_substs.regions.is_erased() { - new_substs = new_substs.erase_regions() - } - - // Carry any FnSpace substitutions along; they don't need to be adjusted - new_substs.with_method_from_subst(&source_substs) -} - -#[derive(Debug, Copy, Clone)] -/// When looking up an item in an impl, it may turn out that the item -/// is actually provided as a default by a more generic impl, or by -/// the trait itself. This enum says where the item came from. -pub enum ItemSource { - Impl { - requested_impl: DefId, - actual_impl: DefId, - }, - Trait { - requested_impl: DefId, - }, -} - -impl ItemSource { - pub fn is_from_trait(&self) -> bool { - match *self { - ItemSource::Trait { .. } => true, - _ => false, - } - } - - /// Given a subst for the requested impl, translate it to a subst - /// appropriate for the actual item definition (whether it be in that impl, - /// a parent impl, or the trait). - pub fn translate_substs<'tcx>(&self, - tcx: &ty::ctxt<'tcx>, - requested_impl_substs: Substs<'tcx>) - -> Substs<'tcx> { - match *self { - ItemSource::Impl { requested_impl, actual_impl } => { - // no need to translate if we're targetting the impl we started with - if requested_impl == actual_impl { - return requested_impl_substs; - } - - translate_substs_between_impls(tcx, - requested_impl, - requested_impl_substs, - actual_impl) - - } - ItemSource::Trait { requested_impl } => { - translate_substs_from_impl_to_trait(tcx, requested_impl, requested_impl_substs) - } - } - } -} - -/// Lookup the definition of an item within `requested_impl` or its specialization -/// parents, including provided items from the trait itself. -/// -/// The closure `f` works in the style of `filter_map`. -pub fn get_impl_item_or_default<'tcx, I, F>(tcx: &ty::ctxt<'tcx>, - requested_impl: DefId, - mut f: F) - -> Option<(I, ItemSource)> - where F: for<'a> FnMut(&ImplOrTraitItem<'tcx>) -> Option<I> -{ - let impl_or_trait_items_map = tcx.impl_or_trait_items.borrow(); - let trait_def_id = tcx.trait_id_of_impl(requested_impl).unwrap(); - let trait_def = tcx.lookup_trait_def(trait_def_id); - - // Walk up the specialization tree, looking for a matching item definition - - let mut current_impl = requested_impl; - loop { - for impl_item_id in &tcx.impl_items.borrow()[¤t_impl] { - let impl_item = &impl_or_trait_items_map[&impl_item_id.def_id()]; - if let Some(t) = f(impl_item) { - let source = ItemSource::Impl { - requested_impl: requested_impl, - actual_impl: current_impl, - }; - return Some((t, source)); - } - } - - if let Some(parent) = trait_def.parent_of_impl(current_impl) { - current_impl = parent; - } else { - break; - } - } - - // The item isn't defined anywhere in the hierarchy. Get the - // default from the trait. - - for trait_item in tcx.trait_items(trait_def_id).iter() { - if let Some(t) = f(trait_item) { - return Some((t, ItemSource::Trait { requested_impl: requested_impl })); - } - } - - None -} - -/// Convenience function for locating an item defined in a specialization parent, if any. -pub fn get_parent_impl_item<'tcx, I, F>(tcx: &ty::ctxt<'tcx>, - child_impl: DefId, - f: F) - -> Option<(I, DefId)> - where F: for<'a> FnMut(&ImplOrTraitItem<'tcx>) -> Option<I> -{ - let trait_def_id = tcx.trait_id_of_impl(child_impl).unwrap(); - let trait_def = tcx.lookup_trait_def(trait_def_id); - - trait_def.parent_of_impl(child_impl) - .and_then(|parent_impl| get_impl_item_or_default(tcx, parent_impl, f)) - .and_then(|(item, source)| { - match source { - ItemSource::Trait { .. } => None, - ItemSource::Impl { actual_impl, .. } => Some((item, actual_impl)), - } - }) -} - -fn skolemizing_subst_for_impl<'a>(tcx: &ty::ctxt<'a>, impl_def_id: DefId) -> Substs<'a> { - let impl_generics = tcx.lookup_item_type(impl_def_id).generics; - - let types = impl_generics.types.map(|def| tcx.mk_param_from_def(def)); - - // FIXME: figure out what we actually want here - let regions = impl_generics.regions.map(|_| ty::Region::ReStatic); - // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name))); - - Substs::new(types, regions) -} - -/// Is impl1 a specialization of impl2? -/// -/// Specialization is determined by the sets of types to which the impls apply; -/// impl1 specializes impl2 if it applies to a subset of the types impl2 applies -/// to. -pub fn specializes(tcx: &ty::ctxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool { - // We determine whether there's a subset relationship by: - // - // - skolemizing impl1, - // - instantiating impl2 with fresh inference variables, - // - assuming the where clauses for impl1, - // - unifying, - // - attempting to prove the where clauses for impl2 - // - // The last three steps are essentially checking for an implication between two impls - // after appropriate substitutions. This is what `fulfill_implication` checks for. - // - // See RFC 1210 for more details and justification. - - let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); - - let impl1_substs = skolemizing_subst_for_impl(tcx, impl1_def_id); - let impl2_substs = util::fresh_type_vars_for_impl(&infcx, DUMMY_SP, impl2_def_id); - - fulfill_implication(&mut infcx, - impl1_def_id, - impl1_substs, - impl2_def_id, - impl2_substs) -} - -/// Does impl1 (instantiated with the impl1_substs) imply impl2 -/// (instantiated with impl2_substs)? -/// -/// Mutates the `infcx` in two ways: -/// - by adding the obligations of impl1 to the parameter environment -/// - via fulfillment, so that if the implication holds the various unifications -fn fulfill_implication<'a, 'tcx>(infcx: &mut InferCtxt<'a, 'tcx>, - impl1_def_id: DefId, - impl1_substs: Substs<'tcx>, - impl2_def_id: DefId, - impl2_substs: Substs<'tcx>) - -> bool { - let tcx = &infcx.tcx; - - let (impl1_trait_ref, impl1_obligations) = { - let selcx = &mut SelectionContext::new(&infcx); - util::impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs) - }; - - let impl1_predicates: Vec<_> = impl1_obligations.iter() - .cloned() - .map(|oblig| oblig.predicate) - .collect(); - - infcx.parameter_environment = ty::ParameterEnvironment { - tcx: tcx, - free_substs: impl1_substs, - implicit_region_bound: ty::ReEmpty, // FIXME: is this OK? - caller_bounds: impl1_predicates, - selection_cache: traits::SelectionCache::new(), - evaluation_cache: traits::EvaluationCache::new(), - free_id_outlive: region::DUMMY_CODE_EXTENT, // FIXME: is this OK? - }; - - let selcx = &mut SelectionContext::new(&infcx); - let (impl2_trait_ref, impl2_obligations) = util::impl_trait_ref_and_oblig(selcx, - impl2_def_id, - &impl2_substs); - - // do the impls unify? If not, no specialization. - if let Err(_) = infer::mk_eq_trait_refs(&infcx, - true, - TypeOrigin::Misc(DUMMY_SP), - impl1_trait_ref, - impl2_trait_ref) { - debug!("fulfill_implication: {:?} does not unify with {:?}", - impl1_trait_ref, - impl2_trait_ref); - return false; - } - - let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut(); - - // attempt to prove all of the predicates for impl2 given those for impl1 - // (which are packed up in penv) - - for oblig in impl2_obligations.into_iter() { - fulfill_cx.register_predicate_obligation(&infcx, oblig); - } - - if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) { - // no dice! - debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \ - {:?}", - impl1_trait_ref, - impl2_trait_ref, - errors, - infcx.parameter_environment.caller_bounds); - false - } else { - debug!("fulfill_implication: an impl for {:?} specializes {:?} (`where` clauses elided)", - impl1_trait_ref, - impl2_trait_ref); - true - } -} diff --git a/src/librustc/middle/traits/specialize/mod.rs b/src/librustc/middle/traits/specialize/mod.rs new file mode 100644 index 00000000000..2dc4926736e --- /dev/null +++ b/src/librustc/middle/traits/specialize/mod.rs @@ -0,0 +1,244 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Logic and data structures related to impl specialization, explained in +// greater detail below. +// +// At the moment, this implementation support only the simple "chain" rule: +// If any two impls overlap, one must be a strict subset of the other. +// +// See traits/README.md for a bit more detail on how specialization +// fits together with the rest of the trait machinery. + +use super::{util, build_selcx, SelectionContext}; + +use middle::cstore::CrateStore; +use middle::def_id::DefId; +use middle::infer::{self, InferCtxt, TypeOrigin}; +use middle::region; +use middle::subst::{Subst, Substs}; +use middle::traits; +use middle::ty; +use syntax::codemap::DUMMY_SP; + +pub mod specialization_graph; + +/// Information pertinent to an overlapping impl error. +pub struct Overlap<'a, 'tcx: 'a> { + pub in_context: InferCtxt<'a, 'tcx>, + pub with_impl: DefId, + pub on_trait_ref: ty::TraitRef<'tcx>, +} + +/// Given a subst for the requested impl, translate it to a subst +/// appropriate for the actual item definition (whether it be in that impl, +/// a parent impl, or the trait). +pub fn translate_substs<'tcx>(tcx: &ty::ctxt<'tcx>, + from_impl: DefId, + from_impl_substs: Substs<'tcx>, + to_node: specialization_graph::Node) + -> Substs<'tcx> { + match to_node { + specialization_graph::Node::Impl(to_impl) => { + // no need to translate if we're targetting the impl we started with + if from_impl == to_impl { + return from_impl_substs; + } + + translate_substs_between_impls(tcx, from_impl, from_impl_substs, to_impl) + + } + specialization_graph::Node::Trait(..) => { + translate_substs_from_impl_to_trait(tcx, from_impl, from_impl_substs) + } + } +} + +/// When we have selected one impl, but are actually using item definitions from +/// a parent impl providing a default, we need a way to translate between the +/// type parameters of the two impls. Here the `source_impl` is the one we've +/// selected, and `source_substs` is a substitution of its generics (and possibly +/// some relevant `FnSpace` variables as well). And `target_impl` is the impl +/// we're actually going to get the definition from. +fn translate_substs_between_impls<'tcx>(tcx: &ty::ctxt<'tcx>, + source_impl: DefId, + source_substs: Substs<'tcx>, + target_impl: DefId) + -> Substs<'tcx> { + + // We need to build a subst that covers all the generics of + // `target_impl`. Start by introducing fresh infer variables: + let target_generics = tcx.lookup_item_type(target_impl).generics; + let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); + let mut target_substs = infcx.fresh_substs_for_generics(DUMMY_SP, &target_generics); + if source_substs.regions.is_erased() { + target_substs = target_substs.erase_regions() + } + + if !fulfill_implication(&mut infcx, + source_impl, + source_substs.clone(), + target_impl, + target_substs.clone()) { + tcx.sess + .bug("When translating substitutions for specialization, the expected specializaiton \ + failed to hold") + } + + // Now resolve the *substitution* we built for the target earlier, replacing + // the inference variables inside with whatever we got from fulfillment. We + // also carry along any FnSpace substitutions, which don't need to be + // adjusted when mapping from one impl to another. + infcx.resolve_type_vars_if_possible(&target_substs) + .with_method_from_subst(&source_substs) +} + +/// When we've selected an impl but need to use an item definition provided by +/// the trait itself, we need to translate the substitution applied to the impl +/// to one that makes sense for the trait. +fn translate_substs_from_impl_to_trait<'tcx>(tcx: &ty::ctxt<'tcx>, + source_impl: DefId, + source_substs: Substs<'tcx>) + -> Substs<'tcx> { + + let source_trait_ref = tcx.impl_trait_ref(source_impl).unwrap().subst(tcx, &source_substs); + + let mut new_substs = source_trait_ref.substs.clone(); + if source_substs.regions.is_erased() { + new_substs = new_substs.erase_regions() + } + + // Carry any FnSpace substitutions along; they don't need to be adjusted + new_substs.with_method_from_subst(&source_substs) +} + +fn skolemizing_subst_for_impl<'a>(tcx: &ty::ctxt<'a>, impl_def_id: DefId) -> Substs<'a> { + let impl_generics = tcx.lookup_item_type(impl_def_id).generics; + + let types = impl_generics.types.map(|def| tcx.mk_param_from_def(def)); + + // FIXME: figure out what we actually want here + let regions = impl_generics.regions.map(|_| ty::Region::ReStatic); + // |d| infcx.next_region_var(infer::RegionVariableOrigin::EarlyBoundRegion(span, d.name))); + + Substs::new(types, regions) +} + +/// Is impl1 a specialization of impl2? +/// +/// Specialization is determined by the sets of types to which the impls apply; +/// impl1 specializes impl2 if it applies to a subset of the types impl2 applies +/// to. +pub fn specializes(tcx: &ty::ctxt, impl1_def_id: DefId, impl2_def_id: DefId) -> bool { + if !tcx.sess.features.borrow().specialization { + return false; + } + + // We determine whether there's a subset relationship by: + // + // - skolemizing impl1, + // - instantiating impl2 with fresh inference variables, + // - assuming the where clauses for impl1, + // - unifying, + // - attempting to prove the where clauses for impl2 + // + // The last three steps are essentially checking for an implication between two impls + // after appropriate substitutions. This is what `fulfill_implication` checks for. + // + // See RFC 1210 for more details and justification. + + let mut infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); + + let impl1_substs = skolemizing_subst_for_impl(tcx, impl1_def_id); + let impl2_substs = util::fresh_type_vars_for_impl(&infcx, DUMMY_SP, impl2_def_id); + + fulfill_implication(&mut infcx, + impl1_def_id, + impl1_substs, + impl2_def_id, + impl2_substs) +} + +/// Does impl1 (instantiated with the impl1_substs) imply impl2 +/// (instantiated with impl2_substs)? +/// +/// Mutates the `infcx` in two ways: +/// - by adding the obligations of impl1 to the parameter environment +/// - via fulfillment, so that if the implication holds the various unifications +fn fulfill_implication<'a, 'tcx>(infcx: &mut InferCtxt<'a, 'tcx>, + impl1_def_id: DefId, + impl1_substs: Substs<'tcx>, + impl2_def_id: DefId, + impl2_substs: Substs<'tcx>) + -> bool { + let tcx = &infcx.tcx; + + let (impl1_trait_ref, impl1_obligations) = { + let selcx = &mut SelectionContext::new(&infcx); + util::impl_trait_ref_and_oblig(selcx, impl1_def_id, &impl1_substs) + }; + + let impl1_predicates: Vec<_> = impl1_obligations.iter() + .cloned() + .map(|oblig| oblig.predicate) + .collect(); + + infcx.parameter_environment = ty::ParameterEnvironment { + tcx: tcx, + free_substs: impl1_substs, + implicit_region_bound: ty::ReEmpty, // FIXME: is this OK? + caller_bounds: impl1_predicates, + selection_cache: traits::SelectionCache::new(), + evaluation_cache: traits::EvaluationCache::new(), + free_id_outlive: region::DUMMY_CODE_EXTENT, // FIXME: is this OK? + }; + + let selcx = &mut build_selcx(&infcx).project_topmost().build(); + let (impl2_trait_ref, impl2_obligations) = util::impl_trait_ref_and_oblig(selcx, + impl2_def_id, + &impl2_substs); + + // do the impls unify? If not, no specialization. + if let Err(_) = infer::mk_eq_trait_refs(&infcx, + true, + TypeOrigin::Misc(DUMMY_SP), + impl1_trait_ref, + impl2_trait_ref) { + debug!("fulfill_implication: {:?} does not unify with {:?}", + impl1_trait_ref, + impl2_trait_ref); + return false; + } + + let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut(); + + // attempt to prove all of the predicates for impl2 given those for impl1 + // (which are packed up in penv) + + for oblig in impl2_obligations.into_iter() { + fulfill_cx.register_predicate_obligation(&infcx, oblig); + } + + if let Err(errors) = infer::drain_fulfillment_cx(&infcx, &mut fulfill_cx, &()) { + // no dice! + debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \ + {:?}", + impl1_trait_ref, + impl2_trait_ref, + errors, + infcx.parameter_environment.caller_bounds); + false + } else { + debug!("fulfill_implication: an impl for {:?} specializes {:?} (`where` clauses elided)", + impl1_trait_ref, + impl2_trait_ref); + true + } +} diff --git a/src/librustc/middle/traits/specialize/specialization_graph.rs b/src/librustc/middle/traits/specialize/specialization_graph.rs new file mode 100644 index 00000000000..01f3b6333f8 --- /dev/null +++ b/src/librustc/middle/traits/specialize/specialization_graph.rs @@ -0,0 +1,382 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use std::cell; +use std::rc::Rc; + +use super::{Overlap, specializes}; + +use middle::cstore::CrateStore; +use middle::def_id::DefId; +use middle::infer; +use middle::traits; +use middle::ty::{self, ImplOrTraitItem, TraitDef, TypeFoldable}; +use syntax::ast::Name; +use util::nodemap::DefIdMap; + +/// A per-trait graph of impls in specialization order. At the moment, this +/// graph forms a tree rooted with the trait itself, with all other nodes +/// representing impls, and parent-child relationships representing +/// specializations. +/// +/// The graph provides two key services: +/// +/// - Construction, which implicitly checks for overlapping impls (i.e., impls +/// that overlap but where neither specializes the other -- an artifact of the +/// simple "chain" rule. +/// +/// - Parent extraction. In particular, the graph can give you the *immediate* +/// parents of a given specializing impl, which is needed for extracting +/// default items amongst other thigns. In the simple "chain" rule, every impl +/// has at most one parent. +pub struct Graph { + // all impls have a parent; the "root" impls have as their parent the def_id + // of the trait + parent: DefIdMap<DefId>, + + // the "root" impls are found by looking up the trait's def_id. + children: DefIdMap<Vec<DefId>>, +} + +impl Graph { + pub fn new() -> Graph { + Graph { + parent: Default::default(), + children: Default::default(), + } + } + + /// Insert a local impl into the specialization graph. If an existing impl + /// conflicts with it (has overlap, but neither specializes the other), + /// information about the area of overlap is returned in the `Err`. + pub fn insert<'a, 'tcx>(&mut self, + tcx: &'a ty::ctxt<'tcx>, + impl_def_id: DefId) + -> Result<(), Overlap<'a, 'tcx>> { + assert!(impl_def_id.is_local()); + + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let trait_def_id = trait_ref.def_id; + + // if the reference itself contains an earlier error (e.g., due to a + // resolution failure), then we just insert the impl at the top level of + // the graph and claim that there's no overlap (in order to supress + // bogus errors). + if trait_ref.references_error() { + debug!("Inserting dummy node for erroneous TraitRef {:?}, \ + impl_def_id={:?}, trait_def_id={:?}", + trait_ref, impl_def_id, trait_def_id); + + self.parent.insert(impl_def_id, trait_def_id); + self.children.entry(trait_def_id).or_insert(vec![]).push(impl_def_id); + return Ok(()); + } + + let mut parent = trait_def_id; + + // Ugly hack around borrowck limitations. Assigned only in the case + // where we bump downward an existing node in the graph. + let child_to_insert; + + 'descend: loop { + let mut possible_siblings = self.children.entry(parent).or_insert(vec![]); + + for slot in possible_siblings.iter_mut() { + let possible_sibling = *slot; + + let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None); + let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id); + + if let Some(trait_ref) = overlap { + let le = specializes(tcx, impl_def_id, possible_sibling); + let ge = specializes(tcx, possible_sibling, impl_def_id); + + if le && !ge { + // the impl specializes possible_sibling + parent = possible_sibling; + continue 'descend; + } else if ge && !le { + // possible_sibling specializes the impl + *slot = impl_def_id; + self.parent.insert(possible_sibling, impl_def_id); + // we have to defer the insertion, because we can't + // relinquish the borrow of `self.children` + child_to_insert = possible_sibling; + break 'descend; + } else { + // overlap, but no specialization; error out + return Err(Overlap { + with_impl: possible_sibling, + on_trait_ref: trait_ref, + in_context: infcx, + }); + } + } + } + + // no overlap with any potential siblings, so add as a new sibling + self.parent.insert(impl_def_id, parent); + possible_siblings.push(impl_def_id); + return Ok(()); + } + + self.children.insert(impl_def_id, vec![child_to_insert]); + Ok(()) + } + + /// Insert cached metadata mapping from a child impl back to its parent. + pub fn record_impl_from_cstore(&mut self, parent: DefId, child: DefId) { + if self.parent.insert(child, parent).is_some() { + panic!("When recording an impl from the crate store, information about its parent \ + was already present."); + } + + self.children.entry(parent).or_insert(vec![]).push(child); + } + + /// The parent of a given impl, which is the def id of the trait when the + /// impl is a "specialization root". + pub fn parent(&self, child: DefId) -> DefId { + *self.parent.get(&child).unwrap() + } +} + +#[derive(Debug, Copy, Clone)] +/// A node in the specialization graph is either an impl or a trait +/// definition; either can serve as a source of item definitions. +/// There is always exactly one trait definition node: the root. +pub enum Node { + Impl(DefId), + Trait(DefId), +} + +impl Node { + pub fn is_from_trait(&self) -> bool { + match *self { + Node::Trait(..) => true, + _ => false, + } + } + + /// Iterate over the items defined directly by the given (impl or trait) node. + pub fn items<'a, 'tcx>(&self, tcx: &'a ty::ctxt<'tcx>) -> NodeItems<'a, 'tcx> { + match *self { + Node::Impl(impl_def_id) => { + NodeItems::Impl { + tcx: tcx, + items: cell::Ref::map(tcx.impl_items.borrow(), + |impl_items| &impl_items[&impl_def_id]), + idx: 0, + } + } + Node::Trait(trait_def_id) => { + NodeItems::Trait { + items: tcx.trait_items(trait_def_id).clone(), + idx: 0, + } + } + } + } + + pub fn def_id(&self) -> DefId { + match *self { + Node::Impl(did) => did, + Node::Trait(did) => did, + } + } +} + +/// An iterator over the items defined within a trait or impl. +pub enum NodeItems<'a, 'tcx: 'a> { + Impl { + tcx: &'a ty::ctxt<'tcx>, + items: cell::Ref<'a, Vec<ty::ImplOrTraitItemId>>, + idx: usize, + }, + Trait { + items: Rc<Vec<ImplOrTraitItem<'tcx>>>, + idx: usize, + }, +} + +impl<'a, 'tcx> Iterator for NodeItems<'a, 'tcx> { + type Item = ImplOrTraitItem<'tcx>; + fn next(&mut self) -> Option<ImplOrTraitItem<'tcx>> { + match *self { + NodeItems::Impl { tcx, ref items, ref mut idx } => { + let items_table = tcx.impl_or_trait_items.borrow(); + if *idx < items.len() { + let item_def_id = items[*idx].def_id(); + let item = items_table[&item_def_id].clone(); + *idx += 1; + Some(item) + } else { + None + } + } + NodeItems::Trait { ref items, ref mut idx } => { + if *idx < items.len() { + let item = items[*idx].clone(); + *idx += 1; + Some(item) + } else { + None + } + } + } + } +} + +pub struct Ancestors<'a, 'tcx: 'a> { + trait_def: &'a TraitDef<'tcx>, + current_source: Option<Node>, +} + +impl<'a, 'tcx> Iterator for Ancestors<'a, 'tcx> { + type Item = Node; + fn next(&mut self) -> Option<Node> { + let cur = self.current_source.take(); + if let Some(Node::Impl(cur_impl)) = cur { + let parent = self.trait_def.specialization_graph.borrow().parent(cur_impl); + if parent == self.trait_def.def_id() { + self.current_source = Some(Node::Trait(parent)); + } else { + self.current_source = Some(Node::Impl(parent)); + } + } + cur + } +} + +pub struct NodeItem<T> { + pub node: Node, + pub item: T, +} + +impl<T> NodeItem<T> { + pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> { + NodeItem { + node: self.node, + item: f(self.item), + } + } +} + +pub struct TypeDefs<'a, 'tcx: 'a> { + // generally only invoked once or twice, so the box doesn't hurt + iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>> + 'a>, +} + +impl<'a, 'tcx> Iterator for TypeDefs<'a, 'tcx> { + type Item = NodeItem<Rc<ty::AssociatedType<'tcx>>>; + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + +pub struct FnDefs<'a, 'tcx: 'a> { + // generally only invoked once or twice, so the box doesn't hurt + iter: Box<Iterator<Item = NodeItem<Rc<ty::Method<'tcx>>>> + 'a>, +} + +impl<'a, 'tcx> Iterator for FnDefs<'a, 'tcx> { + type Item = NodeItem<Rc<ty::Method<'tcx>>>; + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + +pub struct ConstDefs<'a, 'tcx: 'a> { + // generally only invoked once or twice, so the box doesn't hurt + iter: Box<Iterator<Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>> + 'a>, +} + +impl<'a, 'tcx> Iterator for ConstDefs<'a, 'tcx> { + type Item = NodeItem<Rc<ty::AssociatedConst<'tcx>>>; + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + +impl<'a, 'tcx> Ancestors<'a, 'tcx> { + /// Seach the items from the given ancestors, returning each type definition + /// with the given name. + pub fn type_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> TypeDefs<'a, 'tcx> { + let iter = self.flat_map(move |node| { + node.items(tcx) + .filter_map(move |item| { + if let ty::TypeTraitItem(assoc_ty) = item { + if assoc_ty.name == name { + return Some(NodeItem { + node: node, + item: assoc_ty, + }); + } + } + None + }) + + }); + TypeDefs { iter: Box::new(iter) } + } + + /// Seach the items from the given ancestors, returning each fn definition + /// with the given name. + pub fn fn_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> FnDefs<'a, 'tcx> { + let iter = self.flat_map(move |node| { + node.items(tcx) + .filter_map(move |item| { + if let ty::MethodTraitItem(method) = item { + if method.name == name { + return Some(NodeItem { + node: node, + item: method, + }); + } + } + None + }) + + }); + FnDefs { iter: Box::new(iter) } + } + + /// Seach the items from the given ancestors, returning each const + /// definition with the given name. + pub fn const_defs(self, tcx: &'a ty::ctxt<'tcx>, name: Name) -> ConstDefs<'a, 'tcx> { + let iter = self.flat_map(move |node| { + node.items(tcx) + .filter_map(move |item| { + if let ty::ConstTraitItem(konst) = item { + if konst.name == name { + return Some(NodeItem { + node: node, + item: konst, + }); + } + } + None + }) + + }); + ConstDefs { iter: Box::new(iter) } + } +} + +/// Walk up the specialization ancestors of a given impl, starting with that +/// impl itself. +pub fn ancestors<'a, 'tcx>(trait_def: &'a TraitDef<'tcx>, + start_from_impl: DefId) + -> Ancestors<'a, 'tcx> { + Ancestors { + trait_def: trait_def, + current_source: Some(Node::Impl(start_from_impl)), + } +} diff --git a/src/librustc/middle/ty/trait_def.rs b/src/librustc/middle/ty/trait_def.rs index 85cea4d8096..c4e820bde8f 100644 --- a/src/librustc/middle/ty/trait_def.rs +++ b/src/librustc/middle/ty/trait_def.rs @@ -10,7 +10,7 @@ use dep_graph::DepNode; use middle::def_id::DefId; -use middle::traits; +use middle::traits::{self, specialization_graph}; use middle::ty; use middle::ty::fast_reject; use middle::ty::{Ty, TyCtxt, TraitRef}; @@ -61,7 +61,7 @@ pub struct TraitDef<'tcx> { blanket_impls: RefCell<Vec<DefId>>, /// The specialization order for impls of this trait. - pub specialization_graph: RefCell<traits::SpecializationGraph>, + pub specialization_graph: RefCell<traits::specialization_graph::Graph>, /// Various flags pub flags: Cell<TraitFlags> @@ -83,7 +83,7 @@ impl<'tcx> TraitDef<'tcx> { nonblanket_impls: RefCell::new(FnvHashMap()), blanket_impls: RefCell::new(vec![]), flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS), - specialization_graph: RefCell::new(traits::SpecializationGraph::new()), + specialization_graph: RefCell::new(traits::specialization_graph::Graph::new()), } } @@ -170,7 +170,7 @@ impl<'tcx> TraitDef<'tcx> { /// Records a trait-to-implementation mapping for a non-local impl. /// /// The `parent_impl` is the immediately-less-specialized impl, or the - /// trait's def ID if the impl is maximally-specialized -- information that + /// trait's def ID if the impl is is not a specialization -- information that /// should be pulled from the metadata. pub fn record_remote_impl(&self, tcx: &TyCtxt<'tcx>, @@ -201,10 +201,8 @@ impl<'tcx> TraitDef<'tcx> { .insert(tcx, impl_def_id) } - /// Returns the immediately less specialized impl, if any. - pub fn parent_of_impl(&self, impl_def_id: DefId) -> Option<DefId> { - let parent = self.specialization_graph.borrow().parent(impl_def_id); - if parent == self.trait_ref.def_id { None } else { Some(parent) } + pub fn ancestors<'a>(&'a self, of_impl: DefId) -> specialization_graph::Ancestors<'a, 'tcx> { + specialization_graph::ancestors(self, of_impl) } pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &TyCtxt<'tcx>, mut f: F) { diff --git a/src/librustc_data_structures/obligation_forest/README.md b/src/librustc_data_structures/obligation_forest/README.md index d76d7f6ba34..982a2bacce1 100644 --- a/src/librustc_data_structures/obligation_forest/README.md +++ b/src/librustc_data_structures/obligation_forest/README.md @@ -60,7 +60,7 @@ which includes three bits of information: `process_obligations` would simply yield back further ambiguous results. This is used by the `FulfillmentContext` to decide when it has reached a steady state. - + #### Snapshots The `ObligationForest` supports a limited form of snapshots; see @@ -79,5 +79,3 @@ parent and (for convenience) its root (which may be itself). It also has a current state, described by `NodeState`. After each processing step, we compress the vector to remove completed and error nodes, which aren't needed anymore. - - diff --git a/src/librustc_front/hir.rs b/src/librustc_front/hir.rs index 939b527fad3..0b1418fc878 100644 --- a/src/librustc_front/hir.rs +++ b/src/librustc_front/hir.rs @@ -1053,6 +1053,16 @@ pub enum Defaultness { Final, } +impl Defaultness { + pub fn is_final(&self) -> bool { + *self == Defaultness::Final + } + + pub fn is_default(&self) -> bool { + *self == Defaultness::Default + } +} + impl fmt::Display for Unsafety { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Display::fmt(match *self { diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs index bbe9d0ea4c6..707657cfa26 100644 --- a/src/librustc_metadata/encoder.rs +++ b/src/librustc_metadata/encoder.rs @@ -1171,7 +1171,14 @@ fn encode_info_for_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>, if let Some(trait_ref) = tcx.impl_trait_ref(did) { encode_trait_ref(rbml_w, ecx, trait_ref, tag_item_trait_ref); - let parent = tcx.lookup_trait_def(trait_ref.def_id).parent_of_impl(did); + let trait_def = tcx.lookup_trait_def(trait_ref.def_id); + let parent = trait_def.ancestors(did) + .skip(1) + .next() + .and_then(|node| match node { + specialization_graph::Node::Impl(parent) => Some(parent), + _ => None, + }); encode_parent_impl(rbml_w, parent); } encode_path(rbml_w, path.clone()); diff --git a/src/librustc_trans/trans/common.rs b/src/librustc_trans/trans/common.rs index 34ef4f4acec..dd144de6ec5 100644 --- a/src/librustc_trans/trans/common.rs +++ b/src/librustc_trans/trans/common.rs @@ -1138,7 +1138,7 @@ pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, // Do the initial selection for the obligation. This yields the // shallow result we are looking for -- that is, what specific impl. let infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); - let mut selcx = traits::SelectionContext::new(&infcx); + let mut selcx = traits::build_selcx(&infcx).project_any().build(); let obligation = traits::Obligation::new(traits::ObligationCause::misc(span, ast::DUMMY_NODE_ID), @@ -1199,7 +1199,7 @@ pub fn normalize_and_test_predicates<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, let tcx = ccx.tcx(); let infcx = infer::normalizing_infer_ctxt(tcx, &tcx.tables); - let mut selcx = traits::SelectionContext::new(&infcx); + let mut selcx = traits::build_selcx(&infcx).project_any().build(); let mut fulfill_cx = traits::FulfillmentContext::new(); let cause = traits::ObligationCause::dummy(); let traits::Normalized { value: predicates, obligations } = diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs index 072c1dfaa1d..2f5f052a72a 100644 --- a/src/librustc_trans/trans/meth.rs +++ b/src/librustc_trans/trans/meth.rs @@ -486,21 +486,19 @@ pub fn get_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>, { assert!(!substs.types.needs_infer()); - traits::get_impl_item_or_default(tcx, impl_def_id, |cand| { - if let &ty::MethodTraitItem(ref meth) = cand { - if meth.name == name { - return Some(meth.clone()) + let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap(); + let trait_def = tcx.lookup_trait_def(trait_def_id); + + match trait_def.ancestors(impl_def_id).fn_defs(tcx, name).next() { + Some(node_item) => { + ImplMethod { + method: node_item.item, + substs: traits::translate_substs(tcx, impl_def_id, substs, node_item.node), + is_provided: node_item.node.is_from_trait(), } } - None - }).map(|(meth, source)| { - ImplMethod { - method: meth, - substs: source.translate_substs(tcx, substs), - is_provided: source.is_from_trait(), + None => { + tcx.sess.bug(&format!("method {:?} not found in {:?}", name, impl_def_id)) } - }).unwrap_or_else(|| { - tcx.sess.bug(&format!("method {:?} not found in {:?}", - name, impl_def_id)) - }) + } } diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index 51b88612fe4..bb94d80474a 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -127,7 +127,7 @@ use syntax::util::lev_distance::find_best_match_for_name; use rustc_front::intravisit::{self, Visitor}; use rustc_front::hir; -use rustc_front::hir::{Visibility, PatKind, Defaultness}; +use rustc_front::hir::{Visibility, PatKind}; use rustc_front::print::pprust; use rustc_back::slice; @@ -864,33 +864,56 @@ fn check_method_body<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, check_bare_fn(ccx, &sig.decl, body, id, span, fty, param_env); } -fn check_specialization_validity<'tcx, F>(tcx: &ty::ctxt<'tcx>, - impl_id: DefId, - impl_item: &hir::ImplItem, - f: F) - where F: FnMut(&ty::ImplOrTraitItem<'tcx>) -> Option<hir::Defaultness> +fn report_forbidden_specialization(tcx: &ty::ctxt, + impl_item: &hir::ImplItem, + parent_impl: DefId) { - let parent_item_opt = traits::get_parent_impl_item(tcx, impl_id, f); - if let Some((Defaultness::Final, parent_impl)) = parent_item_opt { - let mut err = struct_span_err!( - tcx.sess, impl_item.span, E0520, - "item `{}` is provided by an implementation that \ - specializes another, but the item in the parent \ - implementations is not marked `default` and so it \ - cannot be specialized.", - impl_item.name); - - match tcx.span_of_impl(parent_impl) { - Ok(span) => { - err.span_note(span, "parent implementation is here:"); - } - Err(cname) => { - err.note(&format!("parent implementation is in crate `{}`", cname)); - } + let mut err = struct_span_err!( + tcx.sess, impl_item.span, E0520, + "item `{}` is provided by an implementation that specializes \ + another, but the item in the parent implementations is not \ + marked `default` and so it cannot be specialized.", + impl_item.name); + + match tcx.span_of_impl(parent_impl) { + Ok(span) => { + err.span_note(span, "parent implementation is here:"); } + Err(cname) => { + err.note(&format!("parent implementation is in crate `{}`", cname)); + } + } - err.emit(); + err.emit(); +} + +fn check_specialization_validity<'tcx>(tcx: &ty::ctxt<'tcx>, trait_def: &ty::TraitDef<'tcx>, + impl_id: DefId, impl_item: &hir::ImplItem) +{ + let ancestors = trait_def.ancestors(impl_id); + + let parent = match impl_item.node { + hir::ImplItemKind::Const(..) => { + ancestors.const_defs(tcx, impl_item.name).skip(1).next() + .map(|node_item| node_item.map(|parent| parent.defaultness)) + } + hir::ImplItemKind::Method(..) => { + ancestors.fn_defs(tcx, impl_item.name).skip(1).next() + .map(|node_item| node_item.map(|parent| parent.defaultness)) + + } + hir::ImplItemKind::Type(_) => { + ancestors.type_defs(tcx, impl_item.name).skip(1).next() + .map(|node_item| node_item.map(|parent| parent.defaultness)) + } + }; + + if let Some(parent) = parent { + if parent.item.is_final() { + report_forbidden_specialization(tcx, impl_item, parent.node.def_id()); + } } + } fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, @@ -898,8 +921,14 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, impl_id: DefId, impl_trait_ref: &ty::TraitRef<'tcx>, impl_items: &[hir::ImplItem]) { - // Locate trait methods + // If the trait reference itself is erroneous (so the compilation is going + // to fail), skip checking the items here -- the `impl_item` table in `tcx` + // isn't populated for such impls. + if impl_trait_ref.references_error() { return; } + + // Locate trait definition and items let tcx = ccx.tcx; + let trait_def = tcx.lookup_trait_def(impl_trait_ref.def_id); let trait_items = tcx.trait_items(impl_trait_ref.def_id); let mut overridden_associated_type = None; @@ -910,6 +939,7 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, let ty_trait_item = trait_items.iter() .find(|ac| ac.name() == ty_impl_item.name()); + // Check that impl definition matches trait definition if let Some(ty_trait_item) = ty_trait_item { match impl_item.node { hir::ImplItemKind::Const(..) => { @@ -932,15 +962,6 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, impl_const.name, impl_trait_ref) } - - check_specialization_validity(ccx.tcx, impl_id, impl_item, |cand| { - if let &ty::ConstTraitItem(ref trait_const) = cand { - if trait_const.name == impl_item.name { - return Some(trait_const.defaultness); - } - } - None - }); } hir::ImplItemKind::Method(ref sig, ref body) => { check_trait_fn_not_const(ccx, impl_item.span, sig.constness); @@ -964,15 +985,6 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, impl_method.name, impl_trait_ref) } - - check_specialization_validity(ccx.tcx, impl_id, impl_item, |cand| { - if let &ty::MethodTraitItem(ref meth) = cand { - if meth.name == impl_method.name { - return Some(meth.defaultness); - } - } - None - }); } hir::ImplItemKind::Type(_) => { let impl_type = match ty_impl_item { @@ -991,18 +1003,11 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, impl_type.name, impl_trait_ref) } - - check_specialization_validity(ccx.tcx, impl_id, impl_item, |cand| { - if let &ty::TypeTraitItem(ref at) = cand { - if at.name == impl_item.name { - return Some(at.defaultness); - } - } - None - }); } } } + + check_specialization_validity(tcx, trait_def, impl_id, impl_item); } // Check for missing items from trait @@ -1011,9 +1016,13 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, let mut invalidated_items = Vec::new(); let associated_type_overridden = overridden_associated_type.is_some(); for trait_item in trait_items.iter() { + let is_implemented; + let is_provided; + match *trait_item { ty::ConstTraitItem(ref associated_const) => { - let is_implemented = impl_items.iter().any(|ii| { + is_provided = associated_const.has_value; + is_implemented = impl_items.iter().any(|ii| { match ii.node { hir::ImplItemKind::Const(..) => { ii.name == associated_const.name @@ -1021,57 +1030,30 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, _ => false, } }); - let is_provided = associated_const.has_value; - - if !is_implemented { - if !is_provided { - missing_items.push(associated_const.name); - } else if associated_type_overridden { - invalidated_items.push(associated_const.name); - } - } } ty::MethodTraitItem(ref trait_method) => { - let search_result = traits::get_impl_item_or_default(tcx, impl_id, |cand| { - if let &ty::MethodTraitItem(ref meth) = cand { - if meth.name == trait_method.name { - return Some(()); - } - } - None - }); - - if let Some((_, source)) = search_result { - if source.is_from_trait() { - let is_provided = - provided_methods.iter().any(|m| m.name == trait_method.name); - if !is_provided { - missing_items.push(trait_method.name); - } else if associated_type_overridden { - invalidated_items.push(trait_method.name); - } - } - } else { - missing_items.push(trait_method.name); - } + is_provided = provided_methods.iter().any(|m| m.name == trait_method.name); + is_implemented = trait_def.ancestors(impl_id) + .fn_defs(tcx, trait_method.name) + .next() + .map(|node_item| !node_item.node.is_from_trait()) + .unwrap_or(false); } ty::TypeTraitItem(ref trait_assoc_ty) => { - let search_result = traits::get_impl_item_or_default(tcx, impl_id, |cand| { - if let &ty::TypeTraitItem(ref assoc_ty) = cand { - if assoc_ty.name == trait_assoc_ty.name && assoc_ty.ty.is_some() { - return Some(()); - } - } - None - }); + is_provided = trait_assoc_ty.ty.is_some(); + is_implemented = trait_def.ancestors(impl_id) + .type_defs(tcx, trait_assoc_ty.name) + .next() + .map(|node_item| !node_item.node.is_from_trait()) + .unwrap_or(false); + } + } - if let Some((_, source)) = search_result { - if source.is_from_trait() && associated_type_overridden { - invalidated_items.push(trait_assoc_ty.name); - } - } else { - missing_items.push(trait_assoc_ty.name); - } + if !is_implemented { + if !is_provided { + missing_items.push(trait_item.name()); + } else if associated_type_overridden { + invalidated_items.push(trait_item.name()); } } } diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs index 1ebc131224d..4a5dbe20b78 100644 --- a/src/librustc_typeck/coherence/overlap.rs +++ b/src/librustc_typeck/coherence/overlap.rs @@ -128,7 +128,8 @@ impl<'cx, 'tcx,'v> intravisit::Visitor<'v> for OverlapChecker<'cx, 'tcx> { let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap(); let trait_def_id = trait_ref.def_id; - let _task = self.tcx.dep_graph.in_task(DepNode::CoherenceOverlapCheck(trait_def_id)); + let _task = self.tcx.dep_graph.in_task( + DepNode::CoherenceOverlapCheck(trait_def_id)); let def = self.tcx.lookup_trait_def(trait_def_id); @@ -161,7 +162,8 @@ impl<'cx, 'tcx,'v> intravisit::Visitor<'v> for OverlapChecker<'cx, 'tcx> { err.span_note(span, "conflicting implementation is here:"); } Err(cname) => { - err.note(&format!("conflicting implementation in crate `{}`", cname)); + err.note(&format!("conflicting implementation in crate `{}`", + cname)); } } diff --git a/src/test/compile-fail/specialization-no-default.rs b/src/test/compile-fail/specialization-no-default.rs index 06a01f0ca05..88cd00e69c4 100644 --- a/src/test/compile-fail/specialization-no-default.rs +++ b/src/test/compile-fail/specialization-no-default.rs @@ -65,7 +65,7 @@ impl<T: Clone> Baz for T { } impl Baz for i32 { - fn baz(&self) {} + fn baz(&self) {} //~ ERROR E0520 } //////////////////////////////////////////////////////////////////////////////// @@ -86,7 +86,7 @@ impl<T: Clone> Redundant for T { } impl Redundant for i32 { - default fn redundant(&self) {} + default fn redundant(&self) {} //~ ERROR E0520 } fn main() {} |