1 // Copyright 2013 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
13 This file infers the variance of type and lifetime parameters. The
14 algorithm is taken from Section 4 of the paper "Taming the Wildcards:
15 Combining Definition- and Use-Site Variance" published in PLDI'11 and
16 written by Altidor et al., and hereafter referred to as The Paper.
17
18 This inference is explicitly designed *not* to consider the uses of
19 types within code. To determine the variance of type parameters
20 defined on type `X`, we only consider the definition of the type `X`
21 and the definitions of any types it references.
22
23 We only infer variance for type parameters found on *types*: structs,
24 enums, and traits. We do not infer variance for type parameters found
25 on fns or impls. This is because those things are not type definitions
26 and variance doesn't really make sense in that context.
27
28 It is worth covering what variance means in each case. For structs and
29 enums, I think it is fairly straightforward. The variance of the type
30 or lifetime parameters defines whether `T<A>` is a subtype of `T<B>`
31 (resp. `T<'a>` and `T<'b>`) based on the relationship of `A` and `B`
32 (resp. `'a` and `'b`). (FIXME #3598 -- we do not currently make use of
33 the variances we compute for type parameters.)
34
35 ### Variance on traits
36
37 The meaning of variance for trait parameters is more subtle and worth
38 expanding upon. There are in fact two uses of the variance values we
39 compute.
40
41 #### Trait variance and object types
42
43 The first is for object types. Just as with structs and enums, we can
44 decide the subtyping relationship between two object types `&Trait<A>`
45 and `&Trait<B>` based on the relationship of `A` and `B`. Note that
46 for object types we ignore the `Self` type parameter -- it is unknown,
47 and the nature of dynamic dispatch ensures that we will always call a
48 function that is expected the appropriate `Self` type. However, we
49 must be careful with the other type parameters, or else we could end
50 up calling a function that is expecting one type but provided another.
51
52 To see what I mean, consider a trait like so:
53
54 trait ConvertTo<A> {
55 fn convertTo(&self) -> A;
56 }
57
58 Intuitively, If we had one object `O=&ConvertTo<Object>` and another
59 `S=&ConvertTo<String>`, then `S <: O` because `String <: Object`
60 (presuming Java-like "string" and "object" types, my go to examples
61 for subtyping). The actual algorithm would be to compare the
62 (explicit) type parameters pairwise respecting their variance: here,
63 the type parameter A is covariant (it appears only in a return
64 position), and hence we require that `String <: Object`.
65
66 You'll note though that we did not consider the binding for the
67 (implicit) `Self` type parameter: in fact, it is unknown, so that's
68 good. The reason we can ignore that parameter is precisely because we
69 don't need to know its value until a call occurs, and at that time (as
70 you said) the dynamic nature of virtual dispatch means the code we run
71 will be correct for whatever value `Self` happens to be bound to for
72 the particular object whose method we called. `Self` is thus different
73 from `A`, because the caller requires that `A` be known in order to
74 know the return type of the method `convertTo()`. (As an aside, we
75 have rules preventing methods where `Self` appears outside of the
76 receiver position from being called via an object.)
77
78 #### Trait variance and vtable resolution
79
80 But traits aren't only used with objects. They're also used when
81 deciding whether a given impl satisfies a given trait bound (or should
82 be -- FIXME #5781). To set the scene here, imagine I had a function:
83
84 fn convertAll<A,T:ConvertTo<A>>(v: &[T]) {
85 ...
86 }
87
88 Now imagine that I have an implementation of `ConvertTo` for `Object`:
89
90 impl ConvertTo<int> for Object { ... }
91
92 And I want to call `convertAll` on an array of strings. Suppose
93 further that for whatever reason I specifically supply the value of
94 `String` for the type parameter `T`:
95
96 let mut vector = ~["string", ...];
97 convertAll::<int, String>(v);
98
99 Is this legal? To put another way, can we apply the `impl` for
100 `Object` to the type `String`? The answer is yes, but to see why
101 we have to expand out what will happen:
102
103 - `convertAll` will create a pointer to one of the entries in the
104 vector, which will have type `&String`
105 - It will then call the impl of `convertTo()` that is intended
106 for use with objects. This has the type:
107
108 fn(self: &Object) -> int
109
110 It is ok to provide a value for `self` of type `&String` because
111 `&String <: &Object`.
112
113 OK, so intuitively we want this to be legal, so let's bring this back
114 to variance and see whether we are computing the correct result. We
115 must first figure out how to phrase the question "is an impl for
116 `Object,int` usable where an impl for `String,int` is expected?"
117
118 Maybe it's helpful to think of a dictionary-passing implementation of
119 type classes. In that case, `convertAll()` takes an implicit parameter
120 representing the impl. In short, we *have* an impl of type:
121
122 V_O = ConvertTo<int> for Object
123
124 and the function prototype expects an impl of type:
125
126 V_S = ConvertTo<int> for String
127
128 As with any argument, this is legal if the type of the value given
129 (`V_O`) is a subtype of the type expected (`V_S`). So is `V_O <: V_S`?
130 The answer will depend on the variance of the various parameters. In
131 this case, because the `Self` parameter is contravariant and `A` is
132 covariant, it means that:
133
134 V_O <: V_S iff
135 int <: int
136 String <: Object
137
138 These conditions are satisfied and so we are happy.
139
140 ### The algorithm
141
142 The basic idea is quite straightforward. We iterate over the types
143 defined and, for each use of a type parameter X, accumulate a
144 constraint indicating that the variance of X must be valid for the
145 variance of that use site. We then iteratively refine the variance of
146 X until all constraints are met. There is *always* a sol'n, because at
147 the limit we can declare all type parameters to be invariant and all
148 constraints will be satisfied.
149
150 As a simple example, consider:
151
152 enum Option<A> { Some(A), None }
153 enum OptionalFn<B> { Some(|B|), None }
154 enum OptionalMap<C> { Some(|C| -> C), None }
155
156 Here, we will generate the constraints:
157
158 1. V(A) <= +
159 2. V(B) <= -
160 3. V(C) <= +
161 4. V(C) <= -
162
163 These indicate that (1) the variance of A must be at most covariant;
164 (2) the variance of B must be at most contravariant; and (3, 4) the
165 variance of C must be at most covariant *and* contravariant. All of these
166 results are based on a variance lattice defined as follows:
167
168 * Top (bivariant)
169 - +
170 o Bottom (invariant)
171
172 Based on this lattice, the solution V(A)=+, V(B)=-, V(C)=o is the
173 optimal solution. Note that there is always a naive solution which
174 just declares all variables to be invariant.
175
176 You may be wondering why fixed-point iteration is required. The reason
177 is that the variance of a use site may itself be a function of the
178 variance of other type parameters. In full generality, our constraints
179 take the form:
180
181 V(X) <= Term
182 Term := + | - | * | o | V(X) | Term x Term
183
184 Here the notation V(X) indicates the variance of a type/region
185 parameter `X` with respect to its defining class. `Term x Term`
186 represents the "variance transform" as defined in the paper:
187
188 If the variance of a type variable `X` in type expression `E` is `V2`
189 and the definition-site variance of the [corresponding] type parameter
190 of a class `C` is `V1`, then the variance of `X` in the type expression
191 `C<E>` is `V3 = V1.xform(V2)`.
192
193 */
194
195 use collections::HashMap;
196 use arena;
197 use arena::Arena;
198 use middle::ty;
199 use std::fmt;
200 use std::rc::Rc;
201 use syntax::ast;
202 use syntax::ast_map;
203 use syntax::ast_util;
204 use syntax::owned_slice::OwnedSlice;
205 use syntax::visit;
206 use syntax::visit::Visitor;
207 use util::ppaux::Repr;
208
209 pub fn infer_variance(tcx: &ty::ctxt,
210 krate: &ast::Crate) {
211 let mut arena = arena::Arena::new();
212 let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
213 let constraints_cx = add_constraints_from_crate(terms_cx, krate);
214 solve_constraints(constraints_cx);
215 }
216
217 /**************************************************************************
218 * Representing terms
219 *
220 * Terms are structured as a straightforward tree. Rather than rely on
221 * GC, we allocate terms out of a bounded arena (the lifetime of this
222 * arena is the lifetime 'a that is threaded around).
223 *
224 * We assign a unique index to each type/region parameter whose variance
225 * is to be inferred. We refer to such variables as "inferreds". An
226 * `InferredIndex` is a newtype'd int representing the index of such
227 * a variable.
228 */
229
230 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
231
232 struct InferredIndex(uint);
233
234 enum VarianceTerm<'a> {
235 ConstantTerm(ty::Variance),
236 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
237 InferredTerm(InferredIndex),
238 }
239
240 impl<'a> fmt::Show for VarianceTerm<'a> {
241 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
242 match *self {
243 ConstantTerm(c1) => write!(f.buf, "{}", c1),
244 TransformTerm(v1, v2) => write!(f.buf, "({} \u00D7 {})", v1, v2),
245 InferredTerm(id) => write!(f.buf, "[{}]", { let InferredIndex(i) = id; i })
246 }
247 }
248 }
249
250 /**************************************************************************
251 * The first pass over the crate simply builds up the set of inferreds.
252 */
253
254 struct TermsContext<'a> {
255 tcx: &'a ty::ctxt,
256 arena: &'a Arena,
257
258 empty_variances: Rc<ty::ItemVariances>,
259
260 // Maps from the node id of a type/generic parameter to the
261 // corresponding inferred index.
262 inferred_map: HashMap<ast::NodeId, InferredIndex>,
263
264 // Maps from an InferredIndex to the info for that variable.
265 inferred_infos: Vec<InferredInfo<'a>> ,
266 }
267
268 enum ParamKind { TypeParam, RegionParam, SelfParam }
269
270 struct InferredInfo<'a> {
271 item_id: ast::NodeId,
272 kind: ParamKind,
273 index: uint,
274 param_id: ast::NodeId,
275 term: VarianceTermPtr<'a>,
276 }
277
278 fn determine_parameters_to_be_inferred<'a>(tcx: &'a ty::ctxt,
279 arena: &'a mut Arena,
280 krate: &ast::Crate)
281 -> TermsContext<'a> {
282 let mut terms_cx = TermsContext {
283 tcx: tcx,
284 arena: arena,
285 inferred_map: HashMap::new(),
286 inferred_infos: Vec::new(),
287
288 // cache and share the variance struct used for items with
289 // no type/region parameters
290 empty_variances: Rc::new(ty::ItemVariances {
291 self_param: None,
292 type_params: OwnedSlice::empty(),
293 region_params: OwnedSlice::empty()
294 })
295 };
296
297 visit::walk_crate(&mut terms_cx, krate, ());
298
299 terms_cx
300 }
301
302 impl<'a> TermsContext<'a> {
303 fn add_inferred(&mut self,
304 item_id: ast::NodeId,
305 kind: ParamKind,
306 index: uint,
307 param_id: ast::NodeId) {
308 let inf_index = InferredIndex(self.inferred_infos.len());
309 let term = self.arena.alloc(|| InferredTerm(inf_index));
310 self.inferred_infos.push(InferredInfo { item_id: item_id,
311 kind: kind,
312 index: index,
313 param_id: param_id,
314 term: term });
315 let newly_added = self.inferred_map.insert(param_id, inf_index);
316 assert!(newly_added);
317
318 debug!("add_inferred(item_id={}, \
319 kind={:?}, \
320 index={}, \
321 param_id={},
322 inf_index={:?})",
323 item_id, kind, index, param_id, inf_index);
324 }
325
326 fn num_inferred(&self) -> uint {
327 self.inferred_infos.len()
328 }
329 }
330
331 impl<'a> Visitor<()> for TermsContext<'a> {
332 fn visit_item(&mut self, item: &ast::Item, _: ()) {
333 debug!("add_inferreds for item {}", item.repr(self.tcx));
334
335 let inferreds_on_entry = self.num_inferred();
336
337 // NB: In the code below for writing the results back into the
338 // tcx, we rely on the fact that all inferreds for a particular
339 // item are assigned continuous indices.
340 match item.node {
341 ast::ItemTrait(..) => {
342 self.add_inferred(item.id, SelfParam, 0, item.id);
343 }
344 _ => { }
345 }
346
347 match item.node {
348 ast::ItemEnum(_, ref generics) |
349 ast::ItemStruct(_, ref generics) |
350 ast::ItemTrait(ref generics, _, _, _) => {
351 for (i, p) in generics.lifetimes.iter().enumerate() {
352 self.add_inferred(item.id, RegionParam, i, p.id);
353 }
354 for (i, p) in generics.ty_params.iter().enumerate() {
355 self.add_inferred(item.id, TypeParam, i, p.id);
356 }
357
358 // If this item has no type or lifetime parameters,
359 // then there are no variances to infer, so just
360 // insert an empty entry into the variance map.
361 // Arguably we could just leave the map empty in this
362 // case but it seems cleaner to be able to distinguish
363 // "invalid item id" from "item id with no
364 // parameters".
365 if self.num_inferred() == inferreds_on_entry {
366 let newly_added = self.tcx.item_variance_map.borrow_mut().insert(
367 ast_util::local_def(item.id),
368 self.empty_variances.clone());
369 assert!(newly_added);
370 }
371
372 visit::walk_item(self, item, ());
373 }
374
375 ast::ItemImpl(..) |
376 ast::ItemStatic(..) |
377 ast::ItemFn(..) |
378 ast::ItemMod(..) |
379 ast::ItemForeignMod(..) |
380 ast::ItemTy(..) |
381 ast::ItemMac(..) => {
382 visit::walk_item(self, item, ());
383 }
384 }
385 }
386 }
387
388 /**************************************************************************
389 * Constraint construction and representation
390 *
391 * The second pass over the AST determines the set of constraints.
392 * We walk the set of items and, for each member, generate new constraints.
393 */
394
395 struct ConstraintContext<'a> {
396 terms_cx: TermsContext<'a>,
397
398 // These are the def-id of the std::kinds::marker::InvariantType,
399 // std::kinds::marker::InvariantLifetime, and so on. The arrays
400 // are indexed by the `ParamKind` (type, lifetime, self). Note
401 // that there are no marker types for self, so the entries for
402 // self are always None.
403 invariant_lang_items: [Option<ast::DefId>, ..3],
404 covariant_lang_items: [Option<ast::DefId>, ..3],
405 contravariant_lang_items: [Option<ast::DefId>, ..3],
406
407 // These are pointers to common `ConstantTerm` instances
408 covariant: VarianceTermPtr<'a>,
409 contravariant: VarianceTermPtr<'a>,
410 invariant: VarianceTermPtr<'a>,
411 bivariant: VarianceTermPtr<'a>,
412
413 constraints: Vec<Constraint<'a>> ,
414 }
415
416 /// Declares that the variable `decl_id` appears in a location with
417 /// variance `variance`.
418 struct Constraint<'a> {
419 inferred: InferredIndex,
420 variance: &'a VarianceTerm<'a>,
421 }
422
423 fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
424 krate: &ast::Crate)
425 -> ConstraintContext<'a> {
426 let mut invariant_lang_items = [None, ..3];
427 let mut covariant_lang_items = [None, ..3];
428 let mut contravariant_lang_items = [None, ..3];
429
430 covariant_lang_items[TypeParam as uint] =
431 terms_cx.tcx.lang_items.covariant_type();
432 covariant_lang_items[RegionParam as uint] =
433 terms_cx.tcx.lang_items.covariant_lifetime();
434
435 contravariant_lang_items[TypeParam as uint] =
436 terms_cx.tcx.lang_items.contravariant_type();
437 contravariant_lang_items[RegionParam as uint] =
438 terms_cx.tcx.lang_items.contravariant_lifetime();
439
440 invariant_lang_items[TypeParam as uint] =
441 terms_cx.tcx.lang_items.invariant_type();
442 invariant_lang_items[RegionParam as uint] =
443 terms_cx.tcx.lang_items.invariant_lifetime();
444
445 let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
446 let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
447 let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
448 let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
449 let mut constraint_cx = ConstraintContext {
450 terms_cx: terms_cx,
451
452 invariant_lang_items: invariant_lang_items,
453 covariant_lang_items: covariant_lang_items,
454 contravariant_lang_items: contravariant_lang_items,
455
456 covariant: covariant,
457 contravariant: contravariant,
458 invariant: invariant,
459 bivariant: bivariant,
460 constraints: Vec::new(),
461 };
462 visit::walk_crate(&mut constraint_cx, krate, ());
463 constraint_cx
464 }
465
466 impl<'a> Visitor<()> for ConstraintContext<'a> {
467 fn visit_item(&mut self, item: &ast::Item, _: ()) {
468 let did = ast_util::local_def(item.id);
469 let tcx = self.terms_cx.tcx;
470
471 match item.node {
472 ast::ItemEnum(ref enum_definition, _) => {
473 // Hack: If we directly call `ty::enum_variants`, it
474 // annoyingly takes it upon itself to run off and
475 // evaluate the discriminants eagerly (*grumpy* that's
476 // not the typical pattern). This results in double
477 // error messages because typeck goes off and does
478 // this at a later time. All we really care about is
479 // the types of the variant arguments, so we just call
480 // `ty::VariantInfo::from_ast_variant()` ourselves
481 // here, mainly so as to mask the differences between
482 // struct-like enums and so forth.
483 for &ast_variant in enum_definition.variants.iter() {
484 let variant =
485 ty::VariantInfo::from_ast_variant(tcx,
486 ast_variant,
487 /*discrimant*/ 0);
488 for &arg_ty in variant.args.iter() {
489 self.add_constraints_from_ty(arg_ty, self.covariant);
490 }
491 }
492 }
493
494 ast::ItemStruct(..) => {
495 let struct_fields = ty::lookup_struct_fields(tcx, did);
496 for field_info in struct_fields.iter() {
497 assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
498 let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
499 self.add_constraints_from_ty(field_ty, self.covariant);
500 }
501 }
502
503 ast::ItemTrait(..) => {
504 let methods = ty::trait_methods(tcx, did);
505 for method in methods.iter() {
506 self.add_constraints_from_sig(
507 &method.fty.sig, self.covariant);
508 }
509 }
510
511 ast::ItemStatic(..) |
512 ast::ItemFn(..) |
513 ast::ItemMod(..) |
514 ast::ItemForeignMod(..) |
515 ast::ItemTy(..) |
516 ast::ItemImpl(..) |
517 ast::ItemMac(..) => {
518 visit::walk_item(self, item, ());
519 }
520 }
521 }
522 }
523
524 /// Is `param_id` a lifetime according to `map`?
525 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
526 match map.find(param_id) {
527 Some(ast_map::NodeLifetime(..)) => true, _ => false
528 }
529 }
530
531 impl<'a> ConstraintContext<'a> {
532 fn tcx(&self) -> &'a ty::ctxt {
533 self.terms_cx.tcx
534 }
535
536 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
537 match self.terms_cx.inferred_map.find(¶m_id) {
538 Some(&index) => index,
539 None => {
540 self.tcx().sess.bug(format!(
541 "No inferred index entry for {}",
542 self.tcx().map.node_to_str(param_id)));
543 }
544 }
545 }
546
547 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
548 let tcx = self.terms_cx.tcx;
549 assert!(is_lifetime(&tcx.map, param_id));
550 match tcx.named_region_map.find(¶m_id) {
551 Some(&ast::DefEarlyBoundRegion(_, lifetime_decl_id))
552 => lifetime_decl_id,
553 Some(_) => fail!("should not encounter non early-bound cases"),
554
555 // The lookup should only fail when `param_id` is
556 // itself a lifetime binding: use it as the decl_id.
557 None => param_id,
558 }
559
560 }
561
562 /// Is `param_id` a type parameter for which we infer variance?
563 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
564 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
565
566 // To safe-guard against invalid inferred_map constructions,
567 // double-check if variance is inferred at some use of a type
568 // parameter (by inspecting parent of its binding declaration
569 // to see if it is introduced by a type or by a fn/impl).
570
571 let check_result = |this:&ConstraintContext| -> bool {
572 let tcx = this.terms_cx.tcx;
573 let decl_id = this.find_binding_for_lifetime(param_id);
574 // Currently only called on lifetimes; double-checking that.
575 assert!(is_lifetime(&tcx.map, param_id));
576 let parent_id = tcx.map.get_parent(decl_id);
577 let parent = tcx.map.find(parent_id).unwrap_or_else(
578 || fail!("tcx.map missing entry for id: {}", parent_id));
579
580 let is_inferred;
581 macro_rules! cannot_happen { () => { {
582 fail!("invalid parent: {:s} for {:s}",
583 tcx.map.node_to_str(parent_id),
584 tcx.map.node_to_str(param_id));
585 } } }
586
587 match parent {
588 ast_map::NodeItem(p) => {
589 match p.node {
590 ast::ItemTy(..) |
591 ast::ItemEnum(..) |
592 ast::ItemStruct(..) |
593 ast::ItemTrait(..) => is_inferred = true,
594 ast::ItemFn(..) => is_inferred = false,
595 _ => cannot_happen!(),
596 }
597 }
598 ast_map::NodeTraitMethod(..) => is_inferred = false,
599 ast_map::NodeMethod(_) => is_inferred = false,
600 _ => cannot_happen!(),
601 }
602
603 return is_inferred;
604 };
605
606 assert_eq!(result, check_result(self));
607
608 return result;
609 }
610
611 fn declared_variance(&self,
612 param_def_id: ast::DefId,
613 item_def_id: ast::DefId,
614 kind: ParamKind,
615 index: uint)
616 -> VarianceTermPtr<'a> {
617 /*!
618 * Returns a variance term representing the declared variance of
619 * the type/region parameter with the given id.
620 */
621
622 assert_eq!(param_def_id.krate, item_def_id.krate);
623
624 if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
625 self.invariant
626 } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
627 self.covariant
628 } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
629 self.contravariant
630 } else if param_def_id.krate == ast::LOCAL_CRATE {
631 // Parameter on an item defined within current crate:
632 // variance not yet inferred, so return a symbolic
633 // variance.
634 let InferredIndex(index) = self.inferred_index(param_def_id.node);
635 self.terms_cx.inferred_infos.get(index).term
636 } else {
637 // Parameter on an item defined within another crate:
638 // variance already inferred, just look it up.
639 let variances = ty::item_variances(self.tcx(), item_def_id);
640 let variance = match kind {
641 SelfParam => variances.self_param.unwrap(),
642 TypeParam => *variances.type_params.get(index),
643 RegionParam => *variances.region_params.get(index),
644 };
645 self.constant_term(variance)
646 }
647 }
648
649 fn add_constraint(&mut self,
650 InferredIndex(index): InferredIndex,
651 variance: VarianceTermPtr<'a>) {
652 debug!("add_constraint(index={}, variance={})",
653 index, variance.to_str());
654 self.constraints.push(Constraint { inferred: InferredIndex(index),
655 variance: variance });
656 }
657
658 fn contravariant(&mut self,
659 variance: VarianceTermPtr<'a>)
660 -> VarianceTermPtr<'a> {
661 self.xform(variance, self.contravariant)
662 }
663
664 fn invariant(&mut self,
665 variance: VarianceTermPtr<'a>)
666 -> VarianceTermPtr<'a> {
667 self.xform(variance, self.invariant)
668 }
669
670 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
671 match v {
672 ty::Covariant => self.covariant,
673 ty::Invariant => self.invariant,
674 ty::Contravariant => self.contravariant,
675 ty::Bivariant => self.bivariant,
676 }
677 }
678
679 fn xform(&mut self,
680 v1: VarianceTermPtr<'a>,
681 v2: VarianceTermPtr<'a>)
682 -> VarianceTermPtr<'a> {
683 match (*v1, *v2) {
684 (_, ConstantTerm(ty::Covariant)) => {
685 // Applying a "covariant" transform is always a no-op
686 v1
687 }
688
689 (ConstantTerm(c1), ConstantTerm(c2)) => {
690 self.constant_term(c1.xform(c2))
691 }
692
693 _ => {
694 self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
695 }
696 }
697 }
698
699 /// Adds constraints appropriate for an instance of `ty` appearing
700 /// in a context with ambient variance `variance`
701 fn add_constraints_from_ty(&mut self,
702 ty: ty::t,
703 variance: VarianceTermPtr<'a>) {
704 debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
705
706 match ty::get(ty).sty {
707 ty::ty_nil | ty::ty_bot | ty::ty_bool |
708 ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
709 ty::ty_float(_) | ty::ty_str => {
710 /* leaf type -- noop */
711 }
712
713 ty::ty_rptr(region, ref mt) => {
714 let contra = self.contravariant(variance);
715 self.add_constraints_from_region(region, contra);
716 self.add_constraints_from_mt(mt, variance);
717 }
718
719 ty::ty_vec(ref mt, _) => {
720 self.add_constraints_from_mt(mt, variance);
721 }
722
723 ty::ty_uniq(typ) | ty::ty_box(typ) => {
724 self.add_constraints_from_ty(typ, variance);
725 }
726
727 ty::ty_ptr(ref mt) => {
728 self.add_constraints_from_mt(mt, variance);
729 }
730
731 ty::ty_tup(ref subtys) => {
732 for &subty in subtys.iter() {
733 self.add_constraints_from_ty(subty, variance);
734 }
735 }
736
737 ty::ty_enum(def_id, ref substs) |
738 ty::ty_struct(def_id, ref substs) => {
739 let item_type = ty::lookup_item_type(self.tcx(), def_id);
740 self.add_constraints_from_substs(def_id, &item_type.generics,
741 substs, variance);
742 }
743
744 ty::ty_trait(box ty::TyTrait { def_id, ref substs, .. }) => {
745 let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
746 self.add_constraints_from_substs(def_id, &trait_def.generics,
747 substs, variance);
748 }
749
750 ty::ty_param(ty::param_ty { def_id: ref def_id, .. }) => {
751 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
752 match self.terms_cx.inferred_map.find(&def_id.node) {
753 Some(&index) => {
754 self.add_constraint(index, variance);
755 }
756 None => {
757 // We do not infer variance for type parameters
758 // declared on methods. They will not be present
759 // in the inferred_map.
760 }
761 }
762 }
763
764 ty::ty_self(ref def_id) => {
765 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
766 let index = self.inferred_index(def_id.node);
767 self.add_constraint(index, variance);
768 }
769
770 ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
771 ty::ty_closure(box ty::ClosureTy {
772 ref sig,
773 store: ty::UniqTraitStore,
774 ..
775 }) => {
776 self.add_constraints_from_sig(sig, variance);
777 }
778
779 ty::ty_closure(box ty::ClosureTy { ref sig,
780 store: ty::RegionTraitStore(region, _), .. }) => {
781 let contra = self.contravariant(variance);
782 self.add_constraints_from_region(region, contra);
783 self.add_constraints_from_sig(sig, variance);
784 }
785
786 ty::ty_infer(..) | ty::ty_err => {
787 self.tcx().sess.bug(
788 format!("unexpected type encountered in \
789 variance inference: {}",
790 ty.repr(self.tcx())));
791 }
792 }
793 }
794
795
796 /// Adds constraints appropriate for a nominal type (enum, struct,
797 /// object, etc) appearing in a context with ambient variance `variance`
798 fn add_constraints_from_substs(&mut self,
799 def_id: ast::DefId,
800 generics: &ty::Generics,
801 substs: &ty::substs,
802 variance: VarianceTermPtr<'a>) {
803 debug!("add_constraints_from_substs(def_id={:?})", def_id);
804
805 for (i, p) in generics.type_param_defs().iter().enumerate() {
806 let variance_decl =
807 self.declared_variance(p.def_id, def_id, TypeParam, i);
808 let variance_i = self.xform(variance, variance_decl);
809 self.add_constraints_from_ty(*substs.tps.get(i), variance_i);
810 }
811
812 match substs.regions {
813 ty::ErasedRegions => {}
814 ty::NonerasedRegions(ref rps) => {
815 for (i, p) in generics.region_param_defs().iter().enumerate() {
816 let variance_decl =
817 self.declared_variance(p.def_id, def_id, RegionParam, i);
818 let variance_i = self.xform(variance, variance_decl);
819 self.add_constraints_from_region(*rps.get(i), variance_i);
820 }
821 }
822 }
823 }
824
825 /// Adds constraints appropriate for a function with signature
826 /// `sig` appearing in a context with ambient variance `variance`
827 fn add_constraints_from_sig(&mut self,
828 sig: &ty::FnSig,
829 variance: VarianceTermPtr<'a>) {
830 let contra = self.contravariant(variance);
831 for &input in sig.inputs.iter() {
832 self.add_constraints_from_ty(input, contra);
833 }
834 self.add_constraints_from_ty(sig.output, variance);
835 }
836
837 /// Adds constraints appropriate for a region appearing in a
838 /// context with ambient variance `variance`
839 fn add_constraints_from_region(&mut self,
840 region: ty::Region,
841 variance: VarianceTermPtr<'a>) {
842 match region {
843 ty::ReEarlyBound(param_id, _, _) => {
844 if self.is_to_be_inferred(param_id) {
845 let index = self.inferred_index(param_id);
846 self.add_constraint(index, variance);
847 }
848 }
849
850 ty::ReStatic => { }
851
852 ty::ReLateBound(..) => {
853 // We do not infer variance for region parameters on
854 // methods or in fn types.
855 }
856
857 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
858 ty::ReEmpty => {
859 // We don't expect to see anything but 'static or bound
860 // regions when visiting member types or method types.
861 self.tcx().sess.bug(format!("unexpected region encountered in \
862 variance inference: {}",
863 region.repr(self.tcx())));
864 }
865 }
866 }
867
868 /// Adds constraints appropriate for a mutability-type pair
869 /// appearing in a context with ambient variance `variance`
870 fn add_constraints_from_mt(&mut self,
871 mt: &ty::mt,
872 variance: VarianceTermPtr<'a>) {
873 match mt.mutbl {
874 ast::MutMutable => {
875 let invar = self.invariant(variance);
876 self.add_constraints_from_ty(mt.ty, invar);
877 }
878
879 ast::MutImmutable => {
880 self.add_constraints_from_ty(mt.ty, variance);
881 }
882 }
883 }
884 }
885
886 /**************************************************************************
887 * Constraint solving
888 *
889 * The final phase iterates over the constraints, refining the variance
890 * for each inferred until a fixed point is reached. This will be the
891 * optimal solution to the constraints. The final variance for each
892 * inferred is then written into the `variance_map` in the tcx.
893 */
894
895 struct SolveContext<'a> {
896 terms_cx: TermsContext<'a>,
897 constraints: Vec<Constraint<'a>> ,
898
899 // Maps from an InferredIndex to the inferred value for that variable.
900 solutions: Vec<ty::Variance> }
901
902 fn solve_constraints(constraints_cx: ConstraintContext) {
903 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
904 let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
905 let mut solutions_cx = SolveContext {
906 terms_cx: terms_cx,
907 constraints: constraints,
908 solutions: solutions
909 };
910 solutions_cx.solve();
911 solutions_cx.write();
912 }
913
914 impl<'a> SolveContext<'a> {
915 fn solve(&mut self) {
916 // Propagate constraints until a fixed point is reached. Note
917 // that the maximum number of iterations is 2C where C is the
918 // number of constraints (each variable can change values at most
919 // twice). Since number of constraints is linear in size of the
920 // input, so is the inference process.
921 let mut changed = true;
922 while changed {
923 changed = false;
924
925 for constraint in self.constraints.iter() {
926 let Constraint { inferred, variance: term } = *constraint;
927 let InferredIndex(inferred) = inferred;
928 let variance = self.evaluate(term);
929 let old_value = *self.solutions.get(inferred);
930 let new_value = glb(variance, old_value);
931 if old_value != new_value {
932 debug!("Updating inferred {} (node {}) \
933 from {:?} to {:?} due to {}",
934 inferred,
935 self.terms_cx
936 .inferred_infos
937 .get(inferred)
938 .param_id,
939 old_value,
940 new_value,
941 term.to_str());
942
943 *self.solutions.get_mut(inferred) = new_value;
944 changed = true;
945 }
946 }
947 }
948 }
949
950 fn write(&self) {
951 // Collect all the variances for a particular item and stick
952 // them into the variance map. We rely on the fact that we
953 // generate all the inferreds for a particular item
954 // consecutively (that is, we collect solutions for an item
955 // until we see a new item id, and we assume (1) the solutions
956 // are in the same order as the type parameters were declared
957 // and (2) all solutions or a given item appear before a new
958 // item id).
959
960 let tcx = self.terms_cx.tcx;
961 let solutions = &self.solutions;
962 let inferred_infos = &self.terms_cx.inferred_infos;
963 let mut index = 0;
964 let num_inferred = self.terms_cx.num_inferred();
965 while index < num_inferred {
966 let item_id = inferred_infos.get(index).item_id;
967 let mut self_param = None;
968 let mut type_params = vec!();
969 let mut region_params = vec!();
970
971 while index < num_inferred &&
972 inferred_infos.get(index).item_id == item_id {
973 let info = inferred_infos.get(index);
974 match info.kind {
975 SelfParam => {
976 assert!(self_param.is_none());
977 self_param = Some(*solutions.get(index));
978 }
979 TypeParam => {
980 type_params.push(*solutions.get(index));
981 }
982 RegionParam => {
983 region_params.push(*solutions.get(index));
984 }
985 }
986 index += 1;
987 }
988
989 let item_variances = ty::ItemVariances {
990 self_param: self_param,
991 type_params: OwnedSlice::from_vec(type_params),
992 region_params: OwnedSlice::from_vec(region_params)
993 };
994 debug!("item_id={} item_variances={}",
995 item_id,
996 item_variances.repr(tcx));
997
998 let item_def_id = ast_util::local_def(item_id);
999
1000 // For unit testing: check for a special "rustc_variance"
1001 // attribute and report an error with various results if found.
1002 if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1003 let found = item_variances.repr(tcx);
1004 tcx.sess.span_err(tcx.map.span(item_id), found);
1005 }
1006
1007 let newly_added = tcx.item_variance_map.borrow_mut()
1008 .insert(item_def_id, Rc::new(item_variances));
1009 assert!(newly_added);
1010 }
1011 }
1012
1013 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1014 match *term {
1015 ConstantTerm(v) => {
1016 v
1017 }
1018
1019 TransformTerm(t1, t2) => {
1020 let v1 = self.evaluate(t1);
1021 let v2 = self.evaluate(t2);
1022 v1.xform(v2)
1023 }
1024
1025 InferredTerm(InferredIndex(index)) => {
1026 *self.solutions.get(index)
1027 }
1028 }
1029 }
1030 }
1031
1032 /**************************************************************************
1033 * Miscellany transformations on variance
1034 */
1035
1036 trait Xform {
1037 fn xform(self, v: Self) -> Self;
1038 }
1039
1040 impl Xform for ty::Variance {
1041 fn xform(self, v: ty::Variance) -> ty::Variance {
1042 // "Variance transformation", Figure 1 of The Paper
1043 match (self, v) {
1044 // Figure 1, column 1.
1045 (ty::Covariant, ty::Covariant) => ty::Covariant,
1046 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1047 (ty::Covariant, ty::Invariant) => ty::Invariant,
1048 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1049
1050 // Figure 1, column 2.
1051 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1052 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1053 (ty::Contravariant, ty::Invariant) => ty::Invariant,
1054 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1055
1056 // Figure 1, column 3.
1057 (ty::Invariant, _) => ty::Invariant,
1058
1059 // Figure 1, column 4.
1060 (ty::Bivariant, _) => ty::Bivariant,
1061 }
1062 }
1063 }
1064
1065 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1066 // Greatest lower bound of the variance lattice as
1067 // defined in The Paper:
1068 //
1069 // *
1070 // - +
1071 // o
1072 match (v1, v2) {
1073 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1074
1075 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1076 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1077
1078 (ty::Covariant, ty::Covariant) => ty::Covariant,
1079
1080 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1081
1082 (x, ty::Bivariant) | (ty::Bivariant, x) => x,
1083 }
1084 }
librustc/middle/typeck/variance.rs:233:1-233:1 -enum- definition:
enum VarianceTerm<'a> {
ConstantTerm(ty::Variance),
TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
references:- 3240: impl<'a> fmt::Show for VarianceTerm<'a> {
241: fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
--
419: inferred: InferredIndex,
420: variance: &'a VarianceTerm<'a>,
421: }
librustc/middle/typeck/variance.rs:1035:1-1035:1 -trait- definition:
trait Xform {
fn xform(self, v: Self) -> Self;
}
references:- 31040: impl Xform for ty::Variance {
1041: fn xform(self, v: ty::Variance) -> ty::Variance {
librustc/middle/typeck/variance.rs:894:1-894:1 -struct- definition:
struct SolveContext<'a> {
terms_cx: TermsContext<'a>,
constraints: Vec<Constraint<'a>> ,
references:- 2914: impl<'a> SolveContext<'a> {
915: fn solve(&mut self) {
librustc/middle/typeck/variance.rs:267:1-267:1 -enum- definition:
enum ParamKind { TypeParam, RegionParam, SelfParam }
struct InferredInfo<'a> {
item_id: ast::NodeId,
references:- 3613: item_def_id: ast::DefId,
614: kind: ParamKind,
615: index: uint)
librustc/middle/typeck/variance.rs:229:1-229:1 -NK_AS_STR_TODO- definition:
type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
struct InferredIndex(uint);
enum VarianceTerm<'a> {
references:- 23828: sig: &ty::FnSig,
829: variance: VarianceTermPtr<'a>) {
830: let contra = self.contravariant(variance);
--
840: region: ty::Region,
841: variance: VarianceTermPtr<'a>) {
842: match region {
--
1013: fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1014: match *term {
librustc/middle/typeck/variance.rs:269:1-269:1 -struct- definition:
struct InferredInfo<'a> {
item_id: ast::NodeId,
kind: ParamKind,
references:- 2309: let term = self.arena.alloc(|| InferredTerm(inf_index));
310: self.inferred_infos.push(InferredInfo { item_id: item_id,
311: kind: kind,
librustc/middle/typeck/variance.rs:231:1-231:1 -struct- definition:
struct InferredIndex(uint);
enum VarianceTerm<'a> {
ConstantTerm(ty::Variance),
references:- 5261: // corresponding inferred index.
262: inferred_map: HashMap<ast::NodeId, InferredIndex>,
--
536: fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
537: match self.terms_cx.inferred_map.find(¶m_id) {
--
649: fn add_constraint(&mut self,
650: InferredIndex(index): InferredIndex,
651: variance: VarianceTermPtr<'a>) {
librustc/middle/typeck/variance.rs:394:1-394:1 -struct- definition:
struct ConstraintContext<'a> {
terms_cx: TermsContext<'a>,
// These are the def-id of the std::kinds::marker::InvariantType,
references:- 7448: let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
449: let mut constraint_cx = ConstraintContext {
450: terms_cx: terms_cx,
--
466: impl<'a> Visitor<()> for ConstraintContext<'a> {
467: fn visit_item(&mut self, item: &ast::Item, _: ()) {
--
902: fn solve_constraints(constraints_cx: ConstraintContext) {
903: let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
904: let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
librustc/middle/typeck/variance.rs:253:1-253:1 -struct- definition:
struct TermsContext<'a> {
tcx: &'a ty::ctxt,
arena: &'a Arena,
references:- 7281: -> TermsContext<'a> {
282: let mut terms_cx = TermsContext {
283: tcx: tcx,
--
302: impl<'a> TermsContext<'a> {
303: fn add_inferred(&mut self,
--
895: struct SolveContext<'a> {
896: terms_cx: TermsContext<'a>,
897: constraints: Vec<Constraint<'a>> ,
librustc/middle/typeck/variance.rs:524:49-524:49 -fn- definition:
/// Is `param_id` a lifetime according to `map`?
fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
match map.find(param_id) {
references:- 2574: // Currently only called on lifetimes; double-checking that.
575: assert!(is_lifetime(&tcx.map, param_id));
576: let parent_id = tcx.map.get_parent(decl_id);
librustc/middle/typeck/variance.rs:417:25-417:25 -struct- definition:
/// variance `variance`.
struct Constraint<'a> {
inferred: InferredIndex,
references:- 4653: index, variance.to_str());
654: self.constraints.push(Constraint { inferred: InferredIndex(index),
655: variance: variance });
--
925: for constraint in self.constraints.iter() {
926: let Constraint { inferred, variance: term } = *constraint;
927: let InferredIndex(inferred) = inferred;