1 // Copyright 2012 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
12 use collections::SmallIntMap;
13
14 use middle::ty::{Vid, expected_found, IntVarValue};
15 use middle::ty;
16 use middle::typeck::infer::{Bounds, uok, ures};
17 use middle::typeck::infer::InferCtxt;
18 use middle::typeck::infer::to_str::InferStr;
19 use std::cell::RefCell;
20 use syntax::ast;
21
22 #[deriving(Clone)]
23 pub enum VarValue<V, T> {
24 Redirect(V),
25 Root(T, uint),
26 }
27
28 pub struct ValsAndBindings<V, T> {
29 pub vals: SmallIntMap<VarValue<V, T>>,
30 pub bindings: Vec<(V, VarValue<V, T>)> ,
31 }
32
33 pub struct Node<V, T> {
34 pub root: V,
35 pub possible_types: T,
36 pub rank: uint,
37 }
38
39 pub trait UnifyVid<T> {
40 fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
41 -> &'v RefCell<ValsAndBindings<Self, T>>;
42 }
43
44 pub trait UnifyInferCtxtMethods {
45 fn get<T:Clone,
46 V:Clone + Eq + Vid + UnifyVid<T>>(
47 &self,
48 vid: V)
49 -> Node<V, T>;
50 fn set<T:Clone + InferStr,
51 V:Clone + Vid + ToStr + UnifyVid<T>>(
52 &self,
53 vid: V,
54 new_v: VarValue<V, T>);
55 fn unify<T:Clone + InferStr,
56 V:Clone + Vid + ToStr + UnifyVid<T>>(
57 &self,
58 node_a: &Node<V, T>,
59 node_b: &Node<V, T>)
60 -> (V, uint);
61 }
62
63 impl<'a> UnifyInferCtxtMethods for InferCtxt<'a> {
64 fn get<T:Clone,
65 V:Clone + Eq + Vid + UnifyVid<T>>(
66 &self,
67 vid: V)
68 -> Node<V, T> {
69 /*!
70 *
71 * Find the root node for `vid`. This uses the standard
72 * union-find algorithm with path compression:
73 * http://en.wikipedia.org/wiki/Disjoint-set_data_structure
74 */
75
76 let tcx = self.tcx;
77 let vb = UnifyVid::appropriate_vals_and_bindings(self);
78 return helper(tcx, &mut *vb.borrow_mut(), vid);
79
80 fn helper<T:Clone, V:Clone+Eq+Vid>(
81 tcx: &ty::ctxt,
82 vb: &mut ValsAndBindings<V,T>,
83 vid: V) -> Node<V, T>
84 {
85 let vid_u = vid.to_uint();
86 let var_val = match vb.vals.find(&vid_u) {
87 Some(&ref var_val) => (*var_val).clone(),
88 None => {
89 tcx.sess.bug(format!(
90 "failed lookup of vid `{}`", vid_u));
91 }
92 };
93 match var_val {
94 Redirect(vid) => {
95 let node: Node<V,T> = helper(tcx, vb, vid.clone());
96 if node.root != vid {
97 // Path compression
98 vb.vals.insert(vid.to_uint(),
99 Redirect(node.root.clone()));
100 }
101 node
102 }
103 Root(pt, rk) => {
104 Node {root: vid, possible_types: pt, rank: rk}
105 }
106 }
107 }
108 }
109
110 fn set<T:Clone + InferStr,
111 V:Clone + Vid + ToStr + UnifyVid<T>>(
112 &self,
113 vid: V,
114 new_v: VarValue<V, T>) {
115 /*!
116 *
117 * Sets the value for `vid` to `new_v`. `vid` MUST be a root node!
118 */
119
120 debug!("Updating variable {} to {}",
121 vid.to_str(), new_v.inf_str(self));
122
123 let vb = UnifyVid::appropriate_vals_and_bindings(self);
124 let mut vb = vb.borrow_mut();
125 let old_v = (*vb.vals.get(&vid.to_uint())).clone();
126 vb.bindings.push((vid.clone(), old_v));
127 vb.vals.insert(vid.to_uint(), new_v);
128 }
129
130 fn unify<T:Clone + InferStr,
131 V:Clone + Vid + ToStr + UnifyVid<T>>(
132 &self,
133 node_a: &Node<V, T>,
134 node_b: &Node<V, T>)
135 -> (V, uint) {
136 // Rank optimization: if you don't know what it is, check
137 // out <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>
138
139 debug!("unify(node_a(id={:?}, rank={:?}), \
140 node_b(id={:?}, rank={:?}))",
141 node_a.root, node_a.rank,
142 node_b.root, node_b.rank);
143
144 if node_a.rank > node_b.rank {
145 // a has greater rank, so a should become b's parent,
146 // i.e., b should redirect to a.
147 self.set(node_b.root.clone(), Redirect(node_a.root.clone()));
148 (node_a.root.clone(), node_a.rank)
149 } else if node_a.rank < node_b.rank {
150 // b has greater rank, so a should redirect to b.
151 self.set(node_a.root.clone(), Redirect(node_b.root.clone()));
152 (node_b.root.clone(), node_b.rank)
153 } else {
154 // If equal, redirect one to the other and increment the
155 // other's rank.
156 assert_eq!(node_a.rank, node_b.rank);
157 self.set(node_b.root.clone(), Redirect(node_a.root.clone()));
158 (node_a.root.clone(), node_a.rank + 1)
159 }
160 }
161
162 }
163
164 // ______________________________________________________________________
165 // Code to handle simple variables like ints, floats---anything that
166 // doesn't have a subtyping relationship we need to worry about.
167
168 pub trait SimplyUnifiable {
169 fn to_type_err(expected_found<Self>) -> ty::type_err;
170 }
171
172 pub fn mk_err<T:SimplyUnifiable>(a_is_expected: bool,
173 a_t: T,
174 b_t: T) -> ures {
175 if a_is_expected {
176 Err(SimplyUnifiable::to_type_err(
177 ty::expected_found {expected: a_t, found: b_t}))
178 } else {
179 Err(SimplyUnifiable::to_type_err(
180 ty::expected_found {expected: b_t, found: a_t}))
181 }
182 }
183
184 pub trait InferCtxtMethods {
185 fn simple_vars<T:Clone + Eq + InferStr + SimplyUnifiable,
186 V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
187 &self,
188 a_is_expected: bool,
189 a_id: V,
190 b_id: V)
191 -> ures;
192 fn simple_var_t<T:Clone + Eq + InferStr + SimplyUnifiable,
193 V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
194 &self,
195 a_is_expected: bool,
196 a_id: V,
197 b: T)
198 -> ures;
199 }
200
201 impl<'a> InferCtxtMethods for InferCtxt<'a> {
202 fn simple_vars<T:Clone + Eq + InferStr + SimplyUnifiable,
203 V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
204 &self,
205 a_is_expected: bool,
206 a_id: V,
207 b_id: V)
208 -> ures {
209 /*!
210 *
211 * Unifies two simple variables. Because simple variables do
212 * not have any subtyping relationships, if both variables
213 * have already been associated with a value, then those two
214 * values must be the same. */
215
216 let node_a = self.get(a_id);
217 let node_b = self.get(b_id);
218 let a_id = node_a.root.clone();
219 let b_id = node_b.root.clone();
220
221 if a_id == b_id { return uok(); }
222
223 let combined = match (&node_a.possible_types, &node_b.possible_types)
224 {
225 (&None, &None) => None,
226 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
227 Some((*v).clone())
228 }
229 (&Some(ref v1), &Some(ref v2)) => {
230 if *v1 != *v2 {
231 return mk_err(a_is_expected, (*v1).clone(), (*v2).clone())
232 }
233 Some((*v1).clone())
234 }
235 };
236
237 let (new_root, new_rank) = self.unify(&node_a, &node_b);
238 self.set(new_root, Root(combined, new_rank));
239 return uok();
240 }
241
242 fn simple_var_t<T:Clone + Eq + InferStr + SimplyUnifiable,
243 V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
244 &self,
245 a_is_expected: bool,
246 a_id: V,
247 b: T)
248 -> ures {
249 /*!
250 *
251 * Sets the value of the variable `a_id` to `b`. Because
252 * simple variables do not have any subtyping relationships,
253 * if `a_id` already has a value, it must be the same as
254 * `b`. */
255
256 let node_a = self.get(a_id);
257 let a_id = node_a.root.clone();
258
259 match node_a.possible_types {
260 None => {
261 self.set(a_id, Root(Some(b), node_a.rank));
262 return uok();
263 }
264
265 Some(ref a_t) => {
266 if *a_t == b {
267 return uok();
268 } else {
269 return mk_err(a_is_expected, (*a_t).clone(), b);
270 }
271 }
272 }
273 }
274 }
275
276 // ______________________________________________________________________
277
278 impl UnifyVid<Bounds<ty::t>> for ty::TyVid {
279 fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
280 -> &'v RefCell<ValsAndBindings<ty::TyVid, Bounds<ty::t>>> {
281 return &infcx.ty_var_bindings;
282 }
283 }
284
285 impl UnifyVid<Option<IntVarValue>> for ty::IntVid {
286 fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
287 -> &'v RefCell<ValsAndBindings<ty::IntVid, Option<IntVarValue>>> {
288 return &infcx.int_var_bindings;
289 }
290 }
291
292 impl SimplyUnifiable for IntVarValue {
293 fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err {
294 return ty::terr_int_mismatch(err);
295 }
296 }
297
298 impl UnifyVid<Option<ast::FloatTy>> for ty::FloatVid {
299 fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
300 -> &'v RefCell<ValsAndBindings<ty::FloatVid, Option<ast::FloatTy>>> {
301 return &infcx.float_var_bindings;
302 }
303 }
304
305 impl SimplyUnifiable for ast::FloatTy {
306 fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err {
307 return ty::terr_float_mismatch(err);
308 }
309 }
librustc/middle/typeck/infer/unify.rs:38:1-38:1 -trait- definition:
pub trait UnifyVid<T> {
fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
-> &'v RefCell<ValsAndBindings<Self, T>>;
references:- 2440: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
41: -> &'v RefCell<ValsAndBindings<Self, T>>;
42: }
--
278: impl UnifyVid<Bounds<ty::t>> for ty::TyVid {
279: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
--
298: impl UnifyVid<Option<ast::FloatTy>> for ty::FloatVid {
299: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
librustc/middle/typeck/infer/lattice.rs:
98: fn set_var_to_merged_bounds<T:Clone + InferStr + LatticeValue,
99: V:Clone+Eq+ToStr+Vid+UnifyVid<Bounds<T>>>(
100: &self,
--
191: fn t_sub_var<T:Clone + InferStr + LatticeValue,
192: V:Clone + Eq + ToStr + Vid + UnifyVid<Bounds<T>>>(
193: &self,
--
434: T:Clone + InferStr + LatticeValue,
435: V:Clone + Eq + ToStr + Vid + UnifyVid<Bounds<T>>>(
436: this: &L, // defines whether we want LUB or GLB
--
480: T:Clone + InferStr + LatticeValue,
481: V:Clone + Eq + ToStr + Vid + UnifyVid<Bounds<T>>>(
482: this: &L,
librustc/middle/typeck/infer/unify.rs:
285: impl UnifyVid<Option<IntVarValue>> for ty::IntVid {
286: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
librustc/middle/typeck/infer/unify.rs:167:1-167:1 -trait- definition:
pub trait SimplyUnifiable {
fn to_type_err(expected_found<Self>) -> ty::type_err;
}
references:- 8184: pub trait InferCtxtMethods {
185: fn simple_vars<T:Clone + Eq + InferStr + SimplyUnifiable,
186: V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
--
201: impl<'a> InferCtxtMethods for InferCtxt<'a> {
202: fn simple_vars<T:Clone + Eq + InferStr + SimplyUnifiable,
203: V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
--
242: fn simple_var_t<T:Clone + Eq + InferStr + SimplyUnifiable,
243: V:Clone + Eq + Vid + ToStr + UnifyVid<Option<T>>>(
--
292: impl SimplyUnifiable for IntVarValue {
293: fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err {
--
305: impl SimplyUnifiable for ast::FloatTy {
306: fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err {
librustc/middle/typeck/infer/unify.rs:27:1-27:1 -struct- definition:
pub struct ValsAndBindings<V, T> {
pub vals: SmallIntMap<VarValue<V, T>>,
pub bindings: Vec<(V, VarValue<V, T>)> ,
references:- 12librustc/middle/typeck/infer/mod.rs:
262: fn new_ValsAndBindings<V:Clone,T:Clone>() -> ValsAndBindings<V, T> {
263: ValsAndBindings {
264: vals: SmallIntMap::new(),
librustc/middle/typeck/infer/unify.rs:
286: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
287: -> &'v RefCell<ValsAndBindings<ty::IntVid, Option<IntVarValue>>> {
288: return &infcx.int_var_bindings;
--
299: fn appropriate_vals_and_bindings<'v>(infcx: &'v InferCtxt)
300: -> &'v RefCell<ValsAndBindings<ty::FloatVid, Option<ast::FloatTy>>> {
301: return &infcx.float_var_bindings;
librustc/middle/typeck/infer/mod.rs:
582: fn next_simple_var<V:Clone,T:Clone>(counter: &mut uint,
583: bindings: &mut ValsAndBindings<V,
584: Option<T>>)
librustc/middle/typeck/infer/unify.rs:80:8-80:8 -fn- definition:
fn helper<T:Clone, V:Clone+Eq+Vid>(
tcx: &ty::ctxt,
vb: &mut ValsAndBindings<V,T>,
references:- 294: Redirect(vid) => {
95: let node: Node<V,T> = helper(tcx, vb, vid.clone());
96: if node.root != vid {
librustc/middle/typeck/infer/unify.rs:171:1-171:1 -fn- definition:
pub fn mk_err<T:SimplyUnifiable>(a_is_expected: bool,
a_t: T,
b_t: T) -> ures {
references:- 2268: } else {
269: return mk_err(a_is_expected, (*a_t).clone(), b);
270: }
librustc/middle/typeck/infer/unify.rs:22:19-22:19 -enum- definition:
pub enum VarValue<V, T> {
Redirect(V),
Root(T, uint),
references:- 729: pub vals: SmallIntMap<VarValue<V, T>>,
30: pub bindings: Vec<(V, VarValue<V, T>)> ,
31: }
--
113: vid: V,
114: new_v: VarValue<V, T>) {
115: /*!
librustc/middle/typeck/infer/to_str.rs:
69: impl<V:Vid + ToStr,T:InferStr> InferStr for VarValue<V, T> {
70: fn inf_str(&self, cx: &InferCtxt) -> ~str {
librustc/middle/typeck/infer/unify.rs:
28: pub struct ValsAndBindings<V, T> {
29: pub vals: SmallIntMap<VarValue<V, T>>,
30: pub bindings: Vec<(V, VarValue<V, T>)> ,
librustc/middle/typeck/infer/unify.rs:32:1-32:1 -struct- definition:
pub struct Node<V, T> {
pub root: V,
pub possible_types: T,
references:- 9103: Root(pt, rk) => {
104: Node {root: vid, possible_types: pt, rank: rk}
105: }
--
133: node_a: &Node<V, T>,
134: node_b: &Node<V, T>)
135: -> (V, uint) {