1 // Copyright 2012-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.
15 The collect phase of type check has the job of visiting all items,
16 determining their type, and writing that type into the `tcx.tcache`
17 table. Despite its name, this table does not really operate as a
18 *cache*, at least not for the types of items defined within the
19 current crate: we assume that after the collect phase, the types of
20 all local items will be present in the table.
22 Unlike most of the types that are present in Rust, the types computed
23 for each item are in fact type schemes. This means that they are
24 generic types that may have type parameters. TypeSchemes are
25 represented by an instance of `ty::TypeScheme`. This combines the
26 core type along with a list of the bounds for each parameter. Type
27 parameters themselves are represented as `ty_param()` instances.
29 The phasing of type conversion is somewhat complicated. There is no
30 clear set of phases we can enforce (e.g., converting traits first,
31 then types, or something like that) because the user can introduce
32 arbitrary interdependencies. So instead we generally convert things
33 lazilly and on demand, and include logic that checks for cycles.
34 Demand is driven by calls to `AstConv::get_item_type_scheme` or
35 `AstConv::lookup_trait_def`.
37 Currently, we "convert" types and traits in three phases (note that
38 conversion only affects the types of items / enum variants / methods;
39 it does not e.g. compute the types of individual expressions):
45 Conversion itself is done by simply walking each of the items in turn
46 and invoking an appropriate function (e.g., `trait_def_of_item` or
47 `convert_item`). However, it is possible that while converting an
48 item, we may need to compute the *type scheme* or *trait definition*
51 There are some shortcomings in this design:
53 - Before walking the set of supertraits for a given trait, you must
54 call `ensure_super_predicates` on that trait def-id. Otherwise,
55 `lookup_super_predicates` will result in ICEs.
56 - Because the type scheme includes defaults, cycles through type
57 parameter defaults are illegal even if those defaults are never
58 employed. This is not necessarily a bug.
59 - The phasing of trait definitions before type definitions does not
60 seem to be necessary, sufficient, or particularly helpful, given that
61 processing a trait definition can trigger processing a type def and
62 vice versa. However, if I remove it, I get ICEs, so some more work is
63 needed in that area. -nmatsakis
67 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
69 use constrained_type_params as ctp;
70 use middle::lang_items::SizedTraitLangItem;
71 use middle::free_region::FreeRegionMap;
73 use middle::resolve_lifetime;
74 use middle::subst::{Substs, FnSpace, ParamSpace, SelfSpace, TypeSpace, VecPerParamSpace};
75 use middle::ty::{ToPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
76 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty, TypeScheme};
77 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
81 use util::common::{ErrorReported, memoized};
82 use util::nodemap::{FnvHashMap, FnvHashSet};
85 use std::cell::{Cell, RefCell};
86 use std::collections::HashSet;
91 use syntax::ast_util::local_def;
92 use syntax::codemap::Span;
93 use syntax::parse::token::special_idents;
94 use syntax::parse::token;
98 ///////////////////////////////////////////////////////////////////////////
101 pub fn collect_item_types(tcx: &ty::ctxt) {
102 let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
104 let mut visitor = CollectTraitDefVisitor{ ccx: ccx };
105 visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
107 let mut visitor = CollectItemTypesVisitor{ ccx: ccx };
108 visit::walk_crate(&mut visitor, ccx.tcx.map.krate());
111 ///////////////////////////////////////////////////////////////////////////
113 struct CrateCtxt<'a,'tcx:'a> {
114 tcx: &'a ty::ctxt<'tcx>,
116 // This stack is used to identify cycles in the user's source.
117 // Note that these cycles can cross multiple items.
118 stack: RefCell<Vec<AstConvRequest>>,
121 /// Context specific to some particular item. This is what implements
122 /// AstConv. It has information about the predicates that are defined
123 /// on the trait. Unfortunately, this predicate information is
124 /// available in various different forms at various points in the
125 /// process. So we can't just store a pointer to e.g. the AST or the
126 /// parsed ty form, we have to be more flexible. To this end, the
127 /// `ItemCtxt` is parameterized by a `GetTypeParameterBounds` object
128 /// that it uses to satisfy `get_type_parameter_bounds` requests.
129 /// This object might draw the information from the AST
130 /// (`ast::Generics`) or it might draw from a `ty::GenericPredicates`
131 /// or both (a tuple).
132 struct ItemCtxt<'a,'tcx:'a> {
133 ccx: &'a CrateCtxt<'a,'tcx>,
134 param_bounds: &'a (GetTypeParameterBounds<'tcx>+'a),
137 #[derive(Copy, Clone, PartialEq, Eq)]
138 enum AstConvRequest {
139 GetItemTypeScheme(ast::DefId),
140 GetTraitDef(ast::DefId),
141 EnsureSuperPredicates(ast::DefId),
142 GetTypeParameterBounds(ast::NodeId),
145 ///////////////////////////////////////////////////////////////////////////
146 // First phase: just collect *trait definitions* -- basically, the set
147 // of type parameters and supertraits. This is information we need to
148 // know later when parsing field defs.
150 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
151 ccx: &'a CrateCtxt<'a, 'tcx>
154 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
155 fn visit_item(&mut self, i: &ast::Item) {
157 ast::ItemTrait(..) => {
158 // computing the trait def also fills in the table
159 let _ = trait_def_of_item(self.ccx, i);
164 visit::walk_item(self, i);
168 ///////////////////////////////////////////////////////////////////////////
169 // Second phase: collection proper.
171 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
172 ccx: &'a CrateCtxt<'a, 'tcx>
175 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
176 fn visit_item(&mut self, i: &ast::Item) {
177 convert_item(self.ccx, i);
178 visit::walk_item(self, i);
180 fn visit_foreign_item(&mut self, i: &ast::ForeignItem) {
181 convert_foreign_item(self.ccx, i);
182 visit::walk_foreign_item(self, i);
186 ///////////////////////////////////////////////////////////////////////////
187 // Utility types and common code for the above passes.
189 impl<'a,'tcx> CrateCtxt<'a,'tcx> {
190 fn icx(&'a self, param_bounds: &'a GetTypeParameterBounds<'tcx>) -> ItemCtxt<'a,'tcx> {
191 ItemCtxt { ccx: self, param_bounds: param_bounds }
194 fn method_ty(&self, method_id: ast::NodeId) -> Rc<ty::Method<'tcx>> {
195 let def_id = local_def(method_id);
196 match *self.tcx.impl_or_trait_items.borrow().get(&def_id).unwrap() {
197 ty::MethodTraitItem(ref mty) => mty.clone(),
199 self.tcx.sess.bug(&format!("method with id {} has the wrong type", method_id));
204 fn cycle_check<F,R>(&self,
206 request: AstConvRequest,
208 -> Result<R,ErrorReported>
209 where F: FnOnce() -> Result<R,ErrorReported>
212 let mut stack = self.stack.borrow_mut();
213 match stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
216 let cycle = &stack[i..];
217 self.report_cycle(span, cycle);
218 return Err(ErrorReported);
226 self.stack.borrow_mut().pop();
230 fn report_cycle(&self,
232 cycle: &[AstConvRequest])
234 assert!(!cycle.is_empty());
237 span_err!(tcx.sess, span, E0391,
238 "unsupported cyclic reference between types/traits detected");
241 AstConvRequest::GetItemTypeScheme(def_id) |
242 AstConvRequest::GetTraitDef(def_id) => {
244 &format!("the cycle begins when processing `{}`...",
245 tcx.item_path_str(def_id)));
247 AstConvRequest::EnsureSuperPredicates(def_id) => {
249 &format!("the cycle begins when computing the supertraits of `{}`...",
250 tcx.item_path_str(def_id)));
252 AstConvRequest::GetTypeParameterBounds(id) => {
253 let def = tcx.type_parameter_def(id);
255 &format!("the cycle begins when computing the bounds \
256 for type parameter `{}`...",
261 for request in &cycle[1..] {
263 AstConvRequest::GetItemTypeScheme(def_id) |
264 AstConvRequest::GetTraitDef(def_id) => {
266 &format!("...which then requires processing `{}`...",
267 tcx.item_path_str(def_id)));
269 AstConvRequest::EnsureSuperPredicates(def_id) => {
271 &format!("...which then requires computing the supertraits of `{}`...",
272 tcx.item_path_str(def_id)));
274 AstConvRequest::GetTypeParameterBounds(id) => {
275 let def = tcx.type_parameter_def(id);
277 &format!("...which then requires computing the bounds \
278 for type parameter `{}`...",
285 AstConvRequest::GetItemTypeScheme(def_id) |
286 AstConvRequest::GetTraitDef(def_id) => {
288 &format!("...which then again requires processing `{}`, completing the cycle.",
289 tcx.item_path_str(def_id)));
291 AstConvRequest::EnsureSuperPredicates(def_id) => {
293 &format!("...which then again requires computing the supertraits of `{}`, \
294 completing the cycle.",
295 tcx.item_path_str(def_id)));
297 AstConvRequest::GetTypeParameterBounds(id) => {
298 let def = tcx.type_parameter_def(id);
300 &format!("...which then again requires computing the bounds \
301 for type parameter `{}`, completing the cycle.",
307 /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises.
308 fn get_trait_def(&self, trait_id: ast::DefId)
309 -> &'tcx ty::TraitDef<'tcx>
313 if trait_id.krate != ast::LOCAL_CRATE {
314 return tcx.lookup_trait_def(trait_id)
317 let item = match tcx.map.get(trait_id.node) {
318 ast_map::NodeItem(item) => item,
319 _ => tcx.sess.bug(&format!("get_trait_def({:?}): not an item", trait_id))
322 trait_def_of_item(self, &*item)
325 /// Ensure that the (transitive) super predicates for
326 /// `trait_def_id` are available. This will report a cycle error
327 /// if a trait `X` (transitively) extends itself in some form.
328 fn ensure_super_predicates(&self, span: Span, trait_def_id: ast::DefId)
329 -> Result<(), ErrorReported>
331 self.cycle_check(span, AstConvRequest::EnsureSuperPredicates(trait_def_id), || {
332 let def_ids = ensure_super_predicates_step(self, trait_def_id);
334 for def_id in def_ids {
335 try!(self.ensure_super_predicates(span, def_id));
343 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
344 fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
345 ast_ty_to_ty(self, rs, ast_ty)
349 impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
350 fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
352 fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
353 -> Result<ty::TypeScheme<'tcx>, ErrorReported>
355 self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
356 Ok(type_scheme_of_def_id(self.ccx, id))
360 fn get_trait_def(&self, span: Span, id: ast::DefId)
361 -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>
363 self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
364 Ok(self.ccx.get_trait_def(id))
368 fn ensure_super_predicates(&self,
370 trait_def_id: ast::DefId)
371 -> Result<(), ErrorReported>
373 debug!("ensure_super_predicates(trait_def_id={:?})",
376 self.ccx.ensure_super_predicates(span, trait_def_id)
380 fn get_type_parameter_bounds(&self,
382 node_id: ast::NodeId)
383 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
385 self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
386 let v = self.param_bounds.get_type_parameter_bounds(self, span, node_id)
388 .filter_map(|p| p.to_opt_poly_trait_ref())
394 fn trait_defines_associated_type_named(&self,
395 trait_def_id: ast::DefId,
396 assoc_name: ast::Name)
399 if trait_def_id.krate == ast::LOCAL_CRATE {
400 trait_defines_associated_type_named(self.ccx, trait_def_id.node, assoc_name)
402 let trait_def = self.tcx().lookup_trait_def(trait_def_id);
403 trait_def.associated_type_names.contains(&assoc_name)
408 _ty_param_def: Option<ty::TypeParameterDef<'tcx>>,
409 _substs: Option<&mut Substs<'tcx>>,
410 _space: Option<ParamSpace>,
411 span: Span) -> Ty<'tcx> {
412 span_err!(self.tcx().sess, span, E0121,
413 "the type placeholder `_` is not allowed within types on item signatures");
417 fn projected_ty(&self,
419 trait_ref: ty::TraitRef<'tcx>,
420 item_name: ast::Name)
423 self.tcx().mk_projection(trait_ref, item_name)
427 /// Interface used to find the bounds on a type parameter from within
428 /// an `ItemCtxt`. This allows us to use multiple kinds of sources.
429 trait GetTypeParameterBounds<'tcx> {
430 fn get_type_parameter_bounds(&self,
431 astconv: &AstConv<'tcx>,
433 node_id: ast::NodeId)
434 -> Vec<ty::Predicate<'tcx>>;
437 /// Find bounds from both elements of the tuple.
438 impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
439 where A : GetTypeParameterBounds<'tcx>, B : GetTypeParameterBounds<'tcx>
441 fn get_type_parameter_bounds(&self,
442 astconv: &AstConv<'tcx>,
444 node_id: ast::NodeId)
445 -> Vec<ty::Predicate<'tcx>>
447 let mut v = self.0.get_type_parameter_bounds(astconv, span, node_id);
448 v.extend(self.1.get_type_parameter_bounds(astconv, span, node_id));
453 /// Empty set of bounds.
454 impl<'tcx> GetTypeParameterBounds<'tcx> for () {
455 fn get_type_parameter_bounds(&self,
456 _astconv: &AstConv<'tcx>,
458 _node_id: ast::NodeId)
459 -> Vec<ty::Predicate<'tcx>>
465 /// Find bounds from the parsed and converted predicates. This is
466 /// used when converting methods, because by that time the predicates
467 /// from the trait/impl have been fully converted.
468 impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
469 fn get_type_parameter_bounds(&self,
470 astconv: &AstConv<'tcx>,
472 node_id: ast::NodeId)
473 -> Vec<ty::Predicate<'tcx>>
475 let def = astconv.tcx().type_parameter_def(node_id);
479 .filter(|predicate| {
481 ty::Predicate::Trait(ref data) => {
482 data.skip_binder().self_ty().is_param(def.space, def.index)
484 ty::Predicate::TypeOutlives(ref data) => {
485 data.skip_binder().0.is_param(def.space, def.index)
487 ty::Predicate::Equate(..) |
488 ty::Predicate::RegionOutlives(..) |
489 ty::Predicate::Projection(..) => {
499 /// Find bounds from ast::Generics. This requires scanning through the
500 /// AST. We do this to avoid having to convert *all* the bounds, which
501 /// would create artificial cycles. Instead we can only convert the
502 /// bounds for those a type parameter `X` if `X::Foo` is used.
503 impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
504 fn get_type_parameter_bounds(&self,
505 astconv: &AstConv<'tcx>,
507 node_id: ast::NodeId)
508 -> Vec<ty::Predicate<'tcx>>
510 // In the AST, bounds can derive from two places. Either
511 // written inline like `<T:Foo>` or in a where clause like
514 let def = astconv.tcx().type_parameter_def(node_id);
515 let ty = astconv.tcx().mk_param_from_def(&def);
520 .filter(|p| p.id == node_id)
521 .flat_map(|p| p.bounds.iter())
522 .flat_map(|b| predicates_from_bound(astconv, ty, b));
524 let from_where_clauses =
528 .filter_map(|wp| match *wp {
529 ast::WherePredicate::BoundPredicate(ref bp) => Some(bp),
532 .filter(|bp| is_param(astconv.tcx(), &bp.bounded_ty, node_id))
533 .flat_map(|bp| bp.bounds.iter())
534 .flat_map(|b| predicates_from_bound(astconv, ty, b));
536 from_ty_params.chain(from_where_clauses).collect()
540 /// Tests whether this is the AST for a reference to the type
541 /// parameter with id `param_id`. We use this so as to avoid running
542 /// `ast_ty_to_ty`, because we want to avoid triggering an all-out
543 /// conversion of the type to avoid inducing unnecessary cycles.
544 fn is_param<'tcx>(tcx: &ty::ctxt<'tcx>,
546 param_id: ast::NodeId)
549 if let ast::TyPath(None, _) = ast_ty.node {
550 let path_res = *tcx.def_map.borrow().get(&ast_ty.id).unwrap();
551 match path_res.base_def {
552 def::DefSelfTy(Some(def_id), None) => {
553 path_res.depth == 0 && def_id.node == param_id
555 def::DefTyParam(_, _, def_id, _) => {
556 path_res.depth == 0 && def_id == local_def(param_id)
567 fn get_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
568 enum_scheme: ty::TypeScheme<'tcx>,
569 enum_predicates: ty::GenericPredicates<'tcx>,
570 variants: &[P<ast::Variant>]) {
572 let icx = ccx.icx(&enum_predicates);
574 // Create a set of parameter types shared among all the variants.
575 for variant in variants {
576 let variant_def_id = local_def(variant.node.id);
578 // Nullary enum constructors get turned into constants; n-ary enum
579 // constructors get turned into functions.
580 let result_ty = match variant.node.kind {
581 ast::TupleVariantKind(ref args) if !args.is_empty() => {
582 let rs = ExplicitRscope;
583 let input_tys: Vec<_> = args.iter().map(|va| icx.to_ty(&rs, &*va.ty)).collect();
584 tcx.mk_ctor_fn(variant_def_id, &input_tys, enum_scheme.ty)
587 ast::TupleVariantKind(_) => {
591 ast::StructVariantKind(ref struct_def) => {
592 convert_struct(ccx, &**struct_def, enum_scheme.clone(),
593 enum_predicates.clone(), variant.node.id);
598 let variant_scheme = TypeScheme {
599 generics: enum_scheme.generics.clone(),
603 tcx.register_item_type(variant_def_id, variant_scheme.clone());
604 tcx.predicates.borrow_mut().insert(variant_def_id, enum_predicates.clone());
605 write_ty_to_tcx(tcx, variant.node.id, result_ty);
609 fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
610 container: ImplOrTraitItemContainer,
611 sig: &ast::MethodSig,
614 vis: ast::Visibility,
615 untransformed_rcvr_ty: Ty<'tcx>,
616 rcvr_ty_generics: &ty::Generics<'tcx>,
617 rcvr_ty_predicates: &ty::GenericPredicates<'tcx>) {
618 let ty_generics = ty_generics_for_fn(ccx, &sig.generics, rcvr_ty_generics);
620 let ty_generic_predicates =
621 ty_generic_predicates_for_fn(ccx, &sig.generics, rcvr_ty_predicates);
623 let (fty, explicit_self_category) =
624 astconv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, &sig.generics)),
625 sig, untransformed_rcvr_ty);
627 let def_id = local_def(id);
628 let ty_method = ty::Method::new(ident.name,
630 ty_generic_predicates,
632 explicit_self_category,
638 let fty = ccx.tcx.mk_fn(Some(def_id),
639 ccx.tcx.mk_bare_fn(ty_method.fty.clone()));
640 debug!("method {} (id {}) has type {:?}",
642 ccx.tcx.register_item_type(def_id, TypeScheme {
643 generics: ty_method.generics.clone(),
646 ccx.tcx.predicates.borrow_mut().insert(def_id, ty_method.predicates.clone());
648 write_ty_to_tcx(ccx.tcx, id, fty);
650 debug!("writing method type: def_id={:?} mty={:?}",
653 ccx.tcx.impl_or_trait_items.borrow_mut().insert(def_id,
654 ty::MethodTraitItem(Rc::new(ty_method)));
657 fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
658 struct_generics: &ty::Generics<'tcx>,
659 struct_predicates: &ty::GenericPredicates<'tcx>,
660 v: &ast::StructField,
664 let tt = ccx.icx(struct_predicates).to_ty(&ExplicitRscope, &*v.node.ty);
665 write_ty_to_tcx(ccx.tcx, v.node.id, tt);
667 /* add the field to the tcache */
668 ccx.tcx.register_item_type(local_def(v.node.id),
670 generics: struct_generics.clone(),
673 ccx.tcx.predicates.borrow_mut().insert(local_def(v.node.id),
674 struct_predicates.clone());
677 ast::NamedField(ident, visibility) => {
680 id: local_def(v.node.id),
685 ast::UnnamedField(visibility) => {
687 name: special_idents::unnamed_field.name,
688 id: local_def(v.node.id),
696 fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
697 container: ImplOrTraitItemContainer,
700 vis: ast::Visibility,
702 default: Option<&ast::Expr>)
704 ccx.tcx.predicates.borrow_mut().insert(local_def(id),
705 ty::GenericPredicates::empty());
707 write_ty_to_tcx(ccx.tcx, id, ty);
708 let default_id = default.map(|expr| local_def(expr.id));
710 let associated_const = Rc::new(ty::AssociatedConst {
713 def_id: local_def(id),
714 container: container,
718 ccx.tcx.impl_or_trait_items.borrow_mut()
719 .insert(local_def(id), ty::ConstTraitItem(associated_const));
722 fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
723 container: ImplOrTraitItemContainer,
726 vis: ast::Visibility,
727 ty: Option<Ty<'tcx>>)
729 let associated_type = Rc::new(ty::AssociatedType {
733 def_id: local_def(id),
736 ccx.tcx.impl_or_trait_items.borrow_mut()
737 .insert(local_def(id), ty::TypeTraitItem(associated_type));
740 fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
741 container: ImplOrTraitItemContainer,
743 untransformed_rcvr_ty: Ty<'tcx>,
744 rcvr_ty_generics: &ty::Generics<'tcx>,
745 rcvr_ty_predicates: &ty::GenericPredicates<'tcx>)
746 where I: Iterator<Item=(&'i ast::MethodSig, ast::NodeId, ast::Ident, ast::Visibility, Span)>
748 debug!("convert_methods(untransformed_rcvr_ty={:?}, rcvr_ty_generics={:?}, \
749 rcvr_ty_predicates={:?})",
750 untransformed_rcvr_ty,
754 for (sig, id, ident, vis, _span) in methods {
761 untransformed_rcvr_ty,
767 fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
769 generics: &ast::Generics,
770 thing: &'static str) {
771 let mut warn = false;
773 for ty_param in generics.ty_params.iter() {
774 for bound in ty_param.bounds.iter() {
776 ast::TraitTyParamBound(..) => {
779 ast::RegionTyParamBound(..) => { }
785 // According to accepted RFC #XXX, we should
786 // eventually accept these, but it will not be
787 // part of this PR. Still, convert to warning to
788 // make bootstrapping easier.
789 span_warn!(ccx.tcx.sess, span, E0122,
790 "trait bounds are not (yet) enforced \
796 fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
798 debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
800 // These don't define types.
801 ast::ItemExternCrate(_) | ast::ItemUse(_) |
802 ast::ItemForeignMod(_) | ast::ItemMod(_) | ast::ItemMac(_) => {
804 ast::ItemEnum(ref enum_definition, _) => {
805 let (scheme, predicates) = convert_typed_item(ccx, it);
806 write_ty_to_tcx(tcx, it.id, scheme.ty);
807 get_enum_variant_types(ccx,
810 &enum_definition.variants);
812 ast::ItemDefaultImpl(_, ref ast_trait_ref) => {
814 astconv::instantiate_mono_trait_ref(&ccx.icx(&()),
819 tcx.record_trait_has_default_impl(trait_ref.def_id);
821 tcx.impl_trait_refs.borrow_mut().insert(local_def(it.id), Some(trait_ref));
828 // Create generics from the generics specified in the impl head.
829 debug!("convert: ast_generics={:?}", generics);
830 let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
831 let ty_predicates = ty_generic_predicates_for_type_or_impl(ccx, generics);
833 debug!("convert: impl_bounds={:?}", ty_predicates);
835 let selfty = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &**selfty);
836 write_ty_to_tcx(tcx, it.id, selfty);
838 tcx.register_item_type(local_def(it.id),
839 TypeScheme { generics: ty_generics.clone(),
841 tcx.predicates.borrow_mut().insert(local_def(it.id),
842 ty_predicates.clone());
844 // If there is a trait reference, treat the methods as always public.
845 // This is to work around some incorrect behavior in privacy checking:
846 // when the method belongs to a trait, it should acquire the privacy
847 // from the trait, not the impl. Forcing the visibility to be public
848 // makes things sorta work.
849 let parent_visibility = if opt_trait_ref.is_some() {
855 // Convert all the associated consts.
856 // Also, check if there are any duplicate associated items
857 let mut seen_type_items = FnvHashSet();
858 let mut seen_value_items = FnvHashSet();
860 for impl_item in impl_items {
861 let seen_items = match impl_item.node {
862 ast::TypeImplItem(_) => &mut seen_type_items,
863 _ => &mut seen_value_items,
865 if !seen_items.insert(impl_item.ident.name) {
866 let desc = match impl_item.node {
867 ast::ConstImplItem(_, _) => "associated constant",
868 ast::TypeImplItem(_) => "associated type",
869 ast::MethodImplItem(ref sig, _) =>
870 match sig.explicit_self.node {
871 ast::SelfStatic => "associated function",
874 _ => "associated item",
877 span_err!(tcx.sess, impl_item.span, E0201, "duplicate {}", desc);
880 if let ast::ConstImplItem(ref ty, ref expr) = impl_item.node {
881 let ty = ccx.icx(&ty_predicates)
882 .to_ty(&ExplicitRscope, &*ty);
883 tcx.register_item_type(local_def(impl_item.id),
885 generics: ty_generics.clone(),
888 convert_associated_const(ccx, ImplContainer(local_def(it.id)),
889 impl_item.ident, impl_item.id,
890 impl_item.vis.inherit_from(parent_visibility),
895 // Convert all the associated types.
896 for impl_item in impl_items {
897 if let ast::TypeImplItem(ref ty) = impl_item.node {
898 if opt_trait_ref.is_none() {
899 span_err!(tcx.sess, impl_item.span, E0202,
900 "associated types are not allowed in inherent impls");
903 let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, ty);
905 convert_associated_type(ccx, ImplContainer(local_def(it.id)),
906 impl_item.ident, impl_item.id, impl_item.vis,
911 let methods = impl_items.iter().filter_map(|ii| {
912 if let ast::MethodImplItem(ref sig, _) = ii.node {
913 // if the method specifies a visibility, use that, otherwise
914 // inherit the visibility from the impl (so `foo` in `pub impl
915 // { fn foo(); }` is public, but private in `impl { fn
917 let method_vis = ii.vis.inherit_from(parent_visibility);
918 Some((sig, ii.id, ii.ident, method_vis, ii.span))
924 ImplContainer(local_def(it.id)),
930 for impl_item in impl_items {
931 if let ast::MethodImplItem(ref sig, ref body) = impl_item.node {
932 let body_id = body.id;
933 check_method_self_type(ccx,
934 &BindingRscope::new(),
935 ccx.method_ty(impl_item.id),
942 if let &Some(ref ast_trait_ref) = opt_trait_ref {
943 tcx.impl_trait_refs.borrow_mut().insert(
945 Some(astconv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
951 tcx.impl_trait_refs.borrow_mut().insert(local_def(it.id), None);
954 enforce_impl_params_are_constrained(tcx,
959 ast::ItemTrait(_, _, _, ref trait_items) => {
960 let trait_def = trait_def_of_item(ccx, it);
961 let _: Result<(), ErrorReported> = // any error is already reported, can ignore
962 ccx.ensure_super_predicates(it.span, local_def(it.id));
963 convert_trait_predicates(ccx, it);
964 let trait_predicates = tcx.lookup_predicates(local_def(it.id));
966 debug!("convert: trait_bounds={:?}", trait_predicates);
968 // Convert all the associated types.
969 for trait_item in trait_items {
970 match trait_item.node {
971 ast::ConstTraitItem(ref ty, ref default) => {
972 let ty = ccx.icx(&trait_predicates)
973 .to_ty(&ExplicitRscope, ty);
974 tcx.register_item_type(local_def(trait_item.id),
976 generics: trait_def.generics.clone(),
979 convert_associated_const(ccx, TraitContainer(local_def(it.id)),
980 trait_item.ident, trait_item.id,
981 ast::Public, ty, default.as_ref().map(|d| &**d));
987 // Convert all the associated types.
988 for trait_item in trait_items {
989 match trait_item.node {
990 ast::TypeTraitItem(_, ref opt_ty) => {
991 let typ = opt_ty.as_ref().map({
992 |ty| ccx.icx(&trait_predicates).to_ty(&ExplicitRscope, &ty)
995 convert_associated_type(ccx, TraitContainer(local_def(it.id)),
996 trait_item.ident, trait_item.id, ast::Public,
1003 let methods = trait_items.iter().filter_map(|ti| {
1004 let sig = match ti.node {
1005 ast::MethodTraitItem(ref sig, _) => sig,
1008 Some((sig, ti.id, ti.ident, ast::Inherited, ti.span))
1011 // Run convert_methods on the trait methods.
1012 convert_methods(ccx,
1013 TraitContainer(local_def(it.id)),
1016 &trait_def.generics,
1019 // Add an entry mapping
1020 let trait_item_def_ids = Rc::new(trait_items.iter().map(|trait_item| {
1021 let def_id = local_def(trait_item.id);
1022 match trait_item.node {
1023 ast::ConstTraitItem(..) => {
1024 ty::ConstTraitItemId(def_id)
1026 ast::MethodTraitItem(..) => {
1027 ty::MethodTraitItemId(def_id)
1029 ast::TypeTraitItem(..) => {
1030 ty::TypeTraitItemId(def_id)
1034 tcx.trait_item_def_ids.borrow_mut().insert(local_def(it.id), trait_item_def_ids);
1036 // This must be done after `collect_trait_methods` so that
1037 // we have a method type stored for every method.
1038 for trait_item in trait_items {
1039 let sig = match trait_item.node {
1040 ast::MethodTraitItem(ref sig, _) => sig,
1043 check_method_self_type(ccx,
1044 &BindingRscope::new(),
1045 ccx.method_ty(trait_item.id),
1051 ast::ItemStruct(ref struct_def, _) => {
1052 // Write the class type.
1053 let (scheme, predicates) = convert_typed_item(ccx, it);
1054 write_ty_to_tcx(tcx, it.id, scheme.ty);
1055 convert_struct(ccx, &**struct_def, scheme, predicates, it.id);
1057 ast::ItemTy(_, ref generics) => {
1058 ensure_no_ty_param_bounds(ccx, it.span, generics, "type");
1059 let (scheme, _) = convert_typed_item(ccx, it);
1060 write_ty_to_tcx(tcx, it.id, scheme.ty);
1063 // This call populates the type cache with the converted type
1064 // of the item in passing. All we have to do here is to write
1065 // it into the node type table.
1066 let (scheme, _) = convert_typed_item(ccx, it);
1067 write_ty_to_tcx(tcx, it.id, scheme.ty);
1072 fn convert_struct<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1073 struct_def: &ast::StructDef,
1074 scheme: ty::TypeScheme<'tcx>,
1075 predicates: ty::GenericPredicates<'tcx>,
1079 // Write the type of each of the members and check for duplicate fields.
1080 let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
1081 let field_tys = struct_def.fields.iter().map(|f| {
1082 let result = convert_field(ccx, &scheme.generics, &predicates, f, local_def(id));
1084 if result.name != special_idents::unnamed_field.name {
1085 let dup = match seen_fields.get(&result.name) {
1086 Some(prev_span) => {
1087 span_err!(tcx.sess, f.span, E0124,
1088 "field `{}` is already declared",
1089 token::get_name(result.name));
1090 span_note!(tcx.sess, *prev_span, "previously declared here");
1095 // FIXME(#6393) this whole dup thing is just to satisfy
1096 // the borrow checker :-(
1098 seen_fields.insert(result.name, f.span);
1105 tcx.struct_fields.borrow_mut().insert(local_def(id), Rc::new(field_tys));
1107 let substs = mk_item_substs(ccx, &scheme.generics);
1108 let selfty = tcx.mk_struct(local_def(id), tcx.mk_substs(substs));
1110 // If this struct is enum-like or tuple-like, create the type of its
1112 match struct_def.ctor_id {
1115 if struct_def.fields.is_empty() {
1117 write_ty_to_tcx(tcx, ctor_id, selfty);
1119 tcx.register_item_type(local_def(ctor_id), scheme);
1120 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
1121 } else if struct_def.fields[0].node.kind.is_unnamed() {
1123 let inputs: Vec<_> =
1126 .map(|field| tcx.lookup_item_type(
1127 local_def(field.node.id)).ty)
1129 let ctor_fn_ty = tcx.mk_ctor_fn(local_def(ctor_id),
1132 write_ty_to_tcx(tcx, ctor_id, ctor_fn_ty);
1133 tcx.register_item_type(local_def(ctor_id),
1135 generics: scheme.generics,
1138 tcx.predicates.borrow_mut().insert(local_def(ctor_id), predicates);
1144 /// Ensures that the super-predicates of the trait with def-id
1145 /// trait_def_id are converted and stored. This does NOT ensure that
1146 /// the transitive super-predicates are converted; that is the job of
1147 /// the `ensure_super_predicates()` method in the `AstConv` impl
1148 /// above. Returns a list of trait def-ids that must be ensured as
1149 /// well to guarantee that the transitive superpredicates are
1151 fn ensure_super_predicates_step(ccx: &CrateCtxt,
1152 trait_def_id: ast::DefId)
1157 debug!("ensure_super_predicates_step(trait_def_id={:?})", trait_def_id);
1159 if trait_def_id.krate != ast::LOCAL_CRATE {
1160 // If this trait comes from an external crate, then all of the
1161 // supertraits it may depend on also must come from external
1162 // crates, and hence all of them already have their
1163 // super-predicates "converted" (and available from crate
1164 // meta-data), so there is no need to transitively test them.
1168 let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
1169 let superpredicates = superpredicates.unwrap_or_else(|| {
1170 let trait_node_id = trait_def_id.node;
1172 let item = match ccx.tcx.map.get(trait_node_id) {
1173 ast_map::NodeItem(item) => item,
1174 _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1177 let (generics, bounds) = match item.node {
1178 ast::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
1179 _ => tcx.sess.span_bug(item.span,
1180 "ensure_super_predicates_step invoked on non-trait"),
1183 // In-scope when converting the superbounds for `Trait` are
1184 // that `Self:Trait` as well as any bounds that appear on the
1186 let trait_def = trait_def_of_item(ccx, item);
1187 let self_predicate = ty::GenericPredicates {
1188 predicates: VecPerParamSpace::new(vec![],
1189 vec![trait_def.trait_ref.to_predicate()],
1192 let scope = &(generics, &self_predicate);
1194 // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
1195 let self_param_ty = tcx.mk_self_type();
1196 let superbounds1 = compute_bounds(&ccx.icx(scope),
1202 let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
1204 // Convert any explicit superbounds in the where clause,
1205 // e.g. `trait Foo where Self : Bar`:
1206 let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
1208 // Combine the two lists to form the complete set of superbounds:
1209 let superbounds = superbounds1.into_iter().chain(superbounds2).collect();
1210 let superpredicates = ty::GenericPredicates {
1211 predicates: VecPerParamSpace::new(superbounds, vec![], vec![])
1213 debug!("superpredicates for trait {:?} = {:?}",
1217 tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
1222 let def_ids: Vec<_> = superpredicates.predicates
1224 .filter_map(|p| p.to_opt_poly_trait_ref())
1225 .map(|tr| tr.def_id())
1228 debug!("ensure_super_predicates_step: def_ids={:?}", def_ids);
1233 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1235 -> &'tcx ty::TraitDef<'tcx>
1237 let def_id = local_def(it.id);
1240 if let Some(def) = tcx.trait_defs.borrow().get(&def_id) {
1244 let (unsafety, generics, items) = match it.node {
1245 ast::ItemTrait(unsafety, ref generics, _, ref items) => (unsafety, generics, items),
1246 _ => tcx.sess.span_bug(it.span, "trait_def_of_item invoked on non-trait"),
1249 let paren_sugar = tcx.has_attr(def_id, "rustc_paren_sugar");
1250 if paren_sugar && !ccx.tcx.sess.features.borrow().unboxed_closures {
1251 ccx.tcx.sess.span_err(
1253 "the `#[rustc_paren_sugar]` attribute is a temporary means of controlling \
1254 which traits can use parenthetical notation");
1255 fileline_help!(ccx.tcx.sess, it.span,
1256 "add `#![feature(unboxed_closures)]` to \
1257 the crate attributes to use it");
1260 let substs = ccx.tcx.mk_substs(mk_trait_substs(ccx, generics));
1262 let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
1264 let associated_type_names: Vec<_> = items.iter().filter_map(|trait_item| {
1265 match trait_item.node {
1266 ast::TypeTraitItem(..) => Some(trait_item.ident.name),
1271 let trait_ref = ty::TraitRef {
1276 let trait_def = ty::TraitDef {
1277 paren_sugar: paren_sugar,
1279 generics: ty_generics,
1280 trait_ref: trait_ref,
1281 associated_type_names: associated_type_names,
1282 nonblanket_impls: RefCell::new(FnvHashMap()),
1283 blanket_impls: RefCell::new(vec![]),
1284 flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS)
1287 return tcx.intern_trait_def(trait_def);
1289 fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1290 generics: &ast::Generics)
1295 // Creates a no-op substitution for the trait's type parameters.
1300 .map(|(i, def)| ty::ReEarlyBound(ty::EarlyBoundRegion {
1301 param_id: def.lifetime.id,
1304 name: def.lifetime.name
1308 // Start with the generics in the type parameters...
1313 .map(|(i, def)| tcx.mk_param(TypeSpace,
1314 i as u32, def.ident.name))
1317 // ...and also create the `Self` parameter.
1318 let self_ty = tcx.mk_self_type();
1320 Substs::new_trait(types, regions, self_ty)
1324 fn trait_defines_associated_type_named(ccx: &CrateCtxt,
1325 trait_node_id: ast::NodeId,
1326 assoc_name: ast::Name)
1329 let item = match ccx.tcx.map.get(trait_node_id) {
1330 ast_map::NodeItem(item) => item,
1331 _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
1334 let trait_items = match item.node {
1335 ast::ItemTrait(_, _, _, ref trait_items) => trait_items,
1336 _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not a trait", trait_node_id))
1339 trait_items.iter().any(|trait_item| {
1340 match trait_item.node {
1341 ast::TypeTraitItem(..) => trait_item.ident.name == assoc_name,
1347 fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) {
1349 let trait_def = trait_def_of_item(ccx, it);
1351 let def_id = local_def(it.id);
1353 let (generics, items) = match it.node {
1354 ast::ItemTrait(_, ref generics, _, ref items) => (generics, items),
1358 &format!("trait_def_of_item invoked on {:?}", s));
1362 let super_predicates = ccx.tcx.lookup_super_predicates(def_id);
1364 // `ty_generic_predicates` below will consider the bounds on the type
1365 // parameters (including `Self`) and the explicit where-clauses,
1366 // but to get the full set of predicates on a trait we need to add
1367 // in the supertrait bounds and anything declared on the
1368 // associated types.
1369 let mut base_predicates = super_predicates;
1371 // Add in a predicate that `Self:Trait` (where `Trait` is the
1372 // current trait). This is needed for builtin bounds.
1373 let self_predicate = trait_def.trait_ref.to_poly_trait_ref().to_predicate();
1374 base_predicates.predicates.push(SelfSpace, self_predicate);
1376 // add in the explicit where-clauses
1377 let mut trait_predicates =
1378 ty_generic_predicates(ccx, TypeSpace, generics, &base_predicates);
1380 let assoc_predicates = predicates_for_associated_types(ccx,
1383 trait_def.trait_ref,
1385 trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter());
1387 let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
1388 assert!(prev_predicates.is_none());
1392 fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1393 ast_generics: &ast::Generics,
1394 trait_predicates: &ty::GenericPredicates<'tcx>,
1395 self_trait_ref: ty::TraitRef<'tcx>,
1396 trait_items: &[P<ast::TraitItem>])
1397 -> Vec<ty::Predicate<'tcx>>
1399 trait_items.iter().flat_map(|trait_item| {
1400 let bounds = match trait_item.node {
1401 ast::TypeTraitItem(ref bounds, _) => bounds,
1403 return vec!().into_iter();
1407 let assoc_ty = ccx.tcx.mk_projection(self_trait_ref,
1408 trait_item.ident.name);
1410 let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
1413 SizedByDefault::Yes,
1416 bounds.predicates(ccx.tcx, assoc_ty).into_iter()
1421 fn type_scheme_of_def_id<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1423 -> ty::TypeScheme<'tcx>
1425 if def_id.krate != ast::LOCAL_CRATE {
1426 return ccx.tcx.lookup_item_type(def_id);
1429 match ccx.tcx.map.find(def_id.node) {
1430 Some(ast_map::NodeItem(item)) => {
1431 type_scheme_of_item(ccx, &*item)
1433 Some(ast_map::NodeForeignItem(foreign_item)) => {
1434 let abi = ccx.tcx.map.get_foreign_abi(def_id.node);
1435 type_scheme_of_foreign_item(ccx, &*foreign_item, abi)
1438 ccx.tcx.sess.bug(&format!("unexpected sort of node \
1439 in get_item_type_scheme(): {:?}",
1445 fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1447 -> ty::TypeScheme<'tcx>
1449 memoized(&ccx.tcx.tcache,
1451 |_| compute_type_scheme_of_item(ccx, it))
1454 fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1456 -> ty::TypeScheme<'tcx>
1460 ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
1461 let ty = ccx.icx(&()).to_ty(&ExplicitRscope, &**t);
1462 ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
1464 ast::ItemFn(ref decl, unsafety, _, abi, ref generics, _) => {
1465 let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
1466 let tofd = astconv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &**decl);
1467 let ty = tcx.mk_fn(Some(local_def(it.id)), tcx.mk_bare_fn(tofd));
1468 ty::TypeScheme { ty: ty, generics: ty_generics }
1470 ast::ItemTy(ref t, ref generics) => {
1471 let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1472 let ty = ccx.icx(generics).to_ty(&ExplicitRscope, &**t);
1473 ty::TypeScheme { ty: ty, generics: ty_generics }
1475 ast::ItemEnum(_, ref generics) => {
1476 // Create a new generic polytype.
1477 let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1478 let substs = mk_item_substs(ccx, &ty_generics);
1479 let t = tcx.mk_enum(local_def(it.id), tcx.mk_substs(substs));
1480 ty::TypeScheme { ty: t, generics: ty_generics }
1482 ast::ItemStruct(_, ref generics) => {
1483 let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
1484 let substs = mk_item_substs(ccx, &ty_generics);
1485 let t = tcx.mk_struct(local_def(it.id), tcx.mk_substs(substs));
1486 ty::TypeScheme { ty: t, generics: ty_generics }
1488 ast::ItemDefaultImpl(..) |
1489 ast::ItemTrait(..) |
1492 ast::ItemForeignMod(..) |
1493 ast::ItemExternCrate(..) |
1495 ast::ItemMac(..) => {
1498 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1504 fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1506 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
1510 let tag = type_scheme_of_item(ccx, it);
1511 let scheme = TypeScheme { generics: tag.generics, ty: tag.ty };
1512 let predicates = match it.node {
1513 ast::ItemStatic(..) | ast::ItemConst(..) => {
1514 ty::GenericPredicates::empty()
1516 ast::ItemFn(_, _, _, _, ref ast_generics, _) => {
1517 ty_generic_predicates_for_fn(ccx, ast_generics, &ty::GenericPredicates::empty())
1519 ast::ItemTy(_, ref generics) => {
1520 ty_generic_predicates_for_type_or_impl(ccx, generics)
1522 ast::ItemEnum(_, ref generics) => {
1523 ty_generic_predicates_for_type_or_impl(ccx, generics)
1525 ast::ItemStruct(_, ref generics) => {
1526 ty_generic_predicates_for_type_or_impl(ccx, generics)
1528 ast::ItemDefaultImpl(..) |
1529 ast::ItemTrait(..) |
1530 ast::ItemExternCrate(..) |
1534 ast::ItemForeignMod(..) |
1535 ast::ItemMac(..) => {
1538 &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
1543 let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id),
1544 predicates.clone());
1545 assert!(prev_predicates.is_none());
1548 if tcx.has_attr(local_def(it.id), "rustc_object_lifetime_default") {
1549 let object_lifetime_default_reprs: String =
1550 scheme.generics.types.iter()
1551 .map(|t| match t.object_lifetime_default {
1552 ty::ObjectLifetimeDefault::Specific(r) => r.to_string(),
1553 d => format!("{:?}", d),
1555 .collect::<Vec<String>>()
1558 tcx.sess.span_err(it.span, &object_lifetime_default_reprs);
1561 return (scheme, predicates);
1564 fn type_scheme_of_foreign_item<'a, 'tcx>(
1565 ccx: &CrateCtxt<'a, 'tcx>,
1566 it: &ast::ForeignItem,
1568 -> ty::TypeScheme<'tcx>
1570 memoized(&ccx.tcx.tcache,
1572 |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
1575 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
1576 ccx: &CrateCtxt<'a, 'tcx>,
1577 it: &ast::ForeignItem,
1579 -> ty::TypeScheme<'tcx>
1582 ast::ForeignItemFn(ref fn_decl, ref generics) => {
1583 compute_type_scheme_of_foreign_fn_decl(ccx, fn_decl, generics, abi)
1585 ast::ForeignItemStatic(ref t, _) => {
1587 generics: ty::Generics::empty(),
1588 ty: ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, t)
1594 fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1595 it: &ast::ForeignItem)
1597 // For reasons I cannot fully articulate, I do so hate the AST
1598 // map, and I regard each time that I use it as a personal and
1599 // moral failing, but at the moment it seems like the only
1600 // convenient way to extract the ABI. - ndm
1602 let abi = tcx.map.get_foreign_abi(it.id);
1604 let scheme = type_scheme_of_foreign_item(ccx, it, abi);
1605 write_ty_to_tcx(ccx.tcx, it.id, scheme.ty);
1607 let predicates = match it.node {
1608 ast::ForeignItemFn(_, ref generics) => {
1609 ty_generic_predicates_for_fn(ccx, generics, &ty::GenericPredicates::empty())
1611 ast::ForeignItemStatic(..) => {
1612 ty::GenericPredicates::empty()
1616 let prev_predicates = tcx.predicates.borrow_mut().insert(local_def(it.id), predicates);
1617 assert!(prev_predicates.is_none());
1620 fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1621 generics: &ast::Generics)
1622 -> ty::Generics<'tcx> {
1623 ty_generics(ccx, TypeSpace, generics, &ty::Generics::empty())
1626 fn ty_generic_predicates_for_type_or_impl<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1627 generics: &ast::Generics)
1628 -> ty::GenericPredicates<'tcx>
1630 ty_generic_predicates(ccx, TypeSpace, generics, &ty::GenericPredicates::empty())
1633 fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1634 trait_id: ast::NodeId,
1635 substs: &'tcx Substs<'tcx>,
1636 ast_generics: &ast::Generics)
1637 -> ty::Generics<'tcx>
1639 debug!("ty_generics_for_trait(trait_id={:?}, substs={:?})",
1640 local_def(trait_id), substs);
1642 let mut generics = ty_generics_for_type_or_impl(ccx, ast_generics);
1644 // Add in the self type parameter.
1646 // Something of a hack: use the node id for the trait, also as
1647 // the node id for the Self type parameter.
1648 let param_id = trait_id;
1650 let parent = ccx.tcx.map.get_parent(param_id);
1652 let def = ty::TypeParameterDef {
1655 name: special_idents::type_self.name,
1656 def_id: local_def(param_id),
1657 default_def_id: local_def(parent),
1659 object_lifetime_default: ty::ObjectLifetimeDefault::BaseDefault,
1662 ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
1664 generics.types.push(SelfSpace, def);
1669 fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1670 generics: &ast::Generics,
1671 base_generics: &ty::Generics<'tcx>)
1672 -> ty::Generics<'tcx>
1674 ty_generics(ccx, FnSpace, generics, base_generics)
1677 fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1678 generics: &ast::Generics,
1679 base_predicates: &ty::GenericPredicates<'tcx>)
1680 -> ty::GenericPredicates<'tcx>
1682 ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
1685 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
1686 fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
1687 bounds: &mut ty::BuiltinBounds,
1688 ast_bounds: &[ast::TyParamBound],
1691 let tcx = astconv.tcx();
1693 // Try to find an unbound in bounds.
1694 let mut unbound = None;
1695 for ab in ast_bounds {
1696 if let &ast::TraitTyParamBound(ref ptr, ast::TraitBoundModifier::Maybe) = ab {
1697 if unbound.is_none() {
1698 assert!(ptr.bound_lifetimes.is_empty());
1699 unbound = Some(ptr.trait_ref.clone());
1701 span_err!(tcx.sess, span, E0203,
1702 "type parameter has more than one relaxed default \
1703 bound, only one is supported");
1708 let kind_id = tcx.lang_items.require(SizedTraitLangItem);
1711 // FIXME(#8559) currently requires the unbound to be built-in.
1712 let trait_def_id = tcx.trait_ref_to_def_id(tpb);
1714 Ok(kind_id) if trait_def_id != kind_id => {
1715 tcx.sess.span_warn(span,
1716 "default bound relaxed for a type parameter, but \
1717 this does nothing because the given bound is not \
1718 a default. Only `?Sized` is supported");
1719 tcx.try_add_builtin_trait(kind_id, bounds);
1724 _ if kind_id.is_ok() => {
1725 tcx.try_add_builtin_trait(kind_id.unwrap(), bounds);
1727 // No lang item for Sized, so we can't add it as a bound.
1732 /// Returns the early-bound lifetimes declared in this generics
1733 /// listing. For anything other than fns/methods, this is just all
1734 /// the lifetimes that are declared. For fns or methods, we have to
1735 /// screen out those that do not appear in any where-clauses etc using
1736 /// `resolve_lifetime::early_bound_lifetimes`.
1737 fn early_bound_lifetimes_from_generics(space: ParamSpace,
1738 ast_generics: &ast::Generics)
1739 -> Vec<ast::LifetimeDef>
1742 SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
1743 FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
1747 fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1749 ast_generics: &ast::Generics,
1750 base_predicates: &ty::GenericPredicates<'tcx>)
1751 -> ty::GenericPredicates<'tcx>
1754 let mut result = base_predicates.clone();
1756 // Collect the predicates that were written inline by the user on each
1757 // type parameter (e.g., `<T:Foo>`).
1758 for (index, param) in ast_generics.ty_params.iter().enumerate() {
1759 let index = index as u32;
1760 let param_ty = ty::ParamTy::new(space, index, param.ident.name).to_ty(ccx.tcx);
1761 let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
1764 SizedByDefault::Yes,
1766 let predicates = bounds.predicates(ccx.tcx, param_ty);
1767 result.predicates.extend(space, predicates.into_iter());
1770 // Collect the region predicates that were declared inline as
1771 // well. In the case of parameters declared on a fn or method, we
1772 // have to be careful to only iterate over early-bound regions.
1773 let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1774 for (index, param) in early_lifetimes.iter().enumerate() {
1775 let index = index as u32;
1777 ty::ReEarlyBound(ty::EarlyBoundRegion {
1778 param_id: param.lifetime.id,
1781 name: param.lifetime.name
1783 for bound in ¶m.bounds {
1784 let bound_region = ast_region_to_region(ccx.tcx, bound);
1785 let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
1786 result.predicates.push(space, outlives.to_predicate());
1790 // Add in the bounds that appear in the where-clause
1791 let where_clause = &ast_generics.where_clause;
1792 for predicate in &where_clause.predicates {
1794 &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
1795 let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
1797 &*bound_pred.bounded_ty);
1799 for bound in bound_pred.bounds.iter() {
1801 &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
1802 let mut projections = Vec::new();
1805 conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
1810 result.predicates.push(space, trait_ref.to_predicate());
1812 for projection in &projections {
1813 result.predicates.push(space, projection.to_predicate());
1817 &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
1818 let region = ast_region_to_region(tcx, lifetime);
1819 let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
1820 result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
1826 &ast::WherePredicate::RegionPredicate(ref region_pred) => {
1827 let r1 = ast_region_to_region(tcx, ®ion_pred.lifetime);
1828 for bound in ®ion_pred.bounds {
1829 let r2 = ast_region_to_region(tcx, bound);
1830 let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
1831 result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
1835 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
1837 tcx.sess.span_bug(eq_pred.span,
1838 "Equality constraints are not yet \
1839 implemented (#20041)")
1847 fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1849 ast_generics: &ast::Generics,
1850 base_generics: &ty::Generics<'tcx>)
1851 -> ty::Generics<'tcx>
1854 let mut result = base_generics.clone();
1856 let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
1857 for (i, l) in early_lifetimes.iter().enumerate() {
1858 let bounds = l.bounds.iter()
1859 .map(|l| ast_region_to_region(tcx, l))
1861 let def = ty::RegionParameterDef { name: l.lifetime.name,
1864 def_id: local_def(l.lifetime.id),
1866 result.regions.push(space, def);
1869 assert!(result.types.is_empty_in(space));
1871 // Now create the real type parameters.
1872 for i in 0..ast_generics.ty_params.len() {
1873 let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
1874 debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
1875 result.types.push(space, def);
1881 fn convert_default_type_parameter<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
1887 let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &path);
1889 for leaf_ty in ty.walk() {
1890 if let ty::TyParam(p) = leaf_ty.sty {
1891 if p.space == space && p.idx >= index {
1892 span_err!(ccx.tcx.sess, path.span, E0128,
1893 "type parameters with a default cannot use \
1894 forward declared identifiers");
1896 return ccx.tcx.types.err
1904 fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1905 ast_generics: &ast::Generics,
1908 -> ty::TypeParameterDef<'tcx>
1910 let param = &ast_generics.ty_params[index as usize];
1913 match tcx.ty_param_defs.borrow().get(¶m.id) {
1914 Some(d) => { return d.clone(); }
1918 let default = param.default.as_ref().map(
1919 |def| convert_default_type_parameter(ccx, def, space, index)
1922 let object_lifetime_default =
1923 compute_object_lifetime_default(ccx, param.id,
1924 ¶m.bounds, &ast_generics.where_clause);
1926 let parent = tcx.map.get_parent(param.id);
1928 let def = ty::TypeParameterDef {
1931 name: param.ident.name,
1932 def_id: local_def(param.id),
1933 default_def_id: local_def(parent),
1935 object_lifetime_default: object_lifetime_default,
1938 tcx.ty_param_defs.borrow_mut().insert(param.id, def.clone());
1943 /// Scan the bounds and where-clauses on a parameter to extract bounds
1944 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`.
1945 /// This runs as part of computing the minimal type scheme, so we
1946 /// intentionally avoid just asking astconv to convert all the where
1947 /// clauses into a `ty::Predicate`. This is because that could induce
1948 /// artificial cycles.
1949 fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1950 param_id: ast::NodeId,
1951 param_bounds: &[ast::TyParamBound],
1952 where_clause: &ast::WhereClause)
1953 -> ty::ObjectLifetimeDefault
1955 let inline_bounds = from_bounds(ccx, param_bounds);
1956 let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
1957 let all_bounds: HashSet<_> = inline_bounds.into_iter()
1958 .chain(where_bounds)
1960 return if all_bounds.len() > 1 {
1961 ty::ObjectLifetimeDefault::Ambiguous
1962 } else if all_bounds.len() == 0 {
1963 ty::ObjectLifetimeDefault::BaseDefault
1965 ty::ObjectLifetimeDefault::Specific(
1966 all_bounds.into_iter().next().unwrap())
1969 fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1970 bounds: &[ast::TyParamBound])
1974 .filter_map(|bound| {
1976 ast::TraitTyParamBound(..) =>
1978 ast::RegionTyParamBound(ref lifetime) =>
1979 Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
1985 fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
1986 param_id: ast::NodeId,
1987 predicates: &[ast::WherePredicate])
1991 .flat_map(|predicate| {
1993 ast::WherePredicate::BoundPredicate(ref data) => {
1994 if data.bound_lifetimes.is_empty() &&
1995 is_param(ccx.tcx, &data.bounded_ty, param_id)
1997 from_bounds(ccx, &data.bounds).into_iter()
1999 Vec::new().into_iter()
2002 ast::WherePredicate::RegionPredicate(..) |
2003 ast::WherePredicate::EqPredicate(..) => {
2004 Vec::new().into_iter()
2012 enum SizedByDefault { Yes, No, }
2014 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
2015 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
2016 /// built-in trait (formerly known as kind): Send.
2017 fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
2018 param_ty: ty::Ty<'tcx>,
2019 ast_bounds: &[ast::TyParamBound],
2020 sized_by_default: SizedByDefault,
2022 -> astconv::Bounds<'tcx>
2025 conv_param_bounds(astconv,
2030 if let SizedByDefault::Yes = sized_by_default {
2031 add_unsized_bound(astconv,
2032 &mut bounds.builtin_bounds,
2037 bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
2042 /// Converts a specific TyParamBound from the AST into a set of
2043 /// predicates that apply to the self-type. A vector is returned
2044 /// because this can be anywhere from 0 predicates (`T:?Sized` adds no
2045 /// predicates) to 1 (`T:Foo`) to many (`T:Bar<X=i32>` adds `T:Bar`
2046 /// and `<T as Bar>::X == i32`).
2047 fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
2049 bound: &ast::TyParamBound)
2050 -> Vec<ty::Predicate<'tcx>>
2053 ast::TraitTyParamBound(ref tr, ast::TraitBoundModifier::None) => {
2054 let mut projections = Vec::new();
2055 let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
2056 projections.into_iter()
2057 .map(|p| p.to_predicate())
2058 .chain(Some(pred.to_predicate()))
2061 ast::RegionTyParamBound(ref lifetime) => {
2062 let region = ast_region_to_region(astconv.tcx(), lifetime);
2063 let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
2064 vec![ty::Predicate::TypeOutlives(pred)]
2066 ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) => {
2072 fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
2074 trait_ref: &ast::PolyTraitRef,
2075 projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
2076 -> ty::PolyTraitRef<'tcx>
2078 astconv::instantiate_poly_trait_ref(astconv,
2085 fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
2087 param_ty: ty::Ty<'tcx>,
2088 ast_bounds: &[ast::TyParamBound])
2089 -> astconv::Bounds<'tcx>
2091 let tcx = astconv.tcx();
2092 let astconv::PartitionedBounds {
2096 } = astconv::partition_bounds(tcx, span, &ast_bounds);
2098 let mut projection_bounds = Vec::new();
2100 let trait_bounds: Vec<ty::PolyTraitRef> =
2102 .map(|bound| conv_poly_trait_ref(astconv,
2105 &mut projection_bounds))
2108 let region_bounds: Vec<ty::Region> =
2109 region_bounds.into_iter()
2110 .map(|r| ast_region_to_region(tcx, r))
2114 region_bounds: region_bounds,
2115 builtin_bounds: builtin_bounds,
2116 trait_bounds: trait_bounds,
2117 projection_bounds: projection_bounds,
2121 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
2122 ccx: &CrateCtxt<'a, 'tcx>,
2124 ast_generics: &ast::Generics,
2126 -> ty::TypeScheme<'tcx>
2128 for i in &decl.inputs {
2129 match (*i).pat.node {
2130 ast::PatIdent(_, _, _) => (),
2131 ast::PatWild(ast::PatWildSingle) => (),
2133 span_err!(ccx.tcx.sess, (*i).pat.span, E0130,
2134 "patterns aren't allowed in foreign function declarations");
2139 let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
2141 let rb = BindingRscope::new();
2142 let input_tys = decl.inputs
2144 .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
2147 let output = match decl.output {
2148 ast::Return(ref ty) =>
2149 ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
2150 ast::DefaultReturn(..) =>
2151 ty::FnConverging(ccx.tcx.mk_nil()),
2152 ast::NoReturn(..) =>
2156 let t_fn = ccx.tcx.mk_fn(None,
2157 ccx.tcx.mk_bare_fn(ty::BareFnTy {
2159 unsafety: ast::Unsafety::Unsafe,
2160 sig: ty::Binder(ty::FnSig {inputs: input_tys,
2162 variadic: decl.variadic}),
2166 generics: ty_generics,
2171 fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
2172 ty_generics: &ty::Generics<'tcx>)
2176 ty_generics.types.map(
2177 |def| ccx.tcx.mk_param_from_def(def));
2180 ty_generics.regions.map(
2181 |def| def.to_early_bound_region());
2183 Substs::new(types, regions)
2186 /// Verifies that the explicit self type of a method matches the impl
2187 /// or trait. This is a bit weird but basically because right now we
2188 /// don't handle the general case, but instead map it to one of
2189 /// several pre-defined options using various heuristics, this method
2190 /// comes back to check after the fact that explicit type the user
2191 /// wrote actually matches what the pre-defined option said.
2192 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
2193 ccx: &CrateCtxt<'a, 'tcx>,
2195 method_type: Rc<ty::Method<'tcx>>,
2196 required_type: Ty<'tcx>,
2197 explicit_self: &ast::ExplicitSelf,
2198 body_id: ast::NodeId)
2201 if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
2202 let typ = ccx.icx(&method_type.predicates).to_ty(rs, &**ast_type);
2203 let base_type = match typ.sty {
2204 ty::TyRef(_, tm) => tm.ty,
2205 ty::TyBox(typ) => typ,
2209 let body_scope = region::DestructionScopeData::new(body_id);
2211 // "Required type" comes from the trait definition. It may
2212 // contain late-bound regions from the method, but not the
2213 // trait (since traits only have early-bound region
2215 assert!(!base_type.has_regions_escaping_depth(1));
2216 let required_type_free =
2217 liberate_early_bound_regions(
2219 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(required_type)));
2221 // The "base type" comes from the impl. It too may have late-bound
2222 // regions from the method.
2223 assert!(!base_type.has_regions_escaping_depth(1));
2224 let base_type_free =
2225 liberate_early_bound_regions(
2227 &tcx.liberate_late_bound_regions(body_scope, &ty::Binder(base_type)));
2229 debug!("required_type={:?} required_type_free={:?} \
2230 base_type={:?} base_type_free={:?}",
2236 let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
2237 drop(::require_same_types(tcx,
2244 format!("mismatched self type: expected `{}`",
2248 // We could conceviably add more free-region relations here,
2249 // but since this code is just concerned with checking that
2250 // the `&Self` types etc match up, it's not really necessary.
2251 // It would just allow people to be more approximate in some
2252 // cases. In any case, we can do it later as we feel the need;
2253 // I'd like this function to go away eventually.
2254 let free_regions = FreeRegionMap::new();
2256 infcx.resolve_regions_and_report_errors(&free_regions, body_id);
2259 fn liberate_early_bound_regions<'tcx,T>(
2260 tcx: &ty::ctxt<'tcx>,
2261 scope: region::DestructionScopeData,
2264 where T : TypeFoldable<'tcx>
2267 * Convert early-bound regions into free regions; normally this is done by
2268 * applying the `free_substs` from the `ParameterEnvironment`, but this particular
2269 * method-self-type check is kind of hacky and done very early in the process,
2270 * before we really have a `ParameterEnvironment` to check.
2273 ty_fold::fold_regions(tcx, value, &mut false, |region, _| {
2275 ty::ReEarlyBound(data) => {
2276 let def_id = local_def(data.param_id);
2277 ty::ReFree(ty::FreeRegion { scope: scope,
2278 bound_region: ty::BrNamed(def_id, data.name) })
2286 /// Checks that all the type parameters on an impl
2287 fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
2288 ast_generics: &ast::Generics,
2289 impl_def_id: ast::DefId,
2290 impl_items: &[P<ast::ImplItem>])
2292 let impl_scheme = tcx.lookup_item_type(impl_def_id);
2293 let impl_predicates = tcx.lookup_predicates(impl_def_id);
2294 let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
2296 // The trait reference is an input, so find all type parameters
2297 // reachable from there, to start (if this is an inherent impl,
2298 // then just examine the self type).
2299 let mut input_parameters: HashSet<_> =
2300 ctp::parameters_for_type(impl_scheme.ty).into_iter().collect();
2301 if let Some(ref trait_ref) = impl_trait_ref {
2302 input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref));
2305 ctp::identify_constrained_type_params(tcx,
2306 impl_predicates.predicates.as_slice(),
2308 &mut input_parameters);
2310 for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
2311 let param_ty = ty::ParamTy { space: TypeSpace,
2313 name: ty_param.ident.name };
2314 if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
2315 report_unused_parameter(tcx, ty_param.span, "type", ¶m_ty.to_string());
2319 // Every lifetime used in an associated type must be constrained.
2321 let lifetimes_in_associated_types: HashSet<_> =
2323 .map(|item| tcx.impl_or_trait_item(local_def(item.id)))
2324 .filter_map(|item| match item {
2325 ty::TypeTraitItem(ref assoc_ty) => assoc_ty.ty,
2326 ty::ConstTraitItem(..) | ty::MethodTraitItem(..) => None
2328 .flat_map(|ty| ctp::parameters_for_type(ty))
2329 .filter_map(|p| match p {
2330 ctp::Parameter::Type(_) => None,
2331 ctp::Parameter::Region(r) => Some(r),
2335 for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
2336 let region = ty::EarlyBoundRegion { param_id: lifetime_def.lifetime.id,
2338 index: index as u32,
2339 name: lifetime_def.lifetime.name };
2341 lifetimes_in_associated_types.contains(®ion) && // (*)
2342 !input_parameters.contains(&ctp::Parameter::Region(region))
2344 report_unused_parameter(tcx, lifetime_def.lifetime.span,
2345 "lifetime", ®ion.name.to_string());
2349 // (*) This is a horrible concession to reality. I think it'd be
2350 // better to just ban unconstrianed lifetimes outright, but in
2351 // practice people do non-hygenic macros like:
2354 // macro_rules! __impl_slice_eq1 {
2355 // ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2356 // impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
2363 // In a concession to backwards compatbility, we continue to
2364 // permit those, so long as the lifetimes aren't used in
2365 // associated types. I believe this is sound, because lifetimes
2366 // used elsewhere are not projected back out.
2369 fn report_unused_parameter(tcx: &ty::ctxt,
2374 span_err!(tcx.sess, span, E0207,
2375 "the {} parameter `{}` is not constrained by the \
2376 impl trait, self type, or predicates",