zelkova_compiler/

dependencies.rs

//! Walk package's module dependencies
//!
//! Within a package, each `Module` will depends on other `Module`s. The aim
//! of the dependencies module is to provide a way to sort the modules in a dependent
//! way, allowing parallel action on which module. We will also find out existing
//! cyclic dependencies and return all of them as error.
//!
//! We are currently using the excellent `petgraph` crate for sorting our dependencies
//! and discovering cycle. We currently use the results of the cycle discovery to drive
//! how we execute the processing. If we want to introduce parallel processing of the
//! different module, we will have to be a bit more thorough because we currently don't
//! have any information _at processing time_ to know when to block the check of some
//! modules. We don't know how we will do most of that processing, so it's a bit
//! premature to actually implement multi threading here.
//! Let's see how it goes first on a single thread and we can revisit this decision
//! later on.
//!

use super::name::Name;
use super::source::files::SourceFileId;
use super::SpanLabel;
use log::debug;
use std::collections::{HashMap, HashSet, VecDeque};
use zelkova_syntax::parser::Module;
use zelkova_syntax::position::NodeSpan;

use petgraph::graph::{DiGraph, NodeIndex};

/// What a checker hands [`ModuleWalker::check_in_order`] back for one module.
///
/// A module with errors can still have a shape: it has the interface its declarations
/// that canonicalized give it, whatever the typer says of them, and a typed tree for
/// each declaration the typer did not reject
/// ([`DEC-23`](../../docs/decisions/dec-23.md) decisions 1, 2 and 5). So "checked" and
/// "failed" are not the only two answers: [`Module`](Outcome::Module) carries a module
/// together with everything wrong with it.
#[derive(Debug)]
pub enum Outcome<M, E> {
    /// Nothing to publish.
    Failed(E),
    /// A module, and everything wrong with it. An empty list does not say the module
    /// checked: a checker may drop an error that restates another module's failure, so the
    /// caller reads the module for whether it is whole as well.
    Module(M, Vec<E>),
}

// TODO Improve this with barrier on each module, to be able to parallelize
// the processing down thel line.
pub struct ModuleWalker<'a> {
    /// The list of modules to process. We loose the barrier orders
    /// so we can't really process them in parallel at the moment.
    modules: Vec<&'a Module>,
}

impl<'a> std::fmt::Debug for ModuleWalker<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let modules: Vec<_> = self.modules.iter().map(|m| &m.name).collect();

        f.debug_struct("ModuleWalker")
            .field("modules", &modules)
            .finish()
    }
}

/// One `import` that forms an edge of a dependency cycle.
///
/// `from` imports `to` — the module the note lists right after it, wrapping
/// around to the cycle's start for the last edge — and `span`/`file` are where
/// that specific `import` line was written, when known.
///
/// `file` comes from the `module_files` map [`ModuleWalker::new`] is handed by
/// `compile_package`, the only place that knows which file a parsed module came
/// from — the same reasoning `ERR-5` used for [`crate::Interface::file`].
/// It is `None` for every edge built in this module's own tests, which hand-build
/// modules with nothing on disk behind them.
#[derive(Debug, PartialEq, Clone)]
pub struct CycleEdge {
    pub from: Name,
    pub to: Name,
    pub span: NodeSpan,
    pub file: Option<SourceFileId>,
}

/// A dependency cycle: one loop through a strongly-connected component of the
/// import graph, alongside the `import` that created each edge between consecutive
/// modules (wrapping around to the first), and any component member that loop does
/// not pass through.
#[derive(Debug, PartialEq, Clone)]
pub struct Cycle {
    /// *One* cycle within the strongly-connected component, in cycle order —
    /// what the summary note is built from. Not necessarily every module in the
    /// component: a component with several overlapping loops has more than one
    /// cycle in it, and picking the shortest one through a single start node (see
    /// `cycle_walk`) can leave others out. Finding a cycle that covers every
    /// member is the Hamiltonian cycle problem, and no such cycle need exist, so
    /// this does not try; the members left out are in [`Cycle::others`] instead,
    /// and the note names them so a user does not break one loop and immediately
    /// hit the next one hiding in the same component.
    pub path: Vec<Name>,
    /// The other modules in the same component: genuinely part of the circular
    /// dependency, but not on the particular cycle `path` names. Empty whenever
    /// `path` already covers the component, which every fixture and every real
    /// import graph seen so far is.
    pub others: Vec<Name>,
    /// `edges[i]` is the `import` written in `path[i]` that names `path[i + 1]`
    /// (or `path[0]`, for the last edge). Same length as `path`, and every entry
    /// is a real `import`, because `cycle_walk` only ever returns a path whose
    /// consecutive pairs are edges of the graph.
    pub edges: Vec<CycleEdge>,
}

#[derive(Debug, PartialEq)]
pub enum Error {
    CycleDetected(Vec<Cycle>),
}

/// A dependency cycle belongs to the package, not to any one module, so its message
/// names the modules involved rather than being prefixed with one of them, and its
/// labels — one per `import` that forms an edge — each carry their own file rather
/// than relying on a fallback the way a single-module phase error can
/// (`CompilationError::DependenciesError` renders this without one, see there).
impl crate::PhaseError for Error {
    fn message(&self) -> String {
        match self {
            Error::CycleDetected(cycles) => format!(
                "{} circular dependenc{} between modules",
                cycles.len(),
                if cycles.len() == 1 { "y" } else { "ies" }
            ),
        }
    }

