Fox Documentation¶

Shrinking Failures¶

The benefit of Fox over purely random data generation is Shrinking. An informed random generation is done by size. This allows the tool to reduce the counter-example to a smaller data set without having a user manually separate thes signal from the noise in the randomly generated data.

For example, if a sort() implementation failed with an exception when reading 9s. Fox could generate this value to provoke the failure:

xs = @[@1, @5, @9, @3, @5] // fails

And then proceed to shrink xs by trying smaller permutations:

xs = @[@5, @9, @3, @5] // still fails
xs = @[@9, @3, @5] // fails
xs = @[@3, @5] // passed
xs = @[@9, @5] // fails
xs = @[@9] // fails

Fox does this automatically whenever a failure occurs. This is valuable instead of having to manually debug a failure when random data generation is used.

Ready to get started? Install Fox.

Manually (Git Submodule)¶

Add Fox as a submodule to your project:

$ git submodule add https://github.com/jeffh/Fox.git Externals/Fox

If you don’t want bleeding edge, check out the particular tag of the version:

$ cd Externals/Fox
$ git checkout v1.0.0

Add Fox.xcodeproj to your Xcode project (not Fox.xcworkspace). Then link Fox-iOS or Fox-OSX to your test target.

Fox uses C++, so you’ll need to tell the linker of your test target (in Build Settings):

Other Linker Flags: -l”c++”

And you’re all set up! Dive right in by following the tutorial.

CocoaPods¶

Add to your Podfile for you test target to have the latest stable version of Fox:

pod 'Fox', '~>1.0.0'

And then pod install.

And you’re all set up! Dive right in by following the tutorial.

Carthage¶

TODO

Starting with an Example¶

Throughout this tutorial, we’ll cover the basics of writing property tests. To better understand property tests, let’s start with some example-based ones first:

- (void)testSort {
    NSArray *sortedNumbers = [MySorter sortNumbers:@[@5, @2, @1]];
    XCTAssertEqualObjects(sortedNumbers, @[@1, @2, @5]);
}

This is a simple example test about sorting numbers. Let’s break down parts of this test and see how Fox rebuilds it up:

- (void)testSort {
    // inputs
    NSArray *input = @[@5, @2, @1];
    // behavior to test
    NSArray *sortedNumbers = [MySorter sortNumbers:input];
    // assertion
    XCTAssertEqualObjects(sortedNumbers, @[@1, @2, @5]);
}

Fox takes these parts and separates them.

• Inputs are produced using generator. Generators describe the type of data to generate.
• Behavior to test remains the same.
• The assertion is based on logical statements of the subject and/or based on the generated inputs. The assertions as usually describe properties of the subject under test.

Let’s see how we can convert them to Fox property tests.

Converting to a Property¶

To convert the sort test into the given property, we describe the intrinsic property of the code under test.

For sorting, the resulting output should have the smallest elements in the start of the array and every element afterwards should be greater than or equal to the element before it:

- (void)testSortBySmallestNumber {
    id<FOXGenerator> arraysOfIntegers = FOXArray(FOXInteger());
    FOXAssert(FOXForAll(arraysOfIntegers, ^BOOL(NSArray *integers) {
        // subject under test
        NSArray *sortedNumbers = [MySorter sortNumbers:integers];
        // assertion
        NSNumber *previousNumber = nil;
        for (NSNumber *n in sortedNumbers) {
            if (!previousNumber || [previousNumber integerValue] <= [n integerValue]) {
                previousNumber = n;
            } else {
                return NO; // fail
            }
        }
        return YES; // succeed
    }));
}

Let’s break that down:

• FOXInteger is a generator that describes how to produce random integers (NSNumbers).
• FOXArray is a generator that describes how to generate arbitrary arrays. It takes another generator as an argument. In this case, we’re giving it an integer generator to produce randomly sized array of random integers.
• FOXForAll defines a property that should always hold true. It takes two arguments, the generator to produce and a block on how to assert against the given generated input.
• FOXAssert is how Fox asserts against properties. It will raise an exception if a property does not hold. They’re part of Fox’s runner infrastructure.

The test can be read as:

Assert that for all array of integers named integer, sorting integers should produce sortedNumbers. sortedNumbers is an array where the first number is the smallest and subsequent elements are greater than or equal to the element that preceeds it.

