Bottom Trait Woes

language design
1

This is a bit of a minor nitpick I admit, but I was playing around with the trait system and how constraints are handled, and the ergonomics around trying to have and use a Bottom trait are rather terrible. I was wondering what people's thoughts were, and how unusual my problems actually are here.

This is, to be clear, even more obscure than a bottom type like !, which many already consider obscure. But it is relevant to some very abstract code I've played with.

One can sort of make it work with purely safe code:

trait Bottom: ?Sized {
    const absurd : !;
}

fn unreachable_unchecked_but_safe<T : Bottom + ?Sized>() -> ! {
    T::absurd
}

This version has some downsides however. First off, it would be nice if like ! it participated in dead code detection and similar.

Further, it is not object safe. In general it would be nice if there was some way to use const values, at least in a non-dependent fashion, for object-safe traits. The code gen for such seems obvious, rather than function pointers in the vtable just but the values themselves.

Another option is:

//SAFETY: This must never be implemented in a way that can be satisfied
unsafe trait Bottom: ?Sized { }
fn unreachable_unchecked_but_safe<T : Bottom + ?Sized>() -> ! {
    //SAFETY: This being safe is exactly the  precondition of `Bottom`.
    unsafe { std::hint::unreachable_unchecked!() }
}

Which is object safe, but does require unsafe code.

Its counterpart, Top is easily handled, being just

trait Top: ?Sized {}
impl<T:?Sized> Top for T {}

(Also all of those ?Sized bounds should really be ?Concrete, as in Pre-RFC: A top of the opt out hierarchy and parametricity)

It is a minor nitpick, but it has come up in my experiments with advanced trait manipulation, and I thought I'd share to see if others had thoughts or similar complaints.

2

While these are types that are relevant to the theory of types, what are their actual practical use cases?

To put it concretely: where would I as an application or library developer want to use the Bottom trait (as opposed to !, which does have uses)? Let alone Top which seems even more useless.

What I'm trying to get at is: Is this even a practical issue or just a theoretical one? Some concrete practical code example of use cases might help motivate this.

3

Practical is a strong word. Though many things start out as abstract academic nonsense and then someone actually turns them into something practical. Rust demonstrates that!

But if you want to see some of the sorts of things where this sort of thing appears in my code... enjoy!

(At some point I should probably use macros for de-duplication)

use std::marker::PhantomData;
use std::fmt::Display;

struct Proof<T: ?Sized>(PhantomData<fn(&T) -> &T>);

trait Top {}
impl<T:?Sized> Top for T {}

trait WithTop<T: ?Sized> {
    type Output;
    fn go(self) -> Self::Output where T:Top;
}

trait IsTopProof<T: ?Sized> {
    fn go<Output>(&self, callback : impl WithTop<T,Output=Output>) -> Output;
}

impl<T: Top + ?Sized> IsTopProof<T> for () {
    fn go<Output>(&self, callback : impl WithTop<T,Output=Output>) -> Output {
        callback.go()
    }
}

impl<T: ?Sized> IsTopProof<T> for ! {
    fn go<Output>(&self, _ : impl WithTop<T,Output=Output>) -> Output {
        *self
    }
}

struct TopProof<T: ?Sized>(Proof<T>);

impl<T: ?Sized> IsTopProof<T> for TopProof<T> {
    fn go<Output>(&self, callback: impl WithTop<T,Output=Output>) -> Output {
        let boxed: Box<dyn WithTop<T,Output=Output>> = Box::new(callback);
        //SAFETY: Hoping the vtables line up...
        let alt_boxed : Box<dyn FnOnce() -> Output> = unsafe { std::mem::transmute(boxed) };
        alt_boxed()
    }
}

impl<T: ?Sized> TopProof<T> {
    pub unsafe fn unsafe_mk() -> TopProof<T> {
        TopProof(Proof(PhantomData))
    }
    pub fn mk() -> TopProof<T> where T : Top {
        TopProof::from_proof(())
    }
    pub fn from_proof(val : impl IsTopProof<T>) -> TopProof<T> {
        struct Mk<Inner: ?Sized>(PhantomData<fn() -> TopProof<Inner>>);
        impl<Inner: ?Sized> WithTop<Inner> for Mk<Inner> {
            type Output=TopProof<Inner>;
            fn go(self) -> TopProof<Inner> {
                unsafe { TopProof::unsafe_mk() }
            }
        }
        val.go(Mk(PhantomData))
    }
}

trait WithDisplay<T: ?Sized> {
    type Output;
    fn go(self) -> Self::Output where T:Display;
}

trait IsDisplayProof<T: ?Sized> {
    fn go<Output>(&self, callback : impl WithDisplay<T,Output=Output>) -> Output;
}

impl<T: Display + ?Sized> IsDisplayProof<T> for () {
    fn go<Output>(&self, callback : impl WithDisplay<T,Output=Output>) -> Output {
        callback.go()
    }
}

impl<T: ?Sized> IsDisplayProof<T> for ! {
    fn go<Output>(&self, _ : impl WithDisplay<T,Output=Output>) -> Output {
        *self
    }
}

