File size: 6,425 Bytes
5316c4e
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
-- SPDX-License-Identifier: AGPL-3.0-or-later

-- | The test harness every package uses.
--
-- A test carries a conformance ID. The gate reads those IDs out of the test
-- sources and requires a bijection with @model/ids.toml@ (R3), so the tag is
-- not decoration: it is how a claim is tied to the code that discharges it.
--
-- There is no shrinking. A failing case is reported with the seed and case
-- number that reproduce it, which is enough to debug and keeps the harness
-- small enough to read in one sitting.
module MP.Check
  ( -- * Generators
    Gen
  , runGen
  , integerIn
  , intIn
  , elements
  , listOfLength
  , listUpTo
  , boolG
  , rationalIn
    -- * Results
  , Result
  , pass
  , failWith
  , assert
  , (===)
  , (=/=)
  , allOf
  , (.&&.)
    -- * Tests
  , Test
  , unit
  , prop
  , propN
  , unitIO
  , runSuite
  , checkProperty
  ) where

import Control.Monad (ap, liftM, replicateM)
import Data.IORef (modifyIORef', newIORef, readIORef)
import Data.List (intercalate)
import Data.Ratio ((%))
import Data.Word (Word64)
import MP.Check.Random
import System.Environment (getArgs)
import System.Exit (exitFailure)
import System.IO (hSetEncoding, stdout, utf8)
import Text.Read (readMaybe)

------------------------------------------------------------------------------
-- Generators

newtype Gen a = Gen (Seed -> (a, Seed))

runGen :: Gen a -> Seed -> (a, Seed)
runGen (Gen f) = f

instance Functor Gen where fmap = liftM

instance Applicative Gen where
  pure x = Gen (\s -> (x, s))
  (<*>) = ap

instance Monad Gen where
  Gen f >>= k = Gen (\s -> let (a, s') = f s in runGen (k a) s')

-- | Uniform in the closed interval; an empty interval yields its lower bound.
integerIn :: Integer -> Integer -> Gen Integer
integerIn lo hi
  | hi <= lo = pure lo
  | otherwise = Gen (\s -> let (x, s') = boundedBelow (hi - lo + 1) s in (lo + x, s'))

intIn :: Int -> Int -> Gen Int
intIn lo hi = fromInteger <$> integerIn (toInteger lo) (toInteger hi)

boolG :: Gen Bool
boolG = (== 1) <$> integerIn 0 1

-- | Pick from a non-empty list given as head and tail, so it cannot be called
-- on an empty one.
elements :: a -> [a] -> Gen a
elements x xs = do
  i <- intIn 0 (length xs)
  pure (pick i (x : xs))
  where
    pick _ [] = x
    pick 0 (y : _) = y
    pick k (_ : ys) = pick (k - 1 :: Int) ys

listOfLength :: Int -> Gen a -> Gen [a]
listOfLength = replicateM

listUpTo :: Int -> Gen a -> Gen [a]
listUpTo n g = intIn 0 n >>= \k -> listOfLength k g

-- | A rational with numerator in the given range and denominator in [1, d].
rationalIn :: Integer -> Integer -> Integer -> Gen Rational
rationalIn lo hi d = do
  p <- integerIn lo hi
  q <- integerIn 1 (max 1 d)
  pure (p % q)

------------------------------------------------------------------------------
-- Results

-- | Either a pass or the list of reasons it failed.
newtype Result = Result [String]

instance Semigroup Result where Result a <> Result b = Result (a <> b)

instance Monoid Result where mempty = pass

pass :: Result
pass = Result []

failWith :: String -> Result
failWith msg = Result [msg]

assert :: String -> Bool -> Result
assert msg ok = if ok then pass else failWith msg

infix 4 ===, =/=
infixr 3 .&&.

-- | Conjunction of results. It binds looser than '===', so
-- @a === b .&&. c === d@ reads the way it looks; '<>' would not.
(.&&.) :: Result -> Result -> Result
(.&&.) = (<>)

(===) :: (Eq a, Show a) => a -> a -> Result
a === b = assert ("expected " <> show b <> ", got " <> show a) (a == b)

(=/=) :: (Eq a, Show a) => a -> a -> Result
a =/= b = assert ("expected a value other than " <> show b) (a /= b)

allOf :: [Result] -> Result
allOf = mconcat

------------------------------------------------------------------------------
-- Tests

data Body
  = Unit Result
  | UnitIO (IO Result)
  | forall a. Show a => Prop Int (Gen a) (a -> Result)

data Test = Test String String Body

-- | A deterministic check. The first argument is the conformance ID.
unit :: String -> String -> Result -> Test
unit i n r = Test i n (Unit r)

unitIO :: String -> String -> IO Result -> Test
unitIO i n r = Test i n (UnitIO r)

-- | A property over 200 generated cases.
prop :: Show a => String -> String -> Gen a -> (a -> Result) -> Test
prop i n = propN i n 200

propN :: Show a => String -> String -> Int -> Gen a -> (a -> Result) -> Test
propN i n k g p = Test i n (Prop k g p)

runOne :: Word64 -> Test -> IO (Maybe String)
runOne seed (Test i n body) = do
  outcome <- case body of
    Unit (Result []) -> pure Nothing
    Unit (Result es) -> pure (Just (intercalate "; " es))
    UnitIO act -> do
      Result es <- act
      pure (if null es then Nothing else Just (intercalate "; " es))
    Prop k g p -> pure (checkProperty k g p seed)
  putStrLn (maybe "  ok   " (const "  FAIL ") outcome <> "[" <> i <> "] " <> n)
  pure ((\e -> "[" <> i <> "] " <> n <> "\n      " <> e) <$> outcome)

-- | Evaluate a property on @k@ generated cases; the first failure, described,
-- or 'Nothing'. Pure, so the harness's own tests can run it.
checkProperty :: Show a => Int -> Gen a -> (a -> Result) -> Word64 -> Maybe String
checkProperty k g p seed = go 0 (mkSeed seed)
  where
    go c s
      | c >= k = Nothing
      | otherwise =
          let (s1, s2) = splitSeed s
              (x, _) = runGen g s1
           in case p x of
                Result [] -> go (c + 1) s2
                Result es ->
                  Just
                    ( "case " <> show c <> " of " <> show k <> " (seed " <> show seed <> "): "
                        <> show x <> "\n      " <> intercalate "; " es
                    )

-- | Run every test, print a line per test, exit non-zero if any failed.
-- Pass @--seed N@ to reproduce a reported failure.
runSuite :: String -> [Test] -> IO ()
runSuite name tests = do
  hSetEncoding stdout utf8 -- test names are UTF-8 whatever the locale says
  args <- getArgs
  let seed = case args of
        ["--seed", s] | Just v <- readMaybe s -> v
        _ -> 0x5eed
  putStrLn (name <> " (seed " <> show seed <> ")")
  failures <- newIORef []
  mapM_ (\t -> runOne seed t >>= maybe (pure ()) (\f -> modifyIORef' failures (f :))) tests
  fs <- readIORef failures
  if null fs
    then putStrLn ("  " <> show (length tests) <> " passed")
    else do
      putStrLn ("\n" <> show (length fs) <> " of " <> show (length tests) <> " failed:")
      mapM_ (putStrLn . ("  " <>)) (reverse fs)
      exitFailure