LibCpp: Parse templatized types

We can now parse things like Vector<int>

4 files changed, 153 insertions, 38 deletions

diff --git a/Userland/Libraries/LibCpp/AST.cpp b/Userland/Libraries/LibCpp/AST.cpp
index f44499be1a..7b93ba692d 100644
--- a/Userland/Libraries/LibCpp/AST.cpp
+++ b/Userland/Libraries/LibCpp/AST.cpp
@@ -54,7 +54,7 @@ void FunctionDeclaration::dump(size_t indent) const
 
     String qualifiers_string;
     if (!m_qualifiers.is_empty()) {
-        print_indent(indent+1);
+        print_indent(indent + 1);
         outln("[{}]", String::join(" ", m_qualifiers));
     }
 
@@ -259,7 +259,7 @@ void StringLiteral::dump(size_t indent) const
 void ReturnStatement::dump(size_t indent) const
 {
     ASTNode::dump(indent);
-    if(m_value)
+    if (m_value)
         m_value->dump(indent + 1);
 }
 
@@ -442,4 +442,24 @@ void NullPointerLiteral::dump(size_t indent) const
     ASTNode::dump(indent);
 }
 
+void TemplatizedType::dump(size_t indent) const
+{
+    ASTNode::dump(indent);
+
+    String qualifiers_string;
+    if (!m_qualifiers.is_empty())
+        qualifiers_string = String::formatted("[{}] ", String::join(" ", m_qualifiers));
+
+    print_indent(indent + 1);
+    outln("{}{}", qualifiers_string, m_name);
+
+    print_indent(indent + 1);
+    outln("<");
+    for (auto& arg : m_template_arguments) {
+        arg.dump(indent + 1);
+    }
+    print_indent(indent + 1);
+    outln(">");
+}
+
 }
diff --git a/Userland/Libraries/LibCpp/AST.h b/Userland/Libraries/LibCpp/AST.h
index f1fea9d47e..487c2c094a 100644
--- a/Userland/Libraries/LibCpp/AST.h
+++ b/Userland/Libraries/LibCpp/AST.h
@@ -215,10 +215,10 @@ public:
     const StringView& name() const { return m_name; }
     virtual void dump(size_t indent) const override;
     virtual bool is_type() const override { return true; }
+    virtual bool is_templatized() const { return false; }
 
-    Type(ASTNode* parent, Optional<Position> start, Optional<Position> end, const String& filename, StringView name)
+    Type(ASTNode* parent, Optional<Position> start, Optional<Position> end, const String& filename)
         : ASTNode(parent, start, end, filename)
-        , m_name(name)
     {
     }
 
@@ -226,6 +226,21 @@ public:
     Vector<StringView> m_qualifiers;
 };
 
