Test failures with `-fdebug`

[sjakobi]

Test suite hashset-properties: RUNNING...
...
filter:
  filter: [Failed]
*** Failed! (after 4 tests and 3 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[K {unK = 1},K {unK = 3}]
(used seed 4720166718959071150)

Test suite hashmap-lazy-properties: RUNNING...
...
filter:
  filter: [Failed]
*** Failed! (after 7 tests and 4 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},3),(K {unK = 1},1)]
(used seed 3871391983028917603)
  filterWithKey: [Failed]
*** Failed! (after 6 tests and 4 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},1),(K {unK = 2},3)]
(used seed -189164877360300385)
  mapMaybe: [Failed]
*** Failed! (after 7 tests and 5 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},1),(K {unK = 1},1)]
(used seed 1384504261181191328)
  mapMaybeWithKey: [Failed]
*** Failed! (after 8 tests and 4 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},3),(K {unK = 6},7)]
(used seed 6254909653662964961)

Test suite hashmap-strict-properties: RUNNING...
...
filter:
  filter: [Failed]
*** Failed! (after 10 tests and 9 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},1),(K {unK = 1},3)]
(used seed -1272663384097939588)
  filterWithKey: [Failed]
*** Failed! (after 4 tests and 6 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 3},0),(K {unK = 0},1)]
(used seed -3347919173703349700)
  mapMaybe: [Failed]
*** Failed! (after 5 tests and 5 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 0},1),(K {unK = 1},1)]
(used seed -1232515895682970587)
  mapMaybeWithKey: [Failed]
*** Failed! (after 4 tests and 2 shrinks):
Exception:
  Data.HashMap.Internal.Array.cloneM_off: bounds error, offset -1, length 2
  CallStack (from HasCallStack):
    error, called at ./Data/HashMap/Internal/Array.hs:350:64 in unordered-containers-0.2.15.0-inplace:Data.HashMap.Internal.Array
[(K {unK = 2},1),(K {unK = 0},3)]
(used seed -3664992786517083878)

[sjakobi]

I can reliably reproduce the issue with

cabal test test:hashmap-strict-properties -fdebug --enable-tests --test-options "--maximum-generated-tests=1000 --select-tests=filter"

It seems that the issue was introduced in 8201efe – at least I can't reproduce it at the parent commit.

@treeowl Could you take a look?

[sjakobi]

So the relevant assertion seems to be this one, failing because (_off - 1) is -1.

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 348 to 350 in 1399eda

	cloneM :: MArray s a -> Int -> Int -> ST s (MArray s a)
	cloneM _mary@(MArray mary#) _off@(I# off#) _len@(I# len#) =
	CHECK_BOUNDS("cloneM_off", lengthM _mary, _off - 1)

This causes an error because CHECK_BOUNDS ensures that the offset is non-negative:

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 166 to 167 in 1399eda

	# define CHECK_BOUNDS(_func_,_len_,_k_) \
	if (_k_) < 0 || (_k_) >= (_len_) then error ("Data.HashMap.Internal.Array." ++ (_func_) ++ ": bounds error, offset " ++ show (_k_) ++ ", length " ++ show (_len_)) else

But why do we compute the offset as _off - 1 at all?! I suspect that the checks in cloneM were modeled after the checks in copyM, but probably never run.

unordered-containers/Data/HashMap/Internal/Array.hs

Lines 339 to 346 in 1399eda

	-- | Unsafely copy the elements of an array. Array bounds are not checked.
	copyM :: MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
	copyM !src !_sidx@(I# sidx#) !dst !_didx@(I# didx#) _n@(I# n#) =
	CHECK_BOUNDS("copyM: src", lengthM src, _sidx + _n - 1)
	CHECK_BOUNDS("copyM: dst", lengthM dst, _didx + _n - 1)
	ST $ \ s# ->
	case copyMutableArray# (unMArray src) sidx# (unMArray dst) didx# n# s# of
	s2 -> (# s2, () #)

So I guess the fix should be as simple as this:

 cloneM :: MArray s a -> Int -> Int -> ST s (MArray s a)
 cloneM _mary@(MArray mary#) _off@(I# off#) _len@(I# len#) =
-    CHECK_BOUNDS("cloneM_off", lengthM _mary, _off - 1)
+    CHECK_BOUNDS("cloneM_off", lengthM _mary, _off)
     CHECK_BOUNDS("cloneM_end", lengthM _mary, _off + _len - 1)
     ST $ \ s ->
     case cloneMutableArray# mary# off# len# s of

This patch does in fact fix the tests.

@treeowl, what do you think?

[sjakobi]

#331 includes the suggested fix.

[sjakobi]

@treeowl I'd like to fix this before cutting the next release. When do you think you could take a look?

[treeowl]

Tomorrow night.