addr2line/
line.rs

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

addr2line/
line.rs
