_diffctx/

analytics.rs

use std::sync::Arc;

use rustc_hash::{FxHashMap, FxHashSet};

use crate::config::analytics::ANALYTICS;
use crate::graph::{EdgeCategory, Graph};
use crate::types::{Fragment, FragmentId};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum QuotientLevel {
    Fragment,
    File,
    Directory,
}

impl QuotientLevel {
    pub fn from_str(s: &str) -> Self {
        match s {
            "fragment" => Self::Fragment,
            "file" => Self::File,
            _ => Self::Directory,
        }
    }
}

#[derive(Debug, Clone)]
pub struct QuotientNode {
    pub key: Arc<str>,
    pub label: String,
    pub fragment_count: u32,
    pub token_count: u64,
    pub self_weight: f64,
}

#[derive(Debug, Clone)]
pub struct QuotientEdge {
    pub source: Arc<str>,
    pub target: Arc<str>,
    pub weight: f64,
    pub categories: FxHashMap<EdgeCategory, u32>,
}

#[derive(Debug, Clone)]
pub struct QuotientGraph {
    pub nodes: FxHashMap<Arc<str>, QuotientNode>,
    pub edges: FxHashMap<(Arc<str>, Arc<str>), QuotientEdge>,
    pub level: QuotientLevel,
}

impl QuotientGraph {
    pub fn new(level: QuotientLevel) -> Self {
        Self {
            nodes: FxHashMap::default(),
            edges: FxHashMap::default(),
            level,
        }
    }
}

#[derive(Debug, Clone)]
pub struct ModuleMetrics {
    pub name: Arc<str>,
    pub cohesion: f64,
    pub coupling: f64,
    pub instability: f64,
    pub fan_in: u32,
    pub fan_out: u32,
}

#[derive(Debug, Clone)]
pub struct HotspotEntry {
    pub path: Arc<str>,
    pub score: f64,
    pub out_degree: u32,
}

fn relative_path<'a>(path: &'a str, root: Option<&str>) -> &'a str {
    let root = match root {
        Some(r) if !r.is_empty() => r,
        _ => return path,
    };
    if let Some(stripped) = path.strip_prefix(root) {
        stripped.strip_prefix('/').unwrap_or(stripped)
    } else {
        path
    }
}

fn basename(s: &str) -> &str {
    s.rsplit('/').next().unwrap_or(s)
}

fn parent(s: &str) -> &str {
    match s.rfind('/') {
        Some(i) => &s[..i],
        None => "",
    }
}

fn group_key(fid: &FragmentId, level: QuotientLevel, root: Option<&str>) -> Arc<str> {
    let rel = relative_path(fid.path.as_ref(), root);
    match level {
        QuotientLevel::Fragment => {
            Arc::from(format!("{}:{}-{}", rel, fid.start_line, fid.end_line).as_str())
        }
        QuotientLevel::File => Arc::from(rel),
        QuotientLevel::Directory => {
            let p = parent(rel);
            if p.is_empty() {
                Arc::from(".")
            } else {
                Arc::from(p)
            }
        }
    }
}

fn node_label(fid: &FragmentId, frag: &Fragment, level: QuotientLevel, key: &str) -> String {
    match level {
        QuotientLevel::Fragment => {
            let bn = basename(fid.path.as_ref());
            if let Some(name) = frag.symbol_name.as_deref() {
                format!("{} ({}:{})", name, bn, fid.start_line)
            } else {
                format!("{}:{}-{}", bn, fid.start_line, fid.end_line)
            }
        }
        QuotientLevel::File => basename(fid.path.as_ref()).to_string(),
        QuotientLevel::Directory => {
            let trimmed = key.trim_end_matches('/');
            let bn = basename(trimmed);
            if bn.is_empty() {
                ".".to_string()
            } else {
                bn.to_string()
            }
        }
    }
}

fn iter_forward_edges<F: FnMut(&FragmentId, &FragmentId, f64)>(graph: &Graph, mut f: F) {
    let fwd = match graph.fwd_csr() {
        Some(c) => c,
        None => return,
    };
    for src_idx in 0..fwd.n {
        let s = fwd.indptr[src_idx] as usize;
        let e = fwd.indptr[src_idx + 1] as usize;
        let src = &fwd.idx_to_node[src_idx];
        for k in s..e {
            let dst_idx = fwd.indices[k] as usize;
            let dst = &fwd.idx_to_node[dst_idx];
            f(src, dst, fwd.weights[k]);
        }
    }
}

