Skip to content

ir: IsSubtype walks the hierarchy afresh per call, so its callers go quadratic #850

Closed

Description

@OmarAlJarrah

Problem

ir.IsSubtype walks the target's supertypes from scratch on every call, so code that asks it once per route of a discriminator does work proportional to routes × hierarchy depth. pass/validate asks it for every mapping target of every model discriminator (checkModelDiscriminator). A generated document with N models, each mapping to the bottom of an N-deep allOf chain, validates in time quadratic in its size:

# N chained models, then N discriminated bases that each map to the deepest one
D = K = N
print("openapi: 3.1.0\ninfo: {title: t, version: '1'}\npaths: {}\ncomponents:\n  schemas:")
print("    C0: {type: object, properties: {kind: {type: string}}}")
for i in range(1, D + 1):
    print(f"    C{i}: {{allOf: [{{$ref: '#/components/schemas/C{i-1}'}}], type: object}}")
for k in range(K):
    print(f"    M{k}: {{type: object, discriminator: {{propertyName: kind, mapping: {{x: '#/components/schemas/C{D}'}}}}}}")
N morphic validate --disable-pass validate
1000 0.28 s 0.14 s
2000 0.79 s 0.28 s
4000 2.61 s 0.57 s

Measured on main at a2530c37. The lowering is linear; the pass roughly triples with each doubling.

#808 adds a second caller. The OpenAPI compiler settles a discriminator beside a kept union by asking ir.IsSubtype of each route, union branches included. A document whose N degraded models each name the bottom of the chain as a branch shows the same curve inside the compile.

Expected

Asking whether many types are subtypes of a base costs time linear in the hierarchy plus the number of questions. Two shapes would do it:

  • A per-document index built once (ir.SubtypeIndex or similar) that answers IsSubtype from memoized supertype closures, or from DFS intervals where each type has one supertype. A DAG with Implements needs the general form.
  • Callers group their questions by base and walk down once from the base over a reverse Base index.

Either one must answer exactly what IsSubtype answers today, cycles and alias reads included. That is easiest to guarantee by making IsSubtype itself the index's thin wrapper rather than a second implementation.

Acceptance

  • Validating the generated document grows linearly with N, measured as work counted rather than wall-clock.
  • Both callers go through the same implementation.

Activity

  1. added
    priority:P4Refactors, tests, CI, hostile-input hardening, cosmetic diagnostics, other formats
    on Oct 19, 2026
  2. OmarAlJarrah commented on Oct 19, 2026

    @OmarAlJarrah
    MemberAuthor

    Measured again at c387e25c, through the spec route and without errors:

    • Error-free variant. Putting a discriminator on every model of the chain, each mapping to the deepest one, compiles with exit 0 and no diagnostics. It still makes N(N+1)/2 IsSubtype iterations, 4.00× per doubling.

    • The issue's own generator. The instructions retired by morphic validate minus those of --disable-pass validate:

      N Instructions attributable to Validate
      1,000 2.94 G
      2,000 11.66 G
      4,000 38.2 G

      The compile without the pass is linear (3.78 G, 7.15 G, 14.6 G).

    Reach is small today:

    • The golden spec (the Cloudflare API schema, cloudflare/api-schemas openapi.json at 911ad78) makes 0 IsSubtype calls.
    • 152 of 1,839 compiled documents make any, and none makes more than 6.

    #950 proposes the per-document index this issue's first shape describes, as the home for every derived fact, not subtypes alone.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    priority:P4Refactors, tests, CI, hostile-input hardening, cosmetic diagnostics, other formatstype:bugDefect in shipped behavior

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions