module_diagrams.py

#!/usr/bin/env python3
"""Draws the module diagrams of the nvx crate, which doc/modules publishes.

cargo-modules exports the modules of the crate's library, with its cli, testing,
and guest features, as each of the crate's platforms, Linux and Windows, builds
it: the module that contains each module, and the modules that each uses. It
mistakes modules under some cfg conditions, such as cfg(not(windows)), for test
modules, so this script also reads its analysis with cfg(test), and restores
them. It merges the exports of the platforms, draws with Graphviz the crate's
top-level modules, the dependencies between them, and the modules that each
contains, and writes the page that shows the diagrams. CI draws them after every
merge to dev that changes their inputs, and commits them when they change
(doc/ci.md, "Module diagrams").
"""

from __future__ import annotations

import argparse
import os
import re
import shlex
import shutil
import subprocess
import sys
import textwrap
import xml.etree.ElementTree as ET
from collections import Counter
from collections.abc import Callable, Iterable, Mapping, Sequence
from dataclasses import dataclass
from itertools import pairwise
from pathlib import Path

from nvx_tools.build_constants import (
    BuildConstants,
    GuestRustBuildConstants,
    OpenVMMBuildConstants,
)

REPOSITORY = BuildConstants.REPO_ROOT
MANIFEST = GuestRustBuildConstants.DIRECTORY / "Cargo.toml"
# CI draws into doc/modules, which it commits. A local run draws beside the build
# products by default, so that it leaves the published diagrams to CI.
DEFAULT_OUTPUT = BuildConstants.BUILD_DIR / "modules"
PAGE = "README.md"
# The first line of the page, by which a run knows the output of an earlier one.
MARKER = "<!-- Generated by scripts/module_diagrams.py; do not edit. -->"
CRATE = "nvx"
FEATURES = ("cli", "testing", "guest")
# The platforms that the diagrams cover, with the target that each builds: on
# Linux, the guests' target, for which the guest module builds.
TARGETS = {
    "Linux": GuestRustBuildConstants.TARGET,
    "Windows": OpenVMMBuildConstants.WINDOWS_RUST_TARGET,
}
# The cargo-modules release to install. It builds with the Rust release that
# rust-toolchain.toml pins.
CARGO_MODULES_VERSION = "0.27.0"

# The fill and border colors of the crate root and of each part of the crate.
COLORS = {
    CRATE: ("#14283f", "#14283f"),
    "core": ("#e0f2fe", "#0284c7"),
    "host": ("#ede9fe", "#8b5cf6"),
    "guest": ("#ccfbf1", "#0d9488"),
    "testing": ("#fef3c7", "#d97706"),
}
# What each top-level module holds, in the overview.
DESCRIPTIONS = {
    "activation": "Layered root activation",
    "contract": "Control compatibility",
    "error": "Error types",
    "exec": "Execution stdio and credit",
    "gpt": "GPT partition reader",
    "guest": "Linux guest programs",
    "host": "Launch and supervision",
    "hypervisor": "Backend selection",
    "net": "IP networks",
    "protocol": "NVXS / NVXC codecs",
    "testing": "Fake OpenVMM",
    "uuid": "UUID encoding",
}
# Graphviz measures the labels with the first of these fonts that is installed,
# and SVG viewers show them with the first that they have. CI installs
# Liberation Sans, so that its layouts do not depend on the other fonts of its
# runner, and Arial and Helvetica have the same metrics.
FONT = "Liberation Sans,Arial,Helvetica,sans-serif"
HEADER = (
    'graph [rankdir=LR, bgcolor="white", pad=0.25, nodesep=0.22, ranksep=0.65,'
    f' splines=true, outputorder=edgesfirst, fontname="{FONT}"];',
    f'node [shape=box, style="rounded,filled", fontname="{FONT}", fontsize=13,'
    ' margin="0.16,0.11", penwidth=1.2];',
    f'edge [color="#a8b8ca", arrowsize=0.65, fontname="{FONT}", fontsize=10,'
    ' fontcolor="#52677d"];',
)
# The top-level modules in each row of the overview.
ROW = 4
# The visibilities that a box shows with its border alone: solid if public,
# dashed if private. A box names any other visibility, such as pub(crate).
PUBLIC = ("crate", "pub")
PRIVATE = "pub(self)"
# The width of the page's lines.
WIDTH = 79

