infer or permit declarations of variance for type parameters

[nikomatsakis]

UPDATE

Variance inference is complete.

What is still missing is:

• applying results of variance inference to type parameters -- this is an expressiveness issue
• applying results of variance inference to trait matching (treatment of subtyping in trait matching is unsound #5781) -- this is a soundness issue

ORIGINAL

Today, we treat all type parameters as invariant, but infer variance for region parameters. We can use that same code which infers the variance for region parameters to infer the suitable variance for type parameters if we like.

Alternatively, if we decide that inference here is too magical, we could require explicit declaration of variance. In that case, i'd favor covariance as the default, and the possibility to write struct Foo<mut T> to indicate an invariant type parameter T (which can appear in mutable locations). This seems more intuitive than the usual + and -. We probably don't need a notation for contravariance, but in that case perhaps fn T (to indicate a type parameter that appears only in function arguments, far and away the most common place to have a contravariant type parameter).

Still, I think I favor inference. It's inline with what we do for regions and I think it will basically match up with user expectations.

[nikomatsakis]

Do not forget: current region parameterization inference codes does not consider supertrait inheritance.

[graydon]

Can you be a little more concrete about use cases and current failure modes? I'm having a hard time picturing the implications of this.

[brson]

Doesn't look like 0.6

[catamorphism]

Nominating for milestone 3, feature-complete

[bblum]

@graydon, I ran into this today. I had something like:

struct Foo<'self> {
    field1: &'self Bar
    field2: Option<&'self Baz>,
}

...and I needed to update such a struct that I already had with a new value for field2, and it wouldn't let me intersect the lifetimes (even though the subtyping was safe, it needed them to be equal due to invariance). I have a FIXME in a local branch which should show up here when I push it.

As a workaround, I wrote a hand-monomorphized enum that's the same as option but didn't have a type parameter. (I can imagine that would be impossible for someone implementing a generic data structure, though.)

[pnkfelix]

punting to later triage mtg with niko present.

[nikomatsakis]

Related to #5781

[graydon]

accepted for feature-complete milestone

[nikomatsakis]

@pcwalton thinks this isn't necessary for 1.0. I'm not sure I agree,
particularly because I encountered a lot of compilation errors trying
to fix the whole with the Self type parameter (referenced in my earlier comment).

[nikomatsakis]

As part of the code for #4846 I implemented a general variance inference algorithm, but I do not yet apply it to type parameters.

[pnkfelix]

nominating for discussion during triage when @nikomatsakis is present

[nikomatsakis]

Marking as E-mentor -- this is almost entirely done. The variance inference is written. The declarations are written (in the form of marker types). The only thing missing is to update the type inferencer to consider the results of variance inference rather than treating all type parameters as invariant, and to update the vtable matching code in a similar way. Not exactly easy changes but not terribly hard with some pointers.

[pnkfelix]

Assigning P-backcompat-lang, 1.0 blocker. (The current default of invariant is backwards compatible, but niko says there's some other interaction with trait-matching that niko says makes this more important to the point of being P-backcompat-lang.)

[nrc]

cc me

[nikomatsakis]

@edwardw I guess I don't know what problem you're encountering precisely. I know you sent me some gists but I never head time to read into them. Perhaps you can repost them here. It's hard to say what the options are without knowing what the problem is, it seems to me it's likely just a bug somewhere.

[edwardw]

@nikomatsakis, I'd like to draw your attention to this line of the PR: combine.rs. Without it, the patched rustc won't be able to compile kinds.rs. The specific error messages are:

#[lang="covariant_type"]
#[deriving(Eq,Clone)]  // error: cannot determine a type for this expression: unconstrained type
pub struct CovariantType<T>;

Same error if manually implementing the Eq and Clone traits.

[edwardw]

@nikomatsakis @nick29581 I think I figured out what are those mysterious bivariant. They come from nullary generic type. With that handled we are one step closer to fix this bug.

Since this is going to be a change with potentially big impact, do you have some specific tests in mind for it? Or some formerly ignored tests should be turned on as part of the fix?

[edwardw]

All is worked out. #12828 has all the details and I think it fixes both this bug and #5781 :) Please review.

[pcwalton]

Nominating for removal from 1.0 milestone because the remaining soundness issue is covered by #5781 which is already milestoned.

[brson]

P-high, not 1.0.

[rust-highfive]

This issue has been moved to the RFCs repo: rust-lang/rfcs#281