rust-lang / rust-lang/hashbrown
Support fallible eq and hasher in raw API
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 3k
- Forks
- 358
- Avg merge
- 11h 57m
- Merged PRs (30d)
- 2
Description
Hi!
I want to use the raw API of hashbrown as the underlying table implementation in Rune.
One aspect which has proven to be awkward is that the hasher I need to pass into RawTable::find_or_find_insert_slot is infallible, which works well for a statically typed language, but less so in Rune where I want to store and deal with dynamically typed entries directly.
Note: I've implemented a prototype of this in my
raw-infallible-contextbranch.
What I need to do is something like this:
let mut table: RawTable<(Value, Value)> = todo!();
let entry: (Value, Value) = todo!();
// NB: might fail if the key can't be hashed.
let hash = key.hash()?;
// Comparison might fail.
let eq = |other: &(Value, Value)| -> Result<bool, MyError> { Value::eq(&entry.0, &other.0) };
// Hashing might fail.
let hasher = |key: &(Value, Value)| -> Result<u64, MyError> { Value::hash(&key.0) }
let result = table.find_or_find_insert_slot(hash, eq, hasher);
// deal with my custom result
The change needed would be fairly straightforward (I think) but a bit tedious, what I think is needed is to refactor the API into a pair of methods like this (ignore naming):
use std::convert::Infallible;
#[inline(always)]
fn into_ok<T>(result: Result<T, Infallible>) -> T {
match result {
Ok(value) => value,
Err(error) => match error {},
}
}
#[inline(always)]
fn infallible_eq<T>(mut f: impl FnMut(&T) -> bool) -> impl FnMut(&T) -> Result<bool, Infallible> {
move |value| Ok::<_, Infallible>(f(value))
}
#[inline(always)]
fn infallible_hasher<T>(f: impl Fn(&T) -> u64) -> impl Fn(&T) -> Result<u64, Infallible> {
move |value| Ok::<_, Infallible>(f(value))
}
impl RawTable {
/// Backwards compatibility
#[inline(always)]
pub fn find_or_find_insert_slot(
&mut self,
hash: u64,
eq: impl FnMut(&T) -> bool,
hasher: impl Fn(&T) -> u64,
) -> Result<Bucket<T>, InsertSlot> {
into_ok(self.find_or_find_insert_slot2(hash, infallible_eq(eq), infallible_hasher(hasher)))
}
/// New method
pub fn find_or_find_insert_slot2<E>(
&mut self,
hash: u64,
mut eq: impl FnMut(&T) -> Result<bool, E>,
hasher: impl Fn(&T) -> Result<u64, E>,
) -> Result<Result<Bucket<T>, InsertSlot>, E> {
todo!()
}
}
The signatures leave something to be desired and such a change would have to be propagated through the rest of the API, the majority if which have proven to be internal. I would also hope that the compiler can easily prove the infallible variants are no-ops but this is something that should probably be investigated.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the raw API entry point RawTable::find_or_find_insert_slot and inspect the related raw-table methods mentioned in the issue. Review the linked raw-infallible-context branch to understand the proposed fallible callback design and the API propagation it requires. Done means fallible equality and hashing work through the raw API while preserving the existing infallible interface.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend-api-design
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100