1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
12 use check::{FnCtxt, Inherited, blank_fn_ctxt, regionck};
13 use constrained_type_params::{identify_constrained_type_params, Parameter};
16 use middle::subst::{self, TypeSpace, FnSpace, ParamSpace, SelfSpace};
18 use middle::ty::{self, Ty};
19 use middle::ty_fold::{TypeFolder, TypeFoldable, super_fold_ty};
21 use std::cell::RefCell;
22 use std::collections::HashSet;
24 use syntax::ast_util::local_def;
25 use syntax::codemap::{DUMMY_SP, Span};
26 use syntax::parse::token::special_idents;
28 use syntax::visit::Visitor;
30 pub struct CheckTypeWellFormedVisitor<'ccx, 'tcx:'ccx> {
31 ccx: &'ccx CrateCtxt<'ccx, 'tcx>,
32 cache: HashSet<Ty<'tcx>>
35 impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
36 pub fn new(ccx: &'ccx CrateCtxt<'ccx, 'tcx>) -> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
37 CheckTypeWellFormedVisitor { ccx: ccx, cache: HashSet::new() }
40 fn tcx(&self) -> &ty::ctxt<'tcx> {
44 /// Checks that the field types (in a struct def'n) or argument types (in an enum def'n) are
45 /// well-formed, meaning that they do not require any constraints not declared in the struct
46 /// definition itself. For example, this definition would be illegal:
48 /// struct Ref<'a, T> { x: &'a T }
50 /// because the type did not declare that `T:'a`.
52 /// We do this check as a pre-pass before checking fn bodies because if these constraints are
53 /// not included it frequently leads to confusing errors in fn bodies. So it's better to check
55 fn check_item_well_formed(&mut self, item: &ast::Item) {
57 debug!("check_item_well_formed(it.id={}, it.ident={})",
59 ccx.tcx.item_path_str(local_def(item.id)));
62 /// Right now we check that every default trait implementation
63 /// has an implementation of itself. Basically, a case like:
65 /// `impl Trait for T {}`
67 /// has a requirement of `T: Trait` which was required for default
68 /// method implementations. Although this could be improved now that
69 /// there's a better infrastructure in place for this, it's being left
70 /// for a follow-up work.
72 /// Since there's such a requirement, we need to check *just* positive
73 /// implementations, otherwise things like:
75 /// impl !Send for T {}
77 /// won't be allowed unless there's an *explicit* implementation of `Send`
79 ast::ItemImpl(_, ast::ImplPolarity::Positive, _, _, _, _) => {
80 self.check_impl(item);
82 ast::ItemImpl(_, ast::ImplPolarity::Negative, _, Some(_), _, _) => {
83 let trait_ref = ccx.tcx.impl_trait_ref(local_def(item.id)).unwrap();
84 ccx.tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id);
85 match ccx.tcx.lang_items.to_builtin_kind(trait_ref.def_id) {
86 Some(ty::BoundSend) | Some(ty::BoundSync) => {}
88 if !ccx.tcx.trait_has_default_impl(trait_ref.def_id) {
89 span_err!(ccx.tcx.sess, item.span, E0192,
90 "negative impls are only allowed for traits with \
91 default impls (e.g., `Send` and `Sync`)")
97 self.check_item_type(item);
99 ast::ItemStatic(..) => {
100 self.check_item_type(item);
102 ast::ItemConst(..) => {
103 self.check_item_type(item);
105 ast::ItemStruct(ref struct_def, ref ast_generics) => {
106 self.check_type_defn(item, |fcx| {
107 vec![struct_variant(fcx, &**struct_def)]
110 self.check_variances_for_type_defn(item, ast_generics);
112 ast::ItemEnum(ref enum_def, ref ast_generics) => {
113 self.check_type_defn(item, |fcx| {
114 enum_variants(fcx, enum_def)
117 self.check_variances_for_type_defn(item, ast_generics);
119 ast::ItemTrait(_, _, _, ref items) => {
120 let trait_predicates =
121 ccx.tcx.lookup_predicates(local_def(item.id));
122 reject_non_type_param_bounds(ccx.tcx, item.span, &trait_predicates);
123 if ccx.tcx.trait_has_default_impl(local_def(item.id)) {
124 if !items.is_empty() {
125 span_err!(ccx.tcx.sess, item.span, E0380,
126 "traits with default impls (`e.g. unsafe impl \
127 Trait for ..`) must have no methods or associated items")
135 fn with_fcx<F>(&mut self, item: &ast::Item, mut f: F) where
136 F: for<'fcx> FnMut(&mut CheckTypeWellFormedVisitor<'ccx, 'tcx>, &FnCtxt<'fcx, 'tcx>),
139 let item_def_id = local_def(item.id);
140 let type_scheme = ccx.tcx.lookup_item_type(item_def_id);
141 let type_predicates = ccx.tcx.lookup_predicates(item_def_id);
142 reject_non_type_param_bounds(ccx.tcx, item.span, &type_predicates);
143 let param_env = ccx.tcx.construct_parameter_environment(item.span,
144 &type_scheme.generics,
147 let tables = RefCell::new(ty::Tables::empty());
148 let inh = Inherited::new(ccx.tcx, &tables, param_env);
149 let fcx = blank_fn_ctxt(ccx, &inh, ty::FnConverging(type_scheme.ty), item.id);
151 fcx.select_all_obligations_or_error();
152 regionck::regionck_item(&fcx, item);
155 /// In a type definition, we check that to ensure that the types of the fields are well-formed.
156 fn check_type_defn<F>(&mut self, item: &ast::Item, mut lookup_fields: F) where
157 F: for<'fcx> FnMut(&FnCtxt<'fcx, 'tcx>) -> Vec<AdtVariant<'tcx>>,
159 self.with_fcx(item, |this, fcx| {
160 let variants = lookup_fields(fcx);
161 let mut bounds_checker = BoundsChecker::new(fcx,
163 Some(&mut this.cache));
164 debug!("check_type_defn at bounds_checker.scope: {:?}", bounds_checker.scope);
166 for variant in &variants {
167 for field in &variant.fields {
168 // Regions are checked below.
169 bounds_checker.check_traits_in_ty(field.ty, field.span);
172 // For DST, all intermediate types must be sized.
173 if let Some((_, fields)) = variant.fields.split_last() {
174 for field in fields {
175 fcx.register_builtin_bound(
178 traits::ObligationCause::new(field.span,
180 traits::FieldSized));
185 let field_tys: Vec<Ty> =
186 variants.iter().flat_map(|v| v.fields.iter().map(|f| f.ty)).collect();
188 regionck::regionck_ensure_component_tys_wf(
189 fcx, item.span, &field_tys);
193 fn check_item_type(&mut self,
196 self.with_fcx(item, |this, fcx| {
197 let mut bounds_checker = BoundsChecker::new(fcx,
199 Some(&mut this.cache));
200 debug!("check_item_type at bounds_checker.scope: {:?}", bounds_checker.scope);
202 let type_scheme = fcx.tcx().lookup_item_type(local_def(item.id));
203 let item_ty = fcx.instantiate_type_scheme(item.span,
206 .parameter_environment
210 bounds_checker.check_traits_in_ty(item_ty, item.span);
214 fn check_impl(&mut self,
217 self.with_fcx(item, |this, fcx| {
218 let mut bounds_checker = BoundsChecker::new(fcx,
220 Some(&mut this.cache));
221 debug!("check_impl at bounds_checker.scope: {:?}", bounds_checker.scope);
223 // Find the impl self type as seen from the "inside" --
224 // that is, with all type parameters converted from bound
226 let self_ty = fcx.tcx().node_id_to_type(item.id);
227 let self_ty = fcx.instantiate_type_scheme(item.span,
230 .parameter_environment
234 bounds_checker.check_traits_in_ty(self_ty, item.span);
236 // Similarly, obtain an "inside" reference to the trait
237 // that the impl implements.
238 let trait_ref = match fcx.tcx().impl_trait_ref(local_def(item.id)) {
243 let trait_ref = fcx.instantiate_type_scheme(item.span,
246 .parameter_environment
250 // We are stricter on the trait-ref in an impl than the
251 // self-type. In particular, we enforce region
252 // relationships. The reason for this is that (at least
253 // presently) "applying" an impl does not require that the
254 // application site check the well-formedness constraints on the
255 // trait reference. Instead, this is done at the impl site.
256 // Arguably this is wrong and we should treat the trait-reference
257 // the same way as we treat the self-type.
258 bounds_checker.check_trait_ref(&trait_ref, item.span);
261 traits::ObligationCause::new(
264 traits::ItemObligation(trait_ref.def_id));
266 // Find the supertrait bounds. This will add `int:Bar`.
267 let poly_trait_ref = ty::Binder(trait_ref);
268 let predicates = fcx.tcx().lookup_super_predicates(poly_trait_ref.def_id());
269 let predicates = predicates.instantiate_supertrait(fcx.tcx(), &poly_trait_ref);
271 let selcx = &mut traits::SelectionContext::new(fcx.infcx());
272 traits::normalize(selcx, cause.clone(), &predicates)
274 for predicate in predicates.value.predicates {
275 fcx.register_predicate(traits::Obligation::new(cause.clone(), predicate));
277 for obligation in predicates.obligations {
278 fcx.register_predicate(obligation);
283 fn check_variances_for_type_defn(&self,
285 ast_generics: &ast::Generics)
287 let item_def_id = local_def(item.id);
288 let ty_predicates = self.tcx().lookup_predicates(item_def_id);
289 let variances = self.tcx().item_variances(item_def_id);
291 let mut constrained_parameters: HashSet<_> =
294 .filter(|&(_, _, &variance)| variance != ty::Bivariant)
295 .map(|(space, index, _)| self.param_ty(ast_generics, space, index))
296 .map(|p| Parameter::Type(p))
299 identify_constrained_type_params(self.tcx(),
300 ty_predicates.predicates.as_slice(),
302 &mut constrained_parameters);
304 for (space, index, _) in variances.types.iter_enumerated() {
305 let param_ty = self.param_ty(ast_generics, space, index);
306 if constrained_parameters.contains(&Parameter::Type(param_ty)) {
309 let span = self.ty_param_span(ast_generics, item, space, index);
310 self.report_bivariance(span, param_ty.name);
313 for (space, index, &variance) in variances.regions.iter_enumerated() {
314 if variance != ty::Bivariant {
318 assert_eq!(space, TypeSpace);
319 let span = ast_generics.lifetimes[index].lifetime.span;
320 let name = ast_generics.lifetimes[index].lifetime.name;
321 self.report_bivariance(span, name);
326 ast_generics: &ast::Generics,
331 let name = match space {
332 TypeSpace => ast_generics.ty_params[index].ident.name,
333 SelfSpace => special_idents::type_self.name,
334 FnSpace => self.tcx().sess.bug("Fn space occupied?"),
337 ty::ParamTy { space: space, idx: index as u32, name: name }
340 fn ty_param_span(&self,
341 ast_generics: &ast::Generics,
348 TypeSpace => ast_generics.ty_params[index].span,
349 SelfSpace => item.span,
350 FnSpace => self.tcx().sess.span_bug(item.span, "Fn space occupied?"),
354 fn report_bivariance(&self,
356 param_name: ast::Name)
358 span_err!(self.tcx().sess, span, E0392,
359 "parameter `{}` is never used", param_name);
361 let suggested_marker_id = self.tcx().lang_items.phantom_data();
362 match suggested_marker_id {
364 self.tcx().sess.fileline_help(
366 &format!("consider removing `{}` or using a marker such as `{}`",
368 self.tcx().item_path_str(def_id)));
371 // no lang items, no help!
377 // Reject any predicates that do not involve a type parameter.
378 fn reject_non_type_param_bounds<'tcx>(tcx: &ty::ctxt<'tcx>,
380 predicates: &ty::GenericPredicates<'tcx>) {
381 for predicate in &predicates.predicates {
383 &ty::Predicate::Trait(ty::Binder(ref tr)) => {
384 let found_param = tr.input_types().iter()
385 .flat_map(|ty| ty.walk())
387 if !found_param { report_bound_error(tcx, span, tr.self_ty() )}
389 &ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(ty, _))) => {
390 let found_param = ty.walk().any(|t| is_ty_param(t));
391 if !found_param { report_bound_error(tcx, span, ty) }
397 fn report_bound_error<'t>(tcx: &ty::ctxt<'t>,
399 bounded_ty: ty::Ty<'t>) {
400 span_err!(tcx.sess, span, E0193,
401 "cannot bound type `{}`, where clause \
402 bounds may only be attached to types involving \
407 fn is_ty_param(ty: ty::Ty) -> bool {
409 &ty::TyParam(_) => true,
415 fn reject_shadowing_type_parameters<'tcx>(tcx: &ty::ctxt<'tcx>,
417 generics: &ty::Generics<'tcx>) {
418 let impl_params = generics.types.get_slice(subst::TypeSpace).iter()
419 .map(|tp| tp.name).collect::<HashSet<_>>();
421 for method_param in generics.types.get_slice(subst::FnSpace) {
422 if impl_params.contains(&method_param.name) {
423 span_err!(tcx.sess, span, E0194,
424 "type parameter `{}` shadows another type parameter of the same name",
430 impl<'ccx, 'tcx, 'v> Visitor<'v> for CheckTypeWellFormedVisitor<'ccx, 'tcx> {
431 fn visit_item(&mut self, i: &ast::Item) {
432 self.check_item_well_formed(i);
433 visit::walk_item(self, i);
436 fn visit_fn(&mut self,
437 fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
438 b: &'v ast::Block, span: Span, id: ast::NodeId) {
440 visit::FkFnBlock | visit::FkItemFn(..) => {}
441 visit::FkMethod(..) => {
442 match self.tcx().impl_or_trait_item(local_def(id)) {
443 ty::ImplOrTraitItem::MethodTraitItem(ty_method) => {
444 reject_shadowing_type_parameters(self.tcx(), span, &ty_method.generics)
450 visit::walk_fn(self, fk, fd, b, span)
453 fn visit_trait_item(&mut self, trait_item: &'v ast::TraitItem) {
454 if let ast::MethodTraitItem(_, None) = trait_item.node {
455 match self.tcx().impl_or_trait_item(local_def(trait_item.id)) {
456 ty::ImplOrTraitItem::MethodTraitItem(ty_method) => {
457 reject_non_type_param_bounds(
460 &ty_method.predicates);
461 reject_shadowing_type_parameters(
464 &ty_method.generics);
470 visit::walk_trait_item(self, trait_item)
474 pub struct BoundsChecker<'cx,'tcx:'cx> {
475 fcx: &'cx FnCtxt<'cx,'tcx>,
478 // This field is often attached to item impls; it is not clear
479 // that `CodeExtent` is well-defined for such nodes, so pnkfelix
480 // has left it as a NodeId rather than porting to CodeExtent.
483 binding_count: usize,
484 cache: Option<&'cx mut HashSet<Ty<'tcx>>>,
487 impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
488 pub fn new(fcx: &'cx FnCtxt<'cx,'tcx>,
490 cache: Option<&'cx mut HashSet<Ty<'tcx>>>)
491 -> BoundsChecker<'cx,'tcx> {
492 BoundsChecker { fcx: fcx, span: DUMMY_SP, scope: scope,
493 cache: cache, binding_count: 0 }
496 /// Given a trait ref like `A : Trait<B>`, where `Trait` is defined as (say):
498 /// trait Trait<B:OtherTrait> : Copy { ... }
500 /// This routine will check that `B : OtherTrait` and `A : Trait<B>`. It will also recursively
501 /// check that the types `A` and `B` are well-formed.
503 /// Note that it does not (currently, at least) check that `A : Copy` (that check is delegated
504 /// to the point where impl `A : Trait<B>` is implemented).
505 pub fn check_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>, span: Span) {
506 let trait_predicates = self.fcx.tcx().lookup_predicates(trait_ref.def_id);
508 let bounds = self.fcx.instantiate_bounds(span,
512 self.fcx.add_obligations_for_parameters(
513 traits::ObligationCause::new(
516 traits::ItemObligation(trait_ref.def_id)),
519 for &ty in &trait_ref.substs.types {
520 self.check_traits_in_ty(ty, span);
524 pub fn check_ty(&mut self, ty: Ty<'tcx>, span: Span) {
529 fn check_traits_in_ty(&mut self, ty: Ty<'tcx>, span: Span) {
531 // When checking types outside of a type def'n, we ignore
532 // region obligations. See discussion below in fold_ty().
533 self.binding_count += 1;
535 self.binding_count -= 1;
539 impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
540 fn tcx(&self) -> &ty::ctxt<'tcx> {
544 fn fold_binder<T>(&mut self, binder: &ty::Binder<T>) -> ty::Binder<T>
545 where T : TypeFoldable<'tcx>
547 self.binding_count += 1;
548 let value = self.fcx.tcx().liberate_late_bound_regions(
549 region::DestructionScopeData::new(self.scope),
551 debug!("BoundsChecker::fold_binder: late-bound regions replaced: {:?} at scope: {:?}",
553 let value = value.fold_with(self);
554 self.binding_count -= 1;
558 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
559 debug!("BoundsChecker t={:?}",
563 Some(ref mut cache) => {
564 if !cache.insert(t) {
565 // Already checked this type! Don't check again.
574 ty::TyStruct(def, substs) |
575 ty::TyEnum(def, substs) => {
576 let type_predicates = def.predicates(self.fcx.tcx());
577 let bounds = self.fcx.instantiate_bounds(self.span, substs,
580 if self.binding_count == 0 {
581 self.fcx.add_obligations_for_parameters(
582 traits::ObligationCause::new(self.span,
584 traits::ItemObligation(def.did)),
587 // There are two circumstances in which we ignore
588 // region obligations.
590 // The first is when we are inside of a closure
591 // type. This is because in that case the region
592 // obligations for the parameter types are things
593 // that the closure body gets to assume and the
594 // caller must prove at the time of call. In other
595 // words, if there is a type like `<'a, 'b> | &'a
596 // &'b int |`, it is well-formed, and caller will
597 // have to show that `'b : 'a` at the time of
600 // The second is when we are checking for
601 // well-formedness outside of a type def'n or fn
602 // body. This is for a similar reason: in general,
603 // we only do WF checking for regions in the
604 // result of expressions and type definitions, so
605 // to as allow for implicit where clauses.
607 // (I believe we should do the same for traits, but
608 // that will require an RFC. -nmatsakis)
609 let bounds = filter_to_trait_obligations(bounds);
610 self.fcx.add_obligations_for_parameters(
611 traits::ObligationCause::new(self.span,
613 traits::ItemObligation(def.did)),
617 self.fold_substs(substs);
620 super_fold_ty(self, t);
624 t // we're not folding to produce a new type, so just return `t` here
628 ///////////////////////////////////////////////////////////////////////////
631 struct AdtVariant<'tcx> {
632 fields: Vec<AdtField<'tcx>>,
635 struct AdtField<'tcx> {
640 fn struct_variant<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
641 struct_def: &ast::StructDef)
642 -> AdtVariant<'tcx> {
647 let field_ty = fcx.tcx().node_id_to_type(field.node.id);
648 let field_ty = fcx.instantiate_type_scheme(field.span,
651 .parameter_environment
654 AdtField { ty: field_ty, span: field.span }
657 AdtVariant { fields: fields }
660 fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
661 enum_def: &ast::EnumDef)
662 -> Vec<AdtVariant<'tcx>> {
663 enum_def.variants.iter()
665 match variant.node.kind {
666 ast::TupleVariantKind(ref args) if !args.is_empty() => {
667 let ctor_ty = fcx.tcx().node_id_to_type(variant.node.id);
669 // the regions in the argument types come from the
670 // enum def'n, and hence will all be early bound
671 let arg_tys = fcx.tcx().no_late_bound_regions(&ctor_ty.fn_args()).unwrap();
673 fields: args.iter().enumerate().map(|(index, arg)| {
674 let arg_ty = arg_tys[index];
676 fcx.instantiate_type_scheme(variant.span,
679 .parameter_environment
689 ast::TupleVariantKind(_) => {
694 ast::StructVariantKind(ref struct_def) => {
695 struct_variant(fcx, &**struct_def)
702 fn filter_to_trait_obligations<'tcx>(bounds: ty::InstantiatedPredicates<'tcx>)
703 -> ty::InstantiatedPredicates<'tcx>
705 let mut result = ty::InstantiatedPredicates::empty();
706 for (space, _, predicate) in bounds.predicates.iter_enumerated() {
708 ty::Predicate::Trait(..) |
709 ty::Predicate::Projection(..) => {
710 result.predicates.push(space, predicate.clone())
712 ty::Predicate::Equate(..) |
713 ty::Predicate::TypeOutlives(..) |
714 ty::Predicate::RegionOutlives(..) => {