Shell: Add a 'for' loop

Closes #2760.
This commit adds a 'for' loop, and tweaks the syntax slightly to make &&
bind more tightly than || (allowing for `expr && if_ok || if_bad`) :^)

6 files changed, 334 insertions, 46 deletions

diff --git a/Shell/AST.cpp b/Shell/AST.cpp
index fe167773c4..a1096eccd0 100644
--- a/Shell/AST.cpp
+++ b/Shell/AST.cpp
@@ -732,6 +732,88 @@ Fd2FdRedirection::~Fd2FdRedirection()
 {
 }
 
+void ForLoop::dump(int level) const
+{
+    Node::dump(level);
+    print_indented(String::format("%s in\n", m_variable_name.characters()), level + 1);
+    m_iterated_expression->dump(level + 2);
+    print_indented("Running", level + 1);
+    if (m_block)
+        m_block->dump(level + 2);
+    else
+        print_indented("(null)", level + 2);
+}
+
+RefPtr<Value> ForLoop::run(RefPtr<Shell> shell)
+{
+    if (!m_block)
+        return create<ListValue>({});
+
+    Vector<RefPtr<Value>> values;
+    auto resolved = m_iterated_expression->run(shell)->resolve_without_cast(shell);
+    if (resolved->is_list_without_resolution())
+        values = static_cast<ListValue*>(resolved.ptr())->values();
+    else
+        values = create<ListValue>(resolved->resolve_as_list(shell))->values();
+
+    for (auto& value : values) {
+        auto frame = shell->push_frame();
+        shell->set_local_variable(m_variable_name, value);
+
+        auto block_value = m_block->run(shell)->resolve_without_cast(shell);
+        if (block_value->is_job()) {
+            auto job = static_cast<JobValue*>(block_value.ptr())->job();
+            if (!job || job->is_running_in_background())
+                continue;
+            shell->block_on_job(job);
+        }
+    }
+
+    return create<ListValue>({});
+}
+
+void ForLoop::highlight_in_editor(Line::Editor& editor, Shell& shell, HighlightMetadata metadata)
+{
+    editor.stylize({ m_position.start_offset, m_position.start_offset + 3 }, { Line::Style::Foreground(Line::Style::XtermColor::Yellow) });
+    if (m_in_kw_position.has_value())
+        editor.stylize({ m_in_kw_position.value(), m_in_kw_position.value() + 2 }, { Line::Style::Foreground(Line::Style::XtermColor::Yellow) });
+
+    metadata.is_first_in_list = false;
+    m_iterated_expression->highlight_in_editor(editor, shell, metadata);
+
+    metadata.is_first_in_list = true;
+    if (m_block)
+        m_block->highlight_in_editor(editor, shell, metadata);
+}
+
+HitTestResult ForLoop::hit_test_position(size_t offset)
+{
+    if (!position().contains(offset))
+        return {};
+
+    if (auto result = m_iterated_expression->hit_test_position(offset); result.matching_node)
+        return result;
+
+    return m_block->hit_test_position(offset);
+}
+
+ForLoop::ForLoop(Position position, String variable_name, RefPtr<AST::Node> iterated_expr, RefPtr<AST::Node> block, Optional<size_t> in_kw_position)
+    : Node(move(position))
+    , m_variable_name(move(variable_name))
+    , m_iterated_expression(move(iterated_expr))
+    , m_block(move(block))
+    , m_in_kw_position(move(in_kw_position))
+{
+    if (m_iterated_expression->is_syntax_error())
+        set_is_syntax_error(m_iterated_expression->syntax_error_node());
+    else if (m_block && m_block->is_syntax_error())
+        set_is_syntax_error(m_block->syntax_error_node());
+}
+
+ForLoop::~ForLoop()
+{
+}
+
 void Glob::dump(int level) const
 {
     Node::dump(level);
diff --git a/Shell/AST.h b/Shell/AST.h
index 58945126f4..9873bbbca8 100644
--- a/Shell/AST.h
+++ b/Shell/AST.h
@@ -578,6 +578,24 @@ private:
     int dest_fd { -1 };
 };
 
