Skip to content

Commit 935d78f

Browse files
authored
Merge commit from fork
`expand_` recurses once per level of brace *nesting*, in two places: once per comma member of a set, and once when re-wrapping a set whose body parses to a single part (`x{{a,b}}y` -> `x{a}y x{b}y`). Deep nesting exhausted the native stack and crashed the process: expand('{'.repeat(3200) + 'a,b' + '}'.repeat(3200)) // RangeError: Maximum call stack size exceeded That is about 6KB of input - the cheapest stack-exhaustion payload known against this package, and roughly a tenth of minimatch's MAX_PATTERN_LENGTH. The comma-member shape crashes at ~15.6KB. The CVE-2026-14257 fix made the *tail* iterative - recursion on `m.post`, one level per chained group - so chained input was already safe. Nesting drives a different recursion that the tail fix never touched, which is why `'{a,b}'.repeat(n)` is fine while `'{'.repeat(n) + 'a,b' + '}'.repeat(n)` is not. Neither `max` nor `maxLength` could bound it: both crashes happen while recursing into sub-expansions, before the result set grows. The payloads expand to almost nothing - the single-set shape yields 2 results - so neither bound is ever the limiter. Thread a `maxDepth` bound (default `EXPANSION_MAX_DEPTH`, 1000) through `expand_`. Past the bound a group is treated as non-expanding and returned literally, which is how the parser already handles a group it cannot expand. Truncating rather than throwing keeps `expand` total, matching `max` and `maxLength`. The default sits far above any realistic nesting depth and roughly 3x below the depth at which the stack runs out. Verified equivalent to 5.0.9 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 df7682f commit 935d78f

2 files changed

Lines changed: 100 additions & 4 deletions

File tree

‎src/index.ts‎

Lines changed: 37 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,16 @@ export const EXPANSION_MAX = 100_000
3030
// characters) so legitimate input is unaffected.
3131
export const EXPANSION_MAX_LENGTH = 4_000_000
3232

