Prevent duplicate HashMap inserts from a type system level

I've been learning about the so-called typestate pattern and was curious if there was a way to leverage the type system to prevent inserting the same key.

Example:

So essentially, Wrapper::insert should either only be available to unique, other keys after inserting or fail at the type level having tried to insert the same key multiple times.

Forgive me if I misunderstand what you mean by "fail at the type level". If you want the second map.insert(Key::SomeKey); to fail at compile time, this seems like an undecidable problem. Looking at the function signature, there is no indication whether the SomeKey variant already exists in the map:

fn insert(&mut self, key: Key)

The compiler therefore cannot make any guarantees about what the map contains when this method is called. It would be like saying you have let v: Vec<i32> and you want to reduce v.contains(42) to a boolean at compile time for every Vec<i32>.

1 Like

What have you read so far about the type state pattern? While Rust encourages a type-driven design and has a rich type system, every information is contained in the type itself and there is no meta-state or something similar.
AFAIR this was an idea in the beginning of Rust that was dropped from a language design perspective. It is certain that it is very computationally expensive, even if done well, and generics can (at least partially) emulate it. You could, of course, design your own HashMap that would always give you a new type at insertion that somehow stored the old type (although I wouldn't know how to implement it), but that would be awkward to work with and imo not really worth it.

1 Like

Here is my implementation for keys between 0 and 31:

    let set0 = EMPTY;
    
    // Allowed
    let set1 = set0.insert::<3>();
    let set2 = set1.insert::<5>();
    
    // Disallowed: doesn't compile.
    // let _ = set2.insert::<3>();
5 Likes

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.