meze

‖meze (ˈmeɪzeɪ) Also mese, mezée, mezze, mezzeh. [Turk. meze snack, appetizer.] A type of hors-d’œuvre served esp. with an aperitif in Greece and the Near East. (OED2)

Meze is a very stupid mutation analyser for R6RS-style Scheme running under Chez Scheme.

It is stupid for two reasons: the first and main one is because it does not know about your macros (unless, I guess, you hack the script to tell it about them), nor about the possibility that syntactic keywords may have been lexically rebound. It treats all input Scheme code as if all the keywords it knows about have their usual bindings everywhere and are only used like normal Scheme code is used; also, it expects that some core Scheme bindings such as lambda, if, not etc. are imported and have their usual bindings, for use in its mutations. (A ‘smart’ mutation analyser integrated with a macro expander, without these limitations, would be an interesting project for someone else.)

The other reason it’s stupid is that it’s very user-unfriendly; basic configuration currently requires hacking the source code. A future version might be more friendly to extension by users, to help it understand the macros you wrote yourself, and more user-friendly in general. This would turn it from very stupid to merely normally stupid.

Installation

Compile meze.c to a dynamically-linkable library file called meze.c.so using whatever command is appropriate for your local operating system. This section of the Chez Scheme manual may be helpful.

Use

./meze project-dir target-file test-suite-script

project-dir is the directory containing all the files for the project that will be analysed.

target-file is the Scheme file within that directory (relative path only) which will have mutation tests run against it.

test-suite-script is a shell command (as a single argument to the meze script) which will be run to see if the test suite handles a particular mutation. There is technically no requirement that this run Chez Scheme: the only requirement really is that Chez’s reader is able to understand your source code, but you could in theory use Meze to mutation test code for other Scheme implementations. (In any case, the shell command should almost certainly begin with the word exec.)

During operation, the entire project-dir is copied to a new temporary directory. The file target-file is repeatedly overwritten with source code containing successive new mutations, and the test suite script is run (with the temporary directory as the current working directory) each time. The test suite script must exit 0 if the test suite ran successfully, or some other exit status if there was a compilation error or any test failed. If the test suite script takes more than a certain amount of time (currently 3 seconds), Meze assumes that the mutation caused an infinite loop (for example because it changed the index advance on a vector iteration from (+ idx 1) to (* idx 1) or (+ idx 0)) and considers it equivalent to a test failure.

Meze expects that any random change to the source code will cause either a compilation error or a test failure. If a mutation causes neither, Meze will tell you what it changed in the target file and where. Sometimes multiple mutations will have the same logical effect; just because you got n mutations which caused no test failures, doesn’t mean you need to add n new tests. Sometimes it’s fine for a mutation to have no effect on tests. Use your brain.

Currently implemented mutations

Mutations selected based on those which seem to be most successful in Scheme-like languages, according to the literature, plus a few more I’m trying out.

• change-arithmetic-operator: swaps +, -, /, and * with one another
• invert-predicate: replaces any identifier ending with ? with an inverted version of itself
• and->or, or->and: replaces and with or and vice-versa
• truncate-and, truncate-or: removes clauses from the end of and and or, e.g. (and a b c d) will be replaced with (and a), (and a b), (and a b c)
• if-always, if-never, cond-always, cond-never: replaces the test clause in if with #f or #t
• if-invert, cond-invert: wraps the test clauses of if and cond in a (not ...)
• change-numeric-literal: changes a numeric literal n to 0, 1, -1, 1.0 (inexact), -1.0 (inexact), n+1, n-1, and -n
• list->null: changes any literal list or invocation of the list function to an empty list
• invert-boolean-literal: changes #t to #f and vice-versa
• delete-syntax-rules-literals, delete-syntax-case-literals: delete one literal at a time from a syntax-rules or syntax-case expression
• delete-syntax-rules-clauses, delete-syntax-case-clauses: delete one clause at a time from a syntax-rules or syntax-case expression
• delete-syntax-case-fenders: delete the fenders from syntax-case clauses
• delete-library-exports: delete one export at a time from a library
• delete-library-imports: delete one import at a time from a library
• delete-library-imports/only: delete one import at a time from the only clause of a library import (NB will actually identify any expression called only followed by something that looks vaguely like a library name)

Semi-deliberately not implemented:

• Switching left to right fold operators and vice versa – the false positive rate apparently too high due to widespread use of associative operators in folds. The fold argument order issue is also a problem
• Changing the order of syntax-rules and syntax-case clauses. In the general case the number of orderings grows factorially, and in instances where order is not significant, this would generate a huge number of spurious surviving mutations. Once there is a way to select which mutators to activate this may be implemented, but turned off by default.

Coming soon:

• Changing the order of arguments to append (likely just swapping adjacent arguments)
• Replacing a call to cons with one of its arguments
• Deleting arguments from list and cons*
• Switching around <, <=, =, >=, and >. I want to do this for the numeric versions and for any identifier matching the pattern of e.g. char<?
• Deleting accessor and mutator procedures from define-record-type

Reading material

Duc et al., ‘MuCheck: An Extensible Tool for Mutation Testing of Haskell Programs’ (ISSTA 2014 pp. 429–32)

Zhuang et al., ‘A Tool for Mutation Analysis in Racket’ (IEEE ICSTW 2023, pp. 308–13)