normalize_graph/

lib.rs

//! Pure graph algorithms for dependency analysis.
//!
//! Operates on abstract graphs represented as adjacency lists
//! (`HashMap<String, HashSet<String>>`). No filesystem, CLI, or
//! normalize-specific types.
//!
//! Algorithms: Tarjan SCC, bridge-finding, diamond detection,
//! transitive edge detection, longest chains, weakly connected components.

use normalize_output::OutputFormatter;
use nu_ansi_term::Color;
use serde::Serialize;
use std::collections::{HashMap, HashSet, VecDeque};

/// Minimum chain length (in nodes) to include in the longest-chains report.
///
/// A chain of 4 nodes has depth 3 (3 edges). Depth 2 chains are common in any
/// project with a utilities layer and are not interesting signals. Starting at
/// depth ≥ 3 surfaces only chains that likely indicate layering violations or
/// overly deep call stacks worth reviewing.
const MIN_CHAIN_NODE_COUNT: usize = 4;

// ---------------------------------------------------------------------------
// Types
// ---------------------------------------------------------------------------

/// What the graph nodes represent.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, Serialize, serde::Deserialize, schemars::JsonSchema,
)]
#[serde(rename_all = "lowercase")]
pub enum GraphTarget {
    /// Nodes are files, edges are imports
    Modules,
    /// Nodes are functions (file:symbol), edges are calls
    Symbols,
    /// Nodes are types, edges are type references (fields, params, inheritance, etc.)
    Types,
}

impl std::str::FromStr for GraphTarget {
    type Err = String;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        match s {
            "modules" => Ok(Self::Modules),
            "symbols" => Ok(Self::Symbols),
            "types" => Ok(Self::Types),
            _ => Err(format!(
                "unknown graph target '{}', expected 'modules', 'symbols', or 'types'",
                s
            )),
        }
    }
}

impl std::fmt::Display for GraphTarget {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Modules => write!(f, "modules"),
            Self::Symbols => write!(f, "symbols"),
            Self::Types => write!(f, "types"),
        }
    }
}

/// Overall graph statistics.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct GraphStats {
    pub nodes: usize,
    pub edges: usize,
    /// Edge density: edges / (nodes × (nodes − 1)); 0.0 for graphs with fewer than 2 nodes.
    pub density: f64,
    pub weakly_connected_components: usize,
    pub largest_component_size: usize,
    pub scc_count: usize,
    /// Number of strongly connected components with more than one node (actual circular-dependency clusters).
    pub nontrivial_scc_count: usize,
    pub diamond_count: usize,
    /// Number of bridge edges whose removal would disconnect the graph.
    pub bridge_count: usize,
    /// Number of redundant transitive edges (A→C where A→B→C already exists).
    pub transitive_edge_count: usize,
    /// Depth (edge count) of the longest import chain.
    pub max_chain_depth: usize,
    /// Total number of import chains at or exceeding the depth threshold.
    pub chain_count: usize,
    /// Number of nodes with no inbound edges (unreachable or potentially dead code).
    pub dead_node_count: usize,
}

/// A strongly connected component (circular-dependency cluster).
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct Scc {
    /// Modules that are part of this strongly connected component.
    pub modules: Vec<String>,
    /// Number of edges within the SCC
    pub internal_edges: usize,
}

/// A diamond dependency: source imports left and right, both import target.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct Diamond {
    /// The module that starts the diamond (imports both `left` and `right`).
    pub source: String,
    /// The left intermediate module (imports `target`).
    pub left: String,
    /// The right intermediate module (imports `target`).
    pub right: String,
    /// The shared dependency that both intermediate modules import.
    pub target: String,
}

/// A bridge edge whose removal disconnects the graph.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct BridgeEdge {
    /// The importing module.
    pub from: String,
    /// The imported module.
    pub to: String,
}

/// A deep import chain (longest dependency path).
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct ImportChain {
    /// Modules in the chain from start to end, ordered by import depth.
    pub modules: Vec<String>,
    /// Length of the chain (number of edges, not nodes)
    pub depth: usize,
}

/// A transitive (redundant) import: A→C is redundant because A→B→C.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct TransitiveEdge {
    /// The importing module.
    pub from: String,
    /// The transitively reachable module (redundant direct dependency).
    pub to: String,
    /// The intermediate module that already provides the transitive path.
    pub via: String,
}

/// A file that depends on the query target (modules graph only).
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct DependentEntry {
    pub file: String,
    pub depth: usize,
    pub has_tests: bool,
    pub fan_in: usize,
}

/// Blast radius summary statistics (modules graph only).
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct BlastRadius {
    pub direct_count: usize,
    pub transitive_count: usize,
    pub untested_count: usize,
    pub max_depth: usize,
}

/// Report for reverse dependency queries: what depends on a given file/symbol.
///
/// For `--on modules` (default): structured output with depth, test coverage,
/// fan-in, and blast radius statistics.
/// For `--on symbols` / `--on types`: flat alphabetical list of dependents.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct DependentsReport {
    /// The file or symbol being queried.
    pub target: String,
    /// Graph node kind used for the query.
    pub graph_target: GraphTarget,
    /// Direct dependents (depth = 1) — populated for modules graph.
    #[serde(skip_serializing_if = "Vec::is_empty", default)]
    pub direct: Vec<DependentEntry>,
    /// Transitive dependents (depth > 1) — populated for modules graph.
    #[serde(skip_serializing_if = "Vec::is_empty", default)]
    pub transitive: Vec<DependentEntry>,
    /// Blast radius summary — populated for modules graph.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub blast_radius: Option<BlastRadius>,
    /// Untested impact paths — populated for modules graph.
    #[serde(skip_serializing_if = "Vec::is_empty", default)]
    pub untested_paths: Vec<String>,
    /// Flat dependent list — populated for symbols/types graph.
    #[serde(skip_serializing_if = "Vec::is_empty", default)]
    pub dependents: Vec<String>,
}