# cargo-modules writes one statement per line, and ends each with a comment that
# names the kind of node or edge that it draws.
STATEMENT = re.compile(r'// "[^"]*" (?:node|edge)$', re.M)
NODE = re.compile(
    r'^ *"(?P<path>[^"]+)" \[label="(?P<kind>[^|"]*)\|[^"]*"[^\n]*'
    r'// "(?P<type>crate|mod)" node$',
    re.M,
)
EDGE = re.compile(
    r'^ *"(?P<user>[^"]+)" -> "(?P<used>[^"]+)" [^\n]*'
    r'// "(?P<type>owns|uses)" edge$',
    re.M,
)
# cargo-modules' structure writes the crate, then one module a line, four columns
# deeper than the module that contains it, with its visibility and the cfg
# conditions that must all hold for it.
TREE = re.compile(
    r"^(?P<indent>(?:│   |    )*)[├└]── mod (?P<name>[\w#]+): (?P<rest>.*)$"
)
CONDITION = re.compile(r"#\[cfg\((?P<condition>.+?)\)\](?=, #\[cfg\(|$)")


class DiagramError(Exception):
    """A failure to export, merge, or draw the modules."""


@dataclass(frozen=True)
class Output:
    """What a command wrote."""

    stdout: str
    stderr: str


# Runs a command, with the text for its standard input, if any, and returns its
# output; it fails with a DiagramError if the command fails.
Runner = Callable[[Sequence[str], str | None], Output]


@dataclass(frozen=True)
class Export:
    """The modules of the crate that one platform builds, as cargo-modules
    exports them: the visibility of each, by path, the module that contains each
    module but the crate root, and the pairs of modules in which the first uses
    the second."""

    visibility: dict[str, str]
    owner: dict[str, str]
    uses: frozenset[tuple[str, str]]


@dataclass(frozen=True)
class Module:
    """A module that any platform builds: its visibility, and the platforms that
    build it."""

    visibility: str
    platforms: frozenset[str]


@dataclass(frozen=True)
class Crate:
    """The modules that any platform builds, by path, the module that contains
    each module but the crate root, and the pairs of modules in which the first
    uses the second, with the platforms that build each pair."""

    platforms: tuple[str, ...]
    modules: dict[str, Module]
    owner: dict[str, str]
    uses: dict[tuple[str, str], frozenset[str]]

    def roots(self) -> list[str]:
        """The top-level modules."""
        return sorted(path for path, owner in self.owner.items() if owner == CRATE)

    def subtree(self, root: str) -> list[str]:
        """The module and every module that it contains."""
        return sorted(
            path
            for path in self.modules
            if path == root or path.startswith(root + "::")
        )

    def only(self, path: str) -> str | None:
        """The platforms that alone build a module that every platform would
        otherwise build, as its owner is common to all: the outermost module of
        those that only these platforms build. None for every other module."""
        platforms = self.modules[path].platforms
        owner = self.owner.get(path)
        if len(platforms) == len(self.platforms) or (
            owner is not None
            and len(self.modules[owner].platforms) != len(self.platforms)
        ):
            return None
        return " and ".join(name for name in self.platforms if name in platforms)


@dataclass(frozen=True)
class Diagram:
    """A diagram of the page: the file that holds it, its title, what it shows,
    and its Graphviz source. A hierarchy names its top-level module, and the
    page says what it shows."""

    name: str
    title: str
    text: str
    source: str
    root: str | None = None


