Infinite action chains biased towards small sizes

[gtrefs]

Testing Problem

Consider the following test:

    @Provide
    @Property(tries = 5_000)
    @StatisticsReport(format = Histogram.class)
    void checkMyStackInfinite(@ForAll("infiniteStackActions") ActionChain<MyStringStack> chain) {
        chain.run();
        Statistics.label("Chain size").collect(chain.transformations().size());

    }

    @Provide
    Arbitrary<ActionChain<MyStringStack>> infiniteStackActions() {
        return ActionChain.startWith(MyStringStack::new)
                .withAction(new PushAction())
                .withAction(pop())
                .withAction(new ClearAction())
                .withAction(Action.just(Transformer.endOfChain()))
                .infinite();
    }

Reports will look similar to this one:

timestamp = 2023-08-26T14:39:58.605951, [StackProperties:checkMyStackInfinite] (5000) Chain size = 
       # | label | count | 
    -----|-------|-------|---------------------------------------------------------------------------------
       0 |     1 |  1616 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       1 |     2 |  1025 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       2 |     3 |   705 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       3 |     4 |   459 | ■■■■■■■■■■■■■■■■■■■■■■
       4 |     5 |   377 | ■■■■■■■■■■■■■■■■■■
       5 |     6 |   241 | ■■■■■■■■■■■
       6 |     7 |   180 | ■■■■■■■■
       7 |     8 |   115 | ■■■■■
       8 |     9 |    83 | ■■■■
       9 |    10 |    65 | ■■■
      10 |    11 |    45 | ■■
      11 |    12 |    27 | ■
      12 |    13 |    18 | 
      13 |    14 |    17 | 
      14 |    15 |     8 | 
      15 |    16 |     8 | 
      16 |    17 |     4 | 
      17 |    19 |     1 | 
      18 |    20 |     2 | 
      19 |    21 |     1 | 
      20 |    24 |     1 | 
      21 |    25 |     2 | 

infinite action chains are biased towards small chains and never seem exceed sizes of the low twenties. This is smaller than the default sizes of 32.

Suggested Solution

I would expect that the size is more evenly distributed and that there are chains having a lot of actions (> 100).

[jlink]

Since all actions are added without weight, all get the same weight. Thus, end of chain has a probability of 1/4. The distribution you show seems pretty close to what I’d expect. My recommendation is to raise the weight of all actions but „end of chain“.

[gtrefs]

Thanks @jlink, I was a bit blind there. I changed the code as follows:

        return ActionChain.startWith(MyStringStack::new)
                .withAction(10,new PushAction())
                .withAction(10, pop())
                .withAction(10, new ClearAction())
                .withAction(1, Action.just(Transformer.endOfChain()))
                .infinite();

I was expecting to see some normal distribution over the chain size. However, I was wrong. I did some research and this is actually a geometric distribution over chain size. This means, the probability of randomly selecting the end of the chain becomes less and less, the longer the chain becomes. In this case it would be: P(n)=(30/31)^(n-1) * (1/31). This is why the histogram looks as follows:

