Skip to content

Commit b7c490d

Browse files
martinrrmCopilot
andcommitted
Co-authored-by: Copilot <[email protected]> Copilot-Session: 73e1dfa8-6bec-47aa-b811-4edf404e9883
1 parent 75a943d commit b7c490d

4 files changed

Lines changed: 362 additions & 206 deletions

File tree

Lines changed: 162 additions & 84 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 = void 0;
3+
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';
@@ -19,6 +19,17 @@ const closePattern = /\\}/g;
1919
const commaPattern = /\\,/g;
2020
const periodPattern = /\\\./g;
2121
exports.EXPANSION_MAX = 100_000;
22+
// `EXPANSION_MAX` caps the *number* of expansions, but not their length. An
23+
// input like `'{a,b}'.repeat(1500)` stays under that count - its output is
24+
// truncated to 100k results - while making every result ~1500 characters
25+
// long. The result set, and the intermediate arrays built while combining
26+
// brace sets, then grow large enough to exhaust memory and crash the process
27+
// (CVE-2026-14257). `EXPANSION_MAX_LENGTH` bounds the total number of
28+
// characters the accumulator may hold at any point, so memory stays flat no
29+
// matter how many brace groups are chained. The limit sits well above any
30+
// realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M
31+
// characters) so legitimate input is unaffected.
32+
exports.EXPANSION_MAX_LENGTH = 4_000_000;
2233
function numeric(str) {
2334
return !isNaN(str) ? parseInt(str, 10) : str.charCodeAt(0);
2435
}
@@ -68,7 +79,7 @@ function expand(str, options = {}) {
6879
if (!str) {
6980
return [];
7081
}
71-
const { max = exports.EXPANSION_MAX } = options;
82+
const { max = exports.EXPANSION_MAX, maxLength = exports.EXPANSION_MAX_LENGTH } = options;
7283
// I don't know why Bash 4.3 does this, but it does.
7384
// Anything starting with {} will have the first two bytes preserved
7485
// but *only* at the top level, so {},a}b will not expand to anything,
@@ -78,7 +89,7 @@ function expand(str, options = {}) {
7889
if (str.slice(0, 2) === '{}') {
7990
str = '\\{\\}' + str.slice(2);
8091
}
81-
return expand_(escapeBraces(str), max, true).map(unescapeBraces);
92+
return expand_(escapeBraces(str), max, maxLength, true).map(unescapeBraces);
8293
}
8394
function embrace(str) {
8495
return '{' + str + '}';
@@ -92,25 +103,116 @@ function lte(i, y) {
92103
function gte(i, y) {
93104
return i >= y;
94105
}
95-
function expand_(str, max, isTop) {
96-
/** @type {string[]} */
97-
const expansions = [];
98-
// The `{a},b}` rewrite below restarts expansion on a rewritten string with
99-
// the same `max` and `isTop = true`. Loop instead of recursing so a long run
100-
// of non-expanding `{}` groups can't exhaust the call stack.
106+
// Build `{ acc[a] + pre + values[v] }` for every combination, capping the
107+
// number of results at `max` and the total number of characters at `maxLength`.
108+
// This is the one place output grows, so bounding it here keeps the single
109+
// accumulator - and therefore memory - flat regardless of how many brace groups
110+
// are combined (CVE-2026-14257).
111+
function combine(acc, pre, values, max, maxLength, dropEmpties) {
112+
const out = [];
113+
let length = 0;
114+
for (let a = 0; a < acc.length; a++) {
115+
for (let v = 0; v < values.length; v++) {
116+
if (out.length >= max)
117+
return out;
118+
const expansion = acc[a] + pre + values[v];
119+
// Bash drops empty results at the top level. Skip them before they count
120+
// against `max`, so `max` bounds the number of *kept* results.
121+
if (dropEmpties && !expansion)
122+
continue;
123+
if (length + expansion.length > maxLength)
124+
return out;
125+
out.push(expansion);
126+
length += expansion.length;
127+
}
128+
}
129+
return out;
130+
}
131+
// The expansion values of a single numeric (`1..5`) or alphabetic (`a..e..2`)
132+
// sequence body.
133+
function expandSequence(body, isAlphaSequence, max, maxLength) {
134+
const n = body.split(/\.\./);
135+
const N = [];
136+
// A sequence body always splits into two or three parts, but the compiler
137+
// can't know that.
138+
/* c8 ignore start */
139+
if (n[0] === undefined || n[1] === undefined) {
140+
return N;
141+
}
142+
/* c8 ignore stop */
143+
const x = numeric(n[0]);
144+
const y = numeric(n[1]);
145+
const width = Math.max(n[0].length, n[1].length);
146+
let incr = n.length === 3 && n[2] !== undefined ?
147+
Math.max(Math.abs(numeric(n[2])), 1)
148+
: 1;
149+
let test = lte;
150+
const reverse = y < x;
151+
if (reverse) {
152+
incr *= -1;
153+
test = gte;
154+
}
155+
const pad = n.some(isPadded);
156+
let length = 0;
157+
for (let i = x; test(i, y) && N.length < max; i += incr) {
158+
let c;
159+
if (isAlphaSequence) {
160+
c = String.fromCharCode(i);
161+
if (c === '\\') {
162+
c = '';
163+
}
164+
}
165+
else {
166+
c = String(i);
167+
if (pad) {
168+
const need = width - c.length;
169+
if (need > 0) {
170+
const z = new Array(need + 1).join('0');
171+
if (i < 0) {
172+
c = '-' + z + c.slice(1);
173+
}
174+
else {
175+
c = z + c;
176+
}
177+
}
178+
}
179+
}
180+
if (length + c.length > maxLength)
181+
break;
182+
N.push(c);
183+
length += c.length;
184+
}
185+
return N;
186+
}
187+
function expand_(str, max, maxLength, isTop) {
188+
// Consume the string's top-level brace groups left to right, threading a
189+
// running set of combined prefixes (`acc`). Expanding the tail iteratively -
190+
// rather than recursing on `m.post` once per group - keeps the native stack
191+
// depth constant, so deeply chained input (`'{a,b}'.repeat(3000)`) can no
192+
// longer overflow the stack, and leaves a single accumulator whose size
193+
// `maxLength` bounds directly (CVE-2026-14257).
194+
let acc = [''];
195+
// Bash drops empty results, but only when the *first* top-level group is a
196+
// comma set - a sequence like `{a..\}` may legitimately yield ''. The drop
197+
// is on the final strings, so it is applied to whichever `combine` produces
198+
// them (the one with no brace set left in the tail).
199+
let dropEmpties = false;
200+
let firstGroup = true;
101201
for (;;) {
102202
const m = (0, balanced_match_1.balanced)('{', '}', str);
103-
if (!m)
104-
return [str];
203+
// No brace set left: the rest of the string is literal.
204+
if (!m) {
205+
return combine(acc, str, [''], max, maxLength, dropEmpties);
206+
}
105207
// no need to expand pre, since it is guaranteed to be free of brace-sets
106208
const pre = m.pre;
107-
if (/\$$/.test(m.pre)) {
108-
const post = m.post.length ? expand_(m.post, max, false) : [''];
109-
for (let k = 0; k < post.length && k < max; k++) {
110-
const expansion = pre + '{' + m.body + '}' + post[k];
111-
expansions.push(expansion);
112-
}
113-
return expansions;
209+
if (/\$$/.test(pre)) {
210+
acc = combine(acc, pre + '{' + m.body + '}', [''], max, maxLength, dropEmpties && !m.post.length);
211+
firstGroup = false;
212+
if (!m.post.length)
213+
break;
214+
str = m.post;
215+
continue;
114216
}
115217
const isNumericSequence = /^-?\d+\.\.-?\d+(?:\.\.-?\d+)?$/.test(m.body);
116218
const isAlphaSequence = /^[a-zA-Z]\.\.[a-zA-Z](?:\.\.-?\d+)?$/.test(m.body);
@@ -123,89 +225,65 @@ function expand_(str, max, isTop) {
123225
isTop = true;
124226
continue;
125227
}
126-
return [str];
228+
// Nothing here expands, so the whole remaining string is literal.
229+
return combine(acc, pre + '{' + m.body + '}' + m.post, [''], max, maxLength, dropEmpties);
230+
}
231+
if (firstGroup) {
232+
dropEmpties = isTop && !isSequence;
233+
firstGroup = false;
127234
}
128-
// Only expand post once we know this brace set actually expands. Computing
129-
// it before the early returns above expanded post a second time on every
130-
// non-expanding `{}`, which is what made inputs like `a{},{},{}...` blow up
131-
// exponentially.
132-
const post = m.post.length ? expand_(m.post, max, false) : [''];
133-
let n;
235+
let values;
134236
if (isSequence) {
135-
n = m.body.split(/\.\./);
237+
values = expandSequence(m.body, isAlphaSequence, max, maxLength);
136238
}
137239
else {
138-
n = parseCommaParts(m.body);
240+
let n = parseCommaParts(m.body);
139241
if (n.length === 1 && n[0] !== undefined) {
140242
// x{{a,b}}y ==> x{a}y x{b}y
141-
n = expand_(n[0], max, false).map(embrace);
243+
n = expand_(n[0], max, maxLength, false).map(embrace);
142244
//XXX is this necessary? Can't seem to hit it in tests.
143245
/* c8 ignore start */
144246
if (n.length === 1) {
145-
return post.map(p => m.pre + n[0] + p);
247+
acc = combine(acc, pre + n[0], [''], max, maxLength, dropEmpties && !m.post.length);
248+
if (!m.post.length)
249+
break;
250+
str = m.post;
251+
continue;
146252
}
147253
/* c8 ignore stop */
148254
}
149-
}
150-
// at this point, n is the parts, and we know it's not a comma set
151-
// with a single entry.
152-
let N;
153-
if (isSequence && n[0] !== undefined && n[1] !== undefined) {
154-
const x = numeric(n[0]);
155-
const y = numeric(n[1]);
156-
const width = Math.max(n[0].length, n[1].length);
157-
let incr = n.length === 3 && n[2] !== undefined ?
158-
Math.max(Math.abs(numeric(n[2])), 1)
159-
: 1;
160-
let test = lte;
161-
const reverse = y < x;
162-
if (reverse) {
163-
incr *= -1;
164-
test = gte;
165-
}
166-
const pad = n.some(isPadded);
167-
N = [];
168-
for (let i = x; test(i, y) && N.length < max; i += incr) {
169-
let c;
170-
if (isAlphaSequence) {
171-
c = String.fromCharCode(i);
172-
if (c === '\\') {
173-
c = '';
174-
}
255+
// Values that `combine` is going to drop as empty produce no result, so
256+
// they must not count against `max` - otherwise `{a,,b}` with `max: 2`
257+
// would stop at `['a', '']` and yield one result instead of two. Skipping
258+
// them outright keeps `values` bounded while leaving `max` a bound on
259+
// *kept* results.
260+
let dropsEmpties = dropEmpties && !m.post.length && !pre;
261+
for (let d = 0; dropsEmpties && d < acc.length; d++) {
262+
if (acc[d]) {
263+
dropsEmpties = false;
175264
}
176-
else {
177-
c = String(i);
178-
if (pad) {
179-
const need = width - c.length;
180-
if (need > 0) {
181-
const z = new Array(need + 1).join('0');
182-
if (i < 0) {
183-
c = '-' + z + c.slice(1);
184-
}
185-
else {
186-
c = z + c;
187-
}
188-
}
189-
}
190-
}
191-
N.push(c);
192265
}
193-
}
194-
else {
195-
N = [];
196-
for (let j = 0; j < n.length; j++) {
197-
N.push.apply(N, expand_(n[j], max, false));
198-
}
199-
}
200-
for (let j = 0; j < N.length; j++) {
201-
for (let k = 0; k < post.length && expansions.length < max; k++) {
202-
const expansion = pre + N[j] + post[k];
203-
if (!isTop || isSequence || expansion) {
204-
expansions.push(expansion);
266+
values = [];
267+
let valuesLength = 0;
268+
outer: for (let j = 0; j < n.length; j++) {
269+
const expanded = expand_(n[j], max, maxLength, false);
270+
for (let k = 0; k < expanded.length; k++) {
271+
const v = expanded[k];
272+
if (dropsEmpties && !v)
273+
continue;
274+
if (values.length >= max || valuesLength + v.length > maxLength) {
275+
break outer;
276+
}
277+
values.push(v);
278+
valuesLength += v.length;
205279
}
206280
}
207281
}
208-
return expansions;
282+
acc = combine(acc, pre, values, max, maxLength, dropEmpties && !m.post.length);
283+
if (!m.post.length)
284+
break;
285+
str = m.post;
209286
}
287+
return acc;
210288
}
211289
//# sourceMappingURL=index.js.map

0 commit comments

Comments
 (0)