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