pub fn quotient_graph(
    graph: &Graph,
    fragments: &[Fragment],
    level: QuotientLevel,
    root: Option<&str>,
) -> QuotientGraph {
    let mut qg = QuotientGraph::new(level);

    let mut fid_to_group: FxHashMap<FragmentId, Arc<str>> = FxHashMap::default();
    for frag in fragments {
        let key = group_key(&frag.id, level, root);
        fid_to_group.insert(frag.id.clone(), key.clone());

        let entry = qg.nodes.entry(key.clone()).or_insert_with(|| QuotientNode {
            key: key.clone(),
            label: node_label(&frag.id, frag, level, key.as_ref()),
            fragment_count: 0,
            token_count: 0,
            self_weight: 0.0,
        });
        entry.fragment_count += 1;
        entry.token_count += u64::from(frag.token_count);
    }

    iter_forward_edges(graph, |src, dst, weight| {
        let src_key = match fid_to_group.get(src) {
            Some(k) => k.clone(),
            None => return,
        };
        let dst_key = match fid_to_group.get(dst) {
            Some(k) => k.clone(),
            None => return,
        };
        let cat = graph
            .edge_category(src, dst)
            .unwrap_or(EdgeCategory::Generic);

        if src_key == dst_key {
            if let Some(node) = qg.nodes.get_mut(&src_key) {
                node.self_weight += weight;
            }
        } else {
            let pair = (src_key.clone(), dst_key.clone());
            let edge = qg.edges.entry(pair).or_insert_with(|| QuotientEdge {
                source: src_key,
                target: dst_key,
                weight: 0.0,
                categories: FxHashMap::default(),
            });
            edge.weight += weight;
            *edge.categories.entry(cat).or_insert(0) += 1;
        }
    });

    qg
}

fn edge_matches_filter(edge: &QuotientEdge, filter: Option<&FxHashSet<EdgeCategory>>) -> bool {
    match filter {
        None => true,
        Some(f) => edge.categories.keys().any(|c| f.contains(c)),
    }
}

pub fn detect_cycles(
    graph: &Graph,
    fragments: &[Fragment],
    level: QuotientLevel,
    root: Option<&str>,
    edge_types: Option<&FxHashSet<EdgeCategory>>,
) -> Vec<Vec<Arc<str>>> {
    let qg = quotient_graph(graph, fragments, level, root);
    let mut node_ids: Vec<Arc<str>> = qg.nodes.keys().cloned().collect();
    node_ids.sort();
    let index_of: FxHashMap<Arc<str>, usize> = node_ids
        .iter()
        .enumerate()
        .map(|(i, k)| (k.clone(), i))
        .collect();

    let n = node_ids.len();
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
    for ((src, dst), edge) in &qg.edges {
        if !edge_matches_filter(edge, edge_types) {
            continue;
        }
        let si = index_of[src];
        let di = index_of[dst];
        adj[si].push(di);
    }

    tarjan_scc(&adj)
        .into_iter()
        .filter(|comp| comp.len() > 1)
        .map(|comp| comp.into_iter().map(|i| node_ids[i].clone()).collect())
        .collect()
}

struct TarjanState {
    index: usize,
    indices: Vec<Option<usize>>,
    lowlinks: Vec<usize>,
    on_stack: Vec<bool>,
    stack: Vec<usize>,
    components: Vec<Vec<usize>>,
}

fn tarjan_scc(adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
    let n = adj.len();
    let mut state = TarjanState {
        index: 0,
        indices: vec![None; n],
        lowlinks: vec![0; n],
        on_stack: vec![false; n],
        stack: Vec::new(),
        components: Vec::new(),
    };
    for v in 0..n {
        if state.indices[v].is_none() {
            strongconnect(v, adj, &mut state);
        }
    }
    state.components
}

