walrus/module/debug/
expression.rs

1use crate::{CodeTransform, Function, InstrLocId, ModuleFunctions};
2use id_arena::Id;
3use std::{cmp::Ordering, ops::Range};
4
5use super::dwarf::AddressSearchPreference;
6
7/// Specify roles of origial address.
8#[derive(Debug, PartialEq)]
9pub(crate) enum CodeAddress {
10    /// The address is instruction within a function.
11    InstrInFunction { instr_id: InstrLocId },
12    /// The address is one byte before the instruction.
13    InstrEdge { instr_id: InstrLocId },
14    /// The address is within a function, but does not match any instruction.
15    OffsetInFunction { id: Id<Function>, offset: usize },
16    /// The address is boundary of functions. Equals to OffsetInFunction with offset(section size).
17    FunctionEdge { id: Id<Function> },
18    /// The address is unknown.
19    Unknown,
20}
21
22/// Converts original code address to CodeAddress
23pub(crate) struct CodeAddressGenerator {
24    /// Function range based convert table
25    address_convert_table: Vec<(Range<usize>, Id<Function>)>,
26    /// Instrument based convert table
27    instrument_address_convert_table: Vec<(usize, InstrLocId)>,
28}
29
30impl CodeAddressGenerator {
31    pub(crate) fn new(funcs: &ModuleFunctions) -> Self {
32        let mut address_convert_table = funcs
33            .iter_local()
34            .filter_map(|(func_id, func)| func.original_range.clone().map(|range| (range, func_id)))
35            .collect::<Vec<_>>();
36
37        let mut instrument_address_convert_table = funcs
38            .iter_local()
39            .flat_map(|(_, func)| &func.instruction_mapping)
40            .copied()
41            .collect::<Vec<_>>();
42
43        address_convert_table.sort_by_key(|i| i.0.start);
44        instrument_address_convert_table.sort_by_key(|i| i.0);
45
46        Self {
47            address_convert_table,
48            instrument_address_convert_table,
49        }
50    }
51
52    pub(crate) fn find_address(
53        &self,
54        address: usize,
55        search_preference: AddressSearchPreference,
56    ) -> CodeAddress {
57        match self
58            .instrument_address_convert_table
59            .binary_search_by_key(&address, |i| i.0)
60        {
61            Ok(id) => {
62                return CodeAddress::InstrInFunction {
63                    instr_id: self.instrument_address_convert_table[id].1,
64                }
65            }
66            Err(id) => {
67                if id < self.instrument_address_convert_table.len()
68                    && self.instrument_address_convert_table[id].0 - 1 == address
69                {
70                    return CodeAddress::InstrEdge {
71                        instr_id: self.instrument_address_convert_table[id].1,
72                    };
73                }
74            }
75        };
76
77        // If the address is not mapped to any instruction, falling back to function-range-based comparison.
78        let inclusive_range_comparor = |range: &(Range<usize>, Id<Function>)| {
79            // range.start < address <= range.end
80            if range.0.end < address {
81                Ordering::Less
82            } else if address <= range.0.start {
83                Ordering::Greater
84            } else {
85                Ordering::Equal
86            }
87        };
88        let exclusive_range_comparor = |range: &(Range<usize>, Id<Function>)| {
89            // normal comparison: range.start <= address < range.end
90            if range.0.end <= address {
91                Ordering::Less
92            } else if address < range.0.start {
93                Ordering::Greater
94            } else {
95                Ordering::Equal
96            }
97        };
98        let range_comparor: &dyn Fn(_) -> Ordering = match search_preference {
99            AddressSearchPreference::InclusiveFunctionEnd => &inclusive_range_comparor,
100            AddressSearchPreference::ExclusiveFunctionEnd => &exclusive_range_comparor,
101        };
102
103        match self.address_convert_table.binary_search_by(range_comparor) {
104            Ok(i) => {
105                let entry = &self.address_convert_table[i];
106                let code_offset_from_function_start = address - entry.0.start;
107
108                if address == entry.0.end {
109                    CodeAddress::FunctionEdge { id: entry.1 }
110                } else {
111                    CodeAddress::OffsetInFunction {
112                        id: entry.1,
113                        offset: code_offset_from_function_start,
114                    }
115                }
116            }
117            Err(_) => CodeAddress::Unknown,
118        }
119    }
120}
121
122/// Converts CodeAddress to translated code address
123pub(crate) struct CodeAddressConverter<'a> {
124    code_transform: &'a CodeTransform,
125}
126
127impl<'a> CodeAddressConverter<'a> {
128    pub(crate) fn new(code_transform: &'a CodeTransform) -> Self {
129        Self { code_transform }
130    }
131
132    pub(crate) fn find_address(&self, code: CodeAddress) -> Option<usize> {
133        match code {
134            CodeAddress::InstrInFunction { instr_id } => {
135                match self
136                    .code_transform
137                    .instruction_map
138                    .binary_search_by_key(&instr_id, |i| i.0)
139                {
140                    Ok(id) => Some(self.code_transform.instruction_map[id].1),
141                    Err(_) => None,
142                }
143            }
144            CodeAddress::InstrEdge { instr_id } => {
145                match self
146                    .code_transform
147                    .instruction_map
148                    .binary_search_by_key(&instr_id, |i| i.0)
149                {
150                    Ok(id) => Some(self.code_transform.instruction_map[id].1 - 1),
151                    Err(_) => None,
152                }
153            }
154            CodeAddress::OffsetInFunction { id, offset } => {
155                match self
156                    .code_transform
157                    .function_ranges
158                    .binary_search_by_key(&id, |i| i.0)
159                {
160                    Ok(id) => Some(self.code_transform.function_ranges[id].1.start + offset),
161                    Err(_) => None,
162                }
163            }
164            CodeAddress::FunctionEdge { id } => {
165                match self
166                    .code_transform
167                    .function_ranges
168                    .binary_search_by_key(&id, |i| i.0)
169                {
170                    Ok(id) => Some(self.code_transform.function_ranges[id].1.end),
171                    Err(_) => None,
172                }
173            }
174            CodeAddress::Unknown => None,
175        }
176    }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182
183    #[test]
184    fn test_code_address_generator() {
185        let mut module = crate::Module::default();
186
187        let mut func1 = crate::LocalFunction::new(
188            Vec::new(),
189            crate::FunctionBuilder::new(&mut module.types, &[], &[]),
190        );
191
192        func1.original_range = Some(Range { start: 20, end: 30 });
193
194        let id1 = module.funcs.add_local(func1);
195
196        let mut func2 = crate::LocalFunction::new(
197            Vec::new(),
198            crate::FunctionBuilder::new(&mut module.types, &[], &[]),
199        );
200
201        func2.original_range = Some(Range { start: 30, end: 50 });
202
203        let id2 = module.funcs.add_local(func2);
204
205        let address_converter = CodeAddressGenerator::new(&module.funcs);
206
207        assert_eq!(
208            address_converter.find_address(10, AddressSearchPreference::InclusiveFunctionEnd),
209            CodeAddress::Unknown
210        );
211        assert_eq!(
212            address_converter.find_address(20, AddressSearchPreference::ExclusiveFunctionEnd),
213            CodeAddress::OffsetInFunction { id: id1, offset: 0 }
214        );
215        assert_eq!(
216            address_converter.find_address(20, AddressSearchPreference::InclusiveFunctionEnd),
217            CodeAddress::Unknown
218        );
219        assert_eq!(
220            address_converter.find_address(25, AddressSearchPreference::ExclusiveFunctionEnd),
221            CodeAddress::OffsetInFunction { id: id1, offset: 5 }
222        );
223        assert_eq!(
224            address_converter.find_address(29, AddressSearchPreference::ExclusiveFunctionEnd),
225            CodeAddress::OffsetInFunction { id: id1, offset: 9 }
226        );
227        assert_eq!(
228            address_converter.find_address(29, AddressSearchPreference::InclusiveFunctionEnd),
229            CodeAddress::OffsetInFunction { id: id1, offset: 9 }
230        );
231        assert_eq!(
232            address_converter.find_address(30, AddressSearchPreference::InclusiveFunctionEnd),
233            CodeAddress::FunctionEdge { id: id1 }
234        );
235        assert_eq!(
236            address_converter.find_address(30, AddressSearchPreference::ExclusiveFunctionEnd),
237            CodeAddress::OffsetInFunction { id: id2, offset: 0 }
238        );
239        assert_eq!(
240            address_converter.find_address(50, AddressSearchPreference::InclusiveFunctionEnd),
241            CodeAddress::FunctionEdge { id: id2 }
242        );
243        assert_eq!(
244            address_converter.find_address(50, AddressSearchPreference::ExclusiveFunctionEnd),
245            CodeAddress::Unknown
246        );
247    }
248
249    #[test]
250    fn test_code_address_converter() {
251        let mut module = crate::Module::default();
252
253        let func1 = crate::LocalFunction::new(
254            Vec::new(),
255            crate::FunctionBuilder::new(&mut module.types, &[], &[]),
256        );
257        let id1 = module.funcs.add_local(func1);
258        let instr_id1 = InstrLocId::new(1);
259        let instr_id2 = InstrLocId::new(2);
260
261        let mut code_transform = CodeTransform::default();
262        {
263            code_transform
264                .function_ranges
265                .push((id1, Range { start: 50, end: 80 }));
266            code_transform.instruction_map.push((instr_id1, 60));
267            code_transform.instruction_map.push((instr_id2, 65));
268        }
269
270        let converter = CodeAddressConverter::new(&code_transform);
271
272        assert_eq!(
273            converter.find_address(CodeAddress::OffsetInFunction { id: id1, offset: 5 }),
274            Some(55)
275        );
276        assert_eq!(
277            converter.find_address(CodeAddress::InstrInFunction {
278                instr_id: instr_id1
279            }),
280            Some(60)
281        );
282        assert_eq!(
283            converter.find_address(CodeAddress::InstrEdge {
284                instr_id: instr_id2
285            }),
286            Some(64)
287        );
288        assert_eq!(
289            converter.find_address(CodeAddress::InstrInFunction {
290                instr_id: instr_id2
291            }),
292            Some(65)
293        );
294        assert_eq!(
295            converter.find_address(CodeAddress::FunctionEdge { id: id1 }),
296            Some(80)
297        );
298        assert_eq!(converter.find_address(CodeAddress::Unknown), None);
299    }
300}
walrus/module/debug/expression.rs

walrus/module/debug/
expression.rs
