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).
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
12 use rustc_arena::DroplessArena;
14 use rustc_hir::def::DefKind;
15 use rustc_hir::HirIdMap;
16 use rustc_middle::ty::{self, TyCtxt};
19 use self::VarianceTerm::*;
21 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
23 #[derive(Copy, Clone, Debug)]
24 pub struct InferredIndex(pub usize);
26 #[derive(Copy, Clone)]
27 pub enum VarianceTerm<'a> {
28 ConstantTerm(ty::Variance),
29 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
30 InferredTerm(InferredIndex),
33 impl<'a> fmt::Debug for VarianceTerm<'a> {
34 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36 ConstantTerm(c1) => write!(f, "{:?}", c1),
37 TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2),
38 InferredTerm(id) => write!(f, "[{}]", {
39 let InferredIndex(i) = id;
46 // The first pass over the crate simply builds up the set of inferreds.
48 pub struct TermsContext<'a, 'tcx> {
49 pub tcx: TyCtxt<'tcx>,
50 pub arena: &'a DroplessArena,
52 // For marker types, UnsafeCell, and other lang items where
53 // variance is hardcoded, records the item-id and the hardcoded
55 pub lang_items: Vec<(hir::HirId, Vec<ty::Variance>)>,
57 // Maps from the node id of an item to the first inferred index
58 // used for its type & region parameters.
59 pub inferred_starts: HirIdMap<InferredIndex>,
61 // Maps from an InferredIndex to the term for that variable.
62 pub inferred_terms: Vec<VarianceTermPtr<'a>>,
65 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(
67 arena: &'a DroplessArena,
68 ) -> TermsContext<'a, 'tcx> {
69 let mut terms_cx = TermsContext {
72 inferred_starts: Default::default(),
73 inferred_terms: vec![],
75 lang_items: lang_items(tcx),
78 // See the following for a discussion on dep-graph management.
80 // - https://rustc-dev-guide.rust-lang.org/query.html
81 // - https://rustc-dev-guide.rust-lang.org/variance.html
82 let crate_items = tcx.hir_crate_items(());
84 for id in crate_items.items() {
85 terms_cx.check_item(id);
88 for id in crate_items.trait_items() {
89 if let DefKind::AssocFn = tcx.def_kind(id.def_id) {
90 terms_cx.add_inferreds_for_item(id.hir_id());
94 for id in crate_items.impl_items() {
95 if let DefKind::AssocFn = tcx.def_kind(id.def_id) {
96 terms_cx.add_inferreds_for_item(id.hir_id());
100 for id in crate_items.foreign_items() {
101 if let DefKind::Fn = tcx.def_kind(id.def_id) {
102 terms_cx.add_inferreds_for_item(id.hir_id());
109 fn lang_items(tcx: TyCtxt<'_>) -> Vec<(hir::HirId, Vec<ty::Variance>)> {
110 let lang_items = tcx.lang_items();
112 (lang_items.phantom_data(), vec![ty::Covariant]),
113 (lang_items.unsafe_cell_type(), vec![ty::Invariant]),
116 all.into_iter() // iterating over (Option<DefId>, Variance)
117 .filter(|&(ref d, _)| d.is_some())
118 .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
119 .filter_map(|(d, v)| {
120 d.as_local().map(|d| tcx.hir().local_def_id_to_hir_id(d)).map(|n| (n, v))
121 }) // (HirId, Variance)
125 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
126 fn add_inferreds_for_item(&mut self, id: hir::HirId) {
128 let def_id = tcx.hir().local_def_id(id);
129 let count = tcx.generics_of(def_id).count();
135 // Record the start of this item's inferreds.
136 let start = self.inferred_terms.len();
137 let newly_added = self.inferred_starts.insert(id, InferredIndex(start)).is_none();
138 assert!(newly_added);
140 // N.B., in the code below for writing the results back into the
141 // `CrateVariancesMap`, we rely on the fact that all inferreds
142 // for a particular item are assigned continuous indices.
144 let arena = self.arena;
145 self.inferred_terms.extend(
146 (start..(start + count)).map(|i| &*arena.alloc(InferredTerm(InferredIndex(i)))),
150 fn check_item(&mut self, id: hir::ItemId) {
151 debug!("add_inferreds for item {}", self.tcx.hir().node_to_string(id.hir_id()));
153 let def_kind = self.tcx.def_kind(id.def_id);
155 DefKind::Struct | DefKind::Union => {
156 let item = self.tcx.hir().item(id);
158 if let hir::ItemKind::Struct(ref struct_def, _)
159 | hir::ItemKind::Union(ref struct_def, _) = item.kind
161 self.add_inferreds_for_item(item.hir_id());
163 if let hir::VariantData::Tuple(..) = *struct_def {
164 self.add_inferreds_for_item(struct_def.ctor_hir_id().unwrap());
169 let item = self.tcx.hir().item(id);
171 if let hir::ItemKind::Enum(ref enum_def, _) = item.kind {
172 self.add_inferreds_for_item(item.hir_id());
174 for variant in enum_def.variants {
175 if let hir::VariantData::Tuple(..) = variant.data {
176 self.add_inferreds_for_item(variant.data.ctor_hir_id().unwrap());
182 self.add_inferreds_for_item(id.hir_id());