diff options
author | Carlo Zancanaro <carlo@zancanaro.id.au> | 2015-06-03 19:43:14 +1000 |
---|---|---|
committer | Carlo Zancanaro <carlo@zancanaro.id.au> | 2015-06-03 19:43:14 +1000 |
commit | e0fc94269698982d937b80ff5fd5b1ef8ef28cf4 (patch) | |
tree | 22c335361971363d6856a59ef0c54242f92e74e1 | |
parent | 7b1a783b749ab04ab8219ef28f9b1abb0ded6ca4 (diff) |
Change shrinking a bit, add more generators, fix some types, moved suchThat
Shrinking is now done using a "ShrinkStrategy". It's pretty similar to what it
used to be in the end, but instead of generating new ShrinkTree<T>s yourself,
you just generate smaller <T>s, and the generator framework will re-call your
strategy to shrink smaller elements. (So, essentially, ShrinkStrategy.shrink(T
obj) returns an Iterator<T> which then has smaller trees calculated from it.)
Added some more generators. In particular: longs and doubles.
Fixed some types, so now Generator.tuple(integer(), string()) will work. Yay!
Move suchThat to Generator, so now integer().suchThat(x -> x < 10) will work
instead of the old Generators.suchThat(x -> x < 10, integer()), which felt a
bit weird.
8 files changed, 214 insertions, 86 deletions
diff --git a/src/main/java/au/id/zancanaro/javacheck/Generator.java b/src/main/java/au/id/zancanaro/javacheck/Generator.java index 9d88020..103bc69 100644 --- a/src/main/java/au/id/zancanaro/javacheck/Generator.java +++ b/src/main/java/au/id/zancanaro/javacheck/Generator.java @@ -4,6 +4,7 @@ import java.util.Iterator; import java.util.List; import java.util.Random; import java.util.function.Function; +import java.util.function.Predicate; /** * Generators are a way of producing random objects and their associated shrink @@ -63,13 +64,13 @@ public interface Generator<T> { * @return A {@link Generator} returning a {@link List} */ @SafeVarargs - static <T> Generator<List<T>> tuple(Generator<T>... generators) { + static <T> Generator<List<T>> tuple(Generator<? extends T>... generators) { return (random, size) -> { @SuppressWarnings("unchecked") ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[generators.length]; int index = 0; - for (Generator<T> generator : generators) { - result[index++] = generator.generate(random, size); + for (Generator<? extends T> generator : generators) { + result[index++] = generator.generate(random, size).map(x -> (T) x); } return ShrinkTree.zip(Function.identity(), result); }; @@ -130,6 +131,31 @@ public interface Generator<T> { return (random, size) -> ShrinkTree.join(this.generate(random, size).map(action).map(g -> g.generate(random, size))); } + /** + * Filter the results of this generator to only those matching a given + * predicate. + * + * suchThat will keep trying the generator until either it provides a valid + * value, or a stack overflow error occurs. + * + * <b>Only use this method with predicates which are very likely to + * match.</b> + * + * @param predicate The predicate to match + * @return A new generator resulting from filtering this generator to only + * terms which match the given predicate + */ + default Generator<T> suchThat(Predicate<T> predicate) { + return (random, size) -> { + ShrinkTree<T> result = this.generate(random, size); + if (predicate.test(result.getValue())) { + return result.filter(predicate); + } else { + return this.suchThat(predicate).generate(random, size); + } + }; + } + default Iterator<T> sample(Random random, int maxSize) { return new GeneratorSampleIterator<>(this, random, maxSize); } diff --git a/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java b/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java index f7d8e17..6101d4a 100644 --- a/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java +++ b/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java @@ -3,7 +3,7 @@ package au.id.zancanaro.javacheck; import java.util.Iterator; import java.util.Random; -public class GeneratorSampleIterator<T> implements Iterator<T> { +class GeneratorSampleIterator<T> implements Iterator<T> { private final Generator<T> generator; private final Random random; private final int maxSize; @@ -24,7 +24,7 @@ public class GeneratorSampleIterator<T> implements Iterator<T> { @Override public T next() { return generator - .generate(random, Math.min(size++, maxSize)) + .generate(random, size = Math.min(size + 1, maxSize)) .getValue(); } } diff --git a/src/main/java/au/id/zancanaro/javacheck/Generators.java b/src/main/java/au/id/zancanaro/javacheck/Generators.java index 5dee924..e5699ac 100644 --- a/src/main/java/au/id/zancanaro/javacheck/Generators.java +++ b/src/main/java/au/id/zancanaro/javacheck/Generators.java @@ -1,41 +1,40 @@ package au.id.zancanaro.javacheck; -import java.util.Arrays; -import java.util.Collections; -import java.util.Iterator; -import java.util.List; +import java.util.*; import java.util.function.Function; -import java.util.function.Predicate; -@SuppressWarnings("unused") +@SuppressWarnings({"unused", "WeakerAccess"}) public final class Generators { private Generators() { } + /** + * Create a generator which explicitly depends on the current "size" + * parameter. + * + * @param makeGenerator A function from size to a generator + * @param <T> The static type of the returned generator + * @return The generator returned by makeGenerator + */ public static <T> Generator<T> sized(Function<Integer, Generator<T>> makeGenerator) { return (random, size) -> makeGenerator.apply(size).generate(random, size); } - public static <T> Generator<T> suchThat(Generator<T> gen, Predicate<T> predicate) { - return (random, size) -> { - ShrinkTree<T> result = gen.generate(random, size); - if (predicate.test(result.getValue())) { - return result.filter(predicate); - } else { - return suchThat(gen, predicate).generate(random, size); - } - }; - } - + /** + * Remove a generator's shrink tree. + * + * @param gen The generator + * @param <T> The generator's static type + * @return A new generator which is the previous generator with shrink tree + * removed + */ public static <T> Generator<T> noShrink(Generator<T> gen) { - return (random, size) -> new ShrinkTree<>( - gen.generate(random, size).getValue(), - Collections.emptyList()); + return (random, size) -> ShrinkTree.pure(gen.generate(random, size).getValue()); } @SafeVarargs - public static <T> Generator<T> oneOf(Generator<T>... gens) { - return integer(0, gens.length).flatMap(index -> gens[index]); + public static <T> Generator<T> oneOf(Generator<? extends T>... gens) { + return integer(0, gens.length).flatMap(index -> gens[index].map(x -> (T) x)); } public static <T> Generator<T> elements(T[] elements) { @@ -48,16 +47,67 @@ public final class Generators { public static Generator<Boolean> bool() { return (random, size) -> - random.nextBoolean() ? - new ShrinkTree<>(true, Collections.singletonList(new ShrinkTree<>(false, Collections.emptyList()))) : - new ShrinkTree<>(false, Collections.emptyList()); + ShrinkTree.pure(random.nextBoolean()) + .withShrinkStrategy(boolShrinkStrategy()); + } + + private static ShrinkStrategy<Boolean> boolShrinkStrategy() { + return value -> new Iterator<Boolean>() { + boolean hasMore = value; + + @Override + public boolean hasNext() { + return hasMore; + } + + @Override + public Boolean next() { + if (hasMore) { + return (hasMore = false); + } else { + throw new NoSuchElementException("Boolean shrink tree exhausted"); + } + } + }; + } + + public static Generator<Long> longInteger(long lower, long upper) { + return (random, size) -> { + long value = random.longs(lower, upper).findFirst().getAsLong(); + long bound = lower > 0 ? lower : (upper < 0 ? upper : 0); + return ShrinkTree.pure(value) + .withShrinkStrategy(longShrinkStrategy(bound)); + }; + } + + public static Generator<Long> longInteger() { + return sized(size -> longInteger(-size, size)); + } + + private static ShrinkStrategy<Long> longShrinkStrategy(final long bound) { + return value -> new Iterator<Long>() { + long curr = value - bound; + + @Override + public boolean hasNext() { + return curr != 0; + } + + @Override + public Long next() { + long prevCurr = curr; + curr = curr / 2; + return value - prevCurr; + } + }; } public static Generator<Integer> integer(int lower, int upper) { return (random, size) -> { - int value = lower + random.nextInt(upper - lower); + int value = random.ints(lower, upper).findFirst().getAsInt(); int bound = lower > 0 ? lower : (upper < 0 ? upper : 0); - return new ShrinkTree<>(value, intShrinkingIterable(value, bound)); + return ShrinkTree.pure(value) + .withShrinkStrategy(intShrinkStrategy(bound)); }; } @@ -69,8 +119,8 @@ public final class Generators { return sized(size -> integer(0, size)); } - private static Iterable<ShrinkTree<Integer>> intShrinkingIterable(final int value, final int bound) { - return () -> new Iterator<ShrinkTree<Integer>>() { + public static ShrinkStrategy<Integer> intShrinkStrategy(int bound) { + return value -> new Iterator<Integer>() { int curr = value - bound; @Override @@ -79,10 +129,41 @@ public final class Generators { } @Override - public ShrinkTree<Integer> next() { + public Integer next() { int prevCurr = curr; curr = curr / 2; - return new ShrinkTree<>(value - prevCurr, intShrinkingIterable(value - prevCurr, bound)); + return value - prevCurr; + } + }; + } + + public static Generator<Double> doublePrecision(double lower, double upper) { + return (random, size) -> { + double value = random.doubles(lower, upper).findFirst().getAsDouble(); + double bound = lower > 0 ? lower : (upper < 0 ? upper : 0); + return ShrinkTree.pure(value) + .withShrinkStrategy(doubleShrinkStrategy(bound, Double.MIN_NORMAL /* maybe pick a bigger epsilon? */)); + }; + } + + public static Generator<Double> doublePrecision() { + return sized(size -> doublePrecision(-size, size)); + } + + public static ShrinkStrategy<Double> doubleShrinkStrategy(double bound, double epsilon) { + return value -> new Iterator<Double>() { + double curr = value - bound; + + @Override + public boolean hasNext() { + return Math.abs(curr) > epsilon; + } + + @Override + public Double next() { + double prevCurr = curr; + curr = curr / 2; + return value - prevCurr; } }; } @@ -93,9 +174,7 @@ public final class Generators { int count = countGen.generate(random, size).getValue(); return Generator.list(count, gen) .generate(random, size) - .filter(list -> - minElements <= list.size() - && list.size() < maxElements) + .filter(list -> minElements <= list.size() && list.size() < maxElements) .map(Collections::unmodifiableList); }; } diff --git a/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java b/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java new file mode 100644 index 0000000..6bd1eb9 --- /dev/null +++ b/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java @@ -0,0 +1,7 @@ +package au.id.zancanaro.javacheck; + +import java.util.Iterator; + +interface ShrinkStrategy<T> { + Iterator<T> shrink(T obj); +} diff --git a/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java index a424806..7dff917 100644 --- a/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java +++ b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java @@ -2,16 +2,21 @@ package au.id.zancanaro.javacheck; import java.io.IOException; import java.io.Writer; -import java.util.*; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; import java.util.function.Function; import java.util.function.Predicate; +import static au.id.zancanaro.javacheck.Iterators.*; + @SuppressWarnings("unused") public class ShrinkTree<T> { private final T value; private final Iterable<ShrinkTree<T>> children; - public ShrinkTree(T value, Iterable<ShrinkTree<T>> children) { + private ShrinkTree(T value, Iterable<ShrinkTree<T>> children) { this.value = value; this.children = children; } @@ -31,15 +36,15 @@ public class ShrinkTree<T> { public static <T> ShrinkTree<T> join(ShrinkTree<ShrinkTree<T>> tree) { return new ShrinkTree<>( tree.getValue().getValue(), - () -> Iterators.concat( - Iterators.mappingIterator(ShrinkTree::join, tree.children.iterator()), + () -> concat( + mappingIterator(ShrinkTree::join, tree.children.iterator()), tree.getValue().children.iterator())); } private static <T> Iterator<ShrinkTree<T>[]> permutations(ShrinkTree<T>[] trees) { - return Iterators.flatten( - Iterators.rangeIterator(trees.length, - index -> Iterators.mappingIterator(child -> { + return flatten( + rangeIterator(trees.length, + index -> mappingIterator(child -> { @SuppressWarnings("unchecked") ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[trees.length]; for (int i = 0; i < trees.length; ++i) { @@ -61,14 +66,14 @@ public class ShrinkTree<T> { public static <T, R> ShrinkTree<R> zip(Function<List<T>, R> fn, ShrinkTree<T>[] trees) { return new ShrinkTree<>( fn.apply(makeHeadList(trees)), - () -> Iterators.mappingIterator( + () -> mappingIterator( shrinks -> ShrinkTree.zip(fn, shrinks), ShrinkTree.permutations(trees))); } private static <T> Iterator<ShrinkTree<T>[]> removeEach(ShrinkTree<T>[] trees) { - return Iterators.concat( - Iterators.rangeIterator(trees.length, index -> { + return concat( + rangeIterator(trees.length, index -> { @SuppressWarnings("unchecked") ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[trees.length - 1]; for (int i = 0; i < trees.length - 1; ++i) { @@ -82,7 +87,7 @@ public class ShrinkTree<T> { public static <T, R> ShrinkTree<R> shrink(Function<List<T>, R> fn, ShrinkTree<T>[] trees) { return new ShrinkTree<>( fn.apply(makeHeadList(trees)), - () -> Iterators.mappingIterator( + () -> mappingIterator( shrinks -> ShrinkTree.shrink(fn, shrinks), ShrinkTree.removeEach(trees))); } @@ -90,7 +95,7 @@ public class ShrinkTree<T> { public <R> ShrinkTree<R> map(Function<T, R> f) { return new ShrinkTree<>( f.apply(this.value), - () -> Iterators.mappingIterator(tree -> tree.map(f), this.children.iterator())); + () -> mappingIterator(tree -> tree.map(f), this.children.iterator())); } public <R> ShrinkTree<R> flatMap(Function<T, ShrinkTree<R>> f) { @@ -101,8 +106,8 @@ public class ShrinkTree<T> { if (predicate.test(this.getValue())) { return new ShrinkTree<>( this.getValue(), - () -> Iterators.mappingIterator(tree -> tree.filter(predicate), - Iterators.filteringIterator( + () -> mappingIterator(tree -> tree.filter(predicate), + filteringIterator( tree -> predicate.test(tree.getValue()), this.getChildren()))); } else { @@ -110,6 +115,17 @@ public class ShrinkTree<T> { } } + public ShrinkTree<T> withShrinkStrategy(ShrinkStrategy<T> strategy) { + return new ShrinkTree<>(this.getValue(), strategyIterable(this.getValue(), strategy)); + } + + private static <T> Iterable<ShrinkTree<T>> strategyIterable(final T value, final ShrinkStrategy<T> strategy) { + return () -> + mappingIterator( + v -> new ShrinkTree<>(v, strategyIterable(v, strategy)), + strategy.shrink(value)); + } + @SuppressWarnings("unused") public void print(Writer output) throws IOException { print(output, Object::toString); diff --git a/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java b/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java index b1cb375..ab56374 100644 --- a/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java +++ b/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java @@ -1,8 +1,8 @@ package au.id.zancanaro.javacheck.junit; import au.id.zancanaro.javacheck.Generator; -import au.id.zancanaro.javacheck.ShrinkTree; import au.id.zancanaro.javacheck.ShrinkResult; +import au.id.zancanaro.javacheck.ShrinkTree; import au.id.zancanaro.javacheck.annotations.DataSource; import au.id.zancanaro.javacheck.annotations.Property; import au.id.zancanaro.javacheck.annotations.Seed; @@ -48,7 +48,7 @@ public class Properties extends BlockJUnit4ClassRunner { } Type type = field.getGenericType(); - ParameterizedType parameterizedType;; + ParameterizedType parameterizedType; if (type instanceof ParameterizedType) { parameterizedType = (ParameterizedType) type; if (parameterizedType.getRawType() instanceof Class) { diff --git a/src/test/java/au/id/zancanaro/javacheck/ListFunctorRulesTest.java b/src/test/java/au/id/zancanaro/javacheck/ListFunctorRulesTest.java index 4e516a2..b757bcd 100644 --- a/src/test/java/au/id/zancanaro/javacheck/ListFunctorRulesTest.java +++ b/src/test/java/au/id/zancanaro/javacheck/ListFunctorRulesTest.java @@ -19,27 +19,27 @@ public class ListFunctorRulesTest { private final static int maxSize = 1000; @DataSource - public static Generator<List<Integer>> listOfIntegers = listOf(integer()); + public static Generator<List<Long>> listOfIntegers = listOf(longInteger()); @DataSource - public static Generator<Function<Integer, Integer>> integerFunction = + public static Generator<Function<Long, Long>> integerFunction = oneOf( - integer().map(ListFunctorRulesTest::plusI), - integer().map(ListFunctorRulesTest::timesI), - integer().map(ListFunctorRulesTest::constantlyI)); + longInteger().map(ListFunctorRulesTest::plusI), + longInteger().map(ListFunctorRulesTest::timesI), + longInteger().map(ListFunctorRulesTest::constantlyI)); @Property(maxSize = maxSize, runs = runs) public void mappingCompositionsWithStreams( - List<Integer> list, - Function<Integer, Integer> f, - Function<Integer, Integer> g) { - List<Integer> left = list.stream() + List<Long> list, + Function<Long, Long> f, + Function<Long, Long> g) { + List<Long> left = list.stream() .map(g) .map(f) .collect(Collectors.toList()); - List<Integer> right = list.stream() - .map(x -> f.apply(g.apply(x))) + List<Long> right = list.stream() + .map(f.compose(g)) .collect(Collectors.toList()); assertEquals(left, right); @@ -47,30 +47,30 @@ public class ListFunctorRulesTest { @Property(maxSize = maxSize, runs = runs) public void mappingCompositionsWithIntermediateList( - List<Integer> list, - Function<Integer, Integer> f, - Function<Integer, Integer> g) { - List<Integer> intermediate = list.stream().map(g).collect(Collectors.toList()); - List<Integer> left = intermediate.stream().map(f).collect(Collectors.toList()); - - List<Integer> right = list.stream() - .map(x -> f.apply(g.apply(x))) + List<Long> list, + Function<Long, Long> f, + Function<Long, Long> g) { + List<Long> intermediate = list.stream().map(g).collect(Collectors.toList()); + List<Long> left = intermediate.stream().map(f).collect(Collectors.toList()); + + List<Long> right = list.stream() + .map(f.compose(g)) .collect(Collectors.toList()); assertEquals(left, right); } @Property(maxSize = maxSize, runs = runs) - public void mapIdentityIsIdentity(List<Integer> list) { - List<Integer> mapped = list.stream().map(x -> x).collect(Collectors.toList()); + public void mapIdentityIsIdentity(List<Long> list) { + List<Long> mapped = list.stream().map(x -> x).collect(Collectors.toList()); assertEquals(list, mapped); } - private static Function<Integer,Integer> plusI(final int i) { - return new Function<Integer, Integer>() { + private static Function<Long, Long> plusI(final long i) { + return new Function<Long, Long>() { @Override - public Integer apply(Integer integer) { + public Long apply(Long integer) { return i + integer; } @@ -81,10 +81,10 @@ public class ListFunctorRulesTest { }; } - private static Function<Integer,Integer> timesI(final int i) { - return new Function<Integer, Integer>() { + private static Function<Long, Long> timesI(final long i) { + return new Function<Long, Long>() { @Override - public Integer apply(Integer integer) { + public Long apply(Long integer) { return i * integer; } @@ -94,10 +94,11 @@ public class ListFunctorRulesTest { } }; } - private static Function<Integer,Integer> constantlyI(final int i) { - return new Function<Integer, Integer>() { + + private static Function<Long, Long> constantlyI(final long i) { + return new Function<Long, Long>() { @Override - public Integer apply(Integer integer) { + public Long apply(Long integer) { return i; } diff --git a/src/test/java/au/id/zancanaro/javacheck/SimpleListOperationsTest.java b/src/test/java/au/id/zancanaro/javacheck/SimpleListOperationsTest.java index 972b5b6..8f7b075 100644 --- a/src/test/java/au/id/zancanaro/javacheck/SimpleListOperationsTest.java +++ b/src/test/java/au/id/zancanaro/javacheck/SimpleListOperationsTest.java @@ -1,6 +1,5 @@ package au.id.zancanaro.javacheck; -import au.id.zancanaro.javacheck.Generator; import au.id.zancanaro.javacheck.annotations.DataSource; import au.id.zancanaro.javacheck.annotations.Property; import au.id.zancanaro.javacheck.junit.Properties; |