impl normalize_output::OutputFormatter for DependentsReport {
    fn format_text(&self) -> String {
        match self.graph_target {
            GraphTarget::Modules => self.format_modules_text(false),
            GraphTarget::Symbols | GraphTarget::Types => self.format_flat_text(false),
        }
    }

    fn format_pretty(&self) -> String {
        match self.graph_target {
            GraphTarget::Modules => self.format_modules_text(true),
            GraphTarget::Symbols | GraphTarget::Types => self.format_flat_text(true),
        }
    }
}

impl DependentsReport {
    fn format_modules_text(&self, pretty: bool) -> String {
        let mut lines = Vec::new();
        let total = self.direct.len() + self.transitive.len();

        if pretty {
            lines.push(
                Color::Cyan
                    .bold()
                    .paint(format!("# Dependents of {}", self.target))
                    .to_string(),
            );
        } else {
            lines.push(format!("# Dependents of {}", self.target));
        }
        lines.push(String::new());

        if let Some(ref br) = self.blast_radius {
            if pretty {
                lines.push(format!(
                    "{} files affected · {} direct · {} transitive · {} untested · max depth {}",
                    Color::Default.bold().paint(total.to_string()),
                    Color::Green.paint(br.direct_count.to_string()),
                    Color::Yellow.paint(br.transitive_count.to_string()),
                    Color::Red.paint(br.untested_count.to_string()),
                    br.max_depth
                ));
            } else {
                lines.push(format!(
                    "{} files affected · {} direct · {} transitive · {} untested · max depth {}",
                    total, br.direct_count, br.transitive_count, br.untested_count, br.max_depth
                ));
            }
        }

        if !self.direct.is_empty() {
            lines.push(String::new());
            if pretty {
                lines.push(
                    Color::Green
                        .bold()
                        .paint(format!("## Direct ({})", self.direct.len()))
                        .to_string(),
                );
            } else {
                lines.push(format!("## Direct ({})", self.direct.len()));
            }
            for e in &self.direct {
                let tested = if e.has_tests {
                    if pretty {
                        Color::Green.paint("tested").to_string()
                    } else {
                        "tested".to_string()
                    }
                } else if pretty {
                    Color::Red.bold().paint("UNTESTED").to_string()
                } else {
                    "UNTESTED".to_string()
                };
                lines.push(format!(
                    "  {:<40} depth {}  {}  fan-in {}",
                    e.file, e.depth, tested, e.fan_in
                ));
            }
        }

        if !self.transitive.is_empty() {
            lines.push(String::new());
            if pretty {
                lines.push(
                    Color::Yellow
                        .bold()
                        .paint(format!("## Transitive ({})", self.transitive.len()))
                        .to_string(),
                );
            } else {
                lines.push(format!("## Transitive ({})", self.transitive.len()));
            }
            for e in &self.transitive {
                let tested = if e.has_tests {
                    if pretty {
                        Color::Green.paint("tested").to_string()
                    } else {
                        "tested".to_string()
                    }
                } else if pretty {
                    Color::Red.bold().paint("UNTESTED").to_string()
                } else {
                    "UNTESTED".to_string()
                };
                lines.push(format!(
                    "  {:<40} depth {}  {}  fan-in {}",
                    e.file, e.depth, tested, e.fan_in
                ));
            }
        }

        if !self.untested_paths.is_empty() {
            lines.push(String::new());
            if pretty {
                lines.push(
                    Color::Red
                        .bold()
                        .paint(format!(
                            "## Untested Impact Paths ({})",
                            self.untested_paths.len()
                        ))
                        .to_string(),
                );
            } else {
                lines.push(format!(
                    "## Untested Impact Paths ({})",
                    self.untested_paths.len()
                ));
            }
            for p in &self.untested_paths {
                lines.push(format!("  {}", p));
            }
        }

        lines.join("\n")
    }

    fn format_flat_text(&self, pretty: bool) -> String {
        let kind = match self.graph_target {
            GraphTarget::Modules => "modules",
            GraphTarget::Symbols => "symbols",
            GraphTarget::Types => "types",
        };
        let mut out = Vec::new();
        if pretty {
            out.push(format!(
                "{} {} {}",
                Color::Cyan.bold().paint("# Dependents of"),
                Color::Default.bold().paint(&self.target),
                Color::Default.dimmed().paint(format!(
                    "({} {} depend on it)",
                    self.dependents.len(),
                    kind
                )),
            ));
            for dep in &self.dependents {
                out.push(format!("  {}", Color::White.paint(dep.as_str())));
            }
        } else {
            out.push(format!(
                "# Dependents of {} ({} {} depend on it)",
                self.target,
                self.dependents.len(),
                kind
            ));
            for dep in &self.dependents {
                out.push(format!("  {}", dep));
            }
        }
        out.join("\n")
    }
}

/// Full graph analysis report.
#[derive(Debug, Serialize, schemars::JsonSchema)]
pub struct GraphReport {
    pub target: GraphTarget,
    pub stats: GraphStats,
    pub sccs: Vec<Scc>,
    pub diamonds: Vec<Diamond>,
    pub bridges: Vec<BridgeEdge>,
    pub longest_chains: Vec<ImportChain>,
    pub transitive_edges: Vec<TransitiveEdge>,
    /// Nodes with no inbound edges (files/symbols that nothing imports/calls).
    /// Sorted alphabetically. Does not include fully isolated nodes (no edges at all).
    pub dead_nodes: Vec<String>,
}

