Skip to content

Commit ffdfa3e

Browse files
juliangruberjuliangruber
authored
Merge commit from fork
Bash keeps a quirk where a brace group followed by a comma set still expands (`{a},b}`). The parser implements it by rewriting the string and restarting the scan, absorbing one `}` per pass, so `n` trailing braces cost `n` full passes: expand('{a}' + '}'.repeat(128000) + ',z}') // 27.7 seconds, 2 results `ms/n^2` is flat and each doubling of `n` costs 4x - quadratic. There is a second multiplier: each rewrite replaces the group's closing `}` with the `escClose` sentinel, ~25 characters, so the working string grows by ~25 characters per pass. A 1KB input becomes 26KB, and that ~26x factor multiplies both the constant and peak memory. Neither `max` nor `maxLength` could bound it: the cost is in parsing, before the result set exists, and the payload yields two results at any size. Bound the number of times the scan may restart (`maxRewrites`, default `EXPANSION_MAX_REWRITES`, 1000). Past the bound the remaining string is treated as non-expanding and returned literally, consistent with `max` and `maxLength`, which truncate rather than throw. This bounds the number of passes, not the cost of each, so worst-case work is proportional to `bound x input length` rather than `n x input length`. Spending the whole budget on a 1MB input measures ~350ms, the same as before the change for that shape; the quadratic shape drops from 27.7s to ~50ms at n=128,000. Real `{a},b}` input needs a handful of passes - the existing 30-group regression test for GHSA-3jxr-9vmj-r5cp is far under the bound. Verified equivalent to the published release for input below the bound by differential testing: exhaustive over every string of `{`, `}`, `,` and `a` up to length 8, plus 300k random inputs with and without `max` / `maxLength` - 387,381 cases, zero mismatches.
1 parent c6513ad commit ffdfa3e

2 files changed

Lines changed: 70 additions & 4 deletions

File tree

‎index.js‎

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,16 @@ var EXPANSION_MAX_LENGTH = 4000000
3333
// the depth at which the stack runs out.
3434
var EXPANSION_MAX_DEPTH = 1000
3535

