Always-full HashMap

[leob]

Hi everyone,

I am searching for a type similar to a HashMap<K, V> that is statically guaranteed to contain a V for every possible value of K, i.e. every possible key must have a value. I first thought about creating a data structure like this:

use std::collections::HashMap;
use std::hash::Hash;

#[derive(Debug, Clone)]
struct FullMap<K, V, F = fn(K) -> V>
where
    F: Fn(K) -> V,
{
    map: HashMap<K, V>,
    fallback: F,
}

impl<K, V, F> FullMap<K, V, F>
where
    F: Fn(K) -> V,
{
    fn from_fn(f: F) -> Self {
        Self {
            fallback: f,
            map: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Hash + Eq,
    {
        self.map.insert(key, value)
    }

    fn get(&mut self, key: K) -> &V
    where
        K: Hash + Eq + Clone,
    {
        self.map
            .entry(key.clone())
            .or_insert_with(|| (self.fallback)(key))
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[allow(dead_code)]
enum Foo {
    A,
    B,
    C(Bar),
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[allow(dead_code)]
enum Bar {
    A,
    B(bool),
    C,
}

fn main() {
    let mut my_map: FullMap<Foo, Bar> = FullMap::from_fn(|foo| match foo {
        Foo::A => Bar::A,
        Foo::B => Bar::B(true),
        Foo::C(bar) => bar,
    });

    assert_eq!(my_map.get(Foo::B), &Bar::B(true));
    my_map.insert(Foo::B, Bar::B(false));
    assert_eq!(my_map.get(Foo::B), &Bar::B(false));
    assert_eq!(my_map.get(Foo::C(Bar::A)), &Bar::A);
}

(Rust Playground)

However, this approach has some drawbacks:

• The FullMap is not serializable.
• It has three generic parameters (I could just use function pointers, but that would make any immutable capture impossible)
• get() needs mutable access in order to ensure consistency (if the function was impure), which means you can't read anything out of a &FullMap. Maybe interior mutability could be used to resolve this issue.

Is there a better way to achieve my goals of a statically proven always-full HashMap? Are there other problems with the current design?

[Cerber-Ursi]

Are you essentially looking for some kind of memoization, i.e. for some way to store fallback's results for reuse?

[H2CO3]

This is basically a total function. You could just write a function from an enum to V and call it. If you want to serialize the resulting mapping, you can always just enumerate all input values (e.g. strum has relevant traits/derive macros IIRC) and call the function, then serialize the result.

[leob]

@Cerber-Ursi

Are you essentially looking for some kind of memoization, i.e. for some way to store fallback's results for reuse?

No, although I can see how my current code could be viewed in that way. I am trying to create a data structure that maps every value of a type to one of another type, and is in every other way usable just as a regular HashMap (which does the same, but only partially).

In my example code, fallback is just - well, a fallback function that gets called when the inner HashMap doesn't contain the key. Ideally it wouldn't need to exist and some other way of expressing this relationship would be possible.

---

@H2CO3

This is basically a total function. You could just write a function from an enum to V and call it.

I see that it is fundamentally equivalent to a total function in the mathematical sense, but (to my knowledge) Rust doesn't have that as type and all functions can be impure, nondeterministic and / or halt. I want a data structure that doesn't have these issues. I may have not made this clear enough, but ideally I would not save any function in FullMap. Optimally this could work as a macro invocation like this:

let map = full_map! {
   Foo::A => Bar::A,
   Foo::B => Bar::B(true),
   Foo::C(bar) => bar,
};

This would - again ideally - fail to compile if not every branch was covered, and return a FullMap with the same API as above (even better without needing &mut self in get). But I have no idea on how to achieve this.

---

@H2CO3

you can always just enumerate all input values (e.g. strum has relevant traits/derive macros IIRC)

strum does not seem to support this kind of enumeration for every type, but just for enums (see the EnumIter derive macro docs). For contained values just the default value is used. I need an enumeration over all possible values that all matchable types implement, primitives too and own structs + enums via a derive macro. And I haven't found any crate for that yet.

[kpreid]

@leob

I need an enumeration over all possible values that all matchable types implement, primitives too and own structs + enums via a derive macro. And I haven't found any crate for that yet.

I wrote a crate for that, exhaust.

exhaust - Rust

It is not quite complete to my satisfaction — it does not implement its trait for all possible std types, and it requires that all types implement Clone which I would like to relax by redesigning the trait — but I think it will likely serve your purpose. (The use case for which I wrote it is essentially the same as yours, but exhaust itself does not include a “full map” type, leaving that to the dependent crate.)

[H2CO3]

@leob

Rust doesn't have that as type and all functions can be impure, nondeterministic and / or halt. I want a data structure that doesn't have these issues.

It's impossible. Most trivially, the very moment you start to use functions/Index impls/etc to access the data structure rather than poking around in its memory directly, those functions can be impure or panic.

@leob

Optimally this could work as a macro invocation like this:

let map = full_map! {
   Foo::A => Bar::A,
   Foo::B => Bar::B(true),
   Foo::C(bar) => bar,
};

This would - again ideally - fail to compile if not every branch was covered

That's exactly what the built-in match construct already does.

[leob]

@H2CO3

That's exactly what the built-in match construct already does.

I know, which is exactly the reason I wrote it like this. The macro should look and feel like a standard match construct, but create a data structure instead. Perhaps I should have conveyed this more explicitly.

---

@H2CO3

It's impossible. Most trivially, the very moment you start to use functions/Index impls/etc to access the data structure rather than poking around in its memory directly, those functions can be impure or panic.

The difference is that I control the Index implementation for my data structure and can make it never halt / panic / do impure stuff.
I of course cannot control (or even check) that an fn pointer passed to me halts, which is the reason I just used these for demonstration purposes and I would not consider them to be a viable solution.

---

@kpreid

I wrote a crate for that, exhaust .

This seems very interesting and useful, I will check it out! So if I understood correctly, the best way to make this work would be to require K: Exhaust, make the macro content part of a match statement (which should be possible via macro_rules) and then, for every key of type K, insert (key, f(key)) into the HashMap which FullMap would be a wrapper type around. If the Exhaust implementation fulfilled its rules, HashMap::index should never panic.
I would still have the problem that creation of the map involved arbitrary computation, but that is probably impossible to resolve (maybe that's also what @H2CO3 meant, I'm unsure).

Overall, thanks everyone for their help so far!

[H2CO3]

@leob

I of course cannot control (or even check) that an fn pointer passed to me halts

Perhaps we misunderstood each other. I did not suggest that you accept arbitrary functions from the outside world – rather, I was suggesting that you write the total funciron yourself, instead of regarding it as a data structure. If you are fine with your own Index impls, then writing your own free function should be fine, too.

[leob]

@H2CO3

I was suggesting that you write the total funciron yourself, instead of regarding it as a data structure.

Interesting idea, but I don't think this will work for my purpose as I will need to mutate the FullMap using an insert (or, more accurately named, replace) function. I don't think implementing it like this would be efficient or usable (if it would even borrowcheck).
But it's true that as I will create the data structure (and likely not publish it as a library) checking that the function is pure or doesn't halt is likely unnecessary.

[scottmcm]

@leob

that is statically guaranteed to contain a V for every possible value of K, i.e. every possible key must have a value

If talking about "every possible value" is useful for a type, that means the type has a bijection to some prefix of the natural numbers.

So it sounds like this is less a hash table and more an array.

[leob]

@scottmcm

If talking about "every possible value" is useful for a type, that means the type has a bijection to some prefix of the natural numbers.

Makes sense. Do you know a crate that offers this bijection for primitive types and, perhaps as a derive macro, for own structs and enums?

[kpreid]

@leob

the best way to make this work would be to require K: Exhaust, make the macro content part of a match statement (which should be possible via macro_rules) and then, for every key of type K, insert (key, f(key)) into the HashMap which FullMap would be a wrapper type around. If the Exhaust implementation fulfilled its rules, HashMap::index should never panic.

Yes, that's correct.

@leob

I would still have the problem that creation of the map involved arbitrary computation,

This is sort of impossible to avoid: you can do it for a specific type by defining a struct which contains a field for each possible value, but you can't have Rust macros generate that struct for you. You still get the guarantee that if a FullMap actually exists, it won't panic when accessed.

@leob

Do you know a crate that offers this bijection for primitive types and, perhaps as a derive macro, for own structs and enums?

enum-map does this implicitly for fieldless enums; I don't know of anything that does it for arbitrary structs or enums. (I created exhaust after using enum-map and strum and finding it limiting that they did not support fields.)

[Elmar]

The requested type feature is unclear to me at first but after some riddling, I think, the general solution you'd like to naturally use is called "invariant". Invariants are assertions in types or at function interfaces which are required to be true for all of their instances at every time. It would assert the existence of every key. An assertion rather than a functional feature. I am very new to Rust but a quick search yields this

https://crates.io/crates/contracts
Unfortunately only has invariants for individual methods or functions. Maybe there is a crate for type invariants.

The simpler more specific solution for your problem doesn't require an external software package. From a mathematical point of view, HashMaps are mutable functions. In theory one could create a total HashMap as a macro which returns a stateful function (closure) instead of a hashmap. This stateful function returns an initialized writable and readable reference for each key. I tried to create some code but I just had no experience to produce something, sorry.