diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc/middle/traits/coherence.rs | 203 | ||||
| -rw-r--r-- | src/librustc/middle/traits/select.rs | 103 | ||||
| -rw-r--r-- | src/librustc/middle/traits/util.rs | 38 | ||||
| -rw-r--r-- | src/librustc/middle/ty.rs | 27 | ||||
| -rw-r--r-- | src/librustc/middle/ty_walk.rs | 117 | ||||
| -rw-r--r-- | src/librustc/util/ppaux.rs | 8 | ||||
| -rw-r--r-- | src/libsyntax/feature_gate.rs | 6 |
7 files changed, 337 insertions, 165 deletions
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs index 11d073ce72e..411be28b896 100644 --- a/src/librustc/middle/traits/coherence.rs +++ b/src/librustc/middle/traits/coherence.rs @@ -17,15 +17,17 @@ use super::PredicateObligation; use super::project; use super::util; -use middle::subst::{Subst, TypeSpace}; +use middle::subst::{Subst, Substs, TypeSpace}; use middle::ty::{self, ToPolyTraitRef, Ty}; use middle::infer::{self, InferCtxt}; -use std::collections::HashSet; use std::rc::Rc; use syntax::ast; -use syntax::codemap::DUMMY_SP; +use syntax::codemap::{DUMMY_SP, Span}; use util::ppaux::Repr; +#[derive(Copy)] +struct ParamIsLocal(bool); + /// True if there exist types that satisfy both of the two given impls. pub fn overlapping_impls(infcx: &InferCtxt, impl1_def_id: ast::DefId, @@ -56,10 +58,16 @@ fn overlap(selcx: &mut SelectionContext, a_def_id.repr(selcx.tcx()), b_def_id.repr(selcx.tcx())); - let (a_trait_ref, a_obligations) = impl_trait_ref_and_oblig(selcx, a_def_id); - let (b_trait_ref, b_obligations) = impl_trait_ref_and_oblig(selcx, b_def_id); + let (a_trait_ref, a_obligations) = impl_trait_ref_and_oblig(selcx, + a_def_id, + util::free_substs_for_impl); + + let (b_trait_ref, b_obligations) = impl_trait_ref_and_oblig(selcx, + b_def_id, + util::fresh_type_vars_for_impl); debug!("overlap: a_trait_ref={}", a_trait_ref.repr(selcx.tcx())); + debug!("overlap: b_trait_ref={}", b_trait_ref.repr(selcx.tcx())); // Does `a <: b` hold? If not, no overlap. @@ -74,28 +82,68 @@ fn overlap(selcx: &mut SelectionContext, debug!("overlap: subtraitref check succeeded"); // Are any of the obligations unsatisfiable? If so, no overlap. + let tcx = selcx.tcx(); + let infcx = selcx.infcx(); let opt_failing_obligation = a_obligations.iter() .chain(b_obligations.iter()) + .map(|o| infcx.resolve_type_vars_if_possible(o)) .find(|o| !selcx.evaluate_obligation(o)); if let Some(failing_obligation) = opt_failing_obligation { - debug!("overlap: obligation unsatisfiable {}", failing_obligation.repr(selcx.tcx())); - return false; + debug!("overlap: obligation unsatisfiable {}", failing_obligation.repr(tcx)); + return false } true } +pub fn trait_ref_is_knowable<'tcx>(tcx: &ty::ctxt<'tcx>, trait_ref: &ty::TraitRef<'tcx>) -> bool +{ + debug!("trait_ref_is_knowable(trait_ref={})", trait_ref.repr(tcx)); + + // if the orphan rules pass, that means that no ancestor crate can + // impl this, so it's up to us. + if orphan_check_trait_ref(tcx, trait_ref, ParamIsLocal(false)).is_ok() { + debug!("trait_ref_is_knowable: orphan check passed"); + return true; + } + + // if the trait is not marked fundamental, then it's always possible that + // an ancestor crate will impl this in the future, if they haven't + // already + if + trait_ref.def_id.krate != ast::LOCAL_CRATE && + !ty::has_attr(tcx, trait_ref.def_id, "fundamental") + { + debug!("trait_ref_is_knowable: trait is neither local nor fundamental"); + return false; + } + + // find out when some downstream (or cousin) crate could impl this + // trait-ref, presuming that all the parameters were instantiated + // with downstream types. If not, then it could only be + // implemented by an upstream crate, which means that the impl + // must be visible to us, and -- since the trait is fundamental + // -- we can test. + orphan_check_trait_ref(tcx, trait_ref, ParamIsLocal(true)).is_err() +} + +type SubstsFn = for<'a,'tcx> fn(infcx: &InferCtxt<'a, 'tcx>, + span: Span, + impl_def_id: ast::DefId) + -> Substs<'tcx>; + /// Instantiate fresh variables for all bound parameters of the impl /// and return the impl trait ref with those variables substituted. fn impl_trait_ref_and_oblig<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>, - impl_def_id: ast::DefId) + impl_def_id: ast::DefId, + substs_fn: SubstsFn) -> (Rc<ty::TraitRef<'tcx>>, Vec<PredicateObligation<'tcx>>) { let impl_substs = - &util::fresh_substs_for_impl(selcx.infcx(), DUMMY_SP, impl_def_id); + &substs_fn(selcx.infcx(), DUMMY_SP, impl_def_id); let impl_trait_ref = ty::impl_trait_ref(selcx.tcx(), impl_def_id).unwrap(); let impl_trait_ref = @@ -134,12 +182,12 @@ pub fn orphan_check<'tcx>(tcx: &ty::ctxt<'tcx>, impl_def_id: ast::DefId) -> Result<(), OrphanCheckErr<'tcx>> { - debug!("impl_is_local({})", impl_def_id.repr(tcx)); + debug!("orphan_check({})", impl_def_id.repr(tcx)); // We only except this routine to be invoked on implementations // of a trait, not inherent implementations. let trait_ref = ty::impl_trait_ref(tcx, impl_def_id).unwrap(); - debug!("trait_ref={}", trait_ref.repr(tcx)); + debug!("orphan_check: trait_ref={}", trait_ref.repr(tcx)); // If the *trait* is local to the crate, ok. if trait_ref.def_id.krate == ast::LOCAL_CRATE { @@ -148,34 +196,106 @@ pub fn orphan_check<'tcx>(tcx: &ty::ctxt<'tcx>, return Ok(()); } + orphan_check_trait_ref(tcx, &trait_ref, ParamIsLocal(false)) +} + +fn orphan_check_trait_ref<'tcx>(tcx: &ty::ctxt<'tcx>, + trait_ref: &ty::TraitRef<'tcx>, + param_is_local: ParamIsLocal) + -> Result<(), OrphanCheckErr<'tcx>> +{ + debug!("orphan_check_trait_ref(trait_ref={}, param_is_local={})", + trait_ref.repr(tcx), param_is_local.0); + // First, create an ordered iterator over all the type parameters to the trait, with the self // type appearing first. let input_tys = Some(trait_ref.self_ty()); let input_tys = input_tys.iter().chain(trait_ref.substs.types.get_slice(TypeSpace).iter()); - let mut input_tys = input_tys; // Find the first input type that either references a type parameter OR // some local type. - match input_tys.find(|&&input_ty| references_local_or_type_parameter(tcx, input_ty)) { - Some(&input_ty) => { - // Within this first type, check that all type parameters are covered by a local - // type constructor. Note that if there is no local type constructor, then any - // type parameter at all will be an error. - let covered_params = type_parameters_covered_by_ty(tcx, input_ty); - let all_params = type_parameters_reachable_from_ty(input_ty); - for ¶m in all_params.difference(&covered_params) { - return Err(OrphanCheckErr::UncoveredTy(param)); + for input_ty in input_tys { + if ty_is_local(tcx, input_ty, param_is_local) { + debug!("orphan_check_trait_ref: ty_is_local `{}`", input_ty.repr(tcx)); + + // First local input type. Check that there are no + // uncovered type parameters. + let uncovered_tys = uncovered_tys(tcx, input_ty, param_is_local); + for uncovered_ty in uncovered_tys { + if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) { + debug!("orphan_check_trait_ref: uncovered type `{}`", param.repr(tcx)); + return Err(OrphanCheckErr::UncoveredTy(param)); + } } + + // OK, found local type, all prior types upheld invariant. + return Ok(()); } - None => { - return Err(OrphanCheckErr::NoLocalInputType); + + // Otherwise, enforce invariant that there are no type + // parameters reachable. + if !param_is_local.0 { + if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) { + debug!("orphan_check_trait_ref: uncovered type `{}`", param.repr(tcx)); + return Err(OrphanCheckErr::UncoveredTy(param)); + } } } - return Ok(()); + // If we exit above loop, never found a local type. + debug!("orphan_check_trait_ref: no local type"); + return Err(OrphanCheckErr::NoLocalInputType); +} + +fn uncovered_tys<'tcx>(tcx: &ty::ctxt<'tcx>, + ty: Ty<'tcx>, + param_is_local: ParamIsLocal) + -> Vec<Ty<'tcx>> +{ + if ty_is_local_constructor(tcx, ty, param_is_local) { + vec![] + } else if fundamental_ty(tcx, ty) { + ty.walk_shallow() + .flat_map(|t| uncovered_tys(tcx, t, param_is_local).into_iter()) + .collect() + } else { + vec![ty] + } } -fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool { +fn is_type_parameter<'tcx>(ty: Ty<'tcx>) -> bool { + match ty.sty { + // FIXME(#20590) straighten story about projection types + ty::ty_projection(..) | ty::ty_param(..) => true, + _ => false, + } +} + +fn ty_is_local<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>, param_is_local: ParamIsLocal) -> bool +{ + ty_is_local_constructor(tcx, ty, param_is_local) || + fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, param_is_local)) +} + +fn fundamental_ty<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool +{ + match ty.sty { + ty::ty_uniq(..) | ty::ty_rptr(..) => + true, + ty::ty_enum(def_id, _) | ty::ty_struct(def_id, _) => + ty::has_attr(tcx, def_id, "fundamental"), + ty::ty_trait(ref data) => + ty::has_attr(tcx, data.principal_def_id(), "fundamental"), + _ => + false + } +} + +fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, + ty: Ty<'tcx>, + param_is_local: ParamIsLocal) + -> bool +{ debug!("ty_is_local_constructor({})", ty.repr(tcx)); match ty.sty { @@ -190,11 +310,15 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool { ty::ty_ptr(..) | ty::ty_rptr(..) | ty::ty_tup(..) | - ty::ty_param(..) | + ty::ty_infer(..) | ty::ty_projection(..) => { false } + ty::ty_param(..) => { + param_is_local.0 + } + ty::ty_enum(def_id, _) | ty::ty_struct(def_id, _) => { def_id.krate == ast::LOCAL_CRATE @@ -210,7 +334,6 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool { } ty::ty_closure(..) | - ty::ty_infer(..) | ty::ty_err => { tcx.sess.bug( &format!("ty_is_local invoked on unexpected type: {}", @@ -219,30 +342,4 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool { } } -fn type_parameters_covered_by_ty<'tcx>(tcx: &ty::ctxt<'tcx>, - ty: Ty<'tcx>) - -> HashSet<Ty<'tcx>> -{ - if ty_is_local_constructor(tcx, ty) { - type_parameters_reachable_from_ty(ty) - } else { - ty.walk_children().flat_map(|t| type_parameters_covered_by_ty(tcx, t).into_iter()).collect() - } -} - -/// All type parameters reachable from `ty` -fn type_parameters_reachable_from_ty<'tcx>(ty: Ty<'tcx>) -> HashSet<Ty<'tcx>> { - ty.walk().filter(|&t| is_type_parameter(t)).collect() -} - -fn references_local_or_type_parameter<'tcx>(tcx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool { - ty.walk().any(|ty| is_type_parameter(ty) || ty_is_local_constructor(tcx, ty)) -} -fn is_type_parameter<'tcx>(ty: Ty<'tcx>) -> bool { - match ty.sty { - // FIXME(#20590) straighten story about projection types - ty::ty_projection(..) | ty::ty_param(..) => true, - _ => false, - } -} diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs index 9e4f63dca45..cb9d90744a4 100644 --- a/src/librustc/middle/traits/select.rs +++ b/src/librustc/middle/traits/select.rs @@ -17,6 +17,7 @@ use self::SelectionCandidate::*; use self::BuiltinBoundConditions::*; use self::EvaluationResult::*; +use super::coherence; use super::DerivedObligationCause; use super::project; use super::project::{normalize_with_depth, Normalized}; @@ -81,7 +82,7 @@ struct TraitObligationStack<'prev, 'tcx: 'prev> { /// selection-context's freshener. Used to check for recursion. fresh_trait_ref: ty::PolyTraitRef<'tcx>, - previous: Option<&'prev TraitObligationStack<'prev, 'tcx>> + previous: TraitObligationStackList<'prev, 'tcx>, } #[derive(Clone)] @@ -245,7 +246,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!("select({})", obligation.repr(self.tcx())); assert!(!obligation.predicate.has_escaping_regions()); - let stack = self.push_stack(None, obligation); + let stack = self.push_stack(TraitObligationStackList::empty(), obligation); match try!(self.candidate_from_obligation(&stack)) { None => { self.consider_unification_despite_ambiguity(obligation); @@ -327,7 +328,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!("evaluate_obligation({})", obligation.repr(self.tcx())); - self.evaluate_predicate_recursively(None, obligation).may_apply() + self.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation) + .may_apply() } fn evaluate_builtin_bound_recursively<'o>(&mut self, @@ -346,7 +348,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match obligation { Ok(obligation) => { - self.evaluate_predicate_recursively(Some(previous_stack), &obligation) + self.evaluate_predicate_recursively(previous_stack.list(), &obligation) } Err(ErrorReported) => { EvaluatedToOk @@ -355,7 +357,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } fn evaluate_predicates_recursively<'a,'o,I>(&mut self, - stack: Option<&TraitObligationStack<'o, 'tcx>>, + stack: TraitObligationStackList<'o, 'tcx>, predicates: I) -> EvaluationResult<'tcx> where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a @@ -372,7 +374,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } fn evaluate_predicate_recursively<'o>(&mut self, - previous_stack: Option<&TraitObligationStack<'o, 'tcx>>, + previous_stack: TraitObligationStackList<'o, 'tcx>, obligation: &PredicateObligation<'tcx>) -> EvaluationResult<'tcx> { @@ -423,14 +425,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } fn evaluate_obligation_recursively<'o>(&mut self, - previous_stack: Option<&TraitObligationStack<'o, 'tcx>>, + previous_stack: TraitObligationStackList<'o, 'tcx>, obligation: &TraitObligation<'tcx>) -> EvaluationResult<'tcx> { debug!("evaluate_obligation_recursively({})", obligation.repr(self.tcx())); - let stack = self.push_stack(previous_stack.map(|x| x), obligation); + let stack = self.push_stack(previous_stack, obligation); let result = self.evaluate_stack(&stack); @@ -538,7 +540,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation.recursion_depth + 1, skol_map, snapshot); - self.winnow_selection(None, VtableImpl(vtable_impl)).may_apply() + self.winnow_selection(TraitObligationStackList::empty(), + VtableImpl(vtable_impl)).may_apply() } Err(()) => { false @@ -607,6 +610,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { return Ok(Some(ErrorCandidate)); } + if !self.is_knowable(stack) { + debug!("intercrate not knowable"); + return Ok(None); + } + let candidate_set = try!(self.assemble_candidates(stack)); if candidate_set.ambiguous { @@ -707,6 +715,27 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { Ok(Some(candidate)) } + fn is_knowable<'o>(&mut self, + stack: &TraitObligationStack<'o, 'tcx>) + -> bool + { + debug!("is_knowable(intercrate={})", self.intercrate); + + if !self.intercrate { + return true; + } + + let obligation = &stack.obligation; + let predicate = self.infcx().resolve_type_vars_if_possible(&obligation.predicate); + + // ok to skip binder because of the nature of the + // trait-ref-is-knowable check, which does not care about + // bound regions + let trait_ref = &predicate.skip_binder().trait_ref; + + coherence::trait_ref_is_knowable(self.tcx(), trait_ref) + } + fn pick_candidate_cache(&self) -> &SelectionCache<'tcx> { // If there are any where-clauses in scope, then we always use // a cache local to this particular scope. Otherwise, we @@ -1026,7 +1055,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.infcx().probe(move |_| { match self.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) { Ok(obligations) => { - self.evaluate_predicates_recursively(Some(stack), obligations.iter()) + self.evaluate_predicates_recursively(stack.list(), obligations.iter()) } Err(()) => { EvaluatedToErr(Unimplemented) @@ -1310,7 +1339,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let result = self.infcx.probe(|_| { let candidate = (*candidate).clone(); match self.confirm_candidate(stack.obligation, candidate) { - Ok(selection) => self.winnow_selection(Some(stack), selection), + Ok(selection) => self.winnow_selection(stack.list(), + selection), Err(error) => EvaluatedToErr(error), } }); @@ -1320,7 +1350,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } fn winnow_selection<'o>(&mut self, - stack: Option<&TraitObligationStack<'o, 'tcx>>, + stack: TraitObligationStackList<'o,'tcx>, selection: Selection<'tcx>) -> EvaluationResult<'tcx> { @@ -2303,9 +2333,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { return Err(()); } - let impl_substs = util::fresh_substs_for_impl(self.infcx, - obligation.cause.span, - impl_def_id); + let impl_substs = util::fresh_type_vars_for_impl(self.infcx, + obligation.cause.span, + impl_def_id); let impl_trait_ref = impl_trait_ref.subst(self.tcx(), &impl_substs); @@ -2423,9 +2453,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { { // Create fresh type variables for each type parameter declared // on the impl etc. - let impl_substs = util::fresh_substs_for_impl(self.infcx, - obligation_cause.span, - impl_def_id); + let impl_substs = util::fresh_type_vars_for_impl(self.infcx, + obligation_cause.span, + impl_def_id); // Find the self type for the impl. let impl_self_ty = ty::lookup_item_type(self.tcx(), impl_def_id).ty; @@ -2476,7 +2506,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // Miscellany fn push_stack<'o,'s:'o>(&mut self, - previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>, + previous_stack: TraitObligationStackList<'s, 'tcx>, obligation: &'o TraitObligation<'tcx>) -> TraitObligationStack<'o, 'tcx> { @@ -2486,7 +2516,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { TraitObligationStack { obligation: obligation, fresh_trait_ref: fresh_trait_ref, - previous: previous_stack.map(|p| p), // FIXME variance + previous: previous_stack, } } @@ -2639,17 +2669,36 @@ impl<'tcx> SelectionCache<'tcx> { } } -impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> { - fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> { - Some(self) +impl<'o,'tcx> TraitObligationStack<'o,'tcx> { + fn list(&'o self) -> TraitObligationStackList<'o,'tcx> { + TraitObligationStackList::with(self) + } + + fn iter(&'o self) -> TraitObligationStackList<'o,'tcx> { + self.list() } } -impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> { +#[derive(Copy, Clone)] +struct TraitObligationStackList<'o,'tcx:'o> { + head: Option<&'o TraitObligationStack<'o,'tcx>> +} + +impl<'o,'tcx> TraitObligationStackList<'o,'tcx> { + fn empty() -> TraitObligationStackList<'o,'tcx> { + TraitObligationStackList { head: None } + } + + fn with(r: &'o TraitObligationStack<'o,'tcx>) -> TraitObligationStackList<'o,'tcx> { + TraitObligationStackList { head: Some(r) } + } +} + +impl<'o,'tcx> Iterator for TraitObligationStackList<'o,'tcx>{ type Item = &'o TraitObligationStack<'o,'tcx>; - fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> { - match *self { + fn next(&mut self) -> Option<&'o TraitObligationStack<'o,'tcx>> { + match self.head { Some(o) => { *self = o.previous; Some(o) @@ -2659,7 +2708,7 @@ impl<'o, 'tcx> Iterator for Option<&'o TraitObligationStack<'o, 'tcx>> { } } -impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> { +impl<'o,'tcx> Repr<'tcx> for TraitObligationStack<'o,'tcx> { fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String { format!("TraitObligationStack({})", self.obligation.repr(tcx)) diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs index 7c7db4a64c0..297cea13207 100644 --- a/src/librustc/middle/traits/util.rs +++ b/src/librustc/middle/traits/util.rs @@ -8,6 +8,7 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use middle::region; use middle::subst::{Substs, VecPerParamSpace}; use middle::infer::InferCtxt; use middle::ty::{self, Ty, AsPredicate, ToPolyTraitRef}; @@ -285,7 +286,6 @@ impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { } } - /////////////////////////////////////////////////////////////////////////// // Other /////////////////////////////////////////////////////////////////////////// @@ -294,16 +294,44 @@ impl<'tcx,I:Iterator<Item=ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { // declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>` // would return ($0, $1) where $0 and $1 are freshly instantiated type // variables. -pub fn fresh_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>, - span: Span, - impl_def_id: ast::DefId) - -> Substs<'tcx> +pub fn fresh_type_vars_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>, + span: Span, + impl_def_id: ast::DefId) + -> Substs<'tcx> { let tcx = infcx.tcx; let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics; infcx.fresh_substs_for_generics(span, &impl_generics) } +// determine the `self` type, using fresh variables for all variables +// declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>` +// would return ($0, $1) where $0 and $1 are freshly instantiated type +// variables. +pub fn free_substs_for_impl<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>, + _span: Span, + impl_def_id: ast::DefId) + -> Substs<'tcx> +{ + let tcx = infcx.tcx; + let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics; + + let some_types = impl_generics.types.map(|def| { + ty::mk_param_from_def(tcx, def) + }); + + let some_regions = impl_generics.regions.map(|def| { + // FIXME. This destruction scope information is pretty darn + // bogus; after all, the impl might not even be in this crate! + // But given what we do in coherence, it is harmless enough + // for now I think. -nmatsakis + let extent = region::DestructionScopeData::new(ast::DUMMY_NODE_ID); + ty::free_region_from_def(extent, def) + }); + + Substs::new(some_types, some_regions) +} + impl<'tcx, N> fmt::Debug for VtableImplData<'tcx, N> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "VtableImpl({:?})", self.impl_def_id) diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index 6e81d14d73c..0814ec2c84e 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -58,7 +58,7 @@ use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace}; use middle::traits; use middle::ty; use middle::ty_fold::{self, TypeFoldable, TypeFolder}; -use middle::ty_walk::TypeWalker; +use middle::ty_walk::{self, TypeWalker}; use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string}; use util::ppaux::ty_to_string; use util::ppaux::{Repr, UserString}; @@ -89,7 +89,8 @@ use syntax::codemap::Span; use syntax::parse::token::{self, InternedString, special_idents}; use syntax::print::pprust; use syntax::ptr::P; -use syntax::{ast, ast_map}; +use syntax::ast; +use syntax::ast_map::{self, LinkedPath}; pub type Disr = u64; @@ -3167,21 +3168,11 @@ impl<'tcx> TyS<'tcx> { TypeWalker::new(self) } - /// Iterator that walks types reachable from `self`, in - /// depth-first order. Note that this is a shallow walk. For - /// example: - /// - /// ```notrust - /// isize => { } - /// Foo<Bar<isize>> => { Bar<isize>, isize } - /// [isize] => { isize } - /// ``` - pub fn walk_children(&'tcx self) -> TypeWalker<'tcx> { - // Walks type reachable from `self` but not `self - let mut walker = self.walk(); - let r = walker.next(); - assert_eq!(r, Some(self)); - walker + /// Iterator that walks the immediate children of `self`. Hence + /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]` + /// (but not `i32`, like `walk`). + pub fn walk_shallow(&'tcx self) -> IntoIter<Ty<'tcx>> { + ty_walk::walk_shallow(self) } pub fn as_opt_param_ty(&self) -> Option<ty::ParamTy> { @@ -5484,7 +5475,7 @@ pub fn with_path<T, F>(cx: &ctxt, id: ast::DefId, f: F) -> T where if id.krate == ast::LOCAL_CRATE { cx.map.with_path(id.node, f) } else { - f(csearch::get_item_path(cx, id).iter().cloned().chain(None)) + f(csearch::get_item_path(cx, id).iter().cloned().chain(LinkedPath::empty())) } } diff --git a/src/librustc/middle/ty_walk.rs b/src/librustc/middle/ty_walk.rs index 5d492f1c95e..ec09d6dcc1e 100644 --- a/src/librustc/middle/ty_walk.rs +++ b/src/librustc/middle/ty_walk.rs @@ -12,6 +12,7 @@ use middle::ty::{self, Ty}; use std::iter::Iterator; +use std::vec::IntoIter; pub struct TypeWalker<'tcx> { stack: Vec<Ty<'tcx>>, @@ -23,60 +24,6 @@ impl<'tcx> TypeWalker<'tcx> { TypeWalker { stack: vec!(ty), last_subtree: 1, } } - fn push_subtypes(&mut self, parent_ty: Ty<'tcx>) { - match parent_ty.sty { - ty::ty_bool | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) | - ty::ty_str | ty::ty_infer(_) | ty::ty_param(_) | ty::ty_err => { - } - ty::ty_uniq(ty) | ty::ty_vec(ty, _) => { - self.stack.push(ty); - } - ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => { - self.stack.push(mt.ty); - } - ty::ty_projection(ref data) => { - self.push_reversed(data.trait_ref.substs.types.as_slice()); - } - ty::ty_trait(box ty::TyTrait { ref principal, ref bounds }) => { - self.push_reversed(principal.substs().types.as_slice()); - self.push_reversed(&bounds.projection_bounds.iter().map(|pred| { - pred.0.ty - }).collect::<Vec<_>>()); - } - ty::ty_enum(_, ref substs) | - ty::ty_struct(_, ref substs) | - ty::ty_closure(_, ref substs) => { - self.push_reversed(substs.types.as_slice()); - } - ty::ty_tup(ref ts) => { - self.push_reversed(ts); - } - ty::ty_bare_fn(_, ref ft) => { - self.push_sig_subtypes(&ft.sig); - } - } - } - - fn push_sig_subtypes(&mut self, sig: &ty::PolyFnSig<'tcx>) { - match sig.0.output { - ty::FnConverging(output) => { self.stack.push(output); } - ty::FnDiverging => { } - } - self.push_reversed(&sig.0.inputs); - } - - fn push_reversed(&mut self, tys: &[Ty<'tcx>]) { - // We push slices on the stack in reverse order so as to - // maintain a pre-order traversal. As of the time of this - // writing, the fact that the traversal is pre-order is not - // known to be significant to any code, but it seems like the - // natural order one would expect (basically, the order of the - // types as they are written). - for &ty in tys.iter().rev() { - self.stack.push(ty); - } - } - /// Skips the subtree of types corresponding to the last type /// returned by `next()`. /// @@ -105,10 +52,70 @@ impl<'tcx> Iterator for TypeWalker<'tcx> { } Some(ty) => { self.last_subtree = self.stack.len(); - self.push_subtypes(ty); + push_subtypes(&mut self.stack, ty); debug!("next: stack={:?}", self.stack); Some(ty) } } } } + +pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> { + let mut stack = vec![]; + push_subtypes(&mut stack, ty); + stack.into_iter() +} + +fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) { + match parent_ty.sty { + ty::ty_bool | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) | + ty::ty_str | ty::ty_infer(_) | ty::ty_param(_) | ty::ty_err => { + } + ty::ty_uniq(ty) | ty::ty_vec(ty, _) => { + stack.push(ty); + } + ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => { + stack.push(mt.ty); + } + ty::ty_projection(ref data) => { + push_reversed(stack, data.trait_ref.substs.types.as_slice()); + } + ty::ty_trait(box ty::TyTrait { ref principal, ref bounds }) => { + push_reversed(stack, principal.substs().types.as_slice()); + push_reversed(stack, &bounds.projection_bounds.iter().map(|pred| { + pred.0.ty + }).collect::<Vec<_>>()); + } + ty::ty_enum(_, ref substs) | + ty::ty_struct(_, ref substs) | + ty::ty_closure(_, ref substs) => { + push_reversed(stack, substs.types.as_slice()); + } + ty::ty_tup(ref ts) => { + push_reversed(stack, ts); + } + ty::ty_bare_fn(_, ref ft) => { + push_sig_subtypes(stack, &ft.sig); + } + } +} + +fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) { + match sig.0.output { + ty::FnConverging(output) => { stack.push(output); } + ty::FnDiverging => { } + } + push_reversed(stack, &sig.0.inputs); +} + +fn push_reversed<'tcx>(stack: &mut Vec<Ty<'tcx>>, tys: &[Ty<'tcx>]) { + // We push slices on the stack in reverse order so as to + // maintain a pre-order traversal. As of the time of this + // writing, the fact that the traversal is pre-order is not + // known to be significant to any code, but it seems like the + // natural order one would expect (basically, the order of the + // types as they are written). + for &ty in tys.iter().rev() { + stack.push(ty); + } +} diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs index 452589a2407..4405a9d75ee 100644 --- a/src/librustc/util/ppaux.rs +++ b/src/librustc/util/ppaux.rs @@ -384,13 +384,7 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String { } ty_infer(infer_ty) => infer_ty_to_string(cx, infer_ty), ty_err => "[type error]".to_string(), - ty_param(ref param_ty) => { - if cx.sess.verbose() { - param_ty.repr(cx) - } else { - param_ty.user_string(cx) - } - } + ty_param(ref param_ty) => param_ty.user_string(cx), ty_enum(did, substs) | ty_struct(did, substs) => { let base = ty::item_path_str(cx, did); parameterized(cx, &base, substs, did, &[], diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs index f88381fb36f..113827a3b40 100644 --- a/src/libsyntax/feature_gate.rs +++ b/src/libsyntax/feature_gate.rs @@ -91,6 +91,8 @@ const KNOWN_FEATURES: &'static [(&'static str, &'static str, Status)] = &[ ("start", "1.0.0", Active), ("main", "1.0.0", Active), + ("fundamental", "1.0.0", Active), + // Deprecate after snapshot // SNAP 5520801 ("unsafe_destructor", "1.0.0", Active), @@ -237,6 +239,10 @@ pub const KNOWN_ATTRIBUTES: &'static [(&'static str, AttributeType)] = &[ ("allow_internal_unstable", Gated("allow_internal_unstable", EXPLAIN_ALLOW_INTERNAL_UNSTABLE)), + ("fundamental", Gated("fundamental", + "the `#[fundamental]` attribute \ + is an experimental feature")), + // FIXME: #14408 whitelist docs since rustdoc looks at them ("doc", Whitelisted), |