    fn notes(&self) -> Vec<String> {
        match self {
            // Each cycle is written back to its start, so it reads as the loop it is:
            // `A -> B -> A`. A component that holds more than the one loop gets a
            // second note naming the members that loop leaves out, so breaking it
            // does not just uncover the next cycle in the same component
            // (`Cycle::others`).
            Error::CycleDetected(cycles) => cycles
                .iter()
                .flat_map(|cycle| {
                    let mut path: Vec<String> =
                        cycle.path.iter().map(|name| name.to_string()).collect();
                    if let Some(first) = path.first().cloned() {
                        path.push(first);
                    }
                    let mut notes = vec![format!("cycle: {}", path.join(" -> "))];

                    if !cycle.others.is_empty() {
                        let others: Vec<String> =
                            cycle.others.iter().map(|name| name.to_string()).collect();
                        notes.push(format!(
                            "also part of this circular dependency, on another loop through the same modules: {}",
                            others.join(", ")
                        ));
                    }

                    notes
                })
                .collect(),
        }
    }

    fn labels(&self) -> Vec<SpanLabel> {
        match self {
            Error::CycleDetected(cycles) => cycles
                .iter()
                .flat_map(|cycle| {
                    cycle.edges.iter().filter_map(|edge| {
                        // An edge with no span (a hand-built test module) or no known
                        // file (nothing in the real pipeline, since `module_files`
                        // covers every parsed module) has nowhere honest to point;
                        // it is dropped rather than guessed at, the same rule
                        // `Interface::source_span` follows.
                        let span = edge.span.span()?;
                        let file = edge.file?;
                        Some(SpanLabel {
                            span,
                            // Every edge is equally the cause — breaking any one
                            // of them breaks the loop — so a label states only its
                            // own edge and leaves the loop to the note. Saying
                            // "closing the cycle" here would put that claim on all
                            // N labels when only the last edge closes it.
                            message: format!("`{}` imports `{}` here", edge.from, edge.to),
                            primary: true,
                            file: Some(file),
                        })
                    })
                })
                .collect(),
        }
    }
}

/// Walk `members` — one strongly-connected component `tarjan_scc` found, so every
/// node in it can reach every other — into an actual directed cycle through
/// `start`: a sequence of modules where each one really does import the next, and
/// the last one imports the first.
///
/// `tarjan_scc`'s own ordering of a component does not promise this: it is
/// membership, not a walk, so consecutive entries are not necessarily connected by
/// an edge, and the note used to print a "cycle" the user could not follow. That is
/// what `ERR-6` set out to fix, and `build_cycle` needs it to be true a second time
/// over, because it looks up the `import` behind each consecutive pair and an edge
/// that does not exist has no `import` to point a label at.
///
/// So the guarantee has to hold by construction, not by luck. This is a breadth-first
/// search from `start` over in-component edges only, stopping at the first node found
/// to import `start` back; the path is then reconstructed backwards along the BFS
/// tree. Because BFS pops nodes in non-decreasing distance order, that is the
/// *shortest* cycle through `start`, and because a BFS tree path never repeats a
/// node, it is a simple one. A greedy walk that just takes the first unvisited
/// neighbour cannot promise this — in a component with two loops sharing a node
/// (`B` imports `C` and `E`; `C` imports `D`; `D` imports `B`; `E` imports `B`) it
/// wanders into `E`, dead-ends, and hands back `[D, B, E]` even though `E` does not
/// import `D`.
///
/// The cycle it finds may be a strict subset of `members` — see [`Cycle::path`] for
/// why that is not fixable in general and what is reported instead.
///
/// `start` must be one of `members`. Callers get that from the `partition` in
/// [`ModuleWalker::new`], which is also where the component is known to be
/// non-empty; taking it as a parameter is what keeps this function off an unchecked
/// `members[0]`.
///
/// The returned path is empty only if `start` lies on no cycle at all, which a
/// component `tarjan_scc` reported with more than one member cannot produce.
fn cycle_walk(
    graph: &DiGraph<&Module, ()>,
    members: &[NodeIndex],
    start: NodeIndex,
) -> Vec<NodeIndex> {
    let member_set: HashSet<NodeIndex> = members.iter().copied().collect();

    // How each node was first reached. `start` is deliberately absent: it is the
    // target, so reaching it is what ends the search rather than something to
    // record a predecessor for.
    let mut predecessor: HashMap<NodeIndex, NodeIndex> = HashMap::new();
    let mut queue: VecDeque<NodeIndex> = VecDeque::from([start]);
    // The node that closes the loop: the first one popped that imports `start`.
    let mut closing: Option<NodeIndex> = None;

    'search: while let Some(current) = queue.pop_front() {
        for next in graph.neighbors(current).filter(|n| member_set.contains(n)) {
            if next == start {
                closing = Some(current);
                break 'search;
            }

            // First time we reach `next` is along a shortest path to it, so a
            // later, longer way in is ignored.
            if predecessor.contains_key(&next) {
                continue;
            }

            predecessor.insert(next, current);
            queue.push_back(next);
        }
    }

    let mut path = Vec::new();

    if let Some(closing) = closing {
        let mut node = closing;
        path.push(node);

        // Back up the BFS tree to `start`. `predecessor` was built by this search,
        // so every node on that chain has one until `start` is reached; the `None`
        // arm cannot fire, and stopping is the right thing if it somehow did.
        while node != start {
            match predecessor.get(&node) {
                Some(&previous) => {
                    node = previous;
                    path.push(node);
                }
                None => break,
            }
        }

        path.reverse();
    }

    path
}