// ---------------------------------------------------------------------------
// Algorithms
// ---------------------------------------------------------------------------

/// Collect all nodes from the import graph.
pub fn all_nodes(imports: &HashMap<String, HashSet<String>>) -> HashSet<String> {
    let mut nodes = HashSet::new();
    for (k, vs) in imports {
        nodes.insert(k.clone());
        for v in vs {
            nodes.insert(v.clone());
        }
    }
    nodes
}

/// Count directed edges.
pub fn edge_count(imports: &HashMap<String, HashSet<String>>) -> usize {
    imports.values().map(|s| s.len()).sum()
}

/// Build the reverse (transposed) graph: edges point from target to source.
pub fn reverse_graph(
    imports: &HashMap<String, HashSet<String>>,
) -> HashMap<String, HashSet<String>> {
    let mut rev: HashMap<String, HashSet<String>> = HashMap::new();
    for (src, targets) in imports {
        for tgt in targets {
            rev.entry(tgt.clone()).or_default().insert(src.clone());
        }
    }
    rev
}

/// Find all nodes that (transitively) depend on `target` via BFS on the reverse graph.
/// Returns a sorted list excluding the target itself.
pub fn find_dependents(imports: &HashMap<String, HashSet<String>>, target: &str) -> Vec<String> {
    let rev = reverse_graph(imports);
    let mut visited: HashSet<String> = HashSet::new();
    let mut queue: VecDeque<String> = VecDeque::new();
    queue.push_back(target.to_string());
    visited.insert(target.to_string());

    while let Some(node) = queue.pop_front() {
        if let Some(parents) = rev.get(&node) {
            for parent in parents {
                if visited.insert(parent.clone()) {
                    queue.push_back(parent.clone());
                }
            }
        }
    }

    let mut result: Vec<String> = visited.into_iter().filter(|n| n != target).collect();
    result.sort();
    result
}

/// Find nodes with no inbound edges (nothing imports/calls them) that do have
/// outbound edges (they import/call something). These are unreachable internal
/// nodes — potential dead code. Entry points (main.rs, lib.rs) are included;
/// callers can filter based on their heuristics.
pub fn find_dead_nodes(imports: &HashMap<String, HashSet<String>>) -> Vec<String> {
    // Collect all nodes that appear as targets (have at least one inbound edge)
    let mut has_inbound: HashSet<&str> = HashSet::new();
    for targets in imports.values() {
        for t in targets {
            has_inbound.insert(t.as_str());
        }
    }

    // Nodes that have outbound edges but no inbound edges
    let mut dead: Vec<String> = imports
        .keys()
        .filter(|n| !has_inbound.contains(n.as_str()))
        .cloned()
        .collect();
    dead.sort();
    dead
}

/// Weakly connected components via BFS on the undirected view.
pub fn weakly_connected_components(imports: &HashMap<String, HashSet<String>>) -> Vec<Vec<String>> {
    // Build undirected adjacency
    let mut adj: HashMap<String, HashSet<String>> = HashMap::new();
    for (u, vs) in imports {
        for v in vs {
            adj.entry(u.clone()).or_default().insert(v.clone());
            adj.entry(v.clone()).or_default().insert(u.clone());
        }
    }

    let mut visited: HashSet<String> = HashSet::new();
    let mut components = Vec::new();
    let nodes = all_nodes(imports);

    for node in &nodes {
        if visited.contains(node) {
            continue;
        }
        let mut component = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(node.clone());
        visited.insert(node.clone());

        while let Some(cur) = queue.pop_front() {
            component.push(cur.clone());
            if let Some(neighbors) = adj.get(&cur) {
                for n in neighbors {
                    if visited.insert(n.clone()) {
                        queue.push_back(n.clone());
                    }
                }
            }
        }
        component.sort();
        components.push(component);
    }

    components.sort_by_key(|c| std::cmp::Reverse(c.len()));
    components
}