struct DisplayProof<T: ?Sized>(Proof<T>);

impl<T: ?Sized> IsDisplayProof<T> for DisplayProof<T> {
    fn go<Output>(&self, callback: impl WithDisplay<T,Output=Output>) -> Output {
        let boxed: Box<dyn WithDisplay<T,Output=Output>> = Box::new(callback);
        //SAFETY: Hoping the vtables line up...
        let alt_boxed : Box<dyn FnOnce() -> Output> = unsafe { std::mem::transmute(boxed) };
        alt_boxed()
    }
}

impl<T: ?Sized> DisplayProof<T> {
    pub unsafe fn unsafe_mk() -> DisplayProof<T> {
        DisplayProof(Proof(PhantomData))
    }
    pub fn mk() -> DisplayProof<T> where T : Display {
        DisplayProof::from_proof(())
    }
    pub fn from_proof(val : impl IsDisplayProof<T>) -> DisplayProof<T> {
        struct Mk<Inner: ?Sized>(PhantomData<fn() -> DisplayProof<Inner>>);
        impl<Inner: ?Sized> WithDisplay<Inner> for Mk<Inner> {
            type Output=DisplayProof<Inner>;
            fn go(self) -> DisplayProof<Inner> {
                unsafe { DisplayProof::unsafe_mk() }
            }
        }
        val.go(Mk(PhantomData))
    }
}

impl<T: ?Sized> DisplayProof<T> {
    pub fn print(&self, val : &T) {
        struct Callback<'a,Inner: ?Sized>(&'a Inner);
        impl<'a, Inner: ?Sized> WithDisplay<Inner> for Callback<'a, Inner> {
            type Output = ();
            fn go(self) where Inner:Display{
                print!("{}",self.0)
            }
        }
        self.go(Callback(val))
    }
}

trait WithSend<T: ?Sized> {
    type Output;
    fn go(self) -> Self::Output where T:Send;
}

trait IsSendProof<T: ?Sized> {
    fn go<Output>(&self, callback : impl WithSend<T,Output=Output>) -> Output;
}

impl<T: Send + ?Sized> IsSendProof<T> for () {
    fn go<Output>(&self, callback : impl WithSend<T,Output=Output>) -> Output {
        callback.go()
    }
}

impl<T: ?Sized> IsSendProof<T> for ! {
    fn go<Output>(&self, _ : impl WithSend<T,Output=Output>) -> Output {
        *self
    }
}

struct SendProof<T: ?Sized>(Proof<T>);

impl<T: ?Sized> IsSendProof<T> for SendProof<T> {
    fn go<Output>(&self, callback: impl WithSend<T,Output=Output>) -> Output {
        let boxed: Box<dyn WithSend<T,Output=Output>> = Box::new(callback);
        //SAFETY: Hoping the vtables line up...
        let alt_boxed : Box<dyn FnOnce() -> Output> = unsafe { std::mem::transmute(boxed) };
        alt_boxed()
    }
}

impl<T: ?Sized> SendProof<T> {
    pub unsafe fn unsafe_mk() -> SendProof<T> {
        SendProof(Proof(PhantomData))
    }
    pub fn mk() -> SendProof<T> where T : Send {
        SendProof::from_proof(())
    }
    pub fn from_proof(val : impl IsSendProof<T>) -> SendProof<T> {
        struct Mk<Inner: ?Sized>(PhantomData<fn() -> SendProof<Inner>>);
        impl<Inner: ?Sized> WithSend<Inner> for Mk<Inner> {
            type Output=SendProof<Inner>;
            fn go(self) -> SendProof<Inner> {
                unsafe { SendProof::unsafe_mk() }
            }
        }
        val.go(Mk(PhantomData))
    }
}

trait WithSync<T: ?Sized> {
    type Output;
    fn go(self) -> Self::Output where T:Sync;
}

trait IsSyncProof<T: ?Sized> {
    fn go<Output>(&self, callback : impl WithSync<T,Output=Output>) -> Output;
}

impl<T: Sync + ?Sized> IsSyncProof<T> for () {
    fn go<Output>(&self, callback : impl WithSync<T,Output=Output>) -> Output {
        callback.go()
    }
}

impl<T: ?Sized> IsSyncProof<T> for ! {
    fn go<Output>(&self, _ : impl WithSync<T,Output=Output>) -> Output {
        *self
    }
}

struct SyncProof<T: ?Sized>(Proof<T>);

impl<T: ?Sized> IsSyncProof<T> for SyncProof<T> {
    fn go<Output>(&self, callback: impl WithSync<T,Output=Output>) -> Output {
        let boxed: Box<dyn WithSync<T,Output=Output>> = Box::new(callback);
        //SAFETY: Hoping the vtables line up...
        let alt_boxed : Box<dyn FnOnce() -> Output> = unsafe { std::mem::transmute(boxed) };
        alt_boxed()
    }
}

