Rebalancing coherence: potential late-breaking change


#1

I recently realized that our current trait system contains a forward compatibility hazard concerned with negative reasoning. The TL;DR is that negative reasoning (that is, the compiler saying that “doing X is legal if the trait T is NOT implemented for some type U”) can easily make it impossible to add impls of any traits in a backwards compatible way. The most obvious example of negative reasoning are negative trait bounds, which have been proposed in a rather nicely written RFC. However, even without negative bounds, the trait system as currently implemented already has some amount of negative reasoning, in the form of the coherence system.

I’ve come up with a fairly simple proposal that tries to strike a good balance between parent and child crates, in terms of permitting parent crates to expand but also giving child crates lots of freedom to define the impls they need. However, it does involve tightening coherence so it is somewhat more restrictive (the current rules are designed to permit as much as possible in the child crates; but this winds up limiting the parent crates).

In the process of developing this proposal, I also went through many iterations and wrote up a lot of background material. Therefore, I’ve embedded all of that into a gist with multiple sections:

  1. The problem: explains why negative reasoning is dangerous.
  2. A simple fix: a simple proposal that we can use to avoid the problem. This solution is somewhat limiting and we may wish to evolve it to more comprehensive solutions in the longer term.
  3. Alternatives: other avenues that I explored and which may be the kernel of a more permissive solution.

I plan on opening an RFC regarding the simple solution shortly, but I wanted to post this out first.


#2

I’ve been doing some investigation into compiling cargo crates using this scheme. I’ll try to keep a log of problems I encounter.

  • error crate: impl<E: Error> FromError<E> for Box<Error> fails because Box is not local
  • hyper crate: some similar problems with boxed trait objects
  • regex crate:
    • impl<'t> Replacer for &'t str
    • impl<F> Replacer for F where F: FnMut(&Captures) -> String
    • in conflict because this requires that &str: !FnMut, and neither &str nor FnMut are local

Seems like all the “most downloaded” crates compile just fine except regex. If I permit Box<Local> to be considered local, hyper/iron seem to almost compile but I think they have some existing problems that prevent them from building atm.


#3

@Gankro suggested an interesting possible future generalization, which would be using the Deref trait to draw the line rather than &T and &mut T. I believe it’d be backwards compat to switch, because moving power over to child impls is backwards compat in general.


#4

After looking over the crates, I think I will wind up with a revised version of the proposal that also includes an unstable attribute (unstable because this part of the design seems like something we will want to refine; but we can still use it in libstd as I describe below). Let’s call it #[fundamental] for now – it indicates types/traits that are so fundamental, that adding impls for them is a breaking change.

For types, #[fundamental] would mean “adding a blanket impl over this type is a breaking change”. &T and &mut T are automatically #[fundamental]. Box would also be tagged #[fundamental].

For traits, #[fundamental] would mean “implementing this trait is a breaking change”. The Fn traits would be #[fundamental], since it is common to want to overload on closures vs other kinds of values.

The nice thing about this attribute is that it is a relatively minimal commit. That is, it commits us to finding some mechanism that can be used to make Box and the Fn traits work this way, but it doesn’t have to be the attribute. It is also something we can add to other types/traits over time, because making a type fundamental just lets children implement more impls, which is always backwards compatible (but we can never take the attribute away).

My feeling here is that it is unclear what precise mechanism we want long term to go beyond the basic rules I proposed (or perhaps generalize them), but whatever mechanism it is, it will want to support the impls on Box and Fn I encountered. So it makes sense to put in something simple for now that gives us breathing room to experiment.


#5

Amazing writeup. I am convinced we should bite the bullet and do this. I’ll cross my fingers that no more surprises appear next cycle.


#6

I mentioned this in the negative bounds rfc, but there was no answer.


#7

FYI @nikomatsakis has already wrote an RFC for this