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