+class TemplatizedType : public Type {
+public:
+    virtual ~TemplatizedType() override = default;
+    virtual const char* class_name() const override { return "TemplatizedType"; }
+    virtual void dump(size_t indent) const override;
+    virtual bool is_templatized() const override { return true; }
+
+    TemplatizedType(ASTNode* parent, Optional<Position> start, Optional<Position> end, const String& filename)
+        : Type(parent, start, end, filename)
+    {
+    }
+
+    NonnullRefPtrVector<Type> m_template_arguments;
+};
+
 class Pointer : public Type {
 public:
     virtual ~Pointer() override = default;
@@ -233,7 +248,7 @@ public:
     virtual void dump(size_t indent) const override;
 
     Pointer(ASTNode* parent, Optional<Position> start, Optional<Position> end, const String& filename)
-        : Type(parent, start, end, filename, {})
+        : Type(parent, start, end, filename)
     {
     }
 
diff --git a/Userland/Libraries/LibCpp/Parser.cpp b/Userland/Libraries/LibCpp/Parser.cpp
index 14db37a755..e2a7f86099 100644
--- a/Userland/Libraries/LibCpp/Parser.cpp
+++ b/Userland/Libraries/LibCpp/Parser.cpp
@@ -189,16 +189,16 @@ NonnullRefPtr<FunctionDefinition> Parser::parse_function_definition(ASTNode& par
 NonnullRefPtr<Statement> Parser::parse_statement(ASTNode& parent)
 {
     SCOPE_LOGGER();
-    ArmedScopeGuard consume_semicolumn([this]() {
+    ArmedScopeGuard consume_semicolon([this]() {
         consume(Token::Type::Semicolon);
     });
 
     if (match_block_statement()) {
-        consume_semicolumn.disarm();
+        consume_semicolon.disarm();
         return parse_block_statement(parent);
     }
     if (match_comment()) {
-        consume_semicolumn.disarm();
+        consume_semicolon.disarm();
         return parse_comment(parent);
     }
     if (match_variable_declaration()) {
@@ -211,15 +211,15 @@ NonnullRefPtr<Statement> Parser::parse_statement(ASTNode& parent)
         return parse_return_statement(parent);
     }
     if (match_keyword("for")) {
-        consume_semicolumn.disarm();
+        consume_semicolon.disarm();
         return parse_for_statement(parent);
     }
     if (match_keyword("if")) {
-        consume_semicolumn.disarm();
+        consume_semicolon.disarm();
         return parse_if_statement(parent);
     } else {
         error("unexpected statement type");
-        consume_semicolumn.disarm();
+        consume_semicolon.disarm();
         consume();
         return create_ast_node<InvalidStatement>(parent, position(), position());
     }
@@ -251,16 +251,60 @@ NonnullRefPtr<BlockStatement> Parser::parse_block_statement(ASTNode& parent)
     return block_statement;
 }
 
-bool Parser::match_type()
+Parser::MatchTypeResult Parser::match_type()
 {
     save_state();
     ScopeGuard state_guard = [this] { load_state(); };
 
     parse_type_qualifiers();
-    // Type
+
     if (!peek(Token::Type::KnownType).has_value() && !peek(Token::Type::Identifier).has_value())
+        return MatchTypeResult::NoMatch;
+
+    consume();
+
+    if (peek(Token::Type::Less).has_value()) {
+        if (match_template_arguments()) {
+            return MatchTypeResult::Templatized;
+        }
+        return MatchTypeResult::NoMatch;
+    }
+
+    return MatchTypeResult::Regular;
+}
+
+bool Parser::match_template_arguments()
+{
+    save_state();
+    ScopeGuard state_guard = [this] { load_state(); };
+
+    if (!peek(Token::Type::Less).has_value())
         return false;
-    return true;
+    consume();
+
+    while (!eof() && peek().type() != Token::Type::Greater) {
+        if (match_type() == MatchTypeResult::NoMatch)
+            return false;
+        parse_type(*m_root_node);
+    }
+
+    return peek().type() == Token::Type::Greater;
+}
+
+NonnullRefPtrVector<Type> Parser::parse_template_arguments(ASTNode& parent)
+{
+    SCOPE_LOGGER();
+
+    consume(Token::Type::Less);
+
+    NonnullRefPtrVector<Type> template_arguments;
+    while (!eof() && peek().type() != Token::Type::Greater) {
+        template_arguments.append(parse_type(parent));
+    }
+
+    consume(Token::Type::Greater);
+
+    return template_arguments;
 }
 
 bool Parser::match_variable_declaration()
@@ -269,14 +313,17 @@ bool Parser::match_variable_declaration()
     save_state();
     ScopeGuard state_guard = [this] { load_state(); };
 
-    if (!match_type())
+    if (match_type() == MatchTypeResult::NoMatch) {
         return false;
+    }
+
     VERIFY(m_root_node);
     parse_type(*m_root_node);
 
     // Identifier
-    if (!peek(Token::Type::Identifier).has_value())
+    if (!peek(Token::Type::Identifier).has_value()) {
         return false;
+    }
     consume();
 
     if (match(Token::Type::Equals)) {
@@ -586,7 +633,7 @@ bool Parser::match_function_declaration()
 
     parse_function_qualifiers();
 
-    if (!match_type())
+    if (match_type() == MatchTypeResult::NoMatch)
         return false;
     VERIFY(m_root_node);
     parse_type(*m_root_node);
@@ -770,8 +817,8 @@ void Parser::error(StringView message)
             m_tokens[m_state.token_index].start().line,
             m_tokens[m_state.token_index].start().column);
     }
-    m_errors.append(formatted_message);
-    dbgln_if(CPP_DEBUG, "{}", formatted_message);
+
+    m_state.errors.append(formatted_message);
 }
 
 bool Parser::match_expression()
@@ -925,7 +972,7 @@ NonnullRefPtr<ReturnStatement> Parser::parse_return_statement(ASTNode& parent)
     SCOPE_LOGGER();
     auto return_statement = create_ast_node<ReturnStatement>(parent, position(), {});
     consume(Token::Type::Keyword);
-    if(!peek(Token::Type::Semicolon).has_value()) {
+    if (!peek(Token::Type::Semicolon).has_value()) {
         auto expression = parse_expression(*return_statement);
         return_statement->m_value = expression;
     }
@@ -1011,19 +1058,19 @@ NonnullRefPtr<MemberDeclaration> Parser::parse_member_declaration(ASTNode& paren
 {
     SCOPE_LOGGER();
     auto member_decl = create_ast_node<MemberDeclaration>(parent, position(), {});
-    auto type_token = consume();
+    member_decl->m_type = parse_type(*member_decl);
+
     auto identifier_token = consume(Token::Type::Identifier);
-    RefPtr<Expression> initial_value;
+    member_decl->m_name = text_of_token(identifier_token);
 
+    RefPtr<Expression> initial_value;
     if (match(Token::Type::LeftCurly)) {
         consume(Token::Type::LeftCurly);
         initial_value = parse_expression(*member_decl);
         consume(Token::Type::RightCurly);
     }
-
-    member_decl->m_type = create_ast_node<Type>(*member_decl, type_token.start(), type_token.end(), text_of_token(type_token));
-    member_decl->m_name = text_of_token(identifier_token);
     member_decl->m_initial_value = move(initial_value);
+
     consume(Token::Type::Semicolon);
     member_decl->set_end(position());
 
@@ -1052,21 +1099,47 @@ bool Parser::match_boolean_literal()
 NonnullRefPtr<Type> Parser::parse_type(ASTNode& parent)
 {
     SCOPE_LOGGER();
+
+    auto match_result = match_type();
+    if (match_result == TemplatizedMatchResult::NoMatch) {
+        auto token = consume();
+        return create_ast_node<Type>(parent, token.start(), token.end());
+    }
+    bool is_templatized = match_result == TemplatizedMatchResult::Templatized;
+
+    RefPtr<Type> type;
+    if (is_templatized) {
+        type = create_ast_node<TemplatizedType>(parent, position(), {});
+    } else {
+        type = create_ast_node<Type>(parent, position(), {});
+    }
+
     auto qualifiers = parse_type_qualifiers();
-    auto token = consume();
-    auto type = create_ast_node<Type>(parent, token.start(), token.end(), text_of_token(token));
+    auto type_name_token = consume();
     type->m_qualifiers = move(qualifiers);
-    if (token.type() != Token::Type::KnownType && token.type() != Token::Type::Identifier) {
-        error(String::formatted("unexpected token for type: {}", token.to_string()));
-        return type;
+    type->m_name = text_of_token(type_name_token);
+
+    if (type_name_token.type() != Token::Type::KnownType && type_name_token.type() != Token::Type::Identifier) {
+        type->set_end(position());
+        error(String::formatted("unexpected type_name_token for type: {}", type_name_token.to_string()));
+        return type.release_nonnull();
+    }
+
+    if (is_templatized) {
+        static_cast<TemplatizedType&>(*type).m_template_arguments = parse_template_arguments(*type);
     }
-    while (peek().type() == Token::Type::Asterisk) {
+
+    while (!eof() && peek().type() == Token::Type::Asterisk) {
+        type->set_end(position());
         auto asterisk = consume();
-        auto ptr = create_ast_node<Pointer>(type, asterisk.start(), asterisk.end());
+        auto ptr = create_ast_node<Pointer>(parent, asterisk.start(), asterisk.end());
+        type->set_parent(*ptr);
         ptr->m_pointee = type;
         type = ptr;
     }
-    return type;
+
+    type->set_end(position());
+    return type.release_nonnull();
 }
 
 NonnullRefPtr<ForStatement> Parser::parse_for_statement(ASTNode& parent)
@@ -1142,7 +1215,6 @@ Vector<StringView> Parser::parse_function_qualifiers()
     return qualifiers;
 }
 
-
 bool Parser::match_attribute_specification()
 {
     return text_of_token(peek()) == "__attribute__";
diff --git a/Userland/Libraries/LibCpp/Parser.h b/Userland/Libraries/LibCpp/Parser.h
index 2fe0bacd43..d4a70be0db 100644
--- a/Userland/Libraries/LibCpp/Parser.h
+++ b/Userland/Libraries/LibCpp/Parser.h
@@ -53,7 +53,7 @@ public:
     String text_of_node(const ASTNode&) const;
     StringView text_of_token(const Cpp::Token& token) const;
     void print_tokens() const;
-    Vector<String> errors() const { return m_errors; }
+    const Vector<String>& errors() const { return m_state.errors; }
     const Preprocessor::Definitions& definitions() const { return m_definitions; }
 
     struct TokenAndPreprocessorDefinition {
@@ -88,7 +88,14 @@ private:
     bool match_keyword(const String&);
     bool match_block_statement();
     bool match_namespace_declaration();
-    bool match_type();
+    bool match_template_arguments();
+
+    enum class MatchTypeResult {
+        NoMatch,
+        Regular,
+        Templatized,
+    };
+    MatchTypeResult match_type();
 
     Optional<NonnullRefPtrVector<Parameter>> parse_parameter_list(ASTNode& parent);
     Optional<Token> consume_whitespace();
@@ -98,7 +105,7 @@ private:
     NonnullRefPtr<FunctionDeclaration> parse_function_declaration(ASTNode& parent);
     NonnullRefPtr<FunctionDefinition> parse_function_definition(ASTNode& parent);
     NonnullRefPtr<Statement> parse_statement(ASTNode& parent);
-    NonnullRefPtr<VariableDeclaration> parse_variable_declaration(ASTNode& parent, bool expect_semicolon=true);
+    NonnullRefPtr<VariableDeclaration> parse_variable_declaration(ASTNode& parent, bool expect_semicolon = true);
     NonnullRefPtr<Expression> parse_expression(ASTNode& parent);
     NonnullRefPtr<Expression> parse_primary_expression(ASTNode& parent);
     NonnullRefPtr<Expression> parse_secondary_expression(ASTNode& parent, NonnullRefPtr<Expression> lhs);
@@ -121,6 +128,7 @@ private:
     NonnullRefPtr<NamespaceDeclaration> parse_namespace_declaration(ASTNode& parent, bool is_nested_namespace = false);
     NonnullRefPtrVector<Declaration> parse_declarations_in_translation_unit(ASTNode& parent);
     RefPtr<Declaration> parse_single_declaration_in_translation_unit(ASTNode& parent);
+    NonnullRefPtrVector<Type> parse_template_arguments(ASTNode& parent);
 
     bool match(Token::Type);
     Token consume(Token::Type);
@@ -136,6 +144,7 @@ private:
 
     struct State {
         size_t token_index { 0 };
+        Vector<String> errors;
     };
 
     void error(StringView message = {});
@@ -173,7 +182,6 @@ private:
     Vector<State> m_saved_states;
     RefPtr<TranslationUnit> m_root_node;
     NonnullRefPtrVector<ASTNode> m_nodes;
-    Vector<String> m_errors;
 
     Vector<TokenAndPreprocessorDefinition> m_replaced_preprocessor_tokens;
 };