bashkit 0.19.0

//! Brace expansion (`{a,b,c}`, `{1..5}`).
//!
//! Split out of the monolithic interpreter module; these are pure
//! `&self` helpers driven from the word-expansion path.

use super::*;

impl Interpreter {
    /// Check if a string contains glob characters
    /// Expand brace patterns like {a,b,c} or {1..5}
    /// Returns a Vec of expanded strings, or a single-element Vec if no braces
    /// THREAT[TM-DOS-042]: Cap total expansion count to prevent combinatorial OOM.
    pub(super) fn expand_braces(&self, s: &str) -> Vec<String> {
        const MAX_BRACE_EXPANSION_TOTAL: usize = 100_000;
        let mut count = 0;
        let mut bytes = 0;
        self.expand_braces_capped(s, &mut count, &mut bytes, MAX_BRACE_EXPANSION_TOTAL, 0)
    }

    /// THREAT[TM-DOS-042]: The combinatorial `count` cap alone is insufficient
    /// because it is only incremented *after* each recursive call returns, so
    /// the first DFS path descends to the full nesting/sequence depth (one
    /// level per brace group) with `count` still zero. An input like
    /// `{a,b}{a,b}...` repeated tens of thousands of times (well under
    /// `max_input_bytes`) therefore stack-overflows the worker thread, and
    /// allocates O(depth * suffix) memory, before the count cap or execution
    /// timeout can fire. The `depth` cap bounds the descent up front;
    /// legitimate scripts never approach this many nested/sequential groups.
    fn expand_braces_capped(
        &self,
        s: &str,
        count: &mut usize,
        bytes: &mut usize,
        max: usize,
        recursion_depth: usize,
    ) -> Vec<String> {
        const MAX_BRACE_EXPANSION_DEPTH: usize = 100;
        if *count >= max
            || *bytes >= Self::MAX_EXPANSION_RESULT_BYTES
            || recursion_depth >= MAX_BRACE_EXPANSION_DEPTH
        {
            return vec![s.to_string()];
        }

        // Find the first brace that has a matching close brace
        let mut depth = 0;
        let mut brace_start = None;
        let mut brace_end = None;
        let chars: Vec<char> = s.chars().collect();

        let mut escaped = false;
        for (i, &ch) in chars.iter().enumerate() {
            if escaped {
                escaped = false;
                continue;
            }
            if ch == '\\' {
                escaped = true;
                continue;
            }
            match ch {
                '{' => {
                    if depth == 0 {
                        brace_start = Some(i);
                    }
                    depth += 1;
                }
                '}' => {
                    if depth > 0 {
                        depth -= 1;
                    }
                    if depth == 0 && brace_start.is_some() {
                        brace_end = Some(i);
                        break;
                    }
                }
                _ => {}
            }
        }

        // No valid brace pattern found
        let (start, end) = match (brace_start, brace_end) {
            (Some(s), Some(e)) => (s, e),
            // An unclosed `{` is literal; a later group may still close
            // (`{{a,b}` -> `{a {b`).
            (Some(open), None) => {
                return self.expand_after_literal_brace(
                    &chars,
                    open,
                    count,
                    bytes,
                    max,
                    recursion_depth,
                );
            }
            _ => return vec![s.to_string()],
        };

        let prefix: String = chars[..start].iter().collect();
        let suffix: String = chars[end + 1..].iter().collect();
        let brace_content: String = chars[start + 1..end].iter().collect();

        // Brace content with leading/trailing space is not expanded
        if brace_content.starts_with(' ') || brace_content.ends_with(' ') {
            return self.expand_after_literal_brace(
                &chars,
                start,
                count,
                bytes,
                max,
                recursion_depth,
            );
        }

        // Check for range expansion like {1..5} or {a..z}
        if let Some(range_result) = self.try_expand_range(&brace_content) {
            let mut results = Vec::new();
            for item in range_result {
                if *count >= max || *bytes >= Self::MAX_EXPANSION_RESULT_BYTES {
                    break;
                }
                let expanded = format!("{}{}{}", prefix, item, suffix);
                let sub =
                    self.expand_braces_capped(&expanded, count, bytes, max, recursion_depth + 1);
                *count += sub.len();
                *bytes += sub.iter().map(String::len).sum::<usize>();
                results.extend(sub);
            }
            return results;
        }

        // List expansion like {a,b,c}
        // Need to split by comma, but respect nested braces
        let items = self.split_brace_items(&brace_content);
        if items.len() <= 1 {
            // Not a valid brace expansion (e.g., just {foo}): the `{` stays
            // literal and later groups still expand (`{x}{a,b}` -> `{x}a {x}b`).
            return self.expand_after_literal_brace(
                &chars,
                start,
                count,
                bytes,
                max,
                recursion_depth,
            );
        }

        let mut results = Vec::new();
        for item in items {
            if *count >= max || *bytes >= Self::MAX_EXPANSION_RESULT_BYTES {
                break;
            }
            let expanded = format!("{}{}{}", prefix, item, suffix);
            let sub = self.expand_braces_capped(&expanded, count, bytes, max, recursion_depth + 1);
            *count += sub.len();
            *bytes += sub.iter().map(String::len).sum::<usize>();
            results.extend(sub);
        }

        results
    }

