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::{FnTraitLangItem, FnMutTraitLangItem};
  55 use middle::lang_items::{FnOnceTraitLangItem};
  56 use middle::resolve_lifetime as rl;
  57 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
  58 use middle::subst::{VecPerParamSpace};
  59 use middle::ty;
  60 use middle::typeck::lookup_def_tcx;
  61 use middle::typeck::infer;
  62 use middle::typeck::rscope::{ExplicitRscope, RegionScope, SpecificRscope};
  63 use middle::typeck::rscope;
  64 use middle::typeck::TypeAndSubsts;
  65 use middle::typeck;
  66 use util::ppaux::{Repr, UserString};
  67
  68 use std::collections::HashMap;
  69 use std::rc::Rc;
  70 use syntax::abi;
  71 use syntax::{ast, ast_util};
  72 use syntax::codemap::Span;
  73 use syntax::parse::token;
  74
  75 pub trait AstConv<'tcx> {
  76     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
  77     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype;
  78     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef>;
  79
  80     /// What type should we use when a type is omitted?
  81     fn ty_infer(&self, span: Span) -> ty::t;
  82
  83     /// Returns true if associated types from the given trait and type are
  84     /// allowed to be used here and false otherwise.
  85     fn associated_types_of_trait_are_valid(&self,
  86                                            ty: ty::t,
  87                                            trait_id: ast::DefId)
  88                                            -> bool;
  89
  90     /// Returns the binding of the given associated type for some type.
  91     fn associated_type_binding(&self,
  92                                span: Span,
  93                                ty: Option<ty::t>,
  94                                trait_id: ast::DefId,
  95                                associated_type_id: ast::DefId)
  96                                -> ty::t;
  97 }
  98
  99 pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
 100                             -> ty::Region {
 101     let r = match tcx.named_region_map.find(&lifetime.id) {
 102         None => {
 103             // should have been recorded by the `resolve_lifetime` pass
 104             tcx.sess.span_bug(lifetime.span, "unresolved lifetime");
 105         }
 106
 107         Some(&rl::DefStaticRegion) => {
 108             ty::ReStatic
 109         }
 110
 111         Some(&rl::DefLateBoundRegion(binder_id, _, id)) => {
 112             ty::ReLateBound(binder_id, ty::BrNamed(ast_util::local_def(id),
 113                                                    lifetime.name))
 114         }
 115
 116         Some(&rl::DefEarlyBoundRegion(space, index, id)) => {
 117             ty::ReEarlyBound(id, space, index, lifetime.name)
 118         }
 119
 120         Some(&rl::DefFreeRegion(scope_id, id)) => {
 121             ty::ReFree(ty::FreeRegion {
 122                     scope_id: scope_id,
 123                     bound_region: ty::BrNamed(ast_util::local_def(id),
 124                                               lifetime.name)
 125                 })
 126         }
 127     };
 128
 129     debug!("ast_region_to_region(lifetime={} id={}) yields {}",
 130            lifetime.repr(tcx),
 131            lifetime.id,
 132            r.repr(tcx));
 133
 134     r
 135 }
 136
 137 pub fn opt_ast_region_to_region<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 138     this: &AC,
 139     rscope: &RS,
 140     default_span: Span,
 141     opt_lifetime: &Option<ast::Lifetime>) -> ty::Region
 142 {
 143     let r = match *opt_lifetime {
 144         Some(ref lifetime) => {
 145             ast_region_to_region(this.tcx(), lifetime)
 146         }
 147
 148         None => {
 149             match rscope.anon_regions(default_span, 1) {
 150                 Err(()) => {
 151                     debug!("optional region in illegal location");
 152                     span_err!(this.tcx().sess, default_span, E0106,
 153                         "missing lifetime specifier");
 154                     ty::ReStatic
 155                 }
 156
 157                 Ok(rs) => {
 158                     *rs.get(0)
 159                 }
 160             }
 161         }
 162     };
 163
 164     debug!("opt_ast_region_to_region(opt_lifetime={}) yields {}",
 165             opt_lifetime.repr(this.tcx()),
 166             r.repr(this.tcx()));
 167
 168     r
 169 }
 170
 171 fn ast_path_substs<'tcx,AC,RS>(
 172                    this: &AC,
 173                    rscope: &RS,
 174                    decl_def_id: ast::DefId,
 175                    decl_generics: &ty::Generics,
 176                    self_ty: Option<ty::t>,
 177                    associated_ty: Option<ty::t>,
 178                    path: &ast::Path)
 179                    -> Substs
 180                    where AC: AstConv<'tcx>, RS: RegionScope {
 181     /*!
 182      * Given a path `path` that refers to an item `I` with the
 183      * declared generics `decl_generics`, returns an appropriate
 184      * set of substitutions for this particular reference to `I`.
 185      */
 186
 187     let tcx = this.tcx();
 188
 189     // ast_path_substs() is only called to convert paths that are
 190     // known to refer to traits, types, or structs. In these cases,
 191     // all type parameters defined for the item being referenced will
 192     // be in the TypeSpace or SelfSpace.
 193     //
 194     // Note: in the case of traits, the self parameter is also
 195     // defined, but we don't currently create a `type_param_def` for
 196     // `Self` because it is implicit.
 197     assert!(decl_generics.regions.all(|d| d.space == TypeSpace));
 198     assert!(decl_generics.types.all(|d| d.space != FnSpace));
 199
 200     // If the type is parameterized by the this region, then replace this
 201     // region with the current anon region binding (in other words,
 202     // whatever & would get replaced with).
 203     let expected_num_region_params = decl_generics.regions.len(TypeSpace);
 204     let supplied_num_region_params = path.segments.last().unwrap().lifetimes.len();
 205     let regions = if expected_num_region_params == supplied_num_region_params {
 206         path.segments.last().unwrap().lifetimes.iter().map(
 207             |l| ast_region_to_region(this.tcx(), l)).collect::<Vec<_>>()
 208     } else {
 209         let anon_regions =
 210             rscope.anon_regions(path.span, expected_num_region_params);
 211
 212         if supplied_num_region_params != 0 || anon_regions.is_err() {
 213             span_err!(tcx.sess, path.span, E0107,
 214                 "wrong number of lifetime parameters: expected {}, found {}",
 215                 expected_num_region_params, supplied_num_region_params);
 216         }
 217
 218         match anon_regions {
 219             Ok(v) => v.into_iter().collect(),
 220             Err(()) => Vec::from_fn(expected_num_region_params,
 221                                     |_| ty::ReStatic) // hokey
 222         }
 223     };
 224
 225     // Convert the type parameters supplied by the user.
 226     let ty_param_defs = decl_generics.types.get_slice(TypeSpace);
 227     let supplied_ty_param_count = path.segments.iter().flat_map(|s| s.types.iter()).count();
 228     let formal_ty_param_count =
 229         ty_param_defs.iter()
 230                      .take_while(|x| !ty::is_associated_type(tcx, x.def_id))
 231                      .count();
 232     let required_ty_param_count =
 233         ty_param_defs.iter()
 234                      .take_while(|x| {
 235                         x.default.is_none() &&
 236                         !ty::is_associated_type(tcx, x.def_id)
 237                      })
 238                      .count();
 239     if supplied_ty_param_count < required_ty_param_count {
 240         let expected = if required_ty_param_count < formal_ty_param_count {
 241             "expected at least"
 242         } else {
 243             "expected"
 244         };
 245         this.tcx().sess.span_fatal(path.span,
 246             format!("wrong number of type arguments: {} {}, found {}",
 247                     expected,
 248                     required_ty_param_count,
 249                     supplied_ty_param_count).as_slice());
 250     } else if supplied_ty_param_count > formal_ty_param_count {
 251         let expected = if required_ty_param_count < formal_ty_param_count {
 252             "expected at most"
 253         } else {
 254             "expected"
 255         };
 256         this.tcx().sess.span_fatal(path.span,
 257             format!("wrong number of type arguments: {} {}, found {}",
 258                     expected,
 259                     formal_ty_param_count,
 260                     supplied_ty_param_count).as_slice());
 261     }
 262
 263     if supplied_ty_param_count > required_ty_param_count
 264         && !this.tcx().sess.features.borrow().default_type_params {
 265         span_err!(this.tcx().sess, path.span, E0108,
 266             "default type parameters are experimental and possibly buggy");
 267         span_note!(this.tcx().sess, path.span,
 268             "add #![feature(default_type_params)] to the crate attributes to enable");
 269     }
 270
 271     let tps = path.segments
 272                   .iter()
 273                   .flat_map(|s| s.types.iter())
 274                   .map(|a_t| ast_ty_to_ty(this, rscope, &**a_t))
 275                   .collect();
 276
 277     let mut substs = Substs::new_type(tps, regions);
 278
 279     match self_ty {
 280         None => {
 281             // If no self-type is provided, it's still possible that
 282             // one was declared, because this could be an object type.
 283         }
 284         Some(ty) => {
 285             // If a self-type is provided, one should have been
 286             // "declared" (in other words, this should be a
 287             // trait-ref).
 288             assert!(decl_generics.types.get_self().is_some());
 289             substs.types.push(SelfSpace, ty);
 290         }
 291     }
 292
 293     for param in ty_param_defs.slice_from(supplied_ty_param_count).iter() {
 294         match param.default {
 295             Some(default) => {
 296                 // This is a default type parameter.
 297                 let default = default.subst_spanned(tcx,
 298                                                     &substs,
 299                                                     Some(path.span));
 300                 substs.types.push(TypeSpace, default);
 301             }
 302             None => {
 303                 // This is an associated type.
 304                 substs.types.push(
 305                     TypeSpace,
 306                     this.associated_type_binding(path.span,
 307                                                  associated_ty,
 308                                                  decl_def_id,
 309                                                  param.def_id))
 310             }
 311         }
 312     }
 313
 314     substs
 315 }
 316
 317 pub fn ast_path_to_trait_ref<'tcx,AC,RS>(this: &AC,
 318                                          rscope: &RS,
 319                                          trait_def_id: ast::DefId,
 320                                          self_ty: Option<ty::t>,
 321                                          associated_type: Option<ty::t>,
 322                                          path: &ast::Path)
 323                                          -> Rc<ty::TraitRef>
 324                                          where AC: AstConv<'tcx>,
 325                                                RS: RegionScope {
 326     let trait_def = this.get_trait_def(trait_def_id);
 327     Rc::new(ty::TraitRef {
 328         def_id: trait_def_id,
 329         substs: ast_path_substs(this,
 330                                 rscope,
 331                                 trait_def_id,
 332                                 &trait_def.generics,
 333                                 self_ty,
 334                                 associated_type,
 335                                 path)
 336     })
 337 }
 338
 339 pub fn ast_path_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 340     this: &AC,
 341     rscope: &RS,
 342     did: ast::DefId,
 343     path: &ast::Path)
 344     -> TypeAndSubsts {
 345     let tcx = this.tcx();
 346     let ty::Polytype {
 347         generics: generics,
 348         ty: decl_ty
 349     } = this.get_item_ty(did);
 350
 351     let substs = ast_path_substs(this,
 352                                  rscope,
 353                                  did,
 354                                  &generics,
 355                                  None,
 356                                  None,
 357                                  path);
 358     let ty = decl_ty.subst(tcx, &substs);
 359     TypeAndSubsts { substs: substs, ty: ty }
 360 }
 361
 362 /// Returns the type that this AST path refers to. If the path has no type
 363 /// parameters and the corresponding type has type parameters, fresh type
 364 /// and/or region variables are substituted.
 365 ///
 366 /// This is used when checking the constructor in struct literals.
 367 pub fn ast_path_to_ty_relaxed<'tcx, AC: AstConv<'tcx>,
 368                               RS:RegionScope>(
 369                               this: &AC,
 370                               rscope: &RS,
 371                               did: ast::DefId,
 372                               path: &ast::Path)
 373                               -> TypeAndSubsts {
 374     let tcx = this.tcx();
 375     let ty::Polytype {
 376         generics: generics,
 377         ty: decl_ty
 378     } = this.get_item_ty(did);
 379
 380     let substs = if (generics.has_type_params(TypeSpace) ||
 381         generics.has_region_params(TypeSpace)) &&
 382             path.segments.iter().all(|s| {
 383                 s.lifetimes.len() == 0 && s.types.len() == 0
 384             }) {
 385         let type_params = Vec::from_fn(generics.types.len(TypeSpace),
 386                                        |_| this.ty_infer(path.span));
 387         let region_params =
 388             rscope.anon_regions(path.span, generics.regions.len(TypeSpace))
 389                   .unwrap();
 390         Substs::new(VecPerParamSpace::params_from_type(type_params),
 391                     VecPerParamSpace::params_from_type(region_params))
 392     } else {
 393         ast_path_substs(this, rscope, did, &generics, None, None, path)
 394     };
 395
 396     let ty = decl_ty.subst(tcx, &substs);
 397     TypeAndSubsts {
 398         substs: substs,
 399         ty: ty,
 400     }
 401 }
 402
 403 pub static NO_REGIONS: uint = 1;
 404 pub static NO_TPS: uint = 2;
 405
 406 fn check_path_args(tcx: &ty::ctxt,
 407                    path: &ast::Path,
 408                    flags: uint) {
 409     if (flags & NO_TPS) != 0u {
 410         if !path.segments.iter().all(|s| s.types.is_empty()) {
 411             span_err!(tcx.sess, path.span, E0109,
 412                 "type parameters are not allowed on this type");
 413         }
 414     }
 415
 416     if (flags & NO_REGIONS) != 0u {
 417         if !path.segments.last().unwrap().lifetimes.is_empty() {
 418             span_err!(tcx.sess, path.span, E0110,
 419                 "region parameters are not allowed on this type");
 420         }
 421     }
 422 }
 423
 424 pub fn ast_ty_to_prim_ty(tcx: &ty::ctxt, ast_ty: &ast::Ty) -> Option<ty::t> {
 425     match ast_ty.node {
 426         ast::TyPath(ref path, _, id) => {
 427             let a_def = match tcx.def_map.borrow().find(&id) {
 428                 None => {
 429                     tcx.sess.span_bug(ast_ty.span,
 430                                       format!("unbound path {}",
 431                                               path.repr(tcx)).as_slice())
 432                 }
 433                 Some(&d) => d
 434             };
 435             match a_def {
 436                 def::DefPrimTy(nty) => {
 437                     match nty {
 438                         ast::TyBool => {
 439                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 440                             Some(ty::mk_bool())
 441                         }
 442                         ast::TyChar => {
 443                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 444                             Some(ty::mk_char())
 445                         }
 446                         ast::TyInt(it) => {
 447                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 448                             Some(ty::mk_mach_int(it))
 449                         }
 450                         ast::TyUint(uit) => {
 451                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 452                             Some(ty::mk_mach_uint(uit))
 453                         }
 454                         ast::TyFloat(ft) => {
 455                             check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 456                             Some(ty::mk_mach_float(ft))
 457                         }
 458                         ast::TyStr => {
 459                             Some(ty::mk_str(tcx))
 460                         }
 461                     }
 462                 }
 463                 _ => None
 464             }
 465         }
 466         _ => None
 467     }
 468 }
 469
 470 /// Converts the given AST type to a built-in type. A "built-in type" is, at
 471 /// present, either a core numeric type, a string, or `Box`.
 472 pub fn ast_ty_to_builtin_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 473         this: &AC,
 474         rscope: &RS,
 475         ast_ty: &ast::Ty)
 476         -> Option<ty::t> {
 477     match ast_ty_to_prim_ty(this.tcx(), ast_ty) {
 478         Some(typ) => return Some(typ),
 479         None => {}
 480     }
 481
 482     match ast_ty.node {
 483         ast::TyPath(ref path, _, id) => {
 484             let a_def = match this.tcx().def_map.borrow().find(&id) {
 485                 None => {
 486                     this.tcx()
 487                         .sess
 488                         .span_bug(ast_ty.span,
 489                                   format!("unbound path {}",
 490                                           path.repr(this.tcx())).as_slice())
 491                 }
 492                 Some(&d) => d
 493             };
 494
 495             // FIXME(#12938): This is a hack until we have full support for
 496             // DST.
 497             match a_def {
 498                 def::DefTy(did, _) | def::DefStruct(did)
 499                         if Some(did) == this.tcx().lang_items.owned_box() => {
 500                     if path.segments
 501                            .iter()
 502                            .flat_map(|s| s.types.iter())
 503                            .count() > 1 {
 504                         span_err!(this.tcx().sess, path.span, E0047,
 505                                   "`Box` has only one type parameter");
 506                     }
 507
 508                     for inner_ast_type in path.segments
 509                                               .iter()
 510                                               .flat_map(|s| s.types.iter()) {
 511                         return Some(mk_pointer(this,
 512                                                rscope,
 513                                                ast::MutImmutable,
 514                                                &**inner_ast_type,
 515                                                Uniq,
 516                                                |typ| ty::mk_uniq(this.tcx(), typ)));
 517                     }
 518                     span_err!(this.tcx().sess, path.span, E0113,
 519                               "not enough type parameters supplied to `Box<T>`");
 520                     Some(ty::mk_err())
 521                 }
 522                 def::DefTy(did, _) | def::DefStruct(did)
 523                         if Some(did) == this.tcx().lang_items.gc() => {
 524                     if path.segments
 525                            .iter()
 526                            .flat_map(|s| s.types.iter())
 527                            .count() > 1 {
 528                         span_err!(this.tcx().sess, path.span, E0048,
 529                                   "`Gc` has only one type parameter");
 530                     }
 531
 532                     for inner_ast_type in path.segments
 533                                               .iter()
 534                                               .flat_map(|s| s.types.iter()) {
 535                         return Some(mk_pointer(this,
 536                                                rscope,
 537                                                ast::MutImmutable,
 538                                                &**inner_ast_type,
 539                                                Box,
 540                                                |typ| {
 541                             match ty::get(typ).sty {
 542                                 ty::ty_str => {
 543                                     span_err!(this.tcx().sess, path.span, E0114,
 544                                               "`Gc<str>` is not a type");
 545                                     ty::mk_err()
 546                                 }
 547                                 ty::ty_vec(_, None) => {
 548                                     span_err!(this.tcx().sess, path.span, E0115,
 549                                               "`Gc<[T]>` is not a type");
 550                                     ty::mk_err()
 551                                 }
 552                                 _ => ty::mk_box(this.tcx(), typ),
 553                             }
 554                         }))
 555                     }
 556                     this.tcx().sess.span_bug(path.span,
 557                                              "not enough type parameters \
 558                                               supplied to `Gc<T>`")
 559                 }
 560                 _ => None
 561             }
 562         }
 563         _ => None
 564     }
 565 }
 566
 567 #[deriving(Show)]
 568 enum PointerTy {
 569     Box,
 570     RPtr(ty::Region),
 571     Uniq
 572 }
 573
 574 impl PointerTy {
 575     fn default_region(&self) -> ty::Region {
 576         match *self {
 577             Box => ty::ReStatic,
 578             Uniq => ty::ReStatic,
 579             RPtr(r) => r,
 580         }
 581     }
 582 }
 583
 584 pub fn trait_ref_for_unboxed_function<'tcx, AC: AstConv<'tcx>,
 585                                       RS:RegionScope>(
 586                                       this: &AC,
 587                                       rscope: &RS,
 588                                       unboxed_function: &ast::UnboxedFnTy,
 589                                       self_ty: Option<ty::t>)
 590                                       -> ty::TraitRef {
 591     let lang_item = match unboxed_function.kind {
 592         ast::FnUnboxedClosureKind => FnTraitLangItem,
 593         ast::FnMutUnboxedClosureKind => FnMutTraitLangItem,
 594         ast::FnOnceUnboxedClosureKind => FnOnceTraitLangItem,
 595     };
 596     let trait_did = this.tcx().lang_items.require(lang_item).unwrap();
 597     let input_types =
 598         unboxed_function.decl
 599                         .inputs
 600                         .iter()
 601                         .map(|input| {
 602                             ast_ty_to_ty(this, rscope, &*input.ty)
 603                         }).collect::<Vec<_>>();
 604     let input_tuple = if input_types.len() == 0 {
 605         ty::mk_nil()
 606     } else {
 607         ty::mk_tup(this.tcx(), input_types)
 608     };
 609     let output_type = ast_ty_to_ty(this,
 610                                    rscope,
 611                                    &*unboxed_function.decl.output);
 612     let mut substs = Substs::new_type(vec!(input_tuple, output_type),
 613                                              Vec::new());
 614
 615     match self_ty {
 616         Some(s) => substs.types.push(SelfSpace, s),
 617         None => ()
 618     }
 619
 620     ty::TraitRef {
 621         def_id: trait_did,
 622         substs: substs,
 623     }
 624 }
 625
 626 // Handle `~`, `Box`, and `&` being able to mean strs and vecs.
 627 // If a_seq_ty is a str or a vec, make it a str/vec.
 628 // Also handle first-class trait types.
 629 fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 630         this: &AC,
 631         rscope: &RS,
 632         a_seq_mutbl: ast::Mutability,
 633         a_seq_ty: &ast::Ty,
 634         ptr_ty: PointerTy,
 635         constr: |ty::t| -> ty::t)
 636         -> ty::t {
 637     let tcx = this.tcx();
 638     debug!("mk_pointer(ptr_ty={})", ptr_ty);
 639
 640     match a_seq_ty.node {
 641         ast::TyVec(ref ty) => {
 642             let ty = ast_ty_to_ty(this, rscope, &**ty);
 643             return constr(ty::mk_vec(tcx, ty, None));
 644         }
 645         ast::TyUnboxedFn(ref unboxed_function) => {
 646             let ty::TraitRef {
 647                 def_id,
 648                 substs
 649             } = trait_ref_for_unboxed_function(this,
 650                                                rscope,
 651                                                &**unboxed_function,
 652                                                None);
 653             let r = ptr_ty.default_region();
 654             let tr = ty::mk_trait(this.tcx(),
 655                                   def_id,
 656                                   substs,
 657                                   ty::region_existential_bound(r));
 658             match ptr_ty {
 659                 Uniq => {
 660                     return ty::mk_uniq(this.tcx(), tr);
 661                 }
 662                 RPtr(r) => {
 663                     return ty::mk_rptr(this.tcx(),
 664                                        r,
 665                                        ty::mt {mutbl: a_seq_mutbl, ty: tr});
 666                 }
 667                 _ => {
 668                     tcx.sess.span_err(
 669                         a_seq_ty.span,
 670                         "~trait or &trait are the only supported \
 671                          forms of casting-to-trait");
 672                     return ty::mk_err();
 673                 }
 674
 675             }
 676         }
 677         ast::TyPath(ref path, ref opt_bounds, id) => {
 678             // Note that the "bounds must be empty if path is not a trait"
 679             // restriction is enforced in the below case for ty_path, which
 680             // will run after this as long as the path isn't a trait.
 681             match tcx.def_map.borrow().find(&id) {
 682                 Some(&def::DefPrimTy(ast::TyStr)) => {
 683                     check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 684                     match ptr_ty {
 685                         Uniq => {
 686                             return constr(ty::mk_str(tcx));
 687                         }
 688                         RPtr(r) => {
 689                             return ty::mk_str_slice(tcx, r, ast::MutImmutable);
 690                         }
 691                         _ => {
 692                             tcx.sess
 693                                .span_err(path.span,
 694                                          "managed strings are not supported")
 695                         }
 696                     }
 697                 }
 698                 Some(&def::DefTrait(trait_def_id)) => {
 699                     let result = ast_path_to_trait_ref(this,
 700                                                        rscope,
 701                                                        trait_def_id,
 702                                                        None,
 703                                                        None,
 704                                                        path);
 705                     let bounds = match *opt_bounds {
 706                         None => {
 707                             conv_existential_bounds(this,
 708                                                     rscope,
 709                                                     path.span,
 710                                                     [result.clone()].as_slice(),
 711                                                     [].as_slice())
 712                         }
 713                         Some(ref bounds) => {
 714                             conv_existential_bounds(this,
 715                                                     rscope,
 716                                                     path.span,
 717                                                     [result.clone()].as_slice(),
 718                                                     bounds.as_slice())
 719                         }
 720                     };
 721                     let tr = ty::mk_trait(tcx,
 722                                           result.def_id,
 723                                           result.substs.clone(),
 724                                           bounds);
 725                     return match ptr_ty {
 726                         Uniq => {
 727                             return ty::mk_uniq(tcx, tr);
 728                         }
 729                         RPtr(r) => {
 730                             return ty::mk_rptr(tcx, r, ty::mt{mutbl: a_seq_mutbl, ty: tr});
 731                         }
 732                         _ => {
 733                             tcx.sess.span_err(
 734                                 path.span,
 735                                 "~trait or &trait are the only supported \
 736                                  forms of casting-to-trait");
 737                             return ty::mk_err();
 738                         }
 739                     };
 740                 }
 741                 _ => {}
 742             }
 743         }
 744         _ => {}
 745     }
 746
 747     constr(ast_ty_to_ty(this, rscope, a_seq_ty))
 748 }
 749
 750 fn associated_ty_to_ty<'tcx,AC,RS>(this: &AC,
 751                                    rscope: &RS,
 752                                    trait_path: &ast::Path,
 753                                    for_ast_type: &ast::Ty,
 754                                    trait_type_id: ast::DefId,
 755                                    span: Span)
 756                                    -> ty::t
 757                                    where AC: AstConv<'tcx>, RS: RegionScope {
 758     // Find the trait that this associated type belongs to.
 759     let trait_did = match ty::impl_or_trait_item(this.tcx(),
 760                                                  trait_type_id).container() {
 761         ty::ImplContainer(_) => {
 762             this.tcx().sess.span_bug(span,
 763                                      "associated_ty_to_ty(): impl associated \
 764                                       types shouldn't go through this \
 765                                       function")
 766         }
 767         ty::TraitContainer(trait_id) => trait_id,
 768     };
 769
 770     let for_type = ast_ty_to_ty(this, rscope, for_ast_type);
 771     if !this.associated_types_of_trait_are_valid(for_type, trait_did) {
 772         this.tcx().sess.span_err(span,
 773                                  "this associated type is not \
 774                                   allowed in this context");
 775         return ty::mk_err()
 776     }
 777
 778     let trait_ref = ast_path_to_trait_ref(this,
 779                                           rscope,
 780                                           trait_did,
 781                                           None,
 782                                           Some(for_type),
 783                                           trait_path);
 784     let trait_def = this.get_trait_def(trait_did);
 785     for type_parameter in trait_def.generics.types.iter() {
 786         if type_parameter.def_id == trait_type_id {
 787             return *trait_ref.substs.types.get(type_parameter.space,
 788                                                type_parameter.index)
 789         }
 790     }
 791     this.tcx().sess.span_bug(span,
 792                              "this associated type didn't get added \
 793                               as a parameter for some reason")
 794 }
 795
 796 // Parses the programmer's textual representation of a type into our
 797 // internal notion of a type.
 798 pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 799         this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> ty::t {
 800
 801     let tcx = this.tcx();
 802
 803     let mut ast_ty_to_ty_cache = tcx.ast_ty_to_ty_cache.borrow_mut();
 804     match ast_ty_to_ty_cache.find(&ast_ty.id) {
 805         Some(&ty::atttce_resolved(ty)) => return ty,
 806         Some(&ty::atttce_unresolved) => {
 807             tcx.sess.span_fatal(ast_ty.span,
 808                                 "illegal recursive type; insert an enum \
 809                                  or struct in the cycle, if this is \
 810                                  desired");
 811         }
 812         None => { /* go on */ }
 813     }
 814     ast_ty_to_ty_cache.insert(ast_ty.id, ty::atttce_unresolved);
 815     drop(ast_ty_to_ty_cache);
 816
 817     let typ = ast_ty_to_builtin_ty(this, rscope, ast_ty).unwrap_or_else(|| {
 818         match ast_ty.node {
 819             ast::TyNil => ty::mk_nil(),
 820             ast::TyBot => ty::mk_bot(),
 821             ast::TyBox(ref ty) => {
 822                 mk_pointer(this, rscope, ast::MutImmutable, &**ty, Box,
 823                            |ty| ty::mk_box(tcx, ty))
 824             }
 825             ast::TyUniq(ref ty) => {
 826                 mk_pointer(this, rscope, ast::MutImmutable, &**ty, Uniq,
 827                            |ty| ty::mk_uniq(tcx, ty))
 828             }
 829             ast::TyVec(ref ty) => {
 830                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty), None)
 831             }
 832             ast::TyPtr(ref mt) => {
 833                 ty::mk_ptr(tcx, ty::mt {
 834                     ty: ast_ty_to_ty(this, rscope, &*mt.ty),
 835                     mutbl: mt.mutbl
 836                 })
 837             }
 838             ast::TyRptr(ref region, ref mt) => {
 839                 let r = opt_ast_region_to_region(this, rscope, ast_ty.span, region);
 840                 debug!("ty_rptr r={}", r.repr(this.tcx()));
 841                 mk_pointer(this, rscope, mt.mutbl, &*mt.ty, RPtr(r),
 842                            |ty| ty::mk_rptr(tcx, r, ty::mt {ty: ty, mutbl: mt.mutbl}))
 843             }
 844             ast::TyTup(ref fields) => {
 845                 let flds = fields.iter()
 846                                  .map(|t| ast_ty_to_ty(this, rscope, &**t))
 847                                  .collect();
 848                 ty::mk_tup(tcx, flds)
 849             }
 850             ast::TyParen(ref typ) => ast_ty_to_ty(this, rscope, &**typ),
 851             ast::TyBareFn(ref bf) => {
 852                 if bf.decl.variadic && bf.abi != abi::C {
 853                     tcx.sess.span_err(ast_ty.span,
 854                                       "variadic function must have C calling convention");
 855                 }
 856                 ty::mk_bare_fn(tcx, ty_of_bare_fn(this, ast_ty.id, bf.fn_style,
 857                                                   bf.abi, &*bf.decl))
 858             }
 859             ast::TyClosure(ref f) => {
 860                 // Use corresponding trait store to figure out default bounds
 861                 // if none were specified.
 862                 let bounds = conv_existential_bounds(this,
 863                                                      rscope,
 864                                                      ast_ty.span,
 865                                                      [].as_slice(),
 866                                                      f.bounds.as_slice());
 867                 let fn_decl = ty_of_closure(this,
 868                                             ast_ty.id,
 869                                             f.fn_style,
 870                                             f.onceness,
 871                                             bounds,
 872                                             ty::RegionTraitStore(
 873                                                 bounds.region_bound,
 874                                                 ast::MutMutable),
 875                                             &*f.decl,
 876                                             abi::Rust,
 877                                             None);
 878                 ty::mk_closure(tcx, fn_decl)
 879             }
 880             ast::TyProc(ref f) => {
 881                 // Use corresponding trait store to figure out default bounds
 882                 // if none were specified.
 883                 let bounds = conv_existential_bounds(this, rscope,
 884                                                      ast_ty.span,
 885                                                      [].as_slice(),
 886                                                      f.bounds.as_slice());
 887
 888                 let fn_decl = ty_of_closure(this,
 889                                             ast_ty.id,
 890                                             f.fn_style,
 891                                             f.onceness,
 892                                             bounds,
 893                                             ty::UniqTraitStore,
 894                                             &*f.decl,
 895                                             abi::Rust,
 896                                             None);
 897
 898                 ty::mk_closure(tcx, fn_decl)
 899             }
 900             ast::TyUnboxedFn(..) => {
 901                 tcx.sess.span_err(ast_ty.span,
 902                                   "cannot use unboxed functions here");
 903                 ty::mk_err()
 904             }
 905             ast::TyPath(ref path, ref bounds, id) => {
 906                 let a_def = match tcx.def_map.borrow().find(&id) {
 907                     None => {
 908                         tcx.sess
 909                            .span_bug(ast_ty.span,
 910                                      format!("unbound path {}",
 911                                              path.repr(tcx)).as_slice())
 912                     }
 913                     Some(&d) => d
 914                 };
 915                 // Kind bounds on path types are only supported for traits.
 916                 match a_def {
 917                     // But don't emit the error if the user meant to do a trait anyway.
 918                     def::DefTrait(..) => { },
 919                     _ if bounds.is_some() =>
 920                         tcx.sess.span_err(ast_ty.span,
 921                                           "kind bounds can only be used on trait types"),
 922                     _ => { },
 923                 }
 924                 match a_def {
 925                     def::DefTrait(trait_def_id) => {
 926                         let result = ast_path_to_trait_ref(this,
 927                                                            rscope,
 928                                                            trait_def_id,
 929                                                            None,
 930                                                            None,
 931                                                            path);
 932                         let empty_bounds: &[ast::TyParamBound] = &[];
 933                         let ast_bounds = match *bounds {
 934                             Some(ref b) => b.as_slice(),
 935                             None => empty_bounds
 936                         };
 937                         let bounds = conv_existential_bounds(this,
 938                                                              rscope,
 939                                                              ast_ty.span,
 940                                                              &[result.clone()],
 941                                                              ast_bounds);
 942                         ty::mk_trait(tcx,
 943                                      result.def_id,
 944                                      result.substs.clone(),
 945                                      bounds)
 946                     }
 947                     def::DefTy(did, _) | def::DefStruct(did) => {
 948                         ast_path_to_ty(this, rscope, did, path).ty
 949                     }
 950                     def::DefTyParam(space, id, n) => {
 951                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 952                         ty::mk_param(tcx, space, n, id)
 953                     }
 954                     def::DefSelfTy(id) => {
 955                         // n.b.: resolve guarantees that the this type only appears in a
 956                         // trait, which we rely upon in various places when creating
 957                         // substs
 958                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 959                         let did = ast_util::local_def(id);
 960                         ty::mk_self_type(tcx, did)
 961                     }
 962                     def::DefMod(id) => {
 963                         tcx.sess.span_fatal(ast_ty.span,
 964                             format!("found module name used as a type: {}",
 965                                     tcx.map.node_to_string(id.node)).as_slice());
 966                     }
 967                     def::DefPrimTy(_) => {
 968                         fail!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
 969                     }
 970                     def::DefAssociatedTy(trait_type_id) => {
 971                         let path_str = tcx.map.path_to_string(
 972                             tcx.map.get_parent(trait_type_id.node));
 973                         tcx.sess.span_err(ast_ty.span,
 974                                           format!("ambiguous associated \
 975                                                    type; specify the type \
 976                                                    using the syntax `<Type \
 977                                                    as {}>::{}`",
 978                                                   path_str,
 979                                                   token::get_ident(
 980                                                       path.segments
 981                                                           .last()
 982                                                           .unwrap()
 983                                                           .identifier)
 984                                                   .get()).as_slice());
 985                         ty::mk_err()
 986                     }
 987                     _ => {
 988                         tcx.sess.span_fatal(ast_ty.span,
 989                                             format!("found value name used \
 990                                                      as a type: {:?}",
 991                                                     a_def).as_slice());
 992                     }
 993                 }
 994             }
 995             ast::TyQPath(ref qpath) => {
 996                 match tcx.def_map.borrow().find(&ast_ty.id) {
 997                     None => {
 998                         tcx.sess.span_bug(ast_ty.span,
 999                                           "unbound qualified path")
1000                     }
1001                     Some(&def::DefAssociatedTy(trait_type_id)) => {
1002                         associated_ty_to_ty(this,
1003                                             rscope,
1004                                             &qpath.trait_name,
1005                                             &*qpath.for_type,
1006                                             trait_type_id,
1007                                             ast_ty.span)
1008                     }
1009                     Some(_) => {
1010                         tcx.sess.span_err(ast_ty.span,
1011                                           "this qualified path does not name \
1012                                            an associated type");
1013                         ty::mk_err()
1014                     }
1015                 }
1016             }
1017             ast::TyFixedLengthVec(ref ty, ref e) => {
1018                 match const_eval::eval_const_expr_partial(tcx, &**e) {
1019                     Ok(ref r) => {
1020                         match *r {
1021                             const_eval::const_int(i) =>
1022                                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1023                                            Some(i as uint)),
1024                             const_eval::const_uint(i) =>
1025                                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1026                                            Some(i as uint)),
1027                             _ => {
1028                                 tcx.sess.span_fatal(
1029                                     ast_ty.span, "expected constant expr for vector length");
1030                             }
1031                         }
1032                     }
1033                     Err(ref r) => {
1034                         tcx.sess.span_fatal(
1035                             ast_ty.span,
1036                             format!("expected constant expr for vector \
1037                                      length: {}",
1038                                     *r).as_slice());
1039                     }
1040                 }
1041             }
1042             ast::TyTypeof(ref _e) => {
1043                 tcx.sess.span_bug(ast_ty.span, "typeof is reserved but unimplemented");
1044             }
1045             ast::TyInfer => {
1046                 // TyInfer also appears as the type of arguments or return
1047                 // values in a ExprFnBlock, ExprProc, or ExprUnboxedFn, or as
1048                 // the type of local variables. Both of these cases are
1049                 // handled specially and will not descend into this routine.
1050                 this.ty_infer(ast_ty.span)
1051             }
1052         }
1053     });
1054
1055     tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, ty::atttce_resolved(typ));
1056     return typ;
1057 }
1058
1059 pub fn ty_of_arg<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(this: &AC, rscope: &RS,
1060                                                            a: &ast::Arg,
1061                                                            expected_ty: Option<ty::t>)
1062                                                            -> ty::t {
1063     match a.ty.node {
1064         ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
1065         ast::TyInfer => this.ty_infer(a.ty.span),
1066         _ => ast_ty_to_ty(this, rscope, &*a.ty),
1067     }
1068 }
1069
1070 struct SelfInfo<'a> {
1071     untransformed_self_ty: ty::t,
1072     explicit_self: &'a ast::ExplicitSelf,
1073 }
1074
1075 pub fn ty_of_method<'tcx, AC: AstConv<'tcx>>(
1076                     this: &AC,
1077                     id: ast::NodeId,
1078                     fn_style: ast::FnStyle,
1079                     untransformed_self_ty: ty::t,
1080                     explicit_self: &ast::ExplicitSelf,
1081                     decl: &ast::FnDecl,
1082                     abi: abi::Abi)
1083                     -> (ty::BareFnTy, ty::ExplicitSelfCategory) {
1084     let self_info = Some(SelfInfo {
1085         untransformed_self_ty: untransformed_self_ty,
1086         explicit_self: explicit_self,
1087     });
1088     let (bare_fn_ty, optional_explicit_self_category) =
1089         ty_of_method_or_bare_fn(this,
1090                                 id,
1091                                 fn_style,
1092                                 abi,
1093                                 self_info,
1094                                 decl);
1095     (bare_fn_ty, optional_explicit_self_category.unwrap())
1096 }
1097
1098 pub fn ty_of_bare_fn<'tcx, AC: AstConv<'tcx>>(this: &AC, id: ast::NodeId,
1099                                               fn_style: ast::FnStyle, abi: abi::Abi,
1100                                               decl: &ast::FnDecl) -> ty::BareFnTy {
1101     let (bare_fn_ty, _) =
1102         ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl);
1103     bare_fn_ty
1104 }
1105
1106 fn ty_of_method_or_bare_fn<'tcx, AC: AstConv<'tcx>>(
1107                            this: &AC,
1108                            id: ast::NodeId,
1109                            fn_style: ast::FnStyle,
1110                            abi: abi::Abi,
1111                            opt_self_info: Option<SelfInfo>,
1112                            decl: &ast::FnDecl)
1113                            -> (ty::BareFnTy,
1114                                Option<ty::ExplicitSelfCategory>) {
1115     debug!("ty_of_method_or_bare_fn");
1116
1117     // New region names that appear inside of the arguments of the function
1118     // declaration are bound to that function type.
1119     let rb = rscope::BindingRscope::new(id);
1120
1121     // `implied_output_region` is the region that will be assumed for any
1122     // region parameters in the return type. In accordance with the rules for
1123     // lifetime elision, we can determine it in two ways. First (determined
1124     // here), if self is by-reference, then the implied output region is the
1125     // region of the self parameter.
1126     let mut explicit_self_category_result = None;
1127     let (self_ty, mut implied_output_region) = match opt_self_info {
1128         None => (None, None),
1129         Some(self_info) => {
1130             // Figure out and record the explicit self category.
1131             let explicit_self_category =
1132                 determine_explicit_self_category(this, &rb, &self_info);
1133             explicit_self_category_result = Some(explicit_self_category);
1134             match explicit_self_category {
1135                 ty::StaticExplicitSelfCategory => (None, None),
1136                 ty::ByValueExplicitSelfCategory => {
1137                     (Some(self_info.untransformed_self_ty), None)
1138                 }
1139                 ty::ByReferenceExplicitSelfCategory(region, mutability) => {
1140                     (Some(ty::mk_rptr(this.tcx(),
1141                                       region,
1142                                       ty::mt {
1143                                         ty: self_info.untransformed_self_ty,
1144                                         mutbl: mutability
1145                                       })),
1146                      Some(region))
1147                 }
1148                 ty::ByBoxExplicitSelfCategory => {
1149                     (Some(ty::mk_uniq(this.tcx(),
1150                                       self_info.untransformed_self_ty)),
1151                      None)
1152                 }
1153             }
1154         }
1155     };
1156
1157     // HACK(eddyb) replace the fake self type in the AST with the actual type.
1158     let input_tys = if self_ty.is_some() {
1159         decl.inputs.slice_from(1)
1160     } else {
1161         decl.inputs.as_slice()
1162     };
1163     let input_tys = input_tys.iter().map(|a| ty_of_arg(this, &rb, a, None));
1164     let self_and_input_tys: Vec<_> =
1165         self_ty.into_iter().chain(input_tys).collect();
1166
1167     // Second, if there was exactly one lifetime (either a substitution or a
1168     // reference) in the arguments, then any anonymous regions in the output
1169     // have that lifetime.
1170     if implied_output_region.is_none() {
1171         let mut self_and_input_tys_iter = self_and_input_tys.iter();
1172         if self_ty.is_some() {
1173             // Skip the first argument if `self` is present.
1174             drop(self_and_input_tys_iter.next())
1175         }
1176
1177         let mut accumulator = Vec::new();
1178         for input_type in self_and_input_tys_iter {
1179             ty::accumulate_lifetimes_in_type(&mut accumulator, *input_type)
1180         }
1181         if accumulator.len() == 1 {
1182             implied_output_region = Some(*accumulator.get(0));
1183         }
1184     }
1185
1186     let output_ty = match decl.output.node {
1187         ast::TyInfer => this.ty_infer(decl.output.span),
1188         _ => {
1189             match implied_output_region {
1190                 Some(implied_output_region) => {
1191                     let rb = SpecificRscope::new(implied_output_region);
1192                     ast_ty_to_ty(this, &rb, &*decl.output)
1193                 }
1194                 None => {
1195                     // All regions must be explicitly specified in the output
1196                     // if the lifetime elision rules do not apply. This saves
1197                     // the user from potentially-confusing errors.
1198                     let rb = ExplicitRscope;
1199                     ast_ty_to_ty(this, &rb, &*decl.output)
1200                 }
1201             }
1202         }
1203     };
1204
1205     (ty::BareFnTy {
1206         fn_style: fn_style,
1207         abi: abi,
1208         sig: ty::FnSig {
1209             binder_id: id,
1210             inputs: self_and_input_tys,
1211             output: output_ty,
1212             variadic: decl.variadic
1213         }
1214     }, explicit_self_category_result)
1215 }
1216
1217 fn determine_explicit_self_category<'tcx, AC: AstConv<'tcx>,
1218                                     RS:RegionScope>(
1219                                     this: &AC,
1220                                     rscope: &RS,
1221                                     self_info: &SelfInfo)
1222                                     -> ty::ExplicitSelfCategory {
1223     match self_info.explicit_self.node {
1224         ast::SelfStatic => ty::StaticExplicitSelfCategory,
1225         ast::SelfValue(_) => ty::ByValueExplicitSelfCategory,
1226         ast::SelfRegion(ref lifetime, mutability, _) => {
1227             let region =
1228                 opt_ast_region_to_region(this,
1229                                          rscope,
1230                                          self_info.explicit_self.span,
1231                                          lifetime);
1232             ty::ByReferenceExplicitSelfCategory(region, mutability)
1233         }
1234         ast::SelfExplicit(ref ast_type, _) => {
1235             let explicit_type = ast_ty_to_ty(this, rscope, &**ast_type);
1236
1237             {
1238                 let inference_context = infer::new_infer_ctxt(this.tcx());
1239                 let expected_self = self_info.untransformed_self_ty;
1240                 let actual_self = explicit_type;
1241                 let result = infer::mk_eqty(
1242                     &inference_context,
1243                     false,
1244                     infer::Misc(self_info.explicit_self.span),
1245                     expected_self,
1246                     actual_self);
1247                 match result {
1248                     Ok(_) => {
1249                         inference_context.resolve_regions_and_report_errors();
1250                         return ty::ByValueExplicitSelfCategory
1251                     }
1252                     Err(_) => {}
1253                 }
1254             }
1255
1256             match ty::get(explicit_type).sty {
1257                 ty::ty_rptr(region, tm) => {
1258                     typeck::require_same_types(
1259                         this.tcx(),
1260                         None,
1261                         false,
1262                         self_info.explicit_self.span,
1263                         self_info.untransformed_self_ty,
1264                         tm.ty,
1265                         || "not a valid type for `self`".to_owned());
1266                     return ty::ByReferenceExplicitSelfCategory(region,
1267                                                                tm.mutbl)
1268                 }
1269                 ty::ty_uniq(typ) => {
1270                     typeck::require_same_types(
1271                         this.tcx(),
1272                         None,
1273                         false,
1274                         self_info.explicit_self.span,
1275                         self_info.untransformed_self_ty,
1276                         typ,
1277                         || "not a valid type for `self`".to_owned());
1278                     return ty::ByBoxExplicitSelfCategory
1279                 }
1280                 _ => {
1281                     this.tcx()
1282                         .sess
1283                         .span_err(self_info.explicit_self.span,
1284                                   "not a valid type for `self`");
1285                     return ty::ByValueExplicitSelfCategory
1286                 }
1287             }
1288         }
1289     }
1290 }
1291
1292 pub fn ty_of_closure<'tcx, AC: AstConv<'tcx>>(
1293     this: &AC,
1294     id: ast::NodeId,
1295     fn_style: ast::FnStyle,
1296     onceness: ast::Onceness,
1297     bounds: ty::ExistentialBounds,
1298     store: ty::TraitStore,
1299     decl: &ast::FnDecl,
1300     abi: abi::Abi,
1301     expected_sig: Option<ty::FnSig>)
1302     -> ty::ClosureTy
1303 {
1304     debug!("ty_of_fn_decl");
1305
1306     // new region names that appear inside of the fn decl are bound to
1307     // that function type
1308     let rb = rscope::BindingRscope::new(id);
1309
1310     let input_tys = decl.inputs.iter().enumerate().map(|(i, a)| {
1311         let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1312             // no guarantee that the correct number of expected args
1313             // were supplied
1314             if i < e.inputs.len() {
1315                 Some(*e.inputs.get(i))
1316             } else {
1317                 None
1318             }
1319         });
1320         ty_of_arg(this, &rb, a, expected_arg_ty)
1321     }).collect();
1322
1323     let expected_ret_ty = expected_sig.map(|e| e.output);
1324     let output_ty = match decl.output.node {
1325         ast::TyInfer if expected_ret_ty.is_some() => expected_ret_ty.unwrap(),
1326         ast::TyInfer => this.ty_infer(decl.output.span),
1327         _ => ast_ty_to_ty(this, &rb, &*decl.output)
1328     };
1329
1330     ty::ClosureTy {
1331         fn_style: fn_style,
1332         onceness: onceness,
1333         store: store,
1334         bounds: bounds,
1335         abi: abi,
1336         sig: ty::FnSig {binder_id: id,
1337                         inputs: input_tys,
1338                         output: output_ty,
1339                         variadic: decl.variadic}
1340     }
1341 }
1342
1343 pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1344     this: &AC,
1345     rscope: &RS,
1346     span: Span,
1347     main_trait_refs: &[Rc<ty::TraitRef>],
1348     ast_bounds: &[ast::TyParamBound])
1349     -> ty::ExistentialBounds
1350 {
1351     /*!
1352      * Given an existential type like `Foo+'a+Bar`, this routine
1353      * converts the `'a` and `Bar` intos an `ExistentialBounds`
1354      * struct. The `main_trait_refs` argument specifies the `Foo` --
1355      * it is absent for closures. Eventually this should all be
1356      * normalized, I think, so that there is no "main trait ref" and
1357      * instead we just have a flat list of bounds as the existential
1358      * type.
1359      */
1360
1361     let ast_bound_refs: Vec<&ast::TyParamBound> =
1362         ast_bounds.iter().collect();
1363
1364     let PartitionedBounds { builtin_bounds,
1365                             trait_bounds,
1366                             region_bounds,
1367                             unboxed_fn_ty_bounds } =
1368         partition_bounds(this.tcx(), span, ast_bound_refs.as_slice());
1369
1370     if !trait_bounds.is_empty() {
1371         let b = trait_bounds.get(0);
1372         this.tcx().sess.span_err(
1373             b.path.span,
1374             format!("only the builtin traits can be used \
1375                      as closure or object bounds").as_slice());
1376     }
1377
1378     if !unboxed_fn_ty_bounds.is_empty() {
1379         this.tcx().sess.span_err(
1380             span,
1381             format!("only the builtin traits can be used \
1382                      as closure or object bounds").as_slice());
1383     }
1384
1385     // The "main trait refs", rather annoyingly, have no type
1386     // specified for the `Self` parameter of the trait. The reason for
1387     // this is that they are, after all, *existential* types, and
1388     // hence that type is unknown. However, leaving this type missing
1389     // causes the substitution code to go all awry when walking the
1390     // bounds, so here we clone those trait refs and insert ty::err as
1391     // the self type. Perhaps we should do this more generally, it'd
1392     // be convenient (or perhaps something else, i.e., ty::erased).
1393     let main_trait_refs: Vec<Rc<ty::TraitRef>> =
1394         main_trait_refs.iter()
1395         .map(|t|
1396              Rc::new(ty::TraitRef {
1397                  def_id: t.def_id,
1398                  substs: t.substs.with_self_ty(ty::mk_err()) }))
1399         .collect();
1400
1401     let region_bound = compute_region_bound(this,
1402                                             rscope,
1403                                             span,
1404                                             builtin_bounds,
1405                                             region_bounds.as_slice(),
1406                                             main_trait_refs.as_slice());
1407
1408     ty::ExistentialBounds {
1409         region_bound: region_bound,
1410         builtin_bounds: builtin_bounds,
1411     }
1412 }
1413
1414 pub fn compute_opt_region_bound(tcx: &ty::ctxt,
1415                                 span: Span,
1416                                 builtin_bounds: ty::BuiltinBounds,
1417                                 region_bounds: &[&ast::Lifetime],
1418                                 trait_bounds: &[Rc<ty::TraitRef>])
1419                                 -> Option<ty::Region>
1420 {
1421     /*!
1422      * Given the bounds on a type parameter / existential type,
1423      * determines what single region bound (if any) we can use to
1424      * summarize this type. The basic idea is that we will use the
1425      * bound the user provided, if they provided one, and otherwise
1426      * search the supertypes of trait bounds for region bounds. It may
1427      * be that we can derive no bound at all, in which case we return
1428      * `None`.
1429      */
1430
1431     if region_bounds.len() > 1 {
1432         tcx.sess.span_err(
1433             region_bounds[1].span,
1434             format!("only a single explicit lifetime bound is permitted").as_slice());
1435     }
1436
1437     if region_bounds.len() != 0 {
1438         // Explicitly specified region bound. Use that.
1439         let r = region_bounds[0];
1440         return Some(ast_region_to_region(tcx, r));
1441     }
1442
1443     // No explicit region bound specified. Therefore, examine trait
1444     // bounds and see if we can derive region bounds from those.
1445     let derived_region_bounds =
1446         ty::required_region_bounds(
1447             tcx,
1448             [],
1449             builtin_bounds,
1450             trait_bounds);
1451
1452     // If there are no derived region bounds, then report back that we
1453     // can find no region bound.
1454     if derived_region_bounds.len() == 0 {
1455         return None;
1456     }
1457
1458     // If any of the derived region bounds are 'static, that is always
1459     // the best choice.
1460     if derived_region_bounds.iter().any(|r| ty::ReStatic == *r) {
1461         return Some(ty::ReStatic);
1462     }
1463
1464     // Determine whether there is exactly one unique region in the set
1465     // of derived region bounds. If so, use that. Otherwise, report an
1466     // error.
1467     let r = *derived_region_bounds.get(0);
1468     if derived_region_bounds.slice_from(1).iter().any(|r1| r != *r1) {
1469         tcx.sess.span_err(
1470             span,
1471             format!("ambiguous lifetime bound, \
1472                      explicit lifetime bound required").as_slice());
1473     }
1474     return Some(r);
1475 }
1476
1477 fn compute_region_bound<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1478     this: &AC,
1479     rscope: &RS,
1480     span: Span,
1481     builtin_bounds: ty::BuiltinBounds,
1482     region_bounds: &[&ast::Lifetime],
1483     trait_bounds: &[Rc<ty::TraitRef>])
1484     -> ty::Region
1485 {
1486     /*!
1487      * A version of `compute_opt_region_bound` for use where some
1488      * region bound is required (existential types,
1489      * basically). Reports an error if no region bound can be derived
1490      * and we are in an `rscope` that does not provide a default.
1491      */
1492
1493     match compute_opt_region_bound(this.tcx(), span, builtin_bounds,
1494                                    region_bounds, trait_bounds) {
1495         Some(r) => r,
1496         None => {
1497             match rscope.default_region_bound(span) {
1498                 Some(r) => { r }
1499                 None => {
1500                     this.tcx().sess.span_err(
1501                         span,
1502                         format!("explicit lifetime bound required").as_slice());
1503                     ty::ReStatic
1504                 }
1505             }
1506         }
1507     }
1508 }
1509
1510 pub struct PartitionedBounds<'a> {
1511     pub builtin_bounds: ty::BuiltinBounds,
1512     pub trait_bounds: Vec<&'a ast::TraitRef>,
1513     pub unboxed_fn_ty_bounds: Vec<&'a ast::UnboxedFnTy>,
1514     pub region_bounds: Vec<&'a ast::Lifetime>,
1515 }
1516
1517 pub fn partition_bounds<'a>(tcx: &ty::ctxt,
1518                             _span: Span,
1519                             ast_bounds: &'a [&ast::TyParamBound])
1520                             -> PartitionedBounds<'a>
1521 {
1522     /*!
1523      * Divides a list of bounds from the AST into three groups:
1524      * builtin bounds (Copy, Sized etc), general trait bounds,
1525      * and region bounds.
1526      */
1527
1528     let mut builtin_bounds = ty::empty_builtin_bounds();
1529     let mut region_bounds = Vec::new();
1530     let mut trait_bounds = Vec::new();
1531     let mut unboxed_fn_ty_bounds = Vec::new();
1532     let mut trait_def_ids = HashMap::new();
1533     for &ast_bound in ast_bounds.iter() {
1534         match *ast_bound {
1535             ast::TraitTyParamBound(ref b) => {
1536                 match lookup_def_tcx(tcx, b.path.span, b.ref_id) {
1537                     def::DefTrait(trait_did) => {
1538                         match trait_def_ids.find(&trait_did) {
1539                             // Already seen this trait. We forbid
1540                             // duplicates in the list (for some
1541                             // reason).
1542                             Some(span) => {
1543                                 span_err!(
1544                                     tcx.sess, b.path.span, E0127,
1545                                     "trait `{}` already appears in the \
1546                                      list of bounds",
1547                                     b.path.user_string(tcx));
1548                                 tcx.sess.span_note(
1549                                     *span,
1550                                     "previous appearance is here");
1551
1552                                 continue;
1553                             }
1554
1555                             None => { }
1556                         }
1557
1558                         trait_def_ids.insert(trait_did, b.path.span);
1559
1560                         if ty::try_add_builtin_trait(tcx,
1561                                                      trait_did,
1562                                                      &mut builtin_bounds) {
1563                             continue; // success
1564                         }
1565                     }
1566                     _ => {
1567                         // Not a trait? that's an error, but it'll get
1568                         // reported later.
1569                     }
1570                 }
1571                 trait_bounds.push(b);
1572             }
1573             ast::RegionTyParamBound(ref l) => {
1574                 region_bounds.push(l);
1575             }
1576             ast::UnboxedFnTyParamBound(ref unboxed_function) => {
1577                 unboxed_fn_ty_bounds.push(unboxed_function);
1578             }
1579         }
1580     }
1581
1582     PartitionedBounds {
1583         builtin_bounds: builtin_bounds,
1584         trait_bounds: trait_bounds,
1585         region_bounds: region_bounds,
1586         unboxed_fn_ty_bounds: unboxed_fn_ty_bounds
1587     }
1588 }
1589