velesdb-memory 0.14.1

//! BDD integration tests for `why` — the multi-hop explanation path.
//!
//! This is the differentiator: `why` returns the *connected subgraph* behind a
//! decision, surfacing related memories a purely vector recall is blind to.
//!
//! Categories: Nominal (≥60%), Edge (~20%), Negative (≥20%).

#![cfg(feature = "persistence")]

mod common;

use common::service;
use tempfile::TempDir;
use velesdb_memory::limits::{MAX_WHY_EDGES, MAX_WHY_NODES, MAX_WHY_NODE_DEGREE};
use velesdb_memory::{HashEmbedder, Link, MemoryService};

const DECISION: &str = "we chose parking_lot to avoid lock poisoning";

/// Build the canonical chain: decision -[`decided_in`]-> PR -[`tracked_by`]-> ticket.
/// The ticket wording is deliberately dissimilar to the decision text so that
/// only the graph (not vector similarity) can reach it.
fn seeded_chain() -> (TempDir, MemoryService<HashEmbedder>, u64, u64, u64) {
    let (dir, svc) = service();
    let decision = svc
        .remember(DECISION, &[], None)
        .expect("remember decision");
    let pr = svc
        .remember("PR #42 swaps the mutex implementation", &[], None)
        .expect("remember pr");
    let ticket = svc
        .remember("EPIC-317 xyzzy quux frobnicate", &[], None)
        .expect("remember ticket");
    svc.relate(decision, pr, "decided_in")
        .expect("relate decision->pr");
    svc.relate(pr, ticket, "tracked_by")
        .expect("relate pr->ticket");
    (dir, svc, decision, pr, ticket)
}

/// Node ids of the subgraph `why(DECISION, hops)` returns.
fn why_ids(svc: &MemoryService<HashEmbedder>, hops: usize) -> Vec<u64> {
    svc.why(DECISION, hops, None)
        .expect("why")
        .nodes
        .iter()
        .map(|n| n.id)
        .collect()
}

// --- Nominal ---------------------------------------------------------------

#[test]
fn why_returns_the_full_connected_subgraph() {
    let (_dir, svc, decision, pr, ticket) = seeded_chain();

    let explanation = svc.why(DECISION, 2, None).expect("why");

    let ids: Vec<u64> = explanation.nodes.iter().map(|n| n.id).collect();
    assert!(
        ids.contains(&decision),
        "subgraph must contain the decision"
    );
    assert!(ids.contains(&pr), "subgraph must contain the linked PR");
    assert!(
        ids.contains(&ticket),
        "subgraph must contain the 2-hop ticket"
    );
    assert_eq!(
        explanation.edges.len(),
        2,
        "two typed edges connect the chain"
    );
}

#[test]
fn why_assigns_hop_distances_from_the_seed() {
    let (_dir, svc, decision, pr, ticket) = seeded_chain();

    let explanation = svc.why(DECISION, 2, None).expect("why");
    let hop = |id: u64| explanation.nodes.iter().find(|n| n.id == id).map(|n| n.hop);

    assert_eq!(hop(decision), Some(0), "seed is hop 0");
    assert_eq!(hop(pr), Some(1), "PR is one hop away");
    assert_eq!(hop(ticket), Some(2), "ticket is two hops away");
}

#[test]
fn why_reaches_what_vector_recall_alone_misses() {
    let (_dir, svc, _decision, _pr, ticket) = seeded_chain();

    // The best single semantic match for the decision is NOT the ticket:
    // their wording shares no tokens.
    let top = svc.recall(DECISION, 1, None).expect("recall");
    assert!(
        top.iter().all(|h| h.id != ticket),
        "vector recall alone misses the ticket"
    );

    // The graph traversal reaches it anyway.
    let explanation = svc.why(DECISION, 2, None).expect("why");
    assert!(
        explanation.nodes.iter().any(|n| n.id == ticket),
        "the graph surfaces the connected ticket the vector is blind to"
    );
}

// --- Edge ------------------------------------------------------------------

#[test]
fn why_with_zero_hops_returns_only_the_seed() {
    let (_dir, svc, decision, _pr, _ticket) = seeded_chain();

    let explanation = svc.why(DECISION, 0, None).expect("why");

    assert_eq!(explanation.nodes.len(), 1, "no traversal at zero hops");
    assert_eq!(explanation.nodes[0].id, decision);
    assert!(explanation.edges.is_empty(), "no edges at zero hops");
}

#[test]
fn why_stops_at_the_hop_budget() {
    let (_dir, svc, decision, pr, ticket) = seeded_chain();

    let ids = why_ids(&svc, 1);

    assert!(
        ids.contains(&decision) && ids.contains(&pr),
        "one hop reaches the PR"
    );
    assert!(
        !ids.contains(&ticket),
        "one hop must not reach the two-hop ticket"
    );
}

