compiler/rustc_typeck/src/variance/terms.rs

   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
  12 use rustc_arena::DroplessArena;
  13 use rustc_hir as hir;
  14 use rustc_hir::def::DefKind;
  15 use rustc_hir::HirIdMap;
  16 use rustc_middle::ty::{self, TyCtxt};
  17 use std::fmt;
  18
  19 use self::VarianceTerm::*;
  20
  21 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
  22
  23 #[derive(Copy, Clone, Debug)]
  24 pub struct InferredIndex(pub usize);
  25
  26 #[derive(Copy, Clone)]
  27 pub enum VarianceTerm<'a> {
  28     ConstantTerm(ty::Variance),
  29     TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
  30     InferredTerm(InferredIndex),
  31 }
  32
  33 impl<'a> fmt::Debug for VarianceTerm<'a> {
  34     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  35         match *self {
  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;
  40                 i
  41             }),
  42         }
  43     }
  44 }
  45
  46 // The first pass over the crate simply builds up the set of inferreds.
  47
  48 pub struct TermsContext<'a, 'tcx> {
  49     pub tcx: TyCtxt<'tcx>,
  50     pub arena: &'a DroplessArena,
  51
  52     // For marker types, UnsafeCell, and other lang items where
  53     // variance is hardcoded, records the item-id and the hardcoded
  54     // variance.
  55     pub lang_items: Vec<(hir::HirId, Vec<ty::Variance>)>,
  56
  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>,
  60
  61     // Maps from an InferredIndex to the term for that variable.
  62     pub inferred_terms: Vec<VarianceTermPtr<'a>>,
  63 }
  64
  65 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(
  66     tcx: TyCtxt<'tcx>,
  67     arena: &'a DroplessArena,
  68 ) -> TermsContext<'a, 'tcx> {
  69     let mut terms_cx = TermsContext {
  70         tcx,
  71         arena,
  72         inferred_starts: Default::default(),
  73         inferred_terms: vec![],
  74
  75         lang_items: lang_items(tcx),
  76     };
  77
  78     // See the following for a discussion on dep-graph management.
  79     //
  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(());
  83
  84     for id in crate_items.items() {
  85         terms_cx.check_item(id);
  86     }
  87
  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());
  91         }
  92     }
  93
  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());
  97         }
  98     }
  99
 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());
 103         }
 104     }
 105
 106     terms_cx
 107 }
 108
 109 fn lang_items(tcx: TyCtxt<'_>) -> Vec<(hir::HirId, Vec<ty::Variance>)> {
 110     let lang_items = tcx.lang_items();
 111     let all = [
 112         (lang_items.phantom_data(), vec![ty::Covariant]),
 113         (lang_items.unsafe_cell_type(), vec![ty::Invariant]),
 114     ];
 115
 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)
 122         .collect()
 123 }
 124
 125 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 126     fn add_inferreds_for_item(&mut self, id: hir::HirId) {
 127         let tcx = self.tcx;
 128         let def_id = tcx.hir().local_def_id(id);
 129         let count = tcx.generics_of(def_id).count();
 130
 131         if count == 0 {
 132             return;
 133         }
 134
 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);
 139
 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.
 143
 144         let arena = self.arena;
 145         self.inferred_terms.extend(
 146             (start..(start + count)).map(|i| &*arena.alloc(InferredTerm(InferredIndex(i)))),
 147         );
 148     }
 149
 150     fn check_item(&mut self, id: hir::ItemId) {
 151         debug!("add_inferreds for item {}", self.tcx.hir().node_to_string(id.hir_id()));
 152
 153         let def_kind = self.tcx.def_kind(id.def_id);
 154         match def_kind {
 155             DefKind::Struct | DefKind::Union => {
 156                 let item = self.tcx.hir().item(id);
 157
 158                 if let hir::ItemKind::Struct(ref struct_def, _)
 159                 | hir::ItemKind::Union(ref struct_def, _) = item.kind
 160                 {
 161                     self.add_inferreds_for_item(item.hir_id());
 162
 163                     if let hir::VariantData::Tuple(..) = *struct_def {
 164                         self.add_inferreds_for_item(struct_def.ctor_hir_id().unwrap());
 165                     }
 166                 }
 167             }
 168             DefKind::Enum => {
 169                 let item = self.tcx.hir().item(id);
 170
 171                 if let hir::ItemKind::Enum(ref enum_def, _) = item.kind {
 172                     self.add_inferreds_for_item(item.hir_id());
 173
 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());
 177                         }
 178                     }
 179                 }
 180             }
 181             DefKind::Fn => {
 182                 self.add_inferreds_for_item(id.hir_id());
 183             }
 184             _ => {}
 185         }
 186     }
 187 }