//! BFS graph traversal for impact analysis

use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};
use std::sync::Arc;
use std::sync::OnceLock;

use crate::store::CallGraph;

/// Maximum nodes in any reverse BFS traversal.
/// Prevents unbounded expansion on hub functions with thousands of transitive callers.
const DEFAULT_BFS_MAX_NODES: usize = 10_000;

/// Returns the BFS node cap, reading `CQS_IMPACT_MAX_NODES` once on first call.
pub(super) fn bfs_max_nodes() -> usize {
    static CAP: OnceLock<usize> = OnceLock::new();
    *CAP.get_or_init(|| match std::env::var("CQS_IMPACT_MAX_NODES") {
        Ok(val) => match val.parse::<usize>() {
            Ok(n) if n > 0 => {
                tracing::info!(cap = n, "BFS node cap overridden via CQS_IMPACT_MAX_NODES");
                n
            }
            _ => {
                tracing::warn!(
                    val,
                    "CQS_IMPACT_MAX_NODES invalid, using default {DEFAULT_BFS_MAX_NODES}"
                );
                DEFAULT_BFS_MAX_NODES
            }
        },
        Err(_) => DEFAULT_BFS_MAX_NODES,
    })
}

/// Reverse BFS from a target node, returning all ancestors with their depths.
///
/// The target itself is always included at depth 0. Callers that need only
/// actual ancestors should filter out depth-0 entries.
///
/// Expansion stops when either `max_depth` or `bfs_max_nodes()` is reached.
///
/// When `max_depth == 0`, returns only the target node at depth 0 (no traversal).
///
/// Keys are `Arc<str>` so the BFS reuses the already-interned names from
/// `graph.reverse` instead of allocating a fresh `String` per visit. On a hub
/// function with thousands of transitive callers (default cap = 10k), this is
/// an `Arc::clone` (RC bump only) per visit rather than a `caller.to_string()`
/// heap allocation. Lookup callers can still index by `&str` because
/// `Arc<str>: Borrow<str>`.
pub(super) fn reverse_bfs(
    graph: &CallGraph,
    target: &str,
    max_depth: usize,
) -> HashMap<Arc<str>, usize> {
    let mut ancestors: HashMap<Arc<str>, usize> = HashMap::new();
    let mut queue: VecDeque<(Arc<str>, usize)> = VecDeque::new();
    let target_arc: Arc<str> = Arc::from(target);
    ancestors.insert(Arc::clone(&target_arc), 0);
    queue.push_back((target_arc, 0));

    while let Some((current, d)) = queue.pop_front() {
        // Defensive stale-queue skip mirrored from reverse_bfs_multi.
        // reverse_bfs is correct today because BFS visits depths in
        // non-decreasing order, but a future change that pushes back
        // already-seen nodes at a shorter depth would silently regress
        // without this guard.
        if let Some(&stored) = ancestors.get(current.as_ref()) {
            if d > stored {
                continue;
            }
        }
        if d >= max_depth {
            continue;
        }
        if ancestors.len() >= bfs_max_nodes() {
            tracing::warn!(
                target,
                nodes = ancestors.len(),
                "reverse_bfs hit node cap, returning partial results"
            );
            break;
        }
        if let Some(callers) = graph.reverse.get(current.as_ref()) {
            for caller in callers {
                if ancestors.len() >= bfs_max_nodes() {
                    break;
                }
                if !ancestors.contains_key(caller.as_ref()) {
                    ancestors.insert(Arc::clone(caller), d + 1);
                    queue.push_back((Arc::clone(caller), d + 1));
                }
            }
        }
    }

    ancestors
}

