rustc_hir_analysis/variance/
mod.rs

1//! Module for inferring the variance of type and lifetime parameters. See the [rustc dev guide]
2//! chapter for more info.
3//!
4//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/variance.html
5
6use itertools::Itertools;
7use rustc_arena::DroplessArena;
8use rustc_hir as hir;
9use rustc_hir::def::DefKind;
10use rustc_hir::def_id::{DefId, LocalDefId};
11use rustc_middle::span_bug;
12use rustc_middle::ty::{
13    self, CrateVariancesMap, GenericArgsRef, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable,
14    Unnormalized,
15};
16use tracing::{debug, instrument};
17
18/// Defines the `TermsContext` basically houses an arena where we can
19/// allocate terms.
20mod terms;
21
22/// Code to gather up constraints.
23mod constraints;
24
25/// Code to solve constraints and write out the results.
26mod solve;
27
28pub(crate) mod dump;
29
30pub(super) fn crate_variances(tcx: TyCtxt<'_>, (): ()) -> CrateVariancesMap<'_> {
31    let arena = DroplessArena::default();
32    let terms_cx = terms::determine_parameters_to_be_inferred(tcx, &arena);
33    let constraints_cx = constraints::add_constraints_from_crate(terms_cx);
34    solve::solve_constraints(constraints_cx)
35}
36
37pub(super) fn variances_of(tcx: TyCtxt<'_>, item_def_id: LocalDefId) -> &[ty::Variance] {
38    // Skip items with no generics - there's nothing to infer in them.
39    if tcx.generics_of(item_def_id).is_empty() {
40        return &[];
41    }
42
43    let kind = tcx.def_kind(item_def_id);
44    match kind {
45        DefKind::Fn
46        | DefKind::AssocFn
47        | DefKind::Enum
48        | DefKind::Struct
49        | DefKind::Union
50        | DefKind::Ctor(..) => {
51            // These are inferred.
52            let crate_map = tcx.crate_variances(());
53            return crate_map.variances.get(&item_def_id.to_def_id()).copied().unwrap_or(&[]);
54        }
55        DefKind::TyAlias if tcx.type_alias_is_lazy(item_def_id) => {
56            // These are inferred.
57            let crate_map = tcx.crate_variances(());
58            return crate_map.variances.get(&item_def_id.to_def_id()).copied().unwrap_or(&[]);
59        }
60        DefKind::AssocTy => match tcx.opt_rpitit_info(item_def_id.to_def_id()) {
61            Some(ty::ImplTraitInTraitData::Trait { opaque_def_id, .. }) => {
62                return variance_of_opaque(
63                    tcx,
64                    opaque_def_id.expect_local(),
65                    ForceCaptureTraitArgs::Yes,
66                );
67            }
68            None | Some(ty::ImplTraitInTraitData::Impl { .. }) => {}
69        },
70        DefKind::OpaqueTy => {
71            let force_capture_trait_args = if let hir::OpaqueTyOrigin::FnReturn {
72                parent: _,
73                in_trait_or_impl: Some(hir::RpitContext::Trait),
74            } =
75                tcx.hir_node_by_def_id(item_def_id).expect_opaque_ty().origin
76            {
77                ForceCaptureTraitArgs::Yes
78            } else {
79                ForceCaptureTraitArgs::No
80            };
81
82            return variance_of_opaque(tcx, item_def_id, force_capture_trait_args);
83        }
84        _ => {}
85    }
86
87    // Variance not relevant.
88    ::rustc_middle::util::bug::span_bug_fmt(tcx.def_span(item_def_id),
    format_args!("asked to compute variance for {0}",
        kind.descr(item_def_id.to_def_id())));span_bug!(
89        tcx.def_span(item_def_id),
90        "asked to compute variance for {}",
91        kind.descr(item_def_id.to_def_id())
92    );
93}
94
95#[derive(#[automatically_derived]
impl ::core::fmt::Debug for ForceCaptureTraitArgs {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::write_str(f,
            match self {
                ForceCaptureTraitArgs::Yes => "Yes",
                ForceCaptureTraitArgs::No => "No",
            })
    }
}Debug, #[automatically_derived]
impl ::core::marker::Copy for ForceCaptureTraitArgs { }Copy, #[automatically_derived]
impl ::core::clone::Clone for ForceCaptureTraitArgs {
    #[inline]
    fn clone(&self) -> ForceCaptureTraitArgs { *self }
}Clone)]
96enum ForceCaptureTraitArgs {
97    Yes,
98    No,
99}
100
101x;#[instrument(level = "trace", skip(tcx), ret)]
102fn variance_of_opaque(
103    tcx: TyCtxt<'_>,
104    item_def_id: LocalDefId,
105    force_capture_trait_args: ForceCaptureTraitArgs,
106) -> &[ty::Variance] {
107    let generics = tcx.generics_of(item_def_id);
108
109    // Opaque types may only use regions that are bound. So for
110    // ```rust
111    // type Foo<'a, 'b, 'c> = impl Trait<'a> + 'b;
112    // ```
113    // we may not use `'c` in the hidden type.
114    struct OpaqueTypeLifetimeCollector<'tcx> {
115        tcx: TyCtxt<'tcx>,
116        root_def_id: DefId,
117        variances: Vec<ty::Variance>,
118    }
119
120    impl<'tcx> OpaqueTypeLifetimeCollector<'tcx> {
121        #[instrument(level = "trace", skip(self), ret)]
122        fn visit_opaque(&mut self, def_id: DefId, args: GenericArgsRef<'tcx>) {
123            if def_id != self.root_def_id && self.tcx.is_descendant_of(def_id, self.root_def_id) {
124                let child_variances = self.tcx.variances_of(def_id);
125                for (a, v) in args.iter().zip_eq(child_variances) {
126                    if *v != ty::Bivariant {
127                        a.visit_with(self);
128                    }
129                }
130            } else {
131                args.visit_with(self)
132            }
133        }
134    }
135
136    impl<'tcx> ty::TypeVisitor<TyCtxt<'tcx>> for OpaqueTypeLifetimeCollector<'tcx> {
137        #[instrument(level = "trace", skip(self), ret)]
138        fn visit_region(&mut self, r: ty::Region<'tcx>) {
139            if let ty::RegionKind::ReEarlyParam(ebr) = r.kind() {
140                self.variances[ebr.index as usize] = ty::Invariant;
141            }
142        }
143
144        #[instrument(level = "trace", skip(self), ret)]
145        fn visit_ty(&mut self, t: Ty<'tcx>) {
146            match t.kind() {
147                ty::Alias(ty::AliasTy { kind: ty::Opaque { def_id }, args, .. }) => {
148                    self.visit_opaque(*def_id, args);
149                }
150                _ => t.super_visit_with(self),
151            }
152        }
153    }
154
155    // By default, RPIT are invariant wrt type and const generics, but they are bivariant wrt
156    // lifetime generics.
157    let mut variances = vec![ty::Invariant; generics.count()];
158
159    // Mark all lifetimes from parent generics as unused (Bivariant).
160    // This will be overridden later if required.
161    {
162        let mut generics = generics;
163        while let Some(def_id) = generics.parent {
164            generics = tcx.generics_of(def_id);
165
166            // Don't mark trait params generic if we're in an RPITIT.
167            if matches!(force_capture_trait_args, ForceCaptureTraitArgs::Yes)
168                && generics.parent.is_none()
169            {
170                debug_assert_eq!(tcx.def_kind(def_id), DefKind::Trait);
171                break;
172            }
173
174            for param in &generics.own_params {
175                match param.kind {
176                    ty::GenericParamDefKind::Lifetime => {
177                        variances[param.index as usize] = ty::Bivariant;
178                    }
179                    ty::GenericParamDefKind::Type { .. }
180                    | ty::GenericParamDefKind::Const { .. } => {}
181                }
182            }
183        }
184    }
185
186    let mut collector =
187        OpaqueTypeLifetimeCollector { tcx, root_def_id: item_def_id.to_def_id(), variances };
188    let id_args = ty::GenericArgs::identity_for_item(tcx, item_def_id);
189    for (pred, _) in tcx
190        .explicit_item_bounds(item_def_id)
191        .iter_instantiated_copied(tcx, id_args)
192        .map(Unnormalized::skip_norm_wip)
193    {
194        debug!(?pred);
195
196        // We only ignore opaque type args if the opaque type is the outermost type.
197        // The opaque type may be nested within itself via recursion in e.g.
198        // type Foo<'a> = impl PartialEq<Foo<'a>>;
199        // which thus mentions `'a` and should thus accept hidden types that borrow 'a
200        // instead of requiring an additional `+ 'a`.
201        match pred.kind().skip_binder() {
202            ty::ClauseKind::Trait(ty::TraitPredicate {
203                trait_ref: ty::TraitRef { def_id: _, args, .. },
204                polarity: _,
205            })
206            | ty::ClauseKind::HostEffect(ty::HostEffectPredicate {
207                trait_ref: ty::TraitRef { def_id: _, args, .. },
208                constness: _,
209            }) => {
210                for arg in &args[1..] {
211                    arg.visit_with(&mut collector);
212                }
213            }
214            ty::ClauseKind::Projection(ty::ProjectionPredicate {
215                projection_term: ty::AliasTerm { args, .. },
216                term,
217            }) => {
218                for arg in &args[1..] {
219                    arg.visit_with(&mut collector);
220                }
221                term.visit_with(&mut collector);
222            }
223            ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(_, region)) => {
224                region.visit_with(&mut collector);
225            }
226            _ => {
227                pred.visit_with(&mut collector);
228            }
229        }
230    }
231    tcx.arena.alloc_from_iter(collector.variances)
232}
rustc_hir_analysis/variance/mod.rs

rustc_hir_analysis/variance/
mod.rs
