pre-RFC FromBits/IntoBits

[gnzlbg]

@kornel What I meant is, how do you deal with this (assuming alignment would be right):

pub struct Foo(u8, u8);
let xs = [0_u8; 1];
let Foos: &[Foo] = (&xs).into_bits();   // ?

That is, I don’t understand how safe infallible conversions between slices could work because the length of a slice is not part of its type, so at best such a conversion would need to be fallible and return an Option (and would need to be accounted for by TryFromBits, or similar traits, not discussed here). In the case above, I don’t see a clear way of safely “transmuting” a slice of 1 u8 to a slice of Foo where each Foo has a size of 2 u8s. So what am I missing?

[jmst]

The compiler sees that the fields are not public, and types with any private field would not be compatible with anything except trivially their own exact type (and maybe the same type with different generic parameters, if the private fields had compatible types and if an attribute to enable that was manually placed on the type).

[gnzlbg]

The compiler sees that the fields are not public, and types with any private field would not be compatible with anything (except maybe with same type with different generic parameters, if the private fields had compatible types and if an attribute to enable that was manually placed on the type).

I see. The question then becomes: how do we offer this functionality for types with private fields? FromBits/IntoBits allow this. That is, given the previous example:

// This struct can only contain one value (42, 42)
struct Foo(i32, i32);
impl Foo {
    pub fn new(x: i32, y: i32) -> Self {
        assert!(x == 42, y == 42);
        Foo(x, y)
    }
}

// This struct can contain all permutation pairs of 42, 7: (42, 42)
// (7, 7), (7, 42), (42, 7)
struct Bar(u32, u32);
impl Bar {
    pub fn new(x: u32, y: u32) -> Self {
        assert!(x == 42 || x == 7, y == 42 || y == 7);
        Foo(x, y)
    }
}

impl FromBits<Foo> for Bar { ... } // This is safe and correct
// impl FromBits<Bar> for Foo { ... } // can't be implemented

Transmuting from Foo to Bar is ok while the opposite is not true.

We use this property of FromBits/IntoBits in stdsimd a lot actually. For example, transmuting from b8x8 (a boolean mask of 8 8-bit integers) into i8x8 is ok, but the opposite isn’t (not al i8x8 bit patterns are valid b8x8 ones). Also, all fields of SIMD types are private. You might use a native 128-bit type on one architecture, but emulate it using 4x 32-bit types in another, so the exact internal representation isn’t something we want to expose.

[jmst]

I think both the Foo/Bar and SIMD cases can be addressed by allowing to specify compatibility explicitly and then automatically closing the relation transitively (i.e. if A is manually declared as compatible with B, and B with C, then A becomes compatible with C).

The compatibility specification could either by an explicit trait impl, an attribute on the type or a macro-like syntax.

Could also have a way to say to do as if fields were not public, as a shorthand for declaring compatibility with an identical struct but with public fields.

bool -> int but no int -> bool seems orthogonal, and seems addressable by making Compatible not be reflexive.

Also note that structs with multiple fields without a layout-fixing repr should probably not be compatible with anything other than maybe structs with the exact same contents (and even this would mean giving up the option to do profile-guided struct layout differently for each type, so probably not a good idea).

[gnzlbg]

So how would this system fit with your Compatible trait proposed above? Could you summarize your whole proposal?

[gnzlbg]

@jmst I’ll try to summarize your proposal as good as I can. You propose to add an auto trait:

auto trait Compatible<T> {
    fn from_compatible(T) -> Self; // needed for the explicit impls
}

that:

• is automatically derived for all permutations of two equally-sized equally-aligned types with whose fields are all public,
• allows coercing T as Self, e.g., using Self::from_compatible(T) (or some other syntax)
• is transitive: allows coercing T as V, if Compatible<T> for U and Compatible<U> for V

For types with private fields, the users would need to specify this trait manually for the relations they care about and due to transitivity the compiler would “fill in the blanks” from the relations the users specifies to the relations the target types support.

Is that it?

[jmst]

The idea would that something like this is added to the core crate:

pub unsafe trait Compatible<T> {}

pub fn safe_transmute<T, U>(x: T) -> U where U: Compatible<T> {unsafe{transmute(x)}}

A first version could just be this, requiring manual implementation of the trait.

A second version could add compiler support for automatically deriving the trait in addition to doing so manually and for performing transitive closure so that if A: Compatible<B> and B: Compatible<C> (whether manually or automatically), then A: Compatible<C>.

A further addition could be to provide a safe way to manually implement the trait for private types in the current crate.

The compiler would generally derive it when doing so would not result in safe_transmute having undefined behavior, changing its result depending on compiler optimization strategy or backwards-compatible crate changes or creating values of U that could not be created otherwise.

