source-mesh-core 1.0.0

Rust dependency graph analysis, diagrams, and cycle reports
Documentation
use std::collections::BTreeMap;

use anyhow::Context as _;
use anyhow::Result;
use anyhow::ensure;
use getset::CopyGetters;
use getset::Getters;

use crate::cycles::CycleAnalysis;
use crate::cycles::CycleGroupId;
use crate::cycles::validate_folder_analysis;
use crate::model::DependencyCount;
use crate::model::DependencyKind;
use crate::model::FolderGraph;
use crate::model::FolderNode;

#[derive(CopyGetters)]
#[getset(get_copy = "pub(super)")]
pub(super) struct IndexedEdge {
    source: usize,
    target: usize,
    weight: DependencyCount,
    kind: DependencyKind,
    cycle_group: Option<CycleGroupId>,
}

#[derive(CopyGetters, Getters)]
pub(super) struct IndexedGraph<'graph> {
    #[getset(get = "pub(super)")]
    nodes: BTreeMap<&'graph str, usize>,
    #[getset(get = "pub(super)")]
    edges: Vec<IndexedEdge>,
    #[getset(get_copy = "pub(super)")]
    cycle_group_count: usize,
}

impl<'graph> IndexedGraph<'graph> {
    pub(super) fn new(graph: &'graph FolderGraph) -> Result<Self> {
        let nodes: BTreeMap<_, _> = graph
            .nodes()
            .iter()
            .enumerate()
            .map(|(index, node)| (node.label().as_str(), index))
            .collect();
        let edges = graph
            .edges()
            .iter()
            .map(|(endpoints, &weight)| {
                Ok(IndexedEdge {
                    source: *nodes.get(endpoints.source().label().as_str()).context("edge source is absent from graph nodes")?,
                    target: *nodes.get(endpoints.target().label().as_str()).context("edge target is absent from graph nodes")?,
                    weight,
                    kind: endpoints.kind(),
                    cycle_group: None,
                })
            })
            .collect::<Result<_>>()?;
        Ok(Self { nodes, edges, cycle_group_count: 0 })
    }

    pub(super) fn with_cycles(graph: &'graph FolderGraph, cycles: Option<&CycleAnalysis<FolderNode>>) -> Result<Self> {
        if let Some(cycles) = cycles {
            validate_folder_analysis(cycles, graph)?;
        }
        let mut indexed_graph = Self::new(graph)?;
        if let Some(cycles) = cycles {
            indexed_graph.cycle_group_count = cycles.group_count();
            for (edge, indexed_edge) in graph.edges().keys().zip(&mut indexed_graph.edges) {
                indexed_edge.cycle_group = cycles.edge_group(edge);
            }
        }
        Ok(indexed_graph)
    }
}

#[derive(CopyGetters, Getters)]
pub(super) struct Folder<'graph> {
    #[getset(get_copy = "pub(super)")]
    label: &'graph str,
    #[getset(get_copy = "pub(super)")]
    display_label: &'graph str,
    #[getset(get_copy = "pub(super)")]
    index: usize,
    #[getset(get_copy = "pub(super)")]
    dependency: bool,
    #[getset(get = "pub(super)")]
    children: Vec<Self>,
}

impl<'graph> Folder<'graph> {
    pub(super) fn hierarchy(graph: &IndexedGraph<'graph>) -> Result<Vec<Self>> {
        ensure!(graph.nodes.keys().all(|label| {
            *label == "." || label.split('/').all(|component| !matches!(component, "" | "." | ".."))
        }), "Grouped folder labels must be '.' or slash-separated relative paths without empty, '.' or '..' components");
        if graph.nodes.is_empty() {
            return Ok(Vec::new());
        }
        let mut indices = graph.nodes.clone();
        for &label in graph.nodes.keys() {
            let mut ancestor = label;
            while ancestor != "." {
                ancestor = parent_label(ancestor);
                let next_index = indices.len();
                indices.entry(ancestor).or_insert(next_index);
            }
        }
        let mut folders: BTreeMap<_, _> = indices
            .iter()
            .map(|(&label, &index)| (label, Self {
                label,
                display_label: label,
                index,
                dependency: graph.nodes.contains_key(label),
                children: Vec::new(),
            }))
            .collect();
        let descendants_before_parents = indices.keys().rev().filter(|&&label| label != ".");
        for &label in descendants_before_parents {
            let mut folder = folders.remove(label).context("Hierarchy folder is missing")?;
            folder.children.reverse();
            folders.get_mut(parent_label(label)).context("Hierarchy parent is missing")?.children.push(folder);
        }
        let mut root = folders.remove(".").context("Hierarchy root is missing")?;
        root.children.reverse();
        root.without_common_root()
    }

