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