Opened 7 years ago

Closed 6 years ago

Last modified 4 years ago

#1032 closed bug (wontfix)

Test.QuickCheck.Batch overflow in length of tests

Reported by: gwright@… Owned by:
Priority: normal Milestone: Not GHC
Component: Compiler Version: 6.6
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Difficulty: Easy (less than 1 hour)
Test Case: Blocked By:
Blocking: Related Tickets:

Description

This problem was originally reported as bug #1004. There were
actually two issues, which are now bug #1013 and this one.

The following code fails (compiled and under ghci):

{-# OPTIONS_GHC -fglasgow-exts #-}
--
-- Checksum.hs, support for checksumming data.
--


--module Checksum (
--        checksum
--) where
module Main where

import Utils

import Control.Exception
import Data.Array
import Data.Bits
import Data.List
import Data.Word
import Test.QuickCheck
import Test.QuickCheck.Batch


crcTable :: Array Word8 Word16
crcTable = listArray (0, 255)
    [ 0x0000, 0x5935, 0xB26A, 0xEB5F, 0x3DE1, 0x64D4, 0x8F8B, 0xD6BE,
      0x7BC2, 0x22F7, 0xC9A8, 0x909D, 0x4623, 0x1F16, 0xF449, 0xAD7C,
      0xF784, 0xAEB1, 0x45EE, 0x1CDB, 0xCA65, 0x9350, 0x780F, 0x213A,
      0x8C46, 0xD573, 0x3E2C, 0x6719, 0xB1A7, 0xE892, 0x03CD, 0x5AF8,
      0xB63D, 0xEF08, 0x0457, 0x5D62, 0x8BDC, 0xD2E9, 0x39B6, 0x6083,
      0xCDFF, 0x94CA, 0x7F95, 0x26A0, 0xF01E, 0xA92B, 0x4274, 0x1B41,
      0x41B9, 0x188C, 0xF3D3, 0xAAE6, 0x7C58, 0x256D, 0xCE32, 0x9707,
      0x3A7B, 0x634E, 0x8811, 0xD124, 0x079A, 0x5EAF, 0xB5F0, 0xECC5,
      0x354F, 0x6C7A, 0x8725, 0xDE10, 0x08AE, 0x519B, 0xBAC4, 0xE3F1,
      0x4E8D, 0x17B8, 0xFCE7, 0xA5D2, 0x736C, 0x2A59, 0xC106, 0x9833,
      0xC2CB, 0x9BFE, 0x70A1, 0x2994, 0xFF2A, 0xA61F, 0x4D40, 0x1475,
      0xB909, 0xE03C, 0x0B63, 0x5256, 0x84E8, 0xDDDD, 0x3682, 0x6FB7,
      0x8372, 0xDA47, 0x3118, 0x682D, 0xBE93, 0xE7A6, 0x0CF9, 0x55CC,
      0xF8B0, 0xA185, 0x4ADA, 0x13EF, 0xC551, 0x9C64, 0x773B, 0x2E0E,
      0x74F6, 0x2DC3, 0xC69C, 0x9FA9, 0x4917, 0x1022, 0xFB7D, 0xA248,
      0x0F34, 0x5601, 0xBD5E, 0xE46B, 0x32D5, 0x6BE0, 0x80BF, 0xD98A,
      0x6A9E, 0x33AB, 0xD8F4, 0x81C1, 0x577F, 0x0E4A, 0xE515, 0xBC20,
      0x115C, 0x4869, 0xA336, 0xFA03, 0x2CBD, 0x7588, 0x9ED7, 0xC7E2,
      0x9D1A, 0xC42F, 0x2F70, 0x7645, 0xA0FB, 0xF9CE, 0x1291, 0x4BA4,
      0xE6D8, 0xBFED, 0x54B2, 0x0D87, 0xDB39, 0x820C, 0x6953, 0x3066,
      0xDCA3, 0x8596, 0x6EC9, 0x37FC, 0xE142, 0xB877, 0x5328, 0x0A1D,
      0xA761, 0xFE54, 0x150B, 0x4C3E, 0x9A80, 0xC3B5, 0x28EA, 0x71DF,
      0x2B27, 0x7212, 0x994D, 0xC078, 0x16C6, 0x4FF3, 0xA4AC, 0xFD99,
      0x50E5, 0x09D0, 0xE28F, 0xBBBA, 0x6D04, 0x3431, 0xDF6E, 0x865B,
      0x5FD1, 0x06E4, 0xEDBB, 0xB48E, 0x6230, 0x3B05, 0xD05A, 0x896F,
      0x2413, 0x7D26, 0x9679, 0xCF4C, 0x19F2, 0x40C7, 0xAB98, 0xF2AD,
      0xA855, 0xF160, 0x1A3F, 0x430A, 0x95B4, 0xCC81, 0x27DE, 0x7EEB,
      0xD397, 0x8AA2, 0x61FD, 0x38C8, 0xEE76, 0xB743, 0x5C1C, 0x0529,
      0xE9EC, 0xB0D9, 0x5B86, 0x02B3, 0xD40D, 0x8D38, 0x6667, 0x3F52,
      0x922E, 0xCB1B, 0x2044, 0x7971, 0xAFCF, 0xF6FA, 0x1DA5, 0x4490,
      0x1E68, 0x475D, 0xAC02, 0xF537, 0x2389, 0x7ABC, 0x91E3, 0xC8D6,
      0x65AA, 0x3C9F, 0xD7C0, 0x8EF5, 0x584B, 0x017E, 0xEA21, 0xB314 ]


-- | Compute our standard checksum
--
checksum :: [Word8] -> Word16
checksum msg =
        let
                update :: Word16 -> Word8 -> Word16
                update reg byte = (reg `shiftL` 8) `xor`
                                  crcTable ! ((fromIntegral (reg `shiftR` 8)) `xor` byte)
        in
                foldl' update 0 msg



-- | Tests
--
instance Arbitrary Word8 where
   arbitrary = 
      do n <- choose ((fromIntegral (minBound :: Word8)) :: Int, 
                      (fromIntegral (maxBound :: Word8)) :: Int)
         return (fromIntegral n)
   coarbitrary v = variant 0 . coarbitrary v


prop_checksum xs = checksum (xs ++ splitWord (checksum xs)) == 0
                   where types = xs :: [Word8]

testOpts = TestOptions {no_of_tests     = 1000,
                        length_of_tests = 3600,
                        debug_tests     = True}

batch = do
  result <- run prop_checksum testOpts
  case result of
    TestOk       _    i _ -> putStrLn ("test ok: " ++ show i)
    TestExausted _    i _ -> putStrLn ("test exhausted: " ++ show i)
    TestFailed   strs i   -> putStrLn ("test failed: " ++ concat strs)
    TestAborted  ex       -> putStrLn ("test aborted: " ++ show ex)

main = batch

it fails under ghci with

57:
[61,48,20]
58:
[80,90,202,253,203,52,183]
59:
[]
60:
[170,171,181,63,181,52,179,117]
61:
[56test aborted: <<loop>>
*Main>

As noted by Thorkil (see #1004), the problem is in the length_of_tests field.
This field is an Int, and is converted to microseconds by Test.QuickCheck?.Batch.run.
The conversion can overflow if length_of_tests is too large (a few thousand).

That this error is not detected is a bug. If the length_of_tests field is too
large, ghc should do one of: 1) terminate with an error; 2) throw an exception;
3) silently truncate to the maximum representable delay on the particular OS;
4) wrap around, setting the delay to the specified delay modulo the maximum
representable delay; or 5) do something better that someone else suggests.

