8 files changed, 474 insertions, 0 deletions
diff --git a/src/main/java/au/id/zancanaro/Generator.java b/src/main/java/au/id/zancanaro/Generator.java
new file mode 100644
index 0000000..4b80e51
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/Generator.java
@@ -0,0 +1,51 @@
+package au.id.zancanaro;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+import java.util.function.Function;
+
+public interface Generator<T> {
+    RoseTree<T> generate(Random random, int size);
+
+    static <T> Generator<T> pure(T value) {
+        return (random, size) -> RoseTree.pure(value);
+    }
+
+    default <R> Generator<R> genFlatmap(Function<RoseTree<T>, Generator<R>> f) {
+        return (random, size) -> {
+            RoseTree<T> inner = this.generate(random, size);
+            Generator<R> generator = f.apply(inner);
+            return generator.generate(random, size);
+        };
+    }
+
+    default <R> Generator<R> genFmap(Function<RoseTree<T>, RoseTree<R>> f) {
+        return (random, size) -> f.apply(this.generate(random, size));
+    }
+
+    @SafeVarargs
+    static <T> Generator<T[]> tuple(Generator<T>... generators) {
+        return (random, size) -> {
+            @SuppressWarnings("unchecked")
+            RoseTree<T>[] result = (RoseTree<T>[]) new RoseTree[generators.length];
+            int index = 0;
+            for (Generator<T> generator : generators) {
+                result[index++] = generator.generate(random, size);
+            }
+            return RoseTree.zip(Function.identity(), result);
+        };
+    }
+
+    default <R> Generator<R> fmap(Function<T, R> f) {
+        return (random, size) -> this.generate(random, size).fmap(f);
+    }
+
+    default <R> Generator<R> flatMap(Function<T, Generator<R>> action) {
+        return this.genFlatmap(rose -> {
+            Generator<RoseTree<R>> generator = (random, size) ->
+                    rose.fmap(action).fmap(g -> g.generate(random, size));
+            return generator.<R>genFmap(RoseTree::join);
+        });
+    }
+}
diff --git a/src/main/java/au/id/zancanaro/Generators.java b/src/main/java/au/id/zancanaro/Generators.java
new file mode 100644
index 0000000..f065d1d
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/Generators.java
@@ -0,0 +1,35 @@
+package au.id.zancanaro;
+
+import java.util.Iterator;
+
+public class Generators {
+    @SafeVarargs
+    public static <T> Generator<T[]> arrayGenerator(Generator<? extends T>... generators) {
+        return Generator.tuple((Generator<T>[]) generators);
+    }
+
+    public static Generator<Integer> integerGenerator() {
+        return (random, size) -> {
+            int value = random.nextInt(size);
+            return new RoseTree<>(value, intShrinkingIterable(value));
+        };
+    }
+
+    private static Iterable<RoseTree<Integer>> intShrinkingIterable(final int value) {
+        return () -> new Iterator<RoseTree<Integer>>() {
+            int curr = value;
+
+            @Override
+            public boolean hasNext() {
+                return curr > 0;
+            }
+
+            @Override
+            public RoseTree<Integer> next() {
+                int prevCurr = curr;
+                curr = curr / 2;
+                return new RoseTree<>(value - prevCurr, intShrinkingIterable(value - prevCurr));
+            }
+        };
+    }
+}
diff --git a/src/main/java/au/id/zancanaro/Iterators.java b/src/main/java/au/id/zancanaro/Iterators.java
new file mode 100644
index 0000000..b879c76
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/Iterators.java
@@ -0,0 +1,130 @@
+package au.id.zancanaro;
+
+import java.util.Iterator;
+import java.util.function.Function;
+
+public final class Iterators {
+    public static <T> RangeIterator<T> rangeIterator(int countTo, Function<Integer,T> fn) {
+        return new RangeIterator<T>(countTo, fn);
+    }
+
+    private static class RangeIterator<T> implements Iterator<T> {
+        private final Function<Integer, T> action;
+        private final int countTo;
+        private int index = 0;
+
+        public RangeIterator(int countTo, Function<Integer, T> action) {
+            this.countTo = countTo;
+            this.action = action;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return index < countTo;
+        }
+
+        @Override
+        public T next() {
+            return action.apply(index++);
+        }
+    }
+
+    public static <T> FlattenIterator<T> flatten(Iterator<Iterator<T>> iterators) {
+        return new FlattenIterator<>(iterators);
+    }
+    public static class FlattenIterator<T> implements Iterator<T> {
+        private Iterator<T> current;
+
+        private Iterator<Iterator<T>> iterators;
+
+        public FlattenIterator(Iterator<Iterator<T>> iterators) {
+            this.current = Iterators.emptyIterator();
+            this.iterators = iterators;
+        }
+
+        private Iterator<T> getCurrent() {
+            while (!current.hasNext() && iterators.hasNext()) {
+                current = iterators.next();
+            }
+            return current;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return getCurrent().hasNext();
+        }
+        @Override
+        public T next() {
+            return getCurrent().next();
+        }
+
+    }
+
+    public static <T> ConcatIterator<T> concat(Iterator<T> left, Iterator<T> right) {
+        return new ConcatIterator<>(left, right);
+    }
+    public static class ConcatIterator<T> implements Iterator<T> {
+        private final Iterator<T> left;
+
+        private final Iterator<T> right;
+
+        public ConcatIterator(Iterator<T> left, Iterator<T> right) {
+            this.left = left;
+            this.right = right;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return left.hasNext() || right.hasNext();
+        }
+        @Override
+        public T next() {
+            if (left.hasNext()) {
+                return left.next();
+            } else {
+                return right.next();
+            }
+        }
+
+    }
+
+    public static <T> EmptyIterator<T> emptyIterator() {
+        return new EmptyIterator<>();
+    }
+    public static class EmptyIterator<T> implements Iterator<T> {
+
+        @Override
+        public boolean hasNext() {
+            return false;
+        }
+        @Override
+        public T next() {
+            return null;
+        }
+
+    }
+
+    public static <T,R> MappingIterator<T,R> mappingIterator(Function<T,R> f, Iterator<T> iterator) {
+        return new MappingIterator<>(f, iterator);
+    }
+    private static class MappingIterator<T, R> implements Iterator<R> {
+        private final Function<T, R> mapping;
+
+        private final Iterator<T> iterator;
+
+        public MappingIterator(Function<T, R> mapping, Iterator<T> iterator) {
+            this.mapping = mapping;
+            this.iterator = iterator;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return iterator.hasNext();
+        }
+        @Override
+        public R next() {
+            return mapping.apply(iterator.next());
+        }
+
+    }
+}
diff --git a/src/main/java/au/id/zancanaro/PropertyTestRunner.java b/src/main/java/au/id/zancanaro/PropertyTestRunner.java
new file mode 100644
index 0000000..fc90b8e
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/PropertyTestRunner.java
@@ -0,0 +1,153 @@
+package au.id.zancanaro;
+
+import au.id.zancanaro.annotations.Property;
+import au.id.zancanaro.annotations.Seed;
+import junit.framework.AssertionFailedError;
+import org.junit.AssumptionViolatedException;
+import org.junit.runner.Description;
+import org.junit.runner.Runner;
+import org.junit.runner.notification.Failure;
+import org.junit.runner.notification.RunNotifier;
+
+import java.lang.annotation.Annotation;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.lang.reflect.Type;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Random;
+
+public class PropertyTestRunner extends Runner {
+    private final Class<?> classUnderTest;
+
+    public PropertyTestRunner(Class<?> classUnderTest) {
+        this.classUnderTest = classUnderTest;
+    }
+
+    @Override
+    public Description getDescription() {
+        return Description.createSuiteDescription(classUnderTest);
+    }
+
+    private long getSeed(Method method) {
+        Seed seed = method.getAnnotation(Seed.class);
+        if (seed == null) {
+            return System.currentTimeMillis();
+        } else {
+            return seed.value();
+        }
+    }
+
+    @Override
+    public void run(RunNotifier notifier) {
+        Method[] methods = classUnderTest.getMethods();
+        for (Method method : methods) {
+            Property details = method.getAnnotation(Property.class);
+            if (details != null) {
+                Description description = Description.createTestDescription(classUnderTest, method.getName());
+                boolean failed = false;
+                int assumptionsFailed = 0;
+
+                long seed = getSeed(method);
+                Random random = new Random(seed);
+                int numRuns = details.runs();
+                for (int i = 0; i < numRuns && !failed; ++i) {
+                    int size = details.size();
+                    notifier.fireTestStarted(description);
+                    Object obj;
+                    try {
+                        obj = classUnderTest.getConstructor().newInstance();
+                    } catch (Throwable ex) { // HACKY
+                        System.out.println(ex);
+                        return;
+                    }
+                    RoseTree<Object[]> generated = generateArgs(random, size,
+                            method.getGenericParameterTypes(),
+                            method.getParameterAnnotations());
+                    try {
+                        method.invoke(obj, generated.getValue());
+                    } catch (InvocationTargetException ex) {
+                        if (ex.getTargetException() instanceof AssumptionViolatedException) {
+                            assumptionsFailed++;
+                        } else {
+                            notifier.fireTestFailure(new Failure(description, ex.getTargetException()));
+                            System.out.println("Test failed with seed: " + seed);
+                            System.out.println("Failing arguments: " + Arrays.asList(generated.getValue()));
+                            Object[] shrinkResult = shrink(method, obj, generated);
+                            if (shrinkResult == null) {
+                                System.out.println("Arguments could not be shrunk any further");
+                            } else {
+                                System.out.println("Arguments shrunk to: " + Arrays.asList(shrinkResult));
+                            }
+                            failed = true;
+                        }
+                    } catch (IllegalAccessException ex) {
+                        notifier.fireTestFailure(new Failure(description, ex));
+                        failed = true;
+                    }
+                }
+
+                if (assumptionsFailed > 0) {
+                    System.out.println("Failed " + assumptionsFailed + " assumptions");
+                }
+                notifier.fireTestFinished(description);
+            }
+        }
+    }
+
+    private Object[] shrink(Method method, Object obj, RoseTree<Object[]> failed) {
+        Object[] smallest = failed.getValue();
+        Iterator<RoseTree<Object[]>> trees = failed.getChildren();
+        while (trees.hasNext()) {
+            RoseTree<Object[]> tree = trees.next();
+            try {
+                method.invoke(obj, tree.getValue());
+            } catch (Throwable ex) {
+                Iterator<RoseTree<Object[]>> children = tree.getChildren();
+                if (children.hasNext()) {
+                    trees = children;
+                }
+                smallest = tree.getValue();
+            }
+        }
+        return smallest;
+    }
+
+    private <T> String printShrinkTree(RoseTree<T[]> generated) {
+        StringBuilder builder = new StringBuilder();
+        builder.append('(');
+        builder.append(Arrays.toString(generated.getValue()));
+        generated.getChildren().forEachRemaining((child) -> {
+            builder.append(' ');
+            builder.append(printShrinkTree(child));
+        });
+        builder.append(')');
+        return builder.toString();
+    }
+
+
+    private RoseTree<Object[]> generateArgs(Random random, int size, Type[] types, Annotation[][] annotations) {
+        Generator<?>[] generators = new Generator[types.length];
+        for (int i = 0; i < types.length; ++i) {
+//            generators[i] = getGeneratorFromAnnotations(annotations[i]);
+//            if (generators[i] == null) {
+                generators[i] = getGeneratorFromType(types[i]);
+//            }
+        }
+        return Generators.arrayGenerator(generators).generate(random, size);
+    }
+
+    private Generator<?> getGeneratorFromType(Type type) {
+        if (type instanceof Class) {
+            Class<?> clazz = (Class<?>) type;
+            if (clazz.isPrimitive() && clazz == Integer.TYPE) {
+                return Generators.integerGenerator();
+            } else {
+                throw new RuntimeException("Unknown type for generator (atm only int is supported)");
+            }
+        } else {
+            throw new RuntimeException("Unknown type for generator (atm only int is supported)");
+        }
+    }
+}
diff --git a/src/main/java/au/id/zancanaro/RoseTree.java b/src/main/java/au/id/zancanaro/RoseTree.java
new file mode 100644
index 0000000..2a83ad2
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/RoseTree.java
@@ -0,0 +1,72 @@
+package au.id.zancanaro;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.function.Function;
+
+public class RoseTree<T> {
+    private final T value;
+    private final Iterable<RoseTree<T>> children;
+
+    public RoseTree(T value, Iterable<RoseTree<T>> children) {
+        this.value = value;
+        this.children = children;
+    }
+
+    public T getValue() {
+        return value;
+    }
+
+    public Iterator<RoseTree<T>> getChildren() {
+        return children.iterator();
+    }
+
+    public static <T> RoseTree<T> pure(T value) {
+        return new RoseTree<>(value, Collections.emptyList());
+    }
+
+    public static <T> RoseTree<T> join(RoseTree<RoseTree<T>> tree) {
+        return new RoseTree<>(
+                tree.getValue().getValue(),
+                () -> Iterators.concat(
+                        Iterators.mappingIterator(RoseTree::join, tree.children.iterator()),
+                        tree.getValue().children.iterator()));
+    }
+
+    public static <T> Iterator<RoseTree<T>[]> permutations(RoseTree<T>[] trees) {
+        return Iterators.flatten(Iterators.rangeIterator(trees.length, index ->
+                Iterators.mappingIterator(child -> {
+                    @SuppressWarnings("unchecked")
+                    RoseTree<T>[] result = (RoseTree<T>[]) new RoseTree[trees.length];
+                    for (int i = 0; i < trees.length; ++i) {
+                        result[i] = (i == index ? child : trees[i]);
+                    }
+                    return result;
+                }, trees[index].getChildren())
+        ));
+    }
+
+    public static <T, R> RoseTree<R> zip(Function<T[], R> fn, RoseTree<T>[] trees) {
+        @SuppressWarnings("unchecked")
+        T[] heads = (T[]) new Object[trees.length];
+        for (int i = 0; i < trees.length; ++i) {
+            heads[i] = trees[i].getValue();
+        }
+        return new RoseTree<>(
+                fn.apply(heads),
+                () -> Iterators.mappingIterator(
+                        roses -> RoseTree.zip(fn, roses),
+                        RoseTree.permutations(trees)));
+    }
+
+    public <R> RoseTree<R> fmap(Function<T, R> f) {
+        return new RoseTree<>(
+                f.apply(this.value),
+                () -> Iterators.mappingIterator(tree -> tree.fmap(f), this.children.iterator()));
+    }
+
+    public <R> RoseTree<R> flatmap(Function<T, RoseTree<R>> f) {
+        return RoseTree.join(this.fmap(f));
+    }
+}
diff --git a/src/main/java/au/id/zancanaro/annotations/Generator.java b/src/main/java/au/id/zancanaro/annotations/Generator.java
new file mode 100644
index 0000000..98e9446
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/annotations/Generator.java
@@ -0,0 +1,8 @@
+package au.id.zancanaro.annotations;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Target;
+
+@Target(ElementType.PARAMETER)
+public @interface Generator {
+}
diff --git a/src/main/java/au/id/zancanaro/annotations/Property.java b/src/main/java/au/id/zancanaro/annotations/Property.java
new file mode 100644
index 0000000..cfe8e45
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/annotations/Property.java
@@ -0,0 +1,13 @@
+package au.id.zancanaro.annotations;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+@Target(ElementType.METHOD)
+@Retention(RetentionPolicy.RUNTIME)
+public @interface Property {
+    int size() default 100;
+    int runs() default 100;
+}
diff --git a/src/main/java/au/id/zancanaro/annotations/Seed.java b/src/main/java/au/id/zancanaro/annotations/Seed.java
new file mode 100644
index 0000000..99f00ca
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/annotations/Seed.java
@@ -0,0 +1,12 @@
+package au.id.zancanaro.annotations;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+@Target(ElementType.METHOD)
+@Retention(RetentionPolicy.RUNTIME)
+public @interface Seed {
+    long value();
+}