3 //! The final phase iterates over the constraints, refining the variance
4 //! for each inferred until a fixed point is reached. This will be the
5 //! optimal solution to the constraints. The final variance for each
6 //! inferred is then written into the `variance_map` in the tcx.
8 use rustc_data_structures::fx::FxHashMap;
9 use rustc_hir::def_id::DefId;
12 use super::constraints::*;
13 use super::terms::VarianceTerm::*;
17 struct SolveContext<'a, 'tcx> {
18 terms_cx: TermsContext<'a, 'tcx>,
19 constraints: Vec<Constraint<'a>>,
21 // Maps from an InferredIndex to the inferred value for that variable.
22 solutions: Vec<ty::Variance>,
25 pub fn solve_constraints<'tcx>(
26 constraints_cx: ConstraintContext<'_, 'tcx>,
27 ) -> ty::CrateVariancesMap<'tcx> {
28 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
30 let mut solutions = vec![ty::Bivariant; terms_cx.inferred_terms.len()];
31 for &(id, ref variances) in &terms_cx.lang_items {
32 let InferredIndex(start) = terms_cx.inferred_starts[&id];
33 for (i, &variance) in variances.iter().enumerate() {
34 solutions[start + i] = variance;
38 let mut solutions_cx = SolveContext { terms_cx, constraints, solutions };
40 let variances = solutions_cx.create_map();
42 ty::CrateVariancesMap { variances }
45 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
47 // Propagate constraints until a fixed point is reached. Note
48 // that the maximum number of iterations is 2C where C is the
49 // number of constraints (each variable can change values at most
50 // twice). Since number of constraints is linear in size of the
51 // input, so is the inference process.
52 let mut changed = true;
56 for constraint in &self.constraints {
57 let Constraint { inferred, variance: term } = *constraint;
58 let InferredIndex(inferred) = inferred;
59 let variance = self.evaluate(term);
60 let old_value = self.solutions[inferred];
61 let new_value = glb(variance, old_value);
62 if old_value != new_value {
64 "updating inferred {} \
65 from {:?} to {:?} due to {:?}",
66 inferred, old_value, new_value, term
69 self.solutions[inferred] = new_value;
76 fn enforce_const_invariance(&self, generics: &ty::Generics, variances: &mut [ty::Variance]) {
77 let tcx = self.terms_cx.tcx;
79 // Make all const parameters invariant.
80 for param in generics.params.iter() {
81 if let ty::GenericParamDefKind::Const = param.kind {
82 variances[param.index as usize] = ty::Invariant;
86 // Make all the const parameters in the parent invariant (recursively).
87 if let Some(def_id) = generics.parent {
88 self.enforce_const_invariance(tcx.generics_of(def_id), variances);
92 fn create_map(&self) -> FxHashMap<DefId, &'tcx [ty::Variance]> {
93 let tcx = self.terms_cx.tcx;
95 let solutions = &self.solutions;
99 .map(|(&id, &InferredIndex(start))| {
100 let def_id = tcx.hir().local_def_id(id);
101 let generics = tcx.generics_of(def_id);
102 let count = generics.count();
104 let variances = tcx.arena.alloc_slice(&solutions[start..(start + count)]);
106 // Const parameters are always invariant.
107 self.enforce_const_invariance(generics, variances);
109 // Functions are permitted to have unused generic parameters: make those invariant.
110 if let ty::FnDef(..) = tcx.type_of(def_id).kind {
111 for variance in variances.iter_mut() {
112 if *variance == ty::Bivariant {
113 *variance = ty::Invariant;
118 (def_id.to_def_id(), &*variances)
123 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
125 ConstantTerm(v) => v,
127 TransformTerm(t1, t2) => {
128 let v1 = self.evaluate(t1);
129 let v2 = self.evaluate(t2);
133 InferredTerm(InferredIndex(index)) => self.solutions[index],