def run(command: Sequence[str], stdin: str | None = None) -> Output:
    """Runs a command in the repository, without terminal colors."""
    try:
        result = subprocess.run(
            list(command),
            cwd=REPOSITORY,
            input=stdin,
            capture_output=True,
            encoding="utf-8",
            env={**os.environ, "NO_COLOR": "1"},
            check=False,
        )
    except OSError as error:
        raise DiagramError(f"{shlex.join(command)} failed: {error}") from error
    if result.returncode != 0:
        raise DiagramError(
            f"{shlex.join(command)} failed with exit status {result.returncode}:"
            f" {result.stderr.strip()}"
        )
    return Output(result.stdout, result.stderr)


def warn(output: Output) -> str:
    """Repeats the warnings that a command wrote and returns its standard
    output."""
    if output.stderr.strip():
        print(output.stderr.strip(), file=sys.stderr)
    return output.stdout


def export_command(target: str, *, cfg_test: bool = False) -> list[str]:
    """The cargo-modules command that exports the modules of one target, without
    the functions, types, and traits that they hold or other crates, and with the
    test modules if cfg_test."""
    return [
        "cargo",
        "modules",
        "dependencies",
        "--lib",
        "--manifest-path",
        str(MANIFEST),
        "--features",
        ",".join(FEATURES),
        "--target",
        target,
        "--no-fns",
        "--no-traits",
        "--no-types",
        "--no-externs",
        "--no-sysroot",
        *(["--cfg-test"] if cfg_test else []),
    ]


def structure_command(target: str) -> list[str]:
    """The cargo-modules command that writes the modules of one target, with the
    test modules, and the cfg conditions of each."""
    return [
        "cargo",
        "modules",
        "structure",
        "--lib",
        "--manifest-path",
        str(MANIFEST),
        "--features",
        ",".join(FEATURES),
        "--target",
        target,
        "--no-fns",
        "--no-traits",
        "--no-types",
        "--cfg-test",
    ]


def parse(text: str, target: str) -> Export:
    """Reads and checks the cargo-modules export of one target."""

    def fail(reason: str) -> DiagramError:
        return DiagramError(f"unexpected cargo-modules export of {target}: {reason}")

    nodes = list(NODE.finditer(text))
    edges = list(EDGE.finditer(text))
    if len(nodes) + len(edges) != len(STATEMENT.findall(text)):
        raise fail("it holds nodes or edges other than modules and their uses")
    visibility: dict[str, str] = {}
    for match in nodes:
        path = match["path"]
        if path in visibility:
            raise fail(f"{path} appears twice")
        if (match["type"] == "crate") != (path == CRATE):
            raise fail(f"{path} is a {match['type']}")
        visibility[path] = match["kind"].removesuffix(" mod")
    if CRATE not in visibility:
        raise fail(f"the crate {CRATE} is missing")
    owner: dict[str, str] = {}
    uses: set[tuple[str, str]] = set()
    for match in edges:
        user, used = match["user"], match["used"]
        for path in (user, used):
            if path not in visibility:
                raise fail(f"{path} has an edge but is no module")
        if match["type"] == "uses":
            uses.add((user, used))
        elif used in owner or used.rpartition("::")[0] != user:
            raise fail(f"{user} cannot contain {used}")
        else:
            owner[used] = user
    if owner.keys() != visibility.keys() - {CRATE}:
        raise fail("a module has no owner")
    return Export(visibility, owner, frozenset(uses))


def conditions(text: str, target: str) -> dict[str, tuple[str, ...]]:
    """Reads and checks cargo-modules' structure of one target: the cfg
    conditions of each module, all of which must hold for it."""

    def fail(reason: str) -> DiagramError:
        return DiagramError(f"unexpected cargo-modules structure of {target}: {reason}")

    lines = [line for line in text.splitlines() if line.strip()]
    if not lines or lines[0] != f"crate {CRATE}":
        raise fail(f"it does not start with the crate {CRATE}")
    result: dict[str, tuple[str, ...]] = {CRATE: ()}
    stack = [CRATE]
    for line in lines[1:]:
        match = TREE.match(line)
        if match is None:
            raise fail(f"it holds {line!r}")
        depth = len(match["indent"]) // 4 + 1
        if depth > len(stack):
            raise fail(f"{match['name']} is deeper than a module that contains it")
        stack = [*stack[:depth], match["name"]]
        path = "::".join(stack)
        _, separator, listed = match["rest"].partition(" #[cfg(")
        listed = f"#[cfg({listed}" if separator else ""
        found = tuple(CONDITION.findall(listed))
        if ", ".join(f"#[cfg({condition})]" for condition in found) != listed:
            raise fail(f"the cfg conditions of {path} are unreadable")
        if path in result:
            raise fail(f"{path} appears twice")
        result[path] = found
    return result


