rust-lang / rust-lang/hashbrown

Support fallible eq and hasher in raw API

Open
#456 8 comments 0 reactions 0 assignees View on GitHub

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-context branch.

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.