addr2line/
line.rs

Help
1use alloc::boxed::Box;
2use alloc::string::{String, ToString};
3use alloc::vec::Vec;
4use core::cmp::Ordering;
5use core::mem;
6use core::num::NonZeroU64;
7
8use crate::lazy::LazyResult;
9use crate::{Error, Location};
10
11pub(crate) struct LazyLines(LazyResult<Lines>);
12
13impl LazyLines {
14    pub(crate) fn new() -> Self {
15        LazyLines(LazyResult::new())
16    }
17
18    pub(crate) fn borrow<R: gimli::Reader>(
19        &self,
20        dw_unit: gimli::UnitRef<R>,
21        ilnp: &gimli::IncompleteLineProgram<R, R::Offset>,
22    ) -> Result<&Lines, Error> {
23        self.0
24            .borrow_with(|| Lines::parse(dw_unit, ilnp.clone()))
25            .as_ref()
26            .map_err(Error::clone)
27    }
28}
29
30struct LineSequence {
31    start: u64,
32    end: u64,
33    rows: Box<[LineRow]>,
34}
35
36struct LineRow {
37    address: u64,
38    file_index: u64,
39    line: u32,
40    column: u32,
41}
42
43pub(crate) struct Lines {
44    files: Box<[String]>,
45    sequences: Box<[LineSequence]>,
46}
47
48impl Lines {
49    fn parse<R: gimli::Reader>(
50        dw_unit: gimli::UnitRef<R>,
51        ilnp: gimli::IncompleteLineProgram<R, R::Offset>,
52    ) -> Result<Self, Error> {
53        let mut sequences = Vec::new();
54        let mut sequence_rows = Vec::<LineRow>::new();
55        let mut rows = ilnp.rows();
56        while let Some((_, row)) = rows.next_row()? {
57            if row.end_sequence() {
58                if let Some(start) = sequence_rows.first().map(|x| x.address) {
59                    let end = row.address();
60                    let mut rows = Vec::new();
61                    mem::swap(&mut rows, &mut sequence_rows);
62                    sequences.push(LineSequence {
63                        start,
64                        end,
65                        rows: rows.into_boxed_slice(),
66                    });
67                }
68                continue;
69            }
70
71            let address = row.address();
72            let file_index = row.file_index();
73            // Convert line and column to u32 to save a little memory.
74            // We'll handle the special case of line 0 later,
75            // and return left edge as column 0 in the public API.
76            let line = row.line().map(NonZeroU64::get).unwrap_or(0) as u32;
77            let column = match row.column() {
78                gimli::ColumnType::LeftEdge => 0,
79                gimli::ColumnType::Column(x) => x.get() as u32,
80            };
81
82            if let Some(last_row) = sequence_rows.last_mut() {
83                if last_row.address == address {
84                    last_row.file_index = file_index;
85                    last_row.line = line;
86                    last_row.column = column;
87                    continue;
88                }
89            }
90
91            sequence_rows.push(LineRow {
92                address,
93                file_index,
94                line,
95                column,
96            });
97        }
98        sequences.sort_by_key(|x| x.start);
99
100        let mut files = Vec::new();
101        let header = rows.header();
102        match header.file(0) {
103            Some(file) => files.push(render_file(dw_unit, file, header)?),
104            None => files.push(String::from("")), // DWARF version <= 4 may not have 0th index
105        }
106        let mut index = 1;
107        while let Some(file) = header.file(index) {
108            files.push(render_file(dw_unit, file, header)?);
109            index += 1;
110        }
111
112        Ok(Self {
113            files: files.into_boxed_slice(),
114            sequences: sequences.into_boxed_slice(),
115        })
116    }
117
118    pub(crate) fn file(&self, index: u64) -> Option<&str> {
119        self.files.get(index as usize).map(String::as_str)
120    }
121
122    pub(crate) fn ranges(&self) -> impl Iterator<Item = gimli::Range> + '_ {
123        self.sequences.iter().map(|sequence| gimli::Range {
124            begin: sequence.start,
125            end: sequence.end,
126        })
127    }
128
129    fn row_location(&self, row: &LineRow) -> Location<'_> {
130        let file = self.files.get(row.file_index as usize).map(String::as_str);
131        Location {
132            file,
133            line: if row.line != 0 { Some(row.line) } else { None },
134            // If row.line is specified then row.column always has meaning.
135            column: if row.line != 0 {
136                Some(row.column)
137            } else {
138                None
139            },
140        }
141    }
142
143    pub(crate) fn find_location(&self, probe: u64) -> Result<Option<Location<'_>>, Error> {
144        let seq_idx = self.sequences.binary_search_by(|sequence| {
145            if probe < sequence.start {
146                Ordering::Greater
147            } else if probe >= sequence.end {
148                Ordering::Less
149            } else {
150                Ordering::Equal
151            }
152        });
153        let seq_idx = match seq_idx {
154            Ok(x) => x,
155            Err(_) => return Ok(None),
156        };
157        let sequence = &self.sequences[seq_idx];
158
159        let idx = sequence
160            .rows
161            .binary_search_by(|row| row.address.cmp(&probe));
162        let idx = match idx {
163            Ok(x) => x,
164            Err(0) => return Ok(None),
165            Err(x) => x - 1,
166        };
167        Ok(Some(self.row_location(&sequence.rows[idx])))
168    }
169
170    pub(crate) fn find_location_range(
171        &self,
172        probe_low: u64,
173        probe_high: u64,
174    ) -> Result<LineLocationRangeIter<'_>, Error> {
175        // Find index for probe_low.
176        let seq_idx = self.sequences.binary_search_by(|sequence| {
177            if probe_low < sequence.start {
178                Ordering::Greater
179            } else if probe_low >= sequence.end {
180                Ordering::Less
181            } else {
182                Ordering::Equal
183            }
184        });
185        let seq_idx = match seq_idx {
186            Ok(x) => x,
187            Err(x) => x, // probe below sequence, but range could overlap
188        };
189
190        let row_idx = if let Some(seq) = self.sequences.get(seq_idx) {
191            let idx = seq.rows.binary_search_by(|row| row.address.cmp(&probe_low));
192            match idx {
193                Ok(x) => x,
194                Err(0) => 0, // probe below sequence, but range could overlap
195                Err(x) => x - 1,
196            }
197        } else {
198            0
199        };
200
201        Ok(LineLocationRangeIter {
202            lines: self,
203            seq_idx,
204            row_idx,
205            probe_high,
206        })
207    }
208}
209
210pub(crate) struct LineLocationRangeIter<'ctx> {
211    lines: &'ctx Lines,
212    seq_idx: usize,
213    row_idx: usize,
214    probe_high: u64,
215}
216
217impl<'ctx> Iterator for LineLocationRangeIter<'ctx> {
218    type Item = (u64, u64, Location<'ctx>);
219
220    fn next(&mut self) -> Option<(u64, u64, Location<'ctx>)> {
221        while let Some(seq) = self.lines.sequences.get(self.seq_idx) {
222            if seq.start >= self.probe_high {
223                break;
224            }
225
226            match seq.rows.get(self.row_idx) {
227                Some(row) => {
228                    if row.address >= self.probe_high {
229                        break;
230                    }
231
232                    let nextaddr = seq
233                        .rows
234                        .get(self.row_idx + 1)
235                        .map(|row| row.address)
236                        .unwrap_or(seq.end);
237
238                    let item = (
239                        row.address,
240                        nextaddr - row.address,
241                        self.lines.row_location(row),
242                    );
243                    self.row_idx += 1;
244
245                    return Some(item);
246                }
247                None => {
248                    self.seq_idx += 1;
249                    self.row_idx = 0;
250                }
251            }
252        }
253        None
254    }
255}
256
257fn render_file<R: gimli::Reader>(
258    dw_unit: gimli::UnitRef<R>,
259    file: &gimli::FileEntry<R, R::Offset>,
260    header: &gimli::LineProgramHeader<R, R::Offset>,
261) -> Result<String, gimli::Error> {
262    let mut path = if let Some(ref comp_dir) = dw_unit.comp_dir {
263        comp_dir.to_string_lossy()?.into_owned()
264    } else {
265        String::new()
266    };
267
268    // The directory index 0 is defined to correspond to the compilation unit directory.
269    if file.directory_index() != 0 {
270        if let Some(directory) = file.directory(header) {
271            path_push(
272                &mut path,
273                dw_unit.attr_string(directory)?.to_string_lossy()?.as_ref(),
274            );
275        }
276    }
277
278    path_push(
279        &mut path,
280        dw_unit
281            .attr_string(file.path_name())?
282            .to_string_lossy()?
283            .as_ref(),
284    );
285
286    Ok(path)
287}
288
289fn path_push(path: &mut String, p: &str) {
290    if has_unix_root(p) || has_windows_root(p) {
291        *path = p.to_string();
292    } else {
293        let dir_separator = if has_windows_root(path.as_str()) {
294            '\\'
295        } else {
296            '/'
297        };
298
299        if !path.is_empty() && !path.ends_with(dir_separator) {
300            path.push(dir_separator);
301        }
302        *path += p;
303    }
304}
305
306/// Check if the path in the given string has a unix style root
307fn has_unix_root(p: &str) -> bool {
308    p.starts_with('/')
309}
310
311/// Check if the path in the given string has a windows style root
312fn has_windows_root(p: &str) -> bool {
313    p.starts_with('\\') || p.get(1..3) == Some(":\\")
314}
addr2line/line.rs

addr2line/
line.rs