+class ForLoop final : public Node {
+public:
+    ForLoop(Position, String variable_name, RefPtr<AST::Node> iterated_expr, RefPtr<AST::Node> block, Optional<size_t> in_kw_position = {});
+    virtual ~ForLoop();
+
+private:
+    virtual void dump(int level) const override;
+    virtual RefPtr<Value> run(RefPtr<Shell>) override;
+    virtual void highlight_in_editor(Line::Editor&, Shell&, HighlightMetadata = {}) override;
+    virtual HitTestResult hit_test_position(size_t) override;
+    virtual String class_name() const override { return "ForLoop"; }
+
+    String m_variable_name;
+    RefPtr<AST::Node> m_iterated_expression;
+    RefPtr<AST::Node> m_block;
+    Optional<size_t> m_in_kw_position;
+};
+
 class Glob final : public Node {
 public:
     Glob(Position, String);
diff --git a/Shell/Parser.cpp b/Shell/Parser.cpp
index 4a56761f65..5b964b5602 100644
--- a/Shell/Parser.cpp
+++ b/Shell/Parser.cpp
@@ -144,24 +144,41 @@ RefPtr<AST::Node> Parser::parse_toplevel()
 
 RefPtr<AST::Node> Parser::parse_sequence()
 {
+    consume_while(is_any_of(" \t\n"));
+
     auto rule_start = push_start();
     auto var_decls = parse_variable_decls();
 
     switch (peek()) {
+    case '}':
+        return var_decls;
     case ';':
-    case '\n':
+    case '\n': {
+        if (!var_decls)
+            break;
+
         consume_while(is_any_of("\n;"));
-        break;
+        auto rest = parse_sequence();
+        if (rest)
+            return create<AST::Sequence>(move(var_decls), move(rest));
+        return var_decls;
+    }
     default:
         break;
     }
 
-    auto pipe_seq = parse_pipe_sequence();
-    if (!pipe_seq)
+    RefPtr<AST::Node> first = nullptr;
+    if (auto control_structure = parse_control_structure())
+        first = control_structure;
+
+    if (!first)
+        first = parse_or_logical_sequence();
+
+    if (!first)
         return var_decls;
 
     if (var_decls)
-        pipe_seq = create<AST::Sequence>(move(var_decls), move(pipe_seq));
+        first = create<AST::Sequence>(move(var_decls), move(first));
 
     consume_while(is_whitespace);
 
@@ -170,42 +187,20 @@ RefPtr<AST::Node> Parser::parse_sequence()
     case '\n':
         consume_while(is_any_of("\n;"));
         if (auto expr = parse_sequence()) {
-            return create<AST::Sequence>(move(pipe_seq), move(expr)); // Sequence
+            return create<AST::Sequence>(move(first), move(expr)); // Sequence
         }
-        return pipe_seq;
+        return first;
     case '&': {
-        auto execute_pipe_seq = create<AST::Execute>(pipe_seq);
+        auto execute_pipe_seq = first->would_execute() ? first : static_cast<RefPtr<AST::Node>>(create<AST::Execute>(first));
         consume();
-        if (peek() == '&') {
-            consume();
-            if (auto expr = parse_sequence()) {
-                return create<AST::And>(move(execute_pipe_seq), create<AST::Execute>(move(expr))); // And
-            }
-            return execute_pipe_seq;
-        }
-
-        auto bg = create<AST::Background>(move(pipe_seq)); // Execute Background
+        auto bg = create<AST::Background>(move(first)); // Execute Background
         if (auto rest = parse_sequence())
             return create<AST::Sequence>(move(bg), move(rest)); // Sequence Background Sequence
 
         return bg;
     }
-    case '|': {
-        auto execute_pipe_seq = create<AST::Execute>(pipe_seq);
-        consume();
-        if (peek() != '|') {
-            putback();
-            return execute_pipe_seq;
-        }
-        consume();
-        if (auto expr = parse_sequence()) {
-            return create<AST::Or>(move(execute_pipe_seq), create<AST::Execute>(move(expr))); // Or
-        }
-        putback();
-        return execute_pipe_seq;
-    }
     default:
-        return pipe_seq;
+        return first;
     }
 }
 
