1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
//! # Minimal Specialization
//!
//! This module contains the checks for sound specialization used when the
//! `min_specialization` feature is enabled. This requires that the impl is
//! *always applicable*.
//!
//! If `impl1` specializes `impl2` then `impl1` is always applicable if we know
//! that all the bounds of `impl2` are satisfied, and all of the bounds of
//! `impl1` are satisfied for some choice of lifetimes then we know that
//! `impl1` applies for any choice of lifetimes.
//!
//! ## Basic approach
//!
//! To enforce this requirement on specializations we take the following
//! approach:
//!
//! 1. Match up the args for `impl2` so that the implemented trait and
//!    self-type match those for `impl1`.
//! 2. Check for any direct use of `'static` in the args of `impl2`.
//! 3. Check that all of the generic parameters of `impl1` occur at most once
//!    in the *unconstrained* args for `impl2`. A parameter is constrained if
//!    its value is completely determined by an associated type projection
//!    predicate.
//! 4. Check that all predicates on `impl1` either exist on `impl2` (after
//!    matching args), or are well-formed predicates for the trait's type
//!    arguments.
//!
//! ## Example
//!
//! Suppose we have the following always applicable impl:
//!
//! ```ignore (illustrative)
//! impl<T> SpecExtend<T> for std::vec::IntoIter<T> { /* specialized impl */ }
//! impl<T, I: Iterator<Item=T>> SpecExtend<T> for I { /* default impl */ }
//! ```
//!
//! We get that the subst for `impl2` are `[T, std::vec::IntoIter<T>]`. `T` is
//! constrained to be `<I as Iterator>::Item`, so we check only
//! `std::vec::IntoIter<T>` for repeated parameters, which it doesn't have. The
//! predicates of `impl1` are only `T: Sized`, which is also a predicate of
//! `impl2`. So this specialization is sound.
//!
//! ## Extensions
//!
//! Unfortunately not all specializations in the standard library are allowed
//! by this. So there are two extensions to these rules that allow specializing
//! on some traits: that is, using them as bounds on the specializing impl,
//! even when they don't occur in the base impl.
//!
//! ### rustc_specialization_trait
//!
//! If a trait is always applicable, then it's sound to specialize on it. We
//! check trait is always applicable in the same way as impls, except that step
//! 4 is now "all predicates on `impl1` are always applicable". We require that
//! `specialization` or `min_specialization` is enabled to implement these
//! traits.
//!
//! ### rustc_unsafe_specialization_marker
//!
//! There are also some specialization on traits with no methods, including the
//! stable `FusedIterator` trait. We allow marking marker traits with an
//! unstable attribute that means we ignore them in point 3 of the checks
//! above. This is unsound, in the sense that the specialized impl may be used
//! when it doesn't apply, but we allow it in the short term since it can't
//! cause use after frees with purely safe code in the same way as specializing
//! on traits with methods can.

use crate::errors::SubstsOnOverriddenImpl;
use crate::{constrained_generic_params as cgp, errors};

use rustc_data_structures::fx::FxHashSet;
use rustc_hir as hir;
use rustc_hir::def_id::{DefId, LocalDefId};
use rustc_infer::infer::outlives::env::OutlivesEnvironment;
use rustc_infer::infer::TyCtxtInferExt;
use rustc_infer::traits::specialization_graph::Node;
use rustc_middle::ty::trait_def::TraitSpecializationKind;
use rustc_middle::ty::{self, TyCtxt, TypeVisitableExt};
use rustc_middle::ty::{GenericArg, GenericArgs, GenericArgsRef};
use rustc_span::{ErrorGuaranteed, Span};
use rustc_trait_selection::traits::error_reporting::TypeErrCtxtExt;
use rustc_trait_selection::traits::outlives_bounds::InferCtxtExt as _;
use rustc_trait_selection::traits::{self, translate_args_with_cause, wf, ObligationCtxt};