    /// The group opening at `start` is not a brace expansion: keep text up to
    /// and including that `{` and expand whatever follows it.
    fn expand_after_literal_brace(
        &self,
        chars: &[char],
        start: usize,
        count: &mut usize,
        bytes: &mut usize,
        max: usize,
        recursion_depth: usize,
    ) -> Vec<String> {
        let head: String = chars[..=start].iter().collect();
        let rest: String = chars[start + 1..].iter().collect();
        self.expand_braces_capped(&rest, count, bytes, max, recursion_depth + 1)
            .into_iter()
            .map(|tail| format!("{head}{tail}"))
            .collect()
    }

    /// Brace-expand a word before any other expansion, as bash does.
    ///
    /// Only unquoted literal text takes part: every other part (variables,
    /// command substitutions, quoted segments) is an opaque atom, so text an
    /// expansion produces is never brace-expanded (`y='{a,b}'; echo $y`
    /// prints `{a,b}`) and `{1..$n}` stays literal. Atoms are carried through
    /// the string-based expander as private-use placeholder characters and
    /// mapped back to the original parts afterwards.
    ///
    /// Backslashes stay escapes, as in the lexer's quoted-glob convention
    /// (`a"{"b,c}{1,2}` arrives as `a\{b,c}{1,2}`). Fully quoted words never
    /// brace-expand.
    pub(super) fn brace_expand_word(&self, word: &Word) -> Option<Vec<Word>> {
        if word.quoted && !word.has_unquoted_glob {
            return None;
        }
        let quoted_at = |i: usize| word.part_quoted.get(i).copied().unwrap_or(word.quoted);
        let has_brace =
            word.parts.iter().enumerate().any(
                |(i, p)| matches!(p, WordPart::Literal(t) if !quoted_at(i) && t.contains('{')),
            );
        if !has_brace {
            return None;
        }
        let mut text = String::new();
        for (i, part) in word.parts.iter().enumerate() {
            match part {
                WordPart::Literal(t) if !quoted_at(i) => {
                    for ch in t.chars() {
                        if is_brace_placeholder(ch) {
                            // Cannot encode this word; leave it unexpanded.
                            return None;
                        }
                        text.push(ch);
                    }
                }
                _ => text.push(placeholder_for(i)?),
            }
        }
        let expanded = self.expand_braces(&text);
        if expanded.len() == 1 && expanded[0] == text {
            return None;
        }
        let mut words = Vec::with_capacity(expanded.len());
        for item in expanded {
            // An unquoted brace item that expands to nothing is dropped
            // (`echo {,a}` prints `a`).
            if item.is_empty() {
                continue;
            }
            let mut parts = Vec::new();
            let mut part_quoted = Vec::new();
            let mut lit = String::new();
            for ch in item.chars() {
                if let Some(i) = placeholder_index(ch) {
                    if !lit.is_empty() {
                        parts.push(WordPart::Literal(std::mem::take(&mut lit)));
                        part_quoted.push(false);
                    }
                    parts.push(word.parts[i].clone());
                    part_quoted.push(quoted_at(i));
                } else {
                    lit.push(ch);
                }
            }
            if !lit.is_empty() {
                parts.push(WordPart::Literal(lit));
                part_quoted.push(false);
            }
            words.push(Word {
                parts,
                quoted: word.quoted,
                has_unquoted_glob: word.has_unquoted_glob,
                part_quoted,
                raw: None,
            });
        }
        Some(words)
    }

