Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Possible bug in v0.10 with lookups on Box<[u8]> #225

Open
ezrosent opened this issue Jan 18, 2021 · 11 comments · May be fixed by #232
Open

Possible bug in v0.10 with lookups on Box<[u8]> #225

ezrosent opened this issue Jan 18, 2021 · 11 comments · May be fixed by #232

Comments

@ezrosent
Copy link

The following code exits cleanly using hashbrown 0.9.1, but fails on hashbrown 0.10

use hashbrown::HashSet;
fn main() {
    let mut m = HashSet::<Box<[u8]>>::new();
    m.insert(Box::from(&b"hello"[..]));
    assert!(m.contains(&b"hello"[..]));
}

Lookup of a &Box<[u8]> seems to work fine; the issue happens when calling get with a &[u8] on a HashSet<Box<[u8]>>. I've seen similar behavior with HashMaps
@Amanieu
Copy link
Member

Amanieu commented Jan 18, 2021

Nice catch, it seems that #207 is actually incorrect since the specialized hash impl is only called for &[u8] but not Box<[u8]>.

cc @tkaitchuck

@Amanieu
Copy link
Member

Amanieu commented Jan 18, 2021

I've yanked 0.10.0 until this gets resolved.

@Amanieu Amanieu mentioned this issue Jan 18, 2021
Merged
@CryZe CryZe mentioned this issue Jan 19, 2021
Merged
@tkaitchuck
Copy link
Contributor

tkaitchuck commented Jan 19, 2021 •
edited
Loading

Looking into it.

matklad added a commit to rust-analyzer/rowan that referenced this issue Jan 19, 2021
@matklad
Downgrade hashbrown
47f4ebd 
rust-lang/hashbrown#225
@Amanieu
Copy link
Member

Amanieu commented Jan 19, 2021

I don't think that the current approach for specialization can reliably support all forms of Rc<[u8]> or CustomPointer<[u8]>. We should look into another approach, possibly by modifying the Hash trait in the standard library.

@camshaft camshaft mentioned this issue Jan 19, 2021
Merged
@tkaitchuck
Copy link
Contributor

We can make all of those work correctly. They just won't be able to use the optimized hash implementation

@Amanieu
Copy link
Member

Amanieu commented Jan 19, 2021

I don't see any way other than simply disabling the use specialization altogether. We need to ensure that &[u8] and CustomPointer<[u8]> have their hashes calculated the same way.

@tkaitchuck
Copy link
Contributor

tkaitchuck commented Jan 19, 2021 •
edited
Loading

I can modify the make_hash function to dispatch based on K and pass the function some Q: Hash. Then if the key is CustomPointer<[u8]> and lookup is done with &[u8] it will use the non specialized path even though a specialized path exists.

The only complication is this requires the K: Hash, which is not actually required for some method signatures. I am not sure why not, but at the moment it appears to be possible to construct an empty map which nothing can be inserted into and to call some methods which will all reflect the fact that the map is empty.

@tkaitchuck
Copy link
Contributor

I have a prototype of this working locally. It requires some significant changes I'll have a PR in a few days.

@Amanieu
Copy link
Member

Amanieu commented Jan 20, 2021

Be careful about changing method signatures. Although we can make breaking changes in hashbrown, we should still ensure that hashbrown can be used as a base for the std hashmap.

@tkaitchuck
Copy link
Contributor

Once I get this merged and released: tkaitchuck/aHash#72
The only changes needed are these:
https://github.com/rust-lang/hashbrown/compare/master...tkaitchuck:specialization-fix?expand=1

@Amanieu
Copy link
Member

Amanieu commented Jan 22, 2021

Raw entry is still unstable in libstd, so I think that's probably fine.

This was referenced Jan 22, 2021
Closed
Closed
@KodrAus KodrAus mentioned this issue Jan 22, 2021
Merged
@tkaitchuck tkaitchuck linked a pull request Jan 26, 2021 that will close this issue
Open
@Amanieu Amanieu mentioned this issue Jan 27, 2021
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Issue #225: Specialization fix tkaitchuck/hashbrown
3 participants
@Amanieu @ezrosent @tkaitchuck