Conditional OIBITS

[wthrowe]

Since there are now at least two RFCs (#1323, #1379) in various stages of development using nontrivial conditionally implemented OIBITS, I think the issue of what such implementations actually mean should be resolved.

The OIBIT RFC explains the behavior of OIBIT impls as follows:

Intuitively, to check whether a trait Foo that contains a default impl is implemented for some type T, we first check for explicit (positive) impls that apply to T. If any are found, then T implements Foo. Otherwise, we check for negative impls. If any are found, then T does not implement Foo. If neither positive nor negative impls were found, we proceed to check the component types of T (i.e., the types of a struct's fields) to determine whether all of them implement Foo. If so, then Foo is considered implemented by T.

This is relatively straightforward, but isn't what was actually implemented in the compiler. rustc's behavior is roughly: Examine all impls of Foo that could apply to T, ignoring any bounds on parameters. If any such impls are found and they apply (now considering bounds) then T implements Foo or not depending on whether the impl was positive or negative. If no such impls are found, then the component types are examined as specified in the RFC. Otherwise, T does not implement Foo.

This differs from the RFC behavior in the case where there is an implementation, that would apply except that trait bounds prevent it from doing so. (Also the compiler won't allow there to be both a positive and a negative impl that apply to the same type, but that's not important here.)

For the case of conditional negative impls, this results in bounds effectively being ignored (#23072). Conditional negative impls give other weird behavior as well (#29499) and no one seems to really object to the idea of simply banning them, at least for the time being (first point in the OIBIT tracker). (This should be relatively easy to implement, since it is the same restriction placed on Drop impls.)

The case of conditional positive impls is trickier (#27554). For example, given the (silly) impl

struct Ty(T);
unsafe impl<T: Clone> Sync for Ty(T) {}

some people expect the RFC behavior (Ty<T> is Sync if either T is Sync or T is Clone) and some expect the implemented behavior (Ty<T> is Sync if and only if T is Clone). The current behavior certainly seems to be somewhat buggy, since it results in these two impls having different meanings:

struct Ty<T, U>(T, U);
trait Foo {}
impl Foo for .. {}

// Version 1: Ty<(), i32> is not Foo
trait Same {}
impl<T> Same for (T, T) {}
impl<T, U> Foo for Ty<T, U> where (T, U): Same {}

// Version 2: Ty<(), i32> is Foo
impl<T> Foo for Ty<T, T> {}

It is not obvious what the correct behavior is here, and, unfortunately, any change to the OIBIT resolving code (for positive impls) is a breaking change. (If a type changes from, say, Sync to non-Sync code stops compiling; if it changes from non-Sync to Sync we've potentially silently changed code from safe to unsafe.) This also will likely interact with whatever form of specialization eventually gets added to the language.

I don't think these concerns apply to any of the OIBIT impls currently in the standard library (the negative impls are all unconditional and the positive impls are all on types that have components that never implement the trait), but they do come into play for the recent RFCs.

I think we should make some sort of decision about how these impls should work, at least for the time being, before they enter more widespread use. (My personal preference would be to ban the ambiguous cases until we have an approved version of specialization, but doing so might interact badly with the coherence rules and I'm not sure if there is a good way to actually detect such cases: rustc is designed to prove that types implement traits, not to prove that they don't implement them.)