source: doc/proposals/modules-alvin/2_staged_modules/staged_modules.md@ cbd6b5c

# Staged modules

<table>
    <tr>
        <td>
            <b>Example code:</b><br>
        </td>
        <td>
<pre>
module M;
import M1;
export struct S1 s[N];
export struct S { int i; };
</pre>
        </td>
        <td>
<pre>
module M1;
import M;
import M2;
export struct S1 {
    struct S arrS[2];
    struct S2 *s2;
};
export const int N = 5;
</pre>
        </td>
        <td>
<pre>
module M2;
import M1;
export struct S2 {
    int i;
    struct S1 s1;
};
</pre>
    </tr>
    <tr>
        <td>
            <b>Stage 1:</b><br>
            &emsp;  Exported names<br>
            &emsp;  (file only)<br>
        </td>
        <td>
<pre>
M
M1
S
s
</pre>
        </td>
        <td>
<pre>
M1
M, M2
S1
N
</pre>
        </td>
        <td>
<pre>
M2
M1
S2

</pre>
        </td>
    </tr>
    <tr>
        <td>
            <b>Stage 2:</b><br>
            &emsp;  Scope resolution<br>
            &emsp;  and building a symbol table<br>
            &emsp;  (file + imports)<br>
        </td>
        <td>
<pre>
M  -> S, s
M1 -> S1, N
</pre>
        </td>
        <td>
<pre>
M1 -> S1, N
M  -> S, s
M2 -> S2
</pre>
        </td>
        <td>
<pre>
M2 -> S2
M1 -> S1, N
</pre>
        </td>
    </tr>
    <tr>
        <td>
            Stage 3:<br>
            &emsp;  Symbol resolution in expressions<br>
            &emsp;  and resolving transitive dependencies<br>
            &emsp;  (file + transitive import closure)<br>
        </td>
        <td>
<pre>
    S  <-\
/-> S1 --/
|-> N
\-- s
</pre>
        </td>
        <td>
<pre>
    S  <-\
    S1 --/
    N
</pre>
        </td>
        <td>
<pre>
    S  <-\
/-> S1 --/
\-- S2
</pre>
    </tr>
</table>

## What's going on here?

### User perspective:

The module system runs after the preprocessor and before symbol resolution.

To be a module, `module <identifier>;` must be the first declaration.

`import <identifier>;` must be before any symbol definitions.

`export` must be the first keyword of a symbol definition.

Only symbol definitions are allowed at top-level in modules &mdash; all top-level symbols are already visible to each other, so `struct S1;` is unnecessary.

Exports make symbols visible to importers.

*Some of these restrictions can be modified through future extensions (see Language extensions).*

### Stage 1:

Stage 1 is about gathering useful information from analyzing a single module file in isolation.

At this stage, there is no symbol table, so we're limited to just exported names.

In the example, first line is module name, followed by import names, type names and functions/globals.

Some additional information can be gathered at this stage (eg. `const`, field names), but it's not very useful at this point &mdash; wait until stage 2.

*In order to parse the file without knowing the symbol table beforehand, the first name of a function/global definition is treated as a type.*

*This means implicit int return types are disallowed here (and have been since C99). Note expression statements are disallowed at top-level.*

### Stage 2:

Stage 2 is about what can be done with the stage 1 outputs of imported files (a module file implicitly imports itself).

This information allows us to determine which symbols are in scope, allowing us to resolve names.

This stage lacks the definitions of the imported symbols, so anything that requires those (eg. `x.y.z`) are left for stage 3 to resolve.

*This means expressions are not parsed, so expression-dependent aspects of types are unresolved (eg. array sizes, `auto`, `typeof`, `decltype`, templates).*

*Note: `auto` and `typeof` are not allowed at top-level in C23. Regardless, they can still be resolved in stage 3 by lazily loading their type information.*

### Stage 3:

Stage 3 allows access to stage 2 outputs of the transitive import closure (ie. all modules that are reachable by following imports recursively).

This allows us to resolve expressions and other remaining details by loading symbol definitions as needed.

If a cycle is detected while loading symbol definitions, we have a type of infinite size or an unresolvable ambiguity &mdash; produce an error diagnostic.

To reduce file IO, modules are lazily loaded in as symbol definitions are needed &mdash; S1 doesn't need the definition of S2, so M2 isn't loaded in.

To do this efficiently, expression parsing code would call lookup functions to go from name to symbol candidates.

*The stitched modules approach is to output code that would be reparsed in the original compiler, which is simpler to implement.*

*However, the module system does not parse expressions, so it would have to eagerly grab all reachable symbol definitions, which is inefficient.*

*The point of breaking into stages is more about unlocking parallelization opportunities and avoiding duplicate work.*

## Notes

### Stage 3 does a lot of duplicated work

For example, S1 needs the definition of S in all 3 modules. Ideally we would fetch from a cache instead.

Another example is inline functions. Some thought would need to be put in to figure out exactly how the cache would function.

This means stage 3 is grabbing information from a previous stage 3 run, so this is an optimization, not functionally required.

### Why not merge stages 2 and 3 together?

Stage 2 determines which names are in scope, stage 3 takes it further.

As a language becomes more powerful, the value of stage 2 diminishes because a lot of language features require having the symbol definition.

Zig weaves both stages into a single pass. Names are resolved lazily and symbol definitions loaded lazily.

So stage 2 can be thought of as a substage of stage 3.

### What build optimizations does this enable?

Each file within a stage can be processed in parallel.

If stage 1 doesn't change anything the later stages need, could skip recompiling importers.

If stage 2 gets new symbols but doesn't use them, could also skip.

This fine-grained analysis could be accomplished by hashing symbol definitions, similar to Rust incremental compilation.

Contrast with Zig's top-down approach, which has a different set of advantages and disadvantages.

## Language extensions

There are a number of limitations with the proposed module system, which can be resolved with extensions:

* global module fragment: Taking inspiration from C++20 modules, this allows us to use header files within our modules.
* export import: This allows us to avoid having to write out every import, by having one import expand into multiple imports.
* module namespacing: We can follow the same ABI as C++20 modules (ie. `name@module`). This helps us avoid linker symbol clashes.
* import as module_name: Makes it so we qualify names as `module_name.S` for more control.
* tagged exports: Some modules may need more implementation details than others. `export(tag)` means `import M(tag);` gets it.
* relaxed import placement: import statements could be placed within function definitions.
* alternative module names: What if we imported using the file path, similar to `#include` ?
* constexpr: While not a module-specific feature, having this reduces our reliance on preprocessor directives.
* ordering initializers: `import ordered M;` would mean M is initialized before this module.
* escape hatches: There may be cases where the user needs to circumvent the module system. Let them.
* migration tools: By handling circular imports, we can support much of what .c/.h files do. So build an automatic migration tool.
* code analysis tools: Modules make the link between symbol names explicit, so we can perform more complex analyses and refactorings.