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     ///
 575     /// Note that the type listing given here is *exactly* what the user provided.
 576     fn create_substs_for_ast_path<'a>(&self,
 577         span: Span,
 578         def_id: DefId,
 579         generic_args: &'a hir::GenericArgs,
 580         infer_types: bool,
 581         self_ty: Option<Ty<'tcx>>)
 582         -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'tcx>>, Option<Vec<Span>>)
 583     {
 584         // If the type is parameterized by this region, then replace this
 585         // region with the current anon region binding (in other words,
 586         // whatever & would get replaced with).
 587         debug!("create_substs_for_ast_path(def_id={:?}, self_ty={:?}, \
 588                 generic_args={:?})",
 589                def_id, self_ty, generic_args);
 590
 591         let tcx = self.tcx();
 592         let generic_params = tcx.generics_of(def_id);
 593
 594         // If a self-type was declared, one should be provided.
 595         assert_eq!(generic_params.has_self, self_ty.is_some());
 596
 597         let has_self = generic_params.has_self;
 598         let (_, potential_assoc_types) = Self::check_generic_arg_count(
 599             tcx,
 600             span,
 601             &generic_params,
 602             &generic_args,
 603             GenericArgPosition::Type,
 604             has_self,
 605             infer_types,
 606         );
 607
 608         let is_object = self_ty.map_or(false, |ty| {
 609             ty == self.tcx().types.trait_object_dummy_self
 610         });
 611         let default_needs_object_self = |param: &ty::GenericParamDef| {
 612             if let GenericParamDefKind::Type { has_default, .. } = param.kind {
 613                 if is_object && has_default {
 614                     if tcx.at(span).type_of(param.def_id).has_self_ty() {
 615                         // There is no suitable inference default for a type parameter
 616                         // that references self, in an object type.
 617                         return true;
 618                     }
 619                 }
 620             }
 621
 622             false
 623         };
 624
 625         let substs = Self::create_substs_for_generic_args(
 626             tcx,
 627             def_id,
 628             &[][..],
 629             self_ty.is_some(),
 630             self_ty,
 631             // Provide the generic args, and whether types should be inferred.
 632             |_| (Some(generic_args), infer_types),
 633             // Provide substitutions for parameters for which (valid) arguments have been provided.
 634             |param, arg| {
 635                 match (&param.kind, arg) {
 636                     (GenericParamDefKind::Lifetime, GenericArg::Lifetime(lt)) => {
 637                         self.ast_region_to_region(&lt, Some(param)).into()
 638                     }
 639                     (GenericParamDefKind::Type { .. }, GenericArg::Type(ty)) => {
 640                         self.ast_ty_to_ty(&ty).into()
 641                     }
 642                     (GenericParamDefKind::Const, GenericArg::Const(ct)) => {
 643                         self.ast_const_to_const(&ct.value, tcx.type_of(param.def_id)).into()
 644                     }
 645                     _ => unreachable!(),
 646                 }
 647             },
 648             // Provide substitutions for parameters for which arguments are inferred.
 649             |substs, param, infer_types| {
 650                 match param.kind {
 651                     GenericParamDefKind::Lifetime => tcx.lifetimes.re_static.into(),
 652                     GenericParamDefKind::Type { has_default, .. } => {
 653                         if !infer_types && has_default {
 654                             // No type parameter provided, but a default exists.
 655
 656                             // If we are converting an object type, then the
 657                             // `Self` parameter is unknown. However, some of the
 658                             // other type parameters may reference `Self` in their
 659                             // defaults. This will lead to an ICE if we are not
 660                             // careful!
 661                             if default_needs_object_self(param) {
 662                                 struct_span_err!(tcx.sess, span, E0393,
 663                                     "the type parameter `{}` must be explicitly specified",
 664                                     param.name
 665                                 )
 666                                     .span_label(span, format!(
 667                                         "missing reference to `{}`", param.name))
 668                                     .note(&format!(
 669                                         "because of the default `Self` reference, type parameters \
 670                                          must be specified on object types"))
 671                                     .emit();
 672                                 tcx.types.err.into()
 673                             } else {
 674                                 // This is a default type parameter.
 675                                 self.normalize_ty(
 676                                     span,
 677                                     tcx.at(span).type_of(param.def_id)
 678                                        .subst_spanned(tcx, substs.unwrap(), Some(span))
 679                                 ).into()
 680                             }
 681                         } else if infer_types {
 682                             // No type parameters were provided, we can infer all.
 683                             if !default_needs_object_self(param) {
 684                                 self.ty_infer_for_def(param, span).into()
 685                             } else {
 686                                 self.ty_infer(span).into()
 687                             }
 688                         } else {
 689                             // We've already errored above about the mismatch.
 690                             tcx.types.err.into()
 691                         }
 692                     }
 693                     GenericParamDefKind::Const => {
 694                         // FIXME(const_generics:defaults)
 695                         // We've already errored above about the mismatch.
 696                         tcx.consts.err.into()
 697                     }
 698                 }
 699             },
 700         );
 701
 702         // Convert associated-type bindings or constraints into a separate vector.
 703         // Example: Given this:
 704         //
 705         //     T: Iterator<Item = u32>
 706         //
 707         // The `T` is passed in as a self-type; the `Item = u32` is
 708         // not a "type parameter" of the `Iterator` trait, but rather
 709         // a restriction on `<T as Iterator>::Item`, so it is passed
 710         // back separately.
 711         let assoc_bindings = generic_args.bindings.iter()
 712             .map(|binding| {
 713                 let kind = if let hir::TyKind::AssocTyExistential(ref bounds) = binding.ty.node {
 714                     ConvertedBindingKind::Constraint(bounds.clone())
 715                 } else {
 716                     ConvertedBindingKind::Equality(self.ast_ty_to_ty(&binding.ty))
 717                 };
 718                 ConvertedBinding {
 719                     item_name: binding.ident,
 720                     kind,
 721                     span: binding.span,
 722                 }
 723             })
 724             .collect();
 725
 726         debug!("create_substs_for_ast_path(generic_params={:?}, self_ty={:?}) -> {:?}",
 727                generic_params, self_ty, substs);
 728
 729         (substs, assoc_bindings, potential_assoc_types)
 730     }
 731
 732     /// Instantiates the path for the given trait reference, assuming that it's
 733     /// bound to a valid trait type. Returns the `DefId` of the defining trait.
 734     /// The type _cannot_ be a type other than a trait type.
 735     ///
 736     /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T = X>`
 737     /// are disallowed. Otherwise, they are pushed onto the vector given.
 738     pub fn instantiate_mono_trait_ref(&self,
 739         trait_ref: &hir::TraitRef,
 740         self_ty: Ty<'tcx>
 741     ) -> ty::TraitRef<'tcx>
 742     {
 743         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 744
 745         self.ast_path_to_mono_trait_ref(trait_ref.path.span,
 746                                         trait_ref.trait_def_id(),
 747                                         self_ty,
 748                                         trait_ref.path.segments.last().unwrap())
 749     }
 750
 751     /// The given trait-ref must actually be a trait.
 752     pub(super) fn instantiate_poly_trait_ref_inner(&self,
 753         trait_ref: &hir::TraitRef,
 754         self_ty: Ty<'tcx>,
 755         bounds: &mut Bounds<'tcx>,
 756         speculative: bool,
 757     ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
 758     {
 759         let trait_def_id = trait_ref.trait_def_id();
 760
 761         debug!("instantiate_poly_trait_ref({:?}, def_id={:?})", trait_ref, trait_def_id);
 762
 763         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 764
 765         let (substs, assoc_bindings, potential_assoc_types) = self.create_substs_for_ast_trait_ref(
 766             trait_ref.path.span,
 767             trait_def_id,
 768             self_ty,
 769             trait_ref.path.segments.last().unwrap(),
 770         );
 771         let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs));
 772
 773         let mut dup_bindings = FxHashMap::default();
 774         for binding in &assoc_bindings {
 775             // Specify type to assert that error was already reported in `Err` case.
 776             let _: Result<_, ErrorReported> =
 777                 self.add_predicates_for_ast_type_binding(
 778                     trait_ref.hir_ref_id,
 779                     poly_trait_ref,
 780                     binding,
 781                     bounds,
 782                     speculative,
 783                     &mut dup_bindings
 784                 );
 785             // Okay to ignore `Err` because of `ErrorReported` (see above).
 786         }
 787
 788         debug!("instantiate_poly_trait_ref({:?}, bounds={:?}) -> {:?}",
 789                trait_ref, bounds, poly_trait_ref);
 790         (poly_trait_ref, potential_assoc_types)
 791     }
 792
 793     pub fn instantiate_poly_trait_ref(&self,
 794         poly_trait_ref: &hir::PolyTraitRef,
 795         self_ty: Ty<'tcx>,
 796         bounds: &mut Bounds<'tcx>
 797     ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
 798     {
 799         self.instantiate_poly_trait_ref_inner(&poly_trait_ref.trait_ref, self_ty, bounds, false)
 800     }
 801
 802     fn ast_path_to_mono_trait_ref(&self,
 803         span: Span,
 804         trait_def_id: DefId,
 805         self_ty: Ty<'tcx>,
 806         trait_segment: &hir::PathSegment
 807     ) -> ty::TraitRef<'tcx>
 808     {
 809         let (substs, assoc_bindings, _) =
 810             self.create_substs_for_ast_trait_ref(span,
 811                                                  trait_def_id,
 812                                                  self_ty,
 813                                                  trait_segment);
 814         assoc_bindings.first().map(|b| AstConv::prohibit_assoc_ty_binding(self.tcx(), b.span));
 815         ty::TraitRef::new(trait_def_id, substs)
 816     }
 817
 818     fn create_substs_for_ast_trait_ref(
 819         &self,
 820         span: Span,
 821         trait_def_id: DefId,
 822         self_ty: Ty<'tcx>,
 823         trait_segment: &hir::PathSegment,
 824     ) -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'tcx>>, Option<Vec<Span>>) {
 825         debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
 826                trait_segment);
 827
 828         let trait_def = self.tcx().trait_def(trait_def_id);
 829
 830         if !self.tcx().features().unboxed_closures &&
 831             trait_segment.with_generic_args(|generic_args| generic_args.parenthesized)
 832             != trait_def.paren_sugar {
 833             // For now, require that parenthetical notation be used only with `Fn()` etc.
 834             let msg = if trait_def.paren_sugar {
 835                 "the precise format of `Fn`-family traits' type parameters is subject to change. \
 836                  Use parenthetical notation (Fn(Foo, Bar) -> Baz) instead"
 837             } else {
 838                 "parenthetical notation is only stable when used with `Fn`-family traits"
 839             };
 840             emit_feature_err(&self.tcx().sess.parse_sess, sym::unboxed_closures,
 841                              span, GateIssue::Language, msg);
 842         }
 843
 844         trait_segment.with_generic_args(|generic_args| {
 845             self.create_substs_for_ast_path(span,
 846                                             trait_def_id,
 847                                             generic_args,
 848                                             trait_segment.infer_types,
 849                                             Some(self_ty))
 850         })
 851     }
 852
 853     fn trait_defines_associated_type_named(&self,
 854                                            trait_def_id: DefId,
 855                                            assoc_name: ast::Ident)
 856                                            -> bool
 857     {
 858         self.tcx().associated_items(trait_def_id).any(|item| {
 859             item.kind == ty::AssocKind::Type &&
 860             self.tcx().hygienic_eq(assoc_name, item.ident, trait_def_id)
 861         })
 862     }
 863
 864     // Returns `true` if a bounds list includes `?Sized`.
 865     pub fn is_unsized(&self, ast_bounds: &[hir::GenericBound], span: Span) -> bool {
 866         let tcx = self.tcx();
 867
 868         // Try to find an unbound in bounds.
 869         let mut unbound = None;
 870         for ab in ast_bounds {
 871             if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab {
 872                 if unbound.is_none() {
 873                     unbound = Some(ptr.trait_ref.clone());
 874                 } else {
 875                     span_err!(
 876                         tcx.sess,
 877                         span,
 878                         E0203,
 879                         "type parameter has more than one relaxed default \
 880                         bound, only one is supported"
 881                     );
 882                 }
 883             }
 884         }
 885
 886         let kind_id = tcx.lang_items().require(SizedTraitLangItem);
 887         match unbound {
 888             Some(ref tpb) => {
 889                 // FIXME(#8559) currently requires the unbound to be built-in.
 890                 if let Ok(kind_id) = kind_id {
 891                     if tpb.path.res != Res::Def(DefKind::Trait, kind_id) {
 892                         tcx.sess.span_warn(
 893                             span,
 894                             "default bound relaxed for a type parameter, but \
 895                             this does nothing because the given bound is not \
 896                             a default. Only `?Sized` is supported",
 897                         );
 898                     }
 899                 }
 900             }
 901             _ if kind_id.is_ok() => {
 902                 return false;
 903             }
 904             // No lang item for `Sized`, so we can't add it as a bound.
 905             None => {}
 906         }
 907
 908         true
 909     }
 910
 911     fn add_bounds(&self,
 912         param_ty: Ty<'tcx>,
 913         ast_bounds: &[hir::GenericBound],
 914         bounds: &mut Bounds<'tcx>,
 915     ) {
 916         let mut trait_bounds = Vec::new();
 917         let mut region_bounds = Vec::new();
 918
 919         for ast_bound in ast_bounds {
 920             match *ast_bound {
 921                 hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) =>
 922                     trait_bounds.push(b),
 923                 hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
 924                 hir::GenericBound::Outlives(ref l) =>
 925                     region_bounds.push(l),
 926             }
 927         }
 928
 929         for bound in trait_bounds {
 930             let (poly_trait_ref, _) = self.instantiate_poly_trait_ref(
 931                 bound,
 932                 param_ty,
 933                 bounds,
 934             );
 935             bounds.trait_bounds.push((poly_trait_ref, bound.span))
 936         }
 937
 938         bounds.region_bounds.extend(region_bounds
 939             .into_iter()
 940             .map(|r| (self.ast_region_to_region(r, None), r.span))
 941         );
 942     }
 943
 944     /// Translates the AST's notion of ty param bounds (which are an enum consisting of a newtyped
 945     /// `Ty` or a region) to ty's notion of ty param bounds (which can either be user-defined traits
 946     /// or the built-in trait `Sized`).
 947     pub fn compute_bounds(&self,
 948         param_ty: Ty<'tcx>,
 949         ast_bounds: &[hir::GenericBound],
 950         sized_by_default: SizedByDefault,
 951         span: Span,
 952     ) -> Bounds<'tcx> {
 953         let mut bounds = Bounds::default();
 954
 955         self.add_bounds(param_ty, ast_bounds, &mut bounds);
 956         bounds.trait_bounds.sort_by_key(|(t, _)| t.def_id());
 957
 958         bounds.implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
 959             if !self.is_unsized(ast_bounds, span) {
 960                 Some(span)
 961             } else {
 962                 None
 963             }
 964         } else {
 965             None
 966         };
 967
 968         bounds
 969     }
 970
 971     fn add_predicates_for_ast_type_binding(
 972         &self,
 973         hir_ref_id: hir::HirId,
 974         trait_ref: ty::PolyTraitRef<'tcx>,
 975         binding: &ConvertedBinding<'tcx>,
 976         bounds: &mut Bounds<'tcx>,
 977         speculative: bool,
 978         dup_bindings: &mut FxHashMap<DefId, Span>,
 979     ) -> Result<(), ErrorReported> {
 980         let tcx = self.tcx();
 981
 982         if !speculative {
 983             // Given something like `U: SomeTrait<T = X>`, we want to produce a
 984             // predicate like `<U as SomeTrait>::T = X`. This is somewhat
 985             // subtle in the event that `T` is defined in a supertrait of
 986             // `SomeTrait`, because in that case we need to upcast.
 987             //
 988             // That is, consider this case:
 989             //
 990             // ```
 991             // trait SubTrait: SuperTrait<int> { }
 992             // trait SuperTrait<A> { type T; }
 993             //
 994             // ... B: SubTrait<T = foo> ...
 995             // ```
 996             //
 997             // We want to produce `<B as SuperTrait<int>>::T == foo`.
 998
 999             // Find any late-bound regions declared in `ty` that are not
