HashMap trees generated in property tests are too flat and too small

haskell-unordered-containers / unordered-containers

Efficient hashing-based container types

BSD 3-Clause "New" or "Revised" License

221 stars 99 forks source link

HashMap trees generated in property tests are too flat and too small #438

Closed sjakobi closed 2 years ago

sjakobi commented 2 years ago

https://github.com/haskell-unordered-containers/unordered-containers/blob/4da2c201a274f7f3306117b479c51aef7af61129/tests/Strictness.hs#L24-L29

This hash function produces only values in the range [0..19]. As a result, a typical generated tree will have a BitmapIndexed root node that contains some Leafs and some Collisions. No Full nodes at all, and no internal/non-root BitmapIndexed nodes!

It seems very likely that some code added since #317 hasn't been tested at all. :/

sjakobi commented 2 years ago

Maybe it would also be good to deduplicate the Key type declarations. Currently, tests/Properties/HashMapLazy.hs, tests/Properties/HashSet.hs and tests/Strictness.hs all contain the same newtype Key declaration.