Transitive automatic marker trait implementation yields confusing compile error


#1

Background

I’m writing an OpenGL abstraction that makes it hard to write wrong applications, meaning I’m using the type system to only allow calling certain functions when the OpenGL context is in the right state. For example, OpenGL allows you to upload image data (usually rgba values) to a texture. You first have to generate a texture id, bind the texture id to a texture target and then upload the image data to the texture target. There are different versions of the upload function: glTexImage1D, glTexImage2D, etc. These upload functions only make sense when you’ve bound a texture id to the right texture target. Thus I want to only implement the 2d image upload function on an object that represents a texture bound to a 2d capable texture target. There are other functions as well that require a different grouping of the texture targets. Now that the motivation is somewhat clear it is time for an example.

Working example

The example implements traits to describe inclusion in the groups 1D, 2D, 1D+ and 2D+ which are related as described by this venn diagram.

venn

https://play.rust-lang.org/?gist=395a4e6f3252270ab154deb33c8734e8&version=nightly

// base trait.
trait G {
    fn name(&self) -> &'static str;
}

// 1D and 2D marker traits. If you are ND, you must also be ND+.
trait G1D: G1DP {}
trait G2D: G2DP {}

// 1D+ and 2D+ marker traits. If you are ND+, you must also be (N - 1)D+.
trait G1DP: G {}
trait G2DP: G1DP {}

struct A;
struct B;

impl G for A {
    fn name(&self) -> &'static str {
        "a"
    }
}

impl G for B {
    fn name(&self) -> &'static str {
        "b"
    }
}

// If you are ND+, you must also be (N - 1)D+.
// impl<T: G2DP> G1DP for T {}

// If you are ND, you must also be ND+.
// impl<T: G1D> G1DP for T {}
// impl<T: G2D> G2DP for T {}

// Mark A as 1D (and thus also 1D+).
impl G1D for A {}
impl G1DP for A {}

// Mark B as 2D (and thus also 2D+ and 1D+).
impl G2D for B {}
impl G2DP for B {}
impl G1DP for B {}

// Wrapper struct to provide implementations for different groups.
struct W<T: G>(T);

impl<T: G1D> W<T> {
    fn do_1d_thing(&self) {
        println!(
            "Doing something to {} that can only be done to 1 dimensional objects.",
            self.0.name()
        );
    }
}

impl<T: G1DP> W<T> {
    fn do_1d_plus_thing(&self) {
        println!(
            "Doing something to {} that can only be done to 1 or more dimensional objects.",
            self.0.name()
        );
    }
}

impl<T: G2D> W<T> {
    fn do_2d_thing(&self) {
        println!(
            "Doing something to {} that can only be done to 2 dimensional objects.",
            self.0.name()
        );
    }
}

impl<T: G2DP> W<T> {
    fn do_2d_plus_thing(&self) {
        println!(
            "Doing something to {} that can only be done to 2 or more dimensional objects.",
            self.0.name()
        );
    }
}

fn main() {
    let a = W(A);
    let b = W(B);

    a.do_1d_thing();
    a.do_1d_plus_thing();
    // a.do_2d_thing(); // NOT IMPLEMENTED
    // a.do_2d_plus_thing(); // NOT IMPLEMENTED

    // b.do_1d_thing(); // NOT IMPLEMENTED
    b.do_1d_plus_thing();
    b.do_2d_thing();
    b.do_2d_plus_thing();
}

Automatically implementing traits

We should be able to automatically implement certain traits because the relations between the groups are well defined. Lets make sure all implementors of 2D+ automatically implement 1D+ as well since 2D+ implies 1D+ (it is even a requirement on the G2DP trait).

// If you are ND+, you must also be (N - 1)D+.
impl<T: G2DP> G1DP for T {}

// ...

// Can now remove this line.
// impl G1DP for B {}

So far so good. We should also be able to implement the relation ND implies ND+. Lets start with N = 2 case.

// If you are 2D, you must also be 2D+.
impl<T: G2D> G2DP for T {}

// ...

// Can now remove this line.
// impl G2DP for B {}

Still good. If we add the rule for N = 1, the compiler starts complaining.

// If you are ND+, you must also be (N - 1)D+.
impl<T: G2DP> G1DP for T {}

// If you are ND, you must also be ND+.
impl<T: G1D> G1DP for T {}
impl<T: G2D> G2DP for T {}

// Mark A as 1D (and thus also 1D+).
impl G1D for A {}
// impl G1DP for A {} // SHOULD NOW BE DERIVED

// Mark B as 2D (and thus also 2D+ and 1D+).
impl G2D for B {}
// impl G2DP for B {} // SHOULD NOW BE DERIVED
// impl G1DP for B {} // SHOULD NOW BE DERIVED

Doesn’t compile and throws:

error[E0119]: conflicting implementations of trait `G1DP`:
  --> /home/mick/projects/opengl-rust/src/what2.rs:33:1
   |
30 | impl<T: G2DP> G1DP for T {}
   | ------------------------ first implementation here
...
33 | impl<T: G1D> G1DP for T {}
   | ^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation

When we uncomment the ND+ implies (N - 1)D+ rule,

// impl<T: G2DP> G1DP for T {}

the compiler spits out the following message:

error[E0277]: the trait bound `B: G1D` is not satisfied
  --> /home/mick/projects/opengl-rust/src/what2.rs:41:6
   |
41 | impl G2D for B {}
   |      ^^^ the trait `G1D` is not implemented for `B`
   |
   = note: required because of the requirements on the impl of `G1DP` for `B`

which confuses me because B should not implement G1D at all! The chain should be G2D -> G2DP -> G1DP -> G.

What is going on?


#2

A Trait implementation can be written for any structure (limited only by pub modular access), you can’t make mutually exclusive traits.
So a structure could be written that then implements both G2DP and G1D. The compiler then has no way of knowing which impl for G1DP to use.

edit: reversed text so traits come after creating structure.


#3

I’d expect and want an error but only when you actually try to implement two traits that cannot be combined such as G2DP and G1D. Perhaps there is an implementation detail of the compiler that causes this but do you agree that we should be able to write code like this?


#4

Rust chose to verify for potential overlap (aka coherence) upfront, so to speak. https://github.com/rust-lang/rfcs/blob/master/text/1023-rebalancing-coherence.md has more details on how coherence works.


#5

Maybe @sgrif (if he sees this post) can shed some wisdom/suggestions on navigating coherence safely - diesel is very heavy on stuff like this.


#6

It’s not possible to express mutually exclusive traits in the language today.


#7

Thanks @vitalyd, @sgrif. I can see why after reading the rebalancing coherence RFC. A more informative compiler error would be useful.