crates/mimir-room/src/query.rs
//! The typed query API. Directions: `A[i][j]` = edge `i → j` as the log
//! writes it (`f CALLS g`, `impl FOR_TYPE T`, `mono INSTANCE_OF generic`).
//! Forward walks follow edges; dependents walks follow them backwards on
//! the cached `Aᵀ`.
use std::collections::BTreeSet;
use anyhow::{Result, bail};
use mimir_graph::{Vector, ops};
use mimir_schema::{EdgeKind, Level, Origin, Provenance, kind as nk};
use crate::evidence::{Answer, Emptiness, Evidence};
use crate::snapshot::{F_TEST, Graphs, KindMask, NONE, NONE8, kind_bit};
use crate::Room;
/// The Jikes walk (who must be rechecked when these change): reverse reach
/// over CALLS | USES_TYPE | IMPLEMENTS | FOR_TYPE.
pub const JIKES_KINDS: [EdgeKind; 4] = [EdgeKind::Calls, EdgeKind::UsesType, EdgeKind::Implements, EdgeKind::ForType];
/// Seeds the evidence lists by name before it summarises.
const SEED_LIST_CAP: usize = 20;
/// Node selector: AND across fields, OR inside one; an empty field does not
/// restrict.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct MaskSpec {
pub repos: Vec<String>,
/// `name` or `name@version`.
pub crates: Vec<String>,
pub origins: Vec<Origin>,
pub provenances: Vec<Provenance>,
/// Node `kind` strings (`fn`, `ffi`, `ffi_import`, `mono_instance` …).
pub node_kinds: Vec<String>,
/// Only source definitions (no reference stubs, no endpoint-only ids).
pub defined_only: bool,
/// `Some(true)` = only `is_test` nodes, `Some(false)` = only the others.
pub is_test: Option<bool>,
/// Ladder levels (`crate`, `module`, `item`, `part`).
pub levels: Vec<Level>,
/// Only nodes carrying a `cfg` gate.
pub with_cfg: bool,
/// Files (path as the driver wrote it, in any repo of the scope) the
/// node's span lies in.
pub files: Vec<String>,
/// `Some(true)` = only the nameable API of a crate (effective
/// visibility `direct` or `reexported`), `Some(false)` = only what is
/// not. Nodes without the column value match neither.
pub public_api: Option<bool>,
/// `Some(false)` = only items KNOWN to carry no doc comment.
pub has_doc: Option<bool>,
}
impl MaskSpec {
pub fn kinds(kinds: &[&str]) -> Self {
Self { node_kinds: kinds.iter().map(|k| k.to_string()).collect(), ..Default::default() }
}
/// Does the selection depend on the binary stream?
fn binary(&self) -> bool {
!self.provenances.is_empty()
|| self.node_kinds.iter().any(|k| [nk::MONO_INSTANCE, nk::FFI_IMPORT].contains(&k.as_str()))
}
}
/// A node set of one room.
#[derive(Debug, Clone)]
pub struct Mask {
pub spec: MaskSpec,
n: u64,
ords: Vec<u64>,
}
impl Mask {
/// Combine with `other` (same room): `spec` becomes this mask's — it is
/// what the evidence prints, the ordinals are what counts.
fn combine(&self, other: &Mask, keep: impl Fn(bool, bool) -> bool) -> Mask {
let all: BTreeSet<u64> = self.ords.iter().chain(&other.ords).copied().collect();
let ords = all.into_iter().filter(|o| keep(self.contains(*o), other.contains(*o))).collect();
Mask { spec: self.spec.clone(), n: self.n, ords }
}
/// Nodes in either mask.
pub fn union(&self, other: &Mask) -> Mask {
self.combine(other, |a, b| a || b)
}
/// Nodes in both masks.
pub fn intersect(&self, other: &Mask) -> Mask {
self.combine(other, |a, b| a && b)
}
/// Nodes of this mask that are not in `other`.
pub fn minus(&self, other: &Mask) -> Mask {
self.combine(other, |a, b| a && !b)
}
pub fn len(&self) -> usize {
self.ords.len()
}
pub fn is_empty(&self) -> bool {
self.ords.is_empty()
}
/// Sorted ordinals.
pub fn ordinals(&self) -> &[u64] {
&self.ords
}
pub fn contains(&self, o: u64) -> bool {
self.ords.binary_search(&o).is_ok()
}
pub(crate) fn vector(&self) -> Result<Vector<bool>> {
Ok(Vector::<bool>::from_indices(self.n, &self.ords)?)
}
/// Membership as a dense bitmap (edge filters).
pub(crate) fn bitmap(&self) -> Vec<bool> {
let mut b = vec![false; self.n as usize];
for o in &self.ords {
b[*o as usize] = true;
}
b
}
}
/// Where a walk starts: monikers (unknown ones are reported MISSING),
/// ordinals of this room, or a whole [`Mask`]. Every walk takes
/// `impl Into<Seeds>`, so `&["moniker"]`, `&ordinals[..]` and `&mask` all work.
#[derive(Debug, Clone, Copy)]
pub enum Seeds<'a> {
Monikers(&'a [&'a str]),
Ordinals(&'a [u64]),
Mask(&'a Mask),
}
impl<'a> From<&'a [&'a str]> for Seeds<'a> {
fn from(v: &'a [&'a str]) -> Self {
Seeds::Monikers(v)
}
}
impl<'a, const N: usize> From<&'a [&'a str; N]> for Seeds<'a> {
fn from(v: &'a [&'a str; N]) -> Self {
Seeds::Monikers(v)
}
}
impl<'a> From<&'a Vec<&'a str>> for Seeds<'a> {
fn from(v: &'a Vec<&'a str>) -> Self {
Seeds::Monikers(v)
}
}
impl<'a> From<&'a [u64]> for Seeds<'a> {
fn from(v: &'a [u64]) -> Self {
Seeds::Ordinals(v)
}
}
impl<'a, const N: usize> From<&'a [u64; N]> for Seeds<'a> {
fn from(v: &'a [u64; N]) -> Self {
Seeds::Ordinals(v)
}
}
impl<'a> From<&'a Vec<u64>> for Seeds<'a> {
fn from(v: &'a Vec<u64>) -> Self {
Seeds::Ordinals(v)
}
}
impl<'a> From<&'a Mask> for Seeds<'a> {
fn from(m: &'a Mask) -> Self {
Seeds::Mask(m)
}
}
impl Seeds<'_> {
fn count(&self) -> usize {
match self {
Seeds::Monikers(m) => m.len(),
Seeds::Ordinals(o) => o.len(),
Seeds::Mask(m) => m.len(),
}
}
}
/// Node weights of a weighted walk: `default` for every node of the room,
/// `set` overriding it per ordinal. Integers: scale a fraction yourself
/// (trust 0.85 → 850_000) so equal weights compare equal.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Weights {
pub default: u64,
pub set: Vec<(u64, u64)>,
}
impl Emptiness for Mask {
fn is_empty_answer(&self) -> bool {
self.ords.is_empty()
}
}
/// A walk: the seeds the room knew, and every node reached (seeds excluded).
#[derive(Debug, Clone, Default, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Walk {
pub seeds: Vec<u64>,
pub reached: Vec<u64>,
}
impl Emptiness for Walk {
fn is_empty_answer(&self) -> bool {
self.reached.is_empty()
}
}
/// Walks per frontier matrix in the batched walks (`NORNIR_BFS_BATCH`, default 64).
fn bfs_batch() -> usize {
std::env::var("NORNIR_BFS_BATCH").ok().and_then(|v| v.parse().ok()).filter(|b: &usize| *b > 0).unwrap_or(64)
}
fn kinds_mask(kinds: &[EdgeKind]) -> KindMask {
kinds.iter().map(|k| kind_bit(*k)).fold(0, |a, b| a | b)
}
fn why_no_edges(k: EdgeKind) -> String {
match k {
EdgeKind::GatedBy => "no open GATED_BY edge in this scope: nothing here is behind a cargo feature, or the log was written by a producer older than mimir-schema 2 (which writes item → feature gates)".into(),
EdgeKind::Enables | EdgeKind::EnablesWeak => format!("no open {k} edge in this scope: its crates declare no feature, or the log predates mimir-schema 2"),
EdgeKind::TouchesTable => "no open TOUCHES_TABLE edge in this scope: none of its fns reaches the storage engine with a table, or the log was written by a producer older than mimir-schema 4 (which writes fn → table)".into(),
EdgeKind::Compatible => format!("{k} belongs to another producer; this log has none"),
EdgeKind::InstanceOf => "INSTANCE_OF comes from the binary stream; no open INSTANCE_OF edge in this scope".into(),
EdgeKind::Syscalls => "no open SYSCALLS edge in this scope: the system boundary lives in the dependency universe (fold it in), and its producer runs once per toolchain / target after a consume".into(),
_ => format!("the source stream holds no open {k} edge in this scope"),
}
}
impl Room {
pub(crate) fn graphs(&self) -> std::sync::MutexGuard<'_, Graphs> {
self.snap.graphs.lock().unwrap_or_else(|e| e.into_inner())
}
/// The evidence every answer starts from: scope, inputs, per-repo gaps
/// (no source rows; with `binary`, no binary stream), and the walked
/// kinds with their edge counts (a kind with none is MISSING).
pub(crate) fn evidence(&self, query: String, binary: bool, kinds: &[EdgeKind]) -> Evidence {
let s = &self.snap;
let mut ev = Evidence { query, scope: s.scope.to_string(), inputs: s.inputs.clone(), ..Default::default() };
if s.scope.repos.is_empty() {
ev.miss("repos", None, "the scope holds no repo (the log has no consumer offset)");
}
for (repo, rows) in &s.repo_rows {
let seq = s.scope.repos[repo];
if rows.source == 0 {
ev.miss("source stream", Some(repo), format!("no open source row for this repo at seq ≤ {seq}"));
}
if binary && rows.binary == 0 {
ev.miss(
"binary stream",
Some(repo),
format!(
"no binary stream for this repo at seq ≤ {seq} (consumed without --with-binary, or nothing linked): \
linked symbols, INSTANCE_OF and provenance `both`/`binary_only` are ABSENT here, not false"
),
);
}
}
for k in kinds {
let n = s.edge_counts.get(k).copied().unwrap_or(0);
ev.kinds.push((*k, n));
if n == 0 {
ev.miss(format!("{k} edges"), None, why_no_edges(*k));
}
}
if let Some((inc, all)) = s.ring_owners {
ev.note(format!(
"ring: {inc} of {all} dumped ring crates are in this scope (DEPENDS_ON closure of its local crates at their seqs, plus what its binaries link)"
));
}
if let Some(cached) = s.ring_lookup {
ev.note(format!(
"ring off, but linked ring items: their definitions come from the ring ({})",
if cached { "cached ring definitions" } else { "ring folded for this build" }
));
}
if !s.unknown_kinds.is_empty() {
ev.note(format!("edge kinds this build does not know were skipped: {:?}", s.unknown_kinds));
}
ev
}
pub(crate) fn walk_note(&self, ev: &mut Evidence) {
if !self.snap.scope.universe {
ev.note("universe ring off: walks stop at the reference stubs of dependency / std items (open the room with universe on to follow them)");
}
}
/// The seed ordinals, sorted; what the room does not know is MISSING in `ev`.
pub(crate) fn seeds<'a>(&self, seeds: impl Into<Seeds<'a>>, ev: &mut Evidence) -> Result<Vec<u64>> {
let monikers = match seeds.into() {
Seeds::Monikers(m) => m,
Seeds::Ordinals(o) => {
let n = self.len() as u64;
let out: BTreeSet<u64> = o.iter().copied().filter(|x| *x < n).collect();
let outside = o.iter().filter(|x| **x >= n).count();
if outside > 0 {
ev.miss("seed", None, format!("{outside} seed ordinal(s) are past this room's {n} nodes (ordinals belong to ONE room)"));
}
return Ok(out.into_iter().collect());
}
Seeds::Mask(m) => {
self.check_mask(m)?;
if m.is_empty() {
ev.miss("seed", None, format!("the seed mask {:?} selects no node", m.spec));
}
return Ok(m.ordinals().to_vec());
}
};
let mut out = BTreeSet::new();
let mut unknown = 0usize;
for m in monikers {
match self.ordinal(m) {
Some(o) => {
out.insert(o);
}
// a STABLE id (the ingest's delta keys by them): the node(s)
// whose stored moniker has that stable form
None => match self.stable_ordinals(m)[..] {
[] => {
unknown += 1;
if unknown <= SEED_LIST_CAP {
ev.miss("seed", None, format!("`{m}` is not a node of this room"));
}
}
ref os => out.extend(os),
},
}
}
if unknown > SEED_LIST_CAP {
ev.miss("seed", None, format!("… and {} more seeds unknown to this room", unknown - SEED_LIST_CAP));
}
Ok(out.into_iter().collect())
}
/// BFS from `seeds` over the kinds in `mask` (`Aᵀ` when `reverse`),
/// inside `within` when given. Seeds are not in the result.
fn walk(&self, seeds: &[u64], mask: KindMask, reverse: bool, max_hops: Option<u32>, within: Option<&Mask>) -> Result<Vec<u64>> {
if seeds.is_empty() {
return Ok(Vec::new());
}
let mut g = self.graphs();
let n = g.n;
let Some(a) = g.get(mask, reverse)? else { return Ok(Vec::new()) };
self.bfs(a, n, seeds, max_hops, within)
}
fn bfs(&self, a: &mimir_graph::Matrix<bool>, n: u64, seeds: &[u64], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Vec<u64>> {
let sv = Vector::<bool>::from_indices(n, seeds)?;
let reached = match within {
Some(m) => {
self.check_mask(m)?;
ops::reach(&sv, &ops::mask_by(a, &m.vector()?)?, max_hops)?
}
None => ops::reach(&sv, a, max_hops)?,
};
let mut out = reached.indices()?;
out.retain(|o| seeds.binary_search(o).is_err());
Ok(out)
}
/// One walk per seed (`seeds[i]` alone), batched: entry `i` = what
/// [`Room::walk`] from `[seeds[i]]` returns. The `within` scope is cut
/// out of the adjacency ONCE for all of them.
fn walk_each(&self, seeds: &[u64], mask: KindMask, reverse: bool, max_hops: Option<u32>, within: Option<&Mask>) -> Result<Vec<Vec<u64>>> {
if seeds.is_empty() {
return Ok(Vec::new());
}
let mut g = self.graphs();
let Some(a) = g.get(mask, reverse)? else { return Ok(vec![Vec::new(); seeds.len()]) };
let masked;
let a = match within {
Some(m) => {
self.check_mask(m)?;
masked = ops::mask_by(a, &m.vector()?)?;
&masked
}
None => a,
};
let mut out = ops::reach_each(seeds, a, max_hops, bfs_batch())?;
for (walk, s) in out.iter_mut().zip(seeds) {
walk.retain(|o| o != s);
}
Ok(out)
}
/// [`Room::dependents`] for each seed set — one answer per entry, the
/// very answer (walk and evidence) `dependents(changed[i], within)`
/// gives — every walk at once as frontier matrices on the cached Jikes
/// matrix.
pub fn dependents_each<'a>(&self, changed: &[Seeds<'a>], within: Option<&Mask>) -> Result<Vec<Answer<Walk>>> {
let mut kinds = JIKES_KINDS.to_vec();
kinds.push(EdgeKind::Contains);
let mut walks: Vec<(Evidence, Vec<u64>)> = Vec::with_capacity(changed.len());
for c in changed {
let mut ev = self.evidence(format!("dependents({} changed, Jikes {JIKES_KINDS:?} + CONTAINS down from impls)", c.count()), false, &kinds);
self.walk_note(&mut ev);
let s = self.seeds(*c, &mut ev)?;
self.within_note(&mut ev, within, &s);
walks.push((ev, s));
}
let live: Vec<&[u64]> = walks.iter().map(|(_, s)| s.as_slice()).filter(|s| !s.is_empty()).collect();
let mut reached = Vec::new().into_iter();
if !live.is_empty() {
let impls = self.mask_ords(&MaskSpec::kinds(&[nk::IMPL]), &mut Evidence::default());
let mut g = self.graphs();
if let Some(w) = g.jikes(kinds_mask(&JIKES_KINDS), &impls)? {
let masked;
let w = match within {
Some(m) => {
self.check_mask(m)?;
masked = ops::mask_by(w, &m.vector()?)?;
&masked
}
None => w,
};
let mut r = ops::reach_sets(&live, w, None, bfs_batch())?;
for (walk, s) in r.iter_mut().zip(&live) {
walk.retain(|o| s.binary_search(o).is_err());
}
reached = r.into_iter();
}
}
let mut out = Vec::with_capacity(walks.len());
for (ev, s) in walks {
let r = if s.is_empty() { Vec::new() } else { reached.next().unwrap_or_default() };
out.push(Answer::new(Walk { seeds: s, reached: r }, ev));
}
Ok(out)
}
/// [`Room::reach`] from each seed alone — one answer per seed, the same
/// answer (walk and evidence) that `reach(&[seed][..], ..)` gives —
/// walked together as one frontier matrix.
pub fn reach_each(&self, seeds: &[u64], kinds: &[EdgeKind], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Vec<Answer<Walk>>> {
let binary = kinds.contains(&EdgeKind::InstanceOf);
self.each(seeds, kinds, false, max_hops, within, |ev_seeds| self.evidence(format!("reach({ev_seeds} seed(s), {kinds:?}, max_hops {max_hops:?})"), binary, kinds))
}
/// [`Room::dependents_by`] for each seed alone (one answer per seed,
/// identical to `dependents_by(&[seed][..], ..)`), walked together on
/// the cached `Aᵀ` as one frontier matrix.
pub fn dependents_by_each(&self, seeds: &[u64], kinds: &[EdgeKind], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Vec<Answer<Walk>>> {
let binary = kinds.contains(&EdgeKind::InstanceOf);
self.each(seeds, kinds, true, max_hops, within, |ev_seeds| self.evidence(format!("dependents({ev_seeds} changed, {kinds:?}, max_hops {max_hops:?})"), binary, kinds))
}
fn each(&self, seeds: &[u64], kinds: &[EdgeKind], reverse: bool, max_hops: Option<u32>, within: Option<&Mask>, evidence: impl Fn(usize) -> Evidence) -> Result<Vec<Answer<Walk>>> {
// per seed: the evidence and seed list a single-seed call builds
let mut walks: Vec<(Evidence, Vec<u64>)> = Vec::with_capacity(seeds.len());
for &o in seeds {
let mut ev = evidence(1);
self.walk_note(&mut ev);
let s = self.seeds(Seeds::Ordinals(&[o][..]), &mut ev)?;
self.within_note(&mut ev, within, &s);
walks.push((ev, s));
}
let live: Vec<u64> = walks.iter().filter_map(|(_, s)| s.first().copied()).collect();
let mut reached = self.walk_each(&live, kinds_mask(kinds), reverse, max_hops, within)?.into_iter();
let mut out = Vec::with_capacity(walks.len());
for (ev, s) in walks {
let r = if s.is_empty() { Vec::new() } else { reached.next().unwrap_or_default() };
out.push(Answer::new(Walk { seeds: s, reached: r }, ev));
}
Ok(out)
}
pub(crate) fn check_mask(&self, m: &Mask) -> Result<()> {
if m.n != self.len() as u64 {
bail!("the mask was made for another room ({} nodes, this one {})", m.n, self.len());
}
Ok(())
}
pub(crate) fn within_note(&self, ev: &mut Evidence, within: Option<&Mask>, seeds: &[u64]) {
if let Some(m) = within {
let outside = seeds.iter().filter(|s| !m.contains(**s)).count();
ev.note(format!("walk restricted to the mask {:?} ({} nodes): paths leave it nowhere", m.spec, m.len()));
if outside > 0 {
ev.miss("seed", None, format!("{outside} seed(s) lie outside the mask: no path from them stays inside it"));
}
}
}
/// Every node reachable from `seeds` along `kinds` in at most `max_hops`
/// steps (`None` = unbounded), optionally only through `within`.
pub fn reach<'a>(&self, seeds: impl Into<Seeds<'a>>, kinds: &[EdgeKind], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Answer<Walk>> {
let seeds = seeds.into();
let binary = kinds.contains(&EdgeKind::InstanceOf);
let mut ev = self.evidence(format!("reach({} seed(s), {kinds:?}, max_hops {max_hops:?})", seeds.count()), binary, kinds);
self.walk_note(&mut ev);
let s = self.seeds(seeds, &mut ev)?;
self.within_note(&mut ev, within, &s);
let reached = self.walk(&s, kinds_mask(kinds), false, max_hops, within)?;
Ok(Answer::new(Walk { seeds: s, reached }, ev))
}
/// The Jikes walk: everything that (transitively) calls, uses, implements
/// or is `impl … for` something in `changed` — reverse reach over
/// [`JIKES_KINDS`] — and, from every impl block reached, DOWN its
/// CONTAINS edges to its items (a changed type invalidates the methods
/// of its impls, and their callers). One cached matrix
/// `Jᵀ ∨ diag(impls)·CONTAINS`. [`Room::dependents_by`] walks a custom
/// kind set backwards only.
pub fn dependents<'a>(&self, changed: impl Into<Seeds<'a>>, within: Option<&Mask>) -> Result<Answer<Walk>> {
let changed = changed.into();
let mut kinds = JIKES_KINDS.to_vec();
kinds.push(EdgeKind::Contains);
let mut ev = self.evidence(format!("dependents({} changed, Jikes {JIKES_KINDS:?} + CONTAINS down from impls)", changed.count()), false, &kinds);
self.walk_note(&mut ev);
let s = self.seeds(changed, &mut ev)?;
self.within_note(&mut ev, within, &s);
let reached = if s.is_empty() {
Vec::new()
} else {
let impls = self.mask_ords(&MaskSpec::kinds(&[nk::IMPL]), &mut Evidence::default());
let mut g = self.graphs();
let n = g.n;
match g.jikes(kinds_mask(&JIKES_KINDS), &impls)? {
Some(w) => self.bfs(w, n, &s, None, within)?,
None => Vec::new(),
}
};
Ok(Answer::new(Walk { seeds: s, reached }, ev))
}
/// The backward walk over caller-chosen kinds: every node that reaches
/// `changed` along `kinds` in at most `max_hops` steps (`None` =
/// unbounded; `Some(1)` = the direct callers / users). No step down into
/// impls — that is [`Room::dependents`].
pub fn dependents_by<'a>(&self, changed: impl Into<Seeds<'a>>, kinds: &[EdgeKind], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Answer<Walk>> {
let changed = changed.into();
let binary = kinds.contains(&EdgeKind::InstanceOf);
let mut ev = self.evidence(format!("dependents({} changed, {kinds:?}, max_hops {max_hops:?})", changed.count()), binary, kinds);
self.walk_note(&mut ev);
let s = self.seeds(changed, &mut ev)?;
self.within_note(&mut ev, within, &s);
let reached = self.walk(&s, kinds_mask(kinds), true, max_hops, within)?;
Ok(Answer::new(Walk { seeds: s, reached }, ev))
}
/// Fewest hops FROM the seeds to every node they reach along `kinds`
/// (the hop layers of a forward walk: an entry point's call tree by
/// depth). Seeds are not listed. Sorted by hops, then ordinal.
pub fn hops_from<'a>(&self, seeds: impl Into<Seeds<'a>>, kinds: &[EdgeKind], max_hops: Option<u32>, within: Option<&Mask>) -> Result<Answer<Vec<(u64, u64)>>> {
let seeds = seeds.into();
let binary = kinds.contains(&EdgeKind::InstanceOf);
let mut ev = self.evidence(format!("hops_from({} seed(s), {kinds:?}, max_hops {max_hops:?})", seeds.count()), binary, kinds);
self.walk_note(&mut ev);
let s = self.seeds(seeds, &mut ev)?;
self.within_note(&mut ev, within, &s);
let mut out = Vec::new();
if !s.is_empty() {
let mut g = self.graphs();
let n = g.n;
if let Some(a) = g.get(kinds_mask(kinds), false)? {
let sv = Vector::<bool>::from_indices(n, &s)?;
let d = match within {
Some(m) => {
self.check_mask(m)?;
ops::min_hops(&sv, &ops::mask_by(a, &m.vector()?)?, max_hops)?
}
None => ops::min_hops(&sv, a, max_hops)?,
};
let (i, x) = d.to_tuples()?;
out = i.into_iter().zip(x).filter(|(o, _)| s.binary_search(o).is_err()).collect();
out.sort_by(|a, b| a.1.cmp(&b.1).then(a.0.cmp(&b.0)));
}
}
Ok(Answer::new(out, ev))
}
fn weight_vector(&self, w: &Weights, ev: &mut Evidence) -> Result<Vector<u64>> {
let n = self.len();
let mut dense = vec![w.default; n];
let mut outside = 0usize;
for (o, x) in &w.set {
match dense.get_mut(*o as usize) {
Some(slot) => *slot = *x,
None => outside += 1,
}
}
if outside > 0 {
ev.miss("weights", None, format!("{outside} weight(s) name ordinals past this room's {n} nodes"));
}
Ok(Vector::<u64>::from_dense(&dense)?)
}
/// The bottleneck walk — the (max, min) semiring over NODE weights: for
/// every node the seeds reach along `kinds`, the best over all seed →
/// node paths of the SMALLEST weight on the path, seed and node
/// included (`(ordinal, value)`, seeds included, by ordinal). "A chain
/// is as strong as its weakest hop; of several chains the strongest
/// counts." A node the seeds do not reach is absent.
pub fn bottleneck<'a>(&self, seeds: impl Into<Seeds<'a>>, kinds: &[EdgeKind], weights: &Weights, within: Option<&Mask>) -> Result<Answer<Vec<(u64, u64)>>> {
let seeds = seeds.into();
let mut ev = self.evidence(
format!("bottleneck({} seed(s), {kinds:?}, (max, min) over node weights: default {}, {} set)", seeds.count(), weights.default, weights.set.len()),
kinds.contains(&EdgeKind::InstanceOf),
kinds,
);
self.walk_note(&mut ev);
let s = self.seeds(seeds, &mut ev)?;
self.within_note(&mut ev, within, &s);
let mut out = Vec::new();
if !s.is_empty() {
let w = self.weight_vector(weights, &mut ev)?;
let sv = Vector::<bool>::from_indices(self.len() as u64, &s)?;
let mut g = self.graphs();
let best = match (g.get(kinds_mask(kinds), false)?, within) {
(Some(a), Some(m)) => {
self.check_mask(m)?;
Some(ops::bottleneck(&sv, &ops::mask_by(a, &m.vector()?)?, &w)?)
}
(Some(a), None) => Some(ops::bottleneck(&sv, a, &w)?),
// no edge of these kinds: every seed still has its own weight
(None, _) => None,
};
drop(g);
out = match best {
Some(b) => {
let (i, x) = b.to_tuples()?;
i.into_iter().zip(x).collect()
}
None => s.iter().map(|o| (*o, weights.set.iter().rev().find(|(i, _)| i == o).map_or(weights.default, |(_, x)| *x))).collect(),
};
}
Ok(Answer::new(out, ev))
}
/// For every node, the LARGEST of `values` over everything it reaches
/// along `kinds`, itself included ("worst severity on any path from
/// here"): `(ordinal, value)` by ordinal. Nodes reaching no valued node
/// are absent.
pub fn worst_on_path(&self, kinds: &[EdgeKind], values: &[(u64, u64)], within: Option<&Mask>) -> Result<Answer<Vec<(u64, u64)>>> {
let mut ev = self.evidence(format!("worst_on_path({kinds:?}, {} valued node(s))", values.len()), kinds.contains(&EdgeKind::InstanceOf), kinds);
self.walk_note(&mut ev);
let n = self.len() as u64;
let mut vals: std::collections::BTreeMap<u64, u64> = std::collections::BTreeMap::new();
for (o, x) in values {
if *o < n {
let slot = vals.entry(*o).or_insert(*x);
*slot = (*slot).max(*x);
}
}
if vals.len() < values.iter().map(|v| v.0).collect::<BTreeSet<_>>().len() {
ev.miss("values", None, format!("some valued ordinals are past this room's {n} nodes"));
}
if vals.is_empty() {
ev.miss("values", None, "no valued node: nothing to propagate");
}
let (idx, x): (Vec<u64>, Vec<u64>) = vals.iter().map(|(o, x)| (*o, *x)).unzip();
let v = Vector::<u64>::from_tuples(n, &idx, &x)?;
let mut g = self.graphs();
let got = match (g.get(kinds_mask(kinds), false)?, within) {
(Some(a), Some(m)) => {
self.check_mask(m)?;
ev.note(format!("walk restricted to the mask {:?} ({} nodes)", m.spec, m.len()));
ops::max_on_path(&ops::mask_by(a, &m.vector()?)?, &v)?
}
(Some(a), None) => ops::max_on_path(a, &v)?,
(None, _) => v,
};
drop(g);
let (i, x) = got.to_tuples()?;
Ok(Answer::new(i.into_iter().zip(x).collect(), ev))
}
/// The node set of explicit ordinals (a lookup's result, a walk's
/// `reached`) as a [`Mask`] — to seed or bound another walk.
pub fn mask_of(&self, ordinals: &[u64]) -> Mask {
let n = self.len() as u64;
let ords: BTreeSet<u64> = ordinals.iter().copied().filter(|o| *o < n).collect();
Mask { spec: MaskSpec::default(), n, ords: ords.into_iter().collect() }
}
fn fan(&self, kind: EdgeKind, top: Option<usize>, incoming: bool) -> Result<Answer<Vec<(u64, u64)>>> {
let what = if incoming { "fan_in" } else { "fan_out" };
let ev = self.evidence(format!("{what}({kind}, top {top:?})"), kind == EdgeKind::InstanceOf, &[kind]);
let mut g = self.graphs();
let v = match g.get(kind_bit(kind), false)? {
Some(a) => {
let d = if incoming { ops::fan_in(a)? } else { ops::fan_out(a)? };
let (i, x) = d.to_tuples()?;
let mut v: Vec<(u64, u64)> = i.into_iter().zip(x).collect();
v.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
if let Some(t) = top {
v.truncate(t);
}
v
}
None => Vec::new(),
};
drop(g);
Ok(Answer::new(v, ev))
}
/// In-degree per node along `kind`, highest first (`top` = keep that many).
pub fn fan_in(&self, kind: EdgeKind, top: Option<usize>) -> Result<Answer<Vec<(u64, u64)>>> {
self.fan(kind, top, true)
}
/// Out-degree per node along `kind`, highest first.
pub fn fan_out(&self, kind: EdgeKind, top: Option<usize>) -> Result<Answer<Vec<(u64, u64)>>> {
self.fan(kind, top, false)
}
/// The node set `spec` selects.
pub fn mask(&self, spec: &MaskSpec) -> Result<Answer<Mask>> {
let mut ev = self.evidence(format!("mask({spec:?})"), spec.binary(), &[]);
let ords = self.mask_ords(spec, &mut ev);
Ok(Answer::new(Mask { spec: spec.clone(), n: self.len() as u64, ords }, ev))
}
fn mask_ords(&self, spec: &MaskSpec, ev: &mut Evidence) -> Vec<u64> {
let t = &self.snap.nodes;
for (asked, col) in [(spec.public_api.is_some(), "effective_visibility"), (spec.has_doc.is_some(), "has_doc")] {
if asked && !t.extras.iter().any(|e| e.name == col) {
ev.miss(col, None, format!("the log's node payload has no `{col}` column (written before mimir-schema 2): no node can match"));
}
}
let ids = |want: &[String], list: &[String], what: &str, ev: &mut Evidence| -> Option<BTreeSet<u32>> {
if want.is_empty() {
return None;
}
let mut out = BTreeSet::new();
for w in want {
match list.iter().position(|x| x == w) {
Some(p) => {
out.insert(p as u32);
}
None => ev.miss(format!("{what} `{w}`"), None, format!("no node of this room has {what} `{w}`")),
}
}
Some(out)
};
let repos = ids(&spec.repos, &t.repos, "repo", ev);
let kinds = ids(&spec.node_kinds, &t.kinds, "node kind", ev);
// crates: `name` or `name@version`
let crate_sel: Option<Vec<(u32, Option<u32>)>> = (!spec.crates.is_empty()).then(|| {
let mut out = Vec::new();
for c in &spec.crates {
let (name, ver) = match c.split_once('@') {
Some((n, v)) => (n, Some(v)),
None => (c.as_str(), None),
};
let Some(ni) = t.crates.iter().position(|x| x == name) else {
ev.miss(format!("crate `{c}`"), None, format!("no node of this room is in crate `{c}`"));
continue;
};
let vi = match ver {
None => None,
Some(v) => match t.versions.iter().position(|x| x == v) {
Some(p) => Some(p as u32),
None => {
ev.miss(format!("crate `{c}`"), None, format!("no node of this room is in crate `{c}`"));
continue;
}
},
};
out.push((ni as u32, vi));
}
out
});
let files: Option<BTreeSet<u32>> = (!spec.files.is_empty()).then(|| {
let mut out = BTreeSet::new();
for want in &spec.files {
let hits: Vec<u32> = t.files.iter().enumerate().filter(|(_, f)| f.path == *want).map(|(i, _)| i as u32).collect();
if hits.is_empty() {
ev.miss(format!("file `{want}`"), None, format!("no span of this room lies in `{want}`"));
}
out.extend(hits);
}
out
});
let levels: Vec<u8> = spec.levels.iter().map(|l| Level::ALL.iter().position(|x| x == l).unwrap_or(0) as u8).collect();
let origins: Vec<u8> = spec.origins.iter().map(|o| Origin::ALL.iter().position(|x| x == o).unwrap_or(0) as u8).collect();
let provs: Vec<u8> = spec.provenances.iter().map(|p| 1 + Provenance::ALL.iter().position(|x| x == p).unwrap_or(0) as u8).collect();
let mut out = Vec::new();
for i in 0..t.len() {
if repos.as_ref().is_some_and(|r| !r.contains(&t.repo[i])) {
continue;
}
if kinds.as_ref().is_some_and(|k| t.kind[i] == NONE || !k.contains(&t.kind[i])) {
continue;
}
if let Some(cs) = &crate_sel
&& !cs.iter().any(|(n, v)| t.krate[i] == *n && v.is_none_or(|v| t.version[i] == v))
{
continue;
}
if !origins.is_empty() && !origins.contains(&t.origin[i]) {
continue;
}
if !provs.is_empty() && !provs.contains(&t.prov[i]) {
continue;
}
if spec.defined_only && !self.node(i as u64).defined {
continue;
}
if spec.is_test.is_some_and(|want| (t.flags[i] & F_TEST != 0) != want) {
continue;
}
if !levels.is_empty() && (t.level[i] == NONE8 || !levels.contains(&t.level[i])) {
continue;
}
if spec.with_cfg && t.cfg[i] == NONE {
continue;
}
if let Some(want) = spec.public_api
&& t.extra_str(i, "effective_visibility").and_then(mimir_schema::EffectiveVisibility::parse).map(|v| v.is_public_api()) != Some(want)
{
continue;
}
if let Some(want) = spec.has_doc
&& t.extra_bool(i, "has_doc") != Some(want)
{
continue;
}
if files.as_ref().is_some_and(|f| t.span_file[i] == NONE || !f.contains(&t.span_file[i])) {
continue;
}
out.push(i as u64);
}
out
}
/// Fewest hops from every node to the nearest node `targets` selects
/// (e.g. the FFI border: kinds `ffi` / `ffi_import`), along `kinds`.
/// Targets themselves are not listed. Sorted by hops, then ordinal.
pub fn min_hops_to(&self, targets: &MaskSpec, kinds: &[EdgeKind], max_hops: Option<u32>) -> Result<Answer<Vec<(u64, u64)>>> {
let binary = targets.binary() || kinds.contains(&EdgeKind::InstanceOf);
let mut ev = self.evidence(format!("min_hops_to({targets:?}, {kinds:?}, max_hops {max_hops:?})"), binary, kinds);
self.walk_note(&mut ev);
let t = self.mask_ords(targets, &mut ev);
if t.is_empty() {
ev.miss("targets", None, format!("no node of this room matches {targets:?}"));
}
let mut out = Vec::new();
if !t.is_empty() {
let mut g = self.graphs();
let n = g.n;
if let Some(at) = g.get(kinds_mask(kinds), true)? {
let d = ops::min_hops(&Vector::<bool>::from_indices(n, &t)?, at, max_hops)?;
let (i, x) = d.to_tuples()?;
out = i.into_iter().zip(x).filter(|(o, _)| t.binary_search(o).is_err()).collect();
out.sort_by(|a, b| a.1.cmp(&b.1).then(a.0.cmp(&b.0)));
}
}
Ok(Answer::new(out, ev))
}
/// The linked monomorphised instances of `generic` (INSTANCE_OF in-edges).
pub fn instances_of(&self, generic: &str) -> Result<Answer<Vec<u64>>> {
let mut ev = self.evidence(format!("instances_of({generic})"), true, &[EdgeKind::InstanceOf]);
let s = self.seeds(&[generic], &mut ev)?;
let v = self.walk(&s, kind_bit(EdgeKind::InstanceOf), true, Some(1), None)?;
Ok(Answer::new(v, ev))
}
/// Structural similarity of the nodes in `subset` along `kind`: pairs
/// `(i, j, shared)`, `i < j` both in the subset, sharing ≥ `min_shared`
/// successors anywhere (`S·A·(S·A)ᵀ`), most first.
pub fn similarity(&self, subset: &Mask, kind: EdgeKind, min_shared: u64, top: Option<usize>) -> Result<Answer<Vec<(u64, u64, u64)>>> {
self.check_mask(subset)?;
let mut ev = self.evidence(format!("similarity({} nodes, {kind}, min_shared {min_shared})", subset.len()), kind == EdgeKind::InstanceOf, &[kind]);
if subset.is_empty() {
ev.miss("subset", None, format!("the mask {:?} selects no node", subset.spec));
}
let mut out = Vec::new();
let mut g = self.graphs();
if let Some(a) = g.get(kind_bit(kind), false)?
&& !subset.is_empty()
{
let c = ops::similarity(&ops::mask_rows(a, &subset.vector()?)?)?;
let (i, j, x) = c.to_tuples()?;
out = i.into_iter().zip(j).zip(x).filter(|((i, j), x)| i < j && *x >= min_shared.max(1)).map(|((i, j), x)| (i, j, x)).collect();
out.sort_by(|a, b| b.2.cmp(&a.2).then((a.0, a.1).cmp(&(b.0, b.1))));
if let Some(t) = top {
out.truncate(t);
}
}
drop(g);
ev.note("similarity: pairs inside the subset, counting shared successors anywhere in the room");
Ok(Answer::new(out, ev))
}
}