cache-lens 0.1.0

A static analyzer that detects cache-unfriendly Array-of-Structures (AoS) usage in Rust and suggests Structure-of-Arrays (SoA) refactors.
use std::collections::{HashMap, HashSet};
use syn::spanned::Spanned;
use syn::visit::{self, Visit};
use syn::{
    Expr, ExprField, ExprForLoop, ExprMethodCall, ExprPath, ExprWhile, FnArg, ImplItemFn, ItemFn,
    ItemImpl, Local, Member, Pat, PatIdent, Signature,
};

use crate::config::Config;
use crate::model::{FieldAccessStat, FieldReport, Finding, Severity, StructInfo};
use crate::passes::field_access::{FieldAccessCollector, IndexedFieldAccessCollector};
use crate::passes::scope::Scopes;
use crate::suggestion::{generate_soa_derive_suggestion, generate_soa_suggestion};
use crate::utils::{
    LoopBinding, classify_loop_pattern, estimate_type_size, extract_element_struct_name,
    is_target_path, path_to_string, simple_type_name, type_to_string, unwrap_expr, unwrap_pat,
};

const ELEMENT_CLOSURE_METHODS: &[&str] =
    &["for_each", "map", "filter", "any", "all", "find", "inspect"];

pub struct CacheLensVisitor<'a> {
    structs: &'a HashMap<String, StructInfo>,
    config: &'a Config,
    file_display: String,
    scopes: Scopes,
    self_type_stack: Vec<Option<String>>,
    pub findings: Vec<Finding>,
}

impl<'a> CacheLensVisitor<'a> {
    pub fn new(
        structs: &'a HashMap<String, StructInfo>,
        config: &'a Config,
        file_display: String,
    ) -> Self {
        Self {
            structs,
            config,
            file_display,
            scopes: Scopes::new(),
            self_type_stack: vec![None],
            findings: Vec::new(),
        }
    }

    fn current_self_type(&self) -> Option<&str> {
        self.self_type_stack.last().and_then(|o| o.as_deref())
    }

    fn register_fn_params(&mut self, sig: &Signature) {
        for input in &sig.inputs {
            if let FnArg::Typed(pt) = input
                && let Pat::Ident(PatIdent { ident, .. }) = unwrap_pat(&pt.pat)
                && let Some(struct_name) = extract_element_struct_name(&pt.ty)
                && self.structs.contains_key(&struct_name)
            {
                self.scopes.insert(ident.to_string(), struct_name);
            }
        }
    }

    fn resolve_collection_expr(&self, expr: &Expr) -> Option<(String, String)> {
        match unwrap_expr(expr) {
            Expr::MethodCall(mc) => {
                let name = mc.method.to_string();
                if matches!(name.as_str(), "iter" | "iter_mut" | "into_iter") {
                    self.resolve_collection_expr(&mc.receiver)
                } else {
                    None
                }
            }
            Expr::Path(ExprPath {
                path, qself: None, ..
            }) => {
                let short = path.segments.last()?.ident.to_string();
                self.scopes
                    .lookup(&short)
                    .map(|s| (s.to_string(), path_to_string(path)))
            }
            Expr::Field(ExprField {
                base,
                member: Member::Named(field_ident),
                ..
            }) => {
                if !is_target_path(base, "self") {
                    return None;
                }
                let self_ty = self.current_self_type()?;
                let info = self.structs.get(self_ty)?;
                let field = info.fields.iter().find(|f| *field_ident == f.name)?;
                let struct_name = extract_element_struct_name(&field.ty)?;
                Some((struct_name, format!("self.{field_ident}")))
            }
            _ => None,
        }
    }

    fn analyze_for_loop(&mut self, node: &ExprForLoop) {
        let Some((struct_name, collection_display)) = self.resolve_collection_expr(&node.expr)
        else {
            return;
        };
        if !self.structs.contains_key(&struct_name) {
            return;
        }
        let line = node.span().start().line;

        match classify_loop_pattern(&node.pat) {
            LoopBinding::Ident(var) => {
                let mut collector = FieldAccessCollector::new(&var);
                collector.visit_block(&node.body);
                self.finalize_finding(
                    line,
                    &struct_name,
                    &collection_display,
                    &var,
                    "for",
                    collector.accesses,
                );
            }
            LoopBinding::Destructured(fields) => {
                let accesses = fields
                    .into_iter()
                    .map(|f| {
                        (
                            f,
                            FieldAccessStat {
                                reads: 1,
                                writes: 0,
                            },
                        )
                    })
                    .collect();
                self.finalize_finding(
                    line,
                    &struct_name,
                    &collection_display,
                    "<destructured>",
                    "for (destructured)",
                    accesses,
                );
            }
            LoopBinding::Unsupported => {}
        }
    }

    fn analyze_while_loop(&mut self, node: &ExprWhile) {
        let known = self.scopes.snapshot();
        if known.is_empty() {
            return;
        }
        let mut collector = IndexedFieldAccessCollector::new(&known);
        collector.visit_block(&node.body);
        let line = node.span().start().line;
        for (coll_var, field_map) in collector.data {
            let Some(struct_name) = known.get(&coll_var).cloned() else {
                continue;
            };
            let display = format!("{coll_var}[i]");
            self.finalize_finding(
                line,
                &struct_name,
                &coll_var,
                &display,
                "while (manual index)",
                field_map,
            );
        }
    }

