Our plan for specialization as of now (or, my understanding of a conversation with @aturon):

First, #39 will land giving us the overlap check. I'm going to modify this to, when impls overlap, instead of erroring, follow up with queries to determine if one specializes the other. If there is a specialization relationship, we'll add it to a forest of ImplDatums.

Once that forest has been constructed by the overlap check, that represents the specialization hierarchy of all the impls available. We'll then iterate over those impl datums, mutating them to add a priority ranking, representing their distance from the root of their tree in the forest.

These priority rankings will be used to dispatch associated items the correct impl. Consider these two impls:

trait Foo {
     type Assoc;
}

impl<T> Foo for Vec<T> {
     default type Assoc = bool;
}

impl Foo for Vec<u32> {
    type Assoc = ();
}

The first impl will have priority 0, whereas the second will have priority 1. These impls will correspond to facts like these:

// First impl
Vec<?T>: Foo.
Vec<?T> Foo<Assoc = bool> :- Priority(?T: Foo) >= 0 /\  not { Priority(?T: Foo) >= 1 }.
forall<T> { Priority(Vec<?T>: Foo) >= 0. }

// Second impl
Vec<?T> Foo<Assoc = ()> :- Priority(?T: Foo) >= 1 /\ not { Priority(?T: Foo) >= 2 }.
Priority(Vec<u32> >= 1).

From these facts the solver can dispatch associated items correctly.

One thing that's nice about this system is that impls from upstream crates do not need to have their lowering modified in the presence of new impls. We could literally cache the lowered representation in the .rlib or whatever, and then just load it from disk before lowering the currently compiled crate. However, the logic engine only needs to gain an understanding of a "greater than or equal to" relationship, and not specialization proper.

Specialization #9

Description

nikomatsakisopenedon Jan 16, 2017

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

nikomatsakis
openedon Jan 16, 2017