diff options
| -rw-r--r-- | src/librustc_typeck/Cargo.toml | 1 | ||||
| -rw-r--r-- | src/librustc_typeck/check/impl_parameters_used.rs | 129 | ||||
| -rw-r--r-- | src/librustc_typeck/check/mod.rs | 9 | ||||
| -rw-r--r-- | src/librustc_typeck/collect.rs | 119 | ||||
| -rw-r--r-- | src/librustc_typeck/constrained_type_params.rs | 12 | ||||
| -rw-r--r-- | src/librustc_typeck/lib.rs | 1 |
6 files changed, 160 insertions, 111 deletions
diff --git a/src/librustc_typeck/Cargo.toml b/src/librustc_typeck/Cargo.toml index 720423371a8..f08d26373e5 100644 --- a/src/librustc_typeck/Cargo.toml +++ b/src/librustc_typeck/Cargo.toml @@ -18,6 +18,7 @@ rustc = { path = "../librustc" } rustc_back = { path = "../librustc_back" } rustc_const_eval = { path = "../librustc_const_eval" } rustc_const_math = { path = "../librustc_const_math" } +rustc_data_structures = { path = "../librustc_data_structures" } rustc_platform_intrinsics = { path = "../librustc_platform_intrinsics" } syntax_pos = { path = "../libsyntax_pos" } rustc_errors = { path = "../librustc_errors" } diff --git a/src/librustc_typeck/check/impl_parameters_used.rs b/src/librustc_typeck/check/impl_parameters_used.rs new file mode 100644 index 00000000000..defdcc7906c --- /dev/null +++ b/src/librustc_typeck/check/impl_parameters_used.rs @@ -0,0 +1,129 @@ +// Copyright 2012-2014 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 constrained_type_params as ctp; +use rustc::hir; +use rustc::hir::def_id::DefId; +use rustc::ty; +use rustc::util::nodemap::FxHashSet; + +use syntax_pos::Span; + +use CrateCtxt; + +/// Checks that all the type/lifetime parameters on an impl also +/// appear in the trait ref or self-type (or are constrained by a +/// where-clause). These rules are needed to ensure that, given a +/// trait ref like `<T as Trait<U>>`, we can derive the values of all +/// parameters on the impl (which is needed to make specialization +/// possible). +/// +/// However, in the case of lifetimes, we only enforce these rules if +/// the lifetime parameter is used in an associated type. This is a +/// concession to backwards compatibility; see comment at the end of +/// the fn for details. +/// +/// Example: +/// +/// ``` +/// impl<T> Trait<Foo> for Bar { ... } +/// ^ T does not appear in `Foo` or `Bar`, error! +/// +/// impl<T> Trait<Foo<T>> for Bar { ... } +/// ^ T appears in `Foo<T>`, ok. +/// +/// impl<T> Trait<Foo> for Bar where Bar: Iterator<Item=T> { ... } +/// ^ T is bound to `<Bar as Iterator>::Item`, ok. +/// +/// impl<'a> Trait<Foo> for Bar { } +/// ^ 'a is unused, but for back-compat we allow it +/// +/// impl<'a> Trait<Foo> for Bar { type X = &'a i32; } +/// ^ 'a is unused and appears in assoc type, error +/// ``` +pub fn enforce_impl_params_are_constrained<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, + impl_hir_generics: &hir::Generics, + impl_def_id: DefId, + impl_item_ids: &[hir::ImplItemId]) +{ + // Every lifetime used in an associated type must be constrained. + let impl_scheme = ccx.tcx.lookup_item_type(impl_def_id); + let impl_predicates = ccx.tcx.lookup_predicates(impl_def_id); + let impl_trait_ref = ccx.tcx.impl_trait_ref(impl_def_id); + + let mut input_parameters = ctp::parameters_for_impl(impl_scheme.ty, impl_trait_ref); + ctp::identify_constrained_type_params( + &impl_predicates.predicates.as_slice(), impl_trait_ref, &mut input_parameters); + + // Disallow ANY unconstrained type parameters. + for (ty_param, param) in impl_scheme.generics.types.iter().zip(&impl_hir_generics.ty_params) { + let param_ty = ty::ParamTy::for_def(ty_param); + if !input_parameters.contains(&ctp::Parameter::from(param_ty)) { + report_unused_parameter(ccx, param.span, "type", ¶m_ty.to_string()); + } + } + + // Disallow unconstrained lifetimes, but only if they appear in assoc types. + let lifetimes_in_associated_types: FxHashSet<_> = impl_item_ids.iter() + .map(|item_id| ccx.tcx.map.local_def_id(item_id.id)) + .filter(|&def_id| { + let item = ccx.tcx.associated_item(def_id); + item.kind == ty::AssociatedKind::Type && item.has_value + }) + .flat_map(|def_id| { + ctp::parameters_for(&ccx.tcx.lookup_item_type(def_id).ty, true) + }).collect(); + for (ty_lifetime, lifetime) in impl_scheme.generics.regions.iter() + .zip(&impl_hir_generics.lifetimes) + { + let param = ctp::Parameter::from(ty_lifetime.to_early_bound_region_data()); + + if + lifetimes_in_associated_types.contains(¶m) && // (*) + !input_parameters.contains(¶m) + { + report_unused_parameter(ccx, lifetime.lifetime.span, + "lifetime", &lifetime.lifetime.name.to_string()); + } + } + + // (*) This is a horrible concession to reality. I think it'd be + // better to just ban unconstrianed lifetimes outright, but in + // practice people do non-hygenic macros like: + // + // ``` + // macro_rules! __impl_slice_eq1 { + // ($Lhs: ty, $Rhs: ty, $Bound: ident) => { + // impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> { + // .... + // } + // } + // } + // ``` + // + // In a concession to backwards compatbility, we continue to + // permit those, so long as the lifetimes aren't used in + // associated types. I believe this is sound, because lifetimes + // used elsewhere are not projected back out. +} + +fn report_unused_parameter(ccx: &CrateCtxt, + span: Span, + kind: &str, + name: &str) +{ + struct_span_err!( + ccx.tcx.sess, span, E0207, + "the {} parameter `{}` is not constrained by the \ + impl trait, self type, or predicates", + kind, name) + .span_label(span, &format!("unconstrained {} parameter", kind)) + .emit(); +} diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index e8ebc2eee63..12a1cc8279f 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -143,6 +143,7 @@ mod closure; mod callee; mod compare_method; mod intrinsic; +mod impl_parameters_used; mod op; /// closures defined within the function. For example: @@ -815,7 +816,7 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) { it.id); } hir::ItemFn(..) => {} // entirely within check_item_body - hir::ItemImpl(.., ref impl_item_ids) => { + hir::ItemImpl(_, _, ref hir_generics, _, _, ref impl_item_ids) => { debug!("ItemImpl {} with id {}", it.name, it.id); let impl_def_id = ccx.tcx.map.local_def_id(it.id); if let Some(impl_trait_ref) = ccx.tcx.impl_trait_ref(impl_def_id) { @@ -827,6 +828,12 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) { let trait_def_id = impl_trait_ref.def_id; check_on_unimplemented(ccx, trait_def_id, it); } + + impl_parameters_used::enforce_impl_params_are_constrained(ccx, + hir_generics, + impl_def_id, + impl_item_ids); + } hir::ItemTrait(..) => { let def_id = ccx.tcx.map.local_def_id(it.id); diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs index eb4775a29bf..e7873d2f818 100644 --- a/src/librustc_typeck/collect.rs +++ b/src/librustc_typeck/collect.rs @@ -753,7 +753,15 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) { }); tcx.impl_trait_refs.borrow_mut().insert(def_id, trait_ref); - enforce_impl_params_are_constrained(ccx, generics, &mut ty_predicates, def_id); + // Subtle: before we store the predicates into the tcx, we + // sort them so that predicates like `T: Foo<Item=U>` come + // before uses of `U`. This avoids false ambiguity errors + // in trait checking. See `setup_constraining_predicates` + // for details. + ctp::setup_constraining_predicates(&mut ty_predicates.predicates, + trait_ref, + &mut ctp::parameters_for_impl(selfty, trait_ref)); + tcx.predicates.borrow_mut().insert(def_id, ty_predicates.clone()); @@ -788,8 +796,6 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) { for &impl_item_id in impl_item_ids { convert_impl_item(ccx, impl_item_id); } - - enforce_impl_lifetimes_are_constrained(ccx, generics, def_id, impl_item_ids); }, hir::ItemTrait(.., ref trait_items) => { let trait_def = trait_def_of_item(ccx, it); @@ -2084,110 +2090,3 @@ pub fn mk_item_substs<'gcx: 'tcx, 'tcx>(astconv: &AstConv<'gcx, 'tcx>, |def, _| tcx.mk_region(def.to_early_bound_region()), |def, _| tcx.mk_param_from_def(def)) } - -/// Checks that all the type parameters on an impl -fn enforce_impl_params_are_constrained<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, - generics: &hir::Generics, - impl_predicates: &mut ty::GenericPredicates<'tcx>, - impl_def_id: DefId) -{ - let impl_ty = ccx.tcx.item_type(impl_def_id); - let impl_trait_ref = ccx.tcx.impl_trait_ref(impl_def_id); - - // The trait reference is an input, so find all type parameters - // reachable from there, to start (if this is an inherent impl, - // then just examine the self type). - let mut input_parameters: FxHashSet<_> = - ctp::parameters_for(&impl_ty, false).into_iter().collect(); - if let Some(ref trait_ref) = impl_trait_ref { - input_parameters.extend(ctp::parameters_for(trait_ref, false)); - } - - ctp::setup_constraining_predicates(&mut impl_predicates.predicates, - impl_trait_ref, - &mut input_parameters); - - let ty_generics = generics_of_def_id(ccx, impl_def_id); - for (ty_param, param) in ty_generics.types.iter().zip(&generics.ty_params) { - let param_ty = ty::ParamTy::for_def(ty_param); - if !input_parameters.contains(&ctp::Parameter::from(param_ty)) { - report_unused_parameter(ccx, param.span, "type", ¶m_ty.to_string()); - } - } -} - -fn enforce_impl_lifetimes_are_constrained<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, - ast_generics: &hir::Generics, - impl_def_id: DefId, - impl_item_ids: &[hir::ImplItemId]) -{ - // Every lifetime used in an associated type must be constrained. - let impl_ty = ccx.tcx.item_type(impl_def_id); - let impl_predicates = ccx.tcx.item_predicates(impl_def_id); - let impl_trait_ref = ccx.tcx.impl_trait_ref(impl_def_id); - - let mut input_parameters: FxHashSet<_> = - ctp::parameters_for(&impl_ty, false).into_iter().collect(); - if let Some(ref trait_ref) = impl_trait_ref { - input_parameters.extend(ctp::parameters_for(trait_ref, false)); - } - ctp::identify_constrained_type_params( - &impl_predicates.predicates.as_slice(), impl_trait_ref, &mut input_parameters); - - let lifetimes_in_associated_types: FxHashSet<_> = impl_item_ids.iter() - .map(|item_id| ccx.tcx.map.local_def_id(item_id.id)) - .filter(|&def_id| { - let item = ccx.tcx.associated_item(def_id); - item.kind == ty::AssociatedKind::Type && item.has_value - }) - .flat_map(|def_id| { - ctp::parameters_for(&ccx.tcx.item_type(def_id), true) - }).collect(); - - for (ty_lifetime, lifetime) in ccx.tcx.item_generics(impl_def_id).regions.iter() - .zip(&ast_generics.lifetimes) - { - let param = ctp::Parameter::from(ty_lifetime.to_early_bound_region_data()); - - if - lifetimes_in_associated_types.contains(¶m) && // (*) - !input_parameters.contains(¶m) - { - report_unused_parameter(ccx, lifetime.lifetime.span, - "lifetime", &lifetime.lifetime.name.to_string()); - } - } - - // (*) This is a horrible concession to reality. I think it'd be - // better to just ban unconstrianed lifetimes outright, but in - // practice people do non-hygenic macros like: - // - // ``` - // macro_rules! __impl_slice_eq1 { - // ($Lhs: ty, $Rhs: ty, $Bound: ident) => { - // impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> { - // .... - // } - // } - // } - // ``` - // - // In a concession to backwards compatbility, we continue to - // permit those, so long as the lifetimes aren't used in - // associated types. I believe this is sound, because lifetimes - // used elsewhere are not projected back out. -} - -fn report_unused_parameter(ccx: &CrateCtxt, - span: Span, - kind: &str, - name: &str) -{ - struct_span_err!( - ccx.tcx.sess, span, E0207, - "the {} parameter `{}` is not constrained by the \ - impl trait, self type, or predicates", - kind, name) - .span_label(span, &format!("unconstrained {} parameter", kind)) - .emit(); -} diff --git a/src/librustc_typeck/constrained_type_params.rs b/src/librustc_typeck/constrained_type_params.rs index 7918537a6c0..22be4491273 100644 --- a/src/librustc_typeck/constrained_type_params.rs +++ b/src/librustc_typeck/constrained_type_params.rs @@ -23,6 +23,18 @@ impl From<ty::EarlyBoundRegion> for Parameter { fn from(param: ty::EarlyBoundRegion) -> Self { Parameter(param.index) } } +/// Return the set of parameters constrained by the impl header. +pub fn parameters_for_impl<'tcx>(impl_self_ty: Ty<'tcx>, + impl_trait_ref: Option<ty::TraitRef<'tcx>>) + -> FxHashSet<Parameter> +{ + let vec = match impl_trait_ref { + Some(tr) => parameters_for(&tr, false), + None => parameters_for(&impl_self_ty, false), + }; + vec.into_iter().collect() +} + /// If `include_projections` is false, returns the list of parameters that are /// constrained by `t` - i.e. the value of each parameter in the list is /// uniquely determined by `t` (see RFC 447). If it is true, return the list diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs index 2c12959dbdd..222e60bb054 100644 --- a/src/librustc_typeck/lib.rs +++ b/src/librustc_typeck/lib.rs @@ -95,6 +95,7 @@ extern crate rustc_platform_intrinsics as intrinsics; extern crate rustc_back; extern crate rustc_const_math; extern crate rustc_const_eval; +extern crate rustc_data_structures; extern crate rustc_errors as errors; pub use rustc::dep_graph; |