/// Iterative Tarjan's SCC algorithm.
pub fn tarjan_sccs(imports: &HashMap<String, HashSet<String>>) -> Vec<Vec<String>> {
    let nodes = all_nodes(imports);
    let mut index_counter = 0usize;
    let mut indices: HashMap<String, usize> = HashMap::new();
    let mut lowlink: HashMap<String, usize> = HashMap::new();
    let mut on_stack: HashSet<String> = HashSet::new();
    let mut stack: Vec<String> = Vec::new();
    let mut sccs: Vec<Vec<String>> = Vec::new();

    // Iterative DFS using an explicit call stack
    #[derive(Debug)]
    enum Frame {
        Enter(String),
        Resume(String, String), // (node, neighbor) — resume after returning from neighbor
    }

    for start in &nodes {
        if indices.contains_key(start) {
            continue;
        }

        let mut call_stack: Vec<Frame> = vec![Frame::Enter(start.clone())];

        while let Some(frame) = call_stack.pop() {
            match frame {
                Frame::Enter(node) => {
                    if indices.contains_key(&node) {
                        continue;
                    }
                    indices.insert(node.clone(), index_counter);
                    lowlink.insert(node.clone(), index_counter);
                    index_counter += 1;
                    stack.push(node.clone());
                    on_stack.insert(node.clone());

                    let neighbors: Vec<String> = imports
                        .get(&node)
                        .map(|s| s.iter().cloned().collect())
                        .unwrap_or_default();

                    // Push neighbors in reverse so we process them in order
                    for neighbor in neighbors.into_iter().rev() {
                        if !indices.contains_key(&neighbor) {
                            call_stack.push(Frame::Resume(node.clone(), neighbor.clone()));
                            call_stack.push(Frame::Enter(neighbor));
                        } else if on_stack.contains(&neighbor) {
                            // normalize-syntax-allow: rust/unwrap-in-impl - node inserted into indices/lowlink at Frame::Enter
                            let nl = *lowlink.get(&node).unwrap(); // normalize-syntax-allow: rust/unwrap-in-impl - node inserted at Frame::Enter
                            let ni = *indices.get(&neighbor).unwrap(); // normalize-syntax-allow: rust/unwrap-in-impl - neighbor was already visited (in indices)
                            lowlink.insert(node.clone(), nl.min(ni));
                        }
                    }

                    // After processing all neighbors, check if this is a root
                    // We need a sentinel to know when we're done with a node
                    call_stack.push(Frame::Resume(node.clone(), String::new()));
                }
                Frame::Resume(node, neighbor) => {
                    if neighbor.is_empty() {
                        // Sentinel: all neighbors processed, check if root of SCC
                        // normalize-syntax-allow: rust/unwrap-in-impl - node inserted into indices/lowlink at Frame::Enter
                        let nl = *lowlink.get(&node).unwrap();
                        let ni = *indices.get(&node).unwrap(); // normalize-syntax-allow: rust/unwrap-in-impl - node inserted at Frame::Enter
                        if nl == ni {
                            let mut scc = Vec::new();
                            while let Some(w) = stack.pop() {
                                on_stack.remove(&w);
                                scc.push(w.clone());
                                if w == node {
                                    break;
                                }
                            }
                            scc.sort();
                            sccs.push(scc);
                        }
                    } else {
                        // Resume after DFS into neighbor
                        // normalize-syntax-allow: rust/unwrap-in-impl - node inserted into lowlink at Frame::Enter
                        let nl = *lowlink.get(&node).unwrap();
                        let neighbor_ll = *lowlink.get(&neighbor).unwrap_or(&usize::MAX);
                        lowlink.insert(node.clone(), nl.min(neighbor_ll));
                    }
                }
            }
        }
    }

    sccs
}

/// Find nontrivial SCCs (size > 1) with internal edge counts.
pub fn find_sccs(imports: &HashMap<String, HashSet<String>>) -> Vec<Scc> {
    let raw = tarjan_sccs(imports);
    let mut result = Vec::new();
    for modules in raw {
        if modules.len() <= 1 {
            continue;
        }
        let member_set: HashSet<&str> = modules.iter().map(|s| s.as_str()).collect();
        let mut internal_edges = 0;
        for m in &modules {
            if let Some(targets) = imports.get(m) {
                for t in targets {
                    if member_set.contains(t.as_str()) {
                        internal_edges += 1;
                    }
                }
            }
        }
        result.push(Scc {
            modules,
            internal_edges,
        });
    }
    result.sort_by(|a, b| b.modules.len().cmp(&a.modules.len()));
    result
}

/// Diamond detection: for each node A with imports {B₁,B₂,...}, check pairs for shared targets.
pub fn find_diamonds(imports: &HashMap<String, HashSet<String>>, limit: usize) -> Vec<Diamond> {
    let mut diamonds = Vec::new();
    let mut seen: HashSet<(String, String, String, String)> = HashSet::new();

    let mut sources: Vec<&String> = imports.keys().collect();
    sources.sort();

    for source in sources {
        let deps: Vec<&String> = match imports.get(source) {
            Some(s) => {
                let mut v: Vec<&String> = s.iter().collect();
                v.sort();
                v
            }
            None => continue,
        };
        if deps.len() < 2 {
            continue;
        }

        for i in 0..deps.len() {
            let left_targets = match imports.get(deps[i]) {
                Some(s) => s,
                None => continue,
            };
            for j in (i + 1)..deps.len() {
                let right_targets = match imports.get(deps[j]) {
                    Some(s) => s,
                    None => continue,
                };
                // Find shared targets
                for target in left_targets.intersection(right_targets) {
                    let key = (
                        source.clone(),
                        deps[i].clone(),
                        deps[j].clone(),
                        target.clone(),
                    );
                    if seen.insert(key) {
                        diamonds.push(Diamond {
                            source: source.clone(),
                            left: deps[i].clone(),
                            right: deps[j].clone(),
                            target: target.clone(),
                        });
                        if diamonds.len() >= limit {
                            return diamonds;
                        }
                    }
                }
            }
        }
    }
    diamonds
}

