rustc_hir_analysis/variance/
terms.rs

Help
1// Representing terms
2//
3// Terms are structured as a straightforward tree. Rather than rely on
4// GC, we allocate terms out of a bounded arena (the lifetime of this
5// arena is the lifetime 'a that is threaded around).
6//
7// We assign a unique index to each type/region parameter whose variance
8// is to be inferred. We refer to such variables as "inferreds". An
9// `InferredIndex` is a newtype'd int representing the index of such
10// a variable.
11
12use std::fmt;
13
14use rustc_arena::DroplessArena;
15use rustc_hir::def::DefKind;
16use rustc_hir::def_id::{LocalDefId, LocalDefIdMap};
17use rustc_middle::ty::{self, TyCtxt};
18use tracing::debug;
19
20use self::VarianceTerm::*;
21
22pub(crate) type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
23
24#[derive(Copy, Clone, Debug)]
25pub(crate) struct InferredIndex(pub usize);
26
27#[derive(Copy, Clone)]
28pub(crate) enum VarianceTerm<'a> {
29    ConstantTerm(ty::Variance),
30    TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
31    InferredTerm(InferredIndex),
32}
33
34impl<'a> fmt::Debug for VarianceTerm<'a> {
35    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36        match *self {
37            ConstantTerm(c1) => write!(f, "{c1:?}"),
38            TransformTerm(v1, v2) => write!(f, "({v1:?} \u{00D7} {v2:?})"),
39            InferredTerm(id) => write!(f, "[{}]", {
40                let InferredIndex(i) = id;
41                i
42            }),
43        }
44    }
45}
46
47/// The first pass over the crate simply builds up the set of inferreds.
48
49pub(crate) struct TermsContext<'a, 'tcx> {
50    pub tcx: TyCtxt<'tcx>,
51    pub arena: &'a DroplessArena,
52
53    /// For marker types, `UnsafeCell`, and other lang items where
54    /// variance is hardcoded, records the item-id and the hardcoded
55    /// variance.
56    pub lang_items: Vec<(LocalDefId, Vec<ty::Variance>)>,
57
58    /// Maps from the node id of an item to the first inferred index
59    /// used for its type & region parameters.
60    pub inferred_starts: LocalDefIdMap<InferredIndex>,
61
62    /// Maps from an InferredIndex to the term for that variable.
63    pub inferred_terms: Vec<VarianceTermPtr<'a>>,
64}
65
66pub(crate) fn determine_parameters_to_be_inferred<'a, 'tcx>(
67    tcx: TyCtxt<'tcx>,
68    arena: &'a DroplessArena,
69) -> TermsContext<'a, 'tcx> {
70    let mut terms_cx = TermsContext {
71        tcx,
72        arena,
73        inferred_starts: Default::default(),
74        inferred_terms: vec![],
75
76        lang_items: lang_items(tcx),
77    };
78
79    // See the following for a discussion on dep-graph management.
80    //
81    // - https://rustc-dev-guide.rust-lang.org/query.html
82    // - https://rustc-dev-guide.rust-lang.org/variance.html
83    let crate_items = tcx.hir_crate_items(());
84
85    for def_id in crate_items.definitions() {
86        debug!("add_inferreds for item {:?}", def_id);
87
88        let def_kind = tcx.def_kind(def_id);
89
90        match def_kind {
91            DefKind::Struct | DefKind::Union | DefKind::Enum => {
92                terms_cx.add_inferreds_for_item(def_id);
93
94                let adt = tcx.adt_def(def_id);
95                for variant in adt.variants() {
96                    if let Some(ctor_def_id) = variant.ctor_def_id() {
97                        terms_cx.add_inferreds_for_item(ctor_def_id.expect_local());
98                    }
99                }
100            }
101            DefKind::Fn | DefKind::AssocFn => terms_cx.add_inferreds_for_item(def_id),
102            DefKind::TyAlias if tcx.type_alias_is_lazy(def_id) => {
103                terms_cx.add_inferreds_for_item(def_id)
104            }
105            _ => {}
106        }
107    }
108
109    terms_cx
110}
111
112fn lang_items(tcx: TyCtxt<'_>) -> Vec<(LocalDefId, Vec<ty::Variance>)> {
113    let lang_items = tcx.lang_items();
114    let all = [
115        (lang_items.phantom_data(), vec![ty::Covariant]),
116        (lang_items.unsafe_cell_type(), vec![ty::Invariant]),
117    ];
118
119    all.into_iter() // iterating over (Option<DefId>, Variance)
120        .filter_map(|(d, v)| {
121            let def_id = d?.as_local()?; // LocalDefId
122            Some((def_id, v))
123        })
124        .collect()
125}
126
127impl<'a, 'tcx> TermsContext<'a, 'tcx> {
128    fn add_inferreds_for_item(&mut self, def_id: LocalDefId) {
129        let tcx = self.tcx;
130        let count = tcx.generics_of(def_id).count();
131
132        if count == 0 {
133            return;
134        }
135
136        // Record the start of this item's inferreds.
137        let start = self.inferred_terms.len();
138        let newly_added = self.inferred_starts.insert(def_id, InferredIndex(start)).is_none();
139        assert!(newly_added);
140
141        // N.B., in the code below for writing the results back into the
142        // `CrateVariancesMap`, we rely on the fact that all inferreds
143        // for a particular item are assigned continuous indices.
144
145        let arena = self.arena;
146        self.inferred_terms.extend(
147            (start..(start + count)).map(|i| &*arena.alloc(InferredTerm(InferredIndex(i)))),
148        );
149    }
150}
rustc_hir_analysis/variance/terms.rs

rustc_hir_analysis/variance/
terms.rs
