regression in method dispatch

[nikomatsakis]

According to @SimonSapin, #43880 likely broke Servo's build. Servo itself is fixed in https://github.com/servo/servo/pull/18327, but I'm opening this issue to decide on whether this regression is a bug or expected behavior.

cc @arielb1

[SimonSapin]

The code that broke is:

#[derive(JSTraceable)]
pub enum Filter {
    None,
    Native(fn (node: &Node) -> u16),
    JS(Rc<NodeFilter>)
}

/// A trait to allow tracing (only) DOM objects.
pub unsafe trait JSTraceable {
    /// Trace `self`.
    unsafe fn trace(&self, trc: *mut JSTracer);
}

unsafe impl<A, B> JSTraceable for fn(A) -> B {
    #[inline]
    unsafe fn trace(&self, _: *mut JSTracer) {
        // Do nothing
    }
}

#[proc_macro_derive(JSTraceable)]
pub fn expand_token_stream(input: proc_macro::TokenStream) -> proc_macro::TokenStream {

    // ...

    let style = synstructure::BindStyle::Ref.into();
    let match_body = synstructure::each_field(&mut type_, &style, |binding| {
        Some(quote! { #binding.trace(tracer); })
    });

    // ...

I think the generated code would look something like this:

unsafe impl JSTraceable for Filter {
    unsafe fn trace(&self, tracer: *mut JSTracer) {
        match *self {
            Filter::Native(ref field1) => {
                field1.trace(tracer);
            }
            // ...
        }
    }
}

The error message in rustc 1.21.0-nightly (7eeac1b81 2017-08-30) was:

   Compiling script v0.0.1 (file:///home/simon/servo2/components/script)
error[E0599]: no method named `trace` found for type `&fn(&dom::node::Node) -> u16` in the current scope
   --> /home/simon/servo2/components/script/dom/treewalker.rs:464:10
    |
464 | #[derive(JSTraceable)]
    |          ^^^^^^^^^^^
    |
    = note: JSTraceable is a function, perhaps you wish to call it
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following trait defines an item `trace`, perhaps you need to implement it:
            candidate #1: `dom::bindings::trace::JSTraceable`

error: aborting due to previous error

error: Could not compile `script`.

The fix was adding a new impl for fn(&A) -> B, in addition to the one for fn(A) -> B. Isn’t the former a subset of the types covered by the latter?

unsafe impl<'a, A, B> JSTraceable for fn(&A) -> B {
    #[inline]
    unsafe fn trace(&self, _: *mut JSTracer) {
        // Do nothing
    }
}

[nikomatsakis]

@SimonSapin thanks for the detailed notes.

I was talking to @arielb1 and I understand better the reason for the change. I am of two minds about it, to be honest. In short, under the older algorithm, we integrate "impl selection" directly into method dispatch. In particular, for each potentially applicable impl, we would instantiate the impl and then check whether the receiver type was a valid subtype of what the impl expected. In this case, the receiver type is for<'a> fn(&'a u8). This is a valid subtype of fn(A) where A = &'x u8, because 'a can be instantiated as 'x. Under the newer algorithm, we use trait selection instead. This creates a problem: an impl like impl<A> Foo for fn(A) doesn't implement Foo for for<'a> fn(&u8), because of the placement of the region binders.

This handling of region binders is a subtle point in Rust, and one that I actually consider a borderline bug. In particular, I'm in the process of various refactorings that aim to make the internal handling of higher-ranked things more consistent with all other regions, which offers a lot of simplicity across the board. But one side-effect is that we would no longer permit an impl of Foo for both fn(&u8) and fn(A) -- in other words, the workaround that @SimonSapin put in place would no longer work, which seems suboptimal. (In particular, I aim to have region erasure erase region bindings altogether.)

(It may be that these refactorings I would like to do can't be done the way I wanted to do them, though, since there could be other code relying on the existing behavior; it's hard to be sure without a working branch to test with (which I think is close)).

[SimonSapin]

because of the placement of the region binders.

I don’t understand what that means. Is this a concept of the language that is relevant to its users, or only an internal detail of the compiler’s implementation?

But one side-effect is that we would no longer permit an impl of Foo for both fn(&u8) and fn(A)

Right, #43880 was a breaking change so effectively reverting it is another breaking change (unless it happens within the same release cycle).

The team needs to decide whether this breakage is acceptable per https://github.com/rust-lang/rfcs/blob/master/text/1122-language-semver.md.

[SimonSapin]

And the larger policy question is: “it doesn’t affect any code that happens to be tested by crater/cargobomb” sufficient to justify any breaking change, even if it not a soundness fix?

[nikomatsakis]

@SimonSapin

I don’t understand what that means. Is this a concept of the language that is relevant to its users, or only an internal detail of the compiler’s implementation?

Sorry, I geeked out a bit in the response there. The answer is somewhere in the middle. In short, there are corner cases of the language that interact with particulars in the implementation. Sometimes this gives rise to complicated or internally inconsistent definitions. The goal of #43880 was effectively to remove some "conceptual duplication" between how trait matching worked during method dispatch and how it works at other times.

The changes I was describing around subtyping and higher-ranked regions are another such case. They are independent except that they both interact on this particular example.

Right, #43880 was a breaking change so effectively reverting it is another breaking change (unless it happens within the same release cycle).

This does not necessarily -- that is, I don't know that @arielb1's new method dispatch code accepts anything in particular that the old code did not, but I could be wrong.

The team needs to decide whether this breakage is acceptable per https://github.com/rust-lang/rfcs/blob/master/text/1122-language-semver.md.

Indeed, we do. In my view, all of the changes under discussion fall roughly under the "Underspecified language semantics" heading. This is not to say we should necessarily make those changes -- just that they are the kinds of changes that arise we seek to clean up the compiler implementation and the definition of the trait system. In such cases, the "real-world effects" (i.e., how much code is affected) is definitely a consideration, as is the magnitude of the cruft.

[SimonSapin]

In my view, all of the changes under discussion fall roughly under the "Underspecified language semantics" heading.

Alright, that's fair enough.

And as @aturon just said on IRC it's also the role of Nightly to catch issues like this that might have slipped through cargobomb, with time before they reach Stable.

[nikomatsakis]

@rfcbot fcp close

OK, having had time to think this over, I think the general feeling is that the change here was both permitted and a good change, although the regression is unfortunate. The intention is to clarify and improve method dispatch, and in particular to avoid having two "similar but different in subtle ways" implementations of how to match a trait against impls.

This does however mean that the behavior with respect to function types, consolidating on the behavior using during trait selection (which hence requires that the type of receiver be equal to the type in the trait impl, rather than being a subtype).

I'm going to move that we close this issue, therefore.

[rfcbot]

Team member @nikomatsakis has proposed to close this. The next step is review by the rest of the tagged teams:

• [x] @aturon
• [x] @cramertj
• [x] @eddyb
• [x] @nikomatsakis
• [x] @nrc
• [x] @pnkfelix
• [x] @withoutboats

No concerns currently listed.

Once these reviewers reach consensus, this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[SimonSapin]

I think the general feeling is that the change here was […] a good change

Do you mean that the language should not be changed later to make impl<A, B> SomeTrait for fn(A) -> B apply again to fn(&'a Foo) -> Bar?

[withoutboats]

Could we crater this?

[SimonSapin]

Cargbomb was used: https://github.com/rust-lang/rust/pull/43880#issuecomment-323729971 but unfortunately it did not include Servo. (BTW could we fix that?)

[withoutboats]

Thanks for the info!

[eddyb]

cc @rust-lang/infra on https://github.com/rust-lang/rust/issues/44224#issuecomment-329619451.

[SimonSapin]

Let’s move the servo-in-cargobomb discussion to a separate thread: https://github.com/rust-lang-nursery/cargobomb/issues/133

[arielb1]

Changes in method matching against higher-ranked types

One edge-case in Rust's type-system is higher-ranked types (don't confuse with higher-kinded types, which aren't supported or planned to be supported). In plain words, these are types that contain a for<'lifetime> in them - for example, for<'a> fn(&'a Foo) -> Bar. In Rust, these are always function pointer or trait object types.

Part A - Incomplete impls

One problem with these types, is that they can't directly be decomposed into smaller types. for<'a> fn(&'a Foo) -> Bar is not equal to fn(T) -> Bar for any T (after all, what would that T be? for<'a> &'a Foo? That is not a type, and would give us fn(for<'a> &'a Foo) -> Bar, which has the for in the wrong place).

This means that traits can't be implemented fully generically for them, as they won't be matched by an impl<A, B> JSTraceable for fn(A) -> B. You have to write a more specific impl, like impl<A, B> JSTraceable for for<'a> fn(&'a A) -> B.

That was always the case, and probably will always be the case - you simply can't pick a value for A in that example.

NB: With higher-ranked types you could theoretically have something like impl<A<*>, B<*>> JSTraceable for for<'a> fn(A<'a>) -> B<'a>, but that opens it own can of worms.

Part B - Imperfect subtyping

The reason you could get away with only 1 impl is that there's subtyping between higher-ranked types and their concrete versions (actually, this is a kind of "subtyping" that even Haskell has, they just doesn't call it that way), which means that code like this compiles:

