mutator: Combinator cross over

2 files changed, 385 insertions, 9 deletions

diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinatorsTest.java b/src/test/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinatorsTest.java
index ccf893d2..d0d06f22 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinatorsTest.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinatorsTest.java
@@ -16,27 +16,39 @@
 
 package com.code_intelligence.jazzer.mutation.combinator;
 
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.assemble;
 import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.combine;
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateProduct;
 import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateProperty;
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateSumInPlace;
 import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable;
 import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateViaView;
 import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.infiniteZeros;
+import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockCrossOver;
+import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockCrossOverInPlace;
+import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockInitInPlace;
+import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockInitializer;
 import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockMutator;
 import static com.code_intelligence.jazzer.mutation.support.TestSupport.mockPseudoRandom;
 import static com.code_intelligence.jazzer.mutation.support.TestSupport.nullDataOutputStream;
 import static com.google.common.truth.Truth.assertThat;
+import static java.util.Collections.singletonList;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 
 import com.code_intelligence.jazzer.mutation.api.Debuggable;
 import com.code_intelligence.jazzer.mutation.api.InPlaceMutator;
 import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.Serializer;
+import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator;
 import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
 import com.code_intelligence.jazzer.mutation.support.TestSupport.MockPseudoRandom;
 import java.io.DataInputStream;