Diagnosing Failures¶

The interesting feature of Fox occurs only when properties fail. Let’s write code that will fail the property we just wrote:

+ (NSArray *)sortNumbers:(NSArray *)numbers {
    NSMutableArray *sortedNumbers = [[numbers sortedArrayUsingSelector:@selector(compare:)] mutableCopy];
    if (sortedNumbers.count >= 5) {
        id tmp = sortedNumbers[0];
        sortedNumbers[0] = sortedNumbers[1];
        sortedNumbers[1] = tmp;
    }
    return sortedNumbers;
}

Some nefarious little code we added there! We run again we get to see Fox work:

Property failed with: ( 0, 0, 0, 0, "-1" )
Location:   // /Users/jeff/workspace/FoxExample/FoxExampleTests/FoxExampleTests.m:41
  FOXForAll(arraysOfIntegers, ^BOOL(NSArray *integers) {
   NSArray *sortedNumbers = [self sortNumbers:integers];
   NSNumber *previousNumber = ((void *)0);
   for (NSNumber *n in sortedNumbers) {
   if (!previousNumber || [previousNumber integerValue] <= [n integerValue]) {
   previousNumber = n;
   }
   else {
   return __objc_no;
   }
   }
   return __objc_yes;
   }
  );

RESULT: FAILED
 seed: 1417500369
 maximum size: 200
 number of tests before failing: 8
 size that failed: 7
 shrink depth: 8
 shrink nodes walked: 52
 value that failed: (
    "-3",
    "-3",
    1,
    "-2",
    "-7",
    "-5"
)
 smallest failing value: (
    0,
    0,
    0,
    0,
    "-1"
)

The first line describes the smallest failing example that failed. It’s placed there for convenience:

Property failed with: ( 0, 0, 0, 0, "-1" )

The rest of the first half of the failure describes the location and property that failed.

The latter half of the failure describes specifics on how the smallest failing example was reached:

• seed is the random seed that was used to generate the series of tests to run.
• maximum size is the maximum size hint that Fox used when generating tests. This is useful for reproducing test failures when pairs with the seed.
• number of tests before failing describes how many tests were generated before the failing test was generated. Mostly for technical curiosity.
• size that failed describes the size that was used to generate the original failing test case. The size dicates the general size of the data generated (eg - larger numbers and bigger arrays).
• shrink depth indicates how many “changes” performed to shrink the original failing test to produce the smallest one. Mostly for technical curiosity.
• shrink nodes walked indicates how many variations Fox produced to find the smallest failing test. Mostly for technical curiosity.
• value that failed the original generated value that failed the property. This is before Fox performed any shrinking.
• smallest failing value the smallest generated value that still fails the property. This is identical to the value on the first line of this failure description.

So what happened? Fox generates random data until a failure occurs. Once a failure occurs, Fox starts the shrinking process. The shrinking behavior is generator-dependent, but generally alters the data towards the “zero” value:

• For integers, that means moving towards 0 value.
• For arrays, each element shrinks as well as the number of elements moves towards zero.

Each time the value shrinks, Fox will verify it against the property to ensure the test still fails. This is a brute-force process of elimination is an effective way to drop irrevelant noise that random data generation typically produces.

Notice that the last element has significance since it failed to shrink all the way to zero like the other elements. It’s also worth noting that just because a value has been shrunk to zero doesn’t exclude it’s potential significance, but it is usually less likely to be significant. In this case, the second to last element happens to be significant.

Testing Stateful APIs¶

Now this is all well and good for testing purely functional APIs - where the same input produces the same output. What’s more interesting is testing stateful APIs.

Before we start, let’s talk about the conceptual model Fox uses to verify stateful APIs. We can model API calls as data using Fox’s generator system.

As a simple case, let’s test a Queue. We can add and remove objects to it. Removing objects returns the first item in the Queue:

• [queue add:1]
• [queue remove] // => returns 1
• [queue add:2]
• [queue add:3]
• [queue remove] // => returns 2
• [queue remove] // => returns 3

Just generating a series of API calls isn’t enough. Fox needs more information about the API:

• Which API calls are valid to make at any given point? This is specified in Fox as preconditions.
• What assertions should be after any API call? This is specified in Fox as postconditions.

This is done by describing a state machine. In basic terms, a state machine is two parts: state and transitions.