timestamp = 2023-08-26T17:53:55.998221, [StackProperties:checkMyStackInfinite] (5000) Chain size = 
       # | label | count | 
    -----|-------|-------|---------------------------------------------------------------------------------
       0 |     1 |   245 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       1 |     2 |   187 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       2 |     3 |   199 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       3 |     4 |   154 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       4 |     5 |   171 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       5 |     6 |   164 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       6 |     7 |   156 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       7 |     8 |   139 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       8 |     9 |   100 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
       9 |    10 |   142 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      10 |    11 |   157 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      11 |    12 |   132 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      12 |    13 |   125 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      13 |    14 |   109 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      14 |    15 |    98 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      15 |    16 |   116 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      16 |    17 |    97 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      17 |    18 |   113 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      18 |    19 |   104 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      19 |    20 |    90 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      20 |    21 |    75 | ■■■■■■■■■■■■■■■■■■■■■■■■
      21 |    22 |    80 | ■■■■■■■■■■■■■■■■■■■■■■■■■■
      22 |    23 |    81 | ■■■■■■■■■■■■■■■■■■■■■■■■■■
      23 |    24 |    83 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■
      24 |    25 |    88 | ■■■■■■■■■■■■■■■■■■■■■■■■■■■■
      25 |    26 |    77 | ■■■■■■■■■■■■■■■■■■■■■■■■■
      26 |    27 |    63 | ■■■■■■■■■■■■■■■■■■■■
      27 |    28 |    80 | ■■■■■■■■■■■■■■■■■■■■■■■■■■
      28 |    29 |    66 | ■■■■■■■■■■■■■■■■■■■■■
      29 |    30 |    53 | ■■■■■■■■■■■■■■■■■
      30 |    31 |    54 | ■■■■■■■■■■■■■■■■■
      31 |    32 |    61 | ■■■■■■■■■■■■■■■■■■■
      32 |    33 |    58 | ■■■■■■■■■■■■■■■■■■
      33 |    34 |    46 | ■■■■■■■■■■■■■■■
      34 |    35 |    52 | ■■■■■■■■■■■■■■■■
      35 |    36 |    40 | ■■■■■■■■■■■■■
      36 |    37 |    55 | ■■■■■■■■■■■■■■■■■
      37 |    38 |    37 | ■■■■■■■■■■■■
      38 |    39 |    50 | ■■■■■■■■■■■■■■■■
      39 |    40 |    27 | ■■■■■■■■
      40 |    41 |    31 | ■■■■■■■■■■
      41 |    42 |    44 | ■■■■■■■■■■■■■■
      42 |    43 |    38 | ■■■■■■■■■■■■
      43 |    44 |    37 | ■■■■■■■■■■■■
      44 |    45 |    38 | ■■■■■■■■■■■■
      45 |    46 |    27 | ■■■■■■■■
      46 |    47 |    28 | ■■■■■■■■■
      47 |    48 |    27 | ■■■■■■■■
      48 |    49 |    32 | ■■■■■■■■■■
      49 |    50 |    29 | ■■■■■■■■■
      50 |    51 |    28 | ■■■■■■■■■
      51 |    52 |    30 | ■■■■■■■■■
      52 |    53 |    28 | ■■■■■■■■■
      53 |    54 |    26 | ■■■■■■■■
      54 |    55 |    19 | ■■■■■■
      55 |    56 |    18 | ■■■■■
      56 |    57 |    26 | ■■■■■■■■
      57 |    58 |    18 | ■■■■■
      58 |    59 |    13 | ■■■■
      59 |    60 |    19 | ■■■■■■
      60 |    61 |    17 | ■■■■■
      61 |    62 |    16 | ■■■■■
      62 |    63 |    14 | ■■■■
      63 |    64 |    16 | ■■■■■
      64 |    65 |    17 | ■■■■■
      65 |    66 |    12 | ■■■
      66 |    67 |    15 | ■■■■
      67 |    68 |    14 | ■■■■
      68 |    69 |    11 | ■■■
      69 |    70 |    17 | ■■■■■
      70 |    71 |    16 | ■■■■■
      71 |    72 |     9 | ■■
      72 |    73 |     7 | ■■
      73 |    74 |    14 | ■■■■
      74 |    75 |    15 | ■■■■
      75 |    76 |     5 | ■
      76 |    77 |    11 | ■■■
      77 |    78 |    11 | ■■■
      78 |    79 |     9 | ■■
      79 |    80 |     7 | ■■
      80 |    81 |     8 | ■■
      81 |    82 |     9 | ■■
      82 |    83 |     8 | ■■
      83 |    84 |     4 | ■
      84 |    85 |     6 | ■
      85 |    86 |     7 | ■■
      86 |    87 |     7 | ■■
      87 |    88 |     8 | ■■
      88 |    89 |     4 | ■
      89 |    90 |     4 | ■
      90 |    91 |     3 | 
      91 |    92 |     2 | 
      92 |    93 |     3 | 
      93 |    94 |     4 | ■
      94 |    95 |     3 | 
      95 |    96 |     4 | ■
      96 |    97 |     5 | ■
      97 |    98 |     3 | 
      98 |    99 |     7 | ■■
      99 |   100 |     5 | ■
     100 |   101 |     2 | 
     101 |   102 |     3 | 
     102 |   103 |     1 | 
     103 |   104 |     1 | 
     104 |   105 |     1 | 
     105 |   106 |     3 | 
     106 |   109 |     1 | 
     107 |   110 |     1 | 
     108 |   112 |     1 | 
     109 |   113 |     2 | 
     110 |   114 |     3 | 
     111 |   118 |     5 | ■
     112 |   119 |     1 | 
     113 |   120 |     3 | 
     114 |   122 |     2 | 
     115 |   123 |     2 | 
     116 |   124 |     1 | 
     117 |   125 |     1 | 
     118 |   126 |     2 | 
     119 |   127 |     3 | 
     120 |   128 |     1 | 
     121 |   130 |     1 | 
     122 |   131 |     1 | 
     123 |   132 |     2 | 
     124 |   133 |     2 | 
     125 |   135 |     1 | 
     126 |   137 |     1 | 
     127 |   138 |     2 | 
     128 |   139 |     1 | 
     129 |   140 |     1 | 
     130 |   146 |     1 | 
     131 |   148 |     1 | 
     132 |   156 |     1 | 
     133 |   158 |     2 | 
     134 |   166 |     1 | 
     135 |   170 |     1 | 
     136 |   175 |     1 | 
     137 |   188 |     1 | 
     138 |   196 |     1 | 
     139 |   205 |     1 | 

