mutation: Do not initialize recursive proto fields

When recursive proto fields are initialized, the resulting messages
have an expected nesting depth on the order of the inverse of the
frequency with which a nullable value is non-null, which tends to run
into StackOverflowErrors quickly.

This is fixed by checking whether a given proto field is recursive and
if so, only initializing it "layer by layer" in mutations rather than
all at once during initialization.

5 files changed, 92 insertions, 45 deletions

diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/StressTest.java b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/StressTest.java
index 9f28941c..2e75d243 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/StressTest.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/StressTest.java
@@ -239,15 +239,10 @@ public class StressTest {
                 OptionalPrimitiveField3.newBuilder().setSomeField(false).build(),
                 OptionalPrimitiveField3.newBuilder().setSomeField(true).build())),
         arguments(new TypeHolder<@NotNull RepeatedRecursiveMessageField3>() {}.annotatedType(),
-            "{Builder.Boolean, Builder via List<(cycle) -> Message>} -> Message",
-            contains(RepeatedRecursiveMessageField3.getDefaultInstance(),
-                RepeatedRecursiveMessageField3.newBuilder().setSomeField(true).build(),
-                RepeatedRecursiveMessageField3.newBuilder()
-                    .addMessageField(RepeatedRecursiveMessageField3.getDefaultInstance())
-                    .build(),
-                RepeatedRecursiveMessageField3.newBuilder()
-                    .addMessageField(RepeatedRecursiveMessageField3.newBuilder().setSomeField(true))
-                    .build()),
+            "{Builder.Boolean, WithoutInit(Builder via List<(cycle) -> Message>)} -> Message",
+            // The message field is recursive and thus not initialized.
+            exactly(RepeatedRecursiveMessageField3.getDefaultInstance(),
+                RepeatedRecursiveMessageField3.newBuilder().setSomeField(true).build()),
             manyDistinctElements()),
         arguments(new TypeHolder<@NotNull IntegralField3>() {}.annotatedType(),
             "{Builder.Integer} -> Message",
@@ -307,14 +302,14 @@ public class StressTest {
             "{Builder via List<Float>} -> Message", distinctElementsRatio(0.20),
             distinctElementsRatio(0.9), emptyList()),
         arguments(new TypeHolder<@NotNull TestProtobuf>() {}.annotatedType(),
-            "{Builder.Nullable<Boolean>, Builder.Nullable<Integer>, Builder.Nullable<Integer>, Builder.Nullable<Long>, Builder.Nullable<Long>, Builder.Nullable<Float>, Builder.Nullable<Double>, Builder.Nullable<String>, Builder.Nullable<Enum<Enum>>, Builder.Nullable<{Builder.Nullable<Integer>, Builder via List<Integer>} -> Message>, Builder via List<Boolean>, Builder via List<Integer>, Builder via List<Integer>, Builder via List<Long>, Builder via List<Long>, Builder via List<Float>, Builder via List<Double>, Builder via List<String>, Builder via List<Enum<Enum>>, Builder via List<(cycle) -> Message>, Builder.Map<Integer,Integer>, Builder.Nullable<FixedValue(OnlyLabel)>, Builder.Nullable<{<empty>} -> Message>, Builder.Nullable<Integer> | Builder.Nullable<Long> | Builder.Nullable<Integer>} -> Message",
+            "{Builder.Nullable<Boolean>, Builder.Nullable<Integer>, Builder.Nullable<Integer>, Builder.Nullable<Long>, Builder.Nullable<Long>, Builder.Nullable<Float>, Builder.Nullable<Double>, Builder.Nullable<String>, Builder.Nullable<Enum<Enum>>, WithoutInit(Builder.Nullable<{Builder.Nullable<Integer>, Builder via List<Integer>, WithoutInit(Builder.Nullable<(cycle) -> Message>)} -> Message>), Builder via List<Boolean>, Builder via List<Integer>, Builder via List<Integer>, Builder via List<Long>, Builder via List<Long>, Builder via List<Float>, Builder via List<Double>, Builder via List<String>, Builder via List<Enum<Enum>>, WithoutInit(Builder via List<(cycle) -> Message>), Builder.Map<Integer,Integer>, Builder.Nullable<FixedValue(OnlyLabel)>, Builder.Nullable<{<empty>} -> Message>, Builder.Nullable<Integer> | Builder.Nullable<Long> | Builder.Nullable<Integer>} -> Message",
             manyDistinctElements(), manyDistinctElements()),
         arguments(
             new TypeHolder<@NotNull @DescriptorSource(
                 "com.code_intelligence.jazzer.mutation.mutator.StressTest#TEST_PROTOBUF_DESCRIPTOR")
                 DynamicMessage>() {
             }.annotatedType(),
-            "{Builder.Nullable<Boolean>, Builder.Nullable<Integer>, Builder.Nullable<Integer>, Builder.Nullable<Long>, Builder.Nullable<Long>, Builder.Nullable<Float>, Builder.Nullable<Double>, Builder.Nullable<String>, Builder.Nullable<Enum<Enum>>, Builder.Nullable<{Builder.Nullable<Integer>, Builder via List<Integer>} -> Message>, Builder via List<Boolean>, Builder via List<Integer>, Builder via List<Integer>, Builder via List<Long>, Builder via List<Long>, Builder via List<Float>, Builder via List<Double>, Builder via List<String>, Builder via List<Enum<Enum>>, Builder via List<(cycle) -> Message>, Builder.Map<Integer,Integer>, Builder.Nullable<FixedValue(OnlyLabel)>, Builder.Nullable<{<empty>} -> Message>, Builder.Nullable<Integer> | Builder.Nullable<Long> | Builder.Nullable<Integer>} -> Message",
+            "{Builder.Nullable<Boolean>, Builder.Nullable<Integer>, Builder.Nullable<Integer>, Builder.Nullable<Long>, Builder.Nullable<Long>, Builder.Nullable<Float>, Builder.Nullable<Double>, Builder.Nullable<String>, Builder.Nullable<Enum<Enum>>, WithoutInit(Builder.Nullable<{Builder.Nullable<Integer>, Builder via List<Integer>, WithoutInit(Builder.Nullable<(cycle) -> Message>)} -> Message>), Builder via List<Boolean>, Builder via List<Integer>, Builder via List<Integer>, Builder via List<Long>, Builder via List<Long>, Builder via List<Float>, Builder via List<Double>, Builder via List<String>, Builder via List<Enum<Enum>>, WithoutInit(Builder via List<(cycle) -> Message>), Builder.Map<Integer,Integer>, Builder.Nullable<FixedValue(OnlyLabel)>, Builder.Nullable<{<empty>} -> Message>, Builder.Nullable<Integer> | Builder.Nullable<Long> | Builder.Nullable<Integer>} -> Message",
             manyDistinctElements(), manyDistinctElements()),
         arguments(
             new TypeHolder<@NotNull @AnySource(
@@ -577,6 +572,10 @@ public class StressTest {
           }
         }
       } else if (field.getJavaType() == JavaType.MESSAGE) {
+        // Break up unbounded recursion.
+        if (!builder.hasField(field)) {
+          continue;
+        }
         Builder fieldBuilder = ((Message) builder.getField(field)).toBuilder();
         walkFields(fieldBuilder, transform);
         builder.setField(field, fieldBuilder.build());
diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto2Test.java b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto2Test.java
index f992d502..9492bcec 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto2Test.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto2Test.java
@@ -301,53 +301,57 @@ class BuilderMutatorProto2Test {
         (InPlaceMutator<RecursiveMessageField2.Builder>) FACTORY.createInPlaceOrThrow(
             new TypeHolder<RecursiveMessageField2.@NotNull Builder>() {}.annotatedType());
     assertThat(mutator.toString())
-        .isEqualTo("{Builder.Boolean, Builder.Nullable<(cycle) -> Message>}");
+        .isEqualTo("{Builder.Boolean, WithoutInit(Builder.Nullable<(cycle) -> Message>)}");
     RecursiveMessageField2.Builder builder = RecursiveMessageField2.newBuilder();
 
     try (MockPseudoRandom prng = mockPseudoRandom(
              // boolean
-             true,
-             // message field is not null
-             false,
-             // nested boolean,
-             false,
-             // nested message field is not set
              true)) {
       mutator.initInPlace(builder, prng);
     }
 
-    // Nested message field is *not* set explicitly and implicitly equal to the
-    // default instance.
+    assertThat(builder.build())
+        .isEqualTo(RecursiveMessageField2.newBuilder().setSomeField(true).build());
+    assertThat(builder.hasMessageField()).isFalse();
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // mutate message field (causes init to non-null)
+             1,
+             // bool field in message field
+             false)) {
+      mutator.mutateInPlace(builder, prng);
+    }
+    // Nested message field *is* set explicitly and implicitly equal to the default
+    // instance.
     assertThat(builder.build())
         .isEqualTo(RecursiveMessageField2.newBuilder()
                        .setSomeField(true)
                        .setMessageField(RecursiveMessageField2.newBuilder().setSomeField(false))
                        .build());
-    assertThat(builder.getMessageFieldBuilder().hasMessageField()).isFalse();
+    assertThat(builder.hasMessageField()).isTrue();
+    assertThat(builder.getMessageField().hasMessageField()).isFalse();
 
     try (MockPseudoRandom prng = mockPseudoRandom(
              // mutate message field
              1,
-             // mutate message field as not null
+             //  message field as not null
              false,
              // mutate message field
              1,
              // nested boolean,
-             false,
-             // nested message field is null
              true)) {
       mutator.mutateInPlace(builder, prng);
     }
-    // Nested message field *is* set explicitly and implicitly equal to the default
-    // instance.
     assertThat(builder.build())
         .isEqualTo(RecursiveMessageField2.newBuilder()
                        .setSomeField(true)
                        .setMessageField(
                            RecursiveMessageField2.newBuilder().setSomeField(false).setMessageField(
-                               RecursiveMessageField2.newBuilder().setSomeField(false)))
+                               RecursiveMessageField2.newBuilder().setSomeField(true)))
                        .build());
