Summary
Schema.UnmarshalYAML (parser/schema_yaml.go, added in #399) decodes an items: subtree twice: once generically by the alias decode, which builds a map[string]any that is then thrown away, and once typed by promoteYAMLSchemaOrBool decoding the field's own node. Because that repeats at every level, a chain of nested items: is O(n²) in depth.
Impact
Small in practice. Measured at ~0.2 µs/byte through depth 1000, so it is not a DoS vector, and real specs do not nest items: anywhere near that deep. On flat real-world specs the cost shows up only as part of the accepted +4.8% allocs / +8.0% B/op parse regression from #399.
Known fix
A variant was prototyped during #399 that withholds the five schema-or-bool keys from the alias decode, so each subtree is decoded exactly once:
- walk the mapping node once, decoding each schema-or-bool value from its own node
- build a shallow copy of the mapping with those key/value pairs removed
- hand that filtered node to the alias decode
That makes the work linear in depth. It was measured on the existing benchmarks and reclaimed only ~0.7pp of allocs/op and ~0.4pp of B/op, which did not justify its complexity at the time — the flat fixtures in testdata/bench/ do not exercise the quadratic term at all.
The asymptotic argument is a better reason to do it than the flat-spec numbers were. If it is picked up, note the two edge cases the current implementation handles and any replacement must keep:
- a value inherited through a merge key (
<<) has no node under the merging node, so it still needs the decodeSchemaOrBool fallback
yaml.Unmarshal hands an Unmarshaler the DocumentNode rather than its content, so a root-level Schema sees a different node kind than a nested one (unwrapSchemaNode covers this, and TestSchemaUnmarshalYAMLReportsNestedDecodeErrors is the test that catches getting it wrong)
Raised during v1.57.0 release review.
Summary
Schema.UnmarshalYAML(parser/schema_yaml.go, added in #399) decodes anitems:subtree twice: once generically by the alias decode, which builds amap[string]anythat is then thrown away, and once typed bypromoteYAMLSchemaOrBooldecoding the field's own node. Because that repeats at every level, a chain of nesteditems:is O(n²) in depth.Impact
Small in practice. Measured at ~0.2 µs/byte through depth 1000, so it is not a DoS vector, and real specs do not nest
items:anywhere near that deep. On flat real-world specs the cost shows up only as part of the accepted +4.8% allocs / +8.0% B/op parse regression from #399.Known fix
A variant was prototyped during #399 that withholds the five schema-or-bool keys from the alias decode, so each subtree is decoded exactly once:
That makes the work linear in depth. It was measured on the existing benchmarks and reclaimed only ~0.7pp of allocs/op and ~0.4pp of B/op, which did not justify its complexity at the time — the flat fixtures in
testdata/bench/do not exercise the quadratic term at all.The asymptotic argument is a better reason to do it than the flat-spec numbers were. If it is picked up, note the two edge cases the current implementation handles and any replacement must keep:
<<) has no node under the merging node, so it still needs thedecodeSchemaOrBoolfallbackyaml.Unmarshalhands anUnmarshalerthe DocumentNode rather than its content, so a root-levelSchemasees a different node kind than a nested one (unwrapSchemaNodecovers this, andTestSchemaUnmarshalYAMLReportsNestedDecodeErrorsis the test that catches getting it wrong)Raised during v1.57.0 release review.