Tracking issue for allowing overlapping implementations for marker trait

[nikomatsakis]

Tracking issue for rust-lang/rfcs#1268.

Status

• Initial implementation: Implement RFC 1268 "Allow overlapping implementations for marker traits" #41309
• Documentation
• Move to stabilize
• Stabilization PR

Known bugs

• cross-crate support lacking?
• broken interaction between marker traits, lifetimes, and caching #102360

History

• initial implementation Implement RFC 1268 "Allow overlapping implementations for marker traits" #41309
• Support an explicit annotation for marker traits #53693

Prior to stabilization

1. Is it ok that adding items to a previously empty trait is a breaking change? Should we make declaring something a marker trait more explicit somehow? --> resolved by adding explicit #[marker] annotation, see Support an explicit annotation for marker traits #53693

Other notes

In #96766 we decided NOT to disable the orphan check for marker traits as part of this work (just the overlap check), which was a proposed extension.

[nikomatsakis]

With respect to the second question of whether we should make a more explicit notion of marker trait, I have been pondering this since the RFC discussion. On the one hand, there are a number of places in Rust today where going from nothing to something is a breaking change: adding a private field to a struct, for example.

The difference here I think is that:

1. Given the ability to specify defaults, adding an item to a trait does not necessarily have to be a breaking change otherwise (though methods and fns can cause new ambiguities etc).
2. If there are impls that are taking advantage of the ability to overlap, there may just be no way to port older code forward, because it would require overlap.

However, the second point depends a lot on the fate of specialization. If we wind up adopting specialization, and in particular a model that does not require strict subsets, then it would still be possible to adapt existing impls. This makes me a lot less worried. Of course, implementing that form of specialization is tricky, but not (I don't think...) that much trickier than implementing THIS suggestion. The hard part in both cases is the potential for overlap.

[sgrif]

@nrc This has the RFC implemented label, but I don't think it has been. If it has, is there a feature gate that I'm missing? If it hasn't been implemented, is there anything I can do to help push this along? It's now been a year since the RFC was accepted.

[nikomatsakis]

@sgrif swapped labels

[nikomatsakis]

@scottmcm did you have a specific reason to nominate this? :)

[nikomatsakis]

cc @rust-lang/wg-traits -- I seem to recall some concerns about the implementation potentially being unsound? Does anyone remember what I'm talking about?

[nikomatsakis]

We discussed this in our @rust-lang/lang meeting today. One thing we were wondering about are the active use cases and stakeholders -- seems like @rust-lang/wg-safe-transmute was one potential consumer, did the current design meet the needs there?

[scottmcm]

Likely none of the existing auto traits can be made #[marker], but certainly not Unpin.

Can you elaborate on this one, @RalfJung? I would have guessed that Copy could be #[marker], for example. (Albeit I'm not sure how useful that one would be, given the extra magic requirements that exist on Copy.)

[RalfJung]

For Unpin we have a concrete example where making it #[marker] would introduce soundness issues in a crate (#29864 (comment), taiki-e/pin-project#18).

I assume the same could happen, in principle, for any of the other existing marker traits, though I am not aware of concrete examples.

[lcnr]

cc @rust-lang/wg-traits -- I seem to recall some concerns about the implementation potentially being unsound? Does anyone remember what I'm talking about?

I think the issue was #88139. The implementation now results in weird ambiguities, but at least it isn't unsound anymore afaik

For Unpin we have a concrete example where making it #[marker] would introduce soundness issues in a crate (#29864 (comment), taiki-e/pin-project#18).

Afaict the issue here is about impls for marker traits violating the orphan rules, which is generally unsound to my knowledge and not permitted by the current implementation. It might actually be possible to change all auto traits to marker traits again, only requiring opt-in for non-auto traits, as for those, adding an item to the trait definition would otherwise be a breaking change.

edit: nm, the idea is for a macro to add impl<T: NotImplemented> Unpin for NotUnpin<T> to prevent the type from implementing Unpin. This would not work anymore if Unpin was a marker trait. While I don't necessarily think that this pattern is the best solution and am hoping for the stabilization of negative impls for this instead, it is definitely a reason to keep marker traits as opt in.

[RalfJung]

Afaict the issue here is about impls for marker traits violating the orphan rules, which is generally unsound to my knowledge and not permitted by the current implementation.

The entire point of the feature in this tracking issue is to allow violating the orphan rules by permitting overlapping implementations -- or am I misunderstanding?

[lcnr]

it allows overlapping impls in the same crate, allowing it across crates is unsound without restricting the way marker traits can be used.

consider a crate like this:

#![feature(marker_trait_attr)]
#[marker]
pub trait Marker {}

pub struct B;

trait NotMarker {
    type Assoc;
}

impl NotMarker for B {
    type Assoc = usize;
}

impl<T: Marker> NotMarker for T {
    type Assoc = Box<String>;
}

if a different crate were to add an impl leading to B: Marker, we have an ambiguous associated type

[RalfJung]

Oh, because rustc actually uses negative reasoning inside a crate, so not all 'monotone' extensions of the impl set are actually allowed... that's nasty.

[nikomatsakis]

