aboutsummaryrefslogtreecommitdiff
path: root/src/main/java/com/code_intelligence/jazzer/mutation
diff options
context:
space:
mode:
authorMark <mteffeteller@google.com>2023-06-22 00:59:06 +0000
committerAutomerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>2023-06-22 00:59:06 +0000
commit33edd6723662ea34453766bfdca85dbfdd5342b8 (patch)
tree68cf332a40b94b2d28b256b19b916f99220bb0c4 /src/main/java/com/code_intelligence/jazzer/mutation
parentba37c2e361c2ba91bacc47fcae5383c52e50f6be (diff)
parentf1ff6ce482549c51088d0a4b011d676904ad2506 (diff)
downloadjazzer-api-master.tar.gz
Original change: https://android-review.googlesource.com/c/platform/external/jazzer-api/+/2627336 Change-Id: Iaaed944c1e9e457640f7055fc57e8678f90f4603 Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
Diffstat (limited to 'src/main/java/com/code_intelligence/jazzer/mutation')
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java232
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel16
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java40
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java28
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel5
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java32
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java32
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java35
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java29
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java33
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java34
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java43
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java40
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel21
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java43
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel9
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java48
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java46
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java44
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java74
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java80
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java136
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java116
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java76
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java35
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java75
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel11
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java516
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java89
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java138
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel12
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java288
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel14
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java81
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel13
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java226
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java243
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java28
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java167
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java205
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel16
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java79
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java227
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java47
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java597
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java399
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java30
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java126
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java172
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel15
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java92
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel16
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java188
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java451
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java41
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java52
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java34
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java179
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel11
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java31
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java256
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java63
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java55
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java64
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java72
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java43
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java564
-rw-r--r--src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java168
68 files changed, 7521 insertions, 0 deletions
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java
new file mode 100644
index 00000000..fabda057
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java
@@ -0,0 +1,232 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation;
+
+import static com.code_intelligence.jazzer.mutation.mutator.Mutators.validateAnnotationUsage;
+import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithReadExactly;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.StreamSupport.toArrayOrEmpty;
+import static java.lang.String.format;
+import static java.util.Arrays.stream;
+import static java.util.Objects.requireNonNull;
+import static java.util.stream.Collectors.joining;
+
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators;
+import com.code_intelligence.jazzer.mutation.combinator.ProductMutator;
+import com.code_intelligence.jazzer.mutation.engine.SeededPseudoRandom;
+import com.code_intelligence.jazzer.mutation.mutator.Mutators;
+import com.code_intelligence.jazzer.mutation.support.InputStreamSupport.ReadExactlyInputStream;
+import com.code_intelligence.jazzer.mutation.support.Preconditions;
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.io.UncheckedIOException;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.lang.reflect.Modifier;
+import java.util.Optional;
+
+public final class ArgumentsMutator {
+ private final Object instance;
+ private final Method method;
+ private final ProductMutator productMutator;
+ private Object[] arguments;
+
+ /**
+ * True if the arguments array has already been passed to a user-provided function or exposed
+ * via {@link #getArguments()} without going through {@link ProductMutator#detach(Object[])}.
+ * In this case the arguments may have been modified externally, which interferes with mutation,
+ * or could have been stored in static state that would be affected by future mutations.
+ * Arguments should either be detached or not be reused after being exposed, which is enforced by
+ * this variable.
+ */
+ private boolean argumentsExposed;
+
+ private ArgumentsMutator(Object instance, Method method, ProductMutator productMutator) {
+ this.instance = instance;
+ this.method = method;
+ this.productMutator = productMutator;
+ }
+
+ private static String prettyPrintMethod(Method method) {
+ return format("%s.%s(%s)", method.getDeclaringClass().getName(), method.getName(),
+ stream(method.getAnnotatedParameterTypes()).map(Object::toString).collect(joining(", ")));
+ }
+
+ public static ArgumentsMutator forInstanceMethodOrThrow(Object instance, Method method) {
+ return forInstanceMethod(Mutators.newFactory(), instance, method)
+ .orElseThrow(()
+ -> new IllegalArgumentException(
+ "Failed to construct mutator for " + prettyPrintMethod(method)));
+ }
+
+ public static ArgumentsMutator forStaticMethodOrThrow(Method method) {
+ return forStaticMethod(Mutators.newFactory(), method)
+ .orElseThrow(()
+ -> new IllegalArgumentException(
+ "Failed to construct mutator for " + prettyPrintMethod(method)));
+ }
+
+ public static Optional<ArgumentsMutator> forMethod(Method method) {
+ return forMethod(Mutators.newFactory(), null, method);
+ }
+
+ public static Optional<ArgumentsMutator> forInstanceMethod(
+ MutatorFactory mutatorFactory, Object instance, Method method) {
+ require(!isStatic(method), "method must not be static");
+ requireNonNull(instance, "instance must not be null");
+ require(method.getDeclaringClass().isInstance(instance),
+ format("instance is a %s, expected %s", instance.getClass(), method.getDeclaringClass()));
+ return forMethod(mutatorFactory, instance, method);
+ }
+
+ public static Optional<ArgumentsMutator> forStaticMethod(
+ MutatorFactory mutatorFactory, Method method) {
+ require(isStatic(method), "method must be static");
+ return forMethod(mutatorFactory, null, method);
+ }
+
+ public static Optional<ArgumentsMutator> forMethod(
+ MutatorFactory mutatorFactory, Object instance, Method method) {
+ require(method.getParameterCount() > 0, "Can't fuzz method without parameters: " + method);
+ for (AnnotatedType parameter : method.getAnnotatedParameterTypes()) {
+ validateAnnotationUsage(parameter);
+ }
+ return toArrayOrEmpty(
+ stream(method.getAnnotatedParameterTypes()).map(mutatorFactory::tryCreate),
+ SerializingMutator<?>[] ::new)
+ .map(MutatorCombinators::mutateProduct)
+ .map(productMutator -> ArgumentsMutator.create(instance, method, productMutator));
+ }
+
+ private static ArgumentsMutator create(
+ Object instance, Method method, ProductMutator productMutator) {
+ method.setAccessible(true);
+
+ return new ArgumentsMutator(instance, method, productMutator);
+ }
+
+ private static boolean isStatic(Method method) {
+ return Modifier.isStatic(method.getModifiers());
+ }
+
+ /**
+ * @throws UncheckedIOException if the underlying InputStream throws
+ */
+ public void crossOver(InputStream data1, InputStream data2, long seed) {
+ try {
+ Object[] objects1 = productMutator.readExclusive(data1);
+ Object[] objects2 = productMutator.readExclusive(data2);
+ PseudoRandom prng = new SeededPseudoRandom(seed);
+ arguments = productMutator.crossOver(objects1, objects2, prng);
+ argumentsExposed = false;
+ } catch (IOException e) {
+ throw new UncheckedIOException(e);
+ }
+ }
+
+ /**
+ * @return if the given input stream was consumed exactly
+ * @throws UncheckedIOException if the underlying InputStream throws
+ */
+ public boolean read(ByteArrayInputStream data) {
+ try {
+ ReadExactlyInputStream is = extendWithReadExactly(data);
+ arguments = productMutator.readExclusive(is);
+ argumentsExposed = false;
+ return is.isConsumedExactly();
+ } catch (IOException e) {
+ throw new UncheckedIOException(e);
+ }
+ }
+
+ /**
+ * @throws UncheckedIOException if the underlying OutputStream throws
+ */
+ public void write(OutputStream data) {
+ failIfArgumentsExposed();
+ writeAny(data, arguments);
+ }
+
+ /**
+ * @throws UncheckedIOException if the underlying OutputStream throws
+ */
+ public void writeAny(OutputStream data, Object[] args) throws UncheckedIOException {
+ try {
+ productMutator.writeExclusive(args, data);
+ } catch (IOException e) {
+ throw new UncheckedIOException(e);
+ }
+ }
+
+ public void init(long seed) {
+ init(new SeededPseudoRandom(seed));
+ }
+
+ void init(PseudoRandom prng) {
+ arguments = productMutator.init(prng);
+ argumentsExposed = false;
+ }
+
+ public void mutate(long seed) {
+ mutate(new SeededPseudoRandom(seed));
+ }
+
+ void mutate(PseudoRandom prng) {
+ failIfArgumentsExposed();
+ // TODO: Sometimes mutate the entire byte representation of the current value with libFuzzer's
+ // dictionary and TORC mutations.
+ productMutator.mutate(arguments, prng);
+ }
+
+ public void invoke(boolean detach) throws Throwable {
+ Object[] invokeArguments;
+ if (detach) {
+ invokeArguments = productMutator.detach(arguments);
+ } else {
+ invokeArguments = arguments;
+ argumentsExposed = true;
+ }
+ try {
+ method.invoke(instance, invokeArguments);
+ } catch (IllegalAccessException e) {
+ throw new IllegalStateException("method should have been made accessible", e);
+ } catch (InvocationTargetException e) {
+ throw e.getCause();
+ }
+ }
+
+ public Object[] getArguments() {
+ argumentsExposed = true;
+ return arguments;
+ }
+
+ @Override
+ public String toString() {
+ return "Arguments" + productMutator;
+ }
+
+ private void failIfArgumentsExposed() {
+ Preconditions.check(!argumentsExposed,
+ "Arguments have previously been exposed to user-provided code without calling #detach and may have been modified");
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel
new file mode 100644
index 00000000..9866c2c4
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel
@@ -0,0 +1,16 @@
+java_library(
+ name = "mutation",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//visibility:public",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/combinator",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/engine",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java
new file mode 100644
index 00000000..4d4c4a89
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.ANNOTATION_TYPE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+/**
+ * A meta-annotation that limits the concrete types an annotation for type usages applies to.
+ */
+@Target(ANNOTATION_TYPE)
+@Retention(RUNTIME)
+public @interface AppliesTo {
+ /**
+ * The meta-annotated annotation can be applied to these classes.
+ */
+ Class<?>[] value() default {};
+
+ /**
+ * The meta-annotated annotation can be applied to subclasses of these classes.
+ */
+ Class<?>[] subClassesOf() default {};
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java
new file mode 100644
index 00000000..190ada09
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java
@@ -0,0 +1,28 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo(String.class)
+public @interface Ascii {}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel
new file mode 100644
index 00000000..6d6c4da9
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel
@@ -0,0 +1,5 @@
+java_library(
+ name = "annotation",
+ srcs = glob(["*.java"]),
+ visibility = ["//visibility:public"],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java
new file mode 100644
index 00000000..27765879
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo({double.class, Double.class})
+public @interface DoubleInRange {
+ double min() default Double.NEGATIVE_INFINITY;
+ double max() default Double.POSITIVE_INFINITY;
+ boolean allowNaN() default true;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java
new file mode 100644
index 00000000..ec54e026
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo({float.class, Float.class})
+public @interface FloatInRange {
+ float min() default Float.NEGATIVE_INFINITY;
+ float max() default Float.POSITIVE_INFINITY;
+ boolean allowNaN() default true;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java
new file mode 100644
index 00000000..a8dc8281
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo({byte.class, Byte.class, short.class, Short.class, int.class, Integer.class, long.class,
+ Long.class})
+public @interface InRange {
+ long min() default Long.MIN_VALUE;
+
+ long max() default Long.MAX_VALUE;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java
new file mode 100644
index 00000000..061eeffc
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.PARAMETER;
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+@Target({PARAMETER, TYPE_USE})
+@Retention(RUNTIME)
+@AppliesTo(subClassesOf = Object.class)
+public @interface NotNull {}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java
new file mode 100644
index 00000000..7cee23df
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java
@@ -0,0 +1,33 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.PARAMETER;
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo(byte[].class)
+public @interface WithLength {
+ int min() default 0;
+
+ int max() default 1000;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java
new file mode 100644
index 00000000..32233f4b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+import java.util.List;
+import java.util.Map;
+
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo({List.class, Map.class})
+public @interface WithSize {
+ int min() default 0;
+
+ int max() default 1000;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java
new file mode 100644
index 00000000..00b1f463
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+/**
+ * An annotation that applies to {@link String} to <strong>limit the length of the UTF-8
+ * encoding</strong> of the string. In practical terms, this means that strings given this
+ * annotation will sometimes have a {@link String#length()} of less than
+ * {@code min} but will never exceed {@code max}. <p> Due to the fact that our String mutator is
+ * backed by the byte array mutator, it's difficult to know how many characters we'll get from the
+ * byte array we get from libfuzzer. Rather than reuse {@link WithLength} for strings which may give
+ * the impression that {@link String#length()} will return a value between {@code min} and {@code
+ * max}, we use this annotation to help make clear that the string consists of between
+ * {@code min} and {@code max} UTF-8 bytes, not necessarily (UTF-16) characters.
+ */
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo(String.class)
+public @interface WithUtf8Length {
+ int min() default 0;
+
+ int max() default 1000;
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java
new file mode 100644
index 00000000..9f802dfe
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation.proto;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import com.code_intelligence.jazzer.mutation.annotation.AppliesTo;
+import com.google.protobuf.Message;
+import com.google.protobuf.Message.Builder;
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+/**
+ * Controls the mutations of {@link com.google.protobuf.Any} fields in messages of the annotated
+ * type as well as its recursive message fields.
+ */
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo(subClassesOf = {Message.class, Builder.class})
+public @interface AnySource {
+ /**
+ * A non-empty list of {@link Message}s to use for {@link com.google.protobuf.Any} fields.
+ */
+ Class<? extends Message>[] value();
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel
new file mode 100644
index 00000000..8ef6863b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel
@@ -0,0 +1,21 @@
+java_library(
+ name = "proto",
+ srcs = glob(["*.java"]),
+ visibility = ["//visibility:public"],
+ deps = [
+ ":protobuf_runtime_compile_only",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ ],
+)
+
+java_library(
+ name = "protobuf_runtime_compile_only",
+ # The proto mutator factory detects the presence of Protobuf at runtime and disables itself if
+ # it isn't found. Without something else bringing in the Protobuf runtime, there is no point in
+ # supporting proto mutations.
+ neverlink = True,
+ visibility = ["//src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto:__pkg__"],
+ exports = [
+ "@com_google_protobuf_protobuf_java//jar",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java
new file mode 100644
index 00000000..e26d73a2
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.annotation.proto;
+
+import static java.lang.annotation.ElementType.TYPE_USE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import com.code_intelligence.jazzer.mutation.annotation.AppliesTo;
+import com.google.protobuf.DynamicMessage;
+import com.google.protobuf.Message;
+import java.lang.annotation.Retention;
+import java.lang.annotation.Target;
+
+/**
+ * Provides a default instance to use as the base for mutations of the annotated {@link Message} or
+ * {@link DynamicMessage.Builder}.
+ */
+@Target(TYPE_USE)
+@Retention(RUNTIME)
+@AppliesTo(subClassesOf = {Message.class, Message.Builder.class})
+public @interface WithDefaultInstance {
+ /**
+ * The fully qualified name of a static method (e.g.
+ * {@code com.example.MyClass#getDefaultInstance}) with return type assignable to
+ * {@link com.google.protobuf.Message}, which returns a default instance that mutations should be
+ * based on.
+ */
+ String value();
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel
new file mode 100644
index 00000000..cd5fe60e
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel
@@ -0,0 +1,9 @@
+java_library(
+ name = "api",
+ srcs = glob(["*.java"]),
+ visibility = ["//visibility:public"],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ "@com_google_errorprone_error_prone_annotations//jar",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java
new file mode 100644
index 00000000..bf27e81b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import static com.code_intelligence.jazzer.mutation.support.StreamSupport.findFirstPresent;
+import static java.util.Arrays.asList;
+import static java.util.Collections.unmodifiableList;
+
+import com.google.errorprone.annotations.CheckReturnValue;
+import java.lang.reflect.AnnotatedType;
+import java.util.List;
+import java.util.Optional;
+
+/**
+ * A {@link MutatorFactory} that delegates to the given factories in order.
+ */
+public final class ChainedMutatorFactory extends MutatorFactory {
+ private final List<MutatorFactory> factories;
+
+ /**
+ * Creates a {@link MutatorFactory} that delegates to the given factories in order.
+ *
+ * @param factories a possibly empty collection of factories
+ */
+ public ChainedMutatorFactory(MutatorFactory... factories) {
+ this.factories = unmodifiableList(asList(factories));
+ }
+
+ @Override
+ @CheckReturnValue
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory parent) {
+ return findFirstPresent(factories.stream().map(factory -> factory.tryCreate(type, parent)));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java
new file mode 100644
index 00000000..df6f8288
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import static java.util.Collections.newSetFromMap;
+import static java.util.Objects.requireNonNull;
+
+import java.util.IdentityHashMap;
+import java.util.Set;
+import java.util.function.Predicate;
+
+public interface Debuggable {
+ /**
+ * Returns a string representation of the object that is meant to be used to make assertions about
+ * its structure in tests.
+ *
+ * @param isInCycle evaluates to {@code true} if a cycle has been detected during recursive calls
+ * of this function. Must be called at most once with {@code this} as the single
+ * argument. Implementing classes that know that their current instance can never
+ * be contained in recursive substructures need not call this method.
+ */
+ String toDebugString(Predicate<Debuggable> isInCycle);
+
+ /**
+ * Returns a string representation of the given {@link Debuggable} that is meant to be used to
+ * make assertions about its structure in tests.
+ */
+ static String getDebugString(Debuggable debuggable) {
+ Set<Debuggable> seen = newSetFromMap(new IdentityHashMap<>());
+ return debuggable.toDebugString(child -> !seen.add(requireNonNull(child)));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java
new file mode 100644
index 00000000..d927e505
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import com.google.errorprone.annotations.CheckReturnValue;
+
+/**
+ * Knows how to clone a {@code T} such that it shares no mutable state with the original.
+ */
+@FunctionalInterface
+public interface Detacher<T> {
+ /**
+ * Returns an equal instance that shares no mutable state with {@code value}.
+ *
+ * <p>Implementations
+ * <ul>
+ * <li>MUST return an instance that {@link Object#equals(Object)} the argument;
+ * <li>MUST return an instance that cannot be used to mutate the state of the argument through
+ * its API (ignoring uses of {@link sun.misc.Unsafe});
+ * <li>MUST return an instance that is not affected by any changes to the original value made
+ * by any mutator;</li>
+ * <li>MUST be accepted by mutator methods just like the original value;</li>
+ * <li>MAY return the argument itself if it is deeply immutable.
+ * </ul>
+ *
+ * @param value the instance to detach
+ * @return an equal instance that shares no mutable state with {@code value}
+ */
+ @CheckReturnValue T detach(T value);
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java
new file mode 100644
index 00000000..cf1b243d
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java
@@ -0,0 +1,74 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+/**
+ * Knows how to initialize and mutate (parts of) an existing object of type {@code T} in place and
+ * how to incorporate (cross over) parts of another object of the same type.
+ *
+ * <p>Certain types, such as immutable and primitive types, can not be mutated in place. For
+ * example, {@link java.util.List} can be mutated in place whereas {@link String} and {@code int}
+ * can't. In such cases, use {@link ValueMutator} instead.
+ *
+ * <p>Implementations
+ * <ul>
+ * <li>MAY weakly associate mutable state with the identity (not equality class) of objects they
+ * have been passed as arguments or returned from initialization functions;
+ * <li>MAY assume that they are only passed arguments that they have initialized or mutated;</li>
+ * <li>SHOULD use {@link com.code_intelligence.jazzer.mutation.support.WeakIdentityHashMap} for
+ * this purpose;
+ * <li>MUST otherwise be deeply immutable;
+ * <li>SHOULD override {@link Object#toString()} to return {@code
+ * Debuggable.getDebugString(this)}.
+ * </ul>
+ *
+ * @param <T> the reference type this mutator operates on
+ */
+public interface InPlaceMutator<T> extends Debuggable {
+ /**
+ * Implementations
+ * <ul>
+ * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself.
+ * <li>SHOULD, when called repeatedly, initialize the object in ways that are likely to be
+ * distinct.
+ * </ul>
+ */
+ void initInPlace(T reference, PseudoRandom prng);
+
+ /**
+ * Implementations
+ * <ul>
+ * <li>MUST ensure that {@code reference} does not {@link Object#equals(Object)} the state it
+ * had prior to the call (if possible);
+ * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself.
+ * <li>SHOULD, when called repeatedly, be able to eventually reach any valid state of the part
+ * of {@code T} governed by this mutator;
+ * </ul>
+ */
+ void mutateInPlace(T reference, PseudoRandom prng);
+
+ /**
+ * Implementations
+ * <ul>
+ * <li>MUST ensure that {@code reference} does not {@link Object#equals(Object)} the state it
+ * had prior to the call (if possible);
+ * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself.
+ * <li>MUST NOT mutate {@code otherReference}</li>
+ * </ul>
+ */
+ void crossOverInPlace(T reference, T otherReference, PseudoRandom prng);
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java
new file mode 100644
index 00000000..64771285
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType;
+import static java.lang.String.format;
+
+import com.google.errorprone.annotations.CheckReturnValue;
+import java.lang.reflect.AnnotatedType;
+import java.util.Optional;
+
+/**
+ * Instances of this class are not required to be thread safe, but are generally lightweight and can
+ * thus be created as needed.
+ */
+public abstract class MutatorFactory {
+ public final boolean canMutate(AnnotatedType type) {
+ return tryCreate(type).isPresent();
+ }
+
+ public final <T> SerializingMutator<T> createOrThrow(Class<T> clazz) {
+ return (SerializingMutator<T>) createOrThrow(asAnnotatedType(clazz));
+ }
+
+ public final SerializingMutator<?> createOrThrow(AnnotatedType type) {
+ Optional<SerializingMutator<?>> maybeMutator = tryCreate(type);
+ require(maybeMutator.isPresent(), "Failed to create mutator for " + type);
+ return maybeMutator.get();
+ }
+
+ public final SerializingInPlaceMutator<?> createInPlaceOrThrow(AnnotatedType type) {
+ Optional<SerializingInPlaceMutator<?>> maybeMutator = tryCreateInPlace(type);
+ require(maybeMutator.isPresent(), "Failed to create mutator for " + type);
+ return maybeMutator.get();
+ }
+
+ /**
+ * Tries to create a mutator for {@code type} and, if successful, asserts that it is an instance
+ * of {@link SerializingInPlaceMutator}.
+ */
+ public final Optional<SerializingInPlaceMutator<?>> tryCreateInPlace(AnnotatedType type) {
+ return tryCreate(type).map(mutator -> {
+ require(mutator instanceof InPlaceMutator<?>,
+ format("Mutator for %s is not in-place: %s", type, mutator.getClass()));
+ return (SerializingInPlaceMutator<?>) mutator;
+ });
+ }
+
+ @CheckReturnValue
+ public final Optional<SerializingMutator<?>> tryCreate(AnnotatedType type) {
+ return tryCreate(type, this);
+ }
+
+ /**
+ * Attempt to create a {@link SerializingMutator} for the given type.
+ *
+ * @param type the type to mutate
+ * @param factory the factory to use when creating submutators
+ * @return a {@link SerializingMutator} for the given {@code type}, or {@link Optional#empty()}
+ * if this factory can't create such mutators
+ */
+ @CheckReturnValue
+ public abstract Optional<SerializingMutator<?>> tryCreate(
+ AnnotatedType type, MutatorFactory factory);
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java
new file mode 100644
index 00000000..3755a7b1
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java
@@ -0,0 +1,136 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import com.google.errorprone.annotations.DoNotMock;
+import java.util.List;
+import java.util.function.Supplier;
+
+@DoNotMock("Use TestSupport#mockPseudoRandom instead")
+public interface PseudoRandom {
+ /**
+ * @return a uniformly random {@code boolean}
+ */
+ boolean choice();
+
+ /**
+ * @return a {@code boolean} that is {@code true} with probability {@code 1/inverseFrequencyTrue}
+ */
+ boolean trueInOneOutOf(int inverseFrequencyTrue);
+
+ /**
+ * @throws IllegalArgumentException if {@code array.length == 0}
+ * @return an element from the given array at uniformly random index
+ */
+ <T> T pickIn(T[] array);
+
+ /**
+ * @throws IllegalArgumentException if {@code array.length == 0}
+ * @return an element from the given List at uniformly random index
+ */
+ <T> T pickIn(List<T> array);
+
+ /**
+ * @throws IllegalArgumentException if {@code array.length == 0}
+ * @return a uniformly random index valid for the given array
+ */
+ <T> int indexIn(T[] array);
+
+ /**
+ * @throws IllegalArgumentException if {@code list.size() == 0}
+ * @return a uniformly random index valid for the given list
+ */
+ <T> int indexIn(List<T> list);
+
+ /**
+ * Prefer {@link #indexIn(Object[])} and {@link #indexIn(List)}.
+ *
+ * @throws IllegalArgumentException if {@code range < 1}
+ * @return a uniformly random index in the range {@code [0, range-1]}
+ */
+ int indexIn(int range);
+
+ /**
+ * @throws IllegalArgumentException if {@code array.length < 2}
+ * @return a uniformly random index valid for the given array and different from
+ * {@code currentIndex}
+ */
+ <T> int otherIndexIn(T[] array, int currentIndex);
+
+ /**
+ * @throws IllegalArgumentException if {@code length < 2}
+ * @return a uniformly random {@code int} in the closed range {@code [0, length)} that is
+ * different from {@code currentIndex}
+ */
+ int otherIndexIn(int range, int currentIndex);
+
+ /**
+ * @return a uniformly random {@code int} in the closed range
+ * {@code [lowerInclusive, upperInclusive]}.
+ */
+ int closedRange(int lowerInclusive, int upperInclusive);
+
+ /**
+ * @return a uniformly random {@code long} in the closed range
+ * {@code [lowerInclusive, upperInclusive]}.
+ */
+ long closedRange(long lowerInclusive, long upperInclusive);
+
+ /**
+ * @return a uniformly random {@code float} in the closed range
+ * {@code [lowerInclusive, upperInclusive]}.
+ */
+ float closedRange(float lowerInclusive, float upperInclusive);
+
+ /**
+ * @return a uniformly random {@code double} in the closed range
+ * {@code [lowerInclusive, upperInclusive]}.
+ */
+ double closedRange(double lowerInclusive, double upperInclusive);
+
+ /**
+ * @return a random value in the closed range [0, upperInclusive] that is heavily biased towards
+ * being small
+ */
+ int closedRangeBiasedTowardsSmall(int upperInclusive);
+
+ /**
+ * @return a random value in the closed range [lowerInclusive, upperInclusive] that is heavily
+ * biased towards being small
+ */
+ int closedRangeBiasedTowardsSmall(int lowerInclusive, int upperInclusive);
+
+ /**
+ * Fills the given array with random bytes.
+ */
+ void bytes(byte[] bytes);
+
+ /**
+ * Use the given supplier to produce a value with probability {@code 1/inverseSupplierFrequency},
+ * otherwise randomly return one of the given values.
+ *
+ * @return value produced by the supplier or one of the given values
+ */
+ <T> T pickValue(T value, T otherValue, Supplier<T> supplier, int inverseSupplierFrequency);
+
+ /**
+ * Returns a pseudorandom {@code long} value.
+ *
+ * @return a pseudorandom {@code long} value
+ */
+ long nextLong();
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java
new file mode 100644
index 00000000..b948b177
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java
@@ -0,0 +1,116 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithZeros;
+
+import com.google.errorprone.annotations.CheckReturnValue;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+
+/**
+ * Serializes and deserializes values of type {@code T>} to and from (in-memory or on disk) corpus
+ * entries.
+ *
+ * <p>Binary representations must by default be self-delimiting. For variable-length types, the
+ * {@link #readExclusive(InputStream)} and {@link #writeExclusive(Object, OutputStream)} methods can
+ * optionally be overriden to implement more compact representations that align with existing binary
+ * corpus entries. For example, a {@code Serializer<byte[]>} could implement these optional methods
+ * to read and write the raw bytes without preceding length information whenever it is used in an
+ * already delimited context.
+ */
+public interface Serializer<T> extends Detacher<T> {
+ /**
+ * Reads a {@code T} from an endless stream that is eventually 0.
+ *
+ * <p>Implementations
+ * <ul>
+ * <li>MUST not attempt to consume the entire stream;
+ * <li>MUST return a valid {@code T} and not throw for any (even garbage) stream;
+ * <li>SHOULD short-circuit the creation of nested structures upon reading null bytes.
+ * </ul>
+ *
+ * @param in an endless stream that eventually only reads null bytes
+ * @return a {@code T} constructed from the bytes read
+ * @throws IOException declared, but must not be thrown by implementations unless methods called
+ * on {@code in} do
+ */
+ @CheckReturnValue T read(DataInputStream in) throws IOException;
+
+ /**
+ * Writes a {@code T} to a stream in such a way that an equal object can be recovered from the
+ * written bytes via {@link #read(DataInputStream)}.
+ *
+ * <p>Since {@link #read(DataInputStream)} is called with an endless stream, the binary
+ * representation MUST be self-delimiting. For example, when writing out a list, first write its
+ * length.
+ *
+ * @param value the value to write
+ * @param out the stream to write to
+ * @throws IOException declared, but must not be thrown by implementations unless methods called
+ * on {@code out} do
+ */
+ void write(T value, DataOutputStream out) throws IOException;
+
+ /**
+ * Reads a {@code T} from a finite stream, potentially using a simpler representation than that
+ * read by {@link #read(DataInputStream)}.
+ *
+ * <p>The default implementations call extends the stream with null bytes and then calls
+ * {@link #read(DataInputStream)}.
+ *
+ * <p>Implementations
+ * <ul>
+ * <li>MUST return a valid {@code T} and not throw for any (even garbage) stream;
+ * <li>SHOULD short-circuit the creation of nested structures upon reading null bytes;
+ * <li>SHOULD naturally consume the entire stream.
+ * </ul>
+ *
+ * @param in a finite stream
+ * @return a {@code T} constructed from the bytes read
+ * @throws IOException declared, but must not be thrown by implementations unless methods called
+ * on {@code in} do
+ */
+ @CheckReturnValue
+ default T readExclusive(InputStream in) throws IOException {
+ return read(new DataInputStream(extendWithZeros(in)));
+ }
+
+ /**
+ * Writes a {@code T} to a stream in such a way that an equal object can be recovered from the
+ * written bytes via {@link #readExclusive(InputStream)}.
+ *
+ * <p>The default implementations calls through to {@link #read(DataInputStream)} and should only
+ * be overriden if {@link #readExclusive(InputStream)} is.
+ *
+ * <p>As opposed to {@link #read(DataInputStream)}, {@link #readExclusive(InputStream)} is called
+ * with a finite stream. The binary representation of a {@code T} value thus does not have to be
+ * self-delimiting, which can allow for simpler representations. For example, a {@code byte[]} can
+ * be written to the stream without prepending its length.
+ *
+ * @param value the value to write
+ * @param out the stream to write to
+ * @throws IOException declared, but must not be thrown by implementations unless methods called
+ * on {@code out} do
+ */
+ default void writeExclusive(T value, OutputStream out) throws IOException {
+ write(value, new DataOutputStream(out));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java
new file mode 100644
index 00000000..b7bc4d4c
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import static com.code_intelligence.jazzer.mutation.support.ExceptionSupport.asUnchecked;
+
+import com.google.errorprone.annotations.ForOverride;
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+
+/**
+ * Combines an {@link InPlaceMutator} with a {@link Serializer} for objects of type {@code T}.
+ *
+ * <p>If {@code T} can't be mutated in place, implement {@link SerializingMutator} instead.
+ *
+ * <p>Implementing classes SHOULD be declared final.
+ */
+public abstract class SerializingInPlaceMutator<T>
+ extends SerializingMutator<T> implements InPlaceMutator<T> {
+ // ByteArrayInputStream#close is documented as being a no-op, so it is safe to reuse an instance
+ // here.
+ // TODO: Introduce a dedicated empty InputStream implementation.
+ private static final InputStream emptyInputStream = new ByteArrayInputStream(new byte[0]);
+
+ /**
+ * Constructs a default instance of {@code T}.
+ *
+ * <p>The returned value is immediately passed to {@link #initInPlace(Object, PseudoRandom)}.
+ *
+ * <p>Implementing classes SHOULD provide a more efficient implementation.
+ *
+ * @return a default instance of {@code T}
+ */
+ @ForOverride
+ protected T makeDefaultInstance() {
+ try {
+ return readExclusive(emptyInputStream);
+ } catch (IOException e) {
+ throw asUnchecked(e);
+ }
+ }
+
+ @Override
+ public final T init(PseudoRandom prng) {
+ T value = makeDefaultInstance();
+ initInPlace(value, prng);
+ return value;
+ }
+
+ @Override
+ public final T mutate(T value, PseudoRandom prng) {
+ mutateInPlace(value, prng);
+ return value;
+ }
+
+ @Override
+ public final T crossOver(T value, T otherValue, PseudoRandom prng) {
+ crossOverInPlace(value, otherValue, prng);
+ return value;
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java
new file mode 100644
index 00000000..58b2a49b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import com.google.errorprone.annotations.DoNotMock;
+
+/**
+ * Combines a {@link ValueMutator} with a {@link Serializer} for objects of type {@code T}.
+ *
+ * <p>Implementing classes SHOULD be declared final.
+ *
+ * <p>This is the default fully-featured mutator type. If {@code T} can be mutated fully in place,
+ * consider implementing the more versatile {@link SerializingInPlaceMutator} instead.
+ */
+@DoNotMock("Use TestSupport#mockMutator instead")
+public abstract class SerializingMutator<T> implements Serializer<T>, ValueMutator<T> {
+ @Override
+ public final String toString() {
+ return Debuggable.getDebugString(this);
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java
new file mode 100644
index 00000000..aa2b551e
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java
@@ -0,0 +1,75 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.api;
+
+import com.google.errorprone.annotations.CheckReturnValue;
+
+/**
+ * Knows how to initialize and mutate objects of type {@code T} and how to incorporate
+ * (cross over) parts of another object of the same type.
+ *
+ * <p>Certain types can be mutated fully in place. In such cases, prefer implementing the more
+ * versatile {@link InPlaceMutator} instead.
+ *
+ * <p>Implementations
+ * <ul>
+ * <li>MAY weakly associate mutable state with the identity (not equality class) of objects they
+ * have been passed as arguments or returned from initialization functions;
+ * <li>MAY assume that they are only passed arguments that they have initialized or mutated;</li>
+ * <li>SHOULD use {@link com.code_intelligence.jazzer.mutation.support.WeakIdentityHashMap} for
+ * this purpose;
+ * <li>MUST otherwise be deeply immutable;
+ * <li>SHOULD override {@link Object#toString()} to return {@code
+ * Debuggable.getDebugString(this)}.
+ * </ul>
+ *
+ * @param <T> the type this mutator operates on
+ */
+public interface ValueMutator<T> extends Debuggable {
+ /**
+ * Implementations
+ * <ul>
+ * <li>SHOULD, when called repeatedly, return a low amount of duplicates.
+ * </ul>
+ *
+ * @return an instance of {@code T}
+ */
+ @CheckReturnValue T init(PseudoRandom prng);
+
+ /**
+ * Implementations
+ * <ul>
+ * <li>MUST return a value that does not {@link Object#equals(Object)} the argument (if
+ * possible);
+ * <li>SHOULD, when called repeatedly, be able to eventually return any valid value of
+ * type {@code T};
+ * <li>MAY mutate the argument.
+ * </ul>
+ */
+ @CheckReturnValue T mutate(T value, PseudoRandom prng);
+
+ /**
+ * Implementations
+ * <ul>
+ * <li>MUST return a value that does not {@link Object#equals(Object)} the arguments (if
+ * possible);
+ * <li>MAY mutate {@code value}.
+ * <li>MUST NOT mutate {@code otherValue}.
+ * </ul>
+ */
+ @CheckReturnValue T crossOver(T value, T otherValue, PseudoRandom prng);
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel
new file mode 100644
index 00000000..639a3d09
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel
@@ -0,0 +1,11 @@
+java_library(
+ name = "combinator",
+ srcs = glob(["*.java"]),
+ visibility = ["//visibility:public"],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ "@com_github_jhalterman_typetools//:typetools",
+ "@com_google_errorprone_error_prone_type_annotations//jar",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java
new file mode 100644
index 00000000..18fa0288
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java
@@ -0,0 +1,516 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.combinator;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.requireNonNullElements;
+import static java.util.Arrays.stream;
+import static java.util.Objects.requireNonNull;
+import static java.util.stream.Collectors.joining;
+
+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.google.errorprone.annotations.ImmutableTypeParameter;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.util.Arrays;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import java.util.function.Supplier;
+import java.util.function.ToIntFunction;
+import net.jodah.typetools.TypeResolver;
+
+public final class MutatorCombinators {
+ // Inverse frequency in which value mutator should be used in cross over.
+ private final static int INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY = 100;
+
+ private MutatorCombinators() {}
+
+ public static <T, R> InPlaceMutator<T> mutateProperty(
+ Function<T, R> getter, SerializingMutator<R> mutator, BiConsumer<T, R> setter) {
+ requireNonNull(getter);
+ requireNonNull(mutator);
+ requireNonNull(setter);
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ setter.accept(reference, mutator.init(prng));
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ setter.accept(reference, mutator.mutate(getter.apply(reference), prng));
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ // Most of the time cross over of properties should use one of the
+ // given values and only seldom use the property type specific cross
+ // over function. Other mutator combinators delegate to this one and
+ // don't cross over values themselves.
+ R referenceValue = getter.apply(reference);
+ R otherReferenceValue = getter.apply(otherReference);
+ R crossedOver = prng.pickValue(referenceValue, otherReferenceValue,
+ ()
+ -> mutator.crossOver(referenceValue, otherReferenceValue, prng),
+ INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY);
+ if (crossedOver == otherReferenceValue) {
+ // If otherReference was picked, it needs to be detached as mutating
+ // it is prohibited in cross over.
+ crossedOver = mutator.detach(crossedOver);
+ }
+ setter.accept(reference, crossedOver);
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ Class<?> owningType =
+ TypeResolver.resolveRawArguments(Function.class, getter.getClass())[0];
+ return owningType.getSimpleName() + "." + mutator.toDebugString(isInCycle);
+ }
+
+ @Override
+ public String toString() {
+ return Debuggable.getDebugString(this);
+ }
+ };
+ }
+
+ public static <T, R> InPlaceMutator<T> mutateViaView(
+ Function<T, R> map, InPlaceMutator<R> mutator) {
+ requireNonNull(map);
+ requireNonNull(mutator);
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ mutator.initInPlace(map.apply(reference), prng);
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ mutator.mutateInPlace(map.apply(reference), prng);
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ mutator.crossOverInPlace(map.apply(reference), map.apply(otherReference), prng);
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ Class<?> owningType = TypeResolver.resolveRawArguments(Function.class, map.getClass())[0];
+ return owningType.getSimpleName() + " via " + mutator.toDebugString(isInCycle);
+ }
+
+ @Override
+ public String toString() {
+ return Debuggable.getDebugString(this);
+ }
+ };
+ }
+
+ /**
+ * Combines multiple in-place mutators for different parts of a {@code T} into one that picks one
+ * at random whenever it mutates.
+ *
+ * <p>Calling this method with no arguments returns a no-op mutator that may decrease fuzzing
+ * efficiency.
+ */
+ @SafeVarargs
+ public static <T> InPlaceMutator<T> combine(InPlaceMutator<T>... partialMutators) {
+ requireNonNullElements(partialMutators);
+ if (partialMutators.length == 0) {
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {}
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {}
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {}
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "{<empty>}";
+ }
+
+ @Override
+ public String toString() {
+ return Debuggable.getDebugString(this);
+ }
+ };
+ }
+
+ final InPlaceMutator<T>[] mutators = Arrays.copyOf(partialMutators, partialMutators.length);
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ for (InPlaceMutator<T> mutator : mutators) {
+ mutator.initInPlace(reference, prng);
+ }
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ mutators[prng.indexIn(mutators)].mutateInPlace(reference, prng);
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ for (InPlaceMutator<T> mutator : mutators) {
+ mutator.crossOverInPlace(reference, otherReference, prng);
+ }
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return stream(mutators)
+ .map(mutator -> mutator.toDebugString(isInCycle))
+ .collect(joining(", ", "{", "}"));
+ }
+
+ @Override
+ public String toString() {
+ return Debuggable.getDebugString(this);
+ }
+ };
+ }
+
+ public static <T, R> SerializingMutator<R> mutateThenMap(
+ SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) {
+ return new PostComposedMutator<T, R>(mutator, map, inverse) {};
+ }
+
+ public static <T, R> SerializingMutator<R> mutateThenMap(SerializingMutator<T> mutator,
+ Function<T, R> map, Function<R, T> inverse, Function<Predicate<Debuggable>, String> debug) {
+ return new PostComposedMutator<T, R>(mutator, map, inverse) {
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return debug.apply(isInCycle);
+ }
+ };
+ }
+
+ public static <T, @ImmutableTypeParameter R> SerializingMutator<R> mutateThenMapToImmutable(
+ SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) {
+ return new PostComposedMutator<T, R>(mutator, map, inverse) {
+ @Override
+ public R detach(R value) {
+ return value;
+ }
+ };
+ }
+
+ public static <T, @ImmutableTypeParameter R> SerializingMutator<R> mutateThenMapToImmutable(
+ SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse,
+ Function<Predicate<Debuggable>, String> debug) {
+ return new PostComposedMutator<T, R>(mutator, map, inverse) {
+ @Override
+ public R detach(R value) {
+ return value;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return debug.apply(isInCycle);
+ }
+ };
+ }
+
+ public static SerializingMutator<Integer> mutateIndices(int length) {
+ require(length > 1, "There should be at least two indices to choose from");
+ return new SerializingMutator<Integer>() {
+ @Override
+ public Integer read(DataInputStream in) throws IOException {
+ return Math.floorMod(in.readInt(), length);
+ }
+
+ @Override
+ public void write(Integer value, DataOutputStream out) throws IOException {
+ out.writeInt(value);
+ }
+
+ @Override
+ public Integer detach(Integer value) {
+ return value;
+ }
+
+ @Override
+ public Integer init(PseudoRandom prng) {
+ return prng.closedRange(0, length - 1);
+ }
+
+ @Override
+ public Integer mutate(Integer value, PseudoRandom prng) {
+ return prng.otherIndexIn(length, value);
+ }
+
+ @Override
+ public Integer crossOver(Integer value, Integer otherValue, PseudoRandom prng) {
+ return prng.choice() ? value : otherValue;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "mutateIndices(" + length + ")";
+ }
+ };
+ }
+
+ /**
+ * Combines multiple mutators for potentially different types into one that mutates an
+ * {@code Object[]} containing one instance per mutator.
+ */
+ @SuppressWarnings("rawtypes")
+ public static ProductMutator mutateProduct(SerializingMutator... mutators) {
+ return new ProductMutator(mutators);
+ }
+
+ /**
+ * Mutates a sum type (e.g. a Protobuf oneof) in place, preferring to mutate the current state
+ * but occasionally switching to a different state.
+ * @param getState a function that returns the current state of the sum type as an index into
+ * {@code perStateMutators}, or -1 if the state is indeterminate.
+ * @param perStateMutators the mutators for each state
+ * @return a mutator that mutates the sum type in place
+ */
+ @SafeVarargs
+ public static <T> InPlaceMutator<T> mutateSumInPlace(
+ ToIntFunction<T> getState, InPlaceMutator<T>... perStateMutators) {
+ final InPlaceMutator<T>[] mutators = Arrays.copyOf(perStateMutators, perStateMutators.length);
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ mutators[prng.indexIn(mutators)].initInPlace(reference, prng);
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ int currentState = getState.applyAsInt(reference);
+ if (currentState == -1) {
+ // The value is in an indeterminate state, initialize it.
+ initInPlace(reference, prng);
+ } else if (prng.trueInOneOutOf(100) && mutators.length > 1) {
+ // Initialize to a different state.
+ mutators[prng.otherIndexIn(mutators, currentState)].initInPlace(reference, prng);
+ } else {
+ // Mutate within the current state.
+ mutators[currentState].mutateInPlace(reference, prng);
+ }
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ // Try to cross over in current state and leave state changes to the mutate step.
+ int currentState = getState.applyAsInt(reference);
+ int otherState = getState.applyAsInt(otherReference);
+ if (currentState == -1) {
+ // If reference is not initialized to a concrete state yet, try to do so in
+ // the state of other reference, as that's at least some progress.
+ if (otherState == -1) {
+ // If both states are indeterminate, cross over can not be performed.
+ return;
+ }
+ mutators[otherState].initInPlace(reference, prng);
+ } else if (currentState == otherState) {
+ mutators[currentState].crossOverInPlace(reference, otherReference, prng);
+ }
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return stream(mutators)
+ .map(mutator -> mutator.toDebugString(isInCycle))
+ .collect(joining(" | "));
+ }
+ };
+ }
+
+ /**
+ * @return a mutator that behaves identically to the provided one except that its {@link
+ * InPlaceMutator#initInPlace(Object, PseudoRandom)} is a no-op
+ */
+ public static <T> InPlaceMutator<T> withoutInit(InPlaceMutator<T> mutator) {
+ return new InPlaceMutator<T>() {
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ // Intentionally left empty.
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "WithoutInit(" + mutator.toDebugString(isInCycle) + ")";
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ mutator.mutateInPlace(reference, prng);
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ mutator.crossOverInPlace(reference, otherReference, prng);
+ }
+ };
+ }
+
+ /**
+ * Constructs a mutator that always returns the provided fixed value.
+ *
+ * <p>Note: This mutator explicitly breaks the contract of the init and mutate methods. Use
+ * sparingly as it may harm the overall effectivity of the mutator.
+ */
+ public static <@ImmutableTypeParameter T> SerializingMutator<T> fixedValue(T value) {
+ return new SerializingMutator<T>() {
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "FixedValue(" + value + ")";
+ }
+
+ @Override
+ public T read(DataInputStream in) {
+ return value;
+ }
+
+ @Override
+ public void write(T value, DataOutputStream out) {}
+
+ @Override
+ public T detach(T value) {
+ return value;
+ }
+
+ @Override
+ public T init(PseudoRandom prng) {
+ return value;
+ }
+
+ @Override
+ public T mutate(T value, PseudoRandom prng) {
+ return value;
+ }
+
+ @Override
+ public T crossOver(T value, T otherValue, PseudoRandom prng) {
+ return value;
+ }
+ };
+ }
+
+ /**
+ * Assembles the parameters into a full implementation of {@link SerializingInPlaceMutator<T>}:
+ *
+ * @param registerSelf a callback that will receive the uninitialized mutator instance
+ * before {@code lazyMutator} is invoked. For simple cases this can
+ * just do nothing, but it is needed to implement mutators for
+ * structures that are self-referential (e.g. Protobuf message A having
+ * a field of type A).
+ * @param makeDefaultInstance constructs a mutable default instance of {@code T}
+ * @param serializer implementation of the {@link Serializer<T>} part
+ * @param lazyMutator supplies the implementation of the {@link InPlaceMutator<T>} part.
+ * This is guaranteed to be invoked exactly once and only after
+ * {@code registerSelf}.
+ */
+ public static <T> SerializingInPlaceMutator<T> assemble(
+ Consumer<SerializingInPlaceMutator<T>> registerSelf, Supplier<T> makeDefaultInstance,
+ Serializer<T> serializer, Supplier<InPlaceMutator<T>> lazyMutator) {
+ return new DelegatingSerializingInPlaceMutator<>(
+ registerSelf, makeDefaultInstance, serializer, lazyMutator);
+ }
+
+ private static class DelegatingSerializingInPlaceMutator<T> extends SerializingInPlaceMutator<T> {
+ private final Supplier<T> makeDefaultInstance;
+ private final Serializer<T> serializer;
+ private final InPlaceMutator<T> mutator;
+
+ private DelegatingSerializingInPlaceMutator(Consumer<SerializingInPlaceMutator<T>> registerSelf,
+ Supplier<T> makeDefaultInstance, Serializer<T> serializer,
+ Supplier<InPlaceMutator<T>> lazyMutator) {
+ requireNonNull(makeDefaultInstance);
+ requireNonNull(serializer);
+
+ registerSelf.accept(this);
+ this.makeDefaultInstance = makeDefaultInstance;
+ this.serializer = serializer;
+ this.mutator = lazyMutator.get();
+ }
+
+ @Override
+ public void initInPlace(T reference, PseudoRandom prng) {
+ mutator.initInPlace(reference, prng);
+ }
+
+ @Override
+ public void mutateInPlace(T reference, PseudoRandom prng) {
+ mutator.mutateInPlace(reference, prng);
+ }
+
+ @Override
+ public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {
+ mutator.crossOverInPlace(reference, otherReference, prng);
+ }
+
+ @Override
+ protected T makeDefaultInstance() {
+ return makeDefaultInstance.get();
+ }
+
+ @Override
+ public T read(DataInputStream in) throws IOException {
+ return serializer.read(in);
+ }
+
+ @Override
+ public void write(T value, DataOutputStream out) throws IOException {
+ serializer.write(value, out);
+ }
+
+ @Override
+ public T readExclusive(InputStream in) throws IOException {
+ return serializer.readExclusive(in);
+ }
+
+ @Override
+ public void writeExclusive(T value, OutputStream out) throws IOException {
+ serializer.writeExclusive(value, out);
+ }
+
+ @Override
+ public T detach(T value) {
+ return serializer.detach(value);
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ if (isInCycle.test(this)) {
+ return "(cycle)";
+ } else {
+ return mutator.toDebugString(isInCycle);
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java
new file mode 100644
index 00000000..ae8f97cc
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java
@@ -0,0 +1,89 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.combinator;
+
+import static java.util.Objects.requireNonNull;
+
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import net.jodah.typetools.TypeResolver;
+
+abstract class PostComposedMutator<T, R> extends SerializingMutator<R> {
+ private final SerializingMutator<T> mutator;
+ private final Function<T, R> map;
+ private final Function<R, T> inverse;
+
+ PostComposedMutator(SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) {
+ this.mutator = requireNonNull(mutator);
+ this.map = requireNonNull(map);
+ this.inverse = requireNonNull(inverse);
+ }
+
+ @Override
+ public R detach(R value) {
+ return map.apply(mutator.detach(inverse.apply(value)));
+ }
+
+ @Override
+ public final R init(PseudoRandom prng) {
+ return map.apply(mutator.init(prng));
+ }
+
+ @Override
+ public final R mutate(R value, PseudoRandom prng) {
+ return map.apply(mutator.mutate(inverse.apply(value), prng));
+ }
+
+ @Override
+ public R crossOver(R value, R otherValue, PseudoRandom prng) {
+ return map.apply(mutator.crossOver(inverse.apply(value), inverse.apply(otherValue), prng));
+ }
+
+ @Override
+ public final R read(DataInputStream in) throws IOException {
+ return map.apply(mutator.read(in));
+ }
+
+ @Override
+ public final void write(R value, DataOutputStream out) throws IOException {
+ mutator.write(inverse.apply(value), out);
+ }
+
+ @Override
+ public final R readExclusive(InputStream in) throws IOException {
+ return map.apply(mutator.readExclusive(in));
+ }
+
+ @Override
+ public final void writeExclusive(R value, OutputStream out) throws IOException {
+ mutator.writeExclusive(inverse.apply(value), out);
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ Class<?> returnType = TypeResolver.resolveRawArguments(Function.class, map.getClass())[1];
+ return mutator.toDebugString(isInCycle) + " -> " + returnType.getSimpleName();
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java
new file mode 100644
index 00000000..9057fd35
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java
@@ -0,0 +1,138 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.combinator;
+
+import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithZeros;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.requireNonNullElements;
+import static java.util.Arrays.stream;
+import static java.util.stream.Collectors.joining;
+
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.util.Arrays;
+import java.util.function.Predicate;
+
+@SuppressWarnings({"unchecked", "rawtypes"})
+public final class ProductMutator extends SerializingInPlaceMutator<Object[]> {
+ // Inverse frequency in which product type mutators should be used in cross over.
+ private final static int INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY = 100;
+
+ private final SerializingMutator[] mutators;
+
+ ProductMutator(SerializingMutator[] mutators) {
+ requireNonNullElements(mutators);
+ require(mutators.length > 0, "mutators must not be empty");
+ this.mutators = Arrays.copyOf(mutators, mutators.length);
+ }
+
+ @Override
+ public Object[] read(DataInputStream in) throws IOException {
+ Object[] value = new Object[mutators.length];
+ for (int i = 0; i < mutators.length; i++) {
+ value[i] = mutators[i].read(in);
+ }
+ return value;
+ }
+
+ @Override
+ public Object[] readExclusive(InputStream in) throws IOException {
+ Object[] value = new Object[mutators.length];
+ int lastIndex = mutators.length - 1;
+ DataInputStream endlessData = new DataInputStream(extendWithZeros(in));
+ for (int i = 0; i < lastIndex; i++) {
+ value[i] = mutators[i].read(endlessData);
+ }
+ value[lastIndex] = mutators[lastIndex].readExclusive(in);
+ return value;
+ }
+
+ @Override
+ public void write(Object[] value, DataOutputStream out) throws IOException {
+ for (int i = 0; i < mutators.length; i++) {
+ mutators[i].write(value[i], out);
+ }
+ }
+
+ @Override
+ public void writeExclusive(Object[] value, OutputStream out) throws IOException {
+ DataOutputStream dataOut = new DataOutputStream(out);
+ int lastIndex = mutators.length - 1;
+ for (int i = 0; i < lastIndex; i++) {
+ mutators[i].write(value[i], dataOut);
+ }
+ mutators[lastIndex].writeExclusive(value[lastIndex], out);
+ }
+
+ @Override
+ protected Object[] makeDefaultInstance() {
+ return new Object[mutators.length];
+ }
+
+ @Override
+ public void initInPlace(Object[] reference, PseudoRandom prng) {
+ for (int i = 0; i < mutators.length; i++) {
+ reference[i] = mutators[i].init(prng);
+ }
+ }
+
+ @Override
+ public void mutateInPlace(Object[] reference, PseudoRandom prng) {
+ int i = prng.indexIn(mutators);
+ reference[i] = mutators[i].mutate(reference[i], prng);
+ }
+
+ @Override
+ public void crossOverInPlace(Object[] reference, Object[] otherReference, PseudoRandom prng) {
+ for (int i = 0; i < mutators.length; i++) {
+ SerializingMutator mutator = mutators[i];
+ Object value = reference[i];
+ Object otherValue = otherReference[i];
+ Object crossedOver = prng.pickValue(value, otherValue,
+ () -> mutator.crossOver(value, otherValue, prng), INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY);
+ if (crossedOver == otherReference) {
+ // If otherReference was picked, it needs to be detached as mutating
+ // it is prohibited in cross over.
+ crossedOver = mutator.detach(crossedOver);
+ }
+ reference[i] = crossedOver;
+ }
+ }
+
+ @Override
+ public Object[] detach(Object[] value) {
+ Object[] clone = new Object[mutators.length];
+ for (int i = 0; i < mutators.length; i++) {
+ clone[i] = mutators[i].detach(value[i]);
+ }
+ return clone;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return stream(mutators)
+ .map(mutator -> mutator.toDebugString(isInCycle))
+ .collect(joining(", ", "[", "]"));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel
new file mode 100644
index 00000000..50bc180a
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel
@@ -0,0 +1,12 @@
+java_library(
+ name = "engine",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation:__pkg__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation:__subpackages__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java b/src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java
new file mode 100644
index 00000000..515f345b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java
@@ -0,0 +1,288 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.engine;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.support.Preconditions;
+import com.code_intelligence.jazzer.mutation.support.RandomSupport;
+import java.util.List;
+import java.util.SplittableRandom;
+import java.util.function.Supplier;
+
+public final class SeededPseudoRandom implements PseudoRandom {
+ // We use SplittableRandom instead of Random since it doesn't incur unnecessary synchronization
+ // overhead and uses a much better RNG under the hood that can generate all long values.
+ private final SplittableRandom random;
+
+ public SeededPseudoRandom(long seed) {
+ this.random = new SplittableRandom(seed);
+ }
+
+ @Override
+ public boolean choice() {
+ return random.nextBoolean();
+ }
+
+ @Override
+ public boolean trueInOneOutOf(int inverseFrequencyTrue) {
+ // Ensure that the outcome of the choice isn't fixed.
+ require(inverseFrequencyTrue >= 2);
+ return indexIn(inverseFrequencyTrue) == 0;
+ }
+
+ @Override
+ public <T> T pickIn(T[] array) {
+ return array[indexIn(array.length)];
+ }
+
+ @Override
+ public <T> T pickIn(List<T> list) {
+ return list.get(indexIn(list.size()));
+ }
+
+ @Override
+ public <T> int indexIn(T[] array) {
+ return indexIn(array.length);
+ }
+
+ @Override
+ public <T> int indexIn(List<T> list) {
+ return indexIn(list.size());
+ }
+
+ @Override
+ public int indexIn(int range) {
+ require(range >= 1);
+ // TODO: Replace random.nextInt(length) with the fast version of
+ // https://lemire.me/blog/2016/06/30/fast-random-shuffling/, which avoids a modulo operation.
+ // It's slightly more biased for large bounds, but indices and choices tend to be small and
+ // are generated frequently (e.g. when picking a submutator).
+ return random.nextInt(range);
+ }
+
+ @Override
+ public <T> int otherIndexIn(T[] array, int currentIndex) {
+ return otherIndexIn(array.length, currentIndex);
+ }
+
+ @Override
+ public int otherIndexIn(int range, int currentIndex) {
+ int otherIndex = currentIndex + closedRange(1, range - 1);
+ if (otherIndex < range) {
+ return otherIndex;
+ } else {
+ return otherIndex - range;
+ }
+ }
+
+ @Override
+ public int closedRange(int lowerInclusive, int upperInclusive) {
+ require(lowerInclusive <= upperInclusive);
+ int range = upperInclusive - lowerInclusive + 1;
+ if (range > 0) {
+ return lowerInclusive + random.nextInt(range);
+ } else {
+ // The interval [lowerInclusive, upperInclusive] covers at least half of the
+ // [Integer.MIN_VALUE, Integer.MAX_VALUE] range, fall back to rejection sampling with an
+ // expected number of samples <= 2.
+ int r;
+ do {
+ r = random.nextInt();
+ } while (r < lowerInclusive);
+ return r;
+ }
+ }
+
+ @Override
+ public long closedRange(long lowerInclusive, long upperInclusive) {
+ require(lowerInclusive <= upperInclusive);
+ if (upperInclusive < Long.MAX_VALUE) {
+ // upperInclusive + 1 <= Long.MAX_VALUE
+ return random.nextLong(lowerInclusive, upperInclusive + 1);
+ } else if (lowerInclusive > 0) {
+ // upperInclusive + 1 - lowerInclusive <= Long.MAX_VALUE
+ return lowerInclusive + random.nextLong(upperInclusive + 1 - lowerInclusive);
+ } else {
+ // The interval [lowerInclusive, Long.MAX_VALUE] covers at least half of the
+ // [Long.MIN_VALUE, Long.MAX_VALUE] range, fall back to rejection sampling with an expected
+ // number of samples <= 2.
+ long r;
+ do {
+ r = random.nextLong();
+ } while (r < lowerInclusive);
+ return r;
+ }
+ }
+
+ // This function always returns a finite value
+ @Override
+ public float closedRange(float lowerInclusive, float upperInclusive) {
+ require(lowerInclusive <= upperInclusive);
+ if (lowerInclusive == upperInclusive) {
+ require(Double.isFinite(lowerInclusive));
+ return lowerInclusive;
+ }
+ // Special case: [Float.NEGATIVE_INFINITY, -Float.MAX_VALUE]
+ if (lowerInclusive == Float.NEGATIVE_INFINITY && upperInclusive == -Float.MAX_VALUE)
+ return -Float.MAX_VALUE;
+ // Special case: [Float.MAX_VALUE, Float.POSITIVE_INFINITY]
+ if (lowerInclusive == Float.MAX_VALUE && upperInclusive == Float.POSITIVE_INFINITY)
+ return Float.MAX_VALUE;
+ float limitedLower =
+ lowerInclusive == Float.NEGATIVE_INFINITY ? -Float.MAX_VALUE : lowerInclusive;
+ float limitedUpper =
+ upperInclusive == Float.POSITIVE_INFINITY ? Float.MAX_VALUE : upperInclusive;
+
+ // nextDouble(start, bound) is exclusive of bound, so we use Math.nextUp to extend the bound to
+ // the next representable double. The maximal possible range of a float is always finite when
+ // represented as a double. Therefore, we can safely use nextDouble and convert it to a float.
+ return (float) random.nextDouble((double) limitedLower, Math.nextUp((double) limitedUpper));
+ }
+
+ // This function always returns a finite value
+ @Override
+ public double closedRange(double lowerInclusive, double upperInclusive) {
+ require(lowerInclusive <= upperInclusive);
+ if (lowerInclusive == upperInclusive) {
+ require(Double.isFinite(lowerInclusive));
+ return lowerInclusive;
+ }
+ // Special case: [Double.NEGATIVE_INFINITY, -Double.MAX_VALUE]
+ if (lowerInclusive == Double.NEGATIVE_INFINITY && upperInclusive == -Double.MAX_VALUE)
+ return -Double.MAX_VALUE;
+ // Special case: [Double.MAX_VALUE, Double.POSITIVE_INFINITY)
+ if (lowerInclusive == Double.MAX_VALUE && upperInclusive == Double.POSITIVE_INFINITY)
+ return Double.MAX_VALUE;
+
+ // nextDouble(start, bound) cannot deal with infinite values, so we need to limit them
+ double limitedLower =
+ lowerInclusive == Double.NEGATIVE_INFINITY ? -Double.MAX_VALUE : lowerInclusive;
+ double limitedUpper =
+ upperInclusive == Double.POSITIVE_INFINITY ? Double.MAX_VALUE : upperInclusive;
+
+ // After limiting, the range may contain only a single value: return that
+ if (limitedLower == limitedUpper)
+ return limitedLower;
+
+ // random.nextDouble() is exclusive of the upper bound. To include the upper bound,
+ // we extend the bound to the next double value by using Math.nextUp(limitedUpper).
+ double nextUpper =
+ (limitedUpper == Double.MAX_VALUE) ? limitedUpper : Math.nextUp(limitedUpper);
+
+ // This, however, leads to a problem when the upper bound is Double.MAX_VALUE, because the next
+ // double after that is Double.POSITIVE_INFINITY. This case is treated the same as infinite
+ // range case, in the else branch.
+ boolean couldExtendRange = nextUpper != limitedUpper;
+
+ // nextDouble(start, bound) can only deal with finite ranges
+ if (Double.isFinite(nextUpper - limitedLower) && couldExtendRange) {
+ double result = random.nextDouble(limitedLower, nextUpper);
+ // Clamp random.nextDouble() to the upper bound.
+ // This is a workaround for RandomSupport.nextDouble() that causes it to
+ // return values greater than upper bound.
+ // See https://bugs.openjdk.org/browse/JDK-8281183 for a list of affected JDK versions.
+ if (result > limitedUpper)
+ result = limitedUpper;
+ return result;
+ } else {
+ // Ranges that exceeds the maximum representable double value, or ranges that could not be
+ // extended scale a random n from range [0; 1] onto the range [limitLower, limitUpper]
+ // limitedLower * (1 - n) + limitedUpper * n - is the same as:
+ // limitedLower + (limitedUpper - limitedLower) * n
+ // limitedLower + range * n
+ double n = random.nextDouble(0.0, Math.nextUp(1.0));
+ return limitedLower * (1 - n) + limitedUpper * n;
+ }
+ }
+
+ @Override
+ public void bytes(byte[] bytes) {
+ RandomSupport.nextBytes(random, bytes);
+ }
+
+ @Override
+ public int closedRangeBiasedTowardsSmall(int upperInclusive) {
+ if (upperInclusive == 0) {
+ return 0;
+ }
+ Preconditions.require(upperInclusive > 0);
+ // Modified from (Apache-2.0)
+ // https://github.com/abseil/abseil-cpp/blob/2927340217c37328319b5869285a6dcdbc13e7a7/absl/random/zipf_distribution.h
+ // by inlining the values v = 1 and q = 2.
+ final double kd = upperInclusive;
+ final double hxm = zipf_h(kd + 0.5);
+ final double h0x5 = -1.0 / 1.5;
+ final double elogv_q = 1.0;
+ final double hx0_minus_hxm = (h0x5 - elogv_q) - hxm;
+ final double s = 0.46153846153846123;
+ double k;
+ while (true) {
+ final double v = random.nextDouble();
+ final double u = hxm + v * hx0_minus_hxm;
+ final double x = zipf_hinv(u);
+ k = Math.floor(x + 0.5);
+ if (k > kd) {
+ continue;
+ }
+ if (k - x <= s) {
+ break;
+ }
+ final double h = zipf_h(k + 0.5);
+ final double r = zipf_pow_negative_q(1.0 + k);
+ if (u >= h - r) {
+ break;
+ }
+ }
+ return (int) k;
+ }
+
+ @Override
+ public int closedRangeBiasedTowardsSmall(int lowerInclusive, int upperInclusive) {
+ return lowerInclusive + closedRangeBiasedTowardsSmall(upperInclusive - lowerInclusive);
+ }
+
+ private static double zipf_h(double x) {
+ return -1.0 / (x + 1.0);
+ }
+
+ private static double zipf_hinv(double x) {
+ return -1.0 + -1.0 / x;
+ }
+
+ private static double zipf_pow_negative_q(double x) {
+ return 1.0 / (x * x);
+ }
+
+ @Override
+ public <T> T pickValue(
+ T value, T otherValue, Supplier<T> supplier, int inverseSupplierFrequency) {
+ if (trueInOneOutOf(inverseSupplierFrequency)) {
+ return supplier.get();
+ } else if (choice()) {
+ return value;
+ } else {
+ return otherValue;
+ }
+ }
+
+ @Override
+ public long nextLong() {
+ return random.nextLong();
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel
new file mode 100644
index 00000000..b922a86a
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel
@@ -0,0 +1,14 @@
+java_library(
+ name = "mutator",
+ srcs = glob(["*.java"]),
+ visibility = ["//visibility:public"],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java
new file mode 100644
index 00000000..fcc4d7ea
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator;
+
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.visitAnnotatedType;
+import static java.lang.String.format;
+import static java.util.Arrays.stream;
+import static java.util.stream.Collectors.joining;
+
+import com.code_intelligence.jazzer.mutation.annotation.AppliesTo;
+import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.mutator.collection.CollectionMutators;
+import com.code_intelligence.jazzer.mutation.mutator.lang.LangMutators;
+import com.code_intelligence.jazzer.mutation.mutator.proto.ProtoMutators;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+
+public final class Mutators {
+ private Mutators() {}
+
+ public static MutatorFactory newFactory() {
+ return new ChainedMutatorFactory(
+ LangMutators.newFactory(), CollectionMutators.newFactory(), ProtoMutators.newFactory());
+ }
+
+ /**
+ * Throws an exception if any annotation on {@code type} violates the restrictions of its
+ * {@link AppliesTo} meta-annotation.
+ */
+ public static void validateAnnotationUsage(AnnotatedType type) {
+ visitAnnotatedType(type, (clazz, annotations) -> {
+ outer:
+ for (Annotation annotation : annotations) {
+ AppliesTo appliesTo = annotation.annotationType().getAnnotation(AppliesTo.class);
+ if (appliesTo == null) {
+ continue;
+ }
+ for (Class<?> allowedClass : appliesTo.value()) {
+ if (allowedClass == clazz) {
+ continue outer;
+ }
+ }
+ for (Class<?> allowedSuperClass : appliesTo.subClassesOf()) {
+ if (allowedSuperClass.isAssignableFrom(clazz)) {
+ continue outer;
+ }
+ }
+
+ String helpText = "";
+ if (appliesTo.value().length != 0) {
+ helpText = stream(appliesTo.value()).map(Class::getName).collect(joining(", "));
+ }
+ if (appliesTo.subClassesOf().length != 0) {
+ if (!helpText.isEmpty()) {
+ helpText += "as well as ";
+ }
+ helpText += "subclasses of ";
+ helpText += stream(appliesTo.subClassesOf()).map(Class::getName).collect(joining(", "));
+ }
+ // Use the simple name as our annotations live in a single package.
+ throw new IllegalArgumentException(format("%s does not apply to %s, only applies to %s",
+ annotation.annotationType().getSimpleName(), clazz.getName(), helpText));
+ }
+ });
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel
new file mode 100644
index 00000000..288b700a
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel
@@ -0,0 +1,13 @@
+java_library(
+ name = "collection",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation/mutator:__subpackages__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java
new file mode 100644
index 00000000..c124f517
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java
@@ -0,0 +1,226 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.collection;
+
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+final class ChunkCrossOvers {
+ private ChunkCrossOvers() {}
+
+ static <T> void insertChunk(List<T> list, List<T> otherList, int maxSize, PseudoRandom prng) {
+ int maxChunkSize = Math.min(maxSize - list.size(), Math.min(list.size(), otherList.size()));
+ withChunk(list, otherList, maxChunkSize, prng,
+ (fromPos, toPos, chunk) -> { list.addAll(toPos, chunk); });
+ }
+
+ static <T> void overwriteChunk(List<T> list, List<T> otherList, PseudoRandom prng) {
+ int maxChunkSize = Math.min(list.size(), otherList.size());
+ withChunkElements(list, otherList, maxChunkSize, prng, list::set);
+ }
+
+ static <T> void crossOverChunk(
+ List<T> list, List<T> otherList, SerializingMutator<T> elementMutator, PseudoRandom prng) {
+ int maxChunkSize = Math.min(list.size(), otherList.size());
+ withChunkElements(list, otherList, maxChunkSize, prng, (toPos, element) -> {
+ list.set(toPos, elementMutator.crossOver(list.get(toPos), element, prng));
+ });
+ }
+
+ @FunctionalInterface
+ private interface ChunkListOperation<T> {
+ void apply(int fromPos, int toPos, List<T> chunk);
+ }
+
+ @FunctionalInterface
+ private interface ChunkListElementOperation<T> {
+ void apply(int toPos, T chunk);
+ }
+
+ static private <T> void withChunk(List<T> list, List<T> otherList, int maxChunkSize,
+ PseudoRandom prng, ChunkListOperation<T> operation) {
+ if (maxChunkSize == 0) {
+ return;
+ }
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxChunkSize);
+ int fromPos = prng.closedRange(0, otherList.size() - chunkSize);
+ int toPos = prng.closedRange(0, list.size() - chunkSize);
+ List<T> chunk = otherList.subList(fromPos, fromPos + chunkSize);
+ operation.apply(fromPos, toPos, chunk);
+ }
+
+ static private <T> void withChunkElements(List<T> list, List<T> otherList, int maxChunkSize,
+ PseudoRandom prng, ChunkListElementOperation<T> operation) {
+ withChunk(list, otherList, maxChunkSize, prng, (fromPos, toPos, chunk) -> {
+ for (int i = 0; i < chunk.size(); i++) {
+ operation.apply(toPos + i, chunk.get(i));
+ }
+ });
+ }
+
+ static <K, V> void insertChunk(
+ Map<K, V> map, Map<K, V> otherMap, int maxSize, PseudoRandom prng) {
+ int originalSize = map.size();
+ int maxChunkSize = Math.min(maxSize - originalSize, otherMap.size());
+ withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> {
+ // insertChunk only inserts new entries and does not overwrite existing
+ // ones. As skipping those entries would lead to fewer insertions than
+ // requested, loop over the rest of the map to fill the chunk.
+ while (map.size() < originalSize + chunkSize && fromIterator.hasNext()) {
+ Entry<K, V> entry = fromIterator.next();
+ if (!map.containsKey(entry.getKey())) {
+ map.put(entry.getKey(), entry.getValue());
+ }
+ }
+ });
+ }
+
+ static <K, V> void overwriteChunk(Map<K, V> map, Map<K, V> otherMap, PseudoRandom prng) {
+ int maxChunkSize = Math.min(map.size(), otherMap.size());
+ withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> {
+ // As keys can not be overwritten, only removed and new ones added, this
+ // cross over overwrites the values. Removal of keys is handled by the
+ // removeChunk mutation. Value equality is not checked here.
+ for (int i = 0; i < chunkSize; i++) {
+ Entry<K, V> from = fromIterator.next();
+ Entry<K, V> to = toIterator.next();
+ to.setValue(from.getValue());
+ }
+ });
+ }
+
+ static <K, V> void crossOverChunk(Map<K, V> map, Map<K, V> otherMap,
+ SerializingMutator<K> keyMutator, SerializingMutator<V> valueMutator, PseudoRandom prng) {
+ if (prng.choice()) {
+ crossOverChunkKeys(map, otherMap, keyMutator, prng);
+ } else {
+ crossOverChunkValues(map, otherMap, valueMutator, prng);
+ }
+ }
+
+ private static <K, V> void crossOverChunkKeys(
+ Map<K, V> map, Map<K, V> otherMap, SerializingMutator<K> keyMutator, PseudoRandom prng) {
+ int maxChunkSize = Math.min(map.size(), otherMap.size());
+ withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> {
+ Map<K, V> entriesToAdd = new LinkedHashMap<>(chunkSize);
+ for (int i = 0; i < chunkSize; i++) {
+ Entry<K, V> to = toIterator.next();
+ Entry<K, V> from = fromIterator.next();
+
+ // The entry has to be removed from the map before the cross-over, as
+ // mutating its key could cause problems in subsequent lookups.
+ // Furthermore, no new entries may be added while using the iterator,
+ // so crossed-over keys are collected for later addition.
+ K key = to.getKey();
+ V value = to.getValue();
+ toIterator.remove();
+
+ // As cross-overs do not guarantee to mutate the given object, no
+ // checks if the crossed over key already exists in the map are
+ // performed. This potentially overwrites existing entries or
+ // generates equal keys.
+ // In case of cross over this behavior is acceptable.
+ K newKey = keyMutator.crossOver(key, from.getKey(), prng);
+
+ // Prevent null keys, as those are not allowed in some map implementations.
+ if (newKey != null) {
+ entriesToAdd.put(newKey, value);
+ }
+ }
+ map.putAll(entriesToAdd);
+ });
+ }
+
+ private static <K, V> void crossOverChunkValues(
+ Map<K, V> map, Map<K, V> otherMap, SerializingMutator<V> valueMutator, PseudoRandom prng) {
+ int maxChunkSize = Math.min(map.size(), otherMap.size());
+ withChunkElements(map, otherMap, maxChunkSize, prng, (fromEntry, toEntry) -> {
+ // As cross-overs do not guarantee to mutate the given object, no
+ // checks if a new value is produced are performed.
+ V newValue = valueMutator.crossOver(toEntry.getValue(), fromEntry.getValue(), prng);
+
+ // The cross-over could have already mutated value, but explicitly set it
+ // through the iterator to be sure.
+ toEntry.setValue(newValue);
+ });
+ }
+
+ @FunctionalInterface
+ private interface ChunkMapOperation<K, V> {
+ void apply(Iterator<Entry<K, V>> fromIterator, Iterator<Entry<K, V>> toIterator, int chunkSize);
+ }
+
+ @FunctionalInterface
+ private interface ChunkMapElementOperation<K, V> {
+ void apply(Entry<K, V> fromEntry, Entry<K, V> toEntry);
+ }
+
+ static <K, V> void withChunk(Map<K, V> map, Map<K, V> otherMap, int maxChunkSize,
+ PseudoRandom prng, ChunkMapOperation<K, V> operation) {
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxChunkSize);
+ int fromChunkOffset = prng.closedRange(0, otherMap.size() - chunkSize);
+ int toChunkOffset = prng.closedRange(0, map.size() - chunkSize);
+ Iterator<Entry<K, V>> fromIterator = otherMap.entrySet().iterator();
+ for (int i = 0; i < fromChunkOffset; i++) {
+ fromIterator.next();
+ }
+ Iterator<Entry<K, V>> toIterator = map.entrySet().iterator();
+ for (int i = 0; i < toChunkOffset; i++) {
+ toIterator.next();
+ }
+ operation.apply(fromIterator, toIterator, chunkSize);
+ }
+
+ static <K, V> void withChunkElements(Map<K, V> map, Map<K, V> otherMap, int maxChunkSize,
+ PseudoRandom prng, ChunkMapElementOperation<K, V> operation) {
+ withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> {
+ for (int i = 0; i < chunkSize; i++) {
+ operation.apply(fromIterator.next(), toIterator.next());
+ }
+ });
+ }
+
+ public enum CrossOverAction {
+ INSERT_CHUNK,
+ OVERWRITE_CHUNK,
+ CROSS_OVER_CHUNK,
+ NOOP;
+
+ public static CrossOverAction pickRandomCrossOverAction(
+ Collection<?> reference, Collection<?> otherReference, int maxSize, PseudoRandom prng) {
+ List<CrossOverAction> actions = new ArrayList<>();
+ if (reference.size() < maxSize && !otherReference.isEmpty()) {
+ actions.add(INSERT_CHUNK);
+ }
+ if (!reference.isEmpty() && !otherReference.isEmpty()) {
+ actions.add(OVERWRITE_CHUNK);
+ actions.add(CROSS_OVER_CHUNK);
+ }
+ if (actions.isEmpty()) {
+ return NOOP; // prevent NPE
+ }
+ return prng.pickIn(actions);
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java
new file mode 100644
index 00000000..d5260289
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java
@@ -0,0 +1,243 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.collection;
+
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.api.ValueMutator;
+import com.code_intelligence.jazzer.mutation.support.Preconditions;
+import java.util.AbstractList;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+// Based on (Apache-2.0)
+// https://github.com/google/fuzztest/blob/f81257ed70ec7b9c191b633588cb6e39c42da5e4/fuzztest/internal/domains/container_mutation_helpers.h
+@SuppressWarnings("unchecked")
+final class ChunkMutations {
+ private static final int MAX_FAILED_INSERTION_ATTEMPTS = 100;
+
+ private ChunkMutations() {}
+
+ static <T> void deleteRandomChunk(List<T> list, int minSize, PseudoRandom prng) {
+ int oldSize = list.size();
+ int minFinalSize = Math.max(minSize, oldSize / 2);
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize - minFinalSize);
+ int chunkOffset = prng.closedRange(0, oldSize - chunkSize);
+
+ list.subList(chunkOffset, chunkOffset + chunkSize).clear();
+ }
+
+ static <T> void deleteRandomChunk(Collection<T> collection, int minSize, PseudoRandom prng) {
+ int oldSize = collection.size();
+ int minFinalSize = Math.max(minSize, oldSize / 2);
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize - minFinalSize);
+ int chunkOffset = prng.closedRange(0, oldSize - chunkSize);
+
+ Iterator<T> it = collection.iterator();
+ for (int i = 0; i < chunkOffset; i++) {
+ it.next();
+ }
+ for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) {
+ it.next();
+ it.remove();
+ }
+ }
+
+ static <T> void insertRandomChunk(
+ List<T> list, int maxSize, SerializingMutator<T> elementMutator, PseudoRandom prng) {
+ int oldSize = list.size();
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxSize - oldSize);
+ int chunkOffset = prng.closedRange(0, oldSize);
+
+ T baseElement = elementMutator.init(prng);
+ T[] chunk = (T[]) new Object[chunkSize];
+ for (int i = 0; i < chunk.length; i++) {
+ chunk[i] = elementMutator.detach(baseElement);
+ }
+ // ArrayList#addAll relies on Collection#toArray, but Arrays#asList returns a List whose
+ // toArray() always makes a copy. We avoid this by using a custom list implementation.
+ list.addAll(chunkOffset, new ArraySharingList<>(chunk));
+ }
+
+ static <T> boolean insertRandomChunk(Set<T> set, Consumer<T> addIfNew, int maxSize,
+ ValueMutator<T> elementMutator, PseudoRandom prng) {
+ int oldSize = set.size();
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxSize - oldSize);
+ return growBy(set, addIfNew, chunkSize, () -> elementMutator.init(prng));
+ }
+
+ static <T> void mutateRandomChunk(List<T> list, ValueMutator<T> mutator, PseudoRandom prng) {
+ int size = list.size();
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, size);
+ int chunkOffset = prng.closedRange(0, size - chunkSize);
+
+ for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) {
+ list.set(i, mutator.mutate(list.get(i), prng));
+ }
+ }
+
+ static <K, V, KW, VW> boolean mutateRandomKeysChunk(
+ Map<K, V> map, SerializingMutator<K> keyMutator, PseudoRandom prng) {
+ int originalSize = map.size();
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, originalSize);
+ int chunkOffset = prng.closedRange(0, originalSize - chunkSize);
+
+ // To ensure that mutating keys actually results in the set of keys changing and not just their
+ // values (which is what #mutateRandomValuesChunk is for), we keep the keys to mutate in the
+ // map, try to add new keys (that are therefore distinct from the keys to mutate) and only
+ // remove the successfully mutated keys in the end.
+ ArrayDeque<KW> keysToMutate = new ArrayDeque<>(chunkSize);
+ ArrayDeque<VW> values = new ArrayDeque<>(chunkSize);
+ ArrayList<K> keysToRemove = new ArrayList<>(chunkSize);
+ Iterator<Map.Entry<K, V>> it = map.entrySet().iterator();
+ for (int i = 0; i < chunkOffset; i++) {
+ it.next();
+ }
+ for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) {
+ Map.Entry<K, V> entry = it.next();
+ // ArrayDeque cannot hold null elements, which requires us to replace null with a sentinel.
+ // Also detach the key as keys may be mutable and mutation could destroy them.
+ keysToMutate.add(boxNull(keyMutator.detach(entry.getKey())));
+ values.add(boxNull(entry.getValue()));
+ keysToRemove.add(entry.getKey());
+ }
+
+ Consumer<K> addIfNew = key -> {
+ int sizeBeforeAdd = map.size();
+ map.putIfAbsent(key, unboxNull(values.peekFirst()));
+ // The mutated key was new, try to mutate and add the next in line.
+ if (map.size() > sizeBeforeAdd) {
+ keysToMutate.removeFirst();
+ values.removeFirst();
+ }
+ };
+ Supplier<K> nextCandidate = () -> {
+ // Mutate the next candidate in the queue.
+ K candidate = keyMutator.mutate(unboxNull(keysToMutate.removeFirst()), prng);
+ keysToMutate.addFirst(boxNull(candidate));
+ return candidate;
+ };
+
+ growBy(map.keySet(), addIfNew, chunkSize, nextCandidate);
+ // Remove the original keys that were successfully mutated into new keys. Since the original
+ // keys have been kept in the map up to this point, all keys added were successfully mutated to
+ // be unequal to the original keys.
+ int grownBy = map.size() - originalSize;
+ keysToRemove.stream().limit(grownBy).forEach(map::remove);
+ return grownBy > 0;
+ }
+
+ public static <K, V> void mutateRandomValuesChunk(
+ Map<K, V> map, ValueMutator<V> valueMutator, PseudoRandom prng) {
+ Collection<Map.Entry<K, V>> collection = map.entrySet();
+ int oldSize = collection.size();
+ int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize);
+ int chunkOffset = prng.closedRange(0, oldSize - chunkSize);
+
+ Iterator<Map.Entry<K, V>> it = collection.iterator();
+ for (int i = 0; i < chunkOffset; i++) {
+ it.next();
+ }
+ for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) {
+ Entry<K, V> entry = it.next();
+ entry.setValue(valueMutator.mutate(entry.getValue(), prng));
+ }
+ }
+
+ static <T> boolean growBy(
+ Set<T> set, Consumer<T> addIfNew, int delta, Supplier<T> candidateSupplier) {
+ int oldSize = set.size();
+ Preconditions.require(delta >= 0);
+
+ final int targetSize = oldSize + delta;
+ int remainingAttempts = MAX_FAILED_INSERTION_ATTEMPTS;
+ int currentSize = set.size();
+ while (currentSize < targetSize) {
+ // If addIfNew fails, the size of set will not increase.
+ addIfNew.accept(candidateSupplier.get());
+ int newSize = set.size();
+ if (newSize == currentSize && remainingAttempts-- == 0) {
+ return false;
+ } else {
+ currentSize = newSize;
+ }
+ }
+ return true;
+ }
+
+ private static final Object BOXED_NULL = new Object();
+
+ private static <T, TW> TW boxNull(T object) {
+ return object != null ? (TW) object : (TW) BOXED_NULL;
+ }
+
+ private static <T, TW> T unboxNull(TW object) {
+ return object != BOXED_NULL ? (T) object : null;
+ }
+
+ public enum MutationAction {
+ DELETE_CHUNK,
+ INSERT_CHUNK,
+ MUTATE_CHUNK;
+
+ public static MutationAction pickRandomMutationAction(
+ Collection<?> c, int minSize, int maxSize, PseudoRandom prng) {
+ List<MutationAction> actions = new ArrayList<>();
+ if (c.size() > minSize) {
+ actions.add(DELETE_CHUNK);
+ }
+ if (c.size() < maxSize) {
+ actions.add(INSERT_CHUNK);
+ }
+ if (!c.isEmpty()) {
+ actions.add(MUTATE_CHUNK);
+ }
+ return prng.pickIn(actions);
+ }
+ }
+
+ private static final class ArraySharingList<T> extends AbstractList<T> {
+ private final T[] array;
+
+ ArraySharingList(T[] array) {
+ this.array = array;
+ }
+
+ @Override
+ public T get(int i) {
+ return array[i];
+ }
+
+ @Override
+ public int size() {
+ return array.length;
+ }
+
+ @Override
+ public Object[] toArray() {
+ return array;
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java
new file mode 100644
index 00000000..cf819f11
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java
@@ -0,0 +1,28 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.collection;
+
+import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+
+public final class CollectionMutators {
+ private CollectionMutators() {}
+
+ public static MutatorFactory newFactory() {
+ return new ChainedMutatorFactory(new ListMutatorFactory(), new MapMutatorFactory());
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java
new file mode 100644
index 00000000..86ecbd4f
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java
@@ -0,0 +1,167 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.collection;
+
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.CrossOverAction.pickRandomCrossOverAction;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.crossOverChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.insertChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.overwriteChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.MutationAction.pickRandomMutationAction;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.deleteRandomChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.insertRandomChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomChunk;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.parameterTypeIfParameterized;
+import static java.lang.Math.min;
+import static java.lang.String.format;
+
+import com.code_intelligence.jazzer.mutation.annotation.WithSize;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.support.RandomSupport;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.reflect.AnnotatedType;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Optional;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+final class ListMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ Optional<WithSize> withSize = Optional.ofNullable(type.getAnnotation(WithSize.class));
+ int minSize = withSize.map(WithSize::min).orElse(ListMutator.DEFAULT_MIN_SIZE);
+ int maxSize = withSize.map(WithSize::max).orElse(ListMutator.DEFAULT_MAX_SIZE);
+ return parameterTypeIfParameterized(type, List.class)
+ .flatMap(factory::tryCreate)
+ .map(elementMutator -> new ListMutator<>(elementMutator, minSize, maxSize));
+ }
+
+ private static final class ListMutator<T> extends SerializingInPlaceMutator<List<T>> {
+ private static final int DEFAULT_MIN_SIZE = 0;
+ private static final int DEFAULT_MAX_SIZE = 1000;
+
+ private final SerializingMutator<T> elementMutator;
+ private final int minSize;
+ private final int maxSize;
+
+ ListMutator(SerializingMutator<T> elementMutator, int minSize, int maxSize) {
+ this.elementMutator = elementMutator;
+ this.minSize = minSize;
+ this.maxSize = maxSize;
+ require(maxSize >= 1, format("WithSize#max=%d needs to be greater than 0", maxSize));
+ require(minSize >= 0, format("WithSize#min=%d needs to be positive", minSize));
+ require(minSize <= maxSize,
+ format("WithSize#min=%d needs to be smaller or equal than WithSize#max=%d", minSize,
+ maxSize));
+ }
+
+ @Override
+ public List<T> read(DataInputStream in) throws IOException {
+ int size = RandomSupport.clamp(in.readInt(), minSize, maxSize);
+ ArrayList<T> list = new ArrayList<>(size);
+ for (int i = 0; i < size; i++) {
+ list.add(elementMutator.read(in));
+ }
+ return list;
+ }
+
+ @Override
+ public void write(List<T> list, DataOutputStream out) throws IOException {
+ out.writeInt(list.size());
+ for (T element : list) {
+ elementMutator.write(element, out);
+ }
+ }
+
+ @Override
+ protected List<T> makeDefaultInstance() {
+ return new ArrayList<>(maxInitialSize());
+ }
+
+ @Override
+ public void initInPlace(List<T> list, PseudoRandom prng) {
+ int targetSize = prng.closedRange(minInitialSize(), maxInitialSize());
+ list.clear();
+ for (int i = 0; i < targetSize; i++) {
+ list.add(elementMutator.init(prng));
+ }
+ }
+
+ @Override
+ public void mutateInPlace(List<T> list, PseudoRandom prng) {
+ switch (pickRandomMutationAction(list, minSize, maxSize, prng)) {
+ case DELETE_CHUNK:
+ deleteRandomChunk(list, minSize, prng);
+ break;
+ case INSERT_CHUNK:
+ insertRandomChunk(list, maxSize, elementMutator, prng);
+ break;
+ case MUTATE_CHUNK:
+ mutateRandomChunk(list, elementMutator, prng);
+ break;
+ default:
+ throw new IllegalStateException("unsupported action");
+ }
+ }
+
+ @Override
+ public void crossOverInPlace(List<T> reference, List<T> otherReference, PseudoRandom prng) {
+ // These cross-over functions don't remove entries, that is handled by
+ // the appropriate mutations on the result.
+ switch (pickRandomCrossOverAction(reference, otherReference, maxSize, prng)) {
+ case INSERT_CHUNK:
+ insertChunk(reference, otherReference, maxSize, prng);
+ break;
+ case OVERWRITE_CHUNK:
+ overwriteChunk(reference, otherReference, prng);
+ break;
+ case CROSS_OVER_CHUNK:
+ crossOverChunk(reference, otherReference, elementMutator, prng);
+ break;
+ default:
+ // Both lists are empty or could otherwise not be crossed over.
+ }
+ }
+
+ @Override
+ public List<T> detach(List<T> value) {
+ return value.stream()
+ .map(elementMutator::detach)
+ .collect(Collectors.toCollection(() -> new ArrayList<>(value.size())));
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "List<" + elementMutator.toDebugString(isInCycle) + ">";
+ }
+
+ private int minInitialSize() {
+ return minSize;
+ }
+
+ private int maxInitialSize() {
+ return min(maxSize, minSize + 1);
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java
new file mode 100644
index 00000000..fca8b5cb
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java
@@ -0,0 +1,205 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.collection;
+
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.CrossOverAction.pickRandomCrossOverAction;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.crossOverChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.insertChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.overwriteChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.MutationAction.pickRandomMutationAction;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.deleteRandomChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.growBy;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.insertRandomChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomKeysChunk;
+import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomValuesChunk;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.check;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.parameterTypesIfParameterized;
+import static java.lang.Math.min;
+import static java.lang.String.format;
+import static java.util.stream.Collectors.toMap;
+
+import com.code_intelligence.jazzer.mutation.annotation.WithSize;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.support.RandomSupport;
+import com.code_intelligence.jazzer.mutation.support.StreamSupport;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Optional;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+final class MapMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ return parameterTypesIfParameterized(type, Map.class)
+ .map(parameterTypes
+ -> parameterTypes.stream()
+ .map(factory::tryCreate)
+ .flatMap(StreamSupport::getOrEmpty)
+ .collect(Collectors.toList()))
+ .map(elementMutators -> {
+ check(elementMutators.size() == 2);
+ int min = MapMutator.DEFAULT_MIN_SIZE;
+ int max = MapMutator.DEFAULT_MAX_SIZE;
+ for (Annotation annotation : type.getDeclaredAnnotations()) {
+ if (annotation instanceof WithSize) {
+ WithSize withSize = (WithSize) annotation;
+ min = withSize.min();
+ max = withSize.max();
+ }
+ }
+ return new MapMutator<>(elementMutators.get(0), elementMutators.get(1), min, max);
+ });
+ }
+
+ private static final class MapMutator<K, V> extends SerializingInPlaceMutator<Map<K, V>> {
+ private static final int DEFAULT_MIN_SIZE = 0;
+ private static final int DEFAULT_MAX_SIZE = 1000;
+
+ private final SerializingMutator<K> keyMutator;
+ private final SerializingMutator<V> valueMutator;
+ private final int minSize;
+ private final int maxSize;
+
+ MapMutator(SerializingMutator<K> keyMutator, SerializingMutator<V> valueMutator, int minSize,
+ int maxSize) {
+ this.keyMutator = keyMutator;
+ this.valueMutator = valueMutator;
+ this.minSize = Math.max(minSize, DEFAULT_MIN_SIZE);
+ this.maxSize = Math.min(maxSize, DEFAULT_MAX_SIZE);
+
+ require(maxSize >= 1, format("WithSize#max=%d needs to be greater than 0", maxSize));
+ // TODO: Add support for min > 0 to map. If min > 0, then #read can fail to construct
+ // sufficiently many distinct keys, but the mutation framework currently doesn't offer
+ // a way to handle this situation gracefully. It is also not clear what behavior users
+ // could reasonably expect in this situation in both regression test and fuzzing mode.
+ require(minSize == 0, "@WithSize#min != 0 is not yet supported for Map");
+ }
+
+ @Override
+ public Map<K, V> read(DataInputStream in) throws IOException {
+ int size = RandomSupport.clamp(in.readInt(), minSize, maxSize);
+ Map<K, V> map = new LinkedHashMap<>(size);
+ for (int i = 0; i < size; i++) {
+ map.put(keyMutator.read(in), valueMutator.read(in));
+ }
+ // map may have less than size entries due to the potential for duplicates, but this is fine
+ // as we currently assert that minSize == 0.
+ return map;
+ }
+
+ @Override
+ public void write(Map<K, V> map, DataOutputStream out) throws IOException {
+ out.writeInt(map.size());
+ for (Map.Entry<K, V> entry : map.entrySet()) {
+ keyMutator.write(entry.getKey(), out);
+ valueMutator.write(entry.getValue(), out);
+ }
+ }
+
+ @Override
+ protected Map<K, V> makeDefaultInstance() {
+ // Use a LinkedHashMap to ensure deterministic iteration order, which makes chunk-based
+ // mutations deterministic. The additional overhead compared to HashMap should be minimal.
+ return new LinkedHashMap<>(maxInitialSize());
+ }
+
+ @Override
+ public void initInPlace(Map<K, V> map, PseudoRandom prng) {
+ int targetSize = prng.closedRange(minInitialSize(), maxInitialSize());
+ map.clear();
+ growBy(map.keySet(),
+ key
+ -> map.putIfAbsent(key, valueMutator.init(prng)),
+ targetSize, () -> keyMutator.init(prng));
+ if (map.size() < minSize) {
+ throw new IllegalStateException(String.format(
+ "Failed to create %d distinct elements of type %s to satisfy the @WithSize#minSize constraint on Map",
+ minSize, keyMutator));
+ }
+ }
+
+ @Override
+ public void mutateInPlace(Map<K, V> map, PseudoRandom prng) {
+ switch (pickRandomMutationAction(map.keySet(), minSize, maxSize, prng)) {
+ case DELETE_CHUNK:
+ deleteRandomChunk(map.keySet(), minSize, prng);
+ break;
+ case INSERT_CHUNK:
+ insertRandomChunk(map.keySet(),
+ key -> map.putIfAbsent(key, valueMutator.init(prng)), maxSize, keyMutator, prng);
+ break;
+ case MUTATE_CHUNK:
+ if (prng.choice() || !mutateRandomKeysChunk(map, keyMutator, prng)) {
+ mutateRandomValuesChunk(map, valueMutator, prng);
+ }
+ break;
+ default:
+ throw new IllegalStateException("unsupported action");
+ }
+ }
+
+ @Override
+ public void crossOverInPlace(Map<K, V> reference, Map<K, V> otherReference, PseudoRandom prng) {
+ switch (
+ pickRandomCrossOverAction(reference.keySet(), otherReference.keySet(), maxSize, prng)) {
+ case INSERT_CHUNK:
+ insertChunk(reference, otherReference, maxSize, prng);
+ break;
+ case OVERWRITE_CHUNK:
+ overwriteChunk(reference, otherReference, prng);
+ break;
+ case CROSS_OVER_CHUNK:
+ crossOverChunk(reference, otherReference, keyMutator, valueMutator, prng);
+ break;
+ default:
+ // Both maps are empty or could otherwise not be crossed over.
+ }
+ }
+
+ @Override
+ public Map<K, V> detach(Map<K, V> value) {
+ return value.entrySet().stream().collect(toMap(entry
+ -> keyMutator.detach(entry.getKey()),
+ entry -> valueMutator.detach(entry.getValue())));
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "Map<" + keyMutator.toDebugString(isInCycle) + ","
+ + valueMutator.toDebugString(isInCycle) + ">";
+ }
+
+ private int minInitialSize() {
+ return minSize;
+ }
+
+ private int maxInitialSize() {
+ return min(maxSize, minSize + 1);
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel
new file mode 100644
index 00000000..5b234cee
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel
@@ -0,0 +1,16 @@
+java_library(
+ name = "lang",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation/mutator:__subpackages__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/combinator",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ "@com_google_errorprone_error_prone_annotations//jar",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java
new file mode 100644
index 00000000..a7dda971
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java
@@ -0,0 +1,79 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass;
+
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.google.errorprone.annotations.Immutable;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.reflect.AnnotatedType;
+import java.util.Optional;
+import java.util.function.Predicate;
+
+final class BooleanMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ return findFirstParentIfClass(type, boolean.class, Boolean.class)
+ .map(parent -> BooleanMutator.INSTANCE);
+ }
+
+ @Immutable
+ private static final class BooleanMutator extends SerializingMutator<Boolean> {
+ private static final BooleanMutator INSTANCE = new BooleanMutator();
+
+ @Override
+ public Boolean read(DataInputStream in) throws IOException {
+ return in.readBoolean();
+ }
+
+ @Override
+ public void write(Boolean value, DataOutputStream out) throws IOException {
+ out.writeBoolean(value);
+ }
+
+ @Override
+ public Boolean init(PseudoRandom prng) {
+ return prng.choice();
+ }
+
+ @Override
+ public Boolean mutate(Boolean value, PseudoRandom prng) {
+ return !value;
+ }
+
+ @Override
+ public Boolean crossOver(Boolean value, Boolean otherValue, PseudoRandom prng) {
+ return prng.choice() ? value : otherValue;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInLoop) {
+ return "Boolean";
+ }
+
+ @Override
+ public Boolean detach(Boolean value) {
+ return value;
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java
new file mode 100644
index 00000000..cdd0d881
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java
@@ -0,0 +1,227 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.readAllBytes;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass;
+
+import com.code_intelligence.jazzer.mutation.annotation.WithLength;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator;
+import com.code_intelligence.jazzer.mutation.support.RandomSupport;
+import com.google.errorprone.annotations.Immutable;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.lang.reflect.AnnotatedType;
+import java.util.Arrays;
+import java.util.Optional;
+import java.util.function.Predicate;
+
+final class ByteArrayMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ Optional<WithLength> withLength = Optional.ofNullable(type.getAnnotation(WithLength.class));
+ int minLength = withLength.map(WithLength::min).orElse(ByteArrayMutator.DEFAULT_MIN_LENGTH);
+ int maxLength = withLength.map(WithLength::max).orElse(ByteArrayMutator.DEFAULT_MAX_LENGTH);
+
+ return findFirstParentIfClass(type, byte[].class)
+ .map(parent -> new ByteArrayMutator(minLength, maxLength));
+ }
+
+ @Immutable
+ private static final class ByteArrayMutator extends SerializingMutator<byte[]> {
+ private static final int DEFAULT_MIN_LENGTH = 0;
+ private static final int DEFAULT_MAX_LENGTH = 1000;
+
+ private final int minLength;
+
+ private final int maxLength;
+
+ private ByteArrayMutator(int min, int max) {
+ this.minLength = min;
+ this.maxLength = max;
+ }
+
+ @Override
+ public byte[] read(DataInputStream in) throws IOException {
+ int length = RandomSupport.clamp(in.readInt(), minLength, maxLength);
+ byte[] bytes = new byte[length];
+ in.readFully(bytes);
+ return bytes;
+ }
+
+ @Override
+ public byte[] readExclusive(InputStream in) throws IOException {
+ return readAllBytes(in);
+ }
+
+ @Override
+ public void write(byte[] value, DataOutputStream out) throws IOException {
+ out.writeInt(value.length);
+ out.write(value);
+ }
+
+ @Override
+ public void writeExclusive(byte[] value, OutputStream out) throws IOException {
+ out.write(value);
+ }
+
+ @Override
+ public byte[] detach(byte[] value) {
+ return Arrays.copyOf(value, value.length);
+ }
+
+ @Override
+ public byte[] init(PseudoRandom prng) {
+ int len = prng.closedRange(minInitialSize(), maxInitialSize());
+ byte[] bytes = new byte[len];
+ prng.bytes(bytes);
+ return bytes;
+ }
+
+ private int minInitialSize() {
+ return minLength;
+ }
+
+ private int maxInitialSize() {
+ // Allow some variation in length, but keep the initial elements well within reach of each
+ // other via a single mutation based on a Table of Recent Compares (ToRC) entry, which is
+ // currently limited to 64 bytes.
+ // Compared to List<T>, byte arrays can't result in recursive type hierarchies and thus don't
+ // to limit their expected initial size to be <= 1.
+ return Math.min(minLength + 16, maxLength);
+ }
+
+ @Override
+ public byte[] mutate(byte[] value, PseudoRandom prng) {
+ int maxLengthIncrease = maxLength - value.length;
+ byte[] mutated = LibFuzzerMutator.mutateDefault(value, maxLengthIncrease);
+ return enforceLength(mutated);
+ }
+
+ private byte[] enforceLength(byte[] mutated) {
+ // if the mutated array libfuzzer returns is too long or short, we truncate or extend it
+ // respectively. if we extend it, then copyOf will fill leftover bytes with 0
+ if (mutated.length > maxLength) {
+ return Arrays.copyOf(mutated, maxLength);
+ } else if (mutated.length < minLength) {
+ return Arrays.copyOf(mutated, minLength);
+ } else {
+ return mutated;
+ }
+ }
+
+ @Override
+ public byte[] crossOver(byte[] value, byte[] otherValue, PseudoRandom prng) {
+ // Passed in values are expected to already honor the min/max length constraints.
+ // As there does not seem to be an easy way to call libFuzzer's internal cross over
+ // algorithm, it is re-implemented in native Java. The algorithm is based on:
+ // https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/fuzzer/FuzzerMutate.cpp#L440
+ // https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/fuzzer/FuzzerCrossOver.cpp#L19
+ //
+
+ if (value.length == 0 || otherValue.length == 0) {
+ return value;
+ }
+
+ // TODO: Measure if this is fast enough.
+ byte[] out = null;
+ while (out == null) {
+ switch (prng.indexIn(3)) {
+ case 0:
+ out = intersect(value, otherValue, prng);
+ break;
+ case 1:
+ out = insertPart(value, otherValue, prng);
+ break;
+ case 2:
+ out = overwritePart(value, otherValue, prng);
+ break;
+ default:
+ throw new AssertionError("Invalid cross over function.");
+ }
+ }
+ return enforceLength(out);
+ }
+
+ private static byte[] intersect(byte[] value, byte[] otherValue, PseudoRandom prng) {
+ int maxOutSize = prng.closedRange(0, Math.min(value.length, otherValue.length));
+ byte[] out = new byte[maxOutSize];
+ int outPos = 0;
+ int valuePos = 0;
+ int otherValuePos = 0;
+ boolean usingFirstValue = true;
+ while (outPos < out.length) {
+ if (usingFirstValue && valuePos < value.length) {
+ int extraSize = rndArraycopy(value, valuePos, out, outPos, prng);
+ outPos += extraSize;
+ valuePos += extraSize;
+ } else if (!usingFirstValue && otherValuePos < otherValue.length) {
+ int extraSize = rndArraycopy(otherValue, otherValuePos, out, outPos, prng);
+ outPos += extraSize;
+ otherValuePos += extraSize;
+ }
+ usingFirstValue = !usingFirstValue;
+ }
+ return out;
+ }
+
+ private static int rndArraycopy(
+ byte[] val, int valPos, byte[] out, int outPos, PseudoRandom prng) {
+ int outSizeLeft = out.length - outPos;
+ int inSizeLeft = val.length - valPos;
+ int maxExtraSize = Math.min(outSizeLeft, inSizeLeft);
+ int extraSize = prng.closedRange(0, maxExtraSize);
+ System.arraycopy(val, valPos, out, outPos, extraSize);
+ return extraSize;
+ }
+
+ private static byte[] insertPart(byte[] value, byte[] otherValue, PseudoRandom prng) {
+ int copySize = prng.closedRange(1, otherValue.length);
+ int f = otherValue.length - copySize;
+ int fromPos = f == 0 ? 0 : prng.indexIn(f);
+ int toPos = prng.indexIn(value.length);
+ int tailSize = value.length - toPos;
+
+ byte[] out = new byte[value.length + copySize];
+ System.arraycopy(value, 0, out, 0, toPos);
+ System.arraycopy(otherValue, fromPos, out, toPos, copySize);
+ System.arraycopy(value, toPos, out, toPos + copySize, tailSize);
+ return out;
+ }
+
+ private static byte[] overwritePart(byte[] value, byte[] otherValue, PseudoRandom prng) {
+ int toPos = prng.indexIn(value.length);
+ int copySize = Math.min(prng.closedRange(1, value.length - toPos), otherValue.length);
+ int f = otherValue.length - copySize;
+ int fromPos = f == 0 ? 0 : prng.indexIn(f);
+ System.arraycopy(otherValue, fromPos, value, toPos, copySize);
+ return value;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "byte[]";
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java
new file mode 100644
index 00000000..80b9e6c9
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateIndices;
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMap;
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty;
+
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.lang.reflect.AnnotatedType;
+import java.util.Optional;
+import java.util.function.Predicate;
+
+final class EnumMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ return asSubclassOrEmpty(type, Enum.class).map(parent -> {
+ require(((Class<Enum<?>>) type.getType()).getEnumConstants().length > 1,
+ String.format(
+ "%s defines less than two enum constants and can't be mutated. Use a constant instead.",
+ parent));
+ Enum<?>[] values = ((Class<Enum<?>>) type.getType()).getEnumConstants();
+ return mutateThenMap(mutateIndices(values.length),
+ (index)
+ -> values[index],
+ Enum::ordinal, (Predicate<Debuggable> inCycle) -> "Enum<" + parent.getSimpleName() + ">");
+ });
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java
new file mode 100644
index 00000000..17890a9f
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java
@@ -0,0 +1,597 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static java.lang.String.format;
+
+import com.code_intelligence.jazzer.mutation.annotation.DoubleInRange;
+import com.code_intelligence.jazzer.mutation.annotation.FloatInRange;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Optional;
+import java.util.function.DoubleFunction;
+import java.util.function.Predicate;
+import java.util.stream.DoubleStream;
+
+final class FloatingPointMutatorFactory extends MutatorFactory {
+ @SuppressWarnings("unchecked")
+ private static final DoubleFunction<Double>[] mathFunctions =
+ new DoubleFunction[] {Math::acos, Math::asin, Math::atan, Math::cbrt, Math::ceil, Math::cos,
+ Math::cosh, Math::exp, Math::expm1, Math::floor, Math::log, Math::log10, Math::log1p,
+ Math::rint, Math::sin, Math::sinh, Math::sqrt, Math::tan, Math::tanh, Math::toDegrees,
+ Math::toRadians, n -> n * 0.5, n -> n * 2.0, n -> n * 0.333333333333333, n -> n * 3.0};
+
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ if (!(type.getType() instanceof Class)) {
+ return Optional.empty();
+ }
+ Class<?> clazz = (Class<?>) type.getType();
+
+ if (clazz == float.class || clazz == Float.class) {
+ return Optional.of(
+ new FloatMutator(type, Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, true));
+ } else if (clazz == double.class || clazz == Double.class) {
+ return Optional.of(
+ new DoubleMutator(type, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, true));
+ } else {
+ return Optional.empty();
+ }
+ }
+
+ static final class FloatMutator extends SerializingMutator<Float> {
+ private static final int EXPONENT_INITIAL_BIT = 23;
+ private static final int MANTISSA_MASK = 0x7fffff;
+ private static final int EXPONENT_MASK = 0xff;
+ private static final int MANTISSA_RANDOM_WALK_RANGE = 1000;
+ private static final int EXPONENT_RANDOM_WALK_RANGE = Float.MAX_EXPONENT;
+ private static final int INVERSE_FREQUENCY_SPECIAL_VALUE = 1000;
+
+ // Visible for testing.
+ final float minValue;
+ final float maxValue;
+ final boolean allowNaN;
+ private final float[] specialValues;
+
+ FloatMutator(AnnotatedType type, float defaultMinValueForType, float defaultMaxValueForType,
+ boolean defaultAllowNaN) {
+ float minValue = defaultMinValueForType;
+ float maxValue = defaultMaxValueForType;
+ boolean allowNaN = defaultAllowNaN;
+ // InRange is not repeatable, so the loop body will apply at most once.
+ for (Annotation annotation : type.getAnnotations()) {
+ if (annotation instanceof FloatInRange) {
+ FloatInRange floatInRange = (FloatInRange) annotation;
+ minValue = floatInRange.min();
+ maxValue = floatInRange.max();
+ allowNaN = floatInRange.allowNaN();
+ }
+ }
+
+ require(minValue <= maxValue,
+ format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type));
+ require(minValue != maxValue,
+ format(
+ "[%f, %f] can not be mutated, use a constant instead: %s", minValue, maxValue, type));
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ this.allowNaN = allowNaN;
+ this.specialValues = collectSpecialValues(minValue, maxValue);
+ }
+
+ private float[] collectSpecialValues(float minValue, float maxValue) {
+ // stream of floats
+ List<Double> specialValues =
+ DoubleStream
+ .of(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, 0.0f, -0.0f, Float.NaN,
+ Float.MAX_VALUE, Float.MIN_VALUE, -Float.MAX_VALUE, -Float.MIN_VALUE,
+ this.minValue, this.maxValue)
+ .filter(n -> (n >= minValue && n <= maxValue) || allowNaN && Double.isNaN(n))
+ .distinct()
+ .sorted()
+ .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
+
+ float[] specialValuesArray = new float[specialValues.size()];
+ for (int i = 0; i < specialValues.size(); i++) {
+ specialValuesArray[i] = (float) (double) specialValues.get(i);
+ }
+ return specialValuesArray;
+ }
+
+ public float mutateWithLibFuzzer(float value) {
+ return LibFuzzerMutator.mutateDefault(value, this, 0);
+ }
+
+ @Override
+ public Float init(PseudoRandom prng) {
+ if (prng.choice()) {
+ return specialValues[prng.closedRange(0, specialValues.length - 1)];
+ } else {
+ return prng.closedRange(minValue, maxValue);
+ }
+ }
+
+ @Override
+ public Float mutate(Float value, PseudoRandom prng) {
+ float result;
+ // small chance to return a special value
+ if (prng.trueInOneOutOf(INVERSE_FREQUENCY_SPECIAL_VALUE)) {
+ result = specialValues[prng.closedRange(0, specialValues.length - 1)];
+ } else {
+ switch (prng.closedRange(0, 5)) {
+ case 0:
+ result = mutateWithBitFlip(value, prng);
+ break;
+ case 1:
+ result = mutateExponent(value, prng);
+ break;
+ case 2:
+ result = mutateMantissa(value, prng);
+ break;
+ case 3:
+ result = mutateWithMathematicalFn(value, prng);
+ break;
+ case 4:
+ result = mutateWithLibFuzzer(value);
+ break;
+ case 5: // random in range cannot exceed the given bounds (and cannot be NaN)
+ result = prng.closedRange(minValue, maxValue);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case");
+ }
+ }
+ result = forceInRange(result, minValue, maxValue, allowNaN);
+
+ // Repeating values are not allowed.
+ if (Float.compare(result, value) == 0) {
+ if (Float.isNaN(result)) {
+ return prng.closedRange(minValue, maxValue);
+ } else { // Change the value to the neighboring float.
+ if (result > minValue && result < maxValue) {
+ return prng.choice() ? Math.nextAfter(result, Float.NEGATIVE_INFINITY)
+ : Math.nextAfter(result, Float.POSITIVE_INFINITY);
+ } else if (result > minValue) {
+ return Math.nextAfter(result, Float.NEGATIVE_INFINITY);
+ } else
+ return Math.nextAfter(result, Float.POSITIVE_INFINITY);
+ }
+ }
+
+ return result;
+ }
+
+ static float forceInRange(float value, float minValue, float maxValue, boolean allowNaN) {
+ if ((value >= minValue && value <= maxValue) || (Float.isNaN(value) && allowNaN))
+ return value;
+
+ // Clamp infinite values
+ if (value == Float.POSITIVE_INFINITY)
+ return maxValue;
+ if (value == Float.NEGATIVE_INFINITY)
+ return minValue;
+
+ // From here on limits should be finite
+ float finiteMax = Math.min(Float.MAX_VALUE, maxValue);
+ float finiteMin = Math.max(-Float.MAX_VALUE, minValue);
+
+ // If NaN was allowed, it was handled above. Replace it by the midpoint of the range.
+ if (Float.isNaN(value))
+ return finiteMin * 0.5f + finiteMax * 0.5f;
+
+ float range = finiteMax - finiteMin;
+ if (range == 0f)
+ return finiteMin;
+
+ float diff = value - finiteMin;
+
+ if (Float.isFinite(diff) && Float.isFinite(range)) {
+ return finiteMin + Math.abs(diff % range);
+ }
+
+ // diff, range, or both are infinite: divide both by 2, reduce, and multiply by 2.
+ float halfDiff = value * 0.5f - finiteMin * 0.5f;
+
+ return finiteMin + (halfDiff % (finiteMax * 0.5f - finiteMin * 0.5f)) * 2.0f;
+ }
+
+ public float mutateWithMathematicalFn(float value, PseudoRandom prng) {
+ double result = prng.pickIn(mathFunctions).apply(value);
+ return (float) result;
+ }
+
+ private float mutateWithBitFlip(float value, PseudoRandom prng) {
+ int bits = Float.floatToRawIntBits(value);
+ int bitToFlip = prng.closedRange(0, 31);
+ bits ^= 1L << bitToFlip;
+ return Float.intBitsToFloat(bits);
+ }
+
+ private float mutateExponent(float value, PseudoRandom prng) {
+ int bits = Float.floatToRawIntBits(value);
+ int exponent = ((bits >> EXPONENT_INITIAL_BIT) & EXPONENT_MASK)
+ + prng.closedRange(0, EXPONENT_RANDOM_WALK_RANGE);
+ bits = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT))
+ | ((exponent % EXPONENT_MASK) << EXPONENT_INITIAL_BIT);
+ return Float.intBitsToFloat(bits);
+ }
+
+ private float mutateMantissa(float value, PseudoRandom prng) {
+ int bits = Float.floatToRawIntBits(value);
+
+ int mantissa = bits & MANTISSA_MASK;
+ switch (prng.closedRange(0, 2)) {
+ case 0: // +
+ mantissa =
+ (mantissa + prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE))
+ % MANTISSA_MASK;
+ break;
+ case 1: // *
+ mantissa =
+ (mantissa * prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE))
+ % MANTISSA_MASK;
+ break;
+ case 2: // /
+ int divisor = prng.closedRange(2, MANTISSA_RANDOM_WALK_RANGE);
+ if (prng.choice()) {
+ divisor = -divisor;
+ }
+ mantissa = (mantissa / divisor);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case for mantissa");
+ }
+ bits = (bits & ~MANTISSA_MASK) | mantissa;
+ return Float.intBitsToFloat(bits);
+ }
+
+ @Override
+ public Float crossOver(Float value, Float otherValue, PseudoRandom prng) {
+ float result;
+ switch (prng.closedRange(0, 2)) {
+ case 0:
+ result = crossOverMean(value, otherValue);
+ break;
+ case 1:
+ result = crossOverExponent(value, otherValue);
+ break;
+ case 2:
+ result = crossOverMantissa(value, otherValue);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case");
+ }
+ return forceInRange(result, minValue, maxValue, allowNaN);
+ }
+
+ private float crossOverMean(float value, float otherValue) {
+ return (float) ((((double) value) + ((double) otherValue)) / 2.0);
+ }
+
+ private float crossOverExponent(float value, float otherValue) {
+ int bits = Float.floatToRawIntBits(value);
+ int otherExponent =
+ Float.floatToRawIntBits(otherValue) & (EXPONENT_MASK << EXPONENT_INITIAL_BIT);
+ int bitsWithOtherExponent = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) | otherExponent;
+ return Float.intBitsToFloat(bitsWithOtherExponent);
+ }
+
+ private float crossOverMantissa(float value, float otherValue) {
+ int bits = Float.floatToRawIntBits(value);
+ int otherMantissa = Float.floatToRawIntBits(otherValue) & MANTISSA_MASK;
+ int bitsWithOtherMantissa = (bits & ~MANTISSA_MASK) | otherMantissa;
+ return Float.intBitsToFloat(bitsWithOtherMantissa);
+ }
+
+ @Override
+ public Float read(DataInputStream in) throws IOException {
+ return forceInRange(in.readFloat(), minValue, maxValue, allowNaN);
+ }
+
+ @Override
+ public void write(Float value, DataOutputStream out) throws IOException {
+ out.writeFloat(value);
+ }
+
+ @Override
+ public Float detach(Float value) {
+ return value;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "Float";
+ }
+ }
+
+ static final class DoubleMutator extends SerializingMutator<Double> {
+ private static final long MANTISSA_RANDOM_WALK_RANGE = 1000;
+ private static final int EXPONENT_RANDOM_WALK_RANGE = Double.MAX_EXPONENT;
+ private static final int INVERSE_FREQUENCY_SPECIAL_VALUE = 1000;
+ private static final long MANTISSA_MASK = 0xfffffffffffffL;
+ private static final long EXPONENT_MASK = 0x7ffL;
+ private static final int EXPONENT_INITIAL_BIT = 52;
+
+ // Visible for testing
+ final double minValue;
+ final double maxValue;
+ final boolean allowNaN;
+ private final double[] specialValues;
+
+ DoubleMutator(AnnotatedType type, double defaultMinValueForType, double defaultMaxValueForType,
+ boolean defaultAllowNaN) {
+ double minValue = defaultMinValueForType;
+ double maxValue = defaultMaxValueForType;
+ boolean allowNaN = defaultAllowNaN;
+ // InRange is not repeatable, so the loop body will apply at most once.
+ for (Annotation annotation : type.getAnnotations()) {
+ if (annotation instanceof DoubleInRange) {
+ DoubleInRange doubleInRange = (DoubleInRange) annotation;
+ minValue = doubleInRange.min();
+ maxValue = doubleInRange.max();
+ allowNaN = doubleInRange.allowNaN();
+ }
+ }
+
+ require(!Double.isNaN(minValue) && !Double.isNaN(maxValue),
+ format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type));
+ require(minValue <= maxValue,
+ format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type));
+ require(minValue != maxValue,
+ format(
+ "[%f, %f] can not be mutated, use a constant instead: %s", minValue, maxValue, type));
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ this.allowNaN = allowNaN;
+ this.specialValues = collectSpecialValues(minValue, maxValue);
+ }
+
+ private double[] collectSpecialValues(double minValue, double maxValue) {
+ double[] specialValues = new double[] {Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
+ 0.0, -0.0, Double.NaN, Double.MAX_VALUE, Double.MIN_VALUE, -Double.MAX_VALUE,
+ -Double.MIN_VALUE, this.minValue, this.maxValue};
+ return Arrays.stream(specialValues)
+ .boxed()
+ .filter(value -> (allowNaN && value.isNaN()) || (value >= minValue && value <= maxValue))
+ .distinct()
+ .sorted()
+ .mapToDouble(Double::doubleValue)
+ .toArray();
+ }
+
+ public double mutateWithLibFuzzer(double value) {
+ return LibFuzzerMutator.mutateDefault(value, this, 0);
+ }
+
+ @Override
+ public Double init(PseudoRandom prng) {
+ if (prng.choice()) {
+ return specialValues[prng.closedRange(0, specialValues.length - 1)];
+ } else {
+ return prng.closedRange(minValue, maxValue);
+ }
+ }
+
+ @Override
+ public Double mutate(Double value, PseudoRandom prng) {
+ double result;
+ // small chance to return a special value
+ if (prng.trueInOneOutOf(INVERSE_FREQUENCY_SPECIAL_VALUE)) {
+ result = specialValues[prng.closedRange(0, specialValues.length - 1)];
+ } else {
+ switch (prng.closedRange(0, 5)) {
+ case 0:
+ result = mutateWithBitFlip(value, prng);
+ break;
+ case 1:
+ result = mutateExponent(value, prng);
+ break;
+ case 2:
+ result = mutateMantissa(value, prng);
+ break;
+ case 3:
+ result = mutateWithMathematicalFn(value, prng);
+ break;
+ case 4:
+ result = mutateWithLibFuzzer(value);
+ break;
+ case 5: // random in range cannot exceed the given bounds (and cannot be NaN)
+ result = prng.closedRange(minValue, maxValue);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case");
+ }
+ }
+ result = forceInRange(result, minValue, maxValue, allowNaN);
+
+ // Repeating values are not allowed.
+ if (Double.compare(result, value) == 0) {
+ if (Double.isNaN(result)) {
+ return prng.closedRange(minValue, maxValue);
+ } else { // Change the value to the neighboring float.
+ if (result > minValue && result < maxValue) {
+ return prng.choice() ? Math.nextAfter(result, Double.NEGATIVE_INFINITY)
+ : Math.nextAfter(result, Double.POSITIVE_INFINITY);
+ } else if (result > minValue) {
+ return Math.nextAfter(result, Double.NEGATIVE_INFINITY);
+ } else
+ return Math.nextAfter(result, Double.POSITIVE_INFINITY);
+ }
+ }
+
+ return result;
+ }
+
+ static double forceInRange(double value, double minValue, double maxValue, boolean allowNaN) {
+ if ((value >= minValue && value <= maxValue) || (Double.isNaN(value) && allowNaN)) {
+ return value;
+ }
+
+ // Clamp infinite values
+ if (value == Double.POSITIVE_INFINITY)
+ return maxValue;
+ if (value == Double.NEGATIVE_INFINITY)
+ return minValue;
+
+ // From here on limits should be finite
+ double finiteMax = Math.min(Double.MAX_VALUE, maxValue);
+ double finiteMin = Math.max(-Double.MAX_VALUE, minValue);
+
+ // If NaN was allowed, it was handled above.
+ // Here we replace NaN by the middle of the clamped finite range.
+ if (Double.isNaN(value)) {
+ // maxValue or minValue may be infinite, so we need to clamp them.
+ return minValue
+ + (Math.min(Double.MAX_VALUE, maxValue) * 0.5
+ - Math.max(-Double.MAX_VALUE, minValue) * 0.5);
+ }
+
+ double range = finiteMax - finiteMin;
+ if (range == 0)
+ return finiteMin;
+
+ double diff = value - finiteMin;
+
+ if (Double.isFinite(diff) && Double.isFinite(range)) {
+ return finiteMin + Math.abs(diff % range);
+ }
+
+ // diff, range, or both are infinite: divide both by 2, reduce, and multiply by 2.
+ double halfDiff = value * 0.5 - finiteMin * 0.5;
+ return finiteMin + (halfDiff % (finiteMax * 0.5 - finiteMin * 0.5)) * 2.0;
+ }
+
+ public double mutateWithMathematicalFn(double value, PseudoRandom prng) {
+ return prng.pickIn(mathFunctions).apply(value);
+ }
+
+ public static double mutateWithBitFlip(double value, PseudoRandom prng) {
+ long bits = Double.doubleToRawLongBits(value);
+ int bitToFlip = prng.closedRange(0, 63);
+ bits ^= 1L << bitToFlip;
+ return Double.longBitsToDouble(bits);
+ }
+
+ private static double mutateExponent(double value, PseudoRandom prng) {
+ long bits = Double.doubleToRawLongBits(value);
+ long exponent = ((bits >> EXPONENT_INITIAL_BIT) & EXPONENT_MASK)
+ + prng.closedRange(0, EXPONENT_RANDOM_WALK_RANGE);
+ bits = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT))
+ | ((exponent % EXPONENT_MASK) << EXPONENT_INITIAL_BIT);
+ return Double.longBitsToDouble(bits);
+ }
+
+ public static double mutateMantissa(double value, PseudoRandom prng) {
+ long bits = Double.doubleToRawLongBits(value);
+ long mantissa = bits & MANTISSA_MASK;
+ switch (prng.closedRange(0, 2)) {
+ case 0: // +
+ mantissa =
+ (mantissa + prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE))
+ % MANTISSA_MASK;
+ break;
+ case 1: // *
+ mantissa =
+ (mantissa * prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE))
+ % MANTISSA_MASK;
+ break;
+ case 2: // /
+ long divisor = prng.closedRange(2, MANTISSA_RANDOM_WALK_RANGE);
+ if (prng.choice()) {
+ divisor = -divisor;
+ }
+ mantissa = (mantissa / divisor);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case for mantissa");
+ }
+ bits = (bits & ~MANTISSA_MASK) | mantissa;
+ return Double.longBitsToDouble(bits);
+ }
+
+ @Override
+ public Double crossOver(Double value, Double otherValue, PseudoRandom prng) {
+ double result;
+ switch (prng.closedRange(0, 2)) {
+ case 0:
+ result = crossOverMean(value, otherValue);
+ break;
+ case 1:
+ result = crossOverExponent(value, otherValue);
+ break;
+ case 2:
+ result = crossOverMantissa(value, otherValue);
+ break;
+ default:
+ throw new IllegalStateException("Unknown mutation case");
+ }
+ return forceInRange(result, minValue, maxValue, allowNaN);
+ }
+
+ private double crossOverMean(double value, double otherValue) {
+ return (value * 0.5) + (otherValue * 0.5);
+ }
+
+ private double crossOverExponent(double value, double otherValue) {
+ long bits = Double.doubleToRawLongBits(value);
+ long otherExponent =
+ Double.doubleToRawLongBits(otherValue) & (EXPONENT_MASK << EXPONENT_INITIAL_BIT);
+ long bitsWithOtherExponent =
+ (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) | otherExponent;
+ return Double.longBitsToDouble(bitsWithOtherExponent);
+ }
+
+ private double crossOverMantissa(double value, double otherValue) {
+ long bits = Double.doubleToRawLongBits(value);
+ long otherMantissa = Double.doubleToRawLongBits(otherValue) & MANTISSA_MASK;
+ long bitsWithOtherMantissa = (bits & ~MANTISSA_MASK) | otherMantissa;
+ return Double.longBitsToDouble(bitsWithOtherMantissa);
+ }
+
+ @Override
+ public Double read(DataInputStream in) throws IOException {
+ return forceInRange(in.readDouble(), minValue, maxValue, allowNaN);
+ }
+
+ @Override
+ public void write(Double value, DataOutputStream out) throws IOException {
+ out.writeDouble(value);
+ }
+
+ @Override
+ public Double detach(Double value) {
+ return value;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "Double";
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java
new file mode 100644
index 00000000..e701e6ad
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java
@@ -0,0 +1,399 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static java.lang.String.format;
+
+import com.code_intelligence.jazzer.mutation.annotation.InRange;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator;
+import com.google.errorprone.annotations.ForOverride;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.ParameterizedType;
+import java.util.Optional;
+import java.util.function.Predicate;
+import java.util.stream.LongStream;
+
+final class IntegralMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ if (!(type.getType() instanceof Class)) {
+ return Optional.empty();
+ }
+ Class<?> clazz = (Class<?>) type.getType();
+
+ if (clazz == byte.class || clazz == Byte.class) {
+ return Optional.of(new AbstractIntegralMutator<Byte>(type, Byte.MIN_VALUE, Byte.MAX_VALUE) {
+ @Override
+ protected long mutateWithLibFuzzer(long value) {
+ return LibFuzzerMutator.mutateDefault((byte) value, this, 0);
+ }
+
+ @Override
+ public Byte init(PseudoRandom prng) {
+ return (byte) initImpl(prng);
+ }
+
+ @Override
+ public Byte mutate(Byte value, PseudoRandom prng) {
+ return (byte) mutateImpl(value, prng);
+ }
+
+ @Override
+ public Byte crossOver(Byte value, Byte otherValue, PseudoRandom prng) {
+ return (byte) crossOverImpl(value, otherValue, prng);
+ }
+
+ @Override
+ public Byte read(DataInputStream in) throws IOException {
+ return (byte) forceInRange(in.readByte());
+ }
+
+ @Override
+ public void write(Byte value, DataOutputStream out) throws IOException {
+ out.writeByte(value);
+ }
+ });
+ } else if (clazz == short.class || clazz == Short.class) {
+ return Optional.of(
+ new AbstractIntegralMutator<Short>(type, Short.MIN_VALUE, Short.MAX_VALUE) {
+ @Override
+ protected long mutateWithLibFuzzer(long value) {
+ return LibFuzzerMutator.mutateDefault((short) value, this, 0);
+ }
+
+ @Override
+ public Short init(PseudoRandom prng) {
+ return (short) initImpl(prng);
+ }
+
+ @Override
+ public Short mutate(Short value, PseudoRandom prng) {
+ return (short) mutateImpl(value, prng);
+ }
+
+ @Override
+ public Short crossOver(Short value, Short otherValue, PseudoRandom prng) {
+ return (short) crossOverImpl(value, otherValue, prng);
+ }
+
+ @Override
+ public Short read(DataInputStream in) throws IOException {
+ return (short) forceInRange(in.readShort());
+ }
+
+ @Override
+ public void write(Short value, DataOutputStream out) throws IOException {
+ out.writeShort(value);
+ }
+ });
+ } else if (clazz == int.class || clazz == Integer.class) {
+ return Optional.of(
+ new AbstractIntegralMutator<Integer>(type, Integer.MIN_VALUE, Integer.MAX_VALUE) {
+ @Override
+ protected long mutateWithLibFuzzer(long value) {
+ return LibFuzzerMutator.mutateDefault((int) value, this, 0);
+ }
+
+ @Override
+ public Integer init(PseudoRandom prng) {
+ return (int) initImpl(prng);
+ }
+
+ @Override
+ public Integer mutate(Integer value, PseudoRandom prng) {
+ return (int) mutateImpl(value, prng);
+ }
+
+ @Override
+ public Integer crossOver(Integer value, Integer otherValue, PseudoRandom prng) {
+ return (int) crossOverImpl(value, otherValue, prng);
+ }
+
+ @Override
+ public Integer read(DataInputStream in) throws IOException {
+ return (int) forceInRange(in.readInt());
+ }
+
+ @Override
+ public void write(Integer value, DataOutputStream out) throws IOException {
+ out.writeInt(value);
+ }
+ });
+ } else if (clazz == long.class || clazz == Long.class) {
+ return Optional.of(new AbstractIntegralMutator<Long>(type, Long.MIN_VALUE, Long.MAX_VALUE) {
+ @Override
+ protected long mutateWithLibFuzzer(long value) {
+ return LibFuzzerMutator.mutateDefault(value, this, 0);
+ }
+
+ @Override
+ public Long init(PseudoRandom prng) {
+ return initImpl(prng);
+ }
+
+ @Override
+ public Long mutate(Long value, PseudoRandom prng) {
+ return mutateImpl(value, prng);
+ }
+
+ @Override
+ public Long crossOver(Long value, Long otherValue, PseudoRandom prng) {
+ return crossOverImpl(value, otherValue, prng);
+ }
+
+ @Override
+ public Long read(DataInputStream in) throws IOException {
+ return forceInRange(in.readLong());
+ }
+
+ @Override
+ public void write(Long value, DataOutputStream out) throws IOException {
+ out.writeLong(value);
+ }
+ });
+ } else {
+ return Optional.empty();
+ }
+ }
+
+ // Based on
+ // https://github.com/google/fuzztest/blob/a663ded6c36f050fbdc634a8fc81d553068d71d7/fuzztest/internal/domain.h#L1447
+ // SPDX: Apache-2.0
+ // Copyright 2022 Google LLC
+ //
+ // Visible for testing.
+ static abstract class AbstractIntegralMutator<T extends Number> extends SerializingMutator<T> {
+ private static final long RANDOM_WALK_RANGE = 5;
+ private final long minValue;
+ private final long maxValue;
+ private final int largestMutableBitNegative;
+ private final int largestMutableBitPositive;
+ private final long[] specialValues;
+
+ AbstractIntegralMutator(
+ AnnotatedType type, long defaultMinValueForType, long defaultMaxValueForType) {
+ long minValue = defaultMinValueForType;
+ long maxValue = defaultMaxValueForType;
+ // InRange is not repeatable, so the loop body will apply exactly once.
+ for (Annotation annotation : type.getAnnotations()) {
+ if (annotation instanceof InRange) {
+ InRange inRange = (InRange) annotation;
+ // Since we use a single annotation for all integral types and its min and max fields are
+ // longs, we have to ignore them if they are at their default values.
+ //
+ // This results in a small quirk that is probably acceptable: If someone specifies
+ // @InRange(max = Long.MAX_VALUE) on a byte, we will not fail but silently use
+ // Byte.MAX_VALUE instead. IDEs will warn about the redundant specification of the default
+ // value, so this should not be a problem in practice.
+ if (inRange.min() != Long.MIN_VALUE) {
+ require(inRange.min() >= defaultMinValueForType,
+ format("@InRange.min=%d is out of range: %s", inRange.min(), type.getType()));
+ minValue = inRange.min();
+ }
+ if (inRange.max() != Long.MAX_VALUE) {
+ require(inRange.max() <= defaultMaxValueForType,
+ format("@InRange.max=%d is out of range: %s", inRange.max(), type.getType()));
+ maxValue = inRange.max();
+ }
+ }
+ }
+
+ require(minValue <= maxValue,
+ format("[%d, %d] is not a valid interval: %s", minValue, maxValue, type));
+ require(minValue != maxValue,
+ format(
+ "[%d, %d] can not be mutated, use a constant instead: %s", minValue, maxValue, type));
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ if (minValue >= 0) {
+ largestMutableBitNegative = 0;
+ largestMutableBitPositive = bitWidth(minValue ^ maxValue);
+ } else if (maxValue < 0) {
+ largestMutableBitNegative = bitWidth(minValue ^ maxValue);
+ largestMutableBitPositive = 0;
+ } else /* minValue < 0 && maxValue >= 0 */ {
+ largestMutableBitNegative = bitWidth(~minValue);
+ largestMutableBitPositive = bitWidth(maxValue);
+ }
+ this.specialValues = collectSpecialValues(minValue, maxValue);
+ }
+
+ private static long[] collectSpecialValues(long minValue, long maxValue) {
+ // Special values can collide or not apply when @InRange is used, so filter appropriately and
+ // remove duplicates - we don't want to weigh certain special values higher than others.
+ return LongStream.of(0, 1, minValue, maxValue)
+ .filter(value -> value >= minValue)
+ .filter(value -> value <= maxValue)
+ .distinct()
+ .sorted()
+ .toArray();
+ }
+
+ private static int bitWidth(long value) {
+ return 64 - Long.numberOfLeadingZeros(value);
+ }
+
+ protected final long initImpl(PseudoRandom prng) {
+ int sentinel = specialValues.length;
+ int choice = prng.closedRange(0, sentinel);
+ if (choice < sentinel) {
+ return specialValues[choice];
+ } else {
+ return prng.closedRange(minValue, maxValue);
+ }
+ }
+
+ protected final long mutateImpl(long value, PseudoRandom prng) {
+ final long previousValue = value;
+ // Mutate in a loop to verify that we really mutated.
+ do {
+ switch (prng.indexIn(4)) {
+ case 0:
+ value = bitFlip(value, prng);
+ break;
+ case 1:
+ value = randomWalk(value, prng);
+ break;
+ case 2:
+ value = prng.closedRange(minValue, maxValue);
+ break;
+ case 3:
+ // TODO: Replace this with a structure-aware dictionary/TORC search similar to fuzztest.
+ value = forceInRange(mutateWithLibFuzzer(value));
+ break;
+ }
+ } while (value == previousValue);
+ return value;
+ }
+
+ protected final long crossOverImpl(long x, long y, PseudoRandom prng) {
+ switch (prng.indexIn(3)) {
+ case 0:
+ return mean(x, y);
+ case 1:
+ return forceInRange(x ^ y);
+ case 2:
+ return bitmask(x, y, prng);
+ default:
+ throw new AssertionError("Invalid cross over function.");
+ }
+ }
+
+ private long bitmask(long x, long y, PseudoRandom prng) {
+ long mask = prng.nextLong();
+ return forceInRange((x & mask) | (y & ~mask));
+ }
+
+ private static long mean(long x, long y) {
+ // Add the common set bits (x & y) and the half of the sum of the
+ // differing bits together ((x ^ y) >> 1), the result will never exceed
+ // the sum of x and y as both parts of the calculation are guaranteed to
+ // be smaller than or equal to x and y.
+ long xor = x ^ y;
+ long mean = (x & y) + (xor >> 1);
+ // Round towards zero (add 1) if rounding is not exact (last xor bit is
+ // set) and result is negative (sign bit is set).
+ return mean + (1 & xor & (mean >>> 31));
+ }
+
+ @ForOverride protected abstract long mutateWithLibFuzzer(long value);
+
+ /**
+ * Force value into the closed interval [minValue, maxValue] while preserving as many of its
+ * bits as possible (e.g. so that mutations that apply to the raw byte representation still have
+ * a good chance to actually mutate the value). Clamping would not have this property.
+ */
+ protected final long forceInRange(long value) {
+ // Fast path for the common case.
+ if (value >= minValue && value <= maxValue) {
+ return value;
+ }
+ return forceInRange(value, minValue, maxValue);
+ }
+
+ // Visible for testing.
+ static long forceInRange(long value, long minValue, long maxValue) {
+ long range = maxValue - minValue;
+ if (range > 0) {
+ return minValue + Math.abs((value - minValue) % range);
+ } else {
+ // [minValue, maxValue] covers at least half of the [Long.MIN_VALUE, Long.MAX_VALUE] range,
+ // so if value doesn't lie in [minValue, maxValue], it will after shifting once.
+ if (value >= minValue && value <= maxValue) {
+ return value;
+ } else {
+ return value + range;
+ }
+ }
+ }
+
+ private long bitFlip(long value, PseudoRandom prng) {
+ int range = value >= 0 ? largestMutableBitPositive : largestMutableBitNegative;
+ value = value ^ (1L << prng.indexIn(range));
+ // The bit flip may violate the range constraint, if so, mutate randomly.
+ if (value > maxValue || value < minValue) {
+ value = prng.closedRange(minValue, maxValue);
+ }
+ return value;
+ }
+
+ private long randomWalk(long value, PseudoRandom prng) {
+ // Prevent overflows by averaging the individual bounds.
+ if (maxValue / 2 - minValue / 2 <= RANDOM_WALK_RANGE) {
+ value = prng.closedRange(minValue, maxValue);
+ } else {
+ // At this point we know that (using non-wrapping arithmetic):
+ // RANDOM_WALK_RANGE < maxValue/2 - minValue/2 <= Long.MAX_VALUE/2 - minValue/2, hence
+ // minValue/2 + RANDOM_WALK_RANGE < Long.MAX_VALUE/2, hence
+ // minValue + 2*RANDOM_WALK_RANGE < Long.MAX_VALUE.
+ // In particular, minValue + RANDOM_WALK_RANGE can't overflow, likewise for maxValue.
+ long lower = minValue;
+ if (value > lower + RANDOM_WALK_RANGE) {
+ lower = value - RANDOM_WALK_RANGE;
+ }
+ long upper = maxValue;
+ if (value < upper - RANDOM_WALK_RANGE) {
+ upper = value + RANDOM_WALK_RANGE;
+ }
+ value = prng.closedRange(lower, upper);
+ }
+ return value;
+ }
+
+ @Override
+ public T detach(T value) {
+ // Always immutable.
+ return value;
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return ((Class<T>) ((ParameterizedType) this.getClass().getGenericSuperclass())
+ .getActualTypeArguments()[0])
+ .getSimpleName();
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java
new file mode 100644
index 00000000..00ea8b47
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java
@@ -0,0 +1,30 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+
+public final class LangMutators {
+ private LangMutators() {}
+
+ public static MutatorFactory newFactory() {
+ return new ChainedMutatorFactory(new NullableMutatorFactory(), new BooleanMutatorFactory(),
+ new FloatingPointMutatorFactory(), new IntegralMutatorFactory(),
+ new ByteArrayMutatorFactory(), new StringMutatorFactory(), new EnumMutatorFactory());
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java
new file mode 100644
index 00000000..16e6a132
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java
@@ -0,0 +1,126 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.isPrimitive;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull;
+import static java.util.Arrays.stream;
+
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.PseudoRandom;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.util.Optional;
+import java.util.function.Predicate;
+
+final class NullableMutatorFactory extends MutatorFactory {
+ private static boolean isNotNullAnnotation(Annotation annotation) {
+ // There are many NotNull annotations in the wild (including our own) and we want to recognize
+ // them all.
+ return annotation.annotationType().getSimpleName().equals("NotNull");
+ }
+
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ if (isPrimitive(type)
+ || stream(type.getAnnotations()).anyMatch(NullableMutatorFactory::isNotNullAnnotation)) {
+ return Optional.empty();
+ }
+ return factory.tryCreate(notNull(type), factory).map(NullableMutator::new);
+ }
+
+ private static final class NullableMutator<T> extends SerializingMutator<T> {
+ private static final int INVERSE_FREQUENCY_NULL = 100;
+
+ private final SerializingMutator<T> mutator;
+
+ NullableMutator(SerializingMutator<T> mutator) {
+ this.mutator = mutator;
+ }
+
+ @Override
+ public T read(DataInputStream in) throws IOException {
+ if (in.readBoolean()) {
+ return mutator.read(in);
+ } else {
+ return null;
+ }
+ }
+
+ @Override
+ public void write(T value, DataOutputStream out) throws IOException {
+ out.writeBoolean(value != null);
+ if (value != null) {
+ mutator.write(value, out);
+ }
+ }
+
+ @Override
+ public T init(PseudoRandom prng) {
+ if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) {
+ return null;
+ } else {
+ return mutator.init(prng);
+ }
+ }
+
+ @Override
+ public T mutate(T value, PseudoRandom prng) {
+ if (value == null) {
+ return mutator.init(prng);
+ } else if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) {
+ return null;
+ } else {
+ return mutator.mutate(value, prng);
+ }
+ }
+
+ @Override
+ public T crossOver(T value, T otherValue, PseudoRandom prng) {
+ // Prefer to cross over actual values and only return null if
+ // both are null or at INVERSE_FREQUENCY_NULL probability.
+ if (value != null && otherValue != null) {
+ return mutator.crossOver(value, otherValue, prng);
+ } else if (value == null && otherValue == null) {
+ return null;
+ } else if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) {
+ return null;
+ } else {
+ return value != null ? value : otherValue;
+ }
+ }
+
+ @Override
+ public T detach(T value) {
+ if (value == null) {
+ return null;
+ } else {
+ return mutator.detach(value);
+ }
+ }
+
+ @Override
+ public String toDebugString(Predicate<Debuggable> isInCycle) {
+ return "Nullable<" + mutator.toDebugString(isInCycle) + ">";
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java
new file mode 100644
index 00000000..d77cb9d3
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java
@@ -0,0 +1,172 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.lang;
+
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.*;
+
+import com.code_intelligence.jazzer.mutation.annotation.Ascii;
+import com.code_intelligence.jazzer.mutation.annotation.WithUtf8Length;
+import com.code_intelligence.jazzer.mutation.api.Debuggable;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import java.lang.reflect.AnnotatedType;
+import java.nio.charset.StandardCharsets;
+import java.util.Optional;
+import java.util.function.Predicate;
+
+final class StringMutatorFactory extends MutatorFactory {
+ private static final int HEADER_MASK = 0b1100_0000;
+ private static final int BODY_MASK = 0b0011_1111;
+ private static final int CONTINUATION_HEADER = 0b1000_0000;
+
+ private static final int DEFAULT_MIN_BYTES = 0;
+
+ private static final int DEFAULT_MAX_BYTES = 1000;
+
+ static void fixUpAscii(byte[] bytes) {
+ for (int i = 0; i < bytes.length; i++) {
+ bytes[i] &= 0x7F;
+ }
+ }
+
+ // Based on
+ // https://github.com/google/libprotobuf-mutator/blob/af3bb18749db3559dc4968dd85319d05168d4b5e/src/utf8_fix.cc#L32
+ // SPDX: Apache-2.0
+ // Copyright 2022 Google LLC
+ static void fixUpUtf8(byte[] bytes) {
+ for (int pos = 0; pos < bytes.length;) {
+ // Leniently read a UTF-8 code point consisting of any byte viewed as the leading byte and up
+ // to three following bytes that have a continuation byte header.
+ //
+ // Since the upper two bits of a byte are 10 with probability 25%, this roughly results in
+ // the following distribution for characters:
+ //
+ // ASCII code point: 75%
+ // two-byte UTF-8: 18.75%
+ // three-byte UTF-8: ~4.7%
+ // four-byte UTF-8: ~1.2%
+ int scanPos = pos + 1;
+ int maxScanPos = Math.min(pos + 4, bytes.length);
+
+ int codePoint = bytes[pos] & 0xFF;
+ for (; scanPos < maxScanPos; scanPos++) {
+ byte b = bytes[scanPos];
+ if ((b & HEADER_MASK) != CONTINUATION_HEADER) {
+ break;
+ }
+ codePoint = (codePoint << 6) + (b & BODY_MASK);
+ }
+
+ int size = scanPos - pos;
+ int nextPos = scanPos;
+ switch (size) {
+ case 1:
+ // Force code point to be ASCII.
+ codePoint &= 0x7F;
+
+ bytes[pos] = (byte) codePoint;
+ break;
+ case 2:
+ codePoint &= 0x7FF;
+ if (codePoint <= 0x7F) {
+ // The code point encoding must not be longer than necessary, so fix up the code point
+ // to actually require two bytes without fixing too many bits.
+ codePoint |= 0x80;
+ }
+
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[pos] = (byte) (0b1100_0000 | codePoint);
+ break;
+ case 3:
+ codePoint &= 0xFFFF;
+ if (codePoint <= 0x7FF) {
+ // The code point encoding must not be longer than necessary, so fix up the code point
+ // to actually require three bytes without fixing too many bits.
+ codePoint |= 0x800;
+ }
+ if (codePoint >= 0xD800 && codePoint <= 0xDFFF) {
+ // The code point must not be a low or high UTF-16 surrogate pair, which are not allowed
+ // in UTF-8.
+ codePoint |= (codePoint & ~0xF000) | 0xE000;
+ }
+
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[pos] = (byte) (0b1110_0000 | codePoint);
+ break;
+ case 4:
+ codePoint &= 0x1FFFFF;
+ if (codePoint <= 0xFFFF) {
+ // The code point encoding must not be longer than necessary, so fix up the code point
+ // to actually require four bytes without fixing too many bits.
+ codePoint |= 0x100000;
+ }
+ if (codePoint > 0x10FFFF) {
+ // The code point must be in the valid Unicode range, so fix it up by clearing as few
+ // bits as possible.
+ codePoint &= ~0x10FFFF;
+ }
+
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK));
+ codePoint >>= 6;
+ bytes[pos] = (byte) (0b1111_0000 | codePoint);
+ break;
+ default:
+ throw new IllegalStateException("Not reached as scanPos <= pos + 4");
+ }
+
+ pos = nextPos;
+ }
+ }
+
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ Optional<WithUtf8Length> utf8Length =
+ Optional.ofNullable(type.getAnnotation(WithUtf8Length.class));
+ int min = utf8Length.map(WithUtf8Length::min).orElse(DEFAULT_MIN_BYTES);
+ int max = utf8Length.map(WithUtf8Length::max).orElse(DEFAULT_MAX_BYTES);
+
+ AnnotatedType innerByteArray = notNull(withLength(asAnnotatedType(byte[].class), min, max));
+
+ return findFirstParentIfClass(type, String.class)
+ .flatMap(parent -> factory.tryCreate(innerByteArray))
+ .map(byteArrayMutator -> {
+ boolean fixUpAscii = type.getDeclaredAnnotation(Ascii.class) != null;
+ return mutateThenMapToImmutable((SerializingMutator<byte[]>) byteArrayMutator,
+ bytes
+ -> {
+ if (fixUpAscii) {
+ fixUpAscii(bytes);
+ } else {
+ fixUpUtf8(bytes);
+ }
+ return new String(bytes, StandardCharsets.UTF_8);
+ },
+ string
+ -> string.getBytes(StandardCharsets.UTF_8),
+ (Predicate<Debuggable> inCycle) -> "String");
+ });
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel
new file mode 100644
index 00000000..284264bb
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel
@@ -0,0 +1,15 @@
+java_library(
+ name = "libfuzzer",
+ srcs = ["LibFuzzerMutator.java"],
+ visibility = [
+ # libFuzzer's mutators should only by used by mutators for primitive types as we want to get
+ # rid of this dependency eventually.
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang:__pkg__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation/mutator/lang:__subpackages__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ "//src/main/java/com/code_intelligence/jazzer/runtime:mutator",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java
new file mode 100644
index 00000000..c77c75e5
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.libfuzzer;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+
+import com.code_intelligence.jazzer.mutation.api.Serializer;
+import com.code_intelligence.jazzer.runtime.Mutator;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+public final class LibFuzzerMutator {
+ /**
+ * Key name to give to {@link System#setProperty(String, String)} to control the size of the
+ * returned array for {@link #defaultMutateMock(byte[], int)}. Only used for testing purposes.
+ */
+ public static final String MOCK_SIZE_KEY = "libfuzzermutator.mock.newsize";
+
+ public static byte[] mutateDefault(byte[] data, int maxSizeIncrease) {
+ byte[] mutatedBytes;
+ if (maxSizeIncrease == 0) {
+ mutatedBytes = data;
+ } else {
+ mutatedBytes = Arrays.copyOf(data, data.length + maxSizeIncrease);
+ }
+ int newSize = defaultMutate(mutatedBytes, data.length);
+ if (newSize == 0) {
+ // Mutation failed. This should happen very rarely.
+ return data;
+ }
+ return Arrays.copyOf(mutatedBytes, newSize);
+ }
+
+ public static <T> T mutateDefault(T value, Serializer<T> serializer, int maxSizeIncrease) {
+ require(maxSizeIncrease >= 0);
+ ByteArrayOutputStream out = new ByteArrayOutputStream();
+ try {
+ serializer.writeExclusive(value, out);
+ } catch (IOException e) {
+ throw new IllegalStateException(
+ "writeExclusive is not expected to throw if the underlying stream doesn't", e);
+ }
+
+ byte[] mutatedBytes = mutateDefault(out.toByteArray(), maxSizeIncrease);
+
+ try {
+ return serializer.readExclusive(new ByteArrayInputStream(mutatedBytes));
+ } catch (IOException e) {
+ throw new IllegalStateException(
+ "readExclusive is not expected to throw if the underlying stream doesn't", e);
+ }
+ }
+
+ private static int defaultMutate(byte[] buffer, int size) {
+ if (Mutator.SHOULD_MOCK) {
+ return defaultMutateMock(buffer, size);
+ } else {
+ return Mutator.defaultMutateNative(buffer, size);
+ }
+ }
+
+ private static int defaultMutateMock(byte[] buffer, int size) {
+ String newSizeProp = System.getProperty(MOCK_SIZE_KEY);
+ int newSize = Math.min(buffer.length, size + 1);
+ if (newSizeProp != null) {
+ newSize = Integer.parseUnsignedInt(newSizeProp);
+ }
+
+ for (int i = 0; i < newSize; i++) {
+ buffer[i] += i + 1;
+ }
+ return newSize;
+ }
+
+ private LibFuzzerMutator() {}
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel
new file mode 100644
index 00000000..2c591709
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel
@@ -0,0 +1,16 @@
+java_library(
+ name = "proto",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto:__pkg__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto:protobuf_runtime_compile_only",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/api",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/combinator",
+ "//src/main/java/com/code_intelligence/jazzer/mutation/support",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java
new file mode 100644
index 00000000..12dcd406
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java
@@ -0,0 +1,188 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+import static java.util.Collections.singletonList;
+
+import com.google.protobuf.Descriptors.FieldDescriptor;
+import com.google.protobuf.Message;
+import com.google.protobuf.Message.Builder;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+
+final class BuilderAdapters {
+ private BuilderAdapters() {}
+
+ static <T extends Builder, U> List<U> makeMutableRepeatedFieldView(
+ T builder, FieldDescriptor field) {
+ return new AbstractList<U>() {
+ // O(1)
+ @Override
+ public U get(int index) {
+ return (U) builder.getRepeatedField(field, index);
+ }
+
+ // O(1)
+ @Override
+ public int size() {
+ return builder.getRepeatedFieldCount(field);
+ }
+
+ // O(1)
+ @Override
+ public boolean add(U element) {
+ builder.addRepeatedField(field, element);
+ return true;
+ }
+
+ // O(1)
+ @Override
+ public void add(int index, U element) {
+ addAll(index, singletonList(element));
+ }
+
+ // O(size() + other.size())
+ public boolean addAll(int index, Collection<? extends U> other) {
+ // This was benchmarked against the following implementation and found to be faster in all
+ // cases (up to 4x on lists of size 1000):
+ //
+ // for (U element : other) {
+ // builder.addRepeatedField(field, element);
+ // }
+ // Collections.rotate(subList(index, size()), other.size());
+ int otherSize = other.size();
+ if (otherSize == 0) {
+ return false;
+ }
+
+ int originalSize = size();
+ if (index == originalSize) {
+ for (U element : other) {
+ builder.addRepeatedField(field, element);
+ }
+ return true;
+ }
+
+ int newSize = originalSize + otherSize;
+ ArrayList<U> temp = new ArrayList<>(newSize);
+ for (int i = 0; i < index; i++) {
+ temp.add((U) builder.getRepeatedField(field, i));
+ }
+ temp.addAll(other);
+ for (int i = index; i < originalSize; i++) {
+ temp.add((U) builder.getRepeatedField(field, i));
+ }
+
+ replaceWith(temp);
+ return true;
+ }
+
+ // O(1)
+ @Override
+ public U set(int index, U element) {
+ U previous = get(index);
+ builder.setRepeatedField(field, index, element);
+ return previous;
+ }
+
+ // O(size())
+ @Override
+ public U remove(int index) {
+ U removed = get(index);
+ removeRange(index, index + 1);
+ return removed;
+ }
+
+ // O(size() - (toIndex - fromIndex))
+ @Override
+ protected void removeRange(int fromIndex, int toIndex) {
+ int originalSize = size();
+ int newSize = originalSize - (toIndex - fromIndex);
+ if (newSize == 0) {
+ builder.clearField(field);
+ return;
+ }
+
+ // There is no way to remove individual repeated field entries without clearing the entire
+ // field, so we have to iterate over all entries and keep them in a temporary list.
+ ArrayList<U> temp = new ArrayList<>(newSize);
+ for (int i = 0; i < fromIndex; i++) {
+ temp.add((U) builder.getRepeatedField(field, i));
+ }
+ for (int i = toIndex; i < originalSize; i++) {
+ temp.add((U) builder.getRepeatedField(field, i));
+ }
+
+ replaceWith(temp);
+ }
+
+ private void replaceWith(ArrayList<U> temp) {
+ builder.clearField(field);
+ for (U element : temp) {
+ builder.addRepeatedField(field, element);
+ }
+ }
+ };
+ }
+
+ static <T extends Builder, U> U getPresentFieldOrNull(T builder, FieldDescriptor field) {
+ if (builder.hasField(field)) {
+ return (U) builder.getField(field);
+ } else {
+ return null;
+ }
+ }
+
+ static <T extends Builder, U> void setFieldWithPresence(
+ T builder, FieldDescriptor field, U value) {
+ if (value == null) {
+ builder.clearField(field);
+ } else {
+ builder.setField(field, value);
+ }
+ }
+
+ static <T extends Builder, K, V> Map<K, V> getMapField(T builder, FieldDescriptor field) {
+ int size = builder.getRepeatedFieldCount(field);
+ FieldDescriptor keyField = field.getMessageType().getFields().get(0);
+ FieldDescriptor valueField = field.getMessageType().getFields().get(1);
+ HashMap<K, V> map = new HashMap<>(size);
+ for (int i = 0; i < size; i++) {
+ Message entry = (Message) builder.getRepeatedField(field, i);
+ map.put((K) entry.getField(keyField), (V) entry.getField(valueField));
+ }
+ return map;
+ }
+
+ static <T extends Builder, K, V> void setMapField(
+ Builder builder, FieldDescriptor field, Map<K, V> map) {
+ builder.clearField(field);
+ FieldDescriptor keyField = field.getMessageType().getFields().get(0);
+ FieldDescriptor valueField = field.getMessageType().getFields().get(1);
+ Builder entryBuilder = builder.newBuilderForField(field);
+ for (Entry<K, V> entry : map.entrySet()) {
+ entryBuilder.setField(keyField, entry.getKey());
+ entryBuilder.setField(valueField, entry.getValue());
+ builder.addRepeatedField(field, entryBuilder.build());
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java
new file mode 100644
index 00000000..85427c6f
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java
@@ -0,0 +1,451 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+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.fixedValue;
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateIndices;
+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.mutator.proto.BuilderAdapters.getMapField;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.getPresentFieldOrNull;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.makeMutableRepeatedFieldView;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.setFieldWithPresence;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.setMapField;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.TypeLibrary.getDefaultInstance;
+import static com.code_intelligence.jazzer.mutation.mutator.proto.TypeLibrary.withoutInitIfRecursive;
+import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.cap;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withExtraAnnotations;
+import static java.util.Arrays.stream;
+import static java.util.Objects.requireNonNull;
+import static java.util.function.UnaryOperator.identity;
+import static java.util.stream.Collectors.groupingBy;
+import static java.util.stream.Collectors.toList;
+import static java.util.stream.Collectors.toMap;
+
+import com.code_intelligence.jazzer.mutation.annotation.proto.AnySource;
+import com.code_intelligence.jazzer.mutation.annotation.proto.WithDefaultInstance;
+import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.InPlaceMutator;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+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.Preconditions;
+import com.google.protobuf.Any;
+import com.google.protobuf.Descriptors.Descriptor;
+import com.google.protobuf.Descriptors.EnumDescriptor;
+import com.google.protobuf.Descriptors.EnumValueDescriptor;
+import com.google.protobuf.Descriptors.FieldDescriptor;
+import com.google.protobuf.Descriptors.FieldDescriptor.JavaType;
+import com.google.protobuf.Descriptors.OneofDescriptor;
+import com.google.protobuf.DynamicMessage;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.protobuf.Message;
+import com.google.protobuf.Message.Builder;
+import com.google.protobuf.UnknownFieldSet;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.util.HashMap;
+import java.util.IdentityHashMap;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
+
+public final class BuilderMutatorFactory extends MutatorFactory {
+ private <T extends Builder, U> InPlaceMutator<T> mutatorForField(
+ FieldDescriptor field, Annotation[] annotations, MutatorFactory factory) {
+ factory = withDescriptorDependentMutatorFactoryIfNeeded(factory, field, annotations);
+ AnnotatedType typeToMutate = TypeLibrary.getTypeToMutate(field);
+ requireNonNull(typeToMutate, () -> "Java class not specified for " + field);
+
+ InPlaceMutator<T> mutator;
+ if (field.isMapField()) {
+ SerializingInPlaceMutator<Map> underlyingMutator =
+ (SerializingInPlaceMutator<Map>) factory.createInPlaceOrThrow(typeToMutate);
+ mutator = mutateProperty(builder
+ -> getMapField(builder, field),
+ underlyingMutator, (builder, value) -> setMapField(builder, field, value));
+ } else if (field.isRepeated()) {
+ SerializingInPlaceMutator<List<U>> underlyingMutator =
+ (SerializingInPlaceMutator<List<U>>) factory.createInPlaceOrThrow(typeToMutate);
+ mutator =
+ mutateViaView(builder -> makeMutableRepeatedFieldView(builder, field), underlyingMutator);
+ } else if (field.hasPresence()) {
+ SerializingMutator<U> underlyingMutator =
+ (SerializingMutator<U>) factory.createOrThrow(typeToMutate);
+ mutator = mutateProperty(builder
+ -> getPresentFieldOrNull(builder, field),
+ underlyingMutator, (builder, value) -> setFieldWithPresence(builder, field, value));
+ } else {
+ SerializingMutator<U> underlyingMutator =
+ (SerializingMutator<U>) factory.createOrThrow(typeToMutate);
+ mutator = mutateProperty(builder
+ -> (U) builder.getField(field),
+ underlyingMutator, (builder, value) -> builder.setField(field, value));
+ }
+
+ // If recursive message fields (i.e. those that have themselves as transitive subfields) are
+ // initialized eagerly, they tend to nest very deeply, which easily results in stack overflows.
+ // We guard against that by making their init a no-op and instead initialize them layer by layer
+ // in mutations.
+ return withoutInitIfRecursive(mutator, field);
+ }
+
+ private MutatorFactory withDescriptorDependentMutatorFactoryIfNeeded(
+ MutatorFactory originalFactory, FieldDescriptor field, Annotation[] annotations) {
+ if (field.getJavaType() == JavaType.ENUM) {
+ // Proto enum fields are special as their type (EnumValueDescriptor) does not encode their
+ // domain - we need the actual EnumDescriptor instance.
+ return new ChainedMutatorFactory(originalFactory, new MutatorFactory() {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(
+ AnnotatedType type, MutatorFactory factory) {
+ return findFirstParentIfClass(type, EnumValueDescriptor.class).map(parent -> {
+ EnumDescriptor enumType = field.getEnumType();
+ List<EnumValueDescriptor> values = enumType.getValues();
+ String name = enumType.getName();
+ if (values.size() == 1) {
+ // While we generally prefer to error out instead of creating a mutator that can't
+ // actually mutate its domain, we can't do that for proto enum fields as the user
+ // creating the fuzz test may not be in a position to modify the existing proto
+ // definition.
+ return fixedValue(values.get(0));
+ } else {
+ return mutateThenMapToImmutable(mutateIndices(values.size()), values::get,
+ EnumValueDescriptor::getIndex, unused -> "Enum<" + name + ">");
+ }
+ });
+ }
+ });
+ } else if (field.getJavaType() == JavaType.MESSAGE) {
+ Descriptor messageDescriptor;
+ if (field.isMapField()) {
+ // Map fields are represented as messages, but we mutate them as actual Java Maps. In case
+ // the values of the proto map are themselves messages, we need to mutate their type.
+ FieldDescriptor valueField = field.getMessageType().getFields().get(1);
+ if (valueField.getJavaType() != JavaType.MESSAGE) {
+ return originalFactory;
+ }
+ messageDescriptor = valueField.getMessageType();
+ } else {
+ messageDescriptor = field.getMessageType();
+ }
+ return new ChainedMutatorFactory(originalFactory, new MutatorFactory() {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(
+ AnnotatedType type, MutatorFactory factory) {
+ return asSubclassOrEmpty(type, Message.Builder.class).flatMap(clazz -> {
+ // BuilderMutatorFactory only handles subclasses of Message.Builder and requests
+ // Message.Builder itself for message fields, which we handle here.
+ if (clazz != Message.Builder.class) {
+ return Optional.empty();
+ }
+ // It is important that we use originalFactory here instead of factory: factory has this
+ // field-specific message mutator appended, but this mutator should only be used for
+ // this particular field and not any message subfields.
+ return Optional.of(makeBuilderMutator(originalFactory,
+ DynamicMessage.getDefaultInstance(messageDescriptor), annotations));
+ });
+ }
+ });
+ } else {
+ return originalFactory;
+ }
+ }
+
+ private <T extends Builder> Stream<InPlaceMutator<T>> mutatorsForFields(
+ Optional<OneofDescriptor> oneofField, List<FieldDescriptor> fields, Annotation[] annotations,
+ MutatorFactory factory) {
+ if (oneofField.isPresent()) {
+ // oneof fields are mutated as one as mutating them independently would cause the mutator to
+ // erratically switch between the different states. The individual fields are kept in the
+ // order in which they are defined in the .proto file.
+ OneofDescriptor oneofDescriptor = oneofField.get();
+
+ IdentityHashMap<FieldDescriptor, Integer> indexInOneof =
+ new IdentityHashMap<>(oneofDescriptor.getFieldCount());
+ for (int i = 0; i < oneofDescriptor.getFieldCount(); i++) {
+ indexInOneof.put(oneofDescriptor.getField(i), i);
+ }
+
+ return Stream.of(mutateSumInPlace(
+ (T builder)
+ -> {
+ FieldDescriptor setField = builder.getOneofFieldDescriptor(oneofDescriptor);
+ if (setField == null) {
+ return -1;
+ } else {
+ return indexInOneof.get(setField);
+ }
+ },
+ // Mutating to the unset (-1) state is handled by the individual field mutators, which
+ // are created nullable as oneof fields report that they track presence.
+ fields.stream()
+ .map(field -> mutatorForField(field, annotations, factory))
+ .toArray(InPlaceMutator[] ::new)));
+ } else {
+ // All non-oneof fields are mutated independently, using the order in which they are declared
+ // in the .proto file (which may not coincide with the order by field number).
+ return fields.stream().map(field -> mutatorForField(field, annotations, factory));
+ }
+ }
+
+ private static <M extends Message, B extends Builder> Serializer<B> makeBuilderSerializer(
+ M defaultInstance) {
+ return new Serializer<B>() {
+ @Override
+ public B read(DataInputStream in) throws IOException {
+ int length = Math.max(in.readInt(), 0);
+ return (B) parseLeniently(cap(in, length));
+ }
+
+ @Override
+ public B readExclusive(InputStream in) throws IOException {
+ return (B) parseLeniently(in);
+ }
+
+ private Builder parseLeniently(InputStream in) throws IOException {
+ Builder builder = defaultInstance.toBuilder();
+ try {
+ builder.mergeFrom(in);
+ } catch (InvalidProtocolBufferException ignored) {
+ // builder has been partially modified with what could be decoded before the parser error.
+ }
+ // We never want the fuzz test to see unknown fields and our mutations should never produce
+ // them.
+ builder.setUnknownFields(UnknownFieldSet.getDefaultInstance());
+ // Required fields may not have been set at this point. We set them to default values to
+ // prevent an exception when built.
+ forceInitialized(builder);
+ return builder;
+ }
+
+ private void forceInitialized(Builder builder) {
+ if (builder.isInitialized()) {
+ return;
+ }
+ for (FieldDescriptor field : builder.getDescriptorForType().getFields()) {
+ if (!field.isRequired()) {
+ continue;
+ }
+ if (field.getJavaType() == JavaType.MESSAGE) {
+ forceInitialized(builder.getFieldBuilder(field));
+ } else if (!builder.hasField(field)) {
+ builder.setField(field, field.getDefaultValue());
+ }
+ }
+ }
+
+ @Override
+ public void write(Builder builder, DataOutputStream out) throws IOException {
+ Message message = builder.build();
+ out.writeInt(message.getSerializedSize());
+ message.writeTo(out);
+ }
+
+ @Override
+ public void writeExclusive(Builder builder, OutputStream out) throws IOException {
+ builder.build().writeTo(out);
+ }
+
+ @Override
+ public B detach(Builder builder) {
+ return (B) builder.build().toBuilder();
+ }
+ };
+ }
+
+ /*
+ * Ensures that only a single instance is created per builder class and shared among all mutators
+ * that need it. This ensures that arbitrarily nested recursive structures such as a Protobuf
+ * message type that contains itself as a message field are representable as fixed-size mutator
+ * structures.
+ *
+ * Note: The resulting mutator structures may no longer form a tree: If A is a protobuf message
+ * type with a message field B and B in turn has a message field of type A, then the mutators for
+ * A and B will reference each other, forming a cycle.
+ */
+ private final HashMap<CacheKey, SerializingMutator<? extends Builder>> internedMutators =
+ new HashMap<>();
+
+ private SerializingMutator<Any.Builder> mutatorForAny(
+ AnySource anySource, MutatorFactory factory) {
+ Map<String, Integer> typeUrlToIndex =
+ IntStream.range(0, anySource.value().length)
+ .boxed()
+ .collect(toMap(i -> getTypeUrl(getDefaultInstance(anySource.value()[i])), identity()));
+
+ return assemble(mutator
+ -> internedMutators.put(new CacheKey(Any.getDescriptor(), anySource), mutator),
+ Any.getDefaultInstance()::toBuilder, makeBuilderSerializer(Any.getDefaultInstance()),
+ ()
+ -> mutateSumInPlace(
+ // Corpus entries may contain Anys with arbitrary (and even invalid) messages, so we
+ // fall back to mutating the first message type if the type isn't recognized.
+ (Any.Builder builder)
+ -> typeUrlToIndex.getOrDefault(builder.getTypeUrl(), 0),
+ stream(anySource.value())
+ .map(messageClass -> {
+ SerializingMutator<Message> messageMutator =
+ (SerializingMutator<Message>) factory.createOrThrow(notNull(
+ withExtraAnnotations(asAnnotatedType(messageClass), anySource)));
+ return mutateProperty(
+ (Any.Builder anyBuilder)
+ -> {
+ try {
+ return anyBuilder.build().unpack(messageClass);
+ } catch (InvalidProtocolBufferException e) {
+ // This can only happen if the corpus contains an invalid Any.
+ return getDefaultInstance(messageClass);
+ }
+ },
+ messageMutator,
+ (Any.Builder any, Message message) -> {
+ any.setTypeUrl(getTypeUrl(message));
+ any.setValue(message.toByteString());
+ });
+ })
+ .toArray(InPlaceMutator[] ::new)));
+ }
+
+ private static String getTypeUrl(Message message) {
+ // We only support the default "type.googleapis.com" prefix.
+ // https://github.com/protocolbuffers/protobuf/blob/main/src/google/protobuf/any.proto#L94
+ return "type.googleapis.com/" + message.getDescriptorForType().getFullName();
+ }
+
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ return asSubclassOrEmpty(type, Builder.class).flatMap(builderClass -> {
+ Message defaultInstance;
+ WithDefaultInstance withDefaultInstance = type.getAnnotation(WithDefaultInstance.class);
+ if (withDefaultInstance != null) {
+ defaultInstance = getDefaultInstance(withDefaultInstance);
+ } else if (builderClass == DynamicMessage.Builder.class) {
+ throw new IllegalArgumentException(
+ "To mutate a dynamic message, add a @WithDefaultInstance annotation specifying the"
+ + " fully qualified method name of a static method returning a default instance");
+ } else if (builderClass == Message.Builder.class) {
+ // Handled by a custom mutator factory for message fields that is created in
+ // withDescriptorDependentMutatorFactoryIfNeeded. Without @WithDefaultInstance,
+ // BuilderMutatorFactory only handles proper subclasses, which correspond to generated
+ // message types.
+ return Optional.empty();
+ } else {
+ defaultInstance =
+ getDefaultInstance((Class<? extends Message>) builderClass.getEnclosingClass());
+ }
+
+ return Optional.of(
+ makeBuilderMutator(factory, defaultInstance, type.getDeclaredAnnotations()));
+ });
+ }
+
+ private SerializingMutator<?> makeBuilderMutator(
+ MutatorFactory factory, Message defaultInstance, Annotation[] annotations) {
+ AnySource anySource = (AnySource) stream(annotations)
+ .filter(annotation -> annotation.annotationType() == AnySource.class)
+ .findFirst()
+ .orElse(null);
+ Preconditions.require(anySource == null || anySource.value().length > 0,
+ "@AnySource must list a non-empty list of classes");
+ Descriptor descriptor = defaultInstance.getDescriptorForType();
+
+ CacheKey cacheKey = new CacheKey(descriptor, anySource);
+ if (internedMutators.containsKey(cacheKey)) {
+ return internedMutators.get(cacheKey);
+ }
+
+ // If there is no @AnySource, mutate the Any.Builder fields just like a regular message.
+ // TODO: Determine whether we should show a warning in this case.
+ if (descriptor.equals(Any.getDescriptor()) && anySource != null) {
+ return mutatorForAny(anySource, factory);
+ }
+
+ // assemble inserts the instance of the newly created builder mutator into the
+ // internedMutators map *before* recursively creating the mutators for its fields, which
+ // ensures that the recursion is finite (bounded by the total number of distinct message types
+ // that transitively occur as field types on the current message type).
+ return assemble(mutator
+ -> internedMutators.put(cacheKey, mutator),
+ defaultInstance::toBuilder, makeBuilderSerializer(defaultInstance),
+ ()
+ -> combine(
+ descriptor.getFields()
+ .stream()
+ // Keep oneofs sorted by the first appearance of their fields in the
+ // .proto file.
+ .collect(groupingBy(
+ // groupingBy does not support null keys. We use getRealContainingOneof()
+ // instead of getContainingOneof() as the latter also reports oneofs for
+ // proto3 optional fields, which we handle separately.
+ fieldDescriptor
+ -> Optional.ofNullable(fieldDescriptor.getRealContainingOneof()),
+ LinkedHashMap::new, toList()))
+ .entrySet()
+ .stream()
+ .flatMap(entry
+ -> mutatorsForFields(entry.getKey(), entry.getValue(),
+ anySource == null ? new Annotation[0] : new Annotation[] {anySource},
+ factory))
+ .toArray(InPlaceMutator[] ::new)));
+ }
+
+ private static final class CacheKey {
+ private final Descriptor descriptor;
+ private final AnySource anySource;
+
+ private CacheKey(Descriptor descriptor, AnySource anySource) {
+ this.descriptor = descriptor;
+ this.anySource = anySource;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ CacheKey cacheKey = (CacheKey) o;
+ return descriptor == cacheKey.descriptor && Objects.equals(anySource, cacheKey.anySource);
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 * System.identityHashCode(descriptor) + Objects.hashCode(anySource);
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java
new file mode 100644
index 00000000..a01ffae6
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java
@@ -0,0 +1,41 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull;
+
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.google.protobuf.ByteString;
+import java.lang.reflect.AnnotatedType;
+import java.util.Optional;
+
+final class ByteStringMutatorFactory extends MutatorFactory {
+ ByteStringMutatorFactory() {}
+
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) {
+ return findFirstParentIfClass(type, ByteString.class)
+ .flatMap(parent -> factory.tryCreate(notNull(asAnnotatedType(byte[].class))))
+ .map(byteArrayMutator
+ -> mutateThenMapToImmutable((SerializingMutator<byte[]>) byteArrayMutator,
+ ByteString::copyFrom, ByteString::toByteArray));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java
new file mode 100644
index 00000000..eb3220f5
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java
@@ -0,0 +1,52 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withExtraAnnotations;
+
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.SerializingMutator;
+import com.google.protobuf.Message;
+import com.google.protobuf.Message.Builder;
+import java.lang.reflect.AnnotatedType;
+import java.util.Arrays;
+import java.util.Optional;
+
+public final class MessageMutatorFactory extends MutatorFactory {
+ @Override
+ public Optional<SerializingMutator<?>> tryCreate(
+ AnnotatedType messageType, MutatorFactory factory) {
+ return asSubclassOrEmpty(messageType, Message.class)
+ // If the Message class doesn't have a nested Builder class, it is not a concrete generated
+ // message and we can't mutate it.
+ .flatMap(messageClass
+ -> Arrays.stream(messageClass.getDeclaredClasses())
+ .filter(clazz -> clazz.getSimpleName().equals("Builder"))
+ .findFirst())
+ .flatMap(builderClass
+ ->
+ // Forward the annotations (e.g. @NotNull) on the Message type to the Builder type.
+ factory.tryCreateInPlace(
+ withExtraAnnotations(asAnnotatedType(builderClass), messageType.getAnnotations())))
+ .map(builderMutator
+ -> mutateThenMapToImmutable(
+ (SerializingMutator<Builder>) builderMutator, Builder::build, Message::toBuilder));
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java
new file mode 100644
index 00000000..acb25cd7
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory;
+import com.code_intelligence.jazzer.mutation.api.MutatorFactory;
+
+public final class ProtoMutators {
+ private ProtoMutators() {}
+
+ public static MutatorFactory newFactory() {
+ try {
+ Class.forName("com.google.protobuf.Message");
+ return new ChainedMutatorFactory(
+ new ByteStringMutatorFactory(), new MessageMutatorFactory(), new BuilderMutatorFactory());
+ } catch (ClassNotFoundException e) {
+ return new ChainedMutatorFactory();
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java
new file mode 100644
index 00000000..43338f14
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java
@@ -0,0 +1,179 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.mutator.proto;
+
+import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.withoutInit;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.check;
+import static com.code_intelligence.jazzer.mutation.support.StreamSupport.entry;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.containedInDirectedCycle;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull;
+import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withTypeArguments;
+import static java.lang.String.format;
+import static java.util.Collections.unmodifiableMap;
+import static java.util.stream.Collectors.collectingAndThen;
+import static java.util.stream.Collectors.toMap;
+
+import com.code_intelligence.jazzer.mutation.annotation.NotNull;
+import com.code_intelligence.jazzer.mutation.annotation.proto.WithDefaultInstance;
+import com.code_intelligence.jazzer.mutation.api.InPlaceMutator;
+import com.code_intelligence.jazzer.mutation.support.TypeHolder;
+import com.google.protobuf.ByteString;
+import com.google.protobuf.Descriptors.Descriptor;
+import com.google.protobuf.Descriptors.EnumValueDescriptor;
+import com.google.protobuf.Descriptors.FieldDescriptor;
+import com.google.protobuf.Descriptors.FieldDescriptor.JavaType;
+import com.google.protobuf.DynamicMessage;
+import com.google.protobuf.Message;
+import com.google.protobuf.Message.Builder;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.Field;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.lang.reflect.Modifier;
+import java.util.EnumMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.stream.Stream;
+
+final class TypeLibrary {
+ private static final AnnotatedType RAW_LIST = new TypeHolder<@NotNull List>() {}.annotatedType();
+ private static final AnnotatedType RAW_MAP = new TypeHolder<@NotNull Map>() {}.annotatedType();
+ private static final Map<JavaType, AnnotatedType> BASE_TYPE_WITH_PRESENCE =
+ Stream
+ .of(entry(JavaType.BOOLEAN, Boolean.class), entry(JavaType.BYTE_STRING, ByteString.class),
+ entry(JavaType.DOUBLE, Double.class), entry(JavaType.ENUM, EnumValueDescriptor.class),
+ entry(JavaType.FLOAT, Float.class), entry(JavaType.INT, Integer.class),
+ entry(JavaType.LONG, Long.class), entry(JavaType.MESSAGE, Message.class),
+ entry(JavaType.STRING, String.class))
+ .collect(collectingAndThen(toMap(Entry::getKey, e -> asAnnotatedType(e.getValue())),
+ map -> unmodifiableMap(new EnumMap<>(map))));
+
+ private TypeLibrary() {}
+
+ static <T extends Builder> AnnotatedType getTypeToMutate(FieldDescriptor field) {
+ if (field.isRequired()) {
+ return getBaseType(field);
+ } else if (field.isMapField()) {
+ // Map fields are represented as repeated message fields, so this check has to come before the
+ // one for regular repeated fields.
+ AnnotatedType keyType = getBaseType(field.getMessageType().getFields().get(0));
+ AnnotatedType valueType = getBaseType(field.getMessageType().getFields().get(1));
+ return withTypeArguments(RAW_MAP, keyType, valueType);
+ } else if (field.isRepeated()) {
+ return withTypeArguments(RAW_LIST, getBaseType(field));
+ } else if (field.hasPresence()) {
+ return BASE_TYPE_WITH_PRESENCE.get(field.getJavaType());
+ } else {
+ return getBaseType(field);
+ }
+ }
+
+ private static <T extends Builder> AnnotatedType getBaseType(FieldDescriptor field) {
+ return notNull(BASE_TYPE_WITH_PRESENCE.get(field.getJavaType()));
+ }
+
+ static <T> InPlaceMutator<T> withoutInitIfRecursive(
+ InPlaceMutator<T> mutator, FieldDescriptor field) {
+ if (field.isRequired() || !isRecursiveField(field)) {
+ return mutator;
+ }
+ return withoutInit(mutator);
+ }
+
+ private static boolean isRecursiveField(FieldDescriptor field) {
+ return containedInDirectedCycle(field, f -> {
+ // For map fields, only the value can be a message.
+ FieldDescriptor realField = f.isMapField() ? f.getMessageType().getFields().get(1) : f;
+ if (realField.getJavaType() != JavaType.MESSAGE) {
+ return Stream.empty();
+ }
+ return realField.getMessageType().getFields().stream();
+ });
+ }
+
+ static Message getDefaultInstance(Class<? extends Message> messageClass) {
+ Method getDefaultInstance;
+ try {
+ getDefaultInstance = messageClass.getMethod("getDefaultInstance");
+ check(Modifier.isStatic(getDefaultInstance.getModifiers()));
+ } catch (NoSuchMethodException e) {
+ throw new IllegalStateException(
+ format("Message class for builder type %s does not have a getDefaultInstance method",
+ messageClass.getName()),
+ e);
+ }
+ try {
+ return (Message) getDefaultInstance.invoke(null);
+ } catch (IllegalAccessException | InvocationTargetException e) {
+ throw new IllegalStateException(
+ format(getDefaultInstance + " isn't accessible or threw an exception"), e);
+ }
+ }
+
+ static Message getDefaultInstance(WithDefaultInstance withDefaultInstance) {
+ String[] parts = withDefaultInstance.value().split("#");
+ if (parts.length != 2) {
+ throw new IllegalArgumentException(
+ format("Expected @WithDefaultInstance(\"%s\") to specify a fully-qualified method name"
+ + " (e.g. com.example.MyClass#getDefaultInstance)",
+ withDefaultInstance.value()));
+ }
+
+ Class<?> clazz;
+ try {
+ clazz = Class.forName(parts[0]);
+ } catch (ClassNotFoundException e) {
+ throw new IllegalArgumentException(
+ format("Failed to find class '%s' specified by @WithDefaultInstance(\"%s\")", parts[0],
+ withDefaultInstance.value()),
+ e);
+ }
+
+ Method method;
+ try {
+ method = clazz.getDeclaredMethod(parts[1]);
+ method.setAccessible(true);
+ } catch (NoSuchMethodException e) {
+ throw new IllegalArgumentException(
+ format("Failed to find method specified by @WithDefaultInstance(\"%s\")",
+ withDefaultInstance.value()),
+ e);
+ }
+ if (!Modifier.isStatic(method.getModifiers())) {
+ throw new IllegalArgumentException(
+ format("Expected method specified by @WithDefaultInstance(\"%s\") to be static",
+ withDefaultInstance.value()));
+ }
+ if (!Message.class.isAssignableFrom(method.getReturnType())) {
+ throw new IllegalArgumentException(format(
+ "Expected return type of method specified by @WithDefaultInstance(\"%s\") to be a"
+ + " subtype of %s, got %s",
+ withDefaultInstance.value(), Message.class.getName(), method.getReturnType().getName()));
+ }
+
+ try {
+ return (Message) method.invoke(null);
+ } catch (IllegalAccessException | InvocationTargetException e) {
+ throw new IllegalArgumentException(
+ format("Failed to execute method specified by @WithDefaultInstance(\"%s\")",
+ withDefaultInstance.value()),
+ e);
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel
new file mode 100644
index 00000000..5765ceed
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel
@@ -0,0 +1,11 @@
+java_library(
+ name = "support",
+ srcs = glob(["*.java"]),
+ visibility = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation:__subpackages__",
+ "//src/test/java/com/code_intelligence/jazzer/mutation:__subpackages__",
+ ],
+ deps = [
+ "//src/main/java/com/code_intelligence/jazzer/mutation/annotation",
+ ],
+)
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java
new file mode 100644
index 00000000..bd5f434b
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java
@@ -0,0 +1,31 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+public final class ExceptionSupport {
+ /**
+ * Allows throwing any {@link Throwable} unchanged as if it were an unchecked exception.
+ *
+ * <p>Example: {@code throw asUnchecked(new IOException())}
+ */
+ @SuppressWarnings("unchecked")
+ public static <T extends Throwable> T asUnchecked(Throwable t) throws T {
+ throw(T) t;
+ }
+
+ private ExceptionSupport() {}
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java
new file mode 100644
index 00000000..c643fea2
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java
@@ -0,0 +1,256 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static java.lang.Math.max;
+import static java.lang.Math.min;
+import static java.util.Objects.requireNonNull;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Queue;
+
+public final class InputStreamSupport {
+ public static byte[] readAllBytes(InputStream stream) throws IOException {
+ requireNonNull(stream);
+ Queue<byte[]> buffers = new ArrayDeque<>();
+ int arrayLength = 0;
+ outer:
+ while (true) {
+ byte[] buffer = new byte[max(8192, stream.available())];
+ buffers.add(buffer);
+ int off = 0;
+ while (off < buffer.length) {
+ int bytesRead = stream.read(buffer, off, buffer.length - off);
+ if (bytesRead == -1) {
+ break outer;
+ }
+ off += bytesRead;
+ arrayLength += bytesRead;
+ }
+ }
+
+ byte[] result = new byte[arrayLength];
+ int offset = 0;
+ byte[] buffer;
+ int remaining = arrayLength;
+ while ((buffer = buffers.poll()) != null) {
+ int toCopy = min(buffer.length, remaining);
+ System.arraycopy(buffer, 0, result, offset, toCopy);
+ remaining -= toCopy;
+ }
+ return result;
+ }
+
+ private static final InputStream infiniteZerosStream = new ExtendWithNullInputStream();
+
+ /**
+ * @return an infinite stream consisting of 0s
+ */
+ public static InputStream infiniteZeros() {
+ return infiniteZerosStream;
+ }
+
+ /**
+ * @return {@code stream} extended with 0s to an infinite stream
+ */
+ public static InputStream extendWithZeros(InputStream stream) {
+ if (stream instanceof ExtendWithNullInputStream) {
+ return stream;
+ }
+ return new ExtendWithNullInputStream(requireNonNull(stream));
+ }
+
+ public static final class ExtendWithNullInputStream extends InputStream {
+ private static final InputStream ALWAYS_EOF = new ByteArrayInputStream(new byte[0]);
+ private final InputStream stream;
+ private boolean eof;
+
+ private ExtendWithNullInputStream() {
+ this.stream = ALWAYS_EOF;
+ this.eof = true;
+ }
+
+ private ExtendWithNullInputStream(InputStream stream) {
+ this.stream = stream;
+ this.eof = false;
+ }
+
+ @Override
+ public int read() throws IOException {
+ if (eof) {
+ return 0;
+ }
+
+ int res = stream.read();
+ if (res != -1) {
+ return res;
+ } else {
+ eof = true;
+ return 0;
+ }
+ }
+
+ @Override
+ public int read(byte[] b, int off, int len) throws IOException {
+ if (eof) {
+ Arrays.fill(b, off, off + len, (byte) 0);
+ } else {
+ int bytesRead = stream.read(b, off, len);
+ if (bytesRead < len) {
+ eof = true;
+ Arrays.fill(b, max(off, off + bytesRead), off + len, (byte) 0);
+ }
+ }
+ return len;
+ }
+
+ @Override
+ public int available() throws IOException {
+ if (eof) {
+ return Integer.MAX_VALUE;
+ } else {
+ return stream.available();
+ }
+ }
+
+ @Override
+ public void close() throws IOException {
+ stream.close();
+ }
+ }
+
+ /**
+ * @return a stream with the first {@code bytes} bytes of {@code stream}
+ */
+ public static InputStream cap(InputStream stream, long bytes) {
+ requireNonNull(stream);
+ require(bytes >= 0, "bytes must be non-negative");
+ return new CappedInputStream(stream, bytes);
+ }
+
+ private static final class CappedInputStream extends InputStream {
+ private final InputStream stream;
+ private long remaining;
+
+ CappedInputStream(InputStream stream, long remaining) {
+ this.stream = stream;
+ this.remaining = remaining;
+ }
+
+ @Override
+ public int read() throws IOException {
+ if (remaining == 0) {
+ return -1;
+ }
+
+ int res = stream.read();
+ if (res != -1) {
+ --remaining;
+ }
+ return res;
+ }
+
+ @Override
+ public int read(byte[] b, int off, int len) throws IOException {
+ if (remaining == 0) {
+ return -1;
+ }
+
+ int res = stream.read(b, off, (int) min(len, remaining));
+ if (res != -1) {
+ remaining -= res;
+ }
+ return res;
+ }
+
+ @Override
+ public int available() throws IOException {
+ return (int) min(stream.available(), remaining);
+ }
+
+ @Override
+ public void close() throws IOException {
+ stream.close();
+ }
+ }
+
+ /**
+ * Wraps a given stream with the functionality to detect if it was read exactly.
+ * To do so, the stream must provide an accurate implementation of {@link
+ * InputStream#available()}, hence it's restricted to {@link ByteArrayInputStream} for now.
+ *
+ * @return {@code stream} extended that detects if it was consumed exactly
+ */
+ public static ReadExactlyInputStream extendWithReadExactly(ByteArrayInputStream stream) {
+ return new ReadExactlyInputStream(requireNonNull(stream));
+ }
+
+ public static final class ReadExactlyInputStream extends InputStream {
+ private final InputStream stream;
+ private boolean eof;
+
+ private ReadExactlyInputStream(InputStream stream) {
+ this.stream = stream;
+ this.eof = false;
+ }
+
+ public boolean isConsumedExactly() {
+ try {
+ // Forwards availability check to the underlying ByteInputStream,
+ // which is accurate for the number of available bytes.
+ return !eof && available() == 0;
+ } catch (IOException e) {
+ return false;
+ }
+ }
+
+ @Override
+ public int read() throws IOException {
+ int res = stream.read();
+ if (res == -1) {
+ eof = true;
+ }
+ return res;
+ }
+
+ @Override
+ public int read(byte[] b, int off, int len) throws IOException {
+ int read = stream.read(b, off, len);
+ if (read < len) {
+ eof = true;
+ }
+ return read;
+ }
+
+ @Override
+ public int available() throws IOException {
+ return stream.available();
+ }
+
+ @Override
+ public void close() throws IOException {
+ stream.close();
+ }
+ }
+
+ private InputStreamSupport() {}
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java
new file mode 100644
index 00000000..316a6dfd
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java
@@ -0,0 +1,63 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static java.util.stream.Collectors.toList;
+
+import java.lang.annotation.Annotation;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.Method;
+import java.lang.reflect.Type;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * A factory for {@link AnnotatedType} instances capturing method parameters.
+ *
+ * <p>Due to type erasure, this class can only be used by creating an anonymous subclass with a
+ * method called {@code foo} that takes exactly the desired parameter.
+ *
+ * <p>Example: {@code new ParameterHolder {void foo(@NotNull List<String> param)}.annotatedType}
+ */
+public abstract class ParameterHolder {
+ protected ParameterHolder() {}
+
+ public AnnotatedType annotatedType() {
+ return getMethod().getAnnotatedParameterTypes()[0];
+ }
+
+ public Type type() {
+ return annotatedType().getType();
+ }
+
+ public Annotation[] parameterAnnotations() {
+ return getMethod().getParameterAnnotations()[0];
+ }
+
+ private Method getMethod() {
+ List<Method> foos = Arrays.stream(this.getClass().getDeclaredMethods())
+ .filter(method -> method.getName().equals("foo"))
+ .collect(toList());
+ require(foos.size() == 1,
+ this.getClass().getName() + " must define exactly one function named 'foo'");
+ Method foo = foos.get(0);
+ require(foo.getParameterCount() == 1,
+ this.getClass().getName() + "#foo must define exactly one parameter");
+ return foo;
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java
new file mode 100644
index 00000000..a77f65fb
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static java.util.Objects.requireNonNull;
+
+public final class Preconditions {
+ private Preconditions() {}
+
+ public static void check(boolean property) {
+ if (!property) {
+ throw new IllegalStateException();
+ }
+ }
+
+ public static void check(boolean property, String message) {
+ if (!property) {
+ throw new IllegalStateException(message);
+ }
+ }
+
+ public static void require(boolean property) {
+ if (!property) {
+ throw new IllegalArgumentException();
+ }
+ }
+
+ public static void require(boolean property, String message) {
+ if (!property) {
+ throw new IllegalArgumentException(message);
+ }
+ }
+
+ public static <T> T[] requireNonNullElements(T[] array) {
+ requireNonNull(array);
+ for (T element : array) {
+ requireNonNull(element, "array must not contain null elements");
+ }
+ return array;
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java
new file mode 100644
index 00000000..5cfa765e
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import java.util.SplittableRandom;
+
+public final class RandomSupport {
+ private RandomSupport() {}
+
+ /**
+ * Polyfill for {@link SplittableRandom#nextBytes(byte[])}, which is not available in Java 8.
+ */
+ public static void nextBytes(SplittableRandom random, byte[] bytes) {
+ // Taken from the implementation contract
+ // https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/RandomGenerator.html#nextBytes(byte%5B%5D)
+ // for interoperability with the RandomGenerator interface available as of Java 17.
+ int i = 0;
+ int len = bytes.length;
+ for (int words = len >> 3; words-- > 0;) {
+ long rnd = random.nextLong();
+ for (int n = 8; n-- > 0; rnd >>>= Byte.SIZE) bytes[i++] = (byte) rnd;
+ }
+ if (i < len)
+ for (long rnd = random.nextLong(); i<len; rnd>>>= Byte.SIZE) bytes[i++] = (byte) rnd;
+ }
+
+ /**
+ * Clamp function for integers, which Java does not yet have
+ *
+ * @param value the value you want to clamp
+ * @param min the minimum allowable value (inclusive)
+ * @param max the maximum allowable value (inclusive)
+ * @return Closest number to {@code value} within the range {@code [min, max]}
+ */
+ public static int clamp(int value, int min, int max) {
+ return Math.min(Math.max(value, min), max);
+ }
+
+ /**
+ * Clamp function for longs, which Java does not yet have
+ *
+ * @param value the value you want to clamp
+ * @param min the minimum allowable value (inclusive)
+ * @param max the maximum allowable value (inclusive)
+ * @return Closest number to {@code value} within the range {@code [min, max]}
+ */
+ public static long clamp(long value, long min, long max) {
+ return Math.min(Math.max(value, min), max);
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java
new file mode 100644
index 00000000..b61980c4
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static java.util.stream.Collectors.toList;
+
+import java.util.AbstractMap.SimpleEntry;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Optional;
+import java.util.function.IntFunction;
+import java.util.stream.Stream;
+
+public final class StreamSupport {
+ private StreamSupport() {}
+
+ public static boolean[] toBooleanArray(Stream<Boolean> stream) {
+ List<Boolean> list = stream.collect(toList());
+ boolean[] array = new boolean[list.size()];
+ for (int i = 0; i < list.size(); i++) {
+ array[i] = list.get(i);
+ }
+ return array;
+ }
+
+ /**
+ * @return the first present value, otherwise {@link Optional#empty()}
+ */
+ public static <T> Optional<T> findFirstPresent(Stream<Optional<T>> stream) {
+ return stream.filter(Optional::isPresent).map(Optional::get).findFirst();
+ }
+
+ /**
+ * @return an array with the values if all {@link Optional}s are present, otherwise
+ * {@link Optional#empty()}
+ */
+ public static <T> Optional<T[]> toArrayOrEmpty(
+ Stream<Optional<T>> stream, IntFunction<T[]> newArray) {
+ try {
+ return Optional.of(stream.map(Optional::get).toArray(newArray));
+ } catch (NoSuchElementException e) {
+ return Optional.empty();
+ }
+ }
+
+ /**
+ * Return a stream containing the optional value if present, otherwise an empty stream.
+ *
+ * @return stream containing the optional value
+ */
+ public static <T> Stream<T> getOrEmpty(Optional<T> optional) {
+ return optional.isPresent() ? Stream.of(optional.get()) : Stream.empty();
+ }
+
+ public static <K, V> SimpleEntry<K, V> entry(K key, V value) {
+ return new SimpleEntry<>(key, value);
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java
new file mode 100644
index 00000000..e703f9f1
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import java.lang.reflect.AnnotatedParameterizedType;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.Type;
+
+/**
+ * A factory for {@link AnnotatedType} instances capturing types.
+ *
+ * <p>Due to type erasure, this class can only be used by creating an anonymous subclass.
+ *
+ * <p>Example: {@code new TypeHolder<List<String>> {}.annotatedType}
+ *
+ * @param <T> the type to hold
+ */
+public abstract class TypeHolder<T> {
+ protected TypeHolder() {}
+
+ public AnnotatedType annotatedType() {
+ return ((AnnotatedParameterizedType) this.getClass().getAnnotatedSuperclass())
+ .getAnnotatedActualTypeArguments()[0];
+ }
+
+ public Type type() {
+ return annotatedType().getType();
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java
new file mode 100644
index 00000000..8ce3aefc
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java
@@ -0,0 +1,564 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.check;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.require;
+import static com.code_intelligence.jazzer.mutation.support.Preconditions.requireNonNullElements;
+import static java.util.Arrays.stream;
+import static java.util.Objects.requireNonNull;
+import static java.util.stream.Collectors.joining;
+import static java.util.stream.Collectors.toSet;
+
+import com.code_intelligence.jazzer.mutation.annotation.NotNull;
+import com.code_intelligence.jazzer.mutation.annotation.WithLength;
+import java.lang.annotation.Annotation;
+import java.lang.annotation.Inherited;
+import java.lang.reflect.AnnotatedArrayType;
+import java.lang.reflect.AnnotatedElement;
+import java.lang.reflect.AnnotatedParameterizedType;
+import java.lang.reflect.AnnotatedType;
+import java.lang.reflect.AnnotatedTypeVariable;
+import java.lang.reflect.AnnotatedWildcardType;
+import java.lang.reflect.Array;
+import java.lang.reflect.ParameterizedType;
+import java.lang.reflect.Type;
+import java.util.*;
+import java.util.function.BiConsumer;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+public final class TypeSupport {
+ private static final Annotation NOT_NULL =
+ new TypeHolder<@NotNull String>() {}.annotatedType().getAnnotation(NotNull.class);
+
+ private TypeSupport() {}
+
+ public static boolean isPrimitive(AnnotatedType type) {
+ return isPrimitive(type.getType());
+ }
+
+ public static boolean isPrimitive(Type type) {
+ if (!(type instanceof Class<?>) ) {
+ return false;
+ }
+ return ((Class<?>) type).isPrimitive();
+ }
+
+ public static boolean isInheritable(Annotation annotation) {
+ return annotation.annotationType().getDeclaredAnnotation(Inherited.class) != null;
+ }
+
+ /**
+ * Returns {@code type} as a {@code Class<? extends T>} if it is a subclass of T, otherwise
+ * empty.
+ *
+ * <p>This function also returns an empty {@link Optional} for more complex (e.g. parameterized)
+ * types.
+ */
+ public static <T> Optional<Class<? extends T>> asSubclassOrEmpty(
+ AnnotatedType type, Class<T> superclass) {
+ if (!(type.getType() instanceof Class<?>) ) {
+ return Optional.empty();
+ }
+
+ Class<?> actualClazz = (Class<?>) type.getType();
+ if (!superclass.isAssignableFrom(actualClazz)) {
+ return Optional.empty();
+ }
+
+ return Optional.of(actualClazz.asSubclass(superclass));
+ }
+
+ public static AnnotatedType asAnnotatedType(Class<?> clazz) {
+ requireNonNull(clazz);
+ return new AnnotatedType() {
+ @Override
+ public Type getType() {
+ return clazz;
+ }
+
+ @Override
+ public <T extends Annotation> T getAnnotation(Class<T> annotationClass) {
+ return annotatedElementGetAnnotation(this, annotationClass);
+ }
+
+ @Override
+ public Annotation[] getAnnotations() {
+ // No directly present annotations, look for inheritable present annotations on the
+ // superclass.
+ if (clazz.getSuperclass() == null) {
+ return new Annotation[0];
+ }
+ return stream(clazz.getSuperclass().getAnnotations())
+ .filter(TypeSupport::isInheritable)
+ .toArray(Annotation[] ::new);
+ }
+
+ @Override
+ public Annotation[] getDeclaredAnnotations() {
+ // No directly present annotations.
+ return new Annotation[0];
+ }
+
+ @Override
+ public String toString() {
+ return annotatedTypeToString(this);
+ }
+
+ @Override
+ public int hashCode() {
+ throw new UnsupportedOperationException(
+ "hashCode() is not supported as its behavior isn't specified");
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ throw new UnsupportedOperationException(
+ "equals() is not supported as its behavior isn't specified");
+ }
+ };
+ }
+
+ /**
+ * Visits the individual classes and their directly present annotations that make up the given
+ * type.
+ *
+ * <p>Classes are visited in left-to-right order as they appear in the type definition, except
+ * that an array class is visited before its component class.
+ *
+ * @throws IllegalArgumentException if the given type contains a wildcard type or type variable
+ */
+ public static void visitAnnotatedType(
+ AnnotatedType type, BiConsumer<Class<?>, Annotation[]> visitor) {
+ visitAnnotatedTypeInternal(type, visitor);
+ }
+
+ private static Class<?> visitAnnotatedTypeInternal(
+ AnnotatedType type, BiConsumer<Class<?>, Annotation[]> visitor) {
+ Class<?> clazz;
+ if (type instanceof AnnotatedWildcardType) {
+ throw new IllegalArgumentException("Wildcard types are not supported: " + type);
+ } else if (type instanceof AnnotatedTypeVariable) {
+ throw new IllegalArgumentException("Type variables are not supported: " + type);
+ } else if (type instanceof AnnotatedParameterizedType) {
+ AnnotatedParameterizedType annotatedParameterizedType = (AnnotatedParameterizedType) type;
+ check(annotatedParameterizedType.getType() instanceof ParameterizedType);
+ Type rawType = ((ParameterizedType) annotatedParameterizedType.getType()).getRawType();
+ check(rawType instanceof Class<?>);
+ clazz = (Class<?>) rawType;
+
+ visitor.accept(clazz, type.getDeclaredAnnotations());
+ for (AnnotatedType typeArgument :
+ annotatedParameterizedType.getAnnotatedActualTypeArguments()) {
+ visitAnnotatedTypeInternal(typeArgument, visitor);
+ }
+ } else if (type instanceof AnnotatedArrayType) {
+ AnnotatedArrayType arrayType = (AnnotatedArrayType) type;
+
+ // Recursively determine the array class before visiting the component type.
+ Class<?> componentClass =
+ visitAnnotatedTypeInternal(arrayType.getAnnotatedGenericComponentType(), (c, a) -> {});
+ clazz = Array.newInstance(componentClass, 0).getClass();
+ visitor.accept(clazz, type.getDeclaredAnnotations());
+ visitAnnotatedTypeInternal(arrayType.getAnnotatedGenericComponentType(), visitor);
+ } else {
+ check(type.getType() instanceof Class<?>);
+ clazz = (Class<?>) type.getType();
+
+ visitor.accept(clazz, type.getDeclaredAnnotations());
+ }
+ return clazz;
+ }
+
+ public static AnnotatedType notNull(AnnotatedType type) {
+ return withExtraAnnotations(type, NOT_NULL);
+ }
+
+ /**
+ * Constructs an anonymous WithLength class that can be applied as an annotation to {@code type}
+ * with the given
+ * {@code min} and {@code max} values.
+ * @param type
+ * @param min
+ * @param max
+ * @return {@code type} with a `WithLength` annotation applied to it
+ */
+ public static AnnotatedType withLength(AnnotatedType type, int min, int max) {
+ WithLength withLength = withLengthImplementation(min, max);
+ return withExtraAnnotations(type, withLength);
+ }
+
+ private static WithLength withLengthImplementation(int min, int max) {
+ return new WithLength() {
+ @Override
+ public int min() {
+ return min;
+ }
+
+ @Override
+ public int max() {
+ return max;
+ }
+
+ @Override
+ public Class<? extends Annotation> annotationType() {
+ return WithLength.class;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof WithLength)) {
+ return false;
+ }
+ WithLength other = (WithLength) o;
+ return this.min() == other.min() && this.max() == other.max();
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 0;
+ hash += ("min".hashCode() * 127) ^ Integer.valueOf(this.min()).hashCode();
+ hash += ("max".hashCode() * 127) ^ Integer.valueOf(this.max()).hashCode();
+ return hash;
+ }
+ };
+ }
+
+ public static AnnotatedParameterizedType withTypeArguments(
+ AnnotatedType type, AnnotatedType... typeArguments) {
+ requireNonNull(type);
+ requireNonNullElements(typeArguments);
+ require(typeArguments.length > 0);
+ require(!(type instanceof AnnotatedParameterizedType || type instanceof AnnotatedTypeVariable
+ || type instanceof AnnotatedWildcardType || type instanceof AnnotatedArrayType),
+ "only plain annotated types are supported");
+ require(
+ ((Class<?>) type.getType()).getEnclosingClass() == null, "nested classes aren't supported");
+
+ ParameterizedType filledRawType = new ParameterizedType() {
+ @Override
+ public Type[] getActualTypeArguments() {
+ return stream(typeArguments).map(AnnotatedType::getType).toArray(Type[] ::new);
+ }
+
+ @Override
+ public Type getRawType() {
+ return type.getType();
+ }
+
+ @Override
+ public Type getOwnerType() {
+ // We require the class is top-level.
+ return null;
+ }
+
+ @Override
+ public String toString() {
+ return getRawType()
+ + stream(getActualTypeArguments()).map(Type::toString).collect(joining(",", "<", ">"));
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof ParameterizedType)) {
+ return false;
+ }
+ ParameterizedType other = (ParameterizedType) obj;
+ return getRawType().equals(other.getRawType()) && null == other.getOwnerType()
+ && Arrays.equals(getActualTypeArguments(), other.getActualTypeArguments());
+ }
+
+ @Override
+ public int hashCode() {
+ throw new UnsupportedOperationException(
+ "hashCode() is not supported as its behavior isn't specified");
+ }
+ };
+
+ return new AnnotatedParameterizedType() {
+ @Override
+ public AnnotatedType[] getAnnotatedActualTypeArguments() {
+ return Arrays.copyOf(typeArguments, typeArguments.length);
+ }
+
+ // @Override as of Java 9
+ @SuppressWarnings("Since15")
+ public AnnotatedType getAnnotatedOwnerType() {
+ return null;
+ }
+
+ @Override
+ public Type getType() {
+ return filledRawType;
+ }
+
+ @Override
+ public <T extends Annotation> T getAnnotation(Class<T> annotationClass) {
+ return type.getAnnotation(annotationClass);
+ }
+
+ @Override
+ public Annotation[] getAnnotations() {
+ return type.getAnnotations();
+ }
+
+ @Override
+ public Annotation[] getDeclaredAnnotations() {
+ return type.getDeclaredAnnotations();
+ }
+
+ @Override
+ public String toString() {
+ return annotatedTypeToString(this);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof AnnotatedParameterizedType)) {
+ return false;
+ }
+ AnnotatedParameterizedType other = (AnnotatedParameterizedType) obj;
+ // Can't call getAnnotatedOwnerType on Java 8, but since our own implementation always
+ // returns null, comparing getType().getOwnerType() via getType() is sufficient.
+ return Objects.equals(getType(), other.getType())
+ && Arrays.equals(
+ getAnnotatedActualTypeArguments(), other.getAnnotatedActualTypeArguments())
+ && Arrays.equals(getAnnotations(), other.getAnnotations());
+ }
+
+ @Override
+ public int hashCode() {
+ throw new UnsupportedOperationException(
+ "hashCode() is not supported as its behavior isn't specified");
+ }
+ };
+ }
+
+ public static AnnotatedType withExtraAnnotations(
+ AnnotatedType base, Annotation... extraAnnotations) {
+ requireNonNull(base);
+ requireNonNullElements(extraAnnotations);
+
+ if (extraAnnotations.length == 0) {
+ return base;
+ }
+
+ require(!(base instanceof AnnotatedTypeVariable || base instanceof AnnotatedWildcardType),
+ "Adding annotations to AnnotatedTypeVariables or AnnotatedWildcardTypes is not supported");
+ if (base instanceof AnnotatedArrayType) {
+ return new AugmentedArrayType((AnnotatedArrayType) base, extraAnnotations);
+ } else if (base instanceof AnnotatedParameterizedType) {
+ return new AugmentedParameterizedType((AnnotatedParameterizedType) base, extraAnnotations);
+ } else {
+ return new AugmentedAnnotatedType(base, extraAnnotations);
+ }
+ }
+
+ private static String annotatedTypeToString(AnnotatedType annotatedType) {
+ String annotations =
+ stream(annotatedType.getAnnotations()).map(Annotation::toString).collect(joining(" "));
+ if (annotations.isEmpty()) {
+ return annotatedType.getType().toString();
+ } else {
+ return annotations + " " + annotatedType.getType();
+ }
+ }
+
+ private static <T extends Annotation> T annotatedElementGetAnnotation(
+ AnnotatedElement element, Class<T> annotationClass) {
+ requireNonNull(annotationClass);
+ return stream(element.getAnnotations())
+ .filter(annotation -> annotationClass.equals(annotation.annotationType()))
+ .findFirst()
+ .map(annotationClass::cast)
+ .orElse(null);
+ }
+
+ public static Optional<Class<?>> findFirstParentIfClass(AnnotatedType type, Class<?>... parents) {
+ if (!(type.getType() instanceof Class<?>) ) {
+ return Optional.empty();
+ }
+ Class<?> clazz = (Class<?>) type.getType();
+ return Stream.of(parents).filter(parent -> parent.isAssignableFrom(clazz)).findFirst();
+ }
+
+ public static Optional<AnnotatedType> parameterTypeIfParameterized(
+ AnnotatedType type, Class<?> expectedParent) {
+ return parameterTypesIfParameterized(type, expectedParent).flatMap(typeArguments -> {
+ if (typeArguments.size() != 1) {
+ return Optional.empty();
+ } else {
+ AnnotatedType elementType = typeArguments.get(0);
+ if (!(elementType.getType() instanceof ParameterizedType)
+ && !(elementType.getType() instanceof Class)) {
+ return Optional.empty();
+ } else {
+ return Optional.of(elementType);
+ }
+ }
+ });
+ }
+
+ public static Optional<List<AnnotatedType>> parameterTypesIfParameterized(
+ AnnotatedType type, Class<?> expectedParent) {
+ if (!(type instanceof AnnotatedParameterizedType)) {
+ return Optional.empty();
+ }
+ Class<?> clazz = (Class<?>) ((ParameterizedType) type.getType()).getRawType();
+ if (!expectedParent.isAssignableFrom(clazz)) {
+ return Optional.empty();
+ }
+
+ AnnotatedType[] typeArguments =
+ ((AnnotatedParameterizedType) type).getAnnotatedActualTypeArguments();
+ if (typeArguments.length == 0) {
+ return Optional.empty();
+ }
+ return Optional.of(Collections.unmodifiableList(Arrays.asList(typeArguments)));
+ }
+
+ /**
+ * Whether {@code root} is contained in a directed cycle in the directed graph rooted at it and
+ * defined by the given {@code successors} function.
+ */
+ public static <T> boolean containedInDirectedCycle(T root, Function<T, Stream<T>> successors) {
+ HashSet<T> traversed = new HashSet<>();
+ ArrayDeque<T> toTraverse = new ArrayDeque<>();
+ toTraverse.addLast(root);
+ T currentNode;
+ while ((currentNode = toTraverse.pollLast()) != null) {
+ if (traversed.add(currentNode)) {
+ successors.apply(currentNode).forEachOrdered(toTraverse::addLast);
+ } else if (currentNode.equals(root)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private static class AugmentedArrayType
+ extends AugmentedAnnotatedType implements AnnotatedArrayType {
+ private AugmentedArrayType(AnnotatedArrayType base, Annotation[] extraAnnotations) {
+ super(base, extraAnnotations);
+ }
+
+ @Override
+ public AnnotatedType getAnnotatedGenericComponentType() {
+ return ((AnnotatedArrayType) base).getAnnotatedGenericComponentType();
+ }
+
+ // @Override as of Java 9
+ @SuppressWarnings("Since15")
+ public AnnotatedType getAnnotatedOwnerType() {
+ throw new UnsupportedOperationException("Not implemented");
+ }
+ }
+
+ private static class AugmentedParameterizedType
+ extends AugmentedAnnotatedType implements AnnotatedParameterizedType {
+ private AugmentedParameterizedType(
+ AnnotatedParameterizedType base, Annotation[] extraAnnotations) {
+ super(base, extraAnnotations);
+ }
+
+ @Override
+ public AnnotatedType[] getAnnotatedActualTypeArguments() {
+ return ((AnnotatedParameterizedType) base).getAnnotatedActualTypeArguments();
+ }
+
+ // @Override as of Java 9
+ @SuppressWarnings("Since15")
+ public AnnotatedType getAnnotatedOwnerType() {
+ throw new UnsupportedOperationException("Not implemented");
+ }
+ }
+
+ private static class AugmentedAnnotatedType implements AnnotatedType {
+ protected final AnnotatedType base;
+ private final Annotation[] extraAnnotations;
+
+ private AugmentedAnnotatedType(AnnotatedType base, Annotation[] extraAnnotations) {
+ this.base = requireNonNull(base);
+ this.extraAnnotations = checkExtraAnnotations(base, extraAnnotations);
+ }
+
+ private static Annotation[] checkExtraAnnotations(
+ AnnotatedElement base, Annotation[] extraAnnotations) {
+ requireNonNullElements(extraAnnotations);
+ Set<Class<? extends Annotation>> existingAnnotationTypes =
+ stream(base.getDeclaredAnnotations())
+ .map(Annotation::annotationType)
+ .collect(Collectors.toCollection(HashSet::new));
+ for (Annotation annotation : extraAnnotations) {
+ boolean added = existingAnnotationTypes.add(annotation.annotationType());
+ require(added, annotation + " already directly present on " + base);
+ }
+ return extraAnnotations;
+ }
+
+ @Override
+ public Type getType() {
+ return base.getType();
+ }
+
+ @Override
+ public <T extends Annotation> T getAnnotation(Class<T> annotationClass) {
+ return annotatedElementGetAnnotation(this, annotationClass);
+ }
+
+ @Override
+ public Annotation[] getAnnotations() {
+ Set<Class<? extends Annotation>> directlyPresentTypes =
+ stream(getDeclaredAnnotations()).map(Annotation::annotationType).collect(toSet());
+ return Stream
+ .concat(
+ // Directly present annotations.
+ stream(getDeclaredAnnotations()),
+ // Present but not directly present annotations, never added by us as we don't add
+ // annotations to the super class.
+ stream(base.getAnnotations())
+ .filter(
+ annotation -> !directlyPresentTypes.contains(annotation.annotationType())))
+ .toArray(Annotation[] ::new);
+ }
+
+ @Override
+ public Annotation[] getDeclaredAnnotations() {
+ return Stream.concat(stream(base.getDeclaredAnnotations()), stream(extraAnnotations))
+ .toArray(Annotation[] ::new);
+ }
+
+ @Override
+ public String toString() {
+ return annotatedTypeToString(this);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ throw new UnsupportedOperationException(
+ "equals() is not supported as its behavior isn't specified");
+ }
+
+ @Override
+ public int hashCode() {
+ throw new UnsupportedOperationException(
+ "hashCode() is not supported as its behavior isn't specified");
+ }
+ }
+}
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java
new file mode 100644
index 00000000..0eef7c24
--- /dev/null
+++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java
@@ -0,0 +1,168 @@
+/*
+ * Copyright 2023 Code Intelligence GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.code_intelligence.jazzer.mutation.support;
+
+import static java.util.stream.Collectors.toSet;
+
+import java.lang.ref.Reference;
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.WeakReference;
+import java.util.AbstractMap.SimpleEntry;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+
+/**
+ * An unoptimized version of a {@link java.util.WeakHashMap} with the semantics of a
+ * {@link java.util.IdentityHashMap}.
+ *
+ * <p>If this class ever becomes a bottleneck, e.g. because of the IdentityWeakReference
+ * allocations, it should be replaced by a copy of the * {@link java.util.WeakHashMap} code with all
+ * {@code equals} calls dropped and all {@code hashCode} * calls replaced with {@link
+ * System#identityHashCode}.
+ */
+public final class WeakIdentityHashMap<K, V> implements Map<K, V> {
+ private final HashMap<WeakReference<K>, V> map = new HashMap<>();
+ private final ReferenceQueue<K> weaklyReachables = new ReferenceQueue<>();
+
+ @Override
+ public int size() {
+ removeNewWeaklyReachables();
+ return map.size();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ removeNewWeaklyReachables();
+ return map.isEmpty();
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ removeNewWeaklyReachables();
+ return map.containsKey(new IdentityWeakReference<>(key));
+ }
+
+ @Override
+ public boolean containsValue(Object value) {
+ removeNewWeaklyReachables();
+ return map.containsValue(value);
+ }
+
+ @Override
+ public V get(Object key) {
+ removeNewWeaklyReachables();
+ return map.get(new IdentityWeakReference<>(key));
+ }
+
+ @Override
+ public V put(K key, V value) {
+ removeNewWeaklyReachables();
+ return map.put(new IdentityWeakReference<>(key, weaklyReachables), value);
+ }
+
+ @Override
+ public V remove(Object key) {
+ removeNewWeaklyReachables();
+ return map.remove(new IdentityWeakReference<>(key));
+ }
+
+ @Override
+ public void putAll(Map<? extends K, ? extends V> otherMap) {
+ removeNewWeaklyReachables();
+ for (Entry<? extends K, ? extends V> entry : otherMap.entrySet()) {
+ map.put(new IdentityWeakReference<>(entry.getKey(), weaklyReachables), entry.getValue());
+ }
+ }
+
+ @Override
+ public void clear() {
+ map.clear();
+ }
+
+ @Override
+ public Set<K> keySet() {
+ removeNewWeaklyReachables();
+ return map.keySet().stream().map(WeakReference::get).filter(Objects::nonNull).collect(toSet());
+ }
+
+ @Override
+ public Collection<V> values() {
+ removeNewWeaklyReachables();
+ return map.values();
+ }
+
+ @Override
+ public Set<Entry<K, V>> entrySet() {
+ removeNewWeaklyReachables();
+ return map.entrySet()
+ .stream()
+ .map(e -> new SimpleEntry<>(e.getKey().get(), e.getValue()))
+ .filter(e -> e.getKey() != null)
+ .collect(toSet());
+ }
+
+ void collectKeysForTesting() {
+ map.keySet().forEach(ref -> {
+ ref.clear();
+ ref.enqueue();
+ });
+ }
+
+ private void removeNewWeaklyReachables() {
+ Reference<? extends K> referent;
+ while ((referent = weaklyReachables.poll()) != null) {
+ map.remove(referent);
+ }
+ }
+
+ private static final class IdentityWeakReference<T> extends WeakReference<T> {
+ private final int referentHashCode;
+
+ public IdentityWeakReference(T referent) {
+ super(referent);
+ this.referentHashCode = System.identityHashCode(referent);
+ }
+
+ public IdentityWeakReference(T referent, ReferenceQueue<? super T> queue) {
+ super(referent, queue);
+ this.referentHashCode = System.identityHashCode(referent);
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (this == other) {
+ return true;
+ }
+ if (!(other instanceof WeakReference)) {
+ return false;
+ }
+ T referent = get();
+ if (referent == null) {
+ return false;
+ }
+ return referent == ((WeakReference<?>) other).get();
+ }
+
+ @Override
+ public int hashCode() {
+ return referentHashCode;
+ }
+ }
+}