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