search

haskell-unordered-containers / unordered-containers

Efficient hashing-based container types
BSD 3-Clause "New" or "Revised" License
221 stars 97 forks source link

Check invariants for all operations #449

Closed treeowl closed 2 years ago

treeowl commented 2 years ago

We now check invariants for intersections. We should do it for everything else too. containers generally integrates validity tests into other correctness tests (i.e., is the result valid and does it satisfy the other expected properties). That wouldn't be a bad approach to emulate.

sjakobi commented 2 years ago

containers generally integrates validity tests into other correctness tests (i.e., is the result valid and does it satisfy the other expected properties).

What does this look like in practice? Do you have a link?

treeowl commented 2 years ago

It varies somewhat by module, and I don't know that the design is wonderful. Would it be so bad to just add valid result .&&. to each test?

sjakobi commented 2 years ago

I don't know whether it would be so bad, but my preference is to have separate validation tests. I think that would make it easier to see whether such a test exists for a given function or not. In containers, the existence of these tests doesn't seem obvious in many cases.

treeowl commented 2 years ago

My concern with separate tests is performance. I'd much rather have enough time to run, say, 20×(property+validation) tests than 15×property+15×validation, or whatever it comes out to. Generation isn't free, and neither are intersections, unions, etc. I agree that the way it's handled in containers isn't optimal for clarity; can we do better?

sjakobi commented 2 years ago

Where are these performance concerns coming from? Currently, the entire test suite takes about 1s to run for me. 1.6s with -O0. If it ends up taking 3s, would that be a problem for you?

treeowl commented 2 years ago

Wow ... that's ... surprising. To my mind, such fast runs means our examples are too small or there aren't enough of them.

sjakobi commented 2 years ago

Wow ... that's ... surprising. To my mind, such fast runs means our examples are too small or there aren't enough of them.

Maybe. In my experience test suites of Haskell packages often are quite speedy. The bytestring test suite, which is quite a bit larger than u-c's takes 2s for me for example.

treeowl commented 2 years ago

I haven't looked at the test suite recently. Are we getting coverage of enough tree shapes and heights, ignoring the Full issue?

sjakobi commented 2 years ago

I haven't looked at the test suite recently. Are we getting coverage of enough tree shapes and heights, ignoring the Full issue?

That was the goal with https://github.com/haskell-unordered-containers/unordered-containers/pull/442. I'm fairly confident about the test generators. But feel free to investigate.