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                                       kind: ast::UnboxedClosureKind,
 589                                       decl: &ast::FnDecl,
 590                                       self_ty: Option<ty::t>)
 591                                       -> ty::TraitRef {
 592     let lang_item = match kind {
 593         ast::FnUnboxedClosureKind => FnTraitLangItem,
 594         ast::FnMutUnboxedClosureKind => FnMutTraitLangItem,
 595         ast::FnOnceUnboxedClosureKind => FnOnceTraitLangItem,
 596     };
 597     let trait_did = this.tcx().lang_items.require(lang_item).unwrap();
 598     let input_types = decl.inputs
 599                           .iter()
 600                           .map(|input| {
 601                             ast_ty_to_ty(this, rscope, &*input.ty)
 602                           }).collect::<Vec<_>>();
 603     let input_tuple = if input_types.len() == 0 {
 604         ty::mk_nil()
 605     } else {
 606         ty::mk_tup(this.tcx(), input_types)
 607     };
 608     let output_type = ast_ty_to_ty(this, rscope, &*decl.output);
 609     let mut substs = Substs::new_type(vec!(input_tuple, output_type),
 610                                       Vec::new());
 611
 612     match self_ty {
 613         Some(s) => substs.types.push(SelfSpace, s),
 614         None => ()
 615     }
 616
 617     ty::TraitRef {
 618         def_id: trait_did,
 619         substs: substs,
 620     }
 621 }
 622
 623 // Handle `~`, `Box`, and `&` being able to mean strs and vecs.
 624 // If a_seq_ty is a str or a vec, make it a str/vec.
 625 // Also handle first-class trait types.
 626 fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 627         this: &AC,
 628         rscope: &RS,
 629         a_seq_mutbl: ast::Mutability,
 630         a_seq_ty: &ast::Ty,
 631         ptr_ty: PointerTy,
 632         constr: |ty::t| -> ty::t)
 633         -> ty::t {
 634     let tcx = this.tcx();
 635     debug!("mk_pointer(ptr_ty={})", ptr_ty);
 636
 637     match a_seq_ty.node {
 638         ast::TyVec(ref ty) => {
 639             let ty = ast_ty_to_ty(this, rscope, &**ty);
 640             return constr(ty::mk_vec(tcx, ty, None));
 641         }
 642         ast::TyUnboxedFn(ref unboxed_function) => {
 643             let ty::TraitRef {
 644                 def_id,
 645                 substs
 646             } = trait_ref_for_unboxed_function(this,
 647                                                rscope,
 648                                                unboxed_function.kind,
 649                                                &*unboxed_function.decl,
 650                                                None);
 651             let r = ptr_ty.default_region();
 652             let tr = ty::mk_trait(this.tcx(),
 653                                   def_id,
 654                                   substs,
 655                                   ty::region_existential_bound(r));
 656             match ptr_ty {
 657                 Uniq => {
 658                     return ty::mk_uniq(this.tcx(), tr);
 659                 }
 660                 RPtr(r) => {
 661                     return ty::mk_rptr(this.tcx(),
 662                                        r,
 663                                        ty::mt {mutbl: a_seq_mutbl, ty: tr});
 664                 }
 665                 _ => {
 666                     tcx.sess.span_err(
 667                         a_seq_ty.span,
 668                         "~trait or &trait are the only supported \
 669                          forms of casting-to-trait");
 670                     return ty::mk_err();
 671                 }
 672
 673             }
 674         }
 675         ast::TyPath(ref path, ref opt_bounds, id) => {
 676             // Note that the "bounds must be empty if path is not a trait"
 677             // restriction is enforced in the below case for ty_path, which
 678             // will run after this as long as the path isn't a trait.
 679             match tcx.def_map.borrow().find(&id) {
 680                 Some(&def::DefPrimTy(ast::TyStr)) => {
 681                     check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 682                     match ptr_ty {
 683                         Uniq => {
 684                             return constr(ty::mk_str(tcx));
 685                         }
 686                         RPtr(r) => {
 687                             return ty::mk_str_slice(tcx, r, ast::MutImmutable);
 688                         }
 689                         _ => {
 690                             tcx.sess
 691                                .span_err(path.span,
 692                                          "managed strings are not supported")
 693                         }
 694                     }
 695                 }
 696                 Some(&def::DefTrait(trait_def_id)) => {
 697                     let result = ast_path_to_trait_ref(this,
 698                                                        rscope,
 699                                                        trait_def_id,
 700                                                        None,
 701                                                        None,
 702                                                        path);
 703                     let bounds = match *opt_bounds {
 704                         None => {
 705                             conv_existential_bounds(this,
 706                                                     rscope,
 707                                                     path.span,
 708                                                     [result.clone()].as_slice(),
 709                                                     [].as_slice())
 710                         }
 711                         Some(ref bounds) => {
 712                             conv_existential_bounds(this,
 713                                                     rscope,
 714                                                     path.span,
 715                                                     [result.clone()].as_slice(),
 716                                                     bounds.as_slice())
 717                         }
 718                     };
 719                     let tr = ty::mk_trait(tcx,
 720                                           result.def_id,
 721                                           result.substs.clone(),
 722                                           bounds);
 723                     return match ptr_ty {
 724                         Uniq => {
 725                             return ty::mk_uniq(tcx, tr);
 726                         }
 727                         RPtr(r) => {
 728                             return ty::mk_rptr(tcx, r, ty::mt{mutbl: a_seq_mutbl, ty: tr});
 729                         }
 730                         _ => {
 731                             tcx.sess.span_err(
 732                                 path.span,
 733                                 "~trait or &trait are the only supported \
 734                                  forms of casting-to-trait");
 735                             return ty::mk_err();
 736                         }
 737                     };
 738                 }
 739                 _ => {}
 740             }
 741         }
 742         _ => {}
 743     }
 744
 745     constr(ast_ty_to_ty(this, rscope, a_seq_ty))
 746 }
 747
 748 fn associated_ty_to_ty<'tcx,AC,RS>(this: &AC,
 749                                    rscope: &RS,
 750                                    trait_path: &ast::Path,
 751                                    for_ast_type: &ast::Ty,
 752                                    trait_type_id: ast::DefId,
 753                                    span: Span)
 754                                    -> ty::t
 755                                    where AC: AstConv<'tcx>, RS: RegionScope {
 756     // Find the trait that this associated type belongs to.
 757     let trait_did = match ty::impl_or_trait_item(this.tcx(),
 758                                                  trait_type_id).container() {
 759         ty::ImplContainer(_) => {
 760             this.tcx().sess.span_bug(span,
 761                                      "associated_ty_to_ty(): impl associated \
 762                                       types shouldn't go through this \
 763                                       function")
 764         }
 765         ty::TraitContainer(trait_id) => trait_id,
 766     };
 767
 768     let for_type = ast_ty_to_ty(this, rscope, for_ast_type);
 769     if !this.associated_types_of_trait_are_valid(for_type, trait_did) {
 770         this.tcx().sess.span_err(span,
 771                                  "this associated type is not \
 772                                   allowed in this context");
 773         return ty::mk_err()
 774     }
 775
 776     let trait_ref = ast_path_to_trait_ref(this,
 777                                           rscope,
 778                                           trait_did,
 779                                           None,
 780                                           Some(for_type),
 781                                           trait_path);
 782     let trait_def = this.get_trait_def(trait_did);
 783     for type_parameter in trait_def.generics.types.iter() {
 784         if type_parameter.def_id == trait_type_id {
 785             return *trait_ref.substs.types.get(type_parameter.space,
 786                                                type_parameter.index)
 787         }
 788     }
 789     this.tcx().sess.span_bug(span,
 790                              "this associated type didn't get added \
 791                               as a parameter for some reason")
 792 }
 793
 794 // Parses the programmer's textual representation of a type into our
 795 // internal notion of a type.
 796 pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
 797         this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> ty::t {
 798
 799     let tcx = this.tcx();
 800
 801     let mut ast_ty_to_ty_cache = tcx.ast_ty_to_ty_cache.borrow_mut();
 802     match ast_ty_to_ty_cache.find(&ast_ty.id) {
 803         Some(&ty::atttce_resolved(ty)) => return ty,
 804         Some(&ty::atttce_unresolved) => {
 805             tcx.sess.span_fatal(ast_ty.span,
 806                                 "illegal recursive type; insert an enum \
 807                                  or struct in the cycle, if this is \
 808                                  desired");
 809         }
 810         None => { /* go on */ }
 811     }
 812     ast_ty_to_ty_cache.insert(ast_ty.id, ty::atttce_unresolved);
 813     drop(ast_ty_to_ty_cache);
 814
 815     let typ = ast_ty_to_builtin_ty(this, rscope, ast_ty).unwrap_or_else(|| {
 816         match ast_ty.node {
 817             ast::TyNil => ty::mk_nil(),
 818             ast::TyBot => ty::mk_bot(),
 819             ast::TyBox(ref ty) => {
 820                 mk_pointer(this, rscope, ast::MutImmutable, &**ty, Box,
 821                            |ty| ty::mk_box(tcx, ty))
 822             }
 823             ast::TyUniq(ref ty) => {
 824                 mk_pointer(this, rscope, ast::MutImmutable, &**ty, Uniq,
 825                            |ty| ty::mk_uniq(tcx, ty))
 826             }
 827             ast::TyVec(ref ty) => {
 828                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty), None)
 829             }
 830             ast::TyPtr(ref mt) => {
 831                 ty::mk_ptr(tcx, ty::mt {
 832                     ty: ast_ty_to_ty(this, rscope, &*mt.ty),
 833                     mutbl: mt.mutbl
 834                 })
 835             }
 836             ast::TyRptr(ref region, ref mt) => {
 837                 let r = opt_ast_region_to_region(this, rscope, ast_ty.span, region);
 838                 debug!("ty_rptr r={}", r.repr(this.tcx()));
 839                 mk_pointer(this, rscope, mt.mutbl, &*mt.ty, RPtr(r),
 840                            |ty| ty::mk_rptr(tcx, r, ty::mt {ty: ty, mutbl: mt.mutbl}))
 841             }
 842             ast::TyTup(ref fields) => {
 843                 let flds = fields.iter()
 844                                  .map(|t| ast_ty_to_ty(this, rscope, &**t))
 845                                  .collect();
 846                 ty::mk_tup(tcx, flds)
 847             }
 848             ast::TyParen(ref typ) => ast_ty_to_ty(this, rscope, &**typ),
 849             ast::TyBareFn(ref bf) => {
 850                 if bf.decl.variadic && bf.abi != abi::C {
 851                     tcx.sess.span_err(ast_ty.span,
 852                                       "variadic function must have C calling convention");
 853                 }
 854                 ty::mk_bare_fn(tcx, ty_of_bare_fn(this, ast_ty.id, bf.fn_style,
 855                                                   bf.abi, &*bf.decl))
 856             }
 857             ast::TyClosure(ref f) => {
 858                 // Use corresponding trait store to figure out default bounds
 859                 // if none were specified.
 860                 let bounds = conv_existential_bounds(this,
 861                                                      rscope,
 862                                                      ast_ty.span,
 863                                                      [].as_slice(),
 864                                                      f.bounds.as_slice());
 865                 let fn_decl = ty_of_closure(this,
 866                                             ast_ty.id,
 867                                             f.fn_style,
 868                                             f.onceness,
 869                                             bounds,
 870                                             ty::RegionTraitStore(
 871                                                 bounds.region_bound,
 872                                                 ast::MutMutable),
 873                                             &*f.decl,
 874                                             abi::Rust,
 875                                             None);
 876                 ty::mk_closure(tcx, fn_decl)
 877             }
 878             ast::TyProc(ref f) => {
 879                 // Use corresponding trait store to figure out default bounds
 880                 // if none were specified.
 881                 let bounds = conv_existential_bounds(this, rscope,
 882                                                      ast_ty.span,
 883                                                      [].as_slice(),
 884                                                      f.bounds.as_slice());
 885
 886                 let fn_decl = ty_of_closure(this,
 887                                             ast_ty.id,
 888                                             f.fn_style,
 889                                             f.onceness,
 890                                             bounds,
 891                                             ty::UniqTraitStore,
 892                                             &*f.decl,
 893                                             abi::Rust,
 894                                             None);
 895
 896                 ty::mk_closure(tcx, fn_decl)
 897             }
 898             ast::TyUnboxedFn(..) => {
 899                 tcx.sess.span_err(ast_ty.span,
 900                                   "cannot use unboxed functions here");
 901                 ty::mk_err()
 902             }
 903             ast::TyPath(ref path, ref bounds, id) => {
 904                 let a_def = match tcx.def_map.borrow().find(&id) {
 905                     None => {
 906                         tcx.sess
 907                            .span_bug(ast_ty.span,
 908                                      format!("unbound path {}",
 909                                              path.repr(tcx)).as_slice())
 910                     }
 911                     Some(&d) => d
 912                 };
 913                 // Kind bounds on path types are only supported for traits.
 914                 match a_def {
 915                     // But don't emit the error if the user meant to do a trait anyway.
 916                     def::DefTrait(..) => { },
 917                     _ if bounds.is_some() =>
 918                         tcx.sess.span_err(ast_ty.span,
 919                                           "kind bounds can only be used on trait types"),
 920                     _ => { },
 921                 }
 922                 match a_def {
 923                     def::DefTrait(trait_def_id) => {
 924                         let result = ast_path_to_trait_ref(this,
 925                                                            rscope,
 926                                                            trait_def_id,
 927                                                            None,
 928                                                            None,
 929                                                            path);
 930                         let empty_bounds: &[ast::TyParamBound] = &[];
 931                         let ast_bounds = match *bounds {
 932                             Some(ref b) => b.as_slice(),
 933                             None => empty_bounds
 934                         };
 935                         let bounds = conv_existential_bounds(this,
 936                                                              rscope,
 937                                                              ast_ty.span,
 938                                                              &[result.clone()],
 939                                                              ast_bounds);
 940                         ty::mk_trait(tcx,
 941                                      result.def_id,
 942                                      result.substs.clone(),
 943                                      bounds)
 944                     }
 945                     def::DefTy(did, _) | def::DefStruct(did) => {
 946                         ast_path_to_ty(this, rscope, did, path).ty
 947                     }
 948                     def::DefTyParam(space, id, n) => {
 949                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 950                         ty::mk_param(tcx, space, n, id)
 951                     }
 952                     def::DefSelfTy(id) => {
 953                         // n.b.: resolve guarantees that the this type only appears in a
 954                         // trait, which we rely upon in various places when creating
 955                         // substs
 956                         check_path_args(tcx, path, NO_TPS | NO_REGIONS);
 957                         let did = ast_util::local_def(id);
 958                         ty::mk_self_type(tcx, did)
 959                     }
 960                     def::DefMod(id) => {
 961                         tcx.sess.span_fatal(ast_ty.span,
 962                             format!("found module name used as a type: {}",
 963                                     tcx.map.node_to_string(id.node)).as_slice());
 964                     }
 965                     def::DefPrimTy(_) => {
 966                         fail!("DefPrimTy arm missed in previous ast_ty_to_prim_ty call");
 967                     }
 968                     def::DefAssociatedTy(trait_type_id) => {
 969                         let path_str = tcx.map.path_to_string(
 970                             tcx.map.get_parent(trait_type_id.node));
 971                         tcx.sess.span_err(ast_ty.span,
 972                                           format!("ambiguous associated \
 973                                                    type; specify the type \
 974                                                    using the syntax `<Type \
 975                                                    as {}>::{}`",
 976                                                   path_str,
 977                                                   token::get_ident(
 978                                                       path.segments
 979                                                           .last()
 980                                                           .unwrap()
 981                                                           .identifier)
 982                                                   .get()).as_slice());
 983                         ty::mk_err()
 984                     }
 985                     _ => {
 986                         tcx.sess.span_fatal(ast_ty.span,
 987                                             format!("found value name used \
 988                                                      as a type: {:?}",
 989                                                     a_def).as_slice());
 990                     }
 991                 }
 992             }
 993             ast::TyQPath(ref qpath) => {
 994                 match tcx.def_map.borrow().find(&ast_ty.id) {
 995                     None => {
 996                         tcx.sess.span_bug(ast_ty.span,
 997                                           "unbound qualified path")
 998                     }
 999                     Some(&def::DefAssociatedTy(trait_type_id)) => {
1000                         associated_ty_to_ty(this,
1001                                             rscope,
1002                                             &qpath.trait_name,
1003                                             &*qpath.for_type,
1004                                             trait_type_id,
1005                                             ast_ty.span)
1006                     }
1007                     Some(_) => {
1008                         tcx.sess.span_err(ast_ty.span,
1009                                           "this qualified path does not name \
1010                                            an associated type");
1011                         ty::mk_err()
1012                     }
1013                 }
1014             }
1015             ast::TyFixedLengthVec(ref ty, ref e) => {
1016                 match const_eval::eval_const_expr_partial(tcx, &**e) {
1017                     Ok(ref r) => {
1018                         match *r {
1019                             const_eval::const_int(i) =>
1020                                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1021                                            Some(i as uint)),
1022                             const_eval::const_uint(i) =>
1023                                 ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1024                                            Some(i as uint)),
1025                             _ => {
1026                                 tcx.sess.span_fatal(
1027                                     ast_ty.span, "expected constant expr for vector length");
1028                             }
1029                         }
1030                     }
1031                     Err(ref r) => {
1032                         tcx.sess.span_fatal(
1033                             ast_ty.span,
1034                             format!("expected constant expr for vector \
1035                                      length: {}",
1036                                     *r).as_slice());
1037                     }
1038                 }
1039             }
1040             ast::TyTypeof(ref _e) => {
1041                 tcx.sess.span_bug(ast_ty.span, "typeof is reserved but unimplemented");
1042             }
1043             ast::TyInfer => {
1044                 // TyInfer also appears as the type of arguments or return
1045                 // values in a ExprFnBlock, ExprProc, or ExprUnboxedFn, or as
1046                 // the type of local variables. Both of these cases are
1047                 // handled specially and will not descend into this routine.
1048                 this.ty_infer(ast_ty.span)
1049             }
1050         }
1051     });
1052
1053     tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, ty::atttce_resolved(typ));
1054     return typ;
1055 }
1056
1057 pub fn ty_of_arg<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(this: &AC, rscope: &RS,
1058                                                            a: &ast::Arg,
1059                                                            expected_ty: Option<ty::t>)
1060                                                            -> ty::t {
1061     match a.ty.node {
1062         ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
1063         ast::TyInfer => this.ty_infer(a.ty.span),
1064         _ => ast_ty_to_ty(this, rscope, &*a.ty),
1065     }
1066 }
1067
1068 struct SelfInfo<'a> {
1069     untransformed_self_ty: ty::t,
1070     explicit_self: &'a ast::ExplicitSelf,
1071 }
1072
1073 pub fn ty_of_method<'tcx, AC: AstConv<'tcx>>(
1074                     this: &AC,
1075                     id: ast::NodeId,
1076                     fn_style: ast::FnStyle,
1077                     untransformed_self_ty: ty::t,
1078                     explicit_self: &ast::ExplicitSelf,
1079                     decl: &ast::FnDecl,
1080                     abi: abi::Abi)
1081                     -> (ty::BareFnTy, ty::ExplicitSelfCategory) {
1082     let self_info = Some(SelfInfo {
1083         untransformed_self_ty: untransformed_self_ty,
1084         explicit_self: explicit_self,
1085     });
1086     let (bare_fn_ty, optional_explicit_self_category) =
1087         ty_of_method_or_bare_fn(this,
1088                                 id,
1089                                 fn_style,
1090                                 abi,
1091                                 self_info,
1092                                 decl);
1093     (bare_fn_ty, optional_explicit_self_category.unwrap())
1094 }
1095
1096 pub fn ty_of_bare_fn<'tcx, AC: AstConv<'tcx>>(this: &AC, id: ast::NodeId,
1097                                               fn_style: ast::FnStyle, abi: abi::Abi,
1098                                               decl: &ast::FnDecl) -> ty::BareFnTy {
1099     let (bare_fn_ty, _) =
1100         ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl);
1101     bare_fn_ty
1102 }
1103
1104 fn ty_of_method_or_bare_fn<'tcx, AC: AstConv<'tcx>>(
1105                            this: &AC,
1106                            id: ast::NodeId,
1107                            fn_style: ast::FnStyle,
1108                            abi: abi::Abi,
1109                            opt_self_info: Option<SelfInfo>,
1110                            decl: &ast::FnDecl)
1111                            -> (ty::BareFnTy,
1112                                Option<ty::ExplicitSelfCategory>) {
1113     debug!("ty_of_method_or_bare_fn");
1114
1115     // New region names that appear inside of the arguments of the function
1116     // declaration are bound to that function type.
1117     let rb = rscope::BindingRscope::new(id);
1118
1119     // `implied_output_region` is the region that will be assumed for any
1120     // region parameters in the return type. In accordance with the rules for
1121     // lifetime elision, we can determine it in two ways. First (determined
1122     // here), if self is by-reference, then the implied output region is the
1123     // region of the self parameter.
1124     let mut explicit_self_category_result = None;
1125     let (self_ty, mut implied_output_region) = match opt_self_info {
1126         None => (None, None),
1127         Some(self_info) => {
1128             // Figure out and record the explicit self category.
1129             let explicit_self_category =
1130                 determine_explicit_self_category(this, &rb, &self_info);
1131             explicit_self_category_result = Some(explicit_self_category);
1132             match explicit_self_category {
1133                 ty::StaticExplicitSelfCategory => (None, None),
1134                 ty::ByValueExplicitSelfCategory => {
1135                     (Some(self_info.untransformed_self_ty), None)
1136                 }
1137                 ty::ByReferenceExplicitSelfCategory(region, mutability) => {
1138                     (Some(ty::mk_rptr(this.tcx(),
1139                                       region,
1140                                       ty::mt {
1141                                         ty: self_info.untransformed_self_ty,
1142                                         mutbl: mutability
1143                                       })),
1144                      Some(region))
1145                 }
1146                 ty::ByBoxExplicitSelfCategory => {
1147                     (Some(ty::mk_uniq(this.tcx(),
1148                                       self_info.untransformed_self_ty)),
1149                      None)
1150                 }
1151             }
1152         }
1153     };
1154
1155     // HACK(eddyb) replace the fake self type in the AST with the actual type.
1156     let input_tys = if self_ty.is_some() {
1157         decl.inputs.slice_from(1)
1158     } else {
1159         decl.inputs.as_slice()
1160     };
1161     let input_tys = input_tys.iter().map(|a| ty_of_arg(this, &rb, a, None));
1162     let self_and_input_tys: Vec<_> =
1163         self_ty.into_iter().chain(input_tys).collect();
1164
1165     // Second, if there was exactly one lifetime (either a substitution or a
1166     // reference) in the arguments, then any anonymous regions in the output
1167     // have that lifetime.
1168     if implied_output_region.is_none() {
1169         let mut self_and_input_tys_iter = self_and_input_tys.iter();
1170         if self_ty.is_some() {
1171             // Skip the first argument if `self` is present.
1172             drop(self_and_input_tys_iter.next())
1173         }
1174
1175         let mut accumulator = Vec::new();
1176         for input_type in self_and_input_tys_iter {
1177             ty::accumulate_lifetimes_in_type(&mut accumulator, *input_type)
1178         }
1179         if accumulator.len() == 1 {
1180             implied_output_region = Some(*accumulator.get(0));
1181         }
1182     }
1183
1184     let output_ty = match decl.output.node {
1185         ast::TyInfer => this.ty_infer(decl.output.span),
1186         _ => {
1187             match implied_output_region {
1188                 Some(implied_output_region) => {
1189                     let rb = SpecificRscope::new(implied_output_region);
1190                     ast_ty_to_ty(this, &rb, &*decl.output)
1191                 }
1192                 None => {
1193                     // All regions must be explicitly specified in the output
1194                     // if the lifetime elision rules do not apply. This saves
1195                     // the user from potentially-confusing errors.
1196                     let rb = ExplicitRscope;
1197                     ast_ty_to_ty(this, &rb, &*decl.output)
1198                 }
1199             }
1200         }
1201     };
1202
1203     (ty::BareFnTy {
1204         fn_style: fn_style,
1205         abi: abi,
1206         sig: ty::FnSig {
1207             binder_id: id,
1208             inputs: self_and_input_tys,
1209             output: output_ty,
1210             variadic: decl.variadic
1211         }
1212     }, explicit_self_category_result)
1213 }
1214
1215 fn determine_explicit_self_category<'tcx, AC: AstConv<'tcx>,
1216                                     RS:RegionScope>(
1217                                     this: &AC,
1218                                     rscope: &RS,
1219                                     self_info: &SelfInfo)
1220                                     -> ty::ExplicitSelfCategory {
1221     match self_info.explicit_self.node {
1222         ast::SelfStatic => ty::StaticExplicitSelfCategory,
1223         ast::SelfValue(_) => ty::ByValueExplicitSelfCategory,
1224         ast::SelfRegion(ref lifetime, mutability, _) => {
1225             let region =
1226                 opt_ast_region_to_region(this,
1227                                          rscope,
1228                                          self_info.explicit_self.span,
1229                                          lifetime);
1230             ty::ByReferenceExplicitSelfCategory(region, mutability)
1231         }
1232         ast::SelfExplicit(ref ast_type, _) => {
1233             let explicit_type = ast_ty_to_ty(this, rscope, &**ast_type);
1234
1235             {
1236                 let inference_context = infer::new_infer_ctxt(this.tcx());
1237                 let expected_self = self_info.untransformed_self_ty;
1238                 let actual_self = explicit_type;
1239                 let result = infer::mk_eqty(
1240                     &inference_context,
1241                     false,
1242                     infer::Misc(self_info.explicit_self.span),
1243                     expected_self,
1244                     actual_self);
1245                 match result {
1246                     Ok(_) => {
1247                         inference_context.resolve_regions_and_report_errors();
1248                         return ty::ByValueExplicitSelfCategory
1249                     }
1250                     Err(_) => {}
1251                 }
1252             }
1253
1254             match ty::get(explicit_type).sty {
1255                 ty::ty_rptr(region, tm) => {
1256                     typeck::require_same_types(
1257                         this.tcx(),
1258                         None,
1259                         false,
1260                         self_info.explicit_self.span,
1261                         self_info.untransformed_self_ty,
1262                         tm.ty,
1263                         || "not a valid type for `self`".to_owned());
1264                     return ty::ByReferenceExplicitSelfCategory(region,
1265                                                                tm.mutbl)
1266                 }
1267                 ty::ty_uniq(typ) => {
1268                     typeck::require_same_types(
1269                         this.tcx(),
1270                         None,
1271                         false,
1272                         self_info.explicit_self.span,
1273                         self_info.untransformed_self_ty,
1274                         typ,
1275                         || "not a valid type for `self`".to_owned());
1276                     return ty::ByBoxExplicitSelfCategory
1277                 }
1278                 _ => {
1279                     this.tcx()
1280                         .sess
1281                         .span_err(self_info.explicit_self.span,
1282                                   "not a valid type for `self`");
1283                     return ty::ByValueExplicitSelfCategory
1284                 }
1285             }
1286         }
1287     }
1288 }
1289
1290 pub fn ty_of_closure<'tcx, AC: AstConv<'tcx>>(
1291     this: &AC,
1292     id: ast::NodeId,
1293     fn_style: ast::FnStyle,
1294     onceness: ast::Onceness,
1295     bounds: ty::ExistentialBounds,
1296     store: ty::TraitStore,
1297     decl: &ast::FnDecl,
1298     abi: abi::Abi,
1299     expected_sig: Option<ty::FnSig>)
1300     -> ty::ClosureTy
1301 {
1302     debug!("ty_of_fn_decl");
1303
1304     // new region names that appear inside of the fn decl are bound to
1305     // that function type
1306     let rb = rscope::BindingRscope::new(id);
1307
1308     let input_tys = decl.inputs.iter().enumerate().map(|(i, a)| {
1309         let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1310             // no guarantee that the correct number of expected args
1311             // were supplied
1312             if i < e.inputs.len() {
1313                 Some(*e.inputs.get(i))
1314             } else {
1315                 None
1316             }
1317         });
1318         ty_of_arg(this, &rb, a, expected_arg_ty)
1319     }).collect();
1320
1321     let expected_ret_ty = expected_sig.map(|e| e.output);
1322     let output_ty = match decl.output.node {
1323         ast::TyInfer if expected_ret_ty.is_some() => expected_ret_ty.unwrap(),
1324         ast::TyInfer => this.ty_infer(decl.output.span),
1325         _ => ast_ty_to_ty(this, &rb, &*decl.output)
1326     };
1327
1328     ty::ClosureTy {
1329         fn_style: fn_style,
1330         onceness: onceness,
1331         store: store,
1332         bounds: bounds,
1333         abi: abi,
1334         sig: ty::FnSig {binder_id: id,
1335                         inputs: input_tys,
1336                         output: output_ty,
1337                         variadic: decl.variadic}
1338     }
1339 }
1340
1341 pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1342     this: &AC,
1343     rscope: &RS,
1344     span: Span,
1345     main_trait_refs: &[Rc<ty::TraitRef>],
1346     ast_bounds: &[ast::TyParamBound])
1347     -> ty::ExistentialBounds
1348 {
1349     /*!
1350      * Given an existential type like `Foo+'a+Bar`, this routine
1351      * converts the `'a` and `Bar` intos an `ExistentialBounds`
1352      * struct. The `main_trait_refs` argument specifies the `Foo` --
1353      * it is absent for closures. Eventually this should all be
1354      * normalized, I think, so that there is no "main trait ref" and
1355      * instead we just have a flat list of bounds as the existential
1356      * type.
1357      */
1358
1359     let ast_bound_refs: Vec<&ast::TyParamBound> =
1360         ast_bounds.iter().collect();
1361
1362     let PartitionedBounds { builtin_bounds,
1363                             trait_bounds,
1364                             region_bounds,
1365                             unboxed_fn_ty_bounds } =
1366         partition_bounds(this.tcx(), span, ast_bound_refs.as_slice());
1367
1368     if !trait_bounds.is_empty() {
1369         let b = trait_bounds.get(0);
1370         this.tcx().sess.span_err(
1371             b.path.span,
1372             format!("only the builtin traits can be used \
1373                      as closure or object bounds").as_slice());
1374     }
1375
1376     if !unboxed_fn_ty_bounds.is_empty() {
1377         this.tcx().sess.span_err(
1378             span,
1379             format!("only the builtin traits can be used \
1380                      as closure or object bounds").as_slice());
1381     }
1382
1383     // The "main trait refs", rather annoyingly, have no type
1384     // specified for the `Self` parameter of the trait. The reason for
1385     // this is that they are, after all, *existential* types, and
1386     // hence that type is unknown. However, leaving this type missing
1387     // causes the substitution code to go all awry when walking the
1388     // bounds, so here we clone those trait refs and insert ty::err as
1389     // the self type. Perhaps we should do this more generally, it'd
1390     // be convenient (or perhaps something else, i.e., ty::erased).
1391     let main_trait_refs: Vec<Rc<ty::TraitRef>> =
1392         main_trait_refs.iter()
1393         .map(|t|
1394              Rc::new(ty::TraitRef {
1395                  def_id: t.def_id,
1396                  substs: t.substs.with_self_ty(ty::mk_err()) }))
1397         .collect();
1398
1399     let region_bound = compute_region_bound(this,
1400                                             rscope,
1401                                             span,
1402                                             builtin_bounds,
1403                                             region_bounds.as_slice(),
1404                                             main_trait_refs.as_slice());
1405
1406     ty::ExistentialBounds {
1407         region_bound: region_bound,
1408         builtin_bounds: builtin_bounds,
1409     }
1410 }
1411
1412 pub fn compute_opt_region_bound(tcx: &ty::ctxt,
1413                                 span: Span,
1414                                 builtin_bounds: ty::BuiltinBounds,
1415                                 region_bounds: &[&ast::Lifetime],
1416                                 trait_bounds: &[Rc<ty::TraitRef>])
1417                                 -> Option<ty::Region>
1418 {
1419     /*!
1420      * Given the bounds on a type parameter / existential type,
1421      * determines what single region bound (if any) we can use to
1422      * summarize this type. The basic idea is that we will use the
1423      * bound the user provided, if they provided one, and otherwise
1424      * search the supertypes of trait bounds for region bounds. It may
1425      * be that we can derive no bound at all, in which case we return
1426      * `None`.
1427      */
1428
1429     if region_bounds.len() > 1 {
1430         tcx.sess.span_err(
1431             region_bounds[1].span,
1432             format!("only a single explicit lifetime bound is permitted").as_slice());
1433     }
1434
1435     if region_bounds.len() != 0 {
1436         // Explicitly specified region bound. Use that.
1437         let r = region_bounds[0];
1438         return Some(ast_region_to_region(tcx, r));
1439     }
1440
1441     // No explicit region bound specified. Therefore, examine trait
1442     // bounds and see if we can derive region bounds from those.
1443     let derived_region_bounds =
1444         ty::required_region_bounds(
1445             tcx,
1446             [],
1447             builtin_bounds,
1448             trait_bounds);
1449
1450     // If there are no derived region bounds, then report back that we
1451     // can find no region bound.
1452     if derived_region_bounds.len() == 0 {
1453         return None;
1454     }
1455
1456     // If any of the derived region bounds are 'static, that is always
1457     // the best choice.
1458     if derived_region_bounds.iter().any(|r| ty::ReStatic == *r) {
1459         return Some(ty::ReStatic);
1460     }
1461
1462     // Determine whether there is exactly one unique region in the set
1463     // of derived region bounds. If so, use that. Otherwise, report an
1464     // error.
1465     let r = *derived_region_bounds.get(0);
1466     if derived_region_bounds.slice_from(1).iter().any(|r1| r != *r1) {
1467         tcx.sess.span_err(
1468             span,
1469             format!("ambiguous lifetime bound, \
1470                      explicit lifetime bound required").as_slice());
1471     }
1472     return Some(r);
1473 }
1474
1475 fn compute_region_bound<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
1476     this: &AC,
1477     rscope: &RS,
1478     span: Span,
1479     builtin_bounds: ty::BuiltinBounds,
1480     region_bounds: &[&ast::Lifetime],
1481     trait_bounds: &[Rc<ty::TraitRef>])
1482     -> ty::Region
1483 {
1484     /*!
1485      * A version of `compute_opt_region_bound` for use where some
1486      * region bound is required (existential types,
1487      * basically). Reports an error if no region bound can be derived
1488      * and we are in an `rscope` that does not provide a default.
1489      */
1490
1491     match compute_opt_region_bound(this.tcx(), span, builtin_bounds,
1492                                    region_bounds, trait_bounds) {
1493         Some(r) => r,
1494         None => {
1495             match rscope.default_region_bound(span) {
1496                 Some(r) => { r }
1497                 None => {
1498                     this.tcx().sess.span_err(
1499                         span,
1500                         format!("explicit lifetime bound required").as_slice());
1501                     ty::ReStatic
1502                 }
1503             }
1504         }
1505     }
1506 }
1507
1508 pub struct PartitionedBounds<'a> {
1509     pub builtin_bounds: ty::BuiltinBounds,
1510     pub trait_bounds: Vec<&'a ast::TraitRef>,
1511     pub unboxed_fn_ty_bounds: Vec<&'a ast::UnboxedFnBound>,
1512     pub region_bounds: Vec<&'a ast::Lifetime>,
1513 }
1514
1515 pub fn partition_bounds<'a>(tcx: &ty::ctxt,
1516                             _span: Span,
1517                             ast_bounds: &'a [&ast::TyParamBound])
1518                             -> PartitionedBounds<'a>
1519 {
1520     /*!
1521      * Divides a list of bounds from the AST into three groups:
1522      * builtin bounds (Copy, Sized etc), general trait bounds,
1523      * and region bounds.
1524      */
1525
1526     let mut builtin_bounds = ty::empty_builtin_bounds();
1527     let mut region_bounds = Vec::new();
1528     let mut trait_bounds = Vec::new();
1529     let mut unboxed_fn_ty_bounds = Vec::new();
1530     let mut trait_def_ids = HashMap::new();
1531     for &ast_bound in ast_bounds.iter() {
1532         match *ast_bound {
1533             ast::TraitTyParamBound(ref b) => {
1534                 match lookup_def_tcx(tcx, b.path.span, b.ref_id) {
1535                     def::DefTrait(trait_did) => {
1536                         match trait_def_ids.find(&trait_did) {
1537                             // Already seen this trait. We forbid
1538                             // duplicates in the list (for some
1539                             // reason).
1540                             Some(span) => {
1541                                 span_err!(
1542                                     tcx.sess, b.path.span, E0127,
1543                                     "trait `{}` already appears in the \
1544                                      list of bounds",
1545                                     b.path.user_string(tcx));
1546                                 tcx.sess.span_note(
1547                                     *span,
1548                                     "previous appearance is here");
1549
1550                                 continue;
1551                             }
1552
1553                             None => { }
1554                         }
1555
1556                         trait_def_ids.insert(trait_did, b.path.span);
1557
1558                         if ty::try_add_builtin_trait(tcx,
1559                                                      trait_did,
1560                                                      &mut builtin_bounds) {
1561                             continue; // success
1562                         }
1563                     }
1564                     _ => {
1565                         // Not a trait? that's an error, but it'll get
1566                         // reported later.
1567                     }
1568                 }
1569                 trait_bounds.push(b);
1570             }
1571             ast::RegionTyParamBound(ref l) => {
1572                 region_bounds.push(l);
1573             }
1574             ast::UnboxedFnTyParamBound(ref unboxed_function) => {
1575                 unboxed_fn_ty_bounds.push(&**unboxed_function);
1576             }
1577         }
1578     }
1579
1580     PartitionedBounds {
1581         builtin_bounds: builtin_bounds,
1582         trait_bounds: trait_bounds,
1583         region_bounds: region_bounds,
1584         unboxed_fn_ty_bounds: unboxed_fn_ty_bounds
1585     }
1586 }
1587