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 middle::ty::{BuiltinBounds};
13 use middle::ty;
14 use middle::ty::TyVar;
15 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
16 use middle::typeck::infer::combine::*;
17 use middle::typeck::infer::{cres, CresCompare};
18 use middle::typeck::infer::glb::Glb;
19 use middle::typeck::infer::InferCtxt;
20 use middle::typeck::infer::lattice::CombineFieldsLatticeMethods;
21 use middle::typeck::infer::lub::Lub;
22 use middle::typeck::infer::then;
23 use middle::typeck::infer::to_str::InferStr;
24 use middle::typeck::infer::{TypeTrace, Subtype};
25 use util::common::{indenter};
26 use util::ppaux::bound_region_to_str;
27
28 use syntax::ast::{Onceness, FnStyle};
29
30 pub struct Sub<'f>(pub CombineFields<'f>); // "subtype", "subregion" etc
31
32 impl<'f> Sub<'f> {
33 pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f> { let Sub(ref v) = *self; v }
34 }
35
36 impl<'f> Combine for Sub<'f> {
37 fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.get_ref().infcx }
38 fn tag(&self) -> ~str { "sub".to_owned() }
39 fn a_is_expected(&self) -> bool { self.get_ref().a_is_expected }
40 fn trace(&self) -> TypeTrace { self.get_ref().trace.clone() }
41
42 fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.get_ref().clone()) }
43 fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.get_ref().clone()) }
44 fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.get_ref().clone()) }
45
46 fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
47 let opp = CombineFields {
48 a_is_expected: !self.get_ref().a_is_expected,
49 ..self.get_ref().clone()
50 };
51 Sub(opp).tys(b, a)
52 }
53
54 fn contraregions(&self, a: ty::Region, b: ty::Region)
55 -> cres<ty::Region> {
56 let opp = CombineFields {
57 a_is_expected: !self.get_ref().a_is_expected,
58 ..self.get_ref().clone()
59 };
60 Sub(opp).regions(b, a)
61 }
62
63 fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region> {
64 debug!("{}.regions({}, {})",
65 self.tag(),
66 a.inf_str(self.get_ref().infcx),
67 b.inf_str(self.get_ref().infcx));
68 self.get_ref().infcx.region_vars.make_subregion(Subtype(self.trace()), a, b);
69 Ok(a)
70 }
71
72 fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt> {
73 debug!("mts({} <: {})", a.inf_str(self.get_ref().infcx), b.inf_str(self.get_ref().infcx));
74
75 if a.mutbl != b.mutbl {
76 return Err(ty::terr_mutability);
77 }
78
79 match b.mutbl {
80 MutMutable => {
81 // If supertype is mut, subtype must match exactly
82 // (i.e., invariant if mut):
83 eq_tys(self, a.ty, b.ty).then(|| Ok(*a))
84 }
85 MutImmutable => {
86 // Otherwise we can be covariant:
87 self.tys(a.ty, b.ty).and_then(|_t| Ok(*a) )
88 }
89 }
90 }
91
92 fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle> {
93 self.lub().fn_styles(a, b).compare(b, || {
94 ty::terr_fn_style_mismatch(expected_found(self, a, b))
95 })
96 }
97
98 fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness> {
99 self.lub().oncenesses(a, b).compare(b, || {
100 ty::terr_onceness_mismatch(expected_found(self, a, b))
101 })
102 }
103
104 fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds> {
105 // More bounds is a subtype of fewer bounds.
106 //
107 // e.g., fn:Copy() <: fn(), because the former is a function
108 // that only closes over copyable things, but the latter is
109 // any function at all.
110 if a.contains(b) {
111 Ok(a)
112 } else {
113 Err(ty::terr_builtin_bounds(expected_found(self, a, b)))
114 }
115 }
116
117 fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
118 debug!("{}.tys({}, {})", self.tag(),
119 a.inf_str(self.get_ref().infcx), b.inf_str(self.get_ref().infcx));
120 if a == b { return Ok(a); }
121 let _indenter = indenter();
122 match (&ty::get(a).sty, &ty::get(b).sty) {
123 (&ty::ty_bot, _) => {
124 Ok(a)
125 }
126
127 (&ty::ty_infer(TyVar(a_id)), &ty::ty_infer(TyVar(b_id))) => {
128 if_ok!(self.get_ref().var_sub_var(a_id, b_id));
129 Ok(a)
130 }
131 (&ty::ty_infer(TyVar(a_id)), _) => {
132 if_ok!(self.get_ref().var_sub_t(a_id, b));
133 Ok(a)
134 }
135 (_, &ty::ty_infer(TyVar(b_id))) => {
136 if_ok!(self.get_ref().t_sub_var(a, b_id));
137 Ok(a)
138 }
139
140 (_, &ty::ty_bot) => {
141 Err(ty::terr_sorts(expected_found(self, a, b)))
142 }
143
144 _ => {
145 super_tys(self, a, b)
146 }
147 }
148 }
149
150 fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
151 debug!("fn_sigs(a={}, b={})",
152 a.inf_str(self.get_ref().infcx), b.inf_str(self.get_ref().infcx));
153 let _indenter = indenter();
154
155 // Rather than checking the subtype relationship between `a` and `b`
156 // as-is, we need to do some extra work here in order to make sure
157 // that function subtyping works correctly with respect to regions
158 //
159 // Note: this is a subtle algorithm. For a full explanation,
160 // please see the large comment in `region_inference.rs`.
161
162 // Take a snapshot. We'll never roll this back, but in later
163 // phases we do want to be able to examine "all bindings that
164 // were created as part of this type comparison", and making a
165 // snapshot is a convenient way to do that.
166 let snapshot = self.get_ref().infcx.region_vars.start_snapshot();
167
168 // First, we instantiate each bound region in the subtype with a fresh
169 // region variable.
170 let (a_sig, _) =
171 self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
172 self.trace(), a);
173
174 // Second, we instantiate each bound region in the supertype with a
175 // fresh concrete region.
176 let (skol_map, b_sig) = {
177 replace_late_bound_regions_in_fn_sig(self.get_ref().infcx.tcx, b, |br| {
178 let skol = self.get_ref().infcx.region_vars.new_skolemized(br);
179 debug!("Bound region {} skolemized to {:?}",
180 bound_region_to_str(self.get_ref().infcx.tcx, "", false, br),
181 skol);
182 skol
183 })
184 };
185
186 debug!("a_sig={}", a_sig.inf_str(self.get_ref().infcx));
187 debug!("b_sig={}", b_sig.inf_str(self.get_ref().infcx));
188
189 // Compare types now that bound regions have been replaced.
190 let sig = if_ok!(super_fn_sigs(self, &a_sig, &b_sig));
191
192 // Presuming type comparison succeeds, we need to check
193 // that the skolemized regions do not "leak".
194 let new_vars =
195 self.get_ref().infcx.region_vars.vars_created_since_snapshot(snapshot);
196 for (&skol_br, &skol) in skol_map.iter() {
197 let tainted = self.get_ref().infcx.region_vars.tainted(snapshot, skol);
198 for tainted_region in tainted.iter() {
199 // Each skolemized should only be relatable to itself
200 // or new variables:
201 match *tainted_region {
202 ty::ReInfer(ty::ReVar(ref vid)) => {
203 if new_vars.iter().any(|x| x == vid) { continue; }
204 }
205 _ => {
206 if *tainted_region == skol { continue; }
207 }
208 };
209
210 // A is not as polymorphic as B:
211 if self.a_is_expected() {
212 return Err(ty::terr_regions_insufficiently_polymorphic(
213 skol_br, *tainted_region));
214 } else {
215 return Err(ty::terr_regions_overly_polymorphic(
216 skol_br, *tainted_region));
217 }
218 }
219 }
220
221 return Ok(sig);
222 }
223
224 }