diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_typeck/src/variance/terms.rs | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/compiler/rustc_typeck/src/variance/terms.rs b/compiler/rustc_typeck/src/variance/terms.rs new file mode 100644 index 000000000..1f763011e --- /dev/null +++ b/compiler/rustc_typeck/src/variance/terms.rs @@ -0,0 +1,145 @@ +// Representing terms +// +// Terms are structured as a straightforward tree. Rather than rely on +// GC, we allocate terms out of a bounded arena (the lifetime of this +// arena is the lifetime 'a that is threaded around). +// +// We assign a unique index to each type/region parameter whose variance +// is to be inferred. We refer to such variables as "inferreds". An +// `InferredIndex` is a newtype'd int representing the index of such +// a variable. + +use rustc_arena::DroplessArena; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::{LocalDefId, LocalDefIdMap}; +use rustc_middle::ty::{self, TyCtxt}; +use std::fmt; + +use self::VarianceTerm::*; + +pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>; + +#[derive(Copy, Clone, Debug)] +pub struct InferredIndex(pub usize); + +#[derive(Copy, Clone)] +pub enum VarianceTerm<'a> { + ConstantTerm(ty::Variance), + TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>), + InferredTerm(InferredIndex), +} + +impl<'a> fmt::Debug for VarianceTerm<'a> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + ConstantTerm(c1) => write!(f, "{:?}", c1), + TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2), + InferredTerm(id) => write!(f, "[{}]", { + let InferredIndex(i) = id; + i + }), + } + } +} + +// The first pass over the crate simply builds up the set of inferreds. + +pub struct TermsContext<'a, 'tcx> { + pub tcx: TyCtxt<'tcx>, + pub arena: &'a DroplessArena, + + // For marker types, UnsafeCell, and other lang items where + // variance is hardcoded, records the item-id and the hardcoded + // variance. + pub lang_items: Vec<(LocalDefId, Vec<ty::Variance>)>, + + // Maps from the node id of an item to the first inferred index + // used for its type & region parameters. + pub inferred_starts: LocalDefIdMap<InferredIndex>, + + // Maps from an InferredIndex to the term for that variable. + pub inferred_terms: Vec<VarianceTermPtr<'a>>, +} + +pub fn determine_parameters_to_be_inferred<'a, 'tcx>( + tcx: TyCtxt<'tcx>, + arena: &'a DroplessArena, +) -> TermsContext<'a, 'tcx> { + let mut terms_cx = TermsContext { + tcx, + arena, + inferred_starts: Default::default(), + inferred_terms: vec![], + + lang_items: lang_items(tcx), + }; + + // See the following for a discussion on dep-graph management. + // + // - https://rustc-dev-guide.rust-lang.org/query.html + // - https://rustc-dev-guide.rust-lang.org/variance.html + let crate_items = tcx.hir_crate_items(()); + + for def_id in crate_items.definitions() { + debug!("add_inferreds for item {:?}", def_id); + + let def_kind = tcx.def_kind(def_id); + + match def_kind { + DefKind::Struct | DefKind::Union | DefKind::Enum => { + terms_cx.add_inferreds_for_item(def_id); + + let adt = tcx.adt_def(def_id); + for variant in adt.variants() { + if let Some(ctor) = variant.ctor_def_id { + terms_cx.add_inferreds_for_item(ctor.expect_local()); + } + } + } + DefKind::Fn | DefKind::AssocFn => terms_cx.add_inferreds_for_item(def_id), + _ => {} + } + } + + terms_cx +} + +fn lang_items(tcx: TyCtxt<'_>) -> Vec<(LocalDefId, Vec<ty::Variance>)> { + let lang_items = tcx.lang_items(); + let all = [ + (lang_items.phantom_data(), vec![ty::Covariant]), + (lang_items.unsafe_cell_type(), vec![ty::Invariant]), + ]; + + all.into_iter() // iterating over (Option<DefId>, Variance) + .filter_map(|(d, v)| { + let def_id = d?.as_local()?; // LocalDefId + Some((def_id, v)) + }) + .collect() +} + +impl<'a, 'tcx> TermsContext<'a, 'tcx> { + fn add_inferreds_for_item(&mut self, def_id: LocalDefId) { + let tcx = self.tcx; + let count = tcx.generics_of(def_id).count(); + + if count == 0 { + return; + } + + // Record the start of this item's inferreds. + let start = self.inferred_terms.len(); + let newly_added = self.inferred_starts.insert(def_id, InferredIndex(start)).is_none(); + assert!(newly_added); + + // N.B., in the code below for writing the results back into the + // `CrateVariancesMap`, we rely on the fact that all inferreds + // for a particular item are assigned continuous indices. + + let arena = self.arena; + self.inferred_terms.extend( + (start..(start + count)).map(|i| &*arena.alloc(InferredTerm(InferredIndex(i)))), + ); + } +} |