Recently, me and John Hughes have been working on different approaches to do mutation testing on Haskell code. John is co-author of QuickCheck and we thought of making the same tool for automating mutation testing to some extent. I loaded up emacs and here is my first attempt to develop QuickMutate…
First, let me start by quoting from Wikipedia on mutation testing: "Mutation testing involves modifying a program’s source code or byte code in small ways." The mutations should not break the execution and therefore the mutated programs should pass the type checking. So, I grabbed a version of HTE available online and installed it with Cabal.
> module Test.QuickMutate where
>
> import Language.Haskell.THIH.Typecheck.Load
> import Language.Haskell.THIH.Typecheck.Types hiding (Module)
> import Language.Haskell.Exts.FromTHIH
> import Language.Haskell.Exts hiding (Name)
> import Data.List
Since it is needed to mutate and change different parts of the program, I decided to use Uniplate to do the generics.
> import Data.Generics.Uniplate.Data
Also, it is required to typecheck all of the mutated programs without interruptions, therefore, I used the following hack:
> import Control.DeepSeq
> import System.IO.Unsafe
> import Control.Exception as CE
>
> tcHSE :: Module -> Maybe String
> tcHSE ast = unsafePerformIO $
> CE.catch
> (let x = show $ tcHSEModuleWithPrelude ast
> in deepseq x (return $ Just x))
> ((\_ -> return Nothing)
> :: (SomeException -> IO (Maybe a)))
For automating mutation testing, we need a database of mutation operators. It can be modeled as a list of pairs of names (quantified).
> type MutationOps = [(QName,QName)]
Therefore, the mutating function takes the database of mutation operators and the program and generates the mutated programs.
> mutate :: MutationOps -> Module -> [Module]
As the first step, I defined the transformations using Uniplate:
> mutateE :: (QName , QName) -> Exp -> Exp
> mutateE p e = transformBi (mutateQ p) e
>
> mutateQ :: (QName , QName) -> QName -> QName
> mutateQ (op,op') x
> | x == op = op'
> | otherwise = x
>
> mutate dic m = let
> ms' = [transformBi (mutateE pair) m | pair <- dic]
> -- ...
Then, I used HTE to infer the type of the original program and all the mutated programs. Finally, I filtered out mutated programs with bad types, types different from the original type and duplications.
> -- ...
> Just ty = tcHSE m
> ms'' = filter ( \ m'-> Just ty == tcHSE m') ms'
> in (nub (m : ms'') )
To make it easier to play with the code, I made a front-end that takes string instead of AST.
> mutateStr :: [(String,String)] -> String -> [String]
> mutateStr dic inp = let
> ParseOk m = parseModule inp
> in map prettyPrint $ concat $ map getDecl
> $ mutate [(toQn x ,toQn y ) | (x,y) <- dic] m
> where
> toQn :: String -> QName
> toQn inp = let ParseOk (Var m ) = parseExp inp in m
>
> getDecl :: Module -> [Decl]
> getDecl(Module _ _ _ _ _ _ dcs) = dcs
Then I started to test.
Testing if it actually does the mutation where it should:
> test_new = mutateStr [("(+)","(-)")] "f x = x + x"
ghci> test_new
["f x = x + x","f x = x - x"]
Testing if it accepts a mutation that results in valid, yet different type:
> test_wrong = mutateStr [("(+)","(++)")] "f x = x + x"
ghci> test_wrong
["f x = x + x"]
Testing if it accepts a mutation that does not typecheck:
> test_bad = mutateStr [("(+)","f")] "f x = x + x"
ghci> test_bad
["f x = x + x"]
Testing if it removes duplications:
> test_dup = mutateStr [("(-)","(+)")] "f x = x + x"
ghci> test_dup
["f x = x + x"]
So far it behaves as expected. Of course, there is much more left to do; this is just the beginning!
