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}