Test suite

[Gabriella439]

pipes needs a QuickCheck test suite for those who don't trust my equational reasoning skills. The ideal things to test are laws like category laws and functor laws which are documented throughout the code base although other miscellaneous tests would be useful, too.

This will require bumping the minimum cabal version to > = 1.9.2, but that's okay.

[archblob]

I want to do this if nobody else has started and if there's no hurry.

[Gabriella439]

Yeah, I would be happy if you took this up. Right now I am working on proving the laws using Agda to complement this, and it would be nice to have both.

[archblob]

Oh, I would be very interested to read about that once you are done.

[dag]

I test the Category and Monoid laws for my path package here. It would be harder to exhaustively test pipes like this though because its categories are open-kinded. This could be solved either by simply testing against some fixed Arbitrary instance, or we could generate the code to test the properties with every instance like I did for SafeCopy here.

[archblob]

I've got a free weekend and I will start working on this, but before I do I would like to ask what do you think would be the best approach in generating the test data and writing the Arbitrary instances ?

[Gabriella439]

I think the best we can do is feed the test pipes using each xs, where xs is an Arbitrary list. I don't know of an easy way to do Arbitrary instances for the Proxy type.

[archblob]

I was asking this because I remember a thread on reddit where you said that all the problems you observed where in situations where you use some combination of yield and await, but I see how trying to write an Arbitrary instance for Proxy can give you headaches.

[Gabriella439]

We can do a mix of both property-based testing and single case testing, too. If you give me some time I can produce some specific cases that have historically been very good at catching category law violations.

[archblob]

Well I'll work on the test suite this weekend and submit it for review and discussions and we can add those specific cases later.

[Gabriella439]

Alright, that sounds good.

[Gabriella439]

Ok, I figured it out! I found a way to create Arbitrary instances for Servers, Clients, and Proxys. I'll first paste the code and then explain how it works:

import Control.Monad ((>=>))
import Control.Monad.Trans.Writer (Writer, runWriter, tell)
import Data.List (intercalate)
import Pipes
import Pipes.Core
import Test.QuickCheck

import Prelude hiding (log)

-- My QuickCheck version doesn't have this function, yet
arbitraryBoundedEnum' :: (Bounded a, Enum a) => Gen a
arbitraryBoundedEnum' =
  do let mn = minBound
         mx = maxBound `asTypeOf` mn
     n <- choose (fromEnum mn, fromEnum mx)
     return (toEnum n `asTypeOf` mn)

data ClientStep
    = ClientRequest | ClientLog | ClientInc deriving (Enum, Bounded)

instance Arbitrary ClientStep where
    arbitrary = arbitraryBoundedEnum'
    shrink _  = []

instance Show ClientStep where
    show x = case x of
        ClientRequest -> "request"
        ClientLog     -> "log"
        ClientInc     -> "inc"

data ServerStep
    = ServerRespond | ServerLog | ServerInc deriving (Enum, Bounded)

instance Arbitrary ServerStep where
    arbitrary = arbitraryBoundedEnum'
    shrink _  = []

instance Show ServerStep where
    show x = case x of
        ServerRespond -> "respond"
        ServerLog     -> "log"
        ServerInc     -> "inc"

data ProxyStep
    = ProxyRequest | ProxyRespond | ProxyLog | ProxyInc deriving (Enum, Bounded)

instance Arbitrary ProxyStep where
    arbitrary = arbitraryBoundedEnum'
    shrink _  = []

instance Show ProxyStep where
    show x = case x of
        ProxyRequest -> "request"
        ProxyRespond -> "respond"
        ProxyLog     -> "log"
        ProxyInc     -> "inc"

log :: Int -> Proxy a' a b' b (Writer [Int]) Int
log n = do
    lift (tell [n])
    return n

inc :: (Monad m) => Int -> Proxy a' a b' b m Int
inc n = return (n + 1)

correct :: String -> String
correct str = case str of
    [] -> "return"
    _  -> str

newtype AClient = AClient { unAClient :: [ClientStep] }

instance Arbitrary AClient where
    arbitrary = fmap AClient arbitrary
    shrink = map AClient . shrink . unAClient