State indicates data that persists between transitions. Transitions describe how that state changes over time. Transitions can have prerequisites before allowing them to be used.

For this example, we can model the API as a state machine: with transitions for each unique API call, and its state representing what we think the queue should manage. In this case, we’ll naively choose an array of the queue’s contents as the state.

From there, Fox can generate a sequence of state transitions that conform to the state machine. This allows Fox to generate valid sequences of API calls.

We can translate the diagram into code by configuring a FOXFiniteStateMachine:

- (void)testQueueBehavior {
    // define the state machine with its initial state.
    FOXFiniteStateMachine *stateMachine = [[FOXFiniteStateMachine alloc] initWithInitialModelState:@[]];

    // define the state transition for -[Queue addObject:]
    // we'll only be using randomly generated integers as arguments.
    // note that nextModelState should not mutate the original model state.
    [stateMachine addTransition:[FOXTransition byCallingSelector:@selector(addObject:)
                                                withGenerator:FOXInteger()
                                                nextModelState:^id(id modelState, id generatedValue) {
                                                    return [modelState arrayByAddingObject:generatedValue];
                                                }]];

    // define the state machine for -[Queue removeObject]
    FOXTransition *removeTransition = [FOXTransition byCallingSelector:@selector(removeObject)
                                                        nextModelState:^id(id modelState, id generatedValue) {
                                                            return [modelState subarrayWithRange:NSMakeRange(1, [modelState count] - 1)];
                                                        }];
    removeTransition.precondition = ^BOOL(id modelState) {
        return [modelState count] > 0;
    };
    removeTransition.postcondition = ^BOOL(id modelState, id previousModelState, id subject, id generatedValue, id returnedObject) {
        // modelState is the state machine's state after following the transition
        // previousModelState is the state machine's state before following the transition
        // subject is the subject under test. You should not provoke any mutation changes here.
        // generatedValue is the value that the removeTransition generated. We're not using this value here.
        // returnedObject is the return value of calling [subject removeObject].
        return [[previousModelState firstObject] isEqual:returnedObject];
    };
    [stateMachine addTransition:removeTransition];

    // generate and execute an arbitrary sequence of API calls
    id<FOXGenerator> executedCommands = FOXExecuteCommands(stateMachine, ^id{
        return [[Queue alloc] init];
    });
    // verify that all the executed commands properly conformed to the state machine.
    FOXAssert(FOXForAll(executedCommands, ^BOOL(NSArray *commands) {
        return FOXExecutedSuccessfully(commands);
    }));
}

We can now run this to verify the behavior of the queue. This does take significantly more time that the previous example. But Fox’s execution time can be tweak if you want faster feedback versus a more thorough test run. See Configuring Test Generation.

Just to be on the same page, here’s a naive implementation of the queue that passes the property we just wrote:

@interface Queue : NSObject
- (void)addObject:(id)object;
- (id)removeObject;
@end

@interface Queue ()
@property (nonatomic) NSMutableArray *items;
@end

@implementation Queue

- (instancetype)init {
    self = [super init];
    if (self) {
        self.items = [NSMutableArray array];
    }
    return self;
}

- (void)addObject:(id)object {
    [self.items addObject:object];
}

- (id)removeObject {
    id object = self.items[0];
    [self.items removeObjectAtIndex:0];
    return object;
}

@end

To break this, let’s modify the queue implementation:

- (void)addObject:(id)object {
    if (![object isEqual:@4]) {
        [self.items addObject:object];
    }
}

Running the tests again, Fox shows us a similar failure like sort:

Property failed with: @[ [subject addObject:4] -> (null), [subject removeObject] -> (null) (Postcondition FAILED) Exception Raised: *** -[__NSArrayM objectAtIndex:]: index 0 beyond bounds for empty array Model before: ( 4 ) Model after: ( ), ]
Location:   // /Users/jeff/workspace/FoxExample/FoxExampleTests/FoxExampleTests.m:68
FOXForAll(executedCommands, ^BOOL(NSArray *commands) {
return FOXExecutedSuccessfully(commands);
}
);

