technology from back to front

Checking Squeak Quickly

The good fellows in Haskell land came up with a nice idea one day: instead of relying on a programmer writing well-thought out tests, with test data designed to flush out edge cases, they realised that people aren’t very good at finding bugs in their own code. The real world is too random, too crazy, to leave us alone. Things break in production for reasons we would never anticipate. So why don’t we, as part of our testing process, throw some randomness at our tests?

So that’s just what QuickCheck does. You specify a property – something you hold to be true for all your Foos – and QuickCheck will test your property by generating test cases. If it finds a counterexample, it figures out a minimal version of that counterexample and prints it out.

Good ideas tend to spread: JUnit 4.0 has @Theory annotations – tests that take a single parameter. You define a @DataPoint, and your test runner tests your theories against your supplied data source. QuickCheck’s also been ported to Scala, in the form of ScalaCheck.

So why shouldn’t Smalltalkers also have some fun?

We’re going to extend SUnit to support theories, and implement a fairly general generator framework.

SUnit finds its test cases through reflection – if a TestCase‘s selector starts with test, it’s a test. We’re going to take a different route. We’ll explicitly mark our tests as being tests by adding a <theory> or <theoryTaking: #aSymbol> pragma, or annotation:

TheoryTest >> aPassingTheoryPasses: anObject
    <theory>
    self assert: anObject == anObject.

The pragma <theoryTaking: #aSymbol> indicates that we want a particular kind of data. #aSymbol is any class name. Pragmas are less capable than Java or C# annotations. They’re syntax, rather than arbitrary classes, and are purely metadata. You can’t compute anything with a pragma. Any parameters to a pragma may only be a literal.

This theory indicates a property shared by all trees, and shows how we declare that we want a particular kind of data:

TreeTheories >> aTreeHeightIsNeverMoreThanItsNumberOfNodes: aTree
    <theoryTaking: #Tree>
    self assert: aTree height <= aTree size.

On to how to get our generated test cases. Smalltalk is dynamically typed, so given some theory, it’s a lot of work to figure out the type that that theory wants. (Or, it’s hard to type a method’s parameter.) In Haskell, QuickCheck can leverage the type system to do most of the work – type inference (unification) will figure out what instance of the Arbitrary typeclass to use. So we’ll settle for one of two options. <theoryTaking: #SomeClassName> means “this theory expects SomeClassNames passed to it”, and <theory> will mean “this theory expects anything”.

Putting random data into a test case raises an issue though. You write your theory. The runner finds some counterexample, and falsifies your theory. What value broke your test? Oh, dear. So, two things: we sometimes want to generate non-random data, at the least so that we can build the theory-running infrastructure, and we want to remember the counterexample.

The first of these problems, together with wanting to generate different kinds of data (integers, trees, etc.) sounds a lot like double dispatch. OK, let’s do that then:

Object >> dataFrom: aDataGenerator
    ^ aDataGenerator objectData.

Boolean >> dataFrom: aDataGenerator
    ^ aDataGenerator booleanData.

Integer >> dataFrom: aDataGenerator
    ^ aDataGenerator integerData.

TrivialDataGenerator >> booleanData
    ^ true.

TrivialDataGenerator >> integerData
    ^ 1.

TrivialDataGenerator >> objectData
    ^ self.

Obviously we’d want more kinds of data, and we’d want different generators too. What we have here is sufficient for our initial explorations.

On to the second problem, recording our counterexample. First, some SUnit background. The SUnit TestRunner builds a suite of TestCases, Commands representing the execution of a single test. Tests, as mentioned above, are methods on a TestCase, so a TestCase represents two things – a collection of tests, and the desire to run one of those tests in a TestRunner. A TestRunner executes the TestCase Command by sending it the #runCase message which, in turn, results in a self-sent performTest. performTest simply hides away the details of running a particular test case while runCase manages the execution: setting up and tearing fixtures, and the like.

Our TheoryTestCase, in the interests of not being surprising, will support both the usual SUnit style tests, as well as theories. Since the former are nullary message sends while the latter are unary, we’ll need to distinguish between the two. Let’s add a query method #runningATheory:

TestCase subclass: #TheoryTestCase
    instanceVariableNames: 'currentExample'

TheoryTestCase >> runningATheory
    ^ testSelector numArgs = 1.

testSelector

is just the name of the test/theory.

TheoryTestCase >> runCase
    "If counterExample is NotAssigned, then we're running the test for
     the first time. Otherwise, it contains the value of a
     counterexample to our theory. Run the test using this value."

    | prototype |
    self runningATheory ifFalse: [^ super runCase].
       
    (currentExample = NotAssigned)
        ifTrue: [        
            prototype := self makeTestPrototype.
            1 to: testRunSize do: [:i |
                currentExample := prototype dataFrom: generator.
                "A TestFailure, or a timeout, will break out of the loop,
                 storing the last used value."

                [super runCase]
                    on: TestFailure do: [:e |
                        self
                            generateTestCase: testSelector
                            withCounterexample: currentExample.
                        e signal]]]
        ifFalse: [super runCase]

TheoryTestCase >> performTest
    ^ (self runningATheory)
        ifTrue: [self performTest: currentExample]
        ifFalse: [super performTest]

In particular, when a test is rerun – we have a counterexample to our theory – we will execute super runCase which will call self performTest… which will call self performTest: currentExample.

Two extra details: #makeTestPrototype makes an instance of whatever type the theory takes, and #generateTestCase:withCounterexample: adds a new method to the TheoryTestCase. So given a theory like

TheoryTest >> aFailingTheoryFails: anObject
    <theory>
    self deny: anObject == anObject.

run with our TrivialDataGenerator, we will see the theory fail. When we try rerun that test, the counterExample is set to the datum that falsifies the theory, and we can debug as per usual. Too, the TheoryTestCase has a record of the failure:

TheoryTest >> testAFailingTheoryFailsWith1
    "A test case auto-generated by SqueakCheck."
    self aFailingTheoryFails: 1

Having the environment’s compiler readily available can be very handy!

And, as always, the load script:

Installer ss
    project: 'SqueakCheck';
    install: 'SqueakCheck-Info';
    install: 'SqueakCheck-Generators';
    install: 'SqueakCheck-SUnit';
    install: 'SqueakCheck-Runners'.

"If you'd like to see more complex examples, run the below:"
Installer ss
    project: 'Nutcracker';
    install: 'AlgebraicDataType'.
       
Installer ss
    project: 'SqueakCheck';
    install: 'SqueakCheckForAlgebraicDataType'.
by
Frank Shearar
on
13/09/11
  1. [...] data is hard coded, nothing prevent from adopting an approach as suggested by Frank Shearar in his Squeak Check project. Method that return the array of parameters can rely on any arbitrary complex data generator class, [...]

 
 


6 − = one

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us