brace_expansion/
lib.rs

1//! # brace-expansion — bash-style brace expansion
2//!
3//! Expand brace patterns the way `bash` does: `a{b,c}d` becomes `["abd", "acd"]`,
4//! `{1..3}` becomes `["1", "2", "3"]`, with nested sets, numeric and alphabetic
5//! sequences (with an optional step and zero-padding), and backslash escaping. A
6//! faithful Rust port of the [`brace-expansion`](https://www.npmjs.com/package/brace-expansion)
7//! npm package (the expander behind `minimatch`/`glob`). Zero dependencies and
8//! `#![no_std]`.
9//!
10//! ```
11//! use brace_expansion::expand;
12//!
13//! assert_eq!(expand("a{b,c}d"), ["abd", "acd"]);
14//! assert_eq!(expand("{1..3}"), ["1", "2", "3"]);
15//! assert_eq!(expand("{a..c}"), ["a", "b", "c"]);
16//! assert_eq!(expand("{01..03}"), ["01", "02", "03"]);
17//! assert_eq!(expand("a{b,c{d,e}}f"), ["abf", "acdf", "acef"]);
18//! ```
19
20#![no_std]
21#![doc(html_root_url = "https://docs.rs/brace-expansion/0.1.0")]
22// Index arithmetic mirrors balanced-match's `-1`/`indexOf` logic; every cast is on a
23// value already bounded by the input length.
24#![allow(
25    clippy::cast_possible_truncation,
26    clippy::cast_sign_loss,
27    clippy::cast_possible_wrap
28)]
29
30extern crate alloc;
31
32use alloc::format;
33use alloc::string::{String, ToString};
34use alloc::vec;
35use alloc::vec::Vec;
36
37// Compile-test the README's examples as part of `cargo test`.
38#[cfg(doctest)]
39#[doc = include_str!("../README.md")]
40struct ReadmeDoctests;
41
42/// The default cap on the number of generated results, matching the npm package.
43pub const EXPANSION_MAX: usize = 100_000;
44
45/// A bound on brace-nesting recursion depth, so pathologically nested input degrades
46/// gracefully instead of overflowing the stack. Kept well below what a small (2 MiB)
47/// thread stack tolerates; real patterns nest only a handful of levels.
48const MAX_DEPTH: u32 = 256;
49
50// Sentinels used to hide escaped characters during expansion. They are wrapped in
51// NUL bytes, which do not appear in realistic brace patterns (an input that
52// literally contains these markers would round-trip incorrectly).
53const ESC_SLASH: &str = "\u{0}SLASH\u{0}";
54const ESC_OPEN: &str = "\u{0}OPEN\u{0}";
55const ESC_CLOSE: &str = "\u{0}CLOSE\u{0}";
56const ESC_COMMA: &str = "\u{0}COMMA\u{0}";
57const ESC_PERIOD: &str = "\u{0}PERIOD\u{0}";
58
59/// Expand a brace pattern, returning every resulting string in order.
60///
61/// An empty input yields an empty list. The number of results is capped at
62/// [`EXPANSION_MAX`]; use [`expand_with_max`] to choose a different limit.
63///
64/// ```
65/// assert_eq!(brace_expansion::expand("{a,b}{c,d}"), ["ac", "ad", "bc", "bd"]);
66/// ```
67#[must_use]
68pub fn expand(pattern: &str) -> Vec<String> {
69    expand_with_max(pattern, EXPANSION_MAX)
70}
71
72/// Expand a brace pattern, capping the number of results at `max`.
73#[must_use]
74pub fn expand_with_max(pattern: &str, max: usize) -> Vec<String> {
75    if pattern.is_empty() {
76        return Vec::new();
77    }
78    // Bash 4.3 preserves a leading `{}`; mirror that by escaping it.
79    let pattern = match pattern.strip_prefix("{}") {
80        Some(rest) => format!("\\{{\\}}{rest}"),
81        None => pattern.to_string(),
82    };
83
84    expand_inner(&escape_braces(&pattern), max, true, 0)
85        .iter()
86        .map(|s| unescape_braces(s))
87        .collect()
88}
89
90fn escape_braces(s: &str) -> String {
91    // Order matters: collapse escaped backslashes (`\\`) first, then `\{ \} \, \.`.
92    s.replace("\\\\", ESC_SLASH)
93        .replace("\\{", ESC_OPEN)
94        .replace("\\}", ESC_CLOSE)
95        .replace("\\,", ESC_COMMA)
96        .replace("\\.", ESC_PERIOD)
97}
98
99fn unescape_braces(s: &str) -> String {
100    s.replace(ESC_SLASH, "\\")
101        .replace(ESC_OPEN, "{")
102        .replace(ESC_CLOSE, "}")
103        .replace(ESC_COMMA, ",")
104        .replace(ESC_PERIOD, ".")
105}
106
107fn embrace(s: &str) -> String {
108    let mut out = String::with_capacity(s.len() + 2);
109    out.push('{');
110    out.push_str(s);
111    out.push('}');
112    out
113}
114
115/// `parseInt`-style numeric value: the integer if it parses, otherwise the first
116/// character's code point. Integers beyond `i64` saturate (they only occur in
117/// pathological sequences, which the result cap bounds anyway).
118fn numeric(s: &str) -> i64 {
119    match s.parse::<i64>() {
120        Ok(n) => n,
121        Err(_) if is_int(s) => {
122            if s.starts_with('-') {
123                i64::MIN
124            } else {
125                i64::MAX
126            }
127        }
128        Err(_) => s.chars().next().map_or(0, |c| c as i64),
129    }
130}
131
132/// Whether `el` is zero-padded (`/^-?0\d/`).
133fn is_padded(el: &str) -> bool {
134    let body = el.strip_prefix('-').unwrap_or(el).as_bytes();
135    body.len() >= 2 && body[0] == b'0' && body[1].is_ascii_digit()
136}
137
138fn is_int(s: &str) -> bool {
139    let body = s.strip_prefix('-').unwrap_or(s);
140    !body.is_empty() && body.bytes().all(|b| b.is_ascii_digit())
141}
142
143fn is_single_letter(s: &str) -> bool {
144    let mut chars = s.chars();
145    matches!((chars.next(), chars.next()), (Some(c), None) if c.is_ascii_alphabetic())
146}
147
148fn is_numeric_sequence(body: &str) -> bool {
149    let parts: Vec<&str> = body.split("..").collect();
150    matches!(parts.len(), 2 | 3) && parts.iter().all(|p| is_int(p))
151}
152
153fn is_alpha_sequence(body: &str) -> bool {
154    let parts: Vec<&str> = body.split("..").collect();
155    match parts.len() {
156        2 => is_single_letter(parts[0]) && is_single_letter(parts[1]),
157        3 => is_single_letter(parts[0]) && is_single_letter(parts[1]) && is_int(parts[2]),
158        _ => false,
159    }
160}
161
162/// Whether `post` matches `/,(?!,).*\}/`: a comma not followed by a comma, with a
163/// `}` somewhere after it.
164fn has_dangling_close(post: &str) -> bool {
165    let chars: Vec<char> = post.chars().collect();
166    for i in 0..chars.len() {
167        if chars[i] == ',' && chars.get(i + 1) != Some(&',') && chars[i + 1..].contains(&'}') {
168            return true;
169        }
170    }
171    false
172}
173
174// ---------------------------------------------------------------------------
175// balanced-match: find the first balanced `{ … }`
176// ---------------------------------------------------------------------------
177
178/// Find the first balanced `{ … }` and return `(pre, body, post)`.
179fn balanced(s: &str) -> Option<(String, String, String)> {
180    let chars: Vec<char> = s.chars().collect();
181    let (start, end) = range(&chars)?;
182    Some((
183        chars[..start].iter().collect(),
184        chars[start + 1..end].iter().collect(),
185        chars[end + 1..].iter().collect(),
186    ))
187}
188
189fn index_of(s: &[char], c: char, from: i64) -> i64 {
190    let start = if from < 0 { 0 } else { from as usize };
191    if start >= s.len() {
192        return -1;
193    }
194    match s[start..].iter().position(|&x| x == c) {
195        Some(p) => (start + p) as i64,
196        None => -1,
197    }
198}
199
200/// Port of balanced-match's `range` for `a = '{'`, `b = '}'`.
201#[allow(clippy::many_single_char_names)] // names mirror the reference implementation
202fn range(s: &[char]) -> Option<(usize, usize)> {
203    let (a, b) = ('{', '}');
204    let mut ai = index_of(s, a, 0);
205    let mut bi = index_of(s, b, ai + 1);
206    let mut i = ai;
207    let mut result: Option<(i64, i64)> = None;
208
209    if ai >= 0 && bi > 0 {
210        let mut begs: Vec<i64> = Vec::new();
211        let mut left = s.len() as i64;
212        let mut right: i64 = -1;
213        let mut right_set = false;
214
215        while i >= 0 && result.is_none() {
216            if i == ai {
217                begs.push(i);
218                ai = index_of(s, a, i + 1);
219            } else if begs.len() == 1 {
220                if let Some(r) = begs.pop() {
221                    result = Some((r, bi));
222                }
223            } else {
224                if let Some(beg) = begs.pop() {
225                    if beg < left {
226                        left = beg;
227                        right = bi;
228                        right_set = true;
229                    }
230                }
231                bi = index_of(s, b, i + 1);
232            }
233            i = if ai < bi && ai >= 0 { ai } else { bi };
234        }
235
236        if !begs.is_empty() && right_set {
237            result = Some((left, right));
238        }
239    }
240
241    result.map(|(l, r)| (l as usize, r as usize))
242}
243
244/// Split `str` on top-level commas, treating nested `{ … }` sets as single members.
245fn parse_comma_parts(s: &str, depth: u32) -> Vec<String> {
246    if s.is_empty() {
247        return vec![String::new()];
248    }
249    let split_plain = || s.split(',').map(ToString::to_string).collect();
250    if depth > MAX_DEPTH {
251        return split_plain();
252    }
253    let Some((pre, body, post)) = balanced(s) else {
254        return split_plain();
255    };
256
257    let mut p: Vec<String> = pre.split(',').map(ToString::to_string).collect();
258    let last = p.len() - 1;
259    p[last].push('{');
260    p[last].push_str(&body);
261    p[last].push('}');
262
263    let mut post_parts = parse_comma_parts(&post, depth + 1);
264    if !post.is_empty() && !post_parts.is_empty() {
265        let first = post_parts.remove(0);
266        p[last].push_str(&first);
267        p.extend(post_parts);
268    }
269    p
270}
271
272fn expand_inner(s: &str, max: usize, is_top: bool, depth: u32) -> Vec<String> {
273    if depth > MAX_DEPTH {
274        return vec![s.to_string()];
275    }
276    let Some((pre, body, post_str)) = balanced(s) else {
277        return vec![s.to_string()];
278    };
279
280    let post = if post_str.is_empty() {
281        vec![String::new()]
282    } else {
283        expand_inner(&post_str, max, false, depth + 1)
284    };
285
286    let mut expansions: Vec<String> = Vec::new();
287
288    if pre.ends_with('$') {
289        for p in post.iter().take(max) {
290            expansions.push(format!("{pre}{{{body}}}{p}"));
291        }
292        return expansions;
293    }
294
295    let is_numeric_seq = is_numeric_sequence(&body);
296    let is_alpha_seq = is_alpha_sequence(&body);
297    let is_sequence = is_numeric_seq || is_alpha_seq;
298    let is_options = body.contains(',');
299
300    if !is_sequence && !is_options {
301        if has_dangling_close(&post_str) {
302            let rebuilt = format!("{pre}{{{body}{ESC_CLOSE}{post_str}");
303            return expand_inner(&rebuilt, max, true, depth + 1);
304        }
305        return vec![s.to_string()];
306    }
307
308    let n: Vec<String> = if is_sequence {
309        body.split("..").map(ToString::to_string).collect()
310    } else {
311        let parsed = parse_comma_parts(&body, depth + 1);
312        if parsed.len() == 1 {
313            let embraced: Vec<String> = expand_inner(&parsed[0], max, false, depth + 1)
314                .iter()
315                .map(|x| embrace(x))
316                .collect();
317            if embraced.len() == 1 {
318                return post
319                    .iter()
320                    .map(|p| format!("{pre}{}{p}", embraced[0]))
321                    .collect();
322            }
323            embraced
324        } else {
325            parsed
326        }
327    };
328
329    let big_n: Vec<String> = if is_sequence {
330        sequence(&n, is_alpha_seq, max)
331    } else {
332        let mut v = Vec::new();
333        for part in &n {
334            v.extend(expand_inner(part, max, false, depth + 1));
335        }
336        v
337    };
338
339    for item in &big_n {
340        for p in &post {
341            if expansions.len() >= max {
342                break;
343            }
344            let expansion = format!("{pre}{item}{p}");
345            if !is_top || is_sequence || !expansion.is_empty() {
346                expansions.push(expansion);
347            }
348        }
349    }
350
351    expansions
352}
353
354/// Generate the members of a numeric or alphabetic sequence (`n` is the `..`-split
355/// body, length 2 or 3).
356#[allow(clippy::many_single_char_names)] // names mirror the reference implementation
357fn sequence(n: &[String], is_alpha: bool, max: usize) -> Vec<String> {
358    let x = numeric(&n[0]);
359    let y = numeric(&n[1]);
360    let width = n[0].chars().count().max(n[1].chars().count());
361    let mut incr: i64 = if n.len() == 3 {
362        numeric(&n[2]).saturating_abs().max(1)
363    } else {
364        1
365    };
366    let reverse = y < x;
367    if reverse {
368        incr = -incr;
369    }
370    let pad = n.iter().any(|e| is_padded(e));
371
372    let mut out = Vec::new();
373    let mut i = x;
374    loop {
375        let in_range = if reverse { i >= y } else { i <= y };
376        if !in_range || out.len() >= max {
377            break;
378        }
379        if is_alpha {
380            match u32::try_from(i).ok().and_then(char::from_u32) {
381                Some('\\') | None => out.push(String::new()),
382                Some(c) => out.push(c.to_string()),
383            }
384        } else {
385            out.push(pad_number(i, width, pad));
386        }
387        // Stop rather than overflow when a sequence runs to the i64 boundary.
388        match i.checked_add(incr) {
389            Some(next) => i = next,
390            None => break,
391        }
392    }
393    out
394}
395
396fn pad_number(i: i64, width: usize, pad: bool) -> String {
397    let mut c = i.to_string();
398    if pad {
399        let need = width as i64 - c.chars().count() as i64;
400        if need > 0 {
401            let zeros = "0".repeat(need as usize);
402            c = if i < 0 {
403                let digits = c.strip_prefix('-').unwrap_or("").to_string();
404                format!("-{zeros}{digits}")
405            } else {
406                format!("{zeros}{c}")
407            };
408        }
409    }
410    c
411}
brace_expansion/lib.rs

brace_expansion/
lib.rs