def test_only(found: Mapping[str, Sequence[str]], path: str) -> bool:
    """Whether a module builds only for tests: one of its cfg conditions, or of a
    module that contains it, is test."""
    parts = path.split("::")
    return any(
        "test" in found["::".join(parts[:depth])] for depth in range(1, len(parts) + 1)
    )


def restore(
    plain: Export, tested: Export, found: Mapping[str, Sequence[str]], target: str
) -> Export:
    """The modules that one target builds, outside tests, and their uses.

    Unless it analyzes with cfg(test), cargo-modules drops as a test module every
    module whose cfg holds when test holds and every other condition fails, such
    as one under cfg(not(windows)): has_test_cfg, in its analyzer.rs, folds the
    whole condition with test true and the others false. Its analysis with
    cfg(test) holds those modules, and the test modules, which a cfg condition of
    their own or of a module that contains them, test, marks. The modules that
    build outside tests are those of the analysis with cfg(test) but the test
    modules, so this restores the modules that the plain analysis lacks among
    them. It refuses conditions that depend on test otherwise, such as
    any(test, unix) or not(test), whose modules it cannot tell apart.

    The plain analysis moves the uses of a module that it drops, and those of the
    modules that use it, to the nearest module that contains it and that it
    keeps, and drops those that this turns into a module's use of itself
    (filter.rs). So the uses are those of the analysis with cfg(test) whose move
    lands on a plain use, or on a module itself, and the plain uses that no such
    use lands on, such as those of an item under cfg(not(test)). This leaves out
    the uses that only tests make, and the moved uses. Where a use that involves
    a restored module lands on a plain use, neither analysis tells whether only
    tests make the first, which stays, or whether only an item under
    cfg(not(test)) makes the second, which goes."""

    def fail(reason: str) -> DiagramError:
        return DiagramError(f"cannot restore the modules of {target}: {reason}")

    if found.keys() != tested.visibility.keys():
        raise fail("its structure and its dependencies name different modules")
    for path, listed in found.items():
        for condition in listed:
            # A string, such as the name of a feature, holds no condition.
            unquoted = re.sub(r'"[^"]*"', '""', condition)
            if condition != "test" and re.search(r"\btest\b", unquoted):
                raise fail(f"{path} builds under cfg({condition})")
    built = {path for path in tested.visibility if not test_only(found, path)}
    missing = sorted(plain.visibility.keys() - built)
    if missing:
        raise fail(f"{', '.join(missing)} build outside tests only")

    def kept(path: str) -> str:
        """The module, or the nearest module that contains it, that the plain
        analysis keeps."""
        while path not in plain.visibility:
            path = tested.owner[path]
        return path

    uses: set[tuple[str, str]] = set()
    moved: set[tuple[str, str]] = set()
    for user, used in tested.uses:
        if user not in built or used not in built:
            continue
        move = (kept(user), kept(used))
        if move in plain.uses or (move[0] == move[1] and move != (user, used)):
            uses.add((user, used))
            moved.add(move)
    return Export(
        {path: tested.visibility[path] for path in sorted(built)},
        {path: tested.owner[path] for path in sorted(built - {CRATE})},
        frozenset(uses | (plain.uses - moved)),
    )


