eidos_kernel/

relational.rs

//! Relational (call-graph / impact) retrieval over the code graph.
//!
//! Glyph's lexical retrieval is node-local: "what calls X" returns X itself. But the graph
//! already encodes who-references-what as edges (`A --references--> B`), so the callers/dependents
//! of a symbol are just its REVERSE edges. These traversals surface that. They are deterministic
//! graph facts — confidence is `Exact`, not a similarity guess.

use std::collections::{HashMap, VecDeque};

use crate::graph_index::GraphIndex;
use crate::retrieval::{Confidence, Hit};
use crate::schema::{EdgeBasis, Graph, Kind, Node, relation};

fn last_segment(id: &str) -> &str {
    id.rsplit("::").next().unwrap_or(id)
}

fn hit_exact(id: &str, score: i64, why: String) -> Hit {
    Hit {
        id: id.to_string(),
        score,
        lexical_score: score,
        confidence: Confidence::Exact,
        why: vec![why],
        relation_matches: Vec::new(),
        anchor: 1.0,
        relation_anchor: false,
    }
}

fn is_function_indexed(index: &GraphIndex<'_>, id: &str) -> bool {
    index.is_kind(id, Kind::Function)
}

fn symbol_rank(node: &Node) -> (u8, u8, &str) {
    let test_penalty = u8::from(
        node.id.contains("::tests::")
            || node
                .source_files
                .iter()
                .any(|path| path.contains("/tests/") || path.contains("\\tests\\")),
    );
    let kind_rank = match node.kind {
        Kind::Type => 0,
        Kind::Trait => 1,
        Kind::Function => 2,
        Kind::Module => 3,
        Kind::Skill => 4,
        Kind::Agent => 5,
        Kind::Doc => 6,
        Kind::Section => 7,
        Kind::Unknown => 8,
    };
    (test_penalty, kind_rank, node.id.as_str())
}

fn best_symbol_candidate<'a>(nodes: impl Iterator<Item = &'a Node>) -> Option<String> {
    let mut candidates = nodes.collect::<Vec<_>>();
    candidates.sort_by_key(|node| symbol_rank(node));
    candidates.first().map(|node| node.id.clone())
}

/// Resolve a symbol NAME (e.g. `verify_password`, `Task`) to a concrete node id.
pub fn resolve_symbol(graph: &Graph, needle: &str) -> Option<String> {
    let n = needle.trim().trim_matches('`').to_lowercase();
    if n.is_empty() {
        return None;
    }
    // 1. exact id
    if let Some(node) = graph.nodes.iter().find(|x| x.id.to_lowercase() == n) {
        return Some(node.id.clone());
    }
    // 2. last `::`-segment equals the needle (most direct), deterministic by id
    let seg = graph
        .nodes
        .iter()
        .filter(|x| x.id.to_lowercase().rsplit("::").next() == Some(n.as_str()))
        .collect::<Vec<_>>();
    if !seg.is_empty() {
        return best_symbol_candidate(seg.into_iter());
    }
    // 3. id contains `::needle` as a segment, or title matches
    let needle_seg = format!("::{n}");
    best_symbol_candidate(
        graph
            .nodes
            .iter()
            .filter(|x| x.id.to_lowercase().contains(&needle_seg) || x.title.to_lowercase() == n),
    )
}

/// Direct callers/users of a node: reverse `references` edges (+ `implements` when the node is a
/// trait). Prefers function nodes — a containing type that only references the target *through* one
/// of its methods is dropped in favor of the method.
pub fn callers(graph: &Graph, node_id: &str) -> Vec<Hit> {
    let index = GraphIndex::build(graph);
    let is_trait = index.is_kind(node_id, Kind::Trait);
    let mut froms: Vec<String> = index
        .incoming(node_id)
        // Trusted structural dependents only: a Lexical reference is a name-match candidate, not
        // proven coupling (e.g. a cross-crate name collision), and reporting it as a caller is the
        // over-report the EdgeBasis work exists to prevent. Resolved = import-proven or same-crate
        // unique — the earned band.
        .filter(|e| e.basis == EdgeBasis::Resolved)
        .filter(|e| {
            e.relation == relation::REFERENCES || (is_trait && e.relation == relation::IMPLEMENTS)
        })
        .map(|e| e.from.clone())
        .collect();
    froms.sort_unstable();
    froms.dedup();

    let fn_callers: Vec<&str> = froms
        .iter()
        .filter(|id| is_function_indexed(&index, id))
        .map(std::string::String::as_str)
        .collect();
    let kept: Vec<&str> = froms
        .iter()
        .filter(|id| {
            if is_function_indexed(&index, id) {
                return true;
            }
            // keep a non-function caller only if it doesn't roll up a function caller
            !fn_callers
                .iter()
                .any(|f| index.has_outgoing(id, relation::CONTAINS, f))
        })
        .map(std::string::String::as_str)
        .collect();

    let label = last_segment(node_id).to_string();
    let mut hits: Vec<Hit> = kept
        .iter()
        .map(|id| hit_exact(id, 100, format!("calls/uses {label} (references edge)")))
        .collect();
    hits.sort_by(|a, b| {
        let af = is_function_indexed(&index, &a.id);
        let bf = is_function_indexed(&index, &b.id);
        bf.cmp(&af).then_with(|| a.id.cmp(&b.id))
    });
    hits
}