/// Turn one strongly-connected component into the [`Cycle`] a diagnostic renders:
/// the module path `cycle_walk` finds, the `import` behind each edge of it, and the
/// component members that path leaves out.
///
/// `start` is the node the cycle is found through; [`ModuleWalker::new`] takes it
/// from the component itself, which is how this avoids indexing one.
fn build_cycle(
    graph: &DiGraph<&Module, ()>,
    members: &[NodeIndex],
    start: NodeIndex,
    module_files: &HashMap<Name, SourceFileId>,
) -> Cycle {
    let node_path = cycle_walk(graph, members, start);
    let on_path: HashSet<NodeIndex> = node_path.iter().copied().collect();

    let path: Vec<Name> = node_path
        .iter()
        .map(|&idx| graph[idx].name.clone())
        .collect();

    let mut others: Vec<Name> = members
        .iter()
        .filter(|idx| !on_path.contains(idx))
        .map(|&idx| graph[idx].name.clone())
        .collect();
    // `tarjan_scc`'s ordering within a component is an implementation detail; a
    // note the user reads should not vary with it. Sorted on the identifier text
    // rather than through an `Ord` on `Name`, which `name.rs` deliberately does not
    // derive.
    others.sort_by(|l, r| l.as_str().cmp(r.as_str()));

    let edges = node_path
        .iter()
        .enumerate()
        .map(|(i, &idx)| {
            let from_module = graph[idx];
            let to_idx = node_path[(i + 1) % node_path.len()];
            let to_name = graph[to_idx].name.clone();

            // The specific `import …` line in `from_module` that names `to_name` —
            // there may be several imports in `from_module`, but at most one of
            // them names this particular neighbour. `cycle_walk` guarantees this is
            // a real edge, so the only reason to find nothing is a hand-built
            // module in this file's own tests, which carry no source text.
            let import = from_module.imports.iter().find(|imp| imp.name == to_name);

            CycleEdge {
                from: from_module.name.clone(),
                to: to_name,
                span: import.map(|imp| imp.span).unwrap_or_else(NodeSpan::none),
                file: import.and_then(|_| module_files.get(&from_module.name).copied()),
            }
        })
        .collect();

    Cycle {
        path,
        others,
        edges,
    }
}

/// Put the [default imports](crate::default_imports) into the import
/// graph, so a module that never wrote `import Basics` is still checked after it.
///
/// Canonicalization resolves an implicit import against an `Interface` that already
/// exists, and nothing but this graph decides which module is checked first — so
/// without these edges whether `1 + 2` resolved would come down to the order the
/// source files happened to load in.
///
/// `is_core` is `package.is_core()`, the package's own answer — a property of the
/// package's name rather than of `names`, which here is only one root's worth of
/// modules.
fn add_default_import_edges(
    graph: &mut DiGraph<&Module, ()>,
    names: &HashMap<&Name, NodeIndex>,
    is_core: bool,
) {
    if is_core {
        return;
    }

    let mut importers: Vec<(&Name, NodeIndex)> =
        names.iter().map(|(&name, &idx)| (name, idx)).collect();
    importers.sort_by(|left, right| left.0.as_str().cmp(right.0.as_str()));

    for default in crate::default_imports::DEFAULT_IMPORTS {
        let target = default.name();
        let Some(&target_idx) = names.get(&target) else {
            continue;
        };

        for &(module_name, module_idx) in &importers {
            if crate::default_imports::is_default(module_name) {
                continue;
            }

            // A written import already carries the edge, and replaces the implicit
            // import anyway.
            if graph[module_idx].imports.iter().any(|i| i.name == target) {
                continue;
            }

            if petgraph::algo::has_path_connecting(&*graph, target_idx, module_idx, None) {
                continue;
            }

            graph.add_edge(module_idx, target_idx, ());
        }
    }
}