/// Bridge finding via Tarjan's bridge algorithm on the undirected view.
/// Only report bridges where exactly one directed edge exists (bidirectional ≠ bridge).
pub fn find_bridges(imports: &HashMap<String, HashSet<String>>) -> Vec<BridgeEdge> {
    // Build undirected adjacency list with neighbor indices for efficiency
    let nodes = all_nodes(imports);
    let node_list: Vec<String> = {
        let mut v: Vec<String> = nodes.into_iter().collect();
        v.sort();
        v
    };
    let node_idx: HashMap<&str, usize> = node_list
        .iter()
        .enumerate()
        .map(|(i, s)| (s.as_str(), i))
        .collect();
    let n = node_list.len();

    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut directed_edges: HashSet<(usize, usize)> = HashSet::new();

    for (u, vs) in imports {
        // normalize-syntax-allow: rust/unwrap-in-impl - node_idx built from the same node_list as imports keys
        let ui = *node_idx.get(u.as_str()).unwrap();
        for v in vs {
            // normalize-syntax-allow: rust/unwrap-in-impl - node_idx built from the same node_list as imports values
            let vi = *node_idx.get(v.as_str()).unwrap();
            directed_edges.insert((ui, vi));
            if !adj[ui].contains(&vi) {
                adj[ui].push(vi);
            }
            if !adj[vi].contains(&ui) {
                adj[vi].push(ui);
            }
        }
    }

    // Iterative bridge-finding (Tarjan's)
    let mut disc = vec![0usize; n];
    let mut low = vec![0usize; n];
    let mut visited = vec![false; n];
    let mut timer = 1usize;
    let mut bridges_idx: Vec<(usize, usize)> = Vec::new();

    #[derive(Debug)]
    struct BridgeFrame {
        node: usize,
        parent: usize, // usize::MAX for none
        adj_idx: usize,
    }

    for start in 0..n {
        if visited[start] {
            continue;
        }

        let mut stack = vec![BridgeFrame {
            node: start,
            parent: usize::MAX,
            adj_idx: 0,
        }];
        visited[start] = true;
        disc[start] = timer;
        low[start] = timer;
        timer += 1;

        while let Some(frame) = stack.last_mut() {
            let u = frame.node;
            if frame.adj_idx < adj[u].len() {
                let v = adj[u][frame.adj_idx];
                frame.adj_idx += 1;

                if !visited[v] {
                    visited[v] = true;
                    disc[v] = timer;
                    low[v] = timer;
                    timer += 1;
                    stack.push(BridgeFrame {
                        node: v,
                        parent: u,
                        adj_idx: 0,
                    });
                } else if v != frame.parent {
                    low[u] = low[u].min(disc[v]);
                }
            } else {
                // Done with this node — pop and update parent
                let u = frame.node;
                let parent = frame.parent;
                stack.pop();

                if parent != usize::MAX {
                    low[parent] = low[parent].min(low[u]);
                    if low[u] > disc[parent] {
                        bridges_idx.push((parent, u));
                    }
                }
            }
        }
    }

    // Map back to directed edges, only report if unidirectional
    let mut result = Vec::new();
    for (a, b) in bridges_idx {
        let has_ab = directed_edges.contains(&(a, b));
        let has_ba = directed_edges.contains(&(b, a));
        // Bidirectional edges aren't true dependency bridges
        if has_ab && !has_ba {
            result.push(BridgeEdge {
                from: node_list[a].clone(),
                to: node_list[b].clone(),
            });
        } else if has_ba && !has_ab {
            result.push(BridgeEdge {
                from: node_list[b].clone(),
                to: node_list[a].clone(),
            });
        }
    }
    result.sort_by(|a, b| a.from.cmp(&b.from).then(a.to.cmp(&b.to)));
    result
}

/// Transitive edge detection: A→C is redundant if ∃B: A→B and B→C.
pub fn find_transitive_edges(
    imports: &HashMap<String, HashSet<String>>,
    limit: usize,
) -> Vec<TransitiveEdge> {
    let mut result = Vec::new();
    let mut sources: Vec<&String> = imports.keys().collect();
    sources.sort();

    'outer: for a in &sources {
        let a_targets = match imports.get(*a) {
            Some(s) => s,
            None => continue,
        };
        for c in a_targets {
            // Check if any other direct import B of A has C as a target
            for b in a_targets {
                if b == c {
                    continue;
                }
                if let Some(b_targets) = imports.get(b)
                    && b_targets.contains(c)
                {
                    result.push(TransitiveEdge {
                        from: (*a).clone(),
                        to: c.clone(),
                        via: b.clone(),
                    });
                    if result.len() >= limit {
                        break 'outer;
                    }
                    break; // One witness suffices per (A, C)
                }
            }
        }
    }
    result
}

/// Count all transitive edges (without limit, for stats).
pub fn count_transitive_edges(imports: &HashMap<String, HashSet<String>>) -> usize {
    let mut count = 0;
    for a_targets in imports.values() {
        for c in a_targets {
            for b in a_targets {
                if b == c {
                    continue;
                }
                if let Some(b_targets) = imports.get(b)
                    && b_targets.contains(c)
                {
                    count += 1;
                    break; // One witness per (A, C)
                }
            }
        }
    }
    count
}

/// Find the longest import chains (dependency paths) in the graph.
///
/// Returns up to `limit` chains sorted by depth (longest first). When `limit`
/// is `0` all qualifying chains are returned. Only chains whose node count meets
/// [`MIN_CHAIN_NODE_COUNT`] are included.
///
/// Chains dominated by a suffix of a longer chain are removed: if chain B's
/// modules are a suffix of chain A's modules, B is dropped. This keeps the
/// result set non-redundant — each returned chain represents a unique root.
///
/// Uses DFS from each node with memoization to find the longest path, avoiding cycles.
pub fn find_longest_chains(
    graph: &HashMap<String, HashSet<String>>,
    limit: usize,
) -> Vec<ImportChain> {
    let mut longest_paths: Vec<ImportChain> = Vec::new();
    let mut memo: HashMap<String, Vec<String>> = HashMap::new();

    for start in graph.keys() {
        let mut visited: HashSet<String> = HashSet::new();
        let path = longest_path_from(start, graph, &mut visited, &mut memo);
        if path.len() >= MIN_CHAIN_NODE_COUNT {
            longest_paths.push(ImportChain {
                depth: path.len() - 1,
                modules: path,
            });
        }
    }

    longest_paths.sort_by(|a, b| b.depth.cmp(&a.depth));

    // Deduplicate — if a shorter chain is a suffix of a longer one, skip it
    let mut unique_chains: Vec<ImportChain> = Vec::new();
    for chain in longest_paths {
        let dominated = unique_chains.iter().any(|existing| {
            existing.modules.len() > chain.modules.len()
                && existing.modules.ends_with(&chain.modules)
        });
        if !dominated {
            unique_chains.push(chain);
        }
        if unique_chains.len() >= limit {
            break;
        }
    }

    unique_chains
}