I have an action item to leave a comment here but I can't find the notes. In any case, my vague recollection is that:

Despite marker traits permitting one to stretch the coherence rules, they are specifically targeting the overlap rules and not the orphan rules (i.e., they don't let you write impls in crates that you wouldn't have been permitted to write an impl in). If we ensure that marker traits follow the same orphan rules as everyone else, I don't think they pose any particular problem for the negative reasoning that we do elsewhere.

There was also a (related) interaction between marker traits and negative impls that was discussed here. In short, the problem was that if we lifted the orphan rules for marker traits, then one could add an explicit !Marker impl in a crate and an Marker impl in another crate. As I noted then, the way I think about it is that, after a trait is published, only one crate ever has the right to add any particular impl (positive or negative). Specifically, if an impl applies to a type X, only the crate in which X is declared has the right to add that impl. This fits with the fact that adding blanket impls (which could apply to such types) is a semver-breaking change after a trait is released. This same idea applies to negative impls too: you can only add a negative impl if you would've been the one to add the positive impl.

The case that @RalfJung is talking about seems to be the same, but the "negative reasoning" in question is implicit due to the fact that everything is within the same crate.

[SamPruden]

One use for this which I'm particularly excited about but haven't seen explicitly mentioned is that it allows things like this:

#[marker]
trait TupleHas<T> {}

impl<T1> TupleHas<T1> for (T1, ) {}
impl<T1, T2> TupleHas<T1> for (T1, T2) {}
impl<T1, T2> TupleHas<T2> for (T1, T2) {}
impl<T1, T2, T3> TupleHas<T1> for (T1, T2, T3) {}
impl<T1, T2, T3> TupleHas<T2> for (T1, T2, T3) {}
impl<T1, T2, T3> TupleHas<T3> for (T1, T2, T3) {}
// ...

A use case for this would be Bevy's queries, which look like this.

fn score_system(mut query: Query<(&Player, &mut Score)>) {
    // Type safe access to components
    for (player, mut score) in query.iter_mut() {
        // Some score updating logic here
    }

    // However, we can also do this:
    let player: &Player = query.get_component(some_specific_entity);
    // We're only allowed to call get_component with one of the types in the Query.
    // (Player or Score in this case). 
    // Currently, this is only enforced with a runtime error.
    // A QueryHasReadAccess<T> marker trait could allow this to be a type error instead. 
}

I'd love to see this stabilized!

[scottmcm]

@SamPruden I'd also like to see this stabilize.

It looks like there's at least one open issue that probably blocks it, though: F-marker_trait_attr `#![feature(marker_trait_attr)]`

[SludgePhD]

I'm currently writing a linear algebra library that would really benefit from this feature as well, so I'd love to see this move forward.

My usecases, in case they're insightful:

The first is VectorLike, a trait implemented when one dimension of a matrix is statically known to be 1. This allows interpreting the matrix like a (row or column) vector and allows using some methods and operators where it would otherwise be ambiguous whether they operate in column-major or row-major order (.iter(), indexing with a scalar, etc.).

#[marker]
trait VectorLike {}
impl<D> VectorLike for (Const<1>, D) {}
impl<D> VectorLike for (D, Const<1>) {}

The second is DimEq, a trait implemented when two matrix dimensions are potentially equal at runtime. This is useful in the presence of runtime-dynamic matrix dimensions, indicated by the Dyn type – those require a runtime check in addition to the DimEq bound.

#[marker]
trait DimEq {}
impl<const D: usize> DimEq for (Const<D>, Const<D>) {} // guaranteed to be equal
impl<const D: usize> DimEq for (Dyn, Const<D>) {}  // *can* be equal (ensured by runtime assertion)
impl DimEq for (Dyn, Dyn) {}  // *can* be equal (ensured by runtime assertion)
impl<T, U> DimEq for (T, U) where (U, T): DimEq {} // order shouldn't matter when using this
// (important in generic code calling other generic code, otherwise they have to require both or agree on order)

// Notably, this isn't implemented for `(Const<A>, Const<B>)` when A and B are different.
// catches mistakes at compiletime instead of runtime when possible!

[Kolsky]

@SludgePhD I wonder if your logic for

impl<T, U> DimEq for (T, U) where (U, T): DimEq {}

is right. Notably, it overflows the current typechecker, and the next trait solver intends to resolves cycles with a "yes" answer by separating is-impl and has-impl. It would work as if you've additionaly written

impl<T> DimEq for (T, T) where (T, T): DimEq {} // has impl, so is impl; in other words, always holds.

[nikomatsakis]

I'm nominating this to @rust-lang/lang and @rust-lang/types ---

I'd like to get a temperature check on this feature. Quick summary is that it lets you put #[marker] on a trait and then permit overlap.

From lang, I'm curious as to whether folks still think this is desirable. (I do, though I'm potentially open to bike-shedding on the details -- but this precise scenario comes up all the time.)

From types, I'm curious as to whether folks are aware of impl problems, how this fits with the new solver, etc. Seems like a great candidate to target with a-mir-formality and spec work for testing out a new process.

@rustbot labels +I-lang-nominated +I-types-nominated