+import java.io.DataOutputStream;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.function.Predicate;
+import java.util.function.ToIntFunction;
 import org.junit.jupiter.api.Test;
 
 class MutatorCombinatorsTest {
@@ -47,8 +59,7 @@ class MutatorCombinatorsTest {
 
     assertThat(mutator.toString()).isEqualTo("Foo.Integer");
 
-    Foo foo = new Foo(0);
-    foo.getList().add(13);
+    Foo foo = new Foo(0, singletonList(13));
 
     try (MockPseudoRandom prng = mockPseudoRandom()) {
       mutator.initInPlace(foo, prng);
@@ -65,6 +76,32 @@ class MutatorCombinatorsTest {
   }
 
   @Test
+  void testCrossOverProperty() {
+    InPlaceMutator<Foo> mutator =
+        mutateProperty(Foo::getValue, mockCrossOver((a, b) -> 42), Foo::setValue);
+    Foo foo = new Foo(0);
+    Foo otherFoo = new Foo(1);
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use foo value
+             0)) {
+      mutator.crossOverInPlace(foo, otherFoo, prng);
+      assertThat(foo.getValue()).isEqualTo(0);
+    }
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use otherFoo value
+             1)) {
+      mutator.crossOverInPlace(foo, otherFoo, prng);
+      assertThat(foo.getValue()).isEqualTo(1);
+    }
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use property type cross over
+             2)) {
+      mutator.crossOverInPlace(foo, otherFoo, prng);
+      assertThat(foo.getValue()).isEqualTo(42);
+    }
+  }
+
+  @Test
   void testMutateViaView() {
     InPlaceMutator<Foo> mutator = mutateViaView(Foo::getList, new InPlaceMutator<List<Integer>>() {
       @Override
@@ -90,8 +127,7 @@ class MutatorCombinatorsTest {
 
     assertThat(mutator.toString()).isEqualTo("Foo via List<Integer>");
 
-    Foo foo = new Foo(13);
-    foo.getList().add(13);
+    Foo foo = new Foo(13, singletonList(13));
 
     try (MockPseudoRandom prng = mockPseudoRandom()) {
       mutator.initInPlace(foo, prng);
@@ -108,7 +144,22 @@ class MutatorCombinatorsTest {
   }
 
   @Test
-  void testCombine() {
+  void testCrossOverViaView() {
+    InPlaceMutator<Foo> mutator = mutateViaView(Foo::getList, mockCrossOverInPlace((a, b) -> {
+      a.clear();
+      a.add(42);
+    }));
+
+    Foo foo = new Foo(0, singletonList(0));
+    Foo otherFoo = new Foo(0, singletonList(1));
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      mutator.crossOverInPlace(foo, otherFoo, prng);
+      assertThat(foo.getList()).containsExactly(42);
+    }
+  }
+
+  @Test
+  void testMutateCombine() {
     InPlaceMutator<Foo> valueMutator =
         mutateProperty(Foo::getValue, mockMutator(21, value -> 2 * value), Foo::setValue);
 
@@ -138,8 +189,7 @@ class MutatorCombinatorsTest {
 
     assertThat(mutator.toString()).isEqualTo("{Foo.Integer, Foo via List<Integer>}");
 
-    Foo foo = new Foo(13);
-    foo.getList().add(13);
+    Foo foo = new Foo(13, singletonList(13));
 
     try (MockPseudoRandom prng = mockPseudoRandom()) {
       mutator.initInPlace(foo, prng);
@@ -161,6 +211,145 @@ class MutatorCombinatorsTest {
   }
 
   @Test
+  void testCrossOverCombine() {
+    InPlaceMutator<Foo> valueMutator =
+        mutateProperty(Foo::getValue, mockCrossOver((a, b) -> 42), Foo::setValue);
+    InPlaceMutator<Foo> listMutator = mutateViaView(Foo::getList, mockCrossOverInPlace((a, b) -> {
+      a.clear();
+      a.add(42);
+    }));
+    InPlaceMutator<Foo> mutator = combine(valueMutator, listMutator);
+
+    Foo foo = new Foo(0, singletonList(0));
+    Foo fooOther = new Foo(1, singletonList(1));
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // call cross over in property mutator
+             2)) {
+      mutator.crossOverInPlace(foo, fooOther, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(42);
+    assertThat(foo.getList()).containsExactly(42);
+  }
+
+  @Test
+  void testCrossOverEmptyCombine() {
+    Foo foo = new Foo(0, singletonList(0));
+    Foo fooOther = new Foo(1, singletonList(1));
+    InPlaceMutator<Foo> emptyCombineMutator = combine();
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      emptyCombineMutator.crossOverInPlace(foo, fooOther, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(0);
+    assertThat(foo.getList()).containsExactly(0);
+  }
+
+  @Test
+  void testMutateAssemble() {
+    InPlaceMutator<Foo> valueMutator =
+        mutateProperty(Foo::getValue, mockMutator(21, value -> 2 * value), Foo::setValue);
+
+    InPlaceMutator<Foo> listMutator =
+        mutateViaView(Foo::getList, new InPlaceMutator<List<Integer>>() {
+          @Override
+          public void initInPlace(List<Integer> reference, PseudoRandom prng) {
+            reference.clear();
+            reference.add(21);
+          }
+
+          @Override
+          public void mutateInPlace(List<Integer> reference, PseudoRandom prng) {
+            reference.add(reference.get(reference.size() - 1) + 1);
+          }
+
+          @Override
+          public void crossOverInPlace(
+              List<Integer> reference, List<Integer> otherReference, PseudoRandom prng) {}
+
+          @Override
+          public String toDebugString(Predicate<Debuggable> isInCycle) {
+            return "List<Integer>";
+          }
+        });
+
+    SerializingInPlaceMutator<Foo> mutator =
+        assemble((m) -> {}, () -> new Foo(0, singletonList(0)), new Serializer<Foo>() {
+          @Override
+          public Foo read(DataInputStream in) {
+            return null;
+          }
+
+          @Override
+          public void write(Foo value, DataOutputStream out) {}
+
+          @Override
+          public Foo detach(Foo value) {
+            return null;
+          }
+        }, () -> combine(valueMutator, listMutator));
+
+    assertThat(mutator.toString()).isEqualTo("{Foo.Integer, Foo via List<Integer>}");
+
+    Foo foo = new Foo(13, singletonList(13));
+
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      mutator.initInPlace(foo, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(21);
+    assertThat(foo.getList()).containsExactly(21);
+
+    try (MockPseudoRandom prng = mockPseudoRandom(/* use valueMutator */ 0)) {
+      mutator.mutateInPlace(foo, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(42);
+    assertThat(foo.getList()).containsExactly(21);
+
+    try (MockPseudoRandom prng = mockPseudoRandom(/* use listMutator */ 1)) {
+      mutator.mutateInPlace(foo, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(42);
+    assertThat(foo.getList()).containsExactly(21, 22);
+  }
+
+  @Test
+  void testCrossOverAssemble() {
+    InPlaceMutator<Foo> valueMutator =
+        mutateProperty(Foo::getValue, mockCrossOver((a, b) -> 42), Foo::setValue);
+
+    InPlaceMutator<Foo> listMutator = mutateViaView(Foo::getList, mockCrossOverInPlace((a, b) -> {
+      a.clear();
+      a.add(42);
+    }));
+
+    SerializingInPlaceMutator<Foo> mutator =
+        assemble((m) -> {}, () -> new Foo(0, singletonList(0)), new Serializer<Foo>() {
+          @Override
+          public Foo read(DataInputStream in) {
+            return null;
+          }
+
+          @Override
+          public void write(Foo value, DataOutputStream out) {}
+
+          @Override
+          public Foo detach(Foo value) {
+            return null;
+          }
+        }, () -> combine(valueMutator, listMutator));
+
+    Foo foo = new Foo(0, singletonList(0));
+    Foo fooOther = new Foo(1, singletonList(1));
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // cross over in property mutator
+             2)) {
+      mutator.crossOverInPlace(foo, fooOther, prng);
+    }
+    assertThat(foo.getValue()).isEqualTo(42);
+    assertThat(foo.getList()).containsExactly(42);
+  }
+
+  @Test
   void testMutateThenMapToImmutable() throws IOException {
     SerializingMutator<char[]> charMutator =
         mockMutator(new char[] {'H', 'e', 'l', 'l', 'o'}, chars -> {
@@ -203,13 +392,123 @@ class MutatorCombinatorsTest {
         () -> mutator.write(capturedValue, nullDataOutputStream()));
   }
 
+  @Test
+  void testCrossOverThenMapToImmutable() {
+    SerializingMutator<char[]> charMutator = mockCrossOver((a, b) -> {
+      assertThat(a).isEqualTo(new char[] {'H', 'e', 'l', 'l', 'o'});
+      assertThat(b).isEqualTo(new char[] {'W', 'o', 'r', 'l', 'd'});
+      return new char[] {'T', 'e', 's', 't', 'e', 'd'};
+    });
+    SerializingMutator<String> mutator =
+        mutateThenMapToImmutable(charMutator, String::new, String::toCharArray);
+
+    String crossedOver;
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      crossedOver = mutator.crossOver("Hello", "World", prng);
+    }
+    assertThat(crossedOver).isEqualTo("Tested");
+  }
+
+  @Test
+  void testCrossOverProduct() {
+    SerializingMutator<Boolean> mutator1 = mockCrossOver((a, b) -> true);
+    SerializingMutator<Integer> mutator2 = mockCrossOver((a, b) -> 42);
+    ProductMutator mutator = mutateProduct(mutator1, mutator2);
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use first value in mutator1
+             0,
+             // use second value in mutator2
+             0)) {
+      Object[] crossedOver =
+          mutator.crossOver(new Object[] {false, 0}, new Object[] {true, 1}, prng);
+      assertThat(crossedOver).isEqualTo(new Object[] {false, 0});
+    }
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use first value in mutator1
+             1,
+             // use second value in mutator2
+             1)) {
+      Object[] crossedOver =
+          mutator.crossOver(new Object[] {false, 0}, new Object[] {true, 1}, prng);
+      assertThat(crossedOver).isEqualTo(new Object[] {true, 1});
+    }
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // use cross over in mutator1
+             2,
+             // use cross over in mutator2
+             2)) {
+      Object[] crossedOver =
+          mutator.crossOver(new Object[] {false, 0}, new Object[] {true, 2}, prng);
+      assertThat(crossedOver).isEqualTo(new Object[] {true, 42});
+    }
+  }
+
+  @Test
+  void testCrossOverSumInPlaceSameType() {
+    ToIntFunction<List<Integer>> mutotarIndexFromValue = (r) -> 0;
+    InPlaceMutator<List<Integer>> mutator1 = mockCrossOverInPlace((a, b) -> { a.add(42); });
+    InPlaceMutator<List<Integer>> mutator2 = mockCrossOverInPlace((a, b) -> {});
+    InPlaceMutator<List<Integer>> mutator =
+        mutateSumInPlace(mutotarIndexFromValue, mutator1, mutator2);
+
+    List<Integer> a = new ArrayList<>();
+    List<Integer> b = new ArrayList<>();
+
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      mutator.crossOverInPlace(a, b, prng);
+    }
+    assertThat(a).containsExactly(42);
+  }
+
+  @Test
+  void testCrossOverSumInPlaceIndeterminate() {
+    InPlaceMutator<List<?>> mutator1 = mockCrossOverInPlace((a, b) -> {});
+    InPlaceMutator<List<?>> mutator2 = mockCrossOverInPlace((a, b) -> {});
+    ToIntFunction<List<?>> bothIndeterminate = (r) -> - 1;
+
+    InPlaceMutator<List<?>> mutator = mutateSumInPlace(bothIndeterminate, mutator1, mutator2);
+
+    List<Integer> a = new ArrayList<>();
+    a.add(42);
+    List<Integer> b = new ArrayList<>();
+
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      mutator.crossOverInPlace(a, b, prng);
+      assertThat(a).containsExactly(42);
+    }
+  }
+
+  @Test
+  void testCrossOverSumInPlaceFirstIndeterminate() {
+    List<Integer> reference = new ArrayList<>();
+    List<Integer> otherReference = new ArrayList<>();
+
+    InPlaceMutator<List<Integer>> mutator1 = mockCrossOverInPlace((a, b) -> {});
+    InPlaceMutator<List<Integer>> mutator2 = mockInitInPlace((l) -> { l.add(42); });
+    ToIntFunction<List<Integer>> firstIndeterminate = (r) -> r == reference ? -1 : 1;
+
+    InPlaceMutator<List<Integer>> mutator =
+        mutateSumInPlace(firstIndeterminate, mutator1, mutator2);
+
+    try (MockPseudoRandom prng = mockPseudoRandom()) {
+      mutator.crossOverInPlace(reference, otherReference, prng);
+      assertThat(reference).containsExactly(42);
+    }
+  }
+
   static class Foo {
     private int value;
     private final List<Integer> list;
 
     public Foo(int value) {
+      this(value, new ArrayList<>());
+    }
+    public Foo(int value, List<Integer> list) {
       this.value = value;
-      this.list = new ArrayList<>();
+      this.list = new ArrayList<>(list);
     }
 
     public List<Integer> getList() {
diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/support/TestSupport.java b/src/test/java/com/code_intelligence/jazzer/mutation/support/TestSupport.java
index d4e15a78..8035ef86 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/support/TestSupport.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/support/TestSupport.java
@@ -22,6 +22,7 @@ import static java.util.Arrays.stream;
 import static java.util.stream.Collectors.toCollection;
 
 import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.InPlaceMutator;
 import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
 import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
 import com.code_intelligence.jazzer.mutation.engine.SeededPseudoRandom;
@@ -35,6 +36,9 @@ import java.util.ArrayList;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Queue;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
 import java.util.function.Predicate;
 import java.util.function.Supplier;
 import java.util.function.UnaryOperator;
@@ -117,6 +121,78 @@ public final class TestSupport {
     };
   }
 
+  @CheckReturnValue
+  public static <T> SerializingMutator<T> mockCrossOver(BiFunction<T, T, T> getCrossOverValue) {
+    return new AbstractMockMutator<T>() {
+      @Override
+      protected T nextInitialValue() {
+        throw new UnsupportedOperationException();
+      }
+
+      @Override
+      public T mutate(T value, PseudoRandom prng) {
+        throw new UnsupportedOperationException();
+      }
+
+      @Override
+      public T crossOver(T value, T otherValue, PseudoRandom prng) {
+        return getCrossOverValue.apply(value, otherValue);
+      }
+
+      @Override
+      public T detach(T value) {
+        return value;
+      }
+    };
+  }
+
+  @CheckReturnValue
+  public static <T> InPlaceMutator<T> mockCrossOverInPlace(BiConsumer<T, T> crossOverInPlace) {
+    return new AbstractMockInPlaceMutator<T>() {
+      @Override
+      public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+        crossOverInPlace.accept(reference, otherReference);
+      }
+
+      @Override
+      public String toDebugString(Predicate<Debuggable> isInCycle) {
+        return "CrossOverInPlaceMockMutator";
+      }
+    };
+  }
+
+  @CheckReturnValue
+  public static <T> InPlaceMutator<T> mockInitInPlace(Consumer<T> setInitialValues) {
+    return new AbstractMockInPlaceMutator<T>() {
+      @Override
+      public void initInPlace(T reference, PseudoRandom prng) {
+        setInitialValues.accept(reference);
+      }
+
+      @Override
+      public String toDebugString(Predicate<Debuggable> isInCycle) {
+        return "InitInPlaceMockMutator";
+      }
+    };
+  }
+
+  private static abstract class AbstractMockInPlaceMutator<T> implements InPlaceMutator<T> {
+    @Override
+    public void initInPlace(T reference, PseudoRandom prng) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void mutateInPlace(T reference, PseudoRandom prng) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+      throw new UnsupportedOperationException();
+    }
+  }
+
   private static abstract class AbstractMockMutator<T> extends SerializingMutator<T> {
     abstract protected T nextInitialValue();
 
@@ -315,7 +391,7 @@ public final class TestSupport {
         case 1:
           return otherValue;
         case 2:
-          return producer.get();
+          return supplier.get();
         default:
           throw new AssertionError("Invalid pickValue element");
       }
@@ -333,6 +409,7 @@ public final class TestSupport {
     }
   }
 
+  @SuppressWarnings("unchecked")
   public static <K, V> LinkedHashMap<K, V> asMap(Object... objs) {
     LinkedHashMap<K, V> map = new LinkedHashMap<>();
     for (int i = 0; i < objs.length; i += 2) {