RESULT: FAILED
seed: 1417510193
maximum size: 200
number of tests before failing: 13
size that failed: 12
shrink depth: 10
shrink nodes walked: 16
value that failed: @[
[subject addObject:-1] -> (null),
[subject addObject:-8] -> (null),
[subject addObject:4] -> (null),
[subject addObject:12] -> (null),
[subject removeObject] -> -1,
[subject addObject:4] -> (null),
[subject addObject:10] -> (null),
[subject removeObject] -> -8,
[subject removeObject] -> 12 (Postcondition FAILED)
    Model before: (
    4,
    12,
    4,
    10
)
    Model after: (
    12,
    4,
    10
),
]
smallest failing value: @[
[subject addObject:4] -> (null),
[subject removeObject] -> (null) (Postcondition FAILED)
    Exception Raised: *** -[__NSArrayM objectAtIndex:]: index 0 beyond bounds for empty array
    Model before: (
    4
)
    Model after: (
),
]

Here we can see the original generated test that provoked the failure:

• [subject addObject:-1]
• [subject addObject:-8]
• [subject addObject:4]
• [subject addObject:12]
• [subject removeObject] -> -1
• [subject addObject:4]
• [subject addObject:10]
• [subject removeObject] -> -8
• [subject removeObject] -> 12 (Postcondition FAILED)

That’s not as nice to debug as the test after shrinking:

• [subject addObject:4]
• [subject removeObject] -> (null) (Postcondition FAILED) - out of bounds exception raised.

You may be wondering why the removeObject call is still required. This is the only way assertions are made against the queue. Just calling addObject: doesn’t reveal any issues with an implementation.

And that’s most of the power of Fox. You’re ready to start writing property tests!

If you want read on, read more about the core of Fox’s design: Generators.

Building Custom Generators¶

It’s easy to compose the built-in generators to build generators for custom data types we have. Let’s say we want to generate random permutations of a Person class:

// value object. Implementation assumed
@interface Person : NSObject
@property (nonatomic, copy) NSString *firstName;
@property (nonatomic, copy) NSString *lastName;
@end

We can represent this Person data using by generating an array of values or dictionary of values. Here’s how it looks using a dictionary in an property assertion:

id<FOXGenerator> dictionaryGenerator = FOXDictionary(@{
    @"firstName": FOXAlphabeticalString(),
    @"lastName": FOXAlphabeticalString()
});
FOXAssert(FOXForAll(dictionaryGenerator, ^BOOL(NSDictionary *data) {
    Person *person = [[Person alloc] init];
    person.firstName = data[@"firstName"];
    person.lastName = data[@"lastName"];
    // assert with person
}));

But we want this to be reusable. Using FOXMap, we can create a new generator that is based on the dictionaryGenerator:

// A new generator that creates random person
id<FOXGenerator> AnyPerson(void) {
    id<FOXGenerator> dictionaryGenerator = FOXDictionary(@{
        @"firstName": FOXAlphabeticalString(),
        @"lastName": FOXAlphabeticalString()
    });
    return FOXMap(dictionaryGenerator, ^id(NSDictionary *data) {
        Person *p = [[Person alloc] init];
        p.firstName = data[@"firstName"];
        p.lastName = data[@"lastName"];
        return p;
    });
}

And we can then use is like any other generator:

FOXAssert(FOXForAll(AnyPerson(), ^BOOL(Person *person) {
    // assert with person
}));

You can see the reference for all the generators. Most common generators can be built from the provided mappers.

How Shrinking Works¶

Generators are just functions that accept a random number generator and a size hint as arguments and then return a rose tree of values.

Rose trees sound fancy, but they’re generic trees with an arbitrary number of branches. Each node in the tree represents a value. Fox generators create rose trees instead of individual values. This allows the runner to shrink the value by traversing through the children of the tree.

The main shrinking implementation Fox uses are for integers (via FOXChoose). For example, if a 4 was generated, the rose tree that FOXChoose generates would look like this:

The children of each node represents a smaller value that its parent. Fox will walk depth-first through this tree when a test fails to shrink to the smallest value.

Based on the diagram, the algorithm for shrinking integers prefers:

• Reducing to zero immediately
• Reducing to 50% of the original value
• Reducing the value by 1

This makes it more expensive to find larger integers (because of the redundant checking of zero), but it is generally more common to immediately shrink to the smallest value.

Writing Generators with Custom Shrinking¶

It is worth reading up on How Shrinking Works before proceeding.