@@ -269,6 +264,50 @@ RefPtr<AST::Node> Parser::parse_variable_decls()
     return create<AST::VariableDeclarations>(move(variables));
 }
 
+RefPtr<AST::Node> Parser::parse_or_logical_sequence()
+{
+    consume_while(is_whitespace);
+    auto rule_start = push_start();
+    auto and_sequence = parse_and_logical_sequence();
+    if (!and_sequence)
+        return nullptr;
+
+    consume_while(is_whitespace);
+    auto saved_offset = m_offset;
+    if (!expect("||")) {
+        m_offset = saved_offset;
+        return and_sequence;
+    }
+
+    auto right_and_sequence = parse_and_logical_sequence();
+    if (!right_and_sequence)
+        right_and_sequence = create<AST::SyntaxError>("Expected an expression after '||'");
+
+    return create<AST::Or>(create<AST::Execute>(move(and_sequence)), create<AST::Execute>(move(right_and_sequence)));
+}
+
+RefPtr<AST::Node> Parser::parse_and_logical_sequence()
+{
+    consume_while(is_whitespace);
+    auto rule_start = push_start();
+    auto pipe_sequence = parse_pipe_sequence();
+    if (!pipe_sequence)
+        return nullptr;
+
+    consume_while(is_whitespace);
+    auto saved_offset = m_offset;
+    if (!expect("&&")) {
+        m_offset = saved_offset;
+        return pipe_sequence;
+    }
+
+    auto right_pipe_sequence = parse_pipe_sequence();
+    if (!right_pipe_sequence)
+        right_pipe_sequence = create<AST::SyntaxError>("Expected an expression after '&&'");
+
+    return create<AST::And>(create<AST::Execute>(move(pipe_sequence)), create<AST::Execute>(move(right_pipe_sequence)));
+}
+
 RefPtr<AST::Node> Parser::parse_pipe_sequence()
 {
     auto rule_start = push_start();
@@ -318,6 +357,80 @@ RefPtr<AST::Node> Parser::parse_command()
     return create<AST::Join>(move(redir), command); // Join Command Command
 }
 
