LibSQL: Create a very barebones SQL parser

This parser builds on the LibSQL lexer and currently only allows users
to parse 'CREATE TABLE' statements.

4 files changed, 418 insertions, 0 deletions

diff --git a/Userland/Libraries/LibSQL/AST.h b/Userland/Libraries/LibSQL/AST.h
new file mode 100644
index 0000000000..ca6553e4a6
--- /dev/null
+++ b/Userland/Libraries/LibSQL/AST.h
@@ -0,0 +1,128 @@
+/*
+ * Copyright (c) 2021, Tim Flynn <trflynn89@pm.me>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/NonnullRefPtr.h>
+#include <AK/NonnullRefPtrVector.h>
+#include <AK/RefCounted.h>
+#include <AK/String.h>
+
+namespace SQL {
+
+template<class T, class... Args>
+static inline NonnullRefPtr<T>
+create_ast_node(Args&&... args)
+{
+    return adopt(*new T(forward<Args>(args)...));
+}
+
+class ASTNode : public RefCounted<ASTNode> {
+public:
+    virtual ~ASTNode() { }
+
+protected:
+    ASTNode() = default;
+};
+
+class Statement : public ASTNode {
+};
+
+class ErrorStatement final : public Statement {
+};
+
+class SignedNumber final : public ASTNode {
+public:
+    explicit SignedNumber(double value)
+        : m_value(value)
+    {
+    }
+
+    double value() const { return m_value; }
+
+private:
+    double m_value;
+};
+
+class TypeName : public ASTNode {
+public:
+    TypeName(String name, NonnullRefPtrVector<SignedNumber> signed_numbers)
+        : m_name(move(name))
+        , m_signed_numbers(move(signed_numbers))
+    {
+        VERIFY(m_signed_numbers.size() <= 2);
+    }
+
+    const String& name() const { return m_name; }
+    const NonnullRefPtrVector<SignedNumber> signed_numbers() const { return m_signed_numbers; }
+
+private:
+    String m_name;
+    NonnullRefPtrVector<SignedNumber> m_signed_numbers;
+};
+
+class ColumnDefinition : public ASTNode {
+public:
+    ColumnDefinition(String name, NonnullRefPtr<TypeName> type_name)
+        : m_name(move(name))
+        , m_type_name(move(type_name))
+    {
+    }
+
+    const String& name() const { return m_name; }
+    const NonnullRefPtr<TypeName>& type_name() const { return m_type_name; }
+
+private:
+    String m_name;
+    NonnullRefPtr<TypeName> m_type_name;
+};
+
+class CreateTable : public Statement {
+public:
+    CreateTable(String schema_name, String table_name, NonnullRefPtrVector<ColumnDefinition> columns, bool is_temporary, bool is_error_if_table_exists)
+        : m_schema_name(move(schema_name))
+        , m_table_name(move(table_name))
+        , m_columns(move(columns))
+        , m_is_temporary(is_temporary)
+        , m_is_error_if_table_exists(is_error_if_table_exists)
+    {
+    }
+
+    const String& schema_name() const { return m_schema_name; }
+    const String& table_name() const { return m_table_name; }
+    const NonnullRefPtrVector<ColumnDefinition> columns() const { return m_columns; }
+    bool is_temporary() const { return m_is_temporary; }
+    bool is_error_if_table_exists() const { return m_is_error_if_table_exists; }
+
+private:
+    String m_schema_name;
+    String m_table_name;
+    NonnullRefPtrVector<ColumnDefinition> m_columns;
+    bool m_is_temporary;
+    bool m_is_error_if_table_exists;
+};
+
+}
diff --git a/Userland/Libraries/LibSQL/CMakeLists.txt b/Userland/Libraries/LibSQL/CMakeLists.txt
index 05631d71a2..c6b2ffb545 100644
--- a/Userland/Libraries/LibSQL/CMakeLists.txt
+++ b/Userland/Libraries/LibSQL/CMakeLists.txt
@@ -1,5 +1,6 @@
 set(SOURCES
     Lexer.cpp
+    Parser.cpp
     Token.cpp
 )
 
diff --git a/Userland/Libraries/LibSQL/Parser.cpp b/Userland/Libraries/LibSQL/Parser.cpp
new file mode 100644
index 0000000000..cc76b3d17a
--- /dev/null
+++ b/Userland/Libraries/LibSQL/Parser.cpp
@@ -0,0 +1,202 @@
+/*
+ * Copyright (c) 2021, Tim Flynn <trflynn89@pm.me>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "Parser.h"
+
+namespace SQL {
+
+Parser::Parser(Lexer lexer)
+    : m_parser_state(move(lexer))
+{
+}
+
+NonnullRefPtr<Statement> Parser::next_statement()
+{
+    switch (m_parser_state.m_token.type()) {
+    case TokenType::Create:
+        return parse_create_table_statement();
+    default:
+        expected("CREATE");
+        return create_ast_node<ErrorStatement>();
+    }
+}
+
+NonnullRefPtr<CreateTable> Parser::parse_create_table_statement()
+{
+    // https://sqlite.org/lang_createtable.html
+    consume(TokenType::Create);
+
+    bool is_temporary = false;
+    if (match(TokenType::Temp) || match(TokenType::Temporary)) {
+        consume();
+        is_temporary = true;
+    }
+
+    consume(TokenType::Table);
+
+    bool is_error_if_table_exists = true;
+    if (match(TokenType::If)) {
+        consume(TokenType::If);
+        consume(TokenType::Not);
+        consume(TokenType::Exists);
+        is_error_if_table_exists = false;
+    }
+
+    String schema_or_table_name = consume(TokenType::Identifier).value();
+    String schema_name;
+    String table_name;
+
+    if (match(TokenType::Period)) {
+        consume();
+        schema_name = move(schema_or_table_name);
+        table_name = consume(TokenType::Identifier).value();
+    } else {
+        table_name = move(schema_or_table_name);
+    }
+
+    // FIXME: Parse "AS select-stmt".
+
+    NonnullRefPtrVector<ColumnDefinition> column_definitions;
+    consume(TokenType::ParenOpen);
+    do {
+        column_definitions.append(parse_column_definition());
+
+        if (match(TokenType::ParenClose))
+            break;
+
+        consume(TokenType::Comma);
+    } while (!match(TokenType::Eof));
+
+    // FIXME: Parse "table-constraint".
+
+    consume(TokenType::ParenClose);
+    consume(TokenType::SemiColon);
+
+    return create_ast_node<CreateTable>(move(schema_name), move(table_name), move(column_definitions), is_temporary, is_error_if_table_exists);
+}
+
+NonnullRefPtr<ColumnDefinition> Parser::parse_column_definition()
+{
+    // https://sqlite.org/syntax/column-def.html
+    auto name = consume(TokenType::Identifier).value();
+
+    auto type_name = match(TokenType::Identifier)
+        ? parse_type_name()
+        // https://www.sqlite.org/datatype3.html: If no type is specified then the column has affinity BLOB.
+        : create_ast_node<TypeName>("BLOB", NonnullRefPtrVector<SignedNumber> {});
+
+    // FIXME: Parse "column-constraint".
+
+    return create_ast_node<ColumnDefinition>(move(name), move(type_name));
+}
+
+NonnullRefPtr<TypeName> Parser::parse_type_name()
+{
+    // https: //sqlite.org/syntax/type-name.html
+    auto name = consume(TokenType::Identifier).value();
+    NonnullRefPtrVector<SignedNumber> signed_numbers;
+
+    if (match(TokenType::ParenOpen)) {
+        consume();
+        signed_numbers.append(parse_signed_number());
+
+        if (match(TokenType::Comma)) {
+            consume();
+            signed_numbers.append(parse_signed_number());
+        }
+
+        consume(TokenType::ParenClose);
+    }
+
+    return create_ast_node<TypeName>(move(name), move(signed_numbers));
+}
+
+NonnullRefPtr<SignedNumber> Parser::parse_signed_number()
+{
+    // https://sqlite.org/syntax/signed-number.html
+    bool is_positive = true;
+
+    if (match(TokenType::Plus)) {
+        consume();
+    } else if (match(TokenType::Minus)) {
+        is_positive = false;
+        consume();
+    }
+
+    if (match(TokenType::NumericLiteral)) {
+        auto number = consume(TokenType::NumericLiteral).double_value();
+        return create_ast_node<SignedNumber>(is_positive ? number : (number * -1));
+    }
+
+    expected("NumericLiteral");
+    return create_ast_node<SignedNumber>(0);
+}
+
+Token Parser::consume()
+{
+    auto old_token = m_parser_state.m_token;
+    m_parser_state.m_token = m_parser_state.m_lexer.next();
+    return old_token;
+}
+
+Token Parser::consume(TokenType expected_type)
+{
+    if (!match(expected_type)) {
+        expected(Token::name(expected_type));
+    }
+    return consume();
+}
+
+bool Parser::match(TokenType type) const
+{
+    return m_parser_state.m_token.type() == type;
+}
+
+void Parser::expected(StringView what)
+{
+    syntax_error(String::formatted("Unexpected token {}, expected {}", m_parser_state.m_token.name(), what));
+}
+
+void Parser::syntax_error(String message)
+{
+    m_parser_state.m_errors.append({ move(message), position() });
+}
+
+Parser::Position Parser::position() const
+{
+    return {
+        m_parser_state.m_token.line_number(),
+        m_parser_state.m_token.line_column()
+    };
+}
+
+Parser::ParserState::ParserState(Lexer lexer)
+    : m_lexer(move(lexer))
+    , m_token(m_lexer.next())
+{
+}
+
+}
diff --git a/Userland/Libraries/LibSQL/Parser.h b/Userland/Libraries/LibSQL/Parser.h
new file mode 100644
index 0000000000..6efdd5bba7
--- /dev/null
+++ b/Userland/Libraries/LibSQL/Parser.h
@@ -0,0 +1,87 @@
+/*
+ * Copyright (c) 2021, Tim Flynn <trflynn89@pm.me>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/String.h>
+#include <AK/StringView.h>
+#include <LibSQL/AST.h>
+#include <LibSQL/Lexer.h>
+#include <LibSQL/Token.h>
+
+namespace SQL {
+
+class Parser {
+    struct Position {
+        size_t line { 0 };
+        size_t column { 0 };
+    };
+
+    struct Error {
+        String message;
+        Position position;
+
+        String to_string() const
+        {
+            return String::formatted("{} (line: {}, column: {})", message, position.line, position.column);
+        }
+    };
+
+public:
+    explicit Parser(Lexer lexer);
+
+    NonnullRefPtr<Statement> next_statement();
+
+    bool has_errors() const { return m_parser_state.m_errors.size(); }
+    const Vector<Error>& errors() const { return m_parser_state.m_errors; }
+
+private:
+    struct ParserState {
+        explicit ParserState(Lexer);
+
+        Lexer m_lexer;
+        Token m_token;
+        Vector<Error> m_errors;
+    };
+
+    NonnullRefPtr<ColumnDefinition> parse_column_definition();
+    NonnullRefPtr<CreateTable> parse_create_table_statement();
+    NonnullRefPtr<TypeName> parse_type_name();
+    NonnullRefPtr<SignedNumber> parse_signed_number();
+
+    Token consume();
+    Token consume(TokenType type);
+    bool match(TokenType type) const;
+
+    void expected(StringView what);
+    void syntax_error(String message);
+
+    Position position() const;
+
+    ParserState m_parser_state;
+};
+
+}