src/librustc_typeck/astconv/generics.rs

   1 use crate::astconv::{
   2     AstConv, ExplicitLateBound, GenericArgCountMismatch, GenericArgCountResult, GenericArgPosition,
   3 };
   4 use rustc_ast::ast::ParamKindOrd;
   5 use rustc_errors::{pluralize, struct_span_err, DiagnosticId, ErrorReported};
   6 use rustc_hir as hir;
   7 use rustc_hir::def_id::DefId;
   8 use rustc_hir::{GenericArg, GenericArgs};
   9 use rustc_middle::ty::{
  10     self, subst, subst::SubstsRef, GenericParamDef, GenericParamDefKind, Ty, TyCtxt,
  11 };
  12 use rustc_session::{lint::builtin::LATE_BOUND_LIFETIME_ARGUMENTS, Session};
  13 use rustc_span::{symbol::kw, MultiSpan, Span};
  14
  15 use smallvec::SmallVec;
  16
  17 impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
  18     /// Report an error that a generic argument did not match the generic parameter that was
  19     /// expected.
  20     fn generic_arg_mismatch_err(
  21         sess: &Session,
  22         arg: &GenericArg<'_>,
  23         kind: &'static str,
  24         help: Option<&str>,
  25     ) {
  26         let mut err = struct_span_err!(
  27             sess,
  28             arg.span(),
  29             E0747,
  30             "{} provided when a {} was expected",
  31             arg.descr(),
  32             kind,
  33         );
  34
  35         let unordered = sess.features_untracked().const_generics;
  36         let kind_ord = match kind {
  37             "lifetime" => ParamKindOrd::Lifetime,
  38             "type" => ParamKindOrd::Type,
  39             "constant" => ParamKindOrd::Const { unordered },
  40             // It's more concise to match on the string representation, though it means
  41             // the match is non-exhaustive.
  42             _ => bug!("invalid generic parameter kind {}", kind),
  43         };
  44         let arg_ord = match arg {
  45             GenericArg::Lifetime(_) => ParamKindOrd::Lifetime,
  46             GenericArg::Type(_) => ParamKindOrd::Type,
  47             GenericArg::Const(_) => ParamKindOrd::Const { unordered },
  48         };
  49
  50         // This note is only true when generic parameters are strictly ordered by their kind.
  51         if kind_ord.cmp(&arg_ord) != core::cmp::Ordering::Equal {
  52             let (first, last) =
  53                 if kind_ord < arg_ord { (kind, arg.descr()) } else { (arg.descr(), kind) };
  54             err.note(&format!("{} arguments must be provided before {} arguments", first, last));
  55             if let Some(help) = help {
  56                 err.help(help);
  57             }
  58         }
  59
  60         err.emit();
  61     }
  62
  63     /// Creates the relevant generic argument substitutions
  64     /// corresponding to a set of generic parameters. This is a
  65     /// rather complex function. Let us try to explain the role
  66     /// of each of its parameters:
  67     ///
  68     /// To start, we are given the `def_id` of the thing we are
  69     /// creating the substitutions for, and a partial set of
  70     /// substitutions `parent_substs`. In general, the substitutions
  71     /// for an item begin with substitutions for all the "parents" of
  72     /// that item -- e.g., for a method it might include the
  73     /// parameters from the impl.
  74     ///
  75     /// Therefore, the method begins by walking down these parents,
  76     /// starting with the outermost parent and proceed inwards until
  77     /// it reaches `def_id`. For each parent `P`, it will check `parent_substs`
  78     /// first to see if the parent's substitutions are listed in there. If so,
  79     /// we can append those and move on. Otherwise, it invokes the
  80     /// three callback functions:
  81     ///
  82     /// - `args_for_def_id`: given the `DefId` `P`, supplies back the
  83     ///   generic arguments that were given to that parent from within
  84     ///   the path; so e.g., if you have `<T as Foo>::Bar`, the `DefId`
  85     ///   might refer to the trait `Foo`, and the arguments might be
  86     ///   `[T]`. The boolean value indicates whether to infer values
  87     ///   for arguments whose values were not explicitly provided.
  88     /// - `provided_kind`: given the generic parameter and the value from `args_for_def_id`,
  89     ///   instantiate a `GenericArg`.
  90     /// - `inferred_kind`: if no parameter was provided, and inference is enabled, then
  91     ///   creates a suitable inference variable.
  92     pub fn create_substs_for_generic_args<'b>(
  93         tcx: TyCtxt<'tcx>,
  94         def_id: DefId,
  95         parent_substs: &[subst::GenericArg<'tcx>],
  96         has_self: bool,
  97         self_ty: Option<Ty<'tcx>>,
  98         arg_count: GenericArgCountResult,
  99         args_for_def_id: impl Fn(DefId) -> (Option<&'b GenericArgs<'b>>, bool),
 100         mut provided_kind: impl FnMut(&GenericParamDef, &GenericArg<'_>) -> subst::GenericArg<'tcx>,
 101         mut inferred_kind: impl FnMut(
 102             Option<&[subst::GenericArg<'tcx>]>,
 103             &GenericParamDef,
 104             bool,
 105         ) -> subst::GenericArg<'tcx>,
 106     ) -> SubstsRef<'tcx> {
 107         // Collect the segments of the path; we need to substitute arguments
 108         // for parameters throughout the entire path (wherever there are
 109         // generic parameters).
 110         let mut parent_defs = tcx.generics_of(def_id);
 111         let count = parent_defs.count();
 112         let mut stack = vec![(def_id, parent_defs)];
 113         while let Some(def_id) = parent_defs.parent {
 114             parent_defs = tcx.generics_of(def_id);
 115             stack.push((def_id, parent_defs));
 116         }
 117
 118         // We manually build up the substitution, rather than using convenience
 119         // methods in `subst.rs`, so that we can iterate over the arguments and
 120         // parameters in lock-step linearly, instead of trying to match each pair.
 121         let mut substs: SmallVec<[subst::GenericArg<'tcx>; 8]> = SmallVec::with_capacity(count);
 122         // Iterate over each segment of the path.
 123         while let Some((def_id, defs)) = stack.pop() {
 124             let mut params = defs.params.iter().peekable();
 125
 126             // If we have already computed substitutions for parents, we can use those directly.
 127             while let Some(&param) = params.peek() {
 128                 if let Some(&kind) = parent_substs.get(param.index as usize) {
 129                     substs.push(kind);
 130                     params.next();
 131                 } else {
 132                     break;
 133                 }
 134             }
 135
 136             // `Self` is handled first, unless it's been handled in `parent_substs`.
 137             if has_self {
 138                 if let Some(&param) = params.peek() {
 139                     if param.index == 0 {
 140                         if let GenericParamDefKind::Type { .. } = param.kind {
 141                             substs.push(
 142                                 self_ty
 143                                     .map(|ty| ty.into())
 144                                     .unwrap_or_else(|| inferred_kind(None, param, true)),
 145                             );
 146                             params.next();
 147                         }
 148                     }
 149                 }
 150             }
 151
 152             // Check whether this segment takes generic arguments and the user has provided any.
 153             let (generic_args, infer_args) = args_for_def_id(def_id);
 154
 155             let mut args =
 156                 generic_args.iter().flat_map(|generic_args| generic_args.args.iter()).peekable();
 157
 158             // If we encounter a type or const when we expect a lifetime, we infer the lifetimes.
 159             // If we later encounter a lifetime, we know that the arguments were provided in the
 160             // wrong order. `force_infer_lt` records the type or const that forced lifetimes to be
 161             // inferred, so we can use it for diagnostics later.
 162             let mut force_infer_lt = None;
 163
 164             loop {
 165                 // We're going to iterate through the generic arguments that the user
 166                 // provided, matching them with the generic parameters we expect.
 167                 // Mismatches can occur as a result of elided lifetimes, or for malformed
 168                 // input. We try to handle both sensibly.
 169                 match (args.peek(), params.peek()) {
 170                     (Some(&arg), Some(&param)) => {
 171                         match (arg, &param.kind, arg_count.explicit_late_bound) {
 172                             (GenericArg::Lifetime(_), GenericParamDefKind::Lifetime, _)
 173                             | (GenericArg::Type(_), GenericParamDefKind::Type { .. }, _)
 174                             | (GenericArg::Const(_), GenericParamDefKind::Const, _) => {
 175                                 substs.push(provided_kind(param, arg));
 176                                 args.next();
 177                                 params.next();
 178                             }
 179                             (
 180                                 GenericArg::Type(_) | GenericArg::Const(_),
 181                                 GenericParamDefKind::Lifetime,
 182                                 _,
 183                             ) => {
 184                                 // We expected a lifetime argument, but got a type or const
 185                                 // argument. That means we're inferring the lifetimes.
 186                                 substs.push(inferred_kind(None, param, infer_args));
 187                                 force_infer_lt = Some(arg);
 188                                 params.next();
 189                             }
 190                             (GenericArg::Lifetime(_), _, ExplicitLateBound::Yes) => {
 191                                 // We've come across a lifetime when we expected something else in
 192                                 // the presence of explicit late bounds. This is most likely
 193                                 // due to the presence of the explicit bound so we're just going to
 194                                 // ignore it.
 195                                 args.next();
 196                             }
 197                             (_, kind, _) => {
 198                                 // We expected one kind of parameter, but the user provided
 199                                 // another. This is an error. However, if we already know that
 200                                 // the arguments don't match up with the parameters, we won't issue
 201                                 // an additional error, as the user already knows what's wrong.
 202                                 if arg_count.correct.is_ok()
 203                                     && arg_count.explicit_late_bound == ExplicitLateBound::No
 204                                 {
 205                                     // We're going to iterate over the parameters to sort them out, and
 206                                     // show that order to the user as a possible order for the parameters
 207                                     let mut param_types_present = defs
 208                                         .params
 209                                         .clone()
 210                                         .into_iter()
 211                                         .map(|param| {
 212                                             (
 213                                                 match param.kind {
 214                                                     GenericParamDefKind::Lifetime => {
 215                                                         ParamKindOrd::Lifetime
 216                                                     }
 217                                                     GenericParamDefKind::Type { .. } => {
 218                                                         ParamKindOrd::Type
 219                                                     }
 220                                                     GenericParamDefKind::Const => {
 221                                                         ParamKindOrd::Const {
 222                                                             unordered: tcx
 223                                                                 .sess
 224                                                                 .features_untracked()
 225                                                                 .const_generics,
 226                                                         }
 227                                                     }
 228                                                 },
 229                                                 param,
 230                                             )
 231                                         })
 232                                         .collect::<Vec<(ParamKindOrd, GenericParamDef)>>();
 233                                     param_types_present.sort_by_key(|(ord, _)| *ord);
 234                                     let (mut param_types_present, ordered_params): (
 235                                         Vec<ParamKindOrd>,
 236                                         Vec<GenericParamDef>,
 237                                     ) = param_types_present.into_iter().unzip();
 238                                     param_types_present.dedup();
 239
 240                                     Self::generic_arg_mismatch_err(
 241                                         tcx.sess,
 242                                         arg,
 243                                         kind.descr(),
 244                                         Some(&format!(
 245                                             "reorder the arguments: {}: `<{}>`",
 246                                             param_types_present
 247                                                 .into_iter()
 248                                                 .map(|ord| format!("{}s", ord.to_string()))
 249                                                 .collect::<Vec<String>>()
 250                                                 .join(", then "),
 251                                             ordered_params
 252                                                 .into_iter()
 253                                                 .filter_map(|param| {
 254                                                     if param.name == kw::SelfUpper {
 255                                                         None
 256                                                     } else {
 257                                                         Some(param.name.to_string())
 258                                                     }
 259                                                 })
 260                                                 .collect::<Vec<String>>()
 261                                                 .join(", ")
 262                                         )),
 263                                     );
 264                                 }
 265
 266                                 // We've reported the error, but we want to make sure that this
 267                                 // problem doesn't bubble down and create additional, irrelevant
 268                                 // errors. In this case, we're simply going to ignore the argument
 269                                 // and any following arguments. The rest of the parameters will be
 270                                 // inferred.
 271                                 while args.next().is_some() {}
 272                             }
 273                         }
 274                     }
 275
 276                     (Some(&arg), None) => {
 277                         // We should never be able to reach this point with well-formed input.
 278                         // There are three situations in which we can encounter this issue.
 279                         //
 280                         //  1.  The number of arguments is incorrect. In this case, an error
 281                         //      will already have been emitted, and we can ignore it.
 282                         //  2.  There are late-bound lifetime parameters present, yet the
 283                         //      lifetime arguments have also been explicitly specified by the
 284                         //      user.
 285                         //  3.  We've inferred some lifetimes, which have been provided later (i.e.
 286                         //      after a type or const). We want to throw an error in this case.
 287
 288                         if arg_count.correct.is_ok()
 289                             && arg_count.explicit_late_bound == ExplicitLateBound::No
 290                         {
 291                             let kind = arg.descr();
 292                             assert_eq!(kind, "lifetime");
 293                             let provided =
 294                                 force_infer_lt.expect("lifetimes ought to have been inferred");
 295                             Self::generic_arg_mismatch_err(tcx.sess, provided, kind, None);
 296                         }
 297
 298                         break;
 299                     }
 300
 301                     (None, Some(&param)) => {
 302                         // If there are fewer arguments than parameters, it means
 303                         // we're inferring the remaining arguments.
 304                         substs.push(inferred_kind(Some(&substs), param, infer_args));
 305                         params.next();
 306                     }
 307
 308                     (None, None) => break,
 309                 }
 310             }
 311         }
 312
 313         tcx.intern_substs(&substs)
 314     }
 315
 316     /// Checks that the correct number of generic arguments have been provided.
 317     /// Used specifically for function calls.
 318     pub fn check_generic_arg_count_for_call(
 319         tcx: TyCtxt<'_>,
 320         span: Span,
 321         def: &ty::Generics,
 322         seg: &hir::PathSegment<'_>,
 323         is_method_call: bool,
 324     ) -> GenericArgCountResult {
 325         let empty_args = hir::GenericArgs::none();
 326         let suppress_mismatch = Self::check_impl_trait(tcx, seg, &def);
 327         Self::check_generic_arg_count(
 328             tcx,
 329             span,
 330             def,
 331             if let Some(ref args) = seg.args { args } else { &empty_args },
 332             if is_method_call { GenericArgPosition::MethodCall } else { GenericArgPosition::Value },
 333             def.parent.is_none() && def.has_self, // `has_self`
 334             seg.infer_args || suppress_mismatch,  // `infer_args`
 335         )
 336     }
 337
 338     /// Checks that the correct number of generic arguments have been provided.
 339     /// This is used both for datatypes and function calls.
 340     pub(crate) fn check_generic_arg_count(
 341         tcx: TyCtxt<'_>,
 342         span: Span,
 343         def: &ty::Generics,
 344         args: &hir::GenericArgs<'_>,
 345         position: GenericArgPosition,
 346         has_self: bool,
 347         infer_args: bool,
 348     ) -> GenericArgCountResult {
 349         // At this stage we are guaranteed that the generic arguments are in the correct order, e.g.
 350         // that lifetimes will proceed types. So it suffices to check the number of each generic
 351         // arguments in order to validate them with respect to the generic parameters.
 352         let param_counts = def.own_counts();
 353         let arg_counts = args.own_counts();
 354         let infer_lifetimes = position != GenericArgPosition::Type && arg_counts.lifetimes == 0;
 355
 356         let mut defaults: ty::GenericParamCount = Default::default();
 357         for param in &def.params {
 358             match param.kind {
 359                 GenericParamDefKind::Lifetime => {}
 360                 GenericParamDefKind::Type { has_default, .. } => {
 361                     defaults.types += has_default as usize
 362                 }
 363                 GenericParamDefKind::Const => {
 364                     // FIXME(const_generics:defaults)
 365                 }
 366             };
 367         }
 368
 369         if position != GenericArgPosition::Type && !args.bindings.is_empty() {
 370             Self::prohibit_assoc_ty_binding(tcx, args.bindings[0].span);
 371         }
 372
 373         let explicit_late_bound =
 374             Self::prohibit_explicit_late_bound_lifetimes(tcx, def, args, position);
 375
 376         let check_kind_count = |kind,
 377                                 required,
 378                                 permitted,
 379                                 provided,
 380                                 offset,
 381                                 unexpected_spans: &mut Vec<Span>,
 382                                 silent| {
 383             debug!(
 384                 "check_kind_count: kind: {} required: {} permitted: {} provided: {} offset: {}",
 385                 kind, required, permitted, provided, offset
 386             );
 387             // We enforce the following: `required` <= `provided` <= `permitted`.
 388             // For kinds without defaults (e.g.., lifetimes), `required == permitted`.
 389             // For other kinds (i.e., types), `permitted` may be greater than `required`.
 390             if required <= provided && provided <= permitted {
 391                 return Ok(());
 392             }
 393
 394             if silent {
 395                 return Err(true);
 396             }
 397
 398             // Unfortunately lifetime and type parameter mismatches are typically styled
 399             // differently in diagnostics, which means we have a few cases to consider here.
 400             let (bound, quantifier) = if required != permitted {
 401                 if provided < required {
 402                     (required, "at least ")
 403                 } else {
 404                     // provided > permitted
 405                     (permitted, "at most ")
 406                 }
 407             } else {
 408                 (required, "")
 409             };
 410
 411             let (spans, label) = if required == permitted && provided > permitted {
 412                 // In the case when the user has provided too many arguments,
 413                 // we want to point to the unexpected arguments.
 414                 let spans: Vec<Span> = args.args[offset + permitted..offset + provided]
 415                     .iter()
 416                     .map(|arg| arg.span())
 417                     .collect();
 418                 unexpected_spans.extend(spans.clone());
 419                 (spans, format!("unexpected {} argument", kind))
 420             } else {
 421                 (
 422                     vec![span],
 423                     format!(
 424                         "expected {}{} {} argument{}",
 425                         quantifier,
 426                         bound,
 427                         kind,
 428                         pluralize!(bound),
 429                     ),
 430                 )
 431             };
 432
 433             let mut err = tcx.sess.struct_span_err_with_code(
 434                 spans.clone(),
 435                 &format!(
 436                     "wrong number of {} arguments: expected {}{}, found {}",
 437                     kind, quantifier, bound, provided,
 438                 ),
 439                 DiagnosticId::Error("E0107".into()),
 440             );
 441             for span in spans {
 442                 err.span_label(span, label.as_str());
 443             }
 444             err.emit();
 445
 446             Err(true)
 447         };
 448
 449         let mut arg_count_correct = Ok(());
 450         let mut unexpected_spans = vec![];
 451
 452         if !infer_lifetimes || arg_counts.lifetimes > param_counts.lifetimes {
 453             arg_count_correct = check_kind_count(
 454                 "lifetime",
 455                 param_counts.lifetimes,
 456                 param_counts.lifetimes,
 457                 arg_counts.lifetimes,
 458                 0,
 459                 &mut unexpected_spans,
 460                 explicit_late_bound == ExplicitLateBound::Yes,
 461             )
 462             .and(arg_count_correct);
 463         }
 464         // FIXME(const_generics:defaults)
 465         if !infer_args || arg_counts.consts > param_counts.consts {
 466             arg_count_correct = check_kind_count(
 467                 "const",
 468                 param_counts.consts,
 469                 param_counts.consts,
 470                 arg_counts.consts,
 471                 arg_counts.lifetimes + arg_counts.types,
 472                 &mut unexpected_spans,
 473                 false,
 474             )
 475             .and(arg_count_correct);
 476         }
 477         // Note that type errors are currently be emitted *after* const errors.
 478         if !infer_args || arg_counts.types > param_counts.types - defaults.types - has_self as usize
 479         {
 480             arg_count_correct = check_kind_count(
 481                 "type",
 482                 param_counts.types - defaults.types - has_self as usize,
 483                 param_counts.types - has_self as usize,
 484                 arg_counts.types,
 485                 arg_counts.lifetimes,
 486                 &mut unexpected_spans,
 487                 false,
 488             )
 489             .and(arg_count_correct);
 490         }
 491
 492         GenericArgCountResult {
 493             explicit_late_bound,
 494             correct: arg_count_correct.map_err(|reported_err| GenericArgCountMismatch {
 495                 reported: if reported_err { Some(ErrorReported) } else { None },
 496                 invalid_args: unexpected_spans,
 497             }),
 498         }
 499     }
 500
 501     /// Report error if there is an explicit type parameter when using `impl Trait`.
 502     pub(crate) fn check_impl_trait(
 503         tcx: TyCtxt<'_>,
 504         seg: &hir::PathSegment<'_>,
 505         generics: &ty::Generics,
 506     ) -> bool {
 507         let explicit = !seg.infer_args;
 508         let impl_trait = generics.params.iter().any(|param| match param.kind {
 509             ty::GenericParamDefKind::Type {
 510                 synthetic: Some(hir::SyntheticTyParamKind::ImplTrait),
 511                 ..
 512             } => true,
 513             _ => false,
 514         });
 515
 516         if explicit && impl_trait {
 517             let spans = seg
 518                 .generic_args()
 519                 .args
 520                 .iter()
 521                 .filter_map(|arg| match arg {
 522                     GenericArg::Type(_) => Some(arg.span()),
 523                     _ => None,
 524                 })
 525                 .collect::<Vec<_>>();
 526
 527             let mut err = struct_span_err! {
 528                 tcx.sess,
 529                 spans.clone(),
 530                 E0632,
 531                 "cannot provide explicit generic arguments when `impl Trait` is \
 532                 used in argument position"
 533             };
 534
 535             for span in spans {
 536                 err.span_label(span, "explicit generic argument not allowed");
 537             }
 538
 539             err.emit();
 540         }
 541
 542         impl_trait
 543     }
 544
 545     /// Emits an error regarding forbidden type binding associations
 546     pub fn prohibit_assoc_ty_binding(tcx: TyCtxt<'_>, span: Span) {
 547         let mut err = struct_span_err!(
 548             tcx.sess,
 549             span,
 550             E0229,
 551             "associated type bindings are not allowed here"
 552         );
 553         err.span_label(span, "associated type not allowed here").emit();
 554     }
 555
 556     /// Prohibits explicit lifetime arguments if late-bound lifetime parameters
 557     /// are present. This is used both for datatypes and function calls.
 558     pub(crate) fn prohibit_explicit_late_bound_lifetimes(
 559         tcx: TyCtxt<'_>,
 560         def: &ty::Generics,
 561         args: &hir::GenericArgs<'_>,
 562         position: GenericArgPosition,
 563     ) -> ExplicitLateBound {
 564         let param_counts = def.own_counts();
 565         let arg_counts = args.own_counts();
 566         let infer_lifetimes = position != GenericArgPosition::Type && arg_counts.lifetimes == 0;
 567
 568         if infer_lifetimes {
 569             ExplicitLateBound::No
 570         } else if let Some(span_late) = def.has_late_bound_regions {
 571             let msg = "cannot specify lifetime arguments explicitly \
 572                        if late bound lifetime parameters are present";
 573             let note = "the late bound lifetime parameter is introduced here";
 574             let span = args.args[0].span();
 575             if position == GenericArgPosition::Value
 576                 && arg_counts.lifetimes != param_counts.lifetimes
 577             {
 578                 let mut err = tcx.sess.struct_span_err(span, msg);
 579                 err.span_note(span_late, note);
 580                 err.emit();
 581             } else {
 582                 let mut multispan = MultiSpan::from_span(span);
 583                 multispan.push_span_label(span_late, note.to_string());
 584                 tcx.struct_span_lint_hir(
 585                     LATE_BOUND_LIFETIME_ARGUMENTS,
 586                     args.args[0].id(),
 587                     multispan,
 588                     |lint| lint.build(msg).emit(),
 589                 );
 590             }
 591             ExplicitLateBound::Yes
 592         } else {
 593             ExplicitLateBound::No
 594         }
 595     }
 596 }