1use brush_parser::ast::{self};
16
17use crate::core::ShellCore;
18
19impl<'os> ShellCore<'os> {
20 pub fn expand_word(&mut self, raw: &str) -> String {
22 self.expand_word_with_glob(raw).0
23 }
24
25 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 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 #[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 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 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 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 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 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 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 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 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 Op::LogicalAnd | Op::LogicalOr | Op::Comma => None,
357 }
358 }
359
360 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 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 fn expand_parameter(&mut self, chars: &[char]) -> Option<(String, usize)> {
447 if chars.first() != Some(&'$') {
448 return None;
449 }
450 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 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 {
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 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 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 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 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 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 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 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
617fn 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
633fn 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 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
662pub(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 let rows = text.len() + 1;
677 let cols = pattern.len() + 1;
678 let mut dp = vec![false; rows * cols];
679 dp[0] = true;
680 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 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 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
719struct CharacterClass {
722 members: Vec<(char, char)>,
724 negate: bool,
726 end: usize,
728}
729
730fn 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 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 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 assert!(glob_match("]", "[]]"));
800 assert!(glob_match("-", "[a-]"));
802 assert!(glob_match("+", "[+-/]"));
803 assert!(glob_match("[", "["));
805 assert!(!glob_match("[x", "["));
806 assert!(glob_match("abc", "*[bc]"));
808 }
809}
810
811fn 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}