33+
// `expand_` recurses once per level of brace *nesting* - both when expanding a
34+
// set's comma members and when re-wrapping a set whose body is a single part.
35+
// The CVE-2026-14257 fix made the *tail* iterative (recursion on `m.post`, one
36+
// level per chained group), which left nesting depth unbounded: about 3,100
37+
// levels of `{{{...a,b...}}}` - only ~6KB of input - exhausted the native stack
38+
// and crashed the process. `EXPANSION_MAX_DEPTH` bounds how deep the parser
39+
// will follow nesting. It sits far above any realistic pattern and well below
40+
// the depth at which the stack runs out.
41+
export const EXPANSION_MAX_DEPTH = 1_000
42+
3343
function numeric(str: string) {
3444
return !isNaN(str as any) ? parseInt(str, 10) : str.charCodeAt(0)
3545
}
@@ -104,14 +114,19 @@ function parseCommaParts(str: string) {
104114
export type BraceExpansionOptions = {
105115
max?: number
106116
maxLength?: number
117+
maxDepth?: number
107118
}
108119

109120
export function expand(str: string, options: BraceExpansionOptions = {}) {
110121
if (!str) {
111122
return []
112123
}
113124

114-
const { max = EXPANSION_MAX, maxLength = EXPANSION_MAX_LENGTH } = options
125+
const {
126+
max = EXPANSION_MAX,
127+
maxLength = EXPANSION_MAX_LENGTH,
128+
maxDepth = EXPANSION_MAX_DEPTH,
129+
} = options
115130

116131
// I don't know why Bash 4.3 does this, but it does.
117132
// Anything starting with {} will have the first two bytes preserved
@@ -123,7 +138,7 @@ export function expand(str: string, options: BraceExpansionOptions = {}) {
123138
str = '\\{\\}' + str.slice(2)
124139
}
125140

126-
return expand_(escapeBraces(str), max, maxLength, true).map(
141+
return expand_(escapeBraces(str), max, maxLength, maxDepth, 0, true).map(
127142
unescapeBraces,
128143
)
129144
}
@@ -239,8 +254,17 @@ function expand_(
239254
str: string,
240255
max: number,
241256
maxLength: number,
257+
maxDepth: number,
258+
depth: number,
242259
isTop: boolean,
243260
): string[] {
261+
// Too deeply nested to keep following: treat the rest as literal, the same
262+
// way a group that cannot expand is already handled. Truncating rather than
263+
// throwing keeps `expand` total, matching `max` and `maxLength`.
264+
if (depth > maxDepth) {
265+
return [str]
266+
}
267+
244268
// Consume the string's top-level brace groups left to right, threading a
245269
// running set of combined prefixes (`acc`). Expanding the tail iteratively -
246270
// rather than recursing on `m.post` once per group - keeps the native stack
@@ -318,7 +342,9 @@ function expand_(
318342
let n = parseCommaParts(m.body)
319343
if (n.length === 1 && n[0] !== undefined) {
320344
// x{{a,b}}y ==> x{a}y x{b}y
321-
n = expand_(n[0], max, maxLength, false).map(embrace)
345+
n = expand_(n[0], max, maxLength, maxDepth, depth + 1, false).map(
346+
embrace,
347+
)
322348
//XXX is this necessary? Can't seem to hit it in tests.
323349
/* c8 ignore start */
324350
if (n.length === 1) {
@@ -352,7 +378,14 @@ function expand_(
352378
values = []
353379
let valuesLength = 0
354380
outer: for (let j = 0; j < n.length; j++) {
355-
const expanded = expand_(n[j] as string, max, maxLength, false)
381+
const expanded = expand_(
382+
n[j] as string,
383+
max,
384+
maxLength,
385+
maxDepth,
386+
depth + 1,
387+
false,
388+
)
356389
for (let k = 0; k < expanded.length; k++) {
357390
const v = expanded[k] as string
358391
if (dropsEmpties && !v) continue

‎test/index.js‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -258,6 +258,69 @@ t.test('deep chaining does not overflow the stack', async t => {
258258
})
259259
})
260260

261+
// The tail fix above bounds stack depth for *chained* groups. Nesting drives a
262+
// different recursion - one level per `{` for a set's comma members, and one
263+
// for a set whose body is a single part - which stayed unbounded. Only ~6KB of
264+
// `{{{...a,b...}}}` was enough to exhaust the stack.
265+
t.test('deep nesting does not overflow the stack', async t => {
266+
// A set nested inside every comma member.
267+
const members = '{a,'.repeat(10_000) + 'z' + '}'.repeat(10_000)
268+
t.doesNotThrow(() => {
269+
t.ok(expand(members).length > 0, 'comma members still return a result')
270+
})
271+
272+
// A set whose body parses to a single part, nested all the way down. This is
273+
// the cheapest payload: it crashed at ~3,100 levels, about 6KB of input.
274+
const single = '{'.repeat(10_000) + 'a,b' + '}'.repeat(10_000)
275+
t.doesNotThrow(() => {
276+
t.ok(expand(single).length > 0, 'single set still returns a result')
277+
})
278+
279+
// Neither bound could prevent this - the payloads expand to almost nothing,
280+
// so the result set never reaches either limit.
281+
t.doesNotThrow(
282+
() => expand(single, { max: 1, maxLength: 1 }),
283+
'still safe with both output bounds at their lowest',
284+
)
285+
})
286+
287+
t.test('maxDepth option bounds nesting depth', async t => {
288+
// The bound counts levels of nesting followed, so a flat set never needs any:
289+
// its members are literals, and expanding them is what would recurse.
290+
t.strictSame(expand('{a,b}', { maxDepth: 0 }), ['a', 'b'])
291+
292+
// Each further level costs one. Below the bound the result is exactly what an
293+
// unbounded expansion produces.
294+
for (const str of [
295+
'{a,b}',
296+
'{{a,b}}',
297+
'{{{a,b}}}',
298+
'{a,{b,c}}',
299+
'{a,{b,{c,d}}}',
300+
'x{{a,b}}y',
301+
]) {
302+
t.strictSame(
303+
expand(str, { maxDepth: 50 }),
304+
expand(str),
305+
`${str} is unchanged below the bound`,
306+
)
307+
}
308+
309+
// Past it, the group stops expanding and comes back literal rather than
310+
// throwing - the same way a group that cannot expand is already handled.
311+
t.strictSame(expand('{{a,b}}', { maxDepth: 0 }), ['{{a,b}}'])
312+
t.strictSame(expand('{{{a,b}}}', { maxDepth: 1 }), ['{{{a,b}}}'])
313+
t.strictSame(expand('x{{a,b}}y', { maxDepth: 0 }), ['x{{a,b}}y'])
314+
315+
// Partially: the levels within the bound still expand.
316+
t.strictSame(expand('{a,{b,c}}', { maxDepth: 0 }), ['a', '{b,c}'])
317+
t.strictSame(expand('{a,{b,{c,d}}}', { maxDepth: 1 }), [
318+
'a',
319+
'b',
320+
'{c,d}',
321+
])
322+
})
323+
261324
// The same guarantee for the *parsing* side. `parseCommaParts` recursed on the
262325
// remainder of the string once per brace group, so chaining groups inside a
263326
// brace set exhausted the stack at ~7,000 groups (~29KB of input) even though

0 commit comments

Comments
 (0)