A hashtable with few requirements on types

help
1

Hello !
I am looking for something like :

HashMap<A:Sized + Clone + PartialEq, V: Sized + Clone + PartialEq>
// Sized, Clone and PartialEq are the only trait i can have

and in particular without any of the following trait on A or V : Eq, Hash, Ord; this constraint excludes HashMap and BTreeMap.
Yet, it should be possible: as my type A is sized I could just turn the raw bytes into a Hash to make it work, or just make an ordering out of the raw bytes of my objects (I don't care that my ordering is random I just need one); but I am unable to find a (unsafe) function that could do that for me, do anyone know such function ?
Thanks !
NB : I am kind of new to rust, and English is not my primary language.

2

You can't do this without UB in the general case, because types can contain uninitialized padding bytes, and reading uninitialized data is UB.

The closest thing you'll find is probably bytemuck::bytes_of, which enforces the relevant safety checks via its NoUninit trait.

The easiest way to implement this is probably by defining a wrapper type that implements Hash, Eq, and Ord based on the results of bytes_of, and then store that in a regular HashMap or BTreeMap:

pub struct HashBytes<T>(pub T);

impl<T:NoUninit> PartialEq for HashBytes<T> {
    fn partial_eq(&self, rhs: &Self)->bool {
        bytes_of(self) == bytes_of(rhs)
   }
}

// and similar for other traits...
2 Likes
3

Thanks, it looks exactly like what I want, I'll do some tests.

[First Attempt]
One of the type I want to Ord i s:

#[derive(Clone, NoUninit)]
#[repr(C)]
struct funtype<A: RegularOrd, V: RegularOrd> {
    explicit: Rc<dyn Fn(A) -> V>,
    hashtable: BTreeMap<A, V>,
}

With : RegularOrd: Sized + Clone + PartialEq + Eq + Ord
But NoUninit cannot work with struct using generic types (I don't know why, as long as they are Sized that looks doable).

Without the randomness of padding bytes I could have done something like:

impl<A:RegularOrd, V:RegularOrd> Ord for funtype<A, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        let expl_bytes: &[u8] = bytes_of(&self.explicit);
        let ht_bytes: &[u8] = bytes_of(&self.hashtable);
        let other_bytes: &[u8] = bytes_of(&other.explicit);
        let other_ht_bytes: &[u8] = bytes_of(&other.hashtable);
        // .. do some comparison
    }
}

I could also use repr(packed) but it looks like its not a good solution.

4

What is the reason for this? I guess it doesn't matter what the reason is, but I'm prodding because the general workaround is introducing a newtype that can implement these traits.

Trivial example: Rust Playground

5

The layouts of most std types and many built-in types is unspecified, so an Rc<dyn Fn(A) -> V> or BTreeMap<A, V> may contain unitialized bytes such as padding.

3 Likes
6

Thanks for your help.

The struct :

struct funtype<A: RegularOrd, V: RegularOrd> {
    explicit: Rc<dyn Fn(A) -> V>,
    hashtable: BTreeMap<A, V>,
}

represents a function with (maybe) some modification stored in the table (ex: f(x) = x2 but f(0) = 1), the challenge is that I can have funtypes as function argument.

The challenge is hence ordering all funtypes (whatever the ordering). But, indeed, the padding bytes prevent me from doing it the trivial way.

I tried to Box the fields of the structs in order to be sure that there is no padding bytes (by looking at the code of the Box), but anyway I can't forcefully implement Pod/Copy (that is saying to rust "trust me there is no padding bytes", even in unsafe Rust).

Still looking for a solution.

7

I think that may do the job :

impl<A: RegularOrd, V: RegularOrd> Ord for funtype<A, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        let ptr_expl_self: *const dyn Fn(A) -> V = Rc::as_ptr(&self.explicit);
        let ptr_expl_other: *const dyn Fn(A) -> V = Rc::as_ptr(&other.explicit);
        if ptr_expl_other == ptr_expl_self {
            let ptr_ht_self: *const BTreeMap<A, V> = Rc::as_ptr(&self.hashtable);
            let ptr_ht_other: *const BTreeMap<A, V> = Rc::as_ptr(&other.hashtable);
            ptr_ht_self.cmp(&ptr_ht_other)
        } else {
            ptr_expl_self.cmp(&ptr_expl_other)
        }
    }
}

It's not perfect (two identical functions could have different Rc, so our ordering is not antisymmetric) but it's not a big deal.
I will do some tests and mark the subject solved if that works.

8

You'll want to read the caveats around wide pointer comparison.

9

Thanks for the notice !

In case my *const dyn Fn(A) -> V are considered equal when they should not, it's almost better : that means the functions are indeed identical.

But the deduplication of (identical) vtable is a real issue, why Rust would do that ? Is there a compiler option that could prevent it from doing that ?

Edit: some tests confirm that it does not work :frowning:

10

Not one you can rely on. You can set the number of codegen units but apparently that's not always enough and you'd be relying on unspecified behavior if it happens to work today.

I'll also just throw out there (since it wasn't brought up in that issue) that comparison of pointers to zero-sized types is also problematic. So if you avoid comparing vtables, you're going to have to force your objects to be sized somehow.

(Long story short, pointer identity is a poor fit for Rust.)

1 Like
11

EDIT : I am quite new to the forum, and I am unable to mark the subject closed without selecting a solution, so i selected this message, which is not a solution.

Okay, thanks.
I think I will close the subject: I was thinking that the representation would allow some (weak) comparison of functions, but that does not look really doable.
Behind this issue is the fact that it is really hard (impossible?) to check the equality between two functions.
Thanks for all your responses, it really helped to understand what's going on behind Rc.

12

You might just add a u64 to the struct and use that for ordering. As long as it is given a unique value (either random with low probability of collisions, or sequential identifiers from an atomic static counter) then you can always provide a total order for the type.

Or if you want to order only the functions, put it inside the pointer: Rc<(u64, dyn Fn(A) -> V)>. Anyway, just add extra state and use that for ordering and hashing.

1 Like
13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.