Shell: Allow parts of globs to be named in match expressions

This patchset allows a match expression to have a list of names for its
glob parts, which are assigned to the matched values in the body of the
match.
For example,
```sh
stuff=foobarblahblah/target_{1..30}
for $stuff {
    match $it {
        */* as (dir sub) {
            echo "doing things with $sub in $dir"
            make -C $dir $sub # or whatever...
        }
    }
}
```

With this, match expressions are now significantly more powerful!

6 files changed, 115 insertions, 10 deletions

diff --git a/Shell/AST.cpp b/Shell/AST.cpp
index f6dd6484b5..e225eb916e 100644
--- a/Shell/AST.cpp
+++ b/Shell/AST.cpp
@@ -1520,7 +1520,23 @@ void MatchExpr::dump(int level) const
     print_indented(String::format("(named: %s)", m_expr_name.characters()), level + 1);
     print_indented("(entries)", level + 1);
     for (auto& entry : m_entries) {
-        print_indented("(match)", level + 2);
+        StringBuilder builder;
+        builder.append("(match");
+        if (entry.match_names.has_value()) {
+            builder.append(" to names (");
+            bool first = true;
+            for (auto& name : entry.match_names.value()) {
+                if (!first)
+                    builder.append(' ');
+                first = false;
+                builder.append(name);
+            }
+            builder.append("))");
+
+        } else {
+            builder.append(')');
+        }
+        print_indented(builder.string_view(), level + 2);
         for (auto& node : entry.options)
             node.dump(level + 3);
         print_indented("(execute)", level + 2);
@@ -1536,13 +1552,16 @@ RefPtr<Value> MatchExpr::run(RefPtr<Shell> shell)
     auto value = m_matched_expr->run(shell)->resolve_without_cast(shell);
     auto list = value->resolve_as_list(shell);
 
-    auto list_matches = [&](auto&& pattern) {
+    auto list_matches = [&](auto&& pattern, auto& spans) {
         if (pattern.size() != list.size())
             return false;
 
         for (size_t i = 0; i < pattern.size(); ++i) {
-            if (!list[i].matches(pattern[i]))
+            Vector<AK::MaskSpan> mask_spans;
+            if (!list[i].matches(pattern[i], mask_spans))
                 return false;
+            for (auto& span : mask_spans)
+                spans.append(list[i].substring(span.start, span.length));
         }
 
         return true;
@@ -1554,7 +1573,7 @@ RefPtr<Value> MatchExpr::run(RefPtr<Shell> shell)
             pattern.append(static_cast<const Glob*>(&option)->text());
         } else if (option.is_bareword()) {
             pattern.append(static_cast<const BarewordLiteral*>(&option)->text());
-        } else if (option.is_list()) {
+        } else {
             auto list = option.run(shell);
             option.for_each_entry(shell, [&](auto&& value) {
                 pattern.append(value->resolve_as_list(nullptr)); // Note: 'nullptr' incurs special behaviour,
@@ -1572,11 +1591,21 @@ RefPtr<Value> MatchExpr::run(RefPtr<Shell> shell)
 
     for (auto& entry : m_entries) {
         for (auto& option : entry.options) {
-            if (list_matches(resolve_pattern(option))) {
-                if (entry.body)
+            Vector<String> spans;
+            if (list_matches(resolve_pattern(option), spans)) {
+                if (entry.body) {
+                    if (entry.match_names.has_value()) {
+                        size_t i = 0;
+                        for (auto& name : entry.match_names.value()) {
+                            if (spans.size() > i)
+                                shell->set_local_variable(name, create<AST::StringValue>(spans[i]));
+                            ++i;
+                        }
+                    }
                     return entry.body->run(shell);
-                else
+                } else {
                     return create<AST::ListValue>({});
+                }
             }
         }
     }
@@ -1606,6 +1635,9 @@ void MatchExpr::highlight_in_editor(Line::Editor& editor, Shell& shell, Highligh
 
         for (auto& position : entry.pipe_positions)
             editor.stylize({ position.start_offset, position.end_offset }, { Line::Style::Foreground(Line::Style::XtermColor::Yellow) });
+
+        if (entry.match_as_position.has_value())
+            editor.stylize({ entry.match_as_position.value().start_offset, entry.match_as_position.value().end_offset }, { Line::Style::Foreground(Line::Style::XtermColor::Yellow) });
     }
 }
 
diff --git a/Shell/AST.h b/Shell/AST.h
index 98e2bb4462..8a11f29bc5 100644
--- a/Shell/AST.h
+++ b/Shell/AST.h
@@ -912,6 +912,8 @@ private:
 
 struct MatchEntry {
     NonnullRefPtrVector<Node> options;
+    Optional<Vector<String>> match_names;
+    Optional<Position> match_as_position;
     Vector<Position> pipe_positions;
     RefPtr<Node> body;
 };
diff --git a/Shell/Formatter.cpp b/Shell/Formatter.cpp
index 35a162afd6..05975c4aca 100644
--- a/Shell/Formatter.cpp
+++ b/Shell/Formatter.cpp
@@ -452,6 +452,17 @@ void Formatter::visit(const AST::MatchExpr* node)
             }
 
             current_builder().append(' ');
+            if (entry.match_names.has_value() && !entry.match_names.value().is_empty()) {
+                current_builder().append("as (");
+                auto first = true;
+                for (auto& name : entry.match_names.value()) {
+                    if (!first)
+                        current_builder().append(' ');
+                    first = false;
+                    current_builder().append(name);
+                }
+                current_builder().append(") ");
+            }
             in_new_block([&] {
                 if (entry.body)
                     entry.body->visit(*this);
diff --git a/Shell/Parser.cpp b/Shell/Parser.cpp
index 464f5ff465..a6a59f5412 100644
--- a/Shell/Parser.cpp
+++ b/Shell/Parser.cpp
@@ -752,10 +752,12 @@ AST::MatchEntry Parser::parse_match_entry()
 
     NonnullRefPtrVector<AST::Node> patterns;
     Vector<AST::Position> pipe_positions;
+    Optional<Vector<String>> match_names;
+    Optional<AST::Position> match_as_position;
 
     auto pattern = parse_match_pattern();
     if (!pattern)
-        return { {}, {}, create<AST::SyntaxError>("Expected a pattern in 'match' body") };
+        return { {}, {}, {}, {}, create<AST::SyntaxError>("Expected a pattern in 'match' body") };
 
     patterns.append(pattern.release_nonnull());
 
@@ -782,6 +784,32 @@ AST::MatchEntry Parser::parse_match_entry()
 
     consume_while(is_any_of(" \t\n"));
 
+    auto as_start_position = m_offset;
+    auto as_start_line = line();
+    if (expect("as")) {
+        match_as_position = AST::Position { as_start_position, m_offset, as_start_line, line() };
+        consume_while(is_any_of(" \t\n"));
+        if (!expect('(')) {
+            if (!error)
+                error = create<AST::SyntaxError>("Expected an explicit list of identifiers after a pattern 'as'");
+        } else {
+            match_names = Vector<String>();
+            for (;;) {
+                consume_while(is_whitespace);
+                auto name = consume_while(is_word_character);
+                if (name.is_empty())
+                    break;
+                match_names.value().append(move(name));
+            }
+
+            if (!expect(')')) {
+                if (!error)
+                    error = create<AST::SyntaxError>("Expected a close paren ')' to end the identifier list of pattern 'as'");
+            }
+        }
+        consume_while(is_any_of(" \t\n"));
+    }
+
     if (!expect('{')) {
         if (!error)
             error = create<AST::SyntaxError>("Expected an open brace '{' to start a match entry body");
@@ -799,7 +827,7 @@ AST::MatchEntry Parser::parse_match_entry()
     else if (error)
         body = error;
 
-    return { move(patterns), move(pipe_positions), move(body) };
+    return { move(patterns), move(match_names), move(match_as_position), move(pipe_positions), move(body) };
 }
 
 RefPtr<AST::Node> Parser::parse_match_pattern()
diff --git a/Shell/Parser.h b/Shell/Parser.h
index ec18dfd2da..cf5ee4eb6d 100644
--- a/Shell/Parser.h
+++ b/Shell/Parser.h
@@ -185,7 +185,9 @@ subshell :: '{' toplevel '}'
 
 match_expr :: 'match' ws+ expression ws* ('as' ws+ identifier)? '{' match_entry* '}'
 
-match_entry :: match_pattern ws* '{' toplevel '}'
+match_entry :: match_pattern ws* (as identifier_list)? '{' toplevel '}'
+
+identifier_list :: '(' (identifier ws*)* ')'
 
 match_pattern :: expression (ws* '|' ws* expression)*
 
diff --git a/Shell/Tests/match.sh b/Shell/Tests/match.sh
index 0b2640e9cc..1f1809166c 100644
--- a/Shell/Tests/match.sh
+++ b/Shell/Tests/match.sh
@@ -51,3 +51,33 @@ match "$(echo)" {
 };
 
 test "$result" = yes || echo invalid result $result for string subst match && exit 1
+
+match (foo bar) {
+    (f? *) as (x y) {
+        result=fail
+    }
+    (f* b*) as (x y) {
+        if [ "$x" = oo -a "$y" = ar ] {
+            result=yes
+        } else {
+            result=fail
+        }
+    }
+}
+
+test "$result" = yes || echo invalid result $result for subst match with name && exit 1
+
+match (foo bar baz) {
+    (f? * *z) as (x y z) {
+        result=fail
+    }
+    (f* b* *z) as (x y z) {
+        if [ "$x" = oo -a "$y" = ar -a "$z" = ba ] {
+            result=yes
+        } else {
+            result=fail
+        }
+    }
+}
+
+test "$result" = yes || echo invalid result $result for subst match with name 2 && exit 1