src/librustc/middle/typeck/astconv.rs

   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.
   4 //
   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.
  10
  11 /*!
  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`.
  15  *
  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`.
  25  *
  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.
  30  *
  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:
  35  *
  36  *   type foo = { x: &a.int, y: |&a.int| }
  37  *
  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.
  41  *
  42  * Case (b) says that if you have a type:
  43  *   type foo<'a> = ...;
  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.
  50  */
  51
  52 use middle::const_eval;
  53 use middle::def;
  54 use middle::lang_items::FnMutTraitLangItem;
  55 use rl = middle::resolve_lifetime;
  56 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
  57 use middle::ty;
  58 use middle::typeck::TypeAndSubsts;
  59 use middle::typeck::lookup_def_tcx;
  60 use middle::typeck::rscope::RegionScope;
  61 use middle::typeck::rscope;
  62 use util::ppaux::Repr;
  63
  64 use std::rc::Rc;
  65 use syntax::abi;
  66 use syntax::{ast, ast_util};
  67 use syntax::codemap::Span;
  68 use syntax::owned_slice::OwnedSlice;
  69 use syntax::print::pprust::{lifetime_to_str, path_to_str};
  70
  71 pub trait AstConv {
  72     fn tcx<'a>(&'a self) -> &'a ty::ctxt;
  73     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype;
  74     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef>;
  75
  76     // what type should we use when a type is omitted?
  77     fn ty_infer(&self, span: Span) -> ty::t;
  78 }
  79
  80 pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
  81                             -> ty::Region {
  82     let r = match tcx.named_region_map.find(&lifetime.id) {
  83         None => {
  84             // should have been recorded by the `resolve_lifetime` pass
  85             tcx.sess.span_bug(lifetime.span, "unresolved lifetime");
  86         }
  87
  88         Some(&rl::DefStaticRegion) => {
  89             ty::ReStatic
  90         }
  91
  92         Some(&rl::DefLateBoundRegion(binder_id, _, id)) => {
  93             ty::ReLateBound(binder_id, ty::BrNamed(ast_util::local_def(id),
  94                                                    lifetime.name))
  95         }
  96
  97         Some(&rl::DefEarlyBoundRegion(space, index, id)) => {
  98             ty::ReEarlyBound(id, space, index, lifetime.name)
  99         }
 100
 101         Some(&rl::DefFreeRegion(scope_id, id)) => {
 102             ty::ReFree(ty::FreeRegion {
 103                     scope_id: scope_id,
 104                     bound_region: ty::BrNamed(ast_util::local_def(id),
 105                                               lifetime.name)
 106                 })
 107         }
 108     };
 109
 110     debug!("ast_region_to_region(lifetime={} id={}) yields {}",
 111             lifetime_to_str(lifetime),
 112             lifetime.id, r.repr(tcx));
 113
 114     r
 115 }
 116
 117 pub fn opt_ast_region_to_region<AC:AstConv,RS:RegionScope>(
 118     this: &AC,
 119     rscope: &RS,
 120     default_span: Span,
 121     opt_lifetime: &Option<ast::Lifetime>) -> ty::Region
 122 {
 123     let r = match *opt_lifetime {
 124         Some(ref lifetime) => {
 125             ast_region_to_region(this.tcx(), lifetime)
 126         }
 127
 128         None => {
 129             match rscope.anon_regions(default_span, 1) {
 130                 Err(()) => {
 131                     debug!("optional region in illegal location");
 132                     this.tcx().sess.span_err(
 133                         default_span, "missing lifetime specifier");
 134                     ty::ReStatic
 135                 }
 136
 137                 Ok(rs) => {
 138                     *rs.get(0)
 139                 }
 140             }
 141         }
 142     };
 143
 144     debug!("opt_ast_region_to_region(opt_lifetime={:?}) yields {}",
 145             opt_lifetime.as_ref().map(|e| lifetime_to_str(e)),
 146             r.repr(this.tcx()));
 147
 148     r
 149 }
 150
 151 fn ast_path_substs<AC:AstConv,RS:RegionScope>(
 152     this: &AC,
 153     rscope: &RS,
 154     decl_generics: &ty::Generics,
 155     self_ty: Option<ty::t>,
 156     path: &ast::Path) -> Substs
 157 {
 158     /*!
 159      * Given a path `path` that refers to an item `I` with the
 160      * declared generics `decl_generics`, returns an appropriate
 161      * set of substitutions for this particular reference to `I`.
 162      */
 163
 164     let tcx = this.tcx();
 165
 166     // ast_path_substs() is only called to convert paths that are
 167     // known to refer to traits, types, or structs. In these cases,
 168     // all type parameters defined for the item being referenced will
 169     // be in the TypeSpace or SelfSpace.
 170     //
 171     // Note: in the case of traits, the self parameter is also
 172     // defined, but we don't currently create a `type_param_def` for
 173     // `Self` because it is implicit.
 174     assert!(decl_generics.regions.all(|d| d.space == TypeSpace));
 175     assert!(decl_generics.types.all(|d| d.space != FnSpace));
 176
 177     // If the type is parameterized by the this region, then replace this
 178     // region with the current anon region binding (in other words,
 179     // whatever & would get replaced with).
 180     let expected_num_region_params = decl_generics.regions.len(TypeSpace);
 181     let supplied_num_region_params = path.segments.last().unwrap().lifetimes.len();
 182     let regions = if expected_num_region_params == supplied_num_region_params {
 183         path.segments.last().unwrap().lifetimes.iter().map(
 184             |l| ast_region_to_region(this.tcx(), l)).collect::<Vec<_>>()
 185     } else {
 186         let anon_regions =
 187             rscope.anon_regions(path.span, expected_num_region_params);
 188
 189         if supplied_num_region_params != 0 || anon_regions.is_err() {
 190             tcx.sess.span_err(
 191                 path.span,
 192                 format!("wrong number of lifetime parameters: \
 193                         expected {} but found {}",
 194                         expected_num_region_params,
 195                         supplied_num_region_params).as_slice());
 196         }
 197
 198         match anon_regions {
 199             Ok(v) => v.move_iter().collect(),
 200             Err(()) => Vec::from_fn(expected_num_region_params,
 201                                     |_| ty::ReStatic) // hokey
 202         }
 203     };
 204
 205     // Convert the type parameters supplied by the user.
 206     let ty_param_defs = decl_generics.types.get_vec(TypeSpace);
 207     let supplied_ty_param_count = path.segments.iter().flat_map(|s| s.types.iter()).count();
 208     let formal_ty_param_count = ty_param_defs.len();
 209     let required_ty_param_count = ty_param_defs.iter()
 210                                                .take_while(|x| x.default.is_none())
 211                                                .count();
 212     if supplied_ty_param_count < required_ty_param_count {
 213         let expected = if required_ty_param_count < formal_ty_param_count {
 214             "expected at least"
 215         } else {
 216             "expected"
 217         };
 218         this.tcx().sess.span_fatal(path.span,
 219             format!("wrong number of type arguments: {} {} but found {}",
 220                     expected,
 221                     required_ty_param_count,
 222                     supplied_ty_param_count).as_slice());
 223     } else if supplied_ty_param_count > formal_ty_param_count {
 224         let expected = if required_ty_param_count < formal_ty_param_count {
 225             "expected at most"
 226         } else {
 227             "expected"
 228         };
 229         this.tcx().sess.span_fatal(path.span,
 230             format!("wrong number of type arguments: {} {} but found {}",
 231                     expected,
 232                     formal_ty_param_count,
 233                     supplied_ty_param_count).as_slice());
 234     }
 235
 236     if supplied_ty_param_count > required_ty_param_count
 237         && !this.tcx().sess.features.default_type_params.get() {
 238         this.tcx().sess.span_err(path.span, "default type parameters are \
 239                                              experimental and possibly buggy");
 240         this.tcx().sess.span_note(path.span, "add #![feature(default_type_params)] \
 241                                               to the crate attributes to enable");
 242     }
 243
 244     let tps = path.segments.iter().flat_map(|s| s.types.iter())
 245                             .map(|a_t| ast_ty_to_ty(this, rscope, &**a_t))
 246                             .collect();
 247
 248     let mut substs = Substs::new_type(tps, regions);
 249
 250     match self_ty {
 251         None => {
 252             // If no self-type is provided, it's still possible that
 253             // one was declared, because this could be an object type.
 254         }
 255         Some(ty) => {
 256             // If a self-type is provided, one should have been
 257             // "declared" (in other words, this should be a
 258             // trait-ref).
 259             assert!(decl_generics.types.get_self().is_some());
 260             substs.types.push(SelfSpace, ty);
 261         }
 262     }
 263
 264     for param in ty_param_defs.slice_from(supplied_ty_param_count).iter() {
 265         let default = param.default.unwrap();
 266         let default = default.subst_spanned(tcx, &substs, Some(path.span));
 267         substs.types.push(TypeSpace, default);
 268     }
 269
 270     substs
 271 }
 272
 273 pub fn ast_path_to_trait_ref<AC:AstConv,RS:RegionScope>(
 274         this: &AC,
 275         rscope: &RS,
 276         trait_def_id: ast::DefId,
 277         self_ty: Option<ty::t>,
 278         path: &ast::Path) -> Rc<ty::TraitRef> {
 279     let trait_def = this.get_trait_def(trait_def_id);
 280     Rc::new(ty::TraitRef {
 281         def_id: trait_def_id,
 282         substs: ast_path_substs(this, rscope, &trait_def.generics, self_ty, path)
 283     })
 284 }
 285
 286 pub fn ast_path_to_ty<AC:AstConv,RS:RegionScope>(
 287         this: &AC,
 288         rscope: &RS,
 289         did: ast::DefId,
 290         path: &ast::Path)
 291      -> TypeAndSubsts
 292 {
 293     let tcx = this.tcx();
 294     let ty::Polytype {
 295         generics: generics,
 296         ty: decl_ty
 297     } = this.get_item_ty(did);
 298
 299     let substs = ast_path_substs(this, rscope, &generics, None, path);
 300     let ty = decl_ty.subst(tcx, &substs);
 301     TypeAndSubsts { substs: substs, ty: ty }
 302 }
 303
 304 pub static NO_REGIONS: uint = 1;
 305 pub static NO_TPS: uint = 2;
 306
 307 fn check_path_args(tcx: &ty::ctxt,
 308                    path: &ast::Path,
 309                    flags: uint) {
 310     if (flags & NO_TPS) != 0u {
 311         if !path.segments.iter().all(|s| s.types.is_empty()) {
 312             tcx.sess.span_err(
 313                 path.span,
 314                 "type parameters are not allowed on this type");
 315         }
 316     }
 317
 318     if (flags & NO_REGIONS) != 0u {
 319         if !path.segments.last().unwrap().lifetimes.is_empty() {
 320             tcx.sess.span_err(
 321                 path.span,
 322                 "region parameters are not allowed on this type");
 323         }
 324     }
 325 }
 326
 327 pub fn ast_ty_to_prim_ty(tcx: &ty::ctxt, ast_ty: &ast::Ty) -> Option<ty::t> {
 328     match ast_ty.node {
 329         ast::TyPath(ref path, _, id) => {
 330             let a_def = match tcx.def_map.borrow().find(&id) {
 331                 None => {
 332                     tcx.sess.span_bug(ast_ty.span,
 333                                       format!("unbound path {}",
 334                                               path_to_str(path)).as_slice())
 335                 }
 336                 Some(&d) => d
 337             };
 338             match a_def {
 339                 def::DefPrimTy(nty) => {
 340                     match nty {
 341                         ast::TyBool => {
 342                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 343                             Some(ty::mk_bool())
 344                         }
 345                         ast::TyChar => {
 346                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 347                             Some(ty::mk_char())
 348                         }
 349                         ast::TyInt(it) => {
 350                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 351                             Some(ty::mk_mach_int(it))
 352                         }
 353                         ast::TyUint(uit) => {
 354                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 355                             Some(ty::mk_mach_uint(uit))
 356                         }
 357                         ast::TyFloat(ft) => {
 358                             if ft == ast::TyF128 && !tcx.sess.features.quad_precision_float.get() {
 359                                 tcx.sess.span_err(path.span, "quadruple precision floats are \
 360                                                               missing complete runtime support");
 361                                 tcx.sess.span_note(path.span, "add \
 362                                                                #[feature(quad_precision_float)] \
 363                                                                to the crate attributes to enable");
 364                             }
 365                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 366                             Some(ty::mk_mach_float(ft))
 367                         }
 368                         ast::TyStr => {
 369                             tcx.sess.span_err(ast_ty.span,
 370                                               "bare `str` is not a type");
 371                             // return /something/ so they can at least get more errors
 372                             Some(ty::mk_uniq(tcx, ty::mk_str(tcx)))
 373                         }
 374                     }
 375                 }
 376                 _ => None
 377             }
 378         }
 379         _ => None
 380     }
 381 }
 382
 383 /// Converts the given AST type to a built-in type. A "built-in type" is, at
 384 /// present, either a core numeric type, a string, or `Box`.
 385 pub fn ast_ty_to_builtin_ty<AC:AstConv,
 386                             RS:RegionScope>(
 387                             this: &AC,
 388                             rscope: &RS,
 389                             ast_ty: &ast::Ty)
 390                             -> Option<ty::t> {
 391     match ast_ty_to_prim_ty(this.tcx(), ast_ty) {
 392         Some(typ) => return Some(typ),
 393         None => {}
 394     }
 395
 396     match ast_ty.node {
 397         ast::TyPath(ref path, _, id) => {
 398             let a_def = match this.tcx().def_map.borrow().find(&id) {
 399                 None => {
 400                     this.tcx()
 401                         .sess
 402                         .span_bug(ast_ty.span,
 403                                   format!("unbound path {}",
 404                                           path_to_str(path)).as_slice())
 405                 }
 406                 Some(&d) => d
 407             };
 408
 409             // FIXME(#12938): This is a hack until we have full support for
 410             // DST.
 411             match a_def {
 412                 def::DefTy(did) | def::DefStruct(did)
 413                         if Some(did) == this.tcx().lang_items.owned_box() => {
 414                     if path.segments
 415                            .iter()
 416                            .flat_map(|s| s.types.iter())
 417                            .count() > 1 {
 418                         this.tcx()
 419                             .sess
 420                             .span_err(path.span,
 421                                       "`Box` has only one type parameter")
 422                     }
 423
 424                     for inner_ast_type in path.segments
 425                                               .iter()
 426                                               .flat_map(|s| s.types.iter()) {
 427                         let mt = ast::MutTy {
 428                             ty: *inner_ast_type,
 429                             mutbl: ast::MutImmutable,
 430                         };
 431                         return Some(mk_pointer(this,
 432                                                rscope,
 433                                                &mt,
 434                                                Uniq,
 435                                                |typ| {
 436                             match ty::get(typ).sty {
 437                                 ty::ty_str => {
 438                                     this.tcx()
 439                                         .sess
 440                                         .span_err(path.span,
 441                                                   "`Box<str>` is not a type");
 442                                     ty::mk_err()
 443                                 }
 444                                 ty::ty_vec(_, None) => {
 445                                     this.tcx()
 446                                         .sess
 447                                         .span_err(path.span,
 448                                                   "`Box<[T]>` is not a type");
 449                                     ty::mk_err()
 450                                 }
 451                                 _ => ty::mk_uniq(this.tcx(), typ),
 452                             }
 453                         }))
 454                     }
 455                     this.tcx().sess.span_err(path.span,
 456                                              "not enough type parameters \
 457                                               supplied to `Box<T>`");
 458                     Some(ty::mk_err())
 459                 }
 460                 def::DefTy(did) | def::DefStruct(did)
 461                         if Some(did) == this.tcx().lang_items.gc() => {
 462                     if path.segments
 463                            .iter()
 464                            .flat_map(|s| s.types.iter())
 465                            .count() > 1 {
 466                         this.tcx()
 467                             .sess
 468                             .span_err(path.span,
 469                                       "`Gc` has only one type parameter")
 470                     }
 471
 472                     for inner_ast_type in path.segments
 473                                               .iter()
 474                                               .flat_map(|s| s.types.iter()) {
 475                         let mt = ast::MutTy {
 476                             ty: *inner_ast_type,
 477                             mutbl: ast::MutImmutable,
 478                         };
 479                         return Some(mk_pointer(this,
 480                                                rscope,
 481                                                &mt,
 482                                                Box,
 483                                                |typ| {
 484                             match ty::get(typ).sty {
 485                                 ty::ty_str => {
 486                                     this.tcx()
 487                                         .sess
 488                                         .span_err(path.span,
 489                                                   "`Gc<str>` is not a type");
 490                                     ty::mk_err()
 491                                 }
 492                                 ty::ty_vec(_, None) => {
 493                                     this.tcx()
 494                                         .sess
 495                                         .span_err(path.span,
 496                                                   "`Gc<[T]>` is not a type");
 497                                     ty::mk_err()
 498                                 }
 499                                 _ => ty::mk_box(this.tcx(), typ),
 500                             }
 501                         }))
 502                     }
 503                     this.tcx().sess.span_bug(path.span,
 504                                              "not enough type parameters \
 505                                               supplied to `Gc<T>`")
 506                 }
 507                 _ => None
 508             }
 509         }
 510         _ => None
 511     }
 512 }
 513
 514 enum PointerTy {
 515     Box,
 516     RPtr(ty::Region),
 517     Uniq
 518 }
 519
 520 fn ast_ty_to_mt<AC:AstConv, RS:RegionScope>(this: &AC,
 521                                             rscope: &RS,
 522                                             ty: &ast::Ty) -> ty::mt {
 523     ty::mt {ty: ast_ty_to_ty(this, rscope, ty), mutbl: ast::MutImmutable}
 524 }
 525
 526 pub fn trait_ref_for_unboxed_function<AC:AstConv,
 527                                       RS:RegionScope>(
 528                                           this: &AC,
 529                                           rscope: &RS,
 530                                           unboxed_function: &ast::UnboxedFnTy,
 531                                           self_ty: Option<ty::t>)
 532     -> ty::TraitRef
 533 {
 534     let fn_mut_trait_did = this.tcx()
 535                                .lang_items
 536                                .require(FnMutTraitLangItem)
 537                                .unwrap();
 538     let input_types =
 539         unboxed_function.decl
 540                         .inputs
 541                         .iter()
 542                         .map(|input| {
 543                             ast_ty_to_ty(this, rscope, &*input.ty)
 544                         }).collect::<Vec<_>>();
 545     let input_tuple = ty::mk_tup(this.tcx(), input_types);
 546     let output_type = ast_ty_to_ty(this,
 547                                    rscope,
 548                                    &*unboxed_function.decl.output);
 549     let mut substs = Substs::new_type(vec!(input_tuple, output_type),
 550                                              Vec::new());
 551
 552     match self_ty {
 553         Some(s) => substs.types.push(SelfSpace, s),
 554         None => ()
 555     }
 556
 557     ty::TraitRef {
 558         def_id: fn_mut_trait_did,
 559         substs: substs,
 560     }
 561 }
 562
 563 // Handle `~`, `Box`, and `&` being able to mean strs and vecs.
 564 // If a_seq_ty is a str or a vec, make it a str/vec.
 565 // Also handle first-class trait types.
 566 fn mk_pointer<AC:AstConv,
 567               RS:RegionScope>(
 568               this: &AC,
 569               rscope: &RS,
 570               a_seq_ty: &ast::MutTy,
 571               ptr_ty: PointerTy,
 572               constr: |ty::t| -> ty::t)
 573               -> ty::t {
 574     let tcx = this.tcx();
 575     debug!("mk_pointer(ptr_ty={:?})", ptr_ty);
 576
 577     match a_seq_ty.ty.node {
 578         ast::TyVec(ref ty) => {
 579             let mut mt = ast_ty_to_mt(this, rscope, &**ty);
 580             if a_seq_ty.mutbl == ast::MutMutable {
 581                 mt.mutbl = ast::MutMutable;
 582             }
 583             return constr(ty::mk_vec(tcx, mt, None));
 584         }
 585         ast::TyUnboxedFn(ref unboxed_function) => {
 586             let ty::TraitRef {
 587                 def_id,
 588                 substs
 589             } = trait_ref_for_unboxed_function(this,
 590                                                rscope,
 591                                                &**unboxed_function,
 592                                                None);
 593             let tr = ty::mk_trait(this.tcx(),
 594                                   def_id,
 595                                   substs,
 596                                   ty::empty_builtin_bounds());
 597             match ptr_ty {
 598                 Uniq => {
 599                     return ty::mk_uniq(this.tcx(), tr);
 600                 }
 601                 RPtr(r) => {
 602                     return ty::mk_rptr(this.tcx(),
 603                                        r,
 604                                        ty::mt {mutbl: a_seq_ty.mutbl, ty: tr});
 605                 }
 606                 _ => {
 607                     tcx.sess.span_err(
 608                         a_seq_ty.ty.span,
 609                         "~trait or &trait are the only supported \
 610                          forms of casting-to-trait");
 611                     return ty::mk_err();
 612                 }
 613
 614             }
 615         }
 616         ast::TyPath(ref path, ref bounds, id) => {
 617             // Note that the "bounds must be empty if path is not a trait"
 618             // restriction is enforced in the below case for ty_path, which
 619             // will run after this as long as the path isn't a trait.
 620             match tcx.def_map.borrow().find(&id) {
 621                 Some(&def::DefPrimTy(ast::TyStr)) => {
 622                     check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 623                     match ptr_ty {
 624                         Uniq => {
 625                             return constr(ty::mk_str(tcx));
 626                         }
 627                         RPtr(r) => {
 628                             return ty::mk_str_slice(tcx, r, ast::MutImmutable);
 629                         }
 630                         _ => {
 631                             tcx.sess
 632                                .span_err(path.span,
 633                                          "managed strings are not supported")
 634                         }
 635                     }
 636                 }
 637                 Some(&def::DefTrait(trait_def_id)) => {
 638                     let result = ast_path_to_trait_ref(
 639                         this, rscope, trait_def_id, None, path);
 640                     let trait_store = match ptr_ty {
 641                         Uniq => ty::UniqTraitStore,
 642                         RPtr(r) => {
 643                             ty::RegionTraitStore(r, a_seq_ty.mutbl)
 644                         }
 645                         _ => {
 646                             tcx.sess.span_err(
 647                                 path.span,
 648                                 "~trait or &trait are the only supported \
 649                                  forms of casting-to-trait");
 650                             return ty::mk_err();
 651                         }
 652                     };
 653                     let bounds = conv_builtin_bounds(this.tcx(),
 654                                                      path.span,
 655                                                      bounds,
 656                                                      trait_store);
 657                     let tr = ty::mk_trait(tcx,
 658                                           result.def_id,
 659                                           result.substs.clone(),
 660                                           bounds);
 661                     // We could just match on ptr_ty, but we need to pass a trait
 662                     // store to conv_builtin_bounds, so mathc twice for now.
 663                     return match trait_store {
 664                         ty::UniqTraitStore => {
 665                             return ty::mk_uniq(tcx, tr);
 666                         }
 667                         ty::RegionTraitStore(r, m) => {
 668                             return ty::mk_rptr(tcx, r, ty::mt{mutbl: m, ty: tr});
 669                         }
 670                     }
 671                 }
 672                 _ => {}
 673             }
 674         }
 675         _ => {}
 676     }
 677
 678     constr(ast_ty_to_ty(this, rscope, &*a_seq_ty.ty))
 679 }
 680
 681 // Parses the programmer's textual representation of a type into our
 682 // internal notion of a type.
 683 pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
 684     this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> ty::t {
 685
 686     let tcx = this.tcx();
 687
 688     let mut ast_ty_to_ty_cache = tcx.ast_ty_to_ty_cache.borrow_mut();
 689     match ast_ty_to_ty_cache.find(&ast_ty.id) {
 690         Some(&ty::atttce_resolved(ty)) => return ty,
 691         Some(&ty::atttce_unresolved) => {
 692             tcx.sess.span_fatal(ast_ty.span,
 693                                 "illegal recursive type; insert an enum \
 694                                  or struct in the cycle, if this is \
 695                                  desired");
 696         }
 697         None => { /* go on */ }
 698     }
 699     ast_ty_to_ty_cache.insert(ast_ty.id, ty::atttce_unresolved);
 700     drop(ast_ty_to_ty_cache);
 701
 702     let typ = ast_ty_to_builtin_ty(this, rscope, ast_ty).unwrap_or_else(|| {
 703         match ast_ty.node {
 704             ast::TyNil => ty::mk_nil(),
 705             ast::TyBot => ty::mk_bot(),
 706             ast::TyBox(ty) => {
 707                 let mt = ast::MutTy { ty: ty, mutbl: ast::MutImmutable };
 708                 mk_pointer(this, rscope, &mt, Box, |ty| ty::mk_box(tcx, ty))
 709             }
 710             ast::TyUniq(ty) => {
 711                 let mt = ast::MutTy { ty: ty, mutbl: ast::MutImmutable };
 712                 mk_pointer(this, rscope, &mt, Uniq,
 713                            |ty| ty::mk_uniq(tcx, ty))
 714             }
 715             ast::TyVec(ty) => {
 716                 tcx.sess.span_err(ast_ty.span, "bare `[]` is not a type");
 717                 // return /something/ so they can at least get more errors
 718                 let vec_ty = ty::mk_vec(tcx, ast_ty_to_mt(this, rscope, &*ty), None);
 719                 ty::mk_uniq(tcx, vec_ty)
 720             }
 721             ast::TyPtr(ref mt) => {
 722                 ty::mk_ptr(tcx, ty::mt {
 723                     ty: ast_ty_to_ty(this, rscope, &*mt.ty),
 724                     mutbl: mt.mutbl
 725                 })
 726             }
 727             ast::TyRptr(ref region, ref mt) => {
 728                 let r = opt_ast_region_to_region(this, rscope, ast_ty.span, region);
 729                 debug!("ty_rptr r={}", r.repr(this.tcx()));
 730                 mk_pointer(this, rscope, mt, RPtr(r),
 731                            |ty| ty::mk_rptr(tcx, r, ty::mt {ty: ty, mutbl: mt.mutbl}))
 732             }
 733             ast::TyTup(ref fields) => {
 734                 let flds = fields.iter()
 735                                  .map(|t| ast_ty_to_ty(this, rscope, &**t))
 736                                  .collect();
 737                 ty::mk_tup(tcx, flds)
 738             }
 739             ast::TyParen(ref typ) => ast_ty_to_ty(this, rscope, &**typ),
 740             ast::TyBareFn(ref bf) => {
 741                 if bf.decl.variadic && bf.abi != abi::C {
 742                     tcx.sess.span_err(ast_ty.span,
 743                                       "variadic function must have C calling convention");
 744                 }
 745                 ty::mk_bare_fn(tcx, ty_of_bare_fn(this, ast_ty.id, bf.fn_style,
 746                                                   bf.abi, &*bf.decl))
 747             }
 748             ast::TyClosure(ref f, ref region) => {
 749
 750                 // resolve the function bound region in the original region
 751                 // scope `rscope`, not the scope of the function parameters
 752                 let bound_region = opt_ast_region_to_region(this, rscope,
 753                                                             ast_ty.span, region);
 754
 755                 let store = ty::RegionTraitStore(bound_region, ast::MutMutable);
 756
 757                 // Use corresponding trait store to figure out default bounds
 758                 // if none were specified.
 759                 let bounds = conv_builtin_bounds(this.tcx(),
 760                                                  ast_ty.span,
 761                                                  &f.bounds,
 762                                                  store);
 763
 764                 let fn_decl = ty_of_closure(this,
 765                                             ast_ty.id,
 766                                             f.fn_style,
 767                                             f.onceness,
 768                                             bounds,
 769                                             store,
 770                                             &*f.decl,
 771                                             None);
 772                 ty::mk_closure(tcx, fn_decl)
 773             }
 774             ast::TyProc(ref f) => {
 775                 // Use corresponding trait store to figure out default bounds
 776                 // if none were specified.
 777                 let bounds = conv_builtin_bounds(this.tcx(),
 778                                                  ast_ty.span,
 779                                                  &f.bounds,
 780                                                  ty::UniqTraitStore);
 781
 782                 let fn_decl = ty_of_closure(this,
 783                                             ast_ty.id,
 784                                             f.fn_style,
 785                                             f.onceness,
 786                                             bounds,
 787                                             ty::UniqTraitStore,
 788                                             &*f.decl,
 789                                             None);
 790                 ty::mk_closure(tcx, fn_decl)
 791             }
 792             ast::TyUnboxedFn(_) => {
 793                 tcx.sess.span_err(ast_ty.span,
 794                                   "cannot use unboxed functions here");
 795                 ty::mk_err()
 796             }
 797             ast::TyPath(ref path, ref bounds, id) => {
 798                 let a_def = match tcx.def_map.borrow().find(&id) {
 799                     None => {
 800                         tcx.sess
 801                            .span_bug(ast_ty.span,
 802                                      format!("unbound path {}",
 803                                              path_to_str(path)).as_slice())
 804                     }
 805                     Some(&d) => d
 806                 };
 807                 // Kind bounds on path types are only supported for traits.
 808                 match a_def {
 809                     // But don't emit the error if the user meant to do a trait anyway.
 810                     def::DefTrait(..) => { },
 811                     _ if bounds.is_some() =>
 812                         tcx.sess.span_err(ast_ty.span,
 813                                           "kind bounds can only be used on trait types"),
 814                     _ => { },
 815                 }
 816                 match a_def {
 817                     def::DefTrait(_) => {
 818                         let path_str = path_to_str(path);
 819                         tcx.sess.span_err(
 820                             ast_ty.span,
 821                             format!("reference to trait `{name}` where a \
 822                                      type is expected; try `Box<{name}>` or \
 823                                      `&{name}`",
 824                                     name=path_str).as_slice());
 825                         ty::mk_err()
 826                     }
 827                     def::DefTy(did) | def::DefStruct(did) => {
 828                         ast_path_to_ty(this, rscope, did, path).ty
 829                     }
 830                     def::DefTyParam(space, id, n) => {
 831                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 832                         ty::mk_param(tcx, space, n, id)
 833                     }
 834                     def::DefSelfTy(id) => {
 835                         // n.b.: resolve guarantees that the this type only appears in a
 836                         // trait, which we rely upon in various places when creating
 837                         // substs
 838                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 839                         let did = ast_util::local_def(id);
 840                         ty::mk_self_type(tcx, did)
 841                     }
 842                     def::DefMod(id) => {
 843                         tcx.sess.span_fatal(ast_ty.span,
 844                             format!("found module name used as a type: {}",
 845                                     tcx.map.node_to_str(id.node)).as_slice());
 846                     }
 847                     def::DefPrimTy(_) => {
 848                         fail!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
 849                     }
 850                     _ => {
 851                         tcx.sess.span_fatal(ast_ty.span,
 852                                             format!("found value name used \
 853                                                      as a type: {:?}",
 854                                                     a_def).as_slice());
 855                     }
 856                 }
 857             }
 858             ast::TyFixedLengthVec(ty, e) => {
 859                 match const_eval::eval_const_expr_partial(tcx, &*e) {
 860                     Ok(ref r) => {
 861                         match *r {
 862                             const_eval::const_int(i) =>
 863                                 ty::mk_vec(tcx, ast_ty_to_mt(this, rscope, &*ty),
 864                                            Some(i as uint)),
 865                             const_eval::const_uint(i) =>
 866                                 ty::mk_vec(tcx, ast_ty_to_mt(this, rscope, &*ty),
 867                                            Some(i as uint)),
 868                             _ => {
 869                                 tcx.sess.span_fatal(
 870                                     ast_ty.span, "expected constant expr for vector length");
 871                             }
 872                         }
 873                     }
 874                     Err(ref r) => {
 875                         tcx.sess.span_fatal(
 876                             ast_ty.span,
 877                             format!("expected constant expr for vector \
 878                                      length: {}",
 879                                     *r).as_slice());
 880                     }
 881                 }
 882             }
 883             ast::TyTypeof(_e) => {
 884                 tcx.sess.span_bug(ast_ty.span, "typeof is reserved but unimplemented");
 885             }
 886             ast::TyInfer => {
 887                 // TyInfer also appears as the type of arguments or return
 888                 // values in a ExprFnBlock or ExprProc, or as the type of
 889                 // local variables. Both of these cases are handled specially
 890                 // and will not descend into this routine.
 891                 this.ty_infer(ast_ty.span)
 892             }
 893         }
 894     });
 895
 896     tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, ty::atttce_resolved(typ));
 897     return typ;
 898 }
 899
 900 pub fn ty_of_arg<AC: AstConv, RS: RegionScope>(this: &AC, rscope: &RS, a: &ast::Arg,
 901                                                expected_ty: Option<ty::t>) -> ty::t {
 902     match a.ty.node {
 903         ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
 904         ast::TyInfer => this.ty_infer(a.ty.span),
 905         _ => ast_ty_to_ty(this, rscope, &*a.ty),
 906     }
 907 }
 908
 909 struct SelfInfo {
 910     untransformed_self_ty: ty::t,
 911     explicit_self: ast::ExplicitSelf
 912 }
 913
 914 pub fn ty_of_method<AC:AstConv>(
 915     this: &AC,
 916     id: ast::NodeId,
 917     fn_style: ast::FnStyle,
 918     untransformed_self_ty: ty::t,
 919     explicit_self: ast::ExplicitSelf,
 920     decl: &ast::FnDecl)
 921     -> ty::BareFnTy
 922 {
 923     ty_of_method_or_bare_fn(this, id, fn_style, abi::Rust, Some(SelfInfo {
 924         untransformed_self_ty: untransformed_self_ty,
 925         explicit_self: explicit_self
 926     }), decl)
 927 }
 928
 929 pub fn ty_of_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
 930                                  fn_style: ast::FnStyle, abi: abi::Abi,
 931                                  decl: &ast::FnDecl) -> ty::BareFnTy {
 932     ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl)
 933 }
 934
 935 fn ty_of_method_or_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
 936                                        fn_style: ast::FnStyle, abi: abi::Abi,
 937                                        opt_self_info: Option<SelfInfo>,
 938                                        decl: &ast::FnDecl) -> ty::BareFnTy {
 939     debug!("ty_of_method_or_bare_fn");
 940
 941     // new region names that appear inside of the fn decl are bound to
 942     // that function type
 943     let rb = rscope::BindingRscope::new(id);
 944
 945     let self_ty = opt_self_info.and_then(|self_info| {
 946         match self_info.explicit_self.node {
 947             ast::SelfStatic => None,
 948             ast::SelfValue => {
 949                 Some(self_info.untransformed_self_ty)
 950             }
 951             ast::SelfRegion(ref lifetime, mutability) => {
 952                 let region =
 953                     opt_ast_region_to_region(this, &rb,
 954                                              self_info.explicit_self.span,
 955                                              lifetime);
 956                 Some(ty::mk_rptr(this.tcx(), region,
 957                                  ty::mt {ty: self_info.untransformed_self_ty,
 958                                          mutbl: mutability}))
 959             }
 960             ast::SelfUniq => {
 961                 Some(ty::mk_uniq(this.tcx(), self_info.untransformed_self_ty))
 962             }
 963         }
 964     });
 965
 966     // HACK(eddyb) replace the fake self type in the AST with the actual type.
 967     let input_tys = if self_ty.is_some() {
 968         decl.inputs.slice_from(1)
 969     } else {
 970         decl.inputs.as_slice()
 971     };
 972     let input_tys = input_tys.iter().map(|a| ty_of_arg(this, &rb, a, None));
 973
 974     let self_and_input_tys = self_ty.move_iter().chain(input_tys).collect();
 975
 976     let output_ty = match decl.output.node {
 977         ast::TyInfer => this.ty_infer(decl.output.span),
 978         _ => ast_ty_to_ty(this, &rb, &*decl.output)
 979     };
 980
 981     return ty::BareFnTy {
 982         fn_style: fn_style,
 983         abi: abi,
 984         sig: ty::FnSig {
 985             binder_id: id,
 986             inputs: self_and_input_tys,
 987             output: output_ty,
 988             variadic: decl.variadic
 989         }
 990     };
 991 }
 992
 993 pub fn ty_of_closure<AC:AstConv>(
 994     this: &AC,
 995     id: ast::NodeId,
 996     fn_style: ast::FnStyle,
 997     onceness: ast::Onceness,
 998     bounds: ty::BuiltinBounds,
 999     store: ty::TraitStore,
1000     decl: &ast::FnDecl,
1001     expected_sig: Option<ty::FnSig>)
1002     -> ty::ClosureTy
1003 {
1004     debug!("ty_of_fn_decl");
1005
1006     // new region names that appear inside of the fn decl are bound to
1007     // that function type
1008     let rb = rscope::BindingRscope::new(id);
1009
1010     let input_tys = decl.inputs.iter().enumerate().map(|(i, a)| {
1011         let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1012             // no guarantee that the correct number of expected args
1013             // were supplied
1014             if i < e.inputs.len() {
1015                 Some(*e.inputs.get(i))
1016             } else {
1017                 None
1018             }
1019         });
1020         ty_of_arg(this, &rb, a, expected_arg_ty)
1021     }).collect();
1022
1023     let expected_ret_ty = expected_sig.map(|e| e.output);
1024     let output_ty = match decl.output.node {
1025         ast::TyInfer if expected_ret_ty.is_some() => expected_ret_ty.unwrap(),
1026         ast::TyInfer => this.ty_infer(decl.output.span),
1027         _ => ast_ty_to_ty(this, &rb, &*decl.output)
1028     };
1029
1030     ty::ClosureTy {
1031         fn_style: fn_style,
1032         onceness: onceness,
1033         store: store,
1034         bounds: bounds,
1035         sig: ty::FnSig {binder_id: id,
1036                         inputs: input_tys,
1037                         output: output_ty,
1038                         variadic: decl.variadic}
1039     }
1040 }
1041
1042 fn conv_builtin_bounds(tcx: &ty::ctxt,
1043                        span: Span,
1044                        ast_bounds: &Option<OwnedSlice<ast::TyParamBound>>,
1045                        store: ty::TraitStore)
1046                        -> ty::BuiltinBounds {
1047     //! Converts a list of bounds from the AST into a `BuiltinBounds`
1048     //! struct. Reports an error if any of the bounds that appear
1049     //! in the AST refer to general traits and not the built-in traits
1050     //! like `Send`. Used to translate the bounds that
1051     //! appear in closure and trait types, where only builtin bounds are
1052     //! legal.
1053     //! If no bounds were specified, we choose a "default" bound based on
1054     //! the allocation type of the fn/trait, as per issue #7264. The user can
1055     //! override this with an empty bounds list, e.g. "Box<fn:()>" or
1056     //! "Box<Trait:>".
1057
1058     match (ast_bounds, store) {
1059         (&Some(ref bound_vec), _) => {
1060             let mut builtin_bounds = ty::empty_builtin_bounds();
1061             for ast_bound in bound_vec.iter() {
1062                 match *ast_bound {
1063                     ast::TraitTyParamBound(ref b) => {
1064                         match lookup_def_tcx(tcx, b.path.span, b.ref_id) {
1065                             def::DefTrait(trait_did) => {
1066                                 if ty::try_add_builtin_trait(tcx, trait_did,
1067                                                              &mut builtin_bounds) {
1068                                     continue; // success
1069                                 }
1070                             }
1071                             _ => { }
1072                         }
1073                         tcx.sess.span_fatal(
1074                             b.path.span,
1075                             "only the builtin traits can be used as closure \
1076                              or object bounds");
1077                     }
1078                     ast::StaticRegionTyParamBound => {
1079                         builtin_bounds.add(ty::BoundStatic);
1080                     }
1081                     ast::UnboxedFnTyParamBound(_) => {
1082                         tcx.sess.span_err(span,
1083                                           "unboxed functions are not allowed \
1084                                            here");
1085                     }
1086                     ast::OtherRegionTyParamBound(span) => {
1087                         if !tcx.sess.features.issue_5723_bootstrap.get() {
1088                             tcx.sess.span_err(
1089                                 span,
1090                                 "only the 'static lifetime is accepted \
1091                                  here.");
1092                         }
1093                     }
1094                 }
1095             }
1096             builtin_bounds
1097         },
1098         // &'static Trait is sugar for &'static Trait:'static.
1099         (&None, ty::RegionTraitStore(ty::ReStatic, _)) => {
1100             let mut set = ty::empty_builtin_bounds(); set.add(ty::BoundStatic); set
1101         }
1102         // No bounds are automatically applied for &'r Trait or ~Trait
1103         (&None, ty::RegionTraitStore(..)) |
1104         (&None, ty::UniqTraitStore) => ty::empty_builtin_bounds(),
1105     }
1106 }