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 rustc_const_eval::eval_length;
  52 use hir::{self, SelfKind};
  53 use hir::def::{Def, PathResolution};
  54 use hir::def_id::DefId;
  55 use hir::print as pprust;
  56 use middle::resolve_lifetime as rl;
  57 use rustc::lint;
  58 use rustc::ty::subst::{Subst, Substs};
  59 use rustc::traits;
  60 use rustc::ty::{self, Ty, TyCtxt, ToPredicate, TypeFoldable};
  61 use rustc::ty::wf::object_region_bounds;
  62 use rustc_back::slice;
  63 use require_c_abi_if_variadic;
  64 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
  65              ObjectLifetimeDefaultRscope, ShiftedRscope, BindingRscope,
  66              ElisionFailureInfo, ElidedLifetime};
  67 use rscope::{AnonTypeScope, MaybeWithAnonTypes};
  68 use util::common::{ErrorReported, FN_OUTPUT_NAME};
  69 use util::nodemap::{NodeMap, FnvHashSet};
  70
  71 use std::cell::RefCell;
  72 use syntax::{abi, ast};
  73 use syntax::feature_gate::{GateIssue, emit_feature_err};
  74 use syntax::parse::token::{self, keywords};
  75 use syntax_pos::{Span, Pos};
  76 use errors::DiagnosticBuilder;
  77
  78 pub trait AstConv<'gcx, 'tcx> {
  79     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>;
  80
  81     /// A cache used for the result of `ast_ty_to_ty_cache`
  82     fn ast_ty_to_ty_cache(&self) -> &RefCell<NodeMap<Ty<'tcx>>>;
  83
  84     /// Returns the generic type and lifetime parameters for an item.
  85     fn get_generics(&self, span: Span, id: DefId)
  86                     -> Result<&'tcx ty::Generics<'tcx>, ErrorReported>;
  87
  88     /// Identify the type scheme for an item with a type, like a type
  89     /// alias, fn, or struct. This allows you to figure out the set of
  90     /// type parameters defined on the item.
  91     fn get_item_type_scheme(&self, span: Span, id: DefId)
  92                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>;
  93
  94     /// Returns the `TraitDef` for a given trait. This allows you to
  95     /// figure out the set of type parameters defined on the trait.
  96     fn get_trait_def(&self, span: Span, id: DefId)
  97                      -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>;
  98
  99     /// Ensure that the super-predicates for the trait with the given
 100     /// id are available and also for the transitive set of
 101     /// super-predicates.
 102     fn ensure_super_predicates(&self, span: Span, id: DefId)
 103                                -> Result<(), ErrorReported>;
 104
 105     /// Returns the set of bounds in scope for the type parameter with
 106     /// the given id.
 107     fn get_type_parameter_bounds(&self, span: Span, def_id: ast::NodeId)
 108                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>;
 109
 110     /// Returns true if the trait with id `trait_def_id` defines an
 111     /// associated type with the name `name`.
 112     fn trait_defines_associated_type_named(&self, trait_def_id: DefId, name: ast::Name)
 113                                            -> bool;
 114
 115     /// Return an (optional) substitution to convert bound type parameters that
 116     /// are in scope into free ones. This function should only return Some
 117     /// within a fn body.
 118     /// See ParameterEnvironment::free_substs for more information.
 119     fn get_free_substs(&self) -> Option<&Substs<'tcx>>;
 120
 121     /// What type should we use when a type is omitted?
 122     fn ty_infer(&self, span: Span) -> Ty<'tcx>;
 123
 124     /// Same as ty_infer, but with a known type parameter definition.
 125     fn ty_infer_for_def(&self,
 126                         _def: &ty::TypeParameterDef<'tcx>,
 127                         _substs: &Substs<'tcx>,
 128                         span: Span) -> Ty<'tcx> {
 129         self.ty_infer(span)
 130     }
 131
 132     /// Projecting an associated type from a (potentially)
 133     /// higher-ranked trait reference is more complicated, because of
 134     /// the possibility of late-bound regions appearing in the
 135     /// associated type binding. This is not legal in function
 136     /// signatures for that reason. In a function body, we can always
 137     /// handle it because we can use inference variables to remove the
 138     /// late-bound regions.
 139     fn projected_ty_from_poly_trait_ref(&self,
 140                                         span: Span,
 141                                         poly_trait_ref: ty::PolyTraitRef<'tcx>,
 142                                         item_name: ast::Name)
 143                                         -> Ty<'tcx>;
 144
 145     /// Project an associated type from a non-higher-ranked trait reference.
 146     /// This is fairly straightforward and can be accommodated in any context.
 147     fn projected_ty(&self,
 148                     span: Span,
 149                     _trait_ref: ty::TraitRef<'tcx>,
 150                     _item_name: ast::Name)
 151                     -> Ty<'tcx>;
 152
 153     /// Invoked when we encounter an error from some prior pass
 154     /// (e.g. resolve) that is translated into a ty-error. This is
 155     /// used to help suppress derived errors typeck might otherwise
 156     /// report.
 157     fn set_tainted_by_errors(&self);
 158 }
 159
 160 #[derive(PartialEq, Eq)]
 161 pub enum PathParamMode {
 162     // Any path in a type context.
 163     Explicit,
 164     // The `module::Type` in `module::Type::method` in an expression.
 165     Optional
 166 }
 167
 168 struct ConvertedBinding<'tcx> {
 169     item_name: ast::Name,
 170     ty: Ty<'tcx>,
 171     span: Span,
 172 }
 173
 174 type TraitAndProjections<'tcx> = (ty::PolyTraitRef<'tcx>, Vec<ty::PolyProjectionPredicate<'tcx>>);
 175
 176 /// Dummy type used for the `Self` of a `TraitRef` created for converting
 177 /// a trait object, and which gets removed in `ExistentialTraitRef`.
 178 /// This type must not appear anywhere in other converted types.
 179 const TRAIT_OBJECT_DUMMY_SELF: ty::TypeVariants<'static> = ty::TyInfer(ty::FreshTy(0));
 180
 181 pub fn ast_region_to_region(tcx: TyCtxt, lifetime: &hir::Lifetime)
 182                             -> ty::Region {
 183     let r = match tcx.named_region_map.defs.get(&lifetime.id) {
 184         None => {
 185             // should have been recorded by the `resolve_lifetime` pass
 186             span_bug!(lifetime.span, "unresolved lifetime");
 187         }
 188
 189         Some(&rl::DefStaticRegion) => {
 190             ty::ReStatic
 191         }
 192
 193         Some(&rl::DefLateBoundRegion(debruijn, id)) => {
 194             // If this region is declared on a function, it will have
 195             // an entry in `late_bound`, but if it comes from
 196             // `for<'a>` in some type or something, it won't
 197             // necessarily have one. In that case though, we won't be
 198             // changed from late to early bound, so we can just
 199             // substitute false.
 200             let issue_32330 = tcx.named_region_map
 201                                  .late_bound
 202                                  .get(&id)
 203                                  .cloned()
 204                                  .unwrap_or(ty::Issue32330::WontChange);
 205             ty::ReLateBound(debruijn, ty::BrNamed(tcx.map.local_def_id(id),
 206                                                   lifetime.name,
 207                                                   issue_32330))
 208         }
 209
 210         Some(&rl::DefEarlyBoundRegion(index, _)) => {
 211             ty::ReEarlyBound(ty::EarlyBoundRegion {
 212                 index: index,
 213                 name: lifetime.name
 214             })
 215         }
 216
 217         Some(&rl::DefFreeRegion(scope, id)) => {
 218             // As in DefLateBoundRegion above, could be missing for some late-bound
 219             // regions, but also for early-bound regions.
 220             let issue_32330 = tcx.named_region_map
 221                                  .late_bound
 222                                  .get(&id)
 223                                  .cloned()
 224                                  .unwrap_or(ty::Issue32330::WontChange);
 225             ty::ReFree(ty::FreeRegion {
 226                     scope: scope.to_code_extent(&tcx.region_maps),
 227                     bound_region: ty::BrNamed(tcx.map.local_def_id(id),
 228                                               lifetime.name,
 229                                               issue_32330)
 230             })
 231
 232                 // (*) -- not late-bound, won't change
 233         }
 234     };
 235
 236     debug!("ast_region_to_region(lifetime={:?} id={}) yields {:?}",
 237            lifetime,
 238            lifetime.id,
 239            r);
 240
 241     r
 242 }
 243
 244 fn report_elision_failure(
 245     db: &mut DiagnosticBuilder,
 246     params: Vec<ElisionFailureInfo>)
 247 {
 248     let mut m = String::new();
 249     let len = params.len();
 250
 251     let elided_params: Vec<_> = params.into_iter()
 252                                        .filter(|info| info.lifetime_count > 0)
 253                                        .collect();
 254
 255     let elided_len = elided_params.len();
 256
 257     for (i, info) in elided_params.into_iter().enumerate() {
 258         let ElisionFailureInfo {
 259             name, lifetime_count: n, have_bound_regions
 260         } = info;
 261
 262         let help_name = if name.is_empty() {
 263             format!("argument {}", i + 1)
 264         } else {
 265             format!("`{}`", name)
 266         };
 267
 268         m.push_str(&(if n == 1 {
 269             help_name
 270         } else {
 271             format!("one of {}'s {} elided {}lifetimes", help_name, n,
 272                     if have_bound_regions { "free " } else { "" } )
 273         })[..]);
 274
 275         if elided_len == 2 && i == 0 {
 276             m.push_str(" or ");
 277         } else if i + 2 == elided_len {
 278             m.push_str(", or ");
 279         } else if i != elided_len - 1 {
 280             m.push_str(", ");
 281         }
 282
 283     }
 284
 285     if len == 0 {
 286         help!(db,
 287                    "this function's return type contains a borrowed value, but \
 288                     there is no value for it to be borrowed from");
 289         help!(db,
 290                    "consider giving it a 'static lifetime");
 291     } else if elided_len == 0 {
 292         help!(db,
 293                    "this function's return type contains a borrowed value with \
 294                     an elided lifetime, but the lifetime cannot be derived from \
 295                     the arguments");
 296         help!(db,
 297                    "consider giving it an explicit bounded or 'static \
 298                     lifetime");
 299     } else if elided_len == 1 {
 300         help!(db,
 301                    "this function's return type contains a borrowed value, but \
 302                     the signature does not say which {} it is borrowed from",
 303                    m);
 304     } else {
 305         help!(db,
 306                    "this function's return type contains a borrowed value, but \
 307                     the signature does not say whether it is borrowed from {}",
 308                    m);
 309     }
 310 }
 311
 312 impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 313     pub fn opt_ast_region_to_region(&self,
 314         rscope: &RegionScope,
 315         default_span: Span,
 316         opt_lifetime: &Option<hir::Lifetime>) -> ty::Region
 317     {
 318         let r = match *opt_lifetime {
 319             Some(ref lifetime) => {
 320                 ast_region_to_region(self.tcx(), lifetime)
 321             }
 322
 323             None => match rscope.anon_regions(default_span, 1) {
 324                 Ok(rs) => rs[0],
 325                 Err(params) => {
 326                     let ampersand_span = Span { hi: default_span.lo, ..default_span};
 327
 328                     let mut err = struct_span_err!(self.tcx().sess, ampersand_span, E0106,
 329                                                  "missing lifetime specifier");
 330                     err.span_label(ampersand_span, &format!("expected lifetime parameter"));
 331
 332                     if let Some(params) = params {
 333                         report_elision_failure(&mut err, params);
 334                     }
 335                     err.emit();
 336                     ty::ReStatic
 337                 }
 338             }
 339         };
 340
 341         debug!("opt_ast_region_to_region(opt_lifetime={:?}) yields {:?}",
 342                 opt_lifetime,
 343                 r);
 344
 345         r
 346     }
 347
 348     /// Given a path `path` that refers to an item `I` with the declared generics `decl_generics`,
 349     /// returns an appropriate set of substitutions for this particular reference to `I`.
 350     pub fn ast_path_substs_for_ty(&self,
 351         rscope: &RegionScope,
 352         span: Span,
 353         param_mode: PathParamMode,
 354         def_id: DefId,
 355         item_segment: &hir::PathSegment)
 356         -> &'tcx Substs<'tcx>
 357     {
 358         let tcx = self.tcx();
 359
 360         match item_segment.parameters {
 361             hir::AngleBracketedParameters(_) => {}
 362             hir::ParenthesizedParameters(..) => {
 363                 struct_span_err!(tcx.sess, span, E0214,
 364                           "parenthesized parameters may only be used with a trait")
 365                     .span_label(span, &format!("only traits may use parentheses"))
 366                     .emit();
 367
 368                 return Substs::for_item(tcx, def_id, |_, _| {
 369                     ty::ReStatic
 370                 }, |_, _| {
 371                     tcx.types.err
 372                 });
 373             }
 374         }
 375
 376         let (substs, assoc_bindings) =
 377             self.create_substs_for_ast_path(rscope,
 378                                             span,
 379                                             param_mode,
 380                                             def_id,
 381                                             &item_segment.parameters,
 382                                             None);
 383
 384         assoc_bindings.first().map(|b| self.tcx().prohibit_projection(b.span));
 385
 386         substs
 387     }
 388
 389     /// Given the type/region arguments provided to some path (along with
 390     /// an implicit Self, if this is a trait reference) returns the complete
 391     /// set of substitutions. This may involve applying defaulted type parameters.
 392     ///
 393     /// Note that the type listing given here is *exactly* what the user provided.
 394     fn create_substs_for_ast_path(&self,
 395         rscope: &RegionScope,
 396         span: Span,
 397         param_mode: PathParamMode,
 398         def_id: DefId,
 399         parameters: &hir::PathParameters,
 400         self_ty: Option<Ty<'tcx>>)
 401         -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
 402     {
 403         let tcx = self.tcx();
 404
 405         debug!("create_substs_for_ast_path(def_id={:?}, self_ty={:?}, \
 406                parameters={:?})",
 407                def_id, self_ty, parameters);
 408
 409         let (lifetimes, num_types_provided) = match *parameters {
 410             hir::AngleBracketedParameters(ref data) => {
 411                 if param_mode == PathParamMode::Optional && data.types.is_empty() {
 412                     (&data.lifetimes[..], None)
 413                 } else {
 414                     (&data.lifetimes[..], Some(data.types.len()))
 415                 }
 416             }
 417             hir::ParenthesizedParameters(_) => (&[][..], Some(1))
 418         };
 419
 420         // If the type is parameterized by this region, then replace this
 421         // region with the current anon region binding (in other words,
 422         // whatever & would get replaced with).
 423         let decl_generics = match self.get_generics(span, def_id) {
 424             Ok(generics) => generics,
 425             Err(ErrorReported) => {
 426                 // No convenient way to recover from a cycle here. Just bail. Sorry!
 427                 self.tcx().sess.abort_if_errors();
 428                 bug!("ErrorReported returned, but no errors reports?")
 429             }
 430         };
 431         let expected_num_region_params = decl_generics.regions.len();
 432         let supplied_num_region_params = lifetimes.len();
 433         let regions = if expected_num_region_params == supplied_num_region_params {
 434             lifetimes.iter().map(|l| ast_region_to_region(tcx, l)).collect()
 435         } else {
 436             let anon_regions =
 437                 rscope.anon_regions(span, expected_num_region_params);
 438
 439             if supplied_num_region_params != 0 || anon_regions.is_err() {
 440                 report_lifetime_number_error(tcx, span,
 441                                              supplied_num_region_params,
 442                                              expected_num_region_params);
 443             }
 444
 445             match anon_regions {
 446                 Ok(anon_regions) => anon_regions,
 447                 Err(_) => (0..expected_num_region_params).map(|_| ty::ReStatic).collect()
 448             }
 449         };
 450
 451         // If a self-type was declared, one should be provided.
 452         assert_eq!(decl_generics.has_self, self_ty.is_some());
 453
 454         // Check the number of type parameters supplied by the user.
 455         if let Some(num_provided) = num_types_provided {
 456             let ty_param_defs = &decl_generics.types[self_ty.is_some() as usize..];
 457             check_type_argument_count(tcx, span, num_provided, ty_param_defs);
 458         }
 459
 460         let is_object = self_ty.map_or(false, |ty| ty.sty == TRAIT_OBJECT_DUMMY_SELF);
 461         let default_needs_object_self = |p: &ty::TypeParameterDef<'tcx>| {
 462             if let Some(ref default) = p.default {
 463                 if is_object && default.has_self_ty() {
 464                     // There is no suitable inference default for a type parameter
 465                     // that references self, in an object type.
 466                     return true;
 467                 }
 468             }
 469
 470             false
 471         };
 472
 473         let mut output_assoc_binding = None;
 474         let substs = Substs::for_item(tcx, def_id, |def, _| {
 475             regions[def.index as usize]
 476         }, |def, substs| {
 477             let i = def.index as usize;
 478
 479             // Handle Self first, so we can adjust the index to match the AST.
 480             if let (0, Some(ty)) = (i, self_ty) {
 481                 return ty;
 482             }
 483
 484             let i = i - self_ty.is_some() as usize;
 485             if num_types_provided.map_or(false, |n| i < n) {
 486                 // A provided type parameter.
 487                 match *parameters {
 488                     hir::AngleBracketedParameters(ref data) => {
 489                         self.ast_ty_arg_to_ty(rscope, Some(def), substs, &data.types[i])
 490                     }
 491                     hir::ParenthesizedParameters(ref data) => {
 492                         assert_eq!(i, 0);
 493                         let (ty, assoc) =
 494                             self.convert_parenthesized_parameters(rscope, substs, data);
 495                         output_assoc_binding = Some(assoc);
 496                         ty
 497                     }
 498                 }
 499             } else if num_types_provided.is_none() {
 500                 // No type parameters were provided, we can infer all.
 501                 let ty_var = if !default_needs_object_self(def) {
 502                     self.ty_infer_for_def(def, substs, span)
 503                 } else {
 504                     self.ty_infer(span)
 505                 };
 506                 ty_var
 507             } else if let Some(default) = def.default {
 508                 // No type parameter provided, but a default exists.
 509
 510                 // If we are converting an object type, then the
 511                 // `Self` parameter is unknown. However, some of the
 512                 // other type parameters may reference `Self` in their
 513                 // defaults. This will lead to an ICE if we are not
 514                 // careful!
 515                 if default_needs_object_self(def) {
 516                     span_err!(tcx.sess, span, E0393,
 517                               "the type parameter `{}` must be explicitly specified \
 518                                in an object type because its default value `{}` references \
 519                                the type `Self`",
 520                               def.name,
 521                               default);
 522                     tcx.types.err
 523                 } else {
 524                     // This is a default type parameter.
 525                     default.subst_spanned(tcx, substs, Some(span))
 526                 }
 527             } else {
 528                 // We've already errored above about the mismatch.
 529                 tcx.types.err
 530             }
 531         });
 532
 533         let assoc_bindings = match *parameters {
 534             hir::AngleBracketedParameters(ref data) => {
 535                 data.bindings.iter().map(|b| {
 536                     ConvertedBinding {
 537                         item_name: b.name,
 538                         ty: self.ast_ty_to_ty(rscope, &b.ty),
 539                         span: b.span
 540                     }
 541                 }).collect()
 542             }
 543             hir::ParenthesizedParameters(ref data) => {
 544                 vec![output_assoc_binding.unwrap_or_else(|| {
 545                     // This is an error condition, but we should
 546                     // get the associated type binding anyway.
 547                     self.convert_parenthesized_parameters(rscope, substs, data).1
 548                 })]
 549             }
 550         };
 551
 552         debug!("create_substs_for_ast_path(decl_generics={:?}, self_ty={:?}) -> {:?}",
 553                decl_generics, self_ty, substs);
 554
 555         (substs, assoc_bindings)
 556     }
 557
 558     /// Returns the appropriate lifetime to use for any output lifetimes
 559     /// (if one exists) and a vector of the (pattern, number of lifetimes)
 560     /// corresponding to each input type/pattern.
 561     fn find_implied_output_region(&self,
 562                                   input_tys: &[Ty<'tcx>],
 563                                   input_pats: Vec<String>) -> ElidedLifetime
 564     {
 565         let tcx = self.tcx();
 566         let mut lifetimes_for_params = Vec::new();
 567         let mut possible_implied_output_region = None;
 568
 569         for (input_type, input_pat) in input_tys.iter().zip(input_pats) {
 570             let mut regions = FnvHashSet();
 571             let have_bound_regions = tcx.collect_regions(input_type, &mut regions);
 572
 573             debug!("find_implied_output_regions: collected {:?} from {:?} \
 574                     have_bound_regions={:?}", &regions, input_type, have_bound_regions);
 575
 576             if regions.len() == 1 {
 577                 // there's a chance that the unique lifetime of this
 578                 // iteration will be the appropriate lifetime for output
 579                 // parameters, so lets store it.
 580                 possible_implied_output_region = regions.iter().cloned().next();
 581             }
 582
 583             lifetimes_for_params.push(ElisionFailureInfo {
 584                 name: input_pat,
 585                 lifetime_count: regions.len(),
 586                 have_bound_regions: have_bound_regions
 587             });
 588         }
 589
 590         if lifetimes_for_params.iter().map(|e| e.lifetime_count).sum::<usize>() == 1 {
 591             Ok(possible_implied_output_region.unwrap())
 592         } else {
 593             Err(Some(lifetimes_for_params))
 594         }
 595     }
 596
 597     fn convert_ty_with_lifetime_elision(&self,
 598                                         elided_lifetime: ElidedLifetime,
 599                                         ty: &hir::Ty,
 600                                         anon_scope: Option<AnonTypeScope>)
 601                                         -> Ty<'tcx>
 602     {
 603         match elided_lifetime {
 604             Ok(implied_output_region) => {
 605                 let rb = ElidableRscope::new(implied_output_region);
 606                 self.ast_ty_to_ty(&MaybeWithAnonTypes::new(rb, anon_scope), ty)
 607             }
 608             Err(param_lifetimes) => {
 609                 // All regions must be explicitly specified in the output
 610                 // if the lifetime elision rules do not apply. This saves
 611                 // the user from potentially-confusing errors.
 612                 let rb = UnelidableRscope::new(param_lifetimes);
 613                 self.ast_ty_to_ty(&MaybeWithAnonTypes::new(rb, anon_scope), ty)
 614             }
 615         }
 616     }
 617
 618     fn convert_parenthesized_parameters(&self,
 619                                         rscope: &RegionScope,
 620                                         region_substs: &Substs<'tcx>,
 621                                         data: &hir::ParenthesizedParameterData)
 622                                         -> (Ty<'tcx>, ConvertedBinding<'tcx>)
 623     {
 624         let anon_scope = rscope.anon_type_scope();
 625         let binding_rscope = MaybeWithAnonTypes::new(BindingRscope::new(), anon_scope);
 626         let inputs: Vec<_> = data.inputs.iter().map(|a_t| {
 627             self.ast_ty_arg_to_ty(&binding_rscope, None, region_substs, a_t)
 628         }).collect();
 629         let input_params = vec![String::new(); inputs.len()];
 630         let implied_output_region = self.find_implied_output_region(&inputs, input_params);
 631
 632         let (output, output_span) = match data.output {
 633             Some(ref output_ty) => {
 634                 (self.convert_ty_with_lifetime_elision(implied_output_region,
 635                                                        &output_ty,
 636                                                        anon_scope),
 637                  output_ty.span)
 638             }
 639             None => {
 640                 (self.tcx().mk_nil(), data.span)
 641             }
 642         };
 643
 644         let output_binding = ConvertedBinding {
 645             item_name: token::intern(FN_OUTPUT_NAME),
 646             ty: output,
 647             span: output_span
 648         };
 649
 650         (self.tcx().mk_tup(inputs), output_binding)
 651     }
 652
 653     pub fn instantiate_poly_trait_ref(&self,
 654         rscope: &RegionScope,
 655         ast_trait_ref: &hir::PolyTraitRef,
 656         self_ty: Ty<'tcx>,
 657         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 658         -> ty::PolyTraitRef<'tcx>
 659     {
 660         let trait_ref = &ast_trait_ref.trait_ref;
 661         let trait_def_id = self.trait_def_id(trait_ref);
 662         self.ast_path_to_poly_trait_ref(rscope,
 663                                         trait_ref.path.span,
 664                                         PathParamMode::Explicit,
 665                                         trait_def_id,
 666                                         self_ty,
 667                                         trait_ref.ref_id,
 668                                         trait_ref.path.segments.last().unwrap(),
 669                                         poly_projections)
 670     }
 671
 672     /// Instantiates the path for the given trait reference, assuming that it's
 673     /// bound to a valid trait type. Returns the def_id for the defining trait.
 674     /// Fails if the type is a type other than a trait type.
 675     ///
 676     /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T=X>`
 677     /// are disallowed. Otherwise, they are pushed onto the vector given.
 678     pub fn instantiate_mono_trait_ref(&self,
 679         rscope: &RegionScope,
 680         trait_ref: &hir::TraitRef,
 681         self_ty: Ty<'tcx>)
 682         -> ty::TraitRef<'tcx>
 683     {
 684         let trait_def_id = self.trait_def_id(trait_ref);
 685         self.ast_path_to_mono_trait_ref(rscope,
 686                                         trait_ref.path.span,
 687                                         PathParamMode::Explicit,
 688                                         trait_def_id,
 689                                         self_ty,
 690                                         trait_ref.path.segments.last().unwrap())
 691     }
 692
 693     fn trait_def_id(&self, trait_ref: &hir::TraitRef) -> DefId {
 694         let path = &trait_ref.path;
 695         match self.tcx().expect_def(trait_ref.ref_id) {
 696             Def::Trait(trait_def_id) => trait_def_id,
 697             Def::Err => {
 698                 self.tcx().sess.fatal("cannot continue compilation due to previous error");
 699             }
 700             _ => {
 701                 span_fatal!(self.tcx().sess, path.span, E0245, "`{}` is not a trait",
 702                             path);
 703             }
 704         }
 705     }
 706
 707     fn ast_path_to_poly_trait_ref(&self,
 708         rscope: &RegionScope,
 709         span: Span,
 710         param_mode: PathParamMode,
 711         trait_def_id: DefId,
 712         self_ty: Ty<'tcx>,
 713         path_id: ast::NodeId,
 714         trait_segment: &hir::PathSegment,
 715         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 716         -> ty::PolyTraitRef<'tcx>
 717     {
 718         debug!("ast_path_to_poly_trait_ref(trait_segment={:?})", trait_segment);
 719         // The trait reference introduces a binding level here, so
 720         // we need to shift the `rscope`. It'd be nice if we could
 721         // do away with this rscope stuff and work this knowledge
 722         // into resolve_lifetimes, as we do with non-omitted
 723         // lifetimes. Oh well, not there yet.
 724         let shifted_rscope = &ShiftedRscope::new(rscope);
 725
 726         let (substs, assoc_bindings) =
 727             self.create_substs_for_ast_trait_ref(shifted_rscope,
 728                                                  span,
 729                                                  param_mode,
 730                                                  trait_def_id,
 731                                                  self_ty,
 732                                                  trait_segment);
 733         let poly_trait_ref = ty::Binder(ty::TraitRef::new(trait_def_id, substs));
 734
 735         poly_projections.extend(assoc_bindings.iter().filter_map(|binding| {
 736             // specify type to assert that error was already reported in Err case:
 737             let predicate: Result<_, ErrorReported> =
 738                 self.ast_type_binding_to_poly_projection_predicate(path_id,
 739                                                                    poly_trait_ref,
 740                                                                    binding);
 741             predicate.ok() // ok to ignore Err() because ErrorReported (see above)
 742         }));
 743
 744         debug!("ast_path_to_poly_trait_ref(trait_segment={:?}, projections={:?}) -> {:?}",
 745                trait_segment, poly_projections, poly_trait_ref);
 746         poly_trait_ref
 747     }
 748
 749     fn ast_path_to_mono_trait_ref(&self,
 750                                   rscope: &RegionScope,
 751                                   span: Span,
 752                                   param_mode: PathParamMode,
 753                                   trait_def_id: DefId,
 754                                   self_ty: Ty<'tcx>,
 755                                   trait_segment: &hir::PathSegment)
 756                                   -> ty::TraitRef<'tcx>
 757     {
 758         let (substs, assoc_bindings) =
 759             self.create_substs_for_ast_trait_ref(rscope,
 760                                                  span,
 761                                                  param_mode,
 762                                                  trait_def_id,
 763                                                  self_ty,
 764                                                  trait_segment);
 765         assoc_bindings.first().map(|b| self.tcx().prohibit_projection(b.span));
 766         ty::TraitRef::new(trait_def_id, substs)
 767     }
 768
 769     fn create_substs_for_ast_trait_ref(&self,
 770                                        rscope: &RegionScope,
 771                                        span: Span,
 772                                        param_mode: PathParamMode,
 773                                        trait_def_id: DefId,
 774                                        self_ty: Ty<'tcx>,
 775                                        trait_segment: &hir::PathSegment)
 776                                        -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
 777     {
 778         debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
 779                trait_segment);
 780
 781         let trait_def = match self.get_trait_def(span, trait_def_id) {
 782             Ok(trait_def) => trait_def,
 783             Err(ErrorReported) => {
 784                 // No convenient way to recover from a cycle here. Just bail. Sorry!
 785                 self.tcx().sess.abort_if_errors();
 786                 bug!("ErrorReported returned, but no errors reports?")
 787             }
 788         };
 789
 790         match trait_segment.parameters {
 791             hir::AngleBracketedParameters(_) => {
 792                 // For now, require that parenthetical notation be used
 793                 // only with `Fn()` etc.
 794                 if !self.tcx().sess.features.borrow().unboxed_closures && trait_def.paren_sugar {
 795                     emit_feature_err(&self.tcx().sess.parse_sess.span_diagnostic,
 796                                      "unboxed_closures", span, GateIssue::Language,
 797                                      "\
 798                         the precise format of `Fn`-family traits' \
 799                         type parameters is subject to change. \
 800                         Use parenthetical notation (Fn(Foo, Bar) -> Baz) instead");
 801                 }
 802             }
 803             hir::ParenthesizedParameters(_) => {
 804                 // For now, require that parenthetical notation be used
 805                 // only with `Fn()` etc.
 806                 if !self.tcx().sess.features.borrow().unboxed_closures && !trait_def.paren_sugar {
 807                     emit_feature_err(&self.tcx().sess.parse_sess.span_diagnostic,
 808                                      "unboxed_closures", span, GateIssue::Language,
 809                                      "\
 810                         parenthetical notation is only stable when used with `Fn`-family traits");
 811                 }
 812             }
 813         }
 814
 815         self.create_substs_for_ast_path(rscope,
 816                                         span,
 817                                         param_mode,
 818                                         trait_def_id,
 819                                         &trait_segment.parameters,
 820                                         Some(self_ty))
 821     }
 822
 823     fn ast_type_binding_to_poly_projection_predicate(
 824         &self,
 825         path_id: ast::NodeId,
 826         trait_ref: ty::PolyTraitRef<'tcx>,
 827         binding: &ConvertedBinding<'tcx>)
 828         -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
 829     {
 830         let tcx = self.tcx();
 831
 832         // Given something like `U : SomeTrait<T=X>`, we want to produce a
 833         // predicate like `<U as SomeTrait>::T = X`. This is somewhat
 834         // subtle in the event that `T` is defined in a supertrait of
 835         // `SomeTrait`, because in that case we need to upcast.
 836         //
 837         // That is, consider this case:
 838         //
 839         // ```
 840         // trait SubTrait : SuperTrait<int> { }
 841         // trait SuperTrait<A> { type T; }
 842         //
 843         // ... B : SubTrait<T=foo> ...
 844         // ```
 845         //
 846         // We want to produce `<B as SuperTrait<int>>::T == foo`.
 847
 848         // Find any late-bound regions declared in `ty` that are not
 849         // declared in the trait-ref. These are not wellformed.
 850         //
 851         // Example:
 852         //
 853         //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
 854         //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
 855         let late_bound_in_trait_ref = tcx.collect_constrained_late_bound_regions(&trait_ref);
 856         let late_bound_in_ty = tcx.collect_referenced_late_bound_regions(&ty::Binder(binding.ty));
 857         debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
 858         debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
 859         for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
 860             let br_name = match *br {
 861                 ty::BrNamed(_, name, _) => name,
 862                 _ => {
 863                     span_bug!(
 864                         binding.span,
 865                         "anonymous bound region {:?} in binding but not trait ref",
 866                         br);
 867                 }
 868             };
 869             tcx.sess.add_lint(
 870                 lint::builtin::HR_LIFETIME_IN_ASSOC_TYPE,
 871                 path_id,
 872                 binding.span,
 873                 format!("binding for associated type `{}` references lifetime `{}`, \
 874                          which does not appear in the trait input types",
 875                         binding.item_name, br_name));
 876         }
 877
 878         // Simple case: X is defined in the current trait.
 879         if self.trait_defines_associated_type_named(trait_ref.def_id(), binding.item_name) {
 880             return Ok(trait_ref.map_bound(|trait_ref| {
 881                 ty::ProjectionPredicate {
 882                     projection_ty: ty::ProjectionTy {
 883                         trait_ref: trait_ref,
 884                         item_name: binding.item_name,
 885                     },
 886                     ty: binding.ty,
 887                 }
 888             }));
 889         }
 890
 891         // Otherwise, we have to walk through the supertraits to find
 892         // those that do.
 893         self.ensure_super_predicates(binding.span, trait_ref.def_id())?;
 894
 895         let candidates: Vec<ty::PolyTraitRef> =
 896             traits::supertraits(tcx, trait_ref.clone())
 897             .filter(|r| self.trait_defines_associated_type_named(r.def_id(), binding.item_name))
 898             .collect();
 899
 900         let candidate = self.one_bound_for_assoc_type(candidates,
 901                                                       &trait_ref.to_string(),
 902                                                       &binding.item_name.as_str(),
 903                                                       binding.span)?;
 904
 905         Ok(candidate.map_bound(|trait_ref| {
 906             ty::ProjectionPredicate {
 907                 projection_ty: ty::ProjectionTy {
 908                     trait_ref: trait_ref,
 909                     item_name: binding.item_name,
 910                 },
 911                 ty: binding.ty,
 912             }
 913         }))
 914     }
 915
 916     fn ast_path_to_ty(&self,
 917         rscope: &RegionScope,
 918         span: Span,
 919         param_mode: PathParamMode,
 920         did: DefId,
 921         item_segment: &hir::PathSegment)
 922         -> Ty<'tcx>
 923     {
 924         let tcx = self.tcx();
 925         let decl_ty = match self.get_item_type_scheme(span, did) {
 926             Ok(type_scheme) => type_scheme.ty,
 927             Err(ErrorReported) => {
 928                 return tcx.types.err;
 929             }
 930         };
 931
 932         let substs = self.ast_path_substs_for_ty(rscope,
 933                                                  span,
 934                                                  param_mode,
 935                                                  did,
 936                                                  item_segment);
 937
 938         // FIXME(#12938): This is a hack until we have full support for DST.
 939         if Some(did) == self.tcx().lang_items.owned_box() {
 940             assert_eq!(substs.types.len(), 1);
 941             return self.tcx().mk_box(substs.types[0]);
 942         }
 943
 944         decl_ty.subst(self.tcx(), substs)
 945     }
 946
 947     fn ast_ty_to_object_trait_ref(&self,
 948                                   rscope: &RegionScope,
 949                                   span: Span,
 950                                   ty: &hir::Ty,
 951                                   bounds: &[hir::TyParamBound])
 952                                   -> Ty<'tcx>
 953     {
 954         /*!
 955          * In a type like `Foo + Send`, we want to wait to collect the
 956          * full set of bounds before we make the object type, because we
 957          * need them to infer a region bound.  (For example, if we tried
 958          * made a type from just `Foo`, then it wouldn't be enough to
 959          * infer a 'static bound, and hence the user would get an error.)
 960          * So this function is used when we're dealing with a sum type to
 961          * convert the LHS. It only accepts a type that refers to a trait
 962          * name, and reports an error otherwise.
 963          */
 964
 965         let tcx = self.tcx();
 966         match ty.node {
 967             hir::TyPath(None, ref path) => {
 968                 let resolution = tcx.expect_resolution(ty.id);
 969                 match resolution.base_def {
 970                     Def::Trait(trait_def_id) if resolution.depth == 0 => {
 971                         self.trait_path_to_object_type(rscope,
 972                                                        path.span,
 973                                                        PathParamMode::Explicit,
 974                                                        trait_def_id,
 975                                                        ty.id,
 976                                                        path.segments.last().unwrap(),
 977                                                        span,
 978                                                        partition_bounds(tcx, span, bounds))
 979                     }
 980                     _ => {
 981                         struct_span_err!(tcx.sess, ty.span, E0172,
 982                                   "expected a reference to a trait")
 983                             .span_label(ty.span, &format!("expected a trait"))
 984                             .emit();
 985                         tcx.types.err
 986                     }
 987                 }
 988             }
 989             _ => {
 990                 let mut err = struct_span_err!(tcx.sess, ty.span, E0178,
 991                                                "expected a path on the left-hand side \
 992                                                 of `+`, not `{}`",
 993                                                pprust::ty_to_string(ty));
 994                 err.span_label(ty.span, &format!("expected a path"));
 995                 let hi = bounds.iter().map(|x| match *x {
 996                     hir::TraitTyParamBound(ref tr, _) => tr.span.hi,
 997                     hir::RegionTyParamBound(ref r) => r.span.hi,
 998                 }).max_by_key(|x| x.to_usize());
 999                 let full_span = hi.map(|hi| Span {
1000                     lo: ty.span.lo,
1001                     hi: hi,
1002                     expn_id: ty.span.expn_id,
1003                 });
1004                 match (&ty.node, full_span) {
1005                     (&hir::TyRptr(None, ref mut_ty), Some(full_span)) => {
1006                         let mutbl_str = if mut_ty.mutbl == hir::MutMutable { "mut " } else { "" };
1007                         err.span_suggestion(full_span, "try adding parentheses (per RFC 438):",
1008                                             format!("&{}({} +{})",
1009                                                     mutbl_str,
1010                                                     pprust::ty_to_string(&mut_ty.ty),
1011                                                     pprust::bounds_to_string(bounds)));
1012                     }
1013                     (&hir::TyRptr(Some(ref lt), ref mut_ty), Some(full_span)) => {
1014                         let mutbl_str = if mut_ty.mutbl == hir::MutMutable { "mut " } else { "" };
1015                         err.span_suggestion(full_span, "try adding parentheses (per RFC 438):",
1016                                             format!("&{} {}({} +{})",
1017                                                     pprust::lifetime_to_string(lt),
1018                                                     mutbl_str,
1019                                                     pprust::ty_to_string(&mut_ty.ty),
1020                                                     pprust::bounds_to_string(bounds)));
1021                     }
1022
1023                     _ => {
1024                         help!(&mut err,
1025                                    "perhaps you forgot parentheses? (per RFC 438)");
1026                     }
1027                 }
1028                 err.emit();
1029                 tcx.types.err
1030             }
1031         }
1032     }
1033
1034     /// Transform a PolyTraitRef into a PolyExistentialTraitRef by
1035     /// removing the dummy Self type (TRAIT_OBJECT_DUMMY_SELF).
1036     fn trait_ref_to_existential(&self, trait_ref: ty::TraitRef<'tcx>)
1037                                 -> ty::ExistentialTraitRef<'tcx> {
1038         assert_eq!(trait_ref.self_ty().sty, TRAIT_OBJECT_DUMMY_SELF);
1039         ty::ExistentialTraitRef::erase_self_ty(self.tcx(), trait_ref)
1040     }
1041
1042     fn trait_path_to_object_type(&self,
1043                                  rscope: &RegionScope,
1044                                  path_span: Span,
1045                                  param_mode: PathParamMode,
1046                                  trait_def_id: DefId,
1047                                  trait_path_ref_id: ast::NodeId,
1048                                  trait_segment: &hir::PathSegment,
1049                                  span: Span,
1050                                  partitioned_bounds: PartitionedBounds)
1051                                  -> Ty<'tcx> {
1052         let tcx = self.tcx();
1053
1054         let mut projection_bounds = vec![];
1055         let dummy_self = tcx.mk_ty(TRAIT_OBJECT_DUMMY_SELF);
1056         let principal = self.ast_path_to_poly_trait_ref(rscope,
1057                                                         path_span,
1058                                                         param_mode,
1059                                                         trait_def_id,
1060                                                         dummy_self,
1061                                                         trait_path_ref_id,
1062                                                         trait_segment,
1063                                                         &mut projection_bounds);
1064
1065         let PartitionedBounds { builtin_bounds,
1066                                 trait_bounds,
1067                                 region_bounds } =
1068             partitioned_bounds;
1069
1070         if !trait_bounds.is_empty() {
1071             let b = &trait_bounds[0];
1072             let span = b.trait_ref.path.span;
1073             struct_span_err!(self.tcx().sess, span, E0225,
1074                              "only the builtin traits can be used as closure or object bounds")
1075                 .span_label(span, &format!("non-builtin trait used as bounds"))
1076                 .emit();
1077         }
1078
1079         // Erase the dummy_self (TRAIT_OBJECT_DUMMY_SELF) used above.
1080         let existential_principal = principal.map_bound(|trait_ref| {
1081             self.trait_ref_to_existential(trait_ref)
1082         });
1083         let existential_projections = projection_bounds.iter().map(|bound| {
1084             bound.map_bound(|b| {
1085                 let p = b.projection_ty;
1086                 ty::ExistentialProjection {
1087                     trait_ref: self.trait_ref_to_existential(p.trait_ref),
1088                     item_name: p.item_name,
1089                     ty: b.ty
1090                 }
1091             })
1092         }).collect();
1093
1094         let region_bound =
1095             self.compute_object_lifetime_bound(span,
1096                                                &region_bounds,
1097                                                existential_principal,
1098                                                builtin_bounds);
1099
1100         let region_bound = match region_bound {
1101             Some(r) => r,
1102             None => {
1103                 match rscope.object_lifetime_default(span) {
1104                     Some(r) => r,
1105                     None => {
1106                         span_err!(self.tcx().sess, span, E0228,
1107                                   "the lifetime bound for this object type cannot be deduced \
1108                                    from context; please supply an explicit bound");
1109                         ty::ReStatic
1110                     }
1111                 }
1112             }
1113         };
1114
1115         debug!("region_bound: {:?}", region_bound);
1116
1117         // ensure the super predicates and stop if we encountered an error
1118         if self.ensure_super_predicates(span, principal.def_id()).is_err() {
1119             return tcx.types.err;
1120         }
1121
1122         // check that there are no gross object safety violations,
1123         // most importantly, that the supertraits don't contain Self,
1124         // to avoid ICE-s.
1125         let object_safety_violations =
1126             tcx.astconv_object_safety_violations(principal.def_id());
1127         if !object_safety_violations.is_empty() {
1128             tcx.report_object_safety_error(
1129                 span, principal.def_id(), None, object_safety_violations)
1130                 .unwrap().emit();
1131             return tcx.types.err;
1132         }
1133
1134         let mut associated_types: FnvHashSet<(DefId, ast::Name)> =
1135             traits::supertraits(tcx, principal)
1136             .flat_map(|tr| {
1137                 let trait_def = tcx.lookup_trait_def(tr.def_id());
1138                 trait_def.associated_type_names
1139                     .clone()
1140                     .into_iter()
1141                     .map(move |associated_type_name| (tr.def_id(), associated_type_name))
1142             })
1143             .collect();
1144
1145         for projection_bound in &projection_bounds {
1146             let pair = (projection_bound.0.projection_ty.trait_ref.def_id,
1147                         projection_bound.0.projection_ty.item_name);
1148             associated_types.remove(&pair);
1149         }
1150
1151         for (trait_def_id, name) in associated_types {
1152             struct_span_err!(tcx.sess, span, E0191,
1153                 "the value of the associated type `{}` (from the trait `{}`) must be specified",
1154                         name,
1155                         tcx.item_path_str(trait_def_id))
1156                         .span_label(span, &format!(
1157                             "missing associated type `{}` value", name))
1158                         .emit();
1159         }
1160
1161         let ty = tcx.mk_trait(ty::TraitObject {
1162             principal: existential_principal,
1163             region_bound: region_bound,
1164             builtin_bounds: builtin_bounds,
1165             projection_bounds: existential_projections
1166         });
1167         debug!("trait_object_type: {:?}", ty);
1168         ty
1169     }
1170
1171     fn report_ambiguous_associated_type(&self,
1172                                         span: Span,
1173                                         type_str: &str,
1174                                         trait_str: &str,
1175                                         name: &str) {
1176         struct_span_err!(self.tcx().sess, span, E0223, "ambiguous associated type")
1177             .span_label(span, &format!("ambiguous associated type"))
1178             .note(&format!("specify the type using the syntax `<{} as {}>::{}`",
1179                   type_str, trait_str, name))
1180             .emit();
1181
1182     }
1183
1184     // Search for a bound on a type parameter which includes the associated item
1185     // given by assoc_name. ty_param_node_id is the node id for the type parameter
1186     // (which might be `Self`, but only if it is the `Self` of a trait, not an
1187     // impl). This function will fail if there are no suitable bounds or there is
1188     // any ambiguity.
1189     fn find_bound_for_assoc_item(&self,
1190                                  ty_param_node_id: ast::NodeId,
1191                                  ty_param_name: ast::Name,
1192                                  assoc_name: ast::Name,
1193                                  span: Span)
1194                                  -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1195     {
1196         let tcx = self.tcx();
1197
1198         let bounds = match self.get_type_parameter_bounds(span, ty_param_node_id) {
1199             Ok(v) => v,
1200             Err(ErrorReported) => {
1201                 return Err(ErrorReported);
1202             }
1203         };
1204
1205         // Ensure the super predicates and stop if we encountered an error.
1206         if bounds.iter().any(|b| self.ensure_super_predicates(span, b.def_id()).is_err()) {
1207             return Err(ErrorReported);
1208         }
1209
1210         // Check that there is exactly one way to find an associated type with the
1211         // correct name.
1212         let suitable_bounds: Vec<_> =
1213             traits::transitive_bounds(tcx, &bounds)
1214             .filter(|b| self.trait_defines_associated_type_named(b.def_id(), assoc_name))
1215             .collect();
1216
1217         self.one_bound_for_assoc_type(suitable_bounds,
1218                                       &ty_param_name.as_str(),
1219                                       &assoc_name.as_str(),
1220                                       span)
1221     }
1222
1223
1224     // Checks that bounds contains exactly one element and reports appropriate
1225     // errors otherwise.
1226     fn one_bound_for_assoc_type(&self,
1227                                 bounds: Vec<ty::PolyTraitRef<'tcx>>,
1228                                 ty_param_name: &str,
1229                                 assoc_name: &str,
1230                                 span: Span)
1231         -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1232     {
1233         if bounds.is_empty() {
1234             span_err!(self.tcx().sess, span, E0220,
1235                       "associated type `{}` not found for `{}`",
1236                       assoc_name,
1237                       ty_param_name);
1238             return Err(ErrorReported);
1239         }
1240
1241         if bounds.len() > 1 {
1242             let mut err = struct_span_err!(
1243                 self.tcx().sess, span, E0221,
1244                 "ambiguous associated type `{}` in bounds of `{}`",
1245                 assoc_name,
1246                 ty_param_name);
1247             err.span_label(span, &format!("ambiguous associated type `{}`", assoc_name));
1248
1249             for bound in &bounds {
1250                 span_note!(&mut err, span,
1251                            "associated type `{}` could derive from `{}`",
1252                            ty_param_name,
1253                            bound);
1254             }
1255             err.emit();
1256         }
1257
1258         Ok(bounds[0].clone())
1259     }
1260
1261     // Create a type from a path to an associated type.
1262     // For a path A::B::C::D, ty and ty_path_def are the type and def for A::B::C
1263     // and item_segment is the path segment for D. We return a type and a def for
1264     // the whole path.
1265     // Will fail except for T::A and Self::A; i.e., if ty/ty_path_def are not a type
1266     // parameter or Self.
1267     fn associated_path_def_to_ty(&self,
1268                                  span: Span,
1269                                  ty: Ty<'tcx>,
1270                                  ty_path_def: Def,
1271                                  item_segment: &hir::PathSegment)
1272                                  -> (Ty<'tcx>, Def)
1273     {
1274         let tcx = self.tcx();
1275         let assoc_name = item_segment.name;
1276
1277         debug!("associated_path_def_to_ty: {:?}::{}", ty, assoc_name);
1278
1279         tcx.prohibit_type_params(slice::ref_slice(item_segment));
1280
1281         // Find the type of the associated item, and the trait where the associated
1282         // item is declared.
1283         let bound = match (&ty.sty, ty_path_def) {
1284             (_, Def::SelfTy(Some(trait_did), Some(impl_id))) => {
1285                 // For Def::SelfTy() values inlined from another crate, the
1286                 // impl_id will be DUMMY_NODE_ID, which would cause problems
1287                 // here. But we should never run into an impl from another crate
1288                 // in this pass.
1289                 assert!(impl_id != ast::DUMMY_NODE_ID);
1290
1291                 // `Self` in an impl of a trait - we have a concrete self type and a
1292                 // trait reference.
1293                 let trait_ref = tcx.impl_trait_ref(tcx.map.local_def_id(impl_id)).unwrap();
1294                 let trait_ref = if let Some(free_substs) = self.get_free_substs() {
1295                     trait_ref.subst(tcx, free_substs)
1296                 } else {
1297                     trait_ref
1298                 };
1299
1300                 if self.ensure_super_predicates(span, trait_did).is_err() {
1301                     return (tcx.types.err, Def::Err);
1302                 }
1303
1304                 let candidates: Vec<ty::PolyTraitRef> =
1305                     traits::supertraits(tcx, ty::Binder(trait_ref))
1306                     .filter(|r| self.trait_defines_associated_type_named(r.def_id(),
1307                                                                          assoc_name))
1308                     .collect();
1309
1310                 match self.one_bound_for_assoc_type(candidates,
1311                                                     "Self",
1312                                                     &assoc_name.as_str(),
1313                                                     span) {
1314                     Ok(bound) => bound,
1315                     Err(ErrorReported) => return (tcx.types.err, Def::Err),
1316                 }
1317             }
1318             (&ty::TyParam(_), Def::SelfTy(Some(trait_did), None)) => {
1319                 let trait_node_id = tcx.map.as_local_node_id(trait_did).unwrap();
1320                 match self.find_bound_for_assoc_item(trait_node_id,
1321                                                      keywords::SelfType.name(),
1322                                                      assoc_name,
1323                                                      span) {
1324                     Ok(bound) => bound,
1325                     Err(ErrorReported) => return (tcx.types.err, Def::Err),
1326                 }
1327             }
1328             (&ty::TyParam(_), Def::TyParam(param_did)) => {
1329                 let param_node_id = tcx.map.as_local_node_id(param_did).unwrap();
1330                 let param_name = tcx.type_parameter_def(param_node_id).name;
1331                 match self.find_bound_for_assoc_item(param_node_id,
1332                                                      param_name,
1333                                                      assoc_name,
1334                                                      span) {
1335                     Ok(bound) => bound,
1336                     Err(ErrorReported) => return (tcx.types.err, Def::Err),
1337                 }
1338             }
1339             _ => {
1340                 // Don't print TyErr to the user.
1341                 if !ty.references_error() {
1342                     self.report_ambiguous_associated_type(span,
1343                                                           &ty.to_string(),
1344                                                           "Trait",
1345                                                           &assoc_name.as_str());
1346                 }
1347                 return (tcx.types.err, Def::Err);
1348             }
1349         };
1350
1351         let trait_did = bound.0.def_id;
1352         let ty = self.projected_ty_from_poly_trait_ref(span, bound, assoc_name);
1353
1354         let item_did = if let Some(trait_id) = tcx.map.as_local_node_id(trait_did) {
1355             // `ty::trait_items` used below requires information generated
1356             // by type collection, which may be in progress at this point.
1357             match tcx.map.expect_item(trait_id).node {
1358                 hir::ItemTrait(_, _, _, ref trait_items) => {
1359                     let item = trait_items.iter()
1360                                           .find(|i| i.name == assoc_name)
1361                                           .expect("missing associated type");
1362                     tcx.map.local_def_id(item.id)
1363                 }
1364                 _ => bug!()
1365             }
1366         } else {
1367             let trait_items = tcx.trait_items(trait_did);
1368             let item = trait_items.iter().find(|i| i.name() == assoc_name);
1369             item.expect("missing associated type").def_id()
1370         };
1371
1372         (ty, Def::AssociatedTy(trait_did, item_did))
1373     }
1374
1375     fn qpath_to_ty(&self,
1376                    rscope: &RegionScope,
1377                    span: Span,
1378                    param_mode: PathParamMode,
1379                    opt_self_ty: Option<Ty<'tcx>>,
1380                    trait_def_id: DefId,
1381                    trait_segment: &hir::PathSegment,
1382                    item_segment: &hir::PathSegment)
1383                    -> Ty<'tcx>
1384     {
1385         let tcx = self.tcx();
1386
1387         tcx.prohibit_type_params(slice::ref_slice(item_segment));
1388
1389         let self_ty = if let Some(ty) = opt_self_ty {
1390             ty
1391         } else {
1392             let path_str = tcx.item_path_str(trait_def_id);
1393             self.report_ambiguous_associated_type(span,
1394                                                   "Type",
1395                                                   &path_str,
1396                                                   &item_segment.name.as_str());
1397             return tcx.types.err;
1398         };
1399
1400         debug!("qpath_to_ty: self_type={:?}", self_ty);
1401
1402         let trait_ref = self.ast_path_to_mono_trait_ref(rscope,
1403                                                         span,
1404                                                         param_mode,
1405                                                         trait_def_id,
1406                                                         self_ty,
1407                                                         trait_segment);
1408
1409         debug!("qpath_to_ty: trait_ref={:?}", trait_ref);
1410
1411         self.projected_ty(span, trait_ref, item_segment.name)
1412     }
1413
1414     /// Convert a type supplied as value for a type argument from AST into our
1415     /// our internal representation. This is the same as `ast_ty_to_ty` but that
1416     /// it applies the object lifetime default.
1417     ///
1418     /// # Parameters
1419     ///
1420     /// * `this`, `rscope`: the surrounding context
1421     /// * `def`: the type parameter being instantiated (if available)
1422     /// * `region_substs`: a partial substitution consisting of
1423     ///   only the region type parameters being supplied to this type.
1424     /// * `ast_ty`: the ast representation of the type being supplied
1425     fn ast_ty_arg_to_ty(&self,
1426                         rscope: &RegionScope,
1427                         def: Option<&ty::TypeParameterDef<'tcx>>,
1428                         region_substs: &Substs<'tcx>,
1429                         ast_ty: &hir::Ty)
1430                         -> Ty<'tcx>
1431     {
1432         let tcx = self.tcx();
1433
1434         if let Some(def) = def {
1435             let object_lifetime_default = def.object_lifetime_default.subst(tcx, region_substs);
1436             let rscope1 = &ObjectLifetimeDefaultRscope::new(rscope, object_lifetime_default);
1437             self.ast_ty_to_ty(rscope1, ast_ty)
1438         } else {
1439             self.ast_ty_to_ty(rscope, ast_ty)
1440         }
1441     }
1442
1443     // Check the base def in a PathResolution and convert it to a Ty. If there are
1444     // associated types in the PathResolution, these will need to be separately
1445     // resolved.
1446     fn base_def_to_ty(&self,
1447                       rscope: &RegionScope,
1448                       span: Span,
1449                       param_mode: PathParamMode,
1450                       def: Def,
1451                       opt_self_ty: Option<Ty<'tcx>>,
1452                       base_path_ref_id: ast::NodeId,
1453                       base_segments: &[hir::PathSegment])
1454                       -> Ty<'tcx> {
1455         let tcx = self.tcx();
1456
1457         debug!("base_def_to_ty(def={:?}, opt_self_ty={:?}, base_segments={:?})",
1458                def, opt_self_ty, base_segments);
1459
1460         match def {
1461             Def::Trait(trait_def_id) => {
1462                 // N.B. this case overlaps somewhat with
1463                 // TyObjectSum, see that fn for details
1464
1465                 tcx.prohibit_type_params(base_segments.split_last().unwrap().1);
1466
1467                 self.trait_path_to_object_type(rscope,
1468                                                span,
1469                                                param_mode,
1470                                                trait_def_id,
1471                                                base_path_ref_id,
1472                                                base_segments.last().unwrap(),
1473                                                span,
1474                                                partition_bounds(tcx, span, &[]))
1475             }
1476             Def::Enum(did) | Def::TyAlias(did) | Def::Struct(did) => {
1477                 tcx.prohibit_type_params(base_segments.split_last().unwrap().1);
1478                 self.ast_path_to_ty(rscope,
1479                                     span,
1480                                     param_mode,
1481                                     did,
1482                                     base_segments.last().unwrap())
1483             }
1484             Def::TyParam(did) => {
1485                 tcx.prohibit_type_params(base_segments);
1486
1487                 let node_id = tcx.map.as_local_node_id(did).unwrap();
1488                 let param = tcx.ty_param_defs.borrow().get(&node_id)
1489                                .map(ty::ParamTy::for_def);
1490                 if let Some(p) = param {
1491                     p.to_ty(tcx)
1492                 } else {
1493                     // Only while computing defaults of earlier type
1494                     // parameters can a type parameter be missing its def.
1495                     struct_span_err!(tcx.sess, span, E0128,
1496                                      "type parameters with a default cannot use \
1497                                       forward declared identifiers")
1498                         .span_label(span, &format!("defaulted type parameters \
1499                                                     cannot be forward declared"))
1500                         .emit();
1501                     tcx.types.err
1502                 }
1503             }
1504             Def::SelfTy(_, Some(impl_id)) => {
1505                 // Self in impl (we know the concrete type).
1506
1507                 // For Def::SelfTy() values inlined from another crate, the
1508                 // impl_id will be DUMMY_NODE_ID, which would cause problems
1509                 // here. But we should never run into an impl from another crate
1510                 // in this pass.
1511                 assert!(impl_id != ast::DUMMY_NODE_ID);
1512
1513                 tcx.prohibit_type_params(base_segments);
1514                 let ty = tcx.node_id_to_type(impl_id);
1515                 if let Some(free_substs) = self.get_free_substs() {
1516                     ty.subst(tcx, free_substs)
1517                 } else {
1518                     ty
1519                 }
1520             }
1521             Def::SelfTy(Some(_), None) => {
1522                 // Self in trait.
1523                 tcx.prohibit_type_params(base_segments);
1524                 tcx.mk_self_type()
1525             }
1526             Def::AssociatedTy(trait_did, _) => {
1527                 tcx.prohibit_type_params(&base_segments[..base_segments.len()-2]);
1528                 self.qpath_to_ty(rscope,
1529                                  span,
1530                                  param_mode,
1531                                  opt_self_ty,
1532                                  trait_did,
1533                                  &base_segments[base_segments.len()-2],
1534                                  base_segments.last().unwrap())
1535             }
1536             Def::Mod(..) => {
1537                 // Used as sentinel by callers to indicate the `<T>::A::B::C` form.
1538                 // FIXME(#22519) This part of the resolution logic should be
1539                 // avoided entirely for that form, once we stop needed a Def
1540                 // for `associated_path_def_to_ty`.
1541                 // Fixing this will also let use resolve <Self>::Foo the same way we
1542                 // resolve Self::Foo, at the moment we can't resolve the former because
1543                 // we don't have the trait information around, which is just sad.
1544
1545                 assert!(base_segments.is_empty());
1546
1547                 opt_self_ty.expect("missing T in <T>::a::b::c")
1548             }
1549             Def::PrimTy(prim_ty) => {
1550                 tcx.prim_ty_to_ty(base_segments, prim_ty)
1551             }
1552             Def::Err => {
1553                 self.set_tainted_by_errors();
1554                 return self.tcx().types.err;
1555             }
1556             _ => {
1557                 struct_span_err!(tcx.sess, span, E0248,
1558                            "found value `{}` used as a type",
1559                             tcx.item_path_str(def.def_id()))
1560                            .span_label(span, &format!("value used as a type"))
1561                            .emit();
1562                 return self.tcx().types.err;
1563             }
1564         }
1565     }
1566
1567     // Resolve possibly associated type path into a type and final definition.
1568     // Note that both base_segments and assoc_segments may be empty, although not at same time.
1569     pub fn finish_resolving_def_to_ty(&self,
1570                                       rscope: &RegionScope,
1571                                       span: Span,
1572                                       param_mode: PathParamMode,
1573                                       base_def: Def,
1574                                       opt_self_ty: Option<Ty<'tcx>>,
1575                                       base_path_ref_id: ast::NodeId,
1576                                       base_segments: &[hir::PathSegment],
1577                                       assoc_segments: &[hir::PathSegment])
1578                                       -> (Ty<'tcx>, Def) {
1579         // Convert the base type.
1580         debug!("finish_resolving_def_to_ty(base_def={:?}, \
1581                 base_segments={:?}, \
1582                 assoc_segments={:?})",
1583                base_def,
1584                base_segments,
1585                assoc_segments);
1586         let base_ty = self.base_def_to_ty(rscope,
1587                                           span,
1588                                           param_mode,
1589                                           base_def,
1590                                           opt_self_ty,
1591                                           base_path_ref_id,
1592                                           base_segments);
1593         debug!("finish_resolving_def_to_ty: base_def_to_ty returned {:?}", base_ty);
1594
1595         // If any associated type segments remain, attempt to resolve them.
1596         let (mut ty, mut def) = (base_ty, base_def);
1597         for segment in assoc_segments {
1598             debug!("finish_resolving_def_to_ty: segment={:?}", segment);
1599             // This is pretty bad (it will fail except for T::A and Self::A).
1600             let (new_ty, new_def) = self.associated_path_def_to_ty(span, ty, def, segment);
1601             ty = new_ty;
1602             def = new_def;
1603
1604             if def == Def::Err {
1605                 break;
1606             }
1607         }
1608         (ty, def)
1609     }
1610
1611     /// Parses the programmer's textual representation of a type into our
1612     /// internal notion of a type.
1613     pub fn ast_ty_to_ty(&self, rscope: &RegionScope, ast_ty: &hir::Ty) -> Ty<'tcx> {
1614         debug!("ast_ty_to_ty(id={:?}, ast_ty={:?})",
1615                ast_ty.id, ast_ty);
1616
1617         let tcx = self.tcx();
1618
1619         let cache = self.ast_ty_to_ty_cache();
1620         match cache.borrow().get(&ast_ty.id) {
1621             Some(ty) => { return ty; }
1622             None => { }
1623         }
1624
1625         let result_ty = match ast_ty.node {
1626             hir::TyVec(ref ty) => {
1627                 tcx.mk_slice(self.ast_ty_to_ty(rscope, &ty))
1628             }
1629             hir::TyObjectSum(ref ty, ref bounds) => {
1630                 self.ast_ty_to_object_trait_ref(rscope, ast_ty.span, ty, bounds)
1631             }
1632             hir::TyPtr(ref mt) => {
1633                 tcx.mk_ptr(ty::TypeAndMut {
1634                     ty: self.ast_ty_to_ty(rscope, &mt.ty),
1635                     mutbl: mt.mutbl
1636                 })
1637             }
1638             hir::TyRptr(ref region, ref mt) => {
1639                 let r = self.opt_ast_region_to_region(rscope, ast_ty.span, region);
1640                 debug!("TyRef r={:?}", r);
1641                 let rscope1 =
1642                     &ObjectLifetimeDefaultRscope::new(
1643                         rscope,
1644                         ty::ObjectLifetimeDefault::Specific(r));
1645                 let t = self.ast_ty_to_ty(rscope1, &mt.ty);
1646                 tcx.mk_ref(tcx.mk_region(r), ty::TypeAndMut {ty: t, mutbl: mt.mutbl})
1647             }
1648             hir::TyNever => {
1649                 tcx.types.never
1650             },
1651             hir::TyTup(ref fields) => {
1652                 let flds = fields.iter()
1653                                  .map(|t| self.ast_ty_to_ty(rscope, &t))
1654                                  .collect();
1655                 tcx.mk_tup(flds)
1656             }
1657             hir::TyBareFn(ref bf) => {
1658                 require_c_abi_if_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
1659                 let anon_scope = rscope.anon_type_scope();
1660                 let (bare_fn_ty, _) =
1661                     self.ty_of_method_or_bare_fn(bf.unsafety,
1662                                                  bf.abi,
1663                                                  None,
1664                                                  &bf.decl,
1665                                                  anon_scope,
1666                                                  anon_scope);
1667
1668                 // Find any late-bound regions declared in return type that do
1669                 // not appear in the arguments. These are not wellformed.
1670                 //
1671                 // Example:
1672                 //
1673                 //     for<'a> fn() -> &'a str <-- 'a is bad
1674                 //     for<'a> fn(&'a String) -> &'a str <-- 'a is ok
1675                 //
1676                 // Note that we do this check **here** and not in
1677                 // `ty_of_bare_fn` because the latter is also used to make
1678                 // the types for fn items, and we do not want to issue a
1679                 // warning then. (Once we fix #32330, the regions we are
1680                 // checking for here would be considered early bound
1681                 // anyway.)
1682                 let inputs = bare_fn_ty.sig.inputs();
1683                 let late_bound_in_args = tcx.collect_constrained_late_bound_regions(&inputs);
1684                 let output = bare_fn_ty.sig.output();
1685                 let late_bound_in_ret = tcx.collect_referenced_late_bound_regions(&output);
1686                 for br in late_bound_in_ret.difference(&late_bound_in_args) {
1687                     let br_name = match *br {
1688                         ty::BrNamed(_, name, _) => name,
1689                         _ => {
1690                             span_bug!(
1691                                 bf.decl.output.span(),
1692                                 "anonymous bound region {:?} in return but not args",
1693                                 br);
1694                         }
1695                     };
1696                     tcx.sess.add_lint(
1697                         lint::builtin::HR_LIFETIME_IN_ASSOC_TYPE,
1698                         ast_ty.id,
1699                         ast_ty.span,
1700                         format!("return type references lifetime `{}`, \
1701                                  which does not appear in the trait input types",
1702                                 br_name));
1703                 }
1704                 tcx.mk_fn_ptr(bare_fn_ty)
1705             }
1706             hir::TyPolyTraitRef(ref bounds) => {
1707                 self.conv_object_ty_poly_trait_ref(rscope, ast_ty.span, bounds)
1708             }
1709             hir::TyImplTrait(ref bounds) => {
1710                 use collect::{compute_bounds, SizedByDefault};
1711
1712                 // Create the anonymized type.
1713                 let def_id = tcx.map.local_def_id(ast_ty.id);
1714                 if let Some(anon_scope) = rscope.anon_type_scope() {
1715                     let substs = anon_scope.fresh_substs(self, ast_ty.span);
1716                     let ty = tcx.mk_anon(tcx.map.local_def_id(ast_ty.id), substs);
1717
1718                     // Collect the bounds, i.e. the `A+B+'c` in `impl A+B+'c`.
1719                     let bounds = compute_bounds(self, ty, bounds,
1720                                                 SizedByDefault::Yes,
1721                                                 Some(anon_scope),
1722                                                 ast_ty.span);
1723                     let predicates = bounds.predicates(tcx, ty);
1724                     let predicates = tcx.lift_to_global(&predicates).unwrap();
1725                     tcx.predicates.borrow_mut().insert(def_id, ty::GenericPredicates {
1726                         parent: None,
1727                         predicates: predicates
1728                     });
1729
1730                     ty
1731                 } else {
1732                     span_err!(tcx.sess, ast_ty.span, E0562,
1733                               "`impl Trait` not allowed outside of function \
1734                                and inherent method return types");
1735                     tcx.types.err
1736                 }
1737             }
1738             hir::TyPath(ref maybe_qself, ref path) => {
1739                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
1740                 let path_res = tcx.expect_resolution(ast_ty.id);
1741                 let base_ty_end = path.segments.len() - path_res.depth;
1742                 let opt_self_ty = maybe_qself.as_ref().map(|qself| {
1743                     self.ast_ty_to_ty(rscope, &qself.ty)
1744                 });
1745                 let (ty, def) = self.finish_resolving_def_to_ty(rscope,
1746                                                                 ast_ty.span,
1747                                                                 PathParamMode::Explicit,
1748                                                                 path_res.base_def,
1749                                                                 opt_self_ty,
1750                                                                 ast_ty.id,
1751                                                                 &path.segments[..base_ty_end],
1752                                                                 &path.segments[base_ty_end..]);
1753
1754                 // Write back the new resolution.
1755                 if path_res.depth != 0 {
1756                     tcx.def_map.borrow_mut().insert(ast_ty.id, PathResolution::new(def));
1757                 }
1758
1759                 ty
1760             }
1761             hir::TyFixedLengthVec(ref ty, ref e) => {
1762                 if let Ok(length) = eval_length(tcx.global_tcx(), &e, "array length") {
1763                     tcx.mk_array(self.ast_ty_to_ty(rscope, &ty), length)
1764                 } else {
1765                     self.tcx().types.err
1766                 }
1767             }
1768             hir::TyTypeof(ref _e) => {
1769                 span_err!(tcx.sess, ast_ty.span, E0516,
1770                       "`typeof` is a reserved keyword but unimplemented");
1771                 tcx.types.err
1772             }
1773             hir::TyInfer => {
1774                 // TyInfer also appears as the type of arguments or return
1775                 // values in a ExprClosure, or as
1776                 // the type of local variables. Both of these cases are
1777                 // handled specially and will not descend into this routine.
1778                 self.ty_infer(ast_ty.span)
1779             }
1780         };
1781
1782         cache.borrow_mut().insert(ast_ty.id, result_ty);
1783
1784         result_ty
1785     }
1786
1787     pub fn ty_of_arg(&self,
1788                      rscope: &RegionScope,
1789                      a: &hir::Arg,
1790                      expected_ty: Option<Ty<'tcx>>)
1791                      -> Ty<'tcx>
1792     {
1793         match a.ty.node {
1794             hir::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
1795             hir::TyInfer => self.ty_infer(a.ty.span),
1796             _ => self.ast_ty_to_ty(rscope, &a.ty),
1797         }
1798     }
1799
1800     pub fn ty_of_method(&self,
1801                         sig: &hir::MethodSig,
1802                         untransformed_self_ty: Ty<'tcx>,
1803                         anon_scope: Option<AnonTypeScope>)
1804                         -> (&'tcx ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory) {
1805         self.ty_of_method_or_bare_fn(sig.unsafety,
1806                                      sig.abi,
1807                                      Some(untransformed_self_ty),
1808                                      &sig.decl,
1809                                      None,
1810                                      anon_scope)
1811     }
1812
1813     pub fn ty_of_bare_fn(&self,
1814                          unsafety: hir::Unsafety,
1815                          abi: abi::Abi,
1816                          decl: &hir::FnDecl,
1817                          anon_scope: Option<AnonTypeScope>)
1818                          -> &'tcx ty::BareFnTy<'tcx> {
1819         self.ty_of_method_or_bare_fn(unsafety, abi, None, decl, None, anon_scope).0
1820     }
1821
1822     fn ty_of_method_or_bare_fn(&self,
1823                                unsafety: hir::Unsafety,
1824                                abi: abi::Abi,
1825                                opt_untransformed_self_ty: Option<Ty<'tcx>>,
1826                                decl: &hir::FnDecl,
1827                                arg_anon_scope: Option<AnonTypeScope>,
1828                                ret_anon_scope: Option<AnonTypeScope>)
1829                                -> (&'tcx ty::BareFnTy<'tcx>, ty::ExplicitSelfCategory)
1830     {
1831         debug!("ty_of_method_or_bare_fn");
1832
1833         // New region names that appear inside of the arguments of the function
1834         // declaration are bound to that function type.
1835         let rb = MaybeWithAnonTypes::new(BindingRscope::new(), arg_anon_scope);
1836
1837         // `implied_output_region` is the region that will be assumed for any
1838         // region parameters in the return type. In accordance with the rules for
1839         // lifetime elision, we can determine it in two ways. First (determined
1840         // here), if self is by-reference, then the implied output region is the
1841         // region of the self parameter.
1842         let (self_ty, explicit_self_category) = match (opt_untransformed_self_ty, decl.get_self()) {
1843             (Some(untransformed_self_ty), Some(explicit_self)) => {
1844                 let self_type = self.determine_self_type(&rb, untransformed_self_ty,
1845                                                          &explicit_self);
1846                 (Some(self_type.0), self_type.1)
1847             }
1848             _ => (None, ty::ExplicitSelfCategory::Static),
1849         };
1850
1851         // HACK(eddyb) replace the fake self type in the AST with the actual type.
1852         let arg_params = if self_ty.is_some() {
1853             &decl.inputs[1..]
1854         } else {
1855             &decl.inputs[..]
1856         };
1857         let arg_tys: Vec<Ty> =
1858             arg_params.iter().map(|a| self.ty_of_arg(&rb, a, None)).collect();
1859         let arg_pats: Vec<String> =
1860             arg_params.iter().map(|a| pprust::pat_to_string(&a.pat)).collect();
1861
1862         // Second, if there was exactly one lifetime (either a substitution or a
1863         // reference) in the arguments, then any anonymous regions in the output
1864         // have that lifetime.
1865         let implied_output_region = match explicit_self_category {
1866             ty::ExplicitSelfCategory::ByReference(region, _) => Ok(region),
1867             _ => self.find_implied_output_region(&arg_tys, arg_pats)
1868         };
1869
1870         let output_ty = match decl.output {
1871             hir::Return(ref output) =>
1872                 self.convert_ty_with_lifetime_elision(implied_output_region,
1873                                                       &output,
1874                                                       ret_anon_scope),
1875             hir::DefaultReturn(..) => self.tcx().mk_nil(),
1876         };
1877
1878         (self.tcx().mk_bare_fn(ty::BareFnTy {
1879             unsafety: unsafety,
1880             abi: abi,
1881             sig: ty::Binder(ty::FnSig {
1882                 inputs: self_ty.into_iter().chain(arg_tys).collect(),
1883                 output: output_ty,
1884                 variadic: decl.variadic
1885             }),
1886         }), explicit_self_category)
1887     }
1888
1889     fn determine_self_type<'a>(&self,
1890                                rscope: &RegionScope,
1891                                untransformed_self_ty: Ty<'tcx>,
1892                                explicit_self: &hir::ExplicitSelf)
1893                                -> (Ty<'tcx>, ty::ExplicitSelfCategory)
1894     {
1895         return match explicit_self.node {
1896             SelfKind::Value(..) => {
1897                 (untransformed_self_ty, ty::ExplicitSelfCategory::ByValue)
1898             }
1899             SelfKind::Region(ref lifetime, mutability) => {
1900                 let region =
1901                     self.opt_ast_region_to_region(
1902                                              rscope,
1903                                              explicit_self.span,
1904                                              lifetime);
1905                 (self.tcx().mk_ref(
1906                     self.tcx().mk_region(region),
1907                     ty::TypeAndMut {
1908                         ty: untransformed_self_ty,
1909                         mutbl: mutability
1910                     }),
1911                  ty::ExplicitSelfCategory::ByReference(region, mutability))
1912             }
1913             SelfKind::Explicit(ref ast_type, _) => {
1914                 let explicit_type = self.ast_ty_to_ty(rscope, &ast_type);
1915
1916                 // We wish to (for now) categorize an explicit self
1917                 // declaration like `self: SomeType` into either `self`,
1918                 // `&self`, `&mut self`, or `Box<self>`. We do this here
1919                 // by some simple pattern matching. A more precise check
1920                 // is done later in `check_method_self_type()`.
1921                 //
1922                 // Examples:
1923                 //
1924                 // ```
1925                 // impl Foo for &T {
1926                 //     // Legal declarations:
1927                 //     fn method1(self: &&T); // ExplicitSelfCategory::ByReference
1928                 //     fn method2(self: &T); // ExplicitSelfCategory::ByValue
1929                 //     fn method3(self: Box<&T>); // ExplicitSelfCategory::ByBox
1930                 //
1931                 //     // Invalid cases will be caught later by `check_method_self_type`:
1932                 //     fn method_err1(self: &mut T); // ExplicitSelfCategory::ByReference
1933                 // }
1934                 // ```
1935                 //
1936                 // To do the check we just count the number of "modifiers"
1937                 // on each type and compare them. If they are the same or
1938                 // the impl has more, we call it "by value". Otherwise, we
1939                 // look at the outermost modifier on the method decl and
1940                 // call it by-ref, by-box as appropriate. For method1, for
1941                 // example, the impl type has one modifier, but the method
1942                 // type has two, so we end up with
1943                 // ExplicitSelfCategory::ByReference.
1944
1945                 let impl_modifiers = count_modifiers(untransformed_self_ty);
1946                 let method_modifiers = count_modifiers(explicit_type);
1947
1948                 debug!("determine_explicit_self_category(self_info.untransformed_self_ty={:?} \
1949                        explicit_type={:?} \
1950                        modifiers=({},{})",
1951                        untransformed_self_ty,
1952                        explicit_type,
1953                        impl_modifiers,
1954                        method_modifiers);
1955
1956                 let category = if impl_modifiers >= method_modifiers {
1957                     ty::ExplicitSelfCategory::ByValue
1958                 } else {
1959                     match explicit_type.sty {
1960                         ty::TyRef(r, mt) => ty::ExplicitSelfCategory::ByReference(*r, mt.mutbl),
1961                         ty::TyBox(_) => ty::ExplicitSelfCategory::ByBox,
1962                         _ => ty::ExplicitSelfCategory::ByValue,
1963                     }
1964                 };
1965
1966                 (explicit_type, category)
1967             }
1968         };
1969
1970         fn count_modifiers(ty: Ty) -> usize {
1971             match ty.sty {
1972                 ty::TyRef(_, mt) => count_modifiers(mt.ty) + 1,
1973                 ty::TyBox(t) => count_modifiers(t) + 1,
1974                 _ => 0,
1975             }
1976         }
1977     }
1978
1979     pub fn ty_of_closure(&self,
1980         unsafety: hir::Unsafety,
1981         decl: &hir::FnDecl,
1982         abi: abi::Abi,
1983         expected_sig: Option<ty::FnSig<'tcx>>)
1984         -> ty::ClosureTy<'tcx>
1985     {
1986         debug!("ty_of_closure(expected_sig={:?})",
1987                expected_sig);
1988
1989         // new region names that appear inside of the fn decl are bound to
1990         // that function type
1991         let rb = rscope::BindingRscope::new();
1992
1993         let input_tys: Vec<_> = decl.inputs.iter().enumerate().map(|(i, a)| {
1994             let expected_arg_ty = expected_sig.as_ref().and_then(|e| {
1995                 // no guarantee that the correct number of expected args
1996                 // were supplied
1997                 if i < e.inputs.len() {
1998                     Some(e.inputs[i])
1999                 } else {
2000                     None
2001                 }
2002             });
2003             self.ty_of_arg(&rb, a, expected_arg_ty)
2004         }).collect();
2005
2006         let expected_ret_ty = expected_sig.map(|e| e.output);
2007
2008         let is_infer = match decl.output {
2009             hir::Return(ref output) if output.node == hir::TyInfer => true,
2010             hir::DefaultReturn(..) => true,
2011             _ => false
2012         };
2013
2014         let output_ty = match decl.output {
2015             _ if is_infer && expected_ret_ty.is_some() =>
2016                 expected_ret_ty.unwrap(),
2017             _ if is_infer => self.ty_infer(decl.output.span()),
2018             hir::Return(ref output) =>
2019                 self.ast_ty_to_ty(&rb, &output),
2020             hir::DefaultReturn(..) => bug!(),
2021         };
2022
2023         debug!("ty_of_closure: input_tys={:?}", input_tys);
2024         debug!("ty_of_closure: output_ty={:?}", output_ty);
2025
2026         ty::ClosureTy {
2027             unsafety: unsafety,
2028             abi: abi,
2029             sig: ty::Binder(ty::FnSig {inputs: input_tys,
2030                                        output: output_ty,
2031                                        variadic: decl.variadic}),
2032         }
2033     }
2034
2035     fn conv_object_ty_poly_trait_ref(&self,
2036         rscope: &RegionScope,
2037         span: Span,
2038         ast_bounds: &[hir::TyParamBound])
2039         -> Ty<'tcx>
2040     {
2041         let mut partitioned_bounds = partition_bounds(self.tcx(), span, &ast_bounds[..]);
2042
2043         let trait_bound = if !partitioned_bounds.trait_bounds.is_empty() {
2044             partitioned_bounds.trait_bounds.remove(0)
2045         } else {
2046             span_err!(self.tcx().sess, span, E0224,
2047                       "at least one non-builtin trait is required for an object type");
2048             return self.tcx().types.err;
2049         };
2050
2051         let trait_ref = &trait_bound.trait_ref;
2052         let trait_def_id = self.trait_def_id(trait_ref);
2053         self.trait_path_to_object_type(rscope,
2054                                        trait_ref.path.span,
2055                                        PathParamMode::Explicit,
2056                                        trait_def_id,
2057                                        trait_ref.ref_id,
2058                                        trait_ref.path.segments.last().unwrap(),
2059                                        span,
2060                                        partitioned_bounds)
2061     }
2062
2063     /// Given the bounds on an object, determines what single region bound (if any) we can
2064     /// use to summarize this type. The basic idea is that we will use the bound the user
2065     /// provided, if they provided one, and otherwise search the supertypes of trait bounds
2066     /// for region bounds. It may be that we can derive no bound at all, in which case
2067     /// we return `None`.
2068     fn compute_object_lifetime_bound(&self,
2069         span: Span,
2070         explicit_region_bounds: &[&hir::Lifetime],
2071         principal_trait_ref: ty::PolyExistentialTraitRef<'tcx>,
2072         builtin_bounds: ty::BuiltinBounds)
2073         -> Option<ty::Region> // if None, use the default
2074     {
2075         let tcx = self.tcx();
2076
2077         debug!("compute_opt_region_bound(explicit_region_bounds={:?}, \
2078                principal_trait_ref={:?}, builtin_bounds={:?})",
2079                explicit_region_bounds,
2080                principal_trait_ref,
2081                builtin_bounds);
2082
2083         if explicit_region_bounds.len() > 1 {
2084             span_err!(tcx.sess, explicit_region_bounds[1].span, E0226,
2085                 "only a single explicit lifetime bound is permitted");
2086         }
2087
2088         if !explicit_region_bounds.is_empty() {
2089             // Explicitly specified region bound. Use that.
2090             let r = explicit_region_bounds[0];
2091             return Some(ast_region_to_region(tcx, r));
2092         }
2093
2094         if let Err(ErrorReported) =
2095                 self.ensure_super_predicates(span, principal_trait_ref.def_id()) {
2096             return Some(ty::ReStatic);
2097         }
2098
2099         // No explicit region bound specified. Therefore, examine trait
2100         // bounds and see if we can derive region bounds from those.
2101         let derived_region_bounds =
2102             object_region_bounds(tcx, principal_trait_ref, builtin_bounds);
2103
2104         // If there are no derived region bounds, then report back that we
2105         // can find no region bound. The caller will use the default.
2106         if derived_region_bounds.is_empty() {
2107             return None;
2108         }
2109
2110         // If any of the derived region bounds are 'static, that is always
2111         // the best choice.
2112         if derived_region_bounds.iter().any(|r| ty::ReStatic == *r) {
2113             return Some(ty::ReStatic);
2114         }
2115
2116         // Determine whether there is exactly one unique region in the set
2117         // of derived region bounds. If so, use that. Otherwise, report an
2118         // error.
2119         let r = derived_region_bounds[0];
2120         if derived_region_bounds[1..].iter().any(|r1| r != *r1) {
2121             span_err!(tcx.sess, span, E0227,
2122                       "ambiguous lifetime bound, explicit lifetime bound required");
2123         }
2124         return Some(r);
2125     }
2126 }
2127
2128 pub struct PartitionedBounds<'a> {
2129     pub builtin_bounds: ty::BuiltinBounds,
2130     pub trait_bounds: Vec<&'a hir::PolyTraitRef>,
2131     pub region_bounds: Vec<&'a hir::Lifetime>,
2132 }
2133
2134 /// Divides a list of bounds from the AST into three groups: builtin bounds (Copy, Sized etc),
2135 /// general trait bounds, and region bounds.
2136 pub fn partition_bounds<'a, 'b, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
2137                                             _span: Span,
2138                                             ast_bounds: &'b [hir::TyParamBound])
2139                                             -> PartitionedBounds<'b>
2140 {
2141     let mut builtin_bounds = ty::BuiltinBounds::empty();
2142     let mut region_bounds = Vec::new();
2143     let mut trait_bounds = Vec::new();
2144     for ast_bound in ast_bounds {
2145         match *ast_bound {
2146             hir::TraitTyParamBound(ref b, hir::TraitBoundModifier::None) => {
2147                 match tcx.expect_def(b.trait_ref.ref_id) {
2148                     Def::Trait(trait_did) => {
2149                         if tcx.try_add_builtin_trait(trait_did,
2150                                                      &mut builtin_bounds) {
2151                             let segments = &b.trait_ref.path.segments;
2152                             let parameters = &segments[segments.len() - 1].parameters;
2153                             if !parameters.types().is_empty() {
2154                                 check_type_argument_count(tcx, b.trait_ref.path.span,
2155                                                           parameters.types().len(), &[]);
2156                             }
2157                             if !parameters.lifetimes().is_empty() {
2158                                 report_lifetime_number_error(tcx, b.trait_ref.path.span,
2159                                                              parameters.lifetimes().len(), 0);
2160                             }
2161                             continue; // success
2162                         }
2163                     }
2164                     _ => {
2165                         // Not a trait? that's an error, but it'll get
2166                         // reported later.
2167                     }
2168                 }
2169                 trait_bounds.push(b);
2170             }
2171             hir::TraitTyParamBound(_, hir::TraitBoundModifier::Maybe) => {}
2172             hir::RegionTyParamBound(ref l) => {
2173                 region_bounds.push(l);
2174             }
2175         }
2176     }
2177
2178     PartitionedBounds {
2179         builtin_bounds: builtin_bounds,
2180         trait_bounds: trait_bounds,
2181         region_bounds: region_bounds,
2182     }
2183 }
2184
2185 fn check_type_argument_count(tcx: TyCtxt, span: Span, supplied: usize,
2186                              ty_param_defs: &[ty::TypeParameterDef]) {
2187     let accepted = ty_param_defs.len();
2188     let required = ty_param_defs.iter().take_while(|x| x.default.is_none()) .count();
2189     if supplied < required {
2190         let expected = if required < accepted {
2191             "expected at least"
2192         } else {
2193             "expected"
2194         };
2195         struct_span_err!(tcx.sess, span, E0243, "wrong number of type arguments")
2196             .span_label(
2197                 span,
2198                 &format!("{} {} type arguments, found {}", expected, required, supplied)
2199             )
2200             .emit();
2201     } else if supplied > accepted {
2202         let expected = if required == 0 {
2203             "expected no".to_string()
2204         } else if required < accepted {
2205             format!("expected at most {}", accepted)
2206         } else {
2207             format!("expected {}", accepted)
2208         };
2209
2210         struct_span_err!(tcx.sess, span, E0244, "wrong number of type arguments")
2211             .span_label(
2212                 span,
2213                 &format!("{} type arguments, found {}", expected, supplied)
2214             )
2215             .emit();
2216     }
2217 }
2218
2219 fn report_lifetime_number_error(tcx: TyCtxt, span: Span, number: usize, expected: usize) {
2220     let label = if number < expected {
2221         if expected == 1 {
2222             format!("expected {} lifetime parameter", expected)
2223         } else {
2224             format!("expected {} lifetime parameters", expected)
2225         }
2226     } else {
2227         let additional = number - expected;
2228         if additional == 1 {
2229             "unexpected lifetime parameter".to_string()
2230         } else {
2231             format!("{} unexpected lifetime parameters", additional)
2232         }
2233     };
2234     struct_span_err!(tcx.sess, span, E0107,
2235                      "wrong number of lifetime parameters: expected {}, found {}",
2236                      expected, number)
2237         .span_label(span, &label)
2238         .emit();
2239 }
2240
2241 // A helper struct for conveniently grouping a set of bounds which we pass to
2242 // and return from functions in multiple places.
2243 #[derive(PartialEq, Eq, Clone, Debug)]
2244 pub struct Bounds<'tcx> {
2245     pub region_bounds: Vec<ty::Region>,
2246     pub builtin_bounds: ty::BuiltinBounds,
2247     pub trait_bounds: Vec<ty::PolyTraitRef<'tcx>>,
2248     pub projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
2249 }
2250
2251 impl<'a, 'gcx, 'tcx> Bounds<'tcx> {
2252     pub fn predicates(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, param_ty: Ty<'tcx>)
2253                       -> Vec<ty::Predicate<'tcx>>
2254     {
2255         let mut vec = Vec::new();
2256
2257         for builtin_bound in &self.builtin_bounds {
2258             match tcx.trait_ref_for_builtin_bound(builtin_bound, param_ty) {
2259                 Ok(trait_ref) => { vec.push(trait_ref.to_predicate()); }
2260                 Err(ErrorReported) => { }
2261             }
2262         }
2263
2264         for &region_bound in &self.region_bounds {
2265             // account for the binder being introduced below; no need to shift `param_ty`
2266             // because, at present at least, it can only refer to early-bound regions
2267             let region_bound = ty::fold::shift_region(region_bound, 1);
2268             vec.push(ty::Binder(ty::OutlivesPredicate(param_ty, region_bound)).to_predicate());
2269         }
2270
2271         for bound_trait_ref in &self.trait_bounds {
2272             vec.push(bound_trait_ref.to_predicate());
2273         }
2274
2275         for projection in &self.projection_bounds {
2276             vec.push(projection.to_predicate());
2277         }
2278
2279         vec
2280     }
2281 }