src/librustc_typeck/astconv.rs

   1 //! Conversion from AST representation of types to the `ty.rs` representation.
   2 //! The main routine here is `ast_ty_to_ty()`; each use is parameterized by an
   3 //! instance of `AstConv`.
   4
   5 use errors::{Applicability, DiagnosticId};
   6 use crate::hir::{self, GenericArg, GenericArgs, ExprKind};
   7 use crate::hir::def::{CtorOf, Res, DefKind};
   8 use crate::hir::def_id::DefId;
   9 use crate::hir::HirVec;
  10 use crate::lint;
  11 use crate::middle::lang_items::SizedTraitLangItem;
  12 use crate::middle::resolve_lifetime as rl;
  13 use crate::namespace::Namespace;
  14 use rustc::lint::builtin::AMBIGUOUS_ASSOCIATED_ITEMS;
  15 use rustc::traits;
  16 use rustc::ty::{self, DefIdTree, Ty, TyCtxt, ToPredicate, TypeFoldable};
  17 use rustc::ty::{GenericParamDef, GenericParamDefKind};
  18 use rustc::ty::subst::{Kind, Subst, InternalSubsts, SubstsRef};
  19 use rustc::ty::wf::object_region_bounds;
  20 use rustc::mir::interpret::ConstValue;
  21 use rustc_target::spec::abi;
  22 use crate::require_c_abi_if_c_variadic;
  23 use smallvec::SmallVec;
  24 use syntax::ast;
  25 use syntax::feature_gate::{GateIssue, emit_feature_err};
  26 use syntax::ptr::P;
  27 use syntax::util::lev_distance::find_best_match_for_name;
  28 use syntax::symbol::sym;
  29 use syntax_pos::{DUMMY_SP, Span, MultiSpan};
  30 use crate::util::common::ErrorReported;
  31 use crate::util::nodemap::FxHashMap;
  32
  33 use std::collections::BTreeSet;
  34 use std::iter;
  35 use std::slice;
  36
  37 use super::{check_type_alias_enum_variants_enabled};
  38 use rustc_data_structures::fx::FxHashSet;
  39
  40 #[derive(Debug)]
  41 pub struct PathSeg(pub DefId, pub usize);
  42
  43 pub trait AstConv<'gcx, 'tcx> {
  44     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>;
  45
  46     /// Returns the set of bounds in scope for the type parameter with
  47     /// the given id.
  48     fn get_type_parameter_bounds(&self, span: Span, def_id: DefId)
  49                                  -> &'tcx ty::GenericPredicates<'tcx>;
  50
  51     /// Returns the lifetime to use when a lifetime is omitted (and not elided).
  52     fn re_infer(&self, span: Span, _def: Option<&ty::GenericParamDef>)
  53                 -> Option<ty::Region<'tcx>>;
  54
  55     /// Returns the type to use when a type is omitted.
  56     fn ty_infer(&self, span: Span) -> Ty<'tcx>;
  57
  58     /// Same as `ty_infer`, but with a known type parameter definition.
  59     fn ty_infer_for_def(&self,
  60                         _def: &ty::GenericParamDef,
  61                         span: Span) -> Ty<'tcx> {
  62         self.ty_infer(span)
  63     }
  64
  65     /// Projecting an associated type from a (potentially)
  66     /// higher-ranked trait reference is more complicated, because of
  67     /// the possibility of late-bound regions appearing in the
  68     /// associated type binding. This is not legal in function
  69     /// signatures for that reason. In a function body, we can always
  70     /// handle it because we can use inference variables to remove the
  71     /// late-bound regions.
  72     fn projected_ty_from_poly_trait_ref(&self,
  73                                         span: Span,
  74                                         item_def_id: DefId,
  75                                         poly_trait_ref: ty::PolyTraitRef<'tcx>)
  76                                         -> Ty<'tcx>;
  77
  78     /// Normalize an associated type coming from the user.
  79     fn normalize_ty(&self, span: Span, ty: Ty<'tcx>) -> Ty<'tcx>;
  80
  81     /// Invoked when we encounter an error from some prior pass
  82     /// (e.g., resolve) that is translated into a ty-error. This is
  83     /// used to help suppress derived errors typeck might otherwise
  84     /// report.
  85     fn set_tainted_by_errors(&self);
  86
  87     fn record_ty(&self, hir_id: hir::HirId, ty: Ty<'tcx>, span: Span);
  88 }
  89
  90 pub enum SizedByDefault {
  91     Yes,
  92     No,
  93 }
  94
  95 struct ConvertedBinding<'tcx> {
  96     item_name: ast::Ident,
  97     kind: ConvertedBindingKind<'tcx>,
  98     span: Span,
  99 }
 100
 101 enum ConvertedBindingKind<'tcx> {
 102     Equality(Ty<'tcx>),
 103     Constraint(P<[hir::GenericBound]>),
 104 }
 105
 106 #[derive(PartialEq)]
 107 enum GenericArgPosition {
 108     Type,
 109     Value, // e.g., functions
 110     MethodCall,
 111 }
 112
 113 impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
 114     pub fn ast_region_to_region(&self,
 115         lifetime: &hir::Lifetime,
 116         def: Option<&ty::GenericParamDef>)
 117         -> ty::Region<'tcx>
 118     {
 119         let tcx = self.tcx();
 120         let lifetime_name = |def_id| {
 121             tcx.hir().name_by_hir_id(tcx.hir().as_local_hir_id(def_id).unwrap()).as_interned_str()
 122         };
 123
 124         let r = match tcx.named_region(lifetime.hir_id) {
 125             Some(rl::Region::Static) => {
 126                 tcx.lifetimes.re_static
 127             }
 128
 129             Some(rl::Region::LateBound(debruijn, id, _)) => {
 130                 let name = lifetime_name(id);
 131                 tcx.mk_region(ty::ReLateBound(debruijn,
 132                     ty::BrNamed(id, name)))
 133             }
 134
 135             Some(rl::Region::LateBoundAnon(debruijn, index)) => {
 136                 tcx.mk_region(ty::ReLateBound(debruijn, ty::BrAnon(index)))
 137             }
 138
 139             Some(rl::Region::EarlyBound(index, id, _)) => {
 140                 let name = lifetime_name(id);
 141                 tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
 142                     def_id: id,
 143                     index,
 144                     name,
 145                 }))
 146             }
 147
 148             Some(rl::Region::Free(scope, id)) => {
 149                 let name = lifetime_name(id);
 150                 tcx.mk_region(ty::ReFree(ty::FreeRegion {
 151                     scope,
 152                     bound_region: ty::BrNamed(id, name)
 153                 }))
 154
 155                 // (*) -- not late-bound, won't change
 156             }
 157
 158             None => {
 159                 self.re_infer(lifetime.span, def)
 160                     .unwrap_or_else(|| {
 161                         // This indicates an illegal lifetime
 162                         // elision. `resolve_lifetime` should have
 163                         // reported an error in this case -- but if
 164                         // not, let's error out.
 165                         tcx.sess.delay_span_bug(lifetime.span, "unelided lifetime in signature");
 166
 167                         // Supply some dummy value. We don't have an
 168                         // `re_error`, annoyingly, so use `'static`.
 169                         tcx.lifetimes.re_static
 170                     })
 171             }
 172         };
 173
 174         debug!("ast_region_to_region(lifetime={:?}) yields {:?}",
 175                lifetime,
 176                r);
 177
 178         r
 179     }
 180
 181     /// Given a path `path` that refers to an item `I` with the declared generics `decl_generics`,
 182     /// returns an appropriate set of substitutions for this particular reference to `I`.
 183     pub fn ast_path_substs_for_ty(&self,
 184         span: Span,
 185         def_id: DefId,
 186         item_segment: &hir::PathSegment)
 187         -> SubstsRef<'tcx>
 188     {
 189         let (substs, assoc_bindings, _) = item_segment.with_generic_args(|generic_args| {
 190             self.create_substs_for_ast_path(
 191                 span,
 192                 def_id,
 193                 generic_args,
 194                 item_segment.infer_types,
 195                 None,
 196             )
 197         });
 198
 199         assoc_bindings.first().map(|b| Self::prohibit_assoc_ty_binding(self.tcx(), b.span));
 200
 201         substs
 202     }
 203
 204     /// Report error if there is an explicit type parameter when using `impl Trait`.
 205     fn check_impl_trait(
 206         tcx: TyCtxt<'_, '_, '_>,
 207         span: Span,
 208         seg: &hir::PathSegment,
 209         generics: &ty::Generics,
 210     ) -> bool {
 211         let explicit = !seg.infer_types;
 212         let impl_trait = generics.params.iter().any(|param| match param.kind {
 213             ty::GenericParamDefKind::Type {
 214                 synthetic: Some(hir::SyntheticTyParamKind::ImplTrait), ..
 215             } => true,
 216             _ => false,
 217         });
 218
 219         if explicit && impl_trait {
 220             let mut err = struct_span_err! {
 221                 tcx.sess,
 222                 span,
 223                 E0632,
 224                 "cannot provide explicit type parameters when `impl Trait` is \
 225                  used in argument position."
 226             };
 227
 228             err.emit();
 229         }
 230
 231         impl_trait
 232     }
 233
 234     /// Checks that the correct number of generic arguments have been provided.
 235     /// Used specifically for function calls.
 236     pub fn check_generic_arg_count_for_call(
 237         tcx: TyCtxt<'_, '_, '_>,
 238         span: Span,
 239         def: &ty::Generics,
 240         seg: &hir::PathSegment,
 241         is_method_call: bool,
 242     ) -> bool {
 243         let empty_args = P(hir::GenericArgs {
 244             args: HirVec::new(), bindings: HirVec::new(), parenthesized: false,
 245         });
 246         let suppress_mismatch = Self::check_impl_trait(tcx, span, seg, &def);
 247         Self::check_generic_arg_count(
 248             tcx,
 249             span,
 250             def,
 251             if let Some(ref args) = seg.args {
 252                 args
 253             } else {
 254                 &empty_args
 255             },
 256             if is_method_call {
 257                 GenericArgPosition::MethodCall
 258             } else {
 259                 GenericArgPosition::Value
 260             },
 261             def.parent.is_none() && def.has_self, // `has_self`
 262             seg.infer_types || suppress_mismatch, // `infer_types`
 263         ).0
 264     }
 265
 266     /// Checks that the correct number of generic arguments have been provided.
 267     /// This is used both for datatypes and function calls.
 268     fn check_generic_arg_count(
 269         tcx: TyCtxt<'_, '_, '_>,
 270         span: Span,
 271         def: &ty::Generics,
 272         args: &hir::GenericArgs,
 273         position: GenericArgPosition,
 274         has_self: bool,
 275         infer_types: bool,
 276     ) -> (bool, Option<Vec<Span>>) {
 277         // At this stage we are guaranteed that the generic arguments are in the correct order, e.g.
 278         // that lifetimes will proceed types. So it suffices to check the number of each generic
 279         // arguments in order to validate them with respect to the generic parameters.
 280         let param_counts = def.own_counts();
 281         let arg_counts = args.own_counts();
 282         let infer_lifetimes = position != GenericArgPosition::Type && arg_counts.lifetimes == 0;
 283         let infer_consts = position != GenericArgPosition::Type && arg_counts.consts == 0;
 284
 285         let mut defaults: ty::GenericParamCount = Default::default();
 286         for param in &def.params {
 287             match param.kind {
 288                 GenericParamDefKind::Lifetime => {}
 289                 GenericParamDefKind::Type { has_default, .. } => {
 290                     defaults.types += has_default as usize
 291                 }
 292                 GenericParamDefKind::Const => {
 293                     // FIXME(const_generics:defaults)
 294                 }
 295             };
 296         }
 297
 298         if position != GenericArgPosition::Type && !args.bindings.is_empty() {
 299             AstConv::prohibit_assoc_ty_binding(tcx, args.bindings[0].span);
 300         }
 301
 302         // Prohibit explicit lifetime arguments if late-bound lifetime parameters are present.
 303         let mut reported_late_bound_region_err = None;
 304         if !infer_lifetimes {
 305             if let Some(span_late) = def.has_late_bound_regions {
 306                 let msg = "cannot specify lifetime arguments explicitly \
 307                            if late bound lifetime parameters are present";
 308                 let note = "the late bound lifetime parameter is introduced here";
 309                 let span = args.args[0].span();
 310                 if position == GenericArgPosition::Value
 311                     && arg_counts.lifetimes != param_counts.lifetimes {
 312                     let mut err = tcx.sess.struct_span_err(span, msg);
 313                     err.span_note(span_late, note);
 314                     err.emit();
 315                     reported_late_bound_region_err = Some(true);
 316                 } else {
 317                     let mut multispan = MultiSpan::from_span(span);
 318                     multispan.push_span_label(span_late, note.to_string());
 319                     tcx.lint_hir(lint::builtin::LATE_BOUND_LIFETIME_ARGUMENTS,
 320                                  args.args[0].id(), multispan, msg);
 321                     reported_late_bound_region_err = Some(false);
 322                 }
 323             }
 324         }
 325
 326         let check_kind_count = |kind, required, permitted, provided, offset| {
 327             debug!(
 328                 "check_kind_count: kind: {} required: {} permitted: {} provided: {} offset: {}",
 329                 kind,
 330                 required,
 331                 permitted,
 332                 provided,
 333                 offset
 334             );
 335             // We enforce the following: `required` <= `provided` <= `permitted`.
 336             // For kinds without defaults (i.e., lifetimes), `required == permitted`.
 337             // For other kinds (i.e., types), `permitted` may be greater than `required`.
 338             if required <= provided && provided <= permitted {
 339                 return (reported_late_bound_region_err.unwrap_or(false), None);
 340             }
 341
 342             // Unfortunately lifetime and type parameter mismatches are typically styled
 343             // differently in diagnostics, which means we have a few cases to consider here.
 344             let (bound, quantifier) = if required != permitted {
 345                 if provided < required {
 346                     (required, "at least ")
 347                 } else { // provided > permitted
 348                     (permitted, "at most ")
 349                 }
 350             } else {
 351                 (required, "")
 352             };
 353
 354             let mut potential_assoc_types: Option<Vec<Span>> = None;
 355             let (spans, label) = if required == permitted && provided > permitted {
 356                 // In the case when the user has provided too many arguments,
 357                 // we want to point to the unexpected arguments.
 358                 let spans: Vec<Span> = args.args[offset+permitted .. offset+provided]
 359                         .iter()
 360                         .map(|arg| arg.span())
 361                         .collect();
 362                 potential_assoc_types = Some(spans.clone());
 363                 (spans, format!( "unexpected {} argument", kind))
 364             } else {
 365                 (vec![span], format!(
 366                     "expected {}{} {} argument{}",
 367                     quantifier,
 368                     bound,
 369                     kind,
 370                     if bound != 1 { "s" } else { "" },
 371                 ))
 372             };
 373
 374             let mut err = tcx.sess.struct_span_err_with_code(
 375                 spans.clone(),
 376                 &format!(
 377                     "wrong number of {} arguments: expected {}{}, found {}",
 378                     kind,
 379                     quantifier,
 380                     bound,
 381                     provided,
 382                 ),
 383                 DiagnosticId::Error("E0107".into())
 384             );
 385             for span in spans {
 386                 err.span_label(span, label.as_str());
 387             }
 388             err.emit();
 389
 390             (
 391                 provided > required, // `suppress_error`
 392                 potential_assoc_types,
 393             )
 394         };
 395
 396         if reported_late_bound_region_err.is_none()
 397             && (!infer_lifetimes || arg_counts.lifetimes > param_counts.lifetimes) {
 398             check_kind_count(
 399                 "lifetime",
 400                 param_counts.lifetimes,
 401                 param_counts.lifetimes,
 402                 arg_counts.lifetimes,
 403                 0,
 404             );
 405         }
 406         // FIXME(const_generics:defaults)
 407         if !infer_consts || arg_counts.consts > param_counts.consts {
 408             check_kind_count(
 409                 "const",
 410                 param_counts.consts,
 411                 param_counts.consts,
 412                 arg_counts.consts,
 413                 arg_counts.lifetimes + arg_counts.types,
 414             );
 415         }
 416         // Note that type errors are currently be emitted *after* const errors.
 417         if !infer_types
 418             || arg_counts.types > param_counts.types - defaults.types - has_self as usize {
 419             check_kind_count(
 420                 "type",
 421                 param_counts.types - defaults.types - has_self as usize,
 422                 param_counts.types - has_self as usize,
 423                 arg_counts.types,
 424                 arg_counts.lifetimes,
 425             )
 426         } else {
 427             (reported_late_bound_region_err.unwrap_or(false), None)
 428         }
 429     }
 430
 431     /// Creates the relevant generic argument substitutions
 432     /// corresponding to a set of generic parameters. This is a
 433     /// rather complex function. Let us try to explain the role
 434     /// of each of its parameters:
 435     ///
 436     /// To start, we are given the `def_id` of the thing we are
 437     /// creating the substitutions for, and a partial set of
 438     /// substitutions `parent_substs`. In general, the substitutions
 439     /// for an item begin with substitutions for all the "parents" of
 440     /// that item -- e.g., for a method it might include the
 441     /// parameters from the impl.
 442     ///
 443     /// Therefore, the method begins by walking down these parents,
 444     /// starting with the outermost parent and proceed inwards until
 445     /// it reaches `def_id`. For each parent `P`, it will check `parent_substs`
 446     /// first to see if the parent's substitutions are listed in there. If so,
 447     /// we can append those and move on. Otherwise, it invokes the
 448     /// three callback functions:
 449     ///
 450     /// - `args_for_def_id`: given the `DefId` `P`, supplies back the
 451     ///   generic arguments that were given to that parent from within
 452     ///   the path; so e.g., if you have `<T as Foo>::Bar`, the `DefId`
 453     ///   might refer to the trait `Foo`, and the arguments might be
 454     ///   `[T]`. The boolean value indicates whether to infer values
 455     ///   for arguments whose values were not explicitly provided.
 456     /// - `provided_kind`: given the generic parameter and the value from `args_for_def_id`,
 457     ///   instantiate a `Kind`.
 458     /// - `inferred_kind`: if no parameter was provided, and inference is enabled, then
 459     ///   creates a suitable inference variable.
 460     pub fn create_substs_for_generic_args<'a, 'b>(
 461         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 462         def_id: DefId,
 463         parent_substs: &[Kind<'tcx>],
 464         has_self: bool,
 465         self_ty: Option<Ty<'tcx>>,
 466         args_for_def_id: impl Fn(DefId) -> (Option<&'b GenericArgs>, bool),
 467         provided_kind: impl Fn(&GenericParamDef, &GenericArg) -> Kind<'tcx>,
 468         inferred_kind: impl Fn(Option<&[Kind<'tcx>]>, &GenericParamDef, bool) -> Kind<'tcx>,
 469     ) -> SubstsRef<'tcx> {
 470         // Collect the segments of the path; we need to substitute arguments
 471         // for parameters throughout the entire path (wherever there are
 472         // generic parameters).
 473         let mut parent_defs = tcx.generics_of(def_id);
 474         let count = parent_defs.count();
 475         let mut stack = vec![(def_id, parent_defs)];
 476         while let Some(def_id) = parent_defs.parent {
 477             parent_defs = tcx.generics_of(def_id);
 478             stack.push((def_id, parent_defs));
 479         }
 480
 481         // We manually build up the substitution, rather than using convenience
 482         // methods in `subst.rs`, so that we can iterate over the arguments and
 483         // parameters in lock-step linearly, instead of trying to match each pair.
 484         let mut substs: SmallVec<[Kind<'tcx>; 8]> = SmallVec::with_capacity(count);
 485
 486         // Iterate over each segment of the path.
 487         while let Some((def_id, defs)) = stack.pop() {
 488             let mut params = defs.params.iter().peekable();
 489
 490             // If we have already computed substitutions for parents, we can use those directly.
 491             while let Some(&param) = params.peek() {
 492                 if let Some(&kind) = parent_substs.get(param.index as usize) {
 493                     substs.push(kind);
 494                     params.next();
 495                 } else {
 496                     break;
 497                 }
 498             }
 499
 500             // `Self` is handled first, unless it's been handled in `parent_substs`.
 501             if has_self {
 502                 if let Some(&param) = params.peek() {
 503                     if param.index == 0 {
 504                         if let GenericParamDefKind::Type { .. } = param.kind {
 505                             substs.push(self_ty.map(|ty| ty.into())
 506                                 .unwrap_or_else(|| inferred_kind(None, param, true)));
 507                             params.next();
 508                         }
 509                     }
 510                 }
 511             }
 512
 513             // Check whether this segment takes generic arguments and the user has provided any.
 514             let (generic_args, infer_types) = args_for_def_id(def_id);
 515
 516             let mut args = generic_args.iter().flat_map(|generic_args| generic_args.args.iter())
 517                 .peekable();
 518
 519             loop {
 520                 // We're going to iterate through the generic arguments that the user
 521                 // provided, matching them with the generic parameters we expect.
 522                 // Mismatches can occur as a result of elided lifetimes, or for malformed
 523                 // input. We try to handle both sensibly.
 524                 match (args.peek(), params.peek()) {
 525                     (Some(&arg), Some(&param)) => {
 526                         match (arg, &param.kind) {
 527                             (GenericArg::Lifetime(_), GenericParamDefKind::Lifetime)
 528                             | (GenericArg::Type(_), GenericParamDefKind::Type { .. })
 529                             | (GenericArg::Const(_), GenericParamDefKind::Const) => {
 530                                 substs.push(provided_kind(param, arg));
 531                                 args.next();
 532                                 params.next();
 533                             }
 534                             (GenericArg::Type(_), GenericParamDefKind::Lifetime)
 535                             | (GenericArg::Const(_), GenericParamDefKind::Lifetime) => {
 536                                 // We expected a lifetime argument, but got a type or const
 537                                 // argument. That means we're inferring the lifetimes.
 538                                 substs.push(inferred_kind(None, param, infer_types));
 539                                 params.next();
 540                             }
 541                             (_, _) => {
 542                                 // We expected one kind of parameter, but the user provided
 543                                 // another. This is an error, but we need to handle it
 544                                 // gracefully so we can report sensible errors.
 545                                 // In this case, we're simply going to infer this argument.
 546                                 args.next();
 547                             }
 548                         }
 549                     }
 550                     (Some(_), None) => {
 551                         // We should never be able to reach this point with well-formed input.
 552                         // Getting to this point means the user supplied more arguments than
 553                         // there are parameters.
 554                         args.next();
 555                     }
 556                     (None, Some(&param)) => {
 557                         // If there are fewer arguments than parameters, it means
 558                         // we're inferring the remaining arguments.
 559                         substs.push(inferred_kind(Some(&substs), param, infer_types));
 560                         args.next();
 561                         params.next();
 562                     }
 563                     (None, None) => break,
 564                 }
 565             }
 566         }
 567
 568         tcx.intern_substs(&substs)
 569     }
 570
 571     /// Given the type/lifetime/const arguments provided to some path (along with
 572     /// an implicit `Self`, if this is a trait reference), returns the complete
 573     /// set of substitutions. This may involve applying defaulted type parameters.
 574     /// Also returns back constriants on associated types.
 575     ///
 576     /// Note that the type listing given here is *exactly* what the user provided.
 577     fn create_substs_for_ast_path<'a>(&self,
 578         span: Span,
 579         def_id: DefId,
 580         generic_args: &'a hir::GenericArgs,
 581         infer_types: bool,
 582         self_ty: Option<Ty<'tcx>>)
 583         -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'tcx>>, Option<Vec<Span>>)
 584     {
 585         // If the type is parameterized by this region, then replace this
 586         // region with the current anon region binding (in other words,
 587         // whatever & would get replaced with).
 588         debug!("create_substs_for_ast_path(def_id={:?}, self_ty={:?}, \
 589                 generic_args={:?})",
 590                def_id, self_ty, generic_args);
 591
 592         let tcx = self.tcx();
 593         let generic_params = tcx.generics_of(def_id);
 594
 595         // If a self-type was declared, one should be provided.
 596         assert_eq!(generic_params.has_self, self_ty.is_some());
 597
 598         let has_self = generic_params.has_self;
 599         let (_, potential_assoc_types) = Self::check_generic_arg_count(
 600             tcx,
 601             span,
 602             &generic_params,
 603             &generic_args,
 604             GenericArgPosition::Type,
 605             has_self,
 606             infer_types,
 607         );
 608
 609         let is_object = self_ty.map_or(false, |ty| {
 610             ty == self.tcx().types.trait_object_dummy_self
 611         });
 612         let default_needs_object_self = |param: &ty::GenericParamDef| {
 613             if let GenericParamDefKind::Type { has_default, .. } = param.kind {
 614                 if is_object && has_default {
 615                     if tcx.at(span).type_of(param.def_id).has_self_ty() {
 616                         // There is no suitable inference default for a type parameter
 617                         // that references self, in an object type.
 618                         return true;
 619                     }
 620                 }
 621             }
 622
 623             false
 624         };
 625
 626         let substs = Self::create_substs_for_generic_args(
 627             tcx,
 628             def_id,
 629             &[][..],
 630             self_ty.is_some(),
 631             self_ty,
 632             // Provide the generic args, and whether types should be inferred.
 633             |_| (Some(generic_args), infer_types),
 634             // Provide substitutions for parameters for which (valid) arguments have been provided.
 635             |param, arg| {
 636                 match (&param.kind, arg) {
 637                     (GenericParamDefKind::Lifetime, GenericArg::Lifetime(lt)) => {
 638                         self.ast_region_to_region(&lt, Some(param)).into()
 639                     }
 640                     (GenericParamDefKind::Type { .. }, GenericArg::Type(ty)) => {
 641                         self.ast_ty_to_ty(&ty).into()
 642                     }
 643                     (GenericParamDefKind::Const, GenericArg::Const(ct)) => {
 644                         self.ast_const_to_const(&ct.value, tcx.type_of(param.def_id)).into()
 645                     }
 646                     _ => unreachable!(),
 647                 }
 648             },
 649             // Provide substitutions for parameters for which arguments are inferred.
 650             |substs, param, infer_types| {
 651                 match param.kind {
 652                     GenericParamDefKind::Lifetime => tcx.lifetimes.re_static.into(),
 653                     GenericParamDefKind::Type { has_default, .. } => {
 654                         if !infer_types && has_default {
 655                             // No type parameter provided, but a default exists.
 656
 657                             // If we are converting an object type, then the
 658                             // `Self` parameter is unknown. However, some of the
 659                             // other type parameters may reference `Self` in their
 660                             // defaults. This will lead to an ICE if we are not
 661                             // careful!
 662                             if default_needs_object_self(param) {
 663                                 struct_span_err!(tcx.sess, span, E0393,
 664                                     "the type parameter `{}` must be explicitly specified",
 665                                     param.name
 666                                 )
 667                                     .span_label(span, format!(
 668                                         "missing reference to `{}`", param.name))
 669                                     .note(&format!(
 670                                         "because of the default `Self` reference, type parameters \
 671                                          must be specified on object types"))
 672                                     .emit();
 673                                 tcx.types.err.into()
 674                             } else {
 675                                 // This is a default type parameter.
 676                                 self.normalize_ty(
 677                                     span,
 678                                     tcx.at(span).type_of(param.def_id)
 679                                        .subst_spanned(tcx, substs.unwrap(), Some(span))
 680                                 ).into()
 681                             }
 682                         } else if infer_types {
 683                             // No type parameters were provided, we can infer all.
 684                             if !default_needs_object_self(param) {
 685                                 self.ty_infer_for_def(param, span).into()
 686                             } else {
 687                                 self.ty_infer(span).into()
 688                             }
 689                         } else {
 690                             // We've already errored above about the mismatch.
 691                             tcx.types.err.into()
 692                         }
 693                     }
 694                     GenericParamDefKind::Const => {
 695                         // FIXME(const_generics:defaults)
 696                         // We've already errored above about the mismatch.
 697                         tcx.consts.err.into()
 698                     }
 699                 }
 700             },
 701         );
 702
 703         // Convert associated-type bindings or constraints into a separate vector.
 704         // Example: Given this:
 705         //
 706         //     T: Iterator<Item = u32>
 707         //
 708         // The `T` is passed in as a self-type; the `Item = u32` is
 709         // not a "type parameter" of the `Iterator` trait, but rather
 710         // a restriction on `<T as Iterator>::Item`, so it is passed
 711         // back separately.
 712         let assoc_bindings = generic_args.bindings.iter()
 713             .map(|binding| {
 714                 let kind = match binding.kind {
 715                     hir::TypeBindingKind::Equality { ref ty } =>
 716                         ConvertedBindingKind::Equality(self.ast_ty_to_ty(ty)),
 717                     hir::TypeBindingKind::Constraint { ref bounds } =>
 718                         ConvertedBindingKind::Constraint(bounds.clone()),
 719                 };
 720                 ConvertedBinding {
 721                     item_name: binding.ident,
 722                     kind,
 723                     span: binding.span,
 724                 }
 725             })
 726             .collect();
 727
 728         debug!("create_substs_for_ast_path(generic_params={:?}, self_ty={:?}) -> {:?}",
 729                generic_params, self_ty, substs);
 730
 731         (substs, assoc_bindings, potential_assoc_types)
 732     }
 733
 734     /// Instantiates the path for the given trait reference, assuming that it's
 735     /// bound to a valid trait type. Returns the `DefId` of the defining trait.
 736     /// The type _cannot_ be a type other than a trait type.
 737     ///
 738     /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T = X>`
 739     /// are disallowed. Otherwise, they are pushed onto the vector given.
 740     pub fn instantiate_mono_trait_ref(&self,
 741         trait_ref: &hir::TraitRef,
 742         self_ty: Ty<'tcx>
 743     ) -> ty::TraitRef<'tcx>
 744     {
 745         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 746
 747         self.ast_path_to_mono_trait_ref(trait_ref.path.span,
 748                                         trait_ref.trait_def_id(),
 749                                         self_ty,
 750                                         trait_ref.path.segments.last().unwrap())
 751     }
 752
 753     /// The given trait-ref must actually be a trait.
 754     pub(super) fn instantiate_poly_trait_ref_inner(&self,
 755         trait_ref: &hir::TraitRef,
 756         self_ty: Ty<'tcx>,
 757         bounds: &mut Bounds<'tcx>,
 758         speculative: bool,
 759     ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
 760     {
 761         let trait_def_id = trait_ref.trait_def_id();
 762
 763         debug!("instantiate_poly_trait_ref({:?}, def_id={:?})", trait_ref, trait_def_id);
 764
 765         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 766
 767         let (substs, assoc_bindings, potential_assoc_types) = self.create_substs_for_ast_trait_ref(
 768             trait_ref.path.span,
 769             trait_def_id,
 770             self_ty,
 771             trait_ref.path.segments.last().unwrap(),
 772         );
 773         let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs));
 774
 775         let mut dup_bindings = FxHashMap::default();
 776         for binding in &assoc_bindings {
 777             // Specify type to assert that error was already reported in `Err` case.
 778             let _: Result<_, ErrorReported> =
 779                 self.add_predicates_for_ast_type_binding(
 780                     trait_ref.hir_ref_id,
 781                     poly_trait_ref,
 782                     binding,
 783                     bounds,
 784                     speculative,
 785                     &mut dup_bindings
 786                 );
 787             // Okay to ignore `Err` because of `ErrorReported` (see above).
 788         }
 789
 790         debug!("instantiate_poly_trait_ref({:?}, bounds={:?}) -> {:?}",
 791                trait_ref, bounds, poly_trait_ref);
 792         (poly_trait_ref, potential_assoc_types)
 793     }
 794
 795     /// Given a trait bound like `Debug`, applies that trait bound the given self-type to construct
 796     /// a full trait reference. The resulting trait reference is returned. This may also generate
 797     /// auxiliary bounds, which are added to `bounds`.
 798     ///
 799     /// Example:
 800     ///
 801     /// ```
 802     /// poly_trait_ref = Iterator<Item = u32>
 803     /// self_ty = Foo
 804     /// ```
 805     ///
 806     /// this would return `Foo: Iterator` and add `<Foo as Iterator>::Item = u32` into `bounds`.
 807     ///
 808     /// **A note on binders:** against our usual convention, there is an implied bounder around
 809     /// the `self_ty` and `poly_trait_ref` parameters here. So they may reference bound regions.
 810     /// If for example you had `for<'a> Foo<'a>: Bar<'a>`, then the `self_ty` would be `Foo<'a>`
 811     /// where `'a` is a bound region at depth 0. Similarly, the `poly_trait_ref` would be
 812     /// `Bar<'a>`. The returned poly-trait-ref will have this binder instantiated explicitly,
 813     /// however.
 814     pub fn instantiate_poly_trait_ref(&self,
 815         poly_trait_ref: &hir::PolyTraitRef,
 816         self_ty: Ty<'tcx>,
 817         bounds: &mut Bounds<'tcx>
 818     ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
 819     {
 820         self.instantiate_poly_trait_ref_inner(&poly_trait_ref.trait_ref, self_ty, bounds, false)
 821     }
 822
 823     fn ast_path_to_mono_trait_ref(&self,
 824         span: Span,
 825         trait_def_id: DefId,
 826         self_ty: Ty<'tcx>,
 827         trait_segment: &hir::PathSegment
 828     ) -> ty::TraitRef<'tcx>
 829     {
 830         let (substs, assoc_bindings, _) =
 831             self.create_substs_for_ast_trait_ref(span,
 832                                                  trait_def_id,
 833                                                  self_ty,
 834                                                  trait_segment);
 835         assoc_bindings.first().map(|b| AstConv::prohibit_assoc_ty_binding(self.tcx(), b.span));
 836         ty::TraitRef::new(trait_def_id, substs)
 837     }
 838
 839     fn create_substs_for_ast_trait_ref(
 840         &self,
 841         span: Span,
 842         trait_def_id: DefId,
 843         self_ty: Ty<'tcx>,
 844         trait_segment: &hir::PathSegment,
 845     ) -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'tcx>>, Option<Vec<Span>>) {
 846         debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
 847                trait_segment);
 848
 849         let trait_def = self.tcx().trait_def(trait_def_id);
 850
 851         if !self.tcx().features().unboxed_closures &&
 852             trait_segment.with_generic_args(|generic_args| generic_args.parenthesized)
 853             != trait_def.paren_sugar {
 854             // For now, require that parenthetical notation be used only with `Fn()` etc.
 855             let msg = if trait_def.paren_sugar {
 856                 "the precise format of `Fn`-family traits' type parameters is subject to change. \
 857                  Use parenthetical notation (Fn(Foo, Bar) -> Baz) instead"
 858             } else {
 859                 "parenthetical notation is only stable when used with `Fn`-family traits"
 860             };
 861             emit_feature_err(&self.tcx().sess.parse_sess, sym::unboxed_closures,
 862                              span, GateIssue::Language, msg);
 863         }
 864
 865         trait_segment.with_generic_args(|generic_args| {
 866             self.create_substs_for_ast_path(span,
 867                                             trait_def_id,
 868                                             generic_args,
 869                                             trait_segment.infer_types,
 870                                             Some(self_ty))
 871         })
 872     }
 873
 874     fn trait_defines_associated_type_named(&self,
 875                                            trait_def_id: DefId,
 876                                            assoc_name: ast::Ident)
 877                                            -> bool
 878     {
 879         self.tcx().associated_items(trait_def_id).any(|item| {
 880             item.kind == ty::AssocKind::Type &&
 881             self.tcx().hygienic_eq(assoc_name, item.ident, trait_def_id)
 882         })
 883     }
 884
 885     // Returns `true` if a bounds list includes `?Sized`.
 886     pub fn is_unsized(&self, ast_bounds: &[hir::GenericBound], span: Span) -> bool {
 887         let tcx = self.tcx();
 888
 889         // Try to find an unbound in bounds.
 890         let mut unbound = None;
 891         for ab in ast_bounds {
 892             if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab {
 893                 if unbound.is_none() {
 894                     unbound = Some(ptr.trait_ref.clone());
 895                 } else {
 896                     span_err!(
 897                         tcx.sess,
 898                         span,
 899                         E0203,
 900                         "type parameter has more than one relaxed default \
 901                         bound, only one is supported"
 902                     );
 903                 }
 904             }
 905         }
 906
 907         let kind_id = tcx.lang_items().require(SizedTraitLangItem);
 908         match unbound {
 909             Some(ref tpb) => {
 910                 // FIXME(#8559) currently requires the unbound to be built-in.
 911                 if let Ok(kind_id) = kind_id {
 912                     if tpb.path.res != Res::Def(DefKind::Trait, kind_id) {
 913                         tcx.sess.span_warn(
 914                             span,
 915                             "default bound relaxed for a type parameter, but \
 916                             this does nothing because the given bound is not \
 917                             a default. Only `?Sized` is supported",
 918                         );
 919                     }
 920                 }
 921             }
 922             _ if kind_id.is_ok() => {
 923                 return false;
 924             }
 925             // No lang item for `Sized`, so we can't add it as a bound.
 926             None => {}
 927         }
 928
 929         true
 930     }
 931
 932     /// This helper takes a *converted* parameter type (`param_ty`)
 933     /// and an *unconverted* list of bounds:
 934     ///
 935     /// ```
 936     /// fn foo<T: Debug>
 937     ///        ^  ^^^^^ `ast_bounds` parameter, in HIR form
 938     ///        |
 939     ///        `param_ty`, in ty form
 940     /// ```
 941     ///
 942     /// It adds these `ast_bounds` into the `bounds` structure.
 943     ///
 944     /// **A note on binders:** There is an implied binder around
 945     /// `param_ty` and `ast_bounds`. See `instantiate_poly_trait_ref`
 946     /// for more details.
 947     fn add_bounds(&self,
 948         param_ty: Ty<'tcx>,
 949         ast_bounds: &[hir::GenericBound],
 950         bounds: &mut Bounds<'tcx>,
 951     ) {
 952         let mut trait_bounds = Vec::new();
 953         let mut region_bounds = Vec::new();
 954
 955         for ast_bound in ast_bounds {
 956             match *ast_bound {
 957                 hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) =>
 958                     trait_bounds.push(b),
 959                 hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
 960                 hir::GenericBound::Outlives(ref l) =>
 961                     region_bounds.push(l),
 962             }
 963         }
 964
 965         for bound in trait_bounds {
 966             let (poly_trait_ref, _) = self.instantiate_poly_trait_ref(
 967                 bound,
 968                 param_ty,
 969                 bounds,
 970             );
 971             bounds.trait_bounds.push((poly_trait_ref, bound.span))
 972         }
 973
 974         bounds.region_bounds.extend(region_bounds
 975             .into_iter()
 976             .map(|r| (self.ast_region_to_region(r, None), r.span))
 977         );
 978     }
 979
 980     /// Translates a list of bounds from the HIR into the `Bounds` data structure.
 981     /// The self-type for the bounds is given by `param_ty`.
 982     ///
 983     /// Example:
 984     ///
 985     /// ```
 986     /// fn foo<T: Bar + Baz>() { }
 987     ///        ^  ^^^^^^^^^ ast_bounds
 988     ///        param_ty
 989     /// ```
 990     ///
 991     /// The `sized_by_default` parameter indicates if, in this context, the `param_ty` should be
 992     /// considered `Sized` unless there is an explicit `?Sized` bound.  This would be true in the
 993     /// example above, but is not true in supertrait listings like `trait Foo: Bar + Baz`.
 994     ///
 995     /// `span` should be the declaration size of the parameter.
 996     pub fn compute_bounds(&self,
 997         param_ty: Ty<'tcx>,
 998         ast_bounds: &[hir::GenericBound],
 999         sized_by_default: SizedByDefault,
1000         span: Span,
1001     ) -> Bounds<'tcx> {
1002         let mut bounds = Bounds::default();
1003
1004         self.add_bounds(param_ty, ast_bounds, &mut bounds);
1005         bounds.trait_bounds.sort_by_key(|(t, _)| t.def_id());
1006
1007         bounds.implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
1008             if !self.is_unsized(ast_bounds, span) {
1009                 Some(span)
1010             } else {
1011                 None
1012             }
1013         } else {
1014             None
1015         };
1016
1017         bounds
1018     }
1019
1020     fn add_predicates_for_ast_type_binding(
1021         &self,
1022         hir_ref_id: hir::HirId,
1023         trait_ref: ty::PolyTraitRef<'tcx>,
1024         binding: &ConvertedBinding<'tcx>,
1025         bounds: &mut Bounds<'tcx>,
1026         speculative: bool,
1027         dup_bindings: &mut FxHashMap<DefId, Span>,
1028     ) -> Result<(), ErrorReported> {
1029         let tcx = self.tcx();
1030
1031         if !speculative {
1032             // Given something like `U: SomeTrait<T = X>`, we want to produce a
1033             // predicate like `<U as SomeTrait>::T = X`. This is somewhat
1034             // subtle in the event that `T` is defined in a supertrait of
1035             // `SomeTrait`, because in that case we need to upcast.
1036             //
1037             // That is, consider this case:
1038             //
1039             // ```
1040             // trait SubTrait: SuperTrait<int> { }
1041             // trait SuperTrait<A> { type T; }
1042             //
1043             // ... B: SubTrait<T = foo> ...
1044             // ```
1045             //
1046             // We want to produce `<B as SuperTrait<int>>::T == foo`.
1047
1048             // Find any late-bound regions declared in `ty` that are not
1049             // declared in the trait-ref. These are not well-formed.
1050             //
1051             // Example:
1052             //
1053             //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
1054             //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
1055             if let ConvertedBindingKind::Equality(ty) = binding.kind {
1056                 let late_bound_in_trait_ref =
1057                     tcx.collect_constrained_late_bound_regions(&trait_ref);
1058                 let late_bound_in_ty =
1059                     tcx.collect_referenced_late_bound_regions(&ty::Binder::bind(ty));
1060                 debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
1061                 debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
1062                 for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
1063                     let br_name = match *br {
1064                         ty::BrNamed(_, name) => name,
1065                         _ => {
1066                             span_bug!(
1067                                 binding.span,
1068                                 "anonymous bound region {:?} in binding but not trait ref",
1069                                 br);
1070                         }
1071                     };
1072                     struct_span_err!(tcx.sess,
1073                                     binding.span,
1074                                     E0582,
1075                                     "binding for associated type `{}` references lifetime `{}`, \
1076                                      which does not appear in the trait input types",
1077                                     binding.item_name, br_name)
1078                         .emit();
1079                 }
1080             }
1081         }
1082
1083         let candidate = if self.trait_defines_associated_type_named(trait_ref.def_id(),
1084                                                                     binding.item_name) {
1085             // Simple case: X is defined in the current trait.
1086             Ok(trait_ref)
1087         } else {
1088             // Otherwise, we have to walk through the supertraits to find
1089             // those that do.
1090             let candidates = traits::supertraits(tcx, trait_ref).filter(|r| {
1091                 self.trait_defines_associated_type_named(r.def_id(), binding.item_name)
1092             });
1093             self.one_bound_for_assoc_type(candidates, &trait_ref.to_string(),
1094                                           binding.item_name, binding.span)
1095         }?;
1096
1097         let (assoc_ident, def_scope) =
1098             tcx.adjust_ident_and_get_scope(binding.item_name, candidate.def_id(), hir_ref_id);
1099         let assoc_ty = tcx.associated_items(candidate.def_id()).find(|i| {
1100             i.kind == ty::AssocKind::Type && i.ident.modern() == assoc_ident
1101         }).expect("missing associated type");
1102
1103         if !assoc_ty.vis.is_accessible_from(def_scope, tcx) {
1104             let msg = format!("associated type `{}` is private", binding.item_name);
1105             tcx.sess.span_err(binding.span, &msg);
1106         }
1107         tcx.check_stability(assoc_ty.def_id, Some(hir_ref_id), binding.span);
1108
1109         if !speculative {
1110             dup_bindings.entry(assoc_ty.def_id)
1111                 .and_modify(|prev_span| {
1112                     struct_span_err!(self.tcx().sess, binding.span, E0719,
1113                                      "the value of the associated type `{}` (from the trait `{}`) \
1114                                       is already specified",
1115                                      binding.item_name,
1116                                      tcx.def_path_str(assoc_ty.container.id()))
1117                         .span_label(binding.span, "re-bound here")
1118                         .span_label(*prev_span, format!("`{}` bound here first", binding.item_name))
1119                         .emit();
1120                 })
1121                 .or_insert(binding.span);
1122         }
1123
1124         match binding.kind {
1125             ConvertedBindingKind::Equality(ref ty) => {
1126                 // "Desugar" a constraint like `T: Iterator<Item = u32>` this to
1127                 // the "projection predicate" for:
1128                 //
1129                 // `<T as Iterator>::Item = u32`
1130                 bounds.projection_bounds.push((candidate.map_bound(|trait_ref| {
1131                     ty::ProjectionPredicate {
1132                         projection_ty: ty::ProjectionTy::from_ref_and_name(
1133                             tcx,
1134                             trait_ref,
1135                             binding.item_name,
1136                         ),
1137                         ty,
1138                     }
1139                 }), binding.span));
1140             }
1141             ConvertedBindingKind::Constraint(ref ast_bounds) => {
1142                 // "Desugar" a constraint like `T: Iterator<Item: Debug>` to
1143                 //
1144                 // `<T as Iterator>::Item: Debug`
1145                 //
1146                 // Calling `skip_binder` is okay, because the predicates are re-bound later by
1147                 // `instantiate_poly_trait_ref`.
1148                 let param_ty = tcx.mk_projection(assoc_ty.def_id, candidate.skip_binder().substs);
1149                 self.add_bounds(
1150                     param_ty,
1151                     ast_bounds,
1152                     bounds,
1153                 );
1154             }
1155         }
1156         Ok(())
1157     }
1158
1159     fn ast_path_to_ty(&self,
1160         span: Span,
1161         did: DefId,
1162         item_segment: &hir::PathSegment)
1163         -> Ty<'tcx>
1164     {
1165         let substs = self.ast_path_substs_for_ty(span, did, item_segment);
1166         self.normalize_ty(
1167             span,
1168             self.tcx().at(span).type_of(did).subst(self.tcx(), substs)
1169         )
1170     }
1171
1172     /// Transform a `PolyTraitRef` into a `PolyExistentialTraitRef` by
1173     /// removing the dummy `Self` type (`trait_object_dummy_self`).
1174     fn trait_ref_to_existential(&self, trait_ref: ty::TraitRef<'tcx>)
1175                                 -> ty::ExistentialTraitRef<'tcx> {
1176         if trait_ref.self_ty() != self.tcx().types.trait_object_dummy_self {
1177             bug!("trait_ref_to_existential called on {:?} with non-dummy Self", trait_ref);
1178         }
1179         ty::ExistentialTraitRef::erase_self_ty(self.tcx(), trait_ref)
1180     }
1181
1182     fn conv_object_ty_poly_trait_ref(&self,
1183         span: Span,
1184         trait_bounds: &[hir::PolyTraitRef],
1185         lifetime: &hir::Lifetime)
1186         -> Ty<'tcx>
1187     {
1188         let tcx = self.tcx();
1189
1190         let mut bounds = Bounds::default();
1191         let mut potential_assoc_types = Vec::new();
1192         let dummy_self = self.tcx().types.trait_object_dummy_self;
1193         // FIXME: we want to avoid collecting into a `Vec` here, but simply cloning the iterator is
1194         // not straightforward due to the borrow checker.
1195         let bound_trait_refs: Vec<_> = trait_bounds
1196             .iter()
1197             .rev()
1198             .map(|trait_bound| {
1199                 let (trait_ref, cur_potential_assoc_types) = self.instantiate_poly_trait_ref(
1200                     trait_bound,
1201                     dummy_self,
1202                     &mut bounds,
1203                 );
1204                 potential_assoc_types.extend(cur_potential_assoc_types.into_iter().flatten());
1205                 (trait_ref, trait_bound.span)
1206             })
1207             .collect();
1208
1209         // Expand trait aliases recursively and check that only one regular (non-auto) trait
1210         // is used and no 'maybe' bounds are used.
1211         let expanded_traits = traits::expand_trait_aliases(tcx, bound_trait_refs.iter().cloned());
1212         let (mut auto_traits, regular_traits): (Vec<_>, Vec<_>) =
1213             expanded_traits.partition(|i| tcx.trait_is_auto(i.trait_ref().def_id()));
1214         if regular_traits.len() > 1 {
1215             let first_trait = &regular_traits[0];
1216             let additional_trait = &regular_traits[1];
1217             let mut err = struct_span_err!(tcx.sess, additional_trait.bottom().1, E0225,
1218                 "only auto traits can be used as additional traits in a trait object"
1219             );
1220             additional_trait.label_with_exp_info(&mut err,
1221                 "additional non-auto trait", "additional use");
1222             first_trait.label_with_exp_info(&mut err,
1223                 "first non-auto trait", "first use");
1224             err.emit();
1225         }
1226
1227         if regular_traits.is_empty() && auto_traits.is_empty() {
1228             span_err!(tcx.sess, span, E0224,
1229                 "at least one non-builtin trait is required for an object type");
1230             return tcx.types.err;
1231         }
1232
1233         // Check that there are no gross object safety violations;
1234         // most importantly, that the supertraits don't contain `Self`,
1235         // to avoid ICEs.
1236         for item in &regular_traits {
1237             let object_safety_violations =
1238                 tcx.global_tcx().astconv_object_safety_violations(item.trait_ref().def_id());
1239             if !object_safety_violations.is_empty() {
1240                 tcx.report_object_safety_error(
1241                     span,
1242                     item.trait_ref().def_id(),
1243                     object_safety_violations
1244                 )
1245                     .map(|mut err| err.emit());
1246                 return tcx.types.err;
1247             }
1248         }
1249
1250         // Use a `BTreeSet` to keep output in a more consistent order.
1251         let mut associated_types = BTreeSet::default();
1252
1253         let regular_traits_refs = bound_trait_refs
1254             .into_iter()
1255             .filter(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id()))
1256             .map(|(trait_ref, _)| trait_ref);
1257         for trait_ref in traits::elaborate_trait_refs(tcx, regular_traits_refs) {
1258             debug!("conv_object_ty_poly_trait_ref: observing object predicate `{:?}`", trait_ref);
1259             match trait_ref {
1260                 ty::Predicate::Trait(pred) => {
1261                     associated_types
1262                         .extend(tcx.associated_items(pred.def_id())
1263                         .filter(|item| item.kind == ty::AssocKind::Type)
1264                         .map(|item| item.def_id));
1265                 }
1266                 ty::Predicate::Projection(pred) => {
1267                     // A `Self` within the original bound will be substituted with a
1268                     // `trait_object_dummy_self`, so check for that.
1269                     let references_self =
1270                         pred.skip_binder().ty.walk().any(|t| t == dummy_self);
1271
1272                     // If the projection output contains `Self`, force the user to
1273                     // elaborate it explicitly to avoid a lot of complexity.
1274                     //
1275                     // The "classicaly useful" case is the following:
1276                     // ```
1277                     //     trait MyTrait: FnMut() -> <Self as MyTrait>::MyOutput {
1278                     //         type MyOutput;
1279                     //     }
1280                     // ```
1281                     //
1282                     // Here, the user could theoretically write `dyn MyTrait<Output = X>`,
1283                     // but actually supporting that would "expand" to an infinitely-long type
1284                     // `fix $ τ → dyn MyTrait<MyOutput = X, Output = <τ as MyTrait>::MyOutput`.
1285                     //
1286                     // Instead, we force the user to write `dyn MyTrait<MyOutput = X, Output = X>`,
1287                     // which is uglier but works. See the discussion in #56288 for alternatives.
1288                     if !references_self {
1289                         // Include projections defined on supertraits.
1290                         bounds.projection_bounds.push((pred, DUMMY_SP))
1291                     }
1292                 }
1293                 _ => ()
1294             }
1295         }
1296
1297         for (projection_bound, _) in &bounds.projection_bounds {
1298             associated_types.remove(&projection_bound.projection_def_id());
1299         }
1300
1301         if !associated_types.is_empty() {
1302             let names = associated_types.iter().map(|item_def_id| {
1303                 let assoc_item = tcx.associated_item(*item_def_id);
1304                 let trait_def_id = assoc_item.container.id();
1305                 format!(
1306                     "`{}` (from the trait `{}`)",
1307                     assoc_item.ident,
1308                     tcx.def_path_str(trait_def_id),
1309                 )
1310             }).collect::<Vec<_>>().join(", ");
1311             let mut err = struct_span_err!(
1312                 tcx.sess,
1313                 span,
1314                 E0191,
1315                 "the value of the associated type{} {} must be specified",
1316                 if associated_types.len() == 1 { "" } else { "s" },
1317                 names,
1318             );
1319             let (suggest, potential_assoc_types_spans) =
1320                 if potential_assoc_types.len() == associated_types.len() {
1321                     // Only suggest when the amount of missing associated types equals the number of
1322                     // extra type arguments present, as that gives us a relatively high confidence
1323                     // that the user forgot to give the associtated type's name. The canonical
1324                     // example would be trying to use `Iterator<isize>` instead of
1325                     // `Iterator<Item = isize>`.
1326                     (true, potential_assoc_types)
1327                 } else {
1328                     (false, Vec::new())
1329                 };
1330             let mut suggestions = Vec::new();
1331             for (i, item_def_id) in associated_types.iter().enumerate() {
1332                 let assoc_item = tcx.associated_item(*item_def_id);
1333                 err.span_label(
1334                     span,
1335                     format!("associated type `{}` must be specified", assoc_item.ident),
1336                 );
1337                 if item_def_id.is_local() {
1338                     err.span_label(
1339                         tcx.def_span(*item_def_id),
1340                         format!("`{}` defined here", assoc_item.ident),
1341                     );
1342                 }
1343                 if suggest {
1344                     if let Ok(snippet) = tcx.sess.source_map().span_to_snippet(
1345                         potential_assoc_types_spans[i],
1346                     ) {
1347                         suggestions.push((
1348                             potential_assoc_types_spans[i],
1349                             format!("{} = {}", assoc_item.ident, snippet),
1350                         ));
1351                     }
1352                 }
1353             }
1354             if !suggestions.is_empty() {
1355                 let msg = format!("if you meant to specify the associated {}, write",
1356                     if suggestions.len() == 1 { "type" } else { "types" });
1357                 err.multipart_suggestion(
1358                     &msg,
1359                     suggestions,
1360                     Applicability::MaybeIncorrect,
1361                 );
1362             }
1363             err.emit();
1364         }
1365
1366         // De-duplicate auto traits so that, e.g., `dyn Trait + Send + Send` is the same as
1367         // `dyn Trait + Send`.
1368         auto_traits.sort_by_key(|i| i.trait_ref().def_id());
1369         auto_traits.dedup_by_key(|i| i.trait_ref().def_id());
1370         debug!("regular_traits: {:?}", regular_traits);
1371         debug!("auto_traits: {:?}", auto_traits);
1372
1373         // Erase the `dummy_self` (`trait_object_dummy_self`) used above.
1374         let existential_trait_refs = regular_traits.iter().map(|i| {
1375             i.trait_ref().map_bound(|trait_ref| self.trait_ref_to_existential(trait_ref))
1376         });
1377         let existential_projections = bounds.projection_bounds.iter().map(|(bound, _)| {
1378             bound.map_bound(|b| {
1379                 let trait_ref = self.trait_ref_to_existential(b.projection_ty.trait_ref(tcx));
1380                 ty::ExistentialProjection {
1381                     ty: b.ty,
1382                     item_def_id: b.projection_ty.item_def_id,
1383                     substs: trait_ref.substs,
1384                 }
1385             })
1386         });
1387
1388         // Calling `skip_binder` is okay because the predicates are re-bound.
1389         let regular_trait_predicates = existential_trait_refs.map(
1390             |trait_ref| ty::ExistentialPredicate::Trait(*trait_ref.skip_binder()));
1391         let auto_trait_predicates = auto_traits.into_iter().map(
1392             |trait_ref| ty::ExistentialPredicate::AutoTrait(trait_ref.trait_ref().def_id()));
1393         let mut v =
1394             regular_trait_predicates
1395             .chain(auto_trait_predicates)
1396             .chain(existential_projections
1397                 .map(|x| ty::ExistentialPredicate::Projection(*x.skip_binder())))
1398             .collect::<SmallVec<[_; 8]>>();
1399         v.sort_by(|a, b| a.stable_cmp(tcx, b));
1400         v.dedup();
1401         let existential_predicates = ty::Binder::bind(tcx.mk_existential_predicates(v.into_iter()));
1402
1403         // Use explicitly-specified region bound.
1404         let region_bound = if !lifetime.is_elided() {
1405             self.ast_region_to_region(lifetime, None)
1406         } else {
1407             self.compute_object_lifetime_bound(span, existential_predicates).unwrap_or_else(|| {
1408                 if tcx.named_region(lifetime.hir_id).is_some() {
1409                     self.ast_region_to_region(lifetime, None)
1410                 } else {
1411                     self.re_infer(span, None).unwrap_or_else(|| {
1412                         span_err!(tcx.sess, span, E0228,
1413                             "the lifetime bound for this object type cannot be deduced \
1414                              from context; please supply an explicit bound");
1415                         tcx.lifetimes.re_static
1416                     })
1417                 }
1418             })
1419         };
1420         debug!("region_bound: {:?}", region_bound);
1421
1422         let ty = tcx.mk_dynamic(existential_predicates, region_bound);
1423         debug!("trait_object_type: {:?}", ty);
1424         ty
1425     }
1426
1427     fn report_ambiguous_associated_type(
1428         &self,
1429         span: Span,
1430         type_str: &str,
1431         trait_str: &str,
1432         name: &str,
1433     ) {
1434         let mut err = struct_span_err!(self.tcx().sess, span, E0223, "ambiguous associated type");
1435         if let (Some(_), Ok(snippet)) = (
1436             self.tcx().sess.confused_type_with_std_module.borrow().get(&span),
1437             self.tcx().sess.source_map().span_to_snippet(span),
1438          ) {
1439             err.span_suggestion(
1440                 span,
1441                 "you are looking for the module in `std`, not the primitive type",
1442                 format!("std::{}", snippet),
1443                 Applicability::MachineApplicable,
1444             );
1445         } else {
1446             err.span_suggestion(
1447                     span,
1448                     "use fully-qualified syntax",
1449                     format!("<{} as {}>::{}", type_str, trait_str, name),
1450                     Applicability::HasPlaceholders
1451             );
1452         }
1453         err.emit();
1454     }
1455
1456     // Search for a bound on a type parameter which includes the associated item
1457     // given by `assoc_name`. `ty_param_def_id` is the `DefId` of the type parameter
1458     // This function will fail if there are no suitable bounds or there is
1459     // any ambiguity.
1460     fn find_bound_for_assoc_item(&self,
1461                                  ty_param_def_id: DefId,
1462                                  assoc_name: ast::Ident,
1463                                  span: Span)
1464                                  -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1465     {
1466         let tcx = self.tcx();
1467
1468         let predicates = &self.get_type_parameter_bounds(span, ty_param_def_id).predicates;
1469         let bounds = predicates.iter().filter_map(|(p, _)| p.to_opt_poly_trait_ref());
1470
1471         // Check that there is exactly one way to find an associated type with the
1472         // correct name.
1473         let suitable_bounds = traits::transitive_bounds(tcx, bounds)
1474             .filter(|b| self.trait_defines_associated_type_named(b.def_id(), assoc_name));
1475
1476         let param_hir_id = tcx.hir().as_local_hir_id(ty_param_def_id).unwrap();
1477         let param_name = tcx.hir().ty_param_name(param_hir_id);
1478         self.one_bound_for_assoc_type(suitable_bounds,
1479                                       &param_name.as_str(),
1480                                       assoc_name,
1481                                       span)
1482     }
1483
1484     // Checks that `bounds` contains exactly one element and reports appropriate
1485     // errors otherwise.
1486     fn one_bound_for_assoc_type<I>(&self,
1487                                    mut bounds: I,
1488                                    ty_param_name: &str,
1489                                    assoc_name: ast::Ident,
1490                                    span: Span)
1491         -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1492         where I: Iterator<Item=ty::PolyTraitRef<'tcx>>
1493     {
1494         let bound = match bounds.next() {
1495             Some(bound) => bound,
1496             None => {
1497                 struct_span_err!(self.tcx().sess, span, E0220,
1498                                  "associated type `{}` not found for `{}`",
1499                                  assoc_name,
1500                                  ty_param_name)
1501                   .span_label(span, format!("associated type `{}` not found", assoc_name))
1502                   .emit();
1503                 return Err(ErrorReported);
1504             }
1505         };
1506
1507         if let Some(bound2) = bounds.next() {
1508             let bounds = iter::once(bound).chain(iter::once(bound2)).chain(bounds);
1509             let mut err = struct_span_err!(
1510                 self.tcx().sess, span, E0221,
1511                 "ambiguous associated type `{}` in bounds of `{}`",
1512                 assoc_name,
1513                 ty_param_name);
1514             err.span_label(span, format!("ambiguous associated type `{}`", assoc_name));
1515
1516             for bound in bounds {
1517                 let bound_span = self.tcx().associated_items(bound.def_id()).find(|item| {
1518                     item.kind == ty::AssocKind::Type &&
1519                         self.tcx().hygienic_eq(assoc_name, item.ident, bound.def_id())
1520                 })
1521                 .and_then(|item| self.tcx().hir().span_if_local(item.def_id));
1522
1523                 if let Some(span) = bound_span {
1524                     err.span_label(span, format!("ambiguous `{}` from `{}`",
1525                                                  assoc_name,
1526                                                  bound));
1527                 } else {
1528                     span_note!(&mut err, span,
1529                                "associated type `{}` could derive from `{}`",
1530                                ty_param_name,
1531                                bound);
1532                 }
1533             }
1534             err.emit();
1535         }
1536
1537         return Ok(bound);
1538     }
1539
1540     // Create a type from a path to an associated type.
1541     // For a path `A::B::C::D`, `qself_ty` and `qself_def` are the type and def for `A::B::C`
1542     // and item_segment is the path segment for `D`. We return a type and a def for
1543     // the whole path.
1544     // Will fail except for `T::A` and `Self::A`; i.e., if `qself_ty`/`qself_def` are not a type
1545     // parameter or `Self`.
1546     pub fn associated_path_to_ty(
1547         &self,
1548         hir_ref_id: hir::HirId,
1549         span: Span,
1550         qself_ty: Ty<'tcx>,
1551         qself_res: Res,
1552         assoc_segment: &hir::PathSegment,
1553         permit_variants: bool,
1554     ) -> Result<(Ty<'tcx>, DefKind, DefId), ErrorReported> {
1555         let tcx = self.tcx();
1556         let assoc_ident = assoc_segment.ident;
1557
1558         debug!("associated_path_to_ty: {:?}::{}", qself_ty, assoc_ident);
1559
1560         self.prohibit_generics(slice::from_ref(assoc_segment));
1561
1562         // Check if we have an enum variant.
1563         let mut variant_resolution = None;
1564         if let ty::Adt(adt_def, _) = qself_ty.sty {
1565             if adt_def.is_enum() {
1566                 let variant_def = adt_def.variants.iter().find(|vd| {
1567                     tcx.hygienic_eq(assoc_ident, vd.ident, adt_def.did)
1568                 });
1569                 if let Some(variant_def) = variant_def {
1570                     if permit_variants {
1571                         check_type_alias_enum_variants_enabled(tcx, span);
1572                         tcx.check_stability(variant_def.def_id, Some(hir_ref_id), span);
1573                         return Ok((qself_ty, DefKind::Variant, variant_def.def_id));
1574                     } else {
1575                         variant_resolution = Some(variant_def.def_id);
1576                     }
1577                 }
1578             }
1579         }
1580
1581         // Find the type of the associated item, and the trait where the associated
1582         // item is declared.
1583         let bound = match (&qself_ty.sty, qself_res) {
1584             (_, Res::SelfTy(Some(_), Some(impl_def_id))) => {
1585                 // `Self` in an impl of a trait -- we have a concrete self type and a
1586                 // trait reference.
1587                 let trait_ref = match tcx.impl_trait_ref(impl_def_id) {
1588                     Some(trait_ref) => trait_ref,
1589                     None => {
1590                         // A cycle error occurred, most likely.
1591                         return Err(ErrorReported);
1592                     }
1593                 };
1594
1595                 let candidates = traits::supertraits(tcx, ty::Binder::bind(trait_ref))
1596                     .filter(|r| self.trait_defines_associated_type_named(r.def_id(), assoc_ident));
1597
1598                 self.one_bound_for_assoc_type(candidates, "Self", assoc_ident, span)?
1599             }
1600             (&ty::Param(_), Res::SelfTy(Some(param_did), None)) |
1601             (&ty::Param(_), Res::Def(DefKind::TyParam, param_did)) => {
1602                 self.find_bound_for_assoc_item(param_did, assoc_ident, span)?
1603             }
1604             _ => {
1605                 if variant_resolution.is_some() {
1606                     // Variant in type position
1607                     let msg = format!("expected type, found variant `{}`", assoc_ident);
1608                     tcx.sess.span_err(span, &msg);
1609                 } else if qself_ty.is_enum() {
1610                     let mut err = tcx.sess.struct_span_err(
1611                         assoc_ident.span,
1612                         &format!("no variant `{}` in enum `{}`", assoc_ident, qself_ty),
1613                     );
1614
1615                     let adt_def = qself_ty.ty_adt_def().expect("enum is not an ADT");
1616                     if let Some(suggested_name) = find_best_match_for_name(
1617                         adt_def.variants.iter().map(|variant| &variant.ident.name),
1618                         &assoc_ident.as_str(),
1619                         None,
1620                     ) {
1621                         err.span_suggestion(
1622                             assoc_ident.span,
1623                             "there is a variant with a similar name",
1624                             suggested_name.to_string(),
1625                             Applicability::MaybeIncorrect,
1626                         );
1627                     } else {
1628                         err.span_label(span, format!("variant not found in `{}`", qself_ty));
1629                     }
1630
1631                     if let Some(sp) = tcx.hir().span_if_local(adt_def.did) {
1632                         let sp = tcx.sess.source_map().def_span(sp);
1633                         err.span_label(sp, format!("variant `{}` not found here", assoc_ident));
1634                     }
1635
1636                     err.emit();
1637                 } else if !qself_ty.references_error() {
1638                     // Don't print `TyErr` to the user.
1639                     self.report_ambiguous_associated_type(
1640                         span,
1641                         &qself_ty.to_string(),
1642                         "Trait",
1643                         &assoc_ident.as_str(),
1644                     );
1645                 }
1646                 return Err(ErrorReported);
1647             }
1648         };
1649
1650         let trait_did = bound.def_id();
1651         let (assoc_ident, def_scope) =
1652             tcx.adjust_ident_and_get_scope(assoc_ident, trait_did, hir_ref_id);
1653         let item = tcx.associated_items(trait_did).find(|i| {
1654             Namespace::from(i.kind) == Namespace::Type &&
1655                 i.ident.modern() == assoc_ident
1656         }).expect("missing associated type");
1657
1658         let ty = self.projected_ty_from_poly_trait_ref(span, item.def_id, bound);
1659         let ty = self.normalize_ty(span, ty);
1660
1661         let kind = DefKind::AssocTy;
1662         if !item.vis.is_accessible_from(def_scope, tcx) {
1663             let msg = format!("{} `{}` is private", kind.descr(), assoc_ident);
1664             tcx.sess.span_err(span, &msg);
1665         }
1666         tcx.check_stability(item.def_id, Some(hir_ref_id), span);
1667
1668         if let Some(variant_def_id) = variant_resolution {
1669             let mut err = tcx.struct_span_lint_hir(
1670                 AMBIGUOUS_ASSOCIATED_ITEMS,
1671                 hir_ref_id,
1672                 span,
1673                 "ambiguous associated item",
1674             );
1675
1676             let mut could_refer_to = |kind: DefKind, def_id, also| {
1677                 let note_msg = format!("`{}` could{} refer to {} defined here",
1678                                        assoc_ident, also, kind.descr());
1679                 err.span_note(tcx.def_span(def_id), &note_msg);
1680             };
1681             could_refer_to(DefKind::Variant, variant_def_id, "");
1682             could_refer_to(kind, item.def_id, " also");
1683
1684             err.span_suggestion(
1685                 span,
1686                 "use fully-qualified syntax",
1687                 format!("<{} as {}>::{}", qself_ty, "Trait", assoc_ident),
1688                 Applicability::HasPlaceholders,
1689             ).emit();
1690         }
1691
1692         Ok((ty, kind, item.def_id))
1693     }
1694
1695     fn qpath_to_ty(&self,
1696                    span: Span,
1697                    opt_self_ty: Option<Ty<'tcx>>,
1698                    item_def_id: DefId,
1699                    trait_segment: &hir::PathSegment,
1700                    item_segment: &hir::PathSegment)
1701                    -> Ty<'tcx>
1702     {
1703         let tcx = self.tcx();
1704         let trait_def_id = tcx.parent(item_def_id).unwrap();
1705
1706         self.prohibit_generics(slice::from_ref(item_segment));
1707
1708         let self_ty = if let Some(ty) = opt_self_ty {
1709             ty
1710         } else {
1711             let path_str = tcx.def_path_str(trait_def_id);
1712             self.report_ambiguous_associated_type(
1713                 span,
1714                 "Type",
1715                 &path_str,
1716                 &item_segment.ident.as_str(),
1717             );
1718             return tcx.types.err;
1719         };
1720
1721         debug!("qpath_to_ty: self_type={:?}", self_ty);
1722
1723         let trait_ref = self.ast_path_to_mono_trait_ref(span,
1724                                                         trait_def_id,
1725                                                         self_ty,
1726                                                         trait_segment);
1727
1728         debug!("qpath_to_ty: trait_ref={:?}", trait_ref);
1729
1730         self.normalize_ty(span, tcx.mk_projection(item_def_id, trait_ref.substs))
1731     }
1732
1733     pub fn prohibit_generics<'a, T: IntoIterator<Item = &'a hir::PathSegment>>(
1734             &self, segments: T) -> bool {
1735         let mut has_err = false;
1736         for segment in segments {
1737             segment.with_generic_args(|generic_args| {
1738                 let (mut err_for_lt, mut err_for_ty, mut err_for_ct) = (false, false, false);
1739                 for arg in &generic_args.args {
1740                     let (span, kind) = match arg {
1741                         hir::GenericArg::Lifetime(lt) => {
1742                             if err_for_lt { continue }
1743                             err_for_lt = true;
1744                             has_err = true;
1745                             (lt.span, "lifetime")
1746                         }
1747                         hir::GenericArg::Type(ty) => {
1748                             if err_for_ty { continue }
1749                             err_for_ty = true;
1750                             has_err = true;
1751                             (ty.span, "type")
1752                         }
1753                         hir::GenericArg::Const(ct) => {
1754                             if err_for_ct { continue }
1755                             err_for_ct = true;
1756                             (ct.span, "const")
1757                         }
1758                     };
1759                     let mut err = struct_span_err!(
1760                         self.tcx().sess,
1761                         span,
1762                         E0109,
1763                         "{} arguments are not allowed for this type",
1764                         kind,
1765                     );
1766                     err.span_label(span, format!("{} argument not allowed", kind));
1767                     err.emit();
1768                     if err_for_lt && err_for_ty && err_for_ct {
1769                         break;
1770                     }
1771                 }
1772                 for binding in &generic_args.bindings {
1773                     has_err = true;
1774                     Self::prohibit_assoc_ty_binding(self.tcx(), binding.span);
1775                     break;
1776                 }
1777             })
1778         }
1779         has_err
1780     }
1781
1782     pub fn prohibit_assoc_ty_binding(tcx: TyCtxt<'_, '_, '_>, span: Span) {
1783         let mut err = struct_span_err!(tcx.sess, span, E0229,
1784                                        "associated type bindings are not allowed here");
1785         err.span_label(span, "associated type not allowed here").emit();
1786     }
1787
1788     // FIXME(eddyb, varkor) handle type paths here too, not just value ones.
1789     pub fn def_ids_for_value_path_segments(
1790         &self,
1791         segments: &[hir::PathSegment],
1792         self_ty: Option<Ty<'tcx>>,
1793         kind: DefKind,
1794         def_id: DefId,
1795     ) -> Vec<PathSeg> {
1796         // We need to extract the type parameters supplied by the user in
1797         // the path `path`. Due to the current setup, this is a bit of a
1798         // tricky-process; the problem is that resolve only tells us the
1799         // end-point of the path resolution, and not the intermediate steps.
1800         // Luckily, we can (at least for now) deduce the intermediate steps
1801         // just from the end-point.
1802         //
1803         // There are basically five cases to consider:
1804         //
1805         // 1. Reference to a constructor of a struct:
1806         //
1807         //        struct Foo<T>(...)
1808         //
1809         //    In this case, the parameters are declared in the type space.
1810         //
1811         // 2. Reference to a constructor of an enum variant:
1812         //
1813         //        enum E<T> { Foo(...) }
1814         //
1815         //    In this case, the parameters are defined in the type space,
1816         //    but may be specified either on the type or the variant.
1817         //
1818         // 3. Reference to a fn item or a free constant:
1819         //
1820         //        fn foo<T>() { }
1821         //
1822         //    In this case, the path will again always have the form
1823         //    `a::b::foo::<T>` where only the final segment should have
1824         //    type parameters. However, in this case, those parameters are
1825         //    declared on a value, and hence are in the `FnSpace`.
1826         //
1827         // 4. Reference to a method or an associated constant:
1828         //
1829         //        impl<A> SomeStruct<A> {
1830         //            fn foo<B>(...)
1831         //        }
1832         //
1833         //    Here we can have a path like
1834         //    `a::b::SomeStruct::<A>::foo::<B>`, in which case parameters
1835         //    may appear in two places. The penultimate segment,
1836         //    `SomeStruct::<A>`, contains parameters in TypeSpace, and the
1837         //    final segment, `foo::<B>` contains parameters in fn space.
1838         //
1839         // The first step then is to categorize the segments appropriately.
1840
1841         let tcx = self.tcx();
1842
1843         assert!(!segments.is_empty());
1844         let last = segments.len() - 1;
1845
1846         let mut path_segs = vec![];
1847
1848         match kind {
1849             // Case 1. Reference to a struct constructor.
1850             DefKind::Ctor(CtorOf::Struct, ..) => {
1851                 // Everything but the final segment should have no
1852                 // parameters at all.
1853                 let generics = tcx.generics_of(def_id);
1854                 // Variant and struct constructors use the
1855                 // generics of their parent type definition.
1856                 let generics_def_id = generics.parent.unwrap_or(def_id);
1857                 path_segs.push(PathSeg(generics_def_id, last));
1858             }
1859
1860             // Case 2. Reference to a variant constructor.
1861             DefKind::Ctor(CtorOf::Variant, ..)
1862             | DefKind::Variant => {
1863                 let adt_def = self_ty.map(|t| t.ty_adt_def().unwrap());
1864                 let (generics_def_id, index) = if let Some(adt_def) = adt_def {
1865                     debug_assert!(adt_def.is_enum());
1866                     (adt_def.did, last)
1867                 } else if last >= 1 && segments[last - 1].args.is_some() {
1868                     // Everything but the penultimate segment should have no
1869                     // parameters at all.
1870                     let mut def_id = def_id;
1871
1872                     // `DefKind::Ctor` -> `DefKind::Variant`
1873                     if let DefKind::Ctor(..) = kind {
1874                         def_id = tcx.parent(def_id).unwrap()
1875                     }
1876
1877                     // `DefKind::Variant` -> `DefKind::Enum`
1878                     let enum_def_id = tcx.parent(def_id).unwrap();
1879                     (enum_def_id, last - 1)
1880                 } else {
1881                     // FIXME: lint here recommending `Enum::<...>::Variant` form
1882                     // instead of `Enum::Variant::<...>` form.
1883
1884                     // Everything but the final segment should have no
1885                     // parameters at all.
1886                     let generics = tcx.generics_of(def_id);
1887                     // Variant and struct constructors use the
1888                     // generics of their parent type definition.
1889                     (generics.parent.unwrap_or(def_id), last)
1890                 };
1891                 path_segs.push(PathSeg(generics_def_id, index));
1892             }
1893
1894             // Case 3. Reference to a top-level value.
1895             DefKind::Fn
1896             | DefKind::Const
1897             | DefKind::ConstParam
1898             | DefKind::Static => {
1899                 path_segs.push(PathSeg(def_id, last));
1900             }
1901
1902             // Case 4. Reference to a method or associated const.
1903             DefKind::Method
1904             | DefKind::AssocConst => {
1905                 if segments.len() >= 2 {
1906                     let generics = tcx.generics_of(def_id);
1907                     path_segs.push(PathSeg(generics.parent.unwrap(), last - 1));
1908                 }
1909                 path_segs.push(PathSeg(def_id, last));
1910             }
1911
1912             kind => bug!("unexpected definition kind {:?} for {:?}", kind, def_id),
1913         }
1914
1915         debug!("path_segs = {:?}", path_segs);
1916
1917         path_segs
1918     }
1919
1920     // Check a type `Path` and convert it to a `Ty`.
1921     pub fn res_to_ty(&self,
1922                      opt_self_ty: Option<Ty<'tcx>>,
1923                      path: &hir::Path,
1924                      permit_variants: bool)
1925                      -> Ty<'tcx> {
1926         let tcx = self.tcx();
1927
1928         debug!("res_to_ty(res={:?}, opt_self_ty={:?}, path_segments={:?})",
1929                path.res, opt_self_ty, path.segments);
1930
1931         let span = path.span;
1932         match path.res {
1933             Res::Def(DefKind::Existential, did) => {
1934                 // Check for desugared `impl Trait`.
1935                 assert!(ty::is_impl_trait_defn(tcx, did).is_none());
1936                 let item_segment = path.segments.split_last().unwrap();
1937                 self.prohibit_generics(item_segment.1);
1938                 let substs = self.ast_path_substs_for_ty(span, did, item_segment.0);
1939                 self.normalize_ty(
1940                     span,
1941                     tcx.mk_opaque(did, substs),
1942                 )
1943             }
1944             Res::Def(DefKind::Enum, did)
1945             | Res::Def(DefKind::TyAlias, did)
1946             | Res::Def(DefKind::Struct, did)
1947             | Res::Def(DefKind::Union, did)
1948             | Res::Def(DefKind::ForeignTy, did) => {
1949                 assert_eq!(opt_self_ty, None);
1950                 self.prohibit_generics(path.segments.split_last().unwrap().1);
1951                 self.ast_path_to_ty(span, did, path.segments.last().unwrap())
1952             }
1953             Res::Def(kind @ DefKind::Variant, def_id) if permit_variants => {
1954                 // Convert "variant type" as if it were a real type.
1955                 // The resulting `Ty` is type of the variant's enum for now.
1956                 assert_eq!(opt_self_ty, None);
1957
1958                 let path_segs =
1959                     self.def_ids_for_value_path_segments(&path.segments, None, kind, def_id);
1960                 let generic_segs: FxHashSet<_> =
1961                     path_segs.iter().map(|PathSeg(_, index)| index).collect();
1962                 self.prohibit_generics(path.segments.iter().enumerate().filter_map(|(index, seg)| {
1963                     if !generic_segs.contains(&index) {
1964                         Some(seg)
1965                     } else {
1966                         None
1967                     }
1968                 }));
1969
1970                 let PathSeg(def_id, index) = path_segs.last().unwrap();
1971                 self.ast_path_to_ty(span, *def_id, &path.segments[*index])
1972             }
1973             Res::Def(DefKind::TyParam, did) => {
1974                 assert_eq!(opt_self_ty, None);
1975                 self.prohibit_generics(&path.segments);
1976
1977                 let hir_id = tcx.hir().as_local_hir_id(did).unwrap();
1978                 let item_id = tcx.hir().get_parent_node_by_hir_id(hir_id);
1979                 let item_def_id = tcx.hir().local_def_id_from_hir_id(item_id);
1980                 let generics = tcx.generics_of(item_def_id);
1981                 let index = generics.param_def_id_to_index[
1982                     &tcx.hir().local_def_id_from_hir_id(hir_id)];
1983                 tcx.mk_ty_param(index, tcx.hir().name_by_hir_id(hir_id).as_interned_str())
1984             }
1985             Res::SelfTy(Some(_), None) => {
1986                 // `Self` in trait or type alias.
1987                 assert_eq!(opt_self_ty, None);
1988                 self.prohibit_generics(&path.segments);
1989                 tcx.mk_self_type()
1990             }
1991             Res::SelfTy(_, Some(def_id)) => {
1992                 // `Self` in impl (we know the concrete type).
1993                 assert_eq!(opt_self_ty, None);
1994                 self.prohibit_generics(&path.segments);
1995                 // Try to evaluate any array length constants.
1996                 self.normalize_ty(span, tcx.at(span).type_of(def_id))
1997             }
1998             Res::Def(DefKind::AssocTy, def_id) => {
1999                 debug_assert!(path.segments.len() >= 2);
2000                 self.prohibit_generics(&path.segments[..path.segments.len() - 2]);
2001                 self.qpath_to_ty(span,
2002                                  opt_self_ty,
2003                                  def_id,
2004                                  &path.segments[path.segments.len() - 2],
2005                                  path.segments.last().unwrap())
2006             }
2007             Res::PrimTy(prim_ty) => {
2008                 assert_eq!(opt_self_ty, None);
2009                 self.prohibit_generics(&path.segments);
2010                 match prim_ty {
2011                     hir::Bool => tcx.types.bool,
2012                     hir::Char => tcx.types.char,
2013                     hir::Int(it) => tcx.mk_mach_int(it),
2014                     hir::Uint(uit) => tcx.mk_mach_uint(uit),
2015                     hir::Float(ft) => tcx.mk_mach_float(ft),
2016                     hir::Str => tcx.mk_str()
2017                 }
2018             }
2019             Res::Err => {
2020                 self.set_tainted_by_errors();
2021                 return self.tcx().types.err;
2022             }
2023             _ => span_bug!(span, "unexpected resolution: {:?}", path.res)
2024         }
2025     }
2026
2027     /// Parses the programmer's textual representation of a type into our
2028     /// internal notion of a type.
2029     pub fn ast_ty_to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
2030         debug!("ast_ty_to_ty(id={:?}, ast_ty={:?} ty_ty={:?})",
2031                ast_ty.hir_id, ast_ty, ast_ty.node);
2032
2033         let tcx = self.tcx();
2034
2035         let result_ty = match ast_ty.node {
2036             hir::TyKind::Slice(ref ty) => {
2037                 tcx.mk_slice(self.ast_ty_to_ty(&ty))
2038             }
2039             hir::TyKind::Ptr(ref mt) => {
2040                 tcx.mk_ptr(ty::TypeAndMut {
2041                     ty: self.ast_ty_to_ty(&mt.ty),
2042                     mutbl: mt.mutbl
2043                 })
2044             }
2045             hir::TyKind::Rptr(ref region, ref mt) => {
2046                 let r = self.ast_region_to_region(region, None);
2047                 debug!("ast_ty_to_ty: r={:?}", r);
2048                 let t = self.ast_ty_to_ty(&mt.ty);
2049                 tcx.mk_ref(r, ty::TypeAndMut {ty: t, mutbl: mt.mutbl})
2050             }
2051             hir::TyKind::Never => {
2052                 tcx.types.never
2053             },
2054             hir::TyKind::Tup(ref fields) => {
2055                 tcx.mk_tup(fields.iter().map(|t| self.ast_ty_to_ty(&t)))
2056             }
2057             hir::TyKind::BareFn(ref bf) => {
2058                 require_c_abi_if_c_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
2059                 tcx.mk_fn_ptr(self.ty_of_fn(bf.unsafety, bf.abi, &bf.decl))
2060             }
2061             hir::TyKind::TraitObject(ref bounds, ref lifetime) => {
2062                 self.conv_object_ty_poly_trait_ref(ast_ty.span, bounds, lifetime)
2063             }
2064             hir::TyKind::Path(hir::QPath::Resolved(ref maybe_qself, ref path)) => {
2065                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
2066                 let opt_self_ty = maybe_qself.as_ref().map(|qself| {
2067                     self.ast_ty_to_ty(qself)
2068                 });
2069                 self.res_to_ty(opt_self_ty, path, false)
2070             }
2071             hir::TyKind::Def(item_id, ref lifetimes) => {
2072                 let did = tcx.hir().local_def_id_from_hir_id(item_id.id);
2073                 self.impl_trait_ty_to_ty(did, lifetimes)
2074             }
2075             hir::TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2076                 debug!("ast_ty_to_ty: qself={:?} segment={:?}", qself, segment);
2077                 let ty = self.ast_ty_to_ty(qself);
2078
2079                 let res = if let hir::TyKind::Path(hir::QPath::Resolved(_, ref path)) = qself.node {
2080                     path.res
2081                 } else {
2082                     Res::Err
2083                 };
2084                 self.associated_path_to_ty(ast_ty.hir_id, ast_ty.span, ty, res, segment, false)
2085                     .map(|(ty, _, _)| ty).unwrap_or(tcx.types.err)
2086             }
2087             hir::TyKind::Array(ref ty, ref length) => {
2088                 let length = self.ast_const_to_const(length, tcx.types.usize);
2089                 let array_ty = tcx.mk_ty(ty::Array(self.ast_ty_to_ty(&ty), length));
2090                 self.normalize_ty(ast_ty.span, array_ty)
2091             }
2092             hir::TyKind::Typeof(ref _e) => {
2093                 struct_span_err!(tcx.sess, ast_ty.span, E0516,
2094                                  "`typeof` is a reserved keyword but unimplemented")
2095                     .span_label(ast_ty.span, "reserved keyword")
2096                     .emit();
2097
2098                 tcx.types.err
2099             }
2100             hir::TyKind::Infer => {
2101                 // Infer also appears as the type of arguments or return
2102                 // values in a ExprKind::Closure, or as
2103                 // the type of local variables. Both of these cases are
2104                 // handled specially and will not descend into this routine.
2105                 self.ty_infer(ast_ty.span)
2106             }
2107             hir::TyKind::CVarArgs(lt) => {
2108                 let va_list_did = match tcx.lang_items().va_list() {
2109                     Some(did) => did,
2110                     None => span_bug!(ast_ty.span,
2111                                       "`va_list` lang item required for variadics"),
2112                 };
2113                 let region = self.ast_region_to_region(&lt, None);
2114                 tcx.type_of(va_list_did).subst(tcx, &[region.into()])
2115             }
2116             hir::TyKind::Err => {
2117                 tcx.types.err
2118             }
2119         };
2120
2121         debug!("ast_ty_to_ty: result_ty={:?}", result_ty);
2122
2123         self.record_ty(ast_ty.hir_id, result_ty, ast_ty.span);
2124         result_ty
2125     }
2126
2127     pub fn ast_const_to_const(
2128         &self,
2129         ast_const: &hir::AnonConst,
2130         ty: Ty<'tcx>
2131     ) -> &'tcx ty::Const<'tcx> {
2132         debug!("ast_const_to_const(id={:?}, ast_const={:?})", ast_const.hir_id, ast_const);
2133
2134         let tcx = self.tcx();
2135         let def_id = tcx.hir().local_def_id_from_hir_id(ast_const.hir_id);
2136
2137         let mut const_ = ty::Const {
2138             val: ConstValue::Unevaluated(
2139                 def_id,
2140                 InternalSubsts::identity_for_item(tcx, def_id),
2141             ),
2142             ty,
2143         };
2144
2145         let mut expr = &tcx.hir().body(ast_const.body).value;
2146
2147         // Unwrap a block, so that e.g. `{ P }` is recognised as a parameter. Const arguments
2148         // currently have to be wrapped in curly brackets, so it's necessary to special-case.
2149         if let ExprKind::Block(block, _) = &expr.node {
2150             if block.stmts.is_empty() {
2151                 if let Some(trailing) = &block.expr {
2152                     expr = &trailing;
2153                 }
2154             }
2155         }
2156
2157         if let ExprKind::Path(ref qpath) = expr.node {
2158             if let hir::QPath::Resolved(_, ref path) = qpath {
2159                 if let Res::Def(DefKind::ConstParam, def_id) = path.res {
2160                     let node_id = tcx.hir().as_local_node_id(def_id).unwrap();
2161                     let item_id = tcx.hir().get_parent_node(node_id);
2162                     let item_def_id = tcx.hir().local_def_id(item_id);
2163                     let generics = tcx.generics_of(item_def_id);
2164                     let index = generics.param_def_id_to_index[&tcx.hir().local_def_id(node_id)];
2165                     let name = tcx.hir().name(node_id).as_interned_str();
2166                     const_.val = ConstValue::Param(ty::ParamConst::new(index, name));
2167                 }
2168             }
2169         };
2170
2171         tcx.mk_const(const_)
2172     }
2173
2174     pub fn impl_trait_ty_to_ty(
2175         &self,
2176         def_id: DefId,
2177         lifetimes: &[hir::GenericArg],
2178     ) -> Ty<'tcx> {
2179         debug!("impl_trait_ty_to_ty(def_id={:?}, lifetimes={:?})", def_id, lifetimes);
2180         let tcx = self.tcx();
2181
2182         let generics = tcx.generics_of(def_id);
2183
2184         debug!("impl_trait_ty_to_ty: generics={:?}", generics);
2185         let substs = InternalSubsts::for_item(tcx, def_id, |param, _| {
2186             if let Some(i) = (param.index as usize).checked_sub(generics.parent_count) {
2187                 // Our own parameters are the resolved lifetimes.
2188                 match param.kind {
2189                     GenericParamDefKind::Lifetime => {
2190                         if let hir::GenericArg::Lifetime(lifetime) = &lifetimes[i] {
2191                             self.ast_region_to_region(lifetime, None).into()
2192                         } else {
2193                             bug!()
2194                         }
2195                     }
2196                     _ => bug!()
2197                 }
2198             } else {
2199                 // Replace all parent lifetimes with `'static`.
2200                 match param.kind {
2201                     GenericParamDefKind::Lifetime => {
2202                         tcx.lifetimes.re_static.into()
2203                     }
2204                     _ => tcx.mk_param_from_def(param)
2205                 }
2206             }
2207         });
2208         debug!("impl_trait_ty_to_ty: substs={:?}", substs);
2209
2210         let ty = tcx.mk_opaque(def_id, substs);
2211         debug!("impl_trait_ty_to_ty: {}", ty);
2212         ty
2213     }
2214
2215     pub fn ty_of_arg(&self,
2216                      ty: &hir::Ty,
2217                      expected_ty: Option<Ty<'tcx>>)
2218                      -> Ty<'tcx>
2219     {
2220         match ty.node {
2221             hir::TyKind::Infer if expected_ty.is_some() => {
2222                 self.record_ty(ty.hir_id, expected_ty.unwrap(), ty.span);
2223                 expected_ty.unwrap()
2224             }
2225             _ => self.ast_ty_to_ty(ty),
2226         }
2227     }
2228
2229     pub fn ty_of_fn(&self,
2230                     unsafety: hir::Unsafety,
2231                     abi: abi::Abi,
2232                     decl: &hir::FnDecl)
2233                     -> ty::PolyFnSig<'tcx> {
2234         debug!("ty_of_fn");
2235
2236         let tcx = self.tcx();
2237         let input_tys =
2238             decl.inputs.iter().map(|a| self.ty_of_arg(a, None));
2239
2240         let output_ty = match decl.output {
2241             hir::Return(ref output) => self.ast_ty_to_ty(output),
2242             hir::DefaultReturn(..) => tcx.mk_unit(),
2243         };
2244
2245         debug!("ty_of_fn: output_ty={:?}", output_ty);
2246
2247         let bare_fn_ty = ty::Binder::bind(tcx.mk_fn_sig(
2248             input_tys,
2249             output_ty,
2250             decl.c_variadic,
2251             unsafety,
2252             abi
2253         ));
2254
2255         // Find any late-bound regions declared in return type that do
2256         // not appear in the arguments. These are not well-formed.
2257         //
2258         // Example:
2259         //     for<'a> fn() -> &'a str <-- 'a is bad
2260         //     for<'a> fn(&'a String) -> &'a str <-- 'a is ok
2261         let inputs = bare_fn_ty.inputs();
2262         let late_bound_in_args = tcx.collect_constrained_late_bound_regions(
2263             &inputs.map_bound(|i| i.to_owned()));
2264         let output = bare_fn_ty.output();
2265         let late_bound_in_ret = tcx.collect_referenced_late_bound_regions(&output);
2266         for br in late_bound_in_ret.difference(&late_bound_in_args) {
2267             let lifetime_name = match *br {
2268                 ty::BrNamed(_, name) => format!("lifetime `{}`,", name),
2269                 ty::BrAnon(_) | ty::BrEnv => "an anonymous lifetime".to_string(),
2270             };
2271             let mut err = struct_span_err!(tcx.sess,
2272                                            decl.output.span(),
2273                                            E0581,
2274                                            "return type references {} \
2275                                             which is not constrained by the fn input types",
2276                                            lifetime_name);
2277             if let ty::BrAnon(_) = *br {
2278                 // The only way for an anonymous lifetime to wind up
2279                 // in the return type but **also** be unconstrained is
2280                 // if it only appears in "associated types" in the
2281                 // input. See #47511 for an example. In this case,
2282                 // though we can easily give a hint that ought to be
2283                 // relevant.
2284                 err.note("lifetimes appearing in an associated type \
2285                           are not considered constrained");
2286             }
2287             err.emit();
2288         }
2289
2290         bare_fn_ty
2291     }
2292
2293     /// Given the bounds on an object, determines what single region bound (if any) we can
2294     /// use to summarize this type. The basic idea is that we will use the bound the user
2295     /// provided, if they provided one, and otherwise search the supertypes of trait bounds
2296     /// for region bounds. It may be that we can derive no bound at all, in which case
2297     /// we return `None`.
2298     fn compute_object_lifetime_bound(&self,
2299         span: Span,
2300         existential_predicates: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>)
2301         -> Option<ty::Region<'tcx>> // if None, use the default
2302     {
2303         let tcx = self.tcx();
2304
2305         debug!("compute_opt_region_bound(existential_predicates={:?})",
2306                existential_predicates);
2307
2308         // No explicit region bound specified. Therefore, examine trait
2309         // bounds and see if we can derive region bounds from those.
2310         let derived_region_bounds =
2311             object_region_bounds(tcx, existential_predicates);
2312
2313         // If there are no derived region bounds, then report back that we
2314         // can find no region bound. The caller will use the default.
2315         if derived_region_bounds.is_empty() {
2316             return None;
2317         }
2318
2319         // If any of the derived region bounds are 'static, that is always
2320         // the best choice.
2321         if derived_region_bounds.iter().any(|&r| ty::ReStatic == *r) {
2322             return Some(tcx.lifetimes.re_static);
2323         }
2324
2325         // Determine whether there is exactly one unique region in the set
2326         // of derived region bounds. If so, use that. Otherwise, report an
2327         // error.
2328         let r = derived_region_bounds[0];
2329         if derived_region_bounds[1..].iter().any(|r1| r != *r1) {
2330             span_err!(tcx.sess, span, E0227,
2331                       "ambiguous lifetime bound, explicit lifetime bound required");
2332         }
2333         return Some(r);
2334     }
2335 }
2336
2337 /// Collects together a list of bounds that are applied to some type,
2338 /// after they've been converted into `ty` form (from the HIR
2339 /// representations). These lists of bounds occur in many places in
2340 /// Rust's syntax:
2341 ///
2342 /// ```
2343 /// trait Foo: Bar + Baz { }
2344 ///            ^^^^^^^^^ supertrait list bounding the `Self` type parameter
2345 ///
2346 /// fn foo<T: Bar + Baz>() { }
2347 ///           ^^^^^^^^^ bounding the type parameter `T`
2348 ///
2349 /// impl dyn Bar + Baz
2350 ///          ^^^^^^^^^ bounding the forgotten dynamic type
2351 /// ```
2352 ///
2353 /// Our representation is a bit mixed here -- in some cases, we
2354 /// include the self type (e.g., `trait_bounds`) but in others we do
2355 #[derive(Default, PartialEq, Eq, Clone, Debug)]
2356 pub struct Bounds<'tcx> {
2357     /// A list of region bounds on the (implicit) self type. So if you
2358     /// had `T: 'a + 'b` this might would be a list `['a, 'b]` (but
2359     /// the `T` is not explicitly included).
2360     pub region_bounds: Vec<(ty::Region<'tcx>, Span)>,
2361
2362     /// A list of trait bounds. So if you had `T: Debug` this would be
2363     /// `T: Debug`. Note that the self-type is explicit here.
2364     pub trait_bounds: Vec<(ty::PolyTraitRef<'tcx>, Span)>,
2365
2366     /// A list of projection equality bounds. So if you had `T:
2367     /// Iterator<Item = u32>` this would include `<T as
2368     /// Iterator>::Item => u32`. Note that the self-type is explicit
2369     /// here.
2370     pub projection_bounds: Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>,
2371
2372     /// `Some` if there is *no* `?Sized` predicate. The `span`
2373     /// is the location in the source of the `T` declaration which can
2374     /// be cited as the source of the `T: Sized` requirement.
2375     pub implicitly_sized: Option<Span>,
2376 }
2377
2378 impl<'a, 'gcx, 'tcx> Bounds<'tcx> {
2379     /// Converts a bounds list into a flat set of predicates (like
2380     /// where-clauses). Because some of our bounds listings (e.g.,
2381     /// regions) don't include the self-type, you must supply the
2382     /// self-type here (the `param_ty` parameter).
2383     pub fn predicates(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, param_ty: Ty<'tcx>)
2384                       -> Vec<(ty::Predicate<'tcx>, Span)>
2385     {
2386         // If it could be sized, and is, add the `Sized` predicate.
2387         let sized_predicate = self.implicitly_sized.and_then(|span| {
2388             tcx.lang_items().sized_trait().map(|sized| {
2389                 let trait_ref = ty::TraitRef {
2390                     def_id: sized,
2391                     substs: tcx.mk_substs_trait(param_ty, &[])
2392                 };
2393                 (trait_ref.to_predicate(), span)
2394             })
2395         });
2396
2397         sized_predicate.into_iter().chain(
2398             self.region_bounds.iter().map(|&(region_bound, span)| {
2399                 // Account for the binder being introduced below; no need to shift `param_ty`
2400                 // because, at present at least, it can only refer to early-bound regions.
2401                 let region_bound = ty::fold::shift_region(tcx, region_bound, 1);
2402                 let outlives = ty::OutlivesPredicate(param_ty, region_bound);
2403                 (ty::Binder::dummy(outlives).to_predicate(), span)
2404             }).chain(
2405                 self.trait_bounds.iter().map(|&(bound_trait_ref, span)| {
2406                     (bound_trait_ref.to_predicate(), span)
2407                 })
2408             ).chain(
2409                 self.projection_bounds.iter().map(|&(projection, span)| {
2410                     (projection.to_predicate(), span)
2411                 })
2412             )
2413         ).collect()
2414     }
2415 }