memstead_base/graph/

query.rs

//! BFS reachability search and orphan/stub detection.

use std::cmp::Ordering;
use std::collections::{HashMap, HashSet, VecDeque};

use schemars::JsonSchema;

use crate::entity::EntityId;
use crate::store::{EdgeSource, InEdge, Store};

/// Traversal direction relative to the seed, applied at EVERY hop —
/// depth > 1 is a pure transitive closure in the chosen direction,
/// never a mixed walk (an entity reachable only by alternating
/// directions is not in an `out` or `in` result at any depth; that
/// per-hop property is what makes a fall-through analysis correct).
///
/// `in`/`out` describe the edge relative to the seed and match the
/// Store's own vocabulary — domain words (ancestors/upstream) invert
/// per schema, so the engine does not use them.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, Default, serde::Serialize, serde::Deserialize, JsonSchema,
)]
#[serde(rename_all = "lowercase")]
pub enum TraversalDirection {
    /// Follow edges pointing away from the seed (seed → target).
    Out,
    /// Follow edges pointing at the seed (source → seed).
    In,
    /// Follow both — the historical undirected walk, and the default:
    /// a query that omits the selector returns exactly what it always
    /// returned.
    #[default]
    Both,
}

impl TraversalDirection {
    /// Does this walk follow outgoing edges?
    fn follows_out(self) -> bool {
        !matches!(self, TraversalDirection::In)
    }
    /// Does this walk follow incoming edges?
    fn follows_in(self) -> bool {
        !matches!(self, TraversalDirection::Out)
    }
}

/// Returns each reached entity's hop-distance from `from` — the depth at
/// which BFS first reaches it (`from` itself is 0), following only edges
/// admitted by `direction` at every hop. The distances drive proximity
/// ranking of a `related_to` neighbourhood: nearer first.
pub fn reachable_distances(
    store: &Store,
    from: &EntityId,
    max_depth: usize,
    direction: TraversalDirection,
) -> HashMap<EntityId, usize> {
    let mut dist: HashMap<EntityId, usize> = HashMap::new();
    dist.insert(from.clone(), 0);

    let mut queue: VecDeque<(EntityId, usize)> = VecDeque::new();
    queue.push_back((from.clone(), 0));

    while let Some((id, depth)) = queue.pop_front() {
        if depth >= max_depth {
            continue;
        }
        if direction.follows_out() {
            for edge in store.outgoing(&id) {
                if !dist.contains_key(&edge.target) {
                    dist.insert(edge.target.clone(), depth + 1);
                    queue.push_back((edge.target.clone(), depth + 1));
                }
            }
        }
        if direction.follows_in() {
            for edge in store.incoming(&id) {
                if !dist.contains_key(&edge.from) {
                    dist.insert(edge.from.clone(), depth + 1);
                    queue.push_back((edge.from.clone(), depth + 1));
                }
            }
        }
    }
    dist
}

/// One entity reached by [`reachable_via`]: the edge label it was first
/// reached by, the depth of that first reach (1 = direct neighbour), and
/// the direction that reaching edge was traversed in — so a `both` walk
/// stays interpretable per hit.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReachedVia {
    pub id: EntityId,
    pub via_edge: String,
    pub depth: usize,
    /// The direction of the FIRST-reaching edge: `Out` when it points
    /// away from the entity we walked from, `In` when it points at it.
    /// Never `Both` — a concrete edge has one traversal direction.
    pub direction: TraversalDirection,
}

/// Find all entities reachable from `from` by walking only edges whose
/// `rel_type` is in `edge_types`, up to `max_depth` hops, following only
/// edges admitted by `direction` at every hop. Returns one
/// [`ReachedVia`] per reached entity — never `from` itself.
///
/// `max_depth == 0` or an empty `edge_types` returns an empty vec.
///
/// This is the graph-expansion primitive behind `SearchScope.expand_via`.
pub fn reachable_via(
    store: &Store,
    from: &EntityId,
    edge_types: &[String],
    max_depth: usize,
    direction: TraversalDirection,
) -> Vec<ReachedVia> {
    if max_depth == 0 || edge_types.is_empty() {
        return Vec::new();
    }

    let mut visited: HashSet<EntityId> = HashSet::new();
    visited.insert(from.clone());

    let mut results: Vec<ReachedVia> = Vec::new();
    let mut queue: VecDeque<(EntityId, usize)> = VecDeque::new();
    queue.push_back((from.clone(), 0));

    while let Some((id, depth)) = queue.pop_front() {
        if depth >= max_depth {
            continue;
        }
        if direction.follows_out() {
            for edge in store.outgoing(&id) {
                if !edge_types.iter().any(|t| t == &edge.rel_type) {
                    continue;
                }
                if visited.insert(edge.target.clone()) {
                    results.push(ReachedVia {
                        id: edge.target.clone(),
                        via_edge: edge.rel_type.clone(),
                        depth: depth + 1,
                        direction: TraversalDirection::Out,
                    });
                    queue.push_back((edge.target.clone(), depth + 1));
                }
            }
        }
        if direction.follows_in() {
            for edge in store.incoming(&id) {
                if !edge_types.iter().any(|t| t == &edge.rel_type) {
                    continue;
                }
                if visited.insert(edge.from.clone()) {
                    results.push(ReachedVia {
                        id: edge.from.clone(),
                        via_edge: edge.rel_type.clone(),
                        depth: depth + 1,
                        direction: TraversalDirection::In,
                    });
                    queue.push_back((edge.from.clone(), depth + 1));
                }
            }
        }
    }

    results
}