let my_fn : &fn(_) -> _ = &my_fn; // trigger subtyping
JSTraceable::trace(my_fn, tracer);

Now you would think subtyping would work automatically, without any annotations. In most situations, this is how it works. However, another annoyance with HRTs is that type-inference involving them is undecidable, which means compilers need to perform some hacks to make it work.

The hack rustc uses is that higher-ranked subtyping is "eager", like a coercion - if there are no type hints available at the moment subtyping would be done, it does not trigger. This means that in an example like JSTraceable::trace(&my_fn, tracer), the opportunity for subtyping would be missed and you'll get an error without the type hint.

If you add the type hint, everything works fine (yes I know this is hard to do with macros).

The Change

Before #43880, trait method selection used to provide type hints based on impls. So it would notice the impl<A, B> JSTraceable for fn(A) -> B impl, and try to perform subtyping to get it to match.

That type hint action was a pirate feature that complicated method dispatch and added a bunch of odd edge cases to the compiler, so it was removed. That means the opportunity for higher-ranked subtyping is missed, and you get a type error.

[SimonSapin]

Thanks for the detailed explanation @arielb1. This all makes sense. At this point I’m only worried about what @nikomatsakis wrote earlier:

I'm in the process of various refactorings that aim to make the internal handling of higher-ranked things more consistent with all other regions, which offers a lot of simplicity across the board. But one side-effect is that we would no longer permit an impl of Foo for both fn(&u8) and fn(A) -- in other words, the workaround that @SimonSapin put in place would no longer work, which seems suboptimal. (In particular, I aim to have region erasure erase region bindings altogether.)