    fn without_common_root(mut self) -> Result<Vec<Self>> {
        let mut roots = Vec::new();
        let mut common_root = ".";
        while !self.children.is_empty() {
            common_root = self.label();
            let mut children = std::mem::take(&mut self.children);
            if self.dependency {
                roots.push(self);
            }
            if children.len() == 1 {
                self = children.pop().context("Common hierarchy descendant is missing")?;
            } else {
                for child in &mut children {
                    child.make_relative_to(common_root)?;
                }
                roots.extend(children);
                return Ok(roots);
            }
        }
        self.make_relative_to(common_root)?;
        roots.push(self);
        Ok(roots)
    }

    fn make_relative_to(&mut self, common_root: &str) -> Result<()> {
        if common_root != "." {
            self.display_label = self.label.strip_prefix(common_root)
                .and_then(|relative| relative.strip_prefix('/'))
                .context("Visible hierarchy folder is outside its common root")?;
        }
        for child in &mut self.children {
            child.make_relative_to(common_root)?;
        }
        Ok(())
    }
}

#[must_use]
fn parent_label(label: &str) -> &str {
    label.rsplit_once('/').map_or(".", |(parent, _)| parent)
}

#[cfg(test)]
#[expect(clippy::panic_in_result_fn, reason = "Tests use assertions for expectations while returning Result for fallible setup.")]
mod tests {
    use std::collections::BTreeMap;
    use std::collections::BTreeSet;

    use anyhow::Context as _;
    use anyhow::Result;
    use rstest::rstest;

    use pretty_assertions::assert_eq;
    use super::Folder;
    use super::IndexedGraph;
    use crate::model::DependencyCount;
    use crate::model::DependencyKind;
    use crate::model::FolderEdge;
    use crate::model::FolderGraph;
    use crate::model::FolderNode;

    #[test]
    fn test_hierarchy_ancestors_and_original_node_identifiers() -> Result<()> {
        let fixture = FolderGraph::new(
            BTreeSet::from([FolderNode::new("src/api/v1".into()), FolderNode::new("src/store".into())]),
            BTreeMap::from([(
                FolderEdge::new(FolderNode::new("src/api/v1".into()), FolderNode::new("src/store".into()), DependencyKind::Production),
                DependencyCount::new(7),
            )]),
        )?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;
        let api = system_under_test.first().context("api is missing")?;
        let version = api.children.first().context("v1 is missing")?;
        let storage = system_under_test.last().context("store is missing")?;
        let edge = indexed_graph.edges.first().context("Dependency is missing")?;

        assert_eq!(system_under_test.len(), 2, "Common root containers must be omitted");
        assert_eq!((api.label, api.display_label, api.dependency), ("src/api", "api", false),
            "An ancestor below the common root must remain a relative container");
        assert_eq!((version.label, version.display_label, version.index, version.dependency),
            ("src/api/v1", "api/v1", 0, true), "Original v1 endpoint changed");
        assert_eq!((storage.label, storage.display_label, storage.index, storage.dependency),
            ("src/store", "store", 1, true), "Original storage endpoint changed");
        assert_eq!(indexed_graph.edges.len(), 1, "Hierarchy changed the edge count");
        assert_eq!((edge.source, edge.target, edge.weight), (0, 1, DependencyCount::new(7)), "Hierarchy changed the dependency");
        Ok(())
    }

