crates/mimir-room/src/lookup.rs
//! Name → node. A moniker is exact; people and tools say `Table::open`,
//! `open`, or hand over a linker symbol. Every match is a node of THIS room;
//! what did not match is said in the evidence, never returned as "nothing
//! is called that" when the room simply has no names for the scope.
use std::collections::BTreeSet;
use anyhow::Result;
use crate::Room;
use crate::evidence::Answer;
use crate::query::Mask;
use crate::snapshot::NONE;
/// How [`NameQuery::text`] is matched.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum NameMatch {
/// Try, in order: the moniker itself, a linker symbol, then the path
/// suffix; the first that matches anything wins (the evidence says which).
#[default]
Auto,
/// `text` is a moniker.
Moniker,
/// The item's own name equals `text` (`open`).
Name,
/// `text` is a `::` path and matches a SUFFIX of the node's
/// [`Room::display_path`] on segment borders: `Table::open`,
/// `store::Table::open`, `skade::store::Table::open` all find the
/// method; `open` alone is [`NameMatch::Name`].
Path,
/// `text` occurs in the item's name (case-insensitive) or in its moniker.
Substring,
/// `text` is a linker symbol (mangled) or its demangled form, of a
/// linked artifact in the binary stream — or the link name a foreign
/// item is declared with (`link_name`, the source's side of the border).
Symbol,
}
/// A name lookup.
#[derive(Debug, Clone, Default)]
pub struct NameQuery {
pub text: String,
pub mode: NameMatch,
/// Keep only these node kinds (`fn`, `method`, `struct` …); empty = all.
pub node_kinds: Vec<String>,
/// Keep only source definitions.
pub defined_only: bool,
/// Keep only nodes of this mask.
pub within: Option<Mask>,
/// Return at most this many (the evidence carries the total).
pub limit: Option<usize>,
}
impl NameQuery {
pub fn new(text: impl Into<String>) -> Self {
Self { text: text.into(), ..Default::default() }
}
pub fn mode(mut self, m: NameMatch) -> Self {
self.mode = m;
self
}
pub fn kinds(mut self, kinds: &[&str]) -> Self {
self.node_kinds = kinds.iter().map(|k| k.to_string()).collect();
self
}
pub fn limit(mut self, n: usize) -> Self {
self.limit = Some(n);
self
}
}
impl Room {
/// Ordinals with a name, sorted by (name, ordinal).
fn name_index(&self) -> &[u32] {
self.snap.name_idx.get_or_init(|| {
let t = &self.snap.nodes;
let mut v: Vec<u32> = (0..t.len() as u32).filter(|i| t.name[*i as usize] != NONE).collect();
v.sort_unstable_by(|a, b| t.strs[t.name[*a as usize] as usize].cmp(&t.strs[t.name[*b as usize] as usize]).then(a.cmp(b)));
v
})
}
fn by_name(&self, name: &str) -> Vec<u64> {
let t = &self.snap.nodes;
let idx = self.name_index();
let of = |i: &u32| t.strs[t.name[*i as usize] as usize].as_str();
let at = idx.partition_point(|i| of(i) < name);
idx[at..].iter().take_while(|i| of(i) == name).map(|i| *i as u64).collect()
}
/// (stable form, ordinal), sorted, of every node whose moniker differs
/// from its stable form.
fn stable_index(&self) -> &[(String, u32)] {
self.snap.stable_idx.get_or_init(|| {
let names = &self.snap.nodes.names;
let mut v: Vec<(String, u32)> = (0..self.snap.nodes.len() as u32)
.filter_map(|i| match mimir_schema::moniker::stable(names.get(i as u64)) {
std::borrow::Cow::Borrowed(_) => None,
std::borrow::Cow::Owned(s) => Some((s, i)),
})
.collect();
v.sort_unstable();
v
})
}
/// The node(s) whose moniker's STABLE form is `id` — how a stable id
/// (the ingest keys by them since mimir-schema 5) finds its node(s),
/// whose stored monikers keep their real versions. A moniker that IS its
/// own stable form is found by [`Room::ordinal`] instead.
pub(crate) fn stable_ordinals(&self, id: &str) -> Vec<u64> {
let idx = self.stable_index();
let at = idx.partition_point(|(s, _)| s.as_str() < id);
idx[at..].iter().take_while(|(s, _)| s == id).map(|(_, i)| *i as u64).collect()
}
fn by_path(&self, text: &str) -> Vec<u64> {
let last = text.rsplit("::").next().unwrap_or(text);
let tail = format!("::{text}");
self.by_name(last)
.into_iter()
.filter(|o| {
let p = self.display_path(*o);
p == text || p.ends_with(&tail)
})
.collect()
}
fn symbol_index(&self) -> &[u32] {
self.snap.symbol_idx.get_or_init(|| {
let s = &self.snap.symbols;
let mut v: Vec<u32> = (0..s.len() as u32).collect();
v.sort_unstable_by(|a, b| s.symbol.get(*a as usize).cmp(s.symbol.get(*b as usize)));
v
})
}
fn by_symbol(&self, text: &str) -> Vec<u64> {
let s = &self.snap.symbols;
let idx = self.symbol_index();
let at = idx.partition_point(|i| s.symbol.get(*i as usize) < text);
let mut out: BTreeSet<u64> = idx[at..].iter().take_while(|i| s.symbol.get(**i as usize) == text).map(|i| s.node[*i as usize] as u64).collect();
if out.is_empty() {
// the demangled form (not indexed: one pass over the symbol rows)
out.extend((0..s.len()).filter(|i| s.demangled.get(*i) == text).map(|i| s.node[i] as u64));
}
if out.is_empty() {
// the FFI border by the name the linker knows it under: a foreign
// item DECLARED with this link name (the source's own column, so it
// answers with no binary stream too)
out.extend(self.by_link_name(text));
}
out.into_iter().collect()
}
/// Foreign items whose `link_name` is `text` (one pass over the nodes).
fn by_link_name(&self, text: &str) -> Vec<u64> {
if !self.has_attr("link_name") {
return Vec::new();
}
(0..self.snap.nodes.len() as u64).filter(|o| self.attr(*o, "link_name").and_then(|v| v.as_str()) == Some(text)).collect()
}
fn by_substring(&self, text: &str) -> Vec<u64> {
let t = &self.snap.nodes;
let low = text.to_lowercase();
let hit: Vec<bool> = t.strs.iter().map(|s| s.to_lowercase().contains(&low)).collect();
(0..t.len())
.filter(|i| (t.name[*i] != NONE && hit[t.name[*i] as usize]) || t.names.get(*i as u64).contains(text))
.map(|i| i as u64)
.collect()
}
/// The nodes `q` names, by ordinal. Empty with the reason in the
/// evidence: no such name, or no names in the room at all.
pub fn lookup(&self, q: &NameQuery) -> Result<Answer<Vec<u64>>> {
let mut ev = self.evidence(format!("lookup({:?}, {:?}, kinds {:?})", q.text, q.mode, q.node_kinds), q.mode == NameMatch::Symbol, &[]);
let t = &self.snap.nodes;
let (mut hits, how) = match q.mode {
NameMatch::Moniker => (self.ordinal(&q.text).into_iter().collect(), "moniker"),
NameMatch::Name => (self.by_name(&q.text), "name"),
NameMatch::Path => (self.by_path(&q.text), "path suffix"),
NameMatch::Substring => (self.by_substring(&q.text), "substring"),
NameMatch::Symbol => (self.by_symbol(&q.text), "linker symbol"),
NameMatch::Auto => {
let exact: Vec<u64> = self.ordinal(&q.text).into_iter().collect();
if !exact.is_empty() {
(exact, "moniker")
} else {
let sym = self.by_symbol(&q.text);
if !sym.is_empty() { (sym, "linker symbol") } else { (self.by_path(&q.text), "path suffix") }
}
}
};
if !hits.is_empty() || q.mode != NameMatch::Auto {
ev.note(format!("matched as: {how}"));
}
if q.mode == NameMatch::Symbol && self.snap.symbols.len() == 0 && hits.is_empty() {
ev.miss("linked symbols", None, "the room holds no symbol row (no binary stream in this scope): a symbol cannot be resolved here");
}
if matches!(q.mode, NameMatch::Name | NameMatch::Path | NameMatch::Auto) && !t.is_empty() && t.name.iter().all(|n| *n == NONE) {
ev.miss("node names", None, "no node of this room carries a `name` (the log's node schema has none): only monikers resolve");
}
if !q.node_kinds.is_empty() {
let want: Vec<u32> = q
.node_kinds
.iter()
.filter_map(|k| {
let p = t.kinds.iter().position(|x| x == k);
if p.is_none() {
ev.miss(format!("node kind `{k}`"), None, format!("no node of this room has node kind `{k}`"));
}
p.map(|p| p as u32)
})
.collect();
hits.retain(|o| want.contains(&t.kind[*o as usize]));
}
if q.defined_only {
hits.retain(|o| self.node(*o).defined);
}
if let Some(m) = &q.within {
self.check_mask(m)?;
hits.retain(|o| m.contains(*o));
}
hits.sort_unstable();
hits.dedup();
if let Some(n) = q.limit {
ev.cap(n.min(hits.len()), hits.len());
hits.truncate(n);
}
Ok(Answer::new(hits, ev))
}
}