Property-based testing

Using RapidCheck

Agenda

1. Another test philosophy
2. Assumptions when testing
3. Properties for real life

Agenda

1. Another test philosophy
2. Assumptions when testing
3. Properties for real life

Some tests 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
pre-condition(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

Example:

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

Let's say that our is_substring fails when the string ends by the pattern

It 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
                    

Agenda

1. Another test philosophy
2. Assumptions when testing
3. Properties for real life

Observation

Why do we tests?

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

An helper not an end in itself

Our faith in tests:

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

But what if it was:

• costly to maintain
• limiting possible improvments

Statement

How would you test a JSON serializer given the following specification?

Converts a value to JSON notation representing it.

Such specification is the one described by Mozilla Foundation web docs for `JSON.stringify` of JavaScript. The exhaustive specification is available on ECMA-262.

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
                    

Easy, isn't it?

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...

Key ordering

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

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

Change storage strategy?

Deterministic

Run on other platform?

Static data?

Ident

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

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

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

Divide into multiple threads?

Notation

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

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

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

Full unicode?

Property

Any idea?

namespace json {

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

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.

Agenda

1. Another test philosophy
2. Assumptions when testing
3. Properties for real life

Context

CodinGame

Two sets of tests:

• public set: available for development
• private set: unknown tests

Statement

Aim:

Find the position of a bomb in a limited number of guesses

Each turn:

• receive: indication of the direction of the bomb
• send: new guess

grid size and current location known

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

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

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

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

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

Sources

The goal of this puzzle is to guess the coordinate of a bomb (line and column of a 2 dimensional array). You will have to make a guess at each step of the puzzle and adjust it from given feedbacks. Of course, you have a limited number of guess.

Taken from CodinGame

Before each [guess], the heat-signature device will provide Batman with the direction of the bombs based on Batman current position.

Taken from CodinGame

Prototypes

Expected answer

void locate_in_space(Space& space, std::size_t rounds);

Helper to read from CodinGame

class Space
{
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

Hint: DR

Hint: U

Hint: U

...

void locate_in_space(Space& space, std::size_t rounds)
{
    std::size_t x_min = 0;
    std::size_t x_max = space.dimension_x();
    std::size_t y_min = 0;
    std::size_t y_max = space.dimension_y();
    for (std::size_t n {} ;
        n != rounds && ! space.solved() ;
        ++n)
    {
        // content on next slide
    }
}
                    

if (x_min >= x_max || y_min >= y_max) { return; }
std::size_t x0 = space.previous_x();
auto const& hint = space.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...
space.move(x0, y0);
                    

Results

User tests

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)))

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

Success

Reach the target with a maximum of num_rounds rounds

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");
    Space space = SpaceBuilder{}
        .withDimension(w, h)
        .withSolution(solution.first, solution.second)
        .withCurrent(current.first, current.second).build();
    locate_in_space(space, std::max(h, w));
    RC_ASSERT(space.solved());
}
                    

Run tests

Failed with output:

Falsifiable after 9 tests and 5 shrinks

grid width:
8

grid height:
8

start position:
(0, 1)

target position:
(1, 0)
                    

Hint:                        Strategy:
$: 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"
                    

Hint:                        Strategy:
$: 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"
                    

Hint:                        Strategy:
$: 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"
                    

Hint:                        Strategy:
$: 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"
                    

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

More

Property-based testing in action

Bounded output

for all a and b integers,
the average of a and b is between a and b

RC_GTEST_PROP(Average, ShouldBeBetweenAAndB,
              (int a, int b))
{
    RC_PRE(a <= b);
    RC_ASSERT(a <= average(a,b) && average(a,b) <= b);
}
                    

Assumptions concerning the range in which will be the output

Limited set of inputs

for all (a, b, c) strings,
b is a substring of the concatenation of a, b and c

RC_GTEST_PROP(Contains,
              ShouldBeTrueOnAllStringsBuiltAroundPattern,
              (std::string a,
               std::string b,
               std::string c))
{
    RC_ASSERT(contains(b, a + b + c));
}
                    

Subset of inputs having a trivial answer

Compare to another implementation

for all data - sorted array of integers - and n - integer,
the result of the linear search of n in data is the same as the one of the binary search of n in data

RC_GTEST_PROP(FindDicho, ShouldBeSameAsSimpler,
              (std::vector<int> data, int n))
{
    std::sort(data.begin(), data.end());
    RC_ASSERT(find_dicho(data, n) == find_linear(data, n));
}
                    

Another algorithm - in general, simpler to implement - exists

Combination of functions

Round trip

for all n integer,
the integer equivalent of the roman representation of n is itself

RC_GTEST_PROP(RomanConversion, FromOfToIsIdentity,
              (int n))
{
    RC_ASSERT(from_roman(to_roman(n)) == n);
}
                    

Encode and decode pair of functions

More general combination

for all a and b integers,
lcm(a,b) * gcd(a,b) = a * b

RC_GTEST_PROP(LcmGcd, RelationBetweenLcmAndGcd,
              (int a, int b))
{
    RC_ASSERT(lcm(a,b) * gcd(a,b) = a * b);
}
                    

Some properties hold given a combination of multiple functions

Commands based

Why don't we test that the code follow the specifications?

Check pre-conditions before running a command

Check post-conditions after

struct PlayCommand : MusicPlayerCommand
{
    void checkPreconditions(MPModel const& /*m*/) const override {}
    void apply(MPModel& m) const override { m.is_playing = true; }
    void run(MPModel const& /*m*/, MusicPlayer& p) const override
    {
        p.play();
        RC_ASSERT(p.is_playing());
    }
    void show(std::ostream& os) const override { os << "Play"; }
};
                    

After running play, player must be in playing mode

struct NextCommand : MusicPlayerCommand
{
    void checkPreconditions(MPModel const& /*m*/) const override {}
    void apply(MPModel& m) const override {}
    void run(MPModel const& m, MusicPlayer& p) const override
    {
        auto track_before = p.track_name();
        p.next();
        RC_ASSERT(m.is_playing == p.is_playing());
        if (m.num_tracks == 1)
            RC_ASSERT(track_before == p.track_name());
        else
            RC_ASSERT(track_before != p.track_name());
    }
    void show(std::ostream& os) const override { os << "Next"; }
};
                    

Next always moves to a different song for multiple tracks playlists