/// Transitive dependent closure: BFS over REVERSE `references`/`implements` edges from `node_id`
/// up to `depth` hops. Also seeds the node's `contains` children (changing a type affects users of
/// its own methods). Excludes the subject itself. Answers "what breaks if I change X".
pub fn impact(graph: &Graph, node_id: &str, depth: usize) -> Vec<Hit> {
    let index = GraphIndex::build(graph);
    let depth = depth.clamp(1, 8);
    let mut dist: HashMap<String, usize> = HashMap::new();
    dist.insert(node_id.to_string(), 0);
    let mut q: VecDeque<(String, usize)> = VecDeque::new();
    q.push_back((node_id.to_string(), 0));
    for e in index.outgoing(node_id) {
        if e.relation == relation::CONTAINS && !dist.contains_key(&e.to) {
            dist.insert(e.to.clone(), 1);
            q.push_back((e.to.clone(), 1));
        }
    }
    while let Some((cur, d)) = q.pop_front() {
        if d >= depth {
            continue;
        }
        for e in index.incoming(&cur) {
            // Trusted dependents only (see `callers`): Lexical edges are unproven name matches, so
            // walking them is what makes "what breaks if I change X" cry wolf.
            if e.basis == EdgeBasis::Resolved
                && (e.relation == relation::REFERENCES || e.relation == relation::IMPLEMENTS)
            {
                let nd = d + 1;
                if dist.get(&e.from).is_none_or(|&old| nd < old) {
                    dist.insert(e.from.clone(), nd);
                    q.push_back((e.from.clone(), nd));
                }
            }
        }
    }
    let label = last_segment(node_id).to_string();
    let mut items: Vec<(String, usize)> =
        dist.into_iter().filter(|(id, _)| id != node_id).collect();
    items.sort_by(|a, b| a.1.cmp(&b.1).then_with(|| a.0.cmp(&b.0)));
    items
        .iter()
        .map(|(id, d)| {
            hit_exact(
                id,
                (100 - *d as i64).max(1),
                format!("depends on {label} ({d} hop(s) via references/implements)"),
            )
        })
        .collect()
}

/// Map a generic, language-agnostic KIND word in the query to a node `Kind`. Used to bias
/// retrieval toward the structural shape the user asked for ("the **struct** that…" → Type).
/// Vocabulary only — no project- or language-specific names.
pub fn kind_intent(query: &str) -> Option<Kind> {
    for word in query.to_lowercase().split(|c: char| !c.is_alphanumeric()) {
        let k = match word {
            "struct" | "enum" | "class" | "type" | "record" | "dataclass" | "datatype"
            | "object" => Kind::Type,
            "trait" | "interface" | "protocol" => Kind::Trait,
            "function" | "func" | "fn" | "method" | "def" | "procedure" | "routine" | "handler"
            | "endpoint" | "route" | "hook" | "component" | "callback" => Kind::Function,
            "module" | "package" | "namespace" => Kind::Module,
            _ => continue,
        };
        return Some(k);
    }
    None
}