Is this the desired behavior?

[jlink]

Is this the desired behavior?

It's the only logical outcome from throwing the dice with the given probabilities.

If you want longer chains, you might just use withMaxTransformations(size).
Often varying the length does not bring additional test coverage, since shorter chain checking is included in longer chains.

If you really want equally distributed variation, try something like this:

@Provide
Arbitrary<ActionChain<MyStringStack>> actions() {
	Arbitrary<Integer> length = Arbitraries.integers().between(1, 1000)
									.withDistribution(RandomDistribution.uniform());
	return length.flatMap(maxLength -> ActionChain.startWith(...)
					  .withAction(...)
					  .withMaxTransformations(maxLength));
}

[gtrefs]

Is this the desired behavior?

It's the only logical outcome from throwing the dice with the given probabilities.

It is, but this was not the intent of my question. Given an empty stack, does it make sense to clear it 245 times?

If you want longer chains, you might just use withMaxTransformations(size). Often varying the length does not bring additional test coverage, since shorter chain checking is included in longer chains.

I tend to disagree. I want to generate examples which are more likely to catch a bug. Consider this slightly changed example from the docs:

            // Wrong implementation to provoke falsification for stacks with more than 2 elements
            if (elements.size() > 33) {
                elements.remove(0);
            } else {
                elements.clear();
            }

I was able to run the following property more than 10 times without problems. Even when I lowered, the condition to 10, I only caught it on the 3rd run.

    @Provide
    @Property(tries = 10_000)
    @StatisticsReport(format = Histogram.class)
    void checkMyStackInfinite(@ForAll("infiniteStackActions") ActionChain<MyStringStack> chain) {
        chain.run();
        Statistics.label("Chain size").collect(chain.transformations().size());

    }

I want to find a combination of actions which leads to an undesired state. If a combination of n actions is fine, then still a combination of n+1 actions can lead to an undesired state. As stated in the code, the actions are independent from each other. Though, potential combinations grow exponentially. Maybe the problem is how to create a proper representation of the sample space?

If you really want equally distributed variation, try something like this:

@Provide
Arbitrary<ActionChain<MyStringStack>> actions() {
	Arbitrary<Integer> length = Arbitraries.integers().between(1, 1000)
									.withDistribution(RandomDistribution.uniform());
	return length.flatMap(maxLength -> ActionChain.startWith(...)
					  .withAction(...)
					  .withMaxTransformations(maxLength));
}

This looks better and did a better job in catching the 10 element size problem, but did not catch the 33 element size problem. Does withMaxTransformations create chains with up to maxLength or exactly maxLength?

[jlink]

Does withMaxTransformations create chains with up to maxLength or exactly maxLength?

Without a Transformer.endOfChain() action it should be exactly maxLength.