Module linker 

Assembly of a Miden Assembly project is comprised of four phases:

1. Parsing, where MASM sources are parsed into the AST data structure. Some light validation is done in this phase, to catch invalid syntax, invalid immediate values (e.g. overflow), and other simple checks that require little to no reasoning about surrounding context.
2. Semantic analysis, where initial validation of the AST is performed. This step catches unused imports, references to undefined local symbols, orphaned doc comments, and other checks that only require minimal module-local context. Initial symbol resolution is performed here based on module-local context, as well as constant folding of expressions that can be resolved locally. Symbols which refer to external items are unable to be fully processed as part of this phase, and is instead left to the linking phase.
3. Linking, the most critical phase of compilation. During this phase, the assembler has the full compilation graph available to it, and so this is where inter-module symbol references are finally able to be resolved (or not, in which case appropriate errors are raised). This is the phase where we catch cyclic references, references to undefined symbols, references to non-public symbols from other modules, etc. Once all symbols are linked, the assembler is free to compile all of the procedures to MAST, and generate a crate::Library.
4. Assembly, the final phase, where all of the linked items provided to the assembler are lowered to MAST, or to their final representations in the crate::Library produced as the output of assembly. During this phase, it is expected that the compilation graph has been validated by the linker, and we’re simply processing the conversion to MAST.

This module provides the implementation of the linker and its associated data structures. There are three primary parts:

1. The call graph, this is what tracks dependencies between procedures in the compilation graph, and is used to ensure that all procedure references can be resolved to a MAST root during final assembly.
2. The symbol resolver, this is what is responsible for computing symbol resolutions using context-sensitive details about how a symbol is referenced. This context sensitivity is how we are able to provide better diagnostics when invalid references are found. The resolver shares part of it’s implementation with the same infrastructure used for symbol resolution that is performed during semantic analysis - the difference is that at link-time, we are stricter about what happens when a symbol cannot be resolved correctly.
3. A set of rewrites, applied to symbols/modules at link-time, which rewrite the AST so that all symbol references and constant expressions are fully resolved/folded. This is where any final issues are discovered, and the AST is prepared for lowering to MAST.

Structs

CallGraph

A CallGraph is a directed, acyclic graph which represents all of the edges between procedures formed by a caller/callee relationship.

CycleError

Represents the inability to construct a topological ordering of the nodes in a CallGraph due to a cycle in the graph, which can happen due to recursion.

LinkLibrary

Represents an assembled module or modules to use when resolving references while linking, as well as the method by which referenced symbols will be linked into the assembled MAST.

Linker

The Linker is responsible for analyzing the input modules and libraries provided to the assembler, and linking them together.

ResolverCache

A ResolverCache is used to cache resolutions of type and constant expressions to concrete values that contain no references to other symbols. Since these resolutions can be expensive to compute, and often represent items which are referenced multiple times, we cache them to avoid recomputing the same information over and over again.

Symbol

A Symbol is a named, linkable item defined within a module.

SymbolResolutionContext

Represents the context in which symbols should be resolved.

SymbolResolver

A SymbolResolver is used to resolve a procedure invocation target to its concrete definition.

Enums

LinkLibraryKind

Represents how a library should be linked into the assembled MAST

LinkStatus

Represents the current status of a symbol in the state of the Linker

LinkerError

An error which can be generated while linking modules and resolving procedure references.

SymbolItem

A SymbolItem represents the type of item associated with a Symbol.