def merge(exports: Mapping[str, Export]) -> Crate:
    """Merges the exports of the platforms, in their order. A module whose
    visibility differs between them names the visibility of each."""
    visibilities: dict[str, dict[str, str]] = {}
    owner: dict[str, str] = {}
    uses: dict[tuple[str, str], set[str]] = {}
    for platform, export in exports.items():
        for path, visibility in export.visibility.items():
            visibilities.setdefault(path, {})[platform] = visibility
        owner.update(export.owner)
        for pair in export.uses:
            uses.setdefault(pair, set()).add(platform)
    modules: dict[str, Module] = {}
    for path, by_platform in sorted(visibilities.items()):
        distinct = sorted(set(by_platform.values()))
        visibility = (
            distinct[0]
            if len(distinct) == 1
            else ", ".join(f"{value} on {name}" for name, value in by_platform.items())
        )
        modules[path] = Module(visibility, frozenset(by_platform))
    return Crate(
        tuple(exports),
        modules,
        dict(sorted(owner.items())),
        {pair: frozenset(names) for pair, names in sorted(uses.items())},
    )


def quote(value: object) -> str:
    """A quoted DOT ID, whose newlines break the lines of a label."""
    text = str(value).replace("\\", "\\\\").replace('"', '\\"')
    return '"' + text.replace("\n", "\\n") + '"'


def group(path: str) -> str:
    """The part of the crate that holds a module, which colors it: its top-level
    module, the core that the host and the guest share, or the crate root."""
    parts = path.split("::")
    if len(parts) == 1:
        return CRATE
    return parts[1] if parts[1] in COLORS else "core"


def top(path: str) -> str:
    """The top-level module that holds a module, or the crate root itself."""
    return "::".join(path.split("::")[:2])


def plural(count: int, noun: str) -> str:
    return f"{count} {noun}" + ("" if count == 1 else "s")


def node(crate: Crate, path: str, lines: Iterable[str]) -> str:
    """A node statement, colored by the part of the crate that holds the module,
    solid if the module is public and dashed if not, naming its visibility
    unless it is public or private, and the platforms that alone build it."""
    fill, border = COLORS[group(path)]
    module = crate.modules[path]
    label = [line for line in lines if line]
    if module.visibility not in (*PUBLIC, PRIVATE):
        label.append(module.visibility)
    only = crate.only(path)
    if only is not None:
        label.append(f"{only} only")
    attributes = {
        "label": "\n".join(label),
        "tooltip": f"{path} ({module.visibility})",
        "fillcolor": fill,
        "color": border,
        "fontcolor": "#ffffff" if path == CRATE else "#14283f",
        "style": "rounded,filled"
        if module.visibility in PUBLIC
        else "rounded,filled,dashed",
    }
    listed = ", ".join(f"{key}={quote(value)}" for key, value in attributes.items())
    return f"{quote(path)} [{listed}];"


def graph(name: str, statements: Iterable[str]) -> str:
    return "\n".join((f"digraph {quote(name)} {{", *HEADER, *statements, "}")) + "\n"


def overview(crate: Crate) -> str:
    """The top-level modules in a grid, in the box of the crate that contains
    them."""
    roots = crate.roots()
    fill, border = COLORS[CRATE]
    statements = [
        "graph [rankdir=TB, nodesep=0.25, ranksep=0.3];",
        f"subgraph {quote('cluster_' + CRATE)} {{",
        f'graph [label={quote(CRATE)}, labeljust=l, style="rounded,filled",'
        f' fillcolor="#f8fafc", color={quote(fill)}, fontcolor={quote(border)},'
        " fontsize=16, penwidth=1.5, margin=14];",
    ]
    for root in roots:
        name = root.removeprefix(f"{CRATE}::")
        nested = len(crate.subtree(root)) - 1
        lines = (
            name,
            DESCRIPTIONS.get(name, ""),
            plural(nested, "nested module") if nested else "",
        )
        statements.append(node(crate, root, lines))
    rows = [roots[start : start + ROW] for start in range(0, len(roots), ROW)]
    # Invisible edges order each row, and stack each column, of the grid.
    statements.extend(
        "{rank=same; "
        + " -> ".join(map(quote, row))
        + (" [style=invis]" if len(row) > 1 else "")
        + ";}"
        for row in rows
    )
    statements.extend(
        f"{quote(upper)} -> {quote(lower)} [style=invis];"
        for above, below in pairwise(rows)
        # The last row may be shorter.
        for upper, lower in zip(above, below, strict=False)
    )
    statements.append("}")
    return graph(CRATE, statements)