/// Stable re-rank: hits whose node is of `target` kind move ahead of the rest, preserving the
/// lexical order within each group. Generic — promotes the asked-for shape without touching scores.
pub fn rerank_by_kind(graph: &Graph, mut hits: Vec<Hit>, target: Kind) -> Vec<Hit> {
    let matches = |id: &str| graph.nodes.iter().any(|n| n.id == id && n.kind == target);
    hits.sort_by_key(|h| !matches(&h.id));
    hits
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RelMode {
    Callers,
    Impact,
}

/// Detect a call-graph/impact query and extract its subject symbol. Returns `None` for ordinary
/// lexical queries (so the caller falls through to normal grounding).
pub fn detect_relational_intent(query: &str) -> Option<(RelMode, String)> {
    let q = query.to_lowercase();
    const IMPACT: &[&str] = &[
        "what depends on",
        "depends on",
        "what breaks if",
        "what would break",
        "impact of changing",
        "dependents of",
    ];
    const CALLERS: &[&str] = &[
        "what calls",
        "who calls",
        "callers of",
        "what references",
        "what uses",
    ];
    let (mode, pat) = if let Some(p) = IMPACT.iter().find(|p| q.contains(**p)) {
        (RelMode::Impact, *p)
    } else if let Some(p) = CALLERS.iter().find(|p| q.contains(**p)) {
        (RelMode::Callers, *p)
    } else {
        return None;
    };
    let after = q.split(pat).nth(1).unwrap_or("").to_string();
    let subject = extract_symbol(&after).or_else(|| extract_symbol(&q));
    subject.map(|s| (mode, s))
}

fn extract_symbol(text: &str) -> Option<String> {
    const STOP: &[&str] = &[
        "the", "a", "an", "if", "i", "to", "my", "our", "this", "that", "change", "changing",
        "trait", "enum", "struct", "class", "type", "function", "method", "fn", "module", "it",
        "would", "break", "of", "on", "in", "is", "are",
    ];
    let toks: Vec<&str> = text
        .split(|c: char| !(c.is_alphanumeric() || c == '_'))
        .filter(|t| {
            if t.is_empty() {
                return false;
            }
            let tl = t.to_lowercase();
            !STOP.contains(&tl.as_str())
        })
        .collect();
    toks.last().map(std::string::ToString::to_string)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::schema::{Edge, Node};

    fn node(id: &str, kind: Kind) -> Node {
        Node {
            id: id.into(),
            kind,
            subkind: None,
            title: last_segment(id).into(),
            summary: String::new(),
            aliases: vec![],
            tags: vec![],
            query_examples: vec![],
            source_files: vec![],
            span: None,
            partition: None,
        }
    }
    fn edge(from: &str, to: &str, rel: &str) -> Edge {
        // Fixture edges model earned, same-crate structural references — the Resolved band that
        // impact/callers walk. (EdgeBasis defaults to Lexical since D1.1, so this must be explicit.)
        Edge {
            from: from.into(),
            to: to.into(),
            relation: rel.into(),
            evidence: String::new(),
            basis: EdgeBasis::Resolved,
            ..Default::default()
        }
    }
    fn lexical_edge(from: &str, to: &str, rel: &str) -> Edge {
        Edge {
            basis: EdgeBasis::Lexical,
            ..edge(from, to, rel)
        }
    }
    fn fixture() -> Graph {
        Graph {
            nodes: vec![
                node("fn.a::auth::verify_password", Kind::Function),
                node("fn.a::routes::login", Kind::Function),
                node("fn.a::service::TaskService::authenticate", Kind::Function),
                node("type.a::service::TaskService", Kind::Type),
                node("type.c::scheduler::Scheduler", Kind::Type),
                node("type.c::scheduler::Task", Kind::Type),
                node("fn.c::scheduler::Task::id", Kind::Function),
                node("fn.c::scheduler::tests::Task", Kind::Function),
            ],
            edges: vec![
                edge(
                    "fn.a::routes::login",
                    "fn.a::auth::verify_password",
                    relation::REFERENCES,
                ),
                edge(
                    "fn.a::service::TaskService::authenticate",
                    "fn.a::auth::verify_password",
                    relation::REFERENCES,
                ),
                // rolled-up parent type also references it; should be dropped for the method
                edge(
                    "type.a::service::TaskService",
                    "fn.a::auth::verify_password",
                    relation::REFERENCES,
                ),
                edge(
                    "type.a::service::TaskService",
                    "fn.a::service::TaskService::authenticate",
                    relation::CONTAINS,
                ),
                edge(
                    "type.c::scheduler::Scheduler",
                    "type.c::scheduler::Task",
                    relation::REFERENCES,
                ),
                edge(
                    "type.c::scheduler::Task",
                    "fn.c::scheduler::Task::id",
                    relation::CONTAINS,
                ),
            ],
            ..Default::default()
        }
    }

    #[test]
    fn callers_returns_function_callers_not_the_symbol_or_rolled_up_type() {
        let g = fixture();
        let ids: Vec<String> = callers(&g, "fn.a::auth::verify_password")
            .into_iter()
            .map(|h| h.id)
            .collect();
        assert!(ids.contains(&"fn.a::routes::login".to_string()));
        assert!(ids.contains(&"fn.a::service::TaskService::authenticate".to_string()));
        assert!(!ids.contains(&"fn.a::auth::verify_password".to_string()));
        // the parent type rolled up via its method is dropped
        assert!(!ids.contains(&"type.a::service::TaskService".to_string()));
    }

    #[test]
    fn impact_and_callers_ignore_lexical_edges() {
        // A Lexical reference is an unproven name-match (e.g. a cross-crate name collision). It must
        // NOT be reported as a caller or a dependent — that is the over-report the trusted-only walk
        // exists to prevent.
        let mut g = fixture();
        g.nodes
            .push(node("fn.z::other::coincidental", Kind::Function));
        g.edges.push(lexical_edge(
            "fn.z::other::coincidental",
            "fn.a::auth::verify_password",
            relation::REFERENCES,
        ));

        let callers: Vec<String> = callers(&g, "fn.a::auth::verify_password")
            .into_iter()
            .map(|h| h.id)
            .collect();
        assert!(
            !callers.contains(&"fn.z::other::coincidental".to_string()),
            "a Lexical reference must not appear as a caller: {callers:?}"
        );
        // the genuine Resolved callers are still there
        assert!(callers.contains(&"fn.a::routes::login".to_string()));

        let impacted: Vec<String> = impact(&g, "fn.a::auth::verify_password", 8)
            .into_iter()
            .map(|h| h.id)
            .collect();
        assert!(
            !impacted.contains(&"fn.z::other::coincidental".to_string()),
            "a Lexical reference must not appear as a dependent: {impacted:?}"
        );
    }

    #[test]
    fn impact_includes_dependents_and_contained_children_not_subject() {
        let g = fixture();
        let ids: Vec<String> = impact(&g, "type.c::scheduler::Task", 8)
            .into_iter()
            .map(|h| h.id)
            .collect();
        assert!(ids.contains(&"type.c::scheduler::Scheduler".to_string()));
        assert!(ids.contains(&"fn.c::scheduler::Task::id".to_string()));
        assert!(!ids.contains(&"type.c::scheduler::Task".to_string()));
    }

    #[test]
    fn resolve_symbol_finds_by_last_segment() {
        let g = fixture();
        assert_eq!(
            resolve_symbol(&g, "verify_password").as_deref(),
            Some("fn.a::auth::verify_password")
        );
        assert_eq!(
            resolve_symbol(&g, "Task").as_deref(),
            Some("type.c::scheduler::Task")
        );
        assert_eq!(
            resolve_symbol(&g, "scheduler::Task").as_deref(),
            Some("type.c::scheduler::Task")
        );
        assert_eq!(resolve_symbol(&g, "nonexistent_xyz"), None);
    }

    #[test]
    fn intent_detection() {
        assert_eq!(
            detect_relational_intent("what calls verify_password"),
            Some((RelMode::Callers, "verify_password".to_string()))
        );
        assert_eq!(
            detect_relational_intent("what would break if I change the Task enum"),
            Some((RelMode::Impact, "task".to_string()))
        );
        assert_eq!(
            detect_relational_intent("who calls scheduler tick"),
            Some((RelMode::Callers, "tick".to_string()))
        );
        assert_eq!(detect_relational_intent("the worker run loop"), None);
    }

    #[test]
    fn kind_intent_maps_generic_vocabulary() {
        assert_eq!(
            kind_intent("the struct that owns the queue"),
            Some(Kind::Type)
        );
        assert_eq!(
            kind_intent("the trait that picks a worker"),
            Some(Kind::Trait)
        );
        assert_eq!(kind_intent("the react hook for auth"), Some(Kind::Function));
        assert_eq!(kind_intent("password hashing"), None);
    }

    #[test]
    fn rerank_promotes_target_kind_preserving_order() {
        let g = fixture();
        let hits = vec![
            hit_exact("fn.a::service::TaskService::authenticate", 90, "x".into()),
            hit_exact("type.a::service::TaskService", 80, "x".into()),
        ];
        let r = rerank_by_kind(&g, hits, Kind::Type);
        assert_eq!(r[0].id, "type.a::service::TaskService");
    }
}