pub(super) fn check_min_specialization(tcx: TyCtxt<'_>, impl_def_id: LocalDefId) {
    if let Some(node) = parent_specialization_node(tcx, impl_def_id) {
        check_always_applicable(tcx, impl_def_id, node);
    }
}

fn parent_specialization_node(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId) -> Option<Node> {
    let trait_ref = tcx.impl_trait_ref(impl1_def_id)?;
    let trait_def = tcx.trait_def(trait_ref.skip_binder().def_id);

    let impl2_node = trait_def.ancestors(tcx, impl1_def_id.to_def_id()).ok()?.nth(1)?;

    let always_applicable_trait =
        matches!(trait_def.specialization_kind, TraitSpecializationKind::AlwaysApplicable);
    if impl2_node.is_from_trait() && !always_applicable_trait {
        // Implementing a normal trait isn't a specialization.
        return None;
    }
    if trait_def.is_marker {
        // Overlapping marker implementations are not really specializations.
        return None;
    }
    Some(impl2_node)
}

/// Check that `impl1` is a sound specialization
#[instrument(level = "debug", skip(tcx))]
fn check_always_applicable(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId, impl2_node: Node) {
    let span = tcx.def_span(impl1_def_id);
    check_has_items(tcx, impl1_def_id, impl2_node, span);

    if let Ok((impl1_args, impl2_args)) = get_impl_args(tcx, impl1_def_id, impl2_node) {
        let impl2_def_id = impl2_node.def_id();
        debug!(?impl2_def_id, ?impl2_args);

        let parent_args = if impl2_node.is_from_trait() {
            impl2_args.to_vec()
        } else {
            unconstrained_parent_impl_args(tcx, impl2_def_id, impl2_args)
        };

        check_constness(tcx, impl1_def_id, impl2_node, span);
        check_static_lifetimes(tcx, &parent_args, span);
        check_duplicate_params(tcx, impl1_args, &parent_args, span);
        check_predicates(tcx, impl1_def_id, impl1_args, impl2_node, impl2_args, span);
    }
}

fn check_has_items(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId, impl2_node: Node, span: Span) {
    if let Node::Impl(impl2_id) = impl2_node && tcx.associated_item_def_ids(impl1_def_id).is_empty() {
        let base_impl_span = tcx.def_span(impl2_id);
        tcx.sess.emit_err(errors::EmptySpecialization { span, base_impl_span });
    }
}

/// Check that the specializing impl `impl1` is at least as const as the base
/// impl `impl2`
fn check_constness(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId, impl2_node: Node, span: Span) {
    if impl2_node.is_from_trait() {
        // This isn't a specialization
        return;
    }

    let impl1_constness = tcx.constness(impl1_def_id.to_def_id());
    let impl2_constness = tcx.constness(impl2_node.def_id());

    if let hir::Constness::Const = impl2_constness {
        if let hir::Constness::NotConst = impl1_constness {
            tcx.sess.emit_err(errors::ConstSpecialize { span });
        }
    }
}

