crates/mimir-room/src/export.rs
//! Edges OUT of the engine: the edge list of a node set with site counts
//! (a call-graph pane, an edge-level report), and the quotient graph —
//! nodes collapsed by crate / module / repo / file, group × group edge
//! counts (the architecture board, the metro map, the knowledge bubbles).
//! The matrices stay boolean; `count` (how many sites carry an edge) is the
//! log's own column, kept beside them.
use std::collections::{BTreeMap, BTreeSet};
use anyhow::Result;
use mimir_schema::EdgeKind;
use serde::Serialize;
use crate::evidence::{Answer, Emptiness};
use crate::query::Mask;
use crate::snapshot::{E_NEGATED, E_PARTIAL, FastMap, NONE};
use crate::{Room, ser_map};
fn ser_kind<S: serde::Serializer>(k: &EdgeKind, s: S) -> std::result::Result<S::Ok, S::Error> {
s.serialize_str(k.as_str())
}
/// Which edges [`Room::edges`] returns.
#[derive(Debug, Clone, Default)]
pub struct EdgeSel<'a> {
pub kinds: Vec<EdgeKind>,
/// Only edges leaving a node of this mask.
pub from: Option<&'a Mask>,
/// Only edges entering a node of this mask.
pub to: Option<&'a Mask>,
/// Return at most this many (the evidence and `total` carry the rest).
pub cap: Option<usize>,
/// Order by site count, highest first (default: by kind, from, to).
pub heaviest_first: bool,
}
impl<'a> EdgeSel<'a> {
pub fn kinds(kinds: &[EdgeKind]) -> Self {
Self { kinds: kinds.to_vec(), ..Default::default() }
}
/// Both ends inside `m`.
pub fn inside(mut self, m: &'a Mask) -> Self {
self.from = Some(m);
self.to = Some(m);
self
}
pub fn cap(mut self, n: usize) -> Self {
self.cap = Some(n);
self
}
}
/// One exported edge.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
pub struct EdgeOut {
pub from: u64,
pub to: u64,
#[serde(serialize_with = "ser_kind")]
pub kind: EdgeKind,
/// Distinct sites carrying it (call sites, uses …).
pub count: u32,
/// GATED_BY: every mention of the feature sits under `not(…)`.
pub negated: bool,
/// GATED_BY: the feature gates something INSIDE the item, not the item.
pub partial: bool,
/// TOUCHES_TABLE: `read` / `write` / `both`; `None` on every other kind.
#[serde(serialize_with = "crate::ser_str")]
pub access: Option<mimir_schema::Access>,
}
/// The edges selected, and how many there were before the cap.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
pub struct EdgeList {
pub edges: Vec<EdgeOut>,
pub total: u64,
/// Sum of `count` over ALL selected edges (not only the returned ones).
pub sites: u64,
}
impl Emptiness for EdgeList {
fn is_empty_answer(&self) -> bool {
self.total == 0
}
}
/// What nodes collapse into.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum GroupBy {
/// The repo whose rows describe the node (`@universe` = the ring).
Repo,
/// `name@version`.
Crate,
/// The nearest enclosing module (crate root for items at the root), by
/// its readable path.
Module,
/// `repo:path` of the node's span.
File,
}
/// One group of a quotient.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct Group {
/// Unique: `name@version`, a module path, a repo, `repo:path`.
pub key: String,
/// Short label: the crate name, the module's own name, the file name.
pub label: String,
/// The group's own node (the crate / module node), when it is one.
pub node: Option<u64>,
/// Nodes collapsed into it.
pub nodes: u64,
pub node_kinds: BTreeMap<String, u64>,
/// Distinct files its nodes' spans lie in.
pub files: u64,
/// Edges between two of its own nodes.
pub internal: u64,
/// Edges leaving to / arriving from OTHER groups.
pub fan_out: u64,
pub fan_in: u64,
}
/// Edges from one group to another.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct GroupEdge {
/// Indexes into [`Quotient::groups`].
pub from: usize,
pub to: usize,
/// Node-level edges collapsed into this one.
pub edges: u64,
/// Sum of their site counts.
pub sites: u64,
#[serde(serialize_with = "ser_map")]
pub kinds: BTreeMap<EdgeKind, u64>,
}
/// The quotient graph.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct Quotient {
pub by: GroupBy,
/// By key.
pub groups: Vec<Group>,
/// Between DIFFERENT groups, by (from, to).
pub edges: Vec<GroupEdge>,
/// Nodes (of the mask) that belong to no group: no crate / no module
/// ancestor / no span.
pub ungrouped: u64,
}
impl Emptiness for Quotient {
fn is_empty_answer(&self) -> bool {
self.groups.is_empty()
}
}
impl Room {
/// The (from, to) pairs of one kind (sorted), filtered by endpoint masks.
fn kind_pairs(&self, kind: EdgeKind, from: Option<&[bool]>, to: Option<&[bool]>) -> Result<Vec<(u64, u64)>> {
self.kind_pairs_of(kind, None, from, to)
}
/// [`Room::kind_pairs`], with the `from` mask's sorted ordinals when the
/// caller has them: a SPARSE `from` set extracts its rows only
/// (`A(rows, :)`) instead of listing every edge of the kind and
/// filtering — the same sorted pairs, at the cost of the selected rows
/// (a lens selecting the CALLS out of a few functions of an 8.2 M-node
/// ring room listed all of its CALLS edges every time).
fn kind_pairs_of(&self, kind: EdgeKind, from_ords: Option<&[u64]>, from: Option<&[bool]>, to: Option<&[bool]>) -> Result<Vec<(u64, u64)>> {
let g = self.graphs();
let Some(m) = g.a.get(&kind) else { return Ok(Vec::new()) };
if let Some(rows) = from_ords.filter(|r| r.len() * 8 < self.len()) {
let mut e = m.row_edges(rows)?;
drop(g);
if let Some(b) = to {
e.retain(|(_, t)| b[*t as usize]);
}
return Ok(e);
}
let mut e = m.edges()?;
drop(g);
if from.is_some() || to.is_some() {
e.retain(|(f, t)| from.is_none_or(|b| b[*f as usize]) && to.is_none_or(|b| b[*t as usize]));
}
Ok(e)
}
/// The edges `sel` selects, with their site counts.
pub fn edges(&self, sel: &EdgeSel<'_>) -> Result<Answer<EdgeList>> {
let mut ev = self.evidence(
format!("edges({:?}, from {:?}, to {:?}, cap {:?})", sel.kinds, sel.from.map(|m| m.len()), sel.to.map(|m| m.len()), sel.cap),
sel.kinds.contains(&EdgeKind::InstanceOf),
&sel.kinds,
);
for m in [sel.from, sel.to].into_iter().flatten() {
self.check_mask(m)?;
}
let (fb, tb) = (sel.from.map(Mask::bitmap), sel.to.map(Mask::bitmap));
let mut edges = Vec::new();
for k in sel.kinds.iter().collect::<BTreeSet<_>>() {
for (from, to) in self.kind_pairs_of(*k, sel.from.map(Mask::ordinals), fb.as_deref(), tb.as_deref())? {
let flags = self.flags_of(*k, from, to);
edges.push(EdgeOut { from, to, kind: *k, count: self.count_of(*k, from, to), negated: flags & E_NEGATED != 0, partial: flags & E_PARTIAL != 0, access: self.access_of(*k, from, to) });
}
}
let total = edges.len();
let sites = edges.iter().map(|e| e.count as u64).sum();
if sel.heaviest_first {
edges.sort_by(|a, b| b.count.cmp(&a.count).then((a.kind, a.from, a.to).cmp(&(b.kind, b.from, b.to))));
}
if let Some(c) = sel.cap {
ev.cap(c.min(total), total);
edges.truncate(c);
}
Ok(Answer::new(EdgeList { edges, total: total as u64, sites }, ev))
}
/// The group of every node under `by`: (group index per node, the groups).
///
/// No allocation per node: a group's key and label are built once, when
/// its first node is met (by the interned ids that make it); node kinds
/// and files are counted by id and named at the end.
fn groups(&self, by: GroupBy, within: Option<&Mask>) -> (Vec<u32>, Vec<Group>, u64) {
let t = &self.snap.nodes;
let n = t.len();
let mut of = vec![NONE; n];
// the interned ids a group is made of → its index; the key → its index
// (two id pairs can spell one key: a missing version and an empty one)
let mut by_ids: FastMap<(u32, u32), u32> = FastMap::default();
let mut by_key: FastMap<String, u32> = FastMap::default();
let mut groups: Vec<Group> = Vec::new();
let mut ungrouped = 0u64;
let k_slots = t.kinds.len() + 1;
let mut kind_counts: Vec<u64> = Vec::new();
let mut files: Vec<(u32, u32)> = Vec::new();
for i in 0..n {
if within.is_some_and(|m| !m.contains(i as u64)) {
continue;
}
let ids = match by {
GroupBy::Repo => (t.repo[i] != NONE).then(|| (t.repo[i], 0)),
GroupBy::Crate => (t.krate[i] != NONE && !t.crates[t.krate[i] as usize].is_empty()).then(|| (t.krate[i], t.version[i])),
GroupBy::Module => self.module_of(i as u64).map(|m| (m as u32, 0)),
GroupBy::File => (t.span_file[i] != NONE).then(|| (t.span_file[i], 0)),
};
let Some(ids) = ids else {
ungrouped += 1;
continue;
};
let gi = match by_ids.get(&ids) {
Some(g) => *g,
None => {
let (key, label, node) = match by {
GroupBy::Repo => {
let r = &t.repos[ids.0 as usize];
(r.clone(), r.clone(), None)
}
GroupBy::Crate => {
let c = &t.crates[ids.0 as usize];
let v = if ids.1 == NONE { "" } else { t.versions[ids.1 as usize].as_str() };
(format!("{c}@{v}"), c.clone(), None)
}
GroupBy::Module => {
let m = ids.0 as u64;
(self.display_path(m), self.node(m).name.unwrap_or_else(|| self.moniker(m)).to_string(), Some(m))
}
GroupBy::File => {
let f = &t.files[ids.0 as usize];
(format!("{}:{}", f.repo, f.path), f.path.rsplit('/').next().unwrap_or(&f.path).to_string(), None)
}
};
let g = match by_key.get(&key) {
Some(g) => *g,
None => {
let g = groups.len() as u32;
by_key.insert(key.clone(), g);
groups.push(Group { key, label, node, nodes: 0, node_kinds: BTreeMap::new(), files: 0, internal: 0, fan_out: 0, fan_in: 0 });
kind_counts.resize(groups.len() * k_slots, 0);
g
}
};
by_ids.insert(ids, g);
g
}
};
of[i] = gi;
groups[gi as usize].nodes += 1;
let kind = if t.kind[i] == NONE { t.kinds.len() } else { t.kind[i] as usize };
kind_counts[gi as usize * k_slots + kind] += 1;
if t.span_file[i] != NONE {
files.push((gi, t.span_file[i]));
}
}
for (gi, g) in groups.iter_mut().enumerate() {
for (k, c) in kind_counts[gi * k_slots..(gi + 1) * k_slots].iter().enumerate() {
if *c > 0 {
let name = if k == t.kinds.len() { "(none)" } else { t.kinds[k].as_str() };
*g.node_kinds.entry(name.to_string()).or_default() += *c;
}
}
}
files.sort_unstable();
files.dedup();
for (gi, _) in &files {
groups[*gi as usize].files += 1;
}
// a crate group's own node: the crate root node of that crate
if by == GroupBy::Crate
&& let Some(crate_kind) = t.kinds.iter().position(|k| k == mimir_schema::kind::CRATE)
{
for i in 0..n {
if of[i] != NONE && t.kind[i] == crate_kind as u32 {
groups[of[i] as usize].node.get_or_insert(i as u64);
}
}
}
(of, groups, ungrouped)
}
/// The quotient graph: the nodes (of `within`, when given) collapsed
/// `by` crate / module / repo / file, and the edges of `kinds` between
/// the groups with how many node-level edges and sites each carries.
/// Groups are sorted by key; an edge inside one group is counted in
/// its `internal`, never listed.
pub fn quotient(&self, by: GroupBy, kinds: &[EdgeKind], within: Option<&Mask>) -> Result<Answer<Quotient>> {
let mut ev = self.evidence(format!("quotient({by:?}, {kinds:?}, within {:?})", within.map(|m| m.len())), kinds.contains(&EdgeKind::InstanceOf), kinds);
if let Some(m) = within {
self.check_mask(m)?;
}
let (of, mut groups, ungrouped) = self.groups(by, within);
if ungrouped > 0 {
ev.note(format!(
"{ungrouped} node(s) belong to no group ({}): their edges are not in the quotient",
match by {
GroupBy::Repo => "no describing row",
GroupBy::Crate => "no crate attribute",
GroupBy::Module => "no module / crate ancestor in the room: a reference stub, a binary-only node",
GroupBy::File => "no span row: a stub, a ring item, a binary-only node",
}
));
}
if by == GroupBy::File && self.snap.nodes.files.is_empty() {
ev.miss("code_span_events", None, "the room holds no span: nothing can be grouped by file");
}
// sorted group order
let mut order: Vec<usize> = (0..groups.len()).collect();
order.sort_by(|a, b| groups[*a].key.cmp(&groups[*b].key));
let mut pos = vec![0usize; groups.len()];
for (p, g) in order.iter().enumerate() {
pos[*g] = p;
}
let mut acc: FastMap<(usize, usize), GroupEdge> = FastMap::default();
for k in kinds.iter().collect::<BTreeSet<_>>() {
for (f, t) in self.kind_pairs(*k, None, None)? {
let (gf, gt) = (of[f as usize], of[t as usize]);
if gf == NONE || gt == NONE {
continue;
}
if gf == gt {
groups[gf as usize].internal += 1;
continue;
}
groups[gf as usize].fan_out += 1;
groups[gt as usize].fan_in += 1;
let (pf, pt) = (pos[gf as usize], pos[gt as usize]);
let e = acc.entry((pf, pt)).or_insert_with(|| GroupEdge { from: pf, to: pt, edges: 0, sites: 0, kinds: BTreeMap::new() });
e.edges += 1;
e.sites += self.count_of(*k, f, t) as u64;
*e.kinds.entry(*k).or_default() += 1;
}
}
let mut sorted: Vec<Option<Group>> = groups.into_iter().map(Some).collect();
let groups: Vec<Group> = order.iter().map(|g| sorted[*g].take().expect("each group once")).collect();
let mut edges: Vec<GroupEdge> = acc.into_values().collect();
edges.sort_unstable_by_key(|e| (e.from, e.to));
Ok(Answer::new(Quotient { by, groups, edges, ungrouped }, ev))
}
}