v0.38: building a single-line (minified JSON) document is O(n²) in MapNodes

[s04]

Summary

Since v0.38.0, building a document whose spec is minified JSON (whole document on one line) takes minutes instead of seconds. An 8 MB single-line OpenAPI 3.1 spec with ~700k YAML nodes pins one CPU core at 100% inside index.addNodeLineEntry and does not finish within 4+ minutes. The same file builds in ~1.5 s on v0.37.3.

Cause

Commit 4a22282 (v0.38.0) replaced the per-line map[int]*yaml.Node in index/map_index_nodes.go with a slice per line that is scanned linearly on every insert and lookup:

// nodeLineEntry is a single (column, node) pair on one line of the spec. Lines hold very
// few nodes, so a small slice scanned linearly is far cheaper than a per-line map.

That assumption holds for YAML but not for minified JSON, where every node has Line == 1. Each insert then scans every node already on that line, so MapNodes is O(n²) in the node count. A CPU profile of a 45 s run shows 94% of samples in addNodeLineEntry:

      flat  flat%   sum%        cum   cum%
    36.49s 93.66% 93.66%     38.20s 98.05%  github.com/pb33f/libopenapi/index.addNodeLineEntry
         0     0% 98.31%     38.21s 98.07%  github.com/pb33f/libopenapi/index.(*SpecIndex).MapNodes
         0     0% 98.31%     38.21s 98.07%  github.com/pb33f/libopenapi/index.mapNodesRecursive

lookupNodeLines has the same linear cost per GetNode call, which also affects FindNodeOrigin and the KeyNode lookup in extract_refs_lookup.go.

Reproduction

Any large spec published as compact JSON triggers it. Cloudflare's public spec is one example (fetch it and strip newlines, or use an older minified release):

data, _ := os.ReadFile("cloudflare-minified.json") // one line, ~8 MB
doc, _ := libopenapi.NewDocument(data)
model, err := doc.BuildV3Model() // never returns in a reasonable time on v0.38.x

A synthetic reproduction is in the PR's BenchmarkSpecIndex_MapNodes_SingleLine (20k schemas, ~200k nodes on one line):

	ns/op
origin/main (v0.38.7)	101,835,604,666 (~102 s)
with fix	301,491,542 (~0.3 s)

None of ExtractRefsSequentially, SkipCircularReferenceCheck, SkipMetadataCollection, or UseSchemaQuickHash avoid it, since MapNodes runs regardless.

Environment

• libopenapi v0.38.7 (also reproduced at v0.38.0 tag range via git tag --contains 4a22282)
• Go 1.26, darwin/arm64

Fix

PR incoming: append-only inserts, one stable sort per line by column when MapNodes finishes (collapsing duplicate columns with last-write-wins, preserving the existing parent-wins semantics), and binary-search lookups. The [][]nodeLineEntry type and its call sites are unchanged.