Callisto Modules

Apparently there is a lack of guides or information about how modules are implemented in compiled languages, so I made this page to fix that.

This page talks about how modules work in Callisto.

Summary

Callisto is able to compile one source file to a module file. Callisto module files contain serialised data describing defined types, preprocessor information (Callisto has a thing called "versions". They work like C macros except they have no value, so you can do things similar to #ifdef VERSION), and functions. Module files are organised as an array of sections. Each section contains the data described just before, and in some cases it will also contain compiled code, usually assembly.

For example, here is a deserialised section describing a function called cool_number:

$ cac link test2.mod -ps
==== FUNCTION DEFINITION ====
Public: true
Inline: false
Calls:  []
Name:   coolnumber
Params: 0
Ret:    1
Assembly:
	__func__test2__sep__cool__us__number:
	mov qword [r15], 65
	add r15, 8
	ret
$

(The code block looks bad because I use a bad markdown compiler)

The data describes how many parameters it takes (Callisto currently only has one usable type, so it's fine to just say how many parameters it takes), how many values it returns, whether it's public, whether it's inlined (if it's inlined, it will actually contain Callisto code, as inline functions work like macros - yes this is a bad way of doing it), and the functions it calls.

After that data, it also contains the compiled assembly. Also, having a list of functions that this section calls is useful as you can use it at link time to remove uncalled functions and make the executable smaller.

Linking modules together

One issue that comes up while implementing modules (in languages that support top level code) is importing modules that run top level code. Imagine that main.cal imports b.cal, and the linker is run like this: cac link main.mod b.mod.

Before solving this issue, the linker would just concatenate all the sections together based on the order modules are passed to it. This would make the top level code in main.cal run before b.mod, which is wrong as main.cal imports b.cal before running top level code.

To solve this, one source file has to be designated as the entry point of a program, with its top level code being run last. In Callisto, this is done using a module main statement at the top of the file.

The linker uses a recursive function to import everything in the correct order:

void AddImports(Module mod, string name) {
	added ~= name;

foreach (ref isect ; mod.sections) {
	if (isect.GetType() == SectionType.Import) {
		auto sect = cast(ImportSection) isect;
if (!added.canFind(sect.mod)) {
	AddImports(mods[sect.mod], sect.mod);
}
}
}

Add(mod);
}

This function is first called with the designated main module. The added array is there to prevent modules from being added multiple times.

Creating the final assembly

Creating the final assembly is the main thing happening during linking. The linker backend (backends are required as the linker has to add some of its own assembly) has separate strings containing different types of assembly (top level code assembly, function definition assembly, BSS section assembly, data section assembly). It iterates through all the sections in the modules that have been added and adds the assembly from each one to one of these variables.

Once all the modules have been added, the linker concatenates all 4 of these assembly strings together, adding things like section directives to tell the assembler where they should go.

Then that assembly code is assembled and linked to create an executable.

Stub modules

Another issue that comes up while implementing modules is importing files that haven't been compiled yet. If main.cal imports b.cal, but main.cal is compiled first, then it won't be able to import b.cal since it has no module file yet. This is solved with stub modules. Stub modules have their own compiler (called the stub compiler) that just creates all the section metadata from the program's AST, without compiling anything to assembly. This means it will work fine on its own as it doesn't need to import anything.

A build system for Callisto should create stub modules for all source files before it compiles all of them to normal module files.