crates/mimir-schema/src/mir.rs
//! The MIR fact payload: the ONE grammar the driver writes into the `ty`
//! column of [`kind::MIR_BODY`](crate::kind::MIR_BODY) and
//! [`kind::MIR_BLOCK`](crate::kind::MIR_BLOCK) nodes, and every reader parses.
//!
//! Source: rustc's `mir_promoted` body (built MIR after `SimplifyCfg` and
//! promotion, BEFORE any optimisation): the same source gives the same facts
//! at every `-C opt-level` (what CAN move them is what changes the source's
//! meaning: `-C overflow-checks` / `debug-assertions`, part of the unit's
//! codegen options anyway). Unwind / cleanup blocks are left out.
//!
//! Everything is NAME-FREE: a local is its MIR index (`_3`), never its
//! binding name; a place projection is field indices / deref / index /
//! variant indices; constants are their TYPE (no value). Two copies of one
//! body with renamed locals give the same payload, positions aside.
//!
//! ## `mir_body` (`ty`)
//!
//! ```text
//! 1 ␞ <entry> ␟ <entry> … entry = <block>=<fp>:<term>><succ>+<succ>…
//! ```
//!
//! `<block>` is `3` (the fn's own bb3) or `c1.3` (bb3 of the fn's 1st nested
//! closure / coroutine body); `<fp>` = the block's [`fingerprint`] as 16 hex
//! digits; `<term>` a [`TERM_KINDS`] word.
//!
//! ## `mir_block` (`ty`)
//!
//! ```text
//! <fp> ␞ <terminator> ␞ <stmt> ␟ <stmt> … ␞ <local>:<ty> ␟ … ␞ <a>><b>,<a>><b>…
//! ```
//!
//! * a statement / the terminator is its name-free text — an operand is
//! `_3` (copy), `^_3` (move) or `k:<type>` (a constant) — then `@<dl>:<col>`
//! (line relative to the fn's first line, column 1-based) and `m` when the
//! code comes from a macro expansion (the position is then the macro call
//! site); no `@…` when it lies in another file;
//! * the locals table names every local the block touches with its type;
//! * `a>b` — a def-use pair: local `a` is read where local `b` is written
//! (the value of `a` flows into `b`). Within the body, no kill analysis.
//!
//! [`fingerprint`] hashes the block's statements and terminator with the
//! block's locals renumbered in order of first use (`$0`, `$1` …) and their
//! types — so it is equal for two blocks that do the same thing to the same
//! types, in any two functions, whatever the locals are called or numbered.
/// The MIR fact format (the driver's `stats.mir_facts`): bumped only when
/// this grammar changes. A dump carrying an older one (or none, 0) is still
/// read as it is — its units get the new facts when they are recompiled, or
/// when a consumer asks for them (`mimir-ingest`'s `request_mir_redump`).
pub const FACTS_VERSION: u32 = 1;
/// Section separator (U+001E).
pub const SEP: char = '\u{1e}';
/// Item separator inside a section (U+001F).
pub const ITEM: char = '\u{1f}';
/// The `mir_body` payload's format word ([`encode_body`]).
pub const BODY_FORMAT: &str = "1";
/// Blocks described per body at most (a generated fn can have thousands);
/// the rest are counted, not written.
pub const BLOCKS_PER_BODY: usize = 1024;
/// Statements written per block at most (the fingerprint covers all).
pub const STMTS_PER_BLOCK: usize = 128;
/// The terminator kinds, as written in `<term>`.
pub const TERM_KINDS: &[&str] = &[
"goto", "switch", "return", "unreachable", "drop", "call", "tailcall", "assert", "yield", "coroutine_drop", "false_edge", "false_unwind", "asm", "resume", "terminate",
];
/// FNV-1a, 64 bit: the fingerprint hash (stable across builds and hosts).
pub fn fnv64(bytes: &[u8]) -> u64 {
bytes.iter().fold(0xcbf2_9ce4_8422_2325u64, |h, b| (h ^ *b as u64).wrapping_mul(0x0100_0000_01b3))
}
/// The fingerprint of a block's CANONICAL text (statements, terminator and
/// local types with the locals renumbered in order of first use).
pub fn fingerprint(canonical: &str) -> u64 {
fnv64(canonical.as_bytes())
}
/// The 16-hex spelling of a fingerprint.
pub fn fp_hex(fp: u64) -> String {
format!("{fp:016x}")
}
/// One block of a `mir_body` payload.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BodyBlock<'a> {
/// `3` or `c1.3`.
pub block: &'a str,
pub fp: &'a str,
pub term: &'a str,
pub succ: Vec<&'a str>,
}
/// A `mir_body` payload from its blocks.
pub fn encode_body(blocks: &[(String, u64, &str, Vec<String>)]) -> String {
let mut s = String::from(BODY_FORMAT);
s.push(SEP);
for (i, (b, fp, term, succ)) in blocks.iter().enumerate() {
if i > 0 {
s.push(ITEM);
}
s.push_str(b);
s.push('=');
s.push_str(&fp_hex(*fp));
s.push(':');
s.push_str(term);
s.push('>');
s.push_str(&succ.join("+"));
}
s
}
/// Parse a `mir_body` payload; `None` = not one (another format word).
pub fn parse_body(ty: &str) -> Option<Vec<BodyBlock<'_>>> {
let (fmt, rest) = ty.split_once(SEP)?;
if fmt != BODY_FORMAT {
return None;
}
if rest.is_empty() {
return Some(Vec::new());
}
rest.split(ITEM)
.map(|e| {
let (block, r) = e.split_once('=')?;
let (fp, r) = r.split_once(':')?;
let (term, succ) = r.split_once('>')?;
Some(BodyBlock { block, fp, term, succ: if succ.is_empty() { Vec::new() } else { succ.split('+').collect() } })
})
.collect()
}
/// A statement's / terminator's position: line relative to the fn's first
/// line, 1-based column, and whether it is a macro call site.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Pos {
pub dline: i32,
pub col: u32,
pub macro_site: bool,
}
impl Pos {
pub fn push_to(&self, s: &mut String) {
use std::fmt::Write;
let _ = write!(s, "@{}:{}{}", self.dline, self.col, if self.macro_site { "m" } else { "" });
}
}
/// One statement (or the terminator) of a block: text and position.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Stmt<'a> {
pub text: &'a str,
pub pos: Option<Pos>,
}
fn parse_stmt(s: &str) -> Stmt<'_> {
if let Some((text, p)) = s.rsplit_once('@') {
let (p, macro_site) = match p.strip_suffix('m') {
Some(p) => (p, true),
None => (p, false),
};
if let Some((l, c)) = p.split_once(':') {
if let (Ok(dline), Ok(col)) = (l.parse(), c.parse()) {
return Stmt { text, pos: Some(Pos { dline, col, macro_site }) };
}
}
}
Stmt { text: s, pos: None }
}
/// One `mir_block` payload, parsed.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Block<'a> {
pub fp: &'a str,
pub term: Stmt<'a>,
pub stmts: Vec<Stmt<'a>>,
/// `(local, type)` of every local the block touches.
pub locals: Vec<(u32, &'a str)>,
/// `(a, b)`: `a` is read where `b` is written.
pub def_use: Vec<(u32, u32)>,
}
impl Block<'_> {
/// The terminator's kind word (`call`, `switch` …).
pub fn term_kind(&self) -> &str {
let t = self.term.text;
let end = t.find(|c: char| !(c.is_ascii_alphanumeric() || c == '_')).unwrap_or(t.len());
&t[..end]
}
/// The callee of a `call` / `tailcall` terminator (its stable moniker),
/// `None` for a call through a pointer / a local.
pub fn callee(&self) -> Option<&str> {
let t = self.term.text;
let rest = t.strip_prefix("call ").or_else(|| t.strip_prefix("tailcall "))?;
let end = rest.find(ITEM_CALLEE_END)?;
Some(&rest[..end])
}
/// Every position of the block (statements, then the terminator).
pub fn positions(&self) -> impl Iterator<Item = Pos> + '_ {
self.stmts.iter().filter_map(|s| s.pos).chain(self.term.pos)
}
}
/// Where a call's callee moniker ends in the terminator text: `call <moniker>⟨args⟩`.
pub const ITEM_CALLEE_END: char = '\u{27e8}';
/// Closes a call's argument list.
pub const ITEM_CALLEE_ARGS_END: char = '\u{27e9}';
/// A `mir_block` payload.
pub fn encode_block(fp: u64, term: &str, stmts: &[String], locals: &[(u32, String)], def_use: &[(u32, u32)]) -> String {
use std::fmt::Write;
let mut s = fp_hex(fp);
s.push(SEP);
s.push_str(term);
s.push(SEP);
for (i, st) in stmts.iter().enumerate() {
if i > 0 {
s.push(ITEM);
}
s.push_str(st);
}
s.push(SEP);
for (i, (l, t)) in locals.iter().enumerate() {
if i > 0 {
s.push(ITEM);
}
let _ = write!(s, "{l}:{t}");
}
s.push(SEP);
for (i, (a, b)) in def_use.iter().enumerate() {
if i > 0 {
s.push(',');
}
let _ = write!(s, "{a}>{b}");
}
s
}
/// Parse a `mir_block` payload; `None` = not one.
pub fn parse_block(ty: &str) -> Option<Block<'_>> {
let mut it = ty.split(SEP);
let fp = it.next()?;
if fp.len() != 16 || !fp.bytes().all(|b| b.is_ascii_hexdigit()) {
return None;
}
let term = parse_stmt(it.next()?);
let stmts_s = it.next()?;
let locals_s = it.next()?;
let du_s = it.next()?;
let stmts = if stmts_s.is_empty() { Vec::new() } else { stmts_s.split(ITEM).map(parse_stmt).collect() };
let locals = if locals_s.is_empty() {
Vec::new()
} else {
locals_s.split(ITEM).filter_map(|e| e.split_once(':').and_then(|(l, t)| Some((l.parse().ok()?, t)))).collect()
};
let def_use = if du_s.is_empty() {
Vec::new()
} else {
du_s.split(',').filter_map(|e| e.split_once('>').and_then(|(a, b)| Some((a.parse().ok()?, b.parse().ok()?)))).collect()
};
Some(Block { fp, term, stmts, locals, def_use })
}
/// A statement's text with its locals renumbered in order of first use
/// (`_7` → `$0` …), so the same statement in two bodies is one key.
/// `order` carries the numbering across the statements of one block.
pub fn canonical_locals(text: &str, order: &mut Vec<u32>) -> String {
let b = text.as_bytes();
let mut out = String::with_capacity(text.len());
let mut i = 0;
while i < b.len() {
if b[i] == b'_' && (i == 0 || !(b[i - 1].is_ascii_alphanumeric() || b[i - 1] == b'_')) {
let mut j = i + 1;
while j < b.len() && b[j].is_ascii_digit() {
j += 1;
}
if j > i + 1 && (j == b.len() || !(b[j].is_ascii_alphanumeric() || b[j] == b'_')) {
let n: u32 = text[i + 1..j].parse().unwrap_or(u32::MAX);
let k = match order.iter().position(|x| *x == n) {
Some(k) => k,
None => {
order.push(n);
order.len() - 1
}
};
out.push('$');
out.push_str(&k.to_string());
i = j;
continue;
}
}
let ch = text[i..].chars().next().unwrap_or(' ');
out.push(ch);
i += ch.len_utf8();
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn body_and_block_round_trip() {
let body = encode_body(&[("0".into(), 0xab, "switch", vec!["1".into(), "2".into()]), ("c1.0".into(), 7, "return", vec![])]);
let p = parse_body(&body).unwrap();
assert_eq!(p.len(), 2);
assert_eq!((p[0].block, p[0].term, p[0].succ.clone()), ("0", "switch", vec!["1", "2"]));
assert_eq!(p[0].fp, "00000000000000ab");
assert_eq!((p[1].block, p[1].succ.len()), ("c1.0", 0));
let term = format!("call rust-analyzer cargo a * f().{ITEM_CALLEE_END}_1{ITEM_CALLEE_ARGS_END}->_2@3:9");
let blk = encode_block(5, &term, &["_2=Add(_1,k:u64)@2:5m".into()], &[(1, "u64".into()), (2, "u64".into())], &[(1, 2)]);
let b = parse_block(&blk).unwrap();
assert_eq!(b.term_kind(), "call");
assert_eq!(b.callee(), Some("rust-analyzer cargo a * f()."));
assert_eq!(b.stmts[0].pos, Some(Pos { dline: 2, col: 5, macro_site: true }));
assert_eq!(b.stmts[0].text, "_2=Add(_1,k:u64)");
assert_eq!(b.locals, vec![(1, "u64"), (2, "u64")]);
assert_eq!(b.def_use, vec![(1, 2)]);
assert!(parse_block("not a block").is_none());
assert!(parse_body("2\u{1e}").is_none());
}
#[test]
fn canonical_locals_renumber_by_first_use() {
let mut o = Vec::new();
assert_eq!(canonical_locals("_7=Add(^_3,_7)", &mut o), "$0=Add(^$1,$0)");
assert_eq!(canonical_locals("_3=use(k:Vec<_>)", &mut o), "$1=use(k:Vec<_>)");
assert_eq!(o, vec![7, 3]);
}
}