#[test]
fn why_caps_a_single_nodes_out_degree() {
    // Regression for issue #1743: a super-node (an entity hub in production,
    // but the cap applies to any node) must not dump its entire neighborhood
    // into one response. Relate the seed directly to more facts than
    // `MAX_WHY_NODE_DEGREE` allows and check the walk stops following that
    // node's edges once the cap is spent.
    let (_dir, svc) = service();
    let seed = svc
        .remember("a fact many others point at", &[], None)
        .expect("remember seed");
    for i in 0..MAX_WHY_NODE_DEGREE + 20 {
        let target = svc
            .remember(&format!("fact number {i} related to the seed"), &[], None)
            .expect("remember target");
        svc.relate(seed, target, "mentions").expect("relate");
    }

    let explanation = svc
        .why("a fact many others point at", 1, None)
        .expect("why");

    assert_eq!(
        explanation.nodes.len(),
        1 + MAX_WHY_NODE_DEGREE,
        "the seed plus at most MAX_WHY_NODE_DEGREE one-hop targets, not all of them"
    );
}

#[test]
fn why_caps_the_total_nodes_across_the_whole_walk() {
    // Regression for issue #1743: even when no single node exceeds the
    // per-node degree cap, a long enough chain must not grow the response
    // past `MAX_WHY_NODES`. Each link here has out-degree 1, so
    // `why_caps_a_single_nodes_out_degree` alone would never catch this.
    let (_dir, svc) = service();
    let mut previous = svc
        .remember("chain link 0, the seed", &[], None)
        .expect("remember seed");
    let chain_len = MAX_WHY_NODES + 10;
    for i in 1..chain_len {
        let next = svc
            .remember(&format!("chain link {i}"), &[], None)
            .expect("remember link");
        svc.relate(previous, next, "next").expect("relate");
        previous = next;
    }

    let explanation = svc
        .why("chain link 0, the seed", chain_len, None)
        .expect("why");

    assert_eq!(
        explanation.nodes.len(),
        MAX_WHY_NODES,
        "the walk stops at the total node budget, well short of the full chain"
    );
}

#[test]
fn why_on_isolated_memory_returns_just_that_memory() {
    let (_dir, svc) = service();
    let lone = svc
        .remember("a fact with no relations", &[], None)
        .expect("remember");

    let explanation = svc.why("a fact with no relations", 3, None).expect("why");

    assert_eq!(explanation.nodes.len(), 1);
    assert_eq!(explanation.nodes[0].id, lone);
    assert!(explanation.edges.is_empty());
}

// --- Negative --------------------------------------------------------------

#[test]
fn why_on_empty_store_is_empty() {
    let (_dir, svc) = service();

    let explanation = svc.why("anything", 3, None).expect("why on empty store");

    assert!(explanation.nodes.is_empty(), "no seed, no explanation");
    assert!(explanation.edges.is_empty());
}

#[test]
fn why_via_links_argument_builds_the_same_graph() {
    // `remember(fact, links)` must produce edges traversable by `why`,
    // equivalent to explicit `relate` calls.
    let (_dir, svc) = service();
    let pr = svc
        .remember("PR #99 refactors the lock layer", &[], None)
        .expect("remember pr");
    let decision = svc
        .remember(
            DECISION,
            &[Link {
                target: pr,
                relation: "decided_in".to_owned(),
            }],
            None,
        )
        .expect("remember decision with link");

    let ids = why_ids(&svc, 1);

    assert!(
        ids.contains(&decision) && ids.contains(&pr),
        "link arg is traversable by why"
    );
}

#[test]
fn why_drops_edges_to_forgotten_targets() {
    let (_dir, svc) = service();
    let decision = svc
        .remember(DECISION, &[], None)
        .expect("remember decision");
    let pr = svc
        .remember("PR #7 implements the change", &[], None)
        .expect("remember pr");
    svc.relate(decision, pr, "decided_in").expect("relate");
    svc.forget(pr).expect("forget pr");

    let explanation = svc.why(DECISION, 2, None).expect("why");

    let node_ids: std::collections::HashSet<u64> = explanation.nodes.iter().map(|n| n.id).collect();
    assert!(!node_ids.contains(&pr), "forgotten target is not a node");
    for edge in &explanation.edges {
        assert!(
            node_ids.contains(&edge.from) && node_ids.contains(&edge.to),
            "every edge endpoint must be a node — no dangling edge to the forgotten target"
        );
    }
}

