crates/mimir-driver/src/walk/tables.rs
//! TOUCHES_TABLE: which fn reads / writes which warehouse table.
//!
//! ## What counts as touching a table
//!
//! A fn touches a table at every place in its body where a table NAME meets a
//! READ or a WRITE of the storage engine. Both halves are facts the compiler
//! holds after type check; nothing here matches a fn by its name.
//!
//! **The anchor is the storage engine's own typed API** — the crate
//! [`ANCHOR_CRATE`] (`iceberg`), the one place every warehouse table access of
//! the constellation ends in, whatever wraps it:
//!
//! | engine item | what it says |
//! |---|---|
//! | `TableIdent::new(ns, name)`, `TableIdent { name, .. }` | `name` names a table; the ident stands for it |
//! | `TableIdent::name`, `.name` | the name back out of an ident |
//! | `Catalog::load_table(&ident)` | the `Table` returned stands for the ident's table |
//! | `Table::scan`, `Table::reader_builder`, `Table::inspect` (and `StaticTable`'s) | READ |
//! | `Transaction::new(&table)` | WRITE (every commit — append, overwrite, schema, properties — goes through one) |
//! | `Catalog::create_table(ns, creation)` · `drop_table` · `purge_table` · `register_table` · `rename_table` | WRITE |
//! | `TableCreationBuilder::name(name)` | the creation stands for the table `name` |
//!
//! Everything between a caller and those — skade's readers and writers,
//! nornir's `IcebergWarehouse` helpers, the `Warehouse` trait's impls, a
//! sibling's own wrapper type — is DERIVED, not listed: each fn gets a
//! [`TableSummary`] saying which of its parameters names a table it reads /
//! writes (`effects`) and which table its return value stands for (`ret`). A
//! fn that only passes its parameter on (`load_and_read_all(wh, table)`) is a
//! conduit: no edge of its own, a summary for its callers. The edge is
//! written where the name STOPS being a parameter:
//!
//! * the argument is a literal, a `const` or a `static` (through any
//! re-export; the compiler's value, read with const evaluation — also a
//! `const` array / slice of names, every element) → an edge to that table;
//! * the argument is a runtime value (a field, a computed string, the element
//! of a runtime list) → an edge to the ONE node
//! `moniker::table(TABLE_UNRESOLVED)`. Never dropped: the readers count and
//! name these sites.
//!
//! The typed handles and wrappers are followed by type: the engine's
//! [`HANDLE_TYPES`], and any struct of any crate with a field of such a type
//! (`skade::Table { inner: iceberg::Table, .. }`) — a value of a wrapper
//! stands for the table of the handle inside it.
//!
//! A call through a trait with no body (`dyn Warehouse`, a generic `C:
//! Catalog`) takes the union of the summaries of the trait method's IMPLS —
//! the ones in this crate and the ones in the crates it loads
//! ([`TableSidecar::trait_methods`]).
//!
//! ## The one annotation: an API with no body to derive from
//!
//! A trait whose impls live DOWNSTREAM of its callers (the seam crate is
//! compiled, and its callers with it, before any impl exists) has nothing to
//! derive from. Such a method — and only such a one — says it itself:
//!
//! ```ignore
//! pub trait Warehouse {
//! #[cfg_attr(mimir, mimir::table(write, table))]
//! fn append_arrow(&self, table: &str, batch: RecordBatch) -> Result<()>;
//! #[cfg_attr(mimir, mimir::table(read, table))]
//! fn scan_arrow(&self, table: &str) -> Result<Vec<RecordBatch>>;
//! }
//! ```
//!
//! `mimir::table(<read | write | both>, <parameter name>)`, once per table
//! parameter. `cfg(mimir)` is set by this driver only (the clippy / kani
//! shape: `--cfg mimir` + the tool registered), so a stable build never sees
//! the attribute; the crate declares the cfg once
//! (`[lints.rust] unexpected_cfgs = { level = "warn", check-cfg = ['cfg(mimir)'] }`).
//! The attribute is read when its own crate is compiled and becomes that
//! item's summary — carried to dependent crates by the sidecar like any
//! derived one. One that names no parameter of the fn, or another access
//! word, is counted in [`CrateStats::table_annotations_bad`], never silently
//! ignored.
//!
//! ## How a value is followed inside one body
//!
//! Demand driven, from the argument back: through `let` (also `let … else`,
//! `if let`, `match` arms, an assignment), `&` / `*` / casts, blocks and
//! branches (the union), `.await` and `?`, the identity conversions of std
//! (`to_string`, `to_owned`, `clone`, `into`, `from`, `as_ref`, `as_str`,
//! `borrow`, `deref`, `iter` / `into_iter` / `next` / `copied` / `cloned`, a
//! `for` over a list of names), `Some` / `Ok`, the summary of a called fn, and
//! — for handle types only — any call that takes a handle and returns one
//! (`ident.clone()`, `.context("…")`, `block_on(fut)`). A string that comes
//! out of any other call (`format!`, `replace`, a lookup) is a runtime value.
//!
//! ## Across crates
//!
//! Each compiled crate writes its summaries next to its sidecar
//! (`<key>.tables.json`, keyed by `DefPathHash`); a dependent crate's compile
//! reads the ones of every crate it loads. Without the sidecar index
//! (`MIMIR_INDEX_DIR` unset) only this crate's own fns and the engine's roots
//! are known, and [`CrateStats::table_sidecars`] says so.
//!
//! ## What is NOT covered (said by the readers, not hidden)
//!
//! * a table reached through a closure parameter or a fn pointer (the callee
//! is a value, the same gap as CALLS);
//! * a call through a trait when NO impl with a table summary is visible to
//! this compile (a crate that only holds `&dyn Warehouse` and is compiled
//! before the impl's crate);
//! * SQL text: a query string is not read for table names here;
//! * the namespace / catalog: the table id is its name only.
use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};
use std::path::PathBuf;
use std::rc::Rc;
use std::time::Instant;
use mimir_driver::{artifact_key_of, read_table_sidecar, write_table_sidecar, TableRef, TableSidecar, TableSummary, TABLE_PASS};
use mimir_schema::moniker;
use mimir_schema::{kind, Access, EdgeKind, Level, NodeRow, Origin, Provenance, TABLE_UNRESOLVED};
use rustc_hir::def::{DefKind, Res};
use rustc_hir::def_id::{DefId, LocalDefId, LOCAL_CRATE};
use rustc_hir::intravisit::{self, Visitor};
use rustc_hir::{self as hir, HirId};
use rustc_middle::hir::nested_filter;
use rustc_middle::mir::interpret::GlobalId;
use rustc_middle::ty::consts::ConstExt;
use rustc_middle::ty::{self, GenericArgKind, Instance, Ty, TyCtxt, TypeVisitableExt, TypingEnv};
use rustc_span::{Span, DUMMY_SP};
use super::Walker;
/// The storage engine's crate (lib name). The vendored arrow-59 fork is the
/// package `iceberg-arrow59`, lib `iceberg`; upstream is `iceberg`.
pub(super) const ANCHOR_CRATE: &str = "iceberg";
/// The engine's types a value of which stands for ONE table.
pub(super) const HANDLE_TYPES: [&str; 9] = [
"TableIdent",
"Table",
"StaticTable",
"TableBuilder",
"TableCreation",
"TableCreationBuilder",
"TableCommit",
"Transaction",
"TableScanBuilder",
];
const R: u8 = Access::READ;
const W: u8 = Access::WRITE;
/// The tool and the attribute of the one annotation: `#[mimir::table(…)]`.
pub(super) const TOOL: &str = mimir_driver::CFG;
const ATTR: &str = "table";
/// The engine's roots: `(container type or trait, method)` → what it says.
/// `effects`: parameter → access; `ret`: the parameters the result stands for.
fn engine_api(container: &str, method: &str) -> Option<(&'static [(u32, u8)], &'static [u32])> {
Some(match (container, method) {
("TableIdent", "new") => (&[], &[1]),
("TableIdent", "name") => (&[], &[0]),
("Catalog", "load_table") => (&[], &[1]),
("Catalog", "create_table") => (&[(2, W)], &[2]),
("Catalog", "drop_table") | ("Catalog", "purge_table") => (&[(1, W)], &[]),
("Catalog", "register_table") => (&[(1, W)], &[1]),
("Catalog", "rename_table") => (&[(1, W), (2, W)], &[]),
("TableCreationBuilder", "name") => (&[], &[1]),
("Table", "scan") | ("Table", "reader_builder") | ("Table", "inspect") => (&[(0, R)], &[]),
("StaticTable", "scan") | ("StaticTable", "reader_builder") => (&[(0, R)], &[]),
("Transaction", "new") => (&[(0, W)], &[0]),
_ => return None,
})
}
/// std's conversions that hand the same value on (by trait).
const IDENTITY_TRAITS: [&str; 9] = ["ToString", "ToOwned", "Clone", "Into", "From", "AsRef", "Borrow", "Deref", "IntoIterator"];
/// `Iterator` methods that hand the items on unchanged.
const IDENTITY_ITER: [&str; 6] = ["next", "copied", "cloned", "by_ref", "rev", "peekable"];
/// Inherent std methods (on `str`, `String`, slices, `Vec`, `Option`,
/// `Result`, `Box`, `Arc`, `Rc`, `Cow`) that hand the same value on.
const IDENTITY_INHERENT: [&str; 22] = [
"as_str", "as_ref", "as_deref", "as_slice", "to_owned", "to_string", "to_vec", "into_owned", "into_string", "into_boxed_str", "iter", "into_iter",
"unwrap", "expect", "ok", "cloned", "copied", "new", "pin", "into_inner", "unwrap_or_default", "first",
];
type Set = Rc<BTreeSet<TableRef>>;
fn unknown() -> Set {
Rc::new(BTreeSet::from([TableRef::Unknown]))
}
/// One place in a body where a table meets a read / write.
#[derive(Debug, Clone, PartialEq, Eq)]
struct Site {
/// `None` = a runtime value.
table: Option<String>,
bits: u8,
span: Span,
}
/// What one look at one body found.
#[derive(Default)]
struct BodyOut {
summary: TableSummary,
sites: Vec<Site>,
/// local fns whose (not yet known) summary a value here depends on
demanded: Vec<LocalDefId>,
}
/// The table state of one crate's walk.
#[derive(Default)]
pub(super) struct Tables {
/// the pass runs: the engine's crate is this crate or one it loads, or a
/// crate in reach (this one included) carries a table summary / the
/// annotation
pub(super) enabled: bool,
/// callee (as written AND as resolved) → the bodies that call it
pub(super) callers: HashMap<DefId, Vec<LocalDefId>>,
/// summaries of this crate's fns
local: HashMap<DefId, TableSummary>,
/// trait method → the union of this crate's impls of it
trait_local: HashMap<DefId, TableSummary>,
/// the loaded crates' summaries, by DefPathHash hex
ext_fns: HashMap<String, TableSummary>,
ext_traits: HashMap<String, TableSummary>,
roots: HashMap<DefId, Option<TableSummary>>,
handle_adts: HashMap<DefId, bool>,
sites: HashMap<LocalDefId, Vec<Site>>,
pub(super) sidecars: (usize, usize),
pub(super) stale: Vec<String>,
/// `#[mimir::table(…)]` attributes read / not understood (the item and why)
pub(super) annotations: usize,
pub(super) bad_annotations: Vec<String>,
pub(super) bodies: usize,
pub(super) visits: usize,
pub(super) ms: u128,
pub(super) n_sites: usize,
pub(super) n_unresolved: usize,
pub(super) names: BTreeSet<String>,
pub(super) n_summaries: usize,
/// the pass panicked (its rows were dropped)
pub(super) error: Option<String>,
}
/// Is the engine's crate this crate or one it loads?
pub(super) fn anchor_in_reach(tcx: TyCtxt<'_>) -> bool {
tcx.crate_name(LOCAL_CRATE).as_str() == ANCHOR_CRATE || tcx.crates(()).iter().any(|c| tcx.crate_name(*c).as_str() == ANCHOR_CRATE)
}
fn hash_key(tcx: TyCtxt<'_>, did: DefId) -> String {
tcx.def_path_hash(did).0.to_hex()
}
fn is_lang_crate(tcx: TyCtxt<'_>, did: DefId) -> bool {
matches!(tcx.crate_name(did.krate).as_str(), "core" | "alloc" | "std")
}
fn peel<'tcx>(mut t: Ty<'tcx>) -> Ty<'tcx> {
while let ty::Ref(_, inner, _) = t.kind() {
t = *inner;
}
t
}
impl Tables {
/// What a `#[mimir::table(access, param)]` on `did` says, if it carries one.
fn annotated(&mut self, tcx: TyCtxt<'_>, did: DefId) -> Option<TableSummary> {
if !matches!(tcx.def_kind(did), DefKind::Fn | DefKind::AssocFn) {
return None;
}
let path = [rustc_span::Symbol::intern(TOOL), rustc_span::Symbol::intern(ATTR)];
let mut out = TableSummary::default();
let mut bad = Vec::new();
for attr in tcx.get_attrs_by_path(did, &path) {
self.annotations += 1;
let words: Vec<String> = attr.meta_item_list().map(|l| l.iter().map(|m| m.ident().map(|i| i.name.to_string()).unwrap_or_default()).collect()).unwrap_or_default();
let bits = match words.first().map(String::as_str) {
Some("read") => R,
Some("write") => W,
Some("both") => R | W,
_ => 0,
};
let param = words.get(1).filter(|_| words.len() == 2).and_then(|p| tcx.fn_arg_idents(did).iter().position(|i| i.is_some_and(|i| i.name.as_str() == p)));
match (bits, param) {
(b, Some(p)) if b != 0 => *out.effects.entry(p as u32).or_insert(0) |= b,
_ => bad.push(format!("{}: `mimir::table({})` — expected `(read | write | both, <a parameter of the fn>)`", tcx.def_path_str(did), words.join(", "))),
}
}
self.bad_annotations.extend(bad);
(!out.is_empty()).then_some(out)
}
/// The engine root a def is, if any: an item of the engine's typed API
/// (the def itself, or — for an impl of an engine trait — the trait
/// method it implements).
fn root(&mut self, tcx: TyCtxt<'_>, did: DefId) -> Option<TableSummary> {
if let Some(r) = self.roots.get(&did) {
return r.clone();
}
let r = self.engine_root(tcx, did);
self.roots.insert(did, r.clone());
r
}
fn engine_root(&mut self, tcx: TyCtxt<'_>, did: DefId) -> Option<TableSummary> {
{
if tcx.def_kind(did) != DefKind::AssocFn {
return None;
}
let parent = tcx.parent(did);
let container = match tcx.def_kind(parent) {
DefKind::Trait => parent,
DefKind::Impl { of_trait: true } => tcx.impl_opt_trait_id(parent)?,
DefKind::Impl { of_trait: false } => match tcx.type_of(parent).instantiate_identity().skip_normalization().kind() {
ty::Adt(adt, _) => adt.did(),
_ => return None,
},
_ => return None,
};
if tcx.crate_name(container.krate).as_str() != ANCHOR_CRATE {
return None;
}
let (effects, ret) = engine_api(tcx.item_name(container).as_str(), tcx.item_name(did).as_str())?;
Some(TableSummary { effects: effects.iter().copied().collect(), ret: ret.iter().map(|p| TableRef::Param(*p)).collect() })
}
}
/// Everything known about what calling `written` (resolved to `resolved`)
/// does with a table argument.
fn summary(&mut self, tcx: TyCtxt<'_>, written: DefId, resolved: DefId) -> Option<TableSummary> {
let mut out = TableSummary::default();
for did in [resolved, written] {
if let Some(r) = self.root(tcx, did) {
out.absorb(&r);
}
if did.is_local() {
if let Some(s) = self.local.get(&did) {
out.absorb(s);
}
} else if !self.ext_fns.is_empty() {
if let Some(s) = self.ext_fns.get(&hash_key(tcx, did)) {
out.absorb(s);
}
}
if did == written && did == resolved && tcx.trait_of_assoc(did).is_some() {
// a trait method nobody resolved to an impl: what its impls do
if let Some(s) = self.trait_local.get(&did) {
out.absorb(s);
}
if !self.ext_traits.is_empty() {
if let Some(s) = self.ext_traits.get(&hash_key(tcx, did)) {
out.absorb(s);
}
}
}
if written == resolved {
break;
}
}
(!out.is_empty()).then_some(out)
}
/// Is `adt` one of the engine's handle types, or a WRAPPER of one: a
/// struct with a field that IS a handle (behind `&` / `Box` / `Arc` /
/// `Rc` / `Option` at most)? A struct that merely holds handles somewhere
/// inside (a catalog, a warehouse with a table cache) is not one: a value
/// of it does not stand for ONE table.
fn handle_adt(&mut self, tcx: TyCtxt<'_>, adt: DefId, depth: u8) -> bool {
if let Some(b) = self.handle_adts.get(&adt) {
return *b;
}
let name = tcx.crate_name(adt.krate);
let b = if name.as_str() == ANCHOR_CRATE {
HANDLE_TYPES.contains(&tcx.item_name(adt).as_str())
} else if depth >= 2 || is_lang_crate(tcx, adt) || !tcx.adt_def(adt).is_struct() {
false
} else {
// no cycle: the answer for a type being looked at is "not yet"
self.handle_adts.insert(adt, false);
let fields: Vec<DefId> = tcx.adt_def(adt).non_enum_variant().fields.iter().map(|f| f.did).collect();
fields.len() <= 64
&& fields.into_iter().any(|f| {
let mut fty = tcx.type_of(f).instantiate_identity().skip_normalization();
// `&T`, `Box<T>`, `Arc<T>`, `Rc<T>`, `Option<T>` → `T`
loop {
fty = match fty.kind() {
ty::Ref(_, inner, _) => *inner,
ty::Adt(a, args) if is_lang_crate(tcx, a.did()) && matches!(tcx.item_name(a.did()).as_str(), "Box" | "Arc" | "Rc" | "Option") => match args.types().next() {
Some(inner) => inner,
None => break,
},
_ => break,
};
}
matches!(fty.kind(), ty::Adt(a, _) if self.handle_adt(tcx, a.did(), depth + 1))
})
};
if depth == 0 || b {
self.handle_adts.insert(adt, b);
} else {
self.handle_adts.remove(&adt);
}
b
}
/// Does a value of this type stand for a table — a handle, a wrapper, or
/// a container / tuple / `Result` / `Option` of one?
fn handle_ty<'tcx>(&mut self, tcx: TyCtxt<'tcx>, t: Ty<'tcx>) -> bool {
t.walk().any(|a| match a.kind() {
GenericArgKind::Type(x) => match x.kind() {
ty::Adt(adt, _) => self.handle_adt(tcx, adt.did(), 0),
_ => false,
},
_ => false,
})
}
}
/// A type the pass cannot see into: a future or a closure (what it yields is
/// in the expression that built it, not in the type).
fn opaque_ty(t: Ty<'_>) -> bool {
t.walk().any(|a| match a.kind() {
GenericArgKind::Type(x) => matches!(x.kind(), ty::Alias(..) | ty::Coroutine(..) | ty::CoroutineClosure(..) | ty::Closure(..)),
_ => false,
})
}
/// Does the type hold a string (`str`, `String`) anywhere — a name, a
/// reference to one, an array / slice / `Option` of names?
fn stringy<'tcx>(tcx: TyCtxt<'tcx>, t: Ty<'tcx>) -> bool {
t.walk().any(|a| match a.kind() {
GenericArgKind::Type(x) => match x.kind() {
ty::Str => true,
ty::Adt(adt, _) => is_lang_crate(tcx, adt.did()) && tcx.item_name(adt.did()).as_str() == "String",
_ => false,
},
_ => false,
})
}
/// What kind of value a walk is after. An aggregate (a tuple, a struct
/// literal, the arguments of a constructor) hands on only its parts of that
/// kind: in `(table, batch)` the batch says nothing about which table.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Want {
/// A table handle / wrapper.
Handle,
/// A table name.
Name,
}
/// The strings of a value of type `&str` / `[&str; N]` / `&[&str]` (nested).
fn valtree_strings<'tcx>(tcx: TyCtxt<'tcx>, t: Ty<'tcx>, v: ty::ValTree<'tcx>, out: &mut Vec<String>) -> bool {
match t.kind() {
ty::Ref(_, inner, _) if inner.is_str() => match (ty::Value { ty: t, valtree: v }).try_to_raw_bytes(tcx) {
Some(b) => match std::str::from_utf8(b) {
Ok(s) => {
out.push(s.to_string());
true
}
Err(_) => false,
},
None => false,
},
ty::Ref(_, inner, _) => valtree_strings(tcx, *inner, v, out),
ty::Array(elem, _) | ty::Slice(elem) => match (ty::Value { ty: t, valtree: v }).try_to_branch() {
Some(items) => items.iter().all(|c| match c.try_to_value() {
Some(val) => valtree_strings(tcx, *elem, val.valtree, out),
None => false,
}),
None => false,
},
_ => false,
}
}
/// Is `t` a shape [`valtree_strings`] reads (`&str`, arrays / slices of it)?
fn string_shape(t: Ty<'_>) -> bool {
match t.kind() {
ty::Str => true,
ty::Ref(_, inner, _) => string_shape(*inner),
ty::Array(elem, _) | ty::Slice(elem) => string_shape(*elem),
_ => false,
}
}
/// The pre-pass over one body: where every local gets its value from.
struct Collect<'tcx> {
tcx: TyCtxt<'tcx>,
root: LocalDefId,
sources: HashMap<HirId, Vec<&'tcx hir::Expr<'tcx>>>,
calls: Vec<&'tcx hir::Expr<'tcx>>,
rets: Vec<&'tcx hir::Expr<'tcx>>,
/// depth of plain closures (a `return` inside one is the closure's)
closures: u32,
}
impl<'tcx> Collect<'tcx> {
fn bind(&mut self, pat: &'tcx hir::Pat<'tcx>, from: &'tcx hir::Expr<'tcx>) {
pat.each_binding(|_, id, _, _| self.sources.entry(id).or_default().push(from));
}
}
impl<'tcx> Visitor<'tcx> for Collect<'tcx> {
type NestedFilter = nested_filter::OnlyBodies;
fn maybe_tcx(&mut self) -> TyCtxt<'tcx> {
self.tcx
}
fn visit_nested_body(&mut self, id: hir::BodyId) {
let owner = self.tcx.hir_body_owner_def_id(id);
if self.tcx.typeck_root_def_id_local(owner) == self.root {
let body = self.tcx.hir_body(id);
self.visit_body(body);
}
}
fn visit_local(&mut self, l: &'tcx hir::LetStmt<'tcx>) {
if let Some(init) = l.init {
self.bind(l.pat, init);
}
intravisit::walk_local(self, l);
}
fn visit_expr(&mut self, e: &'tcx hir::Expr<'tcx>) {
match e.kind {
hir::ExprKind::Call(..) | hir::ExprKind::MethodCall(..) => self.calls.push(e),
hir::ExprKind::Let(l) => self.bind(l.pat, l.init),
hir::ExprKind::Match(scrut, arms, _) => {
for a in arms {
self.bind(a.pat, scrut);
}
}
hir::ExprKind::Assign(lhs, rhs, _) => {
if let hir::ExprKind::Path(hir::QPath::Resolved(None, p)) = lhs.kind {
if let Res::Local(id) = p.res {
self.sources.entry(id).or_default().push(rhs);
}
}
}
hir::ExprKind::Ret(Some(v)) if self.closures == 0 => self.rets.push(v),
hir::ExprKind::Closure(c) if matches!(c.kind, hir::ClosureKind::Closure) => {
self.closures += 1;
intravisit::walk_expr(self, e);
self.closures -= 1;
return;
}
_ => {}
}
intravisit::walk_expr(self, e);
}
}
/// One look at one body.
struct Look<'a, 'tcx> {
tcx: TyCtxt<'tcx>,
t: &'a mut Tables,
typeck: &'tcx ty::TypeckResults<'tcx>,
typing_env: TypingEnv<'tcx>,
params: HashMap<HirId, u32>,
sources: HashMap<HirId, Vec<&'tcx hir::Expr<'tcx>>>,
memo: HashMap<(HirId, Want), Set>,
visiting: HashSet<(HirId, Want)>,
out: BodyOut,
}
fn one(r: TableRef) -> Set {
Rc::new(BTreeSet::from([r]))
}
/// A value that stands for NO table (`None`, an error, a diverging branch).
fn nothing() -> Set {
Rc::new(BTreeSet::new())
}
impl<'a, 'tcx> Look<'a, 'tcx> {
fn ty(&self, e: &hir::Expr<'_>) -> Option<Ty<'tcx>> {
self.typeck.expr_ty_opt(e)
}
/// The type of `e` as the place it is used sees it (after `&` / deref
/// adjustments), falling back to its own type.
fn ty_adjusted(&self, e: &hir::Expr<'_>) -> Option<Ty<'tcx>> {
self.typeck.expr_ty_adjusted_opt(e).or_else(|| self.typeck.expr_ty_opt(e))
}
/// What a walk from a value of this type is after.
fn want(&mut self, t: Option<Ty<'tcx>>) -> Want {
match t {
Some(t) if self.t.handle_ty(self.tcx, t) => Want::Handle,
_ => Want::Name,
}
}
/// Can a part of this type carry what the walk is after?
fn fits(&mut self, e: &hir::Expr<'_>, want: Want) -> bool {
let Some(t) = self.ty(e) else { return true };
if t.is_never() {
return false;
}
match want {
Want::Handle => self.t.handle_ty(self.tcx, t) || opaque_ty(t),
Want::Name => stringy(self.tcx, t) || opaque_ty(t),
}
}
/// The callee of a call expression: as written, as rustc resolves it
/// (a trait method with concrete args → the impl's), and the arguments
/// in parameter order (the receiver first).
fn callee(&self, e: &'tcx hir::Expr<'tcx>) -> Option<(DefId, DefId, Vec<&'tcx hir::Expr<'tcx>>)> {
match e.kind {
hir::ExprKind::Call(f, args) => {
let hir::ExprKind::Path(ref q) = f.kind else { return None };
let Res::Def(DefKind::Fn | DefKind::AssocFn, did) = self.typeck.qpath_res(q, f.hir_id) else { return None };
Some((did, self.resolve(did, f.hir_id), args.iter().collect()))
}
hir::ExprKind::MethodCall(_, recv, args, _) => {
let did = self.typeck.type_dependent_def_id(e.hir_id)?;
let mut all = vec![recv];
all.extend(args.iter());
Some((did, self.resolve(did, e.hir_id), all))
}
_ => None,
}
}
fn resolve(&self, did: DefId, hir_id: HirId) -> DefId {
let tcx = self.tcx;
if tcx.trait_of_assoc(did).is_none() {
return did;
}
let Some(args) = self.typeck.node_args_opt(hir_id) else { return did };
if args.has_non_region_param() || args.has_infer() || args.references_error() || args.has_escaping_bound_vars() {
return did;
}
let args = tcx.erase_and_anonymize_regions(args);
match Instance::try_resolve(tcx, self.typing_env, did, args) {
Ok(Some(inst)) => match inst.def {
ty::InstanceKind::Item(d) => d,
_ => did,
},
_ => did,
}
}
/// A std call that hands its first argument on unchanged.
fn identity(&self, written: DefId) -> bool {
let tcx = self.tcx;
if !is_lang_crate(tcx, written) || tcx.def_kind(written) != DefKind::AssocFn {
return false;
}
let name = tcx.item_name(written);
let parent = tcx.parent(written);
let tr = match tcx.def_kind(parent) {
DefKind::Trait => Some(parent),
DefKind::Impl { of_trait: true } => tcx.impl_opt_trait_id(parent),
_ => None,
};
match tr {
Some(tr) => {
let t = tcx.item_name(tr);
IDENTITY_TRAITS.contains(&t.as_str()) || (t.as_str() == "Iterator" && IDENTITY_ITER.contains(&name.as_str()))
}
None => IDENTITY_INHERENT.contains(&name.as_str()),
}
}
/// The union over the parts that can carry what the walk is after.
fn union(&mut self, parts: impl IntoIterator<Item = &'tcx hir::Expr<'tcx>>, want: Want) -> Set {
let mut out = BTreeSet::new();
for p in parts {
if self.fits(p, want) {
out.extend(self.denote(p, want).iter().cloned());
}
}
Rc::new(out)
}
/// The value of a `const` / `static` path, as table names.
fn constant(&mut self, did: DefId, e: &'tcx hir::Expr<'tcx>) -> Set {
let tcx = self.tcx;
let Some(t) = self.ty(e) else { return unknown() };
if !string_shape(t) {
return unknown();
}
let mut names = Vec::new();
let ok = match tcx.def_kind(did) {
DefKind::Const { .. } | DefKind::AssocConst { .. } => (|| {
// (no recorded args = a plain const: the empty list)
let args = self.typeck.node_args(e.hir_id);
if args.has_non_region_param() || args.has_infer() || args.references_error() {
return false;
}
let args = tcx.erase_and_anonymize_regions(args);
let Ok(Some(instance)) = Instance::try_resolve(tcx, self.typing_env, did, args) else { return false };
match tcx.const_eval_global_id_for_typeck(self.typing_env, GlobalId { instance, promoted: None }, DUMMY_SP) {
Ok(Ok(v)) => valtree_strings(tcx, t, v, &mut names),
_ => false,
}
})(),
DefKind::Static { .. } => match static_str(tcx, did, t) {
Some(s) => {
names.push(s);
true
}
None => false,
},
_ => false,
};
if ok && !names.is_empty() { Rc::new(names.into_iter().map(TableRef::Const).collect()) } else { unknown() }
}
/// Which tables the value of `e` stands for. The empty set = no table
/// at all (`None`, an `Err`, a branch that returns).
fn denote(&mut self, e: &'tcx hir::Expr<'tcx>, want: Want) -> Set {
let key = (e.hir_id, want);
if let Some(s) = self.memo.get(&key) {
return s.clone();
}
if !self.visiting.insert(key) {
// a value defined through itself (`x = f(x)`): nothing new here
return nothing();
}
let s = self.denote_inner(e, want);
self.visiting.remove(&key);
self.memo.insert(key, s.clone());
s
}
fn is_table_ident(&self, t: Option<Ty<'tcx>>) -> bool {
let tcx = self.tcx;
t.map(peel).is_some_and(|t| matches!(t.kind(), ty::Adt(adt, _) if tcx.crate_name(adt.did().krate).as_str() == ANCHOR_CRATE && tcx.item_name(adt.did()).as_str() == "TableIdent"))
}
fn denote_inner(&mut self, e: &'tcx hir::Expr<'tcx>, want: Want) -> Set {
use hir::ExprKind as K;
let tcx = self.tcx;
if self.ty(e).is_some_and(|t| t.is_never()) {
return nothing();
}
match e.kind {
K::Lit(lit) => match lit.node {
rustc_ast::LitKind::Str(s, _) => one(TableRef::Const(s.to_string())),
_ => unknown(),
},
K::Path(ref q) => match self.typeck.qpath_res(q, e.hir_id) {
Res::Local(id) => {
if let Some(p) = self.params.get(&id) {
return one(TableRef::Param(*p));
}
match self.sources.get(&id).cloned() {
// the binding may sit inside a pattern (`(table, batch)`,
// `Some(t)`): its source is the whole value, of which
// only the parts of the binding's kind count
Some(srcs) if !srcs.is_empty() => {
let want = self.want(self.ty(e));
let mut out = BTreeSet::new();
for s in srcs {
out.extend(self.denote(s, want).iter().cloned());
}
Rc::new(out)
}
// a closure parameter, a `for` over a runtime value
_ => unknown(),
}
}
Res::Def(DefKind::Const { .. } | DefKind::AssocConst { .. } | DefKind::Static { .. }, did) => self.constant(did, e),
// `None`, a unit struct: no table
Res::Def(DefKind::Ctor(..), _) => nothing(),
_ => unknown(),
},
K::AddrOf(_, _, x) | K::Unary(hir::UnOp::Deref, x) | K::Cast(x, _) | K::Type(x, _) | K::DropTemps(x) | K::Use(x, _) => self.denote(x, want),
K::Block(b, _) => match b.expr {
Some(x) => self.denote(x, want),
None => nothing(),
},
K::If(_, a, Some(b)) => {
let (a, b) = (self.denote(a, want), self.denote(b, want));
Rc::new(a.union(&b).cloned().collect())
}
K::Match(scrut, arms, src) => match src {
// `x?` / `x.await`: the value of `x`
hir::MatchSource::TryDesugar(_) | hir::MatchSource::AwaitDesugar => match scrut.kind {
K::Call(_, [inner]) => self.denote(inner, want),
_ => self.denote(scrut, want),
},
_ => {
let mut out = BTreeSet::new();
for a in arms {
out.extend(self.denote(a.body, want).iter().cloned());
}
Rc::new(out)
}
},
K::Array(items) | K::Tup(items) => self.union(items.iter(), want),
K::Index(base, _, _) => self.denote(base, want),
K::Field(base, field) => {
let ident_name = self.is_table_ident(self.ty_adjusted(base)) && field.name.as_str() == "name";
let handle = self.ty(e).is_some_and(|ft| self.t.handle_ty(tcx, ft));
if ident_name || handle {
let w = self.want(self.ty_adjusted(base));
self.denote(base, w)
} else {
// a runtime field of something that is no table handle
unknown()
}
}
K::Struct(_, fields, _) => {
let ident = self.is_table_ident(self.ty(e));
let mut out = BTreeSet::new();
for f in fields {
let handle = self.ty(f.expr).is_some_and(|ft| self.t.handle_ty(tcx, ft));
if ident && f.ident.name.as_str() == "name" {
out.extend(self.denote(f.expr, Want::Name).iter().cloned());
} else if handle {
out.extend(self.denote(f.expr, Want::Handle).iter().cloned());
}
}
Rc::new(out)
}
// an `async` block is the future of its tail value
K::Closure(c) if matches!(c.kind, hir::ClosureKind::Coroutine(_)) => {
let body = tcx.hir_body(c.body);
let w = self.want(self.ty(body.value));
self.denote(body.value, w)
}
K::Call(f, args) => {
// `Some(x)` / `Ok(x)`, a tuple struct around a handle
if let hir::ExprKind::Path(ref q) = f.kind {
if let Res::Def(DefKind::Ctor(..), _) = self.typeck.qpath_res(q, f.hir_id) {
return self.union(args.iter(), want);
}
}
self.denote_call(e)
}
K::MethodCall(..) => self.denote_call(e),
_ => unknown(),
}
}
fn denote_call(&mut self, e: &'tcx hir::Expr<'tcx>) -> Set {
let tcx = self.tcx;
let Some((written, resolved, args)) = self.callee(e) else { return unknown() };
if let Some(sum) = self.t.summary(tcx, written, resolved) {
if sum.ret.is_empty() {
return unknown();
}
let mut out = BTreeSet::new();
for r in &sum.ret {
match r {
TableRef::Param(i) => match args.get(*i as usize) {
Some(a) => {
let w = self.want(self.ty_adjusted(a));
out.extend(self.denote(a, w).iter().cloned());
}
None => {
out.insert(TableRef::Unknown);
}
},
other => {
out.insert(other.clone());
}
}
}
return Rc::new(out);
}
if self.identity(written) {
return match args.first() {
Some(a) => {
let w = self.want(self.ty_adjusted(a));
self.denote(a, w)
}
None => unknown(),
};
}
let Some(rt) = self.ty(e) else { return unknown() };
let handle = self.t.handle_ty(tcx, rt);
// a local fn nobody looked at yet whose result is a name or a handle:
// look at it, and come back when its summary is known
if let Some(l) = resolved.as_local() {
if (handle || stringy(tcx, rt)) && !self.t.local.contains_key(&resolved) && tcx.hir_maybe_body_owned_by(l).is_some() {
self.out.demanded.push(l);
}
}
if handle || opaque_ty(rt) {
// a handle goes in, a handle comes out (`ident.clone()`,
// `.context("…")`, `block_on(fut)`, a builder step)
let mut out = BTreeSet::new();
let mut any = false;
for a in args.iter().copied() {
let Some(at) = self.ty_adjusted(a) else { continue };
if self.t.handle_ty(tcx, at) || opaque_ty(at) {
any = true;
out.extend(self.denote(a, Want::Handle).iter().cloned());
}
}
if any {
return Rc::new(out);
}
}
unknown()
}
/// A call whose callee does something with a table argument: a site of
/// this body, or — when the argument is this fn's own parameter — a fact
/// about this fn for ITS callers.
fn apply(&mut self, e: &'tcx hir::Expr<'tcx>) {
let tcx = self.tcx;
let Some((written, resolved, args)) = self.callee(e) else { return };
let Some(sum) = self.t.summary(tcx, written, resolved) else { return };
for (i, bits) in &sum.effects {
let Some(arg) = args.get(*i as usize) else { continue };
let w = self.want(self.ty_adjusted(arg));
let what = self.denote(arg, w);
if what.is_empty() {
// nothing the walk understands stands behind the argument:
// a site all the same, with no table
self.out.sites.push(Site { table: None, bits: *bits, span: e.span });
}
for r in what.iter() {
match r {
TableRef::Param(p) => *self.out.summary.effects.entry(*p).or_insert(0) |= bits,
TableRef::Const(name) => self.out.sites.push(Site { table: Some(name.clone()), bits: *bits, span: e.span }),
TableRef::Unknown => self.out.sites.push(Site { table: None, bits: *bits, span: e.span }),
}
}
}
}
}
/// The value of a `static NAME: &str`.
fn static_str<'tcx>(tcx: TyCtxt<'tcx>, did: DefId, t: Ty<'tcx>) -> Option<String> {
if !matches!(t.kind(), ty::Ref(_, inner, _) if inner.is_str()) && !t.is_str() {
return None;
}
let alloc = tcx.eval_static_initializer(did).ok()?;
let a = alloc.inner();
let ptr = tcx.data_layout.pointer_size().bytes_usize();
if a.len() != 2 * ptr || ptr != 8 {
return None;
}
let raw = a.inspect_with_uninit_and_ptr_outside_interpreter(0..2 * ptr);
let offset = u64::from_le_bytes(raw[..8].try_into().ok()?) as usize;
let len = u64::from_le_bytes(raw[8..16].try_into().ok()?) as usize;
let (_, prov) = a.provenance().ptrs().iter().next()?;
let rustc_middle::mir::interpret::GlobalAlloc::Memory(target) = tcx.global_alloc(prov.alloc_id()) else { return None };
let target = target.inner();
if offset.checked_add(len)? > target.len() {
return None;
}
let bytes = target.inspect_with_uninit_and_ptr_outside_interpreter(offset..offset + len);
std::str::from_utf8(bytes).ok().map(str::to_string)
}
impl<'tcx> Walker<'tcx> {
/// Before the bodies are walked: read what the loaded crates say, find
/// this crate's own annotations, and decide whether the pass runs at all.
pub(super) fn init_tables(&mut self) {
let t0 = Instant::now();
let tcx = self.tcx;
self.load_table_sidecars();
// this crate's annotated items: a summary of their own, with or
// without a body
let ids: Vec<LocalDefId> = tcx.iter_local_def_id().filter(|d| matches!(tcx.def_kind(*d), DefKind::Fn | DefKind::AssocFn)).collect();
for d in ids {
if let Some(s) = self.tables.annotated(tcx, d.to_def_id()) {
self.tables.local.entry(d.to_def_id()).or_default().absorb(&s);
}
}
self.tables.enabled = anchor_in_reach(tcx) || !self.tables.local.is_empty() || !self.tables.ext_fns.is_empty() || !self.tables.ext_traits.is_empty();
self.tables.ms = t0.elapsed().as_millis();
}
/// Read the table summaries of every crate this compile loaded.
fn load_table_sidecars(&mut self) {
let tcx = self.tcx;
let crates = tcx.crates(());
self.tables.sidecars.1 = crates.len();
let dir = self.index_dir.clone();
for &cnum in crates {
let src = tcx.used_crate_source(cnum);
let paths: Vec<PathBuf> = src.paths().cloned().collect();
if paths.iter().any(|p| p.starts_with(&self.sysroot)) {
// the toolchain's own crates: compiled by nobody here
continue;
}
let sc = dir.as_ref().and_then(|d| paths.iter().find_map(|p| artifact_key_of(p).and_then(|k| read_table_sidecar(d, &k))));
let Some(sc) = sc else {
self.tables.stale.push(tcx.crate_name(cnum).to_string());
continue;
};
if sc.error.is_some() {
self.tables.stale.push(format!("{} (the pass failed there)", tcx.crate_name(cnum)));
continue;
}
self.tables.sidecars.0 += 1;
for (k, s) in sc.fns {
self.tables.ext_fns.entry(k).or_default().absorb(&s);
}
for (k, s) in sc.trait_methods {
self.tables.ext_traits.entry(k).or_default().absorb(&s);
}
}
self.tables.stale.sort();
}
/// The pass failed on this crate: say so where its dependents read.
pub(super) fn table_pass_failed(&self, why: &str) {
if let (Some(dir), Some(key)) = (self.index_dir.clone(), self.artifact_key.clone()) {
let _ = write_table_sidecar(&dir, &key, &TableSidecar { v: TABLE_PASS, error: Some(why.to_string()), ..Default::default() });
}
}
/// One look at the body of `owner` with the summaries known so far.
fn look(&mut self, owner: LocalDefId) -> Option<BodyOut> {
let tcx = self.tcx;
let body = tcx.hir_maybe_body_owned_by(owner)?;
let mut c = Collect { tcx, root: owner, sources: HashMap::new(), calls: Vec::new(), rets: Vec::new(), closures: 0 };
c.visit_body(body);
let mut params = HashMap::new();
for (i, p) in body.params.iter().enumerate() {
p.pat.each_binding(|_, id, _, _| {
params.insert(id, i as u32);
});
}
let mut l = Look {
tcx,
t: &mut self.tables,
typeck: tcx.typeck(owner),
typing_env: TypingEnv::post_analysis(tcx, owner.to_def_id()),
params,
sources: c.sources,
memo: HashMap::new(),
visiting: HashSet::new(),
out: BodyOut::default(),
};
for call in &c.calls {
l.apply(call);
}
// what the fn hands back: its tail value and every `return`
if matches!(tcx.def_kind(owner), DefKind::Fn | DefKind::AssocFn) {
let mut ret = BTreeSet::new();
for v in std::iter::once(body.value).chain(c.rets.iter().copied()) {
let w = l.want(l.ty(v));
ret.extend(l.denote(v, w).iter().filter(|r| **r != TableRef::Unknown).cloned());
}
l.out.summary.ret = ret;
}
l.out.sites.sort_by(|a, b| (&a.table, a.bits, a.span.lo(), a.span.hi()).cmp(&(&b.table, b.bits, b.span.lo(), b.span.hi())));
l.out.sites.dedup();
Some(l.out)
}
/// The table pass: summaries to a fixpoint, then the edges.
pub(super) fn walk_tables(&mut self, emit: bool) {
if !self.tables.enabled {
return;
}
let t0 = Instant::now();
let tcx = self.tcx;
// start from the bodies that call something already summarised
let callees: Vec<DefId> = self.tables.callers.keys().copied().collect();
let mut queue: VecDeque<LocalDefId> = VecDeque::new();
let mut queued: HashSet<LocalDefId> = HashSet::new();
for did in callees {
if self.tables.summary(tcx, did, did).is_some() {
for o in self.tables.callers.get(&did).cloned().unwrap_or_default() {
if queued.insert(o) {
queue.push_back(o);
}
}
}
}
let mut seen: HashSet<LocalDefId> = HashSet::new();
// a runaway guard, far above any real fixpoint (each look can only
// ADD to a summary: at most params × 2 bits + returns per fn)
let mut budget = 200_000usize;
while let Some(owner) = queue.pop_front() {
queued.remove(&owner);
if budget == 0 {
break;
}
budget -= 1;
self.tables.visits += 1;
seen.insert(owner);
let Some(out) = self.look(owner) else { continue };
for d in out.demanded {
if !seen.contains(&d) && queued.insert(d) {
queue.push_back(d);
}
}
if out.sites.is_empty() {
self.tables.sites.remove(&owner);
} else {
self.tables.sites.insert(owner, out.sites);
}
let did = owner.to_def_id();
let mut wake: Vec<DefId> = Vec::new();
let changed = {
let cur = self.tables.local.entry(did).or_default();
// a fn looked at and found empty stays in the map: "known, nothing"
cur.absorb(&out.summary)
};
if changed {
wake.push(did);
if let Some(tm) = tcx.trait_item_of(did) {
if self.tables.trait_local.entry(tm).or_default().absorb(&out.summary) {
wake.push(tm);
}
}
}
for w in wake {
for o in self.tables.callers.get(&w).cloned().unwrap_or_default() {
if queued.insert(o) {
queue.push_back(o);
}
}
}
}
self.tables.bodies = seen.len();
// ---- the sidecar: what a dependent crate needs to know
let mut sc = TableSidecar { v: TABLE_PASS, ..Default::default() };
for (did, s) in &self.tables.local {
if !s.is_empty() {
sc.fns.insert(hash_key(tcx, *did), s.clone());
}
}
for (did, s) in &self.tables.trait_local {
if !s.is_empty() {
sc.trait_methods.insert(hash_key(tcx, *did), s.clone());
}
}
self.tables.n_summaries = sc.fns.len();
if let (Some(dir), Some(key)) = (self.index_dir.clone(), self.artifact_key.clone()) {
let _ = write_table_sidecar(&dir, &key, &sc);
}
if emit {
self.emit_table_edges();
}
self.tables.ms += t0.elapsed().as_millis();
}
fn emit_table_edges(&mut self) {
let mut sites: Vec<(LocalDefId, Vec<Site>)> = std::mem::take(&mut self.tables.sites).into_iter().collect();
sites.sort_by_key(|(o, _)| o.local_def_index.as_u32());
for (owner, list) in sites {
let Some(from) = self.node_or_ancestor(owner.to_def_id()) else { continue };
let fm = self.moniker(from);
for s in list {
let name = s.table.as_deref().unwrap_or(TABLE_UNRESOLVED);
let tm = moniker::table(name);
self.table_node(&tm, name);
let (file, line, _) = self.file_lines(s.span, true);
self.push_edge(fm.clone(), tm.clone(), EdgeKind::TouchesTable, file, line);
let idx = self.edge_index[&(fm.clone(), tm, EdgeKind::TouchesTable)];
let bits = self.edges[idx].access.map_or(0, Access::bits) | s.bits;
self.edges[idx].access = Access::from_bits(bits);
self.tables.n_sites += 1;
match s.table {
Some(n) => {
self.tables.names.insert(n);
}
None => self.tables.n_unresolved += 1,
}
}
}
}
/// The table's node: the same row from every crate of every repo.
fn table_node(&mut self, id: &str, name: &str) {
if self.node_ids.contains(id) {
return;
}
let mut row = NodeRow::new(id, kind::TABLE, Level::Item, name, moniker::TABLE_PACKAGE, moniker::TABLE_VERSION, Origin::Local);
row.provenance = Provenance::SourceOnly;
row.valid_from_sha = self.local.sha.clone();
self.push_node(row);
}
}