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.
12 * Conversion from AST representation of types to the ty.rs
13 * representation. The main routine here is `ast_ty_to_ty()`: each use
14 * is parameterized by an instance of `AstConv` and a `RegionScope`.
16 * The parameterization of `ast_ty_to_ty()` is because it behaves
17 * somewhat differently during the collect and check phases,
18 * particularly with respect to looking up the types of top-level
19 * items. In the collect phase, the crate context is used as the
20 * `AstConv` instance; in this phase, the `get_item_ty()` function
21 * triggers a recursive call to `ty_of_item()` (note that
22 * `ast_ty_to_ty()` will detect recursive types and report an error).
23 * In the check phase, when the FnCtxt is used as the `AstConv`,
24 * `get_item_ty()` just looks up the item type in `tcx.tcache`.
26 * The `RegionScope` trait controls what happens when the user does
27 * not specify a region in some location where a region is required
28 * (e.g., if the user writes `&Foo` as a type rather than `&'a Foo`).
29 * See the `rscope` module for more details.
31 * Unlike the `AstConv` trait, the region scope can change as we descend
32 * the type. This is to accommodate the fact that (a) fn types are binding
33 * scopes and (b) the default region may change. To understand case (a),
34 * consider something like:
36 * type foo = { x: &a.int, y: |&a.int| }
38 * The type of `x` is an error because there is no region `a` in scope.
39 * In the type of `y`, however, region `a` is considered a bound region
40 * as it does not already appear in scope.
42 * Case (b) says that if you have a type:
44 * type bar = fn(&foo, &a.foo)
45 * The fully expanded version of type bar is:
46 * type bar = fn(&'foo &, &a.foo<'a>)
47 * Note that the self region for the `foo` defaulted to `&` in the first
48 * case but `&a` in the second. Basically, defaults that appear inside
49 * an rptr (`&r.T`) use the region `r` that appears in the rptr.
51 use middle::const_eval;
53 use middle::resolve_lifetime as rl;
54 use middle::subst::{FnSpace, TypeSpace, AssocSpace, SelfSpace, Subst, Substs};
55 use middle::subst::{VecPerParamSpace};
56 use middle::ty::{mod, Ty};
57 use middle::typeck::lookup_def_tcx;
58 use middle::typeck::rscope::{UnelidableRscope, RegionScope, SpecificRscope,
59 ShiftedRscope, BindingRscope};
60 use middle::typeck::rscope;
61 use middle::typeck::TypeAndSubsts;
62 use util::nodemap::DefIdMap;
63 use util::ppaux::{Repr, UserString};
66 use std::iter::AdditiveIterator;
67 use syntax::{abi, ast, ast_util};
68 use syntax::codemap::Span;
69 use syntax::parse::token;
70 use syntax::print::pprust;
72 pub trait AstConv<'tcx> {
73 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
74 fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype<'tcx>;
75 fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>>;
77 /// What type should we use when a type is omitted?
78 fn ty_infer(&self, span: Span) -> Ty<'tcx>;
80 /// Returns true if associated types from the given trait and type are
81 /// allowed to be used here and false otherwise.
82 fn associated_types_of_trait_are_valid(&self,
87 /// Returns the binding of the given associated type for some type.
88 fn associated_type_binding(&self,
92 associated_type_id: ast::DefId)
96 pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
98 let r = match tcx.named_region_map.get(&lifetime.id) {
100 // should have been recorded by the `resolve_lifetime` pass
101 tcx.sess.span_bug(lifetime.span, "unresolved lifetime");
104 Some(&rl::DefStaticRegion) => {
108 Some(&rl::DefLateBoundRegion(debruijn, id)) => {
109 ty::ReLateBound(debruijn, ty::BrNamed(ast_util::local_def(id), lifetime.name))
112 Some(&rl::DefEarlyBoundRegion(space, index, id)) => {
113 ty::ReEarlyBound(id, space, index, lifetime.name)
116 Some(&rl::DefFreeRegion(scope, id)) => {
117 ty::ReFree(ty::FreeRegion {
119 bound_region: ty::BrNamed(ast_util::local_def(id),
125 debug!("ast_region_to_region(lifetime={} id={}) yields {}",
133 pub fn opt_ast_region_to_region<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
137 opt_lifetime: &Option<ast::Lifetime>) -> ty::Region
139 let r = match *opt_lifetime {
140 Some(ref lifetime) => {
141 ast_region_to_region(this.tcx(), lifetime)
145 match rscope.anon_regions(default_span, 1) {
147 debug!("optional region in illegal location");
148 span_err!(this.tcx().sess, default_span, E0106,
149 "missing lifetime specifier");
152 let mut m = String::new();
154 for (i, (name, n)) in v.into_iter().enumerate() {
155 m.push_str(if n == 1 {
156 format!("`{}`", name)
158 format!("one of `{}`'s {} elided lifetimes", name, n)
161 if len == 2 && i == 0 {
163 } else if i == len - 2 {
165 } else if i != len - 1 {
170 span_help!(this.tcx().sess, default_span,
171 "this function's return type contains a borrowed value, but \
172 the signature does not say which {} it is borrowed from",
175 span_help!(this.tcx().sess, default_span,
176 "this function's return type contains a borrowed value, but \
177 there is no value for it to be borrowed from");
178 span_help!(this.tcx().sess, default_span,
179 "consider giving it a 'static lifetime");
181 span_help!(this.tcx().sess, default_span,
182 "this function's return type contains a borrowed value, but \
183 the signature does not say whether it is borrowed from {}",
197 debug!("opt_ast_region_to_region(opt_lifetime={}) yields {}",
198 opt_lifetime.repr(this.tcx()),
204 fn ast_path_substs_for_ty<'tcx,AC,RS>(
207 decl_def_id: ast::DefId,
208 decl_generics: &ty::Generics<'tcx>,
209 self_ty: Option<Ty<'tcx>>,
212 where AC: AstConv<'tcx>, RS: RegionScope
215 * Given a path `path` that refers to an item `I` with the
216 * declared generics `decl_generics`, returns an appropriate
217 * set of substitutions for this particular reference to `I`.
220 let tcx = this.tcx();
222 // ast_path_substs() is only called to convert paths that are
223 // known to refer to traits, types, or structs. In these cases,
224 // all type parameters defined for the item being referenced will
225 // be in the TypeSpace or SelfSpace.
227 // Note: in the case of traits, the self parameter is also
228 // defined, but we don't currently create a `type_param_def` for
229 // `Self` because it is implicit.
230 assert!(decl_generics.regions.all(|d| d.space == TypeSpace));
231 assert!(decl_generics.types.all(|d| d.space != FnSpace));
233 let (regions, types) = match path.segments.last().unwrap().parameters {
234 ast::AngleBracketedParameters(ref data) => {
235 convert_angle_bracketed_parameters(this, rscope, data)
237 ast::ParenthesizedParameters(ref data) => {
238 span_err!(tcx.sess, path.span, E0169,
239 "parenthesized parameters may only be used with a trait");
240 (Vec::new(), convert_parenthesized_parameters(this, data))
244 create_substs_for_ast_path(this, rscope, path.span, decl_def_id,
245 decl_generics, self_ty, types, regions)
248 fn create_substs_for_ast_path<'tcx,AC,RS>(
252 decl_def_id: ast::DefId,
253 decl_generics: &ty::Generics<'tcx>,
254 self_ty: Option<Ty<'tcx>>,
255 types: Vec<Ty<'tcx>>,
256 regions: Vec<ty::Region>)
258 where AC: AstConv<'tcx>, RS: RegionScope
260 let tcx = this.tcx();
262 // If the type is parameterized by the this region, then replace this
263 // region with the current anon region binding (in other words,
264 // whatever & would get replaced with).
265 let expected_num_region_params = decl_generics.regions.len(TypeSpace);
266 let supplied_num_region_params = regions.len();
267 let regions = if expected_num_region_params == supplied_num_region_params {
271 rscope.anon_regions(span, expected_num_region_params);
273 if supplied_num_region_params != 0 || anon_regions.is_err() {
274 span_err!(tcx.sess, span, E0107,
275 "wrong number of lifetime parameters: expected {}, found {}",
276 expected_num_region_params, supplied_num_region_params);
280 Ok(v) => v.into_iter().collect(),
281 Err(_) => Vec::from_fn(expected_num_region_params,
282 |_| ty::ReStatic) // hokey
286 // Convert the type parameters supplied by the user.
287 let ty_param_defs = decl_generics.types.get_slice(TypeSpace);
288 let supplied_ty_param_count = types.len();
289 let formal_ty_param_count =
291 .take_while(|x| !ty::is_associated_type(tcx, x.def_id))
293 let required_ty_param_count =
296 x.default.is_none() &&
297 !ty::is_associated_type(tcx, x.def_id)
300 if supplied_ty_param_count < required_ty_param_count {
301 let expected = if required_ty_param_count < formal_ty_param_count {
306 this.tcx().sess.span_fatal(span,
307 format!("wrong number of type arguments: {} {}, found {}",
309 required_ty_param_count,
310 supplied_ty_param_count).as_slice());
311 } else if supplied_ty_param_count > formal_ty_param_count {
312 let expected = if required_ty_param_count < formal_ty_param_count {
317 this.tcx().sess.span_fatal(span,
318 format!("wrong number of type arguments: {} {}, found {}",
320 formal_ty_param_count,
321 supplied_ty_param_count).as_slice());
324 if supplied_ty_param_count > required_ty_param_count
325 && !this.tcx().sess.features.borrow().default_type_params {
326 span_err!(this.tcx().sess, span, E0108,
327 "default type parameters are experimental and possibly buggy");
328 span_help!(this.tcx().sess, span,
329 "add #![feature(default_type_params)] to the crate attributes to enable");
332 let mut substs = Substs::new_type(types, regions);
336 // If no self-type is provided, it's still possible that
337 // one was declared, because this could be an object type.
340 // If a self-type is provided, one should have been
341 // "declared" (in other words, this should be a
343 assert!(decl_generics.types.get_self().is_some());
344 substs.types.push(SelfSpace, ty);
348 for param in ty_param_defs[supplied_ty_param_count..].iter() {
349 match param.default {
351 // This is a default type parameter.
352 let default = default.subst_spanned(tcx,
355 substs.types.push(TypeSpace, default);
358 tcx.sess.span_bug(span, "extra parameter without default");
363 for param in decl_generics.types.get_slice(AssocSpace).iter() {
366 this.associated_type_binding(span,
375 fn convert_angle_bracketed_parameters<'tcx, AC, RS>(this: &AC,
377 data: &ast::AngleBracketedParameterData)
378 -> (Vec<ty::Region>, Vec<Ty<'tcx>>)
379 where AC: AstConv<'tcx>, RS: RegionScope
381 let regions: Vec<_> =
382 data.lifetimes.iter()
383 .map(|l| ast_region_to_region(this.tcx(), l))
388 .map(|t| ast_ty_to_ty(this, rscope, &**t))
394 fn convert_parenthesized_parameters<'tcx,AC>(this: &AC,
395 data: &ast::ParenthesizedParameterData)
397 where AC: AstConv<'tcx>
399 let binding_rscope = BindingRscope::new();
401 let inputs = data.inputs.iter()
402 .map(|a_t| ast_ty_to_ty(this, &binding_rscope, &**a_t))
404 let input_ty = ty::mk_tup(this.tcx(), inputs);
406 let output = match data.output {
407 Some(ref output_ty) => ast_ty_to_ty(this, &binding_rscope, &**output_ty),
408 None => ty::mk_nil(this.tcx()),
411 vec![input_ty, output]
414 pub fn instantiate_poly_trait_ref<'tcx,AC,RS>(
417 ast_trait_ref: &ast::PolyTraitRef,
418 self_ty: Option<Ty<'tcx>>)
419 -> Rc<ty::TraitRef<'tcx>>
420 where AC: AstConv<'tcx>, RS: RegionScope
422 instantiate_trait_ref(this, rscope, &ast_trait_ref.trait_ref, self_ty)
425 pub fn instantiate_trait_ref<'tcx,AC,RS>(this: &AC,
427 ast_trait_ref: &ast::TraitRef,
428 self_ty: Option<Ty<'tcx>>)
429 -> Rc<ty::TraitRef<'tcx>>
430 where AC: AstConv<'tcx>,
434 * Instantiates the path for the given trait reference, assuming that
435 * it's bound to a valid trait type. Returns the def_id for the defining
436 * trait. Fails if the type is a type other than a trait type.
439 match lookup_def_tcx(this.tcx(),
440 ast_trait_ref.path.span,
441 ast_trait_ref.ref_id) {
442 def::DefTrait(trait_def_id) => {
443 let trait_ref = Rc::new(ast_path_to_trait_ref(this, rscope, trait_def_id,
444 self_ty, &ast_trait_ref.path));
445 this.tcx().trait_refs.borrow_mut().insert(ast_trait_ref.ref_id,
450 this.tcx().sess.span_fatal(
451 ast_trait_ref.path.span,
452 format!("`{}` is not a trait", ast_trait_ref.path.user_string(this.tcx()))[]);
457 fn ast_path_to_trait_ref<'tcx,AC,RS>(
460 trait_def_id: ast::DefId,
461 self_ty: Option<Ty<'tcx>>,
463 -> ty::TraitRef<'tcx>
464 where AC: AstConv<'tcx>, RS: RegionScope
466 let trait_def = this.get_trait_def(trait_def_id);
468 // the trait reference introduces a binding level here, so
469 // we need to shift the `rscope`. It'd be nice if we could
470 // do away with this rscope stuff and work this knowledge
471 // into resolve_lifetimes, as we do with non-omitted
472 // lifetimes. Oh well, not there yet.
473 let shifted_rscope = ShiftedRscope::new(rscope);
475 let (regions, types) = match path.segments.last().unwrap().parameters {
476 ast::AngleBracketedParameters(ref data) => {
477 convert_angle_bracketed_parameters(this, &shifted_rscope, data)
479 ast::ParenthesizedParameters(ref data) => {
480 (Vec::new(), convert_parenthesized_parameters(this, data))
484 let substs = create_substs_for_ast_path(this,
493 ty::TraitRef::new(trait_def_id, substs)
496 pub fn ast_path_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
501 -> TypeAndSubsts<'tcx>
503 let tcx = this.tcx();
507 } = this.get_item_ty(did);
509 let substs = ast_path_substs_for_ty(this,
515 let ty = decl_ty.subst(tcx, &substs);
516 TypeAndSubsts { substs: substs, ty: ty }
519 /// Returns the type that this AST path refers to. If the path has no type
520 /// parameters and the corresponding type has type parameters, fresh type
521 /// and/or region variables are substituted.
523 /// This is used when checking the constructor in struct literals.
524 pub fn ast_path_to_ty_relaxed<'tcx,AC,RS>(
529 -> TypeAndSubsts<'tcx>
530 where AC : AstConv<'tcx>, RS : RegionScope
532 let tcx = this.tcx();
536 } = this.get_item_ty(did);
539 generics.has_type_params(TypeSpace) || generics.has_region_params(TypeSpace);
543 path.segments.iter().all(|s| s.parameters.is_empty());
545 let substs = if needs_defaults {
546 let type_params = Vec::from_fn(generics.types.len(TypeSpace),
547 |_| this.ty_infer(path.span));
549 rscope.anon_regions(path.span, generics.regions.len(TypeSpace))
551 Substs::new(VecPerParamSpace::params_from_type(type_params),
552 VecPerParamSpace::params_from_type(region_params))
554 ast_path_substs_for_ty(this, rscope, did, &generics, None, path)
557 let ty = decl_ty.subst(tcx, &substs);
564 pub const NO_REGIONS: uint = 1;
565 pub const NO_TPS: uint = 2;
567 fn check_path_args(tcx: &ty::ctxt,
570 if (flags & NO_TPS) != 0u {
571 if path.segments.iter().any(|s| s.parameters.has_types()) {
572 span_err!(tcx.sess, path.span, E0109,
573 "type parameters are not allowed on this type");
577 if (flags & NO_REGIONS) != 0u {
578 if path.segments.iter().any(|s| s.parameters.has_lifetimes()) {
579 span_err!(tcx.sess, path.span, E0110,
580 "region parameters are not allowed on this type");
585 pub fn ast_ty_to_prim_ty<'tcx>(tcx: &ty::ctxt<'tcx>, ast_ty: &ast::Ty)
586 -> Option<Ty<'tcx>> {
588 ast::TyPath(ref path, _, id) => {
589 let a_def = match tcx.def_map.borrow().get(&id) {
591 tcx.sess.span_bug(ast_ty.span,
592 format!("unbound path {}",
593 path.repr(tcx)).as_slice())
598 def::DefPrimTy(nty) => {
601 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
605 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
609 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
610 Some(ty::mk_mach_int(it))
612 ast::TyUint(uit) => {
613 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
614 Some(ty::mk_mach_uint(uit))
616 ast::TyFloat(ft) => {
617 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
618 Some(ty::mk_mach_float(ft))
621 Some(ty::mk_str(tcx))
632 /// Converts the given AST type to a built-in type. A "built-in type" is, at
633 /// present, either a core numeric type, a string, or `Box`.
634 pub fn ast_ty_to_builtin_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
638 -> Option<Ty<'tcx>> {
639 match ast_ty_to_prim_ty(this.tcx(), ast_ty) {
640 Some(typ) => return Some(typ),
645 ast::TyPath(ref path, _, id) => {
646 let a_def = match this.tcx().def_map.borrow().get(&id) {
650 .span_bug(ast_ty.span,
651 format!("unbound path {}",
652 path.repr(this.tcx())).as_slice())
657 // FIXME(#12938): This is a hack until we have full support for
661 def::DefStruct(did) if Some(did) == this.tcx().lang_items.owned_box() => {
662 let ty = ast_path_to_ty(this, rscope, did, path).ty;
664 ty::ty_struct(struct_def_id, ref substs) => {
665 assert_eq!(struct_def_id, did);
666 assert_eq!(substs.types.len(TypeSpace), 1);
667 let referent_ty = *substs.types.get(TypeSpace, 0);
668 Some(ty::mk_uniq(this.tcx(), referent_ty))
671 this.tcx().sess.span_bug(
673 format!("converting `Box` to `{}`",
674 ty.repr(this.tcx()))[]);
685 // Handle `~`, `Box`, and `&` being able to mean strs and vecs.
686 // If a_seq_ty is a str or a vec, make it a str/vec.
687 // Also handle first-class trait types.
688 fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
691 a_seq_mutbl: ast::Mutability,
694 constr: |Ty<'tcx>| -> Ty<'tcx>)
697 let tcx = this.tcx();
699 debug!("mk_pointer(region={}, a_seq_ty={})",
703 match a_seq_ty.node {
704 ast::TyVec(ref ty) => {
705 let ty = ast_ty_to_ty(this, rscope, &**ty);
706 return constr(ty::mk_vec(tcx, ty, None));
708 ast::TyPath(ref path, ref opt_bounds, id) => {
709 // Note that the "bounds must be empty if path is not a trait"
710 // restriction is enforced in the below case for ty_path, which
711 // will run after this as long as the path isn't a trait.
712 match tcx.def_map.borrow().get(&id) {
713 Some(&def::DefPrimTy(ast::TyStr)) => {
714 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
715 return ty::mk_str_slice(tcx, region, a_seq_mutbl);
717 Some(&def::DefTrait(trait_def_id)) => {
718 let result = ast_path_to_trait_ref(this,
724 let bounds = match *opt_bounds { None => empty_vec.as_slice(),
725 Some(ref bounds) => bounds.as_slice() };
726 let existential_bounds = conv_existential_bounds(this,
729 &[Rc::new(result.clone())],
731 let tr = ty::mk_trait(tcx,
734 return ty::mk_rptr(tcx, region, ty::mt{mutbl: a_seq_mutbl, ty: tr});
742 constr(ast_ty_to_ty(this, rscope, a_seq_ty))
745 fn qpath_to_ty<'tcx,AC,RS>(this: &AC,
747 ast_ty: &ast::Ty, // the TyQPath
750 where AC: AstConv<'tcx>, RS: RegionScope
752 debug!("qpath_to_ty(ast_ty={})",
753 ast_ty.repr(this.tcx()));
755 let self_type = ast_ty_to_ty(this, rscope, &*qpath.self_type);
757 debug!("qpath_to_ty: self_type={}", self_type.repr(this.tcx()));
759 let trait_ref = instantiate_trait_ref(this,
764 debug!("qpath_to_ty: trait_ref={}", trait_ref.repr(this.tcx()));
766 let trait_def = this.get_trait_def(trait_ref.def_id);
768 for ty_param_def in trait_def.generics.types.get_slice(AssocSpace).iter() {
769 if ty_param_def.name == qpath.item_name.name {
770 debug!("qpath_to_ty: corresponding ty_param_def={}", ty_param_def);
771 return trait_ref.substs.type_for_def(ty_param_def);
775 this.tcx().sess.span_bug(ast_ty.span,
776 "this associated type didn't get added \
777 as a parameter for some reason")
780 // Parses the programmer's textual representation of a type into our
781 // internal notion of a type.
782 pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
783 this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> Ty<'tcx>
785 debug!("ast_ty_to_ty(ast_ty={})",
786 ast_ty.repr(this.tcx()));
788 let tcx = this.tcx();
790 let mut ast_ty_to_ty_cache = tcx.ast_ty_to_ty_cache.borrow_mut();
791 match ast_ty_to_ty_cache.get(&ast_ty.id) {
792 Some(&ty::atttce_resolved(ty)) => return ty,
793 Some(&ty::atttce_unresolved) => {
794 tcx.sess.span_fatal(ast_ty.span,
795 "illegal recursive type; insert an enum \
796 or struct in the cycle, if this is \
799 None => { /* go on */ }
801 ast_ty_to_ty_cache.insert(ast_ty.id, ty::atttce_unresolved);
802 drop(ast_ty_to_ty_cache);
804 let typ = ast_ty_to_builtin_ty(this, rscope, ast_ty).unwrap_or_else(|| {
806 ast::TyVec(ref ty) => {
807 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty), None)
809 ast::TyPtr(ref mt) => {
810 ty::mk_ptr(tcx, ty::mt {
811 ty: ast_ty_to_ty(this, rscope, &*mt.ty),
815 ast::TyRptr(ref region, ref mt) => {
816 let r = opt_ast_region_to_region(this, rscope, ast_ty.span, region);
817 debug!("ty_rptr r={}", r.repr(this.tcx()));
818 mk_pointer(this, rscope, mt.mutbl, &*mt.ty, r,
819 |ty| ty::mk_rptr(tcx, r, ty::mt {ty: ty, mutbl: mt.mutbl}))
821 ast::TyTup(ref fields) => {
822 let flds = fields.iter()
823 .map(|t| ast_ty_to_ty(this, rscope, &**t))
825 ty::mk_tup(tcx, flds)
827 ast::TyParen(ref typ) => ast_ty_to_ty(this, rscope, &**typ),
828 ast::TyBareFn(ref bf) => {
829 if bf.decl.variadic && bf.abi != abi::C {
830 tcx.sess.span_err(ast_ty.span,
831 "variadic function must have C calling convention");
833 ty::mk_bare_fn(tcx, ty_of_bare_fn(this, bf.fn_style, bf.abi, &*bf.decl))
835 ast::TyClosure(ref f) => {
836 // Use corresponding trait store to figure out default bounds
837 // if none were specified.
838 let bounds = conv_existential_bounds(this,
842 f.bounds.as_slice());
843 let fn_decl = ty_of_closure(this,
847 ty::RegionTraitStore(
853 ty::mk_closure(tcx, fn_decl)
855 ast::TyProc(ref f) => {
856 // Use corresponding trait store to figure out default bounds
857 // if none were specified.
858 let bounds = conv_existential_bounds(this, rscope,
861 f.bounds.as_slice());
863 let fn_decl = ty_of_closure(this,
872 ty::mk_closure(tcx, fn_decl)
874 ast::TyPolyTraitRef(ref bounds) => {
875 conv_ty_poly_trait_ref(this, rscope, ast_ty.span, bounds.as_slice())
877 ast::TyPath(ref path, ref bounds, id) => {
878 let a_def = match tcx.def_map.borrow().get(&id) {
881 .span_bug(ast_ty.span,
882 format!("unbound path {}",
883 path.repr(tcx)).as_slice())
887 // Kind bounds on path types are only supported for traits.
889 // But don't emit the error if the user meant to do a trait anyway.
890 def::DefTrait(..) => { },
891 _ if bounds.is_some() =>
892 tcx.sess.span_err(ast_ty.span,
893 "kind bounds can only be used on trait types"),
897 def::DefTrait(trait_def_id) => {
898 let result = ast_path_to_trait_ref(this,
903 let empty_bounds: &[ast::TyParamBound] = &[];
904 let ast_bounds = match *bounds {
905 Some(ref b) => b.as_slice(),
908 let bounds = conv_existential_bounds(this,
911 &[Rc::new(result.clone())],
913 let result_ty = ty::mk_trait(tcx, result, bounds);
914 debug!("ast_ty_to_ty: result_ty={}", result_ty.repr(this.tcx()));
917 def::DefTy(did, _) | def::DefStruct(did) => {
918 ast_path_to_ty(this, rscope, did, path).ty
920 def::DefTyParam(space, id, n) => {
921 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
922 ty::mk_param(tcx, space, n, id)
924 def::DefSelfTy(id) => {
925 // n.b.: resolve guarantees that the this type only appears in a
926 // trait, which we rely upon in various places when creating
928 check_path_args(tcx, path, NO_TPS | NO_REGIONS);
929 let did = ast_util::local_def(id);
930 ty::mk_self_type(tcx, did)
933 tcx.sess.span_fatal(ast_ty.span,
934 format!("found module name used as a type: {}",
935 tcx.map.node_to_string(id.node)).as_slice());
937 def::DefPrimTy(_) => {
938 panic!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
940 def::DefAssociatedTy(trait_type_id) => {
941 let path_str = tcx.map.path_to_string(
942 tcx.map.get_parent(trait_type_id.node));
943 tcx.sess.span_err(ast_ty.span,
944 format!("ambiguous associated \
945 type; specify the type \
946 using the syntax `<Type \
958 tcx.sess.span_fatal(ast_ty.span,
959 format!("found value name used \
965 ast::TyQPath(ref qpath) => {
966 qpath_to_ty(this, rscope, ast_ty, &**qpath)
968 ast::TyFixedLengthVec(ref ty, ref e) => {
969 match const_eval::eval_const_expr_partial(tcx, &**e) {
972 const_eval::const_int(i) =>
973 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
975 const_eval::const_uint(i) =>
976 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
980 ast_ty.span, "expected constant expr for array length");
987 format!("expected constant expr for array \
993 ast::TyTypeof(ref _e) => {
994 tcx.sess.span_bug(ast_ty.span, "typeof is reserved but unimplemented");
997 // TyInfer also appears as the type of arguments or return
998 // values in a ExprClosure or ExprProc, or as
999 // the type of local variables. Both of these cases are
1000 // handled specially and will not descend into this routine.
1001 this.ty_infer(ast_ty.span)
1006 tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, ty::atttce_resolved(typ));
1010 pub fn ty_of_arg<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(this: &AC, rscope: &RS,
1012 expected_ty: Option<Ty<'tcx>>)
1015 ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
1016 ast::TyInfer => this.ty_infer(a.ty.span),
1017 _ => ast_ty_to_ty(this, rscope, &*a.ty),
1021 struct SelfInfo<'a, 'tcx> {
1022 untransformed_self_ty: Ty<'tcx>,
1023 explicit_self: &'a ast::ExplicitSelf,
1026 pub fn ty_of_method<'tcx, AC: AstConv<'tcx>>(
1028 fn_style: ast::FnStyle,
1029 untransformed_self_ty: Ty<'tcx>,
1030 explicit_self: &ast::ExplicitSelf,
1033 -> (ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory) {
1034 let self_info = Some(SelfInfo {
1035 untransformed_self_ty: untransformed_self_ty,
1036 explicit_self: explicit_self,
1038 let (bare_fn_ty, optional_explicit_self_category) =
1039 ty_of_method_or_bare_fn(this,
1044 (bare_fn_ty, optional_explicit_self_category.unwrap())
1047 pub fn ty_of_bare_fn<'tcx, AC: AstConv<'tcx>>(this: &AC, fn_style: ast::FnStyle, abi: abi::Abi,
1048 decl: &ast::FnDecl) -> ty::BareFnTy<'tcx> {
1049 let (bare_fn_ty, _) = ty_of_method_or_bare_fn(this, fn_style, abi, None, decl);
1053 fn ty_of_method_or_bare_fn<'a, 'tcx, AC: AstConv<'tcx>>(
1055 fn_style: ast::FnStyle,
1057 opt_self_info: Option<SelfInfo<'a, 'tcx>>,
1059 -> (ty::BareFnTy<'tcx>,
1060 Option<ty::ExplicitSelfCategory>) {
1061 debug!("ty_of_method_or_bare_fn");
1063 // New region names that appear inside of the arguments of the function
1064 // declaration are bound to that function type.
1065 let rb = rscope::BindingRscope::new();
1067 // `implied_output_region` is the region that will be assumed for any
1068 // region parameters in the return type. In accordance with the rules for
1069 // lifetime elision, we can determine it in two ways. First (determined
1070 // here), if self is by-reference, then the implied output region is the
1071 // region of the self parameter.
1072 let mut explicit_self_category_result = None;
1073 let (self_ty, mut implied_output_region) = match opt_self_info {
1074 None => (None, None),
1075 Some(self_info) => {
1076 // Figure out and record the explicit self category.
1077 let explicit_self_category =
1078 determine_explicit_self_category(this, &rb, &self_info);
1079 explicit_self_category_result = Some(explicit_self_category);
1080 match explicit_self_category {
1081 ty::StaticExplicitSelfCategory => {
1084 ty::ByValueExplicitSelfCategory => {
1085 (Some(self_info.untransformed_self_ty), None)
1087 ty::ByReferenceExplicitSelfCategory(region, mutability) => {
1088 (Some(ty::mk_rptr(this.tcx(),
1091 ty: self_info.untransformed_self_ty,
1096 ty::ByBoxExplicitSelfCategory => {
1097 (Some(ty::mk_uniq(this.tcx(),
1098 self_info.untransformed_self_ty)),
1105 // HACK(eddyb) replace the fake self type in the AST with the actual type.
1106 let input_params = if self_ty.is_some() {
1107 decl.inputs.slice_from(1)
1109 decl.inputs.as_slice()
1111 let input_tys = input_params.iter().map(|a| ty_of_arg(this, &rb, a, None));
1112 let input_pats: Vec<String> = input_params.iter()
1113 .map(|a| pprust::pat_to_string(&*a.pat))
1115 let self_and_input_tys: Vec<Ty> =
1116 self_ty.into_iter().chain(input_tys).collect();
1118 let mut lifetimes_for_params: Vec<(String, Vec<ty::Region>)> = Vec::new();
1120 // Second, if there was exactly one lifetime (either a substitution or a
1121 // reference) in the arguments, then any anonymous regions in the output
1122 // have that lifetime.
1123 if implied_output_region.is_none() {
1124 let mut self_and_input_tys_iter = self_and_input_tys.iter();
1125 if self_ty.is_some() {
1126 // Skip the first argument if `self` is present.
1127 drop(self_and_input_tys_iter.next())
1130 for (input_type, input_pat) in self_and_input_tys_iter.zip(input_pats.into_iter()) {
1131 let mut accumulator = Vec::new();
1132 ty::accumulate_lifetimes_in_type(&mut accumulator, *input_type);
1133 lifetimes_for_params.push((input_pat, accumulator));
1136 if lifetimes_for_params.iter().map(|&(_, ref x)| x.len()).sum() == 1 {
1137 implied_output_region =
1138 Some(lifetimes_for_params.iter()
1139 .filter_map(|&(_, ref x)|
1140 if x.len() == 1 { Some(x[0]) } else { None })
1145 let param_lifetimes: Vec<(String, uint)> = lifetimes_for_params.into_iter()
1146 .map(|(n, v)| (n, v.len()))
1147 .filter(|&(_, l)| l != 0)
1150 let output_ty = match decl.output {
1151 ast::Return(ref output) if output.node == ast::TyInfer =>
1152 ty::FnConverging(this.ty_infer(output.span)),
1153 ast::Return(ref output) =>
1154 ty::FnConverging(match implied_output_region {
1155 Some(implied_output_region) => {
1156 let rb = SpecificRscope::new(implied_output_region);
1157 ast_ty_to_ty(this, &rb, &**output)
1160 // All regions must be explicitly specified in the output
1161 // if the lifetime elision rules do not apply. This saves
1162 // the user from potentially-confusing errors.
1163 let rb = UnelidableRscope::new(param_lifetimes);
1164 ast_ty_to_ty(this, &rb, &**output)
1167 ast::NoReturn(_) => ty::FnDiverging
1174 inputs: self_and_input_tys,
1176 variadic: decl.variadic
1178 }, explicit_self_category_result)
1181 fn determine_explicit_self_category<'a, 'tcx, AC: AstConv<'tcx>,
1185 self_info: &SelfInfo<'a, 'tcx>)
1186 -> ty::ExplicitSelfCategory
1188 return match self_info.explicit_self.node {
1189 ast::SelfStatic => ty::StaticExplicitSelfCategory,
1190 ast::SelfValue(_) => ty::ByValueExplicitSelfCategory,
1191 ast::SelfRegion(ref lifetime, mutability, _) => {
1193 opt_ast_region_to_region(this,
1195 self_info.explicit_self.span,
1197 ty::ByReferenceExplicitSelfCategory(region, mutability)
1199 ast::SelfExplicit(ref ast_type, _) => {
1200 let explicit_type = ast_ty_to_ty(this, rscope, &**ast_type);
1202 // We wish to (for now) categorize an explicit self
1203 // declaration like `self: SomeType` into either `self`,
1204 // `&self`, `&mut self`, or `Box<self>`. We do this here
1205 // by some simple pattern matching. A more precise check
1206 // is done later in `check_method_self_type()`.
1211 // impl Foo for &T {
1212 // // Legal declarations:
1213 // fn method1(self: &&T); // ByReferenceExplicitSelfCategory
1214 // fn method2(self: &T); // ByValueExplicitSelfCategory
1215 // fn method3(self: Box<&T>); // ByBoxExplicitSelfCategory
1217 // // Invalid cases will be caught later by `check_method_self_type`:
1218 // fn method_err1(self: &mut T); // ByReferenceExplicitSelfCategory
1222 // To do the check we just count the number of "modifiers"
1223 // on each type and compare them. If they are the same or
1224 // the impl has more, we call it "by value". Otherwise, we
1225 // look at the outermost modifier on the method decl and
1226 // call it by-ref, by-box as appropriate. For method1, for
1227 // example, the impl type has one modifier, but the method
1228 // type has two, so we end up with
1229 // ByReferenceExplicitSelfCategory.
1231 let impl_modifiers = count_modifiers(self_info.untransformed_self_ty);
1232 let method_modifiers = count_modifiers(explicit_type);
1234 debug!("determine_explicit_self_category(self_info.untransformed_self_ty={} \
1237 self_info.untransformed_self_ty.repr(this.tcx()),
1238 explicit_type.repr(this.tcx()),
1242 if impl_modifiers >= method_modifiers {
1243 ty::ByValueExplicitSelfCategory
1245 match explicit_type.sty {
1246 ty::ty_rptr(r, mt) => ty::ByReferenceExplicitSelfCategory(r, mt.mutbl),
1247 ty::ty_uniq(_) => ty::ByBoxExplicitSelfCategory,
1248 _ => ty::ByValueExplicitSelfCategory,
1254 fn count_modifiers(ty: Ty) -> uint {
1256 ty::ty_rptr(_, mt) => count_modifiers(mt.ty) + 1,
1257 ty::ty_uniq(t) => count_modifiers(t) + 1,
1263 pub fn ty_of_closure<'tcx, AC: AstConv<'tcx>>(
1265 fn_style: ast::FnStyle,
1266 onceness: ast::Onceness,
1267 bounds: ty::ExistentialBounds,
1268 store: ty::TraitStore,
1271 expected_sig: Option<ty::FnSig<'tcx>>)
1272 -> ty::ClosureTy<'tcx>
1274 debug!("ty_of_closure(expected_sig={})",
1275 expected_sig.repr(this.tcx()));
1277 // new region names that appear inside of the fn decl are bound to
1278 // that function type
1279 let rb = rscope::BindingRscope::new();
1281 let input_tys: Vec<_> = decl.inputs.iter().enumerate().map(|(i, a)| {
1282 let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1283 // no guarantee that the correct number of expected args
1285 if i < e.inputs.len() {
1291 ty_of_arg(this, &rb, a, expected_arg_ty)
1294 let expected_ret_ty = expected_sig.map(|e| e.output);
1296 let output_ty = match decl.output {
1297 ast::Return(ref output) if output.node == ast::TyInfer && expected_ret_ty.is_some() =>
1298 expected_ret_ty.unwrap(),
1299 ast::Return(ref output) if output.node == ast::TyInfer =>
1300 ty::FnConverging(this.ty_infer(output.span)),
1301 ast::Return(ref output) =>
1302 ty::FnConverging(ast_ty_to_ty(this, &rb, &**output)),
1303 ast::NoReturn(_) => ty::FnDiverging
1306 debug!("ty_of_closure: input_tys={}", input_tys.repr(this.tcx()));
1307 debug!("ty_of_closure: output_ty={}", output_ty.repr(this.tcx()));
1315 sig: ty::FnSig {inputs: input_tys,
1317 variadic: decl.variadic}
1321 pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1325 main_trait_refs: &[Rc<ty::TraitRef<'tcx>>],
1326 ast_bounds: &[ast::TyParamBound])
1327 -> ty::ExistentialBounds
1330 * Given an existential type like `Foo+'a+Bar`, this routine
1331 * converts the `'a` and `Bar` intos an `ExistentialBounds`
1332 * struct. The `main_trait_refs` argument specifies the `Foo` --
1333 * it is absent for closures. Eventually this should all be
1334 * normalized, I think, so that there is no "main trait ref" and
1335 * instead we just have a flat list of bounds as the existential
1339 let ast_bound_refs: Vec<&ast::TyParamBound> =
1340 ast_bounds.iter().collect();
1342 let partitioned_bounds =
1343 partition_bounds(this.tcx(), span, ast_bound_refs.as_slice());
1345 conv_existential_bounds_from_partitioned_bounds(
1346 this, rscope, span, main_trait_refs, partitioned_bounds)
1349 fn conv_ty_poly_trait_ref<'tcx, AC, RS>(
1353 ast_bounds: &[ast::TyParamBound])
1355 where AC: AstConv<'tcx>, RS:RegionScope
1357 let ast_bounds: Vec<&ast::TyParamBound> = ast_bounds.iter().collect();
1358 let mut partitioned_bounds = partition_bounds(this.tcx(), span, ast_bounds[]);
1360 let main_trait_bound = match partitioned_bounds.trait_bounds.remove(0) {
1361 Some(trait_bound) => {
1362 Some(instantiate_poly_trait_ref(this, rscope, trait_bound, None))
1365 this.tcx().sess.span_err(
1367 "at least one non-builtin trait is required for an object type");
1372 let bounds = conv_existential_bounds_from_partitioned_bounds(this,
1375 main_trait_bound.as_slice(),
1376 partitioned_bounds);
1378 match main_trait_bound {
1379 None => ty::mk_err(),
1380 Some(principal) => ty::mk_trait(this.tcx(), (*principal).clone(), bounds)
1384 pub fn conv_existential_bounds_from_partitioned_bounds<'tcx, AC, RS>(
1388 main_trait_refs: &[Rc<ty::TraitRef<'tcx>>],
1389 partitioned_bounds: PartitionedBounds)
1390 -> ty::ExistentialBounds
1391 where AC: AstConv<'tcx>, RS:RegionScope
1393 let PartitionedBounds { builtin_bounds,
1398 if !trait_bounds.is_empty() {
1399 let b = &trait_bounds[0];
1400 this.tcx().sess.span_err(
1401 b.trait_ref.path.span,
1402 format!("only the builtin traits can be used \
1403 as closure or object bounds").as_slice());
1406 // The "main trait refs", rather annoyingly, have no type
1407 // specified for the `Self` parameter of the trait. The reason for
1408 // this is that they are, after all, *existential* types, and
1409 // hence that type is unknown. However, leaving this type missing
1410 // causes the substitution code to go all awry when walking the
1411 // bounds, so here we clone those trait refs and insert ty::err as
1412 // the self type. Perhaps we should do this more generally, it'd
1413 // be convenient (or perhaps something else, i.e., ty::erased).
1414 let main_trait_refs: Vec<Rc<ty::TraitRef>> =
1415 main_trait_refs.iter()
1417 Rc::new(ty::TraitRef {
1419 substs: t.substs.with_self_ty(ty::mk_err()) }))
1422 let region_bound = compute_region_bound(this,
1426 region_bounds.as_slice(),
1427 main_trait_refs.as_slice());
1429 ty::ExistentialBounds {
1430 region_bound: region_bound,
1431 builtin_bounds: builtin_bounds,
1435 pub fn compute_opt_region_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
1437 builtin_bounds: ty::BuiltinBounds,
1438 region_bounds: &[&ast::Lifetime],
1439 trait_bounds: &[Rc<ty::TraitRef<'tcx>>])
1440 -> Option<ty::Region>
1443 * Given the bounds on a type parameter / existential type,
1444 * determines what single region bound (if any) we can use to
1445 * summarize this type. The basic idea is that we will use the
1446 * bound the user provided, if they provided one, and otherwise
1447 * search the supertypes of trait bounds for region bounds. It may
1448 * be that we can derive no bound at all, in which case we return
1452 if region_bounds.len() > 1 {
1454 region_bounds[1].span,
1455 format!("only a single explicit lifetime bound is permitted").as_slice());
1458 if region_bounds.len() != 0 {
1459 // Explicitly specified region bound. Use that.
1460 let r = region_bounds[0];
1461 return Some(ast_region_to_region(tcx, r));
1464 // No explicit region bound specified. Therefore, examine trait
1465 // bounds and see if we can derive region bounds from those.
1466 let derived_region_bounds =
1467 ty::required_region_bounds(
1473 // If there are no derived region bounds, then report back that we
1474 // can find no region bound.
1475 if derived_region_bounds.len() == 0 {
1479 // If any of the derived region bounds are 'static, that is always
1481 if derived_region_bounds.iter().any(|r| ty::ReStatic == *r) {
1482 return Some(ty::ReStatic);
1485 // Determine whether there is exactly one unique region in the set
1486 // of derived region bounds. If so, use that. Otherwise, report an
1488 let r = derived_region_bounds[0];
1489 if derived_region_bounds.slice_from(1).iter().any(|r1| r != *r1) {
1492 format!("ambiguous lifetime bound, \
1493 explicit lifetime bound required").as_slice());
1498 fn compute_region_bound<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1502 builtin_bounds: ty::BuiltinBounds,
1503 region_bounds: &[&ast::Lifetime],
1504 trait_bounds: &[Rc<ty::TraitRef<'tcx>>])
1508 * A version of `compute_opt_region_bound` for use where some
1509 * region bound is required (existential types,
1510 * basically). Reports an error if no region bound can be derived
1511 * and we are in an `rscope` that does not provide a default.
1514 match compute_opt_region_bound(this.tcx(), span, builtin_bounds,
1515 region_bounds, trait_bounds) {
1518 match rscope.default_region_bound(span) {
1521 this.tcx().sess.span_err(
1523 format!("explicit lifetime bound required").as_slice());
1531 pub struct PartitionedBounds<'a> {
1532 pub builtin_bounds: ty::BuiltinBounds,
1533 pub trait_bounds: Vec<&'a ast::PolyTraitRef>,
1534 pub region_bounds: Vec<&'a ast::Lifetime>,
1537 pub fn partition_bounds<'a>(tcx: &ty::ctxt,
1539 ast_bounds: &'a [&ast::TyParamBound])
1540 -> PartitionedBounds<'a>
1543 * Divides a list of bounds from the AST into three groups:
1544 * builtin bounds (Copy, Sized etc), general trait bounds,
1545 * and region bounds.
1548 let mut builtin_bounds = ty::empty_builtin_bounds();
1549 let mut region_bounds = Vec::new();
1550 let mut trait_bounds = Vec::new();
1551 let mut trait_def_ids = DefIdMap::new();
1552 for &ast_bound in ast_bounds.iter() {
1554 ast::TraitTyParamBound(ref b) => {
1555 match lookup_def_tcx(tcx, b.trait_ref.path.span, b.trait_ref.ref_id) {
1556 def::DefTrait(trait_did) => {
1557 match trait_def_ids.get(&trait_did) {
1558 // Already seen this trait. We forbid
1559 // duplicates in the list (for some
1563 tcx.sess, b.trait_ref.path.span, E0127,
1564 "trait `{}` already appears in the \
1566 b.trait_ref.path.user_string(tcx));
1569 "previous appearance is here");
1577 trait_def_ids.insert(trait_did, b.trait_ref.path.span);
1579 if ty::try_add_builtin_trait(tcx,
1581 &mut builtin_bounds) {
1582 continue; // success
1586 // Not a trait? that's an error, but it'll get
1590 trait_bounds.push(b);
1592 ast::RegionTyParamBound(ref l) => {
1593 region_bounds.push(l);
1599 builtin_bounds: builtin_bounds,
1600 trait_bounds: trait_bounds,
1601 region_bounds: region_bounds,