Shell: Make the parser read consecutive sequences without recursing

This fixes (the easy) part of #4976.

6 files changed, 120 insertions, 88 deletions

diff --git a/Userland/Shell/AST.cpp b/Userland/Shell/AST.cpp
index 93dc4fee8e..3bb9acf09a 100644
--- a/Userland/Shell/AST.cpp
+++ b/Userland/Shell/AST.cpp
@@ -2302,32 +2302,37 @@ ReadWriteRedirection::~ReadWriteRedirection()
 void Sequence::dump(int level) const
 {
     Node::dump(level);
-    m_left->dump(level + 1);
-    m_right->dump(level + 1);
+    for (auto& entry : m_entries)
+        entry.dump(level + 1);
 }
 
 RefPtr<Value> Sequence::run(RefPtr<Shell> shell)
 {
-    auto left = m_left->to_lazy_evaluated_commands(shell);
-    // This could happen if a comment is next to a command.
-    if (left.size() == 1) {
-        auto& command = left.first();
-        if (command.argv.is_empty() && command.redirections.is_empty() && command.next_chain.is_empty())
-            return m_right->run(shell);
-    }
+    Vector<Command> all_commands;
+    Command* last_command_in_sequence = nullptr;
+    for (auto& entry : m_entries) {
+        if (!last_command_in_sequence) {
+            auto commands = entry.to_lazy_evaluated_commands(shell);
+            all_commands.append(move(commands));
+            last_command_in_sequence = &all_commands.last();
+            continue;
+        }
 
-    if (left.last().should_wait)
-        left.last().next_chain.append(NodeWithAction { *m_right, NodeWithAction::Sequence });
-    else
-        left.append(m_right->to_lazy_evaluated_commands(shell));
+        if (last_command_in_sequence->should_wait) {
+            last_command_in_sequence->next_chain.append(NodeWithAction { entry, NodeWithAction::Sequence });
+        } else {
+            all_commands.append(entry.to_lazy_evaluated_commands(shell));
+            last_command_in_sequence = &all_commands.last();
+        }
+    }
 
-    return create<CommandSequenceValue>(move(left));
+    return create<CommandSequenceValue>(move(all_commands));
 }
 
 void Sequence::highlight_in_editor(Line::Editor& editor, Shell& shell, HighlightMetadata metadata)
 {
-    m_left->highlight_in_editor(editor, shell, metadata);
-    m_right->highlight_in_editor(editor, shell, metadata);
+    for (auto& entry : m_entries)
+        entry.highlight_in_editor(editor, shell, metadata);
 }
 
 HitTestResult Sequence::hit_test_position(size_t offset)
@@ -2335,29 +2340,29 @@ HitTestResult Sequence::hit_test_position(size_t offset)
     if (!position().contains(offset))
         return {};
 
-    auto result = m_left->hit_test_position(offset);
-    if (result.matching_node) {
-        if (!result.closest_command_node)
-            result.closest_command_node = m_right;
-        return result;
+    for (auto& entry : m_entries) {
+        auto result = entry.hit_test_position(offset);
+        if (result.matching_node) {
+            if (!result.closest_command_node)
+                result.closest_command_node = entry;
+            return result;
+        }
     }
 
-    result = m_right->hit_test_position(offset);
-    if (!result.closest_command_node)
-        result.closest_command_node = m_right;
-    return result;
+    return {};
 }
 
-Sequence::Sequence(Position position, NonnullRefPtr<Node> left, NonnullRefPtr<Node> right, Position separator_position)
+Sequence::Sequence(Position position, NonnullRefPtrVector<Node> entries, Vector<Position> separator_positions)
     : Node(move(position))
-    , m_left(move(left))
-    , m_right(move(right))
-    , m_separator_position(separator_position)
+    , m_entries(move(entries))
+    , m_separator_positions(separator_positions)
 {
-    if (m_left->is_syntax_error())
-        set_is_syntax_error(m_left->syntax_error_node());
-    else if (m_right->is_syntax_error())
-        set_is_syntax_error(m_right->syntax_error_node());
+    for (auto& entry : m_entries) {
+        if (entry.is_syntax_error()) {
+            set_is_syntax_error(entry.syntax_error_node());
+            break;
+        }
+    }
 }
 
 Sequence::~Sequence()
