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!