summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCarlo Zancanaro <carlo@zancanaro.id.au>2015-06-03 19:43:14 +1000
committerCarlo Zancanaro <carlo@zancanaro.id.au>2015-06-03 19:43:14 +1000
commite0fc94269698982d937b80ff5fd5b1ef8ef28cf4 (patch)
tree22c335361971363d6856a59ef0c54242f92e74e1
parent7b1a783b749ab04ab8219ef28f9b1abb0ded6ca4 (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.
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/Generator.java32
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java4
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/Generators.java147
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java7
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java44
-rw-r--r--src/main/java/au/id/zancanaro/javacheck/junit/Properties.java4
-rw-r--r--src/test/java/au/id/zancanaro/javacheck/ListFunctorRulesTest.java61
-rw-r--r--src/test/java/au/id/zancanaro/javacheck/SimpleListOperationsTest.java1
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;