Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Coherence can be bypassed by an indirect impl for a trait object #57893

Open
arielb1 opened this issue Jan 25, 2019 · 28 comments

Comments

Projects
None yet
8 participants
@arielb1
Copy link
Contributor

commented Jan 25, 2019

Comments

The check for manual impl Object for Object only makes sure there is no direct impl Object for dyn Object - it does not consider such indirect impls. Therefore, you can write a blanket impl<T: ?Sized> Object for T that conflicts with the builtin impl Object for dyn Object.

Reproducer

I had some difficulties with getting the standard "incoherence ICE" reproducer, because the object candidate supersedes the impl candidate in selection. So here's a "transmute_lifetime" reproducer.

trait Object {
    type Output;
}

trait Marker<'b> {}
impl<'b> Marker<'b> for dyn Object<Output=&'b u64> {}

impl<'b, T: ?Sized + Marker<'b>> Object for T {
    type Output = &'static u64;
}

fn foo<'a, 'b, T: Marker<'b> + ?Sized>(x: <T as Object>::Output) -> &'a u64 {
    x
}

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Object<Output=&'a u64>>(x)
}

// And yes this is a genuine `transmute_lifetime`!
fn get_dangling<'a>() -> &'a u64 {
    let x = 0;
    transmute_lifetime(&x)
}

fn main() {
    let r = get_dangling();
    println!("{}", r);
}
@scalexm

This comment has been minimized.

Copy link
Member

commented Jan 31, 2019

@arielb1 Interesting. I guess we would need a deeper check, something along the lines of:

impl<T> Object for SomeType<T> where WC {
/* ... */
}
// If the following goal has a non-empty set of solutions, reject the impl.
exists<T> {
    exists<U> {
        Unify(dyn Object<Output = U>, SomeType<T>),
        dyn Object<Output = U>: WC
    }
}

cc @nikomatsakis

@arielb1

This comment has been minimized.

Copy link
Contributor Author

commented Feb 2, 2019

Sure.

What makes this non-trivial is auto-traits (dyn Object + Send is a distinct wrt. unification from dyn Object), and to some extent binders (unless you ignore them in unification). i.e., supposing the impl you have is

impl<T> Object<'a> for SomeType<T> where WC

Then the "ideal" lowering would be something of this format:

// If the following goal has a non-empty set of solutions, reject the impl.
exists<T: type, 'a('x): lifetime -> lifetime, U('x): lifetime -> type, AT: list of auto-traits> [
    Unify(dyn for<'s> Object<'a('s), Output = U('s)> + AT, SomeType<T>),
    dyn for<'s> Object<'a('s), Output = U('s)> + AT: WC
}

If you ignore binders in unification (i.e., you consider for<'a> Object<'a, Output=&'a T> to be the same as Object<'x, Output=&'y T> in coherence), then you don't have to deal with the HRTB problem, but you still have to deal with auto-traits:

// If the following goal has a non-empty set of solutions, reject the impl.
exists<T: type, 'a: lifetime, U: type, AT: list of auto-traits> [
    Unify(dyn Object<'a, Output = U> + AT, SomeType<T>),
    dyn Object<'a, Output = U> + AT: WC
}

While I don't think this is insurmountable, it is fairly annoying and places some restrictions on how you encode auto-traits.

@Aaron1011

This comment has been minimized.

Copy link
Contributor

commented May 30, 2019

I'm interested in working on this.

@Aaron1011

This comment has been minimized.

Copy link
Contributor

commented Jun 9, 2019

It turns out that only one trait is necessary to reproduce this: (playground)

trait Object {
    type Output;
}

impl<T: ?Sized> Object for T {
    type Output = &'static u64;
}

fn foo<'a, T: ?Sized>(x: <T as Object>::Output) -> &'a u64 {
    x
}

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Object<Output=&'a u64>>(x)
}

// And yes this is a genuine `transmute_lifetime`!
fn get_dangling<'a>() -> &'a u64 {
    let x = 0;
    transmute_lifetime(&x)
}

fn main() {
    let r = get_dangling();
    println!("{}", r);
}

This seems quite bad, as simply writing a blanket impl is enough to expose the issue.

@Aaron1011

This comment has been minimized.

Copy link
Contributor

commented Jun 9, 2019

One way to fix this issue would be the following:

If a trait has any associated items, and a blanket impl exists for it, that trait cannot be object-safe.

This is pretty extreme - however, the only other solution I can think of would be to deny all blanket impls of a trait with associated items - which seems even worse, given that the trait might not have even been object-safe to begin with.

@Centril

This comment has been minimized.

Copy link
Member

commented Jun 9, 2019

Unfortunately, it gets worse. Here's an implementation of mem::transmute in safe Rust:

trait Object<U> {
    type Output;
}