def dependencies(crate: Crate) -> str:
    """The uses between top-level modules, counted by the pairs of their
    modules, and the crate root's re-exports."""
    roots = crate.roots()
    statements = [node(crate, CRATE, (CRATE, "crate re-exports"))]
    statements.extend(
        node(crate, root, (root.removeprefix(f"{CRATE}::"),)) for root in roots
    )
    counts = Counter(
        (top(user), top(used)) for user, used in crate.uses if top(user) != top(used)
    )
    for (user, used), count in sorted(counts.items()):
        tooltip = f"{user} uses {used}: {plural(count, 'pair')} of modules"
        statements.append(
            f"{quote(user)} -> {quote(used)} [label={quote(count)},"
            f" tooltip={quote(tooltip)}, color={quote(COLORS[group(user)][1])}];"
        )
    return graph(f"{CRATE} dependencies", statements)


def hierarchy(crate: Crate, root: str) -> str:
    """A top-level module, the modules that it contains, and their
    containment."""
    selected = crate.subtree(root)
    statements = [
        "graph [nodesep=0.12, ranksep=0.5, ordering=out];",
        'node [height=0.3, margin="0.12,0.04"];',
    ]
    statements.extend(
        node(crate, path, (path if path == root else path.rpartition("::")[2],))
        for path in selected
    )
    statements.extend(
        f"{quote(crate.owner[path])} -> {quote(path)};"
        for path in selected
        if path != root
    )
    return graph(root, statements)


def diagrams(crate: Crate) -> list[Diagram]:
    """The diagrams of the page, in its order: the overview, the dependencies,
    and the hierarchy of each top-level module that contains modules."""
    result = [
        Diagram(
            "overview.svg",
            "Overview",
            "The crate's top-level modules, with what each holds and how many"
            " modules it contains.",
            overview(crate),
        ),
        Diagram(
            "dependencies.svg",
            "Dependencies",
            "The top-level modules that use one another. An arrow points from a"
            " module to a module that it uses, and counts the pairs of their"
            " modules in which the first uses the second, as cargo-modules finds"
            " them: a module uses another whose items it imports, re-exports"
            " included, or whose items the definitions of its own items name,"
            " which counts the implementations of a type's traits toward the"
            " type's module, wherever they are. The crate's own arrows are its"
            " re-exports. The uses within a top-level module are left out.",
            dependencies(crate),
        ),
    ]
    result.extend(
        Diagram(
            f"{root.replace('::', '-')}.svg",
            f"`{root}`",
            f"The modules that {root} contains",
            hierarchy(crate, root),
            root,
        )
        for root in crate.roots()
        if len(crate.subtree(root)) > 1
    )
    return result


def source(root: str) -> Path | None:
    """The file of a top-level module, unless the module is inline."""
    directory = MANIFEST.parent / "src"
    name = root.removeprefix(f"{CRATE}::")
    for path in (directory / name / "mod.rs", directory / f"{name}.rs"):
        if path.is_file():
            return path
    return None


def paragraph(text: str) -> list[str]:
    """The lines of a paragraph of the page."""
    return [
        *textwrap.wrap(
            text, width=WIDTH, break_long_words=False, break_on_hyphens=False
        ),
        "",
    ]


