search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
314 stars 177 forks source link

Improve Ord IntSet instance #787

Open treeowl opened 3 years ago

treeowl commented 3 years ago

An attempt was made in #670, but it proved to have some subtle bug in #783 and had to be reverted. It would be nice to fix and reinstate.

jwaldmann commented 2 years ago

I'm on it. First step is to trigger the bug in testing. I made an Arbitrary instance that produces larger numbers https://github.com/jwaldmann/containers/commit/80af818e01a0b0579a08e6091b1bab3cd6ebbdb1 (this may be generally useful?) and then indeed I am seeing the mis-behaviour with

stack  test :intset-properties --ta '-t instance'  --ta '-a 100000'

I will next look into a proposed fix https://github.com/jwaldmann/containers/commit/259b737c883e447f8f8adebe3ae55cfd7d56fbac but it's not working as-is.

jwaldmann commented 2 years ago

This Large generator already exists (https://hackage.haskell.org/package/QuickCheck-2.14.2/docs/Test-QuickCheck.html#t:Large) so I am using that 7d89135c95b0367d7f1ff367ad92d467ded4cee3 . All intset-properties look good - except for the Ord-related ones. An example is

prop_instanceOrdIntSet: [Failed]
*** Failed! Falsified (after 6487 tests):
fromList [8614693178962916916,9139268739591489368]
fromList [2968846309351689790,4115242320062133052,8853465997820928815]
(used seed 4781226516308396838)

this is probably related to some overflow that changes the sign.

Yes - 182b06bdbdd07aae62fdf96a312131e9a89419d2 looks good now.

jwaldmann commented 2 years ago

How should I proceed here? I think the issue is fixed. Rebase the fix on #788?

treeowl commented 2 years ago

Weren't you trying to fix the clever instance?

jwaldmann commented 2 years ago

I think I did ( https://github.com/haskell/containers/blob/182b06bdbdd07aae62fdf96a312131e9a89419d2/containers/src/Data/IntSet/Internal.hs#L1217 ) I'm just asking how you want the PR.

treeowl commented 2 years ago

I feel like there's some communication issue going on here, but I'm confused as to who doesn't understand whom and why. Yes, I'd expect you to rebase your improvement branch on master and submit a PR, but if you have other intentions just explain again please.

jwaldmann commented 2 years ago

Sorry for being not clear. I was waiting for #788 to land. It is orthogonal in the source - the connection is that it would have caught the bug in this "clever" instance. Anyway I will base on (current) master.