If anyone has a good suggest, I will be happy to work up a patch based on it.
Otherwise, I'll pick one of 1) through 4).

Change History (7)

comment:1 Changed 7 years ago by thorkilnaur

Thanks a lot for taking the trouble to create this report. My suggestion for a solution would be for Test.QuickCheck.Batch.run to simply repeat the request to threadDelay a suitable number of times with maximum value, then a residual value for the last (and possibly only) delay. In this way, Test.QuickCheck.Batch.run never needs to report an error. I am a bit of an IO-idiot, so I cannot off-hand suggest actual QuickCheck code, but this simple idea would seem worthwhile and easy to implement.

comment:2 Changed 7 years ago by igloo

  • Milestone set to Not GHC

thorkilnaur's suggestion makes sense to me too.

comment:3 Changed 7 years ago by thorkilnaur

Or perhaps we might get a possibility of using longer delays: See #1324.

comment:4 Changed 6 years ago by igloo

  • Resolution set to wontfix
  • Status changed from new to closed

Please see
http://www.haskell.org/haskellwiki/Library_submissions
if you would like to propose an alternate interface.

comment:5 Changed 6 years ago by simonmar

  • Architecture changed from Multiple to Unknown/Multiple

comment:6 Changed 6 years ago by simonmar

  • Operating System changed from Multiple to Unknown/Multiple

comment:7 Changed 4 years ago by simonmar

  • Difficulty changed from Easy (1 hr) to Easy (less than 1 hour)
Note: See TracTickets for help on using tickets.