def page(crate: Crate, drawn: Sequence[Diagram], output: Path, tools: str) -> str:
    """The page that shows the diagrams, in the output directory, whose links
    lead to the files that they name in the repository."""

    def link(text: str, path: Path, anchor: str = "") -> str:
        try:
            target = Path(os.path.relpath(path, output)).as_posix()
        except ValueError:
            # Windows has no relative path to another drive.
            return text
        return f"[{text}]({target}{anchor})"

    features = ", ".join(f"`{feature}`" for feature in FEATURES[:-1])
    targets = " and ".join(
        f"{platform} (`{target}`)" for platform, target in TARGETS.items()
    )
    ci = link("Module diagrams", REPOSITORY / "doc" / "ci.md", "#module-diagrams")
    lines = [
        MARKER,
        "",
        "# Module diagrams",
        "",
        *paragraph(
            f"The modules of the {link('`nvx` crate', MANIFEST.parent / 'README.md')},"
            " the modules that each contains, and the dependencies between them, as"
            f" {tools}. They cover the crate's library with its {features}, and"
            f" `{FEATURES[-1]}` features, on {targets}. CI draws them again after"
            " every merge to `dev` that changes the crate, and commits them when"
            f" they change; see {ci}."
        ),
        *paragraph(
            "Each box is a module, colored by the part of the crate that holds it:"
            " blue for the modules that the host and the guest share, purple for"
            " the host, teal for the guest, and amber for the test doubles. A solid"
            " box is a public module, and a dashed box a private one, unless it"
            " names another visibility, such as `pub(crate)`. A box that names"
            " platforms, as in *Linux only*, is a module that only they build, as"
            " are the modules that it contains. The diagrams leave out the crate's"
            " tests and binaries, and other crates."
        ),
    ]
    hierarchies = False
    for diagram in drawn:
        if diagram.root is None:
            lines += [f"## {diagram.title}", "", *paragraph(diagram.text)]
            alt = diagram.title
        else:
            if not hierarchies:
                hierarchies = True
                lines += [
                    "## Hierarchies",
                    "",
                    *paragraph(
                        "The modules that each top-level module contains. An arrow"
                        " points from a module to a module that it contains."
                    ),
                ]
            count = plural(len(crate.subtree(diagram.root)) - 1, "module")
            path = source(diagram.root)
            where = (
                ""
                if path is None
                else ", in "
                + link(f"`{path.relative_to(REPOSITORY).as_posix()}`", path)
                + ","
            )
            lines += [
                f"### {diagram.title}",
                "",
                *paragraph(f"`{diagram.root}`{where} contains {count}."),
            ]
            alt = diagram.text
        lines += [f"![{alt}]({diagram.name})", ""]
    return "\n".join(lines[:-1]) + "\n"


def render(dot: str, diagram: Diagram, execute: Runner) -> str:
    """Lays out a diagram with Graphviz and returns the SVG document."""
    svg = warn(execute([dot, "-Tsvg"], diagram.source))
    try:
        root = ET.fromstring(svg)
    except ET.ParseError as error:
        raise DiagramError(f"Graphviz wrote no SVG for {diagram.name}") from error
    if root.tag != "{http://www.w3.org/2000/svg}svg":
        raise DiagramError(f"Graphviz wrote no SVG for {diagram.name}")
    return svg if svg.endswith("\n") else svg + "\n"


def version(execute: Runner, command: Sequence[str], pattern: str) -> str | None:
    """The version that a tool reports, if it reports one."""
    try:
        output = execute(command, None)
    except DiagramError:
        return None
    match = re.search(pattern, output.stdout + output.stderr)
    return match[1] if match else None


