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
::{TypeFolder, TypeFoldable}
;
48 use ty
::relate
::{Relate, RelateResult, TypeRelation}
;
49 use traits
::PredicateObligations
;
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
>,
60 pub obligations
: PredicateObligations
<'tcx
>,
63 pub fn super_combine_tys
<'a
,'tcx
:'a
,R
>(infcx
: &InferCtxt
<'a
, 'tcx
>,
67 -> RelateResult
<'tcx
, Ty
<'tcx
>>
68 where R
: TypeRelation
<'a
,'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 infcx
.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 unify_integral_variable(infcx
, a_is_expected
, v_id
, IntType(v
))
84 (&ty
::TyInt(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
85 unify_integral_variable(infcx
, !a_is_expected
, v_id
, IntType(v
))
87 (&ty
::TyInfer(ty
::IntVar(v_id
)), &ty
::TyUint(v
)) => {
88 unify_integral_variable(infcx
, a_is_expected
, v_id
, UintType(v
))
90 (&ty
::TyUint(v
), &ty
::TyInfer(ty
::IntVar(v_id
))) => {
91 unify_integral_variable(infcx
, !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 infcx
.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 unify_float_variable(infcx
, a_is_expected
, v_id
, v
)
105 (&ty
::TyFloat(v
), &ty
::TyInfer(ty
::FloatVar(v_id
))) => {
106 unify_float_variable(infcx
, !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
<'a
,'tcx
>(infcx
: &InferCtxt
<'a
,'tcx
>,
123 vid_is_expected
: bool
,
125 val
: ty
::IntVarValue
)
126 -> RelateResult
<'tcx
, Ty
<'tcx
>>
128 infcx
.int_unification_table
130 .unify_var_value(vid
, val
)
131 .map_err(|e
| int_unification_error(vid_is_expected
, e
))?
;
133 IntType(v
) => Ok(infcx
.tcx
.mk_mach_int(v
)),
134 UintType(v
) => Ok(infcx
.tcx
.mk_mach_uint(v
)),
138 fn unify_float_variable
<'a
,'tcx
>(infcx
: &InferCtxt
<'a
,'tcx
>,
139 vid_is_expected
: bool
,
142 -> RelateResult
<'tcx
, Ty
<'tcx
>>
144 infcx
.float_unification_table
146 .unify_var_value(vid
, val
)
147 .map_err(|e
| float_unification_error(vid_is_expected
, e
))?
;
148 Ok(infcx
.tcx
.mk_mach_float(val
))
151 impl<'a
, 'tcx
> CombineFields
<'a
, 'tcx
> {
152 pub fn tcx(&self) -> &'a TyCtxt
<'tcx
> {
156 pub fn switch_expected(&self) -> CombineFields
<'a
, 'tcx
> {
158 a_is_expected
: !self.a_is_expected
,
163 pub fn equate(&self) -> Equate
<'a
, 'tcx
> {
164 Equate
::new(self.clone())
167 pub fn bivariate(&self) -> Bivariate
<'a
, 'tcx
> {
168 Bivariate
::new(self.clone())
171 pub fn sub(&self) -> Sub
<'a
, 'tcx
> {
172 Sub
::new(self.clone())
175 pub fn lub(&self) -> Lub
<'a
, 'tcx
> {
176 Lub
::new(self.clone())
179 pub fn glb(&self) -> Glb
<'a
, 'tcx
> {
180 Glb
::new(self.clone())
183 pub fn instantiate(&self,
187 -> RelateResult
<'tcx
, ()>
189 let mut stack
= Vec
::new();
190 stack
.push((a_ty
, dir
, b_vid
));
192 // For each turn of the loop, we extract a tuple
194 // (a_ty, dir, b_vid)
196 // to relate. Here dir is either SubtypeOf or
197 // SupertypeOf. The idea is that we should ensure that
198 // the type `a_ty` is a subtype or supertype (respectively) of the
199 // type to which `b_vid` is bound.
201 // If `b_vid` has not yet been instantiated with a type
202 // (which is always true on the first iteration, but not
203 // necessarily true on later iterations), we will first
204 // instantiate `b_vid` with a *generalized* version of
205 // `a_ty`. Generalization introduces other inference
206 // variables wherever subtyping could occur (at time of
207 // this writing, this means replacing free regions with
208 // region variables).
209 let (a_ty
, dir
, b_vid
) = match stack
.pop() {
213 // Get the actual variable that b_vid has been inferred to
214 let (b_vid
, b_ty
) = {
215 let mut variables
= self.infcx
.type_variables
.borrow_mut();
216 let b_vid
= variables
.root_var(b_vid
);
217 (b_vid
, variables
.probe_root(b_vid
))
220 debug
!("instantiate(a_ty={:?} dir={:?} b_vid={:?})",
225 // Check whether `vid` has been instantiated yet. If not,
226 // make a generalized form of `ty` and instantiate with
228 let b_ty
= match b_ty
{
229 Some(t
) => t
, // ...already instantiated.
230 None
=> { // ...not yet instantiated:
231 // Generalize type if necessary.
232 let generalized_ty
= match dir
{
233 EqTo
=> self.generalize(a_ty
, b_vid
, false),
234 BiTo
| SupertypeOf
| SubtypeOf
=> self.generalize(a_ty
, b_vid
, true),
236 debug
!("instantiate(a_ty={:?}, dir={:?}, \
237 b_vid={:?}, generalized_ty={:?})",
240 self.infcx
.type_variables
242 .instantiate_and_push(
243 b_vid
, generalized_ty
, &mut stack
);
248 // The original triple was `(a_ty, dir, b_vid)` -- now we have
249 // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
251 // FIXME(#16847): This code is non-ideal because all these subtype
252 // relations wind up attributed to the same spans. We need
253 // to associate causes/spans with each of the relations in
254 // the stack to get this right.
256 BiTo
=> self.bivariate().relate(&a_ty
, &b_ty
),
257 EqTo
=> self.equate().relate(&a_ty
, &b_ty
),
258 SubtypeOf
=> self.sub().relate(&a_ty
, &b_ty
),
259 SupertypeOf
=> self.sub().relate_with_variance(ty
::Contravariant
, &a_ty
, &b_ty
),
266 /// Attempts to generalize `ty` for the type variable `for_vid`. This checks for cycle -- that
267 /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also
268 /// replace all regions with fresh variables. Returns `TyError` in the case of a cycle, `Ok`
273 make_region_vars
: bool
)
274 -> RelateResult
<'tcx
, Ty
<'tcx
>>
276 let mut generalize
= Generalizer
{
278 span
: self.trace
.origin
.span(),
280 make_region_vars
: make_region_vars
,
281 cycle_detected
: false
283 let u
= ty
.fold_with(&mut generalize
);
284 if generalize
.cycle_detected
{
285 Err(TypeError
::CyclicTy
)
292 struct Generalizer
<'cx
, 'tcx
:'cx
> {
293 infcx
: &'cx InferCtxt
<'cx
, 'tcx
>,
296 make_region_vars
: bool
,
297 cycle_detected
: bool
,
300 impl<'cx
, 'tcx
> ty
::fold
::TypeFolder
<'tcx
> for Generalizer
<'cx
, 'tcx
> {
301 fn tcx(&self) -> &TyCtxt
<'tcx
> {
305 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
306 // Check to see whether the type we are genealizing references
307 // `vid`. At the same time, also update any type variables to
308 // the values that they are bound to. This is needed to truly
309 // check for cycles, but also just makes things readable.
311 // (In particular, you could have something like `$0 = Box<$1>`
312 // where `$1` has already been instantiated with `Box<$0>`)
314 ty
::TyInfer(ty
::TyVar(vid
)) => {
315 let mut variables
= self.infcx
.type_variables
.borrow_mut();
316 let vid
= variables
.root_var(vid
);
317 if vid
== self.for_vid
{
318 self.cycle_detected
= true;
321 match variables
.probe_root(vid
) {
331 t
.super_fold_with(self)
336 fn fold_region(&mut self, r
: ty
::Region
) -> ty
::Region
{
338 // Never make variables for regions bound within the type itself.
339 ty
::ReLateBound(..) => { return r; }
341 // Early-bound regions should really have been substituted away before
342 // we get to this point.
343 ty
::ReEarlyBound(..) => {
346 "Encountered early bound region when generalizing: {:?}",
350 // Always make a fresh region variable for skolemized regions;
351 // the higher-ranked decision procedures rely on this.
352 ty
::ReSkolemized(..) => { }
354 // For anything else, we make a region variable, unless we
355 // are *equating*, in which case it's just wasteful.
361 if !self.make_region_vars
{
367 // FIXME: This is non-ideal because we don't give a
368 // very descriptive origin for this region variable.
369 self.infcx
.next_region_var(MiscVariable(self.span
))
373 pub trait RelateResultCompare
<'tcx
, T
> {
374 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
375 F
: FnOnce() -> TypeError
<'tcx
>;
378 impl<'tcx
, T
:Clone
+ PartialEq
> RelateResultCompare
<'tcx
, T
> for RelateResult
<'tcx
, T
> {
379 fn compare
<F
>(&self, t
: T
, f
: F
) -> RelateResult
<'tcx
, T
> where
380 F
: FnOnce() -> TypeError
<'tcx
>,
382 self.clone().and_then(|s
| {
392 fn int_unification_error
<'tcx
>(a_is_expected
: bool
, v
: (ty
::IntVarValue
, ty
::IntVarValue
))
396 TypeError
::IntMismatch(ty
::relate
::expected_found_bool(a_is_expected
, &a
, &b
))
399 fn float_unification_error
<'tcx
>(a_is_expected
: bool
,
400 v
: (ast
::FloatTy
, ast
::FloatTy
))
404 TypeError
::FloatMismatch(ty
::relate
::expected_found_bool(a_is_expected
, &a
, &b
))