types: add initial infrastructure for function serialization

 - Introduce a new "program" entity which holds the list of functions
   created during compilation

 - Instead of storing pointers to the in-memory function representation
   in the constant list, store the index of the function within the
   program's function list

 - When loading functions from the constant list, retrieve the function
   by index from the program entity

Signed-off-by: Jo-Philipp Wich <jo@mein.io>

10 files changed, 193 insertions, 42 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index e668751..1430a61 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -51,7 +51,7 @@ IF(JSONC_FOUND)
   INCLUDE_DIRECTORIES(${JSONC_INCLUDE_DIRS})
 ENDIF()
 
-SET(UCODE_SOURCES lexer.c lib.c vm.c chunk.c vallist.c compiler.c source.c types.c)
+SET(UCODE_SOURCES lexer.c lib.c vm.c chunk.c vallist.c compiler.c source.c types.c program.c)
 ADD_LIBRARY(libucode SHARED ${UCODE_SOURCES})
 SET(SOVERSION 0 CACHE STRING "Override ucode library version")
 SET_TARGET_PROPERTIES(libucode PROPERTIES OUTPUT_NAME ucode SOVERSION ${SOVERSION})
diff --git a/compiler.c b/compiler.c
index b6793d7..745707b 100644
--- a/compiler.c
+++ b/compiler.c
@@ -21,6 +21,7 @@
 #include "ucode/chunk.h"
 #include "ucode/vm.h" /* I_* */
 #include "ucode/source.h"
+#include "ucode/program.h"
 #include "ucode/lib.h" /* uc_error_context_format() */
 
 static void uc_compiler_compile_unary(uc_compiler_t *compiler);
@@ -113,14 +114,15 @@ uc_compiler_exprstack_is(uc_compiler_t *compiler, uc_exprflag_t flag)
 }
 
 static void