#[test]
fn why_on_blank_decision_is_empty() {
    let (_dir, svc, _decision, _pr, _ticket) = seeded_chain();

    let explanation = svc.why("   ", 2, None).expect("why on blank decision");

    assert!(explanation.nodes.is_empty() && explanation.edges.is_empty());
}

#[test]
fn why_cannot_overshoot_the_node_budget_mid_expansion() {
    // Regression for the review of this fix itself. The chain test above can
    // never see an overshoot: with out-degree 1, the budget check before each
    // expansion is exact. With hubs near the boundary it is not — a check
    // that only runs BEFORE an expansion lets the expansion that crosses the
    // line add up to `MAX_WHY_NODE_DEGREE` nodes past it, so the documented
    // ceiling of 500 was actually 563. Nine 64-target hubs cross the line
    // mid-hop and expose exactly that.
    let (_dir, svc) = service();
    let seed = svc
        .remember("hub overshoot seed", &[], None)
        .expect("remember seed");
    for hub_index in 0..9 {
        let hub = svc
            .remember(&format!("hub number {hub_index}"), &[], None)
            .expect("remember hub");
        svc.relate(seed, hub, "spokes").expect("relate seed->hub");
        for target_index in 0..MAX_WHY_NODE_DEGREE {
            let target = svc
                .remember(&format!("target {hub_index}/{target_index}"), &[], None)
                .expect("remember target");
            svc.relate(hub, target, "mentions")
                .expect("relate hub->target");
        }
    }

    let explanation = svc.why("hub overshoot seed", 2, None).expect("why");

    assert_eq!(
        explanation.nodes.len(),
        MAX_WHY_NODES,
        "the node budget is a ceiling, not a suggestion: the expansion that \
         reaches it must stop AT it, not finish its node first"
    );
}

#[test]
fn why_caps_the_total_edges_across_the_whole_walk() {
    // The other half of #1743's own words: "nombre maximal de noeuds ET
    // d'aretes retournes". Every edge followed is recorded even when its
    // target is already visited, so a dense subgraph well under the node
    // budget could still return edges without any bound — 60 fully-connected
    // nodes produce 3 540 directed edges against a node count of 60.
    let (_dir, svc) = service();
    let mut ids = Vec::new();
    for i in 0..60 {
        ids.push(
            svc.remember(&format!("dense clique member {i}"), &[], None)
                .expect("remember member"),
        );
    }
    for &from in &ids {
        for &to in &ids {
            if from != to {
                svc.relate(from, to, "sees").expect("relate");
            }
        }
    }

    let explanation = svc.why("dense clique member 0", 3, None).expect("why");

    assert!(
        explanation.nodes.len() <= MAX_WHY_NODES,
        "sanity: the clique sits well under the node budget"
    );
    assert_eq!(
        explanation.edges.len(),
        MAX_WHY_EDGES,
        "a walk over a dense subgraph must stop recording edges at the edge \
         budget; without one, 60 nodes can still return thousands of edges"
    );
    assert!(
        explanation.truncated,
        "the edge budget stopped this walk mid-node — an exact cut that \
         must be reported (#1820)"
    );
}

// --- Truncation is observable, never silent (#1820) -------------------------

#[test]
fn a_walk_cut_by_a_width_budget_reports_truncation() {
    // A seed whose degree exceeds the per-node budget: the walk follows only
    // MAX_WHY_NODE_DEGREE of its edges, and before #1820 that cut was
    // structurally invisible — a subgraph at exactly the cap read the same
    // as a complete one.
    let (_dir, svc) = service();
    let seed = svc.remember(DECISION, &[], None).expect("remember seed");
    for i in 0..=MAX_WHY_NODE_DEGREE {
        let target = svc
            .remember(&format!("satellite fact {i}"), &[], None)
            .expect("remember satellite");
        svc.relate(seed, target, "cites").expect("relate");
    }

    let explanation = svc.why(DECISION, 1, None).expect("why");
    assert_eq!(
        explanation.edges.len(),
        MAX_WHY_NODE_DEGREE,
        "sanity: the per-node budget did cut the expansion"
    );
    assert!(
        explanation.truncated,
        "a cut walk must SAY it is partial — counts at a cap are ambiguous \
         by construction, which is the defect #1820 names"
    );
}

#[test]
fn a_walk_under_every_budget_is_not_reported_truncated() {
    // The honesty control: the flag must never cry wolf. The canonical
    // three-node chain sits far under every width budget.
    let (_dir, svc, _decision, _pr, _ticket) = seeded_chain();
    let explanation = svc.why(DECISION, 2, None).expect("why");
    assert_eq!(
        explanation.nodes.len(),
        3,
        "sanity: the whole chain is here"
    );
    assert!(
        !explanation.truncated,
        "a complete subgraph must not claim to be partial"
    );
}