search

rust-lang / rfcs

RFCs for changes to Rust
https://rust-lang.github.io/rfcs/
Apache License 2.0
5.78k stars 1.55k forks source link

Scoped `impl Trait for Type` #3634

Open Tamschi opened 1 month ago

Tamschi commented 1 month ago

This may be a bit long. I thought it would be best to go over the interactions with other language features and tooling as well as potential impacts thoroughly in advance, since while the addition to the language itself can be explained quickly, it does interact with a lot of other Rust features and aspects of the crate ecosystem.

In (very) short this is a version of orphan-rule avoidance (i.e. non-unique trait implementations) that does not suffer from either version of "the hashtable problem", does not obscure imports, can be safely ignored unless needed (but is discoverable), is seamlessly compatible with specialisation and tries to strike a good balance between usability and complexity, so that developers are automatically funneled towards correct and unsurprising but also highly compatible code.

I'm aware that there are often rash proposals in this direction, but I believe I've covered all previously-discussed issues. As the overall RFC is a fairly dense read, I've added cross-references and less-formal comments in form of blockquotes to it.

Thanks

Rendered

Tamschi commented 1 month ago

I wasn't sure what to use as "Start Date", so I used today's date.

The main question here is probably whether the feature is easy enough to understand and work with for developers. As far as possible, I tried to do this by not adding any original algorithms and by making sure that the most simple/concise implementation is most likely the ideal one in each situation, or at least can always be refactored without breaing changes, but especially the split between implementation-aware and implementation-invariant generics not quite along which ones are built-ins with special syntax adds a bit of complexity for better ergonomics.

Some of the changes are modular, for example the syntax for using a scoped implementation directly, without bringing it into scope, could be added separately from that for importing it into and later reexporting it from another scope, and referring to global implementations in place of scoped ones could be another separate addition, but anything related to type identity would have to be implemented first in order for the feature to be backwards-compatible and not require an edition change.

Tamschi commented 1 month ago

This RFC covers the use-cases of the following postponed and draft RFCs:

It would likely help with the following RFC by providing a mechanism for access control:

Tamschi commented 1 month ago

