This is an automated email from the ASF dual-hosted git repository.
dcapwell pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
The following commit(s) were added to refs/heads/trunk by this push:
new 7205f68a Add documentation for Accord's property testing (#196)
7205f68a is described below
commit 7205f68a25f5b925a08cc58547981ce2bf485f8f
Author: dcapwell <dcapw...@apache.org>
AuthorDate: Thu May 29 15:23:03 2025 -0700
Add documentation for Accord's property testing (#196)
patch by David Capwell; reviewed by Jordan West, Stefan Miklosovic for
CASSANDRA-20684
---
accord-core/src/test/java/accord/utils/Gen.java | 56 ++-
accord-core/src/test/java/accord/utils/Gens.java | 433 ++++++++++++++++++++-
.../src/test/java/accord/utils/Property.java | 77 +++-
accord-core/src/test/java/accord/utils/README.md | 318 +++++++++++++++
4 files changed, 859 insertions(+), 25 deletions(-)
diff --git a/accord-core/src/test/java/accord/utils/Gen.java
b/accord-core/src/test/java/accord/utils/Gen.java
index 357c197a..822a5e14 100644
--- a/accord-core/src/test/java/accord/utils/Gen.java
+++ b/accord-core/src/test/java/accord/utils/Gen.java
@@ -34,6 +34,17 @@ import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;
+/**
+ * A generator (gen for short) interface that produces values using a {@link
RandomSource}.
+ * <p>
+ * This interface provides a way to generate random values of type {@code A}
and transform them
+ * using various functional operators like {@link #map(Function)}, {@link
#filter(Predicate)}, and {@link #flatMap(Function)}.
+ * <p>
+ * Specialized versions exist for primitive types ({@link IntGen}, {@link
LongGen}) to avoid boxing/unboxing overhead.
+ *
+ * @param <A> The type of values this generator produces
+ */
+@SuppressWarnings("unused")
public interface Gen<A>
{
/**
@@ -45,6 +56,22 @@ public interface Gen<A>
return fn;
}
+ /**
+ * Core method of the {@link Gen} interface that produces a value of type
{@code A} using the provided {@link RandomSource}.
+ * <p>
+ * The semantics of this method are implementation-specific. Some
important considerations:
+ * <ul>
+ * <li>Some implementations may return null values</li>
+ * <li>Implementations may return duplicate or identical values across
calls</li>
+ * <li>Values may contain or be backed by shared mutable state</li>
+ * </ul>
+ * <p>
+ * Due to these implementation-specific behaviors, callers should avoid
storing references to returned
+ * values for extended periods unless the specific generator's safety
guarantees are known.
+ *
+ * @param random The random source to use for generating values
+ * @return A generated value of type {@code A}
+ */
A next(RandomSource random);
default <B> Gen<B> map(Function<? super A, ? extends B> fn)
@@ -77,6 +104,18 @@ public interface Gen<A>
return rs -> mapper.apply(rs, this.next(rs)).next(rs);
}
+ /**
+ * Creates a new generator that only produces values matching the provided
predicate.
+ * <p>
+ * <strong>Warning:</strong> This method is unbounded and will loop
indefinitely if the predicate
+ * never returns true for any generated value. Use with caution,
especially with rare conditions.
+ * <p>
+ * For a bounded alternative that will stop after a specified number of
attempts,
+ * see {@link #filter(int, Object, Predicate)}.
+ *
+ * @param fn the predicate function that values must satisfy
+ * @return a new generator that only produces values matching the predicate
+ */
default Gen<A> filter(Predicate<A> fn)
{
Gen<A> self = this;
@@ -90,6 +129,19 @@ public interface Gen<A>
};
}
+ /**
+ * Creates a new bounded generator that only produces values matching the
provided predicate.
+ * <p>
+ * Unlike the unbounded {@link #filter(Predicate)}, this method will make
at most {@code maxAttempts}
+ * attempts to generate a value that satisfies the predicate. If no
matching value is found within
+ * the specified number of attempts, it returns the provided {@code
defaultValue} instead.
+ *
+ * @param maxAttempts the maximum number of generation attempts before
falling back to the default value
+ * @param defaultValue the value to return if no matching value is found
within maxAttempts
+ * @param fn the predicate function that values must satisfy
+ * @return a new bounded generator that produces values matching the
predicate or the default value
+ * @throws IllegalArgumentException if maxAttempts is not positive
+ */
default Gen<A> filter(int maxAttempts, A defaultValue, Predicate<A> fn)
{
Invariants.requireArgument(maxAttempts > 0, "Max attempts must be
positive; given %d", maxAttempts);
@@ -172,7 +224,7 @@ public interface Gen<A>
@Override
default Gen.IntGen filter(Predicate<Integer> fn)
{
- return filterAsInt(i -> fn.test(i));
+ return filterAsInt(fn::test);
}
default IntSupplier asIntSupplier(RandomSource rs)
@@ -222,7 +274,7 @@ public interface Gen<A>
@Override
default Gen.LongGen filter(Predicate<Long> fn)
{
- return filterAsLong(i -> fn.test(i));
+ return filterAsLong(fn::test);
}
default LongSupplier asLongSupplier(RandomSource rs)
diff --git a/accord-core/src/test/java/accord/utils/Gens.java
b/accord-core/src/test/java/accord/utils/Gens.java
index d3adac61..d9dcfb8e 100644
--- a/accord-core/src/test/java/accord/utils/Gens.java
+++ b/accord-core/src/test/java/accord/utils/Gens.java
@@ -26,15 +26,17 @@ import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.EnumMap;
+import java.util.EnumSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
-import java.util.NavigableSet;
import java.util.Objects;
import java.util.Set;
+import java.util.SortedMap;
+import java.util.SortedSet;
import java.util.function.BooleanSupplier;
import java.util.function.Function;
import java.util.function.Supplier;
@@ -46,7 +48,9 @@ import com.google.common.collect.Iterables;
import accord.utils.random.Picker;
-public class Gens {
+@SuppressWarnings("unused")
+public class Gens
+{
private Gens() {
}
@@ -65,6 +69,19 @@ public class Gens {
return ignore -> constant.get();
}
+ /**
+ * Creates a generator that randomly selects one of the provided
generators on each execution, then calls {@link Gen#next(RandomSource)} on that
chosen generator.
+ * <p>
+ * This method distributes the selection with equal probability. For
weighted selection,
+ * see {@link #oneOf(Map)}.
+ *
+ * @param <T> the type of values to generate
+ * @param gens the generators to select from
+ * @return a generator that uses one of the provided generators for each
value
+ * @throws IllegalArgumentException if gens is empty
+ */
+ @SuppressWarnings("unchecked")
+ @SafeVarargs
public static <T> Gen<T> oneOf(Gen<? extends T>... gens)
{
switch (gens.length)
@@ -75,6 +92,18 @@ public class Gens {
return oneOf(Arrays.asList(gens));
}
+ /**
+ * Creates a generator that randomly selects one of the provided
generators from a list on each execution, then calls {@link
Gen#next(RandomSource)} on that chosen generator.
+ * <p>
+ * This method distributes the selection with equal probability. For
weighted selection,
+ * see {@link #oneOf(Map)}.
+ *
+ * @param <T> the type of values to generate
+ * @param gens the list of generators to select from
+ * @return a generator that uses one of the provided generators for each
value
+ * @throws IllegalArgumentException if gens is empty
+ */
+ @SuppressWarnings("unchecked")
public static <T> Gen<T> oneOf(List<Gen<? extends T>> gens)
{
switch (gens.size())
@@ -85,17 +114,50 @@ public class Gens {
return rs -> rs.pick(gens).next(rs);
}
+ /**
+ * Creates a generator that randomly selects one of the provided
generators based on weight, then calls {@link Gen#next(RandomSource)} on that
chosen generator.
+ * <p>
+ * Each generator is selected with a probability proportional to its
associated weight.
+ * Higher weights increase the likelihood of selection.
+ *
+ * @param <T> the type of values to generate
+ * @param values a map of generators to their respective weights
+ * @return a generator that uses one of the provided generators according
to their weights
+ * @throws IllegalArgumentException if values is empty
+ */
public static <T> Gen<T> oneOf(Map<Gen<T>, Integer> values)
{
Gen<Gen<T>> gen = pick(values);
return rs -> gen.next(rs).next(rs);
}
+ /**
+ * A builder for creating generators that randomly select from multiple
generators with customizable weights.
+ *
+ * @see OneOfBuilder
+ * @return a oneOf builder to aid in creating a {@code Gen} of type {@code
T}
+ * @param <T> the generator will return
+ */
public static <T> OneOfBuilder<T> oneOf()
{
return new OneOfBuilder<>();
}
+ /**
+ * A builder for creating generators that randomly select from multiple
generators with customizable weights.
+ * <p>
+ * This builder allows constructing complex random selection logic with:
+ * <ul>
+ * <li>Weighted probabilities for different generators</li>
+ * <li>Dynamically determined weights at generation time (if {@link
#build} is called, the weight will be {@code 1})</li>
+ * </ul>
+ * <p>
+ * The {@link #buildWithDynamicWeights()} method is particularly powerful
as it creates
+ * a meta-generator that recalculates the weights for unweighted
generators on each invocation,
+ * producing more varied randomization patterns than static weights.
+ *
+ * @param <T> the type of values the generators will produce
+ */
public static class OneOfBuilder<T>
{
private final Map<Gen<T>, Integer> weighted = new LinkedHashMap<>();
@@ -128,8 +190,7 @@ public class Gens {
return i -> gen;
}
return rs -> {
- Map<Gen<T>, Integer> commands = new LinkedHashMap<>();
- commands.putAll(weighted);
+ Map<Gen<T>, Integer> commands = new LinkedHashMap<>(weighted);
for (var gen : unweighted)
commands.put(gen, unknownWeightGen.nextInt(rs));
var top = pick(commands);
@@ -139,8 +200,7 @@ public class Gens {
public Gen<T> build()
{
- Map<Gen<T>, Integer> commands = new LinkedHashMap<>();
- commands.putAll(weighted);
+ Map<Gen<T>, Integer> commands = new LinkedHashMap<>(weighted);
for (var gen : unweighted)
commands.put(gen, 1);
var top = pick(commands);
@@ -148,40 +208,96 @@ public class Gens {
}
}
+ /**
+ * Creates a generator that randomly selects one value from an array.
+ * <p>
+ * Each value has an equal probability of being selected.
+ *
+ * @param ts the array of values to select from
+ * @return a generator that produces random values from the given array
+ * @throws IllegalArgumentException if the array is empty
+ */
public static Gen.IntGen pickInt(int... ts)
{
+ Invariants.requireArgument(ts.length > 0, "Unable to pick from an
empty array");
return rs -> ts[rs.nextInt(0, ts.length)];
}
+ /**
+ * Creates a generator that randomly selects one value from an array.
+ * <p>
+ * Each value has an equal probability of being selected.
+ *
+ * @param <T> the type of values to generate
+ * @param ts the array of values to select from
+ * @return a generator that produces random values from the given array
+ * @throws IllegalArgumentException if the array is empty
+ */
+ @SafeVarargs
public static <T> Gen<T> pick(T... ts)
{
+ Invariants.requireArgument(ts.length > 0, "Unable to pick from an
empty array");
return pick(Arrays.asList(ts));
}
+ /**
+ * Creates a generator that randomly selects one value from a list.
+ * <p>
+ * Each value has an equal probability of being selected.
+ *
+ * @param <T> the type of values to generate
+ * @param ts the list of values to select from
+ * @return a generator that produces random values from the given list
+ * @throws IllegalArgumentException if the list is empty
+ */
public static <T> Gen<T> pick(List<T> ts)
{
+ Invariants.requireArgument(!ts.isEmpty(), "Unable to pick from an
empty collection");
Gen.IntGen offset = ints().between(0, ts.size() - 1);
return rs -> ts.get(offset.nextInt(rs));
}
+ /**
+ * Creates a generator that randomly selects one value from a set. When
the set does not have deterministic
+ * iteration ordering, then the values will be sorted based off their
natural ordering first.
+ * <p>
+ * Each value has an equal probability of being selected.
+ *
+ * @param <T> the type of values to generate
+ * @param set the set of values to select from
+ * @return a generator that produces random values from the given set
+ * @throws IllegalArgumentException if the set is empty
+ */
public static <T extends Comparable<T>> Gen<T> pick(Set<T> set)
{
+ Invariants.requireArgument(!set.isEmpty(), "Unable to pick from an
empty collection");
List<T> list = new ArrayList<>(set);
// Non-ordered sets may have different iteration order on different
environments, which would make a seed produce different histories!
// To avoid such a problem, make sure to apply a deterministic
function (sort).
- if (!(set instanceof NavigableSet))
+ if (!isIterationSafe(set))
list.sort(Comparator.naturalOrder());
return pick(list);
}
+ /**
+ * Creates a generator that randomly selects one value from a weighted map.
+ * <p>
+ * Each value is selected with a probability proportional to its
associated weight.
+ * Higher weights increase the likelihood of selection.
+ * <p>
+ * For deterministic behavior, this method requires maps with
deterministic iteration order
+ * like {@link java.util.EnumMap} or {@link java.util.LinkedHashMap}.
+ *
+ * @param <T> the type of values to generate
+ * @param values a map of values to their respective weights
+ * @return a generator that produces values according to their weights
+ * @throws IllegalArgumentException if values is empty or doesn't have
deterministic iteration order
+ */
public static <T> Gen<T> pick(Map<T, Integer> values)
{
if (values == null || values.isEmpty())
throw new IllegalArgumentException("values is empty");
- // if 2 values have the same weight we need some way to tie-break, but
that isn't always possible...
- // this method relies on the map having some order and will reject any
map that doesn't define a deterministic order
- if (!(values instanceof EnumMap || values instanceof LinkedHashMap))
- throw new IllegalArgumentException("pick(Map) requires a map with
deterministic iteration; given " + values.getClass());
+ checkIterationSafe("pick(Map)", values);
if (values.size() == 1)
return
constant(Objects.requireNonNull(Iterables.getFirst(values.keySet(), null)));
double totalWeight =
values.values().stream().mapToDouble(Integer::intValue).sum();
@@ -205,6 +321,41 @@ public class Gens {
};
}
+ private static boolean isIterationSafe(Map<?, ?> values)
+ {
+ return values instanceof EnumMap
+ || values instanceof LinkedHashMap
+ || values instanceof SortedMap;
+ }
+
+ private static boolean isIterationSafe(Set<?> values)
+ {
+ return values instanceof EnumSet
+ || values instanceof LinkedHashSet
+ || values instanceof SortedSet;
+ }
+
+ private static void checkIterationSafe(String name, Map<?, ?> values)
+ {
+ if (!isIterationSafe(values))
+ throw new IllegalArgumentException(name + " requires a map with
deterministic iteration; given " + values.getClass());
+ }
+
+ /**
+ * Creates a generator that selects values from an array using a Zipfian
distribution.
+ * <p>
+ * In a Zipfian distribution, the probability of selecting an element
decreases as its index increases.
+ * The first element has the highest probability of being selected, the
second element has the second-highest
+ * probability, and so on. This is useful for generating skewed data where
some values are much more common than
+ * others.
+ * <p>
+ * The weights follow a power law where {@code weight = base / (i+1)},
creating a harmonic series.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Zipf%27s_law";>Wikipedia</a>
+ * @param array the array to select from
+ * @return a generator that produces values from the array following a
Zipfian distribution
+ * @throws IllegalArgumentException if the array is null or empty
+ */
public static Gen.IntGen pickZipf(int[] array)
{
if (array == null || array.length == 0)
@@ -230,6 +381,21 @@ public class Gens {
};
}
+ /**
+ * Creates a generator that selects values from an array using a Zipfian
distribution.
+ * <p>
+ * In a Zipfian distribution, the probability of selecting an element
decreases as its index increases.
+ * The first element has the highest probability of being selected, the
second element has the second-highest
+ * probability, and so on. This is useful for generating skewed data where
some values are much more common than
+ * others.
+ * <p>
+ * The weights follow a power law where {@code weight = base / (i+1)},
creating a harmonic series.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Zipf%27s_law";>Wikipedia</a>
+ * @param array the array to select from
+ * @return a generator that produces values from the array following a
Zipfian distribution
+ * @throws IllegalArgumentException if the array is null or empty
+ */
public static Gen.LongGen pickZipf(long[] array)
{
if (array == null || array.length == 0)
@@ -255,11 +421,42 @@ public class Gens {
};
}
+ /**
+ * Creates a generator that selects values from an array using a Zipfian
distribution.
+ * <p>
+ * In a Zipfian distribution, the probability of selecting an element
decreases as its index increases.
+ * The first element has the highest probability of being selected, the
second element has the second-highest
+ * probability, and so on. This is useful for generating skewed data where
some values are much more common than
+ * others.
+ * <p>
+ * The weights follow a power law where {@code weight = base / (i+1)},
creating a harmonic series.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Zipf%27s_law";>Wikipedia</a>
+ * @param array the array to select from
+ * @return a generator that produces values from the array following a
Zipfian distribution
+ * @throws IllegalArgumentException if the array is null or empty
+ */
+ @SafeVarargs
public static <T> Gen<T> pickZipf(T... array)
{
return pickZipf(Arrays.asList(array));
}
+ /**
+ * Creates a generator that selects values from a list using a Zipfian
distribution.
+ * <p>
+ * In a Zipfian distribution, the probability of selecting an element
decreases as its index increases.
+ * The first element has the highest probability of being selected, the
second element has the second-highest
+ * probability, and so on. This is useful for generating skewed data where
some values are much more common than
+ * others.
+ * <p>
+ * The weights follow a power law where {@code weight = base / (i+1)},
creating a harmonic series.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Zipf%27s_law";>Wikipedia</a>
+ * @param array the list to select from
+ * @return a generator that produces values from the list following a
Zipfian distribution
+ * @throws IllegalArgumentException if the list is null or empty
+ */
public static <T> Gen<T> pickZipf(List<T> array)
{
if (array == null || array.isEmpty())
@@ -285,10 +482,57 @@ public class Gens {
};
}
+ /**
+ * Creates a generator that produces a subset of the input list.
+ * <p>
+ * Elements are selected randomly from the input list without modifying
it; the subset returned may not reflect
+ * the original order.
+ *
+ * @param <T> the type of elements in the list
+ * @param input the source list to select elements from
+ * @return a generator that produces variable-sized random subsets of the
input list
+ * @throws IndexOutOfBoundsException if sizeGen produces a value outside
the list's range
+ */
public static <T> Gen<List<T>> select(List<T> input)
{
+ return select(input, rs -> rs.nextInt(0, input.size() + 1));
+ }
+
+ /**
+ * Creates a generator that produces a subset of the input list.
+ * <p>
+ * Elements are selected randomly from the input list without modifying
it; the subset returned may not reflect
+ * the original order.
+ *
+ * @param <T> the type of elements in the list
+ * @param input the source list to select elements from
+ * @param size fixed length of how many elements to return
+ * @return a generator that produces fixed-sized random subsets of the
input list
+ * @throws IndexOutOfBoundsException if sizeGen produces a value outside
the list's range
+ */
+ public static <T> Gen<List<T>> select(List<T> input, int size)
+ {
+ return select(input, ignore -> size);
+ }
+
+ /**
+ * Creates a generator that produces a subset of the input list.
+ * <p>
+ * Elements are selected randomly from the input list without modifying
it; the subset returned may not reflect
+ * the original order.
+ *
+ * @param <T> the type of elements in the list
+ * @param input the source list to select elements from
+ * @param sizeGen a generator that determines how many elements to select
+ * @return a generator that produces variable-sized random subsets of the
input list
+ * @throws IndexOutOfBoundsException if sizeGen produces a value outside
the list's range
+ */
+ public static <T> Gen<List<T>> select(List<T> input, Gen.IntGen sizeGen)
+ {
+ if (input.isEmpty()) return constant(input);
return rs -> {
- int size = rs.nextInt(0, input.size() + 1);
+ int size = sizeGen.nextInt(rs);
+ Invariants.requireIndexInBounds(input.size(), 0, size);
List<T> remaining = new ArrayList<>(input);
List<T> list = new ArrayList<>(size);
for (int i = 0; i < size; i++)
@@ -336,6 +580,27 @@ public class Gens {
return i;
}
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from a range. The range is
+ * broken up into {@code numBuckets} sub ranges, and the bucket will be
selected using the distribution strategies.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code int}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param minInclusive value inclusive
+ * @param maxExclusive value exclusive
+ * @param numBuckets how many sub-ranges to create for the top level range
+ * @return a generator of different distribution strategies
+ */
public static Gen<Gen.IntGen> mixedDistribution(int minInclusive, int
maxExclusive, int numBuckets)
{
int domainSize = (maxExclusive - minInclusive);
@@ -365,7 +630,7 @@ public class Gens {
}
case 1: // median biased
{
- int medians[] = new int[bucket.length];
+ int[] medians = new int[bucket.length];
for (int i = 0; i < medians.length; i++)
{
int start = bucket[i];
@@ -386,6 +651,25 @@ public class Gens {
};
}
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from a range.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code int}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param minInclusive value inclusive
+ * @param maxExclusive value exclusive
+ * @return a generator of different distribution strategies
+ */
public static Gen<Gen.IntGen> mixedDistribution(int minInclusive, int
maxExclusive)
{
int domainSize = (maxExclusive - minInclusive + 1);
@@ -448,6 +732,25 @@ public class Gens {
return array;
}
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from a range.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code int}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param minInclusive value inclusive
+ * @param maxExclusive value exclusive
+ * @return a generator of different distribution strategies
+ */
public static Gen<Gen.LongGen> mixedDistribution(long minInclusive, long
maxExclusive)
{
long domainSize = (maxExclusive - minInclusive + 1);
@@ -511,11 +814,50 @@ public class Gens {
return array;
}
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from an array.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code T}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param <T> the type of elements in the array
+ * @param list the array of values to select from
+ * @return a generator of different distribution strategies
+ */
+ @SafeVarargs
public static <T> Gen<Gen<T>> mixedDistribution(T... list)
{
return mixedDistribution(Arrays.asList(list));
}
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from a list.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code T}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param <T> the type of elements in the list
+ * @param list the list of values to select from
+ * @return a generator of different distribution strategies
+ */
public static <T> Gen<Gen<T>> mixedDistribution(List<T> list)
{
return rs -> {
@@ -542,7 +884,25 @@ public class Gens {
};
}
- public static <T> Gen<Gen.IntGen> mixedDistribution(int[] list)
+ /**
+ * Creates a generator that uses different distribution strategies for
selecting items from an array.
+ * <p>
+ * When the top level generator is called it selects what distribution to
use, and returns a generator of {@code int}
+ * that selects from the input using that distribution.
+ * <p>
+ * This method does not document what distributions it can select from,
that way it is free to change (add/remove)
+ * over time; it only maintains the property that the distribution may
change between calls to the top level generator.
+ * <p>
+ * Some sample distribution strategies:
+ * <ul>
+ * <li>Uniform distribution - Each item has equal chance of
selection</li>
+ * <li>Zipfian distribution - Early items are heavily favored, with
probability decreasing by index</li>
+ * </ul>
+ *
+ * @param list the array of values to select from
+ * @return a generator of different distribution strategies
+ */
+ public static Gen<Gen.IntGen> mixedDistribution(int[] list)
{
return rs -> {
switch (rs.nextInt(0, 4))
@@ -654,15 +1014,31 @@ public class Gens {
return RandomSource::nextBoolean;
}
+ /**
+ * Creates a generator that produces boolean values with a target
ratio of true values,
+ * and with true values appearing in contiguous runs of random length.
+ * <p>
+ * This is a stateful generator (not thread safe) that maintains an
approximate ratio of true values by
+ * tracking the counts of true and false values it has generated. It
will produce runs of consecutive true
+ * values up to the specified maximum length to create a more
realistic pattern than
+ * independent random choices.
+ *
+ * @param ratio the target ratio of true values (between 0 and 1)
+ * @param maxRuns the maximum length of consecutive true values in a
run
+ * @return a generator that produces boolean values matching the
specified distribution pattern
+ * @throws IllegalArgumentException if ratio is not between 0 and 1
+ */
public Gen<Boolean> biasedRepeatingRuns(double ratio, int maxRuns)
{
Invariants.requireArgument(ratio > 0 && ratio <= 1, "Expected %d
to be larger than 0 and <= 1", ratio);
double lower = ratio * .8;
double upper = ratio * 1.2;
- return new Gen<Boolean>() {
+ return new Gen<>()
+ {
// run represents how many consecutaive true values should be
returned; -1 implies no active "run" exists
private int run = -1;
private long falseCount = 0, trueCount = 0;
+
@Override
public Boolean next(RandomSource rs)
{
@@ -705,7 +1081,7 @@ public class Gens {
switch (selection)
{
case 0: // uniform 50/50
- return r -> r.nextBoolean();
+ return RandomSource::nextBoolean;
case 1: // variable frequency
var freq = rs.nextFloat();
return r -> r.decide(freq);
@@ -745,11 +1121,18 @@ public class Gens {
return r -> r.nextInt(min, max + 1);
}
+
+ /**
+ * @see Gens#mixedDistribution(int, int)
+ */
public Gen<Gen.IntGen> mixedDistribution(int minInclusive, int
maxExclusive)
{
return Gens.mixedDistribution(minInclusive, maxExclusive);
}
+ /**
+ * @see Gens#mixedDistribution(int, int, int)
+ */
public Gen<Gen.IntGen> mixedDistribution(int minInclusive, int
maxExclusive, int numBuckets)
{
return Gens.mixedDistribution(minInclusive, maxExclusive,
numBuckets);
@@ -785,11 +1168,21 @@ public class Gens {
return pick(klass.getEnumConstants());
}
+ /**
+ * A mixedDistribution using the enum classes values as input to
{@link Gens#mixedDistribution(Object[])}
+ *
+ * @see Gens#mixedDistribution(Object[])
+ */
public <T extends Enum<T>> Gen<Gen<T>> allMixedDistribution(Class<T>
klass)
{
return mixedDistribution(klass.getEnumConstants());
}
+ /**
+ * Creates a generator that randomly selects one value from the enum
values based off a set of weights
+ *
+ * @see #pick(Map)
+ */
public <T extends Enum<T>> Gen<T> allWithWeights(Class<T> klass,
int... weights)
{
T[] constants = klass.getEnumConstants();
@@ -925,11 +1318,13 @@ public class Gens {
}
}
- public static class ArrayDSL<T> implements BaseSequenceDSL<ArrayDSL<T>,
T[]> {
+ public static class ArrayDSL<T> implements BaseSequenceDSL<ArrayDSL<T>,
T[]>
+ {
private final Class<T> type;
private final Gen<T> fn;
- public ArrayDSL(Class<T> type, Gen<T> fn) {
+ public ArrayDSL(Class<T> type, Gen<T> fn)
+ {
this.type = Objects.requireNonNull(type);
this.fn = Objects.requireNonNull(fn);
}
@@ -952,6 +1347,7 @@ public class Gens {
{
Reset.tryReset(fn);
int size = sizeGen.nextInt(r);
+ //noinspection unchecked
T[] list = (T[]) Array.newInstance(type, size);
for (int i = 0; i < size; i++)
list[i] = fn.next(r);
@@ -1075,6 +1471,7 @@ public class Gens {
{
T value = null;
int i;
+ //noinspection StatementWithEmptyBody
for (i = 0; i < 42 && !seen.add((value = fn.next(random)));
i++) {}
if (i == 42) throw IgnoreGenResult.INSTANCE;
return value;
diff --git a/accord-core/src/test/java/accord/utils/Property.java
b/accord-core/src/test/java/accord/utils/Property.java
index eed829ca..92faad08 100644
--- a/accord-core/src/test/java/accord/utils/Property.java
+++ b/accord-core/src/test/java/accord/utils/Property.java
@@ -45,6 +45,8 @@ public class Property
{
public static abstract class Common<T extends Common<T>>
{
+ private static final StackTraceElement[] STACK_TRACE = new
StackTraceElement[0];
+
protected long seed = SeedProvider.instance.nextSeed();
protected int examples = 1000;
@@ -62,12 +64,14 @@ public class Property
this.timeout = other.timeout;
}
+ @SuppressWarnings("unchecked")
public T withSeed(long seed)
{
this.seed = seed;
return (T) this;
}
+ @SuppressWarnings("unchecked")
public T withExamples(int examples)
{
if (examples <= 0)
@@ -76,12 +80,14 @@ public class Property
return (T) this;
}
+ @SuppressWarnings("unchecked")
public T withPure(boolean pure)
{
this.pure = pure;
return (T) this;
}
+ @SuppressWarnings("unchecked")
public T withTimeout(Duration timeout)
{
this.timeout = timeout;
@@ -91,6 +97,7 @@ public class Property
protected void checkWithTimeout(Runnable fn)
{
+ Invariants.nonNull(timeout);
try
{
TimeoutUtils.runBlocking(timeout, "property with timeout",
fn::run);
@@ -106,7 +113,7 @@ public class Property
catch (TimeoutException e)
{
TimeoutException override = new TimeoutException("property
test did not complete within " + this.timeout);
- override.setStackTrace(new StackTraceElement[0]);
+ override.setStackTrace(STACK_TRACE);
throw new PropertyError(propertyError(this, override));
}
}
@@ -405,11 +412,51 @@ public class Property
}
}
+ /**
+ * QuickCheck style testing framework for property based testing
+ * <p>
+ * Examples
+ * <pre>
+ * import static accord.utils.Property.qt;
+ *
+ * // Run a simple property test
+ * qt().check(random -> {
+ * // Test with random values
+ * int value = random.nextInt();
+ * assert someInvariant(value);
+ * });
+ * </pre>
+ * <pre>
+ * import static accord.utils.Property.qt;
+ *
+ * // Run a property test with strings as input
+ * qt().forAll(Gens.strings().ofLengthBetween(0, 100))
+ * .check(str -> {
+ * // Property assertion goes here
+ * });
+ * </pre>
+ */
public static ForBuilder qt()
{
return new ForBuilder();
}
+ /**
+ * QuickCheck style testing framework for stateful property testing
+ * <p>
+ * Examples
+ * <pre>
+ * import static accord.utils.Property.stateful;
+ * import static accord.utils.Property.commands;
+ *
+ * stateful().check(commands(() -> State::new)
+ * .add(create()) // add "create" command with random
weight
+ * .add(read()) // add "read" command with random weight
+ * .add(update()) // add "update" command with random
weight
+ * .add(delete()) // add "delete" command with random
weight
+ * .build());
+ * </pre>
+ */
public static StatefulBuilder stateful()
{
return new StatefulBuilder();
@@ -438,7 +485,7 @@ public class Property
return this;
}
- @SuppressWarnings("rawtypes")
+ @SuppressWarnings({ "rawtypes", "unchecked" })
public <State, SystemUnderTest> void check(Commands<State,
SystemUnderTest> commands)
{
RandomSource rs = new DefaultRandom(seed);
@@ -530,6 +577,7 @@ public class Property
return newHistory;
}
+ @SuppressWarnings({ "rawtypes", "unchecked" })
private <State, SystemUnderTest> void process(Command cmd, State
state, SystemUnderTest sut, int id, @Nullable LongArrayList stepTiming) throws
Throwable
{
if (stepTimeout == null)
@@ -544,7 +592,8 @@ public class Property
}
finally
{
- stepTiming.add(System.nanoTime() - startNanos);
+ if (stepTiming != null)
+ stepTiming.add(System.nanoTime() - startNanos);
}
}
}
@@ -617,11 +666,13 @@ public class Property
}
}
+ @SafeVarargs
public static <State, SystemUnderTest> MultistepCommand<State,
SystemUnderTest> multistep(Command<State, SystemUnderTest, ?>... cmds)
{
return multistep(Arrays.asList(cmds));
}
+ @SuppressWarnings("unchecked")
public static <State, SystemUnderTest> MultistepCommand<State,
SystemUnderTest> multistep(List<Command<State, SystemUnderTest, ?>> cmds)
{
List<Command<State, SystemUnderTest, ?>> result = new
ArrayList<>(cmds.size());
@@ -633,6 +684,7 @@ public class Property
return result::iterator;
}
+ @SuppressWarnings("unchecked")
private static <State, SystemUnderTest> Collection<? extends
Command<State, SystemUnderTest, ?>> flatten(MultistepCommand<State,
SystemUnderTest> mc)
{
List<Command<State, SystemUnderTest, ?>> result = new ArrayList<>();
@@ -644,6 +696,7 @@ public class Property
return result;
}
+ @SuppressWarnings("RedundantThrows")
public interface MultistepCommand<State, SystemUnderTest> extends
Command<State, SystemUnderTest, Object>, Iterable<Command<State,
SystemUnderTest, ?>>
{
@Override
@@ -688,6 +741,7 @@ public class Property
}
}
+ @SuppressWarnings("RedundantThrows")
public static <State, SystemUnderTest, Result> Command<State,
SystemUnderTest, Result> ignoreCommand()
{
return new Command<>()
@@ -718,6 +772,7 @@ public class Property
};
}
+ @SuppressWarnings("RedundantThrows")
public interface UnitCommand<State, SystemUnderTest> extends
Command<State, SystemUnderTest, Void>
{
void applyUnit(State state) throws Throwable;
@@ -736,8 +791,19 @@ public class Property
runUnit(sut);
return null;
}
+
+ @SuppressWarnings("unused")
+ default void checkPostconditions(State state, SystemUnderTest sut)
throws Throwable {}
+
+ @Override
+ default void checkPostconditions(State state, Void expected,
+ SystemUnderTest sut, Void actual)
throws Throwable
+ {
+ checkPostconditions(state, sut);
+ }
}
+ @SuppressWarnings("RedundantThrows")
public interface StateOnlyCommand<State> extends UnitCommand<State, Void>
{
@Override
@@ -807,6 +873,7 @@ public class Property
void onFailure(State state, SystemUnderTest sut, List<String> history,
Throwable cause) throws Throwable;
}
+ @SuppressWarnings("unused")
public static class CommandsBuilder<State, SystemUnderTest>
{
public interface Setup<State, SystemUnderTest>
@@ -1118,13 +1185,13 @@ public class Property
return new Commands<>()
{
@Override
- public Gen<State> genInitialState() throws Throwable
+ public Gen<State> genInitialState()
{
return stateGen.get();
}
@Override
- public SystemUnderTest createSut(State state) throws Throwable
+ public SystemUnderTest createSut(State state)
{
return sutFactory.apply(state);
}
diff --git a/accord-core/src/test/java/accord/utils/README.md
b/accord-core/src/test/java/accord/utils/README.md
new file mode 100644
index 00000000..71d0f4a8
--- /dev/null
+++ b/accord-core/src/test/java/accord/utils/README.md
@@ -0,0 +1,318 @@
+# Property Testing
+
+There are multiple ways to do property testing, and this package provides
different utilities to aid in writing tests.
+
+# Gen
+
+The `Gen` class is the core abstraction for generating random test values in
our property-based testing framework. A `Gen<T>` instance defines how to
produce random values of type `T` using a provided `RandomSource`.
+
+## Core Concepts
+
+### The `Gen` Interface
+
+`Gen<T>` is a functional interface with a single method:
+
+```java
+T generate(RandomSource random);
+```
+
+This method produces a random value of type `T` using the given random source.
+
+### Using `Gens` Utility Class
+
+The `Gens` class provides a comprehensive set of pre-defined generators for
common types:
+
+#### Primitive Types
+- `Gens.bools()`: Generates random boolean values based off a pattern
+- `Gens.ints()`, `Gens.longs()`: Generates random integer/long values based
off a pattern
+- `Gens.enum()`: Generates enum values based off a pattern
+- `Gens.strings()`: Generates strings based off a pattern
+
+#### Collection Generators
+- `Gens.lists(itemGen)`, `Gens.arrays(class, itemGen)`: Lists/arrays of random
items based off a pattern
+
+#### Advanced Generators
+- `Gens.oneOf(T... values)`: Selects randomly from provided values
+- `Gens.constant(value)`: Always generates the same value
+
+#### Meta-Randomness Generators
+
+To put it simply: a generator of generators. These generators define how to
generate randomness itself!
+
+- `Gens.mixedDistribution`: This is a group of functions that will select
values from some range or input, and the selection will be based off a
distribution. When working with these functions the top level `Gen` selects
what distribution to use, and will return a `Gen` that selects values from that
distribution.
+
+### Composing Generators
+
+Generators can be transformed and combined using methods like:
+
+```java
+// Map a generator to a different type
+Gen<String> stringGen = Gens.ints().between(0, 10).map(i -> "Number: " + i);
+
+// Filter generated values
+Gen<Integer> evenNumbers = Gens.ints().between(0, 10).filter(i -> i % 2 == 0);
+```
+
+### Example Usage
+
+```java
+// Generate a random person object
+Gen<String> nameGen = Gens.strings().all().ofLengthBetween(1, 10);
+Gen.IntGen ageGen = Gens.ints().between(18, 100) // IntGen exposes a "nextInt"
function without boxing
+Gen<Person> personGen = rs -> new Person(nameGen.next(rs), ageGen.nextInt(rs));
+
+// Create a more complex generator with bias
+Gen<Person> complexPersonGen = Gens.oneOf(Map.of(
+ youngPersonGen, 3, // 3x weight for young people
+ adultPersonGen, 2, // 2x weight for adults
+ seniorPersonGen, 1 // 1x weight for seniors
+));
+
+enum Level {IC1, IC2, IC3, IC4, IC5, IC6, IC7}
+// Use "meta-randomness" to have your test change the distribution
+Gen<Gen<Level> levelDistribution =
Gens.enums().allMixedDistribution(Level.class);
+// Select the actual distribution for the test
+Gen<Level> levelGen = levelDistribution.next(rs);
+```
+
+# Property-Based Testing with `qt()`
+
+Property-based testing generates random test inputs to validate that certain
properties or invariants of your code hold true regardless of the input values.
The `Property.qt()` method enables this style of testing, similar to libraries
like QuickCheck or QuickTheory.
+
+## Basic Usage
+
+```java
+import static accord.utils.Property.qt;
+
+// Run a simple property test
+qt().check(random -> {
+ // Test with random values
+ int value = random.nextInt();
+ assert someInvariant(value);
+});
+```
+
+```java
+import static accord.utils.Property.qt;
+
+// Run a property test with strings as input
+qt().forAll(Gens.strings().ofLengthBetween(0, 100))
+ .check(str -> {
+ // Property assertion goes here
+ });
+```
+
+## Terms
+
+- `seed` - input to a `RandomSource` for reproducible tests
+- `example` - a single test execution
+- `pure` - does the test have side effects (that might impact the
reproducibility)?
+
+## Main Features
+
+### Core Method: `qt()`
+Returns a `ForBuilder` instance that serves as the starting point for defining
a property test.
+
+### Configuration Methods
+
+- `withSeed(long seed)`: Sets a specific random seed for the test (useful when
retrying failed tests)
+- `withExamples(int count)`: Sets the number of test cases to generate
(default is 1000)
+- `withPure(boolean pure)`: Controls whether to use a fresh random seed for
each example (default is true)
+- `withTimeout(Duration timeout)`: Sets a timeout for test execution
+
+### Test Input Generation
+
+- `forAll(Gen<T> gen)`: Single generator for one parameter
+- `forAll(Gen<A> a, Gen<B> b)`: Two generators for two parameters
+- `forAll(Gen<A> a, Gen<B> b, Gen<C> c)`: Three generators for three parameters
+
+### Execution
+
+- `check(Consumer<T> fn)`: Runs the test with the specified property function
+
+## Error Handling
+
+When a property test fails, the framework creates a detailed error report
including:
+
+- The random seed used (for test reproducibility)
+- Number of examples planned
+- Whether pure mode was enabled
+- The error message and exception
+- The generated values that caused the failure
+
+# Stateful Property-Based Testing with `stateful()`
+
+Stateful property testing allows you to verify that your system behaves
correctly through a sequence of operations. Unlike simple property testing
which validates individual functions, stateful testing models interactions with
a stateful system and verifies that invariants hold throughout operation
sequences.
+
+## Basic Usage
+
+```java
+import static accord.utils.Property.stateful;
+import static accord.utils.Property.commands;
+
+stateful().check(commands(() -> State::new)
+ .add(create()) // add "create" command with random weight
+ .add(read()) // add "read" command with random weight
+ .add(update()) // add "update" command with random weight
+ .add(delete()) // add "delete" command with random weight
+ .build());
+```
+
+## Terms
+
+`stateful` inherits same terms from `qt`, but adds the following
+
+- `State` - state needed by the test to track changes (eg. a model), and/or
utility functions
+- `SystemUnderTest` - the thing that is being tested
+- `command` - a single operation to apply to both the `State` and the
`SystemUnderTest`
+- `step` - one `Command` to execute
+
+For some tests, `SystemUnderTest` is not needed, in which case `State` acts as
both `State` and `SystemUnderTest`.
+
+## Basic Concepts
+
+### Core Method: `stateful()`
+
+The `Property.stateful()` method is the entry point for stateful property
testing, similar to `qt()` for regular property testing, but takes a `Commands`
rather than a lambda; this `Commands` defines what is allowed to happen in the
test.
+
+## Configuration Options
+
+The same configuration options exist as `qt`, but also add the following
+
+- `withSteps(int)`: Maximum number of commands to try per test run (default is
1000)
+- `withStepTimeout(Duration)`: - Max amount of time a single `step` can take.
This method differs from `withTimeout` as it focuses on a single `step` where
as `withTimeout` focuses on the `example`.
+
+### Command
+
+Command consist of three parts:
+1. **Execution**: Apply the `Command` to both the `State` and `SystemUnderTest`
+2. **Verification**: Check that `State` and `SystemUnderTest` maintain a given
set of properties
+3. **Display**: Creates a human readable string about what this Command does
+
+A typical command looks like this:
+
+```java
+class AddItemCommand implements UnitCommand<ShoppingCart, ActualCart>
+{
+ private final Item item;
+
+ public AddItemCommand(Item item)
+ {
+ this.item = item;
+ }
+
+ // Update the model (what we expect to happen)
+ @Override
+ public void applyUnit(ShoppingCart model)
+ {
+ model.add(item);
+ }
+
+ // Apply to the real system
+ @Override
+ public void runUnit(ActualCart sut)
+ {
+ sut.addItem(item);
+ }
+
+ // Verify that model and sut match after command execution
+ @Override
+ public void checkPostconditions(ShoppingCart model, ActualCart sut)
+ {
+ assertEquals(model.getItems(), sut.getItems());
+ }
+
+ // For history logging
+ @Override
+ public String detailed(ShoppingCart model)
+ {
+ return "Add item: " + item;
+ }
+}
+```
+
+But it is common that the test doesn't include a `SystemUnderTest`, in which
case the command would look like
+
+```java
+class AddItemCommand implements StateOnlyCommand<ShoppingCart>
+{
+ private final Item item;
+
+ // Constructor for the command with its parameters
+ public AddItemCommand(Item item)
+ {
+ this.item = item;
+ }
+
+ // Update the model (what we expect to happen)
+ @Override
+ public void applyUnit(ShoppingCart model)
+ {
+ model.add(item);
+ // verify anything needed
+ }
+
+ // For history logging
+ @Override
+ public String detailed(ShoppingCart model)
+ {
+ return "Add item: " + item;
+ }
+}
+```
+
+Or can use `SimpleCommand` instead
+
+```java
+Item item = ...
+new SimpleCommand<>("Add item: " + item, state -> state.add(item));
+```
+
+### Commands
+
+`Commands` represent a set of `Command` that can be performed on both the
`State` and `SystemUnderTest`.
+
+- `genInitialState` - called at the start of each "example", and creates a new
`State`
+- `createSut(state)` - called at the start of each "example", and creates a
new `SystemUnderTest` from the provided `State`
+- `destroyState(state, @Nullable cause)`, `destroySut(sut, @Nullable cause)` -
called at the end of each "example" to allow closing resources
+- `commands(state)` - called at each "attempt" to create a generator of
`Command`.
+
+## Commands Builder
+
+The framework provides a `Commands` builder to simplify `Commands` generation:
+
+```java
+commands(() -> State::new, Sut::new)
+// Add command with fixed weight
+.add(3, (rs, state) -> new AddItemCommand(Gens.items().next()))
+// Add command with random weights! At the start of each example, the weight
is computed; each example will run with different weights
+// Should default to this method over explicit weights
+.add((rs, state) -> new RemoveItemCommand())
+// Add conditional command
+.addIf(state -> !state.isEmpty(),
+ (rs, state) -> new CheckoutCommand())
+.build();
+```
+
+## Error Reporting
+
+When a stateful test fails, the framework provides detailed information:
+- The command sequence that led to the failure
+- The random seed for reproducibility
+- The specific command that failed
+- The exception and error message
+
+## Example: Testing a Queue Implementation
+
+```java
+stateful()
+ .check(commands(() -> MyQueueImplementation::<>new)
+ .add((rs, state) -> new EnqueueCommand<>(Gens.ints().all().next(rs)))
+ .addIf(state -> !state.isEmpty(),
+ (rs, state) -> new DequeueCommand<>())
+ .addIf(state -> !state.isEmpty(),
+ (rs, state) -> new PeekCommand<>())
+ .build());
+```
+
+This will generate and run sequences of queue operations, automatically
checking that your implementation behaves correctly.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
