Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: juliangruber/brace-expansion
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: v1.1.18
Choose a base ref
...
head repository: juliangruber/brace-expansion
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: v1.1.21
Choose a head ref
  • 6 commits
  • 6 files changed
  • 1 contributor

Commits on Sep 14, 2026

  1. Merge commit from fork

    * fix: make parseCommaParts iterative and avoid push.apply
    
    `parseCommaParts` recursed on the remainder of the string once per brace
    group, so a chain of groups nested inside a brace set exhausted the native
    stack at ~7,000 groups (~29KB of input):
    
        expand('{' + '{a},'.repeat(7000) + 'b}')
        // RangeError: Maximum call stack size exceeded
    
    This is the parsing-side counterpart to the `expand` overflow fixed for
    CVE-2026-14257. That fix documented a constant-stack-depth guarantee, but
    only `expand` was made iterative, so putting the same chain inside a brace
    group routed parsing through the recursion that was left in place.
    
    Neither `max` nor `maxLength` could bound it: the crash happens while
    parsing, before anything is expanded, and the payload produces one result
    per group, so output size grows linearly and is never the limiter.
    
    Rewrite the function as a loop that carries the partial part across chunks.
    
    Separately, `push.apply(target, items)` passes one argument per element, so
    a single large array overflows the stack with no recursion at all - this
    input reaches a recursion depth of exactly one:
    
        expand('{{x},' + 'a,'.repeat(125000) + 'b}')
        // RangeError: Maximum call stack size exceeded
    
    Append element by element via `pushAll` instead.
    
    The leading `if (!str) return ['']` guard is dropped: it is unreachable from
    the sole call site (`m.body` always contains a comma there), and the loop
    returns `['']` for the empty string on its own.
    
    Equivalence with the previous implementation was checked by differential
    testing against the published release of this line - 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.
    
    * review: trim comments
    juliangruber authored Sep 14, 2026
    Configuration menu
    Copy the full SHA
    0bcbfc0 View commit details
    Browse the repository at this point in the history
  2. 1.1.19

    juliangruber committed Sep 14, 2026
    Configuration menu
    Copy the full SHA
    a34340a View commit details
    Browse the repository at this point in the history
  3. 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.
    juliangruber authored Sep 14, 2026
    Configuration menu
    Copy the full SHA
    1efee7c View commit details
    Browse the repository at this point in the history
  4. 1.1.20

    juliangruber committed Sep 14, 2026
    Configuration menu
    Copy the full SHA
    c6513ad View commit details
    Browse the repository at this point in the history
  5. 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.
    juliangruber authored Sep 14, 2026
    Configuration menu
    Copy the full SHA
    ffdfa3e View commit details
    Browse the repository at this point in the history
  6. 1.1.21

    juliangruber committed Sep 14, 2026
    Configuration menu
    Copy the full SHA
    8e81e18 View commit details
    Browse the repository at this point in the history
Loading