use crate::parser::{ParsedWasm, WasmItemKind};
use petgraph::algo::dominators;
use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::EdgeRef;
use std::collections::{HashMap, HashSet, VecDeque};
#[derive(Debug, Clone, serde::Serialize)]
pub struct SizeInfo {
pub shallow_size: u64,
pub retained_size: u64,
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct ItemInfo {
pub name: String,
pub raw_name: String,
pub kind: WasmItemKind,
pub shallow_size: u64,
pub retained_size: u64,
#[serde(skip_serializing_if = "Option::is_none")]
pub func_index: Option<u32>,
}
#[derive(Debug, serde::Serialize)]
pub struct WasmAnalysis {
pub total_size: u64,
pub items: Vec<ItemInfo>,
pub section_sizes: HashMap<String, u64>,
pub is_component: bool,
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct RetentionPath {
pub target: String,
pub target_kind: WasmItemKind,
pub path: Vec<RetentionStep>,
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct RetentionStep {
pub name: String,
pub kind: WasmItemKind,
pub relationship: String,
}
pub struct RetainedSizeAnalyzer {
graph: DiGraph<u32, ()>,
func_to_node: HashMap<u32, NodeIndex>,
node_to_func: HashMap<NodeIndex, u32>,
func_sizes: HashMap<u32, u64>,
roots: HashSet<u32>,
parsed: ParsedWasm,
}
impl RetainedSizeAnalyzer {
pub fn new(parsed: ParsedWasm) -> Self {
let mut graph = DiGraph::new();
let mut func_to_node = HashMap::new();
let mut node_to_func = HashMap::new();
let mut func_sizes = HashMap::new();
for item in &parsed.items {
if item.kind == WasmItemKind::Function {
if let Some(func_idx) = item.func_index {
let node = graph.add_node(func_idx);
func_to_node.insert(func_idx, node);
node_to_func.insert(node, func_idx);
func_sizes.insert(func_idx, item.size);
}
}
}
for (caller, callees) in &parsed.call_graph {
if let Some(&caller_node) = func_to_node.get(caller) {
for callee in callees {
if let Some(&callee_node) = func_to_node.get(callee) {
graph.add_edge(caller_node, callee_node, ());
}
}
}
}
let mut roots = HashSet::new();
for item in &parsed.items {
if item.kind == WasmItemKind::Export && item.name.contains("func") {
for func_item in &parsed.items {
if func_item.kind == WasmItemKind::Function {
if let Some(func_idx) = func_item.func_index {
if func_idx >= parsed.num_imported_funcs {
roots.insert(func_idx);
}
}
}
}
}
}
if roots.is_empty() {
for item in &parsed.items {
if item.kind == WasmItemKind::Function {
if let Some(func_idx) = item.func_index {
roots.insert(func_idx);
}
}
}
}
Self {
graph,
func_to_node,
node_to_func,
func_sizes,
roots,
parsed,
}
}
pub fn retained_size(&self, func_idx: u32) -> u64 {
let Some(&node) = self.func_to_node.get(&func_idx) else {
return 0;
};
let mut reachable = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(node);
reachable.insert(node);
while let Some(current) = queue.pop_front() {
for edge in self.graph.edges(current) {
let target = edge.target();
if !reachable.contains(&target) {
reachable.insert(target);
queue.push_back(target);
}
}
}
let mut total = 0u64;
for &reached_node in &reachable {
if let Some(&func_idx) = self.node_to_func.get(&reached_node) {
total += self.func_sizes.get(&func_idx).copied().unwrap_or(0);
}
}
total
}
pub fn compute_dominated_sizes(&self) -> HashMap<u32, u64> {
let mut dominated_sizes = HashMap::new();
for &root_func in &self.roots {
if let Some(&root_node) = self.func_to_node.get(&root_func) {
let doms = dominators::simple_fast(&self.graph, root_node);
let mut dominator_counts: HashMap<NodeIndex, HashSet<NodeIndex>> = HashMap::new();
for node in self.graph.node_indices() {
let mut current = node;
while let Some(idom) = doms.immediate_dominator(current) {
dominator_counts.entry(idom).or_default().insert(node);
current = idom;
}
}
for (dominator, dominated) in dominator_counts {
if let Some(&func_idx) = self.node_to_func.get(&dominator) {
let size: u64 = dominated
.iter()
.filter_map(|n| self.node_to_func.get(n))
.filter_map(|f| self.func_sizes.get(f))
.sum();
*dominated_sizes.entry(func_idx).or_insert(0) += size;
}
}
}
}
for (&func_idx, &self_size) in &self.func_sizes {
*dominated_sizes.entry(func_idx).or_insert(0) += self_size;
}
dominated_sizes
}
pub fn find_retention_paths(&self, name: &str, max_depth: usize) -> Vec<RetentionPath> {
let mut paths = Vec::new();
let matching_funcs: Vec<_> = self
.parsed
.items
.iter()
.filter(|item| {
item.kind == WasmItemKind::Function
&& (item.name.contains(name) || item.raw_name.contains(name))
})
.collect();
for func in matching_funcs {
let Some(func_idx) = func.func_index else {
continue;
};
let Some(&target_node) = self.func_to_node.get(&func_idx) else {
continue;
};
let reverse_paths = self.find_paths_to_roots(target_node, max_depth);
for path in reverse_paths {
let steps: Vec<RetentionStep> = path
.iter()
.map(|&node| {
let func_idx = self.node_to_func.get(&node).copied().unwrap_or(0);
let name = self
.parsed
.func_names
.get(&func_idx)
.cloned()
.unwrap_or_else(|| format!("func[{}]", func_idx));
RetentionStep {
name: rustc_demangle::demangle(&name).to_string(),
kind: WasmItemKind::Function,
relationship: "calls".to_string(),
}
})
.collect();
paths.push(RetentionPath {
target: func.name.clone(),
target_kind: func.kind,
path: steps,
});
}
}
paths
}
fn find_paths_to_roots(&self, target: NodeIndex, max_depth: usize) -> Vec<Vec<NodeIndex>> {
let mut all_paths = Vec::new();
let mut queue: VecDeque<(NodeIndex, Vec<NodeIndex>)> = VecDeque::new();
queue.push_back((target, vec![target]));
while let Some((current, path)) = queue.pop_front() {
if path.len() > max_depth {
continue;
}
if let Some(&func_idx) = self.node_to_func.get(¤t) {
if self.roots.contains(&func_idx) && path.len() > 1 {
let mut reversed = path.clone();
reversed.reverse();
all_paths.push(reversed);
continue;
}
}
for edge in self
.graph
.edges_directed(current, petgraph::Direction::Incoming)
{
let source = edge.source();
if !path.contains(&source) {
let mut new_path = path.clone();
new_path.push(source);
queue.push_back((source, new_path));
}
}
}
all_paths
}
pub fn analyze(&self, compute_retained: bool) -> WasmAnalysis {
let dominated_sizes = if compute_retained {
self.compute_dominated_sizes()
} else {
HashMap::new()
};
let items: Vec<ItemInfo> = self
.parsed
.items
.iter()
.map(|item| {
let retained_size = if compute_retained {
item.func_index
.and_then(|idx| dominated_sizes.get(&idx))
.copied()
.unwrap_or(item.size)
} else {
item.size
};
ItemInfo {
name: item.name.clone(),
raw_name: item.raw_name.clone(),
kind: item.kind,
shallow_size: item.size,
retained_size,
func_index: item.func_index,
}
})
.collect();
WasmAnalysis {
total_size: self.parsed.total_size,
items,
section_sizes: self.parsed.section_sizes.clone(),
is_component: self.parsed.is_component,
}
}
pub fn parsed(&self) -> &ParsedWasm {
&self.parsed
}
}
#[derive(Debug, serde::Serialize)]
pub struct DiffResult {
pub old_total: u64,
pub new_total: u64,
pub size_delta: i64,
pub items: Vec<DiffItem>,
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct DiffItem {
pub name: String,
pub kind: WasmItemKind,
pub old_size: u64,
pub new_size: u64,
pub delta: i64,
pub status: DiffStatus,
}
#[derive(Debug, Clone, Copy, serde::Serialize)]
#[serde(rename_all = "snake_case")]
pub enum DiffStatus {
Added,
Removed,
Changed,
Unchanged,
}
impl std::fmt::Display for DiffStatus {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
DiffStatus::Added => write!(f, "added"),
DiffStatus::Removed => write!(f, "removed"),
DiffStatus::Changed => write!(f, "changed"),
DiffStatus::Unchanged => write!(f, "unchanged"),
}
}
}
pub fn compute_diff(old: &WasmAnalysis, new: &WasmAnalysis) -> DiffResult {
let mut old_items: HashMap<(&str, WasmItemKind), u64> = HashMap::new();
let mut new_items: HashMap<(&str, WasmItemKind), u64> = HashMap::new();
for item in &old.items {
old_items.insert((&item.name, item.kind), item.shallow_size);
}
for item in &new.items {
new_items.insert((&item.name, item.kind), item.shallow_size);
}
let mut diff_items = Vec::new();
for item in &old.items {
let old_size = item.shallow_size;
let key = (&item.name as &str, item.kind);
let new_size = new_items.get(&key).copied();
let (new_size, status) = match new_size {
Some(ns) if ns == old_size => (ns, DiffStatus::Unchanged),
Some(ns) => (ns, DiffStatus::Changed),
None => (0, DiffStatus::Removed),
};
let delta = new_size as i64 - old_size as i64;
diff_items.push(DiffItem {
name: item.name.clone(),
kind: item.kind,
old_size,
new_size,
delta,
status,
});
}
for item in &new.items {
let key = (&item.name as &str, item.kind);
if !old_items.contains_key(&key) {
diff_items.push(DiffItem {
name: item.name.clone(),
kind: item.kind,
old_size: 0,
new_size: item.shallow_size,
delta: item.shallow_size as i64,
status: DiffStatus::Added,
});
}
}
diff_items.sort_by_key(|b| std::cmp::Reverse(b.delta.abs()));
DiffResult {
old_total: old.total_size,
new_total: new.total_size,
size_delta: new.total_size as i64 - old.total_size as i64,
items: diff_items,
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_diff_status_display() {
assert_eq!(format!("{}", DiffStatus::Added), "added");
assert_eq!(format!("{}", DiffStatus::Removed), "removed");
assert_eq!(format!("{}", DiffStatus::Changed), "changed");
}
}