+RefPtr<AST::Node> Parser::parse_control_structure()
+{
+    auto rule_start = push_start();
+    consume_while(is_whitespace);
+    if (auto for_loop = parse_for_loop())
+        return for_loop;
+
+    return nullptr;
+}
+
+RefPtr<AST::Node> Parser::parse_for_loop()
+{
+    auto rule_start = push_start();
+    if (!expect("for")) {
+        m_offset = rule_start->offset;
+        return nullptr;
+    }
+
+    if (consume_while(is_any_of(" \t\n")).is_empty()) {
+        m_offset = rule_start->offset;
+        return nullptr;
+    }
+
+    auto variable_name = consume_while(is_word_character);
+    Optional<size_t> in_start_position;
+    if (variable_name.is_empty()) {
+        variable_name = "it";
+    } else {
+        consume_while(is_whitespace);
+        auto in_error_start = push_start();
+        in_start_position = in_error_start->offset;
+        if (!expect("in")) {
+            auto syntax_error = create<AST::SyntaxError>("Expected 'in' after a variable name in a 'for' loop");
+            return create<AST::ForLoop>(move(variable_name), move(syntax_error), nullptr); // ForLoop Var Iterated Block
+        }
+    }
+
+    consume_while(is_whitespace);
+    RefPtr<AST::Node> iterated_expression;
+    {
+        auto iter_error_start = push_start();
+        iterated_expression = parse_expression();
+        if (!iterated_expression) {
+            auto syntax_error = create<AST::SyntaxError>("Expected an expression in 'for' loop");
+            return create<AST::ForLoop>(move(variable_name), move(syntax_error), nullptr, move(in_start_position)); // ForLoop Var Iterated Block
+        }
+    }
+
+    consume_while(is_any_of(" \t\n"));
+    {
+        auto obrace_error_start = push_start();
+        if (!expect('{')) {
+            auto syntax_error = create<AST::SyntaxError>("Expected an open brace '{' to start a 'for' loop body");
+            return create<AST::ForLoop>(move(variable_name), move(iterated_expression), move(syntax_error), move(in_start_position)); // ForLoop Var Iterated Block
+        }
+    }
+
+    auto body = parse_toplevel();
+
+    {
+        auto cbrace_error_start = push_start();
+        if (!expect('}')) {
+            auto error_start = push_start();
+            RefPtr<AST::SyntaxError> syntax_error = create<AST::SyntaxError>("Expected a close brace '}' to end a 'for' loop body");
+            if (body)
+                body->set_is_syntax_error(*syntax_error);
+            else
+                body = syntax_error;
+        }
+    }
+
+    return create<AST::ForLoop>(move(variable_name), move(iterated_expression), move(body), move(in_start_position)); // ForLoop Var Iterated Block
+}
+
 RefPtr<AST::Node> Parser::parse_redirection()
 {
     auto rule_start = push_start();
diff --git a/Shell/Parser.h b/Shell/Parser.h
index 681d0d29df..1e56bb68a8 100644
--- a/Shell/Parser.h
+++ b/Shell/Parser.h
@@ -45,9 +45,13 @@ public:
 private:
     RefPtr<AST::Node> parse_toplevel();
     RefPtr<AST::Node> parse_sequence();
+    RefPtr<AST::Node> parse_and_logical_sequence();
+    RefPtr<AST::Node> parse_or_logical_sequence();
     RefPtr<AST::Node> parse_variable_decls();
     RefPtr<AST::Node> parse_pipe_sequence();
     RefPtr<AST::Node> parse_command();
+    RefPtr<AST::Node> parse_control_structure();
+    RefPtr<AST::Node> parse_for_loop();
     RefPtr<AST::Node> parse_redirection();
     RefPtr<AST::Node> parse_list_expression();
     RefPtr<AST::Node> parse_expression();
@@ -100,12 +104,17 @@ private:
 constexpr auto the_grammar = R"(
 toplevel :: sequence?
 
-sequence :: variable_decls? pipe_sequence terminator sequence
-          | variable_decls? pipe_sequence '&'
-          | variable_decls? pipe_sequence '&' '&' sequence
-          | variable_decls? pipe_sequence '|' '|' sequence
-          | variable_decls? pipe_sequence
-          | variable_decls? terminator pipe_sequence
+sequence :: variable_decls? or_logical_sequence terminator sequence
+          | variable_decls? or_logical_sequence '&' sequence
+          | variable_decls? control_structure terminator sequence
+          | variable_decls? or_logical_sequence
+          | variable_decls? terminator sequence
+
+or_logical_sequence :: and_logical_sequence '|' '|' and_logical_sequence
+                     | and_logical_sequence
+
+and_logical_sequence :: pipe_sequence '&' '&' and_logical_sequence
+                      | pipe_sequence
 
 terminator :: ';'
             | '\n'
@@ -116,6 +125,8 @@ variable_decls :: identifier '=' expression (' '+ variable_decls)? ' '*
 pipe_sequence :: command '|' pipe_sequence
                | command
 
+control_structure :: 'for' ws+ (identifier ' '+ 'in' ws*)? expression ws+ '{' toplevel '}'
+
 command :: redirection command
          | list_expression command?
 
diff --git a/Shell/Shell.cpp b/Shell/Shell.cpp
index a7cfbcaaae..08b3493acc 100644
--- a/Shell/Shell.cpp
+++ b/Shell/Shell.cpp
@@ -319,10 +319,21 @@ String Shell::resolve_path(String path) const
     return Core::File::real_path_for(path);
 }
 
+Shell::LocalFrame* Shell::find_frame_containing_local_variable(const String& name)
+{
+    for (auto& frame : m_local_frames) {
+        if (frame.local_variables.contains(name))
+            return &frame;
+    }
+    return nullptr;
+}
+
 RefPtr<AST::Value> Shell::lookup_local_variable(const String& name)
 {
-    auto value = m_local_variables.get(name).value_or(nullptr);
-    return value;
+    if (auto* frame = find_frame_containing_local_variable(name))
+        return frame->local_variables.get(name).value();
+
+    return nullptr;
 }
 
 String Shell::local_variable_or(const String& name, const String& replacement)
