LEP-002: Import Resolution


Created:Thursday, May 5, 2022
Author:David Delassus
Category:Compiler Architecture
Status:FINAL

Abstract

This LEP specifies how the Letlang import system works, how dependencies are resolved during compilation, and the Rust code that is produced by the import statement.

Rationale

As specified in the LEP-001[1], the Letlang’s compilation unit is the module. Each module produce a Rust[2] library crate.

In order to link those crates together in a final executable, the Letlang compiler must keep track of the dependency graph and ensure that there is no circular dependencies.

Specification

Naming Convention

Every Letlang module must have a unique name. This name can be composed of multiple parts separated by dots (.). Each part is composed of lowercase letters and numbers and must start with a letter.

Examples:

  • foo.bar.baz will be compiled to libllmod_foo_bar_baz.rlib
  • encoding.rot13 will be compiled to libllmod_encoding_rot13.rlib

NB: There is no special meaning to the dots in the name, the developer can use them to indicate a module hierarchy.

Module definition

A module is defined by a .let file and the module statement (which must comes before all other statements):

module "foo.bar.baz";

# ...

Dependency graph resolution

Once Letlang modules has been parsed into an Abstract Syntax Tree, the compiler starts the semantic validation of this tree. During this phase, the compiler produce the list of crates that will be generated from those modules.

Once the complete list have been computed, the compiler organizes them into a graph based on the import statements found in each module.

If an import statement references an unknown module, a compilation error is thrown, and the compiler aborts.

Once the graph has been computed, the compiler looks for cycles in the graph. If such cycles are found, a compilation error is thrown, and the compiler aborts.

This graph is a directed graph where:

  • each node of the graph represent a crate
  • each edge of the graph represent a dependency relation (from the crate to its dependency)
graph LR; A --> B; A --> C; B --> D; C --> D;

Compilation order

The dependency graph indicates the order in which Letlang modules must be compiled:

  1. nodes without edges starting from it are compiled first
  2. once compiled, the nodes are removed from the graph
  3. if the graph is not empty, repeat from step 1

Example:

Step 1:
graph LR; A --> B; A --> C; B --> D; C --> D; style A fill:#48C78E;
Step 2:
graph LR; B --> D; C --> D; style B fill:#48C78E; style C fill:#48C78E;
Step 3:
graph LR; D; style D fill:#48C78E;

Import syntax and code output

Dependencies are defined by import statements:

import "foo.bar.baz";

This will add the namespace baz into the current module.

Example:

import "std";

func main() -> @ok {
  std.print("hello world");
  @ok;
}

Imports can be aliased:

import "foo.bar.baz" as "foo";

NB: Aliases must contain only letters and numbers and must start with a letter.

The resulting Rust code is:

// import "foo.bar.baz";
extern crate llmod_foo_bar_baz;
use llmod_foo_bar_baz as baz;

Or if aliased:

// import "foo.bar.baz" as "foo";
extern crate llmod_foo_bar_baz;
use llmod_foo_bar_baz as foo;

Module discovery

By default, the compiler will look for Letlang modules in the src folder relative to the project’s root. Other folders can be included, for example:

  • ./vendor/ or ./deps/: for dependencies
  • /usr/lib/letlang: for the standard library (on Linux)

This is done by passing the -I path option to the compiler.

Rejected Ideas

Filesystem based modules

Python[3] and Javascript[4] both use the filename as a basis for module discovery:

from foo.bar import baz
# Expects:
# |-+ foo/
#   |-- __init__.py
#   |-+ bar/
#     |-- __init__.py
#     |-- baz.py
const baz = require("./foo/bar/baz.js")

Decoupling the directory structure from the module definition gives more liberty to the developer regarding code organization.

Multiple modules per file

Elixir[5] also decouple the directory structure from module definition. But it also allow multiple modules per file:

defmodule Foo do
  # ...
end

defmodule Bar do
  # ...
end

It also supports nesting modules.

This can drasticly increase the complexity of a single source file as well as the compiler architure.

Letlang choose simplicity: one file equals one module.

Circular imports

Opinion: Circular imports are generally a bad idea that can lead to spaghetti code.

Hexagonal architecture[6] with clearly defined boundaries should be the preferred way of doing things.

It is also, at the moment, unclear in which order should compilation happen for circular imports.

References

ReferenceTitleLink
1LEP-001: Language Target/lep/001/
2Rusthttps://www.rust-lang.org/
3Pythonhttps://www.python.org/
4Javascripthttps://en.wikipedia.org/wiki/JavaScript
5Elixirhttps://elixir-lang.org
6Hexagonal Architecturehttps://en.wikipedia.org/wiki/Hexagonal_architecture_(software)