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 rustc::ty;
  19 use std::rc::Rc;
  20
  21 use super::constraints::*;
  22 use super::terms::*;
  23 use super::terms::VarianceTerm::*;
  24 use super::xform::*;
  25
  26 struct SolveContext<'a, 'tcx: 'a> {
  27     terms_cx: TermsContext<'a, 'tcx>,
  28     constraints: Vec<Constraint<'a>>,
  29
  30     // Maps from an InferredIndex to the inferred value for that variable.
  31     solutions: Vec<ty::Variance>,
  32 }
  33
  34 pub fn solve_constraints(constraints_cx: ConstraintContext) {
  35     let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
  36
  37     let solutions = terms_cx.inferred_infos
  38         .iter()
  39         .map(|ii| ii.initial_variance)
  40         .collect();
  41
  42     let mut solutions_cx = SolveContext {
  43         terms_cx: terms_cx,
  44         constraints: constraints,
  45         solutions: solutions,
  46     };
  47     solutions_cx.solve();
  48     solutions_cx.write();
  49 }
  50
  51 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
  52     fn solve(&mut self) {
  53         // Propagate constraints until a fixed point is reached.  Note
  54         // that the maximum number of iterations is 2C where C is the
  55         // number of constraints (each variable can change values at most
  56         // twice). Since number of constraints is linear in size of the
  57         // input, so is the inference process.
  58         let mut changed = true;
  59         while changed {
  60             changed = false;
  61
  62             for constraint in &self.constraints {
  63                 let Constraint { inferred, variance: term } = *constraint;
  64                 let InferredIndex(inferred) = inferred;
  65                 let variance = self.evaluate(term);
  66                 let old_value = self.solutions[inferred];
  67                 let new_value = glb(variance, old_value);
  68                 if old_value != new_value {
  69                     debug!("Updating inferred {} (node {}) \
  70                             from {:?} to {:?} due to {:?}",
  71                            inferred,
  72                            self.terms_cx
  73                                    .inferred_infos[inferred]
  74                                .param_id,
  75                            old_value,
  76                            new_value,
  77                            term);
  78
  79                     self.solutions[inferred] = new_value;
  80                     changed = true;
  81                 }
  82             }
  83         }
  84     }
  85
  86     fn write(&self) {
  87         // Collect all the variances for a particular item and stick
  88         // them into the variance map. We rely on the fact that we
  89         // generate all the inferreds for a particular item
  90         // consecutively (that is, we collect solutions for an item
  91         // until we see a new item id, and we assume (1) the solutions
  92         // are in the same order as the type parameters were declared
  93         // and (2) all solutions or a given item appear before a new
  94         // item id).
  95
  96         let tcx = self.terms_cx.tcx;
  97
  98         // Ignore the writes here because the relevant edges were
  99         // already accounted for in `constraints.rs`. See the section
 100         // on dependency graph management in README.md for more
 101         // information.
 102         let _ignore = tcx.dep_graph.in_ignore();
 103
 104         let solutions = &self.solutions;
 105         let inferred_infos = &self.terms_cx.inferred_infos;
 106         let mut index = 0;
 107         let num_inferred = self.terms_cx.num_inferred();
 108         while index < num_inferred {
 109             let item_id = inferred_infos[index].item_id;
 110
 111             let mut item_variances = vec![];
 112
 113             while index < num_inferred && inferred_infos[index].item_id == item_id {
 114                 let info = &inferred_infos[index];
 115                 let variance = solutions[index];
 116                 debug!("Index {} Info {} Variance {:?}",
 117                        index,
 118                        info.index,
 119                        variance);
 120
 121                 assert_eq!(item_variances.len(), info.index);
 122                 item_variances.push(variance);
 123                 index += 1;
 124             }
 125
 126             debug!("item_id={} item_variances={:?}", item_id, item_variances);
 127
 128             let item_def_id = tcx.hir.local_def_id(item_id);
 129
 130             // For unit testing: check for a special "rustc_variance"
 131             // attribute and report an error with various results if found.
 132             if tcx.has_attr(item_def_id, "rustc_variance") {
 133                 span_err!(tcx.sess,
 134                           tcx.hir.span(item_id),
 135                           E0208,
 136                           "{:?}",
 137                           item_variances);
 138             }
 139
 140             tcx.maps.variances_of.borrow_mut()
 141                .insert(item_def_id, Rc::new(item_variances));
 142         }
 143     }
 144
 145     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
 146         match *term {
 147             ConstantTerm(v) => v,
 148
 149             TransformTerm(t1, t2) => {
 150                 let v1 = self.evaluate(t1);
 151                 let v2 = self.evaluate(t2);
 152                 v1.xform(v2)
 153             }
 154
 155             InferredTerm(InferredIndex(index)) => self.solutions[index],
 156         }
 157     }
 158 }