impl<T: ?Sized> SyncProof<T> {
    pub unsafe fn unsafe_mk() -> SyncProof<T> {
        SyncProof(Proof(PhantomData))
    }
    pub fn mk() -> SyncProof<T> where T : Sync {
        SyncProof::from_proof(())
    }
    pub fn from_proof(val : impl IsSyncProof<T>) -> SyncProof<T> {
        struct Mk<Inner: ?Sized>(PhantomData<fn() -> SyncProof<Inner>>);
        impl<Inner: ?Sized> WithSync<Inner> for Mk<Inner> {
            type Output=SyncProof<Inner>;
            fn go(self) -> SyncProof<Inner> {
                unsafe { SyncProof::unsafe_mk() }
            }
        }
        val.go(Mk(PhantomData))
    }
}

//Fully safe code!
fn sync_to_send<'a, T: ?Sized>(proof : SyncProof<T>) -> SendProof<&'a T> {
    struct MkSendProof<Inner: ?Sized>(PhantomData<fn() -> SendProof<Inner>>);
    impl<'a_inner, Inner: ?Sized> WithSync<Inner> for MkSendProof<&'a_inner Inner> {
        type Output = SendProof<&'a_inner Inner>;
        fn go(self) -> SendProof<&'a_inner Inner> where Inner:Sync {
            SendProof::mk()
        }
    }
    proof.go(MkSendProof(PhantomData))
}

//The reverse can't be done with safe code
/*
fn send_to_sync<'a, T: ?Sized>(proof : SendProof<&'a T>) -> SyncProof<T> {
    struct MkSyncProof<Inner: ?Sized>(PhantomData<fn() -> SyncProof<Inner>>);
    impl<'a_inner, Inner: ?Sized> WithSend<&'a_inner Inner> for MkSyncProof<Inner> {
        type Output = SyncProof<Inner>;
        fn go(self) -> SyncProof<Inner> where &'a_inner Inner:Send {
            SyncProof::mk()
        }
    }
    proof.go(MkSyncProof(PhantomData))
}
*/

// But we could do it with unsafe code, if we wanted!
// Is this actually sound?
fn send_to_sync<'a, T: ?Sized>(_ : SendProof<&'a T>) -> SyncProof<T> {
    unsafe { SyncProof::unsafe_mk() }
}

struct NotDisplay;

fn main() {
    //It actually works!
    DisplayProof::<u8>::mk().print(&5);
    if false {
        // THIS IS BAD
        unsafe { DisplayProof::unsafe_mk().print(&NotDisplay) };
    }
}

Since trait proofs can now be represented as values we can just move around, I'm hoping to extend this system to extracting and recombining dyn metadata, and possibly trying to implement working polymorphic recursion using some terrible abuse of vtable overlap.

Obviously none of this is... how about we use the word 'sane'. None of this is sane.

But rust is already capable of some representation here!

Each of those ZSTs asserts the existence of a vtable. With things like std::ptr::DynMetadata we can then further manipulate those vtables themselves.

However, if I want abstract category theory manipulation of the category of rust traits and rust vtables, top and bottom naturally fall out of that (in fact it would arguably be more proper for me to be casting to WithTop rather than FnOnce, it is only because FnOnce lets me get around the Box issue I do it).

If I want to represent the trait hierarchy properly, this is a must. For example, BottomProof<T> <-> DerefMutProof<&'a T, T> is, I believe, the correct function for lifting the trait hierarchy to the trait level, given how things are currently argued in things like Pin. Though actually that is debatable (Should &! : DerefMut be valid? There is talk about making &! itself an uninhabited type in terms of even validity rules, and even without that it is clearly already uninhabited for safety rules).

With this (horrible abomination of a system) we can represent all these questions as about the safety of various rust functions! We can even, I believe, offer things like From<!> for T without further coherence work (though at so my boilerplate that one might question why do so)!

4

I can't see how code generation is relevant. Since T: Bottom is not possible for any type, surely, not code for unreachable_unchecked_but_safe is ever generated, because you can’t possibly monomophize it for any concrete type in place of T, can you?

What's your point with object safety? It cannot possibly be the case that the type dyn Bottom exists and implements Bottom, that would be unsound! Well, perhaps, the best you could achieve is that dyn Bottom exists as a type (no compilation error by just naming that type) but does not implement the trait Bottom (so the compilation error comes as soon as you try to require _: Bottom on it). But I fail to see how that’s particularly valuable / of any use.

5

Not as in dead code detection for optimization, I mean the thing where if a block contains a ! it automatically can result in !. I'm not sure what that is called besides "dead code detection"?

I agree dyn Bottom : Bottom can't work, but what is interesting is unlike a lot of other cases where dyn Trait : Trait doesn't work, not even for any part of the trait, a parametric function of the shape for<T> fn(metadata : BottomVTable<T>, value : Box<T>) -> Output is interesting.

The VTable has no methods that require using a second instance of the same type, so the erasure doesn't block them. In fact, it is just an uninhabited type.

If I pass in a VTable for Clone and a Box or reference to the type... technically you can do anything with it. You can clone and drop as many times as you want. But there isn't much value to that. With Bottom you can do everything with that.

EDIT: I'm not actually sure the rust calling convention is such that you can reliably call clone on an unknown type, even just to forget the result, even as a non-guaranteed thing, and suspect it might not be.

6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.