Import quark sources

Signed-off-by: Ian Moffett <ian@osmora.org>

11 files changed, 431 insertions, 0 deletions

diff --git a/include/debug.h b/include/debug.h
new file mode 100644
index 0000000..29434be
--- /dev/null
+++ b/include/debug.h
@@ -0,0 +1,18 @@
+/*
+ * Debugging utilities.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _DEBUG_H
+#define _DEBUG_H
+
+void __debug(const char *fmt, ...);
+
+#if defined(ENABLE_DEBUG)
+#define debug __debug
+#else
+#define debug(fmt, ...)
+#endif
+
+#endif /* !_DEBUG_H */
diff --git a/include/hash.h b/include/hash.h
new file mode 100644
index 0000000..f39c6da
--- /dev/null
+++ b/include/hash.h
@@ -0,0 +1,21 @@
+/*
+ * 32-bit FNV-1a hash function.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _HASH_H
+#define _HASH_H
+
+#include <stdint.h>
+#include <stdlib.h>
+
+#define FNV_PRIME        0x01000193
+#define FNV_OFFSET_BASIS 0x811c9dc5
+
+typedef uint32_t hash_t;
+
+hash_t hash_data(const void *data, size_t length);
+hash_t hash_string(const char *str);
+
+#endif /* !_HASH_H */
diff --git a/include/hashmap.h b/include/hashmap.h
new file mode 100644
index 0000000..26dfc61
--- /dev/null
+++ b/include/hashmap.h
@@ -0,0 +1,34 @@
+/*
+ * Tiny hashmap implementation.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _HASHMAP_H
+#define _HASHMAP_H
+
+#include <stddef.h>
+#include "list.h"
+#include "hash.h"
+
+struct hashmap_entry {
+    struct list_entry list_entry;
+    hash_t hash;
+};
+
+struct hashmap {
+    struct list *rows;
+    size_t n_rows;
+};
+
+static inline void
+hashmap_remove(struct hashmap_entry *entry)
+{
+    list_remove(&entry->list_entry);
+}
+
+void hashmap_add(struct hashmap *map, struct hashmap_entry *entry);
+struct hashmap_entry *hashmap_find(struct hashmap *map, hash_t hash);
+void hashmap_init(struct hashmap *map);
+
+#endif /* !_HASHMAP_H */
diff --git a/include/lexer.h b/include/lexer.h
new file mode 100644
index 0000000..99431ec
--- /dev/null
+++ b/include/lexer.h
@@ -0,0 +1,22 @@
+/*
+ * Quark lexer (lexical analyzer).
+ * Turns source code into tokens.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _LEXER_H
+#define _LEXER_H
+
+#include "lexer/token.h"
+
+struct lexer {
+    char *pos;
+    char *line_start;
+    int line;
+};
+
+void lexer_next(struct lexer *ctx, struct token *tok);
+void lexer_init(struct lexer *ctx, char *source);
+
+#endif /* !_LEXER_H */
diff --git a/include/lexer/char_info.h b/include/lexer/char_info.h
new file mode 100644
index 0000000..5987bbf
--- /dev/null
+++ b/include/lexer/char_info.h
@@ -0,0 +1,60 @@
+/*
+ * Character info table.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _LEXER_CHAR_INFO_H
+#define _LEXER_CHAR_INFO_H
+
+#include <stdint.h>
+#include "lexer/token.h"
+
+#define CHAR_HORZ_WS (1 << 0)
+#define CHAR_VERT_WS (1 << 1)
+#define CHAR_DIGIT   (1 << 2)
+#define CHAR_XDIGIT  (1 << 3)
+#define CHAR_UPPER   (1 << 4)
+#define CHAR_LOWER   (1 << 5)
+#define CHAR_OPER    (1 << 6)
+#define CHAR_SINGLE  (1 << 7)
+
+#define CHAR_HEX        (CHAR_DIGIT | CHAR_XDIGIT)
+#define CHAR_XUPPER     (CHAR_XDIGIT | CHAR_UPPER)
+#define CHAR_XLOWER     (CHAR_XDIGIT | CHAR_LOWER)
+#define CHAR_WHITESPACE (CHAR_HORZ_WS | CHAR_VERT_WS)
+#define CHAR_ALPHA      (CHAR_UPPER | CHAR_LOWER)
+#define CHAR_ALNUM      (CHAR_ALPHA | CHAR_DIGIT)
+
+#define CHAR_SINGLE_SHIFT 8
+#define MAKE_SINGLE(kind) ((kind << CHAR_SINGLE_SHIFT) | CHAR_SINGLE)
+#define CHAR_COMMA   MAKE_SINGLE(TK_COMMA)
+#define CHAR_DOT     MAKE_SINGLE(TK_DOT)
+#define CHAR_COLON   MAKE_SINGLE(TK_COLON)
+#define CHAR_SEMI    MAKE_SINGLE(TK_SEMICOLON)
+#define CHAR_LPAREN  MAKE_SINGLE(TK_LPAREN)
+#define CHAR_RPAREN  MAKE_SINGLE(TK_RPAREN)
+#define CHAR_LBRACE  MAKE_SINGLE(TK_LBRACE)
+#define CHAR_RBRACE  MAKE_SINGLE(TK_RBRACE)
+#define CHAR_LBRACK  MAKE_SINGLE(TK_LBRACK)
+#define CHAR_RBRACK  MAKE_SINGLE(TK_RBRACK)
+#define CHAR_TILDE   MAKE_SINGLE(TK_TILDE)
+#define CHAR_EQUALS  MAKE_SINGLE(TK_EQUALS)
+
+#define CHAR_OPER_SHIFT 8
+#define MAKE_OPER(kind) ((kind << CHAR_OPER_SHIFT) | CHAR_OPER)
+#define CHAR_PLUS    MAKE_OPER(TK_PLUS)
+#define CHAR_MINUS   MAKE_OPER(TK_MINUS)
+#define CHAR_STAR    MAKE_OPER(TK_STAR)
+#define CHAR_SLASH   MAKE_OPER(TK_SLASH)
+#define CHAR_PERCENT MAKE_OPER(TK_PERCENT)
+#define CHAR_EXCLAIM MAKE_OPER(TK_EXCLAMATION)
+#define CHAR_LESS    MAKE_OPER(TK_LESS_THAN)
+#define CHAR_GREATER MAKE_OPER(TK_GREATER_THAN)
+#define CHAR_CARET   MAKE_OPER(TK_CARET)
+#define CHAR_AMPER   MAKE_OPER(TK_AMPERSAND)
+#define CHAR_PIPE    MAKE_OPER(TK_PIPE)
+
+extern uint16_t char_info[256];
+
+#endif /* !_LEXER_CHAR_INFO_H */
diff --git a/include/lexer/keywords.h b/include/lexer/keywords.h
new file mode 100644
index 0000000..7da7dc1
--- /dev/null
+++ b/include/lexer/keywords.h
@@ -0,0 +1,15 @@
+/*
+ * Keyword hashmap.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _LEXER_KEYWORDS_H
+#define _LEXER_KEYWORDS_H
+
+#include "lexer/token.h"
+
+token_kind_t keywords_find(struct token *tok);
+void keywords_init(void);
+
+#endif /* !_LEXER_KEYWORDS_H */
diff --git a/include/lexer/token.h b/include/lexer/token.h
new file mode 100644
index 0000000..e0a9ea3
--- /dev/null
+++ b/include/lexer/token.h
@@ -0,0 +1,92 @@
+/*
+ * Token definitions.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _LEXER_TOKEN_H
+#define _LEXER_TOKEN_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include "hash.h"
+
+typedef enum {
+    TK_UNKNOWN,
+    TK_EOF,
+
+    TK_IDENTIFIER,
+    TK_NUMBER,
+    TK_STRING,
+    TK_CHARACTER,
+
+    /* Keywords */
+    TK_TYPE,
+    TK_ENUM,
+    TK_STRUCT,
+
+    /*
+     * Operators.
+     * NOTE: lex_oper() requires that TK_*_EQUALS
+     *       immediately follows TK_*.
+     */
+    TK_PLUS,
+    TK_PLUS_EQUALS,
+    TK_PLUS_PLUS,
+    TK_MINUS,
+    TK_MINUS_EQUALS,
+    TK_MINUS_MINUS,
+    TK_ARROW,
+    TK_STAR,
+    TK_STAR_EQUALS,
+    TK_SLASH,
+    TK_SLASH_EQUALS,
+    TK_PERCENT,
+    TK_PERCENT_EQUALS,
+    TK_EXCLAMATION,
+    TK_EXCLAMATION_EQUALS,
+    TK_LESS_THAN,
+    TK_LESS_THAN_EQUALS,
+    TK_SHIFT_LEFT,
+    TK_SHIFT_LEFT_EQUALS,
+    TK_GREATER_THAN,
+    TK_GREATER_THAN_EQUALS,
+    TK_SHIFT_RIGHT,
+    TK_SHIFT_RIGHT_EQUALS,
+    TK_CARET,
+    TK_CARET_EQUALS,
+    TK_AMPERSAND,
+    TK_AMPERSAND_EQUALS,
+    TK_PIPE,
+    TK_PIPE_EQUALS,
+    TK_TILDE,
+    TK_EQUALS,
+
+    /* Miscellaneous */
+    TK_COMMA,
+    TK_DOT,
+    TK_COLON,
+    TK_SEMICOLON,
+    TK_LPAREN,
+    TK_RPAREN,
+    TK_LBRACE,
+    TK_RBRACE,
+    TK_LBRACK,
+    TK_RBRACK
+} token_kind_t;
+
+struct token {
+    token_kind_t kind;
+
+    char *fname;
+    int line, col;
+    char *pos;
+    size_t len;
+
+    union {
+        hash_t hash;
+        uint64_t value;
+    };
+};
+
+#endif /* !_LEXER_TOKEN_H */
diff --git a/include/list.h b/include/list.h
new file mode 100644
index 0000000..0364f7c
--- /dev/null
+++ b/include/list.h
@@ -0,0 +1,58 @@
+/*
+ * Tiny doubly-linked list implementation.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _LIST_H
+#define _LIST_H
+
+#include <stddef.h>
+
+struct list_entry {
+    struct list_entry *prev;
+    struct list_entry *next;
+};
+
+struct list {
+    struct list_entry *tail;
+    struct list_entry *head;
+    size_t length;
+};
+
+static inline void
+list_remove(struct list_entry *entry)
+{
+    entry->prev->next = entry->next;
+    entry->next->prev = entry->prev;
+}
+
+static inline void
+list_append(struct list *list, struct list_entry *entry)
+{
+    entry->prev = list->tail;
+    entry->next = (struct list_entry*)list;
+    entry->prev->next = entry;
+    list->tail = entry;
+    list->length++;
+}
+
+static inline void
+list_prepend(struct list *list, struct list_entry *entry)
+{
+    entry->next = list->head;
+    entry->prev = (struct list_entry*)list;
+    entry->next->prev = entry;
+    list->head = entry;
+    list->length++;
+}
+
+static inline void
+list_init(struct list *list)
+{
+    list->tail = (struct list_entry*)list;
+    list->head = (struct list_entry*)list;
+    list->length = 0;
+}
+
+#endif /* !_LIST_H */
diff --git a/include/parser.h b/include/parser.h
new file mode 100644
index 0000000..d5e7acf
--- /dev/null
+++ b/include/parser.h
@@ -0,0 +1,34 @@
+/*
+ * Quark parser.
+ * Turns tokens into an AST (Abstract Syntax Tree).
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _PARSER_H
+#define _PARSER_H
+
+#include "lexer/token.h"
+#include "lexer.h"
+
+struct parser {
+    struct lexer lexer;
+    struct token tok;
+    struct hashmap *types;
+    struct hashmap *procs;
+};
+
+static inline struct token *
+next_token(struct parser *ctx)
+{
+    lexer_next(&ctx->lexer, &ctx->tok);
+    return &ctx->tok;
+}
+
+void tok_error(struct token *tok, const char *fmt, ...);
+void tok_warn(struct token *tok, const char *fmt, ...);
+
+void parser_parse(struct parser *ctx);
+void parser_init(struct parser *ctx, char *source);
+
+#endif /* !_PARSER_H */
diff --git a/include/parser/ast.h b/include/parser/ast.h
new file mode 100644
index 0000000..03be1bd
--- /dev/null
+++ b/include/parser/ast.h
@@ -0,0 +1,20 @@
+/*
+ * AST (Abstract Syntax Tree) definitions.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _PARSER_AST_H
+#define _PARSER_AST_H
+
+enum ast_node_kind {
+    NK_UNKNOWN,
+
+    NK_
+};
+
+struct ast_node {
+    enum ast_node_kind kind;
+};
+
+#endif /* !_PARSER_AST_H */
diff --git a/include/parser/type.h b/include/parser/type.h
new file mode 100644
index 0000000..6a939ab
--- /dev/null
+++ b/include/parser/type.h
@@ -0,0 +1,57 @@
+/*
+ * Type parser.
+ * Copyright (c) 2023-2024, Quinn Stephens and the OSMORA team.
+ * Provided under the BSD 3-Clause license.
+ */
+
+#ifndef _PARSER_TYPE_H
+#define _PARSER_TYPE_H
+
+#include <stddef.h>
+#include "hashmap.h"
+#include "parser.h"
+
+enum type_kind {
+    TYK_ALIAS,
+    TYK_ENUM,
+    TYK_STRUCT
+};
+
+struct enum_member {
+    struct hashmap_entry hashmap_entry;
+
+    char *name;
+    size_t name_len;
+
+    uint64_t value;
+};
+
+struct struct_member {
+    struct hashmap_entry hashmap_entry;
+
+    char *name;
+    size_t name_len;
+
+    size_t off, size;
+    struct type *typ;
+    int n_ptrs;
+};
+
+struct type {
+    struct hashmap_entry hashmap_entry;
+
+    enum type_kind kind;
+    char *name;
+    size_t name_len;
+
+    size_t size;
+
+    union {
+        int n_ptrs;
+        struct hashmap members;
+    };
+};
+
+void parse_type(struct parser *ctx);
+
+#endif /* !_PARSER_TYPE_H */