fn strongconnect(v: usize, adj: &[Vec<usize>], state: &mut TarjanState) {
    let mut call_stack: Vec<(usize, usize)> = vec![(v, 0)];
    state.indices[v] = Some(state.index);
    state.lowlinks[v] = state.index;
    state.index += 1;
    state.stack.push(v);
    state.on_stack[v] = true;

    while let Some(&(node, iter_pos)) = call_stack.last() {
        if iter_pos < adj[node].len() {
            let w = adj[node][iter_pos];
            if let Some(last) = call_stack.last_mut() {
                last.1 += 1;
            }
            match state.indices[w] {
                None => {
                    state.indices[w] = Some(state.index);
                    state.lowlinks[w] = state.index;
                    state.index += 1;
                    state.stack.push(w);
                    state.on_stack[w] = true;
                    call_stack.push((w, 0));
                }
                Some(w_idx) => {
                    if state.on_stack[w] {
                        let cur = state.lowlinks[node];
                        state.lowlinks[node] = cur.min(w_idx);
                    }
                }
            }
        } else {
            let node_idx =
                state.indices[node].expect("node must have index when popping in tarjan");
            if state.lowlinks[node] == node_idx {
                let mut component = Vec::new();
                while let Some(w) = state.stack.pop() {
                    state.on_stack[w] = false;
                    component.push(w);
                    if w == node {
                        break;
                    }
                }
                state.components.push(component);
            }
            call_stack.pop();
            if let Some(&(parent, _)) = call_stack.last() {
                let combined = state.lowlinks[parent].min(state.lowlinks[node]);
                state.lowlinks[parent] = combined;
            }
        }
    }
}

pub fn coupling_metrics(
    graph: &Graph,
    fragments: &[Fragment],
    level: QuotientLevel,
    root: Option<&str>,
    edge_types: Option<&FxHashSet<EdgeCategory>>,
) -> Vec<ModuleMetrics> {
    let qg = quotient_graph(graph, fragments, level, root);

    let mut out_weight: FxHashMap<Arc<str>, f64> = FxHashMap::default();
    let mut in_weight: FxHashMap<Arc<str>, f64> = FxHashMap::default();
    let mut fan_in_set: FxHashMap<Arc<str>, FxHashSet<Arc<str>>> = FxHashMap::default();
    let mut fan_out_set: FxHashMap<Arc<str>, FxHashSet<Arc<str>>> = FxHashMap::default();

    for ((src, dst), edge) in &qg.edges {
        if !edge_matches_filter(edge, edge_types) {
            continue;
        }
        *out_weight.entry(src.clone()).or_insert(0.0) += edge.weight;
        *in_weight.entry(dst.clone()).or_insert(0.0) += edge.weight;
        fan_out_set
            .entry(src.clone())
            .or_default()
            .insert(dst.clone());
        fan_in_set
            .entry(dst.clone())
            .or_default()
            .insert(src.clone());
    }

    let mut keys: Vec<Arc<str>> = qg.nodes.keys().cloned().collect();
    keys.sort();

    let mut results = Vec::with_capacity(keys.len());
    for key in keys {
        let node = &qg.nodes[&key];
        let intra = node.self_weight;
        let inter = out_weight.get(&key).copied().unwrap_or(0.0)
            + in_weight.get(&key).copied().unwrap_or(0.0);
        let total = intra + inter;
        let cohesion = if total > 0.0 { intra / total } else { 0.0 };
        let coupling = if total > 0.0 { inter / total } else { 0.0 };
        let fi = fan_in_set.get(&key).map_or(0, |s| s.len()) as u32;
        let fo = fan_out_set.get(&key).map_or(0, |s| s.len()) as u32;
        let denom = fi + fo;
        let instability = if denom > 0 {
            f64::from(fo) / f64::from(denom)
        } else {
            0.0
        };

        results.push(ModuleMetrics {
            name: key,
            cohesion: round3(cohesion),
            coupling: round3(coupling),
            instability: round3(instability),
            fan_in: fi,
            fan_out: fo,
        });
    }

    results
}

pub fn hotspots(
    graph: &Graph,
    fragments: &[Fragment],
    top: usize,
    root: Option<&str>,
    edge_types: Option<&FxHashSet<EdgeCategory>>,
) -> Vec<HotspotEntry> {
    let mut file_frag_count: FxHashMap<Arc<str>, u32> = FxHashMap::default();
    for frag in fragments {
        let rel: Arc<str> = Arc::from(relative_path(frag.id.path.as_ref(), root));
        *file_frag_count.entry(rel).or_insert(0) += 1;
    }

    let mut out_deg: FxHashMap<Arc<str>, u32> = FxHashMap::default();
    graph.for_each_categorized_edge(|src, _dst, cat| {
        if let Some(filter) = edge_types
            && !filter.contains(&cat)
        {
            return;
        }
        let rel: Arc<str> = Arc::from(relative_path(src.path.as_ref(), root));
        *out_deg.entry(rel).or_insert(0) += 1;
    });

    let max_deg = out_deg.values().copied().max().unwrap_or(0).max(1);

    let mut scored: Vec<HotspotEntry> = file_frag_count
        .into_keys()
        .map(|file| {
            let deg = out_deg.get(&file).copied().unwrap_or(0);
            let deg_norm = f64::from(deg) / f64::from(max_deg);
            let score = round4(ANALYTICS.hotspot_degree_weight * deg_norm);
            HotspotEntry {
                path: file,
                score,
                out_degree: deg,
            }
        })
        .collect();

    scored.sort_by(|a, b| {
        b.score
            .partial_cmp(&a.score)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.path.as_ref().cmp(b.path.as_ref()))
    });
    scored.truncate(top);
    scored
}