    fn analyze_method_chain(&mut self, node: &ExprMethodCall) {
        let method_name = node.method.to_string();
        if !ELEMENT_CLOSURE_METHODS.contains(&method_name.as_str()) {
            return;
        }
        let Some(Expr::Closure(closure)) = node.args.first() else {
            return;
        };
        if closure.inputs.len() != 1 {
            return;
        }
        let Some((struct_name, collection_display)) = self.resolve_collection_expr(&node.receiver)
        else {
            return;
        };
        if !self.structs.contains_key(&struct_name) {
            return;
        }
        let line = node.method.span().start().line;
        let loop_kind = format!("{collection_display}.{method_name}(closure)");
        let Some(param_pat) = closure.inputs.first() else {
            return;
        };

        match classify_loop_pattern(param_pat) {
            LoopBinding::Ident(var) => {
                let mut collector = FieldAccessCollector::new(&var);
                collector.visit_expr(&closure.body);
                self.finalize_finding(
                    line,
                    &struct_name,
                    &collection_display,
                    &var,
                    &loop_kind,
                    collector.accesses,
                );
            }
            LoopBinding::Destructured(fields) => {
                let accesses = fields
                    .into_iter()
                    .map(|f| {
                        (
                            f,
                            FieldAccessStat {
                                reads: 1,
                                writes: 0,
                            },
                        )
                    })
                    .collect();
                self.finalize_finding(
                    line,
                    &struct_name,
                    &collection_display,
                    "<destructured>",
                    &loop_kind,
                    accesses,
                );
            }
            LoopBinding::Unsupported => {}
        }
    }

    fn finalize_finding(
        &mut self,
        line: usize,
        struct_name: &str,
        collection_display: &str,
        loop_var: &str,
        loop_kind: &str,
        accesses: HashMap<String, FieldAccessStat>,
    ) {
        let Some(info) = self.structs.get(struct_name) else {
            return;
        };
        if info.fields.len() < self.config.min_fields {
            return;
        }
        if accesses.is_empty() {
            return;
        }
        let total = info.fields.len();
        let accessed = accesses.len();
        if accessed >= total {
            return;
        }
        let ratio = accessed as f64 / total as f64;
        if ratio > self.config.max_access_ratio {
            return;
        }

        let mut hot = Vec::new();
        let mut cold = Vec::new();
        let mut hot_bytes = 0usize;
        let mut total_bytes = 0usize;
        let mut hot_names: HashSet<String> = HashSet::new();

        for f in &info.fields {
            let size = estimate_type_size(&f.ty);
            total_bytes += size;
            if let Some(stat) = accesses.get(&f.name) {
                hot_bytes += size;
                hot_names.insert(f.name.clone());
                hot.push(FieldReport {
                    name: f.name.clone(),
                    ty: type_to_string(&f.ty),
                    reads: stat.reads,
                    writes: stat.writes,
                    approx_size_bytes: size,
                });
            } else {
                cold.push(FieldReport {
                    name: f.name.clone(),
                    ty: type_to_string(&f.ty),
                    reads: 0,
                    writes: 0,
                    approx_size_bytes: size,
                });
            }
        }

        let byte_ratio = if total_bytes > 0 {
            hot_bytes as f64 / total_bytes as f64
        } else {
            ratio
        };
        let severity = if ratio <= 0.3 || byte_ratio <= 0.3 {
            Severity::High
        } else {
            Severity::Medium
        };
        let soa_suggestion = generate_soa_suggestion(info, &hot_names);
        let soa_derive_suggestion = generate_soa_derive_suggestion(info);

        self.findings.push(Finding {
            file: self.file_display.clone(),
            line,
            struct_name: struct_name.to_string(),
            struct_def_line: info.def_line,
            total_fields: total,
            collection_expr: collection_display.to_string(),
            loop_var: loop_var.to_string(),
            loop_kind: loop_kind.to_string(),
            hot_fields: hot,
            cold_fields: cold,
            access_ratio: ratio,
            byte_ratio,
            severity,
            soa_suggestion,
            soa_derive_suggestion,
        });
    }
}

impl<'a, 'ast> Visit<'ast> for CacheLensVisitor<'a> {
    fn visit_item_fn(&mut self, node: &'ast ItemFn) {
        self.scopes.push();
        self.register_fn_params(&node.sig);
        self.visit_block(&node.block);
        self.scopes.pop();
    }

    fn visit_impl_item_fn(&mut self, node: &'ast ImplItemFn) {
        self.scopes.push();
        self.register_fn_params(&node.sig);
        self.visit_block(&node.block);
        self.scopes.pop();
    }

    fn visit_item_impl(&mut self, node: &'ast ItemImpl) {
        let self_name = simple_type_name(&node.self_ty);
        self.self_type_stack.push(self_name);
        visit::visit_item_impl(self, node);
        self.self_type_stack.pop();
    }

    fn visit_local(&mut self, node: &'ast Local) {
        if let Pat::Type(pt) = &node.pat
            && let Pat::Ident(PatIdent { ident, .. }) = unwrap_pat(&pt.pat)
            && let Some(struct_name) = extract_element_struct_name(&pt.ty)
            && self.structs.contains_key(&struct_name)
        {
            self.scopes.insert(ident.to_string(), struct_name);
        }
        visit::visit_local(self, node);
    }

    fn visit_expr_for_loop(&mut self, node: &'ast ExprForLoop) {
        self.analyze_for_loop(node);
        visit::visit_expr_for_loop(self, node);
    }

    fn visit_expr_while(&mut self, node: &'ast ExprWhile) {
        self.analyze_while_loop(node);
        visit::visit_expr_while(self, node);
    }

    fn visit_expr_method_call(&mut self, node: &'ast ExprMethodCall) {
        self.analyze_method_chain(node);
        visit::visit_expr_method_call(self, node);
    }
}