Let’s write a custom integer generator that shrinks to 10 instead of zero. We won’t be using anything built on top of FOXChoose for demonstrative purposes, but we will be using Fox’s Debugging Functions.

Step one, we can easily always generate 10 by returning a child-less rose tree:

id<FOXGenerator> MyInteger(void) {
    FOXGenerate(^FOXRoseTree *(id<FOXRandom> random, NSUInteger size) {
        return [[FOXRoseTree alloc] initWithValue:@10];
    });
}

FOXGenerate is an easy way to create a generator without having to create an object that conforms to FOXGenerator. The block is the method body of the one method that the protocol requires.

This is, in fact, what FOXReturn does. However, we don’t get any randomness:

// FOXSample generates 10 random values using the given generator.
FOXSample(MyInteger()); // => @[@3];

So let’s use the random number generator provided. We’ll also use the size to dictate the size we want:

id<FOXGenerator> MyInteger(void) {
    FOXGenerate(^FOXRoseTree *(id<FOXRandom> random, NSUInteger size) {
        NSInteger lower = -((NSInteger)size);
        NSInteger upper = (NSInteger)size;
        NSInteger randomInteger = [random randomIntegerWithinMinimum:lower
                                                          andMaximum:upper];
        return [[FOXRoseTree alloc] initWithValue:@(randomInteger)];
    });
}

We now generate random integers! But we still don’t have any shrinking:

// Random integers
FOXSample(MyInteger());
// => @[@-30, @103, @188, @-184, @-22, @-118, @147, @-186, @-128, @-68]

// FOXSampleShrinking takes the first 10 values of the rose tree.
// The first value is the generated value. Subsequent values are
// shrinking values from the first one.
FOXSampleShrinking(MyInteger()) // => @[@-8]; there's no shrinking

Let’s add a simple shrinking mechanism, we can populate the children of the rose tree we return:

id<FOXGenerator> MyInteger(void) {
    FOXGenerate(^FOXRoseTree *(id<FOXRandom> random, NSUInteger size) {
        NSInteger lower = -((NSInteger)size);
        NSInteger upper = (NSInteger)size;
        NSInteger randomInteger = [random randomIntegerWithinMinimum:lower
                                                          andMaximum:upper];
        id<FOXSequence> children = [FOXSequence sequenceFromArray:@[[[FOXRoseTree alloc] initWithValue:@10]]];
        return [[FOXRoseTree alloc] initWithValue:@(randomInteger)
                                         children:children];
    });
}
// Shrinking once
FOXSampleShrinking(MyInteger()) // => @[@-8, @10];

Of course, we don’t properly handle shrinking for all variations. FOXSequence is a port of Clojure’s sequence abstraction. They provide opt-in laziness for Fox’s rose tree.

We’ll mimic the behavior of Fox’s integer shrinking algorithm:

• Shrink to 10.
• Shrink towards 10 by 50% of its current value.
• Shrink towards 10 by 1.

We’ll do this by defining functions to recursively create our rose tree:

// sequenceOfHalfIntegers(@14) -> SEQ(@14, @12, @11)
static id<FOXSequence> sequenceOfHalfIntegers(NSNumber *n) {
    if ([n isEqual:@10]) {
        return nil;
    }
    NSNumber *halfN = @(([n integerValue] - 10) / 2 + 10);
    return [FOXSequence sequenceWithObject:n
                         remainingSequence:sequenceOfHalfIntegers(halfN)];
}

sequenceOfHalfIntegers creates a sequence of integers that are half increments from n to 10 starting with n. nil is equivalent to an empty sequence. Next we define the children values:

// eg - sequenceOfSmallerIntegers(@14) -> SEQ(@10, @12, @13)
static id<FOXSequence> sequenceOfSmallerIntegers(NSNumber *n) {
    if ([n isEqual:@10]) {
        return nil;
    }
    return [sequenceOfHalfIntegers(n) sequenceByMapping:^id(NSNumber *m) {
        return @([n integerValue] - ([m integerValue] - 10));
    }];
}

sequenceOfSmallerIntegers creates a lazy sequence of values between n and 10 (including 10). Each element is (n - each half number difference to 10). Finally, we need to convert this sequence into a rose tree:

