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