-uc_compiler_init(uc_compiler_t *compiler, const char *name, size_t srcpos, uc_source_t *source, bool strict)
+uc_compiler_init(uc_compiler_t *compiler, const char *name, size_t srcpos, uc_source_t *source, uc_program_t *program, bool strict)
 {
 	uc_value_t *varname = ucv_string_new("(callee)");
 	uc_function_t *fn;
 
 	compiler->scope_depth = 0;
 
-	compiler->function = ucv_function_new(name, srcpos, source);
+	compiler->program = program;
+	compiler->function = uc_program_function_new(program, name, srcpos, source);
 
 	compiler->locals.count = 0;
 	compiler->locals.entries = NULL;
@@ -1132,7 +1134,7 @@ uc_compiler_compile_arrowfn(uc_compiler_t *compiler, uc_value_t *args, bool rest
 	pos = compiler->parser->prev.pos;
 
 	uc_compiler_init(&fncompiler, NULL, compiler->parser->prev.pos,
-		uc_compiler_current_source(compiler),
+		uc_compiler_current_source(compiler), compiler->program,
 		uc_compiler_is_strict(compiler));
 
 	fncompiler.parent = compiler;
@@ -1563,7 +1565,7 @@ uc_compiler_compile_function(uc_compiler_t *compiler)
 
 	uc_compiler_init(&fncompiler,
 		name ? ucv_string_get(name) : NULL, compiler->parser->prev.pos,
-		uc_compiler_current_source(compiler),
+		uc_compiler_current_source(compiler), compiler->program,
 		uc_compiler_is_strict(compiler));
 
 	fncompiler.parent = compiler;
@@ -2875,10 +2877,11 @@ uc_compile(uc_parse_config_t *config, uc_source_t *source, char **errp)
 	uc_exprstack_t expr = { .token = TK_EOF };
 	uc_parser_t parser = { .config = config };
 	uc_compiler_t compiler = { .parser = &parser, .exprstack = &expr };
+	uc_program_t *prog = uc_program_new();
 	uc_function_t *fn;
 
 	uc_lexer_init(&parser.lex, config, source);
-	uc_compiler_init(&compiler, "main", 0, source,
+	uc_compiler_init(&compiler, "main", 0, source, prog,
 		config && config->strict_declarations);
 
 	uc_compiler_parse_advance(&compiler);
diff --git a/include/ucode/compiler.h b/include/ucode/compiler.h
index 04fc0ef..df242dc 100644
--- a/include/ucode/compiler.h
+++ b/include/ucode/compiler.h
@@ -116,6 +116,7 @@ typedef struct uc_compiler {
 	uc_exprstack_t *exprstack;
 	uc_value_t *function;
 	uc_parser_t *parser;
+	uc_program_t *program;
 	size_t scope_depth, current_srcpos, last_insn;
 } uc_compiler_t;
 
diff --git a/include/ucode/program.h b/include/ucode/program.h
new file mode 100644
index 0000000..19b3c9f
--- /dev/null
+++ b/include/ucode/program.h
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2022 Jo-Philipp Wich <jo@mein.io>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef __PROGRAM_H_
+#define __PROGRAM_H_
+
+#include "types.h"
+
+
+uc_program_t *uc_program_new(void);
+
+void uc_program_free(uc_program_t *);
+
+uc_value_t *uc_program_function_new(uc_program_t *, const char *, size_t, uc_source_t *);
+size_t uc_program_function_id(uc_program_t *, uc_value_t *);
+uc_value_t *uc_program_function_load(uc_program_t *, size_t);
+
+#endif /* __PROGRAM_H_ */
diff --git a/include/ucode/types.h b/include/ucode/types.h
index cbd03dd..7bd0ea9 100644
--- a/include/ucode/types.h
+++ b/include/ucode/types.h
@@ -148,14 +148,16 @@ typedef struct {
 	char source[];
 } uc_regexp_t;
 
-typedef struct {
+typedef struct uc_function {
 	uc_value_t header;
-	bool arrow, vararg, strict;
+	bool arrow, vararg, strict, root;
 	size_t nargs;
 	size_t nupvals;
 	size_t srcpos;
 	uc_chunk_t chunk;
 	uc_source_t *source;
+	struct uc_program *program;
+	uc_weakref_t progref;
 	char name[];
 } uc_function_t;
 
@@ -199,6 +201,13 @@ typedef struct {
 uc_declare_vector(uc_resource_types_t, uc_resource_type_t *);
 
 
+/* Program structure definitions */
+
+typedef struct uc_program {
+	uc_weakref_t functions;
+} uc_program_t;
+
+
 /* Parser definitions */
 
 typedef struct {
@@ -275,6 +284,9 @@ struct uc_vm {
 void ucv_free(uc_value_t *, bool);
 void ucv_put(uc_value_t *);
 
+void ucv_unref(uc_weakref_t *);
+void ucv_ref(uc_weakref_t *, uc_weakref_t *);
+
 uc_value_t *ucv_get(uc_value_t *uv);
 
 uc_type_t ucv_type(uc_value_t *);
@@ -338,7 +350,7 @@ size_t ucv_object_length(uc_value_t *);
 	                 : 0);																		\
 	     entry##key = entry_next##key)
 
-uc_value_t *ucv_function_new(const char *, size_t, uc_source_t *);
+uc_value_t *ucv_function_new(const char *, size_t, uc_source_t *, uc_program_t *);
 size_t ucv_function_srcpos(uc_value_t *, size_t);
 
 uc_value_t *ucv_cfunction_new(const char *, uc_cfn_ptr_t);
diff --git a/include/ucode/vallist.h b/include/ucode/vallist.h
index a1b33a5..f1c1437 100644
--- a/include/ucode/vallist.h
+++ b/include/ucode/vallist.h
@@ -38,7 +38,7 @@ typedef enum {
 	TAG_DBL = 3,
 	TAG_STR = 4,
 	TAG_LSTR = 5,
-	TAG_PTR = 6
+	TAG_FUNC = 6
 } uc_value_type_t;
 
 uc_value_t *uc_number_parse(const char *buf, char **end);
diff --git a/program.c b/program.c
new file mode 100644
index 0000000..c413f38
--- /dev/null
+++ b/program.c
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2022 Jo-Philipp Wich <jo@mein.io>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "ucode/program.h"
+
+
+uc_program_t *
+uc_program_new(void)
+{
+	uc_program_t *prog;
+
+	prog = xalloc(sizeof(*prog));
+
+	prog->functions.next = &prog->functions;
+	prog->functions.prev = &prog->functions;
+
+	return prog;
+}
+
+static inline uc_function_t *
+ref_to_function(uc_weakref_t *ref)
+{
+	return (uc_function_t *)((uintptr_t)ref - offsetof(uc_function_t, progref));
+}
+
+static inline uc_value_t *
+ref_to_uv(uc_weakref_t *ref)
+{
+	return (uc_value_t *)((uintptr_t)ref - offsetof(uc_function_t, progref));
+}
+
+void
+uc_program_free(uc_program_t *prog)
+{
+	uc_weakref_t *ref, *tmp;
+	uc_function_t *func;
+
+	if (!prog)
+		return;
+
+	for (ref = prog->functions.next, tmp = ref->next; ref != &prog->functions; ref = tmp, tmp = tmp->next) {
+		func = ref_to_function(ref);
+		func->program = NULL;
+		func->progref.next = NULL;
+		func->progref.prev = NULL;
+
+		ucv_put(&func->header);
+	}
+
+	free(prog);
+}
+
+uc_value_t *
+uc_program_function_new(uc_program_t *prog, const char *name, size_t srcpos, uc_source_t *source)
+{
+	uc_function_t *func;
+
+	func = (uc_function_t *)ucv_function_new(name, srcpos, source, prog);
+	func->root = (prog->functions.next == &prog->functions);
+
+	ucv_ref(&prog->functions, &func->progref);
+
+	return &func->header;
+}
+
+size_t
+uc_program_function_id(uc_program_t *prog, uc_value_t *func)
+{
+	uc_weakref_t *ref;
+	size_t i;
+
+	for (ref = prog->functions.prev, i = 1; ref != &prog->functions; ref = ref->prev, i++)
+		if (ref_to_uv(ref) == func)
+			return i;
+
+	return 0;
+}
+
+uc_value_t *
+uc_program_function_load(uc_program_t *prog, size_t id)
+{
+	uc_weakref_t *ref;
+	size_t i;
+
+	for (ref = prog->functions.prev, i = 1; ref != &prog->functions; ref = ref->prev, i++)
+		if (i == id)
+			return ref_to_uv(ref);
+
+	return NULL;
+}
diff --git a/types.c b/types.c
index 0122984..65cba22 100644
--- a/types.c
+++ b/types.c
@@ -26,6 +26,7 @@
 #include "ucode/types.h"
 #include "ucode/util.h"
 #include "ucode/vm.h"
+#include "ucode/program.h"
 
 uc_type_t
 ucv_type(uc_value_t *uv)
@@ -60,14 +61,14 @@ ucv_typename(uc_value_t *uv)
 	return "unknown";
 }
 
-static void
+void
 ucv_unref(uc_weakref_t *ref)
 {
 	ref->prev->next = ref->next;
 	ref->next->prev = ref->prev;
 }
 
-static void
+void
 ucv_ref(uc_weakref_t *head, uc_weakref_t *item)
 {
 	item->next = head->next;
@@ -238,6 +239,14 @@ ucv_free(uc_value_t *uv, bool retain)
 
 	case UC_FUNCTION:
 		function = (uc_function_t *)uv;
+
+		if (function->program) {
+			ucv_unref(&function->progref);
+
+			if (function->root)
+				uc_program_free(function->program);
+		}
+
 		uc_chunk_free(&function->chunk);
 		uc_source_put(function->source);
 		break;
@@ -942,7 +951,7 @@ ucv_object_length(uc_value_t *uv)
 
 
 uc_value_t *
-ucv_function_new(const char *name, size_t srcpos, uc_source_t *source)
+ucv_function_new(const char *name, size_t srcpos, uc_source_t *source, uc_program_t *program)
 {
 	size_t namelen = 0;
 	uc_function_t *fn;
@@ -961,6 +970,7 @@ ucv_function_new(const char *name, size_t srcpos, uc_source_t *source)
 	fn->nupvals = 0;
 	fn->srcpos = srcpos;
 	fn->source = uc_source_get(source);
+	fn->program = program;
 	fn->vararg = false;
 
 	uc_chunk_init(&fn->chunk);
@@ -1020,6 +1030,8 @@ ucv_closure_new(uc_vm_t *vm, uc_function_t *function, bool arrow_fn)
 	if (vm)
 		ucv_ref(&vm->values, &closure->ref);
 
+	ucv_get(&function->header);
+
 	return &closure->header;
 }
 
diff --git a/vallist.c b/vallist.c
index d46bf23..abf29ad 100644
--- a/vallist.c
+++ b/vallist.c
@@ -24,6 +24,7 @@
 
 #include "ucode/util.h"
 #include "ucode/chunk.h"
+#include "ucode/program.h"
 #include "ucode/vallist.h"
 #include "ucode/vm.h"
 
@@ -271,17 +272,6 @@ uc_vallist_init(uc_value_list_t *list)
 void
 uc_vallist_free(uc_value_list_t *list)
 {
-	uc_value_t *o;
-	size_t i;
-
-	for (i = 0; i < list->isize; i++) {
-		if (TAG_GET_TYPE(list->index[i]) == TAG_PTR) {
-			o = uc_vallist_get(list, i);
-			ucv_put(o);
-			ucv_put(o);
-		}
-	}
-
 	free(list->index);
 	free(list->data);
 	uc_vallist_init(list);
@@ -476,22 +466,13 @@ find_str(uc_value_list_t *list, const char *s, size_t slen)
 }
 
 static void
-add_ptr(uc_value_list_t *list, void *ptr)
+add_func(uc_value_list_t *list, uc_function_t *func)
 {
-	size_t sz = TAG_ALIGN(sizeof(ptr));
+	size_t id = uc_program_function_id(func->program, &func->header);
 
-	if ((TAG_TYPE)list->dsize + sz > TAG_MASK) {
-		fprintf(stderr, "Constant data too large\n");
-		abort();
-	}
-
-	list->data = xrealloc(list->data, list->dsize + sz);
-
-	memset(list->data + list->dsize, 0, sz);
-	memcpy(list->data + list->dsize, &ptr, sizeof(ptr));
+	assert(id != 0 && TAG_FIT_NV(id));
 
-	list->index[list->isize++] = (uint64_t)(TAG_PTR | (list->dsize << TAG_BITS));
-	list->dsize += sz;
+	list->index[list->isize++] = (TAG_TYPE)(TAG_FUNC | TAG_SET_NV(id));
 }
 
 ssize_t
@@ -545,7 +526,7 @@ uc_vallist_add(uc_value_list_t *list, uc_value_t *value)
 		break;
 
 	case UC_FUNCTION:
-		add_ptr(list, value);
+		add_func(list, (uc_function_t *)value);
 		break;
 
 	default:
@@ -564,10 +545,16 @@ uc_vallist_type(uc_value_list_t *list, size_t idx)
 	return TAG_GET_TYPE(list->index[idx]);
 }
 
+#define container_of(ptr, type, member) ({                      \
+        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
+        (type *)( (char *)__mptr - offsetof(type,member) );})
+
 uc_value_t *
 uc_vallist_get(uc_value_list_t *list, size_t idx)
 {
 	char str[sizeof(TAG_TYPE)];
+	uc_function_t *func;
+	uc_chunk_t *chunk;
 	size_t n, len;
 
 	switch (uc_vallist_type(list, idx)) {
@@ -605,11 +592,11 @@ uc_vallist_get(uc_value_list_t *list, size_t idx)
 
 		return ucv_string_new_length(list->data + TAG_GET_OFFSET(list->index[idx]) + sizeof(uint32_t), len);
 
-	case TAG_PTR:
-		if (TAG_GET_OFFSET(list->index[idx]) + sizeof(void *) > list->dsize)
-			return NULL;
+	case TAG_FUNC:
+		chunk = container_of(list, uc_chunk_t, constants);
+		func = container_of(chunk, uc_function_t, chunk);
 
-		return ucv_get(*(uc_value_t **)(list->data + TAG_GET_OFFSET(list->index[idx])));
+		return uc_program_function_load(func->program, TAG_GET_NV(list->index[idx]));
 
 	default:
 		return NULL;
diff --git a/vm.c b/vm.c
index e7757cd..b8cf50f 100644
--- a/vm.c
+++ b/vm.c
@@ -2602,6 +2602,8 @@ uc_vm_execute(uc_vm_t *vm, uc_function_t *fn, uc_value_t **retval)
 		break;
 	}
 
+	ucv_put(&fn->header);
+
 	return status;
 }