    #[test]
    fn test_hierarchy_common_ancestor_dependencies() -> Result<()> {
        let fixture = FolderGraph::new(
            [".", "src", "src/api", "src/api/v1", "src/api/v2"].map(String::from).map(FolderNode::new).into(),
            BTreeMap::from([
                (FolderEdge::new(FolderNode::new("src".into()), FolderNode::new("src/api".into()), DependencyKind::Production), DependencyCount::new(2)),
                (FolderEdge::new(FolderNode::new("src/api".into()), FolderNode::new("src/api/v1".into()), DependencyKind::Production), DependencyCount::new(3)),
                (FolderEdge::new(FolderNode::new("src/api/v2".into()), FolderNode::new("src".into()), DependencyKind::Production), DependencyCount::new(5)),
            ]),
        )?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;

        assert_eq!(system_under_test.len(), 5, "All original folders, including isolated ancestors, must remain");
        assert!(system_under_test.iter().all(|folder| folder.children.is_empty() && folder.dependency),
            "Common ancestors must become separate dependency leaves");
        for (folder, (canonical, display)) in system_under_test.iter().zip([
            (".", "."), ("src", "src"), ("src/api", "src/api"), ("src/api/v1", "v1"), ("src/api/v2", "v2"),
        ]) {
            assert!(folder.label == canonical && folder.display_label == display,
                "Unexpected common ancestor or descendant label: {}", folder.label);
            assert_eq!(indexed_graph.nodes.get(canonical), Some(&folder.index), "Dependency endpoint was renumbered");
        }
        assert_eq!(indexed_graph.edges.len(), fixture.edges().len(), "Dependencies were removed");
        for ((endpoints, weight), edge) in fixture.edges().iter().zip(&indexed_graph.edges) {
            assert!(indexed_graph.nodes.get(endpoints.source().label().as_str()) == Some(&edge.source)
                && indexed_graph.nodes.get(endpoints.target().label().as_str()) == Some(&edge.target)
                && *weight == edge.weight, "Dependency endpoint or weight changed");
        }
        Ok(())
    }

    #[rstest]
    #[case(".", ".")]
    #[case("src", "src")]
    #[case("src/api/v1", "v1")]
    fn test_hierarchy_single_folder(#[case] label: &str, #[case] display_label: &str) -> Result<()> {
        let fixture = FolderGraph::new(
            BTreeSet::from([FolderNode::new(label.into())]),
            BTreeMap::from([(
                FolderEdge::new(FolderNode::new(label.into()), FolderNode::new(label.into()), DependencyKind::Production),
                DependencyCount::new(4),
            )]),
        )?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;
        let folder = system_under_test.first().context("Only folder is missing")?;
        let edge = indexed_graph.edges.first().context("Self-dependency is missing")?;

        assert_eq!(system_under_test.len(), 1, "The only source folder must remain visible");
        assert_eq!((folder.label, folder.display_label, folder.index, folder.dependency),
            (label, display_label, 0, true), "The only source folder changed");
        assert!(folder.children.is_empty(), "The only source folder retained redundant containers");
        assert_eq!((edge.source, edge.target, edge.weight), (0, 0, DependencyCount::new(4)), "Self-dependency changed");
        Ok(())
    }

    #[test]
    fn test_hierarchy_multiple_top_level_folders() -> Result<()> {
        let fixture = FolderGraph::new(
            BTreeSet::from([FolderNode::new("src/api".into()), FolderNode::new("tests/api".into())]), BTreeMap::new(),
        )?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;

        assert_eq!(system_under_test.len(), 2, "Independent top-level folders must remain separate");
        for (folder, expected_label) in system_under_test.iter().zip(["src", "tests"]) {
            assert!(folder.label == expected_label && folder.display_label == expected_label && !folder.dependency,
                "A top-level folder was removed or relabeled");
            let child = folder.children.first().context("Top-level descendant is missing")?;
            assert!(child.label == child.display_label && child.dependency,
                "A descendant without a shared path prefix was relabeled");
        }
        Ok(())
    }

    #[test]
    fn test_hierarchy_common_prefix_components() -> Result<()> {
        let fixture = FolderGraph::new(
            BTreeSet::from([FolderNode::new("src/api".into()), FolderNode::new("src/api_extra".into())]), BTreeMap::new(),
        )?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;

        let display_labels: Vec<_> = system_under_test.iter().map(|folder| folder.display_label).collect();

        assert_eq!(display_labels, ["api", "api_extra"], "A textual prefix inside a folder component was removed");
        Ok(())
    }

    #[test]
    fn test_hierarchy_empty_graph() -> Result<()> {
        let fixture = FolderGraph::default();
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph)?;

        assert!(system_under_test.is_empty(), "An empty graph must have no hierarchy roots");
        Ok(())
    }

    #[rstest]
    #[case("")]
    #[case("/src")]
    #[case("src/")]
    #[case("src//api")]
    #[case("src/./api")]
    #[case("src/../api")]
    fn test_hierarchy_path_preconditions(#[case] label: &str) -> Result<()> {
        let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new(label.into())]), BTreeMap::new())?;
        let indexed_graph = IndexedGraph::new(&fixture)?;

        let system_under_test = Folder::hierarchy(&indexed_graph);

        assert!(system_under_test.is_err(), "Invalid hierarchy path was accepted: {label}");
        Ok(())
    }
}