Why would impl<'a, A> Foo for fn(&'a A) and impl<A> Foo for fn(A) not be both permitted, if fn(&u8) never matches the latter?

[arielb1]

Why would impl<'a, A> Foo for fn(&'a A) and impl<A> Foo for fn(A) not be both permitted, if fn(&u8) never matches the latter?

We were talking about some theoretical concerns, but here's the practical thing: we might want for<'b> fn(&'α &'b u32) (for some "free" lifetime 'α) to be equal to fn(&'α &'α u32). If we want to allow that, we obviously can't allow there to be 2 separate impls.

Let's see why is that is sane:

1. Obviously, for<'b> fn(&'α &'b u32) is a subtype of fn(&'α &'α u32) (just substitute 'b ← 'α).
2. In the other direction: suppose we have a fn(&'α &'α u32), and we want to use it as an for<'b> fn(&'α &'b u32). A for<'b> fn(&'α &'b u32) is actually a for<'b> WF(&'α &'b u32) ⇒ fn(&'α &'b u32) - the caller has to prove that it is well-formed before calling it (this is just how higher-ranked functions work in Rust). However, that means that the assigned lifetime for 'b must be longer than 'α, which means the argument is a valid &'α &'α u32. So calling the fn(&'α &'α u32) is sound.

Now, if we want, we can take account of that other subtyping as a part of our subtyping rules, and by antisymmetry of subtyping (which I think we'll like to maintain) add that equality to our type equality rules. However, I'm not sure we really want to implement it - it feels like a too confusing addition to an already-complicated thing - HRTs are already complicated enough on their own, and type equality is by itself complicated enough on its own, so doing a breaking change in preparation for a feature we don't actually want to implement feels silly. cc @nikomatsakis .

[arielb1]

I'll note that you can't do this sort of subtyping in today's trait dispatch, because it doesn't assume the trait's arguments are WF in order to do the subtyping.

trait Foo<'a> {
    fn foo<'b>(x: &'a &'b u32) {}
}

impl<'a> Foo<'a> for () {
    fn foo(x: &'a &'a u32) {} //~ ERROR
}

[cramertj]

@rfcbot reviewed

(I don't have permission to check boxes in rust-lang/rust)

[eddyb]

@cramertj Pretty sure that permission is literally "editing anyone else's comments".

• [x] yup

[cramertj]

@eddyb Yes, but I have that permission in rust-lang/rfcs :smile:

[aturon]

Checked for @nrc, who is away.

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period is now complete.

[nikomatsakis]

Closing as resolved.