/// Find the longest path from a node using DFS with memoization.
///
/// # Memoization limitation
///
/// Results are cached keyed only by `node`. When the same node is reached from
/// two different roots the first cached result is reused, even though the
/// `visited` set differs between the two calls. This means the cached result
/// may be shorter than what would be computed from a different root (because
/// some successors were marked visited in the first traversal). The trade-off
/// is acceptable: the memo avoids O(n²) worst-case work and the goal is
/// finding representative longest paths, not an exhaustive enumeration.
pub fn longest_path_from(
    node: &str,
    graph: &HashMap<String, HashSet<String>>,
    visited: &mut HashSet<String>,
    memo: &mut HashMap<String, Vec<String>>,
) -> Vec<String> {
    if let Some(cached) = memo.get(node) {
        return cached.clone();
    }

    visited.insert(node.to_string());

    let mut longest: Vec<String> = vec![node.to_string()];

    if let Some(neighbors) = graph.get(node) {
        for neighbor in neighbors {
            if !visited.contains(neighbor) {
                let sub_path = longest_path_from(neighbor, graph, visited, memo);
                if sub_path.len() + 1 > longest.len() {
                    let mut new_path = vec![node.to_string()];
                    new_path.extend(sub_path);
                    longest = new_path;
                }
            }
        }
    }

    visited.remove(node);
    memo.insert(node.to_string(), longest.clone());
    longest
}

// ---------------------------------------------------------------------------
// Top-level analysis function
// ---------------------------------------------------------------------------

/// Analyze graph-theoretic properties of an abstract dependency graph.
///
/// Takes an adjacency list (`HashMap<String, HashSet<String>>`) and a limit
/// for the number of items to return in each section. Pass `0` or `usize::MAX`
/// for no limit — `0` is treated as "unlimited" so callers do not accidentally
/// truncate all results to empty Vecs while stats counts still reflect the
/// full data (which would produce misleading reports). The `target` parameter
/// is recorded in the report for display.
pub fn analyze_graph_data(
    imports: &HashMap<String, HashSet<String>>,
    target: GraphTarget,
    limit: usize,
) -> GraphReport {
    // Treat 0 as "no limit" — callers should pass usize::MAX explicitly when
    // they want unlimited, but 0 is a common default and should not silently
    // truncate every result Vec to empty.
    let limit = if limit == 0 { usize::MAX } else { limit };
    let nodes = all_nodes(imports);
    let node_count = nodes.len();
    let edges = edge_count(imports);
    let density = if node_count > 1 {
        edges as f64 / (node_count as f64 * (node_count as f64 - 1.0))
    } else {
        0.0
    };

    let wcc = weakly_connected_components(imports);
    let wcc_count = wcc.len();
    let largest_component = wcc.first().map(|c| c.len()).unwrap_or(0);

    let all_sccs = tarjan_sccs(imports);
    let scc_count = all_sccs.len();
    let mut sccs = find_sccs(imports);
    let nontrivial_scc_count = sccs.len();

    let mut diamonds = find_diamonds(
        imports,
        if limit == usize::MAX {
            usize::MAX
        } else {
            limit * 10
        },
    );
    let diamond_count = diamonds.len();

    let bridges = find_bridges(imports);
    let bridge_count = bridges.len();

    let mut longest_chains = find_longest_chains(
        imports,
        if limit == usize::MAX {
            usize::MAX
        } else {
            limit
        },
    );
    let max_chain_depth = longest_chains.first().map(|c| c.depth).unwrap_or(0);
    let chain_count = longest_chains.len();

    let transitive_edge_count = count_transitive_edges(imports);
    let mut transitive_edges = find_transitive_edges(
        imports,
        if limit == usize::MAX {
            usize::MAX
        } else {
            limit
        },
    );

    let mut dead_nodes = find_dead_nodes(imports);
    let dead_node_count = dead_nodes.len();

    // Apply limits
    sccs.truncate(limit);
    diamonds.truncate(limit);
    longest_chains.truncate(limit);
    transitive_edges.truncate(limit);
    dead_nodes.truncate(limit);

    let stats = GraphStats {
        nodes: node_count,
        edges,
        density,
        weakly_connected_components: wcc_count,
        largest_component_size: largest_component,
        scc_count,
        nontrivial_scc_count,
        diamond_count,
        bridge_count,
        transitive_edge_count,
        max_chain_depth,
        chain_count,
        dead_node_count,
    };

    GraphReport {
        target,
        stats,
        sccs,
        diamonds,
        bridges,
        longest_chains,
        transitive_edges,
        dead_nodes,
    }
}

// ---------------------------------------------------------------------------
// Output formatting
// ---------------------------------------------------------------------------

fn truncate_path(path: &str, max_len: usize) -> String {
    if path.len() <= max_len {
        path.to_string()
    } else {
        // Use char_indices to find a safe character boundary, avoiding a byte-index
        // slice into a multi-byte UTF-8 sequence which would panic.
        let suffix = path
            .char_indices()
            .rev()
            .find(|(i, _)| path.len() - i <= max_len - 3)
            .map(|(i, _)| &path[i..])
            .unwrap_or(path);
        format!("...{}", suffix)
    }
}