/// Would adding an edge `from --rel_type--> to` close a cycle in the
/// subgraph restricted to edges of `rel_type`? Returns the back-path as
/// `[to, …, from]` when a cycle exists, `None` otherwise.
///
/// A self-loop (`from == to`) is a length-1 cycle and is reported without
/// a BFS. Otherwise this walks forward from `to` along outgoing edges
/// whose `rel_type` matches, looking for `from`. Cost is O(edges of that
/// rel_type) in the worst case.
pub fn would_cycle(
    store: &Store,
    from: &EntityId,
    to: &EntityId,
    rel_type: &str,
) -> Option<Vec<EntityId>> {
    if from == to {
        return Some(vec![from.clone()]);
    }

    let mut parent: std::collections::HashMap<EntityId, EntityId> =
        std::collections::HashMap::new();
    let mut visited: HashSet<EntityId> = HashSet::new();
    visited.insert(to.clone());

    let mut queue: VecDeque<EntityId> = VecDeque::new();
    queue.push_back(to.clone());

    while let Some(current) = queue.pop_front() {
        for edge in store.outgoing(&current) {
            if edge.rel_type != rel_type {
                continue;
            }
            let next = &edge.target;
            if *next == *from {
                let mut path = vec![from.clone(), current.clone()];
                let mut cursor = current;
                while let Some(p) = parent.get(&cursor) {
                    path.push(p.clone());
                    cursor = p.clone();
                }
                path.reverse();
                return Some(path);
            }
            if visited.insert(next.clone()) {
                parent.insert(next.clone(), current.clone());
                queue.push_back(next.clone());
            }
        }
    }
    None
}

/// Set variant of [`would_cycle`]: walks the UNION subgraph of the
/// declared acyclicity set, so the returned back-path may mix
/// rel-types. Returns the path (same shape as `would_cycle`) plus one
/// rel-type per hop of the path (`len == path.len() - 1`; empty for
/// the self-loop case).
pub fn would_cycle_in_set(
    store: &Store,
    from: &EntityId,
    to: &EntityId,
    set: &[String],
) -> Option<(Vec<EntityId>, Vec<String>)> {
    if from == to {
        return Some((vec![from.clone()], Vec::new()));
    }

    // child -> (parent, rel-type of the parent -> child edge)
    let mut parent: std::collections::HashMap<EntityId, (EntityId, String)> =
        std::collections::HashMap::new();
    let mut visited: HashSet<EntityId> = HashSet::new();
    visited.insert(to.clone());

    let mut queue: VecDeque<EntityId> = VecDeque::new();
    queue.push_back(to.clone());

    while let Some(current) = queue.pop_front() {
        for edge in store.outgoing(&current) {
            if !set.iter().any(|n| n == &edge.rel_type) {
                continue;
            }
            let next = &edge.target;
            if *next == *from {
                let mut ids = vec![current.clone()];
                let mut rels = vec![edge.rel_type.clone()];
                let mut cursor = current.clone();
                while let Some((p, r)) = parent.get(&cursor) {
                    ids.push(p.clone());
                    rels.push(r.clone());
                    cursor = p.clone();
                }
                ids.reverse();
                rels.reverse();
                ids.push(from.clone());
                return Some((ids, rels));
            }
            if visited.insert(next.clone()) {
                parent.insert(next.clone(), (current.clone(), edge.rel_type.clone()));
                queue.push_back(next.clone());
            }
        }
    }
    None
}

/// Find orphan entities — non-stub entities with no edges at all (completely isolated).
pub fn find_orphans(store: &Store) -> Vec<EntityId> {
    find_orphans_with_schemas(store, &std::collections::HashMap::new())
}

