Debian Codegraph @

doc/source/design/module-find-and-resolution.rst

raw
1 .. _module-find-and-resolution:
2
3 Module find and resolution process
4 ==================================
5
6 Description of the procedures involved in turning a module specification
7 string into either the full list of modulefiles it matches or the single
8 modulefile it designates, and of how these procedures cooperate with the
9 other mechanisms (module cache, extra match search, hiding, variants,
10 tags, aliases and symbolic versions) that can alter their result.
11
12 This document complements :ref:`module-selection-contexts`, which describes
13 *when* each context (return all matching modules / select one module) is
14 used by which sub-command. This document describes *how* these two contexts
15 are actually implemented.
16
17 Overview
18 --------
19
20 Locating modules on a modulepath directory is split across three layers,
21 from the lowest (raw filesystem/cache walk) to the highest (single module
22 selection):
23
24 * ``findModules`` (and the ``findModulesFromDirsAndFiles`` walk-down helper
25 it relies on) lists every filesystem or cache entry relevant to a search,
26 with no knowledge of aliases, symbolic versions, hiding, variants or
27 defaults.
28 * ``getModules`` consolidates this raw listing with alias, symbolic version,
29 virtual module, hiding and extra match search information, and computes
30 the default (and, if enabled, the *latest*) element of each directory. It
31 implements the :ref:`module_version_specification_to_return_all_matching_modules`
32 context.
33 * ``getPathToModule`` calls ``getModules`` for each modulepath directory (in
34 precedence order) and walks its result down to exactly one modulefile,
35 resolving aliases, symbolic versions and directory defaults as needed. It
36 implements the :ref:`module_version_specification_to_select_one_module`
37 context.
38
39 A module specification string, as typed by the user or passed by a
40 modulefile command, is parsed once beforehand by ``parseModuleSpecification``
41 (``modspec.tcl``, see :ref:`advanced-module-version-specifiers`) which stores
42 the parsed structure in the ``g_moduleVersSpec`` global array keyed by the
43 raw argument string itself. Downstream procedures keep passing around this
44 raw string as their ``mod`` argument and pull back the structured fields
45 (name, version comparator, variant list, extra specifiers, ...) through
46 accessor procedures (``getModuleNameFromVersSpec``,
47 ``getCmpSpecFromVersSpec``, ``getModuleRootFromVersSpec``, ``...``) whenever
48 needed. Passing a string never registered in ``g_moduleVersSpec`` still
49 works: accessors fall back to plain ``file dirname``/``file tail`` style
50 parsing, which is how ``getPathToModule`` and ``getModules`` can also be
51 called internally with a bare resolved module name.
52
53 ::
54
55 module load foo/1.2
56 -> parseModuleSpecification (modspec.tcl)
57 -> getPathToModule "foo/1.2" (one match, per modulepath dir)
58 -> getModules $dir "foo/1.2" ... (all matches in this dir)
59 -> findModules $dir foo ... (raw filesystem/cache listing)
60 -> resolve alias/version/directory entries until a modulefile,
61 virtual module or error is reached
62
63 Finding every matching entry: ``findModules``
64 ---------------------------------------------
65
66 ``findModules`` returns, for one modulepath directory, every element
67 (modulefile, ``.modulerc``/``.version`` file, or sub-directory) whose name
68 may be relevant to a search, without evaluating any of it beyond the module
69 header validity check (``checkValidModule``). Its result is an array
70 (flattened as a list) keyed by module-relative path, one of:
71
72 * ``{modulefile <mtime> <full-path>}``
73 * ``{modulerc}`` (a ``.modulerc`` or ``.version`` file, further processed by
74 ``getModules``)
75 * ``{invalid <msg> <full-path>}`` / ``{accesserr <msg> <full-path>}``
76
77 Sub-directories are walked down recursively by
78 ``findModulesFromDirsAndFiles``, honoring the ``ignored_dirs`` configuration
79 option and skipping backup/lock file name patterns (``*~``, ``*,v``,
80 ``#*#``, ``.modulecache``). When not in *in-depth* mode (``depthlvl`` set to
81 the query depth plus one rather than ``0``), a directory stops being
82 expanded further once a valid modulefile has already been found for it at
83 the target depth, and ``.version`` files from other depths are skipped, both
84 of which save filesystem access on directories not relevant to the query.
85
86 If a module cache file (``.modulecache``) is available and fresh for the
87 directory, ``findModulesInCacheFile`` (see :ref:`module-cache`) is used
88 instead of walking the directory, transparently to every caller of
89 ``findModules``/``getModules``/``getPathToModule``.
90
91 Results are memoized in ``g_foundModulesMemCache``, keyed by
92 ``dir:mod:depthlvl:fetch_mtime:stop_mod`` (see `Skipping sibling validation
93 on exact version resolution`_ for ``stop_mod``). A later, narrower search can
94 reuse a previously cached broader result: cache keys are matched with
95 ``string match`` so a cache entry gathered with a wildcard pattern (for
96 instance a prior full ``*`` listing of the directory) is recognized as a
97 superset covering the new, more specific query.
98
99 Consolidating and filtering: ``getModules``
100 -------------------------------------------
101
102 ``getModules`` takes a modulepath directory and a module specification and
103 returns every entry it contains that is relevant to that specification:
104 modulefiles, directories (with their computed default element), symbolic
105 versions, aliases and virtual modules, plus any hidden or erroneous element
106 that specifically matches the query. Its signature is:
107
108 .. code-block:: text
109
110 getModules dir ?mod? ?fetch_mtime? ?search? ?filter?
111
112 ``search`` is a list of flags altering search semantics:
113
114 * ``noindepth`` — restrict the search to the query's own depth level rather
115 than recursing into every matching sub-directory (used by ``avail`` and
116 ``whatis`` unless ``avail_indepth``/``spider_indepth`` is enabled).
117 * ``contains`` — substring match instead of prefix/exact match (``-C``,
118 ``--contains``).
119 * ``wild`` — the specification should be treated as a wildcard pattern.
120 * ``resolve`` — the result is gathered for a *select one module* context;
121 the only caller passing this flag is ``getPathToModule``. It enables the
122 fast path described in `Skipping sibling validation on exact version
123 resolution`_, and makes a bare directory name additionally match its
124 ``default`` symbolic version when checking whether a hidden element should
125 stay visible.
126 * ``rc_defs_included`` — also include alias and symbolic version
127 definitions coming from the global or user modulerc files.
128 * ``rc_alias_only`` — return only global/user rc aliases; no directory
129 lookup is performed at all.
130
131 ``filter`` keeps or drops entries after the search itself: ``noplaindir``
132 drops directories without any resolvable symbol (used by ``paths``),
133 ``onlydefaults``/``onlylatest`` keep only each directory's default or latest
134 element (``-d``/``-L`` options).
135
136 ``getModules`` proceeds through a fixed sequence of phases (numbered as such
137 in the source code comments):
138
139 #. **Consolidate** every kind of entry found by ``findModules`` in the
140 result array: ``.modulerc``/``.version`` files are evaluated right away
141 (unless already sourced, tracked through ``g_rcfilesSourced``, which
142 populates the ``g_moduleAlias``/``g_moduleVersion``/``g_moduleVirtual``
143 global tables), then alias, symbolic version and virtual module
144 definitions applying to this directory (or, if ``rc_defs_included`` is
145 set, to the global/user rc files) are merged in.
146 #. **Early filtering**: when the query's root name has no wildcard
147 character, entries whose root does not match it are dropped immediately,
148 before the more expensive phases below run.
149 #. **Extra match search scan**: if required by the query (see
150 :ref:`extra-match-search`), every modulefile/virtual module entry still
151 in the result is evaluated in ``scan`` mode to gather its variant, tag and
152 extra specifier content; provided aliases are inserted into the result if
153 requested.
154 #. **Filter out dynamically hidden or expired elements**: entries hidden by
155 :ref:`hide-or-forbid-modulefile` rules are dropped, unless the query
156 specifically targets them (or one of their symbols); a *forbidden* entry
157 that is specifically targeted is turned into an ``accesserr`` entry
158 instead of being silently dropped.
159 #. **Elaborate directory content and select each directory's default
160 element**: an explicit default (an entry named ``default`` resolving
161 through a symbolic version) takes precedence; otherwise, if
162 :mconfig:`implicit_default` is enabled, the dictionary-highest remaining
163 sibling is used (see :ref:`default-latest-version-specifiers` and
164 :ref:`extended-default`). If :mconfig:`advanced_version_spec` and
165 :mconfig:`implicit_default` are both enabled and the query is not a
166 variant-only wildcard, this is also where the ``default``/``latest``
167 *auto symbols* are synthesized for every directory the query's root name
168 applies to, through ``setModuleResolution``.
169 #. **Extra match search filtering**: entries not matching the variant, tag
170 or extra specifier criteria collected in phase 3 are withdrawn, cascading
171 to any symbolic version (including an auto symbol) pointing at a
172 withdrawn entry.
173 #. **Filter results down to the search query**: entries not matching the
174 query's name/version/depth are dropped, directories are re-elaborated
175 against the filtered set (so a directory's default may change if its
176 previous default got filtered out), *no-indepth* mode trims anything
177 deeper than the query, and the ``filter`` argument's ``onlydefaults``/
178 ``onlylatest``/``noplaindir`` keep-list is applied.
179 #. **Consolidate tags**: for ``avail``/``spider`` only, and once per
180 modulepath directory, every retained modulefile/alias/virtual module has
181 its applicable tags collected (see :ref:`module-tags`) ahead of listing.
182
183 The result (an array, flattened as a list, of the same entry-kind shapes as
184 ``findModules``, plus ``version``/``alias``/``virtual`` kinds) is memoized in
185 ``g_gotModulesMemCache``, keyed by ``dir:mod:fetch_mtime:search:filter``.
186
187 Selecting one module: ``getPathToModule``
188 -----------------------------------------
189
190 ``getPathToModule`` resolves a specification down to a single modulefile.
191 Its signature is:
192
193 .. code-block:: text
194
195 getPathToModule mod ?indir? ?report_issue? ?look_loaded? ?excdir?
196
197 * ``indir`` restricts the search to a given list of directories instead of
198 the full enabled modulepath list.
199 * ``report_issue`` controls whether a resolution failure is reported through
200 ``reportIssue`` directly by this procedure, or left for the caller to
201 handle (several sub-commands pass ``0`` and produce their own message).
202 * ``look_loaded`` (``no``/``exact``/``match``/``close``), when not ``no``,
203 resolves against already-*loaded* modules instead of the filesystem
204 (``getLoadedExactName``/``getLoadedEqstartName``/``getLoadedWithClosestName``
205 respectively), used to resolve a single-name argument to ``unload`` or
206 ``switch``. A non-match in this mode is a ``notloaded`` result and is
207 never reported as an issue, even when ``report_issue`` is set.
208 * ``excdir`` lists directories to skip, used by ``switch`` to continue a
209 search in the directories not already covered by a prior call.
210
211 Three cases are handled before any modulepath search happens: an empty
212 ``mod`` is an immediate error; a ``look_loaded`` request is resolved as
213 above; and a full pathname (matching ``^(|\.|\.\.)/``, i.e. starting with
214 ``/``, ``./`` or ``../``) bypasses modulepath search entirely — only
215 ``checkValidModule`` is applied to the literal file, and the module name
216 *is* the path. No modulerc-based hiding or forbidding applies in this case
217 except through a *global* rc file (see :ref:`hide-or-forbid-modulefile`).
218
219 Otherwise, for each candidate directory in modulepath precedence order
220 (minus ``excdir``):
221
222 #. ``getModules`` is called with the ``resolve`` search flag (the only call
223 site using it in the whole codebase), returning every entry in this
224 directory relevant to the query.
225 #. The looked-up key is resolved against the result array
226 (``getEqArrayKey``, case-insensitive- and implicit-default-aware), then
227 handled according to its entry kind:
228
229 * ``alias``/``version`` — resolved through ``resolveModuleVersionOrAlias``.
230 If the target is present in the same directory's result, the walk
231 continues in place; otherwise a full new call to ``getPathToModule`` is
232 made on the resolved name (any variant collected so far is folded into
233 it first). This recursive call only forwards ``indir`` and
234 ``report_issue``; it does not carry over ``excdir`` or ``look_loaded``.
235 * ``directory`` — the walk moves to the directory's computed default
236 element; with no default available (:mconfig:`implicit_default`
237 disabled and no explicit default set), resolution fails with *"No
238 default version defined for '...'"*. If the default element turns out
239 to be a hidden sub-directory not present in the current result, a new
240 ``getPathToModule`` call is made on it (same recursion rules as above).
241 * ``modulefile`` — resolution is complete; the modulefile's path is
242 returned.
243 * ``virtual`` — resolution is complete; the virtual module's target file
244 is returned, with the virtual module's own name kept as the reported
245 module name.
246 * ``invalid``/``accesserr`` — resolution ends in error.
247
248 The per-directory loop stops as soon as **anything** is found for the
249 query in the current directory — including an error — so a later
250 modulepath directory holding a valid module of the same name is never
251 reached if an earlier directory already produced an invalid or
252 inaccessible match.
253
254 Once a candidate (successful or not) is found, or every directory has been
255 tried without any match, the specified variant (if any) is attached to the
256 resolved module name, and the *forbidden* tag is checked one final time
257 against the fully resolved target — catching a target reached indirectly
258 through an alias or a directory default, since resolving through those does
259 not itself carry forbidden status (see :ref:`hide-or-forbid-modulefile`).
260
261 Skipping sibling validation on exact version resolution
262 -------------------------------------------------------
263
264 Resolving an exact ``name/version`` specification (as done for instance by
265 ``load``) still requires computing the queried directory's default/latest
266 element, in order to determine whether the resolved module should carry the
267 ``default``/``latest`` alternate names (see
268 :ref:`default-latest-version-specifiers`). Naively, this means validating
269 (``checkValidModule``) and hidden-testing every sibling in that directory,
270 even though only the queried version and, at most, the true highest sibling
271 are actually needed to answer both questions at once. On directories with
272 hundreds or thousands of versions of the same module, this dominates
273 resolution time on an otherwise uncached modulepath.
274
275 ``getModules`` computes a ``stop_mod`` value — set to the query's
276 ``name/version`` — whenever all of the following hold, i.e. the query is
277 resolved in a single-module context and cannot itself be satisfied by
278 several different directory elements:
279
280 * the ``resolve`` search flag is set (so, only when called from
281 ``getPathToModule``);
282 * the query's root name has no wildcard character;
283 * no ``filter`` (``onlydefaults``/``onlylatest``/``noplaindir``) applies;
284 * the query's version comparator is a plain equality (not a range or list);
285 * the query is a flat, single-depth ``name/version`` (not e.g.
286 ``name/sub/version``).
287
288 In any other case ``stop_mod`` is left empty and every procedure below
289 behaves exactly as if the optimization did not exist — it never changes
290 what is returned, only how much sibling validation is performed to get
291 there. Listing sub-commands (``avail``, ``whatis``, ``search``, ...) and
292 bare module name resolution are always unaffected.
293
294 ``stop_mod`` is threaded through ``findModules`` into
295 ``findModulesFromDirsAndFiles``, which hands it, together with the directory
296 currently being walked, to ``trimElemListForStopmod`` right before that
297 directory's raw element list is folded into the overall search. This helper
298 only ever activates for the one directory that is ``stop_mod``'s own parent,
299 and only if ``stop_mod`` itself exists there and is a valid modulefile —
300 in any other case it leaves the element list untouched. When it does
301 activate, it:
302
303 * keeps ``.modulerc``/``.version`` files untouched, letting ``getModules``'s
304 normal consolidation phase process them as usual;
305 * proactively sources the modulepath-root ``.modulerc`` and then this
306 directory's own ``.modulerc``/``.version`` right away (guarded by the same
307 ``g_rcfilesSourced`` tracking used later on, to avoid sourcing them
308 twice), since a hiding rule set by either of them may affect which sibling
309 actually qualifies as the true default/latest;
310 * dictionary-sorts the directory's plain elements and walks down from the
311 highest one to ``stop_mod``'s own position, stopping at the first sibling
312 that is itself a valid, non-hidden modulefile — that sibling (or
313 ``stop_mod`` itself, if nothing higher qualifies) is this directory's true
314 implicit default/latest;
315 * if any element visited along that walk is itself a sub-directory (a
316 deeper version layout), the optimization gives up for this directory and
317 the full, unmodified element list is used instead;
318 * keeps only ``stop_mod``'s own element and, if one was found above it, that
319 one qualifying higher element — every other sibling is dropped from what
320 gets validated and returned.
321
322 A module cache file (``.modulecache``) is read as a single, whole-file I/O
323 operation regardless of query shape (see :ref:`module-cache`), so
324 ``findModulesInCacheFile`` has no ``stop_mod`` awareness: this optimization
325 only benefits directories walked live on the filesystem, which is precisely
326 the case a cache file is meant to avoid in the first place.
327
328 Result caching
329 --------------
330
331 Both ``findModules`` and ``getModules`` memoize their results for the
332 lifetime of the current ``module`` invocation, in ``g_foundModulesMemCache``
333 and ``g_gotModulesMemCache`` respectively, each keyed by a string compacting
334 every argument that affects the result (directory, specification, depth
335 level, and the relevant flags — including ``stop_mod`` for the former).
336 Repeated resolution of the same or a related specification against the same
337 directory — for instance while ``getPathToModule`` walks through an alias or
338 a directory default — reuses these cached results instead of re-walking the
339 filesystem or re-evaluating modulerc files.
340
341 See also
342 --------
343
344 The following existing design documents cover behaviors that interact with
345 module find and resolution but are not restated here:
346
347 * :ref:`module-selection-contexts` — the four contexts a module
348 specification can be resolved in, and which sub-command uses which.
349 * :ref:`advanced-module-version-specifiers` — the ``@``-based specification
350 grammar (ranges, lists, variants) parsed ahead of ``getModules``/
351 ``getPathToModule``.
352 * :ref:`default-latest-version-specifiers` — explicit vs. implicit default,
353 the ``latest`` specifier, and the auto symbol mechanism computed in
354 ``getModules``' fifth phase.
355 * :ref:`extended-default` — partial version matching against a directory's
356 siblings.
357 * :ref:`insensitive-case` — case-insensitive matching and its tie-break
358 rules.
359 * :ref:`extra-match-search` — variant, tag and extra specifier filtering
360 performed as part of ``getModules``' third and sixth phases.
361 * :ref:`hide-or-forbid-modulefile` — hiding levels and forbidding, applied
362 in ``getModules``' fourth phase and re-checked by ``getPathToModule``.
363 * :ref:`module-cache` — the ``.modulecache`` file format and how it
364 transparently replaces the directory walk performed by ``findModules``.
365 * :ref:`variants` — variant specification grammar and comparison rules.
366 * :ref:`module-tags` — the tag mechanism used by hiding, forbidding and
367 extra match search alike.
368
369 .. vim:set tabstop=2 shiftwidth=2 expandtab autoindent: