Property-based testing

Using RapidCheck

Agenda

1. Introduction
2. Applications of property-based testing

Introduction

Another test philosophy

Some test strategies

Definition

Test properties instead of isolated cases

for all (x, y, ...)
such that precondition(x, y, ...) holds
property(x, y, ...) is true

How does it work?

for all run it 100 times

(x, y, ...) generate random inputs based on specified generators

such that
precondition(x, y, ...) holds check pre-conditions
fails?: go back to previous

property(x, y, ...) is true run the test
fails?: try shrinking

Benefits

• Reproducible
• Straight to corner cases
• Use the scope of all possible inputs
• Shrink the input in case of failure

Basic example

Let's suppose that we want to test is_substring

for all a, b, c strings
b is a substring of a + b + c

Basic example

Let's suppose that our implementation fails when the string ends by the pattern (arbitrary choice)

Framework might have built:

(a, b, c) = ("aaa", "bbb", "ccc")
is_substring("bbb", "aaabbbccc")?  TEST OK
                    

(a, b, c) = (   "",  "dd",   "e")
is_substring("dd", "dde")?         TEST OK
                    

(a, b, c) = ( "yy",   "w",   "")
is_substring("w", "yyw")?          TEST FAILURE
                    

-- SHRINK INPUT --
                    

(a, b, c) = (   "",    "",   "")
is_substring("", "")?              TEST FAILURE
                    

Applications of property-based testing

1. Case #1: pure algorithm
2. Case #2: game
3. Case #3: user interface

Observation

Why do we test?

• check for possible regressions
• early bug detection
• development logic
• documentation...

A helper not an end in itself

Observation

Our faith in tests:

• up-to-date
• as simple as possible
• evolve with the code
• wide coverage

Observation

But what if it was:

• costly to maintain
• limiting possible improvements

How would you test...?

How would you test a JSON serializer?

namespace json {
    
    class JsonObject;
    class JsonArray : public JsonObject;
    class JsonDictionary : public JsonObject;
    
    std::string stringify(JsonObject const&);
    std::unique_ptr<JsonObject> parse(std::string const&);
    
}//json
                    

How would you test a JSON serializer?

TEST(Stringify, ObjectWithTwoAttributesAandB) {
    auto instanceWithAandB = json::JsonDictionary {}
            .with("a", json::JsonInteger {4})
            .with("b", json::JsonInteger {7});
    
    ASSERT_EQ(
        std::string{"{\"a\":4,\"b\":7}"},
        json::stringify(instanceWithAandB));
}
                    

Not really...

{"a":4,"b":7}

{"b":7,"a":4}

{"a"  :4   ,  "b":7}

{"a":4    ,"b":7    }

{"a" : 4
,"b" : 7}
                                

{"a":4E0,"b":7E0}

{"a":40E-1,"b":7E0}

{"\u0061":4,"b":7}

Property for JSON.stringify

namespace json {

    std::string stringify(JsonObject const&);
    std::unique_ptr<JsonObject> parse(std::string const&);
    
}//json
                    

Property for JSON.stringify

RC_GTEST_PROP(Stringify,
              StringifyThenParseIsIdentity,
              (json::JsonObject const& elt))
{
    RC_ASSERT(*json::parse(json::stringify(elt)) == elt);
}
                    

Taking the object resulting from the conversion of the JsonObject to a string then back to a JsonObject should be equivalent to take the original instance itself.

We've seen:

• tests can rely on too many assumptions
• application of property based testing
• testing without too much hypothesis
• complementary to unit tests

Applications of property-based testing

1. Case #1: pure algorithm
2. Case #2: game
3. Case #3: user interface

Context

CodinGame

Game statement

(0,0)

Hint:
$: dimensions = (8, 8)
$: position   = (4, 4)
$: hint       = "DR"
                    

Game statement

Hint:
$: dimensions = (8, 8)
$: position   = (4, 4)
$: hint       = "DR"
                    

Game statement

Hint:
$: dimensions = (8, 8)
$: position   = (6, 6)
$: hint       = "D"
                    

Game statement

Hint:
$: dimensions = (8, 8)
$: position   = (6, 6)
$: hint       = "D"
                    

Game statement

Hint:
$: dimensions = (8, 8)
$: position   = (6, 7)
$: hint       = ""
                    

Prototypes

void find_bomb(Game& game);

Prototypes

Helper to read from CodinGame

class Game
{
public:
    // dimensions of the grid
    std::size_t dimension_x() const;
    std::size_t dimension_y() const;
    // last known location
    std::size_t previous_x() const;
    std::size_t previous_y() const;
    // direction to the target (U / D, L / R)
    std::string const& hint() const;
    // is it the position of the target?
    bool solved() const;
    // update position
    void move(std::size_t x, std::size_t y);
};
                    

Implementation

Hint: DR

Implementation

Hint: DR

Implementation

Hint: U

Implementation

Hint: U

...

Implementation

void find_bomb(Game& game)
{
    std::size_t x_min = 0;
    std::size_t x_max = game.dimension_x();
    std::size_t y_min = 0;
    std::size_t y_max = game.dimension_y();
    while (x_min < x_max && y_min < y_max)
    {
        // content on next slide
    }
}
                    

Implementation

std::size_t x0 = game.previous_x();
auto const& hint = game.hint();
if (hint.back() == 'L')
{
    x_max = x0 -1;
    x0 = (x_max + x_min) /2;
}
else if (hint.back() == 'R')
{
    x_min = x0 +1;
    x0 = (x_max + x_min) /2;
}
// same for y...
game.move(x0, y0);
                    

Results

User tests

Results

Evaluation tests

Property

What?

Solve the game in a limited amount of guesses

At first, we can assume that we will be able to solve it in a maximum of width x height

We can solve it in max(width, height) without too many complexity

We can solve it in ceil(log2(max(width, height)))

Property

Inputs

(width, height): integers between 1 and 10 000*

(start_x, target_x): integers between 0 and width*

(start_y, target_y): integers between 0 and height*

(num_rounds): max(width, height)

*not included

Property

Success

Reach the target with a maximum of num_rounds rounds

Property

RapidCheck implementation

RC_GTEST_PROP(ShadowsOfTheKnight, SAlwaysReachTarget, ())
{
    auto w = *inRange(1, 10000).as("grid width");
    auto h = *inRange(1, 10000).as("grid height");
    auto inRangeGen = apply(
        [](auto x, auto y) { return std::make_pair(x, y); }
        , inRange(0, w), inRange(0, h));
    auto current  = *inRangeGen.as("start position");
    auto solution = *inRangeGen.as("target position");
    TestGame game = TestGameBuilder{}
        .withDimension(w, h)
        .withSolution(solution.first, solution.second)
        .withCurrent(current.first, current.second).build();
    find_bomb(game);
    RC_ASSERT(game.solved());
}
                    

Run tests

Falsifiable after 9 tests and 5 shrinks

grid width:
8

grid height:
8

start position:
(0, 1)

target position:
(1, 0)
                        

Failure analysis

Hint:                        Next move:
$: dimensions = (8, 8)       $: xmin, xmax = (1, 8)
$: xmin, xmax = (0, 8)       $: ymin, ymax = (0, 0)
$: ymin, ymax = (0, 8)       $: position   = (4, 0)
$: position   = (0, 1)
$: hint       = "UR"
                    

Failure analysis

Hint:                        Next move:
$: dimensions = (8, 8)       $: Cannot suggest anything,
$: xmin, xmax = (1, 8)       $: it seems that
$: ymin, ymax = (0, 0)       $: there is no solution
$: position   = (4, 0)
$: hint       = "L"
                    

Failure analysis

Hint:                        Next move:
$: dimensions = (8, 8)       $: xmin, xmax = (1, 3)
$: xmin, xmax = (1, 8)       $: ymin, ymax = (0, 1)
$: ymin, ymax = (0, 1)       $: position   = (2, 0)
$: position   = (4, 0)
$: hint       = "L"
                    

Failure analysis

Hint:                        Next move:
$: dimensions = (8, 8)       $: xmin, xmax = (1, 2)
$: xmin, xmax = (1, 3)       $: ymin, ymax = (0, 1)
$: ymin, ymax = (0, 1)       $: position   = (1, 0)
$: position   = (2, 0)
$: hint       = "L"
                    

Failure analysis

Hint:
$: dimensions = (8, 8)
$: xmin, xmax = (1, 2)
$: ymin, ymax = (0, 1)
$: position   = (1, 0)
$: hint       = ""
                    

We've seen:

• corner cases not always well covered
• expanding our coverage
• complementary to unit-tests

Applications of property-based testing

1. Case #1: pure algorithm
2. Case #2: game
3. Case #3: user interface

Context

Let's test a web interface

Quick tour of our web interface

• contains multiple tabs
• allows user to cutomize colors (only on some tabs)
• modifying a color done by opening a picker
• modification has to be confirmed (or can be canceled)
• modification can impact 3 different components: spectrum, hue, alpha

Property-based testing applied to UI

We are already able to:

• produce random inputs: integers, arrays, ...
• play our tests randomly
• shrink to the minimal case

Property-based testing applied to UI

Characteristics of a UI under test:

• a user interface
• send valid commands
• check assumptions post execution

Property-based testing applied to UI

We need to define commands:

• check if it can be applied to current state
• apply it

Property-based testing applied to UI

We have to produce arrays of commands

commands = array of commands in {CommandA, CommandB, ...}
                    

Then give them to the framework

Example

List of commands we would like to test:

• Go to tab
• Open color picker
• Select color
• Select hue
• Select alpha
• Confirm our choice
• Cancel modification

Example

Open color picker:

var OpenPaletteForCommand = function(colorId) {
  // can we run the command?
  this.check = model => is_picker_accessible(model, colorId);

  // run it
  this.run = function(browser, model) {
    model.picker_for = colorId;
    model.color_before = await read_color(browser, colorId);
    await open_picker(browser, model, colorId);
    model.color_selected = await read_color_picker(browser);
    return true;
  };
};                
                    

Example

Cancel modification:

var CancelCommand = function() {
  // can we run the command?
  this.check = model => is_picker_opened(model);
  
  // run it
  this.run = function(browser, model) {
    await cancel_picker(browser);
    const color_after_cancel = await read_color(browser, model.picker_for);
    return model.color_before == color_after_cancel;
  };
};                
                    

Run tests

- Expected Error: Failed after 1 tests and 10 shrinks.
rngState: 00a5eb241093fc6d78;
Counterexample: ;
  GoToPanelCommand(color),
  OpenPaletteForCommand(palette_NEUTRAL_DARK),
  AlphaSpectrumCommand(alpha:2%),
  CancelPaletteCommand();
to be undefined.
                    

This example is inspired by a real case. The issue with cancel only occured when we were starting our modification by impacting alpha. It did not failed when we touched spectrum or hue followed by alpha and canceled just after.

We've seen:

• how extend and apply the framework to UI
• run QA-like testing