// The mermaid text is a re-parsed protocol, not just a rendering artifact:
// `src/diffctx/_native/graph_analytics.py`'s `_MERMAID_NODE_LINE` regex
// (`^\s*(n\d+)\["(.*)"\]\s*$`) drives cycle detection by matching the quote
// that closes the label. A path or symbol name containing `"`, `[` or `]`
// (all legal on POSIX, and `[`/`]` are valid in most identifiers too) is
// also invalid inside a mermaid quoted label, so it can corrupt the whole
// diagram for a real mermaid renderer. Escape with mermaid's own `#NNN;`
// numeric-character-reference syntax so the label round-trips as plain text
// with no bare delimiter characters.
fn escape_mermaid_label(text: &str) -> String {
    let mut out = String::with_capacity(text.len());
    for ch in text.chars() {
        match ch {
            '#' => out.push_str("#35;"),
            '"' => out.push_str("#quot;"),
            '[' => out.push_str("#91;"),
            ']' => out.push_str("#93;"),
            other => out.push(other),
        }
    }
    out
}

pub fn to_mermaid(qg: &QuotientGraph, top_n: usize) -> String {
    if qg.nodes.is_empty() {
        return "graph LR\n".to_string();
    }

    let mut node_total_weight: FxHashMap<Arc<str>, f64> = FxHashMap::default();
    for node in qg.nodes.values() {
        node_total_weight.insert(node.key.clone(), node.self_weight);
    }
    for edge in qg.edges.values() {
        if let Some(v) = node_total_weight.get_mut(&edge.source) {
            *v += edge.weight;
        }
        if let Some(v) = node_total_weight.get_mut(&edge.target) {
            *v += edge.weight;
        }
    }

    let mut sorted_nodes: Vec<&QuotientNode> = qg.nodes.values().collect();
    sorted_nodes.sort_by(|a, b| {
        let aw = node_total_weight.get(&a.key).copied().unwrap_or(0.0);
        let bw = node_total_weight.get(&b.key).copied().unwrap_or(0.0);
        bw.partial_cmp(&aw)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.key.as_ref().cmp(b.key.as_ref()))
    });
    sorted_nodes.truncate(top_n);

    let node_keys: FxHashSet<Arc<str>> = sorted_nodes.iter().map(|n| n.key.clone()).collect();
    let node_ids: FxHashMap<Arc<str>, String> = sorted_nodes
        .iter()
        .enumerate()
        .map(|(i, n)| (n.key.clone(), format!("n{i}")))
        .collect();

    let mut lines: Vec<String> = vec!["graph LR".to_string()];
    for node in &sorted_nodes {
        let nid = &node_ids[&node.key];
        let trimmed = node.key.trim_end_matches('/');
        let fallback = if trimmed.is_empty() { "root" } else { trimmed };
        let label = if node.label.is_empty() {
            fallback
        } else {
            node.label.as_str()
        };
        let label = escape_mermaid_label(label);
        lines.push(format!("    {nid}[\"{label}\"]"));
    }

    let mut sorted_edges: Vec<&QuotientEdge> = qg.edges.values().collect();
    sorted_edges.sort_by(|a, b| {
        b.weight
            .partial_cmp(&a.weight)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then_with(|| a.source.as_ref().cmp(b.source.as_ref()))
            .then_with(|| a.target.as_ref().cmp(b.target.as_ref()))
    });

    for edge in sorted_edges {
        if !node_keys.contains(&edge.source) || !node_keys.contains(&edge.target) {
            continue;
        }
        let src_id = &node_ids[&edge.source];
        let dst_id = &node_ids[&edge.target];
        let top_cat = edge
            .categories
            .iter()
            .max_by_key(|&(_, count)| *count)
            .map_or("?", |(c, _)| category_name(*c));
        let weight_str = format_weight(edge.weight);
        lines.push(format!(
            "    {src_id} -->|\"{top_cat}: {weight_str}\"| {dst_id}"
        ));
    }

    let mut out = lines.join("\n");
    out.push('\n');
    out
}