The details of the exact rules to accomplish that would be take quite some work and probably some trial-and-error to specify precisely: for example, it needs to account for private field preservation, alignment preservation, the possibility of struct/enum layout optimization changes, non-exhaustive types like char and enum, and so on.

[gnzlbg]

How does coherence interact with your approach?

For example, with the FromBits/IntoBits approach if you have two crates, A and B, exposing two types A::AT and B::BT, a third crate C cannot implement FromBits<A::AT> for B::BT.

Maybe your approach could “fill in this blank”, but I don’t know whether doing so is brittle. For example if crate B adds a new private field to BT, which used to have only public fields. This already is a breaking change, so this breaking might be ok.

[jmst]

Now that I think of it one could have a fallible extension, like:

pub unsafe trait MaybeCompatible<T> {
    fn is_compatible(&self) -> bool {true}
}

pub unsafe trait Compatible<T> : MaybeCompatible<T> {}

pub fn safe_transmute<T, U>(x: T) -> U where U: Compatible<T> {unsafe{transmute(x)}}

pub fn try_safe_transmute<T, U>(x: T) -> Option<U> where U: MaybeCompatible<T> {if(x.is_compatible) {Some(unsafe{transmute(x)})} else {None}}

which would allow to convert int -> char when int happens to be a valid Unicode code point, or &[u8] -> &[u32] when it happens to be 4-byte-aligned.

[jmst]

In the minimalist version, that’s impossible.

With automatic transitive closure crate C could define a type CT and (using “unsafe”) declare that AT is compatible with CT and CT with BT.

But in general this shouldn’t be an issue if the trait is derived by the compiler, since if AT and BT are not automatically compatible, crate C usually cannot safely declare them compatible (not sure if there can be any cases where that would be safe and compatible with changes in crates A/B).

[gnzlbg]

So I like your approach a lot. Declaring all FromBits/IntoBits implementation in stdsimd is painful and error prone (as in, it is easy to miss one). With your approach we would still need to declare some of them manually, but due to transitivity we would get most of them for free.

For example, we would only need to implement the traits for most portable vector types only once, e.g., from u8x16 to __m128 and viceversa, and because of transitivity, we get the u16x8, u32x4, i32x4, f32x4, … conversions automatically for free.

For the vector mask types like b8x16, we can implement b8x16 -> __m128 but not the other way around, and get all the correct conversions for free.

With FromBits/IntoBits one needs N^2 implementations, with your approach 1 for types with public fields which the compiler fills in for you, and at worst O(N) for types that should only support uni-directional conversions.

I think it would be really nice if you could write an RFC, and if you need help with the motivation or examples we have more than enough in stdsimd.

[kornel]

AFAIK [T] to [u8] always works. [u8] to [T] is not guaranteed to work indeed, but that’s not a problem for me.

I don’t need a specific built-in function/method for conversion between just slices. I need a generic trait bound that lets me implement myself a family of such functions for various combinations of types.

[jcsoo]

This could be extremely useful for use with C-like enums if the compiler is smart enough to recognize valid ranges, much like it does when checking for exhaustiveness in match statements.

The simplest case is a #[repr(T)] enum where every possible value in T is defined in the enum. In practice this would be useful mainly for repr(u8) because of the current require to specify enum items for each individual value.

A slightly more advanced case is a #[repr(T)] enum where every value between 0 and N are defined. Currently it is only possible to convert between enums with the same ranges either through exhaustive match statements or using transmute. Compiler-generated implementations of FromBits / IntoBits or Compatible would eliminate a huge amount of unsafe boilerplate code and be the first step into turning C-like enums into a general-purpose ranged value type.

For instance, bobbin-bits defines enums for U1 to U32 (covering 1-bit to 32-bit values) and ranges R1 to R32 (covering ranges for 1…N). These are used for modeling bit fields and for type-checked indexing of small fixed arrays, but using them with enums requires manually implementing From and To traits to do conversions, which is tedious and mistake-prone.

It would be far more useful if I could do something like this and have the compiler check that Compatible<U4> is valid:

fn takes_u4<T: Compatible<U4>>(v: T) {
   let value: U4 = v.safe_transmute();
   do_something(value)
}

enum ThingWithSixteenItems {
    Item0 = 0,
    Item1 = 1,
    ...
    Item15 = 15,
}

impl Compatible<U4> for ThingWithSixteenItems {}

or even better, have the Compatible<U4> trait automatically derived for any enum matching the valid range of U4.

[gnzlbg]

@jmst One thing that came out during the preparation of the portable SIMD vectors RFC is that a safe Compatible<T> would probably need to produce the same results in both little endian and big endian platforms.

That is, currently unsafe { mem::transmute } produces this behavior (playground):

