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