Add the concept of "collection" to the compiler and remove the concept of "in-order AST nodes"

[emilyaherbert]

The Problem

Currently, the Sway compiler relies heavily on the concept of the AST nodes being ordered “correctly” in order to perform successful compilation. Out of this comes the additional requirement that dependencies be ordered correctly in a Sway project. The burden of deciding the “correct AST node ordering” is not placed on the user, but on the compiler. Currently, the compiler performs a pass before type checking to determine the correct order in which to type check the AST nodes.

Mathematically, this places restrictions on the dependency structure of a Sway project. Currently, Sway projects must be directed acyclic graphs (a tree).

This creates fundamental issues:

• Mutually recursive dependencies are not currently supported, and would not ever be able to be supported without extensive special-casing.
• Mutually recursive AST nodes within the same file are not currently supported, and would not ever be able to be supported without extensive special-casing.
• This inhibits the introduction of recursive functions, recursive trait methods, recursive struct and enum declarations, and more.
• If a user forgets to import a dependency, it is not possible to suggest an import to them without extensive special-casing.

The Solution

The order of AST nodes should not be a factor of importance inside the compiler. I propose that we shift the way that the compiler thinks about AST node ordering, and eliminate the concept of “correct AST node ordering.” This will mean that the order of AST nodes during type-checking will no longer have any effect on the output of the compiler.

This will open up Sway to a new domain of applications, as it would allow Sway projects to be directed cyclic graphs. (two direct mutually recursive dependencies are considered a 1-hop cycle)

I propose these new high-level compiler steps:

1. Parse all files in a Sway project.
2. Perform a “collection pass” on the untyped parsed AST and gather information about all of the AST nodes, without type checking. This will generate a “collection environment” containing key information about the AST nodes.
3. Perform type checking using the “collection environment,” allowing every AST node to have knowledge of the existence of every other AST node. This step will require us to introduce the concepts of a “declaration engine” that will operate similarly to the existing type engine. The declaration engine will work with the collection context to allow AST nodes to undergo type checking, without the need for dummy declarations, multiple passes, or substitutions. Additionally, the introduction of the declaration engine supports the introduction of other Sway features which are currently open on GitHub.
4. Generate IR and do codegen

The Roadmap

The implementation steps are (roughly) as follows in order:

• Parse all modules in a project before beginning the type-checking stage #1578
• Provide a "context" to the type-check phase with the aim of improving ergonomics #1810
• Add a declaration engine #1692
• Introduce a monomorphization cache #2636
• Add the collection context #1693
• Restructure how functions are handled in the IR and codegen to eliminate function inlining #1823
• remove dead code (the node dependencies code, etc)

The original proposal is here: https://docs.google.com/document/d/1kwOk08-Ot7n2RCYCWNNtFCfQAxtlYN-DFHk2sxK139E/edit#

[kayagokalp]

@tritao I was doing a little clean-up and realized this issue is marked as done in compiler board but still open. Is this issue still relevant?

[tritao]

The semantic analysis part is done, I didn't close this due to not being sure about #1823.

Perhaps @ironcev or @vaivaswatha can chime in if that's something that's still needed or if we can close it as well.

[ironcev]

#1823 discusses the very first IR generation that didn't have function calls but was inlining everything and proposes what we do have now, in the IR and in ASM generation, calls and jumps respectively. So I've closed it.