Is transmuting (T, ()) to T safe?

Question

I am implementing an alternative to a BTreeMap<K, V>. On top of this I'm building a BTreeSet, which is a wrapper around type MyBTreeSetContents<T> = MyBTreeMap<T, ()>.

Internally, leaf nodes of this BTree contain a Vec<(K, V)> of values. In the case of the BTreeSet, this thus becomes a Vec<(K, ())>.

I want to provide a fast iterator over references of the values in the BTreeSet. An iterator that produces &T. But the best I can get so far without reaching for transmute is an iterator that produces &(T, ()).

So therefore the question:

• Is the memory representation of K, (K, ) and (K, ()) the same?
• Is it therefore OK to transmute between (K, ()) and K?
• And by extension, is it OK to transmute the Vec<(K, ())> to a Vec<K>?

If there are alternative approaches that circumvent usage of std::mem::transmute all-together, those would of course also be very much appreciated!

Answer 1

No. As far as what is currently enforced, transmuting (T, ()) to T is not guaranteed. Tuples use the default representation which does not imply anything about the layout beyond what is said in The Rust Reference. Only #[repr(transparent)] will guarantee layout compatibility.

---

However, it will probably work and may eventually be guaranteed. From Structs and Tuples in the Unsafe Code Guidelines:

In general, an anonymous tuple type (T1..Tn) of arity N is laid out "as if" there were a corresponding tuple struct...

...

For the purposes of struct layout 1-ZST^[1] fields are ignored.

In particular, if all but one field are 1-ZST, then the struct is equivalent to a single-field struct. In other words, if all but one field is a 1-ZST, then the entire struct has the same layout as that one field.

For example:

type Zst1 = ();
struct S1(i32, Zst1); // same layout as i32

^{[1] Types with zero size are called zero-sized types, which is abbreviated as "ZST". This document also uses the "1-ZST" abbreviation, which stands for "one-aligned zero-sized type", to refer to zero-sized types with an alignment requirement of 1.}

If my understanding of this is correct, (K, ()) has the equivalent layout to K and thus can be transmuted safely. However, that will not extend to transmuting Vec<T> to Vec<U> as mentioned in Transmutes from the Rustonomicon:

Even different instances of the same generic type can have wildly different layout. Vec<i32> and Vec<u32> might have their fields in the same order, or they might not.

Unfortunately, you should take this with a grain of salt. The Unsafe Code Guidelines is an effort to recommend what unsafe code can rely on, but currently it only advertises itself as a work-in-progress and that any concrete additions to the language specification will be moved to the official Rust Reference. I say this "will probably work" because a facet of the guidelines is to document current behavior. But as of yet, no guarantee like this has been mentioned in the reference.