impl<'a> ModuleWalker<'a> {
    /// `module_files` is how a cycle's edges learn which file each `import` was
    /// written in (`CycleEdge::file`) — this is driver code, the same as
    /// `check_in_order` below, so it is handed the map `compile_package` already
    /// built while parsing rather than trying to discover it itself. Every test in
    /// this module passes an empty map: their modules are hand-built, with no file
    /// on disk to name, and `CycleEdge::file` degrades to `None` for them exactly
    /// as documented there.
    pub fn new(
        modules: &'a [Module],
        module_files: &HashMap<Name, SourceFileId>,
        package: &crate::PackageName,
    ) -> Result<ModuleWalker<'a>, Error> {
        ModuleWalker::new_for_root(modules, module_files, package)
    }

    /// A walker over the modules of *one* of a package's two source roots.
    ///
    /// A package has a `src/` and a `tests/`, and each is walked and checked on its own,
    /// but whether `package` is exempt from the default imports
    /// ([`PackageName::is_core`](crate::PackageName::is_core)) does not depend
    /// on which root — or which modules — either one happens to hold, so the two roots
    /// of one package always get the same answer without either walker having to be
    /// told the other's modules.
    ///
    /// The import graph is built from `modules` alone either way. An import naming a
    /// module of the other root resolves through an
    /// [`Interface`](crate::Interface) or not at all, the same as an import
    /// naming another package's module.
    pub fn new_for_root(
        modules: &'a [Module],
        module_files: &HashMap<Name, SourceFileId>,
        package: &crate::PackageName,
    ) -> Result<ModuleWalker<'a>, Error> {
        let mut graph = DiGraph::new();

        let mut names = HashMap::new();

        // First populate the graph with all nodes, and keep a reference from Path to the node index
        for module in modules.iter() {
            let idx = graph.add_node(module);
            names.insert(&module.name, idx);
        }

        // Now that all modules have been inserted, we can create edges
        for module in modules.iter() {
            let m_idx = names.get(&module.name).unwrap();

            // When building the dependency graph, we exclude all imports for
            // modules not in this package. The reason is simple: a dependent
            // package cannot depends on the current package, so no cycle to detect
            for dep in module
                .imports
                .iter()
                .filter_map(|import| names.get(&import.name))
            {
                graph.add_edge(*m_idx, *dep, ());
            }
        }

        add_default_import_edges(&mut graph, &names, package.is_core());

        // Find the strongly connected graphs (scc), if there are more than one node per scc
        // it means there is a circular dependency.
        let scc = petgraph::algo::tarjan_scc(&graph);

        let (cycles, deps): (Vec<_>, Vec<_>) = scc.iter().partition(|&v| v.len() > 1);

        if cycles.is_empty() {
            let modules = deps.into_iter().flatten().map(|&idx| graph[idx]).collect();

            Ok(ModuleWalker { modules })
        } else {
            // `partition` above already established every component here has more
            // than one member, so `first()` is always `Some`; taking the start node
            // from it here, rather than indexing inside `cycle_walk`, is what keeps
            // that guarantee next to the check that establishes it.
            let c = cycles
                .into_iter()
                .filter_map(|members| {
                    members
                        .first()
                        .map(|&start| build_cycle(&graph, members, start, module_files))
                })
                .collect();

            Err(Error::CycleDetected(c))
        }
    }

    /// Given a package name, a set of existing interfaces and a checker function,
    /// check each module in its dependencies order.
    ///
    /// Every module is checked regardless of whether an earlier one failed, and each
    /// comes back as one [`Outcome`], in the order it was checked (`BUG-2`). Every
    /// module the checker hands back has its `Interface` inserted into `interfaces` as
    /// it goes, whether or not it came back with errors, so later modules keep resolving
    /// against earlier ones: an importer of a module with an error in one declaration is
    /// checked against the interface that module has, and reports nothing about the
    /// import ([`DEC-23` decision
    /// 1](../../docs/decisions/dec-23.md#1--a-module-publishes-the-interface-it-has-whichever-phase-failed)).
    /// Only an [`Outcome::Failed`] module is absent from what follows it.
    ///
    /// `module_files` is how a checked module's `Interface` learns the file it was
    /// read from (`Interface::file`, `ERR-5`) — `check` itself is a phase-orchestrating
    /// function and, like every phase, never knows it. This method is driver code
    /// rather than a phase, the same as `compile_package`, so it is the one that can
    /// look the id up and stamp it on before the interface goes into the shared map.
    /// A module missing from `module_files` — there is none in the real pipeline,
    /// since only a module that already parsed reaches here — simply leaves that
    /// interface's `file` as `None`, same as a hand-built one.
    ///
    /// `check` takes `package` and nothing beyond it to say whether this build is
    /// exempt from the default imports — `PackageName::is_core` is a function of
    /// `package` alone, so a checker derives its own answer from the same package
    /// this walker was built from rather than being handed one separately.
    #[allow(clippy::type_complexity)]
    pub fn check_in_order<M: crate::Checked, E>(
        &self,
        package: &crate::PackageName,
        interfaces: &mut HashMap<Name, crate::Interface>,
        module_files: &HashMap<Name, crate::source::files::SourceFileId>,
        check: fn(
            package: &crate::PackageName,
            interfaces: &HashMap<Name, crate::Interface>,
            source: &zelkova_syntax::parser::Module,
        ) -> Outcome<M, E>,
    ) -> Vec<Outcome<M, E>> {
        let mut outcomes = Vec::new();

        for module in self.modules.iter() {
            let outcome = check(package, interfaces, module);

            // A module the checker handed back is available to the modules after it,
            // with or without errors.
            if let Outcome::Module(m, _) = &outcome {
                let iface_name = m.name().name().clone();
                // Driver code, so this is where the module's file is known: the
                // interface carries it so a *later* module's diagnostic can point
                // back into this one's source (`ERR-5`).
                let iface = m.to_interface(module_files.get(&module.name).copied());
                debug!("Inserting {} with value {:?}", iface_name, iface);
                interfaces.insert(iface_name, iface);
            }

            outcomes.push(outcome);
        }

        outcomes
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{canonical, parser, CheckedModule, Interface, ModuleName, Name, PackageName};
    use zelkova_syntax::parser::{Exposing, Import};
    use zelkova_syntax::position::NodeSpan;

    fn module<S: Into<String>>(name: S, deps: Vec<S>) -> Module {
        let imports = deps
            .into_iter()
            .map(|n| Import {
                name: Name::new(n),
                alias: None,
                exposing: Exposing::Open,
                // Hand-built, not parsed: there is no source text behind it.
                span: NodeSpan::none(),
            })
            .collect();

        Module {
            name: Name::new(name),
            binding_foreign: false,
            exposing: Exposing::Open,
            exposing_span: NodeSpan::none(),
            imports,
            infixes: vec![],
            types: vec![],
            classes: vec![],
            instances: vec![],
            functions: vec![],
            failed: vec![],
        }
    }

    fn name<S: Into<String>>(s: S) -> Name {
        Name::new(s)
    }

    /// A package other than `zelkova-core`, for a `ModuleWalker` whose modules are
    /// not shaped like the standard library — every fixture below except the ones
    /// that name `Basics` on purpose.
    fn ordinary_package() -> PackageName {
        PackageName::new("author-project").unwrap()
    }

    /// A `CycleEdge` matching what `module()` above produces: no span, since
    /// there is no source text behind a hand-built import, and no file, since
    /// these tests pass an empty `module_files` map to `ModuleWalker::new`.
    fn edge<S: Into<String>>(from: S, to: S) -> CycleEdge {
        CycleEdge {
            from: Name::new(from),
            to: Name::new(to),
            span: NodeSpan::none(),
            file: None,
        }
    }

    /// An empty canonical module standing in for whatever the real checker would
    /// have produced. Shared by the checkers below, which differ only in which
    /// modules they refuse.
    fn dummy_module(package: &PackageName, source: &parser::Module) -> CheckedModule {
        let canonical = canonical::Module {
            name: ModuleName::new(package.clone(), source.name.clone()),
            exports: canonical::Exports::Everything,
            exposing_span: source.exposing_span,
            infixes: HashMap::new(),
            types: HashMap::new(),
            classes: HashMap::new(),
            instances: Vec::new(),
            imported_instances: Vec::new(),
            values: HashMap::new(),
            broken: Vec::new(),
            binding_foreign: false,
            incomplete: false,
        };
        let ir = crate::ir::build(&canonical, HashMap::new(), Vec::new());

        CheckedModule { canonical, ir }
    }

    fn dummy_check(
        package: &PackageName,
        _interfaces: &HashMap<Name, Interface>,
        source: &parser::Module,
    ) -> Outcome<CheckedModule, ()> {
        Outcome::Module(dummy_module(package, source), vec![])
    }

    /// Like `dummy_check`, except module `b` always fails. Used to pin `BUG-2`:
    /// `check_in_order` must keep checking (and reporting) every other module
    /// rather than discarding them because one sibling failed.
    ///
    /// The error carries the failing module's name rather than being `()` so the
    /// test can assert *which* module failed; with `E = ()` the type system already
    /// guarantees the contents and only the arity would be under test.
    fn dummy_check_fails_for_b(
        package: &PackageName,
        _interfaces: &HashMap<Name, Interface>,
        source: &parser::Module,
    ) -> Outcome<CheckedModule, Name> {
        if source.name.as_str() == "b" {
            Outcome::Failed(source.name.clone())
        } else {
            Outcome::Module(dummy_module(package, source), vec![])
        }
    }

    /// Like `dummy_check`, except module `b` comes back with an error beside its
    /// module, the way a module with a type error does.
    fn dummy_check_reports_for_b(
        package: &PackageName,
        _interfaces: &HashMap<Name, Interface>,
        source: &parser::Module,
    ) -> Outcome<CheckedModule, Name> {
        let errors = if source.name.as_str() == "b" {
            vec![source.name.clone()]
        } else {
            vec![]
        };
        Outcome::Module(dummy_module(package, source), errors)
    }

    /// The name of each module an outcome holds, and the errors of every outcome, in
    /// the order `check_in_order` handed them back.
    fn modules_and_errors<E>(outcomes: Vec<Outcome<CheckedModule, E>>) -> (Vec<String>, Vec<E>) {
        let mut modules = Vec::new();
        let mut errors = Vec::new();
        for outcome in outcomes {
            match outcome {
                Outcome::Module(m, module_errors) => {
                    modules.push(m.canonical.name.name().as_str().to_string());
                    errors.extend(module_errors);
                }
                Outcome::Failed(error) => errors.push(error),
            }
        }
        (modules, errors)
    }

    fn assert_walker_processed_order(walker: ModuleWalker, expected: Vec<&str>) {
        let name = ordinary_package();
        let mut ifaces = HashMap::new();
        let module_files = HashMap::new();
        let (modules, errors) = modules_and_errors(walker.check_in_order(
            &name,
            &mut ifaces,
            &module_files,
            dummy_check,
        ));

        assert_eq!(errors, Vec::<()>::new());
        assert_eq!(
            modules,
            expected
                .into_iter()
                .map(|s| s.to_string())
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn dependencies_without_cycle() {
        let a = module("a", vec![]);
        let b = module("b", vec!["a"]);
        let c = module("c", vec!["b"]);
        let d = module("d", vec!["a"]);

        let modules = vec![a, b, c, d];
        let module_files = HashMap::new();

        let walker = ModuleWalker::new(&modules, &module_files, &ordinary_package());

        assert_walker_processed_order(walker.expect("no errors here"), vec!["a", "b", "c", "d"])
    }

    /// The property `cycle_walk` is supposed to guarantee, asserted directly against
    /// the source modules rather than against `path` restated as `edges`: every
    /// consecutive pair in `path`, wrapping around from the last back to the first,
    /// is an `import` actually written in the earlier module.
    ///
    /// Checking `Cycle::edges` instead would pin nothing — `build_cycle` derives
    /// `from`/`to` from consecutive `path` entries unconditionally, and the two
    /// fields that could tell a real edge from a fabricated one are both dead in
    /// these fixtures (`file` is always `None` with an empty `module_files`, and
    /// `NodeSpan`'s `PartialEq` always returns `true`, per CLAUDE.md).
    fn assert_path_is_a_real_cycle(cycle: &Cycle, modules: &[Module]) {
        assert!(
            cycle.path.len() > 1,
            "a cycle between modules needs at least two of them, got {:?}",
            cycle.path
        );

        for (i, from) in cycle.path.iter().enumerate() {
            let to = &cycle.path[(i + 1) % cycle.path.len()];
            let from_module = modules
                .iter()
                .find(|m| &m.name == from)
                .unwrap_or_else(|| panic!("`{}` is one of the fixture modules", from));

            assert!(
                from_module.imports.iter().any(|imp| &imp.name == to),
                "`{}` does not import `{}`, so the reported cycle {:?} is not a walk \
                 this graph's edges can produce",
                from,
                to,
                cycle.path
            );
        }
    }

    /// Pins two things together: which modules a cycle names (as before this
    /// ticket), and — new for `ERR-6` — that its `path` is a genuine walk along
    /// real `import` edges rather than `tarjan_scc`'s raw, edge-agnostic
    /// component order. Before this change the note for the first cycle here
    /// printed `b -> c -> a -> b`, which is not a walk this graph's edges (`a ->
    /// c`, `b -> a`, `c -> b`) can produce — `b -> c` is not an edge. `path` is
    /// now `[b, a, c]`, which is: `b -> a` (b imports a), `a -> c` (a imports c),
    /// `c -> b` (c imports b, closing the loop).
    ///
    /// The hardcoded `path`/`edges` comparison pins *this* graph's answer; the
    /// `assert_path_is_a_real_cycle` calls pin the general property, and are what
    /// would catch a walk that closed its loop on an edge that does not exist. Both
    /// components here are simple cycles covering every member, so `others` is
    /// empty — `cycle_reports_component_members_left_off_the_loop` covers the case
    /// where it is not.
    ///
    /// Mutation-checked by reverting `cycle_walk` to return `members` verbatim
    /// (`tarjan_scc`'s raw order) instead of searching it: this test goes red
    /// (`[b, c, a]` instead of `[b, a, c]`, and `b` does not import `c`).
    /// `dependency_cycle_labels_each_import` in `crates/zelkova/tests/pipeline.rs` stays green
    /// under that same mutation and says so itself — its two-module fixture has only
    /// one possible walk, so the raw component order and a real walk coincide.
    #[test]
    fn dependencies_with_two_cycles() {
        let a = module("a", vec!["c"]);
        let b = module("b", vec!["a"]);
        let c = module("c", vec!["b"]);

        let d = module("d", vec!["a", "f"]);
        let e = module("e", vec!["d"]);
        let f = module("f", vec!["e"]);

        let modules = vec![a, b, c, d, e, f];
        let module_files = HashMap::new();

        let walker = ModuleWalker::new(&modules, &module_files, &ordinary_package());

        let res = walker.expect_err("I'm expecting an error");

        let Error::CycleDetected(cycles) = &res;
        for cycle in cycles {
            assert_path_is_a_real_cycle(cycle, &modules);
        }

        assert_eq!(
            res,
            Error::CycleDetected(vec![
                Cycle {
                    path: vec![name("b"), name("a"), name("c")],
                    others: vec![],
                    edges: vec![edge("b", "a"), edge("a", "c"), edge("c", "b")],
                },
                Cycle {
                    path: vec![name("e"), name("d"), name("f")],
                    others: vec![],
                    edges: vec![edge("e", "d"), edge("d", "f"), edge("f", "e")],
                },
            ])
        )
    }

    /// Every ordering of `specs` — a list of `(module name, its imports)` — handed to
    /// `ModuleWalker::new` in turn, with `assert` run on each resulting `Cycle`.
    ///
    /// The declaration order is what decides `tarjan_scc`'s ordering of a component,
    /// and therefore which member `build_cycle` starts its search from. A fixture
    /// written in one fixed order only ever exercises one start node, and a walk that
    /// is wrong from *some* start nodes will pass it by luck — which is exactly how
    /// the dead-end below went unnoticed. Running every permutation removes the luck.
    fn for_every_declaration_order(
        specs: &[(&str, Vec<&str>)],
        assert: impl Fn(&Cycle, &[Module], &[&str]),
    ) {
        // Lexicographic permutations of the indices into `specs`, so the whole set is
        // covered without pulling in a crate for it.
        let mut order: Vec<usize> = (0..specs.len()).collect();

        loop {
            let modules: Vec<Module> = order
                .iter()
                .map(|&i| module(specs[i].0, specs[i].1.clone()))
                .collect();
            let names: Vec<&str> = order.iter().map(|&i| specs[i].0).collect();
            let module_files = HashMap::new();

            let res = ModuleWalker::new(&modules, &module_files, &ordinary_package())
                .expect_err("every fixture here has a cycle in it");

            let Error::CycleDetected(cycles) = &res;
            assert_eq!(
                cycles.len(),
                1,
                "one component, so one cycle, in declaration order {:?}: {:?}",
                names,
                cycles
            );

            assert(&cycles[0], &modules, &names);

            // Next permutation.
            let Some(pivot) = (0..order.len() - 1)
                .rev()
                .find(|&i| order[i] < order[i + 1])
            else {
                break;
            };
            let successor = (pivot + 1..order.len())
                .rev()
                .find(|&i| order[i] > order[pivot])
                .expect("`pivot` was chosen because `pivot + 1` qualifies");
            order.swap(pivot, successor);
            order[pivot + 1..].reverse();
        }
    }

    /// The counterexample that sank the original greedy walk: a component holding
    /// two loops that share a node.
    ///
    /// ```text
    /// b imports c, e      b -> c -> d -> b
    /// c imports d         b -> e -> b
    /// d imports b
    /// e imports b
    /// ```
    ///
    /// `{b, c, d, e}` is one component. The greedy walk started at whichever member
    /// `tarjan_scc` listed first, took the first *unvisited* in-component neighbour
    /// at each step, and could walk itself into a corner: starting from `d` it went
    /// to `b`, from `b` to `e`, and `e`'s only neighbour `b` was already visited — so
    /// it stopped and returned `[d, b, e]`, whose wraparound `e -> d` is not an edge
    /// of this graph at all. The note then claimed `cycle: d -> b -> e -> d`, stating
    /// something false about the user's source, and `build_cycle` found no `import`
    /// behind that step so its label was silently dropped.
    ///
    /// Whether the start node is `d` depends on the declaration order, hence
    /// `for_every_declaration_order`.
    ///
    /// Mutation-checked against exactly that: restoring the greedy walk turns this
    /// test red on `e` not importing `d`.
    #[test]
    fn cycle_closes_on_a_real_import_when_two_loops_share_a_module() {
        let specs = [
            ("b", vec!["c", "e"]),
            ("c", vec!["d"]),
            ("d", vec!["b"]),
            ("e", vec!["b"]),
        ];

        for_every_declaration_order(&specs, |cycle, modules, order| {
            assert_path_is_a_real_cycle(cycle, modules);
            // Guard against the property being satisfied vacuously by a walk that
            // stopped one step in.
            assert!(
                cycle.path.len() >= 2,
                "declaration order {:?} produced {:?}",
                order,
                cycle.path
            );
        });
    }

    /// A component whose loops do not all share their members: the reported `path`
    /// is necessarily a strict subset of it.
    ///
    /// ```text
    /// a imports b         a -> b -> d -> a
    /// b imports d, c      b -> c -> b
    /// c imports b
    /// d imports a
    /// ```
    ///
    /// `{a, b, c, d}` is one component holding two loops that overlap only at `b`.
    /// No cycle covers all four, so whichever one `cycle_walk` reports leaves
    /// members out — and a user who breaks only the loop they were shown walks
    /// straight into the other. `Cycle::others` is how the ones left out stay
    /// visible, and `notes()` renders them.
    ///
    /// Mutation-checked by hardcoding `others: vec![]` in `build_cycle`: the union
    /// assertion below goes red.
    #[test]
    fn cycle_reports_component_members_left_off_the_loop() {
        use crate::PhaseError;

        let specs = [
            ("a", vec!["b"]),
            ("b", vec!["d", "c"]),
            ("c", vec!["b"]),
            ("d", vec!["a"]),
        ];

        for_every_declaration_order(&specs, |cycle, modules, order| {
            // Whichever loop was picked, it has to be a real one…
            assert_path_is_a_real_cycle(cycle, modules);

            // …and no member of the component may go unmentioned.
            let mut named: Vec<Name> = cycle
                .path
                .iter()
                .chain(cycle.others.iter())
                .cloned()
                .collect();
            named.sort_by(|l, r| l.as_str().cmp(r.as_str()));
            assert_eq!(
                named,
                vec![name("a"), name("b"), name("c"), name("d")],
                "`path` plus `others` must name the whole component; declaration \
                 order {:?} gave path {:?} and others {:?}",
                order,
                cycle.path,
                cycle.others
            );

            // No cycle here covers all four, so something is always left out — and
            // the note, not just the struct, has to say what.
            assert!(
                !cycle.others.is_empty(),
                "no loop in this component covers it, so `others` cannot be empty; \
                 declaration order {:?} gave path {:?}",
                order,
                cycle.path
            );

            let notes = Error::CycleDetected(vec![cycle.clone()]).notes();
            assert!(
                notes.iter().any(|n| {
                    n.starts_with("also part of this circular dependency")
                        && cycle.others.iter().all(|o| n.contains(o.as_str()))
                }),
                "expected a note naming the members left off the loop, got {:?}",
                notes
            );
        });
    }

    /// `LANG-57`: `Basics` importing the `Js.Basics` facade — `std/core`'s own
    /// shape — is not a dependency cycle. `zelkova-core` adds no implicit edges at
    /// all (below), so the only edge here is the written one, and `Js.Basics` is
    /// checked first because `Basics` actually imports it.
    #[test]
    fn a_facade_a_default_import_is_built_from_is_not_a_cycle() {
        let basics = module("Basics", vec!["Js.Basics"]);
        let js_basics = module("Js.Basics", vec![]);

        let modules = vec![basics, js_basics];
        let module_files = HashMap::new();

        let walker = ModuleWalker::new(&modules, &module_files, &PackageName::core())
            .expect("the standard library's own shape is not a cycle");

        assert_walker_processed_order(walker, vec!["Js.Basics", "Basics"]);
    }

    /// `LANG-57`: `zelkova-core` adds no implicit edges at all — not even one that
    /// would otherwise be perfectly safe to add — while an ordinary package is
    /// unaffected (which for `add_default_import_edges` has always meant "still no
    /// edges, because none of the eight is ever a node in its graph").
    ///
    /// Mutation-checked by dropping the `is_core` guard at the top of
    /// `add_default_import_edges`: the first assertion then finds the edge
    /// `Widget -> Basics` that guard exists to suppress.
    #[test]
    fn a_core_package_gets_no_implicit_edges() {
        let core_shaped = implicit_edges(
            &PackageName::core(),
            &["Widget", "Basics"],
            &[vec![], vec![]],
        );
        assert_eq!(
            core_shaped,
            Vec::new(),
            "`zelkova-core` must add no implicit edges, got {:?}",
            core_shaped
        );

        let ordinary = implicit_edges(&ordinary_package(), &["Widget", "Aux"], &[vec![], vec![]]);
        assert_eq!(
            ordinary,
            Vec::new(),
            "an ordinary package naming neither Basics nor any other default \
             still adds none, got {:?}",
            ordinary
        );
    }

    #[test]
    fn dependencies_with_branches() {
        /*
        a <- c <- b <- d
          <- e <- f <- g <- h

        i -> b
          -> e
          <- h
        i should be after e, c, and b; h should be after i; no guarantee on the order when there is no constraint
        */
        let a = module("a", vec![]);
        let b = module("c", vec!["a"]);
        let c = module("b", vec!["c"]);

        let d = module("d", vec!["c"]);
        let e = module("e", vec!["a"]);
        let f = module("f", vec!["e"]);
        let g = module("g", vec!["f"]);
        let h = module("h", vec!["g", "i"]);

        let i = module("i", vec!["b", "e"]);

        let modules = vec![a, c, b, d, e, f, g, h, i];
        let module_files = HashMap::new();

        let walker = ModuleWalker::new(&modules, &module_files, &ordinary_package());

        assert_walker_processed_order(
            walker.expect("no errors here"),
            vec!["a", "c", "b", "d", "e", "f", "g", "i", "h"],
        )
    }

    /// `BUG-2`: one failing module used to make `check_in_order` discard every
    /// module that checked successfully, returning `Err(errors)` with no way to
    /// recover the successes. It must hand back both: the modules that checked, and
    /// the errors from the ones that didn't.
    ///
    /// Mutation-checked by keeping only the `Failed` outcomes whenever one is present
    /// (`outcomes.retain(..)` before the return) — the old discard behaviour, expressed
    /// in a way that still compiles against the return type. It turns this test red,
    /// since `successes` then comes back empty instead of `["a", "c"]`.
    #[test]
    fn check_in_order_keeps_successful_modules_when_one_fails() {
        let a = module("a", vec![]);
        let b = module("b", vec!["a"]);
        let c = module("c", vec!["b"]);

        let modules = vec![a, b, c];
        let module_files = HashMap::new();
        let name = ordinary_package();
        let walker = ModuleWalker::new(&modules, &module_files, &name).expect("no errors here");

        let mut ifaces = HashMap::new();
        let (successes, errors) = modules_and_errors(walker.check_in_order(
            &name,
            &mut ifaces,
            &module_files,
            dummy_check_fails_for_b,
        ));

        assert_eq!(
            errors,
            vec![Name::new("b")],
            "expected exactly the one error, and for `b`"
        );
        assert_eq!(
            successes,
            vec!["a".to_string(), "c".to_string()],
            "expected the non-failing modules to still be returned"
        );
        assert!(
            !ifaces.contains_key(&Name::new("b")),
            "a module that failed has no interface to publish"
        );
    }

    /// A module that comes back with errors beside it publishes its interface all the
    /// same, so the modules importing it are checked against it.
    ///
    /// Mutation-checked by inserting the interface only for an `Outcome::Module` whose
    /// error list is empty: `b`'s interface is then missing and this turns red.
    #[test]
    fn check_in_order_publishes_a_module_that_came_back_with_errors() {
        let a = module("a", vec![]);
        let b = module("b", vec!["a"]);
        let c = module("c", vec!["b"]);

        let modules = vec![a, b, c];
        let module_files = HashMap::new();
        let name = ordinary_package();
        let walker = ModuleWalker::new(&modules, &module_files, &name).expect("no errors here");

        let mut ifaces = HashMap::new();
        let outcomes =
            walker.check_in_order(&name, &mut ifaces, &module_files, dummy_check_reports_for_b);

        let (modules, errors) = modules_and_errors(outcomes);
        assert_eq!(modules, vec!["a", "b", "c"]);
        assert_eq!(errors, vec![Name::new("b")]);

        let mut published: Vec<&str> = ifaces.keys().map(Name::as_str).collect();
        published.sort();
        assert_eq!(published, vec!["a", "b", "c"]);
    }

    /// The implicit edges `add_default_import_edges` adds, as slot pairs.
    ///
    /// Slots rather than names, so that two namings of one package shape produce
    /// directly comparable answers.
    fn implicit_edges(
        package: &PackageName,
        names: &[&str],
        written: &[Vec<usize>],
    ) -> Vec<(usize, usize)> {
        let modules: Vec<Module> = names
            .iter()
            .enumerate()
            .map(|(i, n)| {
                let deps: Vec<&str> = written[i].iter().map(|&j| names[j]).collect();
                module(*n, deps)
            })
            .collect();

        let mut graph = DiGraph::new();
        let mut idx_of = HashMap::new();
        let mut slot_of = HashMap::new();
        for (slot, m) in modules.iter().enumerate() {
            let idx = graph.add_node(m);
            idx_of.insert(&m.name, idx);
            slot_of.insert(idx, slot);
        }
        for m in modules.iter() {
            let from = idx_of[&m.name];
            for &to in m.imports.iter().filter_map(|i| idx_of.get(&i.name)) {
                graph.add_edge(from, to, ());
            }
        }

        let before = graph.edge_count();
        add_default_import_edges(&mut graph, &idx_of, package.is_core());

        let mut added: Vec<(usize, usize)> = graph
            .edge_indices()
            .skip(before)
            .filter_map(|e| graph.edge_endpoints(e))
            .map(|(from, to)| (slot_of[&from], slot_of[&to]))
            .collect();
        added.sort_unstable();
        added
    }
}