sinter_store/

traverse.rs

//! Graph traversals over the persisted adjacency tables: reverse blast
//! radius and shortest path. Point reads only — never loads the corpus.

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

use sinter_core::{Confidence, CorpusScope, Edge, Evidence, Node, NodeId, Relation};

use crate::error::StoreError;
use crate::store::{FILE_SCOPE, IN_EDGES, NODE_SCOPE, NODES, OUT_EDGES, Store};

/// Per-node scope through the single resolution rule in `scope::resolve`.
fn scope_of(
    node_scopes: &impl redb::ReadableTable<&'static str, &'static str>,
    file_scopes: &impl redb::ReadableTable<&'static str, &'static str>,
    id: &str,
) -> Result<CorpusScope, StoreError> {
    let file = id.split_once('#').map_or(id, |(file, _)| file);
    let file_scope = file_scopes
        .get(file)?
        .and_then(|guard| CorpusScope::from_str_opt(guard.value()));
    Ok(crate::scope::resolve(
        |key| {
            node_scopes
                .get(key)
                .ok()
                .flatten()
                .and_then(|guard| CorpusScope::from_str_opt(guard.value()))
        },
        file_scope,
        id,
        file,
    ))
}

/// Which edges a traversal may walk. Containment is structure, not
/// dependency, so it never participates.
#[derive(Debug, Default, Clone)]
pub struct EdgeFilter {
    /// Allowed evidence kinds; None = all.
    pub evidence: Option<BTreeSet<Evidence>>,
    /// Minimum confidence; None = any.
    pub min_confidence: Option<Confidence>,
    /// Allowed relations; None = all (Contains stays excluded either way).
    pub relations: Option<BTreeSet<Relation>>,
    /// Allowed corpus roles for nodes entered after the explicit start.
    /// None = all. Exact lookup of the start remains independent of scope.
    pub scopes: Option<BTreeSet<CorpusScope>>,
}

impl EdgeFilter {
    pub fn admits(&self, edge: &Edge) -> bool {
        if edge.relation == Relation::Contains {
            return false;
        }
        if let Some(allowed) = &self.relations
            && !allowed.contains(&edge.relation)
        {
            return false;
        }
        if let Some(allowed) = &self.evidence
            && !allowed.contains(&edge.evidence)
        {
            return false;
        }
        if self.min_confidence == Some(Confidence::Certain)
            && edge.confidence != Confidence::Certain
        {
            return false;
        }
        true
    }

    pub fn admits_scope(&self, scope: CorpusScope) -> bool {
        self.scopes
            .as_ref()
            .is_none_or(|allowed| allowed.contains(&scope))
    }
}

/// One step of a traversal result: the node reached, how deep, and the edge
/// that reached it.
pub struct Reached {
    pub node: Node,
    pub depth: usize,
    pub via: Edge,
}

/// Depth-1 dependents and the distinct files they live in — the "who
/// actually calls this" number, distinct from the transitive total that
/// otherwise reads as a caller count.
pub fn direct_summary(reached: &[Reached]) -> (usize, usize) {
    // File `use` lines are dependents, not callers: keep them out of "direct".
    let direct: Vec<&Reached> = reached
        .iter()
        .filter(|r| r.depth == 1 && r.via.relation != Relation::Imports)
        .collect();
    let files: std::collections::HashSet<&str> =
        direct.iter().map(|r| r.node.file.as_str()).collect();
    (direct.len(), files.len())
}

impl Store {
    /// Reverse blast radius: everything transitively depending on `id`
    /// (incoming non-Contains edges), breadth-first, deduplicated.
    pub fn dependents(
        &self,
        id: &NodeId,
        filter: &EdgeFilter,
        max_depth: usize,
    ) -> Result<Vec<Reached>, StoreError> {
        let txn = self.db.begin_read()?;
        let nodes = txn.open_table(NODES)?;
        let scopes = txn.open_table(FILE_SCOPE)?;
        let node_scopes = txn.open_table(NODE_SCOPE)?;
        let incoming = txn.open_multimap_table(IN_EDGES)?;
        let mut seen: HashSet<NodeId> = HashSet::from([id.clone()]);
        let mut queue: VecDeque<(NodeId, usize)> = VecDeque::from([(id.clone(), 0)]);
        let mut out = Vec::new();
        while let Some((current, depth)) = queue.pop_front() {
            if depth >= max_depth {
                continue;
            }
            for guard in incoming.get(current.as_str())? {
                let edge: Edge = postcard::from_bytes(guard?.value())?;
                let scope = scope_of(&node_scopes, &scopes, edge.src.as_str())?;
                if !filter.admits(&edge)
                    || !filter.admits_scope(scope)
                    || !seen.insert(edge.src.clone())
                {
                    continue;
                }
                if let Some(guard) = nodes.get(edge.src.as_str())? {
                    let node = postcard::from_bytes(guard.value())?;
                    queue.push_back((edge.src.clone(), depth + 1));
                    out.push(Reached {
                        node,
                        depth: depth + 1,
                        via: edge,
                    });
                }
            }
        }
        Ok(out)
    }

