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}