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

rustc_hir_analysis/variance/
mod.rs