/// Given a specializing impl `impl1`, and the base impl `impl2`, returns two
/// substitutions `(S1, S2)` that equate their trait references. The returned
/// types are expressed in terms of the generics of `impl1`.
///
/// Example
///
/// ```ignore (illustrative)
/// impl<A, B> Foo<A> for B { /* impl2 */ }
/// impl<C> Foo<Vec<C>> for C { /* impl1 */ }
/// ```
///
/// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`.
fn get_impl_args(
    tcx: TyCtxt<'_>,
    impl1_def_id: LocalDefId,
    impl2_node: Node,
) -> Result<(GenericArgsRef<'_>, GenericArgsRef<'_>), ErrorGuaranteed> {
    let infcx = &tcx.infer_ctxt().build();
    let ocx = ObligationCtxt::new(infcx);
    let param_env = tcx.param_env(impl1_def_id);
    let impl1_span = tcx.def_span(impl1_def_id);
    let assumed_wf_types = ocx.assumed_wf_types_and_report_errors(param_env, impl1_def_id)?;

    let impl1_args = GenericArgs::identity_for_item(tcx, impl1_def_id);
    let impl2_args = translate_args_with_cause(
        infcx,
        param_env,
        impl1_def_id.to_def_id(),
        impl1_args,
        impl2_node,
        |_, span| {
            traits::ObligationCause::new(
                impl1_span,
                impl1_def_id,
                traits::ObligationCauseCode::BindingObligation(impl2_node.def_id(), span),
            )
        },
    );

    let errors = ocx.select_all_or_error();
    if !errors.is_empty() {
        let guar = ocx.infcx.err_ctxt().report_fulfillment_errors(&errors);
        return Err(guar);
    }

    let implied_bounds = infcx.implied_bounds_tys(param_env, impl1_def_id, assumed_wf_types);
    let outlives_env = OutlivesEnvironment::with_bounds(param_env, implied_bounds);
    let _ = ocx.resolve_regions_and_report_errors(impl1_def_id, &outlives_env);
    let Ok(impl2_args) = infcx.fully_resolve(impl2_args) else {
        let span = tcx.def_span(impl1_def_id);
        let guar = tcx.sess.emit_err(SubstsOnOverriddenImpl { span });
        return Err(guar);
    };
    Ok((impl1_args, impl2_args))
}

/// Returns a list of all of the unconstrained subst of the given impl.
///
/// For example given the impl:
///
/// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T>
///
/// This would return the args corresponding to `['a, I]`, because knowing
/// `'a` and `I` determines the value of `T`.
fn unconstrained_parent_impl_args<'tcx>(
    tcx: TyCtxt<'tcx>,
    impl_def_id: DefId,
    impl_args: GenericArgsRef<'tcx>,
) -> Vec<GenericArg<'tcx>> {
    let impl_generic_predicates = tcx.predicates_of(impl_def_id);
    let mut unconstrained_parameters = FxHashSet::default();
    let mut constrained_params = FxHashSet::default();
    let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).map(ty::EarlyBinder::instantiate_identity);

    // Unfortunately the functions in `constrained_generic_parameters` don't do
    // what we want here. We want only a list of constrained parameters while
    // the functions in `cgp` add the constrained parameters to a list of
    // unconstrained parameters.
    for (clause, _) in impl_generic_predicates.predicates.iter() {
        if let ty::ClauseKind::Projection(proj) = clause.kind().skip_binder() {
            let projection_ty = proj.projection_ty;
            let projected_ty = proj.term;

            let unbound_trait_ref = projection_ty.trait_ref(tcx);
            if Some(unbound_trait_ref) == impl_trait_ref {
                continue;
            }

            unconstrained_parameters.extend(cgp::parameters_for(&projection_ty, true));

            for param in cgp::parameters_for(&projected_ty, false) {
                if !unconstrained_parameters.contains(&param) {
                    constrained_params.insert(param.0);
                }
            }

            unconstrained_parameters.extend(cgp::parameters_for(&projected_ty, true));
        }
    }

    impl_args
        .iter()
        .enumerate()
        .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32)))
        .map(|(_, arg)| arg)
        .collect()
}

/// Check that parameters of the derived impl don't occur more than once in the
/// equated args of the base impl.
///
/// For example forbid the following:
///
/// ```ignore (illustrative)
/// impl<A> Tr for A { }
/// impl<B> Tr for (B, B) { }
/// ```
///
/// Note that only consider the unconstrained parameters of the base impl:
///
/// ```ignore (illustrative)
/// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { }
/// impl<T> Tr<T> for Vec<T> { }
/// ```
///
/// The args for the parent impl here are `[T, Vec<T>]`, which repeats `T`,
/// but `S` is constrained in the parent impl, so `parent_args` is only
/// `[Vec<T>]`. This means we allow this impl.
fn check_duplicate_params<'tcx>(
    tcx: TyCtxt<'tcx>,
    impl1_args: GenericArgsRef<'tcx>,
    parent_args: &Vec<GenericArg<'tcx>>,
    span: Span,
) {
    let mut base_params = cgp::parameters_for(parent_args, true);
    base_params.sort_by_key(|param| param.0);
    if let (_, [duplicate, ..]) = base_params.partition_dedup() {
        let param = impl1_args[duplicate.0 as usize];
        tcx.sess
            .struct_span_err(span, format!("specializing impl repeats parameter `{param}`"))
            .emit();
    }
}

