compiler: rework export index allocation

The current implementation of the module export offset tracking was
inadequate and failed to properly handle larger module dependency
graphs. In order to properly support nested module imports/exports,
the following changes have been introduced:

 - Gather export slots during module compilation and emit corresponding
   export opcodes as one contiguous block at the end of the module
   function body, right before the final return. This ensures that
   interleaved imports of other modules do not place foreign exports
   between our module exports.

 - Track the number of program wide allocated export slots in order
   to derive per-module-source offsets for the global VM export list.

 - Derive import opcode source index from the module source export
   offset and the index of the requested name within the module source
   export name list.

 - Improve error reporting for circular module imports.

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

4 files changed, 262 insertions, 14 deletions

diff --git a/compiler.c b/compiler.c
index 177d436..dc6afea 100644
--- a/compiler.c
+++ b/compiler.c
@@ -593,6 +593,45 @@ uc_compiler_set_jmpaddr(uc_compiler_t *compiler, size_t off, uint32_t dest)
 	chunk->entries[off + 4] = addr % 0x100;
 }
 
+static void
+uc_compiler_inc_exportnum(uc_compiler_t *compiler)
+{
+	uc_source_t *root = uc_program_function_source(uc_program_entry(compiler->program));
+	uint64_t u;
+
+	if (root->exports.count == 0) {
+		uc_vector_push(&root->exports, ucv_uint64_new(1));
+	}
+	else {
+		u = ucv_uint64_get(root->exports.entries[0]);
+
+		ucv_put(root->exports.entries[0]);
+
+		root->exports.entries[0] = ucv_uint64_new(u + 1);
+	}
+}
+
+static size_t
+uc_compiler_get_exportnum(uc_compiler_t *compiler)
+{
+	uc_source_t *root = uc_program_function_source(uc_program_entry(compiler->program));
+
+	return root->exports.count ? ucv_uint64_get(root->exports.entries[0]) : 0;
+}
+
+static void
+uc_compiler_emit_exports(uc_compiler_t *compiler) {
+	size_t i;
+
+	if (!compiler->patchlist || compiler->patchlist->token != TK_EXPORT)
+		return;
+
+	for (i = 0; i < compiler->patchlist->count; i++) {
+		uc_compiler_emit_insn(compiler, 0, I_EXPORT);
+		uc_compiler_emit_u32(compiler, 0, compiler->patchlist->entries[i]);
+	}
+}
+
 static uc_function_t *
 uc_compiler_finish(uc_compiler_t *compiler)
 {
@@ -601,6 +640,9 @@ uc_compiler_finish(uc_compiler_t *compiler)
 	uc_upvals_t *upvals = &compiler->upvals;
 	size_t i;
 
+	if (compiler->function->module)
+		uc_compiler_emit_exports(compiler);
+
 	uc_compiler_emit_insn(compiler, 0, I_LNULL);
 	uc_compiler_emit_insn(compiler, 0, I_RETURN);
 
@@ -2782,7 +2824,7 @@ uc_compiler_compile_control(uc_compiler_t *compiler)
 		p = p->parent;
 	}
 
-	if (!p) {
+	if (!p || p->token == TK_EXPORT) {
 		uc_compiler_syntax_error(compiler, pos,
 			(type == TK_BREAK)
 				? "break must be inside loop or switch"
@@ -2954,8 +2996,8 @@ uc_compiler_export_add(uc_compiler_t *compiler, uc_value_t *name, ssize_t slot)
 				"Duplicate default export for module '%s'", source->filename);
 	}
 	else {
-		uc_compiler_emit_insn(compiler, 0, I_EXPORT);
-		uc_compiler_emit_u32(compiler, 0, slot);
+		uc_vector_push(compiler->patchlist, slot);
+		uc_compiler_inc_exportnum(compiler);
 	}
 }
 