/// Forward BFS from multiple source nodes, returning the set of every node
/// reachable through forward call edges. The sources themselves are
/// **excluded** from the returned set unless one of them is reached as a
/// callee from another source (test-calls-test).
///
/// This is the forward dual of `reverse_bfs` used by `suggest_tests`: instead
/// of calling `reverse_bfs(graph, caller)` once per caller and asking "is any
/// test in the ancestor map?", we BFS forward from every test once and ask
/// "is the caller in the reachable set?". Total work drops from
/// `O(callers × graph)` to `O(tests + edges)` — single graph traversal
/// instead of N.
///
/// Depth-bounded by `max_depth` (each source's BFS independently) and
/// node-count-bounded by `bfs_max_nodes()`.
pub(super) fn forward_bfs_multi(
    graph: &CallGraph,
    sources: &[&str],
    max_depth: usize,
) -> HashSet<Arc<str>> {
    let mut reachable: HashSet<Arc<str>> = HashSet::new();
    let mut queue: VecDeque<(Arc<str>, usize)> = VecDeque::new();

    // Seed with the source keys (interned) at depth 0. Sources do NOT enter
    // `reachable` directly — that matches `reverse_bfs(caller, _).get(test)
    // .is_some_and(|d| d > 0)` semantics in the call site we're replacing.
    // If one source happens to be a callee of another, it gets added to
    // `reachable` during expansion, which is correct (test A calls test B
    // ⇒ B is "covered by A").
    for src in sources {
        if let Some((k, _)) = graph.forward.get_key_value(*src) {
            queue.push_back((Arc::clone(k), 0));
        }
    }

    while let Some((current, d)) = queue.pop_front() {
        if d >= max_depth {
            continue;
        }
        if reachable.len() >= bfs_max_nodes() {
            tracing::warn!(
                nodes = reachable.len(),
                "forward_bfs_multi hit node cap, returning partial results"
            );
            break;
        }
        if let Some(callees) = graph.forward.get(current.as_ref()) {
            for callee in callees {
                if reachable.len() >= bfs_max_nodes() {
                    break;
                }
                if reachable.insert(Arc::clone(callee)) {
                    queue.push_back((Arc::clone(callee), d + 1));
                }
            }
        }
    }

    reachable
}

/// Multi-source reverse BFS from multiple target nodes simultaneously.
///
/// Instead of calling `reverse_bfs()` N times (one per changed function),
/// starts BFS from all targets at once. Each node gets the minimum depth
/// from any starting node. Returns ancestors with their minimum depths.
///
/// Production code uses `reverse_bfs_multi_attributed` instead (same traversal
/// but also tracks which source produced each path). Kept for tests.
///
/// Same `Arc<str>` rationale as [`reverse_bfs`].
#[cfg(test)]
pub(super) fn reverse_bfs_multi(
    graph: &CallGraph,
    targets: &[&str],
    max_depth: usize,
) -> HashMap<Arc<str>, usize> {
    let mut ancestors: HashMap<Arc<str>, usize> = HashMap::new();
    let mut queue: VecDeque<(Arc<str>, usize)> = VecDeque::new();

    for &target in targets {
        let arc: Arc<str> = Arc::from(target);
        ancestors.insert(Arc::clone(&arc), 0);
        queue.push_back((arc, 0));
    }

    while let Some((current, d)) = queue.pop_front() {
        if d >= max_depth {
            continue;
        }
        if ancestors.len() >= bfs_max_nodes() {
            tracing::warn!(
                nodes = ancestors.len(),
                "reverse_bfs_multi hit node cap, returning partial results"
            );
            break;
        }
        // Skip stale queue entries: if this node was later reached via a
        // shorter path, the HashMap already has a smaller depth. Processing
        // the stale entry would propagate incorrect (longer) depths downstream.
        if ancestors.get(&current).is_some_and(|&stored| d > stored) {
            continue;
        }
        if let Some(callers) = graph.reverse.get(current.as_ref()) {
            for caller in callers {
                if ancestors.len() >= bfs_max_nodes() {
                    break;
                }
                match ancestors.entry(Arc::clone(caller)) {
                    std::collections::hash_map::Entry::Vacant(e) => {
                        e.insert(d + 1);
                        queue.push_back((Arc::clone(caller), d + 1));
                    }
                    std::collections::hash_map::Entry::Occupied(mut e) => {
                        // Update if we found a shorter path
                        if d + 1 < *e.get() {
                            *e.get_mut() = d + 1;
                            queue.push_back((Arc::clone(caller), d + 1));
                        }
                    }
                }
            }
        }
    }

    ancestors
}