(In fairness I should say that a few of those 🚀 reactions on the OP are from friends who have been following along a bit and seem excited about this. I did not ask them to add those, didn't even give them a link directly to this PR.)

kvverti commented 1 month ago

I think the consequences for type identity should be discussed more.

burdges commented 1 month ago

I'd think scoped traits wind up unsound..

crate x

pub trait SomeTrait { .. }

put unsafe trait SomeTraitConforms : SomeTrait { }

pub fn bar<T: SomeTrait>(..) {
}

pub fn baz<T: SomeTraitConforms>(..) {
    unsafe { .. }
}

crate y

pub struct Foo { .. }
impl SomeTrait for Foo { .. }
impl SomeTraitConforms for Foo { .. }

crate z

use impl SomeTrait for Foo { .. }

// This must use the local SomeTrait 
bar::<Foo>(..)

// This must use the remote SomeTrait, because obviously the local is unsound here.
baz::<Foo>(..)

// Yet, baz could assume that bar invocations used the same SomeTrait, thereby creating unsoundness.

I've not yet explored solutions, but maybe traits should opt into this using an attribute like #[unsafe_forbit_unsafe_subtraits], but Rust has many marker traits which get used as supertraits, so then many traits cannot have local definitions. Also, we've no idea if that's a compelte fix, so really soundness should be formally proven here, ala the rustbelt work.

Tamschi commented 1 month ago

I'd think scoped traits wind up unsound..

[…]

This code wouldn't compile under this RFC. Subtrait impls are shadowed along with any supertrait impls they require, and can only be imported into scopes where all their matching supertrait impls are also present.

burdges commented 1 month ago

Alright fair enough, but SomeTraitConforms need not be a subtrait of SomeTrait, so then pub fn baz<T: SomeTrait+SomeTraitConforms>(..) creates problems.

Also, you could disable seemingly unrelated impls unexpectedly, right? You cannot roll back to an un-specialized impl just because the specilized one depends upon some unsafe subtrait, so presumably some expected generic impls disapear when doing this. That's not necessarily a problem, just surprising.

lcnr commented 1 month ago

I am reaching out here as a member of the Types Team, even if I do not speak for the team as a whole. It is obvious that a lot of work went into this RFC and the design. From what I can tell by looking over it, you've been very thorough and it looks like you've spent a significant effort to make sure learn and apply existing terminology and concepts. This makes it even more disheartening to shut this down without providing any technical feedback.

I expect this RFC to end up getting stale without ever receiving feedback or reasoning from T-lang or T-types, regardless of whether the proposed changes are desirable as described.

This is a very big change to the core type system and we do not currently have to capacity to appropriately review and implement this. From a quick skim, I can tell that it allows some sort of specializing impls (which I expect to require some sort of "always applicable impls" https://github.com/rust-lang/rust/issues/48538), it adds an additional concept similar to variance, and impacts TypeId depending on location in the source. While none if these additions are necessarily unsound, they require a significant amount of care and a proper understanding of the underlying interactions. This holds not only for the author, but also for the team members approving this change.

While we don't officially communicate this anywhere from what I can tell[^1], such big changes should already have the affected teams in the loop far before you've fleshed it out this much. Both the language and the types team have the MCP process (similar to https://github.com/rust-lang/rfcs/pull/2904) and the more or less official concept of a 'liason': someone from the team who is involved in the design and acts as an advisor and a bridge to the rest of the team. This should also catch cases where a proposed solution is not feasible due to a lack of capacity without first requiring the contributor to spend dozens of hours on it.

I do not have any useful recommendations for what you should do here. While you can definitely reach of on the relevant zulip streams (types lang) to get a team member to liason for this work and to try and push this forward, I don't expect that there is a types team member with the necessary capacity. It may be possible to split it in multiple smaller proposals and make progress on these, though I would also only recommend that once you have a team member on board.

I am very sorry that you ended up at this point without getting such feedback earlier. If there's anything you want to respond here or talk about, feel free to do so here or on zulip, either via pm or in a public stream.

[^1]: which is incredibly bad and something we have to change. I made a note to formalize our suggested workflows when proposing changes affecting the types team

Tamschi commented 1 month ago

That's totally fine! Well, maybe not entirely in the general sense, but to be honest I somewhat expected that to be the case. (I think I would have written this up anyway. It has been an interesting exercise in many ways and it's something I wanted to be "out there". I'm sorry if this is causing any work for you, though.)

I'm going to reach out and see if anyone would be interested in reading this, even if it's just out of personal curiosity and without commitment to a thorough review or anything like that. It's very difficult for me to get feedback on this otherwise, so I'd be grateful about anything, really. Also to anyone on this issue who'd still entertain me without expectation that this RFC ends up making a difference, of course. (It's painfully obvious from my writing style, but just to be clear, I'm not part of academia and don't have the means of submitting this for review anywhere.)

You're mistaken about one thing though: I didn't put much specific effort into the research for this. Terminology and concepts happen to be something I pick up passively for the most part, and I do enough systems programming (as a hobby) that I'd ran into most of them beforehand already. The main avoidable difficulty was that I didn't come across much of the earlier discussion and with that prior art until I was far along with the concept, so I ended up re-deriving most of it with stable Rust as a base.

Thanks for the considerate response and pointers!

Tamschi commented 1 month ago

Alright fair enough, but SomeTraitConforms need not be a subtrait of SomeTrait, so then pub fn baz<T: SomeTrait+SomeTraitConforms>(..) creates problems.

That's true. I don't expect this to be a problem for standard library traits (the Trusted… traits are subtraits of those they describe and as far as I can tell right now it's not an issue for existing supertraits beyond what's already clearly unsound), but a rule against the linking of (including indirectly as supertrait) an unsafe trait and an unrelated scoped implementation like that is necessary at least for existing unsafe traits.

This would also affect cases where the type with attached scoped implementation appears as type parameter or associated type in the unsafe trait. This would have to be measured, but it could turn out to be a relatively small amount of friction.

It would be possible to add an #[asserts_at_most_supertrait_implementations] attribute to be applied on the unsafe trait's declaration to allow such combinations, and/or make that the default in an edition change and add an attribute to opt-out of the requirement.

Also, you could disable seemingly unrelated impls unexpectedly, right? You cannot roll back to an un-specialized impl just because the specilized one depends upon some unsafe subtrait, so presumably some expected generic impls disapear when doing this. That's not necessarily a problem, just surprising.

(I'm not entirely sure I understand you correctly, so some of this may be irrelevant.)

Blanket-impls aren't automatically shadowed if some of their bounds can't be fulfilled in a scope, so impls where the trait itself isn't dependent won't disappear automatically. To my knowledge, specialisations can't have different supertraits from any other implementation of that trait, so nothing would become "de-specialised" directly.

A global blanket impl that becomes reapplied could unexpectedly shadow a more specific implementation with the current proposal though, for example impl<T> Trait for T where T: Other { … } would shadow impl Trait for Type { … } in scopes with use impl Other for Type { … }.

(This RFC doesn't allow any mixing of overlapping implementations at all by itself, except through strict lexical shadowing and pointing out how it would interact with existing overlaps from specialisation-proper. That's part of why I don't think it necessarily requires "always applicable impls". The other part is that generic code also can't mis-recognise a specific type with accessible caller-side scoped implementation to instead have the global implementation, due to the distinct TypeId that such a bounds-relevant capture causes in generic code. cc @lcnr)

burdges commented 1 month ago

As an aside, it's plausible a soundness proof for some flavor of this winds up being an interesting paper for some academics.

Tamschi commented 1 month ago

As an aside, it's plausible a soundness proof for some flavor of this winds up being an interesting paper for some academics.

Maybe! I don't think I have the mathematical toolkit to do that rigorously, but it does seem like a cleanly defined problem.

Though, a few of Rust's implicit properties that cause issues here, like 'unsafe impl Trait can guarantee unrelated impl Traits generically', are "grown" and not inherent to a bounds-on-impls programming language with scoped implementations, and also not necessarily useful, so I don't think such a programming language/paper should allow that if it has the choice.

Fortunately that particular one seems to be self-contained enough that a few extra rules can patch it up. (I'm intermittently very busy, so it could take a little while for me to make changes here and will likely happen in bursts.)

nikomatsakis commented 1 month ago

One other suggestion: the (experimental) project goals process is meant to be a good framework for ambitious projects like this one. You could try authoring a project goal (see rust-lang/rust-project-goals) though to be frank I don't think it would make it onto this first slate of goals. But the exercise may be valuable and I do hope that going forward this eoll.be a mechanism for proposing ambitious changes.

On Sun, May 19, 2024, at 11:06 AM, Tamme Schichler wrote:

As an aside, it's plausible a soundness proof for some flavor of this winds up being an interesting paper for some academics.

Maybe! I don't think I have the mathematical toolkit to do that rigorously, but it does seem like a cleanly defined problem.

Though, a few of Rust's implicit properties that cause issues here, like 'unsafe impl Trait can guarantee unrelated impl Traits generically', are "grown" and not inherent to a bounds-on-impls programming language with scoped implementations, and also not necessarily useful, so I don't think such a programming language/paper should allow that if it has the choice.

Fortunately that particular one seems to be self-contained enough that a few extra rules can patch it up. (I'm intermittently very busy, so it could take a little while for me to make changes here and will likely happen in bursts.)

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/rfcs/pull/3634#issuecomment-2119268549, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABF4ZXSHMDHKFXV6V5H6VDZDC5VRAVCNFSM6AAAAABHS2XNF2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCMJZGI3DQNJUHE. You are receiving this because you are subscribed to this thread.Message ID: @.***>

Tamschi commented 1 month ago

I'll fix the direct issues with the RFC that came up here before doing so, but thanks, I'll look into it. (There isn't really a lot that is arbitrary, aside from syntax specifics, so I'd like to make sure the idea is plausible as presented then.)

Tamschi commented 1 month ago

Alright fair enough, but SomeTraitConforms need not be a subtrait of SomeTrait, so then pub fn baz<T: SomeTrait+SomeTraitConforms>(..) creates problems.

Fixed in 360a5944bd9d1d5732c5d794e282f51955879d8f (Forbidden implementation combinations, permalink).

This could cause some friction since the restriction wouldn't be desirable if this feature was drawn up in a vacuum, but hopefully nothing all too serious. It's also something that could potentially eventually be cleaned up for future unsafe traits in an edition change.

Ygg01 commented 1 month ago

I don't think it would make it onto this first slate of goals. But the exercise may be valuable and I do hope that going forward this eoll.be a mechanism for proposing ambitious changes.

Isn't the goal of this RFC in line with https://rust-lang.github.io/rust-project-goals/2024h2/Relaxing-the-Orphan-Rule.html

I.e. it solves by being explicit.

oskgo commented 1 month ago

I don't think it would make it onto this first slate of goals. But the exercise may be valuable and I do hope that going forward this eoll.be a mechanism for proposing ambitious changes.

Isn't the goal of this RFC in line with https://rust-lang.github.io/rust-project-goals/2024h2/Relaxing-the-Orphan-Rule.html

I.e. it solves by being explicit.

Not exactly. The project goal suggests ensuring different trait implementations are consistent with each other by using macros to implement them. This dodges the issue with trait implementations being inconsistent across different scopes that this RFC has. Currently code (including unsafe code) may rely on trait implementations of the same type to be the same everywhere. This RFC tries to address this but I think fails to succeed and I think this is very difficult to solve without using glorified newtypes. Consider the following example, which I believe is sound in current Rust:

struct Foo;
trait Tr1 {
    const ID1: u32;
}
impl Tr1 for Foo {
    const ID1: u32 = 0;
}
trait Tr2: Sealed {
    const ID2: u32;
}
impl Tr2 for Foo {
    const ID2: u32 = 0;
}
fn explode<T: Tr2 + Tr1>() {
    if T::ID1 != T::ID2 {
        unsafe {core::hint::unreachable_unchecked()}
    }
}

It's also sound if Foo and Tr1 are external and ID1 is stably guaranteed. Variants of this which rely on other stably guaranteed properties than values of constants can also be made. Calling explode<Foo> in a scope where Tr1 is implemented differently for Foo leads to UB.

Even so there might still be room for this RFC (assuming it can be made sound without rendering it useless). In some cases you might want a trait to be implemented differently in some places than it would otherwise be, such as with specialization. The fact that you can get a weakened form of specialization from this is a big indication of its complexity though.

Tamschi commented 4 weeks ago

Patched up now in 4d746692f16d69a981bce7570822d6fa6dd690e0, along with cases where the bounds are attached to a concrete type… though that's not enough yet, because even if the trait isn't sealed, implementations on concrete types effectively are. I'll revise it again in a moment.

(Beyond unsafe traits and (effectively) sealed bounds, are there any other patterns that can restrict a public bound to a known subset of implementations?)

Seconding what @oskgo wrote, Relaxing the Orphan Rule is definitely less complicated. I also think that the "standalone derive" mechanism suggested there would be very helpful, doubly-so if it could eventually also create scoped implementations. In my eyes this would require a fully hygienic alternative to the current proc-macro-based derives to have good usability, though.

Tamschi commented 4 weeks ago

That's definitely not pretty, even if the cases it forbids should be relatively rare for the most part.

(I guess indirecting the bound like that could be one very hacky form of access control? Though where this occurs most is most likely just From vs. Into and for operator use and such.)

Tamschi commented 4 weeks ago

…right nevermind, there's more.

can check the TypeId of T and then assume U: ExternalScoped to be a specific global implementation.

oskgo commented 4 weeks ago

It's not enough to handle traits that are explicitly sealed. What about the following case:

mod M1 {
  pub struct Foo;
  pub trait Tr1 {
    const ID1: u32;
  }
  impl Tr1 for Foo {
    const ID1: u32 = 0;
  }
}
pub struct Proof<T: ?Sized>{
  _ph: core::marker::PhantomData<T>
}
pub trait Tr2 {
  fn prove() -> Proof<Self>;
  const ID2: u32;
}
impl Tr2 for M1::Foo {
    fn prove() -> Proof<Self> {Proof{_ph: core::marker::PhantomData}}
    const ID2: u32 = 0;
}
pub fn explode<T: Tr2 + M1::Tr1>() {
  T::prove();
  if T::ID1 != T::ID2 {
    unsafe {core::hint::unreachable_unchecked()}
  }
}

Many variations of this can be made. The only essential part is that it should be impossible to construct an instance of Proof<T> unless T implements Tr1 correctly. Here we do so by exporting no constructors, but we could also do it by only providing constructors that panic unconditionally, check that the trait is implemented correctly (this is possible for example with associated constants and const functions or methods) or are unsafe.

The list of forbidden implementation combinations is starting to look quite complex now. To avoid errors I think that an explanation for why these are necessary, and more importantly why they are sufficient should be present somewhere. Personally I have no idea what an explanation for why the list is sufficient would even look like though.

EDIT: Also, I'm not sure how this RFC interacts with future changes to the language that might expand on the situations where we can observe or rely on the consistency of trait implementations across different scopes. How would this RFC constrain future language design?

Tamschi commented 3 weeks ago

Your example isn't unsound under this RFC with the latest corrections. It falls under the <T: Sealed + ExternalScoped> rule, so only the crate that defines explode can define a scoped implementation use impl Tr2 for … { … } that can be used to call this function. Maybe I can expand the explanation some more when I have time to work on it again, though.

As for implementation consistency: Outside of these combinations with a separate proof type, the inconsistency isn't observable. The effects on the runtime type identity of generic type parameters ensure that generic code safely perceives the types as distinct. In some cases this can lead to an unexpected mismatch, but shouldn't in any way that causes unsoundness with current crates[^1].

[^1]: There's a specific pattern of static or transient type-erased collection where a generic type-identified token can be used to signify presence of an entry that could then be transmuted with unsafe under the transmutation permission here that could then be used on the collection to erroneously assume there is an entry, i.e. calling code obtaining GuaranteedKey<Type>, transmute-ing it into GuaranteedKey<Type as Debug in my_debug> (non-generically only, as in generic code this would require a type key lookup to be sound, which would appear distinct for this use), then indexing the collection. I didn't find any examples of crates that have an API that would permit having this problem, though neither could I find examples of type-erased non-type-keyed collections for which this transmutation permission is required for them to remain sound. Personally, I think the latter is more likely to occur, though, so I think it's probably okay to ask the former to add a runtime check if such an implementation actually exists right now.

Tamschi commented 3 weeks ago 
use std::{any::TypeId, collections::HashSet, sync::Mutex};

pub struct Token<T>(PhantomData<T>);

static STORAGE: Mutex<HashSet<TypeId>> = Mutex::default();

pub fn insert<T>() -> Token<T> {
    STORAGE.lock().unwrap().insert(TypeId::of::<T>());
    Token(PhantomData)
}

pub fn frob<T: Frob>(token: &Token<T>) {
    unsafe { STORAGE.lock().unwrap().get(&TypeId::of::<T>()).unwrap_unchecked(); }
}

is the pattern of currently legal code that would become unsound here since the caller can unsafe { frob(mem::transmute::<Token<T>, Token<T as Frob in custom>>(insert())) };.

You can create a non-static version of this by attaching an invariant must-match lifetime to collection and token type, then exposing collection instances only one at a time with a transient lifetime to a callback.

Edit: Would actually be unsound without the transmute, yes. frob(insert::<T as Frob in custom>()) would cause problems there since insert doesn't observe the type identity regarding Frob differences. It is possible to change this, by making generic type parameters' TypeIds always observe the full implementation environment and removing the transmutation permission, but that would badly compromise the usability of type-erased collections passed between code that uses different scoped implementations.

oskgo commented 3 weeks ago

@Tamschi It's not sealed, at least not in the conventional sense. I've changed the example to add pub to things that can be exported. I don't see how one could easily check whether Proof<T> has safe constructors that don't panic if Tr1 is wrongly implemented. I think that hits Rice's theorem. The example can also be extended to Proof<T> that has more than one value, and where there exists at least one that cannot be constructed (in safe code) without the trait being implemented correctly.

Obviously this is extremely contrived, but if you're going to change what code is considered sound then you should provide guidance on which rules unsafe code should follow after the implementation of this RFC, and the new rules should be consistent with existing practice.

People using unsafe Rust are already relying on trait implementations they can observe to stay consistent across different scopes in various ways. That's an implicit assumption in current Rust. It might be possible to allow them to keep this rule by adding enough exceptions to when scoped impls can be made and just making sure that counterexamples are unobservable, but then the language needs to make sure they stay unobservable as it evolves, we need to make sure that all counterexamples (that exist, not just that I can come up with) are dealt with and we need to deal with counterexamples coming from future language changes or block those changes.

Tamschi commented 3 weeks ago

Tr1 is sealed in your example since it's not exported by the crate (thereby triggering the rule when code outside the crate tries to use explode with a scoped implementation for Tr2), or at least to me that's what's commonly understood as "sealed" since there's no formal sealing mechanism on stable and this is afaik the only way to write this without getting a private_bounds warning by default. I should clarify that though.

I don't think the example is all that contrived, the pattern seems quite common. The use with two bounds like this maybe a little less so, but it's still something I'd expect to see around macros sometimes.

oskgo commented 3 weeks ago

Maybe my notation is a bit imprecise here. The idea is that the contents of M1 are defined in one crate while everything else is in another. A third crate would then make a scoped impl of Tr1 without realizing that another of its dependencies (or a dependency of one if its dependents) is relying on the original behavior. I suppose it's not necessary to have such a complex dependency structure. It would work just as well if everything were exported parts of a single crate, but splitting it up like this illustrates that a conservative approach is needed because if we just detect it when it happens we have a semver hazard.

Tamschi commented 3 weeks ago

Oh, I see. In that case, the crate that publishes explode is already unsound under current rules, since any other crate can implement Tr1 and Tr2 arbitrarily for new types. That could be avoided if either of the traits was unsafe and specified those requirements, but then that would trigger the <T: UnsafeGlobal + Scoped> rule.

oskgo commented 3 weeks ago

It's sound under current rules because Tr2::prove being able to produce a Proof<T> without diverging serves as a proof that the Tr1 and Tr2 implementations are consistent with each other.

Proof<T> can serve this role because we restrict the ways it can be constructed.

Ygg01 commented 3 weeks ago

@oskgo

I believe is sound in current Rust:

// crate m1
struct Foo;
trait Tr1 {
    const ID1: u32;
}
impl Tr1 for Foo {
    const ID1: u32 = 0;
}
// crate m2
trait Tr2: Sealed {
    const ID2: u32;
}
impl Tr2 for Foo {
    const ID2: u32 = 0;
}
fn explode<T: Tr2 + Tr1>() {
    if T::ID1 != T::ID2 {
        unsafe {core::hint::unreachable_unchecked()}
    }
}

I don't think this is sound.

A "sound" function is one that maintains the following invariant: any program that only calls sound functions and doesn't contain any other unsafe code, can't commit UB

Source: https://jacko.io/safety_and_soundness.html

Consider following. 

// crate m2
struct Fubar;
impl Tr1 for Fubar{
     const ID1: u32 = 1;
}
impl Tr2 for Fubar{
     const ID1: u32 = 2;
}
fn main() {
    explode::<Fubar>();
}

I just caused UB without any unsafe code. That to me points that explode is unsound.

For explode to be sound it needs to ensure no possible inputs can cause UB. Regardless of implementation details.

oskgo commented 3 weeks ago

@Ygg01 I probably should have defined Sealed. I'll be more explicit in my examples in the future.

In case you don't know about the sealed trait pattern, Sealed is a trait that is not publicly exported and thus can't be mentioned by any external crate. This prevents external crates from implementing Tr2 for their type because they would first need to implement the supertrait Sealed for it, which they can't.

Anyways, that example is outdated since it has been mitigated in the more recent changes to the RFC. It should be easy to check whether a trait is sealed. My newer example is a variant of this that's not so easy to check for.

Ygg01 commented 3 weeks ago

@oskgo

Anyways, that example is outdated since it has been mitigated in the more recent changes to the RFC. It should be easy to check whether a trait is sealed. My newer example is a variant of this that's not so easy to check for.

Ok. I assume you meant the proof one? It doesn't even have the Sealed trait pattern?

It still doesn't enforce its bounds.

pub struct Fubar;
impl Tr1 for Fubar{
    const ID1: u32 = 0;
}
impl Tr2 for Fubar {
    fn prove() -> Proof<Self> {Proof{_ph: core::marker::PhantomData}}
    const ID2: u32 = 1;
}

fn main() {
    explode::<Fubar>(); // UB here, no unsafe, explode is unsound.
}

If you write code that depends on two traits having to have their const/invariants in sync, but anyone can extend them and violate the constraints, to me, it seems that's the problem.

oskgo commented 3 weeks ago

@Ygg01 The _ph field of the Proof struct is private, so your Tr2 implementation wouldn't compile. The only way to construct Proof<T> is through a constructor provided by the crate, which is only Foo::prove(), which will only provide instances of Proof<Foo>, not Proof<Fubar>. Without being able to construct an instance of Proof<Fubar> a valid implementation of Tr2 needs to have a prove that diverges (panics or loops forever), which means we don't even reach the if condition in explode<Fubar>

Tamschi commented 3 weeks ago

The _ph field of the Proof struct is private, so your Tr2 implementation wouldn't compile.

Ahh, now I get it. Sorry, I missed that before. You're right, that does effectively seal the trait and make your example sound.

I also found another case where an assumption can be made:

use std::mem::MaybeUninit;

pub trait Friend {
    fn prepare(&mut self);
}

pub trait HasUnsafe {
    /// #Safety
    ///
    /// May only be called after `<Self as Fried>::prepare(&mut self)` has returned at least once.
    unsafe fn assume(&self);
}

pub struct Type(MaybeUninit<u8>);

impl Type {
    pub fn new() -> Self {
        Self(MaybeUninit::uninit())
    }
}

impl Friend for Type {
    fn prepare(&mut self) {
        self.0.write(0);
    }
}

impl HasUnsafe for Type {
    unsafe fn assume(&self) {
        dbg!(unsafe {
            // SAFETY:
            // According to the safety requirements for this function, `Friend::prepare`
            // has been called on this instance, so `self.0` is initialised (which this
            // function knows because it's in the same crate as or the behaviour is
            // documented on the implementation of `Friend` for `Type`).
            self.0.assume_init();
        });
    }
}

pub fn sound<T: Friend + HasUnsafe>(value: &mut T) {
    value.prepare();
    unsafe {
        // SAFETY: `.prepare` has been called.
        value.assume();
    }
}

With this RFC, sound would become unsound unless <T: ScopedShadowsFriend + GlobalHasUnsafe>¹ is forbidden. This would create new semver hazards though, even if it was broadened to <T: Scoped + GlobalHasUnsafe>¹, as adding an unsafe fn to a trait that didn't have any would be potentially breaking regardless of the default implementation.

¹ and any variation of the link (i.e. as associated type or type argument), in either direction

I just understood that these combination issues are why specialisation requires marking further-specialisable impl-associated items with default. I'll have to think about whether it's possible to use a similar approach here instead of forbidden implementations (which would be more ergonomic for sure since this is getting too complex, as @oskgo pointed out), though of course the issue is that a global implementation often wouldn't exist, and that adjusting an existing trait definition to later allow scoped/alternative impls is (almost?) always an unsound change in a library.

burdges commented 3 weeks ago

As this feels largely academic now, there is a much simpler but still interesting flavor of all this:

mod deimpl Type {  // Hide all implementations of all traits for Type
    impl<..> Trait1<..> for Type<..>;  // Restore the impl of Trait1 for Type
    impl<..> Trait2<..> for Type<..> { ... }  // Provide a new impl of Trait2 for Type
}

Does this solve any problems for which delegation makes solutions hard?

Tamschi commented 3 weeks ago

Unfortunately not, unless the module has knowledge of implementation details of the original impl Trait1 for Type.

mod deimpl Type {  // Hide all implementations of all traits for Type
    unsafe impl<..> Trait1<..> for Type<..>;  // Restore the impl of Trait1 for Type
    impl<..> Trait2<..> for Type<..> { ... }  // Provide a new impl of Trait2 for Type
}

could be sound if it does, if the deimpl also hides all implementations that mention Type as type argument or associated type.

It's possible to achieve the same effect for this RFC by forbidding directly type-linked bounds fulfillment that combines scoped and global implementations in general and also requiring unsafe use ::{ impl … for … }; to import/"restore" a global implementation as scoped.

oskgo commented 3 weeks ago

An opt-in to having traits allow scoped impls would work, but opting in would then be a breaking change so it couldn't be used on stdlib traits. Still, one can argue that scoped impls are less likely to be useful for std anyways because pushing crate maintainers to implement stdlib traits isn't as hard as pushing them to implement third party traits.

I think that requiring opt-in (together with exportable scoped impls) could be sufficient to allow a second serialization library to start growing support without first needing maintainer buy-in.

It's going to be less useful for specialization, but that might be necessary for a sound version of this anyways.

There's still the drawback of unsafe Rust users needing to learn that they can't assume that traits opting in will have a unique consistent implementation. It's unclear to me how much of a restriction this is in practice, maybe a future possibility would be to allow generics to prioritize between trait implementations to get back the original behavior when this is needed.

Tamschi commented 3 weeks ago

I think that doing both would work and be a good balance:

For most uses (derives for common serialisation libraries, for example, but also of Debug, Clone, Default, uses of From, Into, Try) this would be enough, as they often do not make use of type-linked bounds at all. For other combinations, the TypeId differences hide the identity to generic code (which remains required also for other soundness reasons).

Since scoping has higher priority than Specialisation, this approach also avoids semver hazards. As a side-effect, there'd also be much less need to worry about logic errors related to Borrow.

There would still be friction when using such traits as collection items though, I think, since that would represent a link between e.g. Debug and Eq for example (but notably it's not a problem if the scoped implementation is on the collection, outside of any generic type parameters).¹

It's still allowed in safe code to inline-specify the implementation environment for a generic type argument so that it captures only global implementations.

¹ I also have to think about how far such types can be published… Though at a glance I think that any code that can statically see that the implementation is scoped would have to make a further bounded call resolving with a global implementation to practically mix them, which would trigger the restriction there, without it being a soundness or breakage issue for any code that exists today, at least. There may still be a problem with dyn, though.

If a trait definition opts into allowing alternatives, then:

It would be good to also require the signifier for this on each global implementation of an opted-in trait. This would signal to users of unsafe Rust that there's something unusual going on. On impls it would read well to mirror Specialisation there and have default on the impl itself (rather than on associated items), but that probably sounds very strange on trait definitions depending on how you look at it:

default trait Trait {} // Is this an auto-trait? 🤔
default impl<T> Trait for T {} // This may have alternatives! 🙂

I don't know if there's a keyword that would be a good fit there, currently. Maybe it's best to just use an attribute for the trait and default only on impls.

Edit (next day): A small addendum: The (only, I believe) reason that this needs to be marked on the trait definition and not just global implementations is that it needs to be consistent across specialisation-differentiated global implementations to not create a semver hazard… more precisely a specific global implementation mustn't deny it when added later than a more general global implementation that does allow global/scoped-mixing.

It's possible that this may be a non-issue though, for different reasons in different cases. There are eight cases, depending on whether the special or general implementation came first and whether each implementation (wants to) allow mixing with (type-linked) scoped implementations of other traits. Mitigating factors are where existing global implementations are guaranteed to be visible and limitations to where global implementations may be added.

For example, if an existing (broader) global implementation that allows mixing is guaranteed to be visible everywhere a new more specific global implementation may be added, then the semver hazard can be mitigated by warning on specialisations that don't allow mixing when at least one of its respective next-more-general implementations (in terms of specialisation!) does allow mixing. If the mixing-enabled next-more-general implementation is older and the implementing type is previously published, then the specialising implementation must allow mixing to not be a breaking change. If the specialising global implementation assumes a specific non-supertrait implementation (whether by acting as proof or through internal use of unsafe), it must not allow mixing. Otherwise, it can choose.

Additionally, if specialising implementations always lie in order in the crate dependency hierarchy (I think that's the case due to the current orphan rule, but please correct me if not), then later allowing mixing for an implementation that may do so is not an unsound or semver-breaking change because mixing would remain disabled anywhere the existing specialisations are in use already. By the same condition, it would be possible for a specialising implementation to allow mixing while its more general counterparts do not.

This needs to be checked carefully for all eight cases though (or 12, if you add allowing mixing for an existing global implementation), and right now I'm pretty sure I won't be able to do that before the end of next week.

default seems like the wrong keyword too, if you look at it from this angle. It's more like a "relaxed" implementation, really. I suspect that "strict" blanket implementations can't have their bounds fulfilled by scoped implementations under these rules though, at least not if that implies implementation of a supertrait.

Tamschi commented 1 week ago

I (finally) had some time to start looking into this just now:

Tamschi commented 1 week ago

Point three is not as complex as I had feared - in the least rigid solution, a specialisable implementation that newly adds final associated items where it didn't have any before must opt into mixing to avoid a breaking change, but that's it. I'll include a table that illustrates this better, still chipping away at that slowly between other things. This requirement isn't retroactive either and at worst causes compile-time errors if not heeded.

Unfortunately, this is most likely something that can't be linted for statically with enough accuracy for the lint to be useful. It can be detected easily by comparing the API to a previous version of the crate, but I don't think there's precedent for that outside of third party tools like cargo-semver-checks or cargo-public-api.

Outside of that, I could only confirm the development-time 'race condition' I mentioned in point two of my previous comment. It can be avoided by declaring 'a newly mixing-enabled specialisable impl that was previously specialisable or absent' a breaking change, but I don't have the guidelines knowledge here to decide that, so I'll defer it into an unresolved question.

Everything else seems to work out nicely. The case where a new specific impl shadows an existing mixing-enabled impl is easy to lint for and everything else seems to be either non-breaking or wouldn't compile.

Of course this isn't the actual formal write-up, so something else may come up.

Unrelatedly, blanket implementations effectively seal a trait in some ways and I still have to look into that properly. Adding such a blanket implementation (that's not specialisable) already is a breaking change, so I think letting that narrowly prevent scoped implementations doesn't cause additional SemVer hazards vs. the status quo.

A second opt-in on impls to allow them anyway should be fairly easily possible and unproblematic, though, and specialisable impls without final associated items should always allow scoped implementations since they aren't sealing at all.

(Regarding blanket implementations with final associated items… I think the natural action may be to let scoped implementations 'inherit' them? This is just a hunch, but I think this should work out seamlessly without any workarounds.)