aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.exrc1
-rw-r--r--.gitignore3
-rw-r--r--Makefile46
-rw-r--r--README.md7
-rw-r--r--compile_commands.json167
-rw-r--r--include/ast.h170
-rw-r--r--include/eval.h20
-rw-r--r--include/hmap.h53
-rw-r--r--include/lexer.h25
-rw-r--r--include/object.h81
-rw-r--r--include/parser.h33
-rw-r--r--include/repl.h8
-rw-r--r--include/slice.h27
-rw-r--r--include/tests/tests.h45
-rw-r--r--include/token.h55
-rw-r--r--include/vector.h27
-rw-r--r--src/ast.c381
-rw-r--r--src/cmonkey.c16
-rw-r--r--src/eval.c333
-rw-r--r--src/hmap.c225
-rw-r--r--src/lexer.c187
-rw-r--r--src/object.c195
-rw-r--r--src/parser.c605
-rw-r--r--src/repl.c67
-rw-r--r--src/slice.c77
-rw-r--r--src/tests/ast.c42
-rw-r--r--src/tests/eval.c332
-rw-r--r--src/tests/lexer.c126
-rw-r--r--src/tests/parser.c640
-rw-r--r--src/tests/slice.c41
-rw-r--r--src/token.c106
-rw-r--r--src/vector.c42
32 files changed, 4183 insertions, 0 deletions
diff --git a/.exrc b/.exrc
new file mode 100644
index 0000000..236a385
--- /dev/null
+++ b/.exrc
@@ -0,0 +1 @@
+let ch_syntax_for_h = 1
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..b0b5a06
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+.cache
+obj/
+build/
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..60481b3
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,46 @@
+CC?=gcc
+XFLAGS=
+CFLAGS?=-std=c11 -O2 -Wall $(XFLAGS)
+
+LIBS:=
+IDIRS:=$(addprefix -iquote,include)
+
+BUILDIR?=build/release
+
+ifdef DEBUG
+BUILDIR:=build/debug
+CFLAGS:=-std=c11 -O0 -DDEBUG $(XFLAGS) -g
+endif
+ifdef ASAN
+CFLAGS+= -fsanitize=address -fno-omit-frame-pointer
+endif
+
+OBJDIR=$(BUILDIR)/obj
+
+CMONKEY_SRCS:=$(shell find src -name '*.c' -not -path '*/tests/*')
+CMONKEY_OBJS:=$(CMONKEY_SRCS:%.c=$(OBJDIR)/%.o)
+ALL_OBJS:=$(CMONKEY_OBJS)
+TEST_OBJS:=$(filter-out $(OBJDIR)/src/cmonkey.o,$(ALL_OBJS))
+
+all: cmonkey
+
+test: tests/lexer tests/slice tests/parser tests/ast tests/eval
+
+tests/%: $(OBJDIR)/src/tests/%.o $(TEST_OBJS)
+ mkdir -p $(BUILDIR)/$(@D)
+ $(CC) -o $(BUILDIR)/$@ $^ $(IDIRS) $(LIBS) $(CFLAGS)
+
+$(OBJDIR)/%.o: %.c
+ mkdir -p $(@D)
+ $(CC) -c $(IDIRS) -o $@ $< $(LIBS) $(CFLAGS)
+
+cmonkey: $(ALL_OBJS)
+ mkdir -p $(@D)
+ $(CC) -o $(BUILDIR)/$@ $^ $(LIBS) $(CFLAGS)
+
+clean:
+ rm -r build
+
+.PHONY: clean all test
+
+.PRECIOUS: $(OBJDIR)/src/tests/%.o
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..f684d21
--- /dev/null
+++ b/README.md
@@ -0,0 +1,7 @@
+# cmonkey
+
+A monkey programming language interpreter written in C11. From Thorsten Ball's
+[Writing an Interpreter in Go](https://interpreterbook.com/) book, except I
+wrote mine in C, just for lulz.
+
+TODO: chapter 4, GC, debug
diff --git a/compile_commands.json b/compile_commands.json
new file mode 100644
index 0000000..0dd5bca
--- /dev/null
+++ b/compile_commands.json
@@ -0,0 +1,167 @@
+[
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/lexer.o",
+ "src/lexer.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/lexer.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/token.o",
+ "src/token.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/token.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/cmonkey.o",
+ "src/cmonkey.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/cmonkey.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/hmap.o",
+ "src/hmap.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/hmap.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/slice.o",
+ "src/slice.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/slice.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/repl.o",
+ "src/repl.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/repl.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/parser.o",
+ "src/parser.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/parser.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/eval.o",
+ "src/eval.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/eval.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/vector.o",
+ "src/vector.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/vector.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/ast.o",
+ "src/ast.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/ast.c"
+ },
+ {
+ "directory": "/home/yaroslav/repos/personal/cmonkey",
+ "arguments": [
+ "cc",
+ "-c",
+ "-iquoteinclude",
+ "-o",
+ "build/release/obj/src/object.o",
+ "src/object.c",
+ "-std=c11",
+ "-O2",
+ "-Wall"
+ ],
+ "file": "src/object.c"
+ }
+]
diff --git a/include/ast.h b/include/ast.h
new file mode 100644
index 0000000..eb3e1fc
--- /dev/null
+++ b/include/ast.h
@@ -0,0 +1,170 @@
+#ifndef CMONKEY_AST_H
+#define CMONKEY_AST_H
+
+#include "token.h"
+#include "vector.h"
+
+enum node_type {
+ NODE_PROGRAM,
+ NODE_STATEMENT,
+ NODE_EXPRESSION,
+};
+
+enum statement_type {
+ STATEMENT_LET,
+ STATEMENT_RETURN,
+ STATEMENT_EXPRESSION,
+ STATEMENT_BLOCK,
+};
+
+enum expression_type {
+ EXPRESSION_IDENT,
+ EXPRESSION_INT,
+ EXPRESSION_BOOL,
+ EXPRESSION_PREFIX,
+ EXPRESSION_INFIX,
+ EXPRESSION_IF,
+ EXPRESSION_FUNC,
+ EXPRESSION_CALL,
+};
+
+struct identifier {
+ struct token token;
+ struct slice value;
+};
+
+struct prefix_expression {
+ struct token token;
+ struct slice operator;
+ struct expression *right;
+};
+
+struct infix_expression {
+ struct token token;
+ struct slice operator;
+ struct expression *left;
+ struct expression *right;
+};
+
+struct integer_expression {
+ struct token token;
+ int64_t value;
+};
+
+struct boolean_expression {
+ struct token token;
+ bool value;
+};
+
+struct if_expression {
+ struct token token;
+ struct expression *condition;
+ struct statement *consequence;
+ struct statement *alternative;
+};
+
+struct func_literal {
+ struct token token;
+ struct vector *parameters; // expression type ident
+ struct statement *body;
+};
+
+struct call_expression {
+ struct token token;
+ struct expression *func;
+ struct vector *arguments; // expressions
+};
+
+struct expression {
+ enum expression_type type;
+ union {
+ struct token token; // Common initial sequence
+ struct identifier ident;
+ struct integer_expression integer;
+ struct boolean_expression boolean;
+ struct prefix_expression prefix;
+ struct infix_expression infix;
+ struct if_expression cond;
+ struct func_literal func;
+ struct call_expression call;
+ };
+};
+
+struct expression_statement {
+ struct token token;
+ struct expression *expr;
+};
+
+struct return_statement {
+ struct token token;
+ struct expression *value;
+};
+
+struct let_statement {
+ struct token token;
+ struct identifier *name;
+ struct expression *value;
+};
+
+struct block_statement {
+ struct token token;
+ struct vector *statements;
+};
+
+struct program {
+ struct vector *statements;
+};
+
+struct statement {
+ enum statement_type type;
+ union {
+ struct token token; // Common initial sequence
+ struct let_statement let;
+ struct return_statement retrn;
+ struct expression_statement expr;
+ struct block_statement block;
+ };
+};
+
+struct slice expression_token_literal(struct expression *);
+struct slice statement_token_literal(struct statement *);
+struct slice program_token_literal(struct program *);
+
+#define node_token_literal(n) _Generic((n), \
+ struct program *: program_token_literal, \
+ struct statement *: statement_token_literal, \
+ struct expression *: expression_token_literal \
+ )(n)
+
+char *expression_sprint(struct expression *, char *str);
+char *statement_sprint(struct statement *, char *str);
+char *program_sprint(struct program *, char *str);
+
+#define node_sprint(n, a) _Generic((n), \
+ struct expression *: expression_sprint, \
+ struct statement *: statement_sprint, \
+ struct program *: program_sprint \
+ )(n, a)
+
+struct vector *expression_vector_dup(const struct vector *);
+struct vector *statement_vector_dup(const struct vector *);
+
+struct expression *expression_dup(const struct expression *);
+struct statement *statement_dup(const struct statement *);
+
+#define node_dup(n) _Generic((n), \
+ struct expression *: expression_dup, \
+ struct statement *: statement_dup \
+ )(n)
+
+void expression_destroy(struct expression *);
+void statement_destroy(struct statement *);
+void program_destroy(struct program *);
+
+#define node_destroy(n) _Generic((n), \
+ struct expression *: expression_destroy, \
+ struct statement *: statement_destroy, \
+ struct program *: program_destroy \
+ )(n)
+
+#endif
diff --git a/include/eval.h b/include/eval.h
new file mode 100644
index 0000000..5f19271
--- /dev/null
+++ b/include/eval.h
@@ -0,0 +1,20 @@
+#ifndef CMONKEY_EVAL_H
+#define CMONKEY_EVAL_H
+
+#include "ast.h"
+#include "parser.h"
+#include "object.h"
+
+struct object *eval_program(struct environment *, struct program *);
+
+struct object *eval_statement(struct environment *, struct statement *);
+
+struct object *eval_expression(struct environment *, struct expression *);
+
+#define eval(e, n) _Generic((n), \
+ struct program *: eval_program, \
+ struct statement *: eval_statement, \
+ struct expression *: eval_expression \
+ )(e, n)
+
+#endif
diff --git a/include/hmap.h b/include/hmap.h
new file mode 100644
index 0000000..853df1c
--- /dev/null
+++ b/include/hmap.h
@@ -0,0 +1,53 @@
+#ifndef UNJA_HASHMAP_H
+#define UNJA_HASHMAP_H
+#include <stdbool.h>
+#include <sys/types.h>
+
+#include "slice.h"
+
+#ifndef HASHMAP_CAP
+#define HASHMAP_CAP 32
+#endif
+
+typedef void (hmap_cb)(const void *key, void *value);
+
+struct hmap {
+ struct hnode **buckets;
+ size_t cap;
+ size_t size;
+};
+
+/* allocate a new hmap */
+struct hmap *hmap_new_with_cap(size_t cap);
+
+#define hmap_new() hmap_new_with_cap(HASHMAP_CAP)
+
+
+/*
+ * Inserts a key-value pair into the map. Returns NULL if map did not have key,
+ * old value if it did.
+ */
+void *hmap_sets(struct hmap *hm, struct slice key, void *value);
+void *hmap_set(struct hmap *hm, const char *key, void *value);
+
+/* Returns a pointer to the value corresponding to the key. */
+void *hmap_gets(struct hmap *hm, const struct slice *key);
+void *hmap_get(struct hmap *hm, const char *key);
+
+/*
+ * Removes a key from the map, returning the value at the key if the key was
+ * previously in the map.
+ */
+void *hmap_removes(struct hmap *hm, const struct slice *key);
+void *hmap_remove(struct hmap *hm, const char *key);
+
+/* Iterate over keys in the hmap */
+void hmap_walk(struct hmap *hm, hmap_cb);
+
+/* free hmap related memory calling a function before freeing each node */
+void hmap_destroy(struct hmap *hm, hmap_cb cb);
+
+/* free hmap related memory */
+void hmap_free(struct hmap *hm);
+
+#endif
diff --git a/include/lexer.h b/include/lexer.h
new file mode 100644
index 0000000..d693354
--- /dev/null
+++ b/include/lexer.h
@@ -0,0 +1,25 @@
+#ifndef CMONKEY_LEXER_H
+#define CMONKEY_LEXER_H
+
+#include "slice.h"
+#include "token.h"
+
+#include <sys/types.h>
+
+struct lexer {
+ const char *input;
+ size_t len;
+ struct slice word;
+};
+
+struct lexer *lexer_new();
+
+void lexer_reset(struct lexer *, const char *input);
+
+void lexer_read_char(struct lexer *);
+
+struct token lexer_next_token(struct lexer *);
+
+void lexer_destroy(struct lexer *);
+
+#endif
diff --git a/include/object.h b/include/object.h
new file mode 100644
index 0000000..55ac741
--- /dev/null
+++ b/include/object.h
@@ -0,0 +1,81 @@
+#ifndef CMONKEY_OBJECT_H
+#define CMONKEY_OBJECT_H
+
+#include "ast.h"
+#include "hmap.h"
+
+#include <stdbool.h>
+#include <sys/types.h>
+
+enum object_type {
+ OBJECT_ERROR,
+ OBJECT_NULL,
+ OBJECT_INT,
+ OBJECT_BOOL,
+ OBJECT_RETURN,
+ OBJECT_FUNC,
+};
+
+struct error_object {
+ char *msg;
+};
+
+struct return_object {
+ struct object *value;
+};
+
+struct func_object {
+ struct vector *params; // identifier_expressions
+ struct statement *body;
+};
+
+struct object {
+ enum object_type type;
+ size_t refcount;
+ union {
+ bool boolean;
+ int64_t integer;
+ struct return_object retrn;
+ struct error_object error;
+ struct func_object func;
+ };
+};
+
+struct environment {
+ struct hmap *store;
+ struct environment *outer;
+};
+
+char *object_sprint(struct object *, char *str);
+
+inline const char *object_type_print(enum object_type);
+
+struct object *object_new_int(int64_t val);
+struct object *object_new_error(char *msg);
+struct object *object_new_return(struct object *val);
+struct object *object_new_func(struct expression *);
+
+#define object_new(v) _Generic((v), \
+ int: object_new_int, \
+ int64_t: object_new_int, \
+ char *: object_new_error, \
+ struct object *: object_new_return, \
+ struct expression *: object_new_func \
+ )(v)
+
+void object_ref(struct object *);
+
+void object_unref(struct object *);
+
+struct environment *environment_new_enclosed(struct environment *outer);
+
+#define environment_new() environment_new_enclosed(NULL)
+
+struct object *environment_set(struct environment *,
+ struct slice key, struct object *val);
+
+struct object *environment_get(struct environment *, const struct slice *key);
+
+void environment_destroy(struct environment *);
+
+#endif
diff --git a/include/parser.h b/include/parser.h
new file mode 100644
index 0000000..b344a7b
--- /dev/null
+++ b/include/parser.h
@@ -0,0 +1,33 @@
+#ifndef CMONKEY_PARSER_H
+#define CMONKEY_PARSER_H
+
+#include "ast.h"
+#include "hmap.h"
+#include "lexer.h"
+#include "token.h"
+#include "vector.h"
+
+struct parser {
+ struct lexer *lexer;
+ struct token cur_token;
+ struct token peek_token;
+ struct vector *errors;
+ struct hmap *prefix_fns;
+ struct hmap *infix_fns;
+ struct hmap *precedences;
+};
+
+typedef struct expression *(*prefix_parse_f)(struct parser *);
+typedef struct expression *(*infix_parse_f)(struct parser *, struct expression *);
+
+struct parser *parser_new();
+
+void parser_reset(struct parser *, const char *input);
+
+void parser_next_token(struct parser *);
+
+struct program *parser_parse_program(struct parser *);
+
+void parser_destroy(struct parser *);
+
+#endif
diff --git a/include/repl.h b/include/repl.h
new file mode 100644
index 0000000..f7aeafc
--- /dev/null
+++ b/include/repl.h
@@ -0,0 +1,8 @@
+#ifndef CMONKEY_REPL_H
+#define CMONKEY_REPL_H
+
+#include <stdio.h>
+
+void repl_start(FILE *in, FILE *out);
+
+#endif
diff --git a/include/slice.h b/include/slice.h
new file mode 100644
index 0000000..26f9fd7
--- /dev/null
+++ b/include/slice.h
@@ -0,0 +1,27 @@
+#ifndef CMONKEY_SLICE_H
+#define CMONKEY_SLICE_H
+
+#include <sys/types.h>
+
+struct slice {
+ const char *str;
+ size_t start;
+ size_t end;
+};
+
+struct slice slice_new(const char *str, size_t start, size_t end);
+
+struct slice slice_fullstr(const char *str);
+
+void slice_set(struct slice *, const char *str, size_t start, size_t end);
+
+size_t slice_len(const struct slice *);
+
+/* Returns 0 if equal, 1 if a > b, -1 if a < b */
+int slice_cmp(const struct slice *restrict a, const struct slice *restrict b);
+
+void slice_cpy(struct slice *dst, const struct slice *src);
+
+char *slice_sprint(struct slice *, char *str);
+
+#endif
diff --git a/include/tests/tests.h b/include/tests/tests.h
new file mode 100644
index 0000000..8c89fcc
--- /dev/null
+++ b/include/tests/tests.h
@@ -0,0 +1,45 @@
+#ifndef TESTS_H
+#define TESTS_H
+#include <stdio.h>
+#include <stdlib.h>
+
+#ifndef NOCOLOR
+#define TBLD "\033[1m"
+#define TRED "\033[31m"
+#define TGRN "\033[32m"
+#define TBLU "\033[34m"
+#define TRST "\033[0m"
+#else
+#define TBLD ""
+#define TRED ""
+#define TGRN ""
+#define TBLU ""
+#define TRST ""
+#endif
+
+#define RUN_TEST(test_func) \
+ printf("%s:\t", #test_func); \
+ fflush(stdout); \
+ test_func(); \
+ printf(TGRN "OK!\n" TRST)
+
+#define INIT_TESTS() \
+ printf(TBLD "running %s tests\n" TRST, __FILE__)
+
+#define FAIL_TEST(reason) \
+ printf(TBLD TRED "FAIL!\n" TRST); \
+ printf("%s:%d: %s: ", __FILE__, __LINE__, __func__); \
+ printf(reason); \
+ abort()
+
+#define asserteq(a, b) \
+ if (a != b) { \
+ FAIL_TEST("assertion " TBLD TBLU #a " == " #b TRST " failed\n"); \
+ }
+
+#define assertneq(a, b) \
+ if (a == b) { \
+ FAIL_TEST("assertion " TBLD TBLU #a " != " #b TRST " failed\n"); \
+ }
+
+#endif
diff --git a/include/token.h b/include/token.h
new file mode 100644
index 0000000..2f3cbb3
--- /dev/null
+++ b/include/token.h
@@ -0,0 +1,55 @@
+#ifndef CMONKEY_TOKEN_H
+#define CMONKEY_TOKEN_H
+
+#include "slice.h"
+
+enum token_type {
+ TOKEN_ILLEGAL,
+ TOKEN_EOF,
+ /* Identifiers/Literals */
+ TOKEN_IDENT,
+ TOKEN_INT,
+ /* Operators */
+ TOKEN_ASSIGN,
+ TOKEN_PLUS,
+ TOKEN_MINUS,
+ TOKEN_BANG,
+ TOKEN_ASTERISK,
+ TOKEN_SLASH,
+ TOKEN_LT,
+ TOKEN_GT,
+ TOKEN_EQ,
+ TOKEN_NOTEQ,
+ /* Delimiters */
+ TOKEN_COMMA,
+ TOKEN_SEMICOLON,
+ TOKEN_LPAREN,
+ TOKEN_RPAREN,
+ TOKEN_LBRACE,
+ TOKEN_RBRACE,
+ /* Keywords */
+ TOKEN_FUNC,
+ TOKEN_LET,
+ TOKEN_TRUE,
+ TOKEN_FALSE,
+ TOKEN_IF,
+ TOKEN_ELSE,
+ TOKEN_RETURN,
+};
+
+struct token {
+ enum token_type type;
+ struct slice literal;
+};
+
+void token_init_keywords(void);
+
+enum token_type token_lookup_ident(const struct slice *ident);
+
+inline const char *token_type_print(enum token_type);
+
+char *token_sprint(struct token *, char *str);
+
+void token_free_keywords(void);
+
+#endif
diff --git a/include/vector.h b/include/vector.h
new file mode 100644
index 0000000..a34ecea
--- /dev/null
+++ b/include/vector.h
@@ -0,0 +1,27 @@
+#ifndef VECTOR_H
+#define VECTOR_H
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <sys/types.h>
+
+#define VEC_CAP 32
+
+struct vector {
+ size_t cap;
+ size_t len;
+ void **values;
+};
+
+struct vector *vector_new_with_cap(size_t cap);
+
+#define vector_new() vector_new_with_cap(VEC_CAP)
+
+ssize_t vector_push(struct vector *, void *val);
+
+void vector_free(struct vector *);
+
+#define vector_foreach(vec, i, val) \
+ for (i = 0, val = vec->values[i]; i < vec->len; i++, val = vec->values[i])
+
+#endif
diff --git a/src/ast.c b/src/ast.c
new file mode 100644
index 0000000..c86414e
--- /dev/null
+++ b/src/ast.c
@@ -0,0 +1,381 @@
+#include "ast.h"
+#include "slice.h"
+#include "vector.h"
+
+#include <stdio.h>
+#include <string.h>
+
+#define MEMCPY(d, s) memcpy(d, s, sizeof(*d))
+
+#define MEMDUP(T, d, s) T d = malloc(sizeof(*d)); memcpy(d, s, sizeof(*d))
+
+struct slice
+expression_token_literal(struct expression *expr)
+{
+ return expr->token.literal;
+}
+
+struct slice
+statement_token_literal(struct statement *st)
+{
+ return st->token.literal;
+}
+
+struct slice
+program_token_literal(struct program *prog)
+{
+ if (prog->statements->len > 0) {
+ return node_token_literal(
+ (struct statement *)prog->statements->values[0]);
+ } else {
+ return slice_new("", 0, 0);
+ }
+}
+
+static inline char *
+let_statement_sprint(struct let_statement *st, char *str)
+{
+ char litbuf[32];
+ char namebuf[32];
+ sprintf(str, "%s %s = ", slice_sprint(&st->token.literal, litbuf),
+ slice_sprint(&st->name->value, namebuf));
+ char *cur = str + strlen(str);
+ expression_sprint(st->value, cur);
+ cur += strlen(cur);
+ cur[0] = ';', cur[1] = '\0';
+ return str;
+}
+
+static inline char *
+return_statement_sprint(struct return_statement *st, char *str)
+{
+ char litbuf[32];
+ sprintf(str, "%s ", slice_sprint(&st->token.literal, litbuf));
+ char *cur = str + strlen(str);
+ expression_sprint(st->value, cur);
+ cur += strlen(cur);
+ cur[0] = ';', cur[1] = '\0';
+ return str;
+}
+
+static inline char *
+block_statement_sprint(struct block_statement *st, char *str)
+{
+ size_t i;
+ struct statement *v;
+ char *cur = str;
+ vector_foreach(st->statements, i, v) {
+ statement_sprint(v, cur);
+ cur += strlen(cur);
+ }
+ return str;
+}
+
+static inline char *
+expression_statement_sprint(struct expression_statement *st, char *str)
+{
+ return expression_sprint(st->expr, str);
+}
+
+static inline char *
+prefix_expression_sprint(struct prefix_expression *expr, char *str)
+{
+ *str = '(';
+ char *cur = str + 1;
+ slice_sprint(&expr->operator, cur);
+ cur += strlen(cur);
+ expression_sprint(expr->right, cur);
+ cur += strlen(cur);
+ cur[0] = ')', cur[1] = '\0';
+ return str;
+}
+
+static inline char *
+infix_expression_sprint(struct infix_expression *expr, char *str)
+{
+ *str = '(';
+ char *cur = str + 1;
+ expression_sprint(expr->left, cur);
+ cur += strlen(cur);
+ *cur = ' ', cur++;
+ slice_sprint(&expr->operator, cur);
+ cur += strlen(cur);
+ *cur = ' ', cur++;
+ expression_sprint(expr->right, cur);
+ cur += strlen(cur);
+ cur[0] = ')', cur[1] = '\0';
+ return str;
+}
+
+static inline char *
+if_expression_sprint(struct if_expression *expr, char *str)
+{
+ char *cur = str;
+ strcpy(cur, "if ");
+ cur += strlen(cur);
+ expression_sprint(expr->condition, cur);
+ cur += strlen(cur);
+ *cur = ' ', cur++;
+ statement_sprint(expr->consequence, cur);
+ if (expr->alternative) {
+ cur += strlen(cur);
+ strcpy(cur, "else ");
+ cur += strlen(cur);
+ statement_sprint(expr->alternative, cur);
+ }
+
+ return str;
+}
+
+static inline char *
+func_literal_sprint(struct func_literal *expr, char *str)
+{
+ char *cur = str;
+ slice_sprint(&expr->token.literal, cur);
+ cur += strlen(cur);
+ *cur = '(', cur++;
+ size_t i;
+ struct expression *ident;
+ vector_foreach(expr->parameters, i, ident) {
+ slice_sprint(&ident->token.literal, cur);
+ cur += strlen(cur);
+ if (i < (expr->parameters->len - 1)) {
+ cur[0] = ',', cur[1] = ' ', cur += 2;
+ }
+ }
+ *cur = ')', cur++;
+ statement_sprint(expr->body, cur);
+
+ return str;
+}
+
+static inline char *
+call_expression_sprint(struct call_expression *expr, char *str)
+{
+ char *cur = str;
+ expression_sprint(expr->func, cur);
+ cur += strlen(cur);
+ *cur = '(', cur++;
+ size_t i;
+ struct expression *arg;
+ vector_foreach(expr->arguments, i, arg) {
+ expression_sprint(arg, cur);
+ cur += strlen(cur);
+ if (i < (expr->arguments->len - 1)) {
+ cur[0] = ',', cur[1] = ' ', cur += 2;
+ }
+ }
+ cur[0] = ')', cur[1] = '\0';
+
+ return str;
+}
+
+char *
+expression_sprint(struct expression *expr, char *str)
+{
+ switch (expr->type) {
+ case EXPRESSION_PREFIX:
+ return prefix_expression_sprint(&expr->prefix, str);
+ case EXPRESSION_INFIX:
+ return infix_expression_sprint(&expr->infix, str);
+ case EXPRESSION_IF:
+ return if_expression_sprint(&expr->cond, str);
+ case EXPRESSION_FUNC:
+ return func_literal_sprint(&expr->func, str);
+ case EXPRESSION_CALL:
+ return call_expression_sprint(&expr->call, str);
+ case EXPRESSION_IDENT:
+ case EXPRESSION_INT:
+ case EXPRESSION_BOOL:
+ return slice_sprint(&expr->token.literal, str);
+ }
+};
+
+char *
+statement_sprint(struct statement *st, char *str)
+{
+ switch (st->type) {
+ case STATEMENT_LET:
+ return let_statement_sprint(&st->let, str);
+ case STATEMENT_RETURN:
+ return return_statement_sprint(&st->retrn, str);
+ case STATEMENT_EXPRESSION:
+ return expression_statement_sprint(&st->expr, str);
+ case STATEMENT_BLOCK:
+ return block_statement_sprint(&st->block, str);
+ }
+}
+
+char *
+program_sprint(struct program *prog, char *str)
+{
+ size_t i;
+ struct statement *st;
+ char *cur = str;
+ vector_foreach(prog->statements, i, st) {
+ statement_sprint(st, cur);
+ cur += strlen(cur);
+ }
+ return str;
+}
+
+struct vector *
+expression_vector_dup(const struct vector *vec)
+{
+ struct vector *dupv = vector_new_with_cap(vec->cap);
+ size_t i;
+ struct expression *expr;
+ vector_foreach(vec, i, expr) {
+ struct expression *dupexpr = node_dup(expr);
+ vector_push(dupv, dupexpr);
+ }
+
+ return dupv;
+}
+
+struct vector *
+statement_vector_dup(const struct vector *vec)
+{
+ struct vector *dupv = vector_new_with_cap(vec->cap);
+ size_t i;
+ struct statement *subst;
+ vector_foreach(vec, i, subst) {
+ struct statement *dupsub = node_dup(subst);
+ vector_push(dupv, dupsub);
+ }
+
+ return dupv;
+}
+
+struct expression *
+expression_dup(const struct expression *expr)
+{
+ MEMDUP(struct expression *, dupd, expr);
+ switch (expr->type) {
+ case EXPRESSION_IDENT:
+ case EXPRESSION_INT:
+ case EXPRESSION_BOOL:
+ return dupd;
+ case EXPRESSION_PREFIX:
+ dupd->prefix.right = node_dup(expr->prefix.right);
+ return dupd;
+ case EXPRESSION_INFIX:
+ dupd->infix.left = node_dup(expr->infix.left);
+ dupd->infix.right = node_dup(expr->infix.right);
+ return dupd;
+ case EXPRESSION_IF:
+ dupd->cond.condition = node_dup(expr->cond.condition);
+ dupd->cond.consequence = node_dup(expr->cond.consequence);
+ dupd->cond.alternative = node_dup(expr->cond.alternative);
+ return dupd;
+ case EXPRESSION_FUNC:
+ dupd->func.parameters = expression_vector_dup(expr->func.parameters);
+ dupd->func.body = node_dup(expr->func.body);
+ return dupd;
+ case EXPRESSION_CALL:
+ dupd->call.func = node_dup(expr->call.func);
+ dupd->call.arguments = expression_vector_dup(expr->call.arguments);
+ return dupd;
+ }
+}
+
+struct statement *
+statement_dup(const struct statement *st)
+{
+ MEMDUP(struct statement *, dupd, st);
+ switch (st->type) {
+ case STATEMENT_LET:
+ MEMDUP(, dupd->let.name, st->let.name);
+ dupd->let.value = node_dup(st->let.value);
+ return dupd;
+ case STATEMENT_RETURN:
+ dupd->retrn.value = node_dup(st->retrn.value);
+ return dupd;
+ case STATEMENT_EXPRESSION:
+ dupd->expr.expr = node_dup(st->expr.expr);
+ return dupd;
+ case STATEMENT_BLOCK:
+ dupd->block.statements = statement_vector_dup(st->block.statements);
+ return dupd;
+ }
+}
+
+void
+expression_destroy(struct expression *expr)
+{
+ switch (expr->type) {
+ case EXPRESSION_PREFIX:
+ expression_destroy(expr->prefix.right);
+ break;
+ case EXPRESSION_INFIX:
+ expression_destroy(expr->infix.right);
+ expression_destroy(expr->infix.left);
+ break;
+ case EXPRESSION_IF:
+ expression_destroy(expr->cond.condition);
+ statement_destroy(expr->cond.consequence);
+ if (expr->cond.alternative) statement_destroy(expr->cond.alternative);
+ break;
+ case EXPRESSION_FUNC: {
+ size_t i;
+ struct expression *param;
+ vector_foreach(expr->func.parameters, i ,param) {
+ node_destroy(param);
+ }
+ vector_free(expr->func.parameters);
+ node_destroy(expr->func.body);
+ break;
+ }
+ case EXPRESSION_CALL: {
+ size_t i;
+ struct expression *arg;
+ vector_foreach(expr->call.arguments, i ,arg) {
+ node_destroy(arg);
+ }
+ expression_destroy(expr->call.func);
+ vector_free(expr->call.arguments);
+ break;
+ }
+ default:
+ break;
+ }
+ free(expr);
+}
+
+void
+statement_destroy(struct statement *st)
+{
+ switch (st->type) {
+ case STATEMENT_LET:
+ free(st->let.name);
+ node_destroy(st->let.value);
+ break;
+ case STATEMENT_RETURN:
+ node_destroy(st->retrn.value);
+ break;
+ case STATEMENT_EXPRESSION:
+ if (st->expr.expr) node_destroy(st->expr.expr);
+ break;
+ case STATEMENT_BLOCK:;
+ size_t i;
+ struct statement *subst;
+ vector_foreach(st->block.statements, i ,subst) {
+ node_destroy(subst);
+ }
+ vector_free(st->block.statements);
+ break;
+ }
+ free(st);
+}
+
+void
+program_destroy(struct program *prog)
+{
+ size_t i;
+ struct statement *st;
+ vector_foreach(prog->statements, i ,st) {
+ node_destroy(st);
+ }
+ vector_free(prog->statements);
+ free(prog);
+}
diff --git a/src/cmonkey.c b/src/cmonkey.c
new file mode 100644
index 0000000..64e61d6
--- /dev/null
+++ b/src/cmonkey.c
@@ -0,0 +1,16 @@
+#include "repl.h"
+
+#include <stdio.h>
+
+int
+main(int argc, char *argv[])
+{
+ /* TODO: read from file, interpret and exit
+ if (argc > 1) {
+ FILE *in = fopen(argv[1], "r");
+ }
+ */
+ printf("Welcome to the CMonkey interpreter of the Monkey language!\n");
+ printf("Enter any commands to begin\n");
+ repl_start(stdin, stdout);
+}
diff --git a/src/eval.c b/src/eval.c
new file mode 100644
index 0000000..c1a6a10
--- /dev/null
+++ b/src/eval.c
@@ -0,0 +1,333 @@
+#include "eval.h"
+#include "ast.h"
+#include "object.h"
+#include "token.h"
+
+#include <stdarg.h>
+#include <stdio.h>
+
+static struct object obj_null = {
+ OBJECT_NULL,
+ 2,
+ { 0 },
+};
+static struct object obj_true = {
+ OBJECT_BOOL,
+ 2,
+ .boolean = true,
+};
+static struct object obj_false = {
+ OBJECT_BOOL,
+ 2,
+ .boolean = false,
+};
+
+static inline struct object *
+get_bool_object(bool val)
+{
+ struct object *obj = val ? &obj_true : &obj_false;
+ return obj;
+}
+
+static struct object *
+new_error(char *fmt, ...)
+{
+ char *msg = malloc(1024);
+ struct object *obj = object_new(msg);
+
+ va_list args;
+ va_start(args, fmt);
+ vsprintf(obj->error.msg, fmt, args);
+ va_end(args);
+
+ return obj;
+}
+
+static struct object *
+eval_statements(struct environment *env, struct vector *sts)
+{
+ size_t i;
+ struct object *res;
+ struct statement *st;
+ vector_foreach(sts, i, st) {
+ res = eval(env, st);
+ if (res->type == OBJECT_RETURN || res->type == OBJECT_ERROR) {
+ return res;
+ }
+ }
+ return res;
+}
+
+static inline struct object *
+eval_bang_prefix_expression(struct environment *env, struct object *right)
+{
+ struct object *res;
+ res = get_bool_object(!right->integer);
+ object_unref(right);
+ return res;
+}
+
+static inline struct object *
+eval_minus_prefix_expression(struct environment *env, struct object *right)
+{
+ struct object *res;
+ if (right->type != OBJECT_INT) {
+ struct object *error = new_error("unknown operator: -%s",
+ object_type_print(right->type));
+ object_unref(right);
+ return error;
+ }
+ res = object_new(-right->integer);
+ object_unref(right);
+ return res;
+}
+
+static struct object *
+eval_prefix_expression(struct environment *env, struct token op,
+ struct object *right)
+{
+ struct object *res;
+ switch (op.type) {
+ case TOKEN_BANG:
+ return eval_bang_prefix_expression(env, right);
+ case TOKEN_MINUS:
+ return eval_minus_prefix_expression(env, right);
+ default:;
+ char buf[256];
+ struct object *error = new_error("unknown operator: %s%s",
+ slice_sprint(&op.literal, buf), object_type_print(right->type));
+ object_unref(right);
+ return error;
+ }
+}
+
+static inline struct object *
+eval_integer_infix_expression(struct environment *env, struct token op,
+ struct object *left, struct object *right)
+{
+ bool bres;
+ struct object *ires;
+ switch (op.type) {
+ case TOKEN_PLUS:
+ ires = object_new(left->integer + right->integer);
+ break;
+ case TOKEN_MINUS:
+ ires = object_new(left->integer - right->integer);
+ break;
+ case TOKEN_ASTERISK:
+ ires = object_new(left->integer * right->integer);
+ break;
+ case TOKEN_SLASH:
+ ires = object_new(left->integer / right->integer);
+ break;
+ case TOKEN_LT:
+ bres = left->integer < right->integer;
+ goto boolres;
+ case TOKEN_GT:
+ bres = left->integer > right->integer;
+ goto boolres;
+ case TOKEN_EQ:
+ bres = left->integer == right->integer;
+ goto boolres;
+ case TOKEN_NOTEQ:
+ bres = left->integer != right->integer;
+ goto boolres;
+ default:;
+ char buf[256];
+ struct object *error = new_error("unknown operator: %s %s %s",
+ object_type_print(left->type), slice_sprint(&op.literal, buf),
+ object_type_print(right->type));
+ object_unref(left);
+ object_unref(right);
+ return error;
+ }
+ object_unref(left);
+ object_unref(right);
+ return ires;
+boolres:
+ object_unref(left);
+ object_unref(right);
+ return get_bool_object(bres);
+}
+
+static inline struct object *
+eval_infix_expression(struct environment *env, struct token op,
+ struct object *left, struct object *right)
+{
+ if (left->type == OBJECT_INT && right->type == OBJECT_INT) {
+ return eval_integer_infix_expression(env, op, left, right);
+ }
+ bool res;
+ switch (op.type) {
+ case TOKEN_EQ:
+ res = left->integer == right->integer;
+ break;
+ case TOKEN_NOTEQ:
+ res = left->integer != right->integer;
+ break;
+ default:;
+ char buf[256];
+ struct object *error;
+ if (left->type != right->type) {
+ error = new_error("type mismatch: %s %s %s",
+ object_type_print(left->type), slice_sprint(&op.literal, buf),
+ object_type_print(right->type));
+ } else {
+ error = new_error("unknown operator: %s %s %s",
+ object_type_print(left->type), slice_sprint(&op.literal, buf),
+ object_type_print(right->type));
+ }
+ object_unref(left);
+ object_unref(right);
+ return error;
+ }
+ object_unref(left);
+ object_unref(right);
+ return get_bool_object(res);
+}
+
+static inline struct object *
+eval_if_expression(struct environment *env, struct if_expression *expr)
+{
+ struct object *cond = eval(env, expr->condition);
+ struct object *res;
+ if (cond->boolean) {
+ res = eval(env, expr->consequence);
+ } else if (expr->alternative) {
+ res = eval(env, expr->alternative);
+ } else {
+ res = &obj_null;
+ }
+ object_unref(cond);
+ return res;
+}
+
+static inline struct object *
+eval_call_expression(struct environment *env, struct expression *expr)
+{
+ struct object *func = eval(env, expr->call.func);
+ if (func->type == OBJECT_ERROR) {
+ return func;
+ } else if (func->type != OBJECT_FUNC) {
+ char buf[256];
+ struct object *err = new_error("not a function: %s",
+ object_sprint(func, buf));
+ object_unref(func);
+ return err;
+ }
+ size_t i;
+ struct expression *arg;
+ struct environment *fenv = environment_new_enclosed(env);
+ vector_foreach(expr->call.arguments, i, arg) {
+ struct object *obj = eval(env, arg);
+ if (obj->type == OBJECT_ERROR) {
+ object_unref(func);
+ return obj;
+ }
+ struct expression *param = func->func.params->values[i];
+ environment_set(fenv, param->ident.value, obj);
+ object_unref(obj);
+ }
+ struct object *res = eval(fenv, func->func.body);
+ if (res->type == OBJECT_RETURN) {
+ struct object *ret = res;
+ res = ret->retrn.value;
+ object_ref(res);
+ object_unref(ret);
+ }
+ object_unref(func);
+ environment_destroy(fenv);
+ return res;
+}
+
+struct object *
+eval_expression(struct environment *env, struct expression *expr)
+{
+ struct object *res = NULL;
+ switch (expr->type) {
+ case EXPRESSION_INT:
+ res = object_new(expr->integer.value);
+ return res;
+ case EXPRESSION_BOOL:
+ return expr->boolean.value ? &obj_true : &obj_false;
+ case EXPRESSION_PREFIX:
+ res = eval(env, expr->prefix.right);
+ if (res == OBJECT_ERROR) return res;
+ return eval_prefix_expression(env, expr->token, res);
+ case EXPRESSION_INFIX:;
+ struct object *left = eval(env, expr->infix.left);
+ if (left == OBJECT_ERROR) return res;
+ struct object *right = eval(env, expr->infix.right);
+ if (right == OBJECT_ERROR) {
+ object_unref(left);
+ return right;
+ }
+ return eval_infix_expression(env, expr->token, left, right);
+ case EXPRESSION_IF:
+ return eval_if_expression(env, &expr->cond);
+ case EXPRESSION_IDENT:
+ res = environment_get(env, &expr->ident.value);
+ if (!res) {
+ char ibuf[256];
+ return new_error("not declared: %s",
+ slice_sprint(&expr->ident.value, ibuf));
+ }
+ object_ref(res);
+ return res;
+ case EXPRESSION_FUNC:
+ res = object_new(expr);
+ return res;
+ case EXPRESSION_CALL:
+ return eval_call_expression(env, expr);
+ default:
+ return NULL;
+ }
+}
+
+struct object *
+eval_statement(struct environment *env, struct statement *st)
+{
+ struct object *val;
+ switch (st->type) {
+ case STATEMENT_EXPRESSION:
+ return eval(env, st->expr.expr);
+ case STATEMENT_BLOCK:
+ return eval_statements(env, st->block.statements);
+ case STATEMENT_RETURN:
+ val = eval(env, st->retrn.value);
+ if (val->type == OBJECT_ERROR) return val;
+ struct object *res = object_new(val);
+ return res;
+ case STATEMENT_LET:
+ val = eval(env, st->let.value);
+ if (val->type == OBJECT_ERROR) return val;
+ struct object *old = environment_set(env, st->let.name->value, val);
+ if (old) object_unref(old);
+ object_unref(val);
+ default:
+ return NULL;
+ }
+}
+
+struct object *
+eval_program(struct environment *env, struct program *prog)
+{
+ size_t i;
+ struct object *res = NULL;
+ struct statement *st;
+ vector_foreach(prog->statements, i, st) {
+ if (res) object_unref(res);
+ res = eval(env, st);
+ if (res) {
+ if (res->type == OBJECT_RETURN) {
+ struct object *val = res->retrn.value;
+ object_ref(val);
+ object_unref(res);
+ return val;
+ } else if (res->type == OBJECT_ERROR) {
+ return res;
+ }
+ }
+ }
+ return res;
+}
diff --git a/src/hmap.c b/src/hmap.c
new file mode 100644
index 0000000..c605fad
--- /dev/null
+++ b/src/hmap.c
@@ -0,0 +1,225 @@
+#include "hmap.h"
+#include "slice.h"
+
+#include <inttypes.h>
+#include <string.h>
+#include <stdlib.h>
+#include <err.h>
+
+#if SIZE_MAX == 0xFFFFFFFF
+/* If size_t is 32bit */
+static const size_t fnv_prime = 16777619u;
+static const size_t fnv_offsetb = 2166136261u;
+#elif SIZE_MAX == 0xFFFFFFFFFFFFFFFF
+/* If size_t is 64bit */
+static const size_t fnv_prime = 1099511628211u;
+static const size_t fnv_offsetb = 14695981039346656037u;
+#else
+/* If size_t is 128bit. Maybe this is overdoing it? */
+static const size_t fnv_prime = 309485009821345068724781371u;
+static const size_t fnv_offsetb = 144066263297769815596495629667062367629u;
+#endif
+
+struct hnode {
+ struct slice key;
+ void *value;
+ struct hnode *next;
+};
+
+/* FNV1a */
+static size_t
+hash(const char *str)
+{
+ size_t hash = fnv_offsetb;
+ size_t i = 0;
+ while (str[i] != '\0') {
+ hash ^= str[i];
+ hash *= fnv_prime;
+ i++;
+ }
+
+ return hash;
+}
+
+static size_t
+hash_slice(const struct slice *slice)
+{
+ size_t hash = fnv_offsetb;
+ size_t i = slice->start;
+ while (i < slice->end) {
+ hash ^= slice->str[i];
+ hash *= fnv_prime;
+ i++;
+ }
+
+ return hash;
+}
+
+struct hmap *
+hmap_new_with_cap(size_t cap)
+{
+ struct hmap *hm = malloc(sizeof *hm);
+ hm->cap = cap;
+ hm->size = 0;
+ if (hm == NULL) return NULL;
+ hm->buckets = calloc(cap, sizeof hm->buckets);
+ if (hm->buckets == NULL) {
+ free(hm);
+ return NULL;
+ }
+
+ return hm;
+}
+
+void *
+hmap_sets(struct hmap *hm, struct slice key, void *value)
+{
+ int pos = hash_slice(&key) % hm->cap;
+ struct hnode *head = hm->buckets[pos];
+ struct hnode *node = head;
+ void *old_value = NULL;
+
+ while (node) {
+ if (slice_cmp(&node->key, &key) == 0) {
+ old_value = node->value;
+ node->value = value;
+ return old_value;
+ }
+ node = node->next;
+ }
+
+ node = malloc(sizeof *node);
+ node->key = key;
+ node->value = value;
+ node->next = head;
+ hm->buckets[pos] = node;
+ hm->size++;
+ return old_value;
+}
+
+void *
+hmap_set(struct hmap *hm, const char *k, void *value)
+{
+ struct slice key = slice_fullstr(k);
+ return hmap_sets(hm, key, value);
+}
+
+void *
+hmap_gets(struct hmap *hm, const struct slice *key)
+{
+ size_t pos = hash_slice(key) % hm->cap;
+ struct hnode *node = hm->buckets[pos];
+ while (node != NULL) {
+ if (slice_cmp(&node->key, key) == 0) {
+ return node->value;
+ }
+
+ node = node->next;
+ }
+
+ return NULL;
+}
+
+void *
+hmap_get(struct hmap *hm, const char *k)
+{
+ struct slice key = slice_fullstr(k);
+ return hmap_gets(hm, &key);
+}
+
+void *
+hmap_resolve(struct hmap *hm, const char *key)
+{
+ char tmp_key[64];
+ int i = 0;
+ int j = 0;
+
+ while (1) {
+ for (j=0; key[i] != '.' && key[i] != '\0'; i++, j++) {
+ tmp_key[j] = key[i];
+ }
+ tmp_key[j] = '\0';
+ hm = hmap_get(hm, tmp_key);
+
+ // stop if we read key to end of string
+ if (key[i] == '\0') {
+ break;
+ }
+
+ // otherwise, continue reading keys
+ i++;
+ }
+
+ return hm;
+}
+
+void *
+hmap_removes(struct hmap *hm, const struct slice *key)
+{
+ int pos = hash_slice(key) % hm->cap;
+ struct hnode *node = hm->buckets[pos];
+ struct hnode *prev = NULL;
+ void *old_value;
+
+ while (node) {
+ if (slice_cmp(&node->key, key) == 0) {
+ if (prev) {
+ prev->next = node->next;
+ } else {
+ hm->buckets[pos] = node->next;
+ }
+ old_value = node->value;
+ free(node);
+ hm->size--;
+ return old_value;
+ }
+
+ prev = node;
+ node = node->next;
+ }
+
+ return NULL;
+}
+
+void *
+hmap_remove(struct hmap *hm, const char *k)
+{
+ struct slice key = slice_fullstr(k);
+ return hmap_removes(hm, &key);
+}
+
+#define HMAP_WALK(hm, ...) \
+ struct hnode *node; \
+ struct hnode *next; \
+ for (size_t i = 0; i < hm->cap; i++) { \
+ node = hm->buckets[i]; \
+ while (node) { \
+ next = node->next; \
+ __VA_ARGS__; \
+ node = next; \
+ } \
+ }
+
+void
+hmap_walk(struct hmap *hm, hmap_cb cb)
+{
+ HMAP_WALK(hm, cb(&node->key, node->value));
+}
+
+void
+hmap_destroy(struct hmap *hm, hmap_cb cb)
+{
+ HMAP_WALK(hm, cb(&node->key, node->value), free(node));
+
+ free(hm->buckets);
+ free(hm);
+}
+
+void
+hmap_free(struct hmap *hm)
+{
+ HMAP_WALK(hm, free(node));
+
+ free(hm->buckets);
+ free(hm);
+}
diff --git a/src/lexer.c b/src/lexer.c
new file mode 100644
index 0000000..7ee9cbd
--- /dev/null
+++ b/src/lexer.c
@@ -0,0 +1,187 @@
+#include "lexer.h"
+#include "token.h"
+
+#include <ctype.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+
+static bool
+isidentc(char c)
+{
+ return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '_';
+}
+
+static void
+lexer_eatspace(struct lexer *lexer)
+{
+ while(isspace(lexer->input[lexer->word.start])) {
+ lexer_read_char(lexer);
+ }
+}
+
+static void
+set_token(struct token *token, enum token_type t, const struct slice *s)
+{
+ token->type = t;
+ if (s == NULL) {
+ token->literal.str = "";
+ token->literal.start = 0;
+ token->literal.end = 0;
+ } else {
+ slice_cpy(&token->literal, s);
+ }
+}
+
+static void
+lexer_read_ident(struct lexer *lexer, struct token *token)
+{
+ size_t start = lexer->word.start;
+ token->literal.str = lexer->input;
+ while (isidentc(lexer->input[lexer->word.start])) {
+ lexer_read_char(lexer);
+ }
+ token->literal.start = start;
+ token->literal.end = lexer->word.start;
+}
+
+static void
+lexer_read_num(struct lexer *lexer, struct token *token)
+{
+ size_t start = lexer->word.start;
+ token->literal.str = lexer->input;
+ while (isdigit(lexer->input[lexer->word.start])) {
+ lexer_read_char(lexer);
+ }
+ token->literal.start = start;
+ token->literal.end = lexer->word.start;
+}
+
+static char
+lexer_peek_char(struct lexer *lexer)
+{
+ if (lexer->word.start >= lexer->len) {
+ return 0;
+ }
+ return lexer->input[lexer->word.start + 1];
+}
+
+struct lexer *
+lexer_new()
+{
+ struct lexer *lexer = malloc(sizeof *lexer);
+ token_init_keywords();
+
+ return lexer;
+}
+
+void
+lexer_read_char(struct lexer *lexer)
+{
+ lexer->word.start = lexer->word.end;
+ if (lexer->word.end >= lexer->len) {
+ lexer->word.end = 0;
+ return;
+ }
+ lexer->word.end++;
+}
+
+struct token
+lexer_next_token(struct lexer *lexer)
+{
+ lexer_eatspace(lexer);
+
+ struct token token;
+ char c = lexer->input[lexer->word.start];
+
+ switch (c) {
+ case '=':
+ if (lexer_peek_char(lexer) == '=') {
+ lexer->word.end++;
+ set_token(&token, TOKEN_EQ, &lexer->word);
+ } else {
+ set_token(&token, TOKEN_ASSIGN, &lexer->word);
+ }
+ break;
+ case '+':
+ set_token(&token, TOKEN_PLUS, &lexer->word);
+ break;
+ case '-':
+ set_token(&token, TOKEN_MINUS, &lexer->word);
+ break;
+ case '!':
+ if (lexer_peek_char(lexer) == '=') {
+ lexer->word.end++;
+ set_token(&token, TOKEN_NOTEQ, &lexer->word);
+ } else {
+ set_token(&token, TOKEN_BANG, &lexer->word);
+ }
+ break;
+ case '/':
+ set_token(&token, TOKEN_SLASH, &lexer->word);
+ break;
+ case '*':
+ set_token(&token, TOKEN_ASTERISK, &lexer->word);
+ break;
+ case '<':
+ set_token(&token, TOKEN_LT, &lexer->word);
+ break;
+ case '>':
+ set_token(&token, TOKEN_GT, &lexer->word);
+ break;
+ case ';':
+ set_token(&token, TOKEN_SEMICOLON, &lexer->word);
+ break;
+ case '(':
+ set_token(&token, TOKEN_LPAREN, &lexer->word);
+ break;
+ case ')':
+ set_token(&token, TOKEN_RPAREN, &lexer->word);
+ break;
+ case ',':
+ set_token(&token, TOKEN_COMMA, &lexer->word);
+ break;
+ case '{':
+ set_token(&token, TOKEN_LBRACE, &lexer->word);
+ break;
+ case '}':
+ set_token(&token, TOKEN_RBRACE, &lexer->word);
+ break;
+ case 0:
+ set_token(&token, TOKEN_EOF, NULL);
+ break;
+ default:
+ if (isidentc(c)) {
+ lexer_read_ident(lexer, &token);
+ token.type = token_lookup_ident(&token.literal);
+ return token;
+ } else if (isdigit(c)) {
+ lexer_read_num(lexer, &token);
+ token.type = TOKEN_INT;
+ return token;
+ }
+ set_token(&token, TOKEN_ILLEGAL, &lexer->word);
+ }
+
+ lexer_read_char(lexer);
+
+ return token;
+}
+
+void
+lexer_reset(struct lexer *lexer, const char *input)
+{
+ lexer->input = input;
+ lexer->len = strlen(lexer->input);
+ lexer->word.str = lexer->input;
+ lexer->word.start = 0;
+ lexer->word.end = 0;
+ lexer_read_char(lexer);
+}
+
+void
+lexer_destroy(struct lexer *lexer)
+{
+ free(lexer);
+ token_free_keywords();
+}
diff --git a/src/object.c b/src/object.c
new file mode 100644
index 0000000..d3f589d
--- /dev/null
+++ b/src/object.c
@@ -0,0 +1,195 @@
+#include "object.h"
+#include "ast.h"
+#include "hmap.h"
+#include "vector.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static const char *object_types[] = {
+ "error",
+ "null",
+ "int",
+ "bool",
+ "return",
+};
+
+static void
+environment_destroy_cb(const void *key, void *val)
+{
+ struct object *obj = val;
+ object_unref(obj);
+}
+
+static inline char *
+bool_sprint(bool val, char *str)
+{
+ sprintf(str, val ? "true" : "false");
+ return str;
+}
+
+extern inline const char *
+object_type_print(enum object_type type)
+{
+ return object_types[type];
+}
+
+static inline char *
+object_func_sprint(struct object *obj, char *str)
+{
+ char *cur = str;
+ sprintf(cur, "fn(");
+ cur += strlen(cur);
+ size_t i;
+ struct expression *ident;
+ vector_foreach(obj->func.params, i, ident) {
+ node_sprint(ident, cur);
+ cur += strlen(cur);
+ if (i < (obj->func.params->len - 1)) {
+ cur[0] = ',', cur[1] = ' ', cur += 2;
+ }
+ }
+ sprintf(cur, ") {\n");
+ cur += strlen(cur);
+ node_sprint(obj->func.body, cur);
+ cur += strlen(cur);
+ sprintf(cur, "\n}");
+
+ return str;
+}
+
+char *
+object_sprint(struct object *obj, char *str)
+{
+ switch (obj->type) {
+ case OBJECT_NULL:
+ sprintf(str, "null");
+ break;
+ case OBJECT_BOOL:
+ return bool_sprint(obj->boolean, str);
+ case OBJECT_INT:
+ sprintf(str, "%ld", obj->integer);
+ break;
+ case OBJECT_RETURN:
+ object_sprint(obj->retrn.value, str);
+ case OBJECT_ERROR:
+ strcpy(str, obj->error.msg);
+ case OBJECT_FUNC:
+ return object_func_sprint(obj, str);
+ }
+ return str;
+}
+
+struct object *
+object_new_int(int64_t val)
+{
+ struct object *obj = malloc(sizeof(*obj));
+ obj->type = OBJECT_INT;
+ obj->refcount = 1;
+ obj->integer = val;
+ return obj;
+}
+
+struct object *
+object_new_error(char *msg)
+{
+ struct object *obj = malloc(sizeof(*obj));
+ obj->type = OBJECT_ERROR;
+ obj->refcount = 1;
+ obj->error.msg = msg;
+ return obj;
+}
+
+struct object *
+object_new_return(struct object *val)
+{
+ struct object *obj = malloc(sizeof(*obj));
+ obj->type = OBJECT_RETURN;
+ obj->refcount = 1;
+ obj->retrn.value = val;
+ return obj;
+}
+
+struct object *
+object_new_func(struct expression *expr)
+{
+ struct object *obj = malloc(sizeof(*obj));
+ obj->type = OBJECT_FUNC;
+ obj->refcount = 1;
+ obj->func.body = node_dup(expr->func.body);
+ obj->func.params = expression_vector_dup(expr->func.parameters);
+ return obj;
+}
+
+void
+object_ref(struct object *obj)
+{
+ obj->refcount++;
+}
+
+void
+object_unref(struct object *obj)
+{
+ if (obj->type == OBJECT_NULL || obj->type == OBJECT_BOOL) return;
+ if (--obj->refcount < 1) {
+ switch (obj->type) {
+ case OBJECT_RETURN:
+ object_unref(obj->retrn.value);
+ break;
+ case OBJECT_ERROR:
+ free(obj->error.msg);
+ break;
+ case OBJECT_FUNC:
+ node_destroy(obj->func.body);
+ size_t i;
+ struct expression *param;
+ vector_foreach(obj->func.params, i, param) {
+ node_destroy(param);
+ }
+ vector_free(obj->func.params);
+ break;
+ default:
+ break;
+ }
+ free(obj);
+ }
+}
+
+struct environment *
+environment_new_enclosed(struct environment *outer)
+{
+ struct environment *env = malloc(sizeof(*env));
+ env->store = hmap_new();
+ if (!env->store) {
+ free(env);
+ return NULL;
+ }
+ env->outer = outer;
+
+ return env;
+}
+
+struct object *
+environment_set(struct environment *env, struct slice key, struct object *val)
+{
+ object_ref(val);
+ return hmap_sets(env->store, key, val);
+}
+
+struct object *
+environment_get(struct environment *env, const struct slice *key)
+{
+ struct object *obj = hmap_gets(env->store, key);
+ if (!obj && env->outer) {
+ obj = environment_get(env->outer, key);
+ }
+ return obj;
+}
+
+void
+environment_destroy(struct environment *env)
+{
+ hmap_destroy(env->store, environment_destroy_cb);
+ free(env);
+}
diff --git a/src/parser.c b/src/parser.c
new file mode 100644
index 0000000..e8c44df
--- /dev/null
+++ b/src/parser.c
@@ -0,0 +1,605 @@
+#include "parser.h"
+#include "ast.h"
+#include "token.h"
+#include "vector.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+enum precedence {
+ PRE_LOWEST = 1,
+ PRE_EQUALS,
+ PRE_LG,
+ PRE_SUM,
+ PRE_PROD,
+ PRE_PREFIX,
+ PRE_CALL,
+};
+
+static enum precedence precedences[] = {
+ 0,
+ PRE_LOWEST,
+ PRE_EQUALS,
+ PRE_LG,
+ PRE_SUM,
+ PRE_PROD,
+ PRE_PREFIX,
+ PRE_CALL,
+};
+
+static inline void
+parser_register_prefix(struct parser *parser, enum token_type t,
+ prefix_parse_f fn)
+{
+ hmap_set(parser->prefix_fns, token_type_print(t), fn);
+}
+
+static inline void
+parser_register_infix(struct parser *parser, enum token_type t,
+ infix_parse_f fn)
+{
+ hmap_set(parser->infix_fns, token_type_print(t), fn);
+}
+
+static inline void
+parser_register_precedence(struct parser *parser, enum token_type t,
+ enum precedence pre)
+{
+ hmap_set(parser->precedences, token_type_print(t), &precedences[pre]);
+}
+
+static inline prefix_parse_f
+parser_get_prefix(struct parser *parser, enum token_type t)
+{
+ return hmap_get(parser->prefix_fns, token_type_print(t));
+}
+
+static inline infix_parse_f
+parser_get_infix(struct parser *parser, enum token_type t)
+{
+ return hmap_get(parser->infix_fns, token_type_print(t));
+}
+
+static inline enum precedence
+parser_get_precedence(struct parser *parser, enum token_type t)
+{
+ enum precedence *pre = hmap_get(parser->precedences, token_type_print(t));
+ if (!pre) return PRE_LOWEST;
+ return *pre;
+}
+
+static inline bool
+parser_cur_token_is(struct parser *parser, enum token_type t)
+{
+ return parser->cur_token.type == t;
+}
+
+static inline bool
+parser_peek_token_is(struct parser *parser, enum token_type t)
+{
+ return parser->peek_token.type == t;
+}
+
+static inline enum precedence
+parser_peek_precedence(struct parser *parser)
+{
+ return parser_get_precedence(parser, parser->peek_token.type);
+}
+
+static inline enum precedence
+parser_cur_precedence(struct parser *parser)
+{
+ return parser_get_precedence(parser, parser->cur_token.type);
+}
+
+static inline void
+parser_peek_error(struct parser *parser, enum token_type t)
+{
+ char *msg = malloc(sizeof(*msg) * 1024);
+ if (msg) {
+ sprintf(msg, "expected token %s, got %s", token_type_print(t),
+ token_type_print(parser->peek_token.type));
+ vector_push(parser->errors, msg);
+ }
+}
+
+static inline bool
+parser_expect_peek(struct parser *parser, enum token_type t)
+{
+ if (parser_peek_token_is(parser, t)) {
+ parser_next_token(parser);
+ return true;
+ }
+ parser_peek_error(parser, t);
+ return false;
+}
+
+static inline void
+parser_no_prefix_fn_error(struct parser *parser, enum token_type t)
+{
+ char *msg = malloc(256);
+ sprintf(msg, "%s not recognized as prefix", token_type_print(t));
+ vector_push(parser->errors, msg);
+}
+
+static struct expression *
+parser_parse_expression(struct parser *parser, enum precedence pre)
+{
+ prefix_parse_f prefix = parser_get_prefix(parser, parser->cur_token.type);
+ if (!prefix) {
+ parser_no_prefix_fn_error(parser, parser->cur_token.type);
+ return NULL;
+ }
+ struct expression *lexpr = prefix(parser);
+
+ while (pre < parser_peek_precedence(parser)
+ && !parser_peek_token_is(parser, TOKEN_SEMICOLON)) {
+ infix_parse_f infix = parser_get_infix(parser, parser->peek_token.type);
+ if (!infix) {
+ return lexpr;
+ }
+
+ parser_next_token(parser);
+ lexpr = infix(parser, lexpr);
+ }
+
+ return lexpr;
+}
+
+static struct expression *
+parser_parse_identifier(struct parser *parser)
+{
+ struct expression *expr = malloc(sizeof(*expr));
+ expr->type = EXPRESSION_IDENT;
+ expr->token = parser->cur_token;
+ expr->ident.value = parser->cur_token.literal;
+
+ return expr;
+}
+
+static struct expression *
+parser_parse_integer(struct parser *parser)
+{
+ struct expression *expr = malloc(sizeof(*expr));
+ expr->type = EXPRESSION_INT;
+ expr->token = parser->cur_token;
+
+ char *end;
+ expr->integer.value = strtol(expr->token.literal.str
+ + expr->token.literal.start,
+ &end, 0);
+ if (*end != '\0' && (expr->token.literal.str + expr->token.literal.end) < end) {
+ char *msg = malloc(256);
+ char litbuf[32];
+ sprintf(msg, "%s is not a valid integer",
+ slice_sprint(&expr->token.literal, litbuf));
+ vector_push(parser->errors, msg);
+ free(expr);
+ return NULL;
+ }
+
+ return expr;
+}
+
+static struct expression *
+parser_parse_boolean(struct parser *parser)
+{
+ struct expression *expr = malloc(sizeof(*expr));
+ expr->type = EXPRESSION_BOOL;
+ expr->token = parser->cur_token;
+ expr->boolean.value = expr->token.type == TOKEN_TRUE;
+
+ return expr;
+}
+
+static struct expression *
+parser_parse_grouped(struct parser *parser)
+{
+ parser_next_token(parser);
+ struct expression *expr = parser_parse_expression(parser, PRE_LOWEST);
+ if (!parser_expect_peek(parser, TOKEN_RPAREN)) {
+ return NULL;
+ }
+
+ return expr;
+}
+
+static struct expression *
+parser_parse_prefix(struct parser *parser)
+{
+ struct expression *expr = malloc(sizeof(*expr));
+ expr->type = EXPRESSION_PREFIX;
+ expr->token = parser->cur_token;
+ expr->prefix.operator = parser->cur_token.literal;
+
+ parser_next_token(parser);
+ expr->prefix.right = parser_parse_expression(parser, PRE_PREFIX);
+
+ return expr;
+}
+
+static struct expression *
+parser_parse_infix(struct parser *parser, struct expression *lexpr)
+{
+ struct expression *expr = malloc(sizeof(*expr));
+ expr->type = EXPRESSION_INFIX;
+ expr->token = parser->cur_token;
+ expr->infix.operator = parser->cur_token.literal;
+ expr->infix.left = lexpr;
+
+ enum precedence pre = parser_cur_precedence(parser);
+ parser_next_token(parser);
+ expr->infix.right = parser_parse_expression(parser, pre);
+
+ return expr;
+}
+
+static struct statement *
+parser_parse_let_statement(struct parser *parser)
+{
+ struct statement *st = calloc(1, sizeof(*st));
+ if (!st) return NULL;
+ st->type = STATEMENT_LET;
+ st->token = parser->cur_token;
+
+ if (!parser_expect_peek(parser, TOKEN_IDENT)) goto fail;
+
+ st->let.name = malloc(sizeof(*st->let.name));
+ if (!st->let.name) goto fail;
+ st->let.name->token = parser->cur_token;
+ st->let.name->value = parser->cur_token.literal;
+
+ if (!parser_expect_peek(parser, TOKEN_ASSIGN)) goto ass_fail;
+
+ parser_next_token(parser);
+
+ st->let.value = parser_parse_expression(parser, PRE_LOWEST);
+ if (parser_peek_token_is(parser, TOKEN_SEMICOLON)) {
+ parser_next_token(parser);
+ }
+
+ return st;
+ass_fail:
+ free(st->let.name);
+fail:
+ free(st);
+ return NULL;
+}
+
+static struct statement *
+parser_parse_return_statement(struct parser *parser)
+{
+ struct statement *st = calloc(1, sizeof(*st));
+ if (!st) return NULL;
+ st->type = STATEMENT_RETURN;
+ st->token = parser->cur_token;
+
+ parser_next_token(parser);
+
+ st->retrn.value = parser_parse_expression(parser, PRE_LOWEST);
+ if (parser_peek_token_is(parser, TOKEN_SEMICOLON)) {
+ parser_next_token(parser);
+ }
+
+ return st;
+}
+
+static struct statement *
+parser_parse_expression_statement(struct parser *parser)
+{
+ struct statement *st = calloc(1, sizeof(*st));
+ if (!st) return NULL;
+ st->type = STATEMENT_EXPRESSION;
+ st->token = parser->cur_token;
+ st->expr.expr = parser_parse_expression(parser, PRE_LOWEST);
+
+ if (parser_peek_token_is(parser, TOKEN_SEMICOLON)) {
+ parser_next_token(parser);
+ }
+
+ return st;
+}
+
+static struct statement *parser_parse_statement(struct parser *);
+
+static struct statement *
+parser_parse_block_statement(struct parser *parser)
+{
+ struct statement *st = calloc(1, sizeof(*st));
+ if (!st) return NULL;
+ st->type = STATEMENT_BLOCK;
+ st->block.statements = vector_new();
+ parser_next_token(parser);
+
+ while (!parser_cur_token_is(parser, TOKEN_RBRACE)
+ && !parser_cur_token_is(parser, TOKEN_EOF)) {
+ struct statement *subst = parser_parse_statement(parser);
+ if (subst) {
+ vector_push(st->block.statements, subst);
+ }
+ parser_next_token(parser);
+ }
+
+ return st;
+}
+
+static struct expression *
+parser_parse_if(struct parser *parser)
+{
+ struct expression *expr = calloc(1, sizeof(*expr));
+ expr->type = EXPRESSION_IF;
+ expr->token = parser->cur_token;
+
+ if (!parser_expect_peek(parser, TOKEN_LPAREN)) {
+ goto fail;
+ }
+
+ parser_next_token(parser);
+ expr->cond.condition = parser_parse_expression(parser, PRE_LOWEST);
+
+ if (!parser_expect_peek(parser, TOKEN_RPAREN)) {
+ goto fail;
+ }
+ if (!parser_expect_peek(parser, TOKEN_LBRACE)) {
+ goto fail;
+ }
+
+ expr->cond.consequence = parser_parse_block_statement(parser);
+
+ if (parser_peek_token_is(parser, TOKEN_ELSE)) {
+ parser_next_token(parser);
+ if (!parser_expect_peek(parser, TOKEN_LBRACE)) {
+ goto fail;
+ }
+ expr->cond.alternative = parser_parse_block_statement(parser);
+ }
+
+ return expr;
+fail:
+ free(expr);
+ return NULL;
+}
+
+static struct vector *
+parser_parse_func_params(struct parser *parser)
+{
+ struct vector *idents = vector_new_with_cap(8);
+
+ if (parser_peek_token_is(parser, TOKEN_RPAREN)) {
+ parser_next_token(parser);
+ return idents;
+ }
+
+ parser_next_token(parser);
+
+ struct expression *ident = calloc(1, sizeof(*ident));
+ ident->token = parser->cur_token;
+ ident->ident.value = parser->cur_token.literal;
+ vector_push(idents, ident);
+ while (parser_peek_token_is(parser, TOKEN_COMMA)) {
+ parser_next_token(parser);
+ parser_next_token(parser);
+ ident = calloc(1, sizeof(*ident));
+ ident->token = parser->cur_token;
+ ident->ident.value = parser->cur_token.literal;
+ vector_push(idents, ident);
+ }
+
+ if (!parser_expect_peek(parser, TOKEN_RPAREN)) {
+ size_t i;
+ vector_foreach(idents, i, ident) {
+ expression_destroy(ident);
+ }
+ vector_free(idents);
+ return NULL;
+ }
+
+ return idents;
+}
+
+static struct expression *
+parser_parse_func_literal(struct parser *parser)
+{
+ struct expression *expr = calloc(1, sizeof(*expr));
+ expr->type = EXPRESSION_FUNC;
+ expr->token = parser->cur_token;
+
+ if (!parser_expect_peek(parser, TOKEN_LPAREN)) {
+ goto fail;
+ }
+ expr->func.parameters = parser_parse_func_params(parser);
+ if (!parser_expect_peek(parser, TOKEN_LBRACE)) {
+ goto fail;
+ }
+
+ expr->func.body = parser_parse_block_statement(parser);
+
+ return expr;
+fail:
+ free(expr);
+ return NULL;
+}
+
+static struct vector *
+parser_parse_call_arguments(struct parser *parser)
+{
+ struct vector *args = vector_new_with_cap(8);
+
+ if (parser_peek_token_is(parser, TOKEN_RPAREN)) {
+ parser_next_token(parser);
+ return args;
+ }
+
+ parser_next_token(parser);
+ vector_push(args, parser_parse_expression(parser, PRE_LOWEST));
+
+ while (parser_peek_token_is(parser, TOKEN_COMMA)) {
+ parser_next_token(parser);
+ parser_next_token(parser);
+ vector_push(args, parser_parse_expression(parser, PRE_LOWEST));
+ }
+
+ if (!parser_expect_peek(parser, TOKEN_RPAREN)) {
+ size_t i;
+ struct expression *expr;
+ vector_foreach(args, i, expr) {
+ expression_destroy(expr);
+ }
+ vector_free(args);
+ return NULL;
+ }
+
+ return args;
+}
+
+static struct expression *
+parser_parse_call_expression(struct parser *parser, struct expression *func)
+{
+ struct expression *expr = calloc(1, sizeof(*expr));
+ expr->token = parser->cur_token;
+ expr->type = EXPRESSION_CALL;
+ expr->call.func = func;
+ expr->call.arguments = parser_parse_call_arguments(parser);
+
+ return expr;
+}
+
+static struct statement *
+parser_parse_statement(struct parser *parser)
+{
+ switch (parser->cur_token.type) {
+ case TOKEN_LET:
+ return parser_parse_let_statement(parser);
+ case TOKEN_RETURN:
+ return parser_parse_return_statement(parser);
+ case TOKEN_LBRACE:
+ return parser_parse_block_statement(parser);
+ default:
+ return parser_parse_expression_statement(parser);
+ }
+}
+
+struct parser *
+parser_new()
+{
+ struct parser *parser = malloc(sizeof *parser);
+ if (!parser) return NULL;
+
+ struct lexer *lex = lexer_new();
+ if (!lex) goto fail;
+ parser->lexer = lex;
+
+ parser->errors = vector_new();
+ if (!parser->errors) goto fail2;
+
+ parser->prefix_fns = hmap_new();
+ if (!parser->prefix_fns) goto fail3;
+ parser_register_prefix(parser, TOKEN_IDENT, parser_parse_identifier);
+ parser_register_prefix(parser, TOKEN_INT, parser_parse_integer);
+ parser_register_prefix(parser, TOKEN_BANG, parser_parse_prefix);
+ parser_register_prefix(parser, TOKEN_MINUS, parser_parse_prefix);
+ parser_register_prefix(parser, TOKEN_TRUE, parser_parse_boolean);
+ parser_register_prefix(parser, TOKEN_FALSE, parser_parse_boolean);
+ parser_register_prefix(parser, TOKEN_LPAREN, parser_parse_grouped);
+ parser_register_prefix(parser, TOKEN_RPAREN, parser_parse_grouped);
+ parser_register_prefix(parser, TOKEN_IF, parser_parse_if);
+ parser_register_prefix(parser, TOKEN_FUNC, parser_parse_func_literal);
+
+ parser->infix_fns = hmap_new();
+ if (!parser->infix_fns) goto fail4;
+ parser_register_infix(parser, TOKEN_PLUS, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_MINUS, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_SLASH, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_ASTERISK, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_EQ, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_NOTEQ, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_LT, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_GT, parser_parse_infix);
+ parser_register_infix(parser, TOKEN_LPAREN, parser_parse_call_expression);
+
+ parser->precedences = hmap_new();
+ if (!parser->precedences) goto fail5;
+ parser_register_precedence(parser, TOKEN_EQ, PRE_EQUALS);
+ parser_register_precedence(parser, TOKEN_NOTEQ, PRE_EQUALS);
+ parser_register_precedence(parser, TOKEN_LT, PRE_LG);
+ parser_register_precedence(parser, TOKEN_GT, PRE_LG);
+ parser_register_precedence(parser, TOKEN_PLUS, PRE_SUM);
+ parser_register_precedence(parser, TOKEN_MINUS, PRE_SUM);
+ parser_register_precedence(parser, TOKEN_ASTERISK, PRE_PROD);
+ parser_register_precedence(parser, TOKEN_SLASH, PRE_PROD);
+ parser_register_precedence(parser, TOKEN_LPAREN, PRE_CALL);
+
+ return parser;
+fail5:
+ hmap_free(parser->infix_fns);
+fail4:
+ hmap_free(parser->prefix_fns);
+fail3:
+ vector_free(parser->errors);
+fail2:
+ lexer_destroy(lex);
+fail:
+ free(parser);
+ return NULL;
+}
+
+void
+parser_reset(struct parser *parser, const char *input)
+{
+ size_t i;
+ char *val;
+ vector_foreach (parser->errors, i, val) {
+ free(val);
+ }
+ parser->errors->len = 0;
+
+ lexer_reset(parser->lexer, input);
+
+ parser_next_token(parser);
+ parser_next_token(parser);
+}
+
+void
+parser_next_token(struct parser *parser)
+{
+ parser->cur_token = parser->peek_token;
+ parser->peek_token = lexer_next_token(parser->lexer);
+}
+
+struct program *
+parser_parse_program(struct parser *parser)
+{
+ struct program *program = malloc(sizeof *program);
+ if (!program) return NULL;
+ program->statements = vector_new();
+ if (!program->statements) {
+ free(program);
+ return NULL;
+ }
+
+ while (!parser_cur_token_is(parser, TOKEN_EOF)) {
+ struct statement *st = parser_parse_statement(parser);
+ if (st != NULL) {
+ vector_push(program->statements, st);
+ }
+ parser_next_token(parser);
+ }
+
+ return program;
+}
+
+void
+parser_destroy(struct parser *parser)
+{
+ size_t i;
+ char *val;
+ vector_foreach (parser->errors, i, val) {
+ free(val);
+ }
+ vector_free(parser->errors);
+ hmap_free(parser->infix_fns);
+ hmap_free(parser->prefix_fns);
+ hmap_free(parser->precedences);
+ lexer_destroy(parser->lexer);
+ free(parser);
+}
diff --git a/src/repl.c b/src/repl.c
new file mode 100644
index 0000000..236d9ec
--- /dev/null
+++ b/src/repl.c
@@ -0,0 +1,67 @@
+#include "repl.h"
+
+#include "ast.h"
+#include "object.h"
+#include "token.h"
+#include "vector.h"
+#include "parser.h"
+#include "eval.h"
+
+#define PROMPT ">> "
+
+static void
+print_parser_errors(FILE *out, struct vector *errors)
+{
+ size_t i;
+ char *msg;
+ vector_foreach(errors, i, msg) {
+ fprintf(out, "\t%s\n", msg);
+ }
+}
+
+void
+repl_start(FILE *in, FILE *out)
+{
+ char obuf[2048];
+ struct parser *parser = parser_new();
+ struct environment *env = environment_new();
+ struct vector *history = vector_new();
+ for (;;) {
+ fprintf(out, PROMPT);
+ char *input = malloc(1024);
+ if (!fgets(input, 1024, in)) {
+ if (ferror(in)) {
+ perror("REPL: can't read");
+ free(input);
+ goto end;
+ }
+ fprintf(out, "EOF\n");
+ free(input);
+ goto end;
+ }
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ if (parser->errors->len > 0) {
+ print_parser_errors(out, parser->errors);
+ goto skip;
+ }
+ struct object *res = eval(env, prog);
+ if (res) {
+ fprintf(out, "%s\n", object_sprint(res, obuf));
+ object_unref(res);
+ }
+ vector_push(history, input);
+skip:
+ node_destroy(prog);
+ }
+
+end:;
+ size_t i;
+ char *input;
+ vector_foreach(history, i, input) {
+ free(input);
+ }
+ vector_free(history);
+ environment_destroy(env);
+ parser_destroy(parser);
+}
diff --git a/src/slice.c b/src/slice.c
new file mode 100644
index 0000000..eb88f93
--- /dev/null
+++ b/src/slice.c
@@ -0,0 +1,77 @@
+#include "slice.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+struct slice
+slice_new(const char *str, size_t start, size_t end)
+{
+ struct slice slice = {
+ .str = str,
+ .start = start,
+ .end = end,
+ };
+
+ return slice;
+}
+
+struct slice
+slice_fullstr(const char *str)
+{
+ struct slice slice = {
+ .str = str,
+ .start = 0,
+ .end = strlen(str),
+ };
+
+ return slice;
+}
+
+void
+slice_set(struct slice *slice, const char *str, size_t start, size_t end)
+{
+ slice->str = str;
+ slice->start = start;
+ slice->end = end;
+}
+
+size_t
+slice_len(const struct slice *slice)
+{
+ return slice->end - slice->start;
+}
+
+int
+slice_cmp(const struct slice *restrict a, const struct slice *restrict b)
+{
+ size_t lena = slice_len(a), lenb = slice_len(b);
+ int lencmp = (lena > lenb) - (lena < lenb);
+ if (lencmp) {
+ return lencmp;
+ }
+
+ for (size_t i = 0; i < lena; i++) {
+ char ca = a->str[a->start + i], cb = b->str[b->start + i];
+ int cmp = (ca > cb) - (ca < cb);
+ if (cmp) return cmp;
+ }
+
+ return 0;
+}
+
+void
+slice_cpy(struct slice *dst, const struct slice *src)
+{
+ dst->str = src->str;
+ dst->start = src->start;
+ dst->end = src->end;
+}
+
+char *
+slice_sprint(struct slice *slice, char *str)
+{
+ size_t len = slice->end - slice->start;
+ strncpy(str, slice->str + slice->start, len);
+ str[len] = '\0';
+ return str;
+}
diff --git a/src/tests/ast.c b/src/tests/ast.c
new file mode 100644
index 0000000..eb20e03
--- /dev/null
+++ b/src/tests/ast.c
@@ -0,0 +1,42 @@
+#include "tests/tests.h"
+#include "ast.h"
+
+#include <string.h>
+
+#include "parser.h"
+
+static void
+check_parser_errors(struct parser *parser)
+{
+ if (parser->errors->len > 0) {
+ printf("\n");
+ size_t i;
+ char *val;
+ vector_foreach (parser->errors, i, val) {
+ printf("parser error %lu: %s\n", i, val);
+ }
+ FAIL_TEST("parser encountered errors\n");
+ }
+}
+
+static void
+test_string(void)
+{
+ char *input = "let var = anotherVar;";
+ struct parser *parser = parser_new(input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ char progbuf[1024];
+ node_sprint(prog, progbuf);
+ asserteq(strcmp(input, progbuf), 0);
+ node_destroy(prog);
+ parser_destroy(parser);
+}
+
+int
+main(void)
+{
+ INIT_TESTS();
+ RUN_TEST(test_string);
+}
diff --git a/src/tests/eval.c b/src/tests/eval.c
new file mode 100644
index 0000000..b341181
--- /dev/null
+++ b/src/tests/eval.c
@@ -0,0 +1,332 @@
+#include "eval.h"
+#include "tests/tests.h"
+
+#include "parser.h"
+#include "object.h"
+
+#include <string.h>
+
+struct parser *parser;
+
+static struct object *
+test_eval(const char *input)
+{
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ struct environment *env = environment_new();
+ struct object *obj = eval(env, prog);
+ environment_destroy(env);
+ node_destroy(prog);
+
+ return obj;
+}
+
+static void
+test_eval_integer_expressions(void)
+{
+ struct {
+ char *input;
+ int64_t expect;
+ } tests[] = {
+ { "5", 5 },
+ { "69", 69 },
+ { "-5", -5 },
+ { "-69", -69 },
+ { "5 + 5 + 5 + 5 - 10", 10 },
+ { "2 * 2 * 2 * 2 * 2", 32 },
+ { "-50 + 100 + -50", 0 },
+ { "5 * 2 + 10", 20 },
+ { "5 + 2 * 10", 25 },
+ { "20 + 2 * -10", 0 },
+ { "50 / 2 * 2 + 10", 60 },
+ { "2 * (5 + 10)", 30 },
+ { "3 * 3 * 3 + 10", 37 },
+ { "3 * (3 * 3) + 10", 37 },
+ { "(5 + 10 * 2 + 15 / 3) * 2 + -10", 50 },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_INT);
+ asserteq(tests[i].expect, res->integer);
+ object_unref(res);
+ }
+}
+
+static void
+test_eval_boolean_expressions(void)
+{
+ struct {
+ char *input;
+ bool expect;
+ } tests[] = {
+ { "true", true },
+ { "false", false },
+ { "1 < 2", true },
+ { "1 > 2", false },
+ { "1 < 1", false },
+ { "1 > 1", false },
+ { "1 == 1", true },
+ { "1 != 1", false },
+ { "1 == 2", false },
+ { "1 != 2", true },
+ { "true == true", true },
+ { "false == false", true },
+ { "true == false", false },
+ { "true != false", true },
+ { "false != true", true },
+ { "(1 < 2) == true", true },
+ { "(1 < 2) == false", false },
+ { "(1 > 2) == true", false },
+ { "(1 > 2) == false", true },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_BOOL);
+ asserteq(tests[i].expect, res->boolean);
+ }
+}
+
+static void
+test_eval_bang_operators(void)
+{
+ struct {
+ char *input;
+ bool expect;
+ } tests[] = {
+ { "!true", false },
+ { "!false", true },
+ { "!5", false },
+ { "!!true", true },
+ { "!!false", false },
+ { "!!5", true },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_BOOL);
+ asserteq(tests[i].expect, res->boolean);
+ object_unref(res);
+ }
+}
+
+#define OBJ_INT(v) (struct object) { OBJECT_INT, .integer = v }
+#define OBJ_BOOL(v) (struct object) { OBJECT_BOOL, .boolean = v }
+#define OBJ_NULL() (struct object) { OBJECT_NULL, 0, }
+
+#define OBJ(v) _Generic((v), \
+ int64_t: OBJ_INT(v), \
+ int: OBJ_INT(v), \
+ bool: OBJ_BOOL(v) \
+ )
+
+static void
+test_eval_ifelse_expressions(void)
+{
+ struct {
+ char *input;
+ struct object expect;
+ } tests[] = {
+ { "if (true) { 10 }", OBJ(10) },
+ { "if (false) { 10 }", OBJ_NULL() },
+ { "if (1) { 10 }", OBJ(10) },
+ { "if (1 < 2) { 10 }", OBJ(10) },
+ { "if (1 > 2) { 10 }", OBJ_NULL() },
+ { "if (1 > 2) { 10 } else { 20 }", OBJ(20) },
+ { "if (1 < 2) { 10 } else { 20 }", OBJ(10) },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ asserteq(tests[i].expect.type, res->type);
+ asserteq(tests[i].expect.integer, res->integer);
+ object_unref(res);
+ }
+}
+
+static void
+test_eval_return_statements(void)
+{
+ struct {
+ char *input;
+ int64_t expect;
+ } tests[] = {
+ { "return 10;", 10 },
+ { "return 10; 9;", 10 },
+ { "return 2 * 5; 9;", 10 },
+ { "9; return 2 * 5; 9;", 10 },
+ {
+ "if (10 > 1) {\n"
+ "\tif(10 > 1) {\n"
+ "\t\treturn 10;\n"
+ "\t\n}"
+ "return 1;\n"
+ "}",
+ 10,
+ },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_INT);
+ asserteq(tests[i].expect, res->integer);
+ object_unref(res);
+ }
+}
+
+static void
+test_errors(void)
+{
+ struct {
+ char *input;
+ char *expect;
+ } tests[] = {
+ {
+ "5 + true;",
+ "type mismatch: int + bool",
+ },
+ {
+ "5 + true; 5;",
+ "type mismatch: int + bool",
+ },
+ {
+ "-true",
+ "unknown operator: -bool",
+ },
+ {
+ "true + false;",
+ "unknown operator: bool + bool",
+ },
+ {
+ "5; true + false; 5;",
+ "unknown operator: bool + bool",
+ },
+ {
+ "if (10 > 1) { true + false; }",
+ "unknown operator: bool + bool",
+ },
+ {
+ "if (10 > 1) {\n"
+ "\tif(10 > 1) {\n"
+ "\t\treturn true + false;\n"
+ "\t\n}"
+ "return 1;\n"
+ "}",
+ "unknown operator: bool + bool",
+ },
+ {
+ "foobar;",
+ "not declared: foobar",
+ },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_ERROR);
+ asserteq(strcmp(tests[i].expect, res->error.msg), 0);
+ object_unref(res);
+ }
+}
+
+static void
+test_eval_let_statements(void)
+{
+ struct {
+ char *input;
+ int64_t expect;
+ } tests[] = {
+ { "let a = 5; a;", 5 },
+ { "let a = 5 * 5; a;", 25 },
+ { "let a = 5; let b = a; b;", 5 },
+ { "let a = 5; let b = a; let c = a + b + 5; c;", 15 },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_INT);
+ asserteq(tests[i].expect, res->integer);
+ object_unref(res);
+ }
+}
+
+static void
+test_eval_funcs(void)
+{
+ char *input = "fn(x) { x + 2; };";
+ char *expect = "fn(x) {\n(x + 2)\n}";
+ struct object *res = test_eval(input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_FUNC);
+ char fbuf[128];
+ object_sprint(res, fbuf);
+ asserteq(strcmp(fbuf, expect), 0);
+ object_unref(res);
+}
+
+static void
+test_call_funcs(void)
+{
+ struct {
+ char *input;
+ int64_t expect;
+ } tests[] = {
+ { "let identity = fn(x) { x; }; identity(5);", 5 },
+ { "let identity = fn(x) { return x; }; identity(5);", 5 },
+ { "let double = fn(x) { x * 2; }; double(5);", 10 },
+ { "let add = fn(x, y) { x + y; }; add(5, 5);", 10 },
+ { "let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", 20 },
+ { "fn(x) { x; }(5)", 5 },
+ { 0 },
+ };
+
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ struct object *res = test_eval(tests[i].input);
+ assertneq(res, NULL);
+ asserteq(res->type, OBJECT_INT);
+ asserteq(tests[i].expect, res->integer);
+ object_unref(res);
+ }
+}
+
+static void
+init(void)
+{
+ parser = parser_new();
+}
+
+static void
+cleanup(void)
+{
+ parser_destroy(parser);
+}
+
+int
+main(void)
+{
+ init();
+ INIT_TESTS();
+ RUN_TEST(test_eval_integer_expressions);
+ RUN_TEST(test_eval_boolean_expressions);
+ RUN_TEST(test_eval_bang_operators);
+ RUN_TEST(test_eval_ifelse_expressions);
+ RUN_TEST(test_eval_return_statements);
+ RUN_TEST(test_errors);
+ RUN_TEST(test_eval_let_statements);
+ RUN_TEST(test_eval_funcs);
+ RUN_TEST(test_call_funcs);
+ cleanup();
+}
diff --git a/src/tests/lexer.c b/src/tests/lexer.c
new file mode 100644
index 0000000..3700ae6
--- /dev/null
+++ b/src/tests/lexer.c
@@ -0,0 +1,126 @@
+#include "tests/tests.h"
+#include "lexer.h"
+
+#include <string.h>
+
+#include "slice.h"
+#include "token.h"
+
+static void
+test_next_token(void)
+{
+ char *input = "let five = 5;\n"
+ "let ten = 10;\n"
+ "\n"
+ "let add = fn(x, y) {\n"
+ "\tx + y;\n"
+ "};\n"
+ "\n"
+ "let result = add(five, ten);"
+ "!-/*5;\n"
+ "5 < 10 > 5;\n"
+ "\n"
+ "if (5 < 10) {\n"
+ "\treturn true;\n"
+ "} else {\n"
+ "\treturn false;\n"
+ "}\n"
+ "\n"
+ "10 == 10;\n"
+ "10 != 9;\n";
+
+ struct lexer *lexer = lexer_new(input);
+ struct token expected[] = {
+ { TOKEN_LET, slice_fullstr("let") },
+ { TOKEN_IDENT, slice_fullstr("five") },
+ { TOKEN_ASSIGN, slice_fullstr("=") },
+ { TOKEN_INT, slice_fullstr("5") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_LET, slice_fullstr("let") },
+ { TOKEN_IDENT, slice_fullstr("ten") },
+ { TOKEN_ASSIGN, slice_fullstr("=") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_LET, slice_fullstr("let") },
+ { TOKEN_IDENT, slice_fullstr("add") },
+ { TOKEN_ASSIGN, slice_fullstr("=") },
+ { TOKEN_FUNC, slice_fullstr("fn") },
+ { TOKEN_LPAREN, slice_fullstr("(") },
+ { TOKEN_IDENT, slice_fullstr("x") },
+ { TOKEN_COMMA, slice_fullstr(",") },
+ { TOKEN_IDENT, slice_fullstr("y") },
+ { TOKEN_RPAREN, slice_fullstr(")") },
+ { TOKEN_LBRACE, slice_fullstr("{") },
+ { TOKEN_IDENT, slice_fullstr("x") },
+ { TOKEN_PLUS, slice_fullstr("+") },
+ { TOKEN_IDENT, slice_fullstr("y") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_RBRACE, slice_fullstr("}") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_LET, slice_fullstr("let") },
+ { TOKEN_IDENT, slice_fullstr("result") },
+ { TOKEN_ASSIGN, slice_fullstr("=") },
+ { TOKEN_IDENT, slice_fullstr("add") },
+ { TOKEN_LPAREN, slice_fullstr("(") },
+ { TOKEN_IDENT, slice_fullstr("five") },
+ { TOKEN_COMMA, slice_fullstr(",") },
+ { TOKEN_IDENT, slice_fullstr("ten") },
+ { TOKEN_RPAREN, slice_fullstr(")") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_BANG, slice_fullstr("!") },
+ { TOKEN_MINUS, slice_fullstr("-") },
+ { TOKEN_SLASH, slice_fullstr("/") },
+ { TOKEN_ASTERISK, slice_fullstr("*") },
+ { TOKEN_INT, slice_fullstr("5") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_INT, slice_fullstr("5") },
+ { TOKEN_LT, slice_fullstr("<") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_GT, slice_fullstr(">") },
+ { TOKEN_INT, slice_fullstr("5") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_IF, slice_fullstr("if") },
+ { TOKEN_LPAREN, slice_fullstr("(") },
+ { TOKEN_INT, slice_fullstr("5") },
+ { TOKEN_LT, slice_fullstr("<") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_RPAREN, slice_fullstr(")") },
+ { TOKEN_LBRACE, slice_fullstr("{") },
+ { TOKEN_RETURN, slice_fullstr("return") },
+ { TOKEN_TRUE, slice_fullstr("true") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_RBRACE, slice_fullstr("}") },
+ { TOKEN_ELSE, slice_fullstr("else") },
+ { TOKEN_LBRACE, slice_fullstr("{") },
+ { TOKEN_RETURN, slice_fullstr("return") },
+ { TOKEN_FALSE, slice_fullstr("false") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_RBRACE, slice_fullstr("}") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_EQ, slice_fullstr("==") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_INT, slice_fullstr("10") },
+ { TOKEN_NOTEQ, slice_fullstr("!=") },
+ { TOKEN_INT, slice_fullstr("9") },
+ { TOKEN_SEMICOLON, slice_fullstr(";") },
+ { TOKEN_EOF, slice_fullstr("") },
+ };
+ size_t i = 0;
+
+ do {
+ struct token token = lexer_next_token(lexer);
+ asserteq(token.type, expected[i].type);
+ asserteq(slice_cmp(&token.literal, &expected[i].literal), 0);
+ i++;
+ } while (expected[i].type != TOKEN_EOF);
+
+ lexer_destroy(lexer);
+}
+
+int
+main(void)
+{
+ INIT_TESTS();
+ RUN_TEST(test_next_token);
+}
diff --git a/src/tests/parser.c b/src/tests/parser.c
new file mode 100644
index 0000000..49847ec
--- /dev/null
+++ b/src/tests/parser.c
@@ -0,0 +1,640 @@
+#include "parser.h"
+#include "tests/tests.h"
+
+#include "ast.h"
+#include "slice.h"
+
+#include <string.h>
+
+enum value_type {
+ VALUE_IDENT,
+ VALUE_INT,
+ VALUE_BOOL,
+};
+
+struct value {
+ enum value_type type;
+ union {
+ struct slice ident;
+ int64_t integer;
+ bool boolean;
+ };
+};
+
+struct parser *parser;
+
+static void
+check_parser_errors(struct parser *parser, const char *file, int line,
+ const char *func)
+{
+ if (parser->errors->len > 0) {
+ printf("\n");
+ size_t i;
+ char *val;
+ vector_foreach (parser->errors, i, val) {
+ printf("parser error %lu: %s\n", i, val);
+ }
+ printf(TBLD TRED "FAIL!\n" TRST);
+ printf("%s:%d: %s: ", file, line, func);
+ printf("parser encountered errors\n");
+ abort();
+ }
+}
+
+#define check_parser_errors(p) \
+ check_parser_errors(p, __FILE__, __LINE__, __func__)
+
+static void
+test_return_statement(struct statement *st)
+{
+ struct slice retrn_lit = slice_fullstr("return");
+ struct slice st_lit = node_token_literal(st);
+ asserteq(st->type, STATEMENT_RETURN);
+ asserteq(slice_cmp(&retrn_lit, &st_lit), 0);
+}
+
+static void
+test_integer_literal(struct expression *expr, int64_t val)
+{
+ char buf[128];
+ struct slice sval;
+ asserteq(expr->type, EXPRESSION_INT);
+ asserteq(expr->integer.value, val);
+ sprintf(buf, "%ld", val);
+ sval = slice_fullstr(buf);
+ asserteq(slice_cmp(&expr->token.literal, &sval), 0);
+}
+
+static void
+test_identifier(struct expression *expr, struct slice val)
+{
+ asserteq(expr->type, EXPRESSION_IDENT);
+}
+
+static void
+test_boolean_literal(struct expression *expr, bool val)
+{
+ char *str = val ? "true" : "false";
+ struct slice sval = slice_fullstr(str);
+ asserteq(expr->type, EXPRESSION_BOOL);
+ asserteq(expr->boolean.value, val);
+ asserteq(slice_cmp(&expr->token.literal, &sval), 0);
+}
+
+#define test_literal_expression(expr, expect) _Generic((expect), \
+ int64_t: test_integer_literal, \
+ struct slice: test_identifier, \
+ bool: test_boolean_literal \
+ )(expr, expect)
+
+static inline void
+test_expected(struct expression *expr, struct value v)
+{
+ switch(v.type) {
+ case VALUE_IDENT:
+ test_literal_expression(expr, v.ident);
+ break;
+ case VALUE_INT:
+ test_literal_expression(expr, v.integer);
+ break;
+ case VALUE_BOOL:
+ test_literal_expression(expr, v.boolean);
+ break;
+ }
+}
+
+#define VIDENT(v) \
+ (struct value){ .type = VALUE_IDENT, .ident = slice_fullstr(v) }
+
+#define VINT(v) \
+ (struct value){ .type = VALUE_INT, .integer = v }
+
+#define VBOOL(v) \
+ (struct value){ .type = VALUE_BOOL, .boolean = v }
+
+static inline void
+test_infix(struct infix_expression *expr, struct value lval, struct slice *op,
+ struct value rval)
+{
+ test_expected(expr->left, lval);
+ asserteq(slice_cmp(&expr->operator, op), 0);
+ test_expected(expr->right, rval);
+}
+
+static void
+test_let_statement(struct statement *st, struct slice *name)
+{
+ struct slice let_lit = slice_fullstr("let");
+ struct slice st_lit = node_token_literal(st);
+ asserteq(slice_cmp(&let_lit, &st_lit), 0);
+ asserteq(st->type, STATEMENT_LET);
+ asserteq(slice_cmp(&st->let.name->value, name), 0);
+ asserteq(slice_cmp(&st->let.name->token.literal, name), 0);
+}
+
+static void
+test_let_statements(void)
+{
+ struct {
+ char *input;
+ struct slice ident;
+ struct value val;
+ } tests[] = {
+ { "let x = 5;", slice_fullstr("x"), VINT(5) },
+ { "let y = true;", slice_fullstr("y"), VBOOL(true) },
+ { "let foo = bar;", slice_fullstr("foo"), VIDENT("bar") },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ test_let_statement(st, &tests[i].ident);
+ test_expected(st->let.value, tests[i].val);
+ node_destroy(prog);
+ }
+
+}
+
+static void
+test_return_statements(void)
+{
+ struct {
+ char *input;
+ struct slice ident;
+ struct value val;
+ } tests[] = {
+ { "return 5;", slice_fullstr("x"), VINT(5) },
+ { "return true;", slice_fullstr("y"), VBOOL(true) },
+ { "return bar;", slice_fullstr("foo"), VIDENT("bar") },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ test_return_statement(st);
+ test_expected(st->retrn.value, tests[i].val);
+ node_destroy(prog);
+ }
+}
+
+static void
+test_identifier_expression_statements(void)
+{
+ char *input = "foobar;\n";
+ struct slice val = slice_fullstr("foobar");
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ test_literal_expression(st->expr.expr, val);
+
+ node_destroy(prog);
+}
+
+static void
+test_integer_expression_statements(void)
+{
+ char *input = "469;\n";
+ int64_t val = 469;
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ test_literal_expression(st->expr.expr, val);
+
+ node_destroy(prog);
+}
+
+static void
+test_prefix_expression_statements(void)
+{
+ struct {
+ char *input;
+ struct slice operator;
+ struct value val;
+ } tests[] = {
+ { "!5;", slice_fullstr("!"), VINT(5) },
+ { "-15;", slice_fullstr("-"), VINT(15) },
+ { "!foo;", slice_fullstr("!"), VIDENT("foo") },
+ { "-bar;", slice_fullstr("-"), VIDENT("bar") },
+ { "!true;", slice_fullstr("!"), VBOOL(true) },
+ { "!false;", slice_fullstr("!"), VBOOL(false) },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_PREFIX);
+ test_expected(st->expr.expr->prefix.right, tests[i].val);
+ node_destroy(prog);
+ }
+}
+
+static void
+test_infix_expression_statements(void)
+{
+ struct {
+ char *input;
+ struct value lval;
+ struct slice operator;
+ struct value rval;
+ } tests[] = {
+ { "5 + 5;", VINT(5), slice_fullstr("+"), VINT(5) },
+ { "5 - 5;", VINT(5), slice_fullstr("-"), VINT(5) },
+ { "5 * 5;", VINT(5), slice_fullstr("*"), VINT(5) },
+ { "5 / 5;", VINT(5), slice_fullstr("/"), VINT(5) },
+ { "5 > 5;", VINT(5), slice_fullstr(">"), VINT(5) },
+ { "5 < 5;", VINT(5), slice_fullstr("<"), VINT(5) },
+ { "foo + bar;", VIDENT("foo"), slice_fullstr("+"), VIDENT("bar") },
+ { "foo - bar;", VIDENT("foo"), slice_fullstr("-"), VIDENT("bar") },
+ { "foo * bar;", VIDENT("foo"), slice_fullstr("*"), VIDENT("bar") },
+ { "foo / bar;", VIDENT("foo"), slice_fullstr("/"), VIDENT("bar") },
+ { "foo > bar;", VIDENT("foo"), slice_fullstr(">"), VIDENT("bar") },
+ { "foo < bar;", VIDENT("foo"), slice_fullstr("<"), VIDENT("bar") },
+ { "true == true;", VBOOL(true), slice_fullstr("=="), VBOOL(true) },
+ { "true != false;", VBOOL(true), slice_fullstr("!="), VBOOL(false) },
+ { "false != false;", VBOOL(false), slice_fullstr("!="), VBOOL(false) },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_INFIX);
+ test_infix(&st->expr.expr->infix, tests[i].lval, &tests[i].operator,
+ tests[i].rval);
+ node_destroy(prog);
+ }
+}
+
+static void
+test_operator_precedence(void)
+{
+ struct {
+ char *input;
+ char *expect;
+ } tests[] = {
+ {
+ "-a * b",
+ "((-a) * b)",
+ },
+ {
+ "!-a",
+ "(!(-a))",
+ },
+ {
+ "a + b + c",
+ "((a + b) + c)",
+ },
+ {
+ "a + b - c",
+ "((a + b) - c)",
+ },
+ {
+ "a * b * c",
+ "((a * b) * c)",
+ },
+ {
+ "a * b / c",
+ "((a * b) / c)",
+ },
+ {
+ "a + b / c",
+ "(a + (b / c))",
+ },
+ {
+ "a + b * c + d / e - f",
+ "(((a + (b * c)) + (d / e)) - f)",
+ },
+ {
+ "3 + 4; -5 * 5",
+ "(3 + 4)((-5) * 5)",
+ },
+ {
+ "5 > 4 == 3 < 4",
+ "((5 > 4) == (3 < 4))",
+ },
+ {
+ "5 < 4 != 3 > 4",
+ "((5 < 4) != (3 > 4))",
+ },
+ {
+ "3 + 4 * 5 == 3 * 1 + 4 * 5",
+ "((3 + (4 * 5)) == ((3 * 1) + (4 * 5)))",
+ },
+ {
+ "true",
+ "true",
+ },
+ {
+ "false",
+ "false",
+ },
+ {
+ "3 > 5 == false",
+ "((3 > 5) == false)",
+ },
+ {
+ "3 < 5 == true",
+ "((3 < 5) == true)",
+ },
+ {
+ "1 + (2 + 3) + 4",
+ "((1 + (2 + 3)) + 4)",
+ },
+ {
+ "(5 + 5) * 2",
+ "((5 + 5) * 2)",
+ },
+ {
+ "2 / (5 + 5)",
+ "(2 / (5 + 5))",
+ },
+ {
+ "(5 + 5) * 2 * (5 + 5)",
+ "(((5 + 5) * 2) * (5 + 5))",
+ },
+ {
+ "-(5 + 5)",
+ "(-(5 + 5))",
+ },
+ {
+ "!(true == true)",
+ "(!(true == true))",
+ },
+ {
+ "a + add(b * c) + d",
+ "((a + add((b * c))) + d)",
+ },
+ {
+ "add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))",
+ "add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))",
+ },
+ {
+ "add(a + b + c * d / f + g)",
+ "add((((a + b) + ((c * d) / f)) + g))",
+ },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ char buf[128];
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ node_sprint(prog, buf);
+ asserteq(strcmp(tests[i].expect, buf), 0);
+ node_destroy(prog);
+ }
+}
+
+static void
+test_boolean_expression(void)
+{
+ struct {
+ char *input;
+ bool value;
+ } tests[] = {
+ { "true;", true },
+ { "false;", false },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ test_literal_expression(st->expr.expr, tests[i].value);
+ node_destroy(prog);
+ }
+}
+
+static void
+test_if_expression(void)
+{
+ char *input = "if (x < y) { x }";
+ struct value x = VIDENT("x");
+ struct slice op = slice_fullstr("<");
+ struct value y = VIDENT("y");
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_IF);
+ struct if_expression *ifexpr = &st->expr.expr->cond;
+ asserteq(ifexpr->condition->type, EXPRESSION_INFIX);
+ test_infix(&ifexpr->condition->infix, x, &op, y);
+ asserteq(ifexpr->consequence->type, STATEMENT_BLOCK);
+ asserteq(ifexpr->consequence->block.statements->len, 1);
+ struct statement *ifst = ifexpr->consequence->block.statements->values[0];
+ asserteq(ifst->type, STATEMENT_EXPRESSION);
+ test_identifier(ifst->expr.expr, x.ident);
+ asserteq(ifexpr->alternative, NULL);
+ node_destroy(prog);
+}
+
+static void
+test_if_else_expression(void)
+{
+ char *input = "if (x < y) { x } else { y }";
+ struct value x = VIDENT("x");
+ struct slice op = slice_fullstr("<");
+ struct value y = VIDENT("y");
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_IF);
+ struct if_expression *ifexpr = &st->expr.expr->cond;
+ asserteq(ifexpr->condition->type, EXPRESSION_INFIX);
+ test_infix(&ifexpr->condition->infix, x, &op, y);
+ asserteq(ifexpr->consequence->type, STATEMENT_BLOCK);
+ asserteq(ifexpr->consequence->block.statements->len, 1);
+ struct statement *ifst = ifexpr->consequence->block.statements->values[0];
+ asserteq(ifst->type, STATEMENT_EXPRESSION);
+ test_identifier(ifst->expr.expr, x.ident);
+ assertneq(ifexpr->alternative, NULL);
+ asserteq(ifexpr->alternative->block.statements->len, 1);
+ asserteq(ifexpr->alternative->type, STATEMENT_BLOCK);
+ struct statement *elsest = ifexpr->alternative->block.statements->values[0];
+ asserteq(elsest->type, STATEMENT_EXPRESSION);
+ test_identifier(elsest->expr.expr, y.ident);
+ node_destroy(prog);
+}
+
+static void
+test_func_literal(void)
+{
+ char *input = "fn(x, y) { x + y; }";
+ struct value x = VIDENT("x");
+ struct slice op = slice_fullstr("+");
+ struct value y = VIDENT("y");
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_FUNC);
+ struct func_literal *func = &st->expr.expr->func;
+ asserteq(func->parameters->len, 2);
+ test_identifier(func->parameters->values[0], x.ident);
+ test_identifier(func->parameters->values[1], y.ident);
+ asserteq(func->body->type, STATEMENT_BLOCK);
+ asserteq(func->body->block.statements->len, 1);
+ struct statement *fst = func->body->block.statements->values[0];
+ test_infix(&fst->expr.expr->infix, x, &op, y);
+ node_destroy(prog);
+}
+
+static void
+test_func_parameters(void)
+{
+ struct {
+ char *input;
+ struct {
+ struct slice vals[4];
+ size_t len;
+ } params;
+ } tests[] = {
+ {
+ "fn() {};",
+ { 0 },
+ },
+ {
+ "fn(x) {};",
+ {
+ { slice_fullstr("x") },
+ 1
+ },
+ },
+ {
+ "fn(x, y) {};",
+ {
+ { slice_fullstr("x"), slice_fullstr("y") },
+ 2,
+ }
+ },
+ {
+ "fn(x, y, z) {};",
+ {
+ { slice_fullstr("x"), slice_fullstr("y"), slice_fullstr("z") },
+ 3,
+ }
+ },
+ { 0 },
+ };
+ for (size_t i = 0; tests[i].input != NULL; i++) {
+ parser_reset(parser, tests[i].input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_FUNC);
+ struct func_literal *func = &st->expr.expr->func;
+ asserteq(func->parameters->len, tests[i].params.len);
+ for (size_t j = 0; j < tests[i].params.len; j++) {
+ struct expression *param = func->parameters->values[j];
+ asserteq(slice_cmp(&param->ident.token.literal,
+ &tests[i].params.vals[j]), 0);
+ }
+ node_destroy(prog);
+ }
+}
+
+static void
+test_call_expression(void)
+{
+ char *input = "add(1, x * y, add(x, y, z));";
+ int64_t par1 = 1;
+ struct value x = VIDENT("x");
+ struct value y = VIDENT("y");
+ struct slice op1 = slice_fullstr("*");
+ parser_reset(parser, input);
+ struct program *prog = parser_parse_program(parser);
+ check_parser_errors(parser);
+ assertneq(prog, NULL);
+ asserteq(prog->statements->len, 1);
+ struct statement *st = prog->statements->values[0];
+ asserteq(st->type, STATEMENT_EXPRESSION);
+ asserteq(st->expr.expr->type, EXPRESSION_CALL);
+ struct call_expression *call = &st->expr.expr->call;
+ test_identifier(call->func, slice_fullstr("add"));
+ asserteq(call->arguments->len, 3);
+ struct expression *expr1 = call->arguments->values[0],
+ *expr2 = call->arguments->values[1],
+ *expr3 = call->arguments->values[2];
+ test_literal_expression(expr1, par1);
+ asserteq(expr2->type, EXPRESSION_INFIX);
+ test_infix(&expr2->infix, x, &op1, y);
+ asserteq(expr3->type, EXPRESSION_CALL);
+ asserteq(expr3->call.arguments->len, 3);
+}
+
+static void
+init(void)
+{
+ parser = parser_new();
+}
+
+static void
+cleanup(void)
+{
+ parser_destroy(parser);
+}
+
+int
+main(void)
+{
+ INIT_TESTS();
+ init();
+ RUN_TEST(test_let_statements);
+ RUN_TEST(test_return_statements);
+ RUN_TEST(test_identifier_expression_statements);
+ RUN_TEST(test_integer_expression_statements);
+ RUN_TEST(test_prefix_expression_statements);
+ RUN_TEST(test_infix_expression_statements);
+ RUN_TEST(test_operator_precedence);
+ RUN_TEST(test_boolean_expression);
+ RUN_TEST(test_if_expression);
+ RUN_TEST(test_if_else_expression);
+ RUN_TEST(test_func_literal);
+ RUN_TEST(test_func_parameters);
+ RUN_TEST(test_call_expression);
+ cleanup();
+}
diff --git a/src/tests/slice.c b/src/tests/slice.c
new file mode 100644
index 0000000..e2382e8
--- /dev/null
+++ b/src/tests/slice.c
@@ -0,0 +1,41 @@
+#include "tests/tests.h"
+#include "slice.h"
+
+#include <string.h>
+
+static void
+test_slice_cmp(void)
+{
+ struct slice s1a = {
+ .str = "hello world",
+ .start = 6,
+ .end = 11,
+ };
+ struct slice s1b = {
+ .str = "world",
+ .start = 0,
+ .end = 5,
+ };
+ asserteq(slice_cmp(&s1a, &s1b), 0);
+}
+
+static void
+test_slice_sprint(void)
+{
+ struct slice slice = {
+ .str = "hello world",
+ .start = 6,
+ .end = 11,
+ };
+ char buf[32];
+ slice_sprint(&slice, buf);
+ asserteq(strcmp("world", buf), 0);
+}
+
+int
+main(void)
+{
+ INIT_TESTS();
+ RUN_TEST(test_slice_cmp);
+ RUN_TEST(test_slice_sprint);
+}
diff --git a/src/token.c b/src/token.c
new file mode 100644
index 0000000..300fa8c
--- /dev/null
+++ b/src/token.c
@@ -0,0 +1,106 @@
+#include "token.h"
+
+#include <stdio.h>
+#include <stddef.h>
+
+#include "hmap.h"
+
+static struct hmap *keywords = NULL;
+static const char *keys[] = {
+ "fn",
+ "let",
+ "true",
+ "false",
+ "if",
+ "else",
+ "return",
+ NULL,
+};
+enum token_type values[] = {
+ TOKEN_FUNC,
+ TOKEN_LET,
+ TOKEN_TRUE,
+ TOKEN_FALSE,
+ TOKEN_IF,
+ TOKEN_ELSE,
+ TOKEN_RETURN,
+ TOKEN_EOF,
+};
+
+const char *token_types[] = {
+ "ILLEGAL",
+ "EOF",
+ /* Identifiers/Literals */
+ "identifier",
+ "int",
+ /* Operators */
+ "=",
+ "+",
+ "-",
+ "!",
+ "*",
+ "/",
+ "<",
+ ">",
+ "==",
+ "!=",
+ /* Delimiters */
+ ",",
+ ";",
+ "(",
+ ")",
+ "{",
+ "}",
+ /* Keywords */
+ "fn",
+ "let",
+ "true",
+ "false",
+ "if",
+ "else",
+ "return",
+};
+
+void
+token_init_keywords(void)
+{
+ if (keywords == NULL) {
+ keywords = hmap_new();
+ for (size_t i = 0; keys[i] != NULL; i++) {
+ hmap_set(keywords, keys[i], values + i);
+ }
+ }
+}
+
+enum token_type
+token_lookup_ident(const struct slice *ident)
+{
+ enum token_type *t = hmap_gets(keywords, ident);
+ if (t) {
+ return *t;
+ }
+
+ return TOKEN_IDENT;
+}
+
+extern inline const char *
+token_type_print(enum token_type t)
+{
+ return token_types[t];
+}
+
+char *
+token_sprint(struct token *token, char *str)
+{
+ const char *type = token_type_print(token->type);
+ char slicebuf[256];
+ sprintf(str, "TOKEN: type: %s, literal: %s", type,
+ slice_sprint(&token->literal, slicebuf));
+ return str;
+}
+
+void
+token_free_keywords(void)
+{
+ hmap_free(keywords);
+}
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..cdd1977
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,42 @@
+#include "vector.h"
+
+inline static bool
+vector_grow(struct vector *vec)
+{
+ vec->cap *= 2;
+ vec->values = realloc(vec->values, sizeof(vec->values) * vec->cap);
+ return vec->values != NULL;
+}
+
+struct vector *
+vector_new_with_cap(size_t cap)
+{
+ struct vector *vec = malloc(sizeof(*vec));
+ if (!vec) return NULL;
+ vec->values = malloc(sizeof(vec->values) * cap);
+ if (!vec->values) {
+ free(vec);
+ return NULL;
+ }
+ vec->cap = cap;
+ vec->len = 0;
+
+ return vec;
+}
+
+ssize_t
+vector_push(struct vector *vec, void *val)
+{
+ if (vec->len >= vec->cap && !vector_grow(vec)) return -1;
+ vec->values[vec->len] = val;
+ vec->len++;
+
+ return vec->len - 1;
+}
+
+void
+vector_free(struct vector *vec)
+{
+ free(vec->values);
+ free(vec);
+}