/// Multi-source reverse BFS that tracks which target (by index) first reached each node.
///
/// Like [`reverse_bfs_multi`], starts BFS from all targets simultaneously and records
/// minimum depth. Additionally tracks which target index produced the shortest path to
/// each node, enabling per-source attribution without separate BFS calls.
///
/// Returns `HashMap<node_name, (min_depth, source_index)>` where `source_index` is
/// the index into `targets` that first reached the node at minimum depth.
///
/// Keys are `Arc<str>` so the BFS reuses the already-interned names from
/// `graph.reverse`. See [`reverse_bfs`] for the full rationale.
pub(super) fn reverse_bfs_multi_attributed(
    graph: &CallGraph,
    targets: &[&str],
    max_depth: usize,
) -> HashMap<Arc<str>, (usize, usize)> {
    // (depth, source_index)
    let mut ancestors: HashMap<Arc<str>, (usize, usize)> = HashMap::new();
    // Queue entries: (node_name, depth, source_index)
    let mut queue: VecDeque<(Arc<str>, usize, usize)> = VecDeque::new();

    for (idx, &target) in targets.iter().enumerate() {
        let arc: Arc<str> = Arc::from(target);
        match ancestors.entry(Arc::clone(&arc)) {
            std::collections::hash_map::Entry::Vacant(e) => {
                e.insert((0, idx));
                queue.push_back((arc, 0, idx));
            }
            std::collections::hash_map::Entry::Occupied(_) => {
                // Duplicate target name — first occurrence wins at depth 0
            }
        }
    }

    while let Some((current, d, src)) = queue.pop_front() {
        if d >= max_depth {
            continue;
        }
        if ancestors.len() >= bfs_max_nodes() {
            tracing::warn!(
                nodes = ancestors.len(),
                "reverse_bfs_multi_attributed hit node cap, returning partial results"
            );
            break;
        }
        // Skip stale queue entries (same logic as reverse_bfs_multi)
        if ancestors
            .get(&current)
            .is_some_and(|&(stored_d, _)| d > stored_d)
        {
            continue;
        }
        if let Some(callers) = graph.reverse.get(current.as_ref()) {
            for caller in callers {
                if ancestors.len() >= bfs_max_nodes() {
                    break;
                }
                match ancestors.entry(Arc::clone(caller)) {
                    std::collections::hash_map::Entry::Vacant(e) => {
                        e.insert((d + 1, src));
                        queue.push_back((Arc::clone(caller), d + 1, src));
                    }
                    std::collections::hash_map::Entry::Occupied(mut e) => {
                        if d + 1 < e.get().0 {
                            *e.get_mut() = (d + 1, src);
                            queue.push_back((Arc::clone(caller), d + 1, src));
                        }
                    }
                }
            }
        }
    }

    ancestors
}