fn category_name(c: EdgeCategory) -> &'static str {
    match c {
        EdgeCategory::Semantic => "semantic",
        EdgeCategory::Structural => "structural",
        EdgeCategory::Sibling => "sibling",
        EdgeCategory::Config => "config",
        EdgeCategory::ConfigGeneric => "config_generic",
        EdgeCategory::Document => "document",
        EdgeCategory::Similarity => "similarity",
        EdgeCategory::History => "history",
        EdgeCategory::TestEdge => "test_edge",
        EdgeCategory::Generic => "generic",
    }
}

fn format_weight(w: f64) -> String {
    if (w - w.round()).abs() < f64::EPSILON {
        format!("{}", w as i64)
    } else {
        format!("{w:.1}")
    }
}

fn round3(v: f64) -> f64 {
    (v * 1000.0).round() / 1000.0
}

fn round4(v: f64) -> f64 {
    (v * 10000.0).round() / 10000.0
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::types::FragmentKind;
    use regex::Regex;

    fn fid(path: &str, start: u32, end: u32) -> FragmentId {
        FragmentId::new(Arc::from(path), start, end)
    }

    fn frag(path: &str, start: u32, end: u32, tokens: u32) -> Fragment {
        Fragment {
            id: fid(path, start, end),
            kind: FragmentKind::Function,
            content: Arc::from(""),
            identifiers: FxHashSet::default(),
            token_count: tokens,
            symbol_name: None,
        }
    }

    fn build(
        edges: &[(FragmentId, FragmentId, f64, EdgeCategory)],
        fragments: &[Fragment],
    ) -> Graph {
        let mut g = Graph::new();
        for f in fragments {
            g.add_node(f.id.clone());
        }
        for (s, d, w, c) in edges {
            g.add_edge(s.clone(), d.clone(), *w);
            g.insert_edge_category(s.clone(), d.clone(), *c);
        }
        g.freeze();
        g
    }

    #[test]
    fn detect_cycles_finds_simple_loop() {
        let frags = vec![
            frag("pkg/a.rs", 1, 5, 10),
            frag("pkg/b.rs", 1, 5, 10),
            frag("pkg/c.rs", 1, 5, 10),
            frag("pkg/d.rs", 1, 5, 10),
        ];
        let edges = vec![
            (
                frags[0].id.clone(),
                frags[1].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[1].id.clone(),
                frags[2].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[2].id.clone(),
                frags[0].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[2].id.clone(),
                frags[3].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
        ];
        let g = build(&edges, &frags);
        let cycles = detect_cycles(&g, &frags, QuotientLevel::File, None, None);
        assert_eq!(cycles.len(), 1);
        let c: FxHashSet<&str> = cycles[0].iter().map(|s| s.as_ref()).collect();
        assert!(c.contains("pkg/a.rs"));
        assert!(c.contains("pkg/b.rs"));
        assert!(c.contains("pkg/c.rs"));
        assert!(!c.contains("pkg/d.rs"));
    }

    #[test]
    fn hotspots_returns_top_k_sorted() {
        let frags = vec![
            frag("a.rs", 1, 5, 10),
            frag("b.rs", 1, 5, 10),
            frag("c.rs", 1, 5, 10),
        ];
        let edges = vec![
            (
                frags[0].id.clone(),
                frags[1].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[0].id.clone(),
                frags[2].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[1].id.clone(),
                frags[2].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
        ];
        let g = build(&edges, &frags);
        let hs = hotspots(&g, &frags, 2, None, None);
        assert_eq!(hs.len(), 2);
        assert_eq!(hs[0].path.as_ref(), "a.rs");
        assert!(hs[0].score >= hs[1].score);
    }

    #[test]
    fn coupling_metrics_disconnected_zero_coupling() {
        let frags = vec![frag("dirA/a.rs", 1, 5, 10), frag("dirB/b.rs", 1, 5, 10)];
        let edges: Vec<(FragmentId, FragmentId, f64, EdgeCategory)> = Vec::new();
        let g = build(&edges, &frags);
        let metrics = coupling_metrics(&g, &frags, QuotientLevel::Directory, None, None);
        assert_eq!(metrics.len(), 2);
        for m in &metrics {
            assert!((m.cohesion - 0.0).abs() < 1e-9);
            assert!((m.coupling - 0.0).abs() < 1e-9);
            assert_eq!(m.fan_in, 0);
            assert_eq!(m.fan_out, 0);
        }
    }

    #[test]
    fn quotient_graph_trivial_partition_collapses_to_directories() {
        let frags = vec![
            frag("dirA/a.rs", 1, 5, 100),
            frag("dirA/b.rs", 1, 5, 50),
            frag("dirB/c.rs", 1, 5, 200),
        ];
        let edges = vec![
            (
                frags[0].id.clone(),
                frags[1].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[0].id.clone(),
                frags[2].id.clone(),
                2.0,
                EdgeCategory::Semantic,
            ),
        ];
        let g = build(&edges, &frags);
        let qg = quotient_graph(&g, &frags, QuotientLevel::Directory, None);
        assert_eq!(qg.nodes.len(), 2);
        let dir_a: Arc<str> = Arc::from("dirA");
        let dir_b: Arc<str> = Arc::from("dirB");
        assert!(qg.nodes.contains_key(&dir_a));
        assert!(qg.nodes.contains_key(&dir_b));
        assert_eq!(qg.nodes[&dir_a].fragment_count, 2);
        assert_eq!(qg.nodes[&dir_a].token_count, 150);
        assert!((qg.nodes[&dir_a].self_weight - 1.0).abs() < 1e-9);
        let cross = (dir_a.clone(), dir_b.clone());
        assert!(qg.edges.contains_key(&cross));
        assert!((qg.edges[&cross].weight - 2.0).abs() < 1e-9);
    }

    #[test]
    fn mermaid_round_trip_contains_nodes_and_edges() {
        let frags = vec![frag("dirA/a.rs", 1, 5, 10), frag("dirB/b.rs", 1, 5, 10)];
        let edges = vec![(
            frags[0].id.clone(),
            frags[1].id.clone(),
            3.0,
            EdgeCategory::Structural,
        )];
        let g = build(&edges, &frags);
        let qg = quotient_graph(&g, &frags, QuotientLevel::Directory, None);
        let mermaid = to_mermaid(&qg, 20);
        assert!(mermaid.starts_with("graph LR"));
        assert!(mermaid.contains("dirA"));
        assert!(mermaid.contains("dirB"));
        assert!(mermaid.contains("structural: 3"));
        assert!(mermaid.ends_with('\n'));
    }

    #[test]
    fn mermaid_escapes_quotes_and_brackets_in_node_labels() {
        // Mirrors `src/diffctx/_native/graph_analytics.py`'s
        // `_MERMAID_NODE_LINE = re.compile(r'^\s*(n\d+)\["(.*)"\]\s*$')`,
        // which re-parses this text to drive cycle detection.
        let mermaid_node_line = Regex::new(r#"^\s*(n\d+)\["(.*)"\]\s*$"#).unwrap();

        let frags = vec![frag("src/say\"hi\"[x].rs", 1, 10, 7)];
        let g = build(&[], &frags);
        let qg = quotient_graph(&g, &frags, QuotientLevel::File, None);
        let mermaid = to_mermaid(&qg, 20);

        let node_line = mermaid
            .lines()
            .find(|l| l.contains("n0"))
            .expect("node line for n0 must be present");
        let caps = mermaid_node_line
            .captures(node_line)
            .unwrap_or_else(|| panic!("node line does not match mermaid grammar: {node_line:?}"));
        let label = &caps[2];
        assert!(
            !label.contains('"'),
            "escaped label still contains a bare quote: {label:?}"
        );
    }

    #[test]
    fn mermaid_empty_graph() {
        let qg = QuotientGraph::new(QuotientLevel::Directory);
        assert_eq!(to_mermaid(&qg, 20), "graph LR\n");
    }

    #[test]
    fn detect_cycles_respects_edge_type_filter() {
        let frags = vec![frag("a.rs", 1, 5, 10), frag("b.rs", 1, 5, 10)];
        let edges = vec![
            (
                frags[0].id.clone(),
                frags[1].id.clone(),
                1.0,
                EdgeCategory::Semantic,
            ),
            (
                frags[1].id.clone(),
                frags[0].id.clone(),
                1.0,
                EdgeCategory::History,
            ),
        ];
        let g = build(&edges, &frags);

        let mut filter = FxHashSet::default();
        filter.insert(EdgeCategory::Semantic);
        let cycles = detect_cycles(&g, &frags, QuotientLevel::File, None, Some(&filter));
        assert!(cycles.is_empty());

        let cycles_all = detect_cycles(&g, &frags, QuotientLevel::File, None, None);
        assert_eq!(cycles_all.len(), 1);
    }
}