Module Resolution

Recall that import targets are specified by their local names only. It is perfectly legal that there should be many discoverable modules that share the same local name. Yet it is essential that an import target should be unambiguously understood, lest the wrong module be selected to satisfy an import.

Module resolution is the process by which import targets are resolved to concrete modules. Intuitively, and in brief, module resolution proceeds as follows:

• If the import target is in the same directory as the dependent module, then choose it.
• Otherwise, look in the enclosing directory. If the import target is there, then choose it.
• Keep looking upward through the enclosing directories until reaching a module root. If the import target is discovered along the way, then choose it.
• If the import target is directly inside the same module root as recursively includes the dependent module, then choose it.
• Otherwise, scan through all the module roots in the order that they were provided in the module roots path. Only look directly, not recursively, in each module root. If the import target is found, then choose it.
• If the import target was found, but it refers to a package, then reach inside and choose the representative.
• If the import target couldn't be found, then fail the module resolution process.

Understanding the procedure at the abbreviated level of detail given above is adequate for the vast majority of use cases. It should generally prove safe to skip ahead to the conclusion and example.

Following is a detailed description of the module resolution algorithm: ^[1]

Canonize the import target.

Module resolution begins by naively canonizing the import target — specified by the local name L — as if it were a sibling of the dependent module. A file is sibling to another if they both reside in the same file system directory. Let us call this naive canonical name M.

Is there an applicable rename rule?

Does the module renames file specify a module rename rule that would transform M into the canonical name M′? If so, then apply the rename rule. If not, then go ahead with translating the canonical name to a file system path.

Apply the rename rule.

Apply the module rename rule to transform M into the canonical name M′.

Translate the canonical name into a file path.

Consider the expansion of the canonical name M (or M′ if a module rename rule was applied),

M ≝ /R/P1/P2/…/Pn/L,

where R is a module root name, P1 through Pn are local names of packages, and L is the local name of the import target. To translate M to a file path,

• Replace R with its source module path, denoted by S.
• Rewrite P1 as P1.avail.
• Rewrite P2 as P2.avail.
• …
• Rewrite Pn as Pn.avail.
• Rewrite L as L.avail.
• Replace each occurrence of solidus / (U+002F) with the platform-specific directory separator. (On Unix this will be solidus; on Windows, reverse solidus \ (U+005C).)

Let us call the result of this translation F, whose expansion is

F ≝ /S/P1.avail/P2.avail/…/Pn.avail/L.avail.

Does the file path contain any packages?

F may not include any packages (either because it never included any or because they have all been rejected and removed), so check to see if it does. If so, then see if it references an existing file. If not, then L.avail resides directly within a root.

The file path contains packages, but does it exist?

F (or F′, F″, …, if some packages have already been dropped) includes at least one package, Pi,

F′ ≝ /S/…/Pi.avail/L.avail.

Does F denote an existing file? If so, then determine whether F is a package. If not, then drop Pn.

Drop the rightmost package from the file path.

Derive F′ from F by dropping the rightmost package, Pn. The expansion of F′ is therefore

F′ ≝ /S/P1.avail/P2.avail/…/Pn-1.avail/L.avail.

Now see if F′ includes any packages.

The file path contains no packages. Does it exist?

Since F does not contains any local names that correspond to packages, the expansion of F is given by

F ≝ /S/L.avail.

Does F denote an existing file? If so, then determine whether F is a package. If not, then determine whether there are any unexplored module roots.

Are some module roots still unexplored?

With respect to the resolution of M, are some module roots specified on the module root path still unexplored? If so, then replace S with S′. If not, then module resolution has failed; the system will emit an appropriate error message and then halt.

Try the next unexplored module root.

Recall that the module roots path is the list of all module roots that participate in module discovery. The module roots are necessarily ordered, because all text is ordered. Derive S′ by choosing the leftmost module root from the module roots path that has not already been searched. Then derive F′ such that

F ≝ /S′/L.avail.

Now determine whether F′ exists.

Does the file path refer to a package?

Does F refer to a directory rather than a file? If so, then F refers to a package, so derive F′ from F such that

F′ ≝ /S/P1/P2/…/Pn/L.avail/L.avail,

and verify that its representative exists. If not, then module resolution has succeeded: F is the unambiguous resolution of M.

The file path refers to a package representative, but does it exist?

F denotes a package representative. Does F exists? If so, then module resolution has succeeded: F is the unambiguous resolution of M. If not, then module resolution has failed; the system will emit an appropriate error message and then halt.

An extremely important practical consequence of this procedure is that the contents of a package are always impenetrable to a module that resides outside of that package. This ensures that a module representative is the exclusive gateway to services offered by modules located recursively within its package. This is an essential concept of Avail's encapsulation model.

Take Wump the Wumpus, one of the official Avail case studies available in the examples module root, as the scaffolding for some use cases of module resolution:

Entries beginning with a solidus denote ordinary directories, and just serve to give context to the module roots. Entries encased in plus signs + (U+002B) denote module roots; assume that the two shown here, avail and examples, are the only ones specified by the module roots path, and that the occur in the order given. Entries ending with a solidus denote module packages. Entries ending with an asterisk * (U+002A) denote module package representatives. All other entries are ordinary modules. Assume that the module renames file is empty.

Peering into /examples/Wump the Wumpus/Game/Command/Parser, we find this module header:

Let us consider each of the import targets in turn.

1. Of course, we already know that Avail is the standard library. But the system doesn't know it immediately when it encounters this import target. It just knows that it should try to resolve the local name Avail to an actual module. It starts by canonizing the name to:
   /examples/Wump the Wumpus/Game/Command/Avail
   It then translates this canonical name to the following file path:
   /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Command.avail/Avail.avail
   It then recursively scans the enclosing directories, from the inside out, looking for a file name Avail.avail:
   /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Command.avail/Avail.avail /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Avail.avail /usr/local/avail/src/examples/Wump the Wumpus.avail/Avail.avail /usr/local/avail/src/examples/Avail.avail
   Having exhausted the examples module root, it next rewrites the file path to be relative to the leftmost unexplored module root, avail:
   /usr/local/avail/src/avail/Avail.avail
   This file path refers to a package, so append the name of the package representative, Avail.avail. The local name Avail is ultimately resolved to /usr/local/avail/src/avail/Avail.avail/Avail.avail.
2. The local name Definers is canonized to:
   /examples/Wump the Wumpus/Game/Command/Definers
   And then translated to the file path:
   /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Command.avail/Definers.avail
   This file exists — it is sitting right beside Parser.avail — so resolution succeeds.
3. To find IO, the system tries the following file paths:
   /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Command.avail/IO.avail /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/IO.avail /usr/local/avail/src/examples/Wump the Wumpus.avail/IO.avail
   This file exists, so resolution succeeds.
4. Finally, Scanner is trivially resolved to:
   /usr/local/avail/src/examples/Wump the Wumpus.avail/Game.avail/Command.avail/Scanner.avail

[1] Technically, the system is only guaranteed to carry out an algorithm that is behaviorally isomorphic to this one: it is guaranteed that module resolution produces only results that are consistent with the description of the algorithm provided here. The implementation may actually use different techniques, generally because they are more efficient.