src/librustc_typeck/variance/solve.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Constraint solving
  12 //!
  13 //! The final phase iterates over the constraints, refining the variance
  14 //! for each inferred until a fixed point is reached. This will be the
  15 //! optimal solution to the constraints. The final variance for each
  16 //! inferred is then written into the `variance_map` in the tcx.
  17
  18 use middle::subst::VecPerParamSpace;
  19 use middle::ty;
  20 use std::rc::Rc;
  21
  22 use super::constraints::*;
  23 use super::terms::*;
  24 use super::terms::VarianceTerm::*;
  25 use super::terms::ParamKind::*;
  26 use super::xform::*;
  27
  28 struct SolveContext<'a, 'tcx: 'a> {
  29     terms_cx: TermsContext<'a, 'tcx>,
  30     constraints: Vec<Constraint<'a>> ,
  31
  32     // Maps from an InferredIndex to the inferred value for that variable.
  33     solutions: Vec<ty::Variance>
  34 }
  35
  36 pub fn solve_constraints(constraints_cx: ConstraintContext) {
  37     let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
  38
  39     let solutions =
  40         terms_cx.inferred_infos.iter()
  41                                .map(|ii| ii.initial_variance)
  42                                .collect();
  43
  44     let mut solutions_cx = SolveContext {
  45         terms_cx: terms_cx,
  46         constraints: constraints,
  47         solutions: solutions
  48     };
  49     solutions_cx.solve();
  50     solutions_cx.write();
  51 }
  52
  53 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
  54     fn solve(&mut self) {
  55         // Propagate constraints until a fixed point is reached.  Note
  56         // that the maximum number of iterations is 2C where C is the
  57         // number of constraints (each variable can change values at most
  58         // twice). Since number of constraints is linear in size of the
  59         // input, so is the inference process.
  60         let mut changed = true;
  61         while changed {
  62             changed = false;
  63
  64             for constraint in &self.constraints {
  65                 let Constraint { inferred, variance: term } = *constraint;
  66                 let InferredIndex(inferred) = inferred;
  67                 let variance = self.evaluate(term);
  68                 let old_value = self.solutions[inferred];
  69                 let new_value = glb(variance, old_value);
  70                 if old_value != new_value {
  71                     debug!("Updating inferred {} (node {}) \
  72                             from {:?} to {:?} due to {:?}",
  73                             inferred,
  74                             self.terms_cx
  75                                 .inferred_infos[inferred]
  76                                 .param_id,
  77                             old_value,
  78                             new_value,
  79                             term);
  80
  81                     self.solutions[inferred] = new_value;
  82                     changed = true;
  83                 }
  84             }
  85         }
  86     }
  87
  88     fn write(&self) {
  89         // Collect all the variances for a particular item and stick
  90         // them into the variance map. We rely on the fact that we
  91         // generate all the inferreds for a particular item
  92         // consecutively (that is, we collect solutions for an item
  93         // until we see a new item id, and we assume (1) the solutions
  94         // are in the same order as the type parameters were declared
  95         // and (2) all solutions or a given item appear before a new
  96         // item id).
  97
  98         let tcx = self.terms_cx.tcx;
  99
 100         // Ignore the writes here because the relevant edges were
 101         // already accounted for in `constraints.rs`. See the section
 102         // on dependency graph management in README.md for more
 103         // information.
 104         let _ignore = tcx.dep_graph.in_ignore();
 105
 106         let solutions = &self.solutions;
 107         let inferred_infos = &self.terms_cx.inferred_infos;
 108         let mut index = 0;
 109         let num_inferred = self.terms_cx.num_inferred();
 110         while index < num_inferred {
 111             let item_id = inferred_infos[index].item_id;
 112             let mut types = VecPerParamSpace::empty();
 113             let mut regions = VecPerParamSpace::empty();
 114
 115             while index < num_inferred && inferred_infos[index].item_id == item_id {
 116                 let info = &inferred_infos[index];
 117                 let variance = solutions[index];
 118                 debug!("Index {} Info {} / {:?} / {:?} Variance {:?}",
 119                        index, info.index, info.kind, info.space, variance);
 120                 match info.kind {
 121                     TypeParam => { types.push(info.space, variance); }
 122                     RegionParam => { regions.push(info.space, variance); }
 123                 }
 124
 125                 index += 1;
 126             }
 127
 128             let item_variances = ty::ItemVariances {
 129                 types: types,
 130                 regions: regions
 131             };
 132             debug!("item_id={} item_variances={:?}",
 133                     item_id,
 134                     item_variances);
 135
 136             let item_def_id = tcx.map.local_def_id(item_id);
 137
 138             // For unit testing: check for a special "rustc_variance"
 139             // attribute and report an error with various results if found.
 140             if tcx.has_attr(item_def_id, "rustc_variance") {
 141                 span_err!(tcx.sess, tcx.map.span(item_id), E0208, "{:?}", item_variances);
 142             }
 143
 144             let newly_added = tcx.item_variance_map.borrow_mut()
 145                                  .insert(item_def_id, Rc::new(item_variances)).is_none();
 146             assert!(newly_added);
 147         }
 148     }
 149
 150     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
 151         match *term {
 152             ConstantTerm(v) => {
 153                 v
 154             }
 155
 156             TransformTerm(t1, t2) => {
 157                 let v1 = self.evaluate(t1);
 158                 let v2 = self.evaluate(t2);
 159                 v1.xform(v2)
 160             }
 161
 162             InferredTerm(InferredIndex(index)) => {
 163                 self.solutions[index]
 164             }
 165         }
 166     }
 167 }