Brunobkr/llama.cpp_AlgMor24_github

1var concatMap = require('concat-map');2var balanced = require('balanced-match');3 4module.exports = expandTop;5 6var escSlash = '\0SLASH'+Math.random()+'\0';7var escOpen = '\0OPEN'+Math.random()+'\0';8var escClose = '\0CLOSE'+Math.random()+'\0';9var escComma = '\0COMMA'+Math.random()+'\0';10var escPeriod = '\0PERIOD'+Math.random()+'\0';11 12var EXPANSION_MAX = 10000013 14// `EXPANSION_MAX` caps the *number* of expansions, but not their length. An15// input like `'{a,b}'.repeat(1500)` stays under that count - its output is16// truncated to 100k results - while making every result ~1500 characters17// long. The result set, and the intermediate arrays built while combining18// brace sets, then grow large enough to exhaust memory and crash the process19// (CVE-2026-14257). `EXPANSION_MAX_LENGTH` bounds the total number of20// characters the accumulator may hold at any point, so memory stays flat no21// matter how many brace groups are chained. The limit sits well above any22// realistic expansion (100k results hitting `EXPANSION_MAX` measure ~1M23// characters) so legitimate input is unaffected.24var EXPANSION_MAX_LENGTH = 400000025 26function numeric(str) {27  return parseInt(str, 10) == str28    ? parseInt(str, 10)29    : str.charCodeAt(0);30}31 32function escapeBraces(str) {33  return str.split('\\\\').join(escSlash)34            .split('\\{').join(escOpen)35            .split('\\}').join(escClose)36            .split('\\,').join(escComma)37            .split('\\.').join(escPeriod);38}39 40function unescapeBraces(str) {41  return str.split(escSlash).join('\\')42            .split(escOpen).join('{')43            .split(escClose).join('}')44            .split(escComma).join(',')45            .split(escPeriod).join('.');46}47 48 49// Basically just str.split(","), but handling cases50// where we have nested braced sections, which should be51// treated as individual members, like {a,{b,c},d}52function parseCommaParts(str) {53  if (!str)54    return [''];55 56  var parts = [];57  var m = balanced('{', '}', str);58 59  if (!m)60    return str.split(',');61 62  var pre = m.pre;63  var body = m.body;64  var post = m.post;65  var p = pre.split(',');66 67  p[p.length-1] += '{' + body + '}';68  var postParts = parseCommaParts(post);69  if (post.length) {70    p[p.length-1] += postParts.shift();71    p.push.apply(p, postParts);72  }73 74  parts.push.apply(parts, p);75 76  return parts;77}78 79function expandTop(str, options) {80  if (!str)81    return [];82 83  options = options || {};84  var max = options.max == null ? EXPANSION_MAX : options.max;85  var maxLength = options.maxLength == null ? EXPANSION_MAX_LENGTH : options.maxLength;86 87  // I don't know why Bash 4.3 does this, but it does.88  // Anything starting with {} will have the first two bytes preserved89  // but *only* at the top level, so {},a}b will not expand to anything,90  // but a{},b}c will be expanded to [a}c,abc].91  // One could argue that this is a bug in Bash, but since the goal of92  // this module is to match Bash's rules, we escape a leading {}93  if (str.substr(0, 2) === '{}') {94    str = '\\{\\}' + str.substr(2);95  }96 97  return expand(escapeBraces(str), max, maxLength, true).map(unescapeBraces);98}99 100function identity(e) {101  return e;102}103 104function embrace(str) {105  return '{' + str + '}';106}107function isPadded(el) {108  return /^-?0\d/.test(el);109}110 111function lte(i, y) {112  return i <= y;113}114function gte(i, y) {115  return i >= y;116}117 118// Build `{ acc[a] + pre + values[v] }` for every combination, capping the119// 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 single121// accumulator - and therefore memory - flat regardless of how many brace groups122// are combined (CVE-2026-14257).123//124// `base[a]` is the length of the part of `acc[a]` that predates the current125// empty-drop baseline (see `expand`). The matching baselines for the results126// are appended to `outBase`, which the caller carries forward alongside them.127function combine(128  acc,129  base,130  pre,131  values,132  max,133  maxLength,134  dropEmpties,135  outBase136) {137  var out = []138  var length = 0139  for (var a = 0; a < acc.length; a++) {140    for (var v = 0; v < values.length; v++) {141      if (out.length >= max) return out142      var expansion = acc[a] + pre + values[v]143      // Bash drops empty results at the top level. Skip them before they count144      // 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]) continue147      if (length + expansion.length > maxLength) return out148      out.push(expansion)149      outBase.push(base[a])150      length += expansion.length151    }152  }153  return out154}155 156// The expansion values of a single numeric (`1..5`) or alphabetic (`a..e..2`)157// sequence body.158function expandSequence(159  body,160  isAlphaSequence,161  max,162  maxLength163) {164  var n = body.split(/\.\./)165  var N = []166  // A sequence body always splits into two or three parts, but the compiler167  // can't know that.168  /* c8 ignore start */169  if (n[0] === undefined || n[1] === undefined) {170    return N171  }172  /* c8 ignore stop */173  var x = numeric(n[0])174  var y = numeric(n[1])175  var width = Math.max(n[0].length, n[1].length)176  var incr =177    n.length === 3 && n[2] !== undefined ?178      Math.max(Math.abs(numeric(n[2])), 1)179    : 1180  var test = lte181  var reverse = y < x182  if (reverse) {183    incr *= -1184    test = gte185  }186  var pad = n.some(isPadded)187 188  var length = 0189  for (var i = x; test(i, y) && N.length < max; i += incr) {190    var c191    if (isAlphaSequence) {192      c = String.fromCharCode(i)193      if (c === '\\') {194        c = ''195      }196    } else {197      c = String(i)198      if (pad) {199        var need = width - c.length200        if (need > 0) {201          var z = new Array(need + 1).join('0')202          if (i < 0) {203            c = '-' + z + c.slice(1)204          } else {205            c = z + c206          }207        }208      }209    }210    if (length + c.length > maxLength) break211    N.push(c)212    length += c.length213  }214  return N215}216 217function expand(218  str,219  max,220  maxLength,221  isTop222) {223  // Consume the string's top-level brace groups left to right, threading a224  // running set of combined prefixes (`acc`). Expanding the tail iteratively -225  // rather than recursing on `m.post` once per group - keeps the native stack226  // depth constant, so deeply chained input (`'{a,b}'.repeat(3000)`) can no227  // longer overflow the stack, and leaves a single accumulator whose size228  // `maxLength` bounds directly (CVE-2026-14257).229  var acc = ['']230 231  // Bash drops empty results, but only when the *first* group of the run is a232  // comma set - a sequence like `{a..\}` may legitimately yield ''. The drop233  // is on the final strings, so it is applied to whichever `combine` produces234  // them (the one with no brace set left in the tail).235  //236  // The old implementation recursed on `m.post`, so the drop tested only the237  // expansion of the current call's substring. The `{a},b}` rewrite below turns238  // `isTop` back on part-way through a string, starting a fresh such run, so239  // the drop must ignore whatever `acc` already holds from earlier groups.240  // `accBase[a]` records how much of `acc[a]` predates the current run;241  // `combine` treats an expansion as empty when it adds nothing past that.242  var accBase = [0]243  var dropEmpties = false244  var firstGroup = true245  var nextBase246 247  for (;;) {248    var m = balanced('{', '}', str);249 250    // No brace set left: the rest of the string is literal.251    if (!m) {252      return combine(acc, accBase, str, [''], max, maxLength, dropEmpties, [])253    }254 255    // no need to expand pre, since it is guaranteed to be free of brace-sets256    var pre = m.pre;257 258    // For compatibility reasons, `${` is not eligible for brace expansion, and259    // on the 1.x line it suppresses expansion of the rest of the string too:260    // the whole remainder is literal. The 2.x and 5.x lines instead keep261    // expanding the tail, which is what bash does, but changing that here would262    // be a breaking change for 1.x consumers. Routed through `combine` so the263    // result is still bounded by `max` and `maxLength`.264    if (/\$$/.test(pre)) {265      return combine(acc, accBase, str, [''], max, maxLength, dropEmpties, [])266    }267 268    var isNumericSequence = /^-?\d+\.\.-?\d+(?:\.\.-?\d+)?$/.test(m.body);269    var isAlphaSequence = /^[a-zA-Z]\.\.[a-zA-Z](?:\.\.-?\d+)?$/.test(m.body);270    var isSequence = isNumericSequence || isAlphaSequence;271    var isOptions = m.body.indexOf(',') >= 0;272    if (!isSequence && !isOptions) {273      // {a},b}274      if (m.post.match(/,(?!,).*\}/)) {275        str = m.pre + '{' + m.body + escClose + m.post;276        // The rewritten string is expanded as if it were a fresh top-level one,277        // so start a new empty-drop run: anchor the baseline at what `acc`278        // holds now, and let the next expanding group decide whether to drop.279        isTop = true280        firstGroup = true281        dropEmpties = false282        accBase = []283        for (var b = 0; b < acc.length; b++) {284          accBase.push(acc[b].length)285        }286        continue287      }288      // Nothing here expands, so the whole remaining string is literal.289      return combine(290        acc,291        accBase,292        pre + '{' + m.body + '}' + m.post,293        [''],294        max,295        maxLength,296        dropEmpties,297        []298      )299    }300 301    if (firstGroup) {302      dropEmpties = isTop && !isSequence303      firstGroup = false304    }305 306    var values;307    if (isSequence) {308      values = expandSequence(m.body, isAlphaSequence, max, maxLength);309    } else {310      var n = parseCommaParts(m.body);311      if (n.length === 1 && n[0] !== undefined) {312        // x{{a,b}}y ==> x{a}y x{b}y313        n = expand(n[0], max, maxLength, false).map(embrace);314        //XXX is this necessary? Can't seem to hit it in tests.315        /* c8 ignore start */316        if (n.length === 1) {317          nextBase = []318          acc = combine(319            acc,320            accBase,321            pre + n[0],322            [''],323            max,324            maxLength,325            dropEmpties && !m.post.length,326            nextBase327          )328          accBase = nextBase329          if (!m.post.length) break330          str = m.post331          continue332        }333        /* c8 ignore stop */334      }335 336      // Values that `combine` is going to drop as empty produce no result, so337      // they must not count against `max` - otherwise `{a,,b}` with `max: 2`338      // would stop at `['a', '']` and yield one result instead of two. Skipping339      // them outright keeps `values` bounded while leaving `max` a bound on340      // *kept* results. A value is dropped when it adds nothing past the341      // baseline, which is what `combine` tests.342      var dropsEmpties = dropEmpties && !m.post.length && !pre343      for (var d = 0; dropsEmpties && d < acc.length; d++) {344        if (acc[d].length !== accBase[d]) {345          dropsEmpties = false346        }347      }348 349      values = []350      var valuesLength = 0351      outer: for (var j = 0; j < n.length; j++) {352        var expanded = expand(n[j], max, maxLength, false)353        for (var k = 0; k < expanded.length; k++) {354          var v = expanded[k]355          if (dropsEmpties && !v) continue356          if (values.length >= max || valuesLength + v.length > maxLength) {357            break outer358          }359          values.push(v)360          valuesLength += v.length361        }362      }363    }364 365    nextBase = []366    acc = combine(367      acc,368      accBase,369      pre,370      values,371      max,372      maxLength,373      dropEmpties && !m.post.length,374      nextBase375    )376    accBase = nextBase377    if (!m.post.length) break378    str = m.post379  }380 381  return acc382}383