/// Check that `'static` lifetimes are not introduced by the specializing impl.
///
/// For example forbid the following:
///
/// ```ignore (illustrative)
/// impl<A> Tr for A { }
/// impl Tr for &'static i32 { }
/// ```
fn check_static_lifetimes<'tcx>(
    tcx: TyCtxt<'tcx>,
    parent_args: &Vec<GenericArg<'tcx>>,
    span: Span,
) {
    if tcx.any_free_region_meets(parent_args, |r| r.is_static()) {
        tcx.sess.emit_err(errors::StaticSpecialize { span });
    }
}

/// Check whether predicates on the specializing impl (`impl1`) are allowed.
///
/// Each predicate `P` must be one of:
///
/// * Global (not reference any parameters).
/// * A `T: Tr` predicate where `Tr` is an always-applicable trait.
/// * Present on the base impl `impl2`.
///     * This check is done using the `trait_predicates_eq` function below.
/// * A well-formed predicate of a type argument of the trait being implemented,
///   including the `Self`-type.
#[instrument(level = "debug", skip(tcx))]
fn check_predicates<'tcx>(
    tcx: TyCtxt<'tcx>,
    impl1_def_id: LocalDefId,
    impl1_args: GenericArgsRef<'tcx>,
    impl2_node: Node,
    impl2_args: GenericArgsRef<'tcx>,
    span: Span,
) {
    let impl1_predicates: Vec<_> = traits::elaborate(
        tcx,
        tcx.predicates_of(impl1_def_id).instantiate(tcx, impl1_args).into_iter(),
    )
    .collect();

    let mut impl2_predicates = if impl2_node.is_from_trait() {
        // Always applicable traits have to be always applicable without any
        // assumptions.
        Vec::new()
    } else {
        traits::elaborate(
            tcx,
            tcx.predicates_of(impl2_node.def_id())
                .instantiate(tcx, impl2_args)
                .into_iter()
                .map(|(c, _s)| c.as_predicate()),
        )
        .collect()
    };
    debug!(?impl1_predicates, ?impl2_predicates);

    // Since impls of always applicable traits don't get to assume anything, we
    // can also assume their supertraits apply.
    //
    // For example, we allow:
    //
    // #[rustc_specialization_trait]
    // trait AlwaysApplicable: Debug { }
    //
    // impl<T> Tr for T { }
    // impl<T: AlwaysApplicable> Tr for T { }
    //
    // Specializing on `AlwaysApplicable` allows also specializing on `Debug`
    // which is sound because we forbid impls like the following
    //
    // impl<D: Debug> AlwaysApplicable for D { }
    let always_applicable_traits = impl1_predicates
        .iter()
        .copied()
        .filter(|&(clause, _span)| {
            matches!(
                trait_specialization_kind(tcx, clause),
                Some(TraitSpecializationKind::AlwaysApplicable)
            )
        })
        .map(|(c, _span)| c.as_predicate());

    // Include the well-formed predicates of the type parameters of the impl.
    for arg in tcx.impl_trait_ref(impl1_def_id).unwrap().instantiate_identity().args {
        let infcx = &tcx.infer_ctxt().build();
        let obligations =
            wf::obligations(infcx, tcx.param_env(impl1_def_id), impl1_def_id, 0, arg, span)
                .unwrap();

        assert!(!obligations.has_infer());
        impl2_predicates
            .extend(traits::elaborate(tcx, obligations).map(|obligation| obligation.predicate))
    }
    impl2_predicates.extend(traits::elaborate(tcx, always_applicable_traits));

    for (clause, span) in impl1_predicates {
        if !impl2_predicates
            .iter()
            .any(|pred2| trait_predicates_eq(tcx, clause.as_predicate(), *pred2, span))
        {
            check_specialization_on(tcx, clause, span)
        }
    }
}

