smith: Stack overflow generating an operation against recursive type

[SimonSapin]

Description

Trying to use apollo-smith to generate random operations against an given type system, I ran into stack overflows. This seems to happen when a type can refer to itself, generating deeply nested selection sets.

Steps to reproduce

In short:

• use DocumentBuilder::with_document with
  • sufficiently-long random unstructured input
  • parsed schema { query: Query } type Query { id: ID! parent: Query }
• use DocumentBuilder::operation_definition
• maybe repeat a few times with different random input

In full:

#![cfg(feature = "parser-impl")]

use apollo_smith::Document;
use apollo_smith::DocumentBuilder;

#[test]
fn test_recursive_type() {
    let schema = parse("schema { query: Query } type Query { id: ID! parent: Query }");
    let mut state: u32 = 0;
    let mut prng = || {
        state = state.wrapping_mul(134775813).wrapping_add(1);
        (state >> 24) as u8
    };
    for _ in 0..10 {
        let long = std::iter::repeat_with(&mut prng)
            .take(1024 * 1024)
            .collect::<Vec<_>>();
        generate(schema.clone(), &long);
    }
}

fn parse(schema: &str) -> Document {
    apollo_parser::Parser::new(schema)
        .parse()
        .document()
        .try_into()
        .unwrap()
}

fn generate(schema: Document, unstructured: &[u8]) {
    let mut u = arbitrary::Unstructured::new(unstructured);
    DocumentBuilder::with_document(&mut u, schema)
        .unwrap()
        .operation_definition()
        .unwrap();
}

Expected result

The test terminates in reasonable time and passes

Actual result

running 1 test

thread 'test_recursive_type' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass `-p apollo-smith --test with_document`

Caused by:
  process didn't exit successfully: `/Users/simon/projects/apollo-rs/target/debug/deps/with_document-c24379594086b8ec recur`
  (signal: 6, SIGABRT: process abort signal)

Environment

• Operating system: macOS
• apollo-rs crate: smith
• Crate version: current main, 3af152c200fe2eb0bf793f4d95a7b5bef67b00a6