Index: doc/proposals/modules-alvin/2_staged_modules/staged_modules.md =================================================================== --- doc/proposals/modules-alvin/2_staged_modules/staged_modules.md (revision cbd6b5c66ac6688db5f91224d176d530b57dc80a) +++ doc/proposals/modules-alvin/2_staged_modules/staged_modules.md (revision cbd6b5c66ac6688db5f91224d176d530b57dc80a) @@ -0,0 +1,236 @@ +# Staged modules + + + + + + + + + + + + + + + + + + + + + + + + +
+ Example code:
+ 		+
+module M;
+import M1;
+export struct S1 s[N];
+export struct S { int i; };
+
+ 		+
+module M1;
+import M;
+import M2;
+export struct S1 {
+    struct S arrS[2];
+    struct S2 *s2;
+};
+export const int N = 5;
+
+ 		+
+module M2;
+import M1;
+export struct S2 {
+    int i;
+    struct S1 s1;
+};
+
+
+ Stage 1:
+   Exported names
+   (file only)
+ 		+
+M
+M1
+S
+s
+
+ 		+
+M1
+M, M2
+S1
+N
+
+ 		+
+M2
+M1
+S2
+
+
+
+ Stage 2:
+   Scope resolution
+   and building a symbol table
+   (file + imports)
+ 		+
+M  -> S, s
+M1 -> S1, N
+
+ 		+
+M1 -> S1, N
+M  -> S, s
+M2 -> S2
+
+ 		+
+M2 -> S2
+M1 -> S1, N
+
+
+ Stage 3:
+   Symbol resolution in expressions
+   and resolving transitive dependencies
+   (file + transitive import closure)
+ 		+
+    S  <-\
+/-> S1 --/
+|-> N
+\-- s
+
+ 		+
+    S  <-\
+    S1 --/
+    N
+
+ 		+
+    S  <-\
+/-> S1 --/
+\-- S2
+
+
+ +## What's going on here? + +### User perspective: + +The module system runs after the preprocessor and before symbol resolution. + +To be a module, `module ;` must be the first declaration. + +`import ;` 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 — 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 — 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 — produce an error diagnostic. + +To reduce file IO, modules are lazily loaded in as symbol definitions are needed — 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.