@@ -3078,6 +3120,10 @@ uc_compiler_compile_module_source(uc_compiler_t *compiler, uc_source_t *source,
 
 	uc_program_function_foreach(compiler->program, fn) {
 		if (uc_program_function_source(fn) == source) {
+			if (source->exports.offset == (size_t)-1)
+				uc_compiler_syntax_error(compiler, compiler->parser->prev.pos,
+					"Circular dependency");
+
 			loaded = true;
 			break;
 		}
@@ -3087,9 +3133,14 @@ uc_compiler_compile_module_source(uc_compiler_t *compiler, uc_source_t *source,
 		load_idx = uc_program_function_id(compiler->program,
 			uc_program_function_last(compiler->program)) + 1;
 
+		source->exports.offset = (size_t)-1;
+
 		if (!uc_compile_from_source(&config, source, compiler->program, errp))
 			return false;
 
+		source->exports.offset = uc_compiler_get_exportnum(compiler) - source->exports.count;
+		uc_compiler_current_source(compiler)->exports.offset += source->exports.count;
+
 		/* emit load, call & pop instructions */
 		uc_compiler_emit_insn(compiler, compiler->parser->prev.pos, I_CLFN);
 		uc_compiler_emit_u32(compiler, 0, load_idx);
@@ -3103,20 +3154,17 @@ uc_compiler_compile_module_source(uc_compiler_t *compiler, uc_source_t *source,
 	/* count imports, handle wildcard imports */
 	for (i = 0; i < ucv_array_length(imports); i++) {
 		if (ucv_boolean_get(ucv_array_get(imports, i))) {
-			/* find index of first module export */
-			slot = uc_program_export_lookup(compiler->program, source, source->exports.entries[0]);
-
-			if (slot > 0xffff || source->exports.count > 0xffff) {
+			if (source->exports.offset > 0xffff || source->exports.count > 0xffff) {
 				uc_compiler_syntax_error(compiler, compiler->parser->prev.pos,
 					"Too many module exports");
 			}
 
 			/* emit import instruction... */
-			uc_compiler_emit_insn(compiler, 0, I_IMPORT);
+			uc_compiler_emit_insn(compiler, compiler->parser->prev.pos, I_IMPORT);
 			uc_compiler_emit_u32(compiler, 0, source->exports.count | (0xffff << 16));
 
 			/* ... followed by first module export offset ... */
-			uc_compiler_emit_u16(compiler, 0, slot);
+			uc_compiler_emit_u16(compiler, 0, source->exports.offset);
 
 			/* ... and constant indexes for all exported names */
 			for (load_idx = 0; load_idx < source->exports.count; load_idx++) {
@@ -3144,7 +3192,7 @@ uc_compiler_compile_module_source(uc_compiler_t *compiler, uc_source_t *source,
 		import = ucv_array_get(imports, i);
 
 		if (!ucv_boolean_get(import)) {
-			slot = uc_program_export_lookup(compiler->program, source, import);
+			slot = uc_source_export_lookup(source, import);
 
 			if (slot == -1) {
 				if (import)
@@ -3159,8 +3207,9 @@ uc_compiler_compile_module_source(uc_compiler_t *compiler, uc_source_t *source,
 					"Too many module exports");
 			}
 			else {
-				uc_compiler_emit_insn(compiler, 0, I_IMPORT);
-				uc_compiler_emit_u32(compiler, 0, slot | ((compiler->upvals.count - n_imports + i) << 16));
+				uc_compiler_emit_insn(compiler, compiler->parser->prev.pos, I_IMPORT);
+				uc_compiler_emit_u32(compiler, 0,
+					(source->exports.offset + slot) | ((compiler->upvals.count - n_imports + i) << 16));
 			}
 		}
 	}
@@ -3470,6 +3519,7 @@ uc_compile_from_source(uc_parse_config_t *config, uc_source_t *source, uc_progra
 
 	return NULL;
 #else
+	uc_patchlist_t exports = { .token = TK_EXPORT };
 	uc_exprstack_t expr = { .token = TK_EOF };
 	uc_parser_t parser = { .config = config };
 	uc_compiler_t compiler = { .parser = &parser, .exprstack = &expr };
@@ -3491,6 +3541,7 @@ uc_compile_from_source(uc_parse_config_t *config, uc_source_t *source, uc_progra
 		config && config->strict_declarations);
 
 	if (progptr == prog) {
+		compiler.patchlist = &exports;
 		compiler.function->module = true;
 	}
 
@@ -3510,6 +3561,7 @@ uc_compile_from_source(uc_parse_config_t *config, uc_source_t *source, uc_progra
 	}
 
 	uc_lexer_free(&parser.lex);
+	uc_vector_clear(&exports);
 
 	if (!fn) {
 		if (progptr != prog)
diff --git a/include/ucode/types.h b/include/ucode/types.h
index 64ae7cb..636d6e4 100644
--- a/include/ucode/types.h
+++ b/include/ucode/types.h
@@ -65,7 +65,6 @@ typedef struct {
 /* Source buffer defintions */
 
 uc_declare_vector(uc_lineinfo_t, uint8_t);
-uc_declare_vector(uc_exports_t, uc_value_t *);
 
 typedef struct {
 	uc_value_t header;
@@ -73,7 +72,10 @@ typedef struct {
 	FILE *fp;
 	size_t off;
 	uc_lineinfo_t lineinfo;
-	uc_exports_t exports;
+	struct {
+		size_t count, offset;
+		uc_value_t **entries;
+	} exports;
 } uc_source_t;
 
 
diff --git a/tests/custom/04_modules/14_circular_imports b/tests/custom/04_modules/14_circular_imports
new file mode 100644
index 0000000..0b6070a
--- /dev/null
+++ b/tests/custom/04_modules/14_circular_imports
@@ -0,0 +1,43 @@
+Circular imports are not possible and will lead to a compilation error.
+
+-- Testcase --
+import a_val from "./files/a.uc";
+-- End --
+
+-- File a.uc --
+import b_val from "./b.uc";
+export default "a";
+-- End --
+
+-- File b.uc --
+import a_val from "./a.uc";
+export default "b";
+-- End --
+
+-- Args --
+-R
+-- End --
+
+-- Expect stderr --
+Syntax error: Unable to compile module './files/a.uc':
+
+  | Syntax error: Unable to compile module './files/b.uc':
+  |
+  |   | Syntax error: Circular dependency
+  |   | In ./files/b.uc, line 1, byte 19:
+  |   |
+  |   |  `import a_val from "./a.uc";`
+  |   |   Near here --------^
+  |
+  | In ./files/a.uc, line 1, byte 27:
+  |
+  |  `import b_val from "./b.uc";`
+  |   Near here ----------------^
+
+In [stdin], line 1, byte 33:
+
+ `import a_val from "./files/a.uc";`
+  Near here ----------------------^
+
+
+-- End --
diff --git a/tests/custom/04_modules/15_complex_imports b/tests/custom/04_modules/15_complex_imports
new file mode 100644
index 0000000..f4dd588
--- /dev/null
+++ b/tests/custom/04_modules/15_complex_imports
@@ -0,0 +1,151 @@
+This testcase implements a somewhat complex dependency chain to stress
+test the compiler module resolving.
+
+The dependency tree is:
+
+root
+ + mod1
+    + mod4
+    + mod8
+ + mod2
+    + mod4
+    + mod6
+    + mod8
+    + mod9
+ + mod3
+    + mod4
+    + mod6
+ + mod4
+ + mod5
+    + mod1
+       + mod4
+       + mod8
+    + mod2
+       + mod4
+       + mod6
+       + mod8
+       + mod9
+    + mod4
+    + mod6
+    + mod8
+    + mod9
+       + mod4
+       + mod6
+ + mod6
+ + mod7
+    + mod5
+       + mod1
+          + mod4
+          + mod8
+       + mod2
+          + mod4
+          + mod6
+          + mod8
+          + mod9
+       + mod4
+       + mod6
+       + mod8
+       + mod9
+          + mod4
+          + mod6
+    + mod6
+ + mod8
+
+-- Testcase --
+import mod1 from 'mod1';
+import mod2 from 'mod2';
+import mod3 from 'mod3';
+import mod4 from 'mod4';
+import mod5 from 'mod5';
+import mod6 from 'mod6';
+import mod7 from 'mod7';
+import mod8 from 'mod8';
+
+print("root: ", [ mod1, mod2, mod3, mod4, mod5, mod6, mod7, mod8 ], "\n");
+-- End --
+
+-- File mod1.uc --
+import mod4 from 'mod4';
+import mod8 from 'mod8';
+
+print("mod1: ", [ mod4, mod8 ], "\n");
+
+export default 'mod1';
+-- End --
+
+-- File mod2.uc --
+import mod9 from 'mod9';
+import mod4 from 'mod4';
+import mod8 from 'mod8';
+import mod6 from 'mod6';
+
+print("mod2: ", [ mod4, mod6, mod8, mod9 ], "\n");
+
+export default 'mod2';
+-- End --
+
+-- File mod3.uc --
+import mod4 from 'mod4';
+import mod6 from 'mod6';
+
+print("mod3: ", [ mod4, mod6 ], "\n");
+
+export default 'mod3';
+-- End --
+
+-- File mod4.uc --
+export default 'mod4';
+-- End --
+
+-- File mod5.uc --
+import mod1 from 'mod1';
+import mod4 from 'mod4';
+import mod2 from 'mod2';
+import mod9 from 'mod9';
+import mod8 from 'mod8';
+import mod6 from 'mod6';
+
+print("mod5: ", [ mod1, mod2, mod4, mod6, mod8, mod9 ], "\n");
+
+export default 'mod5';
+-- End --
+
+-- File mod6.uc --
+export default 'mod6';
+-- End --
+
+-- File mod7.uc --
+import mod6 from 'mod6';
+import mod5 from 'mod5';
+
+print("mod7: ", [ mod5, mod6 ], "\n");
+
+export default 'mod7';
+-- End --
+
+-- File mod8.uc --
+export default 'mod8';
+-- End --
+
+-- File mod9.uc --
+import mod4 from 'mod4';
+import mod6 from 'mod6';
+
+print("mod9: ", [ mod4, mod6 ], "\n");
+
+export default 'mod9';
+-- End --
+
+-- Args --
+-R -L files/
+-- End --
+
+-- Expect stdout --
+mod1: [ "mod4", "mod8" ]
+mod9: [ "mod4", "mod6" ]
+mod2: [ "mod4", "mod6", "mod8", "mod9" ]
+mod3: [ "mod4", "mod6" ]
+mod5: [ "mod1", "mod2", "mod4", "mod6", "mod8", "mod9" ]
+mod7: [ "mod5", "mod6" ]
+root: [ "mod1", "mod2", "mod3", "mod4", "mod5", "mod6", "mod7", "mod8" ]
+-- End --