Skip to main content

parsec_encoding/
offsets.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! Offsets into the bytes a page came as. The parser counts UTF-8 bytes
5//! into the text it was given, the decoded page; a caller with the
6//! original bytes wants offsets into those.
7
8use encoding_rs::{CoderResult, Encoding, UTF_8, UTF_16BE, UTF_16LE};
9
10/// Turns offsets into a decoded page into offsets into its bytes, and
11/// back, for the spans and parse errors of a document parsed from bytes.
12///
13/// ```
14/// use parsec_encoding::{Offsets, Options, parse_bytes};
15///
16/// let page = b"<meta charset=shift_jis><p>\x93\xfa\x96\x7b<b>!</b>";
17/// let parsed = parse_bytes(page, Options {
18///     html: parsec::Options { spans: true, ..Default::default() },
19///     ..Options::default()
20/// }).unwrap();
21/// let offsets = Offsets::new(page, parsed.encoding);
22/// let doc = &parsed.document;
23/// let b = (0..doc.len() as u32).find(|&n| doc.lower_name(n) == Some("b")).unwrap();
24/// let span = doc.span(b).unwrap();
25/// // 日本 is six bytes decoded, four in Shift_JIS.
26/// assert_eq!(span, 33..36);
27/// let (start, end) = (offsets.to_source(span.start), offsets.to_source(span.end));
28/// assert_eq!(&page[start..end], b"<b>");
29/// ```
30///
31/// It's built by decoding the bytes again, noting where each character's
32/// bytes started (UTF-8 and the single-byte encodings in one pass, the
33/// others a byte at a time, which takes two or three times as long as
34/// the parse), and keeps only the places where the two stop moving
35/// together: after the byte order mark, at each character whose length
36/// differs between the two (each Shift_JIS kanji, say), and after each
37/// run of bytes the decoding replaced with U+FFFD. ASCII costs nothing;
38/// text that's all non-ASCII costs 8 bytes a character.
39pub struct Offsets {
40    /// (decoded, source) at each place where an offset can't be worked out
41    /// from the one before by counting on, in order of both.
42    points: Vec<(u32, u32)>,
43}
44
45impl Offsets {
46    /// The offsets for `bytes` decoded as [`parse_bytes`](crate::parse_bytes)
47    /// and [`ByteParser`](crate::ByteParser) decode them in `encoding`:
48    /// with the encoding's own byte order mark removed.
49    pub fn new(bytes: &[u8], encoding: &'static Encoding) -> Offsets {
50        let mut map = Offsets { points: Vec::new() };
51        let bom = match Encoding::for_bom(bytes) {
52            Some((found, len)) if found == encoding => len,
53            _ => 0,
54        };
55        map.at(0, bom);
56        if encoding == UTF_8 {
57            // Rust's lossy decoding replaces the same runs with U+FFFD as
58            // the Encoding Standard's, and far faster than byte by byte.
59            let (mut decoded, mut source) = (0, bom);
60            for chunk in bytes[bom..].utf8_chunks() {
61                decoded += chunk.valid().len();
62                source += chunk.valid().len();
63                if !chunk.invalid().is_empty() {
64                    decoded += '\u{FFFD}'.len_utf8();
65                    source += chunk.invalid().len();
66                    map.at(decoded, source);
67                }
68            }
69            return map;
70        }
71        if encoding.is_single_byte() {
72            // One byte, one character, so one decode of the whole will do.
73            let (text, _) = encoding.decode_without_bom_handling(bytes);
74            let mut decoded = 0;
75            for (i, c) in text.chars().enumerate() {
76                map.at(decoded, i);
77                decoded += c.len_utf8();
78            }
79            return map;
80        }
81        // Outside UTF-16, an ASCII character out is the one byte just read
82        // in (escape sequences in ISO-2022-JP produce nothing).
83        let narrow = encoding != UTF_16BE && encoding != UTF_16LE;
84        let mut decoder = encoding.new_decoder_without_bom_handling();
85        let mut out = [0u8; 64];
86        let mut decoded = 0;
87        // Where the bytes of the next character to come out began.
88        let mut from = bom;
89        for i in bom..=bytes.len() {
90            let last = i == bytes.len();
91            let mut input = if last { &[][..] } else { &bytes[i..i + 1] };
92            let mut first = true;
93            loop {
94                let (result, read, written, _) = decoder.decode_to_utf8(input, &mut out, last);
95                input = &input[read..];
96                for (k, &b) in out[..written].iter().enumerate() {
97                    // Every byte but a UTF-8 continuation byte starts one.
98                    if (b as i8) >= -0x40 {
99                        // More than one at once is a U+FFFD for bytes
100                        // before this one, then what this one began.
101                        let start = if first && !(narrow && b < 0x80) {
102                            from
103                        } else {
104                            i
105                        };
106                        map.at(decoded + k, start);
107                        first = false;
108                    }
109                }
110                decoded += written;
111                if result == CoderResult::InputEmpty {
112                    break;
113                }
114            }
115            if !first {
116                from = i + 1;
117            }
118        }
119        map.at(decoded, bytes.len());
120        map
121    }
122
123    /// Notes that decoded offset `decoded` is source offset `source`,
124    /// unless counting on from the last point says so already.
125    fn at(&mut self, decoded: usize, source: usize) {
126        let (d, s) = self.points.last().copied().unwrap_or((0, 0));
127        if source as u64 != u64::from(s) + (decoded as u64 - u64::from(d)) {
128            // A document holds at most 512 MiB, so both fit.
129            self.points.push((decoded as u32, source as u32));
130        }
131    }
132
133    /// Whether every offset is the same in both: ASCII, or UTF-8 with no
134    /// byte order mark and nothing replaced.
135    pub fn is_identity(&self) -> bool {
136        self.points.is_empty()
137    }
138
139    /// The offset into the bytes of offset `decoded` into the decoded text.
140    pub fn to_source(&self, decoded: usize) -> usize {
141        let i = self.points.partition_point(|&(d, _)| d as usize <= decoded);
142        match i.checked_sub(1).map(|i| self.points[i]) {
143            Some((d, s)) => s as usize + (decoded - d as usize),
144            None => decoded,
145        }
146    }
147
148    /// The offset into the decoded text of offset `source` into the bytes.
149    /// One inside a character's bytes gives one inside its decoding, never
150    /// past it.
151    pub fn to_decoded(&self, source: usize) -> usize {
152        let i = self.points.partition_point(|&(_, s)| s as usize <= source);
153        match i.checked_sub(1).map(|i| self.points[i]) {
154            Some((d, s)) => {
155                let at = d as usize + (source - s as usize);
156                self.points
157                    .get(i)
158                    .map_or(at, |&(next, _)| at.min(next as usize))
159            }
160            None => source,
161        }
162    }
163}
164
165#[cfg(test)]
166mod tests {
167    use super::*;
168    use encoding_rs::*;
169
170    /// Every ASCII character of the decoding maps to the same byte in the
171    /// source, and back.
172    fn check(bytes: &[u8], encoding: &'static Encoding) -> Offsets {
173        let (text, _) = encoding.decode_with_bom_removal(bytes);
174        let map = Offsets::new(bytes, encoding);
175        for (d, c) in text.char_indices() {
176            if c.is_ascii() && encoding != UTF_16BE {
177                let s = map.to_source(d);
178                assert_eq!(bytes[s], c as u8, "{} at {d}", encoding.name());
179                assert_eq!(map.to_decoded(s), d);
180            }
181        }
182        assert_eq!(map.to_source(text.len()), bytes.len());
183        map
184    }
185
186    #[test]
187    fn ascii_and_clean_utf8_are_the_identity() {
188        assert!(check(b"<p>plain", UTF_8).is_identity());
189        assert!(check("<p>caf\u{e9}".as_bytes(), UTF_8).is_identity());
190        assert!(check(b"<p>plain", WINDOWS_1252).is_identity());
191    }
192
193    #[test]
194    fn utf8_boms_and_bad_bytes() {
195        let map = check(b"\xef\xbb\xbf<p>\xff\xfe</p><b>x", UTF_8);
196        // A U+FFFD for each bad byte: 3 bytes decoded, 1 in the source.
197        assert_eq!(map.to_source(3 + 6 + 2), 3 + 3 + 2 + 2);
198    }
199
200    #[test]
201    fn legacy_multibyte() {
202        // 日本 in each, with markup around.
203        check(b"<p>\x93\xfa\x96\x7b</p><b>x</b>", SHIFT_JIS);
204        check(b"<p>\xc6\xfc\xcb\xdc</p><b>x</b>", EUC_JP);
205        check(b"<p>\x1b$BF|K\\\x1b(B</p><b>x</b>", ISO_2022_JP);
206        check(b"<p>\xc8\xd5\xb1\xbe</p><b>x</b>", GBK);
207        check(b"<p>\x81\x30\x81\x30\xc8\xd5</p><b>x</b>", GB18030);
208        check(b"<p>\xa4\xe9\xa5\xbb</p><b>x</b>", BIG5);
209        check(b"<p>\xc0\xcf\xba\xbb</p><b>x</b>", EUC_KR);
210        check(b"<p>\xcf\xf0\xe8</p><b>x</b>", WINDOWS_1251);
211    }
212
213    #[test]
214    fn a_bad_lead_byte_then_ascii() {
215        // 0x93 wants a trail byte; `<` isn't one, so the decoder gives
216        // U+FFFD for the 0x93 and then the `<` it reread.
217        let map = check(b"<p>\x93<b>x</b>", SHIFT_JIS);
218        assert_eq!(map.to_source(6), 4);
219        // And one cut off at the end.
220        check(b"<p>x\x93", SHIFT_JIS);
221    }
222
223    #[test]
224    fn utf16() {
225        let mut bytes = vec![0xff, 0xfe];
226        for u in "<p>\u{65e5}\u{1F600}x".encode_utf16() {
227            bytes.extend(u.to_le_bytes());
228        }
229        let map = check(&bytes, UTF_16LE);
230        // `<` at 2 after the byte order mark, then 2 bytes a unit.
231        assert_eq!(map.to_source(0), 2);
232        assert_eq!(map.to_source(3), 8);
233        // 日 is 3 bytes decoded, 😀 4 bytes in both.
234        assert_eq!(map.to_source(6), 10);
235        assert_eq!(map.to_source(10), 14);
236        // Inside 日's two bytes: inside its decoding.
237        assert_eq!(map.to_decoded(9), 4);
238    }
239}