src/librustc_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 //! Conversion from AST representation of types to the ty.rs
  12 //! representation.  The main routine here is `ast_ty_to_ty()`: each use
  13 //! is parameterized by an instance of `AstConv` and a `RegionScope`.
  14 //!
  15 //! The parameterization of `ast_ty_to_ty()` is because it behaves
  16 //! somewhat differently during the collect and check phases,
  17 //! particularly with respect to looking up the types of top-level
  18 //! items.  In the collect phase, the crate context is used as the
  19 //! `AstConv` instance; in this phase, the `get_item_type_scheme()`
  20 //! function triggers a recursive call to `type_scheme_of_item()`
  21 //! (note that `ast_ty_to_ty()` will detect recursive types and report
  22 //! an error).  In the check phase, when the FnCtxt is used as the
  23 //! `AstConv`, `get_item_type_scheme()` just looks up the item type in
  24 //! `tcx.tcache` (using `ty::lookup_item_type`).
  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 use middle::astconv_util::{prim_ty_to_ty, check_path_args, NO_TPS, NO_REGIONS};
  52 use middle::const_eval;
  53 use middle::def;
  54 use middle::resolve_lifetime as rl;
  55 use middle::privacy::{AllPublic, LastMod};
  56 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
  57 use middle::traits;
  58 use middle::ty::{self, RegionEscape, Ty};
  59 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
  60              ObjectLifetimeDefaultRscope, ShiftedRscope, BindingRscope};
  61 use util::common::{ErrorReported, FN_OUTPUT_NAME};
  62 use util::ppaux::{self, Repr, UserString};
  63
  64 use std::iter::{repeat, AdditiveIterator};
  65 use std::rc::Rc;
  66 use std::slice;
  67 use syntax::{abi, ast, ast_util};
  68 use syntax::codemap::Span;
  69 use syntax::parse::token;
  70 use syntax::print::pprust;
  71
  72 pub trait AstConv<'tcx> {
  73     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
  74
  75     /// Identify the type scheme for an item with a type, like a type
  76     /// alias, fn, or struct. This allows you to figure out the set of
  77     /// type parameters defined on the item.
  78     fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
  79                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>;
  80
  81     /// Returns the `TraitDef` for a given trait. This allows you to
  82     /// figure out the set of type parameters defined on the trait.
  83     fn get_trait_def(&self, span: Span, id: ast::DefId)
  84                      -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>;
  85
  86     /// Ensure that the super-predicates for the trait with the given
  87     /// id are available and also for the transitive set of
  88     /// super-predicates.
  89     fn ensure_super_predicates(&self, span: Span, id: ast::DefId)
  90                                -> Result<(), ErrorReported>;
  91
  92     /// Returns the set of bounds in scope for the type parameter with
  93     /// the given id.
  94     fn get_type_parameter_bounds(&self, span: Span, def_id: ast::NodeId)
  95                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>;
  96
  97     /// Returns true if the trait with id `trait_def_id` defines an
  98     /// associated type with the name `name`.
  99     fn trait_defines_associated_type_named(&self, trait_def_id: ast::DefId, name: ast::Name)
 100                                            -> bool;
 101
 102     /// Return an (optional) substitution to convert bound type parameters that
 103     /// are in scope into free ones. This function should only return Some
 104     /// within a fn body.
 105     /// See ParameterEnvironment::free_substs for more information.
 106     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
 107         None
 108     }
 109
 110     /// What type should we use when a type is omitted?
 111     fn ty_infer(&self, span: Span) -> Ty<'tcx>;
 112
 113     /// Projecting an associated type from a (potentially)
 114     /// higher-ranked trait reference is more complicated, because of
 115     /// the possibility of late-bound regions appearing in the
 116     /// associated type binding. This is not legal in function
 117     /// signatures for that reason. In a function body, we can always
 118     /// handle it because we can use inference variables to remove the
 119     /// late-bound regions.
 120     fn projected_ty_from_poly_trait_ref(&self,
 121                                         span: Span,
 122                                         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 123                                         item_name: ast::Name)
 124                                         -> Ty<'tcx>
 125     {
 126         if ty::binds_late_bound_regions(self.tcx(), &poly_trait_ref) {
 127             span_err!(self.tcx().sess, span, E0212,
 128                 "cannot extract an associated type from a higher-ranked trait bound \
 129                  in this context");
 130             self.tcx().types.err
 131         } else {
 132             // no late-bound regions, we can just ignore the binder
 133             self.projected_ty(span, poly_trait_ref.0.clone(), item_name)
 134         }
 135     }
 136
 137     /// Project an associated type from a non-higher-ranked trait reference.
 138     /// This is fairly straightforward and can be accommodated in any context.
 139     fn projected_ty(&self,
 140                     span: Span,
 141                     _trait_ref: Rc<ty::TraitRef<'tcx>>,
 142                     _item_name: ast::Name)
 143                     -> Ty<'tcx>;
 144 }
 145
 146 pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
 147                             -> ty::Region {
 148     let r = match tcx.named_region_map.get(&lifetime.id) {
 149         None => {
 150             // should have been recorded by the `resolve_lifetime` pass
 151             tcx.sess.span_bug(lifetime.span, "unresolved lifetime");
 152         }
 153
 154         Some(&rl::DefStaticRegion) => {
 155             ty::ReStatic
 156         }
 157
 158         Some(&rl::DefLateBoundRegion(debruijn, id)) => {
 159             ty::ReLateBound(debruijn, ty::BrNamed(ast_util::local_def(id), lifetime.name))
 160         }
 161
 162         Some(&rl::DefEarlyBoundRegion(space, index, id)) => {
 163             ty::ReEarlyBound(id, space, index, lifetime.name)
 164         }
 165
 166         Some(&rl::DefFreeRegion(scope, id)) => {
 167             ty::ReFree(ty::FreeRegion {
 168                     scope: scope,
 169                     bound_region: ty::BrNamed(ast_util::local_def(id),
 170                                               lifetime.name)
 171                 })
 172         }
 173     };
 174
 175     debug!("ast_region_to_region(lifetime={} id={}) yields {}",
 176            lifetime.repr(tcx),
 177            lifetime.id,
 178            r.repr(tcx));
 179
 180     r
 181 }
 182
 183 pub fn opt_ast_region_to_region<'tcx>(
 184     this: &AstConv<'tcx>,
 185     rscope: &RegionScope,
 186     default_span: Span,
 187     opt_lifetime: &Option<ast::Lifetime>) -> ty::Region
 188 {
 189     let r = match *opt_lifetime {
 190         Some(ref lifetime) => {
 191             ast_region_to_region(this.tcx(), lifetime)
 192         }
 193
 194         None => {
 195             match rscope.anon_regions(default_span, 1) {
 196                 Err(v) => {
 197                     debug!("optional region in illegal location");
 198                     span_err!(this.tcx().sess, default_span, E0106,
 199                         "missing lifetime specifier");
 200                     match v {
 201                         Some(v) => {
 202                             let mut m = String::new();
 203                             let len = v.len();
 204                             for (i, (name, n)) in v.into_iter().enumerate() {
 205                                 let help_name = if name.is_empty() {
 206                                     format!("argument {}", i + 1)
 207                                 } else {
 208                                     format!("`{}`", name)
 209                                 };
 210
 211                                 m.push_str(&(if n == 1 {
 212                                     help_name
 213                                 } else {
 214                                     format!("one of {}'s {} elided lifetimes", help_name, n)
 215                                 })[..]);
 216
 217                                 if len == 2 && i == 0 {
 218                                     m.push_str(" or ");
 219                                 } else if i + 2 == len {
 220                                     m.push_str(", or ");
 221                                 } else if i + 1 != len {
 222                                     m.push_str(", ");
 223                                 }
 224                             }
 225                             if len == 1 {
 226                                 fileline_help!(this.tcx().sess, default_span,
 227                                     "this function's return type contains a borrowed value, but \
 228                                      the signature does not say which {} it is borrowed from",
 229                                     m);
 230                             } else if len == 0 {
 231                                 fileline_help!(this.tcx().sess, default_span,
 232                                     "this function's return type contains a borrowed value, but \
 233                                      there is no value for it to be borrowed from");
 234                                 fileline_help!(this.tcx().sess, default_span,
 235                                     "consider giving it a 'static lifetime");
 236                             } else {
 237                                 fileline_help!(this.tcx().sess, default_span,
 238                                     "this function's return type contains a borrowed value, but \
 239                                      the signature does not say whether it is borrowed from {}",
 240                                     m);
 241                             }
 242                         }
 243                         None => {},
 244                     }
 245                     ty::ReStatic
 246                 }
 247
 248                 Ok(rs) => rs[0],
 249             }
 250         }
 251     };
 252
 253     debug!("opt_ast_region_to_region(opt_lifetime={}) yields {}",
 254             opt_lifetime.repr(this.tcx()),
 255             r.repr(this.tcx()));
 256
 257     r
 258 }
 259
 260 /// Given a path `path` that refers to an item `I` with the declared generics `decl_generics`,
 261 /// returns an appropriate set of substitutions for this particular reference to `I`.
 262 pub fn ast_path_substs_for_ty<'tcx>(
 263     this: &AstConv<'tcx>,
 264     rscope: &RegionScope,
 265     span: Span,
 266     param_mode: PathParamMode,
 267     decl_generics: &ty::Generics<'tcx>,
 268     item_segment: &ast::PathSegment)
 269     -> Substs<'tcx>
 270 {
 271     let tcx = this.tcx();
 272
 273     // ast_path_substs() is only called to convert paths that are
 274     // known to refer to traits, types, or structs. In these cases,
 275     // all type parameters defined for the item being referenced will
 276     // be in the TypeSpace or SelfSpace.
 277     //
 278     // Note: in the case of traits, the self parameter is also
 279     // defined, but we don't currently create a `type_param_def` for
 280     // `Self` because it is implicit.
 281     assert!(decl_generics.regions.all(|d| d.space == TypeSpace));
 282     assert!(decl_generics.types.all(|d| d.space != FnSpace));
 283
 284     let (regions, types, assoc_bindings) = match item_segment.parameters {
 285         ast::AngleBracketedParameters(ref data) => {
 286             convert_angle_bracketed_parameters(this, rscope, span, decl_generics, data)
 287         }
 288         ast::ParenthesizedParameters(ref data) => {
 289             span_err!(tcx.sess, span, E0214,
 290                 "parenthesized parameters may only be used with a trait");
 291             convert_parenthesized_parameters(this, rscope, span, decl_generics, data)
 292         }
 293     };
 294
 295     prohibit_projections(this.tcx(), &assoc_bindings);
 296
 297     create_substs_for_ast_path(this,
 298                                span,
 299                                param_mode,
 300                                decl_generics,
 301                                None,
 302                                types,
 303                                regions)
 304 }
 305
 306 #[derive(PartialEq, Eq)]
 307 pub enum PathParamMode {
 308     // Any path in a type context.
 309     Explicit,
 310     // The `module::Type` in `module::Type::method` in an expression.
 311     Optional
 312 }
 313
 314 fn create_region_substs<'tcx>(
 315     this: &AstConv<'tcx>,
 316     rscope: &RegionScope,
 317     span: Span,
 318     decl_generics: &ty::Generics<'tcx>,
 319     regions_provided: Vec<ty::Region>)
 320     -> Substs<'tcx>
 321 {
 322     let tcx = this.tcx();
 323
 324     // If the type is parameterized by the this region, then replace this
 325     // region with the current anon region binding (in other words,
 326     // whatever & would get replaced with).
 327     let expected_num_region_params = decl_generics.regions.len(TypeSpace);
 328     let supplied_num_region_params = regions_provided.len();
 329     let regions = if expected_num_region_params == supplied_num_region_params {
 330         regions_provided
 331     } else {
 332         let anon_regions =
 333             rscope.anon_regions(span, expected_num_region_params);
 334
 335         if supplied_num_region_params != 0 || anon_regions.is_err() {
 336             report_lifetime_number_error(tcx, span,
 337                                          supplied_num_region_params,
 338                                          expected_num_region_params);
 339         }
 340
 341         match anon_regions {
 342             Ok(anon_regions) => anon_regions,
 343             Err(_) => (0..expected_num_region_params).map(|_| ty::ReStatic).collect()
 344         }
 345     };
 346     Substs::new_type(vec![], regions)
 347 }
 348
 349 /// Given the type/region arguments provided to some path (along with
 350 /// an implicit Self, if this is a trait reference) returns the complete
 351 /// set of substitutions. This may involve applying defaulted type parameters.
 352 ///
 353 /// Note that the type listing given here is *exactly* what the user provided.
 354 ///
 355 /// The `region_substs` should be the result of `create_region_substs`
 356 /// -- that is, a substitution with no types but the correct number of
 357 /// regions.
 358 fn create_substs_for_ast_path<'tcx>(
 359     this: &AstConv<'tcx>,
 360     span: Span,
 361     param_mode: PathParamMode,
 362     decl_generics: &ty::Generics<'tcx>,
 363     self_ty: Option<Ty<'tcx>>,
 364     types_provided: Vec<Ty<'tcx>>,
 365     region_substs: Substs<'tcx>)
 366     -> Substs<'tcx>
 367 {
 368     let tcx = this.tcx();
 369
 370     debug!("create_substs_for_ast_path(decl_generics={}, self_ty={}, \
 371            types_provided={}, region_substs={}",
 372            decl_generics.repr(tcx), self_ty.repr(tcx), types_provided.repr(tcx),
 373            region_substs.repr(tcx));
 374
 375     assert_eq!(region_substs.regions().len(TypeSpace), decl_generics.regions.len(TypeSpace));
 376     assert!(region_substs.types.is_empty());
 377
 378     // Convert the type parameters supplied by the user.
 379     let ty_param_defs = decl_generics.types.get_slice(TypeSpace);
 380     let formal_ty_param_count = ty_param_defs.len();
 381     let required_ty_param_count = ty_param_defs.iter()
 382                                                .take_while(|x| x.default.is_none())
 383                                                .count();
 384
 385     // Fill with `ty_infer` if no params were specified, as long as
 386     // they were optional (e.g. paths inside expressions).
 387     let mut type_substs = if param_mode == PathParamMode::Optional &&
 388                              types_provided.is_empty() {
 389         (0..formal_ty_param_count).map(|_| this.ty_infer(span)).collect()
 390     } else {
 391         types_provided
 392     };
 393
 394     let supplied_ty_param_count = type_substs.len();
 395     check_type_argument_count(this.tcx(), span, supplied_ty_param_count,
 396                               required_ty_param_count, formal_ty_param_count);
 397
 398     if supplied_ty_param_count < required_ty_param_count {
 399         while type_substs.len() < required_ty_param_count {
 400             type_substs.push(tcx.types.err);
 401         }
 402     } else if supplied_ty_param_count > formal_ty_param_count {
 403         type_substs.truncate(formal_ty_param_count);
 404     }
 405     assert!(type_substs.len() >= required_ty_param_count &&
 406             type_substs.len() <= formal_ty_param_count);
 407
 408     let mut substs = region_substs;
 409     substs.types.extend(TypeSpace, type_substs.into_iter());
 410
 411     match self_ty {
 412         None => {
 413             // If no self-type is provided, it's still possible that
 414             // one was declared, because this could be an object type.
 415         }
 416         Some(ty) => {
 417             // If a self-type is provided, one should have been
 418             // "declared" (in other words, this should be a
 419             // trait-ref).
 420             assert!(decl_generics.types.get_self().is_some());
 421             substs.types.push(SelfSpace, ty);
 422         }
 423     }
 424
 425     let actual_supplied_ty_param_count = substs.types.len(TypeSpace);
 426     for param in &ty_param_defs[actual_supplied_ty_param_count..] {
 427         if let Some(default) = param.default {
 428             // If we are converting an object type, then the
 429             // `Self` parameter is unknown. However, some of the
 430             // other type parameters may reference `Self` in their
 431             // defaults. This will lead to an ICE if we are not
 432             // careful!
 433             if self_ty.is_none() && ty::type_has_self(default) {
 434                 tcx.sess.span_err(
 435                     span,
 436                     &format!("the type parameter `{}` must be explicitly specified \
 437                               in an object type because its default value `{}` references \
 438                               the type `Self`",
 439                              param.name.user_string(tcx),
 440                              default.user_string(tcx)));
 441                 substs.types.push(TypeSpace, tcx.types.err);
 442             } else {
 443                 // This is a default type parameter.
 444                 let default = default.subst_spanned(tcx,
 445                                                     &substs,
 446                                                     Some(span));
 447                 substs.types.push(TypeSpace, default);
 448             }
 449         } else {
 450             tcx.sess.span_bug(span, "extra parameter without default");
 451         }
 452     }
 453
 454     substs
 455 }
 456
 457 struct ConvertedBinding<'tcx> {
 458     item_name: ast::Name,
 459     ty: Ty<'tcx>,
 460     span: Span,
 461 }
 462
 463 fn convert_angle_bracketed_parameters<'tcx>(this: &AstConv<'tcx>,
 464                                             rscope: &RegionScope,
 465                                             span: Span,
 466                                             decl_generics: &ty::Generics<'tcx>,
 467                                             data: &ast::AngleBracketedParameterData)
 468                                             -> (Substs<'tcx>,
 469                                                 Vec<Ty<'tcx>>,
 470                                                 Vec<ConvertedBinding<'tcx>>)
 471 {
 472     let regions: Vec<_> =
 473         data.lifetimes.iter()
 474                       .map(|l| ast_region_to_region(this.tcx(), l))
 475                       .collect();
 476
 477     let region_substs =
 478         create_region_substs(this, rscope, span, decl_generics, regions);
 479
 480     let types: Vec<_> =
 481         data.types.iter()
 482                   .enumerate()
 483                   .map(|(i,t)| ast_ty_arg_to_ty(this, rscope, decl_generics,
 484                                                 i, &region_substs, t))
 485                   .collect();
 486
 487     let assoc_bindings: Vec<_> =
 488         data.bindings.iter()
 489                      .map(|b| ConvertedBinding { item_name: b.ident.name,
 490                                                  ty: ast_ty_to_ty(this, rscope, &*b.ty),
 491                                                  span: b.span })
 492                      .collect();
 493
 494     (region_substs, types, assoc_bindings)
 495 }
 496
 497 /// Returns the appropriate lifetime to use for any output lifetimes
 498 /// (if one exists) and a vector of the (pattern, number of lifetimes)
 499 /// corresponding to each input type/pattern.
 500 fn find_implied_output_region(input_tys: &[Ty], input_pats: Vec<String>)
 501                               -> (Option<ty::Region>, Vec<(String, usize)>)
 502 {
 503     let mut lifetimes_for_params: Vec<(String, usize)> = Vec::new();
 504     let mut possible_implied_output_region = None;
 505
 506     for (input_type, input_pat) in input_tys.iter().zip(input_pats.into_iter()) {
 507         let mut accumulator = Vec::new();
 508         ty::accumulate_lifetimes_in_type(&mut accumulator, *input_type);
 509
 510         if accumulator.len() == 1 {
 511             // there's a chance that the unique lifetime of this
 512             // iteration will be the appropriate lifetime for output
 513             // parameters, so lets store it.
 514             possible_implied_output_region = Some(accumulator[0])
 515         }
 516
 517         lifetimes_for_params.push((input_pat, accumulator.len()));
 518     }
 519
 520     let implied_output_region = if lifetimes_for_params.iter().map(|&(_, n)| n).sum() == 1 {
 521         assert!(possible_implied_output_region.is_some());
 522         possible_implied_output_region
 523     } else {
 524         None
 525     };
 526     (implied_output_region, lifetimes_for_params)
 527 }
 528
 529 fn convert_ty_with_lifetime_elision<'tcx>(this: &AstConv<'tcx>,
 530                                           implied_output_region: Option<ty::Region>,
 531                                           param_lifetimes: Vec<(String, usize)>,
 532                                           ty: &ast::Ty)
 533                                           -> Ty<'tcx>
 534 {
 535     match implied_output_region {
 536         Some(implied_output_region) => {
 537             let rb = ElidableRscope::new(implied_output_region);
 538             ast_ty_to_ty(this, &rb, ty)
 539         }
 540         None => {
 541             // All regions must be explicitly specified in the output
 542             // if the lifetime elision rules do not apply. This saves
 543             // the user from potentially-confusing errors.
 544             let rb = UnelidableRscope::new(param_lifetimes);
 545             ast_ty_to_ty(this, &rb, ty)
 546         }
 547     }
 548 }
 549
 550 fn convert_parenthesized_parameters<'tcx>(this: &AstConv<'tcx>,
 551                                           rscope: &RegionScope,
 552                                           span: Span,
 553                                           decl_generics: &ty::Generics<'tcx>,
 554                                           data: &ast::ParenthesizedParameterData)
 555                                           -> (Substs<'tcx>,
 556                                               Vec<Ty<'tcx>>,
 557                                               Vec<ConvertedBinding<'tcx>>)
 558 {
 559     let region_substs =
 560         create_region_substs(this, rscope, span, decl_generics, Vec::new());
 561
 562     let binding_rscope = BindingRscope::new();
 563     let inputs =
 564         data.inputs.iter()
 565                    .map(|a_t| ast_ty_arg_to_ty(this, &binding_rscope, decl_generics,
 566                                                0, &region_substs, a_t))
 567                    .collect::<Vec<Ty<'tcx>>>();
 568
 569     let input_params: Vec<_> = repeat(String::new()).take(inputs.len()).collect();
 570     let (implied_output_region,
 571          params_lifetimes) = find_implied_output_region(&*inputs, input_params);
 572
 573     let input_ty = ty::mk_tup(this.tcx(), inputs);
 574
 575     let (output, output_span) = match data.output {
 576         Some(ref output_ty) => {
 577             (convert_ty_with_lifetime_elision(this,
 578                                               implied_output_region,
 579                                               params_lifetimes,
 580                                               &**output_ty),
 581              output_ty.span)
 582         }
 583         None => {
 584             (ty::mk_nil(this.tcx()), data.span)
 585         }
 586     };
 587
 588     let output_binding = ConvertedBinding {
 589         item_name: token::intern(FN_OUTPUT_NAME),
 590         ty: output,
 591         span: output_span
 592     };
 593
 594     (region_substs, vec![input_ty], vec![output_binding])
 595 }
 596
 597 pub fn instantiate_poly_trait_ref<'tcx>(
 598     this: &AstConv<'tcx>,
 599     rscope: &RegionScope,
 600     ast_trait_ref: &ast::PolyTraitRef,
 601     self_ty: Option<Ty<'tcx>>,
 602     poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 603     -> ty::PolyTraitRef<'tcx>
 604 {
 605     let trait_ref = &ast_trait_ref.trait_ref;
 606     let trait_def_id = trait_def_id(this, trait_ref);
 607     ast_path_to_poly_trait_ref(this,
 608                                rscope,
 609                                trait_ref.path.span,
 610                                PathParamMode::Explicit,
 611                                trait_def_id,
 612                                self_ty,
 613                                trait_ref.path.segments.last().unwrap(),
 614                                poly_projections)
 615 }
 616
 617 /// Instantiates the path for the given trait reference, assuming that it's
 618 /// bound to a valid trait type. Returns the def_id for the defining trait.
 619 /// Fails if the type is a type other than a trait type.
 620 ///
 621 /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T=X>`
 622 /// are disallowed. Otherwise, they are pushed onto the vector given.
 623 pub fn instantiate_mono_trait_ref<'tcx>(
 624     this: &AstConv<'tcx>,
 625     rscope: &RegionScope,
 626     trait_ref: &ast::TraitRef,
 627     self_ty: Option<Ty<'tcx>>)
 628     -> Rc<ty::TraitRef<'tcx>>
 629 {
 630     let trait_def_id = trait_def_id(this, trait_ref);
 631     ast_path_to_mono_trait_ref(this,
 632                                rscope,
 633                                trait_ref.path.span,
 634                                PathParamMode::Explicit,
 635                                trait_def_id,
 636                                self_ty,
 637                                trait_ref.path.segments.last().unwrap())
 638 }
 639
 640 fn trait_def_id<'tcx>(this: &AstConv<'tcx>, trait_ref: &ast::TraitRef) -> ast::DefId {
 641     let path = &trait_ref.path;
 642     match ::lookup_full_def(this.tcx(), path.span, trait_ref.ref_id) {
 643         def::DefTrait(trait_def_id) => trait_def_id,
 644         _ => {
 645             span_fatal!(this.tcx().sess, path.span, E0245, "`{}` is not a trait",
 646                         path.user_string(this.tcx()));
 647         }
 648     }
 649 }
 650
 651 fn object_path_to_poly_trait_ref<'a,'tcx>(
 652     this: &AstConv<'tcx>,
 653     rscope: &RegionScope,
 654     span: Span,
 655     param_mode: PathParamMode,
 656     trait_def_id: ast::DefId,
 657     trait_segment: &ast::PathSegment,
 658     mut projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 659     -> ty::PolyTraitRef<'tcx>
 660 {
 661     ast_path_to_poly_trait_ref(this,
 662                                rscope,
 663                                span,
 664                                param_mode,
 665                                trait_def_id,
 666                                None,
 667                                trait_segment,
 668                                projections)
 669 }
 670
 671 fn ast_path_to_poly_trait_ref<'a,'tcx>(
 672     this: &AstConv<'tcx>,
 673     rscope: &RegionScope,
 674     span: Span,
 675     param_mode: PathParamMode,
 676     trait_def_id: ast::DefId,
 677     self_ty: Option<Ty<'tcx>>,
 678     trait_segment: &ast::PathSegment,
 679     poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 680     -> ty::PolyTraitRef<'tcx>
 681 {
 682     // The trait reference introduces a binding level here, so
 683     // we need to shift the `rscope`. It'd be nice if we could
 684     // do away with this rscope stuff and work this knowledge
 685     // into resolve_lifetimes, as we do with non-omitted
 686     // lifetimes. Oh well, not there yet.
 687     let shifted_rscope = &ShiftedRscope::new(rscope);
 688
 689     let (substs, assoc_bindings) =
 690         create_substs_for_ast_trait_ref(this,
 691                                         shifted_rscope,
 692                                         span,
 693                                         param_mode,
 694                                         trait_def_id,
 695                                         self_ty,
 696                                         trait_segment);
 697     let poly_trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_def_id, substs)));
 698
 699     {
 700         let converted_bindings =
 701             assoc_bindings
 702             .iter()
 703             .filter_map(|binding| {
 704                 // specify type to assert that error was already reported in Err case:
 705                 let predicate: Result<_, ErrorReported> =
 706                     ast_type_binding_to_poly_projection_predicate(this,
 707                                                                   poly_trait_ref.clone(),
 708                                                                   self_ty,
 709                                                                   binding);
 710                 predicate.ok() // ok to ignore Err() because ErrorReported (see above)
 711             });
 712         poly_projections.extend(converted_bindings);
 713     }
 714
 715     poly_trait_ref
 716 }
 717
 718 fn ast_path_to_mono_trait_ref<'a,'tcx>(this: &AstConv<'tcx>,
 719                                        rscope: &RegionScope,
 720                                        span: Span,
 721                                        param_mode: PathParamMode,
 722                                        trait_def_id: ast::DefId,
 723                                        self_ty: Option<Ty<'tcx>>,
 724                                        trait_segment: &ast::PathSegment)
 725                                        -> Rc<ty::TraitRef<'tcx>>
 726 {
 727     let (substs, assoc_bindings) =
 728         create_substs_for_ast_trait_ref(this,
 729                                         rscope,
 730                                         span,
 731                                         param_mode,
 732                                         trait_def_id,
 733                                         self_ty,
 734                                         trait_segment);
 735     prohibit_projections(this.tcx(), &assoc_bindings);
 736     Rc::new(ty::TraitRef::new(trait_def_id, substs))
 737 }
 738
 739 fn create_substs_for_ast_trait_ref<'a,'tcx>(this: &AstConv<'tcx>,
 740                                             rscope: &RegionScope,
 741                                             span: Span,
 742                                             param_mode: PathParamMode,
 743                                             trait_def_id: ast::DefId,
 744                                             self_ty: Option<Ty<'tcx>>,
 745                                             trait_segment: &ast::PathSegment)
 746                                             -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
 747 {
 748     debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
 749            trait_segment);
 750
 751     let trait_def = match this.get_trait_def(span, trait_def_id) {
 752         Ok(trait_def) => trait_def,
 753         Err(ErrorReported) => {
 754             // No convenient way to recover from a cycle here. Just bail. Sorry!
 755             this.tcx().sess.abort_if_errors();
 756             this.tcx().sess.bug("ErrorReported returned, but no errors reports?")
 757         }
 758     };
 759
 760     let (regions, types, assoc_bindings) = match trait_segment.parameters {
 761         ast::AngleBracketedParameters(ref data) => {
 762             // For now, require that parenthetical notation be used
 763             // only with `Fn()` etc.
 764             if !this.tcx().sess.features.borrow().unboxed_closures && trait_def.paren_sugar {
 765                 span_err!(this.tcx().sess, span, E0215,
 766                                          "angle-bracket notation is not stable when \
 767                                          used with the `Fn` family of traits, use parentheses");
 768                 fileline_help!(this.tcx().sess, span,
 769                            "add `#![feature(unboxed_closures)]` to \
 770                             the crate attributes to enable");
 771             }
 772
 773             convert_angle_bracketed_parameters(this, rscope, span, &trait_def.generics, data)
 774         }
 775         ast::ParenthesizedParameters(ref data) => {
 776             // For now, require that parenthetical notation be used
 777             // only with `Fn()` etc.
 778             if !this.tcx().sess.features.borrow().unboxed_closures && !trait_def.paren_sugar {
 779                 span_err!(this.tcx().sess, span, E0216,
 780                                          "parenthetical notation is only stable when \
 781                                          used with the `Fn` family of traits");
 782                 fileline_help!(this.tcx().sess, span,
 783                            "add `#![feature(unboxed_closures)]` to \
 784                             the crate attributes to enable");
 785             }
 786
 787             convert_parenthesized_parameters(this, rscope, span, &trait_def.generics, data)
 788         }
 789     };
 790
 791     let substs = create_substs_for_ast_path(this,
 792                                             span,
 793                                             param_mode,
 794                                             &trait_def.generics,
 795                                             self_ty,
 796                                             types,
 797                                             regions);
 798
 799     (this.tcx().mk_substs(substs), assoc_bindings)
 800 }
 801
 802 fn ast_type_binding_to_poly_projection_predicate<'tcx>(
 803     this: &AstConv<'tcx>,
 804     mut trait_ref: ty::PolyTraitRef<'tcx>,
 805     self_ty: Option<Ty<'tcx>>,
 806     binding: &ConvertedBinding<'tcx>)
 807     -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
 808 {
 809     let tcx = this.tcx();
 810
 811     // Given something like `U : SomeTrait<T=X>`, we want to produce a
 812     // predicate like `<U as SomeTrait>::T = X`. This is somewhat
 813     // subtle in the event that `T` is defined in a supertrait of
 814     // `SomeTrait`, because in that case we need to upcast.
 815     //
 816     // That is, consider this case:
 817     //
 818     // ```
 819     // trait SubTrait : SuperTrait<int> { }
 820     // trait SuperTrait<A> { type T; }
 821     //
 822     // ... B : SubTrait<T=foo> ...
 823     // ```
 824     //
 825     // We want to produce `<B as SuperTrait<int>>::T == foo`.
 826
 827     // Simple case: X is defined in the current trait.
 828     if this.trait_defines_associated_type_named(trait_ref.def_id(), binding.item_name) {
 829         return Ok(ty::Binder(ty::ProjectionPredicate {      // <-------------------+
 830             projection_ty: ty::ProjectionTy {               //                     |
 831                 trait_ref: trait_ref.skip_binder().clone(), // Binder moved here --+
 832                 item_name: binding.item_name,
 833             },
 834             ty: binding.ty,
 835         }));
 836     }
 837
 838     // Otherwise, we have to walk through the supertraits to find
 839     // those that do.  This is complicated by the fact that, for an
 840     // object type, the `Self` type is not present in the
 841     // substitutions (after all, it's being constructed right now),
 842     // but the `supertraits` iterator really wants one. To handle
 843     // this, we currently insert a dummy type and then remove it
 844     // later. Yuck.
 845
 846     let dummy_self_ty = ty::mk_infer(tcx, ty::FreshTy(0));
 847     if self_ty.is_none() { // if converting for an object type
 848         let mut dummy_substs = trait_ref.skip_binder().substs.clone(); // binder moved here -+
 849         assert!(dummy_substs.self_ty().is_none());                     //                    |
 850         dummy_substs.types.push(SelfSpace, dummy_self_ty);             //                    |
 851         trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_ref.def_id(), // <------------+
 852                                                          tcx.mk_substs(dummy_substs))));
 853     }
 854
 855     try!(this.ensure_super_predicates(binding.span, trait_ref.def_id()));
 856
 857     let mut candidates: Vec<ty::PolyTraitRef> =
 858         traits::supertraits(tcx, trait_ref.clone())
 859         .filter(|r| this.trait_defines_associated_type_named(r.def_id(), binding.item_name))
 860         .collect();
 861
 862     // If converting for an object type, then remove the dummy-ty from `Self` now.
 863     // Yuckety yuck.
 864     if self_ty.is_none() {
 865         for candidate in &mut candidates {
 866             let mut dummy_substs = candidate.0.substs.clone();
 867             assert!(dummy_substs.self_ty() == Some(dummy_self_ty));
 868             dummy_substs.types.pop(SelfSpace);
 869             *candidate = ty::Binder(Rc::new(ty::TraitRef::new(candidate.def_id(),
 870                                                               tcx.mk_substs(dummy_substs))));
 871         }
 872     }
 873
 874     if candidates.len() > 1 {
 875         span_err!(tcx.sess, binding.span, E0217,
 876             "ambiguous associated type: `{}` defined in multiple supertraits `{}`",
 877                     token::get_name(binding.item_name),
 878                     candidates.user_string(tcx));
 879         return Err(ErrorReported);
 880     }
 881
 882     let candidate = match candidates.pop() {
 883         Some(c) => c,
 884         None => {
 885             span_err!(tcx.sess, binding.span, E0218,
 886                 "no associated type `{}` defined in `{}`",
 887                         token::get_name(binding.item_name),
 888                         trait_ref.user_string(tcx));
 889             return Err(ErrorReported);
 890         }
 891     };
 892
 893     Ok(ty::Binder(ty::ProjectionPredicate {             // <-------------------------+
 894         projection_ty: ty::ProjectionTy {               //                           |
 895             trait_ref: candidate.skip_binder().clone(), // binder is moved up here --+
 896             item_name: binding.item_name,
 897         },
 898         ty: binding.ty,
 899     }))
 900 }
 901
 902 fn ast_path_to_ty<'tcx>(
 903     this: &AstConv<'tcx>,
 904     rscope: &RegionScope,
 905     span: Span,
 906     param_mode: PathParamMode,
 907     did: ast::DefId,
 908     item_segment: &ast::PathSegment)
 909     -> Ty<'tcx>
 910 {
 911     let tcx = this.tcx();
 912     let (generics, decl_ty) = match this.get_item_type_scheme(span, did) {
 913         Ok(ty::TypeScheme { generics,  ty: decl_ty }) => {
 914             (generics, decl_ty)
 915         }
 916         Err(ErrorReported) => {
 917             return tcx.types.err;
 918         }
 919     };
 920
 921     let substs = ast_path_substs_for_ty(this,
 922                                         rscope,
 923                                         span,
 924                                         param_mode,
 925                                         &generics,
 926                                         item_segment);
 927
 928     // FIXME(#12938): This is a hack until we have full support for DST.
 929     if Some(did) == this.tcx().lang_items.owned_box() {
 930         assert_eq!(substs.types.len(TypeSpace), 1);
 931         return ty::mk_uniq(this.tcx(), *substs.types.get(TypeSpace, 0));
 932     }
 933
 934     decl_ty.subst(this.tcx(), &substs)
 935 }
 936
 937 type TraitAndProjections<'tcx> = (ty::PolyTraitRef<'tcx>, Vec<ty::PolyProjectionPredicate<'tcx>>);
 938
 939 fn ast_ty_to_trait_ref<'tcx>(this: &AstConv<'tcx>,
 940                              rscope: &RegionScope,
 941                              ty: &ast::Ty,
 942                              bounds: &[ast::TyParamBound])
 943                              -> Result<TraitAndProjections<'tcx>, ErrorReported>
 944 {
 945     /*!
 946      * In a type like `Foo + Send`, we want to wait to collect the
 947      * full set of bounds before we make the object type, because we
 948      * need them to infer a region bound.  (For example, if we tried
 949      * made a type from just `Foo`, then it wouldn't be enough to
 950      * infer a 'static bound, and hence the user would get an error.)
 951      * So this function is used when we're dealing with a sum type to
 952      * convert the LHS. It only accepts a type that refers to a trait
 953      * name, and reports an error otherwise.
 954      */
 955
 956     match ty.node {
 957         ast::TyPath(None, ref path) => {
 958             let def = match this.tcx().def_map.borrow().get(&ty.id) {
 959                 Some(&def::PathResolution { base_def, depth: 0, .. }) => Some(base_def),
 960                 _ => None
 961             };
 962             match def {
 963                 Some(def::DefTrait(trait_def_id)) => {
 964                     let mut projection_bounds = Vec::new();
 965                     let trait_ref = object_path_to_poly_trait_ref(this,
 966                                                                   rscope,
 967                                                                   path.span,
 968                                                                   PathParamMode::Explicit,
 969                                                                   trait_def_id,
 970                                                                   path.segments.last().unwrap(),
 971                                                                   &mut projection_bounds);
 972                     Ok((trait_ref, projection_bounds))
 973                 }
 974                 _ => {
 975                     span_err!(this.tcx().sess, ty.span, E0172, "expected a reference to a trait");
 976                     Err(ErrorReported)
 977                 }
 978             }
 979         }
 980         _ => {
 981             span_err!(this.tcx().sess, ty.span, E0178,
 982                       "expected a path on the left-hand side of `+`, not `{}`",
 983                       pprust::ty_to_string(ty));
 984             match ty.node {
 985                 ast::TyRptr(None, ref mut_ty) => {
 986                     fileline_help!(this.tcx().sess, ty.span,
 987                                "perhaps you meant `&{}({} +{})`? (per RFC 438)",
 988                                ppaux::mutability_to_string(mut_ty.mutbl),
 989                                pprust::ty_to_string(&*mut_ty.ty),
 990                                pprust::bounds_to_string(bounds));
 991                 }
 992                ast::TyRptr(Some(ref lt), ref mut_ty) => {
 993                     fileline_help!(this.tcx().sess, ty.span,
 994                                "perhaps you meant `&{} {}({} +{})`? (per RFC 438)",
 995                                pprust::lifetime_to_string(lt),
 996                                ppaux::mutability_to_string(mut_ty.mutbl),
 997                                pprust::ty_to_string(&*mut_ty.ty),
 998                                pprust::bounds_to_string(bounds));
 999                 }
1000
1001                 _ => {
1002                     fileline_help!(this.tcx().sess, ty.span,
1003                                "perhaps you forgot parentheses? (per RFC 438)");
1004                 }
1005             }
1006             Err(ErrorReported)
1007         }
1008     }
1009 }
1010
1011 fn trait_ref_to_object_type<'tcx>(this: &AstConv<'tcx>,
1012                                   rscope: &RegionScope,
1013                                   span: Span,
1014                                   trait_ref: ty::PolyTraitRef<'tcx>,
1015                                   projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
1016                                   bounds: &[ast::TyParamBound])
1017                                   -> Ty<'tcx>
1018 {
1019     let existential_bounds = conv_existential_bounds(this,
1020                                                      rscope,
1021                                                      span,
1022                                                      trait_ref.clone(),
1023                                                      projection_bounds,
1024                                                      bounds);
1025
1026     let result = ty::mk_trait(this.tcx(), trait_ref, existential_bounds);
1027     debug!("trait_ref_to_object_type: result={}",
1028            result.repr(this.tcx()));
1029
1030     result
1031 }
1032
1033 fn report_ambiguous_associated_type(tcx: &ty::ctxt,
1034                                     span: Span,
1035                                     type_str: &str,
1036                                     trait_str: &str,
1037                                     name: &str) {
1038     span_err!(tcx.sess, span, E0223,
1039               "ambiguous associated type; specify the type using the syntax \
1040                `<{} as {}>::{}`",
1041               type_str, trait_str, name);
1042 }
1043
1044 // Create a type from a a path to an associated type.
1045 // For a path A::B::C::D, ty and ty_path_def are the type and def for A::B::C
1046 // and item_segment is the path segment for D. We return a type and a def for
1047 // the whole path.
1048 // Will fail except for T::A and Self::A; i.e., if ty/ty_path_def are not a type
1049 // parameter or Self.
1050 fn associated_path_def_to_ty<'tcx>(this: &AstConv<'tcx>,
1051                                    span: Span,
1052                                    ty: Ty<'tcx>,
1053                                    ty_path_def: def::Def,
1054                                    item_segment: &ast::PathSegment)
1055                                    -> (Ty<'tcx>, def::Def)
1056 {
1057     let tcx = this.tcx();
1058     let assoc_name = item_segment.identifier.name;
1059
1060     debug!("associated_path_def_to_ty: {}::{}", ty.repr(tcx), token::get_name(assoc_name));
1061
1062     check_path_args(tcx, slice::ref_slice(item_segment), NO_TPS | NO_REGIONS);
1063
1064     // Check that the path prefix given by ty/ty_path_def is a type parameter/Self.
1065     match (&ty.sty, ty_path_def) {
1066         (&ty::ty_param(_), def::DefTyParam(..)) |
1067         (&ty::ty_param(_), def::DefSelfTy(_)) => {}
1068         _ => {
1069             report_ambiguous_associated_type(tcx,
1070                                              span,
1071                                              &ty.user_string(tcx),
1072                                              "Trait",
1073                                              &token::get_name(assoc_name));
1074             return (tcx.types.err, ty_path_def);
1075         }
1076     }
1077
1078     let ty_param_node_id = ty_path_def.local_node_id();
1079     let ty_param_name = tcx.ty_param_defs.borrow().get(&ty_param_node_id).unwrap().name;
1080
1081     let bounds = match this.get_type_parameter_bounds(span, ty_param_node_id) {
1082         Ok(v) => v,
1083         Err(ErrorReported) => {
1084             return (tcx.types.err, ty_path_def);
1085         }
1086     };
1087
1088     // Ensure the super predicates and stop if we encountered an error.
1089     if bounds.iter().any(|b| this.ensure_super_predicates(span, b.def_id()).is_err()) {
1090         return (this.tcx().types.err, ty_path_def);
1091     }
1092
1093     // Check that there is exactly one way to find an associated type with the
1094     // correct name.
1095     let mut suitable_bounds: Vec<_> =
1096         traits::transitive_bounds(tcx, &bounds)
1097         .filter(|b| this.trait_defines_associated_type_named(b.def_id(), assoc_name))
1098         .collect();
1099
1100     if suitable_bounds.len() == 0 {
1101         span_err!(tcx.sess, span, E0220,
1102                           "associated type `{}` not found for type parameter `{}`",
1103                                   token::get_name(assoc_name),
1104                                   token::get_name(ty_param_name));
1105         return (this.tcx().types.err, ty_path_def);
1106     }
1107
1108     if suitable_bounds.len() > 1 {
1109         span_err!(tcx.sess, span, E0221,
1110                           "ambiguous associated type `{}` in bounds of `{}`",
1111                                   token::get_name(assoc_name),
1112                                   token::get_name(ty_param_name));
1113
1114         for suitable_bound in &suitable_bounds {
1115             span_note!(this.tcx().sess, span,
1116                        "associated type `{}` could derive from `{}`",
1117                        token::get_name(ty_param_name),
1118                        suitable_bound.user_string(this.tcx()));
1119         }
1120     }
1121
1122     let suitable_bound = suitable_bounds.pop().unwrap().clone();
1123     let trait_did = suitable_bound.0.def_id;
1124
1125     let ty = this.projected_ty_from_poly_trait_ref(span, suitable_bound, assoc_name);
1126
1127     let item_did = if trait_did.krate == ast::LOCAL_CRATE {
1128         // `ty::trait_items` used below requires information generated
1129         // by type collection, which may be in progress at this point.
1130         match this.tcx().map.expect_item(trait_did.node).node {
1131             ast::ItemTrait(_, _, _, ref trait_items) => {
1132                 let item = trait_items.iter()
1133                                       .find(|i| i.ident.name == assoc_name)
1134                                       .expect("missing associated type");
1135                 ast_util::local_def(item.id)
1136             }
1137             _ => unreachable!()
1138         }
1139     } else {
1140         let trait_items = ty::trait_items(this.tcx(), trait_did);
1141         let item = trait_items.iter().find(|i| i.name() == assoc_name);
1142         item.expect("missing associated type").def_id()
1143     };
1144
1145     (ty, def::DefAssociatedTy(trait_did, item_did))
1146 }
1147
1148 fn qpath_to_ty<'tcx>(this: &AstConv<'tcx>,
1149                      rscope: &RegionScope,
1150                      span: Span,
1151                      param_mode: PathParamMode,
1152                      opt_self_ty: Option<Ty<'tcx>>,
1153                      trait_def_id: ast::DefId,
1154                      trait_segment: &ast::PathSegment,
1155                      item_segment: &ast::PathSegment)
1156                      -> Ty<'tcx>
1157 {
1158     let tcx = this.tcx();
1159
1160     check_path_args(tcx, slice::ref_slice(item_segment), NO_TPS | NO_REGIONS);
1161
1162     let self_ty = if let Some(ty) = opt_self_ty {
1163         ty
1164     } else {
1165         let path_str = ty::item_path_str(tcx, trait_def_id);
1166         report_ambiguous_associated_type(tcx,
1167                                          span,
1168                                          "Type",
1169                                          &path_str,
1170                                          &token::get_ident(item_segment.identifier));
1171         return tcx.types.err;
1172     };
1173
1174     debug!("qpath_to_ty: self_type={}", self_ty.repr(tcx));
1175
1176     let trait_ref =
1177         ast_path_to_mono_trait_ref(this,
1178                                    rscope,
1179                                    span,
1180                                    param_mode,
1181                                    trait_def_id,
1182                                    Some(self_ty),
1183                                    trait_segment);
1184
1185     debug!("qpath_to_ty: trait_ref={}", trait_ref.repr(tcx));
1186
1187     this.projected_ty(span, trait_ref, item_segment.identifier.name)
1188 }
1189
1190 /// Convert a type supplied as value for a type argument from AST into our
1191 /// our internal representation. This is the same as `ast_ty_to_ty` but that
1192 /// it applies the object lifetime default.
1193 ///
1194 /// # Parameters
1195 ///
1196 /// * `this`, `rscope`: the surrounding context
1197 /// * `decl_generics`: the generics of the struct/enum/trait declaration being
1198 ///   referenced
1199 /// * `index`: the index of the type parameter being instantiated from the list
1200 ///   (we assume it is in the `TypeSpace`)
1201 /// * `region_substs`: a partial substitution consisting of
1202 ///   only the region type parameters being supplied to this type.
1203 /// * `ast_ty`: the ast representation of the type being supplied
1204 pub fn ast_ty_arg_to_ty<'tcx>(this: &AstConv<'tcx>,
1205                               rscope: &RegionScope,
1206                               decl_generics: &ty::Generics<'tcx>,
1207                               index: usize,
1208                               region_substs: &Substs<'tcx>,
1209                               ast_ty: &ast::Ty)
1210                               -> Ty<'tcx>
1211 {
1212     let tcx = this.tcx();
1213
1214     if let Some(def) = decl_generics.types.opt_get(TypeSpace, index) {
1215         let object_lifetime_default = def.object_lifetime_default.subst(tcx, region_substs);
1216         let rscope1 = &ObjectLifetimeDefaultRscope::new(rscope, object_lifetime_default);
1217         ast_ty_to_ty(this, rscope1, ast_ty)
1218     } else {
1219         ast_ty_to_ty(this, rscope, ast_ty)
1220     }
1221 }
1222
1223 // Note that both base_segments and assoc_segments may be empty, although not at
1224 // the same time.
1225 pub fn finish_resolving_def_to_ty<'tcx>(this: &AstConv<'tcx>,
1226                                         rscope: &RegionScope,
1227                                         span: Span,
1228                                         param_mode: PathParamMode,
1229                                         def: &def::Def,
1230                                         opt_self_ty: Option<Ty<'tcx>>,
1231                                         base_segments: &[ast::PathSegment],
1232                                         assoc_segments: &[ast::PathSegment])
1233                                         -> Ty<'tcx> {
1234     let tcx = this.tcx();
1235
1236     let base_ty = match *def {
1237         def::DefTrait(trait_def_id) => {
1238             // N.B. this case overlaps somewhat with
1239             // TyObjectSum, see that fn for details
1240             let mut projection_bounds = Vec::new();
1241
1242             let trait_ref = object_path_to_poly_trait_ref(this,
1243                                                           rscope,
1244                                                           span,
1245                                                           param_mode,
1246                                                           trait_def_id,
1247                                                           base_segments.last().unwrap(),
1248                                                           &mut projection_bounds);
1249
1250             check_path_args(tcx, base_segments.init(), NO_TPS | NO_REGIONS);
1251             trait_ref_to_object_type(this,
1252                                      rscope,
1253                                      span,
1254                                      trait_ref,
1255                                      projection_bounds,
1256                                      &[])
1257         }
1258         def::DefTy(did, _) | def::DefStruct(did) => {
1259             check_path_args(tcx, base_segments.init(), NO_TPS | NO_REGIONS);
1260             ast_path_to_ty(this, rscope, span,
1261                            param_mode, did,
1262                            base_segments.last().unwrap())
1263         }
1264         def::DefTyParam(space, index, _, name) => {
1265             check_path_args(tcx, base_segments, NO_TPS | NO_REGIONS);
1266             ty::mk_param(tcx, space, index, name)
1267         }
1268         def::DefSelfTy(_) => {
1269             // N.b.: resolve guarantees that the this type only appears in a
1270             // trait, which we rely upon in various places when creating
1271             // substs.
1272             check_path_args(tcx, base_segments, NO_TPS | NO_REGIONS);
1273             ty::mk_self_type(tcx)
1274         }
1275         def::DefAssociatedTy(trait_did, _) => {
1276             check_path_args(tcx, &base_segments[..base_segments.len()-2], NO_TPS | NO_REGIONS);
1277             qpath_to_ty(this,
1278                         rscope,
1279                         span,
1280                         param_mode,
1281                         opt_self_ty,
1282                         trait_did,
1283                         &base_segments[base_segments.len()-2],
1284                         base_segments.last().unwrap())
1285         }
1286         def::DefMod(id) => {
1287             // Used as sentinel by callers to indicate the `<T>::A::B::C` form.
1288             // FIXME(#22519) This part of the resolution logic should be
1289             // avoided entirely for that form, once we stop needed a Def
1290             // for `associated_path_def_to_ty`.
1291
1292             if !base_segments.is_empty() {
1293                 span_err!(tcx.sess,
1294                           span,
1295                           E0247,
1296                           "found module name used as a type: {}",
1297                           tcx.map.node_to_string(id.node));
1298                 return this.tcx().types.err;
1299             }
1300
1301             opt_self_ty.expect("missing T in <T>::a::b::c")
1302         }
1303         def::DefPrimTy(prim_ty) => {
1304             prim_ty_to_ty(tcx, base_segments, prim_ty)
1305         }
1306         _ => {
1307             span_err!(tcx.sess, span, E0248,
1308                       "found value name used as a type: {:?}", *def);
1309             return this.tcx().types.err;
1310         }
1311     };
1312
1313     // If any associated type segments remain, attempt to resolve them.
1314     let mut ty = base_ty;
1315     let mut def = *def;
1316     for segment in assoc_segments {
1317         if ty.sty == ty::ty_err {
1318             break;
1319         }
1320         // This is pretty bad (it will fail except for T::A and Self::A).
1321         let (a_ty, a_def) = associated_path_def_to_ty(this,
1322                                                       span,
1323                                                       ty,
1324                                                       def,
1325                                                       segment);
1326         ty = a_ty;
1327         def = a_def;
1328     }
1329     ty
1330 }
1331
1332 /// Parses the programmer's textual representation of a type into our
1333 /// internal notion of a type.
1334 pub fn ast_ty_to_ty<'tcx>(this: &AstConv<'tcx>,
1335                           rscope: &RegionScope,
1336                           ast_ty: &ast::Ty)
1337                           -> Ty<'tcx>
1338 {
1339     debug!("ast_ty_to_ty(ast_ty={})",
1340            ast_ty.repr(this.tcx()));
1341
1342     let tcx = this.tcx();
1343
1344     if let Some(&ty) = tcx.ast_ty_to_ty_cache.borrow().get(&ast_ty.id) {
1345         return ty;
1346     }
1347
1348     let typ = match ast_ty.node {
1349         ast::TyVec(ref ty) => {
1350             ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty), None)
1351         }
1352         ast::TyObjectSum(ref ty, ref bounds) => {
1353             match ast_ty_to_trait_ref(this, rscope, &**ty, bounds) {
1354                 Ok((trait_ref, projection_bounds)) => {
1355                     trait_ref_to_object_type(this,
1356                                              rscope,
1357                                              ast_ty.span,
1358                                              trait_ref,
1359                                              projection_bounds,
1360                                              bounds)
1361                 }
1362                 Err(ErrorReported) => {
1363                     this.tcx().types.err
1364                 }
1365             }
1366         }
1367         ast::TyPtr(ref mt) => {
1368             ty::mk_ptr(tcx, ty::mt {
1369                 ty: ast_ty_to_ty(this, rscope, &*mt.ty),
1370                 mutbl: mt.mutbl
1371             })
1372         }
1373         ast::TyRptr(ref region, ref mt) => {
1374             let r = opt_ast_region_to_region(this, rscope, ast_ty.span, region);
1375             debug!("ty_rptr r={}", r.repr(this.tcx()));
1376             let rscope1 =
1377                 &ObjectLifetimeDefaultRscope::new(
1378                     rscope,
1379                     Some(ty::ObjectLifetimeDefault::Specific(r)));
1380             let t = ast_ty_to_ty(this, rscope1, &*mt.ty);
1381             ty::mk_rptr(tcx, tcx.mk_region(r), ty::mt {ty: t, mutbl: mt.mutbl})
1382         }
1383         ast::TyTup(ref fields) => {
1384             let flds = fields.iter()
1385                              .map(|t| ast_ty_to_ty(this, rscope, &**t))
1386                              .collect();
1387             ty::mk_tup(tcx, flds)
1388         }
1389         ast::TyParen(ref typ) => ast_ty_to_ty(this, rscope, &**typ),
1390         ast::TyBareFn(ref bf) => {
1391             if bf.decl.variadic && bf.abi != abi::C {
1392                 span_err!(tcx.sess, ast_ty.span, E0222,
1393                           "variadic function must have C calling convention");
1394             }
1395             let bare_fn = ty_of_bare_fn(this, bf.unsafety, bf.abi, &*bf.decl);
1396             ty::mk_bare_fn(tcx, None, tcx.mk_bare_fn(bare_fn))
1397         }
1398         ast::TyPolyTraitRef(ref bounds) => {
1399             conv_ty_poly_trait_ref(this, rscope, ast_ty.span, bounds)
1400         }
1401         ast::TyPath(ref maybe_qself, ref path) => {
1402             let path_res = if let Some(&d) = tcx.def_map.borrow().get(&ast_ty.id) {
1403                 d
1404             } else if let Some(ast::QSelf { position: 0, .. }) = *maybe_qself {
1405                 // Create some fake resolution that can't possibly be a type.
1406                 def::PathResolution {
1407                     base_def: def::DefMod(ast_util::local_def(ast::CRATE_NODE_ID)),
1408                     last_private: LastMod(AllPublic),
1409                     depth: path.segments.len()
1410                 }
1411             } else {
1412                 tcx.sess.span_bug(ast_ty.span,
1413                                   &format!("unbound path {}", ast_ty.repr(tcx)))
1414             };
1415             let def = path_res.base_def;
1416             let base_ty_end = path.segments.len() - path_res.depth;
1417             let opt_self_ty = maybe_qself.as_ref().map(|qself| {
1418                 ast_ty_to_ty(this, rscope, &qself.ty)
1419             });
1420             let ty = finish_resolving_def_to_ty(this,
1421                                                 rscope,
1422                                                 ast_ty.span,
1423                                                 PathParamMode::Explicit,
1424                                                 &def,
1425                                                 opt_self_ty,
1426                                                 &path.segments[..base_ty_end],
1427                                                 &path.segments[base_ty_end..]);
1428
1429             if path_res.depth != 0 && ty.sty != ty::ty_err {
1430                 // Write back the new resolution.
1431                 tcx.def_map.borrow_mut().insert(ast_ty.id, def::PathResolution {
1432                     base_def: def,
1433                     last_private: path_res.last_private,
1434                     depth: 0
1435                 });
1436             }
1437
1438             ty
1439         }
1440         ast::TyFixedLengthVec(ref ty, ref e) => {
1441             match const_eval::eval_const_expr_partial(tcx, &**e, Some(tcx.types.usize)) {
1442                 Ok(r) => {
1443                     match r {
1444                         const_eval::const_int(i) =>
1445                             ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1446                                         Some(i as usize)),
1447                         const_eval::const_uint(i) =>
1448                             ty::mk_vec(tcx, ast_ty_to_ty(this, rscope, &**ty),
1449                                         Some(i as usize)),
1450                         _ => {
1451                             span_err!(tcx.sess, ast_ty.span, E0249,
1452                                       "expected constant expr for array length");
1453                             this.tcx().types.err
1454                         }
1455                     }
1456                 }
1457                 Err(ref r) => {
1458                     let subspan  =
1459                         ast_ty.span.lo <= r.span.lo && r.span.hi <= ast_ty.span.hi;
1460                     span_err!(tcx.sess, r.span, E0250,
1461                               "array length constant evaluation error: {}",
1462                               r.description());
1463                     if !subspan {
1464                         span_note!(tcx.sess, ast_ty.span, "for array length here")
1465                     }
1466                     this.tcx().types.err
1467                 }
1468             }
1469         }
1470         ast::TyTypeof(ref _e) => {
1471             tcx.sess.span_bug(ast_ty.span, "typeof is reserved but unimplemented");
1472         }
1473         ast::TyInfer => {
1474             // TyInfer also appears as the type of arguments or return
1475             // values in a ExprClosure, or as
1476             // the type of local variables. Both of these cases are
1477             // handled specially and will not descend into this routine.
1478             this.ty_infer(ast_ty.span)
1479         }
1480     };
1481
1482     tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, typ);
1483     return typ;
1484 }
1485
1486 pub fn ty_of_arg<'tcx>(this: &AstConv<'tcx>,
1487                        rscope: &RegionScope,
1488                        a: &ast::Arg,
1489                        expected_ty: Option<Ty<'tcx>>)
1490                        -> Ty<'tcx>
1491 {
1492     match a.ty.node {
1493         ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
1494         ast::TyInfer => this.ty_infer(a.ty.span),
1495         _ => ast_ty_to_ty(this, rscope, &*a.ty),
1496     }
1497 }
1498
1499 struct SelfInfo<'a, 'tcx> {
1500     untransformed_self_ty: Ty<'tcx>,
1501     explicit_self: &'a ast::ExplicitSelf,
1502 }
1503
1504 pub fn ty_of_method<'tcx>(this: &AstConv<'tcx>,
1505                           sig: &ast::MethodSig,
1506                           untransformed_self_ty: Ty<'tcx>)
1507                           -> (ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory) {
1508     let self_info = Some(SelfInfo {
1509         untransformed_self_ty: untransformed_self_ty,
1510         explicit_self: &sig.explicit_self,
1511     });
1512     let (bare_fn_ty, optional_explicit_self_category) =
1513         ty_of_method_or_bare_fn(this,
1514                                 sig.unsafety,
1515                                 sig.abi,
1516                                 self_info,
1517                                 &sig.decl);
1518     (bare_fn_ty, optional_explicit_self_category.unwrap())
1519 }
1520
1521 pub fn ty_of_bare_fn<'tcx>(this: &AstConv<'tcx>, unsafety: ast::Unsafety, abi: abi::Abi,
1522                                               decl: &ast::FnDecl) -> ty::BareFnTy<'tcx> {
1523     let (bare_fn_ty, _) = ty_of_method_or_bare_fn(this, unsafety, abi, None, decl);
1524     bare_fn_ty
1525 }
1526
1527 fn ty_of_method_or_bare_fn<'a, 'tcx>(this: &AstConv<'tcx>,
1528                                      unsafety: ast::Unsafety,
1529                                      abi: abi::Abi,
1530                                      opt_self_info: Option<SelfInfo<'a, 'tcx>>,
1531                                      decl: &ast::FnDecl)
1532                                      -> (ty::BareFnTy<'tcx>, Option<ty::ExplicitSelfCategory>)
1533 {
1534     debug!("ty_of_method_or_bare_fn");
1535
1536     // New region names that appear inside of the arguments of the function
1537     // declaration are bound to that function type.
1538     let rb = rscope::BindingRscope::new();
1539
1540     // `implied_output_region` is the region that will be assumed for any
1541     // region parameters in the return type. In accordance with the rules for
1542     // lifetime elision, we can determine it in two ways. First (determined
1543     // here), if self is by-reference, then the implied output region is the
1544     // region of the self parameter.
1545     let mut explicit_self_category_result = None;
1546     let (self_ty, mut implied_output_region) = match opt_self_info {
1547         None => (None, None),
1548         Some(self_info) => {
1549             // This type comes from an impl or trait; no late-bound
1550             // regions should be present.
1551             assert!(!self_info.untransformed_self_ty.has_escaping_regions());
1552
1553             // Figure out and record the explicit self category.
1554             let explicit_self_category =
1555                 determine_explicit_self_category(this, &rb, &self_info);
1556             explicit_self_category_result = Some(explicit_self_category);
1557             match explicit_self_category {
1558                 ty::StaticExplicitSelfCategory => {
1559                     (None, None)
1560                 }
1561                 ty::ByValueExplicitSelfCategory => {
1562                     (Some(self_info.untransformed_self_ty), None)
1563                 }
1564                 ty::ByReferenceExplicitSelfCategory(region, mutability) => {
1565                     (Some(ty::mk_rptr(this.tcx(),
1566                                       this.tcx().mk_region(region),
1567                                       ty::mt {
1568                                         ty: self_info.untransformed_self_ty,
1569                                         mutbl: mutability
1570                                       })),
1571                      Some(region))
1572                 }
1573                 ty::ByBoxExplicitSelfCategory => {
1574                     (Some(ty::mk_uniq(this.tcx(), self_info.untransformed_self_ty)), None)
1575                 }
1576             }
1577         }
1578     };
1579
1580     // HACK(eddyb) replace the fake self type in the AST with the actual type.
1581     let input_params = if self_ty.is_some() {
1582         &decl.inputs[1..]
1583     } else {
1584         &decl.inputs[..]
1585     };
1586     let input_tys = input_params.iter().map(|a| ty_of_arg(this, &rb, a, None));
1587     let input_pats: Vec<String> = input_params.iter()
1588                                               .map(|a| pprust::pat_to_string(&*a.pat))
1589                                               .collect();
1590     let self_and_input_tys: Vec<Ty> =
1591         self_ty.into_iter().chain(input_tys).collect();
1592
1593
1594     // Second, if there was exactly one lifetime (either a substitution or a
1595     // reference) in the arguments, then any anonymous regions in the output
1596     // have that lifetime.
1597     let lifetimes_for_params = if implied_output_region.is_none() {
1598         let input_tys = if self_ty.is_some() {
1599             // Skip the first argument if `self` is present.
1600             &self_and_input_tys[1..]
1601         } else {
1602             &self_and_input_tys[..]
1603         };
1604
1605         let (ior, lfp) = find_implied_output_region(input_tys, input_pats);
1606         implied_output_region = ior;
1607         lfp
1608     } else {
1609         vec![]
1610     };
1611
1612     let output_ty = match decl.output {
1613         ast::Return(ref output) if output.node == ast::TyInfer =>
1614             ty::FnConverging(this.ty_infer(output.span)),
1615         ast::Return(ref output) =>
1616             ty::FnConverging(convert_ty_with_lifetime_elision(this,
1617                                                               implied_output_region,
1618                                                               lifetimes_for_params,
1619                                                               &**output)),
1620         ast::DefaultReturn(..) => ty::FnConverging(ty::mk_nil(this.tcx())),
1621         ast::NoReturn(..) => ty::FnDiverging
1622     };
1623
1624     (ty::BareFnTy {
1625         unsafety: unsafety,
1626         abi: abi,
1627         sig: ty::Binder(ty::FnSig {
1628             inputs: self_and_input_tys,
1629             output: output_ty,
1630             variadic: decl.variadic
1631         }),
1632     }, explicit_self_category_result)
1633 }
1634
1635 fn determine_explicit_self_category<'a, 'tcx>(this: &AstConv<'tcx>,
1636                                               rscope: &RegionScope,
1637                                               self_info: &SelfInfo<'a, 'tcx>)
1638                                               -> ty::ExplicitSelfCategory
1639 {
1640     return match self_info.explicit_self.node {
1641         ast::SelfStatic => ty::StaticExplicitSelfCategory,
1642         ast::SelfValue(_) => ty::ByValueExplicitSelfCategory,
1643         ast::SelfRegion(ref lifetime, mutability, _) => {
1644             let region =
1645                 opt_ast_region_to_region(this,
1646                                          rscope,
1647                                          self_info.explicit_self.span,
1648                                          lifetime);
1649             ty::ByReferenceExplicitSelfCategory(region, mutability)
1650         }
1651         ast::SelfExplicit(ref ast_type, _) => {
1652             let explicit_type = ast_ty_to_ty(this, rscope, &**ast_type);
1653
1654             // We wish to (for now) categorize an explicit self
1655             // declaration like `self: SomeType` into either `self`,
1656             // `&self`, `&mut self`, or `Box<self>`. We do this here
1657             // by some simple pattern matching. A more precise check
1658             // is done later in `check_method_self_type()`.
1659             //
1660             // Examples:
1661             //
1662             // ```
1663             // impl Foo for &T {
1664             //     // Legal declarations:
1665             //     fn method1(self: &&T); // ByReferenceExplicitSelfCategory
1666             //     fn method2(self: &T); // ByValueExplicitSelfCategory
1667             //     fn method3(self: Box<&T>); // ByBoxExplicitSelfCategory
1668             //
1669             //     // Invalid cases will be caught later by `check_method_self_type`:
1670             //     fn method_err1(self: &mut T); // ByReferenceExplicitSelfCategory
1671             // }
1672             // ```
1673             //
1674             // To do the check we just count the number of "modifiers"
1675             // on each type and compare them. If they are the same or
1676             // the impl has more, we call it "by value". Otherwise, we
1677             // look at the outermost modifier on the method decl and
1678             // call it by-ref, by-box as appropriate. For method1, for
1679             // example, the impl type has one modifier, but the method
1680             // type has two, so we end up with
1681             // ByReferenceExplicitSelfCategory.
1682
1683             let impl_modifiers = count_modifiers(self_info.untransformed_self_ty);
1684             let method_modifiers = count_modifiers(explicit_type);
1685
1686             debug!("determine_explicit_self_category(self_info.untransformed_self_ty={} \
1687                    explicit_type={} \
1688                    modifiers=({},{})",
1689                    self_info.untransformed_self_ty.repr(this.tcx()),
1690                    explicit_type.repr(this.tcx()),
1691                    impl_modifiers,
1692                    method_modifiers);
1693
1694             if impl_modifiers >= method_modifiers {
1695                 ty::ByValueExplicitSelfCategory
1696             } else {
1697                 match explicit_type.sty {
1698                     ty::ty_rptr(r, mt) => ty::ByReferenceExplicitSelfCategory(*r, mt.mutbl),
1699                     ty::ty_uniq(_) => ty::ByBoxExplicitSelfCategory,
1700                     _ => ty::ByValueExplicitSelfCategory,
1701                 }
1702             }
1703         }
1704     };
1705
1706     fn count_modifiers(ty: Ty) -> usize {
1707         match ty.sty {
1708             ty::ty_rptr(_, mt) => count_modifiers(mt.ty) + 1,
1709             ty::ty_uniq(t) => count_modifiers(t) + 1,
1710             _ => 0,
1711         }
1712     }
1713 }
1714
1715 pub fn ty_of_closure<'tcx>(
1716     this: &AstConv<'tcx>,
1717     unsafety: ast::Unsafety,
1718     decl: &ast::FnDecl,
1719     abi: abi::Abi,
1720     expected_sig: Option<ty::FnSig<'tcx>>)
1721     -> ty::ClosureTy<'tcx>
1722 {
1723     debug!("ty_of_closure(expected_sig={})",
1724            expected_sig.repr(this.tcx()));
1725
1726     // new region names that appear inside of the fn decl are bound to
1727     // that function type
1728     let rb = rscope::BindingRscope::new();
1729
1730     let input_tys: Vec<_> = decl.inputs.iter().enumerate().map(|(i, a)| {
1731         let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1732             // no guarantee that the correct number of expected args
1733             // were supplied
1734             if i < e.inputs.len() {
1735                 Some(e.inputs[i])
1736             } else {
1737                 None
1738             }
1739         });
1740         ty_of_arg(this, &rb, a, expected_arg_ty)
1741     }).collect();
1742
1743     let expected_ret_ty = expected_sig.map(|e| e.output);
1744
1745     let is_infer = match decl.output {
1746         ast::Return(ref output) if output.node == ast::TyInfer => true,
1747         ast::DefaultReturn(..) => true,
1748         _ => false
1749     };
1750
1751     let output_ty = match decl.output {
1752         _ if is_infer && expected_ret_ty.is_some() =>
1753             expected_ret_ty.unwrap(),
1754         _ if is_infer =>
1755             ty::FnConverging(this.ty_infer(decl.output.span())),
1756         ast::Return(ref output) =>
1757             ty::FnConverging(ast_ty_to_ty(this, &rb, &**output)),
1758         ast::DefaultReturn(..) => unreachable!(),
1759         ast::NoReturn(..) => ty::FnDiverging
1760     };
1761
1762     debug!("ty_of_closure: input_tys={}", input_tys.repr(this.tcx()));
1763     debug!("ty_of_closure: output_ty={}", output_ty.repr(this.tcx()));
1764
1765     ty::ClosureTy {
1766         unsafety: unsafety,
1767         abi: abi,
1768         sig: ty::Binder(ty::FnSig {inputs: input_tys,
1769                                    output: output_ty,
1770                                    variadic: decl.variadic}),
1771     }
1772 }
1773
1774 /// Given an existential type like `Foo+'a+Bar`, this routine converts the `'a` and `Bar` intos an
1775 /// `ExistentialBounds` struct. The `main_trait_refs` argument specifies the `Foo` -- it is absent
1776 /// for closures. Eventually this should all be normalized, I think, so that there is no "main
1777 /// trait ref" and instead we just have a flat list of bounds as the existential type.
1778 fn conv_existential_bounds<'tcx>(
1779     this: &AstConv<'tcx>,
1780     rscope: &RegionScope,
1781     span: Span,
1782     principal_trait_ref: ty::PolyTraitRef<'tcx>,
1783     projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
1784     ast_bounds: &[ast::TyParamBound])
1785     -> ty::ExistentialBounds<'tcx>
1786 {
1787     let partitioned_bounds =
1788         partition_bounds(this.tcx(), span, ast_bounds);
1789
1790     conv_existential_bounds_from_partitioned_bounds(
1791         this, rscope, span, principal_trait_ref, projection_bounds, partitioned_bounds)
1792 }
1793
1794 fn conv_ty_poly_trait_ref<'tcx>(
1795     this: &AstConv<'tcx>,
1796     rscope: &RegionScope,
1797     span: Span,
1798     ast_bounds: &[ast::TyParamBound])
1799     -> Ty<'tcx>
1800 {
1801     let mut partitioned_bounds = partition_bounds(this.tcx(), span, &ast_bounds[..]);
1802
1803     let mut projection_bounds = Vec::new();
1804     let main_trait_bound = if !partitioned_bounds.trait_bounds.is_empty() {
1805         let trait_bound = partitioned_bounds.trait_bounds.remove(0);
1806         instantiate_poly_trait_ref(this,
1807                                    rscope,
1808                                    trait_bound,
1809                                    None,
1810                                    &mut projection_bounds)
1811     } else {
1812         span_err!(this.tcx().sess, span, E0224,
1813                   "at least one non-builtin trait is required for an object type");
1814         return this.tcx().types.err;
1815     };
1816
1817     let bounds =
1818         conv_existential_bounds_from_partitioned_bounds(this,
1819                                                         rscope,
1820                                                         span,
1821                                                         main_trait_bound.clone(),
1822                                                         projection_bounds,
1823                                                         partitioned_bounds);
1824
1825     ty::mk_trait(this.tcx(), main_trait_bound, bounds)
1826 }
1827
1828 pub fn conv_existential_bounds_from_partitioned_bounds<'tcx>(
1829     this: &AstConv<'tcx>,
1830     rscope: &RegionScope,
1831     span: Span,
1832     principal_trait_ref: ty::PolyTraitRef<'tcx>,
1833     mut projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>, // Empty for boxed closures
1834     partitioned_bounds: PartitionedBounds)
1835     -> ty::ExistentialBounds<'tcx>
1836 {
1837     let PartitionedBounds { builtin_bounds,
1838                             trait_bounds,
1839                             region_bounds } =
1840         partitioned_bounds;
1841
1842     if !trait_bounds.is_empty() {
1843         let b = &trait_bounds[0];
1844         span_err!(this.tcx().sess, b.trait_ref.path.span, E0225,
1845                   "only the builtin traits can be used as closure or object bounds");
1846     }
1847
1848     let region_bound = compute_object_lifetime_bound(this,
1849                                                      rscope,
1850                                                      span,
1851                                                      &region_bounds,
1852                                                      principal_trait_ref,
1853                                                      builtin_bounds);
1854
1855     ty::sort_bounds_list(&mut projection_bounds);
1856
1857     ty::ExistentialBounds {
1858         region_bound: region_bound,
1859         builtin_bounds: builtin_bounds,
1860         projection_bounds: projection_bounds,
1861     }
1862 }
1863
1864 /// Given the bounds on an object, determines what single region bound
1865 /// (if any) we can use to summarize this type. The basic idea is that we will use the bound the
1866 /// user provided, if they provided one, and otherwise search the supertypes of trait bounds for
1867 /// region bounds. It may be that we can derive no bound at all, in which case we return `None`.
1868 fn compute_object_lifetime_bound<'tcx>(
1869     this: &AstConv<'tcx>,
1870     rscope: &RegionScope,
1871     span: Span,
1872     explicit_region_bounds: &[&ast::Lifetime],
1873     principal_trait_ref: ty::PolyTraitRef<'tcx>,
1874     builtin_bounds: ty::BuiltinBounds)
1875     -> ty::Region
1876 {
1877     let tcx = this.tcx();
1878
1879     debug!("compute_opt_region_bound(explicit_region_bounds={:?}, \
1880            principal_trait_ref={}, builtin_bounds={})",
1881            explicit_region_bounds,
1882            principal_trait_ref.repr(tcx),
1883            builtin_bounds.repr(tcx));
1884
1885     if explicit_region_bounds.len() > 1 {
1886         span_err!(tcx.sess, explicit_region_bounds[1].span, E0226,
1887             "only a single explicit lifetime bound is permitted");
1888     }
1889
1890     if explicit_region_bounds.len() != 0 {
1891         // Explicitly specified region bound. Use that.
1892         let r = explicit_region_bounds[0];
1893         return ast_region_to_region(tcx, r);
1894     }
1895
1896     if let Err(ErrorReported) = this.ensure_super_predicates(span,principal_trait_ref.def_id()) {
1897         return ty::ReStatic;
1898     }
1899
1900     // No explicit region bound specified. Therefore, examine trait
1901     // bounds and see if we can derive region bounds from those.
1902     let derived_region_bounds =
1903         object_region_bounds(tcx, &principal_trait_ref, builtin_bounds);
1904
1905     // If there are no derived region bounds, then report back that we
1906     // can find no region bound.
1907     if derived_region_bounds.len() == 0 {
1908         match rscope.object_lifetime_default(span) {
1909             Some(r) => { return r; }
1910             None => {
1911                 span_err!(this.tcx().sess, span, E0228,
1912                           "the lifetime bound for this object type cannot be deduced \
1913                            from context; please supply an explicit bound");
1914                 return ty::ReStatic;
1915             }
1916         }
1917     }
1918
1919     // If any of the derived region bounds are 'static, that is always
1920     // the best choice.
1921     if derived_region_bounds.iter().any(|r| ty::ReStatic == *r) {
1922         return ty::ReStatic;
1923     }
1924
1925     // Determine whether there is exactly one unique region in the set
1926     // of derived region bounds. If so, use that. Otherwise, report an
1927     // error.
1928     let r = derived_region_bounds[0];
1929     if derived_region_bounds[1..].iter().any(|r1| r != *r1) {
1930         span_err!(tcx.sess, span, E0227,
1931                   "ambiguous lifetime bound, explicit lifetime bound required");
1932     }
1933     return r;
1934 }
1935
1936 /// Given an object type like `SomeTrait+Send`, computes the lifetime
1937 /// bounds that must hold on the elided self type. These are derived
1938 /// from the declarations of `SomeTrait`, `Send`, and friends -- if
1939 /// they declare `trait SomeTrait : 'static`, for example, then
1940 /// `'static` would appear in the list. The hard work is done by
1941 /// `ty::required_region_bounds`, see that for more information.
1942 pub fn object_region_bounds<'tcx>(
1943     tcx: &ty::ctxt<'tcx>,
1944     principal: &ty::PolyTraitRef<'tcx>,
1945     others: ty::BuiltinBounds)
1946     -> Vec<ty::Region>
1947 {
1948     // Since we don't actually *know* the self type for an object,
1949     // this "open(err)" serves as a kind of dummy standin -- basically
1950     // a skolemized type.
1951     let open_ty = ty::mk_infer(tcx, ty::FreshTy(0));
1952
1953     // Note that we preserve the overall binding levels here.
1954     assert!(!open_ty.has_escaping_regions());
1955     let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
1956     let trait_refs = vec!(ty::Binder(Rc::new(ty::TraitRef::new(principal.0.def_id, substs))));
1957
1958     let param_bounds = ty::ParamBounds {
1959         region_bounds: Vec::new(),
1960         builtin_bounds: others,
1961         trait_bounds: trait_refs,
1962         projection_bounds: Vec::new(), // not relevant to computing region bounds
1963     };
1964
1965     let predicates = ty::predicates(tcx, open_ty, &param_bounds);
1966     ty::required_region_bounds(tcx, open_ty, predicates)
1967 }
1968
1969 pub struct PartitionedBounds<'a> {
1970     pub builtin_bounds: ty::BuiltinBounds,
1971     pub trait_bounds: Vec<&'a ast::PolyTraitRef>,
1972     pub region_bounds: Vec<&'a ast::Lifetime>,
1973 }
1974
1975 /// Divides a list of bounds from the AST into three groups: builtin bounds (Copy, Sized etc),
1976 /// general trait bounds, and region bounds.
1977 pub fn partition_bounds<'a>(tcx: &ty::ctxt,
1978                             _span: Span,
1979                             ast_bounds: &'a [ast::TyParamBound])
1980                             -> PartitionedBounds<'a>
1981 {
1982     let mut builtin_bounds = ty::empty_builtin_bounds();
1983     let mut region_bounds = Vec::new();
1984     let mut trait_bounds = Vec::new();
1985     for ast_bound in ast_bounds {
1986         match *ast_bound {
1987             ast::TraitTyParamBound(ref b, ast::TraitBoundModifier::None) => {
1988                 match ::lookup_full_def(tcx, b.trait_ref.path.span, b.trait_ref.ref_id) {
1989                     def::DefTrait(trait_did) => {
1990                         if ty::try_add_builtin_trait(tcx,
1991                                                      trait_did,
1992                                                      &mut builtin_bounds) {
1993                             let segments = &b.trait_ref.path.segments;
1994                             let parameters = &segments[segments.len() - 1].parameters;
1995                             if parameters.types().len() > 0 {
1996                                 check_type_argument_count(tcx, b.trait_ref.path.span,
1997                                                           parameters.types().len(), 0, 0);
1998                             }
1999                             if parameters.lifetimes().len() > 0{
2000                                 report_lifetime_number_error(tcx, b.trait_ref.path.span,
2001                                                              parameters.lifetimes().len(), 0);
2002                             }
2003                             continue; // success
2004                         }
2005                     }
2006                     _ => {
2007                         // Not a trait? that's an error, but it'll get
2008                         // reported later.
2009                     }
2010                 }
2011                 trait_bounds.push(b);
2012             }
2013             ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) => {}
2014             ast::RegionTyParamBound(ref l) => {
2015                 region_bounds.push(l);
2016             }
2017         }
2018     }
2019
2020     PartitionedBounds {
2021         builtin_bounds: builtin_bounds,
2022         trait_bounds: trait_bounds,
2023         region_bounds: region_bounds,
2024     }
2025 }
2026
2027 fn prohibit_projections<'tcx>(tcx: &ty::ctxt<'tcx>,
2028                               bindings: &[ConvertedBinding<'tcx>])
2029 {
2030     for binding in bindings.iter().take(1) {
2031         span_err!(tcx.sess, binding.span, E0229,
2032             "associated type bindings are not allowed here");
2033     }
2034 }
2035
2036 fn check_type_argument_count(tcx: &ty::ctxt, span: Span, supplied: usize,
2037                              required: usize, accepted: usize) {
2038     if supplied < required {
2039         let expected = if required < accepted {
2040             "expected at least"
2041         } else {
2042             "expected"
2043         };
2044         span_err!(tcx.sess, span, E0243,
2045                   "wrong number of type arguments: {} {}, found {}",
2046                   expected, required, supplied);
2047     } else if supplied > accepted {
2048         let expected = if required < accepted {
2049             "expected at most"
2050         } else {
2051             "expected"
2052         };
2053         span_err!(tcx.sess, span, E0244,
2054                   "wrong number of type arguments: {} {}, found {}",
2055                   expected,
2056                   accepted,
2057                   supplied);
2058     }
2059 }
2060
2061 fn report_lifetime_number_error(tcx: &ty::ctxt, span: Span, number: usize, expected: usize) {
2062     span_err!(tcx.sess, span, E0107,
2063               "wrong number of lifetime parameters: expected {}, found {}",
2064               expected, number);
2065 }