36+
// Bash keeps a quirk where a brace group followed by a comma set still expands
37+
// (`{a},b}`). The parser implements it by rewriting the string and restarting
38+
// the scan, absorbing one `}` per pass. `n` trailing braces therefore cost `n`
39+
// full passes over a string that itself grows by one `escClose` sentinel each
40+
// time - quadratic in `n`, with a ~26x constant from the sentinel's length.
41+
// 128KB of `'{a}' + '}'.repeat(n) + ',z}'` blocked the event loop for 27
42+
// seconds to produce two results. `EXPANSION_MAX_REWRITES` bounds how many
43+
// times the scan may restart. Real `{a},b}` input needs a handful.
44+
var EXPANSION_MAX_REWRITES = 1000
45+
3646
function numeric(str) {
3747
return parseInt(str, 10) == str
3848
? parseInt(str, 10)
@@ -114,6 +124,7 @@ function expandTop(str, options) {
114124
var max = options.max == null ? EXPANSION_MAX : options.max;
115125
var maxLength = options.maxLength == null ? EXPANSION_MAX_LENGTH : options.maxLength;
116126
var maxDepth = options.maxDepth == null ? EXPANSION_MAX_DEPTH : options.maxDepth;
127+
var maxRewrites = options.maxRewrites == null ? EXPANSION_MAX_REWRITES : options.maxRewrites;
117128

118129
// I don't know why Bash 4.3 does this, but it does.
119130
// Anything starting with {} will have the first two bytes preserved
@@ -125,7 +136,7 @@ function expandTop(str, options) {
125136
str = '\\{\\}' + str.substr(2);
126137
}
127138

128-
return expand(escapeBraces(str), max, maxLength, maxDepth, 0, true).map(unescapeBraces);
139+
return expand(escapeBraces(str), max, maxLength, maxDepth, 0, maxRewrites, true).map(unescapeBraces);
129140
}
130141

131142
function identity(e) {
@@ -251,6 +262,7 @@ function expand(
251262
maxLength,
252263
maxDepth,
253264
depth,
265+
maxRewrites,
254266
isTop
255267
) {
256268
// Too deeply nested to keep following: treat the rest as literal, the same
@@ -280,6 +292,9 @@ function expand(
280292
// `accBase[a]` records how much of `acc[a]` predates the current run;
281293
// `combine` treats an expansion as empty when it adds nothing past that.
282294
var accBase = [0]
295+
// How many times the `{a},b}` rewrite below has restarted the scan. Each pass
296+
// re-reads the whole string, so leaving this unbounded is quadratic.
297+
var rewrites = 0
283298
var dropEmpties = false
284299
var firstGroup = true
285300
var nextBase
@@ -311,7 +326,8 @@ function expand(
311326
var isOptions = m.body.indexOf(',') >= 0;
312327
if (!isSequence && !isOptions) {
313328
// {a},b}
314-
if (m.post.match(/,(?!,).*\}/)) {
329+
if (rewrites < maxRewrites && m.post.match(/,(?!,).*\}/)) {
330+
rewrites++;
315331
str = m.pre + '{' + m.body + escClose + m.post;
316332
// The rewritten string is expanded as if it were a fresh top-level one,
317333
// so start a new empty-drop run: anchor the baseline at what `acc`
@@ -350,7 +366,7 @@ function expand(
350366
var n = parseCommaParts(m.body);
351367
if (n.length === 1 && n[0] !== undefined) {
352368
// x{{a,b}}y ==> x{a}y x{b}y
353-
n = expand(n[0], max, maxLength, maxDepth, depth + 1, false).map(embrace);
369+
n = expand(n[0], max, maxLength, maxDepth, depth + 1, maxRewrites, false).map(embrace);
354370
//XXX is this necessary? Can't seem to hit it in tests.
355371
/* c8 ignore start */
356372
if (n.length === 1) {
@@ -389,7 +405,7 @@ function expand(
389405
values = []
390406
var valuesLength = 0
391407
outer: for (var j = 0; j < n.length; j++) {
392-
var expanded = expand(n[j], max, maxLength, maxDepth, depth + 1, false)
408+
var expanded = expand(n[j], max, maxLength, maxDepth, depth + 1, maxRewrites, false)
393409
for (var k = 0; k < expanded.length; k++) {
394410
var v = expanded[k]
395411
if (dropsEmpties && !v) continue

‎test/ghsa-q2hr-2g5m-vwhr.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
var test = require('tape');
2+
var expand = require('..');
3+
4+
// Bash keeps a quirk where a brace group followed by a comma set still expands
5+
// (`{a},b}`). The parser rewrites the string and restarts the scan, absorbing
6+
// one `}` per pass, so `n` trailing braces cost `n` passes over a string that
7+
// itself grows by one `escClose` sentinel each time - quadratic in `n`. 128KB
8+
// of this shape blocked the event loop for 27 seconds to produce 2 results.
9+
test('the {a},b} rewrite does not run in quadratic time', function (t) {
10+
var build = function (n) { return '{a}' + '}'.repeat(n) + ',z}' }
11+
12+
var startTime = performance.now()
13+
expand(build(128000))
14+
var elapsed = performance.now() - startTime
15+
t.ok(elapsed < 2000, 'Expected time (' + elapsed + 'ms) to be less than 2000ms')
16+
17+
// Neither output bound applies: the payload yields a couple of results at any
18+
// size, so the cost is all in parsing.
19+
t.doesNotThrow(function () { expand(build(128000), { max: 1, maxLength: 1 }) })
20+
21+
t.end();
22+
})
23+
24+
test('maxRewrites option bounds the rescan count', function (t) {
25+
var build = function (n) { return '{a}' + '}'.repeat(n) + ',z}' }
26+
27+
// Real `{a},b}` input needs a handful of passes, and is untouched.
28+
t.deepEqual(expand('{a},b}'), ['a}', 'b'])
29+
t.deepEqual(expand('a{},b}c'), ['a}c', 'abc'])
30+
31+
// Below the bound the result matches an unbounded expansion exactly.
32+
var ns = [1, 10, 100]
33+
for (var i = 0; i < ns.length; i++) {
34+
t.deepEqual(
35+
expand(build(ns[i]), { maxRewrites: 1000 }),
36+
expand(build(ns[i]), { maxRewrites: 100000 }),
37+
ns[i] + ' trailing braces are unchanged below the bound'
38+
)
39+
}
40+
41+
// Past it the scan stops restarting and the rest stays literal, rather than
42+
// throwing - the same way `max` and `maxLength` truncate.
43+
t.deepEqual(expand('{a},b}', { maxRewrites: 0 }), ['{a},b}'])
44+
t.ok(
45+
expand(build(50), { maxRewrites: 10 })[0].indexOf('{a}') === 0,
46+
'past the bound the group comes back literal'
47+
)
48+
49+
t.end();
50+
})

0 commit comments

Comments
 (0)