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