Skip to content

Commit 7614360

Browse files
committed
Co-authored-by: Copilot <[email protected]> Copilot-Session: 51629aea-67ec-442e-9b0f-9b0f88b74fea
1 parent 83ea1a1 commit 7614360

4 files changed

Lines changed: 175 additions & 86 deletions

File tree

‎node_modules/brace-expansion/dist/commonjs/index.js‎

Lines changed: 69 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
"use strict";
22
Object.defineProperty(exports, "__esModule", { value: true });
3-
exports.EXPANSION_MAX_LENGTH = exports.EXPANSION_MAX = void 0;
3+
exports.EXPANSION_MAX_REWRITES = exports.EXPANSION_MAX_DEPTH = exports.EXPANSION_MAX_LENGTH = exports.EXPANSION_MAX = void 0;
44
exports.expand = expand;
55
const balanced_match_1 = require("balanced-match");
66
const escSlash = '\0SLASH' + Math.random() + '\0';
@@ -30,6 +30,24 @@ exports.EXPANSION_MAX = 100_000;
3030
// realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M
3131
// characters) so legitimate input is unaffected.
3232
exports.EXPANSION_MAX_LENGTH = 4_000_000;
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+
exports.EXPANSION_MAX_DEPTH = 1_000;
42+
// Bash keeps a quirk where a brace group followed by a comma set still expands
43+
// (`{a},b}`). The parser implements it by rewriting the string and restarting
44+
// the scan, absorbing one `}` per pass. `n` trailing braces therefore cost `n`
45+
// full passes over a string that itself grows by one `escClose` sentinel each
46+
// time - quadratic in `n`, with a ~26x constant from the sentinel's length.
47+
// 128KB of `'{a}' + '}'.repeat(n) + ',z}'` blocked the event loop for 27
48+
// seconds to produce two results. `EXPANSION_MAX_REWRITES` bounds how many
49+
// times the scan may restart. Real `{a},b}` input needs a handful.
50+
exports.EXPANSION_MAX_REWRITES = 1_000;
3351
function numeric(str) {
3452
return !isNaN(str) ? parseInt(str, 10) : str.charCodeAt(0);
3553
}
@@ -49,37 +67,52 @@ function unescapeBraces(str) {
4967
.replace(escCommaPattern, ',')
5068
.replace(escPeriodPattern, '.');
5169
}
70+
// Like `target.push(...items)` but doesn't overflow the stack
71+
function pushAll(target, items) {
72+
for (let i = 0; i < items.length; i++) {
73+
target.push(items[i]);
74+
}
75+
}
5276
/**
5377
* Basically just str.split(","), but handling cases
5478
* where we have nested braced sections, which should be
5579
* treated as individual members, like {a,{b,c},d}
5680
*/
5781
function parseCommaParts(str) {
58-
if (!str) {
59-
return [''];
60-
}
6182
const parts = [];
62-
const m = (0, balanced_match_1.balanced)('{', '}', str);
63-
if (!m) {
64-
return str.split(',');
65-
}
66-
const { pre, body, post } = m;
67-
const p = pre.split(',');
68-
p[p.length - 1] += '{' + body + '}';
69-
const postParts = parseCommaParts(post);
70-
if (post.length) {
71-
;
72-
p[p.length - 1] += postParts.shift();
73-
p.push.apply(p, postParts);
83+
// Walk the brace groups iteratively. Recursing on `post` once per group let a
84+
// chain of them exhaust the stack - the parsing-side counterpart to
85+
// the `expand_` overflow fixed for CVE-2026-14257, and not something `max` or
86+
// `maxLength` can bound, since it happens before expansion.
87+
//
88+
// The part the next chunk continues
89+
let carry = '';
90+
for (;;) {
91+
const m = (0, balanced_match_1.balanced)('{', '}', str);
92+
if (!m) {
93+
const tail = str.split(',');
94+
tail[0] = carry + tail[0];
95+
pushAll(parts, tail);
96+
return parts;
97+
}
98+
const { pre, body, post } = m;
99+
const p = pre.split(',');
100+
p[0] = carry + p[0];
101+
p[p.length - 1] += '{' + body + '}';
102+
if (!post.length) {
103+
pushAll(parts, p);
104+
return parts;
105+
}
106+
carry = p.pop();
107+
pushAll(parts, p);
108+
str = post;
74109
}
75-
parts.push.apply(parts, p);
76-
return parts;
77110
}
78111
function expand(str, options = {}) {
79112
if (!str) {
80113
return [];
81114
}
82-
const { max = exports.EXPANSION_MAX, maxLength = exports.EXPANSION_MAX_LENGTH } = options;
115+
const { max = exports.EXPANSION_MAX, maxLength = exports.EXPANSION_MAX_LENGTH, maxDepth = exports.EXPANSION_MAX_DEPTH, maxRewrites = exports.EXPANSION_MAX_REWRITES, } = options;
83116
// I don't know why Bash 4.3 does this, but it does.
84117
// Anything starting with {} will have the first two bytes preserved
85118
// but *only* at the top level, so {},a}b will not expand to anything,
@@ -89,7 +122,7 @@ function expand(str, options = {}) {
89122
if (str.slice(0, 2) === '{}') {
90123
str = '\\{\\}' + str.slice(2);
91124
}
92-
return expand_(escapeBraces(str), max, maxLength, true).map(unescapeBraces);
125+
return expand_(escapeBraces(str), max, maxLength, maxDepth, 0, maxRewrites, true).map(unescapeBraces);
93126
}
94127
function embrace(str) {
95128
return '{' + str + '}';
@@ -184,7 +217,13 @@ function expandSequence(body, isAlphaSequence, max, maxLength) {
184217
}
185218
return N;
186219
}
187-
function expand_(str, max, maxLength, isTop) {
220+
function expand_(str, max, maxLength, maxDepth, depth, maxRewrites, isTop) {
221+
// Too deeply nested to keep following: treat the rest as literal, the same
222+
// way a group that cannot expand is already handled. Truncating rather than
223+
// throwing keeps `expand` total, matching `max` and `maxLength`.
224+
if (depth > maxDepth) {
225+
return [str];
226+
}
188227
// Consume the string's top-level brace groups left to right, threading a
189228
// running set of combined prefixes (`acc`). Expanding the tail iteratively -
190229
// rather than recursing on `m.post` once per group - keeps the native stack
@@ -196,6 +235,9 @@ function expand_(str, max, maxLength, isTop) {
196235
// comma set - a sequence like `{a..\}` may legitimately yield ''. The drop
197236
// is on the final strings, so it is applied to whichever `combine` produces
198237
// them (the one with no brace set left in the tail).
238+
// How many times the `{a},b}` rewrite below has restarted the scan. Each pass
239+
// re-reads the whole string, so leaving this unbounded is quadratic.
240+
let rewrites = 0;
199241
let dropEmpties = false;
200242
let firstGroup = true;
201243
for (;;) {
@@ -220,7 +262,8 @@ function expand_(str, max, maxLength, isTop) {
220262
const isOptions = m.body.indexOf(',') >= 0;
221263
if (!isSequence && !isOptions) {
222264
// {a},b}
223-
if (m.post.match(/,(?!,).*\}/)) {
265+
if (rewrites < maxRewrites && m.post.match(/,(?!,).*\}/)) {
266+
rewrites++;
224267
str = m.pre + '{' + m.body + escClose + m.post;
225268
isTop = true;
226269
continue;
@@ -240,7 +283,7 @@ function expand_(str, max, maxLength, isTop) {
240283
let n = parseCommaParts(m.body);
241284
if (n.length === 1 && n[0] !== undefined) {
242285
// x{{a,b}}y ==> x{a}y x{b}y
243-
n = expand_(n[0], max, maxLength, false).map(embrace);
286+
n = expand_(n[0], max, maxLength, maxDepth, depth + 1, maxRewrites, false).map(embrace);
244287
//XXX is this necessary? Can't seem to hit it in tests.
245288
/* c8 ignore start */
246289
if (n.length === 1) {
@@ -266,12 +309,13 @@ function expand_(str, max, maxLength, isTop) {
266309
values = [];
267310
let valuesLength = 0;
268311
outer: for (let j = 0; j < n.length; j++) {
269-
const expanded = expand_(n[j], max, maxLength, false);
312+
const expanded = expand_(n[j], max, maxLength, maxDepth, depth + 1, maxRewrites, false);
270313
for (let k = 0; k < expanded.length; k++) {
271314
const v = expanded[k];
272315
if (dropsEmpties && !v)
273316
continue;
274-
if (values.length >= max || valuesLength + v.length > maxLength) {
317+
if (values.length >= max ||
318+
valuesLength + v.length > maxLength) {
275319
break outer;
276320
}
277321
values.push(v);

‎node_modules/brace-expansion/dist/esm/index.js‎

Lines changed: 68 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,24 @@ export const EXPANSION_MAX = 100_000;
2626
// realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M
2727
// characters) so legitimate input is unaffected.
2828
export const EXPANSION_MAX_LENGTH = 4_000_000;
29+
// `expand_` recurses once per level of brace *nesting* - both when expanding a
30+
// set's comma members and when re-wrapping a set whose body is a single part.
31+
// The CVE-2026-14257 fix made the *tail* iterative (recursion on `m.post`, one
32+
// level per chained group), which left nesting depth unbounded: about 3,100
33+
// levels of `{{{...a,b...}}}` - only ~6KB of input - exhausted the native stack
34+
// and crashed the process. `EXPANSION_MAX_DEPTH` bounds how deep the parser
35+
// will follow nesting. It sits far above any realistic pattern and well below
36+
// the depth at which the stack runs out.
37+
export const EXPANSION_MAX_DEPTH = 1_000;
38+
// Bash keeps a quirk where a brace group followed by a comma set still expands
39+
// (`{a},b}`). The parser implements it by rewriting the string and restarting
40+
// the scan, absorbing one `}` per pass. `n` trailing braces therefore cost `n`
41+
// full passes over a string that itself grows by one `escClose` sentinel each
42+
// time - quadratic in `n`, with a ~26x constant from the sentinel's length.
43+
// 128KB of `'{a}' + '}'.repeat(n) + ',z}'` blocked the event loop for 27
44+
// seconds to produce two results. `EXPANSION_MAX_REWRITES` bounds how many
45+
// times the scan may restart. Real `{a},b}` input needs a handful.
46+
export const EXPANSION_MAX_REWRITES = 1_000;
2947
function numeric(str) {
3048
return !isNaN(str) ? parseInt(str, 10) : str.charCodeAt(0);
3149
}
@@ -45,37 +63,52 @@ function unescapeBraces(str) {
4563
.replace(escCommaPattern, ',')
4664
.replace(escPeriodPattern, '.');
4765
}
66+
// Like `target.push(...items)` but doesn't overflow the stack
67+
function pushAll(target, items) {
68+
for (let i = 0; i < items.length; i++) {
69+
target.push(items[i]);
70+
}
71+
}
4872
/**
4973
* Basically just str.split(","), but handling cases
5074
* where we have nested braced sections, which should be
5175
* treated as individual members, like {a,{b,c},d}
5276
*/
5377
function parseCommaParts(str) {
54-
if (!str) {
55-
return [''];
56-
}
5778
const parts = [];
58-
const m = balanced('{', '}', str);
59-
if (!m) {
60-
return str.split(',');
61-
}
62-
const { pre, body, post } = m;
63-
const p = pre.split(',');
64-
p[p.length - 1] += '{' + body + '}';
65-
const postParts = parseCommaParts(post);
66-
if (post.length) {
67-
;
68-
p[p.length - 1] += postParts.shift();
69-
p.push.apply(p, postParts);
79+
// Walk the brace groups iteratively. Recursing on `post` once per group let a
80+
// chain of them exhaust the stack - the parsing-side counterpart to
81+
// the `expand_` overflow fixed for CVE-2026-14257, and not something `max` or
82+
// `maxLength` can bound, since it happens before expansion.
83+
//
84+
// The part the next chunk continues
85+
let carry = '';
86+
for (;;) {
87+
const m = balanced('{', '}', str);
88+
if (!m) {
89+
const tail = str.split(',');
90+
tail[0] = carry + tail[0];
91+
pushAll(parts, tail);
92+
return parts;
93+
}
94+
const { pre, body, post } = m;
95+
const p = pre.split(',');
96+
p[0] = carry + p[0];
97+
p[p.length - 1] += '{' + body + '}';
98+
if (!post.length) {
99+
pushAll(parts, p);
100+
return parts;
101+
}
102+
carry = p.pop();
103+
pushAll(parts, p);
104+
str = post;
70105
}
71-
parts.push.apply(parts, p);
72-
return parts;
73106
}
74107
export function expand(str, options = {}) {
75108
if (!str) {
76109
return [];
77110
}
78-
const { max = EXPANSION_MAX, maxLength = EXPANSION_MAX_LENGTH } = options;
111+
const { max = EXPANSION_MAX, maxLength = EXPANSION_MAX_LENGTH, maxDepth = EXPANSION_MAX_DEPTH, maxRewrites = EXPANSION_MAX_REWRITES, } = options;
79112
// I don't know why Bash 4.3 does this, but it does.
80113
// Anything starting with {} will have the first two bytes preserved
81114
// but *only* at the top level, so {},a}b will not expand to anything,
@@ -85,7 +118,7 @@ export function expand(str, options = {}) {
85118
if (str.slice(0, 2) === '{}') {
86119
str = '\\{\\}' + str.slice(2);
87120
}
88-
return expand_(escapeBraces(str), max, maxLength, true).map(unescapeBraces);
121+
return expand_(escapeBraces(str), max, maxLength, maxDepth, 0, maxRewrites, true).map(unescapeBraces);
89122
}
90123
function embrace(str) {
91124
return '{' + str + '}';
@@ -180,7 +213,13 @@ function expandSequence(body, isAlphaSequence, max, maxLength) {
180213
}
181214
return N;
182215
}
183-
function expand_(str, max, maxLength, isTop) {
216+
function expand_(str, max, maxLength, maxDepth, depth, maxRewrites, isTop) {
217+
// Too deeply nested to keep following: treat the rest as literal, the same
218+
// way a group that cannot expand is already handled. Truncating rather than
219+
// throwing keeps `expand` total, matching `max` and `maxLength`.
220+
if (depth > maxDepth) {
221+
return [str];
222+
}
184223
// Consume the string's top-level brace groups left to right, threading a
185224
// running set of combined prefixes (`acc`). Expanding the tail iteratively -
186225
// rather than recursing on `m.post` once per group - keeps the native stack
@@ -192,6 +231,9 @@ function expand_(str, max, maxLength, isTop) {
192231
// comma set - a sequence like `{a..\}` may legitimately yield ''. The drop
193232
// is on the final strings, so it is applied to whichever `combine` produces
194233
// them (the one with no brace set left in the tail).
234+
// How many times the `{a},b}` rewrite below has restarted the scan. Each pass
235+
// re-reads the whole string, so leaving this unbounded is quadratic.
236+
let rewrites = 0;
195237
let dropEmpties = false;
196238
let firstGroup = true;
197239
for (;;) {
@@ -216,7 +258,8 @@ function expand_(str, max, maxLength, isTop) {
216258
const isOptions = m.body.indexOf(',') >= 0;
217259
if (!isSequence && !isOptions) {
218260
// {a},b}
219-
if (m.post.match(/,(?!,).*\}/)) {
261+
if (rewrites < maxRewrites && m.post.match(/,(?!,).*\}/)) {
262+
rewrites++;
220263
str = m.pre + '{' + m.body + escClose + m.post;
221264
isTop = true;
222265
continue;
@@ -236,7 +279,7 @@ function expand_(str, max, maxLength, isTop) {
236279
let n = parseCommaParts(m.body);
237280
if (n.length === 1 && n[0] !== undefined) {
238281
// x{{a,b}}y ==> x{a}y x{b}y
239-
n = expand_(n[0], max, maxLength, false).map(embrace);
282+
n = expand_(n[0], max, maxLength, maxDepth, depth + 1, maxRewrites, false).map(embrace);
240283
//XXX is this necessary? Can't seem to hit it in tests.
241284
/* c8 ignore start */
242285
if (n.length === 1) {
@@ -262,12 +305,13 @@ function expand_(str, max, maxLength, isTop) {
262305
values = [];
263306
let valuesLength = 0;
264307
outer: for (let j = 0; j < n.length; j++) {
265-
const expanded = expand_(n[j], max, maxLength, false);
308+
const expanded = expand_(n[j], max, maxLength, maxDepth, depth + 1, maxRewrites, false);
266309
for (let k = 0; k < expanded.length; k++) {
267310
const v = expanded[k];
268311
if (dropsEmpties && !v)
269312
continue;
270-
if (values.length >= max || valuesLength + v.length > maxLength) {
313+
if (values.length >= max ||
314+
valuesLength + v.length > maxLength) {
271315
break outer;
272316
}
273317
values.push(v);

‎node_modules/brace-expansion/package.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
{
22
"name": "brace-expansion",
33
"description": "Brace expansion as known from sh/bash",
4-
"version": "5.0.9",
4+
"version": "5.0.12",
55
"files": [
66
"dist"
77
],
@@ -29,6 +29,7 @@
2929
"test": "tap",
3030
"snap": "tap",
3131
"format": "prettier --write .",
32+
"format:check": "prettier --check .",
3233
"benchmark": "node benchmark/index.js",
3334
"typedoc": "typedoc --tsconfig .tshy/esm.json ./src/*.ts"
3435
},

0 commit comments

Comments
 (0)