let x: [i8; 16] = [
    0, 1, 2, 3, 4, 5, 6, 7,
    8, 9, 10, 11, 12, 13, 14, 15
];
let t: [i16; 8] = unsafe { mem::transmute(x) };
if cfg!(target_endian = "little") {
    let t_el: [i16; 8] = [256, 770, 1284, 1798, 2312, 2826, 3340, 3854];
    assert_eq!(t, t_el);  // OK on LE
} else if cfg!(target_endian = "big") {
    let t_be: [i16; 8] = [1, 515, 1029, 1543, 2057, 2571, 3085, 3599];
    assert_eq!(t, t_be);  // OK on BE
}

It would be nice if a safe_transmute operation could produce the same result in both architectures:

let x: [i8; 16] = [
    0, 1, 2, 3, 4, 5, 6, 7
    8, 9, 10, 11, 12, 13, 14, 15
];
let t: [i16; 8] = safe_transmute(x);
let el: [i16; 8] = [???];
assert_eq!(t, e);  // OK on LE and on BE

Maybe this might not only be nice, but actually a necessary condition to make safe_transmute safe.

AFAIK the only way to achieve this would be to swap bytes inside safe_transmute on either little endian or big endian architectures.

[comex]

That would be impossible when converting slices, and in any case, endianness dependence is not unsafe.

[hsivonen]

I think it would make the RFC more compelling if you gave some SIMD examples - cases where “users might be tempted to reach for unsafe { mem::transmute(…) }” as you put it.

All of the transmute_copy() calls in simd_funcs.rs of encoding_rs are actually safe and I’d like to write them so.

in any case, endianness dependence is not unsafe.

That’s news to me, but happy news.

For ergonomic portable SIMD, it’s essential that we have convenient safe syntax for the SIMD type conversions that are zero-cost reinterpretations in the little-endian case but produce different results in the big-endian case.

Since, thanks to WebGL, big endian is not coming back, I don’t care much what Rust does for SIMD in the big endian case (compute different results, inject shuffles to match little-endian results or make the conversion unavailable when compiling for a big-endian target), but I really want to have safe wrappers for the little-endian SIMD transmutes.

[jmst]

In addition to just ignoring the problem, a way to handle endianness could be to add a trait variant of Compatible that is guaranteed to give the same results regardless of endianness.

To do so, one would introduce a #[repr(ecC)] for “endian-corrected C repr” (could maybe find a better name for this) which would be like repr© except that fields are laid out in reverse order on big-endian machines.

In addition, endian-corrected tuples, slices and arrays need to be introduced, where on big-endian machines items are laid out backwards and indexing is implemented by subtracting from the end (the syntax maybe being something like &'a #[repr(ecC)] [u8]).

Then cases where the conversion would give different results would be defined only for repr(ecC) when using the endian-corrected version of the trait.

Having to duplicate tuples, slices and arrays is annoying, but those types would probably only be used for small sections of code.

Alternatively one could lay out everything backwards by default, but this would be incompatible with C FFI and performance might be reduced since the CPU instruction sequence for backwards indexing is often less efficient and the backward direction might not trigger hardware prefetching if the CPU is not sophisticated enough.

As a further extension, one could add an “always-reversed repr” and an “reversed only on little-endian repr” and provide a ByteSwap trait that could convert between the versions (either implemented with custom derive or again by the compiler).

An even further extension would be allowing structs and code to be generic over the repr (without using macros), although I guess this would not be worth it.

[not sure about the WebGL argument, since it seems to me that only the GPU needs to be configurable to run in little-endian mode, which is true for all PCIe GPUs since they must work in PCs, and the JS/Wasm CPU code could just byteswap on all memory accesses - it’s not ideal, but CPUs are not normally designed to primarily run WebGL or WebAssembly code]

[joshlf]

I recently proposed Pre-RFC: Trait for deserializing untrusted input, which is similar to some of the arbitrary bits stuff (like the pod crate) discussed here.

One important difference is that we propose having a custom derive. So instead of requiring your fields to be public or requiring you to use an unsafe impl, you can voluntarily do #[derive(ArbitraryBytesSafe)] (that’s the trait name we propose), and the custom derive will verify whether all of your fields, and their composition, are safe for deserializing from arbitrary byte patterns. It works for private fields too, but because you have to explicitly use the derive, it won’t just automatically apply to your type, invalidating your invariants.

[gnzlbg]

@joshlf is the trait transitive ? That is, is there a way to safely transmute between two unrelated types deriving ArbitraryBytesSafe ?

[joshlf]

Well you can copy the bytes of any T into something which is ArbitraryBytesSafe because those bytes are just bytes. You could even transmute a T into an ArbitraryBytesSafe as long as you were willing to mem::forget or drop the original T. So I guess it’s transitive in the trivial sense that anything can be converted into an ArbitraryBytesSafe.