How to make the generators surface more edge cases?

[chtenb]

When using the builtin generators in a naieve manner, I find that the probability of generating data that hit upon interesting edge cases is very low.
Here is a simple but extreme example

    [Test] public void TestArray() => TestLaws(Gen.Int.Array);
    // Here are other custom object generators

    protected void TestLaws<T>(Gen<T> gen)
        where T : IEquatable<T>
    {
        Gen.Select(gen, gen).Sample((a, b) =>
        {
            // Test the IEquatable interface Equals against the object.Equals
            AreEq(a.Equals(b), Equals(a, b));

            // Test the symmetry
            AreEq(a.Equals(b), b.Equals(a));

            // Test compability of hashcode implementation with equals implementation.
            if (a.Equals(b))
            {
                var hashA = a.GetHashCode();
                var hashB = b.GetHashCode();
                AreEq(hashA, hashB, $"{a} and {b} are equal while their hash is not: {hashA}, {hashB}");
            }
        }, iter:10000000);
    }

For this test to be meaningful, the generators must generate objects which are structurally similar (or even the same object).
With some experimentation I find that the probability of generating two arrays with the same elements is extremely unlikely.

I think it is possible to improve upon the situation with some pragmatic techniques. Some ideas

• Have tuple/array generators that generate the same objects for a subset of the elements, by re-using the seed or by returning the same object multiple times
• Skew primitive generators more towards builtin edge cases, thereby skewing derived generators too. E.g. if GenInt returns certain numbers a lot more often, a generator like Gen.Select(Gen.DateTime, Gen.TimeSpan, Gen.DateTime, Gen.TimeSpan) is a lot more likely to generate two intervals that are directly adjacent to each other. This would otherwise be near impossible to generate, statistically.
• Skewing primitive generators to smaller instances. Large instances tend to be very similar behaviorally. I.e. whenever the code works for number 2435867, it'll probably also work for 2435868.
• Add builtin knowledge about common pitfalls in code. E.g. Gen.DateTime could generate data around leap-seconds/days or DST transitions more frequently. I see that there is a GenSpecial class for floating point numbers, which is a good example. For good coverage, one should probably use Gen.OneOf(Gen.Double.Special, Gen.Double) when writing tests
• Skew primitive generators by mixing in generators with different distributions. E.g. a generator that builds a number by adding a large random number [1, 9] and a small random number [0.00001, 0.00009] together is more likely to generate two numbers that are very close together than the default GenDouble. Selecting a generator from a set of skewed generators can statistically perform much better at surfacing edge cases.

I've used these techniques with reasonable success in my own ad-hoc testing library, but I'm currently investigating CsCheck as a faster and more ergonomic alternative.

[AnthonyLloyd]

I'm not exactly sure what .ToSet() is but I guess it's like .Distinct().ToHashSet() with some implementation of IEquitable?

Gen.Int is skewed towards smaller values. The .Array will by an array 0 .. 127 in length with equals probability. The array length not matching and probably being long is why it's hard to make them match.

In this test reducing the array size would help e.g. Gen.Int.Array[0, 9].

Array could skew smaller but I've not done that as there is general principle that larger samples tend to catch more failures due to the number of permutations of possible failure configurations (see readme John Hughes).

I did have parametric skew for doubles at one point but it wasn't so useful. Double and other floating point now have a mixture of different types of numbers like fractions and exponents which does catch more types of problems e.g. exactly adding up.

There's an interesting comparison with QuickCheck like random testing libraries here in that they size up until they hit a failure and then follow a tree based shrink. Because of this they may be better in this case at finding a small failure but then not so good at shinking it (and may not even be able to). CsCheck does need to skew well to reduce the time to first failure but once found it's much better at shrinking.

[chtenb]

The ToSet() was a copy-paste error, corrected now.

[AnthonyLloyd]

The ToSet() was a copy-paste error, corrected now.

It doesn't compile because int[] isn't IEquitable<T>. Also no implementation for AreEq but can guess what it would be.