impl<T: ?Sized, U> Object<U> for T {
    type Output = U;
}

fn foo<T: ?Sized, U>(x: <T as Object<U>>::Output) -> U {
    x
}

fn transmute<T, U>(x: T) -> U {
    foo::<dyn Object<U, Output = T>, U>(x)
}

I think blame should be assigned to not normalizing <T as Object<U>>::Output to U in fn foo. If that happened, foo::<dyn Object<U, Output = T>, U>(x) would not type-check.

I checked the code above with godbolt and the problem has existed since Rust 1.0.0.

@jonas-schievink

This comment has been minimized.

Copy link
Member

commented Jun 9, 2019

The first comments in the thread seem to indicate that the problem is instead with the blanket impl itself being accepted by the compiler.

If I understood correctly, @Centril's impl above can be applied to dyn Object<U, Output=T> for any U and T, and defines Output=U. However, a trait object like dyn Object<U, Output=T> already provides an implicit impl with the same input types, but a different output type, which is incoherent.

@jonas-schievink

This comment has been minimized.

Copy link
Member

commented Jun 9, 2019

Seems like a good idea to discuss in language and compiler team, nominating.

@Centril

This comment has been minimized.

Copy link
Member

commented Jun 9, 2019

Notably, in my reproducer above, if you change fn foo to:

fn foo<T: ?Sized + Object<U>, U>(x: <T as Object<U>>::Output) -> U {
    x
}

then you will get:


error[E0308]: mismatched types
  --> src/lib.rs:10:5
   |