    /// Try to expand a range like 1..5, a..z, or 1..10..2
    /// THREAT[TM-DOS-041]: Cap range size to prevent OOM from {1..999999999}
    pub(super) fn try_expand_range(&self, content: &str) -> Option<Vec<String>> {
        /// Maximum number of elements in a brace range expansion
        const MAX_BRACE_RANGE: u64 = 10_000;

        // Check for .. separator: accept {start..end} or {start..end..step}
        let parts: Vec<&str> = content.split("..").collect();
        if parts.len() != 2 && parts.len() != 3 {
            return None;
        }

        let start = parts[0];
        let end = parts[1];

        // Try numeric range
        if let (Ok(start_num), Ok(end_num)) = (start.parse::<i64>(), end.parse::<i64>()) {
            // Parse optional step (default: 1 or -1 based on direction)
            let step: i64 = if parts.len() == 3 {
                match parts[2].parse::<i64>() {
                    // bash treats a zero step as 1.
                    Ok(0) => 1,
                    Ok(s) => s,
                    Err(_) => return None,
                }
            } else if start_num <= end_num {
                1
            } else {
                -1
            };

            let abs_step = step.unsigned_abs() as u128;
            let abs_diff = (end_num as i128 - start_num as i128).unsigned_abs();
            let range_size = abs_diff / abs_step + 1;
            if range_size > MAX_BRACE_RANGE as u128 {
                return None; // Treat as literal — too large
            }

            let mut results = Vec::new();
            // Bash behavior: direction is determined by start/end. Keep stepping in i128 so
            // huge but valid i64 steps cannot overflow after the precomputed range cap passes.
            let step_magnitude = step.unsigned_abs() as i128;
            let effective_step = if start_num <= end_num {
                step_magnitude
            } else {
                -step_magnitude
            };

            // `{01..10}`: a leading zero on either end pads every item to the
            // wider end's length (the `-` counts toward the width).
            let zero_padded = |n: &str| {
                let digits = n.strip_prefix('-').unwrap_or(n);
                digits.len() > 1 && digits.starts_with('0')
            };
            let width = if zero_padded(start) || zero_padded(end) {
                start.len().max(end.len())
            } else {
                0
            };
            let mut i = start_num as i128;
            let end = end_num as i128;
            if effective_step > 0 {
                while i <= end {
                    results.push(format!("{i:0width$}"));
                    i += effective_step;
                }
            } else {
                while i >= end {
                    results.push(format!("{i:0width$}"));
                    i += effective_step;
                }
            }
            return Some(results);
        }

        // Try character range (single chars only)
        if start.len() == 1 && end.len() == 1 {
            let start_char = start.chars().next().unwrap();
            let end_char = end.chars().next().unwrap();

            if start_char.is_ascii_alphabetic() && end_char.is_ascii_alphabetic() {
                let step: i64 = if parts.len() == 3 {
                    match parts[2].parse::<i64>() {
                        Ok(0) => 1,
                        Ok(s) => s,
                        Err(_) => return None,
                    }
                } else {
                    1
                };
                let abs_step = step.unsigned_abs();

                let mut results = Vec::new();
                let start_byte = u64::from(start_char as u8);
                let end_byte = u64::from(end_char as u8);

                if start_byte <= end_byte {
                    let mut b = start_byte;
                    while b <= end_byte {
                        results.push(((b as u8) as char).to_string());
                        b = match b.checked_add(abs_step) {
                            Some(v) => v,
                            None => break,
                        };
                    }
                } else {
                    let mut b = start_byte;
                    while b >= end_byte {
                        results.push(((b as u8) as char).to_string());
                        b = match b.checked_sub(abs_step) {
                            Some(v) => v,
                            None => break,
                        };
                    }
                }
                return Some(results);
            }
        }

        None
    }

    /// Split brace content by commas, respecting nested braces
    fn split_brace_items(&self, content: &str) -> Vec<String> {
        let mut items = Vec::new();
        let mut current = String::new();
        let mut depth = 0;
        let mut escaped = false;

        for ch in content.chars() {
            if escaped {
                escaped = false;
                current.push(ch);
                continue;
            }
            match ch {
                '\\' => {
                    escaped = true;
                    current.push(ch);
                }
                '{' => {
                    depth += 1;
                    current.push(ch);
                }
                '}' => {
                    depth -= 1;
                    current.push(ch);
                }
                ',' if depth == 0 => {
                    items.push(current);
                    current = String::new();
                }
                _ => {
                    current.push(ch);
                }
            }
        }
        items.push(current);

        items
    }
}

/// Opaque word part `i` is carried as `BASE + 1 + i`.
const BRACE_PLACEHOLDER_BASE: u32 = 0xF0000;
/// Words with more parts than this are not brace-expanded.
const BRACE_MAX_PARTS: u32 = 0xFFF0;

fn is_brace_placeholder(ch: char) -> bool {
    (BRACE_PLACEHOLDER_BASE..=BRACE_PLACEHOLDER_BASE + BRACE_MAX_PARTS).contains(&(ch as u32))
}

fn placeholder_for(i: usize) -> Option<char> {
    let i = u32::try_from(i).ok().filter(|i| *i < BRACE_MAX_PARTS)?;
    char::from_u32(BRACE_PLACEHOLDER_BASE + 1 + i)
}

fn placeholder_index(ch: char) -> Option<usize> {
    let c = ch as u32;
    (c > BRACE_PLACEHOLDER_BASE && c <= BRACE_PLACEHOLDER_BASE + BRACE_MAX_PARTS)
        .then(|| (c - BRACE_PLACEHOLDER_BASE - 1) as usize)
}