rustc_typeck to rustc_hir_analysis

6 files changed, 824 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 00000000000..eaf0310d57a
--- /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 00000000000..82103c5a03b
--- /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 00000000000..97aca621aa2
--- /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 00000000000..1f763011e06
--- /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 00000000000..2ba87db880b
--- /dev/null
+++ b/compiler/rustc_hir_analysis/src/variance/test.rs
@@ -0,0 +1,14 @@
+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.def_id.to_def_id(), sym::rustc_variance) {
+            let variances_of = tcx.variances_of(id.def_id);
+            struct_span_err!(tcx.sess, tcx.def_span(id.def_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 00000000000..027f0859fcd
--- /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,
+    }
+}