/// Schema-aware orphan scan: like [`find_orphans`], but entities whose
/// type declares `leaf: true` in their mem's schema are exempt — a
/// leaf is edge-less BY CONSTRUCTION, so counting it as an orphan is
/// noise that masks real orphans (agent-trust plan 06). The exempted
/// population stays visible through [`leaf_population`]. An empty
/// schema map (tests, ad-hoc callers) reproduces the schema-blind
/// behaviour exactly.
pub fn find_orphans_with_schemas(
    store: &Store,
    schemas: &std::collections::HashMap<String, std::sync::Arc<memstead_schema::Schema>>,
) -> Vec<EntityId> {
    let mut results = Vec::new();
    for entity in store.all_entities() {
        if entity.stub {
            continue;
        }
        if entity_is_declared_leaf(entity, schemas) {
            continue;
        }
        let out = store.outgoing(&entity.id);
        let inc = store.incoming(&entity.id);
        if out.is_empty() && inc.is_empty() {
            results.push(entity.id.clone());
        }
    }
    // The store iterates a hash map: order by id so every renderer
    // (CLI, MCP) emits the same bytes.
    results.sort_by(|a, b| a.0.cmp(&b.0));
    results
}

/// Whether `entity`'s type declares `leaf: true` in its mem's schema.
fn entity_is_declared_leaf(
    entity: &crate::entity::Entity,
    schemas: &std::collections::HashMap<String, std::sync::Arc<memstead_schema::Schema>>,
) -> bool {
    schemas
        .get(entity.mem.as_str())
        .and_then(|s| s.types.get(&entity.entity_type))
        .is_some_and(|t| t.leaf)
}

/// The leaf population health reports beside the orphan axis: for
/// every leaf-declared type with at least one real entity, the count
/// of its entities, keyed `<schema_ref>:<type>`. Visible, never
/// vanished — the reader still sees the population the orphan
/// exemption covers.
pub fn leaf_population(
    store: &Store,
    schemas: &std::collections::HashMap<String, std::sync::Arc<memstead_schema::Schema>>,
) -> std::collections::BTreeMap<String, usize> {
    let mut out: std::collections::BTreeMap<String, usize> = std::collections::BTreeMap::new();
    for entity in store.all_entities() {
        if entity.stub {
            continue;
        }
        if let Some(schema) = schemas.get(entity.mem.as_str())
            && schema
                .types
                .get(&entity.entity_type)
                .is_some_and(|t| t.leaf)
        {
            let (name, version) = schema.id();
            *out.entry(format!("{name}@{version}:{}", entity.entity_type))
                .or_default() += 1;
        }
    }
    out
}

/// Find stub entities — entities created from unresolved references.
/// Returns each stub with the list of entities that reference it.
/// Deterministic: stubs sorted by id, referrers sorted within each —
/// the store iterates a HashMap, so without the sorts two identical
/// runs can serve the same list in different orders.
pub fn find_stubs(store: &Store) -> Vec<(EntityId, Vec<EntityId>)> {
    let mut results = Vec::new();
    for entity in store.all_entities() {
        if !entity.stub {
            continue;
        }
        let mut referenced_by: Vec<EntityId> = store
            .incoming(&entity.id)
            .iter()
            .map(|e| e.from.clone())
            .collect();
        referenced_by.sort_by(|a, b| a.0.cmp(&b.0));
        results.push((entity.id.clone(), referenced_by));
    }
    results.sort_by(|a, b| a.0.0.cmp(&b.0.0));
    results
}

/// One entity's degree counts. `total == incoming + outgoing`; kept explicit
/// so the JSON wire shape is self-describing and callers don't re-derive it.
///
/// `typed_*` excludes auto-emitted mention edges (`EdgeSource::BodyLink` —
/// the `[[wiki-link]]` → REFERENCES alias-synthesis pass) so centrality can
/// rank by declared dependency rather than co-mention. Auto-emitted mentions
/// are the bulk of all edges, so `total` (which keeps them) is dominated by
/// co-mention; `typed_total` is the dependency degree. The raw `total` is
/// retained — the mention edges are not dropped from the graph, only set
/// aside for ranking. Mention degree is `total - typed_total`.
/// Stubs are never included in `most_connected` results.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Connectivity {
    pub id: EntityId,
    pub total: usize,
    pub incoming: usize,
    pub outgoing: usize,
    pub typed_total: usize,
    pub typed_incoming: usize,
    pub typed_outgoing: usize,
}

/// Compute one entity's raw and typed degree. `incoming_counts` decides
/// which incoming edges contribute (e.g. source-in-mem scoping for a
/// mem-filtered health view); every outgoing edge always counts. Typed
/// degree excludes `EdgeSource::BodyLink` (auto-emitted mention) edges.
pub fn connectivity_for(
    store: &Store,
    id: &EntityId,
    incoming_counts: impl Fn(&InEdge) -> bool,
) -> Connectivity {
    let out = store.outgoing(id);
    let outgoing = out.len();
    let typed_outgoing = out
        .iter()
        .filter(|e| e.source != EdgeSource::BodyLink)
        .count();

    let mut incoming = 0;
    let mut typed_incoming = 0;
    for e in store.incoming(id) {
        if !incoming_counts(e) {
            continue;
        }
        incoming += 1;
        if e.source != EdgeSource::BodyLink {
            typed_incoming += 1;
        }
    }

    Connectivity {
        id: id.clone(),
        total: outgoing + incoming,
        incoming,
        outgoing,
        typed_total: typed_outgoing + typed_incoming,
        typed_incoming,
        typed_outgoing,
    }
}

