@@ -9,6 +9,20 @@ var escClose = '\0CLOSE'+Math.random()+'\0';
99var escComma = '\0COMMA' + Math . random ( ) + '\0' ;
1010var escPeriod = '\0PERIOD' + Math . random ( ) + '\0' ;
1111
12+ var EXPANSION_MAX = 100000
13+
14+ // `EXPANSION_MAX` caps the *number* of expansions, but not their length. An
15+ // input like `'{a,b}'.repeat(1500)` stays under that count - its output is
16+ // truncated to 100k results - while making every result ~1500 characters
17+ // long. The result set, and the intermediate arrays built while combining
18+ // brace sets, then grow large enough to exhaust memory and crash the process
19+ // (CVE-2026-14257). `EXPANSION_MAX_LENGTH` bounds the total number of
20+ // characters the accumulator may hold at any point, so memory stays flat no
21+ // matter how many brace groups are chained. The limit sits well above any
22+ // realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M
23+ // characters) so legitimate input is unaffected.
24+ var EXPANSION_MAX_LENGTH = 4000000
25+
1226function numeric ( str ) {
1327 return parseInt ( str , 10 ) == str
1428 ? parseInt ( str , 10 )
@@ -67,7 +81,8 @@ function expandTop(str, options) {
6781 return [ ] ;
6882
6983 options = options || { } ;
70- var max = options . max == null ? Infinity : options . max ;
84+ var max = options . max == null ? EXPANSION_MAX : options . max ;
85+ var maxLength = options . maxLength == null ? EXPANSION_MAX_LENGTH : options . maxLength ;
7186
7287 // I don't know why Bash 4.3 does this, but it does.
7388 // Anything starting with {} will have the first two bytes preserved
@@ -79,7 +94,7 @@ function expandTop(str, options) {
7994 str = '\\{\\}' + str . substr ( 2 ) ;
8095 }
8196
82- return expand ( escapeBraces ( str ) , max , true ) . map ( unescapeBraces ) ;
97+ return expand ( escapeBraces ( str ) , max , maxLength , true ) . map ( unescapeBraces ) ;
8398}
8499
85100function identity ( e ) {
@@ -100,15 +115,151 @@ function gte(i, y) {
100115 return i >= y ;
101116}
102117
103- function expand ( str , max , isTop ) {
104- var expansions = [ ] ;
118+ // Build `{ acc[a] + pre + values[v] }` for every combination, capping the
119+ // number of results at `max` and the total number of characters at `maxLength`.
120+ // This is the one place output grows, so bounding it here keeps the single
121+ // accumulator - and therefore memory - flat regardless of how many brace groups
122+ // are combined (CVE-2026-14257).
123+ //
124+ // `base[a]` is the length of the part of `acc[a]` that predates the current
125+ // empty-drop baseline (see `expand`). The matching baselines for the results
126+ // are appended to `outBase`, which the caller carries forward alongside them.
127+ function combine (
128+ acc ,
129+ base ,
130+ pre ,
131+ values ,
132+ max ,
133+ maxLength ,
134+ dropEmpties ,
135+ outBase
136+ ) {
137+ var out = [ ]
138+ var length = 0
139+ for ( var a = 0 ; a < acc . length ; a ++ ) {
140+ for ( var v = 0 ; v < values . length ; v ++ ) {
141+ if ( out . length >= max ) return out
142+ var expansion = acc [ a ] + pre + values [ v ]
143+ // Bash drops empty results at the top level. Skip them before they count
144+ // against `max`, so `max` bounds the number of *kept* results. "Empty"
145+ // means "adds nothing past the baseline", not "empty overall".
146+ if ( dropEmpties && expansion . length === base [ a ] ) continue
147+ if ( length + expansion . length > maxLength ) return out
148+ out . push ( expansion )
149+ outBase . push ( base [ a ] )
150+ length += expansion . length
151+ }
152+ }
153+ return out
154+ }
155+
156+ // The expansion values of a single numeric (`1..5`) or alphabetic (`a..e..2`)
157+ // sequence body.
158+ function expandSequence (
159+ body ,
160+ isAlphaSequence ,
161+ max
162+ ) {
163+ var n = body . split ( / \. \. / )
164+ var N = [ ]
165+ // A sequence body always splits into two or three parts, but the compiler
166+ // can't know that.
167+ /* c8 ignore start */
168+ if ( n [ 0 ] === undefined || n [ 1 ] === undefined ) {
169+ return N
170+ }
171+ /* c8 ignore stop */
172+ var x = numeric ( n [ 0 ] )
173+ var y = numeric ( n [ 1 ] )
174+ var width = Math . max ( n [ 0 ] . length , n [ 1 ] . length )
175+ var incr =
176+ n . length === 3 && n [ 2 ] !== undefined ?
177+ Math . max ( Math . abs ( numeric ( n [ 2 ] ) ) , 1 )
178+ : 1
179+ var test = lte
180+ var reverse = y < x
181+ if ( reverse ) {
182+ incr *= - 1
183+ test = gte
184+ }
185+ var pad = n . some ( isPadded )
186+
187+ for ( var i = x ; test ( i , y ) && N . length < max ; i += incr ) {
188+ var c
189+ if ( isAlphaSequence ) {
190+ c = String . fromCharCode ( i )
191+ if ( c === '\\' ) {
192+ c = ''
193+ }
194+ } else {
195+ c = String ( i )
196+ if ( pad ) {
197+ var need = width - c . length
198+ if ( need > 0 ) {
199+ var z = new Array ( need + 1 ) . join ( '0' )
200+ if ( i < 0 ) {
201+ c = '-' + z + c . slice ( 1 )
202+ } else {
203+ c = z + c
204+ }
205+ }
206+ }
207+ }
208+ N . push ( c )
209+ }
210+ return N
211+ }
212+
213+ function expand (
214+ str ,
215+ max ,
216+ maxLength ,
217+ isTop
218+ ) {
219+ // Consume the string's top-level brace groups left to right, threading a
220+ // running set of combined prefixes (`acc`). Expanding the tail iteratively -
221+ // rather than recursing on `m.post` once per group - keeps the native stack
222+ // depth constant, so deeply chained input (`'{a,b}'.repeat(3000)`) can no
223+ // longer overflow the stack, and leaves a single accumulator whose size
224+ // `maxLength` bounds directly (CVE-2026-14257).
225+ var acc = [ '' ]
226+
227+ // Bash drops empty results, but only when the *first* group of the run is a
228+ // comma set - a sequence like `{a..\}` may legitimately yield ''. The drop
229+ // is on the final strings, so it is applied to whichever `combine` produces
230+ // them (the one with no brace set left in the tail).
231+ //
232+ // The old implementation recursed on `m.post`, so the drop tested only the
233+ // expansion of the current call's substring. The `{a},b }` rewrite below turns
234+ // `isTop` back on part-way through a string, starting a fresh such run, so
235+ // the drop must ignore whatever `acc` already holds from earlier groups.
236+ // `accBase[a]` records how much of `acc[a]` predates the current run;
237+ // `combine` treats an expansion as empty when it adds nothing past that.
238+ var accBase = [ 0 ]
239+ var dropEmpties = false
240+ var firstGroup = true
241+ var nextBase
105242
106- // The `{a},b}` rewrite below restarts expansion on a rewritten string with
107- // the same `max` and `isTop = true`. Loop instead of recursing so a long run
108- // of non-expanding `{}` groups can't exhaust the call stack.
109243 for ( ; ; ) {
110244 var m = balanced ( '{' , '}' , str ) ;
111- if ( ! m || / \$ $ / . test ( m . pre ) ) return [ str ] ;
245+
246+ // No brace set left: the rest of the string is literal.
247+ if ( ! m ) {
248+ return combine ( acc , accBase , str , [ '' ] , max , maxLength , dropEmpties , [ ] )
249+ }
250+
251+ // no need to expand pre, since it is guaranteed to be free of brace-sets
252+ var pre = m . pre ;
253+
254+ // For compatibility reasons, `${` is not eligible for brace expansion, and
255+ // on the 1.x line it suppresses expansion of the rest of the string too:
256+ // the whole remainder is literal. The 2.x and 5.x lines instead keep
257+ // expanding the tail, which is what bash does, but changing that here would
258+ // be a breaking change for 1.x consumers. Routed through `combine` so the
259+ // result is still bounded by `max` and `maxLength`.
260+ if ( / \$ $ / . test ( pre ) ) {
261+ return combine ( acc , accBase , str , [ '' ] , max , maxLength , dropEmpties , [ ] )
262+ }
112263
113264 var isNumericSequence = / ^ - ? \d + \. \. - ? \d + (?: \. \. - ? \d + ) ? $ / . test ( m . body ) ;
114265 var isAlphaSequence = / ^ [ a - z A - Z ] \. \. [ a - z A - Z ] (?: \. \. - ? \d + ) ? $ / . test ( m . body ) ;
@@ -118,92 +269,87 @@ function expand(str, max, isTop) {
118269 // {a},b }
119270 if ( m . post . match ( / , (? ! , ) .* \} / ) ) {
120271 str = m . pre + '{' + m . body + escClose + m . post ;
272+ // The rewritten string is expanded as if it were a fresh top-level one,
273+ // so start a new empty-drop run: anchor the baseline at what `acc`
274+ // holds now, and let the next expanding group decide whether to drop.
121275 isTop = true
276+ firstGroup = true
277+ dropEmpties = false
278+ accBase = [ ]
279+ for ( var b = 0 ; b < acc . length ; b ++ ) {
280+ accBase . push ( acc [ b ] . length )
281+ }
122282 continue
123283 }
124- return [ str ] ;
284+ // Nothing here expands, so the whole remaining string is literal.
285+ return combine (
286+ acc ,
287+ accBase ,
288+ pre + '{' + m . body + '}' + m . post ,
289+ [ '' ] ,
290+ max ,
291+ maxLength ,
292+ dropEmpties ,
293+ [ ]
294+ )
295+ }
296+
297+ if ( firstGroup ) {
298+ dropEmpties = isTop && ! isSequence
299+ firstGroup = false
125300 }
126301
127- var n ;
302+ var values ;
128303 if ( isSequence ) {
129- n = m . body . split ( / \. \. / ) ;
304+ values = expandSequence ( m . body , isAlphaSequence , max ) ;
130305 } else {
131- n = parseCommaParts ( m . body ) ;
132- if ( n . length === 1 ) {
306+ var n = parseCommaParts ( m . body ) ;
307+ if ( n . length === 1 && n [ 0 ] !== undefined ) {
133308 // x{{a,b}}y ==> x{a}y x{b}y
134- n = expand ( n [ 0 ] , max , false ) . map ( embrace ) ;
309+ n = expand ( n [ 0 ] , max , maxLength , false ) . map ( embrace ) ;
310+ //XXX is this necessary? Can't seem to hit it in tests.
311+ /* c8 ignore start */
135312 if ( n . length === 1 ) {
136- var post = m . post . length
137- ? expand ( m . post , max , false )
138- : [ '' ] ;
139- return post . map ( function ( p ) {
140- return m . pre + n [ 0 ] + p ;
141- } ) ;
142- }
143- }
144- }
145-
146- // at this point, n is the parts, and we know it's not a comma set
147- // with a single entry.
148-
149- // no need to expand pre, since it is guaranteed to be free of brace-sets
150- var pre = m . pre ;
151- var post = m . post . length
152- ? expand ( m . post , max , false )
153- : [ '' ] ;
154-
155- var N ;
156-
157- if ( isSequence ) {
158- var x = numeric ( n [ 0 ] ) ;
159- var y = numeric ( n [ 1 ] ) ;
160- var width = Math . max ( n [ 0 ] . length , n [ 1 ] . length )
161- var incr = n . length == 3
162- ? Math . max ( Math . abs ( numeric ( n [ 2 ] ) ) , 1 )
163- : 1 ;
164- var test = lte ;
165- var reverse = y < x ;
166- if ( reverse ) {
167- incr *= - 1 ;
168- test = gte ;
169- }
170- var pad = n . some ( isPadded ) ;
171-
172- N = [ ] ;
173-
174- for ( var i = x ; test ( i , y ) && N . length < max ; i += incr ) {
175- var c ;
176- if ( isAlphaSequence ) {
177- c = String . fromCharCode ( i ) ;
178- if ( c === '\\' )
179- c = '' ;
180- } else {
181- c = String ( i ) ;
182- if ( pad ) {
183- var need = width - c . length ;
184- if ( need > 0 ) {
185- var z = new Array ( need + 1 ) . join ( '0' ) ;
186- if ( i < 0 )
187- c = '-' + z + c . slice ( 1 ) ;
188- else
189- c = z + c ;
190- }
191- }
313+ nextBase = [ ]
314+ acc = combine (
315+ acc ,
316+ accBase ,
317+ pre + n [ 0 ] ,
318+ [ '' ] ,
319+ max ,
320+ maxLength ,
321+ dropEmpties && ! m . post . length ,
322+ nextBase
323+ )
324+ accBase = nextBase
325+ if ( ! m . post . length ) break
326+ str = m . post
327+ continue
192328 }
193- N . push ( c ) ;
329+ /* c8 ignore stop */
194330 }
195- } else {
196- N = concatMap ( n , function ( el ) { return expand ( el , max , false ) } ) ;
197- }
198331
199- for ( var j = 0 ; j < N . length ; j ++ ) {
200- for ( var k = 0 ; k < post . length && expansions . length < max ; k ++ ) {
201- var expansion = pre + N [ j ] + post [ k ] ;
202- if ( ! isTop || isSequence || expansion )
203- expansions . push ( expansion ) ;
332+ values = [ ]
333+ for ( var j = 0 ; j < n . length ; j ++ ) {
334+ values . push . apply ( values , expand ( n [ j ] , max , maxLength , false ) )
204335 }
205336 }
206337
207- return expansions ;
338+ nextBase = [ ]
339+ acc = combine (
340+ acc ,
341+ accBase ,
342+ pre ,
343+ values ,
344+ max ,
345+ maxLength ,
346+ dropEmpties && ! m . post . length ,
347+ nextBase
348+ )
349+ accBase = nextBase
350+ if ( ! m . post . length ) break
351+ str = m . post
208352 }
353+
354+ return acc
209355}
0 commit comments