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`.
  14
  15 use rustc_data_structures::accumulate_vec::AccumulateVec;
  16 use hir::{self, GenericArg};
  17 use hir::def::Def;
  18 use hir::def_id::DefId;
  19 use middle::resolve_lifetime as rl;
  20 use namespace::Namespace;
  21 use rustc::ty::subst::{Subst, Substs};
  22 use rustc::traits;
  23 use rustc::ty::{self, Ty, TyCtxt, ToPredicate, TypeFoldable};
  24 use rustc::ty::GenericParamDefKind;
  25 use rustc::ty::wf::object_region_bounds;
  26 use rustc_target::spec::abi;
  27 use std::slice;
  28 use require_c_abi_if_variadic;
  29 use util::common::ErrorReported;
  30 use util::nodemap::{FxHashSet, FxHashMap};
  31 use errors::FatalError;
  32
  33 use std::iter;
  34 use syntax::ast;
  35 use syntax::feature_gate::{GateIssue, emit_feature_err};
  36 use syntax_pos::Span;
  37
  38 pub trait AstConv<'gcx, 'tcx> {
  39     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>;
  40
  41     /// Returns the set of bounds in scope for the type parameter with
  42     /// the given id.
  43     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId)
  44                                  -> ty::GenericPredicates<'tcx>;
  45
  46     /// What lifetime should we use when a lifetime is omitted (and not elided)?
  47     fn re_infer(&self, span: Span, _def: Option<&ty::GenericParamDef>)
  48                 -> Option<ty::Region<'tcx>>;
  49
  50     /// What type should we use when a type is omitted?
  51     fn ty_infer(&self, span: Span) -> Ty<'tcx>;
  52
  53     /// Same as ty_infer, but with a known type parameter definition.
  54     fn ty_infer_for_def(&self,
  55                         _def: &ty::GenericParamDef,
  56                         span: Span) -> Ty<'tcx> {
  57         self.ty_infer(span)
  58     }
  59
  60     /// Projecting an associated type from a (potentially)
  61     /// higher-ranked trait reference is more complicated, because of
  62     /// the possibility of late-bound regions appearing in the
  63     /// associated type binding. This is not legal in function
  64     /// signatures for that reason. In a function body, we can always
  65     /// handle it because we can use inference variables to remove the
  66     /// late-bound regions.
  67     fn projected_ty_from_poly_trait_ref(&self,
  68                                         span: Span,
  69                                         item_def_id: DefId,
  70                                         poly_trait_ref: ty::PolyTraitRef<'tcx>)
  71                                         -> Ty<'tcx>;
  72
  73     /// Normalize an associated type coming from the user.
  74     fn normalize_ty(&self, span: Span, ty: Ty<'tcx>) -> Ty<'tcx>;
  75
  76     /// Invoked when we encounter an error from some prior pass
  77     /// (e.g. resolve) that is translated into a ty-error. This is
  78     /// used to help suppress derived errors typeck might otherwise
  79     /// report.
  80     fn set_tainted_by_errors(&self);
  81
  82     fn record_ty(&self, hir_id: hir::HirId, ty: Ty<'tcx>, span: Span);
  83 }
  84
  85 struct ConvertedBinding<'tcx> {
  86     item_name: ast::Ident,
  87     ty: Ty<'tcx>,
  88     span: Span,
  89 }
  90
  91 struct ParamRange {
  92     required: usize,
  93     accepted: usize
  94 }
  95
  96 /// Dummy type used for the `Self` of a `TraitRef` created for converting
  97 /// a trait object, and which gets removed in `ExistentialTraitRef`.
  98 /// This type must not appear anywhere in other converted types.
  99 const TRAIT_OBJECT_DUMMY_SELF: ty::TypeVariants<'static> = ty::TyInfer(ty::FreshTy(0));
 100
 101 impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
 102     pub fn ast_region_to_region(&self,
 103         lifetime: &hir::Lifetime,
 104         def: Option<&ty::GenericParamDef>)
 105         -> ty::Region<'tcx>
 106     {
 107         let tcx = self.tcx();
 108         let lifetime_name = |def_id| {
 109             tcx.hir.name(tcx.hir.as_local_node_id(def_id).unwrap()).as_interned_str()
 110         };
 111
 112         let hir_id = tcx.hir.node_to_hir_id(lifetime.id);
 113         let r = match tcx.named_region(hir_id) {
 114             Some(rl::Region::Static) => {
 115                 tcx.types.re_static
 116             }
 117
 118             Some(rl::Region::LateBound(debruijn, id, _)) => {
 119                 let name = lifetime_name(id);
 120                 tcx.mk_region(ty::ReLateBound(debruijn,
 121                     ty::BrNamed(id, name)))
 122             }
 123
 124             Some(rl::Region::LateBoundAnon(debruijn, index)) => {
 125                 tcx.mk_region(ty::ReLateBound(debruijn, ty::BrAnon(index)))
 126             }
 127
 128             Some(rl::Region::EarlyBound(index, id, _)) => {
 129                 let name = lifetime_name(id);
 130                 tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
 131                     def_id: id,
 132                     index,
 133                     name,
 134                 }))
 135             }
 136
 137             Some(rl::Region::Free(scope, id)) => {
 138                 let name = lifetime_name(id);
 139                 tcx.mk_region(ty::ReFree(ty::FreeRegion {
 140                     scope,
 141                     bound_region: ty::BrNamed(id, name)
 142                 }))
 143
 144                     // (*) -- not late-bound, won't change
 145             }
 146
 147             None => {
 148                 self.re_infer(lifetime.span, def)
 149                     .unwrap_or_else(|| {
 150                         // This indicates an illegal lifetime
 151                         // elision. `resolve_lifetime` should have
 152                         // reported an error in this case -- but if
 153                         // not, let's error out.
 154                         tcx.sess.delay_span_bug(lifetime.span, "unelided lifetime in signature");
 155
 156                         // Supply some dummy value. We don't have an
 157                         // `re_error`, annoyingly, so use `'static`.
 158                         tcx.types.re_static
 159                     })
 160             }
 161         };
 162
 163         debug!("ast_region_to_region(lifetime={:?}) yields {:?}",
 164                 lifetime,
 165                 r);
 166
 167         r
 168     }
 169
 170     /// Given a path `path` that refers to an item `I` with the declared generics `decl_generics`,
 171     /// returns an appropriate set of substitutions for this particular reference to `I`.
 172     pub fn ast_path_substs_for_ty(&self,
 173         span: Span,
 174         def_id: DefId,
 175         item_segment: &hir::PathSegment)
 176         -> &'tcx Substs<'tcx>
 177     {
 178
 179         let (substs, assoc_bindings) =
 180             item_segment.with_generic_args(|generic_args| {
 181                 self.create_substs_for_ast_path(
 182                     span,
 183                     def_id,
 184                     generic_args,
 185                     item_segment.infer_types,
 186                     None)
 187             });
 188
 189         assoc_bindings.first().map(|b| self.prohibit_projection(b.span));
 190
 191         substs
 192     }
 193
 194     /// Given the type/region arguments provided to some path (along with
 195     /// an implicit Self, if this is a trait reference) returns the complete
 196     /// set of substitutions. This may involve applying defaulted type parameters.
 197     ///
 198     /// Note that the type listing given here is *exactly* what the user provided.
 199     fn create_substs_for_ast_path(&self,
 200         span: Span,
 201         def_id: DefId,
 202         generic_args: &hir::GenericArgs,
 203         infer_types: bool,
 204         self_ty: Option<Ty<'tcx>>)
 205         -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
 206     {
 207         let tcx = self.tcx();
 208
 209         debug!("create_substs_for_ast_path(def_id={:?}, self_ty={:?}, \
 210                generic_args={:?})",
 211                def_id, self_ty, generic_args);
 212
 213         // If the type is parameterized by this region, then replace this
 214         // region with the current anon region binding (in other words,
 215         // whatever & would get replaced with).
 216
 217         // FIXME(varkor): Separating out the parameters is messy.
 218         let lifetimes: Vec<_> = generic_args.args.iter().filter_map(|arg| match arg {
 219             GenericArg::Lifetime(lt) => Some(lt),
 220             _ => None,
 221         }).collect();
 222         let types: Vec<_> = generic_args.args.iter().filter_map(|arg| match arg {
 223             GenericArg::Type(ty) => Some(ty),
 224             _ => None,
 225         }).collect();
 226         let lt_provided = lifetimes.len();
 227         let ty_provided = types.len();
 228
 229         let decl_generics = tcx.generics_of(def_id);
 230         let mut lt_accepted = 0;
 231         let mut ty_params = ParamRange { required: 0, accepted: 0 };
 232         for param in &decl_generics.params {
 233             match param.kind {
 234                 GenericParamDefKind::Lifetime => {
 235                     lt_accepted += 1;
 236                 }
 237                 GenericParamDefKind::Type { has_default, .. } => {
 238                     ty_params.accepted += 1;
 239                     if !has_default {
 240                         ty_params.required += 1;
 241                     }
 242                 }
 243             };
 244         }
 245         if self_ty.is_some() {
 246             ty_params.required -= 1;
 247             ty_params.accepted -= 1;
 248         }
 249
 250         if lt_accepted != lt_provided {
 251             report_lifetime_number_error(tcx, span, lt_provided, lt_accepted);
 252         }
 253
 254         // If a self-type was declared, one should be provided.
 255         assert_eq!(decl_generics.has_self, self_ty.is_some());
 256
 257         // Check the number of type parameters supplied by the user.
 258         if !infer_types || ty_provided > ty_params.required {
 259             check_type_argument_count(tcx, span, ty_provided, ty_params);
 260         }
 261
 262         let is_object = self_ty.map_or(false, |ty| ty.sty == TRAIT_OBJECT_DUMMY_SELF);
 263         let default_needs_object_self = |param: &ty::GenericParamDef| {
 264             if let GenericParamDefKind::Type { has_default, .. } = param.kind {
 265                 if is_object && has_default {
 266                     if tcx.at(span).type_of(param.def_id).has_self_ty() {
 267                         // There is no suitable inference default for a type parameter
 268                         // that references self, in an object type.
 269                         return true;
 270                     }
 271                 }
 272             }
 273
 274             false
 275         };
 276
 277         let own_self = self_ty.is_some() as usize;
 278         let substs = Substs::for_item(tcx, def_id, |param, substs| {
 279             match param.kind {
 280                 GenericParamDefKind::Lifetime => {
 281                     let i = param.index as usize - own_self;
 282                     if let Some(lt) = lifetimes.get(i) {
 283                         self.ast_region_to_region(lt, Some(param)).into()
 284                     } else {
 285                         tcx.types.re_static.into()
 286                     }
 287                 }
 288                 GenericParamDefKind::Type { has_default, .. } => {
 289                     let i = param.index as usize;
 290
 291                     // Handle Self first, so we can adjust the index to match the AST.
 292                     if let (0, Some(ty)) = (i, self_ty) {
 293                         return ty.into();
 294                     }
 295
 296                     let i = i - (lt_accepted + own_self);
 297                     if i < ty_provided {
 298                         // A provided type parameter.
 299                         self.ast_ty_to_ty(&types[i]).into()
 300                     } else if infer_types {
 301                         // No type parameters were provided, we can infer all.
 302                         if !default_needs_object_self(param) {
 303                             self.ty_infer_for_def(param, span).into()
 304                         } else {
 305                             self.ty_infer(span).into()
 306                         }
 307                     } else if has_default {
 308                         // No type parameter provided, but a default exists.
 309
 310                         // If we are converting an object type, then the
 311                         // `Self` parameter is unknown. However, some of the
 312                         // other type parameters may reference `Self` in their
 313                         // defaults. This will lead to an ICE if we are not
 314                         // careful!
 315                         if default_needs_object_self(param) {
 316                             struct_span_err!(tcx.sess, span, E0393,
 317                                              "the type parameter `{}` must be explicitly \
 318                                              specified",
 319                                              param.name)
 320                                 .span_label(span,
 321                                             format!("missing reference to `{}`", param.name))
 322                                 .note(&format!("because of the default `Self` reference, \
 323                                                 type parameters must be specified on object \
 324                                                 types"))
 325                                 .emit();
 326                             tcx.types.err.into()
 327                         } else {
 328                             // This is a default type parameter.
 329                             self.normalize_ty(
 330                                 span,
 331                                 tcx.at(span).type_of(param.def_id)
 332                                     .subst_spanned(tcx, substs, Some(span))
 333                             ).into()
 334                         }
 335                     } else {
 336                         // We've already errored above about the mismatch.
 337                         tcx.types.err.into()
 338                     }
 339                 }
 340             }
 341         });
 342
 343         let assoc_bindings = generic_args.bindings.iter().map(|binding| {
 344             ConvertedBinding {
 345                 item_name: binding.ident,
 346                 ty: self.ast_ty_to_ty(&binding.ty),
 347                 span: binding.span,
 348             }
 349         }).collect();
 350
 351         debug!("create_substs_for_ast_path(decl_generics={:?}, self_ty={:?}) -> {:?}",
 352                decl_generics, self_ty, substs);
 353
 354         (substs, assoc_bindings)
 355     }
 356
 357     /// Instantiates the path for the given trait reference, assuming that it's
 358     /// bound to a valid trait type. Returns the def_id for the defining trait.
 359     /// The type _cannot_ be a type other than a trait type.
 360     ///
 361     /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T=X>`
 362     /// are disallowed. Otherwise, they are pushed onto the vector given.
 363     pub fn instantiate_mono_trait_ref(&self,
 364         trait_ref: &hir::TraitRef,
 365         self_ty: Ty<'tcx>)
 366         -> ty::TraitRef<'tcx>
 367     {
 368         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 369
 370         let trait_def_id = self.trait_def_id(trait_ref);
 371         self.ast_path_to_mono_trait_ref(trait_ref.path.span,
 372                                         trait_def_id,
 373                                         self_ty,
 374                                         trait_ref.path.segments.last().unwrap())
 375     }
 376
 377     /// Get the DefId of the given trait ref. It _must_ actually be a trait.
 378     fn trait_def_id(&self, trait_ref: &hir::TraitRef) -> DefId {
 379         let path = &trait_ref.path;
 380         match path.def {
 381             Def::Trait(trait_def_id) => trait_def_id,
 382             Def::TraitAlias(alias_def_id) => alias_def_id,
 383             Def::Err => {
 384                 FatalError.raise();
 385             }
 386             _ => unreachable!(),
 387         }
 388     }
 389
 390     /// The given `trait_ref` must actually be trait.
 391     pub(super) fn instantiate_poly_trait_ref_inner(&self,
 392         trait_ref: &hir::TraitRef,
 393         self_ty: Ty<'tcx>,
 394         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>,
 395         speculative: bool)
 396         -> ty::PolyTraitRef<'tcx>
 397     {
 398         let trait_def_id = self.trait_def_id(trait_ref);
 399
 400         debug!("ast_path_to_poly_trait_ref({:?}, def_id={:?})", trait_ref, trait_def_id);
 401
 402         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 403
 404         let (substs, assoc_bindings) =
 405             self.create_substs_for_ast_trait_ref(trait_ref.path.span,
 406                                                  trait_def_id,
 407                                                  self_ty,
 408                                                  trait_ref.path.segments.last().unwrap());
 409         let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs));
 410
 411         let mut dup_bindings = FxHashMap::default();
 412         poly_projections.extend(assoc_bindings.iter().filter_map(|binding| {
 413             // specify type to assert that error was already reported in Err case:
 414             let predicate: Result<_, ErrorReported> =
 415                 self.ast_type_binding_to_poly_projection_predicate(
 416                     trait_ref.ref_id, poly_trait_ref, binding, speculative, &mut dup_bindings);
 417             predicate.ok() // ok to ignore Err() because ErrorReported (see above)
 418         }));
 419
 420         debug!("ast_path_to_poly_trait_ref({:?}, projections={:?}) -> {:?}",
 421                trait_ref, poly_projections, poly_trait_ref);
 422         poly_trait_ref
 423     }
 424
 425     pub fn instantiate_poly_trait_ref(&self,
 426         poly_trait_ref: &hir::PolyTraitRef,
 427         self_ty: Ty<'tcx>,
 428         poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
 429         -> ty::PolyTraitRef<'tcx>
 430     {
 431         self.instantiate_poly_trait_ref_inner(&poly_trait_ref.trait_ref, self_ty,
 432                                               poly_projections, false)
 433     }
 434
 435     fn ast_path_to_mono_trait_ref(&self,
 436                                   span: Span,
 437                                   trait_def_id: DefId,
 438                                   self_ty: Ty<'tcx>,
 439                                   trait_segment: &hir::PathSegment)
 440                                   -> ty::TraitRef<'tcx>
 441     {
 442         let (substs, assoc_bindings) =
 443             self.create_substs_for_ast_trait_ref(span,
 444                                                  trait_def_id,
 445                                                  self_ty,
 446                                                  trait_segment);
 447         assoc_bindings.first().map(|b| self.prohibit_projection(b.span));
 448         ty::TraitRef::new(trait_def_id, substs)
 449     }
 450
 451     fn create_substs_for_ast_trait_ref(&self,
 452                                        span: Span,
 453                                        trait_def_id: DefId,
 454                                        self_ty: Ty<'tcx>,
 455                                        trait_segment: &hir::PathSegment)
 456                                        -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
 457     {
 458         debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
 459                trait_segment);
 460
 461         let trait_def = self.tcx().trait_def(trait_def_id);
 462
 463         if !self.tcx().features().unboxed_closures &&
 464             trait_segment.with_generic_args(|generic_args| generic_args.parenthesized)
 465             != trait_def.paren_sugar {
 466             // For now, require that parenthetical notation be used only with `Fn()` etc.
 467             let msg = if trait_def.paren_sugar {
 468                 "the precise format of `Fn`-family traits' type parameters is subject to change. \
 469                  Use parenthetical notation (Fn(Foo, Bar) -> Baz) instead"
 470             } else {
 471                 "parenthetical notation is only stable when used with `Fn`-family traits"
 472             };
 473             emit_feature_err(&self.tcx().sess.parse_sess, "unboxed_closures",
 474                              span, GateIssue::Language, msg);
 475         }
 476
 477         trait_segment.with_generic_args(|generic_args| {
 478             self.create_substs_for_ast_path(span,
 479                                             trait_def_id,
 480                                             generic_args,
 481                                             trait_segment.infer_types,
 482                                             Some(self_ty))
 483         })
 484     }
 485
 486     fn trait_defines_associated_type_named(&self,
 487                                            trait_def_id: DefId,
 488                                            assoc_name: ast::Ident)
 489                                            -> bool
 490     {
 491         self.tcx().associated_items(trait_def_id).any(|item| {
 492             item.kind == ty::AssociatedKind::Type &&
 493             self.tcx().hygienic_eq(assoc_name, item.ident, trait_def_id)
 494         })
 495     }
 496
 497     fn ast_type_binding_to_poly_projection_predicate(
 498         &self,
 499         ref_id: ast::NodeId,
 500         trait_ref: ty::PolyTraitRef<'tcx>,
 501         binding: &ConvertedBinding<'tcx>,
 502         speculative: bool,
 503         dup_bindings: &mut FxHashMap<DefId, Span>)
 504         -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
 505     {
 506         let tcx = self.tcx();
 507
 508         if !speculative {
 509             // Given something like `U : SomeTrait<T=X>`, we want to produce a
 510             // predicate like `<U as SomeTrait>::T = X`. This is somewhat
 511             // subtle in the event that `T` is defined in a supertrait of
 512             // `SomeTrait`, because in that case we need to upcast.
 513             //
 514             // That is, consider this case:
 515             //
 516             // ```
 517             // trait SubTrait : SuperTrait<int> { }
 518             // trait SuperTrait<A> { type T; }
 519             //
 520             // ... B : SubTrait<T=foo> ...
 521             // ```
 522             //
 523             // We want to produce `<B as SuperTrait<int>>::T == foo`.
 524
 525             // Find any late-bound regions declared in `ty` that are not
 526             // declared in the trait-ref. These are not wellformed.
 527             //
 528             // Example:
 529             //
 530             //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
 531             //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
 532             let late_bound_in_trait_ref = tcx.collect_constrained_late_bound_regions(&trait_ref);
 533             let late_bound_in_ty =
 534                 tcx.collect_referenced_late_bound_regions(&ty::Binder::bind(binding.ty));
 535             debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
 536             debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
 537             for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
 538                 let br_name = match *br {
 539                     ty::BrNamed(_, name) => name,
 540                     _ => {
 541                         span_bug!(
 542                             binding.span,
 543                             "anonymous bound region {:?} in binding but not trait ref",
 544                             br);
 545                     }
 546                 };
 547                 struct_span_err!(tcx.sess,
 548                                 binding.span,
 549                                 E0582,
 550                                 "binding for associated type `{}` references lifetime `{}`, \
 551                                 which does not appear in the trait input types",
 552                                 binding.item_name, br_name)
 553                     .emit();
 554             }
 555         }
 556
 557         let candidate = if self.trait_defines_associated_type_named(trait_ref.def_id(),
 558                                                                     binding.item_name) {
 559             // Simple case: X is defined in the current trait.
 560             Ok(trait_ref)
 561         } else {
 562             // Otherwise, we have to walk through the supertraits to find
 563             // those that do.
 564             let candidates = traits::supertraits(tcx, trait_ref).filter(|r| {
 565                 self.trait_defines_associated_type_named(r.def_id(), binding.item_name)
 566             });
 567             self.one_bound_for_assoc_type(candidates, &trait_ref.to_string(),
 568                                           binding.item_name, binding.span)
 569         }?;
 570
 571         let (assoc_ident, def_scope) =
 572             tcx.adjust_ident(binding.item_name, candidate.def_id(), ref_id);
 573         let assoc_ty = tcx.associated_items(candidate.def_id()).find(|i| {
 574             i.kind == ty::AssociatedKind::Type && i.ident.modern() == assoc_ident
 575         }).expect("missing associated type");
 576
 577         if !assoc_ty.vis.is_accessible_from(def_scope, tcx) {
 578             let msg = format!("associated type `{}` is private", binding.item_name);
 579             tcx.sess.span_err(binding.span, &msg);
 580         }
 581         tcx.check_stability(assoc_ty.def_id, Some(ref_id), binding.span);
 582
 583         if !speculative {
 584             dup_bindings.entry(assoc_ty.def_id)
 585                 .and_modify(|prev_span| {
 586                     let mut err = self.tcx().struct_span_lint_node(
 587                         ::rustc::lint::builtin::DUPLICATE_ASSOCIATED_TYPE_BINDINGS,
 588                         ref_id,
 589                         binding.span,
 590                         &format!("associated type binding `{}` specified more than once",
 591                                 binding.item_name)
 592                     );
 593                     err.span_label(binding.span, "used more than once");
 594                     err.span_label(*prev_span, format!("first use of `{}`", binding.item_name));
 595                     err.emit();
 596                 })
 597                 .or_insert(binding.span);
 598         }
 599
 600         Ok(candidate.map_bound(|trait_ref| {
 601             ty::ProjectionPredicate {
 602                 projection_ty: ty::ProjectionTy::from_ref_and_name(
 603                     tcx,
 604                     trait_ref,
 605                     binding.item_name,
 606                 ),
 607                 ty: binding.ty,
 608             }
 609         }))
 610     }
 611
 612     fn ast_path_to_ty(&self,
 613         span: Span,
 614         did: DefId,
 615         item_segment: &hir::PathSegment)
 616         -> Ty<'tcx>
 617     {
 618         let substs = self.ast_path_substs_for_ty(span, did, item_segment);
 619         self.normalize_ty(
 620             span,
 621             self.tcx().at(span).type_of(did).subst(self.tcx(), substs)
 622         )
 623     }
 624
 625     /// Transform a PolyTraitRef into a PolyExistentialTraitRef by
 626     /// removing the dummy Self type (TRAIT_OBJECT_DUMMY_SELF).
 627     fn trait_ref_to_existential(&self, trait_ref: ty::TraitRef<'tcx>)
 628                                 -> ty::ExistentialTraitRef<'tcx> {
 629         assert_eq!(trait_ref.self_ty().sty, TRAIT_OBJECT_DUMMY_SELF);
 630         ty::ExistentialTraitRef::erase_self_ty(self.tcx(), trait_ref)
 631     }
 632
 633     fn conv_object_ty_poly_trait_ref(&self,
 634         span: Span,
 635         trait_bounds: &[hir::PolyTraitRef],
 636         lifetime: &hir::Lifetime)
 637         -> Ty<'tcx>
 638     {
 639         let tcx = self.tcx();
 640
 641         if trait_bounds.is_empty() {
 642             span_err!(tcx.sess, span, E0224,
 643                       "at least one non-builtin trait is required for an object type");
 644             return tcx.types.err;
 645         }
 646
 647         let mut projection_bounds = vec![];
 648         let dummy_self = tcx.mk_ty(TRAIT_OBJECT_DUMMY_SELF);
 649         let principal = self.instantiate_poly_trait_ref(&trait_bounds[0],
 650                                                         dummy_self,
 651                                                         &mut projection_bounds);
 652
 653         for trait_bound in trait_bounds[1..].iter() {
 654             // Sanity check for non-principal trait bounds
 655             self.instantiate_poly_trait_ref(trait_bound,
 656                                             dummy_self,
 657                                             &mut vec![]);
 658         }
 659
 660         let (mut auto_traits, trait_bounds) = split_auto_traits(tcx, &trait_bounds[1..]);
 661
 662         if !trait_bounds.is_empty() {
 663             let b = &trait_bounds[0];
 664             let span = b.trait_ref.path.span;
 665             struct_span_err!(self.tcx().sess, span, E0225,
 666                 "only auto traits can be used as additional traits in a trait object")
 667                 .span_label(span, "non-auto additional trait")
 668                 .emit();
 669         }
 670
 671         // Erase the dummy_self (TRAIT_OBJECT_DUMMY_SELF) used above.
 672         let existential_principal = principal.map_bound(|trait_ref| {
 673             self.trait_ref_to_existential(trait_ref)
 674         });
 675         let existential_projections = projection_bounds.iter().map(|bound| {
 676             bound.map_bound(|b| {
 677                 let trait_ref = self.trait_ref_to_existential(b.projection_ty.trait_ref(tcx));
 678                 ty::ExistentialProjection {
 679                     ty: b.ty,
 680                     item_def_id: b.projection_ty.item_def_id,
 681                     substs: trait_ref.substs,
 682                 }
 683             })
 684         });
 685
 686         // check that there are no gross object safety violations,
 687         // most importantly, that the supertraits don't contain Self,
 688         // to avoid ICE-s.
 689         let object_safety_violations =
 690             tcx.astconv_object_safety_violations(principal.def_id());
 691         if !object_safety_violations.is_empty() {
 692             tcx.report_object_safety_error(
 693                 span, principal.def_id(), object_safety_violations)
 694                 .emit();
 695             return tcx.types.err;
 696         }
 697
 698         let mut associated_types = FxHashSet::default();
 699         for tr in traits::supertraits(tcx, principal) {
 700             associated_types.extend(tcx.associated_items(tr.def_id())
 701                 .filter(|item| item.kind == ty::AssociatedKind::Type)
 702                 .map(|item| item.def_id));
 703         }
 704
 705         for projection_bound in &projection_bounds {
 706             associated_types.remove(&projection_bound.projection_def_id());
 707         }
 708
 709         for item_def_id in associated_types {
 710             let assoc_item = tcx.associated_item(item_def_id);
 711             let trait_def_id = assoc_item.container.id();
 712             struct_span_err!(tcx.sess, span, E0191,
 713                 "the value of the associated type `{}` (from the trait `{}`) must be specified",
 714                         assoc_item.ident,
 715                         tcx.item_path_str(trait_def_id))
 716                         .span_label(span, format!(
 717                             "missing associated type `{}` value", assoc_item.ident))
 718                         .emit();
 719         }
 720
 721         // Dedup auto traits so that `dyn Trait + Send + Send` is the same as `dyn Trait + Send`.
 722         auto_traits.sort();
 723         auto_traits.dedup();
 724
 725         // skip_binder is okay, because the predicates are re-bound.
 726         let mut v =
 727             iter::once(ty::ExistentialPredicate::Trait(*existential_principal.skip_binder()))
 728             .chain(auto_traits.into_iter().map(ty::ExistentialPredicate::AutoTrait))
 729             .chain(existential_projections
 730                    .map(|x| ty::ExistentialPredicate::Projection(*x.skip_binder())))
 731             .collect::<AccumulateVec<[_; 8]>>();
 732         v.sort_by(|a, b| a.stable_cmp(tcx, b));
 733         let existential_predicates = ty::Binder::bind(tcx.mk_existential_predicates(v.into_iter()));
 734
 735
 736         // Explicitly specified region bound. Use that.
 737         let region_bound = if !lifetime.is_elided() {
 738             self.ast_region_to_region(lifetime, None)
 739         } else {
 740             self.compute_object_lifetime_bound(span, existential_predicates).unwrap_or_else(|| {
 741                 let hir_id = tcx.hir.node_to_hir_id(lifetime.id);
 742                 if tcx.named_region(hir_id).is_some() {
 743                     self.ast_region_to_region(lifetime, None)
 744                 } else {
 745                     self.re_infer(span, None).unwrap_or_else(|| {
 746                         span_err!(tcx.sess, span, E0228,
 747                                   "the lifetime bound for this object type cannot be deduced \
 748                                    from context; please supply an explicit bound");
 749                         tcx.types.re_static
 750                     })
 751                 }
 752             })
 753         };
 754
 755         debug!("region_bound: {:?}", region_bound);
 756
 757         let ty = tcx.mk_dynamic(existential_predicates, region_bound);
 758         debug!("trait_object_type: {:?}", ty);
 759         ty
 760     }
 761
 762     fn report_ambiguous_associated_type(&self,
 763                                         span: Span,
 764                                         type_str: &str,
 765                                         trait_str: &str,
 766                                         name: &str) {
 767         struct_span_err!(self.tcx().sess, span, E0223, "ambiguous associated type")
 768             .span_label(span, "ambiguous associated type")
 769             .note(&format!("specify the type using the syntax `<{} as {}>::{}`",
 770                   type_str, trait_str, name))
 771             .emit();
 772
 773     }
 774
 775     // Search for a bound on a type parameter which includes the associated item
 776     // given by `assoc_name`. `ty_param_def_id` is the `DefId` for the type parameter
 777     // This function will fail if there are no suitable bounds or there is
 778     // any ambiguity.
 779     fn find_bound_for_assoc_item(&self,
 780                                  ty_param_def_id: DefId,
 781                                  assoc_name: ast::Ident,
 782                                  span: Span)
 783                                  -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
 784     {
 785         let tcx = self.tcx();
 786
 787         let bounds: Vec<_> = self.get_type_parameter_bounds(span, ty_param_def_id)
 788             .predicates.into_iter().filter_map(|p| p.to_opt_poly_trait_ref()).collect();
 789
 790         // Check that there is exactly one way to find an associated type with the
 791         // correct name.
 792         let suitable_bounds =
 793             traits::transitive_bounds(tcx, &bounds)
 794             .filter(|b| self.trait_defines_associated_type_named(b.def_id(), assoc_name));
 795
 796         let param_node_id = tcx.hir.as_local_node_id(ty_param_def_id).unwrap();
 797         let param_name = tcx.hir.ty_param_name(param_node_id);
 798         self.one_bound_for_assoc_type(suitable_bounds,
 799                                       &param_name.as_str(),
 800                                       assoc_name,
 801                                       span)
 802     }
 803
 804
 805     // Checks that bounds contains exactly one element and reports appropriate
 806     // errors otherwise.
 807     fn one_bound_for_assoc_type<I>(&self,
 808                                 mut bounds: I,
 809                                 ty_param_name: &str,
 810                                 assoc_name: ast::Ident,
 811                                 span: Span)
 812         -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
 813         where I: Iterator<Item=ty::PolyTraitRef<'tcx>>
 814     {
 815         let bound = match bounds.next() {
 816             Some(bound) => bound,
 817             None => {
 818                 struct_span_err!(self.tcx().sess, span, E0220,
 819                           "associated type `{}` not found for `{}`",
 820                           assoc_name,
 821                           ty_param_name)
 822                   .span_label(span, format!("associated type `{}` not found", assoc_name))
 823                   .emit();
 824                 return Err(ErrorReported);
 825             }
 826         };
 827
 828         if let Some(bound2) = bounds.next() {
 829             let bounds = iter::once(bound).chain(iter::once(bound2)).chain(bounds);
 830             let mut err = struct_span_err!(
 831                 self.tcx().sess, span, E0221,
 832                 "ambiguous associated type `{}` in bounds of `{}`",
 833                 assoc_name,
 834                 ty_param_name);
 835             err.span_label(span, format!("ambiguous associated type `{}`", assoc_name));
 836
 837             for bound in bounds {
 838                 let bound_span = self.tcx().associated_items(bound.def_id()).find(|item| {
 839                     item.kind == ty::AssociatedKind::Type &&
 840                     self.tcx().hygienic_eq(assoc_name, item.ident, bound.def_id())
 841                 })
 842                 .and_then(|item| self.tcx().hir.span_if_local(item.def_id));
 843
 844                 if let Some(span) = bound_span {
 845                     err.span_label(span, format!("ambiguous `{}` from `{}`",
 846                                                   assoc_name,
 847                                                   bound));
 848                 } else {
 849                     span_note!(&mut err, span,
 850                                "associated type `{}` could derive from `{}`",
 851                                ty_param_name,
 852                                bound);
 853                 }
 854             }
 855             err.emit();
 856         }
 857
 858         return Ok(bound);
 859     }
 860
 861     // Create a type from a path to an associated type.
 862     // For a path A::B::C::D, ty and ty_path_def are the type and def for A::B::C
 863     // and item_segment is the path segment for D. We return a type and a def for
 864     // the whole path.
 865     // Will fail except for T::A and Self::A; i.e., if ty/ty_path_def are not a type
 866     // parameter or Self.
 867     pub fn associated_path_def_to_ty(&self,
 868                                      ref_id: ast::NodeId,
 869                                      span: Span,
 870                                      ty: Ty<'tcx>,
 871                                      ty_path_def: Def,
 872                                      item_segment: &hir::PathSegment)
 873                                      -> (Ty<'tcx>, Def)
 874     {
 875         let tcx = self.tcx();
 876         let assoc_name = item_segment.ident;
 877
 878         debug!("associated_path_def_to_ty: {:?}::{}", ty, assoc_name);
 879
 880         self.prohibit_generics(slice::from_ref(item_segment));
 881
 882         // Find the type of the associated item, and the trait where the associated
 883         // item is declared.
 884         let bound = match (&ty.sty, ty_path_def) {
 885             (_, Def::SelfTy(Some(_), Some(impl_def_id))) => {
 886                 // `Self` in an impl of a trait - we have a concrete self type and a
 887                 // trait reference.
 888                 let trait_ref = match tcx.impl_trait_ref(impl_def_id) {
 889                     Some(trait_ref) => trait_ref,
 890                     None => {
 891                         // A cycle error occurred, most likely.
 892                         return (tcx.types.err, Def::Err);
 893                     }
 894                 };
 895
 896                 let candidates =
 897                     traits::supertraits(tcx, ty::Binder::bind(trait_ref))
 898                     .filter(|r| self.trait_defines_associated_type_named(r.def_id(), assoc_name));
 899
 900                 match self.one_bound_for_assoc_type(candidates, "Self", assoc_name, span) {
 901                     Ok(bound) => bound,
 902                     Err(ErrorReported) => return (tcx.types.err, Def::Err),
 903                 }
 904             }
 905             (&ty::TyParam(_), Def::SelfTy(Some(param_did), None)) |
 906             (&ty::TyParam(_), Def::TyParam(param_did)) => {
 907                 match self.find_bound_for_assoc_item(param_did, assoc_name, span) {
 908                     Ok(bound) => bound,
 909                     Err(ErrorReported) => return (tcx.types.err, Def::Err),
 910                 }
 911             }
 912             _ => {
 913                 // Don't print TyErr to the user.
 914                 if !ty.references_error() {
 915                     self.report_ambiguous_associated_type(span,
 916                                                           &ty.to_string(),
 917                                                           "Trait",
 918                                                           &assoc_name.as_str());
 919                 }
 920                 return (tcx.types.err, Def::Err);
 921             }
 922         };
 923
 924         let trait_did = bound.def_id();
 925         let (assoc_ident, def_scope) = tcx.adjust_ident(assoc_name, trait_did, ref_id);
 926         let item = tcx.associated_items(trait_did).find(|i| {
 927             Namespace::from(i.kind) == Namespace::Type &&
 928             i.ident.modern() == assoc_ident
 929         })
 930         .expect("missing associated type");
 931
 932         let ty = self.projected_ty_from_poly_trait_ref(span, item.def_id, bound);
 933         let ty = self.normalize_ty(span, ty);
 934
 935         let def = Def::AssociatedTy(item.def_id);
 936         if !item.vis.is_accessible_from(def_scope, tcx) {
 937             let msg = format!("{} `{}` is private", def.kind_name(), assoc_name);
 938             tcx.sess.span_err(span, &msg);
 939         }
 940         tcx.check_stability(item.def_id, Some(ref_id), span);
 941
 942         (ty, def)
 943     }
 944
 945     fn qpath_to_ty(&self,
 946                    span: Span,
 947                    opt_self_ty: Option<Ty<'tcx>>,
 948                    item_def_id: DefId,
 949                    trait_segment: &hir::PathSegment,
 950                    item_segment: &hir::PathSegment)
 951                    -> Ty<'tcx>
 952     {
 953         let tcx = self.tcx();
 954         let trait_def_id = tcx.parent_def_id(item_def_id).unwrap();
 955
 956         self.prohibit_generics(slice::from_ref(item_segment));
 957
 958         let self_ty = if let Some(ty) = opt_self_ty {
 959             ty
 960         } else {
 961             let path_str = tcx.item_path_str(trait_def_id);
 962             self.report_ambiguous_associated_type(span,
 963                                                   "Type",
 964                                                   &path_str,
 965                                                   &item_segment.ident.as_str());
 966             return tcx.types.err;
 967         };
 968
 969         debug!("qpath_to_ty: self_type={:?}", self_ty);
 970
 971         let trait_ref = self.ast_path_to_mono_trait_ref(span,
 972                                                         trait_def_id,
 973                                                         self_ty,
 974                                                         trait_segment);
 975
 976         debug!("qpath_to_ty: trait_ref={:?}", trait_ref);
 977
 978         self.normalize_ty(span, tcx.mk_projection(item_def_id, trait_ref.substs))
 979     }
 980
 981     pub fn prohibit_generics(&self, segments: &[hir::PathSegment]) {
 982         for segment in segments {
 983             segment.with_generic_args(|generic_args| {
 984                 let (mut err_for_lt, mut err_for_ty) = (false, false);
 985                 for arg in &generic_args.args {
 986                     let (mut span_err, span, kind) = match arg {
 987                         hir::GenericArg::Lifetime(lt) => {
 988                             if err_for_lt { continue }
 989                             err_for_lt = true;
 990                             (struct_span_err!(self.tcx().sess, lt.span, E0110,
 991                                             "lifetime parameters are not allowed on \
 992                                                 this type"),
 993                              lt.span,
 994                              "lifetime")
 995                         }
 996                         hir::GenericArg::Type(ty) => {
 997                             if err_for_ty { continue }
 998                             err_for_ty = true;
 999                             (struct_span_err!(self.tcx().sess, ty.span, E0109,
1000                                             "type parameters are not allowed on this type"),
1001                              ty.span,
1002                              "type")
1003                         }
1004                     };
1005                     span_err.span_label(span, format!("{} parameter not allowed", kind))
1006                             .emit();
1007                     if err_for_lt && err_for_ty {
1008                         break;
1009                     }
1010                 }
1011                 for binding in &generic_args.bindings {
1012                     self.prohibit_projection(binding.span);
1013                     break;
1014                 }
1015             })
1016         }
1017     }
1018
1019     pub fn prohibit_projection(&self, span: Span) {
1020         let mut err = struct_span_err!(self.tcx().sess, span, E0229,
1021                                        "associated type bindings are not allowed here");
1022         err.span_label(span, "associated type not allowed here").emit();
1023     }
1024
1025     // Check a type Path and convert it to a Ty.
1026     pub fn def_to_ty(&self,
1027                      opt_self_ty: Option<Ty<'tcx>>,
1028                      path: &hir::Path,
1029                      permit_variants: bool)
1030                      -> Ty<'tcx> {
1031         let tcx = self.tcx();
1032
1033         debug!("base_def_to_ty(def={:?}, opt_self_ty={:?}, path_segments={:?})",
1034                path.def, opt_self_ty, path.segments);
1035
1036         let span = path.span;
1037         match path.def {
1038             Def::Enum(did) | Def::TyAlias(did) | Def::Struct(did) |
1039             Def::Union(did) | Def::TyForeign(did) => {
1040                 assert_eq!(opt_self_ty, None);
1041                 self.prohibit_generics(path.segments.split_last().unwrap().1);
1042                 self.ast_path_to_ty(span, did, path.segments.last().unwrap())
1043             }
1044             Def::Variant(did) if permit_variants => {
1045                 // Convert "variant type" as if it were a real type.
1046                 // The resulting `Ty` is type of the variant's enum for now.
1047                 assert_eq!(opt_self_ty, None);
1048                 self.prohibit_generics(path.segments.split_last().unwrap().1);
1049                 self.ast_path_to_ty(span,
1050                                     tcx.parent_def_id(did).unwrap(),
1051                                     path.segments.last().unwrap())
1052             }
1053             Def::TyParam(did) => {
1054                 assert_eq!(opt_self_ty, None);
1055                 self.prohibit_generics(&path.segments);
1056
1057                 let node_id = tcx.hir.as_local_node_id(did).unwrap();
1058                 let item_id = tcx.hir.get_parent_node(node_id);
1059                 let item_def_id = tcx.hir.local_def_id(item_id);
1060                 let generics = tcx.generics_of(item_def_id);
1061                 let index = generics.param_def_id_to_index[&tcx.hir.local_def_id(node_id)];
1062                 tcx.mk_ty_param(index, tcx.hir.name(node_id).as_interned_str())
1063             }
1064             Def::SelfTy(_, Some(def_id)) => {
1065                 // Self in impl (we know the concrete type).
1066
1067                 assert_eq!(opt_self_ty, None);
1068                 self.prohibit_generics(&path.segments);
1069
1070                 tcx.at(span).type_of(def_id)
1071             }
1072             Def::SelfTy(Some(_), None) => {
1073                 // Self in trait.
1074                 assert_eq!(opt_self_ty, None);
1075                 self.prohibit_generics(&path.segments);
1076                 tcx.mk_self_type()
1077             }
1078             Def::AssociatedTy(def_id) => {
1079                 self.prohibit_generics(&path.segments[..path.segments.len()-2]);
1080                 self.qpath_to_ty(span,
1081                                  opt_self_ty,
1082                                  def_id,
1083                                  &path.segments[path.segments.len()-2],
1084                                  path.segments.last().unwrap())
1085             }
1086             Def::PrimTy(prim_ty) => {
1087                 assert_eq!(opt_self_ty, None);
1088                 self.prohibit_generics(&path.segments);
1089                 match prim_ty {
1090                     hir::TyBool => tcx.types.bool,
1091                     hir::TyChar => tcx.types.char,
1092                     hir::TyInt(it) => tcx.mk_mach_int(it),
1093                     hir::TyUint(uit) => tcx.mk_mach_uint(uit),
1094                     hir::TyFloat(ft) => tcx.mk_mach_float(ft),
1095                     hir::TyStr => tcx.mk_str()
1096                 }
1097             }
1098             Def::Err => {
1099                 self.set_tainted_by_errors();
1100                 return self.tcx().types.err;
1101             }
1102             _ => span_bug!(span, "unexpected definition: {:?}", path.def)
1103         }
1104     }
1105
1106     /// Parses the programmer's textual representation of a type into our
1107     /// internal notion of a type.
1108     pub fn ast_ty_to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
1109         debug!("ast_ty_to_ty(id={:?}, ast_ty={:?})",
1110                ast_ty.id, ast_ty);
1111
1112         let tcx = self.tcx();
1113
1114         let result_ty = match ast_ty.node {
1115             hir::TySlice(ref ty) => {
1116                 tcx.mk_slice(self.ast_ty_to_ty(&ty))
1117             }
1118             hir::TyPtr(ref mt) => {
1119                 tcx.mk_ptr(ty::TypeAndMut {
1120                     ty: self.ast_ty_to_ty(&mt.ty),
1121                     mutbl: mt.mutbl
1122                 })
1123             }
1124             hir::TyRptr(ref region, ref mt) => {
1125                 let r = self.ast_region_to_region(region, None);
1126                 debug!("TyRef r={:?}", r);
1127                 let t = self.ast_ty_to_ty(&mt.ty);
1128                 tcx.mk_ref(r, ty::TypeAndMut {ty: t, mutbl: mt.mutbl})
1129             }
1130             hir::TyNever => {
1131                 tcx.types.never
1132             },
1133             hir::TyTup(ref fields) => {
1134                 tcx.mk_tup(fields.iter().map(|t| self.ast_ty_to_ty(&t)))
1135             }
1136             hir::TyBareFn(ref bf) => {
1137                 require_c_abi_if_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
1138                 tcx.mk_fn_ptr(self.ty_of_fn(bf.unsafety, bf.abi, &bf.decl))
1139             }
1140             hir::TyTraitObject(ref bounds, ref lifetime) => {
1141                 self.conv_object_ty_poly_trait_ref(ast_ty.span, bounds, lifetime)
1142             }
1143             hir::TyImplTraitExistential(_, def_id, ref lifetimes) => {
1144                 self.impl_trait_ty_to_ty(def_id, lifetimes)
1145             }
1146             hir::TyPath(hir::QPath::Resolved(ref maybe_qself, ref path)) => {
1147                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
1148                 let opt_self_ty = maybe_qself.as_ref().map(|qself| {
1149                     self.ast_ty_to_ty(qself)
1150                 });
1151                 self.def_to_ty(opt_self_ty, path, false)
1152             }
1153             hir::TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
1154                 debug!("ast_ty_to_ty: qself={:?} segment={:?}", qself, segment);
1155                 let ty = self.ast_ty_to_ty(qself);
1156
1157                 let def = if let hir::TyPath(hir::QPath::Resolved(_, ref path)) = qself.node {
1158                     path.def
1159                 } else {
1160                     Def::Err
1161                 };
1162                 self.associated_path_def_to_ty(ast_ty.id, ast_ty.span, ty, def, segment).0
1163             }
1164             hir::TyArray(ref ty, ref length) => {
1165                 let length_def_id = tcx.hir.local_def_id(length.id);
1166                 let substs = Substs::identity_for_item(tcx, length_def_id);
1167                 let length = ty::Const::unevaluated(tcx, length_def_id, substs, tcx.types.usize);
1168                 let array_ty = tcx.mk_ty(ty::TyArray(self.ast_ty_to_ty(&ty), length));
1169                 self.normalize_ty(ast_ty.span, array_ty)
1170             }
1171             hir::TyTypeof(ref _e) => {
1172                 struct_span_err!(tcx.sess, ast_ty.span, E0516,
1173                                  "`typeof` is a reserved keyword but unimplemented")
1174                     .span_label(ast_ty.span, "reserved keyword")
1175                     .emit();
1176
1177                 tcx.types.err
1178             }
1179             hir::TyInfer => {
1180                 // TyInfer also appears as the type of arguments or return
1181                 // values in a ExprClosure, or as
1182                 // the type of local variables. Both of these cases are
1183                 // handled specially and will not descend into this routine.
1184                 self.ty_infer(ast_ty.span)
1185             }
1186             hir::TyErr => {
1187                 tcx.types.err
1188             }
1189         };
1190
1191         self.record_ty(ast_ty.hir_id, result_ty, ast_ty.span);
1192         result_ty
1193     }
1194
1195     pub fn impl_trait_ty_to_ty(
1196         &self,
1197         def_id: DefId,
1198         lifetimes: &[hir::Lifetime],
1199     ) -> Ty<'tcx> {
1200         debug!("impl_trait_ty_to_ty(def_id={:?}, lifetimes={:?})", def_id, lifetimes);
1201         let tcx = self.tcx();
1202
1203         let generics = tcx.generics_of(def_id);
1204
1205         debug!("impl_trait_ty_to_ty: generics={:?}", generics);
1206         let substs = Substs::for_item(tcx, def_id, |param, _| {
1207             if let Some(i) = (param.index as usize).checked_sub(generics.parent_count) {
1208                 // Our own parameters are the resolved lifetimes.
1209                 match param.kind {
1210                     GenericParamDefKind::Lifetime => {
1211                         self.ast_region_to_region(&lifetimes[i], None).into()
1212                     }
1213                     _ => bug!()
1214                 }
1215             } else {
1216                 // Replace all parent lifetimes with 'static.
1217                 match param.kind {
1218                     GenericParamDefKind::Lifetime => {
1219                         tcx.types.re_static.into()
1220                     }
1221                     _ => tcx.mk_param_from_def(param)
1222                 }
1223             }
1224         });
1225         debug!("impl_trait_ty_to_ty: final substs = {:?}", substs);
1226
1227         let ty = tcx.mk_anon(def_id, substs);
1228         debug!("impl_trait_ty_to_ty: {}", ty);
1229         ty
1230     }
1231
1232     pub fn ty_of_arg(&self,
1233                      ty: &hir::Ty,
1234                      expected_ty: Option<Ty<'tcx>>)
1235                      -> Ty<'tcx>
1236     {
1237         match ty.node {
1238             hir::TyInfer if expected_ty.is_some() => {
1239                 self.record_ty(ty.hir_id, expected_ty.unwrap(), ty.span);
1240                 expected_ty.unwrap()
1241             }
1242             _ => self.ast_ty_to_ty(ty),
1243         }
1244     }
1245
1246     pub fn ty_of_fn(&self,
1247                     unsafety: hir::Unsafety,
1248                     abi: abi::Abi,
1249                     decl: &hir::FnDecl)
1250                     -> ty::PolyFnSig<'tcx> {
1251         debug!("ty_of_fn");
1252
1253         let tcx = self.tcx();
1254         let input_tys: Vec<Ty> =
1255             decl.inputs.iter().map(|a| self.ty_of_arg(a, None)).collect();
1256
1257         let output_ty = match decl.output {
1258             hir::Return(ref output) => self.ast_ty_to_ty(output),
1259             hir::DefaultReturn(..) => tcx.mk_nil(),
1260         };
1261
1262         debug!("ty_of_fn: output_ty={:?}", output_ty);
1263
1264         let bare_fn_ty = ty::Binder::bind(tcx.mk_fn_sig(
1265             input_tys.into_iter(),
1266             output_ty,
1267             decl.variadic,
1268             unsafety,
1269             abi
1270         ));
1271
1272         // Find any late-bound regions declared in return type that do
1273         // not appear in the arguments. These are not wellformed.
1274         //
1275         // Example:
1276         //     for<'a> fn() -> &'a str <-- 'a is bad
1277         //     for<'a> fn(&'a String) -> &'a str <-- 'a is ok
1278         let inputs = bare_fn_ty.inputs();
1279         let late_bound_in_args = tcx.collect_constrained_late_bound_regions(
1280             &inputs.map_bound(|i| i.to_owned()));
1281         let output = bare_fn_ty.output();
1282         let late_bound_in_ret = tcx.collect_referenced_late_bound_regions(&output);
1283         for br in late_bound_in_ret.difference(&late_bound_in_args) {
1284             let lifetime_name = match *br {
1285                 ty::BrNamed(_, name) => format!("lifetime `{}`,", name),
1286                 ty::BrAnon(_) | ty::BrFresh(_) | ty::BrEnv => format!("an anonymous lifetime"),
1287             };
1288             let mut err = struct_span_err!(tcx.sess,
1289                                            decl.output.span(),
1290                                            E0581,
1291                                            "return type references {} \
1292                                             which is not constrained by the fn input types",
1293                                            lifetime_name);
1294             if let ty::BrAnon(_) = *br {
1295                 // The only way for an anonymous lifetime to wind up
1296                 // in the return type but **also** be unconstrained is
1297                 // if it only appears in "associated types" in the
1298                 // input. See #47511 for an example. In this case,
1299                 // though we can easily give a hint that ought to be
1300                 // relevant.
1301                 err.note("lifetimes appearing in an associated type \
1302                           are not considered constrained");
1303             }
1304             err.emit();
1305         }
1306
1307         bare_fn_ty
1308     }
1309
1310     /// Given the bounds on an object, determines what single region bound (if any) we can
1311     /// use to summarize this type. The basic idea is that we will use the bound the user
1312     /// provided, if they provided one, and otherwise search the supertypes of trait bounds
1313     /// for region bounds. It may be that we can derive no bound at all, in which case
1314     /// we return `None`.
1315     fn compute_object_lifetime_bound(&self,
1316         span: Span,
1317         existential_predicates: ty::Binder<&'tcx ty::Slice<ty::ExistentialPredicate<'tcx>>>)
1318         -> Option<ty::Region<'tcx>> // if None, use the default
1319     {
1320         let tcx = self.tcx();
1321
1322         debug!("compute_opt_region_bound(existential_predicates={:?})",
1323                existential_predicates);
1324
1325         // No explicit region bound specified. Therefore, examine trait
1326         // bounds and see if we can derive region bounds from those.
1327         let derived_region_bounds =
1328             object_region_bounds(tcx, existential_predicates);
1329
1330         // If there are no derived region bounds, then report back that we
1331         // can find no region bound. The caller will use the default.
1332         if derived_region_bounds.is_empty() {
1333             return None;
1334         }
1335
1336         // If any of the derived region bounds are 'static, that is always
1337         // the best choice.
1338         if derived_region_bounds.iter().any(|&r| ty::ReStatic == *r) {
1339             return Some(tcx.types.re_static);
1340         }
1341
1342         // Determine whether there is exactly one unique region in the set
1343         // of derived region bounds. If so, use that. Otherwise, report an
1344         // error.
1345         let r = derived_region_bounds[0];
1346         if derived_region_bounds[1..].iter().any(|r1| r != *r1) {
1347             span_err!(tcx.sess, span, E0227,
1348                       "ambiguous lifetime bound, explicit lifetime bound required");
1349         }
1350         return Some(r);
1351     }
1352 }
1353
1354 /// Divides a list of general trait bounds into two groups: auto traits (e.g. Sync and Send) and the
1355 /// remaining general trait bounds.
1356 fn split_auto_traits<'a, 'b, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
1357                                          trait_bounds: &'b [hir::PolyTraitRef])
1358     -> (Vec<DefId>, Vec<&'b hir::PolyTraitRef>)
1359 {
1360     let (auto_traits, trait_bounds): (Vec<_>, _) = trait_bounds.iter().partition(|bound| {
1361         // Checks whether `trait_did` is an auto trait and adds it to `auto_traits` if so.
1362         match bound.trait_ref.path.def {
1363             Def::Trait(trait_did) if tcx.trait_is_auto(trait_did) => {
1364                 true
1365             }
1366             _ => false
1367         }
1368     });
1369
1370     let auto_traits = auto_traits.into_iter().map(|tr| {
1371         if let Def::Trait(trait_did) = tr.trait_ref.path.def {
1372             trait_did
1373         } else {
1374             unreachable!()
1375         }
1376     }).collect::<Vec<_>>();
1377
1378     (auto_traits, trait_bounds)
1379 }
1380
1381 fn check_type_argument_count(tcx: TyCtxt,
1382                              span: Span,
1383                              supplied: usize,
1384                              ty_params: ParamRange)
1385 {
1386     let (required, accepted) = (ty_params.required, ty_params.accepted);
1387     if supplied < required {
1388         let expected = if required < accepted {
1389             "expected at least"
1390         } else {
1391             "expected"
1392         };
1393         let arguments_plural = if required == 1 { "" } else { "s" };
1394
1395         struct_span_err!(tcx.sess, span, E0243,
1396                 "wrong number of type arguments: {} {}, found {}",
1397                 expected, required, supplied)
1398             .span_label(span,
1399                 format!("{} {} type argument{}",
1400                     expected,
1401                     required,
1402                     arguments_plural))
1403             .emit();
1404     } else if supplied > accepted {
1405         let expected = if required < accepted {
1406             format!("expected at most {}", accepted)
1407         } else {
1408             format!("expected {}", accepted)
1409         };
1410         let arguments_plural = if accepted == 1 { "" } else { "s" };
1411
1412         struct_span_err!(tcx.sess, span, E0244,
1413                 "wrong number of type arguments: {}, found {}",
1414                 expected, supplied)
1415             .span_label(
1416                 span,
1417                 format!("{} type argument{}",
1418                     if accepted == 0 { "expected no" } else { &expected },
1419                     arguments_plural)
1420             )
1421             .emit();
1422     }
1423 }
1424
1425 fn report_lifetime_number_error(tcx: TyCtxt, span: Span, number: usize, expected: usize) {
1426     let label = if number < expected {
1427         if expected == 1 {
1428             format!("expected {} lifetime parameter", expected)
1429         } else {
1430             format!("expected {} lifetime parameters", expected)
1431         }
1432     } else {
1433         let additional = number - expected;
1434         if additional == 1 {
1435             "unexpected lifetime parameter".to_string()
1436         } else {
1437             format!("{} unexpected lifetime parameters", additional)
1438         }
1439     };
1440     struct_span_err!(tcx.sess, span, E0107,
1441                      "wrong number of lifetime parameters: expected {}, found {}",
1442                      expected, number)
1443         .span_label(span, label)
1444         .emit();
1445 }
1446
1447 // A helper struct for conveniently grouping a set of bounds which we pass to
1448 // and return from functions in multiple places.
1449 #[derive(PartialEq, Eq, Clone, Debug)]
1450 pub struct Bounds<'tcx> {
1451     pub region_bounds: Vec<ty::Region<'tcx>>,
1452     pub implicitly_sized: bool,
1453     pub trait_bounds: Vec<ty::PolyTraitRef<'tcx>>,
1454     pub projection_bounds: Vec<ty::PolyProjectionPredicate<'tcx>>,
1455 }
1456
1457 impl<'a, 'gcx, 'tcx> Bounds<'tcx> {
1458     pub fn predicates(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, param_ty: Ty<'tcx>)
1459                       -> Vec<ty::Predicate<'tcx>>
1460     {
1461         let mut vec = Vec::new();
1462
1463         // If it could be sized, and is, add the sized predicate
1464         if self.implicitly_sized {
1465             if let Some(sized) = tcx.lang_items().sized_trait() {
1466                 let trait_ref = ty::TraitRef {
1467                     def_id: sized,
1468                     substs: tcx.mk_substs_trait(param_ty, &[])
1469                 };
1470                 vec.push(trait_ref.to_predicate());
1471             }
1472         }
1473
1474         for &region_bound in &self.region_bounds {
1475             // account for the binder being introduced below; no need to shift `param_ty`
1476             // because, at present at least, it can only refer to early-bound regions
1477             let region_bound = tcx.mk_region(ty::fold::shift_region(*region_bound, 1));
1478             vec.push(
1479                 ty::Binder::dummy(ty::OutlivesPredicate(param_ty, region_bound)).to_predicate());
1480         }
1481
1482         for bound_trait_ref in &self.trait_bounds {
1483             vec.push(bound_trait_ref.to_predicate());
1484         }
1485
1486         for projection in &self.projection_bounds {
1487             vec.push(projection.to_predicate());
1488         }
1489
1490         vec
1491     }
1492 }