+    assertThat(builder.hasMessageField()).isTrue();
     assertThat(builder.getMessageField().hasMessageField()).isTrue();
+    assertThat(builder.getMessageField().getMessageField().hasMessageField()).isFalse();
   }
 
   @Test
diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto3Test.java b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto3Test.java
index c39376a2..ff298540 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto3Test.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorProto3Test.java
@@ -359,51 +359,57 @@ class BuilderMutatorProto3Test {
         (InPlaceMutator<RecursiveMessageField3.Builder>) FACTORY.createInPlaceOrThrow(
             new TypeHolder<RecursiveMessageField3.@NotNull Builder>() {}.annotatedType());
     assertThat(mutator.toString())
-        .isEqualTo("{Builder.Boolean, Builder.Nullable<(cycle) -> Message>}");
+        .isEqualTo("{Builder.Boolean, WithoutInit(Builder.Nullable<(cycle) -> Message>)}");
     RecursiveMessageField3.Builder builder = RecursiveMessageField3.newBuilder();
 
     try (MockPseudoRandom prng = mockPseudoRandom(
              // boolean
-             true,
-             // message field is not null
-             false,
-             // nested boolean,
-             false,
-             // nested message field is not set
              true)) {
       mutator.initInPlace(builder, prng);
     }
-    // Nested message field is *not* set explicitly and implicitly equal to the
-    // default instance.
+
+    assertThat(builder.build())
+        .isEqualTo(RecursiveMessageField3.newBuilder().setSomeField(true).build());
+    assertThat(builder.hasMessageField()).isFalse();
+
+    try (MockPseudoRandom prng = mockPseudoRandom(
+             // mutate message field (causes init to non-null)
+             1,
+             // bool field in message field
+             false)) {
+      mutator.mutateInPlace(builder, prng);
+    }
+    // Nested message field *is* set explicitly and implicitly equal to the default
+    // instance.
     assertThat(builder.build())
         .isEqualTo(RecursiveMessageField3.newBuilder()
                        .setSomeField(true)
-                       .setMessageField(RecursiveMessageField3.newBuilder())
+                       .setMessageField(RecursiveMessageField3.newBuilder().setSomeField(false))
                        .build());
-    assertThat(builder.getMessageFieldBuilder().hasMessageField()).isFalse();
+    assertThat(builder.hasMessageField()).isTrue();
+    assertThat(builder.getMessageField().hasMessageField()).isFalse();
 
     try (MockPseudoRandom prng = mockPseudoRandom(
              // mutate message field
              1,
-             // mutate message field as not null
+             //  message field as not null
              false,
              // mutate message field
              1,
              // nested boolean,
-             false,
-             // nested message field is null
              true)) {
       mutator.mutateInPlace(builder, prng);
     }
-    // Nested message field *is* set explicitly and implicitly equal to the default
-    // instance.
     assertThat(builder.build())
         .isEqualTo(RecursiveMessageField3.newBuilder()
                        .setSomeField(true)
-                       .setMessageField(RecursiveMessageField3.newBuilder().setMessageField(
-                           RecursiveMessageField3.newBuilder()))
+                       .setMessageField(
+                           RecursiveMessageField3.newBuilder().setSomeField(false).setMessageField(
+                               RecursiveMessageField3.newBuilder().setSomeField(true)))
                        .build());
+    assertThat(builder.hasMessageField()).isTrue();
     assertThat(builder.getMessageField().hasMessageField()).isTrue();
+    assertThat(builder.getMessageField().getMessageField().hasMessageField()).isFalse();
   }
 
   @Test
diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/proto2.proto b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/proto2.proto
index 75ab5e95..a3d563d8 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/proto2.proto
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto/proto2.proto
@@ -75,11 +75,20 @@ message StringField2 {
 optional string some_field = 1;
 }
 
+message Parent {
+  optional Child child = 1;
+}
+
+message Child {
+  optional Parent parent = 1;
+}
+
 // Taken from
 // https://github.com/google/fuzztest/blob/c5fde4baee6134c84d4f2b618def9f60c7505151/fuzztest/internal/test_protobuf.proto#L24
 message TestSubProtobuf {
   optional int32 subproto_i32 = 1;
   repeated int32 subproto_rep_i32 = 2 [packed = true];
+  optional TestProtobuf parent = 3;
 }
 
 message TestProtobuf {
diff --git a/src/test/java/com/code_intelligence/jazzer/mutation/support/TypeSupportTest.java b/src/test/java/com/code_intelligence/jazzer/mutation/support/TypeSupportTest.java
index d5571a1e..bbf4a7e6 100644
--- a/src/test/java/com/code_intelligence/jazzer/mutation/support/TypeSupportTest.java
+++ b/src/test/java/com/code_intelligence/jazzer/mutation/support/TypeSupportTest.java
@@ -18,6 +18,7 @@ package com.code_intelligence.jazzer.mutation.support;
 
 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.containedInDirectedCycle;
 import static com.code_intelligence.jazzer.mutation.support.TypeSupport.visitAnnotatedType;
 import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withTypeArguments;
 import static com.google.common.truth.Truth.assertThat;
@@ -36,6 +37,8 @@ import java.lang.reflect.ParameterizedType;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.function.Function;
+import java.util.stream.Stream;
 import org.junit.jupiter.api.Test;
 import org.junit.jupiter.api.condition.EnabledForJreRange;
 import org.junit.jupiter.api.condition.JRE;
@@ -237,4 +240,30 @@ class TypeSupportTest {
             byte[][].class, 5, byte[].class, 3, byte.class, 6, Byte.class)
         .inOrder();
   }
+
+  @Test
+  void testContainedInDirectedCycle() {
+    Function<Integer, Stream<Integer>> successors = integer -> {
+      switch (integer) {
+        case 1:
+          return Stream.of(2);
+        case 2:
+          return Stream.of(3);
+        case 3:
+          return Stream.of(4, 5);
+        case 4:
+          return Stream.of(2);
+        case 5:
+          return Stream.empty();
+        default:
+          throw new IllegalStateException();
+      }
+    };
+
+    assertThat(containedInDirectedCycle(1, successors)).isFalse();
+    assertThat(containedInDirectedCycle(2, successors)).isTrue();
+    assertThat(containedInDirectedCycle(3, successors)).isTrue();
+    assertThat(containedInDirectedCycle(4, successors)).isTrue();
+    assertThat(containedInDirectedCycle(5, successors)).isFalse();
+  }
 }