impl OutputFormatter for GraphReport {
    fn format_text(&self) -> String {
        let mut out = Vec::new();
        let s = &self.stats;

        let label = match self.target {
            GraphTarget::Modules => "Module graph",
            GraphTarget::Symbols => "Symbol graph",
            GraphTarget::Types => "Type graph",
        };
        out.push(format!(
            "# {} — {} nodes, {} edges, density {:.3}",
            label, s.nodes, s.edges, s.density
        ));
        out.push(format!(
            "  {} weakly connected components (largest: {})",
            s.weakly_connected_components, s.largest_component_size
        ));
        out.push(format!(
            "  {} circular-dependency clusters, {} diamonds, {} bridges, {} transitive edges",
            s.nontrivial_scc_count, s.diamond_count, s.bridge_count, s.transitive_edge_count
        ));
        if s.max_chain_depth > 0 {
            out.push(format!(
                "  max chain depth {}, {} deep chains (depth > 2)",
                s.max_chain_depth, s.chain_count
            ));
        }
        if s.dead_node_count > 0 {
            out.push(format!(
                "  {} unreferenced nodes (no inbound edges)",
                s.dead_node_count
            ));
        }
        out.push(String::new());

        if s.nodes == 0 {
            out.push("No data found. Run `normalize structure rebuild` first.".to_string());
            return out.join("\n");
        }

        // SCCs
        if !self.sccs.is_empty() {
            out.push(format!(
                "## Circular dependency clusters ({} SCCs)",
                self.sccs.len()
            ));
            for scc in &self.sccs {
                let modules: Vec<String> =
                    scc.modules.iter().map(|m| truncate_path(m, 40)).collect();
                out.push(format!(
                    "  [{} modules, {} edges] {}",
                    scc.modules.len(),
                    scc.internal_edges,
                    modules.join(", ")
                ));
            }
            out.push(String::new());
        }

        // Diamonds
        if !self.diamonds.is_empty() {
            out.push(format!(
                "## Diamond dependencies ({} found)",
                self.stats.diamond_count
            ));
            for d in &self.diamonds {
                out.push(format!(
                    "  {} → {{{}, {}}} → {}",
                    truncate_path(&d.source, 30),
                    truncate_path(&d.left, 25),
                    truncate_path(&d.right, 25),
                    truncate_path(&d.target, 30),
                ));
            }
            out.push(String::new());
        }

        // Bridges
        if !self.bridges.is_empty() {
            out.push(format!(
                "## Bridge edges ({} critical dependencies)",
                self.bridges.len()
            ));
            for b in &self.bridges {
                out.push(format!(
                    "  {} → {}",
                    truncate_path(&b.from, 40),
                    truncate_path(&b.to, 40),
                ));
            }
            out.push(String::new());
        }

        // Longest chains
        if !self.longest_chains.is_empty() {
            out.push(format!(
                "## Deep import chains ({}, max depth {})",
                self.longest_chains.len(),
                self.stats.max_chain_depth
            ));
            for chain in &self.longest_chains {
                let short_modules: Vec<String> =
                    chain.modules.iter().map(|m| truncate_path(m, 30)).collect();
                out.push(format!(
                    "  [depth {}] {}",
                    chain.depth,
                    short_modules.join(" → ")
                ));
            }
            out.push(String::new());
        }

        // Transitive edges
        if !self.transitive_edges.is_empty() {
            let showing = if self.transitive_edges.len() < self.stats.transitive_edge_count {
                format!(" (showing {})", self.transitive_edges.len())
            } else {
                String::new()
            };
            out.push(format!(
                "## Transitive edges ({} redundant{})",
                self.stats.transitive_edge_count, showing
            ));
            for te in &self.transitive_edges {
                out.push(format!(
                    "  {} → {}  (via {})",
                    truncate_path(&te.from, 30),
                    truncate_path(&te.to, 30),
                    truncate_path(&te.via, 30),
                ));
            }
            out.push(String::new());
        }

        // Dead nodes (no inbound edges)
        if !self.dead_nodes.is_empty() {
            let label = match self.target {
                GraphTarget::Modules => "Unreferenced modules",
                GraphTarget::Symbols => "Uncalled symbols",
                GraphTarget::Types => "Unreferenced types",
            };
            out.push(format!(
                "## {} ({} nodes with no inbound edges)",
                label,
                self.dead_nodes.len()
            ));
            for node in &self.dead_nodes {
                out.push(format!("  {}", node));
            }
            out.push(String::new());
        }

        out.join("\n")
    }