diff --git a/Userland/Shell/AST.h b/Userland/Shell/AST.h
index 6d74f0f512..5d34c49173 100644
--- a/Userland/Shell/AST.h
+++ b/Userland/Shell/AST.h
@@ -1139,14 +1139,13 @@ private:
 
 class Sequence final : public Node {
 public:
-    Sequence(Position, NonnullRefPtr<Node>, NonnullRefPtr<Node>, Position separator_position);
+    Sequence(Position, NonnullRefPtrVector<Node>, Vector<Position> separator_positions);
     virtual ~Sequence();
     virtual void visit(NodeVisitor& visitor) override { visitor.visit(this); }
 
-    const NonnullRefPtr<Node>& left() const { return m_left; }
-    const NonnullRefPtr<Node>& right() const { return m_right; }
+    const NonnullRefPtrVector<Node>& entries() const { return m_entries; }
 
-    const Position& separator_position() const { return m_separator_position; }
+    const Vector<Position>& separator_positions() const { return m_separator_positions; }
 
 private:
     NODE(Sequence);
@@ -1157,9 +1156,8 @@ private:
     virtual bool is_list() const override { return true; }
     virtual bool should_override_execution_in_current_process() const override { return true; }
 
-    NonnullRefPtr<Node> m_left;
-    NonnullRefPtr<Node> m_right;
-    Position m_separator_position;
+    NonnullRefPtrVector<Node> m_entries;
+    Vector<Position> m_separator_positions;
 };
 
 class Subshell final : public Node {
diff --git a/Userland/Shell/Formatter.cpp b/Userland/Shell/Formatter.cpp
index ee5a3ad28e..27a0dc08b1 100644
--- a/Userland/Shell/Formatter.cpp
+++ b/Userland/Shell/Formatter.cpp
@@ -631,10 +631,17 @@ void Formatter::visit(const AST::Sequence* node)
     test_and_update_output_cursor(node);
 
     TemporaryChange<const AST::Node*> parent { m_parent_node, node };
-    node->left()->visit(*this);
-    insert_separator();
 
-    node->right()->visit(*this);
+    bool first = true;
+    for (auto& entry : node->entries()) {
+        if (first)
+            first = false;
+        else
+            insert_separator();
+
+        entry.visit(*this);
+    }
+
     visited(node);
 }
 
diff --git a/Userland/Shell/NodeVisitor.cpp b/Userland/Shell/NodeVisitor.cpp
index 44ce39a4c4..b4edd8426b 100644
--- a/Userland/Shell/NodeVisitor.cpp
+++ b/Userland/Shell/NodeVisitor.cpp
@@ -186,8 +186,8 @@ void NodeVisitor::visit(const AST::ReadWriteRedirection* node)
 
 void NodeVisitor::visit(const AST::Sequence* node)
 {
-    node->left()->visit(*this);
-    node->right()->visit(*this);
+    for (auto& entry : node->entries())
+        entry.visit(*this);
 }
 
 void NodeVisitor::visit(const AST::Subshell* node)
diff --git a/Userland/Shell/Parser.cpp b/Userland/Shell/Parser.cpp
index f5b6f7a5e7..d705a9a27a 100644
--- a/Userland/Shell/Parser.cpp
+++ b/Userland/Shell/Parser.cpp
@@ -111,6 +111,11 @@ NonnullRefPtr<A> Parser::create(Args... args)
     return make<ScopedOffset>(m_rule_start_offsets, m_rule_start_lines, m_offset, m_line.line_number, m_line.line_column);
 }
 
