Skip to content

internal/harness: the two-order oracle mistakes permutation artifacts for order dependence #241

Description

@OmarAlJarrah

Summary

orderInvariant (internal/harness/order.go) compiles a source as written and again
with every mapping reversed, and reports what the permutation changed. Its
correctness rests on the rewrite being meaning-preserving. reverseMappings
documents exactly one case where it is not — a mapping with duplicate keys, whose
meaning depends on the order being changed — and excludes it.

There are at least three more, and none is excluded. In each the permuted source
is not the same document spelled differently, so the two compiles differ for a
reason that is not a defect, and the oracle attributes it to the compiler.

All three are latent: no committed spec reaches any of them, and the corpus sweep
is green. They surface the moment a spec using one of these spellings is
committed, or the oracle is driven by generated input.

1. Flow-style implicit null is not preserved

openapi: 3.0.0
info: {title: 0, version: 0}
components:
  schemas:
    0:
      allOf:
        - {A}

{A} is a flow mapping whose value is an implicit null. yaml.Marshal re-emits
it as {A: ''}, so the second compile sees an empty string where the first saw
null. The unmodeled residue kept for the allOf branch differs accordingly —
{"A":null} against {"A":""} — and the oracle reports the type registry as
order-dependent.

Block style is unaffected: a:\n A:\n round-trips with the null intact. Only
the flow spelling is rewritten.

2. Reversing a mapping can move an alias above its anchor

openapi: 3.0.0
info: {title: 0, version: 0}
0: &m
1: *m

Reversed, 1: *m precedes 0: &m. YAML requires an anchor to be defined before
it is referenced, so the permuted document does not parse:
yaml: unknown anchor 'm' referenced. The oracle reports the parse failure as
order dependence.

3. diagnosticSet compares a field that is allowed to be positional

openapi: 3.0.0
info: {title: 0, version: 0}
paths:
  0:
    0:
      responses:
        0:
          description: 0
      callbacks:
        0:
          0:
            description:

The two orders produce the same finding at two provenances:

- "warning\x00openapi/validation/validation-invalid-format\x0011:21\x000"
+ "warning\x00openapi/validation/validation-invalid-format\x006:21\x000"

diagnosticSet keys on Provenance.Pointer to identify a finding independently
of the order diagnostics were appended in. But ir/provenance.go:22 documents
that field as holding "a JSON pointer or line:col", and
compilers/openapi/internal/load/load.go:432 writes line:col for a
reference-resolution failure. A permutation moves the offending node to a
different line, so the value changes by design.

The same function already excludes Message for exactly this reason — some
messages enumerate source keywords in source order — and the reasoning applies
unchanged to a positional pointer.

Expected

A source the rewrite cannot faithfully permute is skipped, as a duplicate-key
source already is, and the identity a diagnostic is compared on does not include
a value that moves with the source.

Two fixes were tried against the corpus and keep it green:

  • For 1, compile both arms through the same encoder. The baseline becomes
    yaml.Marshal(parse(src)) rather than src, so a spelling the encoder does
    not preserve changes both sides alike and cannot read as order dependence.
  • For 2, re-parse the permuted bytes and treat a parse failure as "not faithfully
    permutable" — ok=false, the same exit the duplicate-key case takes. This
    covers anchor ordering without enumerating it, and any later YAML rule of the
    same kind.

3 needs a decision rather than a mechanism: either drop Pointer from the
compared identity, or compare it only when it is a JSON pointer.

Each case above is a reproducer for a fuzz target driving harness.Check — worth
adding regardless, since order-invariance is the one oracle no committed fuzz
target applies.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions