Skip to main content

shell/
expansion.rs

1//! Word expansion in the session.
2//!
3//! Expansion runs inside [`crate::core::ShellCore`], because parameter operators and
4//! command substitution need the session: `$(...)` and backticks execute
5//! the inner command through this shell and capture its output, and
6//! `${VAR:=word}` mutates the session environment. Quoting semantics
7//! (`'...'`, `"..."`, backslash, tilde) match the sh family.
8//!
9//! Arithmetic (`$(( ))`, and `(( ))` commands) shares this machinery: the
10//! expression text may contain parameter and command substitutions, which
11//! expand first; the surviving identifiers are then evaluated as references
12//! into the session environment by one evaluator shared with `case`-free
13//! compound commands.
14
15use brush_parser::ast::{self};
16
17use crate::core::ShellCore;
18
19impl<'os> ShellCore<'os> {
20    /// Expands a word with quoting semantics, discarding the glob marker.
21    pub fn expand_word(&mut self, raw: &str) -> String {
22        self.expand_word_with_glob(raw).0
23    }
24
25    /// Expands a word and splits it into fields on the default IFS
26    /// characters (space, tab, newline), as unquoted expansions are in
27    /// real shells: `v="a b"; ls $v` passes two arguments. Characters
28    /// from quoted sections never split.
29    ///
30    /// An empty expansion yields no fields; the caller decides whether an
31    /// empty argument is meaningful.
32    pub fn expand_word_fields(&mut self, raw: &str) -> Vec<String> {
33        let (text, splittable, _glob) = self.expand_word_masked(raw);
34        split_fields(&text, &splittable)
35    }
36
37    /// Expands a word with quoting semantics, reporting whether it contains
38    /// unquoted glob characters.
39    pub fn expand_word_with_glob(&mut self, raw: &str) -> (String, bool) {
40        let mut result = String::new();
41        let mut glob = false;
42        let mut index = 0;
43        let mut at_start = true;
44        let chars: Vec<char> = raw.chars().collect();
45        while index < chars.len() {
46            match chars[index] {
47                '\'' => {
48                    index += 1;
49                    while index < chars.len() && chars[index] != '\'' {
50                        result.push(chars[index]);
51                        index += 1;
52                    }
53                    index += 1;
54                }
55                '"' => {
56                    index += 1;
57                    while index < chars.len() && chars[index] != '"' {
58                        if chars[index] == '\\'
59                            && index + 1 < chars.len()
60                            && matches!(chars[index + 1], '$' | '`' | '"' | '\\')
61                        {
62                            result.push(chars[index + 1]);
63                            index += 2;
64                        } else if chars[index] == '$' {
65                            if let Some((value, consumed)) = self.expand_parameter(&chars[index..])
66                            {
67                                result.push_str(&value);
68                                index += consumed;
69                            } else {
70                                result.push(chars[index]);
71                                index += 1;
72                            }
73                        } else if chars[index] == '`'
74                            && let Some((value, consumed)) =
75                                self.backtick_substitution(&chars, index)
76                        {
77                            result.push_str(&value);
78                            index += consumed;
79                        } else {
80                            result.push(chars[index]);
81                            index += 1;
82                        }
83                    }
84                    index += 1;
85                }
86                '\\' if index + 1 < chars.len() => {
87                    result.push(chars[index + 1]);
88                    index += 2;
89                }
90                '~' if at_start && (index + 1 == chars.len() || chars[index + 1] == '/') => {
91                    result.push_str(self.environment().get("HOME").unwrap_or("/"));
92                    index += 1;
93                }
94                '$' => {
95                    if let Some((value, consumed)) = self.expand_parameter(&chars[index..]) {
96                        result.push_str(&value);
97                        index += consumed;
98                    } else {
99                        result.push(chars[index]);
100                        index += 1;
101                    }
102                }
103                '`' => {
104                    if let Some((value, consumed)) = self.backtick_substitution(&chars, index) {
105                        result.push_str(&value);
106                        index += consumed;
107                    } else {
108                        result.push(chars[index]);
109                        index += 1;
110                    }
111                }
112                '*' | '?' | '[' | ']' => {
113                    glob = true;
114                    result.push(chars[index]);
115                    index += 1;
116                }
117                ch => {
118                    result.push(ch);
119                    index += 1;
120                }
121            }
122            at_start = false;
123        }
124        (result, glob)
125    }
126
127    /// The masked expansion behind field splitting: returns the expanded
128    /// text, a per-character flag marking which characters came from
129    /// *unquoted* parameter or command substitutions (the only positions
130    /// where IFS field splitting may occur), and whether the word carries
131    /// unquoted glob characters.
132    #[allow(clippy::same_item_push)]
133    fn expand_word_masked(&mut self, raw: &str) -> (String, Vec<bool>, bool) {
134        let mut result = String::new();
135        let mut mask: Vec<bool> = Vec::new();
136        let mut glob = false;
137        let mut index = 0;
138        let mut at_start = true;
139        let chars: Vec<char> = raw.chars().collect();
140        while index < chars.len() {
141            match chars[index] {
142                '\'' => {
143                    index += 1;
144                    while index < chars.len() && chars[index] != '\'' {
145                        result.push(chars[index]);
146                        mask.push(false);
147                        index += 1;
148                    }
149                    index += 1;
150                }
151                '"' => {
152                    index += 1;
153                    while index < chars.len() && chars[index] != '"' {
154                        if chars[index] == '\\'
155                            && index + 1 < chars.len()
156                            && matches!(chars[index + 1], '$' | '`' | '"' | '\\')
157                        {
158                            result.push(chars[index + 1]);
159                            mask.push(false);
160                            index += 2;
161                        } else if chars[index] == '$'
162                            && let Some((value, consumed)) = self.expand_parameter(&chars[index..])
163                        {
164                            result.push_str(&value);
165                            for _ in value.chars() {
166                                mask.push(false);
167                            }
168                            index += consumed;
169                        } else if chars[index] == '`'
170                            && let Some((value, consumed)) =
171                                self.backtick_substitution(&chars, index)
172                        {
173                            result.push_str(&value);
174                            for _ in value.chars() {
175                                mask.push(false);
176                            }
177                            index += consumed;
178                        } else {
179                            result.push(chars[index]);
180                            mask.push(false);
181                            index += 1;
182                        }
183                    }
184                    index += 1;
185                }
186                '\\' if index + 1 < chars.len() => {
187                    result.push(chars[index + 1]);
188                    mask.push(false);
189                    index += 2;
190                }
191                '~' if at_start && (index + 1 == chars.len() || chars[index + 1] == '/') => {
192                    let home = self.environment().get("HOME").unwrap_or("/").to_owned();
193                    result.push_str(&home);
194                    for _ in home.chars() {
195                        mask.push(false);
196                    }
197                    index += 1;
198                }
199                '$' => {
200                    let mut value_text = String::new();
201                    if let Some((value, consumed)) = self.expand_parameter(&chars[index..]) {
202                        for ch in value.chars() {
203                            value_text.push(ch);
204                            mask.push(true);
205                        }
206                        index += consumed;
207                    } else {
208                        value_text.push(chars[index]);
209                        mask.push(false);
210                        index += 1;
211                    }
212                    result.push_str(&value_text);
213                }
214                '`' => {
215                    if let Some((value, consumed)) = self.backtick_substitution(&chars, index) {
216                        for ch in value.chars() {
217                            result.push(ch);
218                            mask.push(true);
219                        }
220                        index += consumed;
221                    } else {
222                        result.push(chars[index]);
223                        mask.push(false);
224                        index += 1;
225                    }
226                }
227                '*' | '?' | '[' | ']' => {
228                    glob = true;
229                    result.push(chars[index]);
230                    index += 1;
231                }
232                ch => {
233                    result.push(ch);
234                    mask.push(false);
235                    index += 1;
236                }
237            }
238            at_start = false;
239        }
240        (result, mask, glob)
241    }
242
243    /// `$((...))` arithmetic expansion: finds the balanced closing `))`,
244    /// expands any parameter/command substitutions inside the expression,
245    /// and evaluates it. Returns `None` when the text does not close as
246    /// arithmetic or does not parse as an expression, letting the caller
247    /// fall back to command substitution (the POSIX ambiguity between
248    /// `$((expr))` and `$( (cmd) )`).
249    fn arithmetic_expansion(&mut self, chars: &[char]) -> Option<(String, usize)> {
250        let mut depth = 0i32;
251        let mut end = 2;
252        while end < chars.len() {
253            match chars[end] {
254                '(' => depth += 1,
255                ')' => {
256                    depth -= 1;
257                    if depth == 0 {
258                        break;
259                    }
260                }
261                _ => {}
262            }
263            end += 1;
264        }
265        if depth != 0 || chars.get(end + 1) != Some(&')') || end < 4 {
266            return None;
267        }
268        let inner: String = chars[3..end].iter().collect();
269        // Parameter and command substitutions happen before arithmetic
270        // evaluation; bare identifiers survive expansion as references.
271        let prepared = if inner.contains('$') || inner.contains('`') {
272            self.expand_word(&inner)
273        } else {
274            inner
275        };
276        let value = self.evaluate_arithmetic(&prepared)?;
277        Some((value.to_string(), end + 2))
278    }
279
280    /// Evaluates an arithmetic expression (`$(( ))` expansions and `(( ))`
281    /// commands share this one evaluator).
282    ///
283    /// Identifiers are references into the session environment (unset or
284    /// empty evaluates to 0); the assignment operators mutate it. Overflow,
285    /// division by zero, and array elements fail the evaluation with `None`
286    /// rather than inventing a number.
287    pub(crate) fn evaluate_arithmetic(&mut self, raw: &str) -> Option<i64> {
288        let expr = brush_parser::arithmetic::parse(raw).ok()?;
289        self.arithmetic_value(&expr)
290    }
291
292    /// The value of a variable in arithmetic context.
293    fn arithmetic_variable(&self, name: &str) -> i64 {
294        self.environment()
295            .get(name)
296            .and_then(|value| value.trim().parse::<i64>().ok())
297            .unwrap_or(0)
298    }
299
300    /// Reads an assignment target's current value (`None` for array
301    /// elements).
302    fn arithmetic_target_value(&mut self, target: &ast::ArithmeticTarget) -> Option<i64> {
303        match target {
304            ast::ArithmeticTarget::Variable(name) => Some(self.arithmetic_variable(name)),
305            ast::ArithmeticTarget::ArrayElement(..) => None,
306        }
307    }
308
309    /// Stores an assignment target's value (`None` for array elements).
310    fn arithmetic_assign(&mut self, target: &ast::ArithmeticTarget, value: i64) -> Option<()> {
311        match target {
312            ast::ArithmeticTarget::Variable(name) => {
313                self.environment_mut().set(name, value.to_string());
314                Some(())
315            }
316            ast::ArithmeticTarget::ArrayElement(..) => None,
317        }
318    }
319
320    /// Applies one binary operator to two evaluated sides.
321    fn arithmetic_binary(
322        &self,
323        operator: ast::BinaryOperator,
324        left: i64,
325        right: i64,
326    ) -> Option<i64> {
327        use ast::BinaryOperator as Op;
328        match operator {
329            Op::Add => left.checked_add(right),
330            Op::Subtract => left.checked_sub(right),
331            Op::Multiply => left.checked_mul(right),
332            Op::Divide if right != 0 => left.checked_div(right),
333            Op::Modulo if right != 0 => left.checked_rem(right),
334            // Division and remainder by zero fail the evaluation.
335            Op::Divide | Op::Modulo => None,
336            Op::Power => u32::try_from(right)
337                .ok()
338                .and_then(|exponent| pow(left, exponent)),
339            Op::ShiftLeft => u32::try_from(right)
340                .ok()
341                .and_then(|shift| left.checked_shl(shift)),
342            Op::ShiftRight => u32::try_from(right)
343                .ok()
344                .and_then(|shift| left.checked_shr(shift)),
345            Op::BitwiseAnd => Some(left & right),
346            Op::BitwiseOr => Some(left | right),
347            Op::BitwiseXor => Some(left ^ right),
348            Op::LessThan => Some(i64::from(left < right)),
349            Op::LessThanOrEqualTo => Some(i64::from(left <= right)),
350            Op::GreaterThan => Some(i64::from(left > right)),
351            Op::GreaterThanOrEqualTo => Some(i64::from(left >= right)),
352            Op::Equals => Some(i64::from(left == right)),
353            Op::NotEquals => Some(i64::from(left != right)),
354            // Logical operators short-circuit at their call site; the comma
355            // operator's left side is evaluated there too.
356            Op::LogicalAnd | Op::LogicalOr | Op::Comma => None,
357        }
358    }
359
360    /// Recursively evaluates one arithmetic expression node.
361    fn arithmetic_value(&mut self, expr: &ast::ArithmeticExpr) -> Option<i64> {
362        match expr {
363            ast::ArithmeticExpr::Literal(value) => Some(*value),
364            ast::ArithmeticExpr::Reference(target) => self.arithmetic_target_value(target),
365            ast::ArithmeticExpr::Conditional(condition, then, otherwise) => {
366                let choice = self.arithmetic_value(condition)?;
367                if choice == 0 {
368                    self.arithmetic_value(otherwise)
369                } else {
370                    self.arithmetic_value(then)
371                }
372            }
373            ast::ArithmeticExpr::UnaryOp(operator, operand) => {
374                let value = self.arithmetic_value(operand)?;
375                match operator {
376                    ast::UnaryOperator::UnaryPlus => Some(value),
377                    ast::UnaryOperator::UnaryMinus => value.checked_neg(),
378                    ast::UnaryOperator::BitwiseNot => Some(!value),
379                    ast::UnaryOperator::LogicalNot => Some(i64::from(value == 0)),
380                }
381            }
382            ast::ArithmeticExpr::BinaryOp(operator, left, right) => {
383                use ast::BinaryOperator as Op;
384                match operator {
385                    // Short-circuit forms must not always evaluate both sides.
386                    Op::LogicalAnd => {
387                        if self.arithmetic_value(left)? == 0 {
388                            return Some(0);
389                        }
390                        Some(i64::from(self.arithmetic_value(right)? != 0))
391                    }
392                    Op::LogicalOr => {
393                        if self.arithmetic_value(left)? != 0 {
394                            return Some(1);
395                        }
396                        Some(i64::from(self.arithmetic_value(right)? != 0))
397                    }
398                    Op::Comma => {
399                        self.arithmetic_value(left)?;
400                        self.arithmetic_value(right)
401                    }
402                    _ => {
403                        let left = self.arithmetic_value(left)?;
404                        let right = self.arithmetic_value(right)?;
405                        self.arithmetic_binary(*operator, left, right)
406                    }
407                }
408            }
409            ast::ArithmeticExpr::Assignment(target, value) => {
410                let value = self.arithmetic_value(value)?;
411                self.arithmetic_assign(target, value)?;
412                Some(value)
413            }
414            ast::ArithmeticExpr::BinaryAssignment(operator, target, value) => {
415                let current = self.arithmetic_target_value(target)?;
416                let value = self.arithmetic_value(value)?;
417                let updated = self.arithmetic_binary(*operator, current, value)?;
418                self.arithmetic_assign(target, updated)?;
419                Some(updated)
420            }
421            ast::ArithmeticExpr::UnaryAssignment(operator, target) => {
422                let current = self.arithmetic_target_value(target)?;
423                let updated = match operator {
424                    ast::UnaryAssignmentOperator::PrefixIncrement
425                    | ast::UnaryAssignmentOperator::PostfixIncrement => current.checked_add(1)?,
426                    ast::UnaryAssignmentOperator::PrefixDecrement
427                    | ast::UnaryAssignmentOperator::PostfixDecrement => current.checked_sub(1)?,
428                };
429                self.arithmetic_assign(target, updated)?;
430                match operator {
431                    ast::UnaryAssignmentOperator::PrefixIncrement
432                    | ast::UnaryAssignmentOperator::PrefixDecrement => Some(updated),
433                    ast::UnaryAssignmentOperator::PostfixIncrement
434                    | ast::UnaryAssignmentOperator::PostfixDecrement => Some(current),
435                }
436            }
437        }
438    }
439
440    /// Expands `$VAR`, `${VAR}`, the parameter operators (`${VAR:-x}`,
441    /// `:=`, `:?`, `:+`, `#`, `##`, `%`, `%%`, `${#VAR}`), and `$(...)`
442    /// command substitution at the start of `chars`.
443    ///
444    /// Returns the value and the number of characters consumed, or `None`
445    /// when `chars` does not start with a parameter reference.
446    fn expand_parameter(&mut self, chars: &[char]) -> Option<(String, usize)> {
447        if chars.first() != Some(&'$') {
448            return None;
449        }
450        // `$(...)` command substitution — unless it is arithmetic:
451        // `$((...))` is an arithmetic expansion, recognized by
452        // the doubled parenthesis.
453        if chars.get(1) == Some(&'(') {
454            if chars.get(2) == Some(&'(')
455                && let Some(expansion) = self.arithmetic_expansion(chars)
456            {
457                return Some(expansion);
458            }
459            return self.command_substitution(chars, 0);
460        }
461        if chars.get(1) == Some(&'{') {
462            let close = chars.iter().position(|ch| *ch == '}')?;
463            if close <= 2 {
464                return None;
465            }
466            let body: String = chars[2..close].iter().collect();
467            let consumed = close + 1;
468
469            // `${#VAR}`: the length of the value.
470            if let Some(name) = body.strip_prefix('#') {
471                let length = self.environment().get(name).unwrap_or("").chars().count();
472                return Some((length.to_string(), consumed));
473            }
474
475            // `${VAR:op word}` with `:-`, `:=`, `:?`, `:+`.
476            {
477                for operator in [":-", ":=", ":?", ":+"] {
478                    if let Some((name, word)) = body.split_once(operator) {
479                        let value = self.environment().get(name).unwrap_or("").to_owned();
480                        let empty = value.is_empty();
481                        let word = word.to_owned();
482                        let result = match operator {
483                            ":-" => {
484                                if empty {
485                                    word
486                                } else {
487                                    value
488                                }
489                            }
490                            ":=" => {
491                                if empty {
492                                    self.environment_mut().set(name, word.clone());
493                                    word
494                                } else {
495                                    value
496                                }
497                            }
498                            ":?" => {
499                                // Real shells print the message and abort;
500                                // here the message substitutes into the
501                                // word, keeping the failure visible.
502                                if empty {
503                                    format!("{name}: {word}")
504                                } else {
505                                    value
506                                }
507                            }
508                            ":+" => {
509                                if empty {
510                                    String::new()
511                                } else {
512                                    word
513                                }
514                            }
515                            _ => unreachable!(),
516                        };
517                        return Some((result, consumed));
518                    }
519                }
520            }
521
522            // `${VAR#pat}`, `${VAR##pat}`, `${VAR%pat}`, `${VAR%%pat}`.
523            for operator in ["##", "#", "%%", "%"] {
524                if let Some((name, pattern)) = body.split_once(operator) {
525                    let value = self.environment().get(name).unwrap_or("").to_owned();
526                    let stripped = strip_pattern(
527                        &value,
528                        pattern,
529                        operator == "##" || operator == "%%",
530                        operator == "%" || operator == "%%",
531                    );
532                    return Some((stripped, consumed));
533                }
534            }
535            // `${1}`, `${10}`, … consult the positional frame first.
536            let value = self
537                .positional_value(&body)
538                .unwrap_or_else(|| self.environment().get(&body).unwrap_or("").to_owned());
539            return Some((value, consumed));
540        }
541        // Single-character special parameters like `$?` and `$$`; digits,
542        // `0`, `#`, `@`, and `*` consult the positional frame first.
543        if let Some(second) = chars.get(1)
544            && matches!(second, '?' | '$' | '!' | '#' | '*' | '@' | '-' | '0'..='9')
545        {
546            if let Some(value) = self.positional_value(&second.to_string()) {
547                return Some((value, 2));
548            }
549            let name = second.to_string();
550            let value = self.environment().get(&name).unwrap_or("").to_owned();
551            return Some((value, 2));
552        }
553        let start = 1;
554        let mut end = start;
555        while end < chars.len() && (chars[end].is_alphanumeric() || chars[end] == '_') {
556            end += 1;
557        }
558        if end == start {
559            return None;
560        }
561        let name: String = chars[start..end].iter().collect();
562        let value = self.environment().get(&name).unwrap_or("").to_owned();
563        Some((value, end))
564    }
565
566    /// `$(...)` command substitution: executes the inner command through
567    /// this shell and returns its captured stdout.
568    fn command_substitution(&mut self, chars: &[char], start: usize) -> Option<(String, usize)> {
569        if chars.get(start) != Some(&'$') || chars.get(start + 1) != Some(&'(') {
570            return None;
571        }
572        let mut depth = 0usize;
573        let mut end = start + 2;
574        while end < chars.len() {
575            match chars[end] {
576                '(' => depth += 1,
577                ')' if depth == 0 => break,
578                ')' => depth -= 1,
579                _ => {}
580            }
581            end += 1;
582        }
583        if end >= chars.len() {
584            return None;
585        }
586        let inner: String = chars[start + 2..end].iter().collect();
587        let output = self.execute_captured(&inner);
588        Some((output, end - start + 1))
589    }
590
591    /// Backtick command substitution: `` `command` ``.
592    fn backtick_substitution(&mut self, chars: &[char], start: usize) -> Option<(String, usize)> {
593        let mut end = start + 1;
594        while end < chars.len() && chars[end] != '`' {
595            end += 1;
596        }
597        if end >= chars.len() {
598            return None;
599        }
600        let inner: String = chars[start + 1..end].iter().collect();
601        let output = self.execute_captured(&inner);
602        Some((output, end - start + 1))
603    }
604
605    /// Executes a command substitution and captures its stdout, with
606    /// trailing newlines stripped like the real shells.
607    fn execute_captured(&mut self, source: &str) -> String {
608        let mut stdin = engine::BytesInput::new(Vec::new());
609        let mut stdout = engine::BytesOutput::new();
610        let mut stderr = engine::BytesOutput::new();
611        let _ = self.execute(source, &mut stdin, &mut stdout, &mut stderr);
612        let text = String::from_utf8_lossy(&stdout.into_bytes()).into_owned();
613        text.trim_end_matches('\n').to_owned()
614    }
615}
616
617/// Raises `base` to a non-negative `exponent`.
618///
619/// `checked_pow` iterates the exponent — a few billion multiplications for
620/// `1 ** 4294967295`, which never overflows and would hang the session.
621/// Bases whose powers are closed-form (`-1`, `0`, `1`) resolve
622/// immediately; everything else falls back to the checked iteration,
623/// which overflows within a handful of multiplications.
624fn pow(base: i64, exponent: u32) -> Option<i64> {
625    match base {
626        0 => Some(if exponent == 0 { 1 } else { 0 }),
627        1 => Some(1),
628        -1 => Some(if exponent.is_multiple_of(2) { 1 } else { -1 }),
629        base => base.checked_pow(exponent),
630    }
631}
632
633/// Strips the shortest or longest prefix/suffix of `value` that matches a
634/// glob pattern (`${VAR#pat}`, `${VAR##pat}`, `${VAR%pat}`, `${VAR%%pat}`).
635fn strip_pattern(value: &str, pattern: &str, longest: bool, suffix: bool) -> String {
636    let mut matches: Vec<usize> = Vec::new();
637    let count = value.chars().count();
638    for length in 0..=count {
639        // The part being stripped: the prefix (first `length` chars) or
640        // the suffix (last `length` chars) must match the pattern.
641        let candidate: String = if suffix {
642            value.chars().skip(count - length).collect()
643        } else {
644            value.chars().take(length).collect()
645        };
646        if glob_match(&candidate, pattern) {
647            matches.push(length);
648        }
649    }
650    let chosen = if longest {
651        matches.last().copied().unwrap_or(0)
652    } else {
653        matches.first().copied().unwrap_or(0)
654    };
655    if suffix {
656        value.chars().take(count - chosen).collect()
657    } else {
658        value.chars().skip(chosen).collect()
659    }
660}
661
662/// Simple glob matching for `*`, `?`, and `[...]` character classes
663/// (shared with the core's filesystem globbing).
664///
665/// Classes support single characters, inclusive ranges (`a-z`), and
666/// negation with a leading `!` or `^` (`[!a-z]`). A `]` directly after the
667/// opening `[` (or after the negation mark) is a literal member; an
668/// unterminated `[` matches a literal `[`.
669pub(crate) fn glob_match(text: &str, pattern: &str) -> bool {
670    let text: Vec<char> = text.chars().collect();
671    let pattern: Vec<char> = pattern.chars().collect();
672    // Classic wildcard DP: `dp[i][j]` is whether `text[..i]` matches
673    // `pattern[..j]`. A star is either empty (dp[i][j-1]) or eats one more
674    // character (dp[i-1][j]), so every state resolves in constant time:
675    // O(text.len() * pattern.len()) total, with no backtracking tree.
676    let rows = text.len() + 1;
677    let cols = pattern.len() + 1;
678    let mut dp = vec![false; rows * cols];
679    dp[0] = true;
680    // Leading stars match the empty prefix.
681    for j in 1..=pattern.len() {
682        if pattern[j - 1] == '*' {
683            dp[j] = dp[j - 1];
684        }
685    }
686    for i in 1..=text.len() {
687        // A character class consumes one text character but several
688        // pattern positions; those jumps land at `class.end` and must not
689        // be clobbered by the ascending `j` pass, so they are applied
690        // after the row is computed.
691        let mut jumps: Vec<(usize, bool)> = Vec::new();
692        for j in 1..=pattern.len() {
693            let at = i * cols + j;
694            let ch = pattern[j - 1];
695            match ch {
696                '*' => dp[at] = dp[at - cols] || dp[at - 1],
697                '?' => dp[at] = dp[at - cols - 1],
698                '[' => match parse_class(&pattern, j - 1) {
699                    Some(class) => {
700                        dp[at] = false;
701                        let reached = dp[at - cols - 1] && class.matches(text[i - 1]);
702                        jumps.push((class.end, reached));
703                    }
704                    // Unterminated `[`: a literal bracket.
705                    None => dp[at] = dp[at - cols - 1] && text[i - 1] == '[',
706                },
707                c => dp[at] = dp[at - cols - 1] && text[i - 1] == c,
708            }
709        }
710        for (end, reached) in jumps {
711            if reached {
712                dp[i * cols + end] = true;
713            }
714        }
715    }
716    dp[rows * cols - 1]
717}
718
719/// A parsed `[...]` character class: its member ranges, whether it negates
720/// (`[!a-z]`), and the index just past the closing `]`.
721struct CharacterClass {
722    /// Inclusive member ranges.
723    members: Vec<(char, char)>,
724    /// Whether the class negates its members.
725    negate: bool,
726    /// The pattern index just past the closing `]`.
727    end: usize,
728}
729
730/// Parses the class whose opening `[` is at `pattern[start]`.
731///
732/// Returns `None` when the class never closes.
733fn parse_class(pattern: &[char], start: usize) -> Option<CharacterClass> {
734    let mut index = start + 1;
735    let negate = matches!(pattern.get(index), Some('!') | Some('^'));
736    if negate {
737        index += 1;
738    }
739    let mut members = Vec::new();
740    let mut first = true;
741    while index < pattern.len() {
742        // A `]` in first position is a literal member.
743        if pattern[index] == ']' && !first {
744            return Some(CharacterClass {
745                members,
746                negate,
747                end: index + 1,
748            });
749        }
750        first = false;
751        if index + 2 < pattern.len() && pattern[index + 1] == '-' && pattern[index + 2] != ']' {
752            members.push((pattern[index], pattern[index + 2]));
753            index += 3;
754        } else {
755            members.push((pattern[index], pattern[index]));
756            index += 1;
757        }
758    }
759    None
760}
761
762impl CharacterClass {
763    /// Whether `ch` is inside (or, when negating, outside) the member
764    /// ranges.
765    fn matches(&self, ch: char) -> bool {
766        let contained = self.members.iter().any(|(lo, hi)| ch >= *lo && ch <= *hi);
767        contained != self.negate
768    }
769}
770
771mod tests {
772    #[allow(unused_imports)]
773    use super::glob_match;
774
775    #[test]
776    fn stars_and_questions_match() {
777        assert!(glob_match("hello", "h*o"));
778        assert!(glob_match("hello", "h?llo"));
779        assert!(!glob_match("hello", "h?lo"));
780        assert!(glob_match("", "*"));
781        assert!(glob_match("anything", "*"));
782    }
783
784    #[test]
785    fn classes_match_members_ranges_and_negation() {
786        assert!(glob_match("a", "[abc]"));
787        assert!(!glob_match("d", "[abc]"));
788        assert!(glob_match("m", "[a-z]"));
789        assert!(glob_match("file1.txt", "file[0-9].txt"));
790        assert!(!glob_match("file12.txt", "file[0-9].txt"));
791        assert!(glob_match("d", "[!abc]"));
792        assert!(glob_match("q", "[^abc]"));
793        assert!(!glob_match("a", "[!abc]"));
794    }
795
796    #[test]
797    fn class_edge_cases_follow_posix() {
798        // `]` in first position is a literal member.
799        assert!(glob_match("]", "[]]"));
800        // `-` at either edge is a literal.
801        assert!(glob_match("-", "[a-]"));
802        assert!(glob_match("+", "[+-/]"));
803        // An unterminated `[` matches a literal `[`.
804        assert!(glob_match("[", "["));
805        assert!(!glob_match("[x", "["));
806        // Classes compose with stars.
807        assert!(glob_match("abc", "*[bc]"));
808    }
809}
810
811/// Splits expanded text into fields at IFS whitespace boundaries
812/// (space, tab, newline), but only at positions the expansion marked as
813/// splittable — characters from quoted sections never separate fields.
814///
815/// Runs of splitting whitespace collapse into one boundary, and leading
816/// and trailing boundaries are dropped: `a  b` is two fields, ` a` one.
817fn split_fields(text: &str, mask: &[bool]) -> Vec<String> {
818    let chars: Vec<char> = text.chars().collect();
819    let mut fields = Vec::new();
820    let mut current = String::new();
821    for (index, ch) in chars.iter().enumerate() {
822        let splittable = mask.get(index).copied().unwrap_or(false);
823        if splittable && matches!(ch, ' ' | '\t' | '\n') {
824            if !current.is_empty() {
825                fields.push(std::mem::take(&mut current));
826            }
827        } else {
828            current.push(*ch);
829        }
830    }
831    if !current.is_empty() {
832        fields.push(current);
833    }
834    fields
835}