/// Build a test reachability map via forward BFS from all test nodes.
///
/// Walks forward edges (caller -> callee) from each test node, collecting
/// all functions reachable within `max_depth` hops. Returns a map of
/// `function_name -> count of tests that reach it`.
///
/// **Optimization:** Tests with identical first-hop callee sets
/// produce identical reachable sets (beyond the test node itself). We group
/// tests into equivalence classes by their direct callees and BFS once per
/// unique class, multiplying counts by the class size.
///
/// **Limitation:** Equivalence classes are based solely on first-hop callees.
/// Two tests that call different functions which converge at depth 2+ are
/// treated as separate classes, so BFS runs once per class rather than being
/// shared. Counts are approximate — tests with identical direct callees share
/// BFS results, which may over-count when transitive paths diverge.
pub(crate) fn test_reachability(
    graph: &CallGraph,
    test_names: &[&str],
    max_depth: usize,
) -> HashMap<Arc<str>, usize> {
    let _span = tracing::info_span!("test_reachability", tests = test_names.len()).entered();
    // Keys are `Arc<str>` so each visit/merge is an `Arc::clone` (RC bump)
    // rather than a `callee.to_string()` heap allocation — the same interning
    // rationale as `reverse_bfs`/`forward_bfs_multi`. The graph's node names are
    // already interned `Arc<str>`, so we clone those keys via `get_key_value`.
    // Callers index by `&str` because `Arc<str>: Borrow<str>`.
    let mut counts: HashMap<Arc<str>, usize> = HashMap::new();

    // Step 1: Group tests by their first-hop callee set.
    // Tests with the same direct callees will traverse the same subgraph
    // (forward BFS from depth 1 onward is identical), so we only BFS once.
    let mut equivalence_classes: HashMap<BTreeSet<&str>, usize> = HashMap::new();
    for &test_name in test_names {
        let callees: BTreeSet<&str> = graph
            .forward
            .get(test_name)
            .map(|v| v.iter().map(|s| s.as_ref()).collect())
            .unwrap_or_default();
        *equivalence_classes.entry(callees).or_default() += 1;
    }

    // Step 2: BFS once per unique callee set, multiply counts by class size.
    let mut visited: HashMap<Arc<str>, usize> = HashMap::new();
    let mut queue: VecDeque<(Arc<str>, usize)> = VecDeque::new();

    for (callee_set, class_size) in &equivalence_classes {
        if callee_set.is_empty() {
            // Tests with no callees reach nothing — skip BFS entirely
            continue;
        }

        // Reuse allocations: clear instead of reallocating
        visited.clear();
        queue.clear();

        // Seed BFS from the shared callees at depth 1 (the test node itself
        // is excluded from counts, so we start at depth 1 directly). Reuse the
        // interned key from `graph.forward` when the callee is a key there
        // (i.e. has outgoing edges); a leaf callee falls back to `Arc::from`.
        for &callee in callee_set {
            let arc = intern_node(graph, callee);
            visited.insert(Arc::clone(&arc), 1);
            queue.push_back((arc, 1));
        }

        while let Some((current, d)) = queue.pop_front() {
            if d >= max_depth {
                continue;
            }
            if visited.len() >= bfs_max_nodes() {
                tracing::warn!(
                    nodes = visited.len(),
                    "test_reachability BFS hit node cap, returning partial results"
                );
                break;
            }
            if let Some(callees) = graph.forward.get(current.as_ref()) {
                for callee in callees {
                    if visited.len() >= bfs_max_nodes() {
                        break;
                    }
                    if !visited.contains_key(callee.as_ref()) {
                        visited.insert(Arc::clone(callee), d + 1);
                        queue.push_back((Arc::clone(callee), d + 1));
                    }
                }
            }
        }

        // Every function visited is reachable from all tests in this class
        for name in visited.keys() {
            *counts.entry(Arc::clone(name)).or_default() += class_size;
        }
    }

    counts
}

