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 bom = match Encoding::for_bom(bytes) {
51            Some((found, len)) if found == encoding => len,
52            _ => 0,
53        };
54        if encoding == UTF_8 {
55            return Offsets::utf8(bytes, bom);
56        }
57        let mut map = Offsets { points: Vec::new() };
58        map.at(0, bom);
59        if encoding.is_single_byte() {
60            // One byte, one character, so one decode of the whole will do.
61            let (text, _) = encoding.decode_without_bom_handling(bytes);
62            let mut decoded = 0;
63            for (i, c) in text.chars().enumerate() {
64                map.at(decoded, i);
65                decoded += c.len_utf8();
66            }
67            return map;
68        }
69        // Outside UTF-16, an ASCII character out is the one byte just read
70        // in (escape sequences in ISO-2022-JP produce nothing).
71        let narrow = encoding != UTF_16BE && encoding != UTF_16LE;
72        let mut decoder = encoding.new_decoder_without_bom_handling();
73        let mut out = [0u8; 64];
74        let mut decoded = 0;
75        // Where the bytes of the next character to come out began.
76        let mut from = bom;
77        for i in bom..=bytes.len() {
78            let last = i == bytes.len();
79            let mut input = if last { &[][..] } else { &bytes[i..i + 1] };
80            let mut first = true;
81            loop {
82                let (result, read, written, _) = decoder.decode_to_utf8(input, &mut out, last);
83                input = &input[read..];
84                for (k, &b) in out[..written].iter().enumerate() {
85                    // Every byte but a UTF-8 continuation byte starts one.
86                    if (b as i8) >= -0x40 {
87                        // More than one at once is a U+FFFD for bytes
88                        // before this one, then what this one began.
89                        let start = if first && !(narrow && b < 0x80) {
90                            from
91                        } else {
92                            i
93                        };
94                        map.at(decoded + k, start);
95                        first = false;
96                    }
97                }
98                decoded += written;
99                if result == CoderResult::InputEmpty {
100                    break;
101                }
102            }
103            if !first {
104                from = i + 1;
105            }
106        }
107        map.at(decoded, bytes.len());
108        map
109    }
110
111    /// The offsets for `bytes` decoded as [`String::from_utf8_lossy`]
112    /// decodes them: a byte order mark kept, as text, and each run of
113    /// bytes that isn't UTF-8 one U+FFFD. Parsing such a string, the
114    /// parser counts offsets into it.
115    pub fn lossy_utf8(bytes: &[u8]) -> Offsets {
116        Offsets::utf8(bytes, 0)
117    }
118
119    /// UTF-8 from `bom` on. Rust's lossy decoding replaces the same runs
120    /// with U+FFFD as the Encoding Standard's, and far faster than byte
121    /// by byte.
122    fn utf8(bytes: &[u8], bom: usize) -> Offsets {
123        let mut map = Offsets { points: Vec::new() };
124        map.at(0, bom);
125        let (mut decoded, mut source) = (0, bom);
126        for chunk in bytes[bom..].utf8_chunks() {
127            decoded += chunk.valid().len();
128            source += chunk.valid().len();
129            if !chunk.invalid().is_empty() {
130                decoded += '\u{FFFD}'.len_utf8();
131                source += chunk.invalid().len();
132                map.at(decoded, source);
133            }
134        }
135        map
136    }
137
138    /// Notes that decoded offset `decoded` is source offset `source`,
139    /// unless counting on from the last point says so already.
140    fn at(&mut self, decoded: usize, source: usize) {
141        let (d, s) = self.points.last().copied().unwrap_or((0, 0));
142        if source as u64 != u64::from(s) + (decoded as u64 - u64::from(d)) {
143            // A document holds at most 512 MiB, so both fit.
144            self.points.push((decoded as u32, source as u32));
145        }
146    }
147
148    /// Whether every offset is the same in both: ASCII, or UTF-8 with no
149    /// byte order mark and nothing replaced.
150    pub fn is_identity(&self) -> bool {
151        self.points.is_empty()
152    }
153
154    /// The offset into the bytes of offset `decoded` into the decoded text.
155    /// An offset past the end maps past the end, saturating at `usize::MAX`.
156    pub fn to_source(&self, decoded: usize) -> usize {
157        let i = self.points.partition_point(|&(d, _)| d as usize <= decoded);
158        match i.checked_sub(1).map(|i| self.points[i]) {
159            Some((d, s)) => (s as usize).saturating_add(decoded - d as usize),
160            None => decoded,
161        }
162    }
163
164    /// The offset into the decoded text of offset `source` into the bytes.
165    /// One inside a character's bytes gives one inside its decoding, never
166    /// past it. An offset past the end maps past the end, saturating at
167    /// `usize::MAX`.
168    pub fn to_decoded(&self, source: usize) -> usize {
169        let i = self.points.partition_point(|&(_, s)| s as usize <= source);
170        match i.checked_sub(1).map(|i| self.points[i]) {
171            Some((d, s)) => {
172                let at = (d as usize).saturating_add(source - s as usize);
173                self.points
174                    .get(i)
175                    .map_or(at, |&(next, _)| at.min(next as usize))
176            }
177            None => source,
178        }
179    }
180}
181
182#[cfg(test)]
183mod tests {
184    use super::*;
185    use encoding_rs::*;
186
187    #[test]
188    fn lossy_utf8_keeps_the_byte_order_mark() {
189        let bytes = b"\xEF\xBB\xBF\xFF\xFFab";
190        let text = String::from_utf8_lossy(bytes);
191        let map = Offsets::lossy_utf8(bytes);
192        let a = text.find('a').unwrap();
193        assert_eq!(map.to_source(a), 5);
194        assert_eq!(map.to_decoded(5), a);
195        assert_eq!(map.to_source(0), 0);
196        assert!(Offsets::lossy_utf8(b"plain").is_identity());
197    }
198
199    #[test]
200    fn offsets_past_the_end_saturate() {
201        // A byte order mark and a replaced byte, so neither map is identity.
202        let map = Offsets::new(b"\xEF\xBB\xBFa\xFFb", UTF_8);
203        assert!(!map.is_identity());
204        for far in [usize::MAX, usize::MAX - 1, usize::MAX / 2 + 7] {
205            assert!(map.to_decoded(far) >= far / 2);
206            assert!(map.to_source(far) >= far / 2);
207        }
208    }
209
210    /// Every ASCII character of the decoding maps to the same byte in the
211    /// source, and back.
212    fn check(bytes: &[u8], encoding: &'static Encoding) -> Offsets {
213        let (text, _) = encoding.decode_with_bom_removal(bytes);
214        let map = Offsets::new(bytes, encoding);
215        for (d, c) in text.char_indices() {
216            if c.is_ascii() && encoding != UTF_16BE {
217                let s = map.to_source(d);
218                assert_eq!(bytes[s], c as u8, "{} at {d}", encoding.name());
219                assert_eq!(map.to_decoded(s), d);
220            }
221        }
222        assert_eq!(map.to_source(text.len()), bytes.len());
223        map
224    }
225
226    #[test]
227    fn ascii_and_clean_utf8_are_the_identity() {
228        assert!(check(b"<p>plain", UTF_8).is_identity());
229        assert!(check("<p>caf\u{e9}".as_bytes(), UTF_8).is_identity());
230        assert!(check(b"<p>plain", WINDOWS_1252).is_identity());
231    }
232
233    #[test]
234    fn utf8_boms_and_bad_bytes() {
235        let map = check(b"\xef\xbb\xbf<p>\xff\xfe</p><b>x", UTF_8);
236        // A U+FFFD for each bad byte: 3 bytes decoded, 1 in the source.
237        assert_eq!(map.to_source(3 + 6 + 2), 3 + 3 + 2 + 2);
238    }
239
240    #[test]
241    fn legacy_multibyte() {
242        // 日本 in each, with markup around.
243        check(b"<p>\x93\xfa\x96\x7b</p><b>x</b>", SHIFT_JIS);
244        check(b"<p>\xc6\xfc\xcb\xdc</p><b>x</b>", EUC_JP);
245        check(b"<p>\x1b$BF|K\\\x1b(B</p><b>x</b>", ISO_2022_JP);
246        check(b"<p>\xc8\xd5\xb1\xbe</p><b>x</b>", GBK);
247        check(b"<p>\x81\x30\x81\x30\xc8\xd5</p><b>x</b>", GB18030);
248        check(b"<p>\xa4\xe9\xa5\xbb</p><b>x</b>", BIG5);
249        check(b"<p>\xc0\xcf\xba\xbb</p><b>x</b>", EUC_KR);
250        check(b"<p>\xcf\xf0\xe8</p><b>x</b>", WINDOWS_1251);
251    }
252
253    #[test]
254    fn a_bad_lead_byte_then_ascii() {
255        // 0x93 wants a trail byte; `<` isn't one, so the decoder gives
256        // U+FFFD for the 0x93 and then the `<` it reread.
257        let map = check(b"<p>\x93<b>x</b>", SHIFT_JIS);
258        assert_eq!(map.to_source(6), 4);
259        // And one cut off at the end.
260        check(b"<p>x\x93", SHIFT_JIS);
261    }
262
263    #[test]
264    fn utf16() {
265        let mut bytes = vec![0xff, 0xfe];
266        for u in "<p>\u{65e5}\u{1F600}x".encode_utf16() {
267            bytes.extend(u.to_le_bytes());
268        }
269        let map = check(&bytes, UTF_16LE);
270        // `<` at 2 after the byte order mark, then 2 bytes a unit.
271        assert_eq!(map.to_source(0), 2);
272        assert_eq!(map.to_source(3), 8);
273        // 日 is 3 bytes decoded, 😀 4 bytes in both.
274        assert_eq!(map.to_source(6), 10);
275        assert_eq!(map.to_source(10), 14);
276        // Inside 日's two bytes: inside its decoding.
277        assert_eq!(map.to_decoded(9), 4);
278    }
279}