    /// Forward transitive closure: everything `id` depends on (outgoing
    /// non-Contains edges), breadth-first, deduplicated. A file start seeds
    /// through its Contains edges (a file's dependencies live in the
    /// symbols it contains), silently — containment is not a dependency.
    pub fn dependencies(
        &self,
        id: &NodeId,
        filter: &EdgeFilter,
        max_depth: usize,
    ) -> Result<Vec<Reached>, StoreError> {
        let txn = self.db.begin_read()?;
        let nodes = txn.open_table(NODES)?;
        let scopes = txn.open_table(FILE_SCOPE)?;
        let node_scopes = txn.open_table(NODE_SCOPE)?;
        let outgoing = txn.open_multimap_table(OUT_EDGES)?;
        let mut seen: HashSet<NodeId> = HashSet::from([id.clone()]);
        let mut queue: VecDeque<(NodeId, usize)> = VecDeque::from([(id.clone(), 0)]);
        if nodes
            .get(id.as_str())?
            .map(|guard| postcard::from_bytes::<Node>(guard.value()))
            .transpose()?
            .is_some_and(|n| n.kind == sinter_core::SymbolKind::File)
        {
            for guard in outgoing.get(id.as_str())? {
                let edge: Edge = postcard::from_bytes(guard?.value())?;
                if edge.relation == Relation::Contains && seen.insert(edge.dst.clone()) {
                    queue.push_back((edge.dst.clone(), 0));
                }
            }
        }
        let mut out = Vec::new();
        while let Some((current, depth)) = queue.pop_front() {
            if depth >= max_depth {
                continue;
            }
            for guard in outgoing.get(current.as_str())? {
                let edge: Edge = postcard::from_bytes(guard?.value())?;
                let scope = scope_of(&node_scopes, &scopes, edge.dst.as_str())?;
                if !filter.admits(&edge)
                    || !filter.admits_scope(scope)
                    || !seen.insert(edge.dst.clone())
                {
                    continue;
                }
                if let Some(guard) = nodes.get(edge.dst.as_str())? {
                    let node = postcard::from_bytes(guard.value())?;
                    queue.push_back((edge.dst.clone(), depth + 1));
                    out.push(Reached {
                        node,
                        depth: depth + 1,
                        via: edge,
                    });
                }
            }
        }
        Ok(out)
    }

    /// Shortest edge path `from -> to` over outgoing edges, or None.
    pub fn shortest_path(
        &self,
        from: &NodeId,
        to: &NodeId,
        filter: &EdgeFilter,
    ) -> Result<Option<Vec<Edge>>, StoreError> {
        let txn = self.db.begin_read()?;
        let nodes = txn.open_table(NODES)?;
        let scopes = txn.open_table(FILE_SCOPE)?;
        let node_scopes = txn.open_table(NODE_SCOPE)?;
        let outgoing = txn.open_multimap_table(OUT_EDGES)?;
        let mut prev: HashMap<NodeId, Edge> = HashMap::new();
        let mut seen: HashSet<NodeId> = HashSet::from([from.clone()]);
        let mut queue: VecDeque<NodeId> = VecDeque::from([from.clone()]);
        // A file's dependencies live in the symbols it contains; a file
        // start seeds through its contains edges (shown as path steps).
        // Containment stays non-traversable everywhere past the start.
        if nodes
            .get(from.as_str())?
            .map(|guard| postcard::from_bytes::<Node>(guard.value()))
            .transpose()?
            .is_some_and(|n| n.kind == sinter_core::SymbolKind::File)
        {
            for guard in outgoing.get(from.as_str())? {
                let edge: Edge = postcard::from_bytes(guard?.value())?;
                if edge.relation == Relation::Contains && seen.insert(edge.dst.clone()) {
                    prev.insert(edge.dst.clone(), edge.clone());
                    queue.push_back(edge.dst.clone());
                }
            }
        }
        while let Some(current) = queue.pop_front() {
            if &current == to {
                let mut path = Vec::new();
                let mut at = to.clone();
                while &at != from {
                    let edge = prev[&at].clone();
                    at = edge.src.clone();
                    path.push(edge);
                }
                path.reverse();
                return Ok(Some(path));
            }
            for guard in outgoing.get(current.as_str())? {
                let edge: Edge = postcard::from_bytes(guard?.value())?;
                let scope = scope_of(&node_scopes, &scopes, edge.dst.as_str())?;
                if !filter.admits(&edge)
                    || !filter.admits_scope(scope)
                    || !seen.insert(edge.dst.clone())
                {
                    continue;
                }
                prev.insert(edge.dst.clone(), edge.clone());
                queue.push_back(edge.dst.clone());
            }
        }
        Ok(None)
    }
}