/// Return the interned `Arc<str>` for `name` from the graph's forward map when
/// present (nodes with outgoing edges), else allocate a fresh `Arc`. Lets the
/// BFS reuse the graph's existing interning for the common case.
fn intern_node(graph: &CallGraph, name: &str) -> Arc<str> {
    match graph.forward.get_key_value(name) {
        Some((k, _)) => Arc::clone(k),
        None => Arc::from(name),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashMap;

    #[test]
    fn test_reverse_bfs_empty_graph() {
        let graph = CallGraph::from_string_maps(HashMap::new(), HashMap::new());
        let result = reverse_bfs(&graph, "target", 5);
        assert_eq!(result.len(), 1); // Just the target itself at depth 0
        assert_eq!(result["target"], 0);
    }

    #[test]
    fn test_reverse_bfs_chain() {
        let mut reverse = HashMap::new();
        reverse.insert("C".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);
        let result = reverse_bfs(&graph, "C", 5);
        assert_eq!(result["C"], 0);
        assert_eq!(result["B"], 1);
        assert_eq!(result["A"], 2);
    }

    #[test]
    fn test_reverse_bfs_respects_depth() {
        let mut reverse = HashMap::new();
        reverse.insert("C".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);
        let result = reverse_bfs(&graph, "C", 1);
        assert_eq!(result.len(), 2); // C at 0, B at 1
        assert!(!result.contains_key("A")); // Beyond depth limit
    }

    // ===== reverse_bfs_multi tests =====

    #[test]
    fn test_reverse_bfs_multi_empty_targets() {
        let graph = CallGraph::from_string_maps(HashMap::new(), HashMap::new());
        let result = reverse_bfs_multi(&graph, &[], 5);
        assert!(
            result.is_empty(),
            "Empty targets should produce empty result"
        );
    }

    #[test]
    fn test_reverse_bfs_multi_non_overlapping_ancestors() {
        // Two separate call chains with no shared ancestors:
        //   A -> B -> target1
        //   C -> D -> target2
        let mut reverse = HashMap::new();
        reverse.insert("target1".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        reverse.insert("target2".to_string(), vec!["D".to_string()]);
        reverse.insert("D".to_string(), vec!["C".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi(&graph, &["target1", "target2"], 5);

        // Both targets at depth 0
        assert_eq!(result["target1"], 0);
        assert_eq!(result["target2"], 0);
        // All ancestors found
        assert_eq!(result["B"], 1);
        assert_eq!(result["A"], 2);
        assert_eq!(result["D"], 1);
        assert_eq!(result["C"], 2);
        assert_eq!(result.len(), 6); // 2 targets + 4 ancestors
    }

    #[test]
    fn test_reverse_bfs_multi_shared_ancestor() {
        // Shared caller reaches both targets at different depths:
        //   shared -> mid -> target1
        //   shared -> target2
        let mut reverse = HashMap::new();
        reverse.insert("target1".to_string(), vec!["mid".to_string()]);
        reverse.insert("mid".to_string(), vec!["shared".to_string()]);
        reverse.insert("target2".to_string(), vec!["shared".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi(&graph, &["target1", "target2"], 5);

        assert_eq!(result["target1"], 0);
        assert_eq!(result["target2"], 0);
        assert_eq!(result["mid"], 1);
        // shared is at depth 1 from target2 and depth 2 from target1
        // Multi-source BFS should record minimum depth = 1
        assert_eq!(
            result["shared"], 1,
            "Shared ancestor should get minimum depth across all sources"
        );
    }

    #[test]
    fn test_reverse_bfs_multi_depth_limit() {
        // Chain: A -> B -> C -> target1, D -> target2
        // With depth limit 1, should only find immediate callers
        let mut reverse = HashMap::new();
        reverse.insert("target1".to_string(), vec!["C".to_string()]);
        reverse.insert("C".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        reverse.insert("target2".to_string(), vec!["D".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi(&graph, &["target1", "target2"], 1);

        assert_eq!(result["target1"], 0);
        assert_eq!(result["target2"], 0);
        assert_eq!(result["C"], 1, "Direct caller of target1 should be found");
        assert_eq!(result["D"], 1, "Direct caller of target2 should be found");
        assert!(
            !result.contains_key("B"),
            "B is at depth 2 from target1, beyond limit"
        );
        assert!(
            !result.contains_key("A"),
            "A is at depth 3 from target1, beyond limit"
        );
    }

    #[test]
    fn test_reverse_bfs_multi_single_target_matches_reverse_bfs() {
        // With a single target, multi should produce the same result as single
        let mut reverse = HashMap::new();
        reverse.insert("C".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let single = reverse_bfs(&graph, "C", 5);
        let multi = reverse_bfs_multi(&graph, &["C"], 5);

        assert_eq!(
            single, multi,
            "Single-target multi should match reverse_bfs"
        );
    }

    #[test]
    fn test_reverse_bfs_multi_diamond_graph() {
        // Diamond: A -> B, A -> C, B -> D, C -> D
        // Starting from D: should find B(1), C(1), A(2)
        // Starting from both D and B: D(0), B(0), C(1), A(1)
        let mut reverse = HashMap::new();
        reverse.insert("D".to_string(), vec!["B".to_string(), "C".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        reverse.insert("C".to_string(), vec!["A".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi(&graph, &["D", "B"], 5);

        assert_eq!(result["D"], 0);
        assert_eq!(result["B"], 0); // Target, so depth 0
        assert_eq!(result["C"], 1); // Caller of D
        assert_eq!(
            result["A"], 1,
            "A is at depth 1 from B (target), not depth 2 from D"
        );
    }

    #[test]
    fn test_reverse_bfs_multi_stale_queue_entry() {
        // Regression: stale queue entries must not propagate wrong depths.
        //
        // Graph (reverse edges, i.e., "who calls"):
        //   target1 <- mid <- deep   (chain: deep calls mid calls target1)
        //   target2 <- deep          (deep also calls target2 directly)
        //
        // Multi-BFS from [target1, target2]:
        //   - "deep" is first reached at depth 2 via target1 <- mid <- deep
        //   - "deep" is then reached at depth 1 via target2 <- deep
        //   - Without the stale-entry fix, the queue still has (deep, 2) which
        //     would propagate depth 3 to deep's callers instead of depth 2.
        let mut reverse = HashMap::new();
        reverse.insert("target1".to_string(), vec!["mid".to_string()]);
        reverse.insert("mid".to_string(), vec!["deep".to_string()]);
        reverse.insert("target2".to_string(), vec!["deep".to_string()]);
        reverse.insert("deep".to_string(), vec!["root".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi(&graph, &["target1", "target2"], 5);

        assert_eq!(result["target1"], 0);
        assert_eq!(result["target2"], 0);
        assert_eq!(result["mid"], 1);
        assert_eq!(
            result["deep"], 1,
            "deep should be depth 1 (from target2), not 2 (from target1->mid)"
        );
        assert_eq!(
            result["root"], 2,
            "root should be depth 2 (deep+1), not 3 (from stale queue entry)"
        );
    }

    // ===== reverse_bfs_multi_attributed tests =====

    #[test]
    fn test_attributed_empty_targets() {
        let graph = CallGraph::from_string_maps(HashMap::new(), HashMap::new());
        let result = reverse_bfs_multi_attributed(&graph, &[], 5);
        assert!(result.is_empty());
    }

    #[test]
    fn test_attributed_single_target() {
        // Chain: A -> B -> target
        let mut reverse = HashMap::new();
        reverse.insert("target".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi_attributed(&graph, &["target"], 5);

        assert_eq!(result["target"], (0, 0));
        assert_eq!(result["B"], (1, 0));
        assert_eq!(result["A"], (2, 0));
    }

    #[test]
    fn test_attributed_two_sources_separate_chains() {
        // A -> target0, B -> target1 (no overlap)
        let mut reverse = HashMap::new();
        reverse.insert("target0".to_string(), vec!["A".to_string()]);
        reverse.insert("target1".to_string(), vec!["B".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi_attributed(&graph, &["target0", "target1"], 5);

        assert_eq!(result["target0"], (0, 0));
        assert_eq!(result["target1"], (0, 1));
        assert_eq!(result["A"], (1, 0));
        assert_eq!(result["B"], (1, 1));
    }

    #[test]
    fn test_attributed_shared_ancestor_gets_closest_source() {
        // shared -> mid -> target0  (depth 2 from target0)
        // shared -> target1         (depth 1 from target1)
        // shared should be attributed to target1 (index 1) at depth 1
        let mut reverse = HashMap::new();
        reverse.insert("target0".to_string(), vec!["mid".to_string()]);
        reverse.insert("mid".to_string(), vec!["shared".to_string()]);
        reverse.insert("target1".to_string(), vec!["shared".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi_attributed(&graph, &["target0", "target1"], 5);

        assert_eq!(result["shared"].0, 1, "min depth is 1 from target1");
        assert_eq!(result["shared"].1, 1, "attributed to target1 (index 1)");
    }

    #[test]
    fn test_attributed_depth_matches_multi() {
        // Verify depths agree with reverse_bfs_multi
        let mut reverse = HashMap::new();
        reverse.insert("target0".to_string(), vec!["mid".to_string()]);
        reverse.insert("mid".to_string(), vec!["shared".to_string()]);
        reverse.insert("target1".to_string(), vec!["shared".to_string()]);
        reverse.insert("shared".to_string(), vec!["root".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);
        let targets = &["target0", "target1"];

        let multi = reverse_bfs_multi(&graph, targets, 5);
        let attributed = reverse_bfs_multi_attributed(&graph, targets, 5);

        for (name, &depth) in &multi {
            assert_eq!(
                attributed[name].0, depth,
                "depth mismatch for {name}: multi={depth}, attributed={}",
                attributed[name].0
            );
        }
        assert_eq!(multi.len(), attributed.len());
    }

    #[test]
    fn test_attributed_stale_queue_entry() {
        // Same graph as test_reverse_bfs_multi_stale_queue_entry
        // target1 <- mid <- deep, target2 <- deep, deep <- root
        let mut reverse = HashMap::new();
        reverse.insert("target1".to_string(), vec!["mid".to_string()]);
        reverse.insert("mid".to_string(), vec!["deep".to_string()]);
        reverse.insert("target2".to_string(), vec!["deep".to_string()]);
        reverse.insert("deep".to_string(), vec!["root".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi_attributed(&graph, &["target1", "target2"], 5);

        assert_eq!(result["deep"].0, 1, "depth 1 from target2");
        assert_eq!(result["deep"].1, 1, "attributed to target2 (index 1)");
        assert_eq!(result["root"].0, 2, "root at depth 2, not 3");
        assert_eq!(result["root"].1, 1, "root attributed via target2's chain");
    }

    #[test]
    fn test_attributed_depth_limit() {
        // A -> B -> C -> target0, D -> target1 with depth limit 1
        let mut reverse = HashMap::new();
        reverse.insert("target0".to_string(), vec!["C".to_string()]);
        reverse.insert("C".to_string(), vec!["B".to_string()]);
        reverse.insert("B".to_string(), vec!["A".to_string()]);
        reverse.insert("target1".to_string(), vec!["D".to_string()]);
        let graph = CallGraph::from_string_maps(HashMap::new(), reverse);

        let result = reverse_bfs_multi_attributed(&graph, &["target0", "target1"], 1);

        assert_eq!(result["C"], (1, 0));
        assert_eq!(result["D"], (1, 1));
        assert!(!result.contains_key("B"), "B beyond depth limit");
        assert!(!result.contains_key("A"), "A beyond depth limit");
    }

    // ===== test_reachability tests =====

    #[test]
    fn test_reachability_empty_graph() {
        let graph = CallGraph::from_string_maps(HashMap::new(), HashMap::new());
        let result = test_reachability(&graph, &["test_a"], 5);
        assert!(
            result.is_empty(),
            "No forward edges means nothing reachable"
        );
    }

    #[test]
    fn test_reachability_single_test() {
        // test_a -> B -> C
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["B".to_string()]);
        forward.insert("B".to_string(), vec!["C".to_string()]);
        let graph = CallGraph::from_string_maps(forward, HashMap::new());
        let result = test_reachability(&graph, &["test_a"], 5);
        assert_eq!(result.get("B"), Some(&1), "B reachable from test_a");
        assert_eq!(result.get("C"), Some(&1), "C reachable from test_a");
        assert!(
            !result.contains_key("test_a"),
            "Test itself excluded (depth 0)"
        );
    }

    #[test]
    fn test_reachability_multiple_tests_shared_target() {
        // test_a -> target, test_b -> target
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["target".to_string()]);
        forward.insert("test_b".to_string(), vec!["target".to_string()]);
        let graph = CallGraph::from_string_maps(forward, HashMap::new());
        let result = test_reachability(&graph, &["test_a", "test_b"], 5);
        assert_eq!(
            result.get("target"),
            Some(&2),
            "target reachable from both tests"
        );
    }

    #[test]
    fn test_reachability_respects_depth() {
        // test_a -> B -> C -> D
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["B".to_string()]);
        forward.insert("B".to_string(), vec!["C".to_string()]);
        forward.insert("C".to_string(), vec!["D".to_string()]);
        let graph = CallGraph::from_string_maps(forward, HashMap::new());
        let result = test_reachability(&graph, &["test_a"], 2);
        assert_eq!(result.get("B"), Some(&1), "B at depth 1");
        assert_eq!(result.get("C"), Some(&1), "C at depth 2");
        assert!(!result.contains_key("D"), "D beyond depth limit");
    }

    // ===== forward_bfs_multi tests =====

    /// Helper: build a graph from forward edges; reverse is auto-derived so
    /// we can compare `reverse_bfs` and `forward_bfs_multi` on the same shape.
    fn graph_with_forward(forward: HashMap<String, Vec<String>>) -> CallGraph {
        let mut reverse: HashMap<String, Vec<String>> = HashMap::new();
        for (caller, callees) in &forward {
            for callee in callees {
                reverse
                    .entry(callee.clone())
                    .or_default()
                    .push(caller.clone());
            }
        }
        CallGraph::from_string_maps(forward, reverse)
    }

    #[test]
    fn forward_bfs_multi_empty_sources() {
        let graph = CallGraph::from_string_maps(HashMap::new(), HashMap::new());
        let result = forward_bfs_multi(&graph, &[], 5);
        assert!(result.is_empty(), "no sources => no reachable nodes");
    }

    #[test]
    fn forward_bfs_multi_excludes_source_itself() {
        // test_a -> B
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["B".to_string()]);
        let graph = graph_with_forward(forward);

        let result = forward_bfs_multi(&graph, &["test_a"], 5);
        assert!(
            !result.contains("test_a"),
            "source must NOT be in reachable set (no self-coverage)"
        );
        assert!(result.contains("B"), "B reachable from test_a");
    }

    #[test]
    fn forward_bfs_multi_chain() {
        // test_a -> B -> C -> D
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["B".to_string()]);
        forward.insert("B".to_string(), vec!["C".to_string()]);
        forward.insert("C".to_string(), vec!["D".to_string()]);
        let graph = graph_with_forward(forward);

        let result = forward_bfs_multi(&graph, &["test_a"], 5);
        assert!(result.contains("B"));
        assert!(result.contains("C"));
        assert!(result.contains("D"));
        assert_eq!(result.len(), 3, "B, C, D reachable; test_a excluded");
    }

    #[test]
    fn forward_bfs_multi_respects_depth() {
        // test_a -> B -> C -> D
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["B".to_string()]);
        forward.insert("B".to_string(), vec!["C".to_string()]);
        forward.insert("C".to_string(), vec!["D".to_string()]);
        let graph = graph_with_forward(forward);

        let result = forward_bfs_multi(&graph, &["test_a"], 2);
        assert!(result.contains("B"), "B at depth 1");
        assert!(result.contains("C"), "C at depth 2");
        assert!(!result.contains("D"), "D at depth 3, beyond limit");
    }

    #[test]
    fn forward_bfs_multi_test_calls_test_includes_callee() {
        // test_a -> test_b -> X
        // Both are sources. test_b is a callee of test_a, so it should appear
        // in reachable (covered by test_a).
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["test_b".to_string()]);
        forward.insert("test_b".to_string(), vec!["X".to_string()]);
        let graph = graph_with_forward(forward);

        let result = forward_bfs_multi(&graph, &["test_a", "test_b"], 5);
        assert!(
            result.contains("test_b"),
            "test_b is reached as test_a's callee"
        );
        assert!(result.contains("X"));
        assert!(
            !result.contains("test_a"),
            "test_a never appears as anyone's callee in this graph"
        );
    }

    /// Parity check: for the suggest_tests use case (one caller, one test),
    /// forward_bfs_multi must agree with the reverse_bfs predicate
    ///   `reverse_bfs(caller).get(test).is_some_and(|d| d > 0)`.
    #[test]
    fn forward_bfs_multi_parity_with_reverse_bfs_predicate() {
        // Graph: test_a -> mid -> caller_x; test_b -> caller_y; orphan_z
        let mut forward = HashMap::new();
        forward.insert("test_a".to_string(), vec!["mid".to_string()]);
        forward.insert("mid".to_string(), vec!["caller_x".to_string()]);
        forward.insert("test_b".to_string(), vec!["caller_y".to_string()]);
        let graph = graph_with_forward(forward);

        let tests = ["test_a", "test_b"];
        let reachable = forward_bfs_multi(&graph, &tests, 5);

        for caller in ["caller_x", "caller_y", "orphan_z", "mid"] {
            let ancestors = reverse_bfs(&graph, caller, 5);
            let prior_is_tested = tests
                .iter()
                .any(|t| ancestors.get(*t).is_some_and(|&d| d > 0));
            let new_is_tested = reachable.contains(caller);
            assert_eq!(
                prior_is_tested, new_is_tested,
                "parity mismatch for caller {caller}: reverse_bfs={prior_is_tested}, forward_bfs={new_is_tested}"
            );
        }
    }
}
