simplicityhl 0.7.0

//! Computes the bottom-up load order of dependencies using a DFS.
//!
//! # Architectural Note: Why pure DFS instead of C3?
//! Unlike OOP languages that require C3 Linearization to resolve complex method
//! overriding (MRO), SimplicityHL module imports rely on namespacing and aliasing.
//! Because we do not need to enforce strict local precedence, a standard post-order
//! DFS is a better option.

use std::collections::HashSet;

use crate::driver::{DependencyGraph, MAIN_MODULE};
use crate::error::{Diagnostic, Error};

/// This is a core component of the [`DependencyGraph`].
impl DependencyGraph {
    /// Returns the deterministic, BOTTOM-UP load order of dependencies.
    pub(super) fn linearize(&self) -> Result<Vec<usize>, Diagnostic> {
        let mut visited = HashSet::new();
        let mut visiting = Vec::new();
        let mut order = Vec::new();

        self.dfs_linearize(MAIN_MODULE, &mut visited, &mut visiting, &mut order)?;
        Ok(order)
    }

    /// Core recursive Post-Order DFS for topological sorting.
    ///
    /// - **Visited Set (`visited`):** Prevents processing shared dependencies multiple times (solves diamonds).
    /// - **Cycle Detection (`visiting`):** Tracks the current path stack to catch infinite loops.
    /// - **Order List (`order`):** Accumulates the deterministic load order bottom-up.
    fn dfs_linearize(
        &self,
        module: usize,
        visited: &mut HashSet<usize>,
        visiting: &mut Vec<usize>,
        order: &mut Vec<usize>,
    ) -> Result<(), Diagnostic> {
        // If we have already fully processed this module, skip it (Diamond Deduplication)
        if visited.contains(&module) {
            return Ok(());
        }

        if let Some(cycle_start) = visiting.iter().position(|&m| m == module) {
            return Err(Diagnostic::global(Error::LinearizationCycleDetected {
                deps: visiting[cycle_start..]
                    .iter()
                    .map(|&id| self.modules[&id].source.str_name())
                    .collect(),
            }));
        }

        visiting.push(module);

        let parents = self
            .dependencies
            .get(&module)
            .map_or(&[] as &[usize], |v| v.as_slice());

        for &parent in parents {
            // Ignore self-imports. Since the program is sequential and nodes are loaded
            // sequentially during `AST::analyze`, forward declarations cannot be loaded at all.
            if parent == module {
                continue;
            }
            self.dfs_linearize(parent, visited, visiting, order)?;
        }

        visiting.pop();
        visited.insert(module);
        order.push(module);

        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use crate::driver::tests::setup_graph;

    use super::*;

    #[test]
    fn test_linearize_simple_import() {
        let (graph, ids, _dir, _diags) = setup_graph(vec![
            ("main.simf", "use lib::math::some_func;"),
            ("libs/lib/math.simf", ""),
        ]);

        let order = graph.linearize().unwrap();

        let root_id = ids["main"];
        let math_id = ids["math"];

        assert_eq!(order, vec![math_id, root_id]);
    }

    #[test]
    fn test_linearize_diamond_dependency_deduplication() {
        // Setup:
        // root -> imports A, B
        // A -> imports Common
        // B -> imports Common
        // Expected: Common loaded ONLY ONCE.

        let (graph, ids, _dir, _diags) = setup_graph(vec![
            ("main.simf", "use lib::A::foo; use lib::B::bar;"),
            ("libs/lib/A.simf", "use crate::Common::dummy1;"),
            ("libs/lib/B.simf", "use crate::Common::dummy2;"),
            ("libs/lib/Common.simf", ""),
        ]);

        let order = graph.linearize().unwrap();

        // Verify order using IDs from the helper map
        let main_id = ids["main"];
        let a_id = ids["A"];
        let b_id = ids["B"];
        let common_id = ids["Common"];

        assert!(
            order == vec![common_id, b_id, a_id, main_id]
                || order == vec![common_id, a_id, b_id, main_id]
        );
    }

    #[test]
    fn test_linearize_detects_cycle() {
        let (graph, _, _dir, _diags) = setup_graph(vec![
            ("main.simf", "use lib::A::entry;"),
            ("libs/lib/A.simf", "use crate::B::func;"),
            ("libs/lib/B.simf", "use crate::A::func;"),
        ]);

        let order = graph.linearize();
        let err = order
            .expect_err("expected linearizatoin to fail")
            .error()
            .clone();
        assert!(matches!(err, Error::LinearizationCycleDetected { .. }));
    }

    #[test]
    fn test_linearize_allows_conflicting_nested_import_order() {
        // A imports X then Y, while B imports Y then X.
        // This DAG is still valid because neither X nor Y depends on the other.
        let (graph, ids, _dir, _diags) = setup_graph(vec![
            ("main.simf", "use lib::A::foo; use lib::B::bar;"),
            ("libs/lib/A.simf", "use crate::X::foo; use crate::Y::bar;"),
            ("libs/lib/B.simf", "use crate::Y::baz; use crate::X::qux;"),
            ("libs/lib/X.simf", ""),
            ("libs/lib/Y.simf", ""),
        ]);

        let order = graph
            .linearize()
            .expect("valid dependency DAG should linearize successfully");

        let main_id = ids["main"];
        let a_id = ids["A"];
        let b_id = ids["B"];
        let x_id = ids["X"];
        let y_id = ids["Y"];

        assert!(
            order == vec![x_id, y_id, a_id, b_id, main_id]
                || order == vec![y_id, x_id, a_id, b_id, main_id]
                || order == vec![x_id, y_id, b_id, a_id, main_id]
                || order == vec![y_id, x_id, b_id, a_id, main_id]
        );
    }
}