Invariants should be documented and tested

[sjakobi]

Information about invariants is scattered over the code and old issues. It would be good to collect it in one place and add tests or assertions to check that the invariants are upheld.

So far I'm aware of the following actual or supposed invariants:

1. Empty can appear at the top-level, but never in the tree:

   unordered-containers/Data/HashMap/Internal.hs

   Lines 380 to 383 in f59bb26

   	-- We rely on there being no Empty constructors in the tree!
   	-- This ensures that two equal HashMaps will have the same
   	-- shape, modulo the order of entries in Collisions.
   	equal1 :: Eq k

2. The array in Full has size 2^bitsPerSubkey:

   unordered-containers/Data/HashMap/Internal.hs

   Lines 206 to 207 in f59bb26

   	-- Invariant: The length of the 1st argument to 'Full' is
   	-- 2^bitsPerSubkey

3. In BitmapIndexed b ary, popcount b == size ary (Add more detailed data structure information #161 (comment))

4. When a BitmapIndexed contains only one subtree, that subtree is either a Full or BitmapIndexed node, but never Empty, Leaf or Collision.

5. The size of the array in Collision is at least 2.

6. The size of the array in BitmapIndexed is at least 1 and less than 2^bitsPerSubkey.

7. No two keys in a HashMap are equal according to (==).

8. The hashes in Leaf and Collision are those of the keys they contain.

9. No two Hashes in a HashMap are the same (but in a Collision multiple keys have the same hash).

10. In BitmapIndexed b ary, how exactly do the bits in b correspond to the elements of ary?

[treeowl]

There's also a file on development/contributing info that I think may have some.

[sjakobi]

There's also a file on development/contributing info that I think may have some.

I think you mean https://github.com/haskell-unordered-containers/unordered-containers/blob/master/docs/developer-guide.md. No additional invariants there AFAICT.

[sjakobi]

I have added these items to the issue description:

• No two Hashes in a HashMap are the same (but in a Collision multiple keys have the same hash).
• In BitmapIndexed b ary, how exactly do the bits in b correspond to the elements of ary?

[sjakobi]

TODO: Strictness invariants (#235 is related.)

[sjakobi]

#444 has added the basic tooling for invariant-checking. Most HashMap-producing functions still need tests though.

I'm pretty pleased with this progress, anyway! :)

[sjakobi]

Most HashMap-producing functions still need tests though.

This is tracked in #449.

[treeowl]

Indeed. Sorry for the duplicate.