treatment of subtyping in trait matching is unsound

[nikomatsakis]

We currently assume (at least in vtable.rs. though not in infer) that self types are contravariant. This is not sound since the Self type can appear anywhere, including return types.

For example, this program compiles:

trait Make {
    fn make() -> Self;
}

impl Make for *const uint {
    fn make() -> *const uint {
        ptr::null()
    }
}

fn maker<M:Make>() -> M {
    Make::make()
}

fn main() {
    let a: *uint = maker::<*uint>();
}

Note that we have "produced" a *uint even though there is no function in this program that returns one. In this case, it's harmless, but of course one can construct other more harmful examples (particularly if we add other forms of subtyping such as struct inheritance or datasort refinements).

The fix is a straight-forward modification (search for FIXMEs) but it invalidates a number of existing impls based around *const T and I didn't feel like dealing with the fallout as part of the patch I'm working on.

See also #3598---effectively we need a way to infer/declare variance for the Self parameter as well.

[pnkfelix]

nominating for maturity milestone 1: Well defined.

[nikomatsakis]

I have a local fix for this that simply makes trait matching invariant. It causes a number of compilation errors. The proper fix is to infer variance (#3598). I agree with the nomination that without settling this, the language is not well-defined.

[graydon]

accepted for well-defined milestone

[nikomatsakis]

Note: work on variance inference is underway, so this should be addressable soon-ish.

[nikomatsakis]

PR #10153 includes a general variance inference pass that should allow us to address this

[pcwalton]

I believe this was accidentally fixed by DST, as @edwardw's code changes to variance were effectively introduced. I have rebased all test cases here and they are correctly rejected. Will close after a PR to add tests.