def replace(output: Path, files: Mapping[str, str]) -> None:
    """Makes the output directory hold the files and nothing else, with LF line
    endings. It refuses a directory that holds anything but the page and the
    diagrams of an earlier run."""
    if output.exists():
        if not output.is_dir():
            raise DiagramError(f"{output} is not a directory")
        entries = sorted(output.iterdir())
        # A symbolic link that holds a diagram's name would have the diagram
        # written through it, outside the directory.
        foreign = [
            entry.name
            for entry in entries
            if entry.is_symlink()
            or not entry.is_file()
            or (entry.name != PAGE and entry.suffix != ".svg")
        ]
        earlier = output / PAGE
        if (
            entries
            and not foreign
            and not (
                earlier.is_file()
                and earlier.read_text(encoding="utf-8").startswith(MARKER + "\n")
            )
        ):
            foreign = [PAGE if earlier.is_file() else "no page of an earlier run"]
        if foreign:
            raise DiagramError(
                f"{output} holds more than the diagrams of an earlier run:"
                f" {', '.join(foreign)}; remove it or choose another --output"
            )
    output.mkdir(parents=True, exist_ok=True)
    for entry in output.iterdir():
        if entry.name not in files:
            entry.unlink()
    for name, text in files.items():
        with open(output / name, "w", encoding="utf-8", newline="\n") as file:
            file.write(text)


def find_dot() -> str:
    """The Graphviz dot executable: the one on PATH, or on Windows the one where
    the Graphviz installer puts it, which it does not always add to PATH."""
    found = shutil.which("dot")
    if found is not None:
        return found
    if os.name == "nt":
        programs = Path(os.environ.get("ProgramFiles", r"C:\Program Files"))
        installed = programs / "Graphviz" / "bin" / "dot.exe"
        if installed.is_file():
            return str(installed)
    raise DiagramError(
        "Graphviz is missing; install it, such as with apt-get install graphviz or"
        " winget install --id Graphviz.Graphviz --exact"
    )


def draw(output: Path, dot: str, execute: Runner = run) -> list[str]:
    """Exports the modules of every platform, draws the diagrams, and writes
    them and their page to the output directory, which changes only once every
    diagram is drawn. Returns the names of the files that it holds."""
    exports: dict[str, Export] = {}
    for platform, target in TARGETS.items():
        print(f"Exporting the modules of {platform} ({target})", file=sys.stderr)
        plain = parse(warn(execute(export_command(target), None)), target)
        tested = parse(
            warn(execute(export_command(target, cfg_test=True), None)), target
        )
        found = conditions(warn(execute(structure_command(target), None)), target)
        exports[platform] = restore(plain, tested, found, target)
    crate = merge(exports)
    drawn = diagrams(crate)
    files: dict[str, str] = {}
    for diagram in drawn:
        print(f"Drawing {diagram.name}", file=sys.stderr)
        files[diagram.name] = render(dot, diagram, execute)
    modules = version(execute, ["cargo", "modules", "--version"], r"(\S+)\s*$")
    graphviz = version(execute, [dot, "-V"], r"version (\S+)")
    tools = (
        "[cargo-modules](https://github.com/regexident/cargo-modules)"
        + (f" {modules}" if modules else "")
        + " finds them and Graphviz"
        + (f" {graphviz}" if graphviz else "")
        + " draws them"
    )
    files[PAGE] = page(crate, drawn, output, tools)
    replace(output, files)
    return sorted(files)


def main(argv: Sequence[str] | None = None) -> int:
    parser = argparse.ArgumentParser(
        description=(
            "Draws the module diagrams of the nvx crate, and the page that shows"
            " them, with cargo-modules and Graphviz."
        )
    )
    parser.add_argument(
        "--output",
        type=Path,
        default=DEFAULT_OUTPUT,
        help=(
            "the directory to write, which holds nothing but the output of an"
            " earlier run (default: build/modules; CI writes doc/modules)"
        ),
    )
    parser.add_argument(
        "--dot", help="the Graphviz dot executable (default: dot on PATH)"
    )
    arguments = parser.parse_args(argv)
    output: Path = arguments.output.resolve()
    try:
        if shutil.which("cargo-modules") is None:
            raise DiagramError(
                "cargo-modules is missing; install it with: cargo install --locked"
                f" cargo-modules --version {CARGO_MODULES_VERSION}"
            )
        dot: str = arguments.dot or find_dot()
        for name in draw(output, dot):
            print(output / name)
    except DiagramError as error:
        print(f"error: {error}", file=sys.stderr)
        return 1
    return 0


if __name__ == "__main__":
    sys.exit(main())