@@ -338,12 +349,36 @@ String Shell::local_variable_or(const String& name, const String& replacement)
 
 void Shell::set_local_variable(const String& name, RefPtr<AST::Value> value)
 {
-    m_local_variables.set(name, move(value));
+    if (auto* frame = find_frame_containing_local_variable(name))
+        frame->local_variables.set(name, move(value));
+    else
+        m_local_frames.last().local_variables.set(name, move(value));
 }
 
 void Shell::unset_local_variable(const String& name)
 {
-    m_local_variables.remove(name);
+    if (auto* frame = find_frame_containing_local_variable(name))
+        frame->local_variables.remove(name);
+}
+
+Shell::Frame Shell::push_frame()
+{
+    m_local_frames.empend();
+    return { m_local_frames, m_local_frames.last() };
+}
+
+void Shell::pop_frame()
+{
+    ASSERT(m_local_frames.size() > 1);
+    m_local_frames.take_last();
+}
+
+Shell::Frame::~Frame()
+{
+    if (!should_destroy_frame)
+        return;
+    ASSERT(&frames.last() == &frame);
+    frames.take_last();
 }
 
 String Shell::resolve_alias(const String& name) const
@@ -879,9 +914,11 @@ Vector<Line::CompletionSuggestion> Shell::complete_variable(const String& name,
     editor->suggest(offset);
 
     // Look at local variables.
-    for (auto& variable : m_local_variables) {
-        if (variable.key.starts_with(pattern))
-            suggestions.append(variable.key);
+    for (auto& frame : m_local_frames) {
+        for (auto& variable : frame.local_variables) {
+            if (variable.key.starts_with(pattern) && !suggestions.contains_slow(variable.key))
+                suggestions.append(variable.key);
+        }
     }
 
     // Look at the environment.
@@ -1015,6 +1052,8 @@ Shell::Shell()
     tcsetpgrp(0, getpgrp());
     m_pid = getpid();
 
+    push_frame().leak_frame();
+
     int rc = gethostname(hostname, Shell::HostNameSize);
     if (rc < 0)
         perror("gethostname");
diff --git a/Shell/Shell.h b/Shell/Shell.h
index 177a22eab2..6031c080d0 100644
--- a/Shell/Shell.h
+++ b/Shell/Shell.h
@@ -93,6 +93,29 @@ public:
     void set_local_variable(const String&, RefPtr<AST::Value>);
     void unset_local_variable(const String&);
 
+    struct LocalFrame {
+        HashMap<String, RefPtr<AST::Value>> local_variables;
+    };
+
+    struct Frame {
+        Frame(Vector<LocalFrame>& frames, const LocalFrame& frame)
+            : frames(frames)
+            , frame(frame)
+        {
+        }
+        ~Frame();
+
+        void leak_frame() { should_destroy_frame = false; }
+
+    private:
+        Vector<LocalFrame>& frames;
+        const LocalFrame& frame;
+        bool should_destroy_frame { true };
+    };
+
+    [[nodiscard]] Frame push_frame();
+    void pop_frame();
+
     static String escape_token(const String& token);
     static String unescape_token(const String& token);
 
@@ -166,6 +189,7 @@ private:
     void cache_path();
     void stop_all_jobs();
     const Job* m_current_job { nullptr };
+    LocalFrame* find_frame_containing_local_variable(const String& name);
 
     virtual void custom_event(Core::CustomEvent&) override;
 
@@ -188,7 +212,8 @@ private:
     bool m_should_ignore_jobs_on_next_exit { false };
     pid_t m_pid { 0 };
 
-    HashMap<String, RefPtr<AST::Value>> m_local_variables;
+    Vector<LocalFrame> m_local_frames;
+
     HashMap<String, String> m_aliases;
 };