/// Centrality ordering: dependency degree (`typed_total`) descending first,
/// then raw `total` descending, then `id` lexicographic ascending as a
/// stable deterministic tie-break. Ranking by `typed_total` keeps a
/// co-mention-inflated hub from outranking a real dependency hub.
pub fn cmp_by_dependency(a: &Connectivity, b: &Connectivity) -> Ordering {
    b.typed_total
        .cmp(&a.typed_total)
        .then_with(|| b.total.cmp(&a.total))
        .then_with(|| a.id.0.cmp(&b.id.0))
}

/// Find the most connected non-stub entities, ranked by dependency degree
/// (typed edges) — see [`cmp_by_dependency`]. Returns up to `limit` entries.
pub fn most_connected(store: &Store, limit: usize) -> Vec<Connectivity> {
    let mut entries: Vec<Connectivity> = store
        .all_entities()
        .filter(|e| !e.stub)
        .map(|e| connectivity_for(store, &e.id, |_| true))
        .collect();

    entries.sort_by(cmp_by_dependency);
    entries.truncate(limit);
    entries
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::entity::Entity;
    use crate::store::{Edge, EdgeSource};
    use indexmap::IndexMap;

    fn entity(id: &str, mem: &str, stub: bool) -> Entity {
        Entity {
            id: EntityId(id.to_string()),
            title: id.to_string(),
            entity_type: "spec".to_string(),
            mem: mem.to_string(),
            file_path: String::new(),
            metadata: IndexMap::new(),
            sections: IndexMap::new(),
            relationships: Vec::new(),
            content_hash: String::new(),
            stub,
            stub_kind: if stub {
                Some(crate::entity::StubKind::LoadTime)
            } else {
                None
            },
            heading_spans: std::collections::HashMap::new(),
            raw_section_headings: Vec::new(),
        }
    }

    fn add_edge(store: &mut Store, from: &str, to: &str, rel: &str) {
        store.add_edge(
            EntityId(from.to_string()),
            Edge {
                rel_type: rel.to_string(),
                target: EntityId(to.to_string()),
                source: EdgeSource::Explicit,
            },
        );
    }

    /// An auto-emitted mention edge (the `[[wiki-link]]` → REFERENCES
    /// alias-synthesis pass), marked `EdgeSource::BodyLink` — excluded
    /// from the typed (dependency) degree.
    fn add_body_edge(store: &mut Store, from: &str, to: &str) {
        store.add_edge(
            EntityId(from.to_string()),
            Edge {
                rel_type: "REFERENCES".to_string(),
                target: EntityId(to.to_string()),
                source: EdgeSource::BodyLink,
            },
        );
    }

    fn build_linear_store() -> Store {
        // A -> B -> C
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        store.upsert(EntityId("c".into()), entity("c", "s", false));
        add_edge(&mut store, "a", "b", "USES");
        add_edge(&mut store, "b", "c", "USES");
        store
    }

    #[test]
    fn reachable_distances_within_depth() {
        let store = build_linear_store();
        let a = EntityId("a".into());
        let both = TraversalDirection::Both;

        assert_eq!(reachable_distances(&store, &a, 0, both).len(), 1); // just self
        assert_eq!(reachable_distances(&store, &a, 1, both).len(), 2); // a + b
        assert_eq!(reachable_distances(&store, &a, 2, both).len(), 3); // a + b + c
    }

    #[test]
    fn reachable_distances_both_is_undirected() {
        let store = build_linear_store();
        let c = EntityId("c".into());
        // From C, `both` still walks backwards via incoming edges.
        let r = reachable_distances(&store, &c, 10, TraversalDirection::Both);
        assert_eq!(r.len(), 3);
    }

    /// The per-hop property the feature exists for: on a chain
    /// x --> seed --> y --> z, `out` from the seed is exactly {seed, y,
    /// z} at depth 2+, `in` exactly {seed, x} — and an entity reachable
    /// only by ALTERNATING directions (w, via seed <- x -> w) is in
    /// neither directed result at any depth, because depth > 1 is a
    /// pure transitive closure, never a mixed walk.
    #[test]
    fn reachable_distances_directional_transitive_closure() {
        let mut store = Store::new();
        for id in ["x", "seed", "y", "z", "w"] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        add_edge(&mut store, "x", "seed", "USES");
        add_edge(&mut store, "seed", "y", "USES");
        add_edge(&mut store, "y", "z", "USES");
        add_edge(&mut store, "x", "w", "USES"); // reachable only via in-then-out

        let seed = EntityId("seed".into());
        let ids = |m: &HashMap<EntityId, usize>| {
            let mut v: Vec<String> = m.keys().map(|i| i.0.clone()).collect();
            v.sort();
            v
        };

        let out = reachable_distances(&store, &seed, 10, TraversalDirection::Out);
        assert_eq!(
            ids(&out),
            ["seed", "y", "z"],
            "out = transitive descendants only"
        );

        let inward = reachable_distances(&store, &seed, 10, TraversalDirection::In);
        assert_eq!(
            ids(&inward),
            ["seed", "x"],
            "in = transitive ancestors only"
        );

        let both = reachable_distances(&store, &seed, 10, TraversalDirection::Both);
        assert_eq!(
            ids(&both),
            ["seed", "w", "x", "y", "z"],
            "both = the historical undirected set, mixed walks included"
        );
    }

    #[test]
    fn find_orphans_isolated_node() {
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        add_edge(&mut store, "a", "b", "USES");
        store.upsert(EntityId("c".into()), entity("c", "s", false));
        // c has no edges

        let orphans = find_orphans(&store);
        assert_eq!(orphans.len(), 1);
        assert_eq!(orphans[0], EntityId("c".into()));
    }

    #[test]
    fn find_orphans_skips_stubs() {
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", true)); // stub, isolated
        store.upsert(EntityId("b".into()), entity("b", "s", false)); // non-stub, isolated

        let orphans = find_orphans(&store);
        assert_eq!(orphans.len(), 1);
        assert_eq!(orphans[0], EntityId("b".into()));
    }

    #[test]
    fn find_stubs_returns_stub_entities() {
        let mut store = Store::new();
        store.upsert(EntityId("real".into()), entity("real", "s", false));
        store.upsert(EntityId("stub1".into()), entity("stub1", "s", true));
        add_edge(&mut store, "real", "stub1", "REFERENCES");

        let stubs = find_stubs(&store);
        assert_eq!(stubs.len(), 1);
        assert_eq!(stubs[0].0, EntityId("stub1".into()));
        assert_eq!(stubs[0].1, vec![EntityId("real".into())]);
    }

    #[test]
    fn most_connected_sorted_descending() {
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        store.upsert(EntityId("c".into()), entity("c", "s", false));
        // a has 2 edges (1 out + 1 in from c->a)
        // b has 1 edge (1 in from a->b)
        // c has 1 edge (1 out to a)
        add_edge(&mut store, "a", "b", "USES");
        add_edge(&mut store, "c", "a", "PART_OF");

        let top = most_connected(&store, 10);
        assert_eq!(top[0].id, EntityId("a".into()));
        assert_eq!(top[0].total, 2);
        assert_eq!(top[0].incoming, 1);
        assert_eq!(top[0].outgoing, 1);
    }

    #[test]
    fn most_connected_respects_limit() {
        let mut store = Store::new();
        for i in 0..5 {
            store.upsert(
                EntityId(format!("e{i}")),
                entity(&format!("e{i}"), "s", false),
            );
        }
        let top = most_connected(&store, 2);
        assert_eq!(top.len(), 2);
    }

    // ---- reachable_via ----

    #[test]
    fn reachable_via_filters_by_edge_type() {
        // a --USES--> b ; a --REFERENCES--> c
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        store.upsert(EntityId("c".into()), entity("c", "s", false));
        add_edge(&mut store, "a", "b", "USES");
        add_edge(&mut store, "a", "c", "REFERENCES");

        let r = reachable_via(
            &store,
            &EntityId("a".into()),
            &["USES".to_string()],
            1,
            TraversalDirection::Both,
        );
        assert_eq!(r.len(), 1);
        assert_eq!(r[0].id, EntityId("b".into()));
        assert_eq!(r[0].via_edge, "USES");
        assert_eq!(r[0].depth, 1);
        assert_eq!(r[0].direction, TraversalDirection::Out);
    }

    #[test]
    fn reachable_via_bidirectional() {
        // From b, walk back to a via incoming edge.
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        add_edge(&mut store, "a", "b", "USES");
        let r = reachable_via(
            &store,
            &EntityId("b".into()),
            &["USES".to_string()],
            1,
            TraversalDirection::Both,
        );
        assert_eq!(r.len(), 1);
        assert_eq!(r[0].id, EntityId("a".into()));
        assert_eq!(r[0].depth, 1);
        assert_eq!(
            r[0].direction,
            TraversalDirection::In,
            "reached against the edge — reported as `in`"
        );

        // Directional complements on the same store: from b, `out`
        // reaches nothing (no outgoing USES), `in` reaches a.
        let out = reachable_via(
            &store,
            &EntityId("b".into()),
            &["USES".to_string()],
            1,
            TraversalDirection::Out,
        );
        assert!(out.is_empty(), "no out-edges from b: {out:?}");
        let inward = reachable_via(
            &store,
            &EntityId("b".into()),
            &["USES".to_string()],
            1,
            TraversalDirection::In,
        );
        assert_eq!(inward.len(), 1);
        assert_eq!(inward[0].id, EntityId("a".into()));
    }

    #[test]
    fn reachable_via_zero_depth_empty() {
        let store = build_linear_store();
        let r = reachable_via(
            &store,
            &EntityId("a".into()),
            &["USES".to_string()],
            0,
            TraversalDirection::Both,
        );
        assert!(r.is_empty());
    }

    #[test]
    fn reachable_via_empty_edge_types_empty() {
        let store = build_linear_store();
        let r = reachable_via(
            &store,
            &EntityId("a".into()),
            &[],
            10,
            TraversalDirection::Both,
        );
        assert!(r.is_empty());
    }

    #[test]
    fn reachable_via_respects_depth_limit() {
        let store = build_linear_store(); // a -> b -> c with USES
        let r1 = reachable_via(
            &store,
            &EntityId("a".into()),
            &["USES".to_string()],
            1,
            TraversalDirection::Both,
        );
        assert_eq!(r1.len(), 1, "depth 1 reaches b only");
        assert_eq!(r1[0].id, EntityId("b".into()));
        assert_eq!(r1[0].depth, 1);

        let r2 = reachable_via(
            &store,
            &EntityId("a".into()),
            &["USES".to_string()],
            2,
            TraversalDirection::Both,
        );
        assert_eq!(r2.len(), 2);
        let depths: std::collections::HashMap<EntityId, usize> =
            r2.iter().map(|r| (r.id.clone(), r.depth)).collect();
        assert_eq!(depths[&EntityId("b".into())], 1);
        assert_eq!(depths[&EntityId("c".into())], 2);
    }

    #[test]
    fn reachable_via_bfs_records_shortest_depth() {
        // Diamond: a -> b -> d ; a -> c -> d. d is reachable via 2 hops from a
        // through two paths. BFS should record depth=2 exactly once.
        let mut store = Store::new();
        for id in ["a", "b", "c", "d"] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        add_edge(&mut store, "a", "b", "R");
        add_edge(&mut store, "a", "c", "R");
        add_edge(&mut store, "b", "d", "R");
        add_edge(&mut store, "c", "d", "R");

        let r = reachable_via(
            &store,
            &EntityId("a".into()),
            &["R".to_string()],
            3,
            TraversalDirection::Both,
        );
        let entries: std::collections::HashMap<EntityId, usize> =
            r.iter().map(|e| (e.id.clone(), e.depth)).collect();
        assert_eq!(entries.len(), 3, "b, c, d each appear once");
        assert_eq!(entries[&EntityId("d".into())], 2);
    }

    #[test]
    fn most_connected_skips_stubs() {
        let mut store = Store::new();
        store.upsert(EntityId("real".into()), entity("real", "s", false));
        store.upsert(EntityId("stub".into()), entity("stub", "s", true));
        add_edge(&mut store, "real", "stub", "REFERENCES");

        let top = most_connected(&store, 10);
        assert_eq!(top.len(), 1);
        assert_eq!(top[0].id, EntityId("real".into()));
    }

    // ---- would_cycle ----

    #[test]
    fn would_cycle_self_loop_always_reported() {
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        let path = would_cycle(
            &store,
            &EntityId("a".into()),
            &EntityId("a".into()),
            "PART_OF",
        );
        assert_eq!(path, Some(vec![EntityId("a".into())]));
    }

    #[test]
    fn would_cycle_single_back_edge() {
        // a -PART_OF-> b already. Adding b -PART_OF-> a closes a cycle.
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        add_edge(&mut store, "a", "b", "PART_OF");
        let path = would_cycle(
            &store,
            &EntityId("b".into()),
            &EntityId("a".into()),
            "PART_OF",
        )
        .expect("cycle");
        assert_eq!(path, vec![EntityId("a".into()), EntityId("b".into())]);
    }

    #[test]
    fn would_cycle_deep_chain() {
        // foo's future edge: foo -PART_OF-> bar. Existing: bar->baz->foo.
        let mut store = Store::new();
        for id in ["foo", "bar", "baz"] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        add_edge(&mut store, "bar", "baz", "PART_OF");
        add_edge(&mut store, "baz", "foo", "PART_OF");
        let path = would_cycle(
            &store,
            &EntityId("foo".into()),
            &EntityId("bar".into()),
            "PART_OF",
        )
        .expect("cycle");
        assert_eq!(
            path,
            vec![
                EntityId("bar".into()),
                EntityId("baz".into()),
                EntityId("foo".into())
            ]
        );
    }

    #[test]
    fn would_cycle_ignores_other_rel_types() {
        // a -DEPENDS_ON-> b exists. Proposed b -PART_OF-> a should not
        // trip the PART_OF subgraph even though a non-PART_OF back-edge
        // exists.
        let mut store = Store::new();
        store.upsert(EntityId("a".into()), entity("a", "s", false));
        store.upsert(EntityId("b".into()), entity("b", "s", false));
        add_edge(&mut store, "a", "b", "DEPENDS_ON");
        assert!(
            would_cycle(
                &store,
                &EntityId("b".into()),
                &EntityId("a".into()),
                "PART_OF"
            )
            .is_none()
        );
    }

    #[test]
    fn would_cycle_none_for_disjoint_graph() {
        let mut store = Store::new();
        for id in ["a", "b", "c", "d"] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        add_edge(&mut store, "c", "d", "PART_OF");
        assert!(
            would_cycle(
                &store,
                &EntityId("a".into()),
                &EntityId("b".into()),
                "PART_OF"
            )
            .is_none()
        );
    }

    #[test]
    fn would_cycle_parallel_paths_do_not_trip() {
        // a -PART_OF-> b and a -PART_OF-> c (no path from b to a).
        // Proposed c -PART_OF-> a should be flagged (c has no back-path
        // today, but adding it alongside existing a->c would form a
        // cycle a->c->a — confirm the BFS catches that).
        let mut store = Store::new();
        for id in ["a", "b", "c"] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        add_edge(&mut store, "a", "b", "PART_OF");
        add_edge(&mut store, "a", "c", "PART_OF");
        // Proposed a -PART_OF-> b is fine — a already -PART_OF-> b.
        assert!(
            would_cycle(
                &store,
                &EntityId("a".into()),
                &EntityId("b".into()),
                "PART_OF"
            )
            .is_none(),
            "sibling paths must not trip"
        );
        // Proposed b -PART_OF-> a would close a cycle a->b->a.
        assert!(
            would_cycle(
                &store,
                &EntityId("b".into()),
                &EntityId("a".into()),
                "PART_OF"
            )
            .is_some()
        );
    }

    #[test]
    fn most_connected_distinguishes_hub_vs_fanout() {
        let mut store = Store::new();
        for id in [
            "hub", "fanout", "r1", "r2", "r3", "r4", "t1", "t2", "t3", "t4",
        ] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        // hub: 4 incoming, 0 outgoing
        add_edge(&mut store, "r1", "hub", "REFERENCES");
        add_edge(&mut store, "r2", "hub", "REFERENCES");
        add_edge(&mut store, "r3", "hub", "REFERENCES");
        add_edge(&mut store, "r4", "hub", "REFERENCES");
        // fanout: 0 incoming, 4 outgoing
        add_edge(&mut store, "fanout", "t1", "USES");
        add_edge(&mut store, "fanout", "t2", "USES");
        add_edge(&mut store, "fanout", "t3", "USES");
        add_edge(&mut store, "fanout", "t4", "USES");

        let top = most_connected(&store, 10);
        let hub = top.iter().find(|c| c.id == EntityId("hub".into())).unwrap();
        assert_eq!(hub.total, 4);
        assert_eq!(hub.incoming, 4);
        assert_eq!(hub.outgoing, 0);
        let fanout = top
            .iter()
            .find(|c| c.id == EntityId("fanout".into()))
            .unwrap();
        assert_eq!(fanout.total, 4);
        assert_eq!(fanout.incoming, 0);
        assert_eq!(fanout.outgoing, 4);

        // Tie-break: "fanout" < "hub" lex, so fanout appears first.
        let fanout_pos = top.iter().position(|c| c.id.0 == "fanout").unwrap();
        let hub_pos = top.iter().position(|c| c.id.0 == "hub").unwrap();
        assert!(
            fanout_pos < hub_pos,
            "ties must resolve by id lex ascending"
        );
    }

    /// #46: a node inflated purely by auto-emitted mentions (BodyLink)
    /// must not outrank a node with real typed dependencies. `typed_total`
    /// drives the ranking; `total` (which keeps the mentions) is retained
    /// but only a secondary tie-break.
    #[test]
    fn most_connected_ranks_by_dependency_not_mention() {
        let mut store = Store::new();
        for id in [
            "mentionhub",
            "dephub",
            "m1",
            "m2",
            "m3",
            "m4",
            "m5",
            "d1",
            "d2",
        ] {
            store.upsert(EntityId(id.into()), entity(id, "s", false));
        }
        // mentionhub: 5 incoming mention edges — high total, zero typed.
        for m in ["m1", "m2", "m3", "m4", "m5"] {
            add_body_edge(&mut store, m, "mentionhub");
        }
        // dephub: 2 incoming typed (USES) edges — lower total, real deps.
        add_edge(&mut store, "d1", "dephub", "USES");
        add_edge(&mut store, "d2", "dephub", "USES");

        let top = most_connected(&store, 10);
        let mh = top.iter().find(|c| c.id.0 == "mentionhub").unwrap();
        let dh = top.iter().find(|c| c.id.0 == "dephub").unwrap();

        // Raw total still counts the mentions (not dropped from the graph).
        assert_eq!(mh.total, 5);
        assert_eq!(mh.typed_total, 0, "all of mentionhub's edges are mentions");
        assert_eq!(dh.total, 2);
        assert_eq!(dh.typed_total, 2, "dephub's edges are typed dependencies");

        // Ranking: dephub (2 typed) outranks mentionhub (0 typed) despite
        // mentionhub's higher raw total — the co-mention inflation is gone.
        let mh_pos = top.iter().position(|c| c.id.0 == "mentionhub").unwrap();
        let dh_pos = top.iter().position(|c| c.id.0 == "dephub").unwrap();
        assert!(
            dh_pos < mh_pos,
            "dependency hub must outrank co-mention hub"
        );
    }

    /// Agent-trust plan 06 (criterion 1): leaf-declared types are
    /// exempt from the orphan scan — visible instead through
    /// `leaf_population` — while non-leaf types count exactly as
    /// before, a leaf WITH edges stays legal, and an empty schema map
    /// reproduces the schema-blind behaviour byte-for-byte.
    #[test]
    fn leaf_declared_types_exempt_from_orphans_but_visible_as_population() {
        use std::collections::HashMap;
        use std::sync::Arc;

        let manifest = r#"
name: leafy
version: 0.1.0
description: leaf test schema
when_to_use: tests
types:
  - obs
  - spec
relationships:
  mode: strict
  definitions:
    - name: USES
      description: u
      default_weight: 1.0
    - name: PART_OF
      description: hier
      default_weight: 1.0
      acyclic: true
    - name: _default
      description: fallback
      default_weight: 1.0
community:
  resolution: 1.0
  seed: 42
"#;
        let body = "sections:\n  - key: body\n    heading: Body\n    required: true\n    search_weight: 10.0\n    catch_all: true\n    write_rules: []\nmetadata_fields: []\ntitle_weight: 100.0\ntext_fields:\n  - body\nhierarchy_relationship: PART_OF\nno_self_loop_relationships: []\nupdatable_fields:\n  - title\nhealth_required_fields: []\nstaleness_threshold_days: 90\nwrite_rules: []\n";
        let obs_yaml = format!("name: obs\ndescription: t\nwhen_to_use: h\nleaf: true\n{body}");
        let spec_yaml = format!("name: spec\ndescription: t\nwhen_to_use: h\n{body}");
        let schema = Arc::new(
            memstead_schema::load_schema_from_memory(
                manifest,
                &[
                    ("obs".to_string(), obs_yaml),
                    ("spec".to_string(), spec_yaml),
                ],
            )
            .expect("leaf fixture schema parses"),
        );
        let mut schemas: HashMap<String, Arc<memstead_schema::Schema>> = HashMap::new();
        schemas.insert("s".to_string(), schema);

        let mut store = Store::new();
        let mut e = |id: &str, ty: &str| {
            let mut ent = entity(id, "s", false);
            ent.entity_type = ty.to_string();
            store.upsert(EntityId(id.into()), ent);
        };
        e("lonely-spec", "spec"); // real orphan
        e("lonely-obs", "obs"); // leaf: exempt
        e("linked-obs", "obs"); // leaf with an edge: legal, not orphan anyway
        e("hub", "spec");
        add_edge(&mut store, "linked-obs", "hub", "USES");

        // Schema-aware: only the non-leaf edge-less entity is an orphan.
        let orphans = find_orphans_with_schemas(&store, &schemas);
        assert_eq!(
            orphans,
            vec![EntityId("lonely-spec".into())],
            "leaf-typed edge-less entities are exempt; non-leaf count as before"
        );
        // The exempted population is visible, keyed schema_ref:type.
        let pop = leaf_population(&store, &schemas);
        assert_eq!(pop.get("leafy@0.1.0:obs"), Some(&2));
        assert_eq!(pop.len(), 1);

        // Empty schema map == historical schema-blind behaviour.
        let blind = find_orphans(&store);
        let mut blind_sorted: Vec<String> = blind.iter().map(|i| i.0.clone()).collect();
        blind_sorted.sort();
        assert_eq!(blind_sorted, vec!["lonely-obs", "lonely-spec"]);
        assert!(leaf_population(&store, &HashMap::new()).is_empty());
    }
}