From cf94bdc0742c13e2a0cac864c478b8626b266e1b Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:38 +0200 Subject: Merging upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- .../rustc_hir_analysis/src/variance/constraints.rs | 445 +++++++++++++++++++++ compiler/rustc_hir_analysis/src/variance/mod.rs | 63 +++ compiler/rustc_hir_analysis/src/variance/solve.rs | 135 +++++++ compiler/rustc_hir_analysis/src/variance/terms.rs | 145 +++++++ compiler/rustc_hir_analysis/src/variance/test.rs | 15 + compiler/rustc_hir_analysis/src/variance/xform.rs | 22 + 6 files changed, 825 insertions(+) create mode 100644 compiler/rustc_hir_analysis/src/variance/constraints.rs create mode 100644 compiler/rustc_hir_analysis/src/variance/mod.rs create mode 100644 compiler/rustc_hir_analysis/src/variance/solve.rs create mode 100644 compiler/rustc_hir_analysis/src/variance/terms.rs create mode 100644 compiler/rustc_hir_analysis/src/variance/test.rs create mode 100644 compiler/rustc_hir_analysis/src/variance/xform.rs (limited to 'compiler/rustc_hir_analysis/src/variance') diff --git a/compiler/rustc_hir_analysis/src/variance/constraints.rs b/compiler/rustc_hir_analysis/src/variance/constraints.rs new file mode 100644 index 000000000..eaf0310d5 --- /dev/null +++ b/compiler/rustc_hir_analysis/src/variance/constraints.rs @@ -0,0 +1,445 @@ +//! Constraint construction and representation +//! +//! The second pass over the AST determines the set of constraints. +//! We walk the set of items and, for each member, generate new constraints. + +use hir::def_id::{DefId, LocalDefId}; +use rustc_hir as hir; +use rustc_hir::def::DefKind; +use rustc_middle::ty::subst::{GenericArgKind, SubstsRef}; +use rustc_middle::ty::{self, Ty, TyCtxt}; + +use super::terms::VarianceTerm::*; +use super::terms::*; + +pub struct ConstraintContext<'a, 'tcx> { + pub terms_cx: TermsContext<'a, 'tcx>, + + // These are pointers to common `ConstantTerm` instances + covariant: VarianceTermPtr<'a>, + contravariant: VarianceTermPtr<'a>, + invariant: VarianceTermPtr<'a>, + bivariant: VarianceTermPtr<'a>, + + pub constraints: Vec>, +} + +/// Declares that the variable `decl_id` appears in a location with +/// variance `variance`. +#[derive(Copy, Clone)] +pub struct Constraint<'a> { + pub inferred: InferredIndex, + pub variance: &'a VarianceTerm<'a>, +} + +/// To build constraints, we visit one item (type, trait) at a time +/// and look at its contents. So e.g., if we have +/// ```ignore (illustrative) +/// struct Foo { +/// b: Bar +/// } +/// ``` +/// then while we are visiting `Bar`, the `CurrentItem` would have +/// the `DefId` and the start of `Foo`'s inferreds. +pub struct CurrentItem { + inferred_start: InferredIndex, +} + +pub fn add_constraints_from_crate<'a, 'tcx>( + terms_cx: TermsContext<'a, 'tcx>, +) -> ConstraintContext<'a, 'tcx> { + let tcx = terms_cx.tcx; + let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant)); + let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant)); + let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant)); + let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant)); + let mut constraint_cx = ConstraintContext { + terms_cx, + covariant, + contravariant, + invariant, + bivariant, + constraints: Vec::new(), + }; + + let crate_items = tcx.hir_crate_items(()); + + for def_id in crate_items.definitions() { + let def_kind = tcx.def_kind(def_id); + match def_kind { + DefKind::Struct | DefKind::Union | DefKind::Enum => { + constraint_cx.build_constraints_for_item(def_id); + + let adt = tcx.adt_def(def_id); + for variant in adt.variants() { + if let Some(ctor) = variant.ctor_def_id { + constraint_cx.build_constraints_for_item(ctor.expect_local()); + } + } + } + DefKind::Fn | DefKind::AssocFn => constraint_cx.build_constraints_for_item(def_id), + _ => {} + } + } + + constraint_cx +} + +impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { + fn tcx(&self) -> TyCtxt<'tcx> { + self.terms_cx.tcx + } + + fn build_constraints_for_item(&mut self, def_id: LocalDefId) { + let tcx = self.tcx(); + debug!("build_constraints_for_item({})", tcx.def_path_str(def_id.to_def_id())); + + // Skip items with no generics - there's nothing to infer in them. + if tcx.generics_of(def_id).count() == 0 { + return; + } + + let inferred_start = self.terms_cx.inferred_starts[&def_id]; + let current_item = &CurrentItem { inferred_start }; + match tcx.type_of(def_id).kind() { + ty::Adt(def, _) => { + // Not entirely obvious: constraints on structs/enums do not + // affect the variance of their type parameters. See discussion + // in comment at top of module. + // + // self.add_constraints_from_generics(generics); + + for field in def.all_fields() { + self.add_constraints_from_ty( + current_item, + tcx.type_of(field.did), + self.covariant, + ); + } + } + + ty::FnDef(..) => { + self.add_constraints_from_sig(current_item, tcx.fn_sig(def_id), self.covariant); + } + + ty::Error(_) => {} + _ => { + span_bug!( + tcx.def_span(def_id), + "`build_constraints_for_item` unsupported for this item" + ); + } + } + } + + fn add_constraint(&mut self, current: &CurrentItem, index: u32, variance: VarianceTermPtr<'a>) { + debug!("add_constraint(index={}, variance={:?})", index, variance); + self.constraints.push(Constraint { + inferred: InferredIndex(current.inferred_start.0 + index as usize), + variance, + }); + } + + fn contravariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { + self.xform(variance, self.contravariant) + } + + fn invariant(&mut self, variance: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { + self.xform(variance, self.invariant) + } + + fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> { + match v { + ty::Covariant => self.covariant, + ty::Invariant => self.invariant, + ty::Contravariant => self.contravariant, + ty::Bivariant => self.bivariant, + } + } + + fn xform(&mut self, v1: VarianceTermPtr<'a>, v2: VarianceTermPtr<'a>) -> VarianceTermPtr<'a> { + match (*v1, *v2) { + (_, ConstantTerm(ty::Covariant)) => { + // Applying a "covariant" transform is always a no-op + v1 + } + + (ConstantTerm(c1), ConstantTerm(c2)) => self.constant_term(c1.xform(c2)), + + _ => &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)), + } + } + + #[instrument(level = "debug", skip(self, current))] + fn add_constraints_from_invariant_substs( + &mut self, + current: &CurrentItem, + substs: SubstsRef<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + // Trait are always invariant so we can take advantage of that. + let variance_i = self.invariant(variance); + + for k in substs { + match k.unpack() { + GenericArgKind::Lifetime(lt) => { + self.add_constraints_from_region(current, lt, variance_i) + } + GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i), + GenericArgKind::Const(val) => { + self.add_constraints_from_const(current, val, variance_i) + } + } + } + } + + /// Adds constraints appropriate for an instance of `ty` appearing + /// in a context with the generics defined in `generics` and + /// ambient variance `variance` + fn add_constraints_from_ty( + &mut self, + current: &CurrentItem, + ty: Ty<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + debug!("add_constraints_from_ty(ty={:?}, variance={:?})", ty, variance); + + match *ty.kind() { + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Str + | ty::Never + | ty::Foreign(..) => { + // leaf type -- noop + } + + ty::FnDef(..) | ty::Generator(..) | ty::Closure(..) => { + bug!("Unexpected closure type in variance computation"); + } + + ty::Ref(region, ty, mutbl) => { + let contra = self.contravariant(variance); + self.add_constraints_from_region(current, region, contra); + self.add_constraints_from_mt(current, &ty::TypeAndMut { ty, mutbl }, variance); + } + + ty::Array(typ, len) => { + self.add_constraints_from_const(current, len, variance); + self.add_constraints_from_ty(current, typ, variance); + } + + ty::Slice(typ) => { + self.add_constraints_from_ty(current, typ, variance); + } + + ty::RawPtr(ref mt) => { + self.add_constraints_from_mt(current, mt, variance); + } + + ty::Tuple(subtys) => { + for subty in subtys { + self.add_constraints_from_ty(current, subty, variance); + } + } + + ty::Adt(def, substs) => { + self.add_constraints_from_substs(current, def.did(), substs, variance); + } + + ty::Projection(ref data) => { + self.add_constraints_from_invariant_substs(current, data.substs, variance); + } + + ty::Opaque(_, substs) => { + self.add_constraints_from_invariant_substs(current, substs, variance); + } + + ty::Dynamic(data, r, _) => { + // The type `Foo` is contravariant w/r/t `'a`: + let contra = self.contravariant(variance); + self.add_constraints_from_region(current, r, contra); + + if let Some(poly_trait_ref) = data.principal() { + self.add_constraints_from_invariant_substs( + current, + poly_trait_ref.skip_binder().substs, + variance, + ); + } + + for projection in data.projection_bounds() { + match projection.skip_binder().term.unpack() { + ty::TermKind::Ty(ty) => { + self.add_constraints_from_ty(current, ty, self.invariant); + } + ty::TermKind::Const(c) => { + self.add_constraints_from_const(current, c, self.invariant) + } + } + } + } + + ty::Param(ref data) => { + self.add_constraint(current, data.index, variance); + } + + ty::FnPtr(sig) => { + self.add_constraints_from_sig(current, sig, variance); + } + + ty::Error(_) => { + // we encounter this when walking the trait references for object + // types, where we use Error as the Self type + } + + ty::Placeholder(..) | ty::GeneratorWitness(..) | ty::Bound(..) | ty::Infer(..) => { + bug!( + "unexpected type encountered in \ + variance inference: {}", + ty + ); + } + } + } + + /// Adds constraints appropriate for a nominal type (enum, struct, + /// object, etc) appearing in a context with ambient variance `variance` + fn add_constraints_from_substs( + &mut self, + current: &CurrentItem, + def_id: DefId, + substs: SubstsRef<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + debug!( + "add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})", + def_id, substs, variance + ); + + // We don't record `inferred_starts` entries for empty generics. + if substs.is_empty() { + return; + } + + let (local, remote) = if let Some(def_id) = def_id.as_local() { + (Some(self.terms_cx.inferred_starts[&def_id]), None) + } else { + (None, Some(self.tcx().variances_of(def_id))) + }; + + for (i, k) in substs.iter().enumerate() { + let variance_decl = if let Some(InferredIndex(start)) = local { + // Parameter on an item defined within current crate: + // variance not yet inferred, so return a symbolic + // variance. + self.terms_cx.inferred_terms[start + i] + } else { + // Parameter on an item defined within another crate: + // variance already inferred, just look it up. + self.constant_term(remote.as_ref().unwrap()[i]) + }; + let variance_i = self.xform(variance, variance_decl); + debug!( + "add_constraints_from_substs: variance_decl={:?} variance_i={:?}", + variance_decl, variance_i + ); + match k.unpack() { + GenericArgKind::Lifetime(lt) => { + self.add_constraints_from_region(current, lt, variance_i) + } + GenericArgKind::Type(ty) => self.add_constraints_from_ty(current, ty, variance_i), + GenericArgKind::Const(val) => { + self.add_constraints_from_const(current, val, variance) + } + } + } + } + + /// Adds constraints appropriate for a const expression `val` + /// in a context with ambient variance `variance` + fn add_constraints_from_const( + &mut self, + current: &CurrentItem, + c: ty::Const<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + debug!("add_constraints_from_const(c={:?}, variance={:?})", c, variance); + + match &c.kind() { + ty::ConstKind::Unevaluated(uv) => { + self.add_constraints_from_invariant_substs(current, uv.substs, variance); + } + _ => {} + } + } + + /// Adds constraints appropriate for a function with signature + /// `sig` appearing in a context with ambient variance `variance` + fn add_constraints_from_sig( + &mut self, + current: &CurrentItem, + sig: ty::PolyFnSig<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + let contra = self.contravariant(variance); + for &input in sig.skip_binder().inputs() { + self.add_constraints_from_ty(current, input, contra); + } + self.add_constraints_from_ty(current, sig.skip_binder().output(), variance); + } + + /// Adds constraints appropriate for a region appearing in a + /// context with ambient variance `variance` + fn add_constraints_from_region( + &mut self, + current: &CurrentItem, + region: ty::Region<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + match *region { + ty::ReEarlyBound(ref data) => { + self.add_constraint(current, data.index, variance); + } + + ty::ReStatic => {} + + ty::ReLateBound(..) => { + // Late-bound regions do not get substituted the same + // way early-bound regions do, so we skip them here. + } + + ty::ReFree(..) | ty::ReVar(..) | ty::RePlaceholder(..) | ty::ReErased => { + // We don't expect to see anything but 'static or bound + // regions when visiting member types or method types. + bug!( + "unexpected region encountered in variance \ + inference: {:?}", + region + ); + } + } + } + + /// Adds constraints appropriate for a mutability-type pair + /// appearing in a context with ambient variance `variance` + fn add_constraints_from_mt( + &mut self, + current: &CurrentItem, + mt: &ty::TypeAndMut<'tcx>, + variance: VarianceTermPtr<'a>, + ) { + match mt.mutbl { + hir::Mutability::Mut => { + let invar = self.invariant(variance); + self.add_constraints_from_ty(current, mt.ty, invar); + } + + hir::Mutability::Not => { + self.add_constraints_from_ty(current, mt.ty, variance); + } + } + } +} diff --git a/compiler/rustc_hir_analysis/src/variance/mod.rs b/compiler/rustc_hir_analysis/src/variance/mod.rs new file mode 100644 index 000000000..82103c5a0 --- /dev/null +++ b/compiler/rustc_hir_analysis/src/variance/mod.rs @@ -0,0 +1,63 @@ +//! Module for inferring the variance of type and lifetime parameters. See the [rustc dev guide] +//! chapter for more info. +//! +//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/variance.html + +use rustc_arena::DroplessArena; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::query::Providers; +use rustc_middle::ty::{self, CrateVariancesMap, TyCtxt}; + +/// Defines the `TermsContext` basically houses an arena where we can +/// allocate terms. +mod terms; + +/// Code to gather up constraints. +mod constraints; + +/// Code to solve constraints and write out the results. +mod solve; + +/// Code to write unit tests of variance. +pub mod test; + +/// Code for transforming variances. +mod xform; + +pub fn provide(providers: &mut Providers) { + *providers = Providers { variances_of, crate_variances, ..*providers }; +} + +fn crate_variances(tcx: TyCtxt<'_>, (): ()) -> CrateVariancesMap<'_> { + let arena = DroplessArena::default(); + let terms_cx = terms::determine_parameters_to_be_inferred(tcx, &arena); + let constraints_cx = constraints::add_constraints_from_crate(terms_cx); + solve::solve_constraints(constraints_cx) +} + +fn variances_of(tcx: TyCtxt<'_>, item_def_id: DefId) -> &[ty::Variance] { + // Skip items with no generics - there's nothing to infer in them. + if tcx.generics_of(item_def_id).count() == 0 { + return &[]; + } + + match tcx.def_kind(item_def_id) { + DefKind::Fn + | DefKind::AssocFn + | DefKind::Enum + | DefKind::Struct + | DefKind::Union + | DefKind::Variant + | DefKind::Ctor(..) => {} + _ => { + // Variance not relevant. + span_bug!(tcx.def_span(item_def_id), "asked to compute variance for wrong kind of item") + } + } + + // Everything else must be inferred. + + let crate_map = tcx.crate_variances(()); + crate_map.variances.get(&item_def_id).copied().unwrap_or(&[]) +} diff --git a/compiler/rustc_hir_analysis/src/variance/solve.rs b/compiler/rustc_hir_analysis/src/variance/solve.rs new file mode 100644 index 000000000..97aca621a --- /dev/null +++ b/compiler/rustc_hir_analysis/src/variance/solve.rs @@ -0,0 +1,135 @@ +//! Constraint solving +//! +//! The final phase iterates over the constraints, refining the variance +//! for each inferred until a fixed point is reached. This will be the +//! optimal solution to the constraints. The final variance for each +//! inferred is then written into the `variance_map` in the tcx. + +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::def_id::DefId; +use rustc_middle::ty; + +use super::constraints::*; +use super::terms::VarianceTerm::*; +use super::terms::*; +use super::xform::*; + +struct SolveContext<'a, 'tcx> { + terms_cx: TermsContext<'a, 'tcx>, + constraints: Vec>, + + // Maps from an InferredIndex to the inferred value for that variable. + solutions: Vec, +} + +pub fn solve_constraints<'tcx>( + constraints_cx: ConstraintContext<'_, 'tcx>, +) -> ty::CrateVariancesMap<'tcx> { + let ConstraintContext { terms_cx, constraints, .. } = constraints_cx; + + let mut solutions = vec![ty::Bivariant; terms_cx.inferred_terms.len()]; + for &(id, ref variances) in &terms_cx.lang_items { + let InferredIndex(start) = terms_cx.inferred_starts[&id]; + for (i, &variance) in variances.iter().enumerate() { + solutions[start + i] = variance; + } + } + + let mut solutions_cx = SolveContext { terms_cx, constraints, solutions }; + solutions_cx.solve(); + let variances = solutions_cx.create_map(); + + ty::CrateVariancesMap { variances } +} + +impl<'a, 'tcx> SolveContext<'a, 'tcx> { + fn solve(&mut self) { + // Propagate constraints until a fixed point is reached. Note + // that the maximum number of iterations is 2C where C is the + // number of constraints (each variable can change values at most + // twice). Since number of constraints is linear in size of the + // input, so is the inference process. + let mut changed = true; + while changed { + changed = false; + + for constraint in &self.constraints { + let Constraint { inferred, variance: term } = *constraint; + let InferredIndex(inferred) = inferred; + let variance = self.evaluate(term); + let old_value = self.solutions[inferred]; + let new_value = glb(variance, old_value); + if old_value != new_value { + debug!( + "updating inferred {} \ + from {:?} to {:?} due to {:?}", + inferred, old_value, new_value, term + ); + + self.solutions[inferred] = new_value; + changed = true; + } + } + } + } + + fn enforce_const_invariance(&self, generics: &ty::Generics, variances: &mut [ty::Variance]) { + let tcx = self.terms_cx.tcx; + + // Make all const parameters invariant. + for param in generics.params.iter() { + if let ty::GenericParamDefKind::Const { .. } = param.kind { + variances[param.index as usize] = ty::Invariant; + } + } + + // Make all the const parameters in the parent invariant (recursively). + if let Some(def_id) = generics.parent { + self.enforce_const_invariance(tcx.generics_of(def_id), variances); + } + } + + fn create_map(&self) -> FxHashMap { + let tcx = self.terms_cx.tcx; + + let solutions = &self.solutions; + self.terms_cx + .inferred_starts + .iter() + .map(|(&def_id, &InferredIndex(start))| { + let generics = tcx.generics_of(def_id); + let count = generics.count(); + + let variances = tcx.arena.alloc_slice(&solutions[start..(start + count)]); + + // Const parameters are always invariant. + self.enforce_const_invariance(generics, variances); + + // Functions are permitted to have unused generic parameters: make those invariant. + if let ty::FnDef(..) = tcx.type_of(def_id).kind() { + for variance in variances.iter_mut() { + if *variance == ty::Bivariant { + *variance = ty::Invariant; + } + } + } + + (def_id.to_def_id(), &*variances) + }) + .collect() + } + + fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance { + match *term { + ConstantTerm(v) => v, + + TransformTerm(t1, t2) => { + let v1 = self.evaluate(t1); + let v2 = self.evaluate(t2); + v1.xform(v2) + } + + InferredTerm(InferredIndex(index)) => self.solutions[index], + } + } +} diff --git a/compiler/rustc_hir_analysis/src/variance/terms.rs b/compiler/rustc_hir_analysis/src/variance/terms.rs new file mode 100644 index 000000000..1f763011e --- /dev/null +++ b/compiler/rustc_hir_analysis/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)>, + + // Maps from the node id of an item to the first inferred index + // used for its type & region parameters. + pub inferred_starts: LocalDefIdMap, + + // Maps from an InferredIndex to the term for that variable. + pub inferred_terms: Vec>, +} + +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)> { + 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, 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)))), + ); + } +} diff --git a/compiler/rustc_hir_analysis/src/variance/test.rs b/compiler/rustc_hir_analysis/src/variance/test.rs new file mode 100644 index 000000000..83ed3e44b --- /dev/null +++ b/compiler/rustc_hir_analysis/src/variance/test.rs @@ -0,0 +1,15 @@ +use rustc_errors::struct_span_err; +use rustc_middle::ty::TyCtxt; +use rustc_span::symbol::sym; + +pub fn test_variance(tcx: TyCtxt<'_>) { + // For unit testing: check for a special "rustc_variance" + // attribute and report an error with various results if found. + for id in tcx.hir().items() { + if tcx.has_attr(id.owner_id.to_def_id(), sym::rustc_variance) { + let variances_of = tcx.variances_of(id.owner_id); + struct_span_err!(tcx.sess, tcx.def_span(id.owner_id), E0208, "{:?}", variances_of) + .emit(); + } + } +} diff --git a/compiler/rustc_hir_analysis/src/variance/xform.rs b/compiler/rustc_hir_analysis/src/variance/xform.rs new file mode 100644 index 000000000..027f0859f --- /dev/null +++ b/compiler/rustc_hir_analysis/src/variance/xform.rs @@ -0,0 +1,22 @@ +use rustc_middle::ty; + +pub fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance { + // Greatest lower bound of the variance lattice as + // defined in The Paper: + // + // * + // - + + // o + match (v1, v2) { + (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant, + + (ty::Covariant, ty::Contravariant) => ty::Invariant, + (ty::Contravariant, ty::Covariant) => ty::Invariant, + + (ty::Covariant, ty::Covariant) => ty::Covariant, + + (ty::Contravariant, ty::Contravariant) => ty::Contravariant, + + (x, ty::Bivariant) | (ty::Bivariant, x) => x, + } +} -- cgit v1.2.3