🔬 implement "always applicable impls"

[nikomatsakis]

Part of #31844: In order to eventually stabilize specialization, we need to make it sound. The current plan for doing so is called "always applicable impls", and is explained in this blog post. This issue exists to track the implementation of that proposal.

This does not yet have any mentoring instructions. Ping me if you are interested though and we can talk it over! Or maybe I'll get to it before then.

[giannicic]

@nikomatsakis I would like to take this since it's related to specialization, which is the topic I've covered the most. Months ago I wrote a tracking issue (#45982) pointing out the things to do related to "restrictions around lifetime dispatch".
If I understand correctly, the task number 2 and 3 of that list will be replaced by the "always applicable impls" proposal. Is it right?

[nikomatsakis]

@giannicic sounds about right, yes.

[giannicic]

@nikomatsakis
I've just finished reading the posts but I need some confirmation in order to procede.
It seems that, in order to implement the "always applicable", I should first extend specialization with the "intersection impls" feature.
So, I'll split this implementation in two PRs: the first that covers "intersection impls" and the second the "always applicable test".
Speaking about the first the thigs to do are:

• change the overlap method, it will return None if there is an impl that is the intersection between the two.
• if the intersection impl is not present show a proper note that explain which impl is still needed

Could work?
Thanks

[nikomatsakis]

@giannicic Sorry for the delay. PS, feel free to reach out on gitter as well.

It seems that, in order to implement the "always applicable", I should first extend specialization with the "intersection impls" feature.

I don't think that's necessary, but it seems ok to start there. I agree we want both eventually. It might also be better to wait on the "always applicable" side of the equation until we've made more progress around the chalk-ification process etc.

change the overlap method

Hmm, I don't know that I agree with that proposed change. I think overlap is just a test for whether things overlap -- and indeed they do overlap, so it should return Some. This is more of a "policy' question -- when is it an error to overlap.

That logic is presently handled here, when constructing the specialization graph. You can see that in the event of overlap it checks whether either of the two impls specialize one another:

rust/src/librustc/traits/specialize/specialization_graph.rs

Lines 141 to 154 in 0ff9872

	|overlap| {
	if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
	return Ok((false, false));
	}
	let le = tcx.specializes((impl_def_id, possible_sibling));
	let ge = tcx.specializes((possible_sibling, impl_def_id));
	if le == ge {
	Err(overlap_error(overlap))
	} else {
	Ok((le, ge))
	}
	},

I'm not entirely sure how best to extend this logic to intersection impls though. It seems like we need to start constructing a more complex graph? Maybe I'm overthinking it, but I am imagining something like adding all the impls to a graph, then adding "overlaps" and "specialized by" edges where applicable (note that "specialized by" implies "overlap").

So e.g. the classic "intersection" case might look like:

impl A   <--overlaps-->    impl B
   |                          |
   |                specialized by
   |                          v
   +-----specialized-by-> impl C

If we insert a synthetic "bottom" -- basically, an empty impl that hence specializes all others -- then we can say that impls A and B are allowed to overlap if their immediate, mutual postdominator in the graph is not the "bottom impl". Moreover, that postdominator is the specializing impl (in this case, C).

Note that we have a postdominator computation in librustc_data_structures.

Thinking about this a bit more, I guess we just need to compute the "specialized by" edges -- we may not need to "materialize" the overlaps edges, though we probably want to keep a list for later reference of things that overlapped but did not specialize (so we can check that they have a mutual postdominator).

Does that make some sense?

[giannicic]

@nikomatsakis
I understood, I'm doing as you explained. I'll bother you if I have any other doubts :)
Thanks

[giannicic]

Status update.
What I'm trying to do is to change the specialization graph structure to allow insertion of multiple parents (in case of intersection impls) and overlaps edges.
In order to do this i've changed the graph structure like this:

pub struct Graph {
    // all impls have a parent; the "root" impls have as their parent the def_id
    // of the trait
    // allow one or more parents since an intersection impl has at least two parents
    parent: DefIdMap<Vec<DefId>>,

    // provide overlap edges, I'm still not sure if, for any given overlap, I should insert two nodes in the 
    // maps (Eg <impl1, impl2> and <impl2, impl1>)
    overlap: DefIdMap<DefId>,

    // the "root" impls are found by looking up the trait's def_id.
    children: DefIdMap<Children>,
}

Inserting multiple parent implies that each possible impl must be visited in order to find the parents of a given impl. So the insert method should return a Result<Vec<Inserted>, OverlapError>

Then the overlap error can no more be triggered at insertion time but should be checked once the graph is fully build. I'll use the overlap edges in order to check for overlapping errors.

@nikomatsakis
Let me know what you think.
Thanks

[nikomatsakis]

@giannicic this looks roughly right. I suspect we don't need to store the overlap edges in the graph -- after all, I think we only need them during overlap checking. We could keep a set of pairs instead. Regarding whether to store in "both directions", I would instead canonicalize the def-ids so that the "lower" one appears first, since you don't really need to store both directions.

[JulianKnodt]

Is this issue still open/have things significantly changed? I'd like to work on it if so.

[clarfonthey]

Also left a comment on #31844 but I figured I might as well add this here while I was exploring the possibility of specialising some iterator methods.

From Niko's blog post, this example specifically is brought up as being problematic:

trait Example {}
impl<T> Example for T where T: Clone { }
impl<T> Example for Vec<T> where T: Clone { }

Since, effectively, we can't guarantee that Vec<T>: Clone implies T: Clone, at least in this case. But, what if we moved the bound to the trait itself?

trait Example: Clone {}
impl<T> Example for T where T: Clone { }
impl<T> Example for Vec<T> where T: Clone { }

Now, it doesn't really matter if Vec<T>: Clone implies T: Clone, since T: Clone is guaranteed to be a blanket implementation, and thus always applicable.

There are definitely cases where I'd still like to rely on the full functionality (for example, assuming &mut I: Iterator implies I: Iterator), but at least this subset seems reasonable to support.