summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_hir_analysis/src/variance
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_hir_analysis/src/variance')
-rw-r--r--compiler/rustc_hir_analysis/src/variance/constraints.rs445
-rw-r--r--compiler/rustc_hir_analysis/src/variance/mod.rs63
-rw-r--r--compiler/rustc_hir_analysis/src/variance/solve.rs135
-rw-r--r--compiler/rustc_hir_analysis/src/variance/terms.rs145
-rw-r--r--compiler/rustc_hir_analysis/src/variance/test.rs15
-rw-r--r--compiler/rustc_hir_analysis/src/variance/xform.rs22
6 files changed, 825 insertions, 0 deletions
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<Constraint<'a>>,
+}
+
+/// 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<T> {
+/// b: Bar<T>
+/// }
+/// ```
+/// then while we are visiting `Bar<T>`, 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<T+'a>` 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<Constraint<'a>>,
+
+ // Maps from an InferredIndex to the inferred value for that variable.
+ solutions: Vec<ty::Variance>,
+}
+
+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<DefId, &'tcx [ty::Variance]> {
+ 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<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)))),
+ );
+ }
+}
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,
+ }
+}