How to generate a set of valid actions for a reducer using a property based testing library?

I'm trying to generate a series of actions, where the actions that should be generated depend on what the previous actions were.

Let's say my state is a set of numbers stored as an array:

[1, 2]

And there are the following actions:

{ type: "add", value: number }
{ type: "remove", value: number }

I want to generate a series of actions to dispatch before checking properties of the state. If a remove action is generated, I want to ensure that it's value is in the state.

Valid Examples:

initial state: [1, 2]
[{ type: "remove", value: 1 }, { type: "remove", value: 2 }]
[{ type: "add", value: 3 }, { type: "remove", value: 3 }]

Invalid Examples:

initial state: [1, 2]
[{ type: "remove", value: 3 }]
[{ type: "remove", value: 2 }, { type: "remove", value: 2 }]

Is this something that is possible using a property based testing library, and if so how would I accomplish it?

I am using https://github.com/dubzzz/fast-check, but if this is easier using another library I'm open to examples from others.

Solution

Yes, this is perfectly suited for property-based testing. From a quick skimming of the docs of fast-check, I can see three approaches to this:

Make a precondition. This will ignore tests where an invalid sequence of actions was generated.
Prior to running a remove action, you'd count how often the number was contained in the initial state, how often in add actions before now, and how often in remove actions before now. Then you'd know whether you can remove it another time.
Use model-based testing (also here). This seems to perfectly fit your use case. Each action would be represented by one Command, all commands would simply apply their respective action, and in their check method you would validate whether the action is eligible.
This requires building a model, where you need to make sure that the model is a simplification of the actual state and that it uses a different implementation approach (so that you won't re-implement your bugs here). In your example, that could mean keeping a Set of occurring numbers or a Map of their counts, not an ordered array.
Generate only valid sequences in the first place.
This is much more efficient than the first two approaches, but usually also much more complicated. It might be necessary though if the generated numbers to be removed are too unbiased and rarely ever match one that is in the list. I got two ideas here:
- generate your list of actions recursively, and keep a model similar to the one from model-based testing. You have to update it yourself however. With this, you can generate remove actions only exactly for those numbers that are currently in your model.
  I'm not sure whether letrec or memo help here, whether you might need to use chain, or ask the library author to provide an extra function for this use case. (Maybe even as part of model-based testing, where Command instances could be dynamically derived from the current model?)
- generate a remove action always together with a preceding add action with the same number. After having generated a list of [add(x)] and [add(y), remove(y)] lists, merge these in arbitrary order but keeping the respective order between the elements of each sublist.
  This is probably the most elegant method to do this, as it looks nothing like the model of your state. However, I'm pretty certain that you will need to build your own Arbitrary for the randomMerge function - maybe ask the library author for help with this or request a new feature.