+Parser::Offset Parser::current_position()
+{
+    return Offset { m_offset, { m_line.line_number, m_line.line_column } };
+}
+
 static constexpr bool is_whitespace(char c)
 {
     return c == ' ' || c == '\t';
@@ -180,58 +185,70 @@ RefPtr<AST::Node> Parser::parse_toplevel()
 {
     auto rule_start = push_start();
 
-    if (auto sequence = parse_sequence())
-        return create<AST::Execute>(sequence.release_nonnull());
+    SequenceParseResult result;
+    NonnullRefPtrVector<AST::Node> sequence;
+    Vector<AST::Position> positions;
+    do {
+        result = parse_sequence();
+        if (result.entries.is_empty())
+            break;
 
-    return nullptr;
+        sequence.append(move(result.entries));
+        positions.append(move(result.separator_positions));
+    } while (result.decision == ShouldReadMoreSequences::Yes);
+
+    if (sequence.is_empty())
+        return nullptr;
+
+    return create<AST::Execute>(
+        create<AST::Sequence>(move(sequence), move(positions)));
 }
 
-RefPtr<AST::Node> Parser::parse_sequence()
+Parser::SequenceParseResult Parser::parse_sequence()
 {
     consume_while(is_any_of(" \t\n;")); // ignore whitespaces or terminators without effect.
 
+    NonnullRefPtrVector<AST::Node> left;
+
     auto rule_start = push_start();
-    auto var_decls = parse_variable_decls();
+    {
+        auto var_decls = parse_variable_decls();
+        if (var_decls)
+            left.append(var_decls.release_nonnull());
+    }
 
     auto pos_before_seps = save_offset();
 
     switch (peek()) {
     case '}':
-        return var_decls;
+        return { move(left), {}, ShouldReadMoreSequences::No };
     case ';':
     case '\n': {
-        if (!var_decls)
+        if (left.is_empty())
             break;
 
         consume_while(is_any_of("\n;"));
-
         auto pos_after_seps = save_offset();
+        AST::Position separator_position { pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_after_seps.line };
 
-        auto rest = parse_sequence();
-        if (rest)
-            return create<AST::Sequence>(
-                var_decls.release_nonnull(),
-                rest.release_nonnull(),
-                AST::Position { pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_after_seps.line });
-        return var_decls;
+        return { move(left), { move(separator_position) }, ShouldReadMoreSequences::Yes };
     }
     default:
         break;
     }
 
-    auto first = parse_function_decl();
+    auto first_entry = parse_function_decl();
 
-    if (!first)
-        first = parse_or_logical_sequence();
+    Vector<AST::Position> separator_positions;
 
-    if (!first)
-        return var_decls;
+    if (!first_entry)
+        first_entry = parse_or_logical_sequence();
 
-    if (var_decls)
-        first = create<AST::Sequence>(
-            var_decls.release_nonnull(),
-            first.release_nonnull(),
-            AST::Position { pos_before_seps.offset, pos_before_seps.offset, pos_before_seps.line, pos_before_seps.line });
+    if (!first_entry)
+        return { move(left), {}, ShouldReadMoreSequences::No };
+
+    left.append(first_entry.release_nonnull());
+    separator_positions.empend(pos_before_seps.offset, pos_before_seps.offset, pos_before_seps.line, pos_before_seps.line);
 
     consume_while(is_whitespace);
 
@@ -241,29 +258,19 @@ RefPtr<AST::Node> Parser::parse_sequence()
     case '\n': {
         consume_while(is_any_of("\n;"));
         auto pos_after_seps = save_offset();
-
-        if (auto expr = parse_sequence()) {
-            return create<AST::Sequence>(
-                first.release_nonnull(),
-                expr.release_nonnull(),
-                AST::Position { pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_after_seps.line }); // Sequence
-        }
-        return first;
+        separator_positions.empend(pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_after_seps.line);
+        return { move(left), move(separator_positions), ShouldReadMoreSequences::Yes };
     }
     case '&': {
         consume();
         auto pos_after_seps = save_offset();
-        auto bg = create<AST::Background>(first.release_nonnull()); // Execute Background
-        if (auto rest = parse_sequence())
-            return create<AST::Sequence>(
-                move(bg),
-                rest.release_nonnull(),
-                AST::Position { pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_before_seps.line }); // Sequence Background Sequence
-
-        return bg;
+        auto bg = create<AST::Background>(left.take_last()); // Execute Background
+        left.append(move(bg));
+        separator_positions.empend(pos_before_seps.offset, pos_after_seps.offset, pos_before_seps.line, pos_after_seps.line);
+        return { move(left), move(separator_positions), ShouldReadMoreSequences::Yes };
     }
     default:
-        return first;
+        return { move(left), move(separator_positions), ShouldReadMoreSequences::No };
     }
 }
 
diff --git a/Userland/Shell/Parser.h b/Userland/Shell/Parser.h
index aa2a3b9e53..a3f09b944e 100644
--- a/Userland/Shell/Parser.h
+++ b/Userland/Shell/Parser.h
@@ -55,9 +55,19 @@ public:
     SavedOffset save_offset() const;
 
 private:
+    enum class ShouldReadMoreSequences {
+        Yes,
+        No,
+    };
+    struct SequenceParseResult {
+        NonnullRefPtrVector<AST::Node> entries;
+        Vector<AST::Position, 1> separator_positions;
+        ShouldReadMoreSequences decision;
+    };
+
     constexpr static size_t max_allowed_nested_rule_depth = 2048;
     RefPtr<AST::Node> parse_toplevel();
-    RefPtr<AST::Node> parse_sequence();
+    SequenceParseResult parse_sequence();
     RefPtr<AST::Node> parse_function_decl();
     RefPtr<AST::Node> parse_and_logical_sequence();
     RefPtr<AST::Node> parse_or_logical_sequence();
@@ -108,6 +118,10 @@ private:
 
     StringView consume_while(Function<bool(char)>);
 
+    struct Offset {
+        size_t offset;
+        AST::Position::Line line;
+    };
     struct ScopedOffset {
         ScopedOffset(Vector<size_t>& offsets, Vector<AST::Position::Line>& lines, size_t offset, size_t lineno, size_t linecol)
             : offsets(offsets)
@@ -136,6 +150,7 @@ private:
     void restore_to(const ScopedOffset& offset) { restore_to(offset.offset, offset.line); }
 
     OwnPtr<ScopedOffset> push_start();
+    Offset current_position();
 
     StringView m_input;
     size_t m_offset { 0 };