static FOXRoseTree *roseTreeWithInteger(NSNumber *n) {
    id<FOXSequence> smallerIntegers = sequenceOfSmallerIntegers(n);
    id<FOXSequence> children = [smallerIntegers sequenceByMapping:^id(NSNumber *smallerInteger) {
        return roseTreeWithInteger(smallerInteger);
    }];
    return [[FOXRoseTree alloc] initWithValue:n children:children];
}

sequenceOfSmallerIntegers creates a rose tree for a given number. The children are values from sequenceOfSmallerIntegers(n). The rose tree is recursively generated until sequenceOfSmallerIntegers returns an empty sequence (when the number is 10).

Finally, we wire everything together in our function that defines our generator:

id<FOXGenerator> MyInteger(void) {
    FOXGenerate(^FOXRoseTree *(id<FOXRandom> random, NSUInteger size) {
        NSInteger lower = -((NSInteger)size);
        NSInteger upper = (NSInteger)size;
        NSInteger randomInteger = [random randomIntegerWithinMinimum:lower
                                                          andMaximum:upper];
        return roseTreeWithInteger(@(randomInteger));
    });
}

Conceptually, our data pipeline looks like this:

Now we can generate values that shrink to 10! Obviously, this can be applied to more interesting shrinking strategies.

Configuring Test Generation¶

The primary operation of Fox’s runner is to create and executed tests. There are three primary parameters to configure Fox’s test generation:

• The seed allows you to seed the random number generator. This allows you to set the PRNG to help reproduce failures that Fox may have generated during a test run. Setting this to the default (0) will make Fox generate a seed based on the current time.
• The number of tests indicates the number of tests Fox will generate for this particular property. More tests generated will more thoroughly cover the property at the cost of time. Setting this to the default (0) will make Fox run 500 tests.
• The maximum size indicates the maximum size factor Fox will use when generating tests. Generators use this size factor as a hint to produce data of the appropriate sizes. For example, FOXInteger will generate integers within the range of 0 to maximumSize and FOXArray will generate arrays whose number of elements are in the range of 0 to maximumSize. Setting this to the default (0) will make Fox run with a maximumSize of 200. If you know this property’s data generation can tolerate larger sizes, feel free to increase this. Large collection generation can be prohibitively expensive.

Please note that seed, number of tests, and maximum size should all be recorded to reproduce a failure that Fox may have generated.

Per Assertion Configuration¶

By default, Fox will generate 500 tests per assertion with a maximum size of 200 and a random seed. By changing FOXAssert to FOXAssertWithOptions we can provide optional configuration by using the FOXOptions:

FOXAssertWithOptions(FOXForAll(...), (FOXOptions){
    seed=5,              // default: time(NULL)
    numberOfTests=1000,  // default: 500
    maximumSize=100,     // default: 200
});

Global Configuration¶

Values can be overridden using environment variables to globally change the defaults.

• Setting FOX_SEED can specify a specific seed to run for all properties.
• Setting FOX_NUM_TESTS sets the number of tests to generate for each property.
• Setting FOX_MAX_SIZE sets the maximum size factor Fox will use to when generating tests.

Random Number Generators¶

Random number generation controls how random number generation works in Fox. This is what generators receive as their first argument.

The runner uses FOXDeterministicRandom which uses C++ random by default. This keeps randomization state isolate from any other potential system that uses a global PRNG. But you can implement the FOXRandom protocol to support custom random schemes.

Another implementation Fox provides out of the box is FOXConstantRandom, which always generates a constant number. This can be useful for testing generators by example.

Reporters¶

The runner also provides a way to observe its operation via a reporter. Reporters are simply a the delegate to the runner. Reporters are invoked synchronously, so be careful about its performance impact on execution.

These delegates cannot influence the execution of the runner, but can provide useful user-facing output about the progress of Fox’s execution.

By default, Fox runners do not have a reporter assigned to it. But Fox does provide a couple reporters:

• FOXStandardReporter reports in a rspec-like dot reporter.
• FOXDebugReporter reports more information about the execution.

Data Generators¶

There are many data generators provided for generating data. Most of these generators shrink to zero:

• Numerically zero (or as close as possible)
• Empty collection (or at least shrunk items)

Computation Generators¶

Also, you can compose some computation work on top of data generators. The resulting generator adopts the same shrinking properties as the original generator.

Debugging Functions¶

Fox comes with a handful of functions that can help you diagnose generator problems.