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.
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.
11 ///////////////////////////////////////////////////////////////////////////
14 // There are four type combiners: equate, sub, lub, and glb. Each
15 // implements the trait `Combine` and contains methods for combining
16 // two instances of various things and yielding a new instance. These
17 // combiner methods always yield a `Result<T>`. There is a lot of
18 // common code for these operations, implemented as default methods on
19 // the `Combine` trait.
21 // Each operation may have side-effects on the inference context,
22 // though these can be unrolled using snapshots. On success, the
23 // LUB/GLB operations return the appropriate bound. The Eq and Sub
24 // operations generally return the first operand.
28 // When you are relating two things which have a contravariant
29 // relationship, you should use `contratys()` or `contraregions()`,
30 // rather than inversing the order of arguments! This is necessary
31 // because the order of arguments is not relevant for LUB and GLB. It
32 // is also useful to track which value is the "expected" value in
33 // terms of error reporting.
35 use super::bivariate
::Bivariate
;
36 use super::equate
::Equate
;
40 use super::{InferCtxt}
;
41 use super::{MiscVariable, TypeTrace}
;
42 use super::type_variable
::{RelationDir, BiTo, EqTo, SubtypeOf, SupertypeOf}
;
44 use middle
::ty
::{TyVar}
;
45 use middle
::ty
::{IntType, UintType}
;
46 use middle
::ty
::{self, Ty}
;
48 use middle
::ty_fold
::{TypeFolder, TypeFoldable}
;
49 use middle
::ty_relate
::{self, Relate, RelateResult, TypeRelation}
;
52 use syntax
::codemap
::Span
;
55 pub struct CombineFields
<'a
, 'tcx
: 'a
> {
56 pub infcx
: &'a InferCtxt
<'a
, 'tcx
>,
57 pub a_is_expected
: bool
,
58 pub trace
: TypeTrace
<'tcx
>,
59 pub cause
: Option
<ty_relate
::Cause
>,
62 pub fn super_combine_tys
<'a
,'tcx
:'a
,R
>(infcx
: &InferCtxt
<'a
, 'tcx
>,
66 -> RelateResult
<'tcx
, Ty
<'tcx
>>
67 where R
: TypeRelation
<'a
,'tcx
>
69 let a_is_expected
= relation
.a_is_expected();
71 match (&a
.sty
, &b
.sty
) {
72 // Relate integral variables to other types
73 (&ty
::TyInfer(ty
::IntVar(a_id
)), &ty
::TyInfer(ty
::IntVar(b_id
))) => {
74 try
!(infcx
.int_unification_table
76 .unify_var_var(a_id
, b_id
)
77 .map_err(|e
| int_unification_error(a_is_expected
, e
)));
80 (&ty
::TyInfer(ty
::IntVar(v_id
)), &ty
::TyInt(v
)) => {
81 unify_integral_variable(infcx
, a_is_expected
, v_id
, IntType(v
))
83 (&ty
::TyInt(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
84 unify_integral_variable(infcx
, !a_is_expected
, v_id
, IntType(v
))
86 (&ty
::TyInfer(ty
::IntVar(v_id
)), &ty
::TyUint(v
)) => {
87 unify_integral_variable(infcx
, a_is_expected
, v_id
, UintType(v
))
89 (&ty
::TyUint(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
90 unify_integral_variable(infcx
, !a_is_expected
, v_id
, UintType(v
))
93 // Relate floating-point variables to other types
94 (&ty
::TyInfer(ty
::FloatVar(a_id
)), &ty
::TyInfer(ty
::FloatVar(b_id
))) => {
95 try
!(infcx
.float_unification_table
97 .unify_var_var(a_id
, b_id
)
98 .map_err(|e
| float_unification_error(relation
.a_is_expected(), e
)));
101 (&ty
::TyInfer(ty
::FloatVar(v_id
)), &ty
::TyFloat(v
)) => {
102 unify_float_variable(infcx
, a_is_expected
, v_id
, v
)
104 (&ty
::TyFloat(v
), &ty
::TyInfer(ty
::FloatVar(v_id
))) => {
105 unify_float_variable(infcx
, !a_is_expected
, v_id
, v
)
108 // All other cases of inference are errors
109 (&ty
::TyInfer(_
), _
) |
110 (_
, &ty
::TyInfer(_
)) => {
111 Err(ty
::terr_sorts(ty_relate
::expected_found(relation
, &a
, &b
)))
116 ty_relate
::super_relate_tys(relation
, a
, b
)
121 fn unify_integral_variable
<'a
,'tcx
>(infcx
: &InferCtxt
<'a
,'tcx
>,
122 vid_is_expected
: bool
,
124 val
: ty
::IntVarValue
)
125 -> RelateResult
<'tcx
, Ty
<'tcx
>>
128 .int_unification_table
130 .unify_var_value(vid
, val
)
131 .map_err(|e
| int_unification_error(vid_is_expected
, e
)));
133 IntType(v
) => Ok(ty
::mk_mach_int(infcx
.tcx
, v
)),
134 UintType(v
) => Ok(ty
::mk_mach_uint(infcx
.tcx
, v
)),
138 fn unify_float_variable
<'a
,'tcx
>(infcx
: &InferCtxt
<'a
,'tcx
>,
139 vid_is_expected
: bool
,
142 -> RelateResult
<'tcx
, Ty
<'tcx
>>
145 .float_unification_table
147 .unify_var_value(vid
, val
)
148 .map_err(|e
| float_unification_error(vid_is_expected
, e
)));
149 Ok(ty
::mk_mach_float(infcx
.tcx
, val
))
152 impl<'a
, 'tcx
> CombineFields
<'a
, 'tcx
> {
153 pub fn tcx(&self) -> &'a ty
::ctxt
<'tcx
> {
157 pub fn switch_expected(&self) -> CombineFields
<'a
, 'tcx
> {
159 a_is_expected
: !self.a_is_expected
,
164 pub fn equate(&self) -> Equate
<'a
, 'tcx
> {
165 Equate
::new(self.clone())
168 pub fn bivariate(&self) -> Bivariate
<'a
, 'tcx
> {
169 Bivariate
::new(self.clone())
172 pub fn sub(&self) -> Sub
<'a
, 'tcx
> {
173 Sub
::new(self.clone())
176 pub fn lub(&self) -> Lub
<'a
, 'tcx
> {
177 Lub
::new(self.clone())
180 pub fn glb(&self) -> Glb
<'a
, 'tcx
> {
181 Glb
::new(self.clone())
184 pub fn instantiate(&self,
188 -> RelateResult
<'tcx
, ()>
190 let mut stack
= Vec
::new();
191 stack
.push((a_ty
, dir
, b_vid
));
193 // For each turn of the loop, we extract a tuple
195 // (a_ty, dir, b_vid)
197 // to relate. Here dir is either SubtypeOf or
198 // SupertypeOf. The idea is that we should ensure that
199 // the type `a_ty` is a subtype or supertype (respectively) of the
200 // type to which `b_vid` is bound.
202 // If `b_vid` has not yet been instantiated with a type
203 // (which is always true on the first iteration, but not
204 // necessarily true on later iterations), we will first
205 // instantiate `b_vid` with a *generalized* version of
206 // `a_ty`. Generalization introduces other inference
207 // variables wherever subtyping could occur (at time of
208 // this writing, this means replacing free regions with
209 // region variables).
210 let (a_ty
, dir
, b_vid
) = match stack
.pop() {
215 debug
!("instantiate(a_ty={:?} dir={:?} b_vid={:?})",
220 // Check whether `vid` has been instantiated yet. If not,
221 // make a generalized form of `ty` and instantiate with
223 let b_ty
= self.infcx
.type_variables
.borrow().probe(b_vid
);
224 let b_ty
= match b_ty
{
225 Some(t
) => t
, // ...already instantiated.
226 None
=> { // ...not yet instantiated:
227 // Generalize type if necessary.
228 let generalized_ty
= try
!(match dir
{
229 EqTo
=> self.generalize(a_ty
, b_vid
, false),
230 BiTo
| SupertypeOf
| SubtypeOf
=> self.generalize(a_ty
, b_vid
, true),
232 debug
!("instantiate(a_ty={:?}, dir={:?}, \
233 b_vid={:?}, generalized_ty={:?})",
236 self.infcx
.type_variables
238 .instantiate_and_push(
239 b_vid
, generalized_ty
, &mut stack
);
244 // The original triple was `(a_ty, dir, b_vid)` -- now we have
245 // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
247 // FIXME(#16847): This code is non-ideal because all these subtype
248 // relations wind up attributed to the same spans. We need
249 // to associate causes/spans with each of the relations in
250 // the stack to get this right.
252 BiTo
=> self.bivariate().relate(&a_ty
, &b_ty
),
253 EqTo
=> self.equate().relate(&a_ty
, &b_ty
),
254 SubtypeOf
=> self.sub().relate(&a_ty
, &b_ty
),
255 SupertypeOf
=> self.sub().relate_with_variance(ty
::Contravariant
, &a_ty
, &b_ty
),
262 /// Attempts to generalize `ty` for the type variable `for_vid`. This checks for cycle -- that
263 /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also
264 /// replace all regions with fresh variables. Returns `TyError` in the case of a cycle, `Ok`
269 make_region_vars
: bool
)
270 -> RelateResult
<'tcx
, Ty
<'tcx
>>
272 let mut generalize
= Generalizer
{
274 span
: self.trace
.origin
.span(),
276 make_region_vars
: make_region_vars
,
277 cycle_detected
: false
279 let u
= ty
.fold_with(&mut generalize
);
280 if generalize
.cycle_detected
{
281 Err(ty
::terr_cyclic_ty
)
288 struct Generalizer
<'cx
, 'tcx
:'cx
> {
289 infcx
: &'cx InferCtxt
<'cx
, 'tcx
>,
292 make_region_vars
: bool
,
293 cycle_detected
: bool
,
296 impl<'cx
, 'tcx
> ty_fold
::TypeFolder
<'tcx
> for Generalizer
<'cx
, 'tcx
> {
297 fn tcx(&self) -> &ty
::ctxt
<'tcx
> {
301 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
302 // Check to see whether the type we are genealizing references
303 // `vid`. At the same time, also update any type variables to
304 // the values that they are bound to. This is needed to truly
305 // check for cycles, but also just makes things readable.
307 // (In particular, you could have something like `$0 = Box<$1>`
308 // where `$1` has already been instantiated with `Box<$0>`)
310 ty
::TyInfer(ty
::TyVar(vid
)) => {
311 if vid
== self.for_vid
{
312 self.cycle_detected
= true;
315 match self.infcx
.type_variables
.borrow().probe(vid
) {
316 Some(u
) => self.fold_ty(u
),
322 ty_fold
::super_fold_ty(self, t
)
327 fn fold_region(&mut self, r
: ty
::Region
) -> ty
::Region
{
329 // Never make variables for regions bound within the type itself.
330 ty
::ReLateBound(..) => { return r; }
332 // Early-bound regions should really have been substituted away before
333 // we get to this point.
334 ty
::ReEarlyBound(..) => {
335 self.tcx().sess
.span_bug(
337 &format
!("Encountered early bound region when generalizing: {:?}",
341 // Always make a fresh region variable for skolemized regions;
342 // the higher-ranked decision procedures rely on this.
343 ty
::ReInfer(ty
::ReSkolemized(..)) => { }
345 // For anything else, we make a region variable, unless we
346 // are *equating*, in which case it's just wasteful.
350 ty
::ReInfer(ty
::ReVar(..)) |
352 if !self.make_region_vars
{
358 // FIXME: This is non-ideal because we don't give a
359 // very descriptive origin for this region variable.
360 self.infcx
.next_region_var(MiscVariable(self.span
))
364 pub trait RelateResultCompare
<'tcx
, T
> {
365 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
366 F
: FnOnce() -> ty
::type_err
<'tcx
>;
369 impl<'tcx
, T
:Clone
+ PartialEq
> RelateResultCompare
<'tcx
, T
> for RelateResult
<'tcx
, T
> {
370 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
371 F
: FnOnce() -> ty
::type_err
<'tcx
>,
373 self.clone().and_then(|s
| {
383 fn int_unification_error
<'tcx
>(a_is_expected
: bool
, v
: (ty
::IntVarValue
, ty
::IntVarValue
))
384 -> ty
::type_err
<'tcx
>
387 ty
::terr_int_mismatch(ty_relate
::expected_found_bool(a_is_expected
, &a
, &b
))
390 fn float_unification_error
<'tcx
>(a_is_expected
: bool
,
391 v
: (ast
::FloatTy
, ast
::FloatTy
))
392 -> ty
::type_err
<'tcx
>
395 ty
::terr_float_mismatch(ty_relate
::expected_found_bool(a_is_expected
, &a
, &b
))