instance Show AClient where
    show = correct . intercalate " >=> " . map show . unAClient

aClient :: AClient -> Int -> Client Int Int (Writer [Int]) Int
aClient = foldr (>=>) return . map f . unAClient
  where
    f x = case x of
        ClientRequest -> request
        ClientLog     -> log
        ClientInc     -> inc

newtype AServer = AServer { unAServer :: [ServerStep] }

instance Arbitrary AServer where
    arbitrary = fmap AServer arbitrary
    shrink = map AServer . shrink . unAServer

instance Show AServer where
    show = correct . intercalate " >=> " . map show . unAServer

aServer :: AServer -> Int -> Server Int Int (Writer [Int]) Int
aServer = foldr (>=>) return . map f . unAServer
  where
    f x = case x of
        ServerRespond -> respond
        ServerLog     -> log
        ServerInc     -> inc

newtype AProxy = AProxy { unAProxy :: [ProxyStep] }

instance Arbitrary AProxy where
    arbitrary = fmap AProxy arbitrary
    shrink = map AProxy . shrink . unAProxy

instance Show AProxy where
    show = correct . intercalate " >=> " . map show . unAProxy

aProxy :: AProxy -> Int -> Proxy Int Int Int Int (Writer [Int]) Int
aProxy = foldr (>=>) return . map f . unAProxy
  where
    f x = case x of
        ProxyRequest -> request
        ProxyRespond -> respond
        ProxyLog     -> log
        ProxyInc     -> inc

What this essentially does is generate arbitrary proxies by creating arbitrary sequences of kleisli arrows chosen from a limited set of functions. For example, you can see what kinds of Proxys it generates using sample:

>>> sample (arbitrary :: Gen AProxy)
respond >=> respond
inc
respond >=> inc >=> respond >=> request
request >=> respond >=> log >=> respond >=> inc >=> log
inc >=> request
request >=> inc >=> inc >=> log >=> respond >=> request >=> request >=> log >=> respond >=> inc
log >=> request >=> request >=> log >=> log >=> log >=> log
log >=> inc >=> inc >=> inc >=> respond >=> respond >=> request >=> inc >=> request >=> respond
log >=> log >=> request
inc >=> respond >=> inc >=> inc

These are proxies that thread an Int throughout the entire computation. inc increases the current value of the Int and log stores the current value to a Writer [Int] base monad.

Once you have these instances in hand, it becomes very easy to test pipe laws using QuickCheck. Here is an example:

(*==*)
    :: (Int -> Effect (Writer [Int]) Int)
    -> (Int -> Effect (Writer [Int]) Int)
    -> Bool
p1 *==* p2 = f p1 == f p2
  where
    f p = runWriter (runEffect (p 0))

infix 4 *==*

main = quickCheck $ \p1' p2' p3' ->
    let p1 = aServer p1'
        p2 = aProxy  p2'
        p3 = aClient p3'
    in  p1 >+> (p2 >+> p3) *==* (p1 >+> p2) >+> p3

That then pass all the tests:

+++ OK, passed 100 tests.

If I test an obviously false law, it correctly finds the minimum violation:

main = quickCheck $ \p1' p2' p3' ->
    let p1 = aServer p1'
        p2 = aProxy  p2'
        p3 = aClient p3'
    in  p1 >+> ((inc >=> p2) >+> p3) *==* (p1 >+> p2) >+> p3

This produces the following minimum counterexample:

*** Failed! Falsifiable (after 4 tests and 4 shrinks):    
return
return
request

[archblob]

Oh, this looks great! I'll go through the code and then try and write down all the tests later today.

[Gabriella439]

I wanted to point out one more thing that I just noticed from trying out more test cases by hand. If you want to test things like the respond and request categories then sometimes you need to sandwich the pipe your are testing in between a client and server like this:

p1 >+> (p2 \>\ (p3 \>\ p4)) >+> p5 = p1 >+> ((p2 \>\ p3) \>\ p4) >+> p5

Other than that, though, it is pretty easy.

[Gabriella439]

Fixed by #98.