layout_audit/analysis/
optimize.rs

1//! Field reordering optimization for struct layouts.
2
3use crate::types::{MemberLayout, StructLayout};
4use serde::Serialize;
5use std::collections::HashSet;
6
7/// Result of optimizing a struct layout.
8#[derive(Debug, Clone, Serialize)]
9pub struct OptimizedLayout {
10    pub name: String,
11    pub original_size: u64,
12    pub optimized_size: u64,
13    pub savings_bytes: u64,
14    pub savings_percent: f64,
15    pub struct_alignment: u64,
16    pub original_members: Vec<OptimizedMember>,
17    pub optimized_members: Vec<OptimizedMember>,
18    /// Members that could not be optimized (missing size/offset).
19    #[serde(skip_serializing_if = "Vec::is_empty")]
20    pub skipped_members: Vec<String>,
21    /// True if layout contains bitfields that were kept together.
22    pub has_bitfields: bool,
23}
24
25/// Member with computed offset and alignment.
26#[derive(Debug, Clone, Serialize)]
27pub struct OptimizedMember {
28    pub name: String,
29    pub type_name: String,
30    pub offset: u64,
31    pub size: u64,
32    pub alignment: u64,
33    #[serde(skip_serializing_if = "Option::is_none")]
34    pub bit_offset: Option<u64>,
35    #[serde(skip_serializing_if = "Option::is_none")]
36    pub bit_size: Option<u64>,
37}
38
39/// Infer alignment from size using standard C ABI rules.
40/// Returns alignment as power of 2, capped at max_align.
41pub fn infer_alignment(size: u64, max_align: u64) -> u64 {
42    if size == 0 {
43        return 1;
44    }
45    // For primitives: alignment = min(size rounded to power of 2, max_align)
46    let natural_align = size.next_power_of_two();
47    natural_align.min(max_align).max(1)
48}
49
50/// Align value up to alignment boundary.
51fn align_up(value: u64, alignment: u64) -> u64 {
52    if alignment == 0 {
53        return value;
54    }
55    let mask = alignment - 1;
56    (value + mask) & !mask
57}
58
59/// A sortable unit for optimization - either a single member or a bitfield group.
60#[derive(Clone)]
61struct SortableUnit {
62    members: Vec<OptimizedMember>,
63    total_size: u64,
64    alignment: u64,
65}
66
67/// Group bitfield members that share storage units.
68/// Returns indices of members belonging to each bitfield group.
69fn find_bitfield_groups(members: &[MemberLayout]) -> Vec<Vec<usize>> {
70    let mut groups: Vec<Vec<usize>> = Vec::new();
71    let mut current_group: Vec<usize> = Vec::new();
72    let mut current_offset: Option<u64> = None;
73
74    for (idx, member) in members.iter().enumerate() {
75        if member.bit_size.is_some() {
76            let base_offset = member.offset;
77            if current_offset == base_offset && !current_group.is_empty() {
78                // Same storage unit
79                current_group.push(idx);
80            } else {
81                // New storage unit
82                if !current_group.is_empty() {
83                    groups.push(std::mem::take(&mut current_group));
84                }
85                current_group.push(idx);
86                current_offset = base_offset;
87            }
88        } else if !current_group.is_empty() {
89            // Non-bitfield breaks the group
90            groups.push(std::mem::take(&mut current_group));
91            current_offset = None;
92        }
93    }
94
95    if !current_group.is_empty() {
96        groups.push(current_group);
97    }
98
99    groups
100}
101
102/// Optimize a struct layout by reordering fields to minimize padding.
103/// Uses greedy bin-packing: sort by alignment desc, then size desc.
104pub fn optimize_layout(layout: &StructLayout, max_align: u64) -> OptimizedLayout {
105    // If struct alignment is known, use it; otherwise infer from member alignments
106    let inferred_alignment = layout
107        .members
108        .iter()
109        .filter_map(|m| m.size)
110        .map(|s| infer_alignment(s, max_align))
111        .max()
112        .unwrap_or(1);
113
114    let struct_alignment = layout.alignment.unwrap_or(inferred_alignment).min(max_align);
115
116    // Find bitfield groups
117    let bitfield_groups = find_bitfield_groups(&layout.members);
118    let bitfield_indices: HashSet<usize> = bitfield_groups.iter().flatten().copied().collect();
119    let has_bitfields = !bitfield_groups.is_empty();
120
121    // Build original members list with inferred alignment
122    let mut original_members: Vec<OptimizedMember> = Vec::new();
123    let mut skipped_members: Vec<String> = Vec::new();
124
125    for member in &layout.members {
126        let Some(size) = member.size else {
127            skipped_members.push(member.name.clone());
128            continue;
129        };
130        let Some(offset) = member.offset else {
131            skipped_members.push(member.name.clone());
132            continue;
133        };
134        // Skip zero-size types
135        if size == 0 {
136            continue;
137        }
138
139        let alignment = infer_alignment(size, max_align);
140
141        original_members.push(OptimizedMember {
142            name: member.name.clone(),
143            type_name: member.type_name.clone(),
144            offset,
145            size,
146            alignment,
147            bit_offset: member.bit_offset,
148            bit_size: member.bit_size,
149        });
150    }
151
152    // Build sortable units
153    let mut units: Vec<SortableUnit> = Vec::new();
154    let mut processed_indices: HashSet<usize> = HashSet::new();
155
156    // Add bitfield groups as units
157    for group in &bitfield_groups {
158        if group.is_empty() {
159            continue;
160        }
161
162        let group_members: Vec<OptimizedMember> = group
163            .iter()
164            .filter_map(|&idx| {
165                layout
166                    .members
167                    .get(idx)
168                    .and_then(|lm| original_members.iter().find(|m| m.name == lm.name).cloned())
169            })
170            .collect();
171
172        if group_members.is_empty() {
173            continue;
174        }
175
176        // Bitfield group size = storage unit size (from first member)
177        let total_size = group_members.first().map(|m| m.size).unwrap_or(4);
178        let alignment = group_members.iter().map(|m| m.alignment).max().unwrap_or(4);
179
180        for idx in group {
181            processed_indices.insert(*idx);
182        }
183
184        units.push(SortableUnit { members: group_members, total_size, alignment });
185    }
186
187    // Add non-bitfield members as single-member units
188    for (idx, member) in layout.members.iter().enumerate() {
189        if processed_indices.contains(&idx) || bitfield_indices.contains(&idx) {
190            continue;
191        }
192
193        if let Some(opt_member) = original_members.iter().find(|m| m.name == member.name) {
194            units.push(SortableUnit {
195                members: vec![opt_member.clone()],
196                total_size: opt_member.size,
197                alignment: opt_member.alignment,
198            });
199        }
200    }
201
202    // Sort: largest alignment first, then largest size
203    units.sort_by(|a, b| {
204        b.alignment.cmp(&a.alignment).then_with(|| b.total_size.cmp(&a.total_size))
205    });
206
207    // Place members greedily
208    let mut optimized_members: Vec<OptimizedMember> = Vec::new();
209    let mut current_offset: u64 = 0;
210
211    for unit in units {
212        // Align to unit's alignment requirement
213        let aligned_offset = align_up(current_offset, unit.alignment);
214
215        for mut member in unit.members {
216            member.offset = aligned_offset;
217            optimized_members.push(member);
218        }
219
220        current_offset = aligned_offset + unit.total_size;
221    }
222
223    // Add tail padding to reach struct alignment
224    let optimized_size = align_up(current_offset, struct_alignment);
225
226    let savings_bytes = layout.size.saturating_sub(optimized_size);
227    let savings_percent =
228        if layout.size > 0 { (savings_bytes as f64 / layout.size as f64) * 100.0 } else { 0.0 };
229
230    OptimizedLayout {
231        name: layout.name.clone(),
232        original_size: layout.size,
233        optimized_size,
234        savings_bytes,
235        savings_percent,
236        struct_alignment,
237        original_members,
238        optimized_members,
239        skipped_members,
240        has_bitfields,
241    }
242}
243
244#[cfg(test)]
245mod tests {
246    use super::*;
247
248    #[test]
249    fn test_infer_alignment() {
250        assert_eq!(infer_alignment(1, 8), 1); // char
251        assert_eq!(infer_alignment(2, 8), 2); // short
252        assert_eq!(infer_alignment(4, 8), 4); // int
253        assert_eq!(infer_alignment(8, 8), 8); // long/pointer
254        assert_eq!(infer_alignment(16, 8), 8); // capped at max_align
255        assert_eq!(infer_alignment(3, 8), 4); // rounds up to power of 2
256        assert_eq!(infer_alignment(0, 8), 1); // ZST
257    }
258
259    #[test]
260    fn test_align_up() {
261        assert_eq!(align_up(0, 4), 0);
262        assert_eq!(align_up(1, 4), 4);
263        assert_eq!(align_up(4, 4), 4);
264        assert_eq!(align_up(5, 4), 8);
265        assert_eq!(align_up(7, 8), 8);
266    }
267
268    #[test]
269    fn test_optimize_padded_struct() {
270        // struct { char a; int b; char c; } = 12 bytes with padding
271        // optimal: struct { int b; char a; char c; } = 8 bytes
272        let mut layout = StructLayout::new("Test".to_string(), 12, Some(4));
273        layout.members = vec![
274            MemberLayout::new("a".to_string(), "char".to_string(), Some(0), Some(1)),
275            MemberLayout::new("b".to_string(), "int".to_string(), Some(4), Some(4)),
276            MemberLayout::new("c".to_string(), "char".to_string(), Some(8), Some(1)),
277        ];
278
279        let result = optimize_layout(&layout, 8);
280
281        assert_eq!(result.original_size, 12);
282        assert_eq!(result.optimized_size, 8);
283        assert_eq!(result.savings_bytes, 4);
284
285        // First member should be the int (largest alignment)
286        assert_eq!(result.optimized_members[0].name, "b");
287        assert_eq!(result.optimized_members[0].offset, 0);
288    }
289
290    #[test]
291    fn test_already_optimal() {
292        // struct { int a; int b; } = 8 bytes, already optimal
293        let mut layout = StructLayout::new("Test".to_string(), 8, Some(4));
294        layout.members = vec![
295            MemberLayout::new("a".to_string(), "int".to_string(), Some(0), Some(4)),
296            MemberLayout::new("b".to_string(), "int".to_string(), Some(4), Some(4)),
297        ];
298
299        let result = optimize_layout(&layout, 8);
300
301        assert_eq!(result.original_size, 8);
302        assert_eq!(result.optimized_size, 8);
303        assert_eq!(result.savings_bytes, 0);
304    }
305
306    #[test]
307    fn test_skipped_members() {
308        let mut layout = StructLayout::new("Test".to_string(), 16, Some(8));
309        layout.members = vec![
310            MemberLayout::new("a".to_string(), "int".to_string(), Some(0), Some(4)),
311            MemberLayout::new("b".to_string(), "unknown".to_string(), None, None), // missing info
312        ];
313
314        let result = optimize_layout(&layout, 8);
315
316        assert_eq!(result.skipped_members, vec!["b"]);
317    }
318}
layout_audit/analysis/optimize.rs

layout_audit/analysis/
optimize.rs
