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
;
41 use super::{MiscVariable, TypeTrace}
;
42 use super::type_variable
::{RelationDir, BiTo, EqTo, SubtypeOf, SupertypeOf}
;
44 use ty
::{IntType, UintType}
;
45 use ty
::{self, Ty, TyCtxt}
;
46 use ty
::error
::TypeError
;
47 use ty
::fold
::TypeFoldable
;
48 use ty
::relate
::{RelateResult, TypeRelation}
;
49 use traits
::PredicateObligations
;
55 pub struct CombineFields
<'infcx
, 'gcx
: 'infcx
+'tcx
, 'tcx
: 'infcx
> {
56 pub infcx
: &'infcx InferCtxt
<'infcx
, 'gcx
, 'tcx
>,
57 pub trace
: TypeTrace
<'tcx
>,
58 pub cause
: Option
<ty
::relate
::Cause
>,
59 pub obligations
: PredicateObligations
<'tcx
>,
62 impl<'infcx
, 'gcx
, 'tcx
> InferCtxt
<'infcx
, 'gcx
, 'tcx
> {
63 pub fn super_combine_tys
<R
>(&self,
67 -> RelateResult
<'tcx
, Ty
<'tcx
>>
68 where R
: TypeRelation
<'infcx
, 'gcx
, 'tcx
>
70 let a_is_expected
= relation
.a_is_expected();
72 match (&a
.sty
, &b
.sty
) {
73 // Relate integral variables to other types
74 (&ty
::TyInfer(ty
::IntVar(a_id
)), &ty
::TyInfer(ty
::IntVar(b_id
))) => {
75 self.int_unification_table
77 .unify_var_var(a_id
, b_id
)
78 .map_err(|e
| int_unification_error(a_is_expected
, e
))?
;
81 (&ty
::TyInfer(ty
::IntVar(v_id
)), &ty
::TyInt(v
)) => {
82 self.unify_integral_variable(a_is_expected
, v_id
, IntType(v
))
84 (&ty
::TyInt(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
85 self.unify_integral_variable(!a_is_expected
, v_id
, IntType(v
))
87 (&ty
::TyInfer(ty
::IntVar(v_id
)), &ty
::TyUint(v
)) => {
88 self.unify_integral_variable(a_is_expected
, v_id
, UintType(v
))
90 (&ty
::TyUint(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
91 self.unify_integral_variable(!a_is_expected
, v_id
, UintType(v
))
94 // Relate floating-point variables to other types
95 (&ty
::TyInfer(ty
::FloatVar(a_id
)), &ty
::TyInfer(ty
::FloatVar(b_id
))) => {
96 self.float_unification_table
98 .unify_var_var(a_id
, b_id
)
99 .map_err(|e
| float_unification_error(relation
.a_is_expected(), e
))?
;
102 (&ty
::TyInfer(ty
::FloatVar(v_id
)), &ty
::TyFloat(v
)) => {
103 self.unify_float_variable(a_is_expected
, v_id
, v
)
105 (&ty
::TyFloat(v
), &ty
::TyInfer(ty
::FloatVar(v_id
))) => {
106 self.unify_float_variable(!a_is_expected
, v_id
, v
)
109 // All other cases of inference are errors
110 (&ty
::TyInfer(_
), _
) |
111 (_
, &ty
::TyInfer(_
)) => {
112 Err(TypeError
::Sorts(ty
::relate
::expected_found(relation
, &a
, &b
)))
117 ty
::relate
::super_relate_tys(relation
, a
, b
)
122 fn unify_integral_variable(&self,
123 vid_is_expected
: bool
,
125 val
: ty
::IntVarValue
)
126 -> RelateResult
<'tcx
, Ty
<'tcx
>>
128 self.int_unification_table
130 .unify_var_value(vid
, val
)
131 .map_err(|e
| int_unification_error(vid_is_expected
, e
))?
;
133 IntType(v
) => Ok(self.tcx
.mk_mach_int(v
)),
134 UintType(v
) => Ok(self.tcx
.mk_mach_uint(v
)),
138 fn unify_float_variable(&self,
139 vid_is_expected
: bool
,
142 -> RelateResult
<'tcx
, Ty
<'tcx
>>
144 self.float_unification_table
146 .unify_var_value(vid
, val
)
147 .map_err(|e
| float_unification_error(vid_is_expected
, e
))?
;
148 Ok(self.tcx
.mk_mach_float(val
))
152 impl<'infcx
, 'gcx
, 'tcx
> CombineFields
<'infcx
, 'gcx
, 'tcx
> {
153 pub fn tcx(&self) -> TyCtxt
<'infcx
, 'gcx
, 'tcx
> {
157 pub fn equate
<'a
>(&'a
mut self, a_is_expected
: bool
) -> Equate
<'a
, 'infcx
, 'gcx
, 'tcx
> {
158 Equate
::new(self, a_is_expected
)
161 pub fn bivariate
<'a
>(&'a
mut self, a_is_expected
: bool
) -> Bivariate
<'a
, 'infcx
, 'gcx
, 'tcx
> {
162 Bivariate
::new(self, a_is_expected
)
165 pub fn sub
<'a
>(&'a
mut self, a_is_expected
: bool
) -> Sub
<'a
, 'infcx
, 'gcx
, 'tcx
> {
166 Sub
::new(self, a_is_expected
)
169 pub fn lub
<'a
>(&'a
mut self, a_is_expected
: bool
) -> Lub
<'a
, 'infcx
, 'gcx
, 'tcx
> {
170 Lub
::new(self, a_is_expected
)
173 pub fn glb
<'a
>(&'a
mut self, a_is_expected
: bool
) -> Glb
<'a
, 'infcx
, 'gcx
, 'tcx
> {
174 Glb
::new(self, a_is_expected
)
177 pub fn instantiate(&mut self,
182 -> RelateResult
<'tcx
, ()>
184 let mut stack
= Vec
::new();
185 stack
.push((a_ty
, dir
, b_vid
));
187 // For each turn of the loop, we extract a tuple
189 // (a_ty, dir, b_vid)
191 // to relate. Here dir is either SubtypeOf or
192 // SupertypeOf. The idea is that we should ensure that
193 // the type `a_ty` is a subtype or supertype (respectively) of the
194 // type to which `b_vid` is bound.
196 // If `b_vid` has not yet been instantiated with a type
197 // (which is always true on the first iteration, but not
198 // necessarily true on later iterations), we will first
199 // instantiate `b_vid` with a *generalized* version of
200 // `a_ty`. Generalization introduces other inference
201 // variables wherever subtyping could occur (at time of
202 // this writing, this means replacing free regions with
203 // region variables).
204 let (a_ty
, dir
, b_vid
) = match stack
.pop() {
208 // Get the actual variable that b_vid has been inferred to
209 let (b_vid
, b_ty
) = {
210 let mut variables
= self.infcx
.type_variables
.borrow_mut();
211 let b_vid
= variables
.root_var(b_vid
);
212 (b_vid
, variables
.probe_root(b_vid
))
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
= match b_ty
{
224 Some(t
) => t
, // ...already instantiated.
225 None
=> { // ...not yet instantiated:
226 // Generalize type if necessary.
227 let generalized_ty
= match dir
{
228 EqTo
=> self.generalize(a_ty
, b_vid
, false),
229 BiTo
| SupertypeOf
| SubtypeOf
=> self.generalize(a_ty
, b_vid
, true),
231 debug
!("instantiate(a_ty={:?}, dir={:?}, \
232 b_vid={:?}, generalized_ty={:?})",
235 self.infcx
.type_variables
237 .instantiate_and_push(
238 b_vid
, generalized_ty
, &mut stack
);
243 // The original triple was `(a_ty, dir, b_vid)` -- now we have
244 // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
246 // FIXME(#16847): This code is non-ideal because all these subtype
247 // relations wind up attributed to the same spans. We need
248 // to associate causes/spans with each of the relations in
249 // the stack to get this right.
251 BiTo
=> self.bivariate(a_is_expected
).relate(&a_ty
, &b_ty
),
252 EqTo
=> self.equate(a_is_expected
).relate(&a_ty
, &b_ty
),
253 SubtypeOf
=> self.sub(a_is_expected
).relate(&a_ty
, &b_ty
),
254 SupertypeOf
=> self.sub(a_is_expected
).relate_with_variance(
255 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(TypeError
::CyclicTy
)
288 struct Generalizer
<'cx
, 'gcx
: 'cx
+'tcx
, 'tcx
: 'cx
> {
289 infcx
: &'cx InferCtxt
<'cx
, 'gcx
, 'tcx
>,
292 make_region_vars
: bool
,
293 cycle_detected
: bool
,
296 impl<'cx
, 'gcx
, 'tcx
> ty
::fold
::TypeFolder
<'gcx
, 'tcx
> for Generalizer
<'cx
, 'gcx
, 'tcx
> {
297 fn tcx
<'a
>(&'a
self) -> TyCtxt
<'a
, 'gcx
, '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 let mut variables
= self.infcx
.type_variables
.borrow_mut();
312 let vid
= variables
.root_var(vid
);
313 if vid
== self.for_vid
{
314 self.cycle_detected
= true;
317 match variables
.probe_root(vid
) {
327 t
.super_fold_with(self)
332 fn fold_region(&mut self, r
: &'tcx ty
::Region
) -> &'tcx ty
::Region
{
334 // Never make variables for regions bound within the type itself,
335 // nor for erased regions.
336 ty
::ReLateBound(..) |
337 ty
::ReErased
=> { return r; }
339 // Early-bound regions should really have been substituted away before
340 // we get to this point.
341 ty
::ReEarlyBound(..) => {
344 "Encountered early bound region when generalizing: {:?}",
348 // Always make a fresh region variable for skolemized regions;
349 // the higher-ranked decision procedures rely on this.
350 ty
::ReSkolemized(..) => { }
352 // For anything else, we make a region variable, unless we
353 // are *equating*, in which case it's just wasteful.
359 if !self.make_region_vars
{
365 // FIXME: This is non-ideal because we don't give a
366 // very descriptive origin for this region variable.
367 self.infcx
.next_region_var(MiscVariable(self.span
))
371 pub trait RelateResultCompare
<'tcx
, T
> {
372 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
373 F
: FnOnce() -> TypeError
<'tcx
>;
376 impl<'tcx
, T
:Clone
+ PartialEq
> RelateResultCompare
<'tcx
, T
> for RelateResult
<'tcx
, T
> {
377 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
378 F
: FnOnce() -> TypeError
<'tcx
>,
380 self.clone().and_then(|s
| {
390 fn int_unification_error
<'tcx
>(a_is_expected
: bool
, v
: (ty
::IntVarValue
, ty
::IntVarValue
))
394 TypeError
::IntMismatch(ty
::relate
::expected_found_bool(a_is_expected
, &a
, &b
))
397 fn float_unification_error
<'tcx
>(a_is_expected
: bool
,
398 v
: (ast
::FloatTy
, ast
::FloatTy
))
402 TypeError
::FloatMismatch(ty
::relate
::expected_found_bool(a_is_expected
, &a
, &b
))