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