1000             // declared in the trait-ref. These are not well-formed.
1001             //
1002             // Example:
1003             //
1004             //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
1005             //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
1006             if let ConvertedBindingKind::Equality(ty) = binding.kind {
1007                 let late_bound_in_trait_ref =
1008                     tcx.collect_constrained_late_bound_regions(&trait_ref);
1009                 let late_bound_in_ty =
1010                     tcx.collect_referenced_late_bound_regions(&ty::Binder::bind(ty));
1011                 debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
1012                 debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
1013                 for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
1014                     let br_name = match *br {
1015                         ty::BrNamed(_, name) => name,
1016                         _ => {
1017                             span_bug!(
1018                                 binding.span,
1019                                 "anonymous bound region {:?} in binding but not trait ref",
1020                                 br);
1021                         }
1022                     };
1023                     struct_span_err!(tcx.sess,
1024                                     binding.span,
1025                                     E0582,
1026                                     "binding for associated type `{}` references lifetime `{}`, \
1027                                      which does not appear in the trait input types",
1028                                     binding.item_name, br_name)
1029                         .emit();
1030                 }
1031             }
1032         }
1033
1034         let candidate = if self.trait_defines_associated_type_named(trait_ref.def_id(),
1035                                                                     binding.item_name) {
1036             // Simple case: X is defined in the current trait.
1037             Ok(trait_ref)
1038         } else {
1039             // Otherwise, we have to walk through the supertraits to find
1040             // those that do.
1041             let candidates = traits::supertraits(tcx, trait_ref).filter(|r| {
1042                 self.trait_defines_associated_type_named(r.def_id(), binding.item_name)
1043             });
1044             self.one_bound_for_assoc_type(candidates, &trait_ref.to_string(),
1045                                           binding.item_name, binding.span)
1046         }?;
1047
1048         let (assoc_ident, def_scope) =
1049             tcx.adjust_ident_and_get_scope(binding.item_name, candidate.def_id(), hir_ref_id);
1050         let assoc_ty = tcx.associated_items(candidate.def_id()).find(|i| {
1051             i.kind == ty::AssocKind::Type && i.ident.modern() == assoc_ident
1052         }).expect("missing associated type");
1053
1054         if !assoc_ty.vis.is_accessible_from(def_scope, tcx) {
1055             let msg = format!("associated type `{}` is private", binding.item_name);
1056             tcx.sess.span_err(binding.span, &msg);
1057         }
1058         tcx.check_stability(assoc_ty.def_id, Some(hir_ref_id), binding.span);
1059
1060         if !speculative {
1061             dup_bindings.entry(assoc_ty.def_id)
1062                 .and_modify(|prev_span| {
1063                     struct_span_err!(self.tcx().sess, binding.span, E0719,
1064                                      "the value of the associated type `{}` (from the trait `{}`) \
1065                                       is already specified",
1066                                      binding.item_name,
1067                                      tcx.def_path_str(assoc_ty.container.id()))
1068                         .span_label(binding.span, "re-bound here")
1069                         .span_label(*prev_span, format!("`{}` bound here first", binding.item_name))
1070                         .emit();
1071                 })
1072                 .or_insert(binding.span);
1073         }
1074
1075         match binding.kind {
1076             ConvertedBindingKind::Equality(ref ty) => {
1077                 // "Desugar" a constraint like `T: Iterator<Item = u32>` this to
1078                 // the "projection predicate" for:
1079                 //
1080                 // `<T as Iterator>::Item = u32`
1081                 bounds.projection_bounds.push((candidate.map_bound(|trait_ref| {
1082                     ty::ProjectionPredicate {
1083                         projection_ty: ty::ProjectionTy::from_ref_and_name(
1084                             tcx,
1085                             trait_ref,
1086                             binding.item_name,
1087                         ),
1088                         ty,
1089                     }
1090                 }), binding.span));
1091             }
1092             ConvertedBindingKind::Constraint(ref ast_bounds) => {
1093                 // Calling `skip_binder` is okay, because the predicates are re-bound later by
1094                 // `instantiate_poly_trait_ref`.
1095                 let param_ty = tcx.mk_projection(assoc_ty.def_id, candidate.skip_binder().substs);
1096                 self.add_bounds(
1097                     param_ty,
1098                     ast_bounds,
1099                     bounds,
1100                 );
1101             }
1102         }
1103         Ok(())
1104     }
1105
1106     fn ast_path_to_ty(&self,
1107         span: Span,
1108         did: DefId,
1109         item_segment: &hir::PathSegment)
1110         -> Ty<'tcx>
1111     {
1112         let substs = self.ast_path_substs_for_ty(span, did, item_segment);
1113         self.normalize_ty(
1114             span,
1115             self.tcx().at(span).type_of(did).subst(self.tcx(), substs)
1116         )
1117     }
1118
1119     /// Transform a `PolyTraitRef` into a `PolyExistentialTraitRef` by
1120     /// removing the dummy `Self` type (`trait_object_dummy_self`).
1121     fn trait_ref_to_existential(&self, trait_ref: ty::TraitRef<'tcx>)
1122                                 -> ty::ExistentialTraitRef<'tcx> {
1123         if trait_ref.self_ty() != self.tcx().types.trait_object_dummy_self {
1124             bug!("trait_ref_to_existential called on {:?} with non-dummy Self", trait_ref);
1125         }
1126         ty::ExistentialTraitRef::erase_self_ty(self.tcx(), trait_ref)
1127     }
1128
1129     fn conv_object_ty_poly_trait_ref(&self,
1130         span: Span,
1131         trait_bounds: &[hir::PolyTraitRef],
1132         lifetime: &hir::Lifetime)
1133         -> Ty<'tcx>
1134     {
1135         let tcx = self.tcx();
1136
1137         let mut bounds = Bounds::default();
1138         let mut potential_assoc_types = Vec::new();
1139         let dummy_self = self.tcx().types.trait_object_dummy_self;
1140         // FIXME: we want to avoid collecting into a `Vec` here, but simply cloning the iterator is
1141         // not straightforward due to the borrow checker.
1142         let bound_trait_refs: Vec<_> = trait_bounds
1143             .iter()
1144             .rev()
1145             .map(|trait_bound| {
1146                 let (trait_ref, cur_potential_assoc_types) = self.instantiate_poly_trait_ref(
1147                     trait_bound,
1148                     dummy_self,
1149                     &mut bounds,
1150                 );
1151                 potential_assoc_types.extend(cur_potential_assoc_types.into_iter().flatten());
1152                 (trait_ref, trait_bound.span)
1153             })
1154             .collect();
1155
1156         // Expand trait aliases recursively and check that only one regular (non-auto) trait
1157         // is used and no 'maybe' bounds are used.
1158         let expanded_traits = traits::expand_trait_aliases(tcx, bound_trait_refs.iter().cloned());
1159         let (mut auto_traits, regular_traits): (Vec<_>, Vec<_>) =
1160             expanded_traits.partition(|i| tcx.trait_is_auto(i.trait_ref().def_id()));
1161         if regular_traits.len() > 1 {
1162             let first_trait = &regular_traits[0];
1163             let additional_trait = &regular_traits[1];
1164             let mut err = struct_span_err!(tcx.sess, additional_trait.bottom().1, E0225,
1165                 "only auto traits can be used as additional traits in a trait object"
1166             );
1167             additional_trait.label_with_exp_info(&mut err,
1168                 "additional non-auto trait", "additional use");
1169             first_trait.label_with_exp_info(&mut err,
1170                 "first non-auto trait", "first use");
1171             err.emit();
1172         }
1173
1174         if regular_traits.is_empty() && auto_traits.is_empty() {
1175             span_err!(tcx.sess, span, E0224,
1176                 "at least one non-builtin trait is required for an object type");
1177             return tcx.types.err;
1178         }
1179
1180         // Check that there are no gross object safety violations;
1181         // most importantly, that the supertraits don't contain `Self`,
1182         // to avoid ICEs.
1183         for item in &regular_traits {
1184             let object_safety_violations =
1185                 tcx.global_tcx().astconv_object_safety_violations(item.trait_ref().def_id());
1186             if !object_safety_violations.is_empty() {
1187                 tcx.report_object_safety_error(
1188                     span,
1189                     item.trait_ref().def_id(),
1190                     object_safety_violations
1191                 )
1192                     .map(|mut err| err.emit());
1193                 return tcx.types.err;
1194             }
1195         }
1196
1197         // Use a `BTreeSet` to keep output in a more consistent order.
1198         let mut associated_types = BTreeSet::default();
1199
1200         let regular_traits_refs = bound_trait_refs
1201             .into_iter()
1202             .filter(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id()))
1203             .map(|(trait_ref, _)| trait_ref);
1204         for trait_ref in traits::elaborate_trait_refs(tcx, regular_traits_refs) {
1205             debug!("conv_object_ty_poly_trait_ref: observing object predicate `{:?}`", trait_ref);
1206             match trait_ref {
1207                 ty::Predicate::Trait(pred) => {
1208                     associated_types
1209                         .extend(tcx.associated_items(pred.def_id())
1210                         .filter(|item| item.kind == ty::AssocKind::Type)
1211                         .map(|item| item.def_id));
1212                 }
1213                 ty::Predicate::Projection(pred) => {
1214                     // A `Self` within the original bound will be substituted with a
1215                     // `trait_object_dummy_self`, so check for that.
1216                     let references_self =
1217                         pred.skip_binder().ty.walk().any(|t| t == dummy_self);
1218
1219                     // If the projection output contains `Self`, force the user to
1220                     // elaborate it explicitly to avoid a lot of complexity.
1221                     //
1222                     // The "classicaly useful" case is the following:
1223                     // ```
1224                     //     trait MyTrait: FnMut() -> <Self as MyTrait>::MyOutput {
1225                     //         type MyOutput;
1226                     //     }
1227                     // ```
1228                     //
1229                     // Here, the user could theoretically write `dyn MyTrait<Output = X>`,
1230                     // but actually supporting that would "expand" to an infinitely-long type
1231                     // `fix $ τ → dyn MyTrait<MyOutput = X, Output = <τ as MyTrait>::MyOutput`.
1232                     //
1233                     // Instead, we force the user to write `dyn MyTrait<MyOutput = X, Output = X>`,
1234                     // which is uglier but works. See the discussion in #56288 for alternatives.
1235                     if !references_self {
1236                         // Include projections defined on supertraits.
1237                         bounds.projection_bounds.push((pred, DUMMY_SP))
1238                     }
1239                 }
1240                 _ => ()
1241             }
1242         }
1243
1244         for (projection_bound, _) in &bounds.projection_bounds {
1245             associated_types.remove(&projection_bound.projection_def_id());
1246         }
1247
1248         if !associated_types.is_empty() {
1249             let names = associated_types.iter().map(|item_def_id| {
1250                 let assoc_item = tcx.associated_item(*item_def_id);
1251                 let trait_def_id = assoc_item.container.id();
1252                 format!(
1253                     "`{}` (from the trait `{}`)",
1254                     assoc_item.ident,
1255                     tcx.def_path_str(trait_def_id),
1256                 )
1257             }).collect::<Vec<_>>().join(", ");
1258             let mut err = struct_span_err!(
1259                 tcx.sess,
1260                 span,
1261                 E0191,
1262                 "the value of the associated type{} {} must be specified",
1263                 if associated_types.len() == 1 { "" } else { "s" },
1264                 names,
1265             );
1266             let (suggest, potential_assoc_types_spans) =
1267                 if potential_assoc_types.len() == associated_types.len() {
1268                     // Only suggest when the amount of missing associated types equals the number of
1269                     // extra type arguments present, as that gives us a relatively high confidence
1270                     // that the user forgot to give the associtated type's name. The canonical
1271                     // example would be trying to use `Iterator<isize>` instead of
1272                     // `Iterator<Item = isize>`.
1273                     (true, potential_assoc_types)
1274                 } else {
1275                     (false, Vec::new())
1276                 };
1277             let mut suggestions = Vec::new();
1278             for (i, item_def_id) in associated_types.iter().enumerate() {
1279                 let assoc_item = tcx.associated_item(*item_def_id);
1280                 err.span_label(
1281                     span,
1282                     format!("associated type `{}` must be specified", assoc_item.ident),
1283                 );
1284                 if item_def_id.is_local() {
1285                     err.span_label(
1286                         tcx.def_span(*item_def_id),
1287                         format!("`{}` defined here", assoc_item.ident),
1288                     );
1289                 }
1290                 if suggest {
1291                     if let Ok(snippet) = tcx.sess.source_map().span_to_snippet(
1292                         potential_assoc_types_spans[i],
1293                     ) {
1294                         suggestions.push((
1295                             potential_assoc_types_spans[i],
1296                             format!("{} = {}", assoc_item.ident, snippet),
1297                         ));
1298                     }
1299                 }
1300             }
1301             if !suggestions.is_empty() {
1302                 let msg = format!("if you meant to specify the associated {}, write",
1303                     if suggestions.len() == 1 { "type" } else { "types" });
1304                 err.multipart_suggestion(
1305                     &msg,
1306                     suggestions,
1307                     Applicability::MaybeIncorrect,
1308                 );
1309             }
1310             err.emit();
1311         }
1312
1313         // De-duplicate auto traits so that, e.g., `dyn Trait + Send + Send` is the same as
1314         // `dyn Trait + Send`.
1315         auto_traits.sort_by_key(|i| i.trait_ref().def_id());
1316         auto_traits.dedup_by_key(|i| i.trait_ref().def_id());
1317         debug!("regular_traits: {:?}", regular_traits);
1318         debug!("auto_traits: {:?}", auto_traits);
1319
1320         // Erase the `dummy_self` (`trait_object_dummy_self`) used above.
1321         let existential_trait_refs = regular_traits.iter().map(|i| {
1322             i.trait_ref().map_bound(|trait_ref| self.trait_ref_to_existential(trait_ref))
1323         });
1324         let existential_projections = bounds.projection_bounds.iter().map(|(bound, _)| {
1325             bound.map_bound(|b| {
1326                 let trait_ref = self.trait_ref_to_existential(b.projection_ty.trait_ref(tcx));
1327                 ty::ExistentialProjection {
1328                     ty: b.ty,
1329                     item_def_id: b.projection_ty.item_def_id,
1330                     substs: trait_ref.substs,
1331                 }
1332             })
1333         });
1334
1335         // Calling `skip_binder` is okay because the predicates are re-bound.
1336         let regular_trait_predicates = existential_trait_refs.map(
1337             |trait_ref| ty::ExistentialPredicate::Trait(*trait_ref.skip_binder()));
1338         let auto_trait_predicates = auto_traits.into_iter().map(
1339             |trait_ref| ty::ExistentialPredicate::AutoTrait(trait_ref.trait_ref().def_id()));
1340         let mut v =
1341             regular_trait_predicates
1342             .chain(auto_trait_predicates)
1343             .chain(existential_projections
1344                 .map(|x| ty::ExistentialPredicate::Projection(*x.skip_binder())))
1345             .collect::<SmallVec<[_; 8]>>();
1346         v.sort_by(|a, b| a.stable_cmp(tcx, b));
1347         v.dedup();
1348         let existential_predicates = ty::Binder::bind(tcx.mk_existential_predicates(v.into_iter()));
1349
1350         // Use explicitly-specified region bound.
1351         let region_bound = if !lifetime.is_elided() {
1352             self.ast_region_to_region(lifetime, None)
1353         } else {
1354             self.compute_object_lifetime_bound(span, existential_predicates).unwrap_or_else(|| {
1355                 if tcx.named_region(lifetime.hir_id).is_some() {
1356                     self.ast_region_to_region(lifetime, None)
1357                 } else {
1358                     self.re_infer(span, None).unwrap_or_else(|| {
1359                         span_err!(tcx.sess, span, E0228,
1360                             "the lifetime bound for this object type cannot be deduced \
1361                              from context; please supply an explicit bound");
1362                         tcx.lifetimes.re_static
1363                     })
1364                 }
1365             })
1366         };
1367         debug!("region_bound: {:?}", region_bound);
1368
1369         let ty = tcx.mk_dynamic(existential_predicates, region_bound);
1370         debug!("trait_object_type: {:?}", ty);
1371         ty
1372     }
1373
1374     fn report_ambiguous_associated_type(
1375         &self,
1376         span: Span,
1377         type_str: &str,
1378         trait_str: &str,
1379         name: &str,
1380     ) {
1381         let mut err = struct_span_err!(self.tcx().sess, span, E0223, "ambiguous associated type");
1382         if let (Some(_), Ok(snippet)) = (
1383             self.tcx().sess.confused_type_with_std_module.borrow().get(&span),
1384             self.tcx().sess.source_map().span_to_snippet(span),
1385          ) {
1386             err.span_suggestion(
1387                 span,
1388                 "you are looking for the module in `std`, not the primitive type",
1389                 format!("std::{}", snippet),
1390                 Applicability::MachineApplicable,
1391             );
1392         } else {
1393             err.span_suggestion(
1394                     span,
1395                     "use fully-qualified syntax",
1396                     format!("<{} as {}>::{}", type_str, trait_str, name),
1397                     Applicability::HasPlaceholders
1398             );
1399         }
1400         err.emit();
1401     }
1402
1403     // Search for a bound on a type parameter which includes the associated item
1404     // given by `assoc_name`. `ty_param_def_id` is the `DefId` of the type parameter
1405     // This function will fail if there are no suitable bounds or there is
1406     // any ambiguity.
1407     fn find_bound_for_assoc_item(&self,
1408                                  ty_param_def_id: DefId,
1409                                  assoc_name: ast::Ident,
1410                                  span: Span)
1411                                  -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1412     {
1413         let tcx = self.tcx();
1414
1415         let predicates = &self.get_type_parameter_bounds(span, ty_param_def_id).predicates;
1416         let bounds = predicates.iter().filter_map(|(p, _)| p.to_opt_poly_trait_ref());
1417
1418         // Check that there is exactly one way to find an associated type with the
1419         // correct name.
1420         let suitable_bounds = traits::transitive_bounds(tcx, bounds)
1421             .filter(|b| self.trait_defines_associated_type_named(b.def_id(), assoc_name));
1422
1423         let param_hir_id = tcx.hir().as_local_hir_id(ty_param_def_id).unwrap();
1424         let param_name = tcx.hir().ty_param_name(param_hir_id);
1425         self.one_bound_for_assoc_type(suitable_bounds,
1426                                       &param_name.as_str(),
1427                                       assoc_name,
1428                                       span)
1429     }
1430
1431     // Checks that `bounds` contains exactly one element and reports appropriate
1432     // errors otherwise.
1433     fn one_bound_for_assoc_type<I>(&self,
1434                                    mut bounds: I,
1435                                    ty_param_name: &str,
1436                                    assoc_name: ast::Ident,
1437                                    span: Span)
1438         -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
1439         where I: Iterator<Item=ty::PolyTraitRef<'tcx>>
1440     {
1441         let bound = match bounds.next() {
1442             Some(bound) => bound,
1443             None => {
1444                 struct_span_err!(self.tcx().sess, span, E0220,
1445                                  "associated type `{}` not found for `{}`",
1446                                  assoc_name,
1447                                  ty_param_name)
1448                   .span_label(span, format!("associated type `{}` not found", assoc_name))
1449                   .emit();
1450                 return Err(ErrorReported);
1451             }
1452         };
1453
1454         if let Some(bound2) = bounds.next() {
1455             let bounds = iter::once(bound).chain(iter::once(bound2)).chain(bounds);
1456             let mut err = struct_span_err!(
1457                 self.tcx().sess, span, E0221,
1458                 "ambiguous associated type `{}` in bounds of `{}`",
1459                 assoc_name,
1460                 ty_param_name);
1461             err.span_label(span, format!("ambiguous associated type `{}`", assoc_name));
1462
1463             for bound in bounds {
1464                 let bound_span = self.tcx().associated_items(bound.def_id()).find(|item| {
1465                     item.kind == ty::AssocKind::Type &&
1466                         self.tcx().hygienic_eq(assoc_name, item.ident, bound.def_id())
1467                 })
1468                 .and_then(|item| self.tcx().hir().span_if_local(item.def_id));
1469
1470                 if let Some(span) = bound_span {
1471                     err.span_label(span, format!("ambiguous `{}` from `{}`",
1472                                                  assoc_name,
1473                                                  bound));
1474                 } else {
1475                     span_note!(&mut err, span,
1476                                "associated type `{}` could derive from `{}`",
1477                                ty_param_name,
1478                                bound);
1479                 }
1480             }
1481             err.emit();
1482         }
1483
1484         return Ok(bound);
1485     }
1486
1487     // Create a type from a path to an associated type.
1488     // For a path `A::B::C::D`, `qself_ty` and `qself_def` are the type and def for `A::B::C`
1489     // and item_segment is the path segment for `D`. We return a type and a def for
1490     // the whole path.
1491     // Will fail except for `T::A` and `Self::A`; i.e., if `qself_ty`/`qself_def` are not a type
1492     // parameter or `Self`.
1493     pub fn associated_path_to_ty(
1494         &self,
1495         hir_ref_id: hir::HirId,
1496         span: Span,
1497         qself_ty: Ty<'tcx>,
1498         qself_res: Res,
1499         assoc_segment: &hir::PathSegment,
1500         permit_variants: bool,
1501     ) -> Result<(Ty<'tcx>, DefKind, DefId), ErrorReported> {
1502         let tcx = self.tcx();
1503         let assoc_ident = assoc_segment.ident;
1504
1505         debug!("associated_path_to_ty: {:?}::{}", qself_ty, assoc_ident);
1506
1507         self.prohibit_generics(slice::from_ref(assoc_segment));
1508
1509         // Check if we have an enum variant.
1510         let mut variant_resolution = None;
1511         if let ty::Adt(adt_def, _) = qself_ty.sty {
1512             if adt_def.is_enum() {
1513                 let variant_def = adt_def.variants.iter().find(|vd| {
1514                     tcx.hygienic_eq(assoc_ident, vd.ident, adt_def.did)
1515                 });
1516                 if let Some(variant_def) = variant_def {
1517                     if permit_variants {
1518                         check_type_alias_enum_variants_enabled(tcx, span);
1519                         tcx.check_stability(variant_def.def_id, Some(hir_ref_id), span);
1520                         return Ok((qself_ty, DefKind::Variant, variant_def.def_id));
1521                     } else {
1522                         variant_resolution = Some(variant_def.def_id);
1523                     }
1524                 }
1525             }
1526         }
1527
1528         // Find the type of the associated item, and the trait where the associated
1529         // item is declared.
1530         let bound = match (&qself_ty.sty, qself_res) {
1531             (_, Res::SelfTy(Some(_), Some(impl_def_id))) => {
1532                 // `Self` in an impl of a trait -- we have a concrete self type and a
1533                 // trait reference.
1534                 let trait_ref = match tcx.impl_trait_ref(impl_def_id) {
1535                     Some(trait_ref) => trait_ref,
1536                     None => {
1537                         // A cycle error occurred, most likely.
1538                         return Err(ErrorReported);
1539                     }
1540                 };
1541
1542                 let candidates = traits::supertraits(tcx, ty::Binder::bind(trait_ref))
1543                     .filter(|r| self.trait_defines_associated_type_named(r.def_id(), assoc_ident));
1544
1545                 self.one_bound_for_assoc_type(candidates, "Self", assoc_ident, span)?
1546             }
1547             (&ty::Param(_), Res::SelfTy(Some(param_did), None)) |
1548             (&ty::Param(_), Res::Def(DefKind::TyParam, param_did)) => {
1549                 self.find_bound_for_assoc_item(param_did, assoc_ident, span)?
1550             }
1551             _ => {
1552                 if variant_resolution.is_some() {
1553                     // Variant in type position
1554                     let msg = format!("expected type, found variant `{}`", assoc_ident);
1555                     tcx.sess.span_err(span, &msg);
1556                 } else if qself_ty.is_enum() {
1557                     let mut err = tcx.sess.struct_span_err(
1558                         assoc_ident.span,
1559                         &format!("no variant `{}` in enum `{}`", assoc_ident, qself_ty),
1560                     );
1561
1562                     let adt_def = qself_ty.ty_adt_def().expect("enum is not an ADT");
1563                     if let Some(suggested_name) = find_best_match_for_name(
1564                         adt_def.variants.iter().map(|variant| &variant.ident.name),
1565                         &assoc_ident.as_str(),
1566                         None,
1567                     ) {
1568                         err.span_suggestion(
1569                             assoc_ident.span,
1570                             "there is a variant with a similar name",
1571                             suggested_name.to_string(),
1572                             Applicability::MaybeIncorrect,
1573                         );
1574                     } else {
1575                         err.span_label(span, format!("variant not found in `{}`", qself_ty));
1576                     }
1577
1578                     if let Some(sp) = tcx.hir().span_if_local(adt_def.did) {
1579                         let sp = tcx.sess.source_map().def_span(sp);
1580                         err.span_label(sp, format!("variant `{}` not found here", assoc_ident));
1581                     }
1582
1583                     err.emit();
1584                 } else if !qself_ty.references_error() {
1585                     // Don't print `TyErr` to the user.
1586                     self.report_ambiguous_associated_type(
1587                         span,
1588                         &qself_ty.to_string(),
1589                         "Trait",
1590                         &assoc_ident.as_str(),
1591                     );
1592                 }
1593                 return Err(ErrorReported);
1594             }
1595         };
1596
1597         let trait_did = bound.def_id();
1598         let (assoc_ident, def_scope) =
1599             tcx.adjust_ident_and_get_scope(assoc_ident, trait_did, hir_ref_id);
1600         let item = tcx.associated_items(trait_did).find(|i| {
1601             Namespace::from(i.kind) == Namespace::Type &&
1602                 i.ident.modern() == assoc_ident
1603         }).expect("missing associated type");
1604
1605         let ty = self.projected_ty_from_poly_trait_ref(span, item.def_id, bound);
1606         let ty = self.normalize_ty(span, ty);
1607
1608         let kind = DefKind::AssocTy;
1609         if !item.vis.is_accessible_from(def_scope, tcx) {
1610             let msg = format!("{} `{}` is private", kind.descr(), assoc_ident);
1611             tcx.sess.span_err(span, &msg);
1612         }
1613         tcx.check_stability(item.def_id, Some(hir_ref_id), span);
1614
1615         if let Some(variant_def_id) = variant_resolution {
1616             let mut err = tcx.struct_span_lint_hir(
1617                 AMBIGUOUS_ASSOCIATED_ITEMS,
1618                 hir_ref_id,
1619                 span,
1620                 "ambiguous associated item",
1621             );
1622
1623             let mut could_refer_to = |kind: DefKind, def_id, also| {
1624                 let note_msg = format!("`{}` could{} refer to {} defined here",
1625                                        assoc_ident, also, kind.descr());
1626                 err.span_note(tcx.def_span(def_id), &note_msg);
1627             };
1628             could_refer_to(DefKind::Variant, variant_def_id, "");
1629             could_refer_to(kind, item.def_id, " also");
1630
1631             err.span_suggestion(
1632                 span,
1633                 "use fully-qualified syntax",
1634                 format!("<{} as {}>::{}", qself_ty, "Trait", assoc_ident),
1635                 Applicability::HasPlaceholders,
1636             ).emit();
1637         }
1638
1639         Ok((ty, kind, item.def_id))
1640     }
1641
1642     fn qpath_to_ty(&self,
1643                    span: Span,
1644                    opt_self_ty: Option<Ty<'tcx>>,
1645                    item_def_id: DefId,
1646                    trait_segment: &hir::PathSegment,
1647                    item_segment: &hir::PathSegment)
1648                    -> Ty<'tcx>
1649     {
1650         let tcx = self.tcx();
1651         let trait_def_id = tcx.parent(item_def_id).unwrap();
1652
1653         self.prohibit_generics(slice::from_ref(item_segment));
1654
1655         let self_ty = if let Some(ty) = opt_self_ty {
1656             ty
1657         } else {
1658             let path_str = tcx.def_path_str(trait_def_id);
1659             self.report_ambiguous_associated_type(
1660                 span,
1661                 "Type",
1662                 &path_str,
1663                 &item_segment.ident.as_str(),
1664             );
1665             return tcx.types.err;
1666         };
1667
1668         debug!("qpath_to_ty: self_type={:?}", self_ty);
1669
1670         let trait_ref = self.ast_path_to_mono_trait_ref(span,
1671                                                         trait_def_id,
1672                                                         self_ty,
1673                                                         trait_segment);
1674
1675         debug!("qpath_to_ty: trait_ref={:?}", trait_ref);
1676
1677         self.normalize_ty(span, tcx.mk_projection(item_def_id, trait_ref.substs))
1678     }
1679
1680     pub fn prohibit_generics<'a, T: IntoIterator<Item = &'a hir::PathSegment>>(
1681             &self, segments: T) -> bool {
1682         let mut has_err = false;
1683         for segment in segments {
1684             segment.with_generic_args(|generic_args| {
1685                 let (mut err_for_lt, mut err_for_ty, mut err_for_ct) = (false, false, false);
1686                 for arg in &generic_args.args {
1687                     let (span, kind) = match arg {
1688                         hir::GenericArg::Lifetime(lt) => {
1689                             if err_for_lt { continue }
1690                             err_for_lt = true;
1691                             has_err = true;
1692                             (lt.span, "lifetime")
1693                         }
1694                         hir::GenericArg::Type(ty) => {
1695                             if err_for_ty { continue }
1696                             err_for_ty = true;
1697                             has_err = true;
1698                             (ty.span, "type")
1699                         }
1700                         hir::GenericArg::Const(ct) => {
1701                             if err_for_ct { continue }
1702                             err_for_ct = true;
1703                             (ct.span, "const")
1704                         }
1705                     };
1706                     let mut err = struct_span_err!(
1707                         self.tcx().sess,
1708                         span,
1709                         E0109,
1710                         "{} arguments are not allowed for this type",
1711                         kind,
1712                     );
1713                     err.span_label(span, format!("{} argument not allowed", kind));
1714                     err.emit();
1715                     if err_for_lt && err_for_ty && err_for_ct {
1716                         break;
1717                     }
1718                 }
1719                 for binding in &generic_args.bindings {
1720                     has_err = true;
1721                     Self::prohibit_assoc_ty_binding(self.tcx(), binding.span);
1722                     break;
1723                 }
1724             })
1725         }
1726         has_err
1727     }
1728
1729     pub fn prohibit_assoc_ty_binding(tcx: TyCtxt<'_, '_, '_>, span: Span) {
1730         let mut err = struct_span_err!(tcx.sess, span, E0229,
1731                                        "associated type bindings are not allowed here");
1732         err.span_label(span, "associated type not allowed here").emit();
1733     }
1734
1735     // FIXME(eddyb, varkor) handle type paths here too, not just value ones.
1736     pub fn def_ids_for_value_path_segments(
1737         &self,
1738         segments: &[hir::PathSegment],
1739         self_ty: Option<Ty<'tcx>>,
1740         kind: DefKind,
1741         def_id: DefId,
1742     ) -> Vec<PathSeg> {
1743         // We need to extract the type parameters supplied by the user in
1744         // the path `path`. Due to the current setup, this is a bit of a
1745         // tricky-process; the problem is that resolve only tells us the
1746         // end-point of the path resolution, and not the intermediate steps.
1747         // Luckily, we can (at least for now) deduce the intermediate steps
1748         // just from the end-point.
1749         //
1750         // There are basically five cases to consider:
1751         //
1752         // 1. Reference to a constructor of a struct:
1753         //
1754         //        struct Foo<T>(...)
1755         //
1756         //    In this case, the parameters are declared in the type space.
1757         //
1758         // 2. Reference to a constructor of an enum variant:
1759         //
1760         //        enum E<T> { Foo(...) }
1761         //
1762         //    In this case, the parameters are defined in the type space,
1763         //    but may be specified either on the type or the variant.
1764         //
1765         // 3. Reference to a fn item or a free constant:
1766         //
1767         //        fn foo<T>() { }
1768         //
1769         //    In this case, the path will again always have the form
1770         //    `a::b::foo::<T>` where only the final segment should have
1771         //    type parameters. However, in this case, those parameters are
1772         //    declared on a value, and hence are in the `FnSpace`.
1773         //
1774         // 4. Reference to a method or an associated constant:
1775         //
1776         //        impl<A> SomeStruct<A> {
1777         //            fn foo<B>(...)
1778         //        }
1779         //
1780         //    Here we can have a path like
1781         //    `a::b::SomeStruct::<A>::foo::<B>`, in which case parameters
1782         //    may appear in two places. The penultimate segment,
1783         //    `SomeStruct::<A>`, contains parameters in TypeSpace, and the
1784         //    final segment, `foo::<B>` contains parameters in fn space.
1785         //
1786         // The first step then is to categorize the segments appropriately.
1787
1788         let tcx = self.tcx();
1789
1790         assert!(!segments.is_empty());
1791         let last = segments.len() - 1;
1792
1793         let mut path_segs = vec![];
1794
1795         match kind {
1796             // Case 1. Reference to a struct constructor.
1797             DefKind::Ctor(CtorOf::Struct, ..) => {
1798                 // Everything but the final segment should have no
1799                 // parameters at all.
1800                 let generics = tcx.generics_of(def_id);
1801                 // Variant and struct constructors use the
1802                 // generics of their parent type definition.
1803                 let generics_def_id = generics.parent.unwrap_or(def_id);
1804                 path_segs.push(PathSeg(generics_def_id, last));
1805             }
1806
1807             // Case 2. Reference to a variant constructor.
1808             DefKind::Ctor(CtorOf::Variant, ..)
1809             | DefKind::Variant => {
1810                 let adt_def = self_ty.map(|t| t.ty_adt_def().unwrap());
1811                 let (generics_def_id, index) = if let Some(adt_def) = adt_def {
1812                     debug_assert!(adt_def.is_enum());
1813                     (adt_def.did, last)
1814                 } else if last >= 1 && segments[last - 1].args.is_some() {
1815                     // Everything but the penultimate segment should have no
1816                     // parameters at all.
1817                     let mut def_id = def_id;
1818
1819                     // `DefKind::Ctor` -> `DefKind::Variant`
1820                     if let DefKind::Ctor(..) = kind {
1821                         def_id = tcx.parent(def_id).unwrap()
1822                     }
1823
1824                     // `DefKind::Variant` -> `DefKind::Enum`
1825                     let enum_def_id = tcx.parent(def_id).unwrap();
1826                     (enum_def_id, last - 1)
1827                 } else {
1828                     // FIXME: lint here recommending `Enum::<...>::Variant` form
1829                     // instead of `Enum::Variant::<...>` form.
1830
1831                     // Everything but the final segment should have no
1832                     // parameters at all.
1833                     let generics = tcx.generics_of(def_id);
1834                     // Variant and struct constructors use the
1835                     // generics of their parent type definition.
1836                     (generics.parent.unwrap_or(def_id), last)
1837                 };
1838                 path_segs.push(PathSeg(generics_def_id, index));
1839             }
1840
1841             // Case 3. Reference to a top-level value.
1842             DefKind::Fn
1843             | DefKind::Const
1844             | DefKind::ConstParam
1845             | DefKind::Static => {
1846                 path_segs.push(PathSeg(def_id, last));
1847             }
1848
1849             // Case 4. Reference to a method or associated const.
1850             DefKind::Method
1851             | DefKind::AssocConst => {
1852                 if segments.len() >= 2 {
1853                     let generics = tcx.generics_of(def_id);
1854                     path_segs.push(PathSeg(generics.parent.unwrap(), last - 1));
1855                 }
1856                 path_segs.push(PathSeg(def_id, last));
1857             }
1858
1859             kind => bug!("unexpected definition kind {:?} for {:?}", kind, def_id),
1860         }
1861
1862         debug!("path_segs = {:?}", path_segs);
1863
1864         path_segs
1865     }
1866
1867     // Check a type `Path` and convert it to a `Ty`.
1868     pub fn res_to_ty(&self,
1869                      opt_self_ty: Option<Ty<'tcx>>,
1870                      path: &hir::Path,
1871                      permit_variants: bool)
1872                      -> Ty<'tcx> {
1873         let tcx = self.tcx();
1874
1875         debug!("res_to_ty(res={:?}, opt_self_ty={:?}, path_segments={:?})",
1876                path.res, opt_self_ty, path.segments);
1877
1878         let span = path.span;
1879         match path.res {
1880             Res::Def(DefKind::Existential, did) => {
1881                 // Check for desugared `impl Trait`.
1882                 assert!(ty::is_impl_trait_defn(tcx, did).is_none());
1883                 let item_segment = path.segments.split_last().unwrap();
1884                 self.prohibit_generics(item_segment.1);
1885                 let substs = self.ast_path_substs_for_ty(span, did, item_segment.0);
1886                 self.normalize_ty(
1887                     span,
1888                     tcx.mk_opaque(did, substs),
1889                 )
1890             }
1891             Res::Def(DefKind::Enum, did)
1892             | Res::Def(DefKind::TyAlias, did)
1893             | Res::Def(DefKind::Struct, did)
1894             | Res::Def(DefKind::Union, did)
1895             | Res::Def(DefKind::ForeignTy, did) => {
1896                 assert_eq!(opt_self_ty, None);
1897                 self.prohibit_generics(path.segments.split_last().unwrap().1);
1898                 self.ast_path_to_ty(span, did, path.segments.last().unwrap())
1899             }
1900             Res::Def(kind @ DefKind::Variant, def_id) if permit_variants => {
1901                 // Convert "variant type" as if it were a real type.
1902                 // The resulting `Ty` is type of the variant's enum for now.
1903                 assert_eq!(opt_self_ty, None);
1904
1905                 let path_segs =
1906                     self.def_ids_for_value_path_segments(&path.segments, None, kind, def_id);
1907                 let generic_segs: FxHashSet<_> =
1908                     path_segs.iter().map(|PathSeg(_, index)| index).collect();
1909                 self.prohibit_generics(path.segments.iter().enumerate().filter_map(|(index, seg)| {
1910                     if !generic_segs.contains(&index) {
1911                         Some(seg)
1912                     } else {
1913                         None
1914                     }
1915                 }));
1916
1917                 let PathSeg(def_id, index) = path_segs.last().unwrap();
1918                 self.ast_path_to_ty(span, *def_id, &path.segments[*index])
1919             }
1920             Res::Def(DefKind::TyParam, did) => {
1921                 assert_eq!(opt_self_ty, None);
1922                 self.prohibit_generics(&path.segments);
1923
1924                 let hir_id = tcx.hir().as_local_hir_id(did).unwrap();
1925                 let item_id = tcx.hir().get_parent_node_by_hir_id(hir_id);
1926                 let item_def_id = tcx.hir().local_def_id_from_hir_id(item_id);
1927                 let generics = tcx.generics_of(item_def_id);
1928                 let index = generics.param_def_id_to_index[
1929                     &tcx.hir().local_def_id_from_hir_id(hir_id)];
1930                 tcx.mk_ty_param(index, tcx.hir().name_by_hir_id(hir_id).as_interned_str())
1931             }
1932             Res::SelfTy(Some(_), None) => {
1933                 // `Self` in trait or type alias.
1934                 assert_eq!(opt_self_ty, None);
1935                 self.prohibit_generics(&path.segments);
1936                 tcx.mk_self_type()
1937             }
1938             Res::SelfTy(_, Some(def_id)) => {
1939                 // `Self` in impl (we know the concrete type).
1940                 assert_eq!(opt_self_ty, None);
1941                 self.prohibit_generics(&path.segments);
1942                 // Try to evaluate any array length constants.
1943                 self.normalize_ty(span, tcx.at(span).type_of(def_id))
1944             }
1945             Res::Def(DefKind::AssocTy, def_id) => {
1946                 debug_assert!(path.segments.len() >= 2);
1947                 self.prohibit_generics(&path.segments[..path.segments.len() - 2]);
1948                 self.qpath_to_ty(span,
1949                                  opt_self_ty,
1950                                  def_id,
1951                                  &path.segments[path.segments.len() - 2],
1952                                  path.segments.last().unwrap())
1953             }
1954             Res::PrimTy(prim_ty) => {
1955                 assert_eq!(opt_self_ty, None);
1956                 self.prohibit_generics(&path.segments);
1957                 match prim_ty {
1958                     hir::Bool => tcx.types.bool,
1959                     hir::Char => tcx.types.char,
1960                     hir::Int(it) => tcx.mk_mach_int(it),
1961                     hir::Uint(uit) => tcx.mk_mach_uint(uit),
1962                     hir::Float(ft) => tcx.mk_mach_float(ft),
1963                     hir::Str => tcx.mk_str()
1964                 }
1965             }
1966             Res::Err => {
1967                 self.set_tainted_by_errors();
1968                 return self.tcx().types.err;
1969             }
1970             _ => span_bug!(span, "unexpected resolution: {:?}", path.res)
1971         }
1972     }
1973
1974     /// Parses the programmer's textual representation of a type into our
1975     /// internal notion of a type.
1976     pub fn ast_ty_to_ty(&self, ast_ty: &hir::Ty) -> Ty<'tcx> {
1977         debug!("ast_ty_to_ty(id={:?}, ast_ty={:?} ty_ty={:?})",
1978                ast_ty.hir_id, ast_ty, ast_ty.node);
1979
1980         let tcx = self.tcx();
1981
1982         let result_ty = match ast_ty.node {
1983             hir::TyKind::Slice(ref ty) => {
1984                 tcx.mk_slice(self.ast_ty_to_ty(&ty))
1985             }
1986             hir::TyKind::Ptr(ref mt) => {
1987                 tcx.mk_ptr(ty::TypeAndMut {
1988                     ty: self.ast_ty_to_ty(&mt.ty),
1989                     mutbl: mt.mutbl
1990                 })
1991             }
1992             hir::TyKind::Rptr(ref region, ref mt) => {
1993                 let r = self.ast_region_to_region(region, None);
1994                 debug!("ast_ty_to_ty: r={:?}", r);
1995                 let t = self.ast_ty_to_ty(&mt.ty);
1996                 tcx.mk_ref(r, ty::TypeAndMut {ty: t, mutbl: mt.mutbl})
1997             }
1998             hir::TyKind::Never => {
1999                 tcx.types.never
2000             },
2001             hir::TyKind::Tup(ref fields) => {
2002                 tcx.mk_tup(fields.iter().map(|t| self.ast_ty_to_ty(&t)))
2003             }
2004             hir::TyKind::BareFn(ref bf) => {
2005                 require_c_abi_if_c_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
2006                 tcx.mk_fn_ptr(self.ty_of_fn(bf.unsafety, bf.abi, &bf.decl))
2007             }
2008             hir::TyKind::TraitObject(ref bounds, ref lifetime) => {
2009                 self.conv_object_ty_poly_trait_ref(ast_ty.span, bounds, lifetime)
2010             }
2011             hir::TyKind::Path(hir::QPath::Resolved(ref maybe_qself, ref path)) => {
2012                 debug!("ast_ty_to_ty: maybe_qself={:?} path={:?}", maybe_qself, path);
2013                 let opt_self_ty = maybe_qself.as_ref().map(|qself| {
2014                     self.ast_ty_to_ty(qself)
2015                 });
2016                 self.res_to_ty(opt_self_ty, path, false)
2017             }
2018             hir::TyKind::Def(item_id, ref lifetimes) => {
2019                 let did = tcx.hir().local_def_id_from_hir_id(item_id.id);
2020                 self.impl_trait_ty_to_ty(did, lifetimes)
2021             }
2022             hir::TyKind::Path(hir::QPath::TypeRelative(ref qself, ref segment)) => {
2023                 debug!("ast_ty_to_ty: qself={:?} segment={:?}", qself, segment);
2024                 let ty = self.ast_ty_to_ty(qself);
2025
2026                 let res = if let hir::TyKind::Path(hir::QPath::Resolved(_, ref path)) = qself.node {
2027                     path.res
2028                 } else {
2029                     Res::Err
2030                 };
2031                 self.associated_path_to_ty(ast_ty.hir_id, ast_ty.span, ty, res, segment, false)
2032                     .map(|(ty, _, _)| ty).unwrap_or(tcx.types.err)
2033             }
2034             hir::TyKind::Array(ref ty, ref length) => {
2035                 let length = self.ast_const_to_const(length, tcx.types.usize);
2036                 let array_ty = tcx.mk_ty(ty::Array(self.ast_ty_to_ty(&ty), length));
2037                 self.normalize_ty(ast_ty.span, array_ty)
2038             }
2039             hir::TyKind::Typeof(ref _e) => {
2040                 struct_span_err!(tcx.sess, ast_ty.span, E0516,
2041                                  "`typeof` is a reserved keyword but unimplemented")
2042                     .span_label(ast_ty.span, "reserved keyword")
2043                     .emit();
2044
2045                 tcx.types.err
2046             }
2047             hir::TyKind::Infer => {
2048                 // Infer also appears as the type of arguments or return
2049                 // values in a ExprKind::Closure, or as
2050                 // the type of local variables. Both of these cases are
2051                 // handled specially and will not descend into this routine.
2052                 self.ty_infer(ast_ty.span)
2053             }
2054             hir::TyKind::CVarArgs(lt) => {
2055                 let va_list_did = match tcx.lang_items().va_list() {
2056                     Some(did) => did,
2057                     None => span_bug!(ast_ty.span,
2058                                       "`va_list` lang item required for variadics"),
2059                 };
2060                 let region = self.ast_region_to_region(&lt, None);
2061                 tcx.type_of(va_list_did).subst(tcx, &[region.into()])
2062             }
2063             hir::TyKind::AssocTyExistential(..) => {
2064                 // Type is never actually used.
2065                 tcx.types.err
2066             }
2067             hir::TyKind::Err => {
2068                 tcx.types.err
2069             }
2070         };
2071
2072         debug!("ast_ty_to_ty: result_ty={:?}", result_ty);
2073
2074         self.record_ty(ast_ty.hir_id, result_ty, ast_ty.span);
2075         result_ty
2076     }
2077
2078     pub fn ast_const_to_const(
2079         &self,
2080         ast_const: &hir::AnonConst,
2081         ty: Ty<'tcx>
2082     ) -> &'tcx ty::Const<'tcx> {
2083         debug!("ast_const_to_const(id={:?}, ast_const={:?})", ast_const.hir_id, ast_const);
2084
2085         let tcx = self.tcx();
2086         let def_id = tcx.hir().local_def_id_from_hir_id(ast_const.hir_id);
2087
2088         let mut const_ = ty::Const {
2089             val: ConstValue::Unevaluated(
2090                 def_id,
2091                 InternalSubsts::identity_for_item(tcx, def_id),
2092             ),
2093             ty,
2094         };
2095
2096         let mut expr = &tcx.hir().body(ast_const.body).value;
2097
2098         // Unwrap a block, so that e.g. `{ P }` is recognised as a parameter. Const arguments
2099         // currently have to be wrapped in curly brackets, so it's necessary to special-case.
2100         if let ExprKind::Block(block, _) = &expr.node {
2101             if block.stmts.is_empty() {
2102                 if let Some(trailing) = &block.expr {
2103                     expr = &trailing;
2104                 }
2105             }
2106         }
2107
2108         if let ExprKind::Path(ref qpath) = expr.node {
2109             if let hir::QPath::Resolved(_, ref path) = qpath {
2110                 if let Res::Def(DefKind::ConstParam, def_id) = path.res {
2111                     let node_id = tcx.hir().as_local_node_id(def_id).unwrap();
2112                     let item_id = tcx.hir().get_parent_node(node_id);
2113                     let item_def_id = tcx.hir().local_def_id(item_id);
2114                     let generics = tcx.generics_of(item_def_id);
2115                     let index = generics.param_def_id_to_index[&tcx.hir().local_def_id(node_id)];
2116                     let name = tcx.hir().name(node_id).as_interned_str();
2117                     const_.val = ConstValue::Param(ty::ParamConst::new(index, name));
2118                 }
2119             }
2120         };
2121
2122         tcx.mk_const(const_)
2123     }
2124
2125     pub fn impl_trait_ty_to_ty(
2126         &self,
2127         def_id: DefId,
2128         lifetimes: &[hir::GenericArg],
2129     ) -> Ty<'tcx> {
2130         debug!("impl_trait_ty_to_ty(def_id={:?}, lifetimes={:?})", def_id, lifetimes);
2131         let tcx = self.tcx();
2132
2133         let generics = tcx.generics_of(def_id);
2134
2135         debug!("impl_trait_ty_to_ty: generics={:?}", generics);
2136         let substs = InternalSubsts::for_item(tcx, def_id, |param, _| {
2137             if let Some(i) = (param.index as usize).checked_sub(generics.parent_count) {
2138                 // Our own parameters are the resolved lifetimes.
2139                 match param.kind {
2140                     GenericParamDefKind::Lifetime => {
2141                         if let hir::GenericArg::Lifetime(lifetime) = &lifetimes[i] {
2142                             self.ast_region_to_region(lifetime, None).into()
2143                         } else {
2144                             bug!()
2145                         }
2146                     }
2147                     _ => bug!()
2148                 }
2149             } else {
2150                 // Replace all parent lifetimes with `'static`.
2151                 match param.kind {
2152                     GenericParamDefKind::Lifetime => {
2153                         tcx.lifetimes.re_static.into()
2154                     }
2155                     _ => tcx.mk_param_from_def(param)
2156                 }
2157             }
2158         });
2159         debug!("impl_trait_ty_to_ty: substs={:?}", substs);
2160
2161         let ty = tcx.mk_opaque(def_id, substs);
2162         debug!("impl_trait_ty_to_ty: {}", ty);
2163         ty
2164     }
2165
2166     pub fn ty_of_arg(&self,
2167                      ty: &hir::Ty,
2168                      expected_ty: Option<Ty<'tcx>>)
2169                      -> Ty<'tcx>
2170     {
2171         match ty.node {
2172             hir::TyKind::Infer if expected_ty.is_some() => {
2173                 self.record_ty(ty.hir_id, expected_ty.unwrap(), ty.span);
2174                 expected_ty.unwrap()
2175             }
2176             _ => self.ast_ty_to_ty(ty),
2177         }
2178     }
2179
2180     pub fn ty_of_fn(&self,
2181                     unsafety: hir::Unsafety,
2182                     abi: abi::Abi,
2183                     decl: &hir::FnDecl)
2184                     -> ty::PolyFnSig<'tcx> {
2185         debug!("ty_of_fn");
2186
2187         let tcx = self.tcx();
2188         let input_tys =
2189             decl.inputs.iter().map(|a| self.ty_of_arg(a, None));
2190
2191         let output_ty = match decl.output {
2192             hir::Return(ref output) => self.ast_ty_to_ty(output),
2193             hir::DefaultReturn(..) => tcx.mk_unit(),
2194         };
2195
2196         debug!("ty_of_fn: output_ty={:?}", output_ty);
2197
2198         let bare_fn_ty = ty::Binder::bind(tcx.mk_fn_sig(
2199             input_tys,
2200             output_ty,
2201             decl.c_variadic,
2202             unsafety,
2203             abi
2204         ));
2205
2206         // Find any late-bound regions declared in return type that do
2207         // not appear in the arguments. These are not well-formed.
2208         //
2209         // Example:
2210         //     for<'a> fn() -> &'a str <-- 'a is bad
2211         //     for<'a> fn(&'a String) -> &'a str <-- 'a is ok
2212         let inputs = bare_fn_ty.inputs();
2213         let late_bound_in_args = tcx.collect_constrained_late_bound_regions(
2214             &inputs.map_bound(|i| i.to_owned()));
2215         let output = bare_fn_ty.output();
2216         let late_bound_in_ret = tcx.collect_referenced_late_bound_regions(&output);
2217         for br in late_bound_in_ret.difference(&late_bound_in_args) {
2218             let lifetime_name = match *br {
2219                 ty::BrNamed(_, name) => format!("lifetime `{}`,", name),
2220                 ty::BrAnon(_) | ty::BrEnv => "an anonymous lifetime".to_string(),
2221             };
2222             let mut err = struct_span_err!(tcx.sess,
2223                                            decl.output.span(),
2224                                            E0581,
2225                                            "return type references {} \
2226                                             which is not constrained by the fn input types",
2227                                            lifetime_name);
2228             if let ty::BrAnon(_) = *br {
2229                 // The only way for an anonymous lifetime to wind up
2230                 // in the return type but **also** be unconstrained is
2231                 // if it only appears in "associated types" in the
2232                 // input. See #47511 for an example. In this case,
2233                 // though we can easily give a hint that ought to be
2234                 // relevant.
2235                 err.note("lifetimes appearing in an associated type \
2236                           are not considered constrained");
2237             }
2238             err.emit();
2239         }
2240
2241         bare_fn_ty
2242     }
2243
2244     /// Given the bounds on an object, determines what single region bound (if any) we can
2245     /// use to summarize this type. The basic idea is that we will use the bound the user
2246     /// provided, if they provided one, and otherwise search the supertypes of trait bounds
2247     /// for region bounds. It may be that we can derive no bound at all, in which case
2248     /// we return `None`.
2249     fn compute_object_lifetime_bound(&self,
2250         span: Span,
2251         existential_predicates: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>)
2252         -> Option<ty::Region<'tcx>> // if None, use the default
2253     {
2254         let tcx = self.tcx();
2255
2256         debug!("compute_opt_region_bound(existential_predicates={:?})",
2257                existential_predicates);
2258
2259         // No explicit region bound specified. Therefore, examine trait
2260         // bounds and see if we can derive region bounds from those.
2261         let derived_region_bounds =
2262             object_region_bounds(tcx, existential_predicates);
2263
2264         // If there are no derived region bounds, then report back that we
2265         // can find no region bound. The caller will use the default.
2266         if derived_region_bounds.is_empty() {
2267             return None;
2268         }
2269
2270         // If any of the derived region bounds are 'static, that is always
2271         // the best choice.
2272         if derived_region_bounds.iter().any(|&r| ty::ReStatic == *r) {
2273             return Some(tcx.lifetimes.re_static);
2274         }
2275
2276         // Determine whether there is exactly one unique region in the set
2277         // of derived region bounds. If so, use that. Otherwise, report an
2278         // error.
2279         let r = derived_region_bounds[0];
2280         if derived_region_bounds[1..].iter().any(|r1| r != *r1) {
2281             span_err!(tcx.sess, span, E0227,
2282                       "ambiguous lifetime bound, explicit lifetime bound required");
2283         }
2284         return Some(r);
2285     }
2286 }
2287
2288 // A helper struct for conveniently grouping a set of bounds which we pass to
2289 // and return from functions in multiple places.
2290 #[derive(Default, PartialEq, Eq, Clone, Debug)]
2291 pub struct Bounds<'tcx> {
2292     pub region_bounds: Vec<(ty::Region<'tcx>, Span)>,
2293     pub trait_bounds: Vec<(ty::PolyTraitRef<'tcx>, Span)>,
2294     pub projection_bounds: Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>,
2295     pub implicitly_sized: Option<Span>,
2296 }
2297
2298 impl<'a, 'gcx, 'tcx> Bounds<'tcx> {
2299     pub fn predicates(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, param_ty: Ty<'tcx>)
2300                       -> Vec<(ty::Predicate<'tcx>, Span)>
2301     {
2302         // If it could be sized, and is, add the `Sized` predicate.
2303         let sized_predicate = self.implicitly_sized.and_then(|span| {
2304             tcx.lang_items().sized_trait().map(|sized| {
2305                 let trait_ref = ty::TraitRef {
2306                     def_id: sized,
2307                     substs: tcx.mk_substs_trait(param_ty, &[])
2308                 };
2309                 (trait_ref.to_predicate(), span)
2310             })
2311         });
2312
2313         sized_predicate.into_iter().chain(
2314             self.region_bounds.iter().map(|&(region_bound, span)| {
2315                 // Account for the binder being introduced below; no need to shift `param_ty`
2316                 // because, at present at least, it can only refer to early-bound regions.
2317                 let region_bound = ty::fold::shift_region(tcx, region_bound, 1);
2318                 let outlives = ty::OutlivesPredicate(param_ty, region_bound);
2319                 (ty::Binder::dummy(outlives).to_predicate(), span)
2320             }).chain(
2321                 self.trait_bounds.iter().map(|&(bound_trait_ref, span)| {
2322                     (bound_trait_ref.to_predicate(), span)
2323                 })
2324             ).chain(
2325                 self.projection_bounds.iter().map(|&(projection, span)| {
2326                     (projection.to_predicate(), span)
2327                 })
2328             )
2329         ).collect()
2330     }
2331 }