/// Checks if some predicate on the specializing impl (`predicate1`) is the same
/// as some predicate on the base impl (`predicate2`).
///
/// This basically just checks syntactic equivalence, but is a little more
/// forgiving since we want to equate `T: Tr` with `T: ~const Tr` so this can work:
///
/// ```ignore (illustrative)
/// #[rustc_specialization_trait]
/// trait Specialize { }
///
/// impl<T: Bound> Tr for T { }
/// impl<T: ~const Bound + Specialize> const Tr for T { }
/// ```
///
/// However, we *don't* want to allow the reverse, i.e., when the bound on the
/// specializing impl is not as const as the bound on the base impl:
///
/// ```ignore (illustrative)
/// impl<T: ~const Bound> const Tr for T { }
/// impl<T: Bound + Specialize> const Tr for T { } // should be T: ~const Bound
/// ```
///
/// So we make that check in this function and try to raise a helpful error message.
fn trait_predicates_eq<'tcx>(
    _tcx: TyCtxt<'tcx>,
    predicate1: ty::Predicate<'tcx>,
    predicate2: ty::Predicate<'tcx>,
    _span: Span,
) -> bool {
    // FIXME(effects)
    predicate1 == predicate2
}

#[instrument(level = "debug", skip(tcx))]
fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, clause: ty::Clause<'tcx>, span: Span) {
    match clause.kind().skip_binder() {
        // Global predicates are either always true or always false, so we
        // are fine to specialize on.
        _ if clause.is_global() => (),
        // We allow specializing on explicitly marked traits with no associated
        // items.
        ty::ClauseKind::Trait(ty::TraitPredicate { trait_ref, polarity: _ }) => {
            if !matches!(
                trait_specialization_kind(tcx, clause),
                Some(TraitSpecializationKind::Marker)
            ) {
                tcx.sess
                    .struct_span_err(
                        span,
                        format!(
                            "cannot specialize on trait `{}`",
                            tcx.def_path_str(trait_ref.def_id),
                        ),
                    )
                    .emit();
            }
        }
        ty::ClauseKind::Projection(ty::ProjectionPredicate { projection_ty, term }) => {
            tcx.sess
                .struct_span_err(
                    span,
                    format!("cannot specialize on associated type `{projection_ty} == {term}`",),
                )
                .emit();
        }
        ty::ClauseKind::ConstArgHasType(..) => {
            // FIXME(min_specialization), FIXME(const_generics):
            // It probably isn't right to allow _every_ `ConstArgHasType` but I am somewhat unsure
            // about the actual rules that would be sound. Can't just always error here because otherwise
            // std/core doesn't even compile as they have `const N: usize` in some specializing impls.
            //
            // While we do not support constructs like `<T, const N: T>` there is probably no risk of
            // soundness bugs, but when we support generic const parameter types this will need to be
            // revisited.
        }
        _ => {
            tcx.sess
                .struct_span_err(span, format!("cannot specialize on predicate `{clause}`"))
                .emit();
        }
    }
}

fn trait_specialization_kind<'tcx>(
    tcx: TyCtxt<'tcx>,
    clause: ty::Clause<'tcx>,
) -> Option<TraitSpecializationKind> {
    match clause.kind().skip_binder() {
        ty::ClauseKind::Trait(ty::TraitPredicate { trait_ref, polarity: _ }) => {
            Some(tcx.trait_def(trait_ref.def_id).specialization_kind)
        }
        ty::ClauseKind::RegionOutlives(_)
        | ty::ClauseKind::TypeOutlives(_)
        | ty::ClauseKind::Projection(_)
        | ty::ClauseKind::ConstArgHasType(..)
        | ty::ClauseKind::WellFormed(_)
        | ty::ClauseKind::ConstEvaluatable(..) => None,
    }
}