I wonder how to map a container in-place from type T to a repr(transparent) wrapper of T that establishes some invariant - purely as an optimization so that I do not need to rewrite the entire container into a new one. I very vaguely remember there being some functionality for it in std, although it might have been years ago and it definitely has been removed.
I doubt there is a general solution, but what about the most common containers from std: Vec and HashMap?
How to implement the following code in Rust?
#![feature(hash_map_macro)]
use std::{collections::HashMap, hash_map};
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone)]
#[repr(transparent)]
struct SortedVec<T>(Vec<T>);
fn into_sorted_vec(mut value: Vec<u64>) -> SortedVec<u64> {
value.sort_unstable();
SortedVec(value)
}
fn map_vec(input: Vec<Vec<u64>>) -> Vec<SortedVec<u64>> {
todo!("How to implement without allocating extra memory?");
}
fn map_hm<K>(input: HashMap<K, Vec<u64>>) -> HashMap<K, SortedVec<u64>> {
todo!("How to implement without allocating extra memory?");
}
fn main() {
let vec1: Vec<Vec<u64>> = vec![vec![3, 2, 1], vec![6, 5, 4]];
let vec2_expected: Vec<SortedVec<u64>> =
vec![SortedVec(vec![1, 2, 3]), SortedVec(vec![4, 5, 6])];
let vec1_mapped = map_vec(vec1);
assert_eq!(vec1_mapped, vec2_expected);
let hm1: HashMap<&str, Vec<u64>> = hash_map! {"one" => vec![3,2,1], "two" => vec![6,5,4]};
let hm1_mappedd = map_hm(hm1);
let hm2_expected: HashMap<&str, SortedVec<u64>> =
hash_map! {"one" => SortedVec(vec![1, 2, 3]), "two" => SortedVec(vec![4, 5, 6])};
assert_eq!(hm1_mappedd, hm2_expected);
}
And if you don't want to rely on a best effort feature you can do a dance with Vec::into_raw_parts, casting the raw pointer and then using Vec::from_raw_parts.
Maybe I'm missing something, but why wouldn't transmute be sound here? Assuming that no safety variants of the transparent wrapper are violated, and that the wrapper has the same layout (so no funny NonZero, pattern types, etc). Shouldn't Container<T> and Container<WrapperT> have the exact same memory layout and valid bit patterns?
This isn't needed for Vec (as previous answers show) but why wouldn't it not be sound for e.g. HashMap?
As an example, if the keys are what you're reinterpreting, the new type might have a different Eq or Hash. Or the HashMap might use std::any::type_name as part of the seeding process. So it's not the case by default that you can just transmute a container and get a valid container back.
The compiler is allowed to use a different layout for Container<Foo> and Container<Bar> unless Container and its components all use a repr that is more constrained than default repr(Rust)
Somewhat less plausible, but: the container could be storing a fn(T) -> bool or a dyn Trait<T> for some purpose, at which point compatibility depends not just on the layout of T but the ABI of T.
Broadly, there’s just no way to know from the outside that none of these problems exist for an arbitrary container type, except that type’s documentation.
Ideally, we would have the “safe transmute project”'s traits and containers could expose a trait to convert them in this way only if doing so was sound. But we don’t.
That is a fair point, didn't think of that. But it would be good to have some way to do this zero cost for all the std containers. It would likely have to be unsafe for many containers though, since it would be infeasible to determine if different Hash, Ord etc are equivalent.
We could (and IMO should) limit that. It would have to be after all layout attributes and traits are resolved (to not run into issues with <T as Trait>::Type being different, just though of that one). But if the only thing that differs are repr transparent wrappers it would be useful if they would be laid out the same.
Unsafe code can’t depend on a covariant type parameter remaining the same, due to subtyping between distinct higher-ranked function types that AFAIK could have different trait implementations. (But it could be a requirement for logical correctness.)
I think it could suffice for the type to not be invariant over the relevant generic parameter. (And using an associated type forces invariance, of course.) repr(transparent) should even have the same ABI, right…? In which case the “only” thing that would be needed is a compiler guarantee.
layout for Foo<A> and Foo<B> can differ even if A and B have the same layout.
repr(transparent) should even have the same ABI, right…?
If A is transparent around B then Foo<A> and Foo<B> still could have different layout. In practice they'll be the same most of the time, but you can provoke it with layout randomization.
While this is generally good to allow additional optimisations to be added, does it serve any purpose here (other than "because we can"?)
I think that it would be useful to add a narrow guarantee that if the only thing that differs for a concrete fully resolved type is repr transparent wrappers, then the types have the same layout.
This would mean that transmute is possible, but the actual container type (e.g. HashMap) would also need to guarantee this for it to be then be sound.
Today, I cannot write a HashMap that guarantees such transmutes even if I wanted to, but with language guarantees it would be possible. And then std could add such guarantees. For HashMap in particular it would also need to specify that the implementations of Hash and Eq need to be the same for example.
I can make my container repr(C), yes. But as far as I can tell it doesn't help today if the inner type is a transparent repr around a rust repr. And it is that case I would like to work better. I might not control that inner repr Rust.
A and #[repr(transparent)] Wrapper<A> are guaranteed to have the same layout. And the repr(C) layout algorithm is guaranteed to only take field order, alignment and size into account.
So the container would get the same layout if it is repr(C).
There two things that can prevent transmuting, for generic Foo<T> and T=X, and T=Z it's both that
Foo can change its layout - we can suppress that with repr(C)
X and Z can have different layouts even when we naively wouldn't expect it just by looking at their fields (e.g. randomization).
We can suppress this either by also making the inner types repr(C) or by making one a repr(transparent) wrapper around the other
If that is correct, then I'm happy with that. But I'm not sure where your second bullet point is guaranteed. I read the docs for transmute and the linked to section in the nomicon. Basically I'm not sure where it is stably guaranteed that a repr(Rust) inside a repr(transparent) inside a repr(C) will have the same layout as if the middle repr(transparent) is removed.
The nomicon reads:
So how do you know if the layouts are the same? For repr(C) types and repr(transparent) types, layout is precisely defined. But for your run-of-the-mill repr(Rust), it is not. Even different instances of the same generic type can have wildly different layout.
To me that doesn't clearly say what happens if you nest and mix them.