1use crate::engine::value::{JsString, JsStringError, decode_quickjs_utf8};
11use std::collections::TryReserveError;
12use std::iter::FusedIterator;
13use std::ops::Range;
14
15const HIGH_SURROGATE_START: u16 = 0xd800;
16const LOW_SURROGATE_END: u16 = 0xdfff;
17const CARRIER_START: u32 = 0xe000;
18const CARRIER_UTF8_LEN: usize = 3;
19pub(crate) const INVALID_BYTE_CARRIER: char = '\u{7f}';
20
21#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
32pub struct SurrogateMarker {
33 byte_offset: u32,
34 unit: u16,
35}
36
37#[cfg_attr(not(test), allow(dead_code))]
38impl SurrogateMarker {
39 #[must_use]
40 pub const fn byte_offset(self) -> u32 {
41 self.byte_offset
42 }
43
44 #[must_use]
45 pub const fn unit(self) -> u16 {
46 self.unit
47 }
48}
49
50#[derive(Clone, Debug, Eq, PartialEq)]
56pub struct SourceText {
57 raw: Option<Box<[u8]>>,
60 carrier: Box<str>,
61 surrogates: Box<[SurrogateMarker]>,
62 invalid_bytes: Box<[u32]>,
63}
64
65#[derive(Clone, Copy, Debug)]
67pub struct SourceTextSlice<'a> {
68 raw: &'a [u8],
69 carrier: &'a str,
70 base_byte_offset: u32,
71 surrogates: &'a [SurrogateMarker],
72 invalid_bytes: &'a [u32],
73}
74
75pub struct SourceTextUtf16Units<'a> {
77 chars: std::str::CharIndices<'a>,
78 base_byte_offset: u32,
79 surrogates: &'a [SurrogateMarker],
80 marker_index: usize,
81 pending_low_surrogate: Option<u16>,
82}
83
84#[cfg_attr(not(test), allow(dead_code))]
85impl SourceText {
86 #[must_use]
91 pub fn from_utf8(source: &str) -> Self {
92 Self {
93 raw: None,
94 carrier: source.into(),
95 surrogates: Box::default(),
96 invalid_bytes: Box::default(),
97 }
98 }
99
100 pub fn try_from_raw_bytes(source: &[u8]) -> Result<Self, JsStringError> {
113 if source.len() > u32::MAX as usize {
114 return Err(JsStringError::TooLong);
115 }
116
117 let mut carrier = String::new();
118 carrier
119 .try_reserve_exact(source.len())
120 .map_err(|_| JsStringError::OutOfMemory)?;
121 let mut surrogates = Vec::new();
122 let mut invalid_bytes = Vec::new();
123
124 let mut offset = 0;
125 while offset < source.len() {
126 let byte = source[offset];
127 if byte < 0x80 {
128 carrier.push(char::from(byte));
129 offset += 1;
130 continue;
131 }
132
133 match decode_quickjs_utf8(&source[offset..]) {
134 Some((code_point, consumed)) if code_point <= 0x10_ffff => {
135 if let Ok(unit) = u16::try_from(code_point)
136 && is_surrogate(unit)
137 {
138 let byte_offset =
139 u32::try_from(offset).map_err(|_| JsStringError::TooLong)?;
140 surrogates
141 .try_reserve(1)
142 .map_err(|_| JsStringError::OutOfMemory)?;
143 surrogates.push(SurrogateMarker { byte_offset, unit });
144 carrier.push(surrogate_carrier(unit));
145 } else {
146 carrier.push(
147 char::from_u32(code_point)
148 .expect("validated non-surrogate Unicode scalar"),
149 );
150 }
151 offset += consumed;
152 }
153 Some(_) | None => {
154 invalid_bytes
155 .try_reserve(1)
156 .map_err(|_| JsStringError::OutOfMemory)?;
157 invalid_bytes.push(u32::try_from(offset).map_err(|_| JsStringError::TooLong)?);
158 carrier.push(INVALID_BYTE_CARRIER);
159 offset += 1;
160 }
161 }
162 debug_assert_eq!(carrier.len(), offset);
163 }
164
165 let raw = if surrogates.is_empty() && invalid_bytes.is_empty() {
166 None
167 } else {
168 let mut raw = Vec::new();
169 raw.try_reserve_exact(source.len())
170 .map_err(|_| JsStringError::OutOfMemory)?;
171 raw.extend_from_slice(source);
172 Some(raw.into_boxed_slice())
173 };
174 let result = Self {
175 raw,
176 carrier: carrier.into_boxed_str(),
177 surrogates: surrogates.into_boxed_slice(),
178 invalid_bytes: invalid_bytes.into_boxed_slice(),
179 };
180 debug_assert!(result.invariants_hold());
181 Ok(result)
182 }
183
184 pub fn try_from_js_string(source: &JsString) -> Result<Self, JsStringError> {
193 let raw = source
194 .try_to_wtf8_bytes()
195 .map_err(|_| JsStringError::OutOfMemory)?;
196 Self::try_from_raw_bytes(&raw)
197 }
198
199 pub fn try_from_utf16(units: impl IntoIterator<Item = u16>) -> Result<Self, JsStringError> {
204 let source = JsString::try_from_utf16(units)?;
205 Self::try_from_js_string(&source)
206 }
207
208 #[must_use]
209 pub fn carrier(&self) -> &str {
210 &self.carrier
211 }
212
213 #[must_use]
214 pub fn raw_bytes(&self) -> &[u8] {
215 self.raw.as_deref().unwrap_or(self.carrier.as_bytes())
216 }
217
218 #[must_use]
219 pub fn has_surrogate_markers(&self) -> bool {
220 !self.surrogates.is_empty()
221 }
222
223 #[must_use]
224 pub fn surrogate_markers(&self) -> &[SurrogateMarker] {
225 &self.surrogates
226 }
227
228 #[must_use]
230 pub fn surrogate_at(&self, byte_offset: usize) -> Option<u16> {
231 let byte_offset = u32::try_from(byte_offset).ok()?;
232 self.surrogates
233 .binary_search_by_key(&byte_offset, |marker| marker.byte_offset)
234 .ok()
235 .map(|index| self.surrogates[index].unit)
236 }
237
238 #[must_use]
240 pub fn invalid_byte_at(&self, byte_offset: usize) -> bool {
241 u32::try_from(byte_offset)
242 .is_ok_and(|offset| self.invalid_bytes.binary_search(&offset).is_ok())
243 }
244
245 #[must_use]
247 pub fn slice(&self, range: Range<usize>) -> Option<SourceTextSlice<'_>> {
248 let carrier = self.carrier.get(range.clone())?;
249 let raw = self.raw_bytes().get(range.clone())?;
250 let start = u32::try_from(range.start).ok()?;
251 let end = u32::try_from(range.end).ok()?;
252 let surrogate_start = self
253 .surrogates
254 .partition_point(|marker| marker.byte_offset < start);
255 let surrogate_end = self
256 .surrogates
257 .partition_point(|marker| marker.byte_offset < end);
258 let invalid_start = self.invalid_bytes.partition_point(|offset| *offset < start);
259 let invalid_end = self.invalid_bytes.partition_point(|offset| *offset < end);
260 Some(SourceTextSlice {
261 raw,
262 carrier,
263 base_byte_offset: start,
264 surrogates: &self.surrogates[surrogate_start..surrogate_end],
265 invalid_bytes: &self.invalid_bytes[invalid_start..invalid_end],
266 })
267 }
268
269 #[must_use]
270 pub fn semantic_utf16_units(&self) -> Option<SourceTextUtf16Units<'_>> {
271 if !self.invalid_bytes.is_empty() {
272 return None;
273 }
274 Some(SourceTextUtf16Units {
275 chars: self.carrier.char_indices(),
276 base_byte_offset: 0,
277 surrogates: &self.surrogates,
278 marker_index: 0,
279 pending_low_surrogate: None,
280 })
281 }
282
283 pub fn try_to_raw_bytes(&self) -> Result<Vec<u8>, TryReserveError> {
285 self.full_slice().try_to_raw_bytes()
286 }
287
288 pub fn try_to_js_string(&self) -> Result<JsString, JsStringError> {
290 self.full_slice().try_to_js_string()
291 }
292
293 pub fn try_range_to_js_string(
297 &self,
298 range: Range<usize>,
299 ) -> Result<Option<JsString>, JsStringError> {
300 let Some(slice) = self.slice(range) else {
301 return Ok(None);
302 };
303 if slice.has_invalid_bytes() {
304 return Ok(None);
305 }
306 slice.try_to_js_string().map(Some)
307 }
308
309 pub fn try_range_to_raw_bytes(
313 &self,
314 range: Range<usize>,
315 ) -> Result<Option<Vec<u8>>, TryReserveError> {
316 self.slice(range)
317 .map(|slice| slice.try_to_raw_bytes())
318 .transpose()
319 }
320
321 fn full_slice(&self) -> SourceTextSlice<'_> {
322 SourceTextSlice {
323 raw: self.raw_bytes(),
324 carrier: &self.carrier,
325 base_byte_offset: 0,
326 surrogates: &self.surrogates,
327 invalid_bytes: &self.invalid_bytes,
328 }
329 }
330
331 fn invariants_hold(&self) -> bool {
332 if self.raw_bytes().len() != self.carrier.len()
333 || (!self.surrogates.is_empty() || !self.invalid_bytes.is_empty()) && self.raw.is_none()
334 || self
335 .raw
336 .as_deref()
337 .is_some_and(|raw| raw == self.carrier.as_bytes())
338 {
339 return false;
340 }
341 let mut previous_offset = None;
342 let surrogates_hold = self.surrogates.iter().all(|marker| {
343 let offset = marker.byte_offset as usize;
344 let ordered = previous_offset.is_none_or(|previous| previous < marker.byte_offset);
345 previous_offset = Some(marker.byte_offset);
346 ordered
347 && is_surrogate(marker.unit)
348 && self.carrier.is_char_boundary(offset)
349 && self
350 .carrier
351 .get(offset..)
352 .and_then(|tail| tail.chars().next())
353 == Some(surrogate_carrier(marker.unit))
354 && decode_quickjs_utf8(&self.raw_bytes()[offset..])
355 == Some((u32::from(marker.unit), CARRIER_UTF8_LEN))
356 });
357 let invalid_hold = self.invalid_bytes.windows(2).all(|pair| pair[0] < pair[1])
358 && self.invalid_bytes.iter().all(|offset| {
359 let offset = *offset as usize;
360 let preceding_surrogate = self
361 .surrogates
362 .partition_point(|marker| marker.byte_offset as usize <= offset)
363 .checked_sub(1)
364 .and_then(|index| self.surrogates.get(index));
365 self.carrier.as_bytes().get(offset) == Some(&(INVALID_BYTE_CARRIER as u8))
366 && self.carrier.is_char_boundary(offset)
367 && self
368 .raw
369 .as_deref()
370 .and_then(|raw| raw.get(offset))
371 .is_some_and(|byte| *byte >= 0x80)
372 && preceding_surrogate.is_none_or(|marker| {
373 offset >= marker.byte_offset as usize + CARRIER_UTF8_LEN
374 })
375 });
376 surrogates_hold && invalid_hold
377 }
378}
379
380impl AsRef<str> for SourceText {
381 fn as_ref(&self) -> &str {
382 self.carrier()
383 }
384}
385
386impl From<&str> for SourceText {
387 fn from(source: &str) -> Self {
388 Self::from_utf8(source)
389 }
390}
391
392#[cfg_attr(not(test), allow(dead_code))]
393impl<'a> SourceTextSlice<'a> {
394 #[must_use]
395 pub fn raw_bytes(&self) -> &[u8] {
396 self.raw
397 }
398
399 #[must_use]
400 pub fn carrier(&self) -> &str {
401 self.carrier
402 }
403
404 #[must_use]
405 pub fn base_byte_offset(&self) -> u32 {
406 self.base_byte_offset
407 }
408
409 #[must_use]
410 pub fn has_surrogate_markers(&self) -> bool {
411 !self.surrogates.is_empty()
412 }
413
414 #[must_use]
415 pub fn has_invalid_bytes(&self) -> bool {
416 !self.invalid_bytes.is_empty()
417 }
418
419 #[must_use]
420 pub fn semantic_utf16_units(&self) -> Option<SourceTextUtf16Units<'a>> {
421 if self.has_invalid_bytes() {
422 return None;
423 }
424 Some(SourceTextUtf16Units {
425 chars: self.carrier.char_indices(),
426 base_byte_offset: self.base_byte_offset,
427 surrogates: self.surrogates,
428 marker_index: 0,
429 pending_low_surrogate: None,
430 })
431 }
432
433 pub fn try_to_js_string(&self) -> Result<JsString, JsStringError> {
434 JsString::try_from_bytes(self.raw)
435 }
436
437 pub fn try_to_raw_bytes(&self) -> Result<Vec<u8>, TryReserveError> {
438 let mut output = Vec::new();
439 output.try_reserve_exact(self.raw.len())?;
440 output.extend_from_slice(self.raw);
441 Ok(output)
442 }
443}
444
445impl Iterator for SourceTextUtf16Units<'_> {
446 type Item = u16;
447
448 fn next(&mut self) -> Option<Self::Item> {
449 if let Some(unit) = self.pending_low_surrogate.take() {
450 return Some(unit);
451 }
452
453 let (relative_offset, ch) = self.chars.next()?;
454 let absolute_offset = self.base_byte_offset + relative_offset as u32;
455 if self
456 .surrogates
457 .get(self.marker_index)
458 .is_some_and(|marker| marker.byte_offset == absolute_offset)
459 {
460 let marker = self.surrogates[self.marker_index];
461 self.marker_index += 1;
462 debug_assert_eq!(ch, surrogate_carrier(marker.unit));
463 return Some(marker.unit);
464 }
465
466 let mut encoded = [0_u16; 2];
467 let encoded = ch.encode_utf16(&mut encoded);
468 if encoded.len() == 2 {
469 self.pending_low_surrogate = Some(encoded[1]);
470 }
471 Some(encoded[0])
472 }
473}
474
475impl FusedIterator for SourceTextUtf16Units<'_> {}
476
477const fn is_surrogate(unit: u16) -> bool {
478 unit >= HIGH_SURROGATE_START && unit <= LOW_SURROGATE_END
479}
480
481fn surrogate_carrier(unit: u16) -> char {
482 let code_point = CARRIER_START + (u32::from(unit) - u32::from(HIGH_SURROGATE_START));
483 char::from_u32(code_point).expect("surrogate carrier is a private-use scalar")
484}
485
486#[cfg(test)]
487mod tests {
488 use super::*;
489
490 #[test]
491 fn ordinary_utf8_is_an_identity_carrier() {
492 let original = "ASCII\0\u{7f}\u{feff}Γ©\u{e000}δΈπ\r\n";
493 let source = SourceText::from_utf8(original);
494
495 assert_eq!(source.carrier(), original);
496 assert!(source.raw.is_none());
497 assert!(!source.has_surrogate_markers());
498 assert!(source.surrogate_markers().is_empty());
499 assert_eq!(source.try_to_raw_bytes().unwrap(), original.as_bytes());
500 assert_eq!(source.as_ref(), original);
501 assert_eq!(
502 source.try_to_js_string().unwrap(),
503 JsString::try_from_utf8(original).unwrap()
504 );
505 }
506
507 #[test]
508 fn raw_scalars_share_the_identity_storage_path() {
509 let raw = b"plain\0\x7f\xef\xbb\xbf\xee\x80\x80\xf0\x9f\x98\x80";
510 let source = SourceText::try_from_raw_bytes(raw).unwrap();
511
512 assert!(source.raw.is_none());
513 assert_eq!(source.carrier().as_bytes(), raw);
514 assert_eq!(source.raw_bytes(), raw);
515 assert!(source.surrogate_markers().is_empty());
516 assert!(source.invalid_bytes.is_empty());
517 }
518
519 #[test]
520 fn surrogate_bytes_use_same_width_marked_carriers_without_pua_collision() {
521 let units = [0xd800, 0xe000, 0xdc00, 0xe7ff, 0xdfff];
522 let original = JsString::try_from_utf16(units).unwrap();
523 let source = SourceText::try_from_js_string(&original).unwrap();
524
525 assert_eq!(source.carrier().chars().count(), units.len());
526 assert_eq!(source.carrier().len(), CARRIER_UTF8_LEN * units.len());
527 assert_eq!(
528 source
529 .surrogate_markers()
530 .iter()
531 .map(|marker| (marker.byte_offset(), marker.unit()))
532 .collect::<Vec<_>>(),
533 vec![(0, 0xd800), (6, 0xdc00), (12, 0xdfff)]
534 );
535 assert_eq!(source.surrogate_at(0), Some(0xd800));
536 assert_eq!(source.surrogate_at(3), None);
537 assert_eq!(source.surrogate_at(6), Some(0xdc00));
538 assert_eq!(source.surrogate_at(12), Some(0xdfff));
539 assert_eq!(
540 source.semantic_utf16_units().unwrap().collect::<Vec<_>>(),
541 units
542 );
543 assert_eq!(source.try_to_js_string().unwrap(), original);
544 assert_eq!(
545 source.try_to_raw_bytes().unwrap(),
546 original.try_to_wtf8_bytes().unwrap()
547 );
548 }
549
550 #[test]
551 fn cesu8_pairs_remain_two_markers_and_exact_raw_bytes() {
552 let raw = [0xed, 0xa0, 0xbd, 0xed, 0xb8, 0x80];
553 let source = SourceText::try_from_raw_bytes(&raw).unwrap();
554
555 assert_eq!(source.carrier().len(), raw.len());
556 assert_eq!(source.raw_bytes(), raw);
557 assert_eq!(
558 source.semantic_utf16_units().unwrap().collect::<Vec<_>>(),
559 [0xd83d, 0xde00]
560 );
561 assert_eq!(
562 source
563 .surrogate_markers()
564 .iter()
565 .map(|marker| (marker.byte_offset(), marker.unit()))
566 .collect::<Vec<_>>(),
567 [(0, 0xd83d), (3, 0xde00)]
568 );
569 }
570
571 #[test]
572 fn malformed_bytes_use_distinct_equal_width_del_markers() {
573 let raw = [b'a', 0x7f, 0x80, 0xc0, 0x80, 0xf4, 0x90, 0x80, 0x80, b'z'];
574 let source = SourceText::try_from_raw_bytes(&raw).unwrap();
575
576 assert_eq!(source.raw_bytes(), raw);
577 assert_eq!(source.carrier().len(), raw.len());
578 assert_eq!(
579 source.carrier().as_bytes(),
580 b"a\x7f\x7f\x7f\x7f\x7f\x7f\x7f\x7fz"
581 );
582 assert!(!source.invalid_byte_at(1));
583 assert_eq!(source.invalid_bytes.as_ref(), &[2, 3, 4, 5, 6, 7, 8]);
584 for offset in 2..=8 {
585 assert!(source.invalid_byte_at(offset));
586 }
587 assert!(source.semantic_utf16_units().is_none());
588 assert_eq!(source.try_range_to_js_string(0..raw.len()).unwrap(), None);
589 assert_eq!(source.try_to_raw_bytes().unwrap(), raw);
590 assert_eq!(
591 source
592 .try_to_js_string()
593 .unwrap()
594 .utf16_units()
595 .collect::<Vec<_>>(),
596 [0x61, 0x7f, 0xfffd, 0xfffd, 0x7a]
597 );
598 }
599
600 #[test]
601 fn valid_surrogate_pairs_become_scalars_and_lone_neighbors_remain_marked() {
602 let units = [0xd800, 0xd83d, 0xde80, 0xdc00, 0xdbff, 0xdfff];
603 let original = JsString::try_from_utf16(units).unwrap();
604 let source = SourceText::try_from_utf16(units).unwrap();
605
606 assert_eq!(source.carrier().chars().count(), 4);
607 assert_eq!(
608 source.carrier().chars().collect::<Vec<_>>(),
609 vec![
610 surrogate_carrier(0xd800),
611 'π',
612 surrogate_carrier(0xdc00),
613 'τΏΏ'
614 ]
615 );
616 assert_eq!(
617 source.semantic_utf16_units().unwrap().collect::<Vec<_>>(),
618 units
619 );
620 assert_eq!(source.try_to_js_string().unwrap(), original);
621 assert_eq!(
622 source.try_to_raw_bytes().unwrap(),
623 original.try_to_wtf8_bytes().unwrap()
624 );
625 }
626
627 #[test]
628 fn semantic_slices_recover_original_units_and_wtf8() {
629 let units = [0x61, 0xd800, 0x62, 0xe000, 0xd83d, 0xde80, 0xdc00, 0x63];
630 let source = SourceText::try_from_utf16(units).unwrap();
631 let slice = source.slice(1..15).unwrap();
632
633 assert_eq!(slice.base_byte_offset(), 1);
634 assert_eq!(slice.carrier(), &source.carrier()[1..15]);
635 assert!(slice.has_surrogate_markers());
636 assert!(!slice.has_invalid_bytes());
637 assert_eq!(
638 slice.semantic_utf16_units().unwrap().collect::<Vec<_>>(),
639 units[1..7]
640 );
641 let expected = JsString::try_from_utf16(units[1..7].iter().copied()).unwrap();
642 assert_eq!(slice.try_to_js_string().unwrap(), expected);
643 assert_eq!(
644 slice.try_to_raw_bytes().unwrap(),
645 expected.try_to_wtf8_bytes().unwrap()
646 );
647 assert_eq!(
648 source.try_range_to_js_string(1..15).unwrap(),
649 Some(expected.clone())
650 );
651 assert_eq!(
652 source.try_range_to_raw_bytes(1..15).unwrap(),
653 Some(expected.try_to_wtf8_bytes().unwrap())
654 );
655 assert!(source.slice(2..15).is_none());
656 assert!(
657 source
658 .try_range_to_js_string(0..usize::MAX)
659 .unwrap()
660 .is_none()
661 );
662 }
663
664 #[test]
665 fn surrogate_pair_detection_crosses_js_string_rope_leaf_boundaries() {
666 let mut left_units = vec![u16::from(b'a'); 8192];
667 left_units.push(0xd83d);
668 let left = JsString::try_from_utf16(left_units).unwrap();
669 let right = JsString::try_from_utf16(
670 [0xde80, 0xd800, u16::from(b'b')]
671 .into_iter()
672 .chain(std::iter::repeat_n(u16::from(b'c'), 512)),
673 )
674 .unwrap();
675 let rope = left.try_concat(&right).unwrap();
676 let source = SourceText::try_from_js_string(&rope).unwrap();
677
678 assert_eq!(source.carrier().get(8192..8196), Some("π"));
679 assert_eq!(source.surrogate_at(8196), Some(0xd800));
680 assert_eq!(source.try_to_js_string().unwrap(), rope);
681 assert_eq!(
682 source.try_to_raw_bytes().unwrap(),
683 rope.try_to_wtf8_bytes().unwrap()
684 );
685 }
686
687 #[test]
688 fn raw_slices_preserve_malformed_bytes_and_quickjs_string_decode() {
689 let source = SourceText::try_from_raw_bytes(b"a/*\x80X*/z").unwrap();
690 let slice = source.slice(1..7).unwrap();
691
692 assert_eq!(slice.raw_bytes(), b"/*\x80X*/");
693 assert!(slice.has_invalid_bytes());
694 assert_eq!(slice.try_to_raw_bytes().unwrap(), b"/*\x80X*/");
695 assert_eq!(
696 slice
697 .try_to_js_string()
698 .unwrap()
699 .utf16_units()
700 .collect::<Vec<_>>(),
701 [0x2f, 0x2a, 0xfffd, 0x2a, 0x2f]
702 );
703 }
704}