    fn format_pretty(&self) -> String {
        let mut out = Vec::new();
        let s = &self.stats;

        let label = match self.target {
            GraphTarget::Modules => "Module graph",
            GraphTarget::Symbols => "Symbol graph",
            GraphTarget::Types => "Type graph",
        };
        out.push(format!(
            "\x1b[1;36m# {}\x1b[0m — \x1b[1m{}\x1b[0m nodes, \x1b[1m{}\x1b[0m edges, density \x1b[33m{:.3}\x1b[0m",
            label, s.nodes, s.edges, s.density
        ));
        out.push(format!(
            "  \x1b[32m{}\x1b[0m weakly connected components (largest: \x1b[1m{}\x1b[0m)",
            s.weakly_connected_components, s.largest_component_size
        ));

        let scc_color = if s.nontrivial_scc_count > 0 {
            "\x1b[1;31m"
        } else {
            "\x1b[32m"
        };
        let diamond_color = if s.diamond_count > 0 {
            "\x1b[33m"
        } else {
            "\x1b[32m"
        };
        let bridge_color = if s.bridge_count > 0 {
            "\x1b[1;33m"
        } else {
            "\x1b[32m"
        };
        let trans_color = if s.transitive_edge_count > 0 {
            "\x1b[33m"
        } else {
            "\x1b[32m"
        };

        out.push(format!(
            "  {}{}\x1b[0m circular-dependency clusters, {}{}\x1b[0m diamonds, {}{}\x1b[0m bridges, {}{}\x1b[0m transitive edges",
            scc_color, s.nontrivial_scc_count,
            diamond_color, s.diamond_count,
            bridge_color, s.bridge_count,
            trans_color, s.transitive_edge_count,
        ));
        if s.max_chain_depth > 0 {
            let depth_color = if s.max_chain_depth >= 5 {
                "\x1b[1;31m"
            } else if s.max_chain_depth >= 3 {
                "\x1b[33m"
            } else {
                "\x1b[32m"
            };
            out.push(format!(
                "  max chain depth {}{}\x1b[0m, {} deep chains (depth > 2)",
                depth_color, s.max_chain_depth, s.chain_count
            ));
        }
        if s.dead_node_count > 0 {
            out.push(format!(
                "  \x1b[2m{} unreferenced nodes (no inbound edges)\x1b[0m",
                s.dead_node_count
            ));
        }
        out.push(String::new());

        if s.nodes == 0 {
            out.push("No data found. Run `normalize structure rebuild` first.".to_string());
            return out.join("\n");
        }

        // SCCs
        if !self.sccs.is_empty() {
            out.push(format!(
                "\x1b[1;31m## Circular dependency clusters ({} SCCs)\x1b[0m",
                self.sccs.len()
            ));
            for scc in &self.sccs {
                let modules: Vec<String> =
                    scc.modules.iter().map(|m| truncate_path(m, 40)).collect();
                out.push(format!(
                    "  \x1b[31m[{} modules, {} edges]\x1b[0m {}",
                    scc.modules.len(),
                    scc.internal_edges,
                    modules.join(", ")
                ));
            }
            out.push(String::new());
        }

        // Diamonds
        if !self.diamonds.is_empty() {
            out.push(format!(
                "\x1b[1;33m## Diamond dependencies ({} found)\x1b[0m",
                self.stats.diamond_count
            ));
            for d in &self.diamonds {
                out.push(format!(
                    "  {} \x1b[33m→\x1b[0m {{{}, {}}} \x1b[33m→\x1b[0m {}",
                    truncate_path(&d.source, 30),
                    truncate_path(&d.left, 25),
                    truncate_path(&d.right, 25),
                    truncate_path(&d.target, 30),
                ));
            }
            out.push(String::new());
        }

        // Bridges
        if !self.bridges.is_empty() {
            out.push(format!(
                "\x1b[1;33m## Bridge edges ({} critical dependencies)\x1b[0m",
                self.bridges.len()
            ));
            for b in &self.bridges {
                out.push(format!(
                    "  {} \x1b[1;33m→\x1b[0m {}",
                    truncate_path(&b.from, 40),
                    truncate_path(&b.to, 40),
                ));
            }
            out.push(String::new());
        }

        // Longest chains
        if !self.longest_chains.is_empty() {
            out.push(format!(
                "\x1b[1m## Deep import chains ({}, max depth {})\x1b[0m",
                self.longest_chains.len(),
                self.stats.max_chain_depth
            ));
            for chain in &self.longest_chains {
                let short_modules: Vec<String> =
                    chain.modules.iter().map(|m| truncate_path(m, 30)).collect();
                let depth_color = if chain.depth >= 5 {
                    "\x1b[1;31m"
                } else if chain.depth >= 3 {
                    "\x1b[33m"
                } else {
                    "\x1b[32m"
                };
                out.push(format!(
                    "  {}[depth {}]\x1b[0m {}",
                    depth_color,
                    chain.depth,
                    short_modules.join(" \x1b[2m→\x1b[0m ")
                ));
            }
            out.push(String::new());
        }

        // Transitive edges
        if !self.transitive_edges.is_empty() {
            let showing = if self.transitive_edges.len() < self.stats.transitive_edge_count {
                format!(" (showing {})", self.transitive_edges.len())
            } else {
                String::new()
            };
            out.push(format!(
                "\x1b[33m## Transitive edges ({} redundant{})\x1b[0m",
                self.stats.transitive_edge_count, showing
            ));
            for te in &self.transitive_edges {
                out.push(format!(
                    "  {} → {}  \x1b[2m(via {})\x1b[0m",
                    truncate_path(&te.from, 30),
                    truncate_path(&te.to, 30),
                    truncate_path(&te.via, 30),
                ));
            }
            out.push(String::new());
        }

        // Dead nodes (no inbound edges)
        if !self.dead_nodes.is_empty() {
            let label = match self.target {
                GraphTarget::Modules => "Unreferenced modules",
                GraphTarget::Symbols => "Uncalled symbols",
                GraphTarget::Types => "Unreferenced types",
            };
            out.push(format!(
                "\x1b[2m## {} ({} with no inbound edges)\x1b[0m",
                label,
                self.dead_nodes.len()
            ));
            for node in &self.dead_nodes {
                out.push(format!("  \x1b[2m{}\x1b[0m", node));
            }
            out.push(String::new());
        }

        out.join("\n")
    }
}