OneOf input objects can be defined in a way that makes it impossible to create a value for that type. This breaks the spec's unwritten requirement that all input types be inhabited.

The simplest example of an uninhabited OneOf is the self-recursing input Foo @oneOf { foo:Foo }. Trying to create a value for this type requires an infinitely nested object value, and should be invalid for the same reason that the spec currently considers the non-OneOf variant input Foo { foo:Foo! } to be invalid.

I have an open spec PR that updates the recursive input object requirements to consider OneOf input objects. The proposed algorithm was implemented in graphql-js here.

I previously added a version of these rules to graphql-java, but this was before I had a complete grasp on the problem and the validation is incomplete.

For example, this mixed-OneOf type graph also requires infinite values and is incorrectly allowed by graphql-java:

input Foo @oneOf { bar:Bar }
input Bar { foo:Foo! }

This PR closes this validation hole by porting over graphql-js's implementation of this validator.

Perf

The validator runs once per schema. It uses a worklist algorithm and takes time that is linear relative to the total number of input object fields in a schema. I've included a benchmark that tests a variety of different schemas:

Benchmark                                                           Mode  Cnt   Score   Error  Units
InputObjectHasUnbreakableCycleBenchmark.finiteValuePropagation      avgt    6  33.829 ± 5.185  us/op
InputObjectHasUnbreakableCycleBenchmark.tenTypeMixedInputCycle      avgt    6  34.151 ± 4.320  us/op
InputObjectHasUnbreakableCycleBenchmark.tenTypeTenFieldsInputCycle  avgt    6  52.809 ± 8.401  us/op
InputObjectHasUnbreakableCycleBenchmark.twoTypeMixedInputCycle      avgt    6  28.624 ± 3.921  us/op

The takeaway is that performance is relatively stable even for pathological input object graphs.