Open kevinaboos opened 1 year ago
This seems like an issue for catching which a Rutenspitz test could be useful. I might get around to contributing one eventually.
This should be fixed in 0.8.1, although 0.8.0 should probably still be yanked. There could also be more exhaustive testing as @8573 suggests
Hi @sdleffler, thanks so much for this awesome crate! We've been using it for years in Theseus OS for symbol maps and other things.
Problem
I've discovered a tricky issue with the
Trie
'scount
value -- it's not updated properly when modifying theTrie
via theEntry
API, so if you insert a new value usingVacantEntry
, thecount
will be wrong.This bug manifests in two ways:
count - 1
"overflowing" below0
.0
tousize::MAX
, resulting inTrie::count()
returning a bogus value.Code example
Here's a commented example that shows the various ways this bug manifests.
Discussion
count
isn't updated correctly, but I'm not sure. As far as I can tell, the count is only updated in the top-levelinsert
andremove
functions, but I'm not intimately familiar with the rest of the code.v0.8.1
, the current version0.8.0
should be yanked fromcrates.io
to ensure downstream users don't hit this bug.