PropCheck "list of minimum two elements"-generator

smedegaard

I’m trying to write property based tests for a Reverse Polish Notation calculator.

I’ve implemented the RPN such that it will return an error tuple if you try to push a operator to the stack when the stack has less than two numbers.

defmodule ReversePolishNotation do
  @moduledoc """
  Documentation for ReversePolishNotation.
  """

  def push(list, number) when number |> is_number do
    {:ok, [number | list]}
  end

  @operators [:+, :/, :-, :*]
  def push([x, y | list], op) when op in @operators do
    result = apply(Kernel, op, [x, y])
    {:ok, [result | list]}
  end

  def push(list, input) do
    {:error, list, {:unexpected_input, input}}
  end

end

Now I want to test the happy path of pushing an operator to a stack (list) of numbers, where the list has at least two numbers in it.

since number() |> list() |> non_empty() will shrink to a one element list it does not work for me.

so I tried to to use the such_that macro to generate lists of numbers with length(l) > 1 but that ends with {:error, :cant_generate}

My test and generator

  property "can push operator to a list with minimum 2 numbers" do
    forall {list, operator} <- {list_min_two(), operator()} do
      {:ok, _new_list} = RPN.push(list, operator)
    end
  end

  # Generators

  def operator() do
    oneof([:+, :-, :/, :*])
  end

  def list_min_two() do
    such_that l <- non_empty(list(number())), when: length(l) > 1
  end

Maybe @alfert has some insight?

8 comments

#property-testing #property-based-testing

0 1761 8

2020-01-16 01:40:29 UTC

Showing Posts 1 to 8

Show Best Posts
Show All (oldest first)
Show All (newest first)

Qqwy

TypeCheck Core Team

I have only used StreamData before, but I PropCheck is probably similar. I see two possibilities for the generator:

Reject cases that are shorter than two-elements as ‘improperly generated values that we do not want to use’
Generate a a = non_empty(list(number())) and a separate b = number(), which you then combine (using a map or bind operation to turn them into [a | b] if PropCheck has something like that, I did not find it right away, or otherwise just inside your tests).

Post #1

smedegaard

Thanks for the reply!

such_that l <- non_empty(list(number())), when: length(l) > 1

I was trying to achieve your first point with the above code.
The such_that macro should discard generated values when the anonymous function returns false.

I thought about combining generators in the way you suggest in point 2. But I have not found out how. I’ll dig a bit more into that

Post #2

smedegaard

I thought I tried this yesterday but I Solved i with [ number() | list_of_numbers ]

where list_of_numbers = non_empty(list(number()))

I also filtered 0 out to avoid division by zero errors, but that’s another story.

Post #3

alfert

Sorry for my long delay. I cannot reproduce your problem with the such_that operator. I did the following:

iex> use PropCheck
iex> produce(such_that l <- non_empty(list(number())), when: length(l) > 1)
{:ok,
 [-10, -12.498990234832617, 26.565811750847487, -0.8553774801624835,  -11.727179060408071, 11, 6, -6, 0, -18]}

iex> sample_shrink(such_that l <- non_empty(list(number())), when: length(l) > 1)
[-10.085757951113234,4,0.49263719097867137,-8.994420603636804,-4,-33,
 -1.3484964548787592,-2,-28,0.772165396869481]
[-10.085757951113234,4,0.49263719097867137,-8.994420603636804,-4]
[-10.085757951113234,4,0.49263719097867137]
[4,0.49263719097867137]
[0,0.49263719097867137]
[0,21]
[0,0]
:ok

This would be the expected behaviour. Using the produce and sample_shrink helps to find bugs in the generators.

But your approach using

iex> sample_shrink([number() | non_empty(list(number))])
[-6,-129.9346393942964,1,9]
[0,-129.9346393942964,1,9]
[0,1,9]
[0,9]
[0,0]
:ok

works equally well: a list of generators is also a generator and will not shrink towards the empty list. The combination of generators works on the generator and not on the data level, therefore both generators must be present when shrinking.

Hope that explains the approach.

In your case, I would go for several generators:

def non_zero_number, do: such_that n <- number(), where: n != 0
def list_min_two(elem_gen), do: 
   such_that l <- non_empty(list(elem_gen() )), when: length(l) > 1
def safe_numbers, do: list_min_two(non_zero_number())
def numbers, do: list_min_two(number())

But I assume your approach is similar.

If this still fails, then please file a bug report on GitHub! In the best case, we have a documentation issue.

Post #4

smedegaard

Thanks a lot for the answer. Your examples in iex works fine. Don’t know why the function didn’t work…

Post #5

ferd

Author of Property-Based Testing with PropEr, LYSE, & Erlang in Anger

you may want to use some cheats that let you properly ensure that you never generate useless sequences, using let macros. You can do something like let l <- list(elem()), do: [elem(), elem() | l] which will give a 2-or-more elements list no matter what happens, without needing retried generators in a such_that macro.

Post #6