command_stream/bun_shell/
braces.rs

1//! Brace expansion, ported from Bun's `src/shell_parser/braces.rs` (MIT) via
2//! `js/src/bun-shell/braces.mjs`. Token shapes, the literal-group rules of
3//! bash 5.2 and the output ordering follow Bun exactly.
4
5use std::fmt;
6
7/// Most `{` groups a pattern may have.
8pub(crate) const MAX_BRACE_GROUPS: usize = 256;
9/// Most words a pattern may expand to.
10pub(crate) const MAX_BRACE_EXPANSIONS: u32 = 65536;
11
12/// A brace expansion failure.
13#[derive(Clone, Debug, PartialEq, Eq)]
14pub enum BraceError {
15    /// More than 256 brace groups.
16    TooManyBraces,
17    /// A malformed nested pattern.
18    UnexpectedToken,
19    /// The pattern expands to more than 65536 words (the count, saturated at
20    /// `u32::MAX`).
21    TooManyExpansions(u32),
22}
23
24impl fmt::Display for BraceError {
25    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
26        match self {
27            BraceError::TooManyBraces => f.write_str("Too many braces in brace expansion"),
28            BraceError::UnexpectedToken => f.write_str("Unexpected token in brace expansion"),
29            BraceError::TooManyExpansions(count) => write!(
30                f,
31                "Too many brace expansions ({count} > {MAX_BRACE_EXPANSIONS})"
32            ),
33        }
34    }
35}
36
37impl std::error::Error for BraceError {}
38
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub(crate) enum BraceToken {
41    /// `{`; `idx..end` is its range of variants in the flat expansion table.
42    Open {
43        idx: usize,
44        end: usize,
45    },
46    Comma,
47    Text(String),
48    Close,
49    Eof,
50}
51
52impl BraceToken {
53    fn to_text(&self) -> String {
54        match self {
55            BraceToken::Open { .. } => "{".to_string(),
56            BraceToken::Comma => ",".to_string(),
57            BraceToken::Close => "}".to_string(),
58            BraceToken::Text(t) => t.clone(),
59            BraceToken::Eof => String::new(),
60        }
61    }
62}
63
64/// Tokens of a brace pattern (see [`tokenize`]).
65#[derive(Clone, Debug)]
66pub(crate) struct BraceTokens {
67    /// Ends with [`BraceToken::Eof`].
68    pub tokens: Vec<BraceToken>,
69    /// Some group is nested in another one.
70    pub contains_nested: bool,
71}
72
73fn replace_token_with_string(tokens: &mut [BraceToken], idx: usize) {
74    tokens[idx] = BraceToken::Text(tokens[idx].to_text());
75}
76
77fn append_char(tokens: &mut Vec<BraceToken>, c: char) {
78    if let Some(BraceToken::Text(t)) = tokens.last_mut() {
79        t.push(c);
80    } else {
81        tokens.push(BraceToken::Text(c.to_string()));
82    }
83}
84
85/// Unclosed groups are rolled back innermost first. Everything from the
86/// previous rollback's start onwards is already a fixed point of this scan
87/// (only balanced groups sit between two unclosed opens), so `limit` bounds
88/// the scan and keeps the whole pass linear.
89fn rollback_braces(tokens: &mut [BraceToken], starting_idx: usize, limit: usize) {
90    let mut braces = 0usize;
91    replace_token_with_string(tokens, starting_idx);
92    for i in starting_idx + 1..limit {
93        match tokens[i] {
94            BraceToken::Open { .. } => braces += 1,
95            BraceToken::Close if braces > 0 => braces -= 1,
96            _ if braces > 0 => {}
97            BraceToken::Close | BraceToken::Comma | BraceToken::Text(_) => {
98                replace_token_with_string(tokens, i)
99            }
100            BraceToken::Eof => {}
101        }
102    }
103}
104
105fn flatten_tokens(tokens: Vec<BraceToken>) -> BraceTokens {
106    let mut depth = 0usize;
107    let mut contains_nested = false;
108    let mut out: Vec<BraceToken> = Vec::with_capacity(tokens.len() + 1);
109    for tok in tokens {
110        match tok {
111            BraceToken::Open { .. } => {
112                depth += 1;
113                contains_nested |= depth > 1;
114            }
115            BraceToken::Close => depth = depth.saturating_sub(1),
116            _ => {}
117        }
118        match (out.last_mut(), tok) {
119            (Some(BraceToken::Text(prev)), BraceToken::Text(t)) => prev.push_str(&t),
120            (_, tok) => out.push(tok),
121        }
122    }
123    BraceTokens {
124        tokens: out,
125        contains_nested,
126    }
127}
128
129/// Tokenize a brace pattern. `\X` is a literal `X`; a trailing `\` ends the
130/// input. Groups without a comma and unclosed groups become text.
131pub(crate) fn tokenize(src: &str) -> BraceTokens {
132    struct Pending {
133        tok_idx: usize,
134        has_comma: bool,
135    }
136    let mut tokens = Vec::new();
137    let mut stack: Vec<Pending> = Vec::new();
138    let mut chars = src.chars();
139    while let Some(mut c) = chars.next() {
140        let mut escaped = false;
141        if c == '\\' {
142            let Some(next) = chars.next() else { break };
143            c = next;
144            escaped = true;
145        }
146        if !escaped {
147            if c == '{' {
148                stack.push(Pending {
149                    tok_idx: tokens.len(),
150                    has_comma: false,
151                });
152                tokens.push(BraceToken::Open { idx: 0, end: 0 });
153                continue;
154            }
155            if c == '}' {
156                if let Some(top) = stack.pop() {
157                    if top.has_comma {
158                        tokens.push(BraceToken::Close);
159                    } else {
160                        replace_token_with_string(&mut tokens, top.tok_idx);
161                        tokens.push(BraceToken::Text("}".to_string()));
162                    }
163                    continue;
164                }
165            }
166            if c == ',' {
167                if let Some(top) = stack.last_mut() {
168                    top.has_comma = true;
169                    tokens.push(BraceToken::Comma);
170                    continue;
171                }
172            }
173        }
174        append_char(&mut tokens, c);
175    }
176    let mut limit = tokens.len();
177    while let Some(Pending { tok_idx, .. }) = stack.pop() {
178        rollback_braces(&mut tokens, tok_idx, limit);
179        limit = tok_idx;
180    }
181    let mut flat = flatten_tokens(tokens);
182    flat.tokens.push(BraceToken::Eof);
183    flat
184}
185
186/// Number of words the tokens expand to (0 when there is nothing to expand),
187/// saturated at `u32::MAX`.
188pub(crate) fn calculate_expanded_amount(tokens: &[BraceToken]) -> u32 {
189    struct Entry {
190        segment_product: u32,
191        accumulator: u32,
192    }
193    let mut stack: Vec<Entry> = Vec::new();
194    let mut variant_count = 0u32;
195    for tok in tokens {
196        match tok {
197            BraceToken::Open { .. } => stack.push(Entry {
198                segment_product: 1,
199                accumulator: 0,
200            }),
201            BraceToken::Comma => {
202                if let Some(top) = stack.last_mut() {
203                    top.accumulator = top.accumulator.saturating_add(top.segment_product);
204                    top.segment_product = 1;
205                }
206            }
207            BraceToken::Close => {
208                let Some(entry) = stack.pop() else { continue };
209                let total = entry.accumulator.saturating_add(entry.segment_product);
210                if let Some(parent) = stack.last_mut() {
211                    parent.segment_product = parent.segment_product.saturating_mul(total);
212                } else if variant_count == 0 {
213                    variant_count = total;
214                } else {
215                    variant_count = variant_count.saturating_mul(total);
216                }
217            }
218            _ => {}
219        }
220    }
221    variant_count
222}
223
224fn check_brace_group_count(tokens: &[BraceToken]) -> Result<(), BraceError> {
225    let opens = tokens
226        .iter()
227        .filter(|t| matches!(t, BraceToken::Open { .. }))
228        .count();
229    if opens > MAX_BRACE_GROUPS {
230        return Err(BraceError::TooManyBraces);
231    }
232    Ok(())
233}
234
235/// Output words; keys are allocated in expansion order.
236struct Out {
237    words: Vec<String>,
238    counter: usize,
239}
240
241impl Out {
242    fn new_key(&mut self, from: usize, len: usize) -> usize {
243        let key = self.counter;
244        if key >= self.words.len() {
245            self.words.resize(key + 1, String::new());
246        }
247        let prefix = self.words[from][..len].to_string();
248        self.words[key].push_str(&prefix);
249        self.counter += 1;
250        key
251    }
252}
253
254struct TableEntry {
255    start: usize,
256    end: usize,
257}
258
259fn build_expansion_table(tokens: &mut [BraceToken]) -> Vec<TableEntry> {
260    struct Frame {
261        tok_idx: usize,
262        prev_tok_end: usize,
263    }
264    let mut table = Vec::new();
265    let mut stack: Vec<Frame> = Vec::new();
266    for i in 0..tokens.len() {
267        match tokens[i] {
268            BraceToken::Open { .. } => {
269                tokens[i] = BraceToken::Open {
270                    idx: table.len(),
271                    end: 0,
272                };
273                stack.push(Frame {
274                    tok_idx: i,
275                    prev_tok_end: i,
276                });
277            }
278            BraceToken::Close => {
279                let Some(top) = stack.pop() else { continue };
280                table.push(TableEntry {
281                    start: top.prev_tok_end + 1,
282                    end: i,
283                });
284                if let BraceToken::Open { end, .. } = &mut tokens[top.tok_idx] {
285                    *end = table.len();
286                }
287            }
288            BraceToken::Comma => {
289                let Some(top) = stack.last_mut() else {
290                    continue;
291                };
292                table.push(TableEntry {
293                    start: top.prev_tok_end + 1,
294                    end: i,
295                });
296                top.prev_tok_end = i;
297            }
298            _ => {}
299        }
300    }
301    table
302}
303
304fn expand_flat(
305    tokens: &[BraceToken],
306    table: &[TableEntry],
307    out: &mut Out,
308    key: usize,
309    start: usize,
310    end: usize,
311) {
312    if start >= tokens.len() || end > tokens.len() {
313        return;
314    }
315    for tok in &tokens[start..end] {
316        match tok {
317            BraceToken::Text(t) => out.words[key].push_str(t),
318            BraceToken::Open { idx, end: vend } => {
319                let variants = &table[*idx..*vend];
320                let Some(last) = variants.last() else { return };
321                let skip_over_idx = last.end;
322                let starting_len = out.words[key].len();
323                for (vi, variant) in variants.iter().enumerate() {
324                    let k = if vi == 0 {
325                        key
326                    } else {
327                        out.new_key(key, starting_len)
328                    };
329                    expand_flat(tokens, table, out, k, variant.start, variant.end);
330                    expand_flat(tokens, table, out, k, skip_over_idx, end);
331                }
332                return;
333            }
334            _ => {}
335        }
336    }
337}
338
339enum Node {
340    Text(String),
341    Expansion(Vec<Vec<Node>>),
342}
343
344struct BraceParser<'a> {
345    tokens: &'a [BraceToken],
346    current: usize,
347}
348
349impl BraceParser<'_> {
350    fn parse(&mut self) -> Result<Vec<Node>, BraceError> {
351        check_brace_group_count(self.tokens)?;
352        let mut nodes = Vec::new();
353        while !self.match_eof() {
354            match self.parse_atom()? {
355                Some(atom) => nodes.push(atom),
356                None => break,
357            }
358        }
359        Ok(nodes)
360    }
361
362    fn parse_atom(&mut self) -> Result<Option<Node>, BraceError> {
363        match self.advance() {
364            BraceToken::Open { .. } => Ok(Some(Node::Expansion(self.parse_expansion()?))),
365            BraceToken::Text(t) => Ok(Some(Node::Text(t.clone()))),
366            BraceToken::Eof => Ok(None),
367            _ => Err(BraceError::UnexpectedToken),
368        }
369    }
370
371    fn parse_expansion(&mut self) -> Result<Vec<Vec<Node>>, BraceError> {
372        let mut variants = Vec::new();
373        loop {
374            let mut group = Vec::new();
375            let close = loop {
376                if matches!(self.peek(), BraceToken::Close | BraceToken::Eof) {
377                    self.advance();
378                    break true;
379                }
380                if matches!(self.peek(), BraceToken::Comma) {
381                    self.advance();
382                    break false;
383                }
384                match self.parse_atom()? {
385                    Some(atom) => group.push(atom),
386                    None => break true,
387                }
388            };
389            variants.push(group);
390            if close {
391                return Ok(variants);
392            }
393        }
394    }
395
396    fn match_eof(&mut self) -> bool {
397        if matches!(self.peek(), BraceToken::Eof) {
398            self.advance();
399            return true;
400        }
401        false
402    }
403
404    fn advance(&mut self) -> &BraceToken {
405        if !matches!(self.peek(), BraceToken::Eof) {
406            self.current += 1;
407        }
408        if self.current > 0 {
409            &self.tokens[self.current - 1]
410        } else {
411            self.peek()
412        }
413    }
414
415    fn peek(&self) -> &BraceToken {
416        self.tokens.get(self.current).unwrap_or(&BraceToken::Eof)
417    }
418}
419
420/// Where to continue once a variant group is fully expanded: the rest of the
421/// enclosing group, from atom `next`.
422struct Cont<'a> {
423    group: &'a [Node],
424    next: usize,
425    parent: Option<&'a Cont<'a>>,
426}
427
428fn expand_nested(out: &mut Out, group: &[Node], key: usize, start: usize, cont: Option<&Cont<'_>>) {
429    for (i, node) in group.iter().enumerate().skip(start) {
430        match node {
431            Node::Text(t) => out.words[key].push_str(t),
432            Node::Expansion(variants) => {
433                let here = Cont {
434                    group,
435                    next: i + 1,
436                    parent: cont,
437                };
438                let len = out.words[key].len();
439                for (j, variant) in variants.iter().enumerate() {
440                    let k = if j == 0 { key } else { out.new_key(key, len) };
441                    expand_nested(out, variant, k, 0, Some(&here));
442                }
443                return;
444            }
445        }
446    }
447    if let Some(c) = cont {
448        expand_nested(out, c.group, key, c.next, c.parent);
449    }
450}
451
452/// Expand tokens produced by [`tokenize`] into the `count` words computed by
453/// [`calculate_expanded_amount`].
454pub(crate) fn expand(
455    mut tokens: Vec<BraceToken>,
456    count: u32,
457    contains_nested: bool,
458) -> Result<Vec<String>, BraceError> {
459    check_brace_group_count(&tokens)?;
460    let mut out = Out {
461        words: vec![String::new(); count as usize],
462        counter: 1,
463    };
464    if out.words.is_empty() {
465        out.words.push(String::new());
466    }
467    if !contains_nested {
468        let table = build_expansion_table(&mut tokens);
469        let len = tokens.len();
470        expand_flat(&tokens, &table, &mut out, 0, 0, len);
471    } else {
472        let root = BraceParser {
473            tokens: &tokens,
474            current: 0,
475        }
476        .parse()?;
477        expand_nested(&mut out, &root, 0, 0, None);
478    }
479    Ok(out.words)
480}
481
482/// `$.braces(pattern)`: expand a brace pattern into words.
483pub(crate) fn braces(pattern: &str) -> Result<Vec<String>, BraceError> {
484    let BraceTokens {
485        tokens,
486        contains_nested,
487    } = tokenize(pattern);
488    let count = calculate_expanded_amount(&tokens);
489    if count == 0 {
490        return Ok(vec![pattern.to_string()]);
491    }
492    if count > MAX_BRACE_EXPANSIONS {
493        return Err(BraceError::TooManyExpansions(count));
494    }
495    expand(tokens, count, contains_nested)
496}
497
498#[cfg(test)]
499mod tests {
500    use super::*;
501
502    fn b(p: &str) -> Vec<String> {
503        braces(p).unwrap_or_else(|e| panic!("{p}: {e}"))
504    }
505
506    #[test]
507    fn flat() {
508        assert_eq!(b("echo 123"), ["echo 123"]);
509        assert_eq!(b("echo {123,456}"), ["echo 123", "echo 456"]);
510        assert_eq!(b("{a,b}{c,d}"), ["ac", "ad", "bc", "bd"]);
511        assert_eq!(b(""), [""]);
512        assert_eq!(b("lol {😂,🫵,🤣}"), ["lol 😂", "lol 🫵", "lol 🤣"]);
513        assert_eq!(b("\\{a,b}"), ["\\{a,b}"]);
514        assert_eq!(b("\\{a,b},{c,d}"), ["{a,b},c", "{a,b},d"]);
515        assert_eq!(b("{a}"), ["{a}"]);
516    }
517
518    #[test]
519    fn nested() {
520        assert_eq!(
521            b("echo {123,{456,789},abc}"),
522            ["echo 123", "echo 456", "echo 789", "echo abc"]
523        );
524        assert_eq!(b("{{d,e}{g,h}}"), ["{dg}", "{dh}", "{eg}", "{eh}"]);
525        assert_eq!(b("{a,{b,c}{d,e},f}"), ["a", "bd", "be", "cd", "ce", "f"]);
526        for (pattern, expected) in [
527            ("{x,a{,}b}", &["x", "ab", "ab"][..]),
528            ("{x,{a,}}z", &["xz", "az", "z"]),
529            ("{x,{,a}}z", &["xz", "z", "az"]),
530            ("a{b,c{d,}}e", &["abe", "acde", "ace"]),
531            ("{x,{a,,b}}", &["x", "a", "", "b"]),
532            ("{{a,},x}", &["a", "", "x"]),
533            ("p{q,{r,}{s,}}t", &["pqt", "prst", "prt", "pst", "pt"]),
534        ] {
535            assert_eq!(b(pattern), expected, "{pattern}");
536        }
537        let deep = b("{1,{2,{3,{4,{5,{6,{7,{8,{9,{10,{11,{12,{13,{14,{15,{16,{17}}}}}}}}}}}}}}}}}");
538        assert_eq!(deep.len(), 17);
539        assert_eq!(deep[16], "{17}");
540    }
541
542    #[test]
543    fn literal_outer_group_around_many_groups() {
544        let pattern = format!("{{{}b{}", "{a,".repeat(256), "}".repeat(256));
545        let mut expected = vec!["{a".to_string(); 256];
546        expected.push("{b".to_string());
547        assert_eq!(b(&pattern), expected);
548    }
549
550    #[test]
551    fn errors() {
552        let pattern = format!("{}{}", "{a,".repeat(257), "}".repeat(257));
553        assert_eq!(braces(&pattern), Err(BraceError::TooManyBraces));
554        let pattern = "{a,b}".repeat(17);
555        assert_eq!(
556            braces(&pattern).unwrap_err().to_string(),
557            "Too many brace expansions (131072 > 65536)"
558        );
559        assert_eq!(b(&"{a,b}".repeat(16)).len(), 65536);
560        assert_eq!(
561            BraceError::UnexpectedToken.to_string(),
562            "Unexpected token in brace expansion"
563        );
564    }
565}
command_stream/bun_shell/braces.rs

command_stream/bun_shell/
braces.rs