9  | fn foo<T: ?Sized + Object<U>, U>(x: <T as Object<U>>::Output) -> U {
   |                                                                  - expected `U` because of return type
10 |     x
   |     ^ expected type parameter, found associated type
   |
   = note: expected type `U`
              found type `<T as Object<U>>::Output`
@jonas-schievink

This comment has been minimized.

Copy link
Member

commented Jun 9, 2019

Is that not just due to where-clauses having precedence over impls? AFAIK trait selection will prefer the Object<U> impl in the bounds, which doesn't have an assoc. type specified, so the compiler can't normalize it.

@Aaron1011

This comment has been minimized.

Copy link
Contributor

commented Jun 10, 2019

I made a first attempt at a fix here: https://github.com/Aaron1011/rust/tree/fix/trait-obj-coherence

My idea was to extend the obligations generated by ty::wf::obligations to include projection predicates of the form:

<dyn MyTrait<type Assoc=T> as MyTrait>::Assoc = T.

This is combeind with an extra flag in SelectionContext to force impl candidates to be chosen over object candidates. In the case of an incoherent blanket impl (e.g. any of the reproduces in this thread), <dyn MyTrait<type Assoc=T> as MyTrait>::Assoc should project to the type specified in the blanket impl. This will fail to unify with T, correctly causing a compilation error.

Unfortunately, I wasn't able to get this working, due to how the well-formed predicate generation is integrated with the rest of the compiler. I would need to significantly refactor FulfillmentContext, SelectionContext, and/or Predicatein order to keep track of the extra flag that needs to be passed toSelectionContext`.

I'm hoping that someone can come up with a better approach. However, any solution will need to deal with the fact that SelectionContext masks attempts to detect the incoherence by discarding the impl candidate in favor of the object candidate.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Jun 10, 2019

This is interesting! The fact that foo in @Centril's example even gets accepted shows that we aggressively exploit coherence during type-checking: because we saw an impl that uses a certain associated type, we type-check assuming that that is the impl that got used here. Unfortunately, as the example here shows, that is in conflict with the "implicit impl" that we get for trait objects.

I wouldn't be sad if we would fix this by being less aggressive about exploiting coherence during type-checking -- that makes analysis much more complicated, and this example shows why. But there's likely already tons of code out there that exploits this. Another fix is to refuse to create trait objects that "contradict" the kind of coherence knowledge that the type checker might exploit, but that seems extremely fragile.

@Aaron1011 your plan seems to be to encode in the type of foo the fact that we exploited coherence? However this "exploitation" happens in the body of the function, so what exactly gets exploited cannot be known yet when computing the well-formedness predicate for foo. Thus I guess what you want to / have to do is to aggressively look for all things one might be able to exploit up-front, add them all to the well-formedness obligations, and then during type-checking the boy look only at the obligations and not exploit coherence any more (as doing so would introduce scary bugs if the two systems for getting such type equalities out of coherence would ever not agree).

Once again, exploiting assumptions implicitly instead of inferring them to an explicit form proves to be an issue. This reminds me that we still implicitly exploit WF everywhere instead of turning that into explicit assumptions...

@pnkfelix

This comment has been minimized.

Copy link
Member

commented Jun 13, 2019

triage: P-high due to unsoundness. Leaving nominated in hope of discussing today. Not assigning to anyone yet.

@pnkfelix pnkfelix added the P-high label Jun 13, 2019

@pnkfelix

This comment has been minimized.

Copy link
Member

commented Jun 13, 2019

assigning to @nikomatsakis with expectation that they will delegate. (and removing nomination label)

@Centril

This comment has been minimized.

Copy link
Member

commented Jun 13, 2019

Still nominated for t-lang.

@arielb1

This comment has been minimized.

Copy link
Contributor Author

commented Jun 26, 2019

@RalfJung

I am not sure that giving up on coherence is the right choice here. I think it is too easy to split the code into functions, such that no one function sees the coherence violation:

struct Data<T: ?Sized, U> where T: Object<U> {
    data: <T as Object<U>>::Output
}

trait Object<U> {
    type Output;
}

trait Mark {
    type Output;
}

impl<T: ?Sized, U: Mark<Output=V>, V> Object<U> for T {
    type Output = V;
}

fn iso_1<T, U>(data: T) -> Data<dyn Object<U, Output=T>, U> {
    // in any coherence-less solution, this shouldn't "see" the
    // blanket impl, as it might not apply (e.g., `Local` might
    // be in a third-party crate).
    Data { data }
}

fn iso_2<X: ?Sized, U, V>(data: Data<X, U>) -> V
    where U: Mark<Output=V>
{
    // similarly, this shouldn't "see" the trait-object impl.
    data.data
}

fn transmute_m<T, U, V>(data: T) -> V
    where U: Mark<Output=V>
{
    // This function *also* shouldn't see the blanket impl - `Local`
    // might be in a third-party crate.
    iso_2::<dyn Object<U, Output=T>, U, V>(
        iso_1::<T, U>(data)
    )
}

// These 3 functions could be in a child crate

struct Local<T>(T);

impl<T> Mark for Local<T> {
    type Output = T;
}

fn transmute<T, U>(x: T) -> U {
    // and this function shouldn't see *anything* that looks like a
    // problematic associated type.
    transmute_m::<_, Local<_>, _>(x)
}
@arielb1

This comment has been minimized.

Copy link
Contributor Author

commented Jun 26, 2019

I think that conditioning object safety on an object type being coherent is a reasonable-enough way out of this.

If we want to be tricky, we might put the condition "directly" on the impl - i.e., have ObjectCandidate not apply if an ImplCandidate might "theoretically" apply to any substitution of this type. This would however require doing coherence-style negative reasoning during selection, which would be ugly.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Jun 26, 2019

@arielb1 your iso_2 exploits coherence, so "giving up on exploiting coherence" would not let that function type-check.

@arielb1

This comment has been minimized.

Copy link
Contributor Author

commented Jun 26, 2019

@RalfJung what's the specific way that makes iso_2 exploit coherence?

The wrong derivation that it makes is <X as Object<U>>::Output = V :- U: Mark<Output=V>. I don't think we want to avoid making that sort of derivation "unconditionally" (or is it implicitly making some other derivation?).

@arielb1

This comment has been minimized.

Copy link
Contributor Author

commented Jun 26, 2019

It seems like a basic rule of Rust that we want to keep that it is possible to follow impls. e.g., with IntoIterator, you really want typeck to be able to assume that <T as IntoIterator>::Item = U := T: Iterator, <T as Iterator>::Item = U.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Jun 26, 2019

follow impls

That is exactly what I mean by "exploiting coherence": seeing an impl that applies and relying on the fact it is the only one that can ever apply.

@Centril

This comment has been minimized.

Copy link
Member

commented Jun 27, 2019

@pnkfelix

This comment has been minimized.

Copy link
Member

commented Jun 27, 2019

Discussed at T-compiler meeting. Assigning to @Centril to take point on seeing that progress is made on this issue, in some form.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Jul 11, 2019

We discussed this in depth at today's lang team meeting. We enumerated a few possible solutions to the problem.

The problem

Presently, if you have an object-safe trait Object, the compiler 'auto-generates' an impl like

impl Object for dyn Object { }

However, we do not forbid you from making a potentially duplicate impl:

impl<T: ?Sized> Object for T { }

This in and of itself is not so harmful, but it causes a problem if you have associated types:

trait Object<U> {
    type Output;
}

In this case, the compiler would "auto-generate" an impl like:

impl<A, B> Object<A> for dyn Object<A, Output = B> {
    type Output = B;
}

However, the user could provide an impl that has a different value for the associated type:

impl<A, B> Object<B> for A
where
    B: ?Sized,
{
    type Output = B;
}

Now the problem is that different parts of the compiler could select different impls, resulting in distinct values for Output. In @Centril's example (#57893 (comment)), there is a helper function foo which only knows that it has some T: ?Sized, so it uses the user's impl to resolve Output:

fn foo<T: ?Sized, U>(x: <T as Object<U>>::Output) -> U {
    //                  ^^^^^^^^^^^^^^^^^^^^^^^^^
    // Resolves to `U`, so `foo` thinks it has an argument of
    // type `U` -- therefore, it can be returned.
    x
}

On the other hand, the transmute function invokes foo with the type dyn Object<U, Output = T>:

fn transmute<T, U>(x: T) -> U {
    foo::<dyn Object<U, Output = T>, U>(x)
    //                           ^
    // Output is normalized to `T`
}

This winds up resolving using the "auto-generated" impl, and hence Output is normalized to T -- therefore, we can give an x: T, and we get back a U. (Reading the source, I'm actually not entirely sure why this happens, I might have thought it would result in ambiguity... but in any case it clearly does.)

OK -- I was supposed to start with the solutions, and @Centril was supposed to write-up the problem, but I couldn't help myself. Sorry @Centril. I wanted to be sure I understood it. I'll do the solutions in the next comment.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Jul 11, 2019

We explored three possible solutions.

The most obvious is to "give up on coherence". Actually we didn't go into this in depth; @arielb1 felt that it cannot be made sound, and I'm inclined to agree. I think this Zulip chat contains more details.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Jul 11, 2019

The next solution was modifying the rules around object safety such that the trait Object is not considered "object safe". The idea would be roughly that a trait is not "object safe" if there is some impl that could apply to the object. This was somewhat inspired by #50781 -- which is a rather different, but also concerning, soundness hole around object types. (And one I have to revisit after writing these to see if we can somehow solve it in a similar way.)

In truth, we didn't dig too hard into this option. It would be "backwards incompatible" in a somewhat serious way, in that if someone has traits like

trait Foo { 
    fn method(&self) { }
}
impl<T: ?Sized> Foo for T { 
}

today, the Foo is "object safe" and hence one can have dyn Foo without a problem. (If you invoke method on a dyn Foo, I believe it will dispatch through the vtable, because we'll see it at monomorphization time, but I'm not 100% sure.)

This would be a bit of a departure in the sense that none of the other object safety rules have to do with the set of impls. That said, I believe that @mikeyhew did a lot of refactoring as part of the custom self-type work to make that possible, so it could work out.

Still, it has some "strangeness" to it -- for example, it requires creating a dyn Foo type so that we can test whether any impl applies to it -- but such a type is only well-formed if there is no such impl. (As noted in the next comment, we could probably do this check in a more syntactic way, actually.)

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Jul 11, 2019

The final solution we considered was to suppress the "auto-generation" of the dyn Foo: Foo impl if there exists some user-given impl that might apply to dyn Foo. The idea then is that Foo is object-safe but if you supply an overlapping impl, that's the impl we're going to use.

This has some interesting potential to offer. It might serve as a replacement for the where Self: Sized hack that we use in types like Iterator to permit a trait to be object-safe while still employing lots of complex methods. I'll look at that in the next comment.

My first thought was that we might model this (in chalk terms) by first constructing a program environment for the trait which does not involve the automatic rule. This could be done but feels like a bit of a pain. In particular, solving those impls might require lowering other traits, and we'd have to test those traits to see if they are object safe and hence get an automatic rule, which seems to require a kind of DAG between traits. Uncool.

In practice, however, the impl in question must be be implemented for some type parameter T where T: ?Sized. I don't think there would be any other way to match a dyn Foo object type (at least, not without being generic over "trait bounds" or some such thing). So we might be able to do a simpler, more syntactic check?

The same seems to apply to option two.

@nikomatsakis

This comment has been minimized.

Copy link
Contributor

commented Jul 12, 2019

One final note:

We discussed, somewhat speculatively, the idea that if we took the third option, where users can write their own impl of a trait for dyn Trait, that it might enable an alternative to the where Self: Sized hack. The idea would be that if you have a trait that contains non-object-safe methods, you can define it yourself for the dyn type. This would be a non-trivial bit of design though and it's not necessarily a big win -- it's roughly the approach we opted against in creating object safe in the first place, though with the (nice!) advantage that the compiler will automatically create the dyn Foo impl when it is easy to do so.

The basic idea would be that you can always create a dyn Foo type for any trait, but you can't actually invoke non-object-safe methods through that type. This changes the MIR definition because, for now, MIR knows nothing about virtual dispatch -- that is effectively encapsulated into a "magic impl" that the compiler generates. But in this model, the MIR would have to be extended with some notion of a virtual call, such that when one invokes obj.foo() on some variable obj: dyn Foo, that is not (from MIR's perspective) invoking Foo::foo but rather a virtual call. This lets you write the impl itself that bottoms out in virtual method dispatch.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.