openapi: file-name chains into one wide mapping of the source take quadratic time #775

Problem

With allow-external-refs=true, a schema $ref that names the source by its file name (root.yaml#/x-lib/C1) is read in the source's tree. There, jsonpointer.GetTarget finds a key by comparing the keys of the mapping that holds it, in order. Two readers repeat that read for every hop and charge it by the hop, whatever the mapping's width:

• loops.read (openapi: a $ref cycle closing through the source's own file name overflows the stack #768) reads each hop of such a chain in the tree twice, once in readAt's check that the tree holds the pointer and once in readHop. It counts one hop against maxLoopReads (2¹⁸).
• mappings.chainEnds reads a mapping target's hops the same way, for one step each of maxMappingWork.

So n chains into one mapping of n keys take time quadratic in n, bounded only by hop counts. #774 (for #773) prices the same reads where settle resumes a chain in another document's tree, by the keys they compare (treeReads). These readers read the source and resume nothing, so it leaves them as they are.

Reproduction

Verified at 25bdace. gen.py writes root.yaml, whose schemas each name an entry of its own x-lib by the file name, and each entry names another in the same mapping:

import sys
n = int(sys.argv[1])
root = ["openapi: 3.1.0", "info: {title: T, version: '1'}", "paths: {}", "components:", "  schemas:"]
root += [f"    S{i}: {{$ref: 'root.yaml#/x-lib/C{i}'}}" for i in range(n)]
root += ["x-lib:"]
root += [f"  C{i}: {{$ref: '#/x-lib/D{i}'}}" for i in range(n)]
root += [f"  D{i}: {{type: object}}" for i in range(n)]
open("root.yaml", "w").write("\n".join(root) + "\n")

python3 gen.py 20000, then /usr/bin/time -l morphic validate root.yaml --opt allow-external-refs=true (macOS). The last column is a build of 25bdace whose loops.read returns at once:

With references off, each file-name $ref is refused (external reference not allowed). With them on, every chain resolves and nothing is reported. The branch of #774 times the same (13.35 s at 20,000) and reports no budget crossed.

Cause

loops accounts for about a third of the time at 20,000 chains, which the last column shows. Without it, the rest still grows faster than linearly. This issue does not break the rest down.

Proposal

Price the tree reads loops.readAt and mappings.readAt make with treeReads (#774), and charge their budgets in keys rather than hops. readAt's existence check could reuse readHop's read instead of making its own. Then profile what remains before deciding whether the resolver's own reads of these hops need a bound.

Acceptance

• The keys loops and chainEnds compare when they read the source's tree are charged against a bound.
• 20,000 file-name chains into one mapping either finish within a small factor of the references-off time, or stop at a bound with a diagnostic that says so.

Update: where the time goes

A single-threaded CPU profile (GOMAXPROCS=1, runtime/pprof in a standalone program) of the 20,000-chain run at 25